sfdupes/scan_test.go

package main

import (
	"bytes"
	"context"
	"crypto/sha256"
	"database/sql"
	"encoding/hex"
	"errors"
	"fmt"
	"io"
	"io/fs"
	"os"
	"os/signal"
	"path/filepath"
	"runtime"
	"slices"
	"strconv"
	"strings"
	"syscall"
	"testing"
	"time"

	"golang.org/x/sys/unix"
)

// writeFile creates a file with the given content and returns its path.
func writeFile(t *testing.T, dir, name string, data []byte) string {
	t.Helper()

	p := filepath.Join(dir, name)

	err := os.MkdirAll(filepath.Dir(p), 0o750)
	if err != nil {
		t.Fatal(err)
	}

	err = os.WriteFile(p, data, 0o600)
	if err != nil {
		t.Fatal(err)
	}

	return p
}

// hexSum returns the lowercase-hex SHA-256 of data.
func hexSum(data []byte) string {
	s := sha256.Sum256(data)

	return hex.EncodeToString(s[:])
}

// pattern returns n bytes of deterministic content seeded by tag.
func pattern(tag byte, n int) []byte {
	data := make([]byte, n)
	for i := range data {
		data[i] = tag ^ byte(i)
	}

	return data
}

// sig returns a file's full signature (head, tail, content), failing the
// test on any error.
func sig(t *testing.T, path string, size int64) (string, string, string) {
	t.Helper()

	head, tail, content, err := hashSignature(path, size)
	if err != nil {
		t.Fatalf("hashSignature %s: %v", path, err)
	}

	return head, tail, content
}

// TestHashSignatureBelowThreshold verifies that a file below headTailMin
// is hashed in full and compared directly: head, tail, and content all
// carry the whole-file SHA-256, with no separate end-window step.
func TestHashSignatureBelowThreshold(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()

	cases := []struct {
		name string
		data []byte
	}{
		{"one-byte", []byte("x")},
		{"one-window", pattern(1, headTailWindow)},
		{"several-windows", pattern(2, 3*headTailWindow)},
		{"near-threshold", pattern(3, headTailMin-1)},
	}
	for _, c := range cases {
		t.Run(c.name, func(t *testing.T) {
			t.Parallel()

			p := writeFile(t, dir, c.name, c.data)

			head, tail, content := sig(t, p, int64(len(c.data)))

			whole := hexSum(c.data)
			if head != whole || tail != whole || content != whole {
				t.Errorf("head=%s tail=%s content=%s, want all whole-file %s",
					head, tail, content, whole)
			}
		})
	}
}

// TestHashSignatureEnds exercises the head and tail rungs, which apply
// only to files at least headTailMin. Sparse files keep the fixtures
// cheap: a difference in the first window changes only head, a
// difference in the last window changes only tail, and a difference
// between the windows changes neither end hash but does change the
// whole-file content rung (the file is below wholeFileMax).
// hashSignature leaves the content hash of a file this size to the
// content phase, so that rung is checked through a scan.
func TestHashSignatureEnds(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()

	// Between headTailMin and wholeFileMax: the end-window gate is active
	// and the content rung is a whole-file hash.
	const size = int64(headTailMin + 2*1024*1024)

	base := sparseFile(t, dir, "ends-base", size)
	headDiff := sparseFile(t, dir, "ends-head", size)
	tailDiff := sparseFile(t, dir, "ends-tail", size)
	midDiff := sparseFile(t, dir, "ends-mid", size)

	pokeAt(t, headDiff, 0, []byte{1})
	pokeAt(t, tailDiff, size-1, []byte{1})
	pokeAt(t, midDiff, size/2, []byte{1})

	bHead, bTail, bContent := sig(t, base, size)
	if bContent != "" {
		t.Errorf("content = %q, want none from the hash phase", bContent)
	}

	h, tl, _ := sig(t, headDiff, size)
	if h == bHead {
		t.Error("a byte in the first window did not change head")
	}

	if tl != bTail {
		t.Error("a byte in the first window changed tail")
	}

	h, tl, _ = sig(t, tailDiff, size)
	if tl == bTail {
		t.Error("a byte in the last window did not change tail")
	}

	if h != bHead {
		t.Error("a byte in the last window changed head")
	}

	h, tl, _ = sig(t, midDiff, size)
	if h != bHead || tl != bTail {
		t.Error("a byte between the windows changed an end hash")
	}

	// base and midDiff match on size, head, and tail, so the scan reads
	// both for their content hashes.
	c := scanContents(t, dir, base, midDiff)
	if c[midDiff] == c[base] {
		t.Error("whole-file content rung ignored a byte between the windows")
	}
}

func TestHashSignatureErrors(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()

	// A missing file: an error, and every hash left empty.
	head, tail, content, err := hashSignature(filepath.Join(dir, "missing"), 1)
	if err == nil {
		t.Error("no error for a missing file")
	}

	if head != "" || tail != "" || content != "" {
		t.Errorf("missing file returned hashes: %q %q %q", head, tail, content)
	}

	// A zero-length file has constant hashes and is never opened: even
	// a missing path succeeds.
	head, tail, content, err = hashSignature(filepath.Join(dir, "missing"), 0)
	if err != nil ||
		head != emptyHash || tail != emptyHash || content != emptyHash {
		t.Errorf("empty: head=%q tail=%q content=%q err=%v, "+
			"want constant hashes", head, tail, content, err)
	}

	// A file that shrank between the stat and hash passes: reading at
	// the stat-reported size must fail rather than emit wrong hashes.
	p := writeFile(t, dir, "shrunk", []byte("tiny"))

	head, tail, content, err = hashSignature(p, int64(2*headTailWindow))
	if err == nil {
		t.Error("no error when the stat size exceeds the file size")
	}

	if head != "" || tail != "" || content != "" {
		t.Errorf("shrunk file returned hashes: %q %q %q", head, tail, content)
	}
}

// sparseFile creates a file that is logically size bytes long without
// allocating blocks for the hole, so multi-gigabyte cases stay cheap.
func sparseFile(t *testing.T, dir, name string, size int64) string {
	t.Helper()

	p := filepath.Join(dir, name)

	f, err := os.Create(p) //nolint:gosec // test-controlled path
	if err != nil {
		t.Fatal(err)
	}

	err = f.Truncate(size)
	if err != nil {
		t.Fatal(err)
	}

	err = f.Close()
	if err != nil {
		t.Fatal(err)
	}

	return p
}

// pokeAt writes data into an existing file at off, leaving the rest of
// the file (a sparse hole) untouched.
func pokeAt(t *testing.T, path string, off int64, data []byte) {
	t.Helper()

	f, err := os.OpenFile(path, os.O_WRONLY, 0o600) //nolint:gosec // test path
	if err != nil {
		t.Fatal(err)
	}

	_, err = f.WriteAt(data, off)
	if err != nil {
		t.Fatal(err)
	}

	err = f.Close()
	if err != nil {
		t.Fatal(err)
	}
}

// scanContents scans dir into a fresh database and returns the content
// hash recorded for each file, by path, failing the test if one of want
// has none. A file of headTailMin or more gets a content hash only when
// it is scanned with a file of the same size, head, and tail.
func scanContents(t *testing.T, dir string,
	want ...string,
) map[string]string {
	t.Helper()

	db := openTestDB(t)
	syncTree(t, db, dir)

	contents := make(map[string]string)
	for _, r := range dbRecords(t, db) {
		contents[r.path] = r.content
	}

	for _, p := range want {
		if contents[p] == "" {
			t.Fatalf("%s: no content hash", p)
		}
	}

	return contents
}

