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  
   109  // TODO(markfreeman): Can the value cached on Named be used in validType / hasVarSize?
   110  
   111  // finiteSize returns whether a type has finite size.
   112  func (check *Checker) finiteSize(t Type) bool {
   113  	switch t := Unalias(t).(type) {
   114  	case *Named:
   115  		if t.stateHas(hasFinite) {
   116  			return t.finite
   117  		}
   118  
   119  		if i, ok := check.objPathIdx[t.obj]; ok {
   120  			cycle := check.objPath[i:]
   121  			check.cycleError(cycle, firstInSrc(cycle))
   122  			return false
   123  		}
   124  		check.push(t.obj)
   125  		defer check.pop()
   126  
   127  		isFinite := check.finiteSize(t.fromRHS)
   128  
   129  		t.mu.Lock()
   130  		defer t.mu.Unlock()
   131  		// Careful, t.finite has lock-free readers. Since we might be racing
   132  		// another call to finiteSize, we have to avoid overwriting t.finite.
   133  		// Otherwise, the race detector will be tripped.
   134  		if !t.stateHas(hasFinite) {
   135  			t.finite = isFinite
   136  			t.setState(hasFinite)
   137  		}
   138  
   139  		return isFinite
   140  
   141  	case *Array:
   142  		// The array length is already computed. If it was a valid length, it
   143  		// is finite; else, an error was reported in the computation.
   144  		return check.finiteSize(t.elem)
   145  
   146  	case *Struct:
   147  		for _, f := range t.fields {
   148  			if !check.finiteSize(f.typ) {
   149  				return false
   150  			}
   151  		}
   152  	}
   153  
   154  	return true
   155  }
   156
View as plain text