Imported From: https://issues.scala-lang.org/browse/SI-4528?orig=1
Reporter: Alex Kolonitsky (alex.kolonitsky)

@dcsobral said:
Anyone who threads this, beware!

The solution suggested has a big problem (or consequence) -- non-transformed XMLs still generate new data. Or, speaking through code,

val a = <a><b/></a>
val b = new RuleTransformer(new RewriteRule {})(a)
a eq b

This is true presently, would be false with either of the suggested modifications. It would also break this code:

       if (ch eq nch) n
       else           Elem(n.prefix, n.label, n.attributes, n.scope, nch: _*)

I think a better solution would be something like this:

def transform(ns: Seq[Node]): Seq[Node] = {
    val changed = ns flatMap transform
    if (changed.length != ns.length || (changed, ns).zipped.exists(_ != _)) changed
    else ns
}

That said, I never realized that fixing the double call to transform would change RuleTransformer from O(2^depth) to O(depth) (ignoring the length component of complexity). It's hard to understate that possible gains in performance.

@dcsobral said:
Ok, I was mistaken. I mean, I was mistaken to suggest I never realized calling transform twice makes it exponential -- I did, and opened a ticket about it. This is a duplicate of #3689, and the solution I present there is probably slower, but works much harder at preserving referential equality of unchanged nodes, for whatever that is worth.

Specifically, the solution here only preserves children of a node if none of the siblings is modified. The solution there preserves all nodes where no changes are made.

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