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

[Tom Lane]

I wrote:
> I've marked this RFC, and will push tomorrow unless somebody wants
> to object to the loss of backwards compatibility.

And done.  I noticed in some final testing that it's possible to
make this code take a long time by forcing it to backtrack a lot:

regression=# SELECT (('1' || repeat('.1', 65534))::ltree) ~ '*.*.x';
 ?column? 
--
 f
(1 row)

Time: 54015.421 ms (00:54.015)

so I threw in a CHECK_FOR_INTERRUPTS().  Maybe it'd be worth trying
to optimize such cases, but I'm not sure that it'd ever matter for
real-world cases with reasonable-size label strings.

The old implementation seems to handle that particular case well,
evidently because it more-or-less folds adjacent stars together.
However, before anyone starts complaining about regressions, they
should note that it's really easy to get the old code to fail
via stack overflow:

regression=# SELECT (('1' || repeat('.1', 65534))::ltree) ~ '*.!1.*';
ERROR:  stack depth limit exceeded

(That's as of five minutes ago, before that it dumped core.)
So I don't feel bad about the tradeoff.  At least now we have
simple, visibly correct code that could serve as a starting
point for optimization if anyone feels the need to.

regards, tom lane

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

[Tom Lane]

Nikita Glukhov  writes:
> I think now it looks as simple as the whole algorithm is.

Yeah, I think we've gotten checkCond to the point of "there's no
longer anything to take away".

I've marked this RFC, and will push tomorrow unless somebody wants
to object to the loss of backwards compatibility.

regards, tom lane

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

[Nikita Glukhov]

On 31.03.2020 1:35, Tom Lane wrote:

Nikita Glukhov  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 think now it looks as simple as the whole algorithm is.


--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

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

[Tom Lane]

Nikita Glukhov  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

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

[Nikita Glukhov]

On 31.03.2020 1:12, Tom Lane wrote:


I wrote:

I dunno, that doesn't really seem clearer to me (although some of it
might be that you expended no effort on making the comments match
the new code logic).

... although looking closer, this formulation does have one very nice
advantage: for the typical non-star case with high = low = 1, the
only recursive call is a tail recursion, so it ought to consume less
stack space than what I wrote.


And we even can simply transform this tail call into a loop:

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


Let me see what I can do with the comments.


Thanks.

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

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

[Tom Lane]

I wrote:
> I dunno, that doesn't really seem clearer to me (although some of it
> might be that you expended no effort on making the comments match
> the new code logic).

... although looking closer, this formulation does have one very nice
advantage: for the typical non-star case with high = low = 1, the
only recursive call is a tail recursion, so it ought to consume less
stack space than what I wrote.

Let me see what I can do with the comments.

regards, tom lane

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

[Tom Lane]

Nikita Glukhov  writes:
> On 30.03.2020 21:00, Tom Lane wrote:
>> Hence, new patch versions that do it like that.  (0002 is unchanged.)

> I tried to simplify a bit loops in checkCond() by merging two of them into
> one with an explicit exit condition.  Also I added return statement after
> this loop, so it's now clear that we can't fall into next "while" loop.

I dunno, that doesn't really seem clearer to me (although some of it
might be that you expended no effort on making the comments match
the new code logic).

regards, tom lane

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

[Nikita Glukhov]

On 30.03.2020 21:00, Tom Lane wrote:


Hence, new patch versions that do it like that.  (0002 is unchanged.)


I tried to simplify a bit loops in checkCond() by merging two of them into
one with an explicit exit condition.  Also I added return statement after
this loop, so it's now clear that we can't fall into next "while" loop.

The rest code in 0001 and 0002 is unchanged.

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
>From b30c07ec318edefdcc9faa6c2158f4bb56114789 Mon Sep 17 00:00:00 2001
From: Nikita Glukhov 
Date: Tue, 31 Mar 2020 00:13:40 +0300
Subject: [PATCH v3 1/2] Rationalize ltree input errors

---
 contrib/ltree/expected/ltree.out   | 13 ++-
 contrib/ltree/ltree_io.c   | 99 --
 contrib/ltree/sql/ltree.sql|  1 +
 contrib/ltree_plpython/expected/ltree_plpython.out |  2 +-
 4 files changed, 63 insertions(+), 52 deletions(-)

diff --git a/contrib/ltree/expected/ltree.out b/contrib/ltree/expected/ltree.out
index c78d372..610cb6f 100644
--- a/contrib/ltree/expected/ltree.out
+++ b/contrib/ltree/expected/ltree.out
@@ -464,7 +464,7 @@ SELECT nlevel(('1' || repeat('.1', 65534))::ltree);
 (1 row)
 
 SELECT nlevel(('1' || repeat('.1', 65535))::ltree);
-ERROR:  number of ltree levels (65536) exceeds the maximum allowed (65535)
+ERROR:  number of ltree labels (65536) exceeds the maximum allowed (65535)
 SELECT nlevel(('1' || repeat('.1', 65534))::ltree || '1');
 ERROR:  number of ltree levels (65536) exceeds the maximum allowed (65535)
 SELECT ('1' || repeat('.1', 65534))::lquery IS NULL;
@@ -474,7 +474,7 @@ SELECT ('1' || repeat('.1', 65534))::lquery IS NULL;
 (1 row)
 
 SELECT ('1' || repeat('.1', 65535))::lquery IS NULL;
-ERROR:  number of lquery levels (65536) exceeds the maximum allowed (65535)
+ERROR:  number of lquery items (65536) exceeds the maximum allowed (65535)
 SELECT '*{65535}'::lquery;
   lquery  
 --
@@ -485,7 +485,7 @@ SELECT '*{65536}'::lquery;
 ERROR:  lquery syntax error
 LINE 1: SELECT '*{65536}'::lquery;
^
-DETAIL:  Low limit (65536) exceeds the maximum allowed (65535).
+DETAIL:  Low limit (65536) exceeds the maximum allowed (65535), at character 3.
 SELECT '*{,65534}'::lquery;
   lquery   
 ---
@@ -502,7 +502,12 @@ SELECT '*{,65536}'::lquery;
 ERROR:  lquery syntax error
 LINE 1: SELECT '*{,65536}'::lquery;
^
-DETAIL:  High limit (65536) exceeds the maximum allowed (65535).
+DETAIL:  High limit (65536) exceeds the maximum allowed (65535), at character 4.
+SELECT '*{4,3}'::lquery;
+ERROR:  lquery syntax error
+LINE 1: SELECT '*{4,3}'::lquery;
+   ^
+DETAIL:  Low limit (4) is greater than high limit (3), at character 5.
 SELECT '1.2'::ltree  < '2.2'::ltree;
  ?column? 
 --
