Summary
A :merge expression containing a nested function call silently returns the old value instead of evaluating, whenever the colliding values happen to be equal. The shortcut added in #287 is applied at every node of the merge expression tree, but it is only sound at the root.
Repro
(function Sum (i64 i64) i64 :merge new)
(set (Sum 5 5) 1)
(function F (i64) i64 :merge (min old (Sum old new)))
(set (F 0) 5)
(set (F 0) 5)
(print-function F 10)
Actual:
Expected 1: the second set collides with old = new = 5, so the merge expression is min(5, Sum(5, 5)), and Sum 5 5 is 1, so min(5, 1) = 1.
Reproduced on c92a910 (v2.0.0), release build.
It is specific to the two colliding values being equal
Same program with the values distinct — so the nested call must be evaluated — is correct:
(function Sum (i64 i64) i64 :merge new)
(set (Sum 5 7) 1)
(function F (i64) i64 :merge (min old (Sum old new)))
(set (F 0) 5)
(set (F 0) 7)
(print-function F 10)
So Sum is called and its result used in the ordinary case; it is only skipped when old == new at the enclosing column.
Cause
egglog-bridge/src/lib.rs:1313-1317, the ResolvedMergeFn::Function arm of ResolvedMergeFn::run:
ResolvedMergeFn::Function { func, args, panic } => {
// see github.com/egraphs-good/egglog/pull/287
if cur == new {
return cur;
}run is invoked recursively for every node of the merge expression, but cur/new always refer to the enclosing function's colliding values. At the root, "if the two values are equal, the merged value is that value" is correct. At a nested node it is not: it returns the enclosing column's old value in place of the sub-expression's result, regardless of what the sub-expression computes.
#287's intent — avoid re-running a merge when nothing changed — seems right at the top level. The fix is presumably to apply the check once to each value column's result expression rather than inside the recursive evaluator.
Severity
Silent wrong answer, no error. Requires a merge expression with a nested call to another function, and a collision where the enclosing column's old and new values coincide.
It is worse in a downstream fork of ours that allows actions in a :merge body: there a nested call can have an eq-sort while the enclosing column is i64, so the shortcut returns an i64 payload as an e-class id, producing a row keyed on a dangling e-class that (print-function ...) renders as Unextractable and extraction rejects. That variant is not reachable in upstream syntax, which is why this is filed as the wrong-value case.
Summary
A
:mergeexpression containing a nested function call silently returns the old value instead of evaluating, whenever the colliding values happen to be equal. The shortcut added in #287 is applied at every node of the merge expression tree, but it is only sound at the root.Repro
Actual:
Expected
1: the secondsetcollides withold = new = 5, so the merge expression ismin(5, Sum(5, 5)), andSum 5 5is1, somin(5, 1) = 1.Reproduced on
c92a910(v2.0.0), release build.It is specific to the two colliding values being equal
Same program with the values distinct — so the nested call must be evaluated — is correct:
So
Sumis called and its result used in the ordinary case; it is only skipped whenold == newat the enclosing column.Cause
egglog-bridge/src/lib.rs:1313-1317, theResolvedMergeFn::Functionarm ofResolvedMergeFn::run:runis invoked recursively for every node of the merge expression, butcur/newalways refer to the enclosing function's colliding values. At the root, "if the two values are equal, the merged value is that value" is correct. At a nested node it is not: it returns the enclosing column's old value in place of the sub-expression's result, regardless of what the sub-expression computes.#287's intent — avoid re-running a merge when nothing changed — seems right at the top level. The fix is presumably to apply the check once to each value column's result expression rather than inside the recursive evaluator.
Severity
Silent wrong answer, no error. Requires a merge expression with a nested call to another function, and a collision where the enclosing column's old and new values coincide.
It is worse in a downstream fork of ours that allows actions in a
:mergebody: there a nested call can have an eq-sort while the enclosing column isi64, so the shortcut returns ani64payload as an e-class id, producing a row keyed on a dangling e-class that(print-function ...)renders asUnextractableand extraction rejects. That variant is not reachable in upstream syntax, which is why this is filed as the wrong-value case.