Skip to content

Commit 330cad2

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 073ffef commit 330cad2

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
@@ -251,6 +251,24 @@ SELECT lca('{1.2.3,1.2.3.4.5.6}');
251251
1.2
252252
(1 row)
253253

254+
SELECT lca('{1.2.3}');
255+
lca
256+
-----
257+
1.2
258+
(1 row)
259+
260+
SELECT lca('{1}'), lca('{1}') IS NULL;
261+
lca | ?column?
262+
-----+----------
263+
| f
264+
(1 row)
265+
266+
SELECT lca('{}') IS NULL;
267+
?column?
268+
----------
269+
t
270+
(1 row)
271+
254272
SELECT lca('1.la.2.3','1.2.3.4.5.6');
255273
lca
256274
-----

‎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
@@ -49,6 +49,9 @@ SELECT lca('{la.2.3,1.2.3.4.5.6,""}') IS NULL;
4949
SELECT lca('{la.2.3,1.2.3.4.5.6}') IS NULL;
5050
SELECT lca('{1.la.2.3,1.2.3.4.5.6}');
5151
SELECT lca('{1.2.3,1.2.3.4.5.6}');
52+
SELECT lca('{1.2.3}');
53+
SELECT lca('{1}'), lca('{1}') IS NULL;
54+
SELECT lca('{}') IS NULL;
5255
SELECT lca('1.la.2.3','1.2.3.4.5.6');
5356
SELECT lca('1.2.3','1.2.3.4.5.6');
5457
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)