Walk a tree and return a sequence of (directory, dotdir) pairs.

def find_repositories_by_walking_and_following_symlinks(path):
    """Walk a tree and return a sequence of (directory, dotdir) pairs."""
    repos = []

    # This is for detecting symlink loops and escaping them. This is similar to
    # http://stackoverflow.com/questions/36977259/avoiding-infinite-recursion-with-os-walk/36977656#36977656
    def inode(path):
        stats = os.stat(path)
        return stats.st_dev, stats.st_ino
    seen_inodes = {inode(path)}

    for dirpath, dirnames, filenames in os.walk(path, followlinks=True):
        inodes = [inode(os.path.join(dirpath, p)) for p in dirnames]
        dirnames[:] = [p for p, i in zip(dirnames, inodes)
                       if not i in seen_inodes]
        seen_inodes.update(inodes)

        for dotdir in set(dirnames) & DOTDIRS:
            repos.append((dirpath, dotdir))
    return repos