diff --git a/contrib/pg_trgm/Makefile b/contrib/pg_trgm/Makefile
index 64fd69f..8033733 100644
--- a/contrib/pg_trgm/Makefile
+++ b/contrib/pg_trgm/Makefile
@@ -1,7 +1,7 @@
# contrib/pg_trgm/Makefile
MODULE_big = pg_trgm
-OBJS = trgm_op.o trgm_gist.o trgm_gin.o
+OBJS = trgm_op.o trgm_gist.o trgm_gin.o trgm_regexp.o
EXTENSION = pg_trgm
DATA = pg_trgm--1.0.sql pg_trgm--unpackaged--1.0.sql
diff --git a/contrib/pg_trgm/expected/pg_trgm.out b/contrib/pg_trgm/expected/pg_trgm.out
index 81d0ca8..ee0131f 100644
--- a/contrib/pg_trgm/expected/pg_trgm.out
+++ b/contrib/pg_trgm/expected/pg_trgm.out
@@ -54,7 +54,7 @@ select similarity('wow',' WOW ');
(1 row)
CREATE TABLE test_trgm(t text);
-\copy test_trgm from 'data/trgm.data
+\copy test_trgm from 'data/trgm.data'
select t,similarity(t,'qwertyu0988') as sml from test_trgm where t % 'qwertyu0988' order by sml desc, t;
t | sml
-------------+----------
@@ -3515,6 +3515,47 @@ select * from test2 where t ilike 'qua%';
quark
(1 row)
+select * from test2 where t ~ '[abc]{3}';
+ t
+--------
+ abcdef
+(1 row)
+
+select * from test2 where t ~ 'a[bc]+d';
+ t
+--------
+ abcdef
+(1 row)
+
+select * from test2 where t ~* 'DEF';
+ t
+--------
+ abcdef
+(1 row)
+
+select * from test2 where t ~ 'dEf';
+ t
+---
+(0 rows)
+
+select * from test2 where t ~* '^q';
+ t
+-------
+ quark
+(1 row)
+
+select * from test2 where t ~* '[abc]{3}[def]{3}';
+ t
+--------
+ abcdef
+(1 row)
+
+select * from test2 where t ~ 'q.*rk$';
+ t
+-------
+ quark
+(1 row)
+
drop index test2_idx_gin;
create index test2_idx_gist on test2 using gist (t gist_trgm_ops);
set enable_seqscan=off;
diff --git a/contrib/pg_trgm/pg_trgm--1.0.sql b/contrib/pg_trgm/pg_trgm--1.0.sql
index 8067bd6..ca9bcaa 100644
--- a/contrib/pg_trgm/pg_trgm--1.0.sql
+++ b/contrib/pg_trgm/pg_trgm--1.0.sql
@@ -163,4 +163,6 @@ AS
ALTER OPERATOR FAMILY gin_trgm_ops USING gin ADD
OPERATOR 3 pg_catalog.~~ (text, text),
- OPERATOR 4 pg_catalog.~~* (text, text);
+ OPERATOR 4 pg_catalog.~~* (text, text),
+ OPERATOR 5 pg_catalog.~ (text, text),
+ OPERATOR 6 pg_catalog.~* (text, text);
diff --git a/contrib/pg_trgm/sql/pg_trgm.sql b/contrib/pg_trgm/sql/pg_trgm.sql
index 81ab1e7..7d8a151 100644
--- a/contrib/pg_trgm/sql/pg_trgm.sql
+++ b/contrib/pg_trgm/sql/pg_trgm.sql
@@ -13,7 +13,7 @@ select similarity('wow',' WOW ');
CREATE TABLE test_trgm(t text);
-\copy test_trgm from 'data/trgm.data
+\copy test_trgm from 'data/trgm.data'
select t,similarity(t,'qwertyu0988') as sml from test_trgm where t % 'qwertyu0988' order by sml desc, t;
select t,similarity(t,'gwertyu0988') as sml from test_trgm where t % 'gwertyu0988' order by sml desc, t;
@@ -52,6 +52,14 @@ select * from test2 where t like '%bcd%';
select * from test2 where t like E'%\\bcd%';
select * from test2 where t ilike '%BCD%';
select * from test2 where t ilike 'qua%';
+
+select * from test2 where t ~ '[abc]{3}';
+select * from test2 where t ~ 'a[bc]+d';
+select * from test2 where t ~* 'DEF';
+select * from test2 where t ~ 'dEf';
+select * from test2 where t ~* '^q';
+select * from test2 where t ~* '[abc]{3}[def]{3}';
+select * from test2 where t ~ 'q.*rk$';
drop index test2_idx_gin;
create index test2_idx_gist on test2 using gist (t gist_trgm_ops);
set enable_seqscan=off;
diff --git a/contrib/pg_trgm/trgm.h b/contrib/pg_trgm/trgm.h
index 067f29d..b3ce65b 100644
--- a/contrib/pg_trgm/trgm.h
+++ b/contrib/pg_trgm/trgm.h
@@ -7,7 +7,6 @@
#include "access/gist.h"
#include "access/itup.h"
#include "storage/bufpage.h"
-#include "utils/builtins.h"
/* options */
#define LPADDING 2
@@ -28,6 +27,8 @@
#define DistanceStrategyNumber 2
#define LikeStrategyNumber 3
#define ILikeStrategyNumber 4
+#define RegExpStrategyNumber 5
+#define RegExpStrategyNumberICase 6
typedef char trgm[3];
@@ -46,8 +47,10 @@ uint32 trgm2int(trgm *ptr);
#ifdef KEEPONLYALNUM
#define ISPRINTABLECHAR(a) ( isascii( *(unsigned char*)(a) ) && (isalnum( *(unsigned char*)(a) ) || *(unsigned char*)(a)==' ') )
+#define ISWORDCHR(c) (t_isalpha(c) || t_isdigit(c))
#else
#define ISPRINTABLECHAR(a) ( isascii( *(unsigned char*)(a) ) && isprint( *(unsigned char*)(a) ) )
+#define ISWORDCHR(c) (!t_isspace(c))
#endif
#define ISPRINTABLETRGM(t) ( ISPRINTABLECHAR( ((char*)(t)) ) && ISPRINTABLECHAR( ((char*)(t))+1 ) && ISPRINTABLECHAR( ((char*)(t))+2 ) )
@@ -99,11 +102,16 @@ typedef char *BITVECP;
#define GETARR(x) ( (trgm*)( (char*)x+TRGMHDRSIZE ) )
#define ARRNELEM(x) ( ( VARSIZE(x) - TRGMHDRSIZE )/sizeof(trgm) )
+typedef struct PackedGraph PackedGraph;
+
extern float4 trgm_limit;
TRGM *generate_trgm(char *str, int slen);
TRGM *generate_wildcard_trgm(const char *str, int slen);
float4 cnt_sml(TRGM *trg1, TRGM *trg2);
bool trgm_contained_by(TRGM *trg1, TRGM *trg2);
+void cnt_trigram(trgm *trgmptr, char *str, int bytelen);
+TRGM *createTrgmCNFA(text *text_re, MemoryContext context, PackedGraph **paths);
+bool trigramsMatchGraph(PackedGraph *graph, bool *check);
#endif /* __TRGM_H__ */
diff --git a/contrib/pg_trgm/trgm_gin.c b/contrib/pg_trgm/trgm_gin.c
index 114fb78..b519901 100644
--- a/contrib/pg_trgm/trgm_gin.c
+++ b/contrib/pg_trgm/trgm_gin.c
@@ -80,7 +80,7 @@ gin_extract_query_trgm(PG_FUNCTION_ARGS)
StrategyNumber strategy = PG_GETARG_UINT16(2);
/* bool **pmatch = (bool **) PG_GETARG_POINTER(3); */
- /* Pointer *extra_data = (Pointer *) PG_GETARG_POINTER(4); */
+ Pointer **extra_data = (Pointer **) PG_GETARG_POINTER(4);
/* bool **nullFlags = (bool **) PG_GETARG_POINTER(5); */
int32 *searchMode = (int32 *) PG_GETARG_POINTER(6);
Datum *entries = NULL;
@@ -88,6 +88,7 @@ gin_extract_query_trgm(PG_FUNCTION_ARGS)
int32 trglen;
trgm *ptr;
int32 i;
+ PackedGraph *graph;
switch (strategy)
{
@@ -107,6 +108,32 @@ gin_extract_query_trgm(PG_FUNCTION_ARGS)
*/
trg = generate_wildcard_trgm(VARDATA(val), VARSIZE(val) - VARHDRSZ);
break;
+ case RegExpStrategyNumberICase:
+#ifndef IGNORECASE
+ elog(ERROR, "cannot handle ~* with case-sensitive trigrams");
+#endif
+ /* FALL THRU */
+ case RegExpStrategyNumber:
+ trg = createTrgmCNFA(val, fcinfo->flinfo->fn_mcxt, &graph);
+ if (trg && ARRNELEM(trg) > 0)
+ {
+ /*
+ * Successful regex processing: store CNFA-like graph as an
+ * extra_data.
+ */
+ *extra_data = (Pointer *) palloc0(sizeof(Pointer) *
+ ARRNELEM(trg));
+ for (i = 0; i < ARRNELEM(trg); i++)
+ (*extra_data)[i] = (Pointer) graph;
+ }
+ else
+ {
+ /* No result: have to do full index scan. */
+ *nentries = 0;
+ *searchMode = GIN_SEARCH_MODE_ALL;
+ PG_RETURN_POINTER(entries);
+ }
+ break;
default:
elog(ERROR, "unrecognized strategy number: %d", strategy);
trg = NULL; /* keep compiler quiet */
@@ -147,7 +174,7 @@ gin_trgm_consistent(PG_FUNCTION_ARGS)
/* text *query = PG_GETARG_TEXT_P(2); */
int32 nkeys = PG_GETARG_INT32(3);
- /* Pointer *extra_data = (Pointer *) PG_GETARG_POINTER(4); */
+ Pointer *extra_data = (Pointer *) PG_GETARG_POINTER(4);
bool *recheck = (bool *) PG_GETARG_POINTER(5);
bool res;
int32 i,
@@ -189,6 +216,17 @@ gin_trgm_consistent(PG_FUNCTION_ARGS)
}
}
break;
+ case RegExpStrategyNumber:
+ case RegExpStrategyNumberICase:
+ if (nkeys < 1)
+ {
+ /* Regex processing gave no result: do full index scan */
+ res = true;
+ break;
+ }
+ res = trigramsMatchGraph((PackedGraph *) extra_data[0], check);
+
+ break;
default:
elog(ERROR, "unrecognized strategy number: %d", strategy);
res = false; /* keep compiler quiet */
diff --git a/contrib/pg_trgm/trgm_op.c b/contrib/pg_trgm/trgm_op.c
index 87dffd1..71aa938 100644
--- a/contrib/pg_trgm/trgm_op.c
+++ b/contrib/pg_trgm/trgm_op.c
@@ -77,12 +77,6 @@ unique_array(trgm *a, int len)
return curend + 1 - a;
}
-#ifdef KEEPONLYALNUM
-#define iswordchr(c) (t_isalpha(c) || t_isdigit(c))
-#else
-#define iswordchr(c) (!t_isspace(c))
-#endif
-
/*
* Finds first word in string, returns pointer to the word,
* endword points to the character after word
@@ -92,7 +86,7 @@ find_word(char *str, int lenstr, char **endword, int *charlen)
{
char *beginword = str;
- while (beginword - str < lenstr && !iswordchr(beginword))
+ while (beginword - str < lenstr && !ISWORDCHR(beginword))
beginword += pg_mblen(beginword);
if (beginword - str >= lenstr)
@@ -100,7 +94,7 @@ find_word(char *str, int lenstr, char **endword, int *charlen)
*endword = beginword;
*charlen = 0;
- while (*endword - str < lenstr && iswordchr(*endword))
+ while (*endword - str < lenstr && ISWORDCHR(*endword))
{
*endword += pg_mblen(*endword);
(*charlen)++;
@@ -109,8 +103,7 @@ find_word(char *str, int lenstr, char **endword, int *charlen)
return beginword;
}
-#ifdef USE_WIDE_UPPER_LOWER
-static void
+void
cnt_trigram(trgm *tptr, char *str, int bytelen)
{
if (bytelen == 3)
@@ -131,7 +124,6 @@ cnt_trigram(trgm *tptr, char *str, int bytelen)
CPTRGM(tptr, &crc);
}
}
-#endif
/*
* Adds trigrams from words (already padded).
@@ -287,7 +279,7 @@ get_wildcard_part(const char *str, int lenstr,
{
if (in_escape)
{
- if (iswordchr(beginword))
+ if (ISWORDCHR(beginword))
break;
in_escape = false;
in_leading_wildcard_meta = false;
@@ -298,7 +290,7 @@ get_wildcard_part(const char *str, int lenstr,
in_escape = true;
else if (ISWILDCARDCHAR(beginword))
in_leading_wildcard_meta = true;
- else if (iswordchr(beginword))
+ else if (ISWORDCHR(beginword))
break;
else
in_leading_wildcard_meta = false;
@@ -341,7 +333,7 @@ get_wildcard_part(const char *str, int lenstr,
clen = pg_mblen(endword);
if (in_escape)
{
- if (iswordchr(endword))
+ if (ISWORDCHR(endword))
{
memcpy(s, endword, clen);
(*charlen)++;
@@ -369,7 +361,7 @@ get_wildcard_part(const char *str, int lenstr,
in_trailing_wildcard_meta = true;
break;
}
- else if (iswordchr(endword))
+ else if (ISWORDCHR(endword))
{
memcpy(s, endword, clen);
(*charlen)++;
diff --git a/contrib/pg_trgm/trgm_regexp.c b/contrib/pg_trgm/trgm_regexp.c
new file mode 100644
index 0000000..cfcabbb
--- /dev/null
+++ b/contrib/pg_trgm/trgm_regexp.c
@@ -0,0 +1,1797 @@
+/*
+ * contrib/pg_trgm/trgm_regexp.c - regular expression matching using trigrams
+ *
+ * The general idea of index support for a regular expression (regex) search
+ * is to transform the regex to a logical expression on trigrams. For example:
+ *
+ * (ab|cd)efg => ((abe & bef) | (cde & def)) & efg
+ *
+ * If a string matches the regex, then it must match the logical expression of
+ * trigrams. The opposite is not necessary true, however: a string that matches
+ * the logical expression might not match the original regex. Such false
+ * positives are removed during recheck.
+ *
+ * The algorithm to convert a regex to a logical expression is based on
+ * analysis of an automaton that corresponds to regex. The algorithm consists
+ * of four stages:
+ *
+ * 1) Compile the regexp to CNFA form. This is handled by the PostgreSQL
+ * regexp library, but we have peek into the data structures it produces.
+ *
+ * 2) Transform the original CNFA into an automaton-like graph, where arcs
+ * are labeled with trigrams that must be present in order to move from
+ * state to another via the arc. The trigrams used in this stage consist
+ * of colors, not characters, like the original CNFA.
+ *
+ * 3) Expand the color trigrams into regular trigrams consisting of
+ * characters. If too many distinct trigrams are produced, trigrams are
+ * eliminated and the graph is simplified until it's simple enough.
+ *
+ * 4) Finally, the resulting graph is packed into a PackedGraph struct, and
+ * returned to the caller.
+ *
+ *
+ * 1) Compile the regexp to CNFA form
+ * ----------------------------------
+ * The automaton returned by the regexp compiler is a graph where vertices
+ * are "states" and arcs are labeled with colors. Each color represents
+ * a group of characters, so that all characters assigned to the same color
+ * are interchangeable, as far as matching the regexp is concerned. There are
+ * two special states: "initial" and "final". There can be multiple outgoing
+ * arcs from a state labeled with the same color, which makes the automaton
+ * non-deterministic, because it can be in many states simultaneously.
+ *
+ * 2) Transform the original CNFA into an automaton-like graph
+ * -----------------------------------------------------------
+ * In the 2nd stage, the automaton is transformed into a graph that resembles
+ * the original CNFA. Each state in the transformed graph represents a state
+ * from the original CNFA, with an "enter key". The enter key consists of the
+ * last two characters (colors, to be precise) read before entering the state.
+ * There can be one or more states in the transformed graph for each state in
+ * the original CNFA, depending on what characters can precede it. Each arc
+ * is labelled with a trigram that must be present in the string to match.
+ *
+ * So the transformed graph resembles the original CNFA, but the arcs are
+ * labeled with trigrams instead of individual characters, and there are
+ * more states. It is a lossy representation of the original CNFA: any string
+ * that matches the original regexp must match the transformed graph, but the
+ * reverse is not true.
+ *
+ * When building the graph, if the number of states or arcs exceed pre-defined
+ * limits, we give up and simply mark any states not yet processed as final
+ * states. Roughly speaking, that means that we make use of some portion from
+ * the beginning of the regexp.
+ *
+ * 3) Expand the color trigrams into regular trigrams
+ * --------------------------------------------------
+ * The trigrams in the transformed graph are "color trigrams", consisting
+ * of three consecutive colors that must be present in the string. But for
+ * search, we need regular trigrams consisting of characters. In the 3rd
+ * stage, the color trigrams are expanded into regular trigrams. Since each
+ * color can represent many characters, the total number of regular trigrams
+ * after expansion could be very large. Because searching an index with
+ * thousands of trigrams would be slow, and would likely produce so many
+ * "false positives" that you would have to traverse a large fraction of the
+ * index, the graph is simplified further in a lossy fashion by removing
+ * color trigrams until the number of trigrams after expansion is below
+ * MAX_TRGM_COUNT threshold. When a color trigram is removed, the states
+ * connected by any arcs labelled with that trigram are merged.
+ *
+ * 4) Pack the graph into a compact representation
+ * -----------------------------------------------
+ * The 2nd and 3rd stages might have eliminated or merged many of the states
+ * and trigrams created earlier, so in this final stage, the graph is
+ * compacted and packed into a simpler struct that contains only the
+ * information needed to evaluate it.
+ *
+ *
+ * OLD COMMENTS:
+ * States of the graph produced in the first stage are marked with "keys". Key
+ * is a pair of a "prefix" and a state of the original automaton. "Prefix" is
+ * pair of colors of last two read characters. So, knowing the prefix is enough
+ * to know what is a color trigram when we read new character with some
+ * particular color. However, we can know single color of prefix or don't know
+ * any color of it. Each state of resulting graph have an "enter key" (with that
+ * key we've entered this state) and a set of keys which are reachable without
+ * reading any predictable color trigram. The algorithm of processing each state
+ * of resulting graph are so:
+ * 1) Add all keys which achievable without reading of any predictable color
+ * trigram.
+ * 2) Add outgoing arcs labeled with trigrams.
+ * Step 2 leads to creation of new states. We use breadth-first algorithm for
+ * processing them.
+ *
+ * Consider this on example of regex ab[cd]. This regex are transformed into
+ * following CNFA (for simplicity of example we don't use colors):
+ *
+ * 4#
+ * c/
+ * a b /
+ * 1* --- 2 ---- 3
+ * \
+ * d\
+ * 5#
+ *
+ * We use * to mark initial state and # to mark final state. It's not depicted,
+ * but states 1, 4, 5 have self-referencing arcs for all possible characters,
+ * because pattern can match to any part of string.
+ *
+ * As the result of first stage we will have following graph:
+ *
+ * abc abd
+ * 2# <---- 1* ----> 3#
+ *
+ * Let us consider the sequence of algorithm work for this graph producing.
+ * We will designate state key as (prefix.s, prefix.ambiguity, nstate).
+ * 1) Create state 1 with enter key (" ", true, 1).
+ * 2) Add key (" a", true, 2) to state 1.
+ * 3) Add key ("ab", false, 3) to state 1.
+ * 4) Add arc from output state 1 to new state 2 with enter key
+ * ("bc", false, 4).
+ * 5) Mark state 2 final because state 4 of source CNFA is marked as final.
+ * 6) Add arc from output state 1 to new state 3 with enter key
+ * ("bd", false, 5).
+ * 7) Mark state 3 final because state 4 of source CNFA is marked as final.
+ *
+ * At the second stage we select color trigrams to expand into simple trigrams.
+ * We're removing color trigrams starting from the most wide. When removing
+ * color trigram we have to merge states connected by corresponding arcs.
+ * It's necessary to not merge initial and final states, because our graph
+ * becomes useless in this case.
+ */
+#include "postgres.h"
+
+#include "trgm.h"
+
+#include "catalog/pg_collation.h"
+#include "fmgr.h"
+#include "miscadmin.h"
+#include "mb/pg_wchar.h"
+#include "nodes/pg_list.h"
+#include "regex/regex.h"
+#undef INFINITY /* avoid conflict of INFINITY definition */
+#include "regex/regguts.h"
+#include "tsearch/ts_locale.h"
+#include "utils/hsearch.h"
+
+/*
+ * Uncomment to print intermediate stages, for exploring and debugging the
+ * algorithm implementation. This produces three graphs in Graphviz .dot
+ * format, in /tmp.
+ */
+#define TRGM_REGEXP_DEBUG
+
+/*---
+ * Following group of parameters are used in order to limit our computations.
+ * Otherwise regex processing could be too slow and memory-consuming.
+ *
+ * MAX_RESULT_STATES - How many states we allow in result CNFA-like graph
+ * MAX_RESULT_ARCS - How many arcs we allow in result CNFA-like graph
+ * MAX_TRGM_COUNT - How many simple trigrams we allow to extract
+ */
+#define MAX_RESULT_STATES 128
+#define MAX_RESULT_ARCS 1024
+#define MAX_TRGM_COUNT 256
+
+/* Virtual color for representation in prefixes and color trigrams. */
+#define EMPTY_COLOR ((color) -1)
+#define UNKNOWN_COLOR ((color) -2)
+
+/*
+ * Widechar trigram datatype for holding trigram before possible conversion into
+ * CRC32
+ */
+typedef color ColorTrgm[3];
+
+/*
+ * Maximum length of multibyte encoding character is 4. So, we can hold it in
+ * 32 bit integer for handling simplicity.
+ */
+typedef uint32 mb_char;
+
+/*----
+ * Attributes of CNFA colors:
+ *
+ * expandable - flag indicates we potentially can expand this
+ * color into distinct characters.
+ * containNonAlpha - flag indicates if color might contain
+ * non-alphanumeric characters (which aren't
+ * extracted into trigrams)
+ * alphaCharsCount - count of characters in color
+ * alphaCharsCountAllocated - allocated size of alphaChars array
+ * alphaChars - array of alphanumeric characters of this color
+ * (which are extracted into trigrams)
+ *
+ * When expandable is false, all other attributes doesn't matter we just think
+ * this color as always unknown character.
+ */
+typedef struct
+{
+ bool expandable;
+ bool containNonAlpha;
+ int alphaCharsCount;
+ int alphaCharsCountAllocated;
+ mb_char *alphaChars;
+} ColorInfo;
+
+/*
+ * Prefix is information about colors of last two read characters when coming
+ * into specific CNFA state. These colors could have special values
+ * UNKNOWN_COLOR and EMPTY_COLOR. UNKNOWN_COLOR means that we read some
+ * character of unexpandable color. EMPTY_COLOR means that we read
+ * non-alphanumeric character.
+ */
+typedef struct
+{
+ color s[2];
+} TrgmPrefix;
+
+/*
+ * "Key" of resulting state: pair of prefix and source CNFA state.
+ */
+typedef struct
+{
+ TrgmPrefix prefix;
+ int nstate;
+} TrgmStateKey;
+
+/*---
+ * State of resulting graph.
+ *
+ * enterKey - a key with which we can enter this state
+ * keys - all keys achievable without reading any predictable trigram
+ * arcs - outgoing arcs of this state
+ * parent - parent state if this state has been merged
+ * children - children states if this state has been merged
+ * fin - flag indicated this state is final
+ * init - flag indicated this state is initial
+ * queued - flag indicated this state is queued in CNFA-like graph
+ * construction
+ * number - number of this state (use at the package stage)
+ */
+typedef struct TrgmState
+{
+ TrgmStateKey enterKey;
+ List *arcs;
+ bool fin;
+ bool init;
+
+ /* (stage 2) */
+ List *keys;
+ bool queued;
+
+ struct TrgmState *parent;
+ List *children;
+ int number;
+} TrgmState;
+
+/*
+ * Arc in the transformed graph. Arc is labeled with trigram.
+ */
+typedef struct
+{
+ TrgmState *target;
+ ColorTrgm trgm;
+} TrgmArc;
+
+/*
+ * Information about arc of specific color trigram: contain pointers to the
+ * source and target states. (stage 3)
+ */
+typedef struct
+{
+ TrgmState *source;
+ TrgmState *target;
+} ArcInfo;
+
+/*---
+ * Information about color trigram: (stage 3)
+ *
+ * trgm - trigram itself
+ * number - number of this trigram (used in the package stage)
+ * count - number of simple trigrams fitting into this color trigram
+ * expanded - flag indicates this color trigram is expanded into simple trigrams
+ * arcs - list of all arcs labeled with this color trigram.
+ */
+typedef struct
+{
+ ColorTrgm trgm;
+ int number;
+ int count;
+ bool expanded;
+ List *arcs;
+} ColorTrgmInfo;
+
+/*---
+ * Data structure representing all the data we need during regex processing.
+ * Initially we set "cnfa" to cnfa of regex, write color information info
+ * "colorInfo" and set "overflowed" flag to false. And the stage of trigram
+ * CFNA-like graph creation "states", "initState" and "arcsCount" are filled.
+ * "owerflowed" flag could be set in case of overflow. Then we collect array
+ * of all present color trigrams to "colorTrgms" and "colorTrgmsCount" and
+ * expand them into "trg" and "totalTrgmCount".
+ *
+ * cnfa - source CFNA of regex
+ * colorInfo - processed information of regex colors
+ * ncolors - number of colors in colorInfo
+ * states - hash of states of resulting graph
+ * initState - pointer to initial state of resulting graph
+ * arcsCount - total number of arcs of resulting graph (for resource
+ * limiting)
+ * colorTrgms - array of all color trigrams presented in graph
+ * colorTrgmsCount - count of that color trigrams
+ * totalTrgmCount - total count of extracted simple trigrams
+ * queue - queue for CFNA-like graph construction
+ * overflowed - if set, we have exceeded resource limit for transformation
+ */
+typedef struct
+{
+ /*
+ * Source CNFA of the regexp, and color information extracted from it
+ * (stage 1)
+ */
+ struct cnfa *cnfa;
+ ColorInfo *colorInfo;
+ int ncolors;
+
+ /* Transformed graph (stage 2) */
+ HTAB *states;
+ TrgmState *initState;
+ int arcsCount;
+ List *queue;
+ bool overflowed;
+
+ /* Information about distinct color trigrams in the graph (stage 3) */
+ ColorTrgmInfo *colorTrgms;
+
+ int colorTrgmsCount;
+ int totalTrgmCount;
+} TrgmCNFA;
+
+
+/*
+ * Final, compact representation of CNFA-like graph.
+ */
+typedef struct
+{
+ int targetState;
+ int colorTrgm;
+} PackedArc;
+
+typedef struct
+{
+ int arcsCount;
+ PackedArc *arcs;
+} PackedState;
+
+struct PackedGraph
+{
+ /*
+ * colorTrigramsCount and colorTrigramsGroups contain information
+ * about how trigrams are grouped into color trigrams. "colorTrigramsCount"
+ * represents total count of color trigrams and "colorTrigramGroups" contain
+ * number of simple trigrams in each color trigram.
+ */
+ int colorTrigramsCount;
+ int *colorTrigramGroups;
+
+ /*
+ * "states" points to definition of "statesCount" states. 0 state is
+ * always initial state and 1 state is always final state. Each state's
+ * "arcs" points to "arcsCount" description of arcs. Each arc describe by
+ * number of color trigram and number of target state (both are zero-based).
+ */
+ int statesCount;
+ PackedState *states;
+
+ /* Temporary work space for trigramsMatchGraph() */
+ bool *colorTrigramsActive;
+ bool *statesActive;
+};
+
+
+/* prototypes for private functions */
+static bool activateState(PackedGraph *graph, int stateno);
+static ColorInfo *getColorInfo(regex_t *regex, int *ncolors);
+static TrgmState *getState(TrgmCNFA *trgmCNFA, TrgmStateKey *key);
+static void transformGraph(TrgmCNFA *trgmCNFA);
+static bool selectColorTrigrams(TrgmCNFA *trgmCNFA);
+static TRGM *expandColorTrigrams(TrgmCNFA *trgmCNFA);
+static PackedGraph *packGraph(TrgmCNFA *trgmCNFA, MemoryContext context);
+
+#ifdef TRGM_REGEXP_DEBUG
+static void printSourceCNFA(struct cnfa *cnfa, ColorInfo *colors, int ncolors);
+static void printTrgmCNFA(TrgmCNFA *trgmCNFA);
+static void printPackedGraph(PackedGraph *packedGraph, TRGM *trigrams);
+#endif
+
+
+/*
+ * Main entry point to process a regular expression. Returns a packed graph
+ * representation of the regular expression, or NULL if the regular expression
+ * was too complex.
+ */
+TRGM *
+createTrgmCNFA(text *text_re, MemoryContext context, PackedGraph **graph)
+{
+ struct guts *g;
+ TrgmCNFA trgmCNFA;
+ regex_t *regex;
+ TRGM *trg;
+
+ /*
+ * Stage 1: Compile the regexp into a CNFA, using the PostgreSQL regexp
+ * library.
+ */
+#ifdef IGNORECASE
+ regex = RE_compile_and_cache(text_re, REG_ADVANCED | REG_ICASE, DEFAULT_COLLATION_OID);
+#else
+ regex = RE_compile_and_cache(text_re, REG_ADVANCED, DEFAULT_COLLATION_OID);
+#endif
+ g = (struct guts *) regex->re_guts;
+ trgmCNFA.cnfa = &g->search;
+
+ /* Collect color information from the CNFA */
+ trgmCNFA.colorInfo = getColorInfo(regex, &trgmCNFA.ncolors);
+
+#ifdef TRGM_REGEXP_DEBUG
+ printSourceCNFA(&g->search, trgmCNFA.colorInfo, trgmCNFA.ncolors);
+#endif
+
+ /*
+ * Stage 2: Create a transformed graph from the source CNFA.
+ */
+ transformGraph(&trgmCNFA);
+
+#ifdef TRGM_REGEXP_DEBUG
+ printTrgmCNFA(&trgmCNFA);
+#endif
+
+ if (trgmCNFA.initState->fin)
+ return NULL;
+
+ /*
+ * Stage 3: Select color trigrams to expand.
+ */
+ if (!selectColorTrigrams(&trgmCNFA))
+ return NULL;
+
+ /*
+ * Stage 4: Expand color trigrams and pack graph into final representation.
+ */
+ trg = expandColorTrigrams(&trgmCNFA);
+
+ *graph = packGraph(&trgmCNFA, context);
+
+#ifdef TRGM_REGEXP_DEBUG
+ printPackedGraph(*graph, trg);
+#endif
+
+ return trg;
+}
+
+/*
+ * Main entry point for evaluating a graph.
+ */
+bool
+trigramsMatchGraph(PackedGraph *graph, bool *check)
+{
+ int i,
+ j,
+ k;
+
+ /*
+ * 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. */
+ 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;
+ }
+
+ /* Recursively evaluate graph, starting from initial state */
+ return activateState(graph, 0);
+}
+
+/*
+ * Recursive function for graph state activation. Returns true if state
+ * activation leads to activation of final state.
+ */
+static bool
+activateState(PackedGraph *graph, int stateno)
+{
+ PackedState *state = &graph->states[stateno];
+ int cnt = state->arcsCount;
+ int i;
+
+ graph->statesActive[stateno] = true;
+
+ /* Loop over arcs */
+ for (i = 0; i < cnt; i++)
+ {
+ PackedArc *arc = (PackedArc *) &state->arcs[i];
+ /*
+ * If corresponding color trigram is present then activate the
+ * corresponding state.
+ */
+ if (graph->colorTrigramsActive[arc->colorTrgm])
+ {
+ if (arc->targetState == 1)
+ return true; /* reached final state */
+ if (!graph->statesActive[arc->targetState])
+ {
+ if (activateState(graph, arc->targetState))
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+/*---------------------
+ * Subroutines for pre-processing the color map.
+ *---------------------
+ */
+
+/*
+ * Convert pg_wchar to multibyte character.
+ */
+static mb_char
+convertPgWchar(pg_wchar c)
+{
+ /*
+ * "s" has enough of space for a multibyte character of 4 bytes, and
+ * a zero-byte at the end.
+ */
+ char s[5];
+ char *lowerCased;
+ mb_char result;
+
+ if (c == 0)
+ return 0;
+
+ MemSet(s, 0, sizeof(s));
+ pg_wchar2mb_with_len(&c, s, 1);
+
+ /* Convert to lowercase if needed */
+#ifdef IGNORECASE
+ lowerCased = lowerstr(s);
+ if (strncmp(lowerCased, s, 4))
+ return 0;
+#else
+ lowerCased = s;
+#endif
+ strncpy((char *) &result, lowerCased, 4);
+ return result;
+}
+
+/*
+ * Add new character into color information
+ */
+static void
+addCharToColor(ColorInfo *colorInfo, pg_wchar c)
+{
+ if (!colorInfo->alphaChars)
+ {
+ colorInfo->alphaCharsCountAllocated = 16;
+ colorInfo->alphaChars = (pg_wchar *) palloc(sizeof(pg_wchar) *
+ colorInfo->alphaCharsCountAllocated);
+ }
+ if (colorInfo->alphaCharsCount >= colorInfo->alphaCharsCountAllocated)
+ {
+ colorInfo->alphaCharsCountAllocated *= 2;
+ colorInfo->alphaChars = (pg_wchar *) repalloc(colorInfo->alphaChars,
+ sizeof(pg_wchar) * colorInfo->alphaCharsCountAllocated);
+ }
+ colorInfo->alphaChars[colorInfo->alphaCharsCount++] = c;
+}
+
+/*
+ * Recursive function which scans colormap and updates color attributes in
+ * ColorInfo structure. Colormap is a tree which maps character to colors.
+ * The tree contains 4 levels. Each level corresponding to byte of character.
+ * Non-leaf nodes of tree contain pointers to descending tree nodes for each
+ * byte value. Leaf nodes of tree contain color numbers for each byte value.
+ * Potentially colormap could be very large, but most part of the colormap
+ * points to zero colors. That's tree nodes which corresponds to only zero
+ * color can be reused.
+ */
+static void
+scanColorMap(union tree tree[NBYTS], union tree *t, ColorInfo *colorInfos,
+ int level, pg_wchar p)
+{
+ int i;
+
+ check_stack_depth();
+
+ if (level < NBYTS - 1)
+ {
+ /* non-leaf node */
+ for (i = 0; i < BYTTAB; i++)
+ {
+ /*
+ * This condition checks if all underlying levels express zero
+ * color. Zero color uses multiple links to same tree node. So,
+ * avoid scanning it because it's expensive.
+ */
+ if (t->tptr[i] == &tree[level + 1])
+ continue;
+ /* Recursive scanning of next level color table */
+ scanColorMap(tree, t->tptr[i], colorInfos, level + 1, (p << 8) | i);
+ }
+ }
+ else
+ {
+ /* leaf node */
+ p <<= 8;
+ for (i = 0; i < BYTTAB; i++)
+ {
+ ColorInfo *colorInfo = &colorInfos[t->tcolor[i]];
+ pg_wchar c;
+
+ if (!colorInfo->expandable)
+ continue;
+
+ /* Convert to multibyte character */
+ c = convertPgWchar(p | i);
+
+ if (!c)
+ continue;
+
+ /* Update color attributes according to next character */
+ if (ISWORDCHR((char *)&c))
+ addCharToColor(colorInfo, c);
+ else
+ colorInfo->containNonAlpha = true;
+ }
+ }
+}
+
+/*
+ * Fill ColorInfo structure for each color by scanning colormap.
+ */
+static ColorInfo *
+getColorInfo(regex_t *regex, int *ncolors)
+{
+ struct guts *g;
+ struct colormap *cm;
+ ColorInfo *result;
+ int colorsCount;
+ int i;
+
+ g = (struct guts *) regex->re_guts;
+ cm = &g->cmap;
+ *ncolors = colorsCount = cm->max + 1;
+
+ result = (ColorInfo *) palloc0(colorsCount * sizeof(ColorInfo));
+
+ /*
+ * Zero color is a default color which contains all characters that aren't
+ * in explicitly expressed classes. Mark that we can expect everything
+ * from it.
+ */
+ result[0].expandable = false;
+ for (i = 1; i < colorsCount; i++)
+ result[i].expandable = true;
+
+ scanColorMap(cm->tree, &cm->tree[0], result, 0, 0);
+
+ return result;
+}
+
+/*---------------------
+ * Subroutines for transforming original CNFA graph into a color trigram
+ * graph.
+ *---------------------
+ */
+
+/*
+ * Check if prefix1 "contains" prefix2. "contains" mean that any exact prefix
+ * (which no ambiguity) which satisfy to prefix2 also satisfy to prefix1.
+ */
+static bool
+prefixContains(TrgmPrefix *prefix1, TrgmPrefix *prefix2)
+{
+ if (prefix1->s[1] == UNKNOWN_COLOR)
+ {
+ /* Fully ambiguous prefix contains everything */
+ return true;
+ }
+ else if (prefix1->s[0] == UNKNOWN_COLOR)
+ {
+ /*
+ * Prefix with only first unknown color contains every prefix with same
+ * second color.
+ */
+ if (prefix1->s[1] == prefix2->s[1])
+ return true;
+ else
+ return false;
+ }
+ else
+ {
+ /* Exact prefix contains only exactly same prefix */
+ if (prefix1->s[0] == prefix2->s[0] && prefix1->s[1] == prefix2->s[1])
+ return true;
+ else
+ return false;
+ }
+}
+
+/*
+ * Add all keys that can be reached without reading any color trigram to
+ * state of CNFA-like graph on color trigrams.
+ */
+static void
+addKeys(TrgmCNFA *trgmCNFA, TrgmState *state, TrgmStateKey *key)
+{
+ struct carc *s;
+ TrgmStateKey destKey;
+ ListCell *cell, *prev, *next;
+ TrgmStateKey *keyCopy;
+
+ MemSet(&destKey, 0, sizeof(TrgmStateKey));
+
+ /* Adjust list of keys with new one */
+ prev = NULL;
+ cell = list_head(state->keys);
+ while (cell)
+ {
+ TrgmStateKey *existingKey = (TrgmStateKey *) lfirst(cell);
+ next = lnext(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->keys = list_delete_cell(state->keys, cell, prev);
+ }
+ else
+ prev = cell;
+ }
+ else
+ prev = cell;
+ cell = next;
+ }
+
+ keyCopy = (TrgmStateKey *) palloc(sizeof(TrgmStateKey));
+ memcpy(keyCopy, key, sizeof(TrgmStateKey));
+ state->keys = lappend(state->keys, keyCopy);
+
+ /* Mark final state */
+ if (key->nstate == trgmCNFA->cnfa->post)
+ {
+ state->fin = true;
+ return;
+ }
+
+ /*
+ * Loop through all outgoing arcs from the corresponding state in the
+ * original CNFA.
+ */
+ s = trgmCNFA->cnfa->states[key->nstate];
+ while (s->co != COLORLESS)
+ {
+ ColorInfo *colorInfo;
+
+ if (s->co == trgmCNFA->cnfa->bos[1])
+ {
+ /* Start of line (^) */
+ destKey.nstate = s->to;
+
+ /* Mark prefix as start of new color trigram */
+ destKey.prefix.s[0] = EMPTY_COLOR;
+ destKey.prefix.s[1] = EMPTY_COLOR;
+
+ /* Add key to this state */
+ addKeys(trgmCNFA, state, &destKey);
+ if (state->fin)
+ return;
+ }
+ else if (s->co == trgmCNFA->cnfa->eos[1])
+ {
+ /* End of string ($) */
+ if (key->prefix.s[0] == UNKNOWN_COLOR ||
+ key->prefix.s[1] == EMPTY_COLOR)
+ {
+ destKey.nstate = s->to;
+
+ /*
+ * Let's think prefix to become ambiguous (in order to prevent
+ * latter fiddling around with keys).
+ */
+ destKey.prefix.s[1] = UNKNOWN_COLOR;
+ destKey.prefix.s[0] = UNKNOWN_COLOR;
+
+ /* Prefix is ambiguous, add key to the same state */
+ addKeys(trgmCNFA, state, &destKey);
+ if (state->fin)
+ return;
+ }
+ }
+ else
+ {
+ /* Regular color */
+ colorInfo = &trgmCNFA->colorInfo[s->co];
+
+ if (colorInfo->expandable)
+ {
+ if (colorInfo->containNonAlpha &&
+ (key->prefix.s[0] == UNKNOWN_COLOR ||
+ key->prefix.s[1] == EMPTY_COLOR))
+ {
+ /*
+ * When color contain non-alphanumeric character we should
+ * add empty key with empty prefix.
+ */
+ destKey.prefix.s[0] = EMPTY_COLOR;
+ destKey.prefix.s[1] = EMPTY_COLOR;
+ destKey.nstate = s->to;
+ addKeys(trgmCNFA, state, &destKey);
+ if (state->fin)
+ return;
+ }
+
+ if (colorInfo->alphaCharsCount > 0 &&
+ key->prefix.s[0] == UNKNOWN_COLOR)
+ {
+ /* Add corresponding key when prefix was unknown */
+ destKey.prefix.s[0] = key->prefix.s[1];
+ destKey.prefix.s[1] = s->co;
+ destKey.nstate = s->to;
+ addKeys(trgmCNFA, state, &destKey);
+ if (state->fin)
+ return;
+ }
+ }
+ else
+ {
+ /*
+ * Unexpandable color. Add corresponding key to this state.
+ */
+ destKey.nstate = s->to;
+ destKey.prefix.s[0] = UNKNOWN_COLOR;
+ destKey.prefix.s[1] = UNKNOWN_COLOR;
+ addKeys(trgmCNFA, state, &destKey);
+ if (state->fin)
+ return;
+ }
+ }
+ s++;
+ }
+}
+
+/*
+ * Add outgoing arc from state if needed.
+ */
+static void
+addArc(TrgmCNFA *trgmCNFA, TrgmState *state, TrgmStateKey *key,
+ TrgmStateKey *destKey, color co)
+{
+ TrgmArc *arc;
+ ListCell *cell2;
+
+ /* Check whether we actually can add the arc */
+ if (key->prefix.s[0] == UNKNOWN_COLOR ||
+ (key->prefix.s[1] == EMPTY_COLOR && co == EMPTY_COLOR))
+ return;
+
+ /* If we have the same key here, we don't need to add new arc */
+ foreach(cell2, state->keys)
+ {
+ TrgmStateKey *key2 = (TrgmStateKey *) lfirst(cell2);
+ if (key2->nstate == destKey->nstate &&
+ prefixContains(&key2->prefix, &destKey->prefix))
+ {
+ return;
+ }
+ }
+
+ /* Not found, add new arc */
+ arc = (TrgmArc *) palloc(sizeof(TrgmArc));
+ arc->target = getState(trgmCNFA, destKey);
+ arc->trgm[0] = key->prefix.s[0];
+ arc->trgm[1] = key->prefix.s[1];
+ arc->trgm[2] = co;
+ state->arcs = lappend(state->arcs, arc);
+ trgmCNFA->arcsCount++;
+}
+
+/*
+ * Add outgoing arcs from given state.
+ */
+static void
+addArcs(TrgmCNFA *trgmCNFA, TrgmState *state)
+{
+ struct carc *s;
+ TrgmStateKey destKey;
+ ListCell *cell;
+
+ MemSet(&destKey, 0, sizeof(TrgmStateKey));
+
+ /*
+ * Iterate over keys associated with this output state.
+ */
+ foreach(cell, state->keys)
+ {
+ TrgmStateKey *key = (TrgmStateKey *) lfirst(cell);
+ s = trgmCNFA->cnfa->states[key->nstate];
+ while (s->co != COLORLESS)
+ {
+ ColorInfo *colorInfo;
+ if (s->co == trgmCNFA->cnfa->bos[1])
+ {
+ /* Should be already handled by addKeys. */
+ }
+ else if (s->co == trgmCNFA->cnfa->eos[1])
+ {
+ /* End of the string ($) */
+ destKey.nstate = s->to;
+
+ /* Assume prefix to become ambiguous after end of the string */
+ destKey.prefix.s[1] = UNKNOWN_COLOR;
+ destKey.prefix.s[0] = UNKNOWN_COLOR;
+
+ addArc(trgmCNFA, state, key, &destKey, EMPTY_COLOR);
+ }
+ else
+ {
+ /* Regular color: try to add outgoing arcs */
+ colorInfo = &trgmCNFA->colorInfo[s->co];
+
+ if (colorInfo->expandable)
+ {
+ if (colorInfo->containNonAlpha)
+ {
+ destKey.prefix.s[0] = EMPTY_COLOR;
+ destKey.prefix.s[1] = EMPTY_COLOR;
+ destKey.nstate = s->to;
+ addArc(trgmCNFA, state, key, &destKey, EMPTY_COLOR);
+ }
+
+ if (colorInfo->alphaCharsCount > 0)
+ {
+ destKey.prefix.s[0] = key->prefix.s[1];
+ destKey.prefix.s[1] = s->co;
+ destKey.nstate = s->to;
+ addArc(trgmCNFA, state, key, &destKey, s->co);
+ }
+ }
+ }
+ s++;
+ }
+ }
+}
+
+/*
+ * Get state of trigram CNFA-like graph of given enter key and queue it for
+ * processing if needed.
+ */
+static TrgmState *
+getState(TrgmCNFA *trgmCNFA, TrgmStateKey *key)
+{
+ bool found;
+ TrgmState *state;
+
+ state = hash_search(trgmCNFA->states, key, HASH_ENTER, &found);
+ if (!found)
+ {
+ /* New state: initialize and queue it */
+ state->arcs = NIL;
+ state->keys = NIL;
+ state->init = false;
+ state->fin = false;
+ state->children = NIL;
+ state->parent = NULL;
+ state->number = -1;
+
+ state->queued = true;
+ trgmCNFA->queue = lappend(trgmCNFA->queue, state);
+ }
+ return state;
+}
+
+/*
+ * Process the state: add keys and then add outgoing arcs.
+ */
+static void
+processState(TrgmCNFA *trgmCNFA, TrgmState *state)
+{
+ addKeys(trgmCNFA, state, &state->enterKey);
+ /*
+ * Add outgoing arc only if state isn't final (we have no interest in arc
+ * if we already match)
+ */
+ if (!state->fin)
+ addArcs(trgmCNFA, state);
+
+ state->queued = false;
+}
+
+/*
+ * Process queue of CFNA-like graph states until all the states are processed.
+ * This algorithm may be stopped due to resources limitation. In this case we
+ * assume every unprocessed branch to immediately finish with matching (this
+ * can give us more false positives but no false negatives) by marking all
+ * unprocessed states as final.
+ */
+static void
+transformGraph(TrgmCNFA *trgmCNFA)
+{
+ HASHCTL hashCtl;
+ TrgmStateKey initkey;
+ TrgmState *initstate;
+
+ trgmCNFA->queue = NIL;
+ trgmCNFA->arcsCount = 0;
+ trgmCNFA->overflowed = false;
+
+ /* Initialize hash of states */
+ hashCtl.keysize = sizeof(TrgmStateKey);
+ hashCtl.entrysize = sizeof(TrgmState);
+ hashCtl.hcxt = CurrentMemoryContext;
+ hashCtl.hash = tag_hash;
+ hashCtl.match = memcmp;
+ trgmCNFA->states =
+ hash_create("Trigram CNFA",
+ 1024,
+ &hashCtl,
+ HASH_ELEM | HASH_CONTEXT | HASH_FUNCTION | HASH_COMPARE);
+
+ /* Create initial state */
+ MemSet(&initkey, 0, sizeof(TrgmStateKey));
+ initkey.prefix.s[0] = UNKNOWN_COLOR;
+ initkey.prefix.s[1] = UNKNOWN_COLOR;
+ initkey.nstate = trgmCNFA->cnfa->pre;
+
+ initstate = getState(trgmCNFA, &initkey);
+ initstate->init = true;
+ trgmCNFA->initState = initstate;
+
+ /*
+ * Recursively build the transformed graph by processing queue of
+ * states (Breadth-first search).
+ */
+ while (trgmCNFA->queue != NIL)
+ {
+ TrgmState *state = (TrgmState *) linitial(trgmCNFA->queue);
+
+ state->queued = false;
+ trgmCNFA->queue = list_delete_first(trgmCNFA->queue);
+
+ /*
+ * If we overflow then just mark state as final. Otherwise do actual
+ * processing.
+ */
+ if (trgmCNFA->overflowed)
+ state->fin = true;
+ else
+ processState(trgmCNFA, state);
+
+ /* Did we overflow? */
+ if (trgmCNFA->arcsCount > MAX_RESULT_ARCS ||
+ hash_get_num_entries(trgmCNFA->states) > MAX_RESULT_STATES)
+ {
+ trgmCNFA->overflowed = true;
+ }
+ }
+}
+
+
+/*---------------------
+ * Subroutines for expanding color trigrams into regular trigrams.
+ *---------------------
+ */
+
+/*
+ * Compare function for sorting of color trigrams by their colors.
+ */
+static int
+colorTrgmInfoCmp(const void *p1, const void *p2)
+{
+ const ColorTrgmInfo *c1 = (const ColorTrgmInfo *)p1;
+ const ColorTrgmInfo *c2 = (const ColorTrgmInfo *)p2;
+ return memcmp(c1->trgm, c2->trgm, sizeof(ColorTrgm));
+}
+
+/*
+ * Compare function for sorting color trigrams by descending of their simple
+ * trigrams counts.
+ */
+static int
+colorTrgmInfoCountCmp(const void *p1, const void *p2)
+{
+ const ColorTrgmInfo *c1 = (const ColorTrgmInfo *)p1;
+ const ColorTrgmInfo *c2 = (const ColorTrgmInfo *)p2;
+ if (c1->count < c2->count)
+ return 1;
+ else if (c1->count == c2->count)
+ return 0;
+ else
+ return -1;
+}
+
+/*
+ * Convert trigram into trgm datatype.
+ */
+static void
+fillTrgm(trgm *ptrgm, mb_char s[3])
+{
+ char text[14],
+ *p;
+ int i;
+
+ /* Write multibyte string into "text". */
+ p = text;
+ for (i = 0; i < 3; i++)
+ {
+ int len;
+ if (s[i] != 0)
+ {
+ len = strnlen((char *) &s[i], 4);
+ memcpy(p, &s[i], len);
+ p += len;
+ }
+ else
+ {
+ *p++ = ' ';
+ }
+ }
+ *p = 0;
+
+ /* Extract trigrams from "text" */
+ cnt_trigram(ptrgm, text, p - text);
+}
+
+/*
+ * Merge states of graph.
+ */
+static void
+mergeStates(TrgmState *state1, TrgmState *state2)
+{
+ ListCell *cell;
+
+ Assert(!state1->parent);
+ Assert(!state2->parent);
+ Assert(state1 != state2);
+
+ foreach(cell, state2->children)
+ {
+ TrgmState *state = (TrgmState *) lfirst(cell);
+ state->parent = state1;
+ }
+ state1->init = state1->init || state2->init;
+ state1->fin = state1->fin || state2->fin;
+ state2->parent = state1;
+ state1->children = list_concat(state1->children, state2->children);
+ state1->children = lappend(state1->children, state2);
+ state2->children = NIL;
+}
+
+/*
+ * Get vector of all color trigrams in graph and select which of them to expand
+ * into simple trigrams.
+ */
+static bool
+selectColorTrigrams(TrgmCNFA *trgmCNFA)
+{
+ HASH_SEQ_STATUS scan_status;
+ int arcsCount = trgmCNFA->arcsCount,
+ i;
+ TrgmState *state;
+ ColorTrgmInfo *p1, *p2, *colorTrgms;
+ int totalTrgmCount, number;
+
+ /* Collect color trigrams from all arcs */
+ colorTrgms = (ColorTrgmInfo *) palloc(sizeof(ColorTrgmInfo) * arcsCount);
+ i = 0;
+ hash_seq_init(&scan_status, trgmCNFA->states);
+ while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
+ {
+ ListCell *cell;
+ foreach(cell, state->arcs)
+ {
+ TrgmArc *arc = (TrgmArc *) lfirst(cell);
+ ArcInfo *arcInfo = (ArcInfo *) palloc(sizeof(ArcInfo));
+ arcInfo->source = state;
+ arcInfo->target = arc->target;
+ colorTrgms[i].arcs = list_make1(arcInfo);
+ colorTrgms[i].expanded = true;
+ memcpy(&colorTrgms[i].trgm, &arc->trgm, sizeof(ColorTrgm));
+ i++;
+ }
+ }
+ Assert(i == arcsCount);
+
+ /* Remove duplicates and merge arcs lists */
+ if (arcsCount >= 2)
+ {
+ qsort(colorTrgms, arcsCount, sizeof(ColorTrgmInfo), colorTrgmInfoCmp);
+ p1 = colorTrgms + 1;
+ p2 = colorTrgms;
+ while (p1 - colorTrgms < arcsCount)
+ {
+ if (memcmp(p1->trgm, p2->trgm, sizeof(ColorTrgm)) != 0)
+ {
+ p2++;
+ *p2 = *p1;
+ }
+ else
+ {
+ p2->arcs = list_concat(p2->arcs, p1->arcs);
+ }
+ p1++;
+ }
+ trgmCNFA->colorTrgmsCount = p2 + 1 - colorTrgms;
+ }
+ else
+ {
+ trgmCNFA->colorTrgmsCount = arcsCount;
+ }
+
+ /* Count number of simple trigrams in each color trigram */
+ totalTrgmCount = 0;
+ for (i = 0; i < trgmCNFA->colorTrgmsCount; i++)
+ {
+ int j, count = 1;
+ ColorTrgmInfo *trgmInfo = &colorTrgms[i];
+ for (j = 0; j < 3; j++)
+ {
+ /* FIXME: count could overflow */
+ if (trgmInfo->trgm[j] != EMPTY_COLOR)
+ count *= trgmCNFA->colorInfo[trgmInfo->trgm[j]].alphaCharsCount;
+ }
+ trgmInfo->count = count;
+ totalTrgmCount += count;
+ }
+
+ /* Sort color trigrams by descending of their simple trigram counts */
+ qsort(colorTrgms, trgmCNFA->colorTrgmsCount, sizeof(ColorTrgmInfo),
+ colorTrgmInfoCountCmp);
+ /*
+ * Remove color trigrams from the graph until total number of simple
+ * trigrams is below MAX_TRGM_COUNT. We start removing from largest color
+ * trigrams which are most promising for reduce total number of simple
+ * trigrams. When removing color trigram we have to merge states connected
+ * by corresponding arcs. It's necessary to not merge initial and final
+ * states, because our graph becomes useless in this case.
+ */
+ for (i = 0;
+ (i < trgmCNFA->colorTrgmsCount) && (totalTrgmCount > MAX_TRGM_COUNT);
+ i++)
+ {
+ ColorTrgmInfo *trgmInfo = &colorTrgms[i];
+ bool canRemove = true;
+ ListCell *cell;
+
+ /*
+ * Does any arc of with this color trigram connect initial and final
+ * states?
+ */
+ foreach(cell, trgmInfo->arcs)
+ {
+ ArcInfo *arcInfo = (ArcInfo *) lfirst(cell);
+ TrgmState *source = arcInfo->source, *target = arcInfo->target;
+ while (source->parent)
+ source = source->parent;
+ while (target->parent)
+ target = target->parent;
+ if ((source->init || target->init) && (source->fin || target->fin))
+ {
+ canRemove = false;
+ break;
+ }
+ }
+ if (!canRemove)
+ continue;
+
+ /* Merge states */
+ foreach(cell, trgmInfo->arcs)
+ {
+ ArcInfo *arcInfo = (ArcInfo *) lfirst(cell);
+ TrgmState *source = arcInfo->source, *target = arcInfo->target;
+ while (source->parent)
+ source = source->parent;
+ while (target->parent)
+ target = target->parent;
+ if (source != target)
+ mergeStates(source, target);
+ }
+
+ trgmInfo->expanded = false;
+ totalTrgmCount -= trgmInfo->count;
+ }
+ trgmCNFA->totalTrgmCount = totalTrgmCount;
+
+ /* Did we succeed in fitting into MAX_TRGM_COUNT? */
+ if (totalTrgmCount > MAX_TRGM_COUNT)
+ return false;
+
+ /*
+ * Sort color trigrams by colors (will be useful for bsearch) and enumerate
+ * expanded color trigrams.
+ */
+ number = 0;
+ qsort(colorTrgms, trgmCNFA->colorTrgmsCount, sizeof(ColorTrgmInfo),
+ colorTrgmInfoCmp);
+ for (i = 0; i < trgmCNFA->colorTrgmsCount; i++)
+ {
+ if (colorTrgms[i].expanded)
+ {
+ colorTrgms[i].number = number;
+ number++;
+ }
+ }
+
+ trgmCNFA->colorTrgms = colorTrgms;
+ return true;
+}
+
+/*
+ * Expand selected color trigrams into regular trigrams.
+ */
+static TRGM *
+expandColorTrigrams(TrgmCNFA *trgmCNFA)
+{
+ TRGM *trg;
+ trgm *p;
+ int i;
+ ColorInfo emptyColor;
+ mb_char emptyChar = 0;
+
+ /* Virtual "empty" color structure for representing zero character */
+ emptyColor.alphaCharsCount = 1;
+ emptyColor.alphaChars = &emptyChar;
+
+ trg = (TRGM *) palloc0(TRGMHDRSIZE +
+ trgmCNFA->totalTrgmCount * sizeof(trgm));
+ trg->flag = ARRKEY;
+ SET_VARSIZE(trg, CALCGTSIZE(ARRKEY, trgmCNFA->totalTrgmCount));
+ p = GETARR(trg);
+ for (i = 0; i < trgmCNFA->colorTrgmsCount; i++)
+ {
+ mb_char s[3];
+ ColorTrgmInfo *colorTrgm = &trgmCNFA->colorTrgms[i];
+ ColorInfo *c[3];
+ int j, i1, i2, i3;
+
+ if (!colorTrgm->expanded)
+ continue;
+
+ /* Get colors */
+ for (j = 0; j < 3; j++)
+ {
+ if (colorTrgm->trgm[j] != EMPTY_COLOR)
+ c[j] = &trgmCNFA->colorInfo[colorTrgm->trgm[j]];
+ else
+ c[j] = &emptyColor;
+ }
+
+ /* Iterate over all possible combinations of color characters */
+ for (i1 = 0; i1 < c[0]->alphaCharsCount; i1++)
+ {
+ s[0] = c[0]->alphaChars[i1];
+ for (i2 = 0; i2 < c[1]->alphaCharsCount; i2++)
+ {
+ s[1] = c[1]->alphaChars[i2];
+ for (i3 = 0; i3 < c[2]->alphaCharsCount; i3++)
+ {
+ s[2] = c[2]->alphaChars[i3];
+ fillTrgm(p, s);
+ p++;
+ }
+ }
+ }
+ }
+ return trg;
+}
+
+/*---------------------
+ * Subroutines for packing the graph into final representation
+ *---------------------
+ */
+
+/*
+ * Temporary structure for representing arc during packaging.
+ */
+typedef struct
+{
+ int sourceState;
+ int targetState;
+ int colorTrgm;
+} PackArcInfo;
+
+/*
+ * Comparison function for arcs during comparison. Compares arcs in following
+ * order: sourceState, colorTrgm, targetState.
+ */
+static int
+packArcInfoCmp(const void *a1, const void *a2)
+{
+ const PackArcInfo *p1 = (const PackArcInfo *) a1;
+ const PackArcInfo *p2 = (const PackArcInfo *) 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;
+}
+
+/*
+ * Pack resulting graph into final representation.
+ */
+static PackedGraph *
+packGraph(TrgmCNFA *trgmCNFA, MemoryContext context)
+{
+ int number = 2,
+ arcIndex,
+ arcsCount;
+ HASH_SEQ_STATUS scan_status;
+ TrgmState *state;
+ PackArcInfo *arcs, *p1, *p2;
+ PackedArc *packedArcs;
+ PackedGraph *result;
+ int i,
+ j;
+
+ /* Enumerate states */
+ hash_seq_init(&scan_status, trgmCNFA->states);
+ while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
+ {
+ while (state->parent)
+ state = state->parent;
+
+ if (state->number < 0)
+ {
+ if (state->init)
+ state->number = 0;
+ else if (state->fin)
+ state->number = 1;
+ else
+ {
+ state->number = number;
+ number++;
+ }
+ }
+ }
+
+ /* Collect array of all arcs */
+ arcs = (PackArcInfo *) palloc(sizeof(PackArcInfo) * trgmCNFA->arcsCount);
+ arcIndex = 0;
+ hash_seq_init(&scan_status, trgmCNFA->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->number != target->number)
+ {
+ arcs[arcIndex].sourceState = source->number;
+ arcs[arcIndex].targetState = target->number;
+ arcs[arcIndex].colorTrgm = ((ColorTrgmInfo *)bsearch(&arc->trgm,
+ trgmCNFA->colorTrgms, trgmCNFA->colorTrgmsCount,
+ sizeof(ColorTrgmInfo), colorTrgmInfoCmp))->number;
+
+ arcIndex++;
+ }
+ }
+ }
+ qsort(arcs, arcIndex, sizeof(PackArcInfo), packArcInfoCmp);
+
+ /* We could have duplicates because states were merged. Remove them. */
+ p1 = p2 = arcs;
+ while (p1 < arcs + arcIndex)
+ {
+ if (packArcInfoCmp(p1, p2) > 0)
+ {
+ p2++;
+ *p2 = *p1;
+ }
+ p1++;
+ }
+ arcsCount = p2 - arcs + 1;
+
+ /* Write packed representation */
+ result = (PackedGraph *) MemoryContextAlloc(context, sizeof(PackedGraph));
+
+ /* Pack color trigrams information */
+ result->colorTrigramsCount = 0;
+ for (i = 0; i < trgmCNFA->colorTrgmsCount; i++)
+ if (trgmCNFA->colorTrgms[i].expanded)
+ result->colorTrigramsCount++;
+ result->colorTrigramGroups = (int *) MemoryContextAlloc(context,
+ sizeof(int) * result->colorTrigramsCount);
+ j = 0;
+ for (i = 0; i < trgmCNFA->colorTrgmsCount; i++)
+ {
+ if (trgmCNFA->colorTrgms[i].expanded)
+ {
+ result->colorTrigramGroups[j] = trgmCNFA->colorTrgms[i].count;
+ j++;
+ }
+ }
+
+ /* Pack states and arcs information */
+ result->states = (PackedState *) MemoryContextAlloc(context,
+ number * sizeof(PackedState));
+ result->statesCount = number;
+ packedArcs = (PackedArc *) MemoryContextAlloc(context,
+ arcsCount * sizeof(PackedArc));
+ j = 0;
+ for (i = 0; i < number; 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 memory for evaluation */
+ result->colorTrigramsActive = (bool *) MemoryContextAlloc(context,
+ sizeof(bool) * result->colorTrigramsCount);
+ result->statesActive = (bool *) MemoryContextAlloc(context,
+ sizeof(bool) * result->statesCount);
+
+ return result;
+}
+
+
+/*---------------------
+ * Debugging functions
+ *---------------------
+ */
+
+#ifdef TRGM_REGEXP_DEBUG
+/*
+ * Print initial CNFA, in regexp library's representation
+ */
+static void
+printSourceCNFA(struct cnfa *cnfa, ColorInfo *colors, int ncolors)
+{
+ int state;
+ StringInfoData buf;
+ int i;
+
+ initStringInfo(&buf);
+
+ appendStringInfo(&buf, "\ndigraph sourceCNFA {\n");
+
+ for (state = 0; state < cnfa->nstates; state++)
+ {
+ struct carc *s = cnfa->states[state];
+
+ appendStringInfo(&buf, "s%d", state);
+ if (cnfa->post == state)
+ appendStringInfo(&buf, " [shape = doublecircle]");
+ appendStringInfo(&buf, ";\n");
+
+ while (s->co != COLORLESS)
+ {
+ appendStringInfo(&buf, " s%d -> s%d [label = \"%d\"];\n",
+ state, s->to, s->co);
+ s++;
+ }
+ }
+
+ appendStringInfo(&buf, " node [shape = point ]; initial;\n");
+ appendStringInfo(&buf, " initial -> s%d;\n", cnfa->pre);
+
+ /* Print colors */
+ appendStringInfo(&buf, " { rank = sink;\n");
+ appendStringInfo(&buf, " Colors [shape = none, margin=0, label=<\n");
+
+ for (i = 0; i < ncolors; i++)
+ {
+ ColorInfo *color = &colors[i];
+ int j;
+
+ appendStringInfo(&buf, "
Color %d: ", i);
+
+ if (!color->expandable)
+ appendStringInfo(&buf, "not expandable");
+ else
+ {
+ for (j = 0; j < color->alphaCharsCount; j++)
+ {
+ char s[5];
+ memcpy(s, (char *) &color->alphaChars[j], 4);
+ s[4] = '\0';
+ appendStringInfo(&buf, "%s", s);
+ }
+ }
+ appendStringInfo(&buf, "\n");
+ }
+
+ appendStringInfo(&buf, " >];\n");
+ appendStringInfo(&buf, " }\n");
+
+
+ appendStringInfo(&buf, "}\n");
+
+ {
+ /* dot -Tpng -o /tmp/source.png < /tmp/source.dot */
+ FILE *fp = fopen("/tmp/source.dot", "w");
+ fprintf(fp, "%s", buf.data);
+ fclose(fp);
+ }
+
+ pfree(buf.data);
+}
+
+/*
+ * Print trigram-based CNFA-like graph.
+ */
+static void
+printTrgmCNFA(TrgmCNFA *trgmCNFA)
+{
+ StringInfoData buf;
+ HASH_SEQ_STATUS scan_status;
+ TrgmState *state;
+ TrgmState *initstate = NULL;
+
+ initStringInfo(&buf);
+
+ appendStringInfo(&buf, "\ndigraph transformedCNFA {\n");
+
+ hash_seq_init(&scan_status, trgmCNFA->states);
+ while ((state = (TrgmState *) hash_seq_search(&scan_status)) != NULL)
+ {
+ ListCell *cell;
+
+ appendStringInfo(&buf, "s%p", state);
+ if (state->fin)
+ appendStringInfo(&buf, " [shape = doublecircle]");
+ if (state->init)
+ initstate = state;
+ appendStringInfo(&buf, " [label = \"%d\"]", state->enterKey.nstate);
+ appendStringInfo(&buf, ";\n");
+
+ foreach(cell, state->arcs)
+ {
+ TrgmArc *arc = (TrgmArc *) lfirst(cell);
+
+ appendStringInfo(&buf, " s%p -> s%p [label = \"%d %d %d\"];\n",
+ (void *) state, (void *) arc->target,
+ (uint32) arc->trgm[0], (uint32) arc->trgm[1], (uint32) arc->trgm[2]);
+ }
+ }
+
+ if (initstate)
+ {
+ appendStringInfo(&buf, " node [shape = point ]; initial;\n");
+ appendStringInfo(&buf, " initial -> s%p;\n", (void *) initstate);
+ }
+ appendStringInfo(&buf, "}\n");
+
+ {
+ /* dot -Tpng -o /tmp/transformed.png < /tmp/transformed.dot */
+ FILE *fp = fopen("/tmp/transformed.dot", "w");
+ fprintf(fp, "%s", buf.data);
+ fclose(fp);
+ }
+
+ pfree(buf.data);
+}
+
+/*
+ * Print final packed representation of resulting trigram-based CNFA-like graph.
+ */
+static void
+printPackedGraph(PackedGraph *packedGraph, TRGM *trigrams)
+{
+ int i;
+ trgm *p;
+ StringInfoData buf;
+ initStringInfo(&buf);
+
+ appendStringInfo(&buf, "\ndigraph packedGraph {\n");
+
+ for (i = 0; i < packedGraph->statesCount; i++)
+ {
+ PackedState *state = &packedGraph->states[i];
+ int j;
+
+ appendStringInfo(&buf, " s%d", i);
+ if (i == 1)
+ appendStringInfo(&buf, " [shape = doublecircle]");
+
+ appendStringInfo(&buf, " [label = ];\n", i);
+
+ for (j = 0; j < state->arcsCount; j++)
+ {
+ PackedArc *arc = &state->arcs[j];
+ appendStringInfo(&buf, " s%d -> s%d [label = \"trigram %d\"];\n",
+ i, arc->targetState, arc->colorTrgm);
+ }
+ }
+
+ appendStringInfo(&buf, " node [shape = point ]; initial;\n");
+ appendStringInfo(&buf, " initial -> s%d;\n", 0);
+
+ /* Print trigrams */
+ appendStringInfo(&buf, " { rank = sink;\n");
+ appendStringInfo(&buf, " Trigrams [shape = none, margin=0, label=<\n");
+
+ p = GETARR(trigrams);
+ for (i = 0; i < packedGraph->colorTrigramsCount; i++)
+ {
+ int count = packedGraph->colorTrigramGroups[i];
+ int j;
+
+ appendStringInfo(&buf, "
Trigram %d: ", i);
+
+ for (j = 0; j < count; j++)
+ {
+ if (j > 0)
+ appendStringInfo(&buf, ", ");
+ appendStringInfo(&buf, "\"%c%c%c\"", (*p)[0], (*p)[1], (*p)[2]);
+ p++;
+ }
+ }
+ appendStringInfo(&buf, " >];\n");
+ appendStringInfo(&buf, " }\n");
+
+ appendStringInfo(&buf, "}\n");
+
+ {
+ /* dot -Tpng -o /tmp/packed.png < /tmp/packed.dot */
+ FILE *fp = fopen("/tmp/packed.dot", "w");
+ fprintf(fp, "%s", buf.data);
+ fclose(fp);
+ }
+
+ pfree(buf.data);
+}
+#endif
diff --git a/doc/src/sgml/pgtrgm.sgml b/doc/src/sgml/pgtrgm.sgml
index 30e5355..c4105e1 100644
--- a/doc/src/sgml/pgtrgm.sgml
+++ b/doc/src/sgml/pgtrgm.sgml
@@ -145,9 +145,10 @@
operator classes that allow you to create an index over a text column for
the purpose of very fast similarity searches. These index types support
the above-described similarity operators, and additionally support
- trigram-based index searches for LIKE and ILIKE
- queries. (These indexes do not support equality nor simple comparison
- operators, so you may need a regular B-tree index too.)
+ trigram-based index searches for LIKE, ILIKE,
+ ~ and ~* queries. (These indexes do not
+ support equality nor simple comparison operators, so you may need a
+ regular B-tree index too.)
@@ -203,6 +204,23 @@ SELECT * FROM test_trgm WHERE t LIKE '%foo%bar';
+ Beginning in PostgreSQL 9.3, these index types also support
+ index searches for ~ and ~* (regular expression
+ matching), for example
+
+SELECT * FROM test_trgm WHERE t ~ '(foo|bar)';
+
+ The index search works by extracting trigrams from the regular expression
+ and then looking these up in the index. The more trigrams could be
+ extracted from regular expression, the more effective the index search is.
+ Unlike B-tree based searches, the search string need not be left-anchored.
+ However, sometimes regular expression is too complex for analysis, then
+ it performs the same as when no trigrams can be extracted from regular
+ expression. In this situation full index scan or sequential scan will
+ be performed depending on query plan.
+
+
+
The choice between GiST and GIN indexing depends on the relative
performance characteristics of GiST and GIN, which are discussed elsewhere.
As a rule of thumb, a GIN index is faster to search than a GiST index, but
diff --git a/src/backend/utils/adt/regexp.c b/src/backend/utils/adt/regexp.c
index 6a89fab..e29e734 100644
--- a/src/backend/utils/adt/regexp.c
+++ b/src/backend/utils/adt/regexp.c
@@ -128,7 +128,7 @@ static Datum build_regexp_split_result(regexp_matches_ctx *splitctx);
* Pattern is given in the database encoding. We internally convert to
* an array of pg_wchar, which is what Spencer's regex package wants.
*/
-static regex_t *
+regex_t *
RE_compile_and_cache(text *text_re, int cflags, Oid collation)
{
int text_re_len = VARSIZE_ANY_EXHDR(text_re);
diff --git a/src/include/regex/regex.h b/src/include/regex/regex.h
index 616c2c6..7e19e8a 100644
--- a/src/include/regex/regex.h
+++ b/src/include/regex/regex.h
@@ -171,5 +171,6 @@ extern int pg_regprefix(regex_t *, pg_wchar **, size_t *);
extern void pg_regfree(regex_t *);
extern size_t pg_regerror(int, const regex_t *, char *, size_t);
extern void pg_set_regex_collation(Oid collation);
+regex_t *RE_compile_and_cache(text *text_re, int cflags, Oid collation);
#endif /* _REGEX_H_ */