Skip to content

Commit c5b3bb3

Browse files
author
Markus
committed
fix(workflows): evaluate long and/or chains without exhausting the stack
The Lark engine built its AST with Lark's recursive Transformer, which uses about two Python frames per tree level, and nested `a or b or c` as `((a or b) or c)`. Building, evaluating and validating the tree all recursed once per operator, so a condition of about 500 terms or 500 nested parentheses raised RecursionError. That includes `true or ...`, which the former engine returned after its first operand, and the validation of a bare condition of that length, which raised instead of reporting the missing braces. Build the AST with Transformer_NonRecursive and flatten each and/or chain into one node, as filter chains already are. Evaluation loops over the operands and stops at the first one that decides the result; validation visits all of them. Chains and parentheses no longer depend on the recursion limit (tested to 5,000). `not` chains, comparison chains and nested lists keep the former engine's limit of about 1,000 levels. Assisted-by: Pi Coding Agent (model: claude-opus-5.5, autonomous)
1 parent a9fe9f7 commit c5b3bb3

3 files changed

Lines changed: 73 additions & 26 deletions

File tree

‎src/specify_cli/workflows/expressions/engine.py‎

Lines changed: 31 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@
4444
from functools import lru_cache
4545
from typing import Any
4646

47-
from lark import Lark, Token, Transformer, Tree, v_args
47+
from lark import Lark, Token, Transformer_NonRecursive, Tree, v_args
4848
from lark.exceptions import UnexpectedCharacters, UnexpectedInput, UnexpectedToken, VisitError
4949

5050
from . import namespace
@@ -185,12 +185,15 @@ def _parser() -> Lark:
185185

186186

