--- a/src/share/vm/oops/klassVtable.cpp	Tue Sep 17 23:12:27 2013 +0200
+++ b/src/share/vm/oops/klassVtable.cpp	Fri Sep 13 22:38:02 2013 -0400
@@ -47,11 +47,12 @@
 
 
 // this function computes the vtable size (including the size needed for miranda
-// methods) and the number of miranda methods in this class
+// methods) and the number of miranda methods in this class.
 // Note on Miranda methods: Let's say there is a class C that implements
-// interface I.  Let's say there is a method m in I that neither C nor any
-// of its super classes implement (i.e there is no method of any access, with
-// the same name and signature as m), then m is a Miranda method which is
+// interface I, and none of C's superclasses implements I.
+// Let's say there is an abstract method m in I that neither C
+// nor any of its super classes implement (i.e there is no method of any access,
+// with the same name and signature as m), then m is a Miranda method which is
 // entered as a public abstract method in C's vtable.  From then on it should
 // treated as any other public method in C for method over-ride purposes.
 void klassVtable::compute_vtable_size_and_num_mirandas(
@@ -111,10 +112,13 @@
 }
 
 int klassVtable::index_of(Method* m, int len) const {
-  assert(m->vtable_index() >= 0, "do not ask this of non-vtable methods");
+  assert(m->has_vtable_index(), "do not ask this of non-vtable methods");
   return m->vtable_index();
 }
 
+// Copy super class's vtable to the first part (prefix) of this class's vtable,
+// and return the number of entries copied.  Expects that 'super' is the Java
+// super class (arrays can have "array" super classes that must be skipped).
 int klassVtable::initialize_from_super(KlassHandle super) {
   if (super.is_null()) {
     return 0;
@@ -139,14 +143,14 @@
   }
 }
 
