Clovis: update resource sack to use new dependency graph.

tools/android/loading/resource_sack.py

Index: tools/android/loading/resource_sack.py
diff --git a/tools/android/loading/resource_sack.py b/tools/android/loading/resource_sack.py
index 90ced3801c92a6844d34d98731be4f80cea4228e..ce6dcb2bd34f4a42ab13cfafd24a402a223b0d2f 100644
--- a/tools/android/loading/resource_sack.py
+++ b/tools/android/loading/resource_sack.py
@@ -17,16 +17,16 @@ import urlparse
 from collections import defaultdict
 
 import content_classification_lens
-import dag
+import graph
 import user_satisfied_lens
 
 class GraphSack(object):
-  """Aggreate of ResourceGraphs.
+  """Aggreate of RequestDependencyGraphs.
 
-  Collects ResourceGraph nodes into bags, where each bag contains the nodes with
-  common urls. Dependency edges are tracked between bags (so that each bag may
-  be considered as a node of a graph). This graph of bags is referred to as a
-  sack.
+  Collects RequestDependencyGraph nodes into bags, where each bag contains the
+  nodes with common urls. Dependency edges are tracked between bags (so that
+  each bag may be considered as a node of a graph). This graph of bags is
+  referred to as a sack.
 
   Each bag is associated with a dag.Node, even though the bag graph may not be a
   DAG. The edges are annotated with list of graphs and nodes that generated
@@ -37,55 +37,57 @@ class GraphSack(object):
 
   _GraphInfo = collections.namedtuple('_GraphInfo', (
       'cost',   # The graph cost (aka critical path length).
-      'total_costs',  # A vector by node index of total cost of each node.
       ))
 
   def __init__(self):
-    # A bag is a node in our combined graph.
-    self._bags = []
-    # Each bag in our sack corresponds to a url, as expressed by this map.
-    self._url_to_bag = {}
+    # Each bag in our sack is named as indicated by this map.
+    self._name_to_bag = {}
+    # List our edges by bag pairs: (from_bag, to_bag) -> graph.Edge.
+    self._edges = {}
     # Maps graph -> _GraphInfo structures for each graph we've consumed.
     self._graph_info = {}
 
-  def ConsumeGraph(self, graph):
+    # Our graph, updated after each ConsumeGraph.
+    self._graph = None
+
+  def ConsumeGraph(self, request_graph):
     """Add a graph and process.
 
     Args:
-      graph: (ResourceGraph) the graph to add. The graph is processed sorted
-        according to its current filter.
+      graph: (RequestDependencyGraph) the graph to add. The graph is processed
+        sorted according to its current filter.

[Benoit L, 2016/03/29 13:45:50]

nit: There are no filters anymore.

[mattcary, 2016/03/29 13:56:07]

Done.

     """
     assert graph not in self._graph_info
-    critical_path = []
-    total_costs = []
-    cost = graph.Cost(path_list=critical_path,
-                      costs_out=total_costs)
-    self._graph_info[graph] = self._GraphInfo(
-        cost=cost, total_costs=total_costs)
-    for n in graph.Nodes(sort=True):
-      assert graph._node_filter(n.Node())
-      self.AddNode(graph, n)
-    for node in critical_path:
-      self._url_to_bag[node.Url()].MarkCritical()
-
-  def AddNode(self, graph, node):
+    cost = request_graph.Cost()
+    self._graph_info[request_graph] = self._GraphInfo(cost=cost)
+    for n in request_graph.graph.Nodes():

[Benoit L, 2016/03/29 13:45:50]

The nodes are no longer sorted, is it an issue? (beyond testing)

[mattcary, 2016/03/29 13:56:07]

No. The idea was that because adding nodes transitively adds descendants, doing
it over sorted nodes was more efficient. I'm not actually sure that's true, and
anyway since (I think/hope) it doesn't affect correctness it's doesn't really
matter.

+      self.AddNode(request_graph, n)
+
+    # TODO(mattcary): this is inefficient but our current API doesn't require an
+    # explicit graph creation from the client.
+    self._graph = graph.DirectedGraph(self.bags, self._edges.itervalues())
+
+  def AddNode(self, request_graph, node):
     """Add a node to our collection.
 
     Args:
-      graph: (ResourceGraph) the graph in which the node lives.
-      node: (NodeInfo) the node to add.
+      graph: (RequestDependencyGraph) the graph in which the node lives.
+      node: (RequestDependencyGraph node) the node to add.
 
     Returns:
       The Bag containing the node.
     """
