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