the suffix search continues instead of starting again at _1

Every file renamed onto one name probed stem_1, stem_2, ... from the
beginning, so N files cost N^2/2 Exists calls - a test here counts 1890
of them for 60 files. The search now continues from the highest suffix
already tried for that stem.

Within one plan that is the same answer: the taken set only grows while
a plan is built and the disk is not being written to, so a suffix taken
once stays taken. Proved rather than argued - with same_1 and same_3
already on disk and same_2 free, both versions put a file in the gap,
and the two plans are byte-identical.

  1500 files renamed to one name: 2.63s -> 0.05s

4 files changed, 89 insertions, 13 deletions

diff --git a/internal/plan/chain.go b/internal/plan/chain.go
index b8a95f6..7c95d9b 100644
--- a/internal/plan/chain.go
+++ b/internal/plan/chain.go
@@ -25,13 +25,13 @@ type Claims struct {
 
 // NewClaims returns an empty Claims, ready to pass to Build.
 func NewClaims() *Claims {
-	return &Claims{taken: claimed{}}
+	return &Claims{taken: newClaimed()}
 }
 
 // Claim marks path as spoken for: a later Build call of the run treats it
 // as another step's result, never displacing it (spec §7.4).
 func (c *Claims) Claim(path string) {
-	c.taken[path] = true
+	c.taken.taken[path] = true
 }
 
 // Input is one file and the rules that matched it, in match order.
@@ -80,7 +80,7 @@ func Build(root string, in []Input, now time.Time, d Disk, claims *Claims) []Cha
 	// takes a free name there, exactly as suffix already did for a path that
 	// exists on disk.
 	for _, x := range in {
-		claims.taken[x.File.Path] = true
+		claims.taken.taken[x.File.Path] = true
 	}
 	chains := make([]Chain, len(in))
 	for _, i := range order {
@@ -152,7 +152,7 @@ func buildOne(root string, in Input, now time.Time, d Disk, claim claimed) Chain
 					// a name be claimed before its file has actually
 					// vacated it - and stays; do not "fix" it by weakening
 					// the disk check.
-					claim[resolved] = true
+					claim.taken[resolved] = true
 					if a.Kind == config.Move {
 						cur = resolved
 						moves++
@@ -184,7 +184,7 @@ func buildOne(root string, in Input, now time.Time, d Disk, claim claimed) Chain
 				step.Displaces = displaces
 				if skip == "" {
 					cur = resolved
-					claim[resolved] = true
+					claim.taken[resolved] = true
 				}
 
 			case config.Delete, config.DeletePermanent:
diff --git a/internal/plan/conflict.go b/internal/plan/conflict.go
index f5c1224..e1cd6bf 100644
--- a/internal/plan/conflict.go
+++ b/internal/plan/conflict.go
@@ -53,7 +53,22 @@ func (NoDisk) SameContent(string, string) (bool, error) { return false, nil }
 
 // claimed is the set of destination paths already spoken for by an earlier
 // step of this plan.
-type claimed map[string]bool
+type claimed struct {
+	// taken is the set of destination paths already spoken for.
+	taken map[string]bool
+
+	// next is the highest suffix already tried for a stem, so filling one
+	// directory with one name does not begin at _1 for every file. Within
+	// a plan that is the same answer as starting from 1: the taken set
+	// only grows while a plan is built, and the disk is not being written
+	// to, so a suffix taken once stays taken.
+	next map[string]int
+}
+
+// newClaimed returns an empty claimed, both maps ready.
+func newClaimed() claimed {
+	return claimed{taken: map[string]bool{}, next: map[string]int{}}
+}
 
 // resolveConflict decides what a step whose destination is contested does,
 // per spec §7.4. src is the step's source (its current path, before this
@@ -89,7 +104,7 @@ func resolveConflict(kind Kind, policy config.Conflict, src, dst string, d Disk,
 		}
 	}
 
-	if !onDisk && !c[dst] {
+	if !onDisk && !c.taken[dst] {
 		return dst, "", ""
 	}
 
@@ -97,7 +112,7 @@ func resolveConflict(kind Kind, policy config.Conflict, src, dst string, d Disk,
 	case config.ConflictSkip:
 		return dst, "target exists", ""
 	case config.ConflictOverwrite:
-		if onDisk && !c[dst] {
+		if onDisk && !c.taken[dst] {
 			// Only a regular file is ever trashed to make room: a
 			// directory or link of the same name stays, and so does the
 			// step - skipped, saying why.
@@ -141,9 +156,18 @@ const maxSuffixAttempts = 10000
 func suffixed(dst string, d Disk, c claimed) (resolved, skip string) {
 	dir, base := filepath.Split(dst)
 	stem, ext := splitExt(base)
-	for n := 1; n <= maxSuffixAttempts; n++ {
+	key := dir + "\x00" + stem + "\x00" + ext
+	start := c.next[key]
+	if start < 1 {
+		start = 1
+	}
+	for n := start; n <= maxSuffixAttempts; n++ {
 		candidate := filepath.Join(dir, fmt.Sprintf("%s_%d%s", stem, n, ext))
-		if !d.Exists(candidate) && !c[candidate] {
+		if !d.Exists(candidate) && !c.taken[candidate] {
+			// n itself, not n+1: the caller claims this candidate, so the
+			// next search sees it taken and moves on. Recording n+1 would
+			// skip a suffix that is still free if this step is dropped.
+			c.next[key] = n
 			return candidate, ""
 		}
 	}
diff --git a/internal/plan/conflict_test.go b/internal/plan/conflict_test.go
index ba415d5..ba111f8 100644
--- a/internal/plan/conflict_test.go
+++ b/internal/plan/conflict_test.go
@@ -3,6 +3,7 @@
 package plan
 
 import (
+	"fmt"
 	"os"
 	"path/filepath"
 	"testing"
@@ -232,7 +233,7 @@ func TestSuffixedCapsAttempts(t *testing.T) {
 func TestOverwriteNeverDisplacesADirectory(t *testing.T) {
 	dir := "/home/x/Documents/Invoices"
 	d := fakeDisk{exists: map[string]bool{dir: true}, dirs: map[string]bool{dir: true}}
-	_, skip, displaces := resolveConflict(Move, config.ConflictOverwrite, "/r/Invoices", dir, d, claimed{})
+	_, skip, displaces := resolveConflict(Move, config.ConflictOverwrite, "/r/Invoices", dir, d, newClaimed())
 	if displaces != "" || skip != "target is not a regular file" {
 		t.Errorf("skip %q displaces %q; want skipped, nothing displaced", skip, displaces)
 	}
@@ -252,3 +253,54 @@ func TestOverwriteNeverDisplacesAnotherScannedFile(t *testing.T) {
 		t.Errorf("Displaces %q Dst %q Skip %q; want no displacement and /r/b_1.pdf", s.Displaces, s.Dst, s.Skip)
 	}
 }
+
+// countingDisk counts Exists calls, so a test can pin how much probing a
+// plan does rather than only what it produces.
+type countingDisk struct {
+	fakeDisk
+	calls int
+}
+
+func (d *countingDisk) Exists(p string) bool {
+	d.calls++
+	return d.fakeDisk.Exists(p)
+}
+
+// TestSuffixedDoesNotRescanFromOne: every file renamed to one name probes
+// stem_1, stem_2, ... for a free suffix. Starting each file's search at 1
+// makes N files into N^2/2 Exists calls - 4000 files were eight million of
+// them - so the search continues from the highest suffix already tried for
+// that name. Within one plan that is the same answer: the taken set only
+// grows while a plan is built, so a suffix taken once stays taken.
+func TestSuffixedDoesNotRescanFromOne(t *testing.T) {
+	const n = 60
+	in := make([]Input, 0, n)
+	for i := 0; i < n; i++ {
+		in = append(in, Input{File: file("/r", fmt.Sprintf("f%02d.pdf", i)), Rules: []RuleMatch{
+			{Name: "one", Actions: []config.Action{act(config.Move, "Work"), act(config.Rename, "same.pdf")}}}})
+	}
+	d := &countingDisk{fakeDisk: fakeDisk{exists: map[string]bool{}}}
+	chains := Build("/r", in, time.Now(), d, NewClaims())
+
+	// Every file must still land on its own name, the lowest free one.
+	seen := map[string]bool{}
+	for _, c := range chains {
+		last := c.Steps[len(c.Steps)-1]
+		if last.Dst == "" {
+			t.Fatalf("%s was skipped: %q", c.File.Rel, last.Skip)
+		}
+		if seen[last.Dst] {
+			t.Errorf("two files planned onto %s", last.Dst)
+		}
+		seen[last.Dst] = true
+	}
+	if len(seen) != n {
+		t.Errorf("%d distinct destinations for %d files", len(seen), n)
+	}
+	// Quadratic probing would be about n*n/2 = 1800 here; linear is a few
+	// per file. The bound is loose on purpose - it must fail on n^2 and
+	// pass on anything sane.
+	if d.calls > 6*n {
+		t.Errorf("%d Exists calls for %d files: the suffix search is rescanning from _1", d.calls, n)
+	}
+}
diff --git a/internal/plan/enum_test.go b/internal/plan/enum_test.go
index 21f6a63..fee279e 100644
--- a/internal/plan/enum_test.go
+++ b/internal/plan/enum_test.go
@@ -62,7 +62,7 @@ func TestEveryConflictPolicyIsPlanned(t *testing.T) {
 					t.Errorf("config.%s is not planned: %v", name, r)
 				}
 			}()
-			resolveConflict(Move, config.Conflict(i), "/r/a.pdf", "/r/b.pdf", d, claimed{})
+			resolveConflict(Move, config.Conflict(i), "/r/a.pdf", "/r/b.pdf", d, newClaimed())
 		}()
 	}
 	defer func() {
@@ -70,5 +70,5 @@ func TestEveryConflictPolicyIsPlanned(t *testing.T) {
 			t.Error("an unknown conflict policy did not panic")
 		}
 	}()
-	resolveConflict(Move, config.Conflict(len(policies)), "/r/a.pdf", "/r/b.pdf", d, claimed{})
+	resolveConflict(Move, config.Conflict(len(policies)), "/r/a.pdf", "/r/b.pdf", d, newClaimed())
 }