krino: 0.0.5 — keyword cache, t and d in reviewv0.0.5

1 files changed, 231 insertions, 0 deletions

diff --git a/internal/kwcache/kwcache.go b/internal/kwcache/kwcache.go
new file mode 100644
index 0000000..b61cfb1
--- /dev/null
+++ b/internal/kwcache/kwcache.go
@@ -0,0 +1,231 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+// Package kwcache remembers which content keywords a file's extracted text
+// contains, so a file that has not changed is not extracted again (spec
+// §6.1). It stores answers only, never the text, and knows a file by its
+// ID, never by its name.
+package kwcache
+
+import (
+	"encoding/json"
+	"errors"
+	"fmt"
+	"io/fs"
+	"os"
+	"path/filepath"
+	"sort"
+	"strings"
+	"sync"
+)
+
+// version is the on-disk format; a file of any other version loads empty.
+const version = 1
+
+// ID is how a file is recognised: the same inode with the same size and
+// modification time is taken to hold the same content. A move or rename
+// within one filesystem keeps it.
+type ID struct {
+	Dev, Ino uint64
+	Size     int64
+	MTime    int64 // Unix nanoseconds
+}
+
+// entry is what is known about one file: every keyword it was checked
+// against, and those its text contains.
+type entry struct {
+	checked []string // sorted
+	hits    map[string]bool
+}
+
+// Cache holds one directory's answers: those loaded from disk and those
+// stored during this run. It is safe for concurrent use.
+type Cache struct {
+	fingerprint string
+	existed     bool // Load found a file, so Save must rewrite it even when empty
+
+	mu  sync.Mutex
+	old map[ID]entry
+	cur map[ID]entry
+}
+
+// New returns an empty cache for extractor fingerprint.
+func New(fingerprint string) *Cache {
+	return &Cache{fingerprint: fingerprint, old: map[ID]entry{}, cur: map[ID]entry{}}
+}
+
+type diskFile struct {
+	Dev   uint64 `json:"dev"`
+	Ino   uint64 `json:"ino"`
+	Size  int64  `json:"size"`
+	MTime int64  `json:"mtime"`
+	Set   int    `json:"keywords"` // index into diskCache.Keywords
+	Hits  []int  `json:"hits"`     // indices into that keyword list
+}
+
+type diskCache struct {
+	Version     int        `json:"version"`
+	Fingerprint string     `json:"fingerprint"`
+	Keywords    [][]string `json:"keywords"`
+	Files       []diskFile `json:"files"`
+}
+
+// Load reads the cache at path. A missing file, another format version or
+// another fingerprint is an empty cache and no error; an unreadable file
+// is an empty cache and an error. The cache returned is never nil.
+func Load(path, fingerprint string) (*Cache, error) {
+	c := New(fingerprint)
+	data, err := os.ReadFile(path)
+	if errors.Is(err, fs.ErrNotExist) {
+		return c, nil
+	}
+	c.existed = err == nil
+	if err != nil {
+		return c, err
+	}
+	var d diskCache
+	if err := json.Unmarshal(data, &d); err != nil {
+		return c, fmt.Errorf("%s: %v", path, err)
+	}
+	if d.Version != version || d.Fingerprint != fingerprint {
+		return c, nil
+	}
+	for i, set := range d.Keywords {
+		if !sort.StringsAreSorted(set) {
+			return New(fingerprint), fmt.Errorf("%s: keyword list %d is not sorted", path, i)
+		}
+	}
+	for _, f := range d.Files {
+		if f.Set < 0 || f.Set >= len(d.Keywords) {
+			return New(fingerprint), fmt.Errorf("%s: bad keyword list %d", path, f.Set)
+		}
+		set := d.Keywords[f.Set]
+		hits := make(map[string]bool, len(f.Hits))
+		for _, h := range f.Hits {
+			if h < 0 || h >= len(set) {
+				return New(fingerprint), fmt.Errorf("%s: bad keyword %d", path, h)
+			}
+			hits[set[h]] = true
+		}
+		c.old[ID{Dev: f.Dev, Ino: f.Ino, Size: f.Size, MTime: f.MTime}] = entry{checked: set, hits: hits}
+	}
+	c.existed = true
+	return c, nil
+}
+
+// Lookup reports, for each of keys, whether the text of the file id
+// contains it. ok is false unless an entry for id exists and was checked
+// against every one of keys.
+func (c *Cache) Lookup(id ID, keys []string) (hits []bool, ok bool) {
+	c.mu.Lock()
+	defer c.mu.Unlock()
+	e, found := c.cur[id]
+	if !found {
+		e, found = c.old[id]
+	}
+	if !found {
+		return nil, false
+	}
+	hits = make([]bool, len(keys))
+	for i, k := range keys {
+		j := sort.SearchStrings(e.checked, k)
+		if j == len(e.checked) || e.checked[j] != k {
+			return nil, false
+		}
+		hits[i] = e.hits[k]
+	}
+	return hits, true
+}
+
+// Store records answers, every keyword the file id was checked against
+// and whether its text contains it, replacing anything known about id.
+func (c *Cache) Store(id ID, answers map[string]bool) {
+	e := entry{checked: make([]string, 0, len(answers)), hits: map[string]bool{}}
+	for k, hit := range answers {
+		e.checked = append(e.checked, k)
+		if hit {
+			e.hits[k] = true
+		}
+	}
+	sort.Strings(e.checked)
+	c.mu.Lock()
+	c.cur[id] = e
+	c.mu.Unlock()
+}
+
+// Save writes the entries of the files in present, from this run or loaded,
+// to path, and drops every other: the cache only ever describes files
+// still in the directory. The directory is created 0700 and the file
+// written 0600 under a temporary name, then renamed into place. A cache
+// with nothing to write and no file on disk writes nothing.
+func (c *Cache) Save(path string, present []ID) error {
+	c.mu.Lock()
+	defer c.mu.Unlock()
+
+	d := diskCache{Version: version, Fingerprint: c.fingerprint, Keywords: [][]string{}, Files: []diskFile{}}
+	sets := map[string]int{}
+	seen := map[ID]bool{}
+	for _, id := range present {
+		if seen[id] {
+			continue
+		}
+		seen[id] = true
+		e, ok := c.cur[id]
+		if !ok {
+			e, ok = c.old[id]
+		}
+		if !ok {
+			continue
+		}
+		key := strings.Join(e.checked, "\x00")
+		set, ok := sets[key]
+		if !ok {
+			set = len(d.Keywords)
+			sets[key] = set
+			d.Keywords = append(d.Keywords, e.checked)
+		}
+		f := diskFile{Dev: id.Dev, Ino: id.Ino, Size: id.Size, MTime: id.MTime, Set: set, Hits: []int{}}
+		for i, k := range e.checked {
+			if e.hits[k] {
+				f.Hits = append(f.Hits, i)
+			}
+		}
+		d.Files = append(d.Files, f)
+	}
+	if len(d.Files) == 0 && !c.existed {
+		return nil
+	}
+	sort.Slice(d.Files, func(i, j int) bool {
+		if d.Files[i].Dev != d.Files[j].Dev {
+			return d.Files[i].Dev < d.Files[j].Dev
+		}
+		return d.Files[i].Ino < d.Files[j].Ino
+	})
+
+	data, err := json.Marshal(d)
+	if err != nil {
+		return err
+	}
+	dir := filepath.Dir(path)
+	if err := os.MkdirAll(dir, 0o700); err != nil {
+		return err
+	}
+	tmp, err := os.CreateTemp(dir, ".kwcache-*")
+	if err != nil {
+		return err
+	}
+	if _, err := tmp.Write(data); err != nil {
+		tmp.Close()
+		os.Remove(tmp.Name())
+		return err
+	}
+	if err := tmp.Close(); err != nil {
+		os.Remove(tmp.Name())
+		return err
+	}
+	if err := os.Rename(tmp.Name(), path); err != nil {
+		os.Remove(tmp.Name())
+		return err
+	}
+	c.existed = true
+	return nil
+}