ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
gate_builders.c
Go to the documentation of this file.
1/**
2 * @file gate_builders.c
3 * @brief The gate-building SQL functions the query rewriter calls once per
4 * row or per group, in C.
5 *
6 * These functions used to be PL/pgSQL. Each inner statement of a PL/pgSQL
7 * function runs through SPI, an executor start-up and shutdown of about 2 µs,
8 * and their keys went through the text form of @c uuid[] and back; at one
9 * call per output row this was most of the cost of provenance tracking. The
10 * C versions build the same gates at the same addresses: a gate is addressed
11 * by the version-5 UUID, in the ProvSQL namespace, of a text name
12 * (@c "times{u1,u2}", ...), and the names built here are, byte for byte, the
13 * ones the PL/pgSQL code built. The regression test @c gate_builders keeps
14 * the former bodies as reference functions and compares the two.
15 */
16#include "postgres.h"
17#include "fmgr.h"
18#include "catalog/namespace.h"
19#include "catalog/pg_type.h"
20#include "parser/parse_coerce.h"
21#include "lib/stringinfo.h"
22#include "utils/array.h"
23#include "utils/builtins.h"
24#include "utils/hsearch.h"
25#include "utils/lsyscache.h"
26#include "utils/memutils.h"
27#include "utils/uuid.h"
28
29#include "agg_token.h"
30#include "gate_builders.h"
31#include "provsql_mmap.h"
32#include "provsql_utils.h"
33
34/** @brief @c uuid_ns_provsql(), the namespace of every gate address. */
35static const unsigned char provsql_ns[UUID_LEN] = {
36 0x92, 0x0d, 0x4f, 0x02, 0x87, 0x18, 0x53, 0x19,
37 0x95, 0x32, 0xd4, 0xab, 0x83, 0xa6, 0x44, 0x89
38};
39
40/**
41 * @brief The hash of the name being built, which takes the buffer's content
42 * whenever it grows past @c NAME_FLUSH bytes: the name of a gate with
43 * millions of children (the @c agg of a @c SUM over millions of rows)
44 * is then never held whole. Names are built one at a time, from
45 * @c name_begin to @c name_end.
46 */
48#define NAME_FLUSH 8192
49
50/** @brief Hash what @p buf holds, and empty it. */
51static void name_flush(StringInfo buf) {
52 provsql_sha1_update(&name_hash, (const unsigned char *)buf->data, buf->len);
53 resetStringInfo(buf);
54}
55
56/**
57 * @brief Start the name of a gate address.
58 *
59 * The buffer opens with the namespace, which the version-5 UUID hashes in
60 * front of the name.
61 */
62static void name_begin(StringInfo buf, const char *prefix) {
64 initStringInfo(buf);
65 appendBinaryStringInfo(buf, (const char *)provsql_ns, UUID_LEN);
66 appendStringInfoString(buf, prefix);
67}
68
69/** @brief Append a UUID in the text form of @c uuid_out. */
70static void name_add_uuid(StringInfo buf, const pg_uuid_t *u) {
71 static const char hex[] = "0123456789abcdef";
72 char out[36];
73 int i, p = 0;
74
75 for (i = 0; i < UUID_LEN; ++i) {
76 if (i == 4 || i == 6 || i == 8 || i == 10)
77 out[p++] = '-';
78 out[p++] = hex[u->data[i] >> 4];
79 out[p++] = hex[u->data[i] & 0xF];
80 }
81 appendBinaryStringInfo(buf, out, 36);
82}
83
84/** @brief Append the text form of a @c uuid[], @c "{u1,u2,...}". */
85static void name_add_uuid_array(StringInfo buf, const pg_uuid_t *u, int n) {
86 int i;
87
88 appendStringInfoChar(buf, '{');
89 for (i = 0; i < n; ++i) {
90 if (i > 0)
91 appendStringInfoChar(buf, ',');
92 name_add_uuid(buf, &u[i]);
93 if (buf->len >= NAME_FLUSH)
94 name_flush(buf);
95 }
96 appendStringInfoChar(buf, '}');
97}
98
99/** @brief The version-5 UUID of the name accumulated in @p buf. */
100static pg_uuid_t name_end(StringInfo buf) {
101 unsigned char digest[20];
102 pg_uuid_t u;
103
104 name_flush(buf);
106 memcpy(u.data, digest, UUID_LEN);
107 u.data[6] = (unsigned char)((u.data[6] & 0x0F) | 0x50);
108 u.data[8] = (unsigned char)((u.data[8] & 0x3F) | 0x80);
109 pfree(buf->data);
110 return u;
111}
112
113/** @brief The UUID @p text (one of the constants of @c provsql_utils.h). */
114static pg_uuid_t constant_uuid(const char *text) {
115 return *DatumGetUUIDP(DirectFunctionCall1(uuid_in, CStringGetDatum(text)));
116}
117
118static const pg_uuid_t *address_of_zero(void) {
119 static pg_uuid_t u;
120 static bool known = false;
121 if (!known) { u = constant_uuid(PROVSQL_GATE_ZERO_UUID); known = true; }
122 return &u;
123}
124
125static const pg_uuid_t *address_of_one(void) {
126 static pg_uuid_t u;
127 static bool known = false;
128 if (!known) { u = constant_uuid(PROVSQL_GATE_ONE_UUID); known = true; }
129 return &u;
130}
131
132static int token_cmp(const void *a, const void *b) {
133 return memcmp(a, b, UUID_LEN);
134}
135
136static Datum uuid_result(const pg_uuid_t *u) {
137 pg_uuid_t *r = (pg_uuid_t *)palloc(UUID_LEN);
138 memcpy(r, u, UUID_LEN);
139 return UUIDPGetDatum(r);
140}
141
142/**
143 * @brief The elements of a @c uuid[] that are neither NULL nor @p neutral,
144 * in order. @return their number; @p *out is palloc'd.
145 */
146static int filtered_tokens(ArrayType *arr, const pg_uuid_t *neutral,
147 pg_uuid_t **out) {
148 Datum *elems;
149 bool *nulls;
150 int n, i, kept = 0;
151
152 deconstruct_array(arr, UUIDOID, UUID_LEN, false, 'c', &elems, &nulls, &n);
153 *out = (pg_uuid_t *)palloc(sizeof(pg_uuid_t) * (n > 0 ? n : 1));
154 for (i = 0; i < n; ++i) {
155 pg_uuid_t *u;
156 if (nulls[i])
157 continue;
158 u = DatumGetUUIDP(elems[i]);
159 if (memcmp(u->data, neutral->data, UUID_LEN) == 0)
160 continue;
161 (*out)[kept++] = *u;
162 }
163 return kept;
164}
165
166/** @brief The canonical address, @c "<prefix>{sorted children}".
167 *
168 * Sorting identifies a product with every reordering of its factors, which
169 * requires a commutative @f$\otimes@f$, as in every semiring ProvSQL
170 * evaluates. */
171static pg_uuid_t canonical_address(const char *canonical_prefix,
172 const pg_uuid_t *children, int n) {
173 StringInfoData buf;
174 pg_uuid_t *sorted;
175
176 sorted = (pg_uuid_t *)palloc(sizeof(pg_uuid_t) * (n > 0 ? n : 1));
177 memcpy(sorted, children, sizeof(pg_uuid_t) * n);
178 qsort(sorted, n, sizeof(pg_uuid_t), token_cmp);
179 name_begin(&buf, canonical_prefix);
180 if (n > 0)
181 name_add_uuid_array(&buf, sorted, n);
182 pfree(sorted);
183 return name_end(&buf);
184}
185
186/* -------------------------------------------------------------------------
187 * Planted gates
188 *
189 * The reachability route compiles, at plan time, a certified circuit
190 * equivalent to a sum or product of correlated tokens of the working table it
191 * has just filled, and wants the query to use that circuit where the generic
192 * rewriting builds the sum or the product. It pre-creates ("plants") a gate
193 * at the canonical address of the multiset of tokens, and provenance_plus /
194 * provenance_times return that gate when they are given that very multiset.
195 *
196 * Which addresses are planted is known to the backend that planted them, and
197 * to no one else: the functions below look them up in a table local to the
198 * backend, never in the store. This is enough, because the sum or product
199 * in question is computed above a scan of the working table, a temporary
200 * table: PostgreSQL runs it in the backend that owns the table, not in a
201 * parallel worker, and that backend is the one which lowered the CTE. When
202 * nothing is planted, which is the case of every session that ran no
203 * reachability query, the canonical address is not even computed.
204 *
205 * A planted gate is needed for as long as its working table exists: a cached
206 * plan keeps reading the table, and is invalidated when the table is dropped,
207 * so that the next execution lowers the CTE and plants again. The entries
208 * are therefore grouped by working table, and discarded with it. Gates of
209 * the store outlive an aborted transaction, so an entry never names a gate
210 * that does not exist.
211 * ------------------------------------------------------------------------- */
212
213/** @brief A working table with planted gates. */
214typedef struct PlantedScope {
215 int id;
216 Oid relid; /**< The table, as created by the lowering */
217 char name[NAMEDATALEN];
220
221typedef struct PlantedEntry {
222 pg_uuid_t address; /**< Hash key */
223 int scope;
225
226static HTAB *planted = NULL;
229static int planted_next_id = 0;
230
231/** @brief OID of the temporary table @p name of this backend, if any. */
232static Oid temp_table_oid(const char *name) {
233 Oid nsp = LookupExplicitNamespace("pg_temp", true);
234 return OidIsValid(nsp) ? get_relname_relid(name, nsp) : InvalidOid;
235}
236
237static void planted_forget(PlantedScope *scope) {
238 HASH_SEQ_STATUS seq;
239 PlantedEntry *e;
240 PlantedScope **link;
241
242 if (planted != NULL) {
243 hash_seq_init(&seq, planted);
244 while ((e = (PlantedEntry *)hash_seq_search(&seq)) != NULL)
245 if (e->scope == scope->id)
246 hash_search(planted, &e->address, HASH_REMOVE, NULL);
247 }
248 for (link = &planted_scopes; *link != NULL; link = &(*link)->next)
249 if (*link == scope) {
250 *link = scope->next;
251 break;
252 }
253 if (planted_current == scope)
254 planted_current = NULL;
255 pfree(scope);
256}
257
258/**
259 * @brief Open the scope of the working table @p name, just (re)created:
260 * forget what was planted for the table it replaces, and for every
261 * working table that no longer exists.
262 */
263static PlantedScope *planted_open_scope(const char *name, bool reset) {
264 PlantedScope *s, *next, *found = NULL;
265
266 for (s = planted_scopes; s != NULL; s = next) {
267 next = s->next;
268 if (strcmp(s->name, name) == 0) {
269 if (reset)
271 else
272 found = s;
273 } else if (temp_table_oid(s->name) != s->relid)
275 }
276 if (found == NULL) {
277 found = (PlantedScope *)MemoryContextAllocZero(TopMemoryContext,
278 sizeof(PlantedScope));
279 found->id = planted_next_id++;
280 strlcpy(found->name, name, NAMEDATALEN);
281 found->next = planted_scopes;
282 planted_scopes = found;
283 }
284 found->relid = temp_table_oid(name);
285 return found;
286}
287
288static bool is_planted(const pg_uuid_t *address) {
289 return hash_search(planted, address, HASH_FIND, NULL) != NULL;
290}
291
292pg_uuid_t provsql_plant_canonical(const char *work_name, gate_type type,
293 const pg_uuid_t *children, int n,
294 const pg_uuid_t *target,
295 unsigned info1, unsigned info2) {
296 PlantedScope *scope;
297 PlantedEntry *e;
298 pg_uuid_t address;
299 bool found;
300
301 if (type != gate_plus && type != gate_times)
302 provsql_error("only plus and times gates can be planted");
303 scope = work_name != NULL ? planted_open_scope(work_name, false)
305 if (scope == NULL)
306 provsql_error("planting a gate outside the lowering of a recursive CTE");
307
308 address = canonical_address(type == gate_plus ? "plus-canonical"
309 : "times-canonical",
310 children, n);
311 provsql_internal_create_gate_with(&address, type, 1, target,
312 true, info1, info2, NULL);
313
314 if (planted == NULL) {
315 HASHCTL ctl;
316 memset(&ctl, 0, sizeof(ctl));
317 ctl.keysize = sizeof(pg_uuid_t);
318 ctl.entrysize = sizeof(PlantedEntry);
319 ctl.hcxt = TopMemoryContext;
320 planted = hash_create("ProvSQL planted gates", 256, &ctl,
321 HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
322 }
323 e = (PlantedEntry *)hash_search(planted, &address, HASH_ENTER, &found);
324 e->scope = scope->id;
325 return address;
326}
327
328PG_FUNCTION_INFO_V1(planted_scope);
329/** @brief SQL entry point of @c planted_open_scope(), called by the drivers
330 * of recursive CTEs right after they (re)create the working table. */
331Datum planted_scope(PG_FUNCTION_ARGS) {
332 char *name = text_to_cstring(PG_GETARG_TEXT_PP(0));
334 PG_RETURN_VOID();
335}
336
337PG_FUNCTION_INFO_V1(plant_canonical);
338/** @brief SQL entry point of @c provsql_plant_canonical(). */
339Datum plant_canonical(PG_FUNCTION_ARGS) {
340 char *name = text_to_cstring(PG_GETARG_TEXT_PP(0));
341 char *type_name = text_to_cstring(PG_GETARG_TEXT_PP(1));
342 pg_uuid_t *children, address;
343 pg_uuid_t nothing;
344 int n;
345
346 memset(&nothing, 0xFF, sizeof(nothing));
347 n = filtered_tokens(PG_GETARG_ARRAYTYPE_P(2), &nothing, &children);
348 address = provsql_plant_canonical(
349 name, strcmp(type_name, "plus") == 0 ? gate_plus :
350 strcmp(type_name, "times") == 0 ? gate_times : gate_invalid,
351 children, n, PG_GETARG_UUID_P(3),
352 (unsigned)PG_GETARG_INT32(4), (unsigned)PG_GETARG_INT32(5));
353 return uuid_result(&address);
354}
355
356/**
357 * @brief A gate of type @p type over @p children, unless this backend planted
358 * one at the canonical address of their multiset.
359 */
360static pg_uuid_t nary_gate(gate_type type, const char *plain_prefix,
361 const char *canonical_prefix,
362 const pg_uuid_t *children, int n) {
363 StringInfoData buf;
364 pg_uuid_t token;
365
366 if (planted != NULL && hash_get_num_entries(planted) > 0) {
367 pg_uuid_t canonical = canonical_address(canonical_prefix, children, n);
368 if (is_planted(&canonical))
369 return canonical;
370 }
371
372 name_begin(&buf, plain_prefix);
373 if (n > 0)
374 name_add_uuid_array(&buf, children, n);
375 token = name_end(&buf);
376 provsql_internal_create_gate(&token, type, (unsigned)n, n > 0 ? children : NULL);
377 return token;
378}
379
380PG_FUNCTION_INFO_V1(provenance_times);
381/**
382 * @brief ⊗ of a list of tokens.
383 *
384 * A NULL token is the token slot of an untracked source, which is certain: it
385 * reads as the ⊗-neutral 𝟙 and is dropped, like @c gate_one itself. No
386 * survivor gives 𝟙, a single one is returned as it is.
387 */
388Datum provenance_times(PG_FUNCTION_ARGS) {
389 pg_uuid_t *tokens, result;
390 int n;
391
392 if (PG_ARGISNULL(0))
393 return uuid_result(address_of_one());
394 n = filtered_tokens(PG_GETARG_ARRAYTYPE_P(0), address_of_one(), &tokens);
395 result = provsql_build_times(tokens, n);
396 return uuid_result(&result);
397}
398
399/* The nonnull tokens, @p neutral dropped, in order, into @p out (room for
400 * @p n). */
401static int drop_neutral(const pg_uuid_t *tokens, int n,
402 const pg_uuid_t *neutral, pg_uuid_t *out) {
403 int i, kept = 0;
404 for (i = 0; i < n; ++i)
405 if (memcmp(tokens[i].data, neutral->data, UUID_LEN) != 0)
406 out[kept++] = tokens[i];
407 return kept;
408}
409
411 pg_uuid_t *kept = (pg_uuid_t *)palloc(sizeof(pg_uuid_t) * (n > 0 ? n : 1));
412 pg_uuid_t result;
413 n = drop_neutral(tokens, n, address_of_one(), kept);
414 if (n == 0)
415 result = *address_of_one();
416 else if (n == 1)
417 result = kept[0];
418 else
419 result = nary_gate(gate_times, "times", "times-canonical", kept, n);
420 pfree(kept);
421 return result;
422}
423
424PG_FUNCTION_INFO_V1(provenance_plus);
425/**
426 * @brief ⊕ of an array of tokens. Strict.
427 *
428 * A NULL token stands for a row absent from the disjunction: it reads as the
429 * ⊕-neutral 𝟘 and is dropped, like @c gate_zero itself. No survivor gives 𝟘,
430 * a single one is returned as it is. (The PL/pgSQL version returned, for no
431 * survivor, a @c plus gate without children: @c array_length of the empty
432 * selection is NULL, which sent that case to the general branch. Evaluators
433 * read such a gate as 𝟘, and stored circuits may contain it.)
434 */
435Datum provenance_plus(PG_FUNCTION_ARGS) {
436 pg_uuid_t *tokens, result;
437 int n;
438
439 n = filtered_tokens(PG_GETARG_ARRAYTYPE_P(0), address_of_zero(), &tokens);
440 result = provsql_build_plus(tokens, n);
441 return uuid_result(&result);
442}
443
445 pg_uuid_t *kept = (pg_uuid_t *)palloc(sizeof(pg_uuid_t) * (n > 0 ? n : 1));
446 pg_uuid_t result;
447 n = drop_neutral(tokens, n, address_of_zero(), kept);
448 if (n == 0)
449 result = *address_of_zero();
450 else if (n == 1)
451 result = kept[0];
452 else
453 result = nary_gate(gate_plus, "plus", "plus-canonical", kept, n);
454 pfree(kept);
455 return result;
456}
457
458/* -------------------------------------------------------------------------
459 * Values
460 *
461 * A value gate is addressed by "value" followed by CAST(val AS varchar), and
462 * carries that text as its extra. The cast is resolved as the parser resolves
463 * it (a cast function, the output function, or nothing for a text-like type),
464 * once per call site: true::varchar is 'true' where the output function of
465 * boolean writes 't'.
466 * ------------------------------------------------------------------------- */
467
468typedef struct VarcharCast {
469 Oid type;
470 CoercionPathType path;
471 FmgrInfo fn;
472 int nargs;
474
475/** @brief @c CAST(val AS varchar) of argument @p argno, as a C string. */
476static char *varchar_of_argument(FunctionCallInfo fcinfo, int argno) {
477 VarcharCast *cast = (VarcharCast *)fcinfo->flinfo->fn_extra;
478 Oid type = get_fn_expr_argtype(fcinfo->flinfo, argno);
479 Datum val = PG_GETARG_DATUM(argno);
480
481 if (!OidIsValid(type))
482 provsql_error("cannot determine the type of the value");
483 if (cast == NULL || cast->type != type) {
484 Oid funcid = InvalidOid;
485
486 if (cast == NULL)
487 cast = (VarcharCast *)MemoryContextAllocZero(fcinfo->flinfo->fn_mcxt,
488 sizeof(VarcharCast));
489 cast->path = find_coercion_pathway(VARCHAROID, type, COERCION_EXPLICIT,
490 &funcid);
491 if (cast->path == COERCION_PATH_FUNC) {
492 fmgr_info_cxt(funcid, &cast->fn, fcinfo->flinfo->fn_mcxt);
493 cast->nargs = get_func_nargs(funcid);
494 } else if (cast->path != COERCION_PATH_RELABELTYPE) {
495 bool is_varlena;
496 cast->path = COERCION_PATH_COERCEVIAIO;
497 getTypeOutputInfo(type, &funcid, &is_varlena);
498 fmgr_info_cxt(funcid, &cast->fn, fcinfo->flinfo->fn_mcxt);
499 }
500 cast->type = type;
501 fcinfo->flinfo->fn_extra = cast;
502 }
503
504 switch (cast->path) {
505 case COERCION_PATH_FUNC: {
506 Datum r;
507 if (cast->nargs == 1)
508 r = FunctionCall1(&cast->fn, val);
509 else if (cast->nargs == 2)
510 r = FunctionCall2(&cast->fn, val, Int32GetDatum(-1));
511 else
512 r = FunctionCall3(&cast->fn, val, Int32GetDatum(-1), BoolGetDatum(true));
513 return text_to_cstring(DatumGetTextPP(r));
514 }
515 case COERCION_PATH_RELABELTYPE:
516 return text_to_cstring(DatumGetTextPP(val));
517 default:
518 return OutputFunctionCall(&cast->fn, val);
519 }
520}
521
522/* The value gates this backend has written. The same few values come back
523 * row after row (the 1 of every count), and a gate of the store stays as it
524 * is once written, so there is nothing to repeat. Emptied when it grows
525 * large, and by circuit_cleanup, which may remove gates. */
526static HTAB *written_values = NULL;
527#define WRITTEN_VALUES_MAX 65536
528
530 if (written_values != NULL) {
531 hash_destroy(written_values);
532 written_values = NULL;
533 }
534 while (planted_scopes != NULL)
536}
537
538/** @brief The value gate of the text @p str, at the address named @p name
539 * (@c "value" followed by @p str, or @c "null"). */
540static pg_uuid_t value_gate(const char *prefix, const char *suffix,
541 const char *extra) {
542 StringInfoData buf;
543 pg_uuid_t token;
544 bool found;
545
546 name_begin(&buf, prefix);
547 appendStringInfoString(&buf, suffix);
548 token = name_end(&buf);
549
550 if (written_values != NULL
551 && hash_get_num_entries(written_values) >= WRITTEN_VALUES_MAX) {
552 hash_destroy(written_values);
553 written_values = NULL;
554 }
555 if (written_values == NULL) {
556 HASHCTL ctl;
557 memset(&ctl, 0, sizeof(ctl));
558 ctl.keysize = sizeof(pg_uuid_t);
559 ctl.entrysize = sizeof(pg_uuid_t);
560 ctl.hcxt = TopMemoryContext;
561 written_values = hash_create("ProvSQL value gates written", 256, &ctl,
562 HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
563 }
564 if (hash_search(written_values, &token, HASH_FIND, NULL) == NULL) {
566 false, 0, 0, extra);
567 hash_search(written_values, &token, HASH_ENTER, &found);
568 }
569 return token;
570}
571
572/** @brief The semimod gate @p value_token ⊗ @p token. */
573static Datum semimod_gate(const pg_uuid_t *value_token, const pg_uuid_t *token) {
574 StringInfoData buf;
575 pg_uuid_t semimod, children[2];
576
577 name_begin(&buf, "semimod");
578 name_add_uuid(&buf, value_token);
579 name_add_uuid(&buf, token);
580 semimod = name_end(&buf);
581 children[0] = *token;
582 children[1] = *value_token;
583 provsql_internal_create_gate(&semimod, gate_semimod, 2, children);
584 return uuid_result(&semimod);
585}
586
587static const pg_uuid_t *semimod_token_argument(FunctionCallInfo fcinfo) {
588 if (PG_ARGISNULL(1))
589 provsql_error("provenance_semimod: the provenance token must not be NULL");
590 return PG_GETARG_UUID_P(1);
591}
592
593PG_FUNCTION_INFO_V1(provenance_semimod);
594/**
595 * @brief The semimodule gate @c val ⊗ @c token of an aggregated row.
596 *
597 * A NULL value does not take part in the aggregate (SQL aggregates skip NULL
598 * inputs; @c count(*) passes a constant 1): no gate, NULL is returned and
599 * @c provenance_aggregate drops it.
600 */
601Datum provenance_semimod(PG_FUNCTION_ARGS) {
602 const pg_uuid_t *token;
603 pg_uuid_t value_token;
604 char *str;
605
606 if (PG_ARGISNULL(0))
607 PG_RETURN_NULL();
608 token = semimod_token_argument(fcinfo);
609 str = varchar_of_argument(fcinfo, 0);
610 value_token = value_gate("value", str, str);
611 return semimod_gate(&value_token, token);
612}
613
614PG_FUNCTION_INFO_V1(provenance_semimod_nullable);
615/**
616 * @brief @c provenance_semimod for the aggregates that see their NULL inputs
617 * (@c array_agg, @c json_agg, ...): a NULL value gives a gate over the
618 * constant value gate @c gate_null().
619 */
620Datum provenance_semimod_nullable(PG_FUNCTION_ARGS) {
621 const pg_uuid_t *token = semimod_token_argument(fcinfo);
622 pg_uuid_t value_token;
623
624 if (PG_ARGISNULL(0))
625 value_token = value_gate("null", "", "NULL");
626 else {
627 char *str = varchar_of_argument(fcinfo, 0);
628 value_token = value_gate("value", str, str);
629 }
630 return semimod_gate(&value_token, token);
631}
632
633static bool same_token(const pg_uuid_t *a, const pg_uuid_t *b);
634
635PG_FUNCTION_INFO_V1(provenance_semimod_nested);
636/**
637 * @brief The semimodule gate of a row whose value is itself an aggregate
638 * result: @c semimod(the inner aggregate's gate, @p token).
639 *
640 * The contribution of an outer aggregate that reads an aggregate result of
641 * another kind (an avg of a count, a max of a sum, an aggregate of an
642 * arithmetic expression over aggregates). Such a value is not one value of
643 * the database but one per possible world, so the M side of the semimod is
644 * the inner aggregate's own gate rather than a @c gate_value: an evaluator
645 * that reads a value per world (the sampler) resolves it, and the closed
646 * forms, which read the M side as a constant, decline it.
647 */
648Datum provenance_semimod_nested(PG_FUNCTION_ARGS) {
649 const pg_uuid_t *token;
650 agg_token *aggtok;
651 pg_uuid_t inner;
652
653 if (PG_ARGISNULL(0))
654 PG_RETURN_NULL();
655 token = semimod_token_argument(fcinfo);
656 aggtok = (agg_token *)PG_GETARG_POINTER(0);
657 inner = *DatumGetUUIDP(DirectFunctionCall1(uuid_in,
658 CStringGetDatum(aggtok->tok)));
659 return semimod_gate(&inner, token);
660}
661
662PG_FUNCTION_INFO_V1(provenance_semimod_flat);
663/**
664 * @brief The contributions @c semimod(v_i, token ⊗ k_i) of the aggregate
665 * result @c val, whose gate aggregates the contributions
666 * @c semimod(v_i, k_i), for an aggregate of the same kind over it.
667 *
668 * @c token ⊗ (⊕ k_i ⊗ v_i) = ⊕ (token ⊗ k_i) ⊗ v_i: the outer aggregate of
669 * the rows of the groups, in every semiring. An empty array for a NULL
670 * value, which the outer aggregate skips.
671 */
672Datum provenance_semimod_flat(PG_FUNCTION_ARGS) {
673 const pg_uuid_t *token = semimod_token_argument(fcinfo);
674 agg_token *aggtok;
675 pg_uuid_t agg, *children = NULL, *out;
676 unsigned n = 0, i;
677 gate_type type;
678
679 if (PG_ARGISNULL(0))
680 PG_RETURN_ARRAYTYPE_P(construct_empty_array(UUIDOID));
681 aggtok = (agg_token *)PG_GETARG_POINTER(0);
682 agg = *DatumGetUUIDP(DirectFunctionCall1(uuid_in,
683 CStringGetDatum(aggtok->tok)));
684 type = provsql_fetch_gate(&agg, &n, &children);
685 if (type != gate_agg)
686 provsql_error("provenance_semimod_flat: not the result of an aggregate");
687
688 out = (pg_uuid_t *)palloc(sizeof(pg_uuid_t) * (n > 0 ? n : 1));
689 for (i = 0; i < n; ++i) {
690 unsigned m = 0;
691 pg_uuid_t *wires = NULL, scaled, pair[2];
692
693 if (provsql_fetch_gate(&children[i], &m, &wires) != gate_semimod || m != 2)
694 provsql_error("provenance_semimod_flat: unexpected contribution");
695 pair[0] = *token;
696 pair[1] = wires[0];
697 if (same_token(token, address_of_one()))
698 scaled = wires[0];
699 else if (same_token(&wires[0], address_of_one()))
700 scaled = *token;
701 else
702 scaled = nary_gate(gate_times, "times", "times-canonical", pair, 2);
703 out[i] = *DatumGetUUIDP(semimod_gate(&wires[1], &scaled));
704 free(wires);
705 }
706 free(children);
707 {
708 Datum *elems = (Datum *)palloc(sizeof(Datum) * (n > 0 ? n : 1));
709 for (i = 0; i < n; ++i)
710 elems[i] = UUIDPGetDatum(&out[i]);
711 PG_RETURN_ARRAYTYPE_P(construct_array(elems, (int)n, UUIDOID, UUID_LEN,
712 false, 'c'));
713 }
714}
715
716PG_FUNCTION_INFO_V1(provenance_aggregate);
717/**
718 * @brief The @c agg gate of a group, paired with the aggregate's value.
719 *
720 * The address hashes everything the gate records: the aggregate function
721 * and the scalar flag (info1 and the high bit of info2), the children, then
722 * the result type (the low bits of info2) and the value text (the extra),
723 * after a colon each. A gate's infos and text are written once, so what is
724 * written has to follow from the address: @c SUM(x) and @c AVG(x) over the
725 * same children, a scalar and a grouped aggregate, @c array_agg over
726 * integers and over their texts (same children, another result type), or a
727 * floating-point sum whose rounding depends on the plan, are all different
728 * gates. NULL children are rows whose value was NULL; they are dropped.
729 * No child gives 𝟘 for a group, and an agg gate without children for a
730 * scalar aggregation, whose value over no row is still defined.
731 */
732Datum provenance_aggregate(PG_FUNCTION_ARGS) {
733 int32 aggfnoid, aggtype;
734 bool is_scalar = !PG_ARGISNULL(4) && PG_GETARG_BOOL(4);
735 pg_uuid_t *tokens = NULL, agg, nothing;
736 char *val = NULL;
737 int n = 0;
738 agg_token *result;
739
740 if (PG_ARGISNULL(0) || PG_ARGISNULL(1))
741 provsql_error("provenance_aggregate: the aggregate function and its "
742 "result type must not be NULL");
743 aggfnoid = PG_GETARG_INT32(0);
744 aggtype = PG_GETARG_INT32(1);
745 if (!PG_ARGISNULL(2))
746 val = varchar_of_argument(fcinfo, 2);
747 if (!PG_ARGISNULL(3)) {
748 memset(&nothing, 0xFF, sizeof(nothing));
749 n = filtered_tokens(PG_GETARG_ARRAYTYPE_P(3), &nothing, &tokens);
750 }
751
752 /* A group without rows is no group; a scalar aggregation over no row has a
753 * value (0 for a count), that of an agg gate without children. */
754 if (n == 0 && !is_scalar)
755 agg = *address_of_zero();
756 else {
757 StringInfoData buf;
758
759 name_begin(&buf, "agg");
760 appendStringInfo(&buf, "%d", aggfnoid);
761 name_add_uuid_array(&buf, tokens, n);
762 if (is_scalar)
763 appendStringInfoChar(&buf, 'S');
764 appendStringInfo(&buf, ":%d", aggtype);
765 if (val != NULL)
766 appendStringInfo(&buf, ":%s", val);
767 agg = name_end(&buf);
768 provsql_internal_create_gate_with(&agg, gate_agg, (unsigned)n, tokens,
769 true, (unsigned)aggfnoid,
770 is_scalar ? ((unsigned)aggtype | 0x80000000u)
771 : (unsigned)aggtype,
772 val);
773 }
774
775 /* A NULL value over no row at all is SQL's NULL: there is nothing to
776 * keep. Over rows absent from the database as it is (the displayed value
777 * reads only the present ones), the group exists in other worlds: the
778 * token keeps its circuit, with a NULL value (an empty val). */
779 if (val == NULL && n == 0)
780 PG_RETURN_NULL();
781 result = (agg_token *)palloc0(sizeof(agg_token));
782 {
783 StringInfoData t;
784 initStringInfo(&t);
785 name_add_uuid(&t, &agg);
786 memcpy(result->tok, t.data, 36);
787 pfree(t.data);
788 }
789 if (val != NULL)
790 agg_token_set_value(result, val, strlen(val));
791 PG_RETURN_POINTER(result);
792}
793
794static bool same_token(const pg_uuid_t *a, const pg_uuid_t *b) {
795 return memcmp(a->data, b->data, UUID_LEN) == 0;
796}
797
798PG_FUNCTION_INFO_V1(provenance_monus);
799/**
800 * @brief @c token1 ⊖ @c token2.
801 *
802 * A NULL second argument is the row without a match in the outer join of the
803 * difference: nothing to subtract, and X ⊖ 𝟘 = X. (Not the NULL ≡ 𝟙 of
804 * @c provenance_times: each combinator reads NULL as its own neutral.)
805 * X ⊖ X = 𝟘 and 𝟘 ⊖ X = 𝟘 are applied as well.
806 */
807Datum provenance_monus(PG_FUNCTION_ARGS) {
808 const pg_uuid_t *token1, *token2;
809 pg_uuid_t monus;
810
811 if (PG_ARGISNULL(0))
812 ereport(ERROR,
813 (errmsg("provenance_monus is called with first argument NULL")));
814 token1 = PG_GETARG_UUID_P(0);
815 if (PG_ARGISNULL(1))
816 return uuid_result(token1);
817 token2 = PG_GETARG_UUID_P(1);
818 monus = provsql_build_monus(token1, token2);
819 return uuid_result(&monus);
820}
821
822pg_uuid_t provsql_build_monus(const pg_uuid_t *token1, const pg_uuid_t *token2) {
823 StringInfoData buf;
824 pg_uuid_t monus, children[2];
825
826 if (same_token(token1, token2) || same_token(token1, address_of_zero()))
827 return *address_of_zero();
828 if (same_token(token2, address_of_zero()))
829 return *token1;
830
831 name_begin(&buf, "monus");
832 name_add_uuid(&buf, token1);
833 name_add_uuid(&buf, token2);
834 monus = name_end(&buf);
835 children[0] = *token1;
836 children[1] = *token2;
837 provsql_internal_create_gate(&monus, gate_monus, 2, children);
838 return monus;
839}
840
841PG_FUNCTION_INFO_V1(provenance_delta);
842/**
843 * @brief δ(@c token). A NULL token is an untracked source, 𝟙, and δ(𝟙) = 𝟙;
844 * δ(𝟘) = 𝟘.
845 */
846Datum provenance_delta(PG_FUNCTION_ARGS) {
847 const pg_uuid_t *token;
848 pg_uuid_t delta;
849
850 if (PG_ARGISNULL(0))
851 return uuid_result(address_of_one());
852 token = PG_GETARG_UUID_P(0);
853 delta = provsql_build_delta(token);
854 return uuid_result(&delta);
855}
856
858 StringInfoData buf;
859 pg_uuid_t delta;
860
861 if (same_token(token, address_of_zero()) || same_token(token, address_of_one()))
862 return *token;
863
864 name_begin(&buf, "delta");
865 name_add_uuid(&buf, token);
866 delta = name_end(&buf);
867 provsql_internal_create_gate(&delta, gate_delta, 1, token);
868 return delta;
869}
870
871/**
872 * @brief Is @p sum the gate of @p base plus a nonzero constant?
873 *
874 * The aggregate-value arithmetic builds @c x+c as a @c gate_arith PLUS over
875 * the token of @c x and a @c gate_value; tokens being content-addressed, the
876 * same @c x is the same token.
877 */
878static bool is_shift_of(const pg_uuid_t *sum, const pg_uuid_t *base) {
879 unsigned n = 0, m = 0, info1 = 0, info2 = 0;
880 pg_uuid_t *ch = NULL, *vch = NULL;
881 gate_type t = provsql_fetch_gate(sum, &n, &ch);
882 bool result = false;
883
884 if (t == gate_arith && n == 2) {
885 int k = same_token(&ch[0], base) ? 1 : same_token(&ch[1], base) ? 0 : -1;
886 if (k >= 0) {
887 provsql_internal_get_infos(sum, &info1, &info2);
888 if (info1 == PROVSQL_ARITH_PLUS &&
889 provsql_fetch_gate(&ch[k], &m, &vch) == gate_value) {
890 char *v = provsql_internal_get_extra(&ch[k]);
891 char *end;
892 double c = strtod(v, &end);
893 result = end != v && *end == '\0' && c != 0 && c == c;
894 }
895 }
896 }
897 free(ch);
898 free(vch);
899 return result;
900}
901
902/**
903 * @brief Does @c left @c op @c right hold in no world, by its shape alone?
904 *
905 * Recognised: @c x+c @c = @c x with @c c a nonzero constant, in either order,
906 * the comparison of a row's rank with itself shifted that a self-join on
907 * consecutive ranks builds for each row paired with itself. Cheap, and
908 * deliberately narrow: a row it rules out is one the rewriting may drop.
909 */
910static bool cmp_impossible(const pg_uuid_t *left, Oid op,
911 const pg_uuid_t *right) {
912 char *name = get_opname(op);
913
914 if (name == NULL || strcmp(name, "=") != 0)
915 return false;
916 return is_shift_of(left, right) || is_shift_of(right, left);
917}
918
919PG_FUNCTION_INFO_V1(provenance_cmp);
920/**
921 * @brief The comparison gate @c left @c op @c right of a HAVING condition.
922 *
923 * A comparison with a NULL operand is unknown in every possible world: the
924 * row is annotated 𝟘. Hence not strict: a NULL result would read as the
925 * neutral of ⊗ and turn "unknown" into "certainly true".
926 */
927Datum provenance_cmp(PG_FUNCTION_ARGS) {
928 const pg_uuid_t *left, *right;
929 Oid op;
930 StringInfoData buf;
931 pg_uuid_t cmp, children[2];
932
933 if (PG_ARGISNULL(0) || PG_ARGISNULL(1) || PG_ARGISNULL(2))
935 left = PG_GETARG_UUID_P(0);
936 op = PG_GETARG_OID(1);
937 right = PG_GETARG_UUID_P(2);
938
939 /* False in every world: 𝟘, which the rewriting's filter on it drops. */
940 if (cmp_impossible(left, op, right))
942
943 name_begin(&buf, "cmp");
944 name_add_uuid(&buf, left);
945 appendStringInfo(&buf, "%u", op);
946 name_add_uuid(&buf, right);
947 cmp = name_end(&buf);
948 children[0] = *left;
949 children[1] = *right;
951 true, (unsigned)op, 0, NULL);
952 return uuid_result(&cmp);
953}
954
955PG_FUNCTION_INFO_V1(annotate);
956/**
957 * @brief A transparent @c annotation gate over @c token, carrying @c extra.
958 *
959 * The address hashes @c extra along with the child: two annotations of one
960 * token with different texts are different gates. NULL on a NULL token.
961 */
962Datum annotate(PG_FUNCTION_ARGS) {
963 const pg_uuid_t *token;
964 char *extra = NULL;
965 StringInfoData buf;
966 pg_uuid_t annotated;
967
968 if (PG_ARGISNULL(0))
969 PG_RETURN_NULL();
970 token = PG_GETARG_UUID_P(0);
971 if (!PG_ARGISNULL(1))
972 extra = text_to_cstring(PG_GETARG_TEXT_PP(1));
973
974 name_begin(&buf, "annotation");
975 name_add_uuid(&buf, token);
976 if (extra != NULL)
977 appendStringInfoString(&buf, extra);
978 annotated = name_end(&buf);
980 false, 0, 0, extra);
981 return uuid_result(&annotated);
982}
983
984PG_FUNCTION_INFO_V1(inversion_free_key);
985/**
986 * @brief The order key of an input on the inversion-free route,
987 * @c "K<factor> <bytes of root>:<root><bytes of sec>:<sec>". Strict.
988 */
989Datum inversion_free_key(PG_FUNCTION_ARGS) {
990 text *root = PG_GETARG_TEXT_PP(0), *sec = PG_GETARG_TEXT_PP(1);
991 StringInfoData buf;
992
993 initStringInfo(&buf);
994 appendStringInfo(&buf, "K%d %d:", PG_GETARG_INT32(2),
995 (int)VARSIZE_ANY_EXHDR(root));
996 appendBinaryStringInfo(&buf, VARDATA_ANY(root), VARSIZE_ANY_EXHDR(root));
997 appendStringInfo(&buf, "%d:", (int)VARSIZE_ANY_EXHDR(sec));
998 appendBinaryStringInfo(&buf, VARDATA_ANY(sec), VARSIZE_ANY_EXHDR(sec));
999 PG_RETURN_TEXT_P(cstring_to_text_with_len(buf.data, buf.len));
1000}
1001
1002/* -------------------------------------------------------------------------
1003 * The other content-addressed builders: assumption wrappers, where-provenance
1004 * gates, arithmetic. Each records what its address hashes, so the gate goes
1005 * with its infos or text in one unanswered message.
1006 * ------------------------------------------------------------------------- */
1007
1008/** @brief The @c assumed wrapper of @p token under @p assumption, with
1009 * @p info1 as the route tag (0 for none). */
1010static pg_uuid_t assumed_gate(const pg_uuid_t *token, const char *assumption,
1011 unsigned info1) {
1012 StringInfoData buf;
1013 pg_uuid_t wrapped;
1014
1015 if (strcmp(assumption, "boolean") != 0 && strcmp(assumption, "absorptive") != 0)
1016 ereport(ERROR, (errmsg("provenance_assume: unknown assumption %s", assumption)));
1017 name_begin(&buf, "assumed");
1018 appendStringInfoString(&buf, assumption);
1019 name_add_uuid(&buf, token);
1020 wrapped = name_end(&buf);
1022 info1 != 0, info1, 0, assumption);
1023 return wrapped;
1024}
1025
1026PG_FUNCTION_INFO_V1(provenance_assume);
1027/** @brief Wrap @c token in the assumption marker @c assumption
1028 * (@c 'boolean' or @c 'absorptive'). NULL on a NULL token. */
1029Datum provenance_assume(PG_FUNCTION_ARGS) {
1030 pg_uuid_t wrapped;
1031
1032 if (PG_ARGISNULL(0))
1033 PG_RETURN_NULL();
1034 if (PG_ARGISNULL(1))
1035 ereport(ERROR, (errmsg("provenance_assume: unknown assumption NULL")));
1036 wrapped = assumed_gate(PG_GETARG_UUID_P(0),
1037 text_to_cstring(PG_GETARG_TEXT_PP(1)), 0);
1038 return uuid_result(&wrapped);
1039}
1040
1041PG_FUNCTION_INFO_V1(assume_boolean);
1042/** @brief The Boolean-assumption wrapper the safe-query rewriter puts on
1043 * every per-row root, tagged @c PROVSQL_ROUTE_SQ_REWRITE. */
1044Datum assume_boolean(PG_FUNCTION_ARGS) {
1045 pg_uuid_t wrapped;
1046
1047 if (PG_ARGISNULL(0))
1048 PG_RETURN_NULL();
1049 wrapped = assumed_gate(PG_GETARG_UUID_P(0), "boolean",
1051 return uuid_result(&wrapped);
1052}
1053
1054PG_FUNCTION_INFO_V1(provenance_project);
1055/**
1056 * @brief The where-provenance @c project gate of @c token: its text lists,
1057 * for each output position, the input position it comes from (NULL
1058 * for a position given as 0), as @c '{{in,out},...}'.
1059 */
1060Datum provenance_project(PG_FUNCTION_ARGS) {
1061 const pg_uuid_t *token;
1062 ArrayType *positions;
1063 Datum *elems;
1064 bool *nulls;
1065 int n, i;
1066 StringInfoData buf, extra;
1067 pg_uuid_t project;
1068
1069 if (PG_ARGISNULL(0) || PG_ARGISNULL(1))
1070 provsql_error("provenance_project: NULL argument");
1071 token = PG_GETARG_UUID_P(0);
1072 positions = PG_GETARG_ARRAYTYPE_P(1);
1073 deconstruct_array(positions, INT4OID, sizeof(int32), true, 'i',
1074 &elems, &nulls, &n);
1075
1076 /* The address hashes the array as its text form, '{p1,p2,...}'. */
1077 name_begin(&buf, "project");
1078 name_add_uuid(&buf, token);
1079 appendStringInfoChar(&buf, '{');
1080 initStringInfo(&extra);
1081 appendStringInfoChar(&extra, '{');
1082 for (i = 0; i < n; ++i) {
1083 if (i > 0) {
1084 appendStringInfoChar(&buf, ',');
1085 appendStringInfoChar(&extra, ',');
1086 }
1087 if (nulls[i]) {
1088 appendStringInfoString(&buf, "NULL");
1089 appendStringInfo(&extra, "{NULL,%d}", i + 1);
1090 } else {
1091 int32 pos = DatumGetInt32(elems[i]);
1092 appendStringInfo(&buf, "%d", pos);
1093 if (pos == 0)
1094 appendStringInfo(&extra, "{NULL,%d}", i + 1);
1095 else
1096 appendStringInfo(&extra, "{%d,%d}", pos, i + 1);
1097 }
1098 }
1099 appendStringInfoChar(&buf, '}');
1100 appendStringInfoChar(&extra, '}');
1101 project = name_end(&buf);
1103 false, 0, 0, n > 0 ? extra.data : NULL);
1104 return uuid_result(&project);
1105}
1106
1107PG_FUNCTION_INFO_V1(provenance_eq);
1108/** @brief The where-provenance @c eq gate of @c token, equating positions
1109 * @c pos1 and @c pos2 (its infos). */
1110Datum provenance_eq(PG_FUNCTION_ARGS) {
1111 const pg_uuid_t *token;
1112 StringInfoData buf;
1113 pg_uuid_t eq;
1114 int32 pos1 = PG_ARGISNULL(1) ? 0 : PG_GETARG_INT32(1);
1115 int32 pos2 = PG_ARGISNULL(2) ? 0 : PG_GETARG_INT32(2);
1116
1117 if (PG_ARGISNULL(0))
1118 provsql_error("provenance_eq: NULL token");
1119 token = PG_GETARG_UUID_P(0);
1120 name_begin(&buf, "eq");
1121 name_add_uuid(&buf, token);
1122 if (!PG_ARGISNULL(1))
1123 appendStringInfo(&buf, "%d", pos1);
1124 appendStringInfoChar(&buf, ',');
1125 if (!PG_ARGISNULL(2))
1126 appendStringInfo(&buf, "%d", pos2);
1127 eq = name_end(&buf);
1129 true, (unsigned)pos1, (unsigned)pos2, NULL);
1130 return uuid_result(&eq);
1131}
1132
1133PG_FUNCTION_INFO_V1(provenance_arith);
1134/** @brief The @c arith gate applying operator @c op (a @c provsql_arith_op,
1135 * its info1) to @c children, in order. */
1136Datum provenance_arith(PG_FUNCTION_ARGS) {
1137 StringInfoData buf;
1138 pg_uuid_t arith, *children = NULL, nothing;
1139 int n = 0;
1140 int32 op = PG_ARGISNULL(0) ? 0 : PG_GETARG_INT32(0);
1141
1142 name_begin(&buf, "arith");
1143 if (!PG_ARGISNULL(0))
1144 appendStringInfo(&buf, "%d", op);
1145 if (!PG_ARGISNULL(1)) {
1146 ArrayType *arr = PG_GETARG_ARRAYTYPE_P(1);
1147 if (array_contains_nulls(arr))
1148 provsql_error("provenance_arith: children array must not contain NULL elements");
1149 memset(&nothing, 0xFF, sizeof(nothing));
1150 n = filtered_tokens(arr, &nothing, &children);
1151 name_add_uuid_array(&buf, children, n);
1152 }
1153 arith = name_end(&buf);
1154 provsql_internal_create_gate_with(&arith, gate_arith, (unsigned)n, children,
1155 true, (unsigned)op, 0, NULL);
1156 return uuid_result(&arith);
1157}
void provsql_sha1_final(provsql_sha1_ctx *ctx, unsigned char out[20])
The SHA-1 of all the bytes given to ctx.
void provsql_sha1_init(provsql_sha1_ctx *ctx)
Start an incremental SHA-1.
void provsql_sha1_update(provsql_sha1_ctx *ctx, const unsigned char *data, size_t len)
Hash len more bytes of data.
void agg_token_set_value(agg_token *aggtok, const char *val, size_t len)
Set the value of aggtok to the len first bytes of val.
Definition agg_token.c:40
Aggregate-provenance token type used in SQL aggregate functions.
Datum provenance_monus(PG_FUNCTION_ARGS)
token1 ⊖ token2.
Datum provenance_semimod_flat(PG_FUNCTION_ARGS)
The contributions semimod(v_i, token ⊗ k_i) of the aggregate result val, whose gate aggregates the co...
Datum provenance_semimod_nested(PG_FUNCTION_ARGS)
The semimodule gate of a row whose value is itself an aggregate result: semimod(the inner aggregate's...
Datum provenance_times(PG_FUNCTION_ARGS)
⊗ of a list of tokens.
static void name_begin(StringInfo buf, const char *prefix)
Start the name of a gate address.
Datum provenance_arith(PG_FUNCTION_ARGS)
The arith gate applying operator op (a provsql_arith_op, its info1) to children, in order.
static provsql_sha1_ctx name_hash
The hash of the name being built, which takes the buffer's content whenever it grows past NAME_FLUSH ...
static HTAB * written_values
Datum provenance_eq(PG_FUNCTION_ARGS)
The where-provenance eq gate of token, equating positions pos1 and pos2 (its infos).
static pg_uuid_t value_gate(const char *prefix, const char *suffix, const char *extra)
The value gate of the text str, at the address named name ("value" followed by str,...
Datum inversion_free_key(PG_FUNCTION_ARGS)
The order key of an input on the inversion-free route, "K<factor> <bytes of root>:<root><bytes of sec...
pg_uuid_t provsql_plant_canonical(const char *work_name, gate_type type, const pg_uuid_t *children, int n, const pg_uuid_t *target, unsigned info1, unsigned info2)
Pre-create ("plant") a gate at the canonical address of a multiset of tokens, for the working table o...
static const pg_uuid_t * address_of_zero(void)
pg_uuid_t provsql_build_delta(const pg_uuid_t *token)
δ(token), with δ(𝟘) = 𝟘 and δ(𝟙) = 𝟙.
static pg_uuid_t nary_gate(gate_type type, const char *plain_prefix, const char *canonical_prefix, const pg_uuid_t *children, int n)
A gate of type type over children, unless this backend planted one at the canonical address of their ...
Datum annotate(PG_FUNCTION_ARGS)
A transparent annotation gate over token, carrying extra.
static const pg_uuid_t * address_of_one(void)
static pg_uuid_t name_end(StringInfo buf)
The version-5 UUID of the name accumulated in buf.
static pg_uuid_t constant_uuid(const char *text)
The UUID text (one of the constants of provsql_utils.h).
static pg_uuid_t assumed_gate(const pg_uuid_t *token, const char *assumption, unsigned info1)
The assumed wrapper of token under assumption, with info1 as the route tag (0 for none).
Datum provenance_aggregate(PG_FUNCTION_ARGS)
The agg gate of a group, paired with the aggregate's value.
static void name_flush(StringInfo buf)
Hash what buf holds, and empty it.
static Datum semimod_gate(const pg_uuid_t *value_token, const pg_uuid_t *token)
The semimod gate value_token ⊗ token.
static void name_add_uuid_array(StringInfo buf, const pg_uuid_t *u, int n)
Append the text form of a uuid[], "{u1,u2,...}".
Datum provenance_plus(PG_FUNCTION_ARGS)
⊕ of an array of tokens.
static PlantedScope * planted_current
Datum planted_scope(PG_FUNCTION_ARGS)
SQL entry point of planted_open_scope(), called by the drivers of recursive CTEs right after they (re...
void provsql_gate_builders_forget(void)
Forget what gate_builders.c remembers of the store (planted gates, value gates written).
Datum provenance_cmp(PG_FUNCTION_ARGS)
The comparison gate left op right of a HAVING condition.
#define NAME_FLUSH
static HTAB * planted
static int token_cmp(const void *a, const void *b)
Datum provenance_assume(PG_FUNCTION_ARGS)
Wrap token in the assumption marker assumption ('boolean' or 'absorptive').
static int filtered_tokens(ArrayType *arr, const pg_uuid_t *neutral, pg_uuid_t **out)
The elements of a uuid[] that are neither NULL nor neutral, in order.
#define WRITTEN_VALUES_MAX
static pg_uuid_t canonical_address(const char *canonical_prefix, const pg_uuid_t *children, int n)
The canonical address, "<prefix>{sorted children}".
static bool is_planted(const pg_uuid_t *address)
Datum provenance_semimod(PG_FUNCTION_ARGS)
The semimodule gate val ⊗ token of an aggregated row.
static Oid temp_table_oid(const char *name)
OID of the temporary table name of this backend, if any.
static bool is_shift_of(const pg_uuid_t *sum, const pg_uuid_t *base)
Is sum the gate of base plus a nonzero constant?
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.
static int planted_next_id
Datum assume_boolean(PG_FUNCTION_ARGS)
The Boolean-assumption wrapper the safe-query rewriter puts on every per-row root,...
pg_uuid_t provsql_build_plus(const pg_uuid_t *tokens, int n)
⊕ of n tokens: 𝟘 dropped, none gives 𝟘, one is returned.
static void planted_forget(PlantedScope *scope)
Datum provenance_project(PG_FUNCTION_ARGS)
The where-provenance project gate of token: its text lists, for each output position,...
Datum plant_canonical(PG_FUNCTION_ARGS)
SQL entry point of provsql_plant_canonical().
static Datum uuid_result(const pg_uuid_t *u)
static const unsigned char provsql_ns[UUID_LEN]
uuid_ns_provsql(), the namespace of every gate address.
pg_uuid_t provsql_build_times(const pg_uuid_t *tokens, int n)
⊗ of n tokens: 𝟙 dropped, none gives 𝟙, one is returned.
static int drop_neutral(const pg_uuid_t *tokens, int n, const pg_uuid_t *neutral, pg_uuid_t *out)
Datum provenance_delta(PG_FUNCTION_ARGS)
δ(token).
static bool cmp_impossible(const pg_uuid_t *left, Oid op, const pg_uuid_t *right)
Does left op right hold in no world, by its shape alone?
static const pg_uuid_t * semimod_token_argument(FunctionCallInfo fcinfo)
static PlantedScope * planted_open_scope(const char *name, bool reset)
Open the scope of the working table name, just (re)created: forget what was planted for the table it ...
static PlantedScope * planted_scopes
static char * varchar_of_argument(FunctionCallInfo fcinfo, int argno)
CAST(val AS varchar) of argument argno, as a C string.
static bool same_token(const pg_uuid_t *a, const pg_uuid_t *b)
static void name_add_uuid(StringInfo buf, const pg_uuid_t *u)
Append a UUID in the text form of uuid_out.
Datum provenance_semimod_nullable(PG_FUNCTION_ARGS)
provenance_semimod for the aggregates that see their NULL inputs (array_agg, json_agg,...
The gate builders of the query rewriter, for C/C++ callers.
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
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.
gate_type provsql_fetch_gate(const pg_uuid_t *token, unsigned *nb_children_out, pg_uuid_t **children_out)
PostgreSQL-callable wrapper for get_gate_type().
void provsql_internal_get_infos(const pg_uuid_t *token, unsigned *info1, unsigned *info2)
Read a gate's info1 and info2, through the worker.
char * provsql_internal_get_extra(const pg_uuid_t *token)
Read a gate's extra text, through the worker; palloc'd.
Background worker and IPC primitives for mmap-backed circuit storage.
Core types, constants, and utilities shared across ProvSQL.
@ PROVSQL_ARITH_PLUS
n-ary, sum of children
#define PROVSQL_GATE_ZERO_UUID
UUID of the semiring zero gate: the result of the SQL function gate_zero(), created with the extensio...
#define PROVSQL_GATE_ONE_UUID
UUID of the semiring one gate, the result of gate_one().
@ gate_annotation
Transparent single-child wrapper carrying a query-level annotation in extra (inversion-free certifica...
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)
@ gate_assumed
Structural marker over a single child whose sub-circuit was computed under a Boolean-provenance assum...
@ PROVSQL_ROUTE_SQ_REWRITE
Hierarchical-CQ read-once rewrite (src/safe_query.c).
pg_uuid_t address
Hash key.
A working table with planted gates.
char name[NAMEDATALEN]
struct PlantedScope * next
Oid relid
The table, as created by the lowering.
CoercionPathType path
Aggregate token bundling a provenance UUID with a running value.
Definition agg_token.h:32
char tok[2 *UUID_LEN+5]
Provenance UUID as a text string.
Definition agg_token.h:33
The state of an incremental SHA-1: the digest of a text given in pieces, without holding it whole (th...