context.go

     1  // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
     2  // Source: ../../cmd/compile/internal/types2/context.go
     3  
     4  // Copyright 2021 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 (
    11  	"bytes"
    12  	"fmt"
    13  	"strconv"
    14  	"strings"
    15  	"sync"
    16  )
    17  
    18  // This file contains a definition of the type-checking context; an opaque type
    19  // that may be supplied by users during instantiation.
    20  //
    21  // Contexts serve two purposes:
    22  //  - reduce the duplication of identical instances
    23  //  - short-circuit instantiation cycles
    24  //
    25  // For the latter purpose, we must always have a context during instantiation,
    26  // whether or not it is supplied by the user. For both purposes, it must be the
    27  // case that hashing a pointer-identical type produces consistent results
    28  // (somewhat obviously).
    29  //
    30  // However, neither of these purposes require that our hash is perfect, and so
    31  // this was not an explicit design goal of the context type. In fact, due to
    32  // concurrent use it is convenient not to guarantee de-duplication.
    33  //
    34  // Nevertheless, in the future it could be helpful to allow users to leverage
    35  // contexts to canonicalize instances, and it would probably be possible to
    36  // achieve such a guarantee.
    37  
    38  // A Context is an opaque type checking context. It may be used to share
    39  // identical type instances across type-checked packages or calls to
    40  // Instantiate. Contexts are safe for concurrent use.
    41  //
    42  // The use of a shared context does not guarantee that identical instances are
    43  // deduplicated in all cases.
    44  type Context struct {
    45  	mu        sync.Mutex
    46  	typeMap   map[string][]ctxtEntry // type hash -> instances entries
    47  	nextID    int                    // next unique ID
    48  	originIDs map[Type]int           // origin type -> unique ID
    49  }
    50  
    51  type ctxtEntry struct {
    52  	orig     Type
    53  	targs    []Type
    54  	instance Type // = orig[targs]
    55  }
    56  
    57  // NewContext creates a new Context.
    58  func NewContext() *Context {
    59  	return &Context{
    60  		typeMap:   make(map[string][]ctxtEntry),
    61  		originIDs: make(map[Type]int),
    62  	}
    63  }
    64  
    65  // instanceHash returns a string representation of typ instantiated with targs.
    66  // The hash should be a perfect hash, though out of caution the type checker
    67  // does not assume this. The result is guaranteed to not contain blanks.
    68  func (ctxt *Context) instanceHash(orig Type, targs []Type) string {
    69  	assert(ctxt != nil)
    70  	assert(orig != nil)
    71  	var buf bytes.Buffer
    72  
    73  	h := newTypeHasher(&buf, ctxt)
    74  	h.string(strconv.Itoa(ctxt.getID(orig)))
    75  	// Because we've already written the unique origin ID this call to h.typ is
    76  	// unnecessary, but we leave it for hash readability. It can be removed later
    77  	// if performance is an issue.
    78  	h.typ(orig)
    79  	if len(targs) > 0 {
    80  		// TODO(rfindley): consider asserting on isGeneric(typ) here, if and when
    81  		// isGeneric handles *Signature types.
    82  		h.typeList(targs)
    83  	}
    84  
    85  	return strings.ReplaceAll(buf.String(), " ", "#")
    86  }
    87  
    88  // lookup returns an existing instantiation of orig with targs, if it exists.
    89  // Otherwise, it returns nil.
    90  func (ctxt *Context) lookup(h string, orig Type, targs []Type) Type {
    91  	ctxt.mu.Lock()
    92  	defer ctxt.mu.Unlock()
    93  
    94  	for _, e := range ctxt.typeMap[h] {
    95  		if identicalInstance(orig, targs, e.orig, e.targs) {
    96  			return e.instance
    97  		}
    98  		if debug {
    99  			// Panic during development to surface any imperfections in our hash.
   100  			panic(fmt.Sprintf("non-identical instances: (orig: %s, targs: %v) and %s", orig, targs, e.instance))
   101  		}
   102  	}
   103  
   104  	return nil
   105  }
   106  
   107  // update de-duplicates n against previously seen types with the hash h.  If an
   108  // identical type is found with the type hash h, the previously seen type is
   109  // returned. Otherwise, n is returned, and recorded in the Context for the hash
   110  // h.
   111  func (ctxt *Context) update(h string, orig Type, targs []Type, inst Type) Type {
   112  	assert(inst != nil)
   113  
   114  	ctxt.mu.Lock()
   115  	defer ctxt.mu.Unlock()
   116  
   117  	for _, e := range ctxt.typeMap[h] {
   118  		if inst == nil || Identical(inst, e.instance) {
   119  			return e.instance
   120  		}
   121  		if debug {
   122  			// Panic during development to surface any imperfections in our hash.
   123  			panic(fmt.Sprintf("%s and %s are not identical", inst, e.instance))
   124  		}
   125  	}
   126  
   127  	ctxt.typeMap[h] = append(ctxt.typeMap[h], ctxtEntry{
   128  		orig:     orig,
   129  		targs:    targs,
   130  		instance: inst,
   131  	})
   132  
   133  	return inst
   134  }
   135  
   136  // getID returns a unique ID for the type t.
   137  func (ctxt *Context) getID(t Type) int {
   138  	ctxt.mu.Lock()
   139  	defer ctxt.mu.Unlock()
   140  	id, ok := ctxt.originIDs[t]
   141  	if !ok {
   142  		id = ctxt.nextID
   143  		ctxt.originIDs[t] = id
   144  		ctxt.nextID++
   145  	}
   146  	return id
   147  }
   148
View as plain text