2891 - precompute container sizes and offsets

It's a bit of a trade-off because we need to store copies of
container metadata in each reagent (to support shape-shifting
containers), and metadata is not lightweight and will get heavier. But
it'll become more unambiguously useful when we switch to a compiler.

8 files changed, 166 insertions, 35 deletions

diff --git a/010vm.cc b/010vm.cc
index eec9e2ff..d46719ad 100644
--- a/010vm.cc
+++ b/010vm.cc
@@ -56,6 +56,7 @@ struct reagent {
   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(string s);
   reagent() :type(NULL), value(0), initialized(false) {}
   ~reagent();
@@ -319,6 +320,7 @@ reagent::reagent(const reagent& old) {
                                                     old.properties.at(i).second ? new string_tree(*old.properties.at(i).second) : NULL));
   }
   type = old.type ? new type_tree(*old.type) : NULL;
+  // End reagent Copy Constructor
 }
 
 type_tree::type_tree(const type_tree& old) {
@@ -346,6 +348,7 @@ reagent& reagent::operator=(const reagent& old) {
   initialized = old.initialized;
   if (type) delete type;
   type = old.type ? new type_tree(*old.type) : NULL;
+  // End reagent Copy Operator
   return *this;
 }
 
diff --git a/030container.cc b/030container.cc
index 8daddd2d..2b75e45b 100644
--- a/030container.cc
+++ b/030container.cc
@@ -92,6 +92,39 @@ def main [
 ]
 +mem: storing 0 in location 7
 
+//: Global data structure for container metadata.
+//: Can't put this in type_info because later layers will add support for more
+//: complex type trees where metadata depends not just on the root of the type tree.
+
+:(after "Types")
+struct container_metadata {
+  int size;
+  vector<int> offset;
+  // End container_metadata Fields
+  container_metadata() :size(0) {
+    // End container_metadata Constructor
+  }
+};
+:(before "End reagent Fields")
+container_metadata metadata;  // can't be a pointer into Container_metadata because we keep changing the base storage when we save/restore snapshots
+:(before "End reagent Copy Operator")
+metadata = old.metadata;
+:(before "End reagent Copy Constructor")
+metadata = old.metadata;
+
+:(before "End Globals")
+// todo: switch to map after figuring out how to consistently compare type trees
+vector<pair<type_tree*, container_metadata> > Container_metadata, Container_metadata_snapshot;
+:(before "End save_snapshots")
+Container_metadata_snapshot = Container_metadata;
+:(before "End restore_snapshots")
+Container_metadata = Container_metadata_snapshot;
+
+//: do no work in size_of, simply lookup Container_metadata
+
+:(before "End size_of(reagent) Cases")
+if (r.metadata.size) return r.metadata.size;
+
 :(before "End size_of(type) Cases")
 if (type->value == -1) return 1;  // error value, but we'll raise it elsewhere
 if (type->value == 0) {
@@ -104,17 +137,83 @@ if (!contains_key(Type, type->value)) {
 }
 type_info t = get(Type, type->value);
 if (t.kind == CONTAINER) {
-  // size of a container is the sum of the sizes of its elements
-  int result = 0;
-  for (int i = 0; i < SIZE(t.elements); ++i) {
-    // todo: strengthen assertion to disallow mutual type recursion
-    if (t.elements.at(i).type->value == type->value) {
-      raise << "container " << t.name << " can't include itself as a member\n" << end();
-      return 0;
+  // Compute size_of Container
+  return get(Container_metadata, type).size;
+}
+
+//: precompute Container_metadata before we need size_of
+//: also store a copy in each reagent in each instruction in each recipe
+
+:(after "Begin Instruction Modifying Transforms")  // needs to happen before transform_names, therefore after "End Type Modifying Transforms" below
+Transform.push_back(compute_container_metadata);
+:(code)
+void compute_container_metadata(recipe_ordinal r) {
+  recipe& caller = get(Recipe, r);
+  for (int i = 0; i < SIZE(caller.steps); ++i) {
+    instruction& inst = caller.steps.at(i);
+    for (int i = 0; i < SIZE(inst.ingredients); ++i)
+      compute_container_metadata(inst.ingredients.at(i));
+    for (int i = 0; i < SIZE(inst.products); ++i)
+      compute_container_metadata(inst.products.at(i));
+  }
+}
+
+void compute_container_metadata(reagent& r) {
+  if (is_literal(r) || is_dummy(r)) return;
+  reagent rcopy = r;
+  // Compute Container Metadata(reagent rcopy)
+  set<type_ordinal> pending_metadata;
+  compute_container_metadata(rcopy.type, pending_metadata);
+  if (contains_key(Container_metadata, rcopy.type))
+    r.metadata = get(Container_metadata, rcopy.type);
+}
+
+void compute_container_metadata(const type_tree* type, set<type_ordinal>& pending_metadata) {
+  if (!type) return;
+  if (contains_key(pending_metadata, type->value)) return;
+  pending_metadata.insert(type->value);
+  if (contains_key(Container_metadata, type)) return;
+  if (type->left) compute_container_metadata(type->left, pending_metadata);
+  if (type->right) compute_container_metadata(type->right, pending_metadata);
+  if (!contains_key(Type, type->value)) return;  // error raised elsewhere
+  type_info& info = get(Type, type->value);
+  if (info.kind == CONTAINER) {
+    container_metadata metadata;
+    for (int i = 0; i < SIZE(info.elements); ++i) {
+      reagent element = info.elements.at(i);
+      // Compute Container Metadata(element)
+      compute_container_metadata(element.type, pending_metadata);
+      metadata.offset.push_back(metadata.size);  // save previous size as offset
+      metadata.size += size_of(element.type);
     }
-    result += size_of(element_type(type, i));
+    Container_metadata.push_back(pair<type_tree*, container_metadata>(new type_tree(*type), metadata));
   }
-  return result;
+  // End compute_container_metadata Cases
+}
+
+const container_metadata& get(const vector<pair<type_tree*, container_metadata> >& all, const type_tree* key) {
+  for (int i = 0; i < SIZE(all); ++i) {
+    if (matches(all.at(i).first, key))
+      return all.at(i).second;
+  }
+  tb_shutdown();
+  raise << "unknown size for type " << to_string(key) << '\n' << end();
+  assert(false);
+}
+
+bool contains_key(const vector<pair<type_tree*, container_metadata> >& all, const type_tree* key) {
+  for (int i = 0; i < SIZE(all); ++i) {
+    if (matches(all.at(i).first, key))
+      return true;
+  }
+  return false;
+}
+
+bool matches(const type_tree* a, const type_tree* b) {
+  if (a == b) return true;
+  if (!a || !b) return false;
+  if (a->value != b->value) return false;
+  return matches(a->left, b->left) && matches(a->right, b->right);
 }
 
 :(scenario stash_container)
@@ -188,9 +287,8 @@ case GET: {
   type_ordinal base_type = base.type->value;
   int offset = ingredients.at(1).at(0);
   if (offset < 0 || offset >= SIZE(get(Type, base_type).elements)) break;  // copied from Check above
-  int src = base_address;
-  for (int i = 0; i < offset; ++i)
-    src += size_of(element_type(base.type, i));
+  assert(base.metadata.size);
+  int src = base_address + base.metadata.offset.at(offset);
   trace(9998, "run") << "address to copy is " << src << end();
   reagent element = element_type(base.type, offset);
   element.set_value(src);
diff --git a/031array.cc b/031array.cc
index c2cbfd7f..a40f9e20 100644
--- a/031array.cc
+++ b/031array.cc
@@ -98,7 +98,10 @@ if (r.type && r.type->value == get(Type_ordinal, "array")) {
     raise << maybe(current_recipe_name()) << "'" << r.original_string << "' is an array of what?\n" << end();
     return 1;
   }
-  return 1 + array_length(r)*size_of(array_element(r.type));
+  type_tree* element_type = copy_array_element(r.type);
+  int result = 1 + array_length(r)*size_of(element_type);
+  delete element_type;
+  return result;
 }
 
 //: disable the size mismatch check for arrays since the destination array
@@ -186,7 +189,7 @@ case INDEX: {
   reagent product = inst.products.at(0);
   // Update INDEX product in Check
   reagent element;
-  element.type = new type_tree(*array_element(base.type));
+  element.type = copy_array_element(base.type);
   if (!types_coercible(product, element)) {
     raise << maybe(get(Recipe, r).name) << "'index' on " << base.original_string << " can't be saved in " << product.original_string << "; type should be " << names_to_string_without_quotes(element.type) << '\n' << end();
     break;
@@ -206,29 +209,33 @@ case INDEX: {
   reagent index = current_instruction().ingredients.at(1);
   // Update INDEX index in Run
   vector<double> index_val(read_memory(index));
-  type_tree* element_type = array_element(base.type);
   if (index_val.at(0) < 0 || index_val.at(0) >= get_or_insert(Memory, base_address)) {
     raise << maybe(current_recipe_name()) << "invalid index " << no_scientific(index_val.at(0)) << '\n' << end();
     break;
   }
+  type_tree* element_type = copy_array_element(base.type);
   int src = base_address + 1 + index_val.at(0)*size_of(element_type);
   trace(9998, "run") << "address to copy is " << src << end();
   trace(9998, "run") << "its type is " << get(Type, element_type->value).name << end();
   reagent element;
   element.set_value(src);
-  element.type = new type_tree(*element_type);
+  element.type = element_type;
   // Read element
   products.push_back(read_memory(element));
   break;
 }
 
 :(code)
-type_tree* array_element(const type_tree* type) {
+type_tree* copy_array_element(const type_tree* type) {
   if (type->right->left) {
     assert(!type->right->left->left);
-    return type->right->left;
+    return new type_tree(*type->right->left);
   }
-  return type->right;
+  assert(type->right);
+  // array:<type>:<size>? return just <type>
+  if (type->right->right && is_integer(type->right->right->name))
+    return new type_tree(type->right->name, type->right->value);  // snip type->right->right
+  return new type_tree(*type->right);
 }
 
 int array_length(const reagent& x) {
@@ -331,7 +338,7 @@ case PUT_INDEX: {
   reagent value = inst.ingredients.at(2);
   // Update PUT_INDEX value in Check
   reagent element;
-  element.type = new type_tree(*array_element(base.type));
+  element.type = copy_array_element(base.type);
   if (!types_coercible(element, value)) {
     raise << maybe(get(Recipe, r).name) << "'put-index " << base.original_string << ", " << inst.ingredients.at(1).original_string << "' should store " << names_to_string_without_quotes(element.type) << " but " << value.name << " has type " << names_to_string_without_quotes(value.type) << '\n' << end();
     break;
@@ -350,12 +357,13 @@ case PUT_INDEX: {
   reagent index = current_instruction().ingredients.at(1);
   // Update PUT_INDEX index in Run
   vector<double> index_val(read_memory(index));
-  type_tree* element_type = array_element(base.type);
   if (index_val.at(0) < 0 || index_val.at(0) >= get_or_insert(Memory, base_address)) {
     raise << maybe(current_recipe_name()) << "invalid index " << no_scientific(index_val.at(0)) << '\n' << end();
     break;
   }
+  type_tree* element_type = copy_array_element(base.type);
   int address = base_address + 1 + index_val.at(0)*size_of(element_type);
+  delete element_type;
   trace(9998, "run") << "address to copy to is " << address << end();
   // optimization: directly write the element rather than updating 'product'
   // and writing the entire array
diff --git a/032exclusive_container.cc b/032exclusive_container.cc
index ad82824d..e9f918f4 100644
--- a/032exclusive_container.cc
+++ b/032exclusive_container.cc
@@ -31,18 +31,23 @@ def main [
 +mem: storing 35 in location 6
 
 :(before "End size_of(type) Cases")
-if (t.kind == EXCLUSIVE_CONTAINER) {
+if (t.kind == EXCLUSIVE_CONTAINER) return get(Container_metadata, type).size;
+:(before "End compute_container_metadata Cases")
+if (info.kind == EXCLUSIVE_CONTAINER) {
+  container_metadata metadata;
   // size of an exclusive container is the size of its largest variant
   // (So like containers, it can't contain arrays.)
-  int result = 0;
-  for (int i = 0; i < SIZE(t.elements); ++i) {
-    reagent tmp;
-    tmp.type = new type_tree(*type);
-    int size = size_of(variant_type(tmp, i));
-    if (size > result) result = size;
+  int size = 0;
+  for (int i = 0; i < SIZE(info.elements); ++i) {
+    reagent element = info.elements.at(i);
+    // Compute Exclusive Container Metadata(element)
+    compute_container_metadata(element);
+    int variant_size = size_of(element);
+    if (variant_size > size) size = variant_size;
   }
   // ...+1 for its tag.
-  return result+1;
+  metadata.size = size+1;
+  Container_metadata.push_back(pair<type_tree*, container_metadata>(new type_tree(*type), metadata));
 }
 
 //:: To access variants of an exclusive container, use 'maybe-convert'.
diff --git a/033address.cc b/033address.cc
index 2ea35a59..64618d13 100644
--- a/033address.cc
+++ b/033address.cc
@@ -500,6 +500,12 @@ canonize_type(product);
 canonize_type(lhs);
 canonize_type(rhs);
 
+:(before "Compute Container Metadata(reagent rcopy)")
+if (!canonize_type(rcopy)) return;
+
+:(before "Compute Container Metadata(element)")
+assert(!has_property(element, "lookup"));
+
 :(code)
 bool canonize_type(reagent& r) {
   while (has_property(r, "lookup")) {
diff --git a/042name.cc b/042name.cc
index a53144ea..42011052 100644
--- a/042name.cc
+++ b/042name.cc
@@ -18,7 +18,7 @@ def main [
 +error: main: use before set: y
 # todo: detect conditional defines
 
-:(after "End Type Modifying Transforms")
+:(after "Transform.push_back(compute_container_metadata)")  // we need sizes for all types
 Transform.push_back(transform_names);  // idempotent
 
 :(before "End Globals")
diff --git a/057shape_shifting_container.cc b/057shape_shifting_container.cc
index fa587595..92c2475a 100644
--- a/057shape_shifting_container.cc
+++ b/057shape_shifting_container.cc
@@ -246,12 +246,23 @@ def main [
 +mem: storing 1 in location 4
 
 :(before "End element_type Special-cases")
-if (contains_type_ingredient(element)) {
-  if (!type->right)
-    raise << "illegal type " << names_to_string(type) << " seems to be missing a type ingredient or three\n" << end();
-  replace_type_ingredients(element.type, type->right, info);
+replace_type_ingredients(element, type, info);
+:(before "Compute Container Metadata(element)")
+replace_type_ingredients(element, type, info);
+:(before "Compute Exclusive Container Metadata(element)")
+replace_type_ingredients(element, type, info);
+:(code)
+void replace_type_ingredients(reagent& element, const type_tree* caller_type, const type_info& info) {
+  if (contains_type_ingredient(element)) {
+    if (!caller_type->right)
+      raise << "illegal type " << names_to_string(caller_type) << " seems to be missing a type ingredient or three\n" << end();
+    replace_type_ingredients(element.type, caller_type->right, info);
+  }
 }
 
+:(after "Compute size_of Container")
+assert(!contains_type_ingredient(type));
+
 :(code)
 bool contains_type_ingredient(const reagent& x) {
   return contains_type_ingredient(x.type);
diff --git a/078hash.cc b/078hash.cc
index 91db00ba..36de2fda 100644
--- a/078hash.cc
+++ b/078hash.cc
@@ -78,7 +78,7 @@ size_t hash_mu_array(size_t h, const reagent& r) {
   int size = get_or_insert(Memory, r.value);
   reagent elem = r;
   delete elem.type;
-  elem.type = new type_tree(*array_element(r.type));
+  elem.type = copy_array_element(r.type);
   for (int i=0, address = r.value+1; i < size; ++i, address += size_of(elem)) {
     reagent tmp = elem;
     tmp.value = address;