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

Generated by: LCOV version 1.14