1 #ifndef CTRE__EVALUATION__HPP
2 #define CTRE__EVALUATION__HPP
3
4 #include "flags_and_modes.hpp"
5 #include "atoms.hpp"
6 #include "atoms_unicode.hpp"
7 #include "starts_with_anchor.hpp"
8 #include "utility.hpp"
9 #include "return_type.hpp"
10 #include "find_captures.hpp"
11 #include "first.hpp"
12 #include <iterator>
13
14 // remove me when MSVC fix the constexpr bug
15 #ifdef _MSC_VER
16 #ifndef CTRE_MSVC_GREEDY_WORKAROUND
17 #define CTRE_MSVC_GREEDY_WORKAROUND
18 #endif
19 #endif
20
21 namespace ctre {
22
less_than_or_infinite(size_t i)23 template <size_t Limit> constexpr CTRE_FORCE_INLINE bool less_than_or_infinite(size_t i) {
24 if constexpr (Limit == 0) {
25 // infinite
26 return true;
27 } else {
28 return i < Limit;
29 }
30 }
31
less_than(size_t i)32 template <size_t Limit> constexpr CTRE_FORCE_INLINE bool less_than(size_t i) {
33 if constexpr (Limit == 0) {
34 // infinite
35 return false;
36 } else {
37 return i < Limit;
38 }
39 }
40
is_bidirectional(const std::bidirectional_iterator_tag &)41 constexpr bool is_bidirectional(const std::bidirectional_iterator_tag &) { return true; }
is_bidirectional(...)42 constexpr bool is_bidirectional(...) { return false; }
43
44 // sink for making the errors shorter
45 template <typename R, typename Iterator, typename EndIterator>
46 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator, Iterator, const EndIterator, flags, R, ...) noexcept = delete;
47
48 // if we found "accept" object on stack => ACCEPT
49 template <typename R, typename Iterator, typename EndIterator>
evaluate(const Iterator,Iterator,const EndIterator,flags,R captures,ctll::list<accept>)50 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator, Iterator, const EndIterator, flags, R captures, ctll::list<accept>) noexcept {
51 return captures.matched();
52 }
53
54 // if we found "reject" object on stack => REJECT
55 template <typename R, typename... Rest, typename Iterator, typename EndIterator>
evaluate(const Iterator,Iterator,const EndIterator,flags,R,ctll::list<reject,Rest...>)56 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator, Iterator, const EndIterator, flags, R, ctll::list<reject, Rest...>) noexcept {
57 return not_matched;
58 }
59
60 // mark start of outer capture
61 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<start_mark,Tail...>)62 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<start_mark, Tail...>) noexcept {
63 return evaluate(begin, current, end, f, captures.set_start_mark(current), ctll::list<Tail...>());
64 }
65
66 // mark end of outer capture
67 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<end_mark,Tail...>)68 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<end_mark, Tail...>) noexcept {
69 return evaluate(begin, current, end, f, captures.set_end_mark(current), ctll::list<Tail...>());
70 }
71
72 // mark end of cycle
73 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
evaluate(const Iterator,Iterator current,const EndIterator,const flags & f,R captures,ctll::list<end_cycle_mark>)74 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator, Iterator current, const EndIterator, [[maybe_unused]] const flags & f, R captures, ctll::list<end_cycle_mark>) noexcept {
75 if (cannot_be_empty_match(f)) {
76 return not_matched;
77 }
78
79 return captures.set_end_mark(current).matched();
80 }
81
82 // matching everything which behave as a one character matcher
83
84 template <typename R, typename Iterator, typename EndIterator, typename CharacterLike, typename... Tail, typename = std::enable_if_t<(MatchesCharacter<CharacterLike>::template value<decltype(*std::declval<Iterator>())>)>>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<CharacterLike,Tail...>)85 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<CharacterLike, Tail...>) noexcept {
86 if (current == end) return not_matched;
87 if (!CharacterLike::match_char(*current)) return not_matched;
88
89 return evaluate(begin, ++current, end, consumed_something(f), captures, ctll::list<Tail...>());
90 }
91
92 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<any,Tail...>)93 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<any, Tail...>) noexcept {
94 if (current == end) return not_matched;
95
96 if (multiline_mode(f)) {
97 // TODO add support for different line ending and unicode (in a future unicode mode)
98 if (*current == '\n') return not_matched;
99 }
100 return evaluate(begin, ++current, end, consumed_something(f), captures, ctll::list<Tail...>());
101 }
102
103 // matching strings in patterns
104
105 template <typename Iterator> struct string_match_result {
106 Iterator position;
107 bool match;
108 };
109
compare_character(CharT c,Iterator & it,const EndIterator & end)110 template <typename CharT, typename Iterator, typename EndIterator> constexpr CTRE_FORCE_INLINE bool compare_character(CharT c, Iterator & it, const EndIterator & end) {
111 if (it != end) {
112 using char_type = decltype(*it);
113 return *it++ == static_cast<char_type>(c);
114 }
115 return false;
116 }
117
evaluate_match_string(Iterator current,const EndIterator end,std::index_sequence<Idx...>)118 template <auto... String, size_t... Idx, typename Iterator, typename EndIterator> constexpr CTRE_FORCE_INLINE string_match_result<Iterator> evaluate_match_string(Iterator current, [[maybe_unused]] const EndIterator end, std::index_sequence<Idx...>) noexcept {
119
120 bool same = (compare_character(String, current, end) && ... && true);
121
122 return {current, same};
123 }
124
125 template <typename R, typename Iterator, typename EndIterator, auto... String, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<string<String...>,Tail...>)126 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, [[maybe_unused]] const flags & f, R captures, ctll::list<string<String...>, Tail...>) noexcept {
127 auto result = evaluate_match_string<String...>(current, end, std::make_index_sequence<sizeof...(String)>());
128
129 if (!result.match) {
130 return not_matched;
131 }
132
133 return evaluate(begin, result.position, end, consumed_something(f, sizeof...(String) > 0), captures, ctll::list<Tail...>());
134 }
135
136 // matching select in patterns
137 template <typename R, typename Iterator, typename EndIterator, typename HeadOptions, typename... TailOptions, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<select<HeadOptions,TailOptions...>,Tail...>)138 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<select<HeadOptions, TailOptions...>, Tail...>) noexcept {
139 if (auto r = evaluate(begin, current, end, f, captures, ctll::list<HeadOptions, Tail...>())) {
140 return r;
141 } else {
142 return evaluate(begin, current, end, f, captures, ctll::list<select<TailOptions...>, Tail...>());
143 }
144 }
145
146 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
evaluate(const Iterator,Iterator,const EndIterator,flags,R,ctll::list<select<>,Tail...>)147 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator, Iterator, const EndIterator, flags, R, ctll::list<select<>, Tail...>) noexcept {
148 // no previous option was matched => REJECT
149 return not_matched;
150 }
151
152 // matching sequence in patterns
153 template <typename R, typename Iterator, typename EndIterator, typename HeadContent, typename... TailContent, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<sequence<HeadContent,TailContent...>,Tail...>)154 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<sequence<HeadContent, TailContent...>, Tail...>) noexcept {
155 if constexpr (sizeof...(TailContent) > 0) {
156 return evaluate(begin, current, end, f, captures, ctll::list<HeadContent, sequence<TailContent...>, Tail...>());
157 } else {
158 return evaluate(begin, current, end, f, captures, ctll::list<HeadContent, Tail...>());
159 }
160 }
161
162 // matching empty in patterns
163 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<empty,Tail...>)164 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<empty, Tail...>) noexcept {
165 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
166 }
167
168 // matching asserts
169 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<assert_subject_begin,Tail...>)170 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<assert_subject_begin, Tail...>) noexcept {
171 if (begin != current) {
172 return not_matched;
173 }
174 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
175 }
176
177 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<assert_subject_end,Tail...>)178 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<assert_subject_end, Tail...>) noexcept {
179 if (end != current) {
180 return not_matched;
181 }
182 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
183 }
184
185 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<assert_subject_end_line,Tail...>)186 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<assert_subject_end_line, Tail...>) noexcept {
187 if (multiline_mode(f)) {
188 if (end == current) {
189 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
190 } else if (*current == '\n' && std::next(current) == end) {
191 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
192 } else {
193 return not_matched;
194 }
195 } else {
196 if (end != current) {
197 return not_matched;
198 }
199 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
200 }
201 }
202
203 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<assert_line_begin,Tail...>)204 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<assert_line_begin, Tail...>) noexcept {
205 if (multiline_mode(f)) {
206 if (begin == current) {
207 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
208 } else if (*std::prev(current) == '\n') {
209 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
210 } else {
211 return not_matched;
212 }
213 } else {
214 if (begin != current) {
215 return not_matched;
216 }
217 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
218 }
219 }
220
221 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<assert_line_end,Tail...>)222 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<assert_line_end, Tail...>) noexcept {
223 if (multiline_mode(f)) {
224 if (end == current) {
225 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
226 } else if (*current == '\n') {
227 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
228 } else {
229 return not_matched;
230 }
231 } else {
232 if (end != current) {
233 return not_matched;
234 }
235 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
236 }
237
238 // TODO properly match line end
239 if (end != current) {
240 return not_matched;
241 }
242 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
243 }
244
245 // matching boundary
246 template <typename R, typename Iterator, typename EndIterator, typename CharacterLike, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<boundary<CharacterLike>,Tail...>)247 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<boundary<CharacterLike>, Tail...>) noexcept {
248
249 // reason why I need bidirectional iterators or some clever hack
250 bool before = false;
251 bool after = false;
252
253 static_assert(is_bidirectional(typename std::iterator_traits<Iterator>::iterator_category{}), "To use boundary in regex you need to provide bidirectional iterator or range.");
254
255 if (end != current) {
256 after = CharacterLike::match_char(*current);
257 }
258 if (begin != current) {
259 before = CharacterLike::match_char(*std::prev(current));
260 }
261
262 if (before == after) return not_matched;
263
264 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
265 }
266
267 // matching not_boundary
268 template <typename R, typename Iterator, typename EndIterator, typename CharacterLike, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<not_boundary<CharacterLike>,Tail...>)269 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<not_boundary<CharacterLike>, Tail...>) noexcept {
270
271 // reason why I need bidirectional iterators or some clever hack
272 bool before = false;
273 bool after = false;
274
275 static_assert(is_bidirectional(typename std::iterator_traits<Iterator>::iterator_category{}), "To use boundary in regex you need to provide bidirectional iterator or range.");
276
277 if (end != current) {
278 after = CharacterLike::match_char(*current);
279 }
280 if (begin != current) {
281 before = CharacterLike::match_char(*std::prev(current));
282 }
283
284 if (before != after) return not_matched;
285
286 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
287 }
288
289 // lazy repeat
290 template <typename R, typename Iterator, typename EndIterator, size_t A, size_t B, typename... Content, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<lazy_repeat<A,B,Content...>,Tail...>)291 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, [[maybe_unused]] const flags & f, R captures, ctll::list<lazy_repeat<A,B,Content...>, Tail...>) noexcept {
292
293 if constexpr (B != 0 && A > B) {
294 return not_matched;
295 }
296
297 const Iterator backup_current = current;
298
299 size_t i{0};
300
301 while (less_than<A>(i)) {
302 auto outer_result = evaluate(begin, current, end, not_empty_match(f), captures, ctll::list<Content..., end_cycle_mark>());
303
304 if (!outer_result) return not_matched;
305
306 captures = outer_result.unmatch();
307 current = outer_result.get_end_position();
308
309 ++i;
310 }
311
312 if (auto outer_result = evaluate(begin, current, end, consumed_something(f, backup_current != current), captures, ctll::list<Tail...>())) {
313 return outer_result;
314 }
315
316 while (less_than_or_infinite<B>(i)) {
317 auto inner_result = evaluate(begin, current, end, not_empty_match(f), captures, ctll::list<Content..., end_cycle_mark>());
318
319 if (!inner_result) return not_matched;
320
321 auto outer_result = evaluate(begin, inner_result.get_end_position(), end, consumed_something(f), inner_result.unmatch(), ctll::list<Tail...>());
322
323 if (outer_result) {
324 return outer_result;
325 }
326
327 captures = inner_result.unmatch();
328 current = inner_result.get_end_position();
329
330 ++i;
331 }
332
333 // rest of regex
334 return evaluate(begin, current, end, consumed_something(f), captures, ctll::list<Tail...>());
335 }
336
337 // possessive repeat
338 template <typename R, typename Iterator, typename EndIterator, size_t A, size_t B, typename... Content, typename... Tail>
evaluate(const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<possessive_repeat<A,B,Content...>,Tail...>)339 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, [[maybe_unused]] const flags & f, R captures, ctll::list<possessive_repeat<A,B,Content...>, Tail...>) noexcept {
340
341 if constexpr ((B != 0) && (A > B)) {
342 return not_matched;
343 }
344
345 const auto backup_current = current;
346
347 for (size_t i{0}; less_than_or_infinite<B>(i); ++i) {
348 // try as many of inner as possible and then try outer once
349 auto inner_result = evaluate(begin, current, end, not_empty_match(f), captures, ctll::list<Content..., end_cycle_mark>());
350
351 if (!inner_result) {
352 if (!less_than<A>(i)) break;
353 return not_matched;
354 }
355
356 captures = inner_result.unmatch();
357 current = inner_result.get_end_position();
358 }
359
360 return evaluate(begin, current, end, consumed_something(f, backup_current != current), captures, ctll::list<Tail...>());
361 }
362
363 // (gready) repeat
364 template <typename R, typename Iterator, typename EndIterator, size_t A, size_t B, typename... Content, typename... Tail>
365 #ifdef CTRE_MSVC_GREEDY_WORKAROUND
evaluate_recursive(R & result,size_t i,const Iterator begin,Iterator current,const EndIterator end,const flags & f,R captures,ctll::list<repeat<A,B,Content...>,Tail...> stack)366 constexpr inline void evaluate_recursive(R & result, size_t i, const Iterator begin, Iterator current, const EndIterator end, [[maybe_unused]] const flags & f, R captures, ctll::list<repeat<A,B,Content...>, Tail...> stack) {
367 #else
368 constexpr inline R evaluate_recursive(size_t i, const Iterator begin, Iterator current, const EndIterator end, [[maybe_unused]] const flags & f, R captures, ctll::list<repeat<A,B,Content...>, Tail...> stack) {
369 #endif
370 if (less_than_or_infinite<B>(i)) {
371
372 // a*ab
373 // aab
374
375 if (auto inner_result = evaluate(begin, current, end, not_empty_match(f), captures, ctll::list<Content..., end_cycle_mark>())) {
376 // TODO MSVC issue:
377 // if I uncomment this return it will not fail in constexpr (but the matching result will not be correct)
378 // return inner_result
379 // I tried to add all constructors to R but without any success
380 auto tmp_current = current;
381 tmp_current = inner_result.get_end_position();
382 #ifdef CTRE_MSVC_GREEDY_WORKAROUND
383 evaluate_recursive(result, i+1, begin, tmp_current, end, f, inner_result.unmatch(), stack);
384 if (result) {
385 return;
386 }
387 #else
388 if (auto rec_result = evaluate_recursive(i+1, begin, tmp_current, end, f, inner_result.unmatch(), stack)) {
389 return rec_result;
390 }
391 #endif
392 }
393 }
394 #ifdef CTRE_MSVC_GREEDY_WORKAROUND
395 result = evaluate(begin, current, end, consumed_something(f), captures, ctll::list<Tail...>());
396 #else
397 return evaluate(begin, current, end, consumed_something(f), captures, ctll::list<Tail...>());
398 #endif
399 }
400
401
402
403 // (greedy) repeat
404 template <typename R, typename Iterator, typename EndIterator, size_t A, size_t B, typename... Content, typename... Tail>
405 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, [[maybe_unused]] const flags & f, R captures, [[maybe_unused]] ctll::list<repeat<A,B,Content...>, Tail...> stack) {
406
407 if constexpr ((B != 0) && (A > B)) {
408 return not_matched;
409 }
410
411 #ifndef CTRE_DISABLE_GREEDY_OPT
412 if constexpr (!collides(calculate_first(Content{}...), calculate_first(Tail{}...))) {
413 return evaluate(begin, current, end, f, captures, ctll::list<possessive_repeat<A,B,Content...>, Tail...>());
414 }
415 #endif
416
417 // A..B
418 size_t i{0};
419 while (less_than<A>(i)) {
420 auto inner_result = evaluate(begin, current, end, not_empty_match(f), captures, ctll::list<Content..., end_cycle_mark>());
421
422 if (!inner_result) return not_matched;
423
424 captures = inner_result.unmatch();
425 current = inner_result.get_end_position();
426
427 ++i;
428 }
429
430 #ifdef CTRE_MSVC_GREEDY_WORKAROUND
431 R result;
432 evaluate_recursive(result, i, begin, current, end, f, captures, stack);
433 return result;
434 #else
435 return evaluate_recursive(i, begin, current, end, f, captures, stack);
436 #endif
437
438 }
439
440 // capture (numeric ID)
441 template <typename R, typename Iterator, typename EndIterator, size_t Id, typename... Content, typename... Tail>
442 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<capture<Id, Content...>, Tail...>) noexcept {
443 return evaluate(begin, current, end, f, captures.template start_capture<Id>(current), ctll::list<sequence<Content...>, numeric_mark<Id>, Tail...>());
444 }
445
446 // capture end mark (numeric and string ID)
447 template <typename R, typename Iterator, typename EndIterator, size_t Id, typename... Tail>
448 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<numeric_mark<Id>, Tail...>) noexcept {
449 return evaluate(begin, current, end, f, captures.template end_capture<Id>(current), ctll::list<Tail...>());
450 }
451
452 // capture (string ID)
453 template <typename R, typename Iterator, typename EndIterator, size_t Id, typename Name, typename... Content, typename... Tail>
454 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<capture_with_name<Id, Name, Content...>, Tail...>) noexcept {
455 return evaluate(begin, current, end, f, captures.template start_capture<Id>(current), ctll::list<sequence<Content...>, numeric_mark<Id>, Tail...>());
456 }
457
458 // backreference support (match agains content of iterators)
459 template <typename Iterator, typename EndIterator> constexpr CTRE_FORCE_INLINE string_match_result<Iterator> match_against_range(Iterator current, const EndIterator end, Iterator range_current, const Iterator range_end, flags) noexcept {
460 while (end != current && range_end != range_current) {
461 if (*current == *range_current) {
462 current++;
463 range_current++;
464 } else {
465 return {current, false};
466 }
467 }
468 return {current, range_current == range_end};
469 }
470
471 // backreference with name
472 template <typename R, typename Id, typename Iterator, typename EndIterator, typename... Tail>
473 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<back_reference_with_name<Id>, Tail...>) noexcept {
474
475 if (const auto ref = captures.template get<Id>()) {
476 if (auto result = match_against_range(current, end, ref.begin(), ref.end(), f); result.match) {
477 return evaluate(begin, result.position, end, consumed_something(f, ref.begin() != ref.end()), captures, ctll::list<Tail...>());
478 }
479 }
480 return not_matched;
481 }
482
483 // backreference
484 template <typename R, size_t Id, typename Iterator, typename EndIterator, typename... Tail>
485 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<back_reference<Id>, Tail...>) noexcept {
486
487 if (const auto ref = captures.template get<Id>()) {
488 if (auto result = match_against_range(current, end, ref.begin(), ref.end(), f); result.match) {
489 return evaluate(begin, result.position, end, consumed_something(f, ref.begin() != ref.end()), captures, ctll::list<Tail...>());
490 }
491 }
492 return not_matched;
493 }
494
495 // end of lookahead
496 template <typename R, typename Iterator, typename EndIterator, typename... Tail>
497 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator, Iterator, const EndIterator, flags, R captures, ctll::list<end_lookahead_mark>) noexcept {
498 // TODO check interaction with non-empty flag
499 return captures.matched();
500 }
501
502 // lookahead positive
503 template <typename R, typename Iterator, typename EndIterator, typename... Content, typename... Tail>
504 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<lookahead_positive<Content...>, Tail...>) noexcept {
505
506 if (auto lookahead_result = evaluate(begin, current, end, f, captures, ctll::list<sequence<Content...>, end_lookahead_mark>())) {
507 captures = lookahead_result.unmatch();
508 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
509 } else {
510 return not_matched;
511 }
512 }
513
514 // lookahead negative
515 template <typename R, typename Iterator, typename EndIterator, typename... Content, typename... Tail>
516 constexpr CTRE_FORCE_INLINE R evaluate(const Iterator begin, Iterator current, const EndIterator end, const flags & f, R captures, ctll::list<lookahead_negative<Content...>, Tail...>) noexcept {
517
518 if (auto lookahead_result = evaluate(begin, current, end, f, captures, ctll::list<sequence<Content...>, end_lookahead_mark>())) {
519 return not_matched;
520 } else {
521 return evaluate(begin, current, end, f, captures, ctll::list<Tail...>());
522 }
523 }
524
525
526 }
527
528 #endif
529