Canonical type nodes, or, comptypes considered harmful

[Doug Gregor]

On 10 Nov 2006 19:15:45 +0100, Gabriel Dos Reis
<gdr@integrable-solutions.net> wrote:
> "Doug Gregor" <doug.gregor@gmail.com> writes:
> | With concepts, there are cases where we end up creating two different
> | type nodes that we later find out should have been the same type node.
> | Here's an example:
> |
> |   template<typename T, typename U>
> |   where LessThanComparable<T> && SameType<T, U>
> |   const T& weird_min(const T& t, const U& u) {
> |     return t < u? t : u;
> |   }
> |
> | When we parse the template header, we create two different type nodes
> | for T and U. Then we start parsing the where clause, and create a type
> | node for LessThanComparable<T>. Now we hit the SameType requirement,
> | which says that T and U are the same type. It's a little late to make
> | T and U actually have the same type node (unless we want to re-parse
> | the template or re-write the AST).
>
> I don't think that implies rewriting the AST or reparsing.  The
> same-type constraints reads to me that "it is assume T and U have the
> same canonical type", e.g. the predicate SameType<T, U> translates to
> the constraints
>
>      TYPE_CANONICAL(T) == TYPE_CANONICAL(U)
>
> this equation can be added the constraint set without reparsing (it is
> a semantic constraint).

Yes, but there are types built from 'T' and 'U' that also need to be
"merged" in this way. For instance, say we have built the types T* and
U* before seeing that same-type constraint. Now, we also need
TYPE_CANONICAL (T*) == TYPE_CANONICAL (U*).
And TYPE_CANONICAL(LessThanComparable<T>) ==
TYPE_CANONICAL(LessThanComparable<U>).
If you know about all of these other types that have been built from T
and U, you can use Nelson and Oppen's algorithm to update the
TYPE_CANONICAL information relatively quickly. If you don't have that
information... you're stuck with structural checks or rewriting the
AST to eliminate the duplicated nodes.

  Cheers,
  Doug