Exponential compilation and startup speed with default methods

Test.java

public class Test {
    interface I { default void m1() {} }
    interface A1 extends I { default void a1() {} }
    interface A2 extends I { default void a2() {} }
    static class A3 implements A1, A2 {}
    interface B1 extends A1, A2 { default void b1() {} }
    interface B2 extends A1, A2 { default void b2() {} }
    static class B3 extends A3 implements B1, B2 {}
    interface C1 extends B1, B2 { default void c1() {}  }
    interface C2 extends B1, B2 { default void c2() {} }
    static class C3 extends B3 implements C1, C2 {}
    interface D1 extends C1, C2 { default void d1() {} }
    interface D2 extends C1, C2 { default void d2() {} }
    static class D3 extends C3 implements D1, D2 {}
    interface E1 extends D1, D2 { default void e1() {} }
    interface E2 extends D1, D2 { default void e2() {} }
    static class E3 extends D3 implements E1, E2 {}
    interface F1 extends E1, E2 { default void f1() {} }
    interface F2 extends E1, E2 { default void f2() {} }
    static class F3 extends E3 implements F1, F2 {}
    interface G1 extends F1, F2 { default void g1() {} }
    interface G2 extends F1, F2 { default void g2() {} }
    static class G3 extends F3 implements G1, G2 {}
    interface H1 extends G1, G2 { default void h1() {} }
    interface H2 extends G1, G2 { default void h2() {} }
    static class H3 extends G3 implements H1, H2 {}
    interface I1 extends H1, H2 { default void i1() {} }
    interface I2 extends H1, H2 { default void i2() {} }
    static class I3 extends H3 implements I1, I2 {}
    interface J1 extends I1, I2 { default void j1() {} }
    interface J2 extends I1, I2 { default void j2() {} }
    static class J3 extends I3 implements J1, J2 {}
    interface K1 extends J1, J2 { default void k1() {} }
    interface K2 extends J1, J2 { default void k2() {} }
    static class K3 extends J3 implements K1, K2 {}
    interface L1 extends K1, K2 { default void l1() {} }
    interface L2 extends K1, K2 { default void l2() {} }
    static class L3 extends K3 implements L1, L2 {}
    public static void main(String[] args) {
    	new L3();
    }
}

Level K:

⚡ time javac -d . sandbox/Test.java && time java -cp . Test

real    0m30.103s
user    0m31.339s
sys 0m0.342s

real    0m0.220s
user    0m0.170s
sys 0m0.045s

Level L:

% time javac -d . sandbox/Test.java && time java -cp . Test

real    2m16.642s
user    2m19.112s
sys 0m0.957s

real    0m0.360s
user    0m0.281s
sys 0m0.072s

/*
 * Copyright (c) 2012, 2015, 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.
 *
 */
package test

import java.lang.reflect.{Method, Modifier}

import scala.runtime.ObjectRef


abstract class HierarchyVisitor {
   val _visited = collection.mutable.Set[Class[_]]()

  case class Node(var _class: Class[_], var _algorithm_data: Any, visit_super: Boolean) {
    var _super_was_visited: Boolean = !visit_super
    var interface_index: Int = 0

    def number_of_interfaces(): Int = { _class.getInterfaces.length; }
    def set_super_visited(): Unit = { _super_was_visited = true; }
    def increment_visited_interface(): Unit = { interface_index += 1; }
    def set_all_interfaces_visited(): Unit = {
      interface_index = number_of_interfaces()
    }
    def has_visited_super() = { _super_was_visited; }
    def has_visited_all_interfaces() = {
      interface_index >= number_of_interfaces()
    }
    def interface_at(index: Int) = {
      _class.getInterfaces()(index)
    }
    def next_super() = { _class.getSuperclass }
    def next_interface() = {
      interface_at(interface_index)
    }
  }

  var _cancelled: Boolean = false
  var _path = collection.mutable.ArrayBuffer[Node]()

  def current_top() = { _path.last; }
  def has_more_nodes() = _path.nonEmpty
  def push(cls: Class[_], data: Any) = {
    assert(cls != null, "Requires a valid instance class")
    val node = Node(cls, data, has_super(cls))
    _path += node
  }
  def pop() = { _path.remove(_path.size - 1); }

