1 //: The goal of this skeleton is to make programs more easy to understand and
  2 //: more malleable, easy to rewrite in radical ways without accidentally
  3 //: breaking some corner case. Tests further both goals. They help
  4 //: understandability by letting one make small changes and get feedback. What
  5 //: if I wrote this line like so? What if I removed this function call, is it
  6 //: really necessary? Just try it, see if the tests pass. Want to explore
  7 //: rewriting this bit in this way? Tests put many refactorings on a firmer
  8 //: footing.
  9 //:
 10 //: But the usual way we write tests seems incomplete. Refactorings tend to
 11 //: work in the small, but don't help with changes to function boundaries. If
 12 //: you want to extract a new function you have to manually test-drive it to
 13 //: create tests for it. If you want to inline a function its tests are no
 14 //: longer valid. In both cases you end up having to reorganize code as well as
 15 //: tests, an error-prone activity.
 16 //:
 17 //: This file tries to fix this problem by supporting domain-driven testing
 18 //: We try to focus on the domain of inputs the program should work on. All
 19 //: tests invoke the program in a single way: by calling run() with different
 20 //: inputs. The program operates on the input and logs _facts_ it deduces to a
 21 //: trace:
 22 //:   trace("label") << "fact 1: " << val;
 23 //:
 24 //: The tests check for facts:
 25 //:   :(scenario foo)
 26 //:   34  # call run() with this input
 27 //:   +label: fact 1: 34  # trace should have logged this at the end
 28 //:   -label: fact 1: 35  # trace should never contain such a line
 29 //:
 30 //: Since we never call anything but the run() function directly, we never have
 31 //: to rewrite the tests when we reorganize the internals of the program. We
 32 //: just have to make sure our rewrite deduces the same facts about the domain,
 33 //: and that's something we're going to have to do anyway.
 34 //:
 35 //: To avoid the combinatorial explosion of integration tests, we organize the
 36 //: program into different layers, and each fact is logged to the trace with a
 37 //: specific label. Individual tests can focus on specific labels. In essence,
 38 //: validating the facts logged with a specific label is identical to calling
 39 //: some internal subsystem.
 40 //:
 41 //: Traces interact salubriously with layers. Thanks to our ordering
 42 //: directives, each layer can contain its own tests. They may rely on other
 43 //: layers, but when a test fails its usually due to breakage in the same
 44 //: layer. When multiple tests fail, it's usually useful to debug the very
 45 //: first test to fail. This is in contrast with the traditional approach,
 46 //: where changes can cause breakages in faraway subsystems, and picking the
 47 //: right test to debug can be an important skill to pick up.
 48 //:
 49 //: To build robust tests, trace facts about your domain rather than details of
 50 //: how you computed them.
 51 //:
 52 //: More details: http://akkartik.name/blog/tracing-tests
 53 //:
 54 //: ---
 55 //:
 56 //: Between layers and domain-driven testing, programming starts to look like a
 57 //: fundamentally different activity. Instead of a) superficial, b) local rules
 58 //: on c) code [like http://blog.bbv.ch/2013/06/05/clean-code-cheat-sheet],
 59 //: we allow programmers to engage with the a) deep, b) global structure of the
 60 //: c) domain. If you can systematically track discontinuities in the domain
 61 //: you don't care if the code used gotos as long as it passed the tests. If
 62 //: tests become more robust to run it becomes easier to try out radically
 63 //: different implementations for the same program. If code is super-easy to
 64 //: rewrite, it becomes less important what indentation style it uses, or that
 65 //: the objects are appropriately encapsulated, or that the functions are
 66 //: referentially transparent.
 67 //:
 68 //: Instead of plumbing, programming becomes building and gradually refining a
 69 //: map of the environment the program must operate under. Whether a program is
 70 //: 'correct' at a given point in time is a red herring; what matters is
 71 //: avoiding regression by monotonically nailing down the more 'eventful' parts
 72 //: of the terrain. It helps readers new and old and rewards curiosity to
 73 //: organize large programs in self-similar hiearchies of example scenarios
 74 //: colocated with the code that makes them work.
 75 //:
 76 //:   "Programming properly should be regarded as an activity by which
 77 //:   programmers form a mental model, rather than as production of a program."
 78 //:   -- Peter Naur (http://alistair.cockburn.us/ASD+book+extract%3A+%22Naur,+Ehn,+Musashi%22)
 79 
 80 :(before "End Types")
 81 struct trace_line {
 82   int depth;  // optional field just to help browse traces later
 83   string label;
 84   string contents;
 85   trace_line(string l, string c) :depth(0), label(l), contents(c) {}
 86   trace_line(int d, string l, string c) :depth(d), label(l), contents(c) {}
 87 };
 88 
 89 :(before "End Globals")
 90 bool Hide_errors = false;
 91 bool Dump_trace = false;
 92 string Dump_label = "";
 93 :(before "End Setup")
 94 Hide_errors = false;
 95 Dump_trace = false;
 96 Dump_label = "";
 97 
 98 :(before "End Types")
 99 // Pre-define some global constants that trace_stream needs to know about.