187187
@v_args(inline=True)
188-
class _BuildAst(Transformer):
189-
"""Turn the parse tree into the same kind of tuples the other engines walk.
190-
191-
One small method per grammar rule; aliases (``-> cmp``, ``-> filter_call``)
192-
name the shape, and anonymous terminals (``"|"``, ``"("``, ``","``) are
193-
filtered out by Lark, so the children are exactly the operands.
188+
class _BuildAst(Transformer_NonRecursive):
189+
"""Turn the parse tree into the tuple AST that ``_eval`` and ``_visit`` walk.
190+
191+
Non-recursive, and each ``and``/``or`` chain becomes one node, so a long
192+
chain or deep parentheses do not exhaust Python's call stack while the tree
193+
is built, evaluated or validated. One small method per grammar rule;
194+
aliases (``-> cmp``, ``-> filter_call``) name the shape, and anonymous
195+
terminals (``"|"``, ``"("``, ``","``) are filtered out by Lark, so the
196+
children are exactly the operands.
194197
"""
195198

196199
def string(self, token: Token) -> tuple[str, str]:
@@ -227,11 +230,15 @@ def filtered(self, head: Any, filt: Any) -> tuple[str, Any, tuple[Any, ...]]:
227230
def cmp(self, left: Any, op: Token, right: Any) -> tuple[str, ...]:
228231
return ("cmp", " ".join(str(op).split()), left, right)
229232

230-
def or_op(self, left: Any, _op: Token, right: Any) -> tuple[str, Any, Any]:
231-
return ("or", left, right)
233+
def or_op(self, left: Any, _op: Token, right: Any) -> tuple[str, tuple[Any, ...]]:
234+
# As for ``filtered``: the grammar nests a chain to the left; flatten it
235+
# so ``_eval`` loops over the operands instead of recursing per operator.
236+
operands = left[1] if left[0] == "or" else (left,)
237+
return ("or", operands + (right,))
232238

233-
def and_op(self, left: Any, _op: Token, right: Any) -> tuple[str, Any, Any]:
234-
return ("and", left, right)
239+
def and_op(self, left: Any, _op: Token, right: Any) -> tuple[str, tuple[Any, ...]]:
240+
operands = left[1] if left[0] == "and" else (left,)
241+
return ("and", operands + (right,))
235242

236243
def not_op(self, _op: Token, inner: Any) -> tuple[str, Any]:
237244
return ("not", inner)
@@ -433,18 +440,16 @@ def _eval(node: Any, namespace_: dict[str, Any]) -> Any:
433440
return _safe_membership(left, right, negate=True)
434441
return _safe_compare(left, right, op)
435442

436-
left = _eval(node[1], namespace_)
437-
# Skip the right operand when the left one decides, so a guard protects it.
438-
# Validation walks the parse tree instead, so it still visits both sides.
439-
if tag == "or" and bool(left):
440-
return True
441-
if tag == "and" and not bool(left):
442-
return False
443-
right = _eval(node[2], namespace_)
444-
if tag == "or":
445-
return bool(left) or bool(right)
446-
if tag == "and":
447-
return bool(left) and bool(right)
443+
if tag in ("and", "or"):
444+
# Left to right, stopping at the first operand that decides the result,
445+
# so a guard protects the rest: a true operand decides `or`, a false one
446+
# `and`. Validation walks the parse tree instead, so it still visits
447+
# every operand.
448+
decides = tag == "or"
449+
for operand in node[1]:
450+
if bool(_eval(operand, namespace_)) is decides:
451+
return decides
452+
return not decides
448453
raise ValueError(f"unsupported expression node {tag!r}")
449454

450455

@@ -521,7 +526,7 @@ def _visit(node: Any, paths: list[str] | None = None, filters: list[Any] | None
521526
522527
One traversal serves both contract primitives: ``_collect_leaves`` asks for
523528
the names (``paths``), ``_evaluator_rejects`` asks for the filters to check
524-
against the table (``filters``). Parents are transparent -- both sides of
529+
against the table (``filters``). Parents are transparent -- every operand of
525530
``and``/``or``, every list element and every filter argument is reached.
526531
Text that does not parse has neither names nor filters; ``_syntax_error``
527532
explains why separately.
@@ -544,8 +549,8 @@ def _visit(node: Any, paths: list[str] | None = None, filters: list[Any] | None
544549
elif tag == "not":
545550
_visit(node[1], paths, filters)
546551
elif tag in ("and", "or"):
547-
_visit(node[1], paths, filters)
548-
_visit(node[2], paths, filters)
552+
for operand in node[1]:
553+
_visit(operand, paths, filters)
549554
elif tag == "cmp":
550555
_visit(node[2], paths, filters)
551556
_visit(node[3], paths, filters)

‎tests/test_workflows.py‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -416,6 +416,38 @@ def test_boolean_required_operand_still_raises(self, expression):
416416
"{{ " + expression + " }}", StepContext(inputs={"payload": ""})
417417
)
418418

419+
def test_long_boolean_chains_and_deep_parentheses_evaluate(self):
420+
"""A long ``and``/``or`` chain or deep parentheses must not exhaust the
421+
call stack. A chain stops at the first deciding operand, so the failing
422+
operands after it are never evaluated."""
423+
from specify_cli.workflows.expressions import evaluate_expression
424+
from specify_cli.workflows.base import StepContext
425+
426+
ctx = StepContext(inputs={"flag": True, "payload": ""})
427+
count = 1000
428+
failing = "(inputs.payload | from_json)"
429+
assert evaluate_expression(
430+
"{{ true or " + " or ".join([failing] * count) + " }}", ctx
431+
) is True
432+
assert evaluate_expression(
433+
"{{ false and " + " and ".join([failing] * count) + " }}", ctx
434+
) is False
435+
assert evaluate_expression(
436+
"{{ " + " or ".join(["false"] * count) + " or inputs.flag }}", ctx
437+
) is True
438+
assert evaluate_expression(
439+
"{{ " + " and ".join(["inputs.flag"] * count) + " }}", ctx
440+
) is True
441+
assert evaluate_expression(
442+
"{{ " + "(" * count + "inputs.flag" + ")" * count + " }}", ctx
443+
) is True
444+
# An operand the chain reaches still fails the evaluation.
445+
with pytest.raises(ValueError, match="from_json: invalid JSON"):
446+
evaluate_expression(
447+
"{{ " + " or ".join(["false"] * count) + " or " + failing + " }}",
448+
ctx,
449+
)
450+
419451
def test_list_literal_preserves_quoted_commas(self):
420452
from specify_cli.workflows.expressions import evaluate_expression
421453
from specify_cli.workflows.base import StepContext

‎tests/unit/test_condition_expression_block.py‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1007,6 +1007,16 @@ def test_both_sides_of_a_boolean_are_reported():
10071007
assert _unresolvable_term("false and bogus") is not None
10081008

10091009

1010+
def test_a_long_boolean_chain_is_validated_without_exhausting_the_stack():
1011+
"""Validation walks every operand of a long chain, the last one included."""
1012+
chain = " or ".join(["inputs.flag"] * 1000)
1013+
assert len(_collect_leaves(chain)) == 1000
1014+
assert _unresolvable_term(chain + " or bogus") is not None
1015+
errors = IfThenStep().validate({"id": "s1", "condition": chain, "then": []})
1016+
assert len(errors) == 1
1017+
assert "Wrap the expression" in errors[0]
1018+
1019+
10101020
@pytest.mark.parametrize("template", ["true or ({})", "false and ({})", "true or (false and ({}))"])
10111021
@pytest.mark.parametrize("filtered", ["inputs.x | nosuchfilter", "inputs.x | join", "inputs.x | length(1)"])
10121022
def test_filter_probe_checks_short_circuited_operands(template, filtered):

0 commit comments

Comments
 (0)