OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 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 | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library glob.list_tree; | |
6 | |
7 import 'dart:io'; | 5 import 'dart:io'; |
8 import 'dart:async'; | 6 import 'dart:async'; |
9 | 7 |
| 8 import 'package:async/async.dart'; |
10 import 'package:path/path.dart' as p; | 9 import 'package:path/path.dart' as p; |
11 | 10 |
12 import 'ast.dart'; | 11 import 'ast.dart'; |
13 import 'stream_pool.dart'; | |
14 import 'utils.dart'; | 12 import 'utils.dart'; |
15 | 13 |
16 /// The errno for a file or directory not existing on Mac and Linux. | 14 /// The errno for a file or directory not existing on Mac and Linux. |
17 const _ENOENT = 2; | 15 const _ENOENT = 2; |
18 | 16 |
19 /// Another errno we see on Windows when trying to list a non-existent | 17 /// Another errno we see on Windows when trying to list a non-existent |
20 /// directory. | 18 /// directory. |
21 const _ENOENT_WIN = 3; | 19 const _ENOENT_WIN = 3; |
22 | 20 |
23 /// A structure built from a glob that efficiently lists filesystem entities | 21 /// A structure built from a glob that efficiently lists filesystem entities |
(...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
92 } | 90 } |
93 } | 91 } |
94 | 92 |
95 _addGlob(root, components); | 93 _addGlob(root, components); |
96 } | 94 } |
97 | 95 |
98 _canOverlap = _computeCanOverlap(); | 96 _canOverlap = _computeCanOverlap(); |
99 } | 97 } |
100 | 98 |
101 /// Add the glob represented by [components] to the tree under [root]. | 99 /// Add the glob represented by [components] to the tree under [root]. |
102 void _addGlob(String root, List<AstNode> components) { | 100 void _addGlob(String root, List<SequenceNode> components) { |
103 // The first [parent] represents the root directory itself. It may be null | 101 // 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, | 102 // here if this is the first option with this particular [root]. If so, |
105 // we'll create it below. | 103 // we'll create it below. |
106 // | 104 // |
107 // As we iterate through [components], [parent] will be set to | 105 // As we iterate through [components], [parent] will be set to |
108 // progressively more nested nodes. | 106 // progressively more nested nodes. |
109 var parent = _trees[root]; | 107 var parent = _trees[root]; |
110 for (var i = 0; i < components.length; i++) { | 108 for (var i = 0; i < components.length; i++) { |
111 var component = components[i]; | 109 var component = components[i]; |
112 var recursive = component.nodes.any((node) => node is DoubleStarNode); | 110 var recursive = component.nodes.any((node) => node is DoubleStarNode); |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
165 if (_trees.length > 1 && _trees.containsKey('.')) return true; | 163 if (_trees.length > 1 && _trees.containsKey('.')) return true; |
166 | 164 |
167 // Otherwise, this can only overlap if the tree beneath any given root could | 165 // Otherwise, this can only overlap if the tree beneath any given root could |
168 // overlap internally. | 166 // overlap internally. |
169 return _trees.values.any((node) => node.canOverlap); | 167 return _trees.values.any((node) => node.canOverlap); |
170 } | 168 } |
171 | 169 |
172 /// List all entities that match this glob beneath [root]. | 170 /// List all entities that match this glob beneath [root]. |
173 Stream<FileSystemEntity> list({String root, bool followLinks: true}) { | 171 Stream<FileSystemEntity> list({String root, bool followLinks: true}) { |
174 if (root == null) root = '.'; | 172 if (root == null) root = '.'; |
175 var pool = new StreamPool(); | 173 var group = new StreamGroup<FileSystemEntity>(); |
176 for (var rootDir in _trees.keys) { | 174 for (var rootDir in _trees.keys) { |
177 var dir = rootDir == '.' ? root : rootDir; | 175 var dir = rootDir == '.' ? root : rootDir; |
178 pool.add(_trees[rootDir].list(dir, followLinks: followLinks)); | 176 group.add(_trees[rootDir].list(dir, followLinks: followLinks)); |
179 } | 177 } |
180 pool.closeWhenEmpty(); | 178 group.close(); |
181 | 179 |
182 if (!_canOverlap) return pool.stream; | 180 if (!_canOverlap) return group.stream; |
183 | 181 |
184 // TODO(nweiz): Rather than filtering here, avoid double-listing directories | 182 // TODO(nweiz): Rather than filtering here, avoid double-listing directories |
185 // in the first place. | 183 // in the first place. |
186 var seen = new Set(); | 184 var seen = new Set(); |
187 return pool.stream.where((entity) { | 185 return group.stream.where((entity) { |
188 if (seen.contains(entity.path)) return false; | 186 if (seen.contains(entity.path)) return false; |
189 seen.add(entity.path); | 187 seen.add(entity.path); |
190 return true; | 188 return true; |
191 }); | 189 }); |
192 } | 190 } |
193 | 191 |
194 /// Synchronosuly list all entities that match this glob beneath [root]. | 192 /// Synchronosuly list all entities that match this glob beneath [root]. |
195 List<FileSystemEntity> listSync({String root, bool followLinks: true}) { | 193 List<FileSystemEntity> listSync({String root, bool followLinks: true}) { |
196 if (root == null) root = '.'; | 194 if (root == null) root = '.'; |
197 | 195 |
198 var result = _trees.keys.expand((rootDir) { | 196 // TODO(nweiz): Remove the explicit annotation when sdk#26139 is fixed. |
| 197 var result = _trees.keys.expand/*<FileSystemEntity>*/((rootDir) { |
199 var dir = rootDir == '.' ? root : rootDir; | 198 var dir = rootDir == '.' ? root : rootDir; |
200 return _trees[rootDir].listSync(dir, followLinks: followLinks); | 199 return _trees[rootDir].listSync(dir, followLinks: followLinks); |
201 }); | 200 }); |
202 | 201 |
203 if (!_canOverlap) return result.toList(); | 202 if (!_canOverlap) return result.toList(); |
204 | 203 |
205 // TODO(nweiz): Rather than filtering here, avoid double-listing directories | 204 // TODO(nweiz): Rather than filtering here, avoid double-listing directories |
206 // in the first place. | 205 // in the first place. |
207 var seen = new Set(); | 206 var seen = new Set<String>(); |
208 return result.where((entity) { | 207 return result.where((entity) { |
209 if (seen.contains(entity.path)) return false; | 208 if (seen.contains(entity.path)) return false; |
210 seen.add(entity.path); | 209 seen.add(entity.path); |
211 return true; | 210 return true; |
212 }).toList(); | 211 }).toList(); |
213 } | 212 } |
214 } | 213 } |
215 | 214 |
216 /// A single node in a [ListTree]. | 215 /// A single node in a [ListTree]. |
217 class _ListTreeNode { | 216 class _ListTreeNode { |
218 /// This node's child nodes, by their corresponding globs. | 217 /// This node's child nodes, by their corresponding globs. |
219 /// | 218 /// |
220 /// Each child node will only be listed on directories that match its glob. | 219 /// Each child node will only be listed on directories that match its glob. |
221 /// | 220 /// |
222 /// This may be `null`, indicating that this node should be listed | 221 /// This may be `null`, indicating that this node should be listed |
223 /// recursively. | 222 /// recursively. |
224 Map<SequenceNode, _ListTreeNode> children; | 223 Map<SequenceNode, _ListTreeNode> children; |
225 | 224 |
226 /// This node's validator. | 225 /// This node's validator. |
227 /// | 226 /// |
228 /// This determines which entities will ultimately be emitted when [list] is | 227 /// This determines which entities will ultimately be emitted when [list] is |
229 /// called. | 228 /// called. |
230 OptionsNode _validator; | 229 OptionsNode _validator; |
231 | 230 |
232 /// Whether this node is recursive. | 231 /// Whether this node is recursive. |
233 /// | 232 /// |
234 /// A recursive node has no children and is listed recursively. | 233 /// A recursive node has no children and is listed recursively. |
235 bool get isRecursive => children == null; | 234 bool get isRecursive => children == null; |
236 | 235 |
| 236 bool get _caseSensitive { |
| 237 if (_validator != null) return _validator.caseSensitive; |
| 238 if (children == null) return true; |
| 239 if (children.isEmpty) return true; |
| 240 return children.keys.first.caseSensitive; |
| 241 } |
| 242 |
237 /// Whether this node doesn't itself need to be listed. | 243 /// Whether this node doesn't itself need to be listed. |
238 /// | 244 /// |
239 /// If a node has no validator and all of its children are literal filenames, | 245 /// 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 | 246 /// there's no need to list its contents. We can just directly traverse into |
241 /// its children. | 247 /// its children. |
242 bool get _isIntermediate { | 248 bool get _isIntermediate { |
243 if (_validator != null) return false; | 249 if (_validator != null) return false; |
| 250 if (!_caseSensitive) return false; |
244 return children.keys.every((sequence) => | 251 return children.keys.every((sequence) => |
245 sequence.nodes.length == 1 && sequence.nodes.first is LiteralNode); | 252 sequence.nodes.length == 1 && sequence.nodes.first is LiteralNode); |
246 } | 253 } |
247 | 254 |
248 /// Returns whether listing this node might return overlapping results. | 255 /// Returns whether listing this node might return overlapping results. |
249 bool get canOverlap { | 256 bool get canOverlap { |
250 // A recusive node can never overlap with itself, because it will only ever | 257 // 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 | 258 // involve a single call to [Directory.list] that's then filtered with |
252 // [_validator]. | 259 // [_validator]. |
253 if (isRecursive) return false; | 260 if (isRecursive) return false; |
254 | 261 |
255 // If there's more than one child node and at least one of the children is | 262 // 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 | 263 // dynamic (that is, matches more than just a literal string), there may be |
257 // overlap. | 264 // overlap. |
258 if (children.length > 1 && children.keys.any((sequence) => | 265 if (children.length > 1) { |
| 266 // Case-insensitivity means that even literals may match multiple entries. |
| 267 if (!_caseSensitive) return true; |
| 268 |
| 269 if (children.keys.any((sequence) => |
259 sequence.nodes.length > 1 || sequence.nodes.single is! LiteralNode)) { | 270 sequence.nodes.length > 1 || sequence.nodes.single is! LiteralNode)) { |
260 return true; | 271 return true; |
| 272 } |
261 } | 273 } |
262 | 274 |
263 return children.values.any((node) => node.canOverlap); | 275 return children.values.any((node) => node.canOverlap); |
264 } | 276 } |
265 | 277 |
266 /// Creates a node with no children and no validator. | 278 /// Creates a node with no children and no validator. |
267 _ListTreeNode() | 279 _ListTreeNode() |
268 : children = new Map<SequenceNode, _ListTreeNode>(), | 280 : children = new Map<SequenceNode, _ListTreeNode>(), |
269 _validator = null; | 281 _validator = null; |
270 | 282 |
271 /// Creates a recursive node the given [validator]. | 283 /// Creates a recursive node the given [validator]. |
272 _ListTreeNode.recursive(SequenceNode validator) | 284 _ListTreeNode.recursive(SequenceNode validator) |
273 : children = null, | 285 : children = null, |
274 _validator = new OptionsNode([validator]); | 286 _validator = new OptionsNode([validator], |
| 287 caseSensitive: validator.caseSensitive); |
275 | 288 |
276 /// Transforms this into recursive node, folding all its children into its | 289 /// Transforms this into recursive node, folding all its children into its |
277 /// validator. | 290 /// validator. |
278 void makeRecursive() { | 291 void makeRecursive() { |
279 if (isRecursive) return; | 292 if (isRecursive) return; |
280 _validator = new OptionsNode(children.keys.map((sequence) { | 293 _validator = new OptionsNode(children.keys.map((sequence) { |
281 var child = children[sequence]; | 294 var child = children[sequence]; |
282 child.makeRecursive(); | 295 child.makeRecursive(); |
283 return _join([sequence, child._validator]); | 296 return _join([sequence, child._validator]); |
284 })); | 297 }), caseSensitive: _caseSensitive); |
285 children = null; | 298 children = null; |
286 } | 299 } |
287 | 300 |
288 /// Adds [validator] to this node's existing validator. | 301 /// Adds [validator] to this node's existing validator. |
289 void addOption(SequenceNode validator) { | 302 void addOption(SequenceNode validator) { |
290 if (_validator == null) { | 303 if (_validator == null) { |
291 _validator = new OptionsNode([validator]); | 304 _validator = new OptionsNode([validator], |
| 305 caseSensitive: validator.caseSensitive); |
292 } else { | 306 } else { |
293 _validator.options.add(validator); | 307 _validator.options.add(validator); |
294 } | 308 } |
295 } | 309 } |
296 | 310 |
297 /// Lists all entities within [dir] matching this node or its children. | 311 /// Lists all entities within [dir] matching this node or its children. |
298 /// | 312 /// |
299 /// This may return duplicate entities. These will be filtered out in | 313 /// This may return duplicate entities. These will be filtered out in |
300 /// [ListTree.list]. | 314 /// [ListTree.list]. |
301 Stream<FileSystemEntity> list(String dir, {bool followLinks: true}) { | 315 Stream<FileSystemEntity> list(String dir, {bool followLinks: true}) { |
302 if (isRecursive) { | 316 if (isRecursive) { |
303 return new Directory(dir).list(recursive: true, followLinks: followLinks) | 317 return new Directory(dir).list(recursive: true, followLinks: followLinks) |
304 .where((entity) => _matches(entity.path.substring(dir.length + 1))); | 318 .where((entity) => _matches(p.relative(entity.path, from: dir))); |
305 } | 319 } |
306 | 320 |
307 var resultPool = new StreamPool(); | 321 var resultGroup = new StreamGroup<FileSystemEntity>(); |
308 | 322 |
309 // Don't spawn extra [Directory.list] calls when we already know exactly | 323 // Don't spawn extra [Directory.list] calls when we already know exactly |
310 // which subdirectories we're interested in. | 324 // which subdirectories we're interested in. |
311 if (_isIntermediate) { | 325 if (_isIntermediate) { |
312 children.forEach((sequence, child) { | 326 children.forEach((sequence, child) { |
313 resultPool.add(child.list(p.join(dir, sequence.nodes.single.text), | 327 resultGroup.add(child.list( |
| 328 p.join(dir, (sequence.nodes.single as LiteralNode).text), |
314 followLinks: followLinks)); | 329 followLinks: followLinks)); |
315 }); | 330 }); |
316 resultPool.closeWhenEmpty(); | 331 resultGroup.close(); |
317 return resultPool.stream; | 332 return resultGroup.stream; |
318 } | 333 } |
319 | 334 |
320 var resultController = new StreamController(sync: true); | 335 var resultController = new StreamController<FileSystemEntity>(sync: true); |
321 resultPool.add(resultController.stream); | 336 resultGroup.add(resultController.stream); |
322 new Directory(dir).list(followLinks: followLinks).listen((entity) { | 337 new Directory(dir).list(followLinks: followLinks).listen((entity) { |
323 var basename = entity.path.substring(dir.length + 1); | 338 var basename = p.relative(entity.path, from: dir); |
324 if (_matches(basename)) resultController.add(entity); | 339 if (_matches(basename)) resultController.add(entity); |
325 | 340 |
326 children.forEach((sequence, child) { | 341 children.forEach((sequence, child) { |
327 if (entity is! Directory) return; | 342 if (entity is! Directory) return; |
328 if (!sequence.matches(basename)) return; | 343 if (!sequence.matches(basename)) return; |
329 var stream = child.list(p.join(dir, basename), followLinks: followLinks) | 344 var stream = child.list(p.join(dir, basename), followLinks: followLinks) |
330 .handleError((_) {}, test: (error) { | 345 .handleError((_) {}, test: (error) { |
331 // Ignore errors from directories not existing. We do this here so | 346 // Ignore errors from directories not existing. We do this here so |
332 // that we only ignore warnings below wild cards. For example, the | 347 // 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 | 348 // glob "foo/bar/*/baz" should fail if "foo/bar" doesn't exist but |
334 // succeed if "foo/bar/qux/baz" doesn't exist. | 349 // succeed if "foo/bar/qux/baz" doesn't exist. |
335 return error is FileSystemException && | 350 return error is FileSystemException && |
336 (error.osError.errorCode == _ENOENT || | 351 (error.osError.errorCode == _ENOENT || |
337 error.osError.errorCode == _ENOENT_WIN); | 352 error.osError.errorCode == _ENOENT_WIN); |
338 }); | 353 }); |
339 resultPool.add(stream); | 354 resultGroup.add(stream); |
340 }); | 355 }); |
341 }, | 356 }, |
342 onError: resultController.addError, | 357 onError: resultController.addError, |
343 onDone: resultController.close); | 358 onDone: () { |
| 359 resultController.close(); |
| 360 resultGroup.close(); |
| 361 }); |
344 | 362 |
345 resultPool.closeWhenEmpty(); | 363 return resultGroup.stream; |
346 return resultPool.stream; | |
347 } | 364 } |
348 | 365 |
349 /// Synchronously lists all entities within [dir] matching this node or its | 366 /// Synchronously lists all entities within [dir] matching this node or its |
350 /// children. | 367 /// children. |
351 /// | 368 /// |
352 /// This may return duplicate entities. These will be filtered out in | 369 /// This may return duplicate entities. These will be filtered out in |
353 /// [ListTree.listSync]. | 370 /// [ListTree.listSync]. |
354 Iterable<FileSystemEntity> listSync(String dir, {bool followLinks: true}) { | 371 Iterable<FileSystemEntity> listSync(String dir, {bool followLinks: true}) { |
355 if (isRecursive) { | 372 if (isRecursive) { |
356 return new Directory(dir) | 373 return new Directory(dir) |
357 .listSync(recursive: true, followLinks: followLinks) | 374 .listSync(recursive: true, followLinks: followLinks) |
358 .where((entity) => _matches(entity.path.substring(dir.length + 1))); | 375 .where((entity) => _matches(p.relative(entity.path, from: dir))); |
359 } | 376 } |
360 | 377 |
361 // Don't spawn extra [Directory.listSync] calls when we already know exactly | 378 // Don't spawn extra [Directory.listSync] calls when we already know exactly |
362 // which subdirectories we're interested in. | 379 // which subdirectories we're interested in. |
363 if (_isIntermediate) { | 380 if (_isIntermediate) { |
364 return children.keys.expand((sequence) { | 381 return children.keys.expand((sequence) { |
365 return children[sequence].listSync( | 382 return children[sequence].listSync( |
366 p.join(dir, sequence.nodes.single.text), followLinks: followLinks); | 383 p.join(dir, (sequence.nodes.single as LiteralNode).text), |
| 384 followLinks: followLinks); |
367 }); | 385 }); |
368 } | 386 } |
369 | 387 |
370 return new Directory(dir).listSync(followLinks: followLinks) | 388 return new Directory(dir).listSync(followLinks: followLinks) |
371 .expand((entity) { | 389 .expand((entity) { |
372 var entities = []; | 390 var entities = <FileSystemEntity>[]; |
373 var basename = entity.path.substring(dir.length + 1); | 391 var basename = p.relative(entity.path, from: dir); |
374 if (_matches(basename)) entities.add(entity); | 392 if (_matches(basename)) entities.add(entity); |
375 if (entity is! Directory) return entities; | 393 if (entity is! Directory) return entities; |
376 | 394 |
377 entities.addAll(children.keys | 395 entities.addAll(children.keys |
378 .where((sequence) => sequence.matches(basename)) | 396 .where((sequence) => sequence.matches(basename)) |
379 .expand((sequence) { | 397 .expand((sequence) { |
380 try { | 398 try { |
381 return children[sequence].listSync( | 399 return children[sequence].listSync( |
382 p.join(dir, basename), followLinks: followLinks).toList(); | 400 p.join(dir, basename), followLinks: followLinks).toList(); |
383 } on FileSystemException catch (error) { | 401 } on FileSystemException catch (error) { |
(...skipping 20 matching lines...) Expand all Loading... |
404 return _validator.matches(toPosixPath(p.context, path)); | 422 return _validator.matches(toPosixPath(p.context, path)); |
405 } | 423 } |
406 | 424 |
407 String toString() => "($_validator) $children"; | 425 String toString() => "($_validator) $children"; |
408 } | 426 } |
409 | 427 |
410 /// Joins each [components] into a new glob where each component is separated by | 428 /// Joins each [components] into a new glob where each component is separated by |
411 /// a path separator. | 429 /// a path separator. |
412 SequenceNode _join(Iterable<AstNode> components) { | 430 SequenceNode _join(Iterable<AstNode> components) { |
413 var componentsList = components.toList(); | 431 var componentsList = components.toList(); |
414 var nodes = [componentsList.removeAt(0)]; | 432 var first = componentsList.removeAt(0); |
| 433 var nodes = [first]; |
415 for (var component in componentsList) { | 434 for (var component in componentsList) { |
416 nodes.add(new LiteralNode('/')); | 435 nodes.add(new LiteralNode('/', caseSensitive: first.caseSensitive)); |
417 nodes.add(component); | 436 nodes.add(component); |
418 } | 437 } |
419 return new SequenceNode(nodes); | 438 return new SequenceNode(nodes, caseSensitive: first.caseSensitive); |
420 } | 439 } |
OLD | NEW |