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?

Answer 1

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;
}