context.go

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