Loading...
Searching...
No Matches
regcomp.c File Reference
#include "regex/regguts.h"#include "regc_lex.c"#include "regc_color.c"#include "regc_nfa.c"#include "regc_cvec.c"#include "regc_pg_locale.c"#include "regc_locale.c"
Include dependency graph for regcomp.c:
Go to the source code of this file.
Data Structures | |
| struct | vars |
Variables | |
| static const struct fns | functions |
Macro Definition Documentation
◆ AHEAD
◆ ARCV
◆ BACKREF
◆ BEHIND
◆ CANTMATCH
◆ CCLASS
◆ CCLASSC
◆ CCLASSS
◆ CNOERR
◆ COLLEL
◆ COLORED
Value:
((a)->co >= 0 && \
Definition at line 352 of file regcomp.c.
357 {
360};
361
362
363
364/*
365 * pg_regcomp - compile regular expression
366 *
367 * Note: on failure, no resources remain allocated, so pg_regfree()
368 * need not be applied to re.
369 */
370int
374 int flags,
375 Oid collation)
376{
382
383#ifdef REG_DEBUG
385#else
387#endif
388
389#define CNOERR() { if (ISERR()) return freev(v, v->err); }
390
391 /* sanity checks */
392
400
401 /* Initialize locale-dependent support */
402 pg_set_regex_collation(collation);
403
404 /* initial setup (after which freev() is callable) */
405 v->re = re;
408 v->err = 0;
409 v->cflags = flags;
410 v->nsubexp = 0;
412 v->nsubs = 10;
425 v->nlacons = 0;
426 v->spaceused = 0;
427 re->re_magic = REMAGIC;
428 re->re_info = 0; /* bits get set during parse */
430 re->re_collation = collation;
431 re->re_guts = NULL;
433
434 /* more complex setup, malloced things */
443 g->nlacons = 0;
446 CNOERR();
447 /* set up a reasonably-sized transient cvec for getcvec usage */
451
452 /* parsing */
455 {
456 /* assign newline a unique color */
459 }
460 CNOERR();
463 CNOERR();
465
466 /* finish setup of nfa and its subre tree */
468 CNOERR();
469#ifdef REG_DEBUG
471 {
475 }
476#endif
481 cleanst(v);
482#ifdef REG_DEBUG
484 {
487 }
488#endif
489
490 /* build compacted NFAs for tree and lacons */
492 CNOERR();
495 {
497
498#ifdef REG_DEBUG
501#endif
502
503 /* Prepend .* to pattern if it's a lookbehind LACON */
505 }
506 CNOERR();
509
510 /* build compacted NFAs for tree, lacons, fast search */
511#ifdef REG_DEBUG
514#endif
515 /* can sacrifice main NFA now, so use it as work area */
517 CNOERR();
519 CNOERR();
521 CNOERR();
522
523 /* looks okay, package it up */
524 re->re_nsub = v->nsubexp;
528 g->info = re->re_info;
529 g->nsub = re->re_nsub;
537
538#ifdef REG_DEBUG
540 {
541 dump(re, stdout);
542 fflush(stdout);
543 }
544#endif
545
548}
549
550/*
551 * moresubs - enlarge subRE vector
552 */
553static void
556{
558 size_t n;
559
562
564 {
569 }
570 else
573 {
575 return;
576 }
577 v->subs = p;
579 *p = NULL;
582}
583
584/*
585 * freev - free vars struct's substructures where necessary
586 *
587 * Optionally does error-number setting, and always returns error code
588 * (if any), to make error-handling code terser.
589 */
590static int
593{
603 cleanst(v);
611
613}
614
615/*
616 * makesearch - turn an NFA into a search NFA (implicit prepend of .*?)
617 * NFA must have been optimize()d already.
618 */
619static void
622{
629
630 /* no loops are needed if it's anchored */
632 {
635 break;
636 }
638 {
639 /* add implicit .* in front */
641
642 /* and ^* and \A* too -- not always necessary, but harmless */
645
646 /*
647 * The pattern is still MATCHALL if it was before, but the max match
648 * length is now infinity.
649 */
652 }
653
654 /*
655 * Now here's the subtle part. Because many REs have no lookback
656 * constraints, often knowing when you were in the pre state tells you
657 * little; it's the next state(s) that are informative. But some of them
658 * may have other inarcs, i.e. it may be possible to make actual progress
659 * and then return to one of them. We must de-optimize such cases,
660 * splitting each such state into progress and no-progress states.
661 */
662
663 /* first, make a list of the states reachable from pre and elsewhere */
666 {
667 s = a->to;
669 {
671 break;
672 }
673
674 /*
675 * We want to mark states as being in the list already by having non
676 * NULL tmp fields, but we can't just store the old slist value in tmp
677 * because that doesn't work for the first such state. Instead, the
678 * first list entry gets its own address in tmp.
679 */
681 {
683 slist = s;
684 }
685 }
686
687 /* do the splits */
689 {
691 NOERR();
693 NOERR();
695 {
698 {
701 }
702 }
705 }
706}
707
708/*
709 * parse - parse an RE
710 *
711 * This is actually just the top level, which parses a bunch of branches
712 * tied together with '|'. If there's more than one, they appear in the
713 * tree as the children of a '|' subre.
714 */
721{
724
726
728 NOERRN();
730 do
731 { /* a branch */
735
738 NOERRN();
741 NOERRN();
743 NOERRN();
746 else
752
754 {
757 }
758
759 /* optimize out simple cases */
761 { /* only one branch */
765 }
767 { /* no interesting innards */
771 }
772
774}
775
776/*
777 * parsebranch - parse one branch of an RE
778 *
779 * This mostly manages concatenation, working closely with parseqatom().
780 * Concatenated things are bundled up as much as possible, with separate
781 * '.' nodes introduced only when necessary due to substructure.
782 */
789 int partial) /* is this only part of a branch? */
790{
794
795 lp = left;
796 seencontent = 0;
798 NOERRN();
800 {
802 { /* implicit concat operator */
804 NOERRN();
806 }
807 seencontent = 1;
808
809 /* NB, recursion in parseqatom() may swallow rest of branch */
811 NOERRN();
812 }
813
815 { /* empty branch */
816 if (!partial)
819 EMPTYARC(left, right);
820 }
821
822 return t;
823}
824
825/*
826 * parseqatom - parse one quantified atom or constraint of an RE
827 *
828 * The bookkeeping near the end cooperates very closely with parsebranch();
829 * in particular, it contains a recursion that can involve parsing the rest
830 * of the branch, making this function's name somewhat inaccurate.
831 *
832 * Usually, the return value is just "top", but in some cases where we
833 * have parsed the rest of the branch, we may deem "top" redundant and
834 * free it, returning some child subre instead.
835 */
843{
846
847#define ARCV(t, val) newarc(v->nfa, t, val, lp, rp)
848 int m,
849 n;
857 int f;
859
860 /* initial bookkeeping */
865
866 /* an atom or constraint... */
869 {
870 /* first, constraints, which end by returning */
871 case '^':
875 NEXT();
877 break;
878 case '$':
882 NEXT();
884 break;
888 NEXT();
890 break;
894 NEXT();
896 break;
897 case '<':
898 wordchrs(v);
900 NOERRN();
903 NEXT();
905 break;
906 case '>':
907 wordchrs(v);
909 NOERRN();
912 NEXT();
914 break;
916 wordchrs(v);
918 NOERRN();
922 NOERRN();
925 NEXT();
927 break;
929 wordchrs(v);
931 NOERRN();
935 NOERRN();
938 NEXT();
940 break;
943 NEXT();
946 NOERRN();
949 NOERRN();
951 NEXT();
954 break;
955 /* then errors, to get them out of the way */
956 case '*':
957 case '+':
958 case '?':
959 case '{':
962 break;
963 default:
966 break;
967 /* then plain characters, and minor variants on that theme */
968 case ')': /* unbalanced paren */
970 {
973 }
974 /* legal in EREs due to specification botch */
976 /* fall through into case PLAIN */
977 /* FALLTHROUGH */
981 NOERRN();
982 NEXT();
983 break;
984 case '[':
987 else
990 NEXT();
991 break;
995 NEXT();
996 break;
999 /* charclasscomplement() did okcolors() internally */
1000 NEXT();
1001 break;
1002 case '.':
1006 NEXT();
1007 break;
1008 /* and finally the ugly stuff */
1009 case '(': /* value flags as capturing or non */
1012 {
1013 v->nsubexp++;
1017 }
1018 else
1020 NEXT();
1021
1022 /*
1023 * Make separate endpoint states to keep this sub-NFA distinct
1024 * from what surrounds it. We need to be sure that when we
1025 * duplicate the sub-NFA for a backref, we get the right
1026 * states/arcs and no others. In particular, letting a backref
1027 * duplicate the sub-NFA from lp to rp would be quite wrong,
1028 * because we may add quantification superstructure around this
1029 * atom below. (Perhaps we could skip the extra states for
1030 * non-capturing parens, but it seems not worth the trouble.)
1031 */
1034 NOERRN();
1035 /* We may not need these arcs, but keep things connected for now */
1038 NOERRN();
1041 NEXT();
1042 NOERRN();
1044 {
1046 {
1047 /* normal case: just mark the atom as capturing */
1050 }
1051 else
1052 {
1053 /* generate no-op wrapper node to handle "((x))" */
1055 NOERRN();
1058 atom = t;
1059 }
1062 }
1063 /* postpone everything else pending possible {0} */
1064 break;
1070 NOERRN();
1072 NOERRN();
1074 NOERRN();
1078 NEXT();
1079 break;
1080 }
1081
1082 /* ...and an atom may be followed by a quantifier */
1084 {
1085 case '*':
1086 m = 0;
1087 n = DUPINF;
1089 NEXT();
1090 break;
1091 case '+':
1092 m = 1;
1093 n = DUPINF;
1095 NEXT();
1096 break;
1097 case '?':
1098 m = 0;
1099 n = 1;
1101 NEXT();
1102 break;
1103 case '{':
1104 NEXT();
1105 m = scannum(v);
1107 {
1109 n = scannum(v);
1110 else
1111 n = DUPINF;
1112 if (m > n)
1113 {
1116 }
1117 /* {m,n} exercises preference, even if it's {m,m} */
1119 }
1120 else
1121 {
1122 n = m;
1123 /* {m} passes operand's preference through */
1124 qprefer = 0;
1125 }
1127 { /* catches errors too */
1130 }
1131 NEXT();
1132 break;
1133 default: /* no quantifier */
1134 m = n = 1;
1135 qprefer = 0;
1136 break;
1137 }
1138
1139 /* annoying special case: {0} or {0,0} cancels everything */
1140 if (m == 0 && n == 0)
1141 {
1142 /*
1143 * If we had capturing subexpression(s) within the atom, we don't want
1144 * to destroy them, because it's legal (if useless) to back-ref them
1145 * later. Hence, just unlink the atom from lp/rp and then ignore it.
1146 */
1148 {
1151 }
1152 else
1153 {
1154 /* Otherwise, we can clean up any subre infrastructure we made */
1158 }
1161 }
1162
1163 /* if not a messy case, avoid hard part */
1167 {
1168 if (!(m == 1 && n == 1))
1172 top->flags = f;
1174 }
1175
1176 /*
1177 * hard part: something messy
1178 *
1179 * That is, capturing parens, back reference, short/long clash, or an atom
1180 * with substructure containing one of those.
1181 */
1182
1183 /* now we'll need a subre for the contents even if they're boring */
1185 {
1187 NOERRN();
1188 }
1189
1190 /*
1191 * For what follows, we need the atom to have its own begin/end states
1192 * that are distinct from lp/rp, so that we can wrap iteration structure
1193 * around it. The parenthesized-atom case above already made suitable
1194 * states (and we don't want to modify a capturing subre, since it's
1195 * already recorded in v->subs[]). Otherwise, we need more states.
1196 */
1198 {
1201 NOERRN();
1204 atom->begin = s;
1206 }
1207 else
1208 {
1209 /* The atom's OK, but we must temporarily disconnect it from lp/rp */
1210 /* (this removes the EMPTY arcs we made above) */
1213 }
1214
1215 /*----------
1216 * Prepare a general-purpose state skeleton.
1217 *
1218 * In the no-backrefs case, we want this:
1219 *
1220 * [lp] ---> [s] ---prefix---> ---atom---> ---rest---> [rp]
1221 *
1222 * where prefix is some repetitions of atom, and "rest" is the remainder
1223 * of the branch. In the general case we need:
1224 *
1225 * [lp] ---> [s] ---iterator---> [s2] ---rest---> [rp]
1226 *
1227 * where the iterator wraps around the atom.
1228 *
1229 * We make the s state here for both cases; s2 is made below if needed
1230 *----------
1231 */
1233 NOERRN();
1235 NOERRN();
1236
1237 /* break remaining subRE into x{...} and what follows */
1239 NOERRN();
1242
1243 /*
1244 * Here we should recurse to fill t->child->sibling ... but we must
1245 * postpone that to the end. One reason is that t->child may be replaced
1246 * below, and we don't want to worry about its sibling link.
1247 */
1248
1249 /*
1250 * Convert top node to a concatenation of the prefix (top->child, covering
1251 * whatever we parsed previously) and remaining (t). Note that the prefix
1252 * could be empty, in which case this concatenation node is unnecessary.
1253 * To keep things simple, we operate in a general way for now, and get rid
1254 * of unnecessary subres below.
1255 */
1258 NOERRN();
1260 top->child->sibling = t;
1261 /* top->flags will get updated later */
1262
1263 /* if it's a backref, now is the time to replicate the subNFA */
1265 {
1269
1270 /*
1271 * And here's why the recursion got postponed: it must wait until the
1272 * skeleton is filled in, because it may hit a backref that wants to
1273 * copy the filled-in skeleton.
1274 */
1277 NOERRN();
1278
1279 /* The backref node's NFA should not enforce any constraints */
1281 NOERRN();
1282 }
1283
1284 /*
1285 * It's quantifier time. If the atom is just a backref, we'll let it deal
1286 * with quantifiers internally.
1287 */
1289 {
1290 /* special case: backrefs have internal quantifiers */
1292 /* just stuff everything into atom */
1297 /* rest of branch can be strung starting from atom->end */
1299 }
1300 else if (m == 1 && n == 1 &&
1301 (qprefer == 0 ||
1304 {
1305 /* no/vacuous quantifier: done */
1307 /* rest of branch can be strung starting from atom->end */
1309 }
1311 {
1312 /*
1313 * If there's no captures nor backrefs in the atom being repeated, we
1314 * don't really care where the submatches of the iteration are, so we
1315 * don't need an iteration node. Make a plain DFA node instead.
1316 */
1321 NOERRN();
1323 *atomp = t;
1324 /* rest of branch can be strung starting from t->end */
1326 }
1328 {
1329 /*
1330 * If there's no backrefs involved, we can turn x{m,n} into
1331 * x{m-1,n-1}x, with capturing parens in only the second x. This is
1332 * valid because we only care about capturing matches from the final
1333 * iteration of the quantifier. It's a win because we can implement
1334 * the backref-free left side as a plain DFA node, since we don't
1335 * really care where its submatches are.
1336 */
1342 NOERRN();
1344 NOERRN();
1346 *atomp = t;
1347 /* rest of branch can be strung starting from atom->end */
1349 }
1350 else
1351 {
1352 /* general case: need an iteration node */
1354 NOERRN();
1356 NOERRN();
1361 NOERRN();
1365 *atomp = t;
1366 /* rest of branch is to be strung from iteration's end state */
1367 }
1368
1369 /* and finally, look after that postponed recursion */
1372 {
1373 /* parse all the rest of the branch, and insert in t->child->sibling */
1375 NOERRN();
1377
1378 /* here's the promised update of the flags */
1381
1382 /* neither t nor top could be directly marked for capture as yet */
1385
1386 /*
1387 * At this point both top and t are concatenation (op == '.') subres,
1388 * and we have top->child = prefix of branch, top->child->sibling = t,
1389 * t->child = messy atom (with quantification superstructure if
1390 * needed), t->child->sibling = rest of branch.
1391 *
1392 * If the messy atom was the first thing in the branch, then
1393 * top->child is vacuous and we can get rid of one level of
1394 * concatenation.
1395 */
1398 {
1402 freesrnode(v, t);
1403 }
1404
1405 /*
1406 * Otherwise, it's possible that t->child is not messy in itself, but
1407 * we considered it messy because its greediness conflicts with what
1408 * preceded it. Then it could be that the combination of t->child and
1409 * the rest of the branch is also not messy, in which case we can get
1410 * rid of the child concatenation by merging t->child and the rest of
1411 * the branch into one plain DFA node.
1412 */
1416 {
1421 }
1422 }
1423 else
1424 {
1425 /*
1426 * There's nothing left in the branch, so we don't need the second
1427 * concatenation node 't'. Just link s2 straight to rp.
1428 */
1432 freesrnode(v, t);
1433
1434 /*
1435 * Again, it could be that top->child is vacuous (if the messy atom
1436 * was in fact the only thing in the branch). In that case we need no
1437 * concatenation at all; just replace top with top->child->sibling.
1438 */
1441 {
1446 top = t;
1447 }
1448 }
1449
1451}
1452
1453/*
1454 * nonword - generate arcs for non-word-character ahead or behind
1455 */
1456static void
1458 int dir, /* AHEAD or BEHIND */
1461{
1463
1468 /* (no need for special attention to \n) */
1469}
1470
1471/*
1472 * word - generate arcs for word character ahead or behind
1473 */
1474static void
1476 int dir, /* AHEAD or BEHIND */
1479{
1482 /* (no need for special attention to \n) */
1483}
1484
1485/*
1486 * charclass - generate arcs for a character class
1487 *
1488 * This is used for both atoms (\w and sibling escapes) and for elements
1489 * of bracket expressions. The caller is responsible for calling okcolors()
1490 * at the end of processing the atom or bracket.
1491 */
1492static void
1497{
1499
1500 /* obtain possibly-cached cvec for char class */
1503 NOERR();
1504
1505 /* build the arcs; this may cause color splitting */
1507}
1508
1509/*
1510 * charclasscomplement - generate arcs for a complemented character class
1511 *
1512 * This is used for both atoms (\W and sibling escapes) and for elements
1513 * of bracket expressions. In bracket expressions, it is the caller's
1514 * responsibility that there not be any open subcolors when this is called.
1515 */
1516static void
1521{
1524
1525 /* make dummy state to hang temporary arcs on */
1527 NOERR();
1528
1529 /* obtain possibly-cached cvec for char class */
1532 NOERR();
1533
1534 /* build arcs for char class; this may cause color splitting */
1535 subcolorcvec(v, cv, cstate, cstate);
1536 NOERR();
1537
1538 /* clean up any subcolors in the arc set */
1540 NOERR();
1541
1542 /* now build output arcs for the complement of the char class */
1544 NOERR();
1545
1546 /* clean up dummy state */
1548}
1549
1550/*
1551 * scannum - scan a number
1552 */
1553static int /* value, <= DUPMAX */
1555{
1556 int n = 0;
1557
1559 {
1560 n = n * 10 + v->nextvalue;
1561 NEXT();
1562 }
1564 {
1566 return 0;
1567 }
1568 return n;
1569}
1570
1571/*
1572 * repeat - replicate subNFA for quantifiers
1573 *
1574 * The sub-NFA strung from lp to rp is modified to represent m to n
1575 * repetitions of its initial contents.
1576 *
1577 * The duplication sequences used here are chosen carefully so that any
1578 * pointers starting out pointing into the subexpression end up pointing into
1579 * the last occurrence. (Note that it may not be strung between the same
1580 * left and right end states, however!) This used to be important for the
1581 * subRE tree, although the important bits are now handled by the in-line
1582 * code in parse(), and when this is called, it doesn't matter any more.
1583 */
1584static void
1588 int m,
1589 int n)
1590{
1591#define SOME 2
1592#define INF 3
1593#define PAIR(x, y) ((x)*4 + (y))
1594#define REDUCE(x) ( ((x) == DUPINF) ? INF : (((x) > 1) ? SOME : (x)) )
1599
1601 {
1605 break;
1608 break;
1611 NOERR();
1613 break;
1616 NOERR();
1621 break;
1623 break;
1626 NOERR();
1629 NOERR();
1631 NOERR();
1633 break;
1637 NOERR();
1643 break;
1646 NOERR();
1649 NOERR();
1651 break;
1654 NOERR();
1657 NOERR();
1659 break;
1660 default:
1662 break;
1663 }
1664}
1665
1666/*
1667 * bracket - handle non-complemented bracket expression
1668 *
1669 * Also called from cbracket for complemented bracket expressions.
1670 */
1671static void
1675{
1676 /*
1677 * We can't process complemented char classes (e.g. \W) immediately while
1678 * scanning the bracket expression, else color bookkeeping gets confused.
1679 * Instead, remember whether we saw any in have_cclassc[], and process
1680 * them at the end.
1681 */
1685
1687
1689 NEXT();
1693
1694 /* close up open subcolors from the positive bracket elements */
1696 NOERR();
1697
1698 /* now handle any complemented elements */
1701 {
1703 {
1705 NOERR();
1707 }
1708 }
1709
1710 /*
1711 * If we had any complemented elements, see if we can optimize the bracket
1712 * into a rainbow. Since a complemented element is the only way a WHITE
1713 * arc could get into the result, there's no point in checking otherwise.
1714 */
1717}
1718
1719/*
1720 * cbracket - handle complemented bracket expression
1721 *
1722 * We do it by calling bracket() with dummy endpoints, and then complementing
1723 * the result. The alternative would be to invoke rainbow(), and then delete
1724 * arcs as the b.e. is seen... but that gets messy, and is really quite
1725 * infeasible now that rainbow() just puts out one RAINBOW arc.
1726 */
1727static void
1731{
1734
1735 NOERR();
1736 bracket(v, left, right);
1737
1738 /* in NLSTOP mode, ensure newline is not part of the result set */
1741 NOERR();
1742
1744
1745 /*
1746 * Easy part of complementing, and all there is to do since the MCCE code
1747 * was removed. Note that the result of colorcomplement() cannot be a
1748 * rainbow, since we don't allow empty brackets; so there's no point in
1749 * calling optimizebracket() again.
1750 */
1752 NOERR();
1756}
1757
1758/*
1759 * brackpart - handle one item (or range) within a bracket expression
1760 */
1761static void
1766{
1773
1774 /* parse something, get rid of special cases, take shortcuts */
1776 {
1779 return;
1780 break;
1783 NEXT();
1784 /* shortcut for ordinary chr (not range) */
1786 {
1788 return;
1789 }
1790 NOERR();
1791 break;
1796 NOERR();
1798 NOERR();
1799 break;
1804 NOERR();
1806 NOERR();
1808 NOERR();
1810 return;
1811 break;
1816 NOERR();
1818 NOERR();
1820 return;
1821 break;
1824 NEXT();
1825 return;
1826 break;
1828 /* we cannot call charclasscomplement() immediately */
1830 NEXT();
1831 return;
1832 break;
1833 default:
1835 return;
1836 break;
1837 }
1838
1840 {
1841 NEXT();
1843 {
1847 NEXT();
1848 NOERR();
1849 break;
1854 NOERR();
1856 NOERR();
1857 break;
1858 default:
1860 return;
1861 break;
1862 }
1863 }
1864 else
1866
1867 /*
1868 * Ranges are unportable. Actually, standard C does guarantee that digits
1869 * are contiguous, but making that an exception is just too complicated.
1870 */
1874 NOERR();
1876}
1877
1878/*
1879 * scanplain - scan PLAIN contents of [. etc.
1880 *
1881 * Certain bits of trickery in regc_lex.c know that this code does not try
1882 * to look past the final bracket of the [. etc.
1883 */
1886{
1888
1890 NEXT();
1891
1894 {
1896 NEXT();
1897 }
1898
1900 NEXT();
1901
1903}
1904
1905/*
1906 * onechr - fill in arcs for a plain character, and possible case complements
1907 * This is mostly a shortcut for efficient handling of the common case.
1908 */
1909static void
1914{
1916 {
1918
1920 return;
1921 }
1922
1923 /* rats, need general case anyway... */
1925}
1926
1927/*
1928 * optimizebracket - see if bracket expression can be converted to RAINBOW
1929 *
1930 * Cases such as "[\s\S]" can produce a set of arcs of all colors, which we
1931 * can replace by a single RAINBOW arc for efficiency. (This might seem
1932 * like a silly way to write ".", but it's seemingly a common locution in
1933 * some other flavors of regex, so take the trouble to support it well.)
1934 */
1935static void
1939{
1944
1945 /*
1946 * Scan lp's out-arcs and transiently mark the mentioned colors. We
1947 * expect that all of lp's out-arcs are plain, non-RAINBOW arcs to rp.
1948 * (Note: there shouldn't be any pseudocolors yet, but check anyway.)
1949 */
1951 {
1958 }
1959
1960 /* Scan colors, clear transient marks, check for unmarked live colors */
1963 {
1968 }
1969
1970 /* Can't do anything if not all colors have arcs */
1972 return;
1973
1974 /* OK, drop existing arcs and replace with a rainbow */
1978}
1979
1980/*
1981 * wordchrs - set up word-chr list for word-boundary stuff, if needed
1982 *
1983 * The list is kept as a bunch of circular arcs on an otherwise-unused state.
1984 *
1985 * Note that this must not be called while we have any open subcolors,
1986 * else construction of the list would confuse color bookkeeping.
1987 * Hence, we can't currently apply a similar optimization in
1988 * charclass[complement](), as those need to be usable within bracket
1989 * expressions.
1990 */
1991static void
1993{
1996
1998 return; /* done already */
1999
2000 /* make dummy state to hang the cache arcs on */
2002 NOERR();
2003
2004 /* obtain possibly-cached cvec for \w characters */
2007 NOERR();
2008
2009 /* build the arcs; this may cause color splitting */
2010 subcolorcvec(v, cv, cstate, cstate);
2011 NOERR();
2012
2013 /* close new open subcolors to ensure the cache entry is self-contained */
2015 NOERR();
2016
2017 /* success! save the cache pointer */
2018 v->wordchrs = cstate;
2019}
2020
2021/*
2022 * processlacon - generate the NFA representation of a LACON
2023 *
2024 * In the general case this is just newlacon() + newarc(), but some cases
2025 * can be optimized.
2026 */
2027static void
2031 int latype,
2034{
2036 int n;
2037
2038 /*
2039 * Check for lookaround RE consisting of a single plain color arc (or set
2040 * of arcs); this would typically be a simple chr or a bracket expression.
2041 */
2043 switch (latype)
2044 {
2046 /* If lookahead RE is just colorset C, convert to AHEAD(C) */
2048 {
2050 return;
2051 }
2052 break;
2054 /* If lookahead RE is just colorset C, convert to AHEAD(^C)|$ */
2056 {
2060 return;
2061 }
2062 break;
2064 /* If lookbehind RE is just colorset C, convert to BEHIND(C) */
2066 {
2068 return;
2069 }
2070 break;
2072 /* If lookbehind RE is just colorset C, convert to BEHIND(^C)|^ */
2074 {
2078 return;
2079 }
2080 break;
2081 default:
2083 }
2084
2085 /* General case: we need a LACON subre and arc */
2086 n = newlacon(v, begin, end, latype);
2088}
2089
2090/*
2091 * subre - allocate a subre
2092 */
2099{
2101
2102 /*
2103 * Checking for stack overflow here is sufficient to protect parse() and
2104 * its recursive subroutines.
2105 */
2107 {
2110 }
2111
2114 else
2115 {
2118 {
2121 }
2123 v->treechain = ret;
2124 }
2125
2127
2132 ret->capno = 0;
2133 ret->backno = 0;
2140
2141 return ret;
2142}
2143
2144/*
2145 * freesubre - free a subRE subtree
2146 *
2147 * This frees child node(s) of the given subRE too,
2148 * but not its siblings.
2149 */
2150static void
2153{
2155 return;
2156
2159
2161}
2162
2163/*
2164 * freesubreandsiblings - free a subRE subtree
2165 *
2166 * This frees child node(s) of the given subRE too,
2167 * as well as any following siblings.
2168 */
2169static void
2172{
2174 {
2176
2179 }
2180}
2181
2182/*
2183 * freesrnode - free one node in a subRE subtree
2184 */
2185static void
2188{
2190 return;
2191
2197
2199 {
2200 /* we're still parsing, maybe we can reuse the subre */
2203 }
2204 else
2206}
2207
2208/*
2209 * removecaptures - remove unnecessary capture subREs
2210 *
2211 * If the caller said that it doesn't care about subexpression match data,
2212 * we may delete the "capture" markers on subREs that are not referenced
2213 * by any backrefs, and then simplify anything that's become non-messy.
2214 * Call this only if REG_NOSUB flag is set.
2215 */
2216static void
2219{
2221
2223
2224 /*
2225 * If this isn't itself a backref target, clear capno and tentatively
2226 * clear CAP flag.
2227 */
2229 {
2230 t->capno = 0;
2232 }
2233
2234 /* Now recurse to children */
2236 {
2238 /* Propagate child CAP flag back up, if it's still set */
2241 }
2242
2243 /*
2244 * If t now contains neither captures nor backrefs, there's no longer any
2245 * need to care where its sub-match boundaries are, so we can reduce it to
2246 * a simple DFA node. (Note in particular that MIXED child greediness is
2247 * not a hindrance here, so we don't use the MESSY() macro.)
2248 */
2250 {
2256 }
2257}
2258
2259/*
2260 * numst - number tree nodes (assigning "id" indexes)
2261 */
2262static int /* next number */
2265{
2268
2270
2276}
2277
2278/*
2279 * markst - mark tree nodes as INUSE
2280 *
2281 * Note: this is a great deal more subtle than it looks. During initial
2282 * parsing of a regex, all subres are linked into the treechain list;
2283 * discarded ones are also linked into the treefree list for possible reuse.
2284 * After we are done creating all subres required for a regex, we run markst()
2285 * then cleanst(), which results in discarding all subres not reachable from
2286 * v->tree. We then clear v->treechain, indicating that subres must be found
2287 * by descending from v->tree. This changes the behavior of freesubre(): it
2288 * will henceforth FREE() unwanted subres rather than sticking them into the
2289 * treefree list. (Doing that any earlier would result in dangling links in
2290 * the treechain list.) This all means that freev() will clean up correctly
2291 * if invoked before or after markst()+cleanst(); but it would not work if
2292 * called partway through this state conversion, so we mustn't error out
2293 * in or between these two functions.
2294 */
2295static void
2297{
2299
2301
2305}
2306
2307/*
2308 * cleanst - free any tree nodes not marked INUSE
2309 */
2310static void
2312{
2315
2317 {
2320 FREE(t);
2321 }
2324}
2325
2326/*
2327 * nfatree - turn a subRE subtree into a tree of compacted NFAs
2328 */
2329static long /* optimize results from top node */
2333{
2335
2337
2340
2342}
2343
2344/*
2345 * nfanode - do one NFA for nfatree or lacons
2346 *
2347 * If converttosearch is true, apply makesearch() to the NFA.
2348 */
2349static long /* optimize results */
2354{
2356 long ret = 0;
2357
2359
2360#ifdef REG_DEBUG
2362 {
2364
2367 }
2368#endif
2370 NOERRZ();
2381
2383 return ret;
2384}
2385
2386/*
2387 * newlacon - allocate a lookaround-constraint subRE
2388 */
2389static int /* lacon number */
2393 int latype)
2394{
2395 int n;
2398
2400 {
2401 n = 1; /* skip 0th */
2403 }
2404 else
2405 {
2406 n = v->nlacons;
2409 }
2411 {
2413 return 0;
2414 }
2416 v->nlacons = n + 1;
2417 sub = &v->lacons[n];
2422 return n;
2423}
2424
2425/*
2426 * freelacons - free lookaround-constraint subRE vector
2427 */
2428static void
2430 int n)
2431{
2434
2435 assert(n > 0);
2439 FREE(subs);
2440}
2441
2442/*
2443 * rfree - free a whole RE (insides of regfree)
2444 */
2445static void
2447{
2449
2451 return;
2452
2453 re->re_magic = 0; /* invalidate RE */
2455 re->re_guts = NULL;
2456 re->re_fns = NULL;
2458 {
2459 g->magic = 0;
2467 FREE(g);
2468 }
2469}
2470
2471/*
2472 * rstacktoodeep - check for stack getting dangerously deep
2473 *
2474 * Return nonzero to fail the operation with error code REG_ETOOBIG,
2475 * zero to keep going
2476 *
2477 * The current implementation is Postgres-specific. If we ever get around
2478 * to splitting the regex code out as a standalone library, there will need
2479 * to be some API to let applications define a callback function for this.
2480 */
2481static int
2483{
2485}
2486
2487#ifdef REG_DEBUG
2488
2489/*
2490 * dump - dump an RE in human-readable form
2491 */
2492static void
2493dump(regex_t *re,
2494 FILE *f)
2495{
2498
2501 REMAGIC);
2503 {
2505 return;
2506 }
2510 GUTSMAGIC);
2511
2515
2518 {
2521 }
2523 {
2526
2528 {
2531 break;
2534 break;
2537 break;
2540 break;
2541 default:
2543 break;
2544 }
2547 }
2550}
2551
2552/*
2553 * dumpst - dump a subRE tree
2554 */
2555static void
2557 FILE *f,
2559{
2562 else
2564 fflush(f);
2565}
2566
2567/*
2568 * stdump - recursive guts of dumpst
2569 */
2570static void
2572 FILE *f,
2574{
2577
2600 {
2605 }
2610 /* printing second child isn't necessary, but it is often helpful */
2616 {
2619 }
2623}
2624
2625/*
2626 * stid - identify a subtree node for dumping
2627 */
2628static const char * /* points to buf or constant string */
2632{
2633 /* big enough for hex int or decimal t->id? */
2635 return "unable";
2638 else
2641}
2642#endif /* REG_DEBUG */
2643
2644
2645#include "regc_lex.c"
2646#include "regc_color.c"
2647#include "regc_nfa.c"
2648#include "regc_cvec.c"
2649#include "regc_pg_locale.c"
2650#include "regc_locale.c"
static void freecvec(struct cvec *cv)
static void subcoloronechr(struct vars *v, chr ch, struct state *lp, struct state *rp, color *lastsubcolor)
#define REDUCE(x)
static void cparc(struct nfa *nfa, struct arc *oa, struct state *from, struct state *to)
static void subcolorcvec(struct vars *v, struct cvec *cv, struct state *lp, struct state *rp)
#define INF
static void copyouts(struct nfa *nfa, struct state *oldState, struct state *newState)
static struct cvec * newcvec(int nchrs, int nranges)
static void compact(struct nfa *nfa, struct cnfa *cnfa)
static void specialcolors(struct nfa *nfa)
static void freesubreandsiblings(struct vars *v, struct subre *sr)
Definition regcomp.c:2171
static void dupnfa(struct nfa *nfa, struct state *start, struct state *stop, struct state *from, struct state *to)
static void newarc(struct nfa *nfa, int t, color co, struct state *from, struct state *to)
static void repeat(struct vars *v, struct state *lp, struct state *rp, int m, int n)
Definition regcomp.c:1586
static int casecmp(const chr *x, const chr *y, size_t len)
static struct subre * parsebranch(struct vars *v, int stopper, int type, struct state *left, struct state *right, int partial)
Definition regcomp.c:785
static void freenfa(struct nfa *nfa)
static struct state * single_color_transition(struct state *s1, struct state *s2)
static struct nfa * newnfa(struct vars *v, struct colormap *cm, struct nfa *parent)
static void optimizebracket(struct vars *v, struct state *lp, struct state *rp)
Definition regcomp.c:1937
int pg_regcomp(regex_t *re, const chr *string, size_t len, int flags, Oid collation)
Definition regcomp.c:372
static enum char_classes lookupcclass(struct vars *v, const chr *startp, const chr *endp)
#define PAIR(x, y)
static void moveouts(struct nfa *nfa, struct state *oldState, struct state *newState)
static void freearc(struct nfa *nfa, struct arc *victim)
#define ARCV(t, val)
static void cloneouts(struct nfa *nfa, struct state *old, struct state *from, struct state *to, int type)
static struct subre * parseqatom(struct vars *v, int stopper, int type, struct state *lp, struct state *rp, struct subre *top)
Definition regcomp.c:838
static void freecm(struct colormap *cm)
static long optimize(struct nfa *nfa, FILE *f)
#define CNOERR()
static struct cvec * eclass(struct vars *v, chr c, int cases)
#define SOME
static void dropstate(struct nfa *nfa, struct state *s)
static void okcolors(struct nfa *nfa, struct colormap *cm)
static void initcm(struct vars *v, struct colormap *cm)
static chr newline(void)
static void charclass(struct vars *v, enum char_classes cls, struct state *lp, struct state *rp)
Definition regcomp.c:1494
static void bracket(struct vars *v, struct state *lp, struct state *rp)
Definition regcomp.c:1673
static void cbracket(struct vars *v, struct state *lp, struct state *rp)
Definition regcomp.c:1729
static int cmp(const chr *x, const chr *y, size_t len)
static struct cvec * cclasscvec(struct vars *v, enum char_classes cclasscode, int cases)
static long nfanode(struct vars *v, struct subre *t, int converttosearch, FILE *f)
Definition regcomp.c:2351
static void lexstart(struct vars *v)
static void nonword(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition regcomp.c:1458
static void delsub(struct nfa *nfa, struct state *lp, struct state *rp)
static void moveins(struct nfa *nfa, struct state *oldState, struct state *newState)
static void removeconstraints(struct nfa *nfa, struct state *start, struct state *stop)
static void charclasscomplement(struct vars *v, enum char_classes cls, struct state *lp, struct state *rp)
Definition regcomp.c:1518
static struct state * newstate(struct nfa *nfa)
static struct subre * parse(struct vars *v, int stopper, int type, struct state *init, struct state *final)
Definition regcomp.c:717
static int newlacon(struct vars *v, struct state *begin, struct state *end, int latype)
Definition regcomp.c:2391
static color subcolor(struct colormap *cm, chr c)
static void rainbow(struct nfa *nfa, struct colormap *cm, int type, color but, struct state *from, struct state *to)
static void colorcomplement(struct nfa *nfa, struct colormap *cm, int type, struct state *of, struct state *from, struct state *to)
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
static chr element(struct vars *v, const chr *startp, const chr *endp)
static struct cvec * allcases(struct vars *v, chr c)
static void processlacon(struct vars *v, struct state *begin, struct state *end, int latype, struct state *lp, struct state *rp)
Definition regcomp.c:2029
static void freestate(struct nfa *nfa, struct state *s)
static void dumpnfa(struct nfa *nfa, FILE *f)
static void brackpart(struct vars *v, struct state *lp, struct state *rp, bool *have_cclassc)
Definition regcomp.c:1763
static void onechr(struct vars *v, chr c, struct state *lp, struct state *rp)
Definition regcomp.c:1911
static void word(struct vars *v, int dir, struct state *lp, struct state *rp)
Definition regcomp.c:1476
static void freecnfa(struct cnfa *cnfa)
#define init()
Definition regguts.h:296
Definition regguts.h:177
Definition regguts.h:279
Definition regguts.h:531
Definition regguts.h:349
Definition regguts.h:323
Definition regguts.h:479
Definition regcomp.c:282
◆ COMPATIBLE
◆ DIGIT
◆ EAT
◆ ECLASS
◆ EMPTY
◆ EMPTYARC
◆ END
◆ EOS
◆ ERR
◆ INCOMPATIBLE
◆ INF
| #define INF 3 |
◆ INSIST
◆ ISERR
◆ LACON
◆ NEXT
◆ NOERR
◆ NOERRN
◆ NOERRZ
◆ NOTE
◆ NWBDRY
◆ PAIR
◆ PLAIN
◆ RANGE
◆ REDUCE
◆ REPLACEARC
◆ SATISFIED
◆ SBEGIN
◆ SEE
◆ SEND
◆ SOME
| #define SOME 2 |
◆ VERR
◆ VISERR
◆ WBDRY
Function Documentation
◆ addchr()
◆ addrange()
◆ allcases()
◆ allocarc()
◆ analyze()
◆ before()
◆ bracket()
Definition at line 1673 of file regcomp.c.
1676{
1677 /*
1678 * We can't process complemented char classes (e.g. \W) immediately while
1679 * scanning the bracket expression, else color bookkeeping gets confused.
1680 * Instead, remember whether we saw any in have_cclassc[], and process
1681 * them at the end.
1682 */
1686
1688
1690 NEXT();
1694
1695 /* close up open subcolors from the positive bracket elements */
1697 NOERR();
1698
1699 /* now handle any complemented elements */
1702 {
1704 {
1706 NOERR();
1708 }
1709 }
1710
1711 /*
1712 * If we had any complemented elements, see if we can optimize the bracket
1713 * into a rainbow. Since a complemented element is the only way a WHITE
1714 * arc could get into the result, there's no point in checking otherwise.
1715 */
1718}
References assert, brackpart(), charclasscomplement(), vars::cm, EOS, fb(), i, ISERR, NEXT, vars::nfa, NOERR, NUM_CCLASSES, okcolors(), optimizebracket(), and SEE.
Referenced by cbracket(), and parseqatom().
◆ brackpart()
|
static |
Definition at line 1763 of file regcomp.c.
1767{
1774
1775 /* parse something, get rid of special cases, take shortcuts */
1777 {
1780 return;
1781 break;
1784 NEXT();
1785 /* shortcut for ordinary chr (not range) */
1787 {
1789 return;
1790 }
1791 NOERR();
1792 break;
1797 NOERR();
1799 NOERR();
1800 break;
1805 NOERR();
1807 NOERR();
1809 NOERR();
1811 return;
1812 break;
1817 NOERR();
1819 NOERR();
1821 return;
1822 break;
1825 NEXT();
1826 return;
1827 break;
1829 /* we cannot call charclasscomplement() immediately */
1831 NEXT();
1832 return;
1833 break;
1834 default:
1836 return;
1837 break;
1838 }
1839
1841 {
1842 NEXT();
1844 {
1848 NEXT();
1849 NOERR();
1850 break;
1855 NOERR();
1857 NOERR();
1858 break;
1859 default:
1861 return;
1862 break;
1863 }
1864 }
1865 else
1867
1868 /*
1869 * Ranges are unportable. Actually, standard C does guarantee that digits
1870 * are contiguous, but making that an exception is just too complicated.
1871 */
1875 NOERR();
1877}
References CCLASS, CCLASSC, CCLASSS, vars::cflags, charclass(), COLLEL, eclass(), ECLASS, element(), ERR, fb(), INSIST, lookupcclass(), NEXT, vars::nexttype, vars::nextvalue, NOERR, NOTE, vars::now, onechr(), PLAIN, range(), RANGE, REG_ASSERT, REG_ECOLLATE, REG_ECTYPE, REG_ERANGE, REG_ICASE, REG_UUNPORT, scanplain(), SEE, and subcolorcvec().
Referenced by bracket().
◆ breakconstraintloop()
◆ brenext()
◆ carc_cmp()
◆ carcsort()
◆ casecmp()
◆ cbracket()
Definition at line 1729 of file regcomp.c.
1732{
1735
1736 NOERR();
1737 bracket(v, left, right);
1738
1739 /* in NLSTOP mode, ensure newline is not part of the result set */
1742 NOERR();
1743
1745
1746 /*
1747 * Easy part of complementing, and all there is to do since the MCCE code
1748 * was removed. Note that the result of colorcomplement() cannot be a
1749 * rainbow, since we don't allow empty brackets; so there's no point in
1750 * calling optimizebracket() again.
1751 */
1753 NOERR();
1757}
References assert, bracket(), vars::cflags, vars::cm, colorcomplement(), dropstate(), fb(), freestate(), newarc(), newstate(), vars::nfa, state::nins, vars::nlcolor, NOERR, PLAIN, and REG_NLSTOP.
Referenced by parseqatom().
◆ cclass_column_index()
◆ cclasscvec()
Referenced by charclass(), charclasscomplement(), and wordchrs().
◆ changearcsource()
◆ changearctarget()
◆ charclass()
|
static |
Definition at line 1494 of file regcomp.c.
1498{
1500
1501 /* obtain possibly-cached cvec for char class */
1504 NOERR();
1505
1506 /* build the arcs; this may cause color splitting */
1508}
References cclasscvec(), vars::cflags, fb(), NOERR, NOTE, REG_ICASE, REG_ULOCALE, and subcolorcvec().
Referenced by brackpart(), and parseqatom().
◆ charclasscomplement()
|
static |
Definition at line 1518 of file regcomp.c.
1522{
1525
1526 /* make dummy state to hang temporary arcs on */
1528 NOERR();
1529
1530 /* obtain possibly-cached cvec for char class */
1533 NOERR();
1534
1535 /* build arcs for char class; this may cause color splitting */
1536 subcolorcvec(v, cv, cstate, cstate);
1537 NOERR();
1538
1539 /* clean up any subcolors in the arc set */
1541 NOERR();
1542
1543 /* now build output arcs for the complement of the char class */
1545 NOERR();
1546
1547 /* clean up dummy state */
1549}
References cclasscvec(), vars::cflags, vars::cm, colorcomplement(), dropstate(), fb(), newstate(), vars::nfa, NOERR, NOTE, okcolors(), PLAIN, REG_ICASE, REG_ULOCALE, and subcolorcvec().
Referenced by bracket(), and parseqatom().
◆ check_in_colors_match()
◆ check_out_colors_match()
◆ checkmatchall()
◆ checkmatchall_recurse()
◆ chrnamed()
|
static |
◆ cleanst()
Definition at line 2312 of file regcomp.c.
References subre::chain, fb(), subre::flags, FREE, INUSE, next, vars::treechain, and vars::treefree.
Referenced by freev(), and pg_regcomp().
◆ cleanup()
◆ clearcvec()
◆ cleartraverse()
◆ cloneouts()
|
static |
Referenced by processlacon(), and word().
◆ clonesuccessorstates()
|
static |
◆ cmp()
◆ colorchain()
◆ colorcomplement()
|
static |
Referenced by cbracket(), charclasscomplement(), nonword(), and processlacon().
◆ combine()
◆ compact()
Referenced by nfanode(), and pg_regcomp().
◆ copyins()
◆ copyouts()
Referenced by makesearch().
◆ cparc()
|
static |
Referenced by makesearch().
◆ createarc()
|
static |
◆ delsub()
Referenced by parseqatom(), and repeat().
◆ deltraverse()
◆ dropstate()
Referenced by cbracket(), and charclasscomplement().
◆ dumpnfa()
◆ dupnfa()
|
static |
Referenced by nfanode(), parseqatom(), and repeat().
◆ duptraverse()
◆ eclass()
◆ element()
Referenced by brackpart().
◆ emptyreachable()
|
static |
◆ findarc()
◆ findconstraintloop()
◆ fixconstraintloops()
◆ fixempties()
◆ freearc()
Referenced by makesearch(), and optimizebracket().
◆ freecm()
◆ freecnfa()
Referenced by freelacons(), freesrnode(), and rfree().
◆ freecolor()
◆ freecvec()
◆ freelacons()
Definition at line 2430 of file regcomp.c.
References assert, subre::cnfa, FREE, freecnfa(), i, and NULLCNFA.
◆ freenfa()
◆ freesrnode()
Definition at line 2187 of file regcomp.c.
2189{
2191 return;
2192
2198
2200 {
2201 /* we're still parsing, maybe we can reuse the subre */
2204 }
2205 else
2207}
References fb(), FREE, freecnfa(), NULLCNFA, vars::treechain, and vars::treefree.
Referenced by freesubre(), parse(), and parseqatom().
◆ freestate()
◆ freesubre()
Definition at line 2152 of file regcomp.c.
2154{
2156 return;
2157
2160
2162}
References fb(), freesrnode(), and freesubreandsiblings().
Referenced by freesubreandsiblings(), freev(), parseqatom(), and rfree().
◆ freesubreandsiblings()
Definition at line 2171 of file regcomp.c.
2173{
2175 {
2177
2180 }
2181}
References fb(), freesubre(), next, and subre::sibling.
Referenced by freesubre(), parse(), parseqatom(), and removecaptures().
◆ freev()
Definition at line 592 of file regcomp.c.
References cleanst(), vars::cv, vars::cv2, vars::err, ERR, err(), fb(), FREE, freecvec(), freelacons(), freenfa(), freesubre(), vars::lacons, vars::nfa, vars::nlacons, vars::re, rfree(), vars::sub10, vars::subs, vars::tree, and vars::treechain.
Referenced by pg_regcomp().
◆ getcvec()
◆ hasconstraintout()
◆ hasnonemptyout()
◆ initcm()
◆ isconstraintarc()
◆ lexdigits()
◆ lexescape()
◆ lexstart()
Referenced by pg_regcomp().
◆ lookupcclass()
|
static |
Referenced by brackpart().
◆ makesearch()
Definition at line 621 of file regcomp.c.
623{
630
631 /* no loops are needed if it's anchored */
633 {
636 break;
637 }
639 {
640 /* add implicit .* in front */
642
643 /* and ^* and \A* too -- not always necessary, but harmless */
646
647 /*
648 * The pattern is still MATCHALL if it was before, but the max match
649 * length is now infinity.
650 */
653 }
654
655 /*
656 * Now here's the subtle part. Because many REs have no lookback
657 * constraints, often knowing when you were in the pre state tells you
658 * little; it's the next state(s) that are informative. But some of them
659 * may have other inarcs, i.e. it may be possible to make actual progress
660 * and then return to one of them. We must de-optimize such cases,
661 * splitting each such state into progress and no-progress states.
662 */
663
664 /* first, make a list of the states reachable from pre and elsewhere */
667 {
668 s = a->to;
670 {
672 break;
673 }
674
675 /*
676 * We want to mark states as being in the list already by having non
677 * NULL tmp fields, but we can't just store the old slist value in tmp
678 * because that doesn't work for the first such state. Instead, the
679 * first list entry gets its own address in tmp.
680 */
682 {
684 slist = s;
685 }
686 }
687
688 /* do the splits */
690 {
692 NOERR();
694 NOERR();
696 {
699 {
702 }
703 }
706 }
707}
References a, assert, b, nfa::bos, vars::cm, COLORLESS, copyouts(), cparc(), DUPINF, fb(), nfa::flags, freearc(), state::ins, MATCHALL, nfa::maxmatchall, newarc(), newstate(), NOERR, state::outs, PLAIN, nfa::pre, rainbow(), s2, and state::tmp.
Referenced by nfanode(), and pg_regcomp().
◆ markcanreach()
|
static |
◆ markreachable()
|
static |
◆ markst()
Definition at line 2297 of file regcomp.c.
2298{
2300
2302
2306}
References assert, subre::child, fb(), subre::flags, INUSE, and markst().
Referenced by markst(), and pg_regcomp().
◆ maxcolor()
◆ mergeins()
|
static |
◆ moresubs()
Definition at line 555 of file regcomp.c.
557{
559 size_t n;
560
563
565 {
570 }
571 else
574 {
576 return;
577 }
578 v->subs = p;
580 *p = NULL;
583}
References assert, ERR, fb(), MALLOC, vars::nsubs, REALLOC, REG_ESPACE, vars::sub10, vars::subs, and VS.
Referenced by parseqatom().
◆ moveins()
Referenced by parsebranch(), parseqatom(), and repeat().
◆ moveouts()
Referenced by parseqatom(), and repeat().
◆ newarc()
|
static |
Referenced by cbracket(), makesearch(), nonword(), optimizebracket(), and processlacon().
◆ newcolor()
◆ newcvec()
◆ newfstate()
◆ newhicolorcols()
◆ newhicolorrow()
◆ newlacon()
|
static |
Definition at line 2391 of file regcomp.c.
2395{
2396 int n;
2399
2401 {
2402 n = 1; /* skip 0th */
2404 }
2405 else
2406 {
2407 n = v->nlacons;
2410 }
2412 {
2414 return 0;
2415 }
2417 v->nlacons = n + 1;
2418 sub = &v->lacons[n];
2423 return n;
2424}
References subre::begin, subre::cnfa, subre::end, ERR, fb(), vars::lacons, subre::latype, MALLOC, vars::nlacons, REALLOC, REG_ESPACE, and ZAPCNFA.
Referenced by processlacon().
◆ newline()
Referenced by pg_regcomp().
◆ newnfa()
Referenced by nfanode(), and pg_regcomp().
◆ newstate()
Referenced by cbracket(), charclasscomplement(), makesearch(), parse(), parsebranch(), parseqatom(), repeat(), and wordchrs().
◆ newsub()
◆ next()
◆ nfanode()
Definition at line 2351 of file regcomp.c.
2355{
2357 long ret = 0;
2358
2360
2361#ifdef REG_DEBUG
2363 {
2365
2368 }
2369#endif
2371 NOERRZ();
2382
2384 return ret;
2385}
References assert, subre::begin, vars::cm, subre::cnfa, compact(), dupnfa(), subre::end, fb(), nfa::final, nfa::flags, fprintf, freenfa(), nfa::init, ISERR, makesearch(), newnfa(), vars::nfa, NOERRZ, optimize(), specialcolors(), and nfa::v.
Referenced by nfatree(), and pg_regcomp().
◆ nfatree()
Definition at line 2331 of file regcomp.c.
2334{
2336
2338
2341
2343}
References assert, subre::begin, subre::child, DISCARD, fb(), nfanode(), and nfatree().
Referenced by nfatree(), and pg_regcomp().
◆ nonword()
Definition at line 1458 of file regcomp.c.
1462{
1464
1469 /* (no need for special attention to \n) */
1470}
References AHEAD, assert, BEHIND, vars::cm, colorcomplement(), fb(), newarc(), vars::nfa, and vars::wordchrs.
Referenced by parseqatom().
◆ numst()
◆ okcolors()
Referenced by bracket(), charclasscomplement(), parseqatom(), pg_regcomp(), and wordchrs().
◆ onechr()
Definition at line 1911 of file regcomp.c.
1915{
1917 {
1919
1921 return;
1922 }
1923
1924 /* rats, need general case anyway... */
1926}
References allcases(), vars::cflags, COLORLESS, fb(), REG_ICASE, subcolorcvec(), and subcoloronechr().
Referenced by brackpart(), and parseqatom().
◆ optimize()
Referenced by nfanode(), and pg_regcomp().
◆ optimizebracket()
Definition at line 1937 of file regcomp.c.
1940{
1945
1946 /*
1947 * Scan lp's out-arcs and transiently mark the mentioned colors. We
1948 * expect that all of lp's out-arcs are plain, non-RAINBOW arcs to rp.
1949 * (Note: there shouldn't be any pseudocolors yet, but check anyway.)
1950 */
1952 {
1959 }
1960
1961 /* Scan colors, clear transient marks, check for unmarked live colors */
1964 {
1969 }
1970
1971 /* Can't do anything if not all colors have arcs */
1973 return;
1974
1975 /* OK, drop existing arcs and replace with a rainbow */
1979}
References a, assert, colormap::cd, CDEND, vars::cm, COLMARK, fb(), colordesc::flags, freearc(), newarc(), vars::nfa, PLAIN, PSEUDO, RAINBOW, and UNUSEDCOLOR.
Referenced by bracket().
◆ parse()
|
static |
Definition at line 717 of file regcomp.c.
722{
725
727
729 NOERRN();
731 do
732 { /* a branch */
736
739 NOERRN();
742 NOERRN();
744 NOERRN();
747 else
753
755 {
758 }
759
760 /* optimize out simple cases */
762 { /* only one branch */
766 }
768 { /* no interesting innards */
772 }
773
775}
References assert, EAT, EMPTYARC, EOS, ERR, fb(), freesrnode(), freesubreandsiblings(), init, LONGER, MESSY, newstate(), vars::nfa, NOERRN, parse(), parsebranch(), REG_EPAREN, SEE, type, and UP.
Referenced by parse(), parseqatom(), and pg_regcomp().
◆ parsebranch()
|
static |
Definition at line 785 of file regcomp.c.
791{
795
796 lp = left;
797 seencontent = 0;
799 NOERRN();
801 {
803 { /* implicit concat operator */
805 NOERRN();
807 }
808 seencontent = 1;
809
810 /* NB, recursion in parseqatom() may swallow rest of branch */
812 NOERRN();
813 }
814
816 { /* empty branch */
817 if (!partial)
820 EMPTYARC(left, right);
821 }
822
823 return t;
824}
References assert, EMPTYARC, EOS, fb(), moveins(), newstate(), vars::nfa, NOERRN, NOTE, parseqatom(), REG_UUNSPEC, SEE, and type.
Referenced by parse(), and parseqatom().
◆ parseqatom()
|
static |
Definition at line 838 of file regcomp.c.
844{
847
848#define ARCV(t, val) newarc(v->nfa, t, val, lp, rp)
849 int m,
850 n;
858 int f;
860
861 /* initial bookkeeping */
866
867 /* an atom or constraint... */
870 {
871 /* first, constraints, which end by returning */
872 case '^':
876 NEXT();
878 break;
879 case '$':
883 NEXT();
885 break;
889 NEXT();
891 break;
895 NEXT();
897 break;
898 case '<':
899 wordchrs(v);
901 NOERRN();
904 NEXT();
906 break;
907 case '>':
908 wordchrs(v);
910 NOERRN();
913 NEXT();
915 break;
917 wordchrs(v);
919 NOERRN();
923 NOERRN();
926 NEXT();
928 break;
930 wordchrs(v);
932 NOERRN();
936 NOERRN();
939 NEXT();
941 break;
944 NEXT();
947 NOERRN();
950 NOERRN();
952 NEXT();
955 break;
956 /* then errors, to get them out of the way */
957 case '*':
958 case '+':
959 case '?':
960 case '{':
963 break;
964 default:
967 break;
968 /* then plain characters, and minor variants on that theme */
969 case ')': /* unbalanced paren */
971 {
974 }
975 /* legal in EREs due to specification botch */
977 /* fall through into case PLAIN */
978 /* FALLTHROUGH */
982 NOERRN();
983 NEXT();
984 break;
985 case '[':
988 else
991 NEXT();
992 break;
996 NEXT();
997 break;
1000 /* charclasscomplement() did okcolors() internally */
1001 NEXT();
1002 break;
1003 case '.':
1007 NEXT();
1008 break;
1009 /* and finally the ugly stuff */
1010 case '(': /* value flags as capturing or non */
1013 {
1014 v->nsubexp++;
1018 }
1019 else
1021 NEXT();
1022
1023 /*
1024 * Make separate endpoint states to keep this sub-NFA distinct
1025 * from what surrounds it. We need to be sure that when we
1026 * duplicate the sub-NFA for a backref, we get the right
1027 * states/arcs and no others. In particular, letting a backref
1028 * duplicate the sub-NFA from lp to rp would be quite wrong,
1029 * because we may add quantification superstructure around this
1030 * atom below. (Perhaps we could skip the extra states for
1031 * non-capturing parens, but it seems not worth the trouble.)
1032 */
1035 NOERRN();
1036 /* We may not need these arcs, but keep things connected for now */
1039 NOERRN();
1042 NEXT();
1043 NOERRN();
1045 {
1047 {
1048 /* normal case: just mark the atom as capturing */
1051 }
1052 else
1053 {
1054 /* generate no-op wrapper node to handle "((x))" */
1056 NOERRN();
1059 atom = t;
1060 }
1063 }
1064 /* postpone everything else pending possible {0} */
1065 break;
1071 NOERRN();
1073 NOERRN();
1075 NOERRN();
1079 NEXT();
1080 break;
1081 }
1082
1083 /* ...and an atom may be followed by a quantifier */
1085 {
1086 case '*':
1087 m = 0;
1088 n = DUPINF;
1090 NEXT();
1091 break;
1092 case '+':
1093 m = 1;
1094 n = DUPINF;
1096 NEXT();
1097 break;
1098 case '?':
1099 m = 0;
1100 n = 1;
1102 NEXT();
1103 break;
1104 case '{':
1105 NEXT();
1106 m = scannum(v);
1108 {
1110 n = scannum(v);
1111 else
1112 n = DUPINF;
1113 if (m > n)
1114 {
1117 }
1118 /* {m,n} exercises preference, even if it's {m,m} */
1120 }
1121 else
1122 {
1123 n = m;
1124 /* {m} passes operand's preference through */
1125 qprefer = 0;
1126 }
1128 { /* catches errors too */
1131 }
1132 NEXT();
1133 break;
1134 default: /* no quantifier */
1135 m = n = 1;
1136 qprefer = 0;
1137 break;
1138 }
1139
1140 /* annoying special case: {0} or {0,0} cancels everything */
1141 if (m == 0 && n == 0)
1142 {
1143 /*
1144 * If we had capturing subexpression(s) within the atom, we don't want
1145 * to destroy them, because it's legal (if useless) to back-ref them
1146 * later. Hence, just unlink the atom from lp/rp and then ignore it.
1147 */
1149 {
1152 }
1153 else
1154 {
1155 /* Otherwise, we can clean up any subre infrastructure we made */
1159 }
1162 }
1163
1164 /* if not a messy case, avoid hard part */
1168 {
1169 if (!(m == 1 && n == 1))
1173 top->flags = f;
1175 }
1176
1177 /*
1178 * hard part: something messy
1179 *
1180 * That is, capturing parens, back reference, short/long clash, or an atom
1181 * with substructure containing one of those.
1182 */
1183
1184 /* now we'll need a subre for the contents even if they're boring */
1186 {
1188 NOERRN();
1189 }
1190
1191 /*
1192 * For what follows, we need the atom to have its own begin/end states
1193 * that are distinct from lp/rp, so that we can wrap iteration structure
1194 * around it. The parenthesized-atom case above already made suitable
1195 * states (and we don't want to modify a capturing subre, since it's
1196 * already recorded in v->subs[]). Otherwise, we need more states.
1197 */
1199 {
1202 NOERRN();
1205 atom->begin = s;
1207 }
1208 else
1209 {
1210 /* The atom's OK, but we must temporarily disconnect it from lp/rp */
1211 /* (this removes the EMPTY arcs we made above) */
1214 }
1215
1216 /*----------
1217 * Prepare a general-purpose state skeleton.
1218 *
1219 * In the no-backrefs case, we want this:
1220 *
1221 * [lp] ---> [s] ---prefix---> ---atom---> ---rest---> [rp]
1222 *
1223 * where prefix is some repetitions of atom, and "rest" is the remainder
1224 * of the branch. In the general case we need:
1225 *
1226 * [lp] ---> [s] ---iterator---> [s2] ---rest---> [rp]
1227 *
1228 * where the iterator wraps around the atom.
1229 *
1230 * We make the s state here for both cases; s2 is made below if needed
1231 *----------
1232 */
1234 NOERRN();
1236 NOERRN();
1237
1238 /* break remaining subRE into x{...} and what follows */
1240 NOERRN();
1243
1244 /*
1245 * Here we should recurse to fill t->child->sibling ... but we must
1246 * postpone that to the end. One reason is that t->child may be replaced
1247 * below, and we don't want to worry about its sibling link.
1248 */
1249
1250 /*
1251 * Convert top node to a concatenation of the prefix (top->child, covering
1252 * whatever we parsed previously) and remaining (t). Note that the prefix
1253 * could be empty, in which case this concatenation node is unnecessary.
1254 * To keep things simple, we operate in a general way for now, and get rid
1255 * of unnecessary subres below.
1256 */
1259 NOERRN();
1261 top->child->sibling = t;
1262 /* top->flags will get updated later */
1263
1264 /* if it's a backref, now is the time to replicate the subNFA */
1266 {
1270
1271 /*
1272 * And here's why the recursion got postponed: it must wait until the
1273 * skeleton is filled in, because it may hit a backref that wants to
1274 * copy the filled-in skeleton.
1275 */
1278 NOERRN();
1279
1280 /* The backref node's NFA should not enforce any constraints */
1282 NOERRN();
1283 }
1284
1285 /*
1286 * It's quantifier time. If the atom is just a backref, we'll let it deal
1287 * with quantifiers internally.
1288 */
1290 {
1291 /* special case: backrefs have internal quantifiers */
1293 /* just stuff everything into atom */
1298 /* rest of branch can be strung starting from atom->end */
1300 }
1301 else if (m == 1 && n == 1 &&
1302 (qprefer == 0 ||
1305 {
1306 /* no/vacuous quantifier: done */
1308 /* rest of branch can be strung starting from atom->end */
1310 }
1312 {
1313 /*
1314 * If there's no captures nor backrefs in the atom being repeated, we
1315 * don't really care where the submatches of the iteration are, so we
1316 * don't need an iteration node. Make a plain DFA node instead.
1317 */
1322 NOERRN();
1324 *atomp = t;
1325 /* rest of branch can be strung starting from t->end */
1327 }
1329 {
1330 /*
1331 * If there's no backrefs involved, we can turn x{m,n} into
1332 * x{m-1,n-1}x, with capturing parens in only the second x. This is
1333 * valid because we only care about capturing matches from the final
1334 * iteration of the quantifier. It's a win because we can implement
1335 * the backref-free left side as a plain DFA node, since we don't
1336 * really care where its submatches are.
1337 */
1343 NOERRN();
1345 NOERRN();
1347 *atomp = t;
1348 /* rest of branch can be strung starting from atom->end */
1350 }
1351 else
1352 {
1353 /* general case: need an iteration node */
1355 NOERRN();
1357 NOERRN();
1362 NOERRN();
1366 *atomp = t;
1367 /* rest of branch is to be strung from iteration's end state */
1368 }
1369
1370 /* and finally, look after that postponed recursion */
1373 {
1374 /* parse all the rest of the branch, and insert in t->child->sibling */
1376 NOERRN();
1378
1379 /* here's the promised update of the flags */
1382
1383 /* neither t nor top could be directly marked for capture as yet */
1386
1387 /*
1388 * At this point both top and t are concatenation (op == '.') subres,
1389 * and we have top->child = prefix of branch, top->child->sibling = t,
1390 * t->child = messy atom (with quantification superstructure if
1391 * needed), t->child->sibling = rest of branch.
1392 *
1393 * If the messy atom was the first thing in the branch, then
1394 * top->child is vacuous and we can get rid of one level of
1395 * concatenation.
1396 */
1399 {
1403 freesrnode(v, t);
1404 }
1405
1406 /*
1407 * Otherwise, it's possible that t->child is not messy in itself, but
1408 * we considered it messy because its greediness conflicts with what
1409 * preceded it. Then it could be that the combination of t->child and
1410 * the rest of the branch is also not messy, in which case we can get
1411 * rid of the child concatenation by merging t->child and the rest of
1412 * the branch into one plain DFA node.
1413 */
1417 {
1422 }
1423 }
1424 else
1425 {
1426 /*
1427 * There's nothing left in the branch, so we don't need the second
1428 * concatenation node 't'. Just link s2 straight to rp.
1429 */
1433 freesrnode(v, t);
1434
1435 /*
1436 * Again, it could be that top->child is vacuous (if the messy atom
1437 * was in fact the only thing in the branch). In that case we need no
1438 * concatenation at all; just replace top with top->child->sibling.
1439 */
1442 {
1447 top = t;
1448 }
1449 }
1450
1452}
References AHEAD, ARCV, assert, BACKR, BACKREF, subre::begin, BEHIND, bracket(), BRUSE, CAP, subre::capno, cbracket(), CCLASSC, CCLASSS, vars::cflags, charclass(), charclasscomplement(), subre::child, vars::cm, COLORLESS, COMBINE, delsub(), DIGIT, DUPINF, dupnfa(), EAT, EMPTYARC, subre::end, EOS, ERR, fb(), subre::flags, freesrnode(), freesubre(), freesubreandsiblings(), INSIST, ISERR, LACON, subre::latype, LONGER, subre::max, MESSY, subre::min, MIXED, moresubs(), moveins(), moveouts(), newstate(), NEXT, vars::nexttype, vars::nextvalue, vars::nfa, vars::nlcolor, NOERRN, nonword(), NOTE, vars::nsubexp, vars::nsubs, NWBDRY, okcolors(), onechr(), subre::op, parse(), parsebranch(), PLAIN, PREF, processlacon(), rainbow(), REG_ADVANCED, REG_ASSERT, REG_BADBR, REG_BADRPT, REG_EPAREN, REG_ESUBREG, REG_EXTENDED, REG_NLANCH, REG_NLSTOP, REG_UPBOTCH, removeconstraints(), repeat(), s2, SBEGIN, scannum(), SEE, SEND, SHORTER, subre::sibling, vars::subs, type, UP, WBDRY, word(), and wordchrs().
Referenced by parsebranch().
◆ pg_regcomp()
Definition at line 372 of file regcomp.c.
377{
383
384#ifdef REG_DEBUG
386#else
388#endif
389
390#define CNOERR() { if (ISERR()) return freev(v, v->err); }
391
392 /* sanity checks */
393
401
402 /* Initialize locale-dependent support */
403 pg_set_regex_collation(collation);
404
405 /* initial setup (after which freev() is callable) */
406 v->re = re;
409 v->err = 0;
410 v->cflags = flags;
411 v->nsubexp = 0;
413 v->nsubs = 10;
426 v->nlacons = 0;
427 v->spaceused = 0;
428 re->re_magic = REMAGIC;
429 re->re_info = 0; /* bits get set during parse */
431 re->re_collation = collation;
432 re->re_guts = NULL;
434
435 /* more complex setup, malloced things */
444 g->nlacons = 0;
447 CNOERR();
448 /* set up a reasonably-sized transient cvec for getcvec usage */
452
453 /* parsing */
456 {
457 /* assign newline a unique color */
460 }
461 CNOERR();
464 CNOERR();
466
467 /* finish setup of nfa and its subre tree */
469 CNOERR();
470#ifdef REG_DEBUG
472 {
476 }
477#endif
482 cleanst(v);
483#ifdef REG_DEBUG
485 {
488 }
489#endif
490
491 /* build compacted NFAs for tree and lacons */
493 CNOERR();
496 {
498
499#ifdef REG_DEBUG
502#endif
503
504 /* Prepend .* to pattern if it's a lookbehind LACON */
506 }
507 CNOERR();
510
511 /* build compacted NFAs for tree, lacons, fast search */
512#ifdef REG_DEBUG
515#endif
516 /* can sacrifice main NFA now, so use it as work area */
518 CNOERR();
520 CNOERR();
522 CNOERR();
523
524 /* looks okay, package it up */
525 re->re_nsub = v->nsubexp;
529 g->info = re->re_info;
530 g->nsub = re->re_nsub;
538
539#ifdef REG_DEBUG
541 {
542 dump(re, stdout);
543 fflush(stdout);
544 }
545#endif
546
549}
References assert, casecmp(), vars::cflags, guts::cflags, cleanst(), vars::cm, guts::cmap, cmp(), CNOERR, COLORLESS, compact(), vars::cv, vars::cv2, debug, DISCARD, dumpnfa(), EOS, vars::err, fb(), nfa::final, subre::flags, fprintf, freev(), functions, GUTSMAGIC, i, guts::info, nfa::init, initcm(), j, vars::lacons, guts::lacons, LATYPE_IS_AHEAD, len, lexstart(), guts::magic, makesearch(), MALLOC, markst(), newcvec(), newline(), newnfa(), vars::nfa, nfanode(), nfatree(), vars::nlacons, guts::nlacons, vars::nlcolor, NOTE, vars::now, guts::nsub, vars::nsubexp, vars::nsubs, vars::ntree, guts::ntree, numst(), okcolors(), optimize(), parse(), pg_set_regex_collation(), PLAIN, vars::re, REG_ADVANCED, REG_ADVF, REG_DUMP, REG_ESPACE, REG_EXPANDED, REG_EXTENDED, REG_ICASE, REG_INVARG, REG_NEWLINE, REG_NLANCH, REG_NLSTOP, REG_NOSUB, REG_PROGRESS, REG_QUOTE, REG_USHORTEST, REMAGIC, removecaptures(), guts::search, SEE, SHORTER, vars::spaceused, specialcolors(), vars::stop, vars::sub10, subcolor(), vars::subs, vars::tree, guts::tree, vars::treechain, vars::treefree, VS, vars::wordchrs, and ZAPCNFA.
Referenced by NIAddAffix(), RE_compile(), RE_compile_and_cache(), regcomp_auth_token(), and test_re_compile().
◆ prefixes()
◆ processlacon()
|
static |
Definition at line 2029 of file regcomp.c.
2035{
2037 int n;
2038
2039 /*
2040 * Check for lookaround RE consisting of a single plain color arc (or set
2041 * of arcs); this would typically be a simple chr or a bracket expression.
2042 */
2044 switch (latype)
2045 {
2047 /* If lookahead RE is just colorset C, convert to AHEAD(C) */
2049 {
2051 return;
2052 }
2053 break;
2055 /* If lookahead RE is just colorset C, convert to AHEAD(^C)|$ */
2057 {
2061 return;
2062 }
2063 break;
2065 /* If lookbehind RE is just colorset C, convert to BEHIND(C) */
2067 {
2069 return;
2070 }
2071 break;
2073 /* If lookbehind RE is just colorset C, convert to BEHIND(^C)|^ */
2075 {
2079 return;
2080 }
2081 break;
2082 default:
2084 }
2085
2086 /* General case: we need a LACON subre and arc */
2087 n = newlacon(v, begin, end, latype);
2089}
References AHEAD, assert, BEHIND, cloneouts(), vars::cm, colorcomplement(), fb(), LACON, LATYPE_AHEAD_NEG, LATYPE_AHEAD_POS, LATYPE_BEHIND_NEG, LATYPE_BEHIND_POS, newarc(), newlacon(), vars::nfa, NOTREACHED, s1, and single_color_transition().
Referenced by parseqatom().
◆ pseudocolor()
◆ pull()
◆ pullback()
◆ push()
◆ pushfwd()
◆ rainbow()
|
static |
Referenced by makesearch(), and parseqatom().
◆ range()
Referenced by brackpart().
◆ regc_wc_isalnum()
◆ regc_wc_isalpha()
◆ regc_wc_isdigit()
◆ regc_wc_isgraph()
◆ regc_wc_islower()
◆ regc_wc_isprint()
◆ regc_wc_ispunct()
◆ regc_wc_isspace()
◆ regc_wc_isupper()
◆ regc_wc_isword()
◆ regc_wc_tolower()
◆ regc_wc_toupper()
◆ removecantmatch()
◆ removecaptures()
Definition at line 2218 of file regcomp.c.
2220{
2222
2224
2225 /*
2226 * If this isn't itself a backref target, clear capno and tentatively
2227 * clear CAP flag.
2228 */
2230 {
2231 t->capno = 0;
2233 }
2234
2235 /* Now recurse to children */
2237 {
2239 /* Propagate child CAP flag back up, if it's still set */
2242 }
2243
2244 /*
2245 * If t now contains neither captures nor backrefs, there's no longer any
2246 * need to care where its sub-match boundaries are, so we can reduce it to
2247 * a simple DFA node. (Note in particular that MIXED child greediness is
2248 * not a hindrance here, so we don't use the MESSY() macro.)
2249 */
2251 {
2257 }
2258}
References assert, BACKR, BRUSE, CAP, subre::capno, subre::child, fb(), subre::flags, freesubreandsiblings(), subre::op, and removecaptures().
Referenced by pg_regcomp(), and removecaptures().
◆ removeconstraints()
|
static |
Referenced by parseqatom().
◆ removetraverse()
◆ repeat()
Definition at line 1586 of file regcomp.c.
1591{
1592#define SOME 2
1593#define INF 3
1594#define PAIR(x, y) ((x)*4 + (y))
1595#define REDUCE(x) ( ((x) == DUPINF) ? INF : (((x) > 1) ? SOME : (x)) )
1600
1602 {
1606 break;
1609 break;
1612 NOERR();
1614 break;
1617 NOERR();
1622 break;
1624 break;
1627 NOERR();
1630 NOERR();
1632 NOERR();
1634 break;
1638 NOERR();
1644 break;
1647 NOERR();
1650 NOERR();
1652 break;
1655 NOERR();
1658 NOERR();
1660 break;
1661 default:
1663 break;
1664 }
1665}
References delsub(), dupnfa(), EMPTYARC, ERR, fb(), INF, moveins(), moveouts(), newstate(), vars::nfa, NOERR, PAIR, REDUCE, REG_ASSERT, repeat(), s2, and SOME.
Referenced by in_grouping(), in_grouping_b(), in_grouping_b_U(), in_grouping_U(), out_grouping(), out_grouping_b(), out_grouping_b_U(), out_grouping_U(), parseqatom(), and repeat().
◆ rfree()
Definition at line 2447 of file regcomp.c.
2448{
2450
2452 return;
2453
2454 re->re_magic = 0; /* invalidate RE */
2456 re->re_guts = NULL;
2457 re->re_fns = NULL;
2459 {
2460 g->magic = 0;
2468 FREE(g);
2469 }
2470}
References guts::cmap, fb(), FREE, freecm(), freecnfa(), freelacons(), freesubre(), guts::lacons, guts::magic, guts::nlacons, NULLCNFA, REMAGIC, guts::search, and guts::tree.
Referenced by freev().
◆ rstacktoodeep()
Definition at line 2483 of file regcomp.c.
References stack_is_too_deep().
◆ scannum()
◆ scanplain()
◆ single_color_transition()
Referenced by processlacon().
◆ skip()
◆ sortins()
◆ sortins_cmp()
◆ sortouts()
◆ sortouts_cmp()
◆ specialcolors()
◆ subcolor()
◆ subcolorcvec()
|
static |
Referenced by brackpart(), charclass(), charclasscomplement(), onechr(), and wordchrs().
◆ subcolorhi()
◆ subcoloronechr()
|
static |
Referenced by onechr().
◆ subcoloronerange()
|
static |
◆ subcoloronerow()
|
static |
◆ subre()
|
static |
Definition at line 2095 of file regcomp.c.
2100{
2102
2103 /*
2104 * Checking for stack overflow here is sufficient to protect parse() and
2105 * its recursive subroutines.
2106 */
2108 {
2111 }
2112
2115 else
2116 {
2119 {
2122 }
2124 v->treechain = ret;
2125 }
2126
2128
2133 ret->capno = 0;
2134 ret->backno = 0;
2141
2142 return ret;
2143}
References assert, subre::backno, subre::begin, subre::capno, subre::chain, subre::child, subre::cnfa, subre::end, ERR, fb(), subre::flags, subre::id, subre::latype, MALLOC, subre::max, subre::min, subre::op, vars::re, REG_ESPACE, REG_ETOOBIG, subre::sibling, STACK_TOO_DEEP, vars::treechain, vars::treefree, and ZAPCNFA.
◆ uncolorchain()
◆ word()
Definition at line 1476 of file regcomp.c.
1480{
1483 /* (no need for special attention to \n) */
1484}
References AHEAD, assert, BEHIND, cloneouts(), fb(), vars::nfa, and vars::wordchrs.
Referenced by _metaphone(), addNorm(), AddStem(), addToResult(), byword(), CheckAffix(), CheckCompoundAffixes(), ciprefix(), cmpspell(), compareWORD(), daitch_mokotoff_coding(), dxsyn_lexize(), FindAffixes(), FindWord(), hlfinditem(), itsabbr(), Lookahead(), NIAddSpell(), NINormalizeWord(), NormalizeSubWord(), parseqatom(), pg_leftmost_one_pos32(), pg_leftmost_one_pos64(), pg_popcount32(), pg_popcount32_portable(), pg_popcount64(), pg_popcount64_portable(), pg_rightmost_one_pos32(), pg_rightmost_one_pos64(), pg_rotate_left32(), pg_rotate_right32(), plpgsql_parse_word(), SplitToVariants(), TidStoreSetBlockOffsets(), and unicode_to_utf8word().
◆ wordchrs()
Definition at line 1993 of file regcomp.c.
1994{
1997
1999 return; /* done already */
2000
2001 /* make dummy state to hang the cache arcs on */
2003 NOERR();
2004
2005 /* obtain possibly-cached cvec for \w characters */
2008 NOERR();
2009
2010 /* build the arcs; this may cause color splitting */
2011 subcolorcvec(v, cv, cstate, cstate);
2012 NOERR();
2013
2014 /* close new open subcolors to ensure the cache entry is self-contained */
2016 NOERR();
2017
2018 /* success! save the cache pointer */
2019 v->wordchrs = cstate;
2020}
References CC_WORD, cclasscvec(), vars::cflags, vars::cm, fb(), newstate(), vars::nfa, NOERR, NOTE, okcolors(), REG_ICASE, REG_ULOCALE, subcolorcvec(), and vars::wordchrs.
Referenced by parseqatom().
Variable Documentation
◆ functions
Initial value:
Definition at line 358 of file regcomp.c.
358 {
361};
Referenced by _outRangeTblEntry(), _readRangeTblEntry(), btadjustmembers(), create_functionscan_plan(), ExplainNode(), ginadjustmembers(), gistadjustmembers(), hashadjustmembers(), make_functionscan(), pg_regcomp(), and spgadjustmembers().
