Artifact [ebef00b549]

Artifact ebef00b5494684c2a6d74880f29d97d16b51bb8046c185fe176dfaa644240031:

• File internal/content/memo_trees_test.go — part of check-in [c50ff7c9e2] at 2026-10-29 14:01:29 on branch main — fix(content): serve a kept tree only where a fresh read would give it

  Review of the tree memo found it could classify differently warm than cold. A kept tree was served whenever the store held its name at its rid, even when the store could no longer expand it (a delta whose source became a phantom or lost its row), where a fresh read skips the tree. Each view now lists, once, the rids its store cannot expand: a recursive walk of the delta table seeded with the phantoms and the delta sources the store holds no row for. Those sources only appear when a row is deleted, which forces a full read, so they are found once per lineage (about 20ms on fossil-scm.org) and the per-view walk costs about 0.3ms. The phantom check folds into it.

  Publish dropped the trees a view read whenever the memo had gone past that view's store, though trees do not depend on the store; they are now kept either way. A view over a store read in full after the memo's is no longer taken for a stale one, so a store whose highest rid was deleted stops being read in full on every view.

  The names bound that replaced the byte cap counted pieces, not names, so one publish could pass it; it now counts the names each piece adds, on the fresh-index path too, and is passed as a parameter so it is tested.

  The tests compare the names a horizon's walk produces, memo against fresh, which classification alone can hide: a tree's lost nodes also stop its files counting as files. They lose trees as phantoms, as deleted nodes, behind phantom and deleted delta sources, and by a shun and rebuild in stock fossil; removing either check fails them. (user: [email protected], size: 8208) [annotate] [blame] [check-ins using] [more...]

package content

import (
	"encoding/binary"
	"fmt"
	"math"
	"math/rand/v2"
	"slices"
	"testing"

	libfossil "github.com/danmestas/go-libfossil/internal/fsltype"
)

func TestTreeIDsRoundTrip(t *testing.T) {
	rng := rand.New(rand.NewPCG(1, 2))
	for _, n := range []int{0, 1, 2, 127, 128, 1000, 5000} {
		set := map[uint32]bool{}
		for len(set) < n {
			set[1+rng.Uint32N(1<<31)] = true
		}
		ids := slices.Sorted(func(yield func(uint32) bool) {
			for id := range set {
				if !yield(id) {
					return
				}
			}
		})
		enc := appendTreeIDs(nil, ids)
		if got := decodeTreeIDs(nil, enc); !slices.Equal(got, ids) {
			t.Fatalf("%d ids: round trip differs", n)
		}
	}
	for _, enc := range [][]byte{
		binary.AppendUvarint(binary.AppendUvarint(nil, math.MaxUint32), 1),
		binary.AppendUvarint(binary.AppendUvarint(nil, 1), math.MaxUint64),
		binary.AppendUvarint(nil, 0),
		{0x80},
	} {
		func() {
			defer func() {
				if recover() == nil {
					t.Errorf("% x decoded", enc)
				}
			}()
			decodeTreeIDs(nil, enc)
		}()
	}
	top := []uint32{1, math.MaxUint32}
	if got := decodeTreeIDs(nil, appendTreeIDs(nil, top)); !slices.Equal(got, top) {
		t.Fatalf("decoded %v, want %v", got, top)
	}
	dense := []uint32{1, 2, 3, 4, 5, 100, 227}
	if enc := appendTreeIDs(nil, dense); len(enc) != len(dense) {
		t.Fatalf("dense ids take %d bytes, want one each", len(enc))
	}
}

