28#include "catalog/pg_type.h"
29#include "utils/array.h"
30#include "utils/uuid.h"
41#include <unordered_map>
54struct NotRebuildable {};
66std::vector<pg_uuid_t> make_system(
const std::vector<pg_uuid_t> &unknowns,
67 const std::vector<pg_uuid_t> &rhs)
69 std::vector<pg_uuid_t> wires(unknowns);
70 wires.insert(wires.end(), rhs.begin(), rhs.end());
71 std::string name =
"fixsystem{";
72 for(std::size_t k = 0; k < wires.size(); ++k)
79 std::vector<pg_uuid_t> result;
80 for(std::size_t k = 0; k < unknowns.size(); ++k) {
81 const pg_uuid_t p = fixpoint_address(sys, k + 1);
89std::vector<pg_uuid_t> resolve(
pg_uuid_t sys_token)
114 const std::size_t n = w.size() / 2;
116 std::unordered_map<gate_t, std::size_t> unknown;
117 for(std::size_t i = 0; i < n; ++i)
118 unknown.emplace(w[i], i);
123 std::unordered_map<gate_t, std::vector<std::size_t> > reads;
124 std::unordered_map<gate_t, bool> dep;
126 std::vector<gate_t> st(w.begin() + n, w.end());
128 const gate_t u = st.back();
129 if(dep.count(u)) { st.pop_back();
continue; }
130 auto it = unknown.find(u);
131 if(it != unknown.end()) {
132 dep.emplace(u,
true);
133 reads[u] = {it->second};
139 if(!dep.count(ch)) { st.push_back(ch); ready =
false; }
141 std::vector<std::size_t> r;
144 const auto &rc = reads.at(ch);
145 r.insert(r.end(), rc.begin(), rc.end());
147 std::sort(r.begin(), r.end());
148 r.erase(std::unique(r.begin(), r.end()), r.end());
149 dep.emplace(u, !r.empty());
151 reads.emplace(u, std::move(r));
156 std::vector<std::vector<std::size_t> > out(n);
157 std::vector<bool> self_loop(n,
false);
158 for(std::size_t i = 0; i < n; ++i)
160 for(
const auto j : reads.at(w[n + i])) {
167 std::vector<pg_uuid_t> token(n);
168 std::vector<bool> resolved(n,
false);
173 std::unordered_map<gate_t, pg_uuid_t> memo;
177 auto m = memo.find(g);
181 auto it = unknown.find(g);
182 if(it != unknown.end())
185 std::vector<pg_uuid_t> ch;
187 ch.push_back(rebuild(x));
197 throw NotRebuildable();
202 throw NotRebuildable();
206 throw NotRebuildable();
214 for(
const auto &comp : comps) {
217 if(comp.size() == 1 && !self_loop[comp[0]]) {
218 const std::size_t i = comp[0];
219 token[i] = rebuild(w[n + i]);
223 std::vector<pg_uuid_t> unknowns, rhs;
224 for(
const auto i : comp) {
226 rhs.push_back(rebuild(w[n + i]));
228 const auto fix = make_system(unknowns, rhs);
229 for(std::size_t k = 0; k < comp.size(); ++k) {
230 token[comp[k]] = fix[k];
231 resolved[comp[k]] =
true;
234 }
catch(
const NotRebuildable &) {
236 for(std::size_t i = 0; i < n; ++i) {
237 token[i] = fixpoint_address(sys_token, i + 1);
239 &sys_token,
true, i + 1, 0,
nullptr);
257 const pg_uuid_t sys = *DatumGetUUIDP(PG_GETARG_DATUM(0));
258 const std::vector<pg_uuid_t> tokens = resolve(sys);
260 Datum *elems = (Datum *) palloc(
sizeof(Datum) * (tokens.size() ? tokens.size() : 1));
261 for(std::size_t i = 0; i < tokens.size(); ++i) {
264 elems[i] = UUIDPGetDatum(u);
266 PG_RETURN_ARRAYTYPE_P(construct_array(elems, tokens.size(), UUIDOID,
267 UUID_LEN,
false,
'c'));
268 }
catch(
const std::exception &e) {
pg_uuid_t provsqlUuidV5(const std::string &name)
RFC 4122 version-5 UUID in the ProvSQL namespace.
Content-addressed materialisation of a certified d-D into the mmap provenance store.
GenericCircuit getGenericCircuit(pg_uuid_t token)
Build a GenericCircuit from the mmap store rooted at token.
Build in-memory circuits from the mmap-backed persistent store.
gate_t
Strongly-typed gate identifier.
Strongly connected components of the dependency graph of an equation system (a recursive query,...
std::vector< std::vector< std::size_t > > fixSystemComponents(const std::vector< std::vector< std::size_t > > &out)
Strongly connected components of a directed graph, in the order in which equations along its edges ca...
Semiring-agnostic in-memory provenance circuit.
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
gateType getGateType(gate_t g) const
Return the type of gate g.
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
The SIGINT handler installed for the lifetime of the object, the previous one restored as it ends (a ...
Datum resolve_fix_system(PG_FUNCTION_ARGS)
The token of each tuple of the equation system sys, in order.
pg_uuid_t provsql_build_delta(const pg_uuid_t *token)
δ(token), with δ(𝟘) = 𝟘 and δ(𝟙) = 𝟙.
pg_uuid_t provsql_build_monus(const pg_uuid_t *token1, const pg_uuid_t *token2)
token1 ⊖ token2, with X ⊖ X = 𝟘 ⊖ X = 𝟘 and X ⊖ 𝟘 = X.
pg_uuid_t provsql_build_plus(const pg_uuid_t *tokens, int n)
⊕ of n tokens: 𝟘 dropped, none gives 𝟘, one is returned.
pg_uuid_t provsql_build_times(const pg_uuid_t *tokens, int n)
⊗ of n tokens: 𝟙 dropped, none gives 𝟙, one is returned.
The gate builders of the query rewriter, for C/C++ callers.
bool provsql_absorptive_provenance
Derived flag: the session's provenance class is 'absorptive' or 'boolean' – licenses constructions so...
bool provsql_simplify_on_load
Run universal cmp-resolution passes when getGenericCircuit returns; controlled by the provsql....
bool provsql_boolean_provenance
Derived flag: the session's provenance class is 'boolean' – enables the Boolean-only machinery (safe-...
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
void provsql_cancel_if_interrupted(void)
Raise PG's cancel if the evaluation stopped for one; nothing otherwise.
Cancellation of the long C++ evaluation loops.
void provsql_poll_interrupt()
Throw where an evaluation is to stop, its query cancelled.
void provsql_internal_create_gate(const pg_uuid_t *token, gate_type type, unsigned nb_children, const pg_uuid_t *children_data)
Internal entry point behind create_gate(): cache + worker IPC.
void provsql_internal_create_gate_with(const pg_uuid_t *token, gate_type type, unsigned nb_children, const pg_uuid_t *children, bool has_infos, unsigned info1, unsigned info2, const char *extra)
Create a gate together with its infos and its text, in one message that is not answered.
Background worker and IPC primitives for mmap-backed circuit storage.
Core types, constants, and utilities shared across ProvSQL.
@ gate_fixpoint
Component of the least solution of an equation system: one wire to a gate_fixsystem,...
@ gate_fixsystem
Linear equation system x_i = f_i(x) of a recursive query, one equation per derived tuple: wires [x_1,...
pg_uuid_t string2uuid(const string &source)
Parse a UUID string into a pg_uuid_t.
string uuid2string(pg_uuid_t uuid)
Format a pg_uuid_t as a std::string.
C++ utility functions for UUID manipulation.