diff --git a/contrib/ltree/ltree_io.c b/contrib/ltree/ltree_io.c
index 2503d47..e806a14 100644
--- a/contrib/ltree/ltree_io.c
+++ b/contrib/ltree/ltree_io.c
@@ -17,12 +17,6 @@ PG_FUNCTION_INFO_V1(lquery_in);
 PG_FUNCTION_INFO_V1(lquery_out);
 
 
-#define UNCHAR ereport(ERROR, \
-	   (errcode(ERRCODE_SYNTAX_ERROR), \
-		errmsg("syntax error at position %d", \
-		pos)));
-
-
 typedef struct
 {
 	char	   *start;
@@ -47,7 +41,12 @@ ltree_in(PG_FUNCTION_ARGS)
 	ltree	   *result;
 	ltree_level *curlevel;
 	int			charlen;
-	int			pos = 0;
+	int			pos = 1;		/* character position for error messages */
+
+#define UNCHAR ereport(ERROR, \
+	   errcode(ERRCODE_SYNTAX_ERROR), \
+	   errmsg("ltree syntax error at character %d", \
+			  pos))
 
 	ptr = buf;
 	while (*ptr)
@@ -61,7 +60,7 @@ ltree_in(PG_FUNCTION_ARGS)
 	if (num + 1 > LTREE_MAX_LEVELS)
 		ereport(ERROR,
 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
- errmsg("number of ltree levels (%d) exceeds the maximum allowed (%d)",
+ errmsg("number of ltree labels (%d) exceeds the maximum allowed (%d)",
 		num + 1, LTREE_MAX_LEVELS)));
 	list = lptr = (nodeitem *) palloc(sizeof(nodeitem) * (num + 1));
 	ptr = buf;
@@ -88,10 +87,10 @@ ltree_in(PG_FUNCTION_ARGS)
 if (lptr->wlen > LTREE_LABEL_MAX_CHARS)
 	ereport(ERROR,
 			(errcode(ERRCODE_NAME_TOO_LONG),
-			 errmsg("name of level is too long"),
-			 errdetail("Name length is %d, must "
-	   "be < 256, in position %d.",
-	   lptr->wlen, pos)));
+			 errmsg("label string is too long"),
+			 errdetail("Label length is %d, must be at most %d, at character %d.",
+	   lptr->wlen, LTREE_LABEL_MAX_CHARS,
+	   pos)));
 
 totallen += MAXALIGN(lptr->len + LEVEL_HDRSIZE);
 lptr++;
@@ -115,10 +114,9 @@ ltree_in(PG_FUNCTION_ARGS)
 		if (lptr->wlen > LTREE_LABEL_MAX_CHARS)
 			ereport(ERROR,
 	(errcode(ERRCODE_NAME_TOO_LONG),
-	 errmsg("name of level is too long"),
-	 errdetail("Name length is %d, must "
-			   "be < 256, in position %d.",
-			   lptr->wlen, pos)));
+	 errmsg("label string is too long"),
+	 errdeta

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

[Tom Lane]

I wrote:
> Hence, attached are two revised patches that attack the problem
> this way.  The first one is somewhat unrelated to the original
> point --- it's trying to clean up the error messages in ltree_in
> and lquery_in so that they are more consistent and agree with
> the terminology used in the documentation.  (Notably, the term
> "level" is used nowhere in the ltree docs, except in the legacy
> function name nlevel().)

One thing I changed in that patch was to change the syntax error
reports to say "at character %d" not "in position %d", because
I thought the latter was pretty confusing --- it's not obvious
whether it's counting characters or labels or what.  However,
I now notice that what the code is providing is a zero-based
character index, which is out of line with our practice
elsewhere: core parser errors are reported using 1-based indexes.
If we reword these messages then we should adopt that practice too.
Hence, new patch versions that do it like that.  (0002 is unchanged.)

regards, tom lane

diff --git a/contrib/ltree/expected/ltree.out b/contrib/ltree/expected/ltree.out
index c78d372..610cb6f 100644
--- a/contrib/ltree/expected/ltree.out
+++ b/contrib/ltree/expected/ltree.out
@@ -464,7 +464,7 @@ SELECT nlevel(('1' || repeat('.1', 65534))::ltree);
 (1 row)
 
 SELECT nlevel(('1' || repeat('.1', 65535))::ltree);
-ERROR:  number of ltree levels (65536) exceeds the maximum allowed (65535)
+ERROR:  number of ltree labels (65536) exceeds the maximum allowed (65535)
 SELECT nlevel(('1' || repeat('.1', 65534))::ltree || '1');
 ERROR:  number of ltree levels (65536) exceeds the maximum allowed (65535)
 SELECT ('1' || repeat('.1', 65534))::lquery IS NULL;
@@ -474,7 +474,7 @@ SELECT ('1' || repeat('.1', 65534))::lquery IS NULL;
 (1 row)
 
 SELECT ('1' || repeat('.1', 65535))::lquery IS NULL;
-ERROR:  number of lquery levels (65536) exceeds the maximum allowed (65535)
+ERROR:  number of lquery items (65536) exceeds the maximum allowed (65535)
 SELECT '*{65535}'::lquery;
   lquery  
 --
@@ -485,7 +485,7 @@ SELECT '*{65536}'::lquery;
 ERROR:  lquery syntax error
 LINE 1: SELECT '*{65536}'::lquery;
^
-DETAIL:  Low limit (65536) exceeds the maximum allowed (65535).
+DETAIL:  Low limit (65536) exceeds the maximum allowed (65535), at character 3.
 SELECT '*{,65534}'::lquery;
   lquery   
 ---
@@ -502,7 +502,12 @@ SELECT '*{,65536}'::lquery;
 ERROR:  lquery syntax error
 LINE 1: SELECT '*{,65536}'::lquery;
^
-DETAIL:  High limit (65536) exceeds the maximum allowed (65535).
+DETAIL:  High limit (65536) exceeds the maximum allowed (65535), at character 4.
+SELECT '*{4,3}'::lquery;
+ERROR:  lquery syntax error
+LINE 1: SELECT '*{4,3}'::lquery;
+   ^
+DETAIL:  Low limit (4) is greater than high limit (3), at character 5.
 SELECT '1.2'::ltree  < '2.2'::ltree;
  ?column? 
 --
diff --git a/contrib/ltree/ltree_io.c b/contrib/ltree/ltree_io.c
index 2503d47..e806a14 100644
--- a/contrib/ltree/ltree_io.c
+++ b/contrib/ltree/ltree_io.c
@@ -17,12 +17,6 @@ PG_FUNCTION_INFO_V1(lquery_in);
 PG_FUNCTION_INFO_V1(lquery_out);
 
 