// TestContentRungBoundary checks the 50 MiB boundary between the two
// content rungs: just below it the whole file is hashed and any byte
// difference shows; at the boundary only the gigabyte-spaced samples are
// hashed, so a difference outside a sample window is invisible. The
// files of each pair match on size, head, and tail, so the scan reads
// both for their content hashes.
func TestContentRungBoundary(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()

	// A byte that lands outside the single [0, sampleWindow) sample a
	// sub-gigabyte file has, but well inside the file.
	const off = 10 * 1024 * 1024

	// Just under the boundary: the whole-file rung sees the poked byte.
	under := int64(wholeFileMax - 1)
	underBase := sparseFile(t, dir, "under-base", under)
	underPoked := sparseFile(t, dir, "under-poked", under)

	pokeAt(t, underPoked, off, []byte{1})

	// At the boundary: only [0, sampleWindow) is sampled, so the poked
	// byte at off is invisible and the two content hashes match.
	at := int64(wholeFileMax)
	atBase := sparseFile(t, dir, "at-base", at)
	atPoked := sparseFile(t, dir, "at-poked", at)

	pokeAt(t, atPoked, off, []byte{1})

	c := scanContents(t, dir, underBase, underPoked, atBase, atPoked)

	if c[underBase] == c[underPoked] {
		t.Error("whole-file rung ignored a byte difference below wholeFileMax")
	}

	if c[atBase] != c[atPoked] {
		t.Error("sampled rung saw a byte outside every sample window")
	}
}

// TestContentRungMultiGigabyte exercises the sampled rung across several
// gigabytes using sparse files: a difference inside the third sample
// window (at offset 2*sampleStride) changes the hash, while a difference
// in the gap after it does not. The three files match on size, head,
// and tail, so the scan reads each for its content hash.
func TestContentRungMultiGigabyte(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()

	// Three sample windows (offsets 0, 1 GiB, 2 GiB) plus a trailing gap
	// that no sample covers.
	size := int64(2*sampleStride + 2*sampleWindow)
	thirdSample := int64(2 * sampleStride)
	gap := thirdSample + int64(sampleWindow)

	base := sparseFile(t, dir, "g-base", size)
	inSample := sparseFile(t, dir, "g-insample", size)
	inGap := sparseFile(t, dir, "g-ingap", size)

	pokeAt(t, inSample, thirdSample, []byte{1})
	pokeAt(t, inGap, gap, []byte{1})

	c := scanContents(t, dir, base, inSample, inGap)

	if c[inSample] == c[base] {
		t.Error("sample at 2 GiB was not read: difference there was invisible")
	}

	if c[inGap] != c[base] {
		t.Error("a byte in an unsampled gap changed the content hash")
	}
}

// sparseFileWithoutMatch writes name in dir as a sparse file of size
// bytes, next to another file of that size whose first byte differs. A
// scan then reads the file's head and tail, since its size is shared,
// but finds no file matching them, so it gets no content hash.
func sparseFileWithoutMatch(t *testing.T, dir, name string,
	size int64,
) string {
	t.Helper()

	p := sparseFile(t, dir, name, size)
	other := sparseFile(t, dir, name+"-other-head", size)

	pokeAt(t, other, 0, []byte{1})

	return p
}

// TestScanContentGate checks that a file of headTailMin or more is read
// for its content hash only when its size, head, and tail match another
// file's: a same-size pair whose heads differ and one whose tails differ
// get no content hash and are not reported, while an identical pair is
// read and reported.
func TestScanContentGate(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)

	// Three sizes, so that no pair meets another.
	headA := sparseFile(t, dir, "head-a", headTailMin)
	headB := sparseFile(t, dir, "head-b", headTailMin)
	tailA := sparseFile(t, dir, "tail-a", headTailMin+1)
	tailB := sparseFile(t, dir, "tail-b", headTailMin+1)
	same := []string{
		sparseFile(t, dir, "same-a", headTailMin+2),
		sparseFile(t, dir, "same-b", headTailMin+2),
	}

	pokeAt(t, headB, 0, []byte{1})
	pokeAt(t, tailB, headTailMin, []byte{1}) // its last byte

	syncTree(t, db, dir)

	recs := dbRecords(t, db)
	for _, p := range []string{headA, headB, tailA, tailB} {
		r := recordByPath(t, recs, p)
		if r.head == "" || r.tail == "" || r.content != "" {
			t.Errorf("%s: head = %q tail = %q content = %q, "+
				"want head and tail only", p, r.head, r.tail, r.content)
		}
	}

	groups := dupeGroups(t, db)
	if len(groups) != 1 || !slices.Equal(groups[0].paths, same) {
		t.Fatalf("groups = %+v, want only the identical pair %q",
			groups, same)
	}
}

// TestScanContentAcrossOperands checks that a stored file gets its
// content hash when a later scan of a separate operand brings its
// match: tree A's file has a head and tail but no content hash until
// tree B, holding an identical file, is scanned.
func TestScanContentAcrossOperands(t *testing.T) {
	t.Parallel()

	db := openTestDB(t)
	a := sparseFileWithoutMatch(t, t.TempDir(), "a", headTailMin)

	syncTree(t, db, filepath.Dir(a))

	if r := recordByPath(t, dbRecords(t, db), a); r.head == "" || r.content != "" {
		t.Fatalf("after scanning A: %+v, want head and tail only", r)
	}

	b := sparseFile(t, t.TempDir(), "b", headTailMin)

	syncTree(t, db, filepath.Dir(b))

	recs := dbRecords(t, db)
	if r := recordByPath(t, recs, a); r.content == "" {
		t.Fatalf("after scanning B: %+v, want A's file content-hashed", r)
	}

	want := []string{a, b}
	slices.Sort(want)

	groups := dupeGroups(t, db)
	if len(groups) != 1 || !slices.Equal(groups[0].paths, want) {
		t.Fatalf("groups = %+v, want the pair %q", groups, want)
	}
}

// TestScanContentWithinOperand checks that a rescan adding a match next
// to an unchanged stored file gives the stored file its content hash,
// though the hash phase leaves it alone as unchanged.
func TestScanContentWithinOperand(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	stored := sparseFileWithoutMatch(t, dir, "d1", headTailMin)

	syncTree(t, db, dir)

	added := sparseFile(t, dir, "d2", headTailMin)

	st := syncTree(t, db, dir)
	if st != (scanStats{walked: 3, added: 1, unchanged: 2}) {
		t.Fatalf("rescan stats = %+v, want 1 added 2 unchanged", st)
	}

	want := []string{stored, added}

	groups := dupeGroups(t, db)
	if len(groups) != 1 || !slices.Equal(groups[0].paths, want) {
		t.Fatalf("groups = %+v, want the pair %q", groups, want)
	}
}

// TestScanContentStalePartners checks that a stored file outside the
// operand that has vanished, or changed, since it was recorded is not
// read, and that its match inside the operand is not read either: the
// match has no other partner left, so neither gets a content hash and
// no duplicate is reported.
func TestScanContentStalePartners(t *testing.T) {
	t.Parallel()

	db := openTestDB(t)
	dirA := t.TempDir()
	gone := sparseFileWithoutMatch(t, dirA, "gone", headTailMin)
	changed := sparseFileWithoutMatch(t, dirA, "changed", headTailMin+1)

	syncTree(t, db, dirA)

	before := dbRecords(t, db)

	err := os.Remove(gone)
	if err != nil {
		t.Fatal(err)
	}

	future := time.Now().Add(time.Hour)

	err = os.Chtimes(changed, future, future)
	if err != nil {
		t.Fatal(err)
	}

	dirB := t.TempDir()
	sparseFile(t, dirB, "gone-copy", headTailMin)
	sparseFile(t, dirB, "changed-copy", headTailMin+1)

	st := syncTree(t, db, dirB)
	if st != (scanStats{walked: 2, added: 2}) {
		t.Errorf("stats = %+v, want 2 added and nothing skipped", st)
	}

	recs := dbRecords(t, db)
	for _, r := range recs {
		if r.content != "" {
			t.Errorf("%s: content = %q, want none: its only match is stale",
				r.path, r.content)
		}
	}

	for _, old := range before {
		if r := recordByPath(t, recs, old.path); r != old {
			t.Errorf("record = %+v, want it left as %+v", r, old)
		}
	}

	if groups := dupeGroups(t, db); len(groups) != 0 {
		t.Errorf("groups = %+v, want none", groups)
	}
}

