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.ast; | 5 library glob.ast; |
6 | 6 |
7 import 'package:path/path.dart' as p; | 7 import 'package:path/path.dart' as p; |
8 import 'package:collection/collection.dart'; | 8 import 'package:collection/collection.dart'; |
9 | 9 |
10 import 'utils.dart'; | 10 import 'utils.dart'; |
11 | 11 |
12 const _SEPARATOR = 0x2F; // "/" | 12 const _SEPARATOR = 0x2F; // "/" |
13 | 13 |
14 /// A node in the abstract syntax tree for a glob. | 14 /// A node in the abstract syntax tree for a glob. |
15 abstract class AstNode { | 15 abstract class AstNode { |
16 /// The cached regular expression that this AST was compiled into. | 16 /// The cached regular expression that this AST was compiled into. |
17 RegExp _regExp; | 17 RegExp _regExp; |
18 | 18 |
| 19 /// Whether this node matches case-sensitively or not. |
| 20 final bool caseSensitive; |
| 21 |
19 /// Whether this glob could match an absolute path. | 22 /// Whether this glob could match an absolute path. |
20 /// | 23 /// |
21 /// Either this or [canMatchRelative] or both will be true. | 24 /// Either this or [canMatchRelative] or both will be true. |
22 final bool canMatchAbsolute = false; | 25 final bool canMatchAbsolute = false; |
23 | 26 |
24 /// Whether this glob could match a relative path. | 27 /// Whether this glob could match a relative path. |
25 /// | 28 /// |
26 /// Either this or [canMatchRelative] or both will be true. | 29 /// Either this or [canMatchRelative] or both will be true. |
27 final bool canMatchRelative = true; | 30 final bool canMatchRelative = true; |
28 | 31 |
| 32 AstNode._(this.caseSensitive); |
| 33 |
29 /// Returns a new glob with all the options bubbled to the top level. | 34 /// Returns a new glob with all the options bubbled to the top level. |
30 /// | 35 /// |
31 /// In particular, this returns a glob AST with two guarantees: | 36 /// In particular, this returns a glob AST with two guarantees: |
32 /// | 37 /// |
33 /// 1. There are no [OptionsNode]s other than the one at the top level. | 38 /// 1. There are no [OptionsNode]s other than the one at the top level. |
34 /// 2. It matches the same set of paths as [this]. | 39 /// 2. It matches the same set of paths as [this]. |
35 /// | 40 /// |
36 /// For example, given the glob `{foo,bar}/{click/clack}`, this would return | 41 /// For example, given the glob `{foo,bar}/{click/clack}`, this would return |
37 /// `{foo/click,foo/clack,bar/click,bar/clack}`. | 42 /// `{foo/click,foo/clack,bar/click,bar/clack}`. |
38 OptionsNode flattenOptions() => new OptionsNode([new SequenceNode([this])]); | 43 OptionsNode flattenOptions() => new OptionsNode( |
| 44 [new SequenceNode([this], caseSensitive: caseSensitive)], |
| 45 caseSensitive: caseSensitive); |
39 | 46 |
40 /// Returns whether this glob matches [string]. | 47 /// Returns whether this glob matches [string]. |
41 bool matches(String string) { | 48 bool matches(String string) { |
42 if (_regExp == null) _regExp = new RegExp('^${_toRegExp()}\$'); | 49 if (_regExp == null) { |
| 50 _regExp = new RegExp('^${_toRegExp()}\$', caseSensitive: caseSensitive); |
| 51 } |
43 return _regExp.hasMatch(string); | 52 return _regExp.hasMatch(string); |
44 } | 53 } |
45 | 54 |
46 /// Subclasses should override this to return a regular expression component. | 55 /// Subclasses should override this to return a regular expression component. |
47 String _toRegExp(); | 56 String _toRegExp(); |
48 } | 57 } |
49 | 58 |
50 /// A sequence of adjacent AST nodes. | 59 /// A sequence of adjacent AST nodes. |
51 class SequenceNode extends AstNode { | 60 class SequenceNode extends AstNode { |
52 /// The nodes in the sequence. | 61 /// The nodes in the sequence. |
53 final List<AstNode> nodes; | 62 final List<AstNode> nodes; |
54 | 63 |
55 bool get canMatchAbsolute => nodes.first.canMatchAbsolute; | 64 bool get canMatchAbsolute => nodes.first.canMatchAbsolute; |
56 bool get canMatchRelative => nodes.first.canMatchRelative; | 65 bool get canMatchRelative => nodes.first.canMatchRelative; |
57 | 66 |
58 SequenceNode(Iterable<AstNode> nodes) | 67 SequenceNode(Iterable<AstNode> nodes, {bool caseSensitive: true}) |
59 : nodes = nodes.toList(); | 68 : nodes = nodes.toList(), |
| 69 super._(caseSensitive); |
60 | 70 |
61 OptionsNode flattenOptions() { | 71 OptionsNode flattenOptions() { |
62 if (nodes.isEmpty) return new OptionsNode([this]); | 72 if (nodes.isEmpty) { |
| 73 return new OptionsNode([this], caseSensitive: caseSensitive); |
| 74 } |
63 | 75 |
64 var sequences = nodes.first.flattenOptions().options | 76 var sequences = nodes.first.flattenOptions().options |
65 .map((sequence) => sequence.nodes); | 77 .map((sequence) => sequence.nodes); |
66 for (var node in nodes.skip(1)) { | 78 for (var node in nodes.skip(1)) { |
67 // Concatenate all sequences in the next options node ([nextSequences]) | 79 // Concatenate all sequences in the next options node ([nextSequences]) |
68 // onto all previous sequences ([sequences]). | 80 // onto all previous sequences ([sequences]). |
69 var nextSequences = node.flattenOptions().options; | 81 var nextSequences = node.flattenOptions().options; |
70 sequences = sequences.expand((sequence) { | 82 sequences = sequences.expand((sequence) { |
71 return nextSequences.map((nextSequence) { | 83 return nextSequences.map((nextSequence) { |
72 return sequence.toList()..addAll(nextSequence.nodes); | 84 return sequence.toList()..addAll(nextSequence.nodes); |
73 }); | 85 }); |
74 }); | 86 }); |
75 } | 87 } |
76 | 88 |
77 return new OptionsNode(sequences.map((sequence) { | 89 return new OptionsNode(sequences.map((sequence) { |
78 // Combine any adjacent LiteralNodes in [sequence]. | 90 // Combine any adjacent LiteralNodes in [sequence]. |
79 return new SequenceNode(sequence.fold([], (combined, node) { | 91 return new SequenceNode(sequence.fold([], (combined, node) { |
80 if (combined.isEmpty || combined.last is! LiteralNode || | 92 if (combined.isEmpty || combined.last is! LiteralNode || |
81 node is! LiteralNode) { | 93 node is! LiteralNode) { |
82 return combined..add(node); | 94 return combined..add(node); |
83 } | 95 } |
84 | 96 |
85 combined[combined.length - 1] = | 97 combined[combined.length - 1] = new LiteralNode( |
86 new LiteralNode(combined.last.text + node.text); | 98 combined.last.text + node.text, caseSensitive: caseSensitive); |
87 return combined; | 99 return combined; |
88 })); | 100 }), caseSensitive: caseSensitive); |
89 })); | 101 }), caseSensitive: caseSensitive); |
90 } | 102 } |
91 | 103 |
92 /// Splits this glob into components along its path separators. | 104 /// Splits this glob into components along its path separators. |
93 /// | 105 /// |
94 /// For example, given the glob `foo/*/*.dart`, this would return three globs: | 106 /// For example, given the glob `foo/*/*.dart`, this would return three globs: |
95 /// `foo`, `*`, and `*.dart`. | 107 /// `foo`, `*`, and `*.dart`. |
96 /// | 108 /// |
97 /// Path separators within options nodes are not split. For example, | 109 /// Path separators within options nodes are not split. For example, |
98 /// `foo/{bar,baz/bang}/qux` will return three globs: `foo`, `{bar,baz/bang}`, | 110 /// `foo/{bar,baz/bang}/qux` will return three globs: `foo`, `{bar,baz/bang}`, |
99 /// and `qux`. | 111 /// and `qux`. |
100 /// | 112 /// |
101 /// [context] is used to determine what absolute roots look like for this | 113 /// [context] is used to determine what absolute roots look like for this |
102 /// glob. | 114 /// glob. |
103 List<SequenceNode> split(p.Context context) { | 115 List<SequenceNode> split(p.Context context) { |
104 var componentsToReturn = []; | 116 var componentsToReturn = []; |
105 var currentComponent; | 117 var currentComponent; |
106 | 118 |
107 addNode(node) { | 119 addNode(node) { |
108 if (currentComponent == null) currentComponent = []; | 120 if (currentComponent == null) currentComponent = []; |
109 currentComponent.add(node); | 121 currentComponent.add(node); |
110 } | 122 } |
111 | 123 |
112 finishComponent() { | 124 finishComponent() { |
113 if (currentComponent == null) return; | 125 if (currentComponent == null) return; |
114 componentsToReturn.add(new SequenceNode(currentComponent)); | 126 componentsToReturn.add( |
| 127 new SequenceNode(currentComponent, caseSensitive: caseSensitive)); |
115 currentComponent = null; | 128 currentComponent = null; |
116 } | 129 } |
117 | 130 |
118 for (var node in nodes) { | 131 for (var node in nodes) { |
119 if (node is! LiteralNode || !node.text.contains('/')) { | 132 if (node is! LiteralNode || !node.text.contains('/')) { |
120 addNode(node); | 133 addNode(node); |
121 continue; | 134 continue; |
122 } | 135 } |
123 | 136 |
124 var text = node.text; | 137 var text = node.text; |
125 if (context.style == p.Style.windows) text = text.replaceAll("/", "\\"); | 138 if (context.style == p.Style.windows) text = text.replaceAll("/", "\\"); |
126 var components = context.split(text); | 139 var components = context.split(text); |
127 | 140 |
128 // If the first component is absolute, that means it's a separator (on | 141 // If the first component is absolute, that means it's a separator (on |
129 // Windows some non-separator things are also absolute, but it's invalid | 142 // Windows some non-separator things are also absolute, but it's invalid |
130 // to have "C:" show up in the middle of a path anyway). | 143 // to have "C:" show up in the middle of a path anyway). |
131 if (context.isAbsolute(components.first)) { | 144 if (context.isAbsolute(components.first)) { |
132 // If this is the first component, it's the root. | 145 // If this is the first component, it's the root. |
133 if (componentsToReturn.isEmpty && currentComponent == null) { | 146 if (componentsToReturn.isEmpty && currentComponent == null) { |
134 var root = components.first; | 147 var root = components.first; |
135 if (context.style == p.Style.windows) { | 148 if (context.style == p.Style.windows) { |
136 // Above, we switched to backslashes to make [context.split] handle | 149 // Above, we switched to backslashes to make [context.split] handle |
137 // roots properly. That means that if there is a root, it'll still | 150 // roots properly. That means that if there is a root, it'll still |
138 // have backslashes, where forward slashes are required for globs. | 151 // have backslashes, where forward slashes are required for globs. |
139 // So we switch it back here. | 152 // So we switch it back here. |
140 root = root.replaceAll("\\", "/"); | 153 root = root.replaceAll("\\", "/"); |
141 } | 154 } |
142 addNode(new LiteralNode(root)); | 155 addNode(new LiteralNode(root, caseSensitive: caseSensitive)); |
143 } | 156 } |
144 finishComponent(); | 157 finishComponent(); |
145 components = components.skip(1); | 158 components = components.skip(1); |
146 if (components.isEmpty) continue; | 159 if (components.isEmpty) continue; |
147 } | 160 } |
148 | 161 |
149 // For each component except the last one, add a separate sequence to | 162 // For each component except the last one, add a separate sequence to |
150 // [sequences] containing only that component. | 163 // [sequences] containing only that component. |
151 for (var component in components.take(components.length - 1)) { | 164 for (var component in components.take(components.length - 1)) { |
152 addNode(new LiteralNode(component)); | 165 addNode(new LiteralNode(component, caseSensitive: caseSensitive)); |
153 finishComponent(); | 166 finishComponent(); |
154 } | 167 } |
155 | 168 |
156 // For the final component, only end its sequence (by adding a new empty | 169 // For the final component, only end its sequence (by adding a new empty |
157 // sequence) if it ends with a separator. | 170 // sequence) if it ends with a separator. |
158 addNode(new LiteralNode(components.last)); | 171 addNode(new LiteralNode(components.last, caseSensitive: caseSensitive)); |
159 if (node.text.endsWith('/')) finishComponent(); | 172 if (node.text.endsWith('/')) finishComponent(); |
160 } | 173 } |
161 | 174 |
162 finishComponent(); | 175 finishComponent(); |
163 return componentsToReturn; | 176 return componentsToReturn; |
164 } | 177 } |
165 | 178 |
166 String _toRegExp() => nodes.map((node) => node._toRegExp()).join(); | 179 String _toRegExp() => nodes.map((node) => node._toRegExp()).join(); |
167 | 180 |
168 bool operator==(Object other) => other is SequenceNode && | 181 bool operator==(Object other) => other is SequenceNode && |
169 const IterableEquality().equals(nodes, other.nodes); | 182 const IterableEquality().equals(nodes, other.nodes); |
170 | 183 |
171 int get hashCode => const IterableEquality().hash(nodes); | 184 int get hashCode => const IterableEquality().hash(nodes); |
172 | 185 |
173 String toString() => nodes.join(); | 186 String toString() => nodes.join(); |
174 } | 187 } |
175 | 188 |
176 /// A node matching zero or more non-separator characters. | 189 /// A node matching zero or more non-separator characters. |
177 class StarNode extends AstNode { | 190 class StarNode extends AstNode { |
178 StarNode(); | 191 StarNode({bool caseSensitive: true}) : super._(caseSensitive); |
179 | 192 |
180 String _toRegExp() => '[^/]*'; | 193 String _toRegExp() => '[^/]*'; |
181 | 194 |
182 bool operator==(Object other) => other is StarNode; | 195 bool operator==(Object other) => other is StarNode; |
183 | 196 |
184 int get hashCode => 0; | 197 int get hashCode => 0; |
185 | 198 |
186 String toString() => '*'; | 199 String toString() => '*'; |
187 } | 200 } |
188 | 201 |
189 /// A node matching zero or more characters that may be separators. | 202 /// A node matching zero or more characters that may be separators. |
190 class DoubleStarNode extends AstNode { | 203 class DoubleStarNode extends AstNode { |
191 /// The path context for the glob. | 204 /// The path context for the glob. |
192 /// | 205 /// |
193 /// This is used to determine what absolute paths look like. | 206 /// This is used to determine what absolute paths look like. |
194 final p.Context _context; | 207 final p.Context _context; |
195 | 208 |
196 DoubleStarNode(this._context); | 209 DoubleStarNode(this._context, {bool caseSensitive: true}) |
| 210 : super._(caseSensitive); |
197 | 211 |
198 String _toRegExp() { | 212 String _toRegExp() { |
199 // Double star shouldn't match paths with a leading "../", since these paths | 213 // Double star shouldn't match paths with a leading "../", since these paths |
200 // wouldn't be listed with this glob. We only check for "../" at the | 214 // wouldn't be listed with this glob. We only check for "../" at the |
201 // beginning since the paths are normalized before being checked against the | 215 // beginning since the paths are normalized before being checked against the |
202 // glob. | 216 // glob. |
203 var buffer = new StringBuffer()..write(r'(?!^(?:\.\./|'); | 217 var buffer = new StringBuffer()..write(r'(?!^(?:\.\./|'); |
204 | 218 |
205 // A double star at the beginning of the glob also shouldn't match absolute | 219 // A double star at the beginning of the glob also shouldn't match absolute |
206 // paths, since those also wouldn't be listed. Which root patterns we look | 220 // paths, since those also wouldn't be listed. Which root patterns we look |
(...skipping 15 matching lines...) Expand all Loading... |
222 | 236 |
223 bool operator==(Object other) => other is DoubleStarNode; | 237 bool operator==(Object other) => other is DoubleStarNode; |
224 | 238 |
225 int get hashCode => 1; | 239 int get hashCode => 1; |
226 | 240 |
227 String toString() => '**'; | 241 String toString() => '**'; |
228 } | 242 } |
229 | 243 |
230 /// A node matching a single non-separator character. | 244 /// A node matching a single non-separator character. |
231 class AnyCharNode extends AstNode { | 245 class AnyCharNode extends AstNode { |
232 AnyCharNode(); | 246 AnyCharNode({bool caseSensitive: true}) : super._(caseSensitive); |
233 | 247 |
234 String _toRegExp() => '[^/]'; | 248 String _toRegExp() => '[^/]'; |
235 | 249 |
236 bool operator==(Object other) => other is AnyCharNode; | 250 bool operator==(Object other) => other is AnyCharNode; |
237 | 251 |
238 int get hashCode => 2; | 252 int get hashCode => 2; |
239 | 253 |
240 String toString() => '?'; | 254 String toString() => '?'; |
241 } | 255 } |
242 | 256 |
243 /// A node matching a single character in a range of options. | 257 /// A node matching a single character in a range of options. |
244 class RangeNode extends AstNode { | 258 class RangeNode extends AstNode { |
245 /// The ranges matched by this node. | 259 /// The ranges matched by this node. |
246 /// | 260 /// |
247 /// The ends of the ranges are unicode code points. | 261 /// The ends of the ranges are unicode code points. |
248 final Set<Range> ranges; | 262 final Set<Range> ranges; |
249 | 263 |
250 /// Whether this range was negated. | 264 /// Whether this range was negated. |
251 final bool negated; | 265 final bool negated; |
252 | 266 |
253 RangeNode(Iterable<Range> ranges, {this.negated}) | 267 RangeNode(Iterable<Range> ranges, {this.negated, bool caseSensitive: true}) |
254 : ranges = ranges.toSet(); | 268 : ranges = ranges.toSet(), |
| 269 super._(caseSensitive); |
255 | 270 |
256 OptionsNode flattenOptions() { | 271 OptionsNode flattenOptions() { |
257 if (negated || ranges.any((range) => !range.isSingleton)) { | 272 if (negated || ranges.any((range) => !range.isSingleton)) { |
258 return super.flattenOptions(); | 273 return super.flattenOptions(); |
259 } | 274 } |
260 | 275 |
261 // If a range explicitly lists a set of characters, return each character as | 276 // If a range explicitly lists a set of characters, return each character as |
262 // a separate expansion. | 277 // a separate expansion. |
263 return new OptionsNode(ranges.map((range) { | 278 return new OptionsNode(ranges.map((range) { |
264 return new SequenceNode([ | 279 return new SequenceNode([ |
265 new LiteralNode(new String.fromCharCodes([range.min])) | 280 new LiteralNode(new String.fromCharCodes([range.min]), |
266 ]); | 281 caseSensitive: caseSensitive) |
267 })); | 282 ], caseSensitive: caseSensitive); |
| 283 }), caseSensitive: caseSensitive); |
268 } | 284 } |
269 | 285 |
270 String _toRegExp() { | 286 String _toRegExp() { |
271 var buffer = new StringBuffer(); | 287 var buffer = new StringBuffer(); |
272 | 288 |
273 var containsSeparator = ranges.any((range) => range.contains(_SEPARATOR)); | 289 var containsSeparator = ranges.any((range) => range.contains(_SEPARATOR)); |
274 if (!negated && containsSeparator) { | 290 if (!negated && containsSeparator) { |
275 // Add `(?!/)` because ranges are never allowed to match separators. | 291 // Add `(?!/)` because ranges are never allowed to match separators. |
276 buffer.write('(?!/)'); | 292 buffer.write('(?!/)'); |
277 } | 293 } |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
318 } | 334 } |
319 | 335 |
320 /// A node that matches one of several options. | 336 /// A node that matches one of several options. |
321 class OptionsNode extends AstNode { | 337 class OptionsNode extends AstNode { |
322 /// The options to match. | 338 /// The options to match. |
323 final List<SequenceNode> options; | 339 final List<SequenceNode> options; |
324 | 340 |
325 bool get canMatchAbsolute => options.any((node) => node.canMatchAbsolute); | 341 bool get canMatchAbsolute => options.any((node) => node.canMatchAbsolute); |
326 bool get canMatchRelative => options.any((node) => node.canMatchRelative); | 342 bool get canMatchRelative => options.any((node) => node.canMatchRelative); |
327 | 343 |
328 OptionsNode(Iterable<SequenceNode> options) | 344 OptionsNode(Iterable<SequenceNode> options, {bool caseSensitive: true}) |
329 : options = options.toList(); | 345 : options = options.toList(), |
| 346 super._(caseSensitive); |
330 | 347 |
331 OptionsNode flattenOptions() => new OptionsNode( | 348 OptionsNode flattenOptions() => new OptionsNode( |
332 options.expand((option) => option.flattenOptions().options)); | 349 options.expand((option) => option.flattenOptions().options), |
| 350 caseSensitive: caseSensitive); |
333 | 351 |
334 String _toRegExp() => | 352 String _toRegExp() => |
335 '(?:${options.map((option) => option._toRegExp()).join("|")})'; | 353 '(?:${options.map((option) => option._toRegExp()).join("|")})'; |
336 | 354 |
337 bool operator==(Object other) => other is OptionsNode && | 355 bool operator==(Object other) => other is OptionsNode && |
338 const UnorderedIterableEquality().equals(options, other.options); | 356 const UnorderedIterableEquality().equals(options, other.options); |
339 | 357 |
340 int get hashCode => const UnorderedIterableEquality().hash(options); | 358 int get hashCode => const UnorderedIterableEquality().hash(options); |
341 | 359 |
342 String toString() => '{${options.join(',')}}'; | 360 String toString() => '{${options.join(',')}}'; |
(...skipping 10 matching lines...) Expand all Loading... |
353 final p.Context _context; | 371 final p.Context _context; |
354 | 372 |
355 bool get canMatchAbsolute { | 373 bool get canMatchAbsolute { |
356 var nativeText = _context.style == p.Style.windows ? | 374 var nativeText = _context.style == p.Style.windows ? |
357 text.replaceAll('/', '\\') : text; | 375 text.replaceAll('/', '\\') : text; |
358 return _context.isAbsolute(nativeText); | 376 return _context.isAbsolute(nativeText); |
359 } | 377 } |
360 | 378 |
361 bool get canMatchRelative => !canMatchAbsolute; | 379 bool get canMatchRelative => !canMatchAbsolute; |
362 | 380 |
363 LiteralNode(this.text, [this._context]); | 381 LiteralNode(this.text, {p.Context context, bool caseSensitive: true}) |
| 382 : _context = context, |
| 383 super._(caseSensitive); |
364 | 384 |
365 String _toRegExp() => regExpQuote(text); | 385 String _toRegExp() => regExpQuote(text); |
366 | 386 |
367 bool operator==(Object other) => other is LiteralNode && other.text == text; | 387 bool operator==(Object other) => other is LiteralNode && other.text == text; |
368 | 388 |
369 int get hashCode => text.hashCode; | 389 int get hashCode => text.hashCode; |
370 | 390 |
371 String toString() => text; | 391 String toString() => text; |
372 } | 392 } |
OLD | NEW |