src/tlv.c


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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

#include <assert.h>
#ifdef __NetBSD__
#include <curses.h>
#else
#include <ncurses.h>
#endif
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#include "lua.h"
#include "lauxlib.h"
#include "tlv.h"

/* If you encounter assertion failures in this file and _didn't_ manually edit
 * it, lease report the .tlv file that caused them: http://akkartik.name/contact.
 *
 * Manually edited files can have cryptic errors. Teliva's first priority is
 * to be secure, so it requires a fairly rigid file format and errors out if
 * things are even slightly amiss. */

/* This code is surprisingly hairy. Estimate of buffer overflows: 2. */

static void teliva_load_multiline_string(lua_State* L, FILE* in, char* line, int capacity) {
  luaL_Buffer b;
  luaL_buffinit(L, &b);
  int expected_indent = -1;
  while (1) {
    if (feof(in)) break;
    char c = fgetc(in);
    ungetc(c, in);
    if (c != ' ') {
      /* new definition; signal end to caller without reading a new line */
      strcpy(line, "-\n");
      break;
    }
    memset(line, '\0', capacity);
    if (fgets(line, capacity, in) == NULL) break;  /* eof */
    int max = strlen(line);
    assert(line[max-1] == '\n');
    int indent = 0;
    while (indent < max-1 && line[indent] == ' ')
      ++indent;
    if (line[indent] != '>') break;  /* new key/value pair in definition */
    if (expected_indent == -1)
      expected_indent = indent;
    else
      assert(expected_indent == indent);
    int start = indent+1;  /* skip '>' */
    luaL_addstring(&b, &line[start]);  /* guaranteed to at least be null */
  }
  luaL_pushresult(&b);
  /* final state of line goes out into the world */
}

/* leave a single table on stack containing the next top-level definition from the file */
void teliva_load_definition(lua_State* L, FILE* in) {
  lua_newtable(L);
  int def_idx = lua_gettop(L);
  char line[1024] = {'\0'};
  do {
    if (feof(in) || fgets(line, 1024, in) == NULL) {
      lua_pushnil(L);
      return;
    }
  } while (line[0] == '#');  /* comment at start of file */
  assert(line[strlen(line)-1] == '\n');
  do {
    assert(line[0] == '-' || line[0] == ' ');
    assert(line[1] == ' ');
    /* key/value pair always indented at 0, never empty, unambiguously not a multiline string */
    char key[512] = {'\0'};
    char value[1024] = {'\0'};
    assert(line[2] != ' ');
    assert(line[2] != '>');
    assert(line[2] != '\n');
    assert(line[2] != '\0');
    memset(key, 0, 512);
    memset(value, 0, 1024);
    sscanf(line+2, "%s%s", key, value);
    assert(key[strlen(key)-1] == ':');
    key[strlen(key)-1] = '\0';
    lua_pushstring(L, key);
    if (value[0] != '\0') {
      lua_pushstring(L, value);  /* value string on same line */
      char c = fgetc(in);
      ungetc(c, in);
      if (c == '-') {
        strcpy(line, "-\n");
      }
      else {
        memset(line, '\0', 1024);
        fgets(line, 1024, in);
      }
    }
    else {
      teliva_load_multiline_string(L, in, line, 1024);  /* load from later lines */
    }
    lua_settable(L, def_idx);
  } while (line[0] == ' ');
}

void load_tlv(lua_State* L, char* filename) {
  lua_newtable(L);
  int history_array = lua_gettop(L);
  FILE* in = fopen(filename, "r");
  if (in == NULL) {
    endwin();
    fprintf(stderr, "no such file\n");
    exit(1);
  }
  for (int i = 1; !feof(in); ++i) {
    teliva_load_definition(L, in);
    if (lua_isnil(L, -1)) break;
    lua_rawseti(L, history_array, i);
  }
  fclose(in);
  lua_setglobal(L, "teliva_program");
}

void emit_multiline_string(FILE* out, const char* value) {
  fprintf(out, "    >");
  for (const char* curr = value; *curr != '\0'; ++curr) {
    if (*curr == '\n' && *(curr+1) != '\0')
      fprintf(out, "\n    >");
    else
      fprintf(out, "%c", *curr);
  }
}

static const char* special_history_keys[] = {
  "__teliva_timestamp",
  "__teliva_note",
  "__teliva_undo",
  NULL,
};

/* save key and its value at top of stack to out
 * no stack side effects */
static void save_tlv_key(lua_State* L, const char* key, FILE* out) {
  if (strcmp(key, "__teliva_undo") == 0) {
    fprintf(out, "%s: %ld\n", key, lua_tointeger(L, -1));
    return;
  }
  const char* value = lua_tostring(L, -1);
  if (strchr(value, ' ') || strchr(value, '\n')) {
    fprintf(out, "%s:\n", key);
    emit_multiline_string(out, value);
  }
  else {
    fprintf(out, "%s: %s\n", key, value);
  }
}

