Subversion Repositories openrisc

/* Handle parameterized types (templates) for GNU C++.

   Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,

   2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011, 2012

   Free Software Foundation, Inc.

   Written by Ken Raeburn (raeburn@cygnus.com) while at Watchmaker Computing.

   Rewritten by Jason Merrill (jason@cygnus.com).

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation; either version 3, or (at your option)

any later version.

GCC is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

/* Known bugs or deficiencies include:

     all methods must be provided in header files; can't use a source

     file that contains only the method templates and "just win".  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "tree.h"

#include "intl.h"

#include "pointer-set.h"

#include "flags.h"

#include "cp-tree.h"

#include "c-family/c-common.h"

#include "c-family/c-objc.h"

#include "cp-objcp-common.h"

#include "tree-inline.h"

#include "decl.h"

#include "output.h"

#include "toplev.h"

#include "timevar.h"

#include "tree-iterator.h"

#include "vecprim.h"

/* The type of functions taking a tree, and some additional data, and

   returning an int.  */

typedef int (*tree_fn_t) (tree, void*);

/* The PENDING_TEMPLATES is a TREE_LIST of templates whose

   instantiations have been deferred, either because their definitions

   were not yet available, or because we were putting off doing the work.  */

struct GTY ((chain_next ("%h.next"))) pending_template {

  struct pending_template *next;

  struct tinst_level *tinst;

};

static GTY(()) struct pending_template *pending_templates;

static GTY(()) struct pending_template *last_pending_template;

int processing_template_parmlist;

static int template_header_count;

static GTY(()) tree saved_trees;

static VEC(int,heap) *inline_parm_levels;

static GTY(()) struct tinst_level *current_tinst_level;

static GTY(()) tree saved_access_scope;

/* Live only within one (recursive) call to tsubst_expr.  We use

   this to pass the statement expression node from the STMT_EXPR

   to the EXPR_STMT that is its result.  */

static tree cur_stmt_expr;

/* A map from local variable declarations in the body of the template

   presently being instantiated to the corresponding instantiated

   local variables.  */

static htab_t local_specializations;

typedef struct GTY(()) spec_entry

{

  tree tmpl;

  tree args;

  tree spec;

} spec_entry;

static GTY ((param_is (spec_entry)))

  htab_t decl_specializations;

static GTY ((param_is (spec_entry)))

  htab_t type_specializations;

/* Contains canonical template parameter types. The vector is indexed by

   the TEMPLATE_TYPE_IDX of the template parameter. Each element is a

   TREE_LIST, whose TREE_VALUEs contain the canonical template

   parameters of various types and levels.  */

static GTY(()) VEC(tree,gc) *canonical_template_parms;

#define UNIFY_ALLOW_NONE 0

#define UNIFY_ALLOW_MORE_CV_QUAL 1

#define UNIFY_ALLOW_LESS_CV_QUAL 2

#define UNIFY_ALLOW_DERIVED 4

#define UNIFY_ALLOW_INTEGER 8

#define UNIFY_ALLOW_OUTER_LEVEL 16

#define UNIFY_ALLOW_OUTER_MORE_CV_QUAL 32

#define UNIFY_ALLOW_OUTER_LESS_CV_QUAL 64

enum template_base_result {

  tbr_incomplete_type,

  tbr_ambiguous_baseclass,

  tbr_success

};

static void push_access_scope (tree);

static void pop_access_scope (tree);

static void push_deduction_access_scope (tree);

static void pop_deduction_access_scope (tree);

static bool resolve_overloaded_unification (tree, tree, tree, tree,

                                            unification_kind_t, int,

                                            bool);

static int try_one_overload (tree, tree, tree, tree, tree,

                             unification_kind_t, int, bool, bool);

static int unify (tree, tree, tree, tree, int, bool);

static void add_pending_template (tree);

static tree reopen_tinst_level (struct tinst_level *);

