Adding APISchemaGraph class to Extensions Docserver.

chrome/common/extensions/docs/server2/api_schema_map.py

Index: chrome/common/extensions/docs/server2/api_schema_map.py
diff --git a/chrome/common/extensions/docs/server2/api_schema_map.py b/chrome/common/extensions/docs/server2/api_schema_map.py
new file mode 100644
index 0000000000000000000000000000000000000000..742c2326576e763a7f342e49cd3efb5014f05061
--- /dev/null
+++ b/chrome/common/extensions/docs/server2/api_schema_map.py
@@ -0,0 +1,89 @@
+# 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 collections
+import json
+
+
+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']
+  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, collections.Iterable) and
+          all(isinstance(node, collections.Mapping) for node in value))
+
+
+def _CreateMap(root):
+  '''Recursively moves through an API schema, replacing lists of objects
+  and non-object values with objects.
+  '''
+  api_schema_map = {}
+  if _IsObjectList(root):
+    for node in root:
+      name = _NameForNode(node)
+      assert name not in api_schema_map, 'Duplicate name in availability map.'
+      api_schema_map[name] = dict((key, _CreateMap(value)) for key, value
+                                  in node.iteritems())
+  elif isinstance(root, collections.Mapping):
+    for name, node in root.iteritems():
+      api_schema_map[name] = dict((key, _CreateMap(value)) for key, value
+                                  in node.iteritems())
+  return api_schema_map
+
+
+def _Subtract(minuend, subtrahend):
+  ''' A Set Difference adaptation for maps. Returns a |difference|,
+  which contains key-value pairs found in |minuend| but not in
+  |subtrahend|.
+  '''
+  difference = {}
+  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 maps, 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
+
+
+class APISchemaMap(object):

[not at google - send to devlin, 2013/09/16 14:06:24]

I preferred Graph, and "graph" naming rather than "map". I wasn't thinking
properly when you made that change, sorry.

Map implies it's a map of something to API schema, which it's not. It's a graph
representation of a schema. Or maybe it's a tree?

[epeterson, 2013/09/16 17:47:23]

Done. I considered 'tree' earlier on but decided it looked a little silly.

+  '''Provides an interface for interacting with an API schema map, a
+  nested dict structure that allows for simpler lookups of schema data.
+  '''
+
+  def __init__(self, api_schema):
+    self._map = _CreateMap(api_schema)
+
+  def Subtract(self, other):
+    '''Returns an APISchemaMap instance representing keys that are in
+    this map but not in |other|.
+    '''
+    return APISchemaMap(_Subtract(self._map, other._map))
+
+  def Lookup(self, *path):
+    '''Given a list of path components, |path|, checks if the
+    APISchemaMap instance contains |path|.
+    '''
+    node = self._map
+    for path_piece in path:
+      node = node.get(path_piece)
+      if node is None:
+        return False
+    return True