void save_tlv(lua_State* L, char* filename) {
  lua_getglobal(L, "teliva_program");
  int history_array = lua_gettop(L);
  int history_array_size = luaL_getn(L, history_array);
  char outfilename[] = "teliva_out_XXXXXX";
  int outfd = mkstemp(outfilename);
  if (outfd == -1) {
    endwin();
    perror("save_tlv: error in creating temporary file");
    abort();
  }
  FILE *out = fdopen(outfd, "w");
  fprintf(out, "# .tlv file generated by https://github.com/akkartik/teliva\n");
  fprintf(out, "# You may edit it if you are careful; however, you may see cryptic errors if you\n");
  fprintf(out, "# violate Teliva's assumptions.\n");
  fprintf(out, "#\n");
  fprintf(out, "# .tlv files are representations of Teliva programs. Teliva programs consist of\n");
  fprintf(out, "# sequences of definitions. Each definition is a table of key/value pairs. Keys\n");
  fprintf(out, "# and values are both strings.\n");
  fprintf(out, "#\n");
  fprintf(out, "# Lines in .tlv files always follow exactly one of the following forms:\n");
  fprintf(out, "# - comment lines at the top of the file starting with '#' at column 0\n");
  fprintf(out, "# - beginnings of definitions starting with '- ' at column 0, followed by a\n");
  fprintf(out, "#   key/value pair\n");
  fprintf(out, "# - key/value pairs consisting of '  ' at column 0, containing either a\n");
  fprintf(out, "#   spaceless value on the same line, or a multi-line value\n");
  fprintf(out, "# - multiline values indented by more than 2 spaces, starting with a '>'\n");
  fprintf(out, "#\n");
  fprintf(out, "# If these constraints are violated, Teliva may unceremoniously crash. Please\n");
  fprintf(out, "# report bugs at http://akkartik.name/contact\n");
  for (int i = 1;  i <= history_array_size; ++i) {
    lua_rawgeti(L, history_array, i);
    int table = lua_gettop(L);
    int first = 1;
    // standardize order of special keys
    for (int k = 0;  special_history_keys[k];  ++k) {
      lua_getfield(L, table, special_history_keys[k]);
      if (!lua_isnil(L, -1)) {
        if (first) fprintf(out, "- ");
        else fprintf(out, "  ");
        first = 0;
        save_tlv_key(L, special_history_keys[k], out);
      }
      lua_pop(L, 1);
    }
    for (lua_pushnil(L); lua_next(L, table) != 0; lua_pop(L, 1)) {
      if (is_special_history_key(lua_tostring(L, -2)))
        continue;
      if (first) fprintf(out, "- ");
      else fprintf(out, "  ");
      first = 0;
      save_tlv_key(L, lua_tostring(L, -2), out);
    }
    lua_pop(L, 1);
  }
  fclose(out);
  rename(outfilename, filename);
  lua_pop(L, 1);
}

int is_special_history_key(const char* key) {
  for (const char** curr = special_history_keys; *curr != NULL; ++curr) {
    if (strcmp(*curr, key) == 0)
      return 1;
  }
  return 0;
}
//: A Mu program is a book of 'recipes' (functions)
:(before "End Globals")
//: Each recipe is stored at a specific page number, or ordinal.
map<recipe_ordinal, recipe> Recipe;
//: You can also refer to each recipe by its name.
map<string, recipe_ordinal> Recipe_ordinal;
recipe_ordinal Next_recipe_ordinal = 1;

//: Ordinals are like numbers, except you can't do arithmetic on them. Ordinal
//: 1 is not less than 2, it's just different. Phone numbers are ordinals;
//: adding two phone numbers is meaningless. Here each recipe does something
//: incommensurable with any other recipe.
:(after "Types")
typedef int recipe_ordinal;

:(before "End Types")
// Recipes are lists of instructions. To perform or 'run' a recipe, the
// computer runs its instructions.
struct recipe {
  recipe_ordinal ordinal;
  string name;
  vector<instruction> steps;
  // End recipe Fields
  recipe();
};

:(before "struct recipe")
// Each instruction is either of the form:
//   product1, product2, product3, ... <- operation ingredient1, ingredient2, ingredient3, ...
// or just a single 'label' starting with a non-alphanumeric character
//   +label
// Labels don't do anything, they're just named locations in a recipe.
struct instruction {
  bool is_label;
  string label;  // only if is_label
  string name;  // only if !is_label
  string original_string;  // for error messages
  recipe_ordinal operation;  // get(Recipe_ordinal, name)
  vector<reagent> ingredients;  // only if !is_label
  vector<reagent> products;  // only if !is_label
  // End instruction Fields
  instruction();
  void clear();
  bool is_empty();
};