static tree tsubst_initializer_list (tree, tree);

static tree get_class_bindings (tree, tree, tree);

static tree coerce_template_parms (tree, tree, tree, tsubst_flags_t,

                                   bool, bool);

static void tsubst_enum (tree, tree, tree);

static tree add_to_template_args (tree, tree);

static tree add_outermost_template_args (tree, tree);

static bool check_instantiated_args (tree, tree, tsubst_flags_t);

static int maybe_adjust_types_for_deduction (unification_kind_t, tree*, tree*,

                                             tree);

static int type_unification_real (tree, tree, tree, const tree *,

                                  unsigned int, int, unification_kind_t, int,

                                  bool);

static void note_template_header (int);

static tree convert_nontype_argument_function (tree, tree);

static tree convert_nontype_argument (tree, tree, tsubst_flags_t);

static tree convert_template_argument (tree, tree, tree,

                                       tsubst_flags_t, int, tree);

static int for_each_template_parm (tree, tree_fn_t, void*,

                                   struct pointer_set_t*, bool);

static tree expand_template_argument_pack (tree);

static tree build_template_parm_index (int, int, int, int, tree, tree);

static bool inline_needs_template_parms (tree);

static void push_inline_template_parms_recursive (tree, int);

static tree retrieve_local_specialization (tree);

static void register_local_specialization (tree, tree);

static hashval_t hash_specialization (const void *p);

static tree reduce_template_parm_level (tree, tree, int, tree, tsubst_flags_t);

static int mark_template_parm (tree, void *);

static int template_parm_this_level_p (tree, void *);

static tree tsubst_friend_function (tree, tree);

static tree tsubst_friend_class (tree, tree);

static int can_complete_type_without_circularity (tree);

static tree get_bindings (tree, tree, tree, bool);

static int template_decl_level (tree);

static int check_cv_quals_for_unify (int, tree, tree);

static void template_parm_level_and_index (tree, int*, int*);

static int unify_pack_expansion (tree, tree, tree,

                                 tree, unification_kind_t, bool, bool);

static tree tsubst_template_arg (tree, tree, tsubst_flags_t, tree);

static tree tsubst_template_args (tree, tree, tsubst_flags_t, tree);

static tree tsubst_template_parms (tree, tree, tsubst_flags_t);

static void regenerate_decl_from_template (tree, tree);

static tree most_specialized_class (tree, tree, tsubst_flags_t);

static tree tsubst_aggr_type (tree, tree, tsubst_flags_t, tree, int);

static tree tsubst_arg_types (tree, tree, tsubst_flags_t, tree);

static tree tsubst_function_type (tree, tree, tsubst_flags_t, tree);

static bool check_specialization_scope (void);

static tree process_partial_specialization (tree);

static void set_current_access_from_decl (tree);

static enum template_base_result get_template_base (tree, tree, tree, tree,

                                                    bool , tree *);

static tree try_class_unification (tree, tree, tree, tree, bool);

static int coerce_template_template_parms (tree, tree, tsubst_flags_t,

                                           tree, tree);

static bool template_template_parm_bindings_ok_p (tree, tree);

static int template_args_equal (tree, tree);

static void tsubst_default_arguments (tree);

static tree for_each_template_parm_r (tree *, int *, void *);

static tree copy_default_args_to_explicit_spec_1 (tree, tree);

static void copy_default_args_to_explicit_spec (tree);

static int invalid_nontype_parm_type_p (tree, tsubst_flags_t);

static int eq_local_specializations (const void *, const void *);

static bool dependent_template_arg_p (tree);

static bool any_template_arguments_need_structural_equality_p (tree);

static bool dependent_type_p_r (tree);

static tree tsubst_expr (tree, tree, tsubst_flags_t, tree, bool);

static tree tsubst_copy (tree, tree, tsubst_flags_t, tree);

static tree tsubst_pack_expansion (tree, tree, tsubst_flags_t, tree);

