BasicTransformer has exponential complexity

[biswanaths]

Please see
https://issues.scala-lang.org/browse/SI-3689
https://issues.scala-lang.org/browse/SI-4528

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 , 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.

[mlin6436]

Hi,

Is there any prospect this fix being released soon, cos my team is currently using the patch to get around the exponential complexity problem?

Thanks a lot.

[biswanaths]

Hey, sorry that your team has to use patch for this issue. I will update when we can do a release.