Thread: WIP list rewrite

I've attached the latest list rewrite patch (gzip'ed, against current
sources). Unfortunately, the compatibility API we defined earlier wasn't
that effective: it was more efficient for me to look at more or less
every lfirst() call site in the backend and rewrite it as necessary than
to just start up the backend and wait for things to break. I've done
that now, so I think the patch is fairly close to being ready for
application.

Known problems/TODOs:

- rewrite some macros to be GCC inline functions to avoid
double-evaluation, per discussion off list with Tom

- reorganize list.c to get rid of list_append_auto() and so on, per
discussion off list with Tom

- adapt a few tricky spots in the code to the new list API (e.g.
catalog/dependency.c circa line 994, optimizer/prep/prepunion.c circa
line 662)

- change over more code to use the new forboth() macro (this can wait
until the initial work is applied)

- add a new macro/function that gives the value of the head node, given
a List. Right now, there are lots of places that do:

lfirst(list_head(some_list))

which ought to be a single macro for code clarity (we'd need _int and
_oid variants, as well). Any suggestions for what to name this? I'm
thinking linitial(), but I'm open to alternatives

- fix the remaining bugs this patch has introduced. At the moment, I'm
trying to track down the following bug:

SELECT n.nspname as "Schema",
   c.relname as "Name",
   CASE c.relkind WHEN 'r' THEN 'table' WHEN 'v' THEN 'view' WHEN 'i'
THEN 'index' WHEN 'S' THEN 'sequence' WHEN 's' THEN 'special' END as "Type",
   u.usename as "Owner"
FROM pg_catalog.pg_class c
      LEFT JOIN pg_catalog.pg_user u ON u.usesysid = c.relowner
      LEFT JOIN pg_catalog.pg_namespace n ON n.oid = c.relnamespace
WHERE c.relkind IN ('r','v','S','')
       AND n.nspname NOT IN ('pg_catalog', 'pg_toast')
       AND pg_catalog.pg_table_is_visible(c.oid)
ORDER BY 1,2;
==> ERROR:  table reference "c" is ambiguous

It seems we're mangling pstate->p_namespace in parse_relation.c somehow,
but I haven't managed to figure out why yet (any suggestions welcome)

I'm working hard to get this finished by the end of this week.

-Neil

Neil Conway <neilc@samurai.com> writes:
> I've attached the latest list rewrite patch (gzip'ed, against current
> sources). Unfortunately, the compatibility API we defined earlier wasn't
> that effective: it was more efficient for me to look at more or less
> every lfirst() call site in the backend and rewrite it as necessary than
> to just start up the backend and wait for things to break.

I'm surprised you did that much work and did not fix things to
distinguish ListCell * from List * ... we're gonna have to make
another pass over all these places to do that.

I wonder whether it wasn't a bad idea to define the compatibility API
to try to gloss over the type difference between ListCell* and List*.
I have a strong suspicion that some of the "remaining bugs" you mention
would be caught by enabling the compiler to complain about using one
pointer type where the other is needed.

> It seems we're mangling pstate->p_namespace in parse_relation.c somehow,
> but I haven't managed to figure out why yet (any suggestions welcome)

Odd, the p_namespace manipulations look straightforward enough.  I
wonder if this could be a double-evaluation issue?

> I'm working hard to get this finished by the end of this week.

Offer of help is still open, if you want to try to divvy up the
remaining work.  I really want to see this get in.

            regards, tom lane

Tom Lane wrote:
> I'm surprised you did that much work and did not fix things to
> distinguish ListCell * from List * ... we're gonna have to make
> another pass over all these places to do that.

That would mean changing _every_ usage of foreach(), and a bunch of
other places besides; plus, once one changes an iteration variable to be
ListCell*, you get compiler warnings if you don't disable the list
compat API for the entire file. Since the hope was to make the changes
minimally invasive, I figured I could do this once the initial work is
in CVS.

Also, I'm not so worried about changes that are effectively
s/List/ListCell/ in a bunch of places -- they can largely be automated...

> Offer of help is still open, if you want to try to divvy up the
> remaining work.

I'd be happy to accept some help (Alvaro was kind enough to offer as
well), if we can figure out a reasonable way to divide the work up (say,
if this work were being done in a CVS branch... too late for that now
though). Any thoughts on how best to do this?

At any rate, once the initial work is in CVS then anyone can submit
patches to update particular parts of the tree to use the new API.

> I really want to see this get in.

As do I.

BTW, should I take your lack of comment on linitial() as "no objection"?

-Neil

Neil Conway <neilc@samurai.com> writes:
> BTW, should I take your lack of comment on linitial() as "no objection"?

Make it "no better idea" ;-)

A couple hours' poking at the patch yielded the attached two diffs
and the realization that list_difference_private cannot work, because
its first call to list_append_auto will crash due to new_list being NIL.
We had already talked about getting rid of the _auto functions, and I'd
now say that's a must not just cosmetic cleanup.

            regards, tom lane

*** src/backend/nodes/list.c~    Sun May 23 23:20:34 2004
--- src/backend/nodes/list.c    Sun May 23 23:56:39 2004
***************
*** 433,439 ****
      if (n == list->length - 1)
          return list->tail;

!     for (match = list->head; --n > 0; match = match->next)
          ;

      return match;
--- 433,439 ----
      if (n == list->length - 1)
          return list->tail;

!     for (match = list->head; n-- > 0; match = match->next)
          ;

      return match;
*** src/backend/optimizer/plan/createplan.c~    Sun May 23 23:20:34 2004
--- src/backend/optimizer/plan/createplan.c    Mon May 24 00:19:32 2004
***************
*** 1273,1279 ****
           * Now, determine which index attribute this is, change the
           * indexkey operand as needed, and get the index opclass.
           */
!         lfirst(newclause->args) = fix_indxqual_operand(lfirst(list_head(newclause->args)),
                                                         baserelid,
                                                         index,
                                                         &opclass);
--- 1273,1279 ----
           * Now, determine which index attribute this is, change the
           * indexkey operand as needed, and get the index opclass.
           */
!         lfirst(list_head(newclause->args)) = fix_indxqual_operand(lfirst(list_head(newclause->args)),
                                                         baserelid,
                                                         index,
                                                         &opclass);

Tom Lane wrote:
> A couple hours' poking at the patch yielded the attached two diffs

Thanks Tom!

> and the realization that list_difference_private cannot work, because
> its first call to list_append_auto will crash due to new_list being NIL.

Yeah, I noticed an analogous problem in list_union(), I'd been meaning
to take a look at list_difference(). I'll post an updated patch tomorrow.

-Neil