-// Revised lookup semantics   introduced 1.3 (Kestral beta)
+//
+// Revised lookup semantics   introduced 1.3 (Kestrel beta)
 void klassVtable::initialize_vtable(bool checkconstraints, TRAPS) {
 
   // Note:  Arrays can have intermediate array supers.  Use java_super to skip them.
   KlassHandle super (THREAD, klass()->java_super());
   int nofNewEntries = 0;
 
-
   if (PrintVtables && !klass()->oop_is_array()) {
     ResourceMark rm(THREAD);
     tty->print_cr("Initializing: %s", _klass->name()->as_C_string());
@@ -174,8 +178,10 @@
     int len = methods->length();
     int initialized = super_vtable_len;
 
-    // update_inherited_vtable can stop for gc - ensure using handles
+    // Check each of this class's methods against super;
+    // if override, replace in copy of super vtable, otherwise append to end
     for (int i = 0; i < len; i++) {
+      // update_inherited_vtable can stop for gc - ensure using handles
       HandleMark hm(THREAD);
       assert(methods->at(i)->is_method(), "must be a Method*");
       methodHandle mh(THREAD, methods->at(i));
@@ -189,11 +195,11 @@
       }
     }
 
-    // add miranda methods; it will also update the value of initialized
-    fill_in_mirandas(&initialized);
+    // add miranda methods to end of vtable.
+    initialized = fill_in_mirandas(initialized);
 
     // In class hierarchies where the accessibility is not increasing (i.e., going from private ->
-    // package_private -> publicprotected), the vtable might actually be smaller than our initial
+    // package_private -> public/protected), the vtable might actually be smaller than our initial
     // calculation.
     assert(initialized <= _length, "vtable initialization failed");
     for(;initialized < _length; initialized++) {
@@ -248,14 +254,8 @@
   return superk;
 }
 
-// Methods that are "effectively" final don't need vtable entries.
-bool method_is_effectively_final(
-    AccessFlags klass_flags, methodHandle target) {
-  return target->is_final() || klass_flags.is_final() && !target->is_overpass();
-}
-
 // Update child's copy of super vtable for overrides
-// OR return true if a new vtable entry is required
+// OR return true if a new vtable entry is required.
 // Only called for InstanceKlass's, i.e. not for arrays
 // If that changed, could not use _klass as handle for klass
 bool klassVtable::update_inherited_vtable(InstanceKlass* klass, methodHandle target_method, int super_vtable_len,
@@ -263,6 +263,7 @@
   ResourceMark rm;
   bool allocate_new = true;
   assert(klass->oop_is_instance(), "must be InstanceKlass");
+  assert(klass == target_method()->method_holder(), "caller resp.");
 
   // Initialize the method's vtable index to "nonvirtual".
   // If we allocate a vtable entry, we will update it to a non-negative number.
@@ -273,11 +274,17 @@
     return false;
   }
 
-  if (method_is_effectively_final(klass->access_flags(), target_method)) {
+  if (target_method->is_final_method(klass->access_flags())) {
     // a final method never needs a new entry; final methods can be statically
     // resolved and they have to be present in the vtable only if they override
     // a super's method, in which case they re-use its entry
     allocate_new = false;
+  } else if (klass->is_interface()) {
+    allocate_new = false;  // see note below in needs_new_vtable_entry
+    // An interface never allocates new vtable slots, only inherits old ones.
+    // This method will either be assigned its own itable index later,
+    // or be assigned an inherited vtable index in the loop below.
+    target_method()->set_vtable_index(Method::pending_itable_index);
   }
 
   // we need a new entry if there is no superclass
@@ -411,8 +418,14 @@
                                          Symbol* classname,
                                          AccessFlags class_flags,
                                          TRAPS) {
+  if (class_flags.is_interface()) {
+    // Interfaces do not use vtables, so there is no point to assigning
+    // a vtable index to any of their methods.  If we refrain from doing this,
+    // we can use Method::_vtable_index to hold the itable index
+    return false;
+  }
 
-  if (method_is_effectively_final(class_flags, target_method) ||
+  if (target_method->is_final_method(class_flags) ||
       // a final method never needs a new entry; final methods can be statically
       // resolved and they have to be present in the vtable only if they override
       // a super's method, in which case they re-use its entry
@@ -500,7 +513,8 @@
   return Method::invalid_vtable_index;
 }
 
-// check if an entry is miranda
+// check if an entry at an index is miranda
+// requires that method m at entry be declared ("held") by an interface.
 bool klassVtable::is_miranda_entry_at(int i) {
   Method* m = method_at(i);
   Klass* method_holder = m->method_holder();
@@ -516,7 +530,9 @@
   return false;
 }
 
-// check if a method is a miranda method, given a class's methods table and it's super
+// check if a method is a miranda method, given a class's methods table and its super
+// "miranda" means not static, not defined by this class, and not defined
+// in super unless it is private and therefore inaccessible to this class.
 // the caller must make sure that the method belongs to an interface implemented by the class
 bool klassVtable::is_miranda(Method* m, Array<Method*>* class_methods, Klass* super) {
   if (m->is_static()) {
@@ -541,6 +557,14 @@
   return false;
 }
 
+// Scans current_interface_methods for miranda methods that do not
+// already appear in new_mirandas and are also not defined-and-non-private
+// in super (superclass).  These mirandas are added to all_mirandas if it is
+// not null; in addition, those that are not duplicates of miranda methods
+// inherited by super from its interfaces are added to new_mirandas.
+// Thus, new_mirandas will be the set of mirandas that this class introduces,
+// all_mirandas will be the set of all mirandas applicable to this class
+// including all defined in superclasses.
 void klassVtable::add_new_mirandas_to_lists(
     GrowableArray<Method*>* new_mirandas, GrowableArray<Method*>* all_mirandas,
     Array<Method*>* current_interface_methods, Array<Method*>* class_methods,
@@ -599,17 +623,22 @@
   }
 }
 
-// fill in mirandas
-void klassVtable::fill_in_mirandas(int* initialized) {
+// Discover miranda methods ("miranda" = "interface abstract, no binding"),
+// and append them into the vtable starting at index initialized,
+// return the new value of initialized.
+int klassVtable::fill_in_mirandas(int initialized) {
   GrowableArray<Method*> mirandas(20);
   get_mirandas(&mirandas, NULL, ik()->super(), ik()->methods(),
                ik()->local_interfaces());
   for (int i = 0; i < mirandas.length(); i++) {
-    put_method_at(mirandas.at(i), *initialized);
-    ++(*initialized);
+    put_method_at(mirandas.at(i), initialized);
+    ++initialized;
   }
+  return initialized;
 }
 
+// Copy this class's vtable to the vtable beginning at start.
+// Used to copy superclass vtable to prefix of subclass's vtable.
 void klassVtable::copy_vtable_to(vtableEntry* start) {
   Copy::disjoint_words((HeapWord*)table(), (HeapWord*)start, _length * vtableEntry::size());
 }
@@ -723,6 +752,12 @@
 
 // Initialization
 void klassItable::initialize_itable(bool checkconstraints, TRAPS) {
+  if (_klass->is_interface()) {
+    // This needs to go after vtable indexes are assigned but
+    // before implementors need to know the number of itable indexes.
+    assign_itable_indexes_for_interface(_klass());
+  }
+
   // Cannot be setup doing bootstrapping, interfaces don't have
   // itables, and klass with only ones entry have empty itables
   if (Universe::is_bootstrapping() ||
@@ -754,45 +789,89 @@
 }
 
 
+inline bool interface_method_needs_itable_index(Method* m) {
+  if (m->is_static())           return false;   // e.g., Stream.empty
+  if (m->is_initializer())      return false;   // <init> or <clinit>
+  // If an interface redeclares a method from java.lang.Object,
+  // it should already have a vtable index, don't touch it.
+  // e.g., CharSequence.toString (from initialize_vtable)
+  // if (m->has_vtable_index())  return false; // NO!
+  return true;
+}
+
+int klassItable::assign_itable_indexes_for_interface(Klass* klass) {
+  // an interface does not have an itable, but its methods need to be numbered
+  if (TraceItables) tty->print_cr("%3d: Initializing itable for interface %s", ++initialize_count,
+                                  klass->name()->as_C_string());
+  Array<Method*>* methods = InstanceKlass::cast(klass)->methods();
+  int nof_methods = methods->length();
+  int ime_num = 0;
+  for (int i = 0; i < nof_methods; i++) {
+    Method* m = methods->at(i);
+    if (interface_method_needs_itable_index(m)) {
+      assert(!m->is_final_method(), "no final interface methods");
+      // If m is already assigned a vtable index, do not disturb it.
+      if (!m->has_vtable_index()) {
+        assert(m->vtable_index() == Method::pending_itable_index, "set by initialize_vtable");
+        m->set_itable_index(ime_num);
+        // Progress to next itable entry
+        ime_num++;
+      }
+    }
+  }
+  assert(ime_num == method_count_for_interface(klass), "proper sizing");
+  return ime_num;
+}
+
+int klassItable::method_count_for_interface(Klass* interf) {
+  assert(interf->oop_is_instance(), "must be");
+  assert(interf->is_interface(), "must be");
+  Array<Method*>* methods = InstanceKlass::cast(interf)->methods();
+  int nof_methods = methods->length();
+  while (nof_methods > 0) {
+    Method* m = methods->at(nof_methods-1);
+    if (m->has_itable_index()) {
+      int length = m->itable_index() + 1;
+#ifdef ASSERT
+      while (nof_methods = 0) {
+        m = methods->at(--nof_methods);
+        assert(!m->has_itable_index() || m->itable_index() < length, "");
+      }
+#endif //ASSERT
+      return length;  // return the rightmost itable index, plus one
+    }
+    nof_methods -= 1;
+  }
+  // no methods have itable indexes
+  return 0;
+}
+
+
 void klassItable::initialize_itable_for_interface(int method_table_offset, KlassHandle interf_h, bool checkconstraints, TRAPS) {
   Array<Method*>* methods = InstanceKlass::cast(interf_h())->methods();
   int nof_methods = methods->length();
   HandleMark hm;
-  KlassHandle klass = _klass;
   assert(nof_methods > 0, "at least one method must exist for interface to be in vtable");
   Handle interface_loader (THREAD, InstanceKlass::cast(interf_h())->class_loader());
-  int ime_num = 0;
 
-  // Skip first Method* if it is a class initializer
-  int i = methods->at(0)->is_static_initializer() ? 1 : 0;
-
-  // m, method_name, method_signature, klass reset each loop so they
-  // don't need preserving across check_signature_loaders call
-  // methods needs a handle in case of gc from check_signature_loaders
-  for(; i < nof_methods; i++) {
+  int ime_count = method_count_for_interface(interf_h());
+  for (int i = 0; i < nof_methods; i++) {
     Method* m = methods->at(i);
-    Symbol* method_name = m->name();
-    Symbol* method_signature = m->signature();
-
-    // This is same code as in Linkresolver::lookup_instance_method_in_klasses
-    Method* target = klass->uncached_lookup_method(method_name, method_signature);
-    while (target != NULL && target->is_static()) {
-      // continue with recursive lookup through the superclass
-      Klass* super = target->method_holder()->super();
-      target = (super == NULL) ? (Method*)NULL : super->uncached_lookup_method(method_name, method_signature);
+    methodHandle target;
+    if (m->has_itable_index()) {
+      LinkResolver::lookup_instance_method_in_klasses(target, _klass, m->name(), m->signature(), CHECK);
     }
     if (target == NULL || !target->is_public() || target->is_abstract()) {
       // Entry do not resolve. Leave it empty
     } else {
       // Entry did resolve, check loader constraints before initializing
       // if checkconstraints requested
-      methodHandle  target_h (THREAD, target); // preserve across gc
       if (checkconstraints) {
         Handle method_holder_loader (THREAD, target->method_holder()->class_loader());
         if (method_holder_loader() != interface_loader()) {
           ResourceMark rm(THREAD);
           Symbol* failed_type_symbol =
-            SystemDictionary::check_signature_loaders(method_signature,
+            SystemDictionary::check_signature_loaders(m->signature(),
                                                       method_holder_loader,
                                                       interface_loader,
                                                       true, CHECK);
@@ -803,9 +882,9 @@
               "and the class loader (instance of %s) for interface "
               "%s have different Class objects for the type %s "
               "used in the signature";
-            char* sig = target_h()->name_and_sig_as_C_string();
+            char* sig = target()->name_and_sig_as_C_string();
             const char* loader1 = SystemDictionary::loader_name(method_holder_loader());
-            char* current = klass->name()->as_C_string();
+            char* current = _klass->name()->as_C_string();
             const char* loader2 = SystemDictionary::loader_name(interface_loader());
             char* iface = InstanceKlass::cast(interf_h())->name()->as_C_string();
             char* failed_type_name = failed_type_symbol->as_C_string();
@@ -821,10 +900,10 @@
       }
 
       // ime may have moved during GC so recalculate address
-      itableOffsetEntry::method_entry(_klass(), method_table_offset)[ime_num].initialize(target_h());
+      int ime_num = m->itable_index();
+      assert(ime_num < ime_count, "oob");
+      itableOffsetEntry::method_entry(_klass(), method_table_offset)[ime_num].initialize(target());
     }
-    // Progress to next entry
-    ime_num++;
   }
 }
 
@@ -913,20 +992,22 @@
   virtual void doit(Klass* intf, int method_count) = 0;
 };
 
-// Visit all interfaces with at-least one method (excluding <clinit>)
+// Visit all interfaces with at least one itable method
 void visit_all_interfaces(Array<Klass*>* transitive_intf, InterfaceVisiterClosure *blk) {
   // Handle array argument
   for(int i = 0; i < transitive_intf->length(); i++) {
     Klass* intf = transitive_intf->at(i);
     assert(intf->is_interface(), "sanity check");
 
-    // Find no. of methods excluding a <clinit>
-    int method_count = InstanceKlass::cast(intf)->methods()->length();
-    if (method_count > 0) {
-      Method* m = InstanceKlass::cast(intf)->methods()->at(0);
-      assert(m != NULL && m->is_method(), "sanity check");
-      if (m->name() == vmSymbols::object_initializer_name()) {
-        method_count--;
+    // Find no. of itable methods
+    int method_count = 0;
+    // method_count = klassItable::method_count_for_interface(intf);
+    Array<Method*>* methods = InstanceKlass::cast(intf)->methods();
+    if (methods->length() > 0) {
+      for (int i = methods->length(); --i >= 0; ) {
+        if (interface_method_needs_itable_index(methods->at(i))) {
+          method_count++;
+        }
       }
     }
 
@@ -1024,40 +1105,26 @@
 }
 
 
-// m must be a method in an interface
-int klassItable::compute_itable_index(Method* m) {
-  InstanceKlass* intf = m->method_holder();
-  assert(intf->is_interface(), "sanity check");
-  Array<Method*>* methods = intf->methods();
-  int index = 0;
-  while(methods->at(index) != m) {
-    index++;
-    assert(index < methods->length(), "should find index for resolve_invoke");
-  }
-  // Adjust for <clinit>, which is left out of table if first method
-  if (methods->length() > 0 && methods->at(0)->is_static_initializer()) {
-    index--;
-  }
-  return index;
-}
-
-
-// inverse to compute_itable_index
+// inverse to itable_index
 Method* klassItable::method_for_itable_index(Klass* intf, int itable_index) {
   assert(InstanceKlass::cast(intf)->is_interface(), "sanity check");
+  assert(intf->verify_itable_index(itable_index), "");
   Array<Method*>* methods = InstanceKlass::cast(intf)->methods();
 
+  if (itable_index < 0 || itable_index >= method_count_for_interface(intf))
+    return NULL;                // help caller defend against bad indexes
+
   int index = itable_index;
-  // Adjust for <clinit>, which is left out of table if first method
-  if (methods->length() > 0 && methods->at(0)->is_static_initializer()) {
-    index++;
+  Method* m = methods->at(index);
+  int index2 = -1;
+  while (!m->has_itable_index() ||
+         (index2 = m->itable_index()) != itable_index) {
+    assert(index2 < itable_index, "monotonic");
+    if (++index == methods->length())
+      return NULL;
+    m = methods->at(index);
   }
-
-  if (itable_index < 0 || index >= methods->length())
-    return NULL;                // help caller defend against bad indexes
-
-  Method* m = methods->at(index);
-  assert(compute_itable_index(m) == itable_index, "correct inverse");
+  assert(m->itable_index() == itable_index, "correct inverse");
 
   return m;
 }