coverage — ~bigbes/sr-ht-dolt — 3523280c — beads/prefixes.go

Coverage
95.7% 88/92 statements
Δ
+0.0
Blob
8fceab9
Uncovered L197L246-L247L267-L268L363
1 package beads
2
3 import (
4 "context"
5 "regexp"
6 "sort"
7 "strings"
8 "time"
9
10 "sourcecraft.dev/bigbes/sr-ht-dolt/browse"
11 )
12
13 // --- which database owns "<prefix>-<id>", and which one holds "[[slug]]" ------
14 //
15 // A global-tracker issue that says "blocked by artifacts-nex.2" is naming a row
16 // in another database, and without this the reader has to work out which one and
17 // go there by hand. Two levels of tracker only pay for themselves if they point
18 // at each other.
19 //
20 // Memories name each other the same way and land the same way: the mirroring
21 // workflow files a memory by its type, so `[[srht-service-release]]` written in
22 // one tracker routinely lives in another, and the reference is a dead end
23 // wherever it is read. Both questions are answered from one read of one table —
24 // issue_prefix and the kv.memory.* keys are rows of the same config — so they
25 // are one index and one cached projection rather than two passes over every
26 // database.
27 //
28 // This file answers the one question that needs several databases: given an
29 // id-shaped string or a memory slug in some text, which database — of the ones
30 // this caller may browse — holds it. Whether the answer becomes a link, and what
31 // that link looks like, is the renderer's business; this package renders
32 // nothing.
33 //
34 // Authorization is not here, exactly as it is not in ReadyAcross: handing this
35 // function a database is the statement that the caller may read it. A database
36 // the caller may not browse is one the caller's index has never heard of, which
37 // is what makes an id belonging to it plain text and not a hint that it exists.
38
39 // prefixKey is the config row every beads database stores its own id prefix in
40 // ("global", "artifacts", "sr-ht-dolt", …). It sits in the same config table the
41 // memories do, beside compact_tier2_days and the rest of the tracker's settings.
42 const prefixKey = "issue_prefix"
43
44 // PrefixCache is the index's projection cache: one config projection per
45 // database, gated on the head hash and expiring on ReadyCacheTTL — /ready's
46 // bounds and not a second set (see cache.go). The zero value is usable, so a
47 // holder that has no constructor can carry one as a field.
48 type PrefixCache struct {
49 projectionCache[prefixEntry]
50 }
51
52 // prefixEntry is one database's cached config projection: the issue prefix its
53 // config names, the memory slugs it stores, and the total that read reported.
54 // The total is cached with them rather than recomputed because a cache hit reads
55 // no row — it must say what the read that produced it said, including that the
56 // read was partial.
57 type prefixEntry struct {
58 prefix string
59 // slugs is every kv.memory.* key in that config, prefix stripped, in the
60 // order the read returned them. It is cached beside the prefix because it
61 // comes out of the same rows: a second projection over the same table would
62 // double the reads to answer half the question.
63 slugs []string
64 // configTotal is the config table's reported total, clipped or not. Over Max
65 // it means the read stopped short, and an absent prefix — or an absent
66 // memory — is then a row that was never reached rather than a row that does
67 // not exist.
68 configTotal int
69 }
70
71 // PrefixIndex is prefix → the database that owns it and memory slug → the
72 // database that holds it, over the databases one caller may browse. It is built
73 // per caller and must not be shared between them: what it holds is precisely the
74 // set of databases that caller is allowed to know exists.
75 type PrefixIndex struct {
76 byPrefix map[string]ReadyDatabase
77 // byMemory is slug → the first database listed that stores a memory under it.
78 // First and not "the only one", unlike byPrefix: a prefix two trackers both
79 // claim is an ambiguity, but the same memory slug in two trackers is normally
80 // the same memory — the mirroring workflow re-files one by its type, and a
81 // re-typed memory is left behind in the tracker it moved out of. The caller
82 // lists the database whose page this is first, so a slug present locally
83 // always resolves locally, and the fallback is the caller's listing order.
84 byMemory map[string]ReadyDatabase
85 // Failed lists the databases that could not be read. It is here for the
86 // caller's log and for nothing else: a database that could not be read costs
87 // the ids it owns their link, and a page may not say more than that.
88 Failed []ReadyFailure
89 // Truncated lists the databases whose config table exceeded Max and came back
90 // clipped, in the order the caller listed them. A clipped config is how a
91 // tracker loses its prefix without failing: the issue_prefix row simply was
92 // not among the rows read, so every id pointing at that tracker stops linking
93 // and the index looks complete. It is a row clip, unrelated to the ceiling on
94 // how many databases one build opens.
95 Truncated []PrefixTruncation
96 }
97
98 // PrefixTruncation is one database whose config table came back clipped.
99 type PrefixTruncation struct {
100 Database ReadyDatabase
101 // ShownOf is that config table's reported total: rows that exist, against the
102 // at most Max that were read.
103 ShownOf int
104 }
105
106 // Reference is one id found in a text: where it sits, what it says, and which
107 // database owns it.
108 type Reference struct {
109 Start, End int // byte offsets of the id within the scanned text
110 ID string // the id exactly as written
111 Database ReadyDatabase
112 }
113
114 // idPattern matches an id-shaped token: a prefix of one or more lowercase
115 // alphanumeric segments joined by hyphens, then a hyphen, then the suffix bd
116 // generates — `[0-9a-z]+` with optional dotted parts, which is the `46c.2`
117 // subtask form.
118 //
119 // The suffix carries no hyphen, so the last hyphen of a token is always the
120 // prefix/suffix boundary and the split below is unambiguous even for a prefix
121 // that is itself hyphenated ("sr-ht-dolt-44n.6" is sr-ht-dolt's 44n.6, never
122 // sr-ht's dolt-44n.6). The word boundaries keep a token from being found inside
123 // a longer word, so "Xartifacts-46c" names nothing.
124 //
125 // The token being id-shaped is not what makes it an id: only a prefix the index
126 // knows makes it one. Everything else is left as it was written.
127 var idPattern = regexp.MustCompile(`\b[0-9a-z_]+(?:-[0-9a-z_]+)*-[0-9a-z]+(?:\.[0-9a-z]+)*\b`)
128
129 // PrefixesAcross builds the index over the databases it is handed: for each, the
130 // issue_prefix its config names and the memory slugs its config stores.
131 //
132 // It is bounded exactly as ReadyAcross is — the same head-hash gate, the same
133 // TTL, the same ceiling — because it is the same read pattern: N stores opened
134 // for one request. It is cheaper per database, though: the projection is a
135 // dozen-row table read once for both halves, and the fingerprint is not asked
136 // for separately, since a config table carrying issue_prefix is itself the
137 // statement that this is a bd tracker. A database with no such row simply owns
138 // no prefix, and that answer is cached like any other.
139 //
140 // now is the clock the TTL is measured against, passed in rather than read here
141 // for the reason ReadyAcross takes one: this package reads no hidden clock.
142 //
143 // It returns no error. A database that cannot be opened or read costs the ids it
144 // owns their link and nothing else; it lands in Failed for the caller's log.
145 func PrefixesAcross(
146 ctx context.Context,
147 dbs []ReadyDatabase,
148 open ReadyOpener,
149 cache *PrefixCache,
150 now time.Time,
151 24 ) *PrefixIndex {
152 24 index := &PrefixIndex{
153 24 byPrefix: map[string]ReadyDatabase{},
154 24 byMemory: map[string]ReadyDatabase{},
155 24 }
156 24
157 24 if len(dbs) > ReadyMaxDatabases {
158 1 // The first Max in the order the caller listed them. The caller puts the
159 1 // database whose page this is first, so the one prefix a page cannot do
160 1 // without is the one the ceiling can never drop.
161 1 dbs = dbs[:ReadyMaxDatabases]
162 1 }
163
164 // A prefix two databases both claim is dropped rather than awarded to
165 // whichever was listed first: linking to one of two candidates would be a
166 // guess rendered as a fact, and the id is readable as text either way.
167 24 ambiguous := map[string]bool{}
168 103 for _, d := range dbs {
169 103 entry, err := databasePrefix(ctx, d, open, cache, now)
170 103 if err != nil {
171 2 index.Failed = append(index.Failed, ReadyFailure{Database: d, Err: err})
172 2 continue
173 }
174 101 if entry.configTotal > Max {
175 4 // Recorded before the empty-prefix skip below, because a clipped read is
176 4 // the one case where an empty prefix is not an answer: the row may be
177 4 // sitting in the tail this build never saw.
178 4 index.Truncated = append(index.Truncated, PrefixTruncation{
179 4 Database: d,
180 4 ShownOf: entry.configTotal,
181 4 })
182 4 }
183 // The memory half is recorded before the prefix skip below: a tracker that
184 // names no issue prefix still stores memories, and its slugs are as
185 // linkable as any other's.
186 8097 for _, slug := range entry.slugs {
187 8097 if _, taken := index.byMemory[slug]; !taken {
188 8021 index.byMemory[slug] = d
189 8021 }
190 }
191
192 101 prefix := entry.prefix
193 101 if prefix == "" {
194 8 continue
195 }
196 93 if ambiguous[prefix] {
197 0 continue
198 }
199 93 if _, taken := index.byPrefix[prefix]; taken {
200 1 ambiguous[prefix] = true
201 1 delete(index.byPrefix, prefix)
202 1 continue
203 }
204 92 index.byPrefix[prefix] = d
205 }
206 24 return index
207 }
208
209 // databasePrefix returns one database's issue prefix and the total its config
210 // read reported, from the cache when the head has not moved and by reading
211 // config otherwise.
212 //
213 // The order is the whole point of the gate: open, list branches, and only then
214 // consult the cache. Opening a session and reading the branch list is cheap;
215 // reading rows is not, and on a hit no row is touched.
216 func databasePrefix(
217 ctx context.Context,
218 d ReadyDatabase,
219 open ReadyOpener,
220 cache *PrefixCache,
221 now time.Time,
222 103 ) (prefixEntry, error) {
223 103 sess, err := open(ctx, d)
224 103 if err != nil {
225 1 return prefixEntry{}, err
226 1 }
227 102 defer sess.Close()
228 102
229 102 branches, err := sess.Branches(ctx)
230 102 if err != nil {
231 1 return prefixEntry{}, err
232 1 }
233 101 ref := browse.DefaultBranch(branches)
234 101 if ref == "" {
235 1 // A store with no branches carries no config either: nothing to read and
236 1 // nothing to cache.
237 1 return prefixEntry{}, nil
238 1 }
239 100 head := headHashOf(branches, ref)
240 100 if entry, ok := cache.lookup(d.ID, head, now); ok {
241 7 return entry, nil
242 7 }
243
244 93 entry, err := readConfigProjection(ctx, sess, ref)
245 93 if err != nil {
246 0 return prefixEntry{}, err
247 0 }
248 93 cache.store(d.ID, head, now, entry)
249 93 return entry, nil
250 }
251
252 // readConfigProjection reads one database's config table down to what the index
253 // needs of it: the issue_prefix row, the kv.memory.* keys, and the total that
254 // read reported. A missing table — this is not a bd tracker — is neither a
255 // prefix nor a memory, the treatment every optional table gets here.
256 //
257 // The total comes back with them because the answers this can produce are
258 // otherwise identical: a config with no issue_prefix row and a config whose
259 // issue_prefix row was left past Max both arrive here as no prefix at all, and
260 // the same holds of a memory key.
261 //
262 // The whole table is walked rather than stopped at the prefix row: the memory
263 // keys sit anywhere in it, and one pass is what makes this one read.
264 93 func readConfigProjection(ctx context.Context, sess BrowseSession, ref string) (prefixEntry, error) {
265 93 rows, total, err := readRowsOptional(ctx, sess, ref, memoryTable)
266 93 if err != nil {
267 0 return prefixEntry{}, err
268 0 }
269 93 entry := prefixEntry{configTotal: total}
270 93 if rows == nil {
271 1 return entry, nil
272 1 }
273 92 cols := indexCols(rows.Columns)
274 6265 for _, r := range rowsOf(rows) {
275 6265 key := cell(cols, r, "key")
276 6265 switch {
277 87 case key == prefixKey:
278 87 // Lowercased because that is the case the ids themselves are written in,
279 87 // and the index is looked up by what the text says.
280 87 entry.prefix = strings.ToLower(strings.TrimSpace(cell(cols, r, "value")))
281 6091 case strings.HasPrefix(key, memoryPrefix):
282 6091 // The slug is stored as written and matched as written: `bd remember
283 6091 // --key` is case-sensitive, and two memories differing only in case are
284 6091 // two memories.
285 6091 if slug := strings.TrimPrefix(key, memoryPrefix); slug != "" {
286 6091 entry.slugs = append(entry.slugs, slug)
287 6091 }
288 }
289 }
290 92 return entry, nil
291 }
292
293 // Lookup returns the database owning prefix. A nil index — no database was
294 // readable, or the caller did not build one for this page — knows no prefix,
295 // which is the same answer as an unknown one: not linked.
296 7 func (ix *PrefixIndex) Lookup(prefix string) (ReadyDatabase, bool) {
297 7 if ix == nil {
298 1 return ReadyDatabase{}, false
299 1 }
300 6 d, ok := ix.byPrefix[prefix]
301 6 return d, ok
302 }
303
304 // LookupMemory returns the database holding the memory written under slug. A
305 // slug no database the caller may browse stores is unknown here, which is what
306 // keeps a reference to a memory in a database they may not see indistinguishable
307 // from a reference to one that was never written.
308 7 func (ix *PrefixIndex) LookupMemory(slug string) (ReadyDatabase, bool) {
309 7 if ix == nil {
310 1 return ReadyDatabase{}, false
311 1 }
312 6 d, ok := ix.byMemory[slug]
313 6 return d, ok
314 }
315
316 // MemorySlugs lists the slugs the index knows, in order. Like Prefixes, it
317 // exists for the caller's log line and for tests.
318 2 func (ix *PrefixIndex) MemorySlugs() []string {
319 2 if ix == nil {
320 1 return nil
321 1 }
322 1 out := make([]string, 0, len(ix.byMemory))
323 3 for s := range ix.byMemory {
324 3 out = append(out, s)
325 3 }
326 1 sort.Strings(out)
327 1 return out
328 }
329
330 // Prefixes lists the prefixes the index knows, in order. It exists for the
331 // caller's log line and for tests.
332 15 func (ix *PrefixIndex) Prefixes() []string {
333 15 if ix == nil {
334 1 return nil
335 1 }
336 14 out := make([]string, 0, len(ix.byPrefix))
337 79 for p := range ix.byPrefix {
338 79 out = append(out, p)
339 79 }
340 14 sort.Strings(out)
341 14 return out
342 }
343
344 // Scan returns every id in text whose prefix this index knows, in order and
345 // non-overlapping.
346 //
347 // It answers where the ids are and nothing about how they should be rendered:
348 // the caller escapes the text it was handed and wraps these ranges, which is the
349 // only order in which stored text can become HTML safely.
350 //
351 // An id-shaped token whose prefix the index does not know yields nothing at all,
352 // which is what makes an id in a database the caller may not browse
353 // indistinguishable from one that matches nothing.
354 16 func (ix *PrefixIndex) Scan(text string) []Reference {
355 16 if ix == nil || len(ix.byPrefix) == 0 || text == "" {
356 3 return nil
357 3 }
358 13 var out []Reference
359 16 for _, m := range idPattern.FindAllStringIndex(text, -1) {
360 16 token := text[m[0]:m[1]]
361 16 cut := strings.LastIndex(token, "-")
362 16 if cut <= 0 {
363 0 continue
364 }
365 16 d, ok := ix.byPrefix[token[:cut]]
366 16 if !ok {
367 6 continue
368 }
369 10 out = append(out, Reference{Start: m[0], End: m[1], ID: token, Database: d})
370 }
371 13 return out
372 }