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