tools/treeshake.cc

   1 // Read a set of lines on stdin of the following form:
   2 //  definition:
   3 //    ...
   4 //    ...
   5 //
   6 // Delete all 'dead' definitions with following indented lines that aren't
   7 // used outside their bodies.
   8 //
   9 // This can be transitive; deleting one definition may cause other definitions
  10 // to become dead.
  11 //
  12 // Also assorts segments as a side-effect.
  13 //
  14 // Like linkify, treeshake is a hack.
  15
  16 #include<assert.h>
  17
  18 #include<map>
  19 using std::map;
  20 #include<vector>
  21 using std::vector;
  22 #define SIZE(X) (assert((X).size() < (1LL<<(sizeof(int)*8-2))), static_cast<int>((X).size()))
  23
  24 #include<string>
  25 using std::string;
  26
  27 #include<iostream>
  28 using std::cin;
  29 using std::cout;
  30 using std::cerr;
  31
  32 #include<sstream>
  33 using std::istringstream;
  34
  35 bool starts_with(const string& s, const string& pat) {
  36   string::const_iterator a=s.begin(), b=pat.begin();
  37   for (/*nada*/;  a!=s.end() && b!=pat.end();  ++a, ++b)
  38     if (*a != *b) return false;
  39   return b == pat.end();
  40 }
  41
  42 // input
  43
  44 void read_body(string name, string definition_line, map<string, vector<string> >& segment) {
  45   // last definition wins; this only matters for the 'Entry' label in the code segment
  46   segment[name] = vector<string>();
  47   segment[name].push_back(definition_line);
  48   while (!cin.eof()) {
  49     if (cin.peek() != ' ' && cin.peek() != '$') break;  // assumes: no whitespace but spaces; internal labels start with '$'
  50     string line;
  51     getline(cin, line);
  52     segment[name].push_back(line);
  53   }
  54 }
  55
  56 void read_lines(string segment_header, map<string, vector<string> >& segment) {
  57   // first segment header wins
  58   if (segment.empty())
  59     segment["=="].push_back(segment_header);  // '==' is a special key containing the segment header
  60   while (!cin.eof()) {
  61     if (cin.peek() == '=') break;  // assumes: no line can start with '=' except a segment header
  62     assert(cin.peek() != ' ');  // assumes: no whitespace but spaces
  63     string line;
  64     getline(cin, line);
  65     istringstream lstream(line);
  66     string name;
  67     getline(lstream, name, ' ');
  68     assert(name[SIZE(name)-1] == ':');
  69     name.erase(--name.end());
  70     read_body(name, line, segment);
  71   }
  72 }
  73
  74 void read_lines(map<string, vector<string> >& code, map<string, vector<string> >& data) {
  75   while (!cin.eof()) {
  76     string line;
  77     getline(cin, line);
  78     assert(starts_with(line, "== "));
  79     map<string, vector<string> >& curr = (line.substr(3, 4) == "code") ? code : data;  // HACK: doesn't support segments except 'code' and 'data'
  80     read_lines(line, curr);
  81   }
  82 }
  83
  84 // treeshake
  85
  86 bool any_line_matches(string pat, const vector<string>& lines) {
  87   for (int i = 0;  i < SIZE(lines);  ++i)
  88     if (lines.at(i).find(pat) != string::npos)  // conservative: confused by word boundaries, comments and string literals
  89       return true;
  90   return false;
  91 }
  92
  93 bool is_dead(string key, const map<string, vector<string> >& code, const map<string, vector<string> >& data) {
  94   if (key == "Entry") return false;
  95   if (key == "==") return false;
  96   for (map<string, vector<string> >::const_iterator p = code.begin();  p != code.end();  ++p) {
  97     if (p->first == key) continue;
  98     if (any_line_matches(key, p->second)) return false;
  99   }
 100   for (map<string, vector<string> >::const_iterator p = data.begin();  p != data.end();  ++p) {
 101     if (p->first == key) continue;
 102     if (any_line_matches(key, p->second)) return false;
 103   }
 104   return true;
 105 }
 106
 107 void treeshake(map<string, vector<string> >& code, map<string, vector<string> >& data) {
 108   for (map<string, vector<string> >::iterator p = code.begin();  p != code.end();  ++p) {
 109     if (is_dead(p->first, code, data)) {
 110 //?       cerr << "  erasing " << p->first << '\n';
 111       code.erase(p);
 112       return;
 113     }
 114   }
 115   for (map<string, vector<string> >::iterator p = data.begin();  p != data.end();  ++p) {
 116     if (is_dead(p->first, code, data)) {
 117 //?       cerr << "  erasing " << p->first << '\n';
 118       data.erase(p);
 119       return;
 120     }
 121   }
 122 }
 123
 124 // output
 125
 126 void dump(const map<string, vector<string> > definitions) {
 127   // nothing special needed for segment headers, since '=' precedes all alphabet in ASCII
 128   for (map<string, vector<string> >::const_iterator p = definitions.begin();  p != definitions.end();  ++p) {
 129     const vector<string>& lines = p->second;
 130     for (int i = 0;  i < SIZE(lines);  ++i)
 131       cout << lines[i] << '\n';
 132   }
 133 }
 134
 135 int main() {
 136   map<string, vector<string> > code, data;
 137   read_lines(code, data);
 138   for (int iter = 0;  ;  ++iter) {
 139 //?     cerr << "iter: " << iter << '\n';
 140     int old_csize = SIZE(code), old_dsize = SIZE(data);
 141     treeshake(code, data);
 142     if (SIZE(code) == old_csize && SIZE(data) == old_dsize) break;
 143   }
 144   dump(code);
 145   dump(data);
 146   return 0;
 147 }