/*

 * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code 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

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

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

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#include "precompiled.hpp"

#include "classfile/bytecodeAssembler.hpp"

#include "classfile/defaultMethods.hpp"

#include "classfile/symbolTable.hpp"

#include "memory/allocation.hpp"

#include "memory/metadataFactory.hpp"

#include "memory/resourceArea.hpp"

#include "runtime/signature.hpp"

#include "runtime/thread.hpp"

#include "oops/instanceKlass.hpp"

#include "oops/klass.hpp"

#include "oops/method.hpp"

#include "utilities/accessFlags.hpp"

#include "utilities/exceptions.hpp"

#include "utilities/ostream.hpp"

#include "utilities/pair.hpp"

#include "utilities/resourceHash.hpp"

typedef enum { QUALIFIED, DISQUALIFIED } QualifiedState;

// Because we use an iterative algorithm when iterating over the type

// hierarchy, we can't use traditional scoped objects which automatically do

// cleanup in the destructor when the scope is exited.  PseudoScope (and

// PseudoScopeMark) provides a similar functionality, but for when you want a

// scoped object in non-stack memory (such as in resource memory, as we do

// here).  You've just got to remember to call 'destroy()' on the scope when

// leaving it (and marks have to be explicitly added).

class PseudoScopeMark : public ResourceObj {

 public:

  virtual void destroy() = 0;

};

class PseudoScope : public ResourceObj {

 private:

  GrowableArray<PseudoScopeMark*> _marks;

 public:

  static PseudoScope* cast(void* data) {

    return static_cast<PseudoScope*>(data);

  }

  void add_mark(PseudoScopeMark* psm) {

   _marks.append(psm);

  }

  void destroy() {

    for (int i = 0; i < _marks.length(); ++i) {

      _marks.at(i)->destroy();

    }

  }

};

#ifndef PRODUCT

static void print_slot(outputStream* str, Symbol* name, Symbol* signature) {

  ResourceMark rm;

  str->print("%s%s", name->as_C_string(), signature->as_C_string());

}

static void print_method(outputStream* str, Method* mo, bool with_class=true) {

  ResourceMark rm;

  if (with_class) {

    str->print("%s.", mo->klass_name()->as_C_string());

  }

  print_slot(str, mo->name(), mo->signature());

}

#endif // ndef PRODUCT

/**

 * Perform a depth-first iteration over the class hierarchy, applying

 * algorithmic logic as it goes.

 *

 * This class is one half of the inheritance hierarchy analysis mechanism.

 * It is meant to be used in conjunction with another class, the algorithm,

 * which is indicated by the ALGO template parameter.  This class can be

 * paired with any algorithm class that provides the required methods.

 *

 * This class contains all the mechanics for iterating over the class hierarchy

 * starting at a particular root, without recursing (thus limiting stack growth

 * from this point).  It visits each superclass (if present) and superinterface

 * in a depth-first manner, with callbacks to the ALGO class as each class is

 * encountered (visit()), The algorithm can cut-off further exploration of a

 * particular branch by returning 'false' from a visit() call.

 *

 * The ALGO class, must provide a visit() method, which each of which will be

 * called once for each node in the inheritance tree during the iteration.  In

 * addition, it can provide a memory block via new_node_data(InstanceKlass*),

 * which it can use for node-specific storage (and access via the

 * current_data() and data_at_depth(int) methods).

 *

 * Bare minimum needed to be an ALGO class:

 * class Algo : public HierarchyVisitor<Algo> {

 *   void* new_node_data(InstanceKlass* cls) { return NULL; }

 *   void free_node_data(void* data) { return; }

 *   bool visit() { return true; }

 * };

 */

template <class ALGO>

class HierarchyVisitor : StackObj {

 private:

  class Node : public ResourceObj {

   public:

    InstanceKlass* _class;

    bool _super_was_visited;

    int _interface_index;

    void* _algorithm_data;

    Node(InstanceKlass* cls, void* data, bool visit_super)

        : _class(cls), _super_was_visited(!visit_super),

          _interface_index(0), _algorithm_data(data) {}

    int number_of_interfaces() { return _class->local_interfaces()->length(); }

    int interface_index() { return _interface_index; }

    void set_super_visited() { _super_was_visited = true; }

    void increment_visited_interface() { ++_interface_index; }

    void set_all_interfaces_visited() {

      _interface_index = number_of_interfaces();

    }

    bool has_visited_super() { return _super_was_visited; }

    bool has_visited_all_interfaces() {

      return interface_index() >= number_of_interfaces();

    }

    InstanceKlass* interface_at(int index) {

      return InstanceKlass::cast(_class->local_interfaces()->at(index));

    }

    InstanceKlass* next_super() { return _class->java_super(); }

    InstanceKlass* next_interface() {

      return interface_at(interface_index());

    }

  };

  bool _cancelled;

  GrowableArray<Node*> _path;

  Node* current_top() const { return _path.top(); }

  bool has_more_nodes() const { return !_path.is_empty(); }

  void push(InstanceKlass* cls, void* data) {

    assert(cls != NULL, "Requires a valid instance class");

    Node* node = new Node(cls, data, has_super(cls));

    _path.push(node);

  }

  void pop() { _path.pop(); }

  void reset_iteration() {

    _cancelled = false;

    _path.clear();

  }

  bool is_cancelled() const { return _cancelled; }

  // This code used to skip interface classes because their only

  // superclass was j.l.Object which would be also covered by class

  // superclass hierarchy walks. Now that the starting point can be

  // an interface, we must ensure we catch j.l.Object as the super.

  static bool has_super(InstanceKlass* cls) {

    return cls->super() != NULL;

  }

  Node* node_at_depth(int i) const {

    return (i >= _path.length()) ? NULL : _path.at(_path.length() - i - 1);

  }

 protected:

  // Accessors available to the algorithm

  int current_depth() const { return _path.length() - 1; }

  InstanceKlass* class_at_depth(int i) {

    Node* n = node_at_depth(i);

    return n == NULL ? NULL : n->_class;

  }

  InstanceKlass* current_class() { return class_at_depth(0); }

  void* data_at_depth(int i) {

    Node* n = node_at_depth(i);

    return n == NULL ? NULL : n->_algorithm_data;

  }

  void* current_data() { return data_at_depth(0); }

  void cancel_iteration() { _cancelled = true; }

 public:

  void run(InstanceKlass* root) {

    ALGO* algo = static_cast<ALGO*>(this);

    reset_iteration();

    void* algo_data = algo->new_node_data(root);

    push(root, algo_data);

    bool top_needs_visit = true;

    do {

      Node* top = current_top();

      if (top_needs_visit) {

        if (algo->visit() == false) {

          // algorithm does not want to continue along this path.  Arrange

          // it so that this state is immediately popped off the stack

          top->set_super_visited();

          top->set_all_interfaces_visited();

        }

        top_needs_visit = false;

      }

      if (top->has_visited_super() && top->has_visited_all_interfaces()) {

        algo->free_node_data(top->_algorithm_data);

        pop();

      } else {

        InstanceKlass* next = NULL;

        if (top->has_visited_super() == false) {

          next = top->next_super();

          top->set_super_visited();

        } else {

          next = top->next_interface();

          top->increment_visited_interface();

        }

        assert(next != NULL, "Otherwise we shouldn't be here");

        algo_data = algo->new_node_data(next);

        push(next, algo_data);

        top_needs_visit = true;

      }

    } while (!is_cancelled() && has_more_nodes());

  }

};

#ifndef PRODUCT

class PrintHierarchy : public HierarchyVisitor<PrintHierarchy> {

 public:

  bool visit() {

    InstanceKlass* cls = current_class();

    streamIndentor si(tty, current_depth() * 2);

    tty->indent().print_cr("%s", cls->name()->as_C_string());

    return true;

  }

  void* new_node_data(InstanceKlass* cls) { return NULL; }

  void free_node_data(void* data) { return; }

};

#endif // ndef PRODUCT

// Used to register InstanceKlass objects and all related metadata structures

// (Methods, ConstantPools) as "in-use" by the current thread so that they can't

// be deallocated by class redefinition while we're using them.  The classes are

// de-registered when this goes out of scope.

//

// Once a class is registered, we need not bother with methodHandles or

