Skip to content
go-libfossil Artifact [2119095c2e]
Login

Artifact [2119095c2e]

Check-ins Using Download Hex

Artifact 2119095c2e6dba838d99fdccf83fc4faa5fcba1a8ea3f1c8c9314da29ecdc24a:

// Package seed mints, holds and applies the seed of draft-fossil-horizon-00
// §5.2: the control artifact an origin mints so that a structural-horizon
// clone, which lacks C's ancestry, derives the branch, tag and closed state
// of every check-in in the held set K exactly as a dense repository does.
//
// An origin mints with Mint. A clone holds the seed with Hold, outside the
// artifact store (§5.2.3's second holding): it is in no blob row, so nothing
// that enumerates or serves artifacts -- unsent, unclustered, private, a
// gimme, a rebuild's re-marking -- can reach it. The derived state is
// persisted, so where zit applies its seed at every open this package applies
// it whenever the derivation runs: when the seed is held, by Rebuild, and by
// Apply, which the sync layer calls after every round that links artifacts so
// an entry arriving after its seed is seeded too.
package seed

import (
	"bytes"
	"crypto/md5"
	"database/sql"
	"encoding/hex"
	"encoding/json"
	"errors"
	"fmt"
	"slices"
	"strconv"
	"strings"
	"time"

	"github.com/danmestas/go-libfossil/db"
	"github.com/danmestas/go-libfossil/internal/clearsign"
	"github.com/danmestas/go-libfossil/internal/cone"
	"github.com/danmestas/go-libfossil/internal/content"
	"github.com/danmestas/go-libfossil/internal/deck"
	libfossil "github.com/danmestas/go-libfossil/internal/fsltype"
	"github.com/danmestas/go-libfossil/internal/hash"
	"github.com/danmestas/go-libfossil/internal/leaf"
	"github.com/danmestas/go-libfossil/internal/manifest"
	"github.com/danmestas/go-libfossil/internal/seedcheck"
	"github.com/danmestas/go-libfossil/internal/tag"
)

// BindingTag names a seed's binding card, T +horizon-seed <C> <rule>
// (§5.2.1): the horizon the seed was minted for, part of the signed bytes,
// and no tag in force, so it is never derived into a seed nor applied.
const BindingTag = seedcheck.Tag

var (
	// ErrNotSeed is returned by Hold for bytes that do not hash to the name
	// they were announced under or do not parse as a control artifact with a
	// D card and T cards (§6.2.3), and by Apply for a held seed that no
	// longer parses.
	ErrNotSeed = errors.New("horizon seed: not a seed")
	// ErrProvenance is returned by Hold when the origin's key does not verify
	// the seed, and wraps ErrUnbound and ErrReplay, since a refused seed is
	// handled as a wrongly signed one (§5.2.4): the clone falls back to the
	// content horizon.
	ErrProvenance = errors.New("horizon seed: provenance does not verify")
	// ErrUnbound is a seed that does not carry exactly one binding card
	// naming the store cone's C and rule (§5.2.4).
	ErrUnbound = errors.New("horizon seed: not bound to this store's horizon")
	// ErrReplay is a seed whose D card is earlier than the held seed's: a
	// newer tag state never yields an earlier D (§5.2.2, §5.2.4).
	ErrReplay = errors.New("horizon seed: dated before the seed held")
	// ErrNothingToSeed is returned by Mint when no tag is in force at any
	// entry, so there is no control artifact to mint; the origin then serves
	// the request as content (§6.2.5).
	ErrNothingToSeed = errors.New("horizon seed: no tag in force at any entry")
)

// Verifier checks a seed against its origin's public key (§5.2.4): nil when
// the seed carries a valid clear-signature by that key. A clone that knows
// no key for its origin passes a nil Verifier and accepts an unsigned seed.
// This package verifies no signature itself: go-libfossil strips a clear-
// signing envelope when it parses (deck.Parse) but implements no signing.
type Verifier func(seed []byte) error

// heldSeedSchema holds the seed in a table of its own, created when a seed is
// held and dropped when it is discarded, like the store cone. It is no
// derived table, so a rebuild keeps it and re-applies it.
const heldSeedSchema = `CREATE TABLE IF NOT EXISTS horizonseed(
  id INTEGER PRIMARY KEY CHECK(id=1),
  seed BLOB NOT NULL
)`

