Fix strange behavior (and possible crashes) in full text phrase search.

In an attempt to simplify the tsquery matching engine, the original
phrase search patch invented rewrite rules that would rearrange a
tsquery so that no AND/OR/NOT operator appeared below a PHRASE operator.
But this approach had numerous problems.  The rearrangement step was
missed by ts_rewrite (and perhaps other places), allowing tsqueries
to be created that would cause Assert failures or perhaps crashes at
execution, as reported by Andreas Seltenreich.  The rewrite rules
effectively defined semantics for operators underneath PHRASE that were
buggy, or at least unintuitive.  And because rewriting was done in
tsqueryin() rather than at execution, the rearrangement was user-visible,
which is not very desirable --- for example, it might cause unexpected
matches or failures to match in ts_rewrite.

As a somewhat independent problem, the behavior of nested PHRASE operators
was only sane for left-deep trees; queries like "x <-> (y <-> z)" did not
behave intuitively at all.

To fix, get rid of the rewrite logic altogether, and instead teach the
tsquery execution engine to manage AND/OR/NOT below a PHRASE operator
by explicitly computing the match location(s) and match widths for these
operators.

This requires introducing some additional fields into the publicly visible
ExecPhraseData struct; but since there's no way for third-party code to
pass such a struct to TS_phrase_execute, it shouldn't create an ABI problem
as long as we don't move the offsets of the existing fields.

Another related problem was that index searches supposed that "!x <-> y"
could be lossily approximated as "!x & y", which isn't correct because
the latter will reject, say, "x q y" which the query itself accepts.
This required some tweaking in TS_execute_ternary along with the main
tsquery engine.

Back-patch to 9.6 where phrase operators were introduced.  While this
could be argued to change behavior more than we'd like in a stable branch,
we have to do something about the crash hazards and index-vs-seqscan
inconsistency, and it doesn't seem desirable to let the unintuitive
behaviors induced by the rewriting implementation stand as precedent.

Discussion: https://postgr.es/m/28215.1481999808@sss.pgh.pa.us
Discussion: https://postgr.es/m/26706.1482087250@sss.pgh.pa.us

1 files changed, 4 insertions, 238 deletions

diff --git a/src/backend/utils/adt/tsquery_cleanup.c b/src/backend/utils/adt/tsquery_cleanup.c
index 330664da639..c10c7ef0aa5 100644
--- a/src/backend/utils/adt/tsquery_cleanup.c
+++ b/src/backend/utils/adt/tsquery_cleanup.c
@@ -26,19 +26,6 @@ typedef struct NODE
 } NODE;
 
 /*
- * To simplify walking on query tree and pushing down of phrase operator
- * we define some fake priority here: phrase operator has highest priority
- * of any other operators (and we believe here that OP_PHRASE is a highest
- * code of operations) and value node has ever highest priority.
- * Priority values of other operations don't matter until they are less than
- * phrase operator and value node.
- */
-#define VALUE_PRIORITY			(OP_COUNT + 1)
-#define NODE_PRIORITY(x) \
-	( ((x)->valnode->qoperator.type == QI_OPR) ? \
-		(x)->valnode->qoperator.oper : VALUE_PRIORITY )
-
-/*
  * make query tree from plain view of query
  */
 static NODE *
@@ -368,227 +355,6 @@ clean_stopword_intree(NODE *node, int *ladd, int *radd)
 	return node;
 }
 
