PPAPI Patching System and Unit Tests

visual_studio/NativeClientVSAddIn/InstallerResources/xml_patch.py

Index: visual_studio/NativeClientVSAddIn/InstallerResources/xml_patch.py
diff --git a/visual_studio/NativeClientVSAddIn/InstallerResources/xml_patch.py b/visual_studio/NativeClientVSAddIn/InstallerResources/xml_patch.py
new file mode 100644
index 0000000000000000000000000000000000000000..361cd4cb851a2070dd32d36702ad8347443356bb
--- /dev/null
+++ b/visual_studio/NativeClientVSAddIn/InstallerResources/xml_patch.py
@@ -0,0 +1,165 @@
+#!/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 xml.etree.ElementTree as ElementTree
+
+def patch_xml(source_xml_tree, patch_xml_tree):

[noelallen1, 2012/07/20 21:46:01]

PatchXML

[tysand, 2012/07/24 21:24:15]

Done.

+  """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 element_match(source, patch):
+    raise Exception('Root nodes do not match, cannot merge')
+  return ElementTree.ElementTree(merge_element(source, patch))
+

[noelallen1, 2012/07/20 21:46:01]

two lines

[tysand, 2012/07/24 21:24:15]

Done.

+def merge_element(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 element_match(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 line.

[binji, 2012/07/20 22:54:49]

s/line/element/ here and elsewhere

[tysand, 2012/07/24 21:24:15]

Done.

+    while (len(remove_targets) is 0 and find_target is None and

[binji, 2012/07/20 22:54:49]

s/is 0/== 0/

[tysand, 2012/07/24 21:24:15]

Done.

+          patch_index < len(patch_children)):

[binji, 2012/07/20 22:54:49]

nit: 4 space indent

[tysand, 2012/07/24 21:24:15]

Done.

+
+      # PatchAdd operation.
+      if is_patch_add_tag(patch_children[patch_index].tag):
+        for addition in patch_children[patch_index].getchildren():
+          new_element.append(addition)

[binji, 2012/07/20 22:54:49]

does this clone the addition element or is it shared?

[tysand, 2012/07/24 21:24:15]

I think it is a shallow copy. Although this doesn't make a difference to how we
currently use this code, I will change this to a deep copy to prevent future
bugs and match expected behavior.
On 2012/07/20 22:54:49, binji wrote:

+        patch_index += 1

[binji, 2012/07/20 22:54:49]

extract patch_index += 1, add below this if/elif/else chain

[tysand, 2012/07/24 21:24:15]

Done.

+
+      # Start a remove operation by creating a list of lines to skip adding.
+      elif is_patch_remove_tag(patch_children[patch_index].tag):
+        remove_targets = collections.deque(
+            patch_children[patch_index].getchildren())
+        patch_index += 1
+
+      # 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 line to new_element.
+    if (len(remove_targets) > 0 and
+        element_match(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 element_match(source_child, find_target):
+      merge = merge_element(source_child, find_target)
+      new_element.append(merge)
+      find_target = None
+      patch_index += 1
+
+    # Otherwise this source line doesn't match any patch operations, add it.
+    else:
+      new_element.append(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) is not 0:

[binji, 2012/07/20 22:54:49]

!= 0

[tysand, 2012/07/24 21:24:15]

Done.

+    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 is_patch_add_tag(patch_children[patch_index].tag):
+      for addition in patch_children[patch_index].getchildren():
+        new_element.append(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 element_match(elem1, elem2):
+  return elem1.tag == elem2.tag and elem1.attrib == elem2.attrib
+
+def is_patch_add_tag(tag):
+  return tag[-8:] == 'PatchAdd'

[binji, 2012/07/20 22:54:49]

why is this not tag == 'PatchAdd'?

[tysand, 2012/07/24 21:24:15]

I've added a comment explaining this. Basically because this element can be a
sub-element of any element, it can inherit any namespace, so we need to ignore
the namespace part of the tag.
On 2012/07/20 22:54:49, binji wrote:

[binji, 2012/07/24 22:13:08]

OK, use tag.endswith('PatchAdd')

+
+def is_patch_remove_tag(tag):
+  return tag[-11:] == 'PatchRemove'