BasicTransformer has exponential complexity

[scabug]

It seems BasicTransformer has exponential complexity on the nesting level of the XML being processed. This is due to this method:

  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)
  }

Each modified node is transformed twice: once at the span, and again at the if/else. So, for <a><b><c><d/></c></b></a>, with c being modified, node a gets transformed twice, node b gets transformed four times (twice for each time a is transformed), and node c gets transformed eight times.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-3689?orig=1
Reporter: @dcsobral

[scabug]

@dcsobral said:
I propose the following rewrite of that method as a fix:

  def transform(ns: Seq[Node]): Seq[Node] = {
    val xs = ns.toStream map transform
    val (xs1, xs2) = xs zip ns span { case (x, n) => unchanged(n, x) }
    
    if (xs2.isEmpty) ns
    else (xs1 map (_._2)) ++ xs2.head._1 ++ transform(ns drop (xs1.length + 1))
  }

I considered modifying unchanged, but, as a protected method, it is part of the API. Also, ns take xs1.length might be better than xs1 map (_._2). This whole method could probably be made more efficient with a carefully constructed while loop, I think, but this, at least, solves the complexity problem.

[scabug]

@SethTisue said:
The scala-xml library is now community-maintained. Issues with it are now tracked at https://github.com/scala/scala-xml/issues instead of here in the Scala JIRA.

Interested community members: if you consider this issue significant, feel free to open a new issue for it on GitHub, with links in both directions.

[scabug]

Caoilte O'Connor (caoilte) said:
Seems to be covered by
scala/scala-xml#58
and
scala/scala-xml#59

which is encouraging!