sfdupes/scan_test.go

package main

import (
	"bytes"
	"context"
	"crypto/sha256"
	"database/sql"
	"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
}

// 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) (
	[sha256.Size]byte, [sha256.Size]byte, [sha256.Size]byte,
) {
	t.Helper()

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

	return head, tail, content
}

// TestHashSignature checks the three hashes of a file under
// wholeFileMax: head and tail are the SHA-256 of its first and last
// headTailWindow bytes, and content that of the whole file. In a file
// no larger than headTailWindow each window is the whole file, so all
// three are the whole-file hash.
func TestHashSignature(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+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)))

			window := min(len(c.data), headTailWindow)
			wantHead := sha256.Sum256(c.data[:window])
			wantTail := sha256.Sum256(c.data[len(c.data)-window:])
			wantContent := sha256.Sum256(c.data)

			if head != wantHead || tail != wantTail || content != wantContent {
				t.Errorf("head=%x tail=%x content=%x, want %x %x %x",
					head, tail, content, wantHead, wantTail, wantContent)
			}
		})
	}
}

// TestHashSignatureEnds checks which hashes a one-byte difference
// changes in a file under wholeFileMax. Sparse files keep the fixtures
// cheap: a difference in the first window changes head but not tail,
// one in the last window changes tail but not head, and one between the
// windows changes neither but does change the whole-file content hash.
func TestHashSignatureEnds(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()

	// Room for a byte between the two windows.
	const size = int64(4 * headTailWindow)

	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)

	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, c := sig(t, midDiff, size)
	if h != bHead || tl != bTail {
		t.Error("a byte between the windows changed an end hash")
	}

	if c == bContent {
		t.Error("the whole-file content hash ignored a byte between the " +
			"windows")
	}
}

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

	dir := t.TempDir()

	var zero [sha256.Size]byte

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

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

	// A zero-length file has constant hashes and is never opened: even
	// a missing path succeeds.
	empty := sha256.Sum256(nil)

	head, tail, content, err = hashSignature(filepath.Join(dir, "missing"), 0)
	if err != nil || head != empty || tail != empty || content != empty {
		t.Errorf("empty: head=%x tail=%x content=%x 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 != zero || tail != zero || content != zero {
		t.Errorf("shrunk file returned hashes: %x %x %x", 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)
	}
}

// TestContentHashBoundary checks the 100 MiB boundary between the two
// content hashes through a scan and report. The files of each pair
// differ in one byte that neither end window nor any sample covers.
// Just below the boundary the whole file is hashed, so that pair is not
// reported. At the boundary only the samples are hashed, so that pair
// is reported as duplicates.
func TestContentHashBoundary(t *testing.T) {
	t.Parallel()

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

	// A byte that lands outside the single [0, sampleWindow) sample a
	// sub-gigabyte file has, and outside both end windows.
	const off = 10 * 1024 * 1024

	under := sparseFile(t, dir, "under-a", wholeFileMax-1)
	underPoked := sparseFile(t, dir, "under-b", wholeFileMax-1)
	at := sparseFile(t, dir, "at-a", wholeFileMax)
	atPoked := sparseFile(t, dir, "at-b", wholeFileMax)

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

	syncTree(t, db, dir)

	want := []string{at, atPoked}

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

// TestContentHashMultiGigabyte exercises the sampled content hash
// 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.
func TestContentHashMultiGigabyte(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})

	_, _, cBase := sig(t, base, size)
	_, _, cInSample := sig(t, inSample, size)
	_, _, cInGap := sig(t, inGap, size)

	if cInSample == cBase {
		t.Error("sample at 2 GiB was not read: difference there was invisible")
	}

	if cInGap != cBase {
		t.Error("a byte in an unsampled gap changed the content hash")
	}
}

// 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, walkRules{},
		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
// 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, walkRules{},
		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)
			}

			// A refused descent names the directory, so the scan keeps
			// the records below it.
			var wantEvs []walkEvent
			if !ok {
				wantEvs = []walkEvent{{otherFSDir: sub}}
			}

			if !slices.Equal(evs, wantEvs) {
				t.Fatalf("events = %+v, want %+v", evs, wantEvs)
			}

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

