ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
Circuit.h
Go to the documentation of this file.
1/**
2 * @file Circuit.h
3 * @brief Generic directed-acyclic-graph circuit template and gate identifier.
4 *
5 * This header provides two central abstractions:
6 *
7 * ### @c gate_t
8 * A strongly-typed wrapper around @c size_t used as a compact gate
9 * identifier within a circuit. Using a distinct type prevents accidental
10 * mixing of gate IDs with plain integers. Helper operators (increment,
11 * comparison, stream I/O, @c to_string) make it convenient to use in
12 * loops and containers.
13 *
14 * ### @c Circuit<gateType>
15 * A template base class parameterised by gate type, inherited by all
16 * circuit variants in ProvSQL (@c BooleanCircuit, @c GenericCircuit,
17 * @c DotCircuit, @c WhereCircuit).
18 * A circuit is a directed acyclic graph where:
19 * - Each **gate** has a type drawn from @c gateType (a user-supplied enum).
20 * - **Wires** are directed edges from parent gates to their children.
21 * - Each gate may optionally be associated with a UUID, enabling
22 * round-tripping between the in-memory circuit and the persistent mmap
23 * representation. The UUID is kept as its 16 bytes (@c gate_uuid);
24 * the few gates built in memory under another name keep it as a string.
25 *
26 * @c Circuit.hpp (included by subclass headers) provides the out-of-line
27 * template method implementations.
28 *
29 * ### @c CircuitException
30 * Exception type thrown when a circuit operation fails (e.g. UUID not
31 * found, type mismatch).
32 */
33#ifndef CIRCUIT_H
34#define CIRCUIT_H
35
36#include <cstdint>
37#include <string>
38#include <unordered_map>
39#include <unordered_set>
40#include <iostream>
41#include <set>
42#include <utility>
43#include <vector>
44#include <type_traits>
45
46/**
47 * @brief Strongly-typed gate identifier.
48 *
49 * Wraps a @c size_t so that gate IDs are not accidentally used as plain
50 * integers. The underlying value is a zero-based index into the circuit's
51 * gate and wire vectors.
52 */
53enum class gate_t : size_t {};
54
55/**
56 * @brief A UUID as its 16 bytes, read as two big-endian words.
57 *
58 * The key under which a circuit finds a gate from its UUID: hashing and
59 * comparing it touches 16 bytes, where the text form of a UUID has 36.
60 * Keys compare as their bytes do, in order (as @c memcmp would).
61 */
62struct gate_uuid {
63 std::uint64_t hi = 0; ///< The first eight bytes, big-endian
64 std::uint64_t lo = 0; ///< The last eight bytes, big-endian
65
66 /** @brief The UUID whose 16 bytes start at @p p. */
67 static gate_uuid fromBytes(const unsigned char *p) {
68 gate_uuid u;
69 for(int i = 0; i < 8; ++i) {
70 u.hi = (u.hi << 8) | p[i];
71 u.lo = (u.lo << 8) | p[i + 8];
72 }
73 return u;
74 }
75
76 /** @brief Write the 16 bytes of the UUID to @p p. */
77 void toBytes(unsigned char *p) const {
78 for(int i = 0; i < 8; ++i) {
79 p[i] = static_cast<unsigned char>(hi >> (56 - 8 * i));
80 p[i + 8] = static_cast<unsigned char>(lo >> (56 - 8 * i));
81 }
82 }
83
84 /**
85 * @brief Read @p s as a UUID in the text form PostgreSQL prints
86 * (lowercase, @c xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx).
87 *
88 * Any other string, even one PostgreSQL would read as the same UUID,
89 * is refused, so that the text of a name is given back as it came.
90 *
91 * @return @c false if @p s is not in that form.
92 */
93 static bool parse(const std::string &s, gate_uuid &u) {
94 if(s.size() != 36)
95 return false;
96 std::uint64_t w[2] = {0, 0};
97 int n = 0;
98 for(std::size_t i = 0; i < 36; ++i) {
99 const char c = s[i];
100 if(i == 8 || i == 13 || i == 18 || i == 23) {
101 if(c != '-')
102 return false;
103 continue;
104 }
105 unsigned d;
106 if(c >= '0' && c <= '9')
107 d = c - '0';
108 else if(c >= 'a' && c <= 'f')
109 d = c - 'a' + 10;
110 else
111 return false;
112 w[n / 16] = (w[n / 16] << 4) | d;
113 ++n;
114 }
115 u.hi = w[0];
116 u.lo = w[1];
117 return true;
118 }
119
120 /** @brief The text form of the UUID, as PostgreSQL prints it. */
121 std::string str() const {
122 static const char digits[] = "0123456789abcdef";
123 std::string s(36, '-');
124 std::size_t pos = 0;
125 for(int n = 0; n < 32; ++n) {
126 if(pos == 8 || pos == 13 || pos == 18 || pos == 23)
127 ++pos;
128 const std::uint64_t w = n < 16 ? hi : lo;
129 s[pos++] = digits[(w >> (60 - 4 * (n % 16))) & 0xF];
130 }
131 return s;
132 }
133
134 /** @brief Equality of the 16 bytes. */
135 bool operator==(const gate_uuid &o) const {
136 return hi == o.hi && lo == o.lo;
137 }
138 /** @brief Inequality of the 16 bytes. */
139 bool operator!=(const gate_uuid &o) const {
140 return !(*this == o);
141 }
142 /** @brief The order of the bytes. */
143 bool operator<(const gate_uuid &o) const {
144 return hi != o.hi ? hi < o.hi : lo < o.lo;
145 }
146
147 /** @brief Boost serialisation. */
148 template<class Archive> void serialize(Archive &ar, const unsigned int) {
149 ar & hi & lo;
150 }
151};
152
153/** @brief Hash of a @c gate_uuid: its bytes are already uniformly spread. */
155 /** @brief The hash of @p u. */
156 std::size_t operator()(const gate_uuid &u) const {
157 return static_cast<std::size_t>(u.hi ^ (u.lo * 0x9E3779B97F4A7C15ULL));
158 }
159};
160
161/**
162 * @brief Generic template base class for provenance circuits.
163 *
164 * A @c Circuit stores:
165 * - A vector of gate types indexed by @c gate_t.
166 * - A vector of child-wire lists (also indexed by @c gate_t).
167 * - Maps between gate UUIDs and @c gate_t IDs.
168 *
169 * @tparam gateType Enumeration of gate kinds for this circuit variant.
170 */
171template<class gateType>
172class Circuit {
173public:
174/** @brief UUID type used in this circuit (always @c std::string). */
175using uuid = std::string;
176
177protected:
178/** @brief What a gate is named by, in @c name_kind. */
179enum : unsigned char {
180 NO_NAME, ///< No name
181 UUID_NAME, ///< A UUID, in @c id2uuid
182 OTHER_NAME ///< Another string, in @c id2name
183};
184
185/* Each name is the name of one gate, but a gate redirected to another
186 * (see @c pointName) leaves its name to it: a name -> gate map may send
187 * two names to one gate, which keeps its own name. */
188std::unordered_map<gate_uuid, gate_t, gate_uuid_hash> uuid2id; ///< UUID → gate index
189std::vector<gate_uuid> id2uuid; ///< UUID of each gate (if @c UUID_NAME)
190std::vector<unsigned char> name_kind; ///< What each gate is named by
191std::unordered_map<std::string, gate_t> name2id; ///< Other name → gate index
192std::unordered_map<gate_t, std::string> id2name; ///< Gate index → other name
193
194/** @brief What gate @p g is named by. */
195unsigned char nameKind(gate_t g) const {
196 const auto i = static_cast<std::underlying_type<gate_t>::type>(g);
197 return i < name_kind.size() ? name_kind[i] : static_cast<unsigned char>(NO_NAME);
198}
199
200/** @brief Name gate @p g by the UUID @p u. */
201void bindName(gate_t g, const gate_uuid &u);
202
203/** @brief Name gate @p g by @p u, a UUID in its text form or another string. */
204void bindName(gate_t g, const uuid &u);
205
206/** @brief Make the name of gate @p g, if any, name gate @p target. */
207void pointName(gate_t g, gate_t target);
208
209/** @brief Remove the name of gate @p g, if any. */
210void dropName(gate_t g);
211
212/** @brief Give the name of gate @p from, if any, to gate @p to. */
213void moveName(gate_t from, gate_t to);
214
215std::vector<gateType> gates; ///< Gate type for each gate
216std::vector<std::vector<gate_t> > wires; ///< Child wire lists for each gate
217
218/**
219 * @brief Update the type of an existing gate.
220 * @param g Gate to update.
221 * @param t New gate type.
222 */
223void setGateType(gate_t g, gateType t)
224{
225 gates[static_cast<std::underlying_type<gate_t>::type>(g)]=t;
226}
227
228protected:
229/**
230 * @brief Allocate a new gate with a default-initialised type.
231 *
232 * Derived classes override this to perform additional initialisation
233 * (e.g. resizing auxiliary vectors).
234 *
235 * @return The @c gate_t identifier of the newly created gate.
236 */
237virtual gate_t addGate();
238
239public:
240Circuit() = default;
241Circuit(const Circuit &) = default;
242Circuit(Circuit &&) = default;
243Circuit &operator=(const Circuit &) = default;
244Circuit &operator=(Circuit &&) = default;
245virtual ~Circuit() {
246}
247
248/**
249 * @brief Return the total number of gates in the circuit.
250 * @return Number of gates.
251 */
252std::vector<gate_t>::size_type getNbGates() const {
253 return gates.size();
254}
255
256/**
257 * @brief Return (or create) the gate associated with UUID @p u.
258 *
259 * If no gate with this UUID exists yet a new gate is allocated via
260 * @c addGate() and the UUID mapping is recorded.
261 *
262 * @param u UUID string.
263 * @return Gate identifier for @p u.
264 */
265gate_t getGate(const uuid &u);
266
267/** @copydoc getGate(const uuid &) */
269 return findOrAddGate(u).first;
270}
271
272/**
273 * @brief Return (or create) the gate associated with UUID @p u, and
274 * whether it was created.
275 */
276std::pair<gate_t, bool> findOrAddGate(const gate_uuid &u);
277
278/**
279 * @brief Return the UUID string associated with gate @p g.
280 * @param g Gate identifier.
281 * @return UUID string, or empty if @p g has no UUID.
282 */
283uuid getUUID(gate_t g) const;
284
285/**
286 * @brief Read the UUID of gate @p g into @p u.
287 * @return @c false if @p g is not named by a UUID.
288 */
289bool getUUID(gate_t g, gate_uuid &u) const {
290 if(nameKind(g) != UUID_NAME)
291 return false;
292 u = id2uuid[static_cast<std::underlying_type<gate_t>::type>(g)];
293 return true;
294}
295
296/**
297 * @brief Return the type of gate @p g.
298 * @param g Gate identifier.
299 * @return The gate's type.
300 */
301gateType getGateType(gate_t g) const
302{
303 return gates[static_cast<std::underlying_type<gate_t>::type>(g)];
304}
305
306/**
307 * @brief Return a mutable reference to the child-wire list of gate @p g.
308 * @param g Gate identifier.
309 * @return Reference to the vector of child gate IDs.
310 */
311std::vector<gate_t> &getWires(gate_t g)
312{
313 return wires[static_cast<std::underlying_type<gate_t>::type>(g)];
314}
315
316/**
317 * @brief Return a const reference to the child-wire list of gate @p g.
318 * @param g Gate identifier.
319 * @return Const reference to the vector of child gate IDs.
320 */
321const std::vector<gate_t> &getWires(gate_t g) const
322{
323 return wires[static_cast<std::underlying_type<gate_t>::type>(g)];
324}
325
326/**
327 * @brief Create or update the gate associated with UUID @p u.
328 *
329 * If the UUID is already mapped the existing gate's type is updated.
330 * Otherwise a new gate is allocated.
331 *
332 * @param u UUID string to associate with the gate.
333 * @param type Gate type.
334 * @return Gate identifier.
335 */
336virtual gate_t setGate(const uuid &u, gateType type);
337
338/**
339 * @brief Allocate a new gate with type @p type and no UUID.
340 * @param type Gate type.
341 * @return Gate identifier.
342 */
343virtual gate_t setGate(gateType type);
344
345/**
346 * @brief Test whether a gate with UUID @p u exists.
347 * @param u UUID string.
348 * @return @c true if a gate with this UUID is present.
349 */
350bool hasGate(const uuid &u) const;
351
352/** @copydoc hasGate(const uuid &) const */
353bool hasGate(const gate_uuid &u) const {
354 return uuid2id.find(u) != uuid2id.end();
355}
356
357/**
358 * @brief Add a directed wire from gate @p f (parent) to gate @p t (child).
359 * @param f Source (parent) gate.
360 * @param t Target (child) gate.
361 */
362void addWire(gate_t f, gate_t t);
363
364/**
365 * @brief Return a textual description of gate @p g for debugging.
366 *
367 * Pure virtual; each concrete circuit class provides its own formatting.
368 *
369 * @param g Gate to describe.
370 * @return Human-readable string.
371 */
372virtual std::string toString(gate_t g) const = 0;
373};
374
375/**
376 * @brief Exception type thrown by circuit operations on invalid input.
377 *
378 * Thrown when, for example, a UUID is not found in the circuit or a
379 * type constraint is violated.
380 */
381class CircuitException : public std::exception
382{
383std::string message; ///< Human-readable description of the error
384
385public:
386/**
387 * @brief Construct with a descriptive error message.
388 * @param m Error message string.
389 */
390CircuitException(const std::string &m) : message(m) {
391}
392/**
393 * @brief Return the error message as a C-string.
394 * @return Null-terminated error description.
395 */
396virtual char const * what() const noexcept {
397 return message.c_str();
398}
399};
400
401/**
402 * @brief A refusal by design, or a known gap, rather than an error.
403 *
404 * Reported to the client as a ProvSQL refusal (SQLSTATE @c 0A000, with a
405 * @c provsql-reason tag and its scope; see @c provsql_unsupported), so
406 * that tooling can tell it from an internal fault.
407 */
409{
410const char *scope_; ///< @c PROVSQL_DELIBERATE, @c PROVSQL_GAP, ...
411const char *tag_; ///< Stable short tag of the refusal
412
413public:
414/**
415 * @brief Construct a refusal.
416 * @param scope Its kind (@c PROVSQL_DELIBERATE, @c PROVSQL_GAP, ...).
417 * @param tag Its stable short tag.
418 * @param m The message a user reads.
419 */
420CircuitRefusal(const char *scope, const char *tag, const std::string &m)
422}
423/** @brief The kind of the refusal. */
424const char *scope() const noexcept {
425 return scope_;
426}
427/** @brief The tag of the refusal. */
428const char *tag() const noexcept {
429 return tag_;
430}
431};
432
433/**
434 * @brief Pre-increment operator for @c gate_t.
435 * @param g Gate to increment.
436 * @return Reference to the incremented gate.
437 */
439 return g=gate_t{static_cast<std::underlying_type<gate_t>::type>(g)+1};
440}
441
442/**
443 * @brief Compare a @c gate_t against a @c std::vector size type.
444 * @param t Gate identifier.
445 * @param u Vector size to compare against.
446 * @return @c true if the underlying integer of @p t is less than @p u.
447 */
448inline bool operator<(gate_t t, std::vector<gate_t>::size_type u)
449{
450 return static_cast<std::underlying_type<gate_t>::type>(t)<u;
451}
452
453/**
454 * @brief Convert a @c gate_t to its decimal string representation.
455 * @param g Gate identifier.
456 * @return Decimal string of the underlying integer.
457 */
458inline std::string to_string(gate_t g) {
459 return std::to_string(static_cast<std::underlying_type<gate_t>::type>(g));
460}
461
462/**
463 * @brief Read a @c gate_t from an input stream.
464 * @param i Input stream.
465 * @param g Gate to populate.
466 * @return Reference to @p i.
467 */
468inline std::istream &operator>>(std::istream &i, gate_t &g)
469{
470 std::underlying_type<gate_t>::type u;
471 i >> u;
472 g=gate_t{u};
473 return i;
474}
475
476/**
477 * @brief Write a @c gate_t to an output stream as its decimal value.
478 * @param o Output stream.
479 * @param g Gate identifier to write.
480 * @return Reference to @p o.
481 */
482inline std::ostream &operator<<(std::ostream &o, gate_t g)
483{
484 return o << static_cast<std::underlying_type<gate_t>::type>(g);
485}
486
487#endif /* CIRCUIT_H */
std::istream & operator>>(std::istream &i, gate_t &g)
Read a gate_t from an input stream.
Definition Circuit.h:468
gate_t & operator++(gate_t &g)
Pre-increment operator for gate_t.
Definition Circuit.h:438
std::ostream & operator<<(std::ostream &o, gate_t g)
Write a gate_t to an output stream as its decimal value.
Definition Circuit.h:482
bool operator<(gate_t t, std::vector< gate_t >::size_type u)
Compare a gate_t against a std::vector size type.
Definition Circuit.h:448
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
std::string to_string(gate_t g)
Convert a gate_t to its decimal string representation.
Definition Circuit.h:458
std::string message
Human-readable description of the error.
Definition Circuit.h:383
virtual char const * what() const noexcept
Return the error message as a C-string.
Definition Circuit.h:396
CircuitException(const std::string &m)
Construct with a descriptive error message.
Definition Circuit.h:390
const char * scope_
PROVSQL_DELIBERATE, PROVSQL_GAP, ...
Definition Circuit.h:410
const char * scope() const noexcept
The kind of the refusal.
Definition Circuit.h:424
CircuitRefusal(const char *scope, const char *tag, const std::string &m)
Construct a refusal.
Definition Circuit.h:420
const char * tag_
Stable short tag of the refusal.
Definition Circuit.h:411
const char * tag() const noexcept
The tag of the refusal.
Definition Circuit.h:428
unsigned char nameKind(gate_t g) const
What gate g is named by.
Definition Circuit.h:195
Circuit()=default
std::vector< unsigned char > name_kind
What each gate is named by.
Definition Circuit.h:190
std::string uuid
UUID type used in this circuit (always std::string).
Definition Circuit.h:175
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
Definition Circuit.h:311
@ UUID_NAME
A UUID, in id2uuid.
Definition Circuit.h:181
@ OTHER_NAME
Another string, in id2name.
Definition Circuit.h:182
@ NO_NAME
No name.
Definition Circuit.h:180
gateType getGateType(gate_t g) const
Return the type of gate g.
Definition Circuit.h:301
gate_t getGate(const gate_uuid &u)
Return (or create) the gate associated with UUID u.
Definition Circuit.h:268
Circuit & operator=(const Circuit &)=default
void dropName(gate_t g)
Remove the name of gate g, if any.
Definition Circuit.hpp:127
const std::vector< gate_t > & getWires(gate_t g) const
Return a const reference to the child-wire list of gate g.
Definition Circuit.h:321
bool hasGate(const gate_uuid &u) const
Test whether a gate with UUID u exists.
Definition Circuit.h:353
virtual gate_t setGate(const uuid &u, gateType type)
Create or update the gate associated with UUID u.
Definition Circuit.hpp:187
Circuit(const Circuit &)=default
virtual std::string toString(gate_t g) const =0
Return a textual description of gate g for debugging.
void addWire(gate_t f, gate_t t)
Add a directed wire from gate f (parent) to gate t (child).
Definition Circuit.hpp:195
std::unordered_map< gate_uuid, gate_t, gate_uuid_hash > uuid2id
UUID → gate index.
Definition Circuit.h:188
std::unordered_map< gate_t, std::string > id2name
Gate index → other name.
Definition Circuit.h:192
void setGateType(gate_t g, gateType t)
Update the type of an existing gate.
Definition Circuit.h:223
Circuit & operator=(Circuit &&)=default
void pointName(gate_t g, gate_t target)
Make the name of gate g, if any, name gate target.
Definition Circuit.hpp:111
std::vector< gateType > gates
Gate type for each gate.
Definition Circuit.h:215
virtual ~Circuit()
Definition Circuit.h:245
std::vector< gate_uuid > id2uuid
UUID of each gate (if UUID_NAME).
Definition Circuit.h:189
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
Definition Circuit.hpp:65
std::vector< std::vector< gate_t > > wires
Child wire lists for each gate.
Definition Circuit.h:216
Circuit(Circuit &&)=default
std::pair< gate_t, bool > findOrAddGate(const gate_uuid &u)
Return (or create) the gate associated with UUID u, and whether it was created.
Definition Circuit.hpp:39
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
Definition Circuit.hpp:50
bool getUUID(gate_t g, gate_uuid &u) const
Read the UUID of gate g into u.
Definition Circuit.h:289
bool hasGate(const uuid &u) const
Test whether a gate with UUID u exists.
Definition Circuit.hpp:30
void bindName(gate_t g, const gate_uuid &u)
Name gate g by the UUID u.
Definition Circuit.hpp:78
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
Definition Circuit.h:252
std::unordered_map< std::string, gate_t > name2id
Other name → gate index.
Definition Circuit.h:191
void moveName(gate_t from, gate_t to)
Give the name of gate from, if any, to gate to.
Definition Circuit.hpp:145
virtual gate_t addGate()
Allocate a new gate with a default-initialised type.
Definition Circuit.hpp:168
Hash of a gate_uuid: its bytes are already uniformly spread.
Definition Circuit.h:154
std::size_t operator()(const gate_uuid &u) const
The hash of u.
Definition Circuit.h:156
A UUID as its 16 bytes, read as two big-endian words.
Definition Circuit.h:62
void toBytes(unsigned char *p) const
Write the 16 bytes of the UUID to p.
Definition Circuit.h:77
static gate_uuid fromBytes(const unsigned char *p)
The UUID whose 16 bytes start at p.
Definition Circuit.h:67
bool operator<(const gate_uuid &o) const
The order of the bytes.
Definition Circuit.h:143
std::string str() const
The text form of the UUID, as PostgreSQL prints it.
Definition Circuit.h:121
void serialize(Archive &ar, const unsigned int)
Boost serialisation.
Definition Circuit.h:148
bool operator==(const gate_uuid &o) const
Equality of the 16 bytes.
Definition Circuit.h:135
static bool parse(const std::string &s, gate_uuid &u)
Read s as a UUID in the text form PostgreSQL prints (lowercase, xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx)...
Definition Circuit.h:93
std::uint64_t lo
The last eight bytes, big-endian.
Definition Circuit.h:64
bool operator!=(const gate_uuid &o) const
Inequality of the 16 bytes.
Definition Circuit.h:139
std::uint64_t hi
The first eight bytes, big-endian.
Definition Circuit.h:63