GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Control flow based type guards by ivogabe · Pull Request #6959 · microsoft/TypeScript

Conversation

@ivogabe

@ivogabe Ivo Gabe de Wolff (ivogabe) commented Feb 7, 2016

Copy link
Copy Markdown
Contributor

As discussed in #5168, here's my PR that adds flow based type guards. This is still work in process. The compiler can compile itself, but one of the tests doesn't terminate.

Related issues: #1764, #1769, #2388

Here's a quick overview of the approach I took. During binding, every node gets references to flow markers that preceded the node in the control flow. A flow marker is either a type guard or some node, such as an identifier or a while loop. This represents the control flow graph.

In checker.ts, the type of a variable is calculated as the union of the types after the previous occurrences. The type after a node is in case of an assignment narrowed by the assigned type (see below) and otherwise the same as before the node.

At an assignment x = y, where y can be any expression, the following happens. If the type of x is a union type, the constituent parts are filtered. The local type of x will be the union of all constituent parts to which y is assignable. If this yields an empty union type, the initial type of x is used instead. If x is not a union type, the local type after the assignment will be the initial type.

Since the incoming flow of a catch block can come from anywhere in the try block, I decided to fall back to the initial type as a precaution. I can relax that rule if desired, for instance by looking at assignments in the try block.

Todo:

  • Fix test where compiler doesn't terminate
  • Add tests
  • Clean up & comments
  • Fix bug: let x: string | number = "" doesn't narrow to string, but x = "" does.
  • Fix bug: with x = ""; for (;x;) { x; }, narrowing is removed inside the for (because of recursion), but x = ""; for(;;) { x; } works as expected.

~~Questions:

  1. Not every Node has an id property (at runtime it is undefined). Is that correct or a bug? I currently use flowIndex (which I will remove later on) in getPreviousOccurencies, but id would be better.
  2. One test currently doesn't terminate. The process aborts because it's out of memory (even when I increase the old space to 8 GB). Given that the call stack contains createFileDiagnostic, I think the compiler is trying to create an infinite amount of diagnostics.. Does someone have an idea why that's happening?~~

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

HerringtonDarkholme and mquandalle reacted with thumbs up emoji mquandalle reacted with hooray emoji
All reactions
  • 👍 2 reactions
  • 🎉 1 reaction
Ivo Gabe de Wolff (ivogabe) added 20 commits August 15, 2015 17:21
@ivogabe
Merge remote-tracking branch 'Microsoft/master'
42a8efd
@ivogabe
Merge remote-tracking branch 'Microsoft/master'
80f42ed
@ivogabe
Merge branch 'master' of https://github.com/Microsoft/TypeScript
57f5d5c
@ivogabe
Merge remote-tracking branch 'Microsoft/master' into guards
163291f
@ivogabe
Add flow markers to binder
441c999
@ivogabe
Add BranchFlow for type guards
522a99c
Do and for statements not implemented yet
@ivogabe
Add caching of identifier narrowing in binder
78ca7b5
@ivogabe
Implement flow based type guards in checker
1fb2db6
@ivogabe
Narrow assignments to unions only
f1c9a82
@ivogabe
Make isDeclarationName a weak type guard for Identifiers
d3dd1fa
@ivogabe
Remove trailing space
702edac
@ivogabe
Make getNarrowedTypeOfSymbol work on all nodes again
8670014
Instead of only on Identifiers
@ivogabe
Merge remote-tracking branch 'Microsoft/master' into guards
ecbf9e2
@ivogabe
Merge remote-tracking branch 'Microsoft/master' into guards
c1abed2
@ivogabe
Bind flow of loops and named labels
905a240
@ivogabe
Fix flow based type guards in checker
b8c0e2c
@ivogabe
Merge remote-tracking branch 'Microsoft/master' into guards
f6dc119
# Conflicts:
#	src/compiler/binder.ts
#	src/compiler/checker.ts
@ivogabe
Fix errors after merge
b385472
@ivogabe
Remove restriction on type narrowing with assignments in loops
6f1d84e
@ivogabe
Fix assignment checking
ffa8db3
@msftclas Microsoft Contribution License Agreements (msftclas) added the cla-already-signed label Feb 7, 2016
This was referenced Feb 7, 2016
Thesis on improved type system #5168
Closed
Use control flow analysis for type guards #2388
Closed
Support assignment in typeguard if block #1769
Closed
Type narrowing is not allowed if variable is reassigned after the use site inside if block #1764
Closed
@weswigham