// Entries returns the entries of K (§5.2.1), ascending by rid: C, and every
// check-in of K that names a primary parent outside K. Tag state reaches a
// check-in along its primary parent, so these are where K's state enters
// from below the horizon. A check-in of K other than C that names no parent
// inherits nothing and is no entry, as in zit (src/sparse.zig).
func Entries(q db.Querier, c libfossil.FslID, k []libfossil.FslID) ([]libfossil.FslID, error) {
	if q == nil {
		panic("seed.Entries: q must not be nil")
	}
	if c <= 0 {
		panic("seed.Entries: c must be positive")
	}
	inK := make(map[libfossil.FslID]bool, len(k))
	for _, rid := range k {
		inK[rid] = true
	}
	if !inK[c] {
		return nil, fmt.Errorf("seed.Entries: C rid=%d is not in K", c)
	}
	ids, err := json.Marshal(k)
	if err != nil {
		return nil, fmt.Errorf("seed.Entries: %w", err)
	}
	rows, err := q.Query(`SELECT cid, pid FROM plink
		WHERE isprim=1 AND cid IN (SELECT value FROM json_each(?))`, string(ids))
	if err != nil {
		return nil, fmt.Errorf("seed.Entries: reading plink: %w", err)
	}
	defer rows.Close()
	entries := []libfossil.FslID{c}
	for rows.Next() {
		var cid, pid libfossil.FslID
		if err := rows.Scan(&cid, &pid); err != nil {
			return nil, fmt.Errorf("seed.Entries: reading plink: %w", err)
		}
		if cid != c && !inK[pid] {
			entries = append(entries, cid)
		}
	}
	if err := rows.Err(); err != nil {
		return nil, fmt.Errorf("seed.Entries: reading plink: %w", err)
	}
	slices.Sort(entries)
	return slices.Compact(entries), nil
}

