RegularExpression.cxx 34.3 KB
Newer Older
1 2
/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file Copyright.txt or https://cmake.org/licensing#kwsys for details.  */
3 4 5
//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
6
// Permission is granted to any individual or institution to use, copy, modify
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
//
// Created: MNF 06/13/89  Initial Design and Implementation
// Updated: LGO 08/09/89  Inherit from Generic
// Updated: MBN 09/07/89  Added conditional exception handling
// Updated: MBN 12/15/89  Sprinkled "const" qualifiers all over the place!
// Updated: DLS 03/22/91  New lite version
//

22 23 24
#include "kwsysPrivate.h"
#include KWSYS_HEADER(RegularExpression.hxx)

25 26 27
// Work-around CMake dependency scanning limitation.  This must
// duplicate the above list of headers.
#if 0
28
#include "RegularExpression.hxx.in"
29 30
#endif

31
#include <stdio.h>
32
#include <string.h>
33

34
namespace KWSYS_NAMESPACE {
35 36

// RegularExpression -- Copies the given regular expression.
37 38 39
RegularExpression::RegularExpression(const RegularExpression& rxp)
{
  if (!rxp.program) {
40
    this->program = KWSYS_NULLPTR;
41
    return;
42
  }
43
  int ind;
44 45
  this->progsize = rxp.progsize;            // Copy regular expression size
  this->program = new char[this->progsize]; // Allocate storage
46
  for (ind = this->progsize; ind-- != 0;)   // Copy regular expression
47
    this->program[ind] = rxp.program[ind];
48 49 50
  // Copy pointers into last successful "find" operation
  this->regmatch = rxp.regmatch;
  this->regmust = rxp.regmust; // Copy field
51
  if (rxp.regmust != KWSYS_NULLPTR) {
52 53 54 55 56 57 58 59
    char* dum = rxp.program;
    ind = 0;
    while (dum != rxp.regmust) {
      ++dum;
      ++ind;
    }
    this->regmust = this->program + ind;
  }
60 61 62
  this->regstart = rxp.regstart; // Copy starting index
  this->reganch = rxp.reganch;   // Copy remaining private data
  this->regmlen = rxp.regmlen;   // Copy remaining private data
63 64
}

65
// operator= -- Copies the given regular expression.
66
RegularExpression& RegularExpression::operator=(const RegularExpression& rxp)
67
{
68
  if (this == &rxp) {
69
    return *this;
70 71
  }
  if (!rxp.program) {
72
    this->program = KWSYS_NULLPTR;
73
    return *this;
74
  }
75
  int ind;
76 77 78
  this->progsize = rxp.progsize; // Copy regular expression size
  delete[] this->program;
  this->program = new char[this->progsize]; // Allocate storage
79
  for (ind = this->progsize; ind-- != 0;)   // Copy regular expression
80
    this->program[ind] = rxp.program[ind];
81 82 83
  // Copy pointers into last successful "find" operation
  this->regmatch = rxp.regmatch;
  this->regmust = rxp.regmust; // Copy field
84
  if (rxp.regmust != KWSYS_NULLPTR) {
85 86 87 88 89 90 91 92
    char* dum = rxp.program;
    ind = 0;
    while (dum != rxp.regmust) {
      ++dum;
      ++ind;
    }
    this->regmust = this->program + ind;
  }
93 94 95
  this->regstart = rxp.regstart; // Copy starting index
  this->reganch = rxp.reganch;   // Copy remaining private data
  this->regmlen = rxp.regmlen;   // Copy remaining private data
96 97 98 99

  return *this;
}

100 101
// operator== -- Returns true if two regular expressions have the same
// compiled program for pattern matching.
102 103 104 105 106 107 108 109 110
bool RegularExpression::operator==(const RegularExpression& rxp) const
{
  if (this != &rxp) {         // Same address?
    int ind = this->progsize; // Get regular expression size
    if (ind != rxp.progsize)  // If different size regexp
      return false;           // Return failure
    while (ind-- != 0)        // Else while still characters
      if (this->program[ind] != rxp.program[ind]) // If regexp are different
        return false;                             // Return failure
111
  }
112
  return true; // Else same, return success
113 114 115 116 117
}

// deep_equal -- Returns true if have the same compiled regular expressions
// and the same start and end pointers.

118 119
bool RegularExpression::deep_equal(const RegularExpression& rxp) const
{
120 121 122
  int ind = this->progsize;                     // Get regular expression size
  if (ind != rxp.progsize)                      // If different size regexp
    return false;                               // Return failure
123 124
  while (ind-- != 0)                            // Else while still characters
    if (this->program[ind] != rxp.program[ind]) // If regexp are different
125
      return false;                             // Return failure
126 127 128
  // Else if same start/end ptrs, return true
  return (this->regmatch.start() == rxp.regmatch.start() &&
          this->regmatch.end() == rxp.regmatch.end());
129
}
130

131 132
// The remaining code in this file is derived from the regular expression code
// whose copyright statement appears below.  It has been changed to work
133 134 135
// with the class concepts of C++ and COOL.

/*
136
 * compile and find
137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196
 *
 *      Copyright (c) 1986 by University of Toronto.
 *      Written by Henry Spencer.  Not derived from licensed software.
 *
 *      Permission is granted to anyone to use this software for any
 *      purpose on any computer system, and to redistribute it freely,
 *      subject to the following restrictions:
 *
 *      1. The author is not responsible for the consequences of use of
 *              this software, no matter how awful, even if they arise
 *              from defects in it.
 *
 *      2. The origin of this software must not be misrepresented, either
 *              by explicit claim or by omission.
 *
 *      3. Altered versions must be plainly marked as such, and must not
 *              be misrepresented as being the original software.
 *
 * Beware that some of this code is subtly aware of the way operator
 * precedence is structured in regular expressions.  Serious changes in
 * regular-expression syntax might require a total rethink.
 */

/*
 * The "internal use only" fields in regexp.h are present to pass info from
 * compile to execute that permits the execute phase to run lots faster on
 * simple cases.  They are:
 *
 * regstart     char that must begin a match; '\0' if none obvious
 * reganch      is the match anchored (at beginning-of-line only)?
 * regmust      string (pointer into program) that match must include, or NULL
 * regmlen      length of regmust string
 *
 * Regstart and reganch permit very fast decisions on suitable starting points
 * for a match, cutting down the work a lot.  Regmust permits fast rejection
 * of lines that cannot possibly match.  The regmust tests are costly enough
 * that compile() supplies a regmust only if the r.e. contains something
 * potentially expensive (at present, the only such thing detected is * or +
 * at the start of the r.e., which can involve a lot of backup).  Regmlen is
 * supplied because the test in find() needs it and compile() is computing
 * it anyway.
 */

/*
 * Structure for regexp "program".  This is essentially a linear encoding
 * of a nondeterministic finite-state machine (aka syntax charts or
 * "railroad normal form" in parsing technology).  Each node is an opcode
 * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
 * all nodes except BRANCH implement concatenation; a "next" pointer with
 * a BRANCH on both ends of it is connecting two alternatives.  (Here we
 * have one of the subtle syntax dependencies:  an individual BRANCH (as
 * opposed to a collection of them) is never concatenated with anything
 * because of operator precedence.)  The operand of some types of node is
 * a literal string; for others, it is a node leading into a sub-FSM.  In
 * particular, the operand of a BRANCH node is the first node of the branch.
 * (NB this is *not* a tree structure:  the tail of the branch connects
 * to the thing following the set of BRANCHes.)  The opcodes are:
 */

// definition   number  opnd?   meaning
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214
#define END 0     // no   End of program.
#define BOL 1     // no   Match "" at beginning of line.
#define EOL 2     // no   Match "" at end of line.
#define ANY 3     // no   Match any one character.
#define ANYOF 4   // str  Match any character in this string.
#define ANYBUT 5  // str  Match any character not in this
                  // string.
#define BRANCH 6  // node Match this alternative, or the
                  // next...
#define BACK 7    // no   Match "", "next" ptr points backward.
#define EXACTLY 8 // str  Match this string.
#define NOTHING 9 // no   Match empty string.
#define STAR 10   // node Match this (simple) thing 0 or more
                  // times.
#define PLUS 11   // node Match this (simple) thing 1 or more
                  // times.
#define OPEN 20   // no   Mark this point in input as start of
                  // #n.
215
// OPEN+1 is number 1, etc.
216
#define CLOSE 30 // no   Analogous to OPEN.
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250

/*
 * Opcode notes:
 *
 * BRANCH       The set of branches constituting a single choice are hooked
 *              together with their "next" pointers, since precedence prevents
 *              anything being concatenated to any individual branch.  The
 *              "next" pointer of the last BRANCH in a choice points to the
 *              thing following the whole choice.  This is also where the
 *              final "next" pointer of each individual branch points; each
 *              branch starts with the operand node of a BRANCH node.
 *
 * BACK         Normal "next" pointers all implicitly point forward; BACK
 *              exists to make loop structures possible.
 *
 * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
 *              BRANCH structures using BACK.  Simple cases (one character
 *              per match) are implemented with STAR and PLUS for speed
 *              and to minimize recursive plunges.
 *
 * OPEN,CLOSE   ...are numbered at compile time.
 */

/*
 * A node is one char of opcode followed by two chars of "next" pointer.
 * "Next" pointers are stored as two 8-bit pieces, high order first.  The
 * value is a positive offset from the opcode of the node containing it.
 * An operand, if any, simply follows the node.  (Note that much of the
 * code generation knows about this implicit relationship.)
 *
 * Using two bytes for the "next" pointer is vast overkill for most things,
 * but allows patterns to get big without disasters.
 */

251 252 253
#define OP(p) (*(p))
#define NEXT(p) (((*((p) + 1) & 0377) << 8) + (*((p) + 2) & 0377))
#define OPERAND(p) ((p) + 3)
254 255 256 257 258 259

const unsigned char MAGIC = 0234;
/*
 * Utility definitions.
 */

260
#define UCHARAT(p) (reinterpret_cast<const unsigned char*>(p))[0]
261

262 263
#define ISMULT(c) ((c) == '*' || (c) == '+' || (c) == '?')
#define META "^$.[()|?+*\\"
264 265 266 267

/*
 * Flags to be passed up and down.
 */
268 269 270 271
#define HASWIDTH 01 // Known never to match null string.
#define SIMPLE 02   // Simple enough to be STAR/PLUS operand.
#define SPSTART 04  // Starts with * or +.
#define WORST 0     // Worst case.
272 273 274 275 276 277 278 279

/////////////////////////////////////////////////////////////////////////
//
//  COMPILE AND ASSOCIATED FUNCTIONS
//
/////////////////////////////////////////////////////////////////////////

/*
280
 * Read only utility variables.
281
 */
282
static char regdummy;
283
static char* const regdummyptr = &regdummy;
284 285

/*
286
 * Utility class for RegularExpression::compile().
287
 */
288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306
class RegExpCompile
{
public:
  const char* regparse; // Input-scan pointer.
  int regnpar;          // () count.
  char* regcode;        // Code-emit pointer; regdummyptr = don't.
  long regsize;         // Code size.