-#define UNCHAR ereport(ERROR, \
-	   (errcode(ERRCODE_SYNTAX_ERROR), \
-		errmsg("syntax error at position %d", \
-		pos)));
-
-
 typedef struct
 {
 	char	   *start;
@@ -47,7 +41,12 @@ ltree_in(PG_FUNCTION_ARGS)
 	ltree	   *result;
 	ltree_level *curlevel;
 	int			charlen;
-	int			pos = 0;
+	int			pos = 1;		/* character position for error messages */
+
+#define UNCHAR ereport(ERROR, \
+	   errcode(ERRCODE_SYNTAX_ERROR), \
+	   errmsg("ltree syntax error at character %d", \
+			  pos))
 
 	ptr = buf;
 	while (*ptr)
@@ -61,7 +60,7 @@ ltree_in(PG_FUNCTION_ARGS)
 	if (num + 1 > LTREE_MAX_LEVELS)
 		ereport(ERROR,
 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
- errmsg("number of ltree levels (%d) exceeds the maximum allowed (%d)",
+ errmsg("number of ltree labels (%d) exceeds the maximum allowed (%d)",
 		num + 1, LTREE_MAX_LEVELS)));
 	list = lptr = (nodeitem *) palloc(sizeof(nodeitem) * (num + 1));
 	ptr = buf;
@@ -88,10 +87,10 @@ ltree_in(PG_FUNCTION_ARGS)
 if (lptr->wlen > LTREE_LABEL_MAX_CHARS)
 	ereport(ERROR,
 			(errcode(ERRCODE_NAME_TOO_LONG),
-			 errmsg("name of level is too long"),
-			 errdetail("Name length is %d, must "
-	   "be < 256, in position %d.",
-	   lptr->wlen, pos)));
+			 errmsg("label string is too long"),
+			 errdetail("Label length is %d, must be at most %d, at character %d.",
+	   lptr->wlen, LTREE_LABEL_MAX_CHARS,
+	   pos)));
 
 totallen += MAXALIGN(lptr->len + LEVEL_HDRSIZE);
 lptr++;
