synthetic

Documentation

Overview

Package synthetic generates a deterministic, content-addressed Merkle DAG.

It exists so the library and its renderer have something to draw without reading anything off disk, and so tests have a graph of arbitrary size whose shape is reproducible from a seed.

Nodes are built bottom-up and addressed by the hash of their contents, exactly as a real Merkle store would, which means sharing arises on its own: two subtrees built from the same children collapse to one node with several parents. Lowering Config.Vocabulary narrows the pool of distinct leaves, so more subtrees coincide and the whole graph collapses to fewer, more heavily shared nodes.

This package is example code. It is here to demonstrate the github.com/danielriddell21/merkelbrot/graph.Source interface and carries no compatibility promise.

Index

• type Config
• type Source
  • func New(cfg Config) *Source
  • func (s *Source) Len() int
  • func (s *Source) Node(id string) (graph.Node[string], bool)
  • func (s *Source) Roots() iter.Seq[string]

Examples

• New

Types

type Config

type Config struct {
	// Seed makes generation reproducible. Default 1.
	Seed uint64
	// Commits is the length of the chain of roots. Default 4.
	Commits int
	// Depth is the number of tree levels beneath each commit. Default 2.
	Depth int
	// Branching is how many children each tree holds. Default 3.
	Branching int
	// Vocabulary is the number of distinct leaves available. Smaller values make
	// more subtrees coincide, collapsing the graph to fewer nodes. Default 12.
	Vocabulary int
}

Config describes the graph to generate. The zero value is usable.

type Source

type Source struct {
	// contains filtered or unexported fields
}

Source is a generated Merkle DAG.

func New

func New(cfg Config) *Source

New generates a graph from the configuration.

Example

ExampleNew generates a graph and reports how much of it is shared, which is what content addressing buys: identical subtrees become one node.

package main

import (
	"fmt"
	"slices"

	"github.com/danielriddell21/merkelbrot/examples/synthetic"
	"github.com/danielriddell21/merkelbrot/graph"
)

func main() {
	src := synthetic.New(synthetic.Config{Seed: 2, Commits: 5, Depth: 2, Branching: 3, Vocabulary: 8})
	g, err := graph.New(src)
	if err != nil {
		panic(err)
	}

	kinds := map[string]int{}
	for _, n := range g.All() {
		kinds[n.Kind]++
	}
	fmt.Println("commits:", kinds["commit"])
	fmt.Println("trees:", kinds["tree"])
	fmt.Println("blobs:", kinds["blob"])
	fmt.Println("shared:", len(slices.Collect(g.Shared())))
	fmt.Println("tree:", g.IsTree())
}

Output:
commits: 5
trees: 13
blobs: 8
shared: 7
tree: false

func (*Source) Len

func (s *Source) Len() int

Len reports how many distinct nodes were generated.

func (*Source) Node

func (s *Source) Node(id string) (graph.Node[string], bool)

Node returns the node with the given ID.

func (*Source) Roots

func (s *Source) Roots() iter.Seq[string]

Roots yields the head of the generated chain.