static tree tsubst_decl (tree, tree, tsubst_flags_t);

static void perform_typedefs_access_check (tree tmpl, tree targs);

static void append_type_to_template_for_access_check_1 (tree, tree, tree,

                                                        location_t);

static tree listify (tree);

static tree listify_autos (tree, tree);

static tree template_parm_to_arg (tree t);

static bool arg_from_parm_pack_p (tree, tree);

static tree current_template_args (void);

static tree fixup_template_type_parm_type (tree, int);

static tree fixup_template_parm_index (tree, tree, int);

static tree tsubst_template_parm (tree, tree, tsubst_flags_t);

/* Make the current scope suitable for access checking when we are

   processing T.  T can be FUNCTION_DECL for instantiated function

   template, or VAR_DECL for static member variable (need by

   instantiate_decl).  */

static void

push_access_scope (tree t)

{

  gcc_assert (TREE_CODE (t) == FUNCTION_DECL

              || TREE_CODE (t) == VAR_DECL);

  if (DECL_FRIEND_CONTEXT (t))

    push_nested_class (DECL_FRIEND_CONTEXT (t));

  else if (DECL_CLASS_SCOPE_P (t))

    push_nested_class (DECL_CONTEXT (t));

  else

    push_to_top_level ();

  if (TREE_CODE (t) == FUNCTION_DECL)

    {

      saved_access_scope = tree_cons

        (NULL_TREE, current_function_decl, saved_access_scope);

      current_function_decl = t;

    }

}

/* Restore the scope set up by push_access_scope.  T is the node we

   are processing.  */

static void

pop_access_scope (tree t)

{

  if (TREE_CODE (t) == FUNCTION_DECL)

    {

      current_function_decl = TREE_VALUE (saved_access_scope);

      saved_access_scope = TREE_CHAIN (saved_access_scope);

    }

  if (DECL_FRIEND_CONTEXT (t) || DECL_CLASS_SCOPE_P (t))

    pop_nested_class ();

  else

    pop_from_top_level ();

}

/* Do any processing required when DECL (a member template

   declaration) is finished.  Returns the TEMPLATE_DECL corresponding

   to DECL, unless it is a specialization, in which case the DECL

   itself is returned.  */

tree

finish_member_template_decl (tree decl)

{

  if (decl == error_mark_node)

    return error_mark_node;

  gcc_assert (DECL_P (decl));

  if (TREE_CODE (decl) == TYPE_DECL)

    {

      tree type;

      type = TREE_TYPE (decl);

      if (type == error_mark_node)

        return error_mark_node;

      if (MAYBE_CLASS_TYPE_P (type)

          && CLASSTYPE_TEMPLATE_INFO (type)

          && !CLASSTYPE_TEMPLATE_SPECIALIZATION (type))

        {

          tree tmpl = CLASSTYPE_TI_TEMPLATE (type);

          check_member_template (tmpl);

          return tmpl;

        }

      return NULL_TREE;

    }

  else if (TREE_CODE (decl) == FIELD_DECL)

    error ("data member %qD cannot be a member template", decl);

  else if (DECL_TEMPLATE_INFO (decl))

    {

      if (!DECL_TEMPLATE_SPECIALIZATION (decl))

        {

          check_member_template (DECL_TI_TEMPLATE (decl));

          return DECL_TI_TEMPLATE (decl);

        }

      else

        return decl;

    }

  else

    error ("invalid member template declaration %qD", decl);

  return error_mark_node;

}

/* Create a template info node.  */

tree

build_template_info (tree template_decl, tree template_args)

{

  tree result = make_node (TEMPLATE_INFO);

  TI_TEMPLATE (result) = template_decl;

  TI_ARGS (result) = template_args;

  return result;

}

/* Return the template info node corresponding to T, whatever T is.  */

tree

get_template_info (const_tree t)