// TestWalkPassesOverRemovedPaths removes a file and a directory after
// their parent was read, as when they are deleted while a scan runs.
// The walk then reaches them, the directory also as one to read and as
// an operand. None of that is an error: the walk sends no event.
func TestWalkPassesOverRemovedPaths(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	file := writeFile(t, dir, "file", []byte("x"))
	writeFile(t, dir, "sub/f", []byte("y"))
	sub := filepath.Join(dir, "sub")
	fileEntry := dirEntryFor(t, dir, "file")
	subEntry := dirEntryFor(t, dir, "sub")

	for _, p := range []string{file, sub} {
		err := os.RemoveAll(p)
		if err != nil {
			t.Fatal(err)
		}
	}

	ctx := t.Context()
	events := make(chan walkEvent, 4)

	emitFile(ctx, file, fileEntry, walkRules{}, events)

	_, descend := subdirJob(ctx, sub, subEntry, dirJob{path: dir}, false,
		walkRules{}, events)
	subs := walkOneDir(ctx, dirJob{path: sub}, false, walkRules{}, events)
	jobs := seedRoot(ctx, sub, walkRules{}, events)

	close(events)

	for ev := range events {
		t.Errorf("event %+v for a removed path, want none", ev)
	}

	if descend || len(subs) != 0 || len(jobs) != 0 {
		t.Errorf("descend = %t, subdirectories %+v, jobs %+v, want none",
			descend, subs, jobs)
	}
}

// TestScanWarnsAboutUnreadablePaths checks that a permission error is
// still warned about and counted as skipped, unlike a removed path. The
// walk reaches an unreadable directory, and a file in a directory that
// can be read but not searched. Another such file is an operand.
//
//nolint:paralleltest // captureStderr replaces the process-wide os.Stderr
func TestScanWarnsAboutUnreadablePaths(t *testing.T) {
	if os.Geteuid() == 0 {
		t.Skip("root ignores file permissions")
	}

	stderr := captureStderr(t)
	dir := t.TempDir()
	tree := filepath.Join(dir, "tree")
	walked := writeFile(t, tree, "unsearchable/f", []byte("x"))
	operand := writeFile(t, dir, "unsearchable/f", []byte("y"))
	unreadable := filepath.Join(tree, "unreadable")

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

	modes := map[string]fs.FileMode{
		unreadable:            0,
		filepath.Dir(walked):  0o400,
		filepath.Dir(operand): 0o400,
	}

	for p, mode := range modes {
		err = os.Chmod(p, mode)
		if err != nil {
			t.Fatal(err)
		}

		// Runs before t.TempDir's own cleanup, which must delete the files.
		t.Cleanup(func() {
			//nolint:gosec // removing the files needs the search bit back
			_ = os.Chmod(p, 0o700)
		})
	}

	st := syncTree(t, openTestDB(t), tree, operand)
	if st != (scanStats{skipped: 3}) {
		t.Errorf("stats = %+v, want 3 skipped and nothing else", st)
	}

	got := stderr()
	for _, warning := range []string{
		"walk " + unreadable + ": open " + unreadable + ": permission denied\n",
		"stat " + walked + ": lstat " + walked + ": permission denied\n",
		"walk " + operand + ": lstat " + operand + ": permission denied\n",
	} {
		if !strings.Contains(got, warning) {
			t.Errorf("stderr = %q, want %q", got, warning)
		}
	}
}

