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

Nikita Glukhov <n.gluhov@postgrespro.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