// Mint returns the seed for C and its held set k (horizon.HeldSet) under
// rule, with the SHA3-256 name it is announced under (§6.2.3). It carries one
// T card per tag in force at each entry in this repository's derivation,
// applied to the entry directly: a propagating row as a `*` card, a singleton
// as `+`, each with the value tagxref holds. Cancel rows are not in force and
// are left out, as zit leaves them out (src/sync.zig composeSeed), and so is
// a horizon-seed row (§5.2.1). The binding card, T +horizon-seed <C> <rule>,
// is added to the cards in force and is not one of them.
//
// The D card is the latest mtime of any tag event in the repository, one
// that applied, propagated or cancelled a tag, not the time of minting,
// rounded up to a whole second and written with no fraction (§5.2.2): the
// same at every origin, so two mints over unchanged state yield one name,
// and never earlier than an earlier mint's. A tag event takes effect only
// over an older row and its own row keeps its time, so no new tag event
// moves D back. Dated from the rows in force instead, a cancel of the
// newest one moved D earlier and the clone refused the re-seed as a replay
// (§5.2.4). A shun can still remove the latest rows, so D is also no
// earlier than the latest D this origin has minted, kept in the store's
// config (floorConfig) and raised by every mint. The U card is login, the
// origin's label for the minting implementation. With no row in force there
// is nothing to seed: a control artifact needs a T card, so Mint returns
// ErrNothingToSeed where zit mints a seed of no T card dated at C.
func Mint(q db.Querier, c libfossil.FslID, rule cone.HorizonRule, k []libfossil.FslID, login string) (string, []byte, error) {
	if q == nil {
		panic("seed.Mint: q must not be nil")
	}
	if login == "" {
		panic("seed.Mint: login must not be empty")
	}
	if rule != cone.RuleDescendants && rule != cone.RuleLeaves {
		panic(fmt.Sprintf("seed.Mint: unknown rule %v", rule))
	}
	entries, err := Entries(q, c, k)
	if err != nil {
		return "", nil, err
	}
	var cards []deck.TagCard
	latest, err := latestTagEvent(q)
	if err != nil {
		return "", nil, err
	}
	for _, rid := range entries {
		rowCards, rowLatest, err := cardsAt(q, rid)
		if err != nil {
			return "", nil, err
		}
		cards = append(cards, rowCards...)
		latest = max(latest, rowLatest)
	}
	if len(cards) == 0 {
		return "", nil, ErrNothingToSeed
	}
	var cHash string
	if err := q.QueryRow("SELECT uuid FROM blob WHERE rid=?", c).Scan(&cHash); err != nil {
		return "", nil, fmt.Errorf("seed.Mint: C rid=%d: %w", c, err)
	}
	cards = append(cards, deck.TagCard{Type: deck.TagSingleton, Name: BindingTag, UUID: cHash, Value: rule.String()})
	floor, err := mintedFloor(q)
	if err != nil {
		return "", nil, err
	}
	const second = 1000
	date := time.UnixMilli((max(latest, floor) + second - 1) / second * second).UTC()
	// deck.Marshal writes D to the millisecond; the seed's D is written to
	// the second, as zit writes it, so a seed minted over whole-second tag
	// events is byte-identical to zit's. The cards after D are Marshal's,
	// its Z card replaced by one over the body with D in front.
	tail, err := (&deck.Deck{Type: deck.Control, T: cards, U: deck.User(login)}).Marshal()
	if err != nil {
		return "", nil, fmt.Errorf("seed.Mint: %w", err)
	}
	z := bytes.LastIndex(tail, []byte("Z "))
	body := "D " + date.Format("2006-01-02T15:04:05") + "\n" + string(tail[:z])
	sum := md5.Sum([]byte(body))
	data := []byte(body + "Z " + hex.EncodeToString(sum[:]) + "\n")
	if d, err := parse(data); err != nil || !d.D.Equal(date) {
		panic(fmt.Sprintf("seed.Mint: postcondition: minted seed does not parse back (%v)", err))
	}
	if date.UnixMilli() < floor {
		panic("seed.Mint: postcondition: D is earlier than the minted floor")
	}
	if err := raiseFloor(q, date.UnixMilli()); err != nil {
		return "", nil, err
	}
	return hash.SHA3(data), data, nil
}

// floorConfig is the config row holding the latest D this origin has minted,
// in milliseconds since the Unix epoch, written in decimal as zit keeps it
// (.zit-cache/seed-floor). It is the origin's high-water mark of §5.2.2: a
// shun and purge can remove the latest tag rows, and a seed dated from the
// rows left would be earlier than the one every clone holds. No config group
// carries the row, so it is never sent; it lives with the repository, so it
// survives restarts.
const floorConfig = "horizon-seed-floor"

// mintedFloor returns the floor, or 0 when none is kept or the row is
// unreadable: without it a seed is dated from the tag rows alone, which the
// draft permits (the mark is a SHOULD).
func mintedFloor(q db.Querier) (int64, error) {
	var value string
	err := q.QueryRow("SELECT value FROM config WHERE name=?", floorConfig).Scan(&value)
	if errors.Is(err, sql.ErrNoRows) {
		return 0, nil
	}
	if err != nil {
		return 0, fmt.Errorf("seed.Mint: %s: %w", floorConfig, err)
	}
	floor, err := strconv.ParseInt(value, 10, 64)
	if err != nil || floor < 0 {
		return 0, nil
	}
	return floor, nil
}

// raiseFloor records d as the floor unless a later one is kept. The
// comparison is in the statement, so of two concurrent mints the later D
// stays, whichever writes last.
func raiseFloor(q db.Querier, d int64) error {
	if d <= 0 {
		panic("seed.raiseFloor: d must be positive")
	}
	_, err := q.Exec(`INSERT INTO config(name, value, mtime) VALUES(?1, ?2, strftime('%s','now'))
		ON CONFLICT(name) DO UPDATE SET value=excluded.value, mtime=excluded.mtime
		WHERE coalesce(CAST(config.value AS INTEGER), 0) < CAST(excluded.value AS INTEGER)`,
		floorConfig, strconv.FormatInt(d, 10))
	if err != nil {
		return fmt.Errorf("seed.Mint: %s: %w", floorConfig, err)
	}
	return nil
}

