Total ordering of types (#200)

ahejlsberg · web-flow · commit 13d40be62fe1 · 2025-01-08T13:45:08.000-08:00
diff --git a/internal/ast/ast.go b/internal/ast/ast.go
@@ -5654,14 +5654,14 @@ type SourceFile struct {
 	IsDeclarationFile           bool
 	IsBound                     bool
 	ModuleReferencesProcessed   bool
+	HasNoDefaultLib             bool
 	UsesUriStyleNodeCoreModules core.Tristate
 	SymbolCount                 int
 	ClassifiableNames           core.Set[string]
 	Imports                     []*LiteralLikeNode // []LiteralLikeNode
 	ModuleAugmentations         []*ModuleName      // []ModuleName
 	PatternAmbientModules       []PatternAmbientModule
 	AmbientModuleNames          []string
-	HasNoDefaultLib             bool
 	jsdocCache                  map[*Node][]*Node
 	Pragmas                     []Pragma
 	ReferencedFiles             []*FileReference
diff --git a/internal/ast/utilities.go b/internal/ast/utilities.go
@@ -821,15 +821,13 @@ func WalkUpParenthesizedTypes(node *TypeNode) *Node {
 
 // Walks up the parents of a node to find the containing SourceFile
 func GetSourceFileOfNode(node *Node) *SourceFile {
-	for {
-		if node == nil {
-			return nil
-		}
-		if node.Kind == KindSourceFile {
-			return node.AsSourceFile()
-		}
+	for node.Parent != nil {
 		node = node.Parent
 	}
+	if node.Kind == KindSourceFile {
+		return node.AsSourceFile()
+	}
+	return nil
 }
 
 // Walks up the parents of a node to find the ancestor that matches the callback
diff --git a/internal/compiler/checker.go b/internal/compiler/checker.go
@@ -487,6 +487,8 @@ type Checker struct {
 	host                                    CompilerHost
 	compilerOptions                         *core.CompilerOptions
 	files                                   []*ast.SourceFile
+	fileIndexMap                            map[*ast.SourceFile]int
+	compareSymbols                          func(*ast.Symbol, *ast.Symbol) int
 	typeCount                               uint32
 	symbolCount                             uint32
 	totalInstantiationCount                 uint32
@@ -733,6 +735,8 @@ func NewChecker(program *Program) *Checker {
 	c.host = program.host
 	c.compilerOptions = program.compilerOptions
 	c.files = program.files
+	c.fileIndexMap = createFileIndexMap(c.files)
+	c.compareSymbols = c.compareSymbolsWorker // Closure optimization
 	c.languageVersion = c.compilerOptions.GetEmitScriptTarget()
 	c.moduleKind = c.compilerOptions.GetEmitModuleKind()
 	c.legacyDecorators = c.compilerOptions.ExperimentalDecorators == core.TSTrue
@@ -863,7 +867,7 @@ func NewChecker(program *Program) *Checker {
 	c.emptyStringType = c.getStringLiteralType("")
 	c.zeroType = c.getNumberLiteralType(0)
 	c.zeroBigIntType = c.getBigIntLiteralType(PseudoBigInt{negative: false, base10Value: "0"})
-	c.typeofType = c.getUnionType(core.Map(slices.Collect(maps.Keys(typeofNEFacts)), c.getStringLiteralType))
+	c.typeofType = c.getUnionType(core.Map(slices.Sorted(maps.Keys(typeofNEFacts)), c.getStringLiteralType))
 	c.flowLoopCache = make(map[FlowLoopKey]*Type)
 	c.flowNodeReachable = make(map[*ast.FlowNode]bool)
 	c.flowNodePostSuper = make(map[*ast.FlowNode]bool)
@@ -904,6 +908,14 @@ func NewChecker(program *Program) *Checker {
 	return c
 }
 
+func createFileIndexMap(files []*ast.SourceFile) map[*ast.SourceFile]int {
+	result := make(map[*ast.SourceFile]int, len(files))
+	for i, file := range files {
+		result[file] = i
+	}
+	return result
+}
+
 func (c *Checker) reportUnreliableWorker(t *Type) *Type {
 	if c.outofbandVarianceMarkerHandler != nil && (t == c.markerSuperType || t == c.markerSubType || t == c.markerOtherType) {
 		c.outofbandVarianceMarkerHandler(true /*onlyUnreliable*/)
@@ -15110,7 +15122,7 @@ func (c *Checker) getNamedMembers(members ast.SymbolTable) []*ast.Symbol {
 			result = append(result, symbol)
 		}
 	}
-	sortSymbols(result)
+	c.sortSymbols(result)
 	return result
 }
 
@@ -17862,6 +17874,7 @@ func (c *Checker) newType(flags TypeFlags, objectFlags ObjectFlags, data TypeDat
 	t.flags = flags
 	t.objectFlags = objectFlags &^ (ObjectFlagsCouldContainTypeVariablesComputed | ObjectFlagsCouldContainTypeVariables | ObjectFlagsMembersResolved)
 	t.id = TypeId(c.typeCount)
+	t.checker = c
 	t.data = data
 	return t
 }
@@ -18602,14 +18615,7 @@ func (c *Checker) addTypeToUnion(typeSet []*Type, includes TypeFlags, t *Type) (
 				includes |= TypeFlagsIncludesNonWideningType
 			}
 		} else {
-			var index int
-			var ok bool
-			if len(typeSet) != 0 && t.id > typeSet[len(typeSet)-1].id {
-				index = len(typeSet)
-			} else {
-				index, ok = slices.BinarySearchFunc(typeSet, t, compareTypeIds)
-			}
-			if !ok {
+			if index, ok := slices.BinarySearchFunc(typeSet, t, compareTypes); !ok {
 				typeSet = slices.Insert(typeSet, index, t)
 			}
 		}
@@ -19351,12 +19357,12 @@ func (c *Checker) removeType(t *Type, targetType *Type) *Type {
 }
 
 func containsType(types []*Type, t *Type) bool {
-	_, ok := slices.BinarySearchFunc(types, t, compareTypeIds)
+	_, ok := slices.BinarySearchFunc(types, t, compareTypes)
 	return ok
 }
 
 func insertType(types []*Type, t *Type) ([]*Type, bool) {
-	if i, ok := slices.BinarySearchFunc(types, t, compareTypeIds); !ok {
+	if i, ok := slices.BinarySearchFunc(types, t, compareTypes); !ok {
 		return slices.Insert(types, i, t), true
 	}
 	return types, false
diff --git a/internal/compiler/mapper.go b/internal/compiler/mapper.go
@@ -2,18 +2,31 @@ package compiler
 
 import "github.com/microsoft/typescript-go/internal/core"
 
+// TypeMapperKind
+
+type TypeMapperKind int32
+
+const (
+	TypeMapperKindUnknown TypeMapperKind = iota
+	TypeMapperKindSimple
+	TypeMapperKindArray
+	TypeMapperKindMerged
+)
+
 // TypeMapper
 
 type TypeMapper struct {
 	data TypeMapperData
 }
 
-func (m *TypeMapper) Map(t *Type) *Type { return m.data.Map(t) }
+func (m *TypeMapper) Map(t *Type) *Type    { return m.data.Map(t) }
+func (m *TypeMapper) Kind() TypeMapperKind { return m.data.Kind() }
 
 // TypeMapperData
 
 type TypeMapperData interface {
 	Map(t *Type) *Type
+	Kind() TypeMapperKind
 }
 
 // Factory functions
@@ -70,10 +83,19 @@ func (c *Checker) newBackreferenceMapper(context *InferenceContext, index int) *
 	return newArrayToSingleTypeMapper(typeParameters, c.unknownType)
 }
 
+// TypeMapperBase
+
+type TypeMapperBase struct {
+	TypeMapper
+}
+
+func (m *TypeMapperBase) Map(t *Type) *Type    { return t }
+func (m *TypeMapperBase) Kind() TypeMapperKind { return TypeMapperKindUnknown }
+
 // SimpleTypeMapper
 
 type SimpleTypeMapper struct {
-	TypeMapper
+	TypeMapperBase
 	source *Type
 	target *Type
 }
@@ -93,10 +115,14 @@ func (m *SimpleTypeMapper) Map(t *Type) *Type {
 	return t
 }
 
+func (m *SimpleTypeMapper) Kind() TypeMapperKind {
+	return TypeMapperKindSimple
+}
+
 // ArrayTypeMapper
 
 type ArrayTypeMapper struct {
-	TypeMapper
+	TypeMapperBase
 	sources []*Type
 	targets []*Type
 }
@@ -118,10 +144,14 @@ func (m *ArrayTypeMapper) Map(t *Type) *Type {
 	return t
 }
 
+func (m *ArrayTypeMapper) Kind() TypeMapperKind {
+	return TypeMapperKindArray
+}
+
 // ArrayToSingleTypeMapper
 
 type ArrayToSingleTypeMapper struct {
-	TypeMapper
+	TypeMapperBase
 	sources []*Type
 	target  *Type
 }
@@ -146,7 +176,7 @@ func (m *ArrayToSingleTypeMapper) Map(t *Type) *Type {
 // DeferredTypeMapper
 
 type DeferredTypeMapper struct {
-	TypeMapper
+	TypeMapperBase
 	sources []*Type
 	targets []func() *Type
 }
@@ -171,7 +201,7 @@ func (m *DeferredTypeMapper) Map(t *Type) *Type {
 // FunctionTypeMapper
 
 type FunctionTypeMapper struct {
-	TypeMapper
+	TypeMapperBase
 	fn func(*Type) *Type
 }
 
@@ -189,7 +219,7 @@ func (m *FunctionTypeMapper) Map(t *Type) *Type {
 // MergedTypeMapper
 
 type MergedTypeMapper struct {
-	TypeMapper
+	TypeMapperBase
 	m1 *TypeMapper
 	m2 *TypeMapper
 }
@@ -206,10 +236,14 @@ func (m *MergedTypeMapper) Map(t *Type) *Type {
 	return m.m2.Map(m.m1.Map(t))
 }
 
+func (m *MergedTypeMapper) Kind() TypeMapperKind {
+	return TypeMapperKindMerged
+}
+
 // CompositeTypeMapper
 
 type CompositeTypeMapper struct {
-	TypeMapper
+	TypeMapperBase
 	c  *Checker
 	m1 *TypeMapper
 	m2 *TypeMapper
@@ -235,7 +269,7 @@ func (m *CompositeTypeMapper) Map(t *Type) *Type {
 // InferenceTypeMapper
 
 type InferenceTypeMapper struct {
-	TypeMapper
+	TypeMapperBase
 	c      *Checker
 	n      *InferenceContext
 	fixing bool
diff --git a/internal/compiler/printer.go b/internal/compiler/printer.go
@@ -116,6 +116,7 @@ func (p *Printer) printType(t *Type) {
 }
 
 func (p *Printer) printTypeNoAlias(t *Type) {
+	p.depth++
 	switch {
 	case t.flags&TypeFlagsIntrinsic != 0:
 		p.print(t.AsIntrinsicType().intrinsicName)
@@ -142,14 +143,13 @@ func (p *Printer) printTypeNoAlias(t *Type) {
 	case t.flags&TypeFlagsSubstitution != 0:
 		p.printType(t.AsSubstitutionType().baseType)
 	}
+	p.depth--
 }
 
 func (p *Printer) printRecursive(t *Type, f func(*Printer, *Type)) {
 	if !p.printing.Has(t) && p.depth < 10 {
 		p.printing.Add(t)
-		p.depth++
 		f(p, t)
-		p.depth--
 		p.printing.Delete(t)
 	} else {
 		p.print("???")
@@ -286,22 +286,37 @@ func (p *Printer) printTupleType(t *Type) {
 	tail := false
 	p.print("[")
 	elementInfos := t.TargetTupleType().elementInfos
-	for i, t := range p.c.getTypeArguments(t) {
+	typeArguments := p.c.getTypeArguments(t)
+	for i, info := range elementInfos {
+		t := typeArguments[i]
 		if tail {
 			p.print(", ")
 		}
-		info := elementInfos[i]
 		if info.flags&ElementFlagsVariable != 0 {
 			p.print("...")
 		}
-		if info.flags&ElementFlagsOptional != 0 {
-			p.printTypeEx(t, ast.TypePrecedencePostfix)
-			p.print("?")
-		} else if info.flags&ElementFlagsRest != 0 {
-			p.printTypeEx(t, ast.TypePrecedencePostfix)
-			p.print("[]")
+		if info.labeledDeclaration != nil {
+			p.print(info.labeledDeclaration.Name().Text())
+			if info.flags&ElementFlagsOptional != 0 {
+				p.print("?")
+			}
+			p.print(": ")
+			if info.flags&ElementFlagsRest != 0 {
+				p.printTypeEx(t, ast.TypePrecedencePostfix)
+				p.print("[]")
+			} else {
+				p.printType(t)
+			}
 		} else {
-			p.printType(t)
+			if info.flags&ElementFlagsOptional != 0 {
+				p.printTypeEx(t, ast.TypePrecedencePostfix)
+				p.print("?")
+			} else if info.flags&ElementFlagsRest != 0 {
+				p.printTypeEx(t, ast.TypePrecedencePostfix)
+				p.print("[]")
+			} else {
+				p.printType(t)
+			}
 		}
 		tail = true
 	}
diff --git a/internal/compiler/types.go b/internal/compiler/types.go
diff --git a/internal/compiler/utilities.go b/internal/compiler/utilities.go
