OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. |
| 4 |
| 5 library glob.list_tree; |
| 6 |
| 7 import 'dart:io'; |
| 8 import 'dart:async'; |
| 9 |
| 10 import 'package:path/path.dart' as p; |
| 11 |
| 12 import 'ast.dart'; |
| 13 import 'stream_pool.dart'; |
| 14 |
| 15 /// A structure built from a glob that efficiently lists filesystem entities |
| 16 /// that match that glob. |
| 17 /// |
| 18 /// This structure is designed to list the minimal number of physical |
| 19 /// directories necessary to find everything that matches the glob. For example, |
| 20 /// for the glob `foo/{bar,baz}/*`, there's no need to list the working |
| 21 /// directory or even `foo/`; only `foo/bar` and `foo/baz` should be listed. |
| 22 /// |
| 23 /// This works by creating a tree of [_ListTreeNode]s, each of which corresponds |
| 24 /// to a single of directory nesting in the source glob. Each node has child |
| 25 /// nodes associated with globs ([_ListTreeNode.children]), as well as its own |
| 26 /// glob ([_ListTreeNode._validator]) that indicates which entities within that |
| 27 /// node's directory should be returned. |
| 28 /// |
| 29 /// For example, the glob `foo/{*.dart,b*/*.txt}` creates the following tree: |
| 30 /// |
| 31 /// . |
| 32 /// '-- "foo" (validator: "*.dart") |
| 33 /// '-- "b*" (validator: "*.txt" |
| 34 /// |
| 35 /// If a node doesn't have a validator, we know we don't have to list it |
| 36 /// explicitly. |
| 37 /// |
| 38 /// Nodes can also be marked as "recursive", which means they need to be listed |
| 39 /// recursively (usually to support `**`). In this case, they will have no |
| 40 /// children; instead, their validator will just encompass the globs that would |
| 41 /// otherwise be in their children. For example, the glob |
| 42 /// `foo/{**.dart,bar/*.txt}` creates a recursive node for `foo` with the |
| 43 /// validator `**.dart,bar/*.txt`. |
| 44 /// |
| 45 /// If the glob contains multiple filesystem roots (e.g. `{C:/,D:/}*.dart`), |
| 46 /// each root will have its own tree of nodes. Relative globs use `.` as their |
| 47 /// root instead. |
| 48 class ListTree { |
| 49 /// A map from filesystem roots to the list tree for those roots. |
| 50 /// |
| 51 /// A relative glob will use `.` as its root. |
| 52 final _trees = new Map<String, _ListTreeNode>(); |
| 53 |
| 54 /// Whether paths listed might overlap. |
| 55 /// |
| 56 /// If they do, we need to filter out overlapping paths. |
| 57 bool _canOverlap; |
| 58 |
| 59 ListTree(AstNode glob) { |
| 60 // The first step in constructing a tree from the glob is to simplify the |
| 61 // problem by eliminating options. [glob.flattenOptions] bubbles all options |
| 62 // (and certain ranges) up to the top level of the glob so we can deal with |
| 63 // them one at a time. |
| 64 var options = glob.flattenOptions(); |
| 65 |
| 66 for (var option in options.options) { |
| 67 // Since each option doesn't include its own options, we can safely split |
| 68 // it into path components. |
| 69 var components = option.split(p.context); |
| 70 var firstNode = components.first.nodes.first; |
| 71 var root = '.'; |
| 72 |
| 73 // Determine the root for this option, if it's absolute. If it's not, the |
| 74 // root's just ".". |
| 75 if (firstNode is LiteralNode) { |
| 76 var text = firstNode.text; |
| 77 if (Platform.isWindows) text.replaceAll("/", "\\"); |
| 78 if (p.isAbsolute(text)) { |
| 79 // If the path is absolute, the root should be the only thing in the |
| 80 // first component. |
| 81 assert(components.first.nodes.length == 1); |
| 82 root = firstNode.text; |
| 83 components.removeAt(0); |
| 84 } |
| 85 } |
| 86 |
| 87 _addGlob(root, components); |
| 88 } |
| 89 |
| 90 _canOverlap = _computeCanOverlap(); |
| 91 } |
| 92 |
| 93 /// Add the glob represented by [components] to the tree under [root]. |
| 94 void _addGlob(String root, List<AstNode> components) { |
| 95 // The first [parent] represents the root directory itself. It may be null |
| 96 // here if this is the first option with this particular [root]. If so, |
| 97 // we'll create it below. |
| 98 // |
| 99 // As we iterate through [components], [parent] will be set to |
| 100 // progressively more nested nodes. |
| 101 var parent = _trees[root]; |
| 102 for (var i = 0; i < components.length; i++) { |
| 103 var component = components[i]; |
| 104 var recursive = component.nodes.any((node) => node is DoubleStarNode); |
| 105 var complete = i == components.length - 1; |
| 106 |
| 107 // If the parent node for this level of nesting already exists, the new |
| 108 // option will be added to it as additional validator options and/or |
| 109 // additional children. |
| 110 // |
| 111 // If the parent doesn't exist, we'll create it in one of the else |
| 112 // clauses below. |
| 113 if (parent != null) { |
| 114 if (parent.isRecursive || recursive) { |
| 115 // If [component] is recursive, mark [parent] as recursive. This |
| 116 // will cause all of its children to be folded into its validator. |
| 117 // If [parent] was already recursive, this is a no-op. |
| 118 parent.makeRecursive(); |
| 119 |
| 120 // Add [component] and everything nested beneath it as an option to |
| 121 // [parent]. Since [parent] is recursive, it will recursively list |
| 122 // everything beneath it and filter them with one big glob. |
| 123 parent.addOption(_join(components.sublist(i))); |
| 124 return; |
| 125 } else if (complete) { |
| 126 // If [component] is the last component, add it to [parent]'s |
| 127 // validator but not to its children. |
| 128 parent.addOption(component); |
| 129 } else { |
| 130 // On the other hand if there are more components, add [component] |
| 131 // to [parent]'s children and not its validator. Since we process |
| 132 // each option's components separately, the same component is never |
| 133 // both a validator and a child. |
| 134 if (!parent.children.containsKey(component)) { |
| 135 parent.children[component] = new _ListTreeNode(); |
| 136 } |
| 137 parent = parent.children[component]; |
| 138 } |
| 139 } else if (recursive) { |
| 140 _trees[root] = new _ListTreeNode.recursive( |
| 141 _join(components.sublist(i))); |
| 142 return; |
| 143 } else if (complete) { |
| 144 _trees[root] = new _ListTreeNode()..addOption(component); |
| 145 } else { |
| 146 _trees[root] = new _ListTreeNode(); |
| 147 _trees[root].children[component] = new _ListTreeNode(); |
| 148 parent = _trees[root].children[component]; |
| 149 } |
| 150 } |
| 151 } |
| 152 |
| 153 /// Computes the value for [_canOverlap]. |
| 154 bool _computeCanOverlap() { |
| 155 // If this can list a relative path and an absolute path, the former may be |
| 156 // contained within the latter. |
| 157 if (_trees.length > 1 && _trees.containsKey('.')) return true; |
| 158 |
| 159 // Otherwise, this can only overlap if the tree beneath any given root could |
| 160 // overlap internally. |
| 161 return _trees.values.any((node) => node.canOverlap); |
| 162 } |
| 163 |
| 164 /// List all entities that match this glob beneath [root]. |
| 165 Stream<FileSystemEntity> list({String root, bool followLinks: true}) { |
| 166 if (root == null) root = '.'; |
| 167 var pool = new StreamPool(); |
| 168 for (var rootDir in _trees.keys) { |
| 169 var dir = rootDir == '.' ? root : rootDir; |
| 170 pool.add(_trees[rootDir].list(dir, followLinks: followLinks)); |
| 171 } |
| 172 pool.closeWhenEmpty(); |
| 173 |
| 174 if (!_canOverlap) return pool.stream; |
| 175 |
| 176 // TODO(nweiz): Rather than filtering here, avoid double-listing directories |
| 177 // in the first place. |
| 178 var seen = new Set(); |
| 179 return pool.stream.where((entity) { |
| 180 if (seen.contains(entity.path)) return false; |
| 181 seen.add(entity.path); |
| 182 return true; |
| 183 }); |
| 184 } |
| 185 |
| 186 /// Synchronosuly list all entities that match this glob beneath [root]. |
| 187 List<FileSystemEntity> listSync({String root, bool followLinks: true}) { |
| 188 if (root == null) root = '.'; |
| 189 |
| 190 var result = _trees.keys.expand((rootDir) { |
| 191 var dir = rootDir == '.' ? root : rootDir; |
| 192 return _trees[rootDir].listSync(dir, followLinks: followLinks); |
| 193 }); |
| 194 |
| 195 if (!_canOverlap) return result.toList(); |
| 196 |
| 197 // TODO(nweiz): Rather than filtering here, avoid double-listing directories |
| 198 // in the first place. |
| 199 var seen = new Set(); |
| 200 return result.where((entity) { |
| 201 if (seen.contains(entity.path)) return false; |
| 202 seen.add(entity.path); |
| 203 return true; |
| 204 }).toList(); |
| 205 } |
| 206 } |
| 207 |
| 208 /// A single node in a [ListTree]. |
| 209 class _ListTreeNode { |
| 210 /// This node's child nodes, by their corresponding globs. |
| 211 /// |
| 212 /// Each child node will only be listed on directories that match its glob. |
| 213 /// |
| 214 /// This may be `null`, indicating that this node should be listed |
| 215 /// recursively. |
| 216 Map<SequenceNode, _ListTreeNode> children; |
| 217 |
| 218 /// This node's validator. |
| 219 /// |
| 220 /// This determines which entities will ultimately be emitted when [list] is |
| 221 /// called. |
| 222 OptionsNode _validator; |
| 223 |
| 224 /// Whether this node is recursive. |
| 225 /// |
| 226 /// A recursive node has no children and is listed recursively. |
| 227 bool get isRecursive => children == null; |
| 228 |
| 229 /// Whether this node doesn't itself need to be listed. |
| 230 /// |
| 231 /// If a node has no validator and all of its children are literal filenames, |
| 232 /// there's no need to list its contents. We can just directly traverse into |
| 233 /// its children. |
| 234 bool get _isIntermediate { |
| 235 if (_validator != null) return false; |
| 236 return children.keys.every((sequence) => |
| 237 sequence.nodes.length == 1 && sequence.nodes.first is LiteralNode); |
| 238 } |
| 239 |
| 240 /// Returns whether listing this node might return overlapping results. |
| 241 bool get canOverlap { |
| 242 // A recusive node can never overlap with itself, because it will only ever |
| 243 // involve a single call to [Directory.list] that's then filtered with |
| 244 // [_validator]. |
| 245 if (isRecursive) return false; |
| 246 |
| 247 // If there's more than one child node and at least one of the children is |
| 248 // dynamic (that is, matches more than just a literal string), there may be |
| 249 // overlap. |
| 250 if (children.length > 1 && children.keys.any((sequence) => |
| 251 sequence.nodes.length > 1 || sequence.nodes.single is! LiteralNode)) { |
| 252 return true; |
| 253 } |
| 254 |
| 255 return children.values.any((node) => node.canOverlap); |
| 256 } |
| 257 |
| 258 /// Creates a node with no children and no validator. |
| 259 _ListTreeNode() |
| 260 : children = new Map<SequenceNode, _ListTreeNode>(), |
| 261 _validator = null; |
| 262 |
| 263 /// Creates a recursive node the given [validator]. |
| 264 _ListTreeNode.recursive(SequenceNode validator) |
| 265 : children = null, |
| 266 _validator = new OptionsNode([validator]); |
| 267 |
| 268 /// Transforms this into recursive node, folding all its children into its |
| 269 /// validator. |
| 270 void makeRecursive() { |
| 271 if (isRecursive) return; |
| 272 _validator = new OptionsNode(children.keys.map((sequence) { |
| 273 var child = children[sequence]; |
| 274 child.makeRecursive(); |
| 275 return _join([sequence, child._validator]); |
| 276 })); |
| 277 children = null; |
| 278 } |
| 279 |
| 280 /// Adds [validator] to this node's existing validator. |
| 281 void addOption(SequenceNode validator) { |
| 282 if (_validator == null) { |
| 283 _validator = new OptionsNode([validator]); |
| 284 } else { |
| 285 _validator.options.add(validator); |
| 286 } |
| 287 } |
| 288 |
| 289 /// Lists all entities within [dir] matching this node or its children. |
| 290 /// |
| 291 /// This may return duplicate entities. These will be filtered out in |
| 292 /// [ListTree.list]. |
| 293 Stream<FileSystemEntity> list(String dir, {bool followLinks: true}) { |
| 294 if (isRecursive) { |
| 295 return new Directory(dir).list(recursive: true, followLinks: followLinks) |
| 296 .where((entity) => _matches(entity.path.substring(dir.length + 1))); |
| 297 } |
| 298 |
| 299 var resultPool = new StreamPool(); |
| 300 |
| 301 // Don't spawn extra [Directory.list] calls when we already know exactly |
| 302 // which subdirectories we're interested in. |
| 303 if (_isIntermediate) { |
| 304 children.forEach((sequence, child) { |
| 305 resultPool.add(child.list(p.join(dir, sequence.nodes.single.text), |
| 306 followLinks: followLinks)); |
| 307 }); |
| 308 resultPool.closeWhenEmpty(); |
| 309 return resultPool.stream; |
| 310 } |
| 311 |
| 312 var resultController = new StreamController(sync: true); |
| 313 resultPool.add(resultController.stream); |
| 314 new Directory(dir).list(followLinks: followLinks).listen((entity) { |
| 315 var basename = entity.path.substring(dir.length + 1); |
| 316 if (_matches(basename)) resultController.add(entity); |
| 317 |
| 318 children.forEach((sequence, child) { |
| 319 if (entity is! Directory) return; |
| 320 if (!sequence.matches(basename)) return; |
| 321 resultPool.add(child.list(p.join(dir, basename), |
| 322 followLinks: followLinks)); |
| 323 }); |
| 324 }, |
| 325 onError: resultController.addError, |
| 326 onDone: resultController.close); |
| 327 |
| 328 resultPool.closeWhenEmpty(); |
| 329 return resultPool.stream; |
| 330 } |
| 331 |
| 332 /// Synchronously lists all entities within [dir] matching this node or its |
| 333 /// children. |
| 334 /// |
| 335 /// This may return duplicate entities. These will be filtered out in |
| 336 /// [ListTree.listSync]. |
| 337 Iterable<FileSystemEntity> listSync(String dir, {bool followLinks: true}) { |
| 338 if (isRecursive) { |
| 339 return new Directory(dir) |
| 340 .listSync(recursive: true, followLinks: followLinks) |
| 341 .where((entity) => _matches(entity.path.substring(dir.length + 1))); |
| 342 } |
| 343 |
| 344 // Don't spawn extra [Directory.listSync] calls when we already know exactly |
| 345 // which subdirectories we're interested in. |
| 346 if (_isIntermediate) { |
| 347 return children.keys.expand((sequence) { |
| 348 return children[sequence].listSync( |
| 349 p.join(dir, sequence.nodes.single.text), followLinks: followLinks); |
| 350 }); |
| 351 } |
| 352 |
| 353 return new Directory(dir).listSync(followLinks: followLinks) |
| 354 .expand((entity) { |
| 355 var entities = []; |
| 356 var basename = entity.path.substring(dir.length + 1); |
| 357 if (_matches(basename)) entities.add(entity); |
| 358 if (entity is! Directory) return entities; |
| 359 |
| 360 entities.addAll(children.keys |
| 361 .where((sequence) => sequence.matches(basename)) |
| 362 .expand((sequence) { |
| 363 return children[sequence].listSync( |
| 364 p.join(dir, basename), followLinks: followLinks); |
| 365 })); |
| 366 |
| 367 return entities; |
| 368 }); |
| 369 } |
| 370 |
| 371 /// Returns whether the native [path] matches [_validator]. |
| 372 bool _matches(String path) { |
| 373 if (_validator == null) return false; |
| 374 return _validator.matches(path); |
| 375 } |
| 376 |
| 377 String toString() => "($_validator) $children"; |
| 378 } |
| 379 |
| 380 /// Joins each [components] into a new glob where each component is separated by |
| 381 /// a path separator. |
| 382 SequenceNode _join(Iterable<AstNode> components) { |
| 383 var componentsList = components.toList(); |
| 384 var nodes = [componentsList.removeAt(0)]; |
| 385 for (var component in componentsList) { |
| 386 nodes.add(new LiteralNode('/')); |
| 387 nodes.add(component); |
| 388 } |
| 389 return new SequenceNode(nodes); |
| 390 } |
OLD | NEW |