Re: fix for BUG #3720: wrong results at using ltree

Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru> writes:
> And we even can simply transform this tail call into a loop:

> -if (tlen > 0 && qlen > 0)
> +while (tlen > 0 && qlen > 0)

Yeah, the same occurred to me ... and then we can drop the other loop too.
I've got it down to this now:

/*
* Try to match an lquery (of qlen items) to an ltree (of tlen items)
*/
static bool
checkCond(lquery_level *curq, int qlen,
ltree_level *curt, int tlen)
{
/* Since this function recurses, it could be driven to stack overflow */
check_stack_depth();

/* Loop while we have query items to consider */
while (qlen > 0)
{
int low,
high;
lquery_level *nextq;

/*
* Get min and max repetition counts for this query item, dealing with
* the backwards-compatibility hack that the low/high fields aren't
* meaningful for non-'*' items unless LQL_COUNT is set.
*/
if ((curq->flag & LQL_COUNT) || curq->numvar == 0)
low = curq->low, high = curq->high;
else
low = high = 1;

/*
* We may limit "high" to the remaining text length; this avoids
* separate tests below.
*/
if (high > tlen)
high = tlen;

/* Fail if a match of required number of items is impossible */
if (high < low)
return false;

/*
* Recursively check the rest of the pattern against each possible
* start point following some of this item's match(es).
*/
nextq = LQL_NEXT(curq);
qlen--;

for (int matchcnt = 0; matchcnt < high; matchcnt++)
{
/*
* If we've consumed an acceptable number of matches of this item,
* and the rest of the pattern matches beginning here, we're good.
*/
if (matchcnt >= low && checkCond(nextq, qlen, curt, tlen))
return true;

/*
* Otherwise, try to match one more text item to this query item.
*/
if (!checkLevel(curq, curt))
return false;

curt = LEVEL_NEXT(curt);
tlen--;
}

/*
* Once we've consumed "high" matches, we can succeed only if the rest
* of the pattern matches beginning here. Loop around (if you prefer,
* think of this as tail recursion).
*/
curq = nextq;
}

/*
* Once we're out of query items, we match only if there's no remaining
* text either.
*/
return (tlen == 0);
}

regards, tom lane