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