Bug #22294: Parsing a long && / || chain is quadratic

• Status: Open
• Assignee: -
• 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
• Tags: parser

[make_now_just (Hiroya Fujinami)]

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

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.

[make_now_just (Hiroya Fujinami)]

I crated a pull request for each repo:

• https://github.com/ruby/ruby/pull/18638
• https://github.com/ruby/prism/pull/4221