First part of campaign to make orElse on partia...

First part of campaign to make orElse on partial functions faster than
exponential. In fact, now it's linear, with zero overhead for the common
case. Review by extempore.

2 files changed, 38 insertions, 9 deletions

diff --git a/src/library/scala/PartialFunction.scala b/src/library/scala/PartialFunction.scala
index 69e4dab675..612460d935 100644
--- a/src/library/scala/PartialFunction.scala
+++ b/src/library/scala/PartialFunction.scala
@@ -25,6 +25,8 @@ trait PartialFunction[-A, +B] extends (A => B) {
    */
   def isDefinedAt(x: A): Boolean
 
+  protected def missingCase[A1 <: A, B1 >: B]: PartialFunction[A1, B1] = PartialFunction.empty
+
   /** Composes this partial function with a fallback partial function which
    *  gets applied where this partial function is not defined.
    *
@@ -37,12 +39,12 @@ trait PartialFunction[-A, +B] extends (A => B) {
    */
   def orElse[A1 <: A, B1 >: B](that: PartialFunction[A1, B1]) : PartialFunction[A1, B1] =
     new runtime.AbstractPartialFunction[A1, B1] {
-    def isDefinedAt(x: A1): Boolean =
-      PartialFunction.this.isDefinedAt(x) || that.isDefinedAt(x)
-    def apply(x: A1): B1 =
-      if (PartialFunction.this.isDefinedAt(x)) PartialFunction.this.apply(x)
-      else that.apply(x)
-  }
+      def isDefinedAt(x: A1): Boolean =
+        PartialFunction.this.isDefinedAt(x) || that.isDefinedAt(x)
+      def apply(x: A1): B1 =
+        if (PartialFunction.this.isDefinedAt(x)) PartialFunction.this.apply(x)
+        else that.apply(x)
+    }
 
   /**  Composes this partial function with a transformation function that
    *   gets applied to results of this partial function.
@@ -84,11 +86,11 @@ trait PartialFunction[-A, +B] extends (A => B) {
 object PartialFunction {
   private[this] final val empty_pf: PartialFunction[Any, Nothing] = new runtime.AbstractPartialFunction[Any, Nothing] {
     def isDefinedAt(x: Any) = false
-    def apply(x: Any): Nothing = sys.error("undefined")
+    def apply(x: Any): Nothing = throw new MatchError(x)
     override def orElse[A1, B1](that: PartialFunction[A1, B1]): PartialFunction[A1, B1] = that
     override def lift = (x: Any) => None
   }
-  def empty[A, B] : PartialFunction[A, B] = empty_pf.asInstanceOf[PartialFunction[A, B]]
+  def empty[A, B] : PartialFunction[A, B] = empty_pf
 
   /** Creates a Boolean test based on a value and a partial function.
    *  It behaves like a 'match' statement with an implied 'case _ => false'
diff --git a/src/library/scala/runtime/AbstractPartialFunction.scala b/src/library/scala/runtime/AbstractPartialFunction.scala
index 2f8b54356f..ac68f58b5a 100644
--- a/src/library/scala/runtime/AbstractPartialFunction.scala
+++ b/src/library/scala/runtime/AbstractPartialFunction.scala
@@ -8,4 +8,31 @@
 
 package scala.runtime
 
-abstract class AbstractPartialFunction[-T1, +R] extends AbstractFunction1[T1, R] with PartialFunction[T1, R]
+/** This class provides a default implementation of partial functions
+ *  that is used for all partial function literals.
+ *  It contains an optimized `orElse` method which supports
+ *  chained `orElse` in linear time, and with no slow-down
+ *  if the `orElse` part is not needed.
+ *  The implementation of `orElse` works by cloning the abstract function object
+ *  and modifying a private `fallBack` variable that encodes the `getorElse` part.
+ */
+abstract class AbstractPartialFunction[-T1, +R]
+    extends AbstractFunction1[T1, R]
+    with PartialFunction[T1, R]
+    with Cloneable {
+
+  private var fallBack: PartialFunction[_, _] = PartialFunction.empty
+
+  override protected def missingCase[A1 <: T1, B1 >: R]: PartialFunction[A1, B1] = synchronized {
+    fallBack.asInstanceOf[PartialFunction[A1, B1]]
+  }
+
+  // Question: Need to ensure that fallBack is overwritten before any access
+  // Is the `synchronized` here the right thing to achieve this?
+  // Is there a cheaper way?
+  def orElseFast[A1 <: T1, B1 >: R](that: PartialFunction[A1, B1]) : PartialFunction[A1, B1] = {
+    val result = this.clone.asInstanceOf[AbstractPartialFunction[T1, R]]
+    result.synchronized { result.fallBack = this.fallBack orElse that }
+    result
+  }
+}