go/types, types2: replace pendingType with completion check

This change establishes the invariant that Underlying() cannot observe
a nil RHS for a defined type, unless that type was created by go/types
with an explicitly nil underlying type.

It does so using isComplete, which is a guard to check that a type has
an underlying type. This guard is needed whenever we could produce a
value of a defined type or access some property of a defined type.

Examples include T{}, *x (where x has type *T), T.x, etc. (see CL
734600 for more).

The pendingType mechanism to deeply traverse values of a defined type
is moved to hasVarSize, since this is only truly needed at the site
of a built-in such as unsafe.Sizeof.

This ties cycle detection across value context directly to the syntax,
which seems like the right direction.

Change-Id: Ic47862a2038fb2ba3ae6621e9907265ccbd86ea3
Reviewed-on: https://go-review.googlesource.com/c/go/+/734980
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Robert Griesemer <gri@google.com>
Auto-Submit: Mark Freeman <markfreeman@google.com>

8 files changed, 122 insertions, 116 deletions

diff --git a/src/cmd/compile/internal/types2/builtins.go b/src/cmd/compile/internal/types2/builtins.go
index 549d94615b..b11bacdecf 100644
--- a/src/cmd/compile/internal/types2/builtins.go
+++ b/src/cmd/compile/internal/types2/builtins.go
@@ -752,7 +752,7 @@ func (check *Checker) builtin(x *operand, call *syntax.CallExpr, id builtinId) (
 			return
 		}
 
