- Notifications
You must be signed in to change notification settings - Fork664
Total ordering of types#200
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 ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Uh oh!
There was an error while loading.Please reload this page.
Conversation
Uh oh!
There was an error while loading.Please reload this page.
| TypeFlagsVoid TypeFlags = 1 << 14 | ||
| TypeFlagsUndefined TypeFlags = 1 << 15 | ||
| TypeFlagsNull TypeFlags = 1 << 16 | ||
| TypeFlagsUndefined TypeFlags = 1 << 2 |
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.
Hopefully this reordering doesn't make interop too hard (but I understand why it's a good idea here)
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
| return 1 | ||
| } | ||
| // First sort in order of increasing type flags values. | ||
| if c := getSortOrderFlags(t1) - getSortOrderFlags(t2); c != 0 { |
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 seems like it could be acmp.Compare, but, not really a big deal.
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.
Again, I think just subtracting the two ints is about as efficient as it can get.
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.
Certainly, but I was mainly going for clarity.
Uh oh!
There was an error while loading.Please reload this page.
| if t1.readonly != t2.readonly { | ||
| return core.IfElse(t1.readonly, 1, -1) | ||
| } | ||
| if len(t1.elementInfos) != len(t2.elementInfos) { |
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 feel like this would be clearer as ac := cmp.Compare(len(t1.elementInfos), len(t2.elementInfos)); c != 0 { return c } (which I think I'm just saying for most of these manual checks).
Uh oh!
There was an error while loading.Please reload this page.
Latest commit changes the comparison logic to order types first by kind, then by name (when applicable), and finally by declaration order. This makes the ordering less sensitive to source code movement and file renaming. |
internal/compiler/utilities.go Outdated
| func compareTexts(s1, s2 []string) int { | ||
| if len(s1) != len(s2) { | ||
| return len(s1) - len(s2) | ||
| } | ||
| for i, t1 := range s1 { | ||
| if c := strings.Compare(t1, s2[i]); c != 0 { | ||
| return c | ||
| } | ||
| } | ||
| return 0 | ||
| } |
DanielRosenwasserJan 6, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
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 function and the above arealmost the same asslices.Compare, but they differ in that here, a different length short circuits comparing each individual element.
This does, though, mean that something like
`foobar${T}baz`|`xyz${T}xyz`|`foo${T}bar${T}baz`
is considered "sorted" even though a user might prefer to see
`foobar${T}baz`|`foo${T}bar${T}baz`|`xyz${T}xyz`
I think it's worth reconsidering at least for template string types.
internal/compiler/utilities.go Outdated
| // We have unnamed types or types with identical names. Now sort by data specific to the type. | ||
| switch { | ||
| case t1.flags&(TypeFlagsAny|TypeFlagsUnknown|TypeFlagsString|TypeFlagsNumber|TypeFlagsBoolean|TypeFlagsBigInt|TypeFlagsESSymbol|TypeFlagsVoid|TypeFlagsUndefined|TypeFlagsNull|TypeFlagsNever|TypeFlagsNonPrimitive) != 0: | ||
| // Only distinguished by type IDs |
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.
| // Only distinguished by type IDs | |
| // Only distinguished by type IDs, handled below. |
With latest commit we now sort template literal types by their text segments in sequence. |
internal/compiler/utilities.go Outdated
| return 0 | ||
| } | ||
| func compareTexts(s1, s2 []string) int { |
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.
Why not just useslices.Compare?
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.
Also, maybe worth noting in the function why you don't short-circuit on length.
ahejlsberg commentedJan 8, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
With the latest commits, when ordering depends on source positions we compare the indices of the source files in the program's file list instead of comparing file paths. We obtain source file indices using a map (from source file object to index) constructed by the checker. In order to have access to the checker, type objects now carry a reference to the checker that created them. We'll need this reference in the language service anyway, and it allows us to panic on attempts to relate types that didn't originate in the same checker. I verified that the cost of adding this field is less than 0.5% (when compiling VSCode). |
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
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'm not sure I have any other comments at this point; I'm still a little worried about a change in union ordering having a negative effect on our own testing and potentially real breaks, so hopefully we can mitigate that, backport this change to the old TS compiler to see the difference, etc.
(But, I think union ordering may be the least bad ordering change in terms of breaks; the object ordering one may end up worse.)
13d40be intomainUh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
This PR implements a total ordering of types that replaces the previous ordering based on type IDs. The new total ordering depends on type names, declaration order, and/or literal values, but is free of dependencies on type creation order and never requires resolution of constituent types or members. A desirable effect of the new ordering is that in a given program, union type constituents are always ordered (and possibly reduced) the same regardless of when and how the union types are materialized.
I expect there is some performance penalty associated with the new ordering, though it doesn't appear to be significant.
For details on the exact manner in which types are ordered, see the
compareTypesfunctionhere.