scope.go

     1  // Copyright 2013 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  // This file implements Scopes.
     6  
     7  package types2
     8  
     9  import (
    10  	"cmd/compile/internal/syntax"
    11  	"fmt"
    12  	"io"
    13  	"iter"
    14  	"slices"
    15  	"strings"
    16  	"sync"
    17  	"sync/atomic"
    18  )
    19  
    20  // A Scope maintains a set of objects and links to its containing
    21  // (parent) and contained (children) scopes. Objects may be inserted
    22  // and looked up by name. The zero value for Scope is a ready-to-use
    23  // empty scope.
    24  type Scope struct {
    25  	parent      *Scope
    26  	children    []*Scope
    27  	number      int                      // parent.children[number-1] is this scope; 0 if there is no parent
    28  	objects     map[string]Object        // lazily allocated
    29  	pos, end    syntax.Pos               // scope extent; may be invalid
    30  	comment     string                   // for debugging only
    31  	isFunc      bool                     // set if this is a function scope (internal use only)
    32  	sortedNames atomic.Pointer[[]string] // lazy cache of Names(), cleared during mutation
    33  }
    34  
    35  // NewScope returns a new, empty scope contained in the given parent
    36  // scope, if any. The comment is for debugging only.
    37  func NewScope(parent *Scope, pos, end syntax.Pos, comment string) *Scope {
    38  	s := &Scope{parent: parent, pos: pos, end: end, comment: comment}
    39  	// don't add children to Universe scope!
    40  	if parent != nil && parent != Universe {
    41  		parent.children = append(parent.children, s)
    42  		s.number = len(parent.children)
    43  	}
    44  	return s
    45  }
    46  
    47  // Parent returns the scope's containing (parent) scope.
    48  func (s *Scope) Parent() *Scope { return s.parent }
    49  
    50  // Len returns the number of scope objects.
    51  func (s *Scope) Len() int { return len(s.objects) }
    52  
    53  // Names returns the scope's object names in sorted order.
    54  // The caller must not mutate the array.
    55  func (s *Scope) Names() []string {
    56  	// We cache the result to avoid allocation on
    57  	// each call, as this is a known hotspot.
    58  	ptr := s.sortedNames.Load()
    59  	if ptr == nil {
    60  		// cache miss
    61  		names := make([]string, len(s.objects))
    62  		i := 0
    63  		for name := range s.objects {
    64  			names[i] = name
    65  			i++
    66  		}
    67  		slices.Sort(names)
    68  		ptr = &names
    69  
    70  		// Don't overwrite if another goroutine got there first.
    71  		s.sortedNames.CompareAndSwap(nil, &names)
    72  	}
    73  	return *ptr
    74  }
    75  
    76  // NumChildren returns the number of scopes nested in s.
    77  func (s *Scope) NumChildren() int { return len(s.children) }
    78  
    79  // Child returns the i'th child scope for 0 <= i < NumChildren().
    80  func (s *Scope) Child(i int) *Scope { return s.children[i] }
    81  
    82  // Lookup returns the object in scope s with the given name if such an
    83  // object exists; otherwise the result is nil.
    84  func (s *Scope) Lookup(name string) Object { return resolve(name, s.objects[name]) }
    85  
    86  // Objects returns the sequence of objects in the scope in name order.
    87  //
    88  // The caller should not mutate the Scope during iteration.
    89  //
    90  // Example:
    91  //
    92  //	for obj := range s.Objects() { ... }
    93  func (s *Scope) Objects() iter.Seq[Object] {
    94  	return func(yield func(obj Object) bool) {
    95  		names := s.Names()
    96  		for _, name := range names {
    97  			if !yield(s.Lookup(name)) {
    98  				break
    99  			}
   100  		}
   101  	}
   102  }
   103  
   104  // lookupIgnoringCase returns the objects in scope s whose names match
   105  // the given name ignoring case. If exported is set, only exported names
   106  // are returned.
   107  func (s *Scope) lookupIgnoringCase(name string, exported bool) []Object {
   108  	var matches []Object
   109  	for _, n := range s.Names() {
   110  		if (!exported || isExported(n)) && strings.EqualFold(n, name) {
   111  			matches = append(matches, s.Lookup(n))
   112  		}
   113  	}
   114  	return matches
   115  }
   116  
   117  // Insert attempts to insert an object obj into scope s.
   118  // If s already contains an alternative object alt with
   119  // the same name, Insert leaves s unchanged and returns alt.
   120  // Otherwise it inserts obj, sets the object's parent scope
   121  // if not already set, and returns nil.
   122  func (s *Scope) Insert(obj Object) Object {
   123  	name := obj.Name()
   124  	if alt := s.Lookup(name); alt != nil {
   125  		return alt
   126  	}
   127  	s.insert(name, obj)
   128  	// TODO(gri) Can we always set the parent to s (or is there
   129  	// a need to keep the original parent or some race condition)?
   130  	// If we can, than we may not need environment.lookupScope
   131  	// which is only there so that we get the correct scope for
   132  	// marking "used" dot-imported packages.
   133  	if obj.Parent() == nil {
   134  		obj.setParent(s)
   135  	}
   136  	return nil
   137  }
   138  
   139  // InsertLazy is like Insert, but allows deferring construction of the
   140  // inserted object until it's accessed with Lookup. The Object
   141  // returned by resolve must have the same name as given to InsertLazy.
   142  // If s already contains an alternative object with the same name,
   143  // InsertLazy leaves s unchanged and returns false. Otherwise it
   144  // records the binding and returns true. The object's parent scope
   145  // will be set to s after resolve is called.
   146  func (s *Scope) InsertLazy(name string, resolve func() Object) bool {
   147  	if s.objects[name] != nil {
   148  		return false
   149  	}
   150  	s.insert(name, &lazyObject{parent: s, resolve: resolve})
   151  	return true
   152  }
   153  
   154  func (s *Scope) insert(name string, obj Object) {
   155  	if s.objects == nil {
   156  		s.objects = make(map[string]Object)
   157  	}
   158  	s.sortedNames.Store(nil) // clear cache
   159  	s.objects[name] = obj
   160  }
   161  
   162  // WriteTo writes a string representation of the scope to w,
   163  // with the scope elements sorted by name.
   164  // The level of indentation is controlled by n >= 0, with
   165  // n == 0 for no indentation.
   166  // If recurse is set, it also writes nested (children) scopes.
   167  func (s *Scope) WriteTo(w io.Writer, n int, recurse bool) {
   168  	const ind = ".  "
   169  	indn := strings.Repeat(ind, n)
   170  
   171  	fmt.Fprintf(w, "%s%s scope %p {\n", indn, s.comment, s)
   172  
   173  	indn1 := indn + ind
   174  	for _, name := range s.Names() {
   175  		fmt.Fprintf(w, "%s%s\n", indn1, s.Lookup(name))
   176  	}
   177  
   178  	if recurse {
   179  		for _, s := range s.children {
   180  			s.WriteTo(w, n+1, recurse)
   181  		}
   182  	}
   183  
   184  	fmt.Fprintf(w, "%s}\n", indn)
   185  }
   186  
   187  // String returns a string representation of the scope, for debugging.
   188  func (s *Scope) String() string {
   189  	var buf strings.Builder
   190  	s.WriteTo(&buf, 0, false)
   191  	return buf.String()
   192  }
   193  
   194  // A lazyObject represents an imported Object that has not been fully
   195  // resolved yet by its importer.
   196  type lazyObject struct {
   197  	parent  *Scope
   198  	resolve func() Object
   199  	obj     Object
   200  	once    sync.Once
   201  }
   202  
   203  // resolve returns the Object represented by obj, resolving lazy
   204  // objects as appropriate.
   205  func resolve(name string, obj Object) Object {
   206  	if lazy, ok := obj.(*lazyObject); ok {
   207  		lazy.once.Do(func() {
   208  			obj := lazy.resolve()
   209  
   210  			if _, ok := obj.(*lazyObject); ok {
   211  				panic("recursive lazy object")
   212  			}
   213  			if obj.Name() != name {
   214  				panic("lazy object has unexpected name")
   215  			}
   216  
   217  			if obj.Parent() == nil {
   218  				obj.setParent(lazy.parent)
   219  			}
   220  			lazy.obj = obj
   221  		})
   222  
   223  		obj = lazy.obj
   224  	}
   225  	return obj
   226  }
   227  
   228  // stub implementations so *lazyObject implements Object and we can
   229  // store them directly into Scope.elems.
   230  func (*lazyObject) Parent() *Scope                     { panic("unreachable") }
   231  func (*lazyObject) Pos() syntax.Pos                    { panic("unreachable") }
   232  func (*lazyObject) Pkg() *Package                      { panic("unreachable") }
   233  func (*lazyObject) Name() string                       { panic("unreachable") }
   234  func (*lazyObject) Type() Type                         { panic("unreachable") }
   235  func (*lazyObject) Exported() bool                     { panic("unreachable") }
   236  func (*lazyObject) Id() string                         { panic("unreachable") }
   237  func (*lazyObject) String() string                     { panic("unreachable") }
   238  func (*lazyObject) order() uint32                      { panic("unreachable") }
   239  func (*lazyObject) setType(Type)                       { panic("unreachable") }
   240  func (*lazyObject) setOrder(uint32)                    { panic("unreachable") }
   241  func (*lazyObject) setParent(*Scope)                   { panic("unreachable") }
   242  func (*lazyObject) sameId(*Package, string, bool) bool { panic("unreachable") }
   243  func (*lazyObject) scopePos() syntax.Pos               { panic("unreachable") }
   244  func (*lazyObject) setScopePos(syntax.Pos)             { panic("unreachable") }
   245
View as plain text