OSDN Git Service

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