Skip to content

isNullable is exponential in certain degenerate cases #25

@djspiewak

Description

@djspiewak
lazy val a = b | b
lazy val b = c | c
lazy val c = d | d
// ...
lazy val z = a | a

Example courtesy of Michael Adams. I'm pretty sure this requires 2^26 operations to compute, since tracked is unshared between branches. Unfortunately, the fix is not as simple as extracting tracked to be shared by both branches, since doing so will cause nodes to not be revisited when their values have been subsequently determined. An example of where naive extraction will fail:

lazy val a: Parser[Any] = b ~ c
lazy val b: Parser[Any] = c | () ^^^ ""
lazy val c: Parser[Any] = b | "x"

a.isNullable must beTrue

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions