PostgreSQL Source Code  git master
trgm_regexp.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * trgm_regexp.c
4  * Regular expression matching using trigrams.
5  *
6  * The general idea of trigram index support for a regular expression (regex)
7  * search is to transform the regex into a logical expression on trigrams.
8  * For example:
9  *
10  * (ab|cd)efg => ((abe & bef) | (cde & def)) & efg
11  *
12  * If a string matches the regex, then it must match the logical expression on
13  * trigrams. The opposite is not necessarily true, however: a string that
14  * matches the logical expression might not match the original regex. Such
15  * false positives are removed via recheck, by running the regular regex match
16  * operator on the retrieved heap tuple.
17  *
18  * Since the trigram expression involves both AND and OR operators, we can't
19  * expect the core index machinery to evaluate it completely. Instead, the
20  * result of regex analysis is a list of trigrams to be sought in the index,
21  * plus a simplified graph that is used by trigramsMatchGraph() to determine
22  * whether a particular indexed value matches the expression.
23  *
24  * Converting a regex to a trigram expression is based on analysis of an
25  * automaton corresponding to the regex. The algorithm consists of four
26  * stages:
27  *
28  * 1) Compile the regexp to NFA form. This is handled by the PostgreSQL
29  * regexp library, which provides accessors for its opaque regex_t struct
30  * to expose the NFA state graph and the "colors" (sets of equivalent
31  * characters) used as state transition labels.
32  *
33  * 2) Transform the original NFA into an expanded graph, where arcs
34  * are labeled with trigrams that must be present in order to move from
35  * one state to another via the arcs. The trigrams used in this stage
36  * consist of colors, not characters, as in the original NFA.
37  *
38  * 3) Expand the color trigrams into regular trigrams consisting of
39  * characters. If too many distinct trigrams are produced, trigrams are
40  * eliminated and the graph is simplified until it's simple enough.
41  *
42  * 4) Finally, the resulting graph is packed into a TrgmPackedGraph struct,
43  * and returned to the caller.
44  *
45  * 1) Compile the regexp to NFA form
46  * ---------------------------------
47  * The automaton returned by the regexp compiler is a graph where vertices
48  * are "states" and arcs are labeled with colors. Each color represents
49  * a set of characters, so that all characters assigned to the same color
50  * are interchangeable, so far as matching the regexp is concerned. There
51  * are two special states: "initial" and "final". A state can have multiple
52  * outgoing arcs labeled with the same color, which makes the automaton
53  * non-deterministic, because it can be in many states simultaneously.
54  *
55  * Note that this NFA is already lossy compared to the original regexp,
56  * since it ignores some regex features such as lookahead constraints and
57  * backref matching. This is OK for our purposes since it's still the case
58  * that only strings matching the NFA can possibly satisfy the regexp.
59  *
60  * 2) Transform the original NFA into an expanded graph
61  * ----------------------------------------------------
62  * In the 2nd stage, the automaton is transformed into a graph based on the
63  * original NFA. Each state in the expanded graph represents a state from
64  * the original NFA, plus a prefix identifying the last two characters
65  * (colors, to be precise) seen before entering the state. There can be
66  * multiple states in the expanded graph for each state in the original NFA,
67  * depending on what characters can precede it. A prefix position can be
68  * "unknown" if it's uncertain what the preceding character was, or "blank"
69  * if the character was a non-word character (we don't need to distinguish
70  * which non-word character it was, so just think of all of them as blanks).
71  *
72  * For convenience in description, call an expanded-state identifier
73  * (two prefix colors plus a state number from the original NFA) an
74  * "enter key".
75  *
76  * Each arc of the expanded graph is labeled with a trigram that must be
77  * present in the string to match. We can construct this from an out-arc of
78  * the underlying NFA state by combining the expanded state's prefix with the
79  * color label of the underlying out-arc, if neither prefix position is
80  * "unknown". But note that some of the colors in the trigram might be
81  * "blank". This is OK since we want to generate word-boundary trigrams as
82  * the regular trigram machinery would, if we know that some word characters
83  * must be adjacent to a word boundary in all strings matching the NFA.
84  *
85  * The expanded graph can also have fewer states than the original NFA,
86  * because we don't bother to make a separate state entry unless the state
87  * is reachable by a valid arc. When an enter key is reachable from a state
88  * of the expanded graph, but we do not know a complete trigram associated
89  * with that transition, we cannot make a valid arc; instead we insert the
90  * enter key into the enterKeys list of the source state. This effectively
91  * means that the two expanded states are not reliably distinguishable based
92  * on examining trigrams.
93  *
94  * So the expanded graph resembles the original NFA, but the arcs are
95  * labeled with trigrams instead of individual characters, and there may be
96  * more or fewer states. It is a lossy representation of the original NFA:
97  * any string that matches the original regexp must match the expanded graph,
98  * but the reverse is not true.
99  *
100  * We build the expanded graph through a breadth-first traversal of states
101  * reachable from the initial state. At each reachable state, we identify the
102  * states reachable from it without traversing a predictable trigram, and add
103  * those states' enter keys to the current state. Then we generate all
104  * out-arcs leading out of this collection of states that have predictable
105  * trigrams, adding their target states to the queue of states to examine.
106  *
107  * When building the graph, if the number of states or arcs exceed pre-defined
108  * limits, we give up and simply mark any states not yet processed as final
109  * states. Roughly speaking, that means that we make use of some portion from
110  * the beginning of the regexp. Also, any colors that have too many member
111  * characters are treated as "unknown", so that we can't derive trigrams
112  * from them.
113  *
114  * 3) Expand the color trigrams into regular trigrams
115  * --------------------------------------------------
116  * The trigrams in the expanded graph are "color trigrams", consisting
117  * of three consecutive colors that must be present in the string. But for
118  * search, we need regular trigrams consisting of characters. In the 3rd
119  * stage, the color trigrams are expanded into regular trigrams. Since each
120  * color can represent many characters, the total number of regular trigrams
121  * after expansion could be very large. Because searching the index for
122  * thousands of trigrams would be slow, and would likely produce so many
123  * false positives that we would have to traverse a large fraction of the
124  * index, the graph is simplified further in a lossy fashion by removing
125  * color trigrams. When a color trigram is removed, the states connected by
126  * any arcs labeled with that trigram are merged.
127  *
128  * Trigrams do not all have equivalent value for searching: some of them are
129  * more frequent and some of them are less frequent. Ideally, we would like
130  * to know the distribution of trigrams, but we don't. But because of padding
131  * we know for sure that the empty character is more frequent than others,
132  * so we can penalize trigrams according to presence of whitespace. The
133  * penalty assigned to each color trigram is the number of simple trigrams
134  * it would produce, times the penalties[] multiplier associated with its
135  * whitespace content. (The penalties[] constants were calculated by analysis
136  * of some real-life text.) We eliminate color trigrams starting with the
137  * highest-penalty one, until we get to a total penalty of no more than
138  * WISH_TRGM_PENALTY. However, we cannot remove a color trigram if that would
139  * lead to merging the initial and final states, so we may not be able to
140  * reach WISH_TRGM_PENALTY. It's still okay so long as we have no more than
141  * MAX_TRGM_COUNT simple trigrams in total, otherwise we fail.
142  *
143  * 4) Pack the graph into a compact representation
144  * -----------------------------------------------
145  * The 2nd and 3rd stages might have eliminated or merged many of the states
146  * and trigrams created earlier, so in this final stage, the graph is
147  * compacted and packed into a simpler struct that contains only the
148  * information needed to evaluate it.
149  *
150  * ALGORITHM EXAMPLE:
151  *
152  * Consider the example regex "ab[cd]". This regex is transformed into the
153  * following NFA (for simplicity we show colors as their single members):
154  *
155  * 4#
156  * c/
157  * a b /
158  * 1* --- 2 ---- 3
159  * \
160  * d\
161  * 5#
162  *
163  * We use * to mark initial state and # to mark final state. It's not depicted,
164  * but states 1, 4, 5 have self-referencing arcs for all possible characters,
165  * because this pattern can match to any part of a string.
166  *
167  * As the result of stage 2 we will have the following graph:
168  *
169  * abc abd
170  * 2# <---- 1* ----> 3#
171  *
172  * The process for generating this graph is:
173  * 1) Create state 1 with enter key (UNKNOWN, UNKNOWN, 1).
174  * 2) Add key (UNKNOWN, "a", 2) to state 1.
175  * 3) Add key ("a", "b", 3) to state 1.
176  * 4) Create new state 2 with enter key ("b", "c", 4). Add an arc
177  * from state 1 to state 2 with label trigram "abc".
178  * 5) Mark state 2 final because state 4 of source NFA is marked as final.
179  * 6) Create new state 3 with enter key ("b", "d", 5). Add an arc
180  * from state 1 to state 3 with label trigram "abd".
181  * 7) Mark state 3 final because state 5 of source NFA is marked as final.
182  *
183  *
184  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
185  * Portions Copyright (c) 1994, Regents of the University of California
186  *
187  * IDENTIFICATION
188  * contrib/pg_trgm/trgm_regexp.c
189  *
190  *-------------------------------------------------------------------------
191  */
192 #include "postgres.h"
193 
194 #include "regex/regexport.h"
195 #include "trgm.h"
196 #include "tsearch/ts_locale.h"
197 #include "utils/hsearch.h"
198 #include "utils/memutils.h"
199 #include "varatt.h"
200 
201 /*
202  * Uncomment (or use -DTRGM_REGEXP_DEBUG) to print debug info,
203  * for exploring and debugging the algorithm implementation.
204  * This produces three graph files in /tmp, in Graphviz .gv format.
205  * Some progress information is also printed to postmaster stderr.
206  */
207 /* #define TRGM_REGEXP_DEBUG */
208 
209 /*
210  * These parameters are used to limit the amount of work done.
211  * Otherwise regex processing could be too slow and memory-consuming.
212  *
213  * MAX_EXPANDED_STATES - How many states we allow in expanded graph
214  * MAX_EXPANDED_ARCS - How many arcs we allow in expanded graph
215  * MAX_TRGM_COUNT - How many simple trigrams we allow to be extracted
216  * WISH_TRGM_PENALTY - Maximum desired sum of color trigram penalties
217  * COLOR_COUNT_LIMIT - Maximum number of characters per color
218  */
219 #define MAX_EXPANDED_STATES 128
220 #define MAX_EXPANDED_ARCS 1024
221 #define MAX_TRGM_COUNT 256
222 #define WISH_TRGM_PENALTY 16
223 #define COLOR_COUNT_LIMIT 256
224 
225 /*
226  * Penalty multipliers for trigram counts depending on whitespace contents.
227  * Numbers based on analysis of real-life texts.
228  */
229 static const float4 penalties[8] = {
230  1.0f, /* "aaa" */
231  3.5f, /* "aa " */
232  0.0f, /* "a a" (impossible) */
233  0.0f, /* "a " (impossible) */
234  4.2f, /* " aa" */
235  2.1f, /* " a " */
236  25.0f, /* " a" */
237  0.0f /* " " (impossible) */
238 };
239 
240 /* Struct representing a single pg_wchar, converted back to multibyte form */
241 typedef struct
242 {
244 } trgm_mb_char;
245 
246 /*
247  * Attributes of NFA colors:
248  *
249  * expandable - we know the character expansion of this color
250  * containsNonWord - color contains non-word characters
251  * (which will not be extracted into trigrams)
252  * wordCharsCount - count of word characters in color
253  * wordChars - array of this color's word characters
254  * (which can be extracted into trigrams)
255  *
256  * When expandable is false, the other attributes don't matter; we just
257  * assume this color represents unknown character(s).
258  */
259 typedef struct
260 {
265 } TrgmColorInfo;
266 
267 /*
268  * A "prefix" is information about the colors of the last two characters read
269  * before reaching a specific NFA state. These colors can have special values
270  * COLOR_UNKNOWN and COLOR_BLANK. COLOR_UNKNOWN means that we have no
271  * information, for example because we read some character of an unexpandable
272  * color. COLOR_BLANK means that we read a non-word character.
273  *
274  * We call a prefix ambiguous if at least one of its colors is unknown. It's
275  * fully ambiguous if both are unknown, partially ambiguous if only the first
276  * is unknown. (The case of first color known, second unknown is not valid.)
277  *
278  * Wholly- or partly-blank prefixes are mostly handled the same as regular
279  * color prefixes. This allows us to generate appropriate partly-blank
280  * trigrams when the NFA requires word character(s) to appear adjacent to
281  * non-word character(s).
282  */
283 typedef int TrgmColor;
284 
285 /* We assume that colors returned by the regexp engine cannot be these: */
286 #define COLOR_UNKNOWN (-3)
287 #define COLOR_BLANK (-4)
288 
289 typedef struct
290 {
291  TrgmColor colors[2];
292 } TrgmPrefix;
293 
294 /*
295  * Color-trigram data type. Note that some elements of the trigram can be
296  * COLOR_BLANK, but we don't allow COLOR_UNKNOWN.
297  */
298 typedef struct
299 {
300  TrgmColor colors[3];
301 } ColorTrgm;
302 
303 /*
304  * Key identifying a state of our expanded graph: color prefix, and number
305  * of the corresponding state in the underlying regex NFA. The color prefix
306  * shows how we reached the regex state (to the extent that we know it).
307  */
308 typedef struct
309 {
311  int nstate;
312 } TrgmStateKey;
313 
314 /*
315  * One state of the expanded graph.
316  *
317  * stateKey - ID of this state
318  * arcs - outgoing arcs of this state (List of TrgmArc)
319  * enterKeys - enter keys reachable from this state without reading any
320  * predictable trigram (List of TrgmStateKey)
321  * flags - flag bits
322  * snumber - number of this state (initially assigned as -1, -2, etc,
323  * for debugging purposes only; then at the packaging stage,
324  * surviving states are renumbered with positive numbers)
325  * parent - parent state, if this state has been merged into another
326  * tentFlags - flags this state would acquire via planned merges
327  * tentParent - planned parent state, if considering a merge
328  */
329 #define TSTATE_INIT 0x01 /* flag indicating this state is initial */
330 #define TSTATE_FIN 0x02 /* flag indicating this state is final */
331 
332 typedef struct TrgmState
333 {
334  TrgmStateKey stateKey; /* hashtable key: must be first field */
337  int flags;
338  int snumber;
339  struct TrgmState *parent;
343 
344 /*
345  * One arc in the expanded graph.
346  */
347 typedef struct
348 {
349  ColorTrgm ctrgm; /* trigram needed to traverse arc */
350  TrgmState *target; /* next state */
351 } TrgmArc;
352 
353 /*
354  * Information about arc of specific color trigram (used in stage 3)
355  *
356  * Contains pointers to the source and target states.
357  */
358 typedef struct
359 {
362 } TrgmArcInfo;
363 
364 /*
365  * Information about color trigram (used in stage 3)
366  *
367  * ctrgm - trigram itself
368  * cnumber - number of this trigram (used in the packaging stage)
369  * count - number of simple trigrams created from this color trigram
370  * expanded - indicates this color trigram is expanded into simple trigrams
371  * arcs - list of all arcs labeled with this color trigram.
372  */
373 typedef struct
374 {
376  int cnumber;
377  int count;
379  bool expanded;
381 } ColorTrgmInfo;
382 
383 /*
384  * Data structure representing all the data we need during regex processing.
385  *
386  * regex - compiled regex
387  * colorInfo - extracted information about regex's colors
388  * ncolors - number of colors in colorInfo[]
389  * states - hashtable of TrgmStates (states of expanded graph)
390  * initState - pointer to initial state of expanded graph
391  * queue - queue of to-be-processed TrgmStates
392  * keysQueue - queue of to-be-processed TrgmStateKeys
393  * arcsCount - total number of arcs of expanded graph (for resource
394  * limiting)
395  * overflowed - we have exceeded resource limit for transformation
396  * colorTrgms - array of all color trigrams present in graph
397  * colorTrgmsCount - count of those color trigrams
398  * totalTrgmCount - total count of extracted simple trigrams
399  */
400 typedef struct
401 {
402  /* Source regexp, and color information extracted from it (stage 1) */
405  int ncolors;
406 
407  /* Expanded graph (stage 2) */
410  int nstates;
411 
412  /* Workspace for stage 2 */
417 
418  /* Information about distinct color trigrams in the graph (stage 3) */
422 } TrgmNFA;
423 
424 /*
425  * Final, compact representation of expanded graph.
426  */
427 typedef struct
428 {
429  int targetState; /* index of target state (zero-based) */
430  int colorTrgm; /* index of color trigram for transition */
431 } TrgmPackedArc;
432 
433 typedef struct
434 {
435  int arcsCount; /* number of out-arcs for this state */
436  TrgmPackedArc *arcs; /* array of arcsCount packed arcs */
438 
439 /* "typedef struct TrgmPackedGraph TrgmPackedGraph" appears in trgm.h */
441 {
442  /*
443  * colorTrigramsCount and colorTrigramGroups contain information about how
444  * trigrams are grouped into color trigrams. "colorTrigramsCount" is the
445  * count of color trigrams and "colorTrigramGroups" contains number of
446  * simple trigrams for each color trigram. The array of simple trigrams
447  * (stored separately from this struct) is ordered so that the simple
448  * trigrams for each color trigram are consecutive, and they're in order
449  * by color trigram number.
450  */
452  int *colorTrigramGroups; /* array of size colorTrigramsCount */
453 
454  /*
455  * The states of the simplified NFA. State number 0 is always initial
456  * state and state number 1 is always final state.
457  */
459  TrgmPackedState *states; /* array of size statesCount */
460 
461  /* Temporary work space for trigramsMatchGraph() */
462  bool *colorTrigramsActive; /* array of size colorTrigramsCount */
463  bool *statesActive; /* array of size statesCount */
464  int *statesQueue; /* array of size statesCount */
465 };
466 
467 /*
468  * Temporary structure for representing an arc during packaging.
469  */
470 typedef struct
471 {
476 
477 
478 /* prototypes for private functions */
479 static TRGM *createTrgmNFAInternal(regex_t *regex, TrgmPackedGraph **graph,
480  MemoryContext rcontext);
481 static void RE_compile(regex_t *regex, text *text_re,
482  int cflags, Oid collation);
483 static void getColorInfo(regex_t *regex, TrgmNFA *trgmNFA);
484 static bool convertPgWchar(pg_wchar c, trgm_mb_char *result);
485 static void transformGraph(TrgmNFA *trgmNFA);
486 static void processState(TrgmNFA *trgmNFA, TrgmState *state);
487 static void addKey(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key);
488 static void addKeyToQueue(TrgmNFA *trgmNFA, TrgmStateKey *key);
489 static void addArcs(TrgmNFA *trgmNFA, TrgmState *state);
490 static void addArc(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key,
491  TrgmColor co, TrgmStateKey *destKey);
492 static bool validArcLabel(TrgmStateKey *key, TrgmColor co);
493 static TrgmState *getState(TrgmNFA *trgmNFA, TrgmStateKey *key);
494 static bool prefixContains(TrgmPrefix *prefix1, TrgmPrefix *prefix2);
495 static bool selectColorTrigrams(TrgmNFA *trgmNFA);
496 static TRGM *expandColorTrigrams(TrgmNFA *trgmNFA, MemoryContext rcontext);
497 static void fillTrgm(trgm *ptrgm, trgm_mb_char s[3]);
498 static void mergeStates(TrgmState *state1, TrgmState *state2);
499 static int colorTrgmInfoCmp(const void *p1, const void *p2);
500 static int colorTrgmInfoPenaltyCmp(const void *p1, const void *p2);
501 static TrgmPackedGraph *packGraph(TrgmNFA *trgmNFA, MemoryContext rcontext);
502 static int packArcInfoCmp(const void *a1, const void *a2);
503 
504 #ifdef TRGM_REGEXP_DEBUG
505 static void printSourceNFA(regex_t *regex, TrgmColorInfo *colors, int ncolors);
506 static void printTrgmNFA(TrgmNFA *trgmNFA);
507 static void printTrgmColor(StringInfo buf, TrgmColor co);
508 static void printTrgmPackedGraph(TrgmPackedGraph *packedGraph, TRGM *trigrams);
509 #endif
510 
511 
512 /*
513  * Main entry point to process a regular expression.
514  *
515  * Returns an array of trigrams required by the regular expression, or NULL if
516  * the regular expression was too complex to analyze. In addition, a packed
517  * graph representation of the regex is returned into *graph. The results
518  * must be allocated in rcontext (which might or might not be the current
519  * context).
520  */
521 TRGM *
522 createTrgmNFA(text *text_re, Oid collation,
523  TrgmPackedGraph **graph, MemoryContext rcontext)
524 {
525  TRGM *trg;
526  regex_t regex;
527  MemoryContext tmpcontext;
528  MemoryContext oldcontext;
529 
530  /*
531  * This processing generates a great deal of cruft, which we'd like to
532  * clean up before returning (since this function may be called in a
533  * query-lifespan memory context). Make a temp context we can work in so
534  * that cleanup is easy.
535  */
537  "createTrgmNFA temporary context",
539  oldcontext = MemoryContextSwitchTo(tmpcontext);
540 
541  /*
542  * Stage 1: Compile the regexp into a NFA, using the regexp library.
543  */
544 #ifdef IGNORECASE
545  RE_compile(&regex, text_re,
546  REG_ADVANCED | REG_NOSUB | REG_ICASE, collation);
547 #else
548  RE_compile(&regex, text_re,
549  REG_ADVANCED | REG_NOSUB, collation);
550 #endif
551 
552  trg = createTrgmNFAInternal(&regex, graph, rcontext);
553 
554  /* Clean up all the cruft we created (including regex) */
555  MemoryContextSwitchTo(oldcontext);
556  MemoryContextDelete(tmpcontext);
557 
558  return trg;
559 }
560 
561 /*
562  * Body of createTrgmNFA, exclusive of regex compilation/freeing.
563  */
564 static TRGM *
566  MemoryContext rcontext)
567 {
568  TRGM *trg;
569  TrgmNFA trgmNFA;
570 
571  trgmNFA.regex = regex;
572 
573  /* Collect color information from the regex */
574  getColorInfo(regex, &trgmNFA);
575 
576 #ifdef TRGM_REGEXP_DEBUG
577  printSourceNFA(regex, trgmNFA.colorInfo, trgmNFA.ncolors);
578 #endif
579 
580  /*
581  * Stage 2: Create an expanded graph from the source NFA.
582  */
583  transformGraph(&trgmNFA);
584 
585 #ifdef TRGM_REGEXP_DEBUG
586  printTrgmNFA(&trgmNFA);
587 #endif
588 
589  /*
590  * Fail if we were unable to make a nontrivial graph, ie it is possible to
591  * get from the initial state to the final state without reading any
592  * predictable trigram.
593  */
594  if (trgmNFA.initState->flags & TSTATE_FIN)
595  return NULL;
596 
597  /*
598  * Stage 3: Select color trigrams to expand. Fail if too many trigrams.
599  */
600  if (!selectColorTrigrams(&trgmNFA))
601  return NULL;
602 
603  /*
604  * Stage 4: Expand color trigrams and pack graph into final
605  * representation.
606  */
607  trg = expandColorTrigrams(&trgmNFA, rcontext);
608 
609  *graph = packGraph(&trgmNFA, rcontext);
610 
611 #ifdef TRGM_REGEXP_DEBUG
612  printTrgmPackedGraph(*graph, trg);
613 #endif
614 
615  return trg;
616 }
617 
618 /*
619  * Main entry point for evaluating a graph during index scanning.
620  *
621  * The check[] array is indexed by trigram number (in the array of simple
622  * trigrams returned by createTrgmNFA), and holds true for those trigrams
623  * that are present in the index entry being checked.
624  */
625 bool
627 {
628  int i,
629  j,
630  k,
631  queueIn,
632  queueOut;
633 
634  /*
635  * Reset temporary working areas.
636  */
637  memset(graph->colorTrigramsActive, 0,
638  sizeof(bool) * graph->colorTrigramsCount);
639  memset(graph->statesActive, 0, sizeof(bool) * graph->statesCount);
640 
641  /*
642  * Check which color trigrams were matched. A match for any simple
643  * trigram associated with a color trigram counts as a match of the color
644  * trigram.
645  */
646  j = 0;
647  for (i = 0; i < graph->colorTrigramsCount; i++)
648  {
649  int cnt = graph->colorTrigramGroups[i];
650 
651  for (k = j; k < j + cnt; k++)
652  {
653  if (check[k])
654  {
655  /*
656  * Found one matched trigram in the group. Can skip the rest
657  * of them and go to the next group.
658  */
659  graph->colorTrigramsActive[i] = true;
660  break;
661  }
662  }
663  j = j + cnt;
664  }
665 
666  /*
667  * Initialize the statesQueue to hold just the initial state. Note:
668  * statesQueue has room for statesCount entries, which is certainly enough
669  * since no state will be put in the queue more than once. The
670  * statesActive array marks which states have been queued.
671  */
672  graph->statesActive[0] = true;
673  graph->statesQueue[0] = 0;
674  queueIn = 0;
675  queueOut = 1;
676 
677  /* Process queued states as long as there are any. */
678  while (queueIn < queueOut)
679  {
680  int stateno = graph->statesQueue[queueIn++];
681  TrgmPackedState *state = &graph->states[stateno];
682  int cnt = state->arcsCount;
683 
684  /* Loop over state's out-arcs */
685  for (i = 0; i < cnt; i++)
686  {
687  TrgmPackedArc *arc = &state->arcs[i];
688 
689  /*
690  * If corresponding color trigram is present then activate the
691  * corresponding state. We're done if that's the final state,
692  * otherwise queue the state if it's not been queued already.
693  */
694  if (graph->colorTrigramsActive[arc->colorTrgm])
695  {
696  int nextstate = arc->targetState;
697 
698  if (nextstate == 1)
699  return true; /* success: final state is reachable */
700 
701  if (!graph->statesActive[nextstate])
702  {
703  graph->statesActive[nextstate] = true;
704  graph->statesQueue[queueOut++] = nextstate;
705  }
706  }
707  }
708  }
709 
710  /* Queue is empty, so match fails. */
711  return false;
712 }
713 
714 /*
715  * Compile regex string into struct at *regex.
716  * NB: pg_regfree must be applied to regex if this completes successfully.
717  */
718 static void
719 RE_compile(regex_t *regex, text *text_re, int cflags, Oid collation)
720 {
721  int text_re_len = VARSIZE_ANY_EXHDR(text_re);
722  char *text_re_val = VARDATA_ANY(text_re);
723  pg_wchar *pattern;
724  int pattern_len;
725  int regcomp_result;
726  char errMsg[100];
727 
728  /* Convert pattern string to wide characters */
729  pattern = (pg_wchar *) palloc((text_re_len + 1) * sizeof(pg_wchar));
730  pattern_len = pg_mb2wchar_with_len(text_re_val,
731  pattern,
732  text_re_len);
733 
734  /* Compile regex */
735  regcomp_result = pg_regcomp(regex,
736  pattern,
737  pattern_len,
738  cflags,
739  collation);
740 
741  pfree(pattern);
742 
743  if (regcomp_result != REG_OKAY)
744  {
745  /* re didn't compile (no need for pg_regfree, if so) */
746  pg_regerror(regcomp_result, regex, errMsg, sizeof(errMsg));
747  ereport(ERROR,
748  (errcode(ERRCODE_INVALID_REGULAR_EXPRESSION),
749  errmsg("invalid regular expression: %s", errMsg)));
750  }
751 }
752 
753 
754 /*---------------------
755  * Subroutines for pre-processing the color map (stage 1).
756  *---------------------
757  */
758 
759 /*
760  * Fill TrgmColorInfo structure for each color using regex export functions.
761  */
762 static void
763 getColorInfo(regex_t *regex, TrgmNFA *trgmNFA)
764 {
765  int colorsCount = pg_reg_getnumcolors(regex);
766  int i;
767 
768  trgmNFA->ncolors = colorsCount;
769  trgmNFA->colorInfo = (TrgmColorInfo *)
770  palloc0(colorsCount * sizeof(TrgmColorInfo));
771 
772  /*
773  * Loop over colors, filling TrgmColorInfo about each. Note we include
774  * WHITE (0) even though we know it'll be reported as non-expandable.
775  */
776  for (i = 0; i < colorsCount; i++)
777  {
778  TrgmColorInfo *colorInfo = &trgmNFA->colorInfo[i];
779  int charsCount = pg_reg_getnumcharacters(regex, i);
780  pg_wchar *chars;
781  int j;
782 
783  if (charsCount < 0 || charsCount > COLOR_COUNT_LIMIT)
784  {
785  /* Non expandable, or too large to work with */
786  colorInfo->expandable = false;
787  continue;
788  }
789 
790  colorInfo->expandable = true;
791  colorInfo->containsNonWord = false;
792  colorInfo->wordChars = (trgm_mb_char *)
793  palloc(sizeof(trgm_mb_char) * charsCount);
794  colorInfo->wordCharsCount = 0;
795 
796  /* Extract all the chars in this color */
797  chars = (pg_wchar *) palloc(sizeof(pg_wchar) * charsCount);
798  pg_reg_getcharacters(regex, i, chars, charsCount);
799 
800  /*
801  * Convert characters back to multibyte form, and save only those that
802  * are word characters. Set "containsNonWord" if any non-word
803  * character. (Note: it'd probably be nicer to keep the chars in
804  * pg_wchar format for now, but ISWORDCHR wants to see multibyte.)
805  */
806  for (j = 0; j < charsCount; j++)
807  {
808  trgm_mb_char c;
809 
810  if (!convertPgWchar(chars[j], &c))
811  continue; /* ok to ignore it altogether */
812  if (ISWORDCHR(c.bytes))
813  colorInfo->wordChars[colorInfo->wordCharsCount++] = c;
814  else
815  colorInfo->containsNonWord = true;
816  }
817 
818  pfree(chars);
819  }
820 }
821 
822 /*
823  * Convert pg_wchar to multibyte format.
824  * Returns false if the character should be ignored completely.
825  */
826 static bool
828 {
829  /* "s" has enough space for a multibyte character and a trailing NUL */
830  char s[MAX_MULTIBYTE_CHAR_LEN + 1];
831 
832  /*
833  * We can ignore the NUL character, since it can never appear in a PG text
834  * string. This avoids the need for various special cases when
835  * reconstructing trigrams.
836  */
837  if (c == 0)
838  return false;
839 
840  /* Do the conversion, making sure the result is NUL-terminated */
841  memset(s, 0, sizeof(s));
842  pg_wchar2mb_with_len(&c, s, 1);
843 
844  /*
845  * In IGNORECASE mode, we can ignore uppercase characters. We assume that
846  * the regex engine generated both uppercase and lowercase equivalents
847  * within each color, since we used the REG_ICASE option; so there's no
848  * need to process the uppercase version.
849  *
850  * XXX this code is dependent on the assumption that lowerstr() works the
851  * same as the regex engine's internal case folding machinery. Might be
852  * wiser to expose pg_wc_tolower and test whether c == pg_wc_tolower(c).
853  * On the other hand, the trigrams in the index were created using
854  * lowerstr(), so we're probably screwed if there's any incompatibility
855  * anyway.
856  */
857 #ifdef IGNORECASE
858  {
859  char *lowerCased = lowerstr(s);
860 
861  if (strcmp(lowerCased, s) != 0)
862  {
863  pfree(lowerCased);
864  return false;
865  }
866  pfree(lowerCased);
867  }
868 #endif
869 
870  /* Fill result with exactly MAX_MULTIBYTE_CHAR_LEN bytes */
871  memcpy(result->bytes, s, MAX_MULTIBYTE_CHAR_LEN);
872  return true;
873 }
874 
875 
876 /*---------------------
877  * Subroutines for expanding original NFA graph into a trigram graph (stage 2).
878  *---------------------
879  */
880 
881 /*
882  * Transform the graph, given a regex and extracted color information.
883  *
884  * We create and process a queue of expanded-graph states until all the states
885  * are processed.
886  *
887  * This algorithm may be stopped due to resource limitation. In this case we
888  * force every unprocessed branch to immediately finish with matching (this
889  * can give us false positives but no false negatives) by marking all
890  * unprocessed states as final.
891  */
892 static void
894 {
895  HASHCTL hashCtl;
896  TrgmStateKey initkey;
897  TrgmState *initstate;
898  ListCell *lc;
899 
900  /* Initialize this stage's workspace in trgmNFA struct */
901  trgmNFA->queue = NIL;
902  trgmNFA->keysQueue = NIL;
903  trgmNFA->arcsCount = 0;
904  trgmNFA->overflowed = false;
905 
906  /* Create hashtable for states */
907  hashCtl.keysize = sizeof(TrgmStateKey);
908  hashCtl.entrysize = sizeof(TrgmState);
909  hashCtl.hcxt = CurrentMemoryContext;
910  trgmNFA->states = hash_create("Trigram NFA",
911  1024,
912  &hashCtl,
914  trgmNFA->nstates = 0;
915 
916  /* Create initial state: ambiguous prefix, NFA's initial state */
917  MemSet(&initkey, 0, sizeof(initkey));
918  initkey.prefix.colors[0] = COLOR_UNKNOWN;
919  initkey.prefix.colors[1] = COLOR_UNKNOWN;
920  initkey.nstate = pg_reg_getinitialstate(trgmNFA->regex);
921 
922  initstate = getState(trgmNFA, &initkey);
923  initstate->flags |= TSTATE_INIT;
924  trgmNFA->initState = initstate;
925 
926  /*
927  * Recursively build the expanded graph by processing queue of states
928  * (breadth-first search). getState already put initstate in the queue.
929  * Note that getState will append new states to the queue within the loop,
930  * too; this works as long as we don't do repeat fetches using the "lc"
931  * pointer.
932  */
933  foreach(lc, trgmNFA->queue)
934  {
935  TrgmState *state = (TrgmState *) lfirst(lc);
936 
937  /*
938  * If we overflowed then just mark state as final. Otherwise do
939  * actual processing.
940  */
941  if (trgmNFA->overflowed)
942  state->flags |= TSTATE_FIN;
943  else
944  processState(trgmNFA, state);
945 
946  /* Did we overflow? */
947  if (trgmNFA->arcsCount > MAX_EXPANDED_ARCS ||
949  trgmNFA->overflowed = true;
950  }
951 }
952 
953 /*
954  * Process one state: add enter keys and then add outgoing arcs.
955  */
956 static void
958 {
959  ListCell *lc;
960 
961  /* keysQueue should be NIL already, but make sure */
962  trgmNFA->keysQueue = NIL;
963 
964  /*
965  * Add state's own key, and then process all keys added to keysQueue until
966  * queue is finished. But we can quit if the state gets marked final.
967  */
968  addKey(trgmNFA, state, &state->stateKey);
969  foreach(lc, trgmNFA->keysQueue)
970  {
971  TrgmStateKey *key = (TrgmStateKey *) lfirst(lc);
972 
973  if (state->flags & TSTATE_FIN)
974  break;
975  addKey(trgmNFA, state, key);
976  }
977 
978  /* Release keysQueue to clean up for next cycle */
979  list_free(trgmNFA->keysQueue);
980  trgmNFA->keysQueue = NIL;
981 
982  /*
983  * Add outgoing arcs only if state isn't final (we have no interest in
984  * outgoing arcs if we already match)
985  */
986  if (!(state->flags & TSTATE_FIN))
987  addArcs(trgmNFA, state);
988 }
989 
990 /*
991  * Add the given enter key into the state's enterKeys list, and determine
992  * whether this should result in any further enter keys being added.
993  * If so, add those keys to keysQueue so that processState will handle them.
994  *
995  * If the enter key is for the NFA's final state, mark state as TSTATE_FIN.
996  * This situation means that we can reach the final state from this expanded
997  * state without reading any predictable trigram, so we must consider this
998  * state as an accepting one.
999  *
1000  * The given key could be a duplicate of one already in enterKeys, or be
1001  * redundant with some enterKeys. So we check that before doing anything.
1002  *
1003  * Note that we don't generate any actual arcs here. addArcs will do that
1004  * later, after we have identified all the enter keys for this state.
1005  */
1006 static void
1008 {
1009  regex_arc_t *arcs;
1010  TrgmStateKey destKey;
1011  ListCell *cell;
1012  int i,
1013  arcsCount;
1014 
1015  /*
1016  * Ensure any pad bytes in destKey are zero, since it may get used as a
1017  * hashtable key by getState.
1018  */
1019  MemSet(&destKey, 0, sizeof(destKey));
1020 
1021  /*
1022  * Compare key to each existing enter key of the state to check for
1023  * redundancy. We can drop either old key(s) or the new key if we find
1024  * redundancy.
1025  */
1026  foreach(cell, state->enterKeys)
1027  {
1028  TrgmStateKey *existingKey = (TrgmStateKey *) lfirst(cell);
1029 
1030  if (existingKey->nstate == key->nstate)
1031  {
1032  if (prefixContains(&existingKey->prefix, &key->prefix))
1033  {
1034  /* This old key already covers the new key. Nothing to do */
1035  return;
1036  }
1037  if (prefixContains(&key->prefix, &existingKey->prefix))
1038  {
1039  /*
1040  * The new key covers this old key. Remove the old key, it's
1041  * no longer needed once we add this key to the list.
1042  */
1043  state->enterKeys = foreach_delete_current(state->enterKeys,
1044  cell);
1045  }
1046  }
1047  }
1048 
1049  /* No redundancy, so add this key to the state's list */
1050  state->enterKeys = lappend(state->enterKeys, key);
1051 
1052  /* If state is now known final, mark it and we're done */
1053  if (key->nstate == pg_reg_getfinalstate(trgmNFA->regex))
1054  {
1055  state->flags |= TSTATE_FIN;
1056  return;
1057  }
1058 
1059  /*
1060  * Loop through all outgoing arcs of the corresponding state in the
1061  * original NFA.
1062  */
1063  arcsCount = pg_reg_getnumoutarcs(trgmNFA->regex, key->nstate);
1064  arcs = (regex_arc_t *) palloc(sizeof(regex_arc_t) * arcsCount);
1065  pg_reg_getoutarcs(trgmNFA->regex, key->nstate, arcs, arcsCount);
1066 
1067  for (i = 0; i < arcsCount; i++)
1068  {
1069  regex_arc_t *arc = &arcs[i];
1070 
1071  if (pg_reg_colorisbegin(trgmNFA->regex, arc->co))
1072  {
1073  /*
1074  * Start of line/string (^). Trigram extraction treats start of
1075  * line same as start of word: double space prefix is added.
1076  * Hence, make an enter key showing we can reach the arc
1077  * destination with all-blank prefix.
1078  */
1079  destKey.prefix.colors[0] = COLOR_BLANK;
1080  destKey.prefix.colors[1] = COLOR_BLANK;
1081  destKey.nstate = arc->to;
1082 
1083  /* Add enter key to this state */
1084  addKeyToQueue(trgmNFA, &destKey);
1085  }
1086  else if (pg_reg_colorisend(trgmNFA->regex, arc->co))
1087  {
1088  /*
1089  * End of line/string ($). We must consider this arc as a
1090  * transition that doesn't read anything. The reason for adding
1091  * this enter key to the state is that if the arc leads to the
1092  * NFA's final state, we must mark this expanded state as final.
1093  */
1094  destKey.prefix.colors[0] = COLOR_UNKNOWN;
1095  destKey.prefix.colors[1] = COLOR_UNKNOWN;
1096  destKey.nstate = arc->to;
1097 
1098  /* Add enter key to this state */
1099  addKeyToQueue(trgmNFA, &destKey);
1100  }
1101  else if (arc->co >= 0)
1102  {
1103  /* Regular color (including WHITE) */
1104  TrgmColorInfo *colorInfo = &trgmNFA->colorInfo[arc->co];
1105 
1106  if (colorInfo->expandable)
1107  {
1108  if (colorInfo->containsNonWord &&
1110  {
1111  /*
1112  * We can reach the arc destination after reading a
1113  * non-word character, but the prefix is not something
1114  * that addArc will accept with COLOR_BLANK, so no trigram
1115  * arc can get made for this transition. We must make an
1116  * enter key to show that the arc destination is
1117  * reachable. Set it up with an all-blank prefix, since
1118  * that corresponds to what the trigram extraction code
1119  * will do at a word starting boundary.
1120  */
1121  destKey.prefix.colors[0] = COLOR_BLANK;
1122  destKey.prefix.colors[1] = COLOR_BLANK;
1123  destKey.nstate = arc->to;
1124  addKeyToQueue(trgmNFA, &destKey);
1125  }
1126 
1127  if (colorInfo->wordCharsCount > 0 &&
1128  !validArcLabel(key, arc->co))
1129  {
1130  /*
1131  * We can reach the arc destination after reading a word
1132  * character, but the prefix is not something that addArc
1133  * will accept, so no trigram arc can get made for this
1134  * transition. We must make an enter key to show that the
1135  * arc destination is reachable. The prefix for the enter
1136  * key should reflect the info we have for this arc.
1137  */
1138  destKey.prefix.colors[0] = key->prefix.colors[1];
1139  destKey.prefix.colors[1] = arc->co;
1140  destKey.nstate = arc->to;
1141  addKeyToQueue(trgmNFA, &destKey);
1142  }
1143  }
1144  else
1145  {
1146  /*
1147  * Unexpandable color. Add enter key with ambiguous prefix,
1148  * showing we can reach the destination from this state, but
1149  * the preceding colors will be uncertain. (We do not set the
1150  * first prefix color to key->prefix.colors[1], because a
1151  * prefix of known followed by unknown is invalid.)
1152  */
1153  destKey.prefix.colors[0] = COLOR_UNKNOWN;
1154  destKey.prefix.colors[1] = COLOR_UNKNOWN;
1155  destKey.nstate = arc->to;
1156  addKeyToQueue(trgmNFA, &destKey);
1157  }
1158  }
1159  else
1160  {
1161  /* RAINBOW: treat as unexpandable color */
1162  destKey.prefix.colors[0] = COLOR_UNKNOWN;
1163  destKey.prefix.colors[1] = COLOR_UNKNOWN;
1164  destKey.nstate = arc->to;
1165  addKeyToQueue(trgmNFA, &destKey);
1166  }
1167  }
1168 
1169  pfree(arcs);
1170 }
1171 
1172 /*
1173  * Add copy of given key to keysQueue for later processing.
1174  */
1175 static void
1177 {
1178  TrgmStateKey *keyCopy = (TrgmStateKey *) palloc(sizeof(TrgmStateKey));
1179 
1180  memcpy(keyCopy, key, sizeof(TrgmStateKey));
1181  trgmNFA->keysQueue = lappend(trgmNFA->keysQueue, keyCopy);
1182 }
1183 
1184 /*
1185  * Add outgoing arcs from given state, whose enter keys are all now known.
1186  */
1187 static void
1189 {
1190  TrgmStateKey destKey;
1191  ListCell *cell;
1192  regex_arc_t *arcs;
1193  int arcsCount,
1194  i;
1195 
1196  /*
1197  * Ensure any pad bytes in destKey are zero, since it may get used as a
1198  * hashtable key by getState.
1199  */
1200  MemSet(&destKey, 0, sizeof(destKey));
1201 
1202  /*
1203  * Iterate over enter keys associated with this expanded-graph state. This
1204  * includes both the state's own stateKey, and any enter keys we added to
1205  * it during addKey (which represent expanded-graph states that are not
1206  * distinguishable from this one by means of trigrams). For each such
1207  * enter key, examine all the out-arcs of the key's underlying NFA state,
1208  * and try to make a trigram arc leading to where the out-arc leads.
1209  * (addArc will deal with whether the arc is valid or not.)
1210  */
1211  foreach(cell, state->enterKeys)
1212  {
1213  TrgmStateKey *key = (TrgmStateKey *) lfirst(cell);
1214 
1215  arcsCount = pg_reg_getnumoutarcs(trgmNFA->regex, key->nstate);
1216  arcs = (regex_arc_t *) palloc(sizeof(regex_arc_t) * arcsCount);
1217  pg_reg_getoutarcs(trgmNFA->regex, key->nstate, arcs, arcsCount);
1218 
1219  for (i = 0; i < arcsCount; i++)
1220  {
1221  regex_arc_t *arc = &arcs[i];
1222  TrgmColorInfo *colorInfo;
1223 
1224  /*
1225  * Ignore non-expandable colors; addKey already handled the case.
1226  *
1227  * We need no special check for WHITE or begin/end pseudocolors
1228  * here. We don't need to do any processing for them, and they
1229  * will be marked non-expandable since the regex engine will have
1230  * reported them that way. We do have to watch out for RAINBOW,
1231  * which has a negative color number.
1232  */
1233  if (arc->co < 0)
1234  continue;
1235  Assert(arc->co < trgmNFA->ncolors);
1236 
1237  colorInfo = &trgmNFA->colorInfo[arc->co];
1238  if (!colorInfo->expandable)
1239  continue;
1240 
1241  if (colorInfo->containsNonWord)
1242  {
1243  /*
1244  * Color includes non-word character(s).
1245  *
1246  * Generate an arc, treating this transition as occurring on
1247  * BLANK. This allows word-ending trigrams to be manufactured
1248  * if possible.
1249  */
1250  destKey.prefix.colors[0] = key->prefix.colors[1];
1251  destKey.prefix.colors[1] = COLOR_BLANK;
1252  destKey.nstate = arc->to;
1253 
1254  addArc(trgmNFA, state, key, COLOR_BLANK, &destKey);
1255  }
1256 
1257  if (colorInfo->wordCharsCount > 0)
1258  {
1259  /*
1260  * Color includes word character(s).
1261  *
1262  * Generate an arc. Color is pushed into prefix of target
1263  * state.
1264  */
1265  destKey.prefix.colors[0] = key->prefix.colors[1];
1266  destKey.prefix.colors[1] = arc->co;
1267  destKey.nstate = arc->to;
1268 
1269  addArc(trgmNFA, state, key, arc->co, &destKey);
1270  }
1271  }
1272 
1273  pfree(arcs);
1274  }
1275 }
1276 
1277 /*
1278  * Generate an out-arc of the expanded graph, if it's valid and not redundant.
1279  *
1280  * state: expanded-graph state we want to add an out-arc to
1281  * key: provides prefix colors (key->nstate is not used)
1282  * co: transition color
1283  * destKey: identifier for destination state of expanded graph
1284  */
1285 static void
1287  TrgmColor co, TrgmStateKey *destKey)
1288 {
1289  TrgmArc *arc;
1290  ListCell *cell;
1291 
1292  /* Do nothing if this wouldn't be a valid arc label trigram */
1293  if (!validArcLabel(key, co))
1294  return;
1295 
1296  /*
1297  * Check if we are going to reach key which is covered by a key which is
1298  * already listed in this state. If so arc is useless: the NFA can bypass
1299  * it through a path that doesn't require any predictable trigram, so
1300  * whether the arc's trigram is present or not doesn't really matter.
1301  */
1302  foreach(cell, state->enterKeys)
1303  {
1304  TrgmStateKey *existingKey = (TrgmStateKey *) lfirst(cell);
1305 
1306  if (existingKey->nstate == destKey->nstate &&
1307  prefixContains(&existingKey->prefix, &destKey->prefix))
1308  return;
1309  }
1310 
1311  /* Checks were successful, add new arc */
1312  arc = (TrgmArc *) palloc(sizeof(TrgmArc));
1313  arc->target = getState(trgmNFA, destKey);
1314  arc->ctrgm.colors[0] = key->prefix.colors[0];
1315  arc->ctrgm.colors[1] = key->prefix.colors[1];
1316  arc->ctrgm.colors[2] = co;
1317 
1318  state->arcs = lappend(state->arcs, arc);
1319  trgmNFA->arcsCount++;
1320 }
1321 
1322 /*
1323  * Can we make a valid trigram arc label from the given prefix and arc color?
1324  *
1325  * This is split out so that tests in addKey and addArc will stay in sync.
1326  */
1327 static bool
1329 {
1330  /*
1331  * We have to know full trigram in order to add outgoing arc. So we can't
1332  * do it if prefix is ambiguous.
1333  */
1334  if (key->prefix.colors[0] == COLOR_UNKNOWN)
1335  return false;
1336 
1337  /* If key->prefix.colors[0] isn't unknown, its second color isn't either */
1338  Assert(key->prefix.colors[1] != COLOR_UNKNOWN);
1339  /* And we should not be called with an unknown arc color anytime */
1340  Assert(co != COLOR_UNKNOWN);
1341 
1342  /*
1343  * We don't bother with making arcs representing three non-word
1344  * characters, since that's useless for trigram extraction.
1345  */
1346  if (key->prefix.colors[0] == COLOR_BLANK &&
1347  key->prefix.colors[1] == COLOR_BLANK &&
1348  co == COLOR_BLANK)
1349  return false;
1350 
1351  /*
1352  * We also reject nonblank-blank-anything. The nonblank-blank-nonblank
1353  * case doesn't correspond to any trigram the trigram extraction code
1354  * would make. The nonblank-blank-blank case is also not possible with
1355  * RPADDING = 1. (Note that in many cases we'd fail to generate such a
1356  * trigram even if it were valid, for example processing "foo bar" will
1357  * not result in considering the trigram "o ". So if you want to support
1358  * RPADDING = 2, there's more to do than just twiddle this test.)
1359  */
1360  if (key->prefix.colors[0] != COLOR_BLANK &&
1361  key->prefix.colors[1] == COLOR_BLANK)
1362  return false;
1363 
1364  /*
1365  * Other combinations involving blank are valid, in particular we assume
1366  * blank-blank-nonblank is valid, which presumes that LPADDING is 2.
1367  *
1368  * Note: Using again the example "foo bar", we will not consider the
1369  * trigram " b", though this trigram would be found by the trigram
1370  * extraction code. Since we will find " ba", it doesn't seem worth
1371  * trying to hack the algorithm to generate the additional trigram.
1372  */
1373 
1374  /* arc label is valid */
1375  return true;
1376 }
1377 
1378 /*
1379  * Get state of expanded graph for given state key,
1380  * and queue the state for processing if it didn't already exist.
1381  */
1382 static TrgmState *
1384 {
1385  TrgmState *state;
1386  bool found;
1387 
1388  state = (TrgmState *) hash_search(trgmNFA->states, key, HASH_ENTER,
1389  &found);
1390  if (!found)
1391  {
1392  /* New state: initialize and queue it */
1393  state->arcs = NIL;
1394  state->enterKeys = NIL;
1395  state->flags = 0;
1396  /* states are initially given negative numbers */
1397  state->snumber = -(++trgmNFA->nstates);
1398  state->parent = NULL;
1399  state->tentFlags = 0;
1400  state->tentParent = NULL;
1401 
1402  trgmNFA->queue = lappend(trgmNFA->queue, state);
1403  }
1404  return state;
1405 }
1406 
1407 /*
1408  * Check if prefix1 "contains" prefix2.
1409  *
1410  * "contains" means that any exact prefix (with no ambiguity) that satisfies
1411  * prefix2 also satisfies prefix1.
1412  */
1413 static bool
1415 {
1416  if (prefix1->colors[1] == COLOR_UNKNOWN)
1417  {
1418  /* Fully ambiguous prefix contains everything */
1419  return true;
1420  }
1421  else if (prefix1->colors[0] == COLOR_UNKNOWN)
1422  {
1423  /*
1424  * Prefix with only first unknown color contains every prefix with
1425  * same second color.
1426  */
1427  if (prefix1->colors[1] == prefix2->colors[1])
1428  return true;
1429  else
1430  return false;
1431  }
1432  else
1433  {
1434  /* Exact prefix contains only the exact same prefix */
1435  if (prefix1->colors[0] == prefix2->colors[0] &&
1436  prefix1->colors[1] == prefix2->colors[1])
1437  return true;
1438  else
1439  return false;
1440  }
1441 }
1442 
1443 
1444 /*---------------------
1445  * Subroutines for expanding color trigrams into regular trigrams (stage 3).
1446  *---------------------
1447  */
1448 
1449 /*
1450  * Get vector of all color trigrams in graph and select which of them
1451  * to expand into simple trigrams.
1452  *
1453  * Returns true if OK, false if exhausted resource limits.
1454  */
1455 static bool
1457 {
1458  HASH_SEQ_STATUS scan_status;
1459  int arcsCount = trgmNFA->arcsCount,
1460  i;
1461  TrgmState *state;
1462  ColorTrgmInfo *colorTrgms;
1463  int64 totalTrgmCount;
1464  float4 totalTrgmPenalty;
1465  int cnumber;
1466 
1467  /* Collect color trigrams from all arcs */
1468  colorTrgms = (ColorTrgmInfo *) palloc0(sizeof(ColorTrgmInfo) * arcsCount);
1469  trgmNFA->colorTrgms = colorTrgms;
1470 
1471  i = 0;
1472  hash_seq_init(&scan_status, trgmNFA->states);
1473  while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
1474  {
1475  ListCell *cell;
1476 
1477  foreach(cell, state->arcs)
1478  {
1479  TrgmArc *arc = (TrgmArc *) lfirst(cell);
1480  TrgmArcInfo *arcInfo = (TrgmArcInfo *) palloc(sizeof(TrgmArcInfo));
1481  ColorTrgmInfo *trgmInfo = &colorTrgms[i];
1482 
1483  arcInfo->source = state;
1484  arcInfo->target = arc->target;
1485  trgmInfo->ctrgm = arc->ctrgm;
1486  trgmInfo->cnumber = -1;
1487  /* count and penalty will be set below */
1488  trgmInfo->expanded = true;
1489  trgmInfo->arcs = list_make1(arcInfo);
1490  i++;
1491  }
1492  }
1493  Assert(i == arcsCount);
1494 
1495  /* Remove duplicates, merging their arcs lists */
1496  if (arcsCount >= 2)
1497  {
1498  ColorTrgmInfo *p1,
1499  *p2;
1500 
1501  /* Sort trigrams to ease duplicate detection */
1502  qsort(colorTrgms, arcsCount, sizeof(ColorTrgmInfo), colorTrgmInfoCmp);
1503 
1504  /* p1 is probe point, p2 is last known non-duplicate. */
1505  p2 = colorTrgms;
1506  for (p1 = colorTrgms + 1; p1 < colorTrgms + arcsCount; p1++)
1507  {
1508  if (colorTrgmInfoCmp(p1, p2) > 0)
1509  {
1510  p2++;
1511  *p2 = *p1;
1512  }
1513  else
1514  {
1515  p2->arcs = list_concat(p2->arcs, p1->arcs);
1516  }
1517  }
1518  trgmNFA->colorTrgmsCount = (p2 - colorTrgms) + 1;
1519  }
1520  else
1521  {
1522  trgmNFA->colorTrgmsCount = arcsCount;
1523  }
1524 
1525  /*
1526  * Count number of simple trigrams generated by each color trigram, and
1527  * also compute a penalty value, which is the number of simple trigrams
1528  * times a multiplier that depends on its whitespace content.
1529  *
1530  * Note: per-color-trigram counts cannot overflow an int so long as
1531  * COLOR_COUNT_LIMIT is not more than the cube root of INT_MAX, ie about
1532  * 1290. However, the grand total totalTrgmCount might conceivably
1533  * overflow an int, so we use int64 for that within this routine. Also,
1534  * penalties are calculated in float4 arithmetic to avoid any overflow
1535  * worries.
1536  */
1537  totalTrgmCount = 0;
1538  totalTrgmPenalty = 0.0f;
1539  for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
1540  {
1541  ColorTrgmInfo *trgmInfo = &colorTrgms[i];
1542  int j,
1543  count = 1,
1544  typeIndex = 0;
1545 
1546  for (j = 0; j < 3; j++)
1547  {
1548  TrgmColor c = trgmInfo->ctrgm.colors[j];
1549 
1550  typeIndex *= 2;
1551  if (c == COLOR_BLANK)
1552  typeIndex++;
1553  else
1554  count *= trgmNFA->colorInfo[c].wordCharsCount;
1555  }
1556  trgmInfo->count = count;
1557  totalTrgmCount += count;
1558  trgmInfo->penalty = penalties[typeIndex] * (float4) count;
1559  totalTrgmPenalty += trgmInfo->penalty;
1560  }
1561 
1562  /* Sort color trigrams in descending order of their penalties */
1563  qsort(colorTrgms, trgmNFA->colorTrgmsCount, sizeof(ColorTrgmInfo),
1565 
1566  /*
1567  * Remove color trigrams from the graph so long as total penalty of color
1568  * trigrams exceeds WISH_TRGM_PENALTY. (If we fail to get down to
1569  * WISH_TRGM_PENALTY, it's OK so long as total count is no more than
1570  * MAX_TRGM_COUNT.) We prefer to remove color trigrams with higher
1571  * penalty, since those are the most promising for reducing the total
1572  * penalty. When removing a color trigram we have to merge states
1573  * connected by arcs labeled with that trigram. It's necessary to not
1574  * merge initial and final states, because our graph becomes useless if
1575  * that happens; so we cannot always remove the trigram we'd prefer to.
1576  */
1577  for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
1578  {
1579  ColorTrgmInfo *trgmInfo = &colorTrgms[i];
1580  bool canRemove = true;
1581  ListCell *cell;
1582 
1583  /* Done if we've reached the target */
1584  if (totalTrgmPenalty <= WISH_TRGM_PENALTY)
1585  break;
1586 
1587 #ifdef TRGM_REGEXP_DEBUG
1588  fprintf(stderr, "considering ctrgm %d %d %d, penalty %f, %d arcs\n",
1589  trgmInfo->ctrgm.colors[0],
1590  trgmInfo->ctrgm.colors[1],
1591  trgmInfo->ctrgm.colors[2],
1592  trgmInfo->penalty,
1593  list_length(trgmInfo->arcs));
1594 #endif
1595 
1596  /*
1597  * Does any arc of this color trigram connect initial and final
1598  * states? If so we can't remove it.
1599  */
1600  foreach(cell, trgmInfo->arcs)
1601  {
1602  TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell);
1603  TrgmState *source = arcInfo->source,
1604  *target = arcInfo->target;
1605  int source_flags,
1606  target_flags;
1607 
1608 #ifdef TRGM_REGEXP_DEBUG
1609  fprintf(stderr, "examining arc to s%d (%x) from s%d (%x)\n",
1610  -target->snumber, target->flags,
1611  -source->snumber, source->flags);
1612 #endif
1613 
1614  /* examine parent states, if any merging has already happened */
1615  while (source->parent)
1616  source = source->parent;
1617  while (target->parent)
1618  target = target->parent;
1619 
1620 #ifdef TRGM_REGEXP_DEBUG
1621  fprintf(stderr, " ... after completed merges: to s%d (%x) from s%d (%x)\n",
1622  -target->snumber, target->flags,
1623  -source->snumber, source->flags);
1624 #endif
1625 
1626  /* we must also consider merges we are planning right now */
1627  source_flags = source->flags | source->tentFlags;
1628  while (source->tentParent)
1629  {
1630  source = source->tentParent;
1631  source_flags |= source->flags | source->tentFlags;
1632  }
1633  target_flags = target->flags | target->tentFlags;
1634  while (target->tentParent)
1635  {
1636  target = target->tentParent;
1637  target_flags |= target->flags | target->tentFlags;
1638  }
1639 
1640 #ifdef TRGM_REGEXP_DEBUG
1641  fprintf(stderr, " ... after tentative merges: to s%d (%x) from s%d (%x)\n",
1642  -target->snumber, target_flags,
1643  -source->snumber, source_flags);
1644 #endif
1645 
1646  /* would fully-merged state have both INIT and FIN set? */
1647  if (((source_flags | target_flags) & (TSTATE_INIT | TSTATE_FIN)) ==
1648  (TSTATE_INIT | TSTATE_FIN))
1649  {
1650  canRemove = false;
1651  break;
1652  }
1653 
1654  /* ok so far, so remember planned merge */
1655  if (source != target)
1656  {
1657 #ifdef TRGM_REGEXP_DEBUG
1658  fprintf(stderr, " ... tentatively merging s%d into s%d\n",
1659  -target->snumber, -source->snumber);
1660 #endif
1661  target->tentParent = source;
1662  source->tentFlags |= target_flags;
1663  }
1664  }
1665 
1666  /*
1667  * We must reset all the tentFlags/tentParent fields before
1668  * continuing. tentFlags could only have become set in states that
1669  * are the source or parent or tentative parent of one of the current
1670  * arcs; likewise tentParent could only have become set in states that
1671  * are the target or parent or tentative parent of one of the current
1672  * arcs. There might be some overlap between those sets, but if we
1673  * clear tentFlags in target states as well as source states, we
1674  * should be okay even if we visit a state as target before visiting
1675  * it as a source.
1676  */
1677  foreach(cell, trgmInfo->arcs)
1678  {
1679  TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell);
1680  TrgmState *source = arcInfo->source,
1681  *target = arcInfo->target;
1682  TrgmState *ttarget;
1683 
1684  /* no need to touch previously-merged states */
1685  while (source->parent)
1686  source = source->parent;
1687  while (target->parent)
1688  target = target->parent;
1689 
1690  while (source)
1691  {
1692  source->tentFlags = 0;
1693  source = source->tentParent;
1694  }
1695 
1696  while ((ttarget = target->tentParent) != NULL)
1697  {
1698  target->tentParent = NULL;
1699  target->tentFlags = 0; /* in case it was also a source */
1700  target = ttarget;
1701  }
1702  }
1703 
1704  /* Now, move on if we can't drop this trigram */
1705  if (!canRemove)
1706  {
1707 #ifdef TRGM_REGEXP_DEBUG
1708  fprintf(stderr, " ... not ok to merge\n");
1709 #endif
1710  continue;
1711  }
1712 
1713  /* OK, merge states linked by each arc labeled by the trigram */
1714  foreach(cell, trgmInfo->arcs)
1715  {
1716  TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell);
1717  TrgmState *source = arcInfo->source,
1718  *target = arcInfo->target;
1719 
1720  while (source->parent)
1721  source = source->parent;
1722  while (target->parent)
1723  target = target->parent;
1724  if (source != target)
1725  {
1726 #ifdef TRGM_REGEXP_DEBUG
1727  fprintf(stderr, "merging s%d into s%d\n",
1728  -target->snumber, -source->snumber);
1729 #endif
1730  mergeStates(source, target);
1731  /* Assert we didn't merge initial and final states */
1732  Assert((source->flags & (TSTATE_INIT | TSTATE_FIN)) !=
1733  (TSTATE_INIT | TSTATE_FIN));
1734  }
1735  }
1736 
1737  /* Mark trigram unexpanded, and update totals */
1738  trgmInfo->expanded = false;
1739  totalTrgmCount -= trgmInfo->count;
1740  totalTrgmPenalty -= trgmInfo->penalty;
1741  }
1742 
1743  /* Did we succeed in fitting into MAX_TRGM_COUNT? */
1744  if (totalTrgmCount > MAX_TRGM_COUNT)
1745  return false;
1746 
1747  trgmNFA->totalTrgmCount = (int) totalTrgmCount;
1748 
1749  /*
1750  * Sort color trigrams by colors (will be useful for bsearch in packGraph)
1751  * and enumerate the color trigrams that are expanded.
1752  */
1753  cnumber = 0;
1754  qsort(colorTrgms, trgmNFA->colorTrgmsCount, sizeof(ColorTrgmInfo),
1756  for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
1757  {
1758  if (colorTrgms[i].expanded)
1759  {
1760  colorTrgms[i].cnumber = cnumber;
1761  cnumber++;
1762  }
1763  }
1764 
1765  return true;
1766 }
1767 
1768 /*
1769  * Expand selected color trigrams into regular trigrams.
1770  *
1771  * Returns the TRGM array to be passed to the index machinery.
1772  * The array must be allocated in rcontext.
1773  */
1774 static TRGM *
1776 {
1777  TRGM *trg;
1778  trgm *p;
1779  int i;
1780  TrgmColorInfo blankColor;
1781  trgm_mb_char blankChar;
1782 
1783  /* Set up "blank" color structure containing a single zero character */
1784  memset(blankChar.bytes, 0, sizeof(blankChar.bytes));
1785  blankColor.wordCharsCount = 1;
1786  blankColor.wordChars = &blankChar;
1787 
1788  /* Construct the trgm array */
1789  trg = (TRGM *)
1790  MemoryContextAllocZero(rcontext,
1791  TRGMHDRSIZE +
1792  trgmNFA->totalTrgmCount * sizeof(trgm));
1793  trg->flag = ARRKEY;
1794  SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, trgmNFA->totalTrgmCount));
1795  p = GETARR(trg);
1796  for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
1797  {
1798  ColorTrgmInfo *colorTrgm = &trgmNFA->colorTrgms[i];
1799  TrgmColorInfo *c[3];
1800  trgm_mb_char s[3];
1801  int j,
1802  i1,
1803  i2,
1804  i3;
1805 
1806  /* Ignore any unexpanded trigrams ... */
1807  if (!colorTrgm->expanded)
1808  continue;
1809 
1810  /* Get colors, substituting the dummy struct for COLOR_BLANK */
1811  for (j = 0; j < 3; j++)
1812  {
1813  if (colorTrgm->ctrgm.colors[j] != COLOR_BLANK)
1814  c[j] = &trgmNFA->colorInfo[colorTrgm->ctrgm.colors[j]];
1815  else
1816  c[j] = &blankColor;
1817  }
1818 
1819  /* Iterate over all possible combinations of colors' characters */
1820  for (i1 = 0; i1 < c[0]->wordCharsCount; i1++)
1821  {
1822  s[0] = c[0]->wordChars[i1];
1823  for (i2 = 0; i2 < c[1]->wordCharsCount; i2++)
1824  {
1825  s[1] = c[1]->wordChars[i2];
1826  for (i3 = 0; i3 < c[2]->wordCharsCount; i3++)
1827  {
1828  s[2] = c[2]->wordChars[i3];
1829  fillTrgm(p, s);
1830  p++;
1831  }
1832  }
1833  }
1834  }
1835 
1836  return trg;
1837 }
1838 
1839 /*
1840  * Convert trigram into trgm datatype.
1841  */
1842 static void
1844 {
1845  char str[3 * MAX_MULTIBYTE_CHAR_LEN],
1846  *p;
1847  int i,
1848  j;
1849 
1850  /* Write multibyte string into "str" (we don't need null termination) */
1851  p = str;
1852 
1853  for (i = 0; i < 3; i++)
1854  {
1855  if (s[i].bytes[0] != 0)
1856  {
1857  for (j = 0; j < MAX_MULTIBYTE_CHAR_LEN && s[i].bytes[j]; j++)
1858  *p++ = s[i].bytes[j];
1859  }
1860  else
1861  {
1862  /* Emit a space in place of COLOR_BLANK */
1863  *p++ = ' ';
1864  }
1865  }
1866 
1867  /* Convert "str" to a standard trigram (possibly hashing it) */
1868  compact_trigram(ptrgm, str, p - str);
1869 }
1870 
1871 /*
1872  * Merge two states of graph.
1873  */
1874 static void
1876 {
1877  Assert(state1 != state2);
1878  Assert(!state1->parent);
1879  Assert(!state2->parent);
1880 
1881  /* state1 absorbs state2's flags */
1882  state1->flags |= state2->flags;
1883 
1884  /* state2, and indirectly all its children, become children of state1 */
1885  state2->parent = state1;
1886 }
1887 
1888 /*
1889  * Compare function for sorting of color trigrams by their colors.
1890  */
1891 static int
1892 colorTrgmInfoCmp(const void *p1, const void *p2)
1893 {
1894  const ColorTrgmInfo *c1 = (const ColorTrgmInfo *) p1;
1895  const ColorTrgmInfo *c2 = (const ColorTrgmInfo *) p2;
1896 
1897  return memcmp(&c1->ctrgm, &c2->ctrgm, sizeof(ColorTrgm));
1898 }
1899 
1900 /*
1901  * Compare function for sorting color trigrams in descending order of
1902  * their penalty fields.
1903  */
1904 static int
1905 colorTrgmInfoPenaltyCmp(const void *p1, const void *p2)
1906 {
1907  float4 penalty1 = ((const ColorTrgmInfo *) p1)->penalty;
1908  float4 penalty2 = ((const ColorTrgmInfo *) p2)->penalty;
1909 
1910  if (penalty1 < penalty2)
1911  return 1;
1912  else if (penalty1 == penalty2)
1913  return 0;
1914  else
1915  return -1;
1916 }
1917 
1918 
1919 /*---------------------
1920  * Subroutines for packing the graph into final representation (stage 4).
1921  *---------------------
1922  */
1923 
1924 /*
1925  * Pack expanded graph into final representation.
1926  *
1927  * The result data must be allocated in rcontext.
1928  */
1929 static TrgmPackedGraph *
1930 packGraph(TrgmNFA *trgmNFA, MemoryContext rcontext)
1931 {
1932  int snumber = 2,
1933  arcIndex,
1934  arcsCount;
1935  HASH_SEQ_STATUS scan_status;
1936  TrgmState *state;
1937  TrgmPackArcInfo *arcs;
1938  TrgmPackedArc *packedArcs;
1939  TrgmPackedGraph *result;
1940  int i,
1941  j;
1942 
1943  /* Enumerate surviving states, giving init and fin reserved numbers */
1944  hash_seq_init(&scan_status, trgmNFA->states);
1945  while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
1946  {
1947  while (state->parent)
1948  state = state->parent;
1949 
1950  if (state->snumber < 0)
1951  {
1952  if (state->flags & TSTATE_INIT)
1953  state->snumber = 0;
1954  else if (state->flags & TSTATE_FIN)
1955  state->snumber = 1;
1956  else
1957  {
1958  state->snumber = snumber;
1959  snumber++;
1960  }
1961  }
1962  }
1963 
1964  /* Collect array of all arcs */
1965  arcs = (TrgmPackArcInfo *)
1966  palloc(sizeof(TrgmPackArcInfo) * trgmNFA->arcsCount);
1967  arcIndex = 0;
1968  hash_seq_init(&scan_status, trgmNFA->states);
1969  while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
1970  {
1971  TrgmState *source = state;
1972  ListCell *cell;
1973 
1974  while (source->parent)
1975  source = source->parent;
1976 
1977  foreach(cell, state->arcs)
1978  {
1979  TrgmArc *arc = (TrgmArc *) lfirst(cell);
1980  TrgmState *target = arc->target;
1981 
1982  while (target->parent)
1983  target = target->parent;
1984 
1985  if (source->snumber != target->snumber)
1986  {
1987  ColorTrgmInfo *ctrgm;
1988 
1989  ctrgm = (ColorTrgmInfo *) bsearch(&arc->ctrgm,
1990  trgmNFA->colorTrgms,
1991  trgmNFA->colorTrgmsCount,
1992  sizeof(ColorTrgmInfo),
1994  Assert(ctrgm != NULL);
1995  Assert(ctrgm->expanded);
1996 
1997  arcs[arcIndex].sourceState = source->snumber;
1998  arcs[arcIndex].targetState = target->snumber;
1999  arcs[arcIndex].colorTrgm = ctrgm->cnumber;
2000  arcIndex++;
2001  }
2002  }
2003  }
2004 
2005  /* Sort arcs to ease duplicate detection */
2006  qsort(arcs, arcIndex, sizeof(TrgmPackArcInfo), packArcInfoCmp);
2007 
2008  /* We could have duplicates because states were merged. Remove them. */
2009  if (arcIndex > 1)
2010  {
2011  /* p1 is probe point, p2 is last known non-duplicate. */
2012  TrgmPackArcInfo *p1,
2013  *p2;
2014 
2015  p2 = arcs;
2016  for (p1 = arcs + 1; p1 < arcs + arcIndex; p1++)
2017  {
2018  if (packArcInfoCmp(p1, p2) > 0)
2019  {
2020  p2++;
2021  *p2 = *p1;
2022  }
2023  }
2024  arcsCount = (p2 - arcs) + 1;
2025  }
2026  else
2027  arcsCount = arcIndex;
2028 
2029  /* Create packed representation */
2030  result = (TrgmPackedGraph *)
2031  MemoryContextAlloc(rcontext, sizeof(TrgmPackedGraph));
2032 
2033  /* Pack color trigrams information */
2034  result->colorTrigramsCount = 0;
2035  for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
2036  {
2037  if (trgmNFA->colorTrgms[i].expanded)
2038  result->colorTrigramsCount++;
2039  }
2040  result->colorTrigramGroups = (int *)
2041  MemoryContextAlloc(rcontext, sizeof(int) * result->colorTrigramsCount);
2042  j = 0;
2043  for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
2044  {
2045  if (trgmNFA->colorTrgms[i].expanded)
2046  {
2047  result->colorTrigramGroups[j] = trgmNFA->colorTrgms[i].count;
2048  j++;
2049  }
2050  }
2051 
2052  /* Pack states and arcs information */
2053  result->statesCount = snumber;
2054  result->states = (TrgmPackedState *)
2055  MemoryContextAlloc(rcontext, snumber * sizeof(TrgmPackedState));
2056  packedArcs = (TrgmPackedArc *)
2057  MemoryContextAlloc(rcontext, arcsCount * sizeof(TrgmPackedArc));
2058  j = 0;
2059  for (i = 0; i < snumber; i++)
2060  {
2061  int cnt = 0;
2062 
2063  result->states[i].arcs = &packedArcs[j];
2064  while (j < arcsCount && arcs[j].sourceState == i)
2065  {
2066  packedArcs[j].targetState = arcs[j].targetState;
2067  packedArcs[j].colorTrgm = arcs[j].colorTrgm;
2068  cnt++;
2069  j++;
2070  }
2071  result->states[i].arcsCount = cnt;
2072  }
2073 
2074  /* Allocate working memory for trigramsMatchGraph() */
2075  result->colorTrigramsActive = (bool *)
2076  MemoryContextAlloc(rcontext, sizeof(bool) * result->colorTrigramsCount);
2077  result->statesActive = (bool *)
2078  MemoryContextAlloc(rcontext, sizeof(bool) * result->statesCount);
2079  result->statesQueue = (int *)
2080  MemoryContextAlloc(rcontext, sizeof(int) * result->statesCount);
2081 
2082  return result;
2083 }
2084 
2085 /*
2086  * Comparison function for sorting TrgmPackArcInfos.
2087  *
2088  * Compares arcs in following order: sourceState, colorTrgm, targetState.
2089  */
2090 static int
2091 packArcInfoCmp(const void *a1, const void *a2)
2092 {
2093  const TrgmPackArcInfo *p1 = (const TrgmPackArcInfo *) a1;
2094  const TrgmPackArcInfo *p2 = (const TrgmPackArcInfo *) a2;
2095 
2096  if (p1->sourceState < p2->sourceState)
2097  return -1;
2098  if (p1->sourceState > p2->sourceState)
2099  return 1;
2100  if (p1->colorTrgm < p2->colorTrgm)
2101  return -1;
2102  if (p1->colorTrgm > p2->colorTrgm)
2103  return 1;
2104  if (p1->targetState < p2->targetState)
2105  return -1;
2106  if (p1->targetState > p2->targetState)
2107  return 1;
2108  return 0;
2109 }
2110 
2111 
2112 /*---------------------
2113  * Debugging functions
2114  *
2115  * These are designed to emit GraphViz files.
2116  *---------------------
2117  */
2118 
2119 #ifdef TRGM_REGEXP_DEBUG
2120 
2121 /*
2122  * Print initial NFA, in regexp library's representation
2123  */
2124 static void
2125 printSourceNFA(regex_t *regex, TrgmColorInfo *colors, int ncolors)
2126 {
2128  int nstates = pg_reg_getnumstates(regex);
2129  int state;
2130  int i;
2131 
2132  initStringInfo(&buf);
2133 
2134  appendStringInfoString(&buf, "\ndigraph sourceNFA {\n");
2135 
2136  for (state = 0; state < nstates; state++)
2137  {
2138  regex_arc_t *arcs;
2139  int i,
2140  arcsCount;
2141 
2142  appendStringInfo(&buf, "s%d", state);
2143  if (pg_reg_getfinalstate(regex) == state)
2144  appendStringInfoString(&buf, " [shape = doublecircle]");
2145  appendStringInfoString(&buf, ";\n");
2146 
2147  arcsCount = pg_reg_getnumoutarcs(regex, state);
2148  arcs = (regex_arc_t *) palloc(sizeof(regex_arc_t) * arcsCount);
2149  pg_reg_getoutarcs(regex, state, arcs, arcsCount);
2150 
2151  for (i = 0; i < arcsCount; i++)
2152  {
2153  appendStringInfo(&buf, " s%d -> s%d [label = \"%d\"];\n",
2154  state, arcs[i].to, arcs[i].co);
2155  }
2156 
2157  pfree(arcs);
2158  }
2159 
2160  appendStringInfoString(&buf, " node [shape = point ]; initial;\n");
2161  appendStringInfo(&buf, " initial -> s%d;\n",
2162  pg_reg_getinitialstate(regex));
2163 
2164  /* Print colors */
2165  appendStringInfoString(&buf, " { rank = sink;\n");
2166  appendStringInfoString(&buf, " Colors [shape = none, margin=0, label=<\n");
2167 
2168  for (i = 0; i < ncolors; i++)
2169  {
2170  TrgmColorInfo *color = &colors[i];
2171  int j;
2172 
2173  appendStringInfo(&buf, "<br/>Color %d: ", i);
2174  if (color->expandable)
2175  {
2176  for (j = 0; j < color->wordCharsCount; j++)
2177  {
2178  char s[MAX_MULTIBYTE_CHAR_LEN + 1];
2179 
2180  memcpy(s, color->wordChars[j].bytes, MAX_MULTIBYTE_CHAR_LEN);
2181  s[MAX_MULTIBYTE_CHAR_LEN] = '\0';
2183  }
2184  }
2185  else
2186  appendStringInfoString(&buf, "not expandable");
2187  appendStringInfoChar(&buf, '\n');
2188  }
2189 
2190  appendStringInfoString(&buf, " >];\n");
2191  appendStringInfoString(&buf, " }\n");
2192  appendStringInfoString(&buf, "}\n");
2193 
2194  {
2195  /* dot -Tpng -o /tmp/source.png < /tmp/source.gv */
2196  FILE *fp = fopen("/tmp/source.gv", "w");
2197 
2198  fprintf(fp, "%s", buf.data);
2199  fclose(fp);
2200  }
2201 
2202  pfree(buf.data);
2203 }
2204 
2205 /*
2206  * Print expanded graph.
2207  */
2208 static void
2209 printTrgmNFA(TrgmNFA *trgmNFA)
2210 {
2212  HASH_SEQ_STATUS scan_status;
2213  TrgmState *state;
2214  TrgmState *initstate = NULL;
2215 
2216  initStringInfo(&buf);
2217 
2218  appendStringInfoString(&buf, "\ndigraph transformedNFA {\n");
2219 
2220  hash_seq_init(&scan_status, trgmNFA->states);
2221  while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
2222  {
2223  ListCell *cell;
2224 
2225  appendStringInfo(&buf, "s%d", -state->snumber);
2226  if (state->flags & TSTATE_FIN)
2227  appendStringInfoString(&buf, " [shape = doublecircle]");
2228  if (state->flags & TSTATE_INIT)
2229  initstate = state;
2230  appendStringInfo(&buf, " [label = \"%d\"]", state->stateKey.nstate);
2231  appendStringInfoString(&buf, ";\n");
2232 
2233  foreach(cell, state->arcs)
2234  {
2235  TrgmArc *arc = (TrgmArc *) lfirst(cell);
2236 
2237  appendStringInfo(&buf, " s%d -> s%d [label = \"",
2238  -state->snumber, -arc->target->snumber);
2239  printTrgmColor(&buf, arc->ctrgm.colors[0]);
2240  appendStringInfoChar(&buf, ' ');
2241  printTrgmColor(&buf, arc->ctrgm.colors[1]);
2242  appendStringInfoChar(&buf, ' ');
2243  printTrgmColor(&buf, arc->ctrgm.colors[2]);
2244  appendStringInfoString(&buf, "\"];\n");
2245  }
2246  }
2247 
2248  if (initstate)
2249  {
2250  appendStringInfoString(&buf, " node [shape = point ]; initial;\n");
2251  appendStringInfo(&buf, " initial -> s%d;\n", -initstate->snumber);
2252  }
2253 
2254  appendStringInfoString(&buf, "}\n");
2255 
2256  {
2257  /* dot -Tpng -o /tmp/transformed.png < /tmp/transformed.gv */
2258  FILE *fp = fopen("/tmp/transformed.gv", "w");
2259 
2260  fprintf(fp, "%s", buf.data);
2261  fclose(fp);
2262  }
2263 
2264  pfree(buf.data);
2265 }
2266 
2267 /*
2268  * Print a TrgmColor readably.
2269  */
2270 static void
2271 printTrgmColor(StringInfo buf, TrgmColor co)
2272 {
2273  if (co == COLOR_UNKNOWN)
2274  appendStringInfoChar(buf, 'u');
2275  else if (co == COLOR_BLANK)
2276  appendStringInfoChar(buf, 'b');
2277  else
2278  appendStringInfo(buf, "%d", (int) co);
2279 }
2280 
2281 /*
2282  * Print final packed representation of trigram-based expanded graph.
2283  */
2284 static void
2285 printTrgmPackedGraph(TrgmPackedGraph *packedGraph, TRGM *trigrams)
2286 {
2288  trgm *p;
2289  int i;
2290 
2291  initStringInfo(&buf);
2292 
2293  appendStringInfoString(&buf, "\ndigraph packedGraph {\n");
2294 
2295  for (i = 0; i < packedGraph->statesCount; i++)
2296  {
2297  TrgmPackedState *state = &packedGraph->states[i];
2298  int j;
2299 
2300  appendStringInfo(&buf, " s%d", i);
2301  if (i == 1)
2302  appendStringInfoString(&buf, " [shape = doublecircle]");
2303 
2304  appendStringInfo(&buf, " [label = <s%d>];\n", i);
2305 
2306  for (j = 0; j < state->arcsCount; j++)
2307  {
2308  TrgmPackedArc *arc = &state->arcs[j];
2309 
2310  appendStringInfo(&buf, " s%d -> s%d [label = \"trigram %d\"];\n",
2311  i, arc->targetState, arc->colorTrgm);
2312  }
2313  }
2314 
2315  appendStringInfoString(&buf, " node [shape = point ]; initial;\n");
2316  appendStringInfo(&buf, " initial -> s%d;\n", 0);
2317 
2318  /* Print trigrams */
2319  appendStringInfoString(&buf, " { rank = sink;\n");
2320  appendStringInfoString(&buf, " Trigrams [shape = none, margin=0, label=<\n");
2321 
2322  p = GETARR(trigrams);
2323  for (i = 0; i < packedGraph->colorTrigramsCount; i++)
2324  {
2325  int count = packedGraph->colorTrigramGroups[i];
2326  int j;
2327 
2328  appendStringInfo(&buf, "<br/>Trigram %d: ", i);
2329 
2330  for (j = 0; j < count; j++)
2331  {
2332  if (j > 0)
2333  appendStringInfoString(&buf, ", ");
2334 
2335  /*
2336  * XXX This representation is nice only for all-ASCII trigrams.
2337  */
2338  appendStringInfo(&buf, "\"%c%c%c\"", (*p)[0], (*p)[1], (*p)[2]);
2339  p++;
2340  }
2341  }
2342 
2343  appendStringInfoString(&buf, " >];\n");
2344  appendStringInfoString(&buf, " }\n");
2345  appendStringInfoString(&buf, "}\n");
2346 
2347  {
2348  /* dot -Tpng -o /tmp/packed.png < /tmp/packed.gv */
2349  FILE *fp = fopen("/tmp/packed.gv", "w");
2350 
2351  fprintf(fp, "%s", buf.data);
2352  fclose(fp);
2353  }
2354 
2355  pfree(buf.data);
2356 }
2357 
2358 #endif /* TRGM_REGEXP_DEBUG */
float float4
Definition: c.h:616
#define MemSet(start, val, len)
Definition: c.h:1007
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:955
HTAB * hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
Definition: dynahash.c:352
long hash_get_num_entries(HTAB *hashp)
Definition: dynahash.c:1341
void * hash_seq_search(HASH_SEQ_STATUS *status)
Definition: dynahash.c:1395
void hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)
Definition: dynahash.c:1385
int errcode(int sqlerrcode)
Definition: elog.c:859
int errmsg(const char *fmt,...)
Definition: elog.c:1072
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
static const FormData_pg_attribute a1
Definition: heap.c:142
static const FormData_pg_attribute a2
Definition: heap.c:156
@ HASH_ENTER
Definition: hsearch.h:114
#define HASH_CONTEXT
Definition: hsearch.h:102
#define HASH_ELEM
Definition: hsearch.h:95
#define HASH_BLOBS
Definition: hsearch.h:97
#define CALCGTSIZE(flag, siglen)
Definition: hstore_gist.c:60
int j
Definition: isn.c:74
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
List * lappend(List *list, void *datum)
Definition: list.c:339
void list_free(List *list)
Definition: list.c:1546
List * list_concat(List *list1, const List *list2)
Definition: list.c:561
unsigned int pg_wchar
Definition: mbprint.c:31
int pg_wchar2mb_with_len(const pg_wchar *from, char *to, int len)
Definition: mbutils.c:1008
int pg_mb2wchar_with_len(const char *from, pg_wchar *to, int len)
Definition: mbutils.c:986
void pfree(void *pointer)
Definition: mcxt.c:1508
void * palloc0(Size size)
Definition: mcxt.c:1334
void * MemoryContextAllocZero(MemoryContext context, Size size)
Definition: mcxt.c:1202
MemoryContext CurrentMemoryContext
Definition: mcxt.c:131
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1168
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:442
void * palloc(Size size)
Definition: mcxt.c:1304
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_DEFAULT_SIZES
Definition: memutils.h:153
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
#define lfirst(lc)
Definition: pg_list.h:172
static int list_length(const List *l)
Definition: pg_list.h:152
#define NIL
Definition: pg_list.h:68
#define foreach_delete_current(lst, var_or_cell)
Definition: pg_list.h:391
#define list_make1(x1)
Definition: pg_list.h:212
static rewind_source * source
Definition: pg_rewind.c:89
static char * buf
Definition: pg_test_fsync.c:73
#define MAX_MULTIBYTE_CHAR_LEN
Definition: pg_wchar.h:33
#define fprintf
Definition: port.h:242
#define qsort(a, b, c, d)
Definition: port.h:449
unsigned int Oid
Definition: postgres_ext.h:31
char * c
int pg_regcomp(regex_t *re, const chr *string, size_t len, int flags, Oid collation)
Definition: regcomp.c:370
size_t pg_regerror(int errcode, const regex_t *preg, char *errbuf, size_t errbuf_size)
Definition: regerror.c:60
#define REG_ICASE
Definition: regex.h:106
#define REG_ADVANCED
Definition: regex.h:103
#define REG_OKAY
Definition: regex.h:137
#define REG_NOSUB
Definition: regex.h:107
int pg_reg_getnumoutarcs(const regex_t *regex, int st)
Definition: regexport.c:134
int pg_reg_getnumcolors(const regex_t *regex)
Definition: regexport.c:174
int pg_reg_getnumstates(const regex_t *regex)
Definition: regexport.c:36
int pg_reg_getfinalstate(const regex_t *regex)
Definition: regexport.c:64
int pg_reg_getinitialstate(const regex_t *regex)
Definition: regexport.c:50
void pg_reg_getoutarcs(const regex_t *regex, int st, regex_arc_t *arcs, int arcs_len)
Definition: regexport.c:155
int pg_reg_colorisend(const regex_t *regex, int co)
Definition: regexport.c:208
void pg_reg_getcharacters(const regex_t *regex, int co, pg_wchar *chars, int chars_len)
Definition: regexport.c:266
int pg_reg_getnumcharacters(const regex_t *regex, int co)
Definition: regexport.c:230
int pg_reg_colorisbegin(const regex_t *regex, int co)
Definition: regexport.c:191
short color
Definition: regguts.h:155
void appendStringInfo(StringInfo str, const char *fmt,...)
Definition: stringinfo.c:97
void appendStringInfoString(StringInfo str, const char *s)
Definition: stringinfo.c:182
void appendStringInfoChar(StringInfo str, char ch)
Definition: stringinfo.c:194
void initStringInfo(StringInfo str)
Definition: stringinfo.c:59
ColorTrgm ctrgm
Definition: trgm_regexp.c:375
float4 penalty
Definition: trgm_regexp.c:378
TrgmColor colors[3]
Definition: trgm_regexp.c:300
Size keysize
Definition: hsearch.h:75
Size entrysize
Definition: hsearch.h:76
MemoryContext hcxt
Definition: hsearch.h:86
Definition: dynahash.c:220
Definition: pg_list.h:54
Definition: trgm.h:67
uint8 flag
Definition: trgm.h:69
TrgmState * source
Definition: trgm_regexp.c:360
TrgmState * target
Definition: trgm_regexp.c:361
ColorTrgm ctrgm
Definition: trgm_regexp.c:349
TrgmState * target
Definition: trgm_regexp.c:350
trgm_mb_char * wordChars
Definition: trgm_regexp.c:264
bool containsNonWord
Definition: trgm_regexp.c:262
bool overflowed
Definition: trgm_regexp.c:416
int nstates
Definition: trgm_regexp.c:410
int arcsCount
Definition: trgm_regexp.c:415
ColorTrgmInfo * colorTrgms
Definition: trgm_regexp.c:419
List * queue
Definition: trgm_regexp.c:413
int colorTrgmsCount
Definition: trgm_regexp.c:420
TrgmColorInfo * colorInfo
Definition: trgm_regexp.c:404
int totalTrgmCount
Definition: trgm_regexp.c:421
List * keysQueue
Definition: trgm_regexp.c:414
int ncolors
Definition: trgm_regexp.c:405
TrgmState * initState
Definition: trgm_regexp.c:409
regex_t * regex
Definition: trgm_regexp.c:403
HTAB * states
Definition: trgm_regexp.c:408
TrgmPackedState * states
Definition: trgm_regexp.c:459
bool * statesActive
Definition: trgm_regexp.c:463
bool * colorTrigramsActive
Definition: trgm_regexp.c:462
int * colorTrigramGroups
Definition: trgm_regexp.c:452
TrgmPackedArc * arcs
Definition: trgm_regexp.c:436
TrgmColor colors[2]
Definition: trgm_regexp.c:291
TrgmPrefix prefix
Definition: trgm_regexp.c:310
List * arcs
Definition: trgm_regexp.c:335
List * enterKeys
Definition: trgm_regexp.c:336
struct TrgmState * parent
Definition: trgm_regexp.c:339
TrgmStateKey stateKey
Definition: trgm_regexp.c:334
int tentFlags
Definition: trgm_regexp.c:340
struct TrgmState * tentParent
Definition: trgm_regexp.c:341
Definition: regguts.h:296
color co
Definition: regguts.h:298
struct state * to
Definition: regguts.h:300
Definition: regex.h:56
Definition: regguts.h:323
char bytes[MAX_MULTIBYTE_CHAR_LEN]
Definition: trgm_regexp.c:243
Definition: c.h:674
#define ISWORDCHR(c)
Definition: trgm.h:55
void compact_trigram(trgm *tptr, char *str, int bytelen)
Definition: trgm_op.c:199
char trgm[3]
Definition: trgm.h:42
#define GETARR(x)
Definition: trgm.h:106
#define ARRKEY
Definition: trgm.h:96
#define TRGMHDRSIZE
Definition: trgm.h:73
int TrgmColor
Definition: trgm_regexp.c:283
static bool convertPgWchar(pg_wchar c, trgm_mb_char *result)
Definition: trgm_regexp.c:827
static bool validArcLabel(TrgmStateKey *key, TrgmColor co)
Definition: trgm_regexp.c:1328
static TrgmState * getState(TrgmNFA *trgmNFA, TrgmStateKey *key)
Definition: trgm_regexp.c:1383
static void getColorInfo(regex_t *regex, TrgmNFA *trgmNFA)
Definition: trgm_regexp.c:763
#define COLOR_BLANK
Definition: trgm_regexp.c:287
static TRGM * createTrgmNFAInternal(regex_t *regex, TrgmPackedGraph **graph, MemoryContext rcontext)
Definition: trgm_regexp.c:565
#define TSTATE_INIT
Definition: trgm_regexp.c:329
static void addArc(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key, TrgmColor co, TrgmStateKey *destKey)
Definition: trgm_regexp.c:1286
#define MAX_EXPANDED_STATES
Definition: trgm_regexp.c:219
static int colorTrgmInfoPenaltyCmp(const void *p1, const void *p2)
Definition: trgm_regexp.c:1905
#define MAX_TRGM_COUNT
Definition: trgm_regexp.c:221
#define MAX_EXPANDED_ARCS
Definition: trgm_regexp.c:220
struct TrgmState TrgmState
static bool selectColorTrigrams(TrgmNFA *trgmNFA)
Definition: trgm_regexp.c:1456
static void fillTrgm(trgm *ptrgm, trgm_mb_char s[3])
Definition: trgm_regexp.c:1843
static TRGM * expandColorTrigrams(TrgmNFA *trgmNFA, MemoryContext rcontext)
Definition: trgm_regexp.c:1775
static void transformGraph(TrgmNFA *trgmNFA)
Definition: trgm_regexp.c:893
bool trigramsMatchGraph(TrgmPackedGraph *graph, bool *check)
Definition: trgm_regexp.c:626
static const float4 penalties[8]
Definition: trgm_regexp.c:229
static void addKeyToQueue(TrgmNFA *trgmNFA, TrgmStateKey *key)
Definition: trgm_regexp.c:1176
static void addKey(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key)
Definition: trgm_regexp.c:1007
static TrgmPackedGraph * packGraph(TrgmNFA *trgmNFA, MemoryContext rcontext)
Definition: trgm_regexp.c:1930
static int packArcInfoCmp(const void *a1, const void *a2)
Definition: trgm_regexp.c:2091
static void processState(TrgmNFA *trgmNFA, TrgmState *state)
Definition: trgm_regexp.c:957
TRGM * createTrgmNFA(text *text_re, Oid collation, TrgmPackedGraph **graph, MemoryContext rcontext)
Definition: trgm_regexp.c:522
#define COLOR_COUNT_LIMIT
Definition: trgm_regexp.c:223
#define TSTATE_FIN
Definition: trgm_regexp.c:330
#define WISH_TRGM_PENALTY
Definition: trgm_regexp.c:222
static void mergeStates(TrgmState *state1, TrgmState *state2)
Definition: trgm_regexp.c:1875
#define COLOR_UNKNOWN
Definition: trgm_regexp.c:286
static int colorTrgmInfoCmp(const void *p1, const void *p2)
Definition: trgm_regexp.c:1892
static void RE_compile(regex_t *regex, text *text_re, int cflags, Oid collation)
Definition: trgm_regexp.c:719
static void addArcs(TrgmNFA *trgmNFA, TrgmState *state)
Definition: trgm_regexp.c:1188
static bool prefixContains(TrgmPrefix *prefix1, TrgmPrefix *prefix2)
Definition: trgm_regexp.c:1414
char * lowerstr(const char *str)
Definition: ts_locale.c:253
#define VARDATA_ANY(PTR)
Definition: varatt.h:324
#define SET_VARSIZE(PTR, len)
Definition: varatt.h:305
#define VARSIZE_ANY_EXHDR(PTR)
Definition: varatt.h:317
static char chars[TZ_MAX_CHARS]
Definition: zic.c:401