Canonical type nodes, or, comptypes considered harmful

[Mike Stump]

On Nov 7, 2006, at 7:13 PM, Doug Gregor wrote:
> Now, how much do we worry about the fact that we won't be printing  
> typedef names

The only potential language gotcha I can think of is:

5 If the typedef declaration defines an unnamed  class  (or  enum),  the
   first  typedef-name  declared by the declaration to be that class  
type
   (or enum type) is used to denote the class type  (or  enum  type)   
for
   linkage purposes only (_basic.link_).  [Example:
   typedef struct { } *ps, S;      // S is the class name for linkage  
purposes
     --end example]

we still gotta get that right.  I think this just changes the  
underlying type and doesn't have any typedef bits to it.

As for warning/error messages, I'd hate to regress on that front.   
Doug, as a heavy template user, I'm sure you've see plenty of warning/ 
error messages...  How important is the typedef name in your experience?

> when we combine duplicate nodes? If we don't care, our job is much  
> easier. If we do care, then we need to introduce a system for  
> equivalence classes to keep those typedef names, which will  
> complicate matters a bit.

I agree, it will complicate things if we want the typedef name  
around.  I'm thinking of an inverse mapping that takes us from tuple 
(context,type) to typedef name.  I want to boost the typedef name  
out, kinda like a flyweight pattern, but inverted, instead of  
boosting the invariant out, I want to raise the variant (the typedef  
name) out of the type.  Imagine if we had a map (tuple(context, type)  
-> typedef name, and when we wanted the possible typedef name, we  
take the type and the context in which we got the type and look it up  
in the map.  If not found, no typedef name.  If found, it is the  
typedef name we're interested in.  The benefit of this scheme would  
be that constant time type equality operators remain constant time.   
Producing error messages is slow, but we don't care about that.

Each place that `moves' a type around where we want to preserve the  
typedef would instead have to call move_typedef (new_context,  
old_context, type), which would register the found typedef map(tuple 
(old_context, type) into the tuple(new_context, type) slot in the map.

The map can be added after the fact, if we ripped out the typedef  
name, if we think it isn't important and then later we want to add it  
back in.

> Since we know that type canonicalization is incremental, could we work
> toward type canonicalization in the GCC 4.3 time frame?

If by we you mean you, I don't see why that would be a bad  
idea.  :-)  The risk is if one invests all this effort, and the win  
turns out to be < 1% on real code and 10x on benchmark code, one  
feels bad.  The was the net result of the template-3 patch, nice 10x  
compile time speedup, on more normal code, just a bit slower (2.436%).