diff --git a/contrib/pg_trgm/trgm_regexp.c b/contrib/pg_trgm/trgm_regexp.c index 1e4f0121f3..fcf03de32d 100644 --- a/contrib/pg_trgm/trgm_regexp.c +++ b/contrib/pg_trgm/trgm_regexp.c @@ -282,8 +282,8 @@ typedef struct typedef int TrgmColor; /* We assume that colors returned by the regexp engine cannot be these: */ -#define COLOR_UNKNOWN (-1) -#define COLOR_BLANK (-2) +#define COLOR_UNKNOWN (-3) +#define COLOR_BLANK (-4) typedef struct { @@ -780,7 +780,8 @@ getColorInfo(regex_t *regex, TrgmNFA *trgmNFA) palloc0(colorsCount * sizeof(TrgmColorInfo)); /* - * Loop over colors, filling TrgmColorInfo about each. + * Loop over colors, filling TrgmColorInfo about each. Note we include + * WHITE (0) even though we know it'll be reported as non-expandable. */ for (i = 0; i < colorsCount; i++) { @@ -1098,9 +1099,9 @@ addKey(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key) /* Add enter key to this state */ addKeyToQueue(trgmNFA, &destKey); } - else + else if (arc->co >= 0) { - /* Regular color */ + /* Regular color (including WHITE) */ TrgmColorInfo *colorInfo = &trgmNFA->colorInfo[arc->co]; if (colorInfo->expandable) @@ -1156,6 +1157,14 @@ addKey(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key) addKeyToQueue(trgmNFA, &destKey); } } + else + { + /* RAINBOW: treat as unexpandable color */ + destKey.prefix.colors[0] = COLOR_UNKNOWN; + destKey.prefix.colors[1] = COLOR_UNKNOWN; + destKey.nstate = arc->to; + addKeyToQueue(trgmNFA, &destKey); + } } pfree(arcs); @@ -1216,10 +1225,10 @@ addArcs(TrgmNFA *trgmNFA, TrgmState *state) /* * Ignore non-expandable colors; addKey already handled the case. * - * We need no special check for begin/end pseudocolors here. We - * don't need to do any processing for them, and they will be - * marked non-expandable since the regex engine will have reported - * them that way. + * We need no special check for WHITE or begin/end pseudocolors + * here. We don't need to do any processing for them, and they + * will be marked non-expandable since the regex engine will have + * reported them that way. */ if (!colorInfo->expandable) continue; diff --git a/src/backend/regex/README b/src/backend/regex/README index f08aab69e3..cc1834b89c 100644 --- a/src/backend/regex/README +++ b/src/backend/regex/README @@ -261,6 +261,18 @@ and the NFA has these arcs: states 4 -> 5 on color 2 ("x" only) which can be seen to be a correct representation of the regex. +There is one more complexity, which is how to handle ".", that is a +match-anything atom. We used to do that by generating a "rainbow" +of arcs of all live colors between the two NFA states before and after +the dot. That's expensive in itself when there are lots of colors, +and it also typically adds lots of follow-on arc-splitting work for the +color splitting logic. Now we handle this case by generating a single arc +labeled with the special color RAINBOW, meaning all colors. Such arcs +never need to be split, so they help keep NFAs small in this common case. +(Note: this optimization doesn't help in REG_NLSTOP mode, where "." is +not supposed to match newline. In that case we still handle "." by +generating an almost-rainbow of all colors except newline's color.) + Given this summary, we can see we need the following operations for colors: @@ -349,6 +361,8 @@ The possible arc types are: PLAIN arcs, which specify matching of any character of a given "color" (see above). These are dumped as "[color_number]->to_state". + In addition there can be "rainbow" PLAIN arcs, which are dumped as + "[*]->to_state". EMPTY arcs, which specify a no-op transition to another state. These are dumped as "->to_state". @@ -356,11 +370,11 @@ The possible arc types are: AHEAD constraints, which represent a "next character must be of this color" constraint. AHEAD differs from a PLAIN arc in that the input character is not consumed when crossing the arc. These are dumped as - ">color_number>->to_state". + ">color_number>->to_state", or possibly ">*>->to_state". BEHIND constraints, which represent a "previous character must be of this color" constraint, which likewise consumes no input. These are - dumped as "to_state". + dumped as "to_state", or possibly "<*<->to_state". '^' arcs, which specify a beginning-of-input constraint. These are dumped as "^0->to_state" or "^1->to_state" for beginning-of-string and diff --git a/src/backend/regex/regc_color.c b/src/backend/regex/regc_color.c index f5a4151757..0864011cce 100644 --- a/src/backend/regex/regc_color.c +++ b/src/backend/regex/regc_color.c @@ -977,6 +977,7 @@ colorchain(struct colormap *cm, { struct colordesc *cd = &cm->cd[a->co]; + assert(a->co >= 0); if (cd->arcs != NULL) cd->arcs->colorchainRev = a; a->colorchain = cd->arcs; @@ -994,6 +995,7 @@ uncolorchain(struct colormap *cm, struct colordesc *cd = &cm->cd[a->co]; struct arc *aa = a->colorchainRev; + assert(a->co >= 0); if (aa == NULL) { assert(cd->arcs == a); @@ -1012,6 +1014,9 @@ uncolorchain(struct colormap *cm, /* * rainbow - add arcs of all full colors (but one) between specified states + * + * If there isn't an exception color, we now generate just a single arc + * labeled RAINBOW, saving lots of arc-munging later on. */ static void rainbow(struct nfa *nfa, @@ -1025,6 +1030,13 @@ rainbow(struct nfa *nfa, struct colordesc *end = CDEND(cm); color co; + if (but == COLORLESS) + { + newarc(nfa, type, RAINBOW, from, to); + return; + } + + /* Gotta do it the hard way. Skip subcolors, pseudocolors, and "but" */ for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++) if (!UNUSEDCOLOR(cd) && cd->sub != co && co != but && !(cd->flags & PSEUDO)) @@ -1034,13 +1046,16 @@ rainbow(struct nfa *nfa, /* * colorcomplement - add arcs of complementary colors * + * We add arcs of all colors that are not pseudocolors and do not match + * any of the "of" state's PLAIN outarcs. + * * The calling sequence ought to be reconciled with cloneouts(). */ static void colorcomplement(struct nfa *nfa, struct colormap *cm, int type, - struct state *of, /* complements of this guy's PLAIN outarcs */ + struct state *of, struct state *from, struct state *to) { @@ -1049,6 +1064,11 @@ colorcomplement(struct nfa *nfa, color co; assert(of != from); + + /* A RAINBOW arc matches all colors, making the complement empty */ + if (findarc(of, PLAIN, RAINBOW) != NULL) + return; + for (cd = cm->cd, co = 0; cd < end && !CISERR(); cd++, co++) if (!UNUSEDCOLOR(cd) && !(cd->flags & PSEUDO)) if (findarc(of, PLAIN, co) == NULL) diff --git a/src/backend/regex/regc_nfa.c b/src/backend/regex/regc_nfa.c index 92c9c4d795..1ac030570d 100644 --- a/src/backend/regex/regc_nfa.c +++ b/src/backend/regex/regc_nfa.c @@ -271,6 +271,11 @@ destroystate(struct nfa *nfa, * * This function checks to make sure that no duplicate arcs are created. * In general we never want duplicates. + * + * However: in principle, a RAINBOW arc is redundant with any plain arc + * (unless that arc is for a pseudocolor). But we don't try to recognize + * that redundancy, either here or in allied operations such as moveins(). + * The pseudocolor consideration makes that more costly than it seems worth. */ static void newarc(struct nfa *nfa, @@ -1170,6 +1175,9 @@ copyouts(struct nfa *nfa, /* * cloneouts - copy out arcs of a state to another state pair, modifying type + * + * This is only used to convert PLAIN arcs to AHEAD/BEHIND arcs, which share + * the same interpretation of "co". It wouldn't be sensible with LACONs. */ static void cloneouts(struct nfa *nfa, @@ -1181,9 +1189,13 @@ cloneouts(struct nfa *nfa, struct arc *a; assert(old != from); + assert(type == AHEAD || type == BEHIND); for (a = old->outs; a != NULL; a = a->outchain) + { + assert(a->type == PLAIN); newarc(nfa, type, a->co, from, to); + } } /* @@ -1597,7 +1609,7 @@ pull(struct nfa *nfa, for (a = from->ins; a != NULL && !NISERR(); a = nexta) { nexta = a->inchain; - switch (combine(con, a)) + switch (combine(nfa, con, a)) { case INCOMPATIBLE: /* destroy the arc */ freearc(nfa, a); @@ -1624,6 +1636,10 @@ pull(struct nfa *nfa, cparc(nfa, a, s, to); freearc(nfa, a); break; + case REPLACEARC: /* replace arc's color */ + newarc(nfa, a->type, con->co, a->from, to); + freearc(nfa, a); + break; default: assert(NOTREACHED); break; @@ -1764,7 +1780,7 @@ push(struct nfa *nfa, for (a = to->outs; a != NULL && !NISERR(); a = nexta) { nexta = a->outchain; - switch (combine(con, a)) + switch (combine(nfa, con, a)) { case INCOMPATIBLE: /* destroy the arc */ freearc(nfa, a); @@ -1791,6 +1807,10 @@ push(struct nfa *nfa, cparc(nfa, a, from, s); freearc(nfa, a); break; + case REPLACEARC: /* replace arc's color */ + newarc(nfa, a->type, con->co, from, a->to); + freearc(nfa, a); + break; default: assert(NOTREACHED); break; @@ -1810,9 +1830,11 @@ push(struct nfa *nfa, * #def INCOMPATIBLE 1 // destroys arc * #def SATISFIED 2 // constraint satisfied * #def COMPATIBLE 3 // compatible but not satisfied yet + * #def REPLACEARC 4 // replace arc's color with constraint color */ static int -combine(struct arc *con, +combine(struct nfa *nfa, + struct arc *con, struct arc *a) { #define CA(ct,at) (((ct)<co == a->co) return SATISFIED; + if (con->co == RAINBOW) + { + /* con is satisfied unless arc's color is a pseudocolor */ + if (!(nfa->cm->cd[a->co].flags & PSEUDO)) + return SATISFIED; + } + else if (a->co == RAINBOW) + { + /* con is incompatible if it's for a pseudocolor */ + if (nfa->cm->cd[con->co].flags & PSEUDO) + return INCOMPATIBLE; + /* otherwise, constraint constrains arc to be only its color */ + return REPLACEARC; + } return INCOMPATIBLE; break; case CA('^', '^'): /* collision, similar constraints */ case CA('$', '$'): - case CA(AHEAD, AHEAD): + if (con->co == a->co) /* true duplication */ + return SATISFIED; + return INCOMPATIBLE; + break; + case CA(AHEAD, AHEAD): /* collision, similar constraints */ case CA(BEHIND, BEHIND): if (con->co == a->co) /* true duplication */ return SATISFIED; + if (con->co == RAINBOW) + { + /* con is satisfied unless arc's color is a pseudocolor */ + if (!(nfa->cm->cd[a->co].flags & PSEUDO)) + return SATISFIED; + } + else if (a->co == RAINBOW) + { + /* con is incompatible if it's for a pseudocolor */ + if (nfa->cm->cd[con->co].flags & PSEUDO) + return INCOMPATIBLE; + /* otherwise, constraint constrains arc to be only its color */ + return REPLACEARC; + } return INCOMPATIBLE; break; case CA('^', BEHIND): /* collision, dissimilar constraints */ @@ -2895,6 +2949,7 @@ compact(struct nfa *nfa, break; case LACON: assert(s->no != cnfa->pre); + assert(a->co >= 0); ca->co = (color) (cnfa->ncolors + a->co); ca->to = a->to->no; ca++; @@ -2902,7 +2957,7 @@ compact(struct nfa *nfa, break; default: NERR(REG_ASSERT); - break; + return; } carcsort(first, ca - first); ca->co = COLORLESS; @@ -3068,13 +3123,22 @@ dumparc(struct arc *a, switch (a->type) { case PLAIN: - fprintf(f, "[%ld]", (long) a->co); + if (a->co == RAINBOW) + fprintf(f, "[*]"); + else + fprintf(f, "[%ld]", (long) a->co); break; case AHEAD: - fprintf(f, ">%ld>", (long) a->co); + if (a->co == RAINBOW) + fprintf(f, ">*>"); + else + fprintf(f, ">%ld>", (long) a->co); break; case BEHIND: - fprintf(f, "<%ld<", (long) a->co); + if (a->co == RAINBOW) + fprintf(f, "<*<"); + else + fprintf(f, "<%ld<", (long) a->co); break; case LACON: fprintf(f, ":%ld:", (long) a->co); @@ -3161,7 +3225,9 @@ dumpcstate(int st, pos = 1; for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++) { - if (ca->co < cnfa->ncolors) + if (ca->co == RAINBOW) + fprintf(f, "\t[*]->%d", ca->to); + else if (ca->co < cnfa->ncolors) fprintf(f, "\t[%ld]->%d", (long) ca->co, ca->to); else fprintf(f, "\t:%ld:->%d", (long) (ca->co - cnfa->ncolors), ca->to); diff --git a/src/backend/regex/regcomp.c b/src/backend/regex/regcomp.c index 91078dcd80..5956b86026 100644 --- a/src/backend/regex/regcomp.c +++ b/src/backend/regex/regcomp.c @@ -158,7 +158,8 @@ static int push(struct nfa *, struct arc *, struct state **); #define INCOMPATIBLE 1 /* destroys arc */ #define SATISFIED 2 /* constraint satisfied */ #define COMPATIBLE 3 /* compatible but not satisfied yet */ -static int combine(struct arc *, struct arc *); +#define REPLACEARC 4 /* replace arc's color with constraint color */ +static int combine(struct nfa *nfa, struct arc *con, struct arc *a); static void fixempties(struct nfa *, FILE *); static struct state *emptyreachable(struct nfa *, struct state *, struct state *, struct arc **); @@ -289,9 +290,11 @@ struct vars #define SBEGIN 'A' /* beginning of string (even if not BOL) */ #define SEND 'Z' /* end of string (even if not EOL) */ -/* is an arc colored, and hence on a color chain? */ +/* is an arc colored, and hence should belong to a color chain? */ +/* the test on "co" eliminates RAINBOW arcs, which we don't bother to chain */ #define COLORED(a) \ - ((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND) + ((a)->co >= 0 && \ + ((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND)) /* static function list */ @@ -1390,7 +1393,8 @@ bracket(struct vars *v, * cbracket - handle complemented bracket expression * We do it by calling bracket() with dummy endpoints, and then complementing * the result. The alternative would be to invoke rainbow(), and then delete - * arcs as the b.e. is seen... but that gets messy. + * arcs as the b.e. is seen... but that gets messy, and is really quite + * infeasible now that rainbow() just puts out one RAINBOW arc. */ static void cbracket(struct vars *v, diff --git a/src/backend/regex/rege_dfa.c b/src/backend/regex/rege_dfa.c index 5695e158a5..32be2592c5 100644 --- a/src/backend/regex/rege_dfa.c +++ b/src/backend/regex/rege_dfa.c @@ -612,6 +612,7 @@ miss(struct vars *v, unsigned h; struct carc *ca; struct sset *p; + int ispseudocolor; int ispost; int noprogress; int gotstate; @@ -643,13 +644,15 @@ miss(struct vars *v, */ for (i = 0; i < d->wordsper; i++) d->work[i] = 0; /* build new stateset bitmap in d->work */ + ispseudocolor = d->cm->cd[co].flags & PSEUDO; ispost = 0; noprogress = 1; gotstate = 0; for (i = 0; i < d->nstates; i++) if (ISBSET(css->states, i)) for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) - if (ca->co == co) + if (ca->co == co || + (ca->co == RAINBOW && !ispseudocolor)) { BSET(d->work, ca->to); gotstate = 1; diff --git a/src/backend/regex/regexport.c b/src/backend/regex/regexport.c index d4f940b8c3..a493dbe88c 100644 --- a/src/backend/regex/regexport.c +++ b/src/backend/regex/regexport.c @@ -222,7 +222,8 @@ pg_reg_colorisend(const regex_t *regex, int co) * Get number of member chrs of color number "co". * * Note: we return -1 if the color number is invalid, or if it is a special - * color (WHITE or a pseudocolor), or if the number of members is uncertain. + * color (WHITE, RAINBOW, or a pseudocolor), or if the number of members is + * uncertain. * Callers should not try to extract the members if -1 is returned. */ int @@ -233,7 +234,7 @@ pg_reg_getnumcharacters(const regex_t *regex, int co) assert(regex != NULL && regex->re_magic == REMAGIC); cm = &((struct guts *) regex->re_guts)->cmap; - if (co <= 0 || co > cm->max) /* we reject 0 which is WHITE */ + if (co <= 0 || co > cm->max) /* <= 0 rejects WHITE and RAINBOW */ return -1; if (cm->cd[co].flags & PSEUDO) /* also pseudocolors (BOS etc) */ return -1; @@ -257,7 +258,7 @@ pg_reg_getnumcharacters(const regex_t *regex, int co) * whose length chars_len must be at least as long as indicated by * pg_reg_getnumcharacters(), else not all chars will be returned. * - * Fetching the members of WHITE or a pseudocolor is not supported. + * Fetching the members of WHITE, RAINBOW, or a pseudocolor is not supported. * * Caution: this is a relatively expensive operation. */ diff --git a/src/backend/regex/regprefix.c b/src/backend/regex/regprefix.c index 1d4593ac94..e2fbad7a8a 100644 --- a/src/backend/regex/regprefix.c +++ b/src/backend/regex/regprefix.c @@ -165,9 +165,13 @@ findprefix(struct cnfa *cnfa, /* We can ignore BOS/BOL arcs */ if (ca->co == cnfa->bos[0] || ca->co == cnfa->bos[1]) continue; - /* ... but EOS/EOL arcs terminate the search, as do LACONs */ + + /* + * ... but EOS/EOL arcs terminate the search, as do RAINBOW arcs + * and LACONs + */ if (ca->co == cnfa->eos[0] || ca->co == cnfa->eos[1] || - ca->co >= cnfa->ncolors) + ca->co == RAINBOW || ca->co >= cnfa->ncolors) { thiscolor = COLORLESS; break; diff --git a/src/include/regex/regexport.h b/src/include/regex/regexport.h index e6209463f7..99c4fb854e 100644 --- a/src/include/regex/regexport.h +++ b/src/include/regex/regexport.h @@ -30,6 +30,10 @@ #include "regex/regex.h" +/* These macros must match corresponding ones in regguts.h: */ +#define COLOR_WHITE 0 /* color for chars not appearing in regex */ +#define COLOR_RAINBOW (-2) /* represents all colors except pseudocolors */ + /* information about one arc of a regex's NFA */ typedef struct { diff --git a/src/include/regex/regguts.h b/src/include/regex/regguts.h index 5d0e7a961c..5bcd669d59 100644 --- a/src/include/regex/regguts.h +++ b/src/include/regex/regguts.h @@ -130,11 +130,16 @@ /* * As soon as possible, we map chrs into equivalence classes -- "colors" -- * which are of much more manageable number. + * + * To further reduce the number of arcs in NFAs and DFAs, we also have a + * special RAINBOW "color" that can be assigned to an arc. This is not a + * real color, in that it has no entry in color maps. */ typedef short color; /* colors of characters */ #define MAX_COLOR 32767 /* max color (must fit in 'color' datatype) */ #define COLORLESS (-1) /* impossible color */ +#define RAINBOW (-2) /* represents all colors except pseudocolors */ #define WHITE 0 /* default color, parent of all others */ /* Note: various places in the code know that WHITE is zero */ @@ -276,7 +281,7 @@ struct state; struct arc { int type; /* 0 if free, else an NFA arc type code */ - color co; + color co; /* color the arc matches (possibly RAINBOW) */ struct state *from; /* where it's from (and contained within) */ struct state *to; /* where it's to */ struct arc *outchain; /* link in *from's outs chain or free chain */ @@ -284,6 +289,7 @@ struct arc #define freechain outchain /* we do not maintain "freechainRev" */ struct arc *inchain; /* link in *to's ins chain */ struct arc *inchainRev; /* back-link in *to's ins chain */ + /* these fields are not used when co == RAINBOW: */ struct arc *colorchain; /* link in color's arc chain */ struct arc *colorchainRev; /* back-link in color's arc chain */ }; @@ -344,6 +350,9 @@ struct nfa * Plain arcs just store the transition color number as "co". LACON arcs * store the lookaround constraint number plus cnfa.ncolors as "co". LACON * arcs can be distinguished from plain by testing for co >= cnfa.ncolors. + * + * Note that in a plain arc, "co" can be RAINBOW; since that's negative, + * it doesn't break the rule about how to recognize LACON arcs. */ struct carc {