Missing implicits when attempting to derive encoder/decoder for generic sealed trait

Question

I am having problems with the following:

sealed trait Expression[T] {
  def doSomething: Either[String, T]
}

case class Literal(s: String) extends Expression[String] {
  def soSomething = Right(s)
}

object Expression{
  implicit def encoder[T: Encoder]: Encoder[Expression[T]]
  implicit def decoder[T: Decoder]: Decoder[Expression[T]]
}

I see the several errors:

could not find lazy implicit value of type io.circe.generic.extras.decoding.ConfiguredDecoder[Expression[T]]

not enough arguments for method deriveDecoder: (implicit decode: shapeless.Lazy[ConfiguredDecoder[Expression[T]]])

Obviously I am missing an implicit but cant see what I have missed from the circe examples I have followed.

Could anyone help or point me at a better way of doing this?

Cheers

Terry

EDIT

The solution provided below worked great but I am extending the ADT to cover further cases - I cannot get the following to compile:

case class Equals[F[_] <: Expression[_], T](left: F[T], right: F[T]) extends Expression[Boolean]{
  def doIt: Either[String, Boolean] = ???
}

object Equals {
  implicit def encoder[F[_] <: Expression[_], T](implicit FT: encoder[F[T]]): Encoder[Equals[F, T]] = deriveEncoder
}

I suspect I am not picking up the implicit Encoder for Expression[_] I have tried importing this in the Equals object but that does not help. Any further advice would help including advice how to debug these issues.

Answer 1

The implicits

implicit def encoder[T: Encoder]: Encoder[Expression[T]]
implicit def decoder[T: Decoder]: Decoder[Expression[T]]

mean that in order to generate codecs Circe must know what representation Expression[T] has for arbitrary T (and then to generate codecs for Expression[T] Circe can use codecs for children, codecs for T etc.). And what should the representation be?

implicitly[Generic.Aux[Expression[T], ???]]

(for simplicity I write Generic rather than LabelledGeneric).

Expression[String] has a child Literal, so

implicitly[Generic.Aux[Expression[String], Literal :+: CNil]]

But e.g. Expression[Int] doesn't have children

implicitly[Generic[Expression[Int]]] // doesn't compile, although I guess it could be: Generic.Aux[Expression[Int], CNil]

You just know that

implicitly[Generic.Aux[Expression[_], Literal :+: CNil]]

So try unconditional implicits (and implicits for existential if you need)

object Literal {
  implicit val encoder: Encoder[Literal] = deriveEncoder
  implicit val decoder: Decoder[Literal] = deriveDecoder
}

// optional, you can remove this if you don't need decode[Expression[_]]("...")
trait LowPriorityExpression {
  implicit def encoder1 : Encoder[Expression[_]] = deriveEncoder
  implicit def decoder1: Decoder[Expression[_]] = deriveDecoder
}

object Expression extends LowPriorityExpression {
  implicit def encoder: Encoder[Expression[String]] = deriveEncoder
  implicit def decoder: Decoder[Expression[String]] = deriveDecoder
}

Then

Literal("abc").asJson.noSpaces //{"s":"abc"}
(Literal("abc"): Expression[String]).asJson.noSpaces //{"Literal":{"s":"abc"}}
// (Literal("abc"): Expression[_]).asJson.noSpaces // doesn't compile without io.circe.generic.auto._

decode[Literal]("""{"s":"abc"}""") // Right(Literal(abc))
decode[Expression[String]]("""{"Literal":{"s":"abc"}}""") // Right(Literal(abc))
decode[Expression[_]]("""{"Literal":{"s":"abc"}}""") // Right(Literal(abc))
// decode[Expression[Int]]("""{"Literal":{"s":"abc"}}""") // doesn't compile, expected

See also

How to use circe with generic case class that extends a sealed trait

https://github.com/circe/circe/issues/1353

---

I noticed that with auto insted of semiauto codecs for Expression[T] are resolved a little better. So I looked with reify how they are resolved and defined these codecs manually. So we are not using now auto approach, we are using semiauto approach and re-using some of auto functionality explicitly in one place.

import io.circe.generic.encoding.DerivedAsObjectEncoder
import io.circe.generic.semiauto
import io.circe.generic.auto
import io.circe.generic.decoding.DerivedDecoder
import io.circe.{Decoder, Encoder}

sealed trait Expression[T] {
  def doSomething: Either[String, T]
}

case class Literal(s: String) extends Expression[String] {
  override def doSomething: Either[String, String] = Right(s)
}
object Literal {
  implicit val encoder: Encoder[Literal] = semiauto.deriveEncoder
  implicit val decoder: Decoder[Literal] = semiauto.deriveDecoder
}

