Looking for performant XyDiff Port in C# (XML Diff Patch with XID)

Question

I store some data as XML and the changes of the user as diff to the original XML, so the data for the user can be patched on runtime.

Example for the original xml (only part of it):

<module  id="">
  <title id="">
    ...
  </title>
  <actions>
    ...
  </actions>
  <zones id="" selected="right">
    <zone id="" key="right" name="Right" />
  </zones>
</module>

Example of the user diff (the user changed the value of selected from right to left):

<xd:xmldiff version="1.0" srcDocHash="" 
    options="IgnoreChildOrder IgnoreNamespaces IgnorePrefixes IgnoreSrcValidation " 
    fragments="no" 
    xmlns:xd="http://schemas.microsoft.com/xmltools/2002/xmldiff">
  <xd:node match="1">
    <xd:node match="3">
      <xd:change match="@selected">left</xd:change>
    </xd:node>
  </xd:node>
</xd:xmldiff>

The problem is, that the patch looks for the order of the XML nodes. If the order changes than the diff cannot be applied anymore or even worse it will be applied wrongly. So I would prefer patching by XID. Does anyone know a performant library or algorith for C# for a XyDiff?

Let me get this straight: you are currently comparing two XML files using XyDiff, which produces the shown output. You are not happy with this output, because it relies on an ordered XML-structure. You are now looking for a diff-tool or algorithm, which delivers the ID of changed nodes along with the new value? Is that correct so far? — froeschli, Jun 12 '12 at 08:59
Yes, correct. The match would then show the Guid of the Xml node. ... — Nathalie Kellenberger, Jun 12 '12 at 09:03
Which version of C# are you using? If it is > C# 2.0 then Linq2Xml could be an option. This would require, that you write the comparison yourself. — froeschli, Jun 12 '12 at 10:32
Followup question: does the order of the original file change, after the comparison or is the order of the user-edited file different from the original file? If the latter is the case, you could specify `XmlDiffOptions.IgnoreChildOrder` when creating the diff. See [Using the XML Diff and Patch Tool in Your Applications](http://msdn.microsoft.com/en-us/library/aa302294.aspx) for further information. — froeschli, Jun 12 '12 at 10:43
We are using .Net Framework 4.0. Linq2Xml is great, but we would have to write the comparison first to see if it would be fast enough. — Nathalie Kellenberger, Jun 12 '12 at 11:22
Unfortunately the original file changes. We are already using the IgnoreChildOrder option, but this doesn't help. The administrator can change the original file on any time (change order, delete nodes) and the diffgram of the user must still match after those changes. — Nathalie Kellenberger, Jun 12 '12 at 11:24
We are only saving the original file (used for all) and the diffgram per user. — Nathalie Kellenberger, Jun 12 '12 at 11:26
I had a look at [XML Diff and Patch Tool](http://treepatch.sourceforge.net/report.pdf) which is a dissertation by Kyriakos Komvoteas from 2003. It seems to be able to do what you want, but it still is positional based instead of the required ID-based diff. — froeschli, Jun 12 '12 at 12:42

Nathalie Kellenberger · Accepted Answer · 2012-06-19T08:43:38.190

We developed now our own solution that works fine.

What did we do:

ensure that every xml node in the original file has an unique id (no matter on which level)
generate a flat xml patch for user changes that only saves the changes of each changed node (without the level structure)
if the user changes a value, write a xmlpatch node in the patch xml with attribute targetid pointing to the id of the original node
if the user changed an attribute, write the attribute with the new value to the xmlpatch node
if the user changes a value, write the value to the xmlpatch node

The xml patch looks the following:

<patch>
  <xmlpatch sortorder="10" visible="true" targetId="{Guid-x}" />
  <xmlpatch selected="left" targetId="{Guid-y}" />
  <xmlpatch targetId="{Guid-z}">true</xmlpatch>
</patch>

The code to produce the patch xml is pretty easy. We loop throug all xml nodes and for each node through all attributes. If an attribute or value of a node is different to the original, we generate the patch node with the attribute or value. Please note that the code was written in one night ;)

public static XDocument GenerateDiffGram(XDocument allUserDocument, XDocument runtimeDocument)
{
    XDocument diffDocument = new XDocument();
    XElement root = new XElement("patch");

    AddElements(root, runtimeDocument, allUserDocument.Root);

    diffDocument.Add(root);
    return diffDocument;
}

private static void AddElements(XElement rootPatch, XDocument runtimeDocument, XElement allUserElement)
{
    XElement patchElem = null;
    if (allUserElement.Attribute("id") != null 
        && !string.IsNullOrWhiteSpace(allUserElement.Attribute("id").Value))
    {
        // find runtime element by id
        XElement runtimeElement = (from e in runtimeDocument.Descendants(allUserElement.Name)
                        where e.Attribute("id") != null 
                        && e.Attribute("id").Value.Equals(allUserElement.Attribute("id").Value)
                        select e).FirstOrDefault();
        // create new patch node
        patchElem = new XElement("xmlpatch");

        // check for changed attributes
        foreach (var allUserAttribute in allUserElement.Attributes())
        {
            XAttribute runtimeAttribute = runtimeElement.Attribute(allUserAttribute.Name);
            if (!allUserAttribute.Value.Equals(runtimeAttribute.Value))
            {
                patchElem.SetAttributeValue(allUserAttribute.Name, runtimeAttribute.Value);
            }
        }

        // check for changed value
        if (!allUserElement.HasElements 
        && !allUserElement.Value.Equals(runtimeElement.Value))
        {
            patchElem.Value = runtimeElement.Value;
        }
    }

    // loop through all children to find changed values
    foreach (var childElement in allUserElement.Elements())
    {
        AddElements(rootPatch, runtimeDocument, childElement);
    }

    // add node for changed value
    if (patchElem != null 
        && (patchElem.HasAttributes 
        || !string.IsNullOrEmpty(patchElem.Value)))
    {
        patchElem.SetAttributeValue("targetId", allUserElement.Attribute("id").Value);
        rootPatch.AddFirst(patchElem);
    }
}

On runtime we patch the changes saved in the patch xml back. We geht the original node by the targetid and overwrite the attributes and values.

public static XDocument Patch(XDocument runtimeDocument, XDocument userDocument, string modulePath, string userName)
{
    XDocument patchDocument = new XDocument(userDocument);

    foreach (XElement element in patchDocument.Element("patch").Elements())
    {
        // get id of the element
        string idAttribute = element.Attribute("targetId").Value;
        // get element with id from allUserDocument
        XElement sharedElement = (from e in runtimeDocument.Descendants()
                        where e.Attribute("id") != null 
                        && e.Attribute("id").Value.Equals(idAttribute)
                        select e).FirstOrDefault();

        // element doesn't exist anymore. Maybe the admin has deleted the element
        if (sharedElement == null)
        {
            // delete the element from the user patch
            element.Remove();
        }
        else
        {
            // set attributes to user values
            foreach (XAttribute attribute in element.Attributes())
            {
                if (!attribute.Name.LocalName.Equals("targetId"))
                {
                    sharedElement.SetAttributeValue(attribute.Name, attribute.Value);
                }
            }

            // set element value
            if (!string.IsNullOrEmpty(element.Value))
            {
                sharedElement.Value = element.Value;
            }
        }
    }

    // user patch has changed (nodes deleted by the admin)
    if (!patchDocument.ToString().Equals(userDocument.ToString()))
    {
        // save back the changed user patch
        using (PersonalizationProvider provider = new PersonalizationProvider())
        {
            provider.SaveUserPersonalization(modulePath, userName, patchDocument);
        }
    }

    return runtimeDocument;
}

Looking for performant XyDiff Port in C# (XML Diff Patch with XID)

1 Answers1