// treeIndexFixture is a store's trees as a loader reads them, in the order
// it reads them: full check-ins that drift a few files at a time, a few
// unrelated ones (which a set difference would not shrink), delta
// manifests on those baselines, and sub-manifest trees with their nodes.
func treeIndexFixture(rng *rand.Rand) (names []string, trees []*plainTree) {
	file := func(i int) string { return fmt.Sprintf("%040x", i) }
	current := map[int]bool{}
	for i := 0; i < 300; i++ {
		current[i] = true
	}
	next := 300
	add := func(name string, tr *plainTree) {
		names = append(names, name)
		trees = append(trees, tr)
	}
	for i := 0; i < 120; i++ {
		for j := 0; j < 1+rng.IntN(6); j++ {
			for k := range current {
				delete(current, k)
				break
			}
			current[next] = true
			next++
		}
		files := make([]string, 0, len(current)+1)
		for k := range current {
			files = append(files, file(k))
		}
		if i%37 == 5 {
			files = []string{file(next), file(next + 1)}
			next += 2
		}
		if len(files) > 0 {
			files = append(files, files[0]) // two paths, one blob
		}
		rid := libfossil.FslID(1000 - i)
		add(fmt.Sprintf("c%039d", i), &plainTree{rid: rid, size: int64(10 * i), checkin: true, files: files})
		if i%10 == 3 {
			add(fmt.Sprintf("d%039d", i), &plainTree{rid: rid + 2000, size: 7, checkin: true,
				b: fmt.Sprintf("c%039d", i), files: []string{file(next), file(1)}})
			next++
		}
		if i%25 == 9 {
			node := fmt.Sprintf("n%039d", i)
			add(node, &plainTree{rid: rid + 4000, size: 3, files: []string{file(2), file(next)}})
			add(fmt.Sprintf("t%039d", i), &plainTree{rid: rid + 6000, size: 5, checkin: true,
				s: []string{node, "missing" + node}})
			next++
		}
	}
	add(fmt.Sprintf("e%039d", 0), &plainTree{rid: 9000, size: 11})
	return names, trees
}

// draft-fossil-horizon-00 §6.2: a tree's file set read back from the memo's
// encoding is exactly the set its F cards name, whichever order a walk
// asks for the trees in and however long the chain of set differences
// behind it.
func TestTreeIndexRoundTrip(t *testing.T) {
	rng := rand.New(rand.NewPCG(3, 4))
	names, trees := treeIndexFixture(rng)
	x := newTreeIndex()
	for i, tr := range trees {
		x.add(names[i], tr)
	}
	diffs := 0
	for _, name := range names {
		if p := x.piece(name); p.base != nil {
			diffs++
			if p.depth > treeChain {
				t.Fatalf("%s: chain depth %d past %d", name, p.depth, treeChain)
			}
		}
	}
	if diffs < 50 {
		t.Fatalf("%d of %d trees kept as a set difference", diffs, len(names))
	}
	ascending := slices.Collect(func(yield func(int) bool) {
		for i := range names {
			if !yield(i) {
				return
			}
		}
	})
	descending := slices.Clone(ascending)
	slices.Reverse(descending)
	shuffled := slices.Clone(ascending)
	rng.Shuffle(len(shuffled), func(i, j int) { shuffled[i], shuffled[j] = shuffled[j], shuffled[i] })
	for _, order := range [][]int{ascending, descending, shuffled} {
		var d treeDecoder
		for _, i := range order {
			sameTree(t, x, &d, names[i], trees[i])
		}
	}
	for _, i := range shuffled {
		var d treeDecoder
		sameTree(t, x, &d, names[i], trees[i])
	}
}

// An extended index adds trees without changing what the one it extends
// answers.
func TestTreeIndexExtendLeavesBase(t *testing.T) {
	rng := rand.New(rand.NewPCG(5, 6))
	names, trees := treeIndexFixture(rng)
	half := len(names) / 2
	x := newTreeIndex()
	for i := range names[:half] {
		x.add(names[i], trees[i])
	}
	before := x.bytes
	y := x.clone()
	for i := half; i < len(names); i++ {
		y.add(names[i], trees[i])
	}
	if x.bytes != before || y.bytes <= before {
		t.Fatalf("bytes: base %d (was %d), extension %d", x.bytes, before, y.bytes)
	}
	var d treeDecoder
	for i, name := range names {
		if i >= half {
			if x.piece(name) != nil {
				t.Fatalf("%s: the base index holds a tree added to its extension", name)
			}
		} else {
			sameTree(t, x, &d, name, trees[i])
		}
		sameTree(t, y, &d, name, trees[i])
	}
}

