Artifact [185457b1ec]

Artifact 185457b1ec967fe47a081d6f5b3e0284f4d892e57ca2a6a3fa16cb85f2e724d2:

• File internal/content/memo_test.go — part of check-in [13f8021952] at 2026-10-23 02:24:20 on branch feat/horizon-cones — perf(content): keep the trees a horizon's walk reads in the memo

  draft-fossil-horizon-00 §6.2 asks an origin to read each structural artifact's references once per store and classify every cone over that graph. The memo did so for kinds and P, B, S and A cards, but the F cards of a horizon's trees were walked from the store by the first classification of each horizon, so a second horizon under another C or rule re-read every tree it shared with the first.

  The memo now keeps, per store lineage, each manifest, baseline and node a walk read: its own F-card targets and its B and S references, so a delta manifest shares its baseline's entry. A view stages what it reads and the memo takes it on Publish, so a request that rolls back leaves nothing; a kept piece serves a view only when its rid is held at that view's prefix, and its size is charged as a read would charge it, so budgets fail where a fresh walk fails. Names are interned and the cache is capped at 64MiB with LRU eviction: fossil-scm's history names about 21M F entries, over 300MiB uncapped.

  On a copy of a 21k-check-in fossil repository, horizon B (2000 check-ins back) classified after horizon A (1000 back) took 2.5-3.0s and now 1.6s, reading 995 trees instead of 1995; A is unchanged at about 1.3-1.6s. (user: [email protected], size: 8686) [annotate] [blame] [check-ins using] [more...]

package content_test

import (
	"context"
	"fmt"
	"maps"
	"path/filepath"
	"slices"
	"testing"
	"time"

	"github.com/danmestas/go-libfossil/internal/cone"
	"github.com/danmestas/go-libfossil/internal/content"
	libfossil "github.com/danmestas/go-libfossil/internal/fsltype"
	"github.com/danmestas/go-libfossil/internal/manifest"
	"github.com/danmestas/go-libfossil/internal/repo"
	"github.com/danmestas/go-libfossil/simio"
)

// memoRepo is a store that grows by check-ins written in order, one file
// changing per check-in, in one of the manifest forms hzMode names.
type memoRepo struct {
	t    *testing.T
	r    *repo.Repo
	mode hzMode
	when time.Time
	tips []libfossil.FslID
	n    int
}

func newMemoRepo(t *testing.T, mode hzMode) *memoRepo {
	t.Helper()
	r, err := repo.Create(filepath.Join(t.TempDir(), "memo.fossil"), "u", simio.CryptoRand{}, "")
	if err != nil {
		t.Fatal(err)
	}
	t.Cleanup(func() { r.Close() })
	if mode == hzTree {
		for k, v := range map[string]string{
			manifest.SettingEnableSubmanifests: "on", manifest.SettingSubmanifestK: "1",
		} {
			if err := r.SetConfig(k, v); err != nil {
				t.Fatal(err)
			}
		}
	}
	return &memoRepo{t: t, r: r, mode: mode, when: time.Date(2026, 10, 1, 0, 0, 0, 0, time.UTC)}
}

// commit checks in on parent (0 for a root) a tree of a fixed file set,
// one of whose files changes.
func (m *memoRepo) commit(parent libfossil.FslID) libfossil.FslID {
	m.t.Helper()
	m.n++
	m.when = m.when.Add(time.Hour)
	files := []manifest.File{
		{Name: "lib/x.c", Content: []byte("x\n")}, {Name: "lib/y.c", Content: []byte("y\n")},
		{Name: "src/a.c", Content: []byte("a\n")}, {Name: "src/b.c", Content: []byte("b\n")},
	}
	files[m.n%len(files)].Content = []byte(fmt.Sprintf("v%d\n", m.n))
	rid, _, err := manifest.Checkin(m.r, manifest.CheckinOpts{
		Files: files, Comment: fmt.Sprintf("c%d", m.n), User: "u", Parent: parent, Time: m.when,
		Delta: m.mode == hzDelta && parent != 0,
	})
	if err != nil {
		m.t.Fatal(err)
	}
	m.tips = append(m.tips, rid)
	return rid
}