  char* reg(int, int*);
  char* regbranch(int*);
  char* regpiece(int*);
  char* regatom(int*);
  char* regnode(char);
  void regc(char);
  void reginsert(char, char*);
  static void regtail(char*, const char*);
  static void regoptail(char*, const char*);
};

307 308
static const char* regnext(const char*);
static char* regnext(char*);
309 310

#ifdef STRCSPN
311
static int strcspn();
312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330
#endif

/*
 * We can't allocate space until we know how big the compiled form will be,
 * but we can't compile it (and thus know how big it is) until we've got a
 * place to put the code.  So we cheat:  we compile it twice, once with code
 * generation turned off and size counting turned on, and once "for real".
 * This also means that we don't allocate space until we are sure that the
 * thing really will compile successfully, and we never have to move the
 * code and thus invalidate pointers into it.  (Note that it has to be in
 * one piece because free() must be able to free it all.)
 *
 * Beware that the optimization-preparation code in here knows about some
 * of the structure of the compiled regexp.
 */

// compile -- compile a regular expression into internal code
// for later pattern matching.

331 332 333 334 335 336 337
bool RegularExpression::compile(const char* exp)
{
  const char* scan;
  const char* longest;
  size_t len;
  int flags;

338
  if (exp == KWSYS_NULLPTR) {
339 340 341 342
    // RAISE Error, SYM(RegularExpression), SYM(No_Expr),
    printf("RegularExpression::compile(): No expression supplied.\n");
    return false;
  }
343

344
  // First pass: determine size, legality.
345 346 347 348 349 350 351
  RegExpCompile comp;
  comp.regparse = exp;
  comp.regnpar = 1;
  comp.regsize = 0L;
  comp.regcode = regdummyptr;
  comp.regc(static_cast<char>(MAGIC));
  if (!comp.reg(0, &flags)) {
352 353 354
    printf("RegularExpression::compile(): Error in compile.\n");
    return false;
  }
355
  this->regmatch.clear();
356

357
  // Small enough for pointer-storage convention?
358
  if (comp.regsize >= 32767L) { // Probably could be 65535L.
359 360 361 362
    // RAISE Error, SYM(RegularExpression), SYM(Expr_Too_Big),
    printf("RegularExpression::compile(): Expression too big.\n");
    return false;
  }
363

364 365
  // Allocate space.
  //#ifndef _WIN32
366
  if (this->program != KWSYS_NULLPTR)
367 368
    delete[] this->program;
  //#endif
369 370
  this->program = new char[comp.regsize];
  this->progsize = static_cast<int>(comp.regsize);
371

372
  if (this->program == KWSYS_NULLPTR) {
373 374 375 376
    // RAISE Error, SYM(RegularExpression), SYM(Out_Of_Memory),
    printf("RegularExpression::compile(): Out of memory.\n");
    return false;
  }
377

378
  // Second pass: emit code.
379 380 381 382 383
  comp.regparse = exp;
  comp.regnpar = 1;
  comp.regcode = this->program;
  comp.regc(static_cast<char>(MAGIC));
  comp.reg(0, &flags);
384 385 386 387

  // Dig out information for optimizations.
  this->regstart = '\0'; // Worst-case defaults.
  this->reganch = 0;
388
  this->regmust = KWSYS_NULLPTR;
389 390 391 392 393 394 395 396 397 398
  this->regmlen = 0;
  scan = this->program + 1;       // First BRANCH.
  if (OP(regnext(scan)) == END) { // Only one top-level choice.
    scan = OPERAND(scan);

    // Starting-point info.
    if (OP(scan) == EXACTLY)
      this->regstart = *OPERAND(scan);
    else if (OP(scan) == BOL)
      this->reganch++;
399

400 401 402 403 404 405 406 407 408
    //
    // If there's something expensive in the r.e., find the longest
    // literal string that must appear and make it the regmust.  Resolve
    // ties in favor of later strings, since the regstart check works
    // with the beginning of the r.e. and avoiding duplication
    // strengthens checking.  Not a strong reason, but sufficient in the
    // absence of others.
    //
    if (flags & SPSTART) {
409
      longest = KWSYS_NULLPTR;
410
      len = 0;
411
      for (; scan != KWSYS_NULLPTR; scan = regnext(scan))
412 413 414
        if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
          longest = OPERAND(scan);
          len = strlen(OPERAND(scan));
415
        }
416 417
      this->regmust = longest;
      this->regmlen = len;
418
    }
419 420
  }
  return true;
421 422 423 424 425 426 427 428 429 430 431
}

