From: Tom Lane <tgl@sss.pgh.pa.us>
To: Nikita Glukhov <n.gluhov@postgrespro.ru>
Cc: Pgsql Hackers <pgsql-hackers@postgresql.org>
Cc: Filip Rembiałkowski <filip.rembialkowski@gmail.com>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Alexander Korotkov <a.korotkov@postgrespro.ru>
Cc: Oleg Bartunov <obartunov@postgrespro.ru>
Cc: Thomas Munro <thomas.munro@gmail.com>
Cc: Teodor Sigaev <teodor@sigaev.ru>
Subject: Re: fix for BUG #3720: wrong results at using ltree
Date: Mon, 30 Mar 2020 18:35:48 -0400
Message-ID: <5210.1585607748@sss.pgh.pa.us> (raw)
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>
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: tgl@sss.pgh.pa.us, n.gluhov@postgrespro.ru, filip.rembialkowski@gmail.com, tomas.vondra@2ndquadrant.com, a.korotkov@postgrespro.ru, obartunov@postgrespro.ru, thomas.munro@gmail.com, teodor@sigaev.ru
Subject: Re: fix for BUG #3720: wrong results at using ltree
In-Reply-To: <5210.1585607748@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox