1#!/usr/bin/env python
2# Copyright (c) 2012 The Chromium Authors. All rights reserved.
3# Use of this source code is governed by a BSD-style license that can be
4# found in the LICENSE file.
5
6"""Prints paths between gyp targets.
7"""
8
9import json
10import os
11import sys
12import time
13
14from collections import deque
15
16def usage():
17  print """\
18Usage:
19  tools/gyp-explain.py [--dot] chrome_dll# gtest#
20"""
21
22
23def GetPath(graph, fro, to):
24  """Given a graph in (node -> list of successor nodes) dictionary format,
25  yields all paths from |fro| to |to|, starting with the shortest."""
26  # Storing full paths in the queue is a bit wasteful, but good enough for this.
27  q = deque([(fro, [])])
28  while q:
29    t, path = q.popleft()
30    if t == to:
31      yield path + [t]
32    for d in graph[t]:
33      q.append((d, path + [t]))
34
35
36def MatchNode(graph, substring):
37  """Given a dictionary, returns the key that matches |substring| best. Exits
38  if there's not one single best match."""
39  candidates = []
40  for target in graph:
41    if substring in target:
42      candidates.append(target)
43
44  if not candidates:
45    print 'No targets match "%s"' % substring
46    sys.exit(1)
47  if len(candidates) > 1:
48    print 'More than one target matches "%s": %s' % (
49        substring, ' '.join(candidates))
50    sys.exit(1)
51  return candidates[0]
52
53
54def EscapeForDot(string):
55  suffix = '#target'
56  if string.endswith(suffix):
57    string = string[:-len(suffix)]
58  string = string.replace('\\', '\\\\')
59  return '"' + string + '"'
60
61
62def GenerateDot(fro, to, paths):
63  """Generates an input file for graphviz's dot program."""
64  prefixes = [os.path.commonprefix(path) for path in paths]
65  prefix = os.path.commonprefix(prefixes)
66  print '// Build with "dot -Tpng -ooutput.png this_file.dot"'
67  # "strict" collapses common paths.
68  print 'strict digraph {'
69  for path in paths:
70    print (' -> '.join(EscapeForDot(item[len(prefix):]) for item in path)), ';'
71  print '}'
72
73
74def Main(argv):
75  # Check that dump.json exists and that it's not too old.
76  dump_json_dirty = False
77  try:
78    st = os.stat('dump.json')
79    file_age_s = time.time() - st.st_mtime
80    if file_age_s > 2 * 60 * 60:
81      print 'dump.json is more than 2 hours old.'
82      dump_json_dirty = True
83  except OSError:
84    print 'dump.json not found.'
85    dump_json_dirty = True
86
87  if dump_json_dirty:
88    print 'Run'
89    print '    GYP_GENERATORS=dump_dependency_json build/gyp_chromium'
90    print 'first, then try again.'
91    sys.exit(1)
92
93  g = json.load(open('dump.json'))
94
95  if len(argv) not in (3, 4):
96    usage()
97    sys.exit(1)
98
99  generate_dot = argv[1] == '--dot'
100  if generate_dot:
101    argv.pop(1)
102
103  fro = MatchNode(g, argv[1])
104  to = MatchNode(g, argv[2])
105
106  paths = list(GetPath(g, fro, to))
107  if len(paths) > 0:
108    if generate_dot:
109      GenerateDot(fro, to, paths)
110    else:
111      print 'These paths lead from %s to %s:' % (fro, to)
112      for path in paths:
113        print ' -> '.join(path)
114  else:
115    print 'No paths found from %s to %s.' % (fro, to)
116
117
118if __name__ == '__main__':
119  Main(sys.argv)
120