1# Copyright 2013 The Chromium Authors. All rights reserved. 2# Use of this source code is governed by a BSD-style license that can be 3# found in the LICENSE file. 4 5import json 6from collections import Iterable, Mapping 7 8class LookupResult(object): 9 '''Returned from APISchemaGraph.Lookup(), and relays whether or not 10 some element was found and what annotation object was associated with it, 11 if any. 12 ''' 13 14 def __init__(self, found=None, annotation=None): 15 assert found is not None, 'LookupResult was given None value for |found|.' 16 self.found = found 17 self.annotation = annotation 18 19 def __eq__(self, other): 20 return self.__dict__ == other.__dict__ 21 22 def __ne__(self, other): 23 return not (self == other) 24 25 def __repr__(self): 26 return '%s%s' % (type(self).__name__, repr(self.__dict__)) 27 28 def __str__(self): 29 return repr(self) 30 31 32class _GraphNode(dict): 33 '''Represents some element of an API schema, and allows extra information 34 about that element to be stored on the |_annotation| object. 35 ''' 36 37 def __init__(self, *args, **kwargs): 38 # Use **kwargs here since Python is picky with ordering of default args 39 # and variadic args in the method signature. The only keyword arg we care 40 # about here is 'annotation'. Intentionally don't pass |**kwargs| into the 41 # superclass' __init__(). 42 dict.__init__(self, *args) 43 self._annotation = kwargs.get('annotation') 44 45 def __eq__(self, other): 46 # _GraphNode inherits __eq__() from dict, which will not take annotation 47 # objects into account when comparing. 48 return dict.__eq__(self, other) 49 50 def __ne__(self, other): 51 return not (self == other) 52 53 54def _NameForNode(node): 55 '''Creates a unique id for an object in an API schema, depending on 56 what type of attribute the object is a member of. 57 ''' 58 if 'namespace' in node: return node['namespace'] 59 if 'name' in node: return node['name'] 60 if 'id' in node: return node['id'] 61 if 'type' in node: return node['type'] 62 if '$ref' in node: return node['$ref'] 63 assert False, 'Problems with naming node: %s' % json.dumps(node, indent=3) 64 65 66def _IsObjectList(value): 67 '''Determines whether or not |value| is a list made up entirely of 68 dict-like objects. 69 ''' 70 return (isinstance(value, Iterable) and 71 all(isinstance(node, Mapping) for node in value)) 72 73 74def _CreateGraph(root): 75 '''Recursively moves through an API schema, replacing lists of objects 76 and non-object values with objects. 77 ''' 78 schema_graph = _GraphNode() 79 if _IsObjectList(root): 80 for node in root: 81 name = _NameForNode(node) 82 assert name not in schema_graph, 'Duplicate name in API schema graph.' 83 schema_graph[name] = _GraphNode((key, _CreateGraph(value)) for 84 key, value in node.iteritems()) 85 86 elif isinstance(root, Mapping): 87 for name, node in root.iteritems(): 88 if not isinstance(node, Mapping): 89 schema_graph[name] = _GraphNode() 90 else: 91 schema_graph[name] = _GraphNode((key, _CreateGraph(value)) for 92 key, value in node.iteritems()) 93 return schema_graph 94 95 96def _Subtract(minuend, subtrahend): 97 ''' A Set Difference adaptation for graphs. Returns a |difference|, 98 which contains key-value pairs found in |minuend| but not in 99 |subtrahend|. 100 ''' 101 difference = _GraphNode() 102 for key in minuend: 103 if key not in subtrahend: 104 # Record all of this key's children as being part of the difference. 105 difference[key] = _Subtract(minuend[key], {}) 106 else: 107 # Note that |minuend| and |subtrahend| are assumed to be graphs, and 108 # therefore should have no lists present, only keys and nodes. 109 rest = _Subtract(minuend[key], subtrahend[key]) 110 if rest: 111 # Record a difference if children of this key differed at some point. 112 difference[key] = rest 113 return difference 114 115 116def _Update(base, addend, annotation=None): 117 '''A Set Union adaptation for graphs. Returns a graph which contains 118 the key-value pairs from |base| combined with any key-value pairs 119 from |addend| that are not present in |base|. 120 ''' 121 for key in addend: 122 if key not in base: 123 # Add this key and the rest of its children. 124 base[key] = _Update(_GraphNode(annotation=annotation), 125 addend[key], 126 annotation=annotation) 127 else: 128 # The key is already in |base|, but check its children. 129 _Update(base[key], addend[key], annotation=annotation) 130 return base 131 132 133 134class APISchemaGraph(object): 135 '''Provides an interface for interacting with an API schema graph, a 136 nested dict structure that allows for simpler lookups of schema data. 137 ''' 138 139 def __init__(self, api_schema=None, _graph=None): 140 self._graph = _graph if _graph is not None else _CreateGraph(api_schema) 141 142 def __eq__(self, other): 143 return self._graph == other._graph 144 145 def __ne__(self, other): 146 return not (self == other) 147 148 def Subtract(self, other): 149 '''Returns an APISchemaGraph instance representing keys that are in 150 this graph but not in |other|. 151 ''' 152 return APISchemaGraph(_graph=_Subtract(self._graph, other._graph)) 153 154 def Update(self, other, annotation=None): 155 '''Modifies this graph by adding keys from |other| that are not 156 already present in this graph. 157 ''' 158 _Update(self._graph, other._graph, annotation=annotation) 159 160 def Lookup(self, *path): 161 '''Given a list of path components, |path|, checks if the 162 APISchemaGraph instance contains |path|. 163 ''' 164 node = self._graph 165 for path_piece in path: 166 node = node.get(path_piece) 167 if node is None: 168 return LookupResult(found=False, annotation=None) 169 return LookupResult(found=True, annotation=node._annotation) 170 171 def IsEmpty(self): 172 '''Checks for an empty schema graph. 173 ''' 174 return not self._graph 175