// TestScanContentHashedStalePartners checks that stored matches outside
// the operand that already have a content hash are checked like any
// other: once one has vanished and the other has changed, a copy of
// them scanned in another tree has no match left, so it is not read and
// is not reported as their duplicate.
func TestScanContentHashedStalePartners(t *testing.T) {
	t.Parallel()

	db := openTestDB(t)
	dirA := t.TempDir()
	stored := []string{
		sparseFile(t, dirA, "changed", headTailMin),
		sparseFile(t, dirA, "gone", headTailMin),
	}

	// The two stored files match, so this scan gives both a content
	// hash.
	syncTree(t, db, dirA)

	err := os.Remove(stored[1])
	if err != nil {
		t.Fatal(err)
	}

	future := time.Now().Add(time.Hour)

	err = os.Chtimes(stored[0], future, future)
	if err != nil {
		t.Fatal(err)
	}

	b := sparseFile(t, t.TempDir(), "copy", headTailMin)

	st := syncTree(t, db, filepath.Dir(b))
	if st != (scanStats{walked: 1, added: 1}) {
		t.Errorf("stats = %+v, want 1 added and nothing skipped", st)
	}

	recs := dbRecords(t, db)
	if r := recordByPath(t, recs, b); r.content != "" {
		t.Errorf("copy: content = %q, want none: its only matches are stale",
			r.content)
	}

	// The stored records lie outside the operand and are left as they
	// are, so they still group with each other, but not with the copy.
	groups := dupeGroups(t, db)
	if len(groups) != 1 || !slices.Equal(groups[0].paths, stored) {
		t.Errorf("groups = %+v, want only the stored pair %q", groups, stored)
	}
}

// TestScanContentSameSecondRewrite is TestScanContentStalePartners for
// a stored file rewritten in place at the same size with an mtime later
// in the same second than recorded: the file counts as changed, so
// neither it nor its match inside the operand is read.
func TestScanContentSameSecondRewrite(t *testing.T) {
	t.Parallel()

	db := openTestDB(t)
	dirA := t.TempDir()
	changed := sparseFileWithoutMatch(t, dirA, "changed", headTailMin)

	first := time.Date(2026, 1, 2, 3, 4, 5, 100_000_000, time.UTC)

	err := os.Chtimes(changed, first, first)
	if err != nil {
		t.Fatal(err)
	}

	syncTree(t, db, dirA)

	before := dbRecords(t, db)

	// Rewrite one byte in place, keeping the size.
	pokeAt(t, changed, headTailMin/2, []byte{1})

	later := first.Add(500 * time.Millisecond)

	err = os.Chtimes(changed, later, later)
	if err != nil {
		t.Fatal(err)
	}

	dirB := t.TempDir()
	sparseFile(t, dirB, "changed-copy", headTailMin)

	st := syncTree(t, db, dirB)
	if st != (scanStats{walked: 1, added: 1}) {
		t.Errorf("stats = %+v, want 1 added and nothing skipped", st)
	}

	recs := dbRecords(t, db)
	for _, r := range recs {
		if r.content != "" {
			t.Errorf("%s: content = %q, want none: its only match is stale",
				r.path, r.content)
		}
	}

	for _, old := range before {
		if r := recordByPath(t, recs, old.path); r != old {
			t.Errorf("record = %+v, want it left as %+v", r, old)
		}
	}

	if groups := dupeGroups(t, db); len(groups) != 0 {
		t.Errorf("groups = %+v, want none", groups)
	}
}

// TestScanContentReadFailure checks that a failed content read is
// counted as skipped and leaves the record without a content hash, and
// that a later scan tries the read again.
func TestScanContentReadFailure(t *testing.T) {
	t.Parallel()

	db := openTestDB(t)
	a := sparseFileWithoutMatch(t, t.TempDir(), "a", headTailMin)

	syncTree(t, db, filepath.Dir(a))

	// lstat still works on the unreadable file, so it passes the check
	// and fails only when it is read.
	err := os.Chmod(a, 0)
	if err != nil {
		t.Fatal(err)
	}

	dirB := t.TempDir()
	b := sparseFile(t, dirB, "b", headTailMin)

	st := syncTree(t, db, dirB)
	if st != (scanStats{walked: 1, added: 1, skipped: 1}) {
		t.Fatalf("stats = %+v, want 1 added 1 skipped", st)
	}

	if r := recordByPath(t, dbRecords(t, db), a); r.content != "" {
		t.Fatalf("unreadable file: %+v, want no content hash", r)
	}

	err = os.Chmod(a, 0o600)
	if err != nil {
		t.Fatal(err)
	}

	st = syncTree(t, db, dirB)
	if st != (scanStats{walked: 1, unchanged: 1}) {
		t.Fatalf("rescan stats = %+v, want 1 unchanged", st)
	}

	want := []string{a, b}
	slices.Sort(want)

	groups := dupeGroups(t, db)
	if len(groups) != 1 || !slices.Equal(groups[0].paths, want) {
		t.Fatalf("groups = %+v, want the pair %q after the retry",
			groups, want)
	}
}

// TestScanContentCheckError checks that a stored file the content phase
// cannot lstat, for a reason other than its being gone, is counted as
// skipped and does not count as a match.
func TestScanContentCheckError(t *testing.T) {
	t.Parallel()

	db := openTestDB(t)
	sub := filepath.Join(t.TempDir(), "sub")

	err := os.Mkdir(sub, 0o700)
	if err != nil {
		t.Fatal(err)
	}

	sparseFileWithoutMatch(t, sub, "a", headTailMin)
	syncTree(t, db, sub)

	// Without search permission on its directory, the stored file's
	// lstat fails with permission denied.
	err = os.Chmod(sub, 0)
	if err != nil {
		t.Fatal(err)
	}

	t.Cleanup(func() {
		//nolint:gosec // removing the directory needs its search bit back
		_ = os.Chmod(sub, 0o700)
	})

	b := sparseFile(t, t.TempDir(), "b", headTailMin)

	st := syncTree(t, db, filepath.Dir(b))
	if st != (scanStats{walked: 1, added: 1, skipped: 1}) {
		t.Fatalf("stats = %+v, want 1 added 1 skipped", st)
	}

	if r := recordByPath(t, dbRecords(t, db), b); r.content != "" {
		t.Errorf("b: content = %q, want none: its only match could not be "+
			"checked", r.content)
	}
}

// TestScanContentHardlinks checks that the content phase stores the
// content hash of a hard-linked file on every one of its links.
func TestScanContentHardlinks(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	a := sparseFile(t, dir, "a", headTailMin)
	b := filepath.Join(dir, "b")

	err := os.Link(a, b)
	if err != nil {
		t.Fatal(err)
	}

	c := sparseFile(t, dir, "copy", headTailMin)

	st := syncTree(t, db, dir)
	if st != (scanStats{walked: 3, added: 3}) {
		t.Fatalf("stats = %+v, want 3 added", st)
	}

	recs := dbRecords(t, db)

	want := recordByPath(t, recs, c).content
	if want == "" {
		t.Fatal("the copy has no content hash")
	}

	for _, p := range []string{a, b} {
		if got := recordByPath(t, recs, p).content; got != want {
			t.Errorf("%s: content = %q, want %q", p, got, want)
		}
	}
}

