Issue #22294 has been reported by make_now_just (Hiroya Fujinami). ---------------------------------------- Bug #22294: Parsing a long && / || chain is quadratic https://bugs.ruby-lang.org/issues/22294 * Author: make_now_just (Hiroya Fujinami) * Status: Open * Target version: 4.0 * ruby -v: ruby 4.0.4 (2026-05-12 revision b89eb1bcbf) +PRISM [arm64-darwin25] * Backport: 3.3: UNKNOWN, 3.4: UNKNOWN, 4.0: UNKNOWN ---------------------------------------- Parsing a long chain of short-circuit logical operators (`&&`, `||`, `and`, `or`) takes time that is quadratic in the chain's length. It affects both parsers, parse.y and Prism. ## Reproduction ```ruby require "prism" def bench(label) puts label [2000, 4000, 8000, 16000].each do |n| src = "a" + " && a" * n started = Process.clock_gettime(Process::CLOCK_MONOTONIC) yield src elapsed = Process.clock_gettime(Process::CLOCK_MONOTONIC) - started puts format(" n=%-6d %8.1f ms", n, elapsed * 1000) end end bench("parse.y") { |src| RubyVM::AbstractSyntaxTree.parse(src) } bench("Prism") { |src| Prism.parse(src) } ``` Output on ruby 4.0.4 (arm64-darwin); the time roughly quadruples each time the length doubles: ``` parse.y n=2000 5.7 ms n=4000 22.9 ms n=8000 82.4 ms n=16000 277.0 ms Prism n=2000 4.9 ms n=4000 24.0 ms n=8000 98.5 ms n=16000 368.9 ms ``` `||` / `and` / `or` behave the same. Method chains (`a.b.c...`) and arithmetic (`a + a + ...`) are linear; only the short-circuit logical operators are affected. ## Cause - **parse.y** `logop()`: flattens the left-associative chain into a right-leaning tree, finding the insertion point by walking the whole right branch on every operator (O(n) per operator). - **Prism** `pm_check_value_expression()`: the check descends the left branch of the and/or node (O(n) per operator). ## Note Compiling such chains has a similar issue in the peephole optimizer, which is independent of this parsing issue. -- https://bugs.ruby-lang.org/