func (m *memoRepo) uuid(rid libfossil.FslID) string {
	m.t.Helper()
	var uuid string
	if err := m.r.DB().QueryRow("SELECT uuid FROM blob WHERE rid=?", rid).Scan(&uuid); err != nil {
		m.t.Fatal(err)
	}
	return uuid
}

// memoCones are the cones the tests classify: a path cone, and C's
// horizons under both rules and both depths, with and without paths.
func (m *memoRepo) memoCones(c libfossil.FslID) []*cone.Cone {
	m.t.Helper()
	paths, err := cone.New([]string{"src"}, nil)
	if err != nil {
		m.t.Fatal(err)
	}
	out := []*cone.Cone{paths}
	for _, rule := range []cone.HorizonRule{cone.RuleDescendants, cone.RuleLeaves} {
		for _, depth := range []cone.HorizonDepth{cone.DepthContent, cone.DepthStructural} {
			h, err := cone.NewHorizon(m.uuid(c), rule, depth)
			if err != nil {
				m.t.Fatal(err)
			}
			for _, include := range [][]string{nil, {"src"}} {
				hc, err := cone.NewWithHorizon(include, nil, h)
				if err != nil {
					m.t.Fatal(err)
				}
				out = append(out, hc)
			}
		}
	}
	return out
}

// sameClassification fails unless the view classifies c as a fresh read
// of the store does: every artifact's Outside, Required and below answer,
// and the held set and reach of its horizon.
func sameClassification(t *testing.T, r *repo.Repo, v *content.MemoView, c *cone.Cone) {
	t.Helper()
	ctx := context.Background()
	q := r.DB()
	fresh, err := content.LoadConeReferences(ctx, q, c)
	if err != nil {
		t.Fatal(err)
	}
	memo, err := v.References(ctx, c)
	if err != nil {
		t.Fatal(err)
	}
	var freshBelow, memoBelow func(libfossil.FslID) bool
	if _, ok := c.Horizon(); ok {
		if freshBelow, err = fresh.HorizonBelow(ctx, q, c); err != nil {
			t.Fatal(err)
		}
		if memoBelow, err = v.HorizonBelow(ctx, q, memo, c); err != nil {
			t.Fatal(err)
		}
		if (freshBelow == nil) != (memoBelow == nil) {
			t.Fatalf("%s: placed fresh=%v memo=%v", c, freshBelow != nil, memoBelow != nil)
		}
		h, _ := c.Horizon()
		fk, freach, fplaced, err := content.HorizonReach(ctx, q, h)
		if err != nil {
			t.Fatal(err)
		}
		mk, mreach, mplaced, err := v.HorizonReach(ctx, q, h)
		if err != nil {
			t.Fatal(err)
		}
		if fplaced != mplaced || !slices.Equal(fk, mk) || !maps.Equal(freach, mreach) {
			t.Fatalf("%s: reach fresh K=%v placed=%v, memo K=%v placed=%v", c, fk, fplaced, mk, mplaced)
		}
	}
	rows, err := q.Query("SELECT rid FROM blob ORDER BY rid")
	if err != nil {
		t.Fatal(err)
	}
	defer rows.Close()
	for rows.Next() {
		var rid libfossil.FslID
		if err := rows.Scan(&rid); err != nil {
			t.Fatal(err)
		}
		if fresh.Outside(rid) != memo.Outside(rid) || fresh.Required(rid) != memo.Required(rid) {
			t.Fatalf("%s rid=%d: outside %v/%v required %v/%v (fresh/memo)", c, rid,
				fresh.Outside(rid), memo.Outside(rid), fresh.Required(rid), memo.Required(rid))
		}
		if freshBelow != nil && freshBelow(rid) != memoBelow(rid) {
			t.Fatalf("%s rid=%d: below fresh=%v memo=%v", c, rid, freshBelow(rid), memoBelow(rid))
		}
	}
	if err := rows.Err(); err != nil {
		t.Fatal(err)
	}
}

