8012930: (fs) Eliminate recursion from FileTreeWalker
authoralanb
Tue, 23 Apr 2013 15:01:44 +0100
changeset 17170 9f33b89c7978
parent 17169 5e5039c3181d
child 17171 2b182642a97a
8012930: (fs) Eliminate recursion from FileTreeWalker Reviewed-by: chegar
jdk/src/share/classes/java/nio/file/FileTreeWalker.java
jdk/src/share/classes/java/nio/file/Files.java
jdk/test/java/nio/file/Files/walkFileTree/CreateFileTree.java
jdk/test/java/nio/file/Files/walkFileTree/MaxDepth.java
jdk/test/java/nio/file/Files/walkFileTree/SkipSiblings.java
jdk/test/java/nio/file/Files/walkFileTree/SkipSubtree.java
jdk/test/java/nio/file/Files/walkFileTree/TerminateWalk.java
jdk/test/java/nio/file/Files/walkFileTree/find.sh
jdk/test/java/nio/file/Files/walkFileTree/walk_file_tree.sh
--- a/jdk/src/share/classes/java/nio/file/FileTreeWalker.java	Mon Apr 22 13:37:07 2013 -0700
+++ b/jdk/src/share/classes/java/nio/file/FileTreeWalker.java	Tue Apr 23 15:01:44 2013 +0100
@@ -25,27 +25,147 @@
 
 package java.nio.file;
 
-import java.nio.file.attribute.*;
+import java.nio.file.attribute.BasicFileAttributes;
+import java.io.Closeable;
 import java.io.IOException;
-import java.util.*;
+import java.util.ArrayDeque;
+import java.util.Iterator;
+import java.util.Set;
 import sun.nio.fs.BasicFileAttributesHolder;
 
 /**
- * Simple file tree walker that works in a similar manner to nftw(3C).
+ * Walks a file tree, generating a sequence of events corresponding to the files
+ * in the tree.
+ *
+ * <pre>{@code
+ *     Path top = ...
+ *     Set<FileVisitOption> options = ...
+ *     int maxDepth = ...
+ *
+ *     try (FileTreeWalker walker = new FileTreeWalker(options, maxDepth)) {
+ *         FileTreeWalker.Event ev = walker.walk(top);
+ *         do {
+ *             process(ev);
+ *             ev = walker.next();
+ *         } while (ev != null);
+ *     }
+ * }</pre>
  *
  * @see Files#walkFileTree
  */
 
