rexel.c

   1 /*
   2  * Copyright Neil Brown ©2015-2023 <neil@brown.name>
   3  * May be distributed under terms of GPLv2 - see file:COPYING
   4  *
   5  * rexel - A Regular EXpression Evaluation Library
   6  *    because everyone needs their own regex library
   7  *
   8  * This library supports matching without backtracking by providing
   9  * a single character at a time.  When a match is found, the
  10  * length of that match is reported.
  11  *
  12  * Compiled form of a regex is an array of 16 bit unsigned numbers called
  13  * rexels, or Regular EXpression ELements.
  14  * This involves some cheating as wctype_t (unsigned long int) values
  15  * are stored in 16 bits.
  16  * This array is comprised of a "regexp" section follow by some a "set"
  17  * section.
  18  * The first entry in the regex section is the size of that section (including
  19  * the length).  Adding this size to the start gives the start of the
  20  * "set" section.
  21  *
  22  * The "set" section contains some "sets" each of which contains 1 or
  23  * more subsections followed by a "zero".  Each subsection starts with
  24  * its size.  The first section can have size zero, others cannot (as
  25  * another zero marks the end of the "set").
  26  * The first subsection of a set is a list of "character classes".
  27  * An internal mapping is created from used character classes (like
  28  * "digit" and "lower" etc) to small numbers.  If a set should match a
  29  * given character class, the small number is stored in this subsection
  30  * If a set should *not* match, then the small number is added with the
  31  * msb set.
  32  *
  33  * Subsequent subsections contain a general character-set, each
  34  * subsection for a single unicode plane.  The top six bits of the first
  35  * entry is the plane number, the remaining bits are the size.  After
  36  * this are "size" 16bit chars in sorted order.  The values in even
  37  * slots are in the set, values in odd slots are not.  Value not in any
  38  * slot are treated like the largest value less than it which does have
  39  * a slot.  So iff a search for "largest entry nor larger than" finds an
  40  * even slot, then the target is in the set.
  41  *
  42  * The rexels in the "regexp" section come in 4 groups.
  43  *   0:  15 bit unicode number.  Other unicode numbers require the plane
  44  *           to be given first, described below.
  45  *   100: address of a "regex" subarray.   The match forks at this point,
  46  *        both the next entry and the addressed entry are considered.
  47  *        This limits total size to 8192 entries.
  48  *
  49  *   101: address of a char set.  This 13 bit address is an offset from the
  50  *        start of the "set" section.
  51  *
  52  *   1100: start of a capture group. 4096 possible groups.
  53  *   1101: end of a capture group.
  54  *
  55  *   1110: must match the most recent instance of the capture group.
  56  *
  57  *   1111 0000 000: A UNICODE plane number - 0..16  The next 16 bit
  58  *        number is combined with the plane number to produce a code point
  59  *        to match.  The first half of plane zero does not need this
  60  *        32bit format - those value can be given in 16 bites.
  61  *
  62  *   The last several values have special meanings.
  63  *     0xffe0 - match any char
  64  *     0xffe1 - match any character except any EOL character
  65  *     0xffe2 - match no char - dead end.
  66  *     0xffe3 - report success.
  67  *     0xffe4 - match at start of line
  68  *     0xffe5 - match at end of line
  69  *     0xffe6 - match at start of word
  70  *     0xffe7 - match at end of word
  71  *     0xffe8 - match a word break (start or end)
  72  *     0xffe9 - match any point that isn't a word break.
  73  *     0xffea - match start of document
  74  *     0xffeb - match end of document
  75  *     0xffec - match the location indicated by RXL_POINT
  76  *
  77  *     0xfffb - match any quote: " ' ` - lax searching
  78  *     0xfffc - match 1 or more spaces/tabs/newlines - lax searching.
  79  *     0xfffd - match - or _ - lax searching
  80  *     0xfffe - Subsequent chars (0x..) are matched ignoring case
  81  *     0xffff - Subsequent chars are match case-correct.
  82  *
  83  * When matching, two pairs of extra arrays are allocated and used.
  84  * One pair is 'before', one pair is 'after'.  They swap on each char.
  85  * One contains a threaded linkage among all points in regex subarray
  86  * which are currently matched.  A 'zero' marks the end of the chain.
  87  * The other records the length of the longest match at that point.
  88  * So when a char is matched, the length+1 of the 'before' moves
  89  * to the 'after' position.
  90  *
  91  * A match is *before* processing the index command.
  92  *
  93  * "man 7 regex" described POSIX regular expression and notes some area
  94  * where implementations differ, using (!).  The terminology describes
  95  * a Regular Expression (RE) as:
  96  *  RE -> branch ( '|' branch ) *                # 1 or more branches
  97  *                                               # separated by '|'
  98  *  branch -> piece ( piece ) *                  # 1 or more pieces,
  99  *                                               # concatenated.
 100  *  piece ->  atom ( '*' | '+' | '?' | bound )?  # an atom, possibly
 101  *                                               # followed by repeater
 102  *  bound -> '{' N ( ',' ( N )? )? '}'           # 1 or 2 numbers in braces.
 103  *  atom ->  '(' RE ')' | C | '.' | \??          # dot or char or
 104  *                                               # RE in parentheses.
 105  *
 106  * Responding to each implementation difference:
 107  * - There must be at least one branch in an RE, and all must be non-empty.
 108  * - A branch needs at least one piece.
 109  * - This implementation (currently) only allows a *single* '*','+','?'
 110  *   after an atom.
 111  * - Integers in a bound must be less than 256.
 112  * - The empty string atom '()' is not permitted
 113  * - '\C', where 'C' is a special character: one of ^.[$()|*+?{\  removes any
 114  *    special meaning from that character.  This does not apply inside []
 115  *    as those characters have no special meaning, or a different meaning there.
 116  * - '\C', where 'C' is not in that list is an error except for those used for
 117  *    some special character classes.  Those classes which are not
 118  *    "everything except" are permitted equally inside character sets ([]).
 119  *    The classes are:
 120  *    \d a digit
 121  *    \p a punctuation character
 122  *    \s a spacing character
 123  *    \w a word (alphabetic character)
 124  *    \D \P \S \W  are negation of above.  So non-digit, non-punctuation etc.
 125  *    \A an upper case character
 126  *    \a a lower case character
 127  *
 128  * - A '{' followed by a non-digit is just a '{'
 129  * - Two ranges may *not* share an endpoint.
 130  * - equivalence classes and collating elements are not implemented.
 131  * - No particular limit on the length of an RE is imposed (yet)
 132  *
 133  *
 134  * Other extensions:
 135  * ?:    - a group that will never be captured
 136  * ?|    - don't capture, and within each branch any caputuring uses
 137  *         same numbering
 138  * ?0    - all remainder is literal
 139  * ?nnn:- a group of precisely nnn literal match chars
 140  * ?isLn-isLn:  - flags before any optional '-' are set. Flags after
 141  *         are cleared.
 142  *         i - ignore case
 143  *         L - lax matching for space, hyphen, and quote
 144  *         s - single line, '.' matches newline
 145  *         n - no capture in subgroups either
 146  *
 147  */
 148
 149 #include <stdlib.h>
 150 #include <unistd.h>
 151 #include <wchar.h>
 152 #include <ctype.h>
 153 #include <wctype.h>
 154 #include <memory.h>
 155 #ifdef DEBUG
 156 #include <getopt.h>
 157 #include <fcntl.h>
 158 #include <sys/mman.h>
 159 #include <sys/stat.h>
 160 #endif
 161
 162 #include "safe.h"
 163 #include "misc.h"
 164 #include "rexel.h"
 165
 166 #ifdef DEBUG
 167 #include <stdio.h>
 168 #endif
 169 struct match_state {
 170         unsigned short  *rxl safe;
 171         unsigned short  * safe link[2];
 172         unsigned short  * safe leng[2];
 173         unsigned long   * safe ignorecase;
 174         unsigned short  active;
 175         bool            anchored;
 176         int             match;
 177         int             len;
 178         int             start, total;
 179
 180         /* Backtracking state */
 181         bool            backtrack;
 182         /* 'buf' is an allocated buffer of 'buf_size'.
 183          * There is text up to buf_count which we have been asked
 184          * to match against.  We are currently considering the
 185          * wchar at buf_pos to see if it matches.  If buf_pos == buf_count,
 186          * rxl_advance_bt() will return so that another char can be provided.
 187          */
 188         wint_t          * safe buf;
 189         unsigned short  buf_size;
 190         unsigned short  buf_pos, buf_count;
 191         /* pos in an index in 'rxl' that buf[buf_pos] must be matched against. */
 192         unsigned short  pos;
 193         /* 'record' is an allocated buffer of record_size of
 194          * which record_count entries record details of the current match
 195          * of buf..buf_pos from above.
 196          * We only record fork points that were taken on the path through the
 197          * pattern which achieved the current match.  During matching, we may
 198          * need to rewind to these, and follow forward from that fork.
 199          * During capture extraction, we need to follow those to find
 200          * how the match applied.
 201          */
 202         struct record {
 203                 unsigned short pos;
 204                 unsigned short len;
 205         }               * safe record;
 206         unsigned short  record_count;
 207         unsigned short  record_size;
 208
 209         #ifdef DEBUG
 210         bool            trace;
 211         #endif
 212 };
 213
 214 #define wctype_cells (sizeof(wctype_t) / sizeof(unsigned short))
 215
 216 /* ignorecase is a bit set */
 217 #define BITS_PER_LONG (sizeof(unsigned long) * 8)
 218 static inline int BITSET_SIZE(int bits)
 219 {
 220         return (bits + BITS_PER_LONG - 1) / BITS_PER_LONG;
 221 }
 222 static inline bool test_bit(int bit, const unsigned long *set safe)
 223 {
 224         return !!(set[bit / BITS_PER_LONG] & (1 << (bit % BITS_PER_LONG)));
 225 }
 226
 227 static inline void set_bit(int bit, unsigned long *set safe)
 228 {
 229         set[bit / BITS_PER_LONG] |= (1 << (bit % BITS_PER_LONG));
 230 }
 231
 232 static inline void clear_bit(int bit, unsigned long *set safe)
 233 {
 234         set[bit / BITS_PER_LONG] &= ~(1 << (bit % BITS_PER_LONG));
 235 }
 236
 237 #define NO_LINK         0xFFFF
 238 #define LOOP_CHECK      0xFFFE
 239
 240 /* RExel Commands */
 241 #define REC_ANY         0xFFE0
 242 #define REC_ANY_NONL    0xFFE1
 243 #define REC_NONE        0xFFE2
 244 #define REC_MATCH       0xFFE3
 245
 246 #define REC_SOL         0xFFE4
 247 #define REC_EOL         0xFFE5
 248 #define REC_SOW         0xFFE6
 249 #define REC_EOW         0xFFE7
 250 #define REC_WBRK        0xFFE8
 251 #define REC_NOWBRK      0xFFE9
 252 #define REC_SOD         0xFFEa  /* Start of Document */
 253 #define REC_EOD         0xFFEb  /* End of Document */
 254 #define REC_POINT       0xFFEc
 255
 256 #define REC_LAXQUOT     0xFFFb
 257 #define REC_LAXSPC      0xFFFc
 258 #define REC_LAXDASH     0xFFFd
 259 #define REC_IGNCASE     0xFFFe
 260 #define REC_USECASE     0xFFFf
 261
 262 #define REC_FORK        0x8000
 263 #define REC_FORKLAST    0x8000
 264 #define REC_FORKFIRST   0x9000
 265 #define REC_SET         0xa000
 266 #define REC_CAPTURE     0xc000
 267 #define REC_CAPTURED    0xc800
 268 /* 0xd??? unused */
 269 #define REC_BACKREF     0xe000
 270 #define REC_PLANE       0xf000
 271 #define REC_ISCHAR(x)   (!((x) & 0x8000))
 272 #define REC_ISSPEC(x)   ((x) >= REC_ANY)
 273 #define REC_ISFORK(x)   (((x) & 0xe000) == REC_FORK)
 274 #define REC_ISSET(x)    (((x) & 0xe000) == REC_SET)
 275 #define REC_ISCAPTURE(x) (((x) & 0xf000) == REC_CAPTURE)
 276 #define REC_ISBACKREF(x) (((x) & 0xf000) == REC_BACKREF)
 277 #define REC_BACKREF_MAKE(x) (REC_BACKREF | ((x) & 0x7ff))
 278 #define REC_ADDR(x)     ((x) & 0x0fff)
 279 #define REC_ISFIRST(x)  (!!((x) & (REC_FORKFIRST ^ REC_FORKLAST)))
 280 #define REC_CAPNUM(x)   ((x) & 0x07ff)
 281 #define REC_CAPEND(x)   ((x) & 0x0800)
 282 #define REC_ISPLANE(x)  (((x) & 0xFFE0) == 0xF000)
 283 #define REC_PLANE_OF(x) ((x) & 0x1F)
 284 #define REC_PLANE_MAKE(x, y) ((REC_PLANE_OF(x)<<16) | y)
 285
 286 static inline bool rec_noop(unsigned short cmd)
 287 {
 288         /* These commands don't affect matching directly, they
 289          * are extracted and used outside the core matcher.
 290          */
 291         return cmd == REC_IGNCASE || cmd == REC_USECASE ||
 292                 REC_ISCAPTURE(cmd);
 293 }
 294
 295 static inline bool rec_zerowidth(unsigned short cmd)
 296 {
 297         return ((cmd >= REC_SOL && cmd <= REC_NOWBRK) ||
 298                 rec_noop(cmd));
 299 }
 300
 301 /* First entry contains start of maps, and flags */
 302 #define RXL_PATNLEN(rxl)        ((rxl)[0] & 0x3fff)
 303 #define RXL_SETSTART(rxl)       ((rxl) + RXL_PATNLEN(rxl))
 304
 305 static enum rxl_found rxl_advance_bt(struct match_state *st safe, wint_t ch);
 306 static void bt_link(struct match_state *st safe, int pos, int len);
 307 static int get_capture(struct match_state *s safe, int n, int which,
 308                        char *buf, int *startp);
 309
 310 /*
 311  * The match_state contains several partial matches that lead to "here".
 312  * rxl_advance() examines each of these to determine if they will still match
 313  * after consuming either a character or a position-type flag (SOL, EOL, etc).
 314  * It calls do_link for each case that is still a possible match.
 315  * 'pos' is the position in the regexp that matches the new point in the target.
 316  * 'dest' is the place in the new threaded list to record this match. i.e.
 317  *         the slot that it currently the end of the list.
 318  * 'len' is the length of the match of to this (new) point in the target.
 319  * If there is already a match to this point in the pattern, we just update
 320  * the length and don't relink anything.
 321  *
 322  */
 323 static void do_link(struct match_state *st safe, int pos, int *destp, int len)
 324 {
 325         unsigned short cmd = st->rxl[pos];
 326
 327         while (rec_noop(cmd)) {
 328                 pos += 1;
 329                 cmd = st->rxl[pos];
 330         }
 331         if (cmd == REC_MATCH) {
 332                 if (st->match < len)
 333                         st->match = len;
 334                 /* Don't accept another start point */
 335                 st->anchored = True;
 336         }
 337
 338         if (st->backtrack) {
 339                 bt_link(st, pos, len);
 340                 return;
 341         }
 342
 343         if (!destp)
 344                 return;
 345         if (cmd == REC_NOWBRK) {
 346                 /* NOWBRK is special because it matches a character
 347                  * without consuming it.  We link them at the start
 348                  * of the list so they can be found quickly.
 349                  */
 350                 if (st->link[st->active][pos] == NO_LINK) {
 351                         st->leng[st->active][pos] = len;
 352
 353                         if (st->link[st->active][0] == 0)
 354                                 *destp = pos;
 355                         st->link[st->active][pos] =
 356                                 st->link[st->active][0];
 357                         st->link[st->active][0] = pos;
 358                 } else if (st->leng[st->active][pos] < len)
 359                         st->leng[st->active][pos] = len;
 360         } else if (!REC_ISFORK(cmd)) {
 361                 /* not a FORK, so just link it in. */
 362                 if (st->link[st->active][pos] == NO_LINK) {
 363                         st->leng[st->active][pos] = len;
 364
 365                         st->link[st->active][*destp] = pos;
 366                         st->link[st->active][pos] = 0;
 367                         *destp = pos;
 368                 } else if (st->leng[st->active][pos] < len)
 369                         st->leng[st->active][pos] = len;
 370         } else if (st->link[st->active][pos] == NO_LINK ||
 371                    st->leng[st->active][pos] < len) {
 372                 st->link[st->active][pos] = LOOP_CHECK;
 373                 st->leng[st->active][pos] = len;
 374                 do_link(st, REC_ADDR(cmd), destp, len);
 375                 do_link(st, pos+1, destp, len);
 376         }
 377 }
 378
 379 static int set_match(struct match_state *st safe, unsigned short addr,
 380                      wchar_t ch, bool ic)
 381 {
 382         unsigned short *set safe = RXL_SETSTART(st->rxl) + addr;
 383         wchar_t uch = ch, lch = ch;
 384         unsigned short len;
 385         bool invert = False;
 386
 387         if (ic) {
 388                 /* As Unicode has 3 cases, can we be sure that everything
 389                  * has a 'lower' to map to?  Surely everything has at least
 390                  * and upper or a lower...
 391                  */
 392                 uch = towupper(ch);
 393                 lch = towlower(ch);
 394         }
 395         /* First there is an 'invert' flag and possibly some char classes */
 396         len = *set++;
 397         invert = !!(len & 0x8000);
 398         if (len) {
 399                 len &= 0x7fff;
 400                 for ( ; len; set += wctype_cells) {
 401                         wctype_t class;
 402                         len -= wctype_cells;
 403                         memcpy(&class, set, sizeof(wctype_t));
 404                         if (iswctype(uch, class) ||
 405                             (uch != lch && iswctype(lch, class)))
 406                                 return !invert;
 407                 }
 408         }
 409         /* now there might be some sets.  Each set starts with a size with
 410          * top 5 bytes indicating top bytes of unicode planes, and bottom
 411          * 11 bytes size of table
 412          */
 413         while ((len = *set++) != 0) {
 414                 int high = (len & 0xF800) << 5;
 415                 /* Both upper and lower case have been placed in set,
 416                  * so only need to search for one of them
 417                  */
 418                 unsigned short target;
 419                 int lo, hi;
 420
 421                 len &= 0x7ff;
 422                 if ((uch & 0x1f0000) == high)
 423                         target = uch & 0xffff;
 424                 else if ((lch & 0x1f0000) == high)
 425                         target = lch & 0xffff;
 426                 else {
 427                         set += len;
 428                         continue;
 429                 }
 430                 /* Binary search to find first entry that is greater
 431                  * than target.
 432                  */
 433                 lo = 0; /* Invar: No entry before lo is greater than target */
 434                 hi = len; /* Invar: Every entry at or after hi is greater
 435                            * than target */
 436 #ifdef DEBUG
 437                 /* Sanity check - array must be sorted */
 438                 for (lo = 1; lo < len; lo++)
 439                         if (set[lo-1] >= set[lo]) {
 440                                 printf("Set %d, subset %d not ordered at %u\n",
 441                                        addr, set - RXL_SETSTART(st->rxl) - addr,
 442                                        lo);
 443                                 exit(1);
 444                         }
 445                 lo = 0;
 446 #endif
 447
 448                 while (lo < hi) {
 449                         int mid = (lo + hi) / 2;
 450                         if (set[mid] > target)
 451                                 hi = mid;
 452                         else
 453                                 lo = mid + 1;
 454                 }
 455                 /* set[lo] == set[hi] = first entry greater than target.
 456                  * If 'lo' is even, there was no match.  If 'lo' is odd,
 457                  * there was.
 458                  */
 459                 if (lo & 1)
 460                         return !invert;
 461                 set += len;
 462         }
 463         return invert;
 464 }
 465
 466 /*
 467  * Advance the match state to process 'ch' or a flag.
 468  * flag indicates start/end of word/line.
 469  * Returns -2 if there is no possibility of a match including this ch/flag
 470  * Returns -1 if part of the pattern has matched, and more input is needed.
 471  * Returns >=0 if a match has been found.  The return value is the number
 472  *  of characters (not flags) in the match.
 473  * When a >=0 return is given, it might still be useful to keep calling
 474  * rxl_advance if a maximal match is wanted.
 475  * If the match must be anchor to the first character, this must have been
 476  * advised to rxl_prepare.  The caller should keep calling until no chars are
 477  * left, or -2 is returned (no match), or >=0 is returned.  In the latter case
 478  * the call might keep calling to see if a longer match is possible.  Until -2
 479  * is seen, a longer match is still possible.
 480  */
 481
 482 static int advance_one(struct match_state *st safe, int i,
 483                        wint_t ch, int flag,
 484                        int len, int *eolp)
 485 {
 486         unsigned int cmd = st->rxl[i];
 487         wint_t lch = ch, uch = ch;
 488         bool ic = test_bit(i, st->ignorecase);
 489         int advance = 0;
 490         int inc = 1;
 491
 492         if (ic) {
 493                 uch = toupper(ch);
 494                 lch = tolower(ch);
 495         }
 496
 497         if (REC_ISSPEC(cmd)) {
 498                 switch(cmd) {
 499                 case REC_ANY:
 500                         advance = 1;
 501                         if (flag)
 502                                 advance = 0;
 503                         break;
 504                 case REC_ANY_NONL:
 505                         advance = 1;
 506                         if (ch == '\n' || ch == '\r' || ch == '\f')
 507                                 advance = -1;
 508                         if (flag)
 509                                 advance = 0;
 510                         break;
 511                 case REC_MATCH:
 512                         /* cannot match more chars here */
 513                         if (flag)
 514                                 advance = 0;
 515                         else
 516                                 advance = -1;
 517                         break;
 518                 case REC_NONE:
 519                         advance = -1;
 520                         break;
 521                 case REC_SOL:
 522                         if (flag & RXL_SOL)
 523                                 advance = 1;
 524                         else if (!flag)
 525                                 advance = -1;
 526                         else
 527                                 advance = 0;
 528                         break;
 529                 case REC_EOL:
 530                         if (flag & RXL_EOL)
 531                                 advance = 1;
 532                         else if (!flag)
 533                                 advance = -1;
 534                         else
 535                                 advance = 0;
 536                         break;
 537                 case REC_SOD:
 538                         if (flag & RXL_SOD)
 539                                 advance = 1;
 540                         else if (!flag)
 541                                 advance = -1;
 542                         else
 543                                 advance = 0;
 544                         break;
 545                 case REC_EOD:
 546                         if (flag & RXL_EOD)
 547                                 advance = 1;
 548                         else if (!flag)
 549                                 advance = -1;
 550                         else
 551                                 advance = 0;
 552                         break;
 553                 case REC_POINT:
 554                         if (flag & RXL_POINT)
 555                                 advance = 1;
 556                         else if (!flag)
 557                                 advance = -1;
 558                         else
 559                                 advance = 0;
 560                         break;
 561                 case REC_SOW:
 562                         if (flag & RXL_SOW)
 563                                 advance = 1;
 564                         else if (flag & RXL_NOWBRK || !flag)
 565                                 advance = -1;
 566                         else
 567                                 advance = 0;
 568                         break;
 569                 case REC_EOW:
 570                         if (flag & RXL_EOW)
 571                                 advance = 1;
 572                         else if (flag & RXL_NOWBRK || !flag)
 573                                 advance = -1;
 574                         else
 575                                 advance = 0;
 576                         break;
 577                 case REC_WBRK:
 578                         if (flag & (RXL_SOW | RXL_EOW))
 579                                 advance = 1;
 580                         else if (flag & RXL_NOWBRK || !flag)
 581                                 advance = -1;
 582                         else
 583                                 advance = 0;
 584                         break;
 585                 case REC_NOWBRK:
 586                         if (flag & (RXL_SOW | RXL_EOW))
 587                                 advance = -1;
 588                         else if (flag & RXL_NOWBRK)
 589                                 advance = 1;
 590                         else
 591                                 advance = 0;
 592                         break;
 593                 case REC_LAXSPC:
 594                         if (strchr(" \t\r\n\f", ch) != NULL)
 595                                 advance = 1;
 596                         else
 597                                 advance = -1;
 598                         if (flag)
 599                                 advance = 0;
 600                         break;
 601                 case REC_LAXQUOT:
 602                         if (strchr("'`\"", ch) != NULL)
 603                                 advance = 1;
 604                         else
 605                                 advance = -1;
 606                         if (flag)
 607                                 advance = 0;
 608                         break;
 609                 case REC_LAXDASH:
 610                         if (strchr("-_.", ch) != NULL)
 611                                 advance = 1;
 612                         else
 613                                 advance = -1;
 614                         if (flag)
 615                                 advance = 0;
 616                         break;
 617                 }
 618         } else if (flag) {
 619                 /* expecting a char, so ignore position info */
 620                 advance = 0;
 621         } else if (REC_ISCHAR(cmd)) {
 622                 if (cmd == ch ||
 623                     (ic && (cmd == uch || cmd == lch)))
 624                         advance = 1;
 625                 else
 626                         advance = -1;
 627         } else if (REC_ISPLANE(cmd) && i+1 < RXL_PATNLEN(st->rxl)) {
 628                 cmd = REC_PLANE_MAKE(cmd, st->rxl[i+1]);
 629                 inc = 2;
 630                 if (cmd == ch ||
 631                     (ic && (cmd == uch || cmd == lch)))
 632                         advance = 1;
 633                 else
 634                         advance = -1;
 635         } else if (REC_ISSET(cmd)) {
 636                 if (set_match(st, REC_ADDR(cmd), ch, ic))
 637                         advance = 1;
 638                 else
 639                         advance = -1;
 640         } else if (REC_ISBACKREF(cmd)) {
 641                 /* Backref not supported */
 642                 advance = -2;
 643         } else
 644                 /* Nothing else is possible here */
 645                 /* abort(); */
 646                 advance = -2;
 647         if (advance < 0)
 648                 /* no match on this path */
 649                 ;
 650         else if (advance == 0)
 651                 /* Nothing conclusive here */
 652                 do_link(st, i, eolp, len);
 653         else
 654                 /* Need to advance and link the new address in.  However
 655                  * if there is a fork, we might need to link multiple
 656                  * addresses in.  Best use recursion.
 657                  */
 658                 do_link(st, i+inc, eolp, len + (ch != 0));
 659         return advance;
 660 }
 661
 662 enum rxl_found rxl_advance(struct match_state *st safe, wint_t ch)
 663 {
 664         int active;
 665         int next;
 666         int eol;
 667         unsigned short i;
 668         wint_t flag = ch & ~(0x1fffff);
 669         enum rxl_found ret = RXL_NOMATCH;
 670
 671         if (st->backtrack)
 672                 return rxl_advance_bt(st, ch);
 673
 674         ch &= 0x1fffff;
 675
 676         if (flag && ((flag & (flag-1)) || ch)) {
 677                 int f;
 678                 enum rxl_found r;
 679                 /* Need to handle flags separately */
 680                 for (f = RXL_SOD ; f && f <= RXL_LAST; f <<= 1) {
 681                         if (!(flag & f))
 682                                 continue;
 683                         r = rxl_advance(st, f);
 684                         if (r > ret)
 685                                 ret = r;
 686                 }
 687                 flag = 0;
 688                 if (!ch)
 689                         return ret;
 690         }
 691         if (flag == RXL_ANCHOR) {
 692                 st->anchored = True;
 693                 return ret;
 694         }
 695
 696         active = st->active;
 697         next = 1-active;
 698
 699         if (flag == RXL_NOWBRK &&
 700             (st->link[active][0] == NO_LINK ||
 701              st->rxl[st->link[active][0]] != REC_NOWBRK))
 702                 /* Reporting not-a-word-boundary, but no-one cares,
 703                  * so just return.
 704                  */
 705                 return st->match >= 0 ? RXL_MATCH_FLAG :
 706                         st->len >= 0 ? RXL_CONTINUE : RXL_NOMATCH;
 707
 708         if (!flag)
 709                 st->total += 1;
 710
 711         if (!st->anchored) {
 712                 /* We haven't found a match yet and search is not anchored,
 713                  * so possibly start a search here.
 714                  */
 715                 eol = 0;
 716                 while (st->link[active][eol])
 717                         eol = st->link[active][eol];
 718                 /* Found the end of the list. */
 719                 do_link(st, 1, &eol, 0);
 720         }
 721         st->match = -1;
 722         eol = 0;
 723         st->active = next;
 724 #ifdef DEBUG
 725         if (st->trace) {
 726                 /* Trace shows current length at each state. FORK points
 727                  * are not state points
 728                  * At each point we print the Char or Set number, then the
 729                  * length of a match to there - on the next line.
 730                  * Allow 4 chars per column
 731                  */
 732                 char t[5];
 733                 unsigned short cnt;
 734                 int len = RXL_PATNLEN(st->rxl);
 735
 736                 for (i = 1; i < len; i++)
 737                         if (!REC_ISFORK(st->rxl[i])) {
 738                                 unsigned short cmd = st->rxl[i];
 739                                 if (REC_ISCHAR(cmd)) {
 740                                         if (cmd > ' ' && cmd < 0x7f)
 741                                                 printf("'%c' ", cmd);
 742                                         else
 743                                                 printf("x%3x", cmd);
 744                                 } else if (REC_ISSET(cmd)) {
 745                                         printf("S%-3d", REC_ADDR(cmd));
 746                                 } else if (REC_ISBACKREF(cmd)) {
 747                                         printf("B%-3d", REC_CAPNUM(cmd));
 748                                 } else if (REC_ISCAPTURE(cmd)) {
 749                                         if (REC_CAPEND(cmd))
 750                                                 printf("%3d)", REC_CAPNUM(cmd));
 751                                         else
 752                                                 printf("(%-3d", REC_CAPNUM(cmd));
 753                                 } else switch(cmd) {
 754                                         case REC_ANY: printf(" .  "); break;
 755                                         case REC_ANY_NONL: printf(" .? "); break;
 756                                         case REC_NONE:printf("##  "); break;
 757                                         case REC_SOL: printf(" ^  "); break;
 758                                         case REC_EOL: printf(" $  "); break;
 759                                         case REC_SOW: printf("\\<  "); break;
 760                                         case REC_EOW: printf("\\>  "); break;
 761                                         case REC_SOD: printf("\\`  "); break;
 762                                         case REC_EOD: printf("\\'  "); break;
 763                                         case REC_POINT: printf("\\=  "); break;
 764                                         case REC_WBRK: printf("\\b  "); break;
 765                                         case REC_NOWBRK: printf("\\B "); break;
 766                                         case REC_MATCH:printf("!!! "); break;
 767                                         case REC_LAXSPC: printf("x20!"); break;
 768                                         case REC_LAXQUOT: printf("'!  "); break;
 769                                         case REC_LAXDASH: printf("-!  "); break;
 770                                         case REC_IGNCASE: printf("?i:"); break;
 771                                         case REC_USECASE: printf("?c:"); break;
 772                                         default: printf("!%04x", cmd);
 773                                         }
 774                         }
 775                 printf("\n");
 776                 for (i = 1 ; i < len; i++)
 777                         if (!REC_ISFORK(st->rxl[i])) {
 778                                 if (st->link[active][i] == NO_LINK)
 779                                         printf("--  ");
 780                                 else
 781                                         printf("%2d  ", st->leng[active][i]);
 782                         }
 783                 if (flag) {
 784                         printf("Flag:");
 785                         if (flag & RXL_SOD) printf(" SOD");
 786                         if (flag & RXL_SOL) printf(" SOL");
 787                         if (flag & RXL_EOL) printf(" EOL");
 788                         if (flag & RXL_EOD) printf(" EOD");
 789                         if (flag & RXL_SOW) printf(" SOW");
 790                         if (flag & RXL_EOW) printf(" EOW");
 791                         if (flag & RXL_NOWBRK) printf(" NOWBRK");
 792                         if (flag & RXL_POINT) printf(" POINT");
 793                 } else
 794                         printf("Match %s(%x)",
 795                                ch < ' ' ? "?" : put_utf8(t, ch) , ch);
 796
 797                 /* Now check the linkage is correct.  The chain should lead
 798                  * to 0 without seeing any 'NO_LINK' or any ISFORK, and
 799                  * the number of NO_LINK plus number on chain should make len
 800                  */
 801                 cnt = 0;
 802                 i = 0;
 803                 do {
 804                         if (st->link[active][i] == NO_LINK)
 805                                 abort();
 806                         if (i && REC_ISFORK(st->rxl[i]))
 807                                 abort();
 808                         cnt += 1;
 809                         i = st->link[active][i];
 810                         if (i >= len)
 811                                 abort();
 812                 } while (i);
 813                 for (i = 0; i < len; i++)
 814                         if (st->link[active][i] == NO_LINK ||
 815                             st->link[active][i] == LOOP_CHECK)
 816                                 cnt += 1;
 817                 if (cnt != len)
 818                         abort();
 819         }
 820 #endif /* DEBUG */
 821         /* Firstly, clear out next lists */
 822         /* This works because NO_LINK is 0xffff */
 823         memset(st->link[next], 0xff, RXL_PATNLEN(st->rxl) * 2);
 824         memset(st->leng[next], 0, RXL_PATNLEN(st->rxl) * 2);
 825         st->link[next][0] = 0;
 826
 827         /* Now advance each current match */
 828         for (i = st->link[active][0]; i; i = st->link[active][i]) {
 829                 int len = st->leng[active][i];
 830
 831                 advance_one(st, i, ch, flag, len, &eol);
 832         }
 833         st->link[next][eol] = 0;
 834         if (st->match > st->len) {
 835                 st->len = st->match;
 836                 st->start = st->total - st->len;
 837         }
 838         #ifdef DEBUG
 839         if (st->trace) {
 840                 if (st->match >= 0 || eol != 0)
 841                         printf(" ... -> %d\n", st->match);
 842                 else
 843                         printf(" ... -> NOMATCH\n");
 844         }
 845         #endif
 846         /* 'ret' is the result of an flags, or RXL_NOMATCH. */
 847         if (ret >= RXL_MATCH && !flag && st->match >= 0)
 848                 return RXL_MATCH;
 849         if (ret >= RXL_MATCH_FLAG || (st->match >= 0 && flag))
 850                 return RXL_MATCH_FLAG;
 851         if (ret >= RXL_MATCH || st->match >= 0)
 852                 return RXL_MATCH;
 853         if (eol == 0 && st->match < 0 && st->anchored) {
 854                 /* No chance of finding (another) match now */
 855                 return RXL_DONE;
 856         }
 857         if (st->len >= 0)
 858                 return RXL_CONTINUE;
 859         return RXL_NOMATCH;
 860 }
 861
 862 int rxl_info(struct match_state *st safe, int *lenp safe, int *totalp,
 863               int *startp, int *since_startp)
 864 {
 865         *lenp = st->len;
 866         if (totalp)
 867                 *totalp = st->total;
 868         if (startp) {
 869                 if (st->len < 0)
 870                         *startp = -1;
 871                 else
 872                         *startp = st->start;
 873         }
 874         if (since_startp) {
 875                 if (st->len < 0)
 876                         *since_startp = -1;
 877                 else
 878                         *since_startp = st->total - st->start;
 879         }
 880         /* Return 'true' if there might be something here and
 881          * we cannot safely skip forward
 882          */
 883         return st->anchored ||
 884                 (st->link[st->active] && st->link[st->active][0] != 0);
 885 }
 886
 887 #define RESIZE(buf)                                                     \
 888         do {                                                            \
 889                 if ((buf##_size) <= (buf##_count+1)) {                  \
 890                         if ((buf##_size) < 8)                           \
 891                                 (buf##_size) = 8;                       \
 892                         (buf##_size) *= 2;                              \
 893                         (buf) = realloc(buf, (buf##_size) * sizeof((buf)[0]));\
 894                 }                                                       \
 895         } while(0);
 896
 897 static void bt_link(struct match_state *st safe, int pos, int len)
 898 {
 899         unsigned short cmd = st->rxl[pos];
 900
 901         if (!REC_ISFORK(cmd)) {
 902                 st->pos = pos;
 903                 return;
 904         }
 905
 906         RESIZE(st->record);
 907         st->record[st->record_count].pos = pos;
 908         st->record[st->record_count].len = len;
 909         st->record_count += 1;
 910         if (REC_ISFIRST(cmd))
 911                 /* priority fork - follow the fork */
 912                 do_link(st, REC_ADDR(cmd), NULL, len);
 913         else
 914                 /* just continue for now, fork later */
 915                 do_link(st, pos + 1, NULL, len);
 916 }
 917
 918 static enum rxl_found rxl_advance_bt(struct match_state *st safe, wint_t ch)
 919 {
 920         /* This is a back-tracking version of rxl_advance().  If the new
 921          * ch/flag matches, we store it and return.  If it doesn't, we
 922          * backtrack and retry another path until we run out of all
 923          * paths, or find a path where more input is needed.
 924          */
 925
 926         if (st->anchored && st->record_count == 0 && st->pos == 0)
 927                 return RXL_DONE;
 928
 929         if (st->len >= 0)
 930                 return RXL_DONE;
 931
 932         RESIZE(st->buf);
 933         st->buf[st->buf_count++] = ch;
 934         st->total += 1;
 935
 936         st->match = -1;
 937         do {
 938                 wint_t flags;
 939                 int f = 1;;
 940                 ch = st->buf[st->buf_pos++];
 941                 flags = ch & ~0x1FFFFF;
 942                 ch &= 0x1FFFFF;
 943
 944                 for (f = RXL_SOD ; f && f <= RXL_EOD*2; f <<= 1) {
 945                         int i = st->pos;
 946                         int r;
 947
 948                         #ifdef DEBUG
 949                         if (!st->trace)
 950                                 ;
 951                         else if (f == RXL_EOD*2) {
 952                                 char t[5];
 953                                 printf("%d: Match %s(%x)", i,
 954                                        ch < ' ' ? "?" : put_utf8(t, ch) , ch);
 955                         } else if (f & flags){
 956                                 printf("%d: Flag:", i);
 957                                 if (f & RXL_SOD) printf(" SOD");
 958                                 if (f & RXL_EOD) printf(" EOD");
 959                                 if (f & RXL_SOL) printf(" SOL");
 960                                 if (f & RXL_EOL) printf(" EOL");
 961                                 if (f & RXL_SOW) printf(" SOW");
 962                                 if (f & RXL_EOW) printf(" EOW");
 963                                 if (f & RXL_NOWBRK) printf(" NOWBRK");
 964                                 if (f & RXL_POINT) printf(" POINT");
 965                         }
 966                         #endif
 967
 968                         if (f == RXL_EOD*2 && ch)
 969                                 r = advance_one(st, i, ch, 0,
 970                                                 st->buf_pos - 1, NULL);
 971                         else if (f == RXL_EOD*2)
 972                                 r = -1;
 973                         else if (f & flags)
 974                                 r = advance_one(st, i, 0, f,
 975                                                 st->buf_pos - 1, NULL);
 976                         else
 977                                 continue;
 978
 979                         if (r == -2) {
 980                                 /* REC_BACKREF cannot be handled generically
 981                                  * by advance_one.  We need to find the
 982                                  * referenced string and match - or ask for more.
 983                                  */
 984                                 int prevpos;
 985                                 int start;
 986                                 int len = get_capture(st, REC_CAPNUM(st->rxl[i]), 0,
 987                                                       NULL, &start);
 988                                 st->buf_pos -= 1;
 989                                 prevpos = st->buf_pos;
 990                                 while (len > 0 && st->buf_pos < st->buf_count) {
 991                                         ch = st->buf[st->buf_pos++] & 0x1FFFFF;
 992                                         if ((st->buf[start] & 0x1FFFFF) == ch) {
 993                                                 start += 1;
 994                                                 len -= 1;
 995                                         } else {
 996                                                 /* Failure to match */
 997                                                 len = -1;
 998                                         }
 999                                 }
1000                                 if (len > 0) {
1001                                         /* Need more input */
1002                                         st->buf_pos = prevpos;
1003                                         return RXL_CONTINUE;
1004                                 }
1005                                 if (len == 0) {
1006                                         /* Successful match */
1007                                         do_link(st, i+1, NULL, st->buf_pos);
1008                                         r = 1;
1009                                 }
1010                         }
1011
1012                         if (r >= 0) {
1013                                 /* st->pos has been advanced if needed */
1014                                 if (st->match > st->len) {
1015                                         st->len = st->match;
1016                                         st->start = st->total - st->buf_count;
1017                                 }
1018                                 #ifdef DEBUG
1019                                 if (st->trace)
1020                                         printf(" -- OK(%d %d %d/%d)\n", r,
1021                                                st->buf_pos,
1022                                                st->start, st->len);
1023                                 #endif
1024                                 if (st->len >= 0)
1025                                         return RXL_MATCH;
1026                                 continue;
1027                         }
1028
1029                         /* match failed - backtrack */
1030                         if (st->record_count > 0) {
1031                                 st->record_count -= 1;
1032                                 st->pos = st->record[st->record_count].pos;
1033                                 st->buf_pos = st->record[st->record_count].len;
1034                                 #ifdef DEBUG
1035                                 if (st->trace)
1036                                         printf(" -- NAK backtrack to %d/%d\n",
1037                                                st->pos, st->buf_pos);
1038                                 #endif
1039                                 if (REC_ISFIRST(st->rxl[st->pos]))
1040                                         /* priority jump, just step forward now */
1041                                         do_link(st, st->pos+1, NULL, st->buf_pos);
1042                                 else
1043                                         /* delayed jump, take it now */
1044                                         do_link(st, REC_ADDR(st->rxl[st->pos]),
1045                                                 NULL, st->buf_pos);
1046                         } else {
1047                                 /* cannot backtrack, so skip first char unless anchored */
1048                                 #ifdef DEBUG
1049                                 if (st->trace)
1050                                         printf(" -- NAK - %s\n",
1051                                                st->anchored?"abort":"fail");
1052                                 #endif
1053                                 if (st->anchored) {
1054                                         st->pos = 0;
1055                                         return RXL_DONE;
1056                                 }
1057                                 st->buf_count -= 1;
1058                                 memmove(st->buf, st->buf+1,
1059                                         sizeof(st->buf[0]) * st->buf_count);
1060                                 st->buf_pos = 0;
1061                                 do_link(st, 1, NULL, st->buf_pos);
1062                         }
1063                         break;
1064                 }
1065         } while (st->buf_pos < st->buf_count);
1066
1067         if (st->len < 0)
1068                 return RXL_NOMATCH;
1069         else
1070                 return RXL_CONTINUE;
1071 }
1072
1073 enum modifier {
1074         IgnoreCase      = 1,
1075         LaxMatch        = 2,
1076         SingleLine      = 4,
1077         DoCapture       = 8,
1078         CapturePerBranch=16,
1079 };
1080
1081 struct parse_state {
1082         const char      *patn safe;
1083         unsigned short  *rxl;
1084         int             next;
1085         unsigned short  *sets;
1086         int             set;    /* Next offset to store a set */
1087         enum modifier mod;      /* Multiple 'or'ed together */
1088         int             capture;
1089
1090         /* Details of set currently being parsed */
1091         int             len;
1092 };
1093
1094 static void add_cmd(struct parse_state *st safe, unsigned short cmd)
1095 {
1096         if (st->rxl)
1097                 st->rxl[st->next] = cmd;
1098         st->next += 1;
1099 }
1100
1101 static void relocate(struct parse_state *st safe, unsigned short start, int len)
1102 {
1103         int i;
1104         if (!st->rxl) {
1105                 st->next += len;
1106                 return;
1107         }
1108         for (i = st->next-1; i >= start; i-=1) {
1109                 unsigned short cmd = st->rxl[i];
1110                 if (REC_ISFORK(cmd) &&
1111                     REC_ADDR(cmd) >= start)
1112                         cmd += len;
1113                 st->rxl[i+len] = cmd;
1114         }
1115         st->next += len;
1116 }
1117
1118 static wint_t cvt_hex(const char *s safe, int len)
1119 {
1120         long rv = 0;
1121         while (len) {
1122                 if (!*s || !isxdigit(*s))
1123                         return WERR;
1124                 rv *= 16;
1125                 if (*s <= '9')
1126                         rv += *s - '0';
1127                 else if (*s <= 'F')
1128                         rv += *s - 'A' + 10;
1129                 else if (*s <= 'f')
1130                         rv += *s - 'a' + 10;
1131                 else
1132                         return WERR;
1133                 s++;
1134                 len--;
1135         }
1136         return rv;
1137 }
1138
1139 static wint_t cvt_oct(const char **sp safe, int maxlen)
1140 {
1141         const char *s = *sp;
1142         long rv = 0;
1143         while (maxlen) {
1144                 if (!s || !*s || !isdigit(*s) || *s == '8' || *s == '9')
1145                         break;
1146                 rv *= 8;
1147                 rv += *s - '0';
1148                 s++;
1149                 maxlen--;
1150         }
1151         *sp = s;
1152         return rv;
1153 }
1154
1155 static bool _add_range(struct parse_state *st safe, wchar_t start, wchar_t end,
1156                         int plane, int *planes safe, int *newplane safe)
1157 {
1158         int p;
1159         int lo, hi;
1160         int len;
1161         unsigned short *set;
1162         if (end < start)
1163                 return False;
1164         if (!st->sets) {
1165                 /* guess 2 entries for each plane, plus 1
1166                  * if we add a plane.  Each plane needs an extra slot
1167                  * if the set is inverted.
1168                  */
1169                 for (p = (start & 0x1F0000)>>16;
1170                      p <= (end & 0x1F0000)>>16 ;
1171                      p++) {
1172                         if (!((*planes) & (1 << p))) {
1173                                 *planes |= 1 << p;
1174                                 st->len += 1;
1175                         }
1176                         st->len += 2;
1177                 }
1178                 /* All planes handled, so set *newplane beyond
1179                  * the last.
1180                  */
1181                 *newplane = 0x11 << 16;
1182                 return True;
1183         }
1184         /* OK, for real this time, need to build up set 'plane' */
1185         if (start >= ((plane+1) << 16)) {
1186                 /* Nothing to do for this plane, move to 'start' */
1187                 *newplane = start >> 16;
1188                 return True;
1189         }
1190         if (end < (plane << 16)) {
1191                 /* nothing more to do */
1192                 *newplane = 0x11 << 16;
1193                 return True;
1194         }
1195         /* Contract range to this plane */
1196         if (start < (plane << 16))
1197                 start = plane << 16;
1198         if (end >= ((plane+1) << 16))
1199                 end = ((plane+1) << 16) - 1;
1200         if (!((*planes) & (1 << plane))) {
1201                 st->sets[st->set] = (plane << 11);
1202                 *planes |= 1 << plane;
1203         }
1204         /* now clip to 16bit */
1205         start &= 0xFFFF;
1206         end &= 0xFFFF;
1207
1208         /* Now insert range into the list.
1209          * 1/ Perform search for 'start'.
1210          * 2/ If at 'even' offset then not present yet.
1211          *   2a/ if 'start-1' is present, update that to end
1212          *   2b/ if next is <= end, update that to start
1213          *   2c/ otherwise shift up and insert range - done.
1214          * 3/ if at 'odd' offset then is in already
1215          *   3a/ if next is beyond 'end', then done
1216          *   3b/ otherwise update next to end
1217          * 4/ while ranges over-lap, delete two endpoints
1218          *    and shift down.
1219          */
1220
1221         len = st->len;
1222         set = st->sets + st->set + 1;
1223         /* Binary search to find first entry that is greater
1224          * than target.
1225          */
1226         lo = 0; /* Invar: No entry before lo is greater than target */
1227         hi = len; /* Invar: Every entry at or after hi is greater than target */
1228         while (lo < hi) {
1229                 int mid = (lo + hi) / 2;
1230                 if (set[mid] > start)
1231                         hi = mid;
1232                 else
1233                         lo = mid + 1;
1234         }
1235         /* set[lo] == set[hi] = first entry greater than target.
1236          * If 'lo' is even, there was no match.  If 'lo' is odd,
1237          * there was.
1238          */
1239         if ((lo & 1) == 0) {
1240                 /* Not yet present.*/
1241                 if (lo > 0 && set[lo-1] == start) {
1242                         /* Extend the earlier range */
1243                         lo -= 1;
1244                         if (end == 0xffff)
1245                                 len = lo;
1246                         else
1247                                 set[lo] = end+1;
1248                 } else if (lo < len && set[lo] <= end+1)
1249                         set[lo] = start;
1250                 else {
1251                         /* need to insert */
1252                         memmove(set+lo+2, set+lo, sizeof(set[lo])*(len-lo));
1253                         set[lo] = start;
1254                         if (end == 0xffff)
1255                                 len = lo+1;
1256                         else {
1257                                 set[lo+1] = end+1;
1258                                 len += 2;
1259                         }
1260                 }
1261         } else {
1262                 /* Already present, lo is end of a range, or beyond len */
1263                 if (lo == len || set[lo] > end)
1264                         /* nothing to do */;
1265                 else
1266                         set[lo] = end+1;
1267         }
1268         lo |= 1;
1269         /* Lo now points to the end of a range. If it overlaps the next,
1270          * merge the ranges.
1271          */
1272         while (lo+1 < len && set[lo] >= set[lo+1]) {
1273                 /* Need to merge these ranges */
1274                 if (lo+2 < len){
1275                         if (set[lo] > set[lo+2])
1276                                 set[lo+2] = set[lo];
1277                         memmove(set+lo, set+lo+2,
1278                                 sizeof(set[lo])*(len - (lo+2)));
1279                 }
1280                 len -= 2;
1281         }
1282         st->len = len;
1283         return True;
1284 }
1285
1286 static bool add_range(struct parse_state *st safe, wchar_t start, wchar_t end,
1287                       int plane, int *planes safe, int *newplane safe)
1288 {
1289         if (!(st->mod & IgnoreCase) ||
1290             !iswalpha(start) || !iswalpha(end))
1291                 return _add_range(st, start, end, plane, planes, newplane);
1292         if (!_add_range(st, towlower(start), towlower(end),
1293                         plane, planes, newplane))
1294                 return False;
1295         return _add_range(st, towupper(start), towupper(end),
1296                            plane, planes, newplane);
1297 }
1298
1299 static void add_class(struct parse_state *st safe, int plane, wctype_t cls)
1300 {
1301         if (plane >= 0)
1302                 /* already handled. */
1303                 return;
1304
1305         if (st->sets)
1306                 memcpy(&st->sets[st->set + st->len + 1], &cls,
1307                        sizeof(wctype_t));
1308         st->len += wctype_cells;
1309 }
1310
1311 static bool is_set_element(const char *p safe)
1312 {
1313         int i;
1314
1315         if (p[0] != '.' && p[0] != '=' && p[0] != ':')
1316                 return False;
1317         for (i = 1; p[i]; i++)
1318                 if (p[i] == ']') {
1319                         if (p[i-1] == p[1] && i > 1)
1320                                 return True;
1321                         else
1322                                 return False;
1323                 }
1324         return False;
1325 }
1326
1327 static int do_parse_set(struct parse_state *st safe, int plane)
1328 {
1329         const char *p safe = st->patn;
1330         wint_t ch;
1331         int newplane = 0xFFFFFF;
1332         int planes = 0;
1333         int invert;
1334         /* first characters are special... */
1335         invert = 0;
1336         st->len = 0;
1337         if (*p == '^') {
1338                 invert = 1;
1339                 p += 1;
1340         }
1341         do {
1342                 ch = get_utf8(&p, NULL);
1343                 if (ch == '\\' && p[0] && strchr("0xuUnrft", p[0]) != NULL) {
1344                         switch (*p++) {
1345                         case '0': ch = cvt_oct(&p, 3);  break;
1346                         case 'x': ch = cvt_hex(p, 2); p += 2; break;
1347                         case 'u': ch = cvt_hex(p, 4); p += 4; break;
1348                         case 'U': ch = cvt_hex(p, 8); p += 8; break;
1349                         case 't': ch = '\t'; break;
1350                         case 'n': ch = '\n'; break;
1351                         case 'r': ch = '\r'; break;
1352                         case 'f': ch = '\f'; break;
1353                         }
1354                         if (ch == WEOF)
1355                                 return -1;
1356                 }
1357
1358                 if (ch >= WERR) {
1359                         return -1;
1360                 } else if (ch == '[' && is_set_element(p)) {
1361                         switch(p[0]) {
1362                         case '.': /* collating set */
1363                         case '=': /* collating element */
1364                                 /* FIXME */
1365                                 st->patn = p;
1366                                 return -1;
1367                         case ':': /* character class */
1368                         {
1369                                 const char *e;
1370                                 char *cls;
1371                                 wctype_t wct;
1372                                 p += 1;
1373                                 e = strchr(p, ':');
1374                                 if (!e)
1375                                         e = p + strlen(p);
1376                                 cls = strndup(p, e-p);
1377                                 wct = wctype(cls);
1378                                 free(cls);
1379                                 if (!wct)
1380                                         return -1;
1381                                 p = e;
1382                                 while (*p && *p != ']')
1383                                         p++;
1384                                 p++;
1385                                 add_class(st, plane, wct);
1386                                 break;
1387                         }
1388                         }
1389                 } else if (p[0] == '-' && p[1] != ']') {
1390                         /* range */
1391                         wint_t ch2;
1392                         p += 1;
1393                         ch2 = get_utf8(&p, NULL);
1394                         if (ch2 >= WERR ||
1395                             !add_range(st, ch, ch2, plane, &planes, &newplane))
1396                                 return -1;
1397                 } else if (p[0] == ']' && (p == st->patn ||
1398                                            (invert && p == st->patn+1))) {
1399                         if (!add_range(st, ch, ch, plane, &planes, &newplane))
1400                                 return -1;
1401                 } else if (ch == '\\' && p[0] > 0 && p[0] < 0x7f && p[1] != '-'
1402                            && strchr("daApsw", p[0]) != NULL) {
1403                         switch (p[0]) {
1404                         case 'd': add_class(st, plane, wctype("digit")); break;
1405                         case 'a': add_class(st, plane, wctype("lower")); break;
1406                         case 'A': add_class(st, plane, wctype("upper")); break;
1407                         case 'p': add_class(st, plane, wctype("punct")); break;
1408                         case 's': add_class(st, plane, wctype("space")); break;
1409                         case 'h': add_class(st, plane, wctype("blank")); break;
1410                         case 'w': add_class(st, plane, wctype("alpha")); break;
1411                         }
1412                         p += 1;
1413                 } else if (ch) {
1414                         if (!add_range(st, ch, ch, plane, &planes, &newplane))
1415                                 return -1;
1416                 }
1417         } while (*p != ']');
1418         st->patn = p+1;
1419         if (st->sets) {
1420                 if (plane < 0) {
1421                         /* We have a (possibly empty) class list. Record size */
1422                         unsigned short l = st->len;
1423                         if (invert)
1424                                 l |= 0x8000;
1425                         st->sets[st->set] = l;
1426                 } else {
1427                         /* We have a set, not empty.  Store size */
1428                         st->sets[st->set] = st->len | (plane << 11);
1429                 }
1430         }
1431         st->set += st->len+1;
1432         return newplane;
1433 }
1434
1435 static bool parse_set(struct parse_state *st safe)
1436 {
1437         int plane;
1438         const char *patn;
1439         int set;
1440
1441         if (*st->patn++ != '[')
1442                 return False;
1443         /* parse the set description multiple times if necessary
1444          * building up each sub table one at a time.
1445          * First time through we do classes, and report which set
1446          * to do next.  Then again for each Unicode plane that
1447          * is needed
1448          * do_parse_set returns -1 on error, next plane number needed,
1449          * or a number larger than any valid plane number when done.
1450          * When pre-parsing to calculate sizes, we guess the sizes on a single
1451          * walk through - possibly over-estimating.
1452          */
1453         set = st->set;
1454         plane = -1; /* Code for "parse classes" */
1455         patn = st->patn;
1456         do {
1457                 st->patn = patn;
1458                 plane = do_parse_set(st, plane);
1459         } while (plane >= 0 && plane <= 0x100000);
1460         if (plane < 0)
1461                 return False;
1462         if (st->sets)
1463                 st->sets[st->set] = 0;
1464         st->set++;
1465         add_cmd(st, REC_SET | set);
1466         return True;
1467 }
1468
1469 static unsigned short add_class_set(struct parse_state *st safe,
1470                                     char *cls safe, int in)
1471 {
1472         int set = st->set;
1473         if (!st->sets) {
1474                 /* Need the length header, a class, and another zero length */
1475                 st->set += 1 + wctype_cells + 1;
1476                 return REC_SET;
1477         }
1478         st->sets[set] = wctype_cells + (in ? 0 : 0x8000);
1479         st->len = 0;
1480         add_class(st, -1, wctype(cls));
1481         st->sets[set + 1 + wctype_cells] = 0;
1482         st->set += 1 + wctype_cells + 1;
1483         return REC_SET | set;
1484 }
1485 static bool parse_re(struct parse_state *st safe, int capture);
1486 static bool parse_atom(struct parse_state *st safe)
1487 {
1488         /* parse out an atom: one of:
1489          * (re)
1490          * [set]
1491          * .
1492          * \special
1493          * ^
1494          * $
1495          * char - including UTF8
1496          *
1497          * If there is a syntax error, return False, else return True;
1498          *
1499          */
1500         wint_t ch;
1501         bool is_char = False;
1502
1503         if (*st->patn == '\0')
1504                 return False;
1505         if (*st->patn == '.') {
1506                 if (st->mod & SingleLine)
1507                         add_cmd(st, REC_ANY);
1508                 else
1509                         add_cmd(st, REC_ANY_NONL);
1510                 st->patn++;
1511                 return True;
1512         }
1513         if (*st->patn == '(') {
1514                 st->patn++;
1515                 if (!parse_re(st, 0))
1516                         return False;
1517                 if (*st->patn != ')')
1518                         return False;
1519                 st->patn++;
1520                 return True;
1521         }
1522         if (*st->patn == '^') {
1523                 add_cmd(st, REC_SOL);
1524                 st->patn++;
1525                 return True;
1526         }
1527         if (*st->patn == '$') {
1528                 if (isdigit(st->patn[1])) {
1529                         /* $n and $nn is a backref */
1530                         ch = st->patn[1] - '0';
1531                         st->patn += 2;
1532                         if (isdigit(st->patn[0])) {
1533                                 ch = ch * 10 + st->patn[0] - '0';
1534                                 st->patn += 1;
1535                         }
1536                         add_cmd(st, REC_BACKREF_MAKE(ch));
1537                         return True;
1538                 }
1539                 add_cmd(st, REC_EOL);
1540                 st->patn++;
1541                 return True;
1542         }
1543         if (*st->patn == '[')
1544                 return parse_set(st);
1545         if ((st->mod & LaxMatch) &&
1546             st->patn[0] == ' ' && st->patn[1] != ' ' && st->patn[1] != '\t' &&
1547             (st->next == 1 || (st->patn[-1] != ' ' && st->patn[-1] != '\t'))) {
1548                 add_cmd(st, REC_LAXSPC);
1549                 /* LAXSPC can be repeated */
1550                 add_cmd(st, REC_FORKFIRST | (st->next - 1));
1551                 st->patn++;
1552                 return True;
1553         }
1554         if ((st->mod & LaxMatch) &&
1555             (st->patn[0] == '"' || st->patn[0] == '`' || st->patn[0] == '\'')) {
1556                 add_cmd(st, REC_LAXQUOT);
1557                 st->patn++;
1558                 return True;
1559         }
1560         if ((st->mod & LaxMatch) &&
1561             (st->patn[0] == '-' || st->patn[0] == '_')) {
1562                 add_cmd(st, REC_LAXDASH);
1563                 st->patn++;
1564                 return True;
1565         }
1566         if (*st->patn & 0x80) {
1567                 ch = get_utf8(&st->patn, NULL);
1568                 if (ch >= WERR)
1569                         return False;
1570                 st->patn -= 1;
1571                 is_char = True;
1572         } else
1573                 ch = *st->patn;
1574         if (ch == '\\') {
1575                 st->patn++;
1576                 ch = *st->patn;
1577                 switch (ch) {
1578                         /* These just fall through and are interpreted
1579                          * literally */
1580                 case '^':
1581                 case '.':
1582                 case '[':
1583                 case ']':
1584                 case '$':
1585                 case '(':
1586                 case ')':
1587                 case '|':
1588                 case '*':
1589                 case '+':
1590                 case '?':
1591                 case '{':
1592                 case '}':
1593                 case '\\':
1594                         break;
1595                         /* These are simple translations */
1596                 case '`': ch = REC_SOD; break;
1597                 case '\'':ch = REC_EOD; break;
1598                 case '=': ch = REC_POINT; break;
1599                 case '<': ch = REC_SOW; break;
1600                 case '>': ch = REC_EOW; break;
1601                 case 'b': ch = REC_WBRK; break;
1602                 case 'B': ch = REC_NOWBRK; break;
1603                 case 't': ch = '\t'; break;
1604                 case 'n': ch = '\n'; break;
1605                 case 'r': ch = '\r'; break;
1606                 case 'f': ch = '\f'; break;
1607                 case '0': ch = cvt_oct(&st->patn, 4);
1608                         st->patn -= 1;
1609                         is_char = True;
1610                         break;
1611                 case 'x': ch = cvt_hex(st->patn+1, 2);
1612                         if (ch >= WERR)
1613                                 return False;
1614                         is_char = True;
1615                         st->patn += 2;
1616                         break;
1617                 case 'u': ch = cvt_hex(st->patn+1, 4);
1618                         if (ch >= WERR)
1619                                 return False;
1620                         is_char = True;
1621                         st->patn += 4;
1622                         break;
1623                 case 'U': ch = cvt_hex(st->patn+1, 8);
1624                         if (ch >= WERR)
1625                                 return False;
1626                         is_char = True;
1627                         st->patn += 8;
1628                         break;
1629                 case '1'...'9': ch = st->patn[0] - '0';
1630                         while (st->patn[1] >= '0' && st->patn[1] <= '9') {
1631                                 ch = ch * 10 + st->patn[1] - '0';
1632                                 st->patn += 1;
1633                         }
1634                         ch = REC_BACKREF_MAKE(ch);
1635                         break;
1636                 case 'd': ch = add_class_set(st, "digit", 1); break;
1637                 case 'D': ch = add_class_set(st, "digit", 0); break;
1638                 case 's': ch = add_class_set(st, "space", 1); break;
1639                 case 'S': ch = add_class_set(st, "space", 0); break;
1640                 case 'h': ch = add_class_set(st, "blank", 1); break;
1641                 case 'H': ch = add_class_set(st, "blank", 0); break;
1642                 case 'w': ch = add_class_set(st, "alpha", 1); break;
1643                 case 'W': ch = add_class_set(st, "alpha", 0); break;
1644                 case 'p': ch = add_class_set(st, "punct", 1); break;
1645                 case 'P': ch = add_class_set(st, "punct", 0); break;
1646
1647                 case 'a': ch = add_class_set(st, "lower", 1); break;
1648                 case 'A': ch = add_class_set(st, "upper", 0); break;
1649
1650                         /* Anything else is an error (e.g. \0) or
1651                          * reserved for future use.
1652                          */
1653                 default: return False;
1654                 }
1655         }
1656         if (ch < 0x8000 || !is_char) {
1657                 add_cmd(st, ch);
1658         } else if (ch <= 0x10FFFF) {
1659                 add_cmd(st, REC_PLANE | (ch >> 16));
1660                 add_cmd(st, ch & 0xFFFF);
1661         }
1662         st->patn++;
1663         return True;
1664 }
1665
1666 static bool parse_piece(struct parse_state *st safe)
1667 {
1668         int start = st->next;
1669         char c;
1670         int min, max;
1671         char *ep;
1672         int skip = 0;
1673         int nongreedy = 0;
1674
1675         if (!parse_atom(st))
1676                 return False;
1677         c = *st->patn;
1678         if (c != '*' && c != '+' && c != '?' &&
1679             !(c=='{' && isdigit(st->patn[1])))
1680                 return True;
1681
1682         st->patn += 1;
1683         switch(c) {
1684         case '*':
1685                 /* make spare for 'jump forward' */
1686                 relocate(st, start, 1);
1687                 if (st->patn[0] == '?') {
1688                         st->patn += 1;
1689                         /* non-greedy match */
1690                         add_cmd(st, REC_FORKLAST | (start+1));
1691                         if (st->rxl)
1692                                 st->rxl[start] = REC_FORKFIRST | st->next;
1693                 } else {
1694                         add_cmd(st, REC_FORKFIRST | (start+1));
1695                         if (st->rxl)
1696                                 st->rxl[start] = REC_FORKLAST | st->next;
1697                 }
1698                 return True;
1699         case '+':
1700                 /* just (optional) jump back */
1701                 if (st->patn[0] == '?') {
1702                         st->patn += 1;
1703                         /* non-greedy */
1704                         add_cmd(st, REC_FORKLAST | start);
1705                 } else
1706                         add_cmd(st, REC_FORKFIRST | start);
1707                 return True;
1708         case '?':
1709                 /* Just a jump-forward */
1710                 relocate(st, start, 1);
1711                 if (st->patn[0] == '?') {
1712                         st->patn += 1;
1713                         if (st->rxl)
1714                                 st->rxl[start] = REC_FORKFIRST | st->next;
1715                 } else {
1716                         if (st->rxl)
1717                                 st->rxl[start] = REC_FORKLAST | st->next;
1718                 }
1719                 return True;
1720         case '{':/* Need a number, maybe a comma, if not maybe a number,
1721                   * then }, and optionally a '?' after that.
1722                   */
1723                 min = strtoul(st->patn, &ep, 10);
1724                 if (min > 256 || !ep)
1725                         return False;
1726                 max = min;
1727                 if (*ep == ',') {
1728                         max = -1;
1729                         ep++;
1730                         if (isdigit(*ep)) {
1731                                 max = strtoul(ep, &ep, 10);
1732                                 if (max > 256 || max < min || !ep)
1733                                         return False;
1734                         }
1735                 }
1736                 if (*ep != '}')
1737                         return False;
1738                 if (ep[1] == '?') {
1739                         nongreedy = (REC_FORKLAST ^ REC_FORKFIRST);
1740                         ep += 1;
1741                 }
1742                 st->patn = ep+1;
1743                 /* Atom need to be repeated min times, and maybe as many
1744                  * as 'max', or indefinitely if max < 0
1745                  */
1746                 while (min > 1) {
1747                         /* Make a duplicate */
1748                         int newstart = st->next;
1749                         relocate(st, start, st->next - start);
1750                         start = newstart;
1751                         min -= 1;
1752                         max -= 1;
1753                 }
1754                 if (min == 0) {
1755                         /* Need to allow the atom to be skipped */
1756                         relocate(st, start, 1);
1757                         if (st->rxl) {
1758                                 st->rxl[start] = (REC_FORKLAST^nongreedy) | st->next;
1759                                 skip = start;
1760                         }
1761                         start += 1;
1762                 }
1763                 if (max < 0) {
1764                         add_cmd(st, (REC_FORKFIRST^nongreedy) | start);
1765                 } else if (max > 1) {
1766                         /* need to duplicate atom but make each one optional */
1767                         int len = st->next - start;
1768                         int last = st->next + (len + 1) * (max-1);
1769                         if (skip && st->rxl) {
1770                                 st->rxl[skip] = (REC_FORKLAST^nongreedy) | last;
1771                         }
1772                         while (max > 1) {
1773                                 int newstart;
1774                                 add_cmd(st, (REC_FORKLAST^nongreedy) | last);
1775                                 newstart = st->next;
1776                                 relocate(st, start, len+1);
1777                                 st->next -= 1;
1778                                 start = newstart;
1779                                 max -= 1;
1780                         }
1781                         if (last != st->next) {
1782                                 #ifdef DEBUG
1783                                 abort();
1784                                 #else
1785                                 return False;
1786                                 #endif
1787                         }
1788                 }
1789                 return True;
1790         }
1791         return False;
1792 }
1793
1794 static bool parse_branch(struct parse_state *st safe)
1795 {
1796         do {
1797                 if (!parse_piece(st))
1798                         return False;
1799                 switch (*st->patn) {
1800                 case '*':
1801                 case '+':
1802                 case '?':
1803                         /* repeated modifier - illegal */
1804                         return False;
1805                 }
1806         } while (*st->patn && *st->patn != '|' && *st->patn != ')');
1807         return True;
1808 }
1809
1810 /* rxl_fatch_match
1811  * like 'strstr', but length is passed for both 'needle' and
1812  * 'haystack', and it also finds a match for a prefix of needle
1813  * at the very end.
1814  * This can be used to accelerate search for verbatim content.
1815  */
1816 int rxl_fast_match(const char *needle safe, int nlen,
1817                    const char *haystack safe, int hlen)
1818 {
1819         int ret = 0;
1820
1821         while (hlen >= nlen) {
1822                 int nl = nlen;
1823                 int i = 0;
1824
1825                 while (haystack[i] == needle[i]) {
1826                         i++;
1827                         nl--;
1828                         if (!nl)
1829                                 return ret;
1830                 }
1831                 haystack++;
1832                 hlen--;
1833                 ret++;
1834         }
1835         /* Maybe a suffix of haystack is a prefix of needle */
1836         while (hlen) {
1837                 int nl = hlen;
1838                 int i = 0;
1839
1840                 while (haystack[i] == needle[i]) {
1841                         i++;
1842                         nl--;
1843                         if (!nl)
1844                                 return ret;
1845                 }
1846                 haystack++;
1847                 hlen--;
1848                 ret++;
1849         }
1850         /* No match - return original hlen, when is now in ret */
1851         return ret;
1852 }
1853
1854 static int parse_prefix(struct parse_state *st safe)
1855 {
1856         /* A prefix to an re starts with '?' and 1 or more
1857          * chars depending on what the next char is.
1858          * A () group that starts '?' is never captured.
1859          *
1860          * ?:  no-op.  Only effect is to disable capture  This applies
1861          *     recursively.
1862          * ?|  groups in each branch use same capture numbering
1863          * ?0  All chars to end of pattern are literal matches.  This cannot
1864          *     be used inside ()
1865          * ?N..: where N is a digit 1-9, it and all digits upto ':' give the
1866          *       number of chars for literal pattern.  This must be the whole re,
1867          *       so either ) follows, or end-of-pattern.
1868          * ?iLsn-iLsn:
1869          *     Each letter represents a flag which is set if it appears before
1870          *     '-' and cleared if it appears after.  The '-' is optional, but
1871          *     the ':' isn't.
1872          *   i  ignore case in this group
1873          *   L  lax matching for space and hyphen in this group
1874          *   s  single-line.  '.' matches newline in this group
1875          *   n  no capture in subgroups unless 'n' is explicitly re-enabled.
1876          *      So if 'n' is already disabled, you need
1877          *       (?n:(regexp))
1878          *      to create a captured group
1879          *   any other flag before the ':' causes an error
1880          *
1881          * Return:
1882          * -1  bad prefix
1883          * 0  no prefix
1884          * 1  good prefix, st->mod updated if needed.
1885          * 2  literal parsed, don't parse further for this re.
1886          */
1887         const char *s;
1888         int verblen = 0;
1889         char *ve;
1890         bool neg = False;
1891
1892         if (*st->patn != '?')
1893                 return 0;
1894         s = st->patn + 1;
1895         switch (*s) {
1896         default:
1897                 return -1;
1898         case ':':
1899                 break;
1900         case '|':
1901                 st->mod |= CapturePerBranch;
1902                 break;
1903         case '0':
1904                 verblen = -1;
1905                 break;
1906         case '-':
1907         case 'i':
1908         case 'L':
1909         case 's':
1910         case 'n':
1911                 for (; *s && *s != ':'; s++)
1912                         switch (*s) {
1913                         case '-':
1914                                 neg = True;
1915                                 break;
1916                         case 'i':
1917                                 st->mod |= IgnoreCase;
1918                                 if (neg)
1919                                         st->mod &= ~IgnoreCase;
1920                                 break;
1921                         case 'L':
1922                                 st->mod |= LaxMatch;
1923                                 if (neg)
1924                                         st->mod &= ~LaxMatch;
1925                                 break;
1926                         case 's':
1927                                 st->mod |= SingleLine;
1928                                 if (neg)
1929                                         st->mod &= ~SingleLine;
1930                                 break;
1931                         case 'n':
1932                                 st->mod &= ~DoCapture;
1933                                 if (neg)
1934                                         st->mod |= DoCapture;
1935                                 break;
1936                         case ':':
1937                                 break;
1938                         default:
1939                                 return -1;
1940                         }
1941                 if (*s != ':')
1942                         return -1;
1943                 break;
1944         case '1' ... '9':
1945                 verblen = strtoul(s, &ve, 10);
1946                 if (!ve || *ve != ':')
1947                         return -1;
1948                 s = ve;
1949                 break;
1950         }
1951         s += 1;
1952         st->patn = s;
1953         if (verblen == 0)
1954                 return 1;
1955         while (verblen && *s) {
1956                 wint_t ch;
1957                 if (*s & 0x80) {
1958                         ch = get_utf8(&s, NULL);
1959                         if (ch >= WERR)
1960                                 return 0;
1961                 } else
1962                         ch = *s++;
1963                 add_cmd(st, ch);
1964                 verblen -= 1;
1965         }
1966         st->patn = s;
1967         return 2;
1968 }
1969
1970 static bool parse_re(struct parse_state *st safe, int capture_flag)
1971 {
1972         int re_start;
1973         int start;
1974         int save_mod = st->mod;
1975         int ret;
1976         int capture = st->capture;
1977         int capture_start, capture_max;
1978         int do_capture = st->mod & DoCapture;
1979
1980         switch (parse_prefix(st)) {
1981         case -1: /* error */
1982                 return False;
1983         case 0:
1984                 break;
1985         case 1:
1986                 /* Don't capture if inside () */
1987                 do_capture = capture_flag;
1988                 break;
1989         case 2:
1990                 /* Fully parsed - no more is permitted */
1991                 return True;
1992         }
1993         if ((st->mod ^ save_mod) & IgnoreCase) {
1994                 /* change of ignore-case status */
1995                 if (st->mod & IgnoreCase)
1996                         add_cmd(st, REC_IGNCASE);
1997                 else
1998                         add_cmd(st, REC_USECASE);
1999         }
2000
2001         if (do_capture) {
2002                 add_cmd(st, REC_CAPTURE | capture);
2003                 st->capture += 1;
2004         }
2005         capture_start = capture_max = st->capture;
2006         start = re_start = st->next;
2007
2008         while ((ret = parse_branch(st)) != 0 && *st->patn == '|') {
2009                 st->patn += 1;
2010                 relocate(st, start, 1);
2011                 if (st->rxl)
2012                         st->rxl[start] = REC_FORKLAST | (st->next + 2);
2013                 add_cmd(st, REC_FORKLAST | start); /* will become 'jump to end' */
2014                 add_cmd(st, REC_NONE);
2015                 start = st->next;
2016                 if (st->mod & CapturePerBranch) {
2017                         /* Restart capture index each time */
2018                         if (st->capture > capture_max)
2019                                 capture_max = st->capture;
2020                         st->capture = capture_start;
2021                 }
2022         }
2023         if (ret && st->rxl) {
2024                 /* Need to patch all the "jump to end" links */
2025                 while (start > re_start) {
2026                         unsigned short cmd = st->rxl[start - 2];
2027                         st->rxl[start - 2] = REC_FORKLAST | st->next;
2028                         start = REC_ADDR(cmd);
2029                 }
2030         }
2031         if (st->mod & CapturePerBranch && st->capture < capture_max)
2032                 st->capture = capture_max;
2033         if (do_capture)
2034                 add_cmd(st, REC_CAPTURED | capture);
2035         if ((st->mod ^ save_mod) & IgnoreCase) {
2036                 /* restore from char of ignore-case status */
2037                 if (save_mod & IgnoreCase)
2038                         add_cmd(st, REC_IGNCASE);
2039                 else
2040                         add_cmd(st, REC_USECASE);
2041         }
2042         st->mod = save_mod;
2043         return ret;
2044 }
2045
2046 unsigned short *rxl_parse(const char *patn safe, int *lenp, int nocase)
2047 {
2048         struct parse_state st;
2049         st.patn = patn;
2050         st.mod = nocase ? IgnoreCase | LaxMatch : 0;
2051         st.mod |= DoCapture;
2052         st.rxl = NULL;
2053         st.next = 1;
2054         st.sets = NULL;
2055         st.set = 0;
2056         st.capture = 0;
2057         if (nocase)
2058                 add_cmd(&st, REC_IGNCASE);
2059         if (!parse_re(&st, DoCapture) || *st.patn != '\0') {
2060                 if (lenp)
2061                         *lenp = st.patn - patn;
2062                 return NULL;
2063         }
2064         add_cmd(&st, REC_MATCH);
2065         st.rxl = malloc((st.next + st.set) * sizeof(st.rxl[0]));
2066         st.rxl[0] = st.next;
2067         st.sets = st.rxl + st.next;
2068         st.patn = patn;
2069         st.mod = nocase ? IgnoreCase | LaxMatch : 0;
2070         st.mod |= DoCapture;
2071         st.next = 1;
2072         st.set = 0;
2073         st.capture = 0;
2074         if (nocase)
2075                 add_cmd(&st, REC_IGNCASE);
2076         if (!parse_re(&st, DoCapture)) {
2077                 #ifdef DEBUG
2078                 abort();
2079                 #else
2080                 free(st.rxl);
2081                 return NULL;
2082                 #endif
2083         }
2084         add_cmd(&st, REC_MATCH);
2085         return st.rxl;
2086 }
2087
2088 unsigned short *safe rxl_parse_verbatim(const char *patn safe, int nocase)
2089 {
2090         struct parse_state st;
2091         wint_t ch;
2092
2093         st.next = 1 + !!nocase + strlen(patn) + 1;
2094         st.rxl = malloc(st.next * sizeof(st.rxl[0]));
2095         st.rxl[0] = st.next;
2096         st.next = 1;
2097         if (nocase)
2098                 add_cmd(&st, REC_IGNCASE);
2099         while ((ch = get_utf8(&patn, NULL)) < WERR)
2100                 add_cmd(&st, ch);
2101         add_cmd(&st, REC_MATCH);
2102         return st.rxl;
2103 }
2104
2105 int rxl_prefix(unsigned short *rxl safe, char *ret safe, int max)
2106 {
2107         /* Return in ret a contant prefix of the search string,
2108          * if there is one.  Report the number of bytes.
2109          */
2110         int len = RXL_PATNLEN(rxl);
2111         int i;
2112         int found = 0;
2113
2114         for (i = 1; i < len; i++) {
2115                 if (REC_ISCHAR(rxl[i])) {
2116                         int l = utf8_bytes(rxl[i]);
2117                         if (l == 0 || found + l > max)
2118                                 /* No more room */
2119                                 break;
2120                         put_utf8(ret + found, rxl[i]);
2121                         found += l;
2122                         continue;
2123                 }
2124                 if (REC_ISPLANE(rxl[i]) && i+1 < len) {
2125                         int ch = REC_PLANE_MAKE(rxl[i], rxl[i+1]);
2126                         int l = utf8_bytes(ch);
2127                         i += 1;
2128                         if (l == 0 || found + l > max)
2129                                 /* No more room */
2130                                 break;
2131                         put_utf8(ret + found, ch);
2132                         found += l;
2133                         continue;
2134                 }
2135                 if (rxl[i] >= REC_SOL && rxl[i] <= REC_POINT)
2136                         /* zero-width match doesn't change prefix */
2137                         continue;
2138                 if (rxl[i] == REC_USECASE)
2139                         /* Insisting on case-correct doesn't change prefix */
2140                         continue;
2141                 if (REC_ISCAPTURE(rxl[i]))
2142                         continue;
2143                 /* Nothing more that is fixed */
2144                 break;
2145         }
2146         return found;
2147 }
2148
2149 struct match_state *safe rxl_prepare(unsigned short *rxl safe, int flags)
2150 {
2151         struct match_state *st;
2152         int len = RXL_PATNLEN(rxl);
2153         int i;
2154         bool ic = False;
2155         int eol;
2156
2157         st = malloc(sizeof(*st));
2158         memset(st, 0, sizeof(*st));
2159         st->rxl = rxl;
2160         st->anchored = flags & RXLF_ANCHORED;
2161         st->backtrack = flags & RXLF_BACKTRACK;
2162         if (!st->backtrack) {
2163                 st->link[0] = malloc(len * sizeof(unsigned short) * 4);
2164                 st->link[1] = st->link[0] + len;
2165                 st->leng[0] = st->link[1] + len;
2166                 st->leng[1] = st->leng[0] + len;
2167         }
2168         st->ignorecase = calloc(BITSET_SIZE(len), sizeof(*st->ignorecase));
2169         st->active = 0;
2170         st->match = -1;
2171         if (!st->backtrack) {
2172                 st->link[0][0] = 0;
2173                 st->link[1][0] = 0;
2174         }
2175         for (i = 1; i < len; i++) {
2176                 if (rxl[i] == REC_IGNCASE)
2177                         ic = True;
2178                 if (rxl[i] == REC_USECASE)
2179                         ic = False;
2180                 if (ic)
2181                         set_bit(i, st->ignorecase);
2182                 if (!st->backtrack) {
2183                         st->link[0][i] = NO_LINK;
2184                         st->link[1][i] = NO_LINK;
2185                 }
2186         }
2187
2188         /* Set linkage to say we have a zero-length match
2189          * at the start state.
2190          */
2191         eol = 0;
2192         st->len = -1;
2193         do_link(st, 1, &eol, 0);
2194
2195         return st;
2196 }
2197
2198 void rxl_free_state(struct match_state *s)
2199 {
2200         if (s) {
2201                 free(s->link[0]);
2202                 free(s->ignorecase);
2203                 free(s->buf);
2204                 free(s->record);
2205                 free(s);
2206         }
2207 }
2208
2209 static int get_capture(struct match_state *s safe, int n, int which,
2210                        char *buf, int *startp)
2211 {
2212         int bufp = 0; /* Index in s->buf */
2213         int rxlp = 1; /* Index in s->rxl */
2214         int recp = 0; /* Index in s->rec */
2215         int rxll = RXL_PATNLEN(s->rxl);
2216         int start = 0;
2217         int len = -1;
2218
2219         while (rxlp < rxll && recp <= s->record_count) {
2220                 unsigned short cmd = s->rxl[rxlp];
2221
2222                 if (REC_ISFORK(cmd)) {
2223                         bool recorded = False;
2224                         if (recp < s->record_count &&
2225                             s->record[recp].pos == rxlp &&
2226                             s->record[recp].len == bufp) {
2227                                 recorded = True;
2228                                 recp += 1;
2229                         }
2230                         if (recorded
2231                             ==
2232                             REC_ISFIRST(cmd))
2233                                 /* This fork was taken */
2234                                 rxlp = REC_ADDR(cmd);
2235                         else
2236                                 /* Fork not taken */
2237                                 rxlp += 1;
2238                         continue;
2239                 }
2240                 if (REC_ISCAPTURE(cmd) &&
2241                     REC_CAPNUM(cmd) == n) {
2242                         if (REC_CAPEND(cmd)) {
2243                                 len = bufp - start;
2244                                 if (--which == 0)
2245                                         break;
2246                         } else {
2247                                 start = bufp;
2248                                 len = -1;
2249                         }
2250                 }
2251                 if (rec_zerowidth(cmd)) {
2252                         rxlp += 1;
2253                         continue;
2254                 }
2255                 bufp += 1;
2256                 rxlp += 1;
2257         }
2258         if (which > 0)
2259                 return -1;
2260         if (startp)
2261                 *startp = start;
2262         if (len > 0 && buf) {
2263                 int i;
2264                 for (i = 0; i < len; i++)
2265                         buf[i] = s->buf[start+i] & 0xff;
2266                 buf[i] = 0;
2267         }
2268         return len;
2269 }
2270
2271 int rxl_capture(struct match_state *st safe, int cap, int which,
2272                 int *startp safe, int *lenp safe)
2273 {
2274         int len = get_capture(st, cap, which, NULL, startp);
2275
2276         *lenp = len;
2277         return len >= 0;
2278 }
2279
2280 static int interp(struct match_state *s safe, const char *form safe, char *buf)
2281 {
2282         int len = 0;
2283
2284         while (*form) {
2285                 int which, n = 0;
2286                 char *e;
2287
2288                 if (form[0] != '\\') {
2289                         if (buf)
2290                                 buf[len] = *form;
2291                         len += 1;
2292                         form += 1;
2293                         continue;
2294                 }
2295                 if (form[1] == '\\') {
2296                         if (buf)
2297                                 buf[len] = '\\';
2298                         len += 1;
2299                         form += 2;
2300                         continue;
2301                 }
2302                 /* must be \NN to get last of group NN or
2303                  * \:NN:MM to get MMth of grop NN
2304                  */
2305                 if (isdigit(form[1])) {
2306                         which = strtoul(form+1, &e, 10);
2307                 } else if (form[1] == ':' && isdigit(form[2])) {
2308                         which = strtoul(form+2, &e, 10);
2309                         if (!e || e[0] != ':' || !isdigit(e[1]))
2310                                 return True;
2311                         n = strtoul(e+2, &e, 10);
2312                 } else
2313                         return -1;
2314
2315                 n = get_capture(s, which, n, buf ? buf+len : buf, NULL);
2316                 len += n;
2317                 if (!e)
2318                         break;
2319                 form = e;
2320         }
2321         if (buf)
2322                 buf[len] = 0;
2323         return len;
2324 }
2325
2326 char *rxl_interp(struct match_state *s safe, const char *form safe)
2327 {
2328         int size;
2329         char *ret;
2330
2331         if (!s->backtrack)
2332                 return NULL;
2333         size = interp(s, form, NULL);
2334         if (size < 0)
2335                 return NULL;
2336         ret = malloc(size+1);
2337         interp(s, form, ret);
2338         return ret;
2339 }
2340
2341 #ifdef DEBUG
2342 #include <locale.h>
2343 static void printc(unsigned int c)
2344 {
2345         if (c <= ' ' || c >= 0x7f)
2346                 printf("\\x%02x", c);
2347         else
2348                 printf("%c", c);
2349 }
2350
2351 static void print_set(unsigned short *set safe)
2352 {
2353         int len = *set++;
2354         int invert = len & 0x8000;
2355
2356         if (invert)
2357                 printf("^ ");
2358         len &= 0x7fff;
2359         if (len)
2360                 printf("[{%d}", sizeof(wctype_t));
2361         while (len) {
2362                 wctype_t class;
2363                 memcpy(&class, set, sizeof(wctype_t));
2364                 set += wctype_cells;
2365                 len -= wctype_cells;
2366                 printf(":%lx", class);
2367                 if (!len)
2368                         printf("]");
2369         }
2370         while ((len = *set++) != 0) {
2371                 unsigned int plane = (len & 0xF800) << 5;
2372                 len &= 0x7ff;
2373                 printf("%d:[", len);
2374                 while (len > 0) {
2375                         printc(*set | plane);
2376                         if (len > 1) {
2377                                 printf(",");
2378                                 set += 1;
2379                                 printc(set[0] + plane);
2380                                 len -= 1;
2381                         }
2382                         set += 1;
2383                         len -= 1;
2384                         if (len)
2385                                 printf(";");
2386                 }
2387                 printf("]; ");
2388         }
2389 }
2390
2391 void rxl_print(unsigned short *rxl safe)
2392 {
2393         unsigned short *set = RXL_SETSTART(rxl);
2394         unsigned short *i;
2395
2396         for (i = rxl+1 ; i < set; i++) {
2397                 unsigned int cmd = *i;
2398                 char t[5];
2399                 printf("%04u: ", i-rxl);
2400                 if (REC_ISCHAR(cmd))
2401                         printf("match %s (#%x)\n", put_utf8(t, cmd), cmd);
2402                 else if (REC_ISSPEC(cmd)) {
2403                         switch(cmd) {
2404                         case REC_ANY: printf("match ANY\n"); break;
2405                         case REC_ANY_NONL: printf("match ANY-non-NL\n"); break;
2406                         case REC_NONE: printf("DEAD END\n"); break;
2407                         case REC_SOL: printf("match start-of-line\n"); break;
2408                         case REC_EOL: printf("match end-of-line\n"); break;
2409                         case REC_SOW: printf("match start-of-word\n"); break;
2410                         case REC_EOW: printf("match end-of-word\n"); break;
2411                         case REC_SOD: printf("match start-of-doc\n"); break;
2412                         case REC_EOD: printf("match end-of-doc\n"); break;
2413                         case REC_POINT: printf("match focus-point\n"); break;
2414                         case REC_MATCH: printf("MATCHING COMPLETE\n"); break;
2415                         case REC_WBRK: printf("match word-break\n"); break;
2416                         case REC_NOWBRK: printf("match non-wordbreak\n"); break;
2417                         case REC_LAXSPC: printf("match lax-space\n"); break;
2418                         case REC_LAXQUOT: printf("match lax-quote\n"); break;
2419                         case REC_LAXDASH: printf("match lax-dash\n"); break;
2420                         case REC_IGNCASE: printf("switch ignore-case\n"); break;
2421                         case REC_USECASE: printf("switch use-case\n"); break;
2422                         default: printf("ERROR %x\n", cmd); break;
2423                         }
2424                 } else if (REC_ISPLANE(cmd) && i + 1 < set) {
2425                         cmd = REC_PLANE_MAKE(cmd, i[1]);
2426                         i += 1;
2427                         printf("match %s (#%x)\n", put_utf8(t, cmd), cmd);
2428                 } else if (REC_ISFORK(cmd))
2429                         printf("branch to %d %s\n", REC_ADDR(cmd),
2430                                REC_ISFIRST(cmd) ? "first" : "later");
2431                 else if (REC_ISSET(cmd)) {
2432                         printf("Match from set %d: ", REC_ADDR(cmd));
2433                         print_set(set + REC_ADDR(cmd));
2434                         printf("\n");
2435                 } else if (REC_ISBACKREF(cmd)) {
2436                         printf("Backref to capture %d\n", REC_CAPNUM(cmd));
2437                 } else if (REC_ISCAPTURE(cmd) && !REC_CAPEND(cmd)) {
2438                         printf("Start Capture %d\n", REC_CAPNUM(cmd));
2439                 } else if (REC_ISCAPTURE(cmd)) {
2440                         printf("End   Capture %d\n", REC_CAPNUM(cmd));
2441                 } else
2442                         printf("ERROR %x\n", cmd);
2443         }
2444 }
2445
2446 enum {
2447         F_VERB = 1,
2448         F_ICASE = 2,
2449         F_PERR = 4,
2450         F_BACKTRACK = 8,
2451 };
2452 static struct test {
2453         char *patn, *target;
2454         int flags, start, len;
2455         char *form, *replacement;
2456 } tests[] = {
2457         { "abc", "the abc", 0, 4, 3},
2458         { "abc\\'", "the abc", 0, 4, 3},
2459         { "\\`abc", "the abc", 0, -1, -1},
2460         { "abc\\=", "abcabcPointabc", 0, 3, 3},
2461         { "abc", "the ABC", F_ICASE, 4, 3},
2462         { "a*", " aaaaac", 0, 0,  0},
2463         { "a*", "aaaaac", 0, 0,  5},
2464         { "a*", "AaAaac", F_ICASE, 0,  5},
2465         { "a+", " aaaaac", 0, 1,  5},
2466         { "?0()+*", " (()+***", 0, 2, 4},
2467         { ".(?2:..).", "abcdefg..hijk", 0, 6, 4},
2468         { "?L:1 2", "hello 1 \t\n 2", 0, 6, 6},
2469         { "?s:a.c", "a\nc abc", 0, 0, 3},
2470         { "?-s:a.c", "a\nc abc", 0, 4, 3},
2471         { "ab[]^-]*cd", "xyab-^^]-cd", 0, 2, 9},
2472         //case insensitive
2473         { "?i:(from|to|cc|subject|in-reply-to):", "From: bob", 0, 0, 5 },
2474         // Inverting set of multiple classes
2475         { "[^\\A\\a]", "a", 0, -1, -1},
2476         // Search for start of a C function: non-label at start of line
2477         { "^([^ a-zA-Z0-9#]|[\\A\\a\\d_]+[\\s]*[^: a-zA-Z0-9_])", "hello:  ",
2478          0, -1, -1},
2479         // Match an empty string
2480         { "[^a-z]*", "abc", 0, 0, 0},
2481         { "^[^a-z]*", "abc", 0, 0, 0},
2482         // repeated long string - should match longest
2483         { "(hello |there )+", "I said hello there hello to you", 0, 7, 18},
2484         // pattern not complete
2485         { "extra close paren)", "anyting", F_PERR, -2, -2},
2486         // word boundaries
2487         { "\\bab", "xyabc acab abc a", 0, 11, 2},
2488         { "\\<ab", "xyabc acab abc a", 0, 11, 2},
2489         { "ab\\>", "ababa abaca ab a", 0, 12, 2},
2490         { "ab\\b", "ababa abaca ab", 0, 12, 2},
2491         { "\\Bab", "ababa abaca ab", 0, 2, 2},
2492         { "[0-9].\\Bab", "012+ab 45abc", 0, 7, 4},
2493         { "[\\060-\\x09].\\Bab", "012+ab 45abc", 0, 7, 4},
2494         // octal chars
2495         { "[\\0101\\0102\\x43\\u0064]*", "ABCddCBA1234", 0, 0, 8},
2496         { "\\011", "a\tb", 0, 1, 1},
2497         // special controls
2498         { "[\t\r\f\n]*\t\r\f\n", "trfn\t\r\f\n\t\r\f\n", 0, 4, 8},
2499         // backref for backtracking only
2500         { "(.(.).)\\1", "123123", F_BACKTRACK, 0, 6},
2501         // backre must skip partial match
2502         { "a(bcdef)$1", "abcdefbc abcdefbcdefg", F_BACKTRACK, 9, 11},
2503         // lax matching
2504         { "hello there-all", "Hello\t  There_ALL-youse", F_ICASE, 0, 17},
2505         { "hello there-all", "Hello\t  There_ALL-youse", 0, -1, -1},
2506         { "^[^a-zA-Z0-9\n]*$", "=======", 0, 0, 7},
2507         { "^$", "", 0, 0, 0},
2508         { "a\\S+b", " a b axyb ", 0, 5, 4},
2509         { "a[^\\s]+b", " a b axyb ", 0, 5, 4},
2510         { "a[^\\s123]+b", " a b a12b axyb ", 0, 10, 4},
2511         { "([\\w\\d]+)\\s*=\\s*(.*[^\\s])", " name = some value ", 0, 1, 17,
2512          "\\1,\\2", "name,some value"},
2513         { "\\brl([123]*|end)\\b", " ->rlend = ", 0, 3, 5,
2514          "->ri\\1 = ", "->riend = "},
2515         { "?|foo(bar)|(bat)foo", "foobar", 0, 0, 6, "\\1", "bar"},
2516         { "?|foo(bar)|(bat)foo", "batfoo", 0, 0, 6, "\\1", "bat"},
2517         // compare greedy and non-greedy
2518         { "(.*)=(.*)", "assign=var=val", 0, 0, 14, "\\1..\\2", "assign=var..val"},
2519         { "(.*?)=(.*)", "assign=var=val", 0, 0, 14, "\\1..\\2", "assign..var=val"},
2520         { "(.+)=(.*)", "assign=var=val", 0, 0, 14, "\\1..\\2", "assign=var..val"},
2521         { "(.+?)=(.*)", "assign=var=val", 0, 0, 14, "\\1..\\2", "assign..var=val"},
2522         { "(.{5,15})=(.*)", "assign=var=val", 0, 0, 14, "\\1..\\2", "assign=var..val"},
2523         { "(.{5,15}?)=(.*)", "assign=var=val", 0, 0, 14, "\\1..\\2", "assign..var=val"},
2524         { "(.?)[a-e]*f", "abcdef", 0, 0, 6, "\\1", "a"},
2525         { "(.?""?)[a-e]*f", "abcdef", 0, 0, 6, "\\1", ""},
2526         { "diff|(stg|git).*show", "git diff", 0, 4, 4},
2527         // \h matches space but not newline
2528         { "spa\\hce", "spa\nce spa ce", 0, 7, 6},
2529         // \s matches  newline
2530         { "spa\\sce", "spa\nce spa ce", 0, 0, 6},
2531         { "x🗑x\U0001f5d1\\U0001f5d1x[x\U0001f5d1y]x", "x🗑x🗑🗑x🗑x", 0, 0, 8},
2532 };
2533
2534 static void run_tests(bool trace)
2535 {
2536         int cnt = sizeof(tests) / sizeof(tests[0]);
2537         int i;
2538         int alg;
2539
2540         for (i = 0, alg = 0;
2541              alg <= 1;
2542              i < cnt-1 ? i++ : (i = 0, alg++)) {
2543                 int flags;
2544                 int f = tests[i].flags;
2545                 char *patn = tests[i].patn;
2546                 const char *target = tests[i].target;
2547                 unsigned short *rxl;
2548                 int mstart, mlen;
2549                 int len, ccnt = 0;
2550                 enum rxl_found r;
2551                 wint_t prev;
2552                 struct match_state *st;
2553
2554                 if (trace)
2555                         printf("Match %s against %s using %s\n", patn, target,
2556                                alg ? "backtrack" : "parallel");
2557                 if (f & F_VERB)
2558                         rxl = rxl_parse_verbatim(patn, f & F_ICASE);
2559                 else
2560                         rxl = rxl_parse(patn, &len, f & F_ICASE);
2561                 if (!rxl) {
2562                         if (f & F_PERR) {
2563                                 if (trace)
2564                                         printf("Parse error as expected\n\n");
2565                                 continue;
2566                         }
2567                         printf("test %d(%s): Parse error at %d\n",
2568                                i, patn, len);
2569                         exit(1);
2570                 }
2571                 if (f & F_PERR) {
2572                         printf("test %d(%s): No parse error found\n", i, patn);
2573                         exit (1);
2574                 }
2575
2576                 if (trace)
2577                         rxl_print(rxl);
2578                 st = rxl_prepare(rxl, alg ? RXLF_BACKTRACK : 0);
2579                 st->trace = trace;
2580
2581                 flags = RXL_SOL|RXL_SOD;
2582                 prev = L' ';
2583                 do {
2584                         wint_t wc = get_utf8(&target, NULL);
2585                         if (wc >= WERR)
2586                                 break;
2587                         if (iswalnum(prev) && !iswalnum(wc))
2588                                 flags |= RXL_EOW;
2589                         else if (!iswalnum(prev) && iswalnum(wc))
2590                                 flags |= RXL_SOW;
2591                         else
2592                                 flags |= RXL_NOWBRK;
2593                         if (wc == 'P' && strstarts(target, "oint"))
2594                                 flags |= RXL_POINT;
2595                         prev =  wc;
2596                         r = rxl_advance(st, wc | flags);
2597                         flags = 0;
2598                         ccnt += 1;
2599                 } while (r != RXL_DONE);
2600                 if (*target == 0) {
2601                         flags |= RXL_EOL|RXL_EOD;
2602                         if (iswalnum(prev))
2603                                 flags |= RXL_EOW;
2604                         rxl_advance(st, flags);
2605                 }
2606                 if (trace)
2607                         printf("\n");
2608                 rxl_info(st, &mlen, NULL, &mstart, NULL);
2609                 if ((f & F_BACKTRACK) && !alg) {
2610                         /* This is only expected to work for backtracking */
2611                         if (mstart != -1 || mlen != -1) {
2612                                 printf("test %d(%s) %s: succeeded unexpectedly %d/%d\n",
2613                                        i, patn, "parallel",
2614                                        mstart, mlen);
2615                         }
2616                 } else if (tests[i].start != mstart ||
2617                            tests[i].len != mlen) {
2618                         printf("test %d(%s) %s: found %d/%d instead of %d/%d\n",
2619                                i, patn,
2620                                alg ? "backtracking" : "parallel",
2621                                mstart, mlen, tests[i].start, tests[i].len);
2622                         exit(1);
2623                 }
2624                 if (alg && tests[i].form && tests[i].replacement) {
2625                         char *new;
2626                         if (trace) {
2627                                 int j;
2628                                 printf("Backtrack:");
2629                                 for (j=0; j<st->record_count; j++)
2630                                         printf(" (%d,%d)", st->record[j].pos,
2631                                                st->record[j].len);
2632                                 printf("\n");
2633                         }
2634                         new = rxl_interp(st, tests[i].form);
2635                         if (!new || strcmp(new, tests[i].replacement) != 0) {
2636                                 printf("test %d(%s) replace is <%s>, not <%s>\n",
2637                                        i, patn,
2638                                        new, tests[i].replacement);
2639                                 exit(1);
2640                         }
2641                         free(new);
2642                 }
2643                 rxl_free_state(st);
2644         }
2645 }
2646
2647 static void usage(void)
2648 {
2649         fprintf(stderr, "Usage: rexel -itvB pattern target\n");
2650         fprintf(stderr, "     : rexel -itvB -f pattern file\n");
2651         fprintf(stderr, "     : rexel -T  # run tests\n");
2652         fprintf(stderr, "     : -i=ignore case, -t=trace -v=verbatim pattern, -B=backtrack\n");
2653 }
2654
2655 int main(int argc, char *argv[])
2656 {
2657         unsigned short *rxl;
2658         struct match_state *st;
2659         int flags;
2660         enum rxl_found r;
2661         int len;
2662         int start;
2663         int thelen;
2664         int used;
2665         int use_file = 0;
2666         int ccnt = 0;
2667         int ignore_case = 0;
2668         int verbatim = 0;
2669         int backtrack = 0;
2670         int opt;
2671         int trace = False;
2672         const char *patn, *target, *t;
2673         char prefix[100];
2674         int plen;
2675
2676         while ((opt = getopt(argc, argv, "itvTfB")) > 0)
2677                 switch (opt) {
2678                 case 'f':
2679                         use_file = 1; break;
2680                 case 'i':
2681                         ignore_case = 1; break;
2682                 case 'v':
2683                         verbatim = 1; break;
2684                 case 't':
2685                         trace = True; break;
2686                 case 'B':
2687                         backtrack = RXLF_BACKTRACK; break;
2688                 case 'T':
2689                         run_tests(trace);
2690                         printf("All tests passed successfully\n");
2691                         exit(0);
2692                 default:
2693                         usage();
2694                         exit(1);
2695                 }
2696
2697         if (optind + 2 != argc) {
2698                 usage();
2699                 exit(1);
2700         }
2701         patn = argv[optind];
2702         if (use_file) {
2703                 int fd = open(argv[optind+1], O_RDONLY);
2704                 struct stat stb;
2705                 if (fd < 0) {
2706                         perror(target);
2707                         exit(1);
2708                 }
2709                 fstat(fd, &stb);
2710                 target = mmap(NULL, stb.st_size, PROT_READ, MAP_SHARED, fd, 0);
2711                 close(fd);
2712         } else
2713                 target = argv[optind+1];
2714
2715         setlocale(LC_ALL, "");
2716         setlocale(LC_CTYPE, "enUS.UTF-8");
2717
2718         if (verbatim)
2719                 rxl = rxl_parse_verbatim(patn, ignore_case);
2720         else
2721                 rxl = rxl_parse(patn, &len, ignore_case);
2722
2723         if (!rxl) {
2724                 printf("Failed to parse: %s at %s\n", patn, patn+len);
2725                 exit(2);
2726         }
2727         rxl_print(rxl);
2728
2729         plen = rxl_prefix(rxl, prefix, sizeof(prefix)-1);
2730         if (plen)
2731                 printf("Prefix: \"%.*s\"\n", plen, prefix);
2732         else
2733                 printf("No static prefix\n");
2734
2735         st = rxl_prepare(rxl, backtrack);
2736         st->trace = trace;
2737         t = target;
2738         flags = RXL_SOL|RXL_SOD;
2739         do {
2740                 wint_t wc = get_utf8(&t, NULL);
2741                 if (wc >= WERR) {
2742                         rxl_advance(st, RXL_EOL|RXL_EOD);
2743                         break;
2744                 }
2745                 r = rxl_advance(st, wc | flags);
2746                 flags = 0;
2747                 ccnt+= 1;
2748         } while (r != RXL_DONE);
2749         rxl_info(st, &thelen, NULL, &start, NULL);
2750         if (thelen < 0)
2751                 printf("No match\n");
2752         else {
2753                 int j;
2754                 wint_t wc;
2755                 const char *tstart, *tend;
2756                 tstart = target;
2757                 if (use_file) {
2758                         tstart = target + start;
2759                         while (tstart > target && tstart[-1] != '\n')
2760                                 tstart--;
2761                         tend = tstart;
2762                         while (*tend && *tend != '\n')
2763                                 tend += 1;
2764                 } else {
2765                         tend = tstart + strlen(tstart);
2766                 }
2767                 printf("%0.*s\n", tend-tstart, tstart);
2768                 t = target;
2769                 ccnt = tstart-target;
2770                 while ((wc = get_utf8(&t, NULL)) < WERR) {
2771                         if (ccnt < start)
2772                                 putchar(' ');
2773                         else if (ccnt == start)
2774                                 putchar('^');
2775                         else if (ccnt < start + thelen)
2776                                 putchar('.');
2777                         ccnt += 1;
2778                         if (t >= tend)
2779                                 break;
2780                 }
2781                 putchar('\n');
2782         }
2783         rxl_free_state(st);
2784         exit(0);
2785 }
2786 #endif