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..705c9af0d2735ae8e8c721e0266e0e017b20238d
--- /dev/null
+++ b/chrome/common/extensions/docs/server2/api_schema_map.py
@@ -0,0 +1,97 @@
+# 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, node_type=None):

[not at google - send to devlin, 2013/09/12 20:34:23]

node_type is never used

[epeterson, 2013/09/12 22:39:10]

Done.

+  '''Recursively moves through an API schema, replacing lists of objects
+  for each attribute listed in |attributes| with a dict containing a
+  key for each object in the list.
+  '''
+  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] = {}

[not at google - send to devlin, 2013/09/12 20:34:23]

Is/can this be written similar to:

api_schema_map = dict(key, _CreateMap(value) for key, value in node.iteritems())

?

[epeterson, 2013/09/12 22:39:10]

I do want that check, but I tried to make it neater, and used a comprehension
because that's a cool idea.

Without the check, something like the ('namespace', 'tabs') pair would end up in
the dictionary as ('namespace', {}), which is useless here.

+      for key, value in node.iteritems():
+        # Recur on each (key, value) pair. The key becomes |node_type| and the
+        # value becomes the next |root|. The value will only pass the if/elif
+        # guard if it is a list or dict.
+        if isinstance(value, collections.Mapping) or _IsObjectList(value):
+          # Keep track of availability for 'objects' only.
+          api_schema_map[name][key] = _CreateMap(value, node_type=key)
+  elif isinstance(root, collections.Mapping):
+    for name, node in root.iteritems():
+      api_schema_map[name] = {}
+      for key, value in node.iteritems():
+        if isinstance(value, collections.Mapping) or _IsObjectList(value):
+          api_schema_map[name][key] = _CreateMap(value, node_type=key)
+
+  return api_schema_map
+
+
+def _Subtract(minuend, subtrahend):

[not at google - send to devlin, 2013/09/12 20:34:23]

I've never heard the terms "minuend" and "subtrahend" before, but, cool.

[epeterson, 2013/09/12 22:39:10]

I hadn't either.

[not at google - send to devlin, 2013/09/13 17:00:34]

Btw another convention I see sometimes is to use "lhs" and "rhs".

def _Subtract(self, lhs, rhs):
  pass

but I like the way you have it.

+  ''' A Set Difference adaptation for dicts. 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:
+      rest = _Subtract(minuend[key], subtrahend[key])

[not at google - send to devlin, 2013/09/12 20:34:23]

won't this break if minuend[key] or subtrahend[key] isn't a dict?

[epeterson, 2013/09/12 22:39:10]

Updated the comment -- but the parameters here need to be 'maps', so there
aren't any lists to worry about.

[not at google - send to devlin, 2013/09/13 17:00:34]

I'm.. not totally convinced. Why do they "need" to be maps?

[not at google - send to devlin, 2013/09/13 17:16:30]

Ah, because you create |_map| yourself. Never mind.

+      if rest:
+        # Record a difference if children of this key differed at some point.
+        difference[key] = rest
+  return difference
+
+
+class APISchemaMap(object):
+  '''Represents an API schema as a nested dict structure, where lists of
+  schema nodes are converted to dicts with a key representing each node.
+  '''
+
+  def __init__(self, api_schema):
+    self._map = _CreateMap(api_schema)
+
+  def Subtract(self, other_map):
+    '''Returns an APISchemaMap instance representing keys that are in
+    this map but not in the |other_map|.
+    '''
+    return APISchemaMap(_Subtract(self._map, other_map))

[not at google - send to devlin, 2013/09/12 20:34:23]

|other_map| should be an APISchemaMap, not... whatever it is. So I would expect
this function call to look like _Subtract(self._map, other._map). (i.e.
other_map -> other._map).

[epeterson, 2013/09/12 22:39:10]

Great, this makes things simpler for actually using this class in
AvailabilityFinder. (Wasn't sure if I could access private member data for
|other|)

[not at google - send to devlin, 2013/09/13 17:00:34]

This is fine here because it's private data that this class has knowledge of.

You'll notice in other languages like Java and C++ which enforce private via
compilation that they will allow this too. Methods like isEqual are always
implemented like that.

public boolean isEqual(Object other) {
  return this.someValue == other.someValue &&
         this.otherValue == other.someOtherValue;
}

+
+  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