// collectWalk runs a walk over roots and returns the emitted records
// and the number of warning events.
func collectWalk(t *testing.T, roots []string, oneFS bool,
	workers int,
) ([]fileRec, int) {
	t.Helper()

	var (
		recs []fileRec
		errs int
	)

	for ev := range startWalk(t.Context(), roots, oneFS, workers) {
		if ev.fail {
			errs++

			continue
		}

		recs = append(recs, ev.rec)
	}

	return recs, errs
}

// walkedPaths returns the sorted paths of the walked records.
func walkedPaths(recs []fileRec) []string {
	paths := make([]string, 0, len(recs))
	for _, r := range recs {
		paths = append(paths, r.path)
	}

	slices.Sort(paths)

	return paths
}

func TestWalk(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	want := []string{
		writeFile(t, dir, "a.txt", []byte("a")),
		writeFile(t, dir, "sub/b.txt", []byte("bb")),
		writeFile(t, dir, "sub/deeper/c.txt", []byte("ccc")),
	}

	slices.Sort(want)

	// Files under a .zfs directory must never be walked.
	writeFile(t, dir, ".zfs/snapshot/hourly/a.txt", []byte("a"))

	// Symlinks are skipped, not followed.
	err := os.Symlink(want[0], filepath.Join(dir, "link"))
	if err != nil {
		t.Fatal(err)
	}

	recs, errs := collectWalk(t, []string{dir}, false, 4)
	if errs != 0 {
		t.Fatalf("errs = %d, want 0", errs)
	}

	if got := walkedPaths(recs); !slices.Equal(got, want) {
		t.Fatalf("paths = %q, want %q", got, want)
	}

	// The walk stats each file as it is discovered: every record must
	// carry the real size and a plausible mtime.
	for _, r := range recs {
		if r.size < 1 || r.size > 3 {
			t.Errorf("%s: size = %d, want 1..3", r.path, r.size)
		}

		if r.mtime.Unix() <= 0 {
			t.Errorf("%s: mtime = %v, want after 1970", r.path, r.mtime)
		}
	}
}

func TestWalkDeepAndWide(t *testing.T) {
	t.Parallel()

	// Exercise the dispatcher with more directories than workers and
	// with nesting deeper than the worker count.
	dir := t.TempDir()
	deep := "deep" + strings.Repeat("/d", 30)

	want := make([]string, 0, 41)
	want = append(want, writeFile(t, dir, deep+"/f", []byte("x")))

	for i := range 40 {
		want = append(want, writeFile(t, dir,
			fmt.Sprintf("wide/%02d/f", i), []byte("y")))
	}

	slices.Sort(want)

	recs, errs := collectWalk(t, []string{dir}, false, 8)
	if errs != 0 {
		t.Fatalf("errs = %d, want 0", errs)
	}

	if got := walkedPaths(recs); !slices.Equal(got, want) {
		t.Fatalf("walked %d paths, want %d", len(got), len(want))
	}
}

func TestWalkMultipleRoots(t *testing.T) {
	t.Parallel()

	rootA := t.TempDir()
	rootB := t.TempDir()
	want := []string{
		writeFile(t, rootA, "a1", []byte("1")),
		writeFile(t, rootA, "sub/a2", []byte("2")),
		writeFile(t, rootB, "b1", []byte("3")),
	}

	slices.Sort(want)

	// Operands are enumerated concurrently by the shared pool; order
	// is unspecified.
	recs, errs := collectWalk(t, []string{rootA, rootB}, false, 4)
	if errs != 0 {
		t.Fatalf("errs = %d, want 0", errs)
	}

	if got := walkedPaths(recs); !slices.Equal(got, want) {
		t.Fatalf("paths = %q, want %q", got, want)
	}
}

func TestWalkFileAndSymlinkOperands(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	f := writeFile(t, dir, "plain", []byte("data"))

	link := filepath.Join(dir, "link")

	err := os.Symlink(f, link)
	if err != nil {
		t.Fatal(err)
	}

	// A regular-file operand is emitted as itself, statted.
	recs, errs := collectWalk(t, []string{f}, false, 2)
	if errs != 0 || len(recs) != 1 || recs[0].path != f || recs[0].size != 4 {
		t.Fatalf("file operand: recs = %+v, errs = %d", recs, errs)
	}

	// A symlink operand that reaches the walk (it became one after
	// walkableRoots checked it) is not followed: it yields a warning and
	// no records.
	recs, errs = collectWalk(t, []string{link}, false, 2)
	if errs != 1 || len(recs) != 0 {
		t.Fatalf("symlink operand: recs = %+v, errs = %d", recs, errs)
	}
}

func TestWalkOneFilesystemSameFS(t *testing.T) {
	t.Parallel()

	// Everything in one filesystem: -x must not skip anything.
	dir := t.TempDir()
	want := []string{
		writeFile(t, dir, "a", []byte("a")),
		writeFile(t, dir, "sub/deep/b", []byte("b")),
	}

	recs, errs := collectWalk(t, []string{dir}, true, 4)
	if errs != 0 {
		t.Fatalf("errs = %d, want 0", errs)
	}

	if got := walkedPaths(recs); !slices.Equal(got, want) {
		t.Fatalf("paths = %q, want %q", got, want)
	}
}

func TestDeviceOfInfo(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()

	fi1, err := os.Lstat(dir)
	if err != nil {
		t.Fatal(err)
	}

	fi2, err := os.Lstat(dir)
	if err != nil {
		t.Fatal(err)
	}

	dev1, ok1 := deviceOfInfo(fi1)

	dev2, ok2 := deviceOfInfo(fi2)
	if !ok1 || !ok2 || dev1 != dev2 {
		t.Fatalf("deviceOfInfo unstable: %d/%v vs %d/%v",
			dev1, ok1, dev2, ok2)
	}
}

// dirEntryFor returns the fs.DirEntry for name within dir, obtained via
// the same os.ReadDir the walk uses, so it carries a real Info().
func dirEntryFor(t *testing.T, dir, name string) fs.DirEntry {
	t.Helper()

	entries, err := os.ReadDir(dir)
	if err != nil {
		t.Fatal(err)
	}

	for _, e := range entries {
		if e.Name() == name {
			return e
		}
	}

	t.Fatalf("entry %q not found in %q", name, dir)

	return nil
}

// callSubdirJob runs subdirJob against e under parent, collecting any
// warning events it emits (subdirJob emits at most one).
func callSubdirJob(t *testing.T, p string, e fs.DirEntry,
	parent dirJob, oneFS bool,
) (dirJob, bool, []walkEvent) {
	t.Helper()

	events := make(chan walkEvent, 1)
	job, ok := subdirJob(t.Context(), p, e, parent, oneFS, events)
	close(events)

	var evs []walkEvent
	for ev := range events {
		evs = append(evs, ev)
	}

	return job, ok, evs
}