// latestTagEvent is the latest mtime among every tagxref row in the
// repository, cancels and propagated rows included, in milliseconds since
// the Unix epoch, or 0 when there is none.
func latestTagEvent(q db.Querier) (int64, error) {
	var mtimeRaw any
	if err := q.QueryRow("SELECT max(mtime) FROM tagxref").Scan(&mtimeRaw); err != nil {
		return 0, fmt.Errorf("seed.Mint: latest tag event: %w", err)
	}
	if mtimeRaw == nil {
		return 0, nil
	}
	mtime, ok := db.ScanJulianDay(mtimeRaw)
	if !ok {
		return 0, fmt.Errorf("seed.Mint: latest tag event: unreadable mtime %T", mtimeRaw)
	}
	return libfossil.MillisFromJulianDay(mtime), nil
}

// cardsAt returns a T card for every tag in force at rid, applied to rid,
// and the latest of their mtimes in milliseconds since the Unix epoch.
func cardsAt(q db.Querier, rid libfossil.FslID) ([]deck.TagCard, int64, error) {
	var uuid string
	if err := q.QueryRow("SELECT uuid FROM blob WHERE rid=?", rid).Scan(&uuid); err != nil {
		return nil, 0, fmt.Errorf("seed.Mint: entry rid=%d: %w", rid, err)
	}
	rows, err := q.Query(`SELECT tag.tagname, tagxref.tagtype, tagxref.value, tagxref.mtime
		FROM tagxref JOIN tag USING(tagid)
		WHERE tagxref.rid=? AND tagxref.tagtype>0 AND tag.tagname!=?`, rid, BindingTag)
	if err != nil {
		return nil, 0, fmt.Errorf("seed.Mint: tags of rid=%d: %w", rid, err)
	}
	defer rows.Close()
	var cards []deck.TagCard
	var latest int64
	for rows.Next() {
		var name string
		var typ int
		var value sql.NullString
		var mtimeRaw any
		if err := rows.Scan(&name, &typ, &value, &mtimeRaw); err != nil {
			return nil, 0, fmt.Errorf("seed.Mint: tags of rid=%d: %w", rid, err)
		}
		mtime, ok := db.ScanJulianDay(mtimeRaw)
		if !ok {
			return nil, 0, fmt.Errorf("seed.Mint: tag %q of rid=%d: unreadable mtime %T", name, rid, mtimeRaw)
		}
		cardType := deck.TagSingleton
		if typ == tag.TagPropagating {
			cardType = deck.TagPropagating
		}
		cards = append(cards, deck.TagCard{Type: cardType, Name: name, UUID: uuid, Value: value.String})
		latest = max(latest, libfossil.MillisFromJulianDay(mtime))
	}
	if err := rows.Err(); err != nil {
		return nil, 0, fmt.Errorf("seed.Mint: tags of rid=%d: %w", rid, err)
	}
	return cards, latest, nil
}

