1 //: Everything this project/binary supports.
  2 //: This should give you a sense for what to look forward to in later layers.
  3 
  4 :(before "End Commandline Parsing")
  5 if (argc <= 1 || is_equal(argv[1], "--help")) {
  6   //: this is the functionality later layers will provide
  7   // currently no automated tests for commandline arg parsing
  8   if (argc <= 1) {
  9     cerr << "Please provide a Mu program to run.\n"
 10          << "\n";
 11   }
 12   cerr << "Usage:\n"
 13        << "  mu [options] [test] [files]\n"
 14        << "or:\n"
 15        << "  mu [options] [test] [files] -- [ingredients for function/recipe 'main']\n"
 16        << "Square brackets surround optional arguments.\n"
 17        << "\n"
 18        << "Examples:\n"
 19        << "  To load files and run 'main':\n"
 20        << "    mu file1.mu file2.mu ...\n"
 21        << "  To run 'main' and dump a trace of all operations at the end:\n"
 22        << "    mu --trace file1.mu file2.mu ...\n"
 23        << "  To run all tests:\n"
 24        << "    mu test\n"
 25        << "  To load files and then run all tests:\n"
 26        << "    mu test file1.mu file2.mu ...\n"
 27        << "  To run a single Mu scenario:\n"
 28        << "    mu test file1.mu file2.mu ... scenario\n"
 29        << "  To run a single Mu scenario and dump a trace at the end:\n"
 30        << "    mu --trace test file1.mu file2.mu ... scenario\n"
 31        << "  To load files and run only the tests in explicitly loaded files (for apps):\n"
 32        << "    mu --test-only-app test file1.mu file2.mu ...\n"
 33        << "  To load all files with a numeric prefix in a directory:\n"
 34        << "    mu directory1 directory2 ...\n"
 35        << "  You can test directories just like files.\n"
 36        << "    mu test directory1 directory2 ...\n"
 37        << "  To pass ingredients to a mu program, provide them after '--':\n"
 38        << "    mu file_or_dir1 file_or_dir2 ... -- ingredient1 ingredient2 ...\n"
 39        << "  To see where a mu program is spending its time:\n"
 40        << "    mu --profile file_or_dir1 file_or_dir2 ...\n"
 41        << "  this slices and dices time spent in various profile.* output files\n"
 42        << "\n"
 43        << "  To browse a trace generated by a previous run:\n"
 44        << "    mu browse-trace file\n"
 45        ;
 46   return 0;
 47 }
 48 
 49 //: Support for option parsing.
 50 //: Options always begin with '--' and are always the first arguments. An
 51 //: option will never follow a non-option.
 52 :(before "End Commandline Parsing")
 53 char** arg = &argv[1];
 54 while (argc > 1 && starts_with(*arg, "--")) {
 55   if (false)
 56     ;  // no-op branch just so any further additions can consistently always start with 'else'
 57   // End Commandline Options(*arg)
 58   else
 59     cerr << "skipping unknown option " << *arg << '\n';
 60   --argc;  ++argv;  ++arg;
 61 }
 62 
 63 //:: Helper function used by the above fragment of code (and later layers too,
 64 //:: who knows?).
 65 //: The :(code) directive appends function definitions to the end of the
 66 //: project. Regardless of where functions are defined, we can call them
 67 //: anywhere we like as long as we format the function header in a specific
 68 //: way: put it all on a single line without indent, end the line with ') {'
 69 //: and no trailing whitespace. As long as functions uniformly start this
 70 //: way, our 'build' script contains a little command to automatically
 71 //: generate declarations for them.
 72 :(code)
 73 bool is_equal(char* s, const char* lit) {
 74   return strncmp(s, lit, strlen(lit)) == 0;
 75 }
 76 
 77 bool starts_with(const string& s, const string& pat) {
 78   string::const_iterator a=s.begin(), b=pat.begin();
 79   for (/*nada*/;  a!=s.end() && b!=pat.end();  ++a, ++b)
 80     if (*a != *b) return false;
 81   return b == pat.end();
 82 }
 83 
 84 //: I'll throw some style conventions here for want of a better place for them.
 85 //: As a rule I hate style guides. Do what you want, that's my motto. But since
 86 //: we're dealing with C/C++, the one big thing we want to avoid is undefined
 87 //: behavior. If a compiler ever encounters undefined behavior it can make
 88 //: your program do anything it wants.
 89 //:
 90 //: For reference, my checklist of undefined behaviors to watch out for:
 91 //:   out-of-bounds access
 92 //:   uninitialized variables
 93 //:   use after free
 94 //:   dereferencing invalid pointers: null, a new of size 0, others
 95 //:
 96 //:   casting a large number to a type too small to hold it
 97 //:
 98 //:   integer overflow
 99 //:   division by zero and other undefined expressions
