Traversable recursive node structures

Question

I am trying to implement recursive traversions over a node structure:

sealed class Node(subnodes: Traversable[Node]) extends Traversable[Node] {
  def foreach[U](f: Node => U) {
    f(this)
    subnodes foreach f
  }
}

case class Atom(id: String) extends Node(Nil)

case class Molecule(atoms: List[Node]) extends Node(atoms)

Calling toString on an element like Atom("test").toString causes a stack overflow:

Exception in thread "main" java.lang.StackOverflowError
at java.lang.System.arraycopy(Native Method)
at java.lang.String.getChars(Unknown Source)
at java.lang.AbstractStringBuilder.append(Unknown Source)
at java.lang.StringBuilder.append(Unknown Source)
at scala.collection.mutable.StringBuilder.append(StringBuilder.scala:197)
at scala.collection.TraversableOnce$class.addString(TraversableOnce.scala:297)
at Node.addString(Fail.scala:1)
at scala.collection.TraversableOnce$class.mkString(TraversableOnce.scala:263)
at Node.mkString(Fail.scala:1)
at scala.collection.TraversableLike$class.toString(TraversableLike.scala:615)
at Node.toString(Fail.scala:1)
at java.lang.String.valueOf(Unknown Source)
at scala.collection.mutable.StringBuilder.append(StringBuilder.scala:187)
at scala.collection.TraversableOnce$$anonfun$addString$1.apply(TraversableOnce.scala:300)
[...]
at Node.foreach(Fail.scala:3)
at scala.collection.TraversableOnce$class.addString(TraversableOnce.scala:298)
at Node.addString(Fail.scala:1)
at scala.collection.TraversableOnce$class.mkString(TraversableOnce.scala:263)
at Node.mkString(Fail.scala:1)
at scala.collection.TraversableLike$class.toString(TraversableLike.scala:615)
at Node.toString(Fail.scala:1)
at java.lang.String.valueOf(Unknown Source)
at scala.collection.mutable.StringBuilder.append(StringBuilder.scala:187)
at scala.collection.TraversableOnce$$anonfun$addString$1.apply(TraversableOnce.scala:300)

Note that I haven't called foreach anywhere explicitly. So why do I get a stack overflow?

I solved this particular problem with an additional TraversableNode class and an implicit conversion from Node to TraversableNode, but I would still like to know what caused the stack overflow. Thanks.

Answer 1

When you call toString on an Atom, you're getting the one for Traversable, which the documentation describes like this:

By default this string consists of the stringPrefix of this collection, followed by all elements separated by commas and enclosed in parentheses.

The "followed by all elements" part is implemented in TraversableOnce by calling the collection's foreach. Since your foreach first hits the Node itself, you immediately run into an endless loop.

Answer 2

Normally, the toString method on case classes prints the class name and the list of its arguments (those in the first argument list). An exception is made to this rule, if your case class extends a class which has an explicitly defined toString.

Your Node extends Traversable[Node]. Note that it does not have a compiler-generated case-class toString, as shown in its AST (scalac -Xprint:cleanup):

case class Atom extends Node with Product with Serializable {
   ....
    override <synthetic> def hashCode(): Int = ScalaRunTime.this._hashCode(Atom.this);
    override <synthetic> def equals(x$1: Any): Boolean = Atom.this.eq(x$1.asInstanceOf[Object]()).||(x$1.isInstanceOf[Atom]().&&({
      <synthetic> val Atom$1: Atom = x$1.asInstanceOf[Atom]();
      Atom.this.id().==(Atom$1.id()).&&(Atom$1.canEqual(Atom.this))
    }))
  };

Above, the compiler "only" generates hashCode and equals, the toString is inherited from Traversable.

The Traversable trait from the collection package has a toString method which is defined in terms of foreach. Calling toString thus makes the foreach iterate on the node itself (in line with f(this)), resulting in an infinite loop.