merge.py

   1 import os
   2 from xml.dom import minidom, XMLNS_NAMESPACE, Node
   3 from zeroinstall.injector.namespaces import XMLNS_IFACE
   4 from zeroinstall.injector import model, reader
   5 from logging import info
   6 import xmltools
   7
   8 def childNodes(parent, namespaceURI = None, localName = None):
   9         for x in parent.childNodes:
  10                 if x.nodeType != Node.ELEMENT_NODE: continue
  11                 if namespaceURI is not None and x.namespaceURI != namespaceURI: continue
  12
  13                 if localName is None or x.localName == localName:
  14                         yield x
  15
  16 class Context:
  17         def __init__(self, impl):
  18                 doc = impl.ownerDocument
  19                 self.attribs = {}
  20                 self.requires = []
  21
  22                 node = impl
  23                 while True:
  24                         for name, value in node.attributes.itemsNS():
  25                                 if name[0] == XMLNS_NAMESPACE:
  26                                         xmltools.register_namespace(value, name[1])
  27                                 elif name not in self.attribs:
  28                                         self.attribs[name] = value
  29                         if node.nodeName == 'group':
  30                                 # We don't care about <requires> inside <implementation>; they'll get copied over anyway
  31                                 for x in childNodes(node, XMLNS_IFACE, 'requires'):
  32                                         self.requires.append(x)
  33                         node = node.parentNode
  34                         if node.nodeName != 'group':
  35                                 break
  36
  37 def find_impls(parent):
  38         """Return all <implementation> children, including those inside groups."""
  39         for x in childNodes(parent, XMLNS_IFACE):
  40                 if x.localName == 'implementation':
  41                         yield x
  42                 elif x.localName == 'group':
  43                         for y in find_impls(x):
  44                                 yield y
  45
  46 def find_groups(parent):
  47         """Return all <group> children, including those inside other groups."""
  48         for x in childNodes(parent, XMLNS_IFACE, 'group'):
  49                 yield x
  50                 for y in find_groups(x):
  51                         yield y
  52
  53 def nodesEqual(a, b):
  54         assert a.nodeType == Node.ELEMENT_NODE
  55         assert b.nodeType == Node.ELEMENT_NODE
  56
  57         if a.namespaceURI != b.namespaceURI:
  58                 return False
  59
  60         if a.nodeName != b.nodeName:
  61                 return False
  62
  63         a_attrs = set(["%s %s" % (name, value) for name, value in a.attributes.itemsNS()])
  64         b_attrs = set(["%s %s" % (name, value) for name, value in b.attributes.itemsNS()])
  65
  66         if a_attrs != b_attrs:
  67                 #print "%s != %s" % (a_attrs, b_attrs)
  68                 return False
  69
  70         a_children = list(childNodes(a))
  71         b_children = list(childNodes(b))
  72
  73         if len(a_children) != len(b_children):
  74                 return False
  75
  76         for a_child, b_child in zip(a_children, b_children):
  77                 if not nodesEqual(a_child, b_child):
  78                         return False
  79
  80         return True
  81
  82 def score_subset(group, impl):
  83         """Returns (is_subset, goodness)"""
  84         for key in group.attribs:
  85                 if key not in impl.attribs.keys():
  86                         #print "BAD", key
  87                         return (0,)             # Group sets an attribute the impl doesn't want
  88         for g_req in group.requires:
  89                 for i_req in impl.requires:
  90                         if nodesEqual(g_req, i_req): break
  91                 else:
  92                         return (0,)             # Group adds a requires that the impl doesn't want
  93         # Score result so we get groups that have all the same requires first, then ones with all the same attribs
  94         return (1, len(group.requires), len(group.attribs))
  95
  96 # Note: the namespace stuff isn't quite right yet.
  97 # Might get conflicts if both documents use the same prefix for different things.
  98 def merge(data, local):
  99         local_doc = minidom.parse(local)
 100         master_doc = minidom.parseString(data)
 101
 102         # Merge each implementation in the local feed in turn (normally there will only be one)
 103         for impl in find_impls(local_doc.documentElement):
 104                 # 1. Get the context of the implementation to add. This is:
 105                 #    - The set of its requirements
 106                 #    - Its attributes
 107                 new_impl_context = Context(impl)
 108
 109                 # 2. For each <group> in the master feed, see if it provides a compatible context:
 110                 #    - A subset of the new implementation's requirements
 111                 #    - A subset of the new implementation's attributes (names, not values)
 112                 #    Choose the most compatible <group> (the root counts as a minimally compatible group)
 113
 114                 best_group = ((1, 0, 0), master_doc.documentElement)    # (score, element)
 115
 116                 for group in find_groups(master_doc.documentElement):
 117                         group_context = Context(group)
 118                         score = score_subset(group_context, new_impl_context)
 119                         if score > best_group[0]:
 120                                 best_group = (score, group)
 121
 122                 group = best_group[1]
 123                 group_context = Context(group)
 124
 125                 # If we have additional requirements, we'll need to create a subgroup and add them
 126                 if len(new_impl_context.requires) > len(group_context.requires):
 127                         subgroup = xmltools.create_element(group, 'group')
 128                         group = subgroup
 129                         group_context = Context(group)
 130                         for x in new_impl_context.requires:
 131                                 for y in group_context.requires:
 132                                         if nodesEqual(x, y): break
 133                                 else:
 134                                         req = master_doc.importNode(x, True)
 135                                         #print "Add", req
 136                                         xmltools.insert_element(req, group)
 137
 138                 new_impl = master_doc.importNode(impl, True)
 139
 140                 # Attributes might have been set on a parent group; move to the impl
 141                 for name in new_impl_context.attribs:
 142                         #print "Set", name, value
 143                         xmltools.add_attribute_ns(new_impl, name[0], name[1], new_impl_context.attribs[name])
 144
 145                 for name, value in new_impl.attributes.itemsNS():
 146                         if name[0] == XMLNS_NAMESPACE or \
 147                            (name in group_context.attribs and group_context.attribs[name] == value):
 148                                 #print "Deleting duplicate attribute", name, value
 149                                 new_impl.removeAttributeNS(name[0], name[1])
 150
 151                 xmltools.insert_element(new_impl, group)
 152
 153         return master_doc.toxml()