Debian Codegraph @

modules/lsp-runtime-lib/src/main/io/PathPattern.cpp

raw
1 /*
2 * Copyright (C) 2025 Linux Studio Plugins Project <https://lsp-plug.in/>
3 * (C) 2025 Vladimir Sadovnikov <[email protected]>
4 *
5 * This file is part of lsp-runtime-lib
6 * Created on: 15 окт. 2020 г.
7 *
8 * lsp-runtime-lib is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * any later version.
12 *
13 * lsp-runtime-lib is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with lsp-runtime-lib. If not, see <https://www.gnu.org/licenses/>.
20 */
21
22 #include <lsp-plug.in/io/PathPattern.h>
23 #include <lsp-plug.in/io/charset.h>
24 #include <lsp-plug.in/common/debug.h>
25
26 #include <wctype.h>
27
28 namespace lsp
29 {
30 namespace io
31 {
32 static inline bool is_file_separator(lsp_wchar_t c)
33 {
34 return (c == '/') || (c == '\\');
35 }
36
37 PathPattern::PathPattern()
38 {
39 nFlags = 0;
40 pRoot = NULL;
41 }
42
43 PathPattern::~PathPattern()
44 {
45 destroy_cmd(pRoot);
46 pRoot = NULL;
47 }
48
49 void PathPattern::destroy_cmd(cmd_t *cmd)
50 {
51 if (cmd == NULL)
52 return;
53
54 // Recursively delete all sub-nodes
55 for (size_t i=0, n=cmd->sChildren.size(); i<n; ++i)
56 {
57 cmd_t *child = cmd->sChildren.uget(i);
58 destroy_cmd(child);
59 }
60
61 delete cmd;
62 }
63
64 void PathPattern::next_token(tokenizer_t *it)
65 {
66 it->nToken = -1;
67 }
68
69 ssize_t PathPattern::get_token(tokenizer_t *it)
70 {
71 // There is unget token?
72 if (it->nToken >= 0)
73 return it->nToken;
74
75 const LSPString *mask = it->pMask;
76
77 // End of input?
78 if (it->nPosition >= mask->length())
79 return it->nToken = T_EOF;
80
81 // Analyze first character
82 it->nStart = it->nPosition;
83 it->nLength = 0;
84 it->nChars = -1;
85 lsp_wchar_t c = mask->char_at(it->nPosition++);
86 bool escape;
87
88 switch (c)
89 {
90 case '&': // T_AND
91 return it->nToken = T_AND;
92 case '|': // T_OR
93 return it->nToken = T_OR;
94 case '!': // T_NOT, TT_IGROUP_START
95 if (it->nPosition >= mask->length())
96 return it->nToken = T_NOT;
97 if (mask->char_at(it->nPosition) != '(')
98 return it->nToken = T_NOT;
99
100 ++it->nPosition;
101 return it->nToken = T_IGROUP_START;
102 case ')': // T_GROUP_END
103 return it->nToken = T_GROUP_END;
104
105 case '(': // T_GROUP_START, T_IGROUP_START
106 return it->nToken = T_GROUP_START;
107
108 case '*': // T_ANY, T_ANYPATH
109 if ((it->nPosition + 2) > mask->length())
110 return it->nToken = T_ANY;
111 if (mask->char_at(it->nPosition) != '*')
112 return it->nToken = T_ANY;
113 c = mask->char_at(it->nPosition+1);
114 if (!is_file_separator(c))
115 return it->nToken = T_ANY;
116
117 it->nPosition += 2;
118 return it->nToken = T_ANYPATH;
119
120 default: // T_TEXT
121 it->nToken = T_TEXT;
122 escape = c == '`';
123 it->nChars = (escape) ? 0 : 1;
124 break;
125 }
126
127 // Parse T_TEXT
128 for ( ; it->nPosition < mask->length(); ++it->nPosition )
129 {
130 // Lookup next character
131 c = mask->char_at(it->nPosition);
132
133 switch (c)
134 {
135 // Special symbols
136 case '*': case '(': case ')': case '|':
137 case '&': case '!':
138 if (!escape)
139 {
140 it->nLength = it->nPosition - it->nStart;
141 return it->nToken;
142 }
143 ++it->nChars;
144 escape = false;
145 break;
146
147 case '`':
148 if (escape)
149 ++it->nChars;
150 escape = !escape;
151 break;
152
153 default:
154 if (escape)
155 {
156 ++it->nChars;
157 escape = false;
158 }
159 ++it->nChars;
160 break;
161 }
162 }
163
164 // Escape character pending?
165 if (escape)
166 ++it->nChars;
167 it->nLength = it->nPosition - it->nStart;
168
169 return it->nToken;
170 }
171
172 status_t PathPattern::merge_step(cmd_t **out, cmd_t *next, command_t type)
173 {
174 if (*out == NULL)
175 {
176 cmd_t *tmp = new cmd_t();
177 tmp->nCommand = type;
178 tmp->nStart = 0;
179 tmp->nLength = 0;
180 tmp->nChars = -1;
181 tmp->bInverse = false;
182 *out = tmp;
183 }
184 if (next == NULL)
185 return STATUS_OK;
186
187 return (*out)->sChildren.add(next) ? STATUS_OK : STATUS_NO_MEM;
188 }
189
190 status_t PathPattern::merge_simple(cmd_t **out, command_t type, command_t cmd, tokenizer_t *it)
191 {
192 cmd_t *tmp = new cmd_t();
193 tmp->nCommand = cmd;
194 tmp->nStart = it->nStart;
195 tmp->nLength = it->nLength;
196 tmp->nChars = it->nChars;
197 tmp->bInverse = false;
198
199 status_t res = merge_step(out, tmp, type);
200 if (res != STATUS_OK)
201 destroy_cmd(tmp);
202 return res;
203 }
204
205 status_t PathPattern::merge_last(cmd_t **dst, cmd_t *out, cmd_t *next, ssize_t tok)
206 {
207 // Analyze last token
208 if (tok < 0)
209 {
210 destroy_cmd(next);
211 destroy_cmd(out);
212 return status_t(-tok);
213 }
214 else if (out == NULL)
215 {
216 *dst = next;
217 return STATUS_OK;
218 }
219 else if (!out->sChildren.add(next))
220 {
221 destroy_cmd(out);
222 destroy_cmd(next);
223 return STATUS_NO_MEM;
224 }
225
226 // Return the output expression
227 *dst = out;
228
229 return STATUS_OK;
230 }
231
232 status_t PathPattern::parse_sequence(cmd_t **dst, tokenizer_t *it)
233 {
234 cmd_t *out = NULL, *next = NULL;
235 status_t res = STATUS_OK;
236
237 while (true)
238 {
239 ssize_t tok = get_token(it);
240
241 switch (tok)
242 {
243 case T_GROUP_START:
244 case T_IGROUP_START:
245 next_token(it);
246 if ((res = parse_or(&next, it)) != STATUS_OK)
247 break;
248
249 next->bInverse ^= (tok == T_IGROUP_START);
250
251 if ((next->nCommand == CMD_PATTERN) && (next->nChars <= 0) && (!next->bInverse))
252 {
253 // Premature optimization: ignore empty text since it has no rational sense
254 destroy_cmd(next); // Drop the command
255 next = NULL;
256 }
257 else if ((next->nCommand == CMD_ANY) && (next->nChars < 0) && (next->bInverse))
258 {
259 // Premature optimization: ignore inverse ANY match since it has no rational sense
260 destroy_cmd(next); // Drop the command
261 next = NULL;
262 }
263 else if ((next->nCommand == CMD_PATTERN) && (next->bInverse))
264 {
265 next->nCommand = CMD_ANY;
266 next->bInverse = false;
267
268 // Premature optimization: replace previous ANY match with ANY EXCEPT match
269 cmd_t *prev = (out != NULL) ? out->sChildren.last() : NULL;
270 if ((prev != NULL) && (prev->nCommand == CMD_ANY) && (prev->nChars < 0) && (!prev->bInverse))
271 {
272 // Premature optimization: replace previous ANY match with ANY EXCEPT
273 prev->nChars = next->nChars;
274 prev->nStart = next->nStart;
275 prev->nLength = next->nLength;
276
277 destroy_cmd(next); // Drop the command
278 next = NULL;
279 }
280 }
281
282 // Merge next item
283 if (next != NULL)
284 res = merge_step(&out, next, CMD_SEQUENCE);
285
286 // Check result
287 if (res != STATUS_OK)
288 {
289 destroy_cmd(next);
290 break;
291 }
292
293 // Require END-OF-GROUP token
294 tok = get_token(it);
295 if (tok == T_EOF)
296 return -STATUS_EOF;
297 else if (tok != T_GROUP_END)
298 return -STATUS_BAD_FORMAT;
299 next_token(it);
300 break;
301
302 case T_TEXT:
303 next_token(it);
304
305 // Premature optimization: ignore empty text since it has no rational sense
306 if (it->nChars == 0)
307 break;
308 res = merge_simple(&out, CMD_SEQUENCE, CMD_PATTERN, it);
309 break;
310
311 case T_ANY:
312 next_token(it);
313 // Premature optimization: Reduce sequence of multiple ANY elements to one ANY element
314 next = (out != NULL) ? out->sChildren.last() : NULL;
315 if ((next != NULL) && (next->nCommand == CMD_ANY))
316 break;
317 res = merge_simple(&out, CMD_SEQUENCE, CMD_ANY, it);
318 break;
319
320 case T_ANYPATH:
321 next_token(it);
322 next = (out != NULL) ? out->sChildren.last() : NULL;
323 // Premature optimization: Reduce sequence of **/ to one element
324 if ((next != NULL) && (next->nCommand == CMD_ANYPATH))
325 break;
326 res = merge_simple(&out, CMD_SEQUENCE, CMD_ANYPATH, it);
327 break;
328
329 default:
330 res = merge_step(&out, NULL, CMD_SEQUENCE);
331 if (res != STATUS_OK)
332 break;
333
334 if (out->sChildren.size() == 1)
335 {
336 // Premature optimization: treat sequence of one element as this element
337 *dst = out->sChildren.uget(0);
338 out->sChildren.clear();
339 destroy_cmd(out);
340 }
341 else
342 {
343 if (out->sChildren.is_empty())
344 {
345 // Premature optimization: Treat empty sequence as empty text
346 out->nCommand = CMD_PATTERN;
347 out->nStart = 0;
348 out->nLength = 0;
349 out->nChars = 0;
350 }
351
352 *dst = out;
353 }
354
355 return res;
356 }
357
358 if (res != STATUS_OK)
359 {
360 destroy_cmd(out);
361 return res;
362 }
363 }
364 }
365
366 status_t PathPattern::parse_not(cmd_t **dst, tokenizer_t *it)
367 {
368 bool inverse = false;
369
370 // Premature optimization: treat multiple ! as valid inverse
371 ssize_t tok = get_token(it);
372 while (tok == T_NOT)
373 {
374 next_token(it);
375 inverse = !inverse;
376 tok = get_token(it);
377 }
378
379 status_t res = parse_sequence(dst, it);
380 if (res == STATUS_OK)
381 (*dst)->bInverse ^= inverse;
382
383 return res;
384 }
385
386 status_t PathPattern::parse_and(cmd_t **dst, tokenizer_t *it)
387 {
388 cmd_t *out = NULL, *next = NULL;
389
390 // Parse sub-expression
391 status_t res = parse_not(&next, it);
392 if (res != STATUS_OK)
393 return res;
394
395 // Get token (and move to next)
396 ssize_t tok = get_token(it);
397 while (tok == T_AND)
398 {
399 // Commit token
400 next_token(it);
401
402 // Merge command and parse next sub-expression
403 if ((res = merge_step(&out, next, CMD_AND)) == STATUS_OK)
404 res = parse_not(&next, it);
405
406 // Parse command
407 if (res != STATUS_OK)
408 {
409 destroy_cmd(out);
410 destroy_cmd(next);
411 return res;
412 }
413
414 // Get next token
415 tok = get_token(it);
416 }
417
418 return merge_last(dst, out, next, tok);
419 }
420
421 status_t PathPattern::parse_or(cmd_t **dst, tokenizer_t *it)
422 {
423 cmd_t *out = NULL, *next = NULL;
424
425 // Parse sub-expression
426 status_t res = parse_and(&next, it);
427 if (res != STATUS_OK)
428 return res;
429
430 // Get token (and move to next)
431 ssize_t tok = get_token(it);
432 while (tok == T_OR)
433 {
434 // Commit token
435 next_token(it);
436
437 // Merge command and parse next sub-expression
438 if ((res = merge_step(&out, next, CMD_OR)) == STATUS_OK)
439 res = parse_and(&next, it);
440
441 // Parse command
442 if (res != STATUS_OK)
443 {
444 destroy_cmd(out);
445 destroy_cmd(next);
446 return res;
447 }
448
449 // Get next token
450 tok = get_token(it);
451 }
452
453 return merge_last(dst, out, next, tok);
454 }
455
456 status_t PathPattern::parse(const LSPString *pattern, size_t flags)
457 {
458 tokenizer_t it;
459 PathPattern tmp;
460
461 // Initialize temporary pattern
462 if (!tmp.sMask.set(pattern))
463 return STATUS_NO_MEM;
464 tmp.nFlags = flags;
465
466 // Initialize tokenizer
467 it.nToken = -1;
468 it.pMask = &tmp.sMask;
469 it.nPosition = 0;
470 it.nStart = 0;
471 it.nLength = 0;
472 it.nChars = 0;
473
474 // Parse expression
475 status_t res = parse_or(&tmp.pRoot, &it);
476 if (res == STATUS_OK)
477 {
478 ssize_t tok = get_token(&it);
479 if (tok < 0)
480 return status_t(-tok);
481 else if (tok != T_EOF)
482 return STATUS_BAD_FORMAT;
483
484 tmp.swap(this); // Apply new value on success
485 }
486
487 return res;
488 }
489
490 bool PathPattern::check_pattern_case(const lsp_wchar_t *pat, const lsp_wchar_t *s, size_t len)
491 {
492 lsp_wchar_t c, pc;
493
494 for (size_t off=0; off<len; )
495 {
496 c = *(s++); // Matching character
497 pc = pat[off++]; // Pattern character
498
499 switch (pc)
500 {
501 case '/':
502 case '\\':
503 if (!is_file_separator(c))
504 return false;
505 break;
506 case '?':
507 if (is_file_separator(c))
508 return false;
509 break;
510 case '`':
511 pc = (off < len) ? pat[off] : '`';
512 switch (pc)
513 {
514 // Special symbols
515 case '*': case '(': case ')': case '|':
516 case '&': case '!': case '`':
517 ++off;
518 break;
519 default:
520 pc = '`';
521 break;
522 }
523 if (c != pc)
524 return false;
525 break;
526
527 default:
528 if (c != pc)
529 return false;
530 break;
531 } // switch
532 }
533
534 return true;
535 }
536
537 bool PathPattern::check_pattern_nocase(const lsp_wchar_t *pat, const lsp_wchar_t *s, size_t len)
538 {
539 lsp_wchar_t c, pc;
540
541 for (size_t off=0; off<len; )
542 {
543 c = *(s++); // Matching character
544 pc = pat[off++]; // Pattern character
545
546 switch (pc)
547 {
548 case '/':
549 case '\\':
550 if (!is_file_separator(c))
551 return false;
552 break;
553 case '?':
554 if (is_file_separator(c))
555 return false;
556 break;
557 case '`':
558 pc = (off < len) ? pat[off] : '`';
559 switch (pc)
560 {
561 // Special symbols
562 case '*': case '(': case ')': case '|':
563 case '&': case '!': case '`':
564 ++off;
565 break;
566 default:
567 pc = '`';
568 break;
569 }
570 if (lsp::to_lower(c) != lsp::to_lower(pc))
571 return false;
572 break;
573
574 default:
575 if (lsp::to_lower(c) != lsp::to_lower(pc))
576 return false;
577 break;
578 } // switch
579 }
580
581 return true;
582 }
583
584 ssize_t PathPattern::seek_pattern_case(const lsp_wchar_t *pat, const lsp_wchar_t *s, size_t len, ssize_t rounds)
585 {
586 if (rounds <= 0)
587 return -1;
588
589 for (ssize_t i=0; i < rounds; ++i)
590 {
591 if (check_pattern_case(pat, &s[i], len))
592 return i;
593 }
594 return -1;
595 }
596
597 ssize_t PathPattern::seek_pattern_nocase(const lsp_wchar_t *pat, const lsp_wchar_t *s, size_t len, ssize_t rounds)
598 {
599 if (rounds <= 0)
600 return -1;
601
602 for (ssize_t i=0; i < rounds; ++i)
603 {
604 if (check_pattern_nocase(pat, &s[i], len))
605 return i;
606 }
607 return -1;
608 }
609
610 bool PathPattern::pattern_matcher_match(matcher_t *m, size_t start, size_t count)
611 {
612 const cmd_t *cmd = m->cmd;
613 if (count != size_t(m->cmd->nChars))
614 return cmd->bInverse;
615
616 const lsp_wchar_t *pat = m->pat->characters() + cmd->nStart;
617 const lsp_wchar_t *str = m->str->characters() + start;
618 bool match = (m->flags & MATCH_CASE) ?
619 check_pattern_case(pat, str, cmd->nLength) :
620 check_pattern_nocase(pat, str, cmd->nLength);
621
622 return match ^ cmd->bInverse;
623 }
624
625 bool PathPattern::any_matcher_match(matcher_t *m, size_t start, size_t count)
626 {
627 const cmd_t *cmd = m->cmd;
628 if ((cmd->nChars < 0) && (count == 0))
629 return !cmd->bInverse;
630
631 // Bad match is inside of the passed range?
632 any_matcher_t *am = static_cast<any_matcher_t *>(m);
633 if ((am->bad >= ssize_t(start)) && (am->bad < ssize_t(start + count)))
634 return cmd->bInverse;
635
636 // Good match is inside of the passed range? Return immediately with unsuccess
637 if ((am->good >= ssize_t(start)) && ((am->good + cmd->nChars) < ssize_t(start + count)))
638 return cmd->bInverse;
639
640 // We need to ensure that there are no denied items within the area
641 const lsp_wchar_t *str = m->str->characters() + start;
642 for (size_t i=0; i<count; ++i)
643 {
644 lsp_wchar_t ch = str[i];
645 if (is_file_separator(ch))
646 {
647 am->bad = start + i; // Cache last bad value
648 return cmd->bInverse;
649 }
650 }
651
652 // Additionally, if we have 'except' rule, lookup for the sub-string
653 if (cmd->nChars < 0)
654 return !cmd->bInverse; // No 'except' rule
655 else if (cmd->nChars == 0)
656 return (count > 0) ^ cmd->bInverse; // Empty 'except', always match ranges longer than 0 characters
657
658 // Perform seek by pattern
659 ssize_t loops = count - cmd->nChars + 1;
660 const lsp_wchar_t *pat = m->pat->characters() + cmd->nStart;
661 ssize_t match = (m->flags & MATCH_CASE) ?
662 seek_pattern_case(pat, str, cmd->nLength, loops) :
663 seek_pattern_nocase(pat, str, cmd->nLength, loops);
664 if (match >= 0)
665 am->good = start + match;
666
667 return (match < 0) ^ cmd->bInverse; // There should be no match found for good reason
668 }
669
670 bool PathPattern::anypath_matcher_match(matcher_t *m, size_t start, size_t count)
671 {
672 const cmd_t *cmd = m->cmd;
673 const lsp_wchar_t *str = m->str->characters() + start;
674 lsp_wchar_t ch;
675
676 // Not beginning of string?
677 if (start > 0)
678 {
679 // Previous character in sequence should be a path separator
680 ch = str[-1];
681 if (!is_file_separator(ch))
682 return cmd->bInverse;
683
684 // Zero length, previous character is separator -> matches
685 if (count == 0)
686 return !cmd->bInverse;
687 }
688 else if (count == 0)
689 return true; // Zero length, start of string -> matches, this is special case which always returns true
690
691 // Last character in sequence should be a path separator
692 ch = str[count-1];
693 if (is_file_separator(ch))
694 return !cmd->bInverse;
695
696 // The separator is not necessary if we are at the end of line
697 if ((start + count) >= m->str->length())
698 return !cmd->bInverse;
699
700 return cmd->bInverse;
701 }
702
703 bool PathPattern::and_matcher_match(matcher_t *m, size_t start, size_t count)
704 {
705 bool_matcher_t *bm = static_cast<bool_matcher_t *>(m);
706 const cmd_t *cmd = bm->cmd;
707
708 // If at least one matcher does not match - return result
709 for (size_t i=0, n=bm->cond.size(); i<n; ++i)
710 {
711 matcher_t *m = bm->cond.uget(i);
712 if (!m->match(m, start, count))
713 return cmd->bInverse;
714 }
715 return !cmd->bInverse;
716 }
717
718 bool PathPattern::or_matcher_match(matcher_t *m, size_t start, size_t count)
719 {
720 bool_matcher_t *bm = static_cast<bool_matcher_t *>(m);
721 const cmd_t *cmd = bm->cmd;
722
723 // If at least one matcher matches - return result
724 for (size_t i=0, n=bm->cond.size(); i<n; ++i)
725 {
726 matcher_t *m = bm->cond.uget(i);
727 if (m->match(m, start, count))
728 return !cmd->bInverse;
729 }
730 return cmd->bInverse;
731 }
732
733 ssize_t PathPattern::sequence_check_prefix(sequence_matcher_t *sm, size_t start, size_t count)
734 {
735 const cmd_t *cmd = sm->cmd;
736
737 for (size_t i=0; i<sm->prefix; ++i)
738 {
739 const cmd_t *xc = cmd->sChildren.uget(i);
740 if (count < size_t(xc->nChars))
741 return -1;
742
743 const lsp_wchar_t *src = sm->str->characters() + start;
744 const lsp_wchar_t *pat = sm->pat->characters() + xc->nStart;
745 bool match = (sm->flags & MATCH_CASE) ?
746 check_pattern_case(pat, src, xc->nLength) :
747 check_pattern_nocase(pat, src, xc->nLength);
748 if (!match)
749 return -1;
750
751 // Update the matching range
752 start += xc->nChars;
753 count -= xc->nChars;
754 }
755
756 return start;
757 }
758
759 ssize_t PathPattern::sequence_check_postfix(sequence_matcher_t *sm, size_t start, size_t count)
760 {
761 const cmd_t *cmd = sm->cmd;
762 start += count;
763
764 for (size_t i=0, idx=cmd->sChildren.size()-1; i<sm->postfix; ++i, --idx)
765 {
766 const cmd_t *xc = cmd->sChildren.uget(idx);
767 if (count < size_t(xc->nChars))
768 return -1;
769 start -= xc->nChars;
770
771 const lsp_wchar_t *src = sm->str->characters() + start;
772 const lsp_wchar_t *pat = sm->pat->characters() + xc->nStart;
773 bool match = (sm->flags & MATCH_CASE) ?
774 check_pattern_case(pat, src, xc->nLength) :
775 check_pattern_nocase(pat, src, xc->nLength);
776 if (!match)
777 return -1;
778
779 // Update the matching range
780 count -= xc->nChars;
781 }
782
783 return start;
784 }
785
786 bool PathPattern::sequence_alloc_fixed(sequence_matcher_t *sm, size_t idx, size_t start, size_t count)
787 {
788 ssize_t last = start + count;
789 for (size_t i=idx, n=sm->fixed.size(); i<n; ++i)
790 {
791 mregion_t *r = sm->fixed.uget(i);
792 const cmd_t *xc = r->cmd;
793 const lsp_wchar_t *src = sm->str->characters() + start;
794 const lsp_wchar_t *pat = sm->pat->characters() + xc->nStart;
795
796 // Find match
797 ssize_t loops = last - start - xc->nChars + 1;
798 ssize_t match = (sm->flags & MATCH_CASE) ?
799 seek_pattern_case(pat, src, xc->nLength, loops) :
800 seek_pattern_nocase(pat, src, xc->nLength, loops);
801
802 if (match < 0) // No match found?
803 return false;
804
805 r->start = start + match;
806 start = r->start + xc->nChars;
807 }
808
809 return true;
810 }
811
812 bool PathPattern::sequence_next_fixed(sequence_matcher_t *sm, size_t start, size_t count)
813 {
814 // Now we need to update positions
815 ssize_t last = start + count;
816
817 for (ssize_t i = sm->fixed.size() - 1; i >= 0; --i)
818 {
819 mregion_t *r = sm->fixed.uget(i);
820 const cmd_t *xc = r->cmd;
821 ssize_t first = r->start + 1;
822 const lsp_wchar_t *src = sm->str->characters() + first;
823 const lsp_wchar_t *pat = sm->pat->characters() + xc->nStart;
824
825 ssize_t loops = last - first;
826 ssize_t match = (sm->flags & MATCH_CASE) ?
827 seek_pattern_case(pat, src, xc->nLength, loops) :
828 seek_pattern_nocase(pat, src, xc->nLength, loops);
829
830 if (match >= 0)
831 {
832 r->start = first + match;
833 first = r->start + xc->nChars;
834 if (sequence_alloc_fixed(sm, i + 1, first, last - first))
835 return true;
836 }
837 }
838
839 return false;
840 }
841
842 bool PathPattern::sequence_match_variable(sequence_matcher_t *sm, size_t start, size_t count)
843 {
844 mregion_t *r;
845 matcher_t *m;
846
847 ssize_t first = start, last = start + count;
848 for (size_t i=0, n=sm->fixed.size(); i<n; ++i)
849 {
850 r = sm->fixed.uget(i);
851 m = sm->var.uget(i);
852 if (!m->match(m, first, r->start - first))
853 return false;
854 first = r->start + r->cmd->nChars;
855 }
856
857 // Perform N+1'th match
858 m = sm->var.last();
859 if (!m->match(m, first, last - first))
860 return false;
861
862 return true;
863 }
864
865 bool PathPattern::sequence_matcher_match(matcher_t *m, size_t start, size_t count)
866 {
867 sequence_matcher_t *sm = static_cast<sequence_matcher_t *>(m);
868 const cmd_t *cmd = sm->cmd;
869
870 // Check prefixes
871 ssize_t last = start + count;
872 ssize_t first = sequence_check_prefix(sm, start, count);
873 if (first < 0)
874 return cmd->bInverse;
875
876 // Check postfixes
877 last = sequence_check_postfix(sm, first, last - first);
878 if (last < 0)
879 return cmd->bInverse;
880 count = last - first;
881 start = first;
882
883 // Now we have only N fixed and N+1 variable positions left
884 if (sm->fixed.size() <= 0) // No fixed elements?
885 {
886 if (sm->var.size() <= 0)
887 return (first == last) ^ cmd->bInverse;
888
889 m = sm->var.uget(0);
890 bool match = m->match(m, first, count);
891 return match ^ cmd->bInverse;
892 }
893
894 // Perform initial match
895 if (!sequence_alloc_fixed(sm, 0, start, count))
896 return cmd->bInverse;
897
898 // Check for non-fixed match
899 while (true)
900 {
901 // Perform N matches
902 bool match = sequence_match_variable(sm, start, count);
903 if (match)
904 return !cmd->bInverse;
905
906 // Try to search next fixed pattern
907 if (!sequence_next_fixed(sm, start, count))
908 return cmd->bInverse;
909 }
910
911 return false;
912 }
913
914 bool PathPattern::brute_match_variable(brute_matcher_t *bm, size_t start, size_t count)
915 {
916 mregion_t *r = bm->items.first();
917 ssize_t last = start + count;
918
919 // Check all matchers except last one
920 for (size_t i=1, n=bm->items.size(); i < n; ++i)
921 {
922 mregion_t *nr = bm->items.get(i);
923 if (!r->matcher->match(r->matcher, r->start, nr->start - r->start))
924 return false;
925 r = nr; // Update current matcher
926 }
927
928 // Check last matcher
929 return r->matcher->match(r->matcher, r->start, last - r->start);
930 }
931
932 bool PathPattern::brute_next_variable(brute_matcher_t *bm, size_t start, size_t count)
933 {
934 // We move all regions except the first one
935 for (size_t i=1, n=bm->items.size(); i < n; ++i)
936 {
937 mregion_t *r = bm->items.get(i);
938
939 // Can move current region one position left?
940 if (r->start > start)
941 {
942 --r->start;
943 while ((i--) > 1)
944 {
945 mregion_t *pr = bm->items.get(i);
946 pr->start = r->start;
947 }
948 return true;
949 }
950 }
951
952 return false;
953 }
954
955 bool PathPattern::brute_matcher_match(matcher_t *m, size_t start, size_t count)
956 {
957 brute_matcher_t *bm = static_cast<brute_matcher_t *>(m);
958 const cmd_t *cmd = bm->cmd;
959
960 // Only one element?
961 if (bm->items.size() <= 1)
962 {
963 mregion_t *r = bm->items.first();
964 bool match = r->matcher->match(r->matcher, start, count);
965 return match ^ cmd->bInverse;
966 }
967
968 // Initialize positions
969 ssize_t last = start + count;
970 mregion_t *r = bm->items.first();
971 r->start = start;
972 for (size_t i=1; i<bm->items.size(); ++i)
973 {
974 r = bm->items.uget(i);
975 r->start = last;
976 }
977
978 // Iterate over all variants
979 while (true)
980 {
981 bool match = brute_match_variable(bm, start, count);
982 if (match)
983 return !cmd->bInverse;
984
985 // Try to search next fixed pattern
986 if (!brute_next_variable(bm, start, count))
987 return cmd->bInverse;
988 }
989
990 return false;
991 }
992
993 bool PathPattern::add_range_matcher(sequence_matcher_t *sm, const pos_t *pos)
994 {
995 // Simple case (one command) ?
996 const cmd_t *cmd = sm->cmd;
997 if (pos->count <= 1)
998 {
999 const cmd_t *xc = cmd->sChildren.uget(pos->start);
1000 matcher_t *m = create_matcher(sm, xc);
1001 if ((m != NULL) && (sm->var.add(m)))
1002 return true;
1003
1004 destroy_matcher(m);
1005 return false;
1006 }
1007
1008 // Create brute matcher
1009 brute_matcher_t *bm = new brute_matcher_t();
1010 if (bm == NULL)
1011 return false;
1012
1013 bm->type = M_BRUTE;
1014 bm->match = brute_matcher_match;
1015 bm->cmd = cmd;
1016 bm->pat = sm->pat;
1017 bm->str = sm->str;
1018 bm->flags = sm->flags;
1019
1020 // Add matcher
1021 if (!sm->var.add(bm))
1022 {
1023 destroy_matcher(bm);
1024 return false;
1025 }
1026
1027 for (size_t i=0; i<pos->count; ++i)
1028 {
1029 const cmd_t *xc = cmd->sChildren.uget(pos->start + i);
1030
1031 // Add new sub-matcher descriptor to brute matcher
1032 mregion_t *r = bm->items.add();
1033 if (r == NULL)
1034 return false;
1035
1036 // Create sub-matcher
1037 r->start = 0;
1038 r->matcher = create_matcher(bm, xc);
1039 r->cmd = NULL;
1040
1041 if (r->matcher == NULL)
1042 return false;
1043 }
1044
1045 return true;
1046 }
1047
1048 PathPattern::matcher_t *PathPattern::create_matcher(const matcher_t *src, const cmd_t *cmd)
1049 {
1050 switch (cmd->nCommand)
1051 {
1052 case CMD_PATTERN:
1053 {
1054 matcher_t *m = new matcher_t();
1055 if (m == NULL)
1056 return NULL;
1057
1058 m->type = M_PATTERN;
1059 m->match = pattern_matcher_match;
1060 m->cmd = cmd;
1061 m->pat = src->pat;
1062 m->str = src->str;
1063 m->flags = src->flags;
1064
1065 return m;
1066 }
1067
1068 case CMD_ANY:
1069 {
1070 any_matcher_t *m = new any_matcher_t();
1071 if (m == NULL)
1072 return NULL;
1073
1074 m->type = M_ANY;
1075 m->match = any_matcher_match;
1076 m->cmd = cmd;
1077 m->pat = src->pat;
1078 m->str = src->str;
1079 m->flags = src->flags;
1080 m->bad = -1;
1081 m->good = -1;
1082
1083 return m;
1084 }
1085
1086 case CMD_ANYPATH:
1087 {
1088 matcher_t *m = new matcher_t();
1089 if (m == NULL)
1090 return NULL;
1091
1092 m->type = M_ANYPATH;
1093 m->match = anypath_matcher_match;
1094 m->cmd = cmd;
1095 m->pat = src->pat;
1096 m->str = src->str;
1097 m->flags = src->flags;
1098
1099 return m;
1100 }
1101
1102 case CMD_AND:
1103 case CMD_OR:
1104 {
1105 bool_matcher_t *m = new bool_matcher_t();
1106 if (m == NULL)
1107 return NULL;
1108
1109 m->type = M_BOOL;
1110 m->match = (cmd->nCommand == CMD_AND) ? and_matcher_match : or_matcher_match;
1111 m->cmd = cmd;
1112 m->pat = src->pat;
1113 m->str = src->str;
1114 m->flags = src->flags;
1115
1116 // Create child matchers
1117 for (size_t i=0, n=cmd->sChildren.size(); i<n; ++i)
1118 {
1119 const cmd_t *c = cmd->sChildren.uget(i);
1120 matcher_t *cm = create_matcher(m, c);
1121 if ((cm == NULL) || (!m->cond.add(cm)))
1122 {
1123 destroy_matcher(m);
1124 return NULL;
1125 }
1126 }
1127
1128 return m;
1129 }
1130
1131 case CMD_SEQUENCE:
1132 {
1133 sequence_matcher_t *m = new sequence_matcher_t();
1134 if (m == NULL)
1135 return NULL;
1136
1137 m->type = M_SEQUENCE;
1138 m->match = sequence_matcher_match;
1139 m->cmd = cmd;
1140 m->pat = src->pat;
1141 m->str = src->str;
1142 m->flags = src->flags;
1143 m->prefix = 0;
1144 m->postfix = 0;
1145
1146 size_t i = 0, n = cmd->sChildren.size();
1147
1148 // Count prefixes
1149 for ( ; i < n; ++i)
1150 {
1151 const cmd_t *xc = cmd->sChildren.uget(i);
1152 if ((xc->nCommand != CMD_PATTERN) || (xc->bInverse))
1153 break;
1154 ++m->prefix;
1155 }
1156
1157 // Count postfixes
1158 for ( ; i < n; --n)
1159 {
1160 const cmd_t *xc = cmd->sChildren.uget(n-1);
1161 if ((xc->nCommand != CMD_PATTERN) || (xc->bInverse))
1162 break;
1163 ++m->postfix;
1164 }
1165
1166 // Scan for fixed items and create additional matchers
1167 pos_t range;
1168 range.start = 0;
1169 range.count = 0;
1170
1171 for (; i<n; ++i)
1172 {
1173 const cmd_t *xc = cmd->sChildren.uget(i);
1174 if ((xc->nCommand == CMD_PATTERN) && (!xc->bInverse))
1175 {
1176 mregion_t *r;
1177
1178 // Add variable matcher
1179 if (!add_range_matcher(m, &range))
1180 {
1181 destroy_matcher(m);
1182 return NULL;
1183 }
1184
1185 // Add fixed range matcher
1186 if ((r = m->fixed.add()) == NULL)
1187 {
1188 destroy_matcher(m);
1189 return NULL;
1190 }
1191
1192 // Initialize pattern matcher
1193 r->start = 0;
1194 r->matcher = NULL;
1195 r->cmd = xc;
1196
1197 // Reset counter
1198 range.count = 0;
1199 }
1200 else
1201 {
1202 // Save range as variable-size range
1203 if (range.count == 0)
1204 range.start = i;
1205 ++range.count;
1206 }
1207 }
1208
1209 // Last operation: add variable matcher if there is one
1210 if (range.count <= 0)
1211 return m;
1212
1213 // Add last range
1214 if (!add_range_matcher(m, &range))
1215 {
1216 destroy_matcher(m);
1217 return NULL;
1218 }
1219
1220 return m;
1221 }
1222
1223 default:
1224 break;
1225 }
1226
1227 return NULL;
1228 }
1229
1230 void PathPattern::destroy_matcher(matcher_t *m)
1231 {
1232 if (m == NULL)
1233 return;
1234
1235 switch (m->type)
1236 {
1237 // Pattern matcher
1238 case M_PATTERN:
1239 case M_ANYPATH:
1240 {
1241 delete m;
1242 break;
1243 }
1244
1245 case M_ANY:
1246 {
1247 any_matcher_t *am = static_cast<any_matcher_t *>(m);
1248 delete am;
1249 break;
1250 }
1251
1252 case M_BOOL:
1253 {
1254 bool_matcher_t *bm = static_cast<bool_matcher_t *>(m);
1255
1256 // Destroy all child matchers
1257 for (size_t i=0, n=bm->cond.size(); i<n; ++i)
1258 destroy_matcher(bm->cond.uget(i));
1259
1260 delete bm;
1261 break;
1262 }
1263
1264 case M_SEQUENCE:
1265 {
1266 sequence_matcher_t *sm = static_cast<sequence_matcher_t *>(m);
1267
1268 // Destroy fixed matchers
1269 for (size_t i=0, n=sm->fixed.size(); i<n; ++i)
1270 {
1271 mregion_t *r = sm->fixed.uget(i);
1272 destroy_matcher(r->matcher);
1273 }
1274
1275 // Destroy variable matchers
1276 for (size_t i=0, n=sm->var.size(); i<n; ++i)
1277 destroy_matcher(sm->var.uget(i));
1278
1279 delete sm;
1280 break;
1281 }
1282
1283 case M_BRUTE:
1284 {
1285 brute_matcher_t *bm = static_cast<brute_matcher_t *>(m);
1286
1287 // Destroy nested matchers
1288 for (size_t i=0, n=bm->items.size(); i<n; ++i)
1289 {
1290 mregion_t *r = bm->items.uget(i);
1291 destroy_matcher(r->matcher);
1292 }
1293
1294 delete bm;
1295 break;
1296 }
1297
1298 default:
1299 break;
1300 }
1301 }
1302
1303 bool PathPattern::match_full(const LSPString *path) const
1304 {
1305 matcher_t root;
1306 root.cmd = NULL;
1307 root.pat = &sMask;
1308 root.str = path;
1309 root.flags = nFlags & MATCH_CASE;
1310
1311 matcher_t *rm = create_matcher(&root, pRoot);
1312 if (rm == NULL)
1313 return false;
1314
1315 // Seek the matcher
1316 bool match = rm->match(rm, 0, path->length()) ^ bool(nFlags & INVERSE);
1317
1318 destroy_matcher(rm);
1319
1320 return match;
1321 }
1322
1323 status_t PathPattern::set(const char *pattern, size_t flags)
1324 {
1325 LSPString tmp;
1326 return (tmp.set_utf8(pattern)) ? parse(&tmp, flags) : STATUS_NO_MEM;
1327 }
1328
1329 size_t PathPattern::set_flags(size_t flags)
1330 {
1331 size_t old = nFlags;
1332 nFlags = flags & (INVERSE | MATCH_CASE | FULL_PATH);
1333 return old;
1334 }
1335
1336 bool PathPattern::test(const char *path) const
1337 {
1338 if (pRoot == NULL)
1339 return false;
1340
1341 Path tmp;
1342 if (tmp.set(path) != STATUS_OK)
1343 return false;
1344
1345 if (!(nFlags & FULL_PATH))
1346 {
1347 if (tmp.remove_base() != STATUS_OK)
1348 return false;
1349 }
1350
1351 return match_full(tmp.as_string());
1352 }
1353
1354 bool PathPattern::test(const LSPString *path) const
1355 {
1356 if (pRoot == NULL)
1357 return false;
1358
1359 Path tmp;
1360 if (tmp.set(path) != STATUS_OK)
1361 return false;
1362
1363 if (!(nFlags & FULL_PATH))
1364 {
1365 if (tmp.remove_base() != STATUS_OK)
1366 return false;
1367 }
1368
1369 return match_full(tmp.as_string());
1370 }
1371
1372 bool PathPattern::test(const Path *path) const
1373 {
1374 if (pRoot == NULL)
1375 return false;
1376
1377 if (nFlags & FULL_PATH)
1378 return match_full(path->as_string());
1379
1380 Path tmp;
1381 if (tmp.get_last(&tmp) != STATUS_OK)
1382 return false;
1383
1384 return match_full(tmp.as_string());
1385 }
1386
1387 void PathPattern::swap(PathPattern *dst)
1388 {
1389 sMask.swap(dst->sMask);
1390 lsp::swap(pRoot, dst->pRoot);
1391 lsp::swap(nFlags, dst->nFlags);
1392 }
1393
1394 } /* namespace io */
1395 } /* namespace lsp */