// draft-fossil-horizon-00 §6.2: a memo extended by each appended check-in
// classifies every cone as a fresh read of the store does, in every manifest
// form, and reads only what was appended.
func TestMemoExtendsExactly(t *testing.T) {
	for _, mode := range []hzMode{hzFull, hzDelta, hzTree} {
		t.Run(string(mode), func(t *testing.T) {
			ctx := context.Background()
			m := newMemoRepo(t, mode)
			root := m.commit(0)
			c := m.commit(root)
			memo := content.NewMemo()
			v, err := memo.View(ctx, m.r.DB())
			if err != nil {
				t.Fatal(err)
			}
			if v.Read() == 0 {
				t.Fatal("the first view read nothing")
			}
			for _, sc := range m.memoCones(c) {
				sameClassification(t, m.r, v, sc)
			}
			v.Publish()
			fork := root
			for i := 0; i < 4; i++ {
				before := maxRID(t, m.r)
				tip := m.commit(m.tips[len(m.tips)-1])
				if i == 2 {
					fork = m.commit(fork) // a branch from below C
				}
				v, err := memo.View(ctx, m.r.DB())
				if err != nil {
					t.Fatal(err)
				}
				if appended := int(maxRID(t, m.r) - before); v.Read() != appended {
					t.Fatalf("after check-in %d the view read %d artifacts, want the %d appended", tip, v.Read(), appended)
				}
				for _, sc := range m.memoCones(c) {
					sameClassification(t, m.r, v, sc)
				}
				v.Publish()
			}
			again, err := memo.View(ctx, m.r.DB())
			if err != nil {
				t.Fatal(err)
			}
			if again.Read() != 0 {
				t.Fatalf("an unchanged store read %d artifacts", again.Read())
			}
		})
	}
}

// A view that is not published leaves the memo as it was: what an origin
// classified inside a request that rolls back is never reused.
func TestMemoUnpublishedViewDiscarded(t *testing.T) {
	ctx := context.Background()
	m := newMemoRepo(t, hzFull)
	c := m.commit(0)
	memo := content.NewMemo()
	v, err := memo.View(ctx, m.r.DB())
	if err != nil {
		t.Fatal(err)
	}
	v.Publish()
	before := maxRID(t, m.r)
	m.commit(c)
	if _, err := memo.View(ctx, m.r.DB()); err != nil {
		t.Fatal(err)
	}
	v, err = memo.View(ctx, m.r.DB())
	if err != nil {
		t.Fatal(err)
	}
	if appended := int(maxRID(t, m.r) - before); v.Read() != appended {
		t.Fatalf("view after an unpublished one read %d, want %d", v.Read(), appended)
	}
}

// draft-fossil-horizon-00 §6.2: the memo keeps the trees its horizons'
// walks read, so a second horizon over the same store, under another C or
// rule, reads from the store only the trees the first did not, and
// classifies as a fresh read does.
func TestMemoTreesReadOnce(t *testing.T) {
	for _, mode := range []hzMode{hzFull, hzDelta, hzTree} {
		t.Run(string(mode), func(t *testing.T) {
			ctx := context.Background()
			m := newMemoRepo(t, mode)
			tip := m.commit(0)
			for i := 0; i < 5; i++ {
				tip = m.commit(tip)
			}
			memo := content.NewMemo()
			seen := map[string]bool{}
			for _, c := range []libfossil.FslID{m.tips[3], m.tips[1], m.tips[0]} {
				v, err := memo.View(ctx, m.r.DB())
				if err != nil {
					t.Fatal(err)
				}
				for _, sc := range m.memoCones(c) {
					sameClassification(t, m.r, v, sc)
				}
				names, reads := v.TreesRead()
				if reads != len(names) {
					t.Fatalf("horizon at %d: %d tree reads of %d trees", c, reads, len(names))
				}
				if len(seen) == 0 && len(names) == 0 {
					t.Fatalf("the first horizon, at %d, read no tree", c)
				}
				for _, name := range names {
					if seen[name] {
						t.Fatalf("horizon at %d read %.10s again", c, name)
					}
					seen[name] = true
				}
				v.Publish()
			}
		})
	}
}

func maxRID(t *testing.T, r *repo.Repo) libfossil.FslID {
	t.Helper()
	var n libfossil.FslID
	if err := r.DB().QueryRow("SELECT max(rid) FROM blob").Scan(&n); err != nil {
		t.Fatal(err)
	}
	return n
}