regex/TRE/lib/tre-match-utils.h

   1 /*
   2   tre-match-utils.h - TRE matcher helper definitions
   3
   4   This software is released under a BSD-style license.
   5   See the file LICENSE for details and copyright.
   6
   7 */
   8
   9 #include "tre-internal.h"
  10
  11 #define str_source ((const tre_str_source*)string)
  12
  13 #ifdef TRE_WCHAR
  14
  15 #ifdef TRE_MULTIBYTE
  16
  17 /* Wide character and multibyte support. */
  18
  19 #ifdef TRE_STR_USER
  20 #define GET_NEXT_WCHAR()                                                      \
  21   do {                                                                        \
  22     prev_c = next_c;                                                          \
  23     if (type == STR_BYTE)                                                     \
  24       {                                                                       \
  25         pos++;                                                                \
  26         if (len >= 0 && pos >= len)                                           \
  27           next_c = '\0';                                                      \
  28         else                                                                  \
  29           next_c = (unsigned char)(*str_byte++);                              \
  30       }                                                                       \
  31     else if (type == STR_WIDE)                                                \
  32       {                                                                       \
  33         pos++;                                                                \
  34         if (len >= 0 && pos >= len)                                           \
  35           next_c = L'\0';                                                     \
  36         else                                                                  \
  37           next_c = *str_wide++;                                               \
  38       }                                                                       \
  39     else if (type == STR_MBS)                                                 \
  40       {                                                                       \
  41         pos += pos_add_next;                                                  \
  42         if (str_byte == NULL)                                                 \
  43           next_c = L'\0';                                                     \
  44         else                                                                  \
  45           {                                                                   \
  46             size_t w;                                                         \
  47             int max;                                                          \
  48             if (len >= 0)                                                     \
  49               max = len - pos;                                                \
  50             else                                                              \
  51               max = 32;                                                       \
  52             if (max <= 0)                                                     \
  53               {                                                               \
  54                 next_c = L'\0';                                               \
  55                 pos_add_next = 1;                                             \
  56               }                                                               \
  57             else                                                              \
  58               {                                                               \
  59                 w = tre_mbrtowc_l(&next_c, str_byte, (size_t)max, &mbstate,   \
  60                                   tnfa->loc);                                 \
  61                 if (w == (size_t)-1 || w == (size_t)-2)                       \
  62                   return REG_ILLSEQ;                                          \
  63                 if (w == 0 && len >= 0)                                       \
  64                   {                                                           \
  65                     pos_add_next = 1;                                         \
  66                     next_c = 0;                                               \
  67                     str_byte++;                                               \
  68                   }                                                           \
  69                 else                                                          \
  70                   {                                                           \
  71                     pos_add_next = w;                                         \
  72                     str_byte += w;                                            \
  73                   }                                                           \
  74               }                                                               \
  75           }                                                                   \
  76       }                                                                       \
  77     else if (type == STR_USER)                                                \
  78       {                                                                       \
  79         pos += pos_add_next;                                                  \
  80         str_user_end = str_source->get_next_char(&next_c, &pos_add_next,      \
  81                                                  str_source->context);        \
  82       }                                                                       \
  83   } while(/*CONSTCOND*/0)
  84 #else /* !TRE_STR_USER */
  85 #define GET_NEXT_WCHAR()                                                      \
  86   do {                                                                        \
  87     prev_c = next_c;                                                          \
  88     if (type == STR_BYTE)                                                     \
  89       {                                                                       \
  90         pos++;                                                                \
  91         if (len >= 0 && pos >= len)                                           \
  92           next_c = '\0';                                                      \
  93         else                                                                  \
  94           next_c = (unsigned char)(*str_byte++);                              \
  95       }                                                                       \
  96     else if (type == STR_WIDE)                                                \
  97       {                                                                       \
  98         pos++;                                                                \
  99         if (len >= 0 && pos >= len)                                           \
 100           next_c = L'\0';                                                     \
 101         else                                                                  \
 102           next_c = *str_wide++;                                               \
 103       }                                                                       \
 104     else if (type == STR_MBS)                                                 \
 105       {                                                                       \
 106         pos += pos_add_next;                                                  \
 107         if (str_byte == NULL)                                                 \
 108           next_c = L'\0';                                                     \
 109         else                                                                  \
 110           {                                                                   \
 111             size_t w;                                                         \
 112             int max;                                                          \
 113             if (len >= 0)                                                     \
 114               max = len - pos;                                                \
 115             else                                                              \
 116               max = 32;                                                       \
 117             if (max <= 0)                                                     \
 118               {                                                               \
 119                 next_c = L'\0';                                               \
 120                 pos_add_next = 1;                                             \
 121               }                                                               \
 122             else                                                              \
 123               {                                                               \
 124                 w = tre_mbrtowc_l(&next_c, str_byte, (size_t)max, &mbstate,   \
 125                                   tnfa->loc);                                 \
 126                 if (w == (size_t)-1 || w == (size_t)-2)                       \
 127                   return REG_ILLSEQ;                                          \
 128                 if (w == 0 && len >= 0)                                       \
 129                   {                                                           \
 130                     pos_add_next = 1;                                         \
 131                     next_c = 0;                                               \
 132                     str_byte++;                                               \
 133                   }                                                           \
 134                 else                                                          \
 135                   {                                                           \
 136                     pos_add_next = w;                                         \
 137                     str_byte += w;                                            \
 138                   }                                                           \
 139               }                                                               \
 140           }                                                                   \
 141       }                                                                       \
 142   } while(/*CONSTCOND*/0)
 143 #endif /* !TRE_STR_USER */
 144
 145 #else /* !TRE_MULTIBYTE */
 146
 147 /* Wide character support, no multibyte support. */
 148
 149 #ifdef TRE_STR_USER
 150 #define GET_NEXT_WCHAR()                                                      \
 151   do {                                                                        \
 152     prev_c = next_c;                                                          \
 153     if (type == STR_BYTE)                                                     \
 154       {                                                                       \
 155         pos++;                                                                \
 156         if (len >= 0 && pos >= len)                                           \
 157           next_c = '\0';                                                      \
 158         else                                                                  \
 159           next_c = (unsigned char)(*str_byte++);                              \
 160       }                                                                       \
 161     else if (type == STR_WIDE)                                                \
 162       {                                                                       \
 163         pos++;                                                                \
 164         if (len >= 0 && pos >= len)                                           \
 165           next_c = L'\0';                                                     \
 166         else                                                                  \
 167           next_c = *str_wide++;                                               \
 168       }                                                                       \
 169     else if (type == STR_USER)                                                \
 170       {                                                                       \
 171         pos += pos_add_next;                                                  \
 172         str_user_end = str_source->get_next_char(&next_c, &pos_add_next,      \
 173                                                  str_source->context);        \
 174       }                                                                       \
 175   } while(/*CONSTCOND*/0)
 176 #else /* !TRE_STR_USER */
 177 #define GET_NEXT_WCHAR()                                                      \
 178   do {                                                                        \
 179     prev_c = next_c;                                                          \
 180     if (type == STR_BYTE)                                                     \
 181       {                                                                       \
 182         pos++;                                                                \
 183         if (len >= 0 && pos >= len)                                           \
 184           next_c = '\0';                                                      \
 185         else                                                                  \
 186           next_c = (unsigned char)(*str_byte++);                              \
 187       }                                                                       \
 188     else if (type == STR_WIDE)                                                \
 189       {                                                                       \
 190         pos++;                                                                \
 191         if (len >= 0 && pos >= len)                                           \
 192           next_c = L'\0';                                                     \
 193         else                                                                  \
 194           next_c = *str_wide++;                                               \
 195       }                                                                       \
 196   } while(/*CONSTCOND*/0)
 197 #endif /* !TRE_STR_USER */
 198
 199 #endif /* !TRE_MULTIBYTE */
 200
 201 #else /* !TRE_WCHAR */
 202
 203 /* No wide character or multibyte support. */
 204
 205 #ifdef TRE_STR_USER
 206 #define GET_NEXT_WCHAR()                                                      \
 207   do {                                                                        \
 208     prev_c = next_c;                                                          \
 209     if (type == STR_BYTE)                                                     \
 210       {                                                                       \
 211         pos++;                                                                \
 212         if (len >= 0 && pos >= len)                                           \
 213           next_c = '\0';                                                      \
 214         else                                                                  \
 215           next_c = (unsigned char)(*str_byte++);                              \
 216       }                                                                       \
 217     else if (type == STR_USER)                                                \
 218       {                                                                       \
 219         pos += pos_add_next;                                                  \
 220         str_user_end = str_source->get_next_char(&next_c, &pos_add_next,      \
 221                                                  str_source->context);        \
 222       }                                                                       \
 223   } while(/*CONSTCOND*/0)
 224 #else /* !TRE_STR_USER */
 225 #define GET_NEXT_WCHAR()                                                      \
 226   do {                                                                        \
 227     prev_c = next_c;                                                          \
 228     if (type == STR_BYTE)                                                     \
 229       {                                                                       \
 230         pos++;                                                                \
 231         if (len >= 0 && pos >= len)                                           \
 232           next_c = '\0';                                                      \
 233         else                                                                  \
 234           next_c = (unsigned char)(*str_byte++);                              \
 235       }                                                                       \
 236   } while(/*CONSTCOND*/0)
 237 #endif /* !TRE_STR_USER */
 238
 239 #endif /* !TRE_WCHAR */
 240
 241
 242
 243 /* Assumes tre_tnfa_t *tnfa in scope */
 244 #define IS_WORD_CHAR(c)  ((c) == L'_' || tre_isalnum_l(c, tnfa->loc))
 245
 246 #define CHECK_ASSERTIONS(assertions)                                          \
 247   (((assertions & ASSERT_AT_BOL)                                              \
 248     && (pos > 0 || reg_notbol)                                                \
 249     && (prev_c != L'\n' || !reg_newline))                                     \
 250    || ((assertions & ASSERT_AT_EOL)                                           \
 251        && (next_c != L'\0' || reg_noteol)                                     \
 252        && (next_c != L'\n' || !reg_newline))                                  \
 253    || ((assertions & ASSERT_AT_BOW)                                           \
 254        && (IS_WORD_CHAR(prev_c) || !IS_WORD_CHAR(next_c)))                    \
 255    || ((assertions & ASSERT_AT_EOW)                                           \
 256        && (!IS_WORD_CHAR(prev_c) || IS_WORD_CHAR(next_c)))                    \
 257    || ((assertions & ASSERT_AT_WB)                                            \
 258        && (pos != 0 && next_c != L'\0'                                        \
 259            && IS_WORD_CHAR(prev_c) == IS_WORD_CHAR(next_c)))                  \
 260    || ((assertions & ASSERT_AT_WB_NEG)                                        \
 261        && (pos == 0 || next_c == L'\0'                                        \
 262            || IS_WORD_CHAR(prev_c) != IS_WORD_CHAR(next_c))))
 263
 264 #define CHECK_CHAR_CLASSES(trans_i, tnfa, eflags)                             \
 265   ((trans_i->assertions & ASSERT_BRACKET_MATCH)                               \
 266     && !tre_bracket_match(trans_i->u.bracket_match_list,(tre_cint_t)prev_c,    \
 267                                       tnfa))
 268
 269
 270
 271
 272 inline static int
 273 tre_tag_get(const tre_tag_t *tags, int i)
 274 {
 275   tags += i;
 276   return tags->count > 0 ? tags->value : -1;
 277 }
 278
 279 inline static void
 280 tre_tag_set(tre_tag_t *tags, int i, int val, int touch)
 281 {
 282   tags += i;
 283   if (tags->count++ == 0)
 284     tags->first = val;
 285   tags->value = val;
 286   tags->touch = touch;
 287 }
 288
 289 inline static void
 290 tre_tag_reset(tre_tag_t *tags, int i)
 291 {
 292   tags[i].count = 0;
 293 }
 294
 295 inline static int
 296 tre_tag_touch_get(const tre_tag_t *tags, int i)
 297 {
 298   return tags[i].touch;
 299 }
 300
 301 #ifdef TRE_DEBUG
 302 inline static void
 303 tre_print_tags(const tre_tag_t *tags, int num_tags)
 304 {
 305   int i;
 306   for (i = 0; i < num_tags; i++, tags++)
 307     {
 308       switch(tags->count)
 309         {
 310         case 0:
 311           DPRINT(("%d:(0,-1)", i));
 312           break;
 313         case 1:
 314           DPRINT(("%d:(1,%d)", i, tags->first));
 315           break;
 316         default:
 317           DPRINT(("%d:(%d,%d,%d)", i, tags->count, tags->first,
 318                   tags->value));
 319           break;
 320         }
 321       if (i < (num_tags - 1))
 322         DPRINT((" "));
 323     }
 324 }
 325
 326 inline static void
 327 tre_print_tags_all(const tre_tag_t *tags, int num_tags)
 328 {
 329   int i;
 330   for (i = 0; i < num_tags; i++, tags++)
 331     {
 332       switch(tags->count)
 333         {
 334         case 0:
 335           DPRINT(("%d:(0,-1)/%d", i, tags->touch));
 336           break;
 337         case 1:
 338           DPRINT(("%d:(1,%d)/%d", i, tags->first, tags->touch));
 339           break;
 340         default:
 341           DPRINT(("%d:(%d,%d,%d)/%d", i, tags->count, tags->first,
 342                   tags->value, tags->touch));
 343           break;
 344         }
 345       if (i < (num_tags - 1))
 346         DPRINT((" "));
 347     }
 348 }
 349 #endif /* TRE_DEBUG */
 350
 351 /* Return < 0, = 0 or > 0 depending on how the start/end pairs of a minimal
 352  * group between t1 and t2 compare (t1 loses if < 0, t1 wins if > 0) */
 353 inline static int
 354 tre_minimal_tag_order(int start, int end, const tre_tag_t *tags1,
 355                       const tre_tag_t *tags2)
 356 {
 357   const tre_tag_t *t1, *t2;
 358
 359   t1 = tags1 + start;
 360   t2 = tags2 + start;
 361   /* We need both start tags to be set */
 362   if (t1->count == 0 || t2->count == 0)
 363     return 0;
 364
 365   /* The start tags must be equal */
 366   if (t1->value != t2->value)
 367     return 0;
 368
 369   t1 = tags1 + end;
 370   t2 = tags2 + end;
 371   /* For the end tags, we prefer set over unset, because unset means that
 372    * the end tag is still growing */
 373   if (t1->count == 0)
 374     {
 375       /* if t2 is set, t1 loses since it is unset */
 376       if (t2->count != 0)
 377         return -1;
 378     }
 379   /* if t2 not set, t1 wins since it is set */
 380   else if (t2->count == 0)
 381     return 1;
 382
 383   /* least current value wins */
 384   return t2->value - t1->value;
 385 }
 386
 387 /* Return < 0, = 0 or > 0 depending on how the i-th item of t1 and t2 compare
 388  * (t1 loses if < 0, t1 wins if > 0) */
 389 inline static int
 390 tre_tag_order_1(int i, tre_tag_direction_t dir, const tre_tag_t *t1,
 391                 const tre_tag_t *t2)
 392 {
 393   int diff;
 394
 395   t1 += i;
 396   t2 += i;
 397   switch (dir)
 398     {
 399     case TRE_TAG_MINIMIZE:
 400       /* least current value wins (because tags are initialized to all zeros,
 401        * unset wins over set; also, tre_minimal_tag_order() will have already
 402        * been run, which checks for being unset) */
 403       return t2->value - t1->value;
 404
 405     case TRE_TAG_MAXIMIZE:
 406       /* prefer set */
 407       if (t1->count == 0)
 408         {
 409           /* if neither t1 and t2 are set, try next tag */
 410           if (t2->count == 0)
 411             return 0;
 412           /* t2 is set, t1 loses since it is unset */
 413           return -1;
 414         }
 415       /* if t2 not set, t1 wins since it is set */
 416       else if (t2->count == 0)
 417         return 1;
 418       /* greatest initial value wins */
 419       if ((diff = t1->first - t2->first) != 0)
 420         return diff;
 421       /* least number of times the tag was set, wins */
 422       if ((diff = t2->count - t1->count) != 0)
 423         return diff;
 424       /* if the tags were only set once, they only have initial values */
 425       if (t1->count == 1)
 426         return 0;
 427       /* greatest current value wins */
 428       return t1->value - t2->value;
 429
 430     case TRE_TAG_LEFT_MAXIMIZE:
 431       /* prefer set */
 432       if (t1->count == 0)
 433         {
 434           /* if neither t1 and t2 are set, try next tag */
 435           if (t2->count == 0)
 436             return 0;
 437           /* t2 is set, t1 loses since it is unset */
 438           return -1;
 439         }
 440       /* if t2 not set, t1 wins since it is set */
 441       else if (t2->count == 0)
 442         return 1;
 443       /* least initial value wins */
 444       if ((diff = t2->first - t1->first) != 0)
 445         return diff;
 446       /* least number of times the tag was set, wins */
 447       if ((diff = t2->count - t1->count) != 0)
 448         return diff;
 449       /* if the tags were only set once, they only have initial values */
 450       if (t1->count == 1)
 451         return 0;
 452       /* greatest current value wins */
 453       return t1->value - t2->value;
 454
 455     default:
 456       /* Shouldn't happen: only assert if TRE_DEBUG defined */
 457       assert(0);
 458       break;
 459     }
 460   return 0;
 461 }
 462
 463 #ifdef TRE_DEBUG
 464 #define _MORE_DEBUGGING
 465 #endif /* TRE_DEBUG */
 466
 467 /* Returns 1 if `t1' wins `t2', 0 otherwise. */
 468 inline static int
 469 #ifdef _MORE_DEBUGGING
 470 _tre_tag_order(int num_tags, tre_tag_direction_t *tag_directions,
 471               const tre_tag_t *t1, const tre_tag_t *t2)
 472 #else /* !_MORE_DEBUGGING */
 473 tre_tag_order(int num_tags, tre_tag_direction_t *tag_directions,
 474               const tre_tag_t *t1, const tre_tag_t *t2)
 475 #endif /* !_MORE_DEBUGGING */
 476 {
 477   int i, ret;
 478
 479   for (i = 0; i < num_tags; i++)
 480     {
 481       if ((ret = tre_tag_order_1(i, tag_directions[i], t1, t2)) != 0)
 482         return (ret > 0);
 483     }
 484   /*  assert(0);*/
 485   return 0;
 486 }
 487
 488 #ifdef _MORE_DEBUGGING
 489 inline static int
 490 tre_tag_order(int num_tags, tre_tag_direction_t *tag_directions,
 491               const tre_tag_t *t1, const tre_tag_t *t2)
 492 {
 493   int ret = _tre_tag_order(num_tags, tag_directions, t1, t2);
 494   DPRINT(("tre_tag_order: "));
 495   tre_print_tags(t1, num_tags);
 496   DPRINT((" %s ", ret ? "wins" : "doesn't win"));
 497   tre_print_tags(t2, num_tags);
 498   DPRINT(("\n"));
 499   return ret;
 500 }
 501 #endif /* _MORE_DEBUGGING */
 502
 503 #ifdef __LIBC__
 504 #include <xlocale_private.h>
 505 #else /* !__LIBC__ */
 506 #include <xlocale.h>
 507 #endif /* !__LIBC__ */
 508
 509 int __collate_equiv_value(locale_t loc, const wchar_t *str, size_t len);
 510
 511 inline static int
 512 tre_bracket_match(tre_bracket_match_list_t * __restrict list, tre_cint_t wc,
 513                   const tre_tnfa_t * __restrict tnfa)
 514 {
 515   int match = 0;
 516   int i;
 517   tre_bracket_match_t *b;
 518   tre_cint_t uc, lc;
 519   int we, ue, le, got_equiv = 0;
 520   int icase = ((tnfa->cflags & REG_ICASE) != 0);
 521
 522   DPRINT(("tre_bracket_match: %p, %d, %d\n", list, wc, icase));
 523   if (icase)
 524     {
 525       if (tre_islower_l(wc, tnfa->loc))
 526         {
 527           lc = wc;
 528           uc = tre_toupper_l(wc, tnfa->loc);
 529         }
 530       else if (tre_isupper_l(wc, tnfa->loc))
 531         {
 532           uc = wc;
 533           lc = tre_tolower_l(wc, tnfa->loc);
 534         }
 535       else
 536         {
 537           icase = 0;
 538         }
 539     }
 540   for (i = 0, b = list->bracket_matches; i < list->num_bracket_matches;
 541        i++, b++)
 542     {
 543       switch (b->type)
 544         {
 545         case TRE_BRACKET_MATCH_TYPE_CHAR:
 546           if (icase)
 547             match = (b->value == uc || b->value == lc);
 548           else
 549             match = (b->value == wc);
 550           break;
 551         case TRE_BRACKET_MATCH_TYPE_RANGE_BEGIN:
 552           {
 553             tre_cint_t start = b->value, end;
 554             if (++i >= list->num_bracket_matches ||
 555                 (++b)->type != TRE_BRACKET_MATCH_TYPE_RANGE_END)
 556               {
 557                 DPRINT(("tre_bracket_match: no following range end\n"));
 558                 assert(0);
 559                 goto error;
 560               }
 561             end = b->value;
 562             if (!got_equiv)
 563               {
 564                 if (icase)
 565                   {
 566                     ue = __collate_equiv_value(tnfa->loc, &uc, 1);
 567                     le = __collate_equiv_value(tnfa->loc, &lc, 1);
 568                   }
 569                 else
 570                     we = __collate_equiv_value(tnfa->loc, &wc, 1);
 571                 got_equiv = 1;
 572               }
 573             if (icase)
 574               match = ((start <= ue && ue <= end) ||
 575                       (start <= le && le <= end));
 576             else
 577               match = (start <= we && we <= end);
 578             break;
 579           }
 580         case TRE_BRACKET_MATCH_TYPE_RANGE_END:
 581           DPRINT(("tre_bracket_match: range end without preceeding start\n"));
 582           assert(0);
 583           break;
 584         case TRE_BRACKET_MATCH_TYPE_CLASS:
 585           if (icase)
 586             match = (tre_isctype_l(uc, b->value, tnfa->loc) ||
 587                      tre_isctype_l(lc, b->value, tnfa->loc));
 588           else
 589             match = (tre_isctype_l(wc, b->value, tnfa->loc));
 590           break;
 591         case TRE_BRACKET_MATCH_TYPE_EQUIVALENCE:
 592           if (!got_equiv)
 593             {
 594               if (icase)
 595                 {
 596                   ue = __collate_equiv_value(tnfa->loc, &uc, 1);
 597                   le = __collate_equiv_value(tnfa->loc, &lc, 1);
 598                 }
 599               else
 600                   we = __collate_equiv_value(tnfa->loc, &wc, 1);
 601               got_equiv = 1;
 602             }
 603           if (icase)
 604             match = (b->value == ue || b->value == le);
 605           else
 606             match = (b->value == we);
 607           break;
 608         default:
 609           DPRINT(("tre_bracket_match: unknown type %d\n", b->type));
 610           assert(0);
 611           break;
 612         }
 613         if (match)
 614           break;
 615     }
 616 error:
 617   if (list->flags & TRE_BRACKET_MATCH_FLAG_NEGATE)
 618     match = !match;
 619   return match;
 620 }