{

  tree tinfo = NULL_TREE;

  if (!t || t == error_mark_node)

    return NULL;

  if (DECL_P (t) && DECL_LANG_SPECIFIC (t))

    tinfo = DECL_TEMPLATE_INFO (t);

  if (!tinfo && DECL_IMPLICIT_TYPEDEF_P (t))

    t = TREE_TYPE (t);

  if (TAGGED_TYPE_P (t))

    tinfo = TYPE_TEMPLATE_INFO (t);

  else if (TREE_CODE (t) == BOUND_TEMPLATE_TEMPLATE_PARM)

    tinfo = TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t);

  return tinfo;

}

/* Returns the template nesting level of the indicated class TYPE.

   For example, in:

     template <class T>

     struct A

     {

       template <class U>

       struct B {};

     };

   A<T>::B<U> has depth two, while A<T> has depth one.

   Both A<T>::B<int> and A<int>::B<U> have depth one, if

   they are instantiations, not specializations.

   This function is guaranteed to return 0 if passed NULL_TREE so

   that, for example, `template_class_depth (current_class_type)' is

   always safe.  */

int

template_class_depth (tree type)

{

  int depth;

  for (depth = 0;

       type && TREE_CODE (type) != NAMESPACE_DECL;

       type = (TREE_CODE (type) == FUNCTION_DECL)

         ? CP_DECL_CONTEXT (type) : CP_TYPE_CONTEXT (type))

    {

      tree tinfo = get_template_info (type);

      if (tinfo && PRIMARY_TEMPLATE_P (TI_TEMPLATE (tinfo))

          && uses_template_parms (INNERMOST_TEMPLATE_ARGS (TI_ARGS (tinfo))))

        ++depth;

    }

  return depth;

}

/* Subroutine of maybe_begin_member_template_processing.

   Returns true if processing DECL needs us to push template parms.  */

static bool

inline_needs_template_parms (tree decl)

{

  if (! DECL_TEMPLATE_INFO (decl))

    return false;

  return (TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (most_general_template (decl)))

          > (processing_template_decl + DECL_TEMPLATE_SPECIALIZATION (decl)));

}

/* Subroutine of maybe_begin_member_template_processing.

   Push the template parms in PARMS, starting from LEVELS steps into the

   chain, and ending at the beginning, since template parms are listed

   innermost first.  */

static void

push_inline_template_parms_recursive (tree parmlist, int levels)

{

  tree parms = TREE_VALUE (parmlist);

  int i;

  if (levels > 1)

    push_inline_template_parms_recursive (TREE_CHAIN (parmlist), levels - 1);

  ++processing_template_decl;

  current_template_parms

    = tree_cons (size_int (processing_template_decl),

                 parms, current_template_parms);

  TEMPLATE_PARMS_FOR_INLINE (current_template_parms) = 1;

  begin_scope (TREE_VEC_LENGTH (parms) ? sk_template_parms : sk_template_spec,

               NULL);

  for (i = 0; i < TREE_VEC_LENGTH (parms); ++i)

    {

      tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));

      if (parm == error_mark_node)

        continue;

      gcc_assert (DECL_P (parm));

      switch (TREE_CODE (parm))

        {

        case TYPE_DECL:

        case TEMPLATE_DECL:

          pushdecl (parm);

          break;

        case PARM_DECL:

          {

            /* Make a CONST_DECL as is done in process_template_parm.

               It is ugly that we recreate this here; the original

               version built in process_template_parm is no longer

               available.  */

            tree decl = build_decl (DECL_SOURCE_LOCATION (parm),

                                    CONST_DECL, DECL_NAME (parm),

                                    TREE_TYPE (parm));

            DECL_ARTIFICIAL (decl) = 1;

            TREE_CONSTANT (decl) = 1;

            TREE_READONLY (decl) = 1;

            DECL_INITIAL (decl) = DECL_INITIAL (parm);

            SET_DECL_TEMPLATE_PARM_P (decl);

            pushdecl (decl);

          }

          break;

        default:

          gcc_unreachable ();

        }

    }

}

