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 // TODO(nweiz): Rather than filtering here, avoid double-listing directories | |
175 // in the first place. | |
176 var seen = _canOverlap ? new Set() : null; | |
177 return pool.stream.where((entity) { | |
Bob Nystrom
2014/09/23 00:22:05
How about just:
if (!_canOverlap) return pool.str
nweiz
2014/09/23 00:26:46
Done.
| |
178 if (seen == null) return true; | |
179 if (seen.contains(entity.path)) return false; | |
180 seen.add(entity.path); | |
181 return true; | |
182 }); | |
183 } | |
184 | |
185 /// Synchronosuly list all entities that match this glob beneath [root]. | |
186 List<FileSystemEntity> listSync({String root, bool followLinks: true}) { | |
187 if (root == null) root = '.'; | |
188 | |
189 // TODO(nweiz): Rather than filtering here, avoid double-listing directories | |
190 // in the first place. | |
191 var seen = _canOverlap ? new Set() : null; | |
Bob Nystrom
2014/09/23 00:22:05
Ditto.
nweiz
2014/09/23 00:26:46
Done.
| |
192 return _trees.keys.expand((rootDir) { | |
193 var dir = rootDir == '.' ? root : rootDir; | |
194 return _trees[rootDir].listSync(dir, followLinks: followLinks); | |
195 }).where((entity) { | |
196 if (seen == null) return true; | |
197 if (seen.contains(entity.path)) return false; | |
198 seen.add(entity.path); | |
199 return true; | |
200 }).toList(); | |
201 } | |
202 } | |
203 | |
204 /// A single node in a [ListTree]. | |
205 class _ListTreeNode { | |
206 /// This node's child nodes, by their corresponding globs. | |
207 /// | |
208 /// Each child node will only be listed on directories that match its glob. | |
209 /// | |
210 /// This may be `null`, indicating that this node should be listed | |
211 /// recursively. | |
212 Map<SequenceNode, _ListTreeNode> children; | |
213 | |
214 /// This node's validator. | |
215 /// | |
216 /// This determines which entities will ultimately be emitted when [list] is | |
217 /// called. | |
218 OptionsNode _validator; | |
219 | |
220 /// Whether this node is recursive. | |
221 /// | |
222 /// A recursive node has no children and is listed recursively. | |
223 bool get isRecursive => children == null; | |
224 | |
225 /// Whether this node doesn't itself need to be listed. | |
226 /// | |
227 /// If a node has no validator and all of its children are literal filenames, | |
228 /// there's no need to list its contents. We can just directly traverse into | |
229 /// its children. | |
230 bool get _isIntermediate { | |
231 if (_validator != null) return false; | |
232 return children.keys.every((sequence) => | |
233 sequence.nodes.length == 1 && sequence.nodes.first is LiteralNode); | |
234 } | |
235 | |
236 /// Returns whether listing this node might return overlapping results. | |
237 bool get canOverlap { | |
238 // A recusive node can never overlap with itself, because it will only ever | |
239 // involve a single call to [Directory.list] that's then filtered with | |
240 // [_validator]. | |
241 if (isRecursive) return false; | |
242 | |
243 // If there's more than one child node and at least one of the children is | |
244 // dynamic (that is, matches more than just a literal string), there may be | |
245 // overlap. | |
246 if (children.length > 1 && children.keys.any((sequence) => | |
247 sequence.nodes.length > 1 || sequence.nodes.single is! LiteralNode)) { | |
248 return true; | |
249 } | |
250 | |
251 return children.values.any((node) => node.canOverlap); | |
252 } | |
253 | |
254 /// Creates a node with no children and no validator. | |
255 _ListTreeNode() | |
256 : children = new Map<SequenceNode, _ListTreeNode>(), | |
257 _validator = null; | |
258 | |
259 /// Creates a recursive node the given [validator]. | |
260 _ListTreeNode.recursive(SequenceNode validator) | |
261 : children = null, | |
262 _validator = new OptionsNode([validator]); | |
263 | |
264 /// Transforms this into recursive node, folding all its children into its | |
265 /// validator. | |
266 void makeRecursive() { | |
267 if (isRecursive) return; | |
268 _validator = new OptionsNode(children.keys.map((sequence) { | |
269 var child = children[sequence]; | |
270 child.makeRecursive(); | |
271 return _join([sequence, child._validator]); | |
272 })); | |
273 children = null; | |
274 } | |
275 | |
276 /// Adds [validator] to this node's existing validator. | |
277 void addOption(SequenceNode validator) { | |
278 if (_validator == null) { | |
279 _validator = new OptionsNode([validator]); | |
280 } else { | |
281 _validator.options.add(validator); | |
282 } | |
283 } | |
284 | |
285 /// Lists all entities within [dir] matching this node or its children. | |
286 /// | |
287 /// This may return duplicate entities. These will be filtered out in | |
288 /// [ListTree.list]. | |
289 Stream<FileSystemEntity> list(String dir, {bool followLinks: true}) { | |
290 if (isRecursive) { | |
291 return new Directory(dir).list(recursive: true, followLinks: followLinks) | |
292 .where((entity) => _matches(entity.path.substring(dir.length + 1))); | |
293 } | |
294 | |
295 var resultPool = new StreamPool(); | |
296 | |
297 // Don't spawn extra [Directory.list] calls when we already know exactly | |
298 // which subdirectories we're interested in. | |
299 if (_isIntermediate) { | |
300 children.forEach((sequence, child) { | |
301 resultPool.add(child.list(p.join(dir, sequence.nodes.single.text), | |
302 followLinks: followLinks)); | |
303 }); | |
304 resultPool.closeWhenEmpty(); | |
305 return resultPool.stream; | |
306 } | |
307 | |
308 var resultController = new StreamController(sync: true); | |
309 resultPool.add(resultController.stream); | |
310 new Directory(dir).list(followLinks: followLinks).listen((entity) { | |
311 var basename = entity.path.substring(dir.length + 1); | |
312 if (_matches(basename)) resultController.add(entity); | |
313 | |
314 children.forEach((sequence, child) { | |
315 if (entity is! Directory) return; | |
316 if (!sequence.matches(basename)) return; | |
317 resultPool.add(child.list(p.join(dir, basename), | |
318 followLinks: followLinks)); | |
319 }); | |
320 }, | |
321 onError: resultController.addError, | |
322 onDone: resultController.close); | |
323 | |
324 resultPool.closeWhenEmpty(); | |
325 return resultPool.stream; | |
326 } | |
327 | |
328 /// Synchronously lists all entities within [dir] matching this node or its | |
329 /// children. | |
330 /// | |
331 /// This may return duplicate entities. These will be filtered out in | |
332 /// [ListTree.listSync]. | |
333 Iterable<FileSystemEntity> listSync(String dir, {bool followLinks: true}) { | |
334 if (isRecursive) { | |
335 return new Directory(dir) | |
336 .listSync(recursive: true, followLinks: followLinks) | |
337 .where((entity) => _matches(entity.path.substring(dir.length + 1))); | |
338 } | |
339 | |
340 // Don't spawn extra [Directory.listSync] calls when we already know exactly | |
341 // which subdirectories we're interested in. | |
342 if (_isIntermediate) { | |
343 return children.keys.expand((sequence) { | |
344 return children[sequence].listSync( | |
345 p.join(dir, sequence.nodes.single.text), followLinks: followLinks); | |
346 }); | |
347 } | |
348 | |
349 return new Directory(dir).listSync(followLinks: followLinks) | |
350 .expand((entity) { | |
351 var entities = []; | |
352 var basename = entity.path.substring(dir.length + 1); | |
353 if (_matches(basename)) entities.add(entity); | |
354 if (entity is! Directory) return entities; | |
355 | |
356 entities.addAll(children.keys | |
357 .where((sequence) => sequence.matches(basename)) | |
358 .expand((sequence) { | |
359 return children[sequence].listSync( | |
360 p.join(dir, basename), followLinks: followLinks); | |
361 })); | |
362 | |
363 return entities; | |
364 }); | |
365 } | |
366 | |
367 /// Returns whether the native [path] matches [_validator]. | |
368 bool _matches(String path) { | |
369 if (_validator == null) return false; | |
370 return _validator.matches(path); | |
371 } | |
372 | |
373 String toString() => "($_validator) $children"; | |
374 } | |
375 | |
376 /// Joins each [components] into a new glob where each component is separated by | |
377 /// a path separator. | |
378 SequenceNode _join(Iterable<AstNode> components) { | |
379 var componentsList = components.toList(); | |
380 var nodes = [componentsList.removeAt(0)]; | |
381 for (var component in componentsList) { | |
382 nodes.add(new LiteralNode('/')); | |
383 nodes.add(component); | |
384 } | |
385 return new SequenceNode(nodes); | |
386 } | |
OLD | NEW |