| # 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. |
| |
| """Request dependency graph.""" |
| |
| import logging |
| import sys |
| |
| import common_util |
| import graph |
| import request_track |
| |
| |
| class RequestNode(graph.Node): |
| def __init__(self, request=None): |
| super(RequestNode, self).__init__() |
| self.request = request |
| self.cost = request.Cost() if request else None # Deserialization. |
| |
| def ToJsonDict(self): |
| json_dict = super(RequestNode, self).ToJsonDict() |
| json_dict.update({'request': self.request.ToJsonDict()}) |
| return json_dict |
| |
| @classmethod |
| def FromJsonDict(cls, json_dict): |
| result = super(RequestNode, cls).FromJsonDict(json_dict) |
| result.request = request_track.Request.FromJsonDict(json_dict['request']) |
| return common_util.DeserializeAttributesFromJsonDict( |
| json_dict, result, ['cost']) |
| |
| |
| class Edge(graph.Edge): |
| def __init__(self, from_node, to_node, reason=None): |
| super(Edge, self).__init__(from_node, to_node) |
| self.reason = reason |
| self.cost = None |
| self.is_timing = None |
| if from_node is None: # Deserialization. |
| return |
| self.reason = reason |
| self.cost = request_track.TimeBetween( |
| self.from_node.request, self.to_node.request, self.reason) |
| self.is_timing = False |
| |
| def ToJsonDict(self): |
| result = {} |
| return common_util.SerializeAttributesToJsonDict( |
| result, self, ['reason', 'cost', 'is_timing']) |
| |
| @classmethod |
| def FromJsonDict(cls, json_dict): |
| result = cls(None, None, None) |
| return common_util.DeserializeAttributesFromJsonDict( |
| json_dict, result, ['reason', 'cost', 'is_timing']) |
| |
| |
| class RequestDependencyGraph(object): |
| """Request dependency graph.""" |
| # This resource type may induce a timing dependency. See _SplitChildrenByTime |
| # for details. |
| # TODO(lizeb,mattcary): are these right? |
| _CAN_BE_TIMING_PARENT = set(['script', 'magic-debug-content']) |
| _CAN_MAKE_TIMING_DEPENDENCE = set(['json', 'other', 'magic-debug-content']) |
| |
| def __init__(self, requests, dependencies_lens, |
| node_class=RequestNode, edge_class=Edge): |
| """Creates a request dependency graph. |
| |
| Args: |
| requests: ([Request]) a list of requests. |
| dependencies_lens: (RequestDependencyLens) |
| node_class: (subclass of RequestNode) |
| edge_class: (subclass of Edge) |
| """ |
| self._requests = None |
| self._first_request_node = None |
| self._deps_graph = None |
| self._nodes_by_id = None |
| if requests is None: # Deserialization. |
| return |
| assert issubclass(node_class, RequestNode) |
| assert issubclass(edge_class, Edge) |
| self._requests = requests |
| deps = dependencies_lens.GetRequestDependencies() |
| self._nodes_by_id = {r.request_id : node_class(r) for r in self._requests} |
| edges = [] |
| for (parent_request, child_request, reason) in deps: |
| if (parent_request.request_id not in self._nodes_by_id |
| or child_request.request_id not in self._nodes_by_id): |
| continue |
| parent_node = self._nodes_by_id[parent_request.request_id] |
| child_node = self._nodes_by_id[child_request.request_id] |
| edges.append(edge_class(parent_node, child_node, reason)) |
| self._first_request_node = self._nodes_by_id[self._requests[0].request_id] |
| self._deps_graph = graph.DirectedGraph(self._nodes_by_id.values(), edges) |
| self._HandleTimingDependencies() |
| |
| @property |
| def graph(self): |
| """Return the Graph we're based on.""" |
| return self._deps_graph |
| |
| def UpdateRequestsCost(self, request_id_to_cost): |
| """Updates the cost of the nodes identified by their request ID. |
| |
| Args: |
| request_id_to_cost: ({request_id: new_cost}) Can be a superset of the |
| requests actually present in the graph. |
| """ |
| for node in self._deps_graph.Nodes(): |
| request_id = node.request.request_id |
| if request_id in request_id_to_cost: |
| node.cost = request_id_to_cost[request_id] |
| |
| def Cost(self, from_first_request=True, path_list=None, costs_out=None): |
| """Returns the cost of the graph, that is the costliest path. |
| |
| Args: |
| from_first_request: (boolean) If True, only considers paths that originate |
| from the first request node. |
| path_list: (list) See graph.Cost(). |
| costs_out: (list) See graph.Cost(). |
| """ |
| if from_first_request: |
| return self._deps_graph.Cost( |
| [self._first_request_node], path_list, costs_out) |
| else: |
| return self._deps_graph.Cost(path_list=path_list, costs_out=costs_out) |
| |
| def AncestorRequests(self, descendants): |
| """Return requests that are ancestors of a set of requests. |
| |
| Args: |
| descendants: ([Request]) List of requests. |
| |
| Returns: |
| List of Requests that are ancestors of descendants. |
| """ |
| return [n.request for n in self.graph.AncestorNodes( |
| self._nodes_by_id[r.request_id] for r in descendants)] |
| |
| def _HandleTimingDependencies(self): |
| try: |
| for n in self._deps_graph.TopologicalSort(): |
| self._SplitChildrenByTime(n) |
| except AssertionError as exc: |
| sys.stderr.write('Bad topological sort: %s\n' |
| 'Skipping child split\n' % str(exc)) |
| |
| def _SplitChildrenByTime(self, parent): |
| """Splits children of a node by request times. |
| |
| The initiator of a request may not be the true dependency of a request. For |
| example, a script may appear to load several resources independently, but in |
| fact one of them may be a JSON data file, and the remaining resources assets |
| described in the JSON. The assets should be dependent upon the JSON data |
| file, and not the original script. |
| |
| This function approximates that by rearranging the children of a node |
| according to their request times. The predecessor of each child is made to |
| be the node with the greatest finishing time, that is before the start time |
| of the child. |
| |
| We do this by sorting the nodes twice, once by start time and once by end |
| time. We mark the earliest end time, and then we walk the start time list, |
| advancing the end time mark when it is less than our current start time. |
| |
| This is refined by only considering assets which we believe actually create |
| a dependency. We only split if the original parent is a script, and the new |
| parent a data file. |
| We incorporate this heuristic by skipping over any non-script/json resources |
| when moving the end mark. |
| |
| TODO(mattcary): More heuristics, like incorporating cachability somehow, and |
| not just picking arbitrarily if there are two nodes with the same end time |
| (does that ever really happen?) |
| |
| Args: |
| parent: (_RequestNode) The children of this node are processed by this |
| function. |
| """ |
| if parent.request.GetContentType() not in self._CAN_BE_TIMING_PARENT: |
| return |
| edges = self._deps_graph.OutEdges(parent) |
| edges_by_start_time = sorted( |
| edges, key=lambda e: e.to_node.request.start_msec) |
| edges_by_end_time = sorted( |
| edges, key=lambda e: e.to_node.request.end_msec) |
| end_mark = 0 |
| for current in edges_by_start_time: |
| assert current.from_node is parent |
| if current.to_node.request.start_msec < parent.request.end_msec - 1e-5: |
| parent_url = parent.request.url |
| child_url = current.to_node.request.url |
| logging.warning('Child loaded before parent finished: %s -> %s', |
| request_track.ShortName(parent_url), |
| request_track.ShortName(child_url)) |
| go_to_next_child = False |
| while end_mark < len(edges_by_end_time): |
| if edges_by_end_time[end_mark] == current: |
| go_to_next_child = True |
| break |
| elif (edges_by_end_time[end_mark].to_node.request.GetContentType() |
| not in self._CAN_MAKE_TIMING_DEPENDENCE): |
| end_mark += 1 |
| elif (end_mark < len(edges_by_end_time) - 1 and |
| edges_by_end_time[end_mark + 1].to_node.request.end_msec |
| < current.to_node.request.start_msec): |
| end_mark += 1 |
| else: |
| break |
| if end_mark >= len(edges_by_end_time): |
| break # It's not possible to rearrange any more children. |
| if go_to_next_child: |
| continue # We can't rearrange this child, but the next child may be |
| # eligible. |
| if (edges_by_end_time[end_mark].to_node.request.end_msec |
| <= current.to_node.request.start_msec): |
| current.is_timing = True |
| self._deps_graph.UpdateEdge( |
| current, edges_by_end_time[end_mark].to_node, |
| current.to_node) |
| |
| def ToJsonDict(self): |
| result = {'graph': self.graph.ToJsonDict()} |
| result['requests'] = [r.ToJsonDict() for r in self._requests] |
| return result |
| |
| @classmethod |
| def FromJsonDict(cls, json_dict, node_class, edge_class): |
| result = cls(None, None) |
| graph_dict = json_dict['graph'] |
| g = graph.DirectedGraph.FromJsonDict(graph_dict, node_class, edge_class) |
| result._requests = [request_track.Request.FromJsonDict(r) |
| for r in json_dict['requests']] |
| result._nodes_by_id = {node.request.request_id: node |
| for node in g.Nodes()} |
| result._first_request_node = result._nodes_by_id[ |
| result._requests[0].request_id] |
| result._deps_graph = g |
| return result |
