Proposal: Add Expr.summonIgnoring method to use in macros

[jchyb]

Motivation:

Typeclass derivation libraries have long been using the implicit resolution feature in scala. It:

1. allows for easier developer experience where derivation library designers are able compose calls recursively (as part of the automatic derivation with mirrors, libraries like shapeless, etc.)
2. can allow library users to easily define additional given typeclasses used in the derivation.

Auto derivation can be also implemented using macros, with the main benefit being added performance (at the cost of more difficult library developer experience compared to using the usual shapeless/mirror use), and more control over the generated typeclasses. An issue arises when we want to mix that benefit of gained performance with the ability for users do define those additional typeclasses. Since it is currently impossible to disallow recursive summons we cannot first check on the existence of a user defined given typeclass and then create it, if necessary, as part of the same macro call, we have to structure like we would mirror-based or shapeless-based macro derivation, where we end up with macro methods expanding macro methods as part of their derivation.

However that approach can worsen performance:

• We end up with recursively calling macro methods from macro methods which is costly on compiletime.
• We end up with wasteful allocations in the generated runtime code (generated typeclasses using generated typeclasses using generated typeclasses etc.)
• We will not obtain the full tree of the summoned given (just a val), meaning we cannot do any further optimizations on it.

Workarounds

There historically existed few workarounds for this, some of which we can no longer use:

• Scala 2 could achieve something like this with its inferImplicitValue(https://www.scala-lang.org/api/2.13.2/scala-reflect/scala/reflect/macros/Typers.html#openMacros:List[scala.reflect.macros.blackbox.Context]) method it had as part of its API. That method, used similarly to Expr.summon in macros, had an argument withMacrosDisabled: Boolean which would naturally guard against recursive macro calls, although disallowing other possible functionality with it.

• Another workaround for this was via assigning a different type to a TypeClass obtained from macro (found and used in the chimney library). However, this stopped working with the recent changes to given prioritization, where the following issue can occur:

trait Transformer[From, To] extends Transformer.AutoDerived[From, To]{ // user defined
  def transform(from: From): To
}
object Transformer {
  trait AutoDerived[From, To] { // returned by macro
    def transform(src: From): To
  }
  // macro call
  implicit transparent inline def auto[From, To]: Transformer.AutoDerived[From, To] =
    // in this method we can search for Transformer[_, _], effectively disallowing recursive macro expansions  
    new Transformer.AutoDerived[From, To]{
      def transform(from: From) = ???
    }
  def define[From, To](fun: From => To): Transformer[From, To] =
    new Transformer[From, To]{
      def transform(from: From) = fun(from)
    }
}

case class Foo(a: Int, b: String)
case class Bar(a: Int, b: String)
object Foo {
  given totalTransformer: Transformer[Foo, Bar] = Transformer.define[Foo, Bar](a => Bar(a.a, a.b))
}
extension [From](from: From) def transformInto[To](using t: Transformer.AutoDerived[From, To]): To = t.transform(from)

@main def main() = {
  println(Foo(1, "value").transformInto[Bar])
}

Here we have a Transformer (user defined typeclass) and Transformer.AutoDerived (returned by a macro). This way we are able to summon user defined typeclass in the macro method without rerunning the macro method again. With given prioritization changes introduced in 3.7.0 the compiler will starts seeing those 2 as ambiguous. It seems like this can be worked around again by adding a call to summonFrom in inlined transformInto, continuing the game of cat and mouse until another change/bugfix to implicit resolution.

Proposal

The proposal here is about having an officially sanctioned way of achieving the same result as the above workarounds:

// In Expr.scala
def summonIgnoring[T](using Type[T])(using quotes: Quotes)(ignoredSymbols: quotes.reflect.Symbol): Option[Expr[T]]

Where in addition to the searched type, we can pass symbols which will not be used as part of the implicit search, with the main use case being disallowing recursive macro expansion.

[jchyb]

Prototype implementation: jchyb@d97ec4e

[SethTisue]

fyi @arainko (not sure if relevant, but just in case...)

[MateuszKubuszok]

We were talking about, @ahoy-jon, so this might interest you as well :)

I'd love to have this and something like this in 2.13

[ahoy-jon]

Indeed, that would be great, I am genuinely interested. This proposition could help a lot!

