CODEWITHSUNDEEP
xmlscala
Michael
Michael

Reputation: 42110

How does XML transform work in Scala

I am looking for an application bug, which makes scala.xml.BasicTransformer run in infinite loop. First of all, I am reading BasicTransformer.scala to figure out how transform (see below) works:

abstract class BasicTransformer extends Function1[Node, Node] {

 // ...

  protected def unchanged(n: Node, ns: Seq[Node]) =
    ns.length == 1 && (ns.head == n)

  def transform(ns: Seq[Node]): Seq[Node] = {
    val (xs1, xs2) = ns span (n => unchanged(n, transform(n)))

    if (xs2.isEmpty) ns
    else xs1 ++ transform(xs2.head) ++ transform(xs2.tail)
  }

... // rest of the code

}

Could you explain

Upvotes: 0

Views: 200

Answers (1)

Jack Leow
Jack Leow

Reputation: 22497

As I understand it, span basically splits the Seq into two Seqs, where:

  1. The first Seq contains elements that matches the filter function.
  2. The second Seq starts with the first element that does not match the filter function.

A more technical explanation of Seq#span(...) can be found in the API docs.

The transform function seems to simply be applying the transform recursively to all the nodes in the XML tree, and should always terminate.

After spanning the Seq of nodes, xs1 contains elements where applying transform(n: Node) (note that this is a different transform than the one you pasted) does not change n. xs2 starts with the first element where applying transform to the element changes the element.

It is then done with xs1, but continues processing xs2: It applies transform(n: Node) to the first element of xs2, and transform(ns: Seq[Node]) to the remaining elements in xs2.

The "xs2" keeps getting smaller and smaller until it's eventually empty, and the function terminates.

Edit: I was thinking about this a little bit more, and I realize the span call isn't strictly necessary, it seems like they could have recursed and simply do a head::tail split, but I guess this implementation is more optimal? It does seem to call transform(n: Node) twice for each node that is not unchanged by the transform though.

Upvotes: 1

Related Questions