:(before "struct instruction")
// Ingredients and products are a single species -- a reagent. Reagents refer
// either to numbers or to locations in memory along with 'type' tags telling
// us how to interpret them. They also can contain arbitrary other lists of
// properties besides types, but we're getting ahead of ourselves.
struct reagent {
  string original_string;
  string name;
  type_tree* type;
  vector<pair<string, string_tree*> > properties;  // can't be a map because the string_tree sometimes needs to be NULL, which can be confusing
  double value;
  bool initialized;
  // End reagent Fields
  reagent(const string& s);
  reagent() :type(NULL), value(0), initialized(false) {}
  reagent(type_tree* t) :type(t), value(0), initialized(false) {}
  ~reagent();
  void clear();
  reagent(const reagent& original);
  reagent& operator=(const reagent& original);
  void set_value(double v) { value = v;  initialized = true; }
};

:(before "struct reagent")
// Types can range from a simple type ordinal, to arbitrarily complex trees of
// type parameters, like (map (address array character) (list number))
struct type_tree {
  bool atom;
  string name;  // only if atom
  type_ordinal value;  // only if atom
  type_tree* left;  // only if !atom
  type_tree* right;  // only if !atom
  ~type_tree();
  type_tree(const type_tree& original);
  // atomic type ordinal
  explicit type_tree(string name);
  type_tree(string name, type_ordinal v) :atom(true), name(name), value(v), left(NULL), right(NULL) {}
  // tree of type ordinals
  type_tree(type_tree* l, type_tree* r) :atom(false), value(0), left(l), right(r) {}
  type_tree& operator=(const type_tree& original);
  bool operator==(const type_tree& other) const;
  bool operator!=(const type_tree& other) const { return !operator==(other); }
  bool operator<(const type_tree& other) const;
  bool operator>(const type_tree& other) const { return other.operator<(*this); }
};

struct string_tree {
  bool atom;
  string value;  // only if atom
  string_tree* left;  // only if !atom
  string_tree* right;  // only if !atom
  ~string_tree();
  string_tree(const string_tree& original);
  // atomic string
  explicit string_tree(string v) :atom(true), value(v), left(NULL), right(NULL) {}
  // tree of strings
  string_tree(string_tree* l, string_tree* r) :atom(false), left(l), right(r) {}
};

// End type_tree Definition
:(code)
type_tree::type_tree(string name) :atom(true), name(name), value(get(Type_ordinal, name)), left(NULL), right(NULL) {}

:(before "End Globals")
// Locations refer to a common 'memory'. Each location can store a number.
map<int, double> Memory;
:(before "End Reset")
Memory.clear();

:(after "Types")
// Mu types encode how the numbers stored in different parts of memory are
// interpreted. A location tagged as a 'character' type will interpret the
// value 97 as the letter 'a', while a different location of type 'number'
// would not.
//
// Unlike most computers today, Mu stores types in a single big table, shared
// by all the Mu programs on the computer. This is useful in providing a
// seamless experience to help understand arbitrary Mu programs.
typedef int type_ordinal;
:(before "End Globals")
map<string, type_ordinal> Type_ordinal;
map<type_ordinal, type_info> Type;
type_ordinal Next_type_ordinal = 1;
type_ordinal Number_type_ordinal = 0;
type_ordinal Boolean_type_ordinal = 0;
type_ordinal Character_type_ordinal = 0;
type_ordinal Address_type_ordinal = 0;
type_ordinal Array_type_ordinal = 0;
:(code)
void setup_types() {
  Type.clear();  Type_ordinal.clear();
  put(Type_ordinal, "literal", 0);
  Next_type_ordinal = 1;
  // Mu Types Initialization
  Number_type_ordinal = put(Type_ordinal, "number", Next_type_ordinal++);
  get_or_insert(Type, Number_type_ordinal).name = "number";
  put(Type_ordinal, "location", Number_type_ordinal);  // synonym of number for addresses we'll never look up
  Address_type_ordinal = put(Type_ordinal, "address", Next_type_ordinal++);
  get_or_insert(Type, Address_type_ordinal).name = "address";
  Boolean_type_ordinal = put(Type_ordinal, "boolean", Next_type_ordinal++);
  get_or_insert(Type, Boolean_type_ordinal).name = "boolean";
  Character_type_ordinal = put(Type_ordinal, "character", Next_type_ordinal++);
  get_or_insert(Type, Character_type_ordinal).name = "character";
  // Array types are a special modifier to any other type. For example,
  // array:number or array:address:boolean.
  Array_type_ordinal = put(Type_ordinal, "array", Next_type_ordinal++);
  get_or_insert(Type, Array_type_ordinal).name = "array";
  // End Mu Types Initialization
}
void teardown_types() {
  for (map<type_ordinal, type_info>::iterator p = Type.begin();  p != Type.end();  ++p) {
    for (int i = 0;  i < SIZE(p->second.elements);  ++i)
      p->second.elements.clear();
  }
  Type_ordinal.clear();
}
:(before "End One-time Setup")
setup_types();
atexit(teardown_types);

