.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/internal/memoize/memoize.go

   1 // Copyright 2019 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 memoize supports memoizing the return values of functions with
   6 // idempotent results that are expensive to compute.
   7 //
   8 // To use this package, build a store and use it to acquire handles with the
   9 // Bind method.
  10 //
  11 package memoize
  12
  13 import (
  14         "context"
  15         "flag"
  16         "fmt"
  17         "reflect"
  18         "sync"
  19         "sync/atomic"
  20
  21         "golang.org/x/tools/internal/xcontext"
  22 )
  23
  24 var (
  25         panicOnDestroyed = flag.Bool("memoize_panic_on_destroyed", false,
  26                 "Panic when a destroyed generation is read rather than returning an error. "+
  27                         "Panicking may make it easier to debug lifetime errors, especially when "+
  28                         "used with GOTRACEBACK=crash to see all running goroutines.")
  29 )
  30
  31 // Store binds keys to functions, returning handles that can be used to access
  32 // the functions results.
  33 type Store struct {
  34         mu sync.Mutex
  35         // handles is the set of values stored.
  36         handles map[interface{}]*Handle
  37
  38         // generations is the set of generations live in this store.
  39         generations map[*Generation]struct{}
  40 }
  41
  42 // Generation creates a new Generation associated with s. Destroy must be
  43 // called on the returned Generation once it is no longer in use. name is
  44 // for debugging purposes only.
  45 func (s *Store) Generation(name string) *Generation {
  46         s.mu.Lock()
  47         defer s.mu.Unlock()
  48         if s.handles == nil {
  49                 s.handles = map[interface{}]*Handle{}
  50                 s.generations = map[*Generation]struct{}{}
  51         }
  52         g := &Generation{store: s, name: name}
  53         s.generations[g] = struct{}{}
  54         return g
  55 }
  56
  57 // A Generation is a logical point in time of the cache life-cycle. Cache
  58 // entries associated with a Generation will not be removed until the
  59 // Generation is destroyed.
  60 type Generation struct {
  61         // destroyed is 1 after the generation is destroyed. Atomic.
  62         destroyed uint32
  63         store     *Store
  64         name      string
  65         // wg tracks the reference count of this generation.
  66         wg sync.WaitGroup
  67 }
  68
  69 // Destroy waits for all operations referencing g to complete, then removes
  70 // all references to g from cache entries. Cache entries that no longer
  71 // reference any non-destroyed generation are removed. Destroy must be called
  72 // exactly once for each generation.
  73 func (g *Generation) Destroy() {
  74         g.wg.Wait()
  75         atomic.StoreUint32(&g.destroyed, 1)
  76         g.store.mu.Lock()
  77         defer g.store.mu.Unlock()
  78         for k, e := range g.store.handles {
  79                 e.mu.Lock()
  80                 if _, ok := e.generations[g]; ok {
  81                         delete(e.generations, g) // delete even if it's dead, in case of dangling references to the entry.
  82                         if len(e.generations) == 0 {
  83                                 delete(g.store.handles, k)
  84                                 e.state = stateDestroyed
  85                         }
  86                 }
  87                 e.mu.Unlock()
  88         }
  89         delete(g.store.generations, g)
  90 }
  91
  92 // Acquire creates a new reference to g, and returns a func to release that
  93 // reference.
  94 func (g *Generation) Acquire(ctx context.Context) func() {
  95         destroyed := atomic.LoadUint32(&g.destroyed)
  96         if ctx.Err() != nil {
  97                 return func() {}
  98         }
  99         if destroyed != 0 {
 100                 panic("acquire on destroyed generation " + g.name)
 101         }
 102         g.wg.Add(1)
 103         return g.wg.Done
 104 }
 105
 106 // Arg is a marker interface that can be embedded to indicate a type is
 107 // intended for use as a Function argument.
 108 type Arg interface{ memoizeArg() }
 109
 110 // Function is the type for functions that can be memoized.
 111 // The result must be a pointer.
 112 type Function func(ctx context.Context, arg Arg) interface{}
 113
 114 type state int
 115
 116 const (
 117         stateIdle = iota
 118         stateRunning
 119         stateCompleted
 120         stateDestroyed
 121 )
 122
 123 // Handle is returned from a store when a key is bound to a function.
 124 // It is then used to access the results of that function.
 125 //
 126 // A Handle starts out in idle state, waiting for something to demand its
 127 // evaluation. It then transitions into running state. While it's running,
 128 // waiters tracks the number of Get calls waiting for a result, and the done
 129 // channel is used to notify waiters of the next state transition. Once the
 130 // evaluation finishes, value is set, state changes to completed, and done
 131 // is closed, unblocking waiters. Alternatively, as Get calls are cancelled,
 132 // they decrement waiters. If it drops to zero, the inner context is cancelled,
 133 // computation is abandoned, and state resets to idle to start the process over
 134 // again.
 135 type Handle struct {
 136         key interface{}
 137         mu  sync.Mutex
 138
 139         // generations is the set of generations in which this handle is valid.
 140         generations map[*Generation]struct{}
 141
 142         state state
 143         // done is set in running state, and closed when exiting it.
 144         done chan struct{}
 145         // cancel is set in running state. It cancels computation.
 146         cancel context.CancelFunc
 147         // waiters is the number of Gets outstanding.
 148         waiters uint
 149         // the function that will be used to populate the value
 150         function Function
 151         // value is set in completed state.
 152         value interface{}
 153 }
 154
 155 // Bind returns a handle for the given key and function.
 156 //
 157 // Each call to bind will return the same handle if it is already bound.
 158 // Bind will always return a valid handle, creating one if needed.
 159 // Each key can only have one handle at any given time.
 160 // The value will be held at least until the associated generation is destroyed.
 161 // Bind does not cause the value to be generated.
 162 func (g *Generation) Bind(key interface{}, function Function) *Handle {
 163         // panic early if the function is nil
 164         // it would panic later anyway, but in a way that was much harder to debug
 165         if function == nil {
 166                 panic("the function passed to bind must not be nil")
 167         }
 168         if atomic.LoadUint32(&g.destroyed) != 0 {
 169                 panic("operation on destroyed generation " + g.name)
 170         }
 171         g.store.mu.Lock()
 172         defer g.store.mu.Unlock()
 173         h, ok := g.store.handles[key]
 174         if !ok {
 175                 h := &Handle{
 176                         key:         key,
 177                         function:    function,
 178                         generations: map[*Generation]struct{}{g: {}},
 179                 }
 180                 g.store.handles[key] = h
 181                 return h
 182         }
 183         h.mu.Lock()
 184         defer h.mu.Unlock()
 185         if _, ok := h.generations[g]; !ok {
 186                 h.generations[g] = struct{}{}
 187         }
 188         return h
 189 }
 190
 191 // Stats returns the number of each type of value in the store.
 192 func (s *Store) Stats() map[reflect.Type]int {
 193         s.mu.Lock()
 194         defer s.mu.Unlock()
 195
 196         result := map[reflect.Type]int{}
 197         for k := range s.handles {
 198                 result[reflect.TypeOf(k)]++
 199         }
 200         return result
 201 }
 202
 203 // DebugOnlyIterate iterates through all live cache entries and calls f on them.
 204 // It should only be used for debugging purposes.
 205 func (s *Store) DebugOnlyIterate(f func(k, v interface{})) {
 206         s.mu.Lock()
 207         defer s.mu.Unlock()
 208
 209         for k, e := range s.handles {
 210                 var v interface{}
 211                 e.mu.Lock()
 212                 if e.state == stateCompleted {
 213                         v = e.value
 214                 }
 215                 e.mu.Unlock()
 216                 if v == nil {
 217                         continue
 218                 }
 219                 f(k, v)
 220         }
 221 }
 222
 223 func (g *Generation) Inherit(h *Handle) {
 224         if atomic.LoadUint32(&g.destroyed) != 0 {
 225                 panic("inherit on destroyed generation " + g.name)
 226         }
 227
 228         h.mu.Lock()
 229         defer h.mu.Unlock()
 230         if h.state == stateDestroyed {
 231                 panic(fmt.Sprintf("inheriting destroyed handle %#v (type %T) into generation %v", h.key, h.key, g.name))
 232         }
 233         h.generations[g] = struct{}{}
 234 }
 235
 236 // Cached returns the value associated with a handle.
 237 //
 238 // It will never cause the value to be generated.
 239 // It will return the cached value, if present.
 240 func (h *Handle) Cached(g *Generation) interface{} {
 241         h.mu.Lock()
 242         defer h.mu.Unlock()
 243         if _, ok := h.generations[g]; !ok {
 244                 return nil
 245         }
 246         if h.state == stateCompleted {
 247                 return h.value
 248         }
 249         return nil
 250 }
 251
 252 // Get returns the value associated with a handle.
 253 //
 254 // If the value is not yet ready, the underlying function will be invoked.
 255 // If ctx is cancelled, Get returns nil.
 256 func (h *Handle) Get(ctx context.Context, g *Generation, arg Arg) (interface{}, error) {
 257         release := g.Acquire(ctx)
 258         defer release()
 259
 260         if ctx.Err() != nil {
 261                 return nil, ctx.Err()
 262         }
 263         h.mu.Lock()
 264         if _, ok := h.generations[g]; !ok {
 265                 h.mu.Unlock()
 266
 267                 err := fmt.Errorf("reading key %#v: generation %v is not known", h.key, g.name)
 268                 if *panicOnDestroyed && ctx.Err() != nil {
 269                         panic(err)
 270                 }
 271                 return nil, err
 272         }
 273         switch h.state {
 274         case stateIdle:
 275                 return h.run(ctx, g, arg)
 276         case stateRunning:
 277                 return h.wait(ctx)
 278         case stateCompleted:
 279                 defer h.mu.Unlock()
 280                 return h.value, nil
 281         case stateDestroyed:
 282                 h.mu.Unlock()
 283                 err := fmt.Errorf("Get on destroyed entry %#v (type %T) in generation %v", h.key, h.key, g.name)
 284                 if *panicOnDestroyed {
 285                         panic(err)
 286                 }
 287                 return nil, err
 288         default:
 289                 panic("unknown state")
 290         }
 291 }
 292
 293 // run starts h.function and returns the result. h.mu must be locked.
 294 func (h *Handle) run(ctx context.Context, g *Generation, arg Arg) (interface{}, error) {
 295         childCtx, cancel := context.WithCancel(xcontext.Detach(ctx))
 296         h.cancel = cancel
 297         h.state = stateRunning
 298         h.done = make(chan struct{})
 299         function := h.function // Read under the lock
 300
 301         // Make sure that the generation isn't destroyed while we're running in it.
 302         release := g.Acquire(ctx)
 303         go func() {
 304                 defer release()
 305                 // Just in case the function does something expensive without checking
 306                 // the context, double-check we're still alive.
 307                 if childCtx.Err() != nil {
 308                         return
 309                 }
 310                 v := function(childCtx, arg)
 311                 if childCtx.Err() != nil {
 312                         return
 313                 }
 314
 315                 h.mu.Lock()
 316                 defer h.mu.Unlock()
 317                 // It's theoretically possible that the handle has been cancelled out
 318                 // of the run that started us, and then started running again since we
 319                 // checked childCtx above. Even so, that should be harmless, since each
 320                 // run should produce the same results.
 321                 if h.state != stateRunning {
 322                         return
 323                 }
 324                 h.value = v
 325                 h.function = nil
 326                 h.state = stateCompleted
 327                 close(h.done)
 328         }()
 329
 330         return h.wait(ctx)
 331 }
 332
 333 // wait waits for the value to be computed, or ctx to be cancelled. h.mu must be locked.
 334 func (h *Handle) wait(ctx context.Context) (interface{}, error) {
 335         h.waiters++
 336         done := h.done
 337         h.mu.Unlock()
 338
 339         select {
 340         case <-done:
 341                 h.mu.Lock()
 342                 defer h.mu.Unlock()
 343                 if h.state == stateCompleted {
 344                         return h.value, nil
 345                 }
 346                 return nil, nil
 347         case <-ctx.Done():
 348                 h.mu.Lock()
 349                 defer h.mu.Unlock()
 350                 h.waiters--
 351                 if h.waiters == 0 && h.state == stateRunning {
 352                         h.cancel()
 353                         close(h.done)
 354                         h.state = stateIdle
 355                         h.done = nil
 356                         h.cancel = nil
 357                 }
 358                 return nil, ctx.Err()
 359         }
 360 }