// TestSubdirJobOneFilesystem exercises the -x boundary check in
// subdirJob directly, so no second real filesystem is needed. The
// subdirectory's real device is compared against a fabricated operand
// device.
func TestSubdirJobOneFilesystem(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()

	sub := filepath.Join(dir, "sub")

	err := os.Mkdir(sub, 0o750)
	if err != nil {
		t.Fatal(err)
	}

	info, err := os.Lstat(sub)
	if err != nil {
		t.Fatal(err)
	}

	dev, ok := deviceOfInfo(info)
	if !ok {
		t.Skip("platform exposes no device id")
	}

	// A device the subdirectory is not on, standing in for an operand
	// rooted on a different filesystem.
	otherDev := dev + 1
	e := dirEntryFor(t, dir, "sub")

	cases := []struct {
		name   string
		oneFS  bool
		parent dirJob
		wantOK bool
	}{
		// -x on, subdirectory on a different device than its operand:
		// descent is refused.
		{"reject across boundary", true,
			dirJob{rootDev: otherDev, rootDevOK: true}, false},
		// -x on but the operand's own device is unknown: the boundary
		// check is bypassed and descent proceeds.
		{"bypass when root device unknown", true,
			dirJob{rootDev: otherDev, rootDevOK: false}, true},
		// Default (no -x): boundaries are crossed even onto a different
		// device.
		{"cross by default", false,
			dirJob{rootDev: otherDev, rootDevOK: true}, true},
	}

	for _, tc := range cases {
		t.Run(tc.name, func(t *testing.T) {
			t.Parallel()

			job, ok, evs := callSubdirJob(t, sub, e, tc.parent, tc.oneFS)
			if ok != tc.wantOK {
				t.Fatalf("accepted = %v, want %v", ok, tc.wantOK)
			}

			if len(evs) != 0 {
				t.Fatalf("unexpected events: %+v", evs)
			}

			// The accepted job must carry the operand's device down, or -x
			// stops checking below the first level.
			want := dirJob{
				path:      sub,
				rootDev:   tc.parent.rootDev,
				rootDevOK: tc.parent.rootDevOK,
			}
			if ok && job != want {
				t.Fatalf("job = %+v, want %+v", job, want)
			}
		})
	}
}

// errInfoUnavailable is returned by errDirEntry.Info().
var errInfoUnavailable = errors.New("info unavailable")

// errDirEntry is a directory entry whose Info() always fails, driving
// subdirJob's stat-error branch deterministically.
type errDirEntry struct{ name string }

func (e errDirEntry) Name() string { return e.name }
func (errDirEntry) IsDir() bool    { return true }
func (errDirEntry) Type() fs.FileMode {
	return fs.ModeDir
}

func (errDirEntry) Info() (fs.FileInfo, error) {
	return nil, errInfoUnavailable
}

// TestSubdirJobStatError asserts that when a subdirectory's Info()
// fails under -x, subdirJob warns and refuses descent.
func TestSubdirJobStatError(t *testing.T) {
	t.Parallel()

	p := "/does/not/matter/sub"

	_, ok, evs := callSubdirJob(t, p, errDirEntry{name: "sub"},
		dirJob{rootDev: 1, rootDevOK: true}, true)
	if ok {
		t.Fatal("descent accepted after stat error, want refused")
	}

	if len(evs) != 1 || !evs[0].fail || !strings.Contains(evs[0].warn, p) {
		t.Fatalf("want one warning naming the path, got %+v", evs)
	}
}

// buildSmokeTree recreates the README smoke-test filesystem layout
// with deterministic content and returns the tree root.
func buildSmokeTree(t *testing.T) string {
	t.Helper()

	dir := t.TempDir()
	one := pattern(10, 2000)
	f1 := pattern(30, 3000)
	f2 := pattern(40, 100)

	writeFile(t, dir, "a/one.bin", one)
	writeFile(t, dir, "b/copy.bin", one)
	writeFile(t, dir, "b/copy2.bin", one)
	// Same size as one.bin, different content.
	writeFile(t, dir, "a/unique.bin", pattern(20, 2000))
	writeFile(t, dir, "tiny1", []byte("x"))
	writeFile(t, dir, "tiny2", []byte("x"))
	writeFile(t, dir, "tiny3", []byte("y"))
	writeFile(t, dir, "empty1", nil)
	writeFile(t, dir, "empty2", nil)
	writeFile(t, dir, "t1/f1", f1)
	writeFile(t, dir, "t1/sub/f2", f2)
	writeFile(t, dir, "t2/f1", f1)
	writeFile(t, dir, "t2/sub/f2", f2)
	writeFile(t, dir, "t3/f1", f1)
	writeFile(t, dir, "t3/sub/f2renamed", f2)

	return dir
}

// smokeTreeFiles is the number of regular files buildSmokeTree creates.
const smokeTreeFiles = 15

// syncTree synchronizes the database with the given roots and returns
// the scan stats.
func syncTree(t *testing.T, db *sql.DB, roots ...string) scanStats {
	t.Helper()

	st, err := syncScan(t.Context(), db, roots, 4, false)
	if err != nil {
		t.Fatalf("syncScan: %v", err)
	}

	return st
}

// dbRecords returns every record currently in the database, in path
// order.
func dbRecords(t *testing.T, db *sql.DB) []scanRec {
	t.Helper()

	var recs []scanRec

	err := loadFileRows(t.Context(), db, func(r scanRec) {
		recs = append(recs, r)
	})
	if err != nil {
		t.Fatal(err)
	}

	return recs
}

// recordByPath finds the record with the given path.
func recordByPath(t *testing.T, recs []scanRec, path string) scanRec {
	t.Helper()

	for _, r := range recs {
		if r.path == path {
			return r
		}
	}

	t.Fatalf("no record for %q", path)

	return scanRec{}
}

// recordPaths returns the sorted paths of recs.
func recordPaths(recs []scanRec) []string {
	paths := make([]string, 0, len(recs))
	for _, r := range recs {
		paths = append(paths, r.path)
	}

	slices.Sort(paths)

	return paths
}

// assertSmokeDupeGroups checks the file-level duplicate groups for the
// smoke tree rooted at dir.
func assertSmokeDupeGroups(t *testing.T, dir string, db *sql.DB) {
	t.Helper()

	groups := dupeGroups(t, db)
	if len(groups) != 5 {
		t.Fatalf("len(groups) = %d, want 5", len(groups))
	}

	wantSizes := []int64{3000, 2000, 100, 1, 0}
	for i, g := range groups {
		if g.size != wantSizes[i] {
			t.Errorf("groups[%d].size = %d, want %d",
				i, g.size, wantSizes[i])
		}
	}

	wantF1 := []string{
		filepath.Join(dir, "t1/f1"),
		filepath.Join(dir, "t2/f1"),
		filepath.Join(dir, "t3/f1"),
	}
	if !slices.Equal(groups[0].paths, wantF1) {
		t.Errorf("groups[0].paths = %q, want %q", groups[0].paths, wantF1)
	}
}

// assertSmokeTreeGroups checks the duplicate-tree groups for the smoke
// tree rooted at dir.
func assertSmokeTreeGroups(t *testing.T, dir string, db *sql.DB) {
	t.Helper()

	super, dirs := dbTree(t, db)

	tg := collectTreeGroups(dirs, super)
	if len(tg) != 1 {
		t.Fatalf("len(tree groups) = %d, want 1", len(tg))
	}

	wantTrees := []string{filepath.Join(dir, "t1"), filepath.Join(dir, "t2")}
	if got := groupPaths(tg)[0]; !slices.Equal(got, wantTrees) {
		t.Fatalf("tree group = %q, want %q", got, wantTrees)
	}

	if tg[0][0].fileCount != 2 || tg[0][0].totalSize != 3100 {
		t.Fatalf("tree totals: %d files %d bytes, want 2 3100",
			tg[0][0].fileCount, tg[0][0].totalSize)
	}
}

func TestScanPipeline(t *testing.T) {
	t.Parallel()

	dir := buildSmokeTree(t)
	db := openTestDB(t)

	st := syncTree(t, db, dir)
	if st != (scanStats{walked: smokeTreeFiles, added: smokeTreeFiles}) {
		t.Fatalf("stats = %+v, want %d added only", st, smokeTreeFiles)
	}

	parsed := dbRecords(t, db)
	if len(parsed) != smokeTreeFiles {
		t.Fatalf("len(records) = %d, want %d", len(parsed), smokeTreeFiles)
	}

	assertSmokeDupeGroups(t, dir, db)
	assertSmokeTreeGroups(t, dir, db)
}

