OSDN Git Service

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