// syncOneFilesystem scans roots into db with -x and returns the scan
// stats. Every device pruneRoots looks up, and the device each
// operand's walk compares its subdirectories with, comes from devices
// instead of from lstat, so a test can put a path on a filesystem that
// no directory here is on. Unlike runPhases, it skips walkableRoots and
// the check for a cancelled walk.
func syncOneFilesystem(t *testing.T, db *sql.DB, roots []string,
	devices map[string]uint64,
) scanStats {
	t.Helper()

	device := func(path string) (uint64, bool) {
		dev, ok := devices[path]

		return dev, ok
	}

	roots = pruneRoots(roots, true, walkRules{}, device)

	ctx := t.Context()
	s := &scanState{db: db}

	err := s.loadIndex(ctx, roots)
	if err != nil {
		t.Fatal(err)
	}

	jobs, subdirs, events := startWalkWorkers(ctx, 2, true, walkRules{})

	// seedRoot emits a regular-file operand itself and returns a job
	// only for a directory operand.
	var initial []dirJob

	for _, root := range roots {
		for _, job := range seedRoot(ctx, root, walkRules{}, events) {
			job.rootDev = devices[root]
			initial = append(initial, job)
		}
	}

	dispatchDirs(ctx, initial, jobs, subdirs)

	s.walkPhase(events, roots)

	err = s.hashPhase(ctx, 2)
	if err != nil {
		t.Fatal(err)
	}

	err = s.updatePhase(ctx)
	if err != nil {
		t.Fatal(err)
	}

	return s.st
}

// TestScanOneFilesystemKeepsOtherFilesystemRecords checks that with -x a
// record below a directory the walk does not enter, because it is on
// another filesystem than its operand, counts as outside the operands:
// it is not deleted. The record of a gone file that is not below that
// directory is still deleted, even when its path begins with the
// directory's name. The operand is given a device that no directory
// here is on, so no second real filesystem is needed.
func TestScanOneFilesystemKeepsOtherFilesystemRecords(t *testing.T) {
	t.Parallel()

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

	// A scan without -x records the file below mnt, and mnt2, which is
	// beside mnt, not below it.
	mounted := writeFile(t, dir, "mnt/f", pattern(1, 100))
	gone := writeFile(t, dir, "mnt2", pattern(3, 50))
	syncTree(t, db, dir)

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

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

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

	syncOneFilesystem(t, db, []string{dir}, map[string]uint64{dir: dev + 1})

	recs := dbRecords(t, db)
	recordByPath(t, recs, mounted)

	if slices.Contains(recordPaths(recs), gone) {
		t.Errorf("record for %s kept: the file is gone and not below mnt",
			gone)
	}
}

// TestScanOneFilesystemWalksNestedOperand checks that with -x an
// operand under another one, on a different filesystem than it, is
// walked on its own: a file added below it is recorded, and the record
// of a file gone from below it is deleted. A record below a directory
// that its own walk does not enter is still kept. Each operand is given
// a device that no directory here is on, so neither walk enters a
// subdirectory.
func TestScanOneFilesystemWalksNestedOperand(t *testing.T) {
	t.Parallel()

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

	// A scan without -x records both files below mnt.
	gone := writeFile(t, dir, "mnt/gone", pattern(1, 10))
	kept := writeFile(t, dir, "mnt/sub/kept", pattern(2, 20))
	syncTree(t, db, dir)

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

	added := writeFile(t, dir, "mnt/added", pattern(3, 30))

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

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

	mnt := filepath.Join(dir, "mnt")
	syncOneFilesystem(t, db, []string{dir, mnt},
		map[string]uint64{dir: dev + 1, mnt: dev + 2})

	paths := recordPaths(dbRecords(t, db))

	if !slices.Contains(paths, added) {
		t.Errorf("no record for %s: the walk did not reach %s", added, mnt)
	}

	if slices.Contains(paths, gone) {
		t.Errorf("record for %s kept: the file is gone", gone)
	}

	if !slices.Contains(paths, kept) {
		t.Errorf("record for %s deleted: the walk of %s did not enter %s",
			kept, mnt, filepath.Dir(kept))
	}
}