func TestSyncScanUnchangedReuse(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	a := writeFile(t, dir, "a.bin", pattern(1, 500))

	writeFile(t, dir, "b.bin", pattern(2, 600))

	st := syncTree(t, db, dir)
	if st != (scanStats{walked: 2, added: 2}) {
		t.Fatalf("first scan stats = %+v, want 2 added", st)
	}

	// An immediate rescan reuses every record without reading file
	// contents. Prove the files are not re-read by corrupting a stored
	// hash and observing that it survives the rescan.
	_, err := db.ExecContext(context.Background(),
		"UPDATE files SET head = 'sentinel' WHERE path = ?", []byte(a))
	if err != nil {
		t.Fatal(err)
	}

	st = syncTree(t, db, dir)
	if st != (scanStats{walked: 2, unchanged: 2}) {
		t.Fatalf("rescan stats = %+v, want 2 unchanged", st)
	}

	if r := recordByPath(t, dbRecords(t, db), a); r.head != "sentinel" {
		t.Fatalf("head = %q, want sentinel (file must not be re-read)",
			r.head)
	}
}

func TestSyncScanMtimeBump(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	a := writeFile(t, dir, "a.bin", pattern(1, 500))

	syncTree(t, db, dir)

	// Bump the mtime forward: the file must be re-hashed even though
	// its size is unchanged.
	future := time.Now().Add(time.Hour)

	err := os.Chtimes(a, future, future)
	if err != nil {
		t.Fatal(err)
	}

	st := syncTree(t, db, dir)
	if st != (scanStats{walked: 1, updated: 1}) {
		t.Fatalf("mtime-bump stats = %+v, want 1 updated", st)
	}

	if r := recordByPath(t, dbRecords(t, db), a); !r.mtime.Equal(future) {
		t.Fatalf("mtime = %v, want %v", r.mtime, future)
	}
}

// assertWholeFileHashed fails unless the record for path holds the
// whole-file hash of data as its head, tail, and content.
func assertWholeFileHashed(t *testing.T, db *sql.DB, path string,
	data []byte,
) {
	t.Helper()

	r := recordByPath(t, dbRecords(t, db), path)
	if want := hexSum(data); r.head != want || r.tail != want ||
		r.content != want {
		t.Fatalf("head, tail, content = %q, %q, %q, want %q for each",
			r.head, r.tail, r.content, want)
	}
}

// TestSyncScanSameSecondRewrite rewrites a file in place at the same
// size with an mtime later in the same second as the recorded one: the
// next scan must notice the change and re-hash the file.
func TestSyncScanSameSecondRewrite(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	a := writeFile(t, dir, "a.bin", pattern(1, 500))

	// b.bin shares the size of a.bin, so a.bin is hashed.
	writeFile(t, dir, "b.bin", pattern(2, 500))

	first := time.Date(2026, 1, 2, 3, 4, 5, 100_000_000, time.UTC)

	err := os.Chtimes(a, first, first)
	if err != nil {
		t.Fatal(err)
	}

	syncTree(t, db, dir)

	rewritten := pattern(3, 500)
	writeFile(t, dir, "a.bin", rewritten)

	later := first.Add(500 * time.Millisecond)

	err = os.Chtimes(a, later, later)
	if err != nil {
		t.Fatal(err)
	}

	st := syncTree(t, db, dir)
	if st != (scanStats{walked: 2, updated: 1, unchanged: 1}) {
		t.Fatalf("rescan stats = %+v, want 1 updated 1 unchanged", st)
	}

	assertWholeFileHashed(t, db, a, rewritten)
}

// TestSyncScanOperandSameSecondRewrite is TestSyncScanSameSecondRewrite
// for files given to scan as operands, which scan stats without reading
// their directory.
func TestSyncScanOperandSameSecondRewrite(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	a := writeFile(t, dir, "a.bin", pattern(1, 500))

	// b.bin shares the size of a.bin, so a.bin is hashed.
	b := writeFile(t, dir, "b.bin", pattern(2, 500))

	first := time.Date(2026, 1, 2, 3, 4, 5, 100_000_000, time.UTC)

	err := os.Chtimes(a, first, first)
	if err != nil {
		t.Fatal(err)
	}

	syncTree(t, db, a, b)

	rewritten := pattern(3, 500)
	writeFile(t, dir, "a.bin", rewritten)

	later := first.Add(500 * time.Millisecond)

	err = os.Chtimes(a, later, later)
	if err != nil {
		t.Fatal(err)
	}

	st := syncTree(t, db, a, b)
	if st != (scanStats{walked: 2, updated: 1, unchanged: 1}) {
		t.Fatalf("rescan stats = %+v, want 1 updated 1 unchanged", st)
	}

	assertWholeFileHashed(t, db, a, rewritten)
}

// TestSyncScanRewriteAfter2262 runs assertLateRewriteRehashed with an
// mtime after 2262, a time too late to count in nanoseconds in an int64.
func TestSyncScanRewriteAfter2262(t *testing.T) {
	t.Parallel()

	assertLateRewriteRehashed(t, time.Date(2300, 1, 2, 3, 4, 5, 0, time.UTC))
}

// TestSyncScanRewritePastTimeLimit runs assertLateRewriteRehashed with an
// mtime one second past the latest a time.Time holds without wrapping it
// to a time far in the past.
func TestSyncScanRewritePastTimeLimit(t *testing.T) {
	t.Parallel()

	assertLateRewriteRehashed(t, time.Unix(9223371974719179008, 0))
}

// assertLateRewriteRehashed scans a directory, rewrites a file in it in
// place at the same size, sets its mtime to late, and fails unless the
// next scan re-hashes the file. It skips where late does not fit the
// platform's timespec or the filesystem does not store it.
func assertLateRewriteRehashed(t *testing.T, late time.Time) {
	t.Helper()

	dir := t.TempDir()
	db := openTestDB(t)
	a := writeFile(t, dir, "a.bin", pattern(1, 500))

	// b.bin shares the size of a.bin, so a.bin is hashed.
	writeFile(t, dir, "b.bin", pattern(2, 500))

	syncTree(t, db, dir)

	rewritten := pattern(3, 500)
	writeFile(t, dir, "a.bin", rewritten)

	// os.Chtimes cannot set such a time: it converts through UnixNano.
	ts, err := unix.TimeToTimespec(late)
	if err != nil {
		t.Skipf("an mtime %d seconds after 1970 does not fit this platform's "+
			"timespec: %v", late.Unix(), err)
	}

	err = unix.UtimesNano(a, []unix.Timespec{ts, ts})
	if err != nil {
		t.Fatal(err)
	}

	fi, err := os.Lstat(a)
	if err != nil {
		t.Fatal(err)
	}

	if fi.ModTime().Unix() != late.Unix() {
		t.Skipf("the filesystem stored the mtime as %d seconds after 1970, "+
			"not %d", fi.ModTime().Unix(), late.Unix())
	}

	st := syncTree(t, db, dir)
	if st != (scanStats{walked: 2, updated: 1, unchanged: 1}) {
		t.Fatalf("rescan stats = %+v, want 1 updated 1 unchanged", st)
	}

	assertWholeFileHashed(t, db, a, rewritten)
}

func TestSyncScanAddRemove(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	a := writeFile(t, dir, "a.bin", pattern(1, 500))

	writeFile(t, dir, "b.bin", pattern(2, 600))
	syncTree(t, db, dir)

	// Add one file, remove another.
	c := writeFile(t, dir, "c.bin", pattern(3, 700))

	err := os.Remove(a)
	if err != nil {
		t.Fatal(err)
	}

	st := syncTree(t, db, dir)
	if st != (scanStats{walked: 2, added: 1, removed: 1, unchanged: 1}) {
		t.Fatalf("add/remove stats = %+v, want 1 added 1 removed 1 unchanged",
			st)
	}

	want := []string{filepath.Join(dir, "b.bin"), c}
	if got := recordPaths(dbRecords(t, db)); !slices.Equal(got, want) {
		t.Fatalf("paths = %q, want %q", got, want)
	}
}