case class Literal1(i: Int) extends Expression[Int] {
  override def doSomething: Either[String, Int] = Right(i)
}
object Literal1 {
  implicit val encoder: Encoder[Literal1] = semiauto.deriveEncoder
  implicit val decoder: Decoder[Literal1] = semiauto.deriveDecoder
}

case class Literal2[T](t: T) extends Expression[T] {
  override def doSomething: Either[String, T] = Right(t)
}
object Literal2 {
  implicit def encoder[T: Encoder]: Encoder[Literal2[T]] = semiauto.deriveEncoder
  implicit def decoder[T: Decoder]: Decoder[Literal2[T]] = semiauto.deriveDecoder
}

case class Equals[F[_] <: Expression[_], T](left: F[T], right: F[T]) extends Expression[Boolean] {
  override def doSomething: Either[String, Boolean] = ???
}
object Equals {
  implicit def encoder[F[_] <: Expression[_], T](implicit 
    FT: Encoder[F[T]]
  ): Encoder[Equals[F, T]] = semiauto.deriveEncoder
  implicit def decoder[F[_] <: Expression[_], T](implicit 
    FT: Decoder[F[T]]
  ): Decoder[Equals[F, T]] = semiauto.deriveDecoder
}

object Expression {
  implicit def encoder[T](implicit
    ev: DerivedAsObjectEncoder[Expression[T]]
  ): Encoder[Expression[T]] = Encoder.importedEncoder(auto.exportEncoder)
  implicit def decoder[T](implicit
    ev: DerivedDecoder[Expression[T]]
  ): Decoder[Expression[T]] = Decoder.importedDecoder(auto.exportDecoder)
}

// everything compiles
implicitly[Encoder[Literal]]
implicitly[Decoder[Literal]]
implicitly[Encoder[Literal1]]
implicitly[Decoder[Literal1]]
implicitly[Encoder[Expression[String]]]
implicitly[Encoder[Expression[Int]]]
implicitly[Decoder[Expression[String]]]
implicitly[Decoder[Expression[Int]]]
implicitly[Encoder[Equals[Expression, Int]]]
implicitly[Encoder[Equals[Expression, String]]]
implicitly[Decoder[Equals[Expression, Int]]]
implicitly[Decoder[Equals[Expression, String]]]
implicitly[Encoder[Equals[Literal2, Int]]]
implicitly[Encoder[Equals[Literal2, String]]]
implicitly[Decoder[Equals[Literal2, Int]]]
implicitly[Decoder[Equals[Literal2, String]]]

But implicitly[Decoder[Expression[Boolean]]] and implicitly[Encoder[Expression[Boolean]]] still don't compile even with auto. I'm afraid we come here to the limits of Scala 2 type system (and Shapeless 2).

import shapeless.{Generic, :+:, CNil, Generic1, the}
implicitly[Generic.Aux[Expression[String], Literal :+: Literal2[String] :+: CNil]]
implicitly[Generic.Aux[Expression[Int], Literal1 :+: Literal2[Int] :+: CNil]]
//implicitly[Generic[Expression[Boolean]] // doesn't compile
//implicitly[Generic[Expression[_]]] // doesn't compile
  //kinds of the type arguments (F[_],T) do not conform to the expected 
  //kinds of the type parameters (type F,type T) in class Equals.
  //F[_]'s type parameters do not match type F's expected parameters:
  //type F has 1 type parameter, but type F has 1
type T
implicitly[Generic.Aux[Expression[T], Literal2[T] :+: CNil]]
trait Always[F[_]]
object Always {
  implicit def mkAlways[F[_]]: Always[F] = new Always[F] {}
}
val gen = the[Generic1[Expression, Always]]
implicitly[gen.R[T] =:= (Literal2[T] :+: CNil)]

What could the representation of Expression[Boolean] be?

implicitly[Generic.Aux[Expression[Boolean], ???]]

Should it be (Equals[F, _] forSome {type F[_]}) :: Literal2[Boolean] :+: CNil?

Or Equals[λ[T => Expression[_]], _] :: Literal2[Boolean] :+: CNil

