17#include <unordered_set>
44#include <unordered_map>
74 std::unordered_map<gate_t, gate_t> redirect;
87 for (std::size_t i = 0; i < n; ++i) {
88 auto g =
static_cast<gate_t>(i);
93 std::vector<gate_t> kept;
94 kept.reserve(
wires.size());
96 if (gc.
getGateType(c) != identity) kept.push_back(c);
98 if (kept.size() !=
wires.size()) {
99 wires = std::move(kept);
120 std::unordered_map<gate_t, gate_t> subst;
121 for (std::size_t i = 0; i < n; ++i) {
122 auto g =
static_cast<gate_t>(i);
123 if (redirect.count(g))
continue;
128 bool absorbed =
false;
136 if (absorbed)
continue;
143 for (
auto &kv : subst) {
145 while (subst.count(cur) || redirect.count(cur))
146 cur = subst.count(cur) ? subst[cur] : redirect[cur];
155 if (!subst.empty()) {
156 for (std::size_t i = 0; i < n; ++i) {
159 auto it = subst.find(w);
160 if (it != subst.end()) {
166 for (
const auto &kv : subst) redirect[kv.first] = kv.second;
176 if (!redirect.empty()) {
177 for (
auto &kv : redirect) {
179 while (redirect.count(cur)) cur = redirect[cur];
182 for (
const auto &kv : redirect) {
183 gate_t g = kv.first, target = kv.second;
196 if (subst.empty())
return;
197 for (
auto &kv : subst) {
199 while (subst.count(cur)) cur = subst[cur];
203 for (std::size_t i = 0; i < n; ++i)
205 auto it = subst.find(w);
206 if (it != subst.end()) w = it->second;
208 for (
const auto &kv : subst)
217 for (std::size_t i = 0; i < n; ++i) {
218 auto g =
static_cast<gate_t>(i);
227 bool absorptive_rule_fired =
false;
228 bool boolean_rule_fired =
false;
236 std::unordered_set<gate_t> seen;
237 std::vector<gate_t> deduped;
238 deduped.reserve(
wires.size());
240 if (seen.insert(c).second) deduped.push_back(c);
242 if (deduped.size() !=
wires.size()) {
243 wires = std::move(deduped);
245 absorptive_rule_fired =
true;
247 boolean_rule_fired =
true;
256 bool has_one =
false;
262 gc.
setWires(g, std::vector<gate_t>{});
265 absorptive_rule_fired =
true;
290 const auto &wires_now = gc.
getWires(g);
291 if (wires_now.size() >= 2) {
292 std::unordered_set<gate_t> sibling_set(wires_now.begin(),
294 std::vector<gate_t> kept;
295 kept.reserve(wires_now.size());
296 bool dropped =
false;
297 for (
gate_t c : wires_now) {
301 if (w != c && sibling_set.count(w)) {
306 if (absorb) { dropped =
true;
continue; }
313 absorptive_rule_fired =
true;
315 boolean_rule_fired =
true;
320 if (absorptive_rule_fired)
322 if (boolean_rule_fired)
324 if (absorptive_rule_fired || boolean_rule_fired)
371 const std::size_t n = w.size() / 2;
373 std::unordered_map<gate_t, std::size_t> unknown;
374 for(std::size_t i = 0; i < n; ++i) {
377 "The first half of a gate_fixsystem's wires must be its "
378 "gate_fixvar unknowns");
379 unknown.emplace(w[i], i);
384 std::unordered_map<gate_t, bool> dep;
386 std::vector<gate_t> st;
387 for(std::size_t i = n; i < w.size(); ++i)
390 const gate_t u = st.back();
391 if(dep.count(u)) { st.pop_back();
continue; }
394 if(!unknown.count(u))
396 "An unknown of another equation system occurs in this one");
397 dep.emplace(u,
true);
402 dep.emplace(u,
false);
408 if(!dep.count(c)) { st.push_back(c); ready =
false; }
421 using Conj = std::vector<gate_t>;
424 std::vector<std::pair<std::size_t, Conj> > terms;
426 std::unordered_map<gate_t, Lin> lin;
427 std::function<
const Lin &(
gate_t)> linear = [&](
gate_t u) ->
const Lin & {
428 auto it = lin.find(u);
435 r.terms.emplace_back(unknown.at(u), Conj{});
440 const Lin &l = linear(c);
441 r.c.insert(r.c.end(), l.c.begin(), l.c.end());
442 r.terms.insert(r.terms.end(), l.terms.begin(), l.terms.end());
444 r.c.push_back(Conj{c});
455 "This recursion's equations are not linear: a product "
456 "has two factors depending on the recursive relation");
461 const Lin &l = linear(var);
462 for(
const auto &conj : l.c) {
464 e.insert(e.end(), k.begin(), k.end());
465 r.c.push_back(std::move(e));
467 for(
const auto &[j, conj] : l.terms) {
469 e.insert(e.end(), k.begin(), k.end());
470 r.terms.emplace_back(j, std::move(e));
483 std::string(
"This recursion's equations are not linear "
484 "semiring expressions in the recursive relation "
488 return lin.emplace(u, std::move(r)).first->second;
496 for(std::size_t i = 0; i < n; ++i) {
497 const gate_t f = w[n + i];
499 const Lin &l = linear(f);
501 for(
const auto &[j, conj] : l.terms) {
502 out.
in[i].emplace_back(j, conj);
503 out.
out[j].emplace_back(i, conj);
506 out.
b[i].push_back(Conj{f});
gate_t
Strongly-typed gate identifier.
Semiring-agnostic in-memory provenance circuit.
Exception type thrown by circuit operations on invalid input.
A refusal by design, or a known gap, rather than an error.
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
gateType getGateType(gate_t g) const
Return the type of gate g.
virtual gate_t setGate(const uuid &u, gateType type)
Create or update the gate associated with UUID u.
void setGateType(gate_t g, gateType t)
Update the type of an existing gate.
void pointName(gate_t g, gate_t target)
std::vector< std::vector< gate_t > > wires
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
virtual gate_t addGate()
Allocate a new gate with a default-initialised type.
void setWires(gate_t g, std::vector< gate_t > w)
Replace the wires of g with w.
std::map< gate_t, std::pair< unsigned, unsigned > > infos
Per-gate (info1, info2) annotations.
void markAbsorptiveAssumed(gate_t g)
Mark gate g as absorptive-assumed (in-memory side band).
bool foldSemiringIdentities()
Drop semiring identity wires and collapse single-wire gate_times / gate_plus to their lone non-identi...
void foldAbsorptiveIdentities()
Absorptive-rules-only variant of foldBooleanIdentities(): the joint fixpoint of the absorptive fold r...
std::map< gate_t, std::string > extra
Per-gate string extras.
gate_t addGate() override
Allocate a new gate with a default-initialised type.
std::set< gate_t > inputs
Set of input (leaf) gate IDs.
std::set< gate_t > absorptive_assumed_gates
Side-band absorptive-assumption marker set by the absorptive fold rules (plus-idempotence,...
std::vector< double > prob
Per-gate probability values.
FixSystemLinear linearizeFixSystem(gate_t sys) const
The equations of the gate_fixsystem sys, as linear forms over the gates that do not depend on its unk...
gate_t setGate(gate_type type) override
Allocate a new gate with type type and no UUID.
void markBooleanAssumed(gate_t g)
Mark gate g as Boolean-assumed (in-memory side band).
std::set< gate_t > boolean_assumed_gates
Side-band Boolean-assumption marker set by the Boolean-only fold rules ; an evaluator visiting a gate...
void redirectGates(std::unordered_map< gate_t, gate_t > subst)
Make every reference to a gate of subst point to its target instead.
bool applyFoldRuleSweep(bool boolean_level)
One pass of the fold rules over every gate_plus / gate_times.
void foldBooleanIdentities()
Apply the Boolean-only AND the absorptive simplification rules to gate_plus and gate_times,...
const char * gate_type_name[]
Names of gate types.
@ gate_annotation
Transparent single-child wrapper carrying a query-level annotation in extra (inversion-free certifica...
@ gate_fixpoint
Component of the least solution of an equation system: one wire to a gate_fixsystem,...
@ gate_fixvar
Unknown of an equation system (see gate_fixsystem): a leaf standing for the solution of one equation,...
@ gate_assumed
Structural marker over a single child whose sub-circuit was computed under a Boolean-provenance assum...
In-memory provenance circuit with semiring-generic evaluation.
std::vector< std::vector< std::vector< gate_t > > > b
Constant part of each equation.
std::size_t n
Number of unknowns.
std::vector< std::vector< std::pair< std::size_t, std::vector< gate_t > > > > in
Terms of each equation.
std::vector< std::vector< std::pair< std::size_t, std::vector< gate_t > > > > out
Terms, by unknown read.