Case classes with an upper type bound

Question

I ran into a problem using case classes and parameterized types with an upper type bound. The Scala compiler tells me that it finds type DefaultEdge but requires Edge[Type]. I tried using something like case DefaultEdge[Type] but I get syntax errors.

Here is my setup. I have a couple of edge case classes which correspond to different types. Those classes contain the parameterized type V.

object EdgeKind extends Enumeration {
  type EdgeKind = Value
  val Default, Jump, True, False, DefaultCase, Case, Throw, Return = Value
}

sealed abstract class Edge[V <: VertexLike](val startVertex: V, val endVertex: V, val kind: EdgeKind.EdgeKind)

case class DefaultEdge[V <: VertexLike](override val startVertex: V, override val endVertex: V)
  extends Edge[V](startVertex, endVertex, EdgeKind.Default)
case class JumpEdge[V <: VertexLike](//...

Then I have a trait called GraphLike which defines a couple of methods. The only interesting part should be this one:

trait GraphLike[V <: VertexLike] {
  protected type E <: Edge[V]
}

Another trait in between implements some methods of the GraphLike trait and is called GraphLikeWithAdjacencyMatrix. When I wire everything together I have the following class:

class CFG extends GraphLikeWithAdjacencyMatrix[BasicBlockVertex] {
  def dotExport = {
    def vertexToString(vertex: BasicBlockVertex) = ""
    def edgeToString(edge: E) = edge match {//also tried Edge[BasicBlockVertex] here
      case DefaultEdge => error("CFG may not contain default edges.")
      case JumpEdge => "jump"
      case TrueEdge => "true"
      case FalseEdge => "false"
      case DefaultCaseEdge => "default"
      case CaseEdge => "case"
      case ThrowEdge => "throw"
      case ReturnEdge => "return"
    }
    new DOTExport(this, vertexToString, edgeToString)
  }
}

This is where I run into the problems. I get told that Edge[BasicBlockVertex] is expected and I only provide a DefaultEdge. The definition in DOTExport is class DOTExport[V <: VertexLike](val graph: GraphLike[V], val vertexToString: V => String, val edgeToString: Edge[V] => String)

So my question is now, how could I still use case classes for the edge types and make the compiler happy? It must be some stupid mistake on my side.

By the way, the match-code works once I say DefaultEdge(x,y) instead of DefaultCase etc. However then the instantiation of DOTExport fails because Edge[?] is required and I pass a CFG.E

Thank you!

EDIT: In fact the combination of E = Edge[V] in GraphLike and using DefaultEdge(_, _) works. This is unfortunately just the result of try and error. I would really like to know why it works now.

The error message:

(fragment of test.scala):25: error:
type mismatch;  found   :
(Graph.this.E) => java.lang.String 
required: (this.Edge[?]) => String
    new DOTExport(this, (vertex: V) => vertex.toString, edgeToString)

Here is the full compilable code illustrating my problem. Again, my problem is line 14, since everything works when you replace type E <: Edge[V] with type E = Edge[V] and I have no idea why.

object EdgeKind {
  val Default = 0
  val Jump = 1
}

abstract class Edge[V <: VertexLike](val startVertex: V, val endVertex: V, val kind: Int)

case class DefaultEdge[V <: VertexLike](override val startVertex: V, override val endVertex: V) extends Edge[V](startVertex, endVertex, EdgeKind.Default)
case class JumpEdge[V <: VertexLike](override val startVertex: V, override val endVertex: V) extends Edge[V](startVertex, endVertex, EdgeKind.Jump)

trait VertexLike

trait GraphLike[V <: VertexLike] {
  protected type E <: Edge[V] // Everything works when E = Edge[V]
}

class DOTExport[V <: VertexLike](val graph: GraphLike[V], val vertexToString: V => String, val edgeToString: Edge[V] => String)

class Graph[V <: VertexLike] extends GraphLike[V] {
  def dotExport = {
    def edgeToString(edge: E) = edge match {
      case DefaultEdge(_, _) => ""
      case JumpEdge(_, _) => "jump"
    }
    new DOTExport(this, (vertex: V) => vertex.toString, edgeToString)
  }
}

Answer 1

There's too much missing to be able to really help. You must provide the exact error messages, instead of paraphrasing them.

At any rate, case DefaultEdge means a comparision between the object passed and the object DefaultEdge. The latter is the object companion of the class DefaultEdge, automatically created through the use of the case class statement. Such companion objects do not belong to the class they are companion to. They are singletons, which means their own classes are unique to themselves, and, otherwise, just inherit AnyRef.

So, in other words, DefaultEdge is not an Edge, and that's why you get an error. As for the error you got when you used DefaultEdge(_, _), you ommitted too much detail. However... are you sure you wrote the code that way? I would expect the following instead:

new DOTExport(this, vertexToString _, edgeToString _)

EDIT

Ok, the second error message is clear now. The original declaration of E was that it was a subclass of Edge, but DOTExport is expecting a function that takes an Edge and converts it into a String. To understand the problem here, note that the following definition also works:

protected type E >: Edge[V]

Let's say, to illustrate the problem, that you have two subclasses of Edge: IntEdge and StringEdge. The first has a number field, and the second a name field. So, we could write the following functions:

def intEdgeToString(ie: IntEdge) = ie.number.toString
def stringEdgeToString(se: StringEdge) = se.name

Now, let's create a var and store one of them:

var eTS: E => String = intEdgeToString _

Since E is any subclass of Edge, this would be acceptable. So we create a DOTExport passing eTS to it. Next, we feed DOTExport not with IntEdge, but with StringEdge. Since the latter do not have a number field, trying to run it would cause an exception at run-time, which defeats the whole purpose of static typing.

It is to prevent this kind of problem that Scala did not accept your original definition.

Answer 2

First, Daniel is quite correct that having more precise information would help a lot. However, it looks like you just need to do both things you tried together:

def edgeToString(edge: Edge[BasicBlockVertex]) = edge match {
  case DefaultEdge(_,_) => error("CFG may not contain default edges.")
  case JumpEdge(_,_) => "jump"
  case TrueEdge(_,_) => "true"
  ...

because 1) the pattern DefaultEdge matches the wrong thing 2) edgeToString(edge: E) = ... means edgeToString has the type CFG.E => String when used as a function value and not Edge[V] => String and so can't be passed to new DOTExport!