/* Restore the template parameter context for a member template or

   a friend template defined in a class definition.  */

void

maybe_begin_member_template_processing (tree decl)

{

  tree parms;

  int levels = 0;

  if (inline_needs_template_parms (decl))

    {

      parms = DECL_TEMPLATE_PARMS (most_general_template (decl));

      levels = TMPL_PARMS_DEPTH (parms) - processing_template_decl;

      if (DECL_TEMPLATE_SPECIALIZATION (decl))

        {

          --levels;

          parms = TREE_CHAIN (parms);

        }

      push_inline_template_parms_recursive (parms, levels);

    }

  /* Remember how many levels of template parameters we pushed so that

     we can pop them later.  */

  VEC_safe_push (int, heap, inline_parm_levels, levels);

}

/* Undo the effects of maybe_begin_member_template_processing.  */

void

maybe_end_member_template_processing (void)

{

  int i;

  int last;

  if (VEC_length (int, inline_parm_levels) == 0)

    return;

  last = VEC_pop (int, inline_parm_levels);

  for (i = 0; i < last; ++i)

    {

      --processing_template_decl;

      current_template_parms = TREE_CHAIN (current_template_parms);

      poplevel (0, 0, 0);

    }

}

/* Return a new template argument vector which contains all of ARGS,

   but has as its innermost set of arguments the EXTRA_ARGS.  */

static tree

add_to_template_args (tree args, tree extra_args)

{

  tree new_args;

  int extra_depth;

  int i;

  int j;

  if (args == NULL_TREE || extra_args == error_mark_node)

    return extra_args;

  extra_depth = TMPL_ARGS_DEPTH (extra_args);

  new_args = make_tree_vec (TMPL_ARGS_DEPTH (args) + extra_depth);

  for (i = 1; i <= TMPL_ARGS_DEPTH (args); ++i)

    SET_TMPL_ARGS_LEVEL (new_args, i, TMPL_ARGS_LEVEL (args, i));

  for (j = 1; j <= extra_depth; ++j, ++i)

    SET_TMPL_ARGS_LEVEL (new_args, i, TMPL_ARGS_LEVEL (extra_args, j));

  return new_args;

}

/* Like add_to_template_args, but only the outermost ARGS are added to

   the EXTRA_ARGS.  In particular, all but TMPL_ARGS_DEPTH

   (EXTRA_ARGS) levels are added.  This function is used to combine

   the template arguments from a partial instantiation with the

   template arguments used to attain the full instantiation from the

   partial instantiation.  */

static tree

add_outermost_template_args (tree args, tree extra_args)

{

  tree new_args;

  /* If there are more levels of EXTRA_ARGS than there are ARGS,

     something very fishy is going on.  */

  gcc_assert (TMPL_ARGS_DEPTH (args) >= TMPL_ARGS_DEPTH (extra_args));

  /* If *all* the new arguments will be the EXTRA_ARGS, just return

     them.  */

  if (TMPL_ARGS_DEPTH (args) == TMPL_ARGS_DEPTH (extra_args))

    return extra_args;

  /* For the moment, we make ARGS look like it contains fewer levels.  */

  TREE_VEC_LENGTH (args) -= TMPL_ARGS_DEPTH (extra_args);

  new_args = add_to_template_args (args, extra_args);

  /* Now, we restore ARGS to its full dimensions.  */

  TREE_VEC_LENGTH (args) += TMPL_ARGS_DEPTH (extra_args);

  return new_args;

}

/* Return the N levels of innermost template arguments from the ARGS.  */

tree

get_innermost_template_args (tree args, int n)

