cycles.go

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