Wesley Wigham (weswigham) commented Feb 7, 2016

Copy link
Copy Markdown
Member
  1. Not every Node has an id property (at runtime it is undefined). Is that correct or a bug? I currently use flowIndex (which I will remove later on) in getPreviousOccurencies, but id would be better.

Use the function getNodeId to get node id's - if the node has yet to be assigned one, this function assigns it one.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

weswigham
weswigham reviewed Feb 7, 2016
View reviewed changes
Comment thread src/compiler/utilities.ts

// True if the given identifier, string literal, or number literal is the name of a declaration node
export function isDeclarationName(name: Node): name is Identifier | StringLiteral | LiteralExpression {
export function isDeclarationName(name: Node): name is (Identifier & { __weakTypeGuard: void; }) | StringLiteral | LiteralExpression {

@weswigham Wesley Wigham (weswigham) Feb 7, 2016

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't see this brand applied anywhere - is there a reason for this?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@ivogabe Ivo Gabe de Wolff (ivogabe) Feb 8, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If a type guard returns false, it is expected that the argument is not of the specified type. However, isDeclarationName can return false when name is an identifier. This wasn't an issue, as isDeclarationName was never used in an if statement with an else. However, with control flow based type guards, this wasn't working anymore. The then-block of an if statement contained a return, thus the statements after the if were the else branch of the if. It might not be the best way to solve this, but it's working..

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@weswigham

Wesley Wigham (weswigham) commented Feb 8, 2016

Copy link
Copy Markdown
Member

After a bit of sniffing with your code, I think the (or one of the?) test(s) which hangs is tests/cases/conformance/parser/ecmascript5/parserRealSource7.ts (which I think is a chunk of code form the original compiler). The preCollectFuncDeclTypes function within the file is enough (on its own) to make the test hit the memory ceiling. It seems to spend a lot of cycles re-narrowing the ast cast-and-assignment-to-funcDecl in that function (and in some other places, too).

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

weswigham
weswigham reviewed Feb 8, 2016
View reviewed changes
Comment thread src/compiler/checker.ts Outdated
}
}