100 // Since they're in the Types section, they'll be included in any cleaved
101 // compilation units. So no extern linkage.
102 const int Max_depth = 9999;
103 const int Error_depth = 0;  // definitely always print errors
104 const int App_depth = 2;  // temporarily where all Mu code will trace to
105 
106 struct trace_stream {
107   vector<trace_line> past_lines;
108   // accumulator for current line
109   ostringstream* curr_stream;
110   string curr_label;
111   int curr_depth;
112   int callstack_depth;
113   int collect_depth;
114   ofstream null_stream;  // never opens a file, so writes silently fail
115   trace_stream() :curr_stream(NULL), curr_depth(Max_depth), callstack_depth(0), collect_depth(Max_depth) {}
116   ~trace_stream() { if (curr_stream) delete curr_stream; }
117 
118   ostream& stream(string label) {
119     return stream(Max_depth, label);
120   }
121 
122   ostream& stream(int depth, string label) {
123     if (depth > collect_depth) return null_stream;
124     curr_stream = new ostringstream;
125     curr_label = label;
126     curr_depth = depth;
127     return *curr_stream;
128   }
129 
130   // be sure to call this before messing with curr_stream or curr_label
131   void newline();
132   // useful for debugging
133   string readable_contents(string label);  // empty label = show everything
134 };
135 
136 :(code)
137 void trace_stream::newline() {
138   if (!curr_stream) return;
139   string curr_contents = curr_stream->str();
140   if (!curr_contents.empty()) {
141     past_lines.push_back(trace_line(curr_depth, trim(curr_label), curr_contents));  // preserve indent in contents
142     if ((!Hide_errors && curr_label == "error")
143         || Dump_trace
144         || (!Dump_label.empty() && curr_label == Dump_label))
145       cerr << curr_label << ": " << curr_contents << '\n';
146   }
147   delete curr_stream;
148   curr_stream = NULL;
149   curr_label.clear();
150   curr_depth = Max_depth;
151 }
152 
153 string trace_stream::readable_contents(string label) {
154   ostringstream output;
155   label = trim(label);
156   for (vector<trace_line>::iterator p = past_lines.begin();  p != past_lines.end();  ++p)
157     if (label.empty() || label == p->label) {
158       output << std::setw(4) << p->depth << ' ' << p->label << ": " << p->contents << '\n';
159     }
160   return output.str();
161 }
162 
163 :(before "End Globals")
164 trace_stream* Trace_stream = NULL;
165 int Trace_errors = 0;  // used only when Trace_stream is NULL
166 
167 :(before "End Includes")
168 #define CLEAR_TRACE  delete Trace_stream, Trace_stream = new trace_stream;
169 
170 // Top-level helper. IMPORTANT: can't nest
171 #define trace(...)  !Trace_stream ? cerr /*print nothing*/ : Trace_stream->stream(__VA_ARGS__)
172 
173 // Just for debugging; 'git log' should never show any calls to 'dbg'.
174 #define dbg trace(0, "a")
175 #define DUMP(label)  if (Trace_stream) cerr << Trace_stream->readable_contents(label);
176 
177 // Errors are a special layer.
178 #define raise  (!Trace_stream ? (tb_shutdown(),++Trace_errors,cerr) /*do print*/ : Trace_stream->stream(Error_depth, "error"))
179 // If we aren't yet sure how to deal with some corner case, use assert_for_now
180 // to indicate that it isn't an inviolable invariant.
181 #define assert_for_now assert
182 
183 // Inside tests, fail any tests that displayed (unexpected) errors.
184 // Expected errors in tests should always be hidden and silently checked for.
185 :(before "End Test Teardown")
186 if (Passed && !Hide_errors && trace_contains_errors()) {
187   Passed = false;
188 }
189 :(code)
190 bool trace_contains_errors() {
191   return Trace_errors > 0 || trace_count("error") > 0;
192 }
193 
194 :(before "End Types")
195 struct end {};
196 :(code)
197 ostream& operator<<(ostream& os, unused end) {
198   if (Trace_stream) Trace_stream->newline();
199   return os;
200 }
201 
202 :(before "End Globals")
203 bool Save_trace = false;
204 
205 // Trace_stream is a resource, lease_tracer uses RAII to manage it.
206 :(before "End Types")
207 struct lease_tracer {
208   lease_tracer();
209   ~lease_tracer();
210 };
211 :(code)
212 lease_tracer::lease_tracer() { Trace_stream = new trace_stream; }
213 lease_tracer::~lease_tracer() {
214   if (!Trace_stream) return;  // in case tests close Trace_stream
215   if (Save_trace) {
216     ofstream fout("last_trace");
217     fout << Trace_stream->readable_contents("");
218     fout.close();
219   }
220   delete Trace_stream, Trace_stream = NULL;
221 }
222 :(before "End Includes")
223 #define START_TRACING_UNTIL_END_OF_SCOPE  lease_tracer leased_tracer;
224 :(before "End Test Setup")
225 START_TRACING_UNTIL_END_OF_SCOPE
226 
227 :(before "End Includes")
228 #define CHECK_TRACE_CONTENTS(...)  check_trace_contents(__FUNCTION__, __FILE__, __LINE__, __VA_ARGS__)
229 
230 #define CHECK_TRACE_CONTAINS_ERRORS()  CHECK(trace_contains_errors())
231 #define CHECK_TRACE_DOESNT_CONTAIN_ERRORS() \
232   if (Passed && trace_contains_errors()) { \
233     cerr << "\nF - " << __FUNCTION__ << "(" << __FILE__ << ":" << __LINE__ << "): unexpected errors\n"; \
234     DUMP("error"); \
235     Passed = false; \
236     return; \
237   }
238 
239 #define CHECK_TRACE_COUNT(label, count) \
240   if (Passed && trace_count(label) != (count)) { \
241     cerr << "\nF - " << __FUNCTION__ << "(" << __FILE__ << ":" << __LINE__ << "): trace_count of " << label << " should be " << count << '\n'; \
242     cerr << "  got " << trace_count(label) << '\n';  /* multiple eval */ \
243     DUMP(label); \
244     Passed = false; \
245     return;  /* Currently we stop at the very first failure. */ \
246   }
247 
248 #define CHECK_TRACE_DOESNT_CONTAIN(...)  CHECK(trace_doesnt_contain(__VA_ARGS__))
249 
250 :(code)
251 bool check_trace_contents(string FUNCTION, string FILE, int LINE, string expected) {
252   if (!Passed) return false;
253   if (!Trace_stream) return false;
254   vector<string> expected_lines = split(expected, "^D");
255   int curr_expected_line = 0;
256   while (curr_expected_line < SIZE(expected_lines) && expected_lines.at(curr_expected_line).empty())
257     ++curr_expected_line;
258   if (curr_expected_line == SIZE(expected_lines)) return true;
259   string label, contents;
260   split_label_contents(expected_lines.at(curr_expected_line), &label, &contents);
261   for (vector<trace_line>::iterator p = Trace_stream->past_lines.begin();  p != Trace_stream->past_lines.end();  ++p) {
262     if (label != p->label) continue;
263     if (contents != trim(p->contents)) continue;
264     ++curr_expected_line;
265     while (curr_expected_line < SIZE(expected_lines) && expected_lines.at(curr_expected_line).empty())
266       ++curr_expected_line;
267     if (curr_expected_line == SIZE(expected_lines)) return true;
268     split_label_contents(expected_lines.at(curr_expected_line), &label, &contents);
269   }
270 
271   if (line_exists_anywhere(label, contents)) {
272     cerr << "\nF - " << FUNCTION << "(" << FILE << ":" << LINE << "): line [" << label << ": " << contents << "] out of order in trace:\n";
273     DUMP("");
274   }
275   else {
276     cerr << "\nF - " << FUNCTION << "(" << FILE << ":" << LINE << "): missing [" << contents << "] in trace:\n";
277     DUMP(label);
278   }
279   Passed = false;
280   return false;
281 }
282 
283 void split_label_contents(const string& s, string* label, string* contents) {
284   static const string delim(": ");
285   size_t pos = s.find(delim);
286   if (pos == string::npos) {
287     *label = "";
288     *contents = trim(s);
289   }
290   else {
291     *label = trim(s.substr(0, pos));
292     *contents = trim(s.substr(pos+SIZE(delim)));
293   }
294 }
295 
296 bool line_exists_anywhere(const string& label, const string& contents) {
297   for (vector<trace_line>::iterator p = Trace_stream->past_lines.begin();  p != Trace_stream->past_lines.end();  ++p) {
298     if (label != p->label) continue;
299     if (contents == trim(p->contents)) return true;
300   }
301   return false;
302 }
303 
304 int trace_count(string label) {
305   return trace_count(label, "");
306 }
307 
308 int trace_count(string label, string line) {
309   if (!Trace_stream) return 0;
310   long result = 0;
311   for (vector<trace_line>::iterator p = Trace_stream->past_lines.begin();  p != Trace_stream->past_lines.end();  ++p) {
312     if (label == p->label) {
313       if (line == "" || trim(line) == trim(p->contents))
314         ++result;
315     }
316   }
317   return result;
318 }
319 
320 int trace_count_prefix(string label, string prefix) {
321   if (!Trace_stream) return 0;
322   long result = 0;
323   for (vector<trace_line>::iterator p = Trace_stream->past_lines.begin();  p != Trace_stream->past_lines.end();  ++p) {
324     if (label == p->label) {
325       if (starts_with(trim(p->contents), trim(prefix)))
326         ++result;
327     }
328   }
329   return result;
330 }
331 
332 bool trace_doesnt_contain(string label, string line) {
333   return trace_count(label, line) == 0;
334 }
335 
336 bool trace_doesnt_contain(string expected) {
337   vector<string> tmp = split_first(expected, ": ");
338   return trace_doesnt_contain(tmp.at(0), tmp.at(1));
339 }
340 
341 vector<string> split(string s, string delim) {
342   vector<string> result;
343   size_t begin=0, end=s.find(delim);
344   while (true) {
345     if (end == string::npos) {
346       result.push_back(string(s, begin, string::npos));
347       break;
348     }
349     result.push_back(string(s, begin, end-begin));
350     begin = end+SIZE(delim);
351     end = s.find(delim, begin);
352   }
353   return result;
354 }
355 
356 vector<string> split_first(string s, string delim) {
357   vector<string> result;
358   size_t end=s.find(delim);
359   result.push_back(string(s, 0, end));
360   if (end != string::npos)
361     result.push_back(string(s, end+SIZE(delim), string::npos));
362   return result;
363 }
364 
365 string trim(const string& s) {
366   string::const_iterator first = s.begin();
367   while (first != s.end() && isspace(*first))
368     ++first;
369   if (first == s.end()) return "";
370 
371   string::const_iterator last = --s.end();
372   while (last != s.begin() && isspace(*last))
373     --last;
374   ++last;
375   return string(first, last);
376 }
377 
378 :(before "End Includes")
379 #include <vector>
380 using std::vector;
381 #include <list>
382 using std::list;
383 #include <map>
384 using std::map;
385 #include <set>
386 using std::set;
387 #include <algorithm>
388 
389 #include <sstream>
390 using std::istringstream;
391 using std::ostringstream;
392 
393 #include <fstream>
394 using std::ifstream;
395 using std::ofstream;
396 
397 #include "termbox/termbox.h"
398 
399 :(before "End Globals")
400 //: In future layers we'll use the depth field as follows:
401 //:
402 //: Errors will be depth 0.
403 //: Mu 'applications' will be able to use depths 1-100 as they like.
404 //: Primitive statements will occupy 101-9989
405 extern const int Initial_callstack_depth = 101;
406 extern const int Max_callstack_depth = 9989;
407 //: Finally, details of primitive Mu statements will occupy depth 9990-9999
408 //: (more on that later as well)
409 //:
410 //: This framework should help us hide some details at each level, mixing
411 //: static ideas like layers with the dynamic notion of call-stack depth.