Artifact [c88e5c31b2]

Artifact c88e5c31b2bfd41da1c5890fcf9716d979e4a3d294e5c4416bfdb8b4e9276153:

• File internal/sync/sparse_walk.go — part of check-in [352a0d9e0b] at 2026-10-22 12:02:50 on branch feat/horizon-cones — feat(sync): serve the content horizon and send its pragma

  A horizon store asked every peer for the whole history and threw away what fell below C on arrival, so a horizon clone cost a dense clone's bandwidth. draft-fossil-horizon-00 §6 lets the request carry the horizon and the origin restrict what it sends.

  The client sends `pragma horizon HASH RULE` after its path-cone pragmas on every clone and pull, never horizon-structural, and counts the replies that say `pragma horizon-served content` (HorizonServed on the clone and sync results, internal and public). It still classifies every reply locally, so a horizon-ignorant peer stays correct (§6.3).

  The handler reads the pragma into the request's cone and serves it through the existing keep machinery rather than a parallel path: the pull inventory's keep set drops the blobs below the horizon (via ConeReferences.HorizonBelow) and every cluster; the clone walk walks the tree of a held-set check-in only, counts a parent as sent only inside the held set, and sends every sub-manifest node at its row while sending no cluster. A crossing delta is inflated through the same sourceKept test the path cone uses, charged to the round's batch. req-clusters under a horizon answers nothing, and every reply says horizon-served content.

  A horizon store refuses, through refuseClone, a dense clone and a horizon whose held set is not inside its own, both computed over the store with horizon.Place. That is the spec's subset test; zit refuses any other C or rule. A path-only store now also refuses a horizon-only request, which keeps every path.

  Interop with zit at horizon-rfc bbd1435674 holds both ways: zit clones and pulls at a horizon from the handler, the client from `zit serve`, and each side's horizon store refuses the other's dense clone. (user: [email protected], size: 8276) [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
	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, and its parent counts as sent only when it is
// in the held set too: the blobs sent are those above the horizon. Every
// node and every other structural artifact but a cluster goes out at its
// row, as §4.1 holds them at every age.
type coneWalk struct {
	ctx        context.Context
	h          *handler
	cone       *cone.Cone
	horizon    bool
	held       map[int]bool // the held set; nil when there is no horizon or the store cannot place C
	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()
	return &coneWalk{ctx: ctx, h: h, cone: h.cone, horizon: horizon, kinds: map[int]sparseKind{},
		decks: map[int]*deck.Deck{}, reached: map[int]bool{}, path: map[string]bool{}}
}

// 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
	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
}

// 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)
	return w.atRow(kind)
}

// 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):
	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
}

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
}