LCOV - code coverage report
Current view: top level - contrib/pg_trgm - trgm_regexp.c (source / functions) Hit Total Coverage
Test: PostgreSQL 12beta2 Lines: 518 526 98.5 %
Date: 2019-06-19 16:07:09 Functions: 23 23 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13