/*
 - reg - regular expression, i.e. main body or parenthesized thing
 *
 * Caller must absorb opening parenthesis.
 *
 * Combining parenthesis handling with the base level of regular expression
 * is a trifle forced, but the need to tie the tails of the branches to what
 * follows makes it hard to avoid.
 */
432
char* RegExpCompile::reg(int paren, int* flagp)
433 434 435 436 437 438 439 440 441 442 443
{
  char* ret;
  char* br;
  char* ender;
  int parno = 0;
  int flags;

  *flagp = HASWIDTH; // Tentatively.

  // Make an OPEN node, if parenthesized.
  if (paren) {
444
    if (regnpar >= RegularExpressionMatch::NSUBEXP) {
445 446
      // RAISE Error, SYM(RegularExpression), SYM(Too_Many_Parens),
      printf("RegularExpression::compile(): Too many parentheses.\n");
447
      return KWSYS_NULLPTR;
448
    }
449 450 451 452
    parno = regnpar;
    regnpar++;
    ret = regnode(static_cast<char>(OPEN + parno));
  } else
453
    ret = KWSYS_NULLPTR;
454 455 456

  // Pick up the branches, linking them together.
  br = regbranch(&flags);
457 458 459
  if (br == KWSYS_NULLPTR)
    return (KWSYS_NULLPTR);
  if (ret != KWSYS_NULLPTR)
460 461 462 463 464 465 466 467
    regtail(ret, br); // OPEN -> first.
  else
    ret = br;
  if (!(flags & HASWIDTH))
    *flagp &= ~HASWIDTH;
  *flagp |= flags & SPSTART;
  while (*regparse == '|') {
    regparse++;
468
    br = regbranch(&flags);
469 470
    if (br == KWSYS_NULLPTR)
      return (KWSYS_NULLPTR);
471
    regtail(ret, br); // BRANCH -> BRANCH.
472
    if (!(flags & HASWIDTH))
473
      *flagp &= ~HASWIDTH;
474
    *flagp |= flags & SPSTART;
475
  }
476

477 478 479 480 481
  // Make a closing node, and hook it on the end.
  ender = regnode(static_cast<char>((paren) ? CLOSE + parno : END));
  regtail(ret, ender);

  // Hook the tails of the branches to the closing node.
482
  for (br = ret; br != KWSYS_NULLPTR; br = regnext(br))
483 484 485 486 487 488
    regoptail(br, ender);

  // Check for proper termination.
  if (paren && *regparse++ != ')') {
    // RAISE Error, SYM(RegularExpression), SYM(Unmatched_Parens),
    printf("RegularExpression::compile(): Unmatched parentheses.\n");
489
    return KWSYS_NULLPTR;
490 491 492 493
  } else if (!paren && *regparse != '\0') {
    if (*regparse == ')') {
      // RAISE Error, SYM(RegularExpression), SYM(Unmatched_Parens),
      printf("RegularExpression::compile(): Unmatched parentheses.\n");
494
      return KWSYS_NULLPTR;
495 496 497
    } else {
      // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
      printf("RegularExpression::compile(): Internal error.\n");
498
      return KWSYS_NULLPTR;
499
    }
500 501 502
    // NOTREACHED
  }
  return (ret);
503 504 505 506 507 508 509
}

