From: Tom Lane <tgl@sss.pgh.pa.us>
To: Nikita Glukhov <n.gluhov@postgrespro.ru>
cc: Pgsql Hackers <pgsql-hackers@postgresql.org>,
        =?UTF-8?Q?Filip_Rembia=c5=82kowski?= <filip.rembialkowski@gmail.com>,
        Tomas Vondra <tomas.vondra@2ndquadrant.com>,
        Alexander Korotkov <a.korotkov@postgrespro.ru>,
        Oleg Bartunov <obartunov@postgrespro.ru>,
        Thomas Munro <thomas.munro@gmail.com>,
        Teodor Sigaev <teodor@sigaev.ru>
Subject: Re: fix for BUG #3720: wrong results at using ltree
In-reply-to: <9247ddc2-d1e0-7d62-55a6-62a089e99a8a@postgrespro.ru>
References: 
 <CAP_rww=waX2Oo6q+MbMSiZ9ktdj6eaJj0cQzNu=Ry2cCDij5fw@mail.gmail.com>
 <28639.1554565562@sss.pgh.pa.us>
 <CA+hUKGKVbTGHGpHBX6EGew13CrfYcagThJqBAmeATCMKnVqisQ@mail.gmail.com>
 <CAF4Au4yV8vsgA_7XCce4kFUa2BjseqWj=KVuOwcE+DGLj6AW7g@mail.gmail.com>
 <5eedfd9e-2f14-a2df-3bd9-4c92eb0f08a5@postgrespro.ru>
 <CAPpHfdsvEaqXDsLWebQ4Q4GszRZ_P6h-1_cidmiqPMtWzXnmhA@mail.gmail.com>
 <20200124182915.zz7hzdkijzsb4ic4@development>
 <a315c67d-5b3b-8005-99ef-daa9ea7036a0@postgrespro.ru>
 <19375.1585438012@sss.pgh.pa.us> <15582.1585529626@sss.pgh.pa.us>
 <23304.1585591242@sss.pgh.pa.us>
 <943dc224-eb82-8abd-15c3-f4b516f89767@postgrespro.ru>
 <3007.1585605566@sss.pgh.pa.us> <3843.1585606362@sss.pgh.pa.us>
 <9247ddc2-d1e0-7d62-55a6-62a089e99a8a@postgrespro.ru>
Comments: In-reply-to Nikita Glukhov <n.gluhov@postgrespro.ru>
	message dated "Tue, 31 Mar 2020 01:22:19 +0300"
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <5209.1585607748.1@sss.pgh.pa.us>
Date: Mon, 30 Mar 2020 18:35:48 -0400
Message-ID: <5210.1585607748@sss.pgh.pa.us>
Precedence: bulk

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