trgm_regexp.c File Reference

#include "postgres.h"
#include "catalog/pg_collation_d.h"
#include "regex/regexport.h"
#include "trgm.h"
#include "tsearch/ts_locale.h"
#include "utils/formatting.h"
#include "utils/hsearch.h"
#include "utils/memutils.h"
#include "varatt.h"

Include dependency graph for trgm_regexp.c:

Go to the source code of this file.

Data Structures
struct	trgm_mb_char
struct	TrgmColorInfo
struct	TrgmPrefix
struct	ColorTrgm
struct	TrgmStateKey
struct	TrgmState
struct	TrgmArc
struct	TrgmArcInfo
struct	ColorTrgmInfo
struct	TrgmNFA
struct	TrgmPackedArc
struct	TrgmPackedState
struct	TrgmPackedGraph
struct	TrgmPackArcInfo

Macros
#define	MAX_EXPANDED_STATES   128
#define	MAX_EXPANDED_ARCS   1024
#define	MAX_TRGM_COUNT   256
#define	WISH_TRGM_PENALTY   16
#define	COLOR_COUNT_LIMIT   256
#define	COLOR_UNKNOWN   (-3)
#define	COLOR_BLANK   (-4)
#define	TSTATE_INIT   0x01 /* flag indicating this state is initial */
#define	TSTATE_FIN   0x02 /* flag indicating this state is final */

Typedefs
typedef int	TrgmColor
typedef struct TrgmState	TrgmState

Functions
static TRGM *	createTrgmNFAInternal (regex_t *regex, TrgmPackedGraph **graph, MemoryContext rcontext)
static void	RE_compile (regex_t *regex, text *text_re, int cflags, Oid collation)
static void	getColorInfo (regex_t *regex, TrgmNFA *trgmNFA)
static int	convertPgWchar (pg_wchar c, trgm_mb_char *result)
static void	transformGraph (TrgmNFA *trgmNFA)
static void	processState (TrgmNFA *trgmNFA, TrgmState *state)
static void	addKey (TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key)
static void	addKeyToQueue (TrgmNFA *trgmNFA, TrgmStateKey *key)
static void	addArcs (TrgmNFA *trgmNFA, TrgmState *state)
static void	addArc (TrgmNFA *trgmNFA, TrgmState *state, TrgmStateKey *key, TrgmColor co, TrgmStateKey *destKey)
static bool	validArcLabel (TrgmStateKey *key, TrgmColor co)
static TrgmState *	getState (TrgmNFA *trgmNFA, TrgmStateKey *key)
static bool	prefixContains (TrgmPrefix *prefix1, TrgmPrefix *prefix2)
static bool	selectColorTrigrams (TrgmNFA *trgmNFA)
static TRGM *	expandColorTrigrams (TrgmNFA *trgmNFA, MemoryContext rcontext)
static void	fillTrgm (trgm *ptrgm, trgm_mb_char s[3])
static void	mergeStates (TrgmState *state1, TrgmState *state2)
static int	colorTrgmInfoCmp (const void *p1, const void *p2)
static int	colorTrgmInfoPenaltyCmp (const void *p1, const void *p2)
static TrgmPackedGraph *	packGraph (TrgmNFA *trgmNFA, MemoryContext rcontext)
static int	packArcInfoCmp (const void *a1, const void *a2)
TRGM *	createTrgmNFA (text *text_re, Oid collation, TrgmPackedGraph **graph, MemoryContext rcontext)
bool	trigramsMatchGraph (TrgmPackedGraph *graph, bool *check)

Variables
static const float4	penalties [8]

Macro Definition Documentation

COLOR_BLANK

#define COLOR_BLANK   (-4)

Definition at line 289 of file trgm_regexp.c.

COLOR_COUNT_LIMIT

#define COLOR_COUNT_LIMIT   256

Definition at line 225 of file trgm_regexp.c.

COLOR_UNKNOWN

#define COLOR_UNKNOWN   (-3)

Definition at line 288 of file trgm_regexp.c.

MAX_EXPANDED_ARCS

#define MAX_EXPANDED_ARCS   1024

Definition at line 222 of file trgm_regexp.c.

MAX_EXPANDED_STATES

#define MAX_EXPANDED_STATES   128

Definition at line 221 of file trgm_regexp.c.

MAX_TRGM_COUNT

#define MAX_TRGM_COUNT   256

Definition at line 223 of file trgm_regexp.c.

TSTATE_FIN

#define TSTATE_FIN   0x02 /* flag indicating this state is final */

Definition at line 332 of file trgm_regexp.c.

TSTATE_INIT

#define TSTATE_INIT   0x01 /* flag indicating this state is initial */

Definition at line 331 of file trgm_regexp.c.

WISH_TRGM_PENALTY

#define WISH_TRGM_PENALTY   16

Definition at line 224 of file trgm_regexp.c.

Typedef Documentation

TrgmColor

typedef int TrgmColor

Definition at line 285 of file trgm_regexp.c.

TrgmState

typedef struct TrgmState TrgmState

Function Documentation

addArc()

static void addArc ( TrgmNFA *  trgmNFA, TrgmState *  state, TrgmStateKey *  key, TrgmColor  co, TrgmStateKey *  destKey  )

static

Definition at line 1290 of file trgm_regexp.c.

{
    TrgmArc    *arc;
    ListCell   *cell;
 
    /* Do nothing if this wouldn't be a valid arc label trigram */
    if (!validArcLabel(key, co))
        return;
 
    /*
     * Check if we are going to reach key which is covered by a key which is
     * already listed in this state.  If so arc is useless: the NFA can bypass
     * it through a path that doesn't require any predictable trigram, so
     * whether the arc's trigram is present or not doesn't really matter.
     */
    foreach(cell, state->enterKeys)
    {
        TrgmStateKey *existingKey = (TrgmStateKey *) lfirst(cell);
 
        if (existingKey->nstate == destKey->nstate &&
            prefixContains(&existingKey->prefix, &destKey->prefix))
            return;
    }
 
    /* Checks were successful, add new arc */
    arc = palloc_object(TrgmArc);
    arc->target = getState(trgmNFA, destKey);
    arc->ctrgm.colors[0] = key->prefix.colors[0];
    arc->ctrgm.colors[1] = key->prefix.colors[1];
    arc->ctrgm.colors[2] = co;
 
    state->arcs = lappend(state->arcs, arc);
    trgmNFA->arcsCount++;
}

References fb(), getState(), lappend(), lfirst, palloc_object, prefixContains(), and validArcLabel().

Referenced by addArcs().

addArcs()

static void addArcs ( TrgmNFA *  trgmNFA, TrgmState *  state  )

static

Definition at line 1192 of file trgm_regexp.c.

