Repository: sxyazi/yazi (language: rust)

Issue:
Analyze the renaming order of bulk-renamed files to avoid conflicts
### `yazi --debug` output

```Shell
Yazi
    Version: 0.3.3 (termux 2024-09-05)
    Debug  : false
    OS     : android-aarch64 (unix)

Ya
    Version: 0.3.3 (termux 2024-09-05)

Emulator
    Emulator.via_env: ("xterm-256color", "")
    Emulator.via_csi: Ok(Unknown([]))
    Emulator.detect : Unknown([])

Adapter
    Adapter.matches: X11

Desktop
    XDG_SESSION_TYPE           : None
    WAYLAND_DISPLAY            : None
    DISPLAY                    : Some(":1")
    SWAYSOCK                   : None
    HYPRLAND_INSTANCE_SIGNATURE: None
    WAYFIRE_SOCKET             : None

SSH
    shared.in_ssh_connection: false

WSL
    WSL: false

Variables
    SHELL              : Some("/data/data/com.termux/files/usr/bin/fish")
    EDITOR             : Some("/data/data/com.termux/files/usr/bin/nvim")
    VISUAL             : Some("/data/data/com.termux/files/usr/bin/nvim")
    YAZI_FILE_ONE      : None
    YAZI_CONFIG_HOME   : None

Text Opener
    default: Some(Opener { run: "${EDITOR:-vi} \"$@\"", block: true, orphan: false, desc: "$EDITOR", for_: None, spread: true })
    block  : Some(Opener { run: "${EDITOR:-vi} \"$@\"", block: true, orphan: false, desc: "$EDITOR", for_: None, spread: true })

Multiplexers
    TMUX               : false
    tmux version       : tmux 3.5a
    ZELLIJ_SESSION_NAME: None
    Zellij version     : No such file or directory (os error 2)

Dependencies
    file             : 5.45
    ueberzugpp       : No such file or directory (os error 2)
    ffmpegthumbnailer: No such file or directory (os error 2)
    magick           : No such file or directory (os error 2)
    fzf              : 0.55
    fd               : 10.2.0
    rg               : 14.1.1
    chafa            : No such file or directory (os error 2)
    zoxide           : 0.9.6
    7z               : 17.05
    7zz              : No such file or directory (os error 2)
    jq               : 1.7.1


--------------------------------------------------
When reporting a bug, please also upload the `yazi.log` log file - only upload the most recent content by time.
You can find it in the "/data/data/com.termux/files/home/.local/state/yazi" directory.
```


### Please describe the problem you're trying to solve

when trying to bulk rename files yazi skips renaming if desnination file already exists, even if you were going to rename the destinatoin too

this does not work as expected even though there is no conflict:
```
a -> b
b -> c
```

this makes doing something like incrementing numbers in files in bulk harder to do
```
01 -> 02 ×
02 -> 03 ×
03 -> 04 ×
04 -> 05 ×
05 -> 06 ×
06 -> 07 ×
07 -> 08 ×
08 -> 09 ×
09 -> 10 ✓
```

### Would you be willing to contribute this feature?

- [ ] Yes, I'll give it a shot

### Describe the solution you'd like

use temp/intermediate files if destination exists and is scheduled to be renamed:
```
a -> b.XXXXX
b -> c
b.XXXXX -> b
```

or reshuffle rename execution:
```
b -> c
a -> b
```

(i recommend using temp files since it also takes care of swapping files)

### Additional context

_No response_

### Validations

- [X] I have searched the existing issues/discussions
- [X] The latest nightly build of Yazi doesn't already have this feature


Discussion / hints:
I don't think using temporary filenames is a good idea because it breaks the atomic operation `a -> b` into two steps: `a -> a.tmp` and `a.tmp -> b`. 

Since the filesystem doesn't have the concept of transactions, all I/O operations are prone to failure. This could introduce unexpected security risks, as either of these two steps could fail.

I believe a better approach would be to come up with an algorithm that automatically analyzes the order in which files should be renamed. For example, in the case of:

```
1:  a -> b
2:  b -> c
```

The renaming operations should be done in the order:

```
2:  b -> c
1:  a -> b
```

Anyone want to give it a try? All the code for bulk renaming can be found in  
https://github.com/sxyazi/yazi/blob/main/yazi-core/src/manager/commands/bulk_rename.rs

Hi, I am an open source beginner looking for a good issue to contribute to for the first time. Can I try to handle this issue?