-class FileTreeWalker {
+class FileTreeWalker implements Closeable {
     private final boolean followLinks;
     private final LinkOption[] linkOptions;
-    private final FileVisitor<? super Path> visitor;
     private final int maxDepth;
+    private final ArrayDeque<DirectoryNode> stack = new ArrayDeque<>();
+    private boolean closed;
+
+    /**
+     * The element on the walking stack corresponding to a directory node.
+     */
+    private static class DirectoryNode {
+        private final Path dir;
+        private final Object key;
+        private final DirectoryStream<Path> stream;
+        private final Iterator<Path> iterator;
+        private boolean skipped;
+
+        DirectoryNode(Path dir, Object key, DirectoryStream<Path> stream) {
+            this.dir = dir;
+            this.key = key;
+            this.stream = stream;
+            this.iterator = stream.iterator();
+        }
+
+        Path directory() {
+            return dir;
+        }
+
+        Object key() {
+            return key;
+        }
+
+        DirectoryStream<Path> stream() {
+            return stream;
+        }
+
+        Iterator<Path> iterator() {
+            return iterator;
+        }
+
+        void skip() {
+            skipped = true;
+        }
+
+        boolean skipped() {
+            return skipped;
+        }
+    }
 
-    FileTreeWalker(Set<FileVisitOption> options,
-                   FileVisitor<? super Path> visitor,
-                   int maxDepth)
-    {
+    /**
+     * The event types.
+     */
+    static enum EventType {
+        /**
+         * Start of a directory
+         */
+        START_DIRECTORY,
+        /**
+         * End of a directory
+         */
+        END_DIRECTORY,
+        /**
+         * An entry in a directory
+         */
+        ENTRY;
+    }
+
+    /**
+     * Events returned by the {@link #walk} and {@link #next} methods.
+     */
+    static class Event {
+        private final EventType type;
+        private final Path file;
+        private final BasicFileAttributes attrs;
+        private final IOException ioe;
+
+        private Event(EventType type, Path file, BasicFileAttributes attrs, IOException ioe) {
+            this.type = type;
+            this.file = file;
+            this.attrs = attrs;
+            this.ioe = ioe;
+        }
+
+        Event(EventType type, Path file, BasicFileAttributes attrs) {
+            this(type, file, attrs, null);
+        }
+
+        Event(EventType type, Path file, IOException ioe) {
+            this(type, file, null, ioe);
+        }
+
+        EventType type() {
+            return type;
+        }
+
+        Path file() {
+            return file;
+        }
+
+        BasicFileAttributes attributes() {
+            return attrs;
+        }
+
+        IOException ioeException() {
+            return ioe;
+        }
+    }
+
+    /**
+     * Creates a {@code FileTreeWalker}.
+     */
+    FileTreeWalker(Set<FileVisitOption> options, int maxDepth) {
         boolean fl = false;
         for (FileVisitOption option: options) {
             // will throw NPE if options contains null
@@ -58,191 +178,236 @@
         this.followLinks = fl;
         this.linkOptions = (fl) ? new LinkOption[0] :
             new LinkOption[] { LinkOption.NOFOLLOW_LINKS };
-        this.visitor = visitor;
         this.maxDepth = maxDepth;
     }
 
     /**
-     * Walk file tree starting at the given file
+     * Returns the attributes of the given file, taking into account whether
+     * the walk is following sym links is not. The {@code canUseCached}
+     * argument determines whether this method can use cached attributes.
      */
-    void walk(Path start) throws IOException {
-        FileVisitResult result = walk(start,
-                                      0,
-                                      new ArrayList<AncestorDirectory>());
-        Objects.requireNonNull(result, "FileVisitor returned null");
-    }
-
-    /**
-     * @param   file
-     *          the directory to visit
-     * @param   depth
-     *          depth remaining
-     * @param   ancestors
-     *          use when cycle detection is enabled
-     */
-    private FileVisitResult walk(Path file,
-                                 int depth,
-                                 List<AncestorDirectory> ancestors)
+    private BasicFileAttributes getAttributes(Path file, boolean canUseCached)
         throws IOException
     {
         // if attributes are cached then use them if possible
-        BasicFileAttributes attrs = null;
-        if ((depth > 0) &&
+        if (canUseCached &&
             (file instanceof BasicFileAttributesHolder) &&
             (System.getSecurityManager() == null))
         {
             BasicFileAttributes cached = ((BasicFileAttributesHolder)file).get();
-            if (cached != null && (!followLinks || !cached.isSymbolicLink()))
-                attrs = cached;
-        }
-        IOException exc = null;
-
-        // attempt to get attributes of file. If fails and we are following
-        // links then a link target might not exist so get attributes of link
-        if (attrs == null) {
-            try {
-                try {
-                    attrs = Files.readAttributes(file, BasicFileAttributes.class, linkOptions);
-                } catch (IOException x1) {
-                    if (followLinks) {
-                        try {
-                            attrs = Files.readAttributes(file,
-                                                         BasicFileAttributes.class,
-                                                         LinkOption.NOFOLLOW_LINKS);
-                        } catch (IOException x2) {
-                            exc = x2;
-                        }
-                    } else {
-                        exc = x1;
-                    }
-                }
-            } catch (SecurityException x) {
-                // If access to starting file is denied then SecurityException
-                // is thrown, otherwise the file is ignored.
-                if (depth == 0)
-                    throw x;
-                return FileVisitResult.CONTINUE;
+            if (cached != null && (!followLinks || !cached.isSymbolicLink())) {
+                return cached;
             }
         }
 
-        // unable to get attributes of file
-        if (exc != null) {
-            return visitor.visitFileFailed(file, exc);
+        // attempt to get attributes of file. If fails and we are following
+        // links then a link target might not exist so get attributes of link
+        BasicFileAttributes attrs;
+        try {
+            attrs = Files.readAttributes(file, BasicFileAttributes.class, linkOptions);
+        } catch (IOException ioe) {
+            if (!followLinks)
+                throw ioe;
+
+            // attempt to get attrmptes without following links
+            attrs = Files.readAttributes(file,
+                                         BasicFileAttributes.class,
+                                         LinkOption.NOFOLLOW_LINKS);
+        }
+        return attrs;
+    }
+
+    /**
+     * Returns true if walking into the given directory would result in a
+     * file system loop/cycle.
+     */
+    private boolean wouldLoop(Path dir, Object key) {
+        // if this directory and ancestor has a file key then we compare
+        // them; otherwise we use less efficient isSameFile test.
+        for (DirectoryNode ancestor: stack) {
+            Object ancestorKey = ancestor.key();
+            if (key != null && ancestorKey != null) {
+                if (key.equals(ancestorKey)) {
+                    // cycle detected
+                    return true;
+                }
+            } else {
+                try {
+                    if (Files.isSameFile(dir, ancestor.directory())) {
+                        // cycle detected
+                        return true;
+                    }
+                } catch (IOException | SecurityException x) {
+                    // ignore
+                }
+            }
+        }
+        return false;
+    }
+
+    /**
+     * Visits the given file, returning the {@code Event} corresponding to that
+     * visit.
+     *
+     * The {@code ignoreSecurityException} parameter determines whether
+     * any SecurityException should be ignored or not. If a SecurityException
+     * is thrown, and is ignored, then this method returns {@code null} to
+     * mean that there is no event corresponding to a visit to the file.
+     *
+     * The {@code canUseCached} parameter determines whether cached attributes
+     * for the file can be used or not.
+     */
+    private Event visit(Path entry, boolean ignoreSecurityException, boolean canUseCached) {
+        // need the file attributes
+        BasicFileAttributes attrs;
+        try {
+            attrs = getAttributes(entry, canUseCached);
+        } catch (IOException ioe) {
+            return new Event(EventType.ENTRY, entry, ioe);
+        } catch (SecurityException se) {
+            if (ignoreSecurityException)
+                return null;
+            throw se;
         }
 
         // at maximum depth or file is not a directory
+        int depth = stack.size();
         if (depth >= maxDepth || !attrs.isDirectory()) {
-            return visitor.visitFile(file, attrs);
+            return new Event(EventType.ENTRY, entry, attrs);
         }
 
         // check for cycles when following links
-        if (followLinks) {
-            Object key = attrs.fileKey();
+        if (followLinks && wouldLoop(entry, attrs.fileKey())) {
+            return new Event(EventType.ENTRY, entry,
+                             new FileSystemLoopException(entry.toString()));
+        }
+
+        // file is a directory, attempt to open it
+        DirectoryStream<Path> stream = null;
+        try {
+            stream = Files.newDirectoryStream(entry);
+        } catch (IOException ioe) {
+            return new Event(EventType.ENTRY, entry, ioe);
+        } catch (SecurityException se) {
+            if (ignoreSecurityException)
+                return null;
+            throw se;
+        }
+
+        // push a directory node to the stack and return an event
+        stack.push(new DirectoryNode(entry, attrs.fileKey(), stream));
+        return new Event(EventType.START_DIRECTORY, entry, attrs);
+    }
+
 
-            // if this directory and ancestor has a file key then we compare
-            // them; otherwise we use less efficient isSameFile test.
-            for (AncestorDirectory ancestor: ancestors) {
-                Object ancestorKey = ancestor.fileKey();
-                if (key != null && ancestorKey != null) {
-                    if (key.equals(ancestorKey)) {
-                        // cycle detected
-                        return visitor.visitFileFailed(file,
-                            new FileSystemLoopException(file.toString()));
+    /**
+     * Start walking from the given file.
+     */
+    Event walk(Path file) {
+        if (closed)
+            throw new IllegalStateException("Closed");
+
+        Event ev = visit(file,
+                         false,   // ignoreSecurityException
+                         false);  // canUseCached
+        assert ev != null;
+        return ev;
+    }
+
+    /**
+     * Returns the next Event or {@code null} if there are no more events or
+     * the walker is closed.
+     */
+    Event next() {
+        DirectoryNode top = stack.peek();
+        if (top == null)
+            return null;      // stack is empty, we are done
+
+        // continue iteration of the directory at the top of the stack
+        Event ev;
+        do {
+            Path entry = null;
+            IOException ioe = null;
+
+            // get next entry in the directory
+            if (!top.skipped()) {
+                Iterator<Path> iterator = top.iterator();
+                try {
+                    if (iterator.hasNext()) {
+                        entry = iterator.next();
                     }
-                } else {
-                    boolean isSameFile = false;
-                    try {
-                        isSameFile = Files.isSameFile(file, ancestor.file());
-                    } catch (IOException x) {
-                        // ignore
-                    } catch (SecurityException x) {
-                        // ignore
-                    }
-                    if (isSameFile) {
-                        // cycle detected
-                        return visitor.visitFileFailed(file,
-                            new FileSystemLoopException(file.toString()));
-                    }
+                } catch (DirectoryIteratorException x) {
+                    ioe = x.getCause();
                 }
             }
 
-            ancestors.add(new AncestorDirectory(file, key));
-        }
-
-        // visit directory
-        try {
-            DirectoryStream<Path> stream = null;
-            FileVisitResult result;
-
-            // open the directory
-            try {
-                stream = Files.newDirectoryStream(file);
-            } catch (IOException x) {
-                return visitor.visitFileFailed(file, x);
-            } catch (SecurityException x) {
-                // ignore, as per spec
-                return FileVisitResult.CONTINUE;
+            // no next entry so close and pop directory, creating corresponding event
+            if (entry == null) {
+                try {
+                    top.stream().close();
+                } catch (IOException e) {
+                    if (ioe != null) {
+                        ioe = e;
+                    } else {
+                        ioe.addSuppressed(e);
+                    }
+                }
+                stack.pop();
+                return new Event(EventType.END_DIRECTORY, top.directory(), ioe);
             }
 
-            // the exception notified to the postVisitDirectory method
-            IOException ioe = null;
+            // visit the entry
+            ev = visit(entry,
+                       true,   // ignoreSecurityException
+                       true);  // canUseCached
 
-            // invoke preVisitDirectory and then visit each entry
-            try {
-                result = visitor.preVisitDirectory(file, attrs);
-                if (result != FileVisitResult.CONTINUE) {
-                    return result;
-                }
+        } while (ev == null);
 
-                try {
-                    for (Path entry: stream) {
-                        result = walk(entry, depth+1, ancestors);
-
-                        // returning null will cause NPE to be thrown
-                        if (result == null || result == FileVisitResult.TERMINATE)
-                            return result;
+        return ev;
+    }
 
-                        // skip remaining siblings in this directory
-                        if (result == FileVisitResult.SKIP_SIBLINGS)
-                            break;
-                    }
-                } catch (DirectoryIteratorException e) {
-                    // IOException will be notified to postVisitDirectory
-                    ioe = e.getCause();
-                }
-            } finally {
-                try {
-                    stream.close();
-                } catch (IOException e) {
-                    // IOException will be notified to postVisitDirectory
-                    if (ioe == null)
-                        ioe = e;
-                }
-            }
-
-            // invoke postVisitDirectory last
-            return visitor.postVisitDirectory(file, ioe);
-
-        } finally {
-            // remove key from trail if doing cycle detection
-            if (followLinks) {
-                ancestors.remove(ancestors.size()-1);
-            }
+    /**
+     * Pops the directory node that is the current top of the stack so that
+     * there are no more events for the directory (including no END_DIRECTORY)
+     * event. This method is a no-op if the stack is empty or the walker is
+     * closed.
+     */
+    void pop() {
+        if (!stack.isEmpty()) {
+            DirectoryNode node = stack.pop();
+            try {
+                node.stream().close();
+            } catch (IOException ignore) { }
         }
     }
 
-    private static class AncestorDirectory {
-        private final Path dir;
-        private final Object key;
-        AncestorDirectory(Path dir, Object key) {
-            this.dir = dir;
-            this.key = key;
+    /**
+     * Skips the remaining entries in the directory at the top of the stack.
+     * This method is a no-op if the stack is empty or the walker is closed.
+     */
+    void skipRemainingSiblings() {
+        if (!stack.isEmpty()) {
+            stack.peek().skip();
         }
-        Path file() {
-            return dir;
-        }
-        Object fileKey() {
-            return key;
+    }
+
+    /**
+     * Returns {@code true} if the walker is open.
+     */
+    boolean isOpen() {
+        return !closed;
+    }
+
+    /**
+     * Closes/pops all directories on the stack.
+     */
+    @Override
+    public void close() {
+        if (!closed) {
+            while (!stack.isEmpty()) {
+                pop();
+            }
+            closed = true;
         }
     }
 }
--- a/jdk/src/share/classes/java/nio/file/Files.java	Mon Apr 22 13:37:07 2013 -0700
+++ b/jdk/src/share/classes/java/nio/file/Files.java	Tue Apr 23 15:01:44 2013 +0100
@@ -2589,7 +2589,60 @@
     {
         if (maxDepth < 0)
             throw new IllegalArgumentException("'maxDepth' is negative");
-        new FileTreeWalker(options, visitor, maxDepth).walk(start);
+
+        /**
+         * Create a FileTreeWalker to walk the file tree, invoking the visitor
+         * for each event.
+         */
+        try (FileTreeWalker walker = new FileTreeWalker(options, maxDepth)) {
+            FileTreeWalker.Event ev = walker.walk(start);
+            do {
+                FileVisitResult result;
+                switch (ev.type()) {
+                    case ENTRY :
+                        IOException ioe = ev.ioeException();
+                        if (ioe == null) {
+                            assert ev.attributes() != null;
+                            result = visitor.visitFile(ev.file(), ev.attributes());
+                        } else {
+                            result = visitor.visitFileFailed(ev.file(), ioe);
+                        }
+                        break;
+
+                    case START_DIRECTORY :
+                        result = visitor.preVisitDirectory(ev.file(), ev.attributes());
+
+                        // if SKIP_SIBLINGS and SKIP_SUBTREE is returned then
+                        // there shouldn't be any more events for the current
+                        // directory.
+                        if (result == FileVisitResult.SKIP_SUBTREE ||
+                            result == FileVisitResult.SKIP_SIBLINGS)
+                            walker.pop();
+                        break;
+
+                    case END_DIRECTORY :
+                        result = visitor.postVisitDirectory(ev.file(), ev.ioeException());
+
+                        // SKIP_SIBLINGS is a no-op for postVisitDirectory
+                        if (result == FileVisitResult.SKIP_SIBLINGS)
+                            result = FileVisitResult.CONTINUE;
+                        break;
+
+                    default :
+                        throw new AssertionError("Should not get here");
+                }
+
+                if (Objects.requireNonNull(result) != FileVisitResult.CONTINUE) {
+                    if (result == FileVisitResult.TERMINATE) {
+                        break;
+                    } else if (result == FileVisitResult.SKIP_SIBLINGS) {
+                        walker.skipRemainingSiblings();
+                    }
+                }
+                ev = walker.next();
+            } while (ev != null);
+        }
+
         return start;
     }
 
--- a/jdk/test/java/nio/file/Files/walkFileTree/CreateFileTree.java	Mon Apr 22 13:37:07 2013 -0700
+++ b/jdk/test/java/nio/file/Files/walkFileTree/CreateFileTree.java	Tue Apr 23 15:01:44 2013 +0100
@@ -32,9 +32,23 @@
 
 public class CreateFileTree {
 
-    static final Random rand = new Random();
+    private static final Random rand = new Random();
 
-    public static void main(String[] args) throws IOException {
+    private static boolean supportsLinks(Path dir) {
+        Path link = dir.resolve("testlink");
+        Path target = dir.resolve("testtarget");
+        try {
+            Files.createSymbolicLink(link, target);
+            Files.delete(link);
+            return true;
+        } catch (UnsupportedOperationException x) {
+            return false;
+        } catch (IOException x) {
+            return false;
+        }
+    }
+
+    static Path create() throws IOException {
         Path top = Files.createTempDirectory("tree");
         List<Path> dirs = new ArrayList<Path>();
 
@@ -53,7 +67,6 @@
                 dirs.add(subdir);
             }
         }
-        assert dirs.size() >= 2;
 
         // create a few regular files in the file tree
         int files = dirs.size() * 3;
@@ -64,20 +77,26 @@
         }
 
         // create a few sym links in the file tree so as to create cycles
-        int links = 1 + rand.nextInt(5);
-        for (int i=0; i<links; i++) {
-            int x = rand.nextInt(dirs.size());
-            int y;
-            do {
-                y = rand.nextInt(dirs.size());
-            } while (y != x);
-            String name = "link" + (i+1);
-            Path link = dirs.get(x).resolve(name);
-            Path target = dirs.get(y);
-            Files.createSymbolicLink(link, target);
+        if (supportsLinks(top)) {
+            int links = 1 + rand.nextInt(5);
+            for (int i=0; i<links; i++) {
+                int x = rand.nextInt(dirs.size());
+                int y;
+                do {
+                    y = rand.nextInt(dirs.size());
+                } while (y != x);
+                String name = "link" + (i+1);
+                Path link = dirs.get(x).resolve(name);
+                Path target = dirs.get(y);
+                Files.createSymbolicLink(link, target);
+            }
         }
 
-        // done
+         return top;
+    }
+
+    public static void main(String[] args) throws IOException {
+        Path top = create();
         System.out.println(top);
     }
 }
--- a/jdk/test/java/nio/file/Files/walkFileTree/MaxDepth.java	Mon Apr 22 13:37:07 2013 -0700
+++ b/jdk/test/java/nio/file/Files/walkFileTree/MaxDepth.java	Tue Apr 23 15:01:44 2013 +0100
@@ -21,18 +21,21 @@
  * questions.
  */
 
+/*
+ * @test
+ * @summary Unit test for Files.walkFileTree to test maxDepth parameter
+ * @compile MaxDepth.java CreateFileTree.java
+ * @run main MaxDepth
+ */
+
 import java.nio.file.*;
 import java.nio.file.attribute.*;
 import java.io.IOException;
 import java.util.*;
 
-/**
- * Unit test for Files.walkFileTree to test maxDepth parameter
- */
-
 public class MaxDepth {
     public static void main(String[] args) throws Exception {
-        final Path top = Paths.get(args[0]);
+        final Path top = CreateFileTree.create();
 
         for (int i=0; i<5; i++) {
             Set<FileVisitOption> opts = Collections.emptySet();
--- a/jdk/test/java/nio/file/Files/walkFileTree/SkipSiblings.java	Mon Apr 22 13:37:07 2013 -0700
+++ b/jdk/test/java/nio/file/Files/walkFileTree/SkipSiblings.java	Tue Apr 23 15:01:44 2013 +0100
@@ -21,15 +21,18 @@
  * questions.
  */
 
+/*
+ * @test
+ * @summary Unit test for Files.walkFileTree to test SKIP_SIBLINGS return value
+ * @compile SkipSiblings.java CreateFileTree.java
+ * @run main SkipSiblings
+ */
+
 import java.nio.file.*;
 import java.nio.file.attribute.*;
 import java.io.IOException;
 import java.util.*;
 
-/**
- * Unit test for Files.walkFileTree to test SKIP_SIBLINGS return value.
- */
-
 public class SkipSiblings {
 
     static final Random rand = new Random();
@@ -52,7 +55,7 @@
     }
 
     public static void main(String[] args) throws Exception {
-        Path dir = Paths.get(args[0]);
+        Path dir = CreateFileTree.create();
 
         Files.walkFileTree(dir, new SimpleFileVisitor<Path>() {
             @Override
@@ -74,7 +77,11 @@
                 if (x != null)
                     throw new RuntimeException(x);
                 check(dir);
-                return FileVisitResult.CONTINUE;
+                if (rand.nextBoolean()) {
+                    return FileVisitResult.CONTINUE;
+                } else {
+                    return FileVisitResult.SKIP_SIBLINGS;
+                }
             }
         });
     }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/nio/file/Files/walkFileTree/SkipSubtree.java	Tue Apr 23 15:01:44 2013 +0100
@@ -0,0 +1,85 @@
+/*
+ * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @summary Unit test for Files.walkFileTree to test SKIP_SUBTREE return value
+ * @compile SkipSubtree.java CreateFileTree.java
+ * @run main SkipSubtree
+ */
+import java.nio.file.*;
+import java.nio.file.attribute.BasicFileAttributes;
+import java.io.IOException;
+import java.util.HashSet;
+import java.util.Random;
+import java.util.Set;
+
+public class SkipSubtree {
+
+    static final Random rand = new Random();
+    static final Set<Path> skipped = new HashSet<>();
+
+    // check if this path should have been skipped
+    static void check(Path path) {
+        do {
+            if (skipped.contains(path))
+                throw new RuntimeException(path + " should not have been visited");
+            path = path.getParent();
+        } while (path != null);
+    }
+
+    // indicates if the subtree should be skipped
+    static boolean skip(Path path) {
+        if (rand.nextInt(3) == 0) {
+            skipped.add(path);
+            return true;
+        }
+        return false;
+    }
+
+    public static void main(String[] args) throws Exception {
+        Path dir = CreateFileTree.create();
+
+        Files.walkFileTree(dir, new SimpleFileVisitor<Path>() {
+            @Override
+            public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) {
+                check(dir);
+                if (skip(dir))
+                    return FileVisitResult.SKIP_SUBTREE;
+                return FileVisitResult.CONTINUE;
+            }
+            @Override
+            public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) {
+                check(file);
+                return FileVisitResult.CONTINUE;
+            }
+            @Override
+            public FileVisitResult postVisitDirectory(Path dir, IOException x) {
+                if (x != null)
+                    throw new RuntimeException(x);
+                check(dir);
+                return FileVisitResult.CONTINUE;
+            }
+        });
+    }
+}
--- a/jdk/test/java/nio/file/Files/walkFileTree/TerminateWalk.java	Mon Apr 22 13:37:07 2013 -0700
+++ b/jdk/test/java/nio/file/Files/walkFileTree/TerminateWalk.java	Tue Apr 23 15:01:44 2013 +0100
@@ -21,15 +21,18 @@
  * questions.
  */
 
+/*
+ * @test
+ * @summary Unit test for Files.walkFileTree to test TERMINATE return value
+ * @compile TerminateWalk.java CreateFileTree.java
+ * @run main TerminateWalk
+ */
+
 import java.nio.file.*;
 import java.nio.file.attribute.*;
 import java.io.IOException;
 import java.util.*;
 
-/**
- * Unit test for Files.walkFileTree to test TERMINATE return value
- */
-
 public class TerminateWalk {
 
     static final Random rand = new Random();
@@ -47,7 +50,7 @@
     }
 
     public static void main(String[] args) throws Exception {
-        Path dir = Paths.get(args[0]);
+        Path dir = CreateFileTree.create();
 
         Files.walkFileTree(dir, new SimpleFileVisitor<Path>() {
             @Override
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/nio/file/Files/walkFileTree/find.sh	Tue Apr 23 15:01:44 2013 +0100
@@ -0,0 +1,86 @@
+#
+# Copyright (c) 2008, 2011, Oracle and/or its affiliates. All rights reserved.
+# DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+#
+# This code is free software; you can redistribute it and/or modify it
+# under the terms of the GNU General Public License version 2 only, as
+# published by the Free Software Foundation.
+#
+# This code is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+# FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+# version 2 for more details (a copy is included in the LICENSE file that
+# accompanied this code).
+#
+# You should have received a copy of the GNU General Public License version
+# 2 along with this work; if not, write to the Free Software Foundation,
+# Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+#
+# Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+# or visit www.oracle.com if you need additional information or have any
+# questions.
+#
+
+# @test
+# @bug 4313887 6907737
+# @summary Tests that walkFileTree is consistent with the native find program
+# @build CreateFileTree PrintFileTree
+# @run shell find.sh
+
+# if TESTJAVA isn't set then we assume an interactive run.
+
+if [ -z "$TESTJAVA" ]; then
+    TESTSRC=.
+    TESTCLASSES=.
+    JAVA=java
+else
+    JAVA="${TESTJAVA}/bin/java"
+fi
+
+OS=`uname -s`
+case "$OS" in
+    Windows_* | CYGWIN* )
+        echo "This test does not run on Windows" 
+        exit 0
+        ;;
+    * )
+        CLASSPATH=${TESTCLASSES}:${TESTSRC}
+        ;;
+esac
+export CLASSPATH
+
+# create the file tree
+ROOT=`$JAVA CreateFileTree`
+if [ $? != 0 ]; then exit 1; fi
+
+failures=0
+
+# print the file tree and compare output with find(1)
+$JAVA ${TESTVMOPTS} PrintFileTree "$ROOT" > out1
+find "$ROOT" > out2
+diff out1 out2
+if [ $? != 0 ]; then failures=`expr $failures + 1`; fi
+
+# repeat test following links. Some versions of find(1) output
+# cycles (sym links to ancestor directories), other versions do
+# not. For that reason we run PrintFileTree with the -printCycles
+# option when the output without this option differs to find(1).
+find "$ROOT" -follow > out1
+$JAVA ${TESTVMOPTS} PrintFileTree -follow "$ROOT" > out2
+diff out1 out2
+if [ $? != 0 ];
+  then 
+    # re-run printing cycles to stdout
+    $JAVA ${TESTVMOPTS} PrintFileTree -follow -printCycles "$ROOT" > out2
+    diff out1 out2
+    if [ $? != 0 ]; then failures=`expr $failures + 1`; fi
+  fi
+
+# clean-up
+rm -r "$ROOT"
+
+echo ''
+if [ $failures -gt 0 ];
+  then echo "$failures test(s) failed";
+  else echo "Test passed"; fi
+exit $failures
--- a/jdk/test/java/nio/file/Files/walkFileTree/walk_file_tree.sh	Mon Apr 22 13:37:07 2013 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,98 +0,0 @@
-#
-# Copyright (c) 2008, 2011, Oracle and/or its affiliates. All rights reserved.
-# DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
-#
-# This code is free software; you can redistribute it and/or modify it
-# under the terms of the GNU General Public License version 2 only, as
-# published by the Free Software Foundation.
-#
-# This code is distributed in the hope that it will be useful, but WITHOUT
-# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
-# FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
-# version 2 for more details (a copy is included in the LICENSE file that
-# accompanied this code).
-#
-# You should have received a copy of the GNU General Public License version
-# 2 along with this work; if not, write to the Free Software Foundation,
-# Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
-#
-# Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
-# or visit www.oracle.com if you need additional information or have any
-# questions.
-#
-
-# @test
-# @bug 4313887 6907737
-# @summary Unit test for walkFileTree method
-# @build CreateFileTree PrintFileTree SkipSiblings TerminateWalk MaxDepth
-# @run shell walk_file_tree.sh
-
-# if TESTJAVA isn't set then we assume an interactive run.
-
-if [ -z "$TESTJAVA" ]; then
-    TESTSRC=.
-    TESTCLASSES=.
-    JAVA=java
-else
-    JAVA="${TESTJAVA}/bin/java"
-fi
-
-OS=`uname -s`
-case "$OS" in
-    Windows_* | CYGWIN* )
-        echo "This test does not run on Windows" 
-        exit 0
-        ;;
-    * )
-        CLASSPATH=${TESTCLASSES}:${TESTSRC}
-        ;;
-esac
-export CLASSPATH
-
-# create the file tree
-ROOT=`$JAVA CreateFileTree`
-if [ $? != 0 ]; then exit 1; fi
-
-failures=0
-
-# print the file tree and compare output with find(1)
-$JAVA ${TESTVMOPTS} PrintFileTree "$ROOT" > out1
-find "$ROOT" > out2
-diff out1 out2
-if [ $? != 0 ]; then failures=`expr $failures + 1`; fi
-
-# repeat test following links. Some versions of find(1) output
-# cycles (sym links to ancestor directories), other versions do
-# not. For that reason we run PrintFileTree with the -printCycles
-# option when the output without this option differs to find(1).
-find "$ROOT" -follow > out1
-$JAVA ${TESTVMOPTS} PrintFileTree -follow "$ROOT" > out2
-diff out1 out2
-if [ $? != 0 ];
-  then 
-    # re-run printing cycles to stdout
-    $JAVA ${TESTVMOPTS} PrintFileTree -follow -printCycles "$ROOT" > out2
-    diff out1 out2
-    if [ $? != 0 ]; then failures=`expr $failures + 1`; fi
-  fi
-
-# test SKIP_SIBLINGS
-$JAVA ${TESTVMOPTS} SkipSiblings "$ROOT"
-if [ $? != 0 ]; then failures=`expr $failures + 1`; fi
-
-# test TERMINATE
-$JAVA ${TESTVMOPTS} TerminateWalk "$ROOT"
-if [ $? != 0 ]; then failures=`expr $failures + 1`; fi
-
-# test maxDepth
-$JAVA ${TESTVMOPTS} MaxDepth "$ROOT"
-if [ $? != 0 ]; then failures=`expr $failures + 1`; fi
-
-# clean-up
-rm -r "$ROOT"
-
-echo ''
-if [ $failures -gt 0 ];
-  then echo "$failures test(s) failed";
-  else echo "Test passed"; fi
-exit $failures