{
    TrgmStateKey destKey;
    ListCell   *cell;
    regex_arc_t *arcs;
    int         arcsCount,
                i;
 
    /*
     * Ensure any pad bytes in destKey are zero, since it may get used as a
     * hashtable key by getState.
     */
    MemSet(&destKey, 0, sizeof(destKey));
 
    /*
     * Iterate over enter keys associated with this expanded-graph state. This
     * includes both the state's own stateKey, and any enter keys we added to
     * it during addKey (which represent expanded-graph states that are not
     * distinguishable from this one by means of trigrams).  For each such
     * enter key, examine all the out-arcs of the key's underlying NFA state,
     * and try to make a trigram arc leading to where the out-arc leads.
     * (addArc will deal with whether the arc is valid or not.)
     */
    foreach(cell, state->enterKeys)
    {
        TrgmStateKey *key = (TrgmStateKey *) lfirst(cell);
 
        arcsCount = pg_reg_getnumoutarcs(trgmNFA->regex, key->nstate);
        arcs = palloc_array(regex_arc_t, arcsCount);
        pg_reg_getoutarcs(trgmNFA->regex, key->nstate, arcs, arcsCount);
 
        for (i = 0; i < arcsCount; i++)
        {
            regex_arc_t *arc = &arcs[i];
            TrgmColorInfo *colorInfo;
 
            /*
             * Ignore non-expandable colors; addKey already handled the case.
             *
             * We need no special check for WHITE or begin/end pseudocolors
             * here.  We don't need to do any processing for them, and they
             * will be marked non-expandable since the regex engine will have
             * reported them that way.  We do have to watch out for RAINBOW,
             * which has a negative color number.
             */
            if (arc->co < 0)
                continue;
            Assert(arc->co < trgmNFA->ncolors);
 
            colorInfo = &trgmNFA->colorInfo[arc->co];
            if (!colorInfo->expandable)
                continue;
 
            if (colorInfo->containsNonWord)
            {
                /*
                 * Color includes non-word character(s).
                 *
                 * Generate an arc, treating this transition as occurring on
                 * BLANK.  This allows word-ending trigrams to be manufactured
                 * if possible.
                 */
                destKey.prefix.colors[0] = key->prefix.colors[1];
                destKey.prefix.colors[1] = COLOR_BLANK;
                destKey.nstate = arc->to;
 
                addArc(trgmNFA, state, key, COLOR_BLANK, &destKey);
            }
 
            if (colorInfo->wordCharsCount > 0)
            {
                /*
                 * Color includes word character(s).
                 *
                 * Generate an arc.  Color is pushed into prefix of target
                 * state.
                 */
                destKey.prefix.colors[0] = key->prefix.colors[1];
                destKey.prefix.colors[1] = arc->co;
                destKey.nstate = arc->to;
 
                addArc(trgmNFA, state, key, arc->co, &destKey);
            }
        }
 
        pfree(arcs);
    }
}

References addArc(), Assert, arc::co, COLOR_BLANK, TrgmColorInfo::containsNonWord, TrgmColorInfo::expandable, fb(), i, lfirst, MemSet, palloc_array, pfree(), pg_reg_getnumoutarcs(), pg_reg_getoutarcs(), arc::to, and TrgmColorInfo::wordCharsCount.

Referenced by processState().

addKey()

static void addKey ( TrgmNFA *  trgmNFA, TrgmState *  state, TrgmStateKey *  key  )

static

Definition at line 1011 of file trgm_regexp.c.

{
    regex_arc_t *arcs;
    TrgmStateKey destKey;
    ListCell   *cell;
    int         i,
                arcsCount;
 
    /*
     * Ensure any pad bytes in destKey are zero, since it may get used as a
     * hashtable key by getState.
     */
    MemSet(&destKey, 0, sizeof(destKey));
 
    /*
     * Compare key to each existing enter key of the state to check for
     * redundancy.  We can drop either old key(s) or the new key if we find
     * redundancy.
     */
    foreach(cell, state->enterKeys)
    {
        TrgmStateKey *existingKey = (TrgmStateKey *) lfirst(cell);
 
        if (existingKey->nstate == key->nstate)
        {
            if (prefixContains(&existingKey->prefix, &key->prefix))
            {
                /* This old key already covers the new key. Nothing to do */
                return;
            }
            if (prefixContains(&key->prefix, &existingKey->prefix))
            {
                /*
                 * The new key covers this old key. Remove the old key, it's
                 * no longer needed once we add this key to the list.
                 */
                state->enterKeys = foreach_delete_current(state->enterKeys,
                                                          cell);
            }
        }
    }
 
    /* No redundancy, so add this key to the state's list */
    state->enterKeys = lappend(state->enterKeys, key);
 
    /* If state is now known final, mark it and we're done */
    if (key->nstate == pg_reg_getfinalstate(trgmNFA->regex))
    {
        state->flags |= TSTATE_FIN;
        return;
    }
 
    /*
     * Loop through all outgoing arcs of the corresponding state in the
     * original NFA.
     */
    arcsCount = pg_reg_getnumoutarcs(trgmNFA->regex, key->nstate);
    arcs = palloc_array(regex_arc_t, arcsCount);
    pg_reg_getoutarcs(trgmNFA->regex, key->nstate, arcs, arcsCount);
 
    for (i = 0; i < arcsCount; i++)
    {
        regex_arc_t *arc = &arcs[i];
 
        if (pg_reg_colorisbegin(trgmNFA->regex, arc->co))
        {
            /*
             * Start of line/string (^).  Trigram extraction treats start of
             * line same as start of word: double space prefix is added.
             * Hence, make an enter key showing we can reach the arc
             * destination with all-blank prefix.
             */
            destKey.prefix.colors[0] = COLOR_BLANK;
            destKey.prefix.colors[1] = COLOR_BLANK;
            destKey.nstate = arc->to;
 
            /* Add enter key to this state */
            addKeyToQueue(trgmNFA, &destKey);
        }
        else if (pg_reg_colorisend(trgmNFA->regex, arc->co))
        {
            /*
             * End of line/string ($).  We must consider this arc as a
             * transition that doesn't read anything.  The reason for adding
             * this enter key to the state is that if the arc leads to the
             * NFA's final state, we must mark this expanded state as final.
             */
            destKey.prefix.colors[0] = COLOR_UNKNOWN;
            destKey.prefix.colors[1] = COLOR_UNKNOWN;
            destKey.nstate = arc->to;
 
            /* Add enter key to this state */
            addKeyToQueue(trgmNFA, &destKey);
        }
        else if (arc->co >= 0)
        {
            /* Regular color (including WHITE) */
            TrgmColorInfo *colorInfo = &trgmNFA->colorInfo[arc->co];
 
            if (colorInfo->expandable)
            {
                if (colorInfo->containsNonWord &&
                    !validArcLabel(key, COLOR_BLANK))
                {
                    /*
                     * We can reach the arc destination after reading a
                     * non-word character, but the prefix is not something
                     * that addArc will accept with COLOR_BLANK, so no trigram
                     * arc can get made for this transition.  We must make an
                     * enter key to show that the arc destination is
                     * reachable.  Set it up with an all-blank prefix, since
                     * that corresponds to what the trigram extraction code
                     * will do at a word starting boundary.
                     */
                    destKey.prefix.colors[0] = COLOR_BLANK;
                    destKey.prefix.colors[1] = COLOR_BLANK;
                    destKey.nstate = arc->to;
                    addKeyToQueue(trgmNFA, &destKey);
                }
 
                if (colorInfo->wordCharsCount > 0 &&
                    !validArcLabel(key, arc->co))
                {
                    /*
                     * We can reach the arc destination after reading a word
                     * character, but the prefix is not something that addArc
                     * will accept, so no trigram arc can get made for this
                     * transition.  We must make an enter key to show that the
                     * arc destination is reachable.  The prefix for the enter
                     * key should reflect the info we have for this arc.
                     */
                    destKey.prefix.colors[0] = key->prefix.colors[1];
                    destKey.prefix.colors[1] = arc->co;
                    destKey.nstate = arc->to;
                    addKeyToQueue(trgmNFA, &destKey);
                }
            }
            else
            {
                /*
                 * Unexpandable color.  Add enter key with ambiguous prefix,
                 * showing we can reach the destination from this state, but
                 * the preceding colors will be uncertain.  (We do not set the
                 * first prefix color to key->prefix.colors[1], because a
                 * prefix of known followed by unknown is invalid.)
                 */
                destKey.prefix.colors[0] = COLOR_UNKNOWN;
                destKey.prefix.colors[1] = COLOR_UNKNOWN;
                destKey.nstate = arc->to;
                addKeyToQueue(trgmNFA, &destKey);
            }
        }
        else
        {
            /* RAINBOW: treat as unexpandable color */
            destKey.prefix.colors[0] = COLOR_UNKNOWN;
            destKey.prefix.colors[1] = COLOR_UNKNOWN;
            destKey.nstate = arc->to;
            addKeyToQueue(trgmNFA, &destKey);
        }
    }
 
    pfree(arcs);
}