aka Equals[({type λ[_] = Expression[_]})#λ, _] :: Literal2[Boolean] :+: CNil?

In Scala 3 it's

(Literal, Literal1, Literal2[Boolean], Equals[[_] =>> Expression[?], Any])

aka Literal *: Literal1 *: Literal2[Boolean] *: Equals[[_] =>> Expression[?], Any] *: EmptyTuple

import scala.deriving.*
val exprStrMirror = summon[Mirror.SumOf[Expression[String]]]
summon[exprStrMirror.MirroredElemTypes =:= (Literal, Literal1, Literal2[String], Equals[[_] =>> Expression[?], Any])]
val exprIntMirror = summon[Mirror.SumOf[Expression[Int]]]
summon[exprIntMirror.MirroredElemTypes =:= (Literal, Literal1, Literal2[Int], Equals[[_] =>> Expression[?], Any])]
val exprBoolMirror = summon[Mirror.SumOf[Expression[Boolean]]]
summon[exprBoolMirror.MirroredElemTypes =:= (Literal, Literal1, Literal2[Boolean], Equals[[_] =>> Expression[?], Any])]
type SumOfK1[F[_]] = Mirror.Sum { type MirroredType[T] = F[T] }
val exprMirror = summon[SumOfK1[Expression]]
summon[exprMirror.MirroredElemTypes[T] =:= (Literal, Literal1, Literal2[T], Equals[[_] =>> Expression[?], Any])]

https://scastie.scala-lang.org/DmytroMitin/jrkBc5lkS1KDQO2U6uMt3Q/1

---

Actually, it's funny. If we have at least one generic case class (Literal2[T]) then the original code compiles (probably my manual codecs stolen from auto were incorrect in some cases and also Circe rely not completely on Shapeless represenations)

https://scastie.scala-lang.org/DmytroMitin/m7QZp29yQ3CLeQjOnm3Avw

If we remove the generic case class the code doesn't compile

https://scastie.scala-lang.org/DmytroMitin/m7QZp29yQ3CLeQjOnm3Avw/2

import io.circe.generic.semiauto
import io.circe.{Decoder, Encoder}

sealed trait Expression[T] {
  def doSomething: Either[String, T]
}

case class Literal(s: String) extends Expression[String] {
  override def doSomething: Either[String, String] = Right(s)
}
object Literal {
  implicit val encoder: Encoder[Literal] = semiauto.deriveEncoder
  implicit val decoder: Decoder[Literal] = semiauto.deriveDecoder
}

// !!!
case class Literal2[T](t: T) extends Expression[T] {
  override def doSomething: Either[String, T] = Right(t)
}
object Literal2 {
  implicit def encoder[T: Encoder]: Encoder[Literal2[T]] = semiauto.deriveEncoder
  implicit def decoder[T: Decoder]: Decoder[Literal2[T]] = semiauto.deriveDecoder
}

case class Equals[F[_] <: Expression[_], T](left: F[T], right: F[T]) extends Expression[Boolean] {
  override def doSomething: Either[String, Boolean] = ???
}
object Equals {
  implicit def encoder[F[_] <: Expression[_], T](implicit FT: Encoder[F[T]]): Encoder[Equals[F, T]] = semiauto.deriveEncoder
  implicit def decoder[F[_] <: Expression[_], T](implicit FT: Decoder[F[T]]): Decoder[Equals[F, T]] = semiauto.deriveDecoder
}

object Expression {
  implicit def decoder[T: Decoder]: Decoder[Expression[T]] = semiauto.deriveDecoder
  implicit def encoder[T: Encoder]: Encoder[Expression[T]] = semiauto.deriveEncoder
}

implicitly[Encoder[Literal]]
implicitly[Decoder[Literal]]
implicitly[Encoder[Expression[String]]]
implicitly[Encoder[Expression[Int]]]
implicitly[Decoder[Expression[String]]]
implicitly[Decoder[Expression[Int]]]
implicitly[Encoder[Equals[Expression, Int]]]
implicitly[Encoder[Equals[Expression, String]]]
implicitly[Decoder[Equals[Expression, Int]]]
implicitly[Decoder[Equals[Expression, String]]]
implicitly[Encoder[Equals[Literal2, Int]]]
implicitly[Encoder[Equals[Literal2, String]]]
implicitly[Decoder[Equals[Literal2, Int]]]
implicitly[Decoder[Equals[Literal2, String]]]
implicitly[Encoder[Expression[Boolean]]]
implicitly[Decoder[Expression[Boolean]]]

(Let's call this code (*) for the below purpose.)

---

I removed temporarily all macros but one and with -Ymacro-debug-lite, -Xlog-implicits switched on it produces macro expansion has failed: Sealed trait Expression[T] has no case class subtypes so obviously it's a Circe bug

import io.circe.generic.semiauto
import io.circe.{Decoder, Encoder}

sealed trait Expression[T] {
  def doSomething: Either[String, T]
}

case class Literal(s: String) extends Expression[String] {
  override def doSomething: Either[String, String] = Right(s)
}
object Literal {
  implicit val encoder: Encoder[Literal] = Encoder.forProduct1("s")(_.s)
  implicit val decoder: Decoder[Literal] = Decoder.forProduct1("s")(Literal.apply)
}

case class Equals[F[_] <: Expression[_], T](left: F[T], right: F[T]) extends Expression[Boolean] {
  override def doSomething: Either[String, Boolean] = ???
}
object Equals {
  implicit def encoder[F[_] <: Expression[_], T](implicit FT: Encoder[F[T]]): Encoder[Equals[F, T]] =
    Encoder.forProduct2("left", "right")(e => (e.left, e.right))
  implicit def decoder[F[_] <: Expression[_], T](implicit FT: Decoder[F[T]]): Decoder[Equals[F, T]] =
    Decoder.forProduct2("left", "right")(Equals.apply _)
}

object Expression {
  implicit def decoder[T: Decoder]: Decoder[Expression[T]] = semiauto.deriveDecoder[Expression[T]] /*!!!*/
  // implicit def encoder[T: Encoder]: Encoder[Expression[T]] = semiauto.deriveEncoder
}

---

Actually, Sealed trait Expression[T] has no case class subtypes comes from Shapeless

sealed trait Expression[T]
case class Literal(s: String) extends Expression[String]
// case class Literal2[T](t: T) extends Expression[T]
case class Equals[F[_] <: Expression[_], T](left: F[T], right: F[T]) extends Expression[Boolean]

type T
implicitly[Generic[Expression[T]]]//macro expansion has failed: Sealed trait Expression[T] has no case class subtypes

The reasons are the same

sealed trait Expression[T]
case class Literal(s: String) extends Expression[String]
case class Literal2[T](t: T) extends Expression[T]
case class Equals[F[_] <: Expression[_], T](left: F[T], right: F[T]) extends Expression[Boolean]

implicitly[Generic.Aux[Expression[String], Literal :+: Literal2[String] :+: CNil]]
// implicitly[Generic[Expression[Boolean]]] // doesn't compile, kinds of the type arguments (F[_],T) do not conform to the expected kinds of the type parameters (type F,type T) in class Equals. F[_]'s type parameters do not match type F's expected parameters: type F has 1 type parameter, but type F has 1
type T
implicitly[Generic.Aux[Expression[T], Literal2[T] :+: CNil]]

Shapeless thinks that representation of Expression[T] is Literal2[T] :+: CNil (and doesn't include Literal and Equals) and without Literal2 the representation is empty.

Actually, it's not so good that Shapeless doesn't include Literal and Equals into the representation of Expression[T]. Although the code (*) above compiles, it fails at runtime (throws exception MatchError or produces Left)

Literal("a").asJson.noSpaces
Literal2[Int](1).asJson.noSpaces
Equals[Literal2, Boolean](Literal2(true), Literal2(false)).asJson.noSpaces
//(Literal("a"): Expression[String]).asJson.noSpaces//MatchError
(Literal2[Int](1): Expression[Int]).asJson.noSpaces
//(Equals[Literal2, Boolean](Literal2(true), Literal2(false)): Expression[Boolean]).asJson.noSpaces//MatchError

decode[Literal]("""{"s":"a"}""")
decode[Literal2[Int]]("""{"t":1}""")
decode[Equals[Literal2, Boolean]]("""{"left":{"t":true},"right":{"t":false}}""")
decode[Expression[String]]("""{"Literal":{"s":"a"}}""")//Left, CNil should never happen
decode[Expression[Int]]("""{"Literal2":{"t":1}}""")
decode[Expression[Boolean]]("""{"Equals":{"left":{"Literal2":{"t":true}},"right":{"Literal2":{"t":false}}}}""")//Left, CNil should never happen

https://scastie.scala-lang.org/DmytroMitin/m7QZp29yQ3CLeQjOnm3Avw/4

A workaround is to define codecs for Expression[T] manually

implicit def decoder[T: Decoder]: Decoder[Expression[T]] = Decoder.instance {
  def readExpr(c: HCursor): Result[Expression[T]] =
    c.get[Literal]("Literal").asInstanceOf[Result[Expression[T]]].orElse(
      c.get[Literal2[T]]("Literal2").orElse {
        def readEquals(fieldName: String): Result[Expression[T]] =
          c.downField("Equals")
           .downField(fieldName)
           .success
           .toRight(DecodingFailure(Reason.CustomReason(s"can't read Equals.$fieldName"), c))
           .flatMap(readExpr)

        for {
          l <- readEquals("left")
          r <- readEquals("right")
        } yield new Equals(l, r).asInstanceOf[Expression[T]]
      }
    )

  readExpr
}

implicit def encoder[T: Encoder]: Encoder[Expression[T]] = Encoder.instance {
  case expr@Literal(_) => Json.obj("Literal" -> expr.asJson)
  case expr@Literal2(_) => Json.obj("Literal2" -> expr.asJson)
  case Equals(l, r) => Json.obj("Equals" -> 
    Json.obj(
      "left"  -> l.asInstanceOf[Expression[T]].asJson, 
      "right" -> r.asInstanceOf[Expression[T]].asJson
    )
  )
}

https://scastie.scala-lang.org/DmytroMitin/m7QZp29yQ3CLeQjOnm3Avw/8

---

I understood how to fix issues with failing at runtime (throwing MatchError or producing Left). We should replace

object Expression {
  implicit def decoder[T: Decoder]: Decoder[Expression[T]] = semiauto.deriveDecoder
  implicit def encoder[T: Encoder]: Encoder[Expression[T]] = semiauto.deriveEncoder
}

with

object Expression {
  implicit def decoder[T](implicit 
    ev: DerivedDecoder[Expression[T]]
  ): Decoder[Expression[T]] = semiauto.deriveDecoder /*ev*/
  implicit def encoder[T](implicit
    ev: DerivedAsObjectEncoder[Expression[T]]
  ): Encoder[Expression[T]] = semiauto.deriveEncoder /*ev*/
}

I just added the implicit parameters DerivedDecoder[Expression[T]]/ DerivedAsObjectEncoder[Expression[T]] of semiauto.deriveDecoder/deriveEncoder to def decoder[T]/def encoder[T]. Formerly these implicit parameters were resolved here, at the definition site of def decoder[T], def encoder[T] i.e. for generic T the representation of Expression[T] was Literal2[T] :+: CNil and this failed for Literal. Now these implicit parameters will be resolved at the call site of def decoder[T], def encoder[T] i.e. for T=String the representation of Expression[String] will be Literal :+: Literal2[String] :+: CNil. (This is similar to the difference implicitly[X] vs. (implicit x: X).)

(I guess it would be better if in Circe semiauto.deriveDecoder/deriveEncoder were macros making a user add the implicit parameters to the method when necessary.)

The question remains with type F has 1 type parameter, but type F has 1 i.e. Boolean case.

https://scastie.scala-lang.org/DmytroMitin/m7QZp29yQ3CLeQjOnm3Avw/11

---

I suspect that Shapeless calculates Generic for Expression[Boolean] incorrectly so that there are invalid Equals[_[_] <: Expression[_], _] in the represenation Equals[_[_] <: Expression[_], _] :+: Literal2[Boolean] :+: CNil and Generic instance

//  Generic.instance[Expression[Boolean], Equals[_[_] <: Expression[_], _] :+: Literal2[Boolean] :+: CNil](((p: Expression[Boolean]) => Coproduct.unsafeMkCoproduct(p: @_root_.scala.unchecked match {
//    case (_: Equals[_[_] <: Expression[_], _]) => 0
//    case (_: Literal2[Boolean]) => 1
//  }, p).asInstanceOf[Equals[_[_] <: Expression[_], _] :+: Literal2[Boolean] :+: CNil]), ((x1) => Coproduct.unsafeGet(x1).asInstanceOf[Expression[Boolean]]))

But even if we fix Generic so that it will produce for example Equals2 :+: Literal2[Boolean] :+: CNil

type Equals2 = Equals[F, _] forSome {type F[_] <: Expression[_]}
// type Equals2 = Equals[Const[Expression[_]]#λ, _]

implicit val boolExprGeneric: Generic.Aux[Expression[Boolean], Equals2 :+: Literal2[Boolean] :+: CNil] =
  Generic.instance[Expression[Boolean], Equals2 :+: Literal2[Boolean] :+: CNil](
    (p: Expression[Boolean]) => Coproduct.unsafeMkCoproduct(
      (p: @unchecked) match {
        case _: Equals2           => 0
        case _: Literal2[Boolean] => 1
      },
      p
    ).asInstanceOf[Equals2 :+: Literal2[Boolean] :+: CNil],
    x => Coproduct.unsafeGet(x).asInstanceOf[Expression[Boolean]]
  )

how will we define instances of Encoder/Decoder for existential Equals2?