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 types
     6  
     7  import (
     8  	"bytes"
     9  	"fmt"
    10  	"strconv"
    11  	"strings"
    12  	"sync"
    13  )
    14  
    15  // A Context is an opaque type checking context. It may be used to share
    16  // identical type instances across type-checked packages or calls to
    17  // Instantiate. Contexts are safe for concurrent use.
    18  //
    19  // The use of a shared context does not guarantee that identical instances are
    20  // deduplicated in all cases.
    21  type Context struct {
    22  	mu        sync.Mutex
    23  	typeMap   map[string][]ctxtEntry // type hash -> instances entries
    24  	nextID    int                    // next unique ID
    25  	originIDs map[Type]int           // origin type -> unique ID
    26  }
    27  
    28  type ctxtEntry struct {
    29  	orig     Type
    30  	targs    []Type
    31  	instance Type // = orig[targs]
    32  }
    33  
    34  // NewContext creates a new Context.
    35  func NewContext() *Context {
    36  	return &Context{
    37  		typeMap:   make(map[string][]ctxtEntry),
    38  		originIDs: make(map[Type]int),
    39  	}
    40  }
    41  
    42  // instanceHash returns a string representation of typ instantiated with targs.
    43  // The hash should be a perfect hash, though out of caution the type checker
    44  // does not assume this. The result is guaranteed to not contain blanks.
    45  func (ctxt *Context) instanceHash(orig Type, targs []Type) string {
    46  	assert(ctxt != nil)
    47  	assert(orig != nil)
    48  	var buf bytes.Buffer
    49  
    50  	h := newTypeHasher(&buf, ctxt)
    51  	h.string(strconv.Itoa(ctxt.getID(orig)))
    52  	// Because we've already written the unique origin ID this call to h.typ is
    53  	// unnecessary, but we leave it for hash readability. It can be removed later
    54  	// if performance is an issue.
    55  	h.typ(orig)
    56  	if len(targs) > 0 {
    57  		// TODO(rfindley): consider asserting on isGeneric(typ) here, if and when
    58  		// isGeneric handles *Signature types.
    59  		h.typeList(targs)
    60  	}
    61  
    62  	return strings.Replace(buf.String(), " ", "#", -1) // ReplaceAll is not available in Go1.4
    63  }
    64  
    65  // lookup returns an existing instantiation of orig with targs, if it exists.
    66  // Otherwise, it returns nil.
    67  func (ctxt *Context) lookup(h string, orig Type, targs []Type) Type {
    68  	ctxt.mu.Lock()
    69  	defer ctxt.mu.Unlock()
    70  
    71  	for _, e := range ctxt.typeMap[h] {
    72  		if identicalInstance(orig, targs, e.orig, e.targs) {
    73  			return e.instance
    74  		}
    75  		if debug {
    76  			// Panic during development to surface any imperfections in our hash.
    77  			panic(fmt.Sprintf("non-identical instances: (orig: %s, targs: %v) and %s", orig, targs, e.instance))
    78  		}
    79  	}
    80  
    81  	return nil
    82  }
    83  
    84  // update de-duplicates n against previously seen types with the hash h.  If an
    85  // identical type is found with the type hash h, the previously seen type is
    86  // returned. Otherwise, n is returned, and recorded in the Context for the hash
    87  // h.
    88  func (ctxt *Context) update(h string, orig Type, targs []Type, inst Type) Type {
    89  	assert(inst != nil)
    90  
    91  	ctxt.mu.Lock()
    92  	defer ctxt.mu.Unlock()
    93  
    94  	for _, e := range ctxt.typeMap[h] {
    95  		if inst == nil || Identical(inst, e.instance) {
    96  			return e.instance
    97  		}
    98  		if debug {
    99  			// Panic during development to surface any imperfections in our hash.
   100  			panic(fmt.Sprintf("%s and %s are not identical", inst, e.instance))
   101  		}
   102  	}
   103  
   104  	ctxt.typeMap[h] = append(ctxt.typeMap[h], ctxtEntry{
   105  		orig:     orig,
   106  		targs:    targs,
   107  		instance: inst,
   108  	})
   109  
   110  	return inst
   111  }
   112  
   113  // getID returns a unique ID for the type t.
   114  func (ctxt *Context) getID(t Type) int {
   115  	ctxt.mu.Lock()
   116  	defer ctxt.mu.Unlock()
   117  	id, ok := ctxt.originIDs[t]
   118  	if !ok {
   119  		id = ctxt.nextID
   120  		ctxt.originIDs[t] = id
   121  		ctxt.nextID++
   122  	}
   123  	return id
   124  }
   125
View as plain text