References addKeyToQueue(), arc::co, COLOR_BLANK, COLOR_UNKNOWN, TrgmColorInfo::containsNonWord, TrgmColorInfo::expandable, fb(), foreach_delete_current, i, lappend(), lfirst, MemSet, palloc_array, pfree(), pg_reg_colorisbegin(), pg_reg_colorisend(), pg_reg_getfinalstate(), pg_reg_getnumoutarcs(), pg_reg_getoutarcs(), prefixContains(), arc::to, TSTATE_FIN, validArcLabel(), and TrgmColorInfo::wordCharsCount.

Referenced by processState().

addKeyToQueue()

static void addKeyToQueue ( TrgmNFA *  trgmNFA, TrgmStateKey *  key  )

static

Definition at line 1180 of file trgm_regexp.c.

{
    TrgmStateKey *keyCopy = palloc_object(TrgmStateKey);
 
    memcpy(keyCopy, key, sizeof(TrgmStateKey));
    trgmNFA->keysQueue = lappend(trgmNFA->keysQueue, keyCopy);
}

References fb(), lappend(), and palloc_object.

Referenced by addKey().

colorTrgmInfoCmp()

static int colorTrgmInfoCmp ( const void *  p1, const void *  p2  )

static

Definition at line 1896 of file trgm_regexp.c.

{
    const ColorTrgmInfo *c1 = (const ColorTrgmInfo *) p1;
    const ColorTrgmInfo *c2 = (const ColorTrgmInfo *) p2;
 
    return memcmp(&c1->ctrgm, &c2->ctrgm, sizeof(ColorTrgm));
}

References fb().

Referenced by packGraph(), and selectColorTrigrams().

colorTrgmInfoPenaltyCmp()

static int colorTrgmInfoPenaltyCmp ( const void *  p1, const void *  p2  )

static

Definition at line 1909 of file trgm_regexp.c.

{
    float4      penalty1 = ((const ColorTrgmInfo *) p1)->penalty;
    float4      penalty2 = ((const ColorTrgmInfo *) p2)->penalty;
 
    if (penalty1 < penalty2)
        return 1;
    else if (penalty1 == penalty2)
        return 0;
    else
        return -1;
}

References fb().

Referenced by selectColorTrigrams().

convertPgWchar()

static int convertPgWchar ( pg_wchar  c, trgm_mb_char *  result  )

static

Definition at line 830 of file trgm_regexp.c.

{
    /* "s" has enough space for a multibyte character and a trailing NUL */
    char        s[MAX_MULTIBYTE_CHAR_LEN + 1];
    int         clen;
 
    /*
     * We can ignore the NUL character, since it can never appear in a PG text
     * string.  This avoids the need for various special cases when
     * reconstructing trigrams.
     */
    if (c == 0)
        return 0;
 
    /* Do the conversion, making sure the result is NUL-terminated */
    memset(s, 0, sizeof(s));
    clen = pg_wchar2mb_with_len(&c, s, 1);
 
    /*
     * In IGNORECASE mode, we can ignore uppercase characters.  We assume that
     * the regex engine generated both uppercase and lowercase equivalents
     * within each color, since we used the REG_ICASE option; so there's no
     * need to process the uppercase version.
     *
     * XXX this code is dependent on the assumption that str_tolower() works
     * the same as the regex engine's internal case folding machinery.  Might
     * be wiser to expose pg_wc_tolower and test whether c ==
     * pg_wc_tolower(c). On the other hand, the trigrams in the index were
     * created using str_tolower(), so we're probably screwed if there's any
     * incompatibility anyway.
     */
#ifdef IGNORECASE
    {
        char       *lowerCased = str_tolower(s, clen, DEFAULT_COLLATION_OID);
 
        if (strcmp(lowerCased, s) != 0)
        {
            pfree(lowerCased);
            return 0;
        }
        pfree(lowerCased);
    }
#endif
 
    /* Fill result with exactly MAX_MULTIBYTE_CHAR_LEN bytes */
    memcpy(result->bytes, s, MAX_MULTIBYTE_CHAR_LEN);
    return clen;
}

References trgm_mb_char::bytes, fb(), MAX_MULTIBYTE_CHAR_LEN, pfree(), pg_wchar2mb_with_len(), and str_tolower().

Referenced by getColorInfo().

createTrgmNFA()

TRGM * createTrgmNFA	(	text *	text_re,
		Oid	collation,
		TrgmPackedGraph **	graph,
		MemoryContext	rcontext
	)

Definition at line 524 of file trgm_regexp.c.

{
    TRGM       *trg;
    regex_t     regex;
    MemoryContext tmpcontext;
    MemoryContext oldcontext;
 
    /*
     * This processing generates a great deal of cruft, which we'd like to
     * clean up before returning (since this function may be called in a
     * query-lifespan memory context).  Make a temp context we can work in so
     * that cleanup is easy.
     */
    tmpcontext = AllocSetContextCreate(CurrentMemoryContext,
                                       "createTrgmNFA temporary context",
                                       ALLOCSET_DEFAULT_SIZES);
    oldcontext = MemoryContextSwitchTo(tmpcontext);
 
    /*
     * Stage 1: Compile the regexp into a NFA, using the regexp library.
     */
#ifdef IGNORECASE
    RE_compile(&regex, text_re,
               REG_ADVANCED | REG_NOSUB | REG_ICASE, collation);
#else
    RE_compile(&regex, text_re,
               REG_ADVANCED | REG_NOSUB, collation);
#endif
 
    trg = createTrgmNFAInternal(&regex, graph, rcontext);
 
    /* Clean up all the cruft we created (including regex) */
    MemoryContextSwitchTo(oldcontext);
    MemoryContextDelete(tmpcontext);
 
    return trg;
}

References ALLOCSET_DEFAULT_SIZES, AllocSetContextCreate, createTrgmNFAInternal(), CurrentMemoryContext, fb(), MemoryContextDelete(), MemoryContextSwitchTo(), RE_compile(), REG_ADVANCED, REG_ICASE, REG_NOSUB, and regex_t.

Referenced by gin_extract_query_trgm(), and gtrgm_consistent().

createTrgmNFAInternal()

static TRGM * createTrgmNFAInternal ( regex_t *  regex, TrgmPackedGraph **  graph, MemoryContext  rcontext  )

static

Definition at line 567 of file trgm_regexp.c.

{
    TRGM       *trg;
    TrgmNFA     trgmNFA;
 
    trgmNFA.regex = regex;
 
    /* Collect color information from the regex */
    getColorInfo(regex, &trgmNFA);
 
#ifdef TRGM_REGEXP_DEBUG
    printSourceNFA(regex, trgmNFA.colorInfo, trgmNFA.ncolors);
#endif
 
    /*
     * Stage 2: Create an expanded graph from the source NFA.
     */
    transformGraph(&trgmNFA);
 
#ifdef TRGM_REGEXP_DEBUG
    printTrgmNFA(&trgmNFA);
#endif
 
    /*
     * Fail if we were unable to make a nontrivial graph, ie it is possible to
     * get from the initial state to the final state without reading any
     * predictable trigram.
     */
    if (trgmNFA.initState->flags & TSTATE_FIN)
        return NULL;
 
    /*
     * Stage 3: Select color trigrams to expand.  Fail if too many trigrams.
     */
    if (!selectColorTrigrams(&trgmNFA))
        return NULL;
 
    /*
     * Stage 4: Expand color trigrams and pack graph into final
     * representation.
     */
    trg = expandColorTrigrams(&trgmNFA, rcontext);
 
    *graph = packGraph(&trgmNFA, rcontext);
 
#ifdef TRGM_REGEXP_DEBUG
    printTrgmPackedGraph(*graph, trg);
#endif
 
    return trg;
}

References expandColorTrigrams(), fb(), getColorInfo(), packGraph(), TrgmNFA::regex, selectColorTrigrams(), transformGraph(), and TSTATE_FIN.

Referenced by createTrgmNFA().

expandColorTrigrams()

static TRGM * expandColorTrigrams ( TrgmNFA *  trgmNFA, MemoryContext  rcontext  )

static

Definition at line 1779 of file trgm_regexp.c.

{
    TRGM       *trg;
    trgm       *p;
    int         i;
    TrgmColorInfo blankColor;
    trgm_mb_char blankChar;
 
    /* Set up "blank" color structure containing a single zero character */
    memset(blankChar.bytes, 0, sizeof(blankChar.bytes));
    blankColor.wordCharsCount = 1;
    blankColor.wordChars = &blankChar;
 
    /* Construct the trgm array */
    trg = (TRGM *)
        MemoryContextAllocZero(rcontext,
                               TRGMHDRSIZE +
                               trgmNFA->totalTrgmCount * sizeof(trgm));
    trg->flag = ARRKEY;
    SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, trgmNFA->totalTrgmCount));
    p = GETARR(trg);
    for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
    {
        ColorTrgmInfo *colorTrgm = &trgmNFA->colorTrgms[i];
        TrgmColorInfo *c[3];
        trgm_mb_char s[3];
        int         j,
                    i1,
                    i2,
                    i3;
 
        /* Ignore any unexpanded trigrams ... */
        if (!colorTrgm->expanded)
            continue;
 
        /* Get colors, substituting the dummy struct for COLOR_BLANK */
        for (j = 0; j < 3; j++)
        {
            if (colorTrgm->ctrgm.colors[j] != COLOR_BLANK)
                c[j] = &trgmNFA->colorInfo[colorTrgm->ctrgm.colors[j]];
            else
                c[j] = &blankColor;
        }
 
        /* Iterate over all possible combinations of colors' characters */
        for (i1 = 0; i1 < c[0]->wordCharsCount; i1++)
        {
            s[0] = c[0]->wordChars[i1];
            for (i2 = 0; i2 < c[1]->wordCharsCount; i2++)
            {
                s[1] = c[1]->wordChars[i2];
                for (i3 = 0; i3 < c[2]->wordCharsCount; i3++)
                {
                    s[2] = c[2]->wordChars[i3];
                    fillTrgm(p, s);
                    p++;
                }
            }
        }
    }
 
    return trg;
}

References ARRKEY, CALCGTSIZE, COLOR_BLANK, ColorTrgm::colors, ColorTrgmInfo::ctrgm, ColorTrgmInfo::expanded, fb(), fillTrgm(), TRGM::flag, GETARR, i, j, MemoryContextAllocZero(), SET_VARSIZE(), and TRGMHDRSIZE.

Referenced by createTrgmNFAInternal().

fillTrgm()

static void fillTrgm ( trgm *  ptrgm, trgm_mb_char  s[3]  )

static

Definition at line 1847 of file trgm_regexp.c.

{
    char        str[3 * MAX_MULTIBYTE_CHAR_LEN],
               *p;
    int         i,
                j;
 
    /* Write multibyte string into "str" (we don't need null termination) */
    p = str;
 
    for (i = 0; i < 3; i++)
    {
        if (s[i].bytes[0] != 0)
        {
            for (j = 0; j < MAX_MULTIBYTE_CHAR_LEN && s[i].bytes[j]; j++)
                *p++ = s[i].bytes[j];
        }
        else
        {
            /* Emit a space in place of COLOR_BLANK */
            *p++ = ' ';
        }
    }
 
    /* Convert "str" to a standard trigram (possibly hashing it) */
    compact_trigram(ptrgm, str, p - str);
}

References trgm_mb_char::bytes, compact_trigram(), fb(), i, j, MAX_MULTIBYTE_CHAR_LEN, and str.

Referenced by expandColorTrigrams().

getColorInfo()

static void getColorInfo ( regex_t *  regex, TrgmNFA *  trgmNFA  )

static

Definition at line 765 of file trgm_regexp.c.

{
    int         colorsCount = pg_reg_getnumcolors(regex);
    int         i;
 
    trgmNFA->ncolors = colorsCount;
    trgmNFA->colorInfo = (TrgmColorInfo *)
        palloc0(colorsCount * sizeof(TrgmColorInfo));
 
    /*
     * Loop over colors, filling TrgmColorInfo about each.  Note we include
     * WHITE (0) even though we know it'll be reported as non-expandable.
     */
    for (i = 0; i < colorsCount; i++)
    {
        TrgmColorInfo *colorInfo = &trgmNFA->colorInfo[i];
        int         charsCount = pg_reg_getnumcharacters(regex, i);
        pg_wchar   *chars;
        int         j;
 
        if (charsCount < 0 || charsCount > COLOR_COUNT_LIMIT)
        {
            /* Non expandable, or too large to work with */
            colorInfo->expandable = false;
            continue;
        }
 
        colorInfo->expandable = true;
        colorInfo->containsNonWord = false;
        colorInfo->wordChars = palloc_array(trgm_mb_char, charsCount);
        colorInfo->wordCharsCount = 0;
 
        /* Extract all the chars in this color */
        chars = palloc_array(pg_wchar, charsCount);
        pg_reg_getcharacters(regex, i, chars, charsCount);
 
        /*
         * Convert characters back to multibyte form, and save only those that
         * are word characters.  Set "containsNonWord" if any non-word
         * character.  (Note: it'd probably be nicer to keep the chars in
         * pg_wchar format for now, but ISWORDCHR wants to see multibyte.)
         */
        for (j = 0; j < charsCount; j++)
        {
            trgm_mb_char c;
            int         clen = convertPgWchar(chars[j], &c);
 
            if (!clen)
                continue;       /* ok to ignore it altogether */
            if (ISWORDCHR(c.bytes, clen))
                colorInfo->wordChars[colorInfo->wordCharsCount++] = c;
            else
                colorInfo->containsNonWord = true;
        }
 
        pfree(chars);
    }
}

References chars, COLOR_COUNT_LIMIT, TrgmColorInfo::containsNonWord, convertPgWchar(), TrgmColorInfo::expandable, fb(), i, ISWORDCHR, j, palloc0(), palloc_array, pfree(), pg_reg_getcharacters(), pg_reg_getnumcharacters(), pg_reg_getnumcolors(), TrgmColorInfo::wordChars, and TrgmColorInfo::wordCharsCount.

Referenced by createTrgmNFAInternal().

getState()

static TrgmState * getState ( TrgmNFA *  trgmNFA, TrgmStateKey *  key  )

static

Definition at line 1387 of file trgm_regexp.c.

{
    TrgmState  *state;
    bool        found;
 
    state = (TrgmState *) hash_search(trgmNFA->states, key, HASH_ENTER,
                                      &found);
    if (!found)
    {
        /* New state: initialize and queue it */
        state->arcs = NIL;
        state->enterKeys = NIL;
        state->flags = 0;
        /* states are initially given negative numbers */
        state->snumber = -(++trgmNFA->nstates);
        state->parent = NULL;
        state->tentFlags = 0;
        state->tentParent = NULL;
 
        trgmNFA->queue = lappend(trgmNFA->queue, state);
    }
    return state;
}

References fb(), HASH_ENTER, hash_search(), lappend(), and NIL.