func TestSyncScanSizeChange(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	p := writeFile(t, dir, "f", pattern(1, 100))

	syncTree(t, db, dir)

	// Rewrite with a different size but force the mtime back to the
	// recorded value: the size mismatch alone must trigger a re-hash.
	old := recordByPath(t, dbRecords(t, db), p)

	writeFile(t, dir, "f", pattern(1, 200))

	err := os.Chtimes(p, old.mtime, old.mtime)
	if err != nil {
		t.Fatal(err)
	}

	st := syncTree(t, db, dir)
	if st.updated != 1 {
		t.Fatalf("stats = %+v, want 1 updated", st)
	}

	if got := recordByPath(t, dbRecords(t, db), p); got.size != 200 {
		t.Fatalf("size = %d, want 200", got.size)
	}
}

func TestSyncScanScope(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)

	writeFile(t, dir, "a/keep", pattern(1, 10))

	gone := writeFile(t, dir, "b/gone", pattern(2, 10))

	syncTree(t, db, dir)

	// Deleting a file outside the rescanned root must not remove its
	// record: records outside the scanned operands are untouched.
	err := os.Remove(gone)
	if err != nil {
		t.Fatal(err)
	}

	st := syncTree(t, db, filepath.Join(dir, "a"))
	if st.removed != 0 || st.unchanged != 1 {
		t.Fatalf("subtree stats = %+v, want 0 removed 1 unchanged", st)
	}

	if got := recordPaths(dbRecords(t, db)); len(got) != 2 {
		t.Fatalf("records = %q, want both retained", got)
	}

	// Rescanning the parent now removes the vanished file's record.
	st = syncTree(t, db, dir)
	if st.removed != 1 {
		t.Fatalf("parent stats = %+v, want 1 removed", st)
	}
}

func TestSyncScanRemovesNonRegular(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	p := writeFile(t, dir, "f", pattern(1, 10))
	keep := writeFile(t, dir, "g", pattern(2, 10))

	syncTree(t, db, dir)

	// Replace the file with a symlink: it is no longer walked, so its
	// record must be deleted.
	err := os.Remove(p)
	if err != nil {
		t.Fatal(err)
	}

	err = os.Symlink(keep, p)
	if err != nil {
		t.Fatal(err)
	}

	st := syncTree(t, db, dir)
	if st.removed != 1 || st.unchanged != 1 {
		t.Fatalf("stats = %+v, want 1 removed 1 unchanged", st)
	}
}

func TestSyncScanOverlappingRoots(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)

	writeFile(t, dir, "sub/f", pattern(1, 10))

	// A file reachable via two overlapping operands is deduplicated
	// by path in the shared walk and processed once.
	st := syncTree(t, db, dir, filepath.Join(dir, "sub"))
	if st != (scanStats{walked: 1, added: 1}) {
		t.Fatalf("stats = %+v, want 1 added", st)
	}

	if got := recordPaths(dbRecords(t, db)); len(got) != 1 {
		t.Fatalf("records = %q, want exactly one", got)
	}
}

func TestScanSkipsUniqueSizes(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	a := writeFile(t, dir, "a.bin", pattern(1, 500))

	writeFile(t, dir, "b.bin", pattern(2, 600))

	// Neither size is shared, so neither file is read: both records
	// are written without hashes and no duplicates are reported.
	st := syncTree(t, db, dir)
	if st != (scanStats{walked: 2, added: 2}) {
		t.Fatalf("stats = %+v, want 2 added", st)
	}

	recs := dbRecords(t, db)
	for _, r := range recs {
		if r.head != "" || r.tail != "" || r.content != "" {
			t.Errorf("%s: head = %q tail = %q content = %q, want unhashed",
				r.path, r.head, r.tail, r.content)
		}
	}

	if groups := dupeGroups(t, db); len(groups) != 0 {
		t.Fatalf("groups = %+v, want none from unhashed records", groups)
	}

	// A new same-size file makes 500 a shared size: the next scan
	// hashes both the new file and the previously unhashed unchanged
	// one, and they group as duplicates.
	c := writeFile(t, dir, "c.bin", pattern(1, 500))

	st = syncTree(t, db, dir)
	if st != (scanStats{walked: 3, added: 1, updated: 1, unchanged: 1}) {
		t.Fatalf("rescan stats = %+v, want 1 added 1 updated 1 unchanged",
			st)
	}

	groups := dupeGroups(t, db)
	if len(groups) != 1 {
		t.Fatalf("groups = %+v, want the a/c pair", groups)
	}

	if want := []string{a, c}; !slices.Equal(groups[0].paths, want) {
		t.Fatalf("group paths = %q, want %q", groups[0].paths, want)
	}
}

func TestTreesUnhashedNeverEqual(t *testing.T) {
	t.Parallel()

	// Two trees identical except for same-name, same-size files without
	// a content hash must not compare equal: their content is unknown.
	// That holds for unhashed files (possible when the trees were
	// scanned separately) and for files of headTailMin or more that
	// have only a head and tail.
	sum := hexSum(pattern(1, 100))
	shared := []scanRec{
		{path: "/x/t1/f1", size: 100, head: sum, tail: sum, content: sum},
		{path: "/x/t2/f1", size: 100, head: sum, tail: sum, content: sum},
	}

	cases := map[string][]scanRec{
		"unhashed": {
			{path: "/x/t1/u", size: 50},
			{path: "/x/t2/u", size: 50},
		},
		"head and tail only": {
			{path: "/x/t1/u", size: headTailMin, head: "h", tail: "t"},
			{path: "/x/t2/u", size: headTailMin, head: "h", tail: "t"},
		},
	}

	for name, unknown := range cases {
		super, dirs := treeOf(t, append(slices.Clone(shared), unknown...))

		if tg := collectTreeGroups(dirs, super); len(tg) != 0 {
			t.Errorf("%s: tree groups = %d, want 0 (the files may differ)",
				name, len(tg))
		}
	}
}

func TestScanHardlinksReadOnce(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	a := writeFile(t, dir, "a.bin", pattern(1, 300))
	b := filepath.Join(dir, "b.bin")

	err := os.Link(a, b)
	if err != nil {
		t.Fatal(err)
	}

	st := syncTree(t, db, dir)
	if st != (scanStats{walked: 2, added: 2}) {
		t.Fatalf("stats = %+v, want 2 added", st)
	}

	// Both paths share the single read's hashes and group together.
	recs := dbRecords(t, db)

	ra := recordByPath(t, recs, a)
	rb := recordByPath(t, recs, b)

	if ra.head == "" || ra.head != rb.head || ra.tail != rb.tail {
		t.Fatalf("hardlink hashes differ: %+v vs %+v", ra, rb)
	}

	if groups := dupeGroups(t, db); len(groups) != 1 {
		t.Fatalf("groups = %+v, want the hardlink pair", groups)
	}
}

func TestScanHardlinkRunFailsTogether(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	a := writeFile(t, dir, "a.bin", pattern(1, 300))

	err := os.Link(a, filepath.Join(dir, "b.bin"))
	if err != nil {
		t.Fatal(err)
	}

	// Unreadable inode: the run's single read fails, so both paths are
	// skipped — proof that hard links are read once, not per path.
	err = os.Chmod(a, 0)
	if err != nil {
		t.Fatal(err)
	}

	st := syncTree(t, db, dir)
	if st.skipped != 2 || st.added != 0 {
		t.Fatalf("stats = %+v, want both hardlink paths skipped", st)
	}
}

