ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
BooleanCircuit.cpp
Go to the documentation of this file.
1/**
2 * @file BooleanCircuit.cpp
3 * @brief Boolean circuit implementation and evaluation algorithms.
4 *
5 * Implements the methods declared in @c BooleanCircuit.h, including:
6 * - Gate management (@c addGate, @c setGate, @c setInfo, @c setProb).
7 * - Probability evaluation algorithms: possible worlds, Monte Carlo,
8 * WeightMC, independent evaluation.
9 * - Knowledge compilation: @c compilation() (external tools),
10 * @c interpretAsDD() (direct from circuit structure),
11 * @c makeDD() (dispatcher).
12 * - @c rewriteMultivaluedGates(): replaces MULVAR/MULIN clusters with
13 * standard AND/OR/NOT circuits.
14 * - @c TseytinCNF(): DIMACS/weighted CNF generation for model counters.
15 * - @c exportCircuit(): serialisation in the @c tdkc text format.
16 * - @c toString(): human-readable gate description.
17 *
18 * In the standalone @c tdkc build (when @c TDKC is defined) a lightweight
19 * @c elog() stub replaces the PostgreSQL error-reporting function.
20 */
21#include "BooleanCircuit.h"
22#include "Circuit.hpp"
23#include <type_traits>
24
25extern "C" {
26#include <unistd.h>
27#include <sys/wait.h>
28#include <math.h>
29}
30
31#include <cassert>
32#include <cstdint>
33#include <string>
34#include <fstream>
35#include <sstream>
36#include <cstdlib>
37#include <iostream>
38#include <random>
39#include <vector>
40#include <stack>
41#include <functional>
42#include <algorithm>
43
44#include <boost/archive/text_oarchive.hpp>
45#include <boost/archive/text_iarchive.hpp>
46
48#include "external_tool.h"
49// The tool registry drives external-tool selection and invocation, all of
50// which lives in #ifndef TDKC blocks (tdkc invokes no external tool), so the
51// registry is needed only in the extension build.
52#ifndef TDKC
53#include "ToolRegistry.h"
54#include "kcmcp_client.h"
55#include "provsql_interrupt.h"
56#endif
57
58#ifdef TDKC
59/** Size past which @c toStringHelper stops: PG's limit for a text value
60 * (@c provsql_max_result_size in the extension). */
61static constexpr std::size_t max_rendering_size = std::size_t(1) << 30;
62#endif
63
64/** The error of @c toStringHelper past PG's limit for a text value. */
65static constexpr const char *too_large_to_print =
66 "the Boolean expression is too large to print (over 1 GB): a sub-circuit "
67 "shared by several gates is written out at each of them";
68
69// "provsql_utils.h"
70#ifdef TDKC
71constexpr bool provsql_interrupted = false;
72[[maybe_unused]] constexpr int provsql_verbose = 0;
73constexpr int provsql_monte_carlo_seed = -1;
74// makeDD's final fallback uses this GUC in the extension build; the
75// standalone tdkc tool has no GUC layer, so default it to "d4".
76[[maybe_unused]] constexpr const char *provsql_fallback_compiler = "d4";
77enum levels {ERROR, NOTICE};
78#define elog(level, ...) {fprintf(stderr, __VA_ARGS__); if(level==ERROR) exit(EXIT_FAILURE);}
79#define CHECK_FOR_INTERRUPTS() ((void)0)
80// The standalone tool has no PostgreSQL stack-depth governor; its deep
81// recursions (tree decomposition, d-DNNF) already run on heap stacks.
82#define check_stack_depth() ((void)0)
83#else
84extern "C" {
85#include "provsql_utils.h"
86#include "utils/elog.h"
87#include "miscadmin.h"
88}
89#endif
90#include "provsql_error.h"
91#include "scoped_tempdir.h"
93
94namespace {
95
96/**
97 * @brief Best-effort parse of a model counter's "result line".
98 *
99 * Ganak, SharpSAT-TD, and DPMC each emit their final count on a
100 * line like @c "c s exact arb float 0.4350..." or
101 * @c "c s exact arb int 12345" (and DPMC also accepts the older
102 * @c "s wmc N" shape). Keeping the right-most whitespace-separated
103 * token and feeding it to @c std::stod would rely on the value always
104 * being last on the line, which the DPMC source itself notes is not
105 * stable across versions (a trailing @c "(cputime ...)" suffix would
106 * silently corrupt the parse).
107 *
108 * This helper scans tokens right-to-left and returns the
109 * right-most one that parses as a @c double or as a
110 * @c <num>/<den> rational. Throws a clear
111 * @c "<tool>: could not parse '<line>'" instead of letting
112 * @c std::stod's @c std::invalid_argument leak through.
113 */
114#ifndef TDKC // external model-counter output parser; tdkc runs no counter
115double parse_wmc_value(const std::string &line, const char *tool) {
116 std::vector<std::string> tokens;
117 std::stringstream ss(line);
118 std::string tok;
119 while(ss >> tok) tokens.push_back(tok);
120
121 for(auto it = tokens.rbegin(); it != tokens.rend(); ++it) {
122 const std::string &t = *it;
123 try {
124 auto slash = t.find('/');
125 if(slash != std::string::npos) {
126 size_t pn = 0, pd = 0;
127 double num = std::stod(t.substr(0, slash), &pn);
128 double den = std::stod(t.substr(slash + 1), &pd);
129 if(pn != slash || pd != t.size() - slash - 1) continue;
130 return (den == 0.0) ? 0.0 : num / den;
131 }
132 size_t p = 0;
133 double v = std::stod(t, &p);
134 if(p == t.size()) return v;
135 } catch(const std::exception &) {
136 // Not a number; try the next token to the left.
137 }
138 }
139 throw CircuitException(std::string(tool) + ": could not parse '" + line + "'");
140}
141#endif
142
143} // anonymous namespace
144
146{
147 auto id = Circuit::setGate(type);
148 if(type == BooleanGate::IN) {
149 setProb(id,1.);
150 inputs.insert(id);
151 } else if(type == BooleanGate::MULIN) {
152 mulinputs.insert(id);
153 }
154 return id;
155}
156
158{
159 auto id = Circuit::setGate(u, type);
160 if(type == BooleanGate::IN) {
161 setProb(id,1.);
162 inputs.insert(id);
163 } else if(type == BooleanGate::MULIN) {
164 mulinputs.insert(id);
165 }
166 return id;
167}
168
170{
171 auto id = setGate(u, type);
172 if(std::isnan(p))
173 p=1.;
174 setProb(id,p);
175 return id;
176}
177
179{
180 auto id = setGate(type);
181 if(std::isnan(p))
182 p=1.;
183 setProb(id,p);
184 return id;
185}
186
188{
189 auto id=Circuit::addGate();
190 prob.push_back(1);
191 return id;
192}
193
195{
196 return toStringHelper(g, BooleanGate::UNDETERMINED, nullptr);
197}
198
200 gate_t g,
201 const std::unordered_map<gate_t, std::string> &labels) const
202{
203 return toStringHelper(g, BooleanGate::UNDETERMINED, &labels);
204}
205
207 gate_t g,
208 BooleanGate parent,
209 const std::unordered_map<gate_t, std::string> *labels) const
210{
211 /* The rendering is a formula: a sub-circuit shared by several gates is
212 * written out at each of them, so it can be exponential in the circuit
213 * (that of a recursion on cyclic data, for one). Stay interruptible, and
214 * stop before the text could not be returned anyway. */
216 throw CircuitException("Interrupted");
217
218 std::string op;
219 std::string result;
220 auto gtype = getGateType(g);
221
222 switch(gtype) {
223 case BooleanGate::IN:
224 if(labels) {
225 auto it = labels->find(g);
226 if(it != labels->end())
227 return it->second;
228 }
229 return "x"+to_string(g);
231 if(labels) {
232 auto it = labels->find(g);
233 if(it != labels->end())
234 return "{" + to_string(*getWires(g).begin()) + "=" + it->second +
235 "}[" + std::to_string(getProb(g)) + "]";
236 }
237 return "{" + to_string(*getWires(g).begin()) + "=" + std::to_string(getInfo(g)) + "}[" + std::to_string(getProb(g)) + "]";
238 case BooleanGate::NOT:
239 op="¬";
240 break;
242 op="?";
243 break;
244 case BooleanGate::AND:
245 op="∧";
246 break;
247 case BooleanGate::OR:
248 op="∨";
249 break;
251 ; // already dealt with in MULIN
252 }
253
254 if(getWires(g).empty()) {
255 if(gtype==BooleanGate::AND)
256 return "⊤";
257 else if(gtype==BooleanGate::OR)
258 return "⊥";
259 else return op;
260 }
261
262 for(auto s: getWires(g)) {
263 if(gtype==BooleanGate::NOT)
264 result = op;
265 else if(!result.empty())
266 result+=" "+op+" ";
267 result+=toStringHelper(s, gtype, labels);
268#ifdef TDKC
269 if(result.size() > max_rendering_size)
271#else
272 /* A program_limit_exceeded error (54000), as provsql.max_memory */
274#endif
275 }
276
277 // Parenthesis elision:
278 // * single-wire AND/OR: the join carries no information, drop the wrap.
279 // * root call (parent = UNDETERMINED): no enclosing context, drop the wrap.
280 // * same-op nesting (parent == gtype, AND/OR only): associative, drop the wrap.
281 bool single_join = (gtype==BooleanGate::AND || gtype==BooleanGate::OR)
282 && getWires(g).size()==1;
283 bool same_op_assoc = (gtype==BooleanGate::AND || gtype==BooleanGate::OR)
284 && parent==gtype;
285 if(single_join || parent==BooleanGate::UNDETERMINED || same_op_assoc)
286 return result;
287 return "("+result+")";
288}
289
291{
292 std::stringstream ss;
293
294 std::unordered_set<gate_t> processed;
295 std::stack<gate_t> to_process;
296 to_process.push(root);
297
298 while(!to_process.empty()) {
299 auto g=to_process.top();
300 to_process.pop();
301
302 if(processed.find(g)!=processed.end())
303 continue;
304
305 ss << g << " ";
306
307 switch(getGateType(g)) {
308 case BooleanGate::IN:
309 ss << "IN " << getProb(g);
310 break;
311
312 case BooleanGate::NOT:
313 ss << "NOT " << getWires(g)[0];
314 break;
315
316 case BooleanGate::AND:
317 ss << "AND";
318
319 for(auto s:getWires(g))
320 ss << " " << s;
321 break;
322
323 case BooleanGate::OR:
324 ss << "OR";
325
326 for(auto s:getWires(g))
327 ss << " " << s;
328 break;
329
333 assert(false); // not done
334 }
335
336 ss << "\n";
337
338 for(auto s: getWires(g)) {
339 if(processed.find(s)==processed.end())
340 to_process.push(s);
341 }
342
343 processed.insert(g);
344 }
345
346 return ss.str();
347}
348
349bool BooleanCircuit::evaluate(gate_t g, const std::unordered_set<gate_t> &sampled) const
350{
351 /* Memoised: a sub-circuit shared by several gates is evaluated once, not
352 * once per path to it, which is exponential on a circuit with sharing
353 * (that of a recursion on cyclic data, for one). */
354 std::vector<signed char> memo(gates.size(), -1);
355 return evaluate(g, sampled, memo);
356}
357
358bool BooleanCircuit::evaluate(gate_t g, const std::unordered_set<gate_t> &sampled,
359 std::vector<signed char> &memo) const
360{
361 check_stack_depth(); // recurses on wires; guard deep circuits (see GenericCircuit::evaluate)
362 auto &m = memo[static_cast<std::size_t>(g)];
363 if(m >= 0)
364 return m;
366 throw CircuitException("Interrupted");
367
368 bool disjunction=false;
369 bool value;
370
371 switch(getGateType(g)) {
372 case BooleanGate::IN:
373 value = sampled.find(g)!=sampled.end();
374 m = value;
375 return value;
378 throw CircuitException("Monte-Carlo sampling not implemented on multivalued inputs");
379 case BooleanGate::NOT:
380 value = !evaluate(*(getWires(g).begin()), sampled, memo);
381 memo[static_cast<std::size_t>(g)] = value;
382 return value;
383 case BooleanGate::AND:
384 disjunction = false;
385 break;
386 case BooleanGate::OR:
387 disjunction = true;
388 break;
390 throw CircuitException("Incorrect gate type");
391 }
392
393 /* An OR with a true wire is true, an AND with a false one false; with no
394 * such wire, an OR is false and an AND true. */
395 value = !disjunction;
396 for(auto s: getWires(g))
397 if(evaluate(s, sampled, memo) == disjunction) {
398 value = disjunction;
399 break;
400 }
401 memo[static_cast<std::size_t>(g)] = value;
402 return value;
403}
404
405double BooleanCircuit::monteCarlo(gate_t g, unsigned samples) const
406{
407 // Seed mt19937_64 from the provsql.monte_carlo_seed GUC: -1 (the
408 // default) means non-deterministic via std::random_device, any other
409 // value (including 0) is a literal seed so regression tests can pin
410 // sampling for reproducibility.
411 std::mt19937_64 rng;
412 if(provsql_monte_carlo_seed != -1) {
413 rng.seed(static_cast<uint64_t>(provsql_monte_carlo_seed));
414 } else {
415 std::random_device rd;
416 rng.seed((static_cast<uint64_t>(rd()) << 32) | rd());
417 }
418 std::uniform_real_distribution<double> uniform01(0.0, 1.0);
419
420 auto success{0u};
421
422 for(unsigned i=0; i<samples; ++i) {
423 std::unordered_set<gate_t> sampled;
424 for(auto in: inputs) {
425 if(uniform01(rng) < getProb(in)) {
426 sampled.insert(in);
427 }
428 }
429
430 if(evaluate(g, sampled))
431 ++success;
432
434 throw CircuitException("Interrupted after "+std::to_string(i+1)+" samples");
435 }
436
437 return success*1./samples;
438}
439
441 gate_t g,
442 std::vector<gate_t> &clauses,
443 std::vector<std::set<gate_t> > &supports) const
444{
445 clauses.clear();
446 supports.clear();
447
448 // A top-level OR exposes one clause per child; anything else is a single
449 // clause rooted at g itself (regime (a): a bare AND-of-leaves or a lone
450 // input).
451 std::vector<gate_t> clause_roots;
453 for(auto c: getWires(g))
454 clause_roots.push_back(c);
455 } else {
456 clause_roots.push_back(g);
457 }
458
459 for(auto root: clause_roots) {
460 // Sweep the AND-only stratum below this clause root, collecting the
461 // reachable input leaves. Any OR (nested disjunction), NOT
462 // (negation), or multivalued input below the root takes the circuit
463 // out of regimes (a)/(b): bail.
464 std::set<gate_t> support;
465 std::unordered_set<gate_t> seen;
466 std::stack<gate_t> st;
467 st.push(root);
468 while(!st.empty()) {
469 gate_t cur = st.top();
470 st.pop();
471 if(!seen.insert(cur).second)
472 continue;
473 switch(getGateType(cur)) {
474 case BooleanGate::IN:
475 support.insert(cur);
476 break;
477 case BooleanGate::AND:
478 for(auto s: getWires(cur))
479 st.push(s);
480 break;
481 default:
482 return false;
483 }
484 }
485 clauses.push_back(root);
486 supports.push_back(std::move(support));
487 }
488
489 return true;
490}
491
492bool BooleanCircuit::dnfShapeInfo(gate_t g, std::size_t &num_clauses) const
493{
494 // Clause count: children of a top-level OR, else a single clause rooted at g.
495 std::vector<gate_t> clause_roots;
497 for(auto c: getWires(g))
498 clause_roots.push_back(c);
499 else
500 clause_roots.push_back(g);
501 num_clauses = clause_roots.size();
502
503 // Validate the AND-only strata below every clause root with ONE global
504 // visited-set (each gate's type is path-independent), so a shared subgraph is
505 // checked once and no per-clause supports are materialised. O(circuit).
506 std::unordered_set<gate_t> seen;
507 std::stack<gate_t> st;
508 for(auto r: clause_roots)
509 st.push(r);
510 while(!st.empty()) {
511 gate_t cur = st.top();
512 st.pop();
513 if(!seen.insert(cur).second)
514 continue;
515 switch(getGateType(cur)) {
516 case BooleanGate::IN:
517 break;
518 case BooleanGate::AND:
519 for(auto s: getWires(cur))
520 st.push(s);
521 break;
522 default:
523 return false;
524 }
525 }
526 return true;
527}
528
529namespace {
530
531/**
532 * Shared Karp-Luby sampler state derived from the per-clause supports:
533 * the per-clause probability @c p_i = product of its support-leaf marginals,
534 * the prefix sums for the O(log m) categorical clause draw, the union-bound
535 * total @c S = sum p_i (with @c Pr[F] <= S <= m*Pr[F]), and the set of leaves
536 * that can affect clause membership (only those need to be drawn each round).
537 */
538struct KarpLubyState {
539 std::vector<double> p;
540 std::vector<double> cumulative;
541 double S = 0.;
542 std::vector<gate_t> relevant;
543};
544
545KarpLubyState karpLubyState(
546 const BooleanCircuit &c,
547 const std::vector<std::set<gate_t> > &supports)
548{
549 KarpLubyState st;
550 const size_t m = supports.size();
551 st.p.resize(m);
552 st.cumulative.resize(m);
553 std::set<gate_t> rel;
554 for(size_t i=0; i<m; ++i) {
555 double pi = 1.;
556 for(gate_t leaf: supports[i]) {
557 pi *= c.getProb(leaf);
558 rel.insert(leaf);
559 }
560 st.p[i] = pi;
561 st.S += pi;
562 st.cumulative[i] = st.S;
563 }
564 st.relevant.assign(rel.begin(), rel.end());
565 return st;
566}
567
568/// Seed mt19937_64 from provsql.monte_carlo_seed exactly as monteCarlo, so a
569/// pinned seed makes the estimate reproducible for the regression tests.
570std::mt19937_64 karpLubySeededRNG()
571{
572 std::mt19937_64 rng;
573 if(provsql_monte_carlo_seed != -1) {
574 rng.seed(static_cast<uint64_t>(provsql_monte_carlo_seed));
575 } else {
576 std::random_device rd;
577 rng.seed((static_cast<uint64_t>(rd()) << 32) | rd());
578 }
579 return rng;
580}
581
582/// Draw a clause index with probability @c p_i / S using the prefix sums.
583size_t karpLubyDrawClause(const KarpLubyState &st,
584 std::mt19937_64 &rng,
585 std::uniform_real_distribution<double> &u01)
586{
587 double u = u01(rng) * st.S;
588 size_t i = static_cast<size_t>(
589 std::upper_bound(st.cumulative.begin(), st.cumulative.end(), u)
590 - st.cumulative.begin());
591 if(i >= st.cumulative.size())
592 i = st.cumulative.size() - 1; // guard against u == S from rounding
593 return i;
594}
595
596/**
597 * One Karp-Luby coverage trial in clause @p i: sample an assignment of
598 * @c C_i (its support forced true, every other relevant leaf drawn from its
599 * marginal), then return whether @p i is the smallest-index clause the
600 * assignment satisfies -- the coverage rejection that divides the over-count
601 * @c S by the number of clauses covering each sampled world. @p trueLeaves is
602 * reused across calls to avoid reallocating.
603 */
604bool karpLubyCovers(
605 const BooleanCircuit &c,
606 const std::vector<std::set<gate_t> > &supports,
607 const KarpLubyState &st, size_t i,
608 std::mt19937_64 &rng,
609 std::uniform_real_distribution<double> &u01,
610 std::unordered_set<gate_t> &trueLeaves)
611{
612 trueLeaves.clear();
613 for(gate_t leaf: st.relevant) {
614 if(supports[i].count(leaf) || u01(rng) < c.getProb(leaf))
615 trueLeaves.insert(leaf);
616 }
617 const size_t m = supports.size();
618 for(size_t j=0; j<m; ++j) {
619 bool sat = true;
620 for(gate_t leaf: supports[j]) {
621 if(trueLeaves.find(leaf)==trueLeaves.end()) { sat = false; break; }
622 }
623 if(sat)
624 return j==i;
625 }
626 return false; // unreachable: clause i always covers its own forced support
627}
628
629} // anonymous namespace
630
632 const std::vector<gate_t> &clauses,
633 const std::vector<std::set<gate_t> > &supports,
634 unsigned long samples) const
635{
636 const size_t m = clauses.size();
637 if(m==0 || samples==0)
638 return 0.;
639
640 KarpLubyState st = karpLubyState(*this, supports);
641 if(st.S<=0.)
642 return 0.;
643
644 std::mt19937_64 rng = karpLubySeededRNG();
645 std::uniform_real_distribution<double> u01(0.0, 1.0);
646 std::unordered_set<gate_t> trueLeaves;
647
648 // Fewer rounds than clauses: too few to stratify (every clause needs at
649 // least one sample for its per-clause acceptance rate to be defined), so
650 // fall back to the unstratified categorical-draw estimator -- S times the
651 // overall acceptance ratio, still unbiased for any budget.
652 if(samples < m) {
653 unsigned long accepts = 0;
654 for(unsigned long s=0; s<samples; ++s) {
655 size_t i = karpLubyDrawClause(st, rng, u01);
656 if(karpLubyCovers(*this, supports, st, i, rng, u01, trueLeaves))
657 ++accepts;
659 throw CircuitException("Interrupted after "+std::to_string(s+1)+" samples");
660 }
661 return st.S * accepts / static_cast<double>(samples);
662 }
663
664 // Stratified allocation: n_i = 1 + proportional share of (samples - m) by
665 // p_i / S, with the leftover rounds handed to the largest fractional parts
666 // (largest-remainder rounding) so the n_i stay proportional and sum to
667 // exactly `samples`. Estimating each clause's acceptance rate separately
668 // and combining sum_i p_i * rate_i removes the categorical-draw
669 // (between-strata) variance of the textbook estimator, tightening the
670 // estimate at the same budget by up to a factor m.
671 std::vector<unsigned long> n(m, 1);
672 const unsigned long rest = samples - m;
673 std::vector<double> frac(m);
674 unsigned long base_sum = 0;
675 for(size_t i=0; i<m; ++i) {
676 double want = static_cast<double>(rest) * st.p[i] / st.S;
677 unsigned long fl = static_cast<unsigned long>(want);
678 n[i] += fl;
679 base_sum += fl;
680 frac[i] = want - static_cast<double>(fl);
681 }
682 unsigned long leftover = rest - base_sum;
683 if(leftover > 0) {
684 std::vector<size_t> idx(m);
685 for(size_t i=0; i<m; ++i) idx[i] = i;
686 std::partial_sort(idx.begin(), idx.begin()+leftover, idx.end(),
687 [&](size_t a, size_t b){ return frac[a] > frac[b]; });
688 for(unsigned long k=0; k<leftover; ++k)
689 ++n[idx[k]];
690 }
691
692 double est = 0.;
693 for(size_t i=0; i<m; ++i) {
694 unsigned long accepts = 0;
695 for(unsigned long k=0; k<n[i]; ++k) {
696 if(karpLubyCovers(*this, supports, st, i, rng, u01, trueLeaves))
697 ++accepts;
699 throw CircuitException("Interrupted while sampling clause "
700 +std::to_string(i));
701 }
702 est += st.p[i] * static_cast<double>(accepts) / static_cast<double>(n[i]);
703 }
704 return est;
705}
706
708 const std::vector<gate_t> &clauses,
709 const std::vector<std::set<gate_t> > &supports,
710 double eps, double delta,
711 unsigned long max_samples,
712 unsigned long &samples_used,
713 bool &reached_target) const
714{
715 samples_used = 0;
716 reached_target = false;
717 const size_t m = clauses.size();
718 if(m==0 || max_samples==0)
719 return 0.;
720
721 KarpLubyState st = karpLubyState(*this, supports);
722 if(st.S<=0.)
723 return 0.;
724
725 // DKLR stopping threshold on the accept count: Y1 = 1 + (1+eps)*Y with
726 // Y = 4*(e-2)*ln(2/delta)/eps^2. Sample coverage trials until the accept
727 // count reaches Y1 and return S*Y1/N (a relative (eps,delta) estimate of
728 // Pr[F]); the number of rounds N then adapts to the true acceptance
729 // probability Pr[F]/S in [1/m, 1] -- up to m times fewer rounds than the
730 // fixed bound when the clauses barely overlap.
731 const double e = exp(1.0);
732 const double Y = 4.0 * (e - 2.0) * log(2.0/delta) / (eps*eps);
733 const double Y1 = 1.0 + (1.0 + eps) * Y;
734
735 std::mt19937_64 rng = karpLubySeededRNG();
736 std::uniform_real_distribution<double> u01(0.0, 1.0);
737 std::unordered_set<gate_t> trueLeaves;
738
739 unsigned long accepts = 0;
740 for(unsigned long s=0; s<max_samples; ++s) {
741 size_t i = karpLubyDrawClause(st, rng, u01);
742 if(karpLubyCovers(*this, supports, st, i, rng, u01, trueLeaves)) {
743 ++accepts;
744 if(static_cast<double>(accepts) >= Y1) {
745 samples_used = s + 1;
746 reached_target = true;
747 return st.S * Y1 / static_cast<double>(samples_used);
748 }
749 }
751 throw CircuitException("Interrupted after "+std::to_string(s+1)+" samples");
752 }
753
754 // Cap reached before the threshold: the (eps,delta) target is not met, so
755 // return the plain unbiased S*accepts/N estimate over the spent budget (the
756 // caller reports the weaker guarantee actually achieved).
757 samples_used = max_samples;
758 return st.S * static_cast<double>(accepts) / static_cast<double>(max_samples);
759}
760
761/// Largest clause count for which the 2^m sieve enumeration is admitted.
762static const size_t kSieveMaxClauses = 24;
763
765 const std::vector<gate_t> &clauses,
766 const std::vector<std::set<gate_t> > &supports) const
767{
768 const size_t m = clauses.size();
769 if(m == 0)
770 return 0.;
771 if(m > kSieveMaxClauses)
772 throw CircuitException(
773 "sieve: too many clauses (" + std::to_string(m) + " > "
774 + std::to_string(kSieveMaxClauses)
775 + "); inclusion-exclusion is 2^m -- use another method");
776
777 // Pr[∨ c_i] = Σ_{∅≠S} (-1)^{|S|+1} ∏_{leaf ∈ ∪supports(S)} getProb(leaf).
778 double total = 0.;
779 std::unordered_set<gate_t> u;
780 for(unsigned long long s = 1; s < (1ULL << m); ++s) {
781 u.clear();
782 int bits = 0;
783 for(size_t i = 0; i < m; ++i)
784 if(s & (1ULL << i)) {
785 ++bits;
786 for(gate_t leaf : supports[i])
787 u.insert(leaf);
788 }
789 double p = 1.;
790 for(gate_t leaf : u)
791 p *= getProb(leaf);
792 if(bits & 1) total += p; else total -= p;
793
795 throw CircuitException("Interrupted");
796 }
797 return total;
798}
799
801 const std::vector<std::set<gate_t> > &clauses,
802 double &lower, double &upper) const
803{
804 const size_t m = clauses.size();
805 if(m == 0) {
806 lower = upper = 0.;
807 return;
808 }
809
810 // Per-clause probability P(d) = ∏_{leaf ∈ clauses[d]} getProb(leaf) (an empty
811 // support is a constant-true clause, product over the empty set = 1).
812 std::vector<double> clause_prob(m);
813 for(size_t i = 0; i < m; ++i) {
814 double p = 1.;
815 for(gate_t leaf : clauses[i])
816 p *= getProb(leaf);
817 clause_prob[i] = p;
818 }
819
820 // Greedy partition into buckets of pairwise-independent clauses, clauses taken
821 // in descending marginal-probability order (the paper's improved heuristic).
822 std::vector<size_t> order(m);
823 for(size_t i = 0; i < m; ++i)
824 order[i] = i;
825 std::sort(order.begin(), order.end(),
826 [&](size_t a, size_t b) {
827 return clause_prob[a] > clause_prob[b];
828 });
829
830 // For each bucket: the union of its clauses' supports (to test independence in
831 // O(|support|) against the whole bucket at once -- disjoint from the union iff
832 // independent of every clause already in it) and its running independent-or
833 // probability 1 - ∏(1 - P(d)).
834 std::vector<std::set<gate_t> > bucket_support;
835 std::vector<double> bucket_prob;
836 for(size_t idx : order) {
837 const std::set<gate_t> &sup = clauses[idx];
838 size_t target = bucket_support.size(); // default: open a new bucket
839 for(size_t b = 0; b < bucket_support.size(); ++b) {
840 bool disjoint = true;
841 for(gate_t leaf : sup)
842 if(bucket_support[b].count(leaf)) {
843 disjoint = false;
844 break;
845 }
846 if(disjoint) {
847 target = b;
848 break;
849 }
850 }
851 if(target == bucket_support.size()) {
852 bucket_support.emplace_back();
853 bucket_prob.push_back(0.);
854 }
855 bucket_prob[target] =
856 1. - (1. - bucket_prob[target]) * (1. - clause_prob[idx]);
857 bucket_support[target].insert(sup.begin(), sup.end());
858
860 throw CircuitException("Interrupted");
861 }
862
863 // lower = max bucket probability (each bucket is a sub-disjunction of Φ);
864 // upper = min(1, Σ bucket probabilities) (union bound over the buckets).
865 double L = 0., U = 0.;
866 for(double bp : bucket_prob) {
867 if(bp > L)
868 L = bp;
869 U += bp;
870 }
871 lower = L;
872 upper = (U > 1.) ? 1. : U;
873}
874
876{
877 /* Enumerate only the inputs reachable from g. An input the root does
878 * not reach factors out of every world (its two branches sum to 1), so
879 * restricting the enumeration returns the identical probability -- and
880 * the circuit object routinely carries gates the evaluated root no
881 * longer reaches (e.g. a categorical mulinput block whose comparison
882 * the analytic pre-pass collapsed to a single Bernoulli), which would
883 * otherwise inflate the enumeration exponentially for nothing. */
884 std::set<gate_t> rinputs;
885 {
886 std::unordered_set<gate_t> seen;
887 std::stack<gate_t> stk;
888 stk.push(g);
889 while(!stk.empty()) {
890 gate_t u = stk.top(); stk.pop();
891 if(!seen.insert(u).second) continue;
892 if(getGateType(u) == BooleanGate::IN) rinputs.insert(u);
893 for(gate_t w: getWires(u)) stk.push(w);
894 }
895 }
896
897 if(rinputs.size()>=8*sizeof(unsigned long long))
898 throw CircuitException("Too many possible worlds to iterate over");
899
900 unsigned long long nb=(1ULL<<rinputs.size());
901 double totalp=0.;
902
903 for(unsigned long long i=0; i < nb; ++i) {
904 std::unordered_set<gate_t> s;
905 double p = 1;
906
907 unsigned j=0;
908 for(gate_t in : rinputs) {
909 if(i & (1ULL << j)) {
910 s.insert(in);
911 p*=getProb(in);
912 } else {
913 p*=1-getProb(in);
914 }
915 ++j;
916 }
917
918 if(evaluate(g, s))
919 totalp+=p;
920
922 throw CircuitException("Interrupted");
923 }
924
925 return totalp;
926}
927
928std::string BooleanCircuit::TseytinCNF(gate_t g, bool display_prob, bool mapping) const {
929 std::vector<std::vector<int> > clauses;
930
931 // Tseytin transformation
932 for(gate_t i{0}; i<gates.size(); ++i) {
933 switch(getGateType(i)) {
934 case BooleanGate::AND:
935 {
936 int id{static_cast<int>(i)+1};
937 std::vector<int> c = {id};
938 for(auto s: getWires(i)) {
939 clauses.push_back({-id, static_cast<int>(s)+1});
940 c.push_back(-static_cast<int>(s)-1);
941 }
942 clauses.push_back(c);
943 break;
944 }
945
946 case BooleanGate::OR:
947 {
948 int id{static_cast<int>(i)+1};
949 std::vector<int> c = {-id};
950 for(auto s: getWires(i)) {
951 clauses.push_back({id, -static_cast<int>(s)-1});
952 c.push_back(static_cast<int>(s)+1);
953 }
954 clauses.push_back(c);
955 }
956 break;
957
958 case BooleanGate::NOT:
959 {
960 int id=static_cast<int>(i)+1;
961 auto s=*getWires(i).begin();
962 clauses.push_back({-id,-static_cast<int>(s)-1});
963 clauses.push_back({id,static_cast<int>(s)+1});
964 break;
965 }
966
968 throw CircuitException("Multivalued inputs should have been removed by then.");
970 case BooleanGate::IN:
972 ;
973 }
974 }
975 clauses.push_back({(int)g+1});
976
977 std::ostringstream oss;
978 // Optional self-documenting mapping, emitted as DIMACS comments
979 // before the problem line so a saved CNF records which provenance
980 // input each variable stands for. Comments are ignored by every
981 // model counter / compiler, so the file stays valid DIMACS.
982 if(mapping) {
983 for(const auto &m : tseytinVariableMapping()) {
984 oss << "c input " << m.variable << " "
985 << (m.uuid.empty() ? "?" : m.uuid) << " "
986 << m.probability << "\n";
987 }
988 }
989 oss << "p cnf " << gates.size() << " " << clauses.size() << "\n";
990 for(unsigned i=0; i<clauses.size(); ++i) {
991 for(int x : clauses[i]) {
992 oss << x << " ";
993 }
994 oss << "0\n";
995 }
996 if(display_prob) {
997 for(gate_t in: inputs) {
998 oss << "w " << (static_cast<std::underlying_type<gate_t>::type>(in)+1) << " " << getProb(in) << "\n";
999 oss << "w -" << (static_cast<std::underlying_type<gate_t>::type>(in)+1) << " " << (1. - getProb(in)) << "\n";
1000 }
1001 }
1002 return oss.str();
1003}
1004
1005std::vector<BooleanCircuit::CNFInputMapping>
1007 std::vector<CNFInputMapping> mapping;
1008 // `inputs` is a std::set<gate_t>, so iteration is in gate-id order
1009 // and the variable indices (id + 1) come out sorted and stable.
1010 for(gate_t in : inputs) {
1011 auto id = static_cast<std::underlying_type<gate_t>::type>(in);
1012 mapping.push_back({static_cast<int>(id) + 1, getUUID(in), getProb(in)});
1013 }
1014 return mapping;
1015}
1016
1017std::string BooleanCircuit::BCS12(gate_t g, std::vector<gate_t> &inputOrder) const {
1018 inputOrder.clear();
1019 auto idOf = [](gate_t x) {
1020 return static_cast<std::underlying_type<gate_t>::type>(x);
1021 };
1022
1023 std::set<gate_t> seenInputs;
1024 std::set<gate_t> internalGates; // AND/OR gates to emit, ordered by id
1025
1026 // Resolve a wire to a BC-S1.2 literal, inlining NOT chains as sign flips.
1027 std::function<std::string(gate_t)> lit = [&](gate_t w) -> std::string {
1028 switch(getGateType(w)) {
1029 case BooleanGate::IN:
1030 return "in" + std::to_string(idOf(w));
1031 case BooleanGate::AND:
1032 case BooleanGate::OR:
1033 return "g" + std::to_string(idOf(w));
1034 case BooleanGate::NOT: {
1035 std::string inner = lit(*getWires(w).begin());
1036 return inner[0]=='-' ? inner.substr(1) : "-"+inner;
1037 }
1038 default:
1039 throw CircuitException("BC-S1.2 export: unsupported gate type");
1040 }
1041 };
1042
1043 // DFS collecting input gates (in first-seen order, fixing their d4
1044 // variable numbers) and the AND/OR gates to define; NOT gates are
1045 // traversed but never named.
1046 std::function<void(gate_t)> collect = [&](gate_t w) {
1047 switch(getGateType(w)) {
1048 case BooleanGate::IN:
1049 if(seenInputs.insert(w).second)
1050 inputOrder.push_back(w);
1051 break;
1052 case BooleanGate::NOT:
1053 collect(*getWires(w).begin());
1054 break;
1055 case BooleanGate::AND:
1056 case BooleanGate::OR:
1057 if(internalGates.insert(w).second)
1058 for(gate_t c : getWires(w))
1059 collect(c);
1060 break;
1061 default:
1062 throw CircuitException("BC-S1.2 export: unsupported gate type");
1063 }
1064 };
1065 collect(g);
1066
1067 std::ostringstream oss;
1068 oss << "c BC-S1.2\n";
1069 // Inputs first: d4 numbers them 1..k in this order (see header doc).
1070 for(gate_t in : inputOrder)
1071 oss << "I in" << idOf(in) << "\n";
1072 for(gate_t w : internalGates) {
1073 const auto &ch = getWires(w);
1074 if(ch.empty())
1075 throw CircuitException("BC-S1.2 export: nullary gate");
1076 oss << "G g" << idOf(w) << " := ";
1077 // BC-S1.2 requires >= 2 literals for A/O; a unary AND/OR is the identity.
1078 if(ch.size()==1)
1079 oss << "I";
1080 else
1081 oss << (getGateType(w)==BooleanGate::AND ? "A" : "O");
1082 for(gate_t c : ch)
1083 oss << " " << lit(c);
1084 oss << "\n";
1085 }
1086 oss << "T " << lit(g) << "\n";
1087 return oss.str();
1088}
1089
1090// ---------------------------------------------------------------------------
1091// External-tool knowledge compilation and weighted model counting.
1092//
1093// The standalone tdkc tool deliberately invokes NO external tool (it compiles
1094// purely via tree decomposition), so this whole block -- the knowledge
1095// compilers, the Panini wrapper, the weighted model counters, and the
1096// makeDD/makeDDByName dispatchers that fall back to them -- is excluded from
1097// the tdkc build. The registry is therefore used unconditionally here.
1098// ---------------------------------------------------------------------------
1099#ifndef TDKC
1100
1101// Parse a Panini (KCBox) DD output file into a d-DNNF: this is the
1102// `panini-dd` output parser, selected by compilation() for the panini-*
1103// records (which run the generic compile path -- write a Tseytin CNF, run the
1104// record's argtpl -- and differ only in this parse-back). Panini emits its
1105// own DD format (sequential node ids; "F"/"T" terminals; "C"/"D" decomposable
1106// conjunctions; decision nodes), not the c2d/d4 NNF the `nnf` parser reads.
1107// R2-D2 and CCDD emit "K" (kernelize) nodes that break decomposability, so
1108// ProvSQL does not register the variants that produce them.
1109dDNNF BooleanCircuit::parsePaniniDD(const std::string &outfilename) const {
1110 std::ifstream ifs(outfilename.c_str());
1111 if (!ifs)
1112 throw CircuitException("Cannot open Panini output: " + outfilename);
1113
1114 // Skip Panini's preamble ("Variable order: ...", "Maximum variable: ...",
1115 // "Number of nodes: ...") and stop at the first data line, which always
1116 // starts with "0:".
1117 std::string line;
1118 bool found_data = false;
1119 while (std::getline(ifs, line)) {
1120 if (line.rfind("0:", 0) == 0) { found_data = true; break; }
1121 }
1122 if (!found_data)
1123 throw CircuitException("Panini output: no data lines found");
1124
1125 dDNNF dnnf;
1126 // Panini node ids are sequential 0, 1, 2, ... Highest id is the
1127 // root of the compilation.
1128 std::vector<gate_t> id_to_gate;
1129
1130 do {
1131 if (line.empty()) continue;
1132 auto colon_pos = line.find(':');
1133 if (colon_pos == std::string::npos) continue;
1134
1135 // Sanity-check the leading id matches the size of id_to_gate so far
1136 // (the file should be in monotonically increasing id order).
1137 int panini_id = std::stoi(line.substr(0, colon_pos));
1138 if (static_cast<size_t>(panini_id) != id_to_gate.size())
1139 throw CircuitException(
1140 "Panini output: out-of-order node id "
1141 + std::to_string(panini_id));
1142
1143 std::stringstream ss(line.substr(colon_pos + 1));
1144 std::string first;
1145 ss >> first;
1146
1147 gate_t this_gate;
1148 if (first == "F") {
1149 // FALSE terminal: empty OR.
1150 this_gate = dnnf.setGate(BooleanGate::OR);
1151 } else if (first == "T") {
1152 // TRUE terminal: empty AND.
1153 this_gate = dnnf.setGate(BooleanGate::AND);
1154 } else if (first == "C" || first == "D") {
1155 // C (CONJOIN), D (DECOMPOSE) are decomposable conjunctions in
1156 // Panini's CDD format; OR is only ever expressed implicitly by
1157 // the (v ? t : f) decision nodes. K (KERNELIZE) nodes encode
1158 // literal-equivalence constraints over a shared kernel
1159 // variable and break decomposability; we refuse the only two
1160 // target languages that emit them (R2-D2 and CCDD) upstream,
1161 // so seeing K here is an upstream-Panini surprise.
1162 this_gate = dnnf.setGate(BooleanGate::AND);
1163 int child;
1164 while (ss >> child) {
1165 if (child == 0) break;
1166 if (child < 0 || static_cast<size_t>(child) >= id_to_gate.size())
1167 throw CircuitException(
1168 "Panini output: forward / invalid child reference "
1169 + std::to_string(child));
1170 dnnf.addWire(this_gate, id_to_gate[child]);
1171 }
1172 } else if (first == "K") {
1173 throw CircuitException(
1174 "Panini output: unexpected K (kernelize) node; ProvSQL "
1175 "does not support Panini target languages that emit K "
1176 "nodes (R2-D2, CCDD).");
1177 } else {
1178 // Decision node: <var> <false_child> <true_child> [0]
1179 // (Panini's CDD::Display emits children in ch[0]/ch[1] order;
1180 // CDD.cpp's DOT writer maps ch[0] to the dotted/false edge and
1181 // ch[1] to the solid/true edge.)
1182 int var = std::stoi(first);
1183 int f_child, t_child;
1184 if (!(ss >> f_child >> t_child))
1185 throw CircuitException(
1186 "Panini output: malformed decision line at id "
1187 + std::to_string(panini_id));
1188 if (t_child < 0 || f_child < 0
1189 || static_cast<size_t>(t_child) >= id_to_gate.size()
1190 || static_cast<size_t>(f_child) >= id_to_gate.size())
1191 throw CircuitException(
1192 "Panini output: forward / invalid decision child at id "
1193 + std::to_string(panini_id));
1194 gate_t t_gate = id_to_gate[t_child];
1195 gate_t f_gate = id_to_gate[f_child];
1196
1197 // Translate the decision. Two cases:
1198 // (a) v is an input gate: keep the literal in the structure,
1199 // OR(AND(v, t'), AND(NOT(v), f')).
1200 // (b) v is a Tseytin auxiliary: aux vars are functionally
1201 // determined by inputs, so under WMC we want literal
1202 // weights w(v) = w(NOT v) = 1 (not (p, 1-p)). With those
1203 // weights the AND wrappers contribute 1 to either branch
1204 // and we can drop them entirely, emitting just
1205 // OR(t', f'). The OR is not determinism-preserving on
1206 // the variable v, but the input-projection of its two
1207 // arms is still disjoint by Tseytin determinism so
1208 // @c dDNNF::probabilityEvaluation() still returns the
1209 // correct weighted model count.
1210 size_t var_idx = static_cast<size_t>(var) - 1;
1211 if (var_idx < gates.size() && gates[var_idx] == BooleanGate::IN) {
1212 gate_t pos_lit = dnnf.setGate(
1213 getUUID(static_cast<gate_t>(var_idx)),
1214 BooleanGate::IN, prob[var_idx]);
1215 gate_t neg_lit = dnnf.setGate(BooleanGate::NOT);
1216 dnnf.addWire(neg_lit, pos_lit);
1217 gate_t and_t = dnnf.setGate(BooleanGate::AND);
1218 dnnf.addWire(and_t, pos_lit);
1219 dnnf.addWire(and_t, t_gate);
1220 gate_t and_f = dnnf.setGate(BooleanGate::AND);
1221 dnnf.addWire(and_f, neg_lit);
1222 dnnf.addWire(and_f, f_gate);
1223 this_gate = dnnf.setGate(BooleanGate::OR);
1224 dnnf.addWire(this_gate, and_t);
1225 dnnf.addWire(this_gate, and_f);
1226 } else {
1227 this_gate = dnnf.setGate(BooleanGate::OR);
1228 dnnf.addWire(this_gate, t_gate);
1229 dnnf.addWire(this_gate, f_gate);
1230 }
1231 }
1232 id_to_gate.push_back(this_gate);
1233 } while (std::getline(ifs, line));
1234
1235 ifs.close();
1236
1237 if (id_to_gate.empty())
1238 throw CircuitException("Panini output produced no nodes");
1239
1240 // The root of a Panini DD is the highest-id node.
1241 dnnf.setRoot(id_to_gate.back());
1242
1243 dnnf.simplify();
1244 return dnnf;
1245}
1246
1247// Preference-ranked tool selection for @p operation: honour the explicitly
1248// @p preferred tool when it is enabled, advertises the operation, and is
1249// available; otherwise return the highest-preference enabled tool advertising
1250// the operation whose binary and dependencies resolve on PATH. Returns "" if
1251// none is available, so a dispatcher can fall back or raise a clear error.
1252// This replaces the old "if d4 else c2d ..." chains: an admin reorders or
1253// disables tools (or bumps provsql.fallback_compiler, honoured via @p
1254// preferred) and selection follows.
1255static std::string selectTool(const std::string &operation,
1256 const std::string &preferred = "") {
1257 if(!preferred.empty()) {
1258 const provsql::ToolRecord *r = provsql::tool_registry().find(preferred);
1259 if(r != nullptr && r->enabled && r->hasOperation(operation)
1260 && toolAvailable(*r))
1261 return preferred;
1262 }
1263 for(const provsql::ToolRecord *r : provsql::tool_registry().byOperation(operation))
1264 if(toolAvailable(*r))
1265 return r->name;
1266 return "";
1267}
1268
1269// The compiler for makeDD's last-resort fallback route: prefer
1270// provsql.fallback_compiler (default "d4") when available, otherwise the
1271// highest-preference compiler whose binary resolves on PATH. Falls back to
1272// the configured name when nothing is available, so compilation() raises its
1273// actionable error. (The GUC governs only this fallback route; an explicit
1274// no-argument compilation() request just takes the best available compiler --
1275// symmetric with the no-tool wmc path.)
1276static std::string chooseCompiler() {
1277 const char *fb = (provsql_fallback_compiler != NULL
1278 && provsql_fallback_compiler[0] != '\0')
1280 std::string chosen = selectTool("compile", fb);
1281 return chosen.empty() ? std::string(fb) : chosen;
1282}
1283
1284std::string BooleanCircuit::checkCompiler(std::string compiler) {
1285 // No compiler named: pick the highest-preference available one (symmetric
1286 // with the no-tool wmc path). provsql.fallback_compiler is deliberately
1287 // not consulted here -- it governs only makeDD's last-resort fallback route.
1288 if(compiler.empty()) {
1289 compiler = selectTool("compile");
1290 if(compiler.empty())
1291 throw CircuitException(
1292 "no knowledge compiler is available; install one (d4, d4v2, "
1293 "c2d, minic2d, dsharp) or add its directory to "
1294 "provsql.tool_search_path");
1295 }
1296
1297 // Validate the compiler against the registry before any temp-dir or CNF
1298 // work. A name that is not a registered, enabled 'compile' tool is
1299 // rejected here. compilation() implements two output parsers: the tolerant
1300 // `nnf` reader (both the d4-family header-less NNF and the c2d-style header
1301 // form) and the `panini-dd` reader (Panini's own DD format); a compile tool
1302 // advertising any other parser is something we cannot read back, so reject
1303 // it rather than mis-parse.
1304 const provsql::ToolRecord *rec = provsql::tool_registry().find(compiler);
1305 if(rec == nullptr || !rec->hasOperation("compile"))
1306 throw CircuitException("Unknown compiler '"+compiler+"'");
1307 if(!rec->enabled)
1308 throw CircuitException(
1309 "Compiler '"+compiler+"' is disabled in the tool registry");
1310 if(rec->parser != "nnf" && rec->parser != "panini-dd")
1311 throw CircuitException(
1312 "Compiler '"+compiler+"' uses output parser '"+rec->parser
1313 +"', which compilation() does not implement");
1314 return compiler;
1315}
1316
1318 std::string *resolved) const {
1319 compiler = checkCompiler(compiler);
1320 const provsql::ToolRecord *rec = provsql::tool_registry().find(compiler);
1321 const std::string compiler_binary = rec->binary;
1322 if(resolved)
1323 *resolved = compiler; // the validated tool actually used (CLI or KCMCP)
1324
1325 // KCMCP backend: compile over a warm socket server instead of spawning a
1326 // CLI tool. The problem is sent as a native BC-S1.2 circuit when the record
1327 // advertises that input, else as a Tseytin CNF; the RESULT's d-DNNF text is
1328 // parsed by the same parseDDNNF() the CLI path uses. Any failure (connect,
1329 // protocol, server ERROR) raises, so makeDD's fallback can try another tool.
1330 if(rec->kind == "kcmcp") {
1331 std::vector<gate_t> inputOrder;
1332 std::string content;
1333 uint8_t input_format = 0; // dimacs-cnf
1334 if(rec->acceptsInput("circuit-bcs12")) {
1335 try {
1336 content = BCS12(g, inputOrder);
1337 input_format = 1; // circuit-bcs12
1338 } catch(const CircuitException &) {
1339 inputOrder.clear();
1340 content.clear();
1341 }
1342 }
1343 if(content.empty())
1344 content = TseytinCNF(g, false); // inputOrder stays empty => CNF mode
1345 // Resolve the server address: a literal 'managed' endpoint defers to the
1346 // live address the supervisor worker published in shared memory; anything
1347 // else is a fixed endpoint (unix:/path or host:port).
1348 std::string endpoint = rec->endpoint;
1349 if(endpoint == "managed")
1350 endpoint = provsql_kcmcp_managed_endpoint();
1351 if(endpoint.empty())
1352 throw CircuitException(
1353 "KCMCP tool '"+compiler+"' has no endpoint (managed server not "
1354 "running, or provsql.kcmcp_server unset)");
1355 try {
1356 std::string nnf = provsql::kcmcp_compile(endpoint, input_format, content);
1357 std::istringstream iss(nnf);
1358 return parseDDNNF(iss, inputOrder);
1359 } catch(const CircuitException &) {
1360 throw;
1361 } catch(const std::exception &e) {
1362 throw CircuitException(std::string("KCMCP compile via '")+compiler
1363 +"' failed: "+e.what());
1364 }
1365 }
1366
1367 // A compiler that advertises the BC-S1.2 circuit input (KCMCP
1368 // "circuit-bcs12") is driven with native circuit input: the Boolean circuit
1369 // is sent directly instead of a Tseytin CNF, skipping the CNF transform and
1370 // the aux-variable reconciliation in the parse-back. Requires a parser
1371 // that honours `I` declarations; on a gate shape BC-S1.2 cannot express, we
1372 // fall back to the Tseytin CNF path below. (Today only d4v2 advertises it.)
1373 bool circuit_input = rec->acceptsInput("circuit-bcs12")
1374 && !rec->argtpl_circuit.empty();
1375 if(find_external_tool(compiler_binary).empty())
1376 throw CircuitException(
1377 compiler_binary + " not found on PATH; install it or add its "
1378 "directory to provsql.tool_search_path");
1379
1380 ScopedTempDir tmp;
1381 std::string filename = tmp.file("input");
1382 std::string outfilename = tmp.file("input.nnf");
1383 // In circuit mode, inputOrder[v-1] is the IN gate for d4 variable v
1384 // (1-based); empty in CNF mode.
1385 std::vector<gate_t> inputOrder;
1386 std::string content;
1387 if(circuit_input) {
1388 try {
1389 content = BCS12(g, inputOrder);
1390 } catch(const CircuitException &) {
1391 // A gate shape BC-S1.2 cannot express: fall back to the CNF path.
1392 circuit_input = false;
1393 inputOrder.clear();
1394 }
1395 }
1396 if(!circuit_input)
1397 content = TseytinCNF(g, false);
1398 {
1399 std::ofstream ofs(filename);
1400 ofs << content;
1401 }
1402
1403 if(provsql_verbose>=30) {
1404 provsql_notice("Tseytin circuit in %s", filename.c_str());
1405 }
1406
1407 // The command line is the registry argtpl with {in}/{out} (and {binary})
1408 // substituted -- so a newly-registered compiler runs with its own
1409 // invocation, no per-name branch here. When the BC-S1.2 circuit input is
1410 // in use, the record's argtpl_circuit is used instead (it pairs with the
1411 // circuit input written above and the circuit-mode variable resolution in
1412 // the parse-back).
1413 std::string cmdline;
1414 if(circuit_input)
1416 compiler_binary, filename, outfilename);
1417 else
1418 cmdline = rec->buildCommand(filename, outfilename, compiler_binary);
1419
1420 int retvalue=run_external_tool(cmdline);
1421
1422 // run_external_tool runs the compiler in its own process group and
1423 // raises any pending cancel/terminate itself (after killing the child),
1424 // so a statement_timeout / pg_cancel_backend surfaces as 57014 here
1425 // rather than being masked by the "killed by signal" throw.
1426 //
1427 // (An older d4 CLI without `-dDNNF` is not handled as a compiled-in
1428 // special case: a deployment using it can register a tool with the
1429 // appropriate argtpl, e.g. register_tool('d4-old', argtpl => '{in} -out={out}', ...).)
1430 CHECK_FOR_INTERRUPTS();
1431
1432 if(retvalue)
1433 throw CircuitException(format_external_tool_status(retvalue, compiler));
1434
1435 // Read the result back with the parser the record advertises. Panini's DD
1436 // format has its own reader; everything else is the tolerant NNF parser.
1437 if(rec->parser == "panini-dd")
1438 return parsePaniniDD(outfilename);
1439
1440 std::ifstream ifs(outfilename.c_str());
1441 dDNNF dnnf = parseDDNNF(ifs, inputOrder);
1442 ifs.close();
1443
1444 if(provsql_verbose>=30) {
1445 tmp.keep();
1446 provsql_notice("Compiled d-DNNF in %s", outfilename.c_str());
1447 }
1448
1449 return dnnf;
1450}
1451
1452// Parse a c2d/d4 NNF stream into a dDNNF over this circuit's input gates.
1453// Shared by the CLI compilation() path and the KCMCP client; see the header.
1455 const std::vector<gate_t> &inputOrder) const {
1456 const bool circuit_input = !inputOrder.empty();
1457
1458 std::string line;
1459 getline(in,line);
1460
1461 // Tolerant NNF detection (the single `nnf` parser): the classic c2d/d4
1462 // form opens with an "nnf <nodes> <edges> <vars>" magic line and roots at
1463 // the last node; the d4-family form has no magic line and roots at gate
1464 // "1". A classic compiler emits the header iff satisfiable, so a missing
1465 // header on an empty file is an unsatisfiable formula; a missing header on
1466 // a non-empty file is the d4-family form. (The d4v2 native-circuit path
1467 // also produces the header-less d4 form.)
1468 bool new_d4;
1469 if(line.rfind("nnf", 0) != 0) {
1470 if(line.empty()) {
1471 // unsatisfiable formula (empty output)
1472 return dDNNF();
1473 }
1474 new_d4 = true;
1475 } else {
1476 new_d4 = false;
1477 std::string nnf;
1478 unsigned nb_nodes, nb_edges, nb_variables;
1479
1480 std::stringstream ss(line);
1481 ss >> nnf >> nb_nodes >> nb_edges >> nb_variables;
1482
1483 if(nb_variables!=gates.size())
1484 throw CircuitException("Unreadable d-DNNF (wrong number of variables: " + std::to_string(nb_variables) +" vs " + std::to_string(gates.size()) + ")");
1485
1486 getline(in,line);
1487 }
1488
1489 dDNNF dnnf;
1490
1491 // Map a d-DNNF literal's variable to the IN gate it stands for, if any.
1492 // CNF mode: variable = gate id + 1, real only for IN gates (every other
1493 // variable is a Tseytin auxiliary to skip). Circuit mode: variables 1..k
1494 // are the inputs in BCS12's declaration order, everything above k is an
1495 // internal-gate variable to skip.
1496 size_t k = inputOrder.size();
1497 auto resolveVar = [&](int v) -> std::pair<bool, gate_t> {
1498 unsigned idx = static_cast<unsigned>(abs(v));
1499 if(circuit_input) {
1500 if(idx>=1 && idx<=k)
1501 return {true, inputOrder[idx-1]};
1502 return {false, gate_t{}};
1503 }
1504 if(idx>=1 && (idx-1) < gates.size() && gates[idx-1]==BooleanGate::IN)
1505 return {true, static_cast<gate_t>(idx-1)};
1506 return {false, gate_t{}};
1507 };
1508
1509 unsigned i=0;
1510 do {
1511 std::stringstream ss(line);
1512
1513 std::string c;
1514 ss >> c;
1515
1516 if(c=="O") {
1517 int var, args;
1518 ss >> var >> args;
1519 auto id=dnnf.getGate(std::to_string(i));
1520 dnnf.setGate(std::to_string(i), BooleanGate::OR);
1521 int g;
1522 while(ss >> g) {
1523 auto id2=dnnf.getGate(std::to_string(g));
1524 dnnf.addWire(id,id2);
1525 }
1526 } else if(c=="A") {
1527 int args;
1528 ss >> args;
1529 auto id=dnnf.getGate(std::to_string(i));
1530 dnnf.setGate(std::to_string(i), BooleanGate::AND);
1531 int g;
1532 while(ss >> g) {
1533 auto id2=dnnf.getGate(std::to_string(g));
1534 dnnf.addWire(id,id2);
1535 }
1536 } else if(c=="L") {
1537 int leaf;
1538 ss >> leaf;
1539 auto and_gate=dnnf.setGate(std::to_string(i), BooleanGate::AND);
1540 auto [is_in, in_gate] = resolveVar(leaf);
1541 if(is_in) {
1542 auto pid = static_cast<std::underlying_type<gate_t>::type>(in_gate);
1543 auto leaf_gate = dnnf.setGate(getUUID(in_gate), BooleanGate::IN, prob[pid]);
1544 if(leaf<0) {
1545 auto not_gate = dnnf.setGate(BooleanGate::NOT);
1546 dnnf.addWire(not_gate, leaf_gate);
1547 dnnf.addWire(and_gate, not_gate);
1548 } else {
1549 dnnf.addWire(and_gate, leaf_gate);
1550 }
1551 } else {
1552 ; // Do nothing, TRUE gate
1553 }
1554 } else if(c=="f" || c=="o") {
1555 // d4 extended format
1556 // A FALSE gate is an OR gate without wires
1557 int var;
1558 ss >> var;
1559 dnnf.setGate(std::to_string(var), BooleanGate::OR);
1560 } else if(c=="t" || c=="a") {
1561 // d4 extended format
1562 // A TRUE gate is an AND gate without wires
1563 int var;
1564 ss >> var;
1565 dnnf.setGate(std::to_string(var), BooleanGate::AND);
1566 } else if(dnnf.hasGate(c)) {
1567 // d4 extended format
1568 int var;
1569 ss >> var;
1570 auto id2=dnnf.getGate(std::to_string(var));
1571
1572 std::vector<int> decisions;
1573 int decision;
1574 while(ss >> decision) {
1575 if(decision==0)
1576 break;
1577 // Edges carry decision literals over both real inputs and internal
1578 // variables (Tseytin auxiliaries in CNF mode, gate variables in
1579 // circuit mode). Keep only the input literals; the rest are
1580 // functionally determined and projected out (sound for probability).
1581 if(resolveVar(decision).first)
1582 decisions.push_back(decision);
1583 }
1584
1585 if(decisions.empty()) {
1586 dnnf.addWire(dnnf.getGate(c), id2);
1587 } else {
1588 auto and_gate = dnnf.setGate(BooleanGate::AND);
1589 dnnf.addWire(dnnf.getGate(c), and_gate);
1590 dnnf.addWire(and_gate, id2);
1591 for(auto leaf : decisions) {
1592 auto in_gate = resolveVar(leaf).second;
1593 auto pid = static_cast<std::underlying_type<gate_t>::type>(in_gate);
1594 auto leaf_gate = dnnf.setGate(getUUID(in_gate), BooleanGate::IN, prob[pid]);
1595 if(leaf<0) {
1596 auto not_gate = dnnf.setGate(BooleanGate::NOT);
1597 dnnf.addWire(not_gate, leaf_gate);
1598 dnnf.addWire(and_gate, not_gate);
1599 } else {
1600 dnnf.addWire(and_gate, leaf_gate);
1601 }
1602 }
1603 }
1604 } else
1605 throw CircuitException(std::string("Unreadable d-DNNF (unknown node type: ")+c+")");
1606
1607 ++i;
1608 } while(getline(in, line));
1609
1610 dnnf.setRoot(dnnf.getGate(new_d4?"1":std::to_string(i-1)));
1611
1612 // External NNF writers (c2d, minic2d, dsharp) leave TRUE constants
1613 // (empty AND gates) and FALSE constants (empty OR gates) embedded in
1614 // the structure, because their target formats (Decision-DNNF, SDD)
1615 // require every variable to be "covered" even when its value is
1616 // forced by the CNF. Run the standard peephole so the d-DNNF returned
1617 // to callers is in canonical form, matching the tree-decomposition
1618 // builder which already simplifies.
1619 dnnf.simplify();
1620
1621 return dnnf;
1622}
1623
1624// Generic weighted-model-counting runner. Selects the counter from the
1625// registry by logical name, checks its binary and dependencies resolve,
1626// writes the weighted CNF in the convention its `parser` implies, runs the
1627// record's argtpl and reads the count back the same way -- so the four
1628// per-counter methods (ganak, sharpsat-td, dpmc, weightmc) share one
1629// runner, and a wmc tool speaking a known convention is registrable without
1630// code. The two conventions, keyed by `parser`:
1631// wmc-line MCC-2024 weighted DIMACS in ("c t wmc" + "c p weight" lines);
1632// the count on a "c s exact" / "s wmc" line out.
1633// weightmc weightmc's own weighted DIMACS in; a "mantissa x 2^exp" out.
1634double BooleanCircuit::wmcCount(gate_t g, const std::string &requested,
1635 const std::string &opt) const {
1636 // An empty tool name means "pick the best available counter" (highest
1637 // preference whose binary + dependencies resolve on PATH).
1638 std::string tool = requested;
1639 if(tool.empty()) {
1640 tool = selectTool("wmc");
1641 if(tool.empty())
1642 throw CircuitException(
1643 "no weighted model counter is available; install one (ganak, "
1644 "sharpsat-td, dpmc, weightmc) or add its directory to "
1645 "provsql.tool_search_path");
1646 }
1647
1648 const provsql::ToolRecord *rec = provsql::tool_registry().find(tool);
1649 if(rec == nullptr || !rec->hasOperation("wmc"))
1650 throw CircuitException("Unknown wmc tool '" + tool + "'");
1651 if(!rec->enabled)
1652 throw CircuitException("Tool '" + tool + "' is disabled in the tool registry");
1653
1654 // The binary (when the tool has one of its own) and every dependency must
1655 // resolve on PATH. dpmc has no binary of its own -- it is the htb | dmc
1656 // pipeline named entirely in its template -- so its components are its
1657 // dependencies.
1658 if(!rec->binary.empty() && find_external_tool(rec->binary).empty())
1659 throw CircuitException(
1660 rec->binary + " not found on PATH; install it or add its "
1661 "directory to provsql.tool_search_path");
1662 for(const std::string &dep : rec->dependencies)
1663 if(find_external_tool(dep).empty())
1664 throw CircuitException(
1665 tool + " needs '" + dep + "' on PATH; install it or add its "
1666 "directory to provsql.tool_search_path");
1667
1668 const bool weightmc_io = (rec->parser == "weightmc");
1669
1670 ScopedTempDir tmp;
1671 const std::string &dirname = tmp.path();
1672 std::string filename = tmp.file("input");
1673 std::string outfilename = tmp.file("input.out");
1674 {
1675 std::ofstream ofs(filename);
1676 if(weightmc_io) {
1677 // weightmc reads weights inline, in its own weighted-DIMACS dialect.
1678 ofs << TseytinCNF(g, true);
1679 } else {
1680 // MCC 2024 weighted DIMACS: a plain CNF plus per-input weight lines.
1681 ofs << "c t wmc\n";
1682 ofs << TseytinCNF(g, false);
1683 for(gate_t in : inputs) {
1684 int id = static_cast<int>(in) + 1;
1685 ofs << "c p weight " << id << ' ' << getProb(in) << " 0\n";
1686 ofs << "c p weight -" << id << ' ' << (1.0 - getProb(in)) << " 0\n";
1687 }
1688 }
1689 }
1690
1691 // {tmpdir} (sharpsat-td's flowcutter scratch) and {pivotAC} (weightmc's
1692 // approximation tolerance, from opt='delta;epsilon') are offered as
1693 // template placeholders; a tool that does not reference one ignores it.
1694 double epsilon = 0.8;
1695 {
1696 std::stringstream ssopt(opt);
1697 std::string delta_s, epsilon_s;
1698 getline(ssopt, delta_s, ';');
1699 getline(ssopt, epsilon_s, ';');
1700 try { double e = stod(epsilon_s); if(e != 0) epsilon = e; }
1701 catch(const std::exception &) {}
1702 }
1703 const double pivotAC = 2*ceil(exp(3./2)*(1+1/epsilon)*(1+1/epsilon));
1704
1705 std::string cmdline = rec->buildCommand(
1706 filename, outfilename, rec->binary,
1707 {{"tmpdir", dirname}, {"pivotAC", std::to_string(pivotAC)}});
1708
1709 int retvalue = run_external_tool(cmdline);
1710 CHECK_FOR_INTERRUPTS();
1711 if(retvalue)
1712 throw CircuitException(format_external_tool_status(retvalue, tool));
1713
1714 std::ifstream ifs(outfilename.c_str());
1715 double ret;
1716 if(weightmc_io) {
1717 // weightmc prints the count as "<mantissa> x 2^<exp>" on its last line.
1718 std::string line, prev_line;
1719 while(getline(ifs, line)) prev_line = line;
1720 std::stringstream ss(prev_line);
1721 std::string result;
1722 ss >> result >> result >> result >> result >> result;
1723 std::istringstream iss(result);
1724 std::string val, exp;
1725 getline(iss, val, 'x');
1726 getline(iss, exp);
1727 if(exp.size() < 2)
1728 throw CircuitException("weightmc: could not parse '" + prev_line + "'");
1729 double value = stod(val);
1730 double exponent = stod(exp.substr(2));
1731 ret = value * pow(2.0, exponent);
1732 } else {
1733 // The count is on the last "c s exact ..." (or "s wmc ...") line;
1734 // parse_wmc_value tolerates the per-tool token layout on that line.
1735 std::string line, matched;
1736 while(getline(ifs, line))
1737 if(line.rfind("c s exact", 0) == 0 || line.rfind("s wmc", 0) == 0)
1738 matched = line;
1739 if(matched.empty())
1740 throw CircuitException(tool + ": could not find a count line in output");
1741 ret = parse_wmc_value(matched, tool.c_str());
1742 }
1743
1744 if(provsql_verbose >= 30)
1745 tmp.keep();
1746 return ret;
1747}
1748
1749#endif // external-tool compilation / counting (excluded from tdkc)
1750
1752 gate_t g, std::set<gate_t> &seen,
1753 std::unordered_map<gate_t, double> &memo) const
1754{
1755 check_stack_depth(); // recurses on wires; guard deep circuits (see GenericCircuit::evaluate)
1756 // Memoised gates are variable-free (constant-only) -- returning the cached
1757 // value is sound (it touched nothing in `seen`) and avoids re-traversing a
1758 // shared constant subgraph. A variable-bearing gate is never cached, so a
1759 // second visit re-enters its subtree and throws on the repeated variable.
1760 {
1761 auto it = memo.find(g);
1762 if(it != memo.end())
1763 return it->second;
1764 }
1765
1766 // A certified gate (see DNNF_CERT_INFO) opens a maximal island, walked
1767 // iteratively (certified circuits can be as deep as the data). A
1768 // certified gate reached a second time -- from another island or from
1769 // the uncertified region -- is re-walked: its variables then hit `seen`
1770 // and the evaluation throws, so entanglement across islands is
1771 // conservatively rejected, exactly like a read-once violation.
1772 if(isDNNFCertified(g))
1773 return evaluateCertifiedIsland(g, seen, memo);
1774
1775 const std::size_t seen_before = seen.size();
1776
1777 double result=1.;
1778
1779 switch(getGateType(g)) {
1780 case BooleanGate::AND:
1781 for(const auto &c: getWires(g)) {
1782 result*=independentEvaluationInternal(c, seen, memo);
1783 }
1784 break;
1785
1786 case BooleanGate::OR:
1787 {
1788 // We collect probability among each group of children, where we
1789 // group MULIN gates with the same key var together
1790 std::map<gate_t, double> groups;
1791 std::set<gate_t> local_mulins;
1792 std::set<std::pair<gate_t, unsigned> > mulin_seen;
1793
1794 for(const auto &c: getWires(g)) {
1795 auto group = c;
1797 group = *getWires(c).begin();
1798 if(local_mulins.find(group)==local_mulins.end()) {
1799 if(seen.find(group)!=seen.end())
1800 throw CircuitException("Not an independent circuit");
1801 else
1802 seen.insert(group);
1803 local_mulins.insert(group);
1804 }
1805 auto p = std::make_pair(group, getInfo(c));
1806 if(mulin_seen.find(p)==mulin_seen.end()) {
1807 groups[group] += getProb(c);
1808 mulin_seen.insert(p);
1809 }
1810 } else
1811 groups[group] = independentEvaluationInternal(c, seen, memo);
1812 }
1813
1814 for(const auto [k, v]: groups)
1815 result *= 1-v;
1816 result = 1-result;
1817 }
1818 break;
1819
1820 case BooleanGate::NOT:
1821 result=1-independentEvaluationInternal(*getWires(g).begin(), seen, memo);
1822 break;
1823
1824 case BooleanGate::IN:
1825 {
1826 /* A leaf with probability 0 or 1 is a constant : it carries no
1827 * Boolean variable that can collide with another occurrence of
1828 * itself. Skip the seen-set bookkeeping so circuits where the
1829 * shared subgraphs are all constants (e.g. RangeCheck-resolved
1830 * comparators flowing through a non-tree structure, or
1831 * user-flipped Bernoullis pinned to 0 / 1) stay evaluable under
1832 * the read-once `independent` method. Anything strictly between
1833 * 0 and 1 is a real Bernoulli variable and must remain
1834 * read-once. */
1835 const double p = getProb(g);
1836 if (p == 0.0 || p == 1.0) {
1837 result = p;
1838 break;
1839 }
1840 if(seen.find(g)!=seen.end())
1841 throw CircuitException("Not an independent circuit");
1842 seen.insert(g);
1843 result=p;
1844 }
1845 break;
1846
1847 case BooleanGate::MULIN:
1848 {
1849 auto child = *getWires(g).begin();
1850 if(seen.find(child)!=seen.end())
1851 throw CircuitException("Not an independent circuit");
1852 seen.insert(child);
1853 result=getProb(g);
1854 }
1855 break;
1856
1859 throw CircuitException("Bad gate");
1860 }
1861
1862 // Cache only if this gate consumed no variable (constant-only subgraph).
1863 if(seen.size() == seen_before)
1864 memo[g] = result;
1865 return result;
1866}
1867
1869 gate_t root, std::set<gate_t> &seen,
1870 std::unordered_map<gate_t, double> &memo) const
1871{
1872 const std::size_t seen_before = seen.size();
1873 // Island-local values: within the island every gate is computed once
1874 // (sharing is licensed by the certificate), and the explicit post-order
1875 // stack keeps the walk safe on circuits as deep as the data.
1876 std::unordered_map<gate_t, double> val;
1877 // Key variables of MULIN gates already registered within this island: a
1878 // BID block's alternatives share their key variable by design (they are
1879 // mutually exclusive outcomes appearing under deterministic ORs), so
1880 // only the first registers globally.
1881 std::unordered_set<gate_t> island_mulvars;
1882 std::vector<gate_t> stack{root};
1883
1884 while(!stack.empty()) {
1885 const gate_t g = stack.back();
1886 if(val.find(g) != val.end()) {
1887 stack.pop_back();
1888 continue;
1889 }
1890
1891 const auto t = getGateType(g);
1892
1893 if(t == BooleanGate::IN) {
1894 // Same constant-leaf exemption as the read-once walk: a 0/1 leaf
1895 // carries no Boolean variable.
1896 const double p = getProb(g);
1897 if(p != 0.0 && p != 1.0) {
1898 if(seen.find(g) != seen.end())
1899 throw CircuitException("Not an independent circuit");
1900 seen.insert(g);
1901 }
1902 val[g] = p;
1903 stack.pop_back();
1904 continue;
1905 }
1906 if(t == BooleanGate::MULIN) {
1907 auto child = *getWires(g).begin();
1908 if(island_mulvars.insert(child).second) {
1909 if(seen.find(child) != seen.end())
1910 throw CircuitException("Not an independent circuit");
1911 seen.insert(child);
1912 }
1913 val[g] = getProb(g);
1914 stack.pop_back();
1915 continue;
1916 }
1917 if(t != BooleanGate::NOT && !isDNNFCertified(g)) {
1918 // Uncertified gate inside the island: standard read-once rules (its
1919 // own certified descendants open fresh sub-islands).
1920 val[g] = independentEvaluationInternal(g, seen, memo);
1921 stack.pop_back();
1922 continue;
1923 }
1924
1925 bool ready = true;
1926 for(const auto &c: getWires(g))
1927 if(val.find(c) == val.end()) {
1928 stack.push_back(c);
1929 ready = false;
1930 }
1931 if(!ready)
1932 continue;
1933
1934 double result;
1935 if(t == BooleanGate::NOT)
1936 result = 1 - val[getWires(g)[0]];
1937 else if(t == BooleanGate::AND) {
1938 // Certified decomposable AND: product.
1939 result = 1.;
1940 for(const auto &c: getWires(g))
1941 result *= val[c];
1942 } else {
1943 // Certified deterministic OR: plain sum (mutual exclusivity).
1944 result = 0.;
1945 for(const auto &c: getWires(g))
1946 result += val[c];
1947 }
1948 val[g] = result;
1949 stack.pop_back();
1950 }
1951
1952 // Same global-memo rule as the recursive walk: cache only when the
1953 // island consumed no variable.
1954 if(seen.size() == seen_before)
1955 memo[root] = val[root];
1956 return val[root];
1957}
1958
1960{
1961 std::set<gate_t> seen;
1962 std::unordered_map<gate_t, double> memo;
1963 return independentEvaluationInternal(g, seen, memo);
1964}
1965
1966void BooleanCircuit::setInfo(gate_t g, unsigned int i)
1967{
1968 info[g] = i;
1969}
1970
1972{
1973 auto it = info.find(g);
1974
1975 if(it==info.end())
1976 return 0;
1977 else
1978 return it->second;
1979}
1980
1982 const std::vector<gate_t> &muls,
1983 const std::vector<double> &cumulated_probs,
1984 unsigned start,
1985 unsigned end,
1986 std::vector<gate_t> &prefix)
1987{
1988 if(start==end) {
1989 getWires(muls[start]) = prefix;
1990 return;
1991 }
1992
1993 unsigned mid = (start+end)/2;
1994 // cumulated_probs is an *inclusive* prefix sum (cumulated_probs[i] =
1995 // p[0]+...+p[i]). The conditional probability of being in the left
1996 // half [start..mid] given the range [start..end] is therefore
1997 // (cum[mid] - cum[start-1]) / (cum[end] - cum[start-1])
1998 // with cum[-1] treated as 0 when start==0.
1999 double prev_start = (start == 0) ? 0. : cumulated_probs[start - 1];
2000 auto g = setGate(
2002 (cumulated_probs[mid] - prev_start) /
2003 (cumulated_probs[end] - prev_start));
2004 auto not_g = setGate(BooleanGate::NOT);
2005 getWires(not_g).push_back(g);
2006
2007 prefix.push_back(g);
2008 rewriteMultivaluedGatesRec(muls, cumulated_probs, start, mid, prefix);
2009 prefix.pop_back();
2010 prefix.push_back(not_g);
2011 rewriteMultivaluedGatesRec(muls, cumulated_probs, mid+1, end, prefix);
2012 prefix.pop_back();
2013}
2014
2015/**
2016 * @brief Check whether two double values are approximately equal.
2017 * @param a First value.
2018 * @param b Second value.
2019 * @return @c true if @p a and @p b differ by less than 10× machine epsilon.
2020 */
2021static constexpr bool almost_equals(double a, double b)
2022{
2023 double diff = a - b;
2024 constexpr double epsilon = std::numeric_limits<double>::epsilon() * 10;
2025
2026 return (diff < epsilon && diff > -epsilon);
2027}
2028
2030{
2031 std::map<gate_t,std::vector<gate_t> > var2mulinput;
2032 for(auto mul: mulinputs) {
2033 var2mulinput[*getWires(mul).begin()].push_back(mul);
2034 }
2035 mulinputs.clear();
2036
2037 for(const auto &[var, muls]: var2mulinput)
2038 {
2039 const unsigned n = muls.size();
2040 std::vector<double> cumulated_probs(n);
2041 double cumulated_prob=0.;
2042
2043 for(unsigned i=0; i<n; ++i) {
2044 cumulated_prob += getProb(muls[i]);
2045 cumulated_probs[i] = cumulated_prob;
2046 gates[static_cast<std::underlying_type<gate_t>::type>(muls[i])] = BooleanGate::AND;
2047 getWires(muls[i]).clear();
2048 }
2049
2050 std::vector<gate_t> prefix;
2051 prefix.reserve(static_cast<unsigned>(log(n)/log(2)+2));
2052 if(!almost_equals(cumulated_probs[n-1],1.)) {
2053 prefix.push_back(setGate(BooleanGate::IN, cumulated_probs[n-1]));
2054 }
2055 rewriteMultivaluedGatesRec(muls, cumulated_probs, 0, n-1, prefix);
2056 }
2057}
2058
2059gate_t BooleanCircuit::interpretAsDDInternal(gate_t g, std::set<gate_t> &seen, dDNNF &dd) const {
2060 check_stack_depth(); // recurses on wires; guard deep circuits (see GenericCircuit::evaluate)
2061
2062 // A certified gate (see DNNF_CERT_INFO) opens a maximal island, copied
2063 // iteratively with native deterministic ORs; the recursion only walks
2064 // the uncertified region.
2065 if(isDNNFCertified(g))
2066 return interpretCertifiedIsland(g, seen, dd);
2067
2068 gate_t dg{0};
2069
2070 switch(getGateType(g)) {
2071 case BooleanGate::AND:
2072 {
2073 dg = dd.setGate(BooleanGate::AND);
2074 for(const auto &c: getWires(g)) {
2075 auto dc = interpretAsDDInternal(c, seen, dd);
2076 dd.addWire(dg, dc);
2077 }
2078 }
2079 break;
2080
2081 case BooleanGate::OR:
2082 {
2083 dg = dd.setGate(BooleanGate::NOT);
2084 auto dng = dd.setGate(BooleanGate::AND);
2085 dd.addWire(dg, dng);
2086 for(const auto &c: getWires(g)) {
2087 auto dc = interpretAsDDInternal(c, seen, dd);
2088 auto dnc = dd.setGate(BooleanGate::NOT);
2089 dd.addWire(dnc, dc);
2090 dd.addWire(dng, dnc);
2091 }
2092 }
2093 break;
2094
2095 case BooleanGate::NOT:
2096 {
2097 dg = dd.setGate(BooleanGate::NOT);
2098 auto dc = interpretAsDDInternal(getWires(g)[0], seen, dd);
2099 dd.addWire(dg, dc);
2100 }
2101 break;
2102
2103 case BooleanGate::IN:
2104 if(seen.find(g)!=seen.end())
2105 throw CircuitException("Not an independent circuit");
2106 seen.insert(g);
2107 if(getUUID(g).empty())
2108 dg = dd.setGate(BooleanGate::IN, getProb(g));
2109 else
2110 dg = dd.setGate(getUUID(g), BooleanGate::IN, getProb(g));
2111 break;
2112
2113 case BooleanGate::MULIN:
2116 throw CircuitException("Unsupported gate in interpretAsDD");
2117 }
2118
2119 return dg;
2120}
2121
2123 std::set<gate_t> &seen,
2124 dDNNF &dd) const
2125{
2126 // Same iterative island walk as evaluateCertifiedIsland, building dd
2127 // gates instead of probabilities; shared sub-circuits map to shared dd
2128 // gates, and the copied gates keep their certificate so the produced
2129 // artefact remains self-describing.
2130 std::unordered_map<gate_t, gate_t> val;
2131 std::vector<gate_t> stack{root};
2132
2133 while(!stack.empty()) {
2134 const gate_t g = stack.back();
2135 if(val.find(g) != val.end()) {
2136 stack.pop_back();
2137 continue;
2138 }
2139
2140 const auto t = getGateType(g);
2141
2142 if(t == BooleanGate::IN) {
2143 if(seen.find(g) != seen.end())
2144 throw CircuitException("Not an independent circuit");
2145 seen.insert(g);
2146 val[g] = getUUID(g).empty()
2148 : dd.setGate(getUUID(g), BooleanGate::IN, getProb(g));
2149 stack.pop_back();
2150 continue;
2151 }
2152 if(t != BooleanGate::NOT && !isDNNFCertified(g)) {
2153 // Uncertified gate inside the island: standard rules (its own
2154 // certified descendants open fresh sub-islands).
2155 val[g] = interpretAsDDInternal(g, seen, dd);
2156 stack.pop_back();
2157 continue;
2158 }
2159
2160 bool ready = true;
2161 for(const auto &c: getWires(g))
2162 if(val.find(c) == val.end()) {
2163 stack.push_back(c);
2164 ready = false;
2165 }
2166 if(!ready)
2167 continue;
2168
2169 gate_t dg;
2170 if(t == BooleanGate::NOT) {
2171 dg = dd.setGate(BooleanGate::NOT);
2172 dd.addWire(dg, val[getWires(g)[0]]);
2173 } else {
2174 dg = dd.setGate(t);
2175 dd.setInfo(dg, DNNF_CERT_INFO);
2176 for(const auto &c: getWires(g))
2177 dd.addWire(dg, val[c]);
2178 }
2179 val[g] = dg;
2180 stack.pop_back();
2181 }
2182
2183 return val[root];
2184}
2185
2187{
2188 dDNNF dd;
2189 std::set<gate_t> seen;
2190
2191 dd.setRoot(interpretAsDDInternal(g, seen, dd));
2192
2193 // The OR-as-NOT(AND(NOT, ...)) De Morgan rewriting above introduces
2194 // many redundant NOT-NOT pairs and single-child AND/OR gates that the
2195 // canonical simplify pass folds away; matches what the external-KC
2196 // and tree-decomposition paths already do.
2197 dd.simplify();
2198
2199 return dd;
2200}
2201
2202// makeDD / makeDDByName fall back to the external compilers, so they too are
2203// excluded from the external-tool-free tdkc build.
2204#ifndef TDKC
2205dDNNF BooleanCircuit::makeDD(gate_t g, const std::string &method, const std::string &args) const
2206{
2207 if(method=="compilation") {
2208 return compilation(g, args);
2209 } else if(method=="tree-decomposition") {
2210 try {
2211 TreeDecomposition td(*this);
2213 *this, g, td}.build();
2214 } catch(TreeDecompositionException &) {
2215 provsql_error("Treewidth greater than %u", TreeDecomposition::MAX_TREEWIDTH);
2216 }
2217 } else if(method=="interpret-as-dd") {
2218 return interpretAsDD(g);
2219 } else {
2220 dDNNF dd;
2221 try {
2222 dd = interpretAsDD(g);
2223 if(provsql_verbose>=20)
2224 provsql_notice("Circuit interpreted as dD, %ld gates", dd.getNbGates());
2225 } catch(CircuitException &) {
2226 try {
2227 TreeDecomposition td(*this);
2229 *this, g, td}.build();
2230 if(provsql_verbose>=25)
2231 provsql_notice("dD obtained by tree decomposition, %ld gates", dd.getNbGates());
2232 } catch(TreeDecompositionException &) {
2233 // Last-resort fallback: chooseCompiler() prefers
2234 // provsql.fallback_compiler when available, else the highest-
2235 // preference compiler on PATH.
2236 std::string chosen = chooseCompiler();
2237 dd = compilation(g, chosen);
2238 if(provsql_verbose>=20)
2239 provsql_notice("dD obtained by compilation using %s, %ld gates",
2240 chosen.c_str(), dd.getNbGates());
2241 }
2242 }
2243
2244 return dd;
2245 }
2246}
2247
2248dDNNF BooleanCircuit::makeDDByName(gate_t g, const std::string &name) const
2249{
2250 // In-process meta-routes are dispatched through makeDD: "default" runs the
2251 // whole fallback chain, "tree-decomposition" / "interpret-as-dd" the single
2252 // route. Everything else goes to compilation(); the empty string there
2253 // means "pick the highest-preference available compiler" (so a no-compiler
2254 // request uses the registry instead of a hardcoded d4).
2255 if(name=="default" || name=="tree-decomposition" || name=="interpret-as-dd")
2256 return makeDD(g, name=="default" ? std::string() : name, "");
2257 return compilation(g, name);
2258}
2259#endif // makeDD / makeDDByName (excluded from tdkc)
static constexpr const char * too_large_to_print
The error of toStringHelper past PG's limit for a text value.
static std::string selectTool(const std::string &operation, const std::string &preferred="")
static const size_t kSieveMaxClauses
Largest clause count for which the 2^m sieve enumeration is admitted.
static std::string chooseCompiler()
static constexpr bool almost_equals(double a, double b)
Check whether two double values are approximately equal.
Boolean provenance circuit with support for knowledge compilation.
constexpr unsigned DNNF_CERT_INFO
d-DNNF certificate value for the (gate-type-specific) per-gate info field.
BooleanGate
Gate types for a Boolean provenance circuit.
@ MULVAR
Auxiliary gate grouping all MULIN siblings.
@ NOT
Logical negation of a single child gate.
@ OR
Logical disjunction of child gates.
@ AND
Logical conjunction of child gates.
@ IN
Input (variable) gate representing a base tuple.
@ UNDETERMINED
Placeholder gate whose type has not been set yet.
@ MULIN
Multivalued-input gate (one of several options).
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
Out-of-line template method implementations for Circuit<gateType>.
In-memory catalog of the external tools ProvSQL can invoke.
Boolean circuit for provenance formula evaluation.
std::vector< double > prob
Per-gate probability (for IN gates).
bool evaluate(gate_t g, const std::unordered_set< gate_t > &sampled) const
Evaluate the sub-circuit at g on one sampled world.
dDNNF interpretAsDD(gate_t g) const
Build a dDNNF directly from the Boolean circuit's structure.
double independentEvaluationInternal(gate_t g, std::set< gate_t > &seen, std::unordered_map< gate_t, double > &memo) const
Recursive helper for independentEvaluation().
double sieve(const std::vector< gate_t > &clauses, const std::vector< std::set< gate_t > > &supports) const
Exact probability of a monotone DNF by inclusion-exclusion (sieve).
double possibleWorlds(gate_t g) const
Compute the probability by exact enumeration of all possible worlds.
std::vector< CNFInputMapping > tseytinVariableMapping() const
Map each input gate to its DIMACS variable, UUID, probability.
double karpLubyStopping(const std::vector< gate_t > &clauses, const std::vector< std::set< gate_t > > &supports, double eps, double delta, unsigned long max_samples, unsigned long &samples_used, bool &reached_target) const
Karp-Luby FPRAS with the self-adjusting stopping rule (adaptive sample count for a relative (eps,...
void setProb(gate_t g, double p)
Set the probability for gate g and mark the circuit as probabilistic.
dDNNF parseDDNNF(std::istream &in, const std::vector< gate_t > &inputOrder) const
Parse a c2d/d4 NNF stream into a dDNNF over this circuit's input gates.
std::set< gate_t > inputs
Set of IN (input) gate IDs.
bool isDNNFCertified(gate_t g) const
Is gate g certified by the d-DNNF per-gate marking?
void rewriteMultivaluedGatesRec(const std::vector< gate_t > &muls, const std::vector< double > &cumulated_probs, unsigned start, unsigned end, std::vector< gate_t > &prefix)
Recursive helper for rewriteMultivaluedGates().
double evaluateCertifiedIsland(gate_t root, std::set< gate_t > &seen, std::unordered_map< gate_t, double > &memo) const
Iteratively evaluate a certified d-DNNF island.
std::string exportCircuit(gate_t g) const
Export the circuit in the textual format expected by external compilers.
std::string BCS12(gate_t g, std::vector< gate_t > &inputOrder) const
Serialise the sub-circuit at g in d4's BC-S1.2 circuit format.
std::string TseytinCNF(gate_t g, bool display_prob, bool mapping=false) const
Return the Tseytin transformation of the sub-circuit at g as a DIMACS string.
dDNNF parsePaniniDD(const std::string &outfilename) const
Parse a Panini (KCBox) DD output file into a ProvSQL d-DNNF.
std::string toStringHelper(gate_t g, BooleanGate parent, const std::unordered_map< gate_t, std::string > *labels) const
Internal recursive helper for the two toString() variants.
double karpLuby(const std::vector< gate_t > &clauses, const std::vector< std::set< gate_t > > &supports, unsigned long samples) const
Karp-Luby FPRAS estimate of a DNF-shaped circuit's probability (fixed sample budget,...
dDNNF compilation(gate_t g, std::string compiler, std::string *resolved=nullptr) const
Compile the sub-circuit rooted at g to a dDNNF via an external tool.
dDNNF makeDD(gate_t g, const std::string &method, const std::string &args) const
Dispatch to the appropriate d-DNNF construction method.
gate_t setGate(BooleanGate type) override
Allocate a new gate with type type and no UUID.
unsigned getInfo(gate_t g) const
Return the integer annotation for gate g.
friend class dDNNFTreeDecompositionBuilder
double wmcCount(gate_t g, const std::string &tool, const std::string &opt) const
Weighted model counting through a registered external counter.
gate_t addGate() override
Allocate a new gate with a default-initialised type.
double monteCarlo(gate_t g, unsigned samples) const
Estimate the probability via Monte Carlo sampling.
void rewriteMultivaluedGates()
Rewrite all MULVAR/MULIN gate clusters into standard AND/OR/NOT circuits.
double getProb(gate_t g) const
Return the probability stored for gate g.
bool dnfShapeInfo(gate_t g, std::size_t &num_clauses) const
Cheap shape test: is the circuit DNF-shaped, and how many clauses?
void setInfo(gate_t g, unsigned info)
Store an integer annotation on gate g.
void dnfBounds(const std::vector< std::set< gate_t > > &clauses, double &lower, double &upper) const
Cheap certified probability interval [lower,upper] of a monotone DNF, without compiling it (Olteanu-H...
virtual std::string toString(gate_t g) const override
Return a textual description of gate g for debugging.
bool dnfShape(gate_t g, std::vector< gate_t > &clauses, std::vector< std::set< gate_t > > &supports) const
Detect the DNF shape the Karp-Luby FPRAS requires.
std::map< gate_t, unsigned > info
Per-gate integer info (for MULIN gates).
gate_t interpretCertifiedIsland(gate_t root, std::set< gate_t > &seen, dDNNF &dd) const
Iteratively copy a certified island into dd.
dDNNF makeDDByName(gate_t g, const std::string &name) const
Build a dDNNF from a single compiler/route name.
gate_t interpretAsDDInternal(gate_t g, std::set< gate_t > &seen, dDNNF &dd) const
Recursive helper for interpretAsDD().
double independentEvaluation(gate_t g) const
Compute the probability exactly when inputs are independent.
std::set< gate_t > mulinputs
Set of MULVAR gate IDs.
static std::string checkCompiler(std::string compiler)
Exception type thrown by circuit operations on invalid input.
Definition Circuit.h:382
std::vector< gate_t > & getWires(gate_t g)
Definition Circuit.h:311
BooleanGate getGateType(gate_t g) const
Definition Circuit.h:301
virtual gate_t setGate(const uuid &u, gateType type)
Create or update the gate associated with UUID u.
Definition Circuit.hpp:187
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::vector< BooleanGate > gates
Definition Circuit.h:215
uuid getUUID(gate_t g) const
Definition Circuit.hpp:65
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
Definition Circuit.hpp:50
bool hasGate(const uuid &u) const
Test whether a gate with UUID u exists.
Definition Circuit.hpp:30
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
Definition Circuit.h:252
virtual gate_t addGate()
Allocate a new gate with a default-initialised type.
Definition Circuit.hpp:168
Exception thrown when a tree decomposition cannot be constructed.
Tree decomposition of a Boolean circuit's primal graph.
static constexpr int MAX_TREEWIDTH
Maximum supported treewidth.
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
Definition dDNNF.h:71
void setRoot(gate_t g)
Set the root gate.
Definition dDNNF.h:127
void simplify()
Simplify the d-DNNF by removing redundant constants.
Definition dDNNF.cpp:600
RAII guard around a freshly mkdtemp'd /tmp directory.
std::string file(const std::string &basename)
Build a path under the temp dir and register it for cleanup.
const std::string & path() const
void keep()
Leave the directory on disk; cleanup is skipped at scope exit.
const ToolRecord * find(const std::string &name) const
Find a record by logical name, or nullptr if none is registered.
Constructs a d-DNNF from a Boolean circuit and its tree decomposition.
int run_external_tool(const std::string &cmdline)
Run a shell command line in its own process group, optionally extending PATH, interruptible by query ...
std::string format_external_tool_status(int rv, const std::string &tool)
Decode a system() return value into a human-readable message.
bool toolAvailable(const provsql::ToolRecord &rec)
True iff a registry tool can currently be used.
std::string find_external_tool(const std::string &name)
Locate an external tool by name.
Helpers for invoking external command-line tools.
In-extension KCMCP client: compile a Boolean problem on a warm, socket-attached knowledge compiler in...
const char * provsql_kcmcp_managed_endpoint(void)
Read the live endpoint of the managed KCMCP server from shared memory (e.g.
std::string kcmcp_compile(const std::string &endpoint, uint8_t input_format, const std::string &problem)
Compile problem on a KCMCP server and return its d-DNNF NNF text.
ToolRegistry & tool_registry()
Shorthand for ToolRegistry::instance().
std::string expandCommandTemplate(const std::string &tpl, const std::string &binary, const std::string &in, const std::string &out, const std::vector< std::pair< std::string, std::string > > &extra={})
Expand a command template into a runnable shell command line.
int provsql_verbose
Verbosity level; controlled by the provsql.verbose_level GUC.
Definition provsql.c:115
int provsql_monte_carlo_seed
Seed for the Monte Carlo sampler; -1 means non-deterministic (std::random_device); controlled by the ...
Definition provsql.c:125
bool provsql_interrupted
Set by provsql_sigint_handler: this backend received a cancel.
Definition provsql.c:111
char * provsql_fallback_compiler
Compiler used by BooleanCircuit::makeDD as the final fallback after interpretAsDD and tree-decomposit...
Definition provsql.c:123
Uniform error-reporting macros for ProvSQL.
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
#define provsql_notice(fmt,...)
Emit a ProvSQL informational notice (execution continues).
void provsql_check_result_size(size_t bytes, const char *message)
Throw if a text value of bytes is past what PostgreSQL can hold in a value (1 GB),...
Cancellation of the long C++ evaluation loops.
Core types, constants, and utilities shared across ProvSQL.
One registered external tool.
bool acceptsInput(const std::string &fmt) const
std::vector< std::string > dependencies
std::string argtpl_circuit
std::string kind
"cli" (spawn a binary) or "kcmcp" (talk to a socket server at endpoint).
std::string endpoint
KCMCP server address for kind "kcmcp": "unix:/path" or "host:port".
bool hasOperation(const std::string &op) const
std::string buildCommand(const std::string &in, const std::string &out, const std::string &binary_override, const std::vector< std::pair< std::string, std::string > > &extra={}) const
Build the command line for this tool.