As you mentioned above, I think this problem can be solved by determining the order of rename using topological sort.
Sure, go for it! 

If you need any guidance, just let me know @yw1ee!

Fix patch:
diff --git a/yazi-core/src/manager/commands/bulk_rename.rs b/yazi-core/src/manager/commands/bulk_rename.rs
index 88bf79d2c..17bda7571 100644
--- a/yazi-core/src/manager/commands/bulk_rename.rs
+++ b/yazi-core/src/manager/commands/bulk_rename.rs
@@ -53,7 +53,7 @@ impl Manager {
 			return Ok(());
 		}
 
-		let todo: Vec<_> = old.into_iter().zip(new).filter(|(o, n)| o != n).collect();
+		let todo = Self::prioritized_paths(old, new);
 		if todo.is_empty() {
 			return Ok(());
 		}
@@ -117,4 +117,90 @@ impl Manager {
 		stdin().read_exact(&mut [0]).await?;
 		Ok(())
 	}
+
+	fn prioritized_paths(old: Vec<PathBuf>, new: Vec<PathBuf>) -> Vec<(PathBuf, PathBuf)> {
+		let orders: HashMap<_, _> = old.iter().enumerate().map(|(i, p)| (p, i)).collect();
+		let mut incomes: HashMap<_, _> = old.iter().map(|p| (p, false)).collect();
+		let mut todos: HashMap<_, _> = old
+			.iter()
+			.zip(new)
+			.map(|(o, n)| {
+				incomes.get_mut(&n).map(|b| *b = true);
+				(o, n)
+			})
+			.collect();
+
+		let mut sorted = Vec::with_capacity(old.len());
+		while !todos.is_empty() {
+			// Paths that are non-incomes and don't need to be prioritized in this round
+			let mut outcomes: Vec<_> = incomes.iter().filter(|(_, &b)| !b).map(|(&p, _)| p).collect();
+			outcomes.sort_unstable_by(|a, b| orders[b].cmp(&orders[a]));
+
+			// If there're no outcomes, it means there are cycles in the renaming
+			if outcomes.is_empty() {
+				let mut remain: Vec<_> = todos.into_iter().map(|(o, n)| (o.clone(), n)).collect();
+				remain.sort_unstable_by(|(a, _), (b, _)| orders[a].cmp(&orders[b]));
+				sorted.reverse();
+				sorted.extend(remain);
+				return sorted;
+			}
+
+			for old in outcomes {
+				let Some(new) = todos.remove(old) else { unreachable!() };
+				incomes.remove(&old);
+				incomes.get_mut(&new).map(|b| *b = false);
+				sorted.push((old.clone(), new));
+			}
+		}
+		sorted.reverse();
+		sorted
+	}
+}
+
+#[cfg(test)]
+mod tests {
+	use super::*;
+
+	#[test]
+	fn test_sort() {
+		fn cmp(input: &[(&str, &str)], expected: &[(&str, &str)]) {
+			let sorted = Manager::prioritized_paths(
+				input.iter().map(|&(o, _)| o.into()).collect(),
+				input.iter().map(|&(_, n)| n.into()).collect(),
+			);
+			let sorted: Vec<_> =
+				sorted.iter().map(|(o, n)| (o.to_str().unwrap(), n.to_str().unwrap())).collect();
+			assert_eq!(sorted, expected);
+		}
+
+		#[rustfmt::skip]
+		cmp(
+			&[("2", "3"), ("1", "2"), ("3", "4")],
+			&[("3", "4"), ("2", "3"), ("1", "2")]
+		);
+
+		#[rustfmt::skip]
+		cmp(
+			&[("1", "3"), ("2", "3"), ("3", "4")],
+			&[("3", "4"), ("1", "3"), ("2", "3")]
+		);
+
+		#[rustfmt::skip]
+		cmp(
+			&[("2", "1"), ("1", "2")],
+			&[("2", "1"), ("1", "2")]
+		);
+
+		#[rustfmt::skip]
+		cmp(
+			&[("3", "2"), ("2", "1"), ("1", "3"), ("a", "b"), ("b", "c")],
+			&[("b", "c"), ("a", "b"), ("3", "2"), ("2", "1"), ("1", "3")]
+		);
+
+		#[rustfmt::skip]
+		cmp(
+			&[("b", "b_"), ("a", "a_"), ("c", "c_")],
+			&[("b", "b_"), ("a", "a_"), ("c", "c_")],
+		);
+	}
 }


Test patch: