This post is inspired by a discussion regarding a coding snack done by lanux128 on DonationCoder. A user requested a tool to add a context menu entry that would copy selected files and folders to the parent folder.
Moving folders is one of those tasks that appear trivial. But as always, the devil is in the details.
To keep it simple, we will assume regular files and folders in a filesystem where paths are unique. The problem we will look at is: Given absolute paths Src and Dst (where Dst is not equal to, or a subfolder of Src), move the contents of Src to Dst.
The first solution that comes to mind is to move files and folders recursively. In pseudocode it would be something along the lines of:
This works – well, almost.
Consider the following folder structure (please forgive the tree output, it was an easy way to get a consistent representation):
\---parent \---foo | log.txt ; contains "first" | \---foo log.txt ; contains "second"
We are in \parent\foo and want to move the contents (the subfolder foo and the file log.txt) to \parent. The correct result would be:
\---parent | log.txt ; contains "first" | \---foo log.txt ; contains "second"
The problem is that if we call MoveSimple(\parent\foo, \parent), and we process the subfolder foo first, then we will overwrite \parent\foo\log.txt before it gets moved out to \parent.
You might suggest that we handle files first, and then recurse on subfolders. But that won’t work either:
\---parent \---foo +---foo | \---zeb | log.txt | \---zeb log.txt
If we recurse into foo before zeb, we will overwrite \parent\foo\zeb\log.txt before it gets moved out.
By now it should be clear that the culprit is the foo subfolder. With that, we end up writing to parts of the folder structure we are in the process of moving.
More generally, we may run into problems if any destination path touches the source tree.
The sledge hammer fix is to make sure there is no way we can overwrite anything in the source folder, by first moving it to someplace safe, and then to where we want it:
This works, but now we are moving every file and folder twice. Besides the performance impact, it would also make it hard to interrupt the operation and handle errors – the user could end up with files lost in a temporary directory.
Let’s go back to MoveSimple and try to figure out what exactly went wrong. It worked fine as long as we did not write to parts of the source tree that we had not moved yet.
The only way we can end up writing into the source tree, is if Src contains a special subfolder with a relative path that exactly matches the path from Dst to Src. Such a path would be unique.
Moving that special folder is only a problem if there is still something else left in Src that has not yet been moved. If we moved everything else, there is nothing it can overwrite.
So if we check if we run into such a special folder, and make sure we move everything else before it, it should work:
I wrote a simple Perl script that implements MoveSafe, and it works for all the test cases in this post, but of course standard disclaimers apply.
There are other ways to implement safely moving a folder, depending on what features you desire. For instance you can make it safe to move a folder to a child folder, which this function does not handle. The aim with this particular method was to get (roughly) the same speed as the simple recursive method.
At this point I started wondering if I was overcomplicating things – if this was in fact all rather trivial. So I set out to check how some popular file managers would fare.
I made two test cases, which are similar to the examples above, but contain a few more files to make sure sorting order does not help any application get it right by chance.
I used a script to generate the test cases to make sure they were identical, and used any internal move command where possible. I answered yes to any dialogs that asked if I wanted to overwrite anything.
The first test case is this (as usual we are in \parent\foo and want to move the contents to \parent):
\---parent \---foo | a.txt ; "first" | z.txt ; "first" | \---foo | a.txt ; "second" | z.txt ; "second" | \---foo a.txt ; "third" z.txt ; "third"
And the second test case is:
\---parent \---foo +---ccc | a.txt | x.txt | +---foo | +---ccc | | b.txt | | y.txt | | | \---zzz | b.txt | y.txt | \---zzz a.txt x.txt
None of the five file managers tested handled these two test correctly. I realize this special condition is not very common, but I still found it interesting that none of them, not even Windows Explorer, appear to be able to move any folder to a parent folder.