unsetinternal

// unsetRefs removes all internal node references(hashnode). It
// should be called after a trie is constructed with two edge proofs.
//
// It's the key step for range proof. All visited nodes should be
// marked dirty since the node content might be modified. Besides
// it can happen that some fullnodes only have one child which is
// disallowed. But if the proof is valid, the missing children will
// be filled, otherwise the entire trie will be thrown anyway.
func unsetRefs(root node, remove bool, removeLeft bool) {
	switch rn := root.(type) {
	case *fullNode:
		first, last := -1, -1
		for i := 0; i < 16; i++ {
			switch rn.Children[i].(type) {
			case *fullNode, *shortNode:
				// Filter out small embedded node
				hasher := newHasher(false)
				_, hashed := hasher.proofHash(rn.Children[i])
				if _, ok := hashed.(hashNode); ok {
					if first != -1 && last != -1 {
						panic("more than two extension children")
					}
					if first == -1 {
						first = i
					} else {
						last = i
					}
				}
				returnHasherToPool(hasher)
			}
		}
		// It can happen that all children of parent node(fullnode)
		// are embedded small nodes. Skip in this case.
		//
		// todo(493456442) e.g. fullnode [0: v0, 1: v1, ..., 15: v15]
		// but in the response range, only v0-v5, v7-v15 are given(v6
		// is discarded), but in this case the re-constructued hash is
		// still correct since v6 it's an embedded node.
		if first == -1 && last == -1 {
			return
		}
		if first != -1 && last != -1 {
			if remove {
				panic("shouldn't unset refs before the fork point")
			}
			// Find the fork point! Unset all intermediate references
			for i := first + 1; i < last; i++ {
				if _, ok := rn.Children[i].(hashNode); ok {
					rn.Children[i] = nil
				}
			}
			rn.flags = nodeFlag{dirty: true}
			unsetRefs(rn.Children[first], true, false)
			unsetRefs(rn.Children[last], true, true)
		} else if remove {
			if removeLeft {
				for i := 0; i < first; i++ {
					if _, ok := rn.Children[i].(hashNode); ok {
						rn.Children[i] = nil
					}
				}
				rn.flags = nodeFlag{dirty: true}
				unsetRefs(rn.Children[first], true, true)
			} else {
				for i := first + 1; i < 16; i++ {
					if _, ok := rn.Children[i].(hashNode); ok {
						rn.Children[i] = nil
					}
				}
				rn.flags = nodeFlag{dirty: true}
				unsetRefs(rn.Children[first], true, false)
			}
		} else {
			// Step down, the fork hasn't been found
			rn.flags = nodeFlag{dirty: true}
			unsetRefs(rn.Children[first], false, false)
		}
	case *shortNode:
		rn.flags = nodeFlag{dirty: true}
		unsetRefs(rn.Val, remove, removeLeft)
	case valueNode:
		return
	case hashNode:
		panic("it shouldn't happen")
	}
}