43bool constant_of(GenericCircuit &gc,
gate_t g, std::string &out,
bool &is_null)
55 is_null = out.empty() || out ==
"NULL" ||
56 gc.
getUUID(g) == provsql_having_detail::GATE_NULL_UUID;
61bool decide_constant_cmp(GenericCircuit &gc,
gate_t l,
gate_t r,
65 bool lnull =
false, rnull =
false;
67 int lscale = 0, rscale = 0, scale;
69 if (!constant_of(gc, l, ls, lnull) || !constant_of(gc, r, rs, rnull))
78 scale = lscale > rscale ? lscale : rscale;
82 holds = op_holds(op, lm < rm ? -1 : (lm > rm ? 1 : 0));
92void expand(GenericCircuit &gc,
gate_t cmp,
unsigned side,
gate_t one)
95 const std::vector<gate_t> cw = gc.
getWires(cmp);
96 const gate_t selection = cw[side], other = cw[1 - side];
97 const std::vector<gate_t> aw = gc.
getWires(selection);
98 const std::pair<unsigned, unsigned> infos = gc.
getInfos(cmp);
99 const std::size_t n = aw.size(), arms = (n - 1) / 2;
102 std::vector<gate_t> terms;
104 for (std::size_t i = 0; i <= arms; ++i) {
105 const bool is_default = (i == arms);
106 const gate_t value = is_default ? aw[n - 1] : aw[2 * i + 1];
107 const gate_t l = (side == 0) ? value : other;
108 const gate_t r = (side == 0) ? other : value;
109 std::vector<gate_t> factors;
114 if (okop && decide_constant_cmp(gc, l, r, op, holds)) {
120 gc.
setInfos(arm_cmp, infos.first, infos.second);
124 for (std::size_t j = 0; j < i; ++j)
127 factors.push_back(aw[2 * i]);
128 factors.push_back(arm_cmp);
129 terms.push_back(factors.size() == 1
156bool hoist_cases_out_of_arith(GenericCircuit &gc)
158 std::vector<gate_t> stack;
159 std::vector<bool> seen(gc.
getNbGates(),
false);
160 std::vector<gate_t> todo;
162 for (std::size_t i = 0; i < gc.
getNbGates(); ++i) {
163 const auto g =
static_cast<gate_t>(i);
169 while (!stack.empty()) {
170 const gate_t g = stack.back();
174 seen[
static_cast<std::size_t
>(g)] =
true;
175 bool has_case =
false;
178 const std::size_t n = gc.
getWires(c).size();
179 if (n >= 1 && n % 2 == 1)
190 const std::vector<gate_t> gw = gc.
getWires(g);
191 const std::pair<unsigned, unsigned> infos = gc.
getInfos(g);
194 gc.
getWires(gw[k]).size() % 2 == 1))
198 const std::vector<gate_t> aw = gc.
getWires(gw[k]);
199 const std::size_t n = aw.size();
200 std::vector<gate_t> nw;
201 for (std::size_t i = 0; i < n; ++i) {
202 if (i % 2 == 0 && i != n - 1) {
206 std::vector<gate_t> operands = gw;
213 return !todo.empty();
228bool subtract_expression_comparisons(GenericCircuit &gc,
gate_t &zero,
231 std::vector<gate_t> todo;
233 for (std::size_t i = 0; i < gc.
getNbGates(); ++i) {
234 const auto g =
static_cast<gate_t>(i);
239 bool is_null =
false;
240 if (constant_of(gc, w[0], ignored, is_null) ||
241 constant_of(gc, w[1], ignored, is_null))
255 const std::vector<gate_t> w = gc.
getWires(g);
267 unsigned decided = 0;
269 for (std::size_t i = 0; i < gc.
getNbGates(); ++i) {
270 const auto g =
static_cast<gate_t>(i);
271 bool okop =
false, holds =
false;
276 if (!okop || !decide_constant_cmp(gc, l, r, op, holds))
289 unsigned expanded = 0;
291 bool have_one =
false, have_zero =
false;
296 for (
unsigned round = 0; round < 32; ++round) {
297 std::vector<std::pair<gate_t, unsigned>> todo;
302 bool rewritten =
false;
303 if (subtract_expression_comparisons(gc, zero, have_zero)) {
307 if (hoist_cases_out_of_arith(gc)) {
313 for (std::size_t i = 0; i < nb; ++i) {
314 const auto g =
static_cast<gate_t>(i);
322 for (
unsigned side = 0; side < 2; ++side)
324 const std::size_t n = gc.
getWires(w[side]).size();
325 if (n >= 1 && n % 2 == 1)
326 todo.emplace_back(g, side);
340 for (
const auto &t : todo) {
343 expand(gc, t.first, t.second, one);
ComparisonOperator
SQL comparison operators used in gate_cmp circuit gates.
@ LE
Less than or equal (<=).
@ GE
Greater than or equal (>=).
Expansion of a comparison one of whose operands is a guarded selection (gate_case) into the compariso...
gate_t
Strongly-typed gate identifier.
Out-of-line template method implementations for Circuit<gateType>.
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.
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
void resolveToPlus(gate_t g, std::vector< gate_t > w)
Rewrite an arbitrary gate as a gate_plus over w.
void resolveGateToZero(gate_t g)
Replace an arbitrary gate (typically gate_times) by gate_zero.
void resolveGateToOne(gate_t g)
Rewrite a gate as gate_one, the event that holds in every world.
void resolveToCase(gate_t g, std::vector< gate_t > w)
Rewrite a gate as the gate_case over w (guards and values, then the default).
gate_t addAnonymousArithGate(provsql_arith_op op, std::vector< gate_t > wires_)
Allocate a fresh gate_arith gate with operator tag op and the given wires.
gate_t addAnonymousValueGate(const std::string &text)
Allocate a fresh gate_value gate carrying the textual scalar text.
void setInfos(gate_t g, unsigned info1, unsigned info2)
Set the integer annotation pair for gate g.
std::string getExtra(gate_t g) const
Return the string extra for gate g.
gate_t addAnonymousGate(gate_type type, std::vector< gate_t > wires_)
Allocate a fresh gate of type type over wires_.
std::pair< unsigned, unsigned > getInfos(gate_t g) const
Return the integer annotation pair for gate g.
Provenance evaluation helper for HAVING-clause circuits.
bool rescale_to(long mantissa, int scale, int target_scale, long &out)
bool parse_decimal_scaled(const std::string &s, long &mantissa, int &scale)
ComparisonOperator map_cmp_op(GenericCircuit &c, gate_t cmp_gate, bool &ok)
bool extract_constant_string(GenericCircuit &c, gate_t x, std::string &C_out)
unsigned runConstantCmpDecider(GenericCircuit &gc)
Decide every comparison between two constants.
unsigned runCaseCmpExpander(GenericCircuit &gc)
Expand every gate_cmp with a gate_case operand in gc.
Core types, constants, and utilities shared across ProvSQL.
provsql_arith_op
Arithmetic operator tags used by gate_arith.
@ PROVSQL_ARITH_MINUS
binary, child0 - child1
@ gate_case
N-ary guarded selection over scalar (RV) children: wires are [guard_1, value_1, .....
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)