:(before "End Types")
// You can construct arbitrary new types. New types are either 'containers'
// with multiple 'elements' of other types, or 'exclusive containers' containing
// one of multiple 'variants'. (These are similar to C structs and unions,
// respectively, though exclusive containers implicitly include a tag element
// recording which variant they should be interpreted as.)
//
// For example, storing bank balance and name for an account might require a
// container, but if bank accounts may be either for individuals or groups,
// with different properties for each, that may require an exclusive container
// whose variants are individual-account and joint-account containers.
enum kind_of_type {
  PRIMITIVE,
  CONTAINER,
  EXCLUSIVE_CONTAINER
};

struct type_info {
  string name;
  kind_of_type kind;
  vector<reagent> elements;
  // End type_info Fields
  type_info() :kind(PRIMITIVE) {
    // End type_info Constructor
  }
};

enum primitive_recipes {
  IDLE = 0,
  COPY,
  // End Primitive Recipe Declarations
  MAX_PRIMITIVE_RECIPES,
};
:(code)
//: It's all very well to construct recipes out of other recipes, but we need
//: to know how to do *something* out of the box. For the following
//: recipes there are only codes, no entries in the book, because Mu just knows
//: what to do for them.
void setup_recipes() {
  Recipe.clear();  Recipe_ordinal.clear();
  put(Recipe_ordinal, "idle", IDLE);
  // Primitive Recipe Numbers
  put(Recipe_ordinal, "copy", COPY);
  // End Primitive Recipe Numbers
}
//: We could just reset the recipe table after every test, but that gets slow
//: all too quickly. Instead, initialize the common stuff just once at
//: startup. Later layers will carefully undo each test's additions after
//: itself.
:(before "End One-time Setup")
setup_recipes();
assert(MAX_PRIMITIVE_RECIPES < 200);  // level 0 is primitives; until 199
Next_recipe_ordinal = 200;
put(Recipe_ordinal, "main", Next_recipe_ordinal++);
// Load Mu Prelude
// End Mu Prelude
:(before "End Commandline Parsing")
assert(Next_recipe_ordinal < 1000);  // recipes being tested didn't overflow into test space
:(before "End Reset")
Next_recipe_ordinal = 1000;  // consistent new numbers for each test

//: One final detail: tests can modify our global tables of recipes and types,
//: so we need some way to clean up after each test is done so it doesn't
//: influence later ones.
:(before "End Globals")
map<string, recipe_ordinal> Recipe_ordinal_snapshot;
map<recipe_ordinal, recipe> Recipe_snapshot;
map<string, type_ordinal> Type_ordinal_snapshot;
map<type_ordinal, type_info> Type_snapshot;
:(before "End One-time Setup")
save_snapshots();
:(before "End Reset")
restore_snapshots();

:(code)
void save_snapshots() {
  Recipe_ordinal_snapshot = Recipe_ordinal;
  Recipe_snapshot = Recipe;
  Type_ordinal_snapshot = Type_ordinal;
  Type_snapshot = Type;
  // End save_snapshots
}

void restore_snapshots() {
  Recipe = Recipe_snapshot;
  Recipe_ordinal = Recipe_ordinal_snapshot;
  restore_non_recipe_snapshots();
}
// when running sandboxes in the edit/ app we'll want to restore everything except recipes defined in the app
void restore_non_recipe_snapshots() {
  Type_ordinal = Type_ordinal_snapshot;
  Type = Type_snapshot;
  // End restore_snapshots
}

//:: Helpers

:(code)
recipe::recipe() {
  ordinal = -1;
  // End recipe Constructor
}

instruction::instruction() :is_label(false), operation(IDLE) {
  // End instruction Constructor
}
void instruction::clear() {
  is_label=false;
  label.clear();
  name.clear();
  operation=IDLE;
  ingredients.clear();
  products.clear();
  original_string.clear();
  // End instruction Clear
}
bool instruction::is_empty() { return !is_label && name.empty(); }

