From 57362e98140bdb964d05017690fb0aba37af6b48 Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Mon, 3 Nov 2025 16:54:43 -0800 Subject: [PATCH] go/types, types2: check for direct cycles as a separate phase A direct cycle is the most basic form of cycle, where no type literal or predeclared type is reached. It is formed by a series of only TypeNames. To illustrate, type T T is a direct cycle, but type T [1]T and type T *T are not. Likewise, the below is also a direct cycle: type A B type B C type C = A Direct cycles are handled explicitly as part of resolveUnderlying, since they are the only cycle which can prevent reaching an underlying type. If we move this check to an earlier compiler phase, we can simplify resolveUnderlying. This is the first of (hopefully) several cycle kinds to be moved into a preliminary phase, with the goal of simplifying the main type-checking pass. For that reason, the bulk of the logic is placed in cycles.go. CL based on an earlier version by Mark Freeman. Change-Id: I3044c383278deb6acb8767c498d8cb68099ba8ef Reviewed-on: https://go-review.googlesource.com/c/go/+/717343 Auto-Submit: Robert Griesemer Reviewed-by: Mark Freeman Reviewed-by: Robert Griesemer LUCI-TryBot-Result: Go LUCI --- src/cmd/compile/internal/types2/check.go | 3 + src/cmd/compile/internal/types2/cycles.go | 105 ++++++++++++++++++++++ src/cmd/compile/internal/types2/named.go | 35 ++++---- src/go/types/check.go | 3 + src/go/types/cycles.go | 105 ++++++++++++++++++++++ src/go/types/named.go | 35 ++++---- 6 files changed, 248 insertions(+), 38 deletions(-) create mode 100644 src/cmd/compile/internal/types2/cycles.go create mode 100644 src/go/types/cycles.go diff --git a/src/cmd/compile/internal/types2/check.go b/src/cmd/compile/internal/types2/check.go index 77c59451fd..25cda4f73d 100644 --- a/src/cmd/compile/internal/types2/check.go +++ b/src/cmd/compile/internal/types2/check.go @@ -497,6 +497,9 @@ func (check *Checker) checkFiles(files []*syntax.File) { print("== sortObjects ==") check.sortObjects() + print("== directCycles ==") + check.directCycles() + print("== packageObjects ==") check.packageObjects() diff --git a/src/cmd/compile/internal/types2/cycles.go b/src/cmd/compile/internal/types2/cycles.go new file mode 100644 index 0000000000..fa739a2b84 --- /dev/null +++ b/src/cmd/compile/internal/types2/cycles.go @@ -0,0 +1,105 @@ +// Copyright 2025 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package types2 + +import "cmd/compile/internal/syntax" + +// directCycles searches for direct cycles among package level type declarations. +// See directCycle for details. +func (check *Checker) directCycles() { + pathIdx := make(map[*TypeName]int) + for _, obj := range check.objList { + if tname, ok := obj.(*TypeName); ok { + check.directCycle(tname, pathIdx) + } + } +} + +// directCycle checks if the declaration of the type given by tname contains a direct cycle. +// A direct cycle exists if the path from tname's declaration's RHS leads from type name to +// type name and eventually ends up on that path again, via regular or alias declarations; +// in other words if there are no type literals (or basic types) on the path, and the path +// doesn't end in an undeclared object. +// If a cycle is detected, a cycle error is reported and the type at the start of the cycle +// is marked as invalid. +// +// The pathIdx map tracks which type names have been processed. An entry can be +// in 1 of 3 states as used in a typical 3-state (white/grey/black) graph marking +// algorithm for cycle detection: +// +// - entry not found: tname has not been seen before (white) +// - value is >= 0 : tname has been seen but is not done (grey); the value is the path index +// - value is < 0 : tname has been seen and is done (black) +// +// When directCycle returns, the pathIdx entries for all type names on the path +// that starts at tname are marked black, regardless of whether there was a cycle. +// This ensures that a type name is traversed only once. +func (check *Checker) directCycle(tname *TypeName, pathIdx map[*TypeName]int) { + if debug && check.conf.Trace { + check.trace(tname.Pos(), "-- check direct cycle for %s", tname) + } + + var path []*TypeName + for { + start, found := pathIdx[tname] + if start < 0 { + // tname is marked black - do not traverse it again. + // (start can only be < 0 if it was found in the first place) + break + } + + if found { + // tname is marked grey - we have a cycle on the path beginning at start. + // Mark tname as invalid. + tname.setType(Typ[Invalid]) + tname.setColor(black) + + // collect type names on cycle + var cycle []Object + for _, tname := range path[start:] { + cycle = append(cycle, tname) + } + + check.cycleError(cycle, firstInSrc(cycle)) + break + } + + // tname is marked white - mark it grey and add it to the path. + pathIdx[tname] = len(path) + path = append(path, tname) + + // For direct cycle detection, we don't care about whether we have an alias or not. + // If the associated type is not a name, we're at the end of the path and we're done. + rhs, ok := check.objMap[tname].tdecl.Type.(*syntax.Name) + if !ok { + break + } + + // Determine the RHS type. If it is not found in the package scope, we either + // have an error (which will be reported later), or the type exists elsewhere + // (universe scope, file scope via dot-import) and a cycle is not possible in + // the first place. If it is not a type name, we cannot have a direct cycle + // either. In all these cases we can stop. + tname1, ok := check.pkg.scope.Lookup(rhs.Value).(*TypeName) + if !ok { + break + } + + // Otherwise, continue with the RHS. + tname = tname1 + } + + // Mark all traversed type names black. + // (ensure that pathIdx doesn't contain any grey entries upon returning) + for _, tname := range path { + pathIdx[tname] = -1 + } + + if debug { + for _, i := range pathIdx { + assert(i < 0) + } + } +} diff --git a/src/cmd/compile/internal/types2/named.go b/src/cmd/compile/internal/types2/named.go index cece304925..b5c8ed142a 100644 --- a/src/cmd/compile/internal/types2/named.go +++ b/src/cmd/compile/internal/types2/named.go @@ -613,13 +613,18 @@ func (t *Named) String() string { return TypeString(t, nil) } // type set to T. Aliases are skipped because their underlying type is // not memoized. // -// This method also checks for cycles among alias and named types, which will -// yield no underlying type. If such a cycle is found, the underlying type is -// set to Typ[Invalid] and a cycle is reported. +// resolveUnderlying assumes that there are no direct cycles; if there were +// any, they were broken (by setting the respective types to invalid) during +// the directCycles check phase. func (n *Named) resolveUnderlying() { assert(n.stateHas(unpacked)) - var seen map[*Named]int // allocated lazily + var seen map[*Named]bool // for debugging only + if debug { + seen = make(map[*Named]bool) + } + + var path []*Named var u Type for rhs := Type(n); u == nil; { switch t := rhs.(type) { @@ -630,17 +635,9 @@ func (n *Named) resolveUnderlying() { rhs = unalias(t) case *Named: - if i, ok := seen[t]; ok { - // compute cycle path - path := make([]Object, len(seen)) - for t, j := range seen { - path[j] = t.obj - } - path = path[i:] - // only called during type checking, hence n.check != nil - n.check.cycleError(path, firstInSrc(path)) - u = Typ[Invalid] - break + if debug { + assert(!seen[t]) + seen[t] = true } // don't recalculate the underlying @@ -649,10 +646,10 @@ func (n *Named) resolveUnderlying() { break } - if seen == nil { - seen = make(map[*Named]int) + if debug { + seen[t] = true } - seen[t] = len(seen) + path = append(path, t) t.unpack() assert(t.rhs() != nil || t.allowNilRHS) @@ -663,7 +660,7 @@ func (n *Named) resolveUnderlying() { } } - for t := range seen { + for _, t := range path { func() { t.mu.Lock() defer t.mu.Unlock() diff --git a/src/go/types/check.go b/src/go/types/check.go index d163012f1e..44d3ae5586 100644 --- a/src/go/types/check.go +++ b/src/go/types/check.go @@ -522,6 +522,9 @@ func (check *Checker) checkFiles(files []*ast.File) { print("== sortObjects ==") check.sortObjects() + print("== directCycles ==") + check.directCycles() + print("== packageObjects ==") check.packageObjects() diff --git a/src/go/types/cycles.go b/src/go/types/cycles.go new file mode 100644 index 0000000000..87e8e9729b --- /dev/null +++ b/src/go/types/cycles.go @@ -0,0 +1,105 @@ +// Copyright 2025 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package types + +import "go/ast" + +// directCycles searches for direct cycles among package level type declarations. +// See directCycle for details. +func (check *Checker) directCycles() { + pathIdx := make(map[*TypeName]int) + for _, obj := range check.objList { + if tname, ok := obj.(*TypeName); ok { + check.directCycle(tname, pathIdx) + } + } +} + +// directCycle checks if the declaration of the type given by tname contains a direct cycle. +// A direct cycle exists if the path from tname's declaration's RHS leads from type name to +// type name and eventually ends up on that path again, via regular or alias declarations; +// in other words if there are no type literals (or basic types) on the path, and the path +// doesn't end in an undeclared object. +// If a cycle is detected, a cycle error is reported and the type at the start of the cycle +// is marked as invalid. +// +// The pathIdx map tracks which type names have been processed. An entry can be +// in 1 of 3 states as used in a typical 3-state (white/grey/black) graph marking +// algorithm for cycle detection: +// +// - entry not found: tname has not been seen before (white) +// - value is >= 0 : tname has been seen but is not done (grey); the value is the path index +// - value is < 0 : tname has been seen and is done (black) +// +// When directCycle returns, the pathIdx entries for all type names on the path +// that starts at tname are marked black, regardless of whether there was a cycle. +// This ensures that a type name is traversed only once. +func (check *Checker) directCycle(tname *TypeName, pathIdx map[*TypeName]int) { + if debug && check.conf._Trace { + check.trace(tname.Pos(), "-- check direct cycle for %s", tname) + } + + var path []*TypeName + for { + start, found := pathIdx[tname] + if start < 0 { + // tname is marked black - do not traverse it again. + // (start can only be < 0 if it was found in the first place) + break + } + + if found { + // tname is marked grey - we have a cycle on the path beginning at start. + // Mark tname as invalid. + tname.setType(Typ[Invalid]) + tname.setColor(black) + + // collect type names on cycle + var cycle []Object + for _, tname := range path[start:] { + cycle = append(cycle, tname) + } + + check.cycleError(cycle, firstInSrc(cycle)) + break + } + + // tname is marked white - mark it grey and add it to the path. + pathIdx[tname] = len(path) + path = append(path, tname) + + // For direct cycle detection, we don't care about whether we have an alias or not. + // If the associated type is not a name, we're at the end of the path and we're done. + rhs, ok := check.objMap[tname].tdecl.Type.(*ast.Ident) + if !ok { + break + } + + // Determine the RHS type. If it is not found in the package scope, we either + // have an error (which will be reported later), or the type exists elsewhere + // (universe scope, file scope via dot-import) and a cycle is not possible in + // the first place. If it is not a type name, we cannot have a direct cycle + // either. In all these cases we can stop. + tname1, ok := check.pkg.scope.Lookup(rhs.Name).(*TypeName) + if !ok { + break + } + + // Otherwise, continue with the RHS. + tname = tname1 + } + + // Mark all traversed type names black. + // (ensure that pathIdx doesn't contain any grey entries upon returning) + for _, tname := range path { + pathIdx[tname] = -1 + } + + if debug { + for _, i := range pathIdx { + assert(i < 0) + } + } +} diff --git a/src/go/types/named.go b/src/go/types/named.go index 1f9e2470fa..b106d7a8eb 100644 --- a/src/go/types/named.go +++ b/src/go/types/named.go @@ -616,13 +616,18 @@ func (t *Named) String() string { return TypeString(t, nil) } // type set to T. Aliases are skipped because their underlying type is // not memoized. // -// This method also checks for cycles among alias and named types, which will -// yield no underlying type. If such a cycle is found, the underlying type is -// set to Typ[Invalid] and a cycle is reported. +// resolveUnderlying assumes that there are no direct cycles; if there were +// any, they were broken (by setting the respective types to invalid) during +// the directCycles check phase. func (n *Named) resolveUnderlying() { assert(n.stateHas(unpacked)) - var seen map[*Named]int // allocated lazily + var seen map[*Named]bool // for debugging only + if debug { + seen = make(map[*Named]bool) + } + + var path []*Named var u Type for rhs := Type(n); u == nil; { switch t := rhs.(type) { @@ -633,17 +638,9 @@ func (n *Named) resolveUnderlying() { rhs = unalias(t) case *Named: - if i, ok := seen[t]; ok { - // compute cycle path - path := make([]Object, len(seen)) - for t, j := range seen { - path[j] = t.obj - } - path = path[i:] - // only called during type checking, hence n.check != nil - n.check.cycleError(path, firstInSrc(path)) - u = Typ[Invalid] - break + if debug { + assert(!seen[t]) + seen[t] = true } // don't recalculate the underlying @@ -652,10 +649,10 @@ func (n *Named) resolveUnderlying() { break } - if seen == nil { - seen = make(map[*Named]int) + if debug { + seen[t] = true } - seen[t] = len(seen) + path = append(path, t) t.unpack() assert(t.rhs() != nil || t.allowNilRHS) @@ -666,7 +663,7 @@ func (n *Named) resolveUnderlying() { } } - for t := range seen { + for _, t := range path { func() { t.mu.Lock() defer t.mu.Unlock() -- 2.52.0