Referenced by addArc(), and transformGraph().

mergeStates()

static void mergeStates ( TrgmState *  state1, TrgmState *  state2  )

static

Definition at line 1879 of file trgm_regexp.c.

{
    Assert(state1 != state2);
    Assert(!state1->parent);
    Assert(!state2->parent);
 
    /* state1 absorbs state2's flags */
    state1->flags |= state2->flags;
 
    /* state2, and indirectly all its children, become children of state1 */
    state2->parent = state1;
}

References Assert, and fb().

Referenced by selectColorTrigrams().

packArcInfoCmp()

static int packArcInfoCmp ( const void *  a1, const void *  a2  )

static

Definition at line 2094 of file trgm_regexp.c.

{
    const TrgmPackArcInfo *p1 = (const TrgmPackArcInfo *) a1;
    const TrgmPackArcInfo *p2 = (const TrgmPackArcInfo *) a2;
 
    if (p1->sourceState < p2->sourceState)
        return -1;
    if (p1->sourceState > p2->sourceState)
        return 1;
    if (p1->colorTrgm < p2->colorTrgm)
        return -1;
    if (p1->colorTrgm > p2->colorTrgm)
        return 1;
    if (p1->targetState < p2->targetState)
        return -1;
    if (p1->targetState > p2->targetState)
        return 1;
    return 0;
}

References a1, a2, and fb().

Referenced by packGraph().

packGraph()

static TrgmPackedGraph * packGraph ( TrgmNFA *  trgmNFA, MemoryContext  rcontext  )

static

Definition at line 1934 of file trgm_regexp.c.

{
    int         snumber = 2,
                arcIndex,
                arcsCount;
    HASH_SEQ_STATUS scan_status;
    TrgmState  *state;
    TrgmPackArcInfo *arcs;
    TrgmPackedArc *packedArcs;
    TrgmPackedGraph *result;
    int         i,
                j;
 
    /* Enumerate surviving states, giving init and fin reserved numbers */
    hash_seq_init(&scan_status, trgmNFA->states);
    while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
    {
        while (state->parent)
            state = state->parent;
 
        if (state->snumber < 0)
        {
            if (state->flags & TSTATE_INIT)
                state->snumber = 0;
            else if (state->flags & TSTATE_FIN)
                state->snumber = 1;
            else
            {
                state->snumber = snumber;
                snumber++;
            }
        }
    }
 
    /* Collect array of all arcs */
    arcs = palloc_array(TrgmPackArcInfo, trgmNFA->arcsCount);
    arcIndex = 0;
    hash_seq_init(&scan_status, trgmNFA->states);
    while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
    {
        TrgmState  *source = state;
        ListCell   *cell;
 
        while (source->parent)
            source = source->parent;
 
        foreach(cell, state->arcs)
        {
            TrgmArc    *arc = (TrgmArc *) lfirst(cell);
            TrgmState  *target = arc->target;
 
            while (target->parent)
                target = target->parent;
 
            if (source->snumber != target->snumber)
            {
                ColorTrgmInfo *ctrgm;
 
                ctrgm = (ColorTrgmInfo *) bsearch(&arc->ctrgm,
                                                  trgmNFA->colorTrgms,
                                                  trgmNFA->colorTrgmsCount,
                                                  sizeof(ColorTrgmInfo),
                                                  colorTrgmInfoCmp);
                Assert(ctrgm != NULL);
                Assert(ctrgm->expanded);
 
                arcs[arcIndex].sourceState = source->snumber;
                arcs[arcIndex].targetState = target->snumber;
                arcs[arcIndex].colorTrgm = ctrgm->cnumber;
                arcIndex++;
            }
        }
    }
 
    /* Sort arcs to ease duplicate detection */
    qsort(arcs, arcIndex, sizeof(TrgmPackArcInfo), packArcInfoCmp);
 
    /* We could have duplicates because states were merged. Remove them. */
    if (arcIndex > 1)
    {
        /* p1 is probe point, p2 is last known non-duplicate. */
        TrgmPackArcInfo *p1,
                   *p2;
 
        p2 = arcs;
        for (p1 = arcs + 1; p1 < arcs + arcIndex; p1++)
        {
            if (packArcInfoCmp(p1, p2) > 0)
            {
                p2++;
                *p2 = *p1;
            }
        }
        arcsCount = (p2 - arcs) + 1;
    }
    else
        arcsCount = arcIndex;
 
    /* Create packed representation */
    result = (TrgmPackedGraph *)
        MemoryContextAlloc(rcontext, sizeof(TrgmPackedGraph));
 
    /* Pack color trigrams information */
    result->colorTrigramsCount = 0;
    for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
    {
        if (trgmNFA->colorTrgms[i].expanded)
            result->colorTrigramsCount++;
    }
    result->colorTrigramGroups = (int *)
        MemoryContextAlloc(rcontext, sizeof(int) * result->colorTrigramsCount);
    j = 0;
    for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
    {
        if (trgmNFA->colorTrgms[i].expanded)
        {
            result->colorTrigramGroups[j] = trgmNFA->colorTrgms[i].count;
            j++;
        }
    }
 
    /* Pack states and arcs information */
    result->statesCount = snumber;
    result->states = (TrgmPackedState *)
        MemoryContextAlloc(rcontext, snumber * sizeof(TrgmPackedState));
    packedArcs = (TrgmPackedArc *)
        MemoryContextAlloc(rcontext, arcsCount * sizeof(TrgmPackedArc));
    j = 0;
    for (i = 0; i < snumber; i++)
    {
        int         cnt = 0;
 
        result->states[i].arcs = &packedArcs[j];
        while (j < arcsCount && arcs[j].sourceState == i)
        {
            packedArcs[j].targetState = arcs[j].targetState;
            packedArcs[j].colorTrgm = arcs[j].colorTrgm;
            cnt++;
            j++;
        }
        result->states[i].arcsCount = cnt;
    }
 
    /* Allocate working memory for trigramsMatchGraph() */
    result->colorTrigramsActive = (bool *)
        MemoryContextAlloc(rcontext, sizeof(bool) * result->colorTrigramsCount);
    result->statesActive = (bool *)
        MemoryContextAlloc(rcontext, sizeof(bool) * result->statesCount);
    result->statesQueue = (int *)
        MemoryContextAlloc(rcontext, sizeof(int) * result->statesCount);
 
    return result;
}

References TrgmPackedState::arcs, TrgmPackedState::arcsCount, Assert, ColorTrgmInfo::cnumber, TrgmPackArcInfo::colorTrgm, colorTrgmInfoCmp(), TrgmPackedGraph::colorTrigramGroups, TrgmPackedGraph::colorTrigramsActive, TrgmPackedGraph::colorTrigramsCount, ColorTrgmInfo::expanded, fb(), hash_seq_init(), hash_seq_search(), i, j, lfirst, MemoryContextAlloc(), packArcInfoCmp(), palloc_array, TrgmState::parent, qsort, TrgmState::snumber, source, TrgmPackArcInfo::sourceState, TrgmPackedGraph::states, TrgmPackedGraph::statesActive, TrgmPackedGraph::statesCount, TrgmPackedGraph::statesQueue, TrgmPackedArc::targetState, TrgmPackArcInfo::targetState, TSTATE_FIN, and TSTATE_INIT.

Referenced by createTrgmNFAInternal().

prefixContains()

static bool prefixContains ( TrgmPrefix *  prefix1, TrgmPrefix *  prefix2  )

static

Definition at line 1418 of file trgm_regexp.c.

