Artifact [d06ad25663]

Artifact d06ad2566379b49e780821f33e5c2ad17a470b263bf25489bd01e2c6ad4717ba:

• File internal/sync/sparse_walk_tree.go — part of check-in [0de31d6f8e] at 2026-10-22 23:43:27 on branch feat/horizon-cones — feat(sync): withhold out-of-cone nodes of the trees a horizon keeps

  Under either horizon with path members an origin now sends only the sub-manifest nodes on paths into the cone of the trees its horizon keeps (every check-in's at the content depth, K's at the structural one), announces none of the rest and answers no gimme for them; a request without path members still receives every node (draft-fossil-horizon-00 §6.2 at zit 3a2df62515).

  The walk is zit's walkSlots (src/sparse.zig): only slots that may hold an in-cone path are descended, a last slot takes its parent's bound, and a node is walked again only under a wider bound. It runs over the classification's facts, never the store, and the origin's memo keeps it by cone so a later request walks only the roots appended since, falling back to a fresh walk when a root arrives below the ones walked. A clone round sends nodes by the per-check-in tree walk it already uses without a horizon, walking a check-in outside the held set for its nodes alone.

  Each kept node records the lowest root that keeps it, so a cursor is void (§6.2.6) exactly when some node at or below it is kept only by a root above it: stateless, and the same for a fresh classification and the memo, where zit voids every cursor below the store count at the moment its sidecar sees the change.

  The memo returned a cone's earlier classification whenever no fact list grew, keeping that store's names, so an artifact appended or filled without becoming a record read as unnamed; it now carries the current facts. Found by the memo equivalence test, which now covers path cones under both horizons, the slot walk, cursor voiding and a tree form that widens a node's bound. (user: [email protected], size: 3963) [annotate] [blame] [check-ins using] [more...]

package sync

import (
	"fmt"

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

// coneTreeLevel is one node's S cards and the bound its slice lies below,
// empty meaning unbounded.
type coneTreeLevel struct {
	cards []deck.SubmanifestCard
	upper string
}

func (l coneTreeLevel) limit(i int) string {
	if i+1 < len(l.cards) {
		return l.cards[i+1].Name
	}
	return l.upper
}

type coneTreeRange struct {
	name, uuid, limit string
}

// tree descends the cards whose key range may hold a covered path and which
// the parent's tree does not carry over the same range, the §6.2 walk.
// priorFiles are the parent leaf's files when the child split that leaf.
func (w *coneWalk) tree(
	level, prior coneTreeLevel, priorFiles map[deck.FileCard]bool, depth int, out map[int]bool,
) error {
	same := make(map[coneTreeRange]bool, len(prior.cards))
	byName := make(map[string]coneTreeLevel, len(prior.cards))
	for i, card := range prior.cards {
		same[coneTreeRange{card.Name, card.UUID, prior.limit(i)}] = true
		byName[card.Name] = coneTreeLevel{cards: []deck.SubmanifestCard{card}, upper: prior.limit(i)}
	}
	for i, card := range level.cards {
		if err := w.visit(depth); err != nil {
			return err
		}
		limit := level.limit(i)
		if !w.cone.MayCover(card.Name, limit) || same[coneTreeRange{card.Name, card.UUID, limit}] {
			continue
		}
		next := coneTreeLevel{cards: []deck.SubmanifestCard{card}, upper: limit}
		if err := w.node(next, byName[card.Name], priorFiles, depth, out); err != nil {
			return err
		}
	}
	return nil
}

func (w *coneWalk) visit(depth int) error {
	if err := w.ctx.Err(); err != nil {
		return err
	}
	if depth > coneWalkDepth || w.visits >= coneWalkVisits {
		return fmt.Errorf("sparse cone: tree traversal bound exceeded")
	}
	w.visits++
	return nil
}

// node sends one changed in-cone node and descends it. Each level holds the
// single card it stands for; prior is the parent's card of the same name.
func (w *coneWalk) node(
	at, prior coneTreeLevel, priorFiles map[deck.FileCard]bool, depth int, out map[int]bool,
) error {
	card := at.cards[0]
	d, rid, err := w.nodeDeck(card.UUID)
	if err != nil || d == nil {
		return err
	}
	if err := checkNodeRange(d, card.Name, at.upper); err != nil {
		return err
	}
	if w.path[card.UUID] {
		return fmt.Errorf("sparse cone: cyclic sub-manifest %s", card.UUID)
	}
	if !w.atRow(sparseNode) {
		out[rid] = true
	}
	nextFiles := priorFiles
	nextPrior := coneTreeLevel{}
	if len(prior.cards) == 1 {
		if p, _, err := w.nodeDeck(prior.cards[0].UUID); err != nil {
			return err
		} else if p != nil && len(p.F) > 0 {
			nextFiles = fileSet(p.F)
		} else if p != nil {
			nextPrior = coneTreeLevel{cards: p.S, upper: prior.upper}
		}
	}
	if len(d.F) > 0 {
		if w.nodesOnly {
			return nil
		}
		return w.files(d.F, nextFiles, out)
	}
	w.path[card.UUID] = true
	err = w.tree(coneTreeLevel{cards: d.S, upper: at.upper}, nextPrior, nextFiles, depth+1, out)
	delete(w.path, card.UUID)
	return err
}

// nodeDeck is the sub-manifest uuid names when this clone sends it. A node
// the store lacks is left for the recipient to classify from its spine.
func (w *coneWalk) nodeDeck(uuid string) (*deck.Deck, int, error) {
	rid, ok, err := w.servable(uuid)
	if err != nil || !ok {
		return nil, 0, err
	}
	if kind, d := w.classify(rid); kind == sparseNode {
		return d, rid, nil
	}
	return nil, 0, nil
}

func checkNodeRange(d *deck.Deck, name, limit string) error {
	first, last := "", ""
	switch {
	case len(d.F) > 0:
		first, last = d.F[0].Name, d.F[len(d.F)-1].Name
	case len(d.S) > 0:
		first, last = d.S[0].Name, d.S[len(d.S)-1].Name
	}
	if first == "" || first != name || limit != "" && last >= limit {
		return fmt.Errorf("sparse cone: invalid sub-manifest range")
	}
	return nil
}

func fileSet(files []deck.FileCard) map[deck.FileCard]bool {
	set := make(map[deck.FileCard]bool, len(files))
	for _, f := range files {
		set[deck.FileCard{Name: f.Name, UUID: f.UUID}] = true
	}
	return set
}