Clovis: update resource sack to use new dependency graph.

tools/android/loading/resource_sack.py

 # Copyright 2016 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.
 
 """A collection of ResourceGraphs.
 
 Processes multiple ResourceGraphs, all presumably from requests to the same
 site. Common urls are collected in Bags and different statistics on the
 relationship between bags are collected.
 """
 
 import collections
 import json
 import sys
 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
   them.
   """
   # See CoreSet().
   CORE_THRESHOLD = 0.8
 
   _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()
+    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)
 
-  def AddNode(self, graph, node):
+    # 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.
 
     The core set of a sack is the set of resource that are common to most of the
     graphs in the sack. A core set of a set of graphs are the resources that
     appear with frequency at least CORE_THRESHOLD. For a collection of graph
     sets, for instance pulling the same page under different network
     connections, we intersect the core sets to produce a page core set that
     describes the key resources used by the page. See https://goo.gl/LmqQRS for
@@ skipping 35 matching lines @@
   @property
   def num_graphs(self):
     return len(self.graph_info)
 
   @property
   def graph_info(self):
     return self._graph_info
 
   @property
   def bags(self):
-    return self._bags
+    return self._name_to_bag.values()
 
   def _SingleCore(self, graph_set):
     core = set()
     graph_set = set(graph_set)
     num_graphs = len(graph_set)
     for b in self.bags:
       count = sum([g in graph_set for g in b.graphs])
       if float(count) / num_graphs > self.CORE_THRESHOLD:
         core.add(b.label)
     return core
 
+  def _GetSackName(self, node):
+    return self._MakeShortname(node.request.url)
 
-class Bag(dag.Node):
-  def __init__(self, sack, index, url):
-    super(Bag, self).__init__(index)
+  @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(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):
     return self._label
 
   @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)
+    return sum(len(g) for g in self._graphs.itervalues())
 
-  def MarkCritical(self):
-    self._num_critical += 1
-
-  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)