PPAPI Patching System and Unit Tests

visual_studio/NativeClientVSAddIn/InstallerResources/xml_patch.py

+#!/usr/bin/env python
+# Copyright (c) 2012 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+""" This module is a utility for applying an xml patch to an xml file.
+
+The format of the patch is described in the documentation for
+the patch_xml() function.
+"""
+
+import collections
+import copy
+import xml.etree.ElementTree as ElementTree
+
+
+def PatchXML(source_xml_tree, patch_xml_tree):
+  """Applies a patch to the source xml and returns a new merged xml tree.
+
+  Given a patch xml tree, it applies the patch to the source xml tree
+  and returns the resulting modified xml tree.
+
+  Patching is done by reading the patch_xml_tree for an element and then
+  finding the in-order matching element in the source_xml_tree. Both elements
+  are entered to look for matching sub-elements recursively.
+
+  Patching occurs when a <PatchRemove> or <PatchAdd> element is encountered
+  in the patch xml tree. For a remove operation, the first element in the
+  source_xml_tree from the current read position that matches the contents of
+  the <PatchRemove> element is removed. The read pointer is updated accordingly.
+  For an add operation, the contents of the <PatchAdd> element is added at the
+  current reading location.
+
+  If for example, an add operation needs to be done after certain elements,
+  the elements can be listed before the <PatchAdd> operation so that they are
+  matched first before the add operation.
+
+  Example:
+  Source file:
+  <a>
+    <b></b>
+    <c></c>
+  </a>
+
+  Patch file:
+  <a>
+    <b></b>
+    <PatchAdd><zzz></zzz></PatchAdd>
+  </a>
+
+  Result:
+  <a>
+    <b></b>
+    <zzz></zzz>
+    <c></c>
+  </a>
+
+
+  Args:
+    source_xml_tree: An ElementTree object with base xml to change.
+    patch_xml_tree: An ElementTree object with xml to apply. See above notes
+      for the xml structure of a patch.
+
+  Returns:
+    A new xml tree based on source with the patch applied.
+
+  Raises:
+    General Exception indicating a merge error has occured.
+  """
+  source = source_xml_tree.getroot()
+  patch = patch_xml_tree.getroot()
+  if not ElementMatch(source, patch):
+    raise Exception('Root nodes do not match, cannot merge')
+  return ElementTree.ElementTree(MergeElement(source, patch))
+
+
+def MergeElement(source_elem, patch_elem):
+  """Applies a single patch element to a single source element.
+
+  The merge is applied recursively for sub-elements. See the documentation
+  for patch_xml() for a description of how patching is done.
+
+  Args:
+    source_elem: An Element object with xml to change.
+    patch_elem: An Element object with xml to apply.
+
+  Returns:
+    A new xml Element with the patch_elem applied to source_elem.
+
+  Raises:
+    General Exception indicating a merge error has occured.
+  """
+  assert ElementMatch(source_elem, patch_elem), 'Mismatched merge'
+
+  # Create a new element by copying tags from source. Below we will merge
+  # the subelements of source with the patch and put them in new_element.
+  new_element = ElementTree.Element(source_elem.tag, source_elem.attrib)
+
+  patch_children = patch_elem.getchildren()
+  patch_index = 0
+  remove_targets = collections.deque()
+  find_target = None
+  for source_child in source_elem.getchildren():
+    # If we have no current patch operation then read the next patch element.
+    while (len(remove_targets) == 0 and find_target is None and
+        patch_index < len(patch_children)):
+
+      # PatchAdd operation.
+      if IsPatchAddTag(patch_children[patch_index].tag):
+        for addition in patch_children[patch_index].getchildren():
+          new_element.append(copy.deepcopy(addition))
+
+      # Start a remove operation by creating a list of elements to skip adding.
+      elif IsPatchRemoveTag(patch_children[patch_index].tag):
+        remove_targets = collections.deque(
+            patch_children[patch_index].getchildren())
+
+      # Not an Add or Remove, must be a find target (find operation).
+      else:
+        find_target = patch_children[patch_index]
+      patch_index += 1
+
+    # A remove operation means skipping adding the element to new_element.
+    if (len(remove_targets) > 0 and
+        ElementMatch(source_child, remove_targets[0])):
+      remove_targets.popleft()
+
+    # A matching find target means we must merge the sub-elements.
+    elif find_target is not None and ElementMatch(source_child, find_target):
+      merge = MergeElement(source_child, find_target)
+      new_element.append(copy.deepcopy(merge))
+      find_target = None
+
+    # Otherwise this source element doesn't match any patch operations, add it.
+    else:
+      new_element.append(copy.deepcopy(source_child))
+
+  # Raise exceptions if find/remove didn't finish before the end of the source.
+  if find_target is not None:
+    raise Exception('Find operation never matched:' + find_target.tag)
+  elif len(remove_targets) != 0:
+    raise Exception('Remove operation never matched: ' + remove_targets)
+
+  # We may have more add operations after source has run empty:
+  while patch_index < len(patch_children):
+    if IsPatchAddTag(patch_children[patch_index].tag):
+      for addition in patch_children[patch_index].getchildren():
+        new_element.append(copy.deepcopy(addition))
+      patch_index += 1
+    else:
+      raise Exception('Non-add operation attempted after source end. ' +
+                      'Tag: %s, Children %s' %
+                      (patch_children[patch_index].tag,
+                       patch_children[patch_index].get_children()))
+
+  return new_element
+
+
+def ElementMatch(elem1, elem2):
+  return elem1.tag == elem2.tag and elem1.attrib == elem2.attrib
+
+
+def IsPatchAddTag(tag):
+  # We look at the end of the tag because we need to ignore the namespace.
+  # Because the tag can be a sub-element of arbitrary elements it could inherit
+  # any default namespace.
+  return tag.endswith('PatchAdd')
+
+
+def IsPatchRemoveTag(tag):
+  # We look at the end of the tag because we need to ignore the namespace.
+  # Because the tag can be a sub-element of arbitrary elements it could inherit
+  # any default namespace.
+  return tag.endswith('PatchRemove')