Artifact [f063154d88]

Artifact f063154d88963b6386927d13b587facdec337a82dccfc42ce3d88e3beb016887:

• File internal/sync/sparse_walk.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: 10252) [annotate] [blame] [check-ins using] [more...]

package sync

import (
	"context"
	"database/sql"
	"errors"
	"fmt"
	"sort"

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

// The §8 bounds of single-name lookup, charged across one request.
const (
	coneWalkDepth  = 16
	coneWalkVisits = 1 << 20
)

type sparseKind uint8

const (
	sparseContent    sparseKind = iota // bytes no artifact parses from
	sparseNode                         // sub-manifest node: sent by a walk, or at its row under a horizon alone
	sparseStructural                   // held densely (§5.1)
	sparseCheckin
	sparseCluster // held densely, but never sent under a horizon (horizon §4.5)
)

// coneWalk is §6.2 keep-set discovery for one clone round. A row is read
// only when the round reaches it, and a check-in's tree is walked only when
// the round emits that check-in, so the work tracks the round's batch. Each
// check-in sends what its primary parent's tree does not already hold; the
// parent is a row of the same clone, so by induction every in-cone node and
// blob of every check-in is sent once its own check-in is.
//
// Under a content horizon (draft-fossil-horizon-00 §6.2) only a check-in in
// the held set walks its tree for blobs, and its parent counts as sent only
// when it is in the held set too: the blobs sent are those above the
// horizon. Every structural artifact but a cluster goes out at its row, as
// §4.1 holds them at every age, and so does every node of a horizon alone.
// With path members too, a node goes out only by a walk, as without a
// horizon: every other check-in the request keeps walks its tree for its
// nodes alone, so the nodes sent are those on paths into the cone of every
// tree the horizon keeps, and the rest are withheld.
type coneWalk struct {
	ctx        context.Context
	h          *handler
	cone       *cone.Cone
	horizon    bool
	paths      bool            // the request carries path members
	nodesOnly  bool            // the tree being walked sends its nodes and no blob
	held       map[int]bool    // the held set; nil when there is no horizon or the store cannot place C
	reach      map[string]bool // a structural request's kept manifests and nodes (§5.1); nil otherwise
	kinds      map[int]sparseKind
	decks      map[int]*deck.Deck
	reached    map[int]bool
	path       map[string]bool
	visits     int
	classified int
}

func newConeWalk(ctx context.Context, h *handler) *coneWalk {
	if ctx == nil || h == nil || h.cone == nil {
		panic("sync.newConeWalk: nil context, handler or cone")
	}
	_, horizon := h.cone.Horizon()
	w := &coneWalk{ctx: ctx, h: h, cone: h.cone, horizon: horizon, paths: len(h.cone.Include()) > 0,
		kinds: map[int]sparseKind{},
		decks: map[int]*deck.Deck{}, reached: map[int]bool{}, path: map[string]bool{}}
	if h.structural != nil {
		w.reach = h.structural.reach
	}
	return w
}

// placeHorizon computes the held set over the store, bounded as every
// server-side graph walk is (§8). A C the store cannot place proves no blob
// below the horizon, so every check-in then walks its tree, as a request
// without one would.
func (w *coneWalk) placeHorizon() error {
	h, ok := w.cone.Horizon()
	if !ok {
		return nil
	}
	k, placed, err := horizon.Place(w.ctx, w.h.repo.DB(), h)
	if err != nil || !placed {
		return err
	}
	w.held = make(map[int]bool, len(k))
	for _, rid := range k {
		w.held[int(rid)] = true
	}
	return nil
}

// inHeld reports a check-in whose tree the request keeps.
func (w *coneWalk) inHeld(rid int) bool {
	return w.held == nil || w.held[rid]
}

// atRow reports a kind sent at its own row rather than by a walk.
func (w *coneWalk) atRow(kind sparseKind) bool {
	switch kind {
	case sparseStructural, sparseCheckin:
		return true
	case sparseNode:
		return w.horizon && !w.paths
	case sparseCluster:
		return !w.horizon
	}
	return false
}

// classify parses rid once per request. Unreadable bytes stay structural:
// they go out at their row and fail there exactly as a dense clone would.
func (w *coneWalk) classify(rid int) (sparseKind, *deck.Deck) {
	if kind, ok := w.kinds[rid]; ok {
		return kind, w.decks[rid]
	}
	w.classified++
	kind, d := sparseStructural, (*deck.Deck)(nil)
	data, err := w.h.cache.Expand(w.h.repo.DB(), libfossil.FslID(rid))
	if err == nil {
		kind = sparseContent
		if deck.HasValidZ(data) {
			if parsed, perr := deck.Parse(data); perr == nil {
				kind, d = deckKind(parsed), parsed
			}
		}
	}
	w.kinds[rid], w.decks[rid] = kind, d
	return kind, d
}

func deckKind(d *deck.Deck) sparseKind {
	switch d.Type {
	case deck.Submanifest:
		return sparseNode
	case deck.Checkin:
		return sparseCheckin
	case deck.Cluster:
		return sparseCluster
	}
	return sparseStructural
}

// unreached reports a manifest or node a structural request does not keep:
// one no tree of the held set reaches (horizon §5.1).
func (w *coneWalk) unreached(kind sparseKind, uuid string) bool {
	return w.reach != nil && (kind == sparseCheckin || kind == sparseNode) && !w.reach[uuid]
}

// sourceKept is the §6.2 keep-set test for a served delta's base.
func (w *coneWalk) sourceKept(rid int) bool {
	if w.reached[rid] {
		return true
	}
	kind, _ := w.classify(rid)
	if !w.atRow(kind) {
		return false
	}
	if w.reach == nil || kind != sparseCheckin && kind != sparseNode {
		return true
	}
	info, ok, err := w.h.loadCloneBlob(rid)
	return err == nil && ok && !w.unreached(kind, info.uuid)
}

// servable resolves uuid to a row this clone session sends: held, inside
// the snapshot bound, not shunned, and public unless the clone is private.
func (w *coneWalk) servable(uuid string) (int, bool, error) {
	var rid int
	err := w.h.repo.DB().QueryRow("SELECT rid FROM blob WHERE uuid=? AND size>=0", uuid).Scan(&rid)
	if errors.Is(err, sql.ErrNoRows) {
		return 0, false, nil
	}
	if err != nil {
		return 0, false, fmt.Errorf("sparse walk: resolve %s: %w", uuid, err)
	}
	if rid > w.h.cloneSnapMax {
		return 0, false, nil
	}
	info, ok, err := w.h.loadCloneBlob(rid)
	if err != nil || !ok {
		return 0, false, err
	}
	return rid, !info.priv || w.h.syncPrivate, nil
}

// items returns, ascending, the rows the artifact d at structural row rid
// brings with it: an attachment's source, or a check-in's new in-cone tree.
func (w *coneWalk) items(rid int, d *deck.Deck) ([]int, error) {
	out := map[int]bool{}
	var err error
	switch {
	case d.A != nil && d.A.Source != "":
		err = w.add(d.A.Source, out)
	case d.Type == deck.Checkin && !w.inHeld(rid) && len(d.S) > 0 && !w.atRow(sparseNode):
		err = w.nodes(d, out)
	case d.Type == deck.Checkin && !w.inHeld(rid):
	case d.Type == deck.Checkin && len(d.S) > 0:
		prior := coneTreeLevel{}
		if parent, perr := w.parent(d); perr != nil {
			return nil, perr
		} else if parent != nil {
			prior.cards = parent.S
		}
		err = w.tree(coneTreeLevel{cards: d.S}, prior, nil, 1, out)
	case d.Type == deck.Checkin:
		err = w.flat(d, out)
	}
	if err != nil {
		return nil, err
	}
	rids := make([]int, 0, len(out))
	for item := range out {
		w.reached[item] = true
		rids = append(rids, item)
	}
	sort.Ints(rids)
	return rids, nil
}

// nodes sends the in-cone nodes of the tree of d, a check-in whose blobs
// the request does not keep, that its primary parent's tree does not
// already carry over the same range. A parent's nodes went out when it did:
// every check-in's under a content horizon, a reached one's under a
// structural horizon.
func (w *coneWalk) nodes(d *deck.Deck, out map[int]bool) error {
	prior := coneTreeLevel{}
	if len(d.P) > 0 {
		p, _, err := w.checkin(d.P[0])
		if err != nil {
			return err
		}
		if p != nil && (w.reach == nil || w.reach[d.P[0]]) {
			prior.cards = p.S
		}
	}
	w.nodesOnly = true
	err := w.tree(coneTreeLevel{cards: d.S}, prior, nil, 1, out)
	w.nodesOnly = false
	return err
}

func (w *coneWalk) add(uuid string, out map[int]bool) error {
	rid, ok, err := w.servable(uuid)
	if ok {
		out[rid] = true
	}
	return err
}

// parent is the primary parent check-in when this clone sends its tree,
// else nil: then nothing is known to be sent already and the whole cone
// goes out.
func (w *coneWalk) parent(d *deck.Deck) (*deck.Deck, error) {
	if len(d.P) == 0 {
		return nil, nil
	}
	p, rid, err := w.checkin(d.P[0])
	if err != nil || p == nil || !w.inHeld(rid) {
		return nil, err
	}
	return p, nil
}

func (w *coneWalk) checkin(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 == sparseCheckin {
		return d, rid, nil
	}
	return nil, 0, nil
}

// flat sends the in-cone files of d's full file list that its parent's full
// list does not name identically.
func (w *coneWalk) flat(d *deck.Deck, out map[int]bool) error {
	files, err := w.fileList(d)
	if err != nil {
		return err
	}
	parent, err := w.parent(d)
	if err != nil {
		return err
	}
	prior := map[deck.FileCard]bool{}
	if parent != nil {
		pf, err := w.fileList(parent)
		if err != nil {
			return err
		}
		for _, f := range pf {
			prior[deck.FileCard{Name: f.Name, UUID: f.UUID}] = true
		}
	}
	return w.files(files, prior, out)
}

// fileList applies a delta manifest's F cards to its baseline's. An unheld
// baseline leaves the delta's own cards, the most this store can prove.
func (w *coneWalk) fileList(d *deck.Deck) ([]deck.FileCard, error) {
	if d.B == "" {
		return d.F, nil
	}
	base, _, err := w.checkin(d.B)
	if err != nil || base == nil {
		return d.F, err
	}
	byName := make(map[string]deck.FileCard, len(base.F)+len(d.F))
	for _, f := range base.F {
		byName[f.Name] = f
	}
	for _, f := range d.F {
		byName[f.Name] = f
	}
	merged := make([]deck.FileCard, 0, len(byName))
	for _, f := range byName {
		merged = append(merged, f)
	}
	return merged, nil
}

func (w *coneWalk) files(files []deck.FileCard, prior map[deck.FileCard]bool, out map[int]bool) error {
	for _, f := range files {
		if err := w.ctx.Err(); err != nil {
			return err
		}
		key := deck.FileCard{Name: f.Name, UUID: f.UUID}
		if f.UUID == "" || prior[key] || !w.cone.Covers(f.Name) {
			continue
		}
		if err := w.add(f.UUID, out); err != nil {
			return err
		}
	}
	return nil
}