aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTom Lane <tgl@sss.pgh.pa.us>2018-07-13 18:45:30 -0400
committerTom Lane <tgl@sss.pgh.pa.us>2018-07-13 18:45:30 -0400
commit1f47eb08cb42986f1f0c6ef52156f55ba9f7b1a3 (patch)
treefbcd4c8b83706b82e3b0510d1e97a729d75fc0fb
parentf1963a1e79a499c2cf362fa41206a3b9e4348a54 (diff)
downloadpostgresql-1f47eb08cb42986f1f0c6ef52156f55ba9f7b1a3.tar.gz
postgresql-1f47eb08cb42986f1f0c6ef52156f55ba9f7b1a3.zip
Fix crash in contrib/ltree's lca() function for empty input array.
lca_inner() wasn't prepared for the possibility of getting no inputs. Fix that, and make some cosmetic improvements to the code while at it. Also, I thought the documentation of this function as returning the "longest common prefix" of the paths was entirely misleading; it really returns a path one shorter than the longest common prefix, for the typical definition of "prefix". Don't use that term in the docs, and adjust the examples to clarify what really happens. This has been broken since its beginning, so back-patch to all supported branches. Per report from Hailong Li. Thanks to Pierre Ducroquet for diagnosing and for the initial patch, though I whacked it around some and added test cases. Discussion: https://postgr.es/m/5b0d8e4f-f2a3-1305-d612-e00e35a7be66@qunar.com
-rw-r--r--contrib/ltree/expected/ltree.out18
-rw-r--r--contrib/ltree/ltree_op.c34
-rw-r--r--contrib/ltree/sql/ltree.sql3
-rw-r--r--doc/src/sgml/ltree.sgml8
4 files changed, 50 insertions, 13 deletions
diff --git a/contrib/ltree/expected/ltree.out b/contrib/ltree/expected/ltree.out
index 3d5737d41b1..82269309056 100644
--- a/contrib/ltree/expected/ltree.out
+++ b/contrib/ltree/expected/ltree.out
@@ -259,6 +259,24 @@ SELECT lca('{1.2.3,1.2.3.4.5.6}');
1.2
(1 row)
+SELECT lca('{1.2.3}');
+ lca
+-----
+ 1.2
+(1 row)
+
+SELECT lca('{1}'), lca('{1}') IS NULL;
+ lca | ?column?
+-----+----------
+ | f
+(1 row)
+
+SELECT lca('{}') IS NULL;
+ ?column?
+----------
+ t
+(1 row)
+
SELECT lca('1.la.2.3','1.2.3.4.5.6');
lca
-----
diff --git a/contrib/ltree/ltree_op.c b/contrib/ltree/ltree_op.c
index aa1e9918bef..cb59d21ced4 100644
--- a/contrib/ltree/ltree_op.c
+++ b/contrib/ltree/ltree_op.c
@@ -402,22 +402,34 @@ ltree_textadd(PG_FUNCTION_ARGS)
PG_RETURN_POINTER(r);
}
+/*
+ * Common code for variants of lca(), find longest common ancestor of inputs
+ *
+ * Returns NULL if there is no common ancestor, ie, the longest common
+ * prefix is empty.
+ */
ltree *
lca_inner(ltree **a, int len)
{
int tmp,
- num = ((*a)->numlevel) ? (*a)->numlevel - 1 : 0;
- ltree **ptr = a + 1;
- int i,
- reslen = LTREE_HDRSIZE;
+ num,
+ i,
+ reslen;
+ ltree **ptr;
ltree_level *l1,
*l2;
ltree *res;
-
+ if (len <= 0)
+ return NULL; /* no inputs? */
if ((*a)->numlevel == 0)
- return NULL;
+ return NULL; /* any empty input means NULL result */
+
+ /* num is the length of the longest common ancestor so far */
+ num = (*a)->numlevel - 1;
+ /* Compare each additional input to *a */
+ ptr = a + 1;
while (ptr - a < len)
{
if ((*ptr)->numlevel == 0)
@@ -428,11 +440,12 @@ lca_inner(ltree **a, int len)
{
l1 = LTREE_FIRST(*a);
l2 = LTREE_FIRST(*ptr);
- tmp = num;
+ tmp = Min(num, (*ptr)->numlevel - 1);
num = 0;
- for (i = 0; i < Min(tmp, (*ptr)->numlevel - 1); i++)
+ for (i = 0; i < tmp; i++)
{
- if (l1->len == l2->len && memcmp(l1->name, l2->name, l1->len) == 0)
+ if (l1->len == l2->len &&
+ memcmp(l1->name, l2->name, l1->len) == 0)
num = i + 1;
else
break;
@@ -443,6 +456,8 @@ lca_inner(ltree **a, int len)
ptr++;
}
+ /* Now compute size of result ... */
+ reslen = LTREE_HDRSIZE;
l1 = LTREE_FIRST(*a);
for (i = 0; i < num; i++)
{
@@ -450,6 +465,7 @@ lca_inner(ltree **a, int len)
l1 = LEVEL_NEXT(l1);
}
+ /* ... and construct it by copying from *a */
res = (ltree *) palloc0(reslen);
SET_VARSIZE(res, reslen);
res->numlevel = num;
diff --git a/contrib/ltree/sql/ltree.sql b/contrib/ltree/sql/ltree.sql
index e9f74909a64..846b04e48ee 100644
--- a/contrib/ltree/sql/ltree.sql
+++ b/contrib/ltree/sql/ltree.sql
@@ -54,6 +54,9 @@ SELECT lca('{la.2.3,1.2.3.4.5.6,""}') IS NULL;
SELECT lca('{la.2.3,1.2.3.4.5.6}') IS NULL;
SELECT lca('{1.la.2.3,1.2.3.4.5.6}');
SELECT lca('{1.2.3,1.2.3.4.5.6}');
+SELECT lca('{1.2.3}');
+SELECT lca('{1}'), lca('{1}') IS NULL;
+SELECT lca('{}') IS NULL;
SELECT lca('1.la.2.3','1.2.3.4.5.6');
SELECT lca('1.2.3','1.2.3.4.5.6');
SELECT lca('1.2.2.3','1.2.3.4.5.6');
diff --git a/doc/src/sgml/ltree.sgml b/doc/src/sgml/ltree.sgml
index f42e0bf88c0..77599adeafd 100644
--- a/doc/src/sgml/ltree.sgml
+++ b/doc/src/sgml/ltree.sgml
@@ -457,17 +457,17 @@ Europe &amp; Russia*@ &amp; !Transportation
<row>
<entry><function>lca(ltree, ltree, ...)</function><indexterm><primary>lca</primary></indexterm></entry>
<entry><type>ltree</type></entry>
- <entry>lowest common ancestor, i.e., longest common prefix of paths
+ <entry>longest common ancestor of paths
(up to 8 arguments supported)</entry>
- <entry><literal>lca('1.2.2.3','1.2.3.4.5.6')</literal></entry>
+ <entry><literal>lca('1.2.3','1.2.3.4.5.6')</literal></entry>
<entry><literal>1.2</literal></entry>
</row>
<row>
<entry><function>lca(ltree[])</function></entry>
<entry><type>ltree</type></entry>
- <entry>lowest common ancestor, i.e., longest common prefix of paths</entry>
- <entry><literal>lca(array['1.2.2.3'::ltree,'1.2.3'])</literal></entry>
+ <entry>longest common ancestor of paths in array</entry>
+ <entry><literal>lca(array['1.2.3'::ltree,'1.2.3.4'])</literal></entry>
<entry><literal>1.2</literal></entry>
</row>