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. | |
Bob Nystrom
2014/09/18 22:17:40
The logic for turning a raw AstNode into a ListTre
nweiz
2014/09/22 23:48:39
I factored them that way because it strikes me as
| |
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 ListTree(AstNode glob) { | |
55 // The first step in constructing a tree from the glob is to simplify the | |
56 // problem by eliminating options. [glob.expand] bubbles all options (and | |
57 // certain ranges) up to the top level of the glob so we can deal with them | |
58 // one at a time. | |
59 var options = glob.expand(); | |
60 | |
61 for (var option in options.options) { | |
62 // Since each option doesn't include its own options, we can safely split | |
63 // it into path components. | |
64 var components = option.split(p.context); | |
65 var firstNode = components.first.nodes.first; | |
66 var root; | |
67 | |
68 // Determine the root for this option, if it's absolute. If it's not, the | |
69 // root's just ".". | |
70 if (firstNode is LiteralNode) { | |
71 var text = firstNode.text; | |
72 if (Platform.isWindows) text.replaceAll("/", "\\"); | |
73 if (p.isAbsolute(text)) { | |
74 assert(components.first.nodes.length == 1); | |
Bob Nystrom
2014/09/18 22:17:40
Document this.
nweiz
2014/09/22 23:48:40
Done.
| |
75 root = firstNode.text; | |
76 components.removeAt(0); | |
77 } else { | |
78 root = '.'; | |
Bob Nystrom
2014/09/18 22:17:40
How about just initializing root to "." and ditch
nweiz
2014/09/22 23:48:39
Done.
| |
79 } | |
80 } else { | |
81 root = '.'; | |
82 } | |
83 | |
84 // The first [parent] represents the root directory itself. It may be null | |
Bob Nystrom
2014/09/18 22:17:40
This looks like a good chunk to break out into a s
nweiz
2014/09/22 23:48:40
Done.
| |
85 // here if this is the first option with this particular [root]. If so, | |
86 // we'll create it below. | |
87 // | |
88 // As we iterate through [components], [parent] will be set to | |
89 // progressively more nested nodes. | |
90 var parent = _trees[root]; | |
91 for (var i = 0; i < components.length; i++) { | |
92 var component = components[i]; | |
93 var recursive = component.nodes.any((node) => node is DoubleStarNode); | |
94 var complete = i == components.length - 1; | |
95 | |
96 // If the parent node for this level of nesting already exists, the new | |
97 // option will be added to it as additional validator options and/or | |
98 // additional children. | |
99 // | |
100 // If the parent doesn't exist, we'll create it in one of the else | |
101 // clauses below. | |
102 if (parent != null) { | |
Bob Nystrom
2014/09/18 22:17:40
Breaking this out into a method would get rid of s
nweiz
2014/09/22 23:48:40
How so?
Bob Nystrom
2014/09/23 00:22:04
I was thinking you could early return instead of a
| |
103 if (parent.isRecursive || recursive) { | |
104 // If [component] is recursive, mark [parent] as recursive. This | |
105 // will cause all of its children to be folded into its validator. | |
106 // If [parent] was already recursive, this is a no-op. | |
107 parent.makeRecursive(); | |
108 | |
109 // Add [component] and everything nested beneath it as an option to | |
110 // [parent]. Since [parent] is recursive, it will recursively list | |
111 // everything beneath it and filter them with one big glob. | |
112 parent.addOption(_join(components.sublist(i))); | |
113 break; | |
114 } else if (complete) { | |
115 // If [component] is the last component, add it to [parent]'s | |
116 // validator but not to its children. | |
117 parent.addOption(component); | |
118 } else { | |
119 // On the other hand if there are more components, add [component] | |
120 // to [parent]'s children and not its validator. Since we process | |
121 // each option's components separately, the same component is never | |
122 // both a validator and a child. | |
123 if (!parent.children.containsKey(component)) { | |
124 parent.children[component] = new _ListTreeNode(); | |
125 } | |
126 parent = parent.children[component]; | |
127 } | |
128 } else if (recursive) { | |
129 _trees[root] = new _ListTreeNode.recursive( | |
130 _join(components.sublist(i))); | |
131 break; | |
132 } else if (complete) { | |
133 _trees[root] = new _ListTreeNode()..addOption(component); | |
134 } else { | |
135 _trees[root] = new _ListTreeNode(); | |
136 _trees[root].children[component] = new _ListTreeNode(); | |
137 parent = _trees[root].children[component]; | |
138 } | |
139 } | |
140 } | |
141 } | |
142 | |
143 /// List all entities that match this glob beneath [root]. | |
144 Stream<FileSystemEntity> list({String root, bool followLinks: true}) { | |
145 if (root == null) root = '.'; | |
146 var pool = new StreamPool(); | |
147 for (var rootDir in _trees.keys) { | |
148 var dir = rootDir == '.' ? root : rootDir; | |
149 pool.add(_trees[rootDir].list(dir, followLinks: followLinks)); | |
150 } | |
151 pool.closeWhenEmpty(); | |
152 | |
153 // TODO(nweiz): Rather than filtering here, avoid double-listing directories | |
154 // in the first place. | |
155 var seen = new Set(); | |
156 return pool.stream.where((entity) { | |
157 if (seen.contains(entity.path)) return false; | |
158 seen.add(entity.path); | |
Bob Nystrom
2014/09/18 22:17:40
This will use buckets of memory on large directory
nweiz
2014/09/22 23:48:40
Done.
| |
159 return true; | |
160 }); | |
161 } | |
162 | |
163 /// Synchronosuly list all entities that match this glob beneath [root]. | |
164 List<FileSystemEntity> listSync({String root, bool followLinks: true}) { | |
165 if (root == null) root = '.'; | |
166 | |
167 // TODO(nweiz): Rather than filtering here, avoid double-listing directories | |
168 // in the first place. | |
169 var seen = new Set(); | |
170 return _trees.keys.expand((rootDir) { | |
171 var dir = rootDir == '.' ? root : rootDir; | |
172 return _trees[rootDir].listSync(dir, followLinks: followLinks); | |
173 }).where((entity) { | |
174 if (seen.contains(entity.path)) return false; | |
175 seen.add(entity.path); | |
176 return true; | |
177 }).toList(); | |
178 } | |
179 } | |
180 | |
181 /// A single node in a [ListTree]. | |
182 class _ListTreeNode { | |
183 /// This node's child nodes, by their corresponding globs. | |
184 /// | |
185 /// Each child node will only be listed on directories that match its glob. | |
186 /// | |
187 /// This may be `null`, indicating that this should be listed recursively. | |
Bob Nystrom
2014/09/18 22:17:40
Clarify what the second "this" means.
nweiz
2014/09/22 23:48:40
Done.
| |
188 Map<SequenceNode, _ListTreeNode> children; | |
189 | |
190 /// This node's validator. | |
191 /// | |
192 /// This determines which entities will ultimately be emitted when [list] is | |
193 /// called. | |
194 OptionsNode _validator; | |
195 | |
196 /// Whether this node is recursive. | |
197 /// | |
198 /// A recursive node has no children and is listed recursively. | |
199 bool get isRecursive => children == null; | |
200 | |
201 /// Whether this node doesn't itself need to be listed. | |
202 /// | |
203 /// If a node has no validator and all of its children are literal filenames, | |
204 /// there's no need to list its contents. We can just directly traverse into | |
205 /// its children. | |
206 bool get _isIntermediate { | |
207 if (_validator != null) return false; | |
208 return children.keys.every((sequence) => | |
209 sequence.nodes.length == 1 && sequence.nodes.first is LiteralNode); | |
210 } | |
211 | |
212 /// Creates a node with no children and no validator. | |
213 _ListTreeNode() | |
214 : children = new Map<SequenceNode, _ListTreeNode>(), | |
215 _validator = null; | |
216 | |
217 /// Creates a recursive node the given [validator]. | |
218 _ListTreeNode.recursive(SequenceNode validator) | |
219 : children = null, | |
220 _validator = new OptionsNode([validator]); | |
221 | |
222 /// Transforms this into recursive node, folding all its children into its | |
223 /// validator. | |
224 void makeRecursive() { | |
225 if (isRecursive) return; | |
226 _validator = new OptionsNode(children.keys.map((sequence) { | |
227 var child = children[sequence]; | |
228 child.makeRecursive(); | |
229 return _join([sequence, child._validator]); | |
230 })); | |
231 children = null; | |
232 } | |
233 | |
234 /// Adds [validator] to this node's existing validator. | |
235 void addOption(SequenceNode validator) { | |
236 if (_validator == null) { | |
237 _validator = new OptionsNode([validator]); | |
238 } else { | |
239 _validator.options.add(validator); | |
240 } | |
241 } | |
242 | |
243 /// Lists all entities within [dir] matching this node or its children. | |
Bob Nystrom
2014/09/18 22:17:40
Document that this (and listSync()) may return dup
nweiz
2014/09/22 23:48:39
Done.
| |
244 Stream<FileSystemEntity> list(String dir, {bool followLinks: true}) { | |
245 if (isRecursive) { | |
246 return new Directory(dir).list(recursive: true, followLinks: followLinks) | |
247 .where((entity) => _matches(entity.path.substring(dir.length + 1))) | |
248 .handleError((error) { | |
249 // Swallow FileSystemExceptions because nonexistent or unreadable | |
250 // directories should just not produce any entities rather than crashing | |
251 // the list. | |
Bob Nystrom
2014/09/18 22:17:40
Why?
nweiz
2014/09/22 23:48:40
This was here to handle things like an unreadable
| |
252 if (error is! FileSystemException) throw error; | |
253 }); | |
254 } | |
255 | |
256 var resultPool = new StreamPool(); | |
257 | |
258 // Don't spawn extra [Directory.list] calls when we already know exactly | |
259 // which subdirectories we're interested in. | |
260 if (_isIntermediate) { | |
261 children.forEach((sequence, child) { | |
Bob Nystrom
2014/09/18 22:17:40
How does this handle a glob that points to a file,
nweiz
2014/09/22 23:48:39
That's handled as a validator. The root "." node's
| |
262 resultPool.add(child.list(p.join(dir, sequence.nodes.single.text), | |
263 followLinks: followLinks)); | |
264 }); | |
265 resultPool.closeWhenEmpty(); | |
266 return resultPool.stream; | |
267 } | |
268 | |
269 var resultController = new StreamController(sync: true); | |
270 resultPool.add(resultController.stream); | |
271 new Directory(dir).list(followLinks: followLinks).listen((entity) { | |
272 var basename = entity.path.substring(dir.length + 1); | |
273 if (_matches(basename)) resultController.add(entity); | |
274 | |
275 children.forEach((sequence, child) { | |
276 if (!sequence.matches(basename)) return; | |
277 resultPool.add(child.list(p.join(dir, basename), | |
Bob Nystrom
2014/09/18 22:17:40
Calling this recursively will create a tree of Str
nweiz
2014/09/22 23:48:40
That's right, although it won't create more than a
Bob Nystrom
2014/09/23 00:22:04
Isn't only one necessary? Couldn't you create a si
nweiz
2014/09/23 00:26:46
I suppose so. It seems cleaner to me to keep the [
| |
278 followLinks: followLinks)); | |
279 }); | |
280 }, onError: (error, stackTrace) { | |
281 // Swallow FileSystemExceptions because nonexistent or unreadable | |
282 // directories should just not produce any entities rather than crashing | |
283 // the list. | |
284 if (error is FileSystemException) return; | |
Bob Nystrom
2014/09/18 22:17:40
I don't understand the motivation here. If a raw D
nweiz
2014/09/22 23:48:40
See above.
| |
285 resultController.addError(error, stackTrace); | |
286 }, onDone: resultController.close); | |
287 | |
288 resultPool.closeWhenEmpty(); | |
289 return resultPool.stream; | |
290 } | |
291 | |
292 /// Synchronously lists all entities within [dir] matching this node or its | |
293 /// children. | |
294 Iterable<FileSystemEntity> listSync(String dir, {bool followLinks: true}) { | |
295 try { | |
296 if (isRecursive) { | |
297 return new Directory(dir) | |
298 .listSync(recursive: true, followLinks: followLinks) | |
299 .where((entity) => _matches(entity.path.substring(dir.length + 1))); | |
300 } | |
301 | |
302 // Don't spawn extra [Directory.listSync] calls when we already know exact ly | |
Bob Nystrom
2014/09/18 22:17:40
Long line.
nweiz
2014/09/22 23:48:40
Done.
| |
303 // which subdirectories we're interested in. | |
304 if (_isIntermediate) { | |
305 return children.keys.expand((sequence) { | |
306 return children[sequence].listSync( | |
307 p.join(dir, sequence.nodes.single.text), followLinks: followLinks) ; | |
308 }); | |
309 } | |
310 | |
311 return new Directory(dir).listSync(followLinks: followLinks) | |
312 .expand((entity) { | |
313 var entities = []; | |
314 var basename = entity.path.substring(dir.length + 1); | |
315 if (_matches(basename)) entities.add(entity); | |
316 | |
317 entities.addAll(children.keys | |
318 .where((sequence) => sequence.matches(basename)) | |
319 .expand((sequence) { | |
320 return children[sequence].listSync( | |
321 p.join(dir, basename), followLinks: followLinks); | |
322 })); | |
323 | |
324 return entities; | |
325 }); | |
326 } on FileSystemException catch (error) { | |
327 // Swallow FileSystemExceptions because nonexistent or unreadable | |
328 // directories should just not produce any entities rather than crashing | |
329 // the list. | |
330 return []; | |
331 } | |
332 } | |
333 | |
334 /// Returns whether the native [path] matches [_validator]. | |
335 bool _matches(String path) { | |
336 if (_validator == null) return false; | |
337 return _validator.matches(path); | |
338 } | |
339 | |
340 String toString() => "($_validator) $children"; | |
341 } | |
342 | |
343 /// Joins each [components] into a new glob where each component is separated by | |
344 /// a path separator. | |
345 SequenceNode _join(Iterable<AstNode> components) { | |
346 var componentsList = components.toList(); | |
347 var nodes = [componentsList.removeAt(0)]; | |
348 for (var component in componentsList) { | |
349 nodes.add(new LiteralNode('/')); | |
350 nodes.add(component); | |
351 } | |
352 return new SequenceNode(nodes); | |
353 } | |
OLD | NEW |