eab13a7bc8ab71daf5b8896ed089f289f294a9e9
[dragonfly.git] / contrib / tre / lib / tre-match-backtrack.c
1 /*
2   tre-match-backtrack.c - TRE backtracking regex matching engine
3
4   This software is released under a BSD-style license.
5   See the file LICENSE for details and copyright.
6
7 */
8
9 /*
10   This matcher is for regexps that use back referencing.  Regexp matching
11   with back referencing is an NP-complete problem on the number of back
12   references.  The easiest way to match them is to use a backtracking
13   routine which basically goes through all possible paths in the TNFA
14   and chooses the one which results in the best (leftmost and longest)
15   match.  This can be spectacularly expensive and may run out of stack
16   space, but there really is no better known generic algorithm.  Quoting
17   Henry Spencer from comp.compilers:
18   <URL: http://compilers.iecc.com/comparch/article/93-03-102>
19
20     POSIX.2 REs require longest match, which is really exciting to
21     implement since the obsolete ("basic") variant also includes
22     \<digit>.  I haven't found a better way of tackling this than doing
23     a preliminary match using a DFA (or simulation) on a modified RE
24     that just replicates subREs for \<digit>, and then doing a
25     backtracking match to determine whether the subRE matches were
26     right.  This can be rather slow, but I console myself with the
27     thought that people who use \<digit> deserve very slow execution.
28     (Pun unintentional but very appropriate.)
29
30 */
31
32
33 #ifdef HAVE_CONFIG_H
34 #include <config.h>
35 #endif /* HAVE_CONFIG_H */
36
37 #ifdef TRE_USE_ALLOCA
38 /* AIX requires this to be the first thing in the file.  */
39 #ifndef __GNUC__
40 # if HAVE_ALLOCA_H
41 #  include <alloca.h>
42 # else
43 #  ifdef _AIX
44  #pragma alloca
45 #  else
46 #   ifndef alloca /* predefined by HP cc +Olibcalls */
47 char *alloca ();
48 #   endif
49 #  endif
50 # endif
51 #endif
52 #endif /* TRE_USE_ALLOCA */
53
54 #include <assert.h>
55 #include <stdlib.h>
56 #include <string.h>
57 #ifdef HAVE_WCHAR_H
58 #include <wchar.h>
59 #endif /* HAVE_WCHAR_H */
60 #ifdef HAVE_WCTYPE_H
61 #include <wctype.h>
62 #endif /* HAVE_WCTYPE_H */
63 #ifndef TRE_WCHAR
64 #include <ctype.h>
65 #endif /* !TRE_WCHAR */
66 #ifdef HAVE_MALLOC_H
67 #include <malloc.h>
68 #endif /* HAVE_MALLOC_H */
69
70 #include "tre-internal.h"
71 #include "tre-mem.h"
72 #include "tre-match-utils.h"
73 #include "tre.h"
74 #include "xmalloc.h"
75
76 typedef struct {
77   int pos;
78   const char *str_byte;
79 #ifdef TRE_WCHAR
80   const wchar_t *str_wide;
81 #endif /* TRE_WCHAR */
82   tre_tnfa_transition_t *state;
83   int state_id;
84   int next_c;
85   int *tags;
86 #ifdef TRE_MBSTATE
87   mbstate_t mbstate;
88 #endif /* TRE_MBSTATE */
89 } tre_backtrack_item_t;
90
91 typedef struct tre_backtrack_struct {
92   tre_backtrack_item_t item;
93   struct tre_backtrack_struct *prev;
94   struct tre_backtrack_struct *next;
95 } *tre_backtrack_t;
96
97 #ifdef TRE_WCHAR
98 #define BT_STACK_WIDE_IN(_str_wide)     stack->item.str_wide = (_str_wide)
99 #define BT_STACK_WIDE_OUT               (str_wide) = stack->item.str_wide
100 #else /* !TRE_WCHAR */
101 #define BT_STACK_WIDE_IN(_str_wide)
102 #define BT_STACK_WIDE_OUT
103 #endif /* !TRE_WCHAR */
104
105 #ifdef TRE_MBSTATE
106 #define BT_STACK_MBSTATE_IN  stack->item.mbstate = (mbstate)
107 #define BT_STACK_MBSTATE_OUT (mbstate) = stack->item.mbstate
108 #else /* !TRE_MBSTATE */
109 #define BT_STACK_MBSTATE_IN
110 #define BT_STACK_MBSTATE_OUT
111 #endif /* !TRE_MBSTATE */
112
113
114 #ifdef TRE_USE_ALLOCA
115 #define tre_bt_mem_new            tre_mem_newa
116 #define tre_bt_mem_alloc          tre_mem_alloca
117 #define tre_bt_mem_destroy(obj)   do { } while (0)
118 #else /* !TRE_USE_ALLOCA */
119 #define tre_bt_mem_new            tre_mem_new
120 #define tre_bt_mem_alloc          tre_mem_alloc
121 #define tre_bt_mem_destroy        tre_mem_destroy
122 #endif /* !TRE_USE_ALLOCA */
123
124
125 #define BT_STACK_PUSH(_pos, _str_byte, _str_wide, _state, _state_id, _next_c, _tags, _mbstate) \
126   do                                                                          \
127     {                                                                         \
128       int i;                                                                  \
129       if (!stack->next)                                                       \
130         {                                                                     \
131           tre_backtrack_t s;                                                  \
132           s = tre_bt_mem_alloc(mem, sizeof(*s));                              \
133           if (!s)                                                             \
134             {                                                                 \
135               tre_bt_mem_destroy(mem);                                        \
136               if (tags)                                                       \
137                 xfree(tags);                                                  \
138               if (pmatch)                                                     \
139                 xfree(pmatch);                                                \
140               if (states_seen)                                                \
141                 xfree(states_seen);                                           \
142               return REG_ESPACE;                                              \
143             }                                                                 \
144           s->prev = stack;                                                    \
145           s->next = NULL;                                                     \
146           s->item.tags = tre_bt_mem_alloc(mem,                                \
147                                           sizeof(*tags) * tnfa->num_tags);    \
148           if (!s->item.tags)                                                  \
149             {                                                                 \
150               tre_bt_mem_destroy(mem);                                        \
151               if (tags)                                                       \
152                 xfree(tags);                                                  \
153               if (pmatch)                                                     \
154                 xfree(pmatch);                                                \
155               if (states_seen)                                                \
156                 xfree(states_seen);                                           \
157               return REG_ESPACE;                                              \
158             }                                                                 \
159           stack->next = s;                                                    \
160           stack = s;                                                          \
161         }                                                                     \
162       else                                                                    \
163         stack = stack->next;                                                  \
164       stack->item.pos = (_pos);                                               \
165       stack->item.str_byte = (_str_byte);                                     \
166       BT_STACK_WIDE_IN(_str_wide);                                            \
167       stack->item.state = (_state);                                           \
168       stack->item.state_id = (_state_id);                                     \
169       stack->item.next_c = (_next_c);                                         \
170       for (i = 0; i < tnfa->num_tags; i++)                                    \
171         stack->item.tags[i] = (_tags)[i];                                     \
172       BT_STACK_MBSTATE_IN;                                                    \
173     }                                                                         \
174   while (/*CONSTCOND*/0)
175
176 #define BT_STACK_POP()                                                        \
177   do                                                                          \
178     {                                                                         \
179       int i;                                                                  \
180       assert(stack->prev);                                                    \
181       pos = stack->item.pos;                                                  \
182       if (type == STR_USER)                                                   \
183         str_source->rewind(pos + pos_add_next, str_source->context);          \
184       str_byte = stack->item.str_byte;                                        \
185       BT_STACK_WIDE_OUT;                                                      \
186       state = stack->item.state;                                              \
187       next_c = stack->item.next_c;                                            \
188       for (i = 0; i < tnfa->num_tags; i++)                                    \
189         tags[i] = stack->item.tags[i];                                        \
190       BT_STACK_MBSTATE_OUT;                                                   \
191       stack = stack->prev;                                                    \
192     }                                                                         \
193   while (/*CONSTCOND*/0)
194
195 #undef MIN
196 #define MIN(a, b) ((a) <= (b) ? (a) : (b))
197
198 reg_errcode_t
199 tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string,
200                        int len, tre_str_type_t type, int *match_tags,
201                        int eflags, int *match_end_ofs)
202 {
203   /* State variables required by GET_NEXT_WCHAR. */
204   tre_char_t prev_c = 0, next_c = 0;
205   const char *str_byte = string;
206   int pos = 0;
207   unsigned int pos_add_next = 1;
208 #ifdef TRE_WCHAR
209   const wchar_t *str_wide = string;
210 #ifdef TRE_MBSTATE
211   mbstate_t mbstate;
212 #endif /* TRE_MBSTATE */
213 #endif /* TRE_WCHAR */
214   int reg_notbol = eflags & REG_NOTBOL;
215   int reg_noteol = eflags & REG_NOTEOL;
216   int reg_newline = tnfa->cflags & REG_NEWLINE;
217   int str_user_end = 0;
218
219   /* These are used to remember the necessary values of the above
220      variables to return to the position where the current search
221      started from. */
222   int next_c_start;
223   const char *str_byte_start;
224   int pos_start = -1;
225 #ifdef TRE_WCHAR
226   const wchar_t *str_wide_start;
227 #endif /* TRE_WCHAR */
228 #ifdef TRE_MBSTATE
229   mbstate_t mbstate_start;
230 #endif /* TRE_MBSTATE */
231
232   /* End offset of best match so far, or -1 if no match found yet. */
233   int match_eo = -1;
234   /* Tag arrays. */
235   int *next_tags, *tags = NULL;
236   /* Current TNFA state. */
237   tre_tnfa_transition_t *state;
238   int *states_seen = NULL;
239
240   /* Memory allocator to for allocating the backtracking stack. */
241   tre_mem_t mem = tre_bt_mem_new();
242
243   /* The backtracking stack. */
244   tre_backtrack_t stack;
245
246   tre_tnfa_transition_t *trans_i;
247   regmatch_t *pmatch = NULL;
248   int ret;
249
250 #ifdef TRE_MBSTATE
251   memset(&mbstate, '\0', sizeof(mbstate));
252 #endif /* TRE_MBSTATE */
253
254   if (!mem)
255     return REG_ESPACE;
256   stack = tre_bt_mem_alloc(mem, sizeof(*stack));
257   if (!stack)
258     {
259       ret = REG_ESPACE;
260       goto error_exit;
261     }
262   stack->prev = NULL;
263   stack->next = NULL;
264
265   DPRINT(("tnfa_execute_backtrack, input type %d\n", type));
266   DPRINT(("len = %d\n", len));
267
268 #ifdef TRE_USE_ALLOCA
269   tags = alloca(sizeof(*tags) * tnfa->num_tags);
270   pmatch = alloca(sizeof(*pmatch) * tnfa->num_submatches);
271   states_seen = alloca(sizeof(*states_seen) * tnfa->num_states);
272 #else /* !TRE_USE_ALLOCA */
273   if (tnfa->num_tags)
274     {
275       tags = xmalloc(sizeof(*tags) * tnfa->num_tags);
276       if (!tags)
277         {
278           ret = REG_ESPACE;
279           goto error_exit;
280         }
281     }
282   if (tnfa->num_submatches)
283     {
284       pmatch = xmalloc(sizeof(*pmatch) * tnfa->num_submatches);
285       if (!pmatch)
286         {
287           ret = REG_ESPACE;
288           goto error_exit;
289         }
290     }
291   if (tnfa->num_states)
292     {
293       states_seen = xmalloc(sizeof(*states_seen) * tnfa->num_states);
294       if (!states_seen)
295         {
296           ret = REG_ESPACE;
297           goto error_exit;
298         }
299     }
300 #endif /* !TRE_USE_ALLOCA */
301
302  retry:
303   {
304     int i;
305     for (i = 0; i < tnfa->num_tags; i++)
306       {
307         tags[i] = -1;
308         if (match_tags)
309           match_tags[i] = -1;
310       }
311     for (i = 0; i < tnfa->num_states; i++)
312       states_seen[i] = 0;
313   }
314
315   state = NULL;
316   pos = pos_start;
317   if (type == STR_USER)
318     str_source->rewind(pos + pos_add_next, str_source->context);
319   GET_NEXT_WCHAR();
320   pos_start = pos;
321   next_c_start = next_c;
322   str_byte_start = str_byte;
323 #ifdef TRE_WCHAR
324   str_wide_start = str_wide;
325 #endif /* TRE_WCHAR */
326 #ifdef TRE_MBSTATE
327   mbstate_start = mbstate;
328 #endif /* TRE_MBSTATE */
329
330   /* Handle initial states. */
331   next_tags = NULL;
332   for (trans_i = tnfa->initial; trans_i->state; trans_i++)
333     {
334       DPRINT(("> init %p, prev_c %lc\n", trans_i->state, (tre_cint_t)prev_c));
335       if (trans_i->assertions && CHECK_ASSERTIONS(trans_i->assertions))
336         {
337           DPRINT(("assert failed\n"));
338           continue;
339         }
340       if (state == NULL)
341         {
342           /* Start from this state. */
343           state = trans_i->state;
344           next_tags = trans_i->tags;
345         }
346       else
347         {
348           /* Backtrack to this state. */
349           DPRINT(("saving state %d for backtracking\n", trans_i->state_id));
350           BT_STACK_PUSH(pos, str_byte, str_wide, trans_i->state,
351                         trans_i->state_id, next_c, tags, mbstate);
352           {
353             int *tmp = trans_i->tags;
354             if (tmp)
355               while (*tmp >= 0)
356                 stack->item.tags[*tmp++] = pos;
357           }
358         }
359     }
360
361   if (next_tags)
362     for (; *next_tags >= 0; next_tags++)
363       tags[*next_tags] = pos;
364
365
366   DPRINT(("entering match loop, pos %d, str_byte %p\n", pos, str_byte));
367   DPRINT(("pos:chr/code | state and tags\n"));
368   DPRINT(("-------------+------------------------------------------------\n"));
369
370   if (state == NULL)
371     goto backtrack;
372
373   while (/*CONSTCOND*/1)
374     {
375       tre_tnfa_transition_t *next_state;
376       int empty_br_match;
377
378       DPRINT(("start loop\n"));
379       if (state == tnfa->final)
380         {
381           DPRINT(("  match found, %d %d\n", match_eo, pos));
382           if (match_eo < pos
383               || (match_eo == pos
384                   && match_tags
385                   && tre_tag_order(tnfa->num_tags, tnfa->tag_directions,
386                                    tags, match_tags)))
387             {
388               int i;
389               /* This match wins the previous match. */
390               DPRINT(("  win previous\n"));
391               match_eo = pos;
392               if (match_tags)
393                 for (i = 0; i < tnfa->num_tags; i++)
394                   match_tags[i] = tags[i];
395             }
396           /* Our TNFAs never have transitions leaving from the final state,
397              so we jump right to backtracking. */
398           goto backtrack;
399         }
400
401 #ifdef TRE_DEBUG
402       DPRINT(("%3d:%2lc/%05d | %p ", pos, (tre_cint_t)next_c, (int)next_c,
403               state));
404       {
405         int i;
406         for (i = 0; i < tnfa->num_tags; i++)
407           DPRINT(("%d%s", tags[i], i < tnfa->num_tags - 1 ? ", " : ""));
408         DPRINT(("\n"));
409       }
410 #endif /* TRE_DEBUG */
411
412       /* Go to the next character in the input string. */
413       empty_br_match = 0;
414       trans_i = state;
415       if (trans_i->state && trans_i->assertions & ASSERT_BACKREF)
416         {
417           /* This is a back reference state.  All transitions leaving from
418              this state have the same back reference "assertion".  Instead
419              of reading the next character, we match the back reference. */
420           int so, eo, bt = trans_i->u.backref;
421           int bt_len;
422           int result;
423
424           DPRINT(("  should match back reference %d\n", bt));
425           /* Get the substring we need to match against.  Remember to
426              turn off REG_NOSUB temporarily. */
427           tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & /*LINTED*/!REG_NOSUB,
428                           tnfa, tags, pos);
429           so = pmatch[bt].rm_so;
430           eo = pmatch[bt].rm_eo;
431           bt_len = eo - so;
432
433 #ifdef TRE_DEBUG
434           {
435             int slen;
436             if (len < 0)
437               slen = bt_len;
438             else
439               slen = MIN(bt_len, len - pos);
440
441             if (type == STR_BYTE)
442               {
443                 DPRINT(("  substring (len %d) is [%d, %d[: '%.*s'\n",
444                         bt_len, so, eo, bt_len, (char*)string + so));
445                 DPRINT(("  current string is '%.*s'\n", slen, str_byte - 1));
446               }
447 #ifdef TRE_WCHAR
448             else if (type == STR_WIDE)
449               {
450                 DPRINT(("  substring (len %d) is [%d, %d[: '%.*" STRF "'\n",
451                         bt_len, so, eo, bt_len, (wchar_t*)string + so));
452                 DPRINT(("  current string is '%.*" STRF "'\n",
453                         slen, str_wide - 1));
454               }
455 #endif /* TRE_WCHAR */
456           }
457 #endif
458
459           if (len < 0)
460             {
461               if (type == STR_USER)
462                 result = str_source->compare((unsigned)so, (unsigned)pos,
463                                              (unsigned)bt_len,
464                                              str_source->context);
465 #ifdef TRE_WCHAR
466               else if (type == STR_WIDE)
467                 result = wcsncmp((const wchar_t*)string + so, str_wide - 1,
468                                  (size_t)bt_len);
469 #endif /* TRE_WCHAR */
470               else
471                 result = strncmp((const char*)string + so, str_byte - 1,
472                                  (size_t)bt_len);
473             }
474           else if (len - pos < bt_len)
475             result = 1;
476 #ifdef TRE_WCHAR
477           else if (type == STR_WIDE)
478             result = wmemcmp((const wchar_t*)string + so, str_wide - 1,
479                              (size_t)bt_len);
480 #endif /* TRE_WCHAR */
481           else
482             result = memcmp((const char*)string + so, str_byte - 1,
483                             (size_t)bt_len);
484
485           if (result == 0)
486             {
487               /* Back reference matched.  Check for infinite loop. */
488               if (bt_len == 0)
489                 empty_br_match = 1;
490               if (empty_br_match && states_seen[trans_i->state_id])
491                 {
492                   DPRINT(("  avoid loop\n"));
493                   goto backtrack;
494                 }
495
496               states_seen[trans_i->state_id] = empty_br_match;
497
498               /* Advance in input string and resync `prev_c', `next_c'
499                  and pos. */
500               DPRINT(("  back reference matched\n"));
501               str_byte += bt_len - 1;
502 #ifdef TRE_WCHAR
503               str_wide += bt_len - 1;
504 #endif /* TRE_WCHAR */
505               pos += bt_len - 1;
506               GET_NEXT_WCHAR();
507               DPRINT(("  pos now %d\n", pos));
508             }
509           else
510             {
511               DPRINT(("  back reference did not match\n"));
512               goto backtrack;
513             }
514         }
515       else
516         {
517           /* Check for end of string. */
518           if (len < 0)
519             {
520               if (type == STR_USER)
521                 {
522                   if (str_user_end)
523                     goto backtrack;
524                 }
525               else if (next_c == L'\0')
526                 goto backtrack;
527             }
528           else
529             {
530               if (pos >= len)
531                 goto backtrack;
532             }
533
534           /* Read the next character. */
535           GET_NEXT_WCHAR();
536         }
537
538       next_state = NULL;
539       for (trans_i = state; trans_i->state; trans_i++)
540         {
541           DPRINT(("  transition %d-%d (%c-%c) %d to %d\n",
542                   trans_i->code_min, trans_i->code_max,
543                   trans_i->code_min, trans_i->code_max,
544                   trans_i->assertions, trans_i->state_id));
545           if (trans_i->code_min <= (tre_cint_t)prev_c
546               && trans_i->code_max >= (tre_cint_t)prev_c)
547             {
548               if (trans_i->assertions
549                   && (CHECK_ASSERTIONS(trans_i->assertions)
550                       || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags)))
551                 {
552                   DPRINT(("  assertion failed\n"));
553                   continue;
554                 }
555
556               if (next_state == NULL)
557                 {
558                   /* First matching transition. */
559                   DPRINT(("  Next state is %d\n", trans_i->state_id));
560                   next_state = trans_i->state;
561                   next_tags = trans_i->tags;
562                 }
563               else
564                 {
565                   /* Second matching transition.  We may need to backtrack here
566                      to take this transition instead of the first one, so we
567                      push this transition in the backtracking stack so we can
568                      jump back here if needed. */
569                   DPRINT(("  saving state %d for backtracking\n",
570                           trans_i->state_id));
571                   BT_STACK_PUSH(pos, str_byte, str_wide, trans_i->state,
572                                 trans_i->state_id, next_c, tags, mbstate);
573                   {
574                     int *tmp;
575                     for (tmp = trans_i->tags; tmp && *tmp >= 0; tmp++)
576                       stack->item.tags[*tmp] = pos;
577                   }
578 #if 0 /* XXX - it's important not to look at all transitions here to keep
579          the stack small! */
580                   break;
581 #endif
582                 }
583             }
584         }
585
586       if (next_state != NULL)
587         {
588           /* Matching transitions were found.  Take the first one. */
589           state = next_state;
590
591           /* Update the tag values. */
592           if (next_tags)
593             while (*next_tags >= 0)
594               tags[*next_tags++] = pos;
595         }
596       else
597         {
598         backtrack:
599           /* A matching transition was not found.  Try to backtrack. */
600           if (stack->prev)
601             {
602               DPRINT(("  backtracking\n"));
603               if (stack->item.state->assertions && ASSERT_BACKREF)
604                 {
605                   DPRINT(("  states_seen[%d] = 0\n",
606                           stack->item.state_id));
607                   states_seen[stack->item.state_id] = 0;
608                 }
609
610               BT_STACK_POP();
611             }
612           else if (match_eo < 0)
613             {
614               /* Try starting from a later position in the input string. */
615               /* Check for end of string. */
616               if (len < 0)
617                 {
618                   if (next_c == L'\0')
619                     {
620                       DPRINT(("end of string.\n"));
621                       break;
622                     }
623                 }
624               else
625                 {
626                   if (pos >= len)
627                     {
628                       DPRINT(("end of string.\n"));
629                       break;
630                     }
631                 }
632               DPRINT(("restarting from next start position\n"));
633               next_c = next_c_start;
634 #ifdef TRE_MBSTATE
635               mbstate = mbstate_start;
636 #endif /* TRE_MBSTATE */
637               str_byte = str_byte_start;
638 #ifdef TRE_WCHAR
639               str_wide = str_wide_start;
640 #endif /* TRE_WCHAR */
641               goto retry;
642             }
643           else
644             {
645               DPRINT(("finished\n"));
646               break;
647             }
648         }
649     }
650
651   ret = match_eo >= 0 ? REG_OK : REG_NOMATCH;
652   *match_end_ofs = match_eo;
653
654  error_exit:
655   tre_bt_mem_destroy(mem);
656 #ifndef TRE_USE_ALLOCA
657   if (tags)
658     xfree(tags);
659   if (pmatch)
660     xfree(pmatch);
661   if (states_seen)
662     xfree(states_seen);
663 #endif /* !TRE_USE_ALLOCA */
664
665   return ret;
666 }