merge.py

   1 from xml.dom import minidom, XMLNS_NAMESPACE, Node
   2 from zeroinstall.injector.namespaces import XMLNS_IFACE
   3 import xmltools
   4
   5 def childNodes(parent, namespaceURI = None, localName = None):
   6         for x in parent.childNodes:
   7                 if x.nodeType != Node.ELEMENT_NODE: continue
   8                 if namespaceURI is not None and x.namespaceURI != namespaceURI: continue
   9
  10                 if localName is None or x.localName == localName:
  11                         yield x
  12
  13 class Context:
  14         def __init__(self, impl):
  15                 doc = impl.ownerDocument
  16                 self.attribs = {}               # (ns, localName) -> value
  17                 self.requires = []
  18                 self.commands = {}              # (name, version-expr) -> <command>
  19
  20                 node = impl
  21                 while True:
  22                         for name, value in node.attributes.itemsNS():
  23                                 if name[0] == XMLNS_NAMESPACE:
  24                                         xmltools.register_namespace(value, name[1])
  25                                 elif name not in self.attribs:
  26                                         self.attribs[name] = value
  27                         if node.nodeName == 'group':
  28                                 # We don't care about <requires> or <command> inside <implementation>;
  29                                 # they'll get copied over anyway
  30                                 for x in childNodes(node, XMLNS_IFACE, 'requires'):
  31                                         self.requires.append(x)
  32                                 for x in childNodes(node, XMLNS_IFACE, 'restricts'):
  33                                         self.requires.append(x)
  34                                 for x in childNodes(node, XMLNS_IFACE, 'command'):
  35                                         command_name = (x.getAttribute('name'), x.getAttribute('if-0install-version'))
  36                                         if command_name not in self.commands:
  37                                                 self.commands[command_name] = x
  38                                         # (else the existing definition on the child should be used)
  39                         node = node.parentNode
  40                         if node.nodeName != 'group':
  41                                 break
  42
  43         @property
  44         def has_main_and_run(self):
  45                 """Checks whether we have a main and a <command name='run'>.
  46                 This case requires special care."""
  47                 for name, expr in self.commands:
  48                         if name == 'run':
  49                                 break
  50                 else:
  51                         return False    # No run command
  52                 return (None, 'main') in self.attribs
  53
  54 def find_impls(parent):
  55         """Return all <implementation> children, including those inside groups."""
  56         for x in childNodes(parent, XMLNS_IFACE):
  57                 if x.localName == 'implementation':
  58                         yield x
  59                 elif x.localName == 'group':
  60                         for y in find_impls(x):
  61                                 yield y
  62
  63 def find_groups(parent):
  64         """Return all <group> children, including those inside other groups."""
  65         for x in childNodes(parent, XMLNS_IFACE, 'group'):
  66                 yield x
  67                 for y in find_groups(x):
  68                         yield y
  69
  70 def nodesEqual(a, b):
  71         assert a.nodeType == Node.ELEMENT_NODE
  72         assert b.nodeType == Node.ELEMENT_NODE
  73
  74         if a.namespaceURI != b.namespaceURI:
  75                 return False
  76
  77         if a.nodeName != b.nodeName:
  78                 return False
  79
  80         a_attrs = set(["%s %s" % (name, value) for name, value in a.attributes.itemsNS()])
  81         b_attrs = set(["%s %s" % (name, value) for name, value in b.attributes.itemsNS()])
  82
  83         if a_attrs != b_attrs:
  84                 #print "%s != %s" % (a_attrs, b_attrs)
  85                 return False
  86
  87         a_children = list(childNodes(a))
  88         b_children = list(childNodes(b))
  89
  90         if len(a_children) != len(b_children):
  91                 return False
  92
  93         for a_child, b_child in zip(a_children, b_children):
  94                 if not nodesEqual(a_child, b_child):
  95                         return False
  96
  97         return True
  98
  99 def score_subset(group, impl):
 100         """Returns (is_subset, goodness)"""
 101         for key in group.attribs:
 102                 if key not in impl.attribs.keys():
 103                         #print "BAD", key
 104                         return (0,)             # Group sets an attribute the impl doesn't want
 105         matching_commands = 0
 106         for name_expr, g_command in group.commands.iteritems():
 107                 if name_expr not in impl.commands:
 108                         return (0,)             # Group sets a command the impl doesn't want
 109                 if nodesEqual(g_command, impl.commands[name_expr]):
 110                         # Prefer matching commands to overriding them
 111                         matching_commands += 1
 112         for g_req in group.requires:
 113                 for i_req in impl.requires:
 114                         if nodesEqual(g_req, i_req): break
 115                 else:
 116                         return (0,)             # Group adds a requires that the impl doesn't want
 117         # Score result so we get groups that have all the same requires/commands first, then ones with all the same attribs
 118         return (1, len(group.requires) + len(group.commands), len(group.attribs) + matching_commands)
 119
 120 # Note: the namespace stuff isn't quite right yet.
 121 # Might get conflicts if both documents use the same prefix for different things.
 122 def merge(data, local):
 123         local_doc = minidom.parse(local)
 124         master_doc = minidom.parseString(data)
 125
 126         known_ids = set()
 127         def check_unique(elem):
 128                 impl_id = impl.getAttribute("id")
 129                 if impl_id in known_ids:
 130                         raise Exception("Duplicate ID " + impl_id)
 131                 known_ids.add(impl_id)
 132
 133         for impl in find_impls(master_doc.documentElement):
 134                 check_unique(impl)
 135
 136         # Merge each implementation in the local feed in turn (normally there will only be one)
 137         for impl in find_impls(local_doc.documentElement):
 138                 check_unique(impl)
 139
 140                 # 1. Get the context of the implementation to add. This is:
 141                 #    - The set of its requirements
 142                 #    - The set of its commands
 143                 #    - Its attributes
 144                 new_impl_context = Context(impl)
 145
 146                 # 2. For each <group> in the master feed, see if it provides a compatible context:
 147                 #    - A subset of the new implementation's requirements
 148                 #    - A subset of the new implementation's command names
 149                 #    - A subset of the new implementation's attributes (names, not values)
 150                 #    Choose the most compatible <group> (the root counts as a minimally compatible group)
 151
 152                 best_group = ((1, 0, 0), master_doc.documentElement)    # (score, element)
 153
 154                 for group in find_groups(master_doc.documentElement):
 155                         group_context = Context(group)
 156                         score = score_subset(group_context, new_impl_context)
 157                         if score > best_group[0]:
 158                                 best_group = (score, group)
 159
 160                 group = best_group[1]
 161                 group_context = Context(group)
 162
 163                 if new_impl_context.has_main_and_run:
 164                         # If the existing group doesn't have the same main value then we'll need a new group. Otherwise,
 165                         # we're likely to override the command by having main on the implementation element.
 166                         current_group_main = group_context.attribs.get((None, 'main'), None)
 167                         need_new_group_for_main = current_group_main != new_impl_context.attribs[(None, 'main')]
 168                 else:
 169                         need_new_group_for_main = False
 170
 171                 new_commands = []
 172                 for name_expr, new_command in new_impl_context.commands.iteritems():
 173                         if need_new_group_for_main and name_expr[0] == 'run':
 174                                 # If we're creating a new <group main='...'> then we can't inherit an existing <command name='run'/>,
 175                                 old_command = None
 176                         else:
 177                                 old_command = group_context.commands.get(name_expr, None)
 178                         if not (old_command and nodesEqual(old_command, new_command)):
 179                                 new_commands.append(xmltools.import_node(master_doc, new_command))
 180
 181                 # If we have additional requirements or commands, we'll need to create a subgroup and add them
 182                 if len(new_impl_context.requires) > len(group_context.requires) or new_commands or need_new_group_for_main:
 183                         subgroup = xmltools.create_element(group, 'group')
 184                         group = subgroup
 185                         #group_context = Context(group)
 186                         for x in new_impl_context.requires:
 187                                 for y in group_context.requires:
 188                                         if nodesEqual(x, y): break
 189                                 else:
 190                                         req = xmltools.import_node(master_doc, x)
 191                                         #print "Add", req
 192                                         xmltools.insert_element(req, group)
 193                         for c in new_commands:
 194                                 xmltools.insert_element(c, group)
 195
 196                         if need_new_group_for_main:
 197                                 group.setAttribute('main', new_impl_context.attribs[(None, 'main')])
 198                                 # We'll remove it from the <implementation> below, when cleaning up duplicates
 199
 200                         group_context = Context(group)
 201
 202                 new_impl = xmltools.import_node(master_doc, impl)
 203
 204                 # Attributes might have been set on a parent group; move to the impl
 205                 for name in new_impl_context.attribs:
 206                         #print "Set", name, value
 207                         xmltools.add_attribute_ns(new_impl, name[0], name[1], new_impl_context.attribs[name])
 208
 209                 for name, value in new_impl.attributes.itemsNS():
 210                         if name[0] == XMLNS_NAMESPACE or \
 211                            (name in group_context.attribs and group_context.attribs[name] == value):
 212                                 #print "Deleting duplicate attribute", name, value
 213                                 new_impl.removeAttributeNS(name[0], name[1])
 214
 215                 xmltools.insert_element(new_impl, group)
 216
 217         return master_doc.toxml('utf-8')