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