Detect directory loops

[israel-lugo]

Now that find_duplicates_in_firs has the follow_dirlinks parameter (see #16), we need a way to detect symlink loops. If there is a symlink pointing to ., or to a parent directory, we will go in a loop.

Fortunately, os.walk() seems to stop after several levels of recursion. But still, it's probably undefined behavior.

See what commands like find or rsync do.

[israel-lugo]

We ended up detecting any kind of directory loop, not just those caused by symlinks. Should never happen without symlinks, the filesystem itself may be corrupted somehow (e.g. directory hardlinks).

[israel-lugo]

We still have false positives, when there is a (forward) symlink to a subdir. For example, given the following file tree:

testroot
├── child
│   └── foo2
├── foo
├── same-child -> child
└── unique

we have the following output:

error listing 'testroot/same-child': directory loop detected
testroot/child/foo2
testroot/foo
------------------------------
error: some files/directories could not be compared/indexed (see previous errors)

When in reality we should have output like this:

$ ./capidup testroot
testroot/child/foo2
testroot/same-child/foo2
testroot/foo
------------------------------

[israel-lugo]

We still have false positives. This, for example:

testroot/
├── child1
│   └── foo1
├── child2
│   ├── brother -> ../child1
│   └── foo2
├── foo0
└── unique

Produces a false positive when we enter child2/brother, as we've already visited child1:

$ ./capidup -L testroot
error listing 'testroot/child2/brother': directory loop detected
testroot/child1/foo1
testroot/child2/foo2
testroot/foo0
------------------------------
error: some files/directories could not be compared/indexed (see previous errors)

This isn't a loop. Compare e.g. with find:

$ find -L testroot
testroot
testroot/foo0
testroot/unique
testroot/child2
testroot/child2/brother
testroot/child2/brother/foo1
testroot/child2/foo2
testroot/child1
testroot/child1/foo1

Do we need to go and implement a graph and strongly connected components? :/