// Hold makes data, announced under name, the seed this clone holds, and
// applies it. The bytes must hash to name and parse as a control artifact
// (§6.2.3), or ErrNotSeed is returned and nothing changes; verify, when the
// clone knows its origin's key, must accept them (§5.2.4), or ErrProvenance.
// Signed or not, the seed must be bound to the store cone's horizon and
// dated no earlier than the seed held (§5.2.4), or ErrProvenance wrapping
// ErrUnbound or ErrReplay; a deepen discards the held seed first, which
// restarts the floor.
//
// A seed replacing a different one (a re-seed, §5.6) re-derives the whole
// store before applying the new seed: the old seed's rows sit in tagxref
// beside rows real artifacts wrote, and only a re-derivation tells them
// apart, which is what zit gets by deriving afresh at every open. Holding the
// seed already held only applies it again.
//
// Hold is for the seed of the clone's own structural request. The sync layer
// routes a file card to it only when a horizon-seed pragma in the same reply
// named it; an origin never calls it (§5.2.3: it refuses a seed offered to
// it). A seed arriving any other way is dropped (seedcheck), and an artifact
// of its shape that carries neither this store's label nor a binding card
// is stored and crosslinked as the ordinary control artifact it is.
func Hold(tx *db.Tx, name string, data []byte, verify Verifier) error {
	if tx == nil {
		panic("seed.Hold: tx must not be nil")
	}
	if len(data) == 0 || name == "" || !hash.IsValidHash(name) || hash.ContentHash(data, name) != name {
		return fmt.Errorf("%w: the bytes do not hash to %q", ErrNotSeed, name)
	}
	d, err := parse(data)
	if err != nil {
		return err
	}
	if verify != nil {
		if err := verify(data); errors.Is(err, clearsign.ErrCannotVerify) {
			return err // no judgement of the seed: refuse it without falling back
		} else if err != nil {
			return fmt.Errorf("%w: %w", ErrProvenance, err)
		}
	}
	old, err := Held(tx)
	if err != nil {
		return err
	}
	if err := judge(tx, d, old); err != nil {
		return err
	}
	if _, err := tx.Exec(heldSeedSchema); err != nil {
		return fmt.Errorf("seed.Hold: %w", err)
	}
	if _, err := tx.Exec("REPLACE INTO horizonseed(id, seed) VALUES(1, ?)", data); err != nil {
		return fmt.Errorf("seed.Hold: %w", err)
	}
	if old != nil && !bytes.Equal(old, data) {
		if _, err := manifest.Rederive(tx); err != nil {
			return fmt.Errorf("seed.Hold: %w", err)
		}
	}
	applied, err := Apply(tx, nil)
	if err != nil {
		return err
	}
	if !applied {
		panic("seed.Hold: postcondition: the seed just held was not applied")
	}
	return nil
}

// Held returns the seed this clone holds, or nil when it holds none.
func Held(q db.Querier) ([]byte, error) {
	if q == nil {
		panic("seed.Held: q must not be nil")
	}
	var n int
	if err := q.QueryRow(
		"SELECT count(*) FROM sqlite_master WHERE type='table' AND name='horizonseed'",
	).Scan(&n); err != nil {
		return nil, fmt.Errorf("seed.Held: %w", err)
	}
	if n == 0 {
		return nil, nil
	}
	var data []byte
	err := q.QueryRow("SELECT seed FROM horizonseed WHERE id=1").Scan(&data)
	if errors.Is(err, sql.ErrNoRows) {
		return nil, nil
	}
	if err != nil {
		return nil, fmt.Errorf("seed.Held: %w", err)
	}
	return data, nil
}

// Apply applies the held seed to the derived state as crosslinking a held
// control artifact would (§5.2.3): each T card at the D card's time, on the
// check-in it names, propagating from there, with the leaf rechecks that
// schedules. It reports whether a seed is held and applied.
//
// Each row it writes names its target as its source, as a check-in's own
// inline card does: the seed is no blob, and a positive source keeps a date
// tag in force. A card whose target this store has not linked yet is
// skipped: held and unlinked, a row sourced from it would read as its own
// link and keep the crosslink from ever linking it. The sync layer calls
// Apply again after each round that links artifacts, and a card already
// applied is superseded by its own row, so a repeat costs a lookup per card.
//
// verify, when the clone knows its origin's key, re-checks the held seed
// (§5.2.4: every seed it holds); a seed that fails, or that is no longer
// bound to the store's horizon, is discarded, the store re-derived without
// it, and false returned, so the caller falls back to the content horizon.
// The binding card is applied to nothing.
func Apply(tx *db.Tx, verify Verifier) (bool, error) {
	if tx == nil {
		panic("seed.Apply: tx must not be nil")
	}
	data, err := Held(tx)
	if err != nil || data == nil {
		return false, err
	}
	if verify != nil {
		// A verifier that could not judge the seed (gpg absent or timed out)
		// fails the caller and keeps the seed, which verified when it was
		// held: discarding it would downgrade the store for good over a
		// passing fault.
		if err := verify(data); errors.Is(err, clearsign.ErrCannotVerify) {
			return false, err
		} else if err != nil {
			return false, Discard(tx)
		}
	}
	d, err := parse(data)
	if err != nil {
		return false, err
	}
	if err := judge(tx, d, nil); errors.Is(err, ErrProvenance) {
		return false, Discard(tx)
	} else if err != nil {
		return false, err
	}
	mtime := libfossil.TimeToJulian(d.D)
	leaves := leaf.NewPending()
	for _, tc := range d.T {
		if tc.Name == BindingTag {
			continue
		}
		var target libfossil.FslID
		err := tx.QueryRow(`SELECT rid FROM blob WHERE uuid=? AND size>=0
			AND EXISTS(SELECT 1 FROM event WHERE objid=blob.rid)`, tc.UUID).Scan(&target)
		if errors.Is(err, sql.ErrNoRows) {
			continue
		}
		if err != nil {
			return false, fmt.Errorf("seed.Apply: target %s: %w", tc.UUID, err)
		}
		if err := tag.ApplyTagWithTx(tx, tag.ApplyOpts{
			TargetRID: target,
			SrcRID:    target,
			TagName:   tc.Name,
			TagType:   tagType(tc.Type),
			Value:     tc.Value,
			MTime:     mtime,
			Leaves:    leaves,
		}); err != nil {
			return false, fmt.Errorf("seed.Apply: tag %q on %s: %w", tc.Name, tc.UUID, err)
		}
	}
	if err := leaves.Apply(tx); err != nil {
		return false, fmt.Errorf("seed.Apply: %w", err)
	}
	return true, nil
}

