0006-rewrite-hlCover.patch

diff --git a/src/backend/tsearch/wparser_def.c b/src/backend/tsearch/wparser_def.c
index 2f84259..6bf7e49 100644
--- a/src/backend/tsearch/wparser_def.c
+++ b/src/backend/tsearch/wparser_def.c
@@ -1966,75 +1966,97 @@ checkcondition_HL(void *opaque, QueryOperand *val, ExecPhraseData *data)
 	return false;
 }
 
-
-static bool
-hlCover(HeadlineParsedText *prs, TSQuery query, int *p, int *q)
+/*
+ * hlFirstIndex: find first index >= pos containing any word used in query
+ *
+ * Returns -1 if no such index
+ */
+static int
+hlFirstIndex(HeadlineParsedText *prs, TSQuery query, int pos)
 {
-	int			i,
-				j;
-	QueryItem  *item = GETQUERY(query);
-	int			pos = *p;
-
-	*q = -1;
-	*p = INT_MAX;
+	int			i;
 
-	for (j = 0; j < query->size; j++)
+	/* For each word ... */
+	for (i = pos; i < prs->curwords; i++)
 	{
-		if (item->type != QI_VAL)
+		/* ... scan the query to see if this word matches any operand */
+		QueryItem  *item = GETQUERY(query);
+		int			j;
+
+		for (j = 0; j < query->size; j++)
 		{
+			if (item->type == QI_VAL &&
+				prs->words[i].item == &item->qoperand)
+				return i;
 			item++;
-			continue;
 		}
-		for (i = pos; i < prs->curwords; i++)
-		{
-			if (prs->words[i].item == &item->qoperand)
-			{
-				if (i > *q)
-					*q = i;
-				break;
-			}
-		}
-		item++;
 	}
+	return -1;
+}
 
-	if (*q < 0)
-		return false;
+/*
+ * hlCover: try to find a substring of prs' word list that satisfies query
+ *
+ * At entry, *p must be the first word index to consider (initialize this to
+ * zero, or to the next index after a previous successful search).
+ *
+ * On success, sets *p to first word index and *q to last word index of the
+ * cover substring, and returns true.
+ *
+ * The result is a minimal cover, in the sense that both *p and *q will be
+ * words used in the query.
+ */
+static bool
+hlCover(HeadlineParsedText *prs, TSQuery query, int *p, int *q)
+{
+	int			pmin,
+				pmax,
+				nextpmin,
+				nextpmax;
+	hlCheck		ch;
 
-	item = GETQUERY(query);
-	for (j = 0; j < query->size; j++)
+	/*
+	 * We look for the earliest, shortest substring of prs->words that
+	 * satisfies the query.  Both the pmin and pmax indices must be words
+	 * appearing in the query; there's no point in trying endpoints in between
+	 * such points.
+	 */
+	pmin = hlFirstIndex(prs, query, *p);
+	while (pmin >= 0)
 	{
-		if (item->type != QI_VAL)
+		/* This useless assignment just keeps stupider compilers quiet */
+		nextpmin = -1;
+		/* Consider substrings starting at pmin */
+		ch.words = &(prs->words[pmin]);
+		/* Consider the length-one substring first, then longer substrings */
+		pmax = pmin;
+		do
 		{
-			item++;
-			continue;
-		}
-		for (i = *q; i >= pos; i--)
-		{
-			if (prs->words[i].item == &item->qoperand)
+			/* Try to match query against pmin .. pmax substring */
+			ch.len = pmax - pmin + 1;
+			if (TS_execute(GETQUERY(query), &ch,
+						   TS_EXEC_EMPTY, checkcondition_HL))
 			{
-				if (i < *p)
-					*p = i;
-				break;
+				*p = pmin;
+				*q = pmax;
+				return true;
 			}
-		}
-		item++;
-	}
-
-	if (*p <= *q)
-	{
-		hlCheck		ch;
+			/* Nope, so advance pmax to next feasible endpoint */
+			nextpmax = hlFirstIndex(prs, query, pmax + 1);
 
-		ch.words = &(prs->words[*p]);
-		ch.len = *q - *p + 1;
-		if (TS_execute(GETQUERY(query), &ch, TS_EXEC_EMPTY, checkcondition_HL))
-			return true;
-		else
-		{
-			(*p)++;
-			return hlCover(prs, query, p, q);
+			/*
+			 * If this is our first advance past pmin, then the result is also
+			 * the next feasible value of pmin; remember it to save a
+			 * redundant search.
+			 */
+			if (pmax == pmin)
+				nextpmin = nextpmax;
+			pmax = nextpmax;
 		}
+		while (pmax >= 0);
+		/* No luck here, so try next feasible startpoint */
+		pmin = nextpmin;
 	}
-
 	return false;
 }
 
diff --git a/src/test/regress/expected/tsearch.out b/src/test/regress/expected/tsearch.out
index 36e995b..d6e0ba6 100644
--- a/src/test/regress/expected/tsearch.out
+++ b/src/test/regress/expected/tsearch.out
@@ -1301,12 +1301,12 @@ Water, water, every where,
   Nor any drop to drink.
 S. T. Coleridge (1772-1834)
 ', phraseto_tsquery('english', 'painted Ocean'));
-           ts_headline            
-----------------------------------
- <b>painted</b> <b>Ocean</b>.    +
- Water, water, every where       +
-   And all the boards did shrink;+
- Water, water, every
+              ts_headline              
+---------------------------------------
+ <b>painted</b> Ship                  +
+   Upon a <b>painted</b> <b>Ocean</b>.+
+ Water, water, every where            +
+   And all the boards did shrink
 (1 row)
 
 SELECT ts_headline('english', '
@@ -1332,9 +1332,9 @@ SELECT ts_headline('english',
 'Lorem ipsum urna.  Nullam nullam ullamcorper urna.',
 to_tsquery('english','Lorem') && phraseto_tsquery('english','ullamcorper urna'),
 'MaxWords=100, MinWords=1');
- ts_headline  
---------------
- <b>Lorem</b>
+                                  ts_headline                                  
+-------------------------------------------------------------------------------
+ <b>Lorem</b> ipsum <b>urna</b>.  Nullam nullam <b>ullamcorper</b> <b>urna</b>
 (1 row)
 
 SELECT ts_headline('english', '
@@ -1379,9 +1379,9 @@ SELECT ts_headline('simple', '1 2 3 1 3'::text, '1 & 3', 'MaxWords=4, MinWords=1
 (1 row)
 
 SELECT ts_headline('simple', '1 2 3 1 3'::text, '1 <-> 3', 'MaxWords=4, MinWords=1');
-    ts_headline    
--------------------
- <b>1</b> <b>3</b>
+        ts_headline         
+----------------------------
+ <b>3</b> <b>1</b> <b>3</b>
 (1 row)
 
 --Check if headline fragments work
@@ -1481,9 +1481,9 @@ SELECT ts_headline('english',
 'Lorem ipsum urna.  Nullam nullam ullamcorper urna.',
 to_tsquery('english','Lorem') && phraseto_tsquery('english','ullamcorper urna'),
 'MaxFragments=100, MaxWords=100, MinWords=1');
- ts_headline  
---------------
- <b>Lorem</b>
+                                  ts_headline                                  
+-------------------------------------------------------------------------------
+ <b>Lorem</b> ipsum <b>urna</b>.  Nullam nullam <b>ullamcorper</b> <b>urna</b>
 (1 row)
 
 --Rewrite sub system