@@ -115,10 +114,9 @@ ltree_in(PG_FUNCTION_ARGS)
 		if (lptr->wlen > LTREE_LABEL_MAX_CHARS)
 			ereport(ERROR,
 	(errcode(ERRCODE_NAME_TOO_LONG),
-	 errmsg("name of level is too long"),
-	 errdetail("Name length is %d, must "
-			   "be < 256, in position %d.",
-			   lptr->wlen,

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

[Tom Lane]

I wrote:
> My main complaint about it remains the same, that it changes a
> disturbingly large number of existing regression-test results,
> suggesting that there's not a meeting of the minds about what
> this logic is supposed to do.  Maybe it's okay or maybe it's
> not, but who's going to decide?

Well ... *somebody's* got to decide, and since Oleg and Teodor aren't
stepping up, I took it on myself to study this more closely.

It seems to me that indeed the existing behavior is broken: given
what the documentation has to say, it's really hard to argue that
an lquery like "*.!foo.*" means something other than "match any
ltree that has at least one label that is not 'foo'".  But the
existing code produces

regression=# select 'bar.foo.baz'::ltree ~ '*.!foo.*'::lquery;
 ?column? 
--
 f
(1 row)

I agree that's just plain wrong, and so are all the regression
test cases that this patch is changing the results of.

However, I think there is a valid use-case that the existing
code is trying to solve: how can you say "match any ltree in
which no label is 'foo'"?  That is the effective behavior right
now of a pattern like this, and it seems useful.  So if we change
this, we ought to provide some other way to get that result.

What I propose we do about that is allow lquery quantifiers to
be attached to regular items as well as star items, so that the
need is met by saying this:

regression=# select 'bar.foo.baz'::ltree ~ '!foo{,}'::lquery;
 ?column? 
--
 f
(1 row)

regression=# select 'bar.fool.baz'::ltree ~ '!foo{,}'::lquery;
 ?column? 
--
 t
(1 row)

Also, once we do that, it's possible to treat star and non-star items
basically alike in checkCond, with checkLevel being the place that
accounts for them being different.  This results in logic that's far
simpler and much more nearly like the way that LIKE patterns are
implemented, which seems like a good thing to me.

Hence, attached are two revised patches that attack the problem
this way.  The first one is somewhat unrelated to the original
point --- it's trying to clean up the error messages in ltree_in
and lquery_in so that they are more consistent and agree with
the terminology used in the documentation.  (Notably, the term
"level" is used nowhere in the ltree docs, except in the legacy
function name nlevel().)  However its movement of the check for
high < low is needed to make that cover the case of a bogus non-star
quantifier in patch 0002.  These also depend on the cosmetic
patches I just committed, so you need HEAD as of today to get
them to apply.

regards, tom lane

diff --git a/contrib/ltree/expected/ltree.out b/contrib/ltree/expected/ltree.out
index 1b31dbc..cd18516 100644
--- a/contrib/ltree/expected/ltree.out
+++ b/contrib/ltree/expected/ltree.out
@@ -464,7 +464,7 @@ SELECT nlevel(('1' || repeat('.1', 65534))::ltree);
 (1 row)
 
 SELECT nlevel(('1' || repeat('.1', 65535))::ltree);
-ERROR:  number of ltree levels (65536) exceeds the maximum allowed (65535)
+ERROR:  number of ltree labels (65536) exceeds the maximum allowed (65535)
 SELECT nlevel(('1' || repeat('.1', 65534))::ltree || '1');
 ERROR:  number of ltree levels (65536) exceeds the maximum allowed (65535)
 SELECT ('1' || repeat('.1', 65534))::lquery IS NULL;
@@ -474,7 +474,7 @@ SELECT ('1' || repeat('.1', 65534))::lquery IS NULL;
 (1 row)
 
 SELECT ('1' || repeat('.1', 65535))::lquery IS NULL;
-ERROR:  number of lquery levels (65536) exceeds the maximum allowed (65535)
+ERROR:  number of lquery items (65536) exceeds the maximum allowed (65535)
 SELECT '*{65535}'::lquery;
   lquery  
 --
@@ -485,7 +485,7 @@ SELECT '*{65536}'::lquery;
 ERROR:  lquery syntax error
 LINE 1: SELECT '*{65536}'::lquery;
^
-DETAIL:  Low limit (65536) exceeds the maximum allowed (65535).
+DETAIL:  Low limit (65536) exceeds the maximum allowed (65535), at character 2.
 SELECT '*{,65534}'::lquery;
   lquery   
 ---
@@ -502,7 +502,12 @@ SELECT '*{,65536}'::lquery;
 ERROR:  lquery syntax error
 LINE 1: SELECT '*{,65536}'::lquery;
^
-DETAIL:  High limit (65536) exceeds the maximum allowed (65535).
+DETAIL:  High limit (65536) exceeds the maximum allowed (65535), at character 3.
+SELECT '*{4,3}'::lquery;
+ERROR:  lquery syntax error
+LINE 1: SELECT '*{4,3}'::lquery;
+   ^
+DETAIL:  Low limit (4) is greater than high limit (3), at character 4.
 SELECT '1.2'::ltree  < '2.2'::ltree;
  ?column? 
 --
diff --git a/contrib/ltree/ltree_io.c b/contrib/ltree/ltree_io.c
index 2503d47..2136715 100644
--- a/contrib/ltree/ltree_io.c
+++ b/contrib/ltree/ltree_io.c
@@ -17,12 +17,6 @@ PG_FUNCTION_INFO_V1(lquery_in);
 PG_FUNCTION_INFO_V1(lquery_out);
 
 
-#define UNCHAR ereport(ERROR, \
-	   (errcode(ERRCODE_SYNTAX_ERROR), \
-		errmsg("syntax error at position %d", \
-		pos)));
-
-
 typedef struct
 {
 	char	   *start;
@@ -49,6 +43,11 @@ ltree_in(PG_FUNCTION_ARGS)
 	int			charlen;
 	int			pos = 0;
 
+#define UNCHAR 

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

[Tom Lane]

Nikita Glukhov  writes:
> On 24.01.2020 21:29, Tomas Vondra wrote:
>> Unfortunately, the current code is somewhat undercommented :-(

> The main problem is that no one really understands how it works now.

Indeed.  I was disturbed to realize that lquery_op.c, despite being
far from trivial code, contained NOT ONE SINGLE COMMENT before today,
other than the content-free file header and a commented-out (visibly
unsafe, too) debugging printing function.  This is a long way south
of minimally acceptable, in my book.

Anyway, I concur that Nikita's two patches are bug fixes, so I pushed
them.  Nonetheless, he *did* hijack this thread, so in hopes of restoring
attention to the original topic, here's a rebased version of the original
patch.

My main complaint about it remains the same, that it changes a
disturbingly large number of existing regression-test results,
suggesting that there's not a meeting of the minds about what
this logic is supposed to do.  Maybe it's okay or maybe it's
not, but who's going to decide?

Also, now that I've looked at it a bit more, I'd be inclined to
strip out the parts of the patch that remove setting up the
LQUERY_HASNOT flag.  Even if we're not using that right now,
we might want it again someday, and we're not saving much of
anything by introducing a minor on-disk incompatibility.

regards, tom lane

diff --git a/contrib/ltree/expected/ltree.out b/contrib/ltree/expected/ltree.out
index 1b31dbc..1eef086 100644
--- a/contrib/ltree/expected/ltree.out
+++ b/contrib/ltree/expected/ltree.out
@@ -722,7 +722,7 @@ SELECT 'a.b.c.d.e'::ltree ~ '*.a.*.d.*';
 SELECT 'a.b.c.d.e'::ltree ~ '*.!d.*';
  ?column? 
 --
- f
+ t
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ '*.!d';
@@ -752,7 +752,7 @@ SELECT 'a.b.c.d.e'::ltree ~ '*.!e';
 SELECT 'a.b.c.d.e'::ltree ~ '*.!e.*';
  ?column? 
 --
- f
+ t
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ 'a.*.!e';
@@ -770,7 +770,7 @@ SELECT 'a.b.c.d.e'::ltree ~ 'a.*.!d';
 SELECT 'a.b.c.d.e'::ltree ~ 'a.*.!d.*';
  ?column? 
 --
- f
+ t
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ 'a.*.!f.*';
@@ -788,7 +788,7 @@ SELECT 'a.b.c.d.e'::ltree ~ '*.a.*.!f.*';
 SELECT 'a.b.c.d.e'::ltree ~ '*.a.*.!d.*';
  ?column? 
 --
- f
+ t
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ '*.a.!d.*';
@@ -812,13 +812,13 @@ SELECT 'a.b.c.d.e'::ltree ~ 'a.!d.*';
 SELECT 'a.b.c.d.e'::ltree ~ '*.a.*.!d.*';
  ?column? 
 --
- f
+ t
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ '*.!b.*';
  ?column? 
 --
- f
+ t
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ '*.!b.c.*';
@@ -830,7 +830,7 @@ SELECT 'a.b.c.d.e'::ltree ~ '*.!b.c.*';
 SELECT 'a.b.c.d.e'::ltree ~ '*.!b.*.c.*';
  ?column? 
 --
- f
+ t
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ '!b.*.c.*';
@@ -878,31 +878,31 @@ SELECT 'a.b.c.d.e'::ltree ~ '*{1}.!b.*.!c.*.e';
 SELECT 'a.b.c.d.e'::ltree ~ '*{1}.!b.*{1}.!c.*.e';
  ?column? 
 --
- t
+ f
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ 'a.!b.*{1}.!c.*.e';
  ?column? 
 --
- t
+ f
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ '!b.*{1}.!c.*.e';
  ?column? 
 --
- t
+ f
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ '*.!b.*{1}.!c.*.e';
  ?column? 
 --
- t
+ f
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ '*.!b.*.!c.*.e';
  ?column? 
 --
- f
+ t
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ '!b.!c.*';
@@ -932,19 +932,19 @@ SELECT 'a.b.c.d.e'::ltree ~ '*{1}.!b.*.!c.*';
 SELECT 'a.b.c.d.e'::ltree ~ '*{1}.!b.*{1}.!c.*';
  ?column? 
 --
- t
+ f
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ 'a.!b.*{1}.!c.*';
  ?column? 
 --
- t
+ f
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ '!b.*{1}.!c.*';
  ?column? 
 --
- t
+ f
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ '*.!b.*{1}.!c.*';
@@ -956,7 +956,7 @@ SELECT 'a.b.c.d.e'::ltree ~ '*.!b.*{1}.!c.*';
 SELECT 'a.b.c.d.e'::ltree ~ '*.!b.*.!c.*';
  ?column? 
 --
- f
+ t
 (1 row)
 
 SELECT 'a.b.c.d.e'::ltree ~ 'a.*{2}.*{2}';
@@ -983,6 +983,18 @@ SELECT 'a.b.c.d.e'::ltree ~ 'a.*{5}.*';
  f
 (1 row)
 
+SELECT '5.0.1.0'::ltree ~ '5.!0.!0.0';
+ ?column? 
+--
+ f
+(1 row)
+
+SELECT 'a.b'::ltree ~ '!a.!a';
+ ?column? 
+--
+ f
+(1 row)
+
 SELECT 'QWER_TY'::ltree ~ 'q%@*';
  ?column? 
 --
diff --git a/contrib/ltree/lquery_op.c b/contrib/ltree/lquery_op.c
index 5c7afe5..81fcb0e 100644
--- a/contrib/ltree/lquery_op.c
+++ b/contrib/ltree/lquery_op.c
@@ -19,16 +19,6 @@ PG_FUNCTION_INFO_V1(lt_q_rregex);
 
 #define NEXTVAL(x) ( (lquery*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
 
-typedef struct
-{
-	lquery_level *q;
-	int			nq;
-	ltree_level *t;
-	int			nt;
-	int			posq;
-	int			post;
-} FieldNot;
-
 static char *
 getlexeme(char *start, char *end, int *len)
 {
@@ -109,6 +99,9 @@ checkLevel(lquery_level *curq, ltree_level *curt)
 	int			(*cmpptr) (const char *, const char *, size_t);
 	lquery_variant *curvar = LQL_FIRST(curq);
 	int			i;
+	bool		success;
+
+	success = (curq->flag & LQL_NOT) ? false : true;
 
 	for (i = 0; i < curq->numvar; i++)
 	{
@@ -116,39 +109,26 @@ checkLevel(lquery_level

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

[Nikita Glukhov]

On 24.01.2020 21:29, Tomas Vondra wrote:

Hi Nikita,

This patch seems inactive / stuck in "waiting on author" since November.
It's marked as bugfix, so it'd be good to get it committed instead of
just punting it to the next CF.

I did a quick review, and I came mostly with the same two complaints as
Alexander ...

On Wed, Jul 17, 2019 at 09:33:46PM +0300, Alexander Korotkov wrote:

Hi Nikita,

On Tue, Jul 16, 2019 at 6:52 PM Nikita Glukhov 
 wrote:

I looked at "ltree syntax improvement" patch and found two more very
old bugs in ltree/lquery (fixes are attached):


Thank you for the fixes.  I've couple notes on them.

0001-Fix-max-size-checking-for-ltree-and-lquery.patch

+#define LTREE_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize / 
sizeof(nodeitem))

+#define LQUERY_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize / ITEMSIZE)

Looks over caution.  PG_UINT16_MAX is not even close to MaxAllocSize /
sizeof(nodeitem) or MaxAllocSize / ITEMSIZE.



Yeah, I'm also puzzled by the usage of PG_UINT16_MAX here. It's so much
lower than the other values we could jut use the constant directly, but
let's say the structs could grow from the ~16B to chnge this.


Ok, LTREE_MAX_LEVELS and LQUERY_MAX_LEVELS are defined simply as PG_UINT16_MAX 
now.



The main question is why we need PG_UINT16_MAX at all? It kinda implies
we need to squish the value into a 2B counter or something, but is that
actually true? I don't see anything like that in ltree_io.c.


ltree.numlevel and lquery.numlevel are uint16 fields.


I also found two places in ltree_concat() where numlevel can overflow.

The first is ltree_concat() (operator ||(ltree, ltree)):

=# SELECT nlevel(('a' || repeat('.a', 65533))::ltree || 'a');
 nlevel

  65535
(1 row)

=# SELECT nlevel(('a' || repeat('.a', 65534))::ltree || 'a');
 nlevel

  0
(1 row)



The second is parsing of low and high level limits in lquery_in():

=# SELECT '*{65535}'::lquery;
  lquery
--
 *{65535}
(1 row)

=# SELECT '*{65536}'::lquery;
 lquery

 *{0}
(1 row)

=# SELECT '*{65537}'::lquery;
 lquery

 *{1}
(1 row)


The both problems are fixed in the new version of the patch.


So it seems more like an arbitrary value considered "sane" - which is
fine, but then a comment saying so would be nice, and we could pick a
value that is "nicer" for humans. Or just use value computed from the
MaxAllocSize limit, without the Min().


0002-Fix-successive-lquery-ops.patch

diff --git a/contrib/ltree/lquery_op.c b/contrib/ltree/lquery_op.c
index 62172d5..d4f4941 100644
--- a/contrib/ltree/lquery_op.c
+++ b/contrib/ltree/lquery_op.c
@@ -255,8 +255,8 @@ checkCond(lquery_level *curq, int query_numlevel,
ltree_level *curt, int tree_nu
 }
 else
 {
- low_pos = cur_tpos + curq->low;
- high_pos = cur_tpos + curq->high;
+ low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
+ high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
 if (ptr && ptr->q)
 {
 ptr->nq++;
@@ -282,8 +282,8 @@ checkCond(lquery_level *curq, int query_numlevel,
ltree_level *curt, int tree_nu
 }
 else
 {
- low_pos = cur_tpos + curq->low;
- high_pos = cur_tpos + curq->high;
+ low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
+ high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
 }

 curq = LQL_NEXT(curq);

I'm not sure what do these checks do.  Code around is uncommented and
puzzled.  But could we guarantee the same invariant on the stage of
ltree/lquery parsing?



Unfortunately, the current code is somewhat undercommented :-(


The main problem is that no one really understands how it works now.

low_pos and high_pos seem to be a range of tree levels, from which is allowed
to match the rest of lquery.

For example, when we are matching '.b' in the 'a.*{2,3}.*{4,5}.b'::lquery,
low_pos = 1 + 2 + 4 = 7  and  high_pos = 1 + 3 + 5 = 9.


The main goal of the patch is to fix calculation of low_pos and high_pos:

- low_pos = cur_tpos + curq->low;
- high_pos = cur_tpos + curq->high;
+ low_pos = low_pos + curq->low;
+ high_pos = high_pos + curq->high;



Anyway, I don't quite understand why we need these caps. It kinda seems
like a band-aid for potential overflow.

Why should it be OK for the values to even get past the maximum, with
sane input data? And isn't there a better upper limit (e.g. based on
how much space we actually allocated)?


We can compare low_pos to tree_numlevel and return false earlier, if it is
greater.  And it seems that high_pos we can also limit to tree_numlevel.

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
>From 2bb5d618ca7f0ac3997a2e34e3a06dbd404ca26f Mon Sep 17 00:00:00 2001
From: Nikita Glukhov 
Date: Thu, 7 Mar 2019 17:45:44 +0300
Subject: [PATCH v2 1/2] Fix max size checking for ltree and lquery

---
 contrib/ltree/expected/ltree.out | 46 
 contrib/ltree/ltree.h|  2 ++
 contrib/ltree/ltree_io.c | 44 ++
 contrib/ltree/ltree_op.c |  9 +

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

[Tomas Vondra]

Hi,

I've moved this patch to the next CF - it's still in WoA state, but it's
supposedly a bugfix so I've decided not to return it with feedback.

regards

--
Tomas Vondra  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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

[Tomas Vondra]

Hi Nikita,

This patch seems inactive / stuck in "waiting on author" since November.
It's marked as bugfix, so it'd be good to get it committed instead of
just punting it to the next CF.

I did a quick review, and I came mostly with the same two complaints as
Alexander ...

On Wed, Jul 17, 2019 at 09:33:46PM +0300, Alexander Korotkov wrote:

Hi Nikita,

On Tue, Jul 16, 2019 at 6:52 PM Nikita Glukhov  wrote:

I looked at "ltree syntax improvement" patch and found two more very
old bugs in ltree/lquery (fixes are attached):


Thank you for the fixes.  I've couple notes on them.

0001-Fix-max-size-checking-for-ltree-and-lquery.patch

+#define LTREE_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize / sizeof(nodeitem))
+#define LQUERY_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize / ITEMSIZE)

Looks over caution.  PG_UINT16_MAX is not even close to MaxAllocSize /
sizeof(nodeitem) or MaxAllocSize / ITEMSIZE.



Yeah, I'm also puzzled by the usage of PG_UINT16_MAX here. It's so much
lower than the other values we could jut use the constant directly, but
let's say the structs could grow from the ~16B to chnge this.

The main question is why we need PG_UINT16_MAX at all? It kinda implies
we need to squish the value into a 2B counter or something, but is that
actually true? I don't see anything like that in ltree_io.c.

So it seems more like an arbitrary value considered "sane" - which is
fine, but then a comment saying so would be nice, and we could pick a
value that is "nicer" for humans. Or just use value computed from the
MaxAllocSize limit, without the Min().


0002-Fix-successive-lquery-ops.patch

diff --git a/contrib/ltree/lquery_op.c b/contrib/ltree/lquery_op.c
index 62172d5..d4f4941 100644
--- a/contrib/ltree/lquery_op.c
+++ b/contrib/ltree/lquery_op.c
@@ -255,8 +255,8 @@ checkCond(lquery_level *curq, int query_numlevel,
ltree_level *curt, int tree_nu
 }
 else
 {
- low_pos = cur_tpos + curq->low;
- high_pos = cur_tpos + curq->high;
+ low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
+ high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
 if (ptr && ptr->q)
 {
 ptr->nq++;
@@ -282,8 +282,8 @@ checkCond(lquery_level *curq, int query_numlevel,
ltree_level *curt, int tree_nu
 }
 else
 {
- low_pos = cur_tpos + curq->low;
- high_pos = cur_tpos + curq->high;
+ low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
+ high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
 }

 curq = LQL_NEXT(curq);

I'm not sure what do these checks do.  Code around is uncommented and
puzzled.  But could we guarantee the same invariant on the stage of
ltree/lquery parsing?



Unfortunately, the current code is somewhat undercommented :-(

Anyway, I don't quite understand why we need these caps. It kinda seems
like a band-aid for potential overflow.

Why should it be OK for the values to even get past the maximum, with
sane input data? And isn't there a better upper limit (e.g. based on
how much space we actually allocated)?


regards

--
Tomas Vondra  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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

[Michael Paquier]

On Thu, Sep 05, 2019 at 04:50:58PM -0400, Alvaro Herrera from 2ndQuadrant wrote:
> Hi Oleg, Teodor.  Did you find time to refresh your memory on these things?
> It would be good to have these bugfixes sorted out.

Two months later.  Now would be a good time as well!  Alexander, you
have also looked at two patches from Nikita upthread.  If these look
good enough for you, are you working on merging them into the tree?
--
Michael


signature.asc
Description: PGP signature

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

[Benjie Gillam]

The following review has been posted through the commitfest application:
make installcheck-world:  tested, passed
Implements feature:   tested, passed
Spec compliant:   not tested
Documentation:tested, failed

This is my first PostgreSQL commitfest and review, guidance welcome.

This patch is straightforward, it applies cleanly, and it includes tests (I've 
also tested the feature manually).

The (existing) documentation states "The length of a label path must be less 
than 65kB," I believe that the 65kB mentioned here should instead be 64kB - 
perhaps the patch could be updated with this single-character fix? At first I 
thought the 65kB limit would be applied to the label path string (e.g. 
'Top.Countries.Europe.Russia' would be 27 bytes), but it seems the limit 
applies to the number of labels in the path - perhaps `kB` is not the right 
measurement here and it should explicitly state 65536?

It is not stated in the documentation what should happen if the label path 
length is greater than 65535, so raising an error makes sense (but may be a 
breaking change).

The new status of this patch is: Waiting on Author

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

[Alvaro Herrera from 2ndQuadrant]

On 2019-Jul-09, Oleg Bartunov wrote:

> On Mon, Jul 8, 2019 at 7:22 AM Thomas Munro  wrote:
> >
> > On Sun, Apr 7, 2019 at 3:46 AM Tom Lane  wrote:

> > > In short, I'm wondering if we should treat this as a documentation
> > > bug not a code bug.  But to do that, we'd need a more accurate
> > > description of what the code is supposed to do, because the statement
> > > quoted above is certainly not a match to the actual behavior.

> > Teodor, Oleg, would you like to offer an opinion here?

> We are currently very busy and will look at the problem (and dig into
> our memory) later.

Hi Oleg, Teodor.  Did you find time to refresh your memory on these things?
It would be good to have these bugfixes sorted out.

-- 
Álvaro Herrerahttps://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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

[Ibrar Ahmed]

On Tue, Jul 16, 2019 at 8:52 PM Nikita Glukhov 
wrote:

>
> On 09.07.2019 17:57, Oleg Bartunov wrote:
>
> On Mon, Jul 8, 2019 at 7:22 AM Thomas Munro  
>  wrote:
>
> On Sun, Apr 7, 2019 at 3:46 AM Tom Lane  
>  wrote:
>
> =?UTF-8?Q?Filip_Rembia=C5=82kowski?=  
>  writes:
>
> Here is my attempt to fix a 12-years old ltree bug (which is a todo item).
> I see it's not backward-compatible, but in my understanding that's
> what is documented. Previous behavior was inconsistent with
> documentation (where single asterisk should match zero or more
> labels).http://archives.postgresql.org/pgsql-bugs/2007-11/msg00044.php
>
> [...]
>
>
> In short, I'm wondering if we should treat this as a documentation
> bug not a code bug.  But to do that, we'd need a more accurate
> description of what the code is supposed to do, because the statement
> quoted above is certainly not a match to the actual behavior.
>
> This patch doesn't apply.  More importantly, it seems like we don't
> have a consensus on whether we want it.
>
> Teodor, Oleg, would you like to offer an opinion here?  If I
> understand correctly, the choices are doc change, code/comment change
> or WONT_FIX.  This seems to be an entry that we can bring to a
> conclusion in this CF with some input from the ltree experts.
>
> We are currently very busy and will look at the problem (and dig into
> our memory) later.  There is also another ltree patch
> (https://commitfest.postgresql.org/23/1977/), it would be nice if
> Filip try it.
>
> I looked at "ltree syntax improvement" patch and found two more very
> old bugs in ltree/lquery (fixes are attached):
>
> 1.  ltree/lquery level counter overflow is wrongly checked:
>
> SELECT nlevel((repeat('a.', 65534) || 'a')::ltree);
>  nlevel
> 
>   65535
> (1 row)
>
> -- expected 65536 or error
> SELECT nlevel((repeat('a.', 65535) || 'a')::ltree);
>  nlevel
> 
>   0
> (1 row)
>
> -- expected 65537 or error
> SELECT nlevel((repeat('a.', 65536) || 'a')::ltree);
>  nlevel
> 
>   1
> (1 row)
>
> -- expected 'a...' or error
> SELECT (repeat('a.', 65535) || 'a')::ltree;
>  ltree
> ---
>
> (1 row)
>
> -- expected 'a...' or error
> SELECT (repeat('a.', 65536) || 'a')::ltree;
>  ltree
> ---
>  a
> (1 row)
>
>
> 2.  '*{a}.*{b}.*{c}' is not equivalent to '*{a+b+c}' (as I expect):
>
> SELECT ltree '1.2' ~ '*{2}';
>  ?column?
> --
>  t
> (1 row)
>
> -- expected true
> SELECT ltree '1.2' ~ '*{1}.*{1}';
>  ?column?
> --
>  f
> (1 row)
>
>
> Maybe these two bugs need a separate thread?
>
>
> Please create separate commitfest entry.



> --
> Nikita Glukhov
> Postgres Professional: http://www.postgrespro.com
> The Russian Postgres Company
>
>
>

-- 
Ibrar Ahmed

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

[Ibrar Ahmed]

Please create separate commitfest entry.

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

[Alexander Korotkov]

Hi Nikita,

On Tue, Jul 16, 2019 at 6:52 PM Nikita Glukhov  wrote:
> I looked at "ltree syntax improvement" patch and found two more very
> old bugs in ltree/lquery (fixes are attached):

Thank you for the fixes.  I've couple notes on them.

0001-Fix-max-size-checking-for-ltree-and-lquery.patch

+#define LTREE_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize / sizeof(nodeitem))
+#define LQUERY_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize / ITEMSIZE)

Looks over caution.  PG_UINT16_MAX is not even close to MaxAllocSize /
sizeof(nodeitem) or MaxAllocSize / ITEMSIZE.

0002-Fix-successive-lquery-ops.patch

diff --git a/contrib/ltree/lquery_op.c b/contrib/ltree/lquery_op.c
index 62172d5..d4f4941 100644
--- a/contrib/ltree/lquery_op.c
+++ b/contrib/ltree/lquery_op.c
@@ -255,8 +255,8 @@ checkCond(lquery_level *curq, int query_numlevel,
ltree_level *curt, int tree_nu
  }
  else
  {
- low_pos = cur_tpos + curq->low;
- high_pos = cur_tpos + curq->high;
+ low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
+ high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
  if (ptr && ptr->q)
  {
  ptr->nq++;
@@ -282,8 +282,8 @@ checkCond(lquery_level *curq, int query_numlevel,
ltree_level *curt, int tree_nu
  }
  else
  {
- low_pos = cur_tpos + curq->low;
- high_pos = cur_tpos + curq->high;
+ low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
+ high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
  }

  curq = LQL_NEXT(curq);

I'm not sure what do these checks do.  Code around is uncommented and
puzzled.  But could we guarantee the same invariant on the stage of
ltree/lquery parsing?

--
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

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

[Nikita Glukhov]

On 09.07.2019 17:57, Oleg Bartunov wrote:

On Mon, Jul 8, 2019 at 7:22 AM Thomas Munro  wrote:

On Sun, Apr 7, 2019 at 3:46 AM Tom Lane  wrote:

=?UTF-8?Q?Filip_Rembia=C5=82kowski?=  writes:

Here is my attempt to fix a 12-years old ltree bug (which is a todo item).
I see it's not backward-compatible, but in my understanding that's
what is documented. Previous behavior was inconsistent with
documentation (where single asterisk should match zero or more
labels).
http://archives.postgresql.org/pgsql-bugs/2007-11/msg00044.php

[...]


In short, I'm wondering if we should treat this as a documentation
bug not a code bug.  But to do that, we'd need a more accurate
description of what the code is supposed to do, because the statement
quoted above is certainly not a match to the actual behavior.

This patch doesn't apply.  More importantly, it seems like we don't
have a consensus on whether we want it.

Teodor, Oleg, would you like to offer an opinion here?  If I
understand correctly, the choices are doc change, code/comment change
or WONT_FIX.  This seems to be an entry that we can bring to a
conclusion in this CF with some input from the ltree experts.

We are currently very busy and will look at the problem (and dig into
our memory) later.  There is also another ltree patch
(https://commitfest.postgresql.org/23/1977/), it would be nice if
Filip try it.


I looked at "ltree syntax improvement" patch and found two more very
old bugs in ltree/lquery (fixes are attached):

1.  ltree/lquery level counter overflow is wrongly checked:

SELECT nlevel((repeat('a.', 65534) || 'a')::ltree);
 nlevel

  65535
(1 row)

-- expected 65536 or error
SELECT nlevel((repeat('a.', 65535) || 'a')::ltree);
 nlevel

  0
(1 row)

-- expected 65537 or error
SELECT nlevel((repeat('a.', 65536) || 'a')::ltree);
 nlevel

  1
(1 row)

-- expected 'a...' or error
SELECT (repeat('a.', 65535) || 'a')::ltree;
 ltree
---
 
(1 row)


-- expected 'a...' or error
SELECT (repeat('a.', 65536) || 'a')::ltree;
 ltree
---
 a
(1 row)


2.  '*{a}.*{b}.*{c}' is not equivalent to '*{a+b+c}' (as I expect):

SELECT ltree '1.2' ~ '*{2}';
 ?column?
--
 t
(1 row)

-- expected true
SELECT ltree '1.2' ~ '*{1}.*{1}';
 ?column?
--
 f
(1 row)


Maybe these two bugs need a separate thread?


--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

>From 5334c92406fd281409594a8861cbb40ca9a8c0a9 Mon Sep 17 00:00:00 2001
From: Nikita Glukhov 
Date: Thu, 7 Mar 2019 17:45:44 +0300
Subject: [PATCH 1/2] Fix max size checking for ltree and lquery

---
 contrib/ltree/expected/ltree.out | 16 
 contrib/ltree/ltree.h|  2 ++
 contrib/ltree/ltree_io.c | 12 ++--
 contrib/ltree/sql/ltree.sql  |  5 +
 4 files changed, 29 insertions(+), 6 deletions(-)

diff --git a/contrib/ltree/expected/ltree.out b/contrib/ltree/expected/ltree.out
index 8226930..30b8247 100644
--- a/contrib/ltree/expected/ltree.out
+++ b/contrib/ltree/expected/ltree.out
@@ -457,6 +457,22 @@ SELECT nlevel('1.2.3.4');
   4
 (1 row)
 
+SELECT nlevel(('1' || repeat('.1', 65534))::ltree);
+ nlevel 
+
+  65535
+(1 row)
+
+SELECT nlevel(('1' || repeat('.1', 65535))::ltree);
+ERROR:  number of ltree levels (65536) exceeds the maximum allowed (65535)
+SELECT ('1' || repeat('.1', 65534))::lquery IS NULL;
+ ?column? 
+--
+ f
+(1 row)
+
+SELECT ('1' || repeat('.1', 65535))::lquery IS NULL;
+ERROR:  number of lquery levels (65536) exceeds the maximum allowed (65535)
 SELECT '1.2'::ltree  < '2.2'::ltree;
  ?column? 
 --
diff --git a/contrib/ltree/ltree.h b/contrib/ltree/ltree.h
index 366e580..0e843e3 100644
--- a/contrib/ltree/ltree.h
+++ b/contrib/ltree/ltree.h
@@ -25,6 +25,7 @@ typedef struct
 
 #define LTREE_HDRSIZE	MAXALIGN( offsetof(ltree, data) )
 #define LTREE_FIRST(x)	( (ltree_level*)( ((char*)(x))+LTREE_HDRSIZE ) )
+#define LTREE_MAX_LEVELS	Min(PG_UINT16_MAX, MaxAllocSize / sizeof(nodeitem))
 
 
 /* lquery */
@@ -77,6 +78,7 @@ typedef struct
 
 #define LQUERY_HDRSIZE	 MAXALIGN( offsetof(lquery, data) )
 #define LQUERY_FIRST(x)   ( (lquery_level*)( ((char*)(x))+LQUERY_HDRSIZE ) )
+#define LQUERY_MAX_LEVELS	Min(PG_UINT16_MAX, MaxAllocSize / ITEMSIZE)
 
 #define LQUERY_HASNOT		0x01
 
diff --git a/contrib/ltree/ltree_io.c b/contrib/ltree/ltree_io.c
index f54f037..460ed1a 100644
--- a/contrib/ltree/ltree_io.c
+++ b/contrib/ltree/ltree_io.c
@@ -58,11 +58,11 @@ ltree_in(PG_FUNCTION_ARGS)
 		ptr += charlen;
 	}
 
-	if (num + 1 > MaxAllocSize / sizeof(nodeitem))
+	if (num + 1 > LTREE_MAX_LEVELS)
 		ereport(ERROR,
 (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
- errmsg("number of levels (%d) exceeds the maximum allowed (%d)",
-		num + 1, (int) (MaxAllocSize / sizeof(nodeitem);
+			

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

[Oleg Bartunov]

On Mon, Jul 8, 2019 at 7:22 AM Thomas Munro  wrote:
>
> On Sun, Apr 7, 2019 at 3:46 AM Tom Lane  wrote:
> > =?UTF-8?Q?Filip_Rembia=C5=82kowski?=  writes:
> > > Here is my attempt to fix a 12-years old ltree bug (which is a todo item).
> > > I see it's not backward-compatible, but in my understanding that's
> > > what is documented. Previous behavior was inconsistent with
> > > documentation (where single asterisk should match zero or more
> > > labels).
> > > http://archives.postgresql.org/pgsql-bugs/2007-11/msg00044.php
>
> [...]
>
> > In short, I'm wondering if we should treat this as a documentation
> > bug not a code bug.  But to do that, we'd need a more accurate
> > description of what the code is supposed to do, because the statement
> > quoted above is certainly not a match to the actual behavior.
>
> This patch doesn't apply.  More importantly, it seems like we don't
> have a consensus on whether we want it.
>
> Teodor, Oleg, would you like to offer an opinion here?  If I
> understand correctly, the choices are doc change, code/comment change
> or WONT_FIX.  This seems to be an entry that we can bring to a
> conclusion in this CF with some input from the ltree experts.

We are currently very busy and will look at the problem (and dig into
our memory)
later.  There is also another ltree patch
(https://commitfest.postgresql.org/23/1977/), it would be
nice if Filip try it.

>
> --
> Thomas Munro
> https://enterprisedb.com



-- 
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

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

[Thomas Munro]

On Sun, Apr 7, 2019 at 3:46 AM Tom Lane  wrote:
> =?UTF-8?Q?Filip_Rembia=C5=82kowski?=  writes:
> > Here is my attempt to fix a 12-years old ltree bug (which is a todo item).
> > I see it's not backward-compatible, but in my understanding that's
> > what is documented. Previous behavior was inconsistent with
> > documentation (where single asterisk should match zero or more
> > labels).
> > http://archives.postgresql.org/pgsql-bugs/2007-11/msg00044.php

[...]

> In short, I'm wondering if we should treat this as a documentation
> bug not a code bug.  But to do that, we'd need a more accurate
> description of what the code is supposed to do, because the statement
> quoted above is certainly not a match to the actual behavior.

This patch doesn't apply.  More importantly, it seems like we don't
have a consensus on whether we want it.

Teodor, Oleg, would you like to offer an opinion here?  If I
understand correctly, the choices are doc change, code/comment change
or WONT_FIX.  This seems to be an entry that we can bring to a
conclusion in this CF with some input from the ltree experts.

-- 
Thomas Munro
https://enterprisedb.com

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

[Tom Lane]

=?UTF-8?Q?Filip_Rembia=C5=82kowski?=  writes:
> Here is my attempt to fix a 12-years old ltree bug (which is a todo item).
> I see it's not backward-compatible, but in my understanding that's
> what is documented. Previous behavior was inconsistent with
> documentation (where single asterisk should match zero or more
> labels).
> http://archives.postgresql.org/pgsql-bugs/2007-11/msg00044.php

I took a quick look through this.  I see where you're going with this,
and I agree that this coding seems like a better match to what it says
in the documentation:

... you can put ! (NOT) at the start to match any label that
doesn't match any of the alternatives.

However, it seems like Teodor and Oleg went to an awful lot of trouble
to implement some other behavior.  It looks like what's there is trying
to do something like "true if this pattern does not match any label
between the matches for whatever's around it", rather than just "true
if this pattern does not match at one specific position".  The number
of changes in the expected output for existing regression test cases
is also disheartening: it's fairly hard to believe that whoever wrote
the test cases didn't think those expected outputs were correct.

In short, I'm wondering if we should treat this as a documentation
bug not a code bug.  But to do that, we'd need a more accurate
description of what the code is supposed to do, because the statement
quoted above is certainly not a match to the actual behavior.

BTW, if we do proceed in this direction, I wonder whether the
ltree_gist code needs any adjustments.

Thoughts?

regards, tom lane