diff options
40 files changed, 1516 insertions, 191 deletions
diff --git a/compiler/src/dotty/tools/backend/jvm/DottyBackendInterface.scala b/compiler/src/dotty/tools/backend/jvm/DottyBackendInterface.scala index 123dc3450..c17a32744 100644 --- a/compiler/src/dotty/tools/backend/jvm/DottyBackendInterface.scala +++ b/compiler/src/dotty/tools/backend/jvm/DottyBackendInterface.scala @@ -39,6 +39,10 @@ import dotty.tools.dotc.core.Names.TypeName import scala.annotation.tailrec class DottyBackendInterface(outputDirectory: AbstractFile, val superCallsMap: Map[Symbol, Set[ClassSymbol]])(implicit ctx: Context) extends BackendInterface{ + import Symbols.{toDenot, toClassDenot} + // Dotty deviation: Need to (re-)import implicit decorators here because otherwise + // they would be shadowed by the more deeply nested `symHelper` decorator. + type Symbol = Symbols.Symbol type Type = Types.Type type Tree = tpd.Tree @@ -683,8 +687,6 @@ class DottyBackendInterface(outputDirectory: AbstractFile, val superCallsMap: Ma else sym.enclosingClass(ctx.withPhase(ctx.flattenPhase.prev)) } //todo is handled specially for JavaDefined symbols in scalac - - // members def primaryConstructor: Symbol = toDenot(sym).primaryConstructor diff --git a/compiler/src/dotty/tools/dotc/Compiler.scala b/compiler/src/dotty/tools/dotc/Compiler.scala index ad3249be2..900d2b0e3 100644 --- a/compiler/src/dotty/tools/dotc/Compiler.scala +++ b/compiler/src/dotty/tools/dotc/Compiler.scala @@ -61,6 +61,7 @@ class Compiler { new PatternMatcher, // Compile pattern matches new ExplicitOuter, // Add accessors to outer classes from nested ones. new ExplicitSelf, // Make references to non-trivial self types explicit as casts + new ShortcutImplicits, // Allow implicit functions without creating closures new CrossCastAnd, // Normalize selections involving intersection types. new Splitter), // Expand selections involving union types into conditionals List(new VCInlineMethods, // Inlines calls to value class methods diff --git a/compiler/src/dotty/tools/dotc/ast/Desugar.scala b/compiler/src/dotty/tools/dotc/ast/Desugar.scala index bb15edf5a..db78cfffb 100644 --- a/compiler/src/dotty/tools/dotc/ast/Desugar.scala +++ b/compiler/src/dotty/tools/dotc/ast/Desugar.scala @@ -123,6 +123,13 @@ object desugar { else vdef } + def makeImplicitParameters(tpts: List[Tree], forPrimaryConstructor: Boolean)(implicit ctx: Context) = + for (tpt <- tpts) yield { + val paramFlags: FlagSet = if (forPrimaryConstructor) PrivateLocalParamAccessor else Param + val epname = ctx.freshName(nme.EVIDENCE_PARAM_PREFIX).toTermName + ValDef(epname, tpt, EmptyTree).withFlags(paramFlags | Implicit) + } + /** Expand context bounds to evidence params. E.g., * * def f[T >: L <: H : B](params) @@ -143,19 +150,16 @@ object desugar { val epbuf = new ListBuffer[ValDef] def desugarContextBounds(rhs: Tree): Tree = rhs match { case ContextBounds(tbounds, cxbounds) => - for (cxbound <- cxbounds) { - val paramFlags: FlagSet = if (isPrimaryConstructor) PrivateLocalParamAccessor else Param - val epname = ctx.freshName(nme.EVIDENCE_PARAM_PREFIX).toTermName - epbuf += ValDef(epname, cxbound, EmptyTree).withFlags(paramFlags | Implicit) - } + for (cxbound <- cxbounds) + epbuf ++= makeImplicitParameters(cxbounds, isPrimaryConstructor) tbounds case PolyTypeTree(tparams, body) => cpy.PolyTypeTree(rhs)(tparams, desugarContextBounds(body)) case _ => rhs } - val tparams1 = tparams mapConserve { tdef => - cpy.TypeDef(tdef)(rhs = desugarContextBounds(tdef.rhs)) + val tparams1 = tparams mapConserve { tparam => + cpy.TypeDef(tparam)(rhs = desugarContextBounds(tparam.rhs)) } val meth1 = addEvidenceParams(cpy.DefDef(meth)(tparams = tparams1), epbuf.toList) @@ -680,6 +684,11 @@ object desugar { Function(param :: Nil, Block(vdefs, body)) } + def makeImplicitFunction(formals: List[Type], body: Tree)(implicit ctx: Context): Tree = { + val params = makeImplicitParameters(formals.map(TypeTree), forPrimaryConstructor = false) + new ImplicitFunction(params, body) + } + /** Add annotation with class `cls` to tree: * tree @cls */ diff --git a/compiler/src/dotty/tools/dotc/ast/TreeInfo.scala b/compiler/src/dotty/tools/dotc/ast/TreeInfo.scala index d1e6bd38a..da83d0644 100644 --- a/compiler/src/dotty/tools/dotc/ast/TreeInfo.scala +++ b/compiler/src/dotty/tools/dotc/ast/TreeInfo.scala @@ -290,6 +290,16 @@ trait UntypedTreeInfo extends TreeInfo[Untyped] { self: Trees.Instance[Untyped] case _ => false } + /** Is `tree` an implicit function or closure, possibly nested in a block? */ + def isImplicitClosure(tree: Tree)(implicit ctx: Context): Boolean = unsplice(tree) match { + case Function((param: untpd.ValDef) :: _, _) => param.mods.is(Implicit) + case Closure(_, meth, _) => true + case Block(Nil, expr) => isImplicitClosure(expr) + case Block(DefDef(nme.ANON_FUN, _, (param :: _) :: _, _, _) :: Nil, _: Closure) => + param.mods.is(Implicit) + case _ => false + } + // todo: fill with other methods from TreeInfo that only apply to untpd.Tree's } @@ -501,7 +511,7 @@ trait TypedTreeInfo extends TreeInfo[Type] { self: Trees.Instance[Type] => */ object closure { def unapply(tree: Tree): Option[(List[Tree], Tree, Tree)] = tree match { - case Block(_, Closure(env, meth, tpt)) => Some(env, meth, tpt) + case Block(_, expr) => unapply(expr) case Closure(env, meth, tpt) => Some(env, meth, tpt) case _ => None } diff --git a/compiler/src/dotty/tools/dotc/ast/Trees.scala b/compiler/src/dotty/tools/dotc/ast/Trees.scala index 28ae89c4a..798f0f567 100644 --- a/compiler/src/dotty/tools/dotc/ast/Trees.scala +++ b/compiler/src/dotty/tools/dotc/ast/Trees.scala @@ -890,6 +890,11 @@ object Trees { case tree: Select if (qualifier eq tree.qualifier) && (name == tree.name) => tree case _ => finalize(tree, untpd.Select(qualifier, name)) } + /** Copy Ident or Select trees */ + def Ref(tree: RefTree)(name: Name)(implicit ctx: Context) = tree match { + case Ident(_) => Ident(tree)(name) + case Select(qual, _) => Select(tree)(qual, name) + } def This(tree: Tree)(qual: untpd.Ident): This = tree match { case tree: This if qual eq tree.qual => tree case _ => finalize(tree, untpd.This(qual)) diff --git a/compiler/src/dotty/tools/dotc/ast/tpd.scala b/compiler/src/dotty/tools/dotc/ast/tpd.scala index cd6b3fcf2..433808e8e 100644 --- a/compiler/src/dotty/tools/dotc/ast/tpd.scala +++ b/compiler/src/dotty/tools/dotc/ast/tpd.scala @@ -450,7 +450,8 @@ object tpd extends Trees.Instance[Type] with TypedTreeInfo { } else foldOver(sym, tree) } - override val cpy = new TypedTreeCopier + override val cpy: TypedTreeCopier = // Type ascription needed to pick up any new members in TreeCopier (currently there are none) + new TypedTreeCopier class TypedTreeCopier extends TreeCopier { def postProcess(tree: Tree, copied: untpd.Tree): copied.ThisTree[Type] = diff --git a/compiler/src/dotty/tools/dotc/ast/untpd.scala b/compiler/src/dotty/tools/dotc/ast/untpd.scala index 6c5210287..f3ffce8f8 100644 --- a/compiler/src/dotty/tools/dotc/ast/untpd.scala +++ b/compiler/src/dotty/tools/dotc/ast/untpd.scala @@ -53,6 +53,12 @@ object untpd extends Trees.Instance[Untyped] with UntypedTreeInfo { override def isTerm = body.isTerm override def isType = body.isType } + + /** An implicit function type */ + class ImplicitFunction(args: List[Tree], body: Tree) extends Function(args, body) { + override def toString = s"ImplicitFunction($args, $body)" + } + /** A function created from a wildcard expression * @param placeHolderParams a list of definitions of synthetic parameters * @param body the function body where wildcards are replaced by @@ -111,7 +117,7 @@ object untpd extends Trees.Instance[Untyped] with UntypedTreeInfo { case class Var() extends Mod(Flags.Mutable) - case class Implicit(flag: FlagSet = Flags.ImplicitCommon) extends Mod(flag) + case class Implicit() extends Mod(Flags.ImplicitCommon) case class Final() extends Mod(Flags.Final) @@ -270,8 +276,6 @@ object untpd extends Trees.Instance[Untyped] with UntypedTreeInfo { // ------ Additional creation methods for untyped only ----------------- - // def TypeTree(tpe: Type): TypeTree = TypeTree().withType(tpe) todo: move to untpd/tpd - /** new pre.C[Ts](args1)...(args_n) * ==> * (new pre.C).<init>[Ts](args1)...(args_n) diff --git a/compiler/src/dotty/tools/dotc/config/JavaPlatform.scala b/compiler/src/dotty/tools/dotc/config/JavaPlatform.scala index a695202d3..b5bfbb39f 100644 --- a/compiler/src/dotty/tools/dotc/config/JavaPlatform.scala +++ b/compiler/src/dotty/tools/dotc/config/JavaPlatform.scala @@ -18,6 +18,7 @@ class JavaPlatform extends Platform { currentClassPath = Some(new PathResolver().result) val cp = currentClassPath.get //println(cp) + //println("------------------") cp } diff --git a/compiler/src/dotty/tools/dotc/core/Comments.scala b/compiler/src/dotty/tools/dotc/core/Comments.scala index 1e623db4d..2559209c3 100644 --- a/compiler/src/dotty/tools/dotc/core/Comments.scala +++ b/compiler/src/dotty/tools/dotc/core/Comments.scala @@ -119,7 +119,7 @@ object Comments { def apply(comment: Comment, code: String, codePos: Position)(implicit ctx: Context) = new UseCase(comment, code, codePos) { val untpdCode = { - val tree = new Parser(new SourceFile("<usecase>", code)).localDef(codePos.start, EmptyFlags) + val tree = new Parser(new SourceFile("<usecase>", code)).localDef(codePos.start) tree match { case tree: untpd.DefDef => diff --git a/compiler/src/dotty/tools/dotc/core/Definitions.scala b/compiler/src/dotty/tools/dotc/core/Definitions.scala index 3f1f3e294..45e37eb8b 100644 --- a/compiler/src/dotty/tools/dotc/core/Definitions.scala +++ b/compiler/src/dotty/tools/dotc/core/Definitions.scala @@ -86,24 +86,51 @@ class Definitions { newClassSymbol(ScalaPackageClass, name, EmptyFlags, completer).entered } - /** The trait FunctionN, for some N */ - private def newFunctionNTrait(n: Int) = { + /** The trait FunctionN or ImplicitFunctionN, for some N + * @param name The name of the trait to be created + * + * FunctionN traits follow this template: + * + * trait FunctionN[T0,...T{N-1}, R] extends Object { + * def apply($x0: T0, ..., $x{N_1}: T{N-1}): R + * } + * + * That is, they follow the template given for Function2..Function22 in the + * standard library, but without `tupled` and `curried` methods and without + * a `toString`. + * + * ImplicitFunctionN traits follow this template: + * + * trait ImplicitFunctionN[T0,...,T{N-1}, R] extends Object with FunctionN[T0,...,T{N-1}, R] { + * def apply(implicit $x0: T0, ..., $x{N_1}: T{N-1}): R + * } + */ + private def newFunctionNTrait(name: TypeName) = { val completer = new LazyType { def complete(denot: SymDenotation)(implicit ctx: Context): Unit = { val cls = denot.asClass.classSymbol val decls = newScope + val arity = name.functionArity val argParams = - for (i <- List.range(0, n)) yield - enterTypeParam(cls, s"T$i".toTypeName, Contravariant, decls) - val resParam = enterTypeParam(cls, s"R".toTypeName, Covariant, decls) + for (i <- List.range(0, arity)) yield + enterTypeParam(cls, name ++ "$T" ++ i.toString, Contravariant, decls) + val resParam = enterTypeParam(cls, name ++ "$R", Covariant, decls) + val (methodType, parentTraits) = + if (name.startsWith(tpnme.ImplicitFunction)) { + val superTrait = + FunctionType(arity).appliedTo(argParams.map(_.typeRef) ::: resParam.typeRef :: Nil) + (ImplicitMethodType, ctx.normalizeToClassRefs(superTrait :: Nil, cls, decls)) + } + else (MethodType, Nil) val applyMeth = decls.enter( newMethod(cls, nme.apply, - MethodType(argParams.map(_.typeRef), resParam.typeRef), Deferred)) - denot.info = ClassInfo(ScalaPackageClass.thisType, cls, ObjectType :: Nil, decls) + methodType(argParams.map(_.typeRef), resParam.typeRef), Deferred)) + denot.info = + ClassInfo(ScalaPackageClass.thisType, cls, ObjectType :: parentTraits, decls) } } - newClassSymbol(ScalaPackageClass, s"Function$n".toTypeName, Trait, completer) + newClassSymbol(ScalaPackageClass, name, Trait, completer) } private def newMethod(cls: ClassSymbol, name: TermName, info: Type, flags: FlagSet = EmptyFlags): TermSymbol = @@ -590,15 +617,16 @@ class Definitions { sym.owner.linkedClass.typeRef object FunctionOf { - def apply(args: List[Type], resultType: Type)(implicit ctx: Context) = - FunctionType(args.length).appliedTo(args ::: resultType :: Nil) + def apply(args: List[Type], resultType: Type, isImplicit: Boolean = false)(implicit ctx: Context) = + FunctionType(args.length, isImplicit).appliedTo(args ::: resultType :: Nil) def unapply(ft: Type)(implicit ctx: Context) = { val tsym = ft.typeSymbol - if (isFunctionClass(tsym)) { - lazy val targs = ft.argInfos + val isImplicitFun = isImplicitFunctionClass(tsym) + if (isImplicitFun || isFunctionClass(tsym)) { + val targs = ft.argInfos val numArgs = targs.length - 1 - if (numArgs >= 0 && FunctionType(numArgs).symbol == tsym) - Some(targs.init, targs.last) + if (numArgs >= 0 && FunctionType(numArgs, isImplicitFun).symbol == tsym) + Some(targs.init, targs.last, isImplicitFun) else None } else None @@ -659,8 +687,12 @@ class Definitions { lazy val Function0_applyR = ImplementedFunctionType(0).symbol.requiredMethodRef(nme.apply) def Function0_apply(implicit ctx: Context) = Function0_applyR.symbol - def FunctionType(n: Int)(implicit ctx: Context): TypeRef = - if (n < MaxImplementedFunctionArity) ImplementedFunctionType(n) + def ImplicitFunctionClass(n: Int)(implicit ctx: Context) = + ctx.requiredClass("scala.ImplicitFunction" + n.toString) + + def FunctionType(n: Int, isImplicit: Boolean = false)(implicit ctx: Context): TypeRef = + if (isImplicit && !ctx.erasedTypes) ImplicitFunctionClass(n).typeRef + else if (n < MaxImplementedFunctionArity) ImplementedFunctionType(n) else FunctionClass(n).typeRef private lazy val TupleTypes: Set[TypeRef] = TupleType.toSet @@ -686,6 +718,7 @@ class Definitions { tp.derivesFrom(NothingClass) || tp.derivesFrom(NullClass) def isFunctionClass(cls: Symbol) = isVarArityClass(cls, tpnme.Function) + def isImplicitFunctionClass(cls: Symbol) = isVarArityClass(cls, tpnme.ImplicitFunction) def isUnimplementedFunctionClass(cls: Symbol) = isFunctionClass(cls) && cls.name.functionArity > MaxImplementedFunctionArity def isAbstractFunctionClass(cls: Symbol) = isVarArityClass(cls, tpnme.AbstractFunction) @@ -745,14 +778,21 @@ class Definitions { } else -1 - def isFunctionType(tp: Type)(implicit ctx: Context) = - isFunctionClass(tp.dealias.typeSymbol) && { - val arity = functionArity(tp) - arity >= 0 && tp.isRef(FunctionType(functionArity(tp)).typeSymbol) - } + /** Is `tp` (an alias) of either a scala.FunctionN or a scala.ImplicitFunctionN ? */ + def isFunctionType(tp: Type)(implicit ctx: Context) = { + val arity = functionArity(tp) + val sym = tp.dealias.typeSymbol + arity >= 0 && ( + isFunctionClass(sym) && tp.isRef(FunctionType(arity, isImplicit = false).typeSymbol) || + isImplicitFunctionClass(sym) && tp.isRef(FunctionType(arity, isImplicit = true).typeSymbol) + ) + } def functionArity(tp: Type)(implicit ctx: Context) = tp.dealias.argInfos.length - 1 + def isImplicitFunctionType(tp: Type)(implicit ctx: Context) = + isFunctionType(tp) && tp.dealias.typeSymbol.name.startsWith(tpnme.ImplicitFunction) + // ----- primitive value class machinery ------------------------------------------ /** This class would also be obviated by the implicit function type design */ @@ -825,6 +865,9 @@ class Definitions { // ----- Initialization --------------------------------------------------- + private def maxImplemented(name: Name) = + if (name `startsWith` tpnme.Function) MaxImplementedFunctionArity else 0 + /** Give the scala package a scope where a FunctionN trait is automatically * added when someone looks for it. */ @@ -834,8 +877,8 @@ class Definitions { val newDecls = new MutableScope(oldDecls) { override def lookupEntry(name: Name)(implicit ctx: Context): ScopeEntry = { val res = super.lookupEntry(name) - if (res == null && name.functionArity > MaxImplementedFunctionArity) - newScopeEntry(newFunctionNTrait(name.functionArity)) + if (res == null && name.isTypeName && name.functionArity > maxImplemented(name)) + newScopeEntry(newFunctionNTrait(name.asTypeName)) else res } } diff --git a/compiler/src/dotty/tools/dotc/core/NameOps.scala b/compiler/src/dotty/tools/dotc/core/NameOps.scala index 7a4fc0512..c037d1ce7 100644 --- a/compiler/src/dotty/tools/dotc/core/NameOps.scala +++ b/compiler/src/dotty/tools/dotc/core/NameOps.scala @@ -188,6 +188,8 @@ object NameOps { def errorName: N = likeTyped(name ++ nme.ERROR) + def directName: N = likeTyped(name ++ DIRECT_SUFFIX) + def freshened(implicit ctx: Context): N = likeTyped( if (name.isModuleClassName) name.stripModuleClassSuffix.freshened.moduleClassName @@ -229,11 +231,14 @@ object NameOps { } } - def functionArity: Int = - if (name.startsWith(tpnme.Function)) - try name.drop(tpnme.Function.length).toString.toInt - catch { case ex: NumberFormatException => -1 } - else -1 + def functionArity: Int = { + def test(prefix: Name): Int = + if (name.startsWith(prefix)) + try name.drop(prefix.length).toString.toInt + catch { case ex: NumberFormatException => -1 } + else -1 + test(tpnme.Function) max test(tpnme.ImplicitFunction) + } /** The name of the generic runtime operation corresponding to an array operation */ def genericArrayOp: TermName = name match { diff --git a/compiler/src/dotty/tools/dotc/core/StdNames.scala b/compiler/src/dotty/tools/dotc/core/StdNames.scala index e71893c1e..716959648 100644 --- a/compiler/src/dotty/tools/dotc/core/StdNames.scala +++ b/compiler/src/dotty/tools/dotc/core/StdNames.scala @@ -129,6 +129,7 @@ object StdNames { val COMPANION_MODULE_METHOD: N = "companion$module" val COMPANION_CLASS_METHOD: N = "companion$class" val TRAIT_SETTER_SEPARATOR: N = "$_setter_$" + val DIRECT_SUFFIX: N = "$direct" // value types (and AnyRef) are all used as terms as well // as (at least) arguments to the @specialize annotation. @@ -181,6 +182,7 @@ object StdNames { final val AnyVal: N = "AnyVal" final val ExprApi: N = "ExprApi" final val Function: N = "Function" + final val ImplicitFunction: N = "ImplicitFunction" final val Mirror: N = "Mirror" final val Nothing: N = "Nothing" final val Null: N = "Null" diff --git a/compiler/src/dotty/tools/dotc/core/Symbols.scala b/compiler/src/dotty/tools/dotc/core/Symbols.scala index b10b94ad8..d355686ab 100644 --- a/compiler/src/dotty/tools/dotc/core/Symbols.scala +++ b/compiler/src/dotty/tools/dotc/core/Symbols.scala @@ -393,6 +393,10 @@ object Symbols { denot } + /** The initial denotation of this symbol, without going through `current` */ + final def initialDenot(implicit ctx: Context): SymDenotation = + lastDenot.initial + private[core] def defRunId: RunId = if (lastDenot == null) NoRunId else lastDenot.validFor.runId diff --git a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala index e8905320b..334306f19 100644 --- a/compiler/src/dotty/tools/dotc/core/TypeComparer.scala +++ b/compiler/src/dotty/tools/dotc/core/TypeComparer.scala @@ -478,7 +478,7 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case tp1 @ MethodType(_, formals1) => (tp1.signature consistentParams tp2.signature) && matchingParams(formals1, formals2, tp1.isJava, tp2.isJava) && - tp1.isImplicit == tp2.isImplicit && // needed? + (!tp1.isImplicit || tp2.isImplicit) && // non-implicit functions shadow implicit ones isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1)) case _ => false @@ -1003,9 +1003,9 @@ class TypeComparer(initctx: Context) extends DotClass with ConstraintHandling { case tp1: MethodType => tp2.widen match { case tp2: MethodType => - tp1.isImplicit == tp2.isImplicit && - matchingParams(tp1.paramTypes, tp2.paramTypes, tp1.isJava, tp2.isJava) && - matchesType(tp1.resultType, tp2.resultType.subst(tp2, tp1), relaxed) + // implicitness is ignored when matching + matchingParams(tp1.paramTypes, tp2.paramTypes, tp1.isJava, tp2.isJava) && + matchesType(tp1.resultType, tp2.resultType.subst(tp2, tp1), relaxed) case tp2 => relaxed && tp1.paramNames.isEmpty && matchesType(tp1.resultType, tp2, relaxed) diff --git a/compiler/src/dotty/tools/dotc/core/TypeErasure.scala b/compiler/src/dotty/tools/dotc/core/TypeErasure.scala index 2e7c1db04..91e37d440 100644 --- a/compiler/src/dotty/tools/dotc/core/TypeErasure.scala +++ b/compiler/src/dotty/tools/dotc/core/TypeErasure.scala @@ -2,7 +2,9 @@ package dotty.tools package dotc package core -import Symbols._, Types._, Contexts._, Flags._, Names._, StdNames._, Decorators._, Flags.JavaDefined +import Symbols._, Types._, Contexts._, Flags._, Names._, StdNames._, Decorators._ +import Flags.JavaDefined +import NameOps._ import Uniques.unique import dotc.transform.ExplicitOuter._ import dotc.transform.ValueClasses._ @@ -42,7 +44,7 @@ object TypeErasure { val sym = tp.symbol sym.isClass && sym != defn.AnyClass && sym != defn.ArrayClass && - !defn.isUnimplementedFunctionClass(sym) + !defn.isUnimplementedFunctionClass(sym) && !defn.isImplicitFunctionClass(sym) case _: TermRef => true case JavaArrayType(elem) => @@ -327,6 +329,7 @@ class TypeErasure(isJava: Boolean, semiEraseVCs: Boolean, isConstructor: Boolean * - For a typeref scala.Any, scala.AnyVal or scala.Singleton: |java.lang.Object| * - For a typeref scala.Unit, |scala.runtime.BoxedUnit|. * - For a typeref scala.FunctionN, where N > MaxImplementedFunctionArity, scala.FunctionXXL + * - For a typeref scala.ImplicitFunctionN, | scala.FunctionN | * - For a typeref P.C where C refers to a class, <noprefix> # C. * - For a typeref P.C where C refers to an alias type, the erasure of C's alias. * - For a typeref P.C where C refers to an abstract type, the erasure of C's upper bound. @@ -356,6 +359,7 @@ class TypeErasure(isJava: Boolean, semiEraseVCs: Boolean, isConstructor: Boolean else if (semiEraseVCs && isDerivedValueClass(sym)) eraseDerivedValueClassRef(tp) else if (sym == defn.ArrayClass) apply(tp.appliedTo(TypeBounds.empty)) // i966 shows that we can hit a raw Array type. else if (defn.isUnimplementedFunctionClass(sym)) defn.FunctionXXLType + else if (defn.isImplicitFunctionClass(sym)) apply(defn.FunctionType(sym.name.functionArity)) else eraseNormalClassRef(tp) case tp: RefinedType => val parent = tp.parent @@ -492,7 +496,10 @@ class TypeErasure(isJava: Boolean, semiEraseVCs: Boolean, isConstructor: Boolean val erasedVCRef = eraseDerivedValueClassRef(tp) if (erasedVCRef.exists) return sigName(erasedVCRef) } - normalizeClass(sym.asClass).fullName.asTypeName + if (defn.isImplicitFunctionClass(sym)) + sigName(defn.FunctionType(sym.name.functionArity)) + else + normalizeClass(sym.asClass).fullName.asTypeName case defn.ArrayOf(elem) => sigName(this(tp)) case JavaArrayType(elem) => diff --git a/compiler/src/dotty/tools/dotc/core/Types.scala b/compiler/src/dotty/tools/dotc/core/Types.scala index 9884cc70a..93c381c4c 100644 --- a/compiler/src/dotty/tools/dotc/core/Types.scala +++ b/compiler/src/dotty/tools/dotc/core/Types.scala @@ -1211,7 +1211,7 @@ object Types { case mt @ MethodType(_, formals) if !mt.isDependent || ctx.mode.is(Mode.AllowDependentFunctions) => val formals1 = if (dropLast == 0) formals else formals dropRight dropLast defn.FunctionOf( - formals1 mapConserve (_.underlyingIfRepeated(mt.isJava)), mt.resultType) + formals1 mapConserve (_.underlyingIfRepeated(mt.isJava)), mt.resultType, mt.isImplicit && !ctx.erasedTypes) } /** The signature of this type. This is by default NotAMethod, @@ -2377,7 +2377,9 @@ object Types { protected def computeSignature(implicit ctx: Context): Signature = resultSignature.prepend(paramTypes, isJava) - def derivedMethodType(paramNames: List[TermName], paramTypes: List[Type], resType: Type)(implicit ctx: Context) = + def derivedMethodType(paramNames: List[TermName] = this.paramNames, + paramTypes: List[Type] = this.paramTypes, + resType: Type = this.resType)(implicit ctx: Context) = if ((paramNames eq this.paramNames) && (paramTypes eq this.paramTypes) && (resType eq this.resType)) this else { val resTypeFn = (x: MethodType) => resType.subst(this, x) diff --git a/compiler/src/dotty/tools/dotc/parsing/Parsers.scala b/compiler/src/dotty/tools/dotc/parsing/Parsers.scala index 704f399ca..26656aae8 100644 --- a/compiler/src/dotty/tools/dotc/parsing/Parsers.scala +++ b/compiler/src/dotty/tools/dotc/parsing/Parsers.scala @@ -146,6 +146,7 @@ object Parsers { def isNumericLit = numericLitTokens contains in.token def isModifier = modifierTokens contains in.token def isExprIntro = canStartExpressionTokens contains in.token + def isBindingIntro = canStartBindingTokens contains in.token def isTemplateIntro = templateIntroTokens contains in.token def isDclIntro = dclIntroTokens contains in.token def isStatSeqEnd = in.token == RBRACE || in.token == EOF @@ -681,7 +682,7 @@ object Parsers { } } - /** Type ::= FunArgTypes `=>' Type + /** Type ::= [`implicit'] FunArgTypes `=>' Type * | HkTypeParamClause `->' Type * | InfixType * FunArgTypes ::= InfixType @@ -689,20 +690,26 @@ object Parsers { */ def typ(): Tree = { val start = in.offset + val isImplicit = in.token == IMPLICIT + if (isImplicit) in.nextToken() + def functionRest(params: List[Tree]): Tree = + atPos(start, accept(ARROW)) { + val t = typ() + if (isImplicit) new ImplicitFunction(params, t) else Function(params, t) + } val t = if (in.token == LPAREN) { in.nextToken() if (in.token == RPAREN) { in.nextToken() - atPos(start, accept(ARROW)) { Function(Nil, typ()) } + functionRest(Nil) } else { openParens.change(LPAREN, 1) val ts = commaSeparated(funArgType) openParens.change(LPAREN, -1) accept(RPAREN) - if (in.token == ARROW) - atPos(start, in.skipToken()) { Function(ts, typ()) } + if (isImplicit || in.token == ARROW) functionRest(ts) else { for (t <- ts) if (t.isInstanceOf[ByNameTypeTree]) @@ -722,7 +729,7 @@ object Parsers { else infixType() in.token match { - case ARROW => atPos(start, in.skipToken()) { Function(List(t), typ()) } + case ARROW => functionRest(t :: Nil) case FORSOME => syntaxError("existential types no longer supported; use a wildcard type or dependent type instead"); t case _ => t } @@ -945,14 +952,14 @@ object Parsers { } } - /** Expr ::= FunParams `=>' Expr + /** Expr ::= [`implicit'] FunParams `=>' Expr * | Expr1 * FunParams ::= Bindings - * | [`implicit'] Id + * | Id * | `_' * ExprInParens ::= PostfixExpr `:' Type * | Expr - * BlockResult ::= (FunParams | [`implicit'] Id `:' InfixType) => Block + * BlockResult ::= [`implicit'] FunParams `=>' Block * | Expr1 * Expr1 ::= `if' `(' Expr `)' {nl} Expr [[semi] else Expr] * | `if' Expr `then' Expr [[semi] else Expr] @@ -979,22 +986,27 @@ object Parsers { def expr(): Tree = expr(Location.ElseWhere) def expr(location: Location.Value): Tree = { - val saved = placeholderParams - placeholderParams = Nil - val t = expr1(location) - if (in.token == ARROW) { - placeholderParams = saved - closureRest(startOffset(t), location, convertToParams(t)) - } - else if (isWildcard(t)) { - placeholderParams = placeholderParams ::: saved - t + val start = in.offset + if (in.token == IMPLICIT) + implicitClosure(start, location, implicitMods()) + else { + val saved = placeholderParams + placeholderParams = Nil + val t = expr1(location) + if (in.token == ARROW) { + placeholderParams = saved + closureRest(start, location, convertToParams(t)) + } + else if (isWildcard(t)) { + placeholderParams = placeholderParams ::: saved + t + } + else + try + if (placeholderParams.isEmpty) t + else new WildcardFunction(placeholderParams.reverse, t) + finally placeholderParams = saved } - else - try - if (placeholderParams.isEmpty) t - else new WildcardFunction(placeholderParams.reverse, t) - finally placeholderParams = saved } def expr1(location: Location.Value = Location.ElseWhere): Tree = in.token match { @@ -1060,8 +1072,6 @@ object Parsers { atPos(in.skipToken()) { Return(if (isExprIntro) expr() else EmptyTree, EmptyTree) } case FOR => forExpr() - case IMPLICIT => - implicitClosure(in.skipToken(), location) case _ => expr1Rest(postfixExpr(), location) } @@ -1109,20 +1119,53 @@ object Parsers { } } + /** FunParams ::= Bindings + * | Id + * | `_' + * Bindings ::= `(' [Binding {`,' Binding}] `)' + */ + def funParams(mods: Modifiers, location: Location.Value): List[Tree] = + if (in.token == LPAREN) + inParens(if (in.token == RPAREN) Nil else commaSeparated(() => binding(mods))) + else { + val start = in.offset + val name = bindingName() + val t = + if (in.token == COLON && location == Location.InBlock) { + if (false) // Don't error yet, as the alternative syntax "implicit (x: T) => ... " + // is not supported by Scala2.x + migrationWarningOrError(s"This syntax is no longer supported; parameter needs to be enclosed in (...)") + + in.nextToken() + val t = infixType() + + if (false && in.isScala2Mode) { + patch(source, Position(start), "(") + patch(source, Position(in.lastOffset), ")") + } + t + } + else TypeTree() + (atPos(start) { makeParameter(name, t, mods) }) :: Nil + } + + /** Binding ::= (Id | `_') [`:' Type] + */ + def binding(mods: Modifiers): Tree = + atPos(in.offset) { makeParameter(bindingName(), typedOpt(), mods) } + + def bindingName(): TermName = + if (in.token == USCORE) { + in.nextToken() + ctx.freshName(nme.USCORE_PARAM_PREFIX).toTermName + } + else ident() + /** Expr ::= implicit Id `=>' Expr - * BlockResult ::= implicit Id [`:' InfixType] `=>' Block - */ - def implicitClosure(start: Int, location: Location.Value, implicitMod: Option[Mod] = None): Tree = { - var mods = atPos(start) { Modifiers(Implicit) } - if (implicitMod.nonEmpty) mods = mods.withAddedMod(implicitMod.get) - val id = termIdent() - val paramExpr = - if (location == Location.InBlock && in.token == COLON) - atPos(startOffset(id), in.skipToken()) { Typed(id, infixType()) } - else - id - closureRest(start, location, convertToParam(paramExpr, mods) :: Nil) - } + * BlockResult ::= implicit Id [`:' InfixType] `=>' Block // Scala2 only + */ + def implicitClosure(start: Int, location: Location.Value, implicitMods: Modifiers): Tree = + closureRest(start, location, funParams(implicitMods, location)) def closureRest(start: Int, location: Location.Value, params: List[Tree]): Tree = atPos(start, in.offset) { @@ -1483,7 +1526,7 @@ object Parsers { private def modOfToken(tok: Int): Mod = tok match { case ABSTRACT => Mod.Abstract() case FINAL => Mod.Final() - case IMPLICIT => Mod.Implicit(ImplicitCommon) + case IMPLICIT => Mod.Implicit() case INLINE => Mod.Inline() case LAZY => Mod.Lazy() case OVERRIDE => Mod.Override() @@ -1576,6 +1619,9 @@ object Parsers { normalize(loop(start)) } + def implicitMods(): Modifiers = + addMod(EmptyModifiers, atPos(accept(IMPLICIT)) { Mod.Implicit() }) + /** Wrap annotation or constructor in New(...).<init> */ def wrapNew(tpt: Tree) = Select(New(tpt), nme.CONSTRUCTOR) @@ -1681,9 +1727,9 @@ object Parsers { * Param ::= id `:' ParamType [`=' Expr] */ def paramClauses(owner: Name, ofCaseClass: Boolean = false): List[List[ValDef]] = { - var implicitMod: Mod = null - var firstClauseOfCaseClass = ofCaseClass + var imods: Modifiers = EmptyModifiers var implicitOffset = -1 // use once + var firstClauseOfCaseClass = ofCaseClass def param(): ValDef = { val start = in.offset var mods = annotsAsMods() @@ -1718,7 +1764,7 @@ object Parsers { if (in.token == ARROW) { if (owner.isTypeName && !(mods is Local)) syntaxError(s"${if (mods is Mutable) "`var'" else "`val'"} parameters may not be call-by-name") - else if (implicitMod != null) + else if (imods.hasFlags) syntaxError("implicit parameters may not be call-by-name") } paramType() @@ -1730,7 +1776,7 @@ object Parsers { mods = mods.withPos(mods.pos.union(Position(implicitOffset, implicitOffset))) implicitOffset = -1 } - if (implicitMod != null) mods = addMod(mods, implicitMod) + for (imod <- imods.mods) mods = addMod(mods, imod) ValDef(name, tpt, default).withMods(mods) } } @@ -1739,7 +1785,7 @@ object Parsers { else { if (in.token == IMPLICIT) { implicitOffset = in.offset - implicitMod = atPos(in.skipToken()) { Mod.Implicit(Implicit) } + imods = implicitMods() } commaSeparated(param) } @@ -1749,7 +1795,7 @@ object Parsers { if (in.token == LPAREN) paramClause() :: { firstClauseOfCaseClass = false - if (implicitMod == null) clauses() else Nil + if (imods.hasFlags) Nil else clauses() } else Nil } @@ -2212,9 +2258,9 @@ object Parsers { stats.toList } - def localDef(start: Int, implicitFlag: FlagSet, implicitMod: Option[Mod] = None): Tree = { - var mods = addFlag(defAnnotsMods(localModifierTokens), implicitFlag) - if (implicitMod.nonEmpty) mods = mods.withAddedMod(implicitMod.get) + def localDef(start: Int, implicitMods: Modifiers = EmptyModifiers): Tree = { + var mods = defAnnotsMods(localModifierTokens) + for (imod <- implicitMods.mods) mods = addMod(mods, imod) defOrDcl(start, mods) } @@ -2237,11 +2283,11 @@ object Parsers { else if (isDefIntro(localModifierTokens)) if (in.token == IMPLICIT) { val start = in.offset - val mod = atPos(in.skipToken()) { Mod.Implicit(ImplicitCommon) } - if (isIdent) stats += implicitClosure(start, Location.InBlock, Some(mod)) - else stats += localDef(start, ImplicitCommon, Some(mod)) + val imods = implicitMods() + if (isBindingIntro) stats += implicitClosure(start, Location.InBlock, imods) + else stats += localDef(start, imods) } else { - stats += localDef(in.offset, EmptyFlags) + stats += localDef(in.offset) } else if (!isStatSep && (in.token != CASE)) { exitOnError = mustStartStat diff --git a/compiler/src/dotty/tools/dotc/parsing/Tokens.scala b/compiler/src/dotty/tools/dotc/parsing/Tokens.scala index 5324207db..280832ef3 100644 --- a/compiler/src/dotty/tools/dotc/parsing/Tokens.scala +++ b/compiler/src/dotty/tools/dotc/parsing/Tokens.scala @@ -209,6 +209,8 @@ object Tokens extends TokensCommon { final val canStartTypeTokens = literalTokens | identifierTokens | BitSet( THIS, SUPER, USCORE, LPAREN, AT) + final val canStartBindingTokens = identifierTokens | BitSet(USCORE, LPAREN) + final val templateIntroTokens = BitSet(CLASS, TRAIT, OBJECT, CASECLASS, CASEOBJECT) final val dclIntroTokens = BitSet(DEF, VAL, VAR, TYPE) diff --git a/compiler/src/dotty/tools/dotc/printing/RefinedPrinter.scala b/compiler/src/dotty/tools/dotc/printing/RefinedPrinter.scala index 1ddf3cd6d..3085ad8fd 100644 --- a/compiler/src/dotty/tools/dotc/printing/RefinedPrinter.scala +++ b/compiler/src/dotty/tools/dotc/printing/RefinedPrinter.scala @@ -113,20 +113,21 @@ class RefinedPrinter(_ctx: Context) extends PlainPrinter(_ctx) { override def toText(tp: Type): Text = controlled { def toTextTuple(args: List[Type]): Text = "(" ~ Text(args.map(argText), ", ") ~ ")" - def toTextFunction(args: List[Type]): Text = + def toTextFunction(args: List[Type], isImplicit: Boolean): Text = changePrec(GlobalPrec) { val argStr: Text = if (args.length == 2 && !defn.isTupleType(args.head)) atPrec(InfixPrec) { argText(args.head) } else toTextTuple(args.init) - argStr ~ " => " ~ argText(args.last) + ("implicit " provided isImplicit) ~ argStr ~ " => " ~ argText(args.last) } homogenize(tp) match { case AppliedType(tycon, args) => val cls = tycon.typeSymbol if (tycon.isRepeatedParam) return toTextLocal(args.head) ~ "*" - if (defn.isFunctionClass(cls)) return toTextFunction(args) + if (defn.isFunctionClass(cls)) return toTextFunction(args, isImplicit = false) + if (defn.isImplicitFunctionClass(cls)) return toTextFunction(args, isImplicit = true) if (defn.isTupleClass(cls)) return toTextTuple(args) return (toTextLocal(tycon) ~ "[" ~ Text(args map argText, ", ") ~ "]").close case tp: TypeRef => diff --git a/compiler/src/dotty/tools/dotc/reporting/diagnostic/messages.scala b/compiler/src/dotty/tools/dotc/reporting/diagnostic/messages.scala index 489165e56..9dda233bf 100644 --- a/compiler/src/dotty/tools/dotc/reporting/diagnostic/messages.scala +++ b/compiler/src/dotty/tools/dotc/reporting/diagnostic/messages.scala @@ -224,6 +224,8 @@ object messages { extends Message(8) { val kind = "Member Not Found" + //println(i"site = $site, decls = ${site.decls}, source = ${site.widen.typeSymbol.sourceFile}") //DEBUG + val msg = { import core.Flags._ val maxDist = 3 @@ -606,7 +608,7 @@ object messages { |""" } - case class WrongNumberOfArgs(fntpe: Type, argKind: String, expectedArgs: List[TypeParamInfo], actual: List[untpd.Tree])(implicit ctx: Context) + case class WrongNumberOfTypeArgs(fntpe: Type, expectedArgs: List[TypeParamInfo], actual: List[untpd.Tree])(implicit ctx: Context) extends Message(22) { val kind = "Syntax" @@ -628,7 +630,7 @@ object messages { } val msg = - hl"""|${NoColor(msgPrefix)} ${argKind} arguments for $prettyName$expectedArgString + hl"""|${NoColor(msgPrefix)} type arguments for $prettyName$expectedArgString |expected: $expectedArgString |actual: $actualArgString""".stripMargin diff --git a/compiler/src/dotty/tools/dotc/transform/Erasure.scala b/compiler/src/dotty/tools/dotc/transform/Erasure.scala index 7595e5f2e..71ecb5c65 100644 --- a/compiler/src/dotty/tools/dotc/transform/Erasure.scala +++ b/compiler/src/dotty/tools/dotc/transform/Erasure.scala @@ -345,21 +345,23 @@ object Erasure extends TypeTestsCasts{ override def typedSelect(tree: untpd.Select, pt: Type)(implicit ctx: Context): Tree = { def mapOwner(sym: Symbol): Symbol = { - val owner = sym.owner - if ((owner eq defn.AnyClass) || (owner eq defn.AnyValClass)) { - assert(sym.isConstructor, s"${sym.showLocated}") - defn.ObjectClass - } - else if (defn.isUnimplementedFunctionClass(owner)) - defn.FunctionXXLClass - else - owner + def recur(owner: Symbol): Symbol = + if ((owner eq defn.AnyClass) || (owner eq defn.AnyValClass)) { + assert(sym.isConstructor, s"${sym.showLocated}") + defn.ObjectClass + } else if (defn.isUnimplementedFunctionClass(owner)) + defn.FunctionXXLClass + else if (defn.isImplicitFunctionClass(owner)) + recur(defn.FunctionClass(owner.name.functionArity)) + else + owner + recur(sym.owner) } - var sym = tree.symbol - val owner = mapOwner(sym) - if (owner ne sym.owner) sym = owner.info.decl(sym.name).symbol - assert(sym.exists, owner) + val origSym = tree.symbol + val owner = mapOwner(origSym) + val sym = if (owner eq origSym.owner) origSym else owner.info.decl(origSym.name).symbol + assert(sym.exists, origSym.showLocated) def select(qual: Tree, sym: Symbol): Tree = { val name = tree.typeOpt match { diff --git a/compiler/src/dotty/tools/dotc/transform/ShortcutImplicits.scala b/compiler/src/dotty/tools/dotc/transform/ShortcutImplicits.scala new file mode 100644 index 000000000..b5469610f --- /dev/null +++ b/compiler/src/dotty/tools/dotc/transform/ShortcutImplicits.scala @@ -0,0 +1,165 @@ +package dotty.tools.dotc +package transform + +import TreeTransforms._ +import core.DenotTransformers.IdentityDenotTransformer +import core.Symbols._ +import core.Contexts._ +import core.Types._ +import core.Flags._ +import core.Decorators._ +import core.StdNames.nme +import core.Names._ +import core.NameOps._ +import ast.Trees._ +import ast.tpd +import collection.mutable + +/** This phase optimizes code using implicit function types, by applying two rewrite rules. + * Let IF be the implicit function type + * + * implicit Us => R + * + * (1) A method definition + * + * def m(xs: Ts): IF = implicit (ys: Us) => E + * + * is expanded to two methods: + * + * def m(xs: Ts): IF = implicit (ys: Us) => m$direct(xs)(ys) + * def m$direct(xs: Ts)(ys: Us): R = E + * + * (and equivalently for methods with type parameters or a different number of value parameter lists). + * An abstract method definition + * + * def m(xs: Ts): IF + * + * is expanded to: + * + * def m(xs: Ts): IF + * def m$direct(xs: Ts)(ys: Us): R + * + * (2) A reference `qual.apply` where `qual` has implicit function type and + * `qual` refers to a method `m` is rewritten to a reference to `m$direct`, + * keeping the same type and value arguments as they are found in `qual`. + */ +class ShortcutImplicits extends MiniPhase with IdentityDenotTransformer { thisTransform => + import tpd._ + + override def phaseName: String = "shortcutImplicits" + val treeTransform = new Transform + + /** If this option is true, we don't specialize symbols that are known to be only + * targets of monomorphic calls. + * The reason for this option is that benchmarks show that on the JVM for monomorphic dispatch + * scenarios inlining and escape analysis can often remove all calling overhead, so we might as + * well not duplicate the code. We need more experience to decide on the best setting of this option. + */ + final val specializeMonoTargets = true + + class Transform extends TreeTransform { + def phase = thisTransform + + override def prepareForUnit(tree: Tree)(implicit ctx: Context) = new Transform + + /** A map to cache mapping local methods to their direct counterparts. + * A fresh map is created for each unit. + */ + private val directMeth = new mutable.HashMap[Symbol, Symbol] + + /** Should `sym` get a ..$direct companion? + * This is the case if (1) `sym` is a method with an implicit function type as final result type. + * However if `specializeMonoTargets` is false, we exclude symbols that are known + * to be only targets of monomorphic calls because they are effectively + * final and don't override anything. + */ + private def shouldBeSpecialized(sym: Symbol)(implicit ctx: Context) = + sym.is(Method, butNot = Accessor) && + defn.isImplicitFunctionType(sym.info.finalResultType) && + (specializeMonoTargets || !sym.isEffectivelyFinal || sym.allOverriddenSymbols.nonEmpty) + + /** @pre The type's final result type is an implicit function type `implicit Ts => R`. + * @return The type of the `apply` member of `implicit Ts => R`. + */ + private def directInfo(info: Type)(implicit ctx: Context): Type = info match { + case info: PolyType => info.derivedPolyType(resType = directInfo(info.resultType)) + case info: MethodType => info.derivedMethodType(resType = directInfo(info.resultType)) + case info: ExprType => directInfo(info.resultType) + case info => info.member(nme.apply).info + } + + /** A new `m$direct` method to accompany the given method `m` */ + private def newDirectMethod(sym: Symbol)(implicit ctx: Context): Symbol = { + val direct = sym.copy( + name = sym.name.directName, + flags = sym.flags | Synthetic, + info = directInfo(sym.info)) + if (direct.allOverriddenSymbols.isEmpty) direct.resetFlag(Override) + direct + } + + /** The direct method `m$direct` that accompanies the given method `m`. + * Create one if it does not exist already. + */ + private def directMethod(sym: Symbol)(implicit ctx: Context): Symbol = + if (sym.owner.isClass) { + val direct = sym.owner.info.member(sym.name.directName) + .suchThat(_.info matches directInfo(sym.info)).symbol + if (direct.maybeOwner == sym.owner) direct + else newDirectMethod(sym).enteredAfter(thisTransform) + } + else directMeth.getOrElseUpdate(sym, newDirectMethod(sym)) + + + /** Transform `qual.apply` occurrences according to rewrite rule (2) above */ + override def transformSelect(tree: Select)(implicit ctx: Context, info: TransformerInfo) = + if (tree.name == nme.apply && + defn.isImplicitFunctionType(tree.qualifier.tpe.widen) && + shouldBeSpecialized(tree.qualifier.symbol)) { + def directQual(tree: Tree): Tree = tree match { + case Apply(fn, args) => cpy.Apply(tree)(directQual(fn), args) + case TypeApply(fn, args) => cpy.TypeApply(tree)(directQual(fn), args) + case Block(stats, expr) => cpy.Block(tree)(stats, directQual(expr)) + case tree: RefTree => + cpy.Ref(tree)(tree.name.directName) + .withType(directMethod(tree.symbol).termRef) + } + directQual(tree.qualifier) + } else tree + + /** Transform methods with implicit function type result according to rewrite rule (1) above */ + override def transformDefDef(mdef: DefDef)(implicit ctx: Context, info: TransformerInfo): Tree = { + val original = mdef.symbol + if (shouldBeSpecialized(original)) { + val direct = directMethod(original) + + def splitClosure(tree: Tree): (List[Type] => List[List[Tree]] => Tree, Tree) = tree match { + case Block(Nil, expr) => splitClosure(expr) + case Block((meth @ DefDef(nme.ANON_FUN, Nil, clparams :: Nil, _, _)) :: Nil, cl: Closure) => + val tparamSyms = mdef.tparams.map(_.symbol) + val vparamSymss = mdef.vparamss.map(_.map(_.symbol)) + val clparamSyms = clparams.map(_.symbol) + val remappedCore = (ts: List[Type]) => (prefss: List[List[Tree]]) => + meth.rhs + .subst(tparamSyms ::: (vparamSymss.flatten ++ clparamSyms), + ts.map(_.typeSymbol) ::: prefss.flatten.map(_.symbol)) + .changeOwnerAfter(original, direct, thisTransform) + .changeOwnerAfter(meth.symbol, direct, thisTransform) + val forwarder = ref(direct) + .appliedToTypeTrees(tparamSyms.map(ref(_))) + .appliedToArgss(vparamSymss.map(_.map(ref(_))) :+ clparamSyms.map(ref(_))) + val fwdClosure = cpy.Block(tree)(cpy.DefDef(meth)(rhs = forwarder) :: Nil, cl) + (remappedCore, fwdClosure) + case EmptyTree => + (_ => _ => EmptyTree, EmptyTree) + } + + val (remappedCore, fwdClosure) = splitClosure(mdef.rhs) + val originalDef = cpy.DefDef(mdef)(rhs = fwdClosure) + val directDef = polyDefDef(direct.asTerm, remappedCore) + Thicket(originalDef, directDef) + } + else mdef + } + } +} diff --git a/compiler/src/dotty/tools/dotc/typer/Applications.scala b/compiler/src/dotty/tools/dotc/typer/Applications.scala index da0a59c7b..8a18e63c0 100644 --- a/compiler/src/dotty/tools/dotc/typer/Applications.scala +++ b/compiler/src/dotty/tools/dotc/typer/Applications.scala @@ -975,9 +975,21 @@ trait Applications extends Compatibility { self: Typer with Dynamic => } /** In a set of overloaded applicable alternatives, is `alt1` at least as good as - * `alt2`? `alt1` and `alt2` are non-overloaded references. + * `alt2`? Also used for implicits disambiguation. + * + * @param alt1, alt2 Non-overloaded references indicating the two choices + * @param level1, level2 If alternatives come from a comparison of two contextual + * implicit candidates, the nesting levels of the candidates. + * In all other cases the nesting levels are both 0. + * + * An alternative A1 is "as good as" an alternative A2 if it wins or draws in a tournament + * that awards one point for each of the following + * + * - A1 is nested more deeply than A2 + * - The nesting levels of A1 and A2 are the same, and A1's owner derives from A2's owner + * - A1's type is more specific than A2's type. */ - def isAsGood(alt1: TermRef, alt2: TermRef)(implicit ctx: Context): Boolean = track("isAsGood") { ctx.traceIndented(i"isAsGood($alt1, $alt2)", overload) { + def isAsGood(alt1: TermRef, alt2: TermRef, nesting1: Int = 0, nesting2: Int = 0)(implicit ctx: Context): Boolean = track("isAsGood") { ctx.traceIndented(i"isAsGood($alt1, $alt2)", overload) { assert(alt1 ne alt2) @@ -1092,9 +1104,9 @@ trait Applications extends Compatibility { self: Typer with Dynamic => val tp1 = stripImplicit(alt1.widen) val tp2 = stripImplicit(alt2.widen) - def winsOwner1 = isDerived(owner1, owner2) + def winsOwner1 = nesting1 > nesting2 || isDerived(owner1, owner2) def winsType1 = isAsSpecific(alt1, tp1, alt2, tp2) - def winsOwner2 = isDerived(owner2, owner1) + def winsOwner2 = nesting2 > nesting1 || isDerived(owner2, owner1) def winsType2 = isAsSpecific(alt2, tp2, alt1, tp1) overload.println(i"isAsGood($alt1, $alt2)? $tp1 $tp2 $winsOwner1 $winsType1 $winsOwner2 $winsType2") @@ -1294,7 +1306,7 @@ trait Applications extends Compatibility { self: Typer with Dynamic => val alts1 = alts filter pt.isMatchedBy resolveOverloaded(alts1, pt1, targs1) - case defn.FunctionOf(args, resultType) => + case defn.FunctionOf(args, resultType, _) => narrowByTypes(alts, args, resultType) case pt => @@ -1345,7 +1357,7 @@ trait Applications extends Compatibility { self: Typer with Dynamic => // (p_1_1, ..., p_m_1) => r_1 // ... // (p_1_n, ..., p_m_n) => r_n - val decomposedFormalsForArg: List[Option[(List[Type], Type)]] = + val decomposedFormalsForArg: List[Option[(List[Type], Type, Boolean)]] = formalsForArg.map(defn.FunctionOf.unapply) if (decomposedFormalsForArg.forall(_.isDefined)) { val formalParamTypessForArg: List[List[Type]] = diff --git a/compiler/src/dotty/tools/dotc/typer/ErrorReporting.scala b/compiler/src/dotty/tools/dotc/typer/ErrorReporting.scala index 270ad6c8a..1238ad568 100644 --- a/compiler/src/dotty/tools/dotc/typer/ErrorReporting.scala +++ b/compiler/src/dotty/tools/dotc/typer/ErrorReporting.scala @@ -55,8 +55,8 @@ object ErrorReporting { errorMsg(ex.show, ctx) } - def wrongNumberOfArgs(fntpe: Type, kind: String, expectedArgs: List[TypeParamInfo], actual: List[untpd.Tree], pos: Position)(implicit ctx: Context) = - errorType(WrongNumberOfArgs(fntpe, kind, expectedArgs, actual)(ctx), pos) + def wrongNumberOfTypeArgs(fntpe: Type, expectedArgs: List[TypeParamInfo], actual: List[untpd.Tree], pos: Position)(implicit ctx: Context) = + errorType(WrongNumberOfTypeArgs(fntpe, expectedArgs, actual)(ctx), pos) class Errors(implicit ctx: Context) { diff --git a/compiler/src/dotty/tools/dotc/typer/Implicits.scala b/compiler/src/dotty/tools/dotc/typer/Implicits.scala index 1a9a8f64c..331533204 100644 --- a/compiler/src/dotty/tools/dotc/typer/Implicits.scala +++ b/compiler/src/dotty/tools/dotc/typer/Implicits.scala @@ -29,12 +29,15 @@ import Inferencing.fullyDefinedType import Trees._ import Hashable._ import config.Config -import config.Printers.{implicits, implicitsDetailed} +import config.Printers.{implicits, implicitsDetailed, typr} import collection.mutable /** Implicit resolution */ object Implicits { + /** An eligible implicit candidate, consisting of an implicit reference and a nesting level */ + case class Candidate(ref: TermRef, level: Int) + /** A common base class of contextual implicits and of-type implicits which * represents a set of implicit references. */ @@ -42,11 +45,14 @@ object Implicits { implicit val ctx: Context = if (initctx == NoContext) initctx else initctx retractMode Mode.ImplicitsEnabled + /** The nesting level of this context. Non-zero only in ContextialImplicits */ + def level: Int = 0 + /** The implicit references */ def refs: List[TermRef] /** Return those references in `refs` that are compatible with type `pt`. */ - protected def filterMatching(pt: Type)(implicit ctx: Context): List[TermRef] = track("filterMatching") { + protected def filterMatching(pt: Type)(implicit ctx: Context): List[Candidate] = track("filterMatching") { def refMatches(ref: TermRef)(implicit ctx: Context) = /*ctx.traceIndented(i"refMatches $ref $pt")*/ { @@ -97,8 +103,9 @@ object Implicits { } } - if (refs.isEmpty) refs - else refs filter (refMatches(_)(ctx.fresh.addMode(Mode.TypevarsMissContext).setExploreTyperState)) // create a defensive copy of ctx to avoid constraint pollution + if (refs.isEmpty) Nil + else refs.filter(refMatches(_)(ctx.fresh.addMode(Mode.TypevarsMissContext).setExploreTyperState)) // create a defensive copy of ctx to avoid constraint pollution + .map(Candidate(_, level)) } } @@ -114,8 +121,8 @@ object Implicits { buf.toList } - /** The implicit references that are eligible for expected type `tp` */ - lazy val eligible: List[TermRef] = + /** The candidates that are eligible for expected type `tp` */ + lazy val eligible: List[Candidate] = /*>|>*/ track("eligible in tpe") /*<|<*/ { /*>|>*/ ctx.traceIndented(i"eligible($tp), companions = ${companionRefs.toList}%, %", implicitsDetailed, show = true) /*<|<*/ { if (refs.nonEmpty && monitored) record(s"check eligible refs in tpe", refs.length) @@ -135,10 +142,21 @@ object Implicits { * @param outerCtx the next outer context that makes visible further implicits */ class ContextualImplicits(val refs: List[TermRef], val outerImplicits: ContextualImplicits)(initctx: Context) extends ImplicitRefs(initctx) { - private val eligibleCache = new mutable.AnyRefMap[Type, List[TermRef]] + private val eligibleCache = new mutable.AnyRefMap[Type, List[Candidate]] + + /** The level increases if current context has a different owner or scope than + * the context of the next-outer ImplicitRefs. This is however disabled under + * Scala2 mode, since we do not want to change the implicit disambiguation then. + */ + override val level: Int = + if (outerImplicits == null) 1 + else if (ctx.scala2Mode || + (ctx.owner eq outerImplicits.ctx.owner) && + (ctx.scope eq outerImplicits.ctx.scope)) outerImplicits.level + else outerImplicits.level + 1 /** The implicit references that are eligible for type `tp`. */ - def eligible(tp: Type): List[TermRef] = /*>|>*/ track(s"eligible in ctx") /*<|<*/ { + def eligible(tp: Type): List[Candidate] = /*>|>*/ track(s"eligible in ctx") /*<|<*/ { if (tp.hash == NotCached) computeEligible(tp) else eligibleCache get tp match { case Some(eligibles) => @@ -162,13 +180,13 @@ object Implicits { } } - private def computeEligible(tp: Type): List[TermRef] = /*>|>*/ ctx.traceIndented(i"computeEligible $tp in $refs%, %", implicitsDetailed) /*<|<*/ { + private def computeEligible(tp: Type): List[Candidate] = /*>|>*/ ctx.traceIndented(i"computeEligible $tp in $refs%, %", implicitsDetailed) /*<|<*/ { if (monitored) record(s"check eligible refs in ctx", refs.length) val ownEligible = filterMatching(tp) if (outerImplicits == NoContext.implicits) ownEligible else ownEligible ::: { - val shadowed = (ownEligible map (_.name)).toSet - outerImplicits.eligible(tp) filterNot (ref => shadowed contains ref.name) + val shadowed = ownEligible.map(_.ref.name).toSet + outerImplicits.eligible(tp).filterNot(cand => shadowed.contains(cand.ref.name)) } } @@ -198,8 +216,8 @@ object Implicits { * @param tree The typed tree that needs to be inserted * @param ctx The context after the implicit search */ - case class SearchSuccess(tree: tpd.Tree, ref: TermRef, tstate: TyperState) extends SearchResult { - override def toString = s"SearchSuccess($tree, $ref)" + case class SearchSuccess(tree: tpd.Tree, ref: TermRef, level: Int, tstate: TyperState) extends SearchResult { + override def toString = s"SearchSuccess($tree, $ref, $level)" } /** A failed search */ @@ -478,7 +496,7 @@ trait Implicits { self: Typer => */ def inferImplicitArg(formal: Type, error: (String => String) => Unit, pos: Position)(implicit ctx: Context): Tree = inferImplicit(formal, EmptyTree, pos) match { - case SearchSuccess(arg, _, _) => + case SearchSuccess(arg, _, _, _) => arg case ambi: AmbiguousImplicits => error(where => s"ambiguous implicits: ${ambi.explanation} of $where") @@ -621,12 +639,13 @@ trait Implicits { self: Typer => protected def failedSearch: SearchFailure = NoImplicitMatches /** Search a list of eligible implicit references */ - def searchImplicits(eligible: List[TermRef], contextual: Boolean): SearchResult = { + def searchImplicits(eligible: List[Candidate], contextual: Boolean): SearchResult = { val constr = ctx.typerState.constraint /** Try to typecheck an implicit reference */ - def typedImplicit(ref: TermRef)(implicit ctx: Context): SearchResult = track("typedImplicit") { ctx.traceIndented(i"typed implicit $ref, pt = $pt, implicitsEnabled == ${ctx.mode is ImplicitsEnabled}", implicits, show = true) { + def typedImplicit(cand: Candidate)(implicit ctx: Context): SearchResult = track("typedImplicit") { ctx.traceIndented(i"typed implicit ${cand.ref}, pt = $pt, implicitsEnabled == ${ctx.mode is ImplicitsEnabled}", implicits, show = true) { assert(constr eq ctx.typerState.constraint) + val ref = cand.ref var generated: Tree = tpd.ref(ref).withPos(pos) if (!argument.isEmpty) generated = typedUnadapted( @@ -667,7 +686,7 @@ trait Implicits { self: Typer => if fn.symbol == defn.Predef_eqAny && !validEqAnyArgs(arg1.tpe, arg2.tpe) => nonMatchingImplicit(ref, Nil) case _ => - SearchSuccess(generated1, ref, ctx.typerState) + SearchSuccess(generated1, ref, cand.level, ctx.typerState) } }} @@ -676,19 +695,20 @@ trait Implicits { self: Typer => * @param pending The list of implicit references that remain to be investigated * @param acc An accumulator of successful matches found so far. */ - def rankImplicits(pending: List[TermRef], acc: List[SearchSuccess]): List[SearchSuccess] = pending match { - case ref :: pending1 => + def rankImplicits(pending: List[Candidate], acc: List[SearchSuccess]): List[SearchSuccess] = pending match { + case cand :: pending1 => val history = ctx.searchHistory nest wildProto val result = - if (history eq ctx.searchHistory) divergingImplicit(ref) - else typedImplicit(ref)(nestedContext.setNewTyperState.setSearchHistory(history)) + if (history eq ctx.searchHistory) divergingImplicit(cand.ref) + else typedImplicit(cand)(nestedContext.setNewTyperState.setSearchHistory(history)) result match { case fail: SearchFailure => rankImplicits(pending1, acc) case best: SearchSuccess => if (ctx.mode.is(Mode.ImplicitExploration)) best :: Nil else { - val newPending = pending1 filter (isAsGood(_, best.ref)(nestedContext.setExploreTyperState)) + val newPending = pending1.filter(cand1 => + isAsGood(cand1.ref, best.ref, cand1.level, best.level)(nestedContext.setExploreTyperState)) rankImplicits(newPending, best :: acc) } } @@ -717,8 +737,9 @@ trait Implicits { self: Typer => /** Convert a (possibly empty) list of search successes into a single search result */ def condense(hits: List[SearchSuccess]): SearchResult = hits match { case best :: alts => - alts find (alt => isAsGood(alt.ref, best.ref)(ctx.fresh.setExploreTyperState)) match { + alts find (alt => isAsGood(alt.ref, best.ref, alt.level, best.level)(ctx.fresh.setExploreTyperState)) match { case Some(alt) => + typr.println(i"ambiguous implicits for $pt: ${best.ref} @ ${best.level}, ${alt.ref} @ ${alt.level}") /* !!! DEBUG println(i"ambiguous refs: ${hits map (_.ref) map (_.show) mkString ", "}") isAsGood(best.ref, alt.ref, explain = true)(ctx.fresh.withExploreTyperState) @@ -735,16 +756,18 @@ trait Implicits { self: Typer => failedSearch } + def ranking(cand: Candidate) = -ctx.runInfo.useCount(cand.ref) + /** Sort list of implicit references according to their popularity * (# of times each was picked in current run). */ - def sort(eligible: List[TermRef]) = eligible match { + def sort(eligible: List[Candidate]) = eligible match { case Nil => eligible case e1 :: Nil => eligible case e1 :: e2 :: Nil => - if (ctx.runInfo.useCount(e1) < ctx.runInfo.useCount(e2)) e2 :: e1 :: Nil + if (ranking(e2) < ranking(e1)) e2 :: e1 :: Nil else eligible - case _ => eligible.sortBy(-ctx.runInfo.useCount(_)) + case _ => eligible.sortBy(ranking) } condense(rankImplicits(sort(eligible), Nil)) diff --git a/compiler/src/dotty/tools/dotc/typer/ImportInfo.scala b/compiler/src/dotty/tools/dotc/typer/ImportInfo.scala index b4ec3390e..e44343e70 100644 --- a/compiler/src/dotty/tools/dotc/typer/ImportInfo.scala +++ b/compiler/src/dotty/tools/dotc/typer/ImportInfo.scala @@ -98,7 +98,7 @@ class ImportInfo(symf: => Symbol, val selectors: List[untpd.Tree], val isRootImp * * TODO: Once we have fully bootstrapped, I would prefer if we expressed * unimport with an `override` modifier, and generalized it to all imports. - * I believe this would be more transparent than the curren set of conditions. E.g. + * I believe this would be more transparent than the current set of conditions. E.g. * * override import Predef.{any2stringAdd => _, StringAdd => _, _} // disables String + * override import java.lang.{} // disables all imports diff --git a/compiler/src/dotty/tools/dotc/typer/TypeAssigner.scala b/compiler/src/dotty/tools/dotc/typer/TypeAssigner.scala index ca0af0e2b..4a97648f5 100644 --- a/compiler/src/dotty/tools/dotc/typer/TypeAssigner.scala +++ b/compiler/src/dotty/tools/dotc/typer/TypeAssigner.scala @@ -313,7 +313,8 @@ trait TypeAssigner { val ownType = fn.tpe.widen match { case fntpe @ MethodType(_, ptypes) => if (sameLength(ptypes, args) || ctx.phase.prev.relaxedTyping) fntpe.instantiate(args.tpes) - else wrongNumberOfArgs(fn.tpe, "", fntpe.typeParams, args, tree.pos) + else + errorType(i"wrong number of arguments for $fntpe: ${fn.tpe}, expected: ${ptypes.length}, found: ${args.length}", tree.pos) case t => errorType(i"${err.exprStr(fn)} does not take parameters", tree.pos) } @@ -368,7 +369,7 @@ trait TypeAssigner { else { val argTypes = args.tpes if (sameLength(argTypes, paramNames) || ctx.phase.prev.relaxedTyping) pt.instantiate(argTypes) - else wrongNumberOfArgs(fn.tpe, "type", pt.typeParams, args, tree.pos) + else wrongNumberOfTypeArgs(fn.tpe, pt.typeParams, args, tree.pos) } case _ => errorType(i"${err.exprStr(fn)} does not take type parameters", tree.pos) @@ -461,7 +462,7 @@ trait TypeAssigner { val ownType = if (hasNamedArg(args)) (tycon.tpe /: args)(refineNamed) else if (sameLength(tparams, args)) tycon.tpe.appliedTo(args.tpes) - else wrongNumberOfArgs(tycon.tpe, "type", tparams, args, tree.pos) + else wrongNumberOfTypeArgs(tycon.tpe, tparams, args, tree.pos) tree.withType(ownType) } diff --git a/compiler/src/dotty/tools/dotc/typer/Typer.scala b/compiler/src/dotty/tools/dotc/typer/Typer.scala index af0ae0166..07a27a498 100644 --- a/compiler/src/dotty/tools/dotc/typer/Typer.scala +++ b/compiler/src/dotty/tools/dotc/typer/Typer.scala @@ -522,7 +522,7 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit case tref: TypeRef if !tref.symbol.isClass && !ctx.isAfterTyper => inferImplicit(defn.ClassTagType.appliedTo(tref), EmptyTree, tpt1.pos)(ctx.retractMode(Mode.Pattern)) match { - case SearchSuccess(arg, _, _) => + case SearchSuccess(arg, _, _, _) => return typed(untpd.Apply(untpd.TypedSplice(arg), tree.expr), pt) case _ => } @@ -663,9 +663,13 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit def typedFunction(tree: untpd.Function, pt: Type)(implicit ctx: Context) = track("typedFunction") { val untpd.Function(args, body) = tree - if (ctx.mode is Mode.Type) + if (ctx.mode is Mode.Type) { + val funCls = + if (tree.isInstanceOf[untpd.ImplicitFunction]) defn.ImplicitFunctionClass(args.length) + else defn.FunctionClass(args.length) typed(cpy.AppliedTypeTree(tree)( - untpd.TypeTree(defn.FunctionClass(args.length).typeRef), args :+ body), pt) + untpd.TypeTree(funCls.typeRef), args :+ body), pt) + } else { val params = args.asInstanceOf[List[untpd.ValDef]] @@ -1055,7 +1059,7 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit if (hasNamedArg(args)) typedNamedArgs(args) else { if (args.length != tparams.length) { - wrongNumberOfArgs(tpt1.tpe, "type", tparams, args, tree.pos) + wrongNumberOfTypeArgs(tpt1.tpe, tparams, args, tree.pos) args = args.take(tparams.length) } def typedArg(arg: untpd.Tree, tparam: TypeParamInfo) = { @@ -1493,6 +1497,7 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit case tree: untpd.If => typedIf(tree, pt) case tree: untpd.Function => typedFunction(tree, pt) case tree: untpd.Closure => typedClosure(tree, pt) + case tree: untpd.Import => typedImport(tree, retrieveSym(tree)) case tree: untpd.Match => typedMatch(tree, pt) case tree: untpd.Return => typedReturn(tree) case tree: untpd.Try => typedTry(tree, pt) @@ -1520,9 +1525,13 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit case _ => typedUnadapted(desugar(tree), pt) } - xtree match { + if (defn.isImplicitFunctionType(pt) && + xtree.isTerm && + !untpd.isImplicitClosure(xtree) && + !ctx.isAfterTyper) + makeImplicitFunction(xtree, pt) + else xtree match { case xtree: untpd.NameTree => typedNamed(encodeName(xtree), pt) - case xtree: untpd.Import => typedImport(xtree, retrieveSym(xtree)) case xtree => typedUnnamed(xtree) } } @@ -1531,6 +1540,14 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit protected def encodeName(tree: untpd.NameTree)(implicit ctx: Context): untpd.NameTree = untpd.rename(tree, tree.name.encode) + protected def makeImplicitFunction(tree: untpd.Tree, pt: Type)(implicit ctx: Context): Tree = { + val defn.FunctionOf(formals, resType, true) = pt.dealias + val paramTypes = formals.map(fullyDefinedType(_, "implicit function parameter", tree.pos)) + val ifun = desugar.makeImplicitFunction(paramTypes, tree) + typr.println(i"make implicit function $tree / $pt ---> $ifun") + typedUnadapted(ifun) + } + def typed(tree: untpd.Tree, pt: Type = WildcardType)(implicit ctx: Context): Tree = /*>|>*/ ctx.traceIndented (i"typing $tree", typr, show = true) /*<|<*/ { assertPositioned(tree) try adapt(typedUnadapted(tree, pt), pt, tree) @@ -1615,6 +1632,14 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit } } + /** Is `pt` a prototype of an `apply` selection, or a parameterless function yielding one? */ + def isApplyProto(pt: Type)(implicit ctx: Context): Boolean = pt match { + case pt: SelectionProto => pt.name == nme.apply + case pt: FunProto => pt.args.isEmpty && isApplyProto(pt.resultType) + case pt: IgnoredProto => isApplyProto(pt.ignored) + case _ => false + } + /** Add apply node or implicit conversions. Two strategies are tried, and the first * that is successful is picked. If neither of the strategies are successful, continues with * `fallBack`. @@ -1628,14 +1653,6 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit */ def tryInsertApplyOrImplicit(tree: Tree, pt: ProtoType)(fallBack: => Tree)(implicit ctx: Context): Tree = { - /** Is `pt` a prototype of an `apply` selection, or a parameterless function yielding one? */ - def isApplyProto(pt: Type): Boolean = pt match { - case pt: SelectionProto => pt.name == nme.apply - case pt: FunProto => pt.args.isEmpty && isApplyProto(pt.resultType) - case pt: IgnoredProto => isApplyProto(pt.ignored) - case _ => false - } - def tryApply(implicit ctx: Context) = { val sel = typedSelect(untpd.Select(untpd.TypedSplice(tree), nme.apply), pt) if (sel.tpe.isError) sel else adapt(sel, pt) @@ -1879,7 +1896,14 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit missingArgs case _ => ctx.typeComparer.GADTused = false - if (ctx.mode is Mode.Pattern) { + if (defn.isImplicitFunctionClass(wtp.underlyingClassRef(refinementOK = false).classSymbol) && + !untpd.isImplicitClosure(tree) && + !isApplyProto(pt) && + !ctx.isAfterTyper) { + typr.println("insert apply on implicit $tree") + typed(untpd.Select(untpd.TypedSplice(tree), nme.apply), pt) + } + else if (ctx.mode is Mode.Pattern) { tree match { case _: RefTree | _: Literal if !isVarPattern(tree) && @@ -1952,7 +1976,7 @@ class Typer extends Namer with TypeAssigner with Applications with Implicits wit } // try an implicit conversion inferView(tree, pt) match { - case SearchSuccess(inferred, _, _) => + case SearchSuccess(inferred, _, _, _) => adapt(inferred, pt) case failure: SearchFailure => if (pt.isInstanceOf[ProtoType] && !failure.isInstanceOf[AmbiguousImplicits]) tree diff --git a/compiler/test/dotc/tests.scala b/compiler/test/dotc/tests.scala index 827e1addd..f858926d5 100644 --- a/compiler/test/dotc/tests.scala +++ b/compiler/test/dotc/tests.scala @@ -84,6 +84,7 @@ class tests extends CompilerTest { val runDir = testsDir + "run/" val newDir = testsDir + "new/" val replDir = testsDir + "repl/" + val javaDir = testsDir + "pos-java-interop/" val sourceDir = "./src/" val dottyDir = sourceDir + "dotty/" @@ -260,7 +261,6 @@ class tests extends CompilerTest { dotcDir + "config/PathResolver.scala" ), List(/* "-Ylog:frontend", */ "-Xprompt") ++ staleSymbolError ++ twice) - val javaDir = "./tests/pos-java-interop/" @Test def java_all = compileFiles(javaDir, twice) //@Test def dotc_compilercommand = compileFile(dotcDir + "config/", "CompilerCommand") @@ -349,9 +349,10 @@ class tests extends CompilerTest { @Test def tasty_tests = compileDir(testsDir, "tasty", testPickling) @Test def tasty_bootstrap = { - val opt = List("-priorityclasspath", defaultOutputDir, "-Ylog-classpath") + val logging = if (false) List("-Ylog-classpath", "-verbose") else Nil + val opt = List("-priorityclasspath", defaultOutputDir) ++ logging // first compile dotty - compileDir(dottyDir, ".", List("-deep", "-Ycheck-reentrant", "-strict"))(allowDeepSubtypes) + compileDir(dottyDir, ".", List("-deep", "-Ycheck-reentrant", "-strict") ++ logging)(allowDeepSubtypes) compileDir(libDir, "dotty", "-deep" :: opt) compileDir(libDir, "scala", "-deep" :: opt) diff --git a/compiler/test/dotty/tools/dotc/parsing/ModifiersParsingTest.scala b/compiler/test/dotty/tools/dotc/parsing/ModifiersParsingTest.scala index e31ef2160..32f842e92 100644 --- a/compiler/test/dotty/tools/dotc/parsing/ModifiersParsingTest.scala +++ b/compiler/test/dotty/tools/dotc/parsing/ModifiersParsingTest.scala @@ -140,12 +140,12 @@ class ModifiersParsingTest { source = "def f(implicit a: Int, b: Int) = ???" println(source.defParam(0).modifiers) - assert(source.defParam(0).modifiers == List(Mod.Implicit(Flags.Implicit))) - assert(source.defParam(1).modifiers == List(Mod.Implicit(Flags.Implicit))) + assert(source.defParam(0).modifiers == List(Mod.Implicit())) + assert(source.defParam(1).modifiers == List(Mod.Implicit())) source = "def f(x: Int, y: Int)(implicit a: Int, b: Int) = ???" assert(source.defParam(0, 0).modifiers == List()) - assert(source.defParam(1, 0).modifiers == List(Mod.Implicit(Flags.Implicit))) + assert(source.defParam(1, 0).modifiers == List(Mod.Implicit())) } @Test def blockDef = { diff --git a/docs/blog/_posts/2016-12-05-implicit-function-types.md b/docs/blog/_posts/2016-12-05-implicit-function-types.md new file mode 100644 index 000000000..670c652ee --- /dev/null +++ b/docs/blog/_posts/2016-12-05-implicit-function-types.md @@ -0,0 +1,364 @@ +--- +layout: blog +title: Implicit Function Types +author: Martin Odersky +authorImg: /images/martin.jpg +--- + +I just made the [first pull request](https://github.com/lampepfl/dotty/pull/1775) to add _implicit function types_ to +Scala. I am pretty excited about it, because - citing the explanation +of the pull request - "_This is the first step to bring contextual +abstraction to Scala_". What do I mean by this? + +**Abstraction**: The ability to name a concept and use just the name afterwards. + +**Contextual**: A piece of a program produces results or outputs in +some context. Our programming languages are very good in describing +and abstracting what outputs are produced. But there's hardly anything +yet available to abstract over the inputs that programs get from their +context. Many interesting scenarios fall into that category, +including: + + - passing configuration data to the parts of a system that need them, + - managing capabilities for security critical tasks, + - wiring components up with dependency injection, + - defining the meanings of operations with type classes, + - more generally, passing any sort of context to a computation. + +Implicit function types are a surprisingly simple and general way to +make coding patterns solving these tasks abstractable, reducing +boilerplate code and increasing applicability. + +**First Step**: My pull request is a first implementation. It solves the + problem in principle, but introduces some run-time overhead. The + next step will be to eliminate the run-time overhead through some + simple optimizations. + +## Implicit Parameters + +In a functional setting, the inputs to a computation are most +naturally expressed as _parameters_. One could simply augment +functions to take additional parameters that represent configurations, +capabilities, dictionaries, or whatever contextual data the functions +need. The only downside with this is that often there's a large +distance in the call graph between the definition of a contextual +element and the site where it is used. Consequently, it becomes +tedious to define all those intermediate parameters and to pass them +along to where they are eventually consumed. + +Implicit parameters solve one half of the problem. Implicit +parameters do not have to be propagated using boilerplate code; the +compiler takes care of that. This makes them practical in many +scenarios where plain parameters would be too cumbersome. For +instance, type classes would be a lot less popular if one would have +to pass all dictionaries by hand. Implicit parameters are also very +useful as a general context passing mechanism. For instance in the +_dotty_ compiler, almost every function takes an implicit context +parameter which defines all elements relating to the current state of +the compilation. This is in my experience much better than the cake +pattern because it is lightweight and can express context changes in a +purely functional way. + +The main downside of implicit parameters is the verbosity of their +declaration syntax. It's hard to illustrate this with a smallish example, +because it really only becomes a problem at scale, but let's try anyway. + +Let's say we want to write some piece of code that's designed to run +in a transaction. For the sake of illustration here's a simple transaction class: + + class Transaction { + private val log = new ListBuffer[String] + def println(s: String): Unit = log += s + + private var aborted = false + private var committed = false + + def abort(): Unit = { aborted = true } + def isAborted = aborted + + def commit(): Unit = + if (!aborted && !committed) { + Console.println("******* log ********") + log.foreach(Console.println) + committed = true + } + } + +The transaction encapsulates a log, to which one can print messages. +It can be in one of three states: running, committed, or aborted. +If the transaction is committed, it prints the stored log to the console. + +The `transaction` method lets one run some given code `op` inside +a newly created transaction: + + def transaction[T](op: Transaction => T) = { + val trans: Transaction = new Transaction + op(trans) + trans.commit() + } + +The current transaction needs to be passed along a call chain to all +the places that need to access it. To illustrate this, here are three +functions `f1`, `f2` and `f3` which call each other, and also access +the current transaction. The most convenient way to achieve this is +by passing the current transaction as an implicit parameter. + + def f1(x: Int)(implicit thisTransaction: Transaction): Int = { + thisTransaction.println(s"first step: $x") + f2(x + 1) + } + def f2(x: Int)(implicit thisTransaction: Transaction): Int = { + thisTransaction.println(s"second step: $x") + f3(x * x) + } + def f3(x: Int)(implicit thisTransaction: Transaction): Int = { + thisTransaction.println(s"third step: $x") + if (x % 2 != 0) thisTransaction.abort() + x + } + +The main program calls `f1` in a fresh transaction context and prints +its result: + + def main(args: Array[String]) = { + transaction { + implicit thisTransaction => + val res = f1(args.length) + println(if (thisTransaction.isAborted) "aborted" else s"result: $res") + } + } + +Two sample calls of the program (let's call it `TransactionDemo`) are here: + + scala TransactionDemo 1 2 3 + result: 16 + ******* log ******** + first step: 3 + second step: 4 + third step: 16 + + scala TransactionDemo 1 2 3 4 + aborted + +So far, so good. The code above is quite compact as far as expressions +are concerned. In particular, it's nice that, being implicit +parameters, none of the transaction values had to be passed along +explicitly in a call. But on the definition side, things are less +rosy: Every one of the functions `f1` to `f3` needed an additional +implicit parameter: + + (implicit thisTransaction: Transaction) + +A three-times repetition might not look so bad here, but it certainly +smells of boilerplate. In real-sized projects, this can get much worse. +For instance, the _dotty_ compiler uses implicit abstraction +over contexts for most of its parts. Consequently it ends up with currently +no fewer than 2641 occurrences of the text string + + (implicit ctx: Context) + +It would be nice if we could get rid of them. + +## Implicit Functions + +Let's massage the definition of `f1` a bit by moving the last parameter section to the right of the equals sign: + + def f1(x: Int) = { implicit thisTransaction: Transaction => + thisTransaction.println(s"first step: $x") + f2(x + 1) + } + +The right hand side of this new version of `f1` is now an implicit +function value. What's the type of this value? Previously, it was +`Transaction => Int`, that is, the knowledge that the function has an +implicit parameter got lost in the type. The main extension implemented by +the pull request is to introduce implicit function types that mirror +the implicit function values which we have already. Concretely, the new +type of `f1` is: + + implicit Transaction => Int + +Just like the normal function type syntax `A => B`, desugars to `scala.Function1[A, B]` +the implicit function type syntax `implicit A => B` desugars to `scala.ImplicitFunction1[A, B]`. +The same holds at other function arities. With dotty's [pull request #1758](https://github.com/lampepfl/dotty/pull/1758) +merged there is no longer an upper limit of 22 for such functions. + +The type `ImplicitFunction1` can be thought of being defined as follows: + + trait ImplicitFunction1[-T0, R] extends Function1[T0, R] { + override def apply(implicit x: T0): R + } + +However, you won't find a classfile for this trait because all implicit function traits +get mapped to normal functions during type erasure. + +There are two rules that guide type checking of implicit function types. +The first rule says that an implicit function is applied to implicit arguments +in the same way an implicit method is. More precisely, if `t` is an expression +of an implicit function type + + t: implicit (T1, ..., Tn) => R + +such that `t` is not an implicit closure itself and `t` is not the +prefix of a call `t.apply(...)`, then an `apply` is implicitly +inserted, so `t` becomes `t.apply`. We have already seen that the +definition of `t.apply` is an implicit method as given in the +corresponding implicit function trait. Hence, it will in turn be +applied to a matching sequence of implicit arguments. The end effect is +that references to implicit functions get applied to implicit arguments in the +same way as references to implicit methods. + +The second rule is the dual of the first. If the expected type +of an expression `t` is an implicit function type + + implicit (T1, ..., Tn) => R + +then `t` is converted to an implicit closure, unless it is already one. +More precisely, `t` is mapped to the implicit closure + + implicit ($ev1: T1, ..., $evn: Tn) => t + +The parameter names of this closure are compiler-generated identifiers +which should not be accessed from user code. That is, the only way to +refer to an implicit parameter of a compiler-generated function is via +`implicitly`. + +It is important to note that this second conversion needs to be applied +_before_ the expression `t` is typechecked. This is because the +conversion establishes the necessary context to make type checking `t` +succeed by defining the required implicit parameters. + +There is one final tweak to make this all work: When using implicit parameters +for nested functions it was so far important to give all implicit parameters +of the same type the same name, or else one would get ambiguities. For instance, consider the +following fragment: + + def f(implicit c: C) = { + def g(implicit c: C) = ... implicitly[C] ... + ... + } + +If we had named the inner parameter `d` instead of `c` we would +have gotten an implicit ambiguity at the call of `implicitly` because +both `c` and `d` would be eligible: + + def f(implicit c: C) = { + def g(implicit d: C) = ... implicitly[C] ... // error! + ... + } + +The problem is that parameters in implicit closures now have +compiler-generated names, so the programmer cannot enforce the proper +naming scheme to avoid all ambiguities. We fix the problem by +introducing a new disambiguation rule which makes nested occurrences +of an implicit take precedence over outer ones. This rule, which +applies to all implicit parameters and implicit locals, is conceptually +analogous to the rule that prefers implicits defined in companion +objects of subclasses over those defined in companion objects of +superclass. With that new disambiguation rule the example code above +now compiles. + +That's the complete set of rules needed to deal with implicit function types. + +## How to Remove Boilerplate + +The main advantage of implicit function types is that, being types, +they can be abstracted. That is, one can define a name for an implicit +function type and then use just the name instead of the full type. +Let's revisit our previous example and see how it can be made more +concise using this technique. + +We first define a type `Transactional` for functions that take an implicit parameter of type `Transaction`: + + type Transactional[T] = implicit Transaction => T + +Making the return type of `f1` to `f3` a `Transactional[Int]`, we can +eliminate their implicit parameter sections: + + def f1(x: Int): Transactional[Int] = { + thisTransaction.println(s"first step: $x") + f2(x + 1) + } + def f2(x: Int): Transactional[Int] = { + thisTransaction.println(s"second step: $x") + f3(x * x) + } + def f3(x: Int): Transactional[Int] = { + thisTransaction.println(s"third step: $x") + if (x % 2 != 0) thisTransaction.abort() + x + } + +You might ask, how does `thisTransaction` typecheck, since there is no +longer a parameter with that name? In fact, `thisTransaction` is now a +global definition: + + def thisTransaction: Transactional[Transaction] = implicitly[Transaction] + +You might ask: a `Transactional[Transaction]`, is that not circular? To see more clearly, let's expand +the definition according to the rules given in the last section. `thisTransaction` +is of implicit function type, so the right hand side is expanded to the +implicit closure + + implicit ($ev0: Transaction) => implicitly[Transaction] + +The right hand side of this closure, `implicitly[Transaction]`, needs +an implicit parameter of type `Transaction`, so the closure is further +expanded to + + implicit ($ev0: Transaction) => implicitly[Transaction]($ev0) + +Now, `implicitly` is defined in `scala.Predef` like this: + + def implicitly[T](implicit x: T) = x + +If we plug that definition into the closure above and simplify, we get: + + implicit ($ev0: Transaction) => $ev0 + +So, `thisTransaction` is just the implicit identity function on `transaction`! +In other words, if we use `thisTransaction` in the body of `f1` to `f3`, it will +pick up and return the unnamed implicit parameter that's in scope. + +Finally, here are the `transaction` and `main` method that complete +the example. Since `transactional`'s parameter `op` is now a +`Transactional`, we can eliminate the `Transaction` argument to `op` +and the `Transaction` lambda in `main`; both will be added by the compiler. + + def transaction[T](op: Transactional[T]) = { + implicit val trans: Transaction = new Transaction + op + trans.commit() + } + def main(args: Array[String]) = { + transaction { + val res = f1(args.length) + println(if (thisTransaction.isAborted) "aborted" else s"result: $res") + } + } + +## Categorically Speaking + +There are many interesting connections with category theory to explore +here. On the one hand, implicit functions are used for tasks that are +sometimes covered with monads such as the reader monad. There's an +argument to be made that implicits have better composability than +monads and why that is. + +On the other hand, it turns out that implicit functions can also be +given a co-monadic interpretation, and the interplay between monads and +comonads is very interesting in its own right. + +But these discussions will have to wait for another time, as +this blog post is already too long. + +## Conclusion + +Implicit function types are unique way to abstract over the context in +which some piece of code is run. I believe they will deeply influence +the way we write Scala in the future. They are very powerful +abstractions, in the sense that just declaring a type of a function +will inject certain implicit values into the scope of the function's +implementation. Can this be abused, making code more obscure? +Absolutely, like every other powerful abstraction technique. To keep +your code sane, please keep the [Principle of Least Power](http://www.lihaoyi.com/post/StrategicScalaStylePrincipleofLeastPower.html) in mind. diff --git a/docs/syntax-summary.txt b/docs/syntax-summary.txt index 04e149de6..d382507d3 100644 --- a/docs/syntax-summary.txt +++ b/docs/syntax-summary.txt @@ -95,8 +95,8 @@ grammar. | [id '.'] `super' [ClassQualifier] `.' id ClassQualifier ::= `[' id `]' - Type ::= FunArgTypes `=>' Type Function(ts, t) - | HkTypeParamClause `=>' Type TypeLambda(ps, t) + Type ::= [`implicit'] FunArgTypes `=>' Type Function(ts, t) + | HkTypeParamClause `=>' Type TypeLambda(ps, t) | InfixType FunArgTypes ::= InfixType | `(' [ FunArgType {`,' FunArgType } ] `)' @@ -125,13 +125,13 @@ grammar. TypeBounds ::= [`>:' Type] [`<: Type] | INT TypeBoundsTree(lo, hi) TypeParamBounds ::= TypeBounds {`<%' Type} {`:' Type} ContextBounds(typeBounds, tps) - Expr ::= FunParams `=>' Expr Function(args, expr), Function(ValDef([implicit], id, TypeTree(), EmptyTree), expr) + Expr ::= [`implicit'] FunParams `=>' Expr Function(args, expr), Function(ValDef([implicit], id, TypeTree(), EmptyTree), expr) FunParams ::= Bindings - | [`implicit'] id + | id | `_' ExprInParens ::= PostfixExpr `:' Type | Expr - BlockResult ::= (FunParams | [`implicit'] id `:' InfixType) `=>' Block + BlockResult ::= [`implicit'] FunParams `=>' Block | Expr1 Expr1 ::= `if' `(' Expr `)' {nl} Expr [[semi] else Expr] If(Parens(cond), thenp, elsep?) | `if' Expr `then' Expr [[semi] else Expr] If(cond, thenp, elsep?) @@ -178,9 +178,7 @@ grammar. | {Annotation} {LocalModifier} TmplDef | Expr1 | - ResultExpr ::= Expr1 - | (Bindings | ([`implicit'] id | `_') `:' ) `=>' Block - Function(args, block) // block starts at => + ForExpr ::= `for' (`(' Enumerators `)' | `{' Enumerators `}') ForYield(enums, expr) {nl} [`yield'] Expr ForDo(enums, expr) | `for' Enumerators (`do' Expr | `yield' Expr) @@ -241,7 +239,7 @@ grammar. DefParams ::= DefParam {`,' DefParam} DefParam ::= {Annotation} [`inline'] Param ValDef(mods, id, tpe, expr) -- point of mods at id. - Bindings ::= `(' Binding {`,' Binding `)' bindings + Bindings ::= `(' Binding {`,' Binding}] `)' Binding ::= (id | `_') [`:' Type] ValDef(_, id, tpe, EmptyTree) Modifier ::= LocalModifier diff --git a/tests/bench/transactional/Benchmark.scala b/tests/bench/transactional/Benchmark.scala new file mode 100644 index 000000000..8af7ebb83 --- /dev/null +++ b/tests/bench/transactional/Benchmark.scala @@ -0,0 +1,5 @@ +package transactional +abstract class Benchmark { + def run(): Int +} + diff --git a/tests/bench/transactional/ImplicitMega.scala b/tests/bench/transactional/ImplicitMega.scala new file mode 100644 index 000000000..80e9c4a43 --- /dev/null +++ b/tests/bench/transactional/ImplicitMega.scala @@ -0,0 +1,67 @@ +package transactional +object MegaBench extends Benchmark { + type Transactional[T] = implicit Transaction => T + + def transaction[T](op: Transactional[T]): T = { + implicit val trans: Transaction = new Transaction + val res = op + trans.commit() + res + } + + def thisTransaction: Transactional[Transaction] = implicitly[Transaction] + + abstract class Op { + def f(x: Int): Transactional[Int] + } + + class Op0 extends Op { + def f(x: Int): Transactional[Int] = { + thisTransaction.println("0th step") + x + } + } + + class Op1 extends Op { + def f(x: Int): Transactional[Int] = { + thisTransaction.println("first step") + x + 1 + } + } + + class Op2 extends Op { + def f(x: Int): Transactional[Int] = { + thisTransaction.println("second step") + x + 2 + } + } + + class Op3 extends Op { + def f(x: Int): Transactional[Int] = { + thisTransaction.println("third step") + x + 3 + } + } + + val op = Array[Op](new Op0, new Op1, new Op2, new Op3) + + def f(x: Int, n: Int): Transactional[Int] = { + thisTransaction.println("fourth step") + if (n > 0) f(op(n % 4).f(x), n - 1) + else { + if (x % 2 != 0) thisTransaction.abort() + x + } + } + + def run(): Int = { + transaction { + val res = f(7, 10) + assert(!thisTransaction.isAborted) + assert(res == 22) + res + } + } +} + +object ImplicitMega extends Runner("megamorphic", MegaBench, 22) diff --git a/tests/bench/transactional/ImplicitMono.scala b/tests/bench/transactional/ImplicitMono.scala new file mode 100644 index 000000000..10391f191 --- /dev/null +++ b/tests/bench/transactional/ImplicitMono.scala @@ -0,0 +1,45 @@ +package transactional +object MonoBench extends Benchmark { + type Transactional[T] = implicit Transaction => T + + def transaction[T](op: Transactional[T]): T = { + implicit val trans: Transaction = new Transaction + val res = op + trans.commit() + res + } + + def thisTransaction: Transactional[Transaction] = implicitly[Transaction] + + def f1(x: Int): Transactional[Int] = { + thisTransaction.println("first step") + f2(x + 1) + } + def f2(x: Int): Transactional[Int] = { + thisTransaction.println("second step") + f3(x * x) + } + def f3(x: Int): Transactional[Int] = { + thisTransaction.println("third step") + f4(x + 1, 7) + } + def f4(x: Int, n: Int): Transactional[Int] = { + thisTransaction.println("fourth step") + if (n > 0) f4(x + 1, n - 1) + else { + if (x % 2 != 0) thisTransaction.abort() + x + } + } + + def run(): Int = { + transaction { + val res = f1(7) + assert(!thisTransaction.isAborted) + assert(res == 72) + res + } + } +} + +object ImplicitMono extends Runner("monomorphic implicits", MonoBench, 72) diff --git a/tests/bench/transactional/ReaderMonadic.scala b/tests/bench/transactional/ReaderMonadic.scala new file mode 100644 index 000000000..ce69c35ad --- /dev/null +++ b/tests/bench/transactional/ReaderMonadic.scala @@ -0,0 +1,87 @@ +package transactional + +case class Reader[R,A](run: R => A) { + def map[B](f: A => B): Reader[R, B] = Reader(r => f(run(r))) + def flatMap[B](f: A => Reader[R, B]): Reader[R, B] = Reader(r => f(run(r)).run(r)) +} + +object Reader { + def ask[R]: Reader[R,R] = Reader(r => r) +} + +object ReaderBench extends Benchmark { + type Transactional[T] = Reader[Transaction, T] + + def transaction[T](op: Transactional[T]): T = { + implicit val trans: Transaction = new Transaction + val res = op.run(trans) + trans.commit() + res + } + + def thisTransaction: Transactional[Transaction] = Reader.ask + + abstract class Op { + def f(x: Int): Transactional[Int] + } + + class Op0 extends Op { + def f(x: Int): Transactional[Int] = + for (trans <- thisTransaction) + yield { trans.println("0th step"); x } + } + + class Op1 extends Op { + def f(x: Int): Transactional[Int] = + for (trans <- thisTransaction) + yield { trans.println("first step"); x + 1 } + } + + class Op2 extends Op { + def f(x: Int): Transactional[Int] = + for (trans <- thisTransaction) + yield { trans.println("second step"); x + 2 } + } + + class Op3 extends Op { + def f(x: Int): Transactional[Int] = + for (trans <- thisTransaction) + yield { trans.println("third step"); x + 3 } + } + + val op = Array[Op](new Op0, new Op1, new Op2, new Op3) + + def f(x: Int, n: Int): Transactional[Int] = { + def rest(trans: Transaction): Transactional[Int] = { + trans.println("fourth step") + if (n > 0) { + for { + y <- op(n % 4).f(x) + z <- f(y: Int, n - 1) + } + yield z + } + else { + if (x % 2 != 0) + for (trans <- thisTransaction) + yield { trans.abort(); () } + Reader(_ => x) + } + } + thisTransaction.flatMap(rest) + } + + def run(): Int = { + transaction { + for (res <- f(7, 10)) + yield { + for (trans <- thisTransaction) + yield { assert(!trans.isAborted); () } + assert(res == 22) + res + } + } + } +} + +object ReaderMonadic extends Runner("reader monadic", ReaderBench, 22) diff --git a/tests/bench/transactional/Runner.scala b/tests/bench/transactional/Runner.scala new file mode 100644 index 000000000..48da7ff12 --- /dev/null +++ b/tests/bench/transactional/Runner.scala @@ -0,0 +1,25 @@ +package transactional +import System.nanoTime + +class Runner(name: String, bench: Benchmark, expected: Int) { + + val numIters = 10000000 + val numTests = 5 + + def run(): Unit = { + val start = nanoTime + var cnt = 0 + var i = 0 + while (i < numIters) { + cnt += bench.run() + i += 1 + } + assert(cnt == expected * numIters) + val duration = nanoTime - start + println(s"$name in ${duration / 1000000}ms") + } + + def main(args: Array[String]) = + for (i <- 0 until numTests) + run() +} diff --git a/tests/bench/transactional/Transaction.scala b/tests/bench/transactional/Transaction.scala new file mode 100644 index 000000000..dbb28d452 --- /dev/null +++ b/tests/bench/transactional/Transaction.scala @@ -0,0 +1,21 @@ +package transactional +import collection.mutable.ListBuffer + +class Transaction { + private val log = new ListBuffer[String] + def println(s: String): Unit = log += s + + private var aborted = false + private var committed = false + + def abort(): Unit = { aborted = true } + def isAborted = aborted + + def commit(): Unit = + if (!aborted && !committed) { + //Console.println("******* log ********") + //log.foreach(Console.println) + committed = true + } +} + diff --git a/tests/bench/transactional/results.md b/tests/bench/transactional/results.md new file mode 100644 index 000000000..702617ebb --- /dev/null +++ b/tests/bench/transactional/results.md @@ -0,0 +1,77 @@ +# Benchmark results for implicit compilation scenarios + +### Setup + +Three alternatives: + + 1. No implicit shortcuts + 2. Implicit shortcuts only for possible targets of megamorphic dispatch + (`specializeMonoTargets` in [ShortcutImplicits.scala](../../../compiler/src/dotty/tools/dotc/transform/ShortcutImplicits.scala) set to false) + 3. Implicit shortcuts for all methods returning implicit function types + (`specializeMonoTargets` set to true) + +Two benchmarks: + + - `ImplicitMono`: All calls are monomorphic. + Code in [ImplicitMono.scala](./ImplicitMono.scala). + - `ImplicitMega` : About half of the calls are (4-way) megamorphic, + the others are monomorphic. + Code in [ImplicitMega.scala](./ImplicitMega.scala). + +### Results + +| Scheme | ImplicitMono | ImplicitMega | +|---------------------|-------------:|-------------:| +| no shortcuts | 1354ms | 3260ms +| | 955ms | 2906ms +| | 908ms | 2899ms +| | 906ms | 2887ms +| | 886ms | 2872ms +| only mega shortcuts | | + | 1243ms | 2472ms +| | 926ms | 2146ms +| | 925ms | 2169ms +| | 902ms | 2136ms +| | 913ms | 2179ms +| all shortcuts | | +| | 1354ms | 1940ms +| | 1039ms | 1563ms +| | 1031ms | 1593ms +| | 1065ms | 1548ms +| | 1016ms | 1579ms + +### Interpretation + +In the fully monomorphic benchmark, specializing +only megamorphic targets has the same performance as +not specializing at all (not surprising, since there +are no megamorphic targets). Specializing everything +incurs about a 14% performance hit (maybe due to the extra +code generated; it's hard to pin down what it is). + +Note: We compute relative performance differences by comparing the +second-best test runs of each series with each other. + +In the megamorphic benchmark, it's the other way round. +Specializing only megamorphic call-sites leads to a performance +improvement of about 36% compared to no specialization. Specializing +everything leads to another 37% improvement (85% total compared +to no specialization). + +I think we need larger benchmarks to decide whether we should +specialize monomorphic call-targets or not. + +### Comparing with the Reader Monad + +Translating `ImplicitMega` to the reader monad (code in [ReaderMonadic.scala](./ReaderMonadic.scala)) gives the following runtimes: + +| Reader | +|---------| +| 11563ms | +| 11108ms | +| 11300ms | +| 11098ms | +| 11159ms | + +This translates to a 710% slowdown compared to implicit function types +with full specialization.
\ No newline at end of file diff --git a/tests/run/implicitFuns.scala b/tests/run/implicitFuns.scala new file mode 100644 index 000000000..496fba0d3 --- /dev/null +++ b/tests/run/implicitFuns.scala @@ -0,0 +1,261 @@ +object Test { + def main(args: Array[String]): Unit = { + + implicit val world: String = "world!" + + val i1 = (implicit (s: String) => s.length > 2) + val i2 = {implicit (s: String) => s.length > 2} + + assert(i1) + assert(i2) + + val x: implicit String => Boolean = { implicit (s: String) => s.length > 2 } + + val xx: implicit (String, Int) => Int = implicit (x: String, y: Int) => x.length + y + + val y: String => Boolean = x + + object nested { + implicit val empty: String = "" + assert(!x) + } + + val yy: (String, Int) => Any = xx + + val z1: implicit String => Boolean = implicitly[String].length >= 2 + assert(z1) + + type StringlyBool = implicit String => Boolean + + val z2: StringlyBool = implicitly[String].length >= 2 + assert(z2) + + type Stringly[T] = implicit String => T + + val z3: Stringly[Boolean] = implicitly[String].length >= 2 + assert(z3) + + type GenericImplicit[X] = implicit X => Boolean + + val z4: GenericImplicit[String] = implicitly[String].length >= 2 + assert(z4) + + val b = x("hello") + + val b1: Boolean = b + + val bi = x + + val bi1: Boolean = bi + + val c = xx("hh", 22) + + val c1: Int = c + + Contextual.main(args) + + def foo(s: String): Stringly[Int] = 42 + + (if ("".isEmpty) foo("") else foo("")).apply("") + } +} + +object Contextual { + + class Key[+V] + + class Context(bindings: Map[Key[Any], Any]) { + def binding[V](key: Key[V]): Option[V] = + bindings.get(key).asInstanceOf[Option[V]] + def withBinding[V](key: Key[V], value: V): Context = + new Context(bindings + ((key, value))) + } + + val rootContext = new Context(Map()) + + val Source = new Key[String] + val Options = new Key[List[String]] + + type Ctx[T] = implicit Context => T + + def ctx: Ctx[Context] = implicitly[Context] + + def compile(s: String): Ctx[Boolean] = + runOn(new java.io.File(s))(ctx.withBinding(Source, s)) >= 0 + + def runOn(f: java.io.File): Ctx[Int] = { + val options = List("-verbose", "-explaintypes") + process(f).apply(ctx.withBinding(Options, options)) + } + + def process(f: java.io.File): Ctx[Int] = + ctx.binding(Source).get.length - ctx.binding(Options).get.length + + def main(args: Array[String]) = { + implicit val context: Context = rootContext + assert(compile("abc")) + assert(compile("ab")) + assert(!compile("a")) + } +} + +import collection.mutable.ListBuffer + +class Transaction { + private val log = new ListBuffer[String] + def println(s: String): Unit = log += s + + private var aborted = false + private var committed = false + + def abort(): Unit = { aborted = true } + def isAborted = aborted + + def commit(): Unit = + if (!aborted && !committed) { + Console.println("******* log ********") + log.foreach(Console.println) + committed = true + } +} + +object TransactionalExplicit { + + def transaction[T](op: Transaction => T) = { + val trans: Transaction = new Transaction + op(trans) + trans.commit() + } + + def f1(x: Int)(implicit thisTransaction: Transaction): Int = { + thisTransaction.println(s"first step: $x") + f2(x + 1) + } + def f2(x: Int)(implicit thisTransaction: Transaction): Int = { + thisTransaction.println(s"second step: $x") + f3(x * x) + } + def f3(x: Int)(implicit thisTransaction: Transaction): Int = { + thisTransaction.println(s"third step: $x") + if (x % 2 != 0) thisTransaction.abort() + x + } + + def main(args: Array[String]) = { + transaction { + implicit thisTransaction => + val res = f1(args.length) + println(if (thisTransaction.isAborted) "aborted" else s"result: $res") + } + } +} + +object Transactional { + type Transactional[T] = implicit Transaction => T + + def transaction[T](op: Transactional[T]) = { + implicit val trans: Transaction = new Transaction + op + trans.commit() + } + + def thisTransaction: Transactional[Transaction] = implicitly[Transaction] + + def f1(x: Int): Transactional[Int] = { + thisTransaction.println(s"first step: $x") + f2(x + 1) + } + def f2(x: Int): Transactional[Int] = { + thisTransaction.println(s"second step: $x") + f3(x * x) + } + def f3(x: Int): Transactional[Int] = { + thisTransaction.println(s"third step: $x") + if (x % 2 != 0) thisTransaction.abort() + x + } + + def main(args: Array[String]) = { + transaction { + val res = f1(args.length) + println(if (thisTransaction.isAborted) "aborted" else s"result: $res") + } + } +} + +object TransactionalExpansion { + + def transaction[T](op: Transaction => T) = { + val trans: Transaction = new Transaction + op.apply(trans) + trans.commit() + } + + def thisTransaction = $t: Transaction => $t + + def f1(x: Int) = { $t: Transaction => + thisTransaction.apply($t).println(s"first step: $x") + f2(x + 1).apply($t) + } + def f2(x: Int) = { $t: Transaction => + thisTransaction.apply($t).println(s"second step: $x") + f3(x * x).apply($t) + } + def f3(x: Int) = { $t: Transaction => + thisTransaction.apply($t).println(s"third step: $x") + if (x % 2 != 0) thisTransaction.apply($t).abort() + x + } + + def main(args: Array[String]) = { + transaction { $t => + val res = f1(args.length).apply($t) + println(if (thisTransaction.apply($t).isAborted) "aborted" else s"result: $res") + } + } +} + +object TransactionalAbstracted { + type Transactional[T] = implicit Transaction => T + + trait TransOps { + def thisTransaction: Transactional[Transaction] + def f1(x: Int): Transactional[Int] + def f2(x: Int): Transactional[Int] + def f3(x: Int): Transactional[Int] + } + + object TransOpsObj extends TransOps { + + def thisTransaction: Transactional[Transaction] = implicitly[Transaction] + + def f1(x: Int): Transactional[Int] = { + thisTransaction.println(s"first step: $x") + f2(x + 1) + } + def f2(x: Int): Transactional[Int] = { + thisTransaction.println(s"second step: $x") + f3(x * x) + } + def f3(x: Int): Transactional[Int] = { + thisTransaction.println(s"third step: $x") + if (x % 2 != 0) thisTransaction.abort() + x + } + } + + val transOps: TransOps = TransOpsObj + + def transaction[T](op: Transactional[T]) = { + implicit val trans: Transaction = new Transaction + op + trans.commit() + } + + def main(args: Array[String]) = { + transaction { + val res = transOps.f1(args.length) + println(if (transOps.thisTransaction.isAborted) "aborted" else s"result: $res") + } + } +} |