Artifact [558f90e348]

Artifact 558f90e3486abfc7396d8d050ee7699248c91a08f6916be6c32131aeb7742a01:

• File internal/manifest/tree.go — part of check-in [94f61db228] at 2026-10-26 00:02:06 on branch main — perf(manifest): memoize parsed sub-manifests by hash

  draft-fossil-submanifests-00 §7.4: enumeration results SHOULD be cached keyed by artifact name, so a rebuild parses each distinct sub-manifest once. The tree walk's loader now serves a resolved node from, and keeps it in, a new byte-bounded LRU memo on content.Cache (DerivedSized), keyed by the node's hash and charged its bytes, within a quarter of the cache's budget. The existing 32-entry Derived FIFO is sized for a few parsed check-ins; a tree's working set is every distinct node, which would thrash it and evict those check-ins.

  Only a node that resolved is kept, so a phantom is looked up afresh and fails the walk as before. Depth, cycle and node-count bounds stay per walk. The memo is dropped with Derived on Invalidate and Clear, and the Repo's cache is replaced at every write.

  Listing a tree that differs from one already read in one leaf now parses its manifest and that leaf; listing every check-in of zit's recorded tree history parses 48 sub-manifests instead of 109. SM-7.4-1 is covered.

  Tracked in #493. (user: [email protected], size: 10383) [annotate] [blame] [check-ins using] [more...]

package manifest

// Reading tree manifests, draft-fossil-submanifests-00 §5: the full file-set
// walk (§5.1), sub-manifest resolution (§5.2) and single-name lookup (§5.3).
// Nothing outside this file and files.go knows a check-in can be a tree; every
// file-set consumer asks the enumeration seam in files.go (§9.3), which calls
// in here for a manifest that carries S cards.

