diff options
| -rw-r--r-- | 030container.cc | 257 | ||||
| -rw-r--r-- | 032array.cc | 80 | ||||
| -rw-r--r-- | 033exclusive_container.cc | 35 | ||||
| -rw-r--r-- | 035lookup.cc | 8 | ||||
| -rw-r--r-- | 042name.cc | 2 | ||||
| -rw-r--r-- | 055shape_shifting_container.cc | 140 |
6 files changed, 84 insertions, 438 deletions
diff --git a/030container.cc b/030container.cc index 2ee8351d..f4aaafd4 100644 --- a/030container.cc +++ b/030container.cc @@ -13,8 +13,8 @@ get(Type, point).elements.push_back(reagent("y:number")); //: numbers, no matter how large they are. //: Tests in this layer often explicitly set up memory before reading it as a -//: container. Don't do this in general. I'm tagging exceptions with /unsafe to -//: skip later checks. +//: container. Don't do this in general. I'm tagging such cases with /unsafe; +//: they'll be exceptions to later checks. :(scenario copy_multiple_locations) def main [ 1:num <- copy 34 @@ -92,182 +92,28 @@ def main [ ] +mem: storing 0 in location 7 -//: Can't put this in type_info because later layers will add support for more -//: complex type trees where metadata depends on *combinations* of types. -:(before "struct reagent") -struct container_metadata { - int size; - vector<int> offset; // not used by exclusive containers - // 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 = other.metadata; -:(before "End reagent Copy Constructor") -metadata = other.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") -restore_container_metadata(); -:(before "End One-time Setup") -atexit(clear_container_metadata); -:(code) -// invariant: Container_metadata always contains a superset of Container_metadata_snapshot -void restore_container_metadata() { - for (int i = 0; i < SIZE(Container_metadata); ++i) { - assert(Container_metadata.at(i).first); - if (i < SIZE(Container_metadata_snapshot)) { - assert(Container_metadata.at(i).first == Container_metadata_snapshot.at(i).first); - continue; - } - delete Container_metadata.at(i).first; - Container_metadata.at(i).first = NULL; - } - Container_metadata.resize(SIZE(Container_metadata_snapshot)); -} -void clear_container_metadata() { - Container_metadata_snapshot.clear(); - for (int i = 0; i < SIZE(Container_metadata); ++i) { - delete Container_metadata.at(i).first; - Container_metadata.at(i).first = NULL; - } - Container_metadata.clear(); -} - -//: do no work in size_of, simply lookup Container_metadata - -:(before "End size_of(reagent r) Special-cases") -if (r.metadata.size) return r.metadata.size; - :(before "End size_of(type) Special-cases") -const type_tree* base_type = type; -// Update base_type in size_of(type) -if (!contains_key(Type, base_type->value)) { - raise << "no such type " << base_type->value << '\n' << end(); +if (type->value == -1) return 1; // error value, but we'll raise it elsewhere +if (type->value == 0) return 1; +if (!contains_key(Type, type->value)) { + raise << "no such type " << type->value << '\n' << end(); return 0; } -type_info t = get(Type, base_type->value); +type_info t = get(Type, type->value); if (t.kind == CONTAINER) { - // Compute size_of Container - if (!contains_key(Container_metadata, type)) { - raise << "unknown size for container type '" << to_string(type) << "'\n" << end(); -//? DUMP(""); - return 0; - } - 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 "End Type Modifying Transforms") -Transform.push_back(compute_container_sizes); // idempotent -:(code) -void compute_container_sizes(const recipe_ordinal r) { - recipe& caller = get(Recipe, r); - trace(9992, "transform") << "--- compute container sizes for " << caller.name << end(); - for (int i = 0; i < SIZE(caller.steps); ++i) { - instruction& inst = caller.steps.at(i); - trace(9993, "transform") << "- compute container sizes for " << to_string(inst) << end(); - for (int i = 0; i < SIZE(inst.ingredients); ++i) - compute_container_sizes(inst.ingredients.at(i), " in '"+to_original_string(inst)+"'"); - for (int i = 0; i < SIZE(inst.products); ++i) - compute_container_sizes(inst.products.at(i), " in '"+to_original_string(inst)+"'"); - } -} - -void compute_container_sizes(reagent& r, const string& location_for_error_messages) { - expand_type_abbreviations(r.type); - if (is_literal(r) || is_dummy(r)) return; - reagent rcopy = r; - // Compute Container Size(reagent rcopy) - set<type_tree> pending_metadata; // might actually be faster to just convert to string rather than compare type_tree directly; so far the difference is negligible - compute_container_sizes(rcopy.type, pending_metadata, location_for_error_messages); - if (contains_key(Container_metadata, rcopy.type)) - r.metadata = get(Container_metadata, rcopy.type); -} - -void compute_container_sizes(const type_tree* type, set<type_tree>& pending_metadata, const string& location_for_error_messages) { - if (!type) return; - trace(9993, "transform") << "compute container sizes for " << to_string(type) << end(); - if (contains_key(Container_metadata, type)) return; - if (contains_key(pending_metadata, *type)) return; - pending_metadata.insert(*type); - if (!type->atom) { - if (!type->left->atom) { - raise << "invalid type " << to_string(type) << location_for_error_messages << '\n' << end(); - return; + // 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; } - if (type->left->name == "address") - compute_container_sizes(payload_type(type), pending_metadata, location_for_error_messages); - // End compute_container_sizes Non-atom Special-cases - return; + result += size_of(element_type(type, i)); } - assert(type->atom); - if (!contains_key(Type, type->value)) return; // error raised elsewhere - type_info& info = get(Type, type->value); - if (info.kind == CONTAINER) - compute_container_sizes(info, type, pending_metadata, location_for_error_messages); - // End compute_container_sizes Atom Special-cases -} - -void compute_container_sizes(const type_info& container_info, const type_tree* full_type, set<type_tree>& pending_metadata, const string& location_for_error_messages) { - assert(container_info.kind == CONTAINER); - // size of a container is the sum of the sizes of its element - // (So it can only contain arrays if they're static and include their - // length in the type.) - container_metadata metadata; - for (int i = 0; i < SIZE(container_info.elements); ++i) { - reagent/*copy*/ element = container_info.elements.at(i); - // Compute Container Size(element, full_type) - compute_container_sizes(element.type, pending_metadata, location_for_error_messages); - metadata.offset.push_back(metadata.size); // save previous size as offset - metadata.size += size_of(element.type); - } - Container_metadata.push_back(pair<type_tree*, container_metadata>(new type_tree(*full_type), metadata)); -} - -const type_tree* payload_type(const type_tree* type) { - assert(!type->atom); - const type_tree* result = type->right; - assert(!result->atom); - if (!result->right) return result->left; return result; } -container_metadata& get(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; - } - raise << "unknown size for type '" << to_string(key) << "'\n" << end(); - exit(1); -} - -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->atom != b->atom) return false; - if (a->atom) return a->value == b->value; - return matches(a->left, b->left) && matches(a->right, b->right); -} - :(scenario stash_container) def main [ 1:num <- copy 34 # first @@ -277,70 +123,6 @@ def main [ ] +app: foo: 34 35 36 -//: for the following unit tests we'll do the work of the transform by hand - -:(before "End Unit Tests") -void test_container_sizes() { - // a container we don't have the size for - reagent r("x:point"); - CHECK(!contains_key(Container_metadata, r.type)); - // scan - compute_container_sizes(r, ""); - // the reagent we scanned knows its size - CHECK_EQ(r.metadata.size, 2); - // the global table also knows its size - CHECK(contains_key(Container_metadata, r.type)); - CHECK_EQ(get(Container_metadata, r.type).size, 2); -} - -void test_container_sizes_through_aliases() { - // a new alias for a container - put(Type_abbreviations, "pt", new_type_tree("point")); - reagent r("x:pt"); - // scan - compute_container_sizes(r, ""); - // the reagent we scanned knows its size - CHECK_EQ(r.metadata.size, 2); - // the global table also knows its size - CHECK(contains_key(Container_metadata, r.type)); - CHECK_EQ(get(Container_metadata, r.type).size, 2); -} - -void test_container_sizes_nested() { - // a container we don't have the size for - reagent r("x:point-number"); - CHECK(!contains_key(Container_metadata, r.type)); - // scan - compute_container_sizes(r, ""); - // the reagent we scanned knows its size - CHECK_EQ(r.metadata.size, 3); - // the global table also knows its size - CHECK(contains_key(Container_metadata, r.type)); - CHECK_EQ(get(Container_metadata, r.type).size, 3); -} - -void test_container_sizes_recursive() { - // define a container containing an address to itself - run("container foo [\n" - " x:num\n" - " y:address:foo\n" - "]\n"); - reagent r("x:foo"); - compute_container_sizes(r, ""); - CHECK_EQ(r.metadata.size, 2); -} - -void test_container_sizes_from_address() { - // a container we don't have the size for - reagent container("x:point"); - CHECK(!contains_key(Container_metadata, container.type)); - // scanning an address to the container precomputes the size of the container - reagent r("x:address:point"); - compute_container_sizes(r, ""); - CHECK(contains_key(Container_metadata, container.type)); - CHECK_EQ(get(Container_metadata, container.type).size, 2); -} - //:: To access elements of a container, use 'get' //: 'get' takes a 'base' container and an 'offset' into it and returns the //: appropriate element of the container value. @@ -413,8 +195,9 @@ case GET: { // Update GET base_type in Run int offset = ingredients.at(1).at(0); if (offset < 0 || offset >= SIZE(get(Type, base_type->value).elements)) break; // copied from Check above - assert(base.metadata.size); - int src = base_address + base.metadata.offset.at(offset); + int src = base_address; + for (int i = 0; i < offset; ++i) + src += size_of(element_type(base.type, i)); trace(9998, "run") << "address to copy is " << src << end(); //: use base.type rather than base_type because later layers will introduce compound types reagent/*copy*/ element = element_type(base.type, offset); @@ -569,7 +352,9 @@ case PUT: { // Update PUT base_type in Run int offset = ingredients.at(1).at(0); if (offset < 0 || offset >= SIZE(get(Type, base_type->value).elements)) break; // copied from Check above - int address = base_address + base.metadata.offset.at(offset); + int address = base_address; + for (int i = 0; i < offset; ++i) + address += size_of(element_type(base.type, i)); trace(9998, "run") << "address to copy to is " << address << end(); // optimization: directly write the element rather than updating 'product' // and writing the entire container diff --git a/032array.cc b/032array.cc index a696b450..3bde42fb 100644 --- a/032array.cc +++ b/032array.cc @@ -200,86 +200,6 @@ def foo [ ] # shouldn't die -//:: containers inside arrays -//: make sure we compute container sizes inside arrays - -:(before "End compute_container_sizes Non-atom Special-cases") -else if (type->left->name == "array") - compute_container_sizes(array_element(type), pending_metadata, location_for_error_messages); - -:(before "End Unit Tests") -void test_container_sizes_from_array() { - // a container we don't have the size for - reagent container("x:point"); - CHECK(!contains_key(Container_metadata, container.type)); - // scanning an array of the container precomputes the size of the container - reagent r("x:array:point"); - compute_container_sizes(r, ""); - CHECK(contains_key(Container_metadata, container.type)); - CHECK_EQ(get(Container_metadata, container.type).size, 2); -} - -void test_container_sizes_from_address_to_array() { - // a container we don't have the size for - reagent container("x:point"); - CHECK(!contains_key(Container_metadata, container.type)); - // scanning an address to an array of the container precomputes the size of the container - reagent r("x:address:array:point"); - compute_container_sizes(r, ""); - CHECK(contains_key(Container_metadata, container.type)); - CHECK_EQ(get(Container_metadata, container.type).size, 2); -} - -void test_container_sizes_from_static_array() { - // a container we don't have the size for - reagent container("x:point"); - int old_size = SIZE(Container_metadata); - // scanning an address to an array of the container precomputes the size of the container - reagent r("x:array:point:10"); - compute_container_sizes(r, ""); - CHECK(contains_key(Container_metadata, container.type)); - CHECK_EQ(get(Container_metadata, container.type).size, 2); - // no non-container types precomputed - CHECK_EQ(SIZE(Container_metadata)-old_size, 1); -} - -void test_container_sizes_from_address_to_static_array() { - // a container we don't have the size for - reagent container("x:point"); - int old_size = SIZE(Container_metadata); - // scanning an address to an array of the container precomputes the size of the container - reagent r("x:address:array:point:10"); - compute_container_sizes(r, ""); - CHECK(contains_key(Container_metadata, container.type)); - CHECK_EQ(get(Container_metadata, container.type).size, 2); - // no non-container types precomputed - CHECK_EQ(SIZE(Container_metadata)-old_size, 1); -} - -void test_container_sizes_from_repeated_address_and_array_types() { - // a container we don't have the size for - reagent container("x:point"); - int old_size = SIZE(Container_metadata); - // scanning repeated address and array types modifying the container precomputes the size of the container - reagent r("x:address:array:address:array:point:10"); - compute_container_sizes(r, ""); - CHECK(contains_key(Container_metadata, container.type)); - CHECK_EQ(get(Container_metadata, container.type).size, 2); - // no non-container types precomputed - CHECK_EQ(SIZE(Container_metadata)-old_size, 1); -} - -void test_container_sizes_on_unknown_type() { - // a container we don't have the size for - reagent container("x:point"); - int old_size = SIZE(Container_metadata); - // scanning address to array with a typo - reagent r("x:address:array:adress:number"); - compute_container_sizes(r, ""); // should not crash - // no non-container types precomputed - CHECK_EQ(SIZE(Container_metadata), old_size); -} - //:: To access elements of an array, use 'index' :(scenario index) diff --git a/033exclusive_container.cc b/033exclusive_container.cc index 29a524c9..44161d7c 100644 --- a/033exclusive_container.cc +++ b/033exclusive_container.cc @@ -15,9 +15,9 @@ get(Type, tmp).elements.push_back(reagent("i:number")); get(Type, tmp).elements.push_back(reagent("p:point")); } -//: Tests in this layer often explicitly set up memory before reading it as an -//: array. Don't do this in general. I'm tagging exceptions with /raw to keep -//: checks in future layers from flagging them. +//: Tests in this layer often explicitly set up memory before reading it as a +//: container. Don't do this in general. I'm tagging such cases with /unsafe; +//: they'll be exceptions to later checks. :(scenario copy_exclusive_container) # Copying exclusive containers copies all their contents and an extra location for the tag. def main [ @@ -32,30 +32,17 @@ def main [ :(before "End size_of(type) Special-cases") if (t.kind == EXCLUSIVE_CONTAINER) { - // Compute size_of Exclusive Container - return get(Container_metadata, type).size; -} -:(before "End compute_container_sizes Atom Special-cases") -if (info.kind == EXCLUSIVE_CONTAINER) { - compute_exclusive_container_sizes(info, type, pending_metadata, location_for_error_messages); -} - -:(code) -void compute_exclusive_container_sizes(const type_info& exclusive_container_info, const type_tree* full_type, set<type_tree>& pending_metadata, const string& location_for_error_messages) { // size of an exclusive container is the size of its largest variant - // (So, like containers, it can only contain arrays if they're static and - // include their length in the type.) - container_metadata metadata; - for (int i = 0; i < SIZE(exclusive_container_info.elements); ++i) { - reagent/*copy*/ element = exclusive_container_info.elements.at(i); - // Compute Exclusive Container Size(element, full_type) - compute_container_sizes(element.type, pending_metadata, location_for_error_messages); - int variant_size = size_of(element); - if (variant_size > metadata.size) metadata.size = variant_size; + // (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; } // ...+1 for its tag. - ++metadata.size; - Container_metadata.push_back(pair<type_tree*, container_metadata>(new type_tree(*full_type), metadata)); + return result+1; } //:: To access variants of an exclusive container, use 'maybe-convert'. diff --git a/035lookup.cc b/035lookup.cc index 1823ae3d..a2647f5d 100644 --- a/035lookup.cc +++ b/035lookup.cc @@ -127,14 +127,6 @@ canonize_type(product); canonize_type(lhs); canonize_type(rhs); -:(before "Compute Container Size(reagent rcopy)") -if (!canonize_type(rcopy)) return; - -:(before "Compute Container Size(element, full_type)") -assert(!has_property(element, "lookup")); -:(before "Compute Exclusive Container Size(element, full_type)") -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 077eed0d..f183962c 100644 --- a/042name.cc +++ b/042name.cc @@ -18,7 +18,7 @@ def main [ +error: main: tried to read ingredient 'y' in 'x:num <- copy y:num' but it hasn't been written to yet # todo: detect conditional defines -:(after "Transform.push_back(compute_container_sizes)") +:(after "End Type Modifying Transforms") Transform.push_back(transform_names); // idempotent :(before "End Globals") diff --git a/055shape_shifting_container.cc b/055shape_shifting_container.cc index 32032456..0e7409d8 100644 --- a/055shape_shifting_container.cc +++ b/055shape_shifting_container.cc @@ -12,16 +12,8 @@ base_type = get_base_type(base_type); base_type = get_base_type(base_type); :(after "Update MAYBE_CONVERT base_type in Check") base_type = get_base_type(base_type); -:(after "Update base_type in size_of(type)") -base_type = get_base_type(base_type); :(after "Update base_type in element_type") base_type = get_base_type(base_type); -//? :(after "Update base_type in compute_container_address_offsets") -//? base_type = get_base_type(base_type); -//? :(after "Update base_type in append_container_address_offsets") -//? base_type = get_base_type(base_type); -//? :(after "Update element_base_type For Exclusive Container in append_addresses") -//? element_base_type = get_base_type(element_base_type); :(after "Update base_type in skip_addresses") base_type = get_base_type(base_type); :(replace{} "const type_tree* get_base_type(const type_tree* t)") @@ -39,6 +31,8 @@ def main [ ] # no crash +//: update size_of to handle non-atom container types + :(scenario size_of_shape_shifting_container) container foo:_t [ x:_t @@ -310,18 +304,53 @@ def main [ :(before "End element_type Special-cases") replace_type_ingredients(element, type, info, " while computing element type of container"); -:(before "Compute Container Size(element, full_type)") -replace_type_ingredients(element, full_type, container_info, location_for_error_messages); -:(before "Compute Exclusive Container Size(element, full_type)") -replace_type_ingredients(element, full_type, exclusive_container_info, location_for_error_messages); -//? :(before "Compute Container Address Offset(element)") -//? replace_type_ingredients(element, type, info, location_for_error_messages); -//? if (contains_type_ingredient(element)) return; // error raised elsewhere - -:(after "Compute size_of Container") -assert(!contains_type_ingredient(type)); -:(after "Compute size_of Exclusive Container") -assert(!contains_type_ingredient(type)); + +:(before "End size_of(type) Non-atom Special-cases") +assert(type->left->atom); +if (!contains_key(Type, type->left->value)) { + raise << "no such type " << type->left->value << '\n' << end(); + return 0; +} +type_info t = get(Type, type->left->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 (get_base_type(t.elements.at(i).type)->value == get_base_type(type)->value) { + raise << "container " << t.name << " can't include itself as a member\n" << end(); + return 0; + } + result += size_of(element_type(type, i)); + } + return result; +} +if (t.kind == EXCLUSIVE_CONTAINER) { + // 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; + } + // ...+1 for its tag. + return result+1; +} + +:(scenario complex_shape_shifting_exclusive_container) +exclusive-container foo:_a [ + x:_a + y:num +] +def main [ + 1:text <- new [abc] + 2:foo:point <- merge 0/variant, 34/xx, 35/xy + 10:point, 20:bool <- maybe-convert 2:foo:point, 0/variant +] ++mem: storing 1 in location 20 ++mem: storing 35 in location 11 :(code) bool contains_type_ingredient(const reagent& x) { @@ -539,75 +568,8 @@ def main [ 10:foo:point <- merge 14, 15, 16 1:num <- get 10:foo, 1:offset ] -+error: illegal type "foo" seems to be missing a type ingredient or three in '1:num <- get 10:foo, 1:offset' - -//:: fix up previous layers - -//: We have two transforms in previous layers -- for computing sizes and -//: offsets containing addresses for containers and exclusive containers -- -//: that we need to teach about type ingredients. - -:(before "End compute_container_sizes Non-atom Special-cases") -const type_tree* root = get_base_type(type); -if (contains_key(Type, root->value)) { - type_info& info = get(Type, root->value); - if (info.kind == CONTAINER) { - compute_container_sizes(info, type, pending_metadata, location_for_error_messages); - return; - } - if (info.kind == EXCLUSIVE_CONTAINER) { - compute_exclusive_container_sizes(info, type, pending_metadata, location_for_error_messages); - return; - } -} // otherwise error raised elsewhere - -:(before "End Unit Tests") -void test_container_sizes_shape_shifting_container() { - run("container foo:_t [\n" - " x:num\n" - " y:_t\n" - "]\n"); - reagent r("x:foo:point"); - compute_container_sizes(r, ""); - CHECK_EQ(r.metadata.size, 3); -} - -void test_container_sizes_shape_shifting_exclusive_container() { - run("exclusive-container foo:_t [\n" - " x:num\n" - " y:_t\n" - "]\n"); - reagent r("x:foo:point"); - compute_container_sizes(r, ""); - CHECK_EQ(r.metadata.size, 3); - reagent r2("x:foo:num"); - compute_container_sizes(r2, ""); - CHECK_EQ(r2.metadata.size, 2); -} - -void test_container_sizes_compound_type_ingredient() { - run("container foo:_t [\n" - " x:num\n" - " y:_t\n" - "]\n"); - reagent r("x:foo:&:point"); - compute_container_sizes(r, ""); - CHECK_EQ(r.metadata.size, 2); - // scan also pre-computes metadata for type ingredient - reagent point("x:point"); - CHECK(contains_key(Container_metadata, point.type)); - CHECK_EQ(get(Container_metadata, point.type).size, 2); -} - -void test_container_sizes_recursive_shape_shifting_container() { - run("container foo:_t [\n" - " x:num\n" - " y:&:foo:_t\n" - "]\n"); - reagent r2("x:foo:num"); - compute_container_sizes(r2, ""); - CHECK_EQ(r2.metadata.size, 2); -} +# todo: improve error message ++error: illegal type "foo" seems to be missing a type ingredient or three while computing element type of container :(scenario typos_in_container_definitions) % Hide_errors = true; |