/*

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

 * Copyright (c) 2019 SAP SE. 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/systemDictionary.hpp"

#include "gc/shared/gcLocker.hpp"

#include "interpreter/bytecodeUtils.hpp"

#include "memory/resourceArea.hpp"

#include "runtime/signature.hpp"

#include "runtime/safepointVerifiers.hpp"

#include "utilities/events.hpp"

#include "utilities/ostream.hpp"

class SimulatedOperandStack;

class ExceptionMessageBuilder;

// The entries of a SimulatedOperandStack. They carry the analysis

// information gathered for the slot.

class StackSlotAnalysisData {

 private:

  friend class SimulatedOperandStack;

  friend class ExceptionMessageBuilder;

  unsigned int _bci:17;    // The bci of the bytecode that pushed the current value on the operand stack.

                           // INVALID if ambiguous, e.g. after a control flow merge.

                           // 16 bits for bci (max bytecode size) and one for INVALID.

  unsigned int _type:15;   // The BasicType of the value on the operand stack.

  // Merges this slot data with the given one and returns the result. If

  // the bcis of the two merged objects are different, the bci of the result

  // will be undefined. If the types are different, the result type is T_CONFLICT.

  // (An exception is if one type is an array and the other is object, then

  // the result type will be T_OBJECT).

  StackSlotAnalysisData merge(StackSlotAnalysisData other);

 public:

  // Creates a new object with an invalid bci and the given type.

  StackSlotAnalysisData(BasicType type = T_CONFLICT);

  // Creates a new object with the given bci and type.

  StackSlotAnalysisData(int bci, BasicType type);

  enum {

    // An invalid bytecode index, as > 65535.

    INVALID = 0x1FFFF

  };

  // Returns the bci. If the bci is invalid, INVALID is returned.

  unsigned int get_bci();

  // Returns true, if the bci is not invalid.

  bool has_bci() { return get_bci() != INVALID; }

  // Returns the type of the slot data.

  BasicType get_type();

};

// A stack consisting of SimulatedOperandStackEntries.

// This represents the analysis information for the operand stack

// for a given bytecode at a given bci.

// It also holds an additional field that serves to collect

// information whether local slots were written.

class SimulatedOperandStack: CHeapObj<mtInternal> {

 private:

  friend class ExceptionMessageBuilder;

  friend class StackSlotAnalysisData;

  // The stack.

  GrowableArray<StackSlotAnalysisData> _stack;

  // Optimized bytecode can reuse local variable slots for several

  // local variables.

  // If there is no variable name information, we print 'parameter<i>'

  // if a parameter maps to a local slot. Once a local slot has been

  // written, we don't know any more whether it was written as the

  // corresponding parameter, or whether another local has been

  // mapped to the slot. So we don't want to print 'parameter<i>' any

  // more, but 'local<i>'. Similary for 'this'.

  // Therefore, during the analysis, we mark a bit for local slots that

  // get written and propagate this information.

  // We only run the analysis for 64 slots. If a method has more

  // parameters, we print 'local<i>' in all cases.

  uint64_t _written_local_slots;

  SimulatedOperandStack(): _written_local_slots(0) { };

  SimulatedOperandStack(const SimulatedOperandStack &copy);

  // Pushes the given slot data.

  void push_raw(StackSlotAnalysisData slotData);

  // Like push_raw, but if the slotData has type long or double, we push two.

  void push(StackSlotAnalysisData slotData);

  // Like push(slotData), but using bci/type to create an instance of

  // StackSlotAnalysisData first.

  void push(int bci, BasicType type);

  // Pops the given number of entries.

  void pop(int slots);

  // Merges this with the given stack by merging all entries. The

  // size of the stacks must be the same.

  void merge(SimulatedOperandStack const& other);

 public:

  // Returns the size of the stack.

  int get_size() const;

  // Returns the slot data at the given index. Slot 0 is top of stack.

  StackSlotAnalysisData get_slot_data(int slot);

  // Mark that local slot i was written.

  void set_local_slot_written(int i);

  // Check whether local slot i was written by this or a previous bytecode.

  bool local_slot_was_written(int i);

};

// Helper class to build internal exception messages for exceptions

// that are thrown because prerequisites to execute a bytecode

// are not met.

// E.g., if a NPE is thrown because an iload can not be executed

// by the VM because the reference to load from is null.

//

// It analyses the bytecode to assemble Java-like message text

// to give precise information where in a larger expression the

// exception occured.

//

// To assemble this message text, it is needed to know how

// operand stack slot entries were pushed on the operand stack.

// This class contains an analysis over the bytecodes to compute

// this information. The information is stored in a

// SimulatedOperandStack for each bytecode.

class ExceptionMessageBuilder : public StackObj {

  // The stacks for each bytecode.

  GrowableArray<SimulatedOperandStack*>* _stacks;

  // The method.

  Method* _method;

  // The number of entries used (the sum of all entries of all stacks).

  int _nr_of_entries;

  // If true, we have added at least one new stack.

  bool _added_one;

  // If true, we have processed all bytecodes.

  bool _all_processed;

  // The maximum number of entries we want to use. This is used to

  // limit the amount of memory we waste for insane methods (as they

  // appear in JCK tests).

  static const int _max_entries = 1000000;

  static const int _max_cause_detail = 5;

  // Merges the stack the the given bci with the given stack. If there

  // is no stack at the bci, we just put the given stack there. This

  // method doesn't takes ownership of the stack.

  void merge(int bci, SimulatedOperandStack* stack);

  // Processes the instruction at the given bci in the method. Returns

  // the size of the instruction.

  int do_instruction(int bci);

  bool print_NPE_cause0(outputStream *os, int bci, int slot, int max_detail,

                        bool inner_expr = false, const char *prefix = NULL);

 public:

  // Creates an ExceptionMessageBuilder object and runs the analysis

  // building SimulatedOperandStacks for each bytecode in the given

  // method (the method must be rewritten already). Note that you're

  // not allowed to use this object when crossing a safepoint! If the

  // bci is != -1, we only create the stacks as far as needed to get a

  // stack for the bci.

  ExceptionMessageBuilder(Method* method, int bci = -1);

  // Releases the resources.

  ~ExceptionMessageBuilder();

  // Returns the number of stacks (this is the size of the method).

  int get_size() { return _stacks->length() - 1; }

  // Assuming that a NullPointerException was thrown at the given bci,

  // we return the nr of the slot holding the null reference. If this

  // NPE is created by hand, we return -2 as the slot. If there

  // cannot be a NullPointerException at the bci, -1 is returned.

  int get_NPE_null_slot(int bci);

  // Prints a java-like expression for the bytecode that pushed

  // the value to the given slot being live at the given bci.

  // It constructs the expression by recursing backwards over the

  // bytecode using the results of the analysis done in the

  // constructor of ExceptionMessageBuilder.

  //  os:   The stream to print the message to.

  //  bci:  The index of the bytecode that caused the NPE.

  //  slot: The slot on the operand stack that contains null.

  //        The slots are numbered from TOS downwards, i.e.,

  //        TOS has the slot number 0, that below 1 and so on.

  //

  // Returns false if nothing was printed, else true.

  bool print_NPE_cause(outputStream *os, int bci, int slot);

  // Prints a string describing the failed action.

  void print_NPE_failed_action(outputStream *os, int bci);

};

// Replaces the following well-known class names:

//   java.lang.Object -> Object

//   java.lang.String -> String

static char *trim_well_known_class_names_from_signature(char *signature) {

  size_t len = strlen(signature);

  size_t skip_len = strlen("java.lang.");

  size_t min_pattern_len = strlen("java.lang.String");

  if (len < min_pattern_len) return signature;

  for (size_t isrc = 0, idst = 0; isrc <= len; isrc++, idst++) {

    // We must be careful not to trim names like test.java.lang.String.

    if ((isrc == 0 && strncmp(signature + isrc, "java.lang.Object", min_pattern_len) == 0) ||

        (isrc == 0 && strncmp(signature + isrc, "java.lang.String", min_pattern_len) == 0) ||

        (isrc > 1  && strncmp(signature + isrc-2, ", java.lang.Object", min_pattern_len+2) == 0) ||

        (isrc > 1  && strncmp(signature + isrc-2, ", java.lang.String", min_pattern_len+2) == 0)   ) {

      isrc += skip_len;

    }

    if (idst != isrc) {

      signature[idst] = signature[isrc];

    }

  }

  return signature;

}

// Replaces the following well-known class names:

//   java.lang.Object -> Object

//   java.lang.String -> String

static void print_klass_name(outputStream *os, Symbol *klass) {

  const char *name = klass->as_klass_external_name();

  if (strcmp(name, "java.lang.Object") == 0) name = "Object";

  if (strcmp(name, "java.lang.String") == 0) name = "String";

  os->print("%s", name);

}

// Prints the name of the method that is described at constant pool

// index cp_index in the constant pool of method 'method'.

static void print_method_name(outputStream *os, Method* method, int cp_index) {

  ResourceMark rm;

  ConstantPool* cp  = method->constants();

  Symbol* klass     = cp->klass_ref_at_noresolve(cp_index);

  Symbol* name      = cp->name_ref_at(cp_index);

  Symbol* signature = cp->signature_ref_at(cp_index);

  print_klass_name(os, klass);

  os->print(".%s(", name->as_C_string());

  stringStream sig;

  signature->print_as_signature_external_parameters(&sig);

  os->print("%s)", trim_well_known_class_names_from_signature(sig.as_string()));

}

// Prints the name of the field that is described at constant pool

// index cp_index in the constant pool of method 'method'.

static void print_field_and_class(outputStream *os, Method* method, int cp_index) {

  ResourceMark rm;

  ConstantPool* cp = method->constants();

  Symbol* klass    = cp->klass_ref_at_noresolve(cp_index);

  Symbol *name     = cp->name_ref_at(cp_index);

  print_klass_name(os, klass);

  os->print(".%s", name->as_C_string());

}

// Returns the name of the field that is described at constant pool

// index cp_index in the constant pool of method 'method'.

static char const* get_field_name(Method* method, int cp_index) {

  Symbol* name = method->constants()->name_ref_at(cp_index);

  return name->as_C_string();

}

static void print_local_var(outputStream *os, unsigned int bci, Method* method, int slot, bool is_parameter) {

  if (method->has_localvariable_table()) {

    for (int i = 0; i < method->localvariable_table_length(); i++) {

      LocalVariableTableElement* elem = method->localvariable_table_start() + i;

      unsigned int start = elem->start_bci;

      unsigned int end = start + elem->length;

      if ((bci >= start) && (bci < end) && (elem->slot == slot)) {

        ConstantPool* cp = method->constants();

        char *var =  cp->symbol_at(elem->name_cp_index)->as_C_string();

        os->print("%s", var);

        return;

      }

    }

  }

  // Handle at least some cases we know.

  if (!method->is_static() && (slot == 0) && is_parameter) {

    os->print("this");

  } else {

    int curr = method->is_static() ? 0 : 1;

    SignatureStream ss(method->signature());

    int param_index = 1;

    bool found = false;

    for (SignatureStream ss(method->signature()); !ss.is_done(); ss.next()) {

      if (ss.at_return_type()) {

        continue;

      }

      int size = type2size[ss.type()];

      if ((slot >= curr) && (slot < curr + size)) {

        found = true;

        break;

      }

      param_index += 1;

      curr += size;

    }

    if (found && is_parameter) {

      os->print("<parameter%d>", param_index);

    } else {

      // This is the best we can do.

      os->print("<local%d>", slot);

    }

  }

}

StackSlotAnalysisData::StackSlotAnalysisData(BasicType type) : _bci(INVALID), _type(type) {}

StackSlotAnalysisData::StackSlotAnalysisData(int bci, BasicType type) : _bci(bci), _type(type) {

  assert(bci >= 0, "BCI must be >= 0");

  assert(bci < 65536, "BCI must be < 65536");

}

unsigned int StackSlotAnalysisData::get_bci() {

  return _bci;

}

BasicType StackSlotAnalysisData::get_type() {

  return (BasicType)_type;

}

StackSlotAnalysisData StackSlotAnalysisData::merge(StackSlotAnalysisData other) {

  if (get_type() != other.get_type()) {

    if (((get_type() == T_OBJECT) || (get_type() == T_ARRAY)) &&

        ((other.get_type() == T_OBJECT) || (other.get_type() == T_ARRAY))) {

      if (get_bci() == other.get_bci()) {

        return StackSlotAnalysisData(get_bci(), T_OBJECT);

      } else {

        return StackSlotAnalysisData(T_OBJECT);

      }

    } else {

      return StackSlotAnalysisData(T_CONFLICT);

    }

  }

  if (get_bci() == other.get_bci()) {

    return *this;

  } else {

    return StackSlotAnalysisData(get_type());

  }

}

SimulatedOperandStack::SimulatedOperandStack(const SimulatedOperandStack &copy) {

  for (int i = 0; i < copy.get_size(); i++) {

    push_raw(copy._stack.at(i));

  }

  _written_local_slots = copy._written_local_slots;

}

void SimulatedOperandStack::push_raw(StackSlotAnalysisData slotData) {

  if (slotData.get_type() == T_VOID) {

    return;

  }

  _stack.push(slotData);

}

void SimulatedOperandStack::push(StackSlotAnalysisData slotData) {

  if (type2size[slotData.get_type()] == 2) {

    push_raw(slotData);

    push_raw(slotData);

  } else {

    push_raw(slotData);

  }

}

void SimulatedOperandStack::push(int bci, BasicType type) {

  push(StackSlotAnalysisData(bci, type));

}

void SimulatedOperandStack::pop(int slots) {

  for (int i = 0; i < slots; ++i) {

    _stack.pop();

  }

  assert(get_size() >= 0, "Popped too many slots");

}

void SimulatedOperandStack::merge(SimulatedOperandStack const& other) {

  assert(get_size() == other.get_size(), "Stacks not of same size");

  for (int i = get_size() - 1; i >= 0; --i) {

    _stack.at_put(i, _stack.at(i).merge(other._stack.at(i)));

  }

  _written_local_slots = _written_local_slots | other._written_local_slots;

}

int SimulatedOperandStack::get_size() const {

  return _stack.length();

}

StackSlotAnalysisData SimulatedOperandStack::get_slot_data(int slot) {

  assert(slot >= 0, "Slot=%d < 0", slot);

  assert(slot < get_size(), "Slot=%d >= size=%d", slot, get_size());

  return _stack.at(get_size() - slot - 1);

}

void SimulatedOperandStack::set_local_slot_written(int i) {

  // Local slots > 63 are very unlikely. Consider these

  // as written all the time. Saves space and complexity

  // for dynamic data size.

  if (i > 63) return;

  _written_local_slots = _written_local_slots | (1ULL << i);

}

bool SimulatedOperandStack::local_slot_was_written(int i) {

  if (i > 63) return true;

  return (_written_local_slots & (1ULL << i)) != 0;

}

ExceptionMessageBuilder::ExceptionMessageBuilder(Method* method, int bci) :

                    _method(method), _nr_of_entries(0),

                    _added_one(true), _all_processed(false) {

  ConstMethod* const_method = method->constMethod();

  const int len = const_method->code_size();

  assert(bci >= 0, "BCI too low: %d", bci);

  assert(bci < len, "BCI too large: %d size: %d", bci, len);

  _stacks = new GrowableArray<SimulatedOperandStack*> (len + 1);

  for (int i = 0; i <= len; ++i) {

    _stacks->push(NULL);

  }

  // Initialize stack a bci 0.

  _stacks->at_put(0, new SimulatedOperandStack());

  // And initialize the start of all exception handlers.

  if (const_method->has_exception_handler()) {

    ExceptionTableElement *et = const_method->exception_table_start();

    for (int i = 0; i < const_method->exception_table_length(); ++i) {

      u2 index = et[i].handler_pc;

      if (_stacks->at(index) == NULL) {

        _stacks->at_put(index, new SimulatedOperandStack());

        _stacks->at(index)->push(index, T_OBJECT);

      }

    }

  }

  // Do this until each bytecode has a stack or we haven't

  // added a new stack in one iteration.

  while (!_all_processed && _added_one) {

    _all_processed = true;

    _added_one = false;

    for (int i = 0; i < len; ) {

      // Analyse bytecode i. Step by size of the analyzed bytecode to next bytecode.

      i += do_instruction(i);

      // If we want the data only for a certain bci, we can possibly end early.

      if ((bci == i) && (_stacks->at(i) != NULL)) {

        _all_processed = true;

        break;

      }

      if (_nr_of_entries > _max_entries) {

        return;

      }

    }

  }

}

ExceptionMessageBuilder::~ExceptionMessageBuilder() {

  if (_stacks != NULL) {

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

      delete _stacks->at(i);

    }

  }

}

void ExceptionMessageBuilder::merge(int bci, SimulatedOperandStack* stack) {

  assert(stack != _stacks->at(bci), "Cannot merge itself");

  if (_stacks->at(bci) != NULL) {

    stack->merge(*_stacks->at(bci));

  } else {

    // Got a new stack, so count the entries.

    _nr_of_entries += stack->get_size();

  }