1 files changed, 398 insertions, 0 deletions
diff --git a/internal/dup/dup.go b/internal/dup/dup.go
new file mode 100644
index 0000000..502ef31
--- /dev/null
+++ b/internal/dup/dup.go
@@ -0,0 +1,398 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+// Package dup answers "is this file a duplicate, and of which original?"
+// cheaply: candidates are grouped by size, and only hashed when sizes
+// collide — a partial hash first, a full hash only on a partial collision.
+package dup
+
+import (
+	"crypto/sha256"
+	"encoding/binary"
+	"errors"
+	"fmt"
+	"io"
+	"io/fs"
+	"os"
+	"path/filepath"
+	"sync"
+	"time"
+
+	"krino/internal/scan"
+)
+
+// partialChunk is the size of the head and tail read for the partial hash.
+const partialChunk = 64 << 10 // 64 KiB
+
+// candidate is one file the index knows about: a scanned file, or a file
+// found under one of the extra directories.
+type candidate struct {
+	path    string
+	size    int64
+	modTime time.Time
+	name    string
+	extra   bool // found under one of the extra directories, not scanned
+}
+
+// Index finds files with identical content among the scanned files and,
+// optionally, every regular file under some extra directories.
+type Index struct {
+	candidates []candidate
+	bySize     map[int64][]int // size -> indexes into candidates
+	scanned    map[string]int  // scanned file path -> index into candidates
+
+	mu      sync.Mutex
+	partial map[string][sha256.Size]byte // memoised partial hash, by path
+	full    map[string][sha256.Size]byte // memoised full hash, by path
+
+	candErrs    []CandidateError
+	candErrSeen map[string]bool // path already recorded in candErrs
+}
+
+// CandidateError is one candidate (never the file Lookup was asked about)
+// that could not be hashed, so it was skipped rather than comparing it.
+type CandidateError struct {
+	Path string
+	Err  error
+}
+
+func (e CandidateError) Error() string { return e.Path + ": " + e.Err.Error() }
+
+// NewIndex stats the extra directories (recursively, symlinks skipped). A
+// missing or unreadable extra directory is reported in the error list and
+// otherwise ignored; an unreadable subdirectory found while walking an
+// otherwise-readable extra directory adds its own error but does not stop
+// the rest of that directory from being indexed. An extra directory that is
+// itself a symlink (A4) is not followed either — filepath.WalkDir Lstats
+// its root, so left unchecked it would be indexed as silently empty — and
+// is reported in the error list instead. Nothing is hashed yet.
+func NewIndex(files []scan.File, extra []string) (*Index, []error) {
+	x := &Index{
+		bySize:  make(map[int64][]int),
+		scanned: make(map[string]int, len(files)),
+		partial: make(map[string][sha256.Size]byte),
+		full:    make(map[string][sha256.Size]byte),
+	}
+	for _, f := range files {
+		x.scanned[f.Path] = x.add(candidate{path: f.Path, size: f.Size, modTime: f.ModTime, name: f.Name})
+	}
+
+	var errs []error
+	for _, dir := range extra {
+		errs = append(errs, x.addExtraDir(dir)...)
+	}
+	return x, errs
+}
+
+// add appends c to the candidate list and its size group, and returns its
+// index.
+func (x *Index) add(c candidate) int {
+	idx := len(x.candidates)
+	x.candidates = append(x.candidates, c)
+	x.bySize[c.size] = append(x.bySize[c.size], idx)
+	return idx
+}
+
+// addExtraDir walks dir, adding every regular file found (symlinks, both to
+// files and to directories, are skipped: filepath.WalkDir never follows
+// them, so it is enough not to add or descend into one). An error on dir
+// itself (missing, or unreadable) aborts the walk and is the sole error
+// returned; an unreadable subdirectory deeper in the tree adds one error
+// naming it and the walk continues, so files elsewhere in dir are still
+// indexed. A file whose own Info() fails (A3) is dropped from the index the
+// same way: silently if it has simply vanished (fs.ErrNotExist), otherwise
+// with its own error added to errs.
+func (x *Index) addExtraDir(dir string) []error {
+	var errs []error
+	err := filepath.WalkDir(dir, func(path string, d fs.DirEntry, err error) error {
+		if err != nil {
+			if path == dir {
+				return err
+			}
+			errs = append(errs, fmt.Errorf("%s: %w", path, err))
+			return nil
+		}
+		if path == dir && d.Type()&fs.ModeSymlink != 0 {
+			// filepath.WalkDir Lstats its root: a symlinked extra directory
+			// (A4) would otherwise be silently treated as empty rather than
+			// followed, with no sign anything was wrong.
+			errs = append(errs, fmt.Errorf("%s is a symlink; not followed", path))
+			return nil
+		}
+		if d.Type()&fs.ModeSymlink != 0 || d.IsDir() || !d.Type().IsRegular() {
+			return nil
+		}
+		x.addEntry(path, d, &errs)
+		return nil
+	})
+	if err != nil {
+		errs = append(errs, fmt.Errorf("%s: %w", dir, err))
+	}
+	return errs
+}
+
+// addEntry indexes one regular-file entry found while walking an extra
+// directory: A3, a file whose own Info() fails is dropped from the index —
+// silently if it has simply vanished (fs.ErrNotExist), otherwise with its
+// own error appended to errs. Factored out of addExtraDir's WalkDir
+// callback so a test can drive it directly with a fabricated fs.DirEntry,
+// since filepath.WalkDir gives no way to inject a canned Info() failure on
+// a real walk.
+func (x *Index) addEntry(path string, d fs.DirEntry, errs *[]error) {
+	info, err := d.Info()
+	if err != nil {
+		if !errors.Is(err, fs.ErrNotExist) {
+			*errs = append(*errs, fmt.Errorf("%s: %w", path, err))
+		}
+		return
+	}
+	x.add(candidate{path: path, size: info.Size(), modTime: info.ModTime(), name: d.Name(), extra: true})
+}
+
+// Lookup reports whether path (one of the scanned files) duplicates another
+// file, and which file is the original. Safe for concurrent use.
+func (x *Index) Lookup(path string) (original string, dup bool, err error) {
+	idx, ok := x.scanned[path]
+	if !ok {
+		return "", false, fmt.Errorf("dup: %s was not scanned", path)
+	}
+	c := x.candidates[idx]
+	if c.size == 0 {
+		// Empty files are never duplicates, and are never read.
+		return path, false, nil
+	}
+	group := x.bySize[c.size]
+	if len(group) < 2 {
+		// Alone in its size group: not a duplicate, never read.
+		return path, false, nil
+	}
+
+	identical, err := x.identicalTo(idx, group)
+	if err != nil {
+		return "", false, err
+	}
+	if len(identical) < 2 {
+		return path, false, nil
+	}
+	orig := x.candidates[x.original(identical)].path
+	return orig, orig != path, nil
+}
+
+// identicalTo returns the indexes in group (which all share idx's size,
+// idx included) whose content matches candidates[idx]: same partial hash,
+// then, only for those that collide, the same full hash. idx is the file
+// Lookup was asked about; a failure hashing it propagates, since Lookup can
+// answer nothing without it. A failure hashing any other candidate in group
+// only removes that candidate from consideration: a vanished candidate
+// (errors.Is fs.ErrNotExist) is dropped silently, any other failure is
+// recorded on the Index (see recordCandidateError) so the caller can warn
+// about it once matching is done.
+func (x *Index) identicalTo(idx int, group []int) ([]int, error) {
+	idxPartial, err := x.partialHash(x.candidates[idx].path)
+	if err != nil {
+		return nil, err
+	}
+
+	same := []int{idx}
+	var idxFull [sha256.Size]byte
+	haveIdxFull := false
+	for _, j := range group {
+		if j == idx {
+			continue
+		}
+		jPartial, err := x.partialHash(x.candidates[j].path)
+		if err != nil {
+			x.recordCandidateError(x.candidates[j].path, err)
+			continue
+		}
+		if jPartial != idxPartial {
+			continue
+		}
+		if !haveIdxFull {
+			idxFull, err = x.fullHash(x.candidates[idx].path)
+			if err != nil {
+				return nil, err
+			}
+			haveIdxFull = true
+		}
+		jFull, err := x.fullHash(x.candidates[j].path)
+		if err != nil {
+			x.recordCandidateError(x.candidates[j].path, err)
+			continue
+		}
+		if jFull == idxFull {
+			same = append(same, j)
+		}
+	}
+	return same, nil
+}
+
+// recordCandidateError records that path (never the file Lookup was asked
+// about) could not be hashed and so was skipped, unless it simply vanished
+// (fs.ErrNotExist), which is not worth reporting, or was already recorded.
+// Safe for concurrent use.
+func (x *Index) recordCandidateError(path string, err error) {
+	if errors.Is(err, fs.ErrNotExist) {
+		return
+	}
+	x.mu.Lock()
+	defer x.mu.Unlock()
+	if x.candErrSeen == nil {
+		x.candErrSeen = make(map[string]bool)
+	}
+	if x.candErrSeen[path] {
+		return
+	}
+	x.candErrSeen[path] = true
+	x.candErrs = append(x.candErrs, CandidateError{Path: path, Err: err})
+}
+
+// Errors returns every candidate-hashing failure recorded so far,
+// deduplicated by path, in first-recorded order. Safe for concurrent use.
+func (x *Index) Errors() []CandidateError {
+	x.mu.Lock()
+	defer x.mu.Unlock()
+	return append([]CandidateError(nil), x.candErrs...)
+}
+
+// original picks, among a set of identical candidates, the index that is
+// the original. Spec §5.5: one flat comparison, in order — a file under an
+// extra directory beats one that is not; then the oldest by ModTime; then
+// the shortest base name; then the base name that sorts first; then (the
+// final, always-deterministic tie-break) the full path that sorts first.
+// This one chain applies to every pair alike; extra-vs-extra candidates
+// are not a special case broken by path alone.
+func (x *Index) original(idxs []int) int {
+	best := idxs[0]
+	for _, j := range idxs[1:] {
+		if x.preferred(j, best) {
+			best = j
+		}
+	}
+	return best
+}
+
+// preferred reports whether candidate a should be chosen as the original
+// over candidate b.
+func (x *Index) preferred(a, b int) bool {
+	ca, cb := x.candidates[a], x.candidates[b]
+	if ca.extra != cb.extra {
+		return ca.extra
+	}
+	if !ca.modTime.Equal(cb.modTime) {
+		return ca.modTime.Before(cb.modTime)
+	}
+	if len(ca.name) != len(cb.name) {
+		return len(ca.name) < len(cb.name)
+	}
+	if ca.name != cb.name {
+		return ca.name < cb.name
+	}
+	return ca.path < cb.path
+}
+
+// partialHash returns the memoised partial hash for path, computing and
+// storing it on first use. The hash is computed outside the lock; only the
+// memo access is guarded.
+func (x *Index) partialHash(path string) ([sha256.Size]byte, error) {
+	x.mu.Lock()
+	h, ok := x.partial[path]
+	x.mu.Unlock()
+	if ok {
+		return h, nil
+	}
+	h, err := computePartialHash(path)
+	if err != nil {
+		return h, err
+	}
+	x.mu.Lock()
+	x.partial[path] = h
+	x.mu.Unlock()
+	return h, nil
+}
+
+// fullHash returns the memoised full-file hash for path, computing and
+// storing it on first use.
+func (x *Index) fullHash(path string) ([sha256.Size]byte, error) {
+	x.mu.Lock()
+	h, ok := x.full[path]
+	x.mu.Unlock()
+	if ok {
+		return h, nil
+	}
+	h, err := computeFullHash(path)
+	if err != nil {
+		return h, err
+	}
+	x.mu.Lock()
+	x.full[path] = h
+	x.mu.Unlock()
+	return h, nil
+}
+
+// computePartialHash hashes the file's size, its first 64 KiB and its last
+// 64 KiB (the two overlap, or repeat the whole file, when it is smaller
+// than 64 KiB).
+func computePartialHash(path string) ([sha256.Size]byte, error) {
+	f, err := os.Open(path)
+	if err != nil {
+		return [sha256.Size]byte{}, err
+	}
+	defer f.Close()
+	info, err := f.Stat()
+	if err != nil {
+		return [sha256.Size]byte{}, err
+	}
+	size := info.Size()
+
+	h := sha256.New()
+	var sizeBuf [8]byte
+	binary.BigEndian.PutUint64(sizeBuf[:], uint64(size))
+	h.Write(sizeBuf[:])
+
+	head, err := readAt(f, 0)
+	if err != nil {
+		return [sha256.Size]byte{}, err
+	}
+	h.Write(head)
+
+	tailOff := size - partialChunk
+	if tailOff < 0 {
+		tailOff = 0
+	}
+	tail, err := readAt(f, tailOff)
+	if err != nil {
+		return [sha256.Size]byte{}, err
+	}
+	h.Write(tail)
+
+	var out [sha256.Size]byte
+	copy(out[:], h.Sum(nil))
+	return out, nil
+}
+
+// readAt reads up to partialChunk bytes starting at off, without disturbing
+// f's current offset.
+func readAt(f *os.File, off int64) ([]byte, error) {
+	buf := make([]byte, partialChunk)
+	n, err := f.ReadAt(buf, off)
+	if err != nil && err != io.EOF {
+		return nil, err
+	}
+	return buf[:n], nil
+}
+
+// computeFullHash hashes the whole file.
+func computeFullHash(path string) ([sha256.Size]byte, error) {
+	f, err := os.Open(path)
+	if err != nil {
+		return [sha256.Size]byte{}, err
+	}
+	defer f.Close()
+	h := sha256.New()
+	if _, err := io.Copy(h, f); err != nil {
+		return [sha256.Size]byte{}, err
+	}
+	var out [sha256.Size]byte
+	copy(out[:], h.Sum(nil))
+	return out, nil
+}