-		if hasVarSize(x.typ, nil) {
+		if check.hasVarSize(x.typ) {
 			x.mode = value
 			if check.recordTypes() {
 				check.recordBuiltinType(call.Fun, makeSig(Typ[Uintptr], x.typ))
@@ -816,7 +816,7 @@ func (check *Checker) builtin(x *operand, call *syntax.CallExpr, id builtinId) (
 		// the part of the struct which is variable-sized. This makes both the rules
 		// simpler and also permits (or at least doesn't prevent) a compiler from re-
 		// arranging struct fields if it wanted to.
-		if hasVarSize(base, nil) {
+		if check.hasVarSize(base) {
 			x.mode = value
 			if check.recordTypes() {
 				check.recordBuiltinType(call.Fun, makeSig(Typ[Uintptr], obj.Type()))
@@ -840,7 +840,7 @@ func (check *Checker) builtin(x *operand, call *syntax.CallExpr, id builtinId) (
 			return
 		}
 
-		if hasVarSize(x.typ, nil) {
+		if check.hasVarSize(x.typ) {
 			x.mode = value
 			if check.recordTypes() {
 				check.recordBuiltinType(call.Fun, makeSig(Typ[Uintptr], x.typ))
@@ -1007,37 +1007,56 @@ func sliceElem(x *operand) (Type, *typeError) {
 // hasVarSize reports if the size of type t is variable due to type parameters
 // or if the type is infinitely-sized due to a cycle for which the type has not
 // yet been checked.
-func hasVarSize(t Type, seen map[*Named]bool) (varSized bool) {
-	// Cycles are only possible through *Named types.
-	// The seen map is used to detect cycles and track
-	// the results of previously seen types.
-	if named := asNamed(t); named != nil {
-		if v, ok := seen[named]; ok {
-			return v
+func (check *Checker) hasVarSize(t Type) bool {
+	// Note: We could use Underlying here, but passing through the RHS may yield
+	// better error messages.
+	switch t := Unalias(t).(type) {
+	case *Named:
+		if t.stateHas(hasFinite) {
+			// TODO(mark): Rename t.finite to t.varSize to avoid inversion.
+			return !t.finite
 		}
-		if seen == nil {
-			seen = make(map[*Named]bool)
+
+		if i, ok := check.objPathIdx[t.obj]; ok {
+			cycle := check.objPath[i:]
+			check.cycleError(cycle, firstInSrc(cycle))
+			return true
 		}
-		seen[named] = true // possibly cyclic until proven otherwise
-		defer func() {
-			seen[named] = varSized // record final determination for named
-		}()
-	}
 
-	switch u := t.Underlying().(type) {
+		check.push(t.obj)
+		defer check.pop()
+
+		varSize := check.hasVarSize(t.fromRHS)
+
+		t.mu.Lock()
+		defer t.mu.Unlock()
+
+		// Careful, t.finite has lock-free readers. Since we might be racing
+		// another call to finiteSize, we have to avoid overwriting t.finite.
+		// Otherwise, the race detector will be tripped.
+		if !t.stateHas(hasFinite) {
+			t.finite = !varSize
+			t.setState(hasFinite)
+		}
+
+		return varSize
+
 	case *Array:
-		return hasVarSize(u.elem, seen)
+		// The array length is already computed. If it was a valid length, it
+		// is finite; else, an error was reported in the computation.
+		return check.hasVarSize(t.elem)
+
 	case *Struct:
-		for _, f := range u.fields {
-			if hasVarSize(f.typ, seen) {
+		for _, f := range t.fields {
+			if check.hasVarSize(f.typ) {
 				return true
 			}
 		}
-	case *Interface:
-		return isTypeParam(t)
-	case *Named, *Union:
-		panic("unreachable")
+
+	case *TypeParam:
+		return true
 	}
+
 	return false
 }
 
diff --git a/src/cmd/compile/internal/types2/call.go b/src/cmd/compile/internal/types2/call.go
index c23a1048f2..cf950959f9 100644
--- a/src/cmd/compile/internal/types2/call.go
+++ b/src/cmd/compile/internal/types2/call.go
@@ -199,6 +199,11 @@ func (check *Checker) callExpr(x *operand, call *syntax.CallExpr) exprKind {
 		}
 		T := x.typ
 		x.mode = invalid
+		// We cannot convert a value to an incomplete type; make sure it's complete.
+		if !check.isComplete(T) {
+			x.expr = call
+			return conversion
+		}
 		switch n := len(call.ArgList); n {
 		case 0:
 			check.errorf(call, WrongArgCount, "missing argument in conversion to %s", T)
@@ -319,7 +324,14 @@ func (check *Checker) callExpr(x *operand, call *syntax.CallExpr) exprKind {
 		} else {
 			x.mode = value
 		}
-		x.typ = sig.results.vars[0].typ // unpack tuple
+		typ := sig.results.vars[0].typ // unpack tuple
+		// We cannot return a value of an incomplete type; make sure it's complete.
+		if !check.isComplete(typ) {
+			x.mode = invalid
+			x.expr = call
+			return statement
+		}
+		x.typ = typ
 	default:
 		x.mode = value
 		x.typ = sig.results
@@ -784,8 +796,12 @@ func (check *Checker) selector(x *operand, e *syntax.SelectorExpr, wantType bool
 		goto Error
 	}
 
-	// Avoid crashing when checking an invalid selector in a method declaration
-	// (i.e., where def is not set):
+	// We cannot select on an incomplete type; make sure it's complete.
+	if !check.isComplete(x.typ) {
+		goto Error
+	}
+
+	// Avoid crashing when checking an invalid selector in a method declaration.
 	//
 	//   type S[T any] struct{}
 	//   type V = S[any]
@@ -795,14 +811,17 @@ func (check *Checker) selector(x *operand, e *syntax.SelectorExpr, wantType bool
 	// expecting a type expression, it is an error.
 	//
 	// See go.dev/issue/57522 for more details.
-	//
-	// TODO(rfindley): We should do better by refusing to check selectors in all cases where
-	// x.typ is incomplete.
 	if wantType {
 		check.errorf(e.Sel, NotAType, "%s is not a type", syntax.Expr(e))
 		goto Error
 	}
 
+	// Additionally, if x.typ is a pointer type, selecting implicitly dereferences the value, meaning
+	// its base type must also be complete.
+	if p, ok := x.typ.Underlying().(*Pointer); ok && !check.isComplete(p.base) {
+		goto Error
+	}
+
 	obj, index, indirect = lookupFieldOrMethod(x.typ, x.mode == variable, check.pkg, sel, false)
 	if obj == nil {
 		// Don't report another error if the underlying type was invalid (go.dev/issue/49541).
diff --git a/src/cmd/compile/internal/types2/cycles.go b/src/cmd/compile/internal/types2/cycles.go
index 84a05c9647..14bd7f2630 100644
--- a/src/cmd/compile/internal/types2/cycles.go
+++ b/src/cmd/compile/internal/types2/cycles.go
@@ -103,49 +103,25 @@ func (check *Checker) directCycle(tname *TypeName, pathIdx map[*TypeName]int) {
 	}
 }
 
-// TODO(markfreeman): Can the value cached on Named be used in validType / hasVarSize?
-
-// finiteSize returns whether a type has finite size.
-func (check *Checker) finiteSize(t Type) bool {
-	switch t := Unalias(t).(type) {
-	case *Named:
-		if t.stateHas(hasFinite) {
-			return t.finite
-		}
-
-		if i, ok := check.objPathIdx[t.obj]; ok {
+// isComplete returns whether a type is complete (i.e. up to having an underlying type).
+// Incomplete types will panic if [Type.Underlying] is called on them.
+func (check *Checker) isComplete(t Type) bool {
+	if n, ok := Unalias(t).(*Named); ok {
+		if i, found := check.objPathIdx[n.obj]; found {
 			cycle := check.objPath[i:]
 			check.cycleError(cycle, firstInSrc(cycle))
 			return false
 		}
-		check.push(t.obj)
-		defer check.pop()
-
-		isFinite := check.finiteSize(t.fromRHS)
-
-		t.mu.Lock()
-		defer t.mu.Unlock()
-		// Careful, t.finite has lock-free readers. Since we might be racing
-		// another call to finiteSize, we have to avoid overwriting t.finite.
-		// Otherwise, the race detector will be tripped.
-		if !t.stateHas(hasFinite) {
-			t.finite = isFinite
-			t.setState(hasFinite)
-		}
-
-		return isFinite
-
-	case *Array:
-		// The array length is already computed. If it was a valid length, it
-		// is finite; else, an error was reported in the computation.
-		return check.finiteSize(t.elem)
 
-	case *Struct:
-		for _, f := range t.fields {
-			if !check.finiteSize(f.typ) {
-				return false
-			}
-		}
+		// We must walk through names because we permit certain cycles of names.
+		// Consider:
+		//
+		//   type A B
+		//   type B [unsafe.Sizeof(A{})]int
+		//
+		// starting at B. At the site of A{}, A has no underlying type, and so a
+		// cycle must be reported.
+		return check.isComplete(n.fromRHS)
 	}
 
 	return true
diff --git a/src/cmd/compile/internal/types2/decl.go b/src/cmd/compile/internal/types2/decl.go
index be9c63bc8c..97d486cc5a 100644
--- a/src/cmd/compile/internal/types2/decl.go
+++ b/src/cmd/compile/internal/types2/decl.go
@@ -483,20 +483,6 @@ func (check *Checker) typeDecl(obj *TypeName, tdecl *syntax.TypeDecl) {
 	}
 
 	named := check.newNamed(obj, nil, nil)
-
-	// TODO: adjust this comment (gotypesalias) as needed if we don't need allowNilRHS anymore.
-	// The RHS of a named N can be nil if, for example, N is defined as a cycle of aliases with
-	// gotypesalias=0. Consider:
-	//
-	//   type D N    // N.unpack() will panic
-	//   type N A
-	//   type A = N  // N.fromRHS is not set before N.unpack(), since A does not call setDefType
-	//
-	// There is likely a better way to detect such cases, but it may not be worth the effort.
-	// Instead, we briefly permit a nil N.fromRHS while type-checking D.
-	named.allowNilRHS = true
-	defer (func() { named.allowNilRHS = false })()
-
 	if tdecl.TParamList != nil {
 		check.openScope(tdecl, "type parameters")
 		defer check.closeScope()
diff --git a/src/cmd/compile/internal/types2/expr.go b/src/cmd/compile/internal/types2/expr.go
index e3ef1af1ce..81aeb5ffd0 100644
--- a/src/cmd/compile/internal/types2/expr.go
+++ b/src/cmd/compile/internal/types2/expr.go
@@ -148,7 +148,8 @@ func (check *Checker) unary(x *operand, e *syntax.Operation) {
 		return
 
 	case syntax.Recv:
-		if elem := check.chanElem(x, x, true); elem != nil {
+		// We cannot receive a value with an incomplete type; make sure it's complete.
+		if elem := check.chanElem(x, x, true); elem != nil && check.isComplete(elem) {
 			x.mode = commaok
 			x.typ = elem
 			check.hasCallOrRecv = true
@@ -993,13 +994,6 @@ func (check *Checker) rawExpr(T *target, x *operand, e syntax.Expr, hint Type, a
 		check.nonGeneric(T, x)
 	}
 
-	// Here, x is a value, meaning it has a type. If that type is pending, then we have
-	// a cycle. As an example:
-	//
-	//  type T [unsafe.Sizeof(T{})]int
-	//
-	// has a cycle T->T which is deemed valid (by decl.go), but which is in fact invalid.
-	check.pendingType(x)
 	check.record(x)
 
 	return kind
@@ -1034,19 +1028,6 @@ func (check *Checker) nonGeneric(T *target, x *operand) {
 	}
 }
 
-// If x has a pending type (i.e. its declaring object is on the object path), pendingType
-// reports an error and invalidates x.mode and x.typ.
-// Otherwise it leaves x alone.
-func (check *Checker) pendingType(x *operand) {
-	if x.mode == invalid || x.mode == novalue {
-		return
-	}
-	if !check.finiteSize(x.typ) {
-		x.mode = invalid
-		x.typ = Typ[Invalid]
-	}
-}
-
 // exprInternal contains the core of type checking of expressions.
 // Must only be called by rawExpr.
 // (See rawExpr for an explanation of the parameters.)
@@ -1140,6 +1121,10 @@ func (check *Checker) exprInternal(T *target, x *operand, e syntax.Expr, hint Ty
 		if !isValid(T) {
 			goto Error
 		}
+		// We cannot assert to an incomplete type; make sure it's complete.
+		if !check.isComplete(T) {
+			goto Error
+		}
 		check.typeAssertion(e, x, T, false)
 		x.mode = commaok
 		x.typ = T
@@ -1207,6 +1192,10 @@ func (check *Checker) exprInternal(T *target, x *operand, e syntax.Expr, hint Ty
 					}) {
 						goto Error
 					}
+					// We cannot dereference a pointer with an incomplete base type; make sure it's complete.
+					if !check.isComplete(base) {
+						goto Error
+					}
 					x.mode = variable
 					x.typ = base
 				}
diff --git a/src/cmd/compile/internal/types2/index.go b/src/cmd/compile/internal/types2/index.go
index ca84184d35..98d83833c8 100644
--- a/src/cmd/compile/internal/types2/index.go
+++ b/src/cmd/compile/internal/types2/index.go
@@ -47,6 +47,18 @@ func (check *Checker) indexExpr(x *operand, e *syntax.IndexExpr) (isFuncInst boo
 		return false
 	}
 
+	// We cannot index on an incomplete type; make sure it's complete.
+	if !check.isComplete(x.typ) {
+		x.mode = invalid
+		return false
+	}
+	// Additionally, if x.typ is a pointer to an array type, indexing implicitly dereferences the value, meaning
+	// its base type must also be complete.
+	if p, ok := x.typ.Underlying().(*Pointer); ok && !check.isComplete(p.base) {
+		x.mode = invalid
+		return false
+	}
+
 	// ordinary index expression
 	valid := false
 	length := int64(-1) // valid if >= 0
@@ -251,6 +263,14 @@ func (check *Checker) sliceExpr(x *operand, e *syntax.SliceExpr) {
 		}
 	}
 
+	// Note that we don't permit slice expressions where x is a type expression, so we don't check for that here.
+	// However, if x.typ is a pointer to an array type, slicing implicitly dereferences the value, meaning
+	// its base type must also be complete.
+	if p, ok := x.typ.Underlying().(*Pointer); ok && !check.isComplete(p.base) {
+		x.mode = invalid
+		return
+	}
+
 	valid := false
 	length := int64(-1) // valid if >= 0
 	switch u := cu.(type) {
diff --git a/src/cmd/compile/internal/types2/literals.go b/src/cmd/compile/internal/types2/literals.go
index ed1c3f695c..6817231a76 100644
--- a/src/cmd/compile/internal/types2/literals.go
+++ b/src/cmd/compile/internal/types2/literals.go
@@ -143,6 +143,12 @@ func (check *Checker) compositeLit(x *operand, e *syntax.CompositeLit, hint Type
 		base = typ
 	}
 
+	// We cannot create a literal of an incomplete type; make sure it's complete.
+	if !check.isComplete(base) {
+		x.mode = invalid
+		return
+	}
+
 	switch u, _ := commonUnder(base, nil); utyp := u.(type) {
 	case *Struct:
 		if len(e.ElemList) == 0 {
diff --git a/src/cmd/compile/internal/types2/named.go b/src/cmd/compile/internal/types2/named.go
index 2922fb55eb..77e958139f 100644
--- a/src/cmd/compile/internal/types2/named.go
+++ b/src/cmd/compile/internal/types2/named.go
@@ -106,9 +106,7 @@ type Named struct {
 	check *Checker  // non-nil during type-checking; nil otherwise
 	obj   *TypeName // corresponding declared object for declared types; see above for instantiated types
 
-	// flags indicating temporary violations of the invariants for fromRHS and underlying
-	allowNilRHS        bool // same as below, as well as briefly during checking of a type declaration
-	allowNilUnderlying bool // may be true from creation via [NewNamed] until [Named.SetUnderlying]
+	allowNilRHS bool // may be true from creation via [NewNamed] until [Named.SetUnderlying]
 
 	inst *instance // information for instantiated types; nil otherwise
 
@@ -192,7 +190,6 @@ func NewNamed(obj *TypeName, underlying Type, methods []*Func) *Named {
 	n := (*Checker)(nil).newNamed(obj, underlying, methods)
 	if underlying == nil {
 		n.allowNilRHS = true
-		n.allowNilUnderlying = true
 	} else {
 		n.SetUnderlying(underlying)
 	}
@@ -532,7 +529,6 @@ func (t *Named) SetUnderlying(u Type) {
 	t.setState(lazyLoaded | unpacked | hasMethods) // TODO(markfreeman): Why hasMethods?
 
 	t.underlying = u
-	t.allowNilUnderlying = false
 	t.setState(hasUnder)
 }
 
@@ -594,9 +590,7 @@ func (n *Named) Underlying() Type {
 	// and complicating things there, we just check for that special case here.
 	if n.rhs() == nil {
 		assert(n.allowNilRHS)
-		if n.allowNilUnderlying {
-			return nil
-		}
+		return nil
 	}
 
 	if !n.stateHas(hasUnder) { // minor performance optimization
@@ -637,9 +631,6 @@ func (n *Named) resolveUnderlying() {
 	var u Type
 	for rhs := Type(n); u == nil; {
 		switch t := rhs.(type) {
-		case nil:
-			u = Typ[Invalid]
-
 		case *Alias:
 			rhs = unalias(t)
 
@@ -661,8 +652,8 @@ func (n *Named) resolveUnderlying() {
 			path = append(path, t)
 
 			t.unpack()
-			assert(t.rhs() != nil || t.allowNilRHS)
 			rhs = t.rhs()
+			assert(rhs != nil)
 
 		default:
 			u = rhs // any type literal or predeclared type works