trgm-regexp-0.9-heikki-1.patch

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, "<br/>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 = <s%d>];\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, "<br/>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 <literal>LIKE</> and <literal>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 <literal>LIKE</>, <literal>ILIKE</>,
+   <literal>~</> and <literal>~*</> queries.  (These indexes do not
+   support equality nor simple comparison operators, so you may need a
+   regular B-tree index too.)
   </para>
 
   <para>
@@ -203,6 +204,23 @@ SELECT * FROM test_trgm WHERE t LIKE '%foo%bar';
   </para>
 
   <para>
+   Beginning in <productname>PostgreSQL</> 9.3, these index types also support
+   index searches for <literal>~</> and <literal>~*</> (regular expression
+   matching), for example
+<programlisting>
+SELECT * FROM test_trgm WHERE t ~ '(foo|bar)';
+</programlisting>
+   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.   
+  </para>
+  
+  <para>
    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_ */