path: root/internal/dup/dup.go

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

// SameContent reports whether a and b hold identical content: a stat and
// size check first, then the same partial/full hash comparison Lookup uses
// for scanned candidates. Neither file needs to have been scanned or
// indexed; this is the one place content identity is decided, so callers
// outside this package must not hash a second way.
func SameContent(a, b string) (bool, error) {
	ai, err := os.Stat(a)
	if err != nil {
		return false, err
	}
	bi, err := os.Stat(b)
	if err != nil {
		return false, err
	}
	if ai.Size() != bi.Size() {
		return false, nil
	}

	aPartial, err := computePartialHash(a)
	if err != nil {
		return false, err
	}
	bPartial, err := computePartialHash(b)
	if err != nil {
		return false, err
	}
	if aPartial != bPartial {
		return false, nil
	}

	aFull, err := computeFullHash(a)
	if err != nil {
		return false, err
	}
	bFull, err := computeFullHash(b)
	if err != nil {
		return false, err
	}
	return aFull == bFull, 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
}