Support extending the AST for database specific query support, without losing sealed trait benefits.

[Jacoby6000]

I'm thinking that this can be done by adding in a "hole".

So, given this "base" ADT:

sealed trait ArithmeticOperationsADT[+A,+B]
case class Lit[+A](value: A) extends ArithmeticOperationsADT[A, Nothing]
case class Add[+A, +B](left: ArithmeticOperationsADT[A, B], right: ArithmeticOperationsADT[A, B]) extends ArithmeticOperationsADT[A, B]
case class Sub[+A, +B](left: ArithmeticOperationsADT[A, B], right: ArithmeticOperationsADT[A, B]) extends ArithmeticOperationsADT[A, B] 
case class Div[+A, +B](left: ArithmeticOperationsADT[A, B], right: ArithmeticOperationsADT[A, B]) extends ArithmeticOperationsADT[A, B] 
case class Mul[+A, +B](left: ArithmeticOperationsADT[A, B], right: ArithmeticOperationsADT[A, B]) extends ArithmeticOperationsADT[A, B]
case class ArithmeticOperationsADTExtensions[+B](b: B) extends ArithmeticOperationsADT[Nothing, B]

We can extend ArithmeticOperationsADT (which currently only supports arithmetic) to support more arithmetic operations like this:

sealed trait MoreOperationsADT[+A]
case class Pow[A](base: ArithmeticAndMoreADT[A], exponent: ArithmeticAndMoreADT[A]) extends MoreOperationsADT[A]
case class Root[A](base: ArithmeticAndMoreADT[A], nthRoot: ArithmeticAndMoreADT[A]) extends MoreOperationsADT[A]

type ArithmeticAndMoreADT[+A] = ArithmeticOperationsADT[A, MoreOperationsADT[A]]

Then, usage/construction of these ADTs might looks like

Add(Lit(5), Sub(Lit(6), ArithmeticOperationsADTExtensions(Pow(Lit(5),Lit(2)))))

Which would represent

5 + (6 - (5 ^ 2))

This scastie is an example of what a practical usage might be... This would obviously be much more complex in the context of scoobie.

This idea could be expanded further to support Coproduct extensions, which would allow extending a single ADT with multiple ADTs.

[Jacoby6000]

The above apporoach works fine for a simple ADT, not so much for an entire AST.

[Jacoby6000]

@edmundnoble, @bshelden, and @sellout helped me realize that I have a mutually recursive AST.

The solution to mutually recursive ASTs in general is to have something like below:

trait AST[A[_], I] // A represents additional AST nodes, and I is an Indexer which represents the type of node.

object Indicies {
  trait FooAST
  trait BarAST
}

case class FooAST[A[_]](subNode: A[Indicies.BarAST]) extends AST[A, Indicies.FooAST]
case class FooLeaf[A[_]](foo: Int) extends AST[A, Indicies.FooAST]
case class BarAST[A[_]](subNode: A[Indicies.FooAST]) extends AST[A, Indicies.BarAST]

In the end, you wind up employing the use of FixH

case class FixH[F[_[_], _], A](unfix: F[HFix[F, ?], A])

FixH is necessary to make the compiler happy with the recursive nature of mutually recursive ASTs.

Unfortunately, whenever you try to create an HFunctor, scalac has issues whenever you try to match on the higher order GADT. Scalac has a PR (scala/scala#5744) for these issues in review right now. There are just a couple of things to be worked out.

Once the new versions of Scala are out, the way this will wind up looking in Scoobie is something like

trait Query[T, A[_], I] // T represents the type on query parameters.  In the context of a doobie query, this will be [[doobie.imports.Fragment]]
object Indicies {
  trait Value
  trait Comparison
}

where all nodes extend Query[T, A[_], I].

Once all this is done, extending the AST should be as simple as using a Coproduct (or HCoproduct I think) in the A[_] position. Some work in this direction has been done on branch feature/#40-adjust-ast-to-support-fix-point.

Right now, that branch has it's own implementations of FixH (as HFix), HRecursive and HFunctor. Once slamdata/matryoshka#28 is merged, we can probably pull in matryoshka to do this for us... Though, I'm not sure if that would be worth doing yet. Right now I think I'm going to have it manually implemented, and then have a shims layer of sorts to support their abstractions as well.

The above is just my understanding of the issue currently. Things up there might be wrong, and the approach to solving this in the end might change.

[Jacoby6000]

Making lots of progress on this. Got the DSL functioning with the new Query[T, A[_] I] format. All that's left in the branch is to make the old interpreters work and it'll have parity with what is currently existing. From there, I'd like to do a POC for extending the AST before publishing a 1.0.0 snapshot.

[Jacoby6000]

The dotty branch has everything necessary to implement this. Once https://github.com/scala/scala#5744 gets a resolution, I'll update the scala branch to reflect that. Until then, dotty is where the most up to date stuff is. It all works, besides some dotty instability.

[Jacoby6000]

In lieu of a solution to https://github.com/scala/scala#5744, I'm going to implement this using plain 'ol recursive datastructures. The result will be an extensible AST, but users will be able to generate invalid trees. In the end, I think this is worth it, since the AST should be built by a DSL anyway.