OSDN Git Service

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