Binary Tree as immutable state backing, with rebinding pattern for minimal copy-on-write modifications. Every merkle cached *by default*.

experimental.go

package experimental

import "encoding/binary"

// Experimental code! Everything a tree and cached by default.


type HashFn func(a Root, b Root) Root

// A link is called to rebind a value
type Link func(v Node)

type Root [32]byte

func (s *Root) ComputeRoot(h HashFn) Root {
	return *s
}

type Node interface {
	ComputeRoot(h HashFn) Root
}

// An immutable (L, R) pair with a link to the holding node.
// If L or R changes, the link is used to bind a new (L, *R) or (*L, R) pair in the holding value.
type Commit struct {
	// TODO: instead of value + bool, it could also be a pointer (nil case == Computed false).
	//  But more objects/indirection/allocations.
	Value Root
	Computed bool // true if Value is set to H(L, R)
	Link Link
	Left Node
	Right Node
}

func (c *Commit) ComputeRoot(h HashFn) Root {
	if c.Computed {
		return c.Value
	}
	if c.Left == nil || c.Right == nil {
		panic("invalid state, cannot have left without right")
	}
	c.Value = h(c.Left.ComputeRoot(h), c.Right.ComputeRoot(h))
	c.Computed = true
	return c.Value
}

func (c *Commit) RebindLeft(v Node) {
	c.Link(&Commit{
		Value:    Root{},
		Computed: false,
		Link:     c.Link,
		Left:     v,
		Right:    c.Right,
	})
}

func (c *Commit) RebindRight(v Node) {
	c.Link(&Commit{
		Value:    Root{},
		Computed: false,
		Link:     c.Link,
		Left:     c.Left,
		Right:    v,
	})
}

func (c *Commit) Expand() {
	next := &Commit{
		Value:    Root{},
		Computed: false,
		Link:     c.Link,
		Left:     nil,
		Right:    nil,
	}
	left := &Commit{
		Value:    Root{},
		Computed: false,
		Link:     next.RebindLeft,
		Left:     nil,
		Right:    nil,
	}
	right := &Commit{
		Value:    Root{},
		Computed: false,
		Link:     next.RebindRight,
		Left:     nil,
		Right:    nil,
	}
	next.Left = left
	next.Right = right
	c.Link(next)
}

var zeroHashes = make([]Root, 100)
// TODO init zero hashes

// Unsafe! Modifies L and R, without triggering a rebind in the parent
func (c *Commit) ExpandInplaceTo(to uint64, depth uint8) {
	c.Computed = false
	if depth == 1 {
		c.Left = &Root{}
		c.Right = &Root{}
	} else {
		pivot := uint64(1) << depth
		c.Left = &Commit{
			Value:    Root{},
			Computed: false,
			Link:     c.RebindLeft,
			Left:     nil,
			Right:    nil,
		}
		if to < pivot {
			c.Left.(*Commit).ExpandInplaceTo(to, depth - 1)
			c.Right = &zeroHashes[depth]
		} else {
			c.Left.(*Commit).ExpandInplaceTo(pivot, depth - 1)
			c.Right = &Commit{
				Value:    Root{},
				Computed: false,
				Link:     c.RebindRight,
				Left:     nil,
				Right:    nil,
			}
			c.Right.(*Commit).ExpandInplaceTo(to &^ pivot, depth - 1)
		}
	}
}

func (c *Commit) Navigate(target uint64, depth uint8) (Node, Link) {
	if target == 0 {
		return c.Left, c.RebindLeft
	}
	if target == 1 {
		return c.Right, c.RebindRight
	}
	if pivot := uint64(1) << depth; target < pivot {
		return c.Left.(*Commit).Navigate(target, depth-1)
	} else {
		return c.Right.(*Commit).Navigate(target &^ pivot, depth-1)
	}
}

// Temporarily decouples the commit from its parent to scope modifications within the "work" callback.
// Then rebinds to the parent, and propagates changes if there were any.
func (c *Commit) Batch(work func()) {
	link := c.Link
	var next Node
	c.Link = func(v Node) {
		next = v
	}
	work()
	if next != nil {
		link(next)
	}
	c.Link = link
}






// Example usage:
//  - anything can be a node
//  - commits are wrapped with navigation to fetch getter/setter pairs of containers.
//  - commits can be made read-only
//  - modifications can be batched


type Slot uint64

func (s Slot) ComputeRoot(h HashFn) (out Root) {
	binary.LittleEndian.PutUint64(out[:], uint64(s))
	return
}

type Block struct {
	root Commit
}

type Body Commit

func (b *Block) Slot() (Slot, Link) {
	getter, setter := b.root.Navigate(0, 8)
	return getter.(Slot), setter
}

func (b *Block) Body() (*Body, Link) {
	getter, setter := b.root.Navigate(1, 8)
	return (*Body)(getter.(*Commit)), setter
}

// TODO more examples
// TODO parse commit structure from multiproof backing