// constantPoolHandles for it's associated metadata.

class KeepAliveRegistrar : public StackObj {

 private:

  Thread* _thread;

  GrowableArray<ConstantPool*> _keep_alive;

 public:

  KeepAliveRegistrar(Thread* thread) : _thread(thread), _keep_alive(20) {

    assert(thread == Thread::current(), "Must be current thread");

  }

  ~KeepAliveRegistrar() {

    for (int i = _keep_alive.length() - 1; i >= 0; --i) {

      ConstantPool* cp = _keep_alive.at(i);

      int idx = _thread->metadata_handles()->find_from_end(cp);

      assert(idx > 0, "Must be in the list");

      _thread->metadata_handles()->remove_at(idx);

    }

  }

  // Register a class as 'in-use' by the thread.  It's fine to register a class

  // multiple times (though perhaps inefficient)

  void register_class(InstanceKlass* ik) {

    ConstantPool* cp = ik->constants();

    _keep_alive.push(cp);

    _thread->metadata_handles()->push(cp);

  }

};

class KeepAliveVisitor : public HierarchyVisitor<KeepAliveVisitor> {

 private:

  KeepAliveRegistrar* _registrar;

 public:

  KeepAliveVisitor(KeepAliveRegistrar* registrar) : _registrar(registrar) {}

  void* new_node_data(InstanceKlass* cls) { return NULL; }

  void free_node_data(void* data) { return; }

  bool visit() {

    _registrar->register_class(current_class());

    return true;

  }

};

// A method family contains a set of all methods that implement a single

// erased method. As members of the set are collected while walking over the

// hierarchy, they are tagged with a qualification state.  The qualification

// state for an erased method is set to disqualified if there exists a path

// from the root of hierarchy to the method that contains an interleaving

// erased method defined in an interface.

class MethodFamily : public ResourceObj {

 private:

  GrowableArray<Pair<Method*,QualifiedState> > _members;

  ResourceHashtable<Method*, int> _member_index;

  Method* _selected_target;  // Filled in later, if a unique target exists

  Symbol* _exception_message; // If no unique target is found

  Symbol* _exception_name;    // If no unique target is found

  bool contains_method(Method* method) {

    int* lookup = _member_index.get(method);

    return lookup != NULL;

  }

  void add_method(Method* method, QualifiedState state) {

    Pair<Method*,QualifiedState> entry(method, state);

    _member_index.put(method, _members.length());

    _members.append(entry);

  }

  void disqualify_method(Method* method) {

    int* index = _member_index.get(method);

    guarantee(index != NULL && *index >= 0 && *index < _members.length(), "bad index");

    _members.at(*index).second = DISQUALIFIED;

  }

  Symbol* generate_no_defaults_message(TRAPS) const;

  Symbol* generate_method_message(Symbol *klass_name, Method* method, TRAPS) const;

  Symbol* generate_conflicts_message(GrowableArray<Method*>* methods, TRAPS) const;

 public:

  MethodFamily()

      : _selected_target(NULL), _exception_message(NULL), _exception_name(NULL) {}

  void set_target_if_empty(Method* m) {

    if (_selected_target == NULL && !m->is_overpass()) {

      _selected_target = m;

    }

  }

  void record_qualified_method(Method* m) {

    // If the method already exists in the set as qualified, this operation is

    // redundant.  If it already exists as disqualified, then we leave it as

    // disqualfied.  Thus we only add to the set if it's not already in the

    // set.

    if (!contains_method(m)) {

      add_method(m, QUALIFIED);

    }

  }

  void record_disqualified_method(Method* m) {

    // If not in the set, add it as disqualified.  If it's already in the set,

    // then set the state to disqualified no matter what the previous state was.

    if (!contains_method(m)) {

      add_method(m, DISQUALIFIED);

    } else {

      disqualify_method(m);

    }

  }

  bool has_target() const { return _selected_target != NULL; }

  bool throws_exception() { return _exception_message != NULL; }

  Method* get_selected_target() { return _selected_target; }

  Symbol* get_exception_message() { return _exception_message; }

  Symbol* get_exception_name() { return _exception_name; }

