OSDN Git Service

PR c++/42447
[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
4    Free Software Foundation, Inc.
5    Written by Ken Raeburn (raeburn@cygnus.com) while at Watchmaker Computing.
6    Rewritten by Jason Merrill (jason@cygnus.com).
7
8 This file is part of GCC.
9
10 GCC is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 3, or (at your option)
13 any later version.
14
15 GCC is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18 GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3.  If not see
22 <http://www.gnu.org/licenses/>.  */
23
24 /* Known bugs or deficiencies include:
25
26      all methods must be provided in header files; can't use a source
27      file that contains only the method templates and "just win".  */
28
29 #include "config.h"
30 #include "system.h"
31 #include "coretypes.h"
32 #include "tm.h"
33 #include "obstack.h"
34 #include "tree.h"
35 #include "intl.h"
36 #include "pointer-set.h"
37 #include "flags.h"
38 #include "c-common.h"
39 #include "cp-tree.h"
40 #include "cp-objcp-common.h"
41 #include "tree-inline.h"
42 #include "decl.h"
43 #include "output.h"
44 #include "except.h"
45 #include "toplev.h"
46 #include "rtl.h"
47 #include "timevar.h"
48 #include "tree-iterator.h"
49 #include "vecprim.h"
50
51 /* The type of functions taking a tree, and some additional data, and
52    returning an int.  */
53 typedef int (*tree_fn_t) (tree, void*);
54
55 /* The PENDING_TEMPLATES is a TREE_LIST of templates whose
56    instantiations have been deferred, either because their definitions
57    were not yet available, or because we were putting off doing the work.  */
58 struct GTY (()) pending_template {
59   struct pending_template *next;
60   struct tinst_level *tinst;
61 };
62
63 static GTY(()) struct pending_template *pending_templates;
64 static GTY(()) struct pending_template *last_pending_template;
65
66 int processing_template_parmlist;
67 static int template_header_count;
68
69 static GTY(()) tree saved_trees;
70 static VEC(int,heap) *inline_parm_levels;
71
72 static GTY(()) struct tinst_level *current_tinst_level;
73
74 static GTY(()) tree saved_access_scope;
75
76 /* Live only within one (recursive) call to tsubst_expr.  We use
77    this to pass the statement expression node from the STMT_EXPR
78    to the EXPR_STMT that is its result.  */
79 static tree cur_stmt_expr;
80
81 /* A map from local variable declarations in the body of the template
82    presently being instantiated to the corresponding instantiated
83    local variables.  */
84 static htab_t local_specializations;
85
86 typedef struct GTY(()) spec_entry
87 {
88   tree tmpl;
89   tree args;
90   tree spec;
91 } spec_entry;
92
93 static GTY ((param_is (spec_entry)))
94   htab_t decl_specializations;
95
96 static GTY ((param_is (spec_entry)))
97   htab_t type_specializations;
98
99 /* Contains canonical template parameter types. The vector is indexed by
100    the TEMPLATE_TYPE_IDX of the template parameter. Each element is a
101    TREE_LIST, whose TREE_VALUEs contain the canonical template
102    parameters of various types and levels.  */
103 static GTY(()) VEC(tree,gc) *canonical_template_parms;
104
105 #define UNIFY_ALLOW_NONE 0
106 #define UNIFY_ALLOW_MORE_CV_QUAL 1
107 #define UNIFY_ALLOW_LESS_CV_QUAL 2
108 #define UNIFY_ALLOW_DERIVED 4
109 #define UNIFY_ALLOW_INTEGER 8
110 #define UNIFY_ALLOW_OUTER_LEVEL 16
111 #define UNIFY_ALLOW_OUTER_MORE_CV_QUAL 32
112 #define UNIFY_ALLOW_OUTER_LESS_CV_QUAL 64
113
114 static void push_access_scope (tree);
115 static void pop_access_scope (tree);
116 static bool resolve_overloaded_unification (tree, tree, tree, tree,
117                                             unification_kind_t, int);
118 static int try_one_overload (tree, tree, tree, tree, tree,
119                              unification_kind_t, int, bool);
120 static int unify (tree, tree, tree, tree, int);
121 static void add_pending_template (tree);
122 static int push_tinst_level (tree);
123 static void pop_tinst_level (void);
124 static tree reopen_tinst_level (struct tinst_level *);
125 static tree tsubst_initializer_list (tree, tree);
126 static tree get_class_bindings (tree, tree, tree);
127 static tree coerce_template_parms (tree, tree, tree, tsubst_flags_t,
128                                    bool, bool);
129 static void tsubst_enum (tree, tree, tree);
130 static tree add_to_template_args (tree, tree);
131 static tree add_outermost_template_args (tree, tree);
132 static bool check_instantiated_args (tree, tree, tsubst_flags_t);
133 static int maybe_adjust_types_for_deduction (unification_kind_t, tree*, tree*,
134                                              tree);
135 static int type_unification_real (tree, tree, tree, const tree *,
136                                   unsigned int, int, unification_kind_t, int);
137 static void note_template_header (int);
138 static tree convert_nontype_argument_function (tree, tree);
139 static tree convert_nontype_argument (tree, tree);
140 static tree convert_template_argument (tree, tree, tree,
141                                        tsubst_flags_t, int, tree);
142 static int for_each_template_parm (tree, tree_fn_t, void*,
143                                    struct pointer_set_t*, bool);
144 static tree expand_template_argument_pack (tree);
145 static tree build_template_parm_index (int, int, int, tree, tree);
146 static bool inline_needs_template_parms (tree);
147 static void push_inline_template_parms_recursive (tree, int);
148 static tree retrieve_local_specialization (tree);
149 static void register_local_specialization (tree, tree);
150 static hashval_t hash_specialization (const void *p);
151 static tree reduce_template_parm_level (tree, tree, int, tree, tsubst_flags_t);
152 static int mark_template_parm (tree, void *);
153 static int template_parm_this_level_p (tree, void *);
154 static tree tsubst_friend_function (tree, tree);
155 static tree tsubst_friend_class (tree, tree);
156 static int can_complete_type_without_circularity (tree);
157 static tree get_bindings (tree, tree, tree, bool);
158 static int template_decl_level (tree);
159 static int check_cv_quals_for_unify (int, tree, tree);
160 static void template_parm_level_and_index (tree, int*, int*);
161 static int unify_pack_expansion (tree, tree, tree, tree, int, bool, bool);
162 static tree tsubst_template_arg (tree, tree, tsubst_flags_t, tree);
163 static tree tsubst_template_args (tree, tree, tsubst_flags_t, tree);
164 static tree tsubst_template_parms (tree, tree, tsubst_flags_t);
165 static void regenerate_decl_from_template (tree, tree);
166 static tree most_specialized_class (tree, tree);
167 static tree tsubst_aggr_type (tree, tree, tsubst_flags_t, tree, int);
168 static tree tsubst_arg_types (tree, tree, tsubst_flags_t, tree);
169 static tree tsubst_function_type (tree, tree, tsubst_flags_t, tree);
170 static bool check_specialization_scope (void);
171 static tree process_partial_specialization (tree);
172 static void set_current_access_from_decl (tree);
173 static tree get_template_base (tree, tree, tree, tree);
174 static tree try_class_unification (tree, tree, tree, tree);
175 static int coerce_template_template_parms (tree, tree, tsubst_flags_t,
176                                            tree, tree);
177 static bool template_template_parm_bindings_ok_p (tree, tree);
178 static int template_args_equal (tree, tree);
179 static void tsubst_default_arguments (tree);
180 static tree for_each_template_parm_r (tree *, int *, void *);
181 static tree copy_default_args_to_explicit_spec_1 (tree, tree);
182 static void copy_default_args_to_explicit_spec (tree);
183 static int invalid_nontype_parm_type_p (tree, tsubst_flags_t);
184 static int eq_local_specializations (const void *, const void *);
185 static bool dependent_template_arg_p (tree);
186 static bool any_template_arguments_need_structural_equality_p (tree);
187 static bool dependent_type_p_r (tree);
188 static tree tsubst_expr (tree, tree, tsubst_flags_t, tree, bool);
189 static tree tsubst_copy (tree, tree, tsubst_flags_t, tree);
190 static tree tsubst_pack_expansion (tree, tree, tsubst_flags_t, tree);
191 static tree tsubst_decl (tree, tree, tsubst_flags_t);
192 static void perform_typedefs_access_check (tree tmpl, tree targs);
193 static void append_type_to_template_for_access_check_1 (tree, tree, tree,
194                                                         location_t);
195 static hashval_t iterative_hash_template_arg (tree arg, hashval_t val);
196 static tree listify (tree);
197 static tree listify_autos (tree, tree);
198
199 /* Make the current scope suitable for access checking when we are
200    processing T.  T can be FUNCTION_DECL for instantiated function
201    template, or VAR_DECL for static member variable (need by
202    instantiate_decl).  */
203
204 static void
205 push_access_scope (tree t)
206 {
207   gcc_assert (TREE_CODE (t) == FUNCTION_DECL
208               || TREE_CODE (t) == VAR_DECL);
209
210   if (DECL_FRIEND_CONTEXT (t))
211     push_nested_class (DECL_FRIEND_CONTEXT (t));
212   else if (DECL_CLASS_SCOPE_P (t))
213     push_nested_class (DECL_CONTEXT (t));
214   else
215     push_to_top_level ();
216
217   if (TREE_CODE (t) == FUNCTION_DECL)
218     {
219       saved_access_scope = tree_cons
220         (NULL_TREE, current_function_decl, saved_access_scope);
221       current_function_decl = t;
222     }
223 }
224
225 /* Restore the scope set up by push_access_scope.  T is the node we
226    are processing.  */
227
228 static void
229 pop_access_scope (tree t)
230 {
231   if (TREE_CODE (t) == FUNCTION_DECL)
232     {
233       current_function_decl = TREE_VALUE (saved_access_scope);
234       saved_access_scope = TREE_CHAIN (saved_access_scope);
235     }
236
237   if (DECL_FRIEND_CONTEXT (t) || DECL_CLASS_SCOPE_P (t))
238     pop_nested_class ();
239   else
240     pop_from_top_level ();
241 }
242
243 /* Do any processing required when DECL (a member template
244    declaration) is finished.  Returns the TEMPLATE_DECL corresponding
245    to DECL, unless it is a specialization, in which case the DECL
246    itself is returned.  */
247
248 tree
249 finish_member_template_decl (tree decl)
250 {
251   if (decl == error_mark_node)
252     return error_mark_node;
253
254   gcc_assert (DECL_P (decl));
255
256   if (TREE_CODE (decl) == TYPE_DECL)
257     {
258       tree type;
259
260       type = TREE_TYPE (decl);
261       if (type == error_mark_node)
262         return error_mark_node;
263       if (MAYBE_CLASS_TYPE_P (type)
264           && CLASSTYPE_TEMPLATE_INFO (type)
265           && !CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
266         {
267           tree tmpl = CLASSTYPE_TI_TEMPLATE (type);
268           check_member_template (tmpl);
269           return tmpl;
270         }
271       return NULL_TREE;
272     }
273   else if (TREE_CODE (decl) == FIELD_DECL)
274     error ("data member %qD cannot be a member template", decl);
275   else if (DECL_TEMPLATE_INFO (decl))
276     {
277       if (!DECL_TEMPLATE_SPECIALIZATION (decl))
278         {
279           check_member_template (DECL_TI_TEMPLATE (decl));
280           return DECL_TI_TEMPLATE (decl);
281         }
282       else
283         return decl;
284     }
285   else
286     error ("invalid member template declaration %qD", decl);
287
288   return error_mark_node;
289 }
290
291 /* Create a template info node.  */
292
293 tree
294 build_template_info (tree template_decl, tree template_args)
295 {
296   tree result = make_node (TEMPLATE_INFO);
297   TI_TEMPLATE (result) = template_decl;
298   TI_ARGS (result) = template_args;
299   return result;
300 }
301
302 /* Return the template info node corresponding to T, whatever T is.  */
303
304 tree
305 get_template_info (const_tree t)
306 {
307   tree tinfo = NULL_TREE;
308
309   if (!t || t == error_mark_node)
310     return NULL;
311
312   if (DECL_P (t) && DECL_LANG_SPECIFIC (t))
313     tinfo = DECL_TEMPLATE_INFO (t);
314
315   if (!tinfo && DECL_IMPLICIT_TYPEDEF_P (t))
316     t = TREE_TYPE (t);
317
318   if (TAGGED_TYPE_P (t))
319     tinfo = TYPE_TEMPLATE_INFO (t);
320
321   return tinfo;
322 }
323
324 /* Returns the template nesting level of the indicated class TYPE.
325
326    For example, in:
327      template <class T>
328      struct A
329      {
330        template <class U>
331        struct B {};
332      };
333
334    A<T>::B<U> has depth two, while A<T> has depth one.
335    Both A<T>::B<int> and A<int>::B<U> have depth one, if
336    they are instantiations, not specializations.
337
338    This function is guaranteed to return 0 if passed NULL_TREE so
339    that, for example, `template_class_depth (current_class_type)' is
340    always safe.  */
341
342 int
343 template_class_depth (tree type)
344 {
345   int depth;
346
347   for (depth = 0;
348        type && TREE_CODE (type) != NAMESPACE_DECL;
349        type = (TREE_CODE (type) == FUNCTION_DECL)
350          ? CP_DECL_CONTEXT (type) : TYPE_CONTEXT (type))
351     {
352       tree tinfo = get_template_info (type);
353
354       if (tinfo && PRIMARY_TEMPLATE_P (TI_TEMPLATE (tinfo))
355           && uses_template_parms (INNERMOST_TEMPLATE_ARGS (TI_ARGS (tinfo))))
356         ++depth;
357     }
358
359   return depth;
360 }
361
362 /* Subroutine of maybe_begin_member_template_processing.
363    Returns true if processing DECL needs us to push template parms.  */
364
365 static bool
366 inline_needs_template_parms (tree decl)
367 {
368   if (! DECL_TEMPLATE_INFO (decl))
369     return false;
370
371   return (TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (most_general_template (decl)))
372           > (processing_template_decl + DECL_TEMPLATE_SPECIALIZATION (decl)));
373 }
374
375 /* Subroutine of maybe_begin_member_template_processing.
376    Push the template parms in PARMS, starting from LEVELS steps into the
377    chain, and ending at the beginning, since template parms are listed
378    innermost first.  */
379
380 static void
381 push_inline_template_parms_recursive (tree parmlist, int levels)
382 {
383   tree parms = TREE_VALUE (parmlist);
384   int i;
385
386   if (levels > 1)
387     push_inline_template_parms_recursive (TREE_CHAIN (parmlist), levels - 1);
388
389   ++processing_template_decl;
390   current_template_parms
391     = tree_cons (size_int (processing_template_decl),
392                  parms, current_template_parms);
393   TEMPLATE_PARMS_FOR_INLINE (current_template_parms) = 1;
394
395   begin_scope (TREE_VEC_LENGTH (parms) ? sk_template_parms : sk_template_spec,
396                NULL);
397   for (i = 0; i < TREE_VEC_LENGTH (parms); ++i)
398     {
399       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
400
401       if (parm == error_mark_node)
402         continue;
403
404       gcc_assert (DECL_P (parm));
405
406       switch (TREE_CODE (parm))
407         {
408         case TYPE_DECL:
409         case TEMPLATE_DECL:
410           pushdecl (parm);
411           break;
412
413         case PARM_DECL:
414           {
415             /* Make a CONST_DECL as is done in process_template_parm.
416                It is ugly that we recreate this here; the original
417                version built in process_template_parm is no longer
418                available.  */
419             tree decl = build_decl (DECL_SOURCE_LOCATION (parm),
420                                     CONST_DECL, DECL_NAME (parm),
421                                     TREE_TYPE (parm));
422             DECL_ARTIFICIAL (decl) = 1;
423             TREE_CONSTANT (decl) = 1;
424             TREE_READONLY (decl) = 1;
425             DECL_INITIAL (decl) = DECL_INITIAL (parm);
426             SET_DECL_TEMPLATE_PARM_P (decl);
427             pushdecl (decl);
428           }
429           break;
430
431         default:
432           gcc_unreachable ();
433         }
434     }
435 }
436
437 /* Restore the template parameter context for a member template or
438    a friend template defined in a class definition.  */
439
440 void
441 maybe_begin_member_template_processing (tree decl)
442 {
443   tree parms;
444   int levels = 0;
445
446   if (inline_needs_template_parms (decl))
447     {
448       parms = DECL_TEMPLATE_PARMS (most_general_template (decl));
449       levels = TMPL_PARMS_DEPTH (parms) - processing_template_decl;
450
451       if (DECL_TEMPLATE_SPECIALIZATION (decl))
452         {
453           --levels;
454           parms = TREE_CHAIN (parms);
455         }
456
457       push_inline_template_parms_recursive (parms, levels);
458     }
459
460   /* Remember how many levels of template parameters we pushed so that
461      we can pop them later.  */
462   VEC_safe_push (int, heap, inline_parm_levels, levels);
463 }
464
465 /* Undo the effects of maybe_begin_member_template_processing.  */
466
467 void
468 maybe_end_member_template_processing (void)
469 {
470   int i;
471   int last;
472
473   if (VEC_length (int, inline_parm_levels) == 0)
474     return;
475
476   last = VEC_pop (int, inline_parm_levels);
477   for (i = 0; i < last; ++i)
478     {
479       --processing_template_decl;
480       current_template_parms = TREE_CHAIN (current_template_parms);
481       poplevel (0, 0, 0);
482     }
483 }
484
485 /* Return a new template argument vector which contains all of ARGS,
486    but has as its innermost set of arguments the EXTRA_ARGS.  */
487
488 static tree
489 add_to_template_args (tree args, tree extra_args)
490 {
491   tree new_args;
492   int extra_depth;
493   int i;
494   int j;
495
496   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_NEW (spec_entry);
891                   **slot = elt;
892                 }
893               else if (COMPLETE_TYPE_P (inst) || TYPE_BEING_DEFINED (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_NEW (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     default:
1564       switch (tclass)
1565         {
1566         case tcc_type:
1567           if (TYPE_CANONICAL (arg))
1568             return iterative_hash_object (TYPE_HASH (TYPE_CANONICAL (arg)),
1569                                           val);
1570           else if (TREE_CODE (arg) == DECLTYPE_TYPE)
1571             return iterative_hash_template_arg (DECLTYPE_TYPE_EXPR (arg), val);
1572           /* Otherwise just compare the types during lookup.  */
1573           return val;
1574
1575         case tcc_declaration:
1576         case tcc_constant:
1577           return iterative_hash_expr (arg, val);
1578
1579         default:
1580           gcc_assert (IS_EXPR_CODE_CLASS (tclass));
1581           {
1582             unsigned n = TREE_OPERAND_LENGTH (arg);
1583             for (i = 0; i < n; ++i)
1584               val = iterative_hash_template_arg (TREE_OPERAND (arg, i), val);
1585             return val;
1586           }
1587         }
1588     }
1589   gcc_unreachable ();
1590   return 0;
1591 }
1592
1593 /* Unregister the specialization SPEC as a specialization of TMPL.
1594    Replace it with NEW_SPEC, if NEW_SPEC is non-NULL.  Returns true
1595    if the SPEC was listed as a specialization of TMPL.
1596
1597    Note that SPEC has been ggc_freed, so we can't look inside it.  */
1598
1599 bool
1600 reregister_specialization (tree spec, tree tinfo, tree new_spec)
1601 {
1602   spec_entry **slot;
1603   spec_entry elt;
1604
1605   elt.tmpl = most_general_template (TI_TEMPLATE (tinfo));
1606   elt.args = TI_ARGS (tinfo);
1607   elt.spec = NULL_TREE;
1608
1609   slot = (spec_entry **) htab_find_slot (decl_specializations, &elt, INSERT);
1610   if (*slot)
1611     {
1612       gcc_assert ((*slot)->spec == spec || (*slot)->spec == new_spec);
1613       gcc_assert (new_spec != NULL_TREE);
1614       (*slot)->spec = new_spec;
1615       return 1;
1616     }
1617
1618   return 0;
1619 }
1620
1621 /* Compare an entry in the local specializations hash table P1 (which
1622    is really a pointer to a TREE_LIST) with P2 (which is really a
1623    DECL).  */
1624
1625 static int
1626 eq_local_specializations (const void *p1, const void *p2)
1627 {
1628   return TREE_VALUE ((const_tree) p1) == (const_tree) p2;
1629 }
1630
1631 /* Hash P1, an entry in the local specializations table.  */
1632
1633 static hashval_t
1634 hash_local_specialization (const void* p1)
1635 {
1636   return htab_hash_pointer (TREE_VALUE ((const_tree) p1));
1637 }
1638
1639 /* Like register_specialization, but for local declarations.  We are
1640    registering SPEC, an instantiation of TMPL.  */
1641
1642 static void
1643 register_local_specialization (tree spec, tree tmpl)
1644 {
1645   void **slot;
1646
1647   slot = htab_find_slot_with_hash (local_specializations, tmpl,
1648                                    htab_hash_pointer (tmpl), INSERT);
1649   *slot = build_tree_list (spec, tmpl);
1650 }
1651
1652 /* TYPE is a class type.  Returns true if TYPE is an explicitly
1653    specialized class.  */
1654
1655 bool
1656 explicit_class_specialization_p (tree type)
1657 {
1658   if (!CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
1659     return false;
1660   return !uses_template_parms (CLASSTYPE_TI_ARGS (type));
1661 }
1662
1663 /* Print the list of functions at FNS, going through all the overloads
1664    for each element of the list.  Alternatively, FNS can not be a
1665    TREE_LIST, in which case it will be printed together with all the
1666    overloads.
1667
1668    MORE and *STR should respectively be FALSE and NULL when the function
1669    is called from the outside.  They are used internally on recursive
1670    calls.  print_candidates manages the two parameters and leaves NULL
1671    in *STR when it ends.  */
1672
1673 static void
1674 print_candidates_1 (tree fns, bool more, const char **str)
1675 {
1676   tree fn, fn2;
1677   char *spaces = NULL;
1678
1679   for (fn = fns; fn; fn = OVL_NEXT (fn))
1680     if (TREE_CODE (fn) == TREE_LIST)
1681       {
1682         gcc_assert (!OVL_NEXT (fn) && !is_overloaded_fn (fn));
1683         for (fn2 = fn; fn2 != NULL_TREE; fn2 = TREE_CHAIN (fn2))
1684           print_candidates_1 (TREE_VALUE (fn2),
1685                               TREE_CHAIN (fn2) || more, str);
1686       }
1687     else
1688       {
1689         if (!*str)
1690           {
1691             /* Pick the prefix string.  */
1692             if (!more && !OVL_NEXT (fns))
1693               {
1694                 error ("candidate is: %+#D", OVL_CURRENT (fn));
1695                 continue;
1696               }
1697
1698             *str = _("candidates are:");
1699             spaces = get_spaces (*str);
1700           }
1701         error ("%s %+#D", *str, OVL_CURRENT (fn));
1702         *str = spaces ? spaces : *str;
1703       }
1704
1705   if (!more)
1706     {
1707       free (spaces);
1708       *str = NULL;
1709     }
1710 }
1711
1712 /* Print the list of candidate FNS in an error message.  */
1713
1714 void
1715 print_candidates (tree fns)
1716 {
1717   const char *str = NULL;
1718   print_candidates_1 (fns, false, &str);
1719   gcc_assert (str == NULL);
1720 }
1721
1722 /* Returns the template (one of the functions given by TEMPLATE_ID)
1723    which can be specialized to match the indicated DECL with the
1724    explicit template args given in TEMPLATE_ID.  The DECL may be
1725    NULL_TREE if none is available.  In that case, the functions in
1726    TEMPLATE_ID are non-members.
1727
1728    If NEED_MEMBER_TEMPLATE is nonzero the function is known to be a
1729    specialization of a member template.
1730
1731    The TEMPLATE_COUNT is the number of references to qualifying
1732    template classes that appeared in the name of the function. See
1733    check_explicit_specialization for a more accurate description.
1734
1735    TSK indicates what kind of template declaration (if any) is being
1736    declared.  TSK_TEMPLATE indicates that the declaration given by
1737    DECL, though a FUNCTION_DECL, has template parameters, and is
1738    therefore a template function.
1739
1740    The template args (those explicitly specified and those deduced)
1741    are output in a newly created vector *TARGS_OUT.
1742
1743    If it is impossible to determine the result, an error message is
1744    issued.  The error_mark_node is returned to indicate failure.  */
1745
1746 static tree
1747 determine_specialization (tree template_id,
1748                           tree decl,
1749                           tree* targs_out,
1750                           int need_member_template,
1751                           int template_count,
1752                           tmpl_spec_kind tsk)
1753 {
1754   tree fns;
1755   tree targs;
1756   tree explicit_targs;
1757   tree candidates = NULL_TREE;
1758   /* A TREE_LIST of templates of which DECL may be a specialization.
1759      The TREE_VALUE of each node is a TEMPLATE_DECL.  The
1760      corresponding TREE_PURPOSE is the set of template arguments that,
1761      when used to instantiate the template, would produce a function
1762      with the signature of DECL.  */
1763   tree templates = NULL_TREE;
1764   int header_count;
1765   struct cp_binding_level *b;
1766
1767   *targs_out = NULL_TREE;
1768
1769   if (template_id == error_mark_node || decl == error_mark_node)
1770     return error_mark_node;
1771
1772   fns = TREE_OPERAND (template_id, 0);
1773   explicit_targs = TREE_OPERAND (template_id, 1);
1774
1775   if (fns == error_mark_node)
1776     return error_mark_node;
1777
1778   /* Check for baselinks.  */
1779   if (BASELINK_P (fns))
1780     fns = BASELINK_FUNCTIONS (fns);
1781
1782   if (!is_overloaded_fn (fns))
1783     {
1784       error ("%qD is not a function template", fns);
1785       return error_mark_node;
1786     }
1787
1788   /* Count the number of template headers specified for this
1789      specialization.  */
1790   header_count = 0;
1791   for (b = current_binding_level;
1792        b->kind == sk_template_parms;
1793        b = b->level_chain)
1794     ++header_count;
1795
1796   for (; fns; fns = OVL_NEXT (fns))
1797     {
1798       tree fn = OVL_CURRENT (fns);
1799
1800       if (TREE_CODE (fn) == TEMPLATE_DECL)
1801         {
1802           tree decl_arg_types;
1803           tree fn_arg_types;
1804
1805           /* In case of explicit specialization, we need to check if
1806              the number of template headers appearing in the specialization
1807              is correct. This is usually done in check_explicit_specialization,
1808              but the check done there cannot be exhaustive when specializing
1809              member functions. Consider the following code:
1810
1811              template <> void A<int>::f(int);
1812              template <> template <> void A<int>::f(int);
1813
1814              Assuming that A<int> is not itself an explicit specialization
1815              already, the first line specializes "f" which is a non-template
1816              member function, whilst the second line specializes "f" which
1817              is a template member function. So both lines are syntactically
1818              correct, and check_explicit_specialization does not reject
1819              them.
1820
1821              Here, we can do better, as we are matching the specialization
1822              against the declarations. We count the number of template
1823              headers, and we check if they match TEMPLATE_COUNT + 1
1824              (TEMPLATE_COUNT is the number of qualifying template classes,
1825              plus there must be another header for the member template
1826              itself).
1827
1828              Notice that if header_count is zero, this is not a
1829              specialization but rather a template instantiation, so there
1830              is no check we can perform here.  */
1831           if (header_count && header_count != template_count + 1)
1832             continue;
1833
1834           /* Check that the number of template arguments at the
1835              innermost level for DECL is the same as for FN.  */
1836           if (current_binding_level->kind == sk_template_parms
1837               && !current_binding_level->explicit_spec_p
1838               && (TREE_VEC_LENGTH (DECL_INNERMOST_TEMPLATE_PARMS (fn))
1839                   != TREE_VEC_LENGTH (INNERMOST_TEMPLATE_PARMS
1840                                       (current_template_parms))))
1841             continue;
1842
1843           /* DECL might be a specialization of FN.  */
1844           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1845           fn_arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
1846
1847           /* For a non-static member function, we need to make sure
1848              that the const qualification is the same.  Since
1849              get_bindings does not try to merge the "this" parameter,
1850              we must do the comparison explicitly.  */
1851           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (fn)
1852               && !same_type_p (TREE_VALUE (fn_arg_types),
1853                                TREE_VALUE (decl_arg_types)))
1854             continue;
1855
1856           /* Skip the "this" parameter and, for constructors of
1857              classes with virtual bases, the VTT parameter.  A
1858              full specialization of a constructor will have a VTT
1859              parameter, but a template never will.  */ 
1860           decl_arg_types 
1861             = skip_artificial_parms_for (decl, decl_arg_types);
1862           fn_arg_types 
1863             = skip_artificial_parms_for (fn, fn_arg_types);
1864
1865           /* Check that the number of function parameters matches.
1866              For example,
1867                template <class T> void f(int i = 0);
1868                template <> void f<int>();
1869              The specialization f<int> is invalid but is not caught
1870              by get_bindings below.  */
1871           if (list_length (fn_arg_types) != list_length (decl_arg_types))
1872             continue;
1873
1874           /* Function templates cannot be specializations; there are
1875              no partial specializations of functions.  Therefore, if
1876              the type of DECL does not match FN, there is no
1877              match.  */
1878           if (tsk == tsk_template)
1879             {
1880               if (compparms (fn_arg_types, decl_arg_types))
1881                 candidates = tree_cons (NULL_TREE, fn, candidates);
1882               continue;
1883             }
1884
1885           /* See whether this function might be a specialization of this
1886              template.  */
1887           targs = get_bindings (fn, decl, explicit_targs, /*check_ret=*/true);
1888
1889           if (!targs)
1890             /* We cannot deduce template arguments that when used to
1891                specialize TMPL will produce DECL.  */
1892             continue;
1893
1894           /* Save this template, and the arguments deduced.  */
1895           templates = tree_cons (targs, fn, templates);
1896         }
1897       else if (need_member_template)
1898         /* FN is an ordinary member function, and we need a
1899            specialization of a member template.  */
1900         ;
1901       else if (TREE_CODE (fn) != FUNCTION_DECL)
1902         /* We can get IDENTIFIER_NODEs here in certain erroneous
1903            cases.  */
1904         ;
1905       else if (!DECL_FUNCTION_MEMBER_P (fn))
1906         /* This is just an ordinary non-member function.  Nothing can
1907            be a specialization of that.  */
1908         ;
1909       else if (DECL_ARTIFICIAL (fn))
1910         /* Cannot specialize functions that are created implicitly.  */
1911         ;
1912       else
1913         {
1914           tree decl_arg_types;
1915
1916           /* This is an ordinary member function.  However, since
1917              we're here, we can assume it's enclosing class is a
1918              template class.  For example,
1919
1920                template <typename T> struct S { void f(); };
1921                template <> void S<int>::f() {}
1922
1923              Here, S<int>::f is a non-template, but S<int> is a
1924              template class.  If FN has the same type as DECL, we
1925              might be in business.  */
1926
1927           if (!DECL_TEMPLATE_INFO (fn))
1928             /* Its enclosing class is an explicit specialization
1929                of a template class.  This is not a candidate.  */
1930             continue;
1931
1932           if (!same_type_p (TREE_TYPE (TREE_TYPE (decl)),
1933                             TREE_TYPE (TREE_TYPE (fn))))
1934             /* The return types differ.  */
1935             continue;
1936
1937           /* Adjust the type of DECL in case FN is a static member.  */
1938           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1939           if (DECL_STATIC_FUNCTION_P (fn)
1940               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1941             decl_arg_types = TREE_CHAIN (decl_arg_types);
1942
1943           if (compparms (TYPE_ARG_TYPES (TREE_TYPE (fn)),
1944                          decl_arg_types))
1945             /* They match!  */
1946             candidates = tree_cons (NULL_TREE, fn, candidates);
1947         }
1948     }
1949
1950   if (templates && TREE_CHAIN (templates))
1951     {
1952       /* We have:
1953
1954            [temp.expl.spec]
1955
1956            It is possible for a specialization with a given function
1957            signature to be instantiated from more than one function
1958            template.  In such cases, explicit specification of the
1959            template arguments must be used to uniquely identify the
1960            function template specialization being specialized.
1961
1962          Note that here, there's no suggestion that we're supposed to
1963          determine which of the candidate templates is most
1964          specialized.  However, we, also have:
1965
1966            [temp.func.order]
1967
1968            Partial ordering of overloaded function template
1969            declarations is used in the following contexts to select
1970            the function template to which a function template
1971            specialization refers:
1972
1973            -- when an explicit specialization refers to a function
1974               template.
1975
1976          So, we do use the partial ordering rules, at least for now.
1977          This extension can only serve to make invalid programs valid,
1978          so it's safe.  And, there is strong anecdotal evidence that
1979          the committee intended the partial ordering rules to apply;
1980          the EDG front end has that behavior, and John Spicer claims
1981          that the committee simply forgot to delete the wording in
1982          [temp.expl.spec].  */
1983       tree tmpl = most_specialized_instantiation (templates);
1984       if (tmpl != error_mark_node)
1985         {
1986           templates = tmpl;
1987           TREE_CHAIN (templates) = NULL_TREE;
1988         }
1989     }
1990
1991   if (templates == NULL_TREE && candidates == NULL_TREE)
1992     {
1993       error ("template-id %qD for %q+D does not match any template "
1994              "declaration", template_id, decl);
1995       if (header_count && header_count != template_count + 1)
1996         inform (input_location, "saw %d %<template<>%>, need %d for "
1997                 "specializing a member function template",
1998                 header_count, template_count + 1);
1999       return error_mark_node;
2000     }
2001   else if ((templates && TREE_CHAIN (templates))
2002            || (candidates && TREE_CHAIN (candidates))
2003            || (templates && candidates))
2004     {
2005       error ("ambiguous template specialization %qD for %q+D",
2006              template_id, decl);
2007       candidates = chainon (candidates, templates);
2008       print_candidates (candidates);
2009       return error_mark_node;
2010     }
2011
2012   /* We have one, and exactly one, match.  */
2013   if (candidates)
2014     {
2015       tree fn = TREE_VALUE (candidates);
2016       *targs_out = copy_node (DECL_TI_ARGS (fn));
2017       /* DECL is a re-declaration or partial instantiation of a template
2018          function.  */
2019       if (TREE_CODE (fn) == TEMPLATE_DECL)
2020         return fn;
2021       /* It was a specialization of an ordinary member function in a
2022          template class.  */
2023       return DECL_TI_TEMPLATE (fn);
2024     }
2025
2026   /* It was a specialization of a template.  */
2027   targs = DECL_TI_ARGS (DECL_TEMPLATE_RESULT (TREE_VALUE (templates)));
2028   if (TMPL_ARGS_HAVE_MULTIPLE_LEVELS (targs))
2029     {
2030       *targs_out = copy_node (targs);
2031       SET_TMPL_ARGS_LEVEL (*targs_out,
2032                            TMPL_ARGS_DEPTH (*targs_out),
2033                            TREE_PURPOSE (templates));
2034     }
2035   else
2036     *targs_out = TREE_PURPOSE (templates);
2037   return TREE_VALUE (templates);
2038 }
2039
2040 /* Returns a chain of parameter types, exactly like the SPEC_TYPES,
2041    but with the default argument values filled in from those in the
2042    TMPL_TYPES.  */
2043
2044 static tree
2045 copy_default_args_to_explicit_spec_1 (tree spec_types,
2046                                       tree tmpl_types)
2047 {
2048   tree new_spec_types;
2049
2050   if (!spec_types)
2051     return NULL_TREE;
2052
2053   if (spec_types == void_list_node)
2054     return void_list_node;
2055
2056   /* Substitute into the rest of the list.  */
2057   new_spec_types =
2058     copy_default_args_to_explicit_spec_1 (TREE_CHAIN (spec_types),
2059                                           TREE_CHAIN (tmpl_types));
2060
2061   /* Add the default argument for this parameter.  */
2062   return hash_tree_cons (TREE_PURPOSE (tmpl_types),
2063                          TREE_VALUE (spec_types),
2064                          new_spec_types);
2065 }
2066
2067 /* DECL is an explicit specialization.  Replicate default arguments
2068    from the template it specializes.  (That way, code like:
2069
2070      template <class T> void f(T = 3);
2071      template <> void f(double);
2072      void g () { f (); }
2073
2074    works, as required.)  An alternative approach would be to look up
2075    the correct default arguments at the call-site, but this approach
2076    is consistent with how implicit instantiations are handled.  */
2077
2078 static void
2079 copy_default_args_to_explicit_spec (tree decl)
2080 {
2081   tree tmpl;
2082   tree spec_types;
2083   tree tmpl_types;
2084   tree new_spec_types;
2085   tree old_type;
2086   tree new_type;
2087   tree t;
2088   tree object_type = NULL_TREE;
2089   tree in_charge = NULL_TREE;
2090   tree vtt = NULL_TREE;
2091
2092   /* See if there's anything we need to do.  */
2093   tmpl = DECL_TI_TEMPLATE (decl);
2094   tmpl_types = TYPE_ARG_TYPES (TREE_TYPE (DECL_TEMPLATE_RESULT (tmpl)));
2095   for (t = tmpl_types; t; t = TREE_CHAIN (t))
2096     if (TREE_PURPOSE (t))
2097       break;
2098   if (!t)
2099     return;
2100
2101   old_type = TREE_TYPE (decl);
2102   spec_types = TYPE_ARG_TYPES (old_type);
2103
2104   if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2105     {
2106       /* Remove the this pointer, but remember the object's type for
2107          CV quals.  */
2108       object_type = TREE_TYPE (TREE_VALUE (spec_types));
2109       spec_types = TREE_CHAIN (spec_types);
2110       tmpl_types = TREE_CHAIN (tmpl_types);
2111
2112       if (DECL_HAS_IN_CHARGE_PARM_P (decl))
2113         {
2114           /* DECL may contain more parameters than TMPL due to the extra
2115              in-charge parameter in constructors and destructors.  */
2116           in_charge = spec_types;
2117           spec_types = TREE_CHAIN (spec_types);
2118         }
2119       if (DECL_HAS_VTT_PARM_P (decl))
2120         {
2121           vtt = spec_types;
2122           spec_types = TREE_CHAIN (spec_types);
2123         }
2124     }
2125
2126   /* Compute the merged default arguments.  */
2127   new_spec_types =
2128     copy_default_args_to_explicit_spec_1 (spec_types, tmpl_types);
2129
2130   /* Compute the new FUNCTION_TYPE.  */
2131   if (object_type)
2132     {
2133       if (vtt)
2134         new_spec_types = hash_tree_cons (TREE_PURPOSE (vtt),
2135                                          TREE_VALUE (vtt),
2136                                          new_spec_types);
2137
2138       if (in_charge)
2139         /* Put the in-charge parameter back.  */
2140         new_spec_types = hash_tree_cons (TREE_PURPOSE (in_charge),
2141                                          TREE_VALUE (in_charge),
2142                                          new_spec_types);
2143
2144       new_type = build_method_type_directly (object_type,
2145                                              TREE_TYPE (old_type),
2146                                              new_spec_types);
2147     }
2148   else
2149     new_type = build_function_type (TREE_TYPE (old_type),
2150                                     new_spec_types);
2151   new_type = cp_build_type_attribute_variant (new_type,
2152                                               TYPE_ATTRIBUTES (old_type));
2153   new_type = build_exception_variant (new_type,
2154                                       TYPE_RAISES_EXCEPTIONS (old_type));
2155   TREE_TYPE (decl) = new_type;
2156 }
2157
2158 /* Check to see if the function just declared, as indicated in
2159    DECLARATOR, and in DECL, is a specialization of a function
2160    template.  We may also discover that the declaration is an explicit
2161    instantiation at this point.
2162
2163    Returns DECL, or an equivalent declaration that should be used
2164    instead if all goes well.  Issues an error message if something is
2165    amiss.  Returns error_mark_node if the error is not easily
2166    recoverable.
2167
2168    FLAGS is a bitmask consisting of the following flags:
2169
2170    2: The function has a definition.
2171    4: The function is a friend.
2172
2173    The TEMPLATE_COUNT is the number of references to qualifying
2174    template classes that appeared in the name of the function.  For
2175    example, in
2176
2177      template <class T> struct S { void f(); };
2178      void S<int>::f();
2179
2180    the TEMPLATE_COUNT would be 1.  However, explicitly specialized
2181    classes are not counted in the TEMPLATE_COUNT, so that in
2182
2183      template <class T> struct S {};
2184      template <> struct S<int> { void f(); }
2185      template <> void S<int>::f();
2186
2187    the TEMPLATE_COUNT would be 0.  (Note that this declaration is
2188    invalid; there should be no template <>.)
2189
2190    If the function is a specialization, it is marked as such via
2191    DECL_TEMPLATE_SPECIALIZATION.  Furthermore, its DECL_TEMPLATE_INFO
2192    is set up correctly, and it is added to the list of specializations
2193    for that template.  */
2194
2195 tree
2196 check_explicit_specialization (tree declarator,
2197                                tree decl,
2198                                int template_count,
2199                                int flags)
2200 {
2201   int have_def = flags & 2;
2202   int is_friend = flags & 4;
2203   int specialization = 0;
2204   int explicit_instantiation = 0;
2205   int member_specialization = 0;
2206   tree ctype = DECL_CLASS_CONTEXT (decl);
2207   tree dname = DECL_NAME (decl);
2208   tmpl_spec_kind tsk;
2209
2210   if (is_friend)
2211     {
2212       if (!processing_specialization)
2213         tsk = tsk_none;
2214       else
2215         tsk = tsk_excessive_parms;
2216     }
2217   else
2218     tsk = current_tmpl_spec_kind (template_count);
2219
2220   switch (tsk)
2221     {
2222     case tsk_none:
2223       if (processing_specialization)
2224         {
2225           specialization = 1;
2226           SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2227         }
2228       else if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2229         {
2230           if (is_friend)
2231             /* This could be something like:
2232
2233                template <class T> void f(T);
2234                class S { friend void f<>(int); }  */
2235             specialization = 1;
2236           else
2237             {
2238               /* This case handles bogus declarations like template <>
2239                  template <class T> void f<int>(); */
2240
2241               error ("template-id %qD in declaration of primary template",
2242                      declarator);
2243               return decl;
2244             }
2245         }
2246       break;
2247
2248     case tsk_invalid_member_spec:
2249       /* The error has already been reported in
2250          check_specialization_scope.  */
2251       return error_mark_node;
2252
2253     case tsk_invalid_expl_inst:
2254       error ("template parameter list used in explicit instantiation");
2255
2256       /* Fall through.  */
2257
2258     case tsk_expl_inst:
2259       if (have_def)
2260         error ("definition provided for explicit instantiation");
2261
2262       explicit_instantiation = 1;
2263       break;
2264
2265     case tsk_excessive_parms:
2266     case tsk_insufficient_parms:
2267       if (tsk == tsk_excessive_parms)
2268         error ("too many template parameter lists in declaration of %qD",
2269                decl);
2270       else if (template_header_count)
2271         error("too few template parameter lists in declaration of %qD", decl);
2272       else
2273         error("explicit specialization of %qD must be introduced by "
2274               "%<template <>%>", decl);
2275
2276       /* Fall through.  */
2277     case tsk_expl_spec:
2278       SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2279       if (ctype)
2280         member_specialization = 1;
2281       else
2282         specialization = 1;
2283       break;
2284
2285     case tsk_template:
2286       if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2287         {
2288           /* This case handles bogus declarations like template <>
2289              template <class T> void f<int>(); */
2290
2291           if (uses_template_parms (declarator))
2292             error ("function template partial specialization %qD "
2293                    "is not allowed", declarator);
2294           else
2295             error ("template-id %qD in declaration of primary template",
2296                    declarator);
2297           return decl;
2298         }
2299
2300       if (ctype && CLASSTYPE_TEMPLATE_INSTANTIATION (ctype))
2301         /* This is a specialization of a member template, without
2302            specialization the containing class.  Something like:
2303
2304              template <class T> struct S {
2305                template <class U> void f (U);
2306              };
2307              template <> template <class U> void S<int>::f(U) {}
2308
2309            That's a specialization -- but of the entire template.  */
2310         specialization = 1;
2311       break;
2312
2313     default:
2314       gcc_unreachable ();
2315     }
2316
2317   if (specialization || member_specialization)
2318     {
2319       tree t = TYPE_ARG_TYPES (TREE_TYPE (decl));
2320       for (; t; t = TREE_CHAIN (t))
2321         if (TREE_PURPOSE (t))
2322           {
2323             permerror (input_location, 
2324                        "default argument specified in explicit specialization");
2325             break;
2326           }
2327     }
2328
2329   if (specialization || member_specialization || explicit_instantiation)
2330     {
2331       tree tmpl = NULL_TREE;
2332       tree targs = NULL_TREE;
2333
2334       /* Make sure that the declarator is a TEMPLATE_ID_EXPR.  */
2335       if (TREE_CODE (declarator) != TEMPLATE_ID_EXPR)
2336         {
2337           tree fns;
2338
2339           gcc_assert (TREE_CODE (declarator) == IDENTIFIER_NODE);
2340           if (ctype)
2341             fns = dname;
2342           else
2343             {
2344               /* If there is no class context, the explicit instantiation
2345                  must be at namespace scope.  */
2346               gcc_assert (DECL_NAMESPACE_SCOPE_P (decl));
2347
2348               /* Find the namespace binding, using the declaration
2349                  context.  */
2350               fns = lookup_qualified_name (CP_DECL_CONTEXT (decl), dname,
2351                                            false, true);
2352               if (fns == error_mark_node || !is_overloaded_fn (fns))
2353                 {
2354                   error ("%qD is not a template function", dname);
2355                   fns = error_mark_node;
2356                 }
2357               else
2358                 {
2359                   tree fn = OVL_CURRENT (fns);
2360                   if (!is_associated_namespace (CP_DECL_CONTEXT (decl),
2361                                                 CP_DECL_CONTEXT (fn)))
2362                     error ("%qD is not declared in %qD",
2363                            decl, current_namespace);
2364                 }
2365             }
2366
2367           declarator = lookup_template_function (fns, NULL_TREE);
2368         }
2369
2370       if (declarator == error_mark_node)
2371         return error_mark_node;
2372
2373       if (ctype != NULL_TREE && TYPE_BEING_DEFINED (ctype))
2374         {
2375           if (!explicit_instantiation)
2376             /* A specialization in class scope.  This is invalid,
2377                but the error will already have been flagged by
2378                check_specialization_scope.  */
2379             return error_mark_node;
2380           else
2381             {
2382               /* It's not valid to write an explicit instantiation in
2383                  class scope, e.g.:
2384
2385                    class C { template void f(); }
2386
2387                    This case is caught by the parser.  However, on
2388                    something like:
2389
2390                    template class C { void f(); };
2391
2392                    (which is invalid) we can get here.  The error will be
2393                    issued later.  */
2394               ;
2395             }
2396
2397           return decl;
2398         }
2399       else if (ctype != NULL_TREE
2400                && (TREE_CODE (TREE_OPERAND (declarator, 0)) ==
2401                    IDENTIFIER_NODE))
2402         {
2403           /* Find the list of functions in ctype that have the same
2404              name as the declared function.  */
2405           tree name = TREE_OPERAND (declarator, 0);
2406           tree fns = NULL_TREE;
2407           int idx;
2408
2409           if (constructor_name_p (name, ctype))
2410             {
2411               int is_constructor = DECL_CONSTRUCTOR_P (decl);
2412
2413               if (is_constructor ? !TYPE_HAS_USER_CONSTRUCTOR (ctype)
2414                   : !CLASSTYPE_DESTRUCTORS (ctype))
2415                 {
2416                   /* From [temp.expl.spec]:
2417
2418                      If such an explicit specialization for the member
2419                      of a class template names an implicitly-declared
2420                      special member function (clause _special_), the
2421                      program is ill-formed.
2422
2423                      Similar language is found in [temp.explicit].  */
2424                   error ("specialization of implicitly-declared special member function");
2425                   return error_mark_node;
2426                 }
2427
2428               name = is_constructor ? ctor_identifier : dtor_identifier;
2429             }
2430
2431           if (!DECL_CONV_FN_P (decl))
2432             {
2433               idx = lookup_fnfields_1 (ctype, name);
2434               if (idx >= 0)
2435                 fns = VEC_index (tree, CLASSTYPE_METHOD_VEC (ctype), idx);
2436             }
2437           else
2438             {
2439               VEC(tree,gc) *methods;
2440               tree ovl;
2441
2442               /* For a type-conversion operator, we cannot do a
2443                  name-based lookup.  We might be looking for `operator
2444                  int' which will be a specialization of `operator T'.
2445                  So, we find *all* the conversion operators, and then
2446                  select from them.  */
2447               fns = NULL_TREE;
2448
2449               methods = CLASSTYPE_METHOD_VEC (ctype);
2450               if (methods)
2451                 for (idx = CLASSTYPE_FIRST_CONVERSION_SLOT;
2452                      VEC_iterate (tree, methods, idx, ovl);
2453                      ++idx)
2454                   {
2455                     if (!DECL_CONV_FN_P (OVL_CURRENT (ovl)))
2456                       /* There are no more conversion functions.  */
2457                       break;
2458
2459                     /* Glue all these conversion functions together
2460                        with those we already have.  */
2461                     for (; ovl; ovl = OVL_NEXT (ovl))
2462                       fns = ovl_cons (OVL_CURRENT (ovl), fns);
2463                   }
2464             }
2465
2466           if (fns == NULL_TREE)
2467             {
2468               error ("no member function %qD declared in %qT", name, ctype);
2469               return error_mark_node;
2470             }
2471           else
2472             TREE_OPERAND (declarator, 0) = fns;
2473         }
2474
2475       /* Figure out what exactly is being specialized at this point.
2476          Note that for an explicit instantiation, even one for a
2477          member function, we cannot tell apriori whether the
2478          instantiation is for a member template, or just a member
2479          function of a template class.  Even if a member template is
2480          being instantiated, the member template arguments may be
2481          elided if they can be deduced from the rest of the
2482          declaration.  */
2483       tmpl = determine_specialization (declarator, decl,
2484                                        &targs,
2485                                        member_specialization,
2486                                        template_count,
2487                                        tsk);
2488
2489       if (!tmpl || tmpl == error_mark_node)
2490         /* We couldn't figure out what this declaration was
2491            specializing.  */
2492         return error_mark_node;
2493       else
2494         {
2495           tree gen_tmpl = most_general_template (tmpl);
2496
2497           if (explicit_instantiation)
2498             {
2499               /* We don't set DECL_EXPLICIT_INSTANTIATION here; that
2500                  is done by do_decl_instantiation later.  */
2501
2502               int arg_depth = TMPL_ARGS_DEPTH (targs);
2503               int parm_depth = TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl));
2504
2505               if (arg_depth > parm_depth)
2506                 {
2507                   /* If TMPL is not the most general template (for
2508                      example, if TMPL is a friend template that is
2509                      injected into namespace scope), then there will
2510                      be too many levels of TARGS.  Remove some of them
2511                      here.  */
2512                   int i;
2513                   tree new_targs;
2514
2515                   new_targs = make_tree_vec (parm_depth);
2516                   for (i = arg_depth - parm_depth; i < arg_depth; ++i)
2517                     TREE_VEC_ELT (new_targs, i - (arg_depth - parm_depth))
2518                       = TREE_VEC_ELT (targs, i);
2519                   targs = new_targs;
2520                 }
2521
2522               return instantiate_template (tmpl, targs, tf_error);
2523             }
2524
2525           /* If we thought that the DECL was a member function, but it
2526              turns out to be specializing a static member function,
2527              make DECL a static member function as well.  */
2528           if (DECL_STATIC_FUNCTION_P (tmpl)
2529               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2530             revert_static_member_fn (decl);
2531
2532           /* If this is a specialization of a member template of a
2533              template class, we want to return the TEMPLATE_DECL, not
2534              the specialization of it.  */
2535           if (tsk == tsk_template)
2536             {
2537               tree result = DECL_TEMPLATE_RESULT (tmpl);
2538               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
2539               DECL_INITIAL (result) = NULL_TREE;
2540               if (have_def)
2541                 {
2542                   tree parm;
2543                   DECL_SOURCE_LOCATION (tmpl) = DECL_SOURCE_LOCATION (decl);
2544                   DECL_SOURCE_LOCATION (result)
2545                     = DECL_SOURCE_LOCATION (decl);
2546                   /* We want to use the argument list specified in the
2547                      definition, not in the original declaration.  */
2548                   DECL_ARGUMENTS (result) = DECL_ARGUMENTS (decl);
2549                   for (parm = DECL_ARGUMENTS (result); parm;
2550                        parm = TREE_CHAIN (parm))
2551                     DECL_CONTEXT (parm) = result;
2552                 }
2553               return register_specialization (tmpl, gen_tmpl, targs,
2554                                               is_friend, 0);
2555             }
2556
2557           /* Set up the DECL_TEMPLATE_INFO for DECL.  */
2558           DECL_TEMPLATE_INFO (decl) = build_template_info (tmpl, targs);
2559
2560           /* Inherit default function arguments from the template
2561              DECL is specializing.  */
2562           copy_default_args_to_explicit_spec (decl);
2563
2564           /* This specialization has the same protection as the
2565              template it specializes.  */
2566           TREE_PRIVATE (decl) = TREE_PRIVATE (gen_tmpl);
2567           TREE_PROTECTED (decl) = TREE_PROTECTED (gen_tmpl);
2568
2569           /* 7.1.1-1 [dcl.stc]
2570
2571              A storage-class-specifier shall not be specified in an
2572              explicit specialization...
2573
2574              The parser rejects these, so unless action is taken here,
2575              explicit function specializations will always appear with
2576              global linkage.
2577
2578              The action recommended by the C++ CWG in response to C++
2579              defect report 605 is to make the storage class and linkage
2580              of the explicit specialization match the templated function:
2581
2582              http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#605
2583            */
2584           if (tsk == tsk_expl_spec && DECL_FUNCTION_TEMPLATE_P (gen_tmpl))
2585             {
2586               tree tmpl_func = DECL_TEMPLATE_RESULT (gen_tmpl);
2587               gcc_assert (TREE_CODE (tmpl_func) == FUNCTION_DECL);
2588
2589               /* This specialization has the same linkage and visibility as
2590                  the function template it specializes.  */
2591               TREE_PUBLIC (decl) = TREE_PUBLIC (tmpl_func);
2592               if (! TREE_PUBLIC (decl))
2593                 {
2594                   DECL_INTERFACE_KNOWN (decl) = 1;
2595                   DECL_NOT_REALLY_EXTERN (decl) = 1;
2596                 }
2597               DECL_THIS_STATIC (decl) = DECL_THIS_STATIC (tmpl_func);
2598               if (DECL_VISIBILITY_SPECIFIED (tmpl_func))
2599                 {
2600                   DECL_VISIBILITY_SPECIFIED (decl) = 1;
2601                   DECL_VISIBILITY (decl) = DECL_VISIBILITY (tmpl_func);
2602                 }
2603             }
2604
2605           /* If DECL is a friend declaration, declared using an
2606              unqualified name, the namespace associated with DECL may
2607              have been set incorrectly.  For example, in:
2608
2609                template <typename T> void f(T);
2610                namespace N {
2611                  struct S { friend void f<int>(int); }
2612                }
2613
2614              we will have set the DECL_CONTEXT for the friend
2615              declaration to N, rather than to the global namespace.  */
2616           if (DECL_NAMESPACE_SCOPE_P (decl))
2617             DECL_CONTEXT (decl) = DECL_CONTEXT (tmpl);
2618
2619           if (is_friend && !have_def)
2620             /* This is not really a declaration of a specialization.
2621                It's just the name of an instantiation.  But, it's not
2622                a request for an instantiation, either.  */
2623             SET_DECL_IMPLICIT_INSTANTIATION (decl);
2624           else if (DECL_CONSTRUCTOR_P (decl) || DECL_DESTRUCTOR_P (decl))
2625             /* This is indeed a specialization.  In case of constructors
2626                and destructors, we need in-charge and not-in-charge
2627                versions in V3 ABI.  */
2628             clone_function_decl (decl, /*update_method_vec_p=*/0);
2629
2630           /* Register this specialization so that we can find it
2631              again.  */
2632           decl = register_specialization (decl, gen_tmpl, targs, is_friend, 0);
2633         }
2634     }
2635
2636   return decl;
2637 }
2638
2639 /* Returns 1 iff PARMS1 and PARMS2 are identical sets of template
2640    parameters.  These are represented in the same format used for
2641    DECL_TEMPLATE_PARMS.  */
2642
2643 int
2644 comp_template_parms (const_tree parms1, const_tree parms2)
2645 {
2646   const_tree p1;
2647   const_tree p2;
2648
2649   if (parms1 == parms2)
2650     return 1;
2651
2652   for (p1 = parms1, p2 = parms2;
2653        p1 != NULL_TREE && p2 != NULL_TREE;
2654        p1 = TREE_CHAIN (p1), p2 = TREE_CHAIN (p2))
2655     {
2656       tree t1 = TREE_VALUE (p1);
2657       tree t2 = TREE_VALUE (p2);
2658       int i;
2659
2660       gcc_assert (TREE_CODE (t1) == TREE_VEC);
2661       gcc_assert (TREE_CODE (t2) == TREE_VEC);
2662
2663       if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2664         return 0;
2665
2666       for (i = 0; i < TREE_VEC_LENGTH (t2); ++i)
2667         {
2668           tree parm1 = TREE_VALUE (TREE_VEC_ELT (t1, i));
2669           tree parm2 = TREE_VALUE (TREE_VEC_ELT (t2, i));
2670
2671           /* If either of the template parameters are invalid, assume
2672              they match for the sake of error recovery. */
2673           if (parm1 == error_mark_node || parm2 == error_mark_node)
2674             return 1;
2675
2676           if (TREE_CODE (parm1) != TREE_CODE (parm2))
2677             return 0;
2678
2679           if (TREE_CODE (parm1) == TEMPLATE_TYPE_PARM
2680               && (TEMPLATE_TYPE_PARAMETER_PACK (parm1)
2681                   == TEMPLATE_TYPE_PARAMETER_PACK (parm2)))
2682             continue;
2683           else if (!same_type_p (TREE_TYPE (parm1), TREE_TYPE (parm2)))
2684             return 0;
2685         }
2686     }
2687
2688   if ((p1 != NULL_TREE) != (p2 != NULL_TREE))
2689     /* One set of parameters has more parameters lists than the
2690        other.  */
2691     return 0;
2692
2693   return 1;
2694 }
2695
2696 /* Determine whether PARM is a parameter pack.  */
2697
2698 bool 
2699 template_parameter_pack_p (const_tree parm)
2700 {
2701   /* Determine if we have a non-type template parameter pack.  */
2702   if (TREE_CODE (parm) == PARM_DECL)
2703     return (DECL_TEMPLATE_PARM_P (parm) 
2704             && TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)));
2705
2706   /* If this is a list of template parameters, we could get a
2707      TYPE_DECL or a TEMPLATE_DECL.  */ 
2708   if (TREE_CODE (parm) == TYPE_DECL || TREE_CODE (parm) == TEMPLATE_DECL)
2709     parm = TREE_TYPE (parm);
2710
2711   return ((TREE_CODE (parm) == TEMPLATE_TYPE_PARM
2712            || TREE_CODE (parm) == TEMPLATE_TEMPLATE_PARM)
2713           && TEMPLATE_TYPE_PARAMETER_PACK (parm));
2714 }
2715
2716 /* Determine if T is a function parameter pack.  */
2717
2718 bool
2719 function_parameter_pack_p (const_tree t)
2720 {
2721   if (t && TREE_CODE (t) == PARM_DECL)
2722     return FUNCTION_PARAMETER_PACK_P (t);
2723   return false;
2724 }
2725
2726 /* Return the function template declaration of PRIMARY_FUNC_TMPL_INST.
2727    PRIMARY_FUNC_TMPL_INST is a primary function template instantiation.  */
2728
2729 tree
2730 get_function_template_decl (const_tree primary_func_tmpl_inst)
2731 {
2732   if (! primary_func_tmpl_inst
2733       || TREE_CODE (primary_func_tmpl_inst) != FUNCTION_DECL
2734       || ! primary_template_instantiation_p (primary_func_tmpl_inst))
2735     return NULL;
2736
2737   return DECL_TEMPLATE_RESULT (DECL_TI_TEMPLATE (primary_func_tmpl_inst));
2738 }
2739
2740 /* Return true iff the function parameter PARAM_DECL was expanded
2741    from the function parameter pack PACK.  */
2742
2743 bool
2744 function_parameter_expanded_from_pack_p (tree param_decl, tree pack)
2745 {
2746   if (DECL_ARTIFICIAL (param_decl)
2747       || !function_parameter_pack_p (pack))
2748     return false;
2749
2750   /* The parameter pack and its pack arguments have the same
2751      DECL_PARM_INDEX.  */
2752   return DECL_PARM_INDEX (pack) == DECL_PARM_INDEX (param_decl);
2753 }
2754
2755 /* Determine whether ARGS describes a variadic template args list,
2756    i.e., one that is terminated by a template argument pack.  */
2757
2758 static bool 
2759 template_args_variadic_p (tree args)
2760 {
2761   int nargs;
2762   tree last_parm;
2763
2764   if (args == NULL_TREE)
2765     return false;
2766
2767   args = INNERMOST_TEMPLATE_ARGS (args);
2768   nargs = TREE_VEC_LENGTH (args);
2769
2770   if (nargs == 0)
2771     return false;
2772
2773   last_parm = TREE_VEC_ELT (args, nargs - 1);
2774
2775   return ARGUMENT_PACK_P (last_parm);
2776 }
2777
2778 /* Generate a new name for the parameter pack name NAME (an
2779    IDENTIFIER_NODE) that incorporates its */
2780
2781 static tree
2782 make_ith_pack_parameter_name (tree name, int i)
2783 {
2784   /* Munge the name to include the parameter index.  */
2785 #define NUMBUF_LEN 128
2786   char numbuf[NUMBUF_LEN];
2787   char* newname;
2788   int newname_len;
2789
2790   snprintf (numbuf, NUMBUF_LEN, "%i", i);
2791   newname_len = IDENTIFIER_LENGTH (name)
2792                 + strlen (numbuf) + 2;
2793   newname = (char*)alloca (newname_len);
2794   snprintf (newname, newname_len,
2795             "%s#%i", IDENTIFIER_POINTER (name), i);
2796   return get_identifier (newname);
2797 }
2798
2799 /* Return true if T is a primary function
2800    or class template instantiation.  */
2801
2802 bool
2803 primary_template_instantiation_p (const_tree t)
2804 {
2805   if (!t)
2806     return false;
2807
2808   if (TREE_CODE (t) == FUNCTION_DECL)
2809     return DECL_LANG_SPECIFIC (t)
2810            && DECL_TEMPLATE_INSTANTIATION (t)
2811            && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (t));
2812   else if (CLASS_TYPE_P (t))
2813     return CLASSTYPE_TEMPLATE_INSTANTIATION (t)
2814            && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (t));
2815   return false;
2816 }
2817
2818 /* Return true if PARM is a template template parameter.  */
2819
2820 bool
2821 template_template_parameter_p (const_tree parm)
2822 {
2823   return DECL_TEMPLATE_TEMPLATE_PARM_P (parm);
2824 }
2825
2826 /* Return the template parameters of T if T is a
2827    primary template instantiation, NULL otherwise.  */
2828
2829 tree
2830 get_primary_template_innermost_parameters (const_tree t)
2831 {
2832   tree parms = NULL, template_info = NULL;
2833
2834   if ((template_info = get_template_info (t))
2835       && primary_template_instantiation_p (t))
2836     parms = INNERMOST_TEMPLATE_PARMS
2837         (DECL_TEMPLATE_PARMS (TI_TEMPLATE (template_info)));
2838
2839   return parms;
2840 }
2841
2842 /* Returns the template arguments of T if T is a template instantiation,
2843    NULL otherwise.  */
2844
2845 tree
2846 get_template_innermost_arguments (const_tree t)
2847 {
2848   tree args = NULL, template_info = NULL;
2849
2850   if ((template_info = get_template_info (t))
2851       && TI_ARGS (template_info))
2852     args = INNERMOST_TEMPLATE_ARGS (TI_ARGS (template_info));
2853
2854   return args;
2855 }
2856
2857 /* Return the argument pack elements of T if T is a template argument pack,
2858    NULL otherwise.  */
2859
2860 tree
2861 get_template_argument_pack_elems (const_tree t)
2862 {
2863   if (TREE_CODE (t) != TYPE_ARGUMENT_PACK
2864       && TREE_CODE (t) != NONTYPE_ARGUMENT_PACK)
2865     return NULL;
2866
2867   return ARGUMENT_PACK_ARGS (t);
2868 }
2869
2870 /* Structure used to track the progress of find_parameter_packs_r.  */
2871 struct find_parameter_pack_data 
2872 {
2873   /* TREE_LIST that will contain all of the parameter packs found by
2874      the traversal.  */
2875   tree* parameter_packs;
2876
2877   /* Set of AST nodes that have been visited by the traversal.  */
2878   struct pointer_set_t *visited;
2879 };
2880
2881 /* Identifies all of the argument packs that occur in a template
2882    argument and appends them to the TREE_LIST inside DATA, which is a
2883    find_parameter_pack_data structure. This is a subroutine of
2884    make_pack_expansion and uses_parameter_packs.  */
2885 static tree
2886 find_parameter_packs_r (tree *tp, int *walk_subtrees, void* data)
2887 {
2888   tree t = *tp;
2889   struct find_parameter_pack_data* ppd = 
2890     (struct find_parameter_pack_data*)data;
2891   bool parameter_pack_p = false;
2892
2893   /* Identify whether this is a parameter pack or not.  */
2894   switch (TREE_CODE (t))
2895     {
2896     case TEMPLATE_PARM_INDEX:
2897       if (TEMPLATE_PARM_PARAMETER_PACK (t))
2898         parameter_pack_p = true;
2899       break;
2900
2901     case TEMPLATE_TYPE_PARM:
2902     case TEMPLATE_TEMPLATE_PARM:
2903       if (TEMPLATE_TYPE_PARAMETER_PACK (t))
2904         parameter_pack_p = true;
2905       break;
2906
2907     case PARM_DECL:
2908       if (FUNCTION_PARAMETER_PACK_P (t))
2909         {
2910           /* We don't want to walk into the type of a PARM_DECL,
2911              because we don't want to see the type parameter pack.  */
2912           *walk_subtrees = 0;
2913           parameter_pack_p = true;
2914         }
2915       break;
2916
2917     default:
2918       /* Not a parameter pack.  */
2919       break;
2920     }
2921
2922   if (parameter_pack_p)
2923     {
2924       /* Add this parameter pack to the list.  */
2925       *ppd->parameter_packs = tree_cons (NULL_TREE, t, *ppd->parameter_packs);
2926     }
2927
2928   if (TYPE_P (t))
2929     cp_walk_tree (&TYPE_CONTEXT (t), 
2930                   &find_parameter_packs_r, ppd, ppd->visited);
2931
2932   /* This switch statement will return immediately if we don't find a
2933      parameter pack.  */
2934   switch (TREE_CODE (t)) 
2935     {
2936     case TEMPLATE_PARM_INDEX:
2937       return NULL_TREE;
2938
2939     case BOUND_TEMPLATE_TEMPLATE_PARM:
2940       /* Check the template itself.  */
2941       cp_walk_tree (&TREE_TYPE (TYPE_TI_TEMPLATE (t)), 
2942                     &find_parameter_packs_r, ppd, ppd->visited);
2943       /* Check the template arguments.  */
2944       cp_walk_tree (&TYPE_TI_ARGS (t), &find_parameter_packs_r, ppd, 
2945                     ppd->visited);
2946       *walk_subtrees = 0;
2947       return NULL_TREE;
2948
2949     case TEMPLATE_TYPE_PARM:
2950     case TEMPLATE_TEMPLATE_PARM:
2951       return NULL_TREE;
2952
2953     case PARM_DECL:
2954       return NULL_TREE;
2955
2956     case RECORD_TYPE:
2957       if (TYPE_PTRMEMFUNC_P (t))
2958         return NULL_TREE;
2959       /* Fall through.  */
2960
2961     case UNION_TYPE:
2962     case ENUMERAL_TYPE:
2963       if (TYPE_TEMPLATE_INFO (t))
2964         cp_walk_tree (&TI_ARGS (TYPE_TEMPLATE_INFO (t)),
2965                       &find_parameter_packs_r, ppd, ppd->visited);
2966
2967       *walk_subtrees = 0;
2968       return NULL_TREE;
2969
2970     case TEMPLATE_DECL:
2971       cp_walk_tree (&TREE_TYPE (t),
2972                     &find_parameter_packs_r, ppd, ppd->visited);
2973       return NULL_TREE;
2974  
2975     case TYPENAME_TYPE:
2976       cp_walk_tree (&TYPENAME_TYPE_FULLNAME (t), &find_parameter_packs_r,
2977                    ppd, ppd->visited);
2978       *walk_subtrees = 0;
2979       return NULL_TREE;
2980       
2981     case TYPE_PACK_EXPANSION:
2982     case EXPR_PACK_EXPANSION:
2983       *walk_subtrees = 0;
2984       return NULL_TREE;
2985
2986     case INTEGER_TYPE:
2987       cp_walk_tree (&TYPE_MAX_VALUE (t), &find_parameter_packs_r, 
2988                     ppd, ppd->visited);
2989       *walk_subtrees = 0;
2990       return NULL_TREE;
2991
2992     case IDENTIFIER_NODE:
2993       cp_walk_tree (&TREE_TYPE (t), &find_parameter_packs_r, ppd, 
2994                     ppd->visited);
2995       *walk_subtrees = 0;
2996       return NULL_TREE;
2997
2998     default:
2999       return NULL_TREE;
3000     }
3001
3002   return NULL_TREE;
3003 }
3004
3005 /* Determines if the expression or type T uses any parameter packs.  */
3006 bool
3007 uses_parameter_packs (tree t)
3008 {
3009   tree parameter_packs = NULL_TREE;
3010   struct find_parameter_pack_data ppd;
3011   ppd.parameter_packs = &parameter_packs;
3012   ppd.visited = pointer_set_create ();
3013   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3014   pointer_set_destroy (ppd.visited);
3015   return parameter_packs != NULL_TREE;
3016 }
3017
3018 /* Turn ARG, which may be an expression, type, or a TREE_LIST
3019    representation a base-class initializer into a parameter pack
3020    expansion. If all goes well, the resulting node will be an
3021    EXPR_PACK_EXPANSION, TYPE_PACK_EXPANSION, or TREE_LIST,
3022    respectively.  */
3023 tree 
3024 make_pack_expansion (tree arg)
3025 {
3026   tree result;
3027   tree parameter_packs = NULL_TREE;
3028   bool for_types = false;
3029   struct find_parameter_pack_data ppd;
3030
3031   if (!arg || arg == error_mark_node)
3032     return arg;
3033
3034   if (TREE_CODE (arg) == TREE_LIST)
3035     {
3036       /* The only time we will see a TREE_LIST here is for a base
3037          class initializer.  In this case, the TREE_PURPOSE will be a
3038          _TYPE node (representing the base class expansion we're
3039          initializing) and the TREE_VALUE will be a TREE_LIST
3040          containing the initialization arguments. 
3041
3042          The resulting expansion looks somewhat different from most
3043          expansions. Rather than returning just one _EXPANSION, we
3044          return a TREE_LIST whose TREE_PURPOSE is a
3045          TYPE_PACK_EXPANSION containing the bases that will be
3046          initialized.  The TREE_VALUE will be identical to the
3047          original TREE_VALUE, which is a list of arguments that will
3048          be passed to each base.  We do not introduce any new pack
3049          expansion nodes into the TREE_VALUE (although it is possible
3050          that some already exist), because the TREE_PURPOSE and
3051          TREE_VALUE all need to be expanded together with the same
3052          _EXPANSION node.  Note that the TYPE_PACK_EXPANSION in the
3053          resulting TREE_PURPOSE will mention the parameter packs in
3054          both the bases and the arguments to the bases.  */
3055       tree purpose;
3056       tree value;
3057       tree parameter_packs = NULL_TREE;
3058
3059       /* Determine which parameter packs will be used by the base
3060          class expansion.  */
3061       ppd.visited = pointer_set_create ();
3062       ppd.parameter_packs = &parameter_packs;
3063       cp_walk_tree (&TREE_PURPOSE (arg), &find_parameter_packs_r, 
3064                     &ppd, ppd.visited);
3065
3066       if (parameter_packs == NULL_TREE)
3067         {
3068           error ("base initializer expansion %<%T%> contains no parameter packs", arg);
3069           pointer_set_destroy (ppd.visited);
3070           return error_mark_node;
3071         }
3072
3073       if (TREE_VALUE (arg) != void_type_node)
3074         {
3075           /* Collect the sets of parameter packs used in each of the
3076              initialization arguments.  */
3077           for (value = TREE_VALUE (arg); value; value = TREE_CHAIN (value))
3078             {
3079               /* Determine which parameter packs will be expanded in this
3080                  argument.  */
3081               cp_walk_tree (&TREE_VALUE (value), &find_parameter_packs_r, 
3082                             &ppd, ppd.visited);
3083             }
3084         }
3085
3086       pointer_set_destroy (ppd.visited);
3087
3088       /* Create the pack expansion type for the base type.  */
3089       purpose = cxx_make_type (TYPE_PACK_EXPANSION);
3090       SET_PACK_EXPANSION_PATTERN (purpose, TREE_PURPOSE (arg));
3091       PACK_EXPANSION_PARAMETER_PACKS (purpose) = parameter_packs;
3092
3093       /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3094          they will rarely be compared to anything.  */
3095       SET_TYPE_STRUCTURAL_EQUALITY (purpose);
3096
3097       return tree_cons (purpose, TREE_VALUE (arg), NULL_TREE);
3098     }
3099
3100   if (TYPE_P (arg) || TREE_CODE (arg) == TEMPLATE_DECL)
3101     for_types = true;
3102
3103   /* Build the PACK_EXPANSION_* node.  */
3104   result = for_types
3105      ? cxx_make_type (TYPE_PACK_EXPANSION)
3106      : make_node (EXPR_PACK_EXPANSION);
3107   SET_PACK_EXPANSION_PATTERN (result, arg);
3108   if (TREE_CODE (result) == EXPR_PACK_EXPANSION)
3109     {
3110       /* Propagate type and const-expression information.  */
3111       TREE_TYPE (result) = TREE_TYPE (arg);
3112       TREE_CONSTANT (result) = TREE_CONSTANT (arg);
3113     }
3114   else
3115     /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3116        they will rarely be compared to anything.  */
3117     SET_TYPE_STRUCTURAL_EQUALITY (result);
3118
3119   /* Determine which parameter packs will be expanded.  */
3120   ppd.parameter_packs = &parameter_packs;
3121   ppd.visited = pointer_set_create ();
3122   cp_walk_tree (&arg, &find_parameter_packs_r, &ppd, ppd.visited);
3123   pointer_set_destroy (ppd.visited);
3124
3125   /* Make sure we found some parameter packs.  */
3126   if (parameter_packs == NULL_TREE)
3127     {
3128       if (TYPE_P (arg))
3129         error ("expansion pattern %<%T%> contains no argument packs", arg);
3130       else
3131         error ("expansion pattern %<%E%> contains no argument packs", arg);
3132       return error_mark_node;
3133     }
3134   PACK_EXPANSION_PARAMETER_PACKS (result) = parameter_packs;
3135
3136   return result;
3137 }
3138
3139 /* Checks T for any "bare" parameter packs, which have not yet been
3140    expanded, and issues an error if any are found. This operation can
3141    only be done on full expressions or types (e.g., an expression
3142    statement, "if" condition, etc.), because we could have expressions like:
3143
3144      foo(f(g(h(args)))...)
3145
3146    where "args" is a parameter pack. check_for_bare_parameter_packs
3147    should not be called for the subexpressions args, h(args),
3148    g(h(args)), or f(g(h(args))), because we would produce erroneous
3149    error messages. 
3150
3151    Returns TRUE and emits an error if there were bare parameter packs,
3152    returns FALSE otherwise.  */
3153 bool 
3154 check_for_bare_parameter_packs (tree t)
3155 {
3156   tree parameter_packs = NULL_TREE;
3157   struct find_parameter_pack_data ppd;
3158
3159   if (!processing_template_decl || !t || t == error_mark_node)
3160     return false;
3161
3162   if (TREE_CODE (t) == TYPE_DECL)
3163     t = TREE_TYPE (t);
3164
3165   ppd.parameter_packs = &parameter_packs;
3166   ppd.visited = pointer_set_create ();
3167   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3168   pointer_set_destroy (ppd.visited);
3169
3170   if (parameter_packs) 
3171     {
3172       error ("parameter packs not expanded with %<...%>:");
3173       while (parameter_packs)
3174         {
3175           tree pack = TREE_VALUE (parameter_packs);
3176           tree name = NULL_TREE;
3177
3178           if (TREE_CODE (pack) == TEMPLATE_TYPE_PARM
3179               || TREE_CODE (pack) == TEMPLATE_TEMPLATE_PARM)
3180             name = TYPE_NAME (pack);
3181           else if (TREE_CODE (pack) == TEMPLATE_PARM_INDEX)
3182             name = DECL_NAME (TEMPLATE_PARM_DECL (pack));
3183           else
3184             name = DECL_NAME (pack);
3185
3186           if (name)
3187             inform (input_location, "        %qD", name);
3188           else
3189             inform (input_location, "        <anonymous>");
3190
3191           parameter_packs = TREE_CHAIN (parameter_packs);
3192         }
3193
3194       return true;
3195     }
3196
3197   return false;
3198 }
3199
3200 /* Expand any parameter packs that occur in the template arguments in
3201    ARGS.  */
3202 tree
3203 expand_template_argument_pack (tree args)
3204 {
3205   tree result_args = NULL_TREE;
3206   int in_arg, out_arg = 0, nargs = args ? TREE_VEC_LENGTH (args) : 0;
3207   int num_result_args = -1;
3208
3209   /* First, determine if we need to expand anything, and the number of
3210      slots we'll need.  */
3211   for (in_arg = 0; in_arg < nargs; ++in_arg)
3212     {
3213       tree arg = TREE_VEC_ELT (args, in_arg);
3214       if (arg == NULL_TREE)
3215         return args;
3216       if (ARGUMENT_PACK_P (arg))
3217         {
3218           int num_packed = TREE_VEC_LENGTH (ARGUMENT_PACK_ARGS (arg));
3219           if (num_result_args < 0)
3220             num_result_args = in_arg + num_packed;
3221           else
3222             num_result_args += num_packed;
3223         }
3224       else
3225         {
3226           if (num_result_args >= 0)
3227             num_result_args++;
3228         }
3229     }
3230
3231   /* If no expansion is necessary, we're done.  */
3232   if (num_result_args < 0)
3233     return args;
3234
3235   /* Expand arguments.  */
3236   result_args = make_tree_vec (num_result_args);
3237   for (in_arg = 0; in_arg < nargs; ++in_arg)
3238     {
3239       tree arg = TREE_VEC_ELT (args, in_arg);
3240       if (ARGUMENT_PACK_P (arg))
3241         {
3242           tree packed = ARGUMENT_PACK_ARGS (arg);
3243           int i, num_packed = TREE_VEC_LENGTH (packed);
3244           for (i = 0; i < num_packed; ++i, ++out_arg)
3245             TREE_VEC_ELT (result_args, out_arg) = TREE_VEC_ELT(packed, i);
3246         }
3247       else
3248         {
3249           TREE_VEC_ELT (result_args, out_arg) = arg;
3250           ++out_arg;
3251         }
3252     }
3253
3254   return result_args;
3255 }
3256
3257 /* Checks if DECL shadows a template parameter.
3258
3259    [temp.local]: A template-parameter shall not be redeclared within its
3260    scope (including nested scopes).
3261
3262    Emits an error and returns TRUE if the DECL shadows a parameter,
3263    returns FALSE otherwise.  */
3264
3265 bool
3266 check_template_shadow (tree decl)
3267 {
3268   tree olddecl;
3269
3270   /* If we're not in a template, we can't possibly shadow a template
3271      parameter.  */
3272   if (!current_template_parms)
3273     return true;
3274
3275   /* Figure out what we're shadowing.  */
3276   if (TREE_CODE (decl) == OVERLOAD)
3277     decl = OVL_CURRENT (decl);
3278   olddecl = innermost_non_namespace_value (DECL_NAME (decl));
3279
3280   /* If there's no previous binding for this name, we're not shadowing
3281      anything, let alone a template parameter.  */
3282   if (!olddecl)
3283     return true;
3284
3285   /* If we're not shadowing a template parameter, we're done.  Note
3286      that OLDDECL might be an OVERLOAD (or perhaps even an
3287      ERROR_MARK), so we can't just blithely assume it to be a _DECL
3288      node.  */
3289   if (!DECL_P (olddecl) || !DECL_TEMPLATE_PARM_P (olddecl))
3290     return true;
3291
3292   /* We check for decl != olddecl to avoid bogus errors for using a
3293      name inside a class.  We check TPFI to avoid duplicate errors for
3294      inline member templates.  */
3295   if (decl == olddecl
3296       || TEMPLATE_PARMS_FOR_INLINE (current_template_parms))
3297     return true;
3298
3299   error ("declaration of %q+#D", decl);
3300   error (" shadows template parm %q+#D", olddecl);
3301   return false;
3302 }
3303
3304 /* Return a new TEMPLATE_PARM_INDEX with the indicated INDEX, LEVEL,
3305    ORIG_LEVEL, DECL, and TYPE.  */
3306
3307 static tree
3308 build_template_parm_index (int index,
3309                            int level,
3310                            int orig_level,
3311                            tree decl,
3312                            tree type)
3313 {
3314   tree t = make_node (TEMPLATE_PARM_INDEX);
3315   TEMPLATE_PARM_IDX (t) = index;
3316   TEMPLATE_PARM_LEVEL (t) = level;
3317   TEMPLATE_PARM_ORIG_LEVEL (t) = orig_level;
3318   TEMPLATE_PARM_DECL (t) = decl;
3319   TREE_TYPE (t) = type;
3320   TREE_CONSTANT (t) = TREE_CONSTANT (decl);
3321   TREE_READONLY (t) = TREE_READONLY (decl);
3322
3323   return t;
3324 }
3325
3326 /* Find the canonical type parameter for the given template type
3327    parameter.  Returns the canonical type parameter, which may be TYPE
3328    if no such parameter existed.  */
3329 static tree
3330 canonical_type_parameter (tree type)
3331 {
3332   tree list;
3333   int idx = TEMPLATE_TYPE_IDX (type);
3334   if (!canonical_template_parms)
3335     canonical_template_parms = VEC_alloc (tree, gc, idx+1);
3336
3337   while (VEC_length (tree, canonical_template_parms) <= (unsigned)idx)
3338     VEC_safe_push (tree, gc, canonical_template_parms, NULL_TREE);
3339
3340   list = VEC_index (tree, canonical_template_parms, idx);
3341   while (list && !comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
3342     list = TREE_CHAIN (list);
3343
3344   if (list)
3345     return TREE_VALUE (list);
3346   else
3347     {
3348       VEC_replace(tree, canonical_template_parms, idx,
3349                   tree_cons (NULL_TREE, type, 
3350                              VEC_index (tree, canonical_template_parms, idx)));
3351       return type;
3352     }
3353 }
3354
3355 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
3356    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
3357    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
3358    new one is created.  */
3359
3360 static tree
3361 reduce_template_parm_level (tree index, tree type, int levels, tree args,
3362                             tsubst_flags_t complain)
3363 {
3364   if (TEMPLATE_PARM_DESCENDANTS (index) == NULL_TREE
3365       || (TEMPLATE_PARM_LEVEL (TEMPLATE_PARM_DESCENDANTS (index))
3366           != TEMPLATE_PARM_LEVEL (index) - levels)
3367       || !same_type_p (type, TREE_TYPE (TEMPLATE_PARM_DESCENDANTS (index))))
3368     {
3369       tree orig_decl = TEMPLATE_PARM_DECL (index);
3370       tree decl, t;
3371
3372       decl = build_decl (DECL_SOURCE_LOCATION (orig_decl),
3373                          TREE_CODE (orig_decl), DECL_NAME (orig_decl), type);
3374       TREE_CONSTANT (decl) = TREE_CONSTANT (orig_decl);
3375       TREE_READONLY (decl) = TREE_READONLY (orig_decl);
3376       DECL_ARTIFICIAL (decl) = 1;
3377       SET_DECL_TEMPLATE_PARM_P (decl);
3378
3379       t = build_template_parm_index (TEMPLATE_PARM_IDX (index),
3380                                      TEMPLATE_PARM_LEVEL (index) - levels,
3381                                      TEMPLATE_PARM_ORIG_LEVEL (index),
3382                                      decl, type);
3383       TEMPLATE_PARM_DESCENDANTS (index) = t;
3384       TEMPLATE_PARM_PARAMETER_PACK (t) 
3385         = TEMPLATE_PARM_PARAMETER_PACK (index);
3386
3387         /* Template template parameters need this.  */
3388       if (TREE_CODE (decl) == TEMPLATE_DECL)
3389         DECL_TEMPLATE_PARMS (decl) = tsubst_template_parms
3390           (DECL_TEMPLATE_PARMS (TEMPLATE_PARM_DECL (index)),
3391            args, complain);
3392     }
3393
3394   return TEMPLATE_PARM_DESCENDANTS (index);
3395 }
3396
3397 /* Process information from new template parameter PARM and append it to the
3398    LIST being built.  This new parameter is a non-type parameter iff
3399    IS_NON_TYPE is true. This new parameter is a parameter
3400    pack iff IS_PARAMETER_PACK is true.  The location of PARM is in 
3401    PARM_LOC.  */
3402
3403 tree
3404 process_template_parm (tree list, location_t parm_loc, tree parm, bool is_non_type, 
3405                        bool is_parameter_pack)
3406 {
3407   tree decl = 0;
3408   tree defval;
3409   tree err_parm_list;
3410   int idx = 0;
3411
3412   gcc_assert (TREE_CODE (parm) == TREE_LIST);
3413   defval = TREE_PURPOSE (parm);
3414
3415   if (list)
3416     {
3417       tree p = tree_last (list);
3418
3419       if (p && TREE_VALUE (p) != error_mark_node)
3420         {
3421           p = TREE_VALUE (p);
3422           if (TREE_CODE (p) == TYPE_DECL || TREE_CODE (p) == TEMPLATE_DECL)
3423             idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
3424           else
3425             idx = TEMPLATE_PARM_IDX (DECL_INITIAL (p));
3426         }
3427
3428       ++idx;
3429     }
3430   else
3431     idx = 0;
3432
3433   if (is_non_type)
3434     {
3435       parm = TREE_VALUE (parm);
3436
3437       SET_DECL_TEMPLATE_PARM_P (parm);
3438
3439       if (TREE_TYPE (parm) == error_mark_node)
3440         {
3441           err_parm_list = build_tree_list (defval, parm);
3442           TREE_VALUE (err_parm_list) = error_mark_node;
3443            return chainon (list, err_parm_list);
3444         }
3445       else
3446       {
3447         /* [temp.param]
3448
3449            The top-level cv-qualifiers on the template-parameter are
3450            ignored when determining its type.  */
3451         TREE_TYPE (parm) = TYPE_MAIN_VARIANT (TREE_TYPE (parm));
3452         if (invalid_nontype_parm_type_p (TREE_TYPE (parm), 1))
3453           {
3454             err_parm_list = build_tree_list (defval, parm);
3455             TREE_VALUE (err_parm_list) = error_mark_node;
3456              return chainon (list, err_parm_list);
3457           }
3458
3459         if (uses_parameter_packs (TREE_TYPE (parm)) && !is_parameter_pack)
3460           {
3461             /* This template parameter is not a parameter pack, but it
3462                should be. Complain about "bare" parameter packs.  */
3463             check_for_bare_parameter_packs (TREE_TYPE (parm));
3464             
3465             /* Recover by calling this a parameter pack.  */
3466             is_parameter_pack = true;
3467           }
3468       }
3469
3470       /* A template parameter is not modifiable.  */
3471       TREE_CONSTANT (parm) = 1;
3472       TREE_READONLY (parm) = 1;
3473       decl = build_decl (parm_loc,
3474                          CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
3475       TREE_CONSTANT (decl) = 1;
3476       TREE_READONLY (decl) = 1;
3477       DECL_INITIAL (parm) = DECL_INITIAL (decl)
3478         = build_template_parm_index (idx, processing_template_decl,
3479                                      processing_template_decl,
3480                                      decl, TREE_TYPE (parm));
3481
3482       TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)) 
3483         = is_parameter_pack;
3484     }
3485   else
3486     {
3487       tree t;
3488       parm = TREE_VALUE (TREE_VALUE (parm));
3489
3490       if (parm && TREE_CODE (parm) == TEMPLATE_DECL)
3491         {
3492           t = cxx_make_type (TEMPLATE_TEMPLATE_PARM);
3493           /* This is for distinguishing between real templates and template
3494              template parameters */
3495           TREE_TYPE (parm) = t;
3496           TREE_TYPE (DECL_TEMPLATE_RESULT (parm)) = t;
3497           decl = parm;
3498         }
3499       else
3500         {
3501           t = cxx_make_type (TEMPLATE_TYPE_PARM);
3502           /* parm is either IDENTIFIER_NODE or NULL_TREE.  */
3503           decl = build_decl (parm_loc,
3504                              TYPE_DECL, parm, t);
3505         }
3506
3507       TYPE_NAME (t) = decl;
3508       TYPE_STUB_DECL (t) = decl;
3509       parm = decl;
3510       TEMPLATE_TYPE_PARM_INDEX (t)
3511         = build_template_parm_index (idx, processing_template_decl,
3512                                      processing_template_decl,
3513                                      decl, TREE_TYPE (parm));
3514       TEMPLATE_TYPE_PARAMETER_PACK (t) = is_parameter_pack;
3515       TYPE_CANONICAL (t) = canonical_type_parameter (t);
3516     }
3517   DECL_ARTIFICIAL (decl) = 1;
3518   SET_DECL_TEMPLATE_PARM_P (decl);
3519   pushdecl (decl);
3520   parm = build_tree_list (defval, parm);
3521   return chainon (list, parm);
3522 }
3523
3524 /* The end of a template parameter list has been reached.  Process the
3525    tree list into a parameter vector, converting each parameter into a more
3526    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and others
3527    as PARM_DECLs.  */
3528
3529 tree
3530 end_template_parm_list (tree parms)
3531 {
3532   int nparms;
3533   tree parm, next;
3534   tree saved_parmlist = make_tree_vec (list_length (parms));
3535
3536   current_template_parms
3537     = tree_cons (size_int (processing_template_decl),
3538                  saved_parmlist, current_template_parms);
3539
3540   for (parm = parms, nparms = 0; parm; parm = next, nparms++)
3541     {
3542       next = TREE_CHAIN (parm);
3543       TREE_VEC_ELT (saved_parmlist, nparms) = parm;
3544       TREE_CHAIN (parm) = NULL_TREE;
3545     }
3546
3547   --processing_template_parmlist;
3548
3549   return saved_parmlist;
3550 }
3551
3552 /* end_template_decl is called after a template declaration is seen.  */
3553
3554 void
3555 end_template_decl (void)
3556 {
3557   reset_specialization ();
3558
3559   if (! processing_template_decl)
3560     return;
3561
3562   /* This matches the pushlevel in begin_template_parm_list.  */
3563   finish_scope ();