OSDN Git Service

/cp
[pf3gnuchains/gcc-fork.git] / gcc / cp / pt.c
1 /* Handle parameterized types (templates) for GNU C++.
2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3    2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
4    Free Software Foundation, Inc.
5    Written by Ken Raeburn (raeburn@cygnus.com) while at Watchmaker Computing.
6    Rewritten by Jason Merrill (jason@cygnus.com).
7
8 This file is part of GCC.
9
10 GCC is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 3, or (at your option)
13 any later version.
14
15 GCC is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18 GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3.  If not see
22 <http://www.gnu.org/licenses/>.  */
23
24 /* Known bugs or deficiencies include:
25
26      all methods must be provided in header files; can't use a source
27      file that contains only the method templates and "just win".  */
28
29 #include "config.h"
30 #include "system.h"
31 #include "coretypes.h"
32 #include "tm.h"
33 #include "obstack.h"
34 #include "tree.h"
35 #include "intl.h"
36 #include "pointer-set.h"
37 #include "flags.h"
38 #include "c-common.h"
39 #include "cp-tree.h"
40 #include "cp-objcp-common.h"
41 #include "tree-inline.h"
42 #include "decl.h"
43 #include "output.h"
44 #include "except.h"
45 #include "toplev.h"
46 #include "rtl.h"
47 #include "timevar.h"
48 #include "tree-iterator.h"
49 #include "vecprim.h"
50
51 /* The type of functions taking a tree, and some additional data, and
52    returning an int.  */
53 typedef int (*tree_fn_t) (tree, void*);
54
55 /* The PENDING_TEMPLATES is a TREE_LIST of templates whose
56    instantiations have been deferred, either because their definitions
57    were not yet available, or because we were putting off doing the work.  */
58 struct GTY (()) pending_template {
59   struct pending_template *next;
60   struct tinst_level *tinst;
61 };
62
63 static GTY(()) struct pending_template *pending_templates;
64 static GTY(()) struct pending_template *last_pending_template;
65
66 int processing_template_parmlist;
67 static int template_header_count;
68
69 static GTY(()) tree saved_trees;
70 static VEC(int,heap) *inline_parm_levels;
71
72 static GTY(()) struct tinst_level *current_tinst_level;
73
74 static GTY(()) tree saved_access_scope;
75
76 /* Live only within one (recursive) call to tsubst_expr.  We use
77    this to pass the statement expression node from the STMT_EXPR
78    to the EXPR_STMT that is its result.  */
79 static tree cur_stmt_expr;
80
81 /* A map from local variable declarations in the body of the template
82    presently being instantiated to the corresponding instantiated
83    local variables.  */
84 static htab_t local_specializations;
85
86 typedef struct GTY(()) spec_entry
87 {
88   tree tmpl;
89   tree args;
90   tree spec;
91 } spec_entry;
92
93 static GTY ((param_is (spec_entry)))
94   htab_t decl_specializations;
95
96 static GTY ((param_is (spec_entry)))
97   htab_t type_specializations;
98
99 /* Contains canonical template parameter types. The vector is indexed by
100    the TEMPLATE_TYPE_IDX of the template parameter. Each element is a
101    TREE_LIST, whose TREE_VALUEs contain the canonical template
102    parameters of various types and levels.  */
103 static GTY(()) VEC(tree,gc) *canonical_template_parms;
104
105 #define UNIFY_ALLOW_NONE 0
106 #define UNIFY_ALLOW_MORE_CV_QUAL 1
107 #define UNIFY_ALLOW_LESS_CV_QUAL 2
108 #define UNIFY_ALLOW_DERIVED 4
109 #define UNIFY_ALLOW_INTEGER 8
110 #define UNIFY_ALLOW_OUTER_LEVEL 16
111 #define UNIFY_ALLOW_OUTER_MORE_CV_QUAL 32
112 #define UNIFY_ALLOW_OUTER_LESS_CV_QUAL 64
113
114 static void push_access_scope (tree);
115 static void pop_access_scope (tree);
116 static bool resolve_overloaded_unification (tree, tree, tree, tree,
117                                             unification_kind_t, int);
118 static int try_one_overload (tree, tree, tree, tree, tree,
119                              unification_kind_t, int, bool);
120 static int unify (tree, tree, tree, tree, int);
121 static void add_pending_template (tree);
122 static tree reopen_tinst_level (struct tinst_level *);
123 static tree tsubst_initializer_list (tree, tree);
124 static tree get_class_bindings (tree, tree, tree);
125 static tree coerce_template_parms (tree, tree, tree, tsubst_flags_t,
126                                    bool, bool);
127 static void tsubst_enum (tree, tree, tree);
128 static tree add_to_template_args (tree, tree);
129 static tree add_outermost_template_args (tree, tree);
130 static bool check_instantiated_args (tree, tree, tsubst_flags_t);
131 static int maybe_adjust_types_for_deduction (unification_kind_t, tree*, tree*,
132                                              tree);
133 static int type_unification_real (tree, tree, tree, const tree *,
134                                   unsigned int, int, unification_kind_t, int);
135 static void note_template_header (int);
136 static tree convert_nontype_argument_function (tree, tree);
137 static tree convert_nontype_argument (tree, tree);
138 static tree convert_template_argument (tree, tree, tree,
139                                        tsubst_flags_t, int, tree);
140 static int for_each_template_parm (tree, tree_fn_t, void*,
141                                    struct pointer_set_t*, bool);
142 static tree expand_template_argument_pack (tree);
143 static tree build_template_parm_index (int, int, int, tree, tree);
144 static bool inline_needs_template_parms (tree);
145 static void push_inline_template_parms_recursive (tree, int);
146 static tree retrieve_local_specialization (tree);
147 static void register_local_specialization (tree, tree);
148 static hashval_t hash_specialization (const void *p);
149 static tree reduce_template_parm_level (tree, tree, int, tree, tsubst_flags_t);
150 static int mark_template_parm (tree, void *);
151 static int template_parm_this_level_p (tree, void *);
152 static tree tsubst_friend_function (tree, tree);
153 static tree tsubst_friend_class (tree, tree);
154 static int can_complete_type_without_circularity (tree);
155 static tree get_bindings (tree, tree, tree, bool);
156 static int template_decl_level (tree);
157 static int check_cv_quals_for_unify (int, tree, tree);
158 static void template_parm_level_and_index (tree, int*, int*);
159 static int unify_pack_expansion (tree, tree, tree, tree, int, bool, bool);
160 static tree tsubst_template_arg (tree, tree, tsubst_flags_t, tree);
161 static tree tsubst_template_args (tree, tree, tsubst_flags_t, tree);
162 static tree tsubst_template_parms (tree, tree, tsubst_flags_t);
163 static void regenerate_decl_from_template (tree, tree);
164 static tree most_specialized_class (tree, tree);
165 static tree tsubst_aggr_type (tree, tree, tsubst_flags_t, tree, int);
166 static tree tsubst_arg_types (tree, tree, tsubst_flags_t, tree);
167 static tree tsubst_function_type (tree, tree, tsubst_flags_t, tree);
168 static bool check_specialization_scope (void);
169 static tree process_partial_specialization (tree);
170 static void set_current_access_from_decl (tree);
171 static tree get_template_base (tree, tree, tree, tree);
172 static tree try_class_unification (tree, tree, tree, tree);
173 static int coerce_template_template_parms (tree, tree, tsubst_flags_t,
174                                            tree, tree);
175 static bool template_template_parm_bindings_ok_p (tree, tree);
176 static int template_args_equal (tree, tree);
177 static void tsubst_default_arguments (tree);
178 static tree for_each_template_parm_r (tree *, int *, void *);
179 static tree copy_default_args_to_explicit_spec_1 (tree, tree);
180 static void copy_default_args_to_explicit_spec (tree);
181 static int invalid_nontype_parm_type_p (tree, tsubst_flags_t);
182 static int eq_local_specializations (const void *, const void *);
183 static bool dependent_template_arg_p (tree);
184 static bool any_template_arguments_need_structural_equality_p (tree);
185 static bool dependent_type_p_r (tree);
186 static tree tsubst_expr (tree, tree, tsubst_flags_t, tree, bool);
187 static tree tsubst_copy (tree, tree, tsubst_flags_t, tree);
188 static tree tsubst_pack_expansion (tree, tree, tsubst_flags_t, tree);
189 static tree tsubst_decl (tree, tree, tsubst_flags_t);
190 static void perform_typedefs_access_check (tree tmpl, tree targs);
191 static void append_type_to_template_for_access_check_1 (tree, tree, tree,
192                                                         location_t);
193 static hashval_t iterative_hash_template_arg (tree arg, hashval_t val);
194 static tree listify (tree);
195 static tree listify_autos (tree, tree);
196
197 /* Make the current scope suitable for access checking when we are
198    processing T.  T can be FUNCTION_DECL for instantiated function
199    template, or VAR_DECL for static member variable (need by
200    instantiate_decl).  */
201
202 static void
203 push_access_scope (tree t)
204 {
205   gcc_assert (TREE_CODE (t) == FUNCTION_DECL
206               || TREE_CODE (t) == VAR_DECL);
207
208   if (DECL_FRIEND_CONTEXT (t))
209     push_nested_class (DECL_FRIEND_CONTEXT (t));
210   else if (DECL_CLASS_SCOPE_P (t))
211     push_nested_class (DECL_CONTEXT (t));
212   else
213     push_to_top_level ();
214
215   if (TREE_CODE (t) == FUNCTION_DECL)
216     {
217       saved_access_scope = tree_cons
218         (NULL_TREE, current_function_decl, saved_access_scope);
219       current_function_decl = t;
220     }
221 }
222
223 /* Restore the scope set up by push_access_scope.  T is the node we
224    are processing.  */
225
226 static void
227 pop_access_scope (tree t)
228 {
229   if (TREE_CODE (t) == FUNCTION_DECL)
230     {
231       current_function_decl = TREE_VALUE (saved_access_scope);
232       saved_access_scope = TREE_CHAIN (saved_access_scope);
233     }
234
235   if (DECL_FRIEND_CONTEXT (t) || DECL_CLASS_SCOPE_P (t))
236     pop_nested_class ();
237   else
238     pop_from_top_level ();
239 }
240
241 /* Do any processing required when DECL (a member template
242    declaration) is finished.  Returns the TEMPLATE_DECL corresponding
243    to DECL, unless it is a specialization, in which case the DECL
244    itself is returned.  */
245
246 tree
247 finish_member_template_decl (tree decl)
248 {
249   if (decl == error_mark_node)
250     return error_mark_node;
251
252   gcc_assert (DECL_P (decl));
253
254   if (TREE_CODE (decl) == TYPE_DECL)
255     {
256       tree type;
257
258       type = TREE_TYPE (decl);
259       if (type == error_mark_node)
260         return error_mark_node;
261       if (MAYBE_CLASS_TYPE_P (type)
262           && CLASSTYPE_TEMPLATE_INFO (type)
263           && !CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
264         {
265           tree tmpl = CLASSTYPE_TI_TEMPLATE (type);
266           check_member_template (tmpl);
267           return tmpl;
268         }
269       return NULL_TREE;
270     }
271   else if (TREE_CODE (decl) == FIELD_DECL)
272     error ("data member %qD cannot be a member template", decl);
273   else if (DECL_TEMPLATE_INFO (decl))
274     {
275       if (!DECL_TEMPLATE_SPECIALIZATION (decl))
276         {
277           check_member_template (DECL_TI_TEMPLATE (decl));
278           return DECL_TI_TEMPLATE (decl);
279         }
280       else
281         return decl;
282     }
283   else
284     error ("invalid member template declaration %qD", decl);
285
286   return error_mark_node;
287 }
288
289 /* Create a template info node.  */
290
291 tree
292 build_template_info (tree template_decl, tree template_args)
293 {
294   tree result = make_node (TEMPLATE_INFO);
295   TI_TEMPLATE (result) = template_decl;
296   TI_ARGS (result) = template_args;
297   return result;
298 }
299
300 /* Return the template info node corresponding to T, whatever T is.  */
301
302 tree
303 get_template_info (const_tree t)
304 {
305   tree tinfo = NULL_TREE;
306
307   if (!t || t == error_mark_node)
308     return NULL;
309
310   if (DECL_P (t) && DECL_LANG_SPECIFIC (t))
311     tinfo = DECL_TEMPLATE_INFO (t);
312
313   if (!tinfo && DECL_IMPLICIT_TYPEDEF_P (t))
314     t = TREE_TYPE (t);
315
316   if (TAGGED_TYPE_P (t))
317     tinfo = TYPE_TEMPLATE_INFO (t);
318   else if (TREE_CODE (t) == BOUND_TEMPLATE_TEMPLATE_PARM)
319     tinfo = TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t);
320
321   return tinfo;
322 }
323
324 /* Returns the template nesting level of the indicated class TYPE.
325
326    For example, in:
327      template <class T>
328      struct A
329      {
330        template <class U>
331        struct B {};
332      };
333
334    A<T>::B<U> has depth two, while A<T> has depth one.
335    Both A<T>::B<int> and A<int>::B<U> have depth one, if
336    they are instantiations, not specializations.
337
338    This function is guaranteed to return 0 if passed NULL_TREE so
339    that, for example, `template_class_depth (current_class_type)' is
340    always safe.  */
341
342 int
343 template_class_depth (tree type)
344 {
345   int depth;
346
347   for (depth = 0;
348        type && TREE_CODE (type) != NAMESPACE_DECL;
349        type = (TREE_CODE (type) == FUNCTION_DECL)
350          ? CP_DECL_CONTEXT (type) : TYPE_CONTEXT (type))
351     {
352       tree tinfo = get_template_info (type);
353
354       if (tinfo && PRIMARY_TEMPLATE_P (TI_TEMPLATE (tinfo))
355           && uses_template_parms (INNERMOST_TEMPLATE_ARGS (TI_ARGS (tinfo))))
356         ++depth;
357     }
358
359   return depth;
360 }
361
362 /* Subroutine of maybe_begin_member_template_processing.
363    Returns true if processing DECL needs us to push template parms.  */
364
365 static bool
366 inline_needs_template_parms (tree decl)
367 {
368   if (! DECL_TEMPLATE_INFO (decl))
369     return false;
370
371   return (TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (most_general_template (decl)))
372           > (processing_template_decl + DECL_TEMPLATE_SPECIALIZATION (decl)));
373 }
374
375 /* Subroutine of maybe_begin_member_template_processing.
376    Push the template parms in PARMS, starting from LEVELS steps into the
377    chain, and ending at the beginning, since template parms are listed
378    innermost first.  */
379
380 static void
381 push_inline_template_parms_recursive (tree parmlist, int levels)
382 {
383   tree parms = TREE_VALUE (parmlist);
384   int i;
385
386   if (levels > 1)
387     push_inline_template_parms_recursive (TREE_CHAIN (parmlist), levels - 1);
388
389   ++processing_template_decl;
390   current_template_parms
391     = tree_cons (size_int (processing_template_decl),
392                  parms, current_template_parms);
393   TEMPLATE_PARMS_FOR_INLINE (current_template_parms) = 1;
394
395   begin_scope (TREE_VEC_LENGTH (parms) ? sk_template_parms : sk_template_spec,
396                NULL);
397   for (i = 0; i < TREE_VEC_LENGTH (parms); ++i)
398     {
399       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
400
401       if (parm == error_mark_node)
402         continue;
403
404       gcc_assert (DECL_P (parm));
405
406       switch (TREE_CODE (parm))
407         {
408         case TYPE_DECL:
409         case TEMPLATE_DECL:
410           pushdecl (parm);
411           break;
412
413         case PARM_DECL:
414           {
415             /* Make a CONST_DECL as is done in process_template_parm.
416                It is ugly that we recreate this here; the original
417                version built in process_template_parm is no longer
418                available.  */
419             tree decl = build_decl (DECL_SOURCE_LOCATION (parm),
420                                     CONST_DECL, DECL_NAME (parm),
421                                     TREE_TYPE (parm));
422             DECL_ARTIFICIAL (decl) = 1;
423             TREE_CONSTANT (decl) = 1;
424             TREE_READONLY (decl) = 1;
425             DECL_INITIAL (decl) = DECL_INITIAL (parm);
426             SET_DECL_TEMPLATE_PARM_P (decl);
427             pushdecl (decl);
428           }
429           break;
430
431         default:
432           gcc_unreachable ();
433         }
434     }
435 }
436
437 /* Restore the template parameter context for a member template or
438    a friend template defined in a class definition.  */
439
440 void
441 maybe_begin_member_template_processing (tree decl)
442 {
443   tree parms;
444   int levels = 0;
445
446   if (inline_needs_template_parms (decl))
447     {
448       parms = DECL_TEMPLATE_PARMS (most_general_template (decl));
449       levels = TMPL_PARMS_DEPTH (parms) - processing_template_decl;
450
451       if (DECL_TEMPLATE_SPECIALIZATION (decl))
452         {
453           --levels;
454           parms = TREE_CHAIN (parms);
455         }
456
457       push_inline_template_parms_recursive (parms, levels);
458     }
459
460   /* Remember how many levels of template parameters we pushed so that
461      we can pop them later.  */
462   VEC_safe_push (int, heap, inline_parm_levels, levels);
463 }
464
465 /* Undo the effects of maybe_begin_member_template_processing.  */
466
467 void
468 maybe_end_member_template_processing (void)
469 {
470   int i;
471   int last;
472
473   if (VEC_length (int, inline_parm_levels) == 0)
474     return;
475
476   last = VEC_pop (int, inline_parm_levels);
477   for (i = 0; i < last; ++i)
478     {
479       --processing_template_decl;
480       current_template_parms = TREE_CHAIN (current_template_parms);
481       poplevel (0, 0, 0);
482     }
483 }
484
485 /* Return a new template argument vector which contains all of ARGS,
486    but has as its innermost set of arguments the EXTRA_ARGS.  */
487
488 static tree
489 add_to_template_args (tree args, tree extra_args)
490 {
491   tree new_args;
492   int extra_depth;
493   int i;
494   int j;
495
496   if (args == NULL_TREE)
497     return extra_args;
498
499   extra_depth = TMPL_ARGS_DEPTH (extra_args);
500   new_args = make_tree_vec (TMPL_ARGS_DEPTH (args) + extra_depth);
501
502   for (i = 1; i <= TMPL_ARGS_DEPTH (args); ++i)
503     SET_TMPL_ARGS_LEVEL (new_args, i, TMPL_ARGS_LEVEL (args, i));
504
505   for (j = 1; j <= extra_depth; ++j, ++i)
506     SET_TMPL_ARGS_LEVEL (new_args, i, TMPL_ARGS_LEVEL (extra_args, j));
507
508   return new_args;
509 }
510
511 /* Like add_to_template_args, but only the outermost ARGS are added to
512    the EXTRA_ARGS.  In particular, all but TMPL_ARGS_DEPTH
513    (EXTRA_ARGS) levels are added.  This function is used to combine
514    the template arguments from a partial instantiation with the
515    template arguments used to attain the full instantiation from the
516    partial instantiation.  */
517
518 static tree
519 add_outermost_template_args (tree args, tree extra_args)
520 {
521   tree new_args;
522
523   /* If there are more levels of EXTRA_ARGS than there are ARGS,
524      something very fishy is going on.  */
525   gcc_assert (TMPL_ARGS_DEPTH (args) >= TMPL_ARGS_DEPTH (extra_args));
526
527   /* If *all* the new arguments will be the EXTRA_ARGS, just return
528      them.  */
529   if (TMPL_ARGS_DEPTH (args) == TMPL_ARGS_DEPTH (extra_args))
530     return extra_args;
531
532   /* For the moment, we make ARGS look like it contains fewer levels.  */
533   TREE_VEC_LENGTH (args) -= TMPL_ARGS_DEPTH (extra_args);
534
535   new_args = add_to_template_args (args, extra_args);
536
537   /* Now, we restore ARGS to its full dimensions.  */
538   TREE_VEC_LENGTH (args) += TMPL_ARGS_DEPTH (extra_args);
539
540   return new_args;
541 }
542
543 /* Return the N levels of innermost template arguments from the ARGS.  */
544
545 tree
546 get_innermost_template_args (tree args, int n)
547 {
548   tree new_args;
549   int extra_levels;
550   int i;
551
552   gcc_assert (n >= 0);
553
554   /* If N is 1, just return the innermost set of template arguments.  */
555   if (n == 1)
556     return TMPL_ARGS_LEVEL (args, TMPL_ARGS_DEPTH (args));
557
558   /* If we're not removing anything, just return the arguments we were
559      given.  */
560   extra_levels = TMPL_ARGS_DEPTH (args) - n;
561   gcc_assert (extra_levels >= 0);
562   if (extra_levels == 0)
563     return args;
564
565   /* Make a new set of arguments, not containing the outer arguments.  */
566   new_args = make_tree_vec (n);
567   for (i = 1; i <= n; ++i)
568     SET_TMPL_ARGS_LEVEL (new_args, i,
569                          TMPL_ARGS_LEVEL (args, i + extra_levels));
570
571   return new_args;
572 }
573
574 /* The inverse of get_innermost_template_args: Return all but the innermost
575    EXTRA_LEVELS levels of template arguments from the ARGS.  */
576
577 static tree
578 strip_innermost_template_args (tree args, int extra_levels)
579 {
580   tree new_args;
581   int n = TMPL_ARGS_DEPTH (args) - extra_levels;
582   int i;
583
584   gcc_assert (n >= 0);
585
586   /* If N is 1, just return the outermost set of template arguments.  */
587   if (n == 1)
588     return TMPL_ARGS_LEVEL (args, 1);
589
590   /* If we're not removing anything, just return the arguments we were
591      given.  */
592   gcc_assert (extra_levels >= 0);
593   if (extra_levels == 0)
594     return args;
595
596   /* Make a new set of arguments, not containing the inner arguments.  */
597   new_args = make_tree_vec (n);
598   for (i = 1; i <= n; ++i)
599     SET_TMPL_ARGS_LEVEL (new_args, i,
600                          TMPL_ARGS_LEVEL (args, i));
601
602   return new_args;
603 }
604
605 /* We've got a template header coming up; push to a new level for storing
606    the parms.  */
607
608 void
609 begin_template_parm_list (void)
610 {
611   /* We use a non-tag-transparent scope here, which causes pushtag to
612      put tags in this scope, rather than in the enclosing class or
613      namespace scope.  This is the right thing, since we want
614      TEMPLATE_DECLS, and not TYPE_DECLS for template classes.  For a
615      global template class, push_template_decl handles putting the
616      TEMPLATE_DECL into top-level scope.  For a nested template class,
617      e.g.:
618
619        template <class T> struct S1 {
620          template <class T> struct S2 {};
621        };
622
623      pushtag contains special code to call pushdecl_with_scope on the
624      TEMPLATE_DECL for S2.  */
625   begin_scope (sk_template_parms, NULL);
626   ++processing_template_decl;
627   ++processing_template_parmlist;
628   note_template_header (0);
629 }
630
631 /* This routine is called when a specialization is declared.  If it is
632    invalid to declare a specialization here, an error is reported and
633    false is returned, otherwise this routine will return true.  */
634
635 static bool
636 check_specialization_scope (void)
637 {
638   tree scope = current_scope ();
639
640   /* [temp.expl.spec]
641
642      An explicit specialization shall be declared in the namespace of
643      which the template is a member, or, for member templates, in the
644      namespace of which the enclosing class or enclosing class
645      template is a member.  An explicit specialization of a member
646      function, member class or static data member of a class template
647      shall be declared in the namespace of which the class template
648      is a member.  */
649   if (scope && TREE_CODE (scope) != NAMESPACE_DECL)
650     {
651       error ("explicit specialization in non-namespace scope %qD", scope);
652       return false;
653     }
654
655   /* [temp.expl.spec]
656
657      In an explicit specialization declaration for a member of a class
658      template or a member template that appears in namespace scope,
659      the member template and some of its enclosing class templates may
660      remain unspecialized, except that the declaration shall not
661      explicitly specialize a class member template if its enclosing
662      class templates are not explicitly specialized as well.  */
663   if (current_template_parms)
664     {
665       error ("enclosing class templates are not explicitly specialized");
666       return false;
667     }
668
669   return true;
670 }
671
672 /* We've just seen template <>.  */
673
674 bool
675 begin_specialization (void)
676 {
677   begin_scope (sk_template_spec, NULL);
678   note_template_header (1);
679   return check_specialization_scope ();
680 }
681
682 /* Called at then end of processing a declaration preceded by
683    template<>.  */
684
685 void
686 end_specialization (void)
687 {
688   finish_scope ();
689   reset_specialization ();
690 }
691
692 /* Any template <>'s that we have seen thus far are not referring to a
693    function specialization.  */
694
695 void
696 reset_specialization (void)
697 {
698   processing_specialization = 0;
699   template_header_count = 0;
700 }
701
702 /* We've just seen a template header.  If SPECIALIZATION is nonzero,
703    it was of the form template <>.  */
704
705 static void
706 note_template_header (int specialization)
707 {
708   processing_specialization = specialization;
709   template_header_count++;
710 }
711
712 /* We're beginning an explicit instantiation.  */
713
714 void
715 begin_explicit_instantiation (void)
716 {
717   gcc_assert (!processing_explicit_instantiation);
718   processing_explicit_instantiation = true;
719 }
720
721
722 void
723 end_explicit_instantiation (void)
724 {
725   gcc_assert (processing_explicit_instantiation);
726   processing_explicit_instantiation = false;
727 }
728
729 /* An explicit specialization or partial specialization TMPL is being
730    declared.  Check that the namespace in which the specialization is
731    occurring is permissible.  Returns false iff it is invalid to
732    specialize TMPL in the current namespace.  */
733
734 static bool
735 check_specialization_namespace (tree tmpl)
736 {
737   tree tpl_ns = decl_namespace_context (tmpl);
738
739   /* [tmpl.expl.spec]
740
741      An explicit specialization shall be declared in the namespace of
742      which the template is a member, or, for member templates, in the
743      namespace of which the enclosing class or enclosing class
744      template is a member.  An explicit specialization of a member
745      function, member class or static data member of a class template
746      shall be declared in the namespace of which the class template is
747      a member.  */
748   if (current_scope() != DECL_CONTEXT (tmpl)
749       && !at_namespace_scope_p ())
750     {
751       error ("specialization of %qD must appear at namespace scope", tmpl);
752       return false;
753     }
754   if (is_associated_namespace (current_namespace, tpl_ns))
755     /* Same or super-using namespace.  */
756     return true;
757   else
758     {
759       permerror (input_location, "specialization of %qD in different namespace", tmpl);
760       permerror (input_location, "  from definition of %q+#D", tmpl);
761       return false;
762     }
763 }
764
765 /* SPEC is an explicit instantiation.  Check that it is valid to
766    perform this explicit instantiation in the current namespace.  */
767
768 static void
769 check_explicit_instantiation_namespace (tree spec)
770 {
771   tree ns;
772
773   /* DR 275: An explicit instantiation shall appear in an enclosing
774      namespace of its template.  */
775   ns = decl_namespace_context (spec);
776   if (!is_ancestor (current_namespace, ns))
777     permerror (input_location, "explicit instantiation of %qD in namespace %qD "
778                "(which does not enclose namespace %qD)",
779                spec, current_namespace, ns);
780 }
781
782 /* The TYPE is being declared.  If it is a template type, that means it
783    is a partial specialization.  Do appropriate error-checking.  */
784
785 tree
786 maybe_process_partial_specialization (tree type)
787 {
788   tree context;
789
790   if (type == error_mark_node)
791     return error_mark_node;
792
793   if (TREE_CODE (type) == BOUND_TEMPLATE_TEMPLATE_PARM)
794     {
795       error ("name of class shadows template template parameter %qD",
796              TYPE_NAME (type));
797       return error_mark_node;
798     }
799
800   context = TYPE_CONTEXT (type);
801
802   if (CLASS_TYPE_P (type) && CLASSTYPE_USE_TEMPLATE (type))
803     {
804       /* This is for ordinary explicit specialization and partial
805          specialization of a template class such as:
806
807            template <> class C<int>;
808
809          or:
810
811            template <class T> class C<T*>;
812
813          Make sure that `C<int>' and `C<T*>' are implicit instantiations.  */
814
815       if (CLASSTYPE_IMPLICIT_INSTANTIATION (type)
816           && !COMPLETE_TYPE_P (type))
817         {
818           check_specialization_namespace (CLASSTYPE_TI_TEMPLATE (type));
819           SET_CLASSTYPE_TEMPLATE_SPECIALIZATION (type);
820           if (processing_template_decl)
821             {
822               if (push_template_decl (TYPE_MAIN_DECL (type))
823                   == error_mark_node)
824                 return error_mark_node;
825             }
826         }
827       else if (CLASSTYPE_TEMPLATE_INSTANTIATION (type))
828         error ("specialization of %qT after instantiation", type);
829     }
830   else if (CLASS_TYPE_P (type)
831            && !CLASSTYPE_USE_TEMPLATE (type)
832            && CLASSTYPE_TEMPLATE_INFO (type)
833            && context && CLASS_TYPE_P (context)
834            && CLASSTYPE_TEMPLATE_INFO (context))
835     {
836       /* This is for an explicit specialization of member class
837          template according to [temp.expl.spec/18]:
838
839            template <> template <class U> class C<int>::D;
840
841          The context `C<int>' must be an implicit instantiation.
842          Otherwise this is just a member class template declared
843          earlier like:
844
845            template <> class C<int> { template <class U> class D; };
846            template <> template <class U> class C<int>::D;
847
848          In the first case, `C<int>::D' is a specialization of `C<T>::D'
849          while in the second case, `C<int>::D' is a primary template
850          and `C<T>::D' may not exist.  */
851
852       if (CLASSTYPE_IMPLICIT_INSTANTIATION (context)
853           && !COMPLETE_TYPE_P (type))
854         {
855           tree t;
856           tree tmpl = CLASSTYPE_TI_TEMPLATE (type);
857
858           if (current_namespace
859               != decl_namespace_context (tmpl))
860             {
861               permerror (input_location, "specializing %q#T in different namespace", type);
862               permerror (input_location, "  from definition of %q+#D", tmpl);
863             }
864
865           /* Check for invalid specialization after instantiation:
866
867                template <> template <> class C<int>::D<int>;
868                template <> template <class U> class C<int>::D;  */
869
870           for (t = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
871                t; t = TREE_CHAIN (t))
872             {
873               tree inst = TREE_VALUE (t);
874               if (CLASSTYPE_TEMPLATE_SPECIALIZATION (inst))
875                 {
876                   /* We already have a full specialization of this partial
877                      instantiation.  Reassign it to the new member
878                      specialization template.  */
879                   spec_entry elt;
880                   spec_entry **slot;
881
882                   elt.tmpl = most_general_template (tmpl);
883                   elt.args = CLASSTYPE_TI_ARGS (inst);
884                   elt.spec = inst;
885
886                   htab_remove_elt (type_specializations, &elt);
887
888                   elt.tmpl = tmpl;
889                   elt.args = INNERMOST_TEMPLATE_ARGS (elt.args);
890
891                   slot = (spec_entry **)
892                     htab_find_slot (type_specializations, &elt, INSERT);
893                   *slot = GGC_NEW (spec_entry);
894                   **slot = elt;
895                 }
896               else if (COMPLETE_TYPE_P (inst) || TYPE_BEING_DEFINED (inst))
897                 /* But if we've had an implicit instantiation, that's a
898                    problem ([temp.expl.spec]/6).  */
899                 error ("specialization %qT after instantiation %qT",
900                        type, inst);
901             }
902
903           /* Mark TYPE as a specialization.  And as a result, we only
904              have one level of template argument for the innermost
905              class template.  */
906           SET_CLASSTYPE_TEMPLATE_SPECIALIZATION (type);
907           CLASSTYPE_TI_ARGS (type)
908             = INNERMOST_TEMPLATE_ARGS (CLASSTYPE_TI_ARGS (type));
909         }
910     }
911   else if (processing_specialization)
912     {
913       error ("explicit specialization of non-template %qT", type);
914       return error_mark_node;
915     }
916
917   return type;
918 }
919
920 /* Returns nonzero if we can optimize the retrieval of specializations
921    for TMPL, a TEMPLATE_DECL.  In particular, for such a template, we
922    do not use DECL_TEMPLATE_SPECIALIZATIONS at all.  */
923
924 static inline bool
925 optimize_specialization_lookup_p (tree tmpl)
926 {
927   return (DECL_FUNCTION_TEMPLATE_P (tmpl)
928           && DECL_CLASS_SCOPE_P (tmpl)
929           /* DECL_CLASS_SCOPE_P holds of T::f even if T is a template
930              parameter.  */
931           && CLASS_TYPE_P (DECL_CONTEXT (tmpl))
932           /* The optimized lookup depends on the fact that the
933              template arguments for the member function template apply
934              purely to the containing class, which is not true if the
935              containing class is an explicit or partial
936              specialization.  */
937           && !CLASSTYPE_TEMPLATE_SPECIALIZATION (DECL_CONTEXT (tmpl))
938           && !DECL_MEMBER_TEMPLATE_P (tmpl)
939           && !DECL_CONV_FN_P (tmpl)
940           /* It is possible to have a template that is not a member
941              template and is not a member of a template class:
942
943              template <typename T>
944              struct S { friend A::f(); };
945
946              Here, the friend function is a template, but the context does
947              not have template information.  The optimized lookup relies
948              on having ARGS be the template arguments for both the class
949              and the function template.  */
950           && !DECL_FRIEND_P (DECL_TEMPLATE_RESULT (tmpl)));
951 }
952
953 /* Retrieve the specialization (in the sense of [temp.spec] - a
954    specialization is either an instantiation or an explicit
955    specialization) of TMPL for the given template ARGS.  If there is
956    no such specialization, return NULL_TREE.  The ARGS are a vector of
957    arguments, or a vector of vectors of arguments, in the case of
958    templates with more than one level of parameters.
959
960    If TMPL is a type template and CLASS_SPECIALIZATIONS_P is true,
961    then we search for a partial specialization matching ARGS.  This
962    parameter is ignored if TMPL is not a class template.  */
963
964 static tree
965 retrieve_specialization (tree tmpl, tree args, hashval_t hash)
966 {
967   if (args == error_mark_node)
968     return NULL_TREE;
969
970   gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL);
971
972   /* There should be as many levels of arguments as there are
973      levels of parameters.  */
974   gcc_assert (TMPL_ARGS_DEPTH (args)
975               == TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl)));
976
977   if (optimize_specialization_lookup_p (tmpl))
978     {
979       tree class_template;
980       tree class_specialization;
981       VEC(tree,gc) *methods;
982       tree fns;
983       int idx;
984
985       /* The template arguments actually apply to the containing
986          class.  Find the class specialization with those
987          arguments.  */
988       class_template = CLASSTYPE_TI_TEMPLATE (DECL_CONTEXT (tmpl));
989       class_specialization
990         = retrieve_specialization (class_template, args, 0);
991       if (!class_specialization)
992         return NULL_TREE;
993       /* Now, find the appropriate entry in the CLASSTYPE_METHOD_VEC
994          for the specialization.  */
995       idx = class_method_index_for_fn (class_specialization, tmpl);
996       if (idx == -1)
997         return NULL_TREE;
998       /* Iterate through the methods with the indicated name, looking
999          for the one that has an instance of TMPL.  */
1000       methods = CLASSTYPE_METHOD_VEC (class_specialization);
1001       for (fns = VEC_index (tree, methods, idx); fns; fns = OVL_NEXT (fns))
1002         {
1003           tree fn = OVL_CURRENT (fns);
1004           if (DECL_TEMPLATE_INFO (fn) && DECL_TI_TEMPLATE (fn) == tmpl
1005               /* using-declarations can add base methods to the method vec,
1006                  and we don't want those here.  */
1007               && DECL_CONTEXT (fn) == class_specialization)
1008             return fn;
1009         }
1010       return NULL_TREE;
1011     }
1012   else
1013     {
1014       spec_entry *found;
1015       spec_entry elt;
1016       htab_t specializations;
1017
1018       elt.tmpl = tmpl;
1019       elt.args = args;
1020       elt.spec = NULL_TREE;
1021
1022       if (DECL_CLASS_TEMPLATE_P (tmpl))
1023         specializations = type_specializations;
1024       else
1025         specializations = decl_specializations;
1026
1027       if (hash == 0)
1028         hash = hash_specialization (&elt);
1029       found = (spec_entry *) htab_find_with_hash (specializations, &elt, hash);
1030       if (found)
1031         return found->spec;
1032     }
1033
1034   return NULL_TREE;
1035 }
1036
1037 /* Like retrieve_specialization, but for local declarations.  */
1038
1039 static tree
1040 retrieve_local_specialization (tree tmpl)
1041 {
1042   tree spec;
1043
1044   if (local_specializations == NULL)
1045     return NULL_TREE;
1046
1047   spec = (tree) htab_find_with_hash (local_specializations, tmpl,
1048                                      htab_hash_pointer (tmpl));
1049   return spec ? TREE_PURPOSE (spec) : NULL_TREE;
1050 }
1051
1052 /* Returns nonzero iff DECL is a specialization of TMPL.  */
1053
1054 int
1055 is_specialization_of (tree decl, tree tmpl)
1056 {
1057   tree t;
1058
1059   if (TREE_CODE (decl) == FUNCTION_DECL)
1060     {
1061       for (t = decl;
1062            t != NULL_TREE;
1063            t = DECL_TEMPLATE_INFO (t) ? DECL_TI_TEMPLATE (t) : NULL_TREE)
1064         if (t == tmpl)
1065           return 1;
1066     }
1067   else
1068     {
1069       gcc_assert (TREE_CODE (decl) == TYPE_DECL);
1070
1071       for (t = TREE_TYPE (decl);
1072            t != NULL_TREE;
1073            t = CLASSTYPE_USE_TEMPLATE (t)
1074              ? TREE_TYPE (CLASSTYPE_TI_TEMPLATE (t)) : NULL_TREE)
1075         if (same_type_ignoring_top_level_qualifiers_p (t, TREE_TYPE (tmpl)))
1076           return 1;
1077     }
1078
1079   return 0;
1080 }
1081
1082 /* Returns nonzero iff DECL is a specialization of friend declaration
1083    FRIEND_DECL according to [temp.friend].  */
1084
1085 bool
1086 is_specialization_of_friend (tree decl, tree friend_decl)
1087 {
1088   bool need_template = true;
1089   int template_depth;
1090
1091   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL
1092               || TREE_CODE (decl) == TYPE_DECL);
1093
1094   /* For [temp.friend/6] when FRIEND_DECL is an ordinary member function
1095      of a template class, we want to check if DECL is a specialization
1096      if this.  */
1097   if (TREE_CODE (friend_decl) == FUNCTION_DECL
1098       && DECL_TEMPLATE_INFO (friend_decl)
1099       && !DECL_USE_TEMPLATE (friend_decl))
1100     {
1101       /* We want a TEMPLATE_DECL for `is_specialization_of'.  */
1102       friend_decl = DECL_TI_TEMPLATE (friend_decl);
1103       need_template = false;
1104     }
1105   else if (TREE_CODE (friend_decl) == TEMPLATE_DECL
1106            && !PRIMARY_TEMPLATE_P (friend_decl))
1107     need_template = false;
1108
1109   /* There is nothing to do if this is not a template friend.  */
1110   if (TREE_CODE (friend_decl) != TEMPLATE_DECL)
1111     return false;
1112
1113   if (is_specialization_of (decl, friend_decl))
1114     return true;
1115
1116   /* [temp.friend/6]
1117      A member of a class template may be declared to be a friend of a
1118      non-template class.  In this case, the corresponding member of
1119      every specialization of the class template is a friend of the
1120      class granting friendship.
1121
1122      For example, given a template friend declaration
1123
1124        template <class T> friend void A<T>::f();
1125
1126      the member function below is considered a friend
1127
1128        template <> struct A<int> {
1129          void f();
1130        };
1131
1132      For this type of template friend, TEMPLATE_DEPTH below will be
1133      nonzero.  To determine if DECL is a friend of FRIEND, we first
1134      check if the enclosing class is a specialization of another.  */
1135
1136   template_depth = template_class_depth (DECL_CONTEXT (friend_decl));
1137   if (template_depth
1138       && DECL_CLASS_SCOPE_P (decl)
1139       && is_specialization_of (TYPE_NAME (DECL_CONTEXT (decl)),
1140                                CLASSTYPE_TI_TEMPLATE (DECL_CONTEXT (friend_decl))))
1141     {
1142       /* Next, we check the members themselves.  In order to handle
1143          a few tricky cases, such as when FRIEND_DECL's are
1144
1145            template <class T> friend void A<T>::g(T t);
1146            template <class T> template <T t> friend void A<T>::h();
1147
1148          and DECL's are
1149
1150            void A<int>::g(int);
1151            template <int> void A<int>::h();
1152
1153          we need to figure out ARGS, the template arguments from
1154          the context of DECL.  This is required for template substitution
1155          of `T' in the function parameter of `g' and template parameter
1156          of `h' in the above examples.  Here ARGS corresponds to `int'.  */
1157
1158       tree context = DECL_CONTEXT (decl);
1159       tree args = NULL_TREE;
1160       int current_depth = 0;
1161
1162       while (current_depth < template_depth)
1163         {
1164           if (CLASSTYPE_TEMPLATE_INFO (context))
1165             {
1166               if (current_depth == 0)
1167                 args = TYPE_TI_ARGS (context);
1168               else
1169                 args = add_to_template_args (TYPE_TI_ARGS (context), args);
1170               current_depth++;
1171             }
1172           context = TYPE_CONTEXT (context);
1173         }
1174
1175       if (TREE_CODE (decl) == FUNCTION_DECL)
1176         {
1177           bool is_template;
1178           tree friend_type;
1179           tree decl_type;
1180           tree friend_args_type;
1181           tree decl_args_type;
1182
1183           /* Make sure that both DECL and FRIEND_DECL are templates or
1184              non-templates.  */
1185           is_template = DECL_TEMPLATE_INFO (decl)
1186                         && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (decl));
1187           if (need_template ^ is_template)
1188             return false;
1189           else if (is_template)
1190             {
1191               /* If both are templates, check template parameter list.  */
1192               tree friend_parms
1193                 = tsubst_template_parms (DECL_TEMPLATE_PARMS (friend_decl),
1194                                          args, tf_none);
1195               if (!comp_template_parms
1196                      (DECL_TEMPLATE_PARMS (DECL_TI_TEMPLATE (decl)),
1197                       friend_parms))
1198                 return false;
1199
1200               decl_type = TREE_TYPE (DECL_TI_TEMPLATE (decl));
1201             }
1202           else
1203             decl_type = TREE_TYPE (decl);
1204
1205           friend_type = tsubst_function_type (TREE_TYPE (friend_decl), args,
1206                                               tf_none, NULL_TREE);
1207           if (friend_type == error_mark_node)
1208             return false;
1209
1210           /* Check if return types match.  */
1211           if (!same_type_p (TREE_TYPE (decl_type), TREE_TYPE (friend_type)))
1212             return false;
1213
1214           /* Check if function parameter types match, ignoring the
1215              `this' parameter.  */
1216           friend_args_type = TYPE_ARG_TYPES (friend_type);
1217           decl_args_type = TYPE_ARG_TYPES (decl_type);
1218           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (friend_decl))
1219             friend_args_type = TREE_CHAIN (friend_args_type);
1220           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1221             decl_args_type = TREE_CHAIN (decl_args_type);
1222
1223           return compparms (decl_args_type, friend_args_type);
1224         }
1225       else
1226         {
1227           /* DECL is a TYPE_DECL */
1228           bool is_template;
1229           tree decl_type = TREE_TYPE (decl);
1230
1231           /* Make sure that both DECL and FRIEND_DECL are templates or
1232              non-templates.  */
1233           is_template
1234             = CLASSTYPE_TEMPLATE_INFO (decl_type)
1235               && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (decl_type));
1236
1237           if (need_template ^ is_template)
1238             return false;
1239           else if (is_template)
1240             {
1241               tree friend_parms;
1242               /* If both are templates, check the name of the two
1243                  TEMPLATE_DECL's first because is_friend didn't.  */
1244               if (DECL_NAME (CLASSTYPE_TI_TEMPLATE (decl_type))
1245                   != DECL_NAME (friend_decl))
1246                 return false;
1247
1248               /* Now check template parameter list.  */
1249               friend_parms
1250                 = tsubst_template_parms (DECL_TEMPLATE_PARMS (friend_decl),
1251                                          args, tf_none);
1252               return comp_template_parms
1253                 (DECL_TEMPLATE_PARMS (CLASSTYPE_TI_TEMPLATE (decl_type)),
1254                  friend_parms);
1255             }
1256           else
1257             return (DECL_NAME (decl)
1258                     == DECL_NAME (friend_decl));
1259         }
1260     }
1261   return false;
1262 }
1263
1264 /* Register the specialization SPEC as a specialization of TMPL with
1265    the indicated ARGS.  IS_FRIEND indicates whether the specialization
1266    is actually just a friend declaration.  Returns SPEC, or an
1267    equivalent prior declaration, if available.  */
1268
1269 static tree
1270 register_specialization (tree spec, tree tmpl, tree args, bool is_friend,
1271                          hashval_t hash)
1272 {
1273   tree fn;
1274   spec_entry **slot = NULL;
1275   spec_entry elt;
1276
1277   gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL && DECL_P (spec));
1278
1279   if (TREE_CODE (spec) == FUNCTION_DECL
1280       && uses_template_parms (DECL_TI_ARGS (spec)))
1281     /* This is the FUNCTION_DECL for a partial instantiation.  Don't
1282        register it; we want the corresponding TEMPLATE_DECL instead.
1283        We use `uses_template_parms (DECL_TI_ARGS (spec))' rather than
1284        the more obvious `uses_template_parms (spec)' to avoid problems
1285        with default function arguments.  In particular, given
1286        something like this:
1287
1288           template <class T> void f(T t1, T t = T())
1289
1290        the default argument expression is not substituted for in an
1291        instantiation unless and until it is actually needed.  */
1292     return spec;
1293
1294   if (optimize_specialization_lookup_p (tmpl))
1295     /* We don't put these specializations in the hash table, but we might
1296        want to give an error about a mismatch.  */
1297     fn = retrieve_specialization (tmpl, args, 0);
1298   else
1299     {
1300       elt.tmpl = tmpl;
1301       elt.args = args;
1302       elt.spec = spec;
1303
1304       if (hash == 0)
1305         hash = hash_specialization (&elt);
1306
1307       slot = (spec_entry **)
1308         htab_find_slot_with_hash (decl_specializations, &elt, hash, INSERT);
1309       if (*slot)
1310         fn = (*slot)->spec;
1311       else
1312         fn = NULL_TREE;
1313     }
1314
1315   /* We can sometimes try to re-register a specialization that we've
1316      already got.  In particular, regenerate_decl_from_template calls
1317      duplicate_decls which will update the specialization list.  But,
1318      we'll still get called again here anyhow.  It's more convenient
1319      to simply allow this than to try to prevent it.  */
1320   if (fn == spec)
1321     return spec;
1322   else if (fn && DECL_TEMPLATE_SPECIALIZATION (spec))
1323     {
1324       if (DECL_TEMPLATE_INSTANTIATION (fn))
1325         {
1326           if (DECL_ODR_USED (fn)
1327               || DECL_EXPLICIT_INSTANTIATION (fn))
1328             {
1329               error ("specialization of %qD after instantiation",
1330                      fn);
1331               return error_mark_node;
1332             }
1333           else
1334             {
1335               tree clone;
1336               /* This situation should occur only if the first
1337                  specialization is an implicit instantiation, the
1338                  second is an explicit specialization, and the
1339                  implicit instantiation has not yet been used.  That
1340                  situation can occur if we have implicitly
1341                  instantiated a member function and then specialized
1342                  it later.
1343
1344                  We can also wind up here if a friend declaration that
1345                  looked like an instantiation turns out to be a
1346                  specialization:
1347
1348                    template <class T> void foo(T);
1349                    class S { friend void foo<>(int) };
1350                    template <> void foo(int);
1351
1352                  We transform the existing DECL in place so that any
1353                  pointers to it become pointers to the updated
1354                  declaration.
1355
1356                  If there was a definition for the template, but not
1357                  for the specialization, we want this to look as if
1358                  there were no definition, and vice versa.  */
1359               DECL_INITIAL (fn) = NULL_TREE;
1360               duplicate_decls (spec, fn, is_friend);
1361               /* The call to duplicate_decls will have applied
1362                  [temp.expl.spec]:
1363
1364                    An explicit specialization of a function template
1365                    is inline only if it is explicitly declared to be,
1366                    and independently of whether its function template
1367                    is.
1368
1369                 to the primary function; now copy the inline bits to
1370                 the various clones.  */
1371               FOR_EACH_CLONE (clone, fn)
1372                 {
1373                   DECL_DECLARED_INLINE_P (clone)
1374                     = DECL_DECLARED_INLINE_P (fn);
1375                   DECL_SOURCE_LOCATION (clone)
1376                     = DECL_SOURCE_LOCATION (fn);
1377                 }
1378               check_specialization_namespace (fn);
1379
1380               return fn;
1381             }
1382         }
1383       else if (DECL_TEMPLATE_SPECIALIZATION (fn))
1384         {
1385           if (!duplicate_decls (spec, fn, is_friend) && DECL_INITIAL (spec))
1386             /* Dup decl failed, but this is a new definition. Set the
1387                line number so any errors match this new
1388                definition.  */
1389             DECL_SOURCE_LOCATION (fn) = DECL_SOURCE_LOCATION (spec);
1390
1391           return fn;
1392         }
1393     }
1394   else if (fn)
1395     return duplicate_decls (spec, fn, is_friend);
1396
1397   /* A specialization must be declared in the same namespace as the
1398      template it is specializing.  */
1399   if (DECL_TEMPLATE_SPECIALIZATION (spec)
1400       && !check_specialization_namespace (tmpl))
1401     DECL_CONTEXT (spec) = DECL_CONTEXT (tmpl);
1402
1403   if (!optimize_specialization_lookup_p (tmpl))
1404     {
1405       gcc_assert (tmpl && args && spec);
1406       *slot = GGC_NEW (spec_entry);
1407       **slot = elt;
1408       if (TREE_CODE (spec) == FUNCTION_DECL && DECL_NAMESPACE_SCOPE_P (spec)
1409           && PRIMARY_TEMPLATE_P (tmpl)
1410           && DECL_SAVED_TREE (DECL_TEMPLATE_RESULT (tmpl)) == NULL_TREE)
1411         /* TMPL is a forward declaration of a template function; keep a list
1412            of all specializations in case we need to reassign them to a friend
1413            template later in tsubst_friend_function.  */
1414         DECL_TEMPLATE_INSTANTIATIONS (tmpl)
1415           = tree_cons (args, spec, DECL_TEMPLATE_INSTANTIATIONS (tmpl));
1416     }
1417
1418   return spec;
1419 }
1420
1421 /* Returns true iff two spec_entry nodes are equivalent.  Only compares the
1422    TMPL and ARGS members, ignores SPEC.  */
1423
1424 static int
1425 eq_specializations (const void *p1, const void *p2)
1426 {
1427   const spec_entry *e1 = (const spec_entry *)p1;
1428   const spec_entry *e2 = (const spec_entry *)p2;
1429
1430   return (e1->tmpl == e2->tmpl
1431           && comp_template_args (e1->args, e2->args));
1432 }
1433
1434 /* Returns a hash for a template TMPL and template arguments ARGS.  */
1435
1436 static hashval_t
1437 hash_tmpl_and_args (tree tmpl, tree args)
1438 {
1439   hashval_t val = DECL_UID (tmpl);
1440   return iterative_hash_template_arg (args, val);
1441 }
1442
1443 /* Returns a hash for a spec_entry node based on the TMPL and ARGS members,
1444    ignoring SPEC.  */
1445
1446 static hashval_t
1447 hash_specialization (const void *p)
1448 {
1449   const spec_entry *e = (const spec_entry *)p;
1450   return hash_tmpl_and_args (e->tmpl, e->args);
1451 }
1452
1453 /* Recursively calculate a hash value for a template argument ARG, for use
1454    in the hash tables of template specializations.  */
1455
1456 static hashval_t
1457 iterative_hash_template_arg (tree arg, hashval_t val)
1458 {
1459   unsigned HOST_WIDE_INT i;
1460   enum tree_code code;
1461   char tclass;
1462
1463   if (arg == NULL_TREE)
1464     return iterative_hash_object (arg, val);
1465
1466   if (!TYPE_P (arg))
1467     STRIP_NOPS (arg);
1468
1469   if (TREE_CODE (arg) == ARGUMENT_PACK_SELECT)
1470     /* We can get one of these when re-hashing a previous entry in the middle
1471        of substituting into a pack expansion.  Just look through it.  */
1472     arg = ARGUMENT_PACK_SELECT_FROM_PACK (arg);
1473
1474   code = TREE_CODE (arg);
1475   tclass = TREE_CODE_CLASS (code);
1476
1477   val = iterative_hash_object (code, val);
1478
1479   switch (code)
1480     {
1481     case ERROR_MARK:
1482       return val;
1483
1484     case IDENTIFIER_NODE:
1485       return iterative_hash_object (IDENTIFIER_HASH_VALUE (arg), val);
1486
1487     case TREE_VEC:
1488       {
1489         int i, len = TREE_VEC_LENGTH (arg);
1490         for (i = 0; i < len; ++i)
1491           val = iterative_hash_template_arg (TREE_VEC_ELT (arg, i), val);
1492         return val;
1493       }
1494
1495     case TYPE_PACK_EXPANSION:
1496     case EXPR_PACK_EXPANSION:
1497       return iterative_hash_template_arg (PACK_EXPANSION_PATTERN (arg), val);
1498
1499     case TYPE_ARGUMENT_PACK:
1500     case NONTYPE_ARGUMENT_PACK:
1501       return iterative_hash_template_arg (ARGUMENT_PACK_ARGS (arg), val);
1502
1503     case TREE_LIST:
1504       for (; arg; arg = TREE_CHAIN (arg))
1505         val = iterative_hash_template_arg (TREE_VALUE (arg), val);
1506       return val;
1507
1508     case OVERLOAD:
1509       for (; arg; arg = OVL_CHAIN (arg))
1510         val = iterative_hash_template_arg (OVL_FUNCTION (arg), val);
1511       return val;
1512
1513     case CONSTRUCTOR:
1514       {
1515         tree field, value;
1516         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (arg), i, field, value)
1517           {
1518             val = iterative_hash_template_arg (field, val);
1519             val = iterative_hash_template_arg (value, val);
1520           }
1521         return val;
1522       }
1523
1524     case PARM_DECL:
1525       if (!DECL_ARTIFICIAL (arg))
1526         val = iterative_hash_object (DECL_PARM_INDEX (arg), val);
1527       return iterative_hash_template_arg (TREE_TYPE (arg), val);
1528
1529     case TARGET_EXPR:
1530       return iterative_hash_template_arg (TARGET_EXPR_INITIAL (arg), val);
1531
1532     case PTRMEM_CST:
1533       val = iterative_hash_template_arg (PTRMEM_CST_CLASS (arg), val);
1534       return iterative_hash_template_arg (PTRMEM_CST_MEMBER (arg), val);
1535
1536     case TEMPLATE_PARM_INDEX:
1537       val = iterative_hash_template_arg
1538         (TREE_TYPE (TEMPLATE_PARM_DECL (arg)), val);
1539       val = iterative_hash_object (TEMPLATE_PARM_LEVEL (arg), val);
1540       return iterative_hash_object (TEMPLATE_PARM_IDX (arg), val);
1541
1542     case TRAIT_EXPR:
1543       val = iterative_hash_object (TRAIT_EXPR_KIND (arg), val);
1544       val = iterative_hash_template_arg (TRAIT_EXPR_TYPE1 (arg), val);
1545       return iterative_hash_template_arg (TRAIT_EXPR_TYPE2 (arg), val);
1546
1547     case BASELINK:
1548       val = iterative_hash_template_arg (BINFO_TYPE (BASELINK_BINFO (arg)),
1549                                          val);
1550       return iterative_hash_template_arg (DECL_NAME (get_first_fn (arg)),
1551                                           val);
1552
1553     case MODOP_EXPR:
1554       val = iterative_hash_template_arg (TREE_OPERAND (arg, 0), val);
1555       code = TREE_CODE (TREE_OPERAND (arg, 1));
1556       val = iterative_hash_object (code, val);
1557       return iterative_hash_template_arg (TREE_OPERAND (arg, 2), val);
1558
1559     case ARRAY_TYPE:
1560       /* layout_type sets structural equality for arrays of
1561          incomplete type, so we can't rely on the canonical type
1562          for hashing.  */
1563       val = iterative_hash_template_arg (TREE_TYPE (arg), val);
1564       return iterative_hash_template_arg (TYPE_DOMAIN (arg), val);
1565
1566     case LAMBDA_EXPR:
1567       /* A lambda can't appear in a template arg, but don't crash on
1568          erroneous input.  */
1569       gcc_assert (errorcount > 0);
1570       return val;
1571
1572     default:
1573       switch (tclass)
1574         {
1575         case tcc_type:
1576           if (TYPE_CANONICAL (arg))
1577             return iterative_hash_object (TYPE_HASH (TYPE_CANONICAL (arg)),
1578                                           val);
1579           else if (TREE_CODE (arg) == DECLTYPE_TYPE)
1580             return iterative_hash_template_arg (DECLTYPE_TYPE_EXPR (arg), val);
1581           /* Otherwise just compare the types during lookup.  */
1582           return val;
1583
1584         case tcc_declaration:
1585         case tcc_constant:
1586           return iterative_hash_expr (arg, val);
1587
1588         default:
1589           gcc_assert (IS_EXPR_CODE_CLASS (tclass));
1590           {
1591             unsigned n = TREE_OPERAND_LENGTH (arg);
1592             for (i = 0; i < n; ++i)
1593               val = iterative_hash_template_arg (TREE_OPERAND (arg, i), val);
1594             return val;
1595           }
1596         }
1597     }
1598   gcc_unreachable ();
1599   return 0;
1600 }
1601
1602 /* Unregister the specialization SPEC as a specialization of TMPL.
1603    Replace it with NEW_SPEC, if NEW_SPEC is non-NULL.  Returns true
1604    if the SPEC was listed as a specialization of TMPL.
1605
1606    Note that SPEC has been ggc_freed, so we can't look inside it.  */
1607
1608 bool
1609 reregister_specialization (tree spec, tree tinfo, tree new_spec)
1610 {
1611   spec_entry **slot;
1612   spec_entry elt;
1613
1614   elt.tmpl = most_general_template (TI_TEMPLATE (tinfo));
1615   elt.args = TI_ARGS (tinfo);
1616   elt.spec = NULL_TREE;
1617
1618   slot = (spec_entry **) htab_find_slot (decl_specializations, &elt, INSERT);
1619   if (*slot)
1620     {
1621       gcc_assert ((*slot)->spec == spec || (*slot)->spec == new_spec);
1622       gcc_assert (new_spec != NULL_TREE);
1623       (*slot)->spec = new_spec;
1624       return 1;
1625     }
1626
1627   return 0;
1628 }
1629
1630 /* Compare an entry in the local specializations hash table P1 (which
1631    is really a pointer to a TREE_LIST) with P2 (which is really a
1632    DECL).  */
1633
1634 static int
1635 eq_local_specializations (const void *p1, const void *p2)
1636 {
1637   return TREE_VALUE ((const_tree) p1) == (const_tree) p2;
1638 }
1639
1640 /* Hash P1, an entry in the local specializations table.  */
1641
1642 static hashval_t
1643 hash_local_specialization (const void* p1)
1644 {
1645   return htab_hash_pointer (TREE_VALUE ((const_tree) p1));
1646 }
1647
1648 /* Like register_specialization, but for local declarations.  We are
1649    registering SPEC, an instantiation of TMPL.  */
1650
1651 static void
1652 register_local_specialization (tree spec, tree tmpl)
1653 {
1654   void **slot;
1655
1656   slot = htab_find_slot_with_hash (local_specializations, tmpl,
1657                                    htab_hash_pointer (tmpl), INSERT);
1658   *slot = build_tree_list (spec, tmpl);
1659 }
1660
1661 /* TYPE is a class type.  Returns true if TYPE is an explicitly
1662    specialized class.  */
1663
1664 bool
1665 explicit_class_specialization_p (tree type)
1666 {
1667   if (!CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
1668     return false;
1669   return !uses_template_parms (CLASSTYPE_TI_ARGS (type));
1670 }
1671
1672 /* Print the list of functions at FNS, going through all the overloads
1673    for each element of the list.  Alternatively, FNS can not be a
1674    TREE_LIST, in which case it will be printed together with all the
1675    overloads.
1676
1677    MORE and *STR should respectively be FALSE and NULL when the function
1678    is called from the outside.  They are used internally on recursive
1679    calls.  print_candidates manages the two parameters and leaves NULL
1680    in *STR when it ends.  */
1681
1682 static void
1683 print_candidates_1 (tree fns, bool more, const char **str)
1684 {
1685   tree fn, fn2;
1686   char *spaces = NULL;
1687
1688   for (fn = fns; fn; fn = OVL_NEXT (fn))
1689     if (TREE_CODE (fn) == TREE_LIST)
1690       {
1691         gcc_assert (!OVL_NEXT (fn) && !is_overloaded_fn (fn));
1692         for (fn2 = fn; fn2 != NULL_TREE; fn2 = TREE_CHAIN (fn2))
1693           print_candidates_1 (TREE_VALUE (fn2),
1694                               TREE_CHAIN (fn2) || more, str);
1695       }
1696     else
1697       {
1698         if (!*str)
1699           {
1700             /* Pick the prefix string.  */
1701             if (!more && !OVL_NEXT (fns))
1702               {
1703                 error ("candidate is: %+#D", OVL_CURRENT (fn));
1704                 continue;
1705               }
1706
1707             *str = _("candidates are:");
1708             spaces = get_spaces (*str);
1709           }
1710         error ("%s %+#D", *str, OVL_CURRENT (fn));
1711         *str = spaces ? spaces : *str;
1712       }
1713
1714   if (!more)
1715     {
1716       free (spaces);
1717       *str = NULL;
1718     }
1719 }
1720
1721 /* Print the list of candidate FNS in an error message.  */
1722
1723 void
1724 print_candidates (tree fns)
1725 {
1726   const char *str = NULL;
1727   print_candidates_1 (fns, false, &str);
1728   gcc_assert (str == NULL);
1729 }
1730
1731 /* Returns the template (one of the functions given by TEMPLATE_ID)
1732    which can be specialized to match the indicated DECL with the
1733    explicit template args given in TEMPLATE_ID.  The DECL may be
1734    NULL_TREE if none is available.  In that case, the functions in
1735    TEMPLATE_ID are non-members.
1736
1737    If NEED_MEMBER_TEMPLATE is nonzero the function is known to be a
1738    specialization of a member template.
1739
1740    The TEMPLATE_COUNT is the number of references to qualifying
1741    template classes that appeared in the name of the function. See
1742    check_explicit_specialization for a more accurate description.
1743
1744    TSK indicates what kind of template declaration (if any) is being
1745    declared.  TSK_TEMPLATE indicates that the declaration given by
1746    DECL, though a FUNCTION_DECL, has template parameters, and is
1747    therefore a template function.
1748
1749    The template args (those explicitly specified and those deduced)
1750    are output in a newly created vector *TARGS_OUT.
1751
1752    If it is impossible to determine the result, an error message is
1753    issued.  The error_mark_node is returned to indicate failure.  */
1754
1755 static tree
1756 determine_specialization (tree template_id,
1757                           tree decl,
1758                           tree* targs_out,
1759                           int need_member_template,
1760                           int template_count,
1761                           tmpl_spec_kind tsk)
1762 {
1763   tree fns;
1764   tree targs;
1765   tree explicit_targs;
1766   tree candidates = NULL_TREE;
1767   /* A TREE_LIST of templates of which DECL may be a specialization.
1768      The TREE_VALUE of each node is a TEMPLATE_DECL.  The
1769      corresponding TREE_PURPOSE is the set of template arguments that,
1770      when used to instantiate the template, would produce a function
1771      with the signature of DECL.  */
1772   tree templates = NULL_TREE;
1773   int header_count;
1774   struct cp_binding_level *b;
1775
1776   *targs_out = NULL_TREE;
1777
1778   if (template_id == error_mark_node || decl == error_mark_node)
1779     return error_mark_node;
1780
1781   fns = TREE_OPERAND (template_id, 0);
1782   explicit_targs = TREE_OPERAND (template_id, 1);
1783
1784   if (fns == error_mark_node)
1785     return error_mark_node;
1786
1787   /* Check for baselinks.  */
1788   if (BASELINK_P (fns))
1789     fns = BASELINK_FUNCTIONS (fns);
1790
1791   if (!is_overloaded_fn (fns))
1792     {
1793       error ("%qD is not a function template", fns);
1794       return error_mark_node;
1795     }
1796
1797   /* Count the number of template headers specified for this
1798      specialization.  */
1799   header_count = 0;
1800   for (b = current_binding_level;
1801        b->kind == sk_template_parms;
1802        b = b->level_chain)
1803     ++header_count;
1804
1805   for (; fns; fns = OVL_NEXT (fns))
1806     {
1807       tree fn = OVL_CURRENT (fns);
1808
1809       if (TREE_CODE (fn) == TEMPLATE_DECL)
1810         {
1811           tree decl_arg_types;
1812           tree fn_arg_types;
1813
1814           /* In case of explicit specialization, we need to check if
1815              the number of template headers appearing in the specialization
1816              is correct. This is usually done in check_explicit_specialization,
1817              but the check done there cannot be exhaustive when specializing
1818              member functions. Consider the following code:
1819
1820              template <> void A<int>::f(int);
1821              template <> template <> void A<int>::f(int);
1822
1823              Assuming that A<int> is not itself an explicit specialization
1824              already, the first line specializes "f" which is a non-template
1825              member function, whilst the second line specializes "f" which
1826              is a template member function. So both lines are syntactically
1827              correct, and check_explicit_specialization does not reject
1828              them.
1829
1830              Here, we can do better, as we are matching the specialization
1831              against the declarations. We count the number of template
1832              headers, and we check if they match TEMPLATE_COUNT + 1
1833              (TEMPLATE_COUNT is the number of qualifying template classes,
1834              plus there must be another header for the member template
1835              itself).
1836
1837              Notice that if header_count is zero, this is not a
1838              specialization but rather a template instantiation, so there
1839              is no check we can perform here.  */
1840           if (header_count && header_count != template_count + 1)
1841             continue;
1842
1843           /* Check that the number of template arguments at the
1844              innermost level for DECL is the same as for FN.  */
1845           if (current_binding_level->kind == sk_template_parms
1846               && !current_binding_level->explicit_spec_p
1847               && (TREE_VEC_LENGTH (DECL_INNERMOST_TEMPLATE_PARMS (fn))
1848                   != TREE_VEC_LENGTH (INNERMOST_TEMPLATE_PARMS
1849                                       (current_template_parms))))
1850             continue;
1851
1852           /* DECL might be a specialization of FN.  */
1853           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1854           fn_arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
1855
1856           /* For a non-static member function, we need to make sure
1857              that the const qualification is the same.  Since
1858              get_bindings does not try to merge the "this" parameter,
1859              we must do the comparison explicitly.  */
1860           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (fn)
1861               && !same_type_p (TREE_VALUE (fn_arg_types),
1862                                TREE_VALUE (decl_arg_types)))
1863             continue;
1864
1865           /* Skip the "this" parameter and, for constructors of
1866              classes with virtual bases, the VTT parameter.  A
1867              full specialization of a constructor will have a VTT
1868              parameter, but a template never will.  */ 
1869           decl_arg_types 
1870             = skip_artificial_parms_for (decl, decl_arg_types);
1871           fn_arg_types 
1872             = skip_artificial_parms_for (fn, fn_arg_types);
1873
1874           /* Check that the number of function parameters matches.
1875              For example,
1876                template <class T> void f(int i = 0);
1877                template <> void f<int>();
1878              The specialization f<int> is invalid but is not caught
1879              by get_bindings below.  */
1880           if (list_length (fn_arg_types) != list_length (decl_arg_types))
1881             continue;
1882
1883           /* Function templates cannot be specializations; there are
1884              no partial specializations of functions.  Therefore, if
1885              the type of DECL does not match FN, there is no
1886              match.  */
1887           if (tsk == tsk_template)
1888             {
1889               if (compparms (fn_arg_types, decl_arg_types))
1890                 candidates = tree_cons (NULL_TREE, fn, candidates);
1891               continue;
1892             }
1893
1894           /* See whether this function might be a specialization of this
1895              template.  */
1896           targs = get_bindings (fn, decl, explicit_targs, /*check_ret=*/true);
1897
1898           if (!targs)
1899             /* We cannot deduce template arguments that when used to
1900                specialize TMPL will produce DECL.  */
1901             continue;
1902
1903           /* Save this template, and the arguments deduced.  */
1904           templates = tree_cons (targs, fn, templates);
1905         }
1906       else if (need_member_template)
1907         /* FN is an ordinary member function, and we need a
1908            specialization of a member template.  */
1909         ;
1910       else if (TREE_CODE (fn) != FUNCTION_DECL)
1911         /* We can get IDENTIFIER_NODEs here in certain erroneous
1912            cases.  */
1913         ;
1914       else if (!DECL_FUNCTION_MEMBER_P (fn))
1915         /* This is just an ordinary non-member function.  Nothing can
1916            be a specialization of that.  */
1917         ;
1918       else if (DECL_ARTIFICIAL (fn))
1919         /* Cannot specialize functions that are created implicitly.  */
1920         ;
1921       else
1922         {
1923           tree decl_arg_types;
1924
1925           /* This is an ordinary member function.  However, since
1926              we're here, we can assume it's enclosing class is a
1927              template class.  For example,
1928
1929                template <typename T> struct S { void f(); };
1930                template <> void S<int>::f() {}
1931
1932              Here, S<int>::f is a non-template, but S<int> is a
1933              template class.  If FN has the same type as DECL, we
1934              might be in business.  */
1935
1936           if (!DECL_TEMPLATE_INFO (fn))
1937             /* Its enclosing class is an explicit specialization
1938                of a template class.  This is not a candidate.  */
1939             continue;
1940
1941           if (!same_type_p (TREE_TYPE (TREE_TYPE (decl)),
1942                             TREE_TYPE (TREE_TYPE (fn))))
1943             /* The return types differ.  */
1944             continue;
1945
1946           /* Adjust the type of DECL in case FN is a static member.  */
1947           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1948           if (DECL_STATIC_FUNCTION_P (fn)
1949               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1950             decl_arg_types = TREE_CHAIN (decl_arg_types);
1951
1952           if (compparms (TYPE_ARG_TYPES (TREE_TYPE (fn)),
1953                          decl_arg_types))
1954             /* They match!  */
1955             candidates = tree_cons (NULL_TREE, fn, candidates);
1956         }
1957     }
1958
1959   if (templates && TREE_CHAIN (templates))
1960     {
1961       /* We have:
1962
1963            [temp.expl.spec]
1964
1965            It is possible for a specialization with a given function
1966            signature to be instantiated from more than one function
1967            template.  In such cases, explicit specification of the
1968            template arguments must be used to uniquely identify the
1969            function template specialization being specialized.
1970
1971          Note that here, there's no suggestion that we're supposed to
1972          determine which of the candidate templates is most
1973          specialized.  However, we, also have:
1974
1975            [temp.func.order]
1976
1977            Partial ordering of overloaded function template
1978            declarations is used in the following contexts to select
1979            the function template to which a function template
1980            specialization refers:
1981
1982            -- when an explicit specialization refers to a function
1983               template.
1984
1985          So, we do use the partial ordering rules, at least for now.
1986          This extension can only serve to make invalid programs valid,
1987          so it's safe.  And, there is strong anecdotal evidence that
1988          the committee intended the partial ordering rules to apply;
1989          the EDG front end has that behavior, and John Spicer claims
1990          that the committee simply forgot to delete the wording in
1991          [temp.expl.spec].  */
1992       tree tmpl = most_specialized_instantiation (templates);
1993       if (tmpl != error_mark_node)
1994         {
1995           templates = tmpl;
1996           TREE_CHAIN (templates) = NULL_TREE;
1997         }
1998     }
1999
2000   if (templates == NULL_TREE && candidates == NULL_TREE)
2001     {
2002       error ("template-id %qD for %q+D does not match any template "
2003              "declaration", template_id, decl);
2004       if (header_count && header_count != template_count + 1)
2005         inform (input_location, "saw %d %<template<>%>, need %d for "
2006                 "specializing a member function template",
2007                 header_count, template_count + 1);
2008       return error_mark_node;
2009     }
2010   else if ((templates && TREE_CHAIN (templates))
2011            || (candidates && TREE_CHAIN (candidates))
2012            || (templates && candidates))
2013     {
2014       error ("ambiguous template specialization %qD for %q+D",
2015              template_id, decl);
2016       candidates = chainon (candidates, templates);
2017       print_candidates (candidates);
2018       return error_mark_node;
2019     }
2020
2021   /* We have one, and exactly one, match.  */
2022   if (candidates)
2023     {
2024       tree fn = TREE_VALUE (candidates);
2025       *targs_out = copy_node (DECL_TI_ARGS (fn));
2026       /* DECL is a re-declaration or partial instantiation of a template
2027          function.  */
2028       if (TREE_CODE (fn) == TEMPLATE_DECL)
2029         return fn;
2030       /* It was a specialization of an ordinary member function in a
2031          template class.  */
2032       return DECL_TI_TEMPLATE (fn);
2033     }
2034
2035   /* It was a specialization of a template.  */
2036   targs = DECL_TI_ARGS (DECL_TEMPLATE_RESULT (TREE_VALUE (templates)));
2037   if (TMPL_ARGS_HAVE_MULTIPLE_LEVELS (targs))
2038     {
2039       *targs_out = copy_node (targs);
2040       SET_TMPL_ARGS_LEVEL (*targs_out,
2041                            TMPL_ARGS_DEPTH (*targs_out),
2042                            TREE_PURPOSE (templates));
2043     }
2044   else
2045     *targs_out = TREE_PURPOSE (templates);
2046   return TREE_VALUE (templates);
2047 }
2048
2049 /* Returns a chain of parameter types, exactly like the SPEC_TYPES,
2050    but with the default argument values filled in from those in the
2051    TMPL_TYPES.  */
2052
2053 static tree
2054 copy_default_args_to_explicit_spec_1 (tree spec_types,
2055                                       tree tmpl_types)
2056 {
2057   tree new_spec_types;
2058
2059   if (!spec_types)
2060     return NULL_TREE;
2061
2062   if (spec_types == void_list_node)
2063     return void_list_node;
2064
2065   /* Substitute into the rest of the list.  */
2066   new_spec_types =
2067     copy_default_args_to_explicit_spec_1 (TREE_CHAIN (spec_types),
2068                                           TREE_CHAIN (tmpl_types));
2069
2070   /* Add the default argument for this parameter.  */
2071   return hash_tree_cons (TREE_PURPOSE (tmpl_types),
2072                          TREE_VALUE (spec_types),
2073                          new_spec_types);
2074 }
2075
2076 /* DECL is an explicit specialization.  Replicate default arguments
2077    from the template it specializes.  (That way, code like:
2078
2079      template <class T> void f(T = 3);
2080      template <> void f(double);
2081      void g () { f (); }
2082
2083    works, as required.)  An alternative approach would be to look up
2084    the correct default arguments at the call-site, but this approach
2085    is consistent with how implicit instantiations are handled.  */
2086
2087 static void
2088 copy_default_args_to_explicit_spec (tree decl)
2089 {
2090   tree tmpl;
2091   tree spec_types;
2092   tree tmpl_types;
2093   tree new_spec_types;
2094   tree old_type;
2095   tree new_type;
2096   tree t;
2097   tree object_type = NULL_TREE;
2098   tree in_charge = NULL_TREE;
2099   tree vtt = NULL_TREE;
2100
2101   /* See if there's anything we need to do.  */
2102   tmpl = DECL_TI_TEMPLATE (decl);
2103   tmpl_types = TYPE_ARG_TYPES (TREE_TYPE (DECL_TEMPLATE_RESULT (tmpl)));
2104   for (t = tmpl_types; t; t = TREE_CHAIN (t))
2105     if (TREE_PURPOSE (t))
2106       break;
2107   if (!t)
2108     return;
2109
2110   old_type = TREE_TYPE (decl);
2111   spec_types = TYPE_ARG_TYPES (old_type);
2112
2113   if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2114     {
2115       /* Remove the this pointer, but remember the object's type for
2116          CV quals.  */
2117       object_type = TREE_TYPE (TREE_VALUE (spec_types));
2118       spec_types = TREE_CHAIN (spec_types);
2119       tmpl_types = TREE_CHAIN (tmpl_types);
2120
2121       if (DECL_HAS_IN_CHARGE_PARM_P (decl))
2122         {
2123           /* DECL may contain more parameters than TMPL due to the extra
2124              in-charge parameter in constructors and destructors.  */
2125           in_charge = spec_types;
2126           spec_types = TREE_CHAIN (spec_types);
2127         }
2128       if (DECL_HAS_VTT_PARM_P (decl))
2129         {
2130           vtt = spec_types;
2131           spec_types = TREE_CHAIN (spec_types);
2132         }
2133     }
2134
2135   /* Compute the merged default arguments.  */
2136   new_spec_types =
2137     copy_default_args_to_explicit_spec_1 (spec_types, tmpl_types);
2138
2139   /* Compute the new FUNCTION_TYPE.  */
2140   if (object_type)
2141     {
2142       if (vtt)
2143         new_spec_types = hash_tree_cons (TREE_PURPOSE (vtt),
2144                                          TREE_VALUE (vtt),
2145                                          new_spec_types);
2146
2147       if (in_charge)
2148         /* Put the in-charge parameter back.  */
2149         new_spec_types = hash_tree_cons (TREE_PURPOSE (in_charge),
2150                                          TREE_VALUE (in_charge),
2151                                          new_spec_types);
2152
2153       new_type = build_method_type_directly (object_type,
2154                                              TREE_TYPE (old_type),
2155                                              new_spec_types);
2156     }
2157   else
2158     new_type = build_function_type (TREE_TYPE (old_type),
2159                                     new_spec_types);
2160   new_type = cp_build_type_attribute_variant (new_type,
2161                                               TYPE_ATTRIBUTES (old_type));
2162   new_type = build_exception_variant (new_type,
2163                                       TYPE_RAISES_EXCEPTIONS (old_type));
2164   TREE_TYPE (decl) = new_type;
2165 }
2166
2167 /* Check to see if the function just declared, as indicated in
2168    DECLARATOR, and in DECL, is a specialization of a function
2169    template.  We may also discover that the declaration is an explicit
2170    instantiation at this point.
2171
2172    Returns DECL, or an equivalent declaration that should be used
2173    instead if all goes well.  Issues an error message if something is
2174    amiss.  Returns error_mark_node if the error is not easily
2175    recoverable.
2176
2177    FLAGS is a bitmask consisting of the following flags:
2178
2179    2: The function has a definition.
2180    4: The function is a friend.
2181
2182    The TEMPLATE_COUNT is the number of references to qualifying
2183    template classes that appeared in the name of the function.  For
2184    example, in
2185
2186      template <class T> struct S { void f(); };
2187      void S<int>::f();
2188
2189    the TEMPLATE_COUNT would be 1.  However, explicitly specialized
2190    classes are not counted in the TEMPLATE_COUNT, so that in
2191
2192      template <class T> struct S {};
2193      template <> struct S<int> { void f(); }
2194      template <> void S<int>::f();
2195
2196    the TEMPLATE_COUNT would be 0.  (Note that this declaration is
2197    invalid; there should be no template <>.)
2198
2199    If the function is a specialization, it is marked as such via
2200    DECL_TEMPLATE_SPECIALIZATION.  Furthermore, its DECL_TEMPLATE_INFO
2201    is set up correctly, and it is added to the list of specializations
2202    for that template.  */
2203
2204 tree
2205 check_explicit_specialization (tree declarator,
2206                                tree decl,
2207                                int template_count,
2208                                int flags)
2209 {
2210   int have_def = flags & 2;
2211   int is_friend = flags & 4;
2212   int specialization = 0;
2213   int explicit_instantiation = 0;
2214   int member_specialization = 0;
2215   tree ctype = DECL_CLASS_CONTEXT (decl);
2216   tree dname = DECL_NAME (decl);
2217   tmpl_spec_kind tsk;
2218
2219   if (is_friend)
2220     {
2221       if (!processing_specialization)
2222         tsk = tsk_none;
2223       else
2224         tsk = tsk_excessive_parms;
2225     }
2226   else
2227     tsk = current_tmpl_spec_kind (template_count);
2228
2229   switch (tsk)
2230     {
2231     case tsk_none:
2232       if (processing_specialization)
2233         {
2234           specialization = 1;
2235           SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2236         }
2237       else if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2238         {
2239           if (is_friend)
2240             /* This could be something like:
2241
2242                template <class T> void f(T);
2243                class S { friend void f<>(int); }  */
2244             specialization = 1;
2245           else
2246             {
2247               /* This case handles bogus declarations like template <>
2248                  template <class T> void f<int>(); */
2249
2250               error ("template-id %qD in declaration of primary template",
2251                      declarator);
2252               return decl;
2253             }
2254         }
2255       break;
2256
2257     case tsk_invalid_member_spec:
2258       /* The error has already been reported in
2259          check_specialization_scope.  */
2260       return error_mark_node;
2261
2262     case tsk_invalid_expl_inst:
2263       error ("template parameter list used in explicit instantiation");
2264
2265       /* Fall through.  */
2266
2267     case tsk_expl_inst:
2268       if (have_def)
2269         error ("definition provided for explicit instantiation");
2270
2271       explicit_instantiation = 1;
2272       break;
2273
2274     case tsk_excessive_parms:
2275     case tsk_insufficient_parms:
2276       if (tsk == tsk_excessive_parms)
2277         error ("too many template parameter lists in declaration of %qD",
2278                decl);
2279       else if (template_header_count)
2280         error("too few template parameter lists in declaration of %qD", decl);
2281       else
2282         error("explicit specialization of %qD must be introduced by "
2283               "%<template <>%>", decl);
2284
2285       /* Fall through.  */
2286     case tsk_expl_spec:
2287       SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2288       if (ctype)
2289         member_specialization = 1;
2290       else
2291         specialization = 1;
2292       break;
2293
2294     case tsk_template:
2295       if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2296         {
2297           /* This case handles bogus declarations like template <>
2298              template <class T> void f<int>(); */
2299
2300           if (uses_template_parms (declarator))
2301             error ("function template partial specialization %qD "
2302                    "is not allowed", declarator);
2303           else
2304             error ("template-id %qD in declaration of primary template",
2305                    declarator);
2306           return decl;
2307         }
2308
2309       if (ctype && CLASSTYPE_TEMPLATE_INSTANTIATION (ctype))
2310         /* This is a specialization of a member template, without
2311            specialization the containing class.  Something like:
2312
2313              template <class T> struct S {
2314                template <class U> void f (U);
2315              };
2316              template <> template <class U> void S<int>::f(U) {}
2317
2318            That's a specialization -- but of the entire template.  */
2319         specialization = 1;
2320       break;
2321
2322     default:
2323       gcc_unreachable ();
2324     }
2325
2326   if (specialization || member_specialization)
2327     {
2328       tree t = TYPE_ARG_TYPES (TREE_TYPE (decl));
2329       for (; t; t = TREE_CHAIN (t))
2330         if (TREE_PURPOSE (t))
2331           {
2332             permerror (input_location, 
2333                        "default argument specified in explicit specialization");
2334             break;
2335           }
2336     }
2337
2338   if (specialization || member_specialization || explicit_instantiation)
2339     {
2340       tree tmpl = NULL_TREE;
2341       tree targs = NULL_TREE;
2342
2343       /* Make sure that the declarator is a TEMPLATE_ID_EXPR.  */
2344       if (TREE_CODE (declarator) != TEMPLATE_ID_EXPR)
2345         {
2346           tree fns;
2347
2348           gcc_assert (TREE_CODE (declarator) == IDENTIFIER_NODE);
2349           if (ctype)
2350             fns = dname;
2351           else
2352             {
2353               /* If there is no class context, the explicit instantiation
2354                  must be at namespace scope.  */
2355               gcc_assert (DECL_NAMESPACE_SCOPE_P (decl));
2356
2357               /* Find the namespace binding, using the declaration
2358                  context.  */
2359               fns = lookup_qualified_name (CP_DECL_CONTEXT (decl), dname,
2360                                            false, true);
2361               if (fns == error_mark_node || !is_overloaded_fn (fns))
2362                 {
2363                   error ("%qD is not a template function", dname);
2364                   fns = error_mark_node;
2365                 }
2366               else
2367                 {
2368                   tree fn = OVL_CURRENT (fns);
2369                   if (!is_associated_namespace (CP_DECL_CONTEXT (decl),
2370                                                 CP_DECL_CONTEXT (fn)))
2371                     error ("%qD is not declared in %qD",
2372                            decl, current_namespace);
2373                 }
2374             }
2375
2376           declarator = lookup_template_function (fns, NULL_TREE);
2377         }
2378
2379       if (declarator == error_mark_node)
2380         return error_mark_node;
2381
2382       if (ctype != NULL_TREE && TYPE_BEING_DEFINED (ctype))
2383         {
2384           if (!explicit_instantiation)
2385             /* A specialization in class scope.  This is invalid,
2386                but the error will already have been flagged by
2387                check_specialization_scope.  */
2388             return error_mark_node;
2389           else
2390             {
2391               /* It's not valid to write an explicit instantiation in
2392                  class scope, e.g.:
2393
2394                    class C { template void f(); }
2395
2396                    This case is caught by the parser.  However, on
2397                    something like:
2398
2399                    template class C { void f(); };
2400
2401                    (which is invalid) we can get here.  The error will be
2402                    issued later.  */
2403               ;
2404             }
2405
2406           return decl;
2407         }
2408       else if (ctype != NULL_TREE
2409                && (TREE_CODE (TREE_OPERAND (declarator, 0)) ==
2410                    IDENTIFIER_NODE))
2411         {
2412           /* Find the list of functions in ctype that have the same
2413              name as the declared function.  */
2414           tree name = TREE_OPERAND (declarator, 0);
2415           tree fns = NULL_TREE;
2416           int idx;
2417
2418           if (constructor_name_p (name, ctype))
2419             {
2420               int is_constructor = DECL_CONSTRUCTOR_P (decl);
2421
2422               if (is_constructor ? !TYPE_HAS_USER_CONSTRUCTOR (ctype)
2423                   : !CLASSTYPE_DESTRUCTORS (ctype))
2424                 {
2425                   /* From [temp.expl.spec]:
2426
2427                      If such an explicit specialization for the member
2428                      of a class template names an implicitly-declared
2429                      special member function (clause _special_), the
2430                      program is ill-formed.
2431
2432                      Similar language is found in [temp.explicit].  */
2433                   error ("specialization of implicitly-declared special member function");
2434                   return error_mark_node;
2435                 }
2436
2437               name = is_constructor ? ctor_identifier : dtor_identifier;
2438             }
2439
2440           if (!DECL_CONV_FN_P (decl))
2441             {
2442               idx = lookup_fnfields_1 (ctype, name);
2443               if (idx >= 0)
2444                 fns = VEC_index (tree, CLASSTYPE_METHOD_VEC (ctype), idx);
2445             }
2446           else
2447             {
2448               VEC(tree,gc) *methods;
2449               tree ovl;
2450
2451               /* For a type-conversion operator, we cannot do a
2452                  name-based lookup.  We might be looking for `operator
2453                  int' which will be a specialization of `operator T'.
2454                  So, we find *all* the conversion operators, and then
2455                  select from them.  */
2456               fns = NULL_TREE;
2457
2458               methods = CLASSTYPE_METHOD_VEC (ctype);
2459               if (methods)
2460                 for (idx = CLASSTYPE_FIRST_CONVERSION_SLOT;
2461                      VEC_iterate (tree, methods, idx, ovl);
2462                      ++idx)
2463                   {
2464                     if (!DECL_CONV_FN_P (OVL_CURRENT (ovl)))
2465                       /* There are no more conversion functions.  */
2466                       break;
2467
2468                     /* Glue all these conversion functions together
2469                        with those we already have.  */
2470                     for (; ovl; ovl = OVL_NEXT (ovl))
2471                       fns = ovl_cons (OVL_CURRENT (ovl), fns);
2472                   }
2473             }
2474
2475           if (fns == NULL_TREE)
2476             {
2477               error ("no member function %qD declared in %qT", name, ctype);
2478               return error_mark_node;
2479             }
2480           else
2481             TREE_OPERAND (declarator, 0) = fns;
2482         }
2483
2484       /* Figure out what exactly is being specialized at this point.
2485          Note that for an explicit instantiation, even one for a
2486          member function, we cannot tell apriori whether the
2487          instantiation is for a member template, or just a member
2488          function of a template class.  Even if a member template is
2489          being instantiated, the member template arguments may be
2490          elided if they can be deduced from the rest of the
2491          declaration.  */
2492       tmpl = determine_specialization (declarator, decl,
2493                                        &targs,
2494                                        member_specialization,
2495                                        template_count,
2496                                        tsk);
2497
2498       if (!tmpl || tmpl == error_mark_node)
2499         /* We couldn't figure out what this declaration was
2500            specializing.  */
2501         return error_mark_node;
2502       else
2503         {
2504           tree gen_tmpl = most_general_template (tmpl);
2505
2506           if (explicit_instantiation)
2507             {
2508               /* We don't set DECL_EXPLICIT_INSTANTIATION here; that
2509                  is done by do_decl_instantiation later.  */
2510
2511               int arg_depth = TMPL_ARGS_DEPTH (targs);
2512               int parm_depth = TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl));
2513
2514               if (arg_depth > parm_depth)
2515                 {
2516                   /* If TMPL is not the most general template (for
2517                      example, if TMPL is a friend template that is
2518                      injected into namespace scope), then there will
2519                      be too many levels of TARGS.  Remove some of them
2520                      here.  */
2521                   int i;
2522                   tree new_targs;
2523
2524                   new_targs = make_tree_vec (parm_depth);
2525                   for (i = arg_depth - parm_depth; i < arg_depth; ++i)
2526                     TREE_VEC_ELT (new_targs, i - (arg_depth - parm_depth))
2527                       = TREE_VEC_ELT (targs, i);
2528                   targs = new_targs;
2529                 }
2530
2531               return instantiate_template (tmpl, targs, tf_error);
2532             }
2533
2534           /* If we thought that the DECL was a member function, but it
2535              turns out to be specializing a static member function,
2536              make DECL a static member function as well.  */
2537           if (DECL_STATIC_FUNCTION_P (tmpl)
2538               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2539             revert_static_member_fn (decl);
2540
2541           /* If this is a specialization of a member template of a
2542              template class, we want to return the TEMPLATE_DECL, not
2543              the specialization of it.  */
2544           if (tsk == tsk_template)
2545             {
2546               tree result = DECL_TEMPLATE_RESULT (tmpl);
2547               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
2548               DECL_INITIAL (result) = NULL_TREE;
2549               if (have_def)
2550                 {
2551                   tree parm;
2552                   DECL_SOURCE_LOCATION (tmpl) = DECL_SOURCE_LOCATION (decl);
2553                   DECL_SOURCE_LOCATION (result)
2554                     = DECL_SOURCE_LOCATION (decl);
2555                   /* We want to use the argument list specified in the
2556                      definition, not in the original declaration.  */
2557                   DECL_ARGUMENTS (result) = DECL_ARGUMENTS (decl);
2558                   for (parm = DECL_ARGUMENTS (result); parm;
2559                        parm = TREE_CHAIN (parm))
2560                     DECL_CONTEXT (parm) = result;
2561                 }
2562               return register_specialization (tmpl, gen_tmpl, targs,
2563                                               is_friend, 0);
2564             }
2565
2566           /* Set up the DECL_TEMPLATE_INFO for DECL.  */
2567           DECL_TEMPLATE_INFO (decl) = build_template_info (tmpl, targs);
2568
2569           /* Inherit default function arguments from the template
2570              DECL is specializing.  */
2571           copy_default_args_to_explicit_spec (decl);
2572
2573           /* This specialization has the same protection as the
2574              template it specializes.  */
2575           TREE_PRIVATE (decl) = TREE_PRIVATE (gen_tmpl);
2576           TREE_PROTECTED (decl) = TREE_PROTECTED (gen_tmpl);
2577
2578           /* 7.1.1-1 [dcl.stc]
2579
2580              A storage-class-specifier shall not be specified in an
2581              explicit specialization...
2582
2583              The parser rejects these, so unless action is taken here,
2584              explicit function specializations will always appear with
2585              global linkage.
2586
2587              The action recommended by the C++ CWG in response to C++
2588              defect report 605 is to make the storage class and linkage
2589              of the explicit specialization match the templated function:
2590
2591              http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#605
2592            */
2593           if (tsk == tsk_expl_spec && DECL_FUNCTION_TEMPLATE_P (gen_tmpl))
2594             {
2595               tree tmpl_func = DECL_TEMPLATE_RESULT (gen_tmpl);
2596               gcc_assert (TREE_CODE (tmpl_func) == FUNCTION_DECL);
2597
2598               /* This specialization has the same linkage and visibility as
2599                  the function template it specializes.  */
2600               TREE_PUBLIC (decl) = TREE_PUBLIC (tmpl_func);
2601               if (! TREE_PUBLIC (decl))
2602                 {
2603                   DECL_INTERFACE_KNOWN (decl) = 1;
2604                   DECL_NOT_REALLY_EXTERN (decl) = 1;
2605                 }
2606               DECL_THIS_STATIC (decl) = DECL_THIS_STATIC (tmpl_func);
2607               if (DECL_VISIBILITY_SPECIFIED (tmpl_func))
2608                 {
2609                   DECL_VISIBILITY_SPECIFIED (decl) = 1;
2610                   DECL_VISIBILITY (decl) = DECL_VISIBILITY (tmpl_func);
2611                 }
2612             }
2613
2614           /* If DECL is a friend declaration, declared using an
2615              unqualified name, the namespace associated with DECL may
2616              have been set incorrectly.  For example, in:
2617
2618                template <typename T> void f(T);
2619                namespace N {
2620                  struct S { friend void f<int>(int); }
2621                }
2622
2623              we will have set the DECL_CONTEXT for the friend
2624              declaration to N, rather than to the global namespace.  */
2625           if (DECL_NAMESPACE_SCOPE_P (decl))
2626             DECL_CONTEXT (decl) = DECL_CONTEXT (tmpl);
2627
2628           if (is_friend && !have_def)
2629             /* This is not really a declaration of a specialization.
2630                It's just the name of an instantiation.  But, it's not
2631                a request for an instantiation, either.  */
2632             SET_DECL_IMPLICIT_INSTANTIATION (decl);
2633           else if (DECL_CONSTRUCTOR_P (decl) || DECL_DESTRUCTOR_P (decl))
2634             /* This is indeed a specialization.  In case of constructors
2635                and destructors, we need in-charge and not-in-charge
2636                versions in V3 ABI.  */
2637             clone_function_decl (decl, /*update_method_vec_p=*/0);
2638
2639           /* Register this specialization so that we can find it
2640              again.  */
2641           decl = register_specialization (decl, gen_tmpl, targs, is_friend, 0);
2642         }
2643     }
2644
2645   return decl;
2646 }
2647
2648 /* Returns 1 iff PARMS1 and PARMS2 are identical sets of template
2649    parameters.  These are represented in the same format used for
2650    DECL_TEMPLATE_PARMS.  */
2651
2652 int
2653 comp_template_parms (const_tree parms1, const_tree parms2)
2654 {
2655   const_tree p1;
2656   const_tree p2;
2657
2658   if (parms1 == parms2)
2659     return 1;
2660
2661   for (p1 = parms1, p2 = parms2;
2662        p1 != NULL_TREE && p2 != NULL_TREE;
2663        p1 = TREE_CHAIN (p1), p2 = TREE_CHAIN (p2))
2664     {
2665       tree t1 = TREE_VALUE (p1);
2666       tree t2 = TREE_VALUE (p2);
2667       int i;
2668
2669       gcc_assert (TREE_CODE (t1) == TREE_VEC);
2670       gcc_assert (TREE_CODE (t2) == TREE_VEC);
2671
2672       if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2673         return 0;
2674
2675       for (i = 0; i < TREE_VEC_LENGTH (t2); ++i)
2676         {
2677           tree parm1 = TREE_VALUE (TREE_VEC_ELT (t1, i));
2678           tree parm2 = TREE_VALUE (TREE_VEC_ELT (t2, i));
2679
2680           /* If either of the template parameters are invalid, assume
2681              they match for the sake of error recovery. */
2682           if (parm1 == error_mark_node || parm2 == error_mark_node)
2683             return 1;
2684
2685           if (TREE_CODE (parm1) != TREE_CODE (parm2))
2686             return 0;
2687
2688           if (TREE_CODE (parm1) == TEMPLATE_TYPE_PARM
2689               && (TEMPLATE_TYPE_PARAMETER_PACK (parm1)
2690                   == TEMPLATE_TYPE_PARAMETER_PACK (parm2)))
2691             continue;
2692           else if (!same_type_p (TREE_TYPE (parm1), TREE_TYPE (parm2)))
2693             return 0;
2694         }
2695     }
2696
2697   if ((p1 != NULL_TREE) != (p2 != NULL_TREE))
2698     /* One set of parameters has more parameters lists than the
2699        other.  */
2700     return 0;
2701
2702   return 1;
2703 }
2704
2705 /* Determine whether PARM is a parameter pack.  */
2706
2707 bool 
2708 template_parameter_pack_p (const_tree parm)
2709 {
2710   /* Determine if we have a non-type template parameter pack.  */
2711   if (TREE_CODE (parm) == PARM_DECL)
2712     return (DECL_TEMPLATE_PARM_P (parm) 
2713             && TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)));
2714
2715   /* If this is a list of template parameters, we could get a
2716      TYPE_DECL or a TEMPLATE_DECL.  */ 
2717   if (TREE_CODE (parm) == TYPE_DECL || TREE_CODE (parm) == TEMPLATE_DECL)
2718     parm = TREE_TYPE (parm);
2719
2720   return ((TREE_CODE (parm) == TEMPLATE_TYPE_PARM
2721            || TREE_CODE (parm) == TEMPLATE_TEMPLATE_PARM)
2722           && TEMPLATE_TYPE_PARAMETER_PACK (parm));
2723 }
2724
2725 /* Determine if T is a function parameter pack.  */
2726
2727 bool
2728 function_parameter_pack_p (const_tree t)
2729 {
2730   if (t && TREE_CODE (t) == PARM_DECL)
2731     return FUNCTION_PARAMETER_PACK_P (t);
2732   return false;
2733 }
2734
2735 /* Return the function template declaration of PRIMARY_FUNC_TMPL_INST.
2736    PRIMARY_FUNC_TMPL_INST is a primary function template instantiation.  */
2737
2738 tree
2739 get_function_template_decl (const_tree primary_func_tmpl_inst)
2740 {
2741   if (! primary_func_tmpl_inst
2742       || TREE_CODE (primary_func_tmpl_inst) != FUNCTION_DECL
2743       || ! primary_template_instantiation_p (primary_func_tmpl_inst))
2744     return NULL;
2745
2746   return DECL_TEMPLATE_RESULT (DECL_TI_TEMPLATE (primary_func_tmpl_inst));
2747 }
2748
2749 /* Return true iff the function parameter PARAM_DECL was expanded
2750    from the function parameter pack PACK.  */
2751
2752 bool
2753 function_parameter_expanded_from_pack_p (tree param_decl, tree pack)
2754 {
2755   if (DECL_ARTIFICIAL (param_decl)
2756       || !function_parameter_pack_p (pack))
2757     return false;
2758
2759   /* The parameter pack and its pack arguments have the same
2760      DECL_PARM_INDEX.  */
2761   return DECL_PARM_INDEX (pack) == DECL_PARM_INDEX (param_decl);
2762 }
2763
2764 /* Determine whether ARGS describes a variadic template args list,
2765    i.e., one that is terminated by a template argument pack.  */
2766
2767 static bool 
2768 template_args_variadic_p (tree args)
2769 {
2770   int nargs;
2771   tree last_parm;
2772
2773   if (args == NULL_TREE)
2774     return false;
2775
2776   args = INNERMOST_TEMPLATE_ARGS (args);
2777   nargs = TREE_VEC_LENGTH (args);
2778
2779   if (nargs == 0)
2780     return false;
2781
2782   last_parm = TREE_VEC_ELT (args, nargs - 1);
2783
2784   return ARGUMENT_PACK_P (last_parm);
2785 }
2786
2787 /* Generate a new name for the parameter pack name NAME (an
2788    IDENTIFIER_NODE) that incorporates its */
2789
2790 static tree
2791 make_ith_pack_parameter_name (tree name, int i)
2792 {
2793   /* Munge the name to include the parameter index.  */
2794 #define NUMBUF_LEN 128
2795   char numbuf[NUMBUF_LEN];
2796   char* newname;
2797   int newname_len;
2798
2799   snprintf (numbuf, NUMBUF_LEN, "%i", i);
2800   newname_len = IDENTIFIER_LENGTH (name)
2801                 + strlen (numbuf) + 2;
2802   newname = (char*)alloca (newname_len);
2803   snprintf (newname, newname_len,
2804             "%s#%i", IDENTIFIER_POINTER (name), i);
2805   return get_identifier (newname);
2806 }
2807
2808 /* Return true if T is a primary function
2809    or class template instantiation.  */
2810
2811 bool
2812 primary_template_instantiation_p (const_tree t)
2813 {
2814   if (!t)
2815     return false;
2816
2817   if (TREE_CODE (t) == FUNCTION_DECL)
2818     return DECL_LANG_SPECIFIC (t)
2819            && DECL_TEMPLATE_INSTANTIATION (t)
2820            && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (t));
2821   else if (CLASS_TYPE_P (t))
2822     return CLASSTYPE_TEMPLATE_INSTANTIATION (t)
2823            && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (t));
2824   return false;
2825 }
2826
2827 /* Return true if PARM is a template template parameter.  */
2828
2829 bool
2830 template_template_parameter_p (const_tree parm)
2831 {
2832   return DECL_TEMPLATE_TEMPLATE_PARM_P (parm);
2833 }
2834
2835 /* Return the template parameters of T if T is a
2836    primary template instantiation, NULL otherwise.  */
2837
2838 tree
2839 get_primary_template_innermost_parameters (const_tree t)
2840 {
2841   tree parms = NULL, template_info = NULL;
2842
2843   if ((template_info = get_template_info (t))
2844       && primary_template_instantiation_p (t))
2845     parms = INNERMOST_TEMPLATE_PARMS
2846         (DECL_TEMPLATE_PARMS (TI_TEMPLATE (template_info)));
2847
2848   return parms;
2849 }
2850
2851 /* Return the template parameters of the LEVELth level from the full list
2852    of template parameters PARMS.  */
2853
2854 tree
2855 get_template_parms_at_level (tree parms, int level)
2856 {
2857   tree p;
2858   if (!parms
2859       || TREE_CODE (parms) != TREE_LIST
2860       || level > TMPL_PARMS_DEPTH (parms))
2861     return NULL_TREE;
2862
2863   for (p = parms; p; p = TREE_CHAIN (p))
2864     if (TMPL_PARMS_DEPTH (p) == level)
2865       return p;
2866
2867   return NULL_TREE;
2868 }
2869
2870 /* Returns the template arguments of T if T is a template instantiation,
2871    NULL otherwise.  */
2872
2873 tree
2874 get_template_innermost_arguments (const_tree t)
2875 {
2876   tree args = NULL, template_info = NULL;
2877
2878   if ((template_info = get_template_info (t))
2879       && TI_ARGS (template_info))
2880     args = INNERMOST_TEMPLATE_ARGS (TI_ARGS (template_info));
2881
2882   return args;
2883 }
2884
2885 /* Return the argument pack elements of T if T is a template argument pack,
2886    NULL otherwise.  */
2887
2888 tree
2889 get_template_argument_pack_elems (const_tree t)
2890 {
2891   if (TREE_CODE (t) != TYPE_ARGUMENT_PACK
2892       && TREE_CODE (t) != NONTYPE_ARGUMENT_PACK)
2893     return NULL;
2894
2895   return ARGUMENT_PACK_ARGS (t);
2896 }
2897
2898 /* Structure used to track the progress of find_parameter_packs_r.  */
2899 struct find_parameter_pack_data 
2900 {
2901   /* TREE_LIST that will contain all of the parameter packs found by
2902      the traversal.  */
2903   tree* parameter_packs;
2904
2905   /* Set of AST nodes that have been visited by the traversal.  */
2906   struct pointer_set_t *visited;
2907 };
2908
2909 /* Identifies all of the argument packs that occur in a template
2910    argument and appends them to the TREE_LIST inside DATA, which is a
2911    find_parameter_pack_data structure. This is a subroutine of
2912    make_pack_expansion and uses_parameter_packs.  */
2913 static tree
2914 find_parameter_packs_r (tree *tp, int *walk_subtrees, void* data)
2915 {
2916   tree t = *tp;
2917   struct find_parameter_pack_data* ppd = 
2918     (struct find_parameter_pack_data*)data;
2919   bool parameter_pack_p = false;
2920
2921   /* Identify whether this is a parameter pack or not.  */
2922   switch (TREE_CODE (t))
2923     {
2924     case TEMPLATE_PARM_INDEX:
2925       if (TEMPLATE_PARM_PARAMETER_PACK (t))
2926         parameter_pack_p = true;
2927       break;
2928
2929     case TEMPLATE_TYPE_PARM:
2930     case TEMPLATE_TEMPLATE_PARM:
2931       if (TEMPLATE_TYPE_PARAMETER_PACK (t))
2932         parameter_pack_p = true;
2933       break;
2934
2935     case PARM_DECL:
2936       if (FUNCTION_PARAMETER_PACK_P (t))
2937         {
2938           /* We don't want to walk into the type of a PARM_DECL,
2939              because we don't want to see the type parameter pack.  */
2940           *walk_subtrees = 0;
2941           parameter_pack_p = true;
2942         }
2943       break;
2944
2945     default:
2946       /* Not a parameter pack.  */
2947       break;
2948     }
2949
2950   if (parameter_pack_p)
2951     {
2952       /* Add this parameter pack to the list.  */
2953       *ppd->parameter_packs = tree_cons (NULL_TREE, t, *ppd->parameter_packs);
2954     }
2955
2956   if (TYPE_P (t))
2957     cp_walk_tree (&TYPE_CONTEXT (t), 
2958                   &find_parameter_packs_r, ppd, ppd->visited);
2959
2960   /* This switch statement will return immediately if we don't find a
2961      parameter pack.  */
2962   switch (TREE_CODE (t)) 
2963     {
2964     case TEMPLATE_PARM_INDEX:
2965       return NULL_TREE;
2966
2967     case BOUND_TEMPLATE_TEMPLATE_PARM:
2968       /* Check the template itself.  */
2969       cp_walk_tree (&TREE_TYPE (TYPE_TI_TEMPLATE (t)), 
2970                     &find_parameter_packs_r, ppd, ppd->visited);
2971       /* Check the template arguments.  */
2972       cp_walk_tree (&TYPE_TI_ARGS (t), &find_parameter_packs_r, ppd, 
2973                     ppd->visited);
2974       *walk_subtrees = 0;
2975       return NULL_TREE;
2976
2977     case TEMPLATE_TYPE_PARM:
2978     case TEMPLATE_TEMPLATE_PARM:
2979       return NULL_TREE;
2980
2981     case PARM_DECL:
2982       return NULL_TREE;
2983
2984     case RECORD_TYPE:
2985       if (TYPE_PTRMEMFUNC_P (t))
2986         return NULL_TREE;
2987       /* Fall through.  */
2988
2989     case UNION_TYPE:
2990     case ENUMERAL_TYPE:
2991       if (TYPE_TEMPLATE_INFO (t))
2992         cp_walk_tree (&TI_ARGS (TYPE_TEMPLATE_INFO (t)),
2993                       &find_parameter_packs_r, ppd, ppd->visited);
2994
2995       *walk_subtrees = 0;
2996       return NULL_TREE;
2997
2998     case TEMPLATE_DECL:
2999       cp_walk_tree (&TREE_TYPE (t),
3000                     &find_parameter_packs_r, ppd, ppd->visited);
3001       return NULL_TREE;
3002  
3003     case TYPENAME_TYPE:
3004       cp_walk_tree (&TYPENAME_TYPE_FULLNAME (t), &find_parameter_packs_r,
3005                    ppd, ppd->visited);
3006       *walk_subtrees = 0;
3007       return NULL_TREE;
3008       
3009     case TYPE_PACK_EXPANSION:
3010     case EXPR_PACK_EXPANSION:
3011       *walk_subtrees = 0;
3012       return NULL_TREE;
3013
3014     case INTEGER_TYPE:
3015       cp_walk_tree (&TYPE_MAX_VALUE (t), &find_parameter_packs_r, 
3016                     ppd, ppd->visited);
3017       *walk_subtrees = 0;
3018       return NULL_TREE;
3019
3020     case IDENTIFIER_NODE:
3021       cp_walk_tree (&TREE_TYPE (t), &find_parameter_packs_r, ppd, 
3022                     ppd->visited);
3023       *walk_subtrees = 0;
3024       return NULL_TREE;
3025
3026     default:
3027       return NULL_TREE;
3028     }
3029
3030   return NULL_TREE;
3031 }
3032
3033 /* Determines if the expression or type T uses any parameter packs.  */
3034 bool
3035 uses_parameter_packs (tree t)
3036 {
3037   tree parameter_packs = NULL_TREE;
3038   struct find_parameter_pack_data ppd;
3039   ppd.parameter_packs = &parameter_packs;
3040   ppd.visited = pointer_set_create ();
3041   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3042   pointer_set_destroy (ppd.visited);
3043   return parameter_packs != NULL_TREE;
3044 }
3045
3046 /* Turn ARG, which may be an expression, type, or a TREE_LIST
3047    representation a base-class initializer into a parameter pack
3048    expansion. If all goes well, the resulting node will be an
3049    EXPR_PACK_EXPANSION, TYPE_PACK_EXPANSION, or TREE_LIST,
3050    respectively.  */
3051 tree 
3052 make_pack_expansion (tree arg)
3053 {
3054   tree result;
3055   tree parameter_packs = NULL_TREE;
3056   bool for_types = false;
3057   struct find_parameter_pack_data ppd;
3058
3059   if (!arg || arg == error_mark_node)
3060     return arg;
3061
3062   if (TREE_CODE (arg) == TREE_LIST)
3063     {
3064       /* The only time we will see a TREE_LIST here is for a base
3065          class initializer.  In this case, the TREE_PURPOSE will be a
3066          _TYPE node (representing the base class expansion we're
3067          initializing) and the TREE_VALUE will be a TREE_LIST
3068          containing the initialization arguments. 
3069
3070          The resulting expansion looks somewhat different from most
3071          expansions. Rather than returning just one _EXPANSION, we
3072          return a TREE_LIST whose TREE_PURPOSE is a
3073          TYPE_PACK_EXPANSION containing the bases that will be
3074          initialized.  The TREE_VALUE will be identical to the
3075          original TREE_VALUE, which is a list of arguments that will
3076          be passed to each base.  We do not introduce any new pack
3077          expansion nodes into the TREE_VALUE (although it is possible
3078          that some already exist), because the TREE_PURPOSE and
3079          TREE_VALUE all need to be expanded together with the same
3080          _EXPANSION node.  Note that the TYPE_PACK_EXPANSION in the
3081          resulting TREE_PURPOSE will mention the parameter packs in
3082          both the bases and the arguments to the bases.  */
3083       tree purpose;
3084       tree value;
3085       tree parameter_packs = NULL_TREE;
3086
3087       /* Determine which parameter packs will be used by the base
3088          class expansion.  */
3089       ppd.visited = pointer_set_create ();
3090       ppd.parameter_packs = &parameter_packs;
3091       cp_walk_tree (&TREE_PURPOSE (arg), &find_parameter_packs_r, 
3092                     &ppd, ppd.visited);
3093
3094       if (parameter_packs == NULL_TREE)
3095         {
3096           error ("base initializer expansion %<%T%> contains no parameter packs", arg);
3097           pointer_set_destroy (ppd.visited);
3098           return error_mark_node;
3099         }
3100
3101       if (TREE_VALUE (arg) != void_type_node)
3102         {
3103           /* Collect the sets of parameter packs used in each of the
3104              initialization arguments.  */
3105           for (value = TREE_VALUE (arg); value; value = TREE_CHAIN (value))
3106             {
3107               /* Determine which parameter packs will be expanded in this
3108                  argument.  */
3109               cp_walk_tree (&TREE_VALUE (value), &find_parameter_packs_r, 
3110                             &ppd, ppd.visited);
3111             }
3112         }
3113
3114       pointer_set_destroy (ppd.visited);
3115
3116       /* Create the pack expansion type for the base type.  */
3117       purpose = cxx_make_type (TYPE_PACK_EXPANSION);
3118       SET_PACK_EXPANSION_PATTERN (purpose, TREE_PURPOSE (arg));
3119       PACK_EXPANSION_PARAMETER_PACKS (purpose) = parameter_packs;
3120
3121       /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3122          they will rarely be compared to anything.  */
3123       SET_TYPE_STRUCTURAL_EQUALITY (purpose);
3124
3125       return tree_cons (purpose, TREE_VALUE (arg), NULL_TREE);
3126     }
3127
3128   if (TYPE_P (arg) || TREE_CODE (arg) == TEMPLATE_DECL)
3129     for_types = true;
3130
3131   /* Build the PACK_EXPANSION_* node.  */
3132   result = for_types
3133      ? cxx_make_type (TYPE_PACK_EXPANSION)
3134      : make_node (EXPR_PACK_EXPANSION);
3135   SET_PACK_EXPANSION_PATTERN (result, arg);
3136   if (TREE_CODE (result) == EXPR_PACK_EXPANSION)
3137     {
3138       /* Propagate type and const-expression information.  */
3139       TREE_TYPE (result) = TREE_TYPE (arg);
3140       TREE_CONSTANT (result) = TREE_CONSTANT (arg);
3141     }
3142   else
3143     /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3144        they will rarely be compared to anything.  */
3145     SET_TYPE_STRUCTURAL_EQUALITY (result);
3146
3147   /* Determine which parameter packs will be expanded.  */
3148   ppd.parameter_packs = &parameter_packs;
3149   ppd.visited = pointer_set_create ();
3150   cp_walk_tree (&arg, &find_parameter_packs_r, &ppd, ppd.visited);
3151   pointer_set_destroy (ppd.visited);
3152
3153   /* Make sure we found some parameter packs.  */
3154   if (parameter_packs == NULL_TREE)
3155     {
3156       if (TYPE_P (arg))
3157         error ("expansion pattern %<%T%> contains no argument packs", arg);
3158       else
3159         error ("expansion pattern %<%E%> contains no argument packs", arg);
3160       return error_mark_node;
3161     }
3162   PACK_EXPANSION_PARAMETER_PACKS (result) = parameter_packs;
3163
3164   return result;
3165 }
3166
3167 /* Checks T for any "bare" parameter packs, which have not yet been
3168    expanded, and issues an error if any are found. This operation can
3169    only be done on full expressions or types (e.g., an expression
3170    statement, "if" condition, etc.), because we could have expressions like:
3171
3172      foo(f(g(h(args)))...)
3173
3174    where "args" is a parameter pack. check_for_bare_parameter_packs
3175    should not be called for the subexpressions args, h(args),
3176    g(h(args)), or f(g(h(args))), because we would produce erroneous
3177    error messages. 
3178
3179    Returns TRUE and emits an error if there were bare parameter packs,
3180    returns FALSE otherwise.  */
3181 bool 
3182 check_for_bare_parameter_packs (tree t)
3183 {
3184   tree parameter_packs = NULL_TREE;
3185   struct find_parameter_pack_data ppd;
3186
3187   if (!processing_template_decl || !t || t == error_mark_node)
3188     return false;
3189
3190   if (TREE_CODE (t) == TYPE_DECL)
3191     t = TREE_TYPE (t);
3192
3193   ppd.parameter_packs = &parameter_packs;
3194   ppd.visited = pointer_set_create ();
3195   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3196   pointer_set_destroy (ppd.visited);
3197
3198   if (parameter_packs) 
3199     {
3200       error ("parameter packs not expanded with %<...%>:");
3201       while (parameter_packs)
3202         {
3203           tree pack = TREE_VALUE (parameter_packs);
3204           tree name = NULL_TREE;
3205
3206           if (TREE_CODE (pack) == TEMPLATE_TYPE_PARM
3207               || TREE_CODE (pack) == TEMPLATE_TEMPLATE_PARM)
3208             name = TYPE_NAME (pack);
3209           else if (TREE_CODE (pack) == TEMPLATE_PARM_INDEX)
3210             name = DECL_NAME (TEMPLATE_PARM_DECL (pack));
3211           else
3212             name = DECL_NAME (pack);
3213
3214           if (name)
3215             inform (input_location, "        %qD", name);
3216           else
3217             inform (input_location, "        <anonymous>");
3218
3219           parameter_packs = TREE_CHAIN (parameter_packs);
3220         }
3221
3222       return true;
3223     }
3224
3225   return false;
3226 }
3227
3228 /* Expand any parameter packs that occur in the template arguments in
3229    ARGS.  */
3230 tree
3231 expand_template_argument_pack (tree args)
3232 {
3233   tree result_args = NULL_TREE;
3234   int in_arg, out_arg = 0, nargs = args ? TREE_VEC_LENGTH (args) : 0;
3235   int num_result_args = -1;
3236   int non_default_args_count = -1;
3237
3238   /* First, determine if we need to expand anything, and the number of
3239      slots we'll need.  */
3240   for (in_arg = 0; in_arg < nargs; ++in_arg)
3241     {
3242       tree arg = TREE_VEC_ELT (args, in_arg);
3243       if (arg == NULL_TREE)
3244         return args;
3245       if (ARGUMENT_PACK_P (arg))
3246         {
3247           int num_packed = TREE_VEC_LENGTH (ARGUMENT_PACK_ARGS (arg));
3248           if (num_result_args < 0)
3249             num_result_args = in_arg + num_packed;
3250           else
3251             num_result_args += num_packed;
3252         }
3253       else
3254         {
3255           if (num_result_args >= 0)
3256             num_result_args++;
3257         }
3258     }
3259
3260   /* If no expansion is necessary, we're done.  */
3261   if (num_result_args < 0)
3262     return args;
3263
3264   /* Expand arguments.  */
3265   result_args = make_tree_vec (num_result_args);
3266   if (NON_DEFAULT_TEMPLATE_ARGS_COUNT (args))
3267     non_default_args_count =
3268       GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args);
3269   for (in_arg = 0; in_arg < nargs; ++in_arg)
3270     {
3271       tree arg = TREE_VEC_ELT (args, in_arg);
3272       if (ARGUMENT_PACK_P (arg))
3273         {
3274           tree packed = ARGUMENT_PACK_ARGS (arg);
3275           int i, num_packed = TREE_VEC_LENGTH (packed);
3276           for (i = 0; i < num_packed; ++i, ++out_arg)
3277             TREE_VEC_ELT (result_args, out_arg) = TREE_VEC_ELT(packed, i);
3278           if (non_default_args_count > 0)
3279             non_default_args_count += num_packed;
3280         }
3281       else
3282         {
3283           TREE_VEC_ELT (result_args, out_arg) = arg;
3284           ++out_arg;
3285         }
3286     }
3287   if (non_default_args_count >= 0)
3288     SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (result_args, non_default_args_count);
3289   return result_args;
3290 }
3291
3292 /* Checks if DECL shadows a template parameter.
3293
3294    [temp.local]: A template-parameter shall not be redeclared within its
3295    scope (including nested scopes).
3296
3297    Emits an error and returns TRUE if the DECL shadows a parameter,
3298    returns FALSE otherwise.  */
3299
3300 bool
3301 check_template_shadow (tree decl)
3302 {
3303   tree olddecl;
3304
3305   /* If we're not in a template, we can't possibly shadow a template
3306      parameter.  */
3307   if (!current_template_parms)
3308     return true;
3309
3310   /* Figure out what we're shadowing.  */
3311   if (TREE_CODE (decl) == OVERLOAD)
3312     decl = OVL_CURRENT (decl);
3313   olddecl = innermost_non_namespace_value (DECL_NAME (decl));
3314
3315   /* If there's no previous binding for this name, we're not shadowing
3316      anything, let alone a template parameter.  */
3317   if (!olddecl)
3318     return true;
3319
3320   /* If we're not shadowing a template parameter, we're done.  Note
3321      that OLDDECL might be an OVERLOAD (or perhaps even an
3322      ERROR_MARK), so we can't just blithely assume it to be a _DECL
3323      node.  */
3324   if (!DECL_P (olddecl) || !DECL_TEMPLATE_PARM_P (olddecl))
3325     return true;
3326
3327   /* We check for decl != olddecl to avoid bogus errors for using a
3328      name inside a class.  We check TPFI to avoid duplicate errors for
3329      inline member templates.  */
3330   if (decl == olddecl
3331       || TEMPLATE_PARMS_FOR_INLINE (current_template_parms))
3332     return true;
3333
3334   error ("declaration of %q+#D", decl);
3335   error (" shadows template parm %q+#D", olddecl);
3336   return false;
3337 }
3338
3339 /* Return a new TEMPLATE_PARM_INDEX with the indicated INDEX, LEVEL,
3340    ORIG_LEVEL, DECL, and TYPE.  */
3341
3342 static tree
3343 build_template_parm_index (int index,
3344                            int level,
3345                            int orig_level,
3346                            tree decl,
3347                            tree type)
3348 {
3349   tree t = make_node (TEMPLATE_PARM_INDEX);
3350   TEMPLATE_PARM_IDX (t) = index;
3351   TEMPLATE_PARM_LEVEL (t) = level;
3352   TEMPLATE_PARM_ORIG_LEVEL (t) = orig_level;
3353   TEMPLATE_PARM_DECL (t) = decl;
3354   TREE_TYPE (t) = type;
3355   TREE_CONSTANT (t) = TREE_CONSTANT (decl);
3356   TREE_READONLY (t) = TREE_READONLY (decl);
3357
3358   return t;
3359 }
3360
3361 /* Find the canonical type parameter for the given template type
3362    parameter.  Returns the canonical type parameter, which may be TYPE
3363    if no such parameter existed.  */
3364 static tree
3365 canonical_type_parameter (tree type)
3366 {
3367   tree list;
3368   int idx = TEMPLATE_TYPE_IDX (type);
3369   if (!canonical_template_parms)
3370     canonical_template_parms = VEC_alloc (tree, gc, idx+1);
3371
3372   while (VEC_length (tree, canonical_template_parms) <= (unsigned)idx)
3373     VEC_safe_push (tree, gc, canonical_template_parms, NULL_TREE);
3374
3375   list = VEC_index (tree, canonical_template_parms, idx);
3376   while (list && !comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
3377     list = TREE_CHAIN (list);
3378
3379   if (list)
3380     return TREE_VALUE (list);
3381   else
3382     {
3383       VEC_replace(tree, canonical_template_parms, idx,
3384                   tree_cons (NULL_TREE, type, 
3385                              VEC_index (tree, canonical_template_parms, idx)));
3386       return type;
3387     }
3388 }
3389
3390 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
3391    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
3392    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
3393    new one is created.  */
3394
3395 static tree
3396 reduce_template_parm_level (tree index, tree type, int levels, tree args,
3397                             tsubst_flags_t complain)
3398 {
3399   if (TEMPLATE_PARM_DESCENDANTS (index) == NULL_TREE
3400       || (TEMPLATE_PARM_LEVEL (TEMPLATE_PARM_DESCENDANTS (index))
3401           != TEMPLATE_PARM_LEVEL (index) - levels)
3402       || !same_type_p (type, TREE_TYPE (TEMPLATE_PARM_DESCENDANTS (index))))
3403     {
3404       tree orig_decl = TEMPLATE_PARM_DECL (index);
3405       tree decl, t;
3406
3407       decl = build_decl (DECL_SOURCE_LOCATION (orig_decl),
3408                          TREE_CODE (orig_decl), DECL_NAME (orig_decl), type);
3409       TREE_CONSTANT (decl) = TREE_CONSTANT (orig_decl);
3410       TREE_READONLY (decl) = TREE_READONLY (orig_decl);
3411       DECL_ARTIFICIAL (decl) = 1;
3412       SET_DECL_TEMPLATE_PARM_P (decl);
3413
3414       t = build_template_parm_index (TEMPLATE_PARM_IDX (index),
3415                                      TEMPLATE_PARM_LEVEL (index) - levels,
3416                                      TEMPLATE_PARM_ORIG_LEVEL (index),
3417                                      decl, type);
3418       TEMPLATE_PARM_DESCENDANTS (index) = t;
3419       TEMPLATE_PARM_PARAMETER_PACK (t) 
3420         = TEMPLATE_PARM_PARAMETER_PACK (index);
3421
3422         /* Template template parameters need this.  */
3423       if (TREE_CODE (decl) == TEMPLATE_DECL)
3424         DECL_TEMPLATE_PARMS (decl) = tsubst_template_parms
3425           (DECL_TEMPLATE_PARMS (TEMPLATE_PARM_DECL (index)),
3426            args, complain);
3427     }
3428
3429   return TEMPLATE_PARM_DESCENDANTS (index);
3430 }
3431
3432 /* Process information from new template parameter PARM and append it to the
3433    LIST being built.  This new parameter is a non-type parameter iff
3434    IS_NON_TYPE is true. This new parameter is a parameter
3435    pack iff IS_PARAMETER_PACK is true.  The location of PARM is in 
3436    PARM_LOC.  */
3437
3438 tree
3439 process_template_parm (tree list, location_t parm_loc, tree parm, bool is_non_type, 
3440                        bool is_parameter_pack)
3441 {
3442   tree decl = 0;
3443   tree defval;
3444   tree err_parm_list;
3445   int idx = 0;
3446
3447   gcc_assert (TREE_CODE (parm) == TREE_LIST);
3448   defval = TREE_PURPOSE (parm);
3449
3450   if (list)
3451     {
3452       tree p = tree_last (list);
3453
3454       if (p && TREE_VALUE (p) != error_mark_node)
3455         {
3456           p = TREE_VALUE (p);
3457           if (TREE_CODE (p) == TYPE_DECL || TREE_CODE (p) == TEMPLATE_DECL)
3458             idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
3459           else
3460             idx = TEMPLATE_PARM_IDX (DECL_INITIAL (p));
3461         }
3462
3463       ++idx;
3464     }
3465   else
3466     idx = 0;
3467
3468   if (is_non_type)
3469     {
3470       parm = TREE_VALUE (parm);
3471
3472       SET_DECL_TEMPLATE_PARM_P (parm);
3473
3474       if (TREE_TYPE (parm) == error_mark_node)
3475         {
3476           err_parm_list = build_tree_list (defval, parm);
3477           TREE_VALUE (err_parm_list) = error_mark_node;
3478            return chainon (list, err_parm_list);
3479         }
3480       else
3481       {
3482         /* [temp.param]
3483
3484            The top-level cv-qualifiers on the template-parameter are
3485            ignored when determining its type.  */
3486         TREE_TYPE (parm) = TYPE_MAIN_VARIANT (TREE_TYPE (parm));
3487         if (invalid_nontype_parm_type_p (TREE_TYPE (parm), 1))
3488           {
3489             err_parm_list = build_tree_list (defval, parm);
3490             TREE_VALUE (err_parm_list) = error_mark_node;
3491              return chainon (list, err_parm_list);
3492           }
3493
3494         if (uses_parameter_packs (TREE_TYPE (parm)) && !is_parameter_pack)
3495           {
3496             /* This template parameter is not a parameter pack, but it
3497                should be. Complain about "bare" parameter packs.  */
3498             check_for_bare_parameter_packs (TREE_TYPE (parm));
3499             
3500             /* Recover by calling this a parameter pack.  */
3501             is_parameter_pack = true;
3502           }
3503       }
3504
3505       /* A template parameter is not modifiable.  */
3506       TREE_CONSTANT (parm) = 1;
3507       TREE_READONLY (parm) = 1;
3508       decl = build_decl (parm_loc,
3509                          CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
3510       TREE_CONSTANT (decl) = 1;
3511       TREE_READONLY (decl) = 1;
3512       DECL_INITIAL (parm) = DECL_INITIAL (decl)
3513         = build_template_parm_index (idx, processing_template_decl,
3514                                      processing_template_decl,
3515                                      decl, TREE_TYPE (parm));
3516
3517       TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)) 
3518         = is_parameter_pack;
3519     }
3520   else
3521     {
3522       tree t;
3523       parm = TREE_VALUE (TREE_VALUE (parm));
3524
3525       if (parm && TREE_CODE (parm) == TEMPLATE_DECL)
3526         {
3527           t = cxx_make_type (TEMPLATE_TEMPLATE_PARM);
3528           /* This is for distinguishing between real templates and template
3529              template parameters */
3530           TREE_TYPE (parm) = t;
3531           TREE_TYPE (DECL_TEMPLATE_RESULT (parm)) = t;
3532           decl = parm;
3533         }
3534       else
3535         {
3536           t = cxx_make_type (TEMPLATE_TYPE_PARM);
3537           /* parm is either IDENTIFIER_NODE or NULL_TREE.  */
3538           decl = build_decl (parm_loc,
3539                              TYPE_DECL, parm, t);
3540         }
3541
3542       TYPE_NAME (t) = decl;
3543       TYPE_STUB_DECL (t) = decl;
3544       parm = decl;
3545       TEMPLATE_TYPE_PARM_INDEX (t)
3546         = build_template_parm_index (idx, processing_template_decl,
3547                                      processing_template_decl,
3548                                      decl, TREE_TYPE (parm));
3549       TEMPLATE_TYPE_PARAMETER_PACK (t) = is_parameter_pack;
3550       TYPE_CANONICAL (t) = canonical_type_parameter (t);
3551     }
3552   DECL_ARTIFICIAL (decl) = 1;
3553   SET_DECL_TEMPLATE_PARM_P (decl);
3554   pushdecl (decl);
3555   parm = build_tree_list (defval, parm);
3556   return chainon (list, parm);
3557 }
3558
3559 /* The end of a template parameter list has been reached.  Process the
3560    tree list into a parameter vector, converting each parameter into a more
3561    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and&n