// Discard drops the held seed and re-derives the store without it. A
// deepening clone discards the seed for C before it applies the seed for C'
// (§5.8); the seed is local, so this has no synchronization consequence.
func Discard(tx *db.Tx) error {
	if tx == nil {
		panic("seed.Discard: tx must not be nil")
	}
	old, err := Held(tx)
	if err != nil || old == nil {
		return err
	}
	if _, err := tx.Exec("DROP TABLE horizonseed"); err != nil {
		return fmt.Errorf("seed.Discard: %w", err)
	}
	if _, err := manifest.Rederive(tx); err != nil {
		return fmt.Errorf("seed.Discard: %w", err)
	}
	return nil
}

// judge checks the seed d before it is held or applied (§5.2.4): exactly one
// binding card, naming the store cone's C and rule, and, against held, the
// seed held if any, a D card no earlier than held's. A held seed that does
// not parse sets no floor.
func judge(q db.Querier, d *deck.Deck, held []byte) error {
	if q == nil || d == nil {
		panic("seed.judge: nil querier or seed")
	}
	sc, err := content.StoreCone(q)
	if err != nil {
		return err
	}
	var hz cone.Horizon
	ok := false
	if sc != nil {
		hz, ok = sc.Horizon()
	}
	n, bound := 0, false
	for _, tc := range d.T {
		if tc.Name == BindingTag {
			n++
			bound = ok && tc.Type == deck.TagSingleton && strings.EqualFold(tc.UUID, hz.Hash()) &&
				tc.Value == hz.Rule().String()
		}
	}
	if n != 1 || !bound {
		return fmt.Errorf("%w: %w", ErrProvenance, ErrUnbound)
	}
	if held == nil {
		return nil
	}
	if h, err := parse(held); err == nil && d.D.Before(h.D) {
		return fmt.Errorf("%w: %w: %s, held %s", ErrProvenance, ErrReplay, d.D.Format(time.DateTime), h.D.Format(time.DateTime))
	}
	return nil
}

// parse reads data as a seed: a control artifact with a D card and at least
// one T card. deck.Parse strips a clear-signing envelope first.
func parse(data []byte) (*deck.Deck, error) {
	d, err := deck.Parse(data)
	if err != nil {
		return nil, fmt.Errorf("%w: %w", ErrNotSeed, err)
	}
	if d.Type != deck.Control || d.D.IsZero() || len(d.T) == 0 {
		return nil, fmt.Errorf("%w: not a control artifact with D and T cards", ErrNotSeed)
	}
	return d, nil
}

func tagType(t deck.TagType) int {
	switch t {
	case deck.TagPropagating:
		return tag.TagPropagating
	case deck.TagSingleton:
		return tag.TagSingleton
	case deck.TagCancel:
		return tag.TagCancel
	}
	panic(fmt.Sprintf("seed.tagType: unknown tag type %q", t))
}