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
View as plain text