Skip to content

isNullable is exponential in certain degenerate cases #25

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

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions