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

1 files changed, 29 insertions, 5 deletions

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, ""
 		}
 	}