/*
 - regbranch - one alternative of an | operator
 *
 * Implements the concatenation operator.
 */
510
char* RegExpCompile::regbranch(int* flagp)
511 512 513 514 515 516 517 518 519
{
  char* ret;
  char* chain;
  char* latest;
  int flags;

  *flagp = WORST; // Tentatively.

  ret = regnode(BRANCH);
520
  chain = KWSYS_NULLPTR;
521 522
  while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
    latest = regpiece(&flags);
523 524
    if (latest == KWSYS_NULLPTR)
      return (KWSYS_NULLPTR);
525
    *flagp |= flags & HASWIDTH;
526
    if (chain == KWSYS_NULLPTR) // First piece.
527 528 529 530 531
      *flagp |= flags & SPSTART;
    else
      regtail(chain, latest);
    chain = latest;
  }
532
  if (chain == KWSYS_NULLPTR) // Loop ran zero times.
533
    regnode(NOTHING);
534

535
  return (ret);
536 537 538 539 540 541 542 543 544 545 546
}

/*
 - regpiece - something followed by possible [*+?]
 *
 * Note that the branching code sequences used for ? and the general cases
 * of * and + are somewhat optimized:  they use the same NOTHING node as
 * both the endmarker for their branch list and the body of the last branch.
 * It might seem that this node could be dispensed with entirely, but the
 * endmarker role is not redundant.
 */