{
    if (prefix1->colors[1] == COLOR_UNKNOWN)
    {
        /* Fully ambiguous prefix contains everything */
        return true;
    }
    else if (prefix1->colors[0] == COLOR_UNKNOWN)
    {
        /*
         * Prefix with only first unknown color contains every prefix with
         * same second color.
         */
        if (prefix1->colors[1] == prefix2->colors[1])
            return true;
        else
            return false;
    }
    else
    {
        /* Exact prefix contains only the exact same prefix */
        if (prefix1->colors[0] == prefix2->colors[0] &&
            prefix1->colors[1] == prefix2->colors[1])
            return true;
        else
            return false;
    }
}

References COLOR_UNKNOWN, and fb().

Referenced by addArc(), and addKey().

processState()

static void processState ( TrgmNFA *  trgmNFA, TrgmState *  state  )

static

Definition at line 961 of file trgm_regexp.c.

{
    ListCell   *lc;
 
    /* keysQueue should be NIL already, but make sure */
    trgmNFA->keysQueue = NIL;
 
    /*
     * Add state's own key, and then process all keys added to keysQueue until
     * queue is finished.  But we can quit if the state gets marked final.
     */
    addKey(trgmNFA, state, &state->stateKey);
    foreach(lc, trgmNFA->keysQueue)
    {
        TrgmStateKey *key = (TrgmStateKey *) lfirst(lc);
 
        if (state->flags & TSTATE_FIN)
            break;
        addKey(trgmNFA, state, key);
    }
 
    /* Release keysQueue to clean up for next cycle */
    list_free(trgmNFA->keysQueue);
    trgmNFA->keysQueue = NIL;
 
    /*
     * Add outgoing arcs only if state isn't final (we have no interest in
     * outgoing arcs if we already match)
     */
    if (!(state->flags & TSTATE_FIN))
        addArcs(trgmNFA, state);
}

References addArcs(), addKey(), fb(), lfirst, list_free(), NIL, and TSTATE_FIN.

Referenced by transformGraph().

RE_compile()

static void RE_compile ( regex_t *  regex, text *  text_re, int  cflags, Oid  collation  )

static

Definition at line 721 of file trgm_regexp.c.

{
    int         text_re_len = VARSIZE_ANY_EXHDR(text_re);
    char       *text_re_val = VARDATA_ANY(text_re);
    pg_wchar   *pattern;
    int         pattern_len;
    int         regcomp_result;
    char        errMsg[100];
 
    /* Convert pattern string to wide characters */
    pattern = (pg_wchar *) palloc((text_re_len + 1) * sizeof(pg_wchar));
    pattern_len = pg_mb2wchar_with_len(text_re_val,
                                       pattern,
                                       text_re_len);
 
    /* Compile regex */
    regcomp_result = pg_regcomp(regex,
                                pattern,
                                pattern_len,
                                cflags,
                                collation);
 
    pfree(pattern);
 
    if (regcomp_result != REG_OKAY)
    {
        /* re didn't compile (no need for pg_regfree, if so) */
        pg_regerror(regcomp_result, regex, errMsg, sizeof(errMsg));
        ereport(ERROR,
                (errcode(ERRCODE_INVALID_REGULAR_EXPRESSION),
                 errmsg("invalid regular expression: %s", errMsg)));
    }
}

References ereport, errcode(), errmsg(), ERROR, fb(), palloc(), pfree(), pg_mb2wchar_with_len(), pg_regcomp(), pg_regerror(), REG_OKAY, VARDATA_ANY(), and VARSIZE_ANY_EXHDR().

Referenced by createTrgmNFA().

selectColorTrigrams()

static bool selectColorTrigrams ( TrgmNFA *  trgmNFA )

static

Definition at line 1460 of file trgm_regexp.c.