interface PreviousOccurency {

@weswigham Wesley Wigham (weswigham) Feb 8, 2016

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This type isn't used anywhere, AFAIK.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@ivogabe Ivo Gabe de Wolff (ivogabe) Feb 8, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You're right, I forgot to remove it during refactoring.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@ivogabe
Remove flowIndex, use getNodeId
844a8c1
Ivo Gabe de Wolff (ivogabe) added 19 commits March 13, 2016 20:20
@ivogabe
Merge remote-tracking branch 'Microsoft/master' into guards
8d4cea4
@ivogabe
Fix narrowing of JSX tags
c128582
They caused infinite recursion without this change
@ivogabe
Use initial type when narrowing resulted in empty type
19b3f90
@ivogabe
Move narrowing info from node to NodeLinks
59b543f
@ivogabe
Allow narrowing in nested functions
c0061c0
@ivogabe
Narrow after destructuring assignments with initializers
096c70a
@ivogabe
Merge remote-tracking branch 'Microsoft/master' into guards
fa77df5
@ivogabe
Fix narrowing in for of statement
46786b3
@ivogabe
Stop narrowing with guards that contain assignments
3a7575b
@ivogabe
Add control flow tests
b9f5b79
@ivogabe
Add test for narrowing after assignment
21efd00
@ivogabe
Modify existing tests for new type guards behavior
d5fbd4e
@ivogabe
Add more tests
f8a1827
@ivogabe
Remove redundant bindFlowMarker calls
7cceb0c
@ivogabe
Fix tests
bea32e2
@ivogabe
Accept baseline
a659239
@ivogabe
Merge remote-tracking branch 'Microsoft/master' into guards
9e13d0f
@ivogabe
Update tests
3490979
@ivogabe
Merge remote-tracking branch 'Microsoft/master' into guards
a719858
# Conflicts:
#	src/compiler/checker.ts
#	tests/baselines/reference/assignmentCompatability3.symbols
@weswigham Wesley Wigham (weswigham) mentioned this pull request Mar 22, 2016
strictNullChecks thinks a value may be null if null is assigned to it in its non-null branch #7630
Closed
Ivo Gabe de Wolff (ivogabe) added 3 commits March 23, 2016 19:44
@ivogabe
Implement flow based type guards for this expression and dotted names
90a678d
@ivogabe
Fix unresolved symbols, wrong caching and empty type issues
7646af1
@ivogabe
Accept new baselines
4a76fe2
@ivogabe

Ivo Gabe de Wolff (ivogabe) commented Mar 23, 2016

Copy link
Copy Markdown
Contributor Author

It took a while, but I think most things are working now. I have updated the PR for the dotted names type guards and this type guards. null and undefined worked without extra work. I haven't used the control flow graph for variable assignment checking, but that can be easily added later on.

I think that two minor problems: handling of a try/catch block and getTypeOfSymbolAtLocation. After a try/catch, narrowing breaks and types of variables are set to their initial types. Better would be to use the type before the try if the variable is not assigned within the try, otherwise the initial type; or to take the union of the type before the try with all types of assignments in the try/catch.

The following code compiles, but gives the wrong type in VSCode, with this custom build. When I hover the last x, it says string | number. I suspect this has something to do with getTypeOfSymbolAtLocation, but I'm not sure what's happening. This seems to fail with double type guards. The tests show this too, in tests/baselines/reference/typeGuardsInIfStatement.types.

let x: string | boolean | number;
if (typeof x === "string") {}
else if (typeof x === "boolean") {}
else x.toExponential;

Since most work has been finished, can someone review my code?

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@ivogabe
Stop narrowing of dotted name after assignment of parent type
16555dd
@jods4

jods (jods4) commented Mar 23, 2016

Copy link
Copy Markdown

For try...catch and try..finally it's very useful to keep the narrowed type of symbols that do not change type in the block, including those that are assigned, so that the following works:

let x: number | null;
x = 4; // from here x: number
try {
  x = 7;
  throw new Error();
} 
finally {
  x.toString(); // <-- should be ok, it would be annoying if x reverts to number|null
}

For symbols, which change type inside the block I am unsure whether it's worth the effort. The union of all their types across the block would be correct but it can get hard to reason about, for IMHO little benefit. I think reverting to their initial type would be OK for a first release, it can always be improved later if people have motivating examples of code where it would be nice.

mquandalle reacted with thumbs up emoji
All reactions
  • 👍 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@ahejlsberg Anders Hejlsberg (ahejlsberg) mentioned this pull request Apr 11, 2016
Control flow based type analysis #8010
Merged
@mhegazy

Mohamed Hegazy (mhegazy) commented Apr 22, 2016

Copy link
Copy Markdown
Contributor

this functionality should be handled by #8010.

Big thanks to Ivo Gabe de Wolff (@ivogabe) for sharing this work. it has been the inspiration and guide for the work in #8010. thanks again Ivo Gabe de Wolff (@ivogabe)!

mquandalle and DanielRosenwasser reacted with hooray emoji
All reactions
  • 🎉 2 reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@mhegazy Mohamed Hegazy (mhegazy) closed this Apr 22, 2016
@microsoft Microsoft (microsoft) locked and limited conversation to collaborators Jun 19, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Reviewers

No reviews

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

7 participants

@ivogabe @weswigham @ahejlsberg @jods4 @mhegazy @DanielRosenwasser @msftclas
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.