Data structure for using directive

Data structure for using directive

[Gabriel Dos Reis]

Hi,

Consider C++ PR/2455 :

   namespace A { }
   namespace B { using namespace A; }
   namespace A { using namespace B; }
   void f() { using namespace B; }

This has the remarkable property of sending cc1plus into an infinite
loop because of the following:

   /* Add namespace to using_directives. Return NULL_TREE if nothing was
      changed (i.e. there was already a directive), or the fresh
      TREE_LIST otherwise.  */

   tree
   push_using_directive (used)
	tree used;
   {
     tree ud = current_binding_level->using_directives;
     tree iter, ancestor;

     /* Check if we already have this. */
     if (purpose_member (used, ud) != NULL_TREE)
       return NULL_TREE;

     /* Recursively add all namespaces used. */
     for (iter = DECL_NAMESPACE_USING (used); iter; iter = TREE_CHAIN (iter))
       push_using_directive (TREE_PURPOSE (iter));

     ancestor = namespace_ancestor (current_decl_namespace (), used);
     ud = current_binding_level->using_directives;
     ud = tree_cons (used, ancestor, ud);
     current_binding_level->using_directives = ud;
     return ud;
   }

I think that handling of using-directives is no good:
   1) In the favorable case, each time we encounter a using-directive
      we go through and push the used-namespace and the namespaces it
      uses into the set of used-namespaces of the namespace enclosing the
      using-directive.  Therefore duplicating information.  An
      immediate consequence is that we end up using an extra bit for
      distinguishing a directly used namespace from an indirectly
      used-namespace.  An inconvenient artefact.

   2) In the worst situation like PR/2455, we go into infinite loop
      because upon
 
           namespace A { using namespace B; }

      we insist on pushing the namespaces used by B (here A) into the
      set of used namespace of A an recursively :-(

I think a better approach would be using a splay_tree to store the
used-namespace as the KEY and the common ancestor as the VALUE. This
has the following benefit:

   1) no opportunity of going into infinite loop
   2) no need for an extra word for distinguishing a directly-used
      from an indirectly-used namespace.

The above requires me changing DECL_NAMESPACE_USING use a field of a 
'struct tree_decl' that has a compatible-type (or that can be made so)
with splay_tree.  I'm thinking of DECL_POINTER_ALIAS_SET.  Thoughts?

-- Gaby

Re: Data structure for using directive

[Geoff Keating]

Gabriel Dos Reis <gdr@integrable-solutions.net> writes:

> The above requires me changing DECL_NAMESPACE_USING use a field of a 
> 'struct tree_decl' that has a compatible-type (or that can be made so)
> with splay_tree.  I'm thinking of DECL_POINTER_ALIAS_SET.  Thoughts?

I'm not quite sure what you're thinking of with the above paragraph,
but if you're planning to add a pointer to a splay_tree into the tree
datatype, you might want to consider doing it on the pch-branch
because in mainline splay_tree is not GCable.

-- 
- Geoffrey Keating <geoffk@geoffk.org> <geoffk@redhat.com>

Re: Data structure for using directive

[Gabriel Dos Reis]

Geoff Keating <geoffk@geoffk.org> writes:

| Gabriel Dos Reis <gdr@integrable-solutions.net> writes:
| 
| > The above requires me changing DECL_NAMESPACE_USING use a field of a 
| > 'struct tree_decl' that has a compatible-type (or that can be made so)
| > with splay_tree.  I'm thinking of DECL_POINTER_ALIAS_SET.  Thoughts?
| 
| I'm not quite sure what you're thinking of with the above paragraph,
| but if you're planning to add a pointer to a splay_tree into the tree
| datatype, you might want to consider doing it on the pch-branch
| because in mainline splay_tree is not GCable.

Hmm, my intent is to fix PR/2455 on mainline... 

But your point on GCable field tells me I should be careful about not
fooliing the GC.  Thanks.

[ hmm, I'm dreaming of the day we'll get rid of the catch-all tree ]

-- Gaby