package beads
import (
"context"
"regexp"
"sort"
"strings"
"time"
"sourcecraft.dev/bigbes/sr-ht-dolt/browse"
)
// --- which database owns "<prefix>-<id>", and which one holds "[[slug]]" ------
//
// A global-tracker issue that says "blocked by artifacts-nex.2" is naming a row
// in another database, and without this the reader has to work out which one and
// go there by hand. Two levels of tracker only pay for themselves if they point
// at each other.
//
// Memories name each other the same way and land the same way: the mirroring
// workflow files a memory by its type, so `[[srht-service-release]]` written in
// one tracker routinely lives in another, and the reference is a dead end
// wherever it is read. Both questions are answered from one read of one table —
// issue_prefix and the kv.memory.* keys are rows of the same config — so they
// are one index and one cached projection rather than two passes over every
// database.
//
// This file answers the one question that needs several databases: given an
// id-shaped string or a memory slug in some text, which database — of the ones
// this caller may browse — holds it. Whether the answer becomes a link, and what
// that link looks like, is the renderer's business; this package renders
// nothing.
//
// Authorization is not here, exactly as it is not in ReadyAcross: handing this
// function a database is the statement that the caller may read it. A database
// the caller may not browse is one the caller's index has never heard of, which
// is what makes an id belonging to it plain text and not a hint that it exists.
// prefixKey is the config row every beads database stores its own id prefix in
// ("global", "artifacts", "sr-ht-dolt", …). It sits in the same config table the
// memories do, beside compact_tier2_days and the rest of the tracker's settings.
const prefixKey = "issue_prefix"
// PrefixCache is the index's projection cache: one config projection per
// database, gated on the head hash and expiring on ReadyCacheTTL — /ready's
// bounds and not a second set (see cache.go). The zero value is usable, so a
// holder that has no constructor can carry one as a field.
type PrefixCache struct {
projectionCache[prefixEntry]
}
// prefixEntry is one database's cached config projection: the issue prefix its
// config names, the memory slugs it stores, and the total that read reported.
// The total is cached with them rather than recomputed because a cache hit reads
// no row — it must say what the read that produced it said, including that the
// read was partial.
type prefixEntry struct {
prefix string
// slugs is every kv.memory.* key in that config, prefix stripped, in the
// order the read returned them. It is cached beside the prefix because it
// comes out of the same rows: a second projection over the same table would
// double the reads to answer half the question.
slugs []string
// configTotal is the config table's reported total, clipped or not. Over Max
// it means the read stopped short, and an absent prefix — or an absent
// memory — is then a row that was never reached rather than a row that does
// not exist.
configTotal int
}
// PrefixIndex is prefix → the database that owns it and memory slug → the
// database that holds it, over the databases one caller may browse. It is built
// per caller and must not be shared between them: what it holds is precisely the
// set of databases that caller is allowed to know exists.
type PrefixIndex struct {
byPrefix map[string]ReadyDatabase
// byMemory is slug → the first database listed that stores a memory under it.
// First and not "the only one", unlike byPrefix: a prefix two trackers both
// claim is an ambiguity, but the same memory slug in two trackers is normally
// the same memory — the mirroring workflow re-files one by its type, and a
// re-typed memory is left behind in the tracker it moved out of. The caller
// lists the database whose page this is first, so a slug present locally
// always resolves locally, and the fallback is the caller's listing order.
byMemory map[string]ReadyDatabase
// Failed lists the databases that could not be read. It is here for the
// caller's log and for nothing else: a database that could not be read costs
// the ids it owns their link, and a page may not say more than that.
Failed []ReadyFailure
// Truncated lists the databases whose config table exceeded Max and came back
// clipped, in the order the caller listed them. A clipped config is how a
// tracker loses its prefix without failing: the issue_prefix row simply was
// not among the rows read, so every id pointing at that tracker stops linking
// and the index looks complete. It is a row clip, unrelated to the ceiling on
// how many databases one build opens.
Truncated []PrefixTruncation
}
// PrefixTruncation is one database whose config table came back clipped.
type PrefixTruncation struct {
Database ReadyDatabase
// ShownOf is that config table's reported total: rows that exist, against the
// at most Max that were read.
ShownOf int
}
// Reference is one id found in a text: where it sits, what it says, and which
// database owns it.
type Reference struct {
Start, End int // byte offsets of the id within the scanned text
ID string // the id exactly as written
Database ReadyDatabase
}
// idPattern matches an id-shaped token: a prefix of one or more lowercase
// alphanumeric segments joined by hyphens, then a hyphen, then the suffix bd
// generates — `[0-9a-z]+` with optional dotted parts, which is the `46c.2`
// subtask form.
//
// The suffix carries no hyphen, so the last hyphen of a token is always the
// prefix/suffix boundary and the split below is unambiguous even for a prefix
// that is itself hyphenated ("sr-ht-dolt-44n.6" is sr-ht-dolt's 44n.6, never
// sr-ht's dolt-44n.6). The word boundaries keep a token from being found inside
// a longer word, so "Xartifacts-46c" names nothing.
//
// The token being id-shaped is not what makes it an id: only a prefix the index
// knows makes it one. Everything else is left as it was written.
var idPattern = regexp.MustCompile(`\b[0-9a-z_]+(?:-[0-9a-z_]+)*-[0-9a-z]+(?:\.[0-9a-z]+)*\b`)
// PrefixesAcross builds the index over the databases it is handed: for each, the
// issue_prefix its config names and the memory slugs its config stores.
//
// It is bounded exactly as ReadyAcross is — the same head-hash gate, the same
// TTL, the same ceiling — because it is the same read pattern: N stores opened
// for one request. It is cheaper per database, though: the projection is a
// dozen-row table read once for both halves, and the fingerprint is not asked
// for separately, since a config table carrying issue_prefix is itself the
// statement that this is a bd tracker. A database with no such row simply owns
// no prefix, and that answer is cached like any other.
//
// now is the clock the TTL is measured against, passed in rather than read here
// for the reason ReadyAcross takes one: this package reads no hidden clock.
//
// It returns no error. A database that cannot be opened or read costs the ids it
// owns their link and nothing else; it lands in Failed for the caller's log.
func PrefixesAcross(
ctx context.Context,
dbs []ReadyDatabase,
open ReadyOpener,
cache *PrefixCache,
now time.Time,
) *PrefixIndex {
index := &PrefixIndex{
byPrefix: map[string]ReadyDatabase{},
byMemory: map[string]ReadyDatabase{},
}
if len(dbs) > ReadyMaxDatabases {
// The first Max in the order the caller listed them. The caller puts the
// database whose page this is first, so the one prefix a page cannot do
// without is the one the ceiling can never drop.
dbs = dbs[:ReadyMaxDatabases]
}
// A prefix two databases both claim is dropped rather than awarded to
// whichever was listed first: linking to one of two candidates would be a
// guess rendered as a fact, and the id is readable as text either way.
ambiguous := map[string]bool{}
for _, d := range dbs {
entry, err := databasePrefix(ctx, d, open, cache, now)
if err != nil {
index.Failed = append(index.Failed, ReadyFailure{Database: d, Err: err})
continue
}
if entry.configTotal > Max {
// Recorded before the empty-prefix skip below, because a clipped read is
// the one case where an empty prefix is not an answer: the row may be
// sitting in the tail this build never saw.
index.Truncated = append(index.Truncated, PrefixTruncation{
Database: d,
ShownOf: entry.configTotal,
})
}
// The memory half is recorded before the prefix skip below: a tracker that
// names no issue prefix still stores memories, and its slugs are as
// linkable as any other's.
for _, slug := range entry.slugs {
if _, taken := index.byMemory[slug]; !taken {
index.byMemory[slug] = d
}
}
prefix := entry.prefix
if prefix == "" {
continue
}
if ambiguous[prefix] {
continue
}
if _, taken := index.byPrefix[prefix]; taken {
ambiguous[prefix] = true
delete(index.byPrefix, prefix)
continue
}
index.byPrefix[prefix] = d
}
return index
}
// databasePrefix returns one database's issue prefix and the total its config
// read reported, from the cache when the head has not moved and by reading
// config otherwise.
//
// The order is the whole point of the gate: open, list branches, and only then
// consult the cache. Opening a session and reading the branch list is cheap;
// reading rows is not, and on a hit no row is touched.
func databasePrefix(
ctx context.Context,
d ReadyDatabase,
open ReadyOpener,
cache *PrefixCache,
now time.Time,
) (prefixEntry, error) {
sess, err := open(ctx, d)
if err != nil {
return prefixEntry{}, err
}
defer sess.Close()
branches, err := sess.Branches(ctx)
if err != nil {
return prefixEntry{}, err
}
ref := browse.DefaultBranch(branches)
if ref == "" {
// A store with no branches carries no config either: nothing to read and
// nothing to cache.
return prefixEntry{}, nil
}
head := headHashOf(branches, ref)
if entry, ok := cache.lookup(d.ID, head, now); ok {
return entry, nil
}
entry, err := readConfigProjection(ctx, sess, ref)
if err != nil {
return prefixEntry{}, err
}
cache.store(d.ID, head, now, entry)
return entry, nil
}
// readConfigProjection reads one database's config table down to what the index
// needs of it: the issue_prefix row, the kv.memory.* keys, and the total that
// read reported. A missing table — this is not a bd tracker — is neither a
// prefix nor a memory, the treatment every optional table gets here.
//
// The total comes back with them because the answers this can produce are
// otherwise identical: a config with no issue_prefix row and a config whose
// issue_prefix row was left past Max both arrive here as no prefix at all, and
// the same holds of a memory key.
//
// The whole table is walked rather than stopped at the prefix row: the memory
// keys sit anywhere in it, and one pass is what makes this one read.
func readConfigProjection(ctx context.Context, sess BrowseSession, ref string) (prefixEntry, error) {
rows, total, err := readRowsOptional(ctx, sess, ref, memoryTable)
if err != nil {
return prefixEntry{}, err
}
entry := prefixEntry{configTotal: total}
if rows == nil {
return entry, nil
}
cols := indexCols(rows.Columns)
for _, r := range rowsOf(rows) {
key := cell(cols, r, "key")
switch {
case key == prefixKey:
// Lowercased because that is the case the ids themselves are written in,
// and the index is looked up by what the text says.
entry.prefix = strings.ToLower(strings.TrimSpace(cell(cols, r, "value")))
case strings.HasPrefix(key, memoryPrefix):
// The slug is stored as written and matched as written: `bd remember
// --key` is case-sensitive, and two memories differing only in case are
// two memories.
if slug := strings.TrimPrefix(key, memoryPrefix); slug != "" {
entry.slugs = append(entry.slugs, slug)
}
}
}
return entry, nil
}
// Lookup returns the database owning prefix. A nil index — no database was
// readable, or the caller did not build one for this page — knows no prefix,
// which is the same answer as an unknown one: not linked.
func (ix *PrefixIndex) Lookup(prefix string) (ReadyDatabase, bool) {
if ix == nil {
return ReadyDatabase{}, false
}
d, ok := ix.byPrefix[prefix]
return d, ok
}
// LookupMemory returns the database holding the memory written under slug. A
// slug no database the caller may browse stores is unknown here, which is what
// keeps a reference to a memory in a database they may not see indistinguishable
// from a reference to one that was never written.
func (ix *PrefixIndex) LookupMemory(slug string) (ReadyDatabase, bool) {
if ix == nil {
return ReadyDatabase{}, false
}
d, ok := ix.byMemory[slug]
return d, ok
}
// MemorySlugs lists the slugs the index knows, in order. Like Prefixes, it
// exists for the caller's log line and for tests.
func (ix *PrefixIndex) MemorySlugs() []string {
if ix == nil {
return nil
}
out := make([]string, 0, len(ix.byMemory))
for s := range ix.byMemory {
out = append(out, s)
}
sort.Strings(out)
return out
}
// Prefixes lists the prefixes the index knows, in order. It exists for the
// caller's log line and for tests.
func (ix *PrefixIndex) Prefixes() []string {
if ix == nil {
return nil
}
out := make([]string, 0, len(ix.byPrefix))
for p := range ix.byPrefix {
out = append(out, p)
}
sort.Strings(out)
return out
}
// Scan returns every id in text whose prefix this index knows, in order and
// non-overlapping.
//
// It answers where the ids are and nothing about how they should be rendered:
// the caller escapes the text it was handed and wraps these ranges, which is the
// only order in which stored text can become HTML safely.
//
// An id-shaped token whose prefix the index does not know yields nothing at all,
// which is what makes an id in a database the caller may not browse
// indistinguishable from one that matches nothing.
func (ix *PrefixIndex) Scan(text string) []Reference {
if ix == nil || len(ix.byPrefix) == 0 || text == "" {
return nil
}
var out []Reference
for _, m := range idPattern.FindAllStringIndex(text, -1) {
token := text[m[0]:m[1]]
cut := strings.LastIndex(token, "-")
if cut <= 0 {
continue
}
d, ok := ix.byPrefix[token[:cut]]
if !ok {
continue
}
out = append(out, Reference{Start: m[0], End: m[1], ID: token, Database: d})
}
return out
}