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

2 files changed, 411 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
+}
diff --git a/internal/kwcache/kwcache_test.go b/internal/kwcache/kwcache_test.go
new file mode 100644
index 0000000..8395b2d
--- /dev/null
+++ b/internal/kwcache/kwcache_test.go
@@ -0,0 +1,180 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+package kwcache
+
+import (
+	"os"
+	"path/filepath"
+	"reflect"
+	"testing"
+)
+
+var (
+	a = ID{Dev: 1, Ino: 10, Size: 100, MTime: 1000}
+	b = ID{Dev: 1, Ino: 11, Size: 200, MTime: 2000}
+)
+
+func saved(t *testing.T, c *Cache, present ...ID) string {
+	t.Helper()
+	path := filepath.Join(t.TempDir(), "sub", "dl.cache")
+	if err := c.Save(path, present); err != nil {
+		t.Fatal(err)
+	}
+	return path
+}
+
+// TestLookupAfterReload: answers stored and saved come back after a Load
+// with the same fingerprint, for any keywords the entry covers.
+func TestLookupAfterReload(t *testing.T) {
+	c := New("fp")
+	c.Store(a, map[string]bool{"k:acme": true, "k:faktura": false, "k:nip": true})
+	path := saved(t, c, a)
+
+	got, err := Load(path, "fp")
+	if err != nil {
+		t.Fatal(err)
+	}
+	hits, ok := got.Lookup(a, []string{"k:faktura", "k:nip"})
+	if !ok || !reflect.DeepEqual(hits, []bool{false, true}) {
+		t.Errorf("Lookup = %v, %v; want [false true], true", hits, ok)
+	}
+	if _, ok := got.Lookup(a, []string{"k:acme", "k:new"}); ok {
+		t.Error("a keyword the entry was never checked against must be a miss")
+	}
+	if _, ok := got.Lookup(b, []string{"k:acme"}); ok {
+		t.Error("a file never stored must be a miss")
+	}
+}
+
+// TestLookupBeforeSave: what was stored in this run answers at once.
+func TestLookupBeforeSave(t *testing.T) {
+	c := New("fp")
+	c.Store(a, map[string]bool{"k:acme": true})
+	if hits, ok := c.Lookup(a, []string{"k:acme"}); !ok || !hits[0] {
+		t.Errorf("Lookup = %v, %v", hits, ok)
+	}
+}
+
+// TestChangedFileMisses: a different size or modification time is a
+// different ID, so nothing stored for the old one answers.
+func TestChangedFileMisses(t *testing.T) {
+	c := New("fp")
+	c.Store(a, map[string]bool{"k:acme": true})
+	for _, id := range []ID{{Dev: 1, Ino: 10, Size: 101, MTime: 1000}, {Dev: 1, Ino: 10, Size: 100, MTime: 1001}} {
+		if _, ok := c.Lookup(id, []string{"k:acme"}); ok {
+			t.Errorf("%+v answered from %+v's entry", id, a)
+		}
+	}
+}
+
+// TestFingerprintMismatchDiscardsAll: a cache written under a different
+// extractor fingerprint loads empty, without error.
+func TestFingerprintMismatchDiscardsAll(t *testing.T) {
+	c := New("old")
+	c.Store(a, map[string]bool{"k:acme": true})
+	path := saved(t, c, a)
+	got, err := Load(path, "new")
+	if err != nil {
+		t.Fatal(err)
+	}
+	if _, ok := got.Lookup(a, []string{"k:acme"}); ok {
+		t.Error("entry survived a fingerprint change")
+	}
+}
+
+// TestSaveKeepsOnlyPresentFiles: entries for files not passed to Save, from
+// this run or an earlier one, are dropped.
+func TestSaveKeepsOnlyPresentFiles(t *testing.T) {
+	c := New("fp")
+	c.Store(a, map[string]bool{"k:acme": true})
+	c.Store(b, map[string]bool{"k:acme": false})
+	path := saved(t, c, a, b)
+
+	next, err := Load(path, "fp")
+	if err != nil {
+		t.Fatal(err)
+	}
+	if err := next.Save(path, []ID{b}); err != nil {
+		t.Fatal(err)
+	}
+	last, err := Load(path, "fp")
+	if err != nil {
+		t.Fatal(err)
+	}
+	if _, ok := last.Lookup(a, []string{"k:acme"}); ok {
+		t.Error("a is gone from the directory but its entry was kept")
+	}
+	if hits, ok := last.Lookup(b, []string{"k:acme"}); !ok || hits[0] {
+		t.Errorf("b's entry lost across a reload: %v, %v", hits, ok)
+	}
+}
+
+// TestStoreReplacesLoadedEntry: a file read again this run replaces what
+// an earlier run stored for it.
+func TestStoreReplacesLoadedEntry(t *testing.T) {
+	c := New("fp")
+	c.Store(a, map[string]bool{"k:acme": true})
+	path := saved(t, c, a)
+	next, _ := Load(path, "fp")
+	next.Store(a, map[string]bool{"k:acme": false, "k:new": true})
+	if hits, ok := next.Lookup(a, []string{"k:acme", "k:new"}); !ok || hits[0] || !hits[1] {
+		t.Errorf("Lookup = %v, %v; want the new entry", hits, ok)
+	}
+}
+
+// TestSavePermissions: the directory is private and the file readable by
+// its owner only, with no temporary file left behind.
+func TestSavePermissions(t *testing.T) {
+	c := New("fp")
+	c.Store(a, map[string]bool{"k:acme": true})
+	path := saved(t, c, a)
+	fi, err := os.Stat(path)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if perm := fi.Mode().Perm(); perm != 0o600 {
+		t.Errorf("file mode %o, want 600", perm)
+	}
+	di, err := os.Stat(filepath.Dir(path))
+	if err != nil {
+		t.Fatal(err)
+	}
+	if perm := di.Mode().Perm(); perm != 0o700 {
+		t.Errorf("directory mode %o, want 700", perm)
+	}
+	entries, _ := os.ReadDir(filepath.Dir(path))
+	if len(entries) != 1 {
+		t.Errorf("directory holds %d entries, want only the cache", len(entries))
+	}
+}
+
+// TestLoadMissingAndCorrupt: no file is an empty cache and no error; an
+// unreadable one is an empty cache and an error saying so.
+func TestLoadMissingAndCorrupt(t *testing.T) {
+	dir := t.TempDir()
+	c, err := Load(filepath.Join(dir, "none.cache"), "fp")
+	if err != nil || c == nil {
+		t.Fatalf("missing: %v, %v", c, err)
+	}
+	bad := filepath.Join(dir, "bad.cache")
+	os.WriteFile(bad, []byte("{not json"), 0o600)
+	c, err = Load(bad, "fp")
+	if err == nil || c == nil {
+		t.Fatalf("corrupt: want an empty cache and an error, got %v, %v", c, err)
+	}
+	if _, ok := c.Lookup(a, []string{"k:acme"}); ok {
+		t.Error("corrupt cache answered")
+	}
+}
+
+// TestSaveWithNothingWritesNothing: a cache that never held an entry, and
+// has no file yet, creates none.
+func TestSaveWithNothingWritesNothing(t *testing.T) {
+	path := filepath.Join(t.TempDir(), "sub", "dl.cache")
+	if err := New("fp").Save(path, []ID{a}); err != nil {
+		t.Fatal(err)
+	}
+	if _, err := os.Stat(filepath.Dir(path)); !os.IsNotExist(err) {
+		t.Errorf("Save created %s for an empty cache", filepath.Dir(path))
+	}
+}