// injectedWriteFailure is the message the injected database trigger
// aborts with, so the test can recognize its own failure in the error
// the scan reports.
const injectedWriteFailure = "injected write failure"

// hashLeakFiles is the size of the fixture for the hash-phase failure
// test. The batch commit inside the hash phase is what fails, so the
// tree must hold more than updateBatchSize files for the failure to
// happen at all, and the surplus over that is what is still queued
// when it does. That surplus is 2*workQueueDepth, which jobs, results
// and the workers in flight between them absorb exactly, so the feeder
// itself drains and exits; what an abandoned pool leaves parked is
// every worker, each holding a result nobody will ever receive, plus
// the goroutine waiting on them. That is what this test detects, and
// its margin over detecting nothing at all is the worker count —
// worth knowing before changing hashLeakWorkers or workQueueDepth.
const hashLeakFiles = updateBatchSize + 2*workQueueDepth

// hashLeakWorkers is the worker count for that scan: a fixed, modest
// number keeps the leak deterministic on any machine.
const hashLeakWorkers = 4

// goroutineSettle bounds how long a goroutine count is given to come
// back down to its target. Only a failing run ever waits this long.
const goroutineSettle = 5 * time.Second

// goroutinePoll is the interval between goroutine-count samples.
const goroutinePoll = 10 * time.Millisecond

// writeEmptyFiles creates n empty files directly in dir. Zero-length
// files are never opened by the hasher — their hashes are constant —
// so a fixture this size costs directory entries and no read I/O,
// while still queueing n runs through the hash pool.
func writeEmptyFiles(t *testing.T, dir string, n int) {
	t.Helper()

	for i := range n {
		err := os.WriteFile(
			filepath.Join(dir, strconv.Itoa(i)), nil, 0o600)
		if err != nil {
			t.Fatal(err)
		}
	}
}

// injectWriteFailure creates a scan database at path carrying the real
// schema plus a trigger that aborts every insert. Reads are untouched,
// so a scan loads its index and walks normally and then fails on the
// first record it tries to commit — a genuine database write failure
// partway through the hash phase.
func injectWriteFailure(t *testing.T, path string) {
	t.Helper()

	db, err := openScanDatabase(t.Context(), path)
	if err != nil {
		t.Fatal(err)
	}

	_, err = db.ExecContext(t.Context(),
		"CREATE TRIGGER refuse_insert BEFORE INSERT ON files "+
			"BEGIN SELECT RAISE(ABORT, '"+injectedWriteFailure+"'); END")
	if err != nil {
		t.Fatal(err)
	}

	err = db.Close()
	if err != nil {
		t.Fatal(err)
	}
}

// baselineGoroutines waits for the goroutine count to stop moving and
// returns it. Handles closed by earlier tests take a moment to reap
// their driver goroutines, so a single sample would make the baseline
// itself flaky.
func baselineGoroutines(t *testing.T) int {
	t.Helper()

	// The first scan command in a process starts os/signal's goroutine,
	// which never exits. Start it now, so the baseline counts it
	// instead of the scan seeming to leave it behind.
	ch := make(chan os.Signal, 1)
	signal.Notify(ch, syscall.SIGINT)
	signal.Stop(ch)

	deadline := time.Now().Add(goroutineSettle)
	last := runtime.NumGoroutine()

	for time.Now().Before(deadline) {
		time.Sleep(goroutinePoll)

		n := runtime.NumGoroutine()
		if n == last {
			return n
		}

		last = n
	}

	return last
}

// settledGoroutines polls runtime.NumGoroutine until it is back at or
// below want and returns the last count seen. Polling, rather than one
// sample after a fixed sleep, is what keeps this from being a race
// between the assertion and goroutines that are already exiting.
func settledGoroutines(t *testing.T, want int) int {
	t.Helper()

	deadline := time.Now().Add(goroutineSettle)

	for {
		n := runtime.NumGoroutine()
		if n <= want || time.Now().After(deadline) {
			return n
		}

		time.Sleep(goroutinePoll)
	}
}

// TestScanHashWriteFailureUnwindsPool drives the scan entry point
// against a database that refuses every write. The hash phase gives up
// partway through with thousands of runs still queued, which used to
// leave the feeder parked on a full job channel and every worker parked
// on a full result channel for the life of the process.
func TestScanHashWriteFailureUnwindsPool(t *testing.T) {
	path := testDBPath(t)
	t.Setenv(databaseEnv, path)

	dir := t.TempDir()

	writeEmptyFiles(t, dir, hashLeakFiles)
	injectWriteFailure(t, path)

	base := baselineGoroutines(t)

	var stderr bytes.Buffer

	code := run([]string{
		cmdScan, "--workers", strconv.Itoa(hashLeakWorkers), dir,
	}, io.Discard, &stderr)
	if code != exitFatal {
		t.Fatalf("run(scan) = %d, want %d; stderr: %s",
			code, exitFatal, stderr.String())
	}

	if !strings.Contains(stderr.String(), injectedWriteFailure) {
		t.Errorf("stderr = %q, want the injected write failure",
			stderr.String())
	}

	if got := settledGoroutines(t, base); got > base {
		t.Errorf("goroutines = %d after the failed scan, want %d back",
			got, base)
	}
}

func TestHashRuns(t *testing.T) {
	t.Parallel()

	rec := func(path string, dev, ino uint64) fileRec {
		return fileRec{path: path, dev: dev, ino: ino}
	}

	runs := hashRuns([]fileRec{
		rec("/c", 1, 7),
		rec("/a", 1, 7),
		rec("/b", 1, 9),
		// No inode identity: never merged, even with matching zeros.
		rec("/z1", 0, 0),
		rec("/z2", 0, 0),
	})

	got := make([][]string, 0, len(runs))
	for _, run := range runs {
		paths := make([]string, 0, len(run))
		for _, r := range run {
			paths = append(paths, r.path)
		}

		got = append(got, paths)
	}

	want := [][]string{{"/z1"}, {"/z2"}, {"/a", "/c"}, {"/b"}}
	if !slices.EqualFunc(got, want, slices.Equal) {
		t.Fatalf("runs = %v, want %v", got, want)
	}
}

func TestPruneRoots(t *testing.T) {
	t.Parallel()

	// Duplicates and operands under other operands are dropped; /cc is
	// not under /c (sibling with a shared prefix).
	got := pruneRoots([]string{"/a/b", "/a", "/c", "/a", "/a/b/c", "/cc"})

	want := []string{"/a", "/c", "/cc"}
	if !slices.Equal(got, want) {
		t.Fatalf("pruneRoots = %q, want %q", got, want)
	}
}

func TestReportsNeverTouchFilesystem(t *testing.T) {
	t.Parallel()

	dir := buildSmokeTree(t)
	db := openTestDB(t)

	syncTree(t, db, dir)

	// Remove the scanned tree entirely; the analysis must be
	// unaffected because it reads the database alone.
	err := os.RemoveAll(dir)
	if err != nil {
		t.Fatal(err)
	}

	assertSmokeDupeGroups(t, dir, db)
	assertSmokeTreeGroups(t, dir, db)
}

func TestUnderRoot(t *testing.T) {
	t.Parallel()

	const abRoot = "/a/b"

	cases := []struct {
		path string
		root string
		want bool
	}{
		{"/a/b/c", abRoot, true},
		{abRoot, abRoot, true},
		{"/a/bc", abRoot, false},
		{"/a", abRoot, false},
		{"/x/y", "/", true},
		{"/", "/", true},
	}
	for _, c := range cases {
		if got := underRoot(c.path, c.root); got != c.want {
			t.Errorf("underRoot(%q, %q) = %v, want %v",
				c.path, c.root, got, c.want)
		}
	}
}