547
char* RegExpCompile::regpiece(int* flagp)
548 549 550 551 552
{
  char* ret;
  char op;
  char* next;
  int flags;
553

554
  ret = regatom(&flags);
555 556
  if (ret == KWSYS_NULLPTR)
    return (KWSYS_NULLPTR);
557

558 559 560
  op = *regparse;
  if (!ISMULT(op)) {
    *flagp = flags;
561
    return (ret);
562
  }
563

564 565 566
  if (!(flags & HASWIDTH) && op != '?') {
    // RAISE Error, SYM(RegularExpression), SYM(Empty_Operand),
    printf("RegularExpression::compile() : *+ operand could be empty.\n");
567
    return KWSYS_NULLPTR;
568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600
  }
  *flagp = (op != '+') ? (WORST | SPSTART) : (WORST | HASWIDTH);

  if (op == '*' && (flags & SIMPLE))
    reginsert(STAR, ret);
  else if (op == '*') {
    // Emit x* as (x&|), where & means "self".
    reginsert(BRANCH, ret);         // Either x
    regoptail(ret, regnode(BACK));  // and loop
    regoptail(ret, ret);            // back
    regtail(ret, regnode(BRANCH));  // or
    regtail(ret, regnode(NOTHING)); // null.
  } else if (op == '+' && (flags & SIMPLE))
    reginsert(PLUS, ret);
  else if (op == '+') {
    // Emit x+ as x(&|), where & means "self".
    next = regnode(BRANCH); // Either
    regtail(ret, next);
    regtail(regnode(BACK), ret);    // loop back
    regtail(next, regnode(BRANCH)); // or
    regtail(ret, regnode(NOTHING)); // null.
  } else if (op == '?') {
    // Emit x? as (x|)
    reginsert(BRANCH, ret);        // Either x
    regtail(ret, regnode(BRANCH)); // or
    next = regnode(NOTHING);       // null.
    regtail(ret, next);
    regoptail(ret, next);
  }
  regparse++;
  if (ISMULT(*regparse)) {
    // RAISE Error, SYM(RegularExpression), SYM(Nested_Operand),
    printf("RegularExpression::compile(): Nested *?+.\n");
601
    return KWSYS_NULLPTR;
602 603 604
  }
  return (ret);
}
605 606 607 608 609 610 611 612 613

/*
 - regatom - the lowest level
 *
 * Optimization:  gobbles an entire sequence of ordinary characters so that
 * it can turn them into a single node, which is smaller to store and
 * faster to run.  Backslashed characters are exceptions, each becoming a
 * separate node; the code is simpler that way and it's not worth fixing.
 */
614
char* RegExpCompile::regatom(int* flagp)
615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653
{
  char* ret;
  int flags;

  *flagp = WORST; // Tentatively.

  switch (*regparse++) {
    case '^':
      ret = regnode(BOL);
      break;
    case '$':
      ret = regnode(EOL);
      break;
    case '.':
      ret = regnode(ANY);
      *flagp |= HASWIDTH | SIMPLE;
      break;
    case '[': {
      int rxpclass;
      int rxpclassend;

      if (*regparse == '^') { // Complement of range.
        ret = regnode(ANYBUT);
        regparse++;
      } else
        ret = regnode(ANYOF);
      if (*regparse == ']' || *regparse == '-')
        regc(*regparse++);
      while (*regparse != '\0' && *regparse != ']') {
        if (*regparse == '-') {
          regparse++;
          if (*regparse == ']' || *regparse == '\0')
            regc('-');
          else {
            rxpclass = UCHARAT(regparse - 2) + 1;
            rxpclassend = UCHARAT(regparse);
            if (rxpclass > rxpclassend + 1) {
              // RAISE Error, SYM(RegularExpression), SYM(Invalid_Range),
              printf("RegularExpression::compile(): Invalid range in [].\n");
654
              return KWSYS_NULLPTR;
655
            }
656 657 658 659 660 661 662 663 664 665 666
            for (; rxpclass <= rxpclassend; rxpclass++)
              regc(static_cast<char>(rxpclass));
            regparse++;
          }
        } else
          regc(*regparse++);
      }
      regc('\0');
      if (*regparse != ']') {
        // RAISE Error, SYM(RegularExpression), SYM(Unmatched_Bracket),
        printf("RegularExpression::compile(): Unmatched [].\n");
667
        return KWSYS_NULLPTR;
668 669 670 671 672 673
      }
      regparse++;
      *flagp |= HASWIDTH | SIMPLE;
    } break;
    case '(':
      ret = reg(1, &flags);
674 675
      if (ret == KWSYS_NULLPTR)
        return (KWSYS_NULLPTR);
676 677 678 679 680 681 682
      *flagp |= flags & (HASWIDTH | SPSTART);
      break;
    case '\0':
    case '|':
    case ')':
      // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
      printf("RegularExpression::compile(): Internal error.\n"); // Never here
683
      return KWSYS_NULLPTR;
684 685 686 687 688
    case '?':
    case '+':
    case '*':
      // RAISE Error, SYM(RegularExpression), SYM(No_Operand),
      printf("RegularExpression::compile(): ?+* follows nothing.\n");
689
      return KWSYS_NULLPTR;
690 691 692 693
    case '\\':
      if (*regparse == '\0') {
        // RAISE Error, SYM(RegularExpression), SYM(Trailing_Backslash),
        printf("RegularExpression::compile(): Trailing backslash.\n");
694
        return KWSYS_NULLPTR;
695 696 697 698 699 700 701 702 703 704 705 706 707 708 709
      }
      ret = regnode(EXACTLY);
      regc(*regparse++);
      regc('\0');
      *flagp |= HASWIDTH | SIMPLE;
      break;
    default: {
      int len;
      char ender;

      regparse--;
      len = int(strcspn(regparse, META));
      if (len <= 0) {
        // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
        printf("RegularExpression::compile(): Internal error.\n");
710
        return KWSYS_NULLPTR;
711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726
      }
      ender = *(regparse + len);
      if (len > 1 && ISMULT(ender))
        len--; // Back off clear of ?+* operand.
      *flagp |= HASWIDTH;
      if (len == 1)
        *flagp |= SIMPLE;
      ret = regnode(EXACTLY);
      while (len > 0) {
        regc(*regparse++);
        len--;
      }
      regc('\0');
    } break;
  }
  return (ret);
727 728 729 730 731 732
}

