ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
Regex.h
Go to the documentation of this file.
1/**
2 * @file semiring/Regex.h
3 * @brief Regular-expression semiring: the derivations of a tuple as a
4 * language over the labels of its input tuples.
5 *
6 * The semiring of regular languages over an alphabet of labels, with
7 * @f$\oplus@f$ union, @f$\otimes@f$ concatenation, @f$\mathbb{0} =
8 * \emptyset@f$ and @f$\mathbb{1} = \{\varepsilon\}@f$, each language
9 * written as a regular expression. Concatenation does not commute: a
10 * product gate concatenates its factors in the order of the query, that of
11 * the @c FROM clause for a join, so that a path query reads its paths in
12 * the order it extends them.
13 *
14 * Every value has a star, the Kleene star, which makes the regular
15 * expression of a recursion on cyclic data its exact least solution: the
16 * equations are solved by Gaussian elimination (state elimination, in
17 * automata terms), provided the recursive relation is on the same side of
18 * every coefficient (see @c GenericCircuit::solveFixSystem).
19 *
20 * Operations:
21 * - @c zero() → @f$\emptyset@f$
22 * - @c one() → @f$\varepsilon@f$
23 * - @c plus() → @c "a | b", alternatives that render alike merged
24 * - @c times() → @c "a · b"
25 * - @c star() → @c "(a)*"
26 *
27 * Equality is syntactic: two expressions of the same language may compare
28 * unequal, which only leaves an alternative unmerged.
29 *
30 * @see https://provsql.org/lean-docs/Provenance/Semirings/Regex.html
31 * Lean 4 verified instance: @c Language.instSemiringWithMonus, whose
32 * monus, the difference of languages, this implementation does not
33 * compute; with proofs of @c Language.not_commutative,
34 * @c Language.not_absorptive, @c Language.not_exclusive,
35 * @c Language.complemented_of and of the star identities
36 * (@c Language.kstar_one_add, @c Language.kstar_kstar).
37 */
38#ifndef REGEX_H
39#define REGEX_H
40
41#include <cstddef>
42#include <functional>
43#include <memory>
44#include <string>
45#include <vector>
46
47#include "Semiring.h"
48#include "../Circuit.h"
49
50namespace semiring {
51
52struct regex_node;
53
54/**
55 * @brief A regular expression: an immutable tree, shared between the
56 * expressions built from it.
57 *
58 * Copying an expression, or concatenating two, copies no text: the text is
59 * rendered only once, by @c render(), for a result. Unions and
60 * concatenations are kept flat, so that a union of unions is one union,
61 * without an alternative already present.
62 */
63struct regex_t {
64 /** @brief The operator at the root of the expression. */
65 enum Kind : unsigned char { EMPTY, EPSILON, ATOM, STAR, CONCAT, UNION };
66 std::shared_ptr<const regex_node> node; ///< The root; null for ∅
67
68 inline Kind kind() const;
69 inline std::size_t hash() const;
70 /** @brief Syntactic equality. */
71 inline bool operator==(const regex_t &o) const;
72 /** @brief Syntactic inequality. */
73 bool operator!=(const regex_t &o) const {
74 return !(*this == o);
75 }
76 /** @brief The expression, as text. */
77 std::string render() const {
78 std::string out;
79 render(out);
80 return out;
81 }
82 /** @brief Append the expression, as text, to @p out. */
83 inline void render(std::string &out) const;
84};
85
86/** @brief A node of a @c regex_t. */
87struct regex_node {
88 regex_t::Kind kind; ///< Its operator
89 std::string label; ///< The label of an ATOM
90 std::vector<regex_t> kids; ///< The operands of STAR, CONCAT and UNION
91 std::size_t hash; ///< Of the whole expression
92};
93
95 return node ? node->kind : EMPTY;
96}
97
98std::size_t regex_t::hash() const {
99 return node ? node->hash : 0;
100}
101
102bool regex_t::operator==(const regex_t &o) const {
103 if(node == o.node)
104 return true;
105 if(!node || !o.node || node->hash != o.node->hash ||
106 node->kind != o.node->kind || node->label != o.node->label ||
107 node->kids.size() != o.node->kids.size())
108 return false;
109 for(std::size_t i = 0; i < node->kids.size(); ++i)
110 if(node->kids[i] != o.node->kids[i])
111 return false;
112 return true;
113}
114
115void regex_t::render(std::string &out) const {
116 switch(kind()) {
117 case EMPTY: out += "∅"; return;
118 case EPSILON: out += "ε"; return;
119 case ATOM: out += node->label; return;
120 case UNION:
121 case CONCAT: {
122 const char *sep = kind() == UNION ? " | " : " · ";
123 bool first = true;
124 for(const auto &k : node->kids) {
125 if(!first)
126 out += sep;
127 first = false;
128 /* A union is an operand of a concatenation in parentheses. */
129 if(kind() == CONCAT && k.kind() == UNION) {
130 out += "(";
131 k.render(out);
132 out += ")";
133 } else
134 k.render(out);
135 }
136 return;
137 }
138 case STAR: {
139 const regex_t &k = node->kids[0];
140 /* No parentheses around a single code point. */
141 bool bare = false;
142 if(k.kind() == ATOM && !k.node->label.empty()) {
143 bare = true;
144 const std::string &t = k.node->label;
145 for(std::size_t i = 1; i < t.size(); ++i)
146 if(((unsigned char) t[i] & 0xC0) != 0x80)
147 bare = false;
148 }
149 if(bare)
150 out += k.node->label;
151 else {
152 out += "(";
153 k.render(out);
154 out += ")";
155 }
156 out += "*";
157 return;
158 }
159 }
160}
161
162/**
163 * @brief Operations on regular expressions, shared by @c Regex and
164 * @c TropicalPaths.
165 */
166struct regex_ops {
167 /** @brief A node of kind @p k. */
168 static regex_t make(regex_t::Kind k, std::string label,
169 std::vector<regex_t> kids) {
170 std::size_t h = std::hash<std::string>()(label) * 31 + k + 1;
171 for(const auto &x : kids)
172 h = h * 1000003 ^ x.hash();
173 regex_t r;
174 r.node = std::make_shared<const regex_node>(
175 regex_node{k, std::move(label), std::move(kids), h});
176 return r;
177 }
178
179 /** @brief A one-letter language; @f$\varepsilon@f$ for an empty label. */
180 static regex_t atom(const std::string &label) {
181 return make(label.empty() ? regex_t::EPSILON : regex_t::ATOM, label, {});
182 }
183
184 /** @brief The union of @p v. */
185 static regex_t plus(const std::vector<regex_t> &v) {
186 std::vector<regex_t> alts;
187 bool epsilon = false, starred = false;
188 const auto add = [&](const regex_t &a) {
189 switch(a.kind()) {
190 case regex_t::EMPTY:
191 return;
192 case regex_t::EPSILON:
193 epsilon = true;
194 return;
195 case regex_t::STAR:
196 starred = true;
197 break;
198 default:
199 break;
200 }
201 for(const auto &b : alts)
202 if(a == b)
203 return;
204 alts.push_back(a);
205 };
206 for(const auto &x : v)
207 if(x.kind() == regex_t::UNION)
208 for(const auto &a : x.node->kids)
209 add(a);
210 else
211 add(x);
212 if(alts.empty())
213 return epsilon ? atom("") : regex_t();
214 /* ε is in every starred expression already. */
215 if(epsilon && !starred)
216 alts.insert(alts.begin(), atom(""));
217 if(alts.size() == 1)
218 return alts[0];
219 return make(regex_t::UNION, "", std::move(alts));
220 }
221
222 /** @brief The concatenation of @p v, in this order. */
223 static regex_t times(const std::vector<regex_t> &v) {
224 std::vector<regex_t> factors;
225 for(const auto &x : v)
226 switch(x.kind()) {
227 case regex_t::EMPTY:
228 return regex_t();
229 case regex_t::EPSILON:
230 break;
231 case regex_t::CONCAT:
232 factors.insert(factors.end(), x.node->kids.begin(),
233 x.node->kids.end());
234 break;
235 default:
236 factors.push_back(x);
237 }
238 if(factors.empty())
239 return atom("");
240 if(factors.size() == 1)
241 return factors[0];
242 return make(regex_t::CONCAT, "", std::move(factors));
243 }
244
245 /** @brief The Kleene star of @p a. */
246 static regex_t star(const regex_t &a) {
247 switch(a.kind()) {
248 case regex_t::EMPTY:
249 case regex_t::EPSILON:
250 return atom("");
251 case regex_t::STAR:
252 return a;
253 case regex_t::UNION: {
254 /* (ε | a)* = a* */
255 std::vector<regex_t> alts;
256 for(const auto &x : a.node->kids)
257 if(x.kind() != regex_t::EPSILON)
258 alts.push_back(x);
259 if(alts.size() == 1)
260 return star(alts[0]);
261 if(alts.size() < a.node->kids.size())
262 return make(regex_t::STAR, "",
263 {make(regex_t::UNION, "", std::move(alts))});
264 break;
265 }
266 default:
267 break;
268 }
269 return make(regex_t::STAR, "", {a});
270 }
271};
272
273/**
274 * @brief The regular-expression semiring over @c regex_t.
275 *
276 * Input tuples are read from the mapping as their labels, an empty label
277 * standing for @f$\varepsilon@f$.
278 */
279class Regex : public semiring::Semiring<regex_t>
280{
281public:
282virtual value_type zero() const override {
283 return regex_t();
284}
285virtual value_type one() const override {
286 return regex_ops::atom("");
287}
288virtual value_type plus(const std::vector<value_type> &v) const override {
289 return regex_ops::plus(v);
290}
291virtual value_type times(const std::vector<value_type> &v) const override {
292 return regex_ops::times(v);
293}
294virtual value_type monus(value_type, value_type) const override {
295 throw CircuitRefusal(
296 PROVSQL_GAP, "semiring-no-monus",
297 "The regular-expression semiring computes no monus (outer "
298 "joins, EXCEPT and NOT EXISTS need one): its monus, the "
299 "difference of languages, needs automata to compute, and would "
300 "not register an absence (1 minus a language without the empty "
301 "word is 1).");
302}
303virtual value_type delta(value_type x) const override {
304 return x.kind() == regex_t::EMPTY ? zero() : one();
305}
306/** @brief Union is idempotent. */
307virtual bool idempotent() const override {
308 return true;
309}
310/** @brief Concatenation does not commute. */
311virtual bool commutative() const override {
312 return false;
313}
314/** @brief Every language has a Kleene star. */
315virtual bool has_star() const override {
316 return true;
317}
318virtual value_type star(const value_type &a) const override {
319 return regex_ops::star(a);
320}
321/** @brief Equality is syntactic. */
322virtual bool exact_equality() const override {
323 return false;
324}
325value_type parse_leaf(const char *v) const {
326 return regex_ops::atom(v);
327}
328/** @brief The expression, as text. */
329std::string to_text(const value_type &v) const {
330 return v.render();
331}
332};
333
334}
335
336#endif /* REGEX_H */
Generic directed-acyclic-graph circuit template and gate identifier.
Abstract semiring interface for provenance evaluation.
A refusal by design, or a known gap, rather than an error.
Definition Circuit.h:409
The regular-expression semiring over regex_t.
Definition Regex.h:280
virtual value_type zero() const override
Return the additive identity .
Definition Regex.h:282
virtual bool exact_equality() const override
Equality is syntactic.
Definition Regex.h:322
virtual value_type one() const override
Return the multiplicative identity .
Definition Regex.h:285
virtual bool idempotent() const override
Union is idempotent.
Definition Regex.h:307
virtual value_type delta(value_type x) const override
Apply the operator.
Definition Regex.h:303
virtual bool has_star() const override
Every language has a Kleene star.
Definition Regex.h:315
value_type parse_leaf(const char *v) const
Definition Regex.h:325
virtual value_type star(const value_type &a) const override
, the sum of the powers of a.
Definition Regex.h:318
virtual value_type times(const std::vector< value_type > &v) const override
Apply the multiplicative operation to a list of values.
Definition Regex.h:291
virtual value_type plus(const std::vector< value_type > &v) const override
Apply the additive operation to a list of values.
Definition Regex.h:288
std::string to_text(const value_type &v) const
The expression, as text.
Definition Regex.h:329
virtual value_type monus(value_type, value_type) const override
Apply the monus (m-semiring difference) operation.
Definition Regex.h:294
virtual bool commutative() const override
Concatenation does not commute.
Definition Regex.h:311
Abstract base class for (m-)semirings.
Definition Semiring.h:119
#define PROVSQL_GAP
A node of a regex_t.
Definition Regex.h:87
std::vector< regex_t > kids
The operands of STAR, CONCAT and UNION.
Definition Regex.h:90
std::string label
The label of an ATOM.
Definition Regex.h:89
regex_t::Kind kind
Its operator.
Definition Regex.h:88
std::size_t hash
Of the whole expression.
Definition Regex.h:91
Operations on regular expressions, shared by Regex and TropicalPaths.
Definition Regex.h:166
static regex_t atom(const std::string &label)
A one-letter language; for an empty label.
Definition Regex.h:180
static regex_t plus(const std::vector< regex_t > &v)
The union of v.
Definition Regex.h:185
static regex_t star(const regex_t &a)
The Kleene star of a.
Definition Regex.h:246
static regex_t times(const std::vector< regex_t > &v)
The concatenation of v, in this order.
Definition Regex.h:223
static regex_t make(regex_t::Kind k, std::string label, std::vector< regex_t > kids)
A node of kind k.
Definition Regex.h:168
A regular expression: an immutable tree, shared between the expressions built from it.
Definition Regex.h:63
bool operator!=(const regex_t &o) const
Syntactic inequality.
Definition Regex.h:73
Kind
The operator at the root of the expression.
Definition Regex.h:65
std::size_t hash() const
Definition Regex.h:98
bool operator==(const regex_t &o) const
Syntactic equality.
Definition Regex.h:102
std::string render() const
The expression, as text.
Definition Regex.h:77
Kind kind() const
Definition Regex.h:94
std::shared_ptr< const regex_node > node
The root; null for ∅
Definition Regex.h:66