about summary refs log tree commit diff stats
path: root/tools/treeshake.cc
blob: 9bf5106eddb87fed76a41d4c88d1bc99c3ca50c2 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: 
// Read a set of lines on stdin of the following form:
//  definition:
//    ...
//    ...
//
// Delete all 'dead' definitions with following indented lines that aren't
// used outside their bodies.
//
// This can be transitive; deleting one definition may cause other definitions
// to become dead.
//
// Also assorts segments as a side-effect.
//
// Like linkify, treeshake is a hack.

#include<assert.h>

#include<map>
using std::map;
#include<vector>
using std::vector;
#define SIZE(X) (assert((X).size() < (1LL<<(sizeof(int)*8-2))), static_cast<int>((X).size()))

#include<string>
using std::string;

#include<iostream>
using std::cin;
using std::cout;
using std::cerr;

#include<sstream>
using std::istringstream;

bool starts_with(const string& s, const string& pat) {
  string::const_iterator a=s.begin(), b=pat.begin();
  for (/*nada*/;  a!=s.end() && b!=pat.end();  ++a, ++b)
    if (*a != *b) return false;
  return b == pat.end();
}

// input

void read_body(string name, string definition_line, map<string, vector<string> >& segment) {
  // last definition wins; this only matters for the 'Entry' label in the code segment
  segment[name] = vector<string>();
  segment[name].push_back(definition_line);
  while (!cin.eof()) {
    if (cin.peek() != ' ' && cin.peek() != '$') break;  // assumes: no whitespace but spaces; internal labels start with '$'
    string line;
    getline(cin, line);
    segment[name].push_back(line);
  }
}

void read_lines(string segment_header, map<string, vector<string> >& segment) {
  // first segment header wins
  if (segment.empty())
    segment["=="].push_back(segment_header);  // '==' is a special key containing the segment header
  while (!cin.eof()) {
    if (cin.peek() == '=') break;  // assumes: no line can start with '=' except a segment header
    assert(cin.peek() != ' ');  // assumes: no whitespace but spaces
    string line;
    getline(cin, line);
    istringstream lstream(line);
    string name;
    getline(lstream, name, ' ');
    assert(name[SIZE(name)-1] == ':');
    name.erase(--name.end());
    read_body(name, line, segment);
  }
}

void read_lines(map<string, vector<string> >& code, map<string, vector<string> >& data) {
  while (!cin.eof()) {
    string line;
    getline(cin, line);
    assert(starts_with(line, "== "));
    map<string, vector<string> >& curr = (line.substr(3, 4) == "code") ? code : data;  // HACK: doesn't support segments except 'code' and 'data'
    read_lines(line, curr);
  }
}

// treeshake

bool any_line_matches(string pat, const vector<string>& lines) {
  for (int i = 0;  i < SIZE(lines);  ++i)
    if (lines.at(i).find(pat) != string::npos)  // conservative: confused by word boundaries, comments and string literals
      return true;
  return false;
}

bool is_dead(string key, const map<string, vector<string> >& code, const map<string, vector<string> >& data) {
  if (key == "Entry") return false;
  if (key == "==") return false;
  for (map<string, vector<string> >::const_iterator p = code.begin();  p != code.end();  ++p) {
    if (p->first == key) continue;
    if (any_line_matches(key, p->second)) return false;
  }
  for (map<string, vector<string> >::const_iterator p = data.begin();  p != data.end();  ++p) {
    if (p->first == key) continue;
    if (any_line_matches(key, p->second)) return false;
  }
  return true;
}

void treeshake(map<string, vector<string> >& code, map<string, vector<string> >& data) {
  for (map<string, vector<string> >::iterator p = code.begin();  p != code.end();  ++p) {
    if (is_dead(p->first, code, data)) {
//?       cerr << "  erasing " << p->first << '\n';
      code.erase(p);
      return;
    }
  }
  for (map<string, vector<string> >::iterator p = data.begin();  p != data.end();  ++p) {
    if (is_dead(p->first, code, data)) {
//?       cerr << "  erasing " << p->first << '\n';
      data.erase(p);
      return;
    }
  }
}

// output

void dump(const map<string, vector<string> > definitions) {
  // nothing special needed for segment headers, since '=' precedes all alphabet in ASCII
  for (map<string, vector<string> >::const_iterator p = definitions.begin();  p != definitions.end();  ++p) {
    const vector<string>& lines = p->second;
    for (int i = 0;  i < SIZE(lines);  ++i)
      cout << lines[i] << '\n';
  }
}

int main() {
  map<string, vector<string> > code, data;
  read_lines(code, data);
  for (int iter = 0;  ;  ++iter) {
//?     cerr << "iter: " << iter << '\n';
    int old_csize = SIZE(code), old_dsize = SIZE(data);
    treeshake(code, data);
    if (SIZE(code) == old_csize && SIZE(data) == old_dsize) break;
  }
  dump(code);
  dump(data);
  return 0;
}