/*
 - regnode - emit a node
   Location.
 */
733
char* RegExpCompile::regnode(char op)
734 735 736
{
  char* ret;
  char* ptr;
737

738
  ret = regcode;
739
  if (ret == regdummyptr) {
740
    regsize += 3;
741
    return (ret);
742 743 744 745 746 747 748
  }

  ptr = ret;
  *ptr++ = op;
  *ptr++ = '\0'; // Null "next" pointer.
  *ptr++ = '\0';
  regcode = ptr;
749

750 751
  return (ret);
}
752 753 754 755

/*
 - regc - emit (if appropriate) a byte of code
 */
756
void RegExpCompile::regc(char b)
757
{
758
  if (regcode != regdummyptr)
759 760 761
    *regcode++ = b;
  else
    regsize++;
762 763 764 765 766 767 768
}

/*
 - reginsert - insert an operator in front of already-emitted operand
 *
 * Means relocating the operand.
 */
769
void RegExpCompile::reginsert(char op, char* opnd)
770 771 772 773
{
  char* src;
  char* dst;
  char* place;
774

775
  if (regcode == regdummyptr) {
776 777 778
    regsize += 3;
    return;
  }
779

780 781 782 783 784
  src = regcode;
  regcode += 3;
  dst = regcode;
  while (src > opnd)
    *--dst = *--src;
785

786 787 788 789 790
  place = opnd; // Op node, where operand used to be.
  *place++ = op;
  *place++ = '\0';
  *place = '\0';
}
791 792 793 794

/*
 - regtail - set the next-pointer at the end of a node chain
 */
795
void RegExpCompile::regtail(char* p, const char* val)
796 797 798 799
{
  char* scan;
  char* temp;
  int offset;
800

801
  if (p == regdummyptr)
802
    return;
803

804 805 806 807
  // Find last node.
  scan = p;
  for (;;) {
    temp = regnext(scan);
808
    if (temp == KWSYS_NULLPTR)
809 810 811 812 813 814 815 816 817 818 819
      break;
    scan = temp;
  }

  if (OP(scan) == BACK)
    offset = int(scan - val);
  else
    offset = int(val - scan);
  *(scan + 1) = static_cast<char>((offset >> 8) & 0377);
  *(scan + 2) = static_cast<char>(offset & 0377);
}
820 821 822 823

/*
 - regoptail - regtail on operand of first argument; nop if operandless
 */
824
void RegExpCompile::regoptail(char* p, const char* val)
825 826
{
  // "Operandless" and "op != BRANCH" are synonymous in practice.
827
  if (p == KWSYS_NULLPTR || p == regdummyptr || OP(p) != BRANCH)
828 829
    return;
  regtail(OPERAND(p), val);
830 831 832
}

////////////////////////////////////////////////////////////////////////
833
//
834
//  find and friends
835
//
836 837 838
////////////////////////////////////////////////////////////////////////

/*
839
 * Utility class for RegularExpression::find().
840
 */
841 842 843 844 845 846 847 848 849 850 851 852
class RegExpFind
{
public:
  const char* reginput;   // String-input pointer.
  const char* regbol;     // Beginning of input, for ^ check.
  const char** regstartp; // Pointer to startp array.
  const char** regendp;   // Ditto for endp.

