From 8e1c4783692824238b2d55f8e00bd996261d521c Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Sun, 15 May 2016 18:06:28 -0700 Subject: 2965 - update refcounts when copying containers This is hopefully quite thorough. I handle nested containers, as well as exclusive containers that might contain addresses only when the tag has a specific value. --- 003trace.cc | 3 + 033exclusive_container.cc | 10 ++- 036refcount.cc | 178 ++++++++++++++++++++++++++++++----------- 050scenario.cc | 6 +- 057shape_shifting_container.cc | 17 ++-- 5 files changed, 149 insertions(+), 65 deletions(-) diff --git a/003trace.cc b/003trace.cc index 8859ae96..65f38eca 100644 --- a/003trace.cc +++ b/003trace.cc @@ -166,6 +166,9 @@ if (Passed && !Hide_errors && trace_count("error") > 0) { ++Num_failures; } +// Just for debugging. +#define dbg trace(0, "a") + :(before "End Types") struct end {}; :(before "End Tracing") diff --git a/033exclusive_container.cc b/033exclusive_container.cc index 3811fd03..dc84f2b7 100644 --- a/033exclusive_container.cc +++ b/033exclusive_container.cc @@ -169,10 +169,14 @@ case MAYBE_CONVERT: { :(code) const reagent variant_type(const reagent& base, int tag) { + return variant_type(base.type, tag); +} + +const reagent variant_type(const type_tree* type, int tag) { assert(tag >= 0); - assert(contains_key(Type, base.type->value)); - assert(!get(Type, base.type->value).name.empty()); - const type_info& info = get(Type, base.type->value); + assert(contains_key(Type, type->value)); + assert(!get(Type, type->value).name.empty()); + const type_info& info = get(Type, type->value); assert(info.kind == EXCLUSIVE_CONTAINER); reagent/*copy*/ element = info.elements.at(tag); // End variant_type Special-cases diff --git a/036refcount.cc b/036refcount.cc index 08afca08..bb32ada5 100644 --- a/036refcount.cc +++ b/036refcount.cc @@ -154,10 +154,12 @@ def main [ ] +run: {1: ("address" "number")} <- new {number: "type"} +mem: incrementing refcount of 1000: 0 -> 1 +# merging in an address increments refcount +run: {2: "foo"} <- merge {1: "literal", "p": ()}, {1: ("address" "number")} ++mem: incrementing refcount of 1000: 1 -> 2 +run: {4: ("address" "number")}, {5: "boolean"} <- maybe-convert {2: "foo"}, {1: "variant", "p": ()} # maybe-convert increments refcount on success -+mem: incrementing refcount of 1000: 1 -> 2 ++mem: incrementing refcount of 1000: 2 -> 3 :(after "Write Memory in Successful MAYBE_CONVERT") if (is_mu_address(product)) @@ -176,9 +178,9 @@ def main [ *2:address:foo <- put *2:address:foo, x:offset, 1:address:number 3:foo <- copy *2:address:foo ] -+transform: --- compute address offsets for foo ++transform: compute address offsets for container foo +transform: checking container foo, element 0 -+transform: container foo contains an address at offset 0 ++transform: address at offset 0 +run: {1: ("address" "number")} <- new {number: "type"} +mem: incrementing refcount of 1000: 0 -> 1 +run: {2: ("address" "foo"), "lookup": ()} <- put {2: ("address" "foo"), "lookup": ()}, {x: "offset"}, {1: ("address" "number")} @@ -196,8 +198,12 @@ struct address_element_info { payload_size = p; } }; +:(before "struct container_metadata ") +// valid fields for containers: size, offset, address, maybe_address (if container directly or indirectly contains exclusive containers with addresses) +// valid fields for exclusive containers: size, maybe_address :(before "End container_metadata Fields") vector address; // list of offsets containing addresses, and the sizes of their corresponding payloads +map, vector > maybe_address; //: populate metadata.address in a separate transform, because it requires //: already knowing the sizes of all types @@ -207,8 +213,10 @@ Transform.push_back(compute_container_address_offsets); :(code) void compute_container_address_offsets(const recipe_ordinal r) { recipe& caller = get(Recipe, r); + trace(9992, "transform") << "--- compute address offsets for " << caller.name << end(); for (int i = 0; i < SIZE(caller.steps); ++i) { instruction& inst = caller.steps.at(i); + trace(9993, "transform") << "- compute address offsets for " << to_string(inst) << end(); for (int i = 0; i < SIZE(inst.ingredients); ++i) compute_container_address_offsets(inst.ingredients.at(i)); for (int i = 0; i < SIZE(inst.products); ++i) @@ -230,67 +238,82 @@ void compute_container_address_offsets(type_tree* type) { if (info.kind == CONTAINER) { container_metadata& metadata = get(Container_metadata, type); if (!metadata.address.empty()) return; - trace(9992, "transform") << "--- compute address offsets for " << info.name << end(); - append_addresses(0, type, metadata.address); + trace(9994, "transform") << "compute address offsets for container " << info.name << end(); + if (!append_addresses(0, type, metadata.address, metadata)) + return; // error + } + if (info.kind == EXCLUSIVE_CONTAINER) { + container_metadata& metadata = get(Container_metadata, type); + if (!metadata.maybe_address.empty()) return; + trace(9994, "transform") << "compute address offsets for exclusive container " << info.name << end(); + for (int tag = 0; tag < SIZE(info.elements); ++tag) { + if (!append_addresses(/*skip tag offset*/1, variant_type(type, tag).type, get_or_insert(metadata.maybe_address, pair(/*tag offset*/0, tag)), metadata)) + return; // error + } } } -void append_addresses(int base_offset, const type_tree* type, vector& out) { - stack > containers; - containers.push(pair(new type_tree(*type), 0)); - int curr_offset = base_offset; - while (!containers.empty()) { - const type_tree* curr_type = containers.top().first; - int curr_index = containers.top().second; - type_ordinal t = curr_type->value; - assert(t); - type_info& curr_info = get(Type, t); - assert(curr_info.kind == CONTAINER); - assert(get(Type, curr_type->value).kind == CONTAINER); - if (curr_index >= SIZE(get(Type, curr_type->value).elements)) { - delete curr_type; - containers.pop(); - continue; - } - trace(9993, "transform") << "checking container " << curr_type->name << ", element " << curr_index << end(); - reagent/*copy*/ element = element_type(curr_type, curr_index); +// returns false on error (raised elsewhere) +//: error status is used in later layers +bool append_addresses(int base_offset, const type_tree* type, vector& out, container_metadata& out_metadata) { + const type_info& info = get(Type, type->value); + if (type->name == "address") { + out.push_back(address_element_info(base_offset, payload_size(type))); + return true; + } + if (info.kind == PRIMITIVE) return true; + for (int curr_index = 0, curr_offset = base_offset; curr_index < SIZE(info.elements); ++curr_index) { + trace(9993, "transform") << "checking container " << type->name << ", element " << curr_index << end(); + reagent/*copy*/ element = element_type(type, curr_index); // Compute Container Address Offset(element) - // base case if (is_mu_address(element)) { - trace(9993, "transform") << "container " << type->name << " contains an address at offset " << curr_offset << end(); + trace(9993, "transform") << "address at offset " << curr_offset << end(); out.push_back(address_element_info(curr_offset, payload_size(element))); + ++curr_offset; } - // recursive case and update loop variables - if (is_mu_container(element)) { - ++containers.top().second; - containers.push(pair(new type_tree(*element.type), 0)); + else if (is_mu_container(element)) { + if (!append_addresses(curr_offset, element.type, out, out_metadata)) + return false; // error + curr_offset += size_of(element); } else if (is_mu_exclusive_container(element)) { - // TODO: stub - ++containers.top().second; - ++curr_offset; + const type_info& element_info = get(Type, element.type->value); + for (int tag = 0; tag < SIZE(element_info.elements); ++tag) { + vector& tmp = get_or_insert(out_metadata.maybe_address, pair(curr_offset, tag)); + if (tmp.empty()) { + if (!append_addresses(curr_offset+1, variant_type(element.type, tag).type, tmp, out_metadata)) + return false; // error + } + } + curr_offset += size_of(element); } else { - ++containers.top().second; + // non-address primitive ++curr_offset; } } + return true; +} + +int payload_size(const type_tree* type) { + assert(type->name == "address"); + return size_of(type->right)+/*refcount*/1; } //: use metadata.address to update refcounts within containers, arrays and //: exclusive containers :(before "End write_memory(x) Special-cases") -if (is_mu_container(x)) +if (is_mu_container(x) || is_mu_exclusive_container(x)) update_container_refcounts(x, data); :(before "End Update Refcounts in PUT") -if (is_mu_container(element)) +if (is_mu_container(element) || is_mu_exclusive_container(element)) update_container_refcounts(element, ingredients.at(2)); :(before "End Update Refcounts in PUT_INDEX") -if (is_mu_container(element)) +if (is_mu_container(element) || is_mu_exclusive_container(element)) update_container_refcounts(element, value); :(before "End Update Refcounts in Successful MAYBE_CONVERT") -if (is_mu_container(product)) { +if (is_mu_container(product) || is_mu_exclusive_container(product)) { vector data; for (int i = 0; i < size_of(product); ++i) data.push_back(get_or_insert(Memory, base_address+/*skip tag*/1+i)); @@ -299,12 +322,19 @@ if (is_mu_container(product)) { :(code) void update_container_refcounts(const reagent& x, const vector& data) { - assert(is_mu_container(x)); + assert(is_mu_container(x) || is_mu_exclusive_container(x)); const container_metadata& metadata = get(Container_metadata, x.type); for (int i = 0; i < SIZE(metadata.address); ++i) { const address_element_info& info = metadata.address.at(i); update_refcounts(get_or_insert(Memory, x.value + info.offset), data.at(info.offset), info.payload_size); } + for (map, vector >::const_iterator p = metadata.maybe_address.begin(); p != metadata.maybe_address.end(); ++p) { + if (data.at(p->first.first) != p->first.second) continue; + for (int i = 0; i < SIZE(p->second); ++i) { + const address_element_info& info = p->second.at(i); + update_refcounts(get_or_insert(Memory, x.value + info.offset), data.at(info.offset), info.payload_size); + } + } } :(scenario refcounts_put_container) @@ -365,9 +395,9 @@ def main [ +run: {2: "bar"} <- merge {1: ("address" "number")} +mem: incrementing refcount of 1000: 1 -> 2 +run: {3: "foo"} <- merge {1: "literal", "b": ()}, {2: "bar"} -# todo: refcount should increment here as well, but we can't handle exclusive-containers (sometimes) containing addresses yet -+run: {5: "bar"}, {6: "boolean"} <- maybe-convert {3: "foo"}, {1: "variant", "b": ()} +mem: incrementing refcount of 1000: 2 -> 3 ++run: {5: "bar"}, {6: "boolean"} <- maybe-convert {3: "foo"}, {1: "variant", "b": ()} ++mem: incrementing refcount of 1000: 3 -> 4 :(scenario refcounts_copy_doubly_nested) container foo [ @@ -390,9 +420,9 @@ def main [ *3:address:foo <- put *3:address:foo, 1:offset/b, *2:address:curr 4:foo <- copy *3:address:foo ] -+transform: --- compute address offsets for foo ++transform: compute address offsets for container foo +transform: checking container foo, element 1 -+transform: container foo contains an address at offset 3 ++transform: address at offset 3 +run: {1: ("address" "number")} <- new {number: "type"} +mem: incrementing refcount of 1000: 0 -> 1 # storing an address in a container updates its refcount @@ -405,6 +435,64 @@ def main [ +run: {4: "foo"} <- copy {3: ("address" "foo"), "lookup": ()} +mem: incrementing refcount of 1000: 3 -> 4 +:(scenario refcounts_copy_exclusive_container_within_container) +container foo [ + a:number + b:bar +] +exclusive-container bar [ + x:number + y:number + z:address:number +] +def main [ + 1:address:number <- new number:type + 2:bar <- merge 0/x, 34 + 3:foo <- merge 12, 2:bar + 5:bar <- merge 1/y, 35 + 6:foo <- merge 13, 5:bar + 8:bar <- merge 2/z, 1:address:number + 9:foo <- merge 14, 8:bar + 11:foo <- copy 9:foo +] ++run: {1: ("address" "number")} <- new {number: "type"} ++mem: incrementing refcount of 1000: 0 -> 1 +# no change while merging items of other types ++run: {8: "bar"} <- merge {2: "literal", "z": ()}, {1: ("address" "number")} ++mem: incrementing refcount of 1000: 1 -> 2 ++run: {9: "foo"} <- merge {14: "literal"}, {8: "bar"} ++mem: incrementing refcount of 1000: 2 -> 3 ++run: {11: "foo"} <- copy {9: "foo"} ++mem: incrementing refcount of 1000: 3 -> 4 + +:(scenario refcounts_copy_container_within_exclusive_container) +exclusive-container foo [ + a:number + b:bar +] +container bar [ + x:number + y:number + z:address:number +] +def main [ + 1:address:number <- new number:type + 2:foo <- merge 0/a, 34 + 6:foo <- merge 0/a, 35 + 10:bar <- merge 2/x, 15/y, 1:address:number + 13:foo <- merge 1/b, 10:bar + 17:foo <- copy 13:foo +] ++run: {1: ("address" "number")} <- new {number: "type"} ++mem: incrementing refcount of 1000: 0 -> 1 +# no change while merging items of other types ++run: {10: "bar"} <- merge {2: "literal", "x": ()}, {15: "literal", "y": ()}, {1: ("address" "number")} ++mem: incrementing refcount of 1000: 1 -> 2 ++run: {13: "foo"} <- merge {1: "literal", "b": ()}, {10: "bar"} ++mem: incrementing refcount of 1000: 2 -> 3 ++run: {17: "foo"} <- copy {13: "foo"} ++mem: incrementing refcount of 1000: 3 -> 4 + :(code) bool is_mu_container(const reagent& r) { if (r.type->value == 0) return false; @@ -417,7 +505,3 @@ bool is_mu_exclusive_container(const reagent& r) { type_info& info = get(Type, r.type->value); return info.kind == EXCLUSIVE_CONTAINER; } - -// todo: -// exclusive container sometimes containing address -// container containing exclusive container sometimes containing address diff --git a/050scenario.cc b/050scenario.cc index 30002d77..4a455187 100644 --- a/050scenario.cc +++ b/050scenario.cc @@ -630,15 +630,15 @@ put(Recipe_ordinal, "check-trace-count-for-label", CHECK_TRACE_COUNT_FOR_LABEL); :(before "End Primitive Recipe Checks") case CHECK_TRACE_COUNT_FOR_LABEL: { if (SIZE(inst.ingredients) != 2) { - raise << maybe(get(Recipe, r).name) << "'check-trace-for-label' requires exactly two ingredients, but got '" << to_original_string(inst) << "'\n" << end(); + raise << maybe(get(Recipe, r).name) << "'check-trace-count-for-label' requires exactly two ingredients, but got '" << to_original_string(inst) << "'\n" << end(); break; } if (!is_mu_number(inst.ingredients.at(0))) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'check-trace-for-label' should be a number (count), but got " << inst.ingredients.at(0).original_string << '\n' << end(); + raise << maybe(get(Recipe, r).name) << "first ingredient of 'check-trace-count-for-label' should be a number (count), but got " << inst.ingredients.at(0).original_string << '\n' << end(); break; } if (!is_literal_string(inst.ingredients.at(1))) { - raise << maybe(get(Recipe, r).name) << "second ingredient of 'check-trace-for-label' should be a literal string (label), but got " << inst.ingredients.at(1).original_string << '\n' << end(); + raise << maybe(get(Recipe, r).name) << "second ingredient of 'check-trace-count-for-label' should be a literal string (label), but got " << inst.ingredients.at(1).original_string << '\n' << end(); break; } break; diff --git a/057shape_shifting_container.cc b/057shape_shifting_container.cc index d1feb0fb..fb847899 100644 --- a/057shape_shifting_container.cc +++ b/057shape_shifting_container.cc @@ -252,15 +252,8 @@ replace_type_ingredients(element, type, info); :(before "Compute Exclusive Container Size(element)") replace_type_ingredients(element, type, info); :(before "Compute Container Address Offset(element)") -replace_type_ingredients(element, curr_type, curr_info); -if (contains_type_ingredient(element)) { - // error raised elsewhere; just clean up and leave - while (!containers.empty()) { - delete containers.top().first; - containers.pop(); - } - return; -} +replace_type_ingredients(element, type, info); +if (contains_type_ingredient(element)) return true; // error raised elsewhere :(code) void replace_type_ingredients(reagent& element, const type_tree* caller_type, const type_info& info) { @@ -613,7 +606,7 @@ def main [ :(before "End variant_type Special-cases") if (contains_type_ingredient(element)) { - if (!base.type->right) - raise << "illegal type '" << to_string(base.type) << "' seems to be missing a type ingredient or three\n" << end(); - replace_type_ingredients(element.type, base.type->right, info); + if (!type->right) + raise << "illegal type '" << to_string(type) << "' seems to be missing a type ingredient or three\n" << end(); + replace_type_ingredients(element.type, type->right, info); } -- cgit 1.4.1-2-gfad0