{

  tree new_args;

  int extra_levels;

  int i;

  gcc_assert (n >= 0);

  /* If N is 1, just return the innermost set of template arguments.  */

  if (n == 1)

    return TMPL_ARGS_LEVEL (args, TMPL_ARGS_DEPTH (args));

  /* If we're not removing anything, just return the arguments we were

     given.  */

  extra_levels = TMPL_ARGS_DEPTH (args) - n;

  gcc_assert (extra_levels >= 0);

  if (extra_levels == 0)

    return args;

  /* Make a new set of arguments, not containing the outer arguments.  */

  new_args = make_tree_vec (n);

  for (i = 1; i <= n; ++i)

    SET_TMPL_ARGS_LEVEL (new_args, i,

                         TMPL_ARGS_LEVEL (args, i + extra_levels));

  return new_args;

}

/* The inverse of get_innermost_template_args: Return all but the innermost

   EXTRA_LEVELS levels of template arguments from the ARGS.  */

static tree

strip_innermost_template_args (tree args, int extra_levels)

{

  tree new_args;

  int n = TMPL_ARGS_DEPTH (args) - extra_levels;

  int i;

  gcc_assert (n >= 0);

  /* If N is 1, just return the outermost set of template arguments.  */

  if (n == 1)

    return TMPL_ARGS_LEVEL (args, 1);

  /* If we're not removing anything, just return the arguments we were

     given.  */

  gcc_assert (extra_levels >= 0);

  if (extra_levels == 0)

    return args;

  /* Make a new set of arguments, not containing the inner arguments.  */

  new_args = make_tree_vec (n);

  for (i = 1; i <= n; ++i)

    SET_TMPL_ARGS_LEVEL (new_args, i,

                         TMPL_ARGS_LEVEL (args, i));

  return new_args;

}

/* We've got a template header coming up; push to a new level for storing

   the parms.  */

void

begin_template_parm_list (void)

{

  /* We use a non-tag-transparent scope here, which causes pushtag to

     put tags in this scope, rather than in the enclosing class or

     namespace scope.  This is the right thing, since we want

     TEMPLATE_DECLS, and not TYPE_DECLS for template classes.  For a

     global template class, push_template_decl handles putting the

     TEMPLATE_DECL into top-level scope.  For a nested template class,

     e.g.:

       template <class T> struct S1 {

         template <class T> struct S2 {};

       };

     pushtag contains special code to call pushdecl_with_scope on the

     TEMPLATE_DECL for S2.  */

  begin_scope (sk_template_parms, NULL);

  ++processing_template_decl;

  ++processing_template_parmlist;

  note_template_header (0);

}

/* This routine is called when a specialization is declared.  If it is

   invalid to declare a specialization here, an error is reported and

   false is returned, otherwise this routine will return true.  */

static bool

check_specialization_scope (void)

{

  tree scope = current_scope ();

  /* [temp.expl.spec]

     An explicit specialization shall be declared in the namespace of

     which the template is a member, or, for member templates, in the

     namespace of which the enclosing class or enclosing class

     template is a member.  An explicit specialization of a member

     function, member class or static data member of a class template

     shall be declared in the namespace of which the class template

     is a member.  */

  if (scope && TREE_CODE (scope) != NAMESPACE_DECL)

    {

      error ("explicit specialization in non-namespace scope %qD", scope);

      return false;

    }

  /* [temp.expl.spec]

     In an explicit specialization declaration for a member of a class

     template or a member template that appears in namespace scope,

     the member template and some of its enclosing class templates may

     remain unspecialized, except that the declaration shall not

     explicitly specialize a class member template if its enclosing

     class templates are not explicitly specialized as well.  */

  if (current_template_parms)

    {

      error ("enclosing class templates are not explicitly specialized");

      return false;

    }

  return true;

}

/* We've just seen template <>.  */

bool

begin_specialization (void)

{

  begin_scope (sk_template_spec, NULL);

  note_template_header (1);

  return check_specialization_scope ();

}

/* Called at then end of processing a declaration preceded by

   template<>.  */