Debian Codegraph @

Utilities/KWSys/RegularExpression.cxx

raw
1 /* Distributed under the OSI-approved BSD 3-Clause License. See accompanying
2 file Copyright.txt or https://cmake.org/licensing#kwsys for details. */
3 //
4 // Copyright (C) 1991 Texas Instruments Incorporated.
5 //
6 // Permission is granted to any individual or institution to use, copy, modify
7 // and distribute this software, provided that this complete copyright and
8 // permission notice is maintained, intact, in all copies and supporting
9 // documentation.
10 //
11 // Texas Instruments Incorporated provides this software "as is" without
12 // express or implied warranty.
13 //
14 //
15 // Created: MNF 06/13/89 Initial Design and Implementation
16 // Updated: LGO 08/09/89 Inherit from Generic
17 // Updated: MBN 09/07/89 Added conditional exception handling
18 // Updated: MBN 12/15/89 Sprinkled "const" qualifiers all over the place!
19 // Updated: DLS 03/22/91 New lite version
20 //
21
22 #include "kwsysPrivate.h"
23 #include KWSYS_HEADER(RegularExpression.hxx)
24
25 // Work-around CMake dependency scanning limitation. This must
26 // duplicate the above list of headers.
27 #if 0
28 # include "RegularExpression.hxx.in"
29 #endif
30
31 #include <cstdio>
32 #include <cstring>
33
34 namespace KWSYS_NAMESPACE {
35
36 // RegularExpression -- Copies the given regular expression.
37 RegularExpression::RegularExpression(const RegularExpression& rxp)
38 {
39 if (!rxp.program) {
40 this->program = nullptr;
41 return;
42 }
43 int ind;
44 this->progsize = rxp.progsize; // Copy regular expression size
45 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 // Copy pointers into last successful "find" operation
49 this->regmatch = rxp.regmatch;
50 this->regmust = rxp.regmust; // Copy field
51 if (rxp.regmust != nullptr) {
52 char* dum = rxp.program;
53 ind = 0;
54 while (dum != rxp.regmust) {
55 ++dum;
56 ++ind;
57 }
58 this->regmust = this->program + ind;
59 }
60 this->regstart = rxp.regstart; // Copy starting index
61 this->reganch = rxp.reganch; // Copy remaining private data
62 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 = nullptr;
73 return *this;
74 }
75 int ind;
76 this->progsize = rxp.progsize; // Copy regular expression size
77 delete[] this->program;
78 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 // Copy pointers into last successful "find" operation
82 this->regmatch = rxp.regmatch;
83 this->regmust = rxp.regmust; // Copy field
84 if (rxp.regmust != nullptr) {
85 char* dum = rxp.program;
86 ind = 0;
87 while (dum != rxp.regmust) {
88 ++dum;
89 ++ind;
90 }
91 this->regmust = this->program + ind;
92 }
93 this->regstart = rxp.regstart; // Copy starting index
94 this->reganch = rxp.reganch; // Copy remaining private data
95 this->regmlen = rxp.regmlen; // Copy remaining private data
96
97 return *this;
98 }
99
100 // operator== -- Returns true if two regular expressions have the same
101 // compiled program for pattern matching.
102 bool RegularExpression::operator==(const RegularExpression& rxp) const
103 {
104 if (this != &rxp) { // Same address?
105 int ind = this->progsize; // Get regular expression size
106 if (ind != rxp.progsize) // If different size regexp
107 return false; // Return failure
108 while (ind-- != 0) // Else while still characters
109 if (this->program[ind] != rxp.program[ind]) // If regexp are different
110 return false; // Return failure
111 }
112 return true; // Else same, return success
113 }
114
115 // deep_equal -- Returns true if have the same compiled regular expressions
116 // and the same start and end pointers.
117
118 bool RegularExpression::deep_equal(const RegularExpression& rxp) const
119 {
120 int ind = this->progsize; // Get regular expression size
121 if (ind != rxp.progsize) // If different size regexp
122 return false; // Return failure
123 while (ind-- != 0) // Else while still characters
124 if (this->program[ind] != rxp.program[ind]) // If regexp are different
125 return false; // Return failure
126 // Else if same start/end ptrs, return true
127 return (this->regmatch.start() == rxp.regmatch.start() &&
128 this->regmatch.end() == rxp.regmatch.end());
129 }
130
131 // The remaining code in this file is derived from the regular expression code
132 // whose copyright statement appears below. It has been changed to work
133 // with the class concepts of C++ and COOL.
134
135 /*
136 * compile and find
137 *
138 * Copyright (c) 1986 by University of Toronto.
139 * Written by Henry Spencer. Not derived from licensed software.
140 *
141 * Permission is granted to anyone to use this software for any
142 * purpose on any computer system, and to redistribute it freely,
143 * subject to the following restrictions:
144 *
145 * 1. The author is not responsible for the consequences of use of
146 * this software, no matter how awful, even if they arise
147 * from defects in it.
148 *
149 * 2. The origin of this software must not be misrepresented, either
150 * by explicit claim or by omission.
151 *
152 * 3. Altered versions must be plainly marked as such, and must not
153 * be misrepresented as being the original software.
154 *
155 * Beware that some of this code is subtly aware of the way operator
156 * precedence is structured in regular expressions. Serious changes in
157 * regular-expression syntax might require a total rethink.
158 */
159
160 /*
161 * The "internal use only" fields in regexp.h are present to pass info from
162 * compile to execute that permits the execute phase to run lots faster on
163 * simple cases. They are:
164 *
165 * regstart char that must begin a match; '\0' if none obvious
166 * reganch is the match anchored (at beginning-of-line only)?
167 * regmust string (pointer into program) that match must include, or
168 * nullptr regmlen length of regmust string
169 *
170 * Regstart and reganch permit very fast decisions on suitable starting points
171 * for a match, cutting down the work a lot. Regmust permits fast rejection
172 * of lines that cannot possibly match. The regmust tests are costly enough
173 * that compile() supplies a regmust only if the r.e. contains something
174 * potentially expensive (at present, the only such thing detected is * or +
175 * at the start of the r.e., which can involve a lot of backup). Regmlen is
176 * supplied because the test in find() needs it and compile() is computing
177 * it anyway.
178 */
179
180 /*
181 * Structure for regexp "program". This is essentially a linear encoding
182 * of a nondeterministic finite-state machine (aka syntax charts or
183 * "railroad normal form" in parsing technology). Each node is an opcode
184 * plus a "next" pointer, possibly plus an operand. "Next" pointers of
185 * all nodes except BRANCH implement concatenation; a "next" pointer with
186 * a BRANCH on both ends of it is connecting two alternatives. (Here we
187 * have one of the subtle syntax dependencies: an individual BRANCH (as
188 * opposed to a collection of them) is never concatenated with anything
189 * because of operator precedence.) The operand of some types of node is
190 * a literal string; for others, it is a node leading into a sub-FSM. In
191 * particular, the operand of a BRANCH node is the first node of the branch.
192 * (NB this is *not* a tree structure: the tail of the branch connects
193 * to the thing following the set of BRANCHes.) The opcodes are:
194 */
195
196 // definition number opnd? meaning
197 #define END 0 // no End of program.
198 #define BOL 1 // no Match "" at beginning of line.
199 #define EOL 2 // no Match "" at end of line.
200 #define ANY 3 // no Match any one character.
201 #define ANYOF 4 // str Match any character in this string.
202 #define ANYBUT \
203 5 // str Match any character not in this
204 // string.
205 #define BRANCH \
206 6 // node Match this alternative, or the
207 // next...
208 #define BACK 7 // no Match "", "next" ptr points backward.
209 #define EXACTLY 8 // str Match this string.
210 #define NOTHING 9 // no Match empty string.
211 #define STAR \
212 10 // node Match this (simple) thing 0 or more
213 // times.
214 #define PLUS \
215 11 // node Match this (simple) thing 1 or more
216 // times.
217 #define OPEN \
218 20 // no Mark this point in input as start of
219 // #n.
220 // OPEN+1 is number 1, etc.
221 #define CLOSE 52 // no Analogous to OPEN.
222
223 /*
224 * Opcode notes:
225 *
226 * BRANCH The set of branches constituting a single choice are hooked
227 * together with their "next" pointers, since precedence prevents
228 * anything being concatenated to any individual branch. The
229 * "next" pointer of the last BRANCH in a choice points to the
230 * thing following the whole choice. This is also where the
231 * final "next" pointer of each individual branch points; each
232 * branch starts with the operand node of a BRANCH node.
233 *
234 * BACK Normal "next" pointers all implicitly point forward; BACK
235 * exists to make loop structures possible.
236 *
237 * STAR,PLUS '?', and complex '*' and '+', are implemented as circular
238 * BRANCH structures using BACK. Simple cases (one character
239 * per match) are implemented with STAR and PLUS for speed
240 * and to minimize recursive plunges.
241 *
242 * OPEN,CLOSE ...are numbered at compile time.
243 */
244
245 /*
246 * A node is one char of opcode followed by two chars of "next" pointer.
247 * "Next" pointers are stored as two 8-bit pieces, high order first. The
248 * value is a positive offset from the opcode of the node containing it.
249 * An operand, if any, simply follows the node. (Note that much of the
250 * code generation knows about this implicit relationship.)
251 *
252 * Using two bytes for the "next" pointer is vast overkill for most things,
253 * but allows patterns to get big without disasters.
254 */
255
256 #define OP(p) (*(p))
257 #define NEXT(p) (((*((p) + 1) & 0377) << 8) + (*((p) + 2) & 0377))
258 #define OPERAND(p) ((p) + 3)
259
260 const unsigned char MAGIC = 0234;
261 /*
262 * Utility definitions.
263 */
264
265 #define UCHARAT(p) (reinterpret_cast<const unsigned char*>(p))[0]
266
267 #define ISMULT(c) ((c) == '*' || (c) == '+' || (c) == '?')
268 #define META "^$.[()|?+*\\"
269
270 /*
271 * Flags to be passed up and down.
272 */
273 #define HASWIDTH 01 // Known never to match null string.
274 #define SIMPLE 02 // Simple enough to be STAR/PLUS operand.
275 #define SPSTART 04 // Starts with * or +.
276 #define WORST 0 // Worst case.
277
278 /////////////////////////////////////////////////////////////////////////
279 //
280 // COMPILE AND ASSOCIATED FUNCTIONS
281 //
282 /////////////////////////////////////////////////////////////////////////
283
284 /*
285 * Read only utility variables.
286 */
287 static char regdummy;
288 static char* const regdummyptr = &regdummy;
289
290 /*
291 * Utility class for RegularExpression::compile().
292 */
293 class RegExpCompile
294 {
295 public:
296 const char* regparse; // Input-scan pointer.
297 int regnpar; // () count.
298 char* regcode; // Code-emit pointer; regdummyptr = don't.
299 long regsize; // Code size.
300
301 char* reg(int, int*);
302 char* regbranch(int*);
303 char* regpiece(int*);
304 char* regatom(int*);
305 char* regnode(char);
306 void regc(char);
307 void reginsert(char, char*);
308 static void regtail(char*, const char*);
309 static void regoptail(char*, const char*);
310 };
311
312 static const char* regnext(const char*);
313 static char* regnext(char*);
314
315 #ifdef STRCSPN
316 static int strcspn();
317 #endif
318
319 /*
320 * We can't allocate space until we know how big the compiled form will be,
321 * but we can't compile it (and thus know how big it is) until we've got a
322 * place to put the code. So we cheat: we compile it twice, once with code
323 * generation turned off and size counting turned on, and once "for real".
324 * This also means that we don't allocate space until we are sure that the
325 * thing really will compile successfully, and we never have to move the
326 * code and thus invalidate pointers into it. (Note that it has to be in
327 * one piece because free() must be able to free it all.)
328 *
329 * Beware that the optimization-preparation code in here knows about some
330 * of the structure of the compiled regexp.
331 */
332
333 // compile -- compile a regular expression into internal code
334 // for later pattern matching.
335
336 bool RegularExpression::compile(const char* exp)
337 {
338 const char* scan;
339 const char* longest;
340 int flags;
341
342 if (exp == nullptr) {
343 // RAISE Error, SYM(RegularExpression), SYM(No_Expr),
344 printf("RegularExpression::compile(): No expression supplied.\n");
345 return false;
346 }
347
348 // First pass: determine size, legality.
349 RegExpCompile comp;
350 comp.regparse = exp;
351 comp.regnpar = 1;
352 comp.regsize = 0L;
353 comp.regcode = regdummyptr;
354 comp.regc(static_cast<char>(MAGIC));
355 if (!comp.reg(0, &flags)) {
356 printf("RegularExpression::compile(): Error in compile.\n");
357 return false;
358 }
359 this->regmatch.clear();
360
361 // Small enough for pointer-storage convention?
362 if (comp.regsize >= 65535L) {
363 // RAISE Error, SYM(RegularExpression), SYM(Expr_Too_Big),
364 printf("RegularExpression::compile(): Expression too big.\n");
365 return false;
366 }
367
368 // Allocate space.
369 // #ifndef _WIN32
370 delete[] this->program;
371 // #endif
372 this->program = new char[comp.regsize];
373 this->progsize = static_cast<int>(comp.regsize);
374
375 if (this->program == nullptr) {
376 // RAISE Error, SYM(RegularExpression), SYM(Out_Of_Memory),
377 printf("RegularExpression::compile(): Out of memory.\n");
378 return false;
379 }
380
381 #ifdef __clang_analyzer__ /* Convince it that the program is initialized. */
382 memset(this->program, 0, comp.regsize);
383 #endif
384
385 // Second pass: emit code.
386 comp.regparse = exp;
387 comp.regnpar = 1;
388 comp.regcode = this->program;
389 comp.regc(static_cast<char>(MAGIC));
390 comp.reg(0, &flags);
391
392 // Dig out information for optimizations.
393 this->regstart = '\0'; // Worst-case defaults.
394 this->reganch = 0;
395 this->regmust = nullptr;
396 this->regmlen = 0;
397 scan = this->program + 1; // First BRANCH.
398 if (OP(regnext(scan)) == END) { // Only one top-level choice.
399 scan = OPERAND(scan);
400
401 // Starting-point info.
402 if (OP(scan) == EXACTLY)
403 this->regstart = *OPERAND(scan);
404 else if (OP(scan) == BOL)
405 this->reganch++;
406
407 //
408 // If there's something expensive in the r.e., find the longest
409 // literal string that must appear and make it the regmust. Resolve
410 // ties in favor of later strings, since the regstart check works
411 // with the beginning of the r.e. and avoiding duplication
412 // strengthens checking. Not a strong reason, but sufficient in the
413 // absence of others.
414 //
415 if (flags & SPSTART) {
416 longest = nullptr;
417 size_t len = 0;
418 for (; scan != nullptr; scan = regnext(scan))
419 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
420 longest = OPERAND(scan);
421 len = strlen(OPERAND(scan));
422 }
423 this->regmust = longest;
424 this->regmlen = len;
425 }
426 }
427 return true;
428 }
429
430 /*
431 - reg - regular expression, i.e. main body or parenthesized thing
432 *
433 * Caller must absorb opening parenthesis.
434 *
435 * Combining parenthesis handling with the base level of regular expression
436 * is a trifle forced, but the need to tie the tails of the branches to what
437 * follows makes it hard to avoid.
438 */
439 char* RegExpCompile::reg(int paren, int* flagp)
440 {
441 char* ret;
442 char* br;
443 char* ender;
444 int parno = 0;
445 int flags;
446
447 *flagp = HASWIDTH; // Tentatively.
448
449 // Make an OPEN node, if parenthesized.
450 if (paren) {
451 if (regnpar >= RegularExpressionMatch::NSUBEXP) {
452 // RAISE Error, SYM(RegularExpression), SYM(Too_Many_Parens),
453 printf("RegularExpression::compile(): Too many parentheses.\n");
454 return nullptr;
455 }
456 parno = regnpar;
457 regnpar++;
458 ret = regnode(static_cast<char>(OPEN + parno));
459 } else
460 ret = nullptr;
461
462 // Pick up the branches, linking them together.
463 br = regbranch(&flags);
464 if (br == nullptr)
465 return (nullptr);
466 if (ret != nullptr)
467 regtail(ret, br); // OPEN -> first.
468 else
469 ret = br;
470 if (!(flags & HASWIDTH))
471 *flagp &= ~HASWIDTH;
472 *flagp |= flags & SPSTART;
473 while (*regparse == '|') {
474 regparse++;
475 br = regbranch(&flags);
476 if (br == nullptr)
477 return (nullptr);
478 regtail(ret, br); // BRANCH -> BRANCH.
479 if (!(flags & HASWIDTH))
480 *flagp &= ~HASWIDTH;
481 *flagp |= flags & SPSTART;
482 }
483
484 // Make a closing node, and hook it on the end.
485 ender = regnode(static_cast<char>((paren) ? CLOSE + parno : END));
486 regtail(ret, ender);
487
488 // Hook the tails of the branches to the closing node.
489 for (br = ret; br != nullptr; br = regnext(br))
490 regoptail(br, ender);
491
492 // Check for proper termination.
493 if (paren && *regparse++ != ')') {
494 // RAISE Error, SYM(RegularExpression), SYM(Unmatched_Parens),
495 printf("RegularExpression::compile(): Unmatched parentheses.\n");
496 return nullptr;
497 } else if (!paren && *regparse != '\0') {
498 if (*regparse == ')') {
499 // RAISE Error, SYM(RegularExpression), SYM(Unmatched_Parens),
500 printf("RegularExpression::compile(): Unmatched parentheses.\n");
501 return nullptr;
502 } else {
503 // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
504 printf("RegularExpression::compile(): Internal error.\n");
505 return nullptr;
506 }
507 // NOTREACHED
508 }
509 return (ret);
510 }
511
512 /*
513 - regbranch - one alternative of an | operator
514 *
515 * Implements the concatenation operator.
516 */
517 char* RegExpCompile::regbranch(int* flagp)
518 {
519 char* ret;
520 char* chain;
521 char* latest;
522 int flags;
523
524 *flagp = WORST; // Tentatively.
525
526 ret = regnode(BRANCH);
527 chain = nullptr;
528 while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
529 latest = regpiece(&flags);
530 if (latest == nullptr)
531 return (nullptr);
532 *flagp |= flags & HASWIDTH;
533 if (chain == nullptr) // First piece.
534 *flagp |= flags & SPSTART;
535 else
536 regtail(chain, latest);
537 chain = latest;
538 }
539 if (chain == nullptr) // Loop ran zero times.
540 regnode(NOTHING);
541
542 return (ret);
543 }
544
545 /*
546 - regpiece - something followed by possible [*+?]
547 *
548 * Note that the branching code sequences used for ? and the general cases
549 * of * and + are somewhat optimized: they use the same NOTHING node as
550 * both the endmarker for their branch list and the body of the last branch.
551 * It might seem that this node could be dispensed with entirely, but the
552 * endmarker role is not redundant.
553 */
554 char* RegExpCompile::regpiece(int* flagp)
555 {
556 char* ret;
557 char op;
558 char* next;
559 int flags;
560
561 ret = regatom(&flags);
562 if (ret == nullptr)
563 return (nullptr);
564
565 op = *regparse;
566 if (!ISMULT(op)) {
567 *flagp = flags;
568 return (ret);
569 }
570
571 if (!(flags & HASWIDTH) && op != '?') {
572 // RAISE Error, SYM(RegularExpression), SYM(Empty_Operand),
573 printf("RegularExpression::compile() : *+ operand could be empty.\n");
574 return nullptr;
575 }
576 *flagp = (op != '+') ? (WORST | SPSTART) : (WORST | HASWIDTH);
577
578 if (op == '*' && (flags & SIMPLE))
579 reginsert(STAR, ret);
580 else if (op == '*') {
581 // Emit x* as (x&|), where & means "self".
582 reginsert(BRANCH, ret); // Either x
583 regoptail(ret, regnode(BACK)); // and loop
584 regoptail(ret, ret); // back
585 regtail(ret, regnode(BRANCH)); // or
586 regtail(ret, regnode(NOTHING)); // null.
587 } else if (op == '+' && (flags & SIMPLE))
588 reginsert(PLUS, ret);
589 else if (op == '+') {
590 // Emit x+ as x(&|), where & means "self".
591 next = regnode(BRANCH); // Either
592 regtail(ret, next);
593 regtail(regnode(BACK), ret); // loop back
594 regtail(next, regnode(BRANCH)); // or
595 regtail(ret, regnode(NOTHING)); // null.
596 } else if (op == '?') {
597 // Emit x? as (x|)
598 reginsert(BRANCH, ret); // Either x
599 regtail(ret, regnode(BRANCH)); // or
600 next = regnode(NOTHING); // null.
601 regtail(ret, next);
602 regoptail(ret, next);
603 }
604 regparse++;
605 if (ISMULT(*regparse)) {
606 // RAISE Error, SYM(RegularExpression), SYM(Nested_Operand),
607 printf("RegularExpression::compile(): Nested *?+.\n");
608 return nullptr;
609 }
610 return (ret);
611 }
612
613 /*
614 - regatom - the lowest level
615 *
616 * Optimization: gobbles an entire sequence of ordinary characters so that
617 * it can turn them into a single node, which is smaller to store and
618 * faster to run. Backslashed characters are exceptions, each becoming a
619 * separate node; the code is simpler that way and it's not worth fixing.
620 */
621 char* RegExpCompile::regatom(int* flagp)
622 {
623 char* ret;
624 int flags;
625
626 *flagp = WORST; // Tentatively.
627
628 switch (*regparse++) {
629 case '^':
630 ret = regnode(BOL);
631 break;
632 case '$':
633 ret = regnode(EOL);
634 break;
635 case '.':
636 ret = regnode(ANY);
637 *flagp |= HASWIDTH | SIMPLE;
638 break;
639 case '[': {
640 int rxpclass;
641 int rxpclassend;
642
643 if (*regparse == '^') { // Complement of range.
644 ret = regnode(ANYBUT);
645 regparse++;
646 } else
647 ret = regnode(ANYOF);
648 if (*regparse == ']' || *regparse == '-')
649 regc(*regparse++);
650 while (*regparse != '\0' && *regparse != ']') {
651 if (*regparse == '-') {
652 regparse++;
653 if (*regparse == ']' || *regparse == '\0')
654 regc('-');
655 else {
656 rxpclass = UCHARAT(regparse - 2) + 1;
657 rxpclassend = UCHARAT(regparse);
658 if (rxpclass > rxpclassend + 1) {
659 // RAISE Error, SYM(RegularExpression), SYM(Invalid_Range),
660 printf("RegularExpression::compile(): Invalid range in [].\n");
661 return nullptr;
662 }
663 for (; rxpclass <= rxpclassend; rxpclass++)
664 regc(static_cast<char>(rxpclass));
665 regparse++;
666 }
667 } else
668 regc(*regparse++);
669 }
670 regc('\0');
671 if (*regparse != ']') {
672 // RAISE Error, SYM(RegularExpression), SYM(Unmatched_Bracket),
673 printf("RegularExpression::compile(): Unmatched [].\n");
674 return nullptr;
675 }
676 regparse++;
677 *flagp |= HASWIDTH | SIMPLE;
678 } break;
679 case '(':
680 ret = reg(1, &flags);
681 if (ret == nullptr)
682 return (nullptr);
683 *flagp |= flags & (HASWIDTH | SPSTART);
684 break;
685 case '\0':
686 case '|':
687 case ')':
688 // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
689 printf("RegularExpression::compile(): Internal error.\n"); // Never here
690 return nullptr;
691 case '?':
692 case '+':
693 case '*':
694 // RAISE Error, SYM(RegularExpression), SYM(No_Operand),
695 printf("RegularExpression::compile(): ?+* follows nothing.\n");
696 return nullptr;
697 case '\\':
698 if (*regparse == '\0') {
699 // RAISE Error, SYM(RegularExpression), SYM(Trailing_Backslash),
700 printf("RegularExpression::compile(): Trailing backslash.\n");
701 return nullptr;
702 }
703 ret = regnode(EXACTLY);
704 regc(*regparse++);
705 regc('\0');
706 *flagp |= HASWIDTH | SIMPLE;
707 break;
708 default: {
709 int len;
710 char ender;
711
712 regparse--;
713 len = int(strcspn(regparse, META));
714 if (len <= 0) {
715 // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
716 printf("RegularExpression::compile(): Internal error.\n");
717 return nullptr;
718 }
719 ender = *(regparse + len);
720 if (len > 1 && ISMULT(ender))
721 len--; // Back off clear of ?+* operand.
722 *flagp |= HASWIDTH;
723 if (len == 1)
724 *flagp |= SIMPLE;
725 ret = regnode(EXACTLY);
726 while (len > 0) {
727 regc(*regparse++);
728 len--;
729 }
730 regc('\0');
731 } break;
732 }
733 return (ret);
734 }
735
736 /*
737 - regnode - emit a node
738 Location.
739 */
740 char* RegExpCompile::regnode(char op)
741 {
742 char* ret;
743 char* ptr;
744
745 ret = regcode;
746 if (ret == regdummyptr) {
747 regsize += 3;
748 return (ret);
749 }
750
751 ptr = ret;
752 *ptr++ = op;
753 *ptr++ = '\0'; // Null "next" pointer.
754 *ptr++ = '\0';
755 regcode = ptr;
756
757 return (ret);
758 }
759
760 /*
761 - regc - emit (if appropriate) a byte of code
762 */
763 void RegExpCompile::regc(char b)
764 {
765 if (regcode != regdummyptr)
766 *regcode++ = b;
767 else
768 regsize++;
769 }
770
771 /*
772 - reginsert - insert an operator in front of already-emitted operand
773 *
774 * Means relocating the operand.
775 */
776 void RegExpCompile::reginsert(char op, char* opnd)
777 {
778 char* src;
779 char* dst;
780 char* place;
781
782 if (regcode == regdummyptr) {
783 regsize += 3;
784 return;
785 }
786
787 src = regcode;
788 regcode += 3;
789 dst = regcode;
790 while (src > opnd)
791 *--dst = *--src;
792
793 place = opnd; // Op node, where operand used to be.
794 *place++ = op;
795 *place++ = '\0';
796 *place = '\0';
797 }
798
799 /*
800 - regtail - set the next-pointer at the end of a node chain
801 */
802 void RegExpCompile::regtail(char* p, const char* val)
803 {
804 char* scan;
805 char* temp;
806 int offset;
807
808 if (p == regdummyptr)
809 return;
810
811 // Find last node.
812 scan = p;
813 for (;;) {
814 temp = regnext(scan);
815 if (temp == nullptr)
816 break;
817 scan = temp;
818 }
819
820 if (OP(scan) == BACK)
821 offset = int(scan - val);
822 else
823 offset = int(val - scan);
824 *(scan + 1) = static_cast<char>((offset >> 8) & 0377);
825 *(scan + 2) = static_cast<char>(offset & 0377);
826 }
827
828 /*
829 - regoptail - regtail on operand of first argument; nop if operandless
830 */
831 void RegExpCompile::regoptail(char* p, const char* val)
832 {
833 // "Operandless" and "op != BRANCH" are synonymous in practice.
834 if (p == nullptr || p == regdummyptr || OP(p) != BRANCH)
835 return;
836 regtail(OPERAND(p), val);
837 }
838
839 ////////////////////////////////////////////////////////////////////////
840 //
841 // find and friends
842 //
843 ////////////////////////////////////////////////////////////////////////
844
845 /*
846 * Utility class for RegularExpression::find().
847 */
848 class RegExpFind
849 {
850 public:
851 const char* reginput; // String-input pointer.
852 const char* regbol; // Beginning of input, for ^ check.
853 const char** regstartp; // Pointer to startp array.
854 const char** regendp; // Ditto for endp.
855
856 int regtry(const char*, const char**, const char**, const char*);
857 int regmatch(const char*);
858 int regrepeat(const char*);
859 };
860
861 // find -- Matches the regular expression to the given string.
862 // Returns true if found, and sets start and end indexes accordingly.
863 bool RegularExpression::find(char const* string,
864 RegularExpressionMatch& rmatch) const
865 {
866 const char* s;
867
868 rmatch.clear();
869 rmatch.searchstring = string;
870
871 if (!this->program) {
872 return false;
873 }
874
875 // Check validity of program.
876 if (UCHARAT(this->program) != MAGIC) {
877 // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
878 printf(
879 "RegularExpression::find(): Compiled regular expression corrupted.\n");
880 return false;
881 }
882
883 // If there is a "must appear" string, look for it.
884 if (this->regmust != nullptr) {
885 s = string;
886 while ((s = strchr(s, this->regmust[0])) != nullptr) {
887 if (strncmp(s, this->regmust, this->regmlen) == 0)
888 break; // Found it.
889 s++;
890 }
891 if (s == nullptr) // Not present.
892 return false;
893 }
894
895 RegExpFind regFind;
896
897 // Mark beginning of line for ^ .
898 regFind.regbol = string;
899
900 // Simplest case: anchored match need be tried only once.
901 if (this->reganch)
902 return (
903 regFind.regtry(string, rmatch.startp, rmatch.endp, this->program) != 0);
904
905 // Messy cases: unanchored match.
906 s = string;
907 if (this->regstart != '\0')
908 // We know what char it must start with.
909 while ((s = strchr(s, this->regstart)) != nullptr) {
910 if (regFind.regtry(s, rmatch.startp, rmatch.endp, this->program))
911 return true;
912 s++;
913 }
914 else
915 // We don't -- general case.
916 do {
917 if (regFind.regtry(s, rmatch.startp, rmatch.endp, this->program))
918 return true;
919 } while (*s++ != '\0');
920
921 // Failure.
922 return false;
923 }
924
925 /*
926 - regtry - try match at specific point
927 0 failure, 1 success
928 */
929 int RegExpFind::regtry(const char* string, const char** start,
930 const char** end, const char* prog)
931 {
932 int i;
933 const char** sp1;
934 const char** ep;
935
936 reginput = string;
937 regstartp = start;
938 regendp = end;
939
940 sp1 = start;
941 ep = end;
942 for (i = RegularExpressionMatch::NSUBEXP; i > 0; i--) {
943 *sp1++ = nullptr;
944 *ep++ = nullptr;
945 }
946 if (regmatch(prog + 1)) {
947 start[0] = string;
948 end[0] = reginput;
949 return (1);
950 } else
951 return (0);
952 }
953
954 /*
955 - regmatch - main matching routine
956 *
957 * Conceptually the strategy is simple: check to see whether the current
958 * node matches, call self recursively to see whether the rest matches,
959 * and then act accordingly. In practice we make some effort to avoid
960 * recursion, in particular by going through "ordinary" nodes (that don't
961 * need to know whether the rest of the match failed) by a loop instead of
962 * by recursion.
963 * 0 failure, 1 success
964 */
965 int RegExpFind::regmatch(const char* prog)
966 {
967 const char* scan; // Current node.
968 const char* next; // Next node.
969
970 scan = prog;
971
972 while (scan != nullptr) {
973
974 next = regnext(scan);
975
976 switch (OP(scan)) {
977 case BOL:
978 if (reginput != regbol)
979 return (0);
980 break;
981 case EOL:
982 if (*reginput != '\0')
983 return (0);
984 break;
985 case ANY:
986 if (*reginput == '\0')
987 return (0);
988 reginput++;
989 break;
990 case EXACTLY: {
991 size_t len;
992 const char* opnd;
993
994 opnd = OPERAND(scan);
995 // Inline the first character, for speed.
996 if (*opnd != *reginput)
997 return (0);
998 len = strlen(opnd);
999 if (len > 1 && strncmp(opnd, reginput, len) != 0)
1000 return (0);
1001 reginput += len;
1002 } break;
1003 case ANYOF:
1004 if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == nullptr)
1005 return (0);
1006 reginput++;
1007 break;
1008 case ANYBUT:
1009 if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != nullptr)
1010 return (0);
1011 reginput++;
1012 break;
1013 case NOTHING:
1014 break;
1015 case BACK:
1016 break;
1017 case OPEN + 1:
1018 case OPEN + 2:
1019 case OPEN + 3:
1020 case OPEN + 4:
1021 case OPEN + 5:
1022 case OPEN + 6:
1023 case OPEN + 7:
1024 case OPEN + 8:
1025 case OPEN + 9:
1026 case OPEN + 10:
1027 case OPEN + 11:
1028 case OPEN + 12:
1029 case OPEN + 13:
1030 case OPEN + 14:
1031 case OPEN + 15:
1032 case OPEN + 16:
1033 case OPEN + 17:
1034 case OPEN + 18:
1035 case OPEN + 19:
1036 case OPEN + 20:
1037 case OPEN + 21:
1038 case OPEN + 22:
1039 case OPEN + 23:
1040 case OPEN + 24:
1041 case OPEN + 25:
1042 case OPEN + 26:
1043 case OPEN + 27:
1044 case OPEN + 28:
1045 case OPEN + 29:
1046 case OPEN + 30:
1047 case OPEN + 31:
1048 case OPEN + 32: {
1049 int no;
1050 const char* save;
1051
1052 no = OP(scan) - OPEN;
1053 save = reginput;
1054
1055 if (regmatch(next)) {
1056
1057 //
1058 // Don't set startp if some later invocation of the
1059 // same parentheses already has.
1060 //
1061 if (regstartp[no] == nullptr)
1062 regstartp[no] = save;
1063 return (1);
1064 } else
1065 return (0);
1066 }
1067 // break;
1068 case CLOSE + 1:
1069 case CLOSE + 2:
1070 case CLOSE + 3:
1071 case CLOSE + 4:
1072 case CLOSE + 5:
1073 case CLOSE + 6:
1074 case CLOSE + 7:
1075 case CLOSE + 8:
1076 case CLOSE + 9:
1077 case CLOSE + 10:
1078 case CLOSE + 11:
1079 case CLOSE + 12:
1080 case CLOSE + 13:
1081 case CLOSE + 14:
1082 case CLOSE + 15:
1083 case CLOSE + 16:
1084 case CLOSE + 17:
1085 case CLOSE + 18:
1086 case CLOSE + 19:
1087 case CLOSE + 20:
1088 case CLOSE + 21:
1089 case CLOSE + 22:
1090 case CLOSE + 23:
1091 case CLOSE + 24:
1092 case CLOSE + 25:
1093 case CLOSE + 26:
1094 case CLOSE + 27:
1095 case CLOSE + 28:
1096 case CLOSE + 29:
1097 case CLOSE + 30:
1098 case CLOSE + 31:
1099 case CLOSE + 32: {
1100 int no;
1101 const char* save;
1102
1103 no = OP(scan) - CLOSE;
1104 save = reginput;
1105
1106 if (regmatch(next)) {
1107
1108 //
1109 // Don't set endp if some later invocation of the
1110 // same parentheses already has.
1111 //
1112 if (regendp[no] == nullptr)
1113 regendp[no] = save;
1114 return (1);
1115 } else
1116 return (0);
1117 }
1118 // break;
1119 case BRANCH: {
1120
1121 const char* save;
1122
1123 if (OP(next) != BRANCH) // No choice.
1124 next = OPERAND(scan); // Avoid recursion.
1125 else {
1126 do {
1127 save = reginput;
1128 if (regmatch(OPERAND(scan)))
1129 return (1);
1130 reginput = save;
1131 scan = regnext(scan);
1132 } while (scan != nullptr && OP(scan) == BRANCH);
1133 return (0);
1134 // NOTREACHED
1135 }
1136 } break;
1137 case STAR:
1138 case PLUS: {
1139 char nextch;
1140 int no;
1141 const char* save;
1142 int min_no;
1143
1144 //
1145 // Lookahead to avoid useless match attempts when we know
1146 // what character comes next.
1147 //
1148 nextch = '\0';
1149 if (OP(next) == EXACTLY)
1150 nextch = *OPERAND(next);
1151 min_no = (OP(scan) == STAR) ? 0 : 1;
1152 save = reginput;
1153 no = regrepeat(OPERAND(scan));
1154 while (no >= min_no) {
1155 // If it could work, try it.
1156 if (nextch == '\0' || *reginput == nextch)
1157 if (regmatch(next))
1158 return (1);
1159 // Couldn't or didn't -- back up.
1160 no--;
1161 reginput = save + no;
1162 }
1163 return (0);
1164 }
1165 // break;
1166 case END:
1167 return (1); // Success!
1168
1169 default:
1170 // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
1171 printf(
1172 "RegularExpression::find(): Internal error -- memory corrupted.\n");
1173 return 0;
1174 }
1175 scan = next;
1176 }
1177
1178 //
1179 // We get here only if there's trouble -- normally "case END" is the
1180 // terminating point.
1181 //
1182 // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
1183 printf("RegularExpression::find(): Internal error -- corrupted pointers.\n");
1184 return (0);
1185 }
1186
1187 /*
1188 - regrepeat - repeatedly match something simple, report how many
1189 */
1190 int RegExpFind::regrepeat(const char* p)
1191 {
1192 int count = 0;
1193 const char* scan;
1194 const char* opnd;
1195
1196 scan = reginput;
1197 opnd = OPERAND(p);
1198 switch (OP(p)) {
1199 case ANY:
1200 count = int(strlen(scan));
1201 scan += count;
1202 break;
1203 case EXACTLY:
1204 while (*opnd == *scan) {
1205 count++;
1206 scan++;
1207 }
1208 break;
1209 case ANYOF:
1210 while (*scan != '\0' && strchr(opnd, *scan) != nullptr) {
1211 count++;
1212 scan++;
1213 }
1214 break;
1215 case ANYBUT:
1216 while (*scan != '\0' && strchr(opnd, *scan) == nullptr) {
1217 count++;
1218 scan++;
1219 }
1220 break;
1221 default: // Oh dear. Called inappropriately.
1222 // RAISE Error, SYM(RegularExpression), SYM(Internal_Error),
1223 printf("cm RegularExpression::find(): Internal error.\n");
1224 return 0;
1225 }
1226 reginput = scan;
1227 return (count);
1228 }
1229
1230 /*
1231 - regnext - dig the "next" pointer out of a node
1232 */
1233 static const char* regnext(const char* p)
1234 {
1235 int offset;
1236
1237 if (p == regdummyptr)
1238 return (nullptr);
1239
1240 offset = NEXT(p);
1241 if (offset == 0)
1242 return (nullptr);
1243
1244 if (OP(p) == BACK)
1245 return (p - offset);
1246 else
1247 return (p + offset);
1248 }
1249
1250 static char* regnext(char* p)
1251 {
1252 int offset;
1253
1254 if (p == regdummyptr)
1255 return (nullptr);
1256
1257 offset = NEXT(p);
1258 if (offset == 0)
1259 return (nullptr);
1260
1261 if (OP(p) == BACK)
1262 return (p - offset);
1263 else
1264 return (p + offset);
1265 }
1266
1267 } // namespace KWSYS_NAMESPACE