100 //:   left-shift by negative count
101 //:   shifting values by more than or equal to the number of bits they contain
102 //:   bitwise operations on signed numbers
103 //:
104 //:   Converting pointers to types of different alignment requirements
105 //:     T* -> void* -> T*: defined
106 //:     T* -> U* -> T*: defined if non-function pointers and alignment requirements are same
107 //:     function pointers may be cast to other function pointers
108 //:
109 //:       Casting a numeric value into a value that can't be represented by the target type (either directly or via static_cast)
110 //:
111 //: To guard against these, some conventions:
112 //:
113 //: 0. Initialize all primitive variables in functions and constructors.
114 //:
115 //: 1. Minimize use of pointers and pointer arithmetic. Avoid 'new' and
116 //: 'delete' as far as possible. Rely on STL to perform memory management to
117 //: avoid use-after-free issues (and memory leaks).
118 //:
119 //: 2. Avoid naked arrays to avoid out-of-bounds access. Never use operator[]
120 //: except with map. Use at() with STL vectors and so on.
121 //:
122 //: 3. Valgrind all the things.
123 //:
124 //: 4. Avoid unsigned numbers. Not strictly an undefined-behavior issue, but
125 //: the extra range doesn't matter, and it's one less confusing category of
126 //: interaction gotchas to worry about.
127 //:
128 //: Corollary: don't use the size() method on containers, since it returns an
129 //: unsigned and that'll cause warnings about mixing signed and unsigned,
130 //: yadda-yadda. Instead use this macro below to perform an unsafe cast to
131 //: signed. We'll just give up immediately if a container's ever too large.
132 //: Basically, Mu is not concerned about this being a little slower than it
133 //: could be. (https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7)
134 //:
135 //: Addendum to corollary: We're going to uniformly use int everywhere, to
136 //: indicate that we're oblivious to number size, and since Clang on 32-bit
137 //: platforms doesn't yet support multiplication over 64-bit integers, and
138 //: since multiplying two integers seems like a more common situation to end
139 //: up in than integer overflow.
140 :(before "End Includes")
141 #define SIZE(X) (assert((X).size() < (1LL<<(sizeof(int)*8-2))), static_cast<int>((X).size()))
142 
143 //: 5. Integer overflow is guarded against at runtime using the -ftrapv flag
144 //: to the compiler, supported by Clang (GCC version only works sometimes:
145 //: http://stackoverflow.com/questions/20851061/how-to-make-gcc-ftrapv-work).
146 :(before "atexit(reset)")
147 initialize_signal_handlers();  // not always necessary, but doesn't hurt
148 //? cerr << INT_MAX+1 << '\n';  // test overflow
149 //? assert(false);  // test SIGABRT
150 :(code)
151 // based on https://spin.atomicobject.com/2013/01/13/exceptions-stack-traces-c
152 void initialize_signal_handlers() {
153   struct sigaction action;
154   bzero(&action, sizeof(action));
155   action.sa_sigaction = dump_and_exit;
156   sigemptyset(&action.sa_mask);
157   sigaction(SIGABRT, &action, NULL);  // assert() failure or integer overflow on linux (with -ftrapv)
158   sigaction(SIGILL,  &action, NULL);  // integer overflow on OS X (with -ftrapv)
159 }
160 void dump_and_exit(int sig, unused siginfo_t* dummy1, unused void* dummy2) {
161   switch (sig) {
162     case SIGABRT:
163       #ifndef __APPLE__
164         cerr << "SIGABRT: might be an integer overflow if it wasn't an assert() failure or exception\n";
165         _Exit(1);
166       #endif
167       break;
168     case SIGILL:
169       #ifdef __APPLE__
170         cerr << "SIGILL: most likely caused by integer overflow\n";
171         _Exit(1);
172       #endif
173       break;
174     default:
175       break;
176   }
177 }
178 :(before "End Includes")
179 #include <signal.h>
180 
181 //: For good measure we'll also enable SIGFPE.
182 :(before "atexit(reset)")
183 feenableexcept(FE_OVERFLOW | FE_UNDERFLOW);
184 //? assert(sizeof(int) == 4 && sizeof(float) == 4);
185 //? //                          | exp   |  mantissa
186 //? int smallest_subnormal = 0b00000000000000000000000000000001;
187 //? float smallest_subnormal_f = *reinterpret_cast<float*>(&smallest_subnormal);
188 //? cerr << "ε: " << smallest_subnormal_f << '\n';
189 //? cerr << "ε/2: " << smallest_subnormal_f/2 << " (underflow)\n";  // test SIGFPE
190 :(before "End Includes")
191 #include <fenv.h>
192 :(code)
193 #ifdef __APPLE__
194 // Public domain polyfill for feenableexcept on OS X
195 // http://www-personal.umich.edu/~williams/archive/computation/fe-handling-example.c
196 int feenableexcept(unsigned int excepts) {
197   static fenv_t fenv;
198   unsigned int new_excepts = excepts & FE_ALL_EXCEPT;
199   unsigned int old_excepts;
200   if (fegetenv(&fenv)) return -1;
201   old_excepts = fenv.__control & FE_ALL_EXCEPT;
202   fenv.__control &= ~new_excepts;
203   fenv.__mxcsr &= ~(new_excepts << 7);
204   return fesetenv(&fenv) ? -1 : old_excepts;
205 }
206 #endif
207 
208 //: 6. Map's operator[] being non-const is fucking evil.
209 :(before "Globals")  // can't generate prototypes for these
210 // from http://stackoverflow.com/questions/152643/idiomatic-c-for-reading-from-a-const-map
211 template<typename T> typename T::mapped_type& get(T& map, typename T::key_type const& key) {
212   typename T::iterator iter(map.find(key));
213   assert(iter != map.end());
214   return iter->second;
215 }
216 template<typename T> typename T::mapped_type const& get(const T& map, typename T::key_type const& key) {
217   typename T::const_iterator iter(map.find(key));
218   assert(iter != map.end());
219   return iter->second;
220 }
221 template<typename T> typename T::mapped_type const& put(T& map, typename T::key_type const& key, typename T::mapped_type const& value) {
222   // map[key] requires mapped_type to have a zero-arg (default) constructor
223   map.insert(std::make_pair(key, value)).first->second = value;
224   return value;
225 }
226 template<typename T> bool contains_key(T& map, typename T::key_type const& key) {
227   return map.find(key) != map.end();
228 }
229 template<typename T> typename T::mapped_type& get_or_insert(T& map, typename T::key_type const& key) {
230   return map[key];
231 }
232 //: The contract: any container that relies on get_or_insert should never call
233 //: contains_key.
234 
235 //: 7. istreams are a royal pain in the arse. You have to be careful about
236 //: what subclass you try to putback into. You have to watch out for the pesky
237 //: failbit and badbit. Just avoid eof() and use this helper instead.
238 :(code)
239 bool has_data(istream& in) {
240   return in && !in.eof();
241 }
242 
243 :(before "End Includes")
244 #include <assert.h>
245 
246 #include <iostream>
247 using std::istream;
248 using std::ostream;
249 using std::iostream;
250 using std::cin;
251 using std::cout;
252 using std::cerr;
253 #include <iomanip>
254 
255 #include <string.h>
256 #include <string>
257 using std::string;
258 
259 #define unused  __attribute__((unused))
260 
261 #include <algorithm>
262 using std::min;
263 using std::max;