Patchwork Require canonical type comparison for typedefs again.

login
register
mail settings
Submitter Dodji Seketeli
Date Sept. 25, 2010, 3:19 p.m.
Message ID <m3lj6p4zre.fsf@seketeli.org>
Download mbox | patch
Permalink /patch/65746/
State New
Headers show

Comments

Dodji Seketeli - Sept. 25, 2010, 3:19 p.m.
Hello,

I have reworked the patch to address your points. Please see my comments
below.

Jason Merrill <jason@redhat.com> writes:

> On 09/20/2010 12:29 PM, Dodji Seketeli wrote:
>>  #define TEMPLATE_TYPE_PARM_SIBLING_PARMS(NODE) \
>> -  (TREE_CHECK ((NODE), TEMPLATE_TYPE_PARM))->type.maxval
>> +  (TREE_CHECK3 ((NODE), TEMPLATE_TYPE_PARM,    \
>> +		TEMPLATE_TEMPLATE_PARM,	       \
>> +		BOUND_TEMPLATE_TEMPLATE_PARM))->type.maxval
>
> With your patch we aren't actually using this list anymore, only its
> length, so we might as well just store the length directly rather than
> the list.  That way, this:
>
>> +      /* If T1 belongs to a not-yet fully parsed template parameters
>> +	 list, let's assume it's different from T2 which belongs to an
>> +	 already fully parsed template template parameters list.  */
>> +      if ((TEMPLATE_TYPE_PARM_SIBLING_PARMS
>> +	   (TYPE_MAIN_VARIANT (t1)) != NULL_TREE)
>> +	  != (TEMPLATE_TYPE_PARM_SIBLING_PARMS
>> +	      (TYPE_MAIN_VARIANT (t1)) != NULL_TREE))
>> +	return false;
>> +
>> +      /* If T1 and T2 belong to template parm lists of different
>> +	 size, then can't be equal.  */
>> +      if ((TEMPLATE_TYPE_PARM_SIBLING_PARMS
>> +	   (TYPE_MAIN_VARIANT (t1)) != NULL_TREE)
>> +	  && (TEMPLATE_TYPE_PARM_SIBLING_PARMS
>> +	      (TYPE_MAIN_VARIANT (t2)) != NULL_TREE)
>> +	  && (TREE_VEC_LENGTH (INNERMOST_TEMPLATE_PARMS
>> +			       (TEMPLATE_TYPE_PARM_SIBLING_PARMS
>> +				(TYPE_MAIN_VARIANT (t1))))
>> +	      != TREE_VEC_LENGTH (INNERMOST_TEMPLATE_PARMS
>> +				  (TEMPLATE_TYPE_PARM_SIBLING_PARMS
>> +				   (TYPE_MAIN_VARIANT (t2))))))
>> +	return false;
>
> Can become a single simple comparison.  Which should go into
> comp_template_parms_position.
>

Nice. I have done that.

>> +/* Contains canonical template parameter types. The vector is indexed
>> +   by the TEMPLATE_TYPE_IDX of the template parameter. Each element is
>> +   a TREE_LIST, whose TREE_PURPOSE is a INT_CST tree representing a
>> +   total size of the template parameter list a given template
>> +   parameter would belong too, and whose TREE_VALUEs contain the
>> +   canonical template parameters of various types and levels,
>> +   belonging to a set of template parameters which size is
>> +   TREE_PURPOSE.  */
>>  static GTY(()) VEC(tree,gc) *canonical_template_parms;
>
> Since we're adding more elements to this table, maybe we should
> convert it to a hash table.  But that can be a follow-on patch.
>

Sure. I'll post a separate patch for it once we are done with this one.

>> +  if (total_num_parms == 0)
>> +    return NULL_TREE;
>
> Since you're already treating parms from a list of unknown length as
> distinct from parms from a list of known length, we can give them a
> canonical type, too.
>

Doing that doesn't seem to work. The problem is not with the comparison
of type template parms but rather with the comparison of dependent types
created during the template parms parsing.

If type template parms don't require structural comparison then a type A
(created during template parms parsing) dependent on those parms will
have a canonical type. The fixup then creates a type A' that is
structurally equivalent to A, but has a different canonical type. Later,
possible calls to lookup_template_class could then compare A and A' and
the sanity constraints activated by ENABLE_CHECKING in comptypes would
be violated because two structurally equivalent types have different
canonical types.

We don't have the issue in comptypes if A doesn't have a canonical type
to begin with.

