1 /*
   2  * Copyright (c) 2007, 2012, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.nio.file;
  27 
  28 import java.nio.file.attribute.BasicFileAttributes;
  29 import java.io.Closeable;
  30 import java.io.IOException;
  31 import java.util.ArrayDeque;
  32 import java.util.Collection;
  33 import java.util.Iterator;
  34 import sun.nio.fs.BasicFileAttributesHolder;
  35 
  36 /**
  37  * Walks a file tree, generating a sequence of events corresponding to the files
  38  * in the tree.
  39  *
  40  * <pre>{@code
  41  *     Path top = ...
  42  *     Set<FileVisitOption> options = ...
  43  *     int maxDepth = ...
  44  *
  45  *     try (FileTreeWalker walker = new FileTreeWalker(options, maxDepth)) {
  46  *         FileTreeWalker.Event ev = walker.walk(top);
  47  *         do {
  48  *             process(ev);
  49  *             ev = walker.next();
  50  *         } while (ev != null);
  51  *     }
  52  * }</pre>
  53  *
  54  * @see Files#walkFileTree
  55  */
  56 
  57 class FileTreeWalker implements Closeable {
  58     private final boolean followLinks;
  59     private final LinkOption[] linkOptions;
  60     private final int maxDepth;
  61     private final ArrayDeque<DirectoryNode> stack = new ArrayDeque<>();
  62     private boolean closed;
  63 
  64     /**
  65      * The element on the walking stack corresponding to a directory node.
  66      */
  67     private static class DirectoryNode {
  68         private final Path dir;
  69         private final Object key;
  70         private final DirectoryStream<Path> stream;
  71         private final Iterator<Path> iterator;
  72         private boolean skipped;
  73 
  74         DirectoryNode(Path dir, Object key, DirectoryStream<Path> stream) {
  75             this.dir = dir;
  76             this.key = key;
  77             this.stream = stream;
  78             this.iterator = stream.iterator();
  79         }
  80 
  81         Path directory() {
  82             return dir;
  83         }
  84 
  85         Object key() {
  86             return key;
  87         }
  88 
  89         DirectoryStream<Path> stream() {
  90             return stream;
  91         }
  92 
  93         Iterator<Path> iterator() {
  94             return iterator;
  95         }
  96 
  97         void skip() {
  98             skipped = true;
  99         }
 100 
 101         boolean skipped() {
 102             return skipped;
 103         }
 104     }
 105 
 106     /**
 107      * The event types.
 108      */
 109     static enum EventType {
 110         /**
 111          * Start of a directory
 112          */
 113         START_DIRECTORY,
 114         /**
 115          * End of a directory
 116          */
 117         END_DIRECTORY,
 118         /**
 119          * An entry in a directory
 120          */
 121         ENTRY;
 122     }
 123 
 124     /**
 125      * Events returned by the {@link #walk} and {@link #next} methods.
 126      */
 127     static class Event {
 128         private final EventType type;
 129         private final Path file;
 130         private final BasicFileAttributes attrs;
 131         private final IOException ioe;
 132 
 133         private Event(EventType type, Path file, BasicFileAttributes attrs, IOException ioe) {
 134             this.type = type;
 135             this.file = file;
 136             this.attrs = attrs;
 137             this.ioe = ioe;
 138         }
 139 
 140         Event(EventType type, Path file, BasicFileAttributes attrs) {
 141             this(type, file, attrs, null);
 142         }
 143 
 144         Event(EventType type, Path file, IOException ioe) {
 145             this(type, file, null, ioe);
 146         }
 147 
 148         EventType type() {
 149             return type;
 150         }
 151 
 152         Path file() {
 153             return file;
 154         }
 155 
 156         BasicFileAttributes attributes() {
 157             return attrs;
 158         }
 159 
 160         IOException ioeException() {
 161             return ioe;
 162         }
 163     }
 164 
 165     /**
 166      * Creates a {@code FileTreeWalker}.
 167      *
 168      * @throws  IllegalArgumentException
 169      *          if {@code maxDepth} is negative
 170      * @throws  ClassCastException
 171      *          if (@code options} contains an element that is not a
 172      *          {@code FileVisitOption}
 173      * @throws  NullPointerException
 174      *          if {@code options} is {@ocde null} or the options
 175      *          array contains a {@code null} element
 176      */
 177     FileTreeWalker(Collection<FileVisitOption> options, int maxDepth) {
 178         boolean fl = false;
 179         for (FileVisitOption option: options) {
 180             // will throw NPE if options contains null
 181             switch (option) {
 182                 case FOLLOW_LINKS : fl = true; break;
 183                 default:
 184                     throw new AssertionError("Should not get here");
 185             }
 186         }
 187         if (maxDepth < 0)
 188             throw new IllegalArgumentException("'maxDepth' is negative");
 189 
 190         this.followLinks = fl;
 191         this.linkOptions = (fl) ? new LinkOption[0] :
 192             new LinkOption[] { LinkOption.NOFOLLOW_LINKS };
 193         this.maxDepth = maxDepth;
 194     }
 195 
 196     /**
 197      * Returns the attributes of the given file, taking into account whether
 198      * the walk is following sym links is not. The {@code canUseCached}
 199      * argument determines whether this method can use cached attributes.
 200      */
 201     private BasicFileAttributes getAttributes(Path file, boolean canUseCached)
 202         throws IOException
 203     {
 204         // if attributes are cached then use them if possible
 205         if (canUseCached &&
 206             (file instanceof BasicFileAttributesHolder) &&
 207             (System.getSecurityManager() == null))
 208         {
 209             BasicFileAttributes cached = ((BasicFileAttributesHolder)file).get();
 210             if (cached != null && (!followLinks || !cached.isSymbolicLink())) {
 211                 return cached;
 212             }
 213         }
 214 
 215         // attempt to get attributes of file. If fails and we are following
 216         // links then a link target might not exist so get attributes of link
 217         BasicFileAttributes attrs;
 218         try {
 219             attrs = Files.readAttributes(file, BasicFileAttributes.class, linkOptions);
 220         } catch (IOException ioe) {
 221             if (!followLinks)
 222                 throw ioe;
 223 
 224             // attempt to get attrmptes without following links
 225             attrs = Files.readAttributes(file,
 226                                          BasicFileAttributes.class,
 227                                          LinkOption.NOFOLLOW_LINKS);
 228         }
 229         return attrs;
 230     }
 231 
 232     /**
 233      * Returns true if walking into the given directory would result in a
 234      * file system loop/cycle.
 235      */
 236     private boolean wouldLoop(Path dir, Object key) {
 237         // if this directory and ancestor has a file key then we compare
 238         // them; otherwise we use less efficient isSameFile test.
 239         for (DirectoryNode ancestor: stack) {
 240             Object ancestorKey = ancestor.key();
 241             if (key != null && ancestorKey != null) {
 242                 if (key.equals(ancestorKey)) {
 243                     // cycle detected
 244                     return true;
 245                 }
 246             } else {
 247                 try {
 248                     if (Files.isSameFile(dir, ancestor.directory())) {
 249                         // cycle detected
 250                         return true;
 251                     }
 252                 } catch (IOException | SecurityException x) {
 253                     // ignore
 254                 }
 255             }
 256         }
 257         return false;
 258     }
 259 
 260     /**
 261      * Visits the given file, returning the {@code Event} corresponding to that
 262      * visit.
 263      *
 264      * The {@code ignoreSecurityException} parameter determines whether
 265      * any SecurityException should be ignored or not. If a SecurityException
 266      * is thrown, and is ignored, then this method returns {@code null} to
 267      * mean that there is no event corresponding to a visit to the file.
 268      *
 269      * The {@code canUseCached} parameter determines whether cached attributes
 270      * for the file can be used or not.
 271      */
 272     private Event visit(Path entry, boolean ignoreSecurityException, boolean canUseCached) {
 273         // need the file attributes
 274         BasicFileAttributes attrs;
 275         try {
 276             attrs = getAttributes(entry, canUseCached);
 277         } catch (IOException ioe) {
 278             return new Event(EventType.ENTRY, entry, ioe);
 279         } catch (SecurityException se) {
 280             if (ignoreSecurityException)
 281                 return null;
 282             throw se;
 283         }
 284 
 285         // at maximum depth or file is not a directory
 286         int depth = stack.size();
 287         if (depth >= maxDepth || !attrs.isDirectory()) {
 288             return new Event(EventType.ENTRY, entry, attrs);
 289         }
 290 
 291         // check for cycles when following links
 292         if (followLinks && wouldLoop(entry, attrs.fileKey())) {
 293             return new Event(EventType.ENTRY, entry,
 294                              new FileSystemLoopException(entry.toString()));
 295         }
 296 
 297         // file is a directory, attempt to open it
 298         DirectoryStream<Path> stream = null;
 299         try {
 300             stream = Files.newDirectoryStream(entry);
 301         } catch (IOException ioe) {
 302             return new Event(EventType.ENTRY, entry, ioe);
 303         } catch (SecurityException se) {
 304             if (ignoreSecurityException)
 305                 return null;
 306             throw se;
 307         }
 308 
 309         // push a directory node to the stack and return an event
 310         stack.push(new DirectoryNode(entry, attrs.fileKey(), stream));
 311         return new Event(EventType.START_DIRECTORY, entry, attrs);
 312     }
 313 
 314 
 315     /**
 316      * Start walking from the given file.
 317      */
 318     Event walk(Path file) {
 319         if (closed)
 320             throw new IllegalStateException("Closed");
 321 
 322         Event ev = visit(file,
 323                          false,   // ignoreSecurityException
 324                          false);  // canUseCached
 325         assert ev != null;
 326         return ev;
 327     }
 328 
 329     /**
 330      * Returns the next Event or {@code null} if there are no more events or
 331      * the walker is closed.
 332      */
 333     Event next() {
 334         DirectoryNode top = stack.peek();
 335         if (top == null)
 336             return null;      // stack is empty, we are done
 337 
 338         // continue iteration of the directory at the top of the stack
 339         Event ev;
 340         do {
 341             Path entry = null;
 342             IOException ioe = null;
 343 
 344             // get next entry in the directory
 345             if (!top.skipped()) {
 346                 Iterator<Path> iterator = top.iterator();
 347                 try {
 348                     if (iterator.hasNext()) {
 349                         entry = iterator.next();
 350                     }
 351                 } catch (DirectoryIteratorException x) {
 352                     ioe = x.getCause();
 353                 }
 354             }
 355 
 356             // no next entry so close and pop directory, creating corresponding event
 357             if (entry == null) {
 358                 try {
 359                     top.stream().close();
 360                 } catch (IOException e) {
 361                     if (ioe != null) {
 362                         ioe = e;
 363                     } else {
 364                         ioe.addSuppressed(e);
 365                     }
 366                 }
 367                 stack.pop();
 368                 return new Event(EventType.END_DIRECTORY, top.directory(), ioe);
 369             }
 370 
 371             // visit the entry
 372             ev = visit(entry,
 373                        true,   // ignoreSecurityException
 374                        true);  // canUseCached
 375 
 376         } while (ev == null);
 377 
 378         return ev;
 379     }
 380 
 381     /**
 382      * Pops the directory node that is the current top of the stack so that
 383      * there are no more events for the directory (including no END_DIRECTORY)
 384      * event. This method is a no-op if the stack is empty or the walker is
 385      * closed.
 386      */
 387     void pop() {
 388         if (!stack.isEmpty()) {
 389             DirectoryNode node = stack.pop();
 390             try {
 391                 node.stream().close();
 392             } catch (IOException ignore) { }
 393         }
 394     }
 395 
 396     /**
 397      * Skips the remaining entries in the directory at the top of the stack.
 398      * This method is a no-op if the stack is empty or the walker is closed.
 399      */
 400     void skipRemainingSiblings() {
 401         if (!stack.isEmpty()) {
 402             stack.peek().skip();
 403         }
 404     }
 405 
 406     /**
 407      * Returns {@code true} if the walker is open.
 408      */
 409     boolean isOpen() {
 410         return !closed;
 411     }
 412 
 413     /**
 414      * Closes/pops all directories on the stack.
 415      */
 416     @Override
 417     public void close() {
 418         if (!closed) {
 419             while (!stack.isEmpty()) {
 420                 pop();
 421             }
 422             closed = true;
 423         }
 424     }
 425 }