-static NODE *
-copyNODE(NODE *node)
-{
-	NODE	   *cnode = palloc(sizeof(NODE));
-
-	/* since this function recurses, it could be driven to stack overflow. */
-	check_stack_depth();
-
-	cnode->valnode = palloc(sizeof(QueryItem));
-	*(cnode->valnode) = *(node->valnode);
-
-	if (node->valnode->type == QI_OPR)
-	{
-		cnode->right = copyNODE(node->right);
-		if (node->valnode->qoperator.oper != OP_NOT)
-			cnode->left = copyNODE(node->left);
-	}
-
-	return cnode;
-}
-
-static NODE *
-makeNODE(int8 op, NODE *left, NODE *right)
-{
-	NODE	   *node = palloc(sizeof(NODE));
-
-	/* zeroing allocation to prevent difference in unused bytes */
-	node->valnode = palloc0(sizeof(QueryItem));
-
-	node->valnode->qoperator.type = QI_OPR;
-	node->valnode->qoperator.oper = op;
-
-	node->left = left;
-	node->right = right;
-
-	return node;
-}
-
-/*
- * Move operation with high priority to the leaves. This guarantees
- * that the phrase operator will be near the bottom of the tree.
- * An idea behind is do not store position of lexemes during execution
- * of ordinary operations (AND, OR, NOT) because it could be expensive.
- * Actual transformation will be performed only on subtrees under the
- * <-> (<n>) operation since it's needed solely for the phrase operator.
- *
- * Rules:
- *	  a  <->  (b | c)	=>	(a <-> b)  |   (a <-> c)
- *	 (a | b)  <->	 c	   =>	(a <-> c)  |   (b <-> c)
- *	  a  <->	!b	   =>		a	  &  !(a <-> b)
- *	 !a  <->	 b	   =>		b	  &  !(a <-> b)
- *
- * Warnings for readers:
- *		  a <-> b	   !=	   b <-> a
- *
- *	  a <n> (b <n> c)	!=	 (a <n> b) <n> c since the phrase lengths are:
- *			 n					2n-1
- */
-static NODE *
-normalize_phrase_tree(NODE *node)
-{
-	/* there should be no stop words at this point */
-	Assert(node->valnode->type != QI_VALSTOP);
-
-	if (node->valnode->type == QI_VAL)
-		return node;
-
-	/* since this function recurses, it could be driven to stack overflow. */
-	check_stack_depth();
-
-	Assert(node->valnode->type == QI_OPR);
-
-	if (node->valnode->qoperator.oper == OP_NOT)
-	{
-		NODE	   *orignode = node;
-
-		/* eliminate NOT sequence */
-		while (node->valnode->type == QI_OPR &&
-		node->valnode->qoperator.oper == node->right->valnode->qoperator.oper)
-		{
-			node = node->right->right;
-		}
-
-		if (orignode != node)
-			/* current node isn't checked yet */
-			node = normalize_phrase_tree(node);
-		else
-			node->right = normalize_phrase_tree(node->right);
-	}
-	else if (node->valnode->qoperator.oper == OP_PHRASE)
-	{
-		int16		distance;
-		NODE	   *X;
-
-		node->left = normalize_phrase_tree(node->left);
-		node->right = normalize_phrase_tree(node->right);
-
-		/*
-		 * if subtree contains only nodes with higher "priority" then we are
-		 * done. See comment near NODE_PRIORITY()
-		 */
-		if (NODE_PRIORITY(node) <= NODE_PRIORITY(node->right) &&
-			NODE_PRIORITY(node) <= NODE_PRIORITY(node->left))
-			return node;
-
-		/*
-		 * We can't swap left-right and works only with left child because of
-		 * a <-> b	!=	b <-> a
-		 */
-
-		distance = node->valnode->qoperator.distance;
-
-		if (node->right->valnode->type == QI_OPR)
-		{
-			switch (node->right->valnode->qoperator.oper)
-			{
-				case OP_AND:
-					/* a <-> (b & c)  =>  (a <-> b) & (a <-> c) */
-					node = makeNODE(OP_AND,
-									makeNODE(OP_PHRASE,
-											 node->left,
-											 node->right->left),
-									makeNODE(OP_PHRASE,
-											 copyNODE(node->left),
-											 node->right->right));
-					node->left->valnode->qoperator.distance =
-						node->right->valnode->qoperator.distance = distance;
-					break;
-				case OP_OR:
-					/* a <-> (b | c)  =>  (a <-> b) | (a <-> c) */
-					node = makeNODE(OP_OR,
-									makeNODE(OP_PHRASE,
-											 node->left,
-											 node->right->left),
-									makeNODE(OP_PHRASE,
-											 copyNODE(node->left),
-											 node->right->right));
-					node->left->valnode->qoperator.distance =
-						node->right->valnode->qoperator.distance = distance;
-					break;
-				case OP_NOT:
-					/* a <-> !b  =>  a & !(a <-> b) */
-					X = node->right;
-					node->right = node->right->right;
-					X->right = node;
-					node = makeNODE(OP_AND,
-									copyNODE(node->left),
-									X);
-					break;
-				case OP_PHRASE:
-					/* no-op */
-					break;
-				default:
-					elog(ERROR, "Wrong type of tsquery node: %d",
-						 node->right->valnode->qoperator.oper);
-			}
-		}
-
-		if (node->left->valnode->type == QI_OPR &&
-			node->valnode->qoperator.oper == OP_PHRASE)
-		{
-			/*
-			 * if the node is still OP_PHRASE, check the left subtree,
-			 * otherwise the whole node will be transformed later.
-			 */
-			switch (node->left->valnode->qoperator.oper)
-			{
-				case OP_AND:
-					/* (a & b) <-> c  =>  (a <-> c) & (b <-> c) */
-					node = makeNODE(OP_AND,
-									makeNODE(OP_PHRASE,
-											 node->left->left,
-											 node->right),
-									makeNODE(OP_PHRASE,
-											 node->left->right,
-											 copyNODE(node->right)));
-					node->left->valnode->qoperator.distance =
-						node->right->valnode->qoperator.distance = distance;
-					break;
-				case OP_OR:
-					/* (a | b) <-> c  =>  (a <-> c) | (b <-> c) */
-					node = makeNODE(OP_OR,
-									makeNODE(OP_PHRASE,
-											 node->left->left,
-											 node->right),
-									makeNODE(OP_PHRASE,
-											 node->left->right,
-											 copyNODE(node->right)));
-					node->left->valnode->qoperator.distance =
-						node->right->valnode->qoperator.distance = distance;
-					break;
-				case OP_NOT:
-					/* !a <-> b  =>  b & !(a <-> b) */
-					X = node->left;
-					node->left = node->left->right;
-					X->right = node;
-					node = makeNODE(OP_AND,
-									X,
-									copyNODE(node->right));
-					break;
-				case OP_PHRASE:
-					/* no-op */
-					break;
-				default:
-					elog(ERROR, "Wrong type of tsquery node: %d",
-						 node->left->valnode->qoperator.oper);
-			}
-		}
-
-		/* continue transformation */
-		node = normalize_phrase_tree(node);
-	}
-	else	/* AND or OR */
-	{
-		node->left = normalize_phrase_tree(node->left);
-		node->right = normalize_phrase_tree(node->right);
-	}
-
-	return node;
-}
-
 /*
  * Number of elements in query tree
  */
@@ -613,8 +379,11 @@ calcstrlen(NODE *node)
 	return size;
 }
 
+/*
+ * Remove QI_VALSTOP (stopword) nodes from TSQuery.
+ */
 TSQuery
-cleanup_fakeval_and_phrase(TSQuery in)
+cleanup_tsquery_stopwords(TSQuery in)
 {
 	int32		len,
 				lenstr,
@@ -642,9 +411,6 @@ cleanup_fakeval_and_phrase(TSQuery in)
 		return out;
 	}
 
-	/* push OP_PHRASE nodes down */
-	root = normalize_phrase_tree(root);
-
 	/*
 	 * Build TSQuery from plain view
 	 */