>> +      if (TREE_CODE (parm) == TYPE_DECL
>> +	     || TREE_CODE (parm) == TEMPLATE_DECL)
>> +	{
>> +	  /* Compute the canonical type of type template
>> +	     parameters and their variants.  */
>
> Hmm, don't we need to handle substituting type parameters into
> template parameters?
>
> template <class T, template <T> class U> struct A { };
>
> It should work to do a single loop over the template args, doing any
> substitution and then replacing them with their canonical variants as
> appropriate.  Since a particular parameter can only refer to previous
> ones, we can't run into ordering issues.
>

Good catch.

I have done this but it made me scratch head for a little while because
tsubsting into the parms of a template template parm wasn't as straight
forward as I thought it would be.

The issue where the followings.

* Template parm level reduction.

When at least one of the parms is itself a template [like in
testsuite/g++.old-deja/g++.pt/nttp1.C] then at some point we end up in
tsubst (at least) with an argument set that has a depth that is less
than the depth of the parm of the template template parm we are
susbtituting into.

My understanding is that the tsubsting code then thinks that we are
doing the substitution for the purpose of instantiation and then reduces
the level of the resulting parms.

In this current case though, we are not doing the substitution for the
purpose of instantiation; we want the levels of all the resulting
tsubsted parms to remain unchanged; we want an "in place substitution"
so to speak.

So I introduced a new tf_no_tpl_reduce (for "no template parm level
reduce") flag in enum tsubst_flags and changed tsubst and
tsubst_template_parms to avoid doing level reduction when passed this
flag.]

Incidentally I noticed that the tf_no_class_instantiation is not used by
any client code anymore. Would you accept a patchlet to remove it?

* I had to use use_template_parms in make_typename_type

I know I have to be careful each time I use use_template_parms instead
of dependent_type_p so I'll give some context.

Consider this example distilled from testsuite/g++.dg/template/ttp25.C:

~=~
template<typename T> struct metafun { typedef T type; };

template<typename T, template<typename metafun<T>::type> class C> //#0
void f4(T, C<5>);

template<int N> struct X {};
void g() {
  f4(5, X<5>()); // OK.
}
~=~

Consider when we build the set of overload candidate functions for
f4(5, X<5>()). add_template_candidate_real at some point tries to deduce the
template argument to C.

During unification of C<5> with X<5> the argument 5 of X is converted
into the type of the parameter of C, i.e 5 is converted into typename
metafun<T>::type. convert_template_argument then tries to substitute
into typename metafun<T>::type. This should just create another
equivalent typename becase metafun<T> is dependent and thus non
complete. But when tsubst calls make_typename_type, the later fails to
detect that metafun<T> is dependent [because processing_template_decl is
0] and goes crazy. As tsubst uses use_template_parms to detect that
metafun<T> is dependent before calling make_typename_type, I thought I'd
use the same in the later.

Interestingly, the reason why this wasn't happening before is, in #0,
when lookup_class_template is called to build the type of metafun<T>,
that template-id is considered as naming template<class T> struct
metafun; so its canonical type is set to the TREE_TYPE of the
TEMPLATE_DECL of metafun. That type is complete. So later when
make_typename_type is called during the overload resolution of
f4(5, X<5>()), the "if (!dependent_scope_p (context))" succeeds and the
call to t = lookup_field (context, name, 2, /*want_type=*/true);
returns the field "type".

Tested for the c++ languages against trunk on
x86_64-unknown-linux-gnu. I am going launch a test for the other
languages right away.
Jason Merrill - Sept. 25, 2010, 11:31 p.m.
On 09/25/2010 11:19 AM, Dodji Seketeli wrote:
> Jason Merrill<jason@redhat.com>  writes:
>
> Sure. I'll post a separate patch for it once we are done with this one.
>
>>> +  if (total_num_parms == 0)
>>> +    return NULL_TREE;
>>
>> Since you're already treating parms from a list of unknown length as
>> distinct from parms from a list of known length, we can give them a
>> canonical type, too.
>
> Doing that doesn't seem to work. The problem is not with the comparison
> of type template parms but rather with the comparison of dependent types
> created during the template parms parsing.
>
> If type template parms don't require structural comparison then a type A
> (created during template parms parsing) dependent on those parms will
> have a canonical type.

Yep.

> The fixup then creates a type A' that is
> structurally equivalent to A, but has a different canonical type.

It shouldn't be structurally equivalent, since A's template parms come 
from a list of non-0 length, which is not true of A'.

> * Template parm level reduction.
>
> When at least one of the parms is itself a template [like in
> testsuite/g++.old-deja/g++.pt/nttp1.C] then at some point we end up in
> tsubst (at least) with an argument set that has a depth that is less
> than the depth of the parm of the template template parm we are
> susbtituting into.

Rather, the problem comes when we don't have any argument at all; in 
that case we reduce the level.

> My understanding is that the tsubsting code then thinks that we are
> doing the substitution for the purpose of instantiation and then reduces
> the level of the resulting parms.

Partial instantiation, yes.

I would expect that when we get to this point we've already done the 
fixup for these parms, so that they don't need to be substituted 
directly; we only need to fixup the type of any non-type parms (and so 
on recursively for template template parms).  That ought to avoid this 
problem.

> Incidentally I noticed that the tf_no_class_instantiation is not used by
> any client code anymore. Would you accept a patchlet to remove it?

Yep.

> During unification of C<5>  with X<5>  the argument 5 of X is converted
> into the type of the parameter of C, i.e 5 is converted into typename
> metafun<T>::type. convert_template_argument then tries to substitute
> into typename metafun<T>::type. This should just create another
> equivalent typename becase metafun<T>  is dependent and thus non
> complete. But when tsubst calls make_typename_type, the later fails to
> detect that metafun<T>  is dependent [because processing_template_decl is
> 0] and goes crazy.

Why don't we have an argument for T by this point?

Jason

Patch

diff --git a/gcc/cp/class.c b/gcc/cp/class.c
index c594d6a..1537786 100644
--- a/gcc/cp/class.c
+++ b/gcc/cp/class.c
@@ -6673,7 +6673,7 @@  build_self_reference (void)
   DECL_CONTEXT (value) = current_class_type;
   DECL_ARTIFICIAL (value) = 1;
   SET_DECL_SELF_REFERENCE_P (value);
-  cp_set_underlying_type (value);
+  set_underlying_type (value);
 
   if (processing_template_decl)
     value = push_template_decl (value);
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index c78beb7..cf936d2 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -3954,6 +3954,8 @@  enum tsubst_flags {
 				    when issuing other errors.   */
   /* Do not instantiate classes (used by count_non_default_template_args). */
   tf_no_class_instantiations = 1 << 8,
+  tf_no_tpl_reduce = 1 << 9,    /* Do not reduce the level of
+				   template parameters.  */
   /* Convenient substitution flags combinations.  */
   tf_warning_or_error = tf_warning | tf_error
 };
@@ -4321,10 +4323,13 @@  enum overload_flags { NO_SPECIAL = 0, DTOR_FLAG, TYPENAME_FLAG };
   (TEMPLATE_PARM_DECL (TEMPLATE_TYPE_PARM_INDEX (NODE)))
 #define TEMPLATE_TYPE_PARAMETER_PACK(NODE) \
   (TEMPLATE_PARM_PARAMETER_PACK (TEMPLATE_TYPE_PARM_INDEX (NODE)))
-/* The list of template parms that a given template parameter of type
-   TEMPLATE_TYPE_PARM belongs to.*/
-#define TEMPLATE_TYPE_PARM_SIBLING_PARMS(NODE) \
-  (TREE_CHECK ((NODE), TEMPLATE_TYPE_PARM))->type.maxval
+
+/* The length of the template parms list this template parm belongs
+   to. This is a an integer wrapped into a tree node.  */
+#define TEMPLATE_NUM_SIBLING_PARMS(NODE)			\
+  (TREE_CHECK3 ((NODE), TEMPLATE_TYPE_PARM,			\
+		TEMPLATE_TEMPLATE_PARM,				\
+		BOUND_TEMPLATE_TEMPLATE_PARM))->type.maxval
 
 /* These constants can used as bit flags in the process of tree formatting.
 
@@ -5005,7 +5010,7 @@  extern void append_type_to_template_for_access_check (tree, tree, tree,
 extern tree splice_late_return_type		(tree, tree);
 extern bool is_auto				(const_tree);
 extern tree process_template_parm		(tree, location_t, tree, 
-						 bool, bool);
+						 bool, bool, unsigned);
 extern tree end_template_parm_list		(tree);
 extern void end_template_decl			(void);
 extern tree maybe_update_decl_type		(tree, tree);
@@ -5341,7 +5346,6 @@  extern bool type_has_nontrivial_copy_init	(const_tree);
 extern bool class_tmpl_impl_spec_p		(const_tree);
 extern int zero_init_p				(const_tree);
 extern tree strip_typedefs			(tree);
-extern void cp_set_underlying_type		(tree);
 extern tree copy_binfo				(tree, tree, tree,
 						 tree *, int);
 extern int member_p				(const_tree);
diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c
index 3d1420a..e4d39a8 100644
--- a/gcc/cp/decl.c
+++ b/gcc/cp/decl.c
@@ -3099,7 +3099,7 @@  make_typename_type (tree context, tree name, enum tag_types tag_type,
   else
     t = NULL_TREE;
 
-  if ((!t || TREE_CODE (t) == TREE_LIST) && dependent_type_p (context))
+  if ((!t || TREE_CODE (t) == TREE_LIST) && uses_template_parms (context))
     return build_typename_type (context, name, fullname, tag_type);
 
   want_template = TREE_CODE (fullname) == TEMPLATE_ID_EXPR;
diff --git a/gcc/cp/decl2.c b/gcc/cp/decl2.c
index 63197705..1c6bbbe 100644
--- a/gcc/cp/decl2.c
+++ b/gcc/cp/decl2.c
@@ -879,7 +879,7 @@  grokfield (const cp_declarator *declarator,
       if (declspecs->specs[(int)ds_typedef]
           && TREE_TYPE (value) != error_mark_node
           && TYPE_NAME (TYPE_MAIN_VARIANT (TREE_TYPE (value))) != value)
-	cp_set_underlying_type (value);
+	set_underlying_type (value);
 
       return value;
     }
diff --git a/gcc/cp/name-lookup.c b/gcc/cp/name-lookup.c
index 41feb57..a044659 100644
--- a/gcc/cp/name-lookup.c
+++ b/gcc/cp/name-lookup.c
@@ -872,7 +872,7 @@  pushdecl_maybe_friend (tree x, bool is_friend)
 		     inlining.  */
 		  && (!TYPE_NAME (type)
 		      || TYPE_NAME (type) != DECL_ABSTRACT_ORIGIN (x))))
