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 // 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.Replace(buf.String(), " ", "#", -1) // ReplaceAll is not available in Go1.4 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 n against previously seen types with the hash h. If an 105 // identical type is found with the type hash h, the previously seen type is 106 // returned. Otherwise, n is returned, and recorded in the Context for the hash 107 // 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