vendor/github.com/moby/buildkit/solver/index.go

package solver

import (
	"sync"

	"github.com/moby/buildkit/identity"
)

// edgeIndex is a synchronous map for detecting edge collisions.
type edgeIndex struct {
	mu sync.Mutex

	items    map[string]*indexItem
	backRefs map[*edge]map[string]struct{}
}

type indexItem struct {
	edge  *edge
	links map[CacheInfoLink]map[string]struct{}
	deps  map[string]struct{}
}

func newEdgeIndex() *edgeIndex {
	return &edgeIndex{
		items:    map[string]*indexItem{},
		backRefs: map[*edge]map[string]struct{}{},
	}
}

func (ei *edgeIndex) Release(e *edge) {
	ei.mu.Lock()
	defer ei.mu.Unlock()

	for id := range ei.backRefs[e] {
		ei.releaseEdge(id, e)
	}
	delete(ei.backRefs, e)
}

func (ei *edgeIndex) releaseEdge(id string, e *edge) {
	item, ok := ei.items[id]
	if !ok {
		return
	}

	item.edge = nil

	if len(item.links) == 0 {
		for d := range item.deps {
			ei.releaseLink(d, id)
		}
		delete(ei.items, id)
	}
}

func (ei *edgeIndex) releaseLink(id, target string) {
	item, ok := ei.items[id]
	if !ok {
		return
	}

	for lid, links := range item.links {
		for check := range links {
			if check == target {
				delete(links, check)
			}
		}
		if len(links) == 0 {
			delete(item.links, lid)
		}
	}

	if item.edge == nil && len(item.links) == 0 {
		for d := range item.deps {
			ei.releaseLink(d, id)
		}
		delete(ei.items, id)
	}
}

func (ei *edgeIndex) LoadOrStore(k *CacheKey, e *edge) *edge {
	ei.mu.Lock()
	defer ei.mu.Unlock()

	// get all current edges that match the cachekey
	ids := ei.getAllMatches(k)

	var oldID string
	var old *edge

	for _, id := range ids {
		if item, ok := ei.items[id]; ok {
			if item.edge != e {
				oldID = id
				old = item.edge
			}
		}
	}

	if old != nil && !(!isIgnoreCache(old) && isIgnoreCache(e)) {
		ei.enforceLinked(oldID, k)
		return old
	}

	id := identity.NewID()
	if len(ids) > 0 {
		id = ids[0]
	}

	ei.enforceLinked(id, k)

	ei.items[id].edge = e
	backRefs, ok := ei.backRefs[e]
	if !ok {
		backRefs = map[string]struct{}{}
		ei.backRefs[e] = backRefs
	}
	backRefs[id] = struct{}{}

	return nil
}

// enforceLinked adds links from current ID to all dep keys
func (er *edgeIndex) enforceLinked(id string, k *CacheKey) {
	main, ok := er.items[id]
	if !ok {
		main = &indexItem{
			links: map[CacheInfoLink]map[string]struct{}{},
			deps:  map[string]struct{}{},
		}
		er.items[id] = main
	}

	deps := k.Deps()

	for i, dd := range deps {
		for _, d := range dd {
			ck := d.CacheKey.CacheKey
			er.enforceIndexID(ck)
			ll := CacheInfoLink{Input: Index(i), Digest: k.Digest(), Output: k.Output(), Selector: d.Selector}
			for _, ckID := range ck.indexIDs {
				if item, ok := er.items[ckID]; ok {
					links, ok := item.links[ll]
					if !ok {
						links = map[string]struct{}{}
						item.links[ll] = links
					}
					links[id] = struct{}{}
					main.deps[ckID] = struct{}{}
				}
			}
		}
	}
}

func (ei *edgeIndex) enforceIndexID(k *CacheKey) {
	if len(k.indexIDs) > 0 {
		return
	}

	matches := ei.getAllMatches(k)

	if len(matches) > 0 {
		k.indexIDs = matches
	} else {
		k.indexIDs = []string{identity.NewID()}
	}

	for _, id := range k.indexIDs {
		ei.enforceLinked(id, k)
	}
}

func (ei *edgeIndex) getAllMatches(k *CacheKey) []string {
	deps := k.Deps()

	if len(deps) == 0 {
		return []string{rootKey(k.Digest(), k.Output()).String()}
	}

	for _, dd := range deps {
		for _, k := range dd {
			ei.enforceIndexID(k.CacheKey.CacheKey)
		}
	}

	matches := map[string]struct{}{}

	for i, dd := range deps {
		if i == 0 {
			for _, d := range dd {
				ll := CacheInfoLink{Input: Index(i), Digest: k.Digest(), Output: k.Output(), Selector: d.Selector}
				for _, ckID := range d.CacheKey.CacheKey.indexIDs {
					item, ok := ei.items[ckID]
					if ok {
						for l := range item.links[ll] {
							matches[l] = struct{}{}
						}
					}
				}
			}
			continue
		}

		if len(matches) == 0 {
			break
		}

		for m := range matches {
			found := false
			for _, d := range dd {
				ll := CacheInfoLink{Input: Index(i), Digest: k.Digest(), Output: k.Output(), Selector: d.Selector}
				for _, ckID := range d.CacheKey.CacheKey.indexIDs {
					if item, ok := ei.items[ckID]; ok {
						if l, ok := item.links[ll]; ok {
							if _, ok := l[m]; ok {
								found = true
								break
							}
						}
					}
				}
			}

			if !found {
				delete(matches, m)
			}
		}
	}

	out := make([]string, 0, len(matches))

	for m := range matches {
		out = append(out, m)
	}

	return out
}

func isIgnoreCache(e *edge) bool {
	if e.edge.Vertex == nil {
		return false
	}
	return e.edge.Vertex.Options().IgnoreCache
}