Bounded Loop with UUID Fallback for Unique Names

Bounded Loop with UUID Fallback for Unique Names

Problem

When generating unique names (files, resources, identifiers), the common pattern of incrementing a counter until finding an available name can degrade to O(n) performance or infinite loops in pathological cases.

Symptoms:

• Application hangs when importing to folder with many similarly-named files
• CPU spikes during name collision resolution
• Tests timeout in edge cases with high collision counts

Investigation

Steps Tried

1. Unbounded counter loop - Works normally, but O(n) worst case and potential infinite loop
2. Pre-scan for max counter - Expensive for large directories
3. Bounded loop with UUID fallback - Optimal: O(1) worst case, human-readable common case

Root Cause

Traditional unique name generation assumes:

• Collisions are rare (usually true)
• Counter increments are cheap (true, but iteration isn’t)
• There’s always a free slot (not guaranteed without bounds)

In edge cases (batch imports, test fixtures, adversarial inputs), these assumptions fail.

Solution

Bound the search loop and fall back to UUID for guaranteed uniqueness:

Code Changes

// Before (unbounded - potential infinite loop)
fn generate_unique_name(workspace_path: &Path, relative: &Path) -> PathBuf {
    let stem = relative.file_stem().unwrap().to_string_lossy();
    let ext = relative.extension().unwrap().to_string_lossy();

    let mut counter = 1;
    loop {  // DANGEROUS: no upper bound
        let new_name = format!("{}-{}.{}", stem, counter, ext);
        let full_path = workspace_path.join(&new_name);
        if !full_path.exists() {
            return new_name.into();
        }
        counter += 1;
    }
}

// After (bounded with UUID fallback)
const MAX_UNIQUE_NAME_ATTEMPTS: u32 = 10_000;

fn generate_unique_name(workspace_path: &Path, relative: &Path) -> PathBuf {
    let parent = relative.parent().unwrap_or(Path::new(""));
    let stem = relative.file_stem()
        .map(|s| s.to_string_lossy().to_string())
        .unwrap_or_default();
    let ext = relative.extension()
        .map(|e| e.to_string_lossy().to_string())
        .unwrap_or_default();

    // Try human-readable incrementing names first
    for counter in 1..=Self::MAX_UNIQUE_NAME_ATTEMPTS {
        let new_name = format!("{}-{}.{}", stem, counter, ext);
        let new_path = parent.join(&new_name);
        let full_path = workspace_path.join(&new_path);

        if !full_path.exists() {
            return new_path;
        }
    }

    // Fallback: UUID guarantees uniqueness without checking
    let uuid_suffix = uuid::Uuid::new_v4().to_string();
    let fallback_name = format!("{}-{}.{}", stem, uuid_suffix, ext);
    parent.join(&fallback_name)
}

Implementation Notes

• 10,000 attempts balances human-readability vs performance
• UUID fallback requires no existence check - statistically unique
• Preserve directory structure - join with parent path
• Handle missing extension - empty string is valid

Prevention

Best Practices

1. Always bound uniqueness loops - define MAX_ATTEMPTS constant
2. Provide deterministic fallback - UUID, timestamp, or hash
3. Document the bound - so callers know worst-case behavior
4. Consider the context - 100 might be enough for UI, 10,000 for imports

Warning Signs

• Any loop { ... counter += 1 } without break condition
• while !exists() { ... } patterns
• Tests that “usually pass” but occasionally timeout

Design Tradeoffs

Approach	Pros	Cons
Unbounded counter	Simple, readable names	O(n), potential hang
UUID only	O(1), always unique	Ugly names always
Bounded + fallback	Readable names, O(1) worst	Slightly complex
Hash-based	Deterministic, O(1)	May still collide

Related Patterns

This pattern applies to:

• Workspace names: My Workspace, My Workspace-1, …, My Workspace-{uuid}
• Temp files: upload.tmp, upload-1.tmp, …, upload-{uuid}.tmp
• Database slugs: page-title, page-title-1, …, page-title-{uuid}
• Asset names in imports/exports

References

• Commit: 52bf3bf - feat(import): add Copy and In-Place import modes
• Location: crates/infrastructure/import/src/import/import_repository.rs:344