// TestScanOneFilesystemWalksOperandBelowOtherFilesystem checks that
// with -x an operand on the same filesystem as the operand covering it
// is walked on its own when a directory between them is on another
// filesystem, since the walk of the covering operand does not enter
// that directory: a file added below the nested operand is recorded,
// and the record of a file gone from below it is deleted. A record
// below that directory but outside the nested operand is still kept.
// Both operands are given one device that no directory here is on,
// while mnt keeps its own.
func TestScanOneFilesystemWalksOperandBelowOtherFilesystem(t *testing.T) {
	t.Parallel()

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

	// A scan without -x records both files below mnt.
	gone := writeFile(t, dir, "mnt/back/gone", pattern(1, 10))
	kept := writeFile(t, dir, "mnt/kept", pattern(2, 20))
	syncTree(t, db, dir)

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

	added := writeFile(t, dir, "mnt/back/added", pattern(3, 30))

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

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

	mnt := filepath.Join(dir, "mnt")
	back := filepath.Join(mnt, "back")
	syncOneFilesystem(t, db, []string{dir, back},
		map[string]uint64{dir: dev + 1, mnt: dev, back: dev + 1})

	paths := recordPaths(dbRecords(t, db))

	if !slices.Contains(paths, added) {
		t.Errorf("no record for %s: the walk did not reach %s", added, back)
	}

	if slices.Contains(paths, gone) {
		t.Errorf("record for %s kept: the file is gone", gone)
	}

	if !slices.Contains(paths, kept) {
		t.Errorf("record for %s deleted: the walk of %s did not enter %s",
			kept, dir, mnt)
	}
}

// TestScanOneFilesystemRecordsNestedFileOnce checks that with -x a
// regular-file operand under another operand is dropped when the file
// reports a different device than that operand but its directory does
// not, as a file bind-mounted into the tree does: the walk of the other
// operand enters the directory and reaches the file, so the file is
// recorded once.
func TestScanOneFilesystemRecordsNestedFileOnce(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	file := writeFile(t, dir, "sub/f", pattern(1, 10))

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

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

	st := syncOneFilesystem(t, db, []string{dir, file}, map[string]uint64{
		dir: dev, filepath.Dir(file): dev, file: dev + 1,
	})

	if st.added != 1 {
		t.Errorf("%s recorded %d times, want once", file, st.added)
	}
}

// TestScanOneFilesystemWalksNestedFileOperand checks that with -x a
// regular-file operand under another operand is kept when its directory
// is on a different filesystem than that operand: the walk of the other
// operand does not enter the directory, so the file is recorded once,
// as its own operand. The other operand is given a device that no
// directory here is on.
func TestScanOneFilesystemWalksNestedFileOperand(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	file := writeFile(t, dir, "sub/f", pattern(1, 10))

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

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

	st := syncOneFilesystem(t, db, []string{dir, file}, map[string]uint64{
		dir: dev + 1, filepath.Dir(file): dev,
	})

	if st.added != 1 {
		t.Errorf("%s recorded %d times, want once", file, st.added)
	}
}

// buildSmokeTree recreates the tree of the test under README
// "Definition of done" 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, walkRules{})
	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(int64) {}, 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, nil)
	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)
}

// TestScanProgressNamesEachPhase checks the plain progress lines of a
// first scan, and of a rescan of one operand holding two of the
// database's records. Each phase's first line names it with its place
// among the four: load counts the records before reading them, and the
// walk estimates its total from the records under its operand, or says
// its time remaining is unknown when there are none.
//
//nolint:paralleltest // captureStderr replaces the process-wide os.Stderr
func TestScanProgressNamesEachPhase(t *testing.T) {
	stderr := captureStderr(t)
	dir := buildSmokeTree(t)
	db := openTestDB(t)

	syncTree(t, db, dir)

	first := stderr()

	syncTree(t, db, filepath.Join(dir, "a"))

	rescan := stderr()[len(first):]
	load := "[1/4] load: counting the records, elapsed 0s, remain unknown"
	cases := map[string][]string{
		first: {
			load, "[2/4] walk: 0 files, 0 files/s, elapsed 0s, remain unknown",
			"[3/4] hash: [0/", "[4/4] update: [0/",
		},
		rescan: {
			load, "[2/4] walk: [0/~2] 0%, 0 files/s, elapsed 0s, remain unknown",
			"[3/4] hash: [0/", "[4/4] update: [0/",
		},
	}

	for out, want := range cases {
		var got []string

		for line := range strings.Lines(out) {
			label, _, _ := strings.Cut(line, ":")
			if len(got) == 0 || !strings.HasPrefix(got[len(got)-1], label) {
				got = append(got, line)
			}
		}

		if len(got) != len(want) {
			t.Fatalf("first lines of the phases = %q, want %q", got, want)
		}

		for i := range want {
			if !strings.HasPrefix(got[i], want[i]) {
				t.Errorf("phase %d starts %q, want %q", i+1, got[i], want[i])
			}
		}
	}

	// The load phase's total is the count of the records.
	loaded := fmt.Sprintf("\n[1/4] load: [%d/%d] 100%%, ",
		smokeTreeFiles, smokeTreeFiles)
	if !strings.Contains(rescan, loaded) {
		t.Errorf("rescan stderr = %q, want %q", rescan, loaded)
	}
}

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

	dir := t.TempDir()
	db := openTestDB(t)
	a := writeFile(t, dir, "a.bin", pattern(1, 500))
	b := 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 it: make every file unreadable, so that a read
	// would fail and count as skipped, and corrupt a stored hash, which
	// must survive the rescan.
	for _, p := range []string{a, b} {
		err := os.Chmod(p, 0)
		if err != nil {
			t.Fatal(err)
		}
	}

	sentinel := sha256.Sum256([]byte("sentinel"))

	_, err := db.ExecContext(context.Background(),
		"UPDATE files SET head = ? WHERE path = ?", sentinel[:], []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 and none skipped",
			st)
	}

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

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 := sha256.Sum256(data); r.head != want || r.tail != want ||
		r.content != want {
		t.Fatalf("head, tail, content = %x, %x, %x, want %x for each",
			r.head, r.tail, r.content, want)
	}
}

