From 42c6fb8ce814ed109f6418bcc5809d23e1db1965 Mon Sep 17 00:00:00 2001 From: Pavel Pavlov Date: Tue, 21 Aug 2012 01:40:14 +0700 Subject: PartialFunction polishing - ScalaDocs added - TODOs fixed - controversive method `run` deleted - not used class runtime.AbstractTotalFunction removed - small corrections & fixes - tests for `orElse` & `runWith` --- src/library/scala/Function.scala | 4 +- src/library/scala/PartialFunction.scala | 114 ++++++++++++++------- .../scala/runtime/AbstractPartialFunction.scala | 40 +------- test/files/run/partialfun.check | 6 ++ test/files/run/partialfun.scala | 86 ++++++++++++++++ 5 files changed, 173 insertions(+), 77 deletions(-) create mode 100644 test/files/run/partialfun.check create mode 100644 test/files/run/partialfun.scala diff --git a/src/library/scala/Function.scala b/src/library/scala/Function.scala index 270581a3aa..d470f4c966 100644 --- a/src/library/scala/Function.scala +++ b/src/library/scala/Function.scala @@ -28,11 +28,11 @@ object Function { /** Turns a function `A => Option[B]` into a `PartialFunction[A, B]`. * - * TODO: check if the paragraph below is still correct * '''Important note''': this transformation implies the original function - * will be called 2 or more times on each logical invocation, because the + * may be called 2 or more times on each logical invocation, because the * only way to supply an implementation of `isDefinedAt` is to call the * function and examine the return value. + * See also [[scala.PartialFunction]], method `applyOrElse`. * * @param f a function `T => Option[R]` * @return a partial function defined for those inputs where diff --git a/src/library/scala/PartialFunction.scala b/src/library/scala/PartialFunction.scala index 7154b8da34..91eae2984a 100644 --- a/src/library/scala/PartialFunction.scala +++ b/src/library/scala/PartialFunction.scala @@ -67,7 +67,7 @@ trait PartialFunction[-A, +B] extends (A => B) { self => * of this partial function and `that`. The resulting partial function * takes `x` to `this(x)` where `this` is defined, and to `that(x)` where it is not. */ - def orElse[A1 <: A, B1 >: B](that: PartialFunction[A1, B1]) : PartialFunction[A1, B1] = + def orElse[A1 <: A, B1 >: B](that: PartialFunction[A1, B1]): PartialFunction[A1, B1] = new OrElse[A1, B1] (this, that) //TODO: why not overload it with orElse(that: F1): F1? @@ -78,10 +78,8 @@ trait PartialFunction[-A, +B] extends (A => B) { self => * @return a partial function with the same domain as this partial function, which maps * arguments `x` to `k(this(x))`. */ - override def andThen[C](k: B => C) : PartialFunction[A, C] = new PartialFunction[A, C] { - def isDefinedAt(x: A): Boolean = self isDefinedAt x - def apply(x: A): C = k(self(x)) - } + override def andThen[C](k: B => C): PartialFunction[A, C] = + new AndThen[A, B, C] (this, k) /** Turns this partial function into an plain function returning an `Option` result. * @see Function.unlift @@ -90,28 +88,54 @@ trait PartialFunction[-A, +B] extends (A => B) { self => */ def lift: A => Option[B] = new Lifted(this) - /** - * TODO: comment + /** Applies this partial function to the given argument when it is contained in the function domain. + * Applies fallback function where this partial function is not defined. + * + * Note that expression `pf.applyOrElse(x, default)` is equivalent to + * {{{ if(pf isDefinedAt x) pf(x) else default(x) }}} + * except that `applyOrElse` method can be implemented more efficiently. + * For all partial function literals compiler generates `applyOrElse` implementation which + * avoids double evaluation of pattern matchers and guards. + * This makes `applyOrElse` the basis for the efficient implementation for many operations and scenarios, such as: + * + * - combining partial functions into `orElse`/`andThen` chains does not lead to + * excessive `apply`/`isDefinedAt` evaluation + * - `lift` and `unlift` do not evaluate source functions twice on each invocation + * - `runWith` allows efficient imperative-style combining of partial functions + * with conditionally applied actions + * + * For non-literal partial function classes with nontrivial `isDefinedAt` method + * it is recommended to override `applyOrElse` with custom implementation that avoids + * double `isDefinedAt` evaluation. This may result in better performance + * and more predictable behavior w.r.t. side effects. + * + * @param x the function argument + * @param default the fallback function + * @return the result of this function or fallback function application. * @since 2.10 */ def applyOrElse[A1 <: A, B1 >: B](x: A1, default: A1 => B1): B1 = if (isDefinedAt(x)) apply(x) else default(x) - /** - * TODO: comment - * @since 2.10 - */ - def run[U](x: A)(action: B => U): Boolean = - applyOrElse(x, fallbackToken) match { - case FallbackToken => false - case z => action(z); true - } - - /** - * TODO: comment + /** Composes this partial function with an action function which + * gets applied to results of this partial function. + * The action function is invoked only for its side effects; its result is ignored. + * + * Note that expression `pf.runWith(action)(x)` is equivalent to + * {{{ if(pf isDefinedAt x) { action(pf(x)); true } else false }}} + * except that `runWith` is implemented via `applyOrElse` and thus potentially more efficient. + * Using `runWith` avoids double evaluation of pattern matchers and guards for partial function literals. + * @see `applyOrElse`. + * + * @param action the action function + * @return a function which maps arguments `x` to `isDefinedAt(x)`. The resulting function + * runs `action(this(x))` where `this` is defined. * @since 2.10 */ - def runWith[U](action: B => U): A => Boolean = { x => run(x)(action) } + def runWith[U](action: B => U): A => Boolean = { x => + val z = applyOrElse(x, checkFallback[B]) + if (!fallbackOccurred(z)) { action(z); true } else false + } } /** A few handy operations which leverage the extra bit of information @@ -137,11 +161,10 @@ object PartialFunction { def apply(x: A): B = f1.applyOrElse(x, f2) - override def applyOrElse[A1 <: A, B1 >: B](x: A1, default: A1 => B1): B1 = - f1.applyOrElse(x, fallbackToken) match { - case FallbackToken => f2.applyOrElse(x, default) - case z => z - } + override def applyOrElse[A1 <: A, B1 >: B](x: A1, default: A1 => B1): B1 = { + val z = f1.applyOrElse(x, checkFallback[B]) + if (!fallbackOccurred(z)) z else f2.applyOrElse(x, default) + } override def orElse[A1 <: A, B1 >: B](that: PartialFunction[A1, B1]) = new OrElse[A1, B1] (f1, f2 orElse that) @@ -150,23 +173,40 @@ object PartialFunction { new OrElse[A, C] (f1 andThen k, f2 andThen k) } - private[scala] lazy val FallbackToken: PartialFunction[Any, PartialFunction[Any, Nothing]] = { case _ => FallbackToken.asInstanceOf[PartialFunction[Any, Nothing]] } - private[scala] final def fallbackToken[B] = FallbackToken.asInstanceOf[PartialFunction[Any, B]] - //TODO: check generated code for PF literal here + /** Composite function produced by `PartialFunction#andThen` method + */ + private final class AndThen[-A, B, +C] (pf: PartialFunction[A, B], k: B => C) extends PartialFunction[A, C] { + def isDefinedAt(x: A) = pf.isDefinedAt(x) + + def apply(x: A): C = k(pf(x)) - private[scala] final class Lifted[-A, +B] (val pf: PartialFunction[A, B]) + override def applyOrElse[A1 <: A, C1 >: C](x: A1, default: A1 => C1): C1 = { + val z = pf.applyOrElse(x, checkFallback[B]) + if (!fallbackOccurred(z)) k(z) else default(x) + } + } + + private[this] final val fallback_pf: PartialFunction[Any, Any] = { case _ => fallback_pf } + @inline private final def checkFallback[B] = fallback_pf.asInstanceOf[PartialFunction[Any, B]] + @inline private final def fallbackOccurred[B](x: B) = (fallback_pf eq x.asInstanceOf[AnyRef]) + + private final class Lifted[-A, +B] (val pf: PartialFunction[A, B]) extends runtime.AbstractFunction1[A, Option[B]] { - def apply(x: A): Option[B] = pf.applyOrElse(x, fallbackToken) match { - case FallbackToken => None - case z => Some(z) + def apply(x: A): Option[B] = { + val z = pf.applyOrElse(x, checkFallback[B]) + if (!fallbackOccurred(z)) Some(z) else None } } private final class Unlifted[A, B] (f: A => Option[B]) extends runtime.AbstractPartialFunction[A, B] { def isDefinedAt(x: A): Boolean = f(x).isDefined - override def applyOrElse[A1 <: A, B1 >: B](x: A1, default: A1 => B1): B1 = - f(x) getOrElse default(x) //TODO: check generated code and inline getOrElse if needed + + override def applyOrElse[A1 <: A, B1 >: B](x: A1, default: A1 => B1): B1 = { + val z = f(x) + if (!z.isEmpty) z.get else default(x) + } + override def lift = f } @@ -178,7 +218,6 @@ object PartialFunction { /** Converts ordinary function to partial one * @since 2.10 */ - //TODO: check generated code for PF literal here def apply[A, B](f: A => B): PartialFunction[A, B] = { case x => f(x) } private[this] final val constFalse: Any => Boolean = { _ => false} @@ -189,12 +228,11 @@ object PartialFunction { override def orElse[A1, B1](that: PartialFunction[A1, B1]) = that override def andThen[C](k: Nothing => C) = this override val lift = (x: Any) => None - override def run[U](x: Any)(action: Nothing => U) = false override def runWith[U](action: Nothing => U) = constFalse } - /** - * TODO: comment + /** The partial function with empty domain. + * Any attempt to invoke empty partial function leads to throwing [[scala.MatchError]] exception. * @since 2.10 */ def empty[A, B] : PartialFunction[A, B] = empty_pf diff --git a/src/library/scala/runtime/AbstractPartialFunction.scala b/src/library/scala/runtime/AbstractPartialFunction.scala index f499350ce9..c1f245590b 100644 --- a/src/library/scala/runtime/AbstractPartialFunction.scala +++ b/src/library/scala/runtime/AbstractPartialFunction.scala @@ -8,7 +8,8 @@ package scala.runtime -/** `AbstractPartialFunction` reformulates all operations of its supertrait `PartialFunction` in terms of `isDefinedAt` and `applyOrElse`. +/** `AbstractPartialFunction` reformulates all operations of its supertrait `PartialFunction` + * in terms of `isDefinedAt` and `applyOrElse`. * * This allows more efficient implementations in many cases: * - optimized `orElse` method supports chained `orElse` in linear time, @@ -16,12 +17,7 @@ package scala.runtime * - optimized `lift` method helps to avoid double evaluation of pattern matchers & guards * of partial function literals. * - * This trait is used as a basis for implementation of all partial function literals - * with non-exhaustive matchers. - * - * Use of `AbstractPartialFunction` instead of `PartialFunction` as a base trait for - * user-defined partial functions may result in better performance - * and more predictable behavior w.r.t. side effects. + * This trait is used as a basis for implementation of all partial function literals. * * @author Pavel Pavlov * @since 2.10 @@ -35,34 +31,4 @@ abstract class AbstractPartialFunction[@specialized(scala.Int, scala.Long, scala // probably okay to make final since classes compiled before have overridden against the old version of AbstractPartialFunction // let's not make it final so as not to confuse anyone /*final*/ def apply(x: T1): R = applyOrElse(x, PartialFunction.empty) - - @annotation.unspecialized override final def andThen[C](k: R => C) : PartialFunction[T1, C] = - new AbstractPartialFunction[T1, C] { - def isDefinedAt(x: T1): Boolean = self.isDefinedAt(x) - override def applyOrElse[A1 <: T1, C1 >: C](x: A1, default: A1 => C1): C1 = - self.applyOrElse(x, PartialFunction.fallbackToken) match { - case PartialFunction.FallbackToken => default(x) - case z => k(z) - } - } - - // TODO: remove - protected def missingCase(x: T1): R = throw new MatchError(x) -} - - -/** `AbstractTotalFunction` is a partial function whose `isDefinedAt` method always returns `true`. - * - * This class is used as base class for partial function literals with - * certainly exhaustive pattern matchers. - * - * @author Pavel Pavlov - * @since 2.10 - */ -abstract class AbstractTotalFunction[@specialized(scala.Int, scala.Long, scala.Float, scala.Double, scala.AnyRef) -T1, @specialized(scala.Unit, scala.Boolean, scala.Int, scala.Float, scala.Long, scala.Double, scala.AnyRef) +R] extends Function1[T1, R] with PartialFunction[T1, R] { - final def isDefinedAt(x: T1): Boolean = true - @annotation.unspecialized override final def applyOrElse[A1 <: T1, B1 >: R](x: A1, default: A1 => B1): B1 = apply(x) - @annotation.unspecialized override final def orElse[A1 <: T1, B1 >: R](that: PartialFunction[A1, B1]): PartialFunction[A1, B1] = this - //TODO: check generated code for PF literal here - @annotation.unspecialized override final def andThen[C](k: R => C): PartialFunction[T1, C] = { case x => k(apply(x)) } } diff --git a/test/files/run/partialfun.check b/test/files/run/partialfun.check new file mode 100644 index 0000000000..a317f7b150 --- /dev/null +++ b/test/files/run/partialfun.check @@ -0,0 +1,6 @@ +47 +147 +100 +0:isDefinedAt +1:isDefinedAt +2:apply diff --git a/test/files/run/partialfun.scala b/test/files/run/partialfun.scala new file mode 100644 index 0000000000..4b360750c9 --- /dev/null +++ b/test/files/run/partialfun.scala @@ -0,0 +1,86 @@ +import collection._ +import collection.generic._ + +object Test { + def collectIDA[A, B, Repr, That](_this: TraversableLike[A, Repr])(pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Repr, B, That]): That = { + val repr: Repr = _this.asInstanceOf[Repr] + val b = bf(repr) + _this foreach { x => if (pf isDefinedAt x) b += pf(x) } + b.result + } + + def collectRW[A, B, Repr, That](_this: TraversableLike[A, Repr])(pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Repr, B, That]): That = { + val repr: Repr = _this.asInstanceOf[Repr] + val b = bf(repr) + val f = pf runWith { b += _ } + _this foreach f + b.result + } + + var cnt = 0 + + object Ex1 { + def unapply(x: Int) : Option[Int] = { + cnt += 1 + if ((x % 3) == 0) Some(-x) else None + } + } + + object Ex2 { + def unapply(x: Int) : Option[Int] = { + //cnt += 1 + if ((x % 5) == 0) Some(x) else None + } + } + + def resetCnt() = { val r = cnt; cnt = 0; r } + + val pf: PartialFunction[Int,Int] = { + case Ex1(result) => result + case Ex2(result) => result + } + + def collectTest() { + val xs = 1 to 100 + resetCnt() + + val ysIDA = collectIDA(xs)(pf) + val cntIDA = resetCnt() + + val ysRW = collectRW(xs)(pf) + val cntRW = resetCnt() + + val ys = xs collect pf + + assert(ys == ysIDA) + assert(ys == ysRW) + assert(cntIDA == xs.length + ys.length) + assert(cntRW == xs.length) + println(ys.length) + println(cntIDA) + println(cntRW) + } + + def orElseTest() { + val pf0 = new PartialFunction[Unit, Unit] { + def apply(u: Unit) { println("0:apply") } + def isDefinedAt(u: Unit) = { println("0:isDefinedAt"); false } + } + val pf1 = new PartialFunction[Unit, Unit] { + def apply(u: Unit) { println("1:apply") } + def isDefinedAt(u: Unit) = { println("1:isDefinedAt"); false } + } + val pf2 = new PartialFunction[Unit, Unit] { + def apply(u: Unit) { println("2:apply") } + def isDefinedAt(u: Unit) = { println("2:isDefinedAt"); true } + } + + val chained = pf0 orElse pf1 orElse pf2 + chained() + } + + def main(args: Array[String]): Unit = { + collectTest() + orElseTest() + } +} -- cgit v1.2.3 From b8136ad5b2d9950006e4a440e4a73bbbec553169 Mon Sep 17 00:00:00 2001 From: pavelpavlov Date: Thu, 23 Aug 2012 20:31:30 +0400 Subject: pull request feedback Added note about role of `fallback_pf` in the implementation --- src/library/scala/PartialFunction.scala | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) diff --git a/src/library/scala/PartialFunction.scala b/src/library/scala/PartialFunction.scala index 91eae2984a..d0a339bdd5 100644 --- a/src/library/scala/PartialFunction.scala +++ b/src/library/scala/PartialFunction.scala @@ -186,6 +186,27 @@ object PartialFunction { } } + /** To implement patterns like {{{ if(pf isDefinedAt x) f1(pf(x)) else f2(x) }}} efficiently + * the following trick is used: + * + * To avoid double evaluation of pattern matchers & guards `applyOrElse` method is used here + * instead of `isDefinedAt`/`apply` pair. + * + * After call to `applyOrElse` we need both the function result it returned and + * the fact if the function's argument was contained in its domain. The only degree of freedom we have here + * to achieve this goal is tweaking with the continuation argument (`default`) of `applyOrElse` method. + * The obvious way is to throw an exception from `default` function and to catch it after + * calling `applyOrElse` but I consider this somewhat inefficient. + * + * I know only one way how you can do this task efficiently: `default` function should return unique marker object + * which never may be returned by any other (regular/partial) function. This way after calling `applyOrElse` you need + * just one reference comparison to distinguish if `pf isDefined x` or not. + * + * This correctly interacts with specialization as return type of `applyOrElse` + * (which is parameterized upper bound) can never be specialized. + * + * Here `fallback_pf` is used as both unique marker object and special fallback function that returns it. + */ private[this] final val fallback_pf: PartialFunction[Any, Any] = { case _ => fallback_pf } @inline private final def checkFallback[B] = fallback_pf.asInstanceOf[PartialFunction[Any, B]] @inline private final def fallbackOccurred[B](x: B) = (fallback_pf eq x.asInstanceOf[AnyRef]) -- cgit v1.2.3