{
    HASH_SEQ_STATUS scan_status;
    int         arcsCount = trgmNFA->arcsCount,
                i;
    TrgmState  *state;
    ColorTrgmInfo *colorTrgms;
    int64       totalTrgmCount;
    float4      totalTrgmPenalty;
    int         cnumber;
 
    /* Collect color trigrams from all arcs */
    colorTrgms = palloc0_array(ColorTrgmInfo, arcsCount);
    trgmNFA->colorTrgms = colorTrgms;
 
    i = 0;
    hash_seq_init(&scan_status, trgmNFA->states);
    while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
    {
        ListCell   *cell;
 
        foreach(cell, state->arcs)
        {
            TrgmArc    *arc = (TrgmArc *) lfirst(cell);
            TrgmArcInfo *arcInfo = palloc_object(TrgmArcInfo);
            ColorTrgmInfo *trgmInfo = &colorTrgms[i];
 
            arcInfo->source = state;
            arcInfo->target = arc->target;
            trgmInfo->ctrgm = arc->ctrgm;
            trgmInfo->cnumber = -1;
            /* count and penalty will be set below */
            trgmInfo->expanded = true;
            trgmInfo->arcs = list_make1(arcInfo);
            i++;
        }
    }
    Assert(i == arcsCount);
 
    /* Remove duplicates, merging their arcs lists */
    if (arcsCount >= 2)
    {
        ColorTrgmInfo *p1,
                   *p2;
 
        /* Sort trigrams to ease duplicate detection */
        qsort(colorTrgms, arcsCount, sizeof(ColorTrgmInfo), colorTrgmInfoCmp);
 
        /* p1 is probe point, p2 is last known non-duplicate. */
        p2 = colorTrgms;
        for (p1 = colorTrgms + 1; p1 < colorTrgms + arcsCount; p1++)
        {
            if (colorTrgmInfoCmp(p1, p2) > 0)
            {
                p2++;
                *p2 = *p1;
            }
            else
            {
                p2->arcs = list_concat(p2->arcs, p1->arcs);
            }
        }
        trgmNFA->colorTrgmsCount = (p2 - colorTrgms) + 1;
    }
    else
    {
        trgmNFA->colorTrgmsCount = arcsCount;
    }
 
    /*
     * Count number of simple trigrams generated by each color trigram, and
     * also compute a penalty value, which is the number of simple trigrams
     * times a multiplier that depends on its whitespace content.
     *
     * Note: per-color-trigram counts cannot overflow an int so long as
     * COLOR_COUNT_LIMIT is not more than the cube root of INT_MAX, ie about
     * 1290.  However, the grand total totalTrgmCount might conceivably
     * overflow an int, so we use int64 for that within this routine.  Also,
     * penalties are calculated in float4 arithmetic to avoid any overflow
     * worries.
     */
    totalTrgmCount = 0;
    totalTrgmPenalty = 0.0f;
    for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
    {
        ColorTrgmInfo *trgmInfo = &colorTrgms[i];
        int         j,
                    count = 1,
                    typeIndex = 0;
 
        for (j = 0; j < 3; j++)
        {
            TrgmColor   c = trgmInfo->ctrgm.colors[j];
 
            typeIndex *= 2;
            if (c == COLOR_BLANK)
                typeIndex++;
            else
                count *= trgmNFA->colorInfo[c].wordCharsCount;
        }
        trgmInfo->count = count;
        totalTrgmCount += count;
        trgmInfo->penalty = penalties[typeIndex] * (float4) count;
        totalTrgmPenalty += trgmInfo->penalty;
    }
 
    /* Sort color trigrams in descending order of their penalties */
    qsort(colorTrgms, trgmNFA->colorTrgmsCount, sizeof(ColorTrgmInfo),
          colorTrgmInfoPenaltyCmp);
 
    /*
     * Remove color trigrams from the graph so long as total penalty of color
     * trigrams exceeds WISH_TRGM_PENALTY.  (If we fail to get down to
     * WISH_TRGM_PENALTY, it's OK so long as total count is no more than
     * MAX_TRGM_COUNT.)  We prefer to remove color trigrams with higher
     * penalty, since those are the most promising for reducing the total
     * penalty.  When removing a color trigram we have to merge states
     * connected by arcs labeled with that trigram.  It's necessary to not
     * merge initial and final states, because our graph becomes useless if
     * that happens; so we cannot always remove the trigram we'd prefer to.
     */
    for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
    {
        ColorTrgmInfo *trgmInfo = &colorTrgms[i];
        bool        canRemove = true;
        ListCell   *cell;
 
        /* Done if we've reached the target */
        if (totalTrgmPenalty <= WISH_TRGM_PENALTY)
            break;
 
#ifdef TRGM_REGEXP_DEBUG
        fprintf(stderr, "considering ctrgm %d %d %d, penalty %f, %d arcs\n",
                trgmInfo->ctrgm.colors[0],
                trgmInfo->ctrgm.colors[1],
                trgmInfo->ctrgm.colors[2],
                trgmInfo->penalty,
                list_length(trgmInfo->arcs));
#endif
 
        /*
         * Does any arc of this color trigram connect initial and final
         * states?  If so we can't remove it.
         */
        foreach(cell, trgmInfo->arcs)
        {
            TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell);
            TrgmState  *source = arcInfo->source,
                       *target = arcInfo->target;
            int         source_flags,
                        target_flags;
 
#ifdef TRGM_REGEXP_DEBUG
            fprintf(stderr, "examining arc to s%d (%x) from s%d (%x)\n",
                    -target->snumber, target->flags,
                    -source->snumber, source->flags);
#endif
 
            /* examine parent states, if any merging has already happened */
            while (source->parent)
                source = source->parent;
            while (target->parent)
                target = target->parent;
 
#ifdef TRGM_REGEXP_DEBUG
            fprintf(stderr, " ... after completed merges: to s%d (%x) from s%d (%x)\n",
                    -target->snumber, target->flags,
                    -source->snumber, source->flags);
#endif
 
            /* we must also consider merges we are planning right now */
            source_flags = source->flags | source->tentFlags;
            while (source->tentParent)
            {
                source = source->tentParent;
                source_flags |= source->flags | source->tentFlags;
            }
            target_flags = target->flags | target->tentFlags;
            while (target->tentParent)
            {
                target = target->tentParent;
                target_flags |= target->flags | target->tentFlags;
            }
 
#ifdef TRGM_REGEXP_DEBUG
            fprintf(stderr, " ... after tentative merges: to s%d (%x) from s%d (%x)\n",
                    -target->snumber, target_flags,
                    -source->snumber, source_flags);
#endif
 
            /* would fully-merged state have both INIT and FIN set? */
            if (((source_flags | target_flags) & (TSTATE_INIT | TSTATE_FIN)) ==
                (TSTATE_INIT | TSTATE_FIN))
            {
                canRemove = false;
                break;
            }
 
            /* ok so far, so remember planned merge */
            if (source != target)
            {
#ifdef TRGM_REGEXP_DEBUG
                fprintf(stderr, " ... tentatively merging s%d into s%d\n",
                        -target->snumber, -source->snumber);
#endif
                target->tentParent = source;
                source->tentFlags |= target_flags;
            }
        }
 
        /*
         * We must reset all the tentFlags/tentParent fields before
         * continuing.  tentFlags could only have become set in states that
         * are the source or parent or tentative parent of one of the current
         * arcs; likewise tentParent could only have become set in states that
         * are the target or parent or tentative parent of one of the current
         * arcs.  There might be some overlap between those sets, but if we
         * clear tentFlags in target states as well as source states, we
         * should be okay even if we visit a state as target before visiting
         * it as a source.
         */
        foreach(cell, trgmInfo->arcs)
        {
            TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell);
            TrgmState  *source = arcInfo->source,
                       *target = arcInfo->target;
            TrgmState  *ttarget;
 
            /* no need to touch previously-merged states */
            while (source->parent)
                source = source->parent;
            while (target->parent)
                target = target->parent;
 
            while (source)
            {
                source->tentFlags = 0;
                source = source->tentParent;
            }
 
            while ((ttarget = target->tentParent) != NULL)
            {
                target->tentParent = NULL;
                target->tentFlags = 0;  /* in case it was also a source */
                target = ttarget;
            }
        }
 
        /* Now, move on if we can't drop this trigram */
        if (!canRemove)
        {
#ifdef TRGM_REGEXP_DEBUG
            fprintf(stderr, " ... not ok to merge\n");
#endif
            continue;
        }
 
        /* OK, merge states linked by each arc labeled by the trigram */
        foreach(cell, trgmInfo->arcs)
        {
            TrgmArcInfo *arcInfo = (TrgmArcInfo *) lfirst(cell);
            TrgmState  *source = arcInfo->source,
                       *target = arcInfo->target;
 
            while (source->parent)
                source = source->parent;
            while (target->parent)
                target = target->parent;
            if (source != target)
            {
#ifdef TRGM_REGEXP_DEBUG
                fprintf(stderr, "merging s%d into s%d\n",
                        -target->snumber, -source->snumber);
#endif
                mergeStates(source, target);
                /* Assert we didn't merge initial and final states */
                Assert((source->flags & (TSTATE_INIT | TSTATE_FIN)) !=
                       (TSTATE_INIT | TSTATE_FIN));
            }
        }
 
        /* Mark trigram unexpanded, and update totals */
        trgmInfo->expanded = false;
        totalTrgmCount -= trgmInfo->count;
        totalTrgmPenalty -= trgmInfo->penalty;
    }
 
    /* Did we succeed in fitting into MAX_TRGM_COUNT? */
    if (totalTrgmCount > MAX_TRGM_COUNT)
        return false;
 
    trgmNFA->totalTrgmCount = (int) totalTrgmCount;
 
    /*
     * Sort color trigrams by colors (will be useful for bsearch in packGraph)
     * and enumerate the color trigrams that are expanded.
     */
    cnumber = 0;
    qsort(colorTrgms, trgmNFA->colorTrgmsCount, sizeof(ColorTrgmInfo),
          colorTrgmInfoCmp);
    for (i = 0; i < trgmNFA->colorTrgmsCount; i++)
    {
        if (colorTrgms[i].expanded)
        {
            colorTrgms[i].cnumber = cnumber;
            cnumber++;
        }
    }
 
    return true;
}

References ColorTrgmInfo::arcs, Assert, ColorTrgmInfo::cnumber, COLOR_BLANK, ColorTrgm::colors, colorTrgmInfoCmp(), colorTrgmInfoPenaltyCmp(), ColorTrgmInfo::ctrgm, fb(), fprintf, hash_seq_init(), hash_seq_search(), i, j, lfirst, list_concat(), list_length(), list_make1, MAX_TRGM_COUNT, mergeStates(), palloc0_array, palloc_object, penalties, qsort, source, TSTATE_FIN, TSTATE_INIT, and WISH_TRGM_PENALTY.

Referenced by createTrgmNFAInternal().

transformGraph()

static void transformGraph ( TrgmNFA *  trgmNFA )

static

Definition at line 897 of file trgm_regexp.c.

