Line data Source code
1 : // Copyright 2026 The Authors. See the AUTHORS file for details.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // https://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : import 'package:betto_common/collections.dart' show Stack;
16 : import 'package:characters/characters.dart';
17 :
18 : import 'core_rules.dart';
19 : import 'parse.dart';
20 :
21 : /// Visitor interface for traversing ABNF grammar [Element] nodes.
22 : abstract class ElementVisitor<R> {
23 : R visitAlternativeLiterals(AlternativeLiterals element);
24 : R visitAlternatives(Alternatives element);
25 : R visitConcatenation(Concatenation element);
26 : R visitGroup(Group element);
27 : R visitLiteralElement(LiteralElement element);
28 : R visitOptionalSequence(OptionalSequence element);
29 : R visitRepetition(Repetition element);
30 : R visitSequence(Sequence element);
31 : R visitRule(Rule element);
32 : R visitGrammar(Grammar element);
33 : R visitValueRange(ValueRange element);
34 : R visitCharacterElement(CharacterElement element);
35 : R visitEmptyElement(EmptyElement element);
36 : R visitNegativeLookahead(NegativeLookahead element);
37 :
38 1 : R visitElement(Element element) => switch (element) {
39 1 : AlternativeLiterals _ => visitAlternativeLiterals(element),
40 2 : Alternatives _ => visitAlternatives(element),
41 1 : Concatenation _ => visitConcatenation(element),
42 2 : Group _ => visitGroup(element),
43 2 : LiteralElement _ => visitLiteralElement(element),
44 2 : CharacterElement _ => visitCharacterElement(element),
45 2 : OptionalSequence _ => visitOptionalSequence(element),
46 2 : Repetition _ => visitRepetition(element),
47 1 : Sequence _ => visitSequence(element),
48 2 : ValueRange _ => visitValueRange(element),
49 2 : Grammar _ => visitGrammar(element),
50 2 : Rule _ => visitRule(element),
51 0 : EmptyElement _ => visitEmptyElement(element),
52 0 : NegativeLookahead _ => visitNegativeLookahead(element),
53 : };
54 : }
55 :
56 : /// The base representation of an ABNF grammar element.
57 : sealed class Element {
58 : /// Attempts to parse the [source] string matching this element.
59 : ///
60 : /// Returns a [ParseResult] containing the parsed lexeme and remaining string
61 : /// on success. On failure, returns a failed [ParseResult].
62 : ParseResult parse(String source);
63 :
64 : /// Accepts an [ElementVisitor] for traversing the grammar tree.
65 : void accept(ElementVisitor visitor);
66 :
67 : /// An optional human-readable description of this element.
68 : String? get description;
69 : }
70 :
71 : /// Represents a complete ABNF grammar starting from an entry rule.
72 : final class Grammar implements Element {
73 : /// The unique name of this grammar.
74 : final String name;
75 :
76 : @override
77 : final String? description;
78 :
79 : /// The entry point [Rule] for parsing.
80 : final Rule entryRule;
81 :
82 4 : @Deprecated('Use grammar() factory instead.')
83 : Grammar(this.name, this.entryRule, {this.description});
84 :
85 0 : Rule get element => entryRule;
86 :
87 4 : @override
88 16 : String toString() => '$name = ${entryRule.name}';
89 :
90 : /// Alias for [entryRule].
91 0 : Rule get value => entryRule;
92 :
93 4 : @override
94 : ParseResult parse(String source) {
95 8 : final result = entryRule.parse(source);
96 8 : if (result.remaining.isNotEmpty) {
97 : // The full source was not consumed so the parsing has failed
98 4 : return ParseResult(
99 : false,
100 4 : result.remaining,
101 4 : lexeme: result.lexeme,
102 4 : ruleName: name,
103 4 : element: toString(),
104 8 : stack: Stack<ParseResult>()..push(result),
105 : );
106 : }
107 4 : return ParseResult(
108 4 : result.success,
109 4 : result.remaining,
110 4 : lexeme: result.lexeme,
111 4 : ruleName: name,
112 4 : element: toString(),
113 8 : stack: Stack<ParseResult>()..push(result),
114 : );
115 : }
116 :
117 0 : @override
118 0 : void accept(ElementVisitor visitor) => visitor.visitGrammar(this);
119 : }
120 :
121 4 : Grammar grammar(String name, Rule entryRule, {String? description}) =>
122 : // ignore: deprecated_member_use_from_same_package
123 4 : Grammar(name, entryRule, description: description);
124 :
125 : /// A named grammar rule combining a name and an underlying [Element].
126 : final class Rule implements Element {
127 : final String name;
128 : final Element element;
129 : @override
130 : final String? description;
131 :
132 4 : @Deprecated('Use rule() factory instead.')
133 : Rule(this.name, this.element, {this.description});
134 :
135 4 : @override
136 : String toString() =>
137 24 : '$name = ${element is Rule ? (element as Rule).name : element}';
138 :
139 4 : @override
140 : ParseResult parse(String source) {
141 8 : final result = element.parse(source);
142 :
143 4 : if (!result.success) {
144 3 : return ParseResult(
145 : false,
146 : source,
147 3 : ruleName: name,
148 3 : element: toString(),
149 6 : stack: Stack<ParseResult>()..push(result),
150 : );
151 : }
152 :
153 20 : final lexeme = source.substring(0, source.length - result.remaining.length);
154 :
155 4 : return ParseResult(
156 4 : result.success,
157 4 : result.remaining,
158 : lexeme: lexeme,
159 4 : ruleName: name,
160 4 : element: toString(),
161 8 : stack: Stack<ParseResult>()..push(result),
162 : );
163 : }
164 :
165 3 : static final abnfRuleName = rule(
166 : 'rule',
167 2 : Concatenation([
168 1 : alpha,
169 6 : variableRepetition(alternatives([alpha, digit, literal('-')])),
170 : ]),
171 : );
172 :
173 0 : @override
174 0 : void accept(ElementVisitor visitor) => visitor.visitRule(this);
175 : }
176 :
177 : /// Creates a named [Rule] from a given grammar [element].
178 4 : Rule rule(String name, Element element, {String? description}) =>
179 : // ignore: deprecated_member_use_from_same_package
180 4 : Rule(name, element, description: description);
181 :
182 : /// Represents a single character (code point) element.
183 : final class CharacterElement implements Element {
184 : /// The 32-bit Unicode code point value.
185 : final int value;
186 : @override
187 : final String? description;
188 :
189 2 : CharacterElement(this.value, {this.description});
190 :
191 0 : @override
192 0 : void accept(ElementVisitor visitor) => visitor.visitCharacterElement(this);
193 :
194 2 : @override
195 : ParseResult parse(String source) {
196 2 : if (source.isEmpty) {
197 2 : return ParseResult(false, source, element: toString());
198 : }
199 :
200 4 : final rune = source.runes.first;
201 4 : if (rune == value) {
202 : // Consume exactly one rune. String.fromCharCodes reconstructs the
203 : // string correctly even if the rune required a surrogate pair.
204 2 : final lexeme = String.fromCharCode(rune);
205 2 : return ParseResult(
206 : true,
207 4 : source.substring(lexeme.length),
208 : lexeme: lexeme,
209 2 : element: toString(),
210 : );
211 : }
212 4 : return ParseResult(false, source, element: toString());
213 : }
214 :
215 2 : @override
216 : String toString() =>
217 10 : '%x${value.toRadixString(16).padLeft(2, '0').toUpperCase()}';
218 : }
219 :
220 2 : CharacterElement character(int value, {String? description}) =>
221 2 : CharacterElement(value, description: description);
222 :
223 : /// Represents a literal string (e.g., `"en"`).
224 : ///
225 : /// Per RFC 5234 §2.3, string literals in ABNF are case-**insensitive**
226 : /// by default. Set to `true` to opt into case-sensitive matching
227 : /// (equivalent to the `%s` prefix in RFC 7405).
228 : final class LiteralElement implements Element {
229 : final String value;
230 :
231 : /// Whether matching is case-sensitive.
232 : ///
233 : /// Per RFC 5234 §2.3, string literals in ABNF are case-**insensitive**
234 : /// by default. Set to `true` to opt into case-sensitive matching
235 : /// (equivalent to the `%s` prefix in RFC 7405).
236 : final bool caseSensitive;
237 :
238 : @override
239 : final String? description;
240 :
241 2 : LiteralElement(this.value, {this.caseSensitive = false, this.description});
242 :
243 2 : @override
244 : // RFC 7405: prefix %s for case-sensitive, %i (or no prefix) for insensitive.
245 8 : String toString() => caseSensitive ? '%s"$value"' : '"$value"';
246 :
247 2 : @override
248 : ParseResult parse(String source) {
249 2 : final matched = caseSensitive
250 2 : ? source.startsWith(value)
251 8 : : source.toLowerCase().startsWith(value.toLowerCase());
252 : if (matched) {
253 2 : return ParseResult(
254 : true,
255 6 : source.substring(value.length),
256 6 : lexeme: source.substring(0, value.length),
257 2 : element: toString(),
258 : );
259 : }
260 4 : return ParseResult(false, source, element: toString());
261 : }
262 :
263 0 : @override
264 0 : void accept(ElementVisitor visitor) => visitor.visitLiteralElement(this);
265 : }
266 :
267 : /// Creates a case-insensitive literal element (the RFC 5234 default).
268 2 : Element literal(String value, {String? description}) =>
269 2 : LiteralElement(value, description: description);
270 :
271 : /// Creates a case-sensitive literal element (equivalent to RFC 7405 `%s`).
272 1 : Element caseSensitiveLiteral(String value, {String? description}) =>
273 1 : LiteralElement(value, caseSensitive: true, description: description);
274 :
275 : /// Represents a list of alternative literal strings (e.g., `"en" / "de"`).
276 : final class AlternativeLiterals implements Element {
277 : /// The original (unmodified) values, used for display and for
278 : /// case-sensitive matching.
279 : final Set<String> values;
280 :
281 : /// Whether matching is case-sensitive.
282 : ///
283 : /// Per RFC 5234 §2.3, string literals in ABNF are case-**insensitive**
284 : /// by default. Set to `true` to opt into case-sensitive matching
285 : /// (equivalent to the `%s` prefix in RFC 7405).
286 : final bool caseSensitive;
287 :
288 : final bool jagged;
289 : final int minLength;
290 : @override
291 : final String? description;
292 :
293 : // Sort the strings by length - longest first.
294 : // This helps us be greedy when the literal list is jagged.
295 3 : static Set<String> _sortBySize(Iterable<String> literals) {
296 3 : final l = literals.toList(growable: false);
297 15 : l.sort((a, b) => b.length.compareTo(a.length));
298 3 : return Set<String>.of(l);
299 : }
300 :
301 6 : static bool _isJagged(Iterable<String> literals) => literals.any(
302 21 : (element) => element.characters.length != literals.first.characters.length,
303 : );
304 :
305 6 : static int _minLength(Iterable<String> literals) => literals.fold<int>(
306 9 : literals.first.characters.length,
307 18 : (min, e) => min < e.characters.length ? min : e.characters.length,
308 : );
309 :
310 3 : AlternativeLiterals(
311 : Iterable<String> literals, {
312 : this.caseSensitive = false,
313 : this.description,
314 3 : }) : values = _sortBySize(literals),
315 3 : jagged = _isJagged(literals),
316 3 : minLength = _minLength(literals);
317 :
318 3 : @override
319 : // RFC 7405: emit %s prefix for case-sensitive; bare quotes = case-insensitive.
320 : String toString() =>
321 3 : description ??
322 18 : values.map((e) => caseSensitive ? '%s"$e"' : '"$e"').join(' / ');
323 :
324 1 : ParseResult _parseJaggedSet(String source) {
325 2 : final sourceCmp = caseSensitive ? source : source.toLowerCase();
326 2 : for (final str in values) {
327 2 : final strCmp = caseSensitive ? str : str.toLowerCase();
328 1 : if (sourceCmp.startsWith(strCmp)) {
329 : // Return the slice from the original source to preserve input casing.
330 1 : return ParseResult(
331 : true,
332 2 : source.substring(str.length),
333 2 : lexeme: source.substring(0, str.length),
334 1 : element: toString(),
335 : );
336 : }
337 : }
338 0 : return ParseResult(false, source, element: toString());
339 : }
340 :
341 3 : ParseResult _parseUniformSet(String source) {
342 12 : if (source.characters.length < minLength) {
343 2 : return ParseResult(false, source, element: toString());
344 : }
345 12 : final slice = source.characters.take(minLength).toString();
346 6 : final sliceCmp = caseSensitive ? slice : slice.toLowerCase();
347 : // Build a normalised lookup set on demand (not stored, avoids extra field).
348 6 : final match = values.any(
349 12 : (v) => (caseSensitive ? v : v.toLowerCase()) == sliceCmp,
350 : );
351 : if (match) {
352 3 : return ParseResult(
353 : true,
354 6 : source.substring(slice.length),
355 : lexeme: slice,
356 3 : element: toString(),
357 : );
358 : }
359 4 : return ParseResult(false, source, element: toString());
360 : }
361 :
362 3 : @override
363 : ParseResult parse(String source) =>
364 7 : jagged ? _parseJaggedSet(source) : _parseUniformSet(source);
365 :
366 0 : @override
367 0 : void accept(ElementVisitor visitor) => visitor.visitAlternativeLiterals(this);
368 : }
369 :
370 : /// Creates a case-insensitive set of alternative literals (the RFC 5234 default).
371 3 : AlternativeLiterals alternativeLiterals(
372 : Iterable<String> value, {
373 : String? description,
374 3 : }) => AlternativeLiterals(value, description: description);
375 :
376 : /// Creates a case-sensitive set of alternative literals (equivalent to RFC 7405 `%s`).
377 0 : AlternativeLiterals caseSensitiveAlternativeLiterals(
378 : Iterable<String> value, {
379 : String? description,
380 0 : }) => AlternativeLiterals(value, caseSensitive: true, description: description);
381 :
382 : typedef ElementSequence = Iterable<Element>;
383 :
384 : /// A sequence of grammar elements that must be matched in order.
385 : final class Sequence implements Element {
386 : final ElementSequence elements;
387 : @override
388 : final String? description;
389 :
390 1 : Sequence(this.elements, {this.description});
391 :
392 1 : @override
393 : String toString() =>
394 1 : description ??
395 6 : elements.map((e) => e is Rule ? e.name : e.toString()).join(' ');
396 :
397 1 : @override
398 : ParseResult parse(String source) {
399 1 : final results = Stack<ParseResult>();
400 : var remaining = source;
401 :
402 2 : for (final element in elements) {
403 1 : final result = element.parse(remaining);
404 1 : results.push(result);
405 :
406 1 : if (!result.success) {
407 : // Backtrack: One part of the sequence failed, so the whole sequence fails.
408 : // We return the source as 'remaining' to allow the caller to retry other
409 : // paths if this sequence was part of an Alternatives.
410 1 : return ParseResult(
411 : false,
412 : remaining, // Original remaining before failure
413 4 : lexeme: source.substring(0, source.length - remaining.length),
414 1 : element: toString(),
415 : stack: results,
416 : );
417 : }
418 1 : remaining = result.remaining;
419 : }
420 1 : return ParseResult(
421 : true,
422 : remaining,
423 4 : lexeme: source.substring(0, source.length - remaining.length),
424 1 : element: toString(),
425 : stack: results,
426 : );
427 : }
428 :
429 0 : @override
430 0 : void accept(ElementVisitor visitor) => visitor.visitSequence(this);
431 : }
432 :
433 : /// Represents a concatenation of elements that must be matched in order (e.g., `foo bar`).
434 : final class Concatenation implements Element {
435 : final ElementSequence sequence;
436 : @override
437 : final String? description;
438 :
439 2 : Concatenation(this.sequence, {this.description});
440 :
441 2 : @override
442 : String toString() =>
443 13 : sequence.map((e) => e is Rule ? e.name : e.toString()).join(' ');
444 :
445 2 : @override
446 : ParseResult parse(String source) {
447 : // Delegate to the shared sequence parsing logic
448 6 : return sequence._parseSequenceWithBacktracking(source, toString());
449 : }
450 :
451 0 : @override
452 0 : void accept(ElementVisitor visitor) => visitor.visitConcatenation(this);
453 : }
454 :
455 1 : Concatenation concatenation(ElementSequence elements) =>
456 1 : Concatenation(elements);
457 :
458 : /// Represents a group of elements that must be matched together (e.g., `(foo bar)`).
459 : final class Group implements Element {
460 : final Sequence sequence;
461 : @override
462 : final String? description;
463 :
464 1 : Group(ElementSequence elements, {this.description})
465 1 : : sequence = Sequence(elements);
466 :
467 3 : ElementSequence get elements => sequence.elements;
468 :
469 1 : @override
470 2 : String toString() => '($sequence)';
471 :
472 1 : @override
473 2 : ParseResult parse(String source) => sequence.parse(source);
474 :
475 0 : @override
476 0 : void accept(ElementVisitor visitor) => visitor.visitGroup(this);
477 : }
478 :
479 2 : Group group(ElementSequence elements) => Group(elements);
480 :
481 : /// Represents an optional sequence of elements (e.g., `[foo bar]`).
482 : final class OptionalSequence implements Element {
483 : final Sequence sequence;
484 : @override
485 : final String? description;
486 :
487 1 : OptionalSequence(ElementSequence elements, {this.description})
488 1 : : sequence = Sequence(elements);
489 :
490 3 : ElementSequence get elements => sequence.elements;
491 :
492 1 : @override
493 2 : String toString() => '[$sequence]';
494 :
495 1 : @override
496 : ParseResult parse(String source) {
497 3 : final result = sequence.elements._parseSequenceWithBacktracking(
498 : source,
499 1 : toString(),
500 : );
501 :
502 1 : if (result.success) {
503 : return result;
504 : } else {
505 : // If the sequence parse failed, the optional sequence still succeeds,
506 : // but consumes nothing and returns an empty result.
507 1 : return ParseResult(
508 : true, // Success is true because it's optional
509 : source, // No input consumed, remaining is the original source
510 1 : element: toString(),
511 : lexeme: '', // No lexeme produced
512 1 : stack: Stack<ParseResult>(), // Empty stack
513 : );
514 : }
515 : }
516 :
517 : /// Returns the alternatives for backtracking: the sequence and an empty match.
518 0 : Iterable<Element> get asAlternatives => [sequence, EmptyElement(toString())];
519 :
520 0 : @override
521 0 : void accept(ElementVisitor visitor) => visitor.visitOptionalSequence(this);
522 : }
523 :
524 : class EmptyElement implements Element {
525 : @override
526 : final String? description;
527 0 : EmptyElement(this.description);
528 0 : @override
529 0 : ParseResult parse(String source) => ParseResult(
530 : true,
531 : source,
532 0 : element: toString(),
533 : lexeme: '',
534 0 : stack: Stack<ParseResult>(),
535 : );
536 0 : @override
537 : void accept(ElementVisitor visitor) {}
538 0 : @override
539 : String toString() => '[]';
540 : }
541 :
542 0 : OptionalSequence optionalSequence(ElementSequence elements) =>
543 0 : OptionalSequence(elements);
544 :
545 1 : OptionalSequence optional(ElementSequence elements) =>
546 1 : OptionalSequence(elements);
547 :
548 : /// Represents a negative lookahead assertion. Matches if the inner element fails.
549 : /// Consumes no input.
550 : final class NegativeLookahead implements Element {
551 : final Element element;
552 : @override
553 : final String? description;
554 :
555 0 : NegativeLookahead(this.element, {this.description});
556 :
557 0 : @override
558 0 : String toString() => '(?!$element)';
559 :
560 0 : @override
561 : ParseResult parse(String source) {
562 0 : final result = element.parse(source);
563 0 : if (!result.success) {
564 0 : return ParseResult(
565 : true,
566 : source, // consumes no input
567 0 : element: toString(),
568 : lexeme: '',
569 : );
570 : }
571 0 : return ParseResult(false, source, element: toString());
572 : }
573 :
574 0 : @override
575 0 : void accept(ElementVisitor visitor) => visitor.visitNegativeLookahead(this);
576 : }
577 :
578 0 : NegativeLookahead negativeLookahead(Element element, {String? description}) =>
579 0 : NegativeLookahead(element, description: description);
580 :
581 : /// Represents alternative rules that can be matched (e.g., `foo / bar` in RFC 5234).
582 : final class Alternatives implements Element {
583 : final ElementSequence elements;
584 : @override
585 : final String? description;
586 :
587 3 : Alternatives(this.elements, {this.description});
588 :
589 3 : @override
590 : String toString() =>
591 20 : elements.map((e) => e is Rule ? e.name : e.toString()).join(' / ');
592 :
593 2 : @override
594 : ParseResult parse(String source) {
595 4 : for (final element in elements) {
596 2 : final result = element.parse(source);
597 2 : if (result.success) {
598 : // Return the first successful match found.
599 : // Construct a new result attributed to this Alternatives rule,
600 : // pushing the successful sub-element's result onto its stack.
601 2 : final lexeme = source.substring(
602 : 0,
603 8 : source.length - result.remaining.length,
604 : );
605 2 : return ParseResult(
606 : true,
607 2 : result.remaining,
608 2 : element: toString(),
609 : lexeme: lexeme,
610 4 : stack: Stack<ParseResult>()..push(result),
611 : );
612 : }
613 : // If result.success is false, we continue to the next alternative (backtracking).
614 : }
615 :
616 : // If no alternatives succeeded, return failure.
617 4 : return ParseResult(false, source, element: toString());
618 : }
619 :
620 0 : @override
621 0 : void accept(ElementVisitor visitor) => visitor.visitAlternatives(this);
622 : }
623 :
624 6 : Alternatives alternatives(Iterable<Element> elements) => Alternatives(elements);
625 :
626 : /// Represents variable repetition of an element (e.g., `*foo` or `1*3foo`).
627 : final class Repetition implements Element {
628 : final Element element;
629 : final int min;
630 :
631 : @override
632 : final String? description;
633 :
634 : // If [max] is null, infinity is the maximum
635 : final int? max;
636 :
637 4 : Repetition(this.element, {this.min = 0, this.max, this.description});
638 :
639 4 : @override
640 : String toString() {
641 4 : final buffer = StringBuffer();
642 :
643 12 : if (min == max) {
644 4 : buffer.write(min);
645 : } else {
646 13 : buffer.write(min > 0 ? '$min*' : '*');
647 :
648 3 : if (max != null) {
649 4 : buffer.write(max!);
650 : }
651 : }
652 :
653 24 : buffer.write('(${element is Rule ? (element as Rule).name : element})');
654 4 : return buffer.toString();
655 : }
656 :
657 3 : @override
658 : ParseResult parse(String source) {
659 9 : if (min > source.length) {
660 1 : return ParseResult(false, source);
661 : }
662 :
663 3 : final results = Stack<ParseResult>();
664 :
665 : var remaining = source;
666 : var count = 0;
667 :
668 3 : final upper = max;
669 :
670 5 : while (remaining.isNotEmpty && (upper == null || count < upper)) {
671 6 : final result = element.parse(remaining);
672 3 : results.push(result);
673 3 : if (result.success) {
674 3 : count++;
675 3 : remaining = result.remaining;
676 : } else {
677 : // If the inner element fails but we've met the minimum requirement,
678 : // we stop repeating and return success.
679 6 : if (count >= min) {
680 : break;
681 : }
682 : // Otherwise, the entire repetition fails.
683 2 : return ParseResult(false, source, stack: results, element: toString());
684 : }
685 : }
686 :
687 6 : if (count < min) {
688 : // Didn't get the lower limit of repetitions
689 0 : return ParseResult(false, remaining, stack: results, element: toString());
690 : }
691 12 : final String lexeme = source.substring(0, source.length - remaining.length);
692 3 : return ParseResult(
693 : true,
694 : remaining,
695 : stack: results,
696 : lexeme: lexeme,
697 3 : element: toString(),
698 : );
699 : }
700 :
701 0 : @override
702 0 : void accept(ElementVisitor visitor) => visitor.visitRepetition(this);
703 : }
704 :
705 3 : Repetition variableRepetition(Element value, {int min = 0, int? max}) =>
706 3 : Repetition(value, min: min, max: max);
707 :
708 2 : Repetition repetition(Element value, int n) =>
709 2 : Repetition(value, min: n, max: n);
710 :
711 : /// Represents a range of values (e.g., `%x41-5A`).
712 : final class ValueRange implements Element {
713 : final int start;
714 : final int end;
715 : @override
716 : final String? description;
717 :
718 4 : ValueRange(this.start, this.end, {this.description});
719 :
720 4 : @override
721 : String toString() =>
722 28 : '%x${start.toRadixString(16).toUpperCase()}-${end.toRadixString(16).toUpperCase()}';
723 :
724 0 : AlternativeLiterals toAlternativeLiteral() {
725 0 : final alts = <String>[];
726 :
727 0 : for (int i = start; i <= end; i++) {
728 0 : alts.add(String.fromCharCode(i));
729 : }
730 0 : return alternativeLiterals(alts);
731 : }
732 :
733 4 : @override
734 : ParseResult parse(String source) {
735 : // Check if the source string is empty.
736 4 : if (source.isEmpty) {
737 2 : return ParseResult(false, source, element: toString());
738 : }
739 :
740 8 : final rune = source.runes.first;
741 :
742 : // Check if the 32-bit code point falls within the range.
743 16 : if (rune < start || rune > end) {
744 8 : return ParseResult(false, source, element: toString());
745 : }
746 :
747 : // Yield exactly one rune.
748 4 : final lexeme = String.fromCharCode(rune);
749 4 : return ParseResult(
750 : true,
751 8 : source.substring(lexeme.length),
752 4 : element: toString(),
753 : lexeme: lexeme,
754 : );
755 : }
756 :
757 0 : @override
758 0 : void accept(ElementVisitor visitor) => visitor.visitValueRange(this);
759 : }
760 :
761 8 : ValueRange valueRange(int start, int end) => ValueRange(start, end);
762 :
763 : extension _ParseSequenceExtension on ElementSequence {
764 : /// Parses a sequence of elements using backtracking to support alternative paths.
765 : ///
766 : /// Backtracking is required when a sequence contains [Alternatives] that might
767 : /// match different lengths of the input source. If one path fails later in the
768 : /// sequence, this will backtrack and attempt other alternative paths.
769 3 : ParseResult _parseSequenceWithBacktracking(
770 : String source,
771 : String ruleDescription,
772 : ) {
773 : // Helper function to parse a subsequence starting from a given index
774 3 : ParseResult parseSubsequence(String currentSource, int startIndex) {
775 3 : final Stack<ParseResult> successfulResults = Stack();
776 : String remainingSource = currentSource;
777 :
778 9 : for (int i = startIndex; i < length; i++) {
779 3 : final element = elementAt(i);
780 :
781 6 : if (element is Alternatives || element is OptionalSequence) {
782 0 : final alternatives = element is Alternatives
783 0 : ? element.elements
784 0 : : (element as OptionalSequence).asAlternatives;
785 : bool alternativeMatched = false;
786 0 : for (final alternativeElement in alternatives) {
787 0 : final altResult = alternativeElement.parse(remainingSource);
788 0 : if (altResult.success) {
789 : // Try parsing the rest of the sequence with this alternative's result
790 0 : final restResult = parseSubsequence(altResult.remaining, i + 1);
791 0 : if (restResult.success) {
792 : // Found a valid path
793 : // Combine altResult and restResult into the main stack
794 0 : successfulResults.push(altResult);
795 0 : successfulResults.pushAll(restResult.stack);
796 0 : remainingSource = restResult.remaining;
797 : alternativeMatched = true;
798 : break; // Found a working alternative, stop trying others
799 : }
800 : // Backtrack: This alternative didn't work for the rest of the sequence
801 : // Continue to the next alternative
802 : }
803 : }
804 : if (!alternativeMatched) {
805 : // No alternative allowed the rest of the sequence to parse
806 0 : return ParseResult(
807 : false,
808 : source,
809 : element: ruleDescription,
810 0 : stack: Stack<ParseResult>()..pushAll(successfulResults),
811 : );
812 : }
813 : } else {
814 : // Regular element (not Alternatives)
815 3 : final result = element.parse(remainingSource);
816 3 : if (result.success) {
817 3 : successfulResults.push(result);
818 3 : remainingSource = result.remaining;
819 : } else {
820 : // If any non-alternative element fails, the concatenation fails
821 3 : return ParseResult(
822 : false,
823 : source,
824 : element: ruleDescription,
825 6 : stack: Stack<ParseResult>()..pushAll(successfulResults),
826 : );
827 : }
828 : }
829 : }
830 :
831 : // If we reached here, the subsequence (from startIndex) parsed successfully
832 3 : final String lexeme = source.substring(
833 : 0,
834 9 : source.length - remainingSource.length,
835 : );
836 3 : return ParseResult(
837 : true,
838 : remainingSource,
839 : element: ruleDescription,
840 : lexeme: lexeme,
841 : stack: successfulResults,
842 : );
843 : }
844 :
845 : // Start parsing from the beginning of the sequence
846 3 : return parseSubsequence(source, 0);
847 : }
848 : }
|
