path: root/internal/kwcache/kwcache.go

// 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
}