9
\$\begingroup\$

Given the path to a filesystem directory, the task is to delete all empty directories within that root directory. After the process is finished, no empty dir should exist under the root directory (the root should also be deleted if it ends up empty). Examples (the d prefix means it's a directory):

       dA                             dA
      /  \                           /
     dB   dC          =====>        dB
    /       \                       / 
  1.txt      dE                  1.txt
       dA                          (empty dir)
      /  \                          
     dB   dC          =====>       
    /    /  \                      
   dE   dF  dH 

The idea is to do DFS. Reaching a node for the second time during backtracking, check if the directory is empty and delete it if needed. Java code:

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.io.File;
import java.io.IOException;

public class CleanupProcessor {

    private static final Logger logger = LoggerFactory.getLogger(CleanupProcessor.class);

    public void cleanupDirectory(String path) {
        File root = new File(path);
        if (!root.exists()) {
            logger.error("Directory {} doesn't exist", root.getAbsolutePath());
            return;
        }
        if (!root.isDirectory()) {
            logger.error("{} is not a directory", root.getAbsolutePath());
            return;
        }
        cleanupHelper(root);
    }

    private void cleanupHelper(File dir) {
        if (!dir.isDirectory()) {
            logger.info("Found non-directory file {}", dir.getAbsolutePath());
            return;
        }

        File[] children = dir.listFiles();
        if (children == null) {
            logger.error("Could not read contents of {}", dir.getAbsolutePath());
            return;
        }
        for (File f: children) {
            cleanupHelper(f);
        }

        children = dir.listFiles();
        if (children == null) {
            logger.error("Could not read contents of {}", dir.getAbsolutePath());
            return;
        }
        if (children.length == 0) {
            try {
                FileUtils.deleteDirectory(dir);
            } catch (IOException e) {
                logger.error("Could not delete directory {}", dir.getAbsolutePath(), e);
            }
        }
    }
}

Do you see any mistake/something that could go wrong with this code? Thanks in advance.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Have a look at java.nio.file.Files which can handle symlinks properly. \$\endgroup\$
    – morgwai
    Commented Feb 12 at 20:44

3 Answers 3

4
\$\begingroup\$

You're using an actual logger - that's good. However, for the errors that appear in cleanupDirectory, it's probably a better idea to throw an exception. The caller should decide whether to leave these as fatal or catch and log them.

You should move from the old File API to the nio API. Among other reasons, it removes null-signalling and uses proper exceptions.

There's some risk that your recursive implementation will blow the stack. Through accident or evil, your program could be given a very deep directory tree. For that reason, Files.find() accepts an explicit maximum depth, and takes care of the recursion for you, which is safer.

As with all operations of this kind, it's highly valuable to be able to perform a dry-run that doesn't actually delete anything, and your current code can't do that. It should. However, adding this functionality is not entirely straightforward with this problem.

There are many different approaches - an iterator, a stream, callbacks, etc. I demonstrate with a recursion-free algorithm that uses a Spliterator with a queue to simplify the work of passing results to the caller. It isn't particularly efficient - it builds up a partial tree in memory as a map of sets - but it does work, and should serve as inspiration for you.

package com.stackexchange;

import java.io.IOException;
import java.nio.file.DirectoryStream;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.attribute.BasicFileAttributes;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.Spliterator;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public class Main {
    public static class CleanupProcessor {
        public final Path root;
        public final int maxDepth;

        public CleanupProcessor(String root) {
            this(Path.of(root), 50);
        }

        public CleanupProcessor(Path root, int maxDepth) {
            this.root = root;
            this.maxDepth = maxDepth;
        }

        public void deleteAll() throws IOException {
            paths().forEach(CleanupProcessor::uncheckedDelete);
        }

        private static void uncheckedDelete(Path path) {
            try {
                Files.delete(path);
            } catch (IOException cause) {
                throw new RuntimeException(cause);
            }
        }

        public Stream<Path> paths() throws IOException {
            return StreamSupport.stream(new CleanSpliterator(), false);
        }

        private class CleanSpliterator implements Spliterator<Path> {
            private final Map<Path, Set<Path>> tree;
            private final Set<Path> deleted = new HashSet<>();
            private final Queue<Path> emit = new ArrayDeque<>();

            public CleanSpliterator() throws IOException {
                // Skips symlinks
                try (Stream<Path> search = Files.find(
                    root, maxDepth, CleanSpliterator::dirWithNoFiles
                )) {
                    tree = search.collect(Collectors.toMap(
                        Function.identity(), CleanSpliterator::treeInit
                    ));
                }
            }

            private static boolean dirWithNoFiles(Path path, BasicFileAttributes attrs) {
                if (!attrs.isDirectory())
                    return false;

                // If the directory has any non-subdirectory files, ignore it
                try (
                    DirectoryStream<Path> dir = Files.newDirectoryStream(
                        path, p -> !Files.isDirectory((p))
                    )
                ) {
                    return !dir.iterator().hasNext();
                } catch (IOException ex) {
                    throw new RuntimeException(ex);
                }
            }

            private static Set<Path> treeInit(Path path) {
                // Add all subdirectories to the mapped set
                try (
                    DirectoryStream<Path> dir = Files.newDirectoryStream(path, Files::isDirectory)
                ) {
                    return StreamSupport.stream(
                        dir.spliterator(), false
                    ).collect(Collectors.toUnmodifiableSet());
                } catch (IOException ex) {
                    throw new RuntimeException(ex);
                }
            }

            private void advance() {
                Set<Path> transfer = new LinkedHashSet<>();

                for (Map.Entry<Path, Set<Path>> kv: tree.entrySet()) {
                    // The set of deleted directories entirely includes the children of
                    // this directory, so schedule it for deletion
                    if (deleted.containsAll(kv.getValue()))
                        transfer.add(kv.getKey());
                }

                // If there are no results, clear the tree to signal to the spliterator that it's done
                if (transfer.isEmpty())
                    tree.clear();
                else {
                    // Queue to emit from the spliterator
                    emit.addAll(transfer);
                    // Add to the deleted set to change the results on the next call
                    deleted.addAll(transfer);
                    // Reduce the iteration load on the next call, or even prevent the next call
                    // if every directory has been emitted
                    for (Path transferred: transfer)
                        tree.remove(transferred);
                }
            }

            @Override
            public int characteristics() {
                return ORDERED | DISTINCT | NONNULL;
            }
            @Override
            public long estimateSize() {
                // Wild guess: 50% of the remaining dirs will be empty
                return tree.size() / 2;
            }

            @Override
            public boolean tryAdvance(Consumer<? super Path> action) {
                if (emit.isEmpty()) {
                    if (tree.isEmpty())
                        return false;
                    advance();
                    if (emit.isEmpty())
                        return false;
                }
                action.accept(emit.remove());
                return true;
            }

            @Override
            public Spliterator<Path> trySplit() {
                // There are ways to parallel-split this algorithm, but they aren't shown here to
                // promote simplicity
                return null;
            }
        }
    }

    public static void main(String[] args) {
        CleanupProcessor proc = new CleanupProcessor(".");

        // Dryrun only
        try {
            proc.paths().forEach(System.out::println);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

When run on the current project's directory, it produces sensible results for the following (initially and eventually) empty directories:

.\src\main\resources
.\src\test\resources
.\build\generated\sources\headers\java\main
.\src\test\java
.\.gradle\8.4\vcsMetadata
.\build\generated\sources\annotationProcessor\java\main
.\build\tmp\compileJava\compileTransaction\backup-dir
.\src\test
.\build\generated\sources\annotationProcessor\java
.\build\generated\sources\headers\java
.\build\generated\sources\headers
.\build\generated\sources\annotationProcessor
.\build\generated\sources
.\build\generated
\$\endgroup\$
4
\$\begingroup\$

The nio call Files.walkFileTree provides a much easier way to scan a directory tree using FileVisitor and has callbacks for each file and pre/post directory.

All you need to do is setup and increment counters when visiting pre-directory or file, and check for counter == 0 in post directory. This example will print the names of directories that would get deleted because they are, or will be empty. Change doDelete = true to delete them.

public class PruneTree extends SimpleFileVisitor<Path> {
    // Take care before setting doDelete = true
    private boolean doDelete = false;
    private int deletes;
    private final LinkedList<AtomicInteger> contentSize = new LinkedList<>(List.of(new AtomicInteger()));

    @Override
    public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) throws IOException {
        // Modify parent counter:
        contentSize.getLast().incrementAndGet();
        return FileVisitResult.CONTINUE;
    }

    @Override
    public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) throws IOException {
        // Modify parent counter:
        contentSize.getLast().incrementAndGet();

        // Setup a counter for this directory
        contentSize.add(new AtomicInteger());

        return FileVisitResult.CONTINUE;
    }

    @Override
    public FileVisitResult postVisitDirectory(Path dir, IOException exc) throws IOException {
        // Remove and check counter for this directory
        if (contentSize.removeLast().get() == 0) {
            // Can delete this dir:
            deletes++;
            System.out.println("RMDIR #"+deletes+" "+dir);

            // Fix parent count:
            contentSize.getLast().decrementAndGet();

            if (doDelete)  {
                Files.delete(dir);
            }
        }
        return FileVisitResult.CONTINUE;
    }

    /**
     * Example prune tree.
     * Note that Files.walkFileTree accepts both file and dirs
     */
    public static void main(String[] args) throws IOException
    {
        for (Path src : Arrays.stream(args).map(Path::of).toList()) {
            Files.walkFileTree(src, new PruneTree());
        }
    }
}
\$\endgroup\$
3
\$\begingroup\$

You're not taking into account loops created by symbolic links. This may not be a problem to your use case but in a generic case it will lead to a stack overflow error. A quick but a bit dirty fix would be to add a recursion depth limit parameter (which is always a good idea).

The cleanupHelper could have a more descriptive name. Perhaps recursiveDelete?

Returning error result via a log file is a code smell. Either return an result that indicates success/failure or let the exception propagate. At the moment a non-empty directory and a failed delete look exactly the same to the caller.

Logging the existence of a regular file on info level is log spamming. That is a normal and expected occurrence and absolutely not worth a log statement. If you are using logging statements as a substitute for a debugger, you should try to avoid that and learn to use an IDE with a debugger.

The algorithm could be simplified if you return a boolean from recursiveDelete denoting if the directory was deleted when the method returned. This also lets you handle the file delete failure gracefully by returning false.

private boolean recursiveDelete(File directory) {
    boolean canDelete = true;
    for (File file : directory.listFiles()) {
        if (! file.isDirectory() || ! recursiveDelete(file)) {
            canDelete = false;
        }
    }

    return canDelete && directory.delete();
}

And just for the sake of shaming the generic programming languages, here is how it is done from the command line: find folderToDelete -type d -empty -delete

\$\endgroup\$
1
  • 3
    \$\begingroup\$ related: java.nio.file.Files can handle symlinks properly. \$\endgroup\$
    – morgwai
    Commented Feb 12 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.