可遍历的递归节点结构

Question

我试图在节点结构上实现递归遍历:

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)

调用toString类似的元素Atom("test").toString会导致堆栈溢出:

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)

请注意,我没有明确地调用foreach.那么为什么我会出现堆栈溢出？

我用一个额外的TraversableNode类和一个隐式转换Node来解决这个特殊的问题TraversableNode,但是我仍然想知道导致堆栈溢出的原因.谢谢.

Answer 1

当你打电话toString给Atom,你得到的Traversable那个,文档描述如下:

默认情况下,此字符串stringPrefix由此集合组成,后跟所有以逗号分隔并括在括号中的元素.

该"之后的所有元素"部分实现在TraversableOnce通过调用集合的foreach.因为你的foreach第一次打击Node自己,你立即遇到无限循环.