diff options
Diffstat (limited to '')
| -rw-r--r-- | contrib/pg_trgm/trgm_regexp.c | 2338 |
1 files changed, 2338 insertions, 0 deletions
diff --git a/contrib/pg_trgm/trgm_regexp.c b/contrib/pg_trgm/trgm_regexp.c new file mode 100644 index 0000000..21e8a9f --- /dev/null +++ b/contrib/pg_trgm/trgm_regexp.c @@ -0,0 +1,2338 @@ +/*------------------------------------------------------------------------- + * + * trgm_regexp.c + * Regular expression matching using trigrams. + * + * The general idea of trigram index support for a regular expression (regex) + * search is to transform the regex into a logical expression on trigrams. + * For example: + * + * (ab|cd)efg => ((abe & bef) | (cde & def)) & efg + * + * If a string matches the regex, then it must match the logical expression on + * trigrams. The opposite is not necessarily true, however: a string that + * matches the logical expression might not match the original regex. Such + * false positives are removed via recheck, by running the regular regex match + * operator on the retrieved heap tuple. + * + * Since the trigram expression involves both AND and OR operators, we can't + * expect the core index machinery to evaluate it completely. Instead, the + * result of regex analysis is a list of trigrams to be sought in the index, + * plus a simplified graph that is used by trigramsMatchGraph() to determine + * whether a particular indexed value matches the expression. + * + * Converting a regex to a trigram expression is based on analysis of an + * automaton corresponding to the regex. The algorithm consists of four + * stages: + * + * 1) Compile the regexp to NFA form. This is handled by the PostgreSQL + * regexp library, which provides accessors for its opaque regex_t struct + * to expose the NFA state graph and the "colors" (sets of equivalent + * characters) used as state transition labels. + * + * 2) Transform the original NFA into an expanded graph, where arcs + * are labeled with trigrams that must be present in order to move from + * one state to another via the arcs. The trigrams used in this stage + * consist of colors, not characters, as in the original NFA. + * + * 3) Expand the color trigrams into regular trigrams consisting of + * characters. If too many distinct trigrams are produced, trigrams are + * eliminated and the graph is simplified until it's simple enough. + * + * 4) Finally, the resulting graph is packed into a TrgmPackedGraph struct, + * and returned to the caller. + * + * 1) Compile the regexp to NFA form + * --------------------------------- + * The automaton returned by the regexp compiler is a graph where vertices + * are "states" and arcs are labeled with colors. Each color represents + * a set of characters, so that all characters assigned to the same color + * are interchangeable, so far as matching the regexp is concerned. There + * are two special states: "initial" and "final". A state can have multiple + * outgoing arcs labeled with the same color, which makes the automaton + * non-deterministic, because it can be in many states simultaneously. + * + * Note that this NFA is already lossy compared to the original regexp, + * since it ignores some regex features such as lookahead constraints and + * backref matching. This is OK for our purposes since it's still the case + * that only strings matching the NFA can possibly satisfy the regexp. + * + * 2) Transform the original NFA into an expanded graph + * ---------------------------------------------------- + * In the 2nd stage, the automaton is transformed into a graph based on the + * original NFA. Each state in the expanded graph represents a state from + * the original NFA, plus a prefix identifying the last two characters + * (colors, to be precise) seen before entering the state. There can be + * multiple states in the expanded graph for each state in the original NFA, + * depending on what characters can precede it. A prefix position can be + * "unknown" if it's uncertain what the preceding character was, or "blank" + * if the character was a non-word character (we don't need to distinguish + * which non-word character it was, so just think of all of them as blanks). + * + * For convenience in description, call an expanded-state identifier + * (two prefix colors plus a state number from the original NFA) an + * "enter key". + * + * Each arc of the expanded graph is labeled with a trigram that must be + * present in the string to match. We can construct this from an out-arc of + * the underlying NFA state by combining the expanded state's prefix with the + * color label of the underlying out-arc, if neither prefix position is + * "unknown". But note that some of the colors in the trigram might be + * "blank". This is OK since we want to generate word-boundary trigrams as + * the regular trigram machinery would, if we know that some word characters + * must be adjacent to a word boundary in all strings matching the NFA. + * + * The expanded graph can also have fewer states than the original NFA, + * because we don't bother to make a separate state entry unless the state + * is reachable by a valid arc. When an enter key is reachable from a state + * of the expanded graph, but we do not know a complete trigram associated + * with that transition, we cannot make a valid arc; instead we insert the + * enter key into the enterKeys list of the source state. This effectively + * means that the two expanded states are not reliably distinguishable based + * on examining trigrams. + * + * So the expanded graph resembles the original NFA, but the arcs are + * labeled with trigrams instead of individual characters, and there may be + * more or fewer states. It is a lossy representation of the original NFA: + * any string that matches the original regexp must match the expanded graph, + * but the reverse is not true. + * + * We build the expanded graph through a breadth-first traversal of states + * reachable from the initial state. At each reachable state, we identify the + * states reachable from it without traversing a predictable trigram, and add + * those states' enter keys to the current state. Then we generate all + * out-arcs leading out of this collection of states that have predictable + * trigrams, adding their target states to the queue of states to examine. + * + * When building the graph, if the number of states or arcs exceed pre-defined + * limits, we give up and simply mark any states not yet processed as final + * states. Roughly speaking, that means that we make use of some portion from + * the beginning of the regexp. Also, any colors that have too many member + * characters are treated as "unknown", so that we can't derive trigrams + * from them. + * + * 3) Expand the color trigrams into regular trigrams + * -------------------------------------------------- + * The trigrams in the expanded graph are "color trigrams", consisting + * of three consecutive colors that must be present in the string. But for + * search, we need regular trigrams consisting of characters. In the 3rd + * stage, the color trigrams are expanded into regular trigrams. Since each + * color can represent many characters, the total number of regular trigrams + * after expansion could be very large. Because searching the index for + * thousands of trigrams would be slow, and would likely produce so many + * false positives that we would have to traverse a large fraction of the + * index, the graph is simplified further in a lossy fashion by removing + * color trigrams. When a color trigram is removed, the states connected by + * any arcs labeled with that trigram are merged. + * + * Trigrams do not all have equivalent value for searching: some of them are + * more frequent and some of them are less frequent. Ideally, we would like + * to know the distribution of trigrams, but we don't. But because of padding + * we know for sure that the empty character is more frequent than others, + * so we can penalize trigrams according to presence of whitespace. The + * penalty assigned to each color trigram is the number of simple trigrams + * it would produce, times the penalties[] multiplier associated with its + * whitespace content. (The penalties[] constants were calculated by analysis + * of some real-life text.) We eliminate color trigrams starting with the + * highest-penalty one, until we get to a total penalty of no more than + * WISH_TRGM_PENALTY. However, we cannot remove a color trigram if that would + * lead to merging the initial and final states, so we may not be able to + * reach WISH_TRGM_PENALTY. It's still okay so long as we have no more than + * MAX_TRGM_COUNT simple trigrams in total, otherwise we fail. + * + * 4) Pack the graph into a compact representation + * ----------------------------------------------- + * The 2nd and 3rd stages might have eliminated or merged many of the states + * and trigrams created earlier, so in this final stage, the graph is + * compacted and packed into a simpler struct that contains only the + * information needed to evaluate it. + * + * ALGORITHM EXAMPLE: + * + * Consider the example regex "ab[cd]". This regex is transformed into the + * following NFA (for simplicity we show colors as their single members): + * + * 4# + * c/ + * a b / + * 1* --- 2 ---- 3 + * \ + * d\ + * 5# + * + * We use * to mark initial state and # to mark final state. It's not depicted, + * but states 1, 4, 5 have self-referencing arcs for all possible characters, + * because this pattern can match to any part of a string. + * + * As the result of stage 2 we will have the following graph: + * + * abc abd + * 2# <---- 1* ----> 3# + * + * The process for generating this graph is: + * 1) Create state 1 with enter key (UNKNOWN, UNKNOWN, 1). + * 2) Add key (UNKNOWN, "a", 2) to state 1. + * 3) Add key ("a", "b", 3) to state 1. + * 4) Create new state 2 with enter key ("b", "c", 4). Add an arc + * from state 1 to state 2 with label trigram "abc". + * 5) Mark state 2 final because state 4 of source NFA is marked as final. + * 6) Create new state 3 with enter key ("b", "d", 5). Add an arc + * from state 1 to state 3 with label trigram "abd". + * 7) Mark state 3 final because state 5 of source NFA is marked as final. + * + * + * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * contrib/pg_trgm/trgm_regexp.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "regex/regexport.h" +#include "trgm.h" +#include "tsearch/ts_locale.h" +#include "utils/hsearch.h" +#include "utils/memutils.h" + +/* + * Uncomment (or use -DTRGM_REGEXP_DEBUG) to print debug info, + * for exploring and debugging the algorithm implementation. + * This produces three graph files in /tmp, in Graphviz .gv format. + * Some progress information is also printed to postmaster stderr. + */ +/* #define TRGM_REGEXP_DEBUG */ + +/* + * These parameters are used to limit the amount of work done. + * Otherwise regex processing could be too slow and memory-consuming. + * + * MAX_EXPANDED_STATES - How many states we allow in expanded graph + * MAX_EXPANDED_ARCS - How many arcs we allow in expanded graph + * MAX_TRGM_COUNT - How many simple trigrams we allow to be extracted + * WISH_TRGM_PENALTY - Maximum desired sum of color trigram penalties + * COLOR_COUNT_LIMIT - Maximum number of characters per color + */ +#define MAX_EXPANDED_STATES 128 +#define MAX_EXPANDED_ARCS 1024 +#define MAX_TRGM_COUNT 256 +#define WISH_TRGM_PENALTY 16 +#define COLOR_COUNT_LIMIT 256 + +/* + * Penalty multipliers for trigram counts depending on whitespace contents. + * Numbers based on analysis of real-life texts. + */ +static const float4 penalties[8] = { + 1.0f, /* "aaa" */ + 3.5f, /* "aa " */ + 0.0f, /* "a a" (impossible) */ + 0.0f, /* "a " (impossible) */ + 4.2f, /* " aa" */ + 2.1f, /* " a " */ + 25.0f, /* " a" */ + 0.0f /* " " (impossible) */ +}; + +/* Struct representing a single pg_wchar, converted back to multibyte form */ +typedef struct +{ + char bytes[MAX_MULTIBYTE_CHAR_LEN]; +} trgm_mb_char; + +/* + * Attributes of NFA colors: + * + * expandable - we know the character expansion of this color + * containsNonWord - color contains non-word characters + * (which will not be extracted into trigrams) + * wordCharsCount - count of word characters in color + * wordChars - array of this color's word characters + * (which can be extracted into trigrams) + * + * When expandable is false, the other attributes don't matter; we just + * assume this color represents unknown character(s). + */ +typedef struct +{ + bool expandable; + bool containsNonWord; + int wordCharsCount; + trgm_mb_char *wordChars; +} TrgmColorInfo; + +/* + * A "prefix" is information about the colors of the last two characters read + * before reaching a specific NFA state. These colors can have special values + * COLOR_UNKNOWN and COLOR_BLANK. COLOR_UNKNOWN means that we have no + * information, for example because we read some character of an unexpandable + * color. COLOR_BLANK means that we read a non-word character. + * + * We call a prefix ambiguous if at least one of its colors is unknown. It's + * fully ambiguous if both are unknown, partially ambiguous if only the first + * is unknown. (The case of first color known, second unknown is not valid.) + * + * Wholly- or partly-blank prefixes are mostly handled the same as regular + * color prefixes. This allows us to generate appropriate partly-blank + * trigrams when the NFA requires word character(s) to appear adjacent to + * non-word character(s). + */ +typedef int TrgmColor; + +/* We assume that colors returned by the regexp engine cannot be these: */ +#define COLOR_UNKNOWN (-1) +#define COLOR_BLANK (-2) + +typedef struct +{ + TrgmColor colors[2]; +} TrgmPrefix; + +/* + * Color-trigram data type. Note that some elements of the trigram can be + * COLOR_BLANK, but we don't allow COLOR_UNKNOWN. + */ +typedef struct +{ + TrgmColor colors[3]; +} ColorTrgm; + +/* + * Key identifying a state of our expanded graph: color prefix, and number + * of the corresponding state in the underlying regex NFA. The color prefix + * shows how we reached the regex state (to the extent that we know it). + */ +typedef struct +{ + TrgmPrefix prefix; + int nstate; +} TrgmStateKey; + +/* + * One state of the expanded graph. + * + * stateKey - ID of this state + * arcs - outgoing arcs of this state (List of TrgmArc) + * enterKeys - enter keys reachable from this state without reading any + * predictable trigram (List of TrgmStateKey) + * flags - flag bits + * snumber - number of this state (initially assigned as -1, -2, etc, + * for debugging purposes only; then at the packaging stage, + * surviving states are renumbered with positive numbers) + * parent - parent state, if this state has been merged into another + * tentFlags - flags this state would acquire via planned merges + * tentParent - planned parent state, if considering a merge + */ +#define TSTATE_INIT 0x01 /* flag indicating this state is initial */ +#define TSTATE_FIN 0x02 /* flag indicating this state is final */ + +typedef struct TrgmState +{ + TrgmStateKey stateKey; /* hashtable key: must be first field */ + List *arcs; + List *enterKeys; + int flags; + int snumber; + struct TrgmState *parent; + int tentFlags; + struct TrgmState *tentParent; +} TrgmState; + +/* + * One arc in the expanded graph. + */ +typedef struct +{ + ColorTrgm ctrgm; /* trigram needed to traverse arc */ + TrgmState *target; /* next state */ +} TrgmArc; + +/* + * Information about arc of specific color trigram (used in stage 3) + * + * Contains pointers to the source and target states. + */ +typedef struct +{ + TrgmState *source; + TrgmState *target; +} TrgmArcInfo; + +/* + * Information about color trigram (used in stage 3) + * + * ctrgm - trigram itself + * cnumber - number of this trigram (used in the packaging stage) + * count - number of simple trigrams created from this color trigram + * expanded - indicates this color trigram is expanded into simple trigrams + * arcs - list of all arcs labeled with this color trigram. + */ +typedef struct +{ + ColorTrgm ctrgm; + int cnumber; + int count; + float4 penalty; + bool expanded; + List *arcs; +} ColorTrgmInfo; + +/* + * Data structure representing all the data we need during regex processing. + * + * regex - compiled regex + * colorInfo - extracted information about regex's colors + * ncolors - number of colors in colorInfo[] + * states - hashtable of TrgmStates (states of expanded graph) + * initState - pointer to initial state of expanded graph + * queue - queue of to-be-processed TrgmStates + * keysQueue - queue of to-be-processed TrgmStateKeys + * arcsCount - total number of arcs of expanded graph (for resource + * limiting) + * overflowed - we have exceeded resource limit for transformation + * colorTrgms - array of all color trigrams present in graph + * colorTrgmsCount - count of those color trigrams + * totalTrgmCount - total count of extracted simple trigrams + */ +typedef struct +{ + /* Source regexp, and color information extracted from it (stage 1) */ + regex_t *regex; + TrgmColorInfo *colorInfo; + int ncolors; + + /* Expanded graph (stage 2) */ + HTAB *states; + TrgmState *initState; + int nstates; + + /* Workspace for stage 2 */ + List *queue; + List *keysQueue; + int arcsCount; + bool overflowed; + + /* Information about distinct color trigrams in the graph (stage 3) */ + ColorTrgmInfo *colorTrgms; + int colorTrgmsCount; + int totalTrgmCount; +} TrgmNFA; + +/* + * Final, compact representation of expanded graph. + */ +typedef struct +{ + int targetState; /* index of target state (zero-based) */ + int colorTrgm; /* index of color trigram for transition */ +} TrgmPackedArc; + +typedef struct +{ + int arcsCount; /* number of out-arcs for this state */ + TrgmPackedArc *arcs; /* array of arcsCount packed arcs */ +} TrgmPackedState; + +/* "typedef struct TrgmPackedGraph TrgmPackedGraph" appears in trgm.h */ +struct TrgmPackedGraph +{ + /* + * colorTrigramsCount and colorTrigramGroups contain information about how + * trigrams are grouped into color trigrams. "colorTrigramsCount" is the + * count of color trigrams and "colorTrigramGroups" contains number of + * simple trigrams for each color trigram. The array of simple trigrams + * (stored separately from this struct) is ordered so that the simple + * trigrams for each color trigram are consecutive, and they're in order + * by color trigram number. + */ + int colorTrigramsCount; + int *colorTrigramGroups; /* array of size colorTrigramsCount */ + + /* + * The states of the simplified NFA. State number 0 is always initial + * state and state number 1 is always final state. + */ + int statesCount; + TrgmPackedState *states; /* array of size statesCount */ + + /* Temporary work space for trigramsMatchGraph() */ + bool *colorTrigramsActive; /* array of size colorTrigramsCount */ + bool *statesActive; /* array of size statesCount */ + int *statesQueue; /* array of size statesCount */ +}; + +/* + * Temporary structure for representing an arc during packaging. + */ +typedef struct +{ + int sourceState; + int targetState; + int colorTrgm; +} TrgmPackArcInfo; + + +/* prototypes for private functions */ +static TRGM *createTrgmNFAInternal(regex_t *regex, TrgmPackedGraph **graph, + MemoryContext rcontext); +static void RE_compile(regex_t *regex, text *text_re, + int cflags, Oid collation); +static void getColorInfo(regex_t *regex, TrgmNFA *trgmNFA); +static bool convertPgWchar(pg_wchar c, trgm_mb_char *result); +static void transformGraph(TrgmNFA *trgmNFA); +static void processState(TrgmNFA *trgmNFA, TrgmState *state); +static void addKey(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key); +static void addKeyToQueue(TrgmNFA *trgmNFA, TrgmStateKey *key); +static void addArcs(TrgmNFA *trgmNFA, TrgmState *state); +static void addArc(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key, + TrgmColor co, TrgmStateKey *destKey); +static bool validArcLabel(TrgmStateKey *key, TrgmColor co); +static TrgmState *getState(TrgmNFA *trgmNFA, TrgmStateKey *key); +static bool prefixContains(TrgmPrefix *prefix1, TrgmPrefix *prefix2); +static bool selectColorTrigrams(TrgmNFA *trgmNFA); +static TRGM *expandColorTrigrams(TrgmNFA *trgmNFA, MemoryContext rcontext); +static void fillTrgm(trgm *ptrgm, trgm_mb_char s[3]); +static void mergeStates(TrgmState *state1, TrgmState *state2); +static int colorTrgmInfoCmp(const void *p1, const void *p2); +static int colorTrgmInfoPenaltyCmp(const void *p1, const void *p2); +static TrgmPackedGraph *packGraph(TrgmNFA *trgmNFA, MemoryContext rcontext); +static int packArcInfoCmp(const void *a1, const void *a2); + +#ifdef TRGM_REGEXP_DEBUG +static void printSourceNFA(regex_t *regex, TrgmColorInfo *colors, int ncolors); +static void printTrgmNFA(TrgmNFA *trgmNFA); +static void printTrgmColor(StringInfo buf, TrgmColor co); +static void printTrgmPackedGraph(TrgmPackedGraph *packedGraph, TRGM *trigrams); +#endif + + +/* + * Main entry point to process a regular expression. + * + * Returns an array of trigrams required by the regular expression, or NULL if + * the regular expression was too complex to analyze. In addition, a packed + * graph representation of the regex is returned into *graph. The results + * must be allocated in rcontext (which might or might not be the current + * context). + */ +TRGM * +createTrgmNFA(text *text_re, Oid collation, + TrgmPackedGraph **graph, MemoryContext rcontext) +{ + TRGM *trg; + regex_t regex; + MemoryContext tmpcontext; + MemoryContext oldcontext; + + /* + * This processing generates a great deal of cruft, which we'd like to + * clean up before returning (since this function may be called in a + * query-lifespan memory context). Make a temp context we can work in so + * that cleanup is easy. + */ + tmpcontext = AllocSetContextCreate(CurrentMemoryContext, + "createTrgmNFA temporary context", + ALLOCSET_DEFAULT_SIZES); + oldcontext = MemoryContextSwitchTo(tmpcontext); + + /* + * Stage 1: Compile the regexp into a NFA, using the regexp library. + */ +#ifdef IGNORECASE + RE_compile(®ex, text_re, REG_ADVANCED | REG_ICASE, collation); +#else + RE_compile(®ex, text_re, REG_ADVANCED, collation); +#endif + + /* + * Since the regexp library allocates its internal data structures with + * malloc, we need to use a PG_TRY block to ensure that pg_regfree() gets + * done even if there's an error. + */ + PG_TRY(); + { + trg = createTrgmNFAInternal(®ex, graph, rcontext); + } + PG_FINALLY(); + { + pg_regfree(®ex); + } + PG_END_TRY(); + + /* Clean up all the cruft we created */ + MemoryContextSwitchTo(oldcontext); + MemoryContextDelete(tmpcontext); + + return trg; +} + +/* + * Body of createTrgmNFA, exclusive of regex compilation/freeing. + */ +static TRGM * +createTrgmNFAInternal(regex_t *regex, TrgmPackedGraph **graph, + MemoryContext rcontext) +{ + TRGM *trg; + TrgmNFA trgmNFA; + + trgmNFA.regex = regex; + + /* Collect color information from the regex */ + getColorInfo(regex, &trgmNFA); + +#ifdef TRGM_REGEXP_DEBUG + printSourceNFA(regex, trgmNFA.colorInfo, trgmNFA.ncolors); +#endif + + /* + * Stage 2: Create an expanded graph from the source NFA. + */ + transformGraph(&trgmNFA); + +#ifdef TRGM_REGEXP_DEBUG + printTrgmNFA(&trgmNFA); +#endif + + /* + * Fail if we were unable to make a nontrivial graph, ie it is possible to + * get from the initial state to the final state without reading any + * predictable trigram. + */ + if (trgmNFA.initState->flags & TSTATE_FIN) + return NULL; + + /* + * Stage 3: Select color trigrams to expand. Fail if too many trigrams. + */ + if (!selectColorTrigrams(&trgmNFA)) + return NULL; + + /* + * Stage 4: Expand color trigrams and pack graph into final + * representation. + */ + trg = expandColorTrigrams(&trgmNFA, rcontext); + + *graph = packGraph(&trgmNFA, rcontext); + +#ifdef TRGM_REGEXP_DEBUG + printTrgmPackedGraph(*graph, trg); +#endif + + return trg; +} + +/* + * Main entry point for evaluating a graph during index scanning. + * + * The check[] array is indexed by trigram number (in the array of simple + * trigrams returned by createTrgmNFA), and holds true for those trigrams + * that are present in the index entry being checked. + */ +bool +trigramsMatchGraph(TrgmPackedGraph *graph, bool *check) +{ + int i, + j, + k, + queueIn, + queueOut; + + /* + * Reset temporary working areas. + */ + memset(graph->colorTrigramsActive, 0, + sizeof(bool) * graph->colorTrigramsCount); + memset(graph->statesActive, 0, sizeof(bool) * graph->statesCount); + + /* + * Check which color trigrams were matched. A match for any simple + * trigram associated with a color trigram counts as a match of the color + * trigram. + */ + j = 0; + for (i = 0; i < graph->colorTrigramsCount; i++) + { + int cnt = graph->colorTrigramGroups[i]; + + for (k = j; k < j + cnt; k++) + { + if (check[k]) + { + /* + * Found one matched trigram in the group. Can skip the rest + * of them and go to the next group. + */ + graph->colorTrigramsActive[i] = true; + break; + } + } + j = j + cnt; + } + + /* + * Initialize the statesQueue to hold just the initial state. Note: + * statesQueue has room for statesCount entries, which is certainly enough + * since no state will be put in the queue more than once. The + * statesActive array marks which states have been queued. + */ + graph->statesActive[0] = true; + graph->statesQueue[0] = 0; + queueIn = 0; + queueOut = 1; + + /* Process queued states as long as there are any. */ + while (queueIn < queueOut) + { + int stateno = graph->statesQueue[queueIn++]; + TrgmPackedState *state = &graph->states[stateno]; + int cnt = state->arcsCount; + + /* Loop over state's out-arcs */ + for (i = 0; i < cnt; i++) + { + TrgmPackedArc *arc = &state->arcs[i]; + + /* + * If corresponding color trigram is present then activate the + * corresponding state. We're done if that's the final state, + * otherwise queue the state if it's not been queued already. + */ + if (graph->colorTrigramsActive[arc->colorTrgm]) + { + int nextstate = arc->targetState; + + if (nextstate == 1) + return true; /* success: final state is reachable */ + + if (!graph->statesActive[nextstate]) + { + graph->statesActive[nextstate] = true; + graph->statesQueue[queueOut++] = nextstate; + } + } + } + } + + /* Queue is empty, so match fails. */ + return false; +} + +/* + * Compile regex string into struct at *regex. + * NB: pg_regfree must be applied to regex if this completes successfully. + */ +static void +RE_compile(regex_t *regex, text *text_re, int cflags, Oid collation) +{ + int text_re_len = VARSIZE_ANY_EXHDR(text_re); + char *text_re_val = VARDATA_ANY(text_re); + pg_wchar *pattern; + int pattern_len; + int regcomp_result; + char errMsg[100]; + + /* Convert pattern string to wide characters */ + pattern = (pg_wchar *) palloc((text_re_len + 1) * sizeof(pg_wchar)); + pattern_len = pg_mb2wchar_with_len(text_re_val, + pattern, + text_re_len); + + /* Compile regex */ + regcomp_result = pg_regcomp(regex, + pattern, + pattern_len, + cflags, + collation); + + pfree(pattern); + + if (regcomp_result != REG_OKAY) + { + /* re didn't compile (no need for pg_regfree, if so) */ + pg_regerror(regcomp_result, regex, errMsg, sizeof(errMsg)); + ereport(ERROR, + (errcode(ERRCODE_INVALID_REGULAR_EXPRESSION), + errmsg("invalid regular expression: %s", errMsg))); + } +} + + +/*--------------------- + * Subroutines for pre-processing the color map (stage 1). + *--------------------- + */ + +/* + * Fill TrgmColorInfo structure for each color using regex export functions. + */ +static void +getColorInfo(regex_t *regex, TrgmNFA *trgmNFA) +{ + int colorsCount = pg_reg_getnumcolors(regex); + int i; + + trgmNFA->ncolors = colorsCount; + trgmNFA->colorInfo = (TrgmColorInfo *) + palloc0(colorsCount * sizeof(TrgmColorInfo)); + + /* + * Loop over colors, filling TrgmColorInfo about each. + */ + for (i = 0; i < colorsCount; i++) + { + TrgmColorInfo *colorInfo = &trgmNFA->colorInfo[i]; + int charsCount = pg_reg_getnumcharacters(regex, i); + pg_wchar *chars; + int j; + + if (charsCount < 0 || charsCount > COLOR_COUNT_LIMIT) + { + /* Non expandable, or too large to work with */ + colorInfo->expandable = false; + continue; + } + + colorInfo->expandable = true; + colorInfo->containsNonWord = false; + colorInfo->wordChars = (trgm_mb_char *) + palloc(sizeof(trgm_mb_char) * charsCount); + colorInfo->wordCharsCount = 0; + + /* Extract all the chars in this color */ + chars = (pg_wchar *) palloc(sizeof(pg_wchar) * charsCount); + pg_reg_getcharacters(regex, i, chars, charsCount); + + /* + * Convert characters back to multibyte form, and save only those that + * are word characters. Set "containsNonWord" if any non-word + * character. (Note: it'd probably be nicer to keep the chars in + * pg_wchar format for now, but ISWORDCHR wants to see multibyte.) + */ + for (j = 0; j < charsCount; j++) + { + trgm_mb_char c; + + if (!convertPgWchar(chars[j], &c)) + continue; /* ok to ignore it altogether */ + if (ISWORDCHR(c.bytes)) + colorInfo->wordChars[colorInfo->wordCharsCount++] = c; + else + colorInfo->containsNonWord = true; + } + + pfree(chars); + } +} + +/* + * Convert pg_wchar to multibyte format. + * Returns false if the character should be ignored completely. + */ +static bool +convertPgWchar(pg_wchar c, trgm_mb_char *result) +{ + /* "s" has enough space for a multibyte character and a trailing NUL */ + char s[MAX_MULTIBYTE_CHAR_LEN + 1]; + + /* + * We can ignore the NUL character, since it can never appear in a PG text + * string. This avoids the need for various special cases when + * reconstructing trigrams. + */ + if (c == 0) + return false; + + /* Do the conversion, making sure the result is NUL-terminated */ + memset(s, 0, sizeof(s)); + pg_wchar2mb_with_len(&c, s, 1); + + /* + * In IGNORECASE mode, we can ignore uppercase characters. We assume that + * the regex engine generated both uppercase and lowercase equivalents + * within each color, since we used the REG_ICASE option; so there's no + * need to process the uppercase version. + * + * XXX this code is dependent on the assumption that lowerstr() works the + * same as the regex engine's internal case folding machinery. Might be + * wiser to expose pg_wc_tolower and test whether c == pg_wc_tolower(c). + * On the other hand, the trigrams in the index were created using + * lowerstr(), so we're probably screwed if there's any incompatibility + * anyway. + */ +#ifdef IGNORECASE + { + char *lowerCased = lowerstr(s); + + if (strcmp(lowerCased, s) != 0) + { + pfree(lowerCased); + return false; + } + pfree(lowerCased); + } +#endif + + /* Fill result with exactly MAX_MULTIBYTE_CHAR_LEN bytes */ + memcpy(result->bytes, s, MAX_MULTIBYTE_CHAR_LEN); + return true; +} + + +/*--------------------- + * Subroutines for expanding original NFA graph into a trigram graph (stage 2). + *--------------------- + */ + +/* + * Transform the graph, given a regex and extracted color information. + * + * We create and process a queue of expanded-graph states until all the states + * are processed. + * + * This algorithm may be stopped due to resource limitation. In this case we + * force every unprocessed branch to immediately finish with matching (this + * can give us false positives but no false negatives) by marking all + * unprocessed states as final. + */ +static void +transformGraph(TrgmNFA *trgmNFA) +{ + HASHCTL hashCtl; + TrgmStateKey initkey; + TrgmState *initstate; + + /* Initialize this stage's workspace in trgmNFA struct */ + trgmNFA->queue = NIL; + trgmNFA->keysQueue = NIL; + trgmNFA->arcsCount = 0; + trgmNFA->overflowed = false; + + /* Create hashtable for states */ + hashCtl.keysize = sizeof(TrgmStateKey); + hashCtl.entrysize = sizeof(TrgmState); + hashCtl.hcxt = CurrentMemoryContext; + trgmNFA->states = hash_create("Trigram NFA", + 1024, + &hashCtl, + HASH_ELEM | HASH_BLOBS | HASH_CONTEXT); + trgmNFA->nstates = 0; + + /* Create initial state: ambiguous prefix, NFA's initial state */ + MemSet(&initkey, 0, sizeof(initkey)); + initkey.prefix.colors[0] = COLOR_UNKNOWN; + initkey.prefix.colors[1] = COLOR_UNKNOWN; + initkey.nstate = pg_reg_getinitialstate(trgmNFA->regex); + + initstate = getState(trgmNFA, &initkey); + initstate->flags |= TSTATE_INIT; + trgmNFA->initState = initstate; + + /* + * Recursively build the expanded graph by processing queue of states + * (breadth-first search). getState already put initstate in the queue. + */ + while (trgmNFA->queue != NIL) + { + TrgmState *state = (TrgmState *) linitial(trgmNFA->queue); + + trgmNFA->queue = list_delete_first(trgmNFA->queue); + + /* + * If we overflowed then just mark state as final. Otherwise do + * actual processing. + */ + if (trgmNFA->overflowed) + state->flags |= TSTATE_FIN; + else + processState(trgmNFA, state); + + /* Did we overflow? */ + if (trgmNFA->arcsCount > MAX_EXPANDED_ARCS || + hash_get_num_entries(trgmNFA->states) > MAX_EXPANDED_STATES) + trgmNFA->overflowed = true; + } +} + +/* + * Process one state: add enter keys and then add outgoing arcs. + */ +static void +processState(TrgmNFA *trgmNFA, TrgmState *state) +{ + /* keysQueue should be NIL already, but make sure */ + trgmNFA->keysQueue = NIL; + + /* + * Add state's own key, and then process all keys added to keysQueue until + * queue is empty. But we can quit if the state gets marked final. + */ + addKey(trgmNFA, state, &state->stateKey); + while (trgmNFA->keysQueue != NIL && !(state->flags & TSTATE_FIN)) + { + TrgmStateKey *key = (TrgmStateKey *) linitial(trgmNFA->keysQueue); + + trgmNFA->keysQueue = list_delete_first(trgmNFA->keysQueue); + addKey(trgmNFA, state, key); + } + + /* + * Add outgoing arcs only if state isn't final (we have no interest in + * outgoing arcs if we already match) + */ + if (!(state->flags & TSTATE_FIN)) + addArcs(trgmNFA, state); +} + +/* + * Add the given enter key into the state's enterKeys list, and determine + * whether this should result in any further enter keys being added. + * If so, add those keys to keysQueue so that processState will handle them. + * + * If the enter key is for the NFA's final state, mark state as TSTATE_FIN. + * This situation means that we can reach the final state from this expanded + * state without reading any predictable trigram, so we must consider this + * state as an accepting one. + * + * The given key could be a duplicate of one already in enterKeys, or be + * redundant with some enterKeys. So we check that before doing anything. + * + * Note that we don't generate any actual arcs here. addArcs will do that + * later, after we have identified all the enter keys for this state. + */ +static void +addKey(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key) +{ + regex_arc_t *arcs; + TrgmStateKey destKey; + ListCell *cell; + int i, + arcsCount; + + /* + * Ensure any pad bytes in destKey are zero, since it may get used as a + * hashtable key by getState. + */ + MemSet(&destKey, 0, sizeof(destKey)); + + /* + * Compare key to each existing enter key of the state to check for + * redundancy. We can drop either old key(s) or the new key if we find + * redundancy. + */ + foreach(cell, state->enterKeys) + { + TrgmStateKey *existingKey = (TrgmStateKey *) lfirst(cell); + + if (existingKey->nstate == key->nstate) + { + if (prefixContains(&existingKey->prefix, &key->prefix)) + { + /* This old key already covers the new key. Nothing to do */ + return; + } + if (prefixContains(&key->prefix, &existingKey->prefix)) + { + /* + * The new key covers this old key. Remove the old key, it's + * no longer needed once we add this key to the list. + */ + state->enterKeys = foreach_delete_current(state->enterKeys, + cell); + } + } + } + + /* No redundancy, so add this key to the state's list */ + state->enterKeys = lappend(state->enterKeys, key); + + /* If state is now known final, mark it and we're done */ + if (key->nstate == pg_reg_getfinalstate(trgmNFA->regex)) + { + state->flags |= TSTATE_FIN; + return; + } + + /* + * Loop through all outgoing arcs of the corresponding state in the + * original NFA. + */ + arcsCount = pg_reg_getnumoutarcs(trgmNFA->regex, key->nstate); + arcs = (regex_arc_t *) palloc(sizeof(regex_arc_t) * arcsCount); + pg_reg_getoutarcs(trgmNFA->regex, key->nstate, arcs, arcsCount); + + for (i = 0; i < arcsCount; i++) + { + regex_arc_t *arc = &arcs[i]; + + if (pg_reg_colorisbegin(trgmNFA->regex, arc->co)) + { + /* + * Start of line/string (^). Trigram extraction treats start of + * line same as start of word: double space prefix is added. + * Hence, make an enter key showing we can reach the arc + * destination with all-blank prefix. + */ + destKey.prefix.colors[0] = COLOR_BLANK; + destKey.prefix.colors[1] = COLOR_BLANK; + destKey.nstate = arc->to; + + /* Add enter key to this state */ + addKeyToQueue(trgmNFA, &destKey); + } + else if (pg_reg_colorisend(trgmNFA->regex, arc->co)) + { + /* + * End of line/string ($). We must consider this arc as a + * transition that doesn't read anything. The reason for adding + * this enter key to the state is that if the arc leads to the + * NFA's final state, we must mark this expanded state as final. + */ + destKey.prefix.colors[0] = COLOR_UNKNOWN; + destKey.prefix.colors[1] = COLOR_UNKNOWN; + destKey.nstate = arc->to; + + /* Add enter key to this state */ + addKeyToQueue(trgmNFA, &destKey); + } + else + { + /* Regular color */ + TrgmColorInfo *colorInfo = &trgmNFA->colorInfo[arc->co]; + + if (colorInfo->expandable) + { + if (colorInfo->containsNonWord && + !validArcLabel(key, COLOR_BLANK)) + { + /* + * We can reach the arc destination after reading a + * non-word character, but the prefix is not something + * that addArc will accept with COLOR_BLANK, so no trigram + * arc can get made for this transition. We must make an + * enter key to show that the arc destination is + * reachable. Set it up with an all-blank prefix, since + * that corresponds to what the trigram extraction code + * will do at a word starting boundary. + */ + destKey.prefix.colors[0] = COLOR_BLANK; + destKey.prefix.colors[1] = COLOR_BLANK; + destKey.nstate = arc->to; + addKeyToQueue(trgmNFA, &destKey); + } + + if (colorInfo->wordCharsCount > 0 && + !validArcLabel(key, arc->co)) + { + /* + * We can reach the arc destination after reading a word + * character, but the prefix is not something that addArc + * will accept, so no trigram arc can get made for this + * transition. We must make an enter key to show that the + * arc destination is reachable. The prefix for the enter + * key should reflect the info we have for this arc. + */ + destKey.prefix.colors[0] = key->prefix.colors[1]; + destKey.prefix.colors[1] = arc->co; + destKey.nstate = arc->to; + addKeyToQueue(trgmNFA, &destKey); + } + } + else + { + /* + * Unexpandable color. Add enter key with ambiguous prefix, + * showing we can reach the destination from this state, but + * the preceding colors will be uncertain. (We do not set the + * first prefix color to key->prefix.colors[1], because a + * prefix of known followed by unknown is invalid.) + */ + destKey.prefix.colors[0] = COLOR_UNKNOWN; + destKey.prefix.colors[1] = COLOR_UNKNOWN; + destKey.nstate = arc->to; + addKeyToQueue(trgmNFA, &destKey); + } + } + } + + pfree(arcs); +} + +/* + * Add copy of given key to keysQueue for later processing. + */ +static void +addKeyToQueue(TrgmNFA *trgmNFA, TrgmStateKey *key) +{ + TrgmStateKey *keyCopy = (TrgmStateKey *) palloc(sizeof(TrgmStateKey)); + + memcpy(keyCopy, key, sizeof(TrgmStateKey)); + trgmNFA->keysQueue = lappend(trgmNFA->keysQueue, keyCopy); +} + +/* + * Add outgoing arcs from given state, whose enter keys are all now known. + */ +static void +addArcs(TrgmNFA *trgmNFA, TrgmState *state) +{ + TrgmStateKey destKey; + ListCell *cell; + regex_arc_t *arcs; + int arcsCount, + i; + + /* + * Ensure any pad bytes in destKey are zero, since it may get used as a + * hashtable key by getState. + */ + MemSet(&destKey, 0, sizeof(destKey)); + + /* + * Iterate over enter keys associated with this expanded-graph state. This + * includes both the state's own stateKey, and any enter keys we added to + * it during addKey (which represent expanded-graph states that are not + * distinguishable from this one by means of trigrams). For each such + * enter key, examine all the out-arcs of the key's underlying NFA state, + * and try to make a trigram arc leading to where the out-arc leads. + * (addArc will deal with whether the arc is valid or not.) + */ + foreach(cell, state->enterKeys) + { + TrgmStateKey *key = (TrgmStateKey *) lfirst(cell); + + arcsCount = pg_reg_getnumoutarcs(trgmNFA->regex, key->nstate); + arcs = (regex_arc_t *) palloc(sizeof(regex_arc_t) * arcsCount); + pg_reg_getoutarcs(trgmNFA->regex, key->nstate, arcs, arcsCount); + + for (i = 0; i < arcsCount; i++) + { + regex_arc_t *arc = &arcs[i]; + TrgmColorInfo *colorInfo = &trgmNFA->colorInfo[arc->co]; + + /* + * 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. + */ + if (!colorInfo->expandable) + continue; + + if (colorInfo->containsNonWord) + { + /* + * Color includes non-word character(s). + * + * Generate an arc, treating this transition as occurring on + * BLANK. This allows word-ending trigrams to be manufactured + * if possible. + */ + destKey.prefix.colors[0] = key->prefix.colors[1]; + destKey.prefix.colors[1] = COLOR_BLANK; + destKey.nstate = arc->to; + + addArc(trgmNFA, state, key, COLOR_BLANK, &destKey); + } + + if (colorInfo->wordCharsCount > 0) + { + /* + * Color includes word character(s). + * + * Generate an arc. Color is pushed into prefix of target + * state. + */ + destKey.prefix.colors[0] = key->prefix.colors[1]; + destKey.prefix.colors[1] = arc->co; + destKey.nstate = arc->to; + + addArc(trgmNFA, state, key, arc->co, &destKey); + } + } + + pfree(arcs); + } +} + +/* + * Generate an out-arc of the expanded graph, if it's valid and not redundant. + * + * state: expanded-graph state we want to add an out-arc to + * key: provides prefix colors (key->nstate is not used) + * co: transition color + * destKey: identifier for destination state of expanded graph + */ +static void +addArc(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key, + TrgmColor co, TrgmStateKey *destKey) +{ + TrgmArc *arc; + ListCell *cell; + + /* Do nothing if this wouldn't be a valid arc label trigram */ + if (!validArcLabel(key, co)) + return; + + /* + * Check if we are going to reach key which is covered by a key which is + * already listed in this state. If so arc is useless: the NFA can bypass + * it through a path that doesn't require any predictable trigram, so + * whether the arc's trigram is present or not doesn't really matter. + */ + foreach(cell, state->enterKeys) + { + TrgmStateKey *existingKey = (TrgmStateKey *) lfirst(cell); + + if (existingKey->nstate == destKey->nstate && + prefixContains(&existingKey->prefix, &destKey->prefix)) + return; + } + + /* Checks were successful, add new arc */ + arc = (TrgmArc *) palloc(sizeof(TrgmArc)); + arc->target = getState(trgmNFA, destKey); + arc->ctrgm.colors[0] = key->prefix.colors[0]; + arc->ctrgm.colors[1] = key->prefix.colors[1]; + arc->ctrgm.colors[2] = co; + + state->arcs = lappend(state->arcs, arc); + trgmNFA->arcsCount++; +} + +/* + * Can we make a valid trigram arc label from the given prefix and arc color? + * + * This is split out so that tests in addKey and addArc will stay in sync. + */ +static bool +validArcLabel(TrgmStateKey *key, TrgmColor co) +{ + /* + * We have to know full trigram in order to add outgoing arc. So we can't + * do it if prefix is ambiguous. + */ + if (key->prefix.colors[0] == COLOR_UNKNOWN) + return false; + + /* If key->prefix.colors[0] isn't unknown, its second color isn't either */ + Assert(key->prefix.colors[1] != COLOR_UNKNOWN); + /* And we should not be called with an unknown arc color anytime */ + Assert(co != COLOR_UNKNOWN); + + /* + * We don't bother with making arcs representing three non-word + * characters, since that's useless for trigram extraction. + */ + if (key->prefix.colors[0] == COLOR_BLANK && + key->prefix.colors[1] == COLOR_BLANK && + co == COLOR_BLANK) + return false; + + /* + * We also reject nonblank-blank-anything. The nonblank-blank-nonblank + * case doesn't correspond to any trigram the trigram extraction code + * would make. The nonblank-blank-blank case is also not possible with + * RPADDING = 1. (Note that in many cases we'd fail to generate such a + * trigram even if it were valid, for example processing "foo bar" will + * not result in considering the trigram "o ". So if you want to support + * RPADDING = 2, there's more to do than just twiddle this test.) + */ + if (key->prefix.colors[0] != COLOR_BLANK && + key->prefix.colors[1] == COLOR_BLANK) + return false; + + /* + * Other combinations involving blank are valid, in particular we assume + * blank-blank-nonblank is valid, which presumes that LPADDING is 2. + * + * Note: Using again the example "foo bar", we will not consider the + * trigram " b", though this trigram would be found by the trigram + * extraction code. Since we will find " ba", it doesn't seem worth + * trying to hack the algorithm to generate the additional trigram. + */ + + /* arc label is valid */ + return true; +} + +/* + * Get state of expanded graph for given state key, + * and queue the state for processing if it didn't already exist. + */ +static TrgmState * +getState(TrgmNFA *trgmNFA, TrgmStateKey *key) +{ + TrgmState *state; + bool found; + + state = (TrgmState *) hash_search(trgmNFA->states, key, HASH_ENTER, + &found); + if (!found) + { + /* New state: initialize and queue it */ + state->arcs = NIL; + state->enterKeys = NIL; + state->flags = 0; + /* states are initially given negative numbers */ + state->snumber = -(++trgmNFA->nstates); + state->parent = NULL; + state->tentFlags = 0; + state->tentParent = NULL; + + trgmNFA->queue = lappend(trgmNFA->queue, state); + } + return state; +} + +/* + * Check if prefix1 "contains" prefix2. + * + * "contains" means that any exact prefix (with no ambiguity) that satisfies + * prefix2 also satisfies prefix1. + */ +static bool +prefixContains(TrgmPrefix *prefix1, TrgmPrefix *prefix2) +{ + if (prefix1->colors[1] == COLOR_UNKNOWN) + { + /* Fully ambiguous prefix contains everything */ + return true; + } + else if (prefix1->colors[0] == COLOR_UNKNOWN) + { + /* + * Prefix with only first unknown color contains every prefix with + * same second color. + */ + if (prefix1->colors[1] == prefix2->colors[1]) + return true; + else + return false; + } + else + { + /* Exact prefix contains only the exact same prefix */ + if (prefix1->colors[0] == prefix2->colors[0] && + prefix1->colors[1] == prefix2->colors[1]) + return true; + else + return false; + } +} + + +/*--------------------- + * Subroutines for expanding color trigrams into regular trigrams (stage 3). + *--------------------- + */ + +/* + * Get vector of all color trigrams in graph and select which of them + * to expand into simple trigrams. + * + * Returns true if OK, false if exhausted resource limits. + */ +static bool +selectColorTrigrams(TrgmNFA *trgmNFA) +{ + HASH_SEQ_STATUS scan_status; + int arcsCount = trgmNFA->arcsCount, + i; + TrgmState *state; + ColorTrgmInfo *colorTrgms; + int64 totalTrgmCount; + float4 totalTrgmPenalty; + int cnumber; + + /* Collect color trigrams from all arcs */ + colorTrgms = (ColorTrgmInfo *) palloc0(sizeof(ColorTrgmInfo) * arcsCount); + trgmNFA->colorTrgms = colorTrgms; + + i = 0; + hash_seq_init(&scan_status, trgmNFA->states); + while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL) + { + ListCell *cell; + + foreach(cell, state->arcs) + { + TrgmArc *arc = (TrgmArc *) lfirst(cell); + TrgmArcInfo *arcInfo = (TrgmArcInfo *) palloc(sizeof(TrgmArcInfo)); + ColorTrgmInfo *trgmInfo = &colorTrgms[i]; + + arcInfo->source = state; + arcInfo->target = arc->target; + trgmInfo->ctrgm = arc->ctrgm; + trgmInfo->cnumber = -1; + /* count and penalty will be set below */ + trgmInfo->expanded = true; + trgmInfo->arcs = list_make1(arcInfo); + i++; + } + } + Assert(i == arcsCount); + + /* Remove duplicates, merging their arcs lists */ + if (arcsCount >= 2) + { + ColorTrgmInfo *p1, + *p2; + + /* Sort trigrams to ease duplicate detection */ + qsort(colorTrgms, arcsCount, sizeof(ColorTrgmInfo), colorTrgmInfoCmp); + + /* p1 is probe point, p2 is last known non-duplicate. */ + p2 = colorTrgms; + for (p1 = colorTrgms + 1; p1 < colorTrgms + arcsCount; p1++) + { + if (colorTrgmInfoCmp(p1, p2) > 0) + { + p2++; + *p2 = *p1; + } + else + { + p2->arcs = list_concat(p2->arcs, p1->arcs); + } + } + trgmNFA->colorTrgmsCount = (p2 - colorTrgms) + 1; + } + else + { + trgmNFA->colorTrgmsCount = arcsCount; + } + + /* + * Count number of simple trigrams generated by each color trigram, and + * also compute a penalty value, which is the number of simple trigrams + * times a multiplier that depends on its whitespace content. + * + * Note: per-color-trigram counts cannot overflow an int so long as + * COLOR_COUNT_LIMIT is not more than the cube root of INT_MAX, ie about + * 1290. However, the grand total totalTrgmCount might conceivably + * overflow an int, so we use int64 for that within this routine. Also, + * penalties are calculated in float4 arithmetic to avoid any overflow + * worries. + */ + totalTrgmCount = 0; + totalTrgmPenalty = 0.0f; + for (i = 0; i < trgmNFA->colorTrgmsCount; i++) + { + ColorTrgmInfo *trgmInfo = &colorTrgms[i]; + int j, + count = 1, + typeIndex = 0; + + for (j = 0; j < 3; j++) + { + TrgmColor c = trgmInfo->ctrgm.colors[j]; + + typeIndex *= 2; + if (c == COLOR_BLANK) + typeIndex++; + else + count *= trgmNFA->colorInfo[c].wordCharsCount; + } + trgmInfo->count = count; + totalTrgmCount += count; + trgmInfo->penalty = penalties[typeIndex] * (float4) count; + totalTrgmPenalty += trgmInfo->penalty; + } + + /* Sort color trigrams in descending order of their penalties */ + qsort(colorTrgms, trgmNFA->colorTrgmsCount, sizeof(ColorTrgmInfo), + colorTrgmInfoPenaltyCmp); + + /* + * Remove color trigrams from the graph so long as total penalty of color + * trigrams exceeds WISH_TRGM_PENALTY. (If we fail to get down to + * WISH_TRGM_PENALTY, it's OK so long as total count is no more than + * MAX_TRGM_COUNT.) We prefer to remove color trigrams with higher + * penalty, since those are the most promising for reducing the total + * penalty. When removing a color trigram we have to merge states + * connected by arcs labeled with that trigram. It's necessary to not + * merge initial and final states, because our graph becomes useless if + * that happens; so we cannot always remove the trigram we'd prefer to. + */ + for (i = 0; i < trgmNFA->colorTrgmsCount; i++) + { + ColorTrgmInfo *trgmInfo = &colorTrgms[i]; + bool canRemove = true; + ListCell *cell; + + /* Done if we've reached the target */ + if (totalTrgmPenalty <= WISH_TRGM_PENALTY) + break; + +#ifdef TRGM_REGEXP_DEBUG + fprintf(stderr, "considering ctrgm %d %d %d, penalty %f, %d arcs\n", + trgmInfo->ctrgm.colors[0], + trgmInfo->ctrgm.colors[1], + trgmInfo->ctrgm.colors[2], + trgmInfo->penalty, + list_length(trgmInfo->arcs)); +#endif + + /* + * Does any arc of this color trigram connect initial and final + * states? If so we can't remove it. + */ + foreach(cell, trgmInfo->arcs) + { + TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell); + TrgmState *source = arcInfo->source, + *target = arcInfo->target; + int source_flags, + target_flags; + +#ifdef TRGM_REGEXP_DEBUG + fprintf(stderr, "examining arc to s%d (%x) from s%d (%x)\n", + -target->snumber, target->flags, + -source->snumber, source->flags); +#endif + + /* examine parent states, if any merging has already happened */ + while (source->parent) + source = source->parent; + while (target->parent) + target = target->parent; + +#ifdef TRGM_REGEXP_DEBUG + fprintf(stderr, " ... after completed merges: to s%d (%x) from s%d (%x)\n", + -target->snumber, target->flags, + -source->snumber, source->flags); +#endif + + /* we must also consider merges we are planning right now */ + source_flags = source->flags | source->tentFlags; + while (source->tentParent) + { + source = source->tentParent; + source_flags |= source->flags | source->tentFlags; + } + target_flags = target->flags | target->tentFlags; + while (target->tentParent) + { + target = target->tentParent; + target_flags |= target->flags | target->tentFlags; + } + +#ifdef TRGM_REGEXP_DEBUG + fprintf(stderr, " ... after tentative merges: to s%d (%x) from s%d (%x)\n", + -target->snumber, target_flags, + -source->snumber, source_flags); +#endif + + /* would fully-merged state have both INIT and FIN set? */ + if (((source_flags | target_flags) & (TSTATE_INIT | TSTATE_FIN)) == + (TSTATE_INIT | TSTATE_FIN)) + { + canRemove = false; + break; + } + + /* ok so far, so remember planned merge */ + if (source != target) + { +#ifdef TRGM_REGEXP_DEBUG + fprintf(stderr, " ... tentatively merging s%d into s%d\n", + -target->snumber, -source->snumber); +#endif + target->tentParent = source; + source->tentFlags |= target_flags; + } + } + + /* + * We must reset all the tentFlags/tentParent fields before + * continuing. tentFlags could only have become set in states that + * are the source or parent or tentative parent of one of the current + * arcs; likewise tentParent could only have become set in states that + * are the target or parent or tentative parent of one of the current + * arcs. There might be some overlap between those sets, but if we + * clear tentFlags in target states as well as source states, we + * should be okay even if we visit a state as target before visiting + * it as a source. + */ + foreach(cell, trgmInfo->arcs) + { + TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell); + TrgmState *source = arcInfo->source, + *target = arcInfo->target; + TrgmState *ttarget; + + /* no need to touch previously-merged states */ + while (source->parent) + source = source->parent; + while (target->parent) + target = target->parent; + + while (source) + { + source->tentFlags = 0; + source = source->tentParent; + } + + while ((ttarget = target->tentParent) != NULL) + { + target->tentParent = NULL; + target->tentFlags = 0; /* in case it was also a source */ + target = ttarget; + } + } + + /* Now, move on if we can't drop this trigram */ + if (!canRemove) + { +#ifdef TRGM_REGEXP_DEBUG + fprintf(stderr, " ... not ok to merge\n"); +#endif + continue; + } + + /* OK, merge states linked by each arc labeled by the trigram */ + foreach(cell, trgmInfo->arcs) + { + TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell); + TrgmState *source = arcInfo->source, + *target = arcInfo->target; + + while (source->parent) + source = source->parent; + while (target->parent) + target = target->parent; + if (source != target) + { +#ifdef TRGM_REGEXP_DEBUG + fprintf(stderr, "merging s%d into s%d\n", + -target->snumber, -source->snumber); +#endif + mergeStates(source, target); + /* Assert we didn't merge initial and final states */ + Assert((source->flags & (TSTATE_INIT | TSTATE_FIN)) != + (TSTATE_INIT | TSTATE_FIN)); + } + } + + /* Mark trigram unexpanded, and update totals */ + trgmInfo->expanded = false; + totalTrgmCount -= trgmInfo->count; + totalTrgmPenalty -= trgmInfo->penalty; + } + + /* Did we succeed in fitting into MAX_TRGM_COUNT? */ + if (totalTrgmCount > MAX_TRGM_COUNT) + return false; + + trgmNFA->totalTrgmCount = (int) totalTrgmCount; + + /* + * Sort color trigrams by colors (will be useful for bsearch in packGraph) + * and enumerate the color trigrams that are expanded. + */ + cnumber = 0; + qsort(colorTrgms, trgmNFA->colorTrgmsCount, sizeof(ColorTrgmInfo), + colorTrgmInfoCmp); + for (i = 0; i < trgmNFA->colorTrgmsCount; i++) + { + if (colorTrgms[i].expanded) + { + colorTrgms[i].cnumber = cnumber; + cnumber++; + } + } + + return true; +} + +/* + * Expand selected color trigrams into regular trigrams. + * + * Returns the TRGM array to be passed to the index machinery. + * The array must be allocated in rcontext. + */ +static TRGM * +expandColorTrigrams(TrgmNFA *trgmNFA, MemoryContext rcontext) +{ + TRGM *trg; + trgm *p; + int i; + TrgmColorInfo blankColor; + trgm_mb_char blankChar; + + /* Set up "blank" color structure containing a single zero character */ + memset(blankChar.bytes, 0, sizeof(blankChar.bytes)); + blankColor.wordCharsCount = 1; + blankColor.wordChars = &blankChar; + + /* Construct the trgm array */ + trg = (TRGM *) + MemoryContextAllocZero(rcontext, + TRGMHDRSIZE + + trgmNFA->totalTrgmCount * sizeof(trgm)); + trg->flag = ARRKEY; + SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, trgmNFA->totalTrgmCount)); + p = GETARR(trg); + for (i = 0; i < trgmNFA->colorTrgmsCount; i++) + { + ColorTrgmInfo *colorTrgm = &trgmNFA->colorTrgms[i]; + TrgmColorInfo *c[3]; + trgm_mb_char s[3]; + int j, + i1, + i2, + i3; + + /* Ignore any unexpanded trigrams ... */ + if (!colorTrgm->expanded) + continue; + + /* Get colors, substituting the dummy struct for COLOR_BLANK */ + for (j = 0; j < 3; j++) + { + if (colorTrgm->ctrgm.colors[j] != COLOR_BLANK) + c[j] = &trgmNFA->colorInfo[colorTrgm->ctrgm.colors[j]]; + else + c[j] = &blankColor; + } + + /* Iterate over all possible combinations of colors' characters */ + for (i1 = 0; i1 < c[0]->wordCharsCount; i1++) + { + s[0] = c[0]->wordChars[i1]; + for (i2 = 0; i2 < c[1]->wordCharsCount; i2++) + { + s[1] = c[1]->wordChars[i2]; + for (i3 = 0; i3 < c[2]->wordCharsCount; i3++) + { + s[2] = c[2]->wordChars[i3]; + fillTrgm(p, s); + p++; + } + } + } + } + + return trg; +} + +/* + * Convert trigram into trgm datatype. + */ +static void +fillTrgm(trgm *ptrgm, trgm_mb_char s[3]) +{ + char str[3 * MAX_MULTIBYTE_CHAR_LEN], + *p; + int i, + j; + + /* Write multibyte string into "str" (we don't need null termination) */ + p = str; + + for (i = 0; i < 3; i++) + { + if (s[i].bytes[0] != 0) + { + for (j = 0; j < MAX_MULTIBYTE_CHAR_LEN && s[i].bytes[j]; j++) + *p++ = s[i].bytes[j]; + } + else + { + /* Emit a space in place of COLOR_BLANK */ + *p++ = ' '; + } + } + + /* Convert "str" to a standard trigram (possibly hashing it) */ + compact_trigram(ptrgm, str, p - str); +} + +/* + * Merge two states of graph. + */ +static void +mergeStates(TrgmState *state1, TrgmState *state2) +{ + Assert(state1 != state2); + Assert(!state1->parent); + Assert(!state2->parent); + + /* state1 absorbs state2's flags */ + state1->flags |= state2->flags; + + /* state2, and indirectly all its children, become children of state1 */ + state2->parent = state1; +} + +/* + * Compare function for sorting of color trigrams by their colors. + */ +static int +colorTrgmInfoCmp(const void *p1, const void *p2) +{ + const ColorTrgmInfo *c1 = (const ColorTrgmInfo *) p1; + const ColorTrgmInfo *c2 = (const ColorTrgmInfo *) p2; + + return memcmp(&c1->ctrgm, &c2->ctrgm, sizeof(ColorTrgm)); +} + +/* + * Compare function for sorting color trigrams in descending order of + * their penalty fields. + */ +static int +colorTrgmInfoPenaltyCmp(const void *p1, const void *p2) +{ + float4 penalty1 = ((const ColorTrgmInfo *) p1)->penalty; + float4 penalty2 = ((const ColorTrgmInfo *) p2)->penalty; + + if (penalty1 < penalty2) + return 1; + else if (penalty1 == penalty2) + return 0; + else + return -1; +} + + +/*--------------------- + * Subroutines for packing the graph into final representation (stage 4). + *--------------------- + */ + +/* + * Pack expanded graph into final representation. + * + * The result data must be allocated in rcontext. + */ +static TrgmPackedGraph * +packGraph(TrgmNFA *trgmNFA, MemoryContext rcontext) +{ + int snumber = 2, + arcIndex, + arcsCount; + HASH_SEQ_STATUS scan_status; + TrgmState *state; + TrgmPackArcInfo *arcs, + *p1, + *p2; + TrgmPackedArc *packedArcs; + TrgmPackedGraph *result; + int i, + j; + + /* Enumerate surviving states, giving init and fin reserved numbers */ + hash_seq_init(&scan_status, trgmNFA->states); + while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL) + { + while (state->parent) + state = state->parent; + + if (state->snumber < 0) + { + if (state->flags & TSTATE_INIT) + state->snumber = 0; + else if (state->flags & TSTATE_FIN) + state->snumber = 1; + else + { + state->snumber = snumber; + snumber++; + } + } + } + + /* Collect array of all arcs */ + arcs = (TrgmPackArcInfo *) + palloc(sizeof(TrgmPackArcInfo) * trgmNFA->arcsCount); + arcIndex = 0; + hash_seq_init(&scan_status, trgmNFA->states); + while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL) + { + TrgmState *source = state; + ListCell *cell; + + while (source->parent) + source = source->parent; + + foreach(cell, state->arcs) + { + TrgmArc *arc = (TrgmArc *) lfirst(cell); + TrgmState *target = arc->target; + + while (target->parent) + target = target->parent; + + if (source->snumber != target->snumber) + { + ColorTrgmInfo *ctrgm; + + ctrgm = (ColorTrgmInfo *) bsearch(&arc->ctrgm, + trgmNFA->colorTrgms, + trgmNFA->colorTrgmsCount, + sizeof(ColorTrgmInfo), + colorTrgmInfoCmp); + Assert(ctrgm != NULL); + Assert(ctrgm->expanded); + + arcs[arcIndex].sourceState = source->snumber; + arcs[arcIndex].targetState = target->snumber; + arcs[arcIndex].colorTrgm = ctrgm->cnumber; + arcIndex++; + } + } + } + + /* Sort arcs to ease duplicate detection */ + qsort(arcs, arcIndex, sizeof(TrgmPackArcInfo), packArcInfoCmp); + + /* We could have duplicates because states were merged. Remove them. */ + /* p1 is probe point, p2 is last known non-duplicate. */ + p2 = arcs; + for (p1 = arcs + 1; p1 < arcs + arcIndex; p1++) + { + if (packArcInfoCmp(p1, p2) > 0) + { + p2++; + *p2 = *p1; + } + } + arcsCount = (p2 - arcs) + 1; + + /* Create packed representation */ + result = (TrgmPackedGraph *) + MemoryContextAlloc(rcontext, sizeof(TrgmPackedGraph)); + + /* Pack color trigrams information */ + result->colorTrigramsCount = 0; + for (i = 0; i < trgmNFA->colorTrgmsCount; i++) + { + if (trgmNFA->colorTrgms[i].expanded) + result->colorTrigramsCount++; + } + result->colorTrigramGroups = (int *) + MemoryContextAlloc(rcontext, sizeof(int) * result->colorTrigramsCount); + j = 0; + for (i = 0; i < trgmNFA->colorTrgmsCount; i++) + { + if (trgmNFA->colorTrgms[i].expanded) + { + result->colorTrigramGroups[j] = trgmNFA->colorTrgms[i].count; + j++; + } + } + + /* Pack states and arcs information */ + result->statesCount = snumber; + result->states = (TrgmPackedState *) + MemoryContextAlloc(rcontext, snumber * sizeof(TrgmPackedState)); + packedArcs = (TrgmPackedArc *) + MemoryContextAlloc(rcontext, arcsCount * sizeof(TrgmPackedArc)); + j = 0; + for (i = 0; i < snumber; i++) + { + int cnt = 0; + + result->states[i].arcs = &packedArcs[j]; + while (j < arcsCount && arcs[j].sourceState == i) + { + packedArcs[j].targetState = arcs[j].targetState; + packedArcs[j].colorTrgm = arcs[j].colorTrgm; + cnt++; + j++; + } + result->states[i].arcsCount = cnt; + } + + /* Allocate working memory for trigramsMatchGraph() */ + result->colorTrigramsActive = (bool *) + MemoryContextAlloc(rcontext, sizeof(bool) * result->colorTrigramsCount); + result->statesActive = (bool *) + MemoryContextAlloc(rcontext, sizeof(bool) * result->statesCount); + result->statesQueue = (int *) + MemoryContextAlloc(rcontext, sizeof(int) * result->statesCount); + + return result; +} + +/* + * Comparison function for sorting TrgmPackArcInfos. + * + * Compares arcs in following order: sourceState, colorTrgm, targetState. + */ +static int +packArcInfoCmp(const void *a1, const void *a2) +{ + const TrgmPackArcInfo *p1 = (const TrgmPackArcInfo *) a1; + const TrgmPackArcInfo *p2 = (const TrgmPackArcInfo *) a2; + + if (p1->sourceState < p2->sourceState) + return -1; + if (p1->sourceState > p2->sourceState) + return 1; + if (p1->colorTrgm < p2->colorTrgm) + return -1; + if (p1->colorTrgm > p2->colorTrgm) + return 1; + if (p1->targetState < p2->targetState) + return -1; + if (p1->targetState > p2->targetState) + return 1; + return 0; +} + + +/*--------------------- + * Debugging functions + * + * These are designed to emit GraphViz files. + *--------------------- + */ + +#ifdef TRGM_REGEXP_DEBUG + +/* + * Print initial NFA, in regexp library's representation + */ +static void +printSourceNFA(regex_t *regex, TrgmColorInfo *colors, int ncolors) +{ + StringInfoData buf; + int nstates = pg_reg_getnumstates(regex); + int state; + int i; + + initStringInfo(&buf); + + appendStringInfoString(&buf, "\ndigraph sourceNFA {\n"); + + for (state = 0; state < nstates; state++) + { + regex_arc_t *arcs; + int i, + arcsCount; + + appendStringInfo(&buf, "s%d", state); + if (pg_reg_getfinalstate(regex) == state) + appendStringInfoString(&buf, " [shape = doublecircle]"); + appendStringInfoString(&buf, ";\n"); + + arcsCount = pg_reg_getnumoutarcs(regex, state); + arcs = (regex_arc_t *) palloc(sizeof(regex_arc_t) * arcsCount); + pg_reg_getoutarcs(regex, state, arcs, arcsCount); + + for (i = 0; i < arcsCount; i++) + { + appendStringInfo(&buf, " s%d -> s%d [label = \"%d\"];\n", + state, arcs[i].to, arcs[i].co); + } + + pfree(arcs); + } + + appendStringInfoString(&buf, " node [shape = point ]; initial;\n"); + appendStringInfo(&buf, " initial -> s%d;\n", + pg_reg_getinitialstate(regex)); + + /* Print colors */ + appendStringInfoString(&buf, " { rank = sink;\n"); + appendStringInfoString(&buf, " Colors [shape = none, margin=0, label=<\n"); + + for (i = 0; i < ncolors; i++) + { + TrgmColorInfo *color = &colors[i]; + int j; + + appendStringInfo(&buf, "<br/>Color %d: ", i); + if (color->expandable) + { + for (j = 0; j < color->wordCharsCount; j++) + { + char s[MAX_MULTIBYTE_CHAR_LEN + 1]; + + memcpy(s, color->wordChars[j].bytes, MAX_MULTIBYTE_CHAR_LEN); + s[MAX_MULTIBYTE_CHAR_LEN] = '\0'; + appendStringInfoString(&buf, s); + } + } + else + appendStringInfoString(&buf, "not expandable"); + appendStringInfoChar(&buf, '\n'); + } + + appendStringInfoString(&buf, " >];\n"); + appendStringInfoString(&buf, " }\n"); + appendStringInfoString(&buf, "}\n"); + + { + /* dot -Tpng -o /tmp/source.png < /tmp/source.gv */ + FILE *fp = fopen("/tmp/source.gv", "w"); + + fprintf(fp, "%s", buf.data); + fclose(fp); + } + + pfree(buf.data); +} + +/* + * Print expanded graph. + */ +static void +printTrgmNFA(TrgmNFA *trgmNFA) +{ + StringInfoData buf; + HASH_SEQ_STATUS scan_status; + TrgmState *state; + TrgmState *initstate = NULL; + + initStringInfo(&buf); + + appendStringInfoString(&buf, "\ndigraph transformedNFA {\n"); + + hash_seq_init(&scan_status, trgmNFA->states); + while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL) + { + ListCell *cell; + + appendStringInfo(&buf, "s%d", -state->snumber); + if (state->flags & TSTATE_FIN) + appendStringInfoString(&buf, " [shape = doublecircle]"); + if (state->flags & TSTATE_INIT) + initstate = state; + appendStringInfo(&buf, " [label = \"%d\"]", state->stateKey.nstate); + appendStringInfoString(&buf, ";\n"); + + foreach(cell, state->arcs) + { + TrgmArc *arc = (TrgmArc *) lfirst(cell); + + appendStringInfo(&buf, " s%d -> s%d [label = \"", + -state->snumber, -arc->target->snumber); + printTrgmColor(&buf, arc->ctrgm.colors[0]); + appendStringInfoChar(&buf, ' '); + printTrgmColor(&buf, arc->ctrgm.colors[1]); + appendStringInfoChar(&buf, ' '); + printTrgmColor(&buf, arc->ctrgm.colors[2]); + appendStringInfoString(&buf, "\"];\n"); + } + } + + if (initstate) + { + appendStringInfoString(&buf, " node [shape = point ]; initial;\n"); + appendStringInfo(&buf, " initial -> s%d;\n", -initstate->snumber); + } + + appendStringInfoString(&buf, "}\n"); + + { + /* dot -Tpng -o /tmp/transformed.png < /tmp/transformed.gv */ + FILE *fp = fopen("/tmp/transformed.gv", "w"); + + fprintf(fp, "%s", buf.data); + fclose(fp); + } + + pfree(buf.data); +} + +/* + * Print a TrgmColor readably. + */ +static void +printTrgmColor(StringInfo buf, TrgmColor co) +{ + if (co == COLOR_UNKNOWN) + appendStringInfoChar(buf, 'u'); + else if (co == COLOR_BLANK) + appendStringInfoChar(buf, 'b'); + else + appendStringInfo(buf, "%d", (int) co); +} + +/* + * Print final packed representation of trigram-based expanded graph. + */ +static void +printTrgmPackedGraph(TrgmPackedGraph *packedGraph, TRGM *trigrams) +{ + StringInfoData buf; + trgm *p; + int i; + + initStringInfo(&buf); + + appendStringInfoString(&buf, "\ndigraph packedGraph {\n"); + + for (i = 0; i < packedGraph->statesCount; i++) + { + TrgmPackedState *state = &packedGraph->states[i]; + int j; + + appendStringInfo(&buf, " s%d", i); + if (i == 1) + appendStringInfoString(&buf, " [shape = doublecircle]"); + + appendStringInfo(&buf, " [label = <s%d>];\n", i); + + for (j = 0; j < state->arcsCount; j++) + { + TrgmPackedArc *arc = &state->arcs[j]; + + appendStringInfo(&buf, " s%d -> s%d [label = \"trigram %d\"];\n", + i, arc->targetState, arc->colorTrgm); + } + } + + appendStringInfoString(&buf, " node [shape = point ]; initial;\n"); + appendStringInfo(&buf, " initial -> s%d;\n", 0); + + /* Print trigrams */ + appendStringInfoString(&buf, " { rank = sink;\n"); + appendStringInfoString(&buf, " Trigrams [shape = none, margin=0, label=<\n"); + + p = GETARR(trigrams); + for (i = 0; i < packedGraph->colorTrigramsCount; i++) + { + int count = packedGraph->colorTrigramGroups[i]; + int j; + + appendStringInfo(&buf, "<br/>Trigram %d: ", i); + + for (j = 0; j < count; j++) + { + if (j > 0) + appendStringInfoString(&buf, ", "); + + /* + * XXX This representation is nice only for all-ASCII trigrams. + */ + appendStringInfo(&buf, "\"%c%c%c\"", (*p)[0], (*p)[1], (*p)[2]); + p++; + } + } + + appendStringInfoString(&buf, " >];\n"); + appendStringInfoString(&buf, " }\n"); + appendStringInfoString(&buf, "}\n"); + + { + /* dot -Tpng -o /tmp/packed.png < /tmp/packed.gv */ + FILE *fp = fopen("/tmp/packed.gv", "w"); + + fprintf(fp, "%s", buf.data); + fclose(fp); + } + + pfree(buf.data); +} + +#endif /* TRGM_REGEXP_DEBUG */ |