1
# ubuntuone.u1sync.genericmerge
3
# Generic merge function
5
# Author: Tim Cole <tim.cole@canonical.com>
7
# Copyright 2009 Canonical Ltd.
9
# This program is free software: you can redistribute it and/or modify it
10
# under the terms of the GNU General Public License version 3, as published
11
# by the Free Software Foundation.
13
# This program is distributed in the hope that it will be useful, but
14
# WITHOUT ANY WARRANTY; without even the implied warranties of
15
# MERCHANTABILITY, SATISFACTORY QUALITY, or FITNESS FOR A PARTICULAR
16
# PURPOSE. See the GNU General Public License for more details.
18
# You should have received a copy of the GNU General Public License along
19
# with this program. If not, see <http://www.gnu.org/licenses/>.
20
"""A generic abstraction for merge operations on directory trees."""
22
from itertools import chain
23
from ubuntuone.storageprotocol.dircontent_pb2 import DIRECTORY
25
class MergeNode(object):
26
"""A filesystem node. Should generally be treated as immutable."""
27
def __init__(self, node_type, content_hash=None, uuid=None, children=None,
29
"""Initializes a node instance."""
30
self.node_type = node_type
31
self.children = children
33
self.content_hash = content_hash
34
self.conflict_info = conflict_info
36
def __eq__(self, other):
38
if type(other) is not type(self):
40
return self.node_type == other.node_type and \
41
self.children == other.children and \
42
self.uuid == other.uuid and \
43
self.content_hash == other.content_hash and \
44
self.conflict_info == other.conflict_info
46
def __ne__(self, other):
47
"""Non-equality test."""
48
return not self.__eq__(other)
51
def show_tree(tree, indent="", name="/"):
53
if tree.node_type == DIRECTORY:
57
print "%s%-36s %s %s %s" % (indent, tree.uuid, type_str, name,
59
if tree.node_type == DIRECTORY and tree.children is not None:
60
for name in sorted(tree.children.keys()):
61
subtree = tree.children[name]
62
show_tree(subtree, indent=" " + indent, name=name)
64
def generic_merge(trees, pre_merge, post_merge, partial_parent, name):
65
"""Generic tree merging function."""
67
partial_result = pre_merge(nodes=trees, name=name,
68
partial_parent=partial_parent)
70
def tree_children(tree):
71
"""Returns children if tree is not None"""
72
return tree.children if tree is not None else None
74
child_dicts = [tree_children(t) or {} for t in trees]
75
child_names = set(chain(*[cs.iterkeys() for cs in child_dicts]))
77
for child_name in child_names:
78
subtrees = [cs.get(child_name, None) for cs in child_dicts]
79
child_result = generic_merge(trees=subtrees,
81
post_merge=post_merge,
82
partial_parent=partial_result,
84
child_results[child_name] = child_result
86
return post_merge(nodes=trees, partial_result=partial_result,
87
child_results=child_results)
added
removed
ubuntuone/u1sync/genericmerge.py
