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