In the discussion of #1433694 on the #python-dev channel, it was
observed that the normalize method of minidom.Node could take some
refactoring. A patch is attached.

I have applied the supplied patch to the current trunk, and it passes
the tests.  I've also attached a more extensive test case that exercises
the recursion.

I checked the speed of the proposed patch, and found that it was
definitely slower than the original code.  So I took another look at the
original, and refactored it in a different way: instead of moving the
sibling relinking into a second pass, I changed to code to only relink
siblings when a node is removed.  The new patch passes all test, and is
faster than the old code.  I tested the timing both against the same
small nested document I used in testNormalize2, and by running normalize
on a 37K html document (a copy of the xml.dom.minidom chapter from the
Library Reference):

original code:
testNormalize2: [2.5144219398498535, 2.5053589344024658, 2.5059471130371094]
example.html:   [44.641155958175659, 44.575434923171997, 44.996657133102417]

original patch
testNormalize2: [2.7070891857147217, 2.7012341022491455, 2.7003159523010254]
example.html:   [67.908604860305786, 68.088788986206055, 67.92288613319397]

My patch
testNormalize2: [2.4626028537750244, 2.4619381427764893, 2.4617609977722168]
example.html:   [22.780415058135986, 22.780103921890259, 22.721666097640991]

IMO my refactoring is also easier to understand than either the old code
or the proposed patch.

Patch, including new test, is attached, and also pushed to
bzr+ssh://bazaar.launchpad.net/~rdmurray/python/issue2170.

Er, I meant to say, "as easy to understand" as the proposed patch.

I eyeballed the new patch and wonder if the case where text nodes are
collapsed is handled correctly. Assume that self.childNodes contains
nodes [A, B, C], where A and B are non-empty text nodes and C is a
non-text node.

The algorithm would collapse A and B into A and then unlink B, and I
think C.previousSibling would still reference the unlinked B, rather
than the correct A. Am I missing something?

If this is indeed a bug in the proposed patch, I suggest adding an
additional test for this case.

The bug itself should not be too hard to fix; the "elif" case would need
the same

    if child.nextSibling:
        child.nextSibling.previousSibling = child.previousSibling

assignment as the "if" case.

You are absolutely right.  I will write a test case and fix the patch.

Added several more tests, to validate the sibling link code more, and
fixed the bug.

While we're cleaning up:
       data = child.data
       if not data:
could be
       if not child.data:
since data is not used again.

Alternatively, you could use data in place of child.data later on for a
small speed-up, but I doubt that we care about such small optimizations
here. If we do, then we should also assign a name to child.nextSibling,
though.

I found the three-line duplication between the two branches mildly
refactor-worthy, but when I eliminated it the control logic got more
involved and I don't think that's a good trade-off here.

I removed my original patch which has been superseded by David's patch.

David, I suggest that you also remove test_minidom.patch which is
superseded by your later patch (see http://bugs.python.org/msg77766 for
policy on this).

Removed old patches, updated patch to remvoe the unnecessary local
variable assignment (also pushed to launchpad).

Short review: code looks good to me, patch applies cleanly to trunk,
passes tests.

@akuchling: I don't know if you remember, but this rewrite was
originally suggested by you on a bug day some time ago. I think David's
patch is ready to be applied.

Andrew, any objection to my going ahead and applying this patch?

The new version of the code looks all right, so I
think this patch can be applied.

Committed in r71414.