-	    cp_set_underlying_type (x);
+	    set_underlying_type (x);
 
 	  if (type != error_mark_node
 	      && TYPE_NAME (type)
diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c
index 9385344..b8c35b3 100644
--- a/gcc/cp/parser.c
+++ b/gcc/cp/parser.c
@@ -10997,6 +10997,15 @@  cp_parser_template_parameter_list (cp_parser* parser)
   tree parameter_list = NULL_TREE;
 
   begin_template_parm_list ();
+
+  /* The loop below parses the template parms. Note that dependent
+     types created during this parsing require structural comparison
+     rather than canonical type comparison. This is because we first
+     need to know the total number of template parms to be able to
+     compute canonical types of each dependent type. So after the
+     loop, when we know the total number of template parms,
+     end_template_parm_list computes the proper canonical types and
+     fixes up the dependent types accordingly.  */
   while (true)
     {
       tree parameter;
@@ -11015,11 +11024,11 @@  cp_parser_template_parameter_list (cp_parser* parser)
 						parm_loc,
 						parameter,
 						is_non_type,
-                                                is_parameter_pack);
+						is_parameter_pack,
+						0);
       else
        {
          tree err_parm = build_tree_list (parameter, parameter);
-         TREE_VALUE (err_parm) = error_mark_node;
          parameter_list = chainon (parameter_list, err_parm);
        }
 
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 5a90bdc..a4b13b1 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -93,10 +93,14 @@  static GTY ((param_is (spec_entry)))
 static GTY ((param_is (spec_entry)))
   htab_t type_specializations;
 
-/* Contains canonical template parameter types. The vector is indexed by
-   the TEMPLATE_TYPE_IDX of the template parameter. Each element is a
-   TREE_LIST, whose TREE_VALUEs contain the canonical template
-   parameters of various types and levels.  */
+/* Contains canonical template parameter types. The vector is indexed
+   by the TEMPLATE_TYPE_IDX of the template parameter. Each element is
+   a TREE_LIST, whose TREE_PURPOSE is a INT_CST tree representing a
+   total size of the template parameter list a given template
+   parameter would belong too, and whose TREE_VALUEs contain the
+   canonical template parameters of various types and levels,
+   belonging to a set of template parameters which size is
+   TREE_PURPOSE.  */
 static GTY(()) VEC(tree,gc) *canonical_template_parms;
 
 #define UNIFY_ALLOW_NONE 0
