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

Generated by: LCOV version 1.13