import (
	"errors"
	"fmt"

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

// maxTreeDepth is §5.1 step 3's bound: the sub-manifest artifacts on one
// reference path, counting the leaf. A walk holds at most maxTreeDepth+1
// frames, the manifest's included.
const maxTreeDepth = 16

// maxTreeNodes bounds the sub-manifests one enumeration or one lookup
// resolves (§10). Sub-manifests are shared by hash, so a legitimate tree of
// this many nodes already describes millions of files; past it the walk is
// treated as hostile rather than slow.
const maxTreeNodes = 1 << 20

// SubmanifestError reports that a tree cannot be enumerated because of the
// sub-manifest reference UUID: either that artifact is not available locally
// (Missing), the one fault a caller may defer on under §5.2's soft
// discipline, or the reference breaks a rule of §5.1, which is permanent for
// the bytes involved.
type SubmanifestError struct {
	UUID    string
	Missing bool
	Reason  string
}

func (e *SubmanifestError) Error() string {
	if e.Missing {
		return fmt.Sprintf("sub-manifest %s is not available", e.UUID)
	}
	return fmt.Sprintf("sub-manifest %s: %s", e.UUID, e.Reason)
}

// MissingSubmanifest reports the hash of the absent sub-manifest err names,
// if err is or wraps a SubmanifestError for an unavailable artifact.
func MissingSubmanifest(err error) (string, bool) {
	var e *SubmanifestError
	if errors.As(err, &e) && e.Missing {
		return e.UUID, true
	}
	return "", false
}

// treeFault builds the SubmanifestError for a rule the reference uuid breaks.
func treeFault(uuid, format string, args ...any) error {
	return &SubmanifestError{UUID: uuid, Reason: fmt.Sprintf(format, args...)}
}

// isTree reports whether d is a tree manifest: a manifest whose file set is
// conveyed by S cards (§5). A sub-manifest is not one.
func isTree(d *deck.Deck) bool {
	return d.Type == deck.Checkin && len(d.S) > 0
}

// subtreeLoader resolves S references to parsed sub-manifests, counting each
// resolution against maxTreeNodes.
type subtreeLoader struct {
	q        db.Querier
	cache    *content.Cache
	resolved int
}

// nodeKey is the memo key of a parsed sub-manifest: its artifact name, which
// §7.4 says enumeration results SHOULD be cached under ("keyed by artifact
// name: unchanged subtrees are shared by hash across check-ins, so a
// memoizing rebuild parses each distinct sub-manifest once").
type nodeKey string

// parsedNode is a resolved sub-manifest as the memo keeps it.
type parsedNode struct {
	d   *deck.Deck
	rid libfossil.FslID
}

// load resolves uuid to an available artifact of type SUBMANIFEST (§5.2):
// absent is a Missing SubmanifestError, anything else that is not a
// sub-manifest is a fault of the referencing tree. A resolved node is served
// from, and kept in, the cache's sized memo, charged its bytes. Only a node
// that resolved is kept, so an absent one is looked up afresh each time; and
// content is only ever added while a cache lives (the Repo's is replaced at
// every write), so a node available once stays available.
func (l *subtreeLoader) load(uuid string) (*deck.Deck, libfossil.FslID, error) {
	if uuid == "" {
		panic("manifest.subtreeLoader.load: uuid must not be empty")
	}
	if l.resolved >= maxTreeNodes {
		return nil, 0, treeFault(uuid, "the tree resolves more than %d sub-manifests", maxTreeNodes)
	}
	l.resolved++
	if v, ok := l.cache.DerivedSized(nodeKey(uuid)); ok {
		n := v.(parsedNode)
		return n.d, n.rid, nil
	}
	rid, ok := content.AvailableByUUID(l.q, uuid)
	if !ok {
		return nil, 0, &SubmanifestError{UUID: uuid, Missing: true}
	}
	data, err := expandManifestBytes(l.q, l.cache, rid)
	if err != nil {
		return nil, 0, treeFault(uuid, "%v", err)
	}
	d, err := deck.Parse(data)
	if err != nil {
		return nil, 0, treeFault(uuid, "%v", err)
	}
	if d.Type != deck.Submanifest {
		return nil, 0, treeFault(uuid, "not a sub-manifest")
	}
	l.cache.SetDerivedSized(nodeKey(uuid), parsedNode{d: d, rid: rid}, int64(len(data)))
	return d, rid, nil
}

// treeFrame is one artifact on the walk's stack and its cursor over its S run.
type treeFrame struct {
	rid    libfossil.FslID // 0 for the manifest itself
	cards  []deck.SubmanifestCard
	cursor int
	limit  string // the exclusive upper bound of the frame's keys; "" for none
}

// treeWalk is the state of one §5.1 enumeration.
type treeWalk struct {
	loader  *subtreeLoader
	filter  FileFilter // nil for the full enumeration
	stack   []treeFrame
	last    string
	hasLast bool
	files   []deck.FileCard
	// Only readiness inspection may skip proven outside gaps; enumeration never does.
	skipMissing func(string) bool
}

// walkTree enumerates tree manifest d as §5.1 specifies: depth first, in
// order, with an explicit stack rather than recursion. It returns the F cards
// of the leaves in enumeration order, or an error -- never a partial set
// (§5.2). Every tree fault is a SubmanifestError.
func walkTree(q db.Querier, cache *content.Cache, d *deck.Deck) ([]deck.FileCard, error) {
	return walkTreeFiltered(q, cache, d, nil)
}

// walkTreeFiltered is walkTree narrowed by filter, when it is not nil: it
// emits only the files filter covers and never resolves a sub-manifest whose
// key range filter cannot cover (draft-fossil-sparse-cone-00 §1.3, §4.1).
// Every node is a contiguous range of the sorted file list, from its S card's
// name up to the next sibling's (or its parent's bound), so a skipped node
// holds nothing the filter covers.
func walkTreeFiltered(q db.Querier, cache *content.Cache, d *deck.Deck, filter FileFilter) ([]deck.FileCard, error) {
	if !isTree(d) {
		panic("manifest.walkTree: d must be a tree manifest")
	}
	w := &treeWalk{
		loader: &subtreeLoader{q: q, cache: cache},
		filter: filter,
		stack:  []treeFrame{{cards: d.S}},
	}
	// Each step either advances a cursor or pops a frame, and every pushed
	// frame costs a resolution, so the loop is bounded by the S cards the
	// resolved artifacts carry; maxTreeNodes bounds those.
	for len(w.stack) > 0 {
		if err := w.step(); err != nil {
			return nil, err
		}
	}
	if len(w.files) == 0 && filter == nil {
		panic("manifest.walkTree: a tree enumerated no files")
	}
	return w.files, nil
}

// step performs §5.1 steps 2 to 5 once.
func (w *treeWalk) step() error {
	top := &w.stack[len(w.stack)-1]
	if top.cursor == len(top.cards) {
		w.stack = w.stack[:len(w.stack)-1] // step 2
		return nil
	}
	card := top.cards[top.cursor]
	top.cursor++
	if w.hasLast && deck.Compare(card.Name, w.last) <= 0 {
		return treeFault(card.UUID, "S-card %q does not follow %q", card.Name, w.last)
	}
	limit := top.limit
	if top.cursor < len(top.cards) {
		limit = top.cards[top.cursor].Name
	}
	if w.filter != nil && !w.filter.MayCover(card.Name, limit) {
		return nil
	}
	// The resolved artifact's depth is the sub-manifests on its path,
	// itself included: one per frame above the manifest's, plus one.
	if len(w.stack) > maxTreeDepth {
		return treeFault(card.UUID, "deeper than %d sub-manifests", maxTreeDepth)
	}
	sub, rid, err := w.loader.load(card.UUID)
	if err != nil {
		if uuid, missing := MissingSubmanifest(err); missing && w.skipMissing != nil && w.skipMissing(uuid) {
			return nil
		}
		return err
	}
	for _, frame := range w.stack {
		if frame.rid == rid {
			return treeFault(card.UUID, "the reference closes a cycle")
		}
	}
	if len(sub.F) > 0 {
		return w.emitLeaf(card, sub)
	}
	if sub.S[0].Name != card.Name { // step 5
		return treeFault(card.UUID, "S-card %q names a subtree starting at %q", card.Name, sub.S[0].Name)
	}
	w.stack = append(w.stack, treeFrame{rid: rid, cards: sub.S, limit: limit})
	return nil
}

// emitLeaf is §5.1 step 4: a leaf's F cards, the first of them named exactly
// as the S card that reached it, every one strictly after the last emitted.
func (w *treeWalk) emitLeaf(card deck.SubmanifestCard, leaf *deck.Deck) error {
	if leaf.F[0].Name != card.Name {
		return treeFault(card.UUID, "S-card %q names a leaf starting at %q", card.Name, leaf.F[0].Name)
	}
	for _, f := range leaf.F {
		if w.hasLast && deck.Compare(f.Name, w.last) <= 0 {
			return treeFault(card.UUID, "file %q does not follow %q", f.Name, w.last)
		}
		if w.filter == nil || w.filter.Covers(f.Name) {
			w.files = append(w.files, f)
		}
		w.last, w.hasLast = f.Name, true
	}
	return nil
}

// lookupTree resolves one name in tree manifest d as §5.3 specifies: the last
// S card at or before the name, one sub-manifest per level, at most
// maxTreeDepth of them. A sub-manifest on the path that cannot be resolved is
// a SubmanifestError; a name the search proves absent is (_, false, nil).
func lookupTree(q db.Querier, cache *content.Cache, d *deck.Deck, name string) (deck.FileCard, bool, error) {
	if !isTree(d) {
		panic("manifest.lookupTree: d must be a tree manifest")
	}
	loader := &subtreeLoader{q: q, cache: cache}
	cards := d.S
	for depth := 1; depth <= maxTreeDepth; depth++ {
		card, ok := lastSCardAtOrBefore(cards, name)
		if !ok {
			return deck.FileCard{}, false, nil
		}
		sub, _, err := loader.load(card.UUID)
		if err != nil {
			return deck.FileCard{}, false, err
		}
		if len(sub.F) > 0 {
			f, found := findFileCard(sub.F, name)
			return f, found, nil
		}
		cards = sub.S
	}
	return deck.FileCard{}, false, treeFault(cards[0].UUID, "lookup of %q descends deeper than %d", name, maxTreeDepth)
}

// lastSCardAtOrBefore binary-searches an S run, which the parser keeps in
// comparator order, for the last card whose filename is at or before name.
func lastSCardAtOrBefore(cards []deck.SubmanifestCard, name string) (deck.SubmanifestCard, bool) {
	lo, hi := 0, len(cards)
	for lo < hi {
		mid := lo + (hi-lo)/2
		if deck.Compare(cards[mid].Name, name) <= 0 {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	if lo == 0 {
		return deck.SubmanifestCard{}, false
	}
	return cards[lo-1], true
}