cycles.go

     1  // Copyright 2025 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package types2
     6  
     7  import "cmd/compile/internal/syntax"
     8  
     9  // directCycles searches for direct cycles among package level type declarations.
    10  // See directCycle for details.
    11  func (check *Checker) directCycles() {
    12  	pathIdx := make(map[*TypeName]int)
    13  	for _, obj := range check.objList {
    14  		if tname, ok := obj.(*TypeName); ok {
    15  			check.directCycle(tname, pathIdx)
    16  		}
    17  	}
    18  }
    19  
    20  // directCycle checks if the declaration of the type given by tname contains a direct cycle.
    21  // A direct cycle exists if the path from tname's declaration's RHS leads from type name to
    22  // type name and eventually ends up on that path again, via regular or alias declarations;
    23  // in other words if there are no type literals (or basic types) on the path, and the path
    24  // doesn't end in an undeclared object.
    25  // If a cycle is detected, a cycle error is reported and the type at the start of the cycle
    26  // is marked as invalid.
    27  //
    28  // The pathIdx map tracks which type names have been processed. An entry can be
    29  // in 1 of 3 states as used in a typical 3-state (white/grey/black) graph marking
    30  // algorithm for cycle detection:
    31  //
    32  //   - entry not found: tname has not been seen before (white)
    33  //   - value is >= 0  : tname has been seen but is not done (grey); the value is the path index
    34  //   - value is <  0  : tname has been seen and is done (black)
    35  //
    36  // When directCycle returns, the pathIdx entries for all type names on the path
    37  // that starts at tname are marked black, regardless of whether there was a cycle.
    38  // This ensures that a type name is traversed only once.
    39  func (check *Checker) directCycle(tname *TypeName, pathIdx map[*TypeName]int) {
    40  	if debug && check.conf.Trace {
    41  		check.trace(tname.Pos(), "-- check direct cycle for %s", tname)
    42  	}
    43  
    44  	var path []*TypeName
    45  	for {
    46  		start, found := pathIdx[tname]
    47  		if start < 0 {
    48  			// tname is marked black - do not traverse it again.
    49  			// (start can only be < 0 if it was found in the first place)
    50  			break
    51  		}
    52  
    53  		if found {
    54  			// tname is marked grey - we have a cycle on the path beginning at start.
    55  			// Mark tname as invalid.
    56  			tname.setType(Typ[Invalid])
    57  
    58  			// collect type names on cycle
    59  			var cycle []Object
    60  			for _, tname := range path[start:] {
    61  				cycle = append(cycle, tname)
    62  			}
    63  
    64  			check.cycleError(cycle, firstInSrc(cycle))
    65  			break
    66  		}
    67  
    68  		// tname is marked white - mark it grey and add it to the path.
    69  		pathIdx[tname] = len(path)
    70  		path = append(path, tname)
    71  
    72  		// For direct cycle detection, we don't care about whether we have an alias or not.
    73  		// If the associated type is not a name, we're at the end of the path and we're done.
    74  		rhs, ok := check.objMap[tname].tdecl.Type.(*syntax.Name)
    75  		if !ok {
    76  			break
    77  		}
    78  
    79  		// Determine the RHS type. If it is not found in the package scope, we either
    80  		// have an error (which will be reported later), or the type exists elsewhere
    81  		// (universe scope, file scope via dot-import) and a cycle is not possible in
    82  		// the first place. If it is not a type name, we cannot have a direct cycle
    83  		// either. In all these cases we can stop.
    84  		tname1, ok := check.pkg.scope.Lookup(rhs.Value).(*TypeName)
    85  		if !ok {
    86  			break
    87  		}
    88  
    89  		// Otherwise, continue with the RHS.
    90  		tname = tname1
    91  	}
    92  
    93  	// Mark all traversed type names black.
    94  	// (ensure that pathIdx doesn't contain any grey entries upon returning)
    95  	for _, tname := range path {
    96  		pathIdx[tname] = -1
    97  	}
    98  
    99  	if debug {
   100  		for _, i := range pathIdx {
   101  			assert(i < 0)
   102  		}
   103  	}
   104  }
   105  
   106  // isComplete returns whether a type is complete (i.e. up to having an underlying type).
   107  // Incomplete types will panic if [Type.Underlying] is called on them.
   108  func (check *Checker) isComplete(t Type) bool {
   109  	var (
   110  		obj Object
   111  		rhs Type
   112  	)
   113  	switch t := t.(type) {
   114  	case *Alias:
   115  		obj = t.obj
   116  		rhs = t.fromRHS
   117  	case *Named:
   118  		obj = t.obj
   119  		rhs = t.fromRHS
   120  	default:
   121  		return true
   122  	}
   123  
   124  	if i, found := check.objPathIdx[obj]; found {
   125  		cycle := check.objPath[i:]
   126  		check.cycleError(cycle, firstInSrc(cycle))
   127  		return false
   128  	}
   129  
   130  	// We must walk through names because we permit certain cycles of names.
   131  	// Consider:
   132  	//
   133  	//   type A B
   134  	//   type B [unsafe.Sizeof(A{})]int
   135  	//
   136  	// starting at B. At the site of A{}, A has no underlying type, and so a
   137  	// cycle must be reported.
   138  	return check.isComplete(rhs)
   139  }
   140
View as plain text