Re: About connectby() again - Mailing list pgsql-hackers

Masaru Sugawara wrote:
> The previous patch fixed an infinite recursion bug in
> contrib/tablefunc/tablefunc.c:connectby. But, other unmanageable error
> seems to occur even if a table has commonplace tree data(see below).
>
> I would think the patch, ancestor check, should be
>
>   if (strstr(branch_delim || branchstr->data || branch_delim,
>                        branch_delim || current_key || branch_delim))
>
> This is my image, not a real code. However, if branchstr->data includes
> branch_delim, my image will not be perfect.

Good point. Thank you Masaru for the suggested fix.

Attached is a patch to fix the bug found by Masaru. His example now produces:

regression=# SELECT * FROM connectby('connectby_tree', 'keyid',
'parent_keyid', '11', 0, '-') AS t(keyid int, parent_keyid int, level int,
branch text);
  keyid | parent_keyid | level |  branch
-------+--------------+-------+----------
     11 |              |     0 | 11
     10 |           11 |     1 | 11-10
    111 |           11 |     1 | 11-111
      1 |          111 |     2 | 11-111-1
(4 rows)

While making the patch I also realized that the "no show branch" form of the
function was not going to work very well for recursion detection. Therefore
there is now a default branch delimiter ('~') that is used internally, for
that case, to enable recursion detection to work. If you need a different
delimiter for your specific data, you will have to use the "show branch" form
of the function.

If there are no objections, please apply. Thanks,

Joe
Index: contrib/tablefunc/README.tablefunc
===================================================================
RCS file: /opt/src/cvs/pgsql-server/contrib/tablefunc/README.tablefunc,v
retrieving revision 1.3
diff -c -r1.3 README.tablefunc
*** contrib/tablefunc/README.tablefunc    2 Sep 2002 05:44:04 -0000    1.3
--- contrib/tablefunc/README.tablefunc    26 Sep 2002 22:57:27 -0000
***************
*** 365,371 ****

    branch_delim

!     if optional branch value is desired, this string is used as the delimiter

  Outputs

--- 365,373 ----

    branch_delim

!     If optional branch value is desired, this string is used as the delimiter.
!     When not provided, a default value of '~' is used for internal
!     recursion detection only, and no "branch" field is returned.

  Outputs

***************
*** 388,394 ****
       the level value output

    3. If the branch field is not desired, omit both the branch_delim input
!      parameter *and* the branch field in the query column definition

    4. If the branch field is desired, it must be the forth column in the query
       column definition, and it must be type TEXT
--- 390,399 ----
       the level value output

    3. If the branch field is not desired, omit both the branch_delim input
!      parameter *and* the branch field in the query column definition. Note
!      that when branch_delim is not provided, a default value of '~' is used
!      for branch_delim for internal recursion detection, even though the branch
!      field is not returned.

    4. If the branch field is desired, it must be the forth column in the query
       column definition, and it must be type TEXT
Index: contrib/tablefunc/tablefunc.c
===================================================================
RCS file: /opt/src/cvs/pgsql-server/contrib/tablefunc/tablefunc.c,v
retrieving revision 1.9
diff -c -r1.9 tablefunc.c
*** contrib/tablefunc/tablefunc.c    14 Sep 2002 19:32:54 -0000    1.9
--- contrib/tablefunc/tablefunc.c    26 Sep 2002 23:09:27 -0000
***************
*** 652,657 ****
--- 652,660 ----
          branch_delim = GET_STR(PG_GETARG_TEXT_P(5));
          show_branch = true;
      }
+     else
+         /* default is no show, tilde for the delimiter */
+         branch_delim = pstrdup("~");

      per_query_ctx = rsinfo->econtext->ecxt_per_query_memory;
      oldcontext = MemoryContextSwitchTo(per_query_ctx);
***************
*** 798,807 ****
--- 801,816 ----
          char       *current_branch;
          char      **values;
          StringInfo    branchstr = NULL;
+         StringInfo    chk_branchstr = NULL;
+         StringInfo    chk_current_key = NULL;

          /* start a new branch */
          branchstr = makeStringInfo();

+         /* need these to check for recursion */
+         chk_branchstr = makeStringInfo();
+         chk_current_key = makeStringInfo();
+
          if (show_branch)
              values = (char **) palloc(CONNECTBY_NCOLS * sizeof(char *));
          else
***************
*** 854,875 ****
          {
              /* initialize branch for this pass */
              appendStringInfo(branchstr, "%s", branch);

              /* get the next sql result tuple */
              spi_tuple = tuptable->vals[i];

              /* get the current key and parent */
              current_key = SPI_getvalue(spi_tuple, spi_tupdesc, 1);
              current_key_parent = pstrdup(SPI_getvalue(spi_tuple, spi_tupdesc, 2));

-             /* check to see if this key is also an ancestor */
-             if (strstr(branchstr->data, current_key))
-                 elog(ERROR, "infinite recursion detected");
-
              /* get the current level */
              sprintf(current_level, "%d", level);

!             /* extend the branch */
              appendStringInfo(branchstr, "%s%s", branch_delim, current_key);
              current_branch = branchstr->data;

--- 863,886 ----
          {
              /* initialize branch for this pass */
              appendStringInfo(branchstr, "%s", branch);
+             appendStringInfo(chk_branchstr, "%s%s%s", branch_delim, branch, branch_delim);

              /* get the next sql result tuple */
              spi_tuple = tuptable->vals[i];

              /* get the current key and parent */
              current_key = SPI_getvalue(spi_tuple, spi_tupdesc, 1);
+             appendStringInfo(chk_current_key, "%s%s%s", branch_delim, current_key, branch_delim);
              current_key_parent = pstrdup(SPI_getvalue(spi_tuple, spi_tupdesc, 2));

              /* get the current level */
              sprintf(current_level, "%d", level);

!             /* check to see if this key is also an ancestor */
!             if (strstr(chk_branchstr->data, chk_current_key->data))
!                 elog(ERROR, "infinite recursion detected");
!
!             /* OK, extend the branch */
              appendStringInfo(branchstr, "%s%s", branch_delim, current_key);
              current_branch = branchstr->data;

***************
*** 913,918 ****
--- 924,935 ----
              /* reset branch for next pass */
              xpfree(branchstr->data);
              initStringInfo(branchstr);
+
+             xpfree(chk_branchstr->data);
+             initStringInfo(chk_branchstr);
+
+             xpfree(chk_current_key->data);
+             initStringInfo(chk_current_key);
          }
      }