OSDN Git Service

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