  int regtry(const char*, const char**, const char**, const char*);
  int regmatch(const char*);
  int regrepeat(const char*);
};
853 854 855

// find -- Matches the regular expression to the given string.
// Returns true if found, and sets start and end indexes accordingly.
856 857
bool RegularExpression::find(char const* string,
                             RegularExpressionMatch& rmatch) const
858 859
{
  const char* s;
860

861 862
  rmatch.clear();
  rmatch.searchstring = string;
863

864 865 866
  if (!this->program) {
    return false;
  }
867

868 869 870 871 872
  // Check validity of program.
  if (UCHARAT(this->program) != MAGIC) {
    // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
    printf(
      "RegularExpression::find(): Compiled regular expression corrupted.\n");
873
    return false;
874
  }
875

876
  // If there is a "must appear" string, look for it.
877
  if (this->regmust != KWSYS_NULLPTR) {
878
    s = string;
879
    while ((s = strchr(s, this->regmust[0])) != KWSYS_NULLPTR) {
880 881 882
      if (strncmp(s, this->regmust, this->regmlen) == 0)
        break; // Found it.
      s++;
883
    }
884
    if (s == KWSYS_NULLPTR) // Not present.
885
      return false;
886
  }
887

888 889
  RegExpFind regFind;

890
  // Mark beginning of line for ^ .
891
  regFind.regbol = string;
892

893 894
  // Simplest case:  anchored match need be tried only once.
  if (this->reganch)
895 896
    return (
      regFind.regtry(string, rmatch.startp, rmatch.endp, this->program) != 0);
897

898 899 900 901
  // Messy cases:  unanchored match.
  s = string;
  if (this->regstart != '\0')
    // We know what char it must start with.
902
    while ((s = strchr(s, this->regstart)) != KWSYS_NULLPTR) {
903
      if (regFind.regtry(s, rmatch.startp, rmatch.endp, this->program))
904
        return true;
905 906 907 908 909
      s++;
    }
  else
    // We don't -- general case.
    do {
910 911
      if (regFind.regtry(s, rmatch.startp, rmatch.endp, this->program))
        return true;
912
    } while (*s++ != '\0');
913

914
  // Failure.
915
  return false;
916 917 918 919 920 921
}

/*
 - regtry - try match at specific point
   0 failure, 1 success
 */
922 923
int RegExpFind::regtry(const char* string, const char** start,
                       const char** end, const char* prog)
924 925 926 927 928 929 930 931 932 933 934
{
  int i;
  const char** sp1;
  const char** ep;

  reginput = string;
  regstartp = start;
  regendp = end;

  sp1 = start;
  ep = end;
935
  for (i = RegularExpressionMatch::NSUBEXP; i > 0; i--) {
936 937
    *sp1++ = KWSYS_NULLPTR;
    *ep++ = KWSYS_NULLPTR;
938 939 940 941 942 943 944
  }
  if (regmatch(prog + 1)) {
    start[0] = string;
    end[0] = reginput;
    return (1);
  } else
    return (0);
945 946 947 948 949 950 951 952 953 954 955 956 957
}

/*
 - regmatch - main matching routine
 *
 * Conceptually the strategy is simple:  check to see whether the current
 * node matches, call self recursively to see whether the rest matches,
 * and then act accordingly.  In practice we make some effort to avoid
 * recursion, in particular by going through "ordinary" nodes (that don't
 * need to know whether the rest of the match failed) by a loop instead of
 * by recursion.
 * 0 failure, 1 success
 */
