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