{
    HASHCTL     hashCtl;
    TrgmStateKey initkey;
    TrgmState  *initstate;
    ListCell   *lc;
 
    /* Initialize this stage's workspace in trgmNFA struct */
    trgmNFA->queue = NIL;
    trgmNFA->keysQueue = NIL;
    trgmNFA->arcsCount = 0;
    trgmNFA->overflowed = false;
 
    /* Create hashtable for states */
    hashCtl.keysize = sizeof(TrgmStateKey);
    hashCtl.entrysize = sizeof(TrgmState);
    hashCtl.hcxt = CurrentMemoryContext;
    trgmNFA->states = hash_create("Trigram NFA",
                                  1024,
                                  &hashCtl,
                                  HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
    trgmNFA->nstates = 0;
 
    /* Create initial state: ambiguous prefix, NFA's initial state */
    MemSet(&initkey, 0, sizeof(initkey));
    initkey.prefix.colors[0] = COLOR_UNKNOWN;
    initkey.prefix.colors[1] = COLOR_UNKNOWN;
    initkey.nstate = pg_reg_getinitialstate(trgmNFA->regex);
 
    initstate = getState(trgmNFA, &initkey);
    initstate->flags |= TSTATE_INIT;
    trgmNFA->initState = initstate;
 
    /*
     * Recursively build the expanded graph by processing queue of states
     * (breadth-first search).  getState already put initstate in the queue.
     * Note that getState will append new states to the queue within the loop,
     * too; this works as long as we don't do repeat fetches using the "lc"
     * pointer.
     */
    foreach(lc, trgmNFA->queue)
    {
        TrgmState  *state = (TrgmState *) lfirst(lc);
 
        /*
         * If we overflowed then just mark state as final.  Otherwise do
         * actual processing.
         */
        if (trgmNFA->overflowed)
            state->flags |= TSTATE_FIN;
        else
            processState(trgmNFA, state);
 
        /* Did we overflow? */
        if (trgmNFA->arcsCount > MAX_EXPANDED_ARCS ||
            hash_get_num_entries(trgmNFA->states) > MAX_EXPANDED_STATES)
            trgmNFA->overflowed = true;
    }
}

References COLOR_UNKNOWN, CurrentMemoryContext, fb(), TrgmState::flags, getState(), HASH_BLOBS, HASH_CONTEXT, hash_create(), HASH_ELEM, hash_get_num_entries(), lfirst, MAX_EXPANDED_ARCS, MAX_EXPANDED_STATES, MemSet, NIL, pg_reg_getinitialstate(), processState(), TSTATE_FIN, and TSTATE_INIT.

Referenced by createTrgmNFAInternal().

trigramsMatchGraph()

bool trigramsMatchGraph	(	TrgmPackedGraph *	graph,
		bool *	check
	)

Definition at line 628 of file trgm_regexp.c.

{
    int         i,
                j,
                k,
                queueIn,
                queueOut;
 
    /*
     * Reset temporary working areas.
     */
    memset(graph->colorTrigramsActive, 0,
           sizeof(bool) * graph->colorTrigramsCount);
    memset(graph->statesActive, 0, sizeof(bool) * graph->statesCount);
 
    /*
     * Check which color trigrams were matched.  A match for any simple
     * trigram associated with a color trigram counts as a match of the color
     * trigram.
     */
    j = 0;
    for (i = 0; i < graph->colorTrigramsCount; i++)
    {
        int         cnt = graph->colorTrigramGroups[i];
 
        for (k = j; k < j + cnt; k++)
        {
            if (check[k])
            {
                /*
                 * Found one matched trigram in the group. Can skip the rest
                 * of them and go to the next group.
                 */
                graph->colorTrigramsActive[i] = true;
                break;
            }
        }
        j = j + cnt;
    }
 
    /*
     * Initialize the statesQueue to hold just the initial state.  Note:
     * statesQueue has room for statesCount entries, which is certainly enough
     * since no state will be put in the queue more than once. The
     * statesActive array marks which states have been queued.
     */
    graph->statesActive[0] = true;
    graph->statesQueue[0] = 0;
    queueIn = 0;
    queueOut = 1;
 
    /* Process queued states as long as there are any. */
    while (queueIn < queueOut)
    {
        int         stateno = graph->statesQueue[queueIn++];
        TrgmPackedState *state = &graph->states[stateno];
        int         cnt = state->arcsCount;
 
        /* Loop over state's out-arcs */
        for (i = 0; i < cnt; i++)
        {
            TrgmPackedArc *arc = &state->arcs[i];
 
            /*
             * If corresponding color trigram is present then activate the
             * corresponding state.  We're done if that's the final state,
             * otherwise queue the state if it's not been queued already.
             */
            if (graph->colorTrigramsActive[arc->colorTrgm])
            {
                int         nextstate = arc->targetState;
 
                if (nextstate == 1)
                    return true;    /* success: final state is reachable */
 
                if (!graph->statesActive[nextstate])
                {
                    graph->statesActive[nextstate] = true;
                    graph->statesQueue[queueOut++] = nextstate;
                }
            }
        }
    }
 
    /* Queue is empty, so match fails. */
    return false;
}

References TrgmPackedGraph::colorTrigramGroups, TrgmPackedGraph::colorTrigramsActive, TrgmPackedGraph::colorTrigramsCount, fb(), i, j, TrgmPackedGraph::states, TrgmPackedGraph::statesActive, TrgmPackedGraph::statesCount, and TrgmPackedGraph::statesQueue.

Referenced by gin_trgm_consistent(), gin_trgm_triconsistent(), and gtrgm_consistent().

validArcLabel()

static bool validArcLabel ( TrgmStateKey *  key, TrgmColor  co  )

static

Definition at line 1332 of file trgm_regexp.c.

{
    /*
     * We have to know full trigram in order to add outgoing arc.  So we can't
     * do it if prefix is ambiguous.
     */
    if (key->prefix.colors[0] == COLOR_UNKNOWN)
        return false;
 
    /* If key->prefix.colors[0] isn't unknown, its second color isn't either */
    Assert(key->prefix.colors[1] != COLOR_UNKNOWN);
    /* And we should not be called with an unknown arc color anytime */
    Assert(co != COLOR_UNKNOWN);
 
    /*
     * We don't bother with making arcs representing three non-word
     * characters, since that's useless for trigram extraction.
     */
    if (key->prefix.colors[0] == COLOR_BLANK &&
        key->prefix.colors[1] == COLOR_BLANK &&
        co == COLOR_BLANK)
        return false;
 
    /*
     * We also reject nonblank-blank-anything.  The nonblank-blank-nonblank
     * case doesn't correspond to any trigram the trigram extraction code
     * would make.  The nonblank-blank-blank case is also not possible with
     * RPADDING = 1.  (Note that in many cases we'd fail to generate such a
     * trigram even if it were valid, for example processing "foo bar" will
     * not result in considering the trigram "o  ".  So if you want to support
     * RPADDING = 2, there's more to do than just twiddle this test.)
     */
    if (key->prefix.colors[0] != COLOR_BLANK &&
        key->prefix.colors[1] == COLOR_BLANK)
        return false;
 
    /*
     * Other combinations involving blank are valid, in particular we assume
     * blank-blank-nonblank is valid, which presumes that LPADDING is 2.
     *
     * Note: Using again the example "foo bar", we will not consider the
     * trigram "  b", though this trigram would be found by the trigram
     * extraction code.  Since we will find " ba", it doesn't seem worth
     * trying to hack the algorithm to generate the additional trigram.
     */
 
    /* arc label is valid */
    return true;
}

References Assert, COLOR_BLANK, and COLOR_UNKNOWN.

Referenced by addArc(), and addKey().

Variable Documentation

penalties

const float4 penalties[8]

static

Initial value:

= {
    1.0f,                       
    3.5f,                       
    0.0f,                       
    0.0f,                       
    4.2f,                       
    2.1f,                       
    25.0f,                      
    0.0f                        
}

Definition at line 231 of file trgm_regexp.c.

                                   {
    1.0f,                       /* "aaa" */
    3.5f,                       /* "aa " */
    0.0f,                       /* "a a" (impossible) */
    0.0f,                       /* "a  " (impossible) */
    4.2f,                       /* " aa" */
    2.1f,                       /* " a " */
    25.0f,                      /* "  a" */
    0.0f                        /* "   " (impossible) */
};

Referenced by selectColorTrigrams().