Age Owner TLA Line data Source code
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-2023, 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 : {
243 : char bytes[MAX_MULTIBYTE_CHAR_LEN];
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 : {
261 : bool expandable;
262 : bool containsNonWord;
263 : int wordCharsCount;
264 : trgm_mb_char *wordChars;
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 : {
310 : TrgmPrefix prefix;
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 */
335 : List *arcs;
336 : List *enterKeys;
337 : int flags;
338 : int snumber;
339 : struct TrgmState *parent;
340 : int tentFlags;
341 : struct TrgmState *tentParent;
342 : } TrgmState;
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 : {
360 : TrgmState *source;
361 : TrgmState *target;
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 : {
375 : ColorTrgm ctrgm;
376 : int cnumber;
377 : int count;
378 : float4 penalty;
379 : bool expanded;
380 : List *arcs;
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) */
403 : regex_t *regex;
404 : TrgmColorInfo *colorInfo;
405 : int ncolors;
406 :
407 : /* Expanded graph (stage 2) */
408 : HTAB *states;
409 : TrgmState *initState;
410 : int nstates;
411 :
412 : /* Workspace for stage 2 */
413 : List *queue;
414 : List *keysQueue;
415 : int arcsCount;
416 : bool overflowed;
417 :
418 : /* Information about distinct color trigrams in the graph (stage 3) */
419 : ColorTrgmInfo *colorTrgms;
420 : int colorTrgmsCount;
421 : int totalTrgmCount;
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 */
437 : } TrgmPackedState;
438 :
439 : /* "typedef struct TrgmPackedGraph TrgmPackedGraph" appears in trgm.h */
440 : struct TrgmPackedGraph
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 : */
451 : int colorTrigramsCount;
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 : */
458 : int statesCount;
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 : {
472 : int sourceState;
473 : int targetState;
474 : int colorTrgm;
475 : } TrgmPackArcInfo;
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 *
3651 tgl 522 GIC 65 : createTrgmNFA(text *text_re, Oid collation,
3651 tgl 523 ECB : 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 : */
3652 tgl 536 GIC 65 : tmpcontext = AllocSetContextCreate(CurrentMemoryContext,
3652 tgl 537 ECB : "createTrgmNFA temporary context",
538 : ALLOCSET_DEFAULT_SIZES);
3652 tgl 539 GIC 65 : oldcontext = MemoryContextSwitchTo(tmpcontext);
3652 tgl 540 ECB :
541 : /*
542 : * Stage 1: Compile the regexp into a NFA, using the regexp library.
543 : */
544 : #ifdef IGNORECASE
608 tgl 545 GIC 65 : RE_compile(®ex, text_re,
608 tgl 546 ECB : REG_ADVANCED | REG_NOSUB | REG_ICASE, collation);
547 : #else
548 : RE_compile(®ex, text_re,
549 : REG_ADVANCED | REG_NOSUB, collation);
550 : #endif
551 :
1 tmunro 552 GNC 65 : trg = createTrgmNFAInternal(®ex, graph, rcontext);
1 tmunro 553 ECB :
554 : /* Clean up all the cruft we created (including regex) */
3652 tgl 555 GIC 65 : MemoryContextSwitchTo(oldcontext);
556 65 : MemoryContextDelete(tmpcontext);
557 :
558 65 : return trg;
3652 tgl 559 ECB : }
560 :
561 : /*
562 : * Body of createTrgmNFA, exclusive of regex compilation/freeing.
563 : */
564 : static TRGM *
3652 tgl 565 GIC 65 : createTrgmNFAInternal(regex_t *regex, TrgmPackedGraph **graph,
566 : MemoryContext rcontext)
567 : {
568 : TRGM *trg;
569 : TrgmNFA trgmNFA;
570 :
3652 tgl 571 CBC 65 : trgmNFA.regex = regex;
572 :
573 : /* Collect color information from the regex */
3652 tgl 574 GIC 65 : 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.
3652 tgl 582 ECB : */
3652 tgl 583 CBC 65 : transformGraph(&trgmNFA);
584 :
585 : #ifdef TRGM_REGEXP_DEBUG
586 : printTrgmNFA(&trgmNFA);
587 : #endif
3652 tgl 588 ECB :
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 : */
2237 tgl 594 GIC 65 : if (trgmNFA.initState->flags & TSTATE_FIN)
3652 tgl 595 CBC 9 : return NULL;
596 :
3652 tgl 597 ECB : /*
598 : * Stage 3: Select color trigrams to expand. Fail if too many trigrams.
599 : */
3652 tgl 600 GIC 56 : if (!selectColorTrigrams(&trgmNFA))
601 3 : return NULL;
602 :
3652 tgl 603 ECB : /*
604 : * Stage 4: Expand color trigrams and pack graph into final
605 : * representation.
606 : */
3652 tgl 607 GIC 53 : trg = expandColorTrigrams(&trgmNFA, rcontext);
608 :
609 53 : *graph = packGraph(&trgmNFA, rcontext);
610 :
611 : #ifdef TRGM_REGEXP_DEBUG
612 : printTrgmPackedGraph(*graph, trg);
613 : #endif
3652 tgl 614 ECB :
3652 tgl 615 GIC 53 : 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 : */
3652 tgl 625 ECB : bool
3652 tgl 626 CBC 3556 : trigramsMatchGraph(TrgmPackedGraph *graph, bool *check)
3652 tgl 627 ECB : {
628 : int i,
629 : j,
630 : k,
631 : queueIn,
632 : queueOut;
633 :
634 : /*
635 : * Reset temporary working areas.
636 : */
3652 tgl 637 CBC 3556 : memset(graph->colorTrigramsActive, 0,
3652 tgl 638 GIC 3556 : sizeof(bool) * graph->colorTrigramsCount);
3652 tgl 639 CBC 3556 : memset(graph->statesActive, 0, sizeof(bool) * graph->statesCount);
640 :
3652 tgl 641 ECB : /*
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 : */
3652 tgl 646 GIC 3556 : j = 0;
3652 tgl 647 CBC 11036 : for (i = 0; i < graph->colorTrigramsCount; i++)
3652 tgl 648 ECB : {
3652 tgl 649 GIC 7480 : int cnt = graph->colorTrigramGroups[i];
650 :
3652 tgl 651 CBC 166727 : for (k = j; k < j + cnt; k++)
652 : {
3652 tgl 653 GIC 163097 : 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 3850 : graph->colorTrigramsActive[i] = true;
3652 tgl 660 CBC 3850 : break;
3652 tgl 661 ECB : }
662 : }
3652 tgl 663 CBC 7480 : j = j + cnt;
664 : }
665 :
3652 tgl 666 ECB : /*
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 : */
3652 tgl 672 GIC 3556 : graph->statesActive[0] = true;
3652 tgl 673 CBC 3556 : graph->statesQueue[0] = 0;
3652 tgl 674 GIC 3556 : queueIn = 0;
3652 tgl 675 CBC 3556 : queueOut = 1;
676 :
677 : /* Process queued states as long as there are any. */
3652 tgl 678 GIC 7656 : while (queueIn < queueOut)
679 : {
680 7520 : int stateno = graph->statesQueue[queueIn++];
681 7520 : TrgmPackedState *state = &graph->states[stateno];
3652 tgl 682 CBC 7520 : int cnt = state->arcsCount;
683 :
3652 tgl 684 ECB : /* Loop over state's out-arcs */
3652 tgl 685 GIC 15154 : for (i = 0; i < cnt; i++)
3652 tgl 686 ECB : {
3652 tgl 687 CBC 11054 : TrgmPackedArc *arc = &state->arcs[i];
688 :
3652 tgl 689 ECB : /*
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 : */
3652 tgl 694 GIC 11054 : if (graph->colorTrigramsActive[arc->colorTrgm])
695 : {
696 7722 : int nextstate = arc->targetState;
697 :
698 7722 : if (nextstate == 1)
3652 tgl 699 CBC 3420 : return true; /* success: final state is reachable */
700 :
3652 tgl 701 GIC 4302 : if (!graph->statesActive[nextstate])
702 : {
703 4245 : graph->statesActive[nextstate] = true;
704 4245 : graph->statesQueue[queueOut++] = nextstate;
705 : }
706 : }
3652 tgl 707 ECB : }
708 : }
709 :
710 : /* Queue is empty, so match fails. */
3652 tgl 711 GIC 136 : 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.
3652 tgl 717 ECB : */
718 : static void
3652 tgl 719 GIC 65 : RE_compile(regex_t *regex, text *text_re, int cflags, Oid collation)
720 : {
721 65 : int text_re_len = VARSIZE_ANY_EXHDR(text_re);
722 65 : char *text_re_val = VARDATA_ANY(text_re);
3652 tgl 723 ECB : pg_wchar *pattern;
724 : int pattern_len;
725 : int regcomp_result;
726 : char errMsg[100];
727 :
728 : /* Convert pattern string to wide characters */
3652 tgl 729 CBC 65 : pattern = (pg_wchar *) palloc((text_re_len + 1) * sizeof(pg_wchar));
3652 tgl 730 GIC 65 : pattern_len = pg_mb2wchar_with_len(text_re_val,
3652 tgl 731 ECB : pattern,
732 : text_re_len);
733 :
3652 tgl 734 EUB : /* Compile regex */
3652 tgl 735 GBC 65 : regcomp_result = pg_regcomp(regex,
736 : pattern,
737 : pattern_len,
738 : cflags,
3652 tgl 739 ECB : collation);
740 :
3652 tgl 741 GIC 65 : pfree(pattern);
742 :
743 65 : if (regcomp_result != REG_OKAY)
744 : {
745 : /* re didn't compile (no need for pg_regfree, if so) */
3652 tgl 746 UIC 0 : pg_regerror(regcomp_result, regex, errMsg, sizeof(errMsg));
747 0 : ereport(ERROR,
748 : (errcode(ERRCODE_INVALID_REGULAR_EXPRESSION),
749 : errmsg("invalid regular expression: %s", errMsg)));
750 : }
3652 tgl 751 CBC 65 : }
752 :
3652 tgl 753 ECB :
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
3652 tgl 763 GIC 65 : getColorInfo(regex_t *regex, TrgmNFA *trgmNFA)
3652 tgl 764 ECB : {
3652 tgl 765 GIC 65 : int colorsCount = pg_reg_getnumcolors(regex);
3652 tgl 766 ECB : int i;
767 :
3652 tgl 768 GIC 65 : trgmNFA->ncolors = colorsCount;
769 65 : trgmNFA->colorInfo = (TrgmColorInfo *)
770 65 : palloc0(colorsCount * sizeof(TrgmColorInfo));
3652 tgl 771 ECB :
772 : /*
773 : * Loop over colors, filling TrgmColorInfo about each. Note we include
778 774 : * WHITE (0) even though we know it'll be reported as non-expandable.
3652 775 : */
3652 tgl 776 GIC 596 : for (i = 0; i < colorsCount; i++)
777 : {
3652 tgl 778 CBC 531 : TrgmColorInfo *colorInfo = &trgmNFA->colorInfo[i];
779 531 : int charsCount = pg_reg_getnumcharacters(regex, i);
3652 tgl 780 ECB : pg_wchar *chars;
781 : int j;
782 :
3652 tgl 783 GIC 531 : if (charsCount < 0 || charsCount > COLOR_COUNT_LIMIT)
784 : {
3652 tgl 785 ECB : /* Non expandable, or too large to work with */
3652 tgl 786 CBC 325 : colorInfo->expandable = false;
3652 tgl 787 GIC 325 : continue;
788 : }
789 :
790 206 : colorInfo->expandable = true;
791 206 : colorInfo->containsNonWord = false;
792 206 : colorInfo->wordChars = (trgm_mb_char *)
793 206 : palloc(sizeof(trgm_mb_char) * charsCount);
3652 tgl 794 CBC 206 : colorInfo->wordCharsCount = 0;
795 :
796 : /* Extract all the chars in this color */
3652 tgl 797 GIC 206 : chars = (pg_wchar *) palloc(sizeof(pg_wchar) * charsCount);
3652 tgl 798 CBC 206 : pg_reg_getcharacters(regex, i, chars, charsCount);
3652 tgl 799 ECB :
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 : */
3652 tgl 806 CBC 991 : for (j = 0; j < charsCount; j++)
807 : {
3652 tgl 808 ECB : trgm_mb_char c;
809 :
3652 tgl 810 GIC 785 : if (!convertPgWchar(chars[j], &c))
811 365 : continue; /* ok to ignore it altogether */
812 420 : if (ISWORDCHR(c.bytes))
813 395 : colorInfo->wordChars[colorInfo->wordCharsCount++] = c;
814 : else
3652 tgl 815 CBC 25 : colorInfo->containsNonWord = true;
816 : }
817 :
3652 tgl 818 GIC 206 : pfree(chars);
819 : }
820 65 : }
821 :
822 : /*
823 : * Convert pg_wchar to multibyte format.
824 : * Returns false if the character should be ignored completely.
3652 tgl 825 ECB : */
3652 tgl 826 EUB : static bool
3652 tgl 827 GIC 785 : convertPgWchar(pg_wchar c, trgm_mb_char *result)
828 : {
3652 tgl 829 ECB : /* "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 : */
3652 tgl 837 GIC 785 : if (c == 0)
3652 tgl 838 UIC 0 : return false;
839 :
840 : /* Do the conversion, making sure the result is NUL-terminated */
3652 tgl 841 GIC 785 : memset(s, 0, sizeof(s));
842 785 : 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
3652 tgl 847 ECB : * 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 : {
3652 tgl 859 CBC 785 : char *lowerCased = lowerstr(s);
3652 tgl 860 ECB :
3652 tgl 861 GIC 785 : if (strcmp(lowerCased, s) != 0)
862 : {
863 365 : pfree(lowerCased);
864 365 : return false;
865 : }
866 420 : pfree(lowerCased);
867 : }
868 : #endif
869 :
870 : /* Fill result with exactly MAX_MULTIBYTE_CHAR_LEN bytes */
2997 871 420 : memcpy(result->bytes, s, MAX_MULTIBYTE_CHAR_LEN);
3652 872 420 : return true;
873 : }
874 :
875 :
876 : /*---------------------
877 : * Subroutines for expanding original NFA graph into a trigram graph (stage 2).
878 : *---------------------
879 : */
880 :
3652 tgl 881 ECB : /*
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
3652 tgl 893 GIC 65 : transformGraph(TrgmNFA *trgmNFA)
894 : {
3652 tgl 895 ECB : HASHCTL hashCtl;
896 : TrgmStateKey initkey;
897 : TrgmState *initstate;
524 898 : ListCell *lc;
899 :
900 : /* Initialize this stage's workspace in trgmNFA struct */
3652 tgl 901 GIC 65 : trgmNFA->queue = NIL;
3652 tgl 902 CBC 65 : trgmNFA->keysQueue = NIL;
3652 tgl 903 GIC 65 : trgmNFA->arcsCount = 0;
904 65 : trgmNFA->overflowed = false;
3652 tgl 905 ECB :
906 : /* Create hashtable for states */
3652 tgl 907 CBC 65 : hashCtl.keysize = sizeof(TrgmStateKey);
908 65 : hashCtl.entrysize = sizeof(TrgmState);
3652 tgl 909 GIC 65 : hashCtl.hcxt = CurrentMemoryContext;
3652 tgl 910 CBC 65 : trgmNFA->states = hash_create("Trigram NFA",
3652 tgl 911 ECB : 1024,
912 : &hashCtl,
913 : HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
2186 tgl 914 GIC 65 : trgmNFA->nstates = 0;
915 :
916 : /* Create initial state: ambiguous prefix, NFA's initial state */
3652 917 65 : MemSet(&initkey, 0, sizeof(initkey));
918 65 : initkey.prefix.colors[0] = COLOR_UNKNOWN;
919 65 : initkey.prefix.colors[1] = COLOR_UNKNOWN;
920 65 : initkey.nstate = pg_reg_getinitialstate(trgmNFA->regex);
3652 tgl 921 ECB :
3652 tgl 922 GIC 65 : initstate = getState(trgmNFA, &initkey);
2237 tgl 923 CBC 65 : initstate->flags |= TSTATE_INIT;
3652 tgl 924 GIC 65 : 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.
524 tgl 929 ECB : * 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.
3652 932 : */
524 tgl 933 GIC 729 : foreach(lc, trgmNFA->queue)
934 : {
524 tgl 935 CBC 664 : TrgmState *state = (TrgmState *) lfirst(lc);
3652 tgl 936 ECB :
937 : /*
938 : * If we overflowed then just mark state as final. Otherwise do
939 : * actual processing.
940 : */
3652 tgl 941 GIC 664 : if (trgmNFA->overflowed)
2237 942 9 : state->flags |= TSTATE_FIN;
943 : else
3652 944 655 : processState(trgmNFA, state);
3652 tgl 945 ECB :
946 : /* Did we overflow? */
3652 tgl 947 GIC 1328 : if (trgmNFA->arcsCount > MAX_EXPANDED_ARCS ||
948 664 : hash_get_num_entries(trgmNFA->states) > MAX_EXPANDED_STATES)
949 12 : trgmNFA->overflowed = true;
3652 tgl 950 ECB : }
3652 tgl 951 GIC 65 : }
952 :
953 : /*
954 : * Process one state: add enter keys and then add outgoing arcs.
955 : */
3652 tgl 956 ECB : static void
3652 tgl 957 CBC 655 : processState(TrgmNFA *trgmNFA, TrgmState *state)
958 : {
524 tgl 959 ECB : ListCell *lc;
960 :
3652 961 : /* keysQueue should be NIL already, but make sure */
3652 tgl 962 CBC 655 : trgmNFA->keysQueue = NIL;
3652 tgl 963 ECB :
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 : */
3652 tgl 968 CBC 655 : addKey(trgmNFA, state, &state->stateKey);
524 tgl 969 GIC 1266 : foreach(lc, trgmNFA->keysQueue)
970 : {
971 692 : TrgmStateKey *key = (TrgmStateKey *) lfirst(lc);
972 :
973 692 : if (state->flags & TSTATE_FIN)
524 tgl 974 CBC 81 : break;
3652 975 611 : addKey(trgmNFA, state, key);
3652 tgl 976 ECB : }
977 :
978 : /* Release keysQueue to clean up for next cycle */
524 tgl 979 GIC 655 : list_free(trgmNFA->keysQueue);
980 655 : 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 : */
2237 986 655 : if (!(state->flags & TSTATE_FIN))
3652 987 571 : addArcs(trgmNFA, state);
988 655 : }
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 : *
2237 tgl 995 ECB : * 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
3652 tgl 1007 CBC 1266 : addKey(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key)
1008 : {
1009 : regex_arc_t *arcs;
1010 : TrgmStateKey destKey;
1011 : ListCell *cell;
1012 : int i,
1013 : arcsCount;
3652 tgl 1014 ECB :
1015 : /*
1016 : * Ensure any pad bytes in destKey are zero, since it may get used as a
1017 : * hashtable key by getState.
1018 : */
3652 tgl 1019 GIC 1266 : MemSet(&destKey, 0, sizeof(destKey));
3652 tgl 1020 ECB :
1021 : /*
1022 : * Compare key to each existing enter key of the state to check for
3260 bruce 1023 : * redundancy. We can drop either old key(s) or the new key if we find
1024 : * redundancy.
3652 tgl 1025 : */
1364 tgl 1026 GIC 1979 : foreach(cell, state->enterKeys)
1027 : {
3652 1028 1016 : TrgmStateKey *existingKey = (TrgmStateKey *) lfirst(cell);
1029 :
1030 1016 : if (existingKey->nstate == key->nstate)
3652 tgl 1031 ECB : {
3652 tgl 1032 GIC 312 : if (prefixContains(&existingKey->prefix, &key->prefix))
1033 : {
1034 : /* This old key already covers the new key. Nothing to do */
1035 303 : return;
1036 : }
1037 9 : if (prefixContains(&key->prefix, &existingKey->prefix))
3652 tgl 1038 ECB : {
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 : */
1364 tgl 1043 CBC 6 : state->enterKeys = foreach_delete_current(state->enterKeys,
1364 tgl 1044 ECB : cell);
1045 : }
1046 : }
1047 : }
1048 :
1049 : /* No redundancy, so add this key to the state's list */
3652 tgl 1050 GIC 963 : state->enterKeys = lappend(state->enterKeys, key);
3652 tgl 1051 ECB :
1052 : /* If state is now known final, mark it and we're done */
3652 tgl 1053 CBC 963 : if (key->nstate == pg_reg_getfinalstate(trgmNFA->regex))
1054 : {
2237 1055 84 : state->flags |= TSTATE_FIN;
3652 tgl 1056 GIC 84 : return;
3652 tgl 1057 ECB : }
1058 :
1059 : /*
1060 : * Loop through all outgoing arcs of the corresponding state in the
1061 : * original NFA.
1062 : */
3652 tgl 1063 GIC 879 : arcsCount = pg_reg_getnumoutarcs(trgmNFA->regex, key->nstate);
1064 879 : arcs = (regex_arc_t *) palloc(sizeof(regex_arc_t) * arcsCount);
1065 879 : pg_reg_getoutarcs(trgmNFA->regex, key->nstate, arcs, arcsCount);
1066 :
3652 tgl 1067 CBC 2384 : for (i = 0; i < arcsCount; i++)
3652 tgl 1068 ECB : {
3652 tgl 1069 CBC 1505 : regex_arc_t *arc = &arcs[i];
1070 :
3652 tgl 1071 GIC 1505 : if (pg_reg_colorisbegin(trgmNFA->regex, arc->co))
3652 tgl 1072 ECB : {
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 : */
3652 tgl 1079 GIC 246 : destKey.prefix.colors[0] = COLOR_BLANK;
1080 246 : destKey.prefix.colors[1] = COLOR_BLANK;
1081 246 : destKey.nstate = arc->to;
3652 tgl 1082 ECB :
1083 : /* Add enter key to this state */
3652 tgl 1084 CBC 246 : addKeyToQueue(trgmNFA, &destKey);
1085 : }
3652 tgl 1086 GIC 1259 : else if (pg_reg_colorisend(trgmNFA->regex, arc->co))
3652 tgl 1087 ECB : {
1088 : /*
3260 bruce 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
3652 tgl 1092 : * NFA's final state, we must mark this expanded state as final.
1093 : */
3652 tgl 1094 CBC 162 : destKey.prefix.colors[0] = COLOR_UNKNOWN;
3652 tgl 1095 GIC 162 : destKey.prefix.colors[1] = COLOR_UNKNOWN;
3652 tgl 1096 CBC 162 : destKey.nstate = arc->to;
3652 tgl 1097 ECB :
1098 : /* Add enter key to this state */
3652 tgl 1099 GIC 162 : addKeyToQueue(trgmNFA, &destKey);
1100 : }
778 1101 1097 : else if (arc->co >= 0)
1102 : {
1103 : /* Regular color (including WHITE) */
3652 1104 893 : TrgmColorInfo *colorInfo = &trgmNFA->colorInfo[arc->co];
1105 :
1106 893 : if (colorInfo->expandable)
1107 : {
1108 893 : if (colorInfo->containsNonWord &&
3652 tgl 1109 CBC 55 : !validArcLabel(key, COLOR_BLANK))
3652 tgl 1110 ECB : {
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 : */
3652 tgl 1121 GIC 27 : destKey.prefix.colors[0] = COLOR_BLANK;
1122 27 : destKey.prefix.colors[1] = COLOR_BLANK;
1123 27 : destKey.nstate = arc->to;
1124 27 : addKeyToQueue(trgmNFA, &destKey);
1125 : }
3652 tgl 1126 ECB :
3652 tgl 1127 CBC 893 : if (colorInfo->wordCharsCount > 0 &&
1128 838 : !validArcLabel(key, arc->co))
3652 tgl 1129 ECB : {
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 : */
3652 tgl 1138 GIC 131 : destKey.prefix.colors[0] = key->prefix.colors[1];
1139 131 : destKey.prefix.colors[1] = arc->co;
1140 131 : destKey.nstate = arc->to;
3652 tgl 1141 GBC 131 : addKeyToQueue(trgmNFA, &destKey);
3652 tgl 1142 EUB : }
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
3652 tgl 1150 ECB : * first prefix color to key->prefix.colors[1], because a
1151 : * prefix of known followed by unknown is invalid.)
1152 : */
3652 tgl 1153 LBC 0 : destKey.prefix.colors[0] = COLOR_UNKNOWN;
3652 tgl 1154 UIC 0 : destKey.prefix.colors[1] = COLOR_UNKNOWN;
1155 0 : destKey.nstate = arc->to;
1156 0 : addKeyToQueue(trgmNFA, &destKey);
3652 tgl 1157 ECB : }
1158 : }
1159 : else
1160 : {
1161 : /* RAINBOW: treat as unexpandable color */
778 tgl 1162 GIC 204 : destKey.prefix.colors[0] = COLOR_UNKNOWN;
1163 204 : destKey.prefix.colors[1] = COLOR_UNKNOWN;
778 tgl 1164 CBC 204 : destKey.nstate = arc->to;
778 tgl 1165 GIC 204 : addKeyToQueue(trgmNFA, &destKey);
778 tgl 1166 ECB : }
1167 : }
3652 1168 :
3652 tgl 1169 CBC 879 : pfree(arcs);
3652 tgl 1170 ECB : }
1171 :
1172 : /*
1173 : * Add copy of given key to keysQueue for later processing.
1174 : */
1175 : static void
3652 tgl 1176 CBC 770 : addKeyToQueue(TrgmNFA *trgmNFA, TrgmStateKey *key)
1177 : {
3652 tgl 1178 GIC 770 : TrgmStateKey *keyCopy = (TrgmStateKey *) palloc(sizeof(TrgmStateKey));
1179 :
1180 770 : memcpy(keyCopy, key, sizeof(TrgmStateKey));
1181 770 : trgmNFA->keysQueue = lappend(trgmNFA->keysQueue, keyCopy);
1182 770 : }
1183 :
1184 : /*
1185 : * Add outgoing arcs from given state, whose enter keys are all now known.
1186 : */
1187 : static void
3652 tgl 1188 CBC 571 : addArcs(TrgmNFA *trgmNFA, TrgmState *state)
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.
3652 tgl 1199 ECB : */
3652 tgl 1200 GIC 571 : MemSet(&destKey, 0, sizeof(destKey));
3652 tgl 1201 ECB :
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 : */
3652 tgl 1211 GIC 1336 : foreach(cell, state->enterKeys)
1212 : {
1213 765 : TrgmStateKey *key = (TrgmStateKey *) lfirst(cell);
1214 :
1215 765 : arcsCount = pg_reg_getnumoutarcs(trgmNFA->regex, key->nstate);
1216 765 : arcs = (regex_arc_t *) palloc(sizeof(regex_arc_t) * arcsCount);
1217 765 : pg_reg_getoutarcs(trgmNFA->regex, key->nstate, arcs, arcsCount);
1218 :
1219 1946 : for (i = 0; i < arcsCount; i++)
1220 : {
3652 tgl 1221 CBC 1181 : regex_arc_t *arc = &arcs[i];
777 tgl 1222 ECB : TrgmColorInfo *colorInfo;
3652 1223 :
1224 : /*
1225 : * Ignore non-expandable colors; addKey already handled the case.
1226 : *
778 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 : */
777 tgl 1233 GIC 1181 : if (arc->co < 0)
1234 102 : continue;
1235 1079 : Assert(arc->co < trgmNFA->ncolors);
1236 :
1237 1079 : colorInfo = &trgmNFA->colorInfo[arc->co];
3652 tgl 1238 CBC 1079 : if (!colorInfo->expandable)
1239 210 : continue;
3652 tgl 1240 ECB :
3652 tgl 1241 GIC 869 : if (colorInfo->containsNonWord)
3652 tgl 1242 ECB : {
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 : */
3652 tgl 1250 GIC 55 : destKey.prefix.colors[0] = key->prefix.colors[1];
1251 55 : destKey.prefix.colors[1] = COLOR_BLANK;
1252 55 : destKey.nstate = arc->to;
3652 tgl 1253 ECB :
3652 tgl 1254 CBC 55 : addArc(trgmNFA, state, key, COLOR_BLANK, &destKey);
3652 tgl 1255 ECB : }
1256 :
3652 tgl 1257 CBC 869 : if (colorInfo->wordCharsCount > 0)
1258 : {
1259 : /*
1260 : * Color includes word character(s).
3652 tgl 1261 ECB : *
1262 : * Generate an arc. Color is pushed into prefix of target
1263 : * state.
1264 : */
3652 tgl 1265 GIC 814 : destKey.prefix.colors[0] = key->prefix.colors[1];
1266 814 : destKey.prefix.colors[1] = arc->co;
1267 814 : destKey.nstate = arc->to;
1268 :
1269 814 : addArc(trgmNFA, state, key, arc->co, &destKey);
1270 : }
1271 : }
1272 :
1273 765 : pfree(arcs);
3652 tgl 1274 ECB : }
3652 tgl 1275 GIC 571 : }
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
3652 tgl 1281 ECB : * 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
3652 tgl 1286 GIC 869 : addArc(TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key,
1287 : TrgmColor co, TrgmStateKey *destKey)
1288 : {
1289 : TrgmArc *arc;
3652 tgl 1290 ECB : ListCell *cell;
1291 :
1292 : /* Do nothing if this wouldn't be a valid arc label trigram */
3652 tgl 1293 GIC 869 : if (!validArcLabel(key, co))
3652 tgl 1294 CBC 137 : return;
3652 tgl 1295 ECB :
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 : */
3652 tgl 1302 CBC 1767 : foreach(cell, state->enterKeys)
3652 tgl 1303 ECB : {
3652 tgl 1304 CBC 1041 : TrgmStateKey *existingKey = (TrgmStateKey *) lfirst(cell);
1305 :
1306 1066 : if (existingKey->nstate == destKey->nstate &&
1307 25 : prefixContains(&existingKey->prefix, &destKey->prefix))
3652 tgl 1308 GIC 6 : return;
1309 : }
1310 :
1311 : /* Checks were successful, add new arc */
1312 726 : arc = (TrgmArc *) palloc(sizeof(TrgmArc));
1313 726 : arc->target = getState(trgmNFA, destKey);
1314 726 : arc->ctrgm.colors[0] = key->prefix.colors[0];
1315 726 : arc->ctrgm.colors[1] = key->prefix.colors[1];
3652 tgl 1316 CBC 726 : arc->ctrgm.colors[2] = co;
1317 :
3652 tgl 1318 GIC 726 : state->arcs = lappend(state->arcs, arc);
1319 726 : trgmNFA->arcsCount++;
1320 : }
1321 :
3652 tgl 1322 ECB : /*
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
3652 tgl 1328 CBC 1762 : validArcLabel(TrgmStateKey *key, TrgmColor co)
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 1762 : if (key->prefix.colors[0] == COLOR_UNKNOWN)
1335 233 : return false;
1336 :
3652 tgl 1337 ECB : /* If key->prefix.colors[0] isn't unknown, its second color isn't either */
3652 tgl 1338 GIC 1529 : Assert(key->prefix.colors[1] != COLOR_UNKNOWN);
1339 : /* And we should not be called with an unknown arc color anytime */
1340 1529 : 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 1529 : if (key->prefix.colors[0] == COLOR_BLANK &&
1347 164 : key->prefix.colors[1] == COLOR_BLANK &&
3652 tgl 1348 ECB : co == COLOR_BLANK)
3652 tgl 1349 CBC 12 : return false;
3652 tgl 1350 ECB :
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 : */
3652 tgl 1360 GIC 1517 : if (key->prefix.colors[0] != COLOR_BLANK &&
1361 1365 : key->prefix.colors[1] == COLOR_BLANK)
1362 50 : return false;
3652 tgl 1363 ECB :
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 */
3652 tgl 1375 GIC 1467 : return true;
3652 tgl 1376 ECB : }
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 *
3652 tgl 1383 CBC 791 : getState(TrgmNFA *trgmNFA, TrgmStateKey *key)
1384 : {
3652 tgl 1385 ECB : TrgmState *state;
1386 : bool found;
1387 :
3652 tgl 1388 CBC 791 : state = (TrgmState *) hash_search(trgmNFA->states, key, HASH_ENTER,
1389 : &found);
1390 791 : if (!found)
1391 : {
3652 tgl 1392 ECB : /* New state: initialize and queue it */
3652 tgl 1393 GIC 664 : state->arcs = NIL;
1394 664 : state->enterKeys = NIL;
2237 1395 664 : state->flags = 0;
1396 : /* states are initially given negative numbers */
2186 1397 664 : state->snumber = -(++trgmNFA->nstates);
3652 1398 664 : state->parent = NULL;
2186 1399 664 : state->tentFlags = 0;
2237 1400 664 : state->tentParent = NULL;
1401 :
3652 tgl 1402 CBC 664 : trgmNFA->queue = lappend(trgmNFA->queue, state);
1403 : }
1404 791 : return state;
1405 : }
1406 :
3652 tgl 1407 ECB : /*
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
3652 tgl 1414 GIC 346 : prefixContains(TrgmPrefix *prefix1, TrgmPrefix *prefix2)
3652 tgl 1415 ECB : {
3652 tgl 1416 CBC 346 : if (prefix1->colors[1] == COLOR_UNKNOWN)
1417 : {
3652 tgl 1418 ECB : /* Fully ambiguous prefix contains everything */
3652 tgl 1419 GIC 306 : return true;
1420 : }
1421 40 : else if (prefix1->colors[0] == COLOR_UNKNOWN)
1422 : {
3652 tgl 1423 ECB : /*
1424 : * Prefix with only first unknown color contains every prefix with
1425 : * same second color.
1426 : */
3652 tgl 1427 CBC 12 : if (prefix1->colors[1] == prefix2->colors[1])
3652 tgl 1428 GIC 3 : return true;
1429 : else
1430 9 : return false;
1431 : }
1432 : else
1433 : {
1434 : /* Exact prefix contains only the exact same prefix */
1435 28 : if (prefix1->colors[0] == prefix2->colors[0] &&
1436 13 : prefix1->colors[1] == prefix2->colors[1])
1437 6 : return true;
1438 : else
1439 22 : return false;
1440 : }
1441 : }
1442 :
1443 :
3652 tgl 1444 ECB : /*---------------------
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
3652 tgl 1456 CBC 56 : selectColorTrigrams(TrgmNFA *trgmNFA)
3652 tgl 1457 ECB : {
1458 : HASH_SEQ_STATUS scan_status;
3652 tgl 1459 CBC 56 : int arcsCount = trgmNFA->arcsCount,
3652 tgl 1460 ECB : i;
1461 : TrgmState *state;
1462 : ColorTrgmInfo *colorTrgms;
1463 : int64 totalTrgmCount;
1464 : float4 totalTrgmPenalty;
2186 1465 : int cnumber;
1466 :
3652 1467 : /* Collect color trigrams from all arcs */
2186 tgl 1468 CBC 56 : colorTrgms = (ColorTrgmInfo *) palloc0(sizeof(ColorTrgmInfo) * arcsCount);
3652 1469 56 : trgmNFA->colorTrgms = colorTrgms;
1470 :
1471 56 : i = 0;
1472 56 : hash_seq_init(&scan_status, trgmNFA->states);
1473 711 : while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
3652 tgl 1474 ECB : {
1475 : ListCell *cell;
1476 :
3652 tgl 1477 CBC 1381 : foreach(cell, state->arcs)
3652 tgl 1478 ECB : {
3652 tgl 1479 GIC 726 : TrgmArc *arc = (TrgmArc *) lfirst(cell);
1480 726 : TrgmArcInfo *arcInfo = (TrgmArcInfo *) palloc(sizeof(TrgmArcInfo));
2186 tgl 1481 CBC 726 : ColorTrgmInfo *trgmInfo = &colorTrgms[i];
1482 :
3652 tgl 1483 GIC 726 : arcInfo->source = state;
3652 tgl 1484 CBC 726 : arcInfo->target = arc->target;
2186 tgl 1485 GIC 726 : trgmInfo->ctrgm = arc->ctrgm;
1486 726 : trgmInfo->cnumber = -1;
1487 : /* count and penalty will be set below */
1488 726 : trgmInfo->expanded = true;
1489 726 : trgmInfo->arcs = list_make1(arcInfo);
3652 tgl 1490 CBC 726 : i++;
1491 : }
1492 : }
1493 56 : Assert(i == arcsCount);
3652 tgl 1494 ECB :
1495 : /* Remove duplicates, merging their arcs lists */
3652 tgl 1496 CBC 56 : if (arcsCount >= 2)
1497 : {
3652 tgl 1498 ECB : ColorTrgmInfo *p1,
1499 : *p2;
1500 :
1501 : /* Sort trigrams to ease duplicate detection */
3652 tgl 1502 GIC 34 : qsort(colorTrgms, arcsCount, sizeof(ColorTrgmInfo), colorTrgmInfoCmp);
3652 tgl 1503 ECB :
1504 : /* p1 is probe point, p2 is last known non-duplicate. */
3652 tgl 1505 GIC 34 : p2 = colorTrgms;
3652 tgl 1506 CBC 706 : for (p1 = colorTrgms + 1; p1 < colorTrgms + arcsCount; p1++)
1507 : {
3652 tgl 1508 GIC 672 : if (colorTrgmInfoCmp(p1, p2) > 0)
1509 : {
3652 tgl 1510 CBC 224 : p2++;
3652 tgl 1511 GIC 224 : *p2 = *p1;
1512 : }
1513 : else
1514 : {
1515 448 : p2->arcs = list_concat(p2->arcs, p1->arcs);
1516 : }
1517 : }
1518 34 : trgmNFA->colorTrgmsCount = (p2 - colorTrgms) + 1;
1519 : }
1520 : else
1521 : {
1522 22 : trgmNFA->colorTrgmsCount = arcsCount;
1523 : }
1524 :
3652 tgl 1525 ECB : /*
3291 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.
3652 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,
3291 1534 : * penalties are calculated in float4 arithmetic to avoid any overflow
1535 : * worries.
3652 1536 : */
3652 tgl 1537 GIC 56 : totalTrgmCount = 0;
3291 tgl 1538 CBC 56 : totalTrgmPenalty = 0.0f;
3652 1539 334 : for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
3652 tgl 1540 ECB : {
3652 tgl 1541 GIC 278 : ColorTrgmInfo *trgmInfo = &colorTrgms[i];
3652 tgl 1542 ECB : int j,
3291 tgl 1543 GIC 278 : count = 1,
3291 tgl 1544 CBC 278 : typeIndex = 0;
3652 tgl 1545 ECB :
3652 tgl 1546 CBC 1112 : for (j = 0; j < 3; j++)
3652 tgl 1547 ECB : {
3652 tgl 1548 GIC 834 : TrgmColor c = trgmInfo->ctrgm.colors[j];
1549 :
3291 1550 834 : typeIndex *= 2;
3291 tgl 1551 CBC 834 : if (c == COLOR_BLANK)
3291 tgl 1552 GIC 113 : typeIndex++;
1553 : else
3652 1554 721 : count *= trgmNFA->colorInfo[c].wordCharsCount;
1555 : }
1556 278 : trgmInfo->count = count;
1557 278 : totalTrgmCount += count;
3291 1558 278 : trgmInfo->penalty = penalties[typeIndex] * (float4) count;
1559 278 : totalTrgmPenalty += trgmInfo->penalty;
1560 : }
1561 :
1562 : /* Sort color trigrams in descending order of their penalties */
3652 1563 56 : qsort(colorTrgms, trgmNFA->colorTrgmsCount, sizeof(ColorTrgmInfo),
1564 : colorTrgmInfoPenaltyCmp);
3652 tgl 1565 ECB :
1566 : /*
3291 1567 : * Remove color trigrams from the graph so long as total penalty of color
3260 bruce 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
3291 tgl 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 : */
3291 tgl 1577 GIC 204 : for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
1578 : {
3652 1579 179 : ColorTrgmInfo *trgmInfo = &colorTrgms[i];
1580 179 : bool canRemove = true;
1581 : ListCell *cell;
1582 :
1583 : /* Done if we've reached the target */
3291 1584 179 : if (totalTrgmPenalty <= WISH_TRGM_PENALTY)
1585 31 : break;
1586 :
1587 : #ifdef TRGM_REGEXP_DEBUG
2186 tgl 1588 ECB : 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 : */
3652 tgl 1600 GIC 306 : foreach(cell, trgmInfo->arcs)
1601 : {
1602 191 : TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell);
3652 tgl 1603 CBC 191 : TrgmState *source = arcInfo->source,
1604 191 : *target = arcInfo->target;
2237 tgl 1605 ECB : 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 */
3652 tgl 1615 CBC 341 : while (source->parent)
1616 150 : source = source->parent;
3652 tgl 1617 GIC 407 : while (target->parent)
3652 tgl 1618 CBC 216 : target = target->parent;
3652 tgl 1619 ECB :
1620 : #ifdef TRGM_REGEXP_DEBUG
2186 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 */
2186 tgl 1627 GIC 191 : source_flags = source->flags | source->tentFlags;
2237 1628 195 : while (source->tentParent)
1629 : {
1630 4 : source = source->tentParent;
2186 1631 4 : source_flags |= source->flags | source->tentFlags;
1632 : }
1633 191 : target_flags = target->flags | target->tentFlags;
2237 1634 206 : while (target->tentParent)
2237 tgl 1635 ECB : {
2237 tgl 1636 GIC 15 : target = target->tentParent;
2186 1637 15 : target_flags |= target->flags | target->tentFlags;
2237 tgl 1638 ECB : }
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,
2186 1643 : -source->snumber, source_flags);
1644 : #endif
1645 :
1646 : /* would fully-merged state have both INIT and FIN set? */
2237 tgl 1647 GIC 191 : if (((source_flags | target_flags) & (TSTATE_INIT | TSTATE_FIN)) ==
1648 : (TSTATE_INIT | TSTATE_FIN))
3652 tgl 1649 ECB : {
3652 tgl 1650 CBC 33 : canRemove = false;
3652 tgl 1651 GIC 33 : break;
1652 : }
1653 :
1654 : /* ok so far, so remember planned merge */
2237 1655 158 : 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 113 : target->tentParent = source;
2186 1662 113 : source->tentFlags |= target_flags;
1663 : }
1664 : }
2237 tgl 1665 ECB :
1666 : /*
2186 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 : */
2237 tgl 1677 GIC 348 : foreach(cell, trgmInfo->arcs)
2237 tgl 1678 ECB : {
2237 tgl 1679 GIC 200 : TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell);
2186 tgl 1680 CBC 200 : TrgmState *source = arcInfo->source,
1681 200 : *target = arcInfo->target;
1682 : TrgmState *ttarget;
1683 :
2186 tgl 1684 ECB : /* no need to touch previously-merged states */
2186 tgl 1685 GIC 350 : while (source->parent)
2186 tgl 1686 CBC 150 : source = source->parent;
2237 1687 440 : while (target->parent)
1688 240 : target = target->parent;
1689 :
2186 tgl 1690 GIC 406 : while (source)
1691 : {
1692 206 : source->tentFlags = 0;
2186 tgl 1693 CBC 206 : source = source->tentParent;
1694 : }
1695 :
2237 tgl 1696 GIC 313 : while ((ttarget = target->tentParent) != NULL)
1697 : {
2237 tgl 1698 CBC 113 : target->tentParent = NULL;
2186 tgl 1699 GIC 113 : target->tentFlags = 0; /* in case it was also a source */
2237 1700 113 : target = ttarget;
1701 : }
2237 tgl 1702 ECB : }
1703 :
1704 : /* Now, move on if we can't drop this trigram */
3652 tgl 1705 CBC 148 : if (!canRemove)
2186 tgl 1706 ECB : {
1707 : #ifdef TRGM_REGEXP_DEBUG
1708 : fprintf(stderr, " ... not ok to merge\n");
1709 : #endif
3652 tgl 1710 CBC 33 : continue;
2186 tgl 1711 ECB : }
3652 1712 :
1713 : /* OK, merge states linked by each arc labeled by the trigram */
3652 tgl 1714 GIC 263 : foreach(cell, trgmInfo->arcs)
1715 : {
1716 148 : TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell);
1717 148 : TrgmState *source = arcInfo->source,
3652 tgl 1718 CBC 148 : *target = arcInfo->target;
1719 :
1720 292 : while (source->parent)
3652 tgl 1721 GIC 144 : source = source->parent;
1722 346 : while (target->parent)
1723 198 : target = target->parent;
1724 148 : if (source != target)
1725 : {
2186 tgl 1726 ECB : #ifdef TRGM_REGEXP_DEBUG
1727 : fprintf(stderr, "merging s%d into s%d\n",
1728 : -target->snumber, -source->snumber);
1729 : #endif
3652 tgl 1730 GIC 103 : mergeStates(source, target);
1731 : /* Assert we didn't merge initial and final states */
2237 tgl 1732 CBC 103 : Assert((source->flags & (TSTATE_INIT | TSTATE_FIN)) !=
2237 tgl 1733 ECB : (TSTATE_INIT | TSTATE_FIN));
1734 : }
3652 1735 : }
1736 :
1737 : /* Mark trigram unexpanded, and update totals */
3652 tgl 1738 GIC 115 : trgmInfo->expanded = false;
1739 115 : totalTrgmCount -= trgmInfo->count;
3291 1740 115 : totalTrgmPenalty -= trgmInfo->penalty;
3652 tgl 1741 ECB : }
1742 :
1743 : /* Did we succeed in fitting into MAX_TRGM_COUNT? */
3652 tgl 1744 CBC 56 : if (totalTrgmCount > MAX_TRGM_COUNT)
3652 tgl 1745 GIC 3 : return false;
3652 tgl 1746 ECB :
3652 tgl 1747 GIC 53 : trgmNFA->totalTrgmCount = (int) totalTrgmCount;
3652 tgl 1748 ECB :
1749 : /*
1750 : * Sort color trigrams by colors (will be useful for bsearch in packGraph)
1751 : * and enumerate the color trigrams that are expanded.
1752 : */
2186 tgl 1753 CBC 53 : cnumber = 0;
3652 tgl 1754 GIC 53 : qsort(colorTrgms, trgmNFA->colorTrgmsCount, sizeof(ColorTrgmInfo),
1755 : colorTrgmInfoCmp);
1756 328 : for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
1757 : {
1758 275 : if (colorTrgms[i].expanded)
1759 : {
2186 1760 160 : colorTrgms[i].cnumber = cnumber;
1761 160 : cnumber++;
1762 : }
3652 tgl 1763 ECB : }
1764 :
3652 tgl 1765 GIC 53 : 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.
3652 tgl 1772 ECB : * The array must be allocated in rcontext.
1773 : */
1774 : static TRGM *
3652 tgl 1775 GIC 53 : expandColorTrigrams(TrgmNFA *trgmNFA, MemoryContext rcontext)
1776 : {
1777 : TRGM *trg;
3652 tgl 1778 ECB : 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 */
3652 tgl 1784 CBC 53 : memset(blankChar.bytes, 0, sizeof(blankChar.bytes));
3652 tgl 1785 GIC 53 : blankColor.wordCharsCount = 1;
3652 tgl 1786 CBC 53 : blankColor.wordChars = &blankChar;
1787 :
1788 : /* Construct the trgm array */
1789 : trg = (TRGM *)
3652 tgl 1790 GIC 53 : MemoryContextAllocZero(rcontext,
1791 : TRGMHDRSIZE +
1792 53 : trgmNFA->totalTrgmCount * sizeof(trgm));
1793 53 : trg->flag = ARRKEY;
1794 53 : SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, trgmNFA->totalTrgmCount));
3652 tgl 1795 CBC 53 : p = GETARR(trg);
1796 328 : for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
1797 : {
3652 tgl 1798 GIC 275 : ColorTrgmInfo *colorTrgm = &trgmNFA->colorTrgms[i];
3652 tgl 1799 ECB : TrgmColorInfo *c[3];
1800 : trgm_mb_char s[3];
1801 : int j,
1802 : i1,
1803 : i2,
1804 : i3;
1805 :
1806 : /* Ignore any unexpanded trigrams ... */
3652 tgl 1807 GIC 275 : if (!colorTrgm->expanded)
3652 tgl 1808 CBC 115 : continue;
1809 :
3652 tgl 1810 ECB : /* Get colors, substituting the dummy struct for COLOR_BLANK */
3652 tgl 1811 CBC 640 : for (j = 0; j < 3; j++)
1812 : {
1813 480 : if (colorTrgm->ctrgm.colors[j] != COLOR_BLANK)
1814 413 : c[j] = &trgmNFA->colorInfo[colorTrgm->ctrgm.colors[j]];
1815 : else
1816 67 : c[j] = &blankColor;
3652 tgl 1817 ECB : }
1818 :
1819 : /* Iterate over all possible combinations of colors' characters */
3652 tgl 1820 GIC 377 : for (i1 = 0; i1 < c[0]->wordCharsCount; i1++)
1821 : {
1822 217 : s[0] = c[0]->wordChars[i1];
1823 728 : for (i2 = 0; i2 < c[1]->wordCharsCount; i2++)
3652 tgl 1824 ECB : {
3652 tgl 1825 GIC 511 : s[1] = c[1]->wordChars[i2];
1826 1970 : for (i3 = 0; i3 < c[2]->wordCharsCount; i3++)
1827 : {
1828 1459 : s[2] = c[2]->wordChars[i3];
1829 1459 : fillTrgm(p, s);
1830 1459 : p++;
3652 tgl 1831 ECB : }
1832 : }
1833 : }
1834 : }
1835 :
3652 tgl 1836 GIC 53 : return trg;
1837 : }
1838 :
3652 tgl 1839 ECB : /*
1840 : * Convert trigram into trgm datatype.
1841 : */
1842 : static void
3652 tgl 1843 CBC 1459 : fillTrgm(trgm *ptrgm, trgm_mb_char s[3])
1844 : {
3652 tgl 1845 ECB : 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) */
3652 tgl 1851 CBC 1459 : p = str;
1852 :
3652 tgl 1853 GIC 5836 : for (i = 0; i < 3; i++)
1854 : {
1855 4377 : if (s[i].bytes[0] != 0)
3652 tgl 1856 ECB : {
3652 tgl 1857 CBC 8232 : for (j = 0; j < MAX_MULTIBYTE_CHAR_LEN && s[i].bytes[j]; j++)
3652 tgl 1858 GIC 4116 : *p++ = s[i].bytes[j];
1859 : }
1860 : else
1861 : {
1862 : /* Emit a space in place of COLOR_BLANK */
3652 tgl 1863 CBC 261 : *p++ = ' ';
1864 : }
3652 tgl 1865 ECB : }
1866 :
1867 : /* Convert "str" to a standard trigram (possibly hashing it) */
3652 tgl 1868 GIC 1459 : compact_trigram(ptrgm, str, p - str);
1869 1459 : }
3652 tgl 1870 ECB :
1871 : /*
1872 : * Merge two states of graph.
1873 : */
1874 : static void
3652 tgl 1875 GIC 103 : mergeStates(TrgmState *state1, TrgmState *state2)
1876 : {
1877 103 : Assert(state1 != state2);
1878 103 : Assert(!state1->parent);
1879 103 : Assert(!state2->parent);
3652 tgl 1880 ECB :
1881 : /* state1 absorbs state2's flags */
2237 tgl 1882 CBC 103 : state1->flags |= state2->flags;
3652 tgl 1883 ECB :
1884 : /* state2, and indirectly all its children, become children of state1 */
3652 tgl 1885 CBC 103 : state2->parent = state1;
3652 tgl 1886 GIC 103 : }
1887 :
1888 : /*
1889 : * Compare function for sorting of color trigrams by their colors.
1890 : */
1891 : static int
1892 5089 : colorTrgmInfoCmp(const void *p1, const void *p2)
3652 tgl 1893 ECB : {
3652 tgl 1894 GIC 5089 : const ColorTrgmInfo *c1 = (const ColorTrgmInfo *) p1;
3652 tgl 1895 CBC 5089 : const ColorTrgmInfo *c2 = (const ColorTrgmInfo *) p2;
3652 tgl 1896 ECB :
3652 tgl 1897 GIC 5089 : return memcmp(&c1->ctrgm, &c2->ctrgm, sizeof(ColorTrgm));
3652 tgl 1898 ECB : }
1899 :
1900 : /*
1901 : * Compare function for sorting color trigrams in descending order of
1902 : * their penalty fields.
1903 : */
1904 : static int
3291 tgl 1905 GIC 423 : colorTrgmInfoPenaltyCmp(const void *p1, const void *p2)
1906 : {
1907 423 : float4 penalty1 = ((const ColorTrgmInfo *) p1)->penalty;
1908 423 : float4 penalty2 = ((const ColorTrgmInfo *) p2)->penalty;
1909 :
1910 423 : if (penalty1 < penalty2)
3652 1911 127 : return 1;
3291 1912 296 : else if (penalty1 == penalty2)
3652 1913 162 : return 0;
1914 : else
1915 134 : return -1;
1916 : }
1917 :
3652 tgl 1918 ECB :
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 *
3652 tgl 1930 GIC 53 : packGraph(TrgmNFA *trgmNFA, MemoryContext rcontext)
1931 : {
2186 tgl 1932 CBC 53 : int snumber = 2,
3652 tgl 1933 ECB : 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 */
3652 tgl 1944 GIC 53 : hash_seq_init(&scan_status, trgmNFA->states);
1945 755 : while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
3652 tgl 1946 ECB : {
3652 tgl 1947 CBC 971 : while (state->parent)
3652 tgl 1948 GIC 322 : state = state->parent;
1949 :
2186 1950 649 : if (state->snumber < 0)
1951 : {
2237 1952 546 : if (state->flags & TSTATE_INIT)
2186 1953 53 : state->snumber = 0;
2237 tgl 1954 CBC 493 : else if (state->flags & TSTATE_FIN)
2186 1955 57 : state->snumber = 1;
3652 tgl 1956 ECB : else
1957 : {
2186 tgl 1958 GIC 436 : state->snumber = snumber;
2186 tgl 1959 CBC 436 : snumber++;
1960 : }
1961 : }
3652 tgl 1962 ECB : }
1963 :
1964 : /* Collect array of all arcs */
1965 : arcs = (TrgmPackArcInfo *)
3652 tgl 1966 GIC 53 : palloc(sizeof(TrgmPackArcInfo) * trgmNFA->arcsCount);
3652 tgl 1967 CBC 53 : arcIndex = 0;
1968 53 : hash_seq_init(&scan_status, trgmNFA->states);
3652 tgl 1969 GIC 702 : while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
3652 tgl 1970 ECB : {
3652 tgl 1971 CBC 649 : TrgmState *source = state;
1972 : ListCell *cell;
3652 tgl 1973 ECB :
3652 tgl 1974 GIC 971 : while (source->parent)
1975 322 : source = source->parent;
1976 :
3652 tgl 1977 CBC 1372 : foreach(cell, state->arcs)
3652 tgl 1978 ECB : {
3652 tgl 1979 CBC 723 : TrgmArc *arc = (TrgmArc *) lfirst(cell);
3652 tgl 1980 GIC 723 : TrgmState *target = arc->target;
1981 :
3652 tgl 1982 CBC 1352 : while (target->parent)
1983 629 : target = target->parent;
1984 :
2186 1985 723 : if (source->snumber != target->snumber)
3652 tgl 1986 ECB : {
1987 : ColorTrgmInfo *ctrgm;
1988 :
3652 tgl 1989 GIC 566 : ctrgm = (ColorTrgmInfo *) bsearch(&arc->ctrgm,
1990 566 : trgmNFA->colorTrgms,
1991 566 : trgmNFA->colorTrgmsCount,
1992 : sizeof(ColorTrgmInfo),
1993 : colorTrgmInfoCmp);
3652 tgl 1994 CBC 566 : Assert(ctrgm != NULL);
3652 tgl 1995 GIC 566 : Assert(ctrgm->expanded);
1996 :
2186 tgl 1997 CBC 566 : arcs[arcIndex].sourceState = source->snumber;
2186 tgl 1998 GIC 566 : arcs[arcIndex].targetState = target->snumber;
1999 566 : arcs[arcIndex].colorTrgm = ctrgm->cnumber;
3652 2000 566 : arcIndex++;
2001 : }
2002 : }
3652 tgl 2003 ECB : }
2004 :
2005 : /* Sort arcs to ease duplicate detection */
3652 tgl 2006 CBC 53 : qsort(arcs, arcIndex, sizeof(TrgmPackArcInfo), packArcInfoCmp);
2007 :
3652 tgl 2008 ECB : /* We could have duplicates because states were merged. Remove them. */
29 tgl 2009 CBC 53 : if (arcIndex > 1)
2010 : {
2011 : /* p1 is probe point, p2 is last known non-duplicate. */
29 tgl 2012 ECB : TrgmPackArcInfo *p1,
2013 : *p2;
2014 :
29 tgl 2015 CBC 31 : p2 = arcs;
29 tgl 2016 GIC 546 : for (p1 = arcs + 1; p1 < arcs + arcIndex; p1++)
2017 : {
2018 515 : if (packArcInfoCmp(p1, p2) > 0)
29 tgl 2019 ECB : {
29 tgl 2020 GIC 509 : p2++;
2021 509 : *p2 = *p1;
29 tgl 2022 ECB : }
3652 2023 : }
29 tgl 2024 GIC 31 : arcsCount = (p2 - arcs) + 1;
3652 tgl 2025 ECB : }
29 2026 : else
29 tgl 2027 GIC 22 : arcsCount = arcIndex;
3652 tgl 2028 ECB :
2029 : /* Create packed representation */
2030 : result = (TrgmPackedGraph *)
3652 tgl 2031 CBC 53 : MemoryContextAlloc(rcontext, sizeof(TrgmPackedGraph));
2032 :
3652 tgl 2033 ECB : /* Pack color trigrams information */
3652 tgl 2034 GIC 53 : result->colorTrigramsCount = 0;
3652 tgl 2035 CBC 328 : for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
3652 tgl 2036 ECB : {
3652 tgl 2037 GIC 275 : if (trgmNFA->colorTrgms[i].expanded)
2038 160 : result->colorTrigramsCount++;
2039 : }
2040 53 : result->colorTrigramGroups = (int *)
3652 tgl 2041 CBC 53 : MemoryContextAlloc(rcontext, sizeof(int) * result->colorTrigramsCount);
2042 53 : j = 0;
2043 328 : for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
2044 : {
2045 275 : if (trgmNFA->colorTrgms[i].expanded)
3652 tgl 2046 ECB : {
3652 tgl 2047 CBC 160 : result->colorTrigramGroups[j] = trgmNFA->colorTrgms[i].count;
3652 tgl 2048 GIC 160 : j++;
3652 tgl 2049 ECB : }
2050 : }
2051 :
2052 : /* Pack states and arcs information */
2186 tgl 2053 GIC 53 : result->statesCount = snumber;
3652 tgl 2054 CBC 53 : result->states = (TrgmPackedState *)
2186 2055 53 : MemoryContextAlloc(rcontext, snumber * sizeof(TrgmPackedState));
3652 tgl 2056 ECB : packedArcs = (TrgmPackedArc *)
3652 tgl 2057 CBC 53 : MemoryContextAlloc(rcontext, arcsCount * sizeof(TrgmPackedArc));
3652 tgl 2058 GIC 53 : j = 0;
2186 tgl 2059 CBC 595 : for (i = 0; i < snumber; i++)
2060 : {
3652 tgl 2061 GIC 542 : int cnt = 0;
2062 :
3652 tgl 2063 CBC 542 : result->states[i].arcs = &packedArcs[j];
2064 1102 : while (j < arcsCount && arcs[j].sourceState == i)
3652 tgl 2065 ECB : {
3652 tgl 2066 CBC 560 : packedArcs[j].targetState = arcs[j].targetState;
2067 560 : packedArcs[j].colorTrgm = arcs[j].colorTrgm;
2068 560 : cnt++;
3652 tgl 2069 GIC 560 : j++;
3652 tgl 2070 ECB : }
3652 tgl 2071 GIC 542 : result->states[i].arcsCount = cnt;
2072 : }
2073 :
2074 : /* Allocate working memory for trigramsMatchGraph() */
2075 53 : result->colorTrigramsActive = (bool *)
2076 53 : MemoryContextAlloc(rcontext, sizeof(bool) * result->colorTrigramsCount);
2077 53 : result->statesActive = (bool *)
2078 53 : MemoryContextAlloc(rcontext, sizeof(bool) * result->statesCount);
3652 tgl 2079 CBC 53 : result->statesQueue = (int *)
3652 tgl 2080 GIC 53 : MemoryContextAlloc(rcontext, sizeof(int) * result->statesCount);
3652 tgl 2081 ECB :
3652 tgl 2082 CBC 53 : return result;
2083 : }
3652 tgl 2084 ECB :
2085 : /*
2086 : * Comparison function for sorting TrgmPackArcInfos.
2087 : *
2088 : * Compares arcs in following order: sourceState, colorTrgm, targetState.
2089 : */
2090 : static int
3652 tgl 2091 CBC 4546 : packArcInfoCmp(const void *a1, const void *a2)
3652 tgl 2092 ECB : {
3652 tgl 2093 GBC 4546 : const TrgmPackArcInfo *p1 = (const TrgmPackArcInfo *) a1;
3652 tgl 2094 CBC 4546 : const TrgmPackArcInfo *p2 = (const TrgmPackArcInfo *) a2;
3652 tgl 2095 EUB :
3652 tgl 2096 CBC 4546 : if (p1->sourceState < p2->sourceState)
3652 tgl 2097 GIC 2179 : return -1;
2098 2367 : if (p1->sourceState > p2->sourceState)
2099 2050 : return 1;
2100 317 : if (p1->colorTrgm < p2->colorTrgm)
2101 198 : return -1;
2102 119 : if (p1->colorTrgm > p2->colorTrgm)
2103 107 : return 1;
2104 12 : if (p1->targetState < p2->targetState)
3652 tgl 2105 UIC 0 : return -1;
3652 tgl 2106 GIC 12 : if (p1->targetState > p2->targetState)
3652 tgl 2107 UIC 0 : return 1;
3652 tgl 2108 GIC 12 : 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 : {
2127 : StringInfoData buf;
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';
2182 : appendStringInfoString(&buf, s);
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 : {
2211 : StringInfoData buf;
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 : {
2287 : StringInfoData buf;
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 */
|