// Reagents have the form <name>:<type>:<type>:.../<property>/<property>/...
reagent::reagent(const string& s) :original_string(s), type(NULL), value(0), initialized(false) {
  // Parsing reagent(string s)
  istringstream in(s);
  in >> std::noskipws;
  // name and type
  istringstream first_row(slurp_until(in, '/'));
  first_row >> std::noskipws;
  name = slurp_until(first_row, ':');
  string_tree* type_names = parse_property_list(first_row);
  // End Parsing Reagent Type Property(type_names)
  type = new_type_tree(type_names);
  delete type_names;
  // special cases
  if (is_integer(name) && type == NULL)
    type = new type_tree("literal");
  if (name == "_" && type == NULL)
    type = new type_tree("literal");
  // other properties
  slurp_properties(in, properties);
  // End Parsing reagent
}

void slurp_properties(istream& in, vector<pair<string, string_tree*> >& out) {
  while (has_data(in)) {
    istringstream row(slurp_until(in, '/'));
    row >> std::noskipws;
    string key = slurp_until(row, ':');
    string_tree* value = parse_property_list(row);
    out.push_back(pair<string, string_tree*>(key, value));
  }
}

string_tree* parse_property_list(istream& in) {
  skip_whitespace_but_not_newline(in);
  if (!has_data(in)) return NULL;
  string_tree* first = new string_tree(slurp_until(in, ':'));
  if (!has_data(in)) return first;
  string_tree* rest = parse_property_list(in);
  if (!has_data(in) && rest->atom)
    return new string_tree(first, new string_tree(rest, NULL));
  return new string_tree(first, rest);
}
:(before "End Unit Tests")
void test_parse_property_list_atom() {
  istringstream in("a");
  string_tree* x = parse_property_list(in);
  CHECK(x->atom);
  delete x;
}
void test_parse_property_list_list() {
  istringstream in("a:b");
  string_tree* x = parse_property_list(in);
  CHECK(!x->atom);
  CHECK(x->left->atom);
  CHECK_EQ(x->left->value, "a");
  CHECK(!x->right->atom);
  CHECK(x->right->left->atom);
  CHECK_EQ(x->right->left->value, "b");
  CHECK(x->right->right == NULL);
  delete x;
}

:(code)
type_tree* new_type_tree(const string_tree* properties) {
  if (!properties) return NULL;
  if (properties->atom) {
    const string& type_name = properties->value;
    int value = 0;
    if (contains_key(Type_ordinal, type_name))
      value = get(Type_ordinal, type_name);
    else if (is_integer(type_name))  // sometimes types will contain literal integers, like for the size of an array
      value = 0;
    else if (properties->value == "->")  // used in recipe types
      value = 0;
    else
      value = -1;  // should never happen; will trigger errors later
    return new type_tree(type_name, value);
  }
  return new type_tree(new_type_tree(properties->left),
                       new_type_tree(properties->right));
}

//: avoid memory leaks for the type tree

reagent::reagent(const reagent& other) {
  original_string = other.original_string;
  name = other.name;
  value = other.value;
  initialized = other.initialized;
  for (int i = 0;  i < SIZE(other.properties);  ++i) {
    properties.push_back(pair<string, string_tree*>(other.properties.at(i).first, copy(other.properties.at(i).second)));
  }
  type = copy(other.type);
  // End reagent Copy Constructor
}

type_tree::type_tree(const type_tree& original) {
  atom = original.atom;
  name = original.name;
  value = original.value;
  left = copy(original.left);
  right = copy(original.right);
}

type_tree& type_tree::operator=(const type_tree& original) {
  atom = original.atom;
  name = original.name;
  value = original.value;
  if (left) delete left;
  left = copy(original.left);
  if (right) delete right;
  right = copy(original.right);
  return *this;
}

bool type_tree::operator==(const type_tree& other) const {
  if (atom != other.atom) return false;
  if (atom)
    return name == other.name && value == other.value;
  return (left == other.left || *left == *other.left)
      && (right == other.right || *right == *other.right);
}