  def reset_iteration() {
    _cancelled = false
    _path.clear()
  }
  def is_cancelled() = { _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.
  def has_super(cls: Class[_]) = {
    cls.getSuperclass != null
  }

  def node_at_depth(i: Int) = {
    if (i >= _path.length) null else _path.apply(_path.length - i - 1)
  }

  // Accessors available to the algorithm
  def current_depth() = { _path.length - 1; }

  def class_at_depth(i: Int): Class[_] = {
    val n = node_at_depth(i)
    if (n == null) null else n._class
  }
  def current_class() = { class_at_depth(0); }

  def data_at_depth(i: Int): Any = {
    val n = node_at_depth(i)
    if (n == null) null else n._algorithm_data
  }
  def current_data() = { data_at_depth(0); }

  def cancel_iteration() { _cancelled = true; }

  def new_node_data(cls: Class[_]): Any
  def free_node_data(data: Any): Unit = ()
  def visit(): Boolean

  def run(root: Class[_]) {
    reset_iteration()

    var algo_data = new_node_data(root)
    push(root, algo_data)
    var top_needs_visit = true

    do {
      toString
      var top: Node = current_top()

      if (top_needs_visit) {
        def visitIfNotVisited() = {
          if (!_visited(current_class())) {
            _visited += current_class()
            visit()
          } else false
        }
        if (!visit()) {
          // 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()) {
        free_node_data(top._algorithm_data)
        pop()
      } else {
        var next: Class[_] = null
        if (!top.has_visited_super()) {
          next = top.next_super()
          top.set_super_visited()
        } else {
          next = top.next_interface()
          top.increment_visited_interface()
        }
        algo_data = new_node_data(next)
        push(next, algo_data)
        top_needs_visit = true
      }
    } while (!is_cancelled() && has_more_nodes())
  }
}

class PrintHierarchy extends HierarchyVisitor {
  val seen = collection.mutable.Set[Class[_]]()
  def visit(): Boolean = {
    val cls = current_class()
    if (seen.contains(cls)) {
      false
    } else {
      seen += cls
      print("  " * current_depth())
      println(cls.getSimpleName)
      true
    }
  }

  def new_node_data(cls: Class[_]): Any = { null; }
  override def free_node_data(data: Any): Unit = ()
}


// Iterates over the superinterface type hierarchy looking for all methods
// with a specific erased signature.
class FindMethodsByErasedSig(var _method_name: String, var _method_signature: String) extends HierarchyVisitor {
  var _family: StatefulMethodFamily = _

  class MethodFamily {
    val _members = collection.mutable.ArrayBuffer[(Method, ObjectRef[QualifiedState])]()
    val _member_index = collection.mutable.Map[Method, Int]()

    var _selected_target: Method = _
    // Filled in later, if a unique target exists
    var _exception_message: String = _
    // If no unique target is found
    var _exception_name: String = ""
    override def toString = s"MethodFamily(${_selected_target}, ${_exception_name}, ${_exception_message})"

    // If no unique target is found

    def contains_method(method: Method): Boolean = {
      _member_index.contains(method)
    }

    def add_method(method: Method, state: QualifiedState) = {
      println(s"$method=$state")
      _member_index(method) = _members.length
      _members += Tuple2(method, ObjectRef.create(state))
    }

    def disqualify_method(method: Method) = {
      println(s"disqualify_method($method)")
      _members.apply(_member_index(method))._2.elem = 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;

    def set_target_if_empty(m: Method) = {
      if (_selected_target == null /*&& !m.is_overpass()*/ ) {
        _selected_target = m
      }
    }

    def record_qualified_method(m: Method): Unit = {
      // 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)
      }
    }

    def record_disqualified_method(m: Method) {
      // 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)
      }
    }

    def has_target() = {
      _selected_target != null
    }

    def throws_exception() = {
      _exception_message != null
    }

    def get_selected_target() = {
      _selected_target
    }

    def get_exception_message() = {
      _exception_message
    }

    def get_exception_name() = {
      _exception_name
    }

    // Either sets the target or the exception error message
    def determine_target(root: Class[_] /*, TRAPS*/) {
      if (has_target() || throws_exception()) {
        return
      }

      // Qualified methods are maximally-specific methods
      // These include public, instance concrete (=default) and abstract methods
      val qualified_methods = scala.collection.mutable.ArrayBuffer[Method]()
      var num_defaults = 0
      var default_index = -1
      var qualified_index = -1
      for (entry <- _members) {
        if (entry._2.elem == QUALIFIED) {
          qualified_methods.append(entry._1)
          qualified_index += 1
          if (entry._1.isDefault) {
            num_defaults += 1
            default_index = qualified_index
          }
        }
      }

      if (num_defaults == 0) {
        _exception_message = "none found"
        _exception_name = "AbstractMethodError"

        // If only one qualified method is default, select that
      } else if (num_defaults == 1) {
        _selected_target = qualified_methods.apply(default_index)

      } else if (num_defaults > 1) {
        _exception_message = qualified_methods.mkString("\n")
        _exception_name = "IncompatibleClassChangeError"
      }
    }

    def contains_signature(query: String) {
      _members.exists(m => descriptorOf(m._1) == query)
    }
  }

  sealed abstract class QualifiedState
  case object QUALIFIED extends QualifiedState
  case object DISQUALIFIED extends QualifiedState
  case class StatefulMethodFamily(var _qualification_state: QualifiedState = QUALIFIED, var _method_family: MethodFamily = new MethodFamily()) {

    def set_target_if_empty(m: Method) = _method_family.set_target_if_empty(m)

    def record_method_and_dq_further(m: Method): StateRestorer = {
      val mark = StateRestorer(_qualification_state, this)
      if (_qualification_state == QUALIFIED) {
        _method_family.record_qualified_method(m)
      } else {
        _method_family.record_disqualified_method(m)
      }
      // Everything found "above"??? this method in the hierarchy walk is set to
      // disqualified
      _qualification_state = DISQUALIFIED
      mark
    }

    def get_method_family(): MethodFamily = _method_family
  }
  case class StateRestorer(_state_to_restore: QualifiedState, _method: StatefulMethodFamily) {
    def restore_state() { _method._qualification_state = _state_to_restore; }
  }
  class PseudoScope {
    val marks = collection.mutable.ArrayBuffer[StateRestorer]()
    def add_mark(restorer: StateRestorer) = marks += restorer

    def destroy(): Unit = marks.foreach(_.restore_state())
    override def toString = "<>"
  }

  def get_discovered_family: MethodFamily = {
      if (_family != null) {
        _family.get_method_family()
      } else {
        null
      }
  }

  def new_node_data(cls: Class[_]) = { new PseudoScope(); }
  override def free_node_data(node_data: Any): Unit = {
    node_data.asInstanceOf[PseudoScope].destroy()
  }

  def descriptorOf(m: Method): String = {
    java.lang.invoke.MethodType.methodType(m.getReturnType, m.getParameterTypes).toMethodDescriptorString
  }

  // Find all methods on this hierarchy that match this
  // method's erased (name, signature)
  def visit() = {
    println(_path)
    val scope = current_data().asInstanceOf[PseudoScope]
    val iklass = current_class()

    val m = iklass.getDeclaredMethods.find(x => x.getName == _method_name && descriptorOf(x) == _method_signature).orNull
    // private interface methods are not candidates for default methods
    // invokespecial to private interface methods doesn't use default method logic
    // private class methods are not candidates for default methods,
    // private methods do not override default methods, so need to perform
    // default method inheritance without including private methods
    // The overpasses are your supertypes' errors, we do not include them
    // future: take access controls into account for superclass methods
    if (m != null && !Modifier.isStatic(m.getModifiers) && /*!m->is_overpass() && */ !Modifier.isPrivate(m.getModifiers)) {
      if (_family == null) {
        _family = StatefulMethodFamily()
      }

      if (iklass.isInterface) {
        val restorer: StateRestorer = _family.record_method_and_dq_further(m)
        scope.add_mark(restorer)
      } else {
        // This is the rule that methods in classes "win" (bad word) over
        // methods in interfaces. This works because of single inheritance
        // private methods in classes do not "win", they will be found
        // first on searching, but overriding for invokevirtual needs
        // to find default method candidates for the same signature
        _family.set_target_if_empty(m)
      }
    }
    true
  }
}


object Scratch {
  def main(args: Array[String]): Unit = {
//    new PrintHierarchy().run(classOf[List[_]])

    val findMethodsByErasedSig = new FindMethodsByErasedSig("spliterator", "()Ljava/util/Spliterator;")
    val klass = Class.forName("java.util.AbstractSet")
    findMethodsByErasedSig.run(klass)
    println(findMethodsByErasedSig._family)
    val methodFamily = findMethodsByErasedSig.get_discovered_family
    methodFamily.determine_target(klass)
    Console.out.flush()
    assert(methodFamily._exception_name == "")
  }
}