@@ -190,6 +194,9 @@  static void append_type_to_template_for_access_check_1 (tree, tree, tree,
 static hashval_t iterative_hash_template_arg (tree arg, hashval_t val);
 static tree listify (tree);
 static tree listify_autos (tree, tree);
+static tree current_template_args (void);
+static void fixup_template_parms_canonical_types (void);
+static tree tsubst_template_parm (tree, tree, tsubst_flags_t);
 
 /* Make the current scope suitable for access checking when we are
    processing T.  T can be FUNCTION_DECL for instantiated function
@@ -3369,12 +3376,25 @@  build_template_parm_index (int index,
 
 /* Find the canonical type parameter for the given template type
    parameter.  Returns the canonical type parameter, which may be TYPE
-   if no such parameter existed.  */
+   if no such parameter existed. TOTAL_NUM_PARMS is the number of
+   template parameters carried by the considered template.
+
+   If TYPE is the template parameter at position P in a
+   template, this function won't return the same canonical type as for
+   a another TYPE that would be a template parameter at position Q,
+   with Q != P.
+
+   If TOTAL_NUM_PARMS is 0, the function returns NULL_TREE.  */
+
 static tree
-canonical_type_parameter (tree type)
+canonical_type_parameter (tree type, unsigned total_num_parms)
 {
   tree list;
   int idx = TEMPLATE_TYPE_IDX (type);
+
+  if (total_num_parms == 0)
+    return NULL_TREE;
+
   if (!canonical_template_parms)
     canonical_template_parms = VEC_alloc (tree, gc, idx+1);
 
@@ -3382,15 +3402,20 @@  canonical_type_parameter (tree type)
     VEC_safe_push (tree, gc, canonical_template_parms, NULL_TREE);
 
   list = VEC_index (tree, canonical_template_parms, idx);
-  while (list && !comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
-    list = TREE_CHAIN (list);
+  while (list)
+    {
+      if (TREE_INT_CST_LOW (TREE_PURPOSE (list)) == total_num_parms
+	  && comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
+	break;
+      list = TREE_CHAIN (list);
+    }
 
   if (list)
     return TREE_VALUE (list);
   else
     {
       VEC_replace(tree, canonical_template_parms, idx,
-		  tree_cons (NULL_TREE, type, 
+		  tree_cons (size_int (total_num_parms), type, 
 			     VEC_index (tree, canonical_template_parms, idx)));
       return type;
     }
@@ -3438,15 +3463,21 @@  reduce_template_parm_level (tree index, tree type, int levels, tree args,
   return TEMPLATE_PARM_DESCENDANTS (index);
 }
 
-/* Process information from new template parameter PARM and append it to the
-   LIST being built.  This new parameter is a non-type parameter iff
-   IS_NON_TYPE is true. This new parameter is a parameter
-   pack iff IS_PARAMETER_PACK is true.  The location of PARM is in 
-   PARM_LOC.  */
+/* Process information from new template parameter PARM and append it
+   to the LIST being built.  This new parameter is a non-type
+   parameter iff IS_NON_TYPE is true. This new parameter is a
+   parameter pack iff IS_PARAMETER_PACK is true.  The location of PARM
+   is in PARM_LOC. NUM_TEMPLATE_PARMS is the size of the template
+   parameter list PARM belongs to. This is used used to create a
+   proper canonical type for the type of PARM that is to be created,
+   iff PARM is a type.  If the size is not known, this parameter can
+   be set to 0. Setting it to zero would create a template type
+   parameter with no canonical type.  */
 
 tree
-process_template_parm (tree list, location_t parm_loc, tree parm, bool is_non_type, 
-                       bool is_parameter_pack)
+process_template_parm (tree list, location_t parm_loc, tree parm,
+		       bool is_non_type, bool is_parameter_pack,
+		       unsigned num_template_parms)
 {
   tree decl = 0;
   tree defval;
@@ -3556,8 +3587,9 @@  process_template_parm (tree list, location_t parm_loc, tree parm, bool is_non_ty
 				     processing_template_decl,
 				     decl, TREE_TYPE (parm));
       TEMPLATE_TYPE_PARAMETER_PACK (t) = is_parameter_pack;
-      TYPE_CANONICAL (t) = canonical_type_parameter (t);
-    }
+      TYPE_CANONICAL (t) =
+	canonical_type_parameter (t, num_template_parms);
+   }
   DECL_ARTIFICIAL (decl) = 1;
   SET_DECL_TEMPLATE_PARM_P (decl);
   pushdecl (decl);
@@ -3573,9 +3605,9 @@  process_template_parm (tree list, location_t parm_loc, tree parm, bool is_non_ty
 tree
 end_template_parm_list (tree parms)
 {
-  int nparms;
+  int nparms, length = list_length (parms);
   tree parm, next;
-  tree saved_parmlist = make_tree_vec (list_length (parms));
+  tree saved_parmlist = make_tree_vec (length);
 
   current_template_parms
     = tree_cons (size_int (processing_template_decl),
@@ -3586,16 +3618,141 @@  end_template_parm_list (tree parms)
       next = TREE_CHAIN (parm);
       TREE_VEC_ELT (saved_parmlist, nparms) = parm;
       TREE_CHAIN (parm) = NULL_TREE;
-      if (TREE_CODE (TREE_VALUE (parm)) == TYPE_DECL)
-	TEMPLATE_TYPE_PARM_SIBLING_PARMS (TREE_TYPE (TREE_VALUE (parm))) =
-	      current_template_parms;
+      if (TREE_CODE (TREE_VALUE (parm)) == TYPE_DECL
+	  || TREE_CODE (TREE_VALUE (parm)) == TEMPLATE_DECL)
+	TEMPLATE_NUM_SIBLING_PARMS (TREE_TYPE (TREE_VALUE (parm))) =
+	  size_int (length);
     }
 
+  fixup_template_parms_canonical_types ();
+
   --processing_template_parmlist;
 
   return saved_parmlist;
 }
 
+/* Walk current the template parms and properly compute the canonical
+   types of the dependent types created during
+   cp_parser_template_parameter_list.  */
+
+static void
+fixup_template_parms_canonical_types (void)
+{
+  tree parm;
+  tree full_template_args;
+  tree parameter_vec;
+  int i, num_parms;
+
+  parameter_vec = INNERMOST_TEMPLATE_PARMS (current_template_parms);
+  if (parameter_vec == NULL_TREE)
+    return;
+
+  num_parms = TREE_VEC_LENGTH (parameter_vec);
+
+  /* In this first loop, let's update the canonical type of each
+     type template parameter.  */
+  for (i = 0; i < num_parms; ++i)
+    {
+      tree main_type, variant;
+
+      parm = TREE_VALUE (TREE_VEC_ELT (parameter_vec, i));
+      if (TREE_CODE (parm) == TYPE_DECL
+	  || TREE_CODE (parm) == TEMPLATE_DECL)
+	{
+	  if (TREE_CODE (parm) == TEMPLATE_DECL)
+	    {
+	      tree arglist = current_template_args ();
+	      tree tparms;
+	      int j;
+
+	      /* So PARM is a template tempate parameter, e.g, like TT
+		 in:
+
+		   template<class T, template<T> class TT> class S;
+		   
+		 In this case we want to substitute T into the
+		 template parameters of TT.
+
+		 Sot let's walk the template parms of PARM here, and
+		 tsubst ARGLIST into into each of the template
+		 parms.   */
+	      tparms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (parm));
+	      for (j = 0; j < TREE_VEC_LENGTH (tparms); ++j)
+		{
+		  tree substed_parm;
+		  ++cp_unevaluated_operand;
+		  /* Note the use of tf_no_tpl_reduce as the last
+		     argument to tsubst_template_parm here. Suppose
+		     the current template parameter of PARM is itself
+		     a template. In that case, we do not want
+		     tsubst_template_parm to reduce the level of the
+		     parameters of that later template , as tsubst or
+		     tsubst_template_parms would normally do [because
+		     we are not tsubsting here for the purpose of
+		     instantiating a type, rather, we just want to
+		     substitute template parameters "in
+		     place"]. Therefore, we use tf_no_tpl_reduce to
+		     really avoid that template parm level
+		     reduction.  */
+		  substed_parm = tsubst_template_parm (TREE_VEC_ELT (tparms, j),
+						       arglist, 
+						       tf_no_tpl_reduce);
+		  --cp_unevaluated_operand;
+		  TREE_VEC_ELT (tparms, j) = substed_parm;
+		}
+	    }
+
+	  /* Compute the canonical type of type template
+	     parameters and their variants.  */
+	  main_type = TYPE_MAIN_VARIANT (TREE_TYPE (parm));
+	  TYPE_CANONICAL (main_type) =
+	    canonical_type_parameter (main_type, num_parms);
+	  for (variant = TYPE_NEXT_VARIANT (main_type);
+	       variant;
+	       variant = TYPE_NEXT_VARIANT (variant))
+	    TYPE_CANONICAL (variant) =
+	      canonical_type_parameter (variant, num_parms);
+	}
+    }
+
+  /* And now let's substitute the template type parameters into
+     dependent non-type template arguments and default template
+     arguments.  */
+  full_template_args = current_template_args ();
+  for (i = 0; i < num_parms; ++i)
+    {
+      tree cur = TREE_VEC_ELT (parameter_vec, i);
+
+      if ((TREE_CODE (parm) == TYPE_DECL
+	   || TREE_CODE (parm) == TEMPLATE_DECL)
+	  && TREE_PURPOSE (cur))
+	{
+	  tree default_arg = TREE_PURPOSE (cur);
+
+	  if (TYPE_P (default_arg)
+	      && !dependent_type_p (default_arg))
+	    continue;
+
+	  ++cp_unevaluated_operand;
+	  TREE_PURPOSE (cur) =
+	    tsubst_expr (default_arg, full_template_args,
+			 tf_none, default_arg, false);
+	  --cp_unevaluated_operand;
+	}
+
+      if (TREE_CODE (TREE_VALUE (cur)) == PARM_DECL)
+	{
+	  tree non_type_parm = TREE_VALUE (cur);
+	  ++cp_unevaluated_operand;
+	  TREE_VALUE (cur) =
+	    tsubst_decl (non_type_parm,
+			 full_template_args,
+			 tf_none);
+	  --cp_unevaluated_operand;
+	}
+    }
+}
+
 /* end_template_decl is called after a template declaration is seen.  */
 
 void
@@ -3706,7 +3863,23 @@  current_template_args (void)
       else
 	args = a;
     }
-
+  
+    if (length > 1 && TREE_VEC_ELT (args, 0) == NULL_TREE)
+      /* This can happen for template parms of a template template
+	 parameter, e.g:
+
+	 template<template<class T, class U> class TT> struct S;
+
+	 Consider the level of the parms of TT; T and U both have
+	 level 2; TT has no template parm of level 1. So in this case
+	 the first element of full_template_args is NULL_TREE. If we
+	 leave it like this TMPL_ARG_DEPTH on args returns 1 instead
+	 of 2. This will make tsubst wrongly consider that T and U
+	 have level 1. Instead, let's create a dummy vector as the
+	 first element of full_template_args so that TMPL_ARG_DEPTH
+	 returns the correct depth for args.
+      */
+      TREE_VEC_ELT (args, 0) = make_tree_vec (1);
   return args;
 }
 
@@ -6681,16 +6854,22 @@  lookup_template_class (tree d1,
 	  if (context == current_function_decl)
 	    pushtag (DECL_NAME (gen_tmpl), t, /*tag_scope=*/ts_current);
 
-	  if (comp_template_args (CLASSTYPE_TI_ARGS (template_type), arglist))
+	  if (any_template_arguments_need_structural_equality_p (arglist))
+	    /* Some of the template arguments require structural
+	       equality testing, so this template class requires
+	       structural equality testing. Note that we check this
+	       condition first because for dependent types that are
+	       created /during/ the parsing of template parameter lists,
+	       we must not require canonical type equality because
+	       canonical types of dependent types are actually going
+	       to be properly computed right at /the end/ of the
+	       template parms parsing.  */
+	    SET_TYPE_STRUCTURAL_EQUALITY (t);
+	  else if (comp_template_args (CLASSTYPE_TI_ARGS (template_type), arglist))
 	    /* This instantiation is another name for the primary
 	       template type. Set the TYPE_CANONICAL field
 	       appropriately. */
 	    TYPE_CANONICAL (t) = template_type;
-	  else if (any_template_arguments_need_structural_equality_p (arglist))
-	    /* Some of the template arguments require structural
-	       equality testing, so this template class requires
-	       structural equality testing. */
-	    SET_TYPE_STRUCTURAL_EQUALITY (t);
 	}
 
       /* If we called start_enum or pushtag above, this information
@@ -8722,6 +8901,7 @@  tsubst_template_parms (tree parms, tree args, tsubst_flags_t complain)
 {
   tree r = NULL_TREE;
   tree* new_parms;
+  bool reduce_level_p = !(complain & tf_no_tpl_reduce);
 
   /* When substituting into a template, we must set
      PROCESSING_TEMPLATE_DECL as the template parameters may be
@@ -8730,19 +8910,18 @@  tsubst_template_parms (tree parms, tree args, tsubst_flags_t complain)
   ++processing_template_decl;
 
   for (new_parms = &r;
-       TMPL_PARMS_DEPTH (parms) > TMPL_ARGS_DEPTH (args);
+       ((reduce_level_p && TMPL_PARMS_DEPTH (parms) > TMPL_ARGS_DEPTH (args))
+	||(!reduce_level_p && parms));
        new_parms = &(TREE_CHAIN (*new_parms)),
 	 parms = TREE_CHAIN (parms))
     {
       tree new_vec =
 	make_tree_vec (TREE_VEC_LENGTH (TREE_VALUE (parms)));
-      int i;
+      int i, new_level;
 
       for (i = 0; i < TREE_VEC_LENGTH (new_vec); ++i)
 	{
           tree tuple;
-          tree default_value;
-          tree parm_decl;
 
           if (parms == error_mark_node)
             continue;
@@ -8752,23 +8931,16 @@  tsubst_template_parms (tree parms, tree args, tsubst_flags_t complain)
           if (tuple == error_mark_node)
             continue;
 
-          default_value = TREE_PURPOSE (tuple);
-          parm_decl = TREE_VALUE (tuple);
-
-	  parm_decl = tsubst (parm_decl, args, complain, NULL_TREE);
-	  if (TREE_CODE (parm_decl) == PARM_DECL
-	      && invalid_nontype_parm_type_p (TREE_TYPE (parm_decl), complain))
-	    parm_decl = error_mark_node;
-	  default_value = tsubst_template_arg (default_value, args,
-					       complain, NULL_TREE);
-
-	  tuple = build_tree_list (default_value, parm_decl);
-	  TREE_VEC_ELT (new_vec, i) = tuple;
+	  TREE_VEC_ELT (new_vec, i) =
+	    tsubst_template_parm (tuple, args, complain);
 	}
 
+      new_level = reduce_level_p
+	? TMPL_PARMS_DEPTH (parms) - TMPL_ARGS_DEPTH (args)
+	: TMPL_PARMS_DEPTH (parms);
+
       *new_parms =
-	tree_cons (size_int (TMPL_PARMS_DEPTH (parms)
-			     - TMPL_ARGS_DEPTH (args)),
+	tree_cons (size_int (new_level),
 		   new_vec, NULL_TREE);
     }
 
@@ -8777,6 +8949,36 @@  tsubst_template_parms (tree parms, tree args, tsubst_flags_t complain)
   return r;
 }
 
+/* Return the result of substituting ARGS into one template parameter
+   given by T. T Must be a TREE_LIST which TREE_VALUE is the template
+   parameter and which TREE_PURPOSE is the default argument of the
+   template parameter.  */
+
+static tree
+tsubst_template_parm (tree t, tree args, tsubst_flags_t complain)
+{
+  tree default_value, parm_decl;
+
+  if (args == NULL_TREE
+      || t == NULL_TREE
+      || t == error_mark_node)
+    return t;
+
+  gcc_assert (TREE_CODE (t) == TREE_LIST);
+
+  default_value = TREE_PURPOSE (t);
+  parm_decl = TREE_VALUE (t);
+
+  parm_decl = tsubst (parm_decl, args, complain, NULL_TREE);
+  if (TREE_CODE (parm_decl) == PARM_DECL
+      && invalid_nontype_parm_type_p (TREE_TYPE (parm_decl), complain))
+    parm_decl = error_mark_node;
+  default_value = tsubst_template_arg (default_value, args,
+				       complain, NULL_TREE);
+
+  return build_tree_list (default_value, parm_decl);
+}
+
 /* Substitute the ARGS into the indicated aggregate (or enumeration)
    type T.  If T is not an aggregate or enumeration type, it is
    handled as if by tsubst.  IN_DECL is as for tsubst.  If
@@ -10271,9 +10473,10 @@  tsubst (tree t, tree args, tsubst_flags_t complain, tree in_decl)
 	    else
 	      {
 		r = copy_type (t);
-		TEMPLATE_TYPE_PARM_INDEX (r)
-		  = reduce_template_parm_level (TEMPLATE_TYPE_PARM_INDEX (t),
-						r, levels, args, complain);
+		if (!(complain & tf_no_tpl_reduce))
+		  TEMPLATE_TYPE_PARM_INDEX (r)
+		    = reduce_template_parm_level (TEMPLATE_TYPE_PARM_INDEX (t),
+						  r, levels, args, complain);
 		TYPE_STUB_DECL (r) = TYPE_NAME (r) = TEMPLATE_TYPE_DECL (r);
 		TYPE_MAIN_VARIANT (r) = r;
 		TYPE_POINTER_TO (r) = NULL_TREE;
@@ -10291,7 +10494,14 @@  tsubst (tree t, tree args, tsubst_flags_t complain, tree in_decl)
 		else if (TYPE_STRUCTURAL_EQUALITY_P (t))
 		  SET_TYPE_STRUCTURAL_EQUALITY (r);
 		else
-		  TYPE_CANONICAL (r) = canonical_type_parameter (r);
+		  {
+		    unsigned num_parms =
+		      (TEMPLATE_NUM_SIBLING_PARMS (t))
+		      ? TREE_INT_CST_LOW (TEMPLATE_NUM_SIBLING_PARMS (t))
+		      : 0;
+		    TYPE_CANONICAL (r) =
+		      canonical_type_parameter (r, num_parms);
+		  }
 
 		if (code == BOUND_TEMPLATE_TEMPLATE_PARM)
 		  {
@@ -10307,7 +10517,10 @@  tsubst (tree t, tree args, tsubst_flags_t complain, tree in_decl)
 	    break;
 
 	  case TEMPLATE_PARM_INDEX:
-	    r = reduce_template_parm_level (t, type, levels, args, complain);
+	    if (complain & tf_no_tpl_reduce)
+	      r = t;
+	    else
+	      r = reduce_template_parm_level (t, type, levels, args, complain);
 	    break;
 
 	  default:
@@ -17786,7 +17999,8 @@  type_dependent_expression_p (tree expression)
   if (!processing_template_decl)
     return false;
 
-  if (expression == error_mark_node)
+  if (expression == error_mark_node
+      || expression == NULL_TREE)
     return false;
 
   /* An unresolved name is always dependent.  */
@@ -18406,7 +18620,7 @@  make_auto (void)
   TEMPLATE_TYPE_PARM_INDEX (au) = build_template_parm_index
     (0, processing_template_decl + 1, processing_template_decl + 1,
      TYPE_NAME (au), NULL_TREE);
-  TYPE_CANONICAL (au) = canonical_type_parameter (au);
+  TYPE_CANONICAL (au) = canonical_type_parameter (au, 0);
   DECL_ARTIFICIAL (TYPE_NAME (au)) = 1;
   SET_DECL_TEMPLATE_PARM_P (TYPE_NAME (au));
 
diff --git a/gcc/cp/tree.c b/gcc/cp/tree.c
index ea01d1f..580ebf3 100644
--- a/gcc/cp/tree.c
+++ b/gcc/cp/tree.c
@@ -1063,22 +1063,6 @@  strip_typedefs (tree t)
   return cp_build_qualified_type (result, cp_type_quals (t));
 }
 
-/* Setup a TYPE_DECL node as a typedef representation.
-   See comments of set_underlying_type in c-common.c.  */
-
-void
-cp_set_underlying_type (tree t)
-{
-  set_underlying_type (t);
-  /* If T is a template type parm, make it require structural equality.
-     This is useful when comparing two template type parms,
-     because it forces the comparison of the template parameters of their
-     decls.  */
-  if (TREE_CODE (TREE_TYPE (t)) == TEMPLATE_TYPE_PARM)
-    SET_TYPE_STRUCTURAL_EQUALITY (TREE_TYPE (t));
-}
-
-
 /* Makes a copy of BINFO and TYPE, which is to be inherited into a
    graph dominated by T.  If BINFO is NULL, TYPE is a dependent base,
    and we do a shallow copy.  If BINFO is non-NULL, we do a deep copy.
diff --git a/gcc/cp/typeck.c b/gcc/cp/typeck.c
index 0ac95d0..41aaca7 100644
--- a/gcc/cp/typeck.c
+++ b/gcc/cp/typeck.c
@@ -1143,114 +1143,20 @@  comp_template_parms_position (tree t1, tree t2)
 		  || TREE_CODE (t1) == TEMPLATE_TEMPLATE_PARM
 		  || TREE_CODE (t1) == TEMPLATE_TYPE_PARM));
 
-      if (TEMPLATE_TYPE_IDX (t1) != TEMPLATE_TYPE_IDX (t2)
-	  || TEMPLATE_TYPE_LEVEL (t1) != TEMPLATE_TYPE_LEVEL (t2)
-          || (TEMPLATE_TYPE_PARAMETER_PACK (t1) 
-              != TEMPLATE_TYPE_PARAMETER_PACK (t2)))
-	return false;
-
-      return true;
-}
-
-/* Subroutine of incompatible_dependent_types_p.
-   Return the template parameter of the dependent type T.
-   If T is a typedef, return the template parameters of
-   the _decl_ of the typedef. T must be a dependent type.  */
-
-static tree
-get_template_parms_of_dependent_type (tree t)
-{
-  tree tinfo = NULL_TREE, tparms = NULL_TREE;
-
-  /* First, try the obvious case of getting the
-     template info from T itself.  */
-  if ((tinfo = get_template_info (t)))
-    ;
-  else if (TREE_CODE (t) == TEMPLATE_TYPE_PARM)
-    return TEMPLATE_TYPE_PARM_SIBLING_PARMS (t);
-  else if (typedef_variant_p (t)
-	   && !NAMESPACE_SCOPE_P (TYPE_NAME (t)))
-    tinfo = get_template_info (DECL_CONTEXT (TYPE_NAME (t)));
-  /* If T is a TYPENAME_TYPE which context is a template type
-     parameter, get the template parameters from that context.  */
-  else if (TYPE_CONTEXT (t)
-	   && TREE_CODE (TYPE_CONTEXT (t)) == TEMPLATE_TYPE_PARM)
-   return TEMPLATE_TYPE_PARM_SIBLING_PARMS (TYPE_CONTEXT (t));
-  else if (TYPE_CONTEXT (t)
-	   && !NAMESPACE_SCOPE_P (t))
-    tinfo = get_template_info (TYPE_CONTEXT (t));
-
-  if (tinfo)
-    tparms = DECL_TEMPLATE_PARMS (TI_TEMPLATE (tinfo));
-
-  return tparms;
-}
-
-/* Subroutine of structural_comptypes.
-   Compare the dependent types T1 and T2.
-   Return TRUE if we are sure they can't be equal, FALSE otherwise.
-   The whole point of this function is to support cases where either T1 or
-   T2 is a typedef. In those cases, we need to compare the template parameters
-   of the _decl_ of the typedef. If those don't match then we know T1
-   and T2 cannot be equal.  */
-
-static bool
-incompatible_dependent_types_p (tree t1, tree t2)
-{
-  tree tparms1 = NULL_TREE, tparms2 = NULL_TREE;
-  bool t1_typedef_variant_p, t2_typedef_variant_p;
-
-  if (!uses_template_parms (t1) || !uses_template_parms (t2))
-    return false;
-
-  if (TREE_CODE (t1) == TEMPLATE_TYPE_PARM)
-    {
-      /* If T1 and T2 don't have the same relative position in their
-	 template parameters set, they can't be equal.  */
-      if (!comp_template_parms_position (t1, t2))
-	return true;
-    }
-
-  t1_typedef_variant_p = typedef_variant_p (t1);
-  t2_typedef_variant_p = typedef_variant_p (t2);
-
-  /* Either T1 or T2 must be a typedef.  */
-  if (!t1_typedef_variant_p && !t2_typedef_variant_p)
+  /* If T1 and T2 belong to template parm lists of different size,
+     let's assume they are different.  */
+  if (TEMPLATE_NUM_SIBLING_PARMS (TYPE_MAIN_VARIANT (t1))
+      != TEMPLATE_NUM_SIBLING_PARMS (TYPE_MAIN_VARIANT (t2)))
     return false;
 
-  if (!t1_typedef_variant_p || !t2_typedef_variant_p)
-    /* Either T1 or T2 is not a typedef so we cannot compare the
-       template parms of the typedefs of T1 and T2.
-       At this point, if the main variant type of T1 and T2 are equal
-       it means the two types can't be incompatible, from the perspective
-       of this function.  */
-    if (TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
-      return false;
-
-  /* So if we reach this point, it means either T1 or T2 is a typedef variant.
-     Let's compare their template parameters.  */
-
-  tparms1 = get_template_parms_of_dependent_type (t1);
-  tparms2 = get_template_parms_of_dependent_type (t2);
-
-  /* If T2 is a template type parm and if we could not get the template
-     parms it belongs to, that means we have not finished parsing the
-     full set of template parameters of the template declaration it
-     belongs to yet. If we could get the template parms T1 belongs to,
-     that mostly means T1 and T2 belongs to templates that are
-     different and incompatible.  */
-  if (TREE_CODE (t1) == TEMPLATE_TYPE_PARM
-      && (tparms1 == NULL_TREE || tparms2 == NULL_TREE)
-      && tparms1 != tparms2)
-    return true;
-
-  if (tparms1 == NULL_TREE
-      || tparms2 == NULL_TREE
-      || tparms1 == tparms2)
+  /* Then compare their relative position.  */
+  if (TEMPLATE_TYPE_IDX (t1) != TEMPLATE_TYPE_IDX (t2)
+      || TEMPLATE_TYPE_LEVEL (t1) != TEMPLATE_TYPE_LEVEL (t2)
+      || (TEMPLATE_TYPE_PARAMETER_PACK (t1) 
+	  != TEMPLATE_TYPE_PARAMETER_PACK (t2)))
     return false;
 
-  /* And now compare the mighty template parms!  */
-  return !comp_template_parms (tparms1, tparms2);
+  return true;
 }
 
 /* Subroutine in comptypes.  */
@@ -1295,12 +1201,6 @@  structural_comptypes (tree t1, tree t2, int strict)
   if (TYPE_FOR_JAVA (t1) != TYPE_FOR_JAVA (t2))
     return false;
 
-  /* If T1 and T2 are dependent typedefs then check upfront that
-     the template parameters of their typedef DECLs match before
-     going down checking their subtypes.  */
-  if (incompatible_dependent_types_p (t1, t2))
-    return false;
-
   /* Allow for two different type nodes which have essentially the same
      definition.  Note that we already checked for equality of the type
      qualifiers (just above).  */
@@ -1345,6 +1245,7 @@  structural_comptypes (tree t1, tree t2, int strict)
 	  (DECL_TEMPLATE_PARMS (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t1)),
 	   DECL_TEMPLATE_PARMS (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t2))))
 	return false;
