Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Nullability rewriter is O(2^n) when visiting converted tuple literals #36880

Open
gafter opened this issue Jun 28, 2019 · 1 comment
Open

Nullability rewriter is O(2^n) when visiting converted tuple literals #36880

gafter opened this issue Jun 28, 2019 · 1 comment
Labels
Area-Compilers Bug Concept-Design Debt Engineering Debt, Design Debt, or poor product code quality New Language Feature - Nullable Reference Types Nullable Reference Types
Milestone

Comments

@gafter
Copy link
Member

gafter commented Jun 28, 2019

The generated Nullability rewriter contains a method that begins

        public override BoundNode VisitConvertedTupleLiteral(BoundConvertedTupleLiteral node)
        {
            BoundTupleLiteral sourceTuple = (BoundTupleLiteral)this.Visit(node.SourceTuple);
            ImmutableArray<BoundExpression> arguments = this.VisitList(node.Arguments);

The bound trees in node.Arguments share part of the expression tree with node.SourceTuple. Consequently, they will be visited twice. When tuples are nested n deep, nodes at the leaves will be visited O(2n) times.

We want to avoid repeated visits of a given node, so this needs to be revised.

/cc @chsienki

@jcouv jcouv added this to the Compiler.Next milestone Jul 8, 2019
@gafter gafter added the Concept-Design Debt Engineering Debt, Design Debt, or poor product code quality label Jul 12, 2019
@gafter
Copy link
Member Author

gafter commented Jul 12, 2019

I believe the "original tuple" is not needed. However, the "natural (unconverted) type" of the tuple is needed.

@jaredpar jaredpar modified the milestones: Compiler.Next, Backlog Sep 12, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Area-Compilers Bug Concept-Design Debt Engineering Debt, Design Debt, or poor product code quality New Language Feature - Nullable Reference Types Nullable Reference Types
Projects
None yet
Development

No branches or pull requests

3 participants