-    if not graph._node_filter(node):
-      return
-    if node.Url() not in self._url_to_bag:
-      new_index = len(self._bags)
-      self._bags.append(Bag(self, new_index, node.Url()))
-      self._url_to_bag[node.Url()] = self._bags[-1]
-    self._url_to_bag[node.Url()].AddNode(graph, node)
-    return self._url_to_bag[node.Url()]
+    sack_name = self._GetSackName(node)
+    if sack_name not in self._name_to_bag:
+      self._name_to_bag[sack_name] = Bag(self, sack_name)
+    bag = self._name_to_bag[sack_name]
+    bag.AddNode(request_graph, node)
+    return bag
+
+  def AddEdge(self, from_bag, to_bag):
+    """Add an edge between two bags."""
+    if (from_bag, to_bag) not in self._edges:
+      self._edges[(from_bag, to_bag)] = graph.Edge(from_bag, to_bag)
 
   def CoreSet(self, *graph_sets):
     """Compute the core set of this sack.
@@ -141,7 +143,7 @@ class GraphSack(object):
 
   @property
   def bags(self):
-    return self._bags
+    return self._name_to_bag.values()
 
   def _SingleCore(self, graph_set):
     core = set()
@@ -153,31 +155,30 @@ class GraphSack(object):
         core.add(b.label)
     return core
 
+  def _GetSackName(self, node):
+    return self._MakeShortname(node.request.url)
+
+  @classmethod
+  def _MakeShortname(cls, url):

[Benoit L, 2016/03/29 13:45:50]

nit: Add a TODO(lizeb) to move this method elsewhere, while you're touching it.
It's copied in a couple places.

[mattcary, 2016/03/29 13:56:07]

Done.

Note it's not exactly copied... but I agree the variations are immaterial and we
should standardize somehow. Note also that in the very new future I think I'll
want to do approximate URL matching, so it might be best to wait for that to
shake out before spending time on this.

+    parsed = urlparse.urlparse(url)
+    if parsed.scheme == 'data':
+      if ';' in parsed.path:
+        kind, _ = parsed.path.split(';', 1)
+      else:
+        kind, _ = parsed.path.split(',', 1)
+      return 'data:' + kind
+    path = parsed.path[:10]
+    hostname = parsed.hostname if parsed.hostname else '?.?.?'
+    return hostname + '/' + path
+
 
-class Bag(dag.Node):
-  def __init__(self, sack, index, url):
-    super(Bag, self).__init__(index)
+class Bag(graph.Node):
+  def __init__(self, sack, label):
+    super(Bag, self).__init__()
     self._sack = sack
-    self._url = url
-    self._label = self._MakeShortname(url)
+    self._label = label
     # Maps a ResourceGraph to its Nodes contained in this Bag.
     self._graphs = defaultdict(set)
-    # Maps each successor bag to the set of (graph, node, graph-successor)
-    # tuples that generated it.
-    self._successor_sources = defaultdict(set)
-    # Maps each successor bag to a set of edge costs. This is just used to
-    # track min and max; if we want more statistics we'd have to count the
-    # costs with multiplicity.
-    self._successor_edge_costs = defaultdict(set)
-
-    # Miscellaneous counts and costs used in display.
-    self._total_costs = []
-    self._relative_costs = []
-    self._num_critical = 0
-
-  @property
-  def url(self):
-    return self._url
 
   @property
   def label(self):
@@ -185,62 +186,16 @@ class Bag(dag.Node):
 
   @property
   def graphs(self):
-    return self._graphs
-
-  @property
-  def successor_sources(self):
-    return self._successor_sources
-
-  @property
-  def successor_edge_costs(self):
-    return self._successor_edge_costs
-
-  @property
-  def total_costs(self):
-    return self._total_costs
-
-  @property
-  def relative_costs(self):
-    return self._relative_costs
-
-  @property
-  def num_critical(self):
-    return self._num_critical
+    return self._graphs.iterkeys()
 
   @property
   def num_nodes(self):
-    return len(self._total_costs)
-
-  def MarkCritical(self):
-    self._num_critical += 1
+    return sum(len(g) for g in self._graphs.itervalues())
 
-  def AddNode(self, graph, node):
-    if node in self._graphs[graph]:
+  def AddNode(self, request_graph, node):
+    if node in self._graphs[request_graph]:
       return  # Already added.
-    graph_info = self._sack.graph_info[graph]
-    self._graphs[graph].add(node)
-    node_total_cost = graph_info.total_costs[node.Index()]
-    self._total_costs.append(node_total_cost)
-    self._relative_costs.append(
-        float(node_total_cost) / graph_info.cost)
-    for s in node.Node().Successors():
-      if not graph._node_filter(s):
-        continue
-      node_info = graph.NodeInfo(s)
-      successor_bag = self._sack.AddNode(graph, node_info)
-      self.AddSuccessor(successor_bag)
-      self._successor_sources[successor_bag].add((graph, node, s))
-      self._successor_edge_costs[successor_bag].add(graph.EdgeCost(node, s))
-
-  @classmethod
-  def _MakeShortname(cls, url):
-    parsed = urlparse.urlparse(url)
-    if parsed.scheme == 'data':
-      if ';' in parsed.path:
-        kind, _ = parsed.path.split(';', 1)
-      else:
-        kind, _ = parsed.path.split(',', 1)
-      return 'data:' + kind
-    path = parsed.path[:10]
-    hostname = parsed.hostname if parsed.hostname else '?.?.?'
-    return hostname + '/' + path
+    self._graphs[request_graph].add(node)
+    for edge in request_graph.graph.OutEdges(node):
+      out_bag = self._sack.AddNode(request_graph, edge.to_node)
+      self._sack.AddEdge(self, out_bag)