// The memo's trees hold no more names than their bound: a publish that
// would pass it starts again from the view's own pieces, and keeps none
// when even those pass it.
func TestPublishTreesNamesBound(t *testing.T) {
	rng := rand.New(rand.NewPCG(7, 8))
	names, trees := treeIndexFixture(rng)
	pieces := func(lo, hi int) map[string]*plainTree {
		out := map[string]*plainTree{}
		for i := lo; i < hi; i++ {
			out[names[i]] = trees[i]
		}
		return out
	}
	half := len(names) / 2
	count := func(lo, hi int) int {
		x := newTreeIndex()
		x.addPieces(names[lo:hi], pieces(lo, hi), math.MaxInt)
		return len(x.names.names)
	}
	first, whole := count(0, half), count(0, len(names))
	limit := first + (whole-first)/2
	if count(half, len(names)) > limit {
		t.Fatalf("fixture: the second half's names pass the bound %d", limit)
	}
	m := &Memo{}
	m.publishTrees(pieces(0, half), limit)
	if m.trees == nil || m.trees.piece(names[0]) == nil {
		t.Fatal("the first publish, under the bound, was not kept")
	}
	m.publishTrees(pieces(half, len(names)), limit)
	if m.trees == nil || m.trees.piece(names[0]) != nil || m.trees.piece(names[len(names)-1]) == nil {
		t.Fatal("past the bound the trees did not start again from the view's pieces")
	}
	if n := len(m.trees.names.names); n > limit {
		t.Fatalf("%d names past the bound %d", n, limit)
	}
	var d treeDecoder
	for i := half; i < len(names); i++ {
		sameTree(t, m.trees, &d, names[i], trees[i])
	}
	m.publishTrees(pieces(0, len(names)), 10)
	if m.trees != nil {
		t.Fatalf("a view whose own pieces pass the bound left %d names", len(m.trees.names.names))
	}
}

func sameTree(t *testing.T, x *treeIndex, d *treeDecoder, name string, want *plainTree) {
	t.Helper()
	p := x.piece(name)
	if p == nil {
		t.Fatalf("%s: not indexed", name)
	}
	if p.rid != want.rid || p.size != want.size || x.names.name(p.b) != want.b {
		t.Fatalf("%s: rid %d size %d b %q, want %d %d %q", name, p.rid, p.size, x.names.name(p.b),
			want.rid, want.size, want.b)
	}
	s := make([]string, len(p.s))
	for i, id := range p.s {
		s[i] = x.names.name(id)
	}
	if !slices.Equal(s, want.s) {
		t.Fatalf("%s: S %v, want %v", name, s, want.s)
	}
	var got []string
	for _, id := range d.files(p) {
		got = append(got, x.names.name(id))
	}
	slices.Sort(got)
	files := slices.Compact(slices.Sorted(slices.Values(want.files)))
	if !slices.Equal(got, files) {
		t.Fatalf("%s: %d files decoded, want %d", name, len(got), len(files))
	}
}

// BenchmarkTreeIndexClone clones an index the size of fossil-scm.org's
// whole tree history, as a publish does.
func BenchmarkTreeIndexClone(b *testing.B) {
	x := newTreeIndex()
	for i := 0; i < 45000; i++ {
		x.intern(fmt.Sprintf("%040x", i))
	}
	for i := 0; i < 21000; i++ {
		x.add(fmt.Sprintf("m%039x", i), &plainTree{rid: libfossil.FslID(i + 1), checkin: true,
			files: []string{fmt.Sprintf("%040x", i), fmt.Sprintf("%040x", i+1)}})
	}
	b.ResetTimer()
	for b.Loop() {
		_ = x.clone()
	}
}