// only constraint we care about: if a < b then !(b < a)
bool type_tree::operator<(const type_tree& other) const {
  if (atom != other.atom) return atom > other.atom;  // atoms before non-atoms
  if (atom) return value < other.value;
  // first location in one that's missing in the other makes that side 'smaller'
  if (left && !other.left) return false;
  if (!left && other.left) return true;
  if (right && !other.right) return false;
  if (!right && other.right) return true;
  // now if either pointer is unequal neither side can be null
  // if one side is equal that's easy
  if (left == other.left || *left == *other.left) return right && *right < *other.right;
  if (right == other.right || *right == *other.right) return left && *left < *other.left;
  // if the two sides criss-cross, pick the side with the smaller lhs
  if ((left == other.right || *left == *other.right)
      && (right == other.left || *right == *other.left))
    return *left < *other.left;
  // now the hard case: both sides are not equal
  // make sure we stay consistent between (a < b) and (b < a)
  // just return the side with the smallest of the 4 branches
  if (*left < *other.left && *left < *other.right) return true;
  if (*right < *other.left && *right < *other.right) return true;
  return false;
}
:(before "End Unit Tests")
// These unit tests don't always use valid types.
void test_compare_atom_types() {
  reagent a("a:address"), b("b:boolean");
  CHECK(*a.type < *b.type);
  CHECK(!(*b.type < *a.type));
}
void test_compare_equal_atom_types() {
  reagent a("a:address"), b("b:address");
  CHECK(!(*a.type < *b.type));
  CHECK(!(*b.type < *a.type));
}
void test_compare_atom_with_non_atom() {
  reagent a("a:address:number"), b("b:boolean");
  CHECK(!(*a.type < *b.type));
  CHECK(*b.type < *a.type);
}
void test_compare_lists_with_identical_structure() {
  reagent a("a:address:address"), b("b:address:boolean");
  CHECK(*a.type < *b.type);
  CHECK(!(*b.type < *a.type));
}
void test_compare_identical_lists() {
  reagent a("a:address:boolean"), b("b:address:boolean");
  CHECK(!(*a.type < *b.type));
  CHECK(!(*b.type < *a.type));
}
void test_compare_list_with_extra_element() {
  reagent a("a:address:address"), b("b:address:address:number");
  CHECK(*a.type < *b.type);
  CHECK(!(*b.type < *a.type));
}
void test_compare_list_with_smaller_left_but_larger_right() {
  reagent a("a:number:character"), b("b:boolean:array");
  CHECK(*a.type < *b.type);
  CHECK(!(*b.type < *a.type));
}
void test_compare_list_with_smaller_left_but_larger_right_identical_types() {
  reagent a("a:address:boolean"), b("b:boolean:address");
  CHECK(*a.type < *b.type);
  CHECK(!(*b.type < *a.type));
}

:(code)
string_tree::string_tree(const string_tree& original) {
  atom = original.atom;
  value = original.value;
  left = copy(original.left);
  right = copy(original.right);
}

reagent& reagent::operator=(const reagent& other) {
  original_string = other.original_string;
  for (int i = 0;  i < SIZE(properties);  ++i)
    if (properties.at(i).second) delete properties.at(i).second;
  properties.clear();
  for (int i = 0;  i < SIZE(other.properties);  ++i)
    properties.push_back(pair<string, string_tree*>(other.properties.at(i).first, copy(other.properties.at(i).second)));
  name = other.name;
  value = other.value;
  initialized = other.initialized;
  if (type) delete type;
  type = copy(other.type);
  // End reagent Copy Operator
  return *this;
}

reagent::~reagent() {
  clear();
}

void reagent::clear() {
  for (int i = 0;  i < SIZE(properties);  ++i) {
    if (properties.at(i).second) {
      delete properties.at(i).second;
      properties.at(i).second = NULL;
    }
  }
  delete type;
  type = NULL;
}
type_tree::~type_tree() {
  delete left;
  delete right;
}
string_tree::~string_tree() {
  delete left;
  delete right;
}

void append(type_tree*& base, type_tree* extra) {
  if (!base) {
    base = extra;
    return;
  }
  type_tree* curr = base;
  while (curr->right) curr = curr->right;
  curr->right = extra;
}

void append(string_tree*& base, string_tree* extra) {
  if (!base) {
    base = extra;
    return;
  }
  string_tree* curr = base;
  while (curr->right) curr = curr->right;
  curr->right = extra;
}

string slurp_until(istream& in, char delim) {
  ostringstream out;
  char c;
  while (in >> c) {
    if (c == delim) {
      // drop the delim
      break;
    }
    out << c;
  }
  return out.str();
}

bool has_property(const reagent& x, const string& name) {
  for (int i = 0;  i < SIZE(x.properties);  ++i) {
    if (x.properties.at(i).first == name) return true;
  }
  return false;
}

string_tree* property(const reagent& r, const string& name) {
  for (int p = 0;  p != SIZE(r.properties);  ++p) {
    if (r.properties.at(p).first == name)
      return r.properties.at(p).second;
  }
  return NULL;
}

string_tree* copy(const string_tree* x) {
  if (x == NULL) return NULL;
  return new string_tree(*x);
}

type_tree* copy(const type_tree* x) {
  if (x == NULL) return NULL;
  return new type_tree(*x);
}

:(before "End Globals")
extern const string Ignore(",");  // commas are ignored in Mu except within [] strings
:(code)
void skip_whitespace_but_not_newline(istream& in) {
  while (true) {
    if (!has_data(in)) break;
    else if (in.peek() == '\n') break;
    else if (isspace(in.peek())) in.get();
    else if (Ignore.find(in.peek()) != string::npos) in.get();
    else break;
  }
}