[prolativ]

Speaking of the workaround, wouldn't this keep working with the new implicit search rules if we get rid of the inheritance relation between Transformer and AutoDerived? E.g.

trait Transformer[From, To]:
  def transform(from: From): To

object Transformer:
  opaque type AutoDerived[From, To] = Transformer[From, To]

  object AutoDerived:
    inline given auto[From, To]: Transformer.AutoDerived[From, To] =
      // in this method we can search for Transformer[_, _], effectively disallowing recursive macro expansions  
      new Transformer[From, To]:
        def transform(from: From): To = ???
    
  inline given fromAuto[From, To](using a: AutoDerived[From, To]): Transformer[From, To] = a

  def define[From, To](fun: From => To): Transformer[From, To] =
    new Transformer[From, To]:
      def transform(from: From) = fun(from)

extension [From](from: From) def transformInto[To](using t: Transformer[From, To]): To = t.transform(from)

case class Foo(a: Int, b: String)
object Foo {
  given totalTransformer: Transformer[Foo, Bar] = Transformer.define[Foo, Bar](foo => Bar(foo.a, foo.b))
}
case class Bar(a: Int, b: String)
case class Baz(a: Int, b: String)

@main def main() = {
  println(summon[Transformer.AutoDerived[Foo, Bar]])
  println(summon[Transformer[Foo, Bar]])
  println(summon[Transformer.AutoDerived[Foo, Baz]])
  println(summon[Transformer[Foo, Baz]])
}

[MateuszKubuszok]

This (or other) workaround is necessary because there is no summonIgnoring - if we remove it Chimney will end up with suboptimal code generation: longer compilation times and less performant code. Vide: https://www.youtube.com/watch?v=scWvlO_fb78 .

We didn't introduce this split hierarchy for fun, it's a leaky implementation detail from solution of the issues I described in the presentation. I'd be happy to get rid of it (and have only Transformer and inline given derived[From, To] which could be used both for auto and semi), but without summonIgnoring or similar there is no replacement.

EDIT: Oh, and I also forgot about errors: if I cannot make the derivation recursive in a single macro expansion (because for every summon it would call another macro expansion) the ability to aggregate nested errors is lost as well, soo... extreme degradation in quality.

[odersky]

Does this affect regular code using derives clauses in classes, or is this only an issue when we generate givens outside that mechanism? I am asking because derives naturally caches and re-use things, but by-hand given generation might well not do that.

[lbialy]

Mateusz prepared benchmarks if you are willing to investigate: https://github.com/MateuszKubuszok/derivation-benchmarks

Why can't jsoniter/chimney full-tree macro be faster? (it is, in both runtime and compile time). There's a lot of work that compiler has to do with shapeless approach which is doing everything on type level with implicits while a macro happily traverses the whole tree in a single piece of code and only interacts with compiler when triggering implicit search to find user-provided instances. It never triggers itself so there are no recursive macro expansions.

Miles' caching improvements from Scala 2.13 seem to be missing in dotty so auto mode using Mirrors in Scala 3 is veeeery slow - it's the circe generic auto and circe magnolia auto in Scala 3, derives / semi-automatic looks pretty good on the other hand (as expected).

                     Scala 2   Scala 3  Units
compilation of      cold hot  cold hot
circeGenericAuto      14   4    46  16      s
circeGenericSemi      12   3    10   1      s
circeMagnoliaAuto     13   2    65  32      s
circeMagnoliaSemi     12   7    12   2      s
jsoniterScalaSanely    -   -     9   1      s
jsoniterScalaSemi     10   4     8   1      s

This table is quite telling - circe generic semi is equivalent to derives and it's doing quite well but jsoniter is doing just as well and is massively faster in runtime. What is really interesting is that sanely-automatic (only done for Dotty) is basically equally fast as semi-automatic jsoniter (makes sense, it's a very thin wrapper).

[lbialy]

Just to clarify further which pieces of code are roughly equivalent to each other:

circe with semi-automatic derivation (circe generic semi) - these implicits would land in companion objects with derives so this represent derives like approach: https://github.com/MateuszKubuszok/derivation-benchmarks/blob/master/circe-generic-semi/src/main/scala/example/CirceGenericSemi.scala
and here's how this is implemented in circe: https://github.com/circe/circe/blob/series/0.14.x/modules/generic/shared/src/main/scala-3/io/circe/generic/semiauto.scala

