#!/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 third_party.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 = list(patch_elem) | |
patch_index = 0 | |
remove_targets = collections.deque() | |
find_target = None | |
for source_child in source_elem: | |
# 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]: | |
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]) | |
# 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]: | |
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, | |
list(patch_children[patch_index]))) | |
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') |