src/chrome/common/extensions/docs/server2/api_schema_graph.py

   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
   5 import json
   6 from collections import Iterable, Mapping
   7
   8 class 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
  32 class _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
  54 def _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
  66 def _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
  74 def _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
  96 def _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
 116 def _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
 134 class 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