// TestScanStoresRawHashes checks what the database holds for a file
// larger than both end windows, whose three hashes all differ: head,
// tail and content are each a BLOB of the 32 bytes of the SHA-256 the
// scan computed.
func TestScanStoresRawHashes(t *testing.T) {
	t.Parallel()

	dir := t.TempDir()
	db := openTestDB(t)
	data := pattern(3, 3*headTailWindow)
	p := writeFile(t, dir, "f.bin", data)

	syncTree(t, db, dir)

	var (
		blobs               bool
		head, tail, content []byte
	)

	err := db.QueryRowContext(t.Context(),
		"SELECT typeof(head) = 'blob' AND typeof(tail) = 'blob' AND "+
			"typeof(content) = 'blob', head, tail, content "+
			"FROM files WHERE path = ?", []byte(p)).
		Scan(&blobs, &head, &tail, &content)
	if err != nil {
		t.Fatal(err)
	}

	if !blobs {
		t.Error("head, tail and content are not all BLOBs")
	}

	wantHead := sha256.Sum256(data[:headTailWindow])
	wantTail := sha256.Sum256(data[len(data)-headTailWindow:])
	wantContent := sha256.Sum256(data)

	if !bytes.Equal(head, wantHead[:]) || !bytes.Equal(tail, wantTail[:]) ||
		!bytes.Equal(content, wantContent[:]) {
		t.Errorf("head, tail, content = %x, %x, %x, want %x, %x, %x",
			head, tail, content, wantHead, wantTail, wantContent)
	}
}

// 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. The operand is
// the file's directory, or the file itself, which scan stats without
// reading its directory.
func TestSyncScanSameSecondRewrite(t *testing.T) {
	t.Parallel()

	for _, fileOperand := range []bool{false, true} {
		t.Run(fmt.Sprintf("file operand %v", fileOperand), func(t *testing.T) {
			t.Parallel()

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

			operand := dir
			if fileOperand {
				operand = a
			}

			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, operand)

			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, operand)
			if st != (scanStats{walked: 1, updated: 1}) {
				t.Fatalf("rescan stats = %+v, want 1 updated", 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))

	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: 1, updated: 1}) {
		t.Fatalf("rescan stats = %+v, want 1 updated", 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)
	}
}

// TestScanHashesUniqueSize checks that a file whose size no other file
// shares is hashed like every other file.
func TestScanHashesUniqueSize(t *testing.T) {
	t.Parallel()

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

	syncTree(t, db, dir)

	assertWholeFileHashed(t, db, a, data)
}

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 == [sha256.Size]byte{} || 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)
	}
}

