/*

 * Copyright (c) 2012, 2019, 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 "classfile/systemDictionary.hpp"

#include "logging/log.hpp"

#include "logging/logStream.hpp"

#include "memory/allocation.hpp"

#include "memory/metadataFactory.hpp"

#include "memory/resourceArea.hpp"

#include "memory/universe.hpp"

#include "runtime/handles.inline.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();

    }

  }

};

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

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

}

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

  if (with_class) {

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

  }

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

}

/**

 * 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 _visited_Object;

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

    if (cls == SystemDictionary::Object_klass()) {

      _visited_Object = true;

    }

    _path.push(node);

  }

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

  // Since the starting point can be an interface, we must ensure we catch

  // j.l.Object as the super once in those cases. The _visited_Object flag

  // only ensures we don't then repeatedly enqueue Object for each interface

  // in the class hierarchy.

  bool has_super(InstanceKlass* cls) {

    return cls->super() != NULL && (!_visited_Object || !cls->is_interface());

  }

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

 public:

  void run(InstanceKlass* root) {

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

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

  }

};

class PrintHierarchy : public HierarchyVisitor<PrintHierarchy> {

 private:

   outputStream* _st;

 public:

  bool visit() {

    InstanceKlass* cls = current_class();

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

    _st->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; }

  PrintHierarchy(outputStream* st = tty) : _st(st) {}

};

// 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; }

  // 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 (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) {

      _exception_message = generate_conflicts_message(&qualified_methods,CHECK);

      _exception_name = vmSymbols::java_lang_IncompatibleClassChangeError();

      LogTarget(Debug, defaultmethods) lt;

      if (lt.is_enabled()) {

        LogStream ls(lt);

        _exception_message->print_value_on(&ls);

        ls.cr();

      }

    }

  }

  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()) {

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

    }

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

  }

};

Symbol* MethodFamily::generate_no_defaults_message(TRAPS) const {

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

}

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

  ss.write((const char*)klass_name->bytes(), klass_name->utf8_length());

  ss.print(".");

  ss.write((const char*)name->bytes(), name->utf8_length());

  ss.write((const char*)signature->bytes(), signature->utf8_length());

  ss.print(" is abstract");

  return SymbolTable::new_symbol(ss.base(), (int)ss.size());

}

Symbol* MethodFamily::generate_conflicts_message(GrowableArray<Method*>* methods, TRAPS) const {

  stringStream ss;

  ss.print("Conflicting default methods:");

  for (int i = 0; i < methods->length(); ++i) {

    Method* method = methods->at(i);

    Symbol* klass = method->klass_name();

    Symbol* name = method->name();

    ss.print(" ");

    ss.write((const char*)klass->bytes(), klass->utf8_length());

    ss.print(".");

    ss.write((const char*)name->bytes(), name->utf8_length());

  }

  return SymbolTable::new_symbol(ss.base(), (int)ss.size());

}

class StateRestorer;

// StatefulMethodFamily is a wrapper around a MethodFamily that maintains the

// qualification state during hierarchy visitation, and applies that state

// when adding members to the MethodFamily

class StatefulMethodFamily : public ResourceObj {

  friend class StateRestorer;

 private:

  QualifiedState _qualification_state;

  void set_qualification_state(QualifiedState state) {

    _qualification_state = state;

  }

 protected:

  MethodFamily _method_family;

 public:

  StatefulMethodFamily() {

   _qualification_state = QUALIFIED;

  }