hphp/tools/header-deps

   1 #!/usr/bin/env php
   2 <?hh
   3
   4 function usage($name) {
   5   $format = <<<EOT
   6 Usage: %s [--dot] <filename>
   7
   8 This script looks for cycles in the include graph rooted at the given file,
   9 printing them if any are found. The return status is 0 if no cycles are found,
  10 and 1 otherwise. filename should be a path to any .h or .cpp file within hphp/,
  11 relative to cwd.
  12
  13 The logic to search for includes is very naive, and doesn't pay attention to
  14 #ifdefs.
  15
  16 If --dot is given, the header graph will be dumped as a dot graph instead,
  17 suitable for piping to something like `dot -T pdf -o out.pdf`. The leading
  18 hphp/ is stripped from filenames in this mode for readability. Files outside of
  19 hphp/ are treated as system includes and ignored.
  20
  21 EOT;
  22   fprintf(STDERR, $format, $name);
  23   exit(1);
  24 }
  25
  26 // Return an array of all headers included by $file, and whether or not it's a
  27 // system include (we treat anything outside of hphp/ as system for the
  28 // purposes of this tool).
  29 function get_file_headers($file) {
  30   $headers = [];
  31   if (!is_readable($file)) {
  32     fprintf(STDERR, "File %s does not exist\n", $file);
  33     exit(1);
  34   }
  35
  36   $f = fopen($file, 'r');
  37   while ($line = fgets($f)) {
  38     $line = trim($line);
  39     if (preg_match(
  40           '/^\s*#include ([<"])(.+)[>"]\s*$/', $line, &$matches
  41         ) !== 1) {
  42       continue;
  43     }
  44     $file = $matches[2];
  45     // Some files are build artifacts that don't live in the source tree. Treat
  46     // them as system files.
  47     $fake_systems = [
  48       'hphp/runtime/ir-opcode-generated.h' => true,
  49       'hphp/util/hphp-config.h' => true,
  50       'd6bb57672e27b8acd36563390cf86f2a4b111aed' => true,
  51     ];
  52     $system = strpos($file, 'hphp/') !== 0 ||
  53       isset($fake_systems[$file]) || isset($fake_systems[sha1($file)]);
  54     $headers[] = [
  55       'file' => $file,
  56       'system' => $system,
  57     ];
  58   }
  59   fclose($f);
  60   return $headers;
  61 }
  62
  63 function go_deps($file, &$visited, &$edges) {
  64   if (isset($visited[$file])) return;
  65   $visited[$file] = true;
  66
  67   foreach (get_file_headers($file) as $header) {
  68     if ($header['system']) continue;
  69     $target = $header['file'];
  70     $edges[$file][] = $target;
  71     if (!$header['system']) go_deps($target, &$visited, &$edges);
  72   }
  73 }
  74
  75 // Return the graph of header dependencies rooted at $file, as an array of
  76 // edges: [$from => [$dep1, $dep2, ...], ...].
  77 function get_all_deps(...$files) {
  78   $visited = [];
  79   $edges = [];
  80   foreach ($files as $file) {
  81     go_deps($file, &$visited, &$edges);
  82   }
  83   return $edges;
  84 }
  85
  86 // Return $s with an optional leading hphp/ stripped.
  87 function strip_hphp($s) {
  88   return preg_replace('/^hphp\//', '', $s);
  89 }
  90
  91 // Generate a dot graph from the output of get_all_deps().
  92 function make_dot_deps($deps) {
  93   $ret = "digraph {\n";
  94   foreach ($deps as $src => $headers) {
  95     foreach ($headers as $dst) {
  96       $ret .= sprintf("  \"%s\" -> \"%s\";\n",
  97                       strip_hphp($src), strip_hphp($dst));
  98     }
  99   }
 100   $ret .= "}\n";
 101   return $ret;
 102 }
 103
 104 // Find cycles using DFS with a stack representing the current path from the
 105 // root.
 106 function go_cycles($file, $deps, &$visited, &$stack, &$found) {
 107   $it = array_search($file, $stack);
 108   if ($it !== false) {
 109     $cycle = array_slice($stack, $it);
 110     $cycle[] = $file;
 111     if (!isset($found[$file]) ||
 112         array_search($cycle, $found[$file]) === false) {
 113         $found[$file][] = $cycle;
 114       }
 115     return;
 116   }
 117
 118   if (isset($visited[$file])) return;
 119   $visited[$file] = true;
 120
 121   if (!isset($deps[$file])) return;
 122
 123   $stack[] = $file;
 124   foreach ($deps[$file] as $dep) {
 125     go_cycles($dep, $deps, &$visited, &$stack, &$found);
 126   }
 127   array_pop(&$stack);
 128 }
 129
 130 // Look for cycles in the output of get_all_deps(). Return an array with all
 131 // unique cycles.
 132 function find_cycles($deps) {
 133   $visited = [];
 134   $stack = [];
 135   $found = [];
 136   foreach ($deps as $src => $headers) {
 137     go_cycles($src, $deps, &$visited, &$stack, &$found);
 138   }
 139   return $found;
 140 }
 141
 142 function main($argv) {
 143   if (count($argv) < 2 ||
 144       in_array('-h', $argv) || in_array('--help', $argv)) {
 145     usage($argv[0]);
 146   }
 147
 148   $do_dot = $argv[1] === '--dot';
 149
 150   // Canonicalize $file in case it wasn't give relative to hphp/'s parent,
 151   // where we want to work from.
 152   $files = array_map(
 153     $f ==> is_readable($f) ? realpath($f) : $f
 154         |> preg_replace('/.+\/hphp\//', 'hphp/', $$),
 155     array_slice($argv, $do_dot ? 2 : 1)
 156   );
 157   chdir(preg_replace('/\/hphp\/.*/', '', __DIR__));
 158   $deps = get_all_deps(...$files);
 159
 160   if ($argv[1] === '--dot') {
 161     echo make_dot_deps($deps);
 162     return 0;
 163   }
 164
 165   $cycles = find_cycles($deps);
 166   foreach ($cycles as $root => $list) {
 167     printf("%d cycles starting at %s:\n", count($list), $root);
 168     foreach ($list as $cycle) {
 169       foreach ($cycle as $elem) {
 170         printf("  %s\n", $elem);
 171       }
 172       printf("\n");
 173     }
 174   }
 175   return empty($cycles) ? 0 : 1;
 176 }
 177
 178 exit(main($argv));