+
       if (TREE_CODE (t1) == TEMPLATE_TEMPLATE_PARM)
 	break;
       /* Don't check inheritance.  */
@@ -1401,8 +1302,10 @@  structural_comptypes (tree t1, tree t2, int strict)
       break;
 
     case TEMPLATE_TYPE_PARM:
-      /* If incompatible_dependent_types_p called earlier didn't decide
-         T1 and T2 were different, they might be equal.  */
+      /* If T1 and T2 don't have the same relative position in their
+	 template parameters set, they can't be equal.  */
+      if (!comp_template_parms_position (t1, t2))
+	return false;
       break;
 
     case TYPENAME_TYPE:
diff --git a/gcc/testsuite/g++.dg/template/typedef36.C b/gcc/testsuite/g++.dg/template/typedef36.C
new file mode 100644
index 0000000..f6155c1
--- /dev/null
+++ b/gcc/testsuite/g++.dg/template/typedef36.C
@@ -0,0 +1,23 @@ 
+// Origin: PR c++/45606
+// { dg-do compile }
+
+#include <list>
+
+template<class T>
+class Test
+{
+protected:
+  typedef std::list<T> ListAlias;
+  ListAlias list;
+public:
+  typedef typename ListAlias::const_iterator const_iterator;
+  inline const_iterator begin() const;
+
+};
+
+template<class T>
+inline typename std::list<T>::const_iterator Test<T>::begin() const
+{
+  return list.begin();
+}
+