// TestHashPhaseSkipsFileReplacedByFIFO replaces a walked regular file
// with a FIFO before the hash phase reads it. Opening a FIFO that has
// no writer waits for one, so a blocking open would hang the phase. The
// path must be warned about once and skipped, with no record written.
//
//nolint:paralleltest // captureStderr replaces the process-wide os.Stderr
func TestHashPhaseSkipsFileReplacedByFIFO(t *testing.T) {
	stderr := captureStderr(t)
	dir := t.TempDir()
	p := writeFile(t, dir, "a.bin", pattern(1, 300))

	walked, _ := collectWalk(t, []string{dir}, false, 1)

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

	err = unix.Mkfifo(p, 0o600)
	if err != nil {
		t.Fatal(err)
	}

	s := &scanState{db: openTestDB(t), toHash: walked}

	err = s.hashPhase(t.Context(), 1)
	if err != nil {
		t.Fatalf("hashPhase = %v, want nil", err)
	}

	if s.st.skipped != 1 || len(s.batch) != 0 {
		t.Errorf("skipped = %d, records = %d, want 1 skipped and none",
			s.st.skipped, len(s.batch))
	}

	warning := "hash " + p + ": not a regular file\n"
	if got := stderr(); strings.Count(got, warning) != 1 {
		t.Errorf("stderr = %q, want %q once", got, warning)
	}
}

// TestHashPhasePassesOverRemovedFiles removes two walked files before
// the hash phase reads them: one with no other path, and the first of
// two hard links to one file. Neither is an error. The phase prints
// nothing but its progress, counts nothing as skipped, and records only
// the hard link still there.
//
//nolint:paralleltest // captureStderr replaces the process-wide os.Stderr
func TestHashPhasePassesOverRemovedFiles(t *testing.T) {
	stderr := captureStderr(t)
	dir := t.TempDir()
	alone := writeFile(t, dir, "alone.bin", pattern(1, 300))
	a := writeFile(t, dir, "a.bin", pattern(2, 300))
	b := filepath.Join(dir, "b.bin")

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

	walked, _ := collectWalk(t, []string{dir}, false, 1)

	// a.bin sorts before b.bin, so the run of the two reads it first.
	for _, p := range []string{alone, a} {
		err = os.Remove(p)
		if err != nil {
			t.Fatal(err)
		}
	}

	s := &scanState{db: openTestDB(t), toHash: walked}

	err = s.hashPhase(t.Context(), 1)
	if err != nil {
		t.Fatalf("hashPhase = %v, want nil", err)
	}

	if s.st.skipped != 0 || len(s.batch) != 1 || s.batch[0].path != b {
		t.Errorf("skipped = %d, records %+v, want none skipped and a "+
			"record for %s alone", s.st.skipped, s.batch, b)
	}

	for line := range strings.Lines(stderr()) {
		if !strings.HasPrefix(line, scanPhase("hash")+": ") {
			t.Errorf("stderr holds %q, want the hash phase's progress alone",
				line)
		}
	}
}

// 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()

	const pqRoot = "/p/q"

	// /p/q is on another filesystem than /p; /p/q/r is on the same one as
	// /p/q, /p/s as /p, and /p/t has no known device.
	devices := map[string]uint64{"/p": 1, pqRoot: 2, "/p/q/r": 2, "/p/s": 1}
	device := func(path string) (uint64, bool) {
		dev, ok := devices[path]

		return dev, ok
	}

	// 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"},
		false, walkRules{}, device)

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

	nested := []string{"/p/q/r", pqRoot, "/p", "/p", "/p/s", "/p/t"}

	got = pruneRoots(nested, false, walkRules{}, device)

	want = []string{"/p"}
	if !slices.Equal(got, want) {
		t.Fatalf("pruneRoots without -x = %q, want %q", got, want)
	}

	// With -x, /p/q, on another filesystem than /p, is kept as well.
	got = pruneRoots(nested, true, walkRules{}, device)

	want = []string{"/p", pqRoot}
	if !slices.Equal(got, want) {
		t.Fatalf("pruneRoots with -x = %q, want %q", got, want)
	}

	// The walk of /p does not enter /p/q when it is a default exclude, so
	// /p/q is kept, without -x too; /p/q/r lies under it and is dropped.
	got = pruneRoots(nested, false, walkRules{excludes: []string{pqRoot}},
		device)
	if !slices.Equal(got, want) {
		t.Fatalf("pruneRoots excluding %s = %q, want %q", pqRoot, got, want)
	}

	// Nor does it enter /p/q when the filesystem of /p/q is not
	// persistent, so /p/q/r/m, of no known device, is kept.
	got = pruneRoots([]string{"/p", "/p/q/r/m"}, false,
		walkRules{nonPersistent: map[uint64]string{2: "tmpfs"}}, device)

	want = []string{"/p", "/p/q/r/m"}
	if !slices.Equal(got, want) {
		t.Fatalf("pruneRoots with %s not persistent = %q, want %q",
			pqRoot, 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)
		}
	}
}