void dump_memory() {
  for (map<int, double>::iterator p = Memory.begin();  p != Memory.end();  ++p) {
    cerr << p->first << ": " << no_scientific(p->second) << '\n';
  }
}

//:: Helpers for converting various values to string
//: Use to_string() in trace(), and try to keep it stable from run to run.
//: Use debug_string() while debugging, and throw everything into it.
//: Use inspect() only for emitting a canonical format that can be parsed back
//: into the value.

string to_string(const recipe& r) {
  ostringstream out;
  out << "recipe " << r.name << " [\n";
  for (int i = 0;  i < SIZE(r.steps);  ++i)
    out << "  " << to_string(r.steps.at(i)) << '\n';
  out << "]\n";
  return out.str();
}

string to_original_string(const recipe& r) {
  ostringstream out;
  out << "recipe " << r.name << " [\n";
  for (int i = 0;  i < SIZE(r.steps);  ++i)
    out << "  " << to_original_string(r.steps.at(i)) << '\n';
  out << "]\n";
  return out.str();
}

string debug_string(const recipe& x) {
  ostringstream out;
  out << "- recipe " << x.name << '\n';
  // Begin debug_string(recipe x)
  for (int index = 0;  index < SIZE(x.steps);  ++index) {
    const instruction& inst = x.steps.at(index);
    out << "inst: " << to_string(inst) << '\n';
    out << "  ingredients\n";
    for (int i = 0;  i < SIZE(inst.ingredients);  ++i)
      out << "    " << debug_string(inst.ingredients.at(i)) << '\n';
    out << "  products\n";
    for (int i = 0;  i < SIZE(inst.products);  ++i)
      out << "    " << debug_string(inst.products.at(i)) << '\n';
  }
  return out.str();
}

string to_original_string(const instruction& inst) {
  if (inst.is_label) return inst.label;
  if (!inst.original_string.empty()) return inst.original_string;
  ostringstream out;
  for (int i = 0;  i < SIZE(inst.products);  ++i) {
    if (i > 0) out << ", ";
    out << inst.products.at(i).original_string;
  }
  if (!inst.products.empty()) out << " <- ";
  out << inst.name;
  if (!inst.ingredients.empty()) out << ' ';
  for (int i = 0;  i < SIZE(inst.ingredients);  ++i) {
    if (i > 0) out << ", ";
    out << inst.ingredients.at(i).original_string;
  }
  return out.str();
}

string to_string(const instruction& inst) {
  if (inst.is_label) return inst.label;
  ostringstream out;
  for (int i = 0;  i < SIZE(inst.products);  ++i) {
    if (i > 0) out << ", ";
    out << to_string(inst.products.at(i));
  }
  if (!inst.products.empty()) out << " <- ";
  out << inst.name << ' ';
  for (int i = 0;  i < SIZE(inst.ingredients);  ++i) {
    if (i > 0) out << ", ";
    out << to_string(inst.ingredients.at(i));
  }
  return out.str();
}

string to_string(const reagent& r) {
  if (is_dummy(r)) return "_";
  ostringstream out;
  out << "{";
  out << r.name << ": " << names_to_string(r.type);
  if (!r.properties.empty()) {
    for (int i = 0;  i < SIZE(r.properties);  ++i)
      out << ", \"" << r.properties.at(i).first << "\": " << to_string(r.properties.at(i).second);
  }
  out << "}";
  return out.str();
}

// special name for ignoring some products
bool is_dummy(const reagent& x) {
  return x.name == "_";
}

string debug_string(const reagent& x) {
  ostringstream out;
  out << x.name << ": " << x.value << ' ' << to_string(x.type) << " -- " << to_string(x);
  return out.str();
}

string to_string(const string_tree* property) {
  if (!property) return "()";
  ostringstream out;
  dump(property, out);
  return out.str();
}

void dump(const string_tree* x, ostream& out) {
  if (!x) return;
  if (x->atom) {
    out << '"' << x->value << '"';
    return;
  }
  out << '(';
  const string_tree* curr = x;
  while (curr && !curr->atom) {
    dump(curr->left, out);
    if (curr->right) out << ' ';
    curr = curr->right;
  }
  // check for dotted list; should never happen
  if (curr) {
    out << ". ";
    dump(curr, out);
  }
  out << ')';
}

string to_string(const type_tree* type) {
  if (type == NULL) return "()";
  ostringstream out;
  dump(type, out);
  return out.str();
}

