Last year, I gave a talk on XML differencing at the
Extreme Markup Languages
2005 conference in Montr al. Since then I didn't have much time to work
on that project.
The prototype app is opensource, and available at
ssddiff.alioth.debian.org.
The slides are there, too, and so is a link to the article.
XML differencing is actually a two phase process; I've been mostly working
on the first phase. Traditional approaches intertwine the two phases.
In the first phase, you build a mapping between the two documents. I called
this a "nodeset correspondence" in the slides. Basically you decide which node
from the first document corresponds to which node in the second document.
When you have found this mapping (the "marked" output writer of ssddiff will
output this information in form of two XML documents marked with numbers in
a certain attribute), the actual differencing is done. But much of the work
remains.
When doing a diff, the
output (format) is just as important as the actual
result.
While the "marked" output explained above is very precise, it doesn't give
the user an overview of what has changed in the document. That's why I added
two more output writers, the "xupdate" writer and the "merged" writer.
The "xupdate" writer does obviously produce an XUpdate script. It goes a long
way to optimizing the output (read: minimizing the number of operations),
and employs a longest-common-subsequence algorithm for that (LCS is what
regular diff uses on lines!). Fortunately we already have a 1:1 mapping,
so this boils down to a longest-increasing-subsequence which can be computed
very efficiently.
Then the writer employs some XUpdate tricks to do real moves (by storing
parts of the tree in variables to be inserted later), and avoids collapsing of
text nodes (it will eventually insert dummy nodes for that). But all this gives
just a glimpse of the complexity I've encountered in what I considered to be a
"remote" part of my project. It isn't even described in the paper, because I
just hacked this code together to work somewhat (attribute handling is
incomplete IIRC).
The "merged" writer turned out to be much more powerful than I had imagined
and actually rather easy. After "merging" two version of an HTML document,
I could add some CSS rules and have a visual presentation of the changes
in my browser. Very cool. I'd love to add this html merge functionality to
the prototype, but I didn't have enough time yet (you'll find some refactoring
of the merged writer in SVN though to get there someday).
But let me get back to the difficulties in the "XUpdate" writer. Not all of
these difficulties are actually of technical nature. It is (like with the
semantics of differencing) a matter of the intended data model and use.
When you are doing a diff to be applied by a computer (e.g. via XUpdate),
you may have the requirement, that the resulting document is
identical
to the original document. In that case, the diff is likely to have to restore
whitespace. If you are interested in
analyzing the differences, you
will want to skip any irrelevant information.
Let's assume we have an address book:
<abook><entry name="tom" /><entry name="jerry" /></abook>
Ordering of the entry nodes is likely to be irrelevant. You address book
applications will sort the entries on demand. So a "semantic diff" shouldn't
include any changes to the ordering of "entry" nodes, should it?
The XUpdate writer doesn't have any functionality in place to skip such changes
from being written to the output file. This will likely be not possible
without some DTD magic and extra user information.
However, to have the benefits of the "-u" context option of good old
"diffutils" - fuzzy matches, and somewhat reliable merging of changes without
having all revisions available - such semantics are needed, too. But this
will even further increase complexity of the output writer, which for example
would need to detect somehow that the "name" attribute in my address book is
a unique key, and therefore xpath expressions like
/abook/entry[@name='tom'] are preferrable to expressions such as
/abook/entry[1], which will easily break when merging.
The specification of an "XUpdate-replacement with context information" is
probably a whole thesis in itself, I guess.
P.S. I'm occasionally asked about a Java version of ssddiff. Sorry that I
have to disappoint you there. First of all, I'm very short of time. Then I'm
not too comfortable in Java, and I estimated that the Java version would
need at least twice as much memory, because of certain
optimizations I can't easily access in Java that I can just hide in a template in C++. And memory is the key limiting factor at least in exact mode.
Serves 8.