// TestRunScanPassesOverDatabase scans a tree that holds the scan's own
// database, reached directly and through a symlinked directory. The
// walk passes over the database file, its -wal and -shm files and its
// .lock file with no line and no count, and the record an earlier scan
// left for the .lock file is deleted. A rescan of the unchanged tree
// updates nothing, and report lists none of the database's files.
func TestRunScanPassesOverDatabase(t *testing.T) {
	for _, viaSymlink := range []bool{false, true} {
		t.Run(fmt.Sprintf("via symlink %v", viaSymlink), func(t *testing.T) {
			base := t.TempDir()
			tree := filepath.Join(base, "real", "tree")
			operand := tree

			writeFile(t, tree, "a", pattern(1, 100))
			writeFile(t, tree, "b", pattern(1, 100))
			writeFile(t, tree, "empty1", nil)
			writeFile(t, tree, "empty2", nil)

			if viaSymlink {
				err := os.Symlink(filepath.Join(base, "real"),
					filepath.Join(base, "link"))
				if err != nil {
					t.Fatal(err)
				}

				operand = filepath.Join(base, "link", "tree")
			}

			dbPath := filepath.Join(tree, "db.sqlite")
			t.Setenv(databaseEnv, dbPath)

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

			err = applyChanges(t.Context(), db, []scanRec{
				{path: filepath.Join(operand, "db.sqlite.lock")},
			}, nil, nil)
			if err != nil {
				t.Fatal(err)
			}

			closeScanDatabase(t.Context(), db, dbPath)

			assertScanSummary(t,
				"4 files seen (4 added, 0 updated, 1 removed, 0 unchanged)",
				operand)
			assertScanSummary(t,
				"4 files seen (0 added, 0 updated, 0 removed, 4 unchanged)",
				operand)

			report := runStdout(t, cmdReport)
			if strings.Contains(report, "db.sqlite") ||
				!strings.Contains(report, filepath.Join(operand, "empty2")) {
				t.Errorf("report = %q, want the empty files and none of "+
					"the database's files", report)
			}
		})
	}
}

// TestRunScanPassesOverDatabaseOperands scans the database file and its
// .lock file given as operands themselves: neither is recorded or
// counted.
func TestRunScanPassesOverDatabaseOperands(t *testing.T) {
	dbPath := testDBPath(t)
	t.Setenv(databaseEnv, dbPath)

	// The first scan creates both files.
	scanOK(t, t.TempDir())

	assertScanSummary(t,
		"0 files seen (0 added, 0 updated, 0 removed, 0 unchanged)",
		dbPath, dbPath+".lock")
}

// assertScanSummary scans operands and fails the test unless the
// summary line gives counts with nothing skipped, and the line naming
// the database is the only one that names one of its files.
func assertScanSummary(t *testing.T, counts string, operands ...string) {
	t.Helper()

	stderr := scanOK(t, operands...)

	want := "scan: " + counts + ", 0 skipped\n"
	if !strings.Contains(stderr, want) {
		t.Errorf("scan %q: stderr = %q, want %q", operands, stderr, want)
	}

	if strings.Count(stderr, "db.sqlite") != 1 {
		t.Errorf("scan %q: stderr = %q, want only the line naming the "+
			"database to name one of its files", operands, stderr)
	}
}