  // Return true if the specified klass has a static method that matches

  // the name and signature of the target method.

  bool has_matching_static(InstanceKlass* root) {

    if (_members.length() > 0) {

      Pair<Method*,QualifiedState> entry = _members.at(0);

      Method* impl = root->find_method(entry.first->name(),

                                       entry.first->signature());

      if ((impl != NULL) && impl->is_static()) {

        return true;

      }

    }

    return false;

  }

  // Either sets the target or the exception error message

  void determine_target(InstanceKlass* root, TRAPS) {

    if (has_target() || throws_exception()) {

      return;

    }

    // Qualified methods are maximally-specific methods

    // These include public, instance concrete (=default) and abstract methods

    GrowableArray<Method*> qualified_methods;

    int num_defaults = 0;

    int default_index = -1;

    int qualified_index = -1;

    for (int i = 0; i < _members.length(); ++i) {

      Pair<Method*,QualifiedState> entry = _members.at(i);

      if (entry.second == QUALIFIED) {

        qualified_methods.append(entry.first);

        qualified_index++;

        if (entry.first->is_default_method()) {

          num_defaults++;

          default_index = qualified_index;

        }

      }

    }

    if (num_defaults == 0) {

      // If the root klass has a static method with matching name and signature

      // then do not generate an overpass method because it will hide the

      // static method during resolution.

      if (!has_matching_static(root)) {

        if (qualified_methods.length() == 0) {

          _exception_message = generate_no_defaults_message(CHECK);

        } else {

          assert(root != NULL, "Null root class");

          _exception_message = generate_method_message(root->name(), qualified_methods.at(0), CHECK);

        }

        _exception_name = vmSymbols::java_lang_AbstractMethodError();

      }

    // If only one qualified method is default, select that

    } else if (num_defaults == 1) {

        _selected_target = qualified_methods.at(default_index);

    } else if (num_defaults > 1 && !has_matching_static(root)) {

      _exception_message = generate_conflicts_message(&qualified_methods,CHECK);

      _exception_name = vmSymbols::java_lang_IncompatibleClassChangeError();

      if (TraceDefaultMethods) {

        _exception_message->print_value_on(tty);

        tty->print_cr("");

      }

    }

  }

  bool contains_signature(Symbol* query) {

    for (int i = 0; i < _members.length(); ++i) {

      if (query == _members.at(i).first->signature()) {

        return true;

      }

    }

    return false;

  }

#ifndef PRODUCT

  void print_sig_on(outputStream* str, Symbol* signature, int indent) const {

    streamIndentor si(str, indent * 2);

    str->indent().print_cr("Logical Method %s:", signature->as_C_string());

    streamIndentor si2(str);

    for (int i = 0; i < _members.length(); ++i) {

      str->indent();

      print_method(str, _members.at(i).first);

      if (_members.at(i).second == DISQUALIFIED) {

        str->print(" (disqualified)");

      }

      str->print_cr("");

    }

    if (_selected_target != NULL) {

      print_selected(str, 1);

    }

  }

  void print_selected(outputStream* str, int indent) const {

    assert(has_target(), "Should be called otherwise");

    streamIndentor si(str, indent * 2);

    str->indent().print("Selected method: ");

    print_method(str, _selected_target);

    Klass* method_holder = _selected_target->method_holder();

    if (!method_holder->is_interface()) {

      tty->print(" : in superclass");

    }

    str->print_cr("");

  }

  void print_exception(outputStream* str, int indent) {

    assert(throws_exception(), "Should be called otherwise");

    assert(_exception_name != NULL, "exception_name should be set");

    streamIndentor si(str, indent * 2);

    str->indent().print_cr("%s: %s", _exception_name->as_C_string(), _exception_message->as_C_string());

  }

#endif // ndef PRODUCT

};

Symbol* MethodFamily::generate_no_defaults_message(TRAPS) const {

  return SymbolTable::new_symbol("No qualifying defaults found", CHECK_NULL);

}

Symbol* MethodFamily::generate_method_message(Symbol *klass_name, Method* method, TRAPS) const {

  stringStream ss;

  ss.print("Method ");

  Symbol* name = method->name();

  Symbol* signature = method->signature();