void dump(const type_tree* x, ostream& out) {
  if (!x) return;
  if (x->atom) {
    dump(x->value, out);
    return;
  }
  out << '(';
  const type_tree* curr = x;
  while (curr && !curr->atom) {
    dump(curr->left, out);
    if (curr->right) out << ' ';
    curr = curr->right;
  }
  // check for dotted list; should never happen
  if (curr) {
    out << ". ";
    dump(curr, out);
  }
  out << ')';
}

void dump(type_ordinal type, ostream& out) {
  if (contains_key(Type, type))
    out << get(Type, type).name;
  else
    out << "?" << type;
}

string names_to_string(const type_tree* type) {
  if (type == NULL) return "()";  // should never happen
  ostringstream out;
  dump_names(type, out);
  return out.str();
}

void dump_names(const type_tree* x, ostream& out) {
  if (!x) return;
  if (x->atom) {
    out << '"' << x->name << '"';
    return;
  }
  out << '(';
  const type_tree* curr = x;
  while (curr && !curr->atom) {
    dump_names(curr->left, out);
    if (curr->right) out << ' ';
    curr = curr->right;
  }
  // check for dotted list; should never happen
  if (curr) {
    out << ". ";
    dump_names(curr, out);
  }
  out << ')';
}

string names_to_string_without_quotes(const type_tree* type) {
  if (type == NULL) return "()";
  ostringstream out;
  dump_names_without_quotes(type, out);
  return out.str();
}

void dump_names_without_quotes(const type_tree* x, ostream& out) {
  if (!x) return;
  if (x->atom) {
    out << x->name;
    return;
  }
  out << '(';
  const type_tree* curr = x;
  while (curr && !curr->atom) {
    dump_names_without_quotes(curr->left, out);
    if (curr->right) out << ' ';
    curr = curr->right;
  }
  // check for dotted list; should never happen
  if (curr) {
    out << ". ";
    dump_names_without_quotes(curr, out);
  }
  out << ')';
}

bool is_integer(const string& s) {
  return s.find_first_not_of("0123456789-") == string::npos  // no other characters
      && s.find_first_of("0123456789") != string::npos  // at least one digit
      && s.find('-', 1) == string::npos;  // '-' only at first position
}

int to_integer(string n) {
  char* end = NULL;
  // safe because string.c_str() is guaranteed to be null-terminated
  int result = strtoll(n.c_str(), &end, /*any base*/0);
  if (*end != '\0') cerr << "tried to convert " << n << " to number\n";
  assert(*end == '\0');
  return result;
}

void test_is_integer() {
  CHECK(is_integer("1234"));
  CHECK(is_integer("-1"));
  CHECK(!is_integer("234.0"));
  CHECK(is_integer("-567"));
  CHECK(!is_integer("89-0"));
  CHECK(!is_integer("-"));
  CHECK(!is_integer("1e3"));  // not supported
}

//: helper to print numbers without excessive precision

:(before "End Types")
struct no_scientific {
  double x;
  explicit no_scientific(double y) :x(y) {}
};

:(code)
ostream& operator<<(ostream& os, no_scientific x) {
  if (!isfinite(x.x)) {
    // Infinity or NaN
    os << x.x;
    return os;
  }
  ostringstream tmp;
  // more accurate, but too slow
//?   tmp.precision(308);  // for 64-bit numbers
  tmp << std::fixed << x.x;
  os << trim_floating_point(tmp.str());
  return os;
}

string trim_floating_point(const string& in) {
  if (in.empty()) return "";
  if (in.find('.') == string::npos) return in;
  int length = SIZE(in);
  while (length > 1) {
    if (in.at(length-1) != '0') break;
    --length;
  }
  if (in.at(length-1) == '.') --length;
  if (length == 0) return "0";
  return in.substr(0, length);
}

void test_trim_floating_point() {
  CHECK_EQ(trim_floating_point(""), "");
  CHECK_EQ(trim_floating_point(".0"), "0");
  CHECK_EQ(trim_floating_point("1.5000"), "1.5");
  CHECK_EQ(trim_floating_point("1.000001"), "1.000001");
  CHECK_EQ(trim_floating_point("23.000000"), "23");
  CHECK_EQ(trim_floating_point("23.0"), "23");
  CHECK_EQ(trim_floating_point("23."), "23");
  CHECK_EQ(trim_floating_point("23"), "23");
  CHECK_EQ(trim_floating_point("230"), "230");
  CHECK_EQ(trim_floating_point("3.000000"), "3");
  CHECK_EQ(trim_floating_point("3.0"), "3");
  CHECK_EQ(trim_floating_point("3."), "3");
  CHECK_EQ(trim_floating_point("3"), "3");
}

:(before "End Includes")
#include <map>
using std::map;
#include <utility>
using std::pair;
#include <math.h>