958
int RegExpFind::regmatch(const char* prog)
959 960 961 962 963 964
{
  const char* scan; // Current node.
  const char* next; // Next node.

  scan = prog;

965
  while (scan != KWSYS_NULLPTR) {
966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996

    next = regnext(scan);

    switch (OP(scan)) {
      case BOL:
        if (reginput != regbol)
          return (0);
        break;
      case EOL:
        if (*reginput != '\0')
          return (0);
        break;
      case ANY:
        if (*reginput == '\0')
          return (0);
        reginput++;
        break;
      case EXACTLY: {
        size_t len;
        const char* opnd;

        opnd = OPERAND(scan);
        // Inline the first character, for speed.
        if (*opnd != *reginput)
          return (0);
        len = strlen(opnd);
        if (len > 1 && strncmp(opnd, reginput, len) != 0)
          return (0);
        reginput += len;
      } break;
      case ANYOF:
997 998
        if (*reginput == '\0' ||
            strchr(OPERAND(scan), *reginput) == KWSYS_NULLPTR)
999 1000 1001 1002
          return (0);
        reginput++;
        break;
      case ANYBUT:
1003 1004
        if (*reginput == '\0' ||
            strchr(OPERAND(scan), *reginput) != KWSYS_NULLPTR)
1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032
          return (0);
        reginput++;
        break;
      case NOTHING:
        break;
      case BACK:
        break;
      case OPEN + 1:
      case OPEN + 2:
      case OPEN + 3:
      case OPEN + 4:
      case OPEN + 5:
      case OPEN + 6:
      case OPEN + 7:
      case OPEN + 8:
      case OPEN + 9: {
        int no;
        const char* save;

        no = OP(scan) - OPEN;
        save = reginput;

        if (regmatch(next)) {

          //
          // Don't set startp if some later invocation of the
          // same parentheses already has.
          //
1033
          if (regstartp[no] == KWSYS_NULLPTR)
1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060
            regstartp[no] = save;
          return (1);
        } else
          return (0);
      }
      //              break;
      case CLOSE + 1:
      case CLOSE + 2:
      case CLOSE + 3:
      case CLOSE + 4:
      case CLOSE + 5:
      case CLOSE + 6:
      case CLOSE + 7:
      case CLOSE + 8:
      case CLOSE + 9: {
        int no;
        const char* save;

        no = OP(scan) - CLOSE;
        save = reginput;

        if (regmatch(next)) {

          //
          // Don't set endp if some later invocation of the
          // same parentheses already has.
          //
1061
          if (regendp[no] == KWSYS_NULLPTR)
1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080
            regendp[no] = save;
          return (1);
        } else
          return (0);
      }
      //              break;
      case BRANCH: {

        const char* save;

        if (OP(next) != BRANCH) // No choice.
          next = OPERAND(scan); // Avoid recursion.
        else {
          do {
            save = reginput;
            if (regmatch(OPERAND(scan)))
              return (1);
            reginput = save;
            scan = regnext(scan);
1081
          } while (scan != KWSYS_NULLPTR && OP(scan) == BRANCH);
1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110
          return (0);
          // NOTREACHED
        }
      } break;
      case STAR:
      case PLUS: {
        char nextch;
        int no;
        const char* save;
        int min_no;

        //
        // Lookahead to avoid useless match attempts when we know
        // what character comes next.
        //
        nextch = '\0';
        if (OP(next) == EXACTLY)
          nextch = *OPERAND(next);
        min_no = (OP(scan) == STAR) ? 0 : 1;
        save = reginput;
        no = regrepeat(OPERAND(scan));
        while (no >= min_no) {
          // If it could work, try it.
          if (nextch == '\0' || *reginput == nextch)
            if (regmatch(next))
              return (1);
          // Couldn't or didn't -- back up.
          no--;
          reginput = save + no;
1111
        }
1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122
        return (0);
      }
      //              break;
      case END:
        return (1); // Success!

      default:
        // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
        printf(
          "RegularExpression::find(): Internal error -- memory corrupted.\n");
        return 0;
1123
    }
1124 1125
    scan = next;
  }
1126

1127 1128 1129 1130 1131 1132 1133
  //
  //  We get here only if there's trouble -- normally "case END" is the
  //  terminating point.
  //
  // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
  printf("RegularExpression::find(): Internal error -- corrupted pointers.\n");
  return (0);
1134 1135 1136 1137 1138
}

/*
 - regrepeat - repeatedly match something simple, report how many
 */
1139
int RegExpFind::regrepeat(const char* p)
1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158
{
  int count = 0;
  const char* scan;
  const char* opnd;

  scan = reginput;
  opnd = OPERAND(p);
  switch (OP(p)) {
    case ANY:
      count = int(strlen(scan));
      scan += count;
      break;
    case EXACTLY:
      while (*opnd == *scan) {
        count++;
        scan++;
      }
      break;
    case ANYOF:
1159
      while (*scan != '\0' && strchr(opnd, *scan) != KWSYS_NULLPTR) {
1160 1161 1162 1163 1164
        count++;
        scan++;
      }
      break;
    case ANYBUT:
1165
      while (*scan != '\0' && strchr(opnd, *scan) == KWSYS_NULLPTR) {
1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176
        count++;
        scan++;
      }
      break;
    default: // Oh dear.  Called inappropriately.
      // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
      printf("cm RegularExpression::find(): Internal error.\n");
      return 0;
  }
  reginput = scan;
  return (count);
1177 1178 1179 1180 1181
}

/*
 - regnext - dig the "next" pointer out of a node
 */
1182 1183 1184
static const char* regnext(const char* p)
{
  int offset;
1185

1186
  if (p == regdummyptr)
1187
    return (KWSYS_NULLPTR);
1188

1189 1190
  offset = NEXT(p);
  if (offset == 0)
1191
    return (KWSYS_NULLPTR);
1192

1193 1194 1195 1196
  if (OP(p) == BACK)
    return (p - offset);
  else
    return (p + offset);
1197 1198
}

1199 1200 1201
static char* regnext(char* p)
{
  int offset;
1202

1203
  if (p == regdummyptr)
1204
    return (KWSYS_NULLPTR);
1205

1206 1207
  offset = NEXT(p);
  if (offset == 0)
1208
    return (KWSYS_NULLPTR);
1209

1210 1211 1212 1213
  if (OP(p) == BACK)
    return (p - offset);
  else
    return (p + offset);
1214 1215 1216
}

} // namespace KWSYS_NAMESPACE