Subversion Repositories openrisc_2011-10-31

/* 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

   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 "obstack.h"

#include "tree.h"

#include "intl.h"

#include "pointer-set.h"

#include "flags.h"

#include "c-common.h"

#include "cp-tree.h"

#include "cp-objcp-common.h"

#include "tree-inline.h"

#include "decl.h"

#include "output.h"

#include "except.h"

#include "toplev.h"

#include "rtl.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 (()) 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

static void push_access_scope (tree);

static void pop_access_scope (tree);

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

                                            unification_kind_t, int);

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

                             unification_kind_t, int, bool);

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

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);

static void note_template_header (int);

static tree convert_nontype_argument_function (tree, tree);

static tree convert_nontype_argument (tree, tree);

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, 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, int, 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);

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 tree get_template_base (tree, tree, tree, tree);

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

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 hashval_t iterative_hash_template_arg (tree arg, hashval_t val);

static tree listify (tree);

static tree listify_autos (tree, tree);

/* 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) : 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)

    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<>.  */

void

end_specialization (void)

{

  finish_scope ();

  reset_specialization ();

}

/* Any template <>'s that we have seen thus far are not referring to a

   function specialization.  */

void

reset_specialization (void)

{

  processing_specialization = 0;

  template_header_count = 0;

}

/* We've just seen a template header.  If SPECIALIZATION is nonzero,

   it was of the form template <>.  */