111 SemiringT S = SemiringT{})
117 if (cmp_gates.empty())
124 if (!S.commutative())
127 "A HAVING condition's provenance is a product over the worlds "
128 "of its group, in no order of the query: it has no value in a "
129 "semiring whose multiplication does not commute.");
138 auto certifiable_contributors =
139 [&](
const std::vector<typename SemiringT::value_type> &kv) ->
bool {
144 for (
size_t i = 0; i < kv.size(); ++i) {
145 if (!S.independent_literal(kv[i]))
149 if (kv[i] == S.one() || kv[i] == S.zero())
151 for (
size_t j = 0; j < i; ++j)
173 auto combine_exhaustive_worlds =
174 [&](
const std::vector<mask_t> &worlds,
175 const std::vector<typename SemiringT::value_type> &kvals,
176 bool upset,
bool monotone) ->
typename SemiringT::value_type {
180 if (certifiable_contributors(kvals)) {
181 std::vector<typename SemiringT::value_type> disjuncts;
182 disjuncts.reserve(worlds.size());
183 for (
const auto &mask : worlds) {
184 std::vector<typename SemiringT::value_type> present, missing;
186 for (
size_t i = 0; i < kvals.size(); ++i)
187 (mask[i] ? present : missing).push_back(kvals[i]);
188 disjuncts.push_back(S.certified_world_term(present, missing));
190 return S.certified_exclusive_plus(disjuncts);
193 std::vector<typename SemiringT::value_type> disjuncts;
194 disjuncts.reserve(worlds.size());
195 const size_t n = kvals.size();
196 const bool no_monus = upset || (monotone && S.idempotent());
198 for (
const auto &mask : worlds) {
199 std::vector<typename SemiringT::value_type> present, missing;
204 for (
size_t i = 0; i < n; ++i) {
206 if (kvals[i] != S.one())
207 present.push_back(kvals[i]);
208 }
else if (!no_monus) {
209 if (kvals[i] != S.zero())
210 missing.push_back(kvals[i]);
214 auto present_prod = S.times(present);
216 if (missing.empty()) {
217 disjuncts.push_back(std::move(present_prod));
219 auto monus_factor = S.monus(S.one(), S.plus(missing));
220 auto term = monus_factor;
221 if (present_prod != S.one())
222 term = S.times(std::vector<typename SemiringT::value_type>{
223 present_prod, monus_factor});
224 disjuncts.push_back(std::move(term));
228 return S.plus(disjuncts);
253 [&](
const std::vector<long> &mvals,
long C,
254 const std::vector<typename SemiringT::value_type> &kvals,
257 using V =
typename SemiringT::value_type;
258 std::vector<V> lt, le, ge, gt, eq;
259 for (
size_t i = 0; i < kvals.size(); ++i) {
260 if (kvals[i] == S.zero())
continue;
261 if (mvals[i] < C) lt.push_back(kvals[i]);
262 if (mvals[i] <= C) le.push_back(kvals[i]);
263 if (mvals[i] >= C) ge.push_back(kvals[i]);
264 if (mvals[i] > C) gt.push_back(kvals[i]);
265 if (mvals[i] == C) eq.push_back(kvals[i]);
267 auto sum = [&](
const std::vector<V> &v) -> V {
268 return v.empty() ? S.zero() : S.plus(v);
271 auto guarded = [&](
const std::vector<V> &spoilers,
272 const std::vector<V> &witnesses) -> V {
273 if (witnesses.empty())
return S.zero();
274 V w = S.plus(witnesses);
275 if (spoilers.empty())
return w;
276 return S.times(std::vector<V>{S.monus(S.one(), S.plus(spoilers)), w});
282 const std::vector<V> &below = is_max ? gt : lt;
283 const std::vector<V> &below_eq = is_max ? ge : le;
284 const std::vector<V> &above = is_max ? lt : gt;
285 const std::vector<V> &above_eq = is_max ? le : ge;
296 V b = guarded(below_eq, above);
297 if (a == S.zero())
return b;
298 if (b == S.zero())
return a;
299 return S.plus(std::vector<V>{a, b});
320 using fiber_t = std::pair<size_t, std::vector<size_t>>;
321 auto first_present_provenance =
322 [&](
const std::vector<fiber_t> &fibers,
323 const std::vector<typename SemiringT::value_type> &kvals,
324 bool monotone) ->
typename SemiringT::value_type {
325 using V =
typename SemiringT::value_type;
326 if (fibers.empty())
return S.zero();
328 if (S.absorptive() && S.mul_sub_left_distributive()) {
329 std::vector<V> terms;
330 for (
const auto &fb : fibers) {
331 const V &k = kvals[fb.first];
332 if (k == S.zero())
continue;
333 std::vector<V> absent;
334 for (
size_t j : fb.second)
335 if (kvals[j] != S.zero()) absent.push_back(kvals[j]);
336 if (absent.empty()) { terms.push_back(k);
continue; }
337 V guard = S.monus(S.one(), S.plus(absent));
338 terms.push_back(k == S.one() ? guard : S.times(std::vector<V>{guard, k}));
340 return terms.empty() ? S.zero() : S.plus(terms);
343 const size_t n = kvals.size();
344 std::vector<mask_t> worlds;
345 for (
const auto &fb : fibers) {
346 std::vector<bool> fixed(n,
false);
347 fixed[fb.first] =
true;
348 for (
size_t j : fb.second) fixed[j] =
true;
349 std::vector<size_t> free_idx;
350 for (
size_t j = 0; j < n; ++j)
351 if (!fixed[j]) free_idx.push_back(j);
352 const size_t m = free_idx.size();
354 : worlds.size() + (
size_t(1) << m));
355 for (
size_t sub = 0; sub < (size_t(1) << m); ++sub) {
357 mask[fb.first] =
true;
358 for (
size_t b = 0; b < m; ++b)
359 if (sub & (
size_t(1) << b)) mask[free_idx[b]] =
true;
360 worlds.push_back(std::move(mask));
363 return combine_exhaustive_worlds(worlds, kvals,
false, monotone);
372auto build_joint = [&](
const std::vector<JointAtom> &atoms,
373 const std::function<bool(
const std::vector<bool> &)>
375 typename SemiringT::value_type &pw_out) ->
bool {
380 std::vector<std::pair<int, double> > contribs;
383 auto text_is_int = [](
const std::string &s) ->
bool {
384 if (s.empty())
return false;
386 if (!((ch >=
'0' && ch <=
'9') || ch ==
'+' || ch ==
'-'))
390 std::map<gate_t, AggInfo> aggs;
391 std::map<gate_t, int> kindex;
392 std::vector<gate_t> kgates;
396 auto parse_number = [](
const std::string &s,
double &out) ->
bool {
399 out = std::stod(s, &pos);
400 return pos == s.size();
406 std::function<bool(
gate_t)> collect = [&](
gate_t gx) ->
bool {
440 auto it = kindex.find(kg);
441 if (it == kindex.end()) {
442 idx =
static_cast<int>(kgates.size());
444 kgates.push_back(kg);
448 if (!parse_number(ms, m))
return false;
449 ai.contribs.emplace_back(idx, m);
451 aggs.emplace(gx, std::move(ai));
472 for (
const JointAtom &a : atoms)
473 if (!collect(a.L) || !collect(a.R))
477 const size_t n = kgates.size();
483 std::function<bool(
gate_t, uint64_t,
double &,
bool &)> eval =
484 [&](
gate_t gx, uint64_t world,
double &out,
bool &is_int) ->
bool {
488 if (!parse_number(s, out))
return false;
489 is_int = text_is_int(s);
493 std::string ms;
gate_t kg{};
495 if (!parse_number(ms, out))
return false;
496 is_int = text_is_int(ms);
500 const AggInfo &ai = aggs.at(gx);
501 double acc = 0, mn = 0, mx = 0, fst = 0;
504 for (
const auto &pr : ai.contribs)
505 if (world & (uint64_t(1) << pr.first)) {
506 double m = pr.second;
508 if (first) { mn = mx = fst = m; first =
false; }
509 else { mn = std::min(mn, m); mx = std::max(mx, m); }
531 if (cnt == 0 && !ai.is_scalar)
return false;
532 out = acc;
return true;
543 "having_semantics: aggregate kind not read per world");
548 unsigned aop =
static_cast<unsigned>(c.
getInfos(gx).first);
554 if (!eval(ch, world, v, vi))
return false;
556 all_int = all_int && vi;
558 out = r; is_int = all_int;
return true;
561 if (w.size() != 2)
return false;
562 double a, b;
bool ai, bi;
563 if (!eval(w[0], world, a, ai) || !eval(w[1], world, b, bi))
return false;
564 out = a - b; is_int = ai && bi;
return true;
567 if (w.size() != 2)
return false;
568 double a, b;
bool ai, bi;
569 if (!eval(w[0], world, a, ai) || !eval(w[1], world, b, bi))
return false;
570 if (b == 0)
return false;
572 out = std::trunc(a / b);
591 if (w.size() != 1)
return false;
593 if (!eval(w[0], world, a, ai))
return false;
594 out = -a; is_int = ai;
return true;
602 if (w.size() != 1 || !eval(w[0], world, a, ai))
return false;
604 ? a :
static_cast<double>(
static_cast<float>(a));
614 if (w.empty() || !eval(w[0], world, a, ai))
return false;
618 else if (w.size() == 1) out = std::round(a);
622 if (!eval(w[1], world, d, di))
return false;
623 const double f = std::pow(10.0, d);
624 out = std::round(a * f) / f;
651 if (w.empty() || !eval(w[0], world, a, ai))
return false;
652 bool nan_operand = std::isnan(a);
654 if (!nan_operand && !(a > 0))
return false;
662 if (w.size() != 2 || !eval(w[1], world, e, ei))
return false;
663 nan_operand = nan_operand || std::isnan(e);
664 out = std::pow(a, e);
665 if (std::isnan(out) && !nan_operand)
return false;
667 if (!nan_operand && !std::isfinite(out))
return false;
672 if (w.empty())
return false;
673 double r = 0;
bool all_int =
true, first =
true;
676 if (!eval(ch, world, v, vi))
return false;
678 if (first) { r = v; first =
false; }
682 all_int = all_int && vi;
684 out = r; is_int = all_int;
return true;
696 std::vector<double> members;
697 double fraction, pos, fp;
700 if (w.empty() || w.size() % 2 != 0)
return false;
702 fraction = std::stod(c.
getExtra(gx));
703 }
catch (
const std::exception &) {
706 for (std::size_t i = 0; i < w.size(); i += 2) {
710 if (!eval(w[i], world, ind, ii))
return false;
711 if (ind < 0.5)
continue;
713 if (!eval(w[i + 1], world, x, xi))
continue;
714 members.push_back(x);
716 if (members.empty())
return false;
718 pos = fraction *
static_cast<double>(members.size() - 1);
719 lo =
static_cast<std::size_t
>(pos);
720 fp = pos -
static_cast<double>(lo);
721 out = (lo + 1 < members.size())
722 ? members[lo] + fp * (members[lo + 1] - members[lo])
737 "having_semantics: unknown gate_arith operator tag: " +
738 std::to_string(aop));
743 std::vector<typename SemiringT::value_type> kval(n);
744 for (
size_t i = 0; i < n; ++i)
745 kval[i] = c.
evaluate<SemiringT>(kgates[i], mapping, S);
749 const bool certify = certifiable_contributors(kval);
759 const bool empty_world_valid =
761 std::all_of(aggs.begin(), aggs.end(),
762 [](
const std::pair<const gate_t, AggInfo> &e) {
763 return e.second.is_scalar;
768 if (n == 0 && !empty_world_valid)
771 std::vector<typename SemiringT::value_type> disjuncts;
772 const uint64_t total = uint64_t(1) << n;
773 for (uint64_t world = empty_world_valid ? 0 : 1; world < total; ++world) {
774 std::vector<bool> truth(atoms.size(),
false);
775 for (
size_t ai = 0; ai < atoms.size(); ++ai) {
778 if (!eval(atoms[ai].L, world, lv, lint) ||
779 !eval(atoms[ai].R, world, rv, rint))
784 switch (atoms[ai].op) {
799 std::vector<typename SemiringT::value_type> present, missing;
800 for (
size_t i = 0; i < n; ++i) {
801 if (world & (uint64_t(1) << i)) {
802 if (certify || kval[i] != S.one()) present.push_back(kval[i]);
804 if (certify || kval[i] != S.zero()) missing.push_back(kval[i]);
808 disjuncts.push_back(S.certified_world_term(present, missing));
811 auto present_prod = S.times(present);
813 disjuncts.push_back(std::move(present_prod));
815 auto monus_factor = S.monus(S.one(), S.plus(missing));
817 present_prod == S.one()
819 : S.times(std::vector<typename SemiringT::value_type>{
820 present_prod, monus_factor}));
824 pw_out = disjuncts.empty() ? S.zero()
825 : certify ? S.certified_exclusive_plus(disjuncts)
830 auto pw_from_cmp_gate = [&](
gate_t cmp_gate,
typename SemiringT::value_type &pw_out) ->
bool {
831 const auto &cw = c.
getWires(cmp_gate);
832 if (cw.size() != 2)
return false;
839 if (!okop)
return false;
848 const bool is_scalar =
851 const auto &children = c.
getWires(agg_side);
866 std::vector<std::string> mvals_str;
867 std::vector<typename SemiringT::value_type> kvals;
868 mvals_str.reserve(children.size());
869 kvals.reserve(children.size());
870 for (
gate_t ch : children) {
875 mvals_str.push_back(m_str);
876 kvals.push_back(c.
evaluate<SemiringT>(k_gate, mapping, S));
883 throw std::runtime_error(
884 "comparing an aggregate with a text constant in HAVING "
885 "is only implemented for choose()");
888 throw std::runtime_error(
889 "only = and <> are supported when comparing choose() "
890 "with a text constant");
901 if (certifiable_contributors(kvals)) {
902 std::vector<typename SemiringT::value_type> disjuncts;
903 std::vector<typename SemiringT::value_type> before;
904 for (
size_t i = 0; i < kvals.size(); ++i) {
906 ? (mvals_str[i] == C_str)
907 : (mvals_str[i] != C_str);
909 disjuncts.push_back(S.certified_world_term(
910 std::vector<typename SemiringT::value_type>{kvals[i]},
912 before.push_back(kvals[i]);
914 pw_out = disjuncts.empty() ? S.zero()
915 : S.certified_exclusive_plus(disjuncts);
918 std::vector<fiber_t> fibers;
919 std::vector<size_t> before;
920 for (
size_t i = 0; i < kvals.size(); ++i) {
922 ? (mvals_str[i] == C_str)
923 : (mvals_str[i] != C_str);
924 if (match) fibers.emplace_back(i, before);
927 pw_out = first_present_provenance(fibers, kvals,
false);
953 throw std::runtime_error(
954 "only = and <> are supported when comparing a boolean aggregate "
955 "(bool_or / bool_and / every) with a constant in HAVING");
957 auto parse_bool = [](
const std::string &s,
bool &ok) ->
bool {
959 if (s ==
"t" || s ==
"true" || s ==
"1")
return true;
960 if (s ==
"f" || s ==
"false" || s ==
"0")
return false;
961 ok =
false;
return false;
967 const bool C = parse_bool(C_str, okc);
968 if (!okc)
return false;
972 std::vector<bool> vals;
973 std::vector<typename SemiringT::value_type> kvals;
974 vals.reserve(children.size());
975 kvals.reserve(children.size());
976 for (
gate_t ch : children) {
982 const bool b = parse_bool(m_str, okv);
983 if (!okv)
return false;
985 kvals.push_back(c.
evaluate<SemiringT>(k_gate, mapping, S));
989 std::vector<size_t> someE;
990 std::vector<size_t> noneF;
991 if (want_or == target) {
994 for (
size_t i = 0; i < vals.size(); ++i)
995 if (vals[i] == want_or) someE.push_back(i);
999 for (
size_t i = 0; i < vals.size(); ++i)
1000 (vals[i] == want_or ? noneF : someE).push_back(i);
1003 if (someE.empty()) { pw_out = S.zero();
return true; }
1005 if (certifiable_contributors(kvals)) {
1006 std::vector<typename SemiringT::value_type> disjuncts;
1007 std::vector<typename SemiringT::value_type> before;
1008 for (
size_t e : someE) {
1009 std::vector<typename SemiringT::value_type> missing = before;
1010 for (
size_t f : noneF) missing.push_back(kvals[f]);
1011 disjuncts.push_back(S.certified_world_term(
1012 std::vector<typename SemiringT::value_type>{kvals[e]}, missing));
1013 before.push_back(kvals[e]);
1015 pw_out = S.certified_exclusive_plus(disjuncts);
1027 if (noneF.empty() && S.absorptive()) {
1028 std::vector<typename SemiringT::value_type> witnesses;
1029 for (
size_t e : someE)
1030 if (kvals[e] != S.zero()) witnesses.push_back(kvals[e]);
1031 pw_out = witnesses.empty() ? S.zero() : S.plus(witnesses);
1035 std::vector<fiber_t> fibers;
1036 std::vector<size_t> absent = noneF;
1037 for (
size_t e : someE) {
1038 fibers.emplace_back(e, absent);
1039 absent.push_back(e);
1041 pw_out = first_present_provenance(fibers, kvals,
1055 throw std::runtime_error(
1056 "only = and <> are supported when comparing array_agg() with a "
1057 "constant array in HAVING");
1061 std::vector<std::string> target;
1064 std::vector<std::string> vals;
1065 std::vector<typename SemiringT::value_type> kvals;
1066 vals.reserve(children.size());
1067 kvals.reserve(children.size());
1068 for (
gate_t ch : children) {
1075 m_str = array_null_element();
1076 vals.push_back(m_str);
1077 kvals.push_back(c.
evaluate<SemiringT>(k_gate, mapping, S));
1085 auto canon_bool = [](std::string &s) {
1086 if (s ==
"t" || s ==
"true" || s ==
"1") s =
"true";
1087 else if (s ==
"f" || s ==
"false" || s ==
"0") s =
"false";
1089 for (
auto &e : target) canon_bool(e);
1090 for (
auto &v : vals) canon_bool(v);
1095 pw_out = combine_exhaustive_worlds(worlds, kvals,
false,
1103 auto finish_domain = [&](
const std::vector<long> &mvals,
long C,
1104 const std::vector<typename SemiringT::value_type> &kvals)
1112 const bool certify = certifiable_contributors(kvals);
1122 S.absorptive() && !certify) {
1123 const bool existential =
1129 if (existential || S.mul_sub_left_distributive()) {
1130 pw_out = min_max_scan(mvals, C, kvals, effective_op, agg_kind);
1137 certify ?
false : S.absorptive(),
1148 bool monotone =
false;
1155 std::all_of(mvals.begin(), mvals.end(), [](
long v) { return v >= 0; });
1160 pw_out = combine_exhaustive_worlds(worlds, kvals, upset, monotone);
1175 std::vector<std::string> m_strs;
1176 std::vector<typename SemiringT::value_type> kvals;
1177 for (
gate_t ch : children) {
1182 m_strs.push_back(m_str);
1183 kvals.push_back(c.
evaluate<SemiringT>(k_gate, mapping, S));
1185 std::vector<long> ranks;
1189 return finish_domain(ranks, C_rank, kvals);
1199 long C_mant = 0;
int C_scale = 0;
1202 std::vector<long> m_mant;
1203 std::vector<int> m_scale;
1204 std::vector<typename SemiringT::value_type> kvals;
1205 m_mant.reserve(children.size());
1206 m_scale.reserve(children.size());
1207 kvals.reserve(children.size());
1208 for (
gate_t ch : children) {
1213 long mm = 0;
int ms = 0;
1215 m_mant.push_back(mm);
1216 m_scale.push_back(ms);
1217 kvals.push_back(c.
evaluate<SemiringT>(k_gate, mapping, S));
1221 int target_scale = C_scale;
1222 for (
int ms : m_scale) target_scale = std::max(target_scale, ms);
1224 if (!
rescale_to(C_mant, C_scale, target_scale, C))
return false;
1225 std::vector<long> mvals(m_mant.size());
1226 for (
size_t i = 0; i < m_mant.size(); ++i)
1227 if (!
rescale_to(m_mant[i], m_scale[i], target_scale, mvals[i]))
return false;
1229 return finish_domain(mvals, C, kvals);
1243 return build_joint(std::vector<JointAtom>{JointAtom{Lx, Rx, opx}},
1244 [](
const std::vector<bool> &t) {
return t[0]; },
1256 std::map<gate_t, std::size_t> bit;
1257 std::vector<typename SemiringT::value_type> kvals;
1258 std::vector<std::size_t> bits[2];
1259 std::vector<std::string> vals[2];
1260 const gate_t sides[2] = {Lx, Rx};
1262 for (
int side = 0; side < 2; ++side) {
1272 m_str = array_null_element();
1273 auto it = bit.find(k_gate);
1274 if (it == bit.end()) {
1275 if (kvals.size() >= 20)
1277 it = bit.emplace(k_gate, kvals.size()).first;
1278 kvals.push_back(c.
evaluate<SemiringT>(k_gate, mapping, S));
1280 bits[side].push_back(it->second);
1281 vals[side].push_back(m_str);
1288 bits[0], vals[0], bits[1], vals[1], kvals.size(),
1290 pw_out = combine_exhaustive_worlds(worlds, kvals,
false,
1300 build_array_pair(L, R, op))
1303 return build_general(L, R, op);
1320 std::vector<FNode> kids;
1328 auto count_range = [&](
const std::vector<JointAtom> &atoms,
1330 typename SemiringT::value_type &out) ->
bool {
1331 if (!S.absorptive() || !S.mul_sub_left_distributive())
1333 std::function<bool(
const FNode &)> all_and = [&](
const FNode &n) {
1334 if (n.kind == 0)
return true;
1335 if (n.kind != 1)
return false;
1336 for (
const FNode &k : n.kids)
1337 if (!all_and(k))
return false;
1342 long lo = 0, hi = -1;
1343 bool scalar =
false;
1344 std::vector<gate_t> ks;
1345 for (
size_t ai = 0; ai < atoms.size(); ++ai) {
1346 gate_t agg = atoms[ai].L, cst = atoms[ai].R;
1349 std::swap(agg, cst);
1361 std::size_t pos = 0;
1362 v = std::stol(cs, &pos);
1363 if (pos != cs.size())
return false;
1368 std::vector<gate_t> these;
1375 these.push_back(kg);
1379 else if (these != ks)
1387 lo = std::max(lo, v);
1388 hi = hi < 0 ? v : std::min(hi, v);
1394 if (!scalar && lo < 1)
1396 const long n =
static_cast<long>(ks.size());
1397 if ((hi >= 0 && hi < lo) || lo > n) {
1401 const long top = (hi >= 0 && hi + 1 <= n) ? hi + 1 : lo;
1402 std::vector<typename SemiringT::value_type> Sj(top + 1, S.zero());
1404 for (
long i = 0; i < n; ++i) {
1405 auto a = c.
evaluate<SemiringT>(ks[i], mapping, S);
1406 for (
long j = std::min(top, i + 1); j >= 1; --j)
1407 Sj[j] = S.plus(std::vector<typename SemiringT::value_type>{
1408 Sj[j], S.times(std::vector<typename SemiringT::value_type>{
1411 out = (hi >= 0 && hi + 1 <= n) ? S.monus(Sj[lo], Sj[hi + 1]) : Sj[lo];
1415 if (!S.product_is_joint()) {
1416 std::set<gate_t> cmpset(cmp_gates.begin(), cmp_gates.end());
1419 std::function<void(
gate_t, std::set<gate_t> &)> family_walk =
1420 [&](
gate_t x, std::set<gate_t> &fam) {
1432 family_walk(ch, fam);
1435 std::function<bool(
gate_t, std::set<gate_t> &,
bool &, FNode &,
1436 std::vector<JointAtom> &)> as_combination =
1437 [&](
gate_t x, std::set<gate_t> &fam,
bool &fam_set, FNode &out,
1438 std::vector<JointAtom> &atoms) ->
bool {
1439 if (cmpset.count(x)) {
1444 if (w.size() != 2 || !okop)
1452 }
else if (fam != f)
1455 out.atom = atoms.size();
1456 atoms.push_back(JointAtom{w[0], w[1], op});
1465 if (!as_combination(ch, fam, fam_set, k, atoms))
1467 out.kids.push_back(std::move(k));
1469 return !out.kids.empty();
1471 std::function<bool(
const FNode &,
const std::vector<bool> &)> holds =
1472 [&](
const FNode &n,
const std::vector<bool> &t) ->
bool {
1475 for (
const FNode &k : n.kids) {
1476 bool v = holds(k, t);
1477 if (n.kind == 1 && !v)
return false;
1478 if (n.kind == 2 && v)
return true;
1483 std::set<gate_t> seen;
1484 std::vector<gate_t> todo{g};
1486 static TimestampTz warned_at = 0;
1487 bool warned = warned_at == GetCurrentStatementStartTimestamp();
1488 while (!todo.empty()) {
1491 if (!seen.insert(p).second)
1496 std::map<std::set<gate_t>, std::vector<std::pair<gate_t, FNode>>> groups;
1498 std::set<gate_t> fam;
1499 bool fam_set =
false;
1501 std::vector<JointAtom> scratch;
1502 if (as_combination(ch, fam, fam_set, n, scratch))
1503 groups[fam].emplace_back(ch, FNode());
1505 for (
auto &grp : groups) {
1506 if (grp.second.size() < 2)
1508 std::vector<JointAtom> atoms;
1511 std::set<gate_t> fam;
1512 bool fam_set =
false, ok =
true;
1513 for (
auto &m : grp.second) {
1515 if (!as_combination(m.first, fam, fam_set, k, atoms)) {
1519 root.kids.push_back(std::move(k));
1521 typename SemiringT::value_type joint;
1523 (!count_range(atoms, root, joint) &&
1525 [&](
const std::vector<bool> &t) {
1526 return holds(root, t);
1531 warned_at = GetCurrentStatementStartTimestamp();
1533 "conditions on aggregates of one group are combined as the "
1534 "product of their provenances, which is not the provenance "
1535 "of their combination in this semiring: these aggregates are "
1536 "not resolved jointly");
1543 mapping[n] = std::move(joint);
1544 std::vector<gate_t> wires;
1545 std::set<gate_t> replaced;
1546 for (
auto &m : grp.second)
1547 replaced.insert(m.first);
1549 if (!replaced.count(ch))
1550 wires.push_back(ch);
1556 if (!cmpset.count(ch))
1571 std::set<gate_t> reachable;
1573 std::vector<gate_t> st{g};
1574 while (!st.empty()) {
1577 if (!reachable.insert(x).second)
1583 for (
gate_t cmp_gate : cmp_gates) {
1584 typename SemiringT::value_type pw;
1585 if (!reachable.count(cmp_gate))
1588 if (!S.product_is_joint()) {
1589 const auto &w = c.
getWires(cmp_gate);
1595 if (w.size() == 2 && okop &&
1596 count_range(std::vector<JointAtom>{JointAtom{w[0], w[1], op}}, one,
1598 mapping[cmp_gate] = std::move(pw);
1602 if (!pw_from_cmp_gate(cmp_gate, pw))
1605 mapping[cmp_gate] = std::move(pw);