builder.go

Documentation: golang.org/x/tools/go/callgraph/vta/internal/trie

     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 trie
     6  
     7  // Collision functions combine a left and right hand side (lhs and rhs) values
     8  // the two values are associated with the same key and produces the value that
     9  // will be stored for the key.
    10  //
    11  // Collision functions must be idempotent:
    12  //
    13  //	collision(x, x) == x for all x.
    14  //
    15  // Collisions functions may be applied whenever a value is inserted
    16  // or two maps are merged, or intersected.
    17  type Collision func(lhs interface{}, rhs interface{}) interface{}
    18  
    19  // TakeLhs always returns the left value in a collision.
    20  func TakeLhs(lhs, rhs interface{}) interface{} { return lhs }
    21  
    22  // TakeRhs always returns the right hand side in a collision.
    23  func TakeRhs(lhs, rhs interface{}) interface{} { return rhs }
    24  
    25  // Builder creates new Map. Each Builder has a unique Scope.
    26  //
    27  // IMPORTANT:  Nodes are hash-consed internally to reduce memory consumption. To
    28  // support hash-consing Builders keep an internal Map of all of the Maps that they
    29  // have created. To GC any of the Maps created by the Builder, all references to
    30  // the Builder must be dropped. This includes MutMaps.
    31  type Builder struct {
    32  	scope Scope
    33  
    34  	// hash-consing maps for each node type.
    35  	empty    *empty
    36  	leaves   map[leaf]*leaf
    37  	branches map[branch]*branch
    38  	// It may be possible to support more types of patricia tries
    39  	// (e.g. non-hash-consed) by making Builder an interface and abstracting
    40  	// the mkLeaf and mkBranch functions.
    41  }
    42  
    43  // NewBuilder creates a new Builder with a unique Scope.
    44  func NewBuilder() *Builder {
    45  	s := newScope()
    46  	return &Builder{
    47  		scope:    s,
    48  		empty:    &empty{s},
    49  		leaves:   make(map[leaf]*leaf),
    50  		branches: make(map[branch]*branch),
    51  	}
    52  }
    53  
    54  func (b *Builder) Scope() Scope { return b.scope }
    55  
    56  // Rescope changes the builder's scope to a new unique Scope.
    57  //
    58  // Any Maps created using the previous scope need to be Cloned
    59  // before any operation.
    60  //
    61  // This makes the old internals of the Builder eligible to be GC'ed.
    62  func (b *Builder) Rescope() {
    63  	s := newScope()
    64  	b.scope = s
    65  	b.empty = &empty{s}
    66  	b.leaves = make(map[leaf]*leaf)
    67  	b.branches = make(map[branch]*branch)
    68  }
    69  
    70  // Empty is the empty map.
    71  func (b *Builder) Empty() Map { return Map{b.Scope(), b.empty} }
    72  
    73  // InsertWith inserts a new association from k to v into the Map m to create a new map
    74  // in the current scope and handle collisions using the collision function c.
    75  //
    76  // This is roughly corresponds to updating a map[uint64]interface{} by:
    77  //
    78  //	if _, ok := m[k]; ok { m[k] = c(m[k], v} else { m[k] = v}
    79  //
    80  // An insertion or update happened whenever Insert(m, ...) != m .
    81  func (b *Builder) InsertWith(c Collision, m Map, k uint64, v interface{}) Map {
    82  	m = b.Clone(m)
    83  	return Map{b.Scope(), b.insert(c, m.n, b.mkLeaf(key(k), v), false)}
    84  }
    85  
    86  // Inserts a new association from key to value into the Map m to create
    87  // a new map in the current scope.
    88  //
    89  // If there was a previous value mapped by key, keep the previously mapped value.
    90  // This is roughly corresponds to updating a map[uint64]interface{} by:
    91  //
    92  //	if _, ok := m[k]; ok { m[k] = val }
    93  //
    94  // This is equivalent to b.Merge(m, b.Create({k: v})).
    95  func (b *Builder) Insert(m Map, k uint64, v interface{}) Map {
    96  	return b.InsertWith(TakeLhs, m, k, v)
    97  }
    98  
    99  // Updates a (key, value) in the map. This is roughly corresponds to
   100  // updating a map[uint64]interface{} by:
   101  //
   102  //	m[key] = val
   103  func (b *Builder) Update(m Map, key uint64, val interface{}) Map {
   104  	return b.InsertWith(TakeRhs, m, key, val)
   105  }
   106  
   107  // Merge two maps lhs and rhs to create a new map in the current scope.
   108  //
   109  // Whenever there is a key in both maps (a collision), the resulting value mapped by
   110  // the key will be `c(lhs[key], rhs[key])`.
   111  func (b *Builder) MergeWith(c Collision, lhs, rhs Map) Map {
   112  	lhs, rhs = b.Clone(lhs), b.Clone(rhs)
   113  	return Map{b.Scope(), b.merge(c, lhs.n, rhs.n)}
   114  }
   115  
   116  // Merge two maps lhs and rhs to create a new map in the current scope.
   117  //
   118  // Whenever there is a key in both maps (a collision), the resulting value mapped by
   119  // the key will be the value in lhs `b.Collision(lhs[key], rhs[key])`.
   120  func (b *Builder) Merge(lhs, rhs Map) Map {
   121  	return b.MergeWith(TakeLhs, lhs, rhs)
   122  }
   123  
   124  // Clone returns a Map that contains the same (key, value) elements
   125  // within b.Scope(), i.e. return m if m.Scope() == b.Scope() or return
   126  // a deep copy of m within b.Scope() otherwise.
   127  func (b *Builder) Clone(m Map) Map {
   128  	if m.Scope() == b.Scope() {
   129  		return m
   130  	} else if m.n == nil {
   131  		return Map{b.Scope(), b.empty}
   132  	}
   133  	return Map{b.Scope(), b.clone(m.n)}
   134  }
   135  func (b *Builder) clone(n node) node {
   136  	switch n := n.(type) {
   137  	case *empty:
   138  		return b.empty
   139  	case *leaf:
   140  		return b.mkLeaf(n.k, n.v)
   141  	case *branch:
   142  		return b.mkBranch(n.prefix, n.branching, b.clone(n.left), b.clone(n.right))
   143  	default:
   144  		panic("unreachable")
   145  	}
   146  }
   147  
   148  // Remove a key from a Map m and return the resulting Map.
   149  func (b *Builder) Remove(m Map, k uint64) Map {
   150  	m = b.Clone(m)
   151  	return Map{b.Scope(), b.remove(m.n, key(k))}
   152  }
   153  
   154  // Intersect Maps lhs and rhs and returns a map with all of the keys in
   155  // both lhs and rhs and the value comes from lhs, i.e.
   156  //
   157  //	{(k, lhs[k]) | k in lhs, k in rhs}.
   158  func (b *Builder) Intersect(lhs, rhs Map) Map {
   159  	return b.IntersectWith(TakeLhs, lhs, rhs)
   160  }
   161  
   162  // IntersectWith take lhs and rhs and returns the intersection
   163  // with the value coming from the collision function, i.e.
   164  //
   165  //	{(k, c(lhs[k], rhs[k]) ) | k in lhs, k in rhs}.
   166  //
   167  // The elements of the resulting map are always { <k, c(lhs[k], rhs[k]) > }
   168  // for each key k that a key in both lhs and rhs.
   169  func (b *Builder) IntersectWith(c Collision, lhs, rhs Map) Map {
   170  	l, r := b.Clone(lhs), b.Clone(rhs)
   171  	return Map{b.Scope(), b.intersect(c, l.n, r.n)}
   172  }
   173  
   174  // MutMap is a convenient wrapper for a Map and a *Builder that will be used to create
   175  // new Maps from it.
   176  type MutMap struct {
   177  	B *Builder
   178  	M Map
   179  }
   180  
   181  // MutEmpty is an empty MutMap for a builder.
   182  func (b *Builder) MutEmpty() MutMap {
   183  	return MutMap{b, b.Empty()}
   184  }
   185  
   186  // Insert an element into the map using the collision function for the builder.
   187  // Returns true if the element was inserted.
   188  func (mm *MutMap) Insert(k uint64, v interface{}) bool {
   189  	old := mm.M
   190  	mm.M = mm.B.Insert(old, k, v)
   191  	return old != mm.M
   192  }
   193  
   194  // Updates an element in the map. Returns true if the map was updated.
   195  func (mm *MutMap) Update(k uint64, v interface{}) bool {
   196  	old := mm.M
   197  	mm.M = mm.B.Update(old, k, v)
   198  	return old != mm.M
   199  }
   200  
   201  // Removes a key from the map. Returns true if the element was removed.
   202  func (mm *MutMap) Remove(k uint64) bool {
   203  	old := mm.M
   204  	mm.M = mm.B.Remove(old, k)
   205  	return old != mm.M
   206  }
   207  
   208  // Merge another map into the current one using the collision function
   209  // for the builder. Returns true if the map changed.
   210  func (mm *MutMap) Merge(other Map) bool {
   211  	old := mm.M
   212  	mm.M = mm.B.Merge(old, other)
   213  	return old != mm.M
   214  }
   215  
   216  // Intersect another map into the current one using the collision function
   217  // for the builder. Returns true if the map changed.
   218  func (mm *MutMap) Intersect(other Map) bool {
   219  	old := mm.M
   220  	mm.M = mm.B.Intersect(old, other)
   221  	return old != mm.M
   222  }
   223  
   224  func (b *Builder) Create(m map[uint64]interface{}) Map {
   225  	var leaves []*leaf
   226  	for k, v := range m {
   227  		leaves = append(leaves, b.mkLeaf(key(k), v))
   228  	}
   229  	return Map{b.Scope(), b.create(leaves)}
   230  }
   231  
   232  // Merge another map into the current one using the collision function
   233  // for the builder. Returns true if the map changed.
   234  func (mm *MutMap) MergeWith(c Collision, other Map) bool {
   235  	old := mm.M
   236  	mm.M = mm.B.MergeWith(c, old, other)
   237  	return old != mm.M
   238  }
   239  
   240  // creates a map for a collection of leaf nodes.
   241  func (b *Builder) create(leaves []*leaf) node {
   242  	n := len(leaves)
   243  	if n == 0 {
   244  		return b.empty
   245  	} else if n == 1 {
   246  		return leaves[0]
   247  	}
   248  	// Note: we can do a more sophisicated algorithm by:
   249  	// - sorting the leaves ahead of time,
   250  	// - taking the prefix and branching bit of the min and max key,
   251  	// - binary searching for the branching bit,
   252  	// - splitting exactly where the branch will be, and
   253  	// - making the branch node for this prefix + branching bit.
   254  	// Skipping until this is a performance bottleneck.
   255  
   256  	m := n / 2 // (n >= 2) ==> 1 <= m < n
   257  	l, r := leaves[:m], leaves[m:]
   258  	return b.merge(nil, b.create(l), b.create(r))
   259  }
   260  
   261  // mkLeaf returns the hash-consed representative of (k, v) in the current scope.
   262  func (b *Builder) mkLeaf(k key, v interface{}) *leaf {
   263  	l := &leaf{k: k, v: v}
   264  	if rep, ok := b.leaves[*l]; ok {
   265  		return rep
   266  	}
   267  	b.leaves[*l] = l
   268  	return l
   269  }
   270  
   271  // mkBranch returns the hash-consed representative of the tuple
   272  //
   273  //	(prefix, branch, left, right)
   274  //
   275  // in the current scope.
   276  func (b *Builder) mkBranch(p prefix, bp bitpos, left node, right node) *branch {
   277  	br := &branch{
   278  		sz:        left.size() + right.size(),
   279  		prefix:    p,
   280  		branching: bp,
   281  		left:      left,
   282  		right:     right,
   283  	}
   284  	if rep, ok := b.branches[*br]; ok {
   285  		return rep
   286  	}
   287  	b.branches[*br] = br
   288  	return br
   289  }
   290  
   291  // join two maps with prefixes p0 and p1 that are *known* to disagree.
   292  func (b *Builder) join(p0 prefix, t0 node, p1 prefix, t1 node) *branch {
   293  	m := branchingBit(p0, p1)
   294  	var left, right node
   295  	if zeroBit(p0, m) {
   296  		left, right = t0, t1
   297  	} else {
   298  		left, right = t1, t0
   299  	}
   300  	prefix := mask(p0, m)
   301  	return b.mkBranch(prefix, m, left, right)
   302  }
   303  
   304  // collide two leaves with the same key to create a leaf
   305  // with the collided value.
   306  func (b *Builder) collide(c Collision, left, right *leaf) *leaf {
   307  	if left == right {
   308  		return left // c is idempotent: c(x, x) == x
   309  	}
   310  	val := left.v // keep the left value by default if c is nil
   311  	if c != nil {
   312  		val = c(left.v, right.v)
   313  	}
   314  	switch val {
   315  	case left.v:
   316  		return left
   317  	case right.v:
   318  		return right
   319  	default:
   320  		return b.mkLeaf(left.k, val)
   321  	}
   322  }
   323  
   324  // inserts a leaf l into a map m and returns the resulting map.
   325  // When lhs is true, l is the left hand side in a collision.
   326  // Both l and m are in the current scope.
   327  func (b *Builder) insert(c Collision, m node, l *leaf, lhs bool) node {
   328  	switch m := m.(type) {
   329  	case *empty:
   330  		return l
   331  	case *leaf:
   332  		if m.k == l.k {
   333  			left, right := l, m
   334  			if !lhs {
   335  				left, right = right, left
   336  			}
   337  			return b.collide(c, left, right)
   338  		}
   339  		return b.join(prefix(l.k), l, prefix(m.k), m)
   340  	case *branch:
   341  		// fallthrough
   342  	}
   343  	// m is a branch
   344  	br := m.(*branch)
   345  	if !matchPrefix(prefix(l.k), br.prefix, br.branching) {
   346  		return b.join(prefix(l.k), l, br.prefix, br)
   347  	}
   348  	var left, right node
   349  	if zeroBit(prefix(l.k), br.branching) {
   350  		left, right = b.insert(c, br.left, l, lhs), br.right
   351  	} else {
   352  		left, right = br.left, b.insert(c, br.right, l, lhs)
   353  	}
   354  	if left == br.left && right == br.right {
   355  		return m
   356  	}
   357  	return b.mkBranch(br.prefix, br.branching, left, right)
   358  }
   359  
   360  // merge two maps in the current scope.
   361  func (b *Builder) merge(c Collision, lhs, rhs node) node {
   362  	if lhs == rhs {
   363  		return lhs
   364  	}
   365  	switch lhs := lhs.(type) {
   366  	case *empty:
   367  		return rhs
   368  	case *leaf:
   369  		return b.insert(c, rhs, lhs, true)
   370  	case *branch:
   371  		switch rhs := rhs.(type) {
   372  		case *empty:
   373  			return lhs
   374  		case *leaf:
   375  			return b.insert(c, lhs, rhs, false)
   376  		case *branch:
   377  			// fallthrough
   378  		}
   379  	}
   380  
   381  	// Last remaining case is branch merging.
   382  	// For brevity, we adopt the Okasaki and Gill naming conventions
   383  	// for branching and prefixes.
   384  	s, t := lhs.(*branch), rhs.(*branch)
   385  	p, m := s.prefix, s.branching
   386  	q, n := t.prefix, t.branching
   387  
   388  	if m == n && p == q { // prefixes are identical.
   389  		left, right := b.merge(c, s.left, t.left), b.merge(c, s.right, t.right)
   390  		return b.mkBranch(p, m, left, right)
   391  	}
   392  	if !prefixesOverlap(p, m, q, n) {
   393  		return b.join(p, s, q, t) // prefixes are disjoint.
   394  	}
   395  	// prefixesOverlap(p, m, q, n) && !(m ==n && p == q)
   396  	// By prefixesOverlap(...), either:
   397  	//   higher(m, n) && matchPrefix(q, p, m), or
   398  	//   higher(n, m) && matchPrefix(p, q, n)
   399  	// So either s or t may can be merged with one branch or the other.
   400  	switch {
   401  	case ord(m, n) && zeroBit(q, m):
   402  		return b.mkBranch(p, m, b.merge(c, s.left, t), s.right)
   403  	case ord(m, n) && !zeroBit(q, m):
   404  		return b.mkBranch(p, m, s.left, b.merge(c, s.right, t))
   405  	case ord(n, m) && zeroBit(p, n):
   406  		return b.mkBranch(q, n, b.merge(c, s, t.left), t.right)
   407  	default:
   408  		return b.mkBranch(q, n, t.left, b.merge(c, s, t.right))
   409  	}
   410  }
   411  
   412  func (b *Builder) remove(m node, k key) node {
   413  	switch m := m.(type) {
   414  	case *empty:
   415  		return m
   416  	case *leaf:
   417  		if m.k == k {
   418  			return b.empty
   419  		}
   420  		return m
   421  	case *branch:
   422  		// fallthrough
   423  	}
   424  	br := m.(*branch)
   425  	kp := prefix(k)
   426  	if !matchPrefix(kp, br.prefix, br.branching) {
   427  		// The prefix does not match. kp is not in br.
   428  		return br
   429  	}
   430  	// the prefix matches. try to remove from the left or right branch.
   431  	left, right := br.left, br.right
   432  	if zeroBit(kp, br.branching) {
   433  		left = b.remove(left, k) // k may be in the left branch.
   434  	} else {
   435  		right = b.remove(right, k) // k may be in the right branch.
   436  	}
   437  	if left == br.left && right == br.right {
   438  		return br // no update
   439  	} else if _, ok := left.(*empty); ok {
   440  		return right // left updated and is empty.
   441  	} else if _, ok := right.(*empty); ok {
   442  		return left // right updated and is empty.
   443  	}
   444  	// Either left or right updated. Both left and right are not empty.
   445  	// The left and right branches still share the same prefix and disagree
   446  	// on the same branching bit. It is safe to directly create the branch.
   447  	return b.mkBranch(br.prefix, br.branching, left, right)
   448  }
   449  
   450  func (b *Builder) intersect(c Collision, l, r node) node {
   451  	if l == r {
   452  		return l
   453  	}
   454  	switch l := l.(type) {
   455  	case *empty:
   456  		return b.empty
   457  	case *leaf:
   458  		if rleaf := r.find(l.k); rleaf != nil {
   459  			return b.collide(c, l, rleaf)
   460  		}
   461  		return b.empty
   462  	case *branch:
   463  		switch r := r.(type) {
   464  		case *empty:
   465  			return b.empty
   466  		case *leaf:
   467  			if lleaf := l.find(r.k); lleaf != nil {
   468  				return b.collide(c, lleaf, r)
   469  			}
   470  			return b.empty
   471  		case *branch:
   472  			// fallthrough
   473  		}
   474  	}
   475  	// Last remaining case is branch intersection.
   476  	s, t := l.(*branch), r.(*branch)
   477  	p, m := s.prefix, s.branching
   478  	q, n := t.prefix, t.branching
   479  
   480  	if m == n && p == q {
   481  		// prefixes are identical.
   482  		left, right := b.intersect(c, s.left, t.left), b.intersect(c, s.right, t.right)
   483  		if _, ok := left.(*empty); ok {
   484  			return right
   485  		} else if _, ok := right.(*empty); ok {
   486  			return left
   487  		}
   488  		// The left and right branches are both non-empty.
   489  		// They still share the same prefix and disagree on the same branching bit.
   490  		// It is safe to directly create the branch.
   491  		return b.mkBranch(p, m, left, right)
   492  	}
   493  
   494  	if !prefixesOverlap(p, m, q, n) {
   495  		return b.empty // The prefixes share no keys.
   496  	}
   497  	// prefixesOverlap(p, m, q, n) && !(m ==n && p == q)
   498  	// By prefixesOverlap(...), either:
   499  	//   ord(m, n) && matchPrefix(q, p, m), or
   500  	//   ord(n, m) && matchPrefix(p, q, n)
   501  	// So either s or t may be a strict subtree of the other.
   502  	var lhs, rhs node
   503  	switch {
   504  	case ord(m, n) && zeroBit(q, m):
   505  		lhs, rhs = s.left, t
   506  	case ord(m, n) && !zeroBit(q, m):
   507  		lhs, rhs = s.right, t
   508  	case ord(n, m) && zeroBit(p, n):
   509  		lhs, rhs = s, t.left
   510  	default:
   511  		lhs, rhs = s, t.right
   512  	}
   513  	return b.intersect(c, lhs, rhs)
   514  }
   515
View as plain text