Skip to content

Commit 1f47eb0

Browse files
tglsfdctglsfdc
committed
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
1 parent f1963a1 commit 1f47eb0

File tree

4 files changed

+50
-13
lines changed

4 files changed

+50
-13
lines changed

‎contrib/ltree/expected/ltree.out

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -259,6 +259,24 @@ SELECT lca('{1.2.3,1.2.3.4.5.6}');
259259
1.2
260260
(1 row)
261261

262+
SELECT lca('{1.2.3}');
263+
lca
264+
-----
265+
1.2
266+
(1 row)
267+
268+
SELECT lca('{1}'), lca('{1}') IS NULL;
269+
lca | ?column?
270+
-----+----------
271+
| f
272+
(1 row)
273+
274+
SELECT lca('{}') IS NULL;
275+
?column?
276+
----------
277+
t
278+
(1 row)
279+
262280
SELECT lca('1.la.2.3','1.2.3.4.5.6');
263281
lca
264282
-----

‎contrib/ltree/ltree_op.c

Lines changed: 25 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -402,22 +402,34 @@ ltree_textadd(PG_FUNCTION_ARGS)
402402
PG_RETURN_POINTER(r);
403403
}
404404

405+
/*
406+
* Common code for variants of lca(), find longest common ancestor of inputs
407+
*
408+
* Returns NULL if there is no common ancestor, ie, the longest common
409+
* prefix is empty.
410+
*/
405411
ltree *
406412
lca_inner(ltree **a, int len)
407413
{
408414
int tmp,
409-
num = ((*a)->numlevel) ? (*a)->numlevel - 1 : 0;
410-
ltree **ptr = a + 1;
411-
int i,
412-
reslen = LTREE_HDRSIZE;
415+
num,
416+
i,
417+
reslen;
418+
ltree **ptr;
413419
ltree_level *l1,
414420
*l2;
415421
ltree *res;
416422

417-
423+
if (len <= 0)
424+
return NULL; /* no inputs? */
418425
if ((*a)->numlevel == 0)
419-
return NULL;
426+
return NULL; /* any empty input means NULL result */
427+
428+
/* num is the length of the longest common ancestor so far */
429+
num = (*a)->numlevel - 1;
420430

431+
/* Compare each additional input to *a */
432+
ptr = a + 1;
421433
while (ptr - a < len)
422434
{
423435
if ((*ptr)->numlevel == 0)
@@ -428,11 +440,12 @@ lca_inner(ltree **a, int len)
428440
{
429441
l1 = LTREE_FIRST(*a);
430442
l2 = LTREE_FIRST(*ptr);
431-
tmp = num;
443+
tmp = Min(num, (*ptr)->numlevel - 1);
432444
num = 0;
433-
for (i = 0; i < Min(tmp, (*ptr)->numlevel - 1); i++)
445+
for (i = 0; i < tmp; i++)
434446
{
435-
if (l1->len == l2->len && memcmp(l1->name, l2->name, l1->len) == 0)
447+
if (l1->len == l2->len &&
448+
memcmp(l1->name, l2->name, l1->len) == 0)
436449
num = i + 1;
437450
else
438451
break;
@@ -443,13 +456,16 @@ lca_inner(ltree **a, int len)
443456
ptr++;
444457
}
445458

459+
/* Now compute size of result ... */
460+
reslen = LTREE_HDRSIZE;
446461
l1 = LTREE_FIRST(*a);
447462
for (i = 0; i < num; i++)
448463
{
449464
reslen += MAXALIGN(l1->len + LEVEL_HDRSIZE);
450465
l1 = LEVEL_NEXT(l1);
451466
}
452467

468+
/* ... and construct it by copying from *a */
453469
res = (ltree *) palloc0(reslen);
454470
SET_VARSIZE(res, reslen);
455471
res->numlevel = num;

‎contrib/ltree/sql/ltree.sql

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -54,6 +54,9 @@ SELECT lca('{la.2.3,1.2.3.4.5.6,""}') IS NULL;
5454
SELECT lca('{la.2.3,1.2.3.4.5.6}') IS NULL;
5555
SELECT lca('{1.la.2.3,1.2.3.4.5.6}');
5656
SELECT lca('{1.2.3,1.2.3.4.5.6}');
57+
SELECT lca('{1.2.3}');
58+
SELECT lca('{1}'), lca('{1}') IS NULL;
59+
SELECT lca('{}') IS NULL;
5760
SELECT lca('1.la.2.3','1.2.3.4.5.6');
5861
SELECT lca('1.2.3','1.2.3.4.5.6');
5962
SELECT lca('1.2.2.3','1.2.3.4.5.6');

‎doc/src/sgml/ltree.sgml

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -457,17 +457,17 @@ Europe &amp; Russia*@ &amp; !Transportation
457457
<row>
458458
<entry><function>lca(ltree, ltree, ...)</function><indexterm><primary>lca</primary></indexterm></entry>
459459
<entry><type>ltree</type></entry>
460-
<entry>lowest common ancestor, i.e., longest common prefix of paths
460+
<entry>longest common ancestor of paths
461461
(up to 8 arguments supported)</entry>
462-
<entry><literal>lca('1.2.2.3','1.2.3.4.5.6')</literal></entry>
462+
<entry><literal>lca('1.2.3','1.2.3.4.5.6')</literal></entry>
463463
<entry><literal>1.2</literal></entry>
464464
</row>
465465

466466
<row>
467467
<entry><function>lca(ltree[])</function></entry>
468468
<entry><type>ltree</type></entry>
469-
<entry>lowest common ancestor, i.e., longest common prefix of paths</entry>
470-
<entry><literal>lca(array['1.2.2.3'::ltree,'1.2.3'])</literal></entry>
469+
<entry>longest common ancestor of paths in array</entry>
470+
<entry><literal>lca(array['1.2.3'::ltree,'1.2.3.4'])</literal></entry>
471471
<entry><literal>1.2</literal></entry>
472472
</row>
473473

0 commit comments

Comments
 (0)