jsoniter-scala with semi-automatic full tree recursive derivation (jsoniter scala semi) - single typeclass instance derived, all instances are inlined as methods in that single instance https://github.com/MateuszKubuszok/derivation-benchmarks/blob/master/jsoniter-scala-semi/src/main/scala/example/JsoniterScalaSemi.scala

jsoniter-scala with Mateusz's sanely-automatic full tree recursive derivation - no manual typeclass derivation at all: https://github.com/MateuszKubuszok/derivation-benchmarks/blob/master/jsoniter-scala-sanely/src/main/scala-3/example/JsoniterScalaSanely.scala
the wrapper is this thing https://github.com/MateuszKubuszok/derivation-benchmarks/blob/master/jsoniter-scala-wrapper/src/main/scala-3/example/jsonitersanely/JsonCodec.scala and this is exactly what this proposal is trying to address - in Scala pre-3.7 it requires a hierarchy for the derived typeclass so that it can always look for the subtype, Scala 3.7 breaks this as that search becomes ambiguous, this proposal allows to have just one typeclass trait without subtyping and use Expr.summonIgnoring[TC[A]](selfSymbol) to prevent recursive self-expansion.

[odersky]

Thanks for explaining. Yes, I see if one bypasses implicit search in a well-written macro that can be faster. But there's still the problem that the full tree will be generated on each call-site, potentially leading to a lot of code duplication, which in turn slows down compilation. How is that handled when there are multiple call sites of the macro?

[lbialy]

Once duplication becomes a compile-time problem it pays off to use derives/semi-auto for the nodes in the graph that recur between trees. Since semi-auto yields a user-defined typeclass instance it's always picked up as an overload and prohibits further traversal into that node. Effectively derives becomes an opt-in caching strategy.

After conversations with Mateusz I started to wonder if we could use tasty-query to find good candidates for which instance caching would bring large benefits.

[MateuszKubuszok]

I agree with what @lbialy said. Currently:

• derives is basically a nice syntactic sugar for semi-automatic derivation when we are able to put given in the companion object (not always the case)
• semi-automatic derivation is good choice when we want to enforce consistent behavior across the whole application... although it becomes a boilerplate if one's dominating use case are implicit derived and used only in a single place (especially if these implicits rely on customization provided via annotations or runtime config via another given), e.g.
  • e.g. Circe was using implicit Configuration to tell codecs how field names should have been converted (e.g. pascal-case to kebab-case, etc). To put these into companion object one needs to be able to put implicit Configuration in the scope of the companion object (defining it or importing) and also be able to edit case classes/enums
  • Jsoniter uses both annotations and config represented as erased value (e.g. JsonCodecMaker.make(CodecMakerConfig.withAllowRecursiveTypes(true).withJavaEnumValueNameMapper(...)) - expression CodecMakerConfig is parsed by macro so that in runtime no allocation actually happens, if there are some methods/lambdas defined, the code gets converted into straight method call)
    • Jsoniter makes it possible to user derives with it, although it requires defining inline ConfigMakerConfig
    • automatic derivation was never supported - because recursive derivation in a single macro is a big part of its success when it comes to the performance, and it's hard to keep that with automatic derivation
    • but lacking automatic derivation is arguably one of the reasons why its cannot gain wider adoption, as it makes the learning curve steeper
  • Chimney has the unique problem that it is a converter library, it always has 2 type parameters, so Shapeless or Mirrors would have to works with 2 lists of fields/subtypes, Magnolia does not handle such cases at all, and derives is not supporting such use cases
    • additionally, a lot of use cases is about recursive rewriting of case classes, that has to be done in a single place, possibly with customization:

      case class Foo[A](a: A)
      case class Bar(i: Int)
      case class Baz(i: Int, d: Double)
      
      import io.scalaland.chimney.dsl._
      Foo(Bar(10)).into[Foo[Baz]].withFieldConst(_.a.d, 20.0).transform

      which sabotages any attempt to handle it with derives (it is possible to use semi-automatic derivation, but user has to manually decide where to store it)
    • actually, there is another tricky thing in Chimney, as it supports transformations as both total functions, and partial functions (where mappings between all inputs and outputs is still done in compile time, but some conversions need to e.g. safely unwrap Option or call smart constructor, the different from PartialFunction is that it doesn't throw buy returns a Result that handles nulls, Nones, Eithers, exceptions, etc and aggregate errors with a path to field which failed ) an partial transformations allow users to override the internal mappings both Transformer[Source, Target] as well as PartialTransformer[Source, Target]. But it doesn't lift all values to Result imediatelly - we are trying to keep values unboxed as long ans possible, so internal exprs are trying to be of Target type rather than Result[Target] as long as possible, (it's possible to defer it even until we are just about to return the value from type class, although in such case user could probably just use a total Transformer). With a single recursive macro it is easy to achieve. But by creating intermediate instances, which override the behavior, we are forced to lift values much earlier, creating unnecessary intermediate allocations
    • since we managed to pull-off automatic derivation what works similar to Jsoniter's semi-automatic derivation, all the cases that do not require manual customization simply work out of the box, the compilation time is really nice, benchmarks show comparable performance to hand-written code and compilation errors messages are one of the best in the community.

The compile times and performance when one reuses type class is a valid concern, although I believe that it's a bit more complex than one-fit-all solution:

• the approach that is proposed does not prevent derives from being used in such case:

  package packagename
  
  trait TypeClass[A]
  object TypeClass extends TypeClassLowPriprityImplicits
  private[packagename] trait TypeClassLowPriprityImplicits {
    // uses Expr.summonIgnoring(Symbol for TypeClass.derived)
    inline given derived[A]: TypeClass[A] = ${ ... }
  }

  • this would provide implicit for any supported type OOTB
  • allow users to cache things in givens with TypeClass.derived[MyType]
  • cooperate with case class MyType() derives TypeClass

  so this is not incompatible with the approach proposed with derives - it supplements it, allowing users to user derives when they want, and use (much more convenient) automatic derivation for all these cases when they are not reusing the derived type classes

• if one derives the code for a deep nested hierarchy on one place, and then they share large part of its subtree in another deep nested hierarchy that derives code, obviously there will be a duplication of the effort of the compiler

• however, as noticed above, the users are still able to use derives for the shared part, and they would only have to use derives it the outermost type of the shared substree

  • additionally, as far as I could tell with some experiments, Shapeless/Mirrors/Magnolia relying on the type checker for every little thing, cause so much overhead and a macro (which only asks whether there is an implicit type class overridding something) might return so much quicker, that deriving the same code twice with macro, might take as much as deriving the code a single time with derives deferring to Mirrors. For complex cases automatic re-derivation of the same code with macros can become an issue much later than semi-automatic derivation with derives that uses Mirrors all the inline ops

• as for the runtime performance, it is important to mention that the code doesn't have to be naively inlined, e.g. what Jsoniter does looks more like this (:

  new TypeClass[MyType] {
    def method(value: A): Result = {
      // used build-ins
      def handle_string(str: String): Result = ...
      def handle_int(int: Int): Result = ...
      def handle_nested_type(nestedType: NestedType): Result = ...
      def handle_my_type(myType: MyType): Result = ...
      handle_my_type(value)
    }
  }

  and this approach:

  • would require instantiating and allocating only a single object (less important if all of them are cached, more when some of them has to be instantiated in place because of reasons)
  • calls methods inside the same instance
  • keep each such method reasonably small
  • allows handling recursion without instantiating a new object or some Lazy wrapper

  which helps JVM optimize the code much more than when it has a bunch of separate classes calling one another, probably in different places in memory. It isn't always the most optimal solution, I would never claim such things, but it's quite a good default, and one user can always opt-out just by defining an type class and putting it into implicit scope themselves (e.g. with derives).

As far as I can tell, there is nothing incompatible sanely-automatic derivation an:

• preferences to use derives for single-param type classes without customization
• semi-automatic derivation in general
• automatic derivation

It would allow users to keep their code as it is, just enabling some improvements by library authors when it comes to:

• automatic derivation

• performance optimization

• since it promotes macros it also allows better errors messages

• as a bonus, this approach - recursive derivation in a single macro - is currently the only one that without special cases or workarounds cooperates with:

  enum Foo derives TypeClass:
    case Bar(a: Int)
    case Baz(b: Int)