From 15936c91a9f8023dc868a021029f84b45aa50176 Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Sun, 24 Apr 2016 00:36:30 -0700 Subject: 2863 Finally after much massaging, the 'address' and 'new' layers are adjacent. --- 030address.cc | 180 --------- 030container.cc | 779 +++++++++++++++++++++++++++++++++++++++ 031array.cc | 448 +++++++++++++++++++++++ 031container.cc | 807 ----------------------------------------- 032array.cc | 467 ------------------------ 032exclusive_container.cc | 416 +++++++++++++++++++++ 033address.cc | 387 ++++++++++++++++++++ 033exclusive_container.cc | 414 --------------------- 034new.cc | 686 +++++++++++++++++++++++++++++++++++ 035location_array.cc | 42 +++ 037new.cc | 686 ----------------------------------- 038location_array.cc | 42 --- 057shape_shifting_container.cc | 12 +- 13 files changed, 2764 insertions(+), 2602 deletions(-) delete mode 100644 030address.cc create mode 100644 030container.cc create mode 100644 031array.cc delete mode 100644 031container.cc delete mode 100644 032array.cc create mode 100644 032exclusive_container.cc create mode 100644 033address.cc delete mode 100644 033exclusive_container.cc create mode 100644 034new.cc create mode 100644 035location_array.cc delete mode 100644 037new.cc delete mode 100644 038location_array.cc diff --git a/030address.cc b/030address.cc deleted file mode 100644 index 5f86b30a..00000000 --- a/030address.cc +++ /dev/null @@ -1,180 +0,0 @@ -//: Instructions can read from addresses pointing at other locations using the -//: 'lookup' property. - -:(scenario copy_indirect) -def main [ - 1:address:number <- copy 2/unsafe - 2:number <- copy 34 - # This loads location 1 as an address and looks up *that* location. - 3:number <- copy 1:address:number/lookup -] -+mem: storing 34 in location 3 - -:(before "End Preprocess read_memory(x)") -canonize(x); - -//: similarly, write to addresses pointing at other locations using the -//: 'lookup' property -:(scenario store_indirect) -def main [ - 1:address:number <- copy 2/unsafe - 1:address:number/lookup <- copy 34 -] -+mem: storing 34 in location 2 - -:(before "End Preprocess write_memory(x)") -canonize(x); -if (x.value == 0) { - raise << "can't write to location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); - return; -} - -//: writes to address 0 always loudly fail -:(scenario store_to_0_fails) -% Hide_errors = true; -def main [ - 1:address:number <- copy 0 - 1:address:number/lookup <- copy 34 -] --mem: storing 34 in location 0 -+error: can't write to location 0 in '1:address:number/lookup <- copy 34' - -:(code) -void canonize(reagent& x) { - if (is_literal(x)) return; - // End canonize(x) Special-cases - while (has_property(x, "lookup")) - lookup_memory(x); -} - -void lookup_memory(reagent& x) { - if (!x.type || x.type->value != get(Type_ordinal, "address")) { - raise << maybe(current_recipe_name()) << "tried to /lookup " << x.original_string << " but it isn't an address\n" << end(); - return; - } - // compute value - if (x.value == 0) { - raise << maybe(current_recipe_name()) << "tried to /lookup 0\n" << end(); - return; - } - trace(9999, "mem") << "location " << x.value << " is " << no_scientific(get_or_insert(Memory, x.value)) << end(); - x.set_value(get_or_insert(Memory, x.value)); - drop_from_type(x, "address"); - // End Drop Address In lookup_memory(x) - drop_one_lookup(x); -} - -:(after "bool types_strictly_match(reagent to, reagent from)") - if (!canonize_type(to)) return false; - if (!canonize_type(from)) return false; - -:(after "bool is_mu_array(reagent r)") - if (!canonize_type(r)) return false; - -:(after "bool is_mu_address(reagent r)") - if (!canonize_type(r)) return false; - -:(after "bool is_mu_number(reagent r)") - if (!canonize_type(r)) return false; -:(after "bool is_mu_boolean(reagent r)") - if (!canonize_type(r)) return false; - -:(before "End Compute Call Ingredient") -canonize_type(ingredient); -:(before "End Preprocess NEXT_INGREDIENT product") -canonize_type(product); -:(before "End Check REPLY Copy(lhs, rhs) -canonize_type(lhs); -canonize_type(rhs); - -:(code) -bool canonize_type(reagent& r) { - while (has_property(r, "lookup")) { - if (!r.type || r.type->value != get(Type_ordinal, "address")) { - raise << "can't lookup non-address: " << to_string(r) << ": " << to_string(r.type) << '\n' << end(); - return false; - } - drop_from_type(r, "address"); - // End Drop Address In canonize_type(r) - drop_one_lookup(r); - } - return true; -} - -void drop_from_type(reagent& r, string expected_type) { - if (r.type->name != expected_type) { - raise << "can't drop2 " << expected_type << " from " << to_string(r) << '\n' << end(); - return; - } - type_tree* tmp = r.type; - r.type = tmp->right; - tmp->right = NULL; - delete tmp; -} - -void drop_one_lookup(reagent& r) { - for (vector >::iterator p = r.properties.begin(); p != r.properties.end(); ++p) { - if (p->first == "lookup") { - r.properties.erase(p); - return; - } - } - assert(false); -} - -//:: abbreviation for '/lookup': a prefix '*' - -:(scenario lookup_abbreviation) -def main [ - 1:address:number <- copy 2/unsafe - 2:number <- copy 34 - 3:number <- copy *1:address:number -] -+parse: ingredient: {1: ("address" "number"), "lookup": ()} -+mem: storing 34 in location 3 - -:(before "End Parsing reagent") -{ - while (!name.empty() && name.at(0) == '*') { - name.erase(0, 1); - properties.push_back(pair("lookup", NULL)); - } - if (name.empty()) - raise << "illegal name " << original_string << '\n' << end(); -} - -//:: helpers for debugging - -:(before "End Primitive Recipe Declarations") -_DUMP, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "$dump", _DUMP); -:(before "End Primitive Recipe Implementations") -case _DUMP: { - reagent after_canonize = current_instruction().ingredients.at(0); - canonize(after_canonize); - cerr << maybe(current_recipe_name()) << current_instruction().ingredients.at(0).name << ' ' << no_scientific(current_instruction().ingredients.at(0).value) << " => " << no_scientific(after_canonize.value) << " => " << no_scientific(get_or_insert(Memory, after_canonize.value)) << '\n'; - break; -} - -//: grab an address, and then dump its value at intervals -//: useful for tracking down memory corruption (writing to an out-of-bounds address) -:(before "End Globals") -int Bar = -1; -:(before "End Primitive Recipe Declarations") -_BAR, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "$bar", _BAR); -:(before "End Primitive Recipe Implementations") -case _BAR: { - if (current_instruction().ingredients.empty()) { - if (Bar != -1) cerr << Bar << ": " << no_scientific(get_or_insert(Memory, Bar)) << '\n'; - else cerr << '\n'; - } - else { - reagent tmp = current_instruction().ingredients.at(0); - canonize(tmp); - Bar = tmp.value; - } - break; -} diff --git a/030container.cc b/030container.cc new file mode 100644 index 00000000..ead9be70 --- /dev/null +++ b/030container.cc @@ -0,0 +1,779 @@ +//: Containers contain a fixed number of elements of different types. + +:(before "End Mu Types Initialization") +//: We'll use this container as a running example, with two number elements. +type_ordinal point = put(Type_ordinal, "point", Next_type_ordinal++); +get_or_insert(Type, point); // initialize +get(Type, point).kind = CONTAINER; +get(Type, point).name = "point"; +get(Type, point).elements.push_back(reagent("x:number")); +get(Type, point).elements.push_back(reagent("y:number")); + +//: Containers can be copied around with a single instruction just like +//: numbers, no matter how large they are. + +//: Tests in this layer often explicitly setup memory before reading it as a +//: container. Don't do this in general. I'm tagging exceptions with /raw to +//: avoid errors. +:(scenario copy_multiple_locations) +def main [ + 1:number <- copy 34 + 2:number <- copy 35 + 3:point <- copy 1:point/unsafe +] ++mem: storing 34 in location 3 ++mem: storing 35 in location 4 + +//: trying to copy to a differently-typed destination will fail +:(scenario copy_checks_size) +% Hide_errors = true; +def main [ + 2:point <- copy 1:number +] ++error: main: can't copy 1:number to 2:point; types don't match + +:(before "End Mu Types Initialization") +// A more complex container, containing another container as one of its +// elements. +type_ordinal point_number = put(Type_ordinal, "point-number", Next_type_ordinal++); +get_or_insert(Type, point_number); // initialize +get(Type, point_number).kind = CONTAINER; +get(Type, point_number).name = "point-number"; +get(Type, point_number).elements.push_back(reagent("xy:point")); +get(Type, point_number).elements.push_back(reagent("z:number")); + +:(scenario copy_handles_nested_container_elements) +def main [ + 12:number <- copy 34 + 13:number <- copy 35 + 14:number <- copy 36 + 15:point-number <- copy 12:point-number/unsafe +] ++mem: storing 36 in location 17 + +//: products of recipes can include containers +:(scenario reply_container) +def main [ + 3:point <- f 2 +] +def f [ + 12:number <- next-ingredient + 13:number <- copy 35 + return 12:point/raw +] ++run: result 0 is [2, 35] ++mem: storing 2 in location 3 ++mem: storing 35 in location 4 + +//: Containers can be checked for equality with a single instruction just like +//: numbers, no matter how large they are. + +:(scenario compare_multiple_locations) +def main [ + 1:number <- copy 34 # first + 2:number <- copy 35 + 3:number <- copy 36 + 4:number <- copy 34 # second + 5:number <- copy 35 + 6:number <- copy 36 + 7:boolean <- equal 1:point-number/raw, 4:point-number/unsafe +] ++mem: storing 1 in location 7 + +:(scenario compare_multiple_locations_2) +def main [ + 1:number <- copy 34 # first + 2:number <- copy 35 + 3:number <- copy 36 + 4:number <- copy 34 # second + 5:number <- copy 35 + 6:number <- copy 37 # different + 7:boolean <- equal 1:point-number/raw, 4:point-number/unsafe +] ++mem: storing 0 in location 7 + +:(before "End size_of(type) Cases") +if (type->value == -1) { + // error value, but we'll raise it elsewhere + return 1; +} +if (type->value == 0) { + assert(!type->left && !type->right); + return 1; +} +if (!contains_key(Type, type->value)) { + raise << "no such type " << type->value << '\n' << end(); + return 0; +} +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; + } + reagent tmp; + tmp.type = new type_tree(*type); + result += size_of(element_type(tmp, i)); + } + return result; +} + +:(scenario stash_container) +def main [ + 1:number <- copy 34 # first + 2:number <- copy 35 + 3:number <- copy 36 + stash [foo:], 1:point-number/raw +] ++app: foo: 34 35 36 + +//:: To access elements of a container, use 'get' +:(scenario get) +def main [ + 12:number <- copy 34 + 13:number <- copy 35 + 15:number <- get 12:point/raw, 1:offset # unsafe +] ++mem: storing 35 in location 15 + +:(before "End Primitive Recipe Declarations") +GET, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "get", GET); +:(before "End Primitive Recipe Checks") +case GET: { + if (SIZE(inst.ingredients) != 2) { + raise << maybe(get(Recipe, r).name) << "'get' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end(); + break; + } + reagent base = inst.ingredients.at(0); // new copy for every invocation + // Update GET base in Check + if (!base.type || !base.type->value || !contains_key(Type, base.type->value) || get(Type, base.type->value).kind != CONTAINER) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'get' should be a container, but got " << inst.ingredients.at(0).original_string << '\n' << end(); + break; + } + type_ordinal base_type = base.type->value; + reagent offset = inst.ingredients.at(1); + if (!is_literal(offset) || !is_mu_scalar(offset)) { + raise << maybe(get(Recipe, r).name) << "second ingredient of 'get' should have type 'offset', but got " << inst.ingredients.at(1).original_string << '\n' << end(); + break; + } + int offset_value = 0; + if (is_integer(offset.name)) // later layers permit non-integer offsets + offset_value = to_integer(offset.name); + else + offset_value = offset.value; + if (offset_value < 0 || offset_value >= SIZE(get(Type, base_type).elements)) { + raise << maybe(get(Recipe, r).name) << "invalid offset " << offset_value << " for " << get(Type, base_type).name << '\n' << end(); + break; + } + if (inst.products.empty()) break; + reagent product = inst.products.at(0); + // Update GET product in Check + const reagent element = element_type(base, offset_value); + if (!types_coercible(product, element)) { + raise << maybe(get(Recipe, r).name) << "'get " << base.original_string << ", " << offset.original_string << "' should write to " << names_to_string_without_quotes(element.type) << " but " << product.name << " has type " << names_to_string_without_quotes(product.type) << '\n' << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case GET: { + reagent base = current_instruction().ingredients.at(0); + // Update GET base in Run + int base_address = base.value; + if (base_address == 0) { + raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); + break; + } + 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, i)); + trace(9998, "run") << "address to copy is " << src << end(); + reagent element = element_type(base, offset); + element.set_value(src); + trace(9998, "run") << "its type is " << names_to_string(element.type) << end(); + // Read element + products.push_back(read_memory(element)); + break; +} + +:(code) +const reagent element_type(const reagent& base, int offset_value) { + assert(offset_value >= 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(info.kind == CONTAINER); + reagent element = info.elements.at(offset_value); + // End element_type Special-cases + return element; +} + +:(scenario get_handles_nested_container_elements) +def main [ + 12:number <- copy 34 + 13:number <- copy 35 + 14:number <- copy 36 + 15:number <- get 12:point-number/raw, 1:offset # unsafe +] ++mem: storing 36 in location 15 + +:(scenario get_out_of_bounds) +% Hide_errors = true; +def main [ + 12:number <- copy 34 + 13:number <- copy 35 + 14:number <- copy 36 + get 12:point-number/raw, 2:offset # point-number occupies 3 locations but has only 2 fields; out of bounds +] ++error: main: invalid offset 2 for point-number + +:(scenario get_out_of_bounds_2) +% Hide_errors = true; +def main [ + 12:number <- copy 34 + 13:number <- copy 35 + 14:number <- copy 36 + get 12:point-number/raw, -1:offset +] ++error: main: invalid offset -1 for point-number + +:(scenario get_product_type_mismatch) +% Hide_errors = true; +def main [ + 12:number <- copy 34 + 13:number <- copy 35 + 14:number <- copy 36 + 15:address:number <- get 12:point-number/raw, 1:offset +] ++error: main: 'get 12:point-number/raw, 1:offset' should write to number but 15 has type (address number) + +//: we might want to call 'get' without saving the results, say in a sandbox + +:(scenario get_without_product) +def main [ + 12:number <- copy 34 + 13:number <- copy 35 + get 12:point/raw, 1:offset # unsafe +] +# just don't die + +//:: To write to elements of containers, use 'put'. + +:(scenario put) +def main [ + 12:number <- copy 34 + 13:number <- copy 35 + $clear-trace + 12:point <- put 12:point, 1:offset, 36 +] ++mem: storing 36 in location 13 +-mem: storing 34 in location 12 + +:(before "End Primitive Recipe Declarations") +PUT, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "put", PUT); +:(before "End Primitive Recipe Checks") +case PUT: { + if (SIZE(inst.ingredients) != 3) { + raise << maybe(get(Recipe, r).name) << "'put' expects exactly 3 ingredients in '" << to_original_string(inst) << "'\n" << end(); + break; + } + reagent base = inst.ingredients.at(0); + // Update PUT base in Check + if (!base.type || !base.type->value || !contains_key(Type, base.type->value) || get(Type, base.type->value).kind != CONTAINER) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'put' should be a container, but got " << inst.ingredients.at(0).original_string << '\n' << end(); + break; + } + type_ordinal base_type = base.type->value; + reagent offset = inst.ingredients.at(1); + // Update PUT offset in Check + if (!is_literal(offset) || !is_mu_scalar(offset)) { + raise << maybe(get(Recipe, r).name) << "second ingredient of 'put' should have type 'offset', but got " << inst.ingredients.at(1).original_string << '\n' << end(); + break; + } + int offset_value = 0; + if (is_integer(offset.name)) { // later layers permit non-integer offsets + offset_value = to_integer(offset.name); + if (offset_value < 0 || offset_value >= SIZE(get(Type, base_type).elements)) { + raise << maybe(get(Recipe, r).name) << "invalid offset " << offset_value << " for " << get(Type, base_type).name << '\n' << end(); + break; + } + } + else { + offset_value = offset.value; + } + reagent& value = inst.ingredients.at(2); + reagent element = element_type(base, offset_value); + if (!types_coercible(element, value)) { + raise << maybe(get(Recipe, r).name) << "'put " << base.original_string << ", " << offset.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; + } + break; +} +:(before "End Primitive Recipe Implementations") +case PUT: { + reagent base = current_instruction().ingredients.at(0); + // Update PUT base in Run + int base_address = base.value; + if (base_address == 0) { + raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); + break; + } + 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 address = base_address; + for (int i = 0; i < offset; ++i) + address += size_of(element_type(base, 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 + for (int i = 0; i < SIZE(ingredients.at(2)); ++i) { + trace(9999, "mem") << "storing " << no_scientific(ingredients.at(2).at(i)) << " in location " << address+i << end(); + put(Memory, address+i, ingredients.at(2).at(i)); + } + goto finish_instruction; +} + +//:: Allow containers to be defined in mu code. + +:(scenarios load) +:(scenario container) +container foo [ + x:number + y:number +] ++parse: --- defining container foo ++parse: element: {x: "number"} ++parse: element: {y: "number"} + +:(scenario container_use_before_definition) +container foo [ + x:number + y:bar +] + +container bar [ + x:number + y:number +] ++parse: --- defining container foo ++parse: type number: 1000 ++parse: element: {x: "number"} +# todo: brittle +# type bar is unknown at this point, but we assign it a number ++parse: element: {y: "bar"} +# later type bar geon ++parse: --- defining container bar ++parse: type number: 1001 ++parse: element: {x: "number"} ++parse: element: {y: "number"} + +:(before "End Command Handlers") +else if (command == "container") { + insert_container(command, CONTAINER, in); +} + +:(code) +void insert_container(const string& command, kind_of_type kind, istream& in) { + skip_whitespace_but_not_newline(in); + string name = next_word(in); + // End container Name Refinements + trace(9991, "parse") << "--- defining " << command << ' ' << name << end(); + if (!contains_key(Type_ordinal, name) + || get(Type_ordinal, name) == 0) { + put(Type_ordinal, name, Next_type_ordinal++); + } + trace(9999, "parse") << "type number: " << get(Type_ordinal, name) << end(); + skip_bracket(in, "'container' must begin with '['"); + type_info& info = get_or_insert(Type, get(Type_ordinal, name)); + info.name = name; + info.kind = kind; + while (has_data(in)) { + skip_whitespace_and_comments(in); + string element = next_word(in); + if (element == "]") break; + info.elements.push_back(reagent(element)); + replace_unknown_types_with_unique_ordinals(info.elements.back().type, info); + trace(9993, "parse") << " element: " << to_string(info.elements.back()) << end(); + // End Load Container Element Definition + } +} + +void replace_unknown_types_with_unique_ordinals(type_tree* type, const type_info& info) { + if (!type) return; + if (!type->name.empty()) { + if (contains_key(Type_ordinal, type->name)) { + type->value = get(Type_ordinal, type->name); + } + else if (is_integer(type->name)) { // sometimes types will contain non-type tags, like numbers for the size of an array + type->value = 0; + } + // End insert_container Special-cases + else if (type->name != "->") { // used in recipe types + put(Type_ordinal, type->name, Next_type_ordinal++); + type->value = get(Type_ordinal, type->name); + } + } + replace_unknown_types_with_unique_ordinals(type->left, info); + replace_unknown_types_with_unique_ordinals(type->right, info); +} + +void skip_bracket(istream& in, string message) { + skip_whitespace_and_comments(in); + if (in.get() != '[') + raise << message << '\n' << end(); +} + +:(scenarios run) +:(scenario container_define_twice) +container foo [ + x:number +] + +container foo [ + y:number +] + +def main [ + 1:number <- copy 34 + 2:number <- copy 35 + 3:number <- get 1:foo, 0:offset + 4:number <- get 1:foo, 1:offset +] ++mem: storing 34 in location 3 ++mem: storing 35 in location 4 + +//: ensure scenarios are consistent by always starting them at the same type +//: number. +:(before "End Setup") //: for tests +Next_type_ordinal = 1000; +:(before "End Test Run Initialization") +assert(Next_type_ordinal < 1000); + +//:: Allow container definitions anywhere in the codebase, but complain if you +//:: can't find a definition at the end. + +:(scenario run_complains_on_unknown_types) +% Hide_errors = true; +def main [ + # integer is not a type + 1:integer <- copy 0 +] ++error: main: unknown type integer in '1:integer <- copy 0' + +:(scenario run_allows_type_definition_after_use) +def main [ + 1:bar <- copy 0/unsafe +] + +container bar [ + x:number +] +$error: 0 + +:(after "Begin Instruction Modifying Transforms") +// Begin Type Modifying Transforms +Transform.push_back(check_or_set_invalid_types); // idempotent +// End Type Modifying Transforms + +:(code) +void check_or_set_invalid_types(const recipe_ordinal r) { + recipe& caller = get(Recipe, r); + trace(9991, "transform") << "--- check for invalid types in recipe " << caller.name << end(); + for (int index = 0; index < SIZE(caller.steps); ++index) { + instruction& inst = caller.steps.at(index); + for (int i = 0; i < SIZE(inst.ingredients); ++i) + check_or_set_invalid_types(inst.ingredients.at(i).type, maybe(caller.name), "'"+to_original_string(inst)+"'"); + for (int i = 0; i < SIZE(inst.products); ++i) + check_or_set_invalid_types(inst.products.at(i).type, maybe(caller.name), "'"+to_original_string(inst)+"'"); + } + // End check_or_set_invalid_types +} + +void check_or_set_invalid_types(type_tree* type, const string& block, const string& name) { + if (!type) return; // will throw a more precise error elsewhere + // End Container Type Checks + if (type->value == 0) return; + if (!contains_key(Type, type->value)) { + assert(!type->name.empty()); + if (contains_key(Type_ordinal, type->name)) + type->value = get(Type_ordinal, type->name); + else + raise << block << "unknown type " << type->name << " in " << name << '\n' << end(); + } + check_or_set_invalid_types(type->left, block, name); + check_or_set_invalid_types(type->right, block, name); +} + +:(scenario container_unknown_field) +% Hide_errors = true; +container foo [ + x:number + y:bar +] ++error: foo: unknown type in y + +:(scenario read_container_with_bracket_in_comment) +container foo [ + x:number + # ']' in comment + y:number +] ++parse: --- defining container foo ++parse: element: {x: "number"} ++parse: element: {y: "number"} + +:(before "End transform_all") +check_container_field_types(); + +:(code) +void check_container_field_types() { + for (map::iterator p = Type.begin(); p != Type.end(); ++p) { + const type_info& info = p->second; + // Check Container Field Types(info) + for (int i = 0; i < SIZE(info.elements); ++i) + check_invalid_types(info.elements.at(i).type, maybe(info.name), info.elements.at(i).name); + } +} + +void check_invalid_types(const type_tree* type, const string& block, const string& name) { + if (!type) return; // will throw a more precise error elsewhere + if (type->value == 0) { + assert(!type->left && !type->right); + return; + } + if (!contains_key(Type, type->value)) + raise << block << "unknown type in " << name << '\n' << end(); + check_invalid_types(type->left, block, name); + check_invalid_types(type->right, block, name); +} + +//:: Construct types out of their constituent fields. + +:(scenario merge) +container foo [ + x:number + y:number +] + +def main [ + 1:foo <- merge 3, 4 +] ++mem: storing 3 in location 1 ++mem: storing 4 in location 2 + +:(before "End Primitive Recipe Declarations") +MERGE, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "merge", MERGE); +:(before "End Primitive Recipe Checks") +case MERGE: { + // type-checking in a separate transform below + break; +} +:(before "End Primitive Recipe Implementations") +case MERGE: { + products.resize(1); + for (int i = 0; i < SIZE(ingredients); ++i) + for (int j = 0; j < SIZE(ingredients.at(i)); ++j) + products.at(0).push_back(ingredients.at(i).at(j)); + break; +} + +//: type-check 'merge' to avoid interpreting numbers as addresses + +:(scenario merge_check) +def main [ + 1:point <- merge 3, 4 +] +$error: 0 + +:(scenario merge_check_missing_element) +% Hide_errors = true; +def main [ + 1:point <- merge 3 +] ++error: main: too few ingredients in '1:point <- merge 3' + +:(scenario merge_check_extra_element) +% Hide_errors = true; +def main [ + 1:point <- merge 3, 4, 5 +] ++error: main: too many ingredients in '1:point <- merge 3, 4, 5' + +//: We want to avoid causing memory corruption, but other than that we want to +//: be flexible in how we construct containers of containers. It should be +//: equally easy to define a container out of primitives or intermediate +//: container fields. + +:(scenario merge_check_recursive_containers) +def main [ + 1:point <- merge 3, 4 + 1:point-number <- merge 1:point, 5 +] +$error: 0 + +:(scenario merge_check_recursive_containers_2) +% Hide_errors = true; +def main [ + 1:point <- merge 3, 4 + 2:point-number <- merge 1:point +] ++error: main: too few ingredients in '2:point-number <- merge 1:point' + +:(scenario merge_check_recursive_containers_3) +def main [ + 1:point-number <- merge 3, 4, 5 +] +$error: 0 + +:(scenario merge_check_recursive_containers_4) +% Hide_errors = true; +def main [ + 1:point-number <- merge 3, 4 +] ++error: main: too few ingredients in '1:point-number <- merge 3, 4' + +:(scenario merge_check_reflexive) +% Hide_errors = true; +def main [ + 1:point <- merge 3, 4 + 2:point <- merge 1:point +] +$error: 0 + +//: Since a container can be merged in several ways, we need to be able to +//: backtrack through different possibilities. Later we'll allow creating +//: exclusive containers which contain just one of rather than all of their +//: elements. That will also require backtracking capabilities. Here's the +//: state we need to maintain for backtracking: + +:(before "End Types") +struct merge_check_point { + reagent container; + int container_element_index; + merge_check_point(const reagent& c, int i) :container(c), container_element_index(i) {} +}; + +struct merge_check_state { + stack data; +}; + +:(before "End Checks") +Transform.push_back(check_merge_calls); +:(code) +void check_merge_calls(const recipe_ordinal r) { + const recipe& caller = get(Recipe, r); + trace(9991, "transform") << "--- type-check merge instructions in recipe " << caller.name << end(); + for (int i = 0; i < SIZE(caller.steps); ++i) { + const instruction& inst = caller.steps.at(i); + if (inst.name != "merge") continue; + if (SIZE(inst.products) != 1) { + raise << maybe(caller.name) << "'merge' should yield a single product in '" << to_original_string(inst) << "'\n" << end(); + continue; + } + reagent product = inst.products.at(0); + // Update product While Type-checking Merge + type_ordinal product_type = product.type->value; + if (product_type == 0 || !contains_key(Type, product_type)) { + raise << maybe(caller.name) << "'merge' should yield a container in '" << to_original_string(inst) << "'\n" << end(); + continue; + } + const type_info& info = get(Type, product_type); + if (info.kind != CONTAINER && info.kind != EXCLUSIVE_CONTAINER) { + raise << maybe(caller.name) << "'merge' should yield a container in '" << to_original_string(inst) << "'\n" << end(); + continue; + } + check_merge_call(inst.ingredients, product, caller, inst); + } +} + +void check_merge_call(const vector& ingredients, const reagent& product, const recipe& caller, const instruction& inst) { + int ingredient_index = 0; + merge_check_state state; + state.data.push(merge_check_point(product, 0)); + while (true) { + assert(!state.data.empty()); + trace(9999, "transform") << ingredient_index << " vs " << SIZE(ingredients) << end(); + if (ingredient_index >= SIZE(ingredients)) { + raise << maybe(caller.name) << "too few ingredients in '" << to_original_string(inst) << "'\n" << end(); + return; + } + reagent& container = state.data.top().container; + type_info& container_info = get(Type, container.type->value); + switch (container_info.kind) { + case CONTAINER: { + // degenerate case: merge with the same type always succeeds + if (state.data.top().container_element_index == 0 && types_coercible(container, inst.ingredients.at(ingredient_index))) + return; + reagent expected_ingredient = element_type(container, state.data.top().container_element_index); + trace(9999, "transform") << "checking container " << to_string(container) << " || " << to_string(expected_ingredient) << " vs ingredient " << ingredient_index << end(); + // if the current element is the ingredient we expect, move on to the next element/ingredient + if (types_coercible(expected_ingredient, ingredients.at(ingredient_index))) { + ++ingredient_index; + ++state.data.top().container_element_index; + while (state.data.top().container_element_index >= SIZE(get(Type, state.data.top().container.type->value).elements)) { + state.data.pop(); + if (state.data.empty()) { + if (ingredient_index < SIZE(ingredients)) + raise << maybe(caller.name) << "too many ingredients in '" << to_original_string(inst) << "'\n" << end(); + return; + } + ++state.data.top().container_element_index; + } + } + // if not, maybe it's a field of the current element + else { + // no change to ingredient_index + state.data.push(merge_check_point(expected_ingredient, 0)); + } + break; + } + // End valid_merge Cases + default: { + if (!types_coercible(container, ingredients.at(ingredient_index))) { + raise << maybe(caller.name) << "incorrect type of ingredient " << ingredient_index << " in '" << to_original_string(inst) << "'\n" << end(); + raise << " (expected " << debug_string(container) << ")\n" << end(); + raise << " (got " << debug_string(ingredients.at(ingredient_index)) << ")\n" << end(); + return; + } + ++ingredient_index; + // ++state.data.top().container_element_index; // unnecessary, but wouldn't do any harm + do { + state.data.pop(); + if (state.data.empty()) { + if (ingredient_index < SIZE(ingredients)) + raise << maybe(caller.name) << "too many ingredients in '" << to_original_string(inst) << "'\n" << end(); + return; + } + ++state.data.top().container_element_index; + } while (state.data.top().container_element_index >= SIZE(get(Type, state.data.top().container.type->value).elements)); + } + } + } + // never gets here + assert(false); +} + +:(scenario merge_check_product) +% Hide_errors = true; +def main [ + 1:number <- merge 3 +] ++error: main: 'merge' should yield a container in '1:number <- merge 3' + +:(before "End Includes") +#include +using std::stack; diff --git a/031array.cc b/031array.cc new file mode 100644 index 00000000..ac1cc848 --- /dev/null +++ b/031array.cc @@ -0,0 +1,448 @@ +//: Arrays contain a variable number of elements of the same type. Their value +//: starts with the length of the array. +//: +//: You can create arrays of containers, but containers can only contain +//: elements of a fixed size, so you can't create containers containing arrays. +//: Create containers containing addresses to arrays instead. + +//: You can create arrays using 'create-array'. +:(scenario create_array) +def main [ + # create an array occupying locations 1 (for the size) and 2-4 (for the elements) + 1:array:number:3 <- create-array +] ++run: creating array of size 4 + +:(before "End Primitive Recipe Declarations") +CREATE_ARRAY, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "create-array", CREATE_ARRAY); +:(before "End Primitive Recipe Checks") +case CREATE_ARRAY: { + if (inst.products.empty()) { + raise << maybe(get(Recipe, r).name) << "'create-array' needs one product and no ingredients but got '" << to_original_string(inst) << '\n' << end(); + break; + } + reagent product = inst.products.at(0); + // Update CREATE_ARRAY product in Check + if (!is_mu_array(product)) { + raise << maybe(get(Recipe, r).name) << "'create-array' cannot create non-array " << product.original_string << '\n' << end(); + break; + } + if (!product.type->right) { + raise << maybe(get(Recipe, r).name) << "create array of what? " << to_original_string(inst) << '\n' << end(); + break; + } + // 'create-array' will need to check properties rather than types + if (!product.type->right->right) { + raise << maybe(get(Recipe, r).name) << "create array of what size? " << to_original_string(inst) << '\n' << end(); + break; + } + if (!is_integer(product.type->right->right->name)) { + raise << maybe(get(Recipe, r).name) << "'create-array' product should specify size of array after its element type, but got " << product.type->right->right->name << '\n' << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case CREATE_ARRAY: { + reagent product = current_instruction().products.at(0); + // Update CREATE_ARRAY product in Run + int base_address = product.value; + int array_length = to_integer(product.type->right->right->name); + // initialize array size, so that size_of will work + trace(9999, "mem") << "storing " << array_length << " in location " << base_address << end(); + put(Memory, base_address, array_length); // in array elements + int size = size_of(product); // in locations + trace(9998, "run") << "creating array of size " << size << '\n' << end(); + // initialize array + for (int i = 1; i <= size_of(product); ++i) { + put(Memory, base_address+i, 0); + } + // no need to update product + goto finish_instruction; +} + +:(scenario copy_array) +# Arrays can be copied around with a single instruction just like numbers, +# no matter how large they are. +# You don't need to pass the size around, since each array variable stores its +# size in memory at run-time. We'll call a variable with an explicit size a +# 'static' array, and one without a 'dynamic' array since it can contain +# arrays of many different sizes. +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:array:number <- copy 1:array:number:3 +] ++mem: storing 3 in location 5 ++mem: storing 14 in location 6 ++mem: storing 15 in location 7 ++mem: storing 16 in location 8 + +:(scenario stash_array) +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + stash [foo:], 1:array:number:3 +] ++app: foo: 3 14 15 16 + +:(before "End size_of(reagent) Cases") +if (r.type && r.type->value == get(Type_ordinal, "array")) { + if (!r.type->right) { + 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)); +} + +//: disable the size mismatch check for arrays since the destination array +//: need not be initialized +:(before "End size_mismatch(x) Cases") +if (x.type && x.type->value == get(Type_ordinal, "array")) return false; + +//: arrays are disallowed inside containers unless their length is fixed in +//: advance + +:(scenario container_contains_array) +container foo [ + x:array:number:3 +] +$error: 0 + +:(scenario container_disallows_dynamic_array_element) +% Hide_errors = true; +container foo [ + x:array:number +] ++error: container 'foo' cannot determine size of element x + +:(before "End Load Container Element Definition") +{ + const type_tree* type = info.elements.back().type; + if (type->name == "array") { + if (!type->right) { + raise << "container '" << name << "' doesn't specify type of array elements for " << info.elements.back().name << '\n' << end(); + continue; + } + if (!type->right->right) { // array has no length + raise << "container '" << name << "' cannot determine size of element " << info.elements.back().name << '\n' << end(); + continue; + } + } +} + +//:: To access elements of an array, use 'index' + +:(scenario index) +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:number <- index 1:array:number:3, 0 +] ++mem: storing 14 in location 5 + +:(scenario index_direct_offset) +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:number <- copy 0 + 6:number <- index 1:array:number, 5:number +] ++mem: storing 14 in location 6 + +:(before "End Primitive Recipe Declarations") +INDEX, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "index", INDEX); +:(before "End Primitive Recipe Checks") +case INDEX: { + if (SIZE(inst.ingredients) != 2) { + raise << maybe(get(Recipe, r).name) << "'index' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end(); + break; + } + reagent base = inst.ingredients.at(0); + // Update INDEX base in Check + if (!is_mu_array(base)) { + raise << maybe(get(Recipe, r).name) << "'index' on a non-array " << base.original_string << '\n' << end(); + break; + } + reagent index = inst.ingredients.at(1); + // Update INDEX index in Check + if (!is_mu_number(index)) { + raise << maybe(get(Recipe, r).name) << "second ingredient of 'index' should be a number, but got " << index.original_string << '\n' << end(); + break; + } + if (inst.products.empty()) break; + reagent product = inst.products.at(0); + // Update INDEX product in Check + reagent element; + element.type = new type_tree(*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; + } + break; +} +:(before "End Primitive Recipe Implementations") +case INDEX: { + reagent base = current_instruction().ingredients.at(0); + // Update INDEX base in Run + int base_address = base.value; + trace(9998, "run") << "base address is " << base_address << end(); + if (base_address == 0) { + raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); + break; + } + reagent index = current_instruction().ingredients.at(1); + // Update INDEX index in Run + vector 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; + } + 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); + // Read element + products.push_back(read_memory(element)); + break; +} + +:(code) +type_tree* array_element(const type_tree* type) { + if (type->right->left) { + assert(!type->right->left->left); + return type->right->left; + } + return type->right; +} + +int array_length(const reagent& x) { + if (x.type->right->right) { + return to_integer(x.type->right->right->name); + } + // this should never happen at transform time + // x should already be canonized. + return get_or_insert(Memory, x.value); +} + +:(scenario index_out_of_bounds) +% Hide_errors = true; +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:number <- copy 14 + 6:number <- copy 15 + 7:number <- copy 16 + index 1:array:number:3, 4 # less than size of array in locations, but larger than its length in elements +] ++error: main: invalid index 4 + +:(scenario index_out_of_bounds_2) +% Hide_errors = true; +def main [ + 1:array:point:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:number <- copy 14 + 6:number <- copy 15 + 7:number <- copy 16 + index 1:array:point, -1 +] ++error: main: invalid index -1 + +:(scenario index_product_type_mismatch) +% Hide_errors = true; +def main [ + 1:array:point:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:number <- copy 14 + 6:number <- copy 15 + 7:number <- copy 16 + 9:number <- index 1:array:point, 0 +] ++error: main: 'index' on 1:array:point can't be saved in 9:number; type should be point + +//: we might want to call 'index' without saving the results, say in a sandbox + +:(scenario index_without_product) +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + index 1:array:number:3, 0 +] +# just don't die + +//:: To write to elements of arrays, use 'put'. + +:(scenario put_index) +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 1:array:number <- put-index 1:array:number, 1, 34 +] ++mem: storing 34 in location 3 + +:(before "End Primitive Recipe Declarations") +PUT_INDEX, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "put-index", PUT_INDEX); +:(before "End Primitive Recipe Checks") +case PUT_INDEX: { + if (SIZE(inst.ingredients) != 3) { + raise << maybe(get(Recipe, r).name) << "'put-index' expects exactly 3 ingredients in '" << to_original_string(inst) << "'\n" << end(); + break; + } + reagent base = inst.ingredients.at(0); + // Update PUT_INDEX base in Check + if (!is_mu_array(base)) { + raise << maybe(get(Recipe, r).name) << "'put-index' on a non-array " << base.original_string << '\n' << end(); + break; + } + reagent index = inst.ingredients.at(1); + // Update PUT_INDEX index in Check + if (!is_mu_number(index)) { + raise << maybe(get(Recipe, r).name) << "second ingredient of 'put-index' should have type 'number', but got " << inst.ingredients.at(1).original_string << '\n' << end(); + break; + } + reagent value = inst.ingredients.at(2); + // Update PUT_INDEX value in Check + reagent element; + element.type = new type_tree(*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; + } + break; +} +:(before "End Primitive Recipe Implementations") +case PUT_INDEX: { + reagent base = current_instruction().ingredients.at(0); + // Update PUT_INDEX base in Run + int base_address = base.value; + if (base_address == 0) { + raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); + break; + } + reagent index = current_instruction().ingredients.at(1); + // Update PUT_INDEX index in Run + vector 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; + } + int address = base_address + 1 + index_val.at(0)*size_of(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 + vector value = read_memory(current_instruction().ingredients.at(2)); + for (int i = 0; i < SIZE(value); ++i) { + trace(9999, "mem") << "storing " << no_scientific(value.at(i)) << " in location " << address+i << end(); + put(Memory, address+i, value.at(i)); + } + goto finish_instruction; +} + +:(scenario put_index_out_of_bounds) +% Hide_errors = true; +def main [ + 1:array:point:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:number <- copy 14 + 6:number <- copy 15 + 7:number <- copy 16 + 8:point <- merge 34, 35 + 1:array:point <- put-index 1:array:point, 4, 8:point # '4' is less than size of array in locations, but larger than its length in elements +] ++error: main: invalid index 4 + +:(scenario put_index_out_of_bounds_2) +% Hide_errors = true; +def main [ + 1:array:point:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:number <- copy 14 + 6:number <- copy 15 + 7:number <- copy 16 + 8:point <- merge 34, 35 + 1:array:point <- put-index 1:array:point, -1, 8:point +] ++error: main: invalid index -1 + +//:: compute the length of an array + +:(scenario array_length) +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:number <- length 1:array:number:3 +] ++mem: storing 3 in location 5 + +:(before "End Primitive Recipe Declarations") +LENGTH, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "length", LENGTH); +:(before "End Primitive Recipe Checks") +case LENGTH: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'length' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end(); + break; + } + reagent array = inst.ingredients.at(0); + // Update LENGTH array in Check + if (!is_mu_array(array)) { + raise << "tried to calculate length of non-array " << array.original_string << '\n' << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case LENGTH: { + reagent array = current_instruction().ingredients.at(0); + // Update LENGTH array in Run + if (array.value == 0) { + raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); + break; + } + products.resize(1); + products.at(0).push_back(get_or_insert(Memory, array.value)); + break; +} + +//: optimization: none of the instructions in this layer use 'ingredients' so +//: stop copying potentially huge arrays into it. +:(before "End should_copy_ingredients Special-cases") +recipe_ordinal r = current_instruction().operation; +if (r == CREATE_ARRAY || r == INDEX || r == PUT_INDEX || r == LENGTH) + return false; diff --git a/031container.cc b/031container.cc deleted file mode 100644 index 963afb68..00000000 --- a/031container.cc +++ /dev/null @@ -1,807 +0,0 @@ -//: Containers contain a fixed number of elements of different types. - -:(before "End Mu Types Initialization") -//: We'll use this container as a running example, with two number elements. -type_ordinal point = put(Type_ordinal, "point", Next_type_ordinal++); -get_or_insert(Type, point); // initialize -get(Type, point).kind = CONTAINER; -get(Type, point).name = "point"; -get(Type, point).elements.push_back(reagent("x:number")); -get(Type, point).elements.push_back(reagent("y:number")); - -//: Containers can be copied around with a single instruction just like -//: numbers, no matter how large they are. - -//: Tests in this layer often explicitly setup memory before reading it as a -//: container. Don't do this in general. I'm tagging exceptions with /raw to -//: avoid errors. -:(scenario copy_multiple_locations) -def main [ - 1:number <- copy 34 - 2:number <- copy 35 - 3:point <- copy 1:point/unsafe -] -+mem: storing 34 in location 3 -+mem: storing 35 in location 4 - -//: trying to copy to a differently-typed destination will fail -:(scenario copy_checks_size) -% Hide_errors = true; -def main [ - 2:point <- copy 1:number -] -+error: main: can't copy 1:number to 2:point; types don't match - -:(before "End Mu Types Initialization") -// A more complex container, containing another container as one of its -// elements. -type_ordinal point_number = put(Type_ordinal, "point-number", Next_type_ordinal++); -get_or_insert(Type, point_number); // initialize -get(Type, point_number).kind = CONTAINER; -get(Type, point_number).name = "point-number"; -get(Type, point_number).elements.push_back(reagent("xy:point")); -get(Type, point_number).elements.push_back(reagent("z:number")); - -:(scenario copy_handles_nested_container_elements) -def main [ - 12:number <- copy 34 - 13:number <- copy 35 - 14:number <- copy 36 - 15:point-number <- copy 12:point-number/unsafe -] -+mem: storing 36 in location 17 - -//: Products of recipes can include containers and exclusive containers, addresses and arrays. -:(scenario reply_container) -def main [ - 3:point <- f 2 -] -def f [ - 12:number <- next-ingredient - 13:number <- copy 35 - return 12:point/raw -] -+run: result 0 is [2, 35] -+mem: storing 2 in location 3 -+mem: storing 35 in location 4 - -//: Containers can be checked for equality with a single instruction just like -//: numbers, no matter how large they are. - -:(scenario compare_multiple_locations) -def main [ - 1:number <- copy 34 # first - 2:number <- copy 35 - 3:number <- copy 36 - 4:number <- copy 34 # second - 5:number <- copy 35 - 6:number <- copy 36 - 7:boolean <- equal 1:point-number/raw, 4:point-number/unsafe -] -+mem: storing 1 in location 7 - -:(scenario compare_multiple_locations_2) -def main [ - 1:number <- copy 34 # first - 2:number <- copy 35 - 3:number <- copy 36 - 4:number <- copy 34 # second - 5:number <- copy 35 - 6:number <- copy 37 # different - 7:boolean <- equal 1:point-number/raw, 4:point-number/unsafe -] -+mem: storing 0 in location 7 - -:(before "End size_of(type) Cases") -if (type->value == -1) { - // error value, but we'll raise it elsewhere - return 1; -} -if (type->value == 0) { - assert(!type->left && !type->right); - return 1; -} -if (!contains_key(Type, type->value)) { - raise << "no such type " << type->value << '\n' << end(); - return 0; -} -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; - } - reagent tmp; - tmp.type = new type_tree(*type); - result += size_of(element_type(tmp, i)); - } - return result; -} - -:(scenario stash_container) -def main [ - 1:number <- copy 34 # first - 2:number <- copy 35 - 3:number <- copy 36 - stash [foo:], 1:point-number/raw -] -+app: foo: 34 35 36 - -//:: To access elements of a container, use 'get' -:(scenario get) -def main [ - 12:number <- copy 34 - 13:number <- copy 35 - 15:number <- get 12:point/raw, 1:offset # unsafe -] -+mem: storing 35 in location 15 - -:(before "End Primitive Recipe Declarations") -GET, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "get", GET); -:(before "End Primitive Recipe Checks") -case GET: { - if (SIZE(inst.ingredients) != 2) { - raise << maybe(get(Recipe, r).name) << "'get' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end(); - break; - } - reagent base = inst.ingredients.at(0); // new copy for every invocation - if (!canonize_type(base)) break; - if (!base.type || !base.type->value || !contains_key(Type, base.type->value) || get(Type, base.type->value).kind != CONTAINER) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'get' should be a container, but got " << inst.ingredients.at(0).original_string << '\n' << end(); - break; - } - type_ordinal base_type = base.type->value; - reagent offset = inst.ingredients.at(1); - if (!is_literal(offset) || !is_mu_scalar(offset)) { - raise << maybe(get(Recipe, r).name) << "second ingredient of 'get' should have type 'offset', but got " << inst.ingredients.at(1).original_string << '\n' << end(); - break; - } - int offset_value = 0; - if (is_integer(offset.name)) // later layers permit non-integer offsets - offset_value = to_integer(offset.name); - else - offset_value = offset.value; - if (offset_value < 0 || offset_value >= SIZE(get(Type, base_type).elements)) { - raise << maybe(get(Recipe, r).name) << "invalid offset " << offset_value << " for " << get(Type, base_type).name << '\n' << end(); - break; - } - if (inst.products.empty()) break; - reagent product = inst.products.at(0); - if (!canonize_type(product)) break; - const reagent element = element_type(base, offset_value); - if (!types_coercible(product, element)) { - raise << maybe(get(Recipe, r).name) << "'get " << base.original_string << ", " << offset.original_string << "' should write to " << names_to_string_without_quotes(element.type) << " but " << product.name << " has type " << names_to_string_without_quotes(product.type) << '\n' << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case GET: { - reagent base = current_instruction().ingredients.at(0); - canonize(base); - int base_address = base.value; - if (base_address == 0) { - raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); - break; - } - 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, i)); - trace(9998, "run") << "address to copy is " << src << end(); - reagent element = element_type(base, offset); - element.set_value(src); - trace(9998, "run") << "its type is " << names_to_string(element.type) << end(); - // Read element - products.push_back(read_memory(element)); - break; -} - -:(code) -const reagent element_type(const reagent& canonized_base, int offset_value) { - assert(offset_value >= 0); - assert(contains_key(Type, canonized_base.type->value)); - assert(!get(Type, canonized_base.type->value).name.empty()); - const type_info& info = get(Type, canonized_base.type->value); - assert(info.kind == CONTAINER); - reagent element = info.elements.at(offset_value); - // End element_type Special-cases - return element; -} - -:(scenario get_handles_nested_container_elements) -def main [ - 12:number <- copy 34 - 13:number <- copy 35 - 14:number <- copy 36 - 15:number <- get 12:point-number/raw, 1:offset # unsafe -] -+mem: storing 36 in location 15 - -:(scenario get_out_of_bounds) -% Hide_errors = true; -def main [ - 12:number <- copy 34 - 13:number <- copy 35 - 14:number <- copy 36 - get 12:point-number/raw, 2:offset # point-number occupies 3 locations but has only 2 fields; out of bounds -] -+error: main: invalid offset 2 for point-number - -:(scenario get_out_of_bounds_2) -% Hide_errors = true; -def main [ - 12:number <- copy 34 - 13:number <- copy 35 - 14:number <- copy 36 - get 12:point-number/raw, -1:offset -] -+error: main: invalid offset -1 for point-number - -:(scenario get_product_type_mismatch) -% Hide_errors = true; -def main [ - 12:number <- copy 34 - 13:number <- copy 35 - 14:number <- copy 36 - 15:address:number <- get 12:point-number/raw, 1:offset -] -+error: main: 'get 12:point-number/raw, 1:offset' should write to number but 15 has type (address number) - -//: 'get' can read from container address -:(scenario get_indirect) -def main [ - 1:number <- copy 2 - 2:number <- copy 34 - 3:number <- copy 35 - 4:number <- get 1:address:point/lookup, 0:offset -] -+mem: storing 34 in location 4 - -:(scenario get_indirect2) -def main [ - 1:number <- copy 2 - 2:number <- copy 34 - 3:number <- copy 35 - 4:address:number <- copy 5/unsafe - *4:address:number <- get 1:address:point/lookup, 0:offset -] -+mem: storing 34 in location 5 - -:(scenario include_nonlookup_properties) -def main [ - 1:number <- copy 2 - 2:number <- copy 34 - 3:number <- copy 35 - 4:number <- get 1:address:point/lookup/foo, 0:offset -] -+mem: storing 34 in location 4 - -//: we might want to call 'get' without saving the results, say in a sandbox - -:(scenario get_without_product) -def main [ - 12:number <- copy 34 - 13:number <- copy 35 - get 12:point/raw, 1:offset # unsafe -] -# just don't die - -//:: To write to elements of containers, use 'put'. - -:(scenario put) -def main [ - 12:number <- copy 34 - 13:number <- copy 35 - $clear-trace - 12:point <- put 12:point, 1:offset, 36 -] -+mem: storing 36 in location 13 --mem: storing 34 in location 12 - -:(before "End Primitive Recipe Declarations") -PUT, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "put", PUT); -:(before "End Primitive Recipe Checks") -case PUT: { - if (SIZE(inst.ingredients) != 3) { - raise << maybe(get(Recipe, r).name) << "'put' expects exactly 3 ingredients in '" << to_original_string(inst) << "'\n" << end(); - break; - } - reagent base = inst.ingredients.at(0); - if (!canonize_type(base)) break; - if (!base.type || !base.type->value || !contains_key(Type, base.type->value) || get(Type, base.type->value).kind != CONTAINER) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'put' should be a container, but got " << inst.ingredients.at(0).original_string << '\n' << end(); - break; - } - type_ordinal base_type = base.type->value; - reagent offset = inst.ingredients.at(1); - if (!is_literal(offset) || !is_mu_scalar(offset)) { - raise << maybe(get(Recipe, r).name) << "second ingredient of 'put' should have type 'offset', but got " << inst.ingredients.at(1).original_string << '\n' << end(); - break; - } - int offset_value = 0; - if (is_integer(offset.name)) { // later layers permit non-integer offsets - offset_value = to_integer(offset.name); - if (offset_value < 0 || offset_value >= SIZE(get(Type, base_type).elements)) { - raise << maybe(get(Recipe, r).name) << "invalid offset " << offset_value << " for " << get(Type, base_type).name << '\n' << end(); - break; - } - } - else { - offset_value = offset.value; - } - reagent& value = inst.ingredients.at(2); - reagent element = element_type(base, offset_value); - if (!types_coercible(element, value)) { - raise << maybe(get(Recipe, r).name) << "'put " << base.original_string << ", " << offset.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; - } - break; -} -:(before "End Primitive Recipe Implementations") -case PUT: { - reagent base = current_instruction().ingredients.at(0); - canonize(base); - int base_address = base.value; - if (base_address == 0) { - raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); - break; - } - 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 address = base_address; - for (int i = 0; i < offset; ++i) - address += size_of(element_type(base, 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 - for (int i = 0; i < SIZE(ingredients.at(2)); ++i) { - trace(9999, "mem") << "storing " << no_scientific(ingredients.at(2).at(i)) << " in location " << address+i << end(); - put(Memory, address+i, ingredients.at(2).at(i)); - } - goto finish_instruction; -} - -//:: Allow containers to be defined in mu code. - -:(scenarios load) -:(scenario container) -container foo [ - x:number - y:number -] -+parse: --- defining container foo -+parse: element: {x: "number"} -+parse: element: {y: "number"} - -:(scenario container_use_before_definition) -container foo [ - x:number - y:bar -] - -container bar [ - x:number - y:number -] -+parse: --- defining container foo -+parse: type number: 1000 -+parse: element: {x: "number"} -# todo: brittle -# type bar is unknown at this point, but we assign it a number -+parse: element: {y: "bar"} -# later type bar geon -+parse: --- defining container bar -+parse: type number: 1001 -+parse: element: {x: "number"} -+parse: element: {y: "number"} - -:(before "End Command Handlers") -else if (command == "container") { - insert_container(command, CONTAINER, in); -} - -:(code) -void insert_container(const string& command, kind_of_type kind, istream& in) { - skip_whitespace_but_not_newline(in); - string name = next_word(in); - // End container Name Refinements - trace(9991, "parse") << "--- defining " << command << ' ' << name << end(); - if (!contains_key(Type_ordinal, name) - || get(Type_ordinal, name) == 0) { - put(Type_ordinal, name, Next_type_ordinal++); - } - trace(9999, "parse") << "type number: " << get(Type_ordinal, name) << end(); - skip_bracket(in, "'container' must begin with '['"); - type_info& info = get_or_insert(Type, get(Type_ordinal, name)); - info.name = name; - info.kind = kind; - while (has_data(in)) { - skip_whitespace_and_comments(in); - string element = next_word(in); - if (element == "]") break; - info.elements.push_back(reagent(element)); - replace_unknown_types_with_unique_ordinals(info.elements.back().type, info); - trace(9993, "parse") << " element: " << to_string(info.elements.back()) << end(); - // End Load Container Element Definition - } -} - -void replace_unknown_types_with_unique_ordinals(type_tree* type, const type_info& info) { - if (!type) return; - if (!type->name.empty()) { - if (contains_key(Type_ordinal, type->name)) { - type->value = get(Type_ordinal, type->name); - } - else if (is_integer(type->name)) { // sometimes types will contain non-type tags, like numbers for the size of an array - type->value = 0; - } - // End insert_container Special-cases - else if (type->name != "->") { // used in recipe types - put(Type_ordinal, type->name, Next_type_ordinal++); - type->value = get(Type_ordinal, type->name); - } - } - replace_unknown_types_with_unique_ordinals(type->left, info); - replace_unknown_types_with_unique_ordinals(type->right, info); -} - -void skip_bracket(istream& in, string message) { - skip_whitespace_and_comments(in); - if (in.get() != '[') - raise << message << '\n' << end(); -} - -:(scenarios run) -:(scenario container_define_twice) -container foo [ - x:number -] - -container foo [ - y:number -] - -def main [ - 1:number <- copy 34 - 2:number <- copy 35 - 3:number <- get 1:foo, 0:offset - 4:number <- get 1:foo, 1:offset -] -+mem: storing 34 in location 3 -+mem: storing 35 in location 4 - -//: ensure scenarios are consistent by always starting them at the same type -//: number. -:(before "End Setup") //: for tests -Next_type_ordinal = 1000; -:(before "End Test Run Initialization") -assert(Next_type_ordinal < 1000); - -//:: Allow container definitions anywhere in the codebase, but complain if you -//:: can't find a definition at the end. - -:(scenario run_complains_on_unknown_types) -% Hide_errors = true; -def main [ - # integer is not a type - 1:integer <- copy 0 -] -+error: main: unknown type integer in '1:integer <- copy 0' - -:(scenario run_allows_type_definition_after_use) -def main [ - 1:bar <- copy 0/unsafe -] - -container bar [ - x:number -] -$error: 0 - -:(after "Begin Instruction Modifying Transforms") -// Begin Type Modifying Transforms -Transform.push_back(check_or_set_invalid_types); // idempotent -// End Type Modifying Transforms - -:(code) -void check_or_set_invalid_types(const recipe_ordinal r) { - recipe& caller = get(Recipe, r); - trace(9991, "transform") << "--- check for invalid types in recipe " << caller.name << end(); - for (int index = 0; index < SIZE(caller.steps); ++index) { - instruction& inst = caller.steps.at(index); - for (int i = 0; i < SIZE(inst.ingredients); ++i) - check_or_set_invalid_types(inst.ingredients.at(i).type, maybe(caller.name), "'"+to_original_string(inst)+"'"); - for (int i = 0; i < SIZE(inst.products); ++i) - check_or_set_invalid_types(inst.products.at(i).type, maybe(caller.name), "'"+to_original_string(inst)+"'"); - } - // End check_or_set_invalid_types -} - -void check_or_set_invalid_types(type_tree* type, const string& block, const string& name) { - if (!type) return; // will throw a more precise error elsewhere - // End Container Type Checks - if (type->value == 0) return; - if (!contains_key(Type, type->value)) { - assert(!type->name.empty()); - if (contains_key(Type_ordinal, type->name)) - type->value = get(Type_ordinal, type->name); - else - raise << block << "unknown type " << type->name << " in " << name << '\n' << end(); - } - check_or_set_invalid_types(type->left, block, name); - check_or_set_invalid_types(type->right, block, name); -} - -:(scenario container_unknown_field) -% Hide_errors = true; -container foo [ - x:number - y:bar -] -+error: foo: unknown type in y - -:(scenario read_container_with_bracket_in_comment) -container foo [ - x:number - # ']' in comment - y:number -] -+parse: --- defining container foo -+parse: element: {x: "number"} -+parse: element: {y: "number"} - -:(before "End transform_all") -check_container_field_types(); - -:(code) -void check_container_field_types() { - for (map::iterator p = Type.begin(); p != Type.end(); ++p) { - const type_info& info = p->second; - // Check Container Field Types(info) - for (int i = 0; i < SIZE(info.elements); ++i) - check_invalid_types(info.elements.at(i).type, maybe(info.name), info.elements.at(i).name); - } -} - -void check_invalid_types(const type_tree* type, const string& block, const string& name) { - if (!type) return; // will throw a more precise error elsewhere - if (type->value == 0) { - assert(!type->left && !type->right); - return; - } - if (!contains_key(Type, type->value)) - raise << block << "unknown type in " << name << '\n' << end(); - check_invalid_types(type->left, block, name); - check_invalid_types(type->right, block, name); -} - -//:: Construct types out of their constituent fields. - -:(scenario merge) -container foo [ - x:number - y:number -] - -def main [ - 1:foo <- merge 3, 4 -] -+mem: storing 3 in location 1 -+mem: storing 4 in location 2 - -:(before "End Primitive Recipe Declarations") -MERGE, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "merge", MERGE); -:(before "End Primitive Recipe Checks") -case MERGE: { - // type-checking in a separate transform below - break; -} -:(before "End Primitive Recipe Implementations") -case MERGE: { - products.resize(1); - for (int i = 0; i < SIZE(ingredients); ++i) - for (int j = 0; j < SIZE(ingredients.at(i)); ++j) - products.at(0).push_back(ingredients.at(i).at(j)); - break; -} - -//: type-check 'merge' to avoid interpreting numbers as addresses - -:(scenario merge_check) -def main [ - 1:point <- merge 3, 4 -] -$error: 0 - -:(scenario merge_check_missing_element) -% Hide_errors = true; -def main [ - 1:point <- merge 3 -] -+error: main: too few ingredients in '1:point <- merge 3' - -:(scenario merge_check_extra_element) -% Hide_errors = true; -def main [ - 1:point <- merge 3, 4, 5 -] -+error: main: too many ingredients in '1:point <- merge 3, 4, 5' - -//: We want to avoid causing memory corruption, but other than that we want to -//: be flexible in how we construct containers of containers. It should be -//: equally easy to define a container out of primitives or intermediate -//: container fields. - -:(scenario merge_check_recursive_containers) -def main [ - 1:point <- merge 3, 4 - 1:point-number <- merge 1:point, 5 -] -$error: 0 - -:(scenario merge_check_recursive_containers_2) -% Hide_errors = true; -def main [ - 1:point <- merge 3, 4 - 2:point-number <- merge 1:point -] -+error: main: too few ingredients in '2:point-number <- merge 1:point' - -:(scenario merge_check_recursive_containers_3) -def main [ - 1:point-number <- merge 3, 4, 5 -] -$error: 0 - -:(scenario merge_check_recursive_containers_4) -% Hide_errors = true; -def main [ - 1:point-number <- merge 3, 4 -] -+error: main: too few ingredients in '1:point-number <- merge 3, 4' - -:(scenario merge_check_reflexive) -% Hide_errors = true; -def main [ - 1:point <- merge 3, 4 - 2:point <- merge 1:point -] -$error: 0 - -//: Since a container can be merged in several ways, we need to be able to -//: backtrack through different possibilities. Later we'll allow creating -//: exclusive containers which contain just one of rather than all of their -//: elements. That will also require backtracking capabilities. Here's the -//: state we need to maintain for backtracking: - -:(before "End Types") -struct merge_check_point { - reagent container; - int container_element_index; - merge_check_point(const reagent& c, int i) :container(c), container_element_index(i) {} -}; - -struct merge_check_state { - stack data; -}; - -:(before "End Checks") -Transform.push_back(check_merge_calls); -:(code) -void check_merge_calls(const recipe_ordinal r) { - const recipe& caller = get(Recipe, r); - trace(9991, "transform") << "--- type-check merge instructions in recipe " << caller.name << end(); - for (int i = 0; i < SIZE(caller.steps); ++i) { - const instruction& inst = caller.steps.at(i); - if (inst.name != "merge") continue; - if (SIZE(inst.products) != 1) { - raise << maybe(caller.name) << "'merge' should yield a single product in '" << to_original_string(inst) << "'\n" << end(); - continue; - } - reagent product = inst.products.at(0); - if (!canonize_type(product)) continue; - type_ordinal product_type = product.type->value; - if (product_type == 0 || !contains_key(Type, product_type)) { - raise << maybe(caller.name) << "'merge' should yield a container in '" << to_original_string(inst) << "'\n" << end(); - continue; - } - const type_info& info = get(Type, product_type); - if (info.kind != CONTAINER && info.kind != EXCLUSIVE_CONTAINER) { - raise << maybe(caller.name) << "'merge' should yield a container in '" << to_original_string(inst) << "'\n" << end(); - continue; - } - check_merge_call(inst.ingredients, product, caller, inst); - } -} - -void check_merge_call(const vector& ingredients, const reagent& product, const recipe& caller, const instruction& inst) { - int ingredient_index = 0; - merge_check_state state; - state.data.push(merge_check_point(product, 0)); - while (true) { - assert(!state.data.empty()); - trace(9999, "transform") << ingredient_index << " vs " << SIZE(ingredients) << end(); - if (ingredient_index >= SIZE(ingredients)) { - raise << maybe(caller.name) << "too few ingredients in '" << to_original_string(inst) << "'\n" << end(); - return; - } - reagent& container = state.data.top().container; - type_info& container_info = get(Type, container.type->value); - switch (container_info.kind) { - case CONTAINER: { - // degenerate case: merge with the same type always succeeds - if (state.data.top().container_element_index == 0 && types_coercible(container, inst.ingredients.at(ingredient_index))) - return; - reagent expected_ingredient = element_type(container, state.data.top().container_element_index); - trace(9999, "transform") << "checking container " << to_string(container) << " || " << to_string(expected_ingredient) << " vs ingredient " << ingredient_index << end(); - // if the current element is the ingredient we expect, move on to the next element/ingredient - if (types_coercible(expected_ingredient, ingredients.at(ingredient_index))) { - ++ingredient_index; - ++state.data.top().container_element_index; - while (state.data.top().container_element_index >= SIZE(get(Type, state.data.top().container.type->value).elements)) { - state.data.pop(); - if (state.data.empty()) { - if (ingredient_index < SIZE(ingredients)) - raise << maybe(caller.name) << "too many ingredients in '" << to_original_string(inst) << "'\n" << end(); - return; - } - ++state.data.top().container_element_index; - } - } - // if not, maybe it's a field of the current element - else { - // no change to ingredient_index - state.data.push(merge_check_point(expected_ingredient, 0)); - } - break; - } - // End valid_merge Cases - default: { - if (!types_coercible(container, ingredients.at(ingredient_index))) { - raise << maybe(caller.name) << "incorrect type of ingredient " << ingredient_index << " in '" << to_original_string(inst) << "'\n" << end(); - raise << " (expected " << debug_string(container) << ")\n" << end(); - raise << " (got " << debug_string(ingredients.at(ingredient_index)) << ")\n" << end(); - return; - } - ++ingredient_index; - // ++state.data.top().container_element_index; // unnecessary, but wouldn't do any harm - do { - state.data.pop(); - if (state.data.empty()) { - if (ingredient_index < SIZE(ingredients)) - raise << maybe(caller.name) << "too many ingredients in '" << to_original_string(inst) << "'\n" << end(); - return; - } - ++state.data.top().container_element_index; - } while (state.data.top().container_element_index >= SIZE(get(Type, state.data.top().container.type->value).elements)); - } - } - } - // never gets here - assert(false); -} - -:(scenario merge_check_product) -% Hide_errors = true; -def main [ - 1:number <- merge 3 -] -+error: main: 'merge' should yield a container in '1:number <- merge 3' - -:(before "End Includes") -#include -using std::stack; diff --git a/032array.cc b/032array.cc deleted file mode 100644 index 44d063d9..00000000 --- a/032array.cc +++ /dev/null @@ -1,467 +0,0 @@ -//: Arrays contain a variable number of elements of the same type. Their value -//: starts with the length of the array. -//: -//: You can create arrays of containers, but containers can only contain -//: elements of a fixed size, so you can't create containers containing arrays. -//: Create containers containing addresses to arrays instead. - -//: You can create arrays using 'create-array'. -:(scenario create_array) -def main [ - # create an array occupying locations 1 (for the size) and 2-4 (for the elements) - 1:array:number:3 <- create-array -] -+run: creating array of size 4 - -:(before "End Primitive Recipe Declarations") -CREATE_ARRAY, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "create-array", CREATE_ARRAY); -:(before "End Primitive Recipe Checks") -case CREATE_ARRAY: { - if (inst.products.empty()) { - raise << maybe(get(Recipe, r).name) << "'create-array' needs one product and no ingredients but got '" << to_original_string(inst) << '\n' << end(); - break; - } - reagent product = inst.products.at(0); - canonize_type(product); - if (!is_mu_array(product)) { - raise << maybe(get(Recipe, r).name) << "'create-array' cannot create non-array " << product.original_string << '\n' << end(); - break; - } - if (!product.type->right) { - raise << maybe(get(Recipe, r).name) << "create array of what? " << to_original_string(inst) << '\n' << end(); - break; - } - // 'create-array' will need to check properties rather than types - if (!product.type->right->right) { - raise << maybe(get(Recipe, r).name) << "create array of what size? " << to_original_string(inst) << '\n' << end(); - break; - } - if (!is_integer(product.type->right->right->name)) { - raise << maybe(get(Recipe, r).name) << "'create-array' product should specify size of array after its element type, but got " << product.type->right->right->name << '\n' << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case CREATE_ARRAY: { - reagent product = current_instruction().products.at(0); - canonize(product); - int base_address = product.value; - int array_length = to_integer(product.type->right->right->name); - // initialize array size, so that size_of will work - put(Memory, base_address, array_length); // in array elements - int size = size_of(product); // in locations - trace(9998, "run") << "creating array of size " << size << '\n' << end(); - // initialize array - for (int i = 1; i <= size_of(product); ++i) { - put(Memory, base_address+i, 0); - } - // no need to update product - goto finish_instruction; -} - -:(scenario copy_array) -# Arrays can be copied around with a single instruction just like numbers, -# no matter how large they are. -# You don't need to pass the size around, since each array variable stores its -# size in memory at run-time. We'll call a variable with an explicit size a -# 'static' array, and one without a 'dynamic' array since it can contain -# arrays of many different sizes. -def main [ - 1:array:number:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 5:array:number <- copy 1:array:number:3 -] -+mem: storing 3 in location 5 -+mem: storing 14 in location 6 -+mem: storing 15 in location 7 -+mem: storing 16 in location 8 - -:(scenario copy_array_indirect) -def main [ - 1:array:number:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 5:address:array:number <- copy 1/unsafe - 6:array:number <- copy *5:address:array:number -] -+mem: storing 3 in location 6 -+mem: storing 14 in location 7 -+mem: storing 15 in location 8 -+mem: storing 16 in location 9 - -:(scenario stash_array) -def main [ - 1:array:number:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - stash [foo:], 1:array:number:3 -] -+app: foo: 3 14 15 16 - -:(before "End size_of(reagent) Cases") -if (r.type && r.type->value == get(Type_ordinal, "array")) { - if (!r.type->right) { - 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)); -} - -//: disable the size mismatch check for arrays since the destination array -//: need not be initialized -:(before "End size_mismatch(x) Cases") -if (x.type && x.type->value == get(Type_ordinal, "array")) return false; - -//: arrays are disallowed inside containers unless their length is fixed in -//: advance - -:(scenario container_contains_array) -container foo [ - x:array:number:3 -] -$error: 0 - -:(scenario container_disallows_dynamic_array_element) -% Hide_errors = true; -container foo [ - x:array:number -] -+error: container 'foo' cannot determine size of element x - -:(before "End Load Container Element Definition") -{ - const type_tree* type = info.elements.back().type; - if (type->name == "array") { - if (!type->right) { - raise << "container '" << name << "' doesn't specify type of array elements for " << info.elements.back().name << '\n' << end(); - continue; - } - if (!type->right->right) { // array has no length - raise << "container '" << name << "' cannot determine size of element " << info.elements.back().name << '\n' << end(); - continue; - } - } -} - -//:: To access elements of an array, use 'index' - -:(scenario index) -def main [ - 1:array:number:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 5:number <- index 1:array:number:3, 0 -] -+mem: storing 14 in location 5 - -:(scenario index_direct_offset) -def main [ - 1:array:number:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 5:number <- copy 0 - 6:number <- index 1:array:number, 5:number -] -+mem: storing 14 in location 6 - -:(before "End Primitive Recipe Declarations") -INDEX, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "index", INDEX); -:(before "End Primitive Recipe Checks") -case INDEX: { - if (SIZE(inst.ingredients) != 2) { - raise << maybe(get(Recipe, r).name) << "'index' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end(); - break; - } - reagent base = inst.ingredients.at(0); - canonize_type(base); - if (!is_mu_array(base)) { - raise << maybe(get(Recipe, r).name) << "'index' on a non-array " << base.original_string << '\n' << end(); - break; - } - if (inst.products.empty()) break; - reagent product = inst.products.at(0); - canonize_type(product); - reagent element; - element.type = new type_tree(*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; - } - break; -} -:(before "End Primitive Recipe Implementations") -case INDEX: { - reagent base = current_instruction().ingredients.at(0); - canonize(base); - int base_address = base.value; - trace(9998, "run") << "base address is " << base_address << end(); - if (base_address == 0) { - raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); - break; - } - reagent offset = current_instruction().ingredients.at(1); - canonize(offset); - vector offset_val(read_memory(offset)); - type_tree* element_type = array_element(base.type); - if (offset_val.at(0) < 0 || offset_val.at(0) >= get_or_insert(Memory, base_address)) { - raise << maybe(current_recipe_name()) << "invalid index " << no_scientific(offset_val.at(0)) << '\n' << end(); - break; - } - int src = base_address + 1 + offset_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); - // Read element - products.push_back(read_memory(element)); - break; -} - -:(code) -type_tree* array_element(const type_tree* type) { - if (type->right->left) { - assert(!type->right->left->left); - return type->right->left; - } - return type->right; -} - -int array_length(const reagent& x) { - if (x.type->right->right) { - return to_integer(x.type->right->right->name); - } - // this should never happen at transform time - // x should already be canonized. - return get_or_insert(Memory, x.value); -} - -:(scenario index_indirect) -def main [ - 1:array:number:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 5:address:array:number <- copy 1/unsafe - 6:number <- index *5:address:array:number, 1 -] -+mem: storing 15 in location 6 - -:(scenario index_out_of_bounds) -% Hide_errors = true; -def main [ - 1:array:number:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 5:number <- copy 14 - 6:number <- copy 15 - 7:number <- copy 16 - 8:address:array:point <- copy 1/unsafe - index *8:address:array:point, 4 # less than size of array in locations, but larger than its length in elements -] -+error: main: invalid index 4 - -:(scenario index_out_of_bounds_2) -% Hide_errors = true; -def main [ - 1:array:point:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 5:number <- copy 14 - 6:number <- copy 15 - 7:number <- copy 16 - 8:address:array:point <- copy 1/unsafe - index *8:address:array:point, -1 -] -+error: main: invalid index -1 - -:(scenario index_product_type_mismatch) -% Hide_errors = true; -def main [ - 1:array:point:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 5:number <- copy 14 - 6:number <- copy 15 - 7:number <- copy 16 - 8:address:array:point <- copy 1/unsafe - 9:number <- index *8:address:array:point, 0 -] -+error: main: 'index' on *8:address:array:point can't be saved in 9:number; type should be point - -//: we might want to call 'index' without saving the results, say in a sandbox - -:(scenario index_without_product) -def main [ - 1:array:number:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - index 1:array:number:3, 0 -] -# just don't die - -//:: To write to elements of arrays, use 'put'. - -:(scenario put_index) -def main [ - 1:array:number:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 1:array:number <- put-index 1:array:number, 1, 34 -] -+mem: storing 34 in location 3 - -:(before "End Primitive Recipe Declarations") -PUT_INDEX, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "put-index", PUT_INDEX); -:(before "End Primitive Recipe Checks") -case PUT_INDEX: { - if (SIZE(inst.ingredients) != 3) { - raise << maybe(get(Recipe, r).name) << "'put-index' expects exactly 3 ingredients in '" << to_original_string(inst) << "'\n" << end(); - break; - } - reagent base = inst.ingredients.at(0); - if (!canonize_type(base)) break; - if (!is_mu_array(base)) { - raise << maybe(get(Recipe, r).name) << "'put-index' on a non-array " << base.original_string << '\n' << end(); - break; - } - if (!is_mu_number(inst.ingredients.at(1))) { - raise << maybe(get(Recipe, r).name) << "second ingredient of 'put-index' should have type 'number', but got " << inst.ingredients.at(1).original_string << '\n' << end(); - break; - } - reagent value = inst.ingredients.at(2); - canonize_type(value); - reagent element; - element.type = new type_tree(*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; - } - break; -} -:(before "End Primitive Recipe Implementations") -case PUT_INDEX: { - reagent base = current_instruction().ingredients.at(0); - canonize(base); - int base_address = base.value; - if (base_address == 0) { - raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); - break; - } - reagent offset = current_instruction().ingredients.at(1); - canonize(offset); - vector offset_val(read_memory(offset)); - type_tree* element_type = array_element(base.type); - if (offset_val.at(0) < 0 || offset_val.at(0) >= get_or_insert(Memory, base_address)) { - raise << maybe(current_recipe_name()) << "invalid index " << no_scientific(offset_val.at(0)) << '\n' << end(); - break; - } - int address = base_address + 1 + offset_val.at(0)*size_of(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 - vector value = read_memory(current_instruction().ingredients.at(2)); - for (int i = 0; i < SIZE(value); ++i) { - trace(9999, "mem") << "storing " << no_scientific(value.at(i)) << " in location " << address+i << end(); - put(Memory, address+i, value.at(i)); - } - goto finish_instruction; -} - -:(scenario put_index_out_of_bounds) -% Hide_errors = true; -def main [ - 1:array:point:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 5:number <- copy 14 - 6:number <- copy 15 - 7:number <- copy 16 - 8:point <- merge 34, 35 - 1:array:point <- put-index 1:array:point, 4, 8:point # '4' is less than size of array in locations, but larger than its length in elements -] -+error: main: invalid index 4 - -:(scenario put_index_out_of_bounds_2) -% Hide_errors = true; -def main [ - 1:array:point:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 5:number <- copy 14 - 6:number <- copy 15 - 7:number <- copy 16 - 8:point <- merge 34, 35 - 1:array:point <- put-index 1:array:point, -1, 8:point -] -+error: main: invalid index -1 - -//:: compute the length of an array - -:(scenario array_length) -def main [ - 1:array:number:3 <- create-array - 2:number <- copy 14 - 3:number <- copy 15 - 4:number <- copy 16 - 5:number <- length 1:array:number:3 -] -+mem: storing 3 in location 5 - -:(before "End Primitive Recipe Declarations") -LENGTH, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "length", LENGTH); -:(before "End Primitive Recipe Checks") -case LENGTH: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'length' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end(); - break; - } - reagent x = inst.ingredients.at(0); - canonize_type(x); - if (!is_mu_array(x)) { - raise << "tried to calculate length of non-array " << x.original_string << '\n' << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case LENGTH: { - reagent x = current_instruction().ingredients.at(0); - canonize(x); - if (x.value == 0) { - raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); - break; - } - products.resize(1); - products.at(0).push_back(get_or_insert(Memory, x.value)); - break; -} - -//: optimization: none of the instructions in this layer use 'ingredients' so -//: stop copying potentially huge arrays into it. -:(before "End should_copy_ingredients Special-cases") -recipe_ordinal r = current_instruction().operation; -if (r == CREATE_ARRAY || r == INDEX || r == PUT_INDEX || r == LENGTH) - return false; diff --git a/032exclusive_container.cc b/032exclusive_container.cc new file mode 100644 index 00000000..ad82824d --- /dev/null +++ b/032exclusive_container.cc @@ -0,0 +1,416 @@ +//: Exclusive containers contain exactly one of a fixed number of 'variants' +//: of different types. +//: +//: They also implicitly contain a tag describing precisely which variant is +//: currently stored in them. + +:(before "End Mu Types Initialization") +//: We'll use this container as a running example, with two number elements. +{ +type_ordinal tmp = put(Type_ordinal, "number-or-point", Next_type_ordinal++); +get_or_insert(Type, tmp); // initialize +get(Type, tmp).kind = EXCLUSIVE_CONTAINER; +get(Type, tmp).name = "number-or-point"; +get(Type, tmp).elements.push_back(reagent("i:number")); +get(Type, tmp).elements.push_back(reagent("p:point")); +} + +//: Tests in this layer often explicitly setup memory before reading it as an +//: array. Don't do this in general. I'm tagging exceptions with /raw to +//: avoid errors. +:(scenario copy_exclusive_container) +# Copying exclusive containers copies all their contents and an extra location for the tag. +def main [ + 1:number <- copy 1 # 'point' variant + 2:number <- copy 34 + 3:number <- copy 35 + 4:number-or-point <- copy 1:number-or-point/unsafe +] ++mem: storing 1 in location 4 ++mem: storing 34 in location 5 ++mem: storing 35 in location 6 + +:(before "End size_of(type) Cases") +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; +} + +//:: To access variants of an exclusive container, use 'maybe-convert'. +//: It always returns an address (so that you can modify it) or null (to +//: signal that the conversion failed (because the container contains a +//: different variant). + +//: 'maybe-convert' requires a literal in ingredient 1. We'll use a synonym +//: called 'variant'. +:(before "End Mu Types Initialization") +put(Type_ordinal, "variant", 0); + +:(scenario maybe_convert) +def main [ + 12:number <- copy 1 + 13:number <- copy 35 + 14:number <- copy 36 + 20:point, 22:boolean <- maybe-convert 12:number-or-point/unsafe, 1:variant +] +# point ++mem: storing 35 in location 20 ++mem: storing 36 in location 21 +# boolean ++mem: storing 1 in location 22 + +:(scenario maybe_convert_fail) +def main [ + 12:number <- copy 1 + 13:number <- copy 35 + 14:number <- copy 36 + 20:number, 21:boolean <- maybe-convert 12:number-or-point/unsafe, 0:variant +] +# number: no write +# boolean ++mem: storing 0 in location 21 + +:(before "End Primitive Recipe Declarations") +MAYBE_CONVERT, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "maybe-convert", MAYBE_CONVERT); +:(before "End Primitive Recipe Checks") +case MAYBE_CONVERT: { + const recipe& caller = get(Recipe, r); + if (SIZE(inst.ingredients) != 2) { + raise << maybe(caller.name) << "'maybe-convert' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end(); + break; + } + reagent base = inst.ingredients.at(0); + // Update MAYBE_CONVERT base in Check + if (!base.type || !base.type->value || get(Type, base.type->value).kind != EXCLUSIVE_CONTAINER) { + raise << maybe(caller.name) << "first ingredient of 'maybe-convert' should be an exclusive-container, but got " << base.original_string << '\n' << end(); + break; + } + if (!is_literal(inst.ingredients.at(1))) { + raise << maybe(caller.name) << "second ingredient of 'maybe-convert' should have type 'variant', but got " << inst.ingredients.at(1).original_string << '\n' << end(); + break; + } + if (inst.products.empty()) break; + if (SIZE(inst.products) != 2) { + raise << maybe(caller.name) << "'maybe-convert' expects exactly 2 products in '" << to_original_string(inst) << "'\n" << end(); + break; + } + reagent product = inst.products.at(0); + // Update MAYBE_CONVERT product in Check + reagent& offset = inst.ingredients.at(1); + populate_value(offset); + if (offset.value >= SIZE(get(Type, base.type->value).elements)) { + raise << maybe(caller.name) << "invalid tag " << offset.value << " in '" << to_original_string(inst) << '\n' << end(); + break; + } + reagent variant = variant_type(base, offset.value); + if (!types_coercible(product, variant)) { + raise << maybe(caller.name) << "'maybe-convert " << base.original_string << ", " << inst.ingredients.at(1).original_string << "' should write to " << to_string(variant.type) << " but " << product.name << " has type " << to_string(product.type) << '\n' << end(); + break; + } + reagent status = inst.products.at(1); + // Update MAYBE_CONVERT status in Check + if (!is_mu_boolean(status)) { + raise << maybe(get(Recipe, r).name) << "second product yielded by 'maybe-convert' should be a boolean, but tried to write to " << inst.products.at(1).original_string << '\n' << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case MAYBE_CONVERT: { + reagent base = current_instruction().ingredients.at(0); + // Update MAYBE_CONVERT base in Run + int base_address = base.value; + if (base_address == 0) { + raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); + break; + } + int tag = current_instruction().ingredients.at(1).value; + reagent product = current_instruction().products.at(0); + // Update MAYBE_CONVERT product in Run + reagent status = current_instruction().products.at(1); + // Update MAYBE_CONVERT status in Run + // optimization: directly write results to only update first product when necessary + if (tag == static_cast(get_or_insert(Memory, base_address))) { + const reagent variant = variant_type(base, tag); + for (int i = 0; i < size_of(variant); ++i) { + double val = get_or_insert(Memory, base_address+1+i); + trace(9999, "mem") << "storing " << no_scientific(val) << " in location " << product.value+i << end(); + put(Memory, product.value+i, val); + } + trace(9999, "mem") << "storing 1 in location " << status.value << end(); + put(Memory, status.value, 1); + } + else { + trace(9999, "mem") << "storing 0 in location " << status.value << end(); + put(Memory, status.value, 0); + } + goto finish_instruction; +} + +:(code) +const reagent variant_type(const reagent& base, 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(info.kind == EXCLUSIVE_CONTAINER); + reagent element = info.elements.at(tag); + // End variant_type Special-cases + return element; +} + +:(scenario maybe_convert_product_type_mismatch) +% Hide_errors = true; +def main [ + 12:number <- copy 1 + 13:number <- copy 35 + 14:number <- copy 36 + 20:number, 21:boolean <- maybe-convert 12:number-or-point/unsafe, 1:variant +] ++error: main: 'maybe-convert 12:number-or-point/unsafe, 1:variant' should write to point but 20 has type number + +//:: Allow exclusive containers to be defined in mu code. + +:(scenario exclusive_container) +exclusive-container foo [ + x:number + y:number +] ++parse: --- defining exclusive-container foo ++parse: element: {x: "number"} ++parse: element: {y: "number"} + +:(before "End Command Handlers") +else if (command == "exclusive-container") { + insert_container(command, EXCLUSIVE_CONTAINER, in); +} + +//: arrays are disallowed inside exclusive containers unless their length is +//: fixed in advance + +:(scenario exclusive_container_contains_array) +exclusive-container foo [ + x:array:number:3 +] +$error: 0 + +:(scenario exclusive_container_disallows_dynamic_array_element) +% Hide_errors = true; +exclusive-container foo [ + x:array:number +] ++error: container 'foo' cannot determine size of element x + +//:: To construct exclusive containers out of variant types, use 'merge'. +:(scenario lift_to_exclusive_container) +exclusive-container foo [ + x:number + y:number +] + +def main [ + 1:number <- copy 34 + 2:foo <- merge 0/x, 1:number # tag must be a literal when merging exclusive containers + 4:foo <- merge 1/y, 1:number +] ++mem: storing 0 in location 2 ++mem: storing 34 in location 3 ++mem: storing 1 in location 4 ++mem: storing 34 in location 5 + +//: type-checking for 'merge' on exclusive containers + +:(scenario merge_handles_exclusive_container) +exclusive-container foo [ + x:number + y:bar +] +container bar [ + z:number +] +def main [ + 1:foo <- merge 0/x, 34 +] ++mem: storing 0 in location 1 ++mem: storing 34 in location 2 +$error: 0 + +:(scenario merge_requires_literal_tag_for_exclusive_container) +% Hide_errors = true; +exclusive-container foo [ + x:number + y:bar +] +container bar [ + z:number +] +def main [ + local-scope + 1:number <- copy 0 + 2:foo <- merge 1:number, 34 +] ++error: main: ingredient 0 of 'merge' should be a literal, for the tag of exclusive-container foo + +:(before "End valid_merge Cases") +case EXCLUSIVE_CONTAINER: { + assert(state.data.top().container_element_index == 0); + trace(9999, "transform") << "checking exclusive container " << to_string(container) << " vs ingredient " << ingredient_index << end(); + if (!is_literal(ingredients.at(ingredient_index))) { + raise << maybe(caller.name) << "ingredient " << ingredient_index << " of 'merge' should be a literal, for the tag of exclusive-container " << container_info.name << '\n' << end(); + return; + } + reagent ingredient = ingredients.at(ingredient_index); // unnecessary copy just to keep this function from modifying caller + populate_value(ingredient); + if (ingredient.value >= SIZE(container_info.elements)) { + raise << maybe(caller.name) << "invalid tag at " << ingredient_index << " for " << container_info.name << " in '" << to_original_string(inst) << '\n' << end(); + return; + } + reagent variant = variant_type(container, ingredient.value); + trace(9999, "transform") << "tag: " << ingredient.value << end(); + // replace union with its variant + state.data.pop(); + state.data.push(merge_check_point(variant, 0)); + ++ingredient_index; + break; +} + +:(scenario merge_check_container_containing_exclusive_container) +container foo [ + x:number + y:bar +] +exclusive-container bar [ + x:number + y:number +] +def main [ + 1:foo <- merge 23, 1/y, 34 +] ++mem: storing 23 in location 1 ++mem: storing 1 in location 2 ++mem: storing 34 in location 3 +$error: 0 + +:(scenario merge_check_container_containing_exclusive_container_2) +% Hide_errors = true; +container foo [ + x:number + y:bar +] +exclusive-container bar [ + x:number + y:number +] +def main [ + 1:foo <- merge 23, 1/y, 34, 35 +] ++error: main: too many ingredients in '1:foo <- merge 23, 1/y, 34, 35' + +:(scenario merge_check_exclusive_container_containing_container) +exclusive-container foo [ + x:number + y:bar +] +container bar [ + x:number + y:number +] +def main [ + 1:foo <- merge 1/y, 23, 34 +] ++mem: storing 1 in location 1 ++mem: storing 23 in location 2 ++mem: storing 34 in location 3 +$error: 0 + +:(scenario merge_check_exclusive_container_containing_container_2) +exclusive-container foo [ + x:number + y:bar +] +container bar [ + x:number + y:number +] +def main [ + 1:foo <- merge 0/x, 23 +] +$error: 0 + +:(scenario merge_check_exclusive_container_containing_container_3) +% Hide_errors = true; +exclusive-container foo [ + x:number + y:bar +] +container bar [ + x:number + y:number +] +def main [ + 1:foo <- merge 1/y, 23 +] ++error: main: too few ingredients in '1:foo <- merge 1/y, 23' + +:(scenario merge_check_exclusive_container_containing_container_4) +exclusive-container foo [ + x:number + y:bar +] +container bar [ + a:number + b:number +] +def main [ + 1:bar <- merge 23, 24 + 3:foo <- merge 1/y, 1:bar +] +$error: 0 + +//: Since the different variants of an exclusive-container might have +//: different sizes, relax the size mismatch check for 'merge' instructions. +:(before "End size_mismatch(x) Cases") +if (current_step_index() < SIZE(Current_routine->steps()) + && current_instruction().operation == MERGE + && !current_instruction().products.empty() + && current_instruction().products.at(0).type) { + reagent x = current_instruction().products.at(0); + // Update size_mismatch Check for MERGE(x) + if (get(Type, x.type->value).kind == EXCLUSIVE_CONTAINER) + return size_of(x) < SIZE(data); +} + +:(scenario merge_exclusive_container_with_mismatched_sizes) +container foo [ + x:number + y:number +] + +exclusive-container bar [ + x:number + y:foo +] + +def main [ + 1:number <- copy 34 + 2:number <- copy 35 + 3:bar <- merge 0/x, 1:number + 6:bar <- merge 1/foo, 1:number, 2:number +] ++mem: storing 0 in location 3 ++mem: storing 34 in location 4 +# bar is always 3 large so location 5 is skipped ++mem: storing 1 in location 6 ++mem: storing 34 in location 7 ++mem: storing 35 in location 8 diff --git a/033address.cc b/033address.cc new file mode 100644 index 00000000..1b956fe0 --- /dev/null +++ b/033address.cc @@ -0,0 +1,387 @@ +//: Instructions can read from addresses pointing at other locations using the +//: 'lookup' property. + +:(scenario copy_indirect) +def main [ + 1:address:number <- copy 2/unsafe + 2:number <- copy 34 + # This loads location 1 as an address and looks up *that* location. + 3:number <- copy 1:address:number/lookup +] ++mem: storing 34 in location 3 + +:(before "End Preprocess read_memory(x)") +canonize(x); + +//: similarly, write to addresses pointing at other locations using the +//: 'lookup' property +:(scenario store_indirect) +def main [ + 1:address:number <- copy 2/unsafe + 1:address:number/lookup <- copy 34 +] ++mem: storing 34 in location 2 + +:(before "End Preprocess write_memory(x)") +canonize(x); +if (x.value == 0) { + raise << "can't write to location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); + return; +} + +//: writes to address 0 always loudly fail +:(scenario store_to_0_fails) +% Hide_errors = true; +def main [ + 1:address:number <- copy 0 + 1:address:number/lookup <- copy 34 +] +-mem: storing 34 in location 0 ++error: can't write to location 0 in '1:address:number/lookup <- copy 34' + +:(code) +void canonize(reagent& x) { + if (is_literal(x)) return; + // End canonize(x) Special-cases + while (has_property(x, "lookup")) + lookup_memory(x); +} + +void lookup_memory(reagent& x) { + if (!x.type || x.type->value != get(Type_ordinal, "address")) { + raise << maybe(current_recipe_name()) << "tried to /lookup " << x.original_string << " but it isn't an address\n" << end(); + return; + } + // compute value + if (x.value == 0) { + raise << maybe(current_recipe_name()) << "tried to /lookup 0\n" << end(); + return; + } + trace(9999, "mem") << "location " << x.value << " is " << no_scientific(get_or_insert(Memory, x.value)) << end(); + x.set_value(get_or_insert(Memory, x.value)); + drop_from_type(x, "address"); + // End Drop Address In lookup_memory(x) + drop_one_lookup(x); +} + +:(after "bool types_strictly_match(reagent to, reagent from)") + if (!canonize_type(to)) return false; + if (!canonize_type(from)) return false; + +:(after "bool is_mu_array(reagent r)") + if (!canonize_type(r)) return false; + +:(after "bool is_mu_address(reagent r)") + if (!canonize_type(r)) return false; + +:(after "bool is_mu_number(reagent r)") + if (!canonize_type(r)) return false; +:(after "bool is_mu_boolean(reagent r)") + if (!canonize_type(r)) return false; + +:(after "Update product While Type-checking Merge") +if (!canonize_type(product)) continue; + +:(before "End Compute Call Ingredient") +canonize_type(ingredient); +:(before "End Preprocess NEXT_INGREDIENT product") +canonize_type(product); +:(before "End Check REPLY Copy(lhs, rhs) +canonize_type(lhs); +canonize_type(rhs); + +:(code) +bool canonize_type(reagent& r) { + while (has_property(r, "lookup")) { + if (!r.type || r.type->value != get(Type_ordinal, "address")) { + raise << "can't lookup non-address: " << to_string(r) << ": " << to_string(r.type) << '\n' << end(); + return false; + } + drop_from_type(r, "address"); + // End Drop Address In canonize_type(r) + drop_one_lookup(r); + } + return true; +} + +void drop_from_type(reagent& r, string expected_type) { + if (r.type->name != expected_type) { + raise << "can't drop2 " << expected_type << " from " << to_string(r) << '\n' << end(); + return; + } + type_tree* tmp = r.type; + r.type = tmp->right; + tmp->right = NULL; + delete tmp; +} + +void drop_one_lookup(reagent& r) { + for (vector >::iterator p = r.properties.begin(); p != r.properties.end(); ++p) { + if (p->first == "lookup") { + r.properties.erase(p); + return; + } + } + assert(false); +} + +//:: 'get' can read from container address +:(scenario get_indirect) +def main [ + 1:number <- copy 2 + 2:number <- copy 34 + 3:number <- copy 35 + 4:number <- get 1:address:point/lookup, 0:offset +] ++mem: storing 34 in location 4 + +:(scenario get_indirect2) +def main [ + 1:number <- copy 2 + 2:number <- copy 34 + 3:number <- copy 35 + 4:address:number <- copy 5/unsafe + *4:address:number <- get 1:address:point/lookup, 0:offset +] ++mem: storing 34 in location 5 + +:(scenario include_nonlookup_properties) +def main [ + 1:number <- copy 2 + 2:number <- copy 34 + 3:number <- copy 35 + 4:number <- get 1:address:point/lookup/foo, 0:offset +] ++mem: storing 34 in location 4 + +:(after "Update GET base in Check") +if (!canonize_type(base)) break; +:(after "Update GET product in Check") +if (!canonize_type(product)) break; +:(after "Update GET base in Run") +canonize(base); + +:(scenario put_indirect) +# 'put' can read from container address +def main [ + 1:number <- copy 2 + 2:number <- copy 34 + 3:number <- copy 35 + 1:address:point/lookup <- put 1:address:point/lookup, 0:offset, 36 +] ++mem: storing 36 in location 2 + +:(after "Update PUT base in Check") +if (!canonize_type(base)) break; +:(after "Update PUT offset in Check") +if (!canonize_type(offset)) break; +:(after "Update PUT base in Run") +canonize(base); + +:(scenario copy_array_indirect) +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:address:array:number <- copy 1/unsafe + 6:array:number <- copy *5:address:array:number +] ++mem: storing 3 in location 6 ++mem: storing 14 in location 7 ++mem: storing 15 in location 8 ++mem: storing 16 in location 9 + +:(before "Update CREATE_ARRAY product in Check") +// 'create-array' does not support indirection. Static arrays are meant to be +// allocated on the 'stack'. +assert(!has_property(product, "lookup")); +:(before "Update CREATE_ARRAY product in Run") +// 'create-array' does not support indirection. Static arrays are meant to be +// allocated on the 'stack'. +assert(!has_property(product, "lookup")); + +:(scenario index_indirect) +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:address:array:number <- copy 1/unsafe + 6:number <- index 5:address:array:number/lookup, 1 +] ++mem: storing 15 in location 6 + +:(before "Update INDEX base in Check") +if (!canonize_type(base)) break; +:(before "Update INDEX index in Check") +if (!canonize_type(index)) break; +:(before "Update INDEX product in Check") +if (!canonize_type(product)) break; + +:(before "Update INDEX base in Run") +canonize(base); +:(before "Update INDEX index in Run") +canonize(index); + +:(scenario put_index_indirect) +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:address:array:number <- copy 1/unsafe + 5:address:array:number/lookup <- put-index 5:address:array:number/lookup, 1, 34 +] ++mem: storing 34 in location 3 + +:(scenario put_index_indirect_2) +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:address:number <- copy 6/unsafe + 6:number <- copy 1 + 5:address:array:number/lookup <- put-index 1:array:number:3, 5:address:number/lookup, 34 +] ++mem: storing 34 in location 3 + +:(before "Update PUT_INDEX base in Check") +if (!canonize_type(base)) break; +:(before "Update PUT_INDEX index in Check") +if (!canonize_type(index)) break; +:(before "Update PUT_INDEX value in Check") +if (!canonize_type(value)) break; + +:(before "Update PUT_INDEX base in Run") +canonize(base); +:(before "Update PUT_INDEX index in Run") +canonize(index); + +:(scenario length_indirect) +def main [ + 1:array:number:3 <- create-array + 2:number <- copy 14 + 3:number <- copy 15 + 4:number <- copy 16 + 5:address:array:number <- copy 1/unsafe + 6:number <- length 5:address:array:number/lookup +] ++mem: storing 3 in location 6 + +:(before "Update LENGTH array in Check") +if (!canonize_type(array)) break; +:(before "Update LENGTH array in Run") +canonize(array); + +:(scenario maybe_convert_indirect) +def main [ + 1:number-or-point <- merge 0/number, 34 + 10:address:number-or-point <- copy 1/unsafe + 11:number, 12:boolean <- maybe-convert 10:address:number-or-point/lookup, i:variant +] ++mem: storing 34 in location 11 ++mem: storing 1 in location 12 + +:(scenario maybe_convert_indirect_2) +def main [ + 1:number-or-point <- merge 0/number, 34 + 10:address:number-or-point <- copy 1/unsafe + 11:address:number <- copy 20/unsafe + 11:address:number/lookup, 12:boolean <- maybe-convert 10:address:number-or-point/lookup, i:variant +] ++mem: storing 34 in location 20 ++mem: storing 1 in location 12 + +:(scenario maybe_convert_indirect_3) +def main [ + 1:number-or-point <- merge 0/number, 34 + 10:address:number-or-point <- copy 1/unsafe + 12:address:boolean <- copy 20/unsafe + 11:number, 12:address:boolean/lookup <- maybe-convert 10:address:number-or-point/lookup, i:variant +] ++mem: storing 34 in location 11 ++mem: storing 1 in location 20 + +:(before "Update MAYBE_CONVERT base in Check") +if (!canonize_type(base)) break; +:(before "Update MAYBE_CONVERT product in Check") +if (!canonize_type(product)) break; +:(before "Update MAYBE_CONVERT status in Check") +if (!canonize_type(status)) break; + +:(before "Update MAYBE_CONVERT base in Run") +canonize(base); +:(before "Update MAYBE_CONVERT product in Run") +canonize(product); +:(before "Update MAYBE_CONVERT status in Run") +canonize(status); + +:(scenario merge_exclusive_container_indirect) +def main [ + 1:address:number-or-point <- copy 10/unsafe + 1:address:number-or-point/lookup <- merge 0/number, 34 +] ++mem: storing 0 in location 10 ++mem: storing 34 in location 11 + +:(before "Update size_mismatch Check for MERGE(x) +canonize(x); + +//:: abbreviation for '/lookup': a prefix '*' + +:(scenario lookup_abbreviation) +def main [ + 1:address:number <- copy 2/unsafe + 2:number <- copy 34 + 3:number <- copy *1:address:number +] ++parse: ingredient: {1: ("address" "number"), "lookup": ()} ++mem: storing 34 in location 3 + +:(before "End Parsing reagent") +{ + while (!name.empty() && name.at(0) == '*') { + name.erase(0, 1); + properties.push_back(pair("lookup", NULL)); + } + if (name.empty()) + raise << "illegal name " << original_string << '\n' << end(); +} + +//:: helpers for debugging + +:(before "End Primitive Recipe Declarations") +_DUMP, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "$dump", _DUMP); +:(before "End Primitive Recipe Implementations") +case _DUMP: { + reagent after_canonize = current_instruction().ingredients.at(0); + canonize(after_canonize); + cerr << maybe(current_recipe_name()) << current_instruction().ingredients.at(0).name << ' ' << no_scientific(current_instruction().ingredients.at(0).value) << " => " << no_scientific(after_canonize.value) << " => " << no_scientific(get_or_insert(Memory, after_canonize.value)) << '\n'; + break; +} + +//: grab an address, and then dump its value at intervals +//: useful for tracking down memory corruption (writing to an out-of-bounds address) +:(before "End Globals") +int Bar = -1; +:(before "End Primitive Recipe Declarations") +_BAR, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "$bar", _BAR); +:(before "End Primitive Recipe Implementations") +case _BAR: { + if (current_instruction().ingredients.empty()) { + if (Bar != -1) cerr << Bar << ": " << no_scientific(get_or_insert(Memory, Bar)) << '\n'; + else cerr << '\n'; + } + else { + reagent tmp = current_instruction().ingredients.at(0); + canonize(tmp); + Bar = tmp.value; + } + break; +} diff --git a/033exclusive_container.cc b/033exclusive_container.cc deleted file mode 100644 index 4a7a5e40..00000000 --- a/033exclusive_container.cc +++ /dev/null @@ -1,414 +0,0 @@ -//: Exclusive containers contain exactly one of a fixed number of 'variants' -//: of different types. -//: -//: They also implicitly contain a tag describing precisely which variant is -//: currently stored in them. - -:(before "End Mu Types Initialization") -//: We'll use this container as a running example, with two number elements. -{ -type_ordinal tmp = put(Type_ordinal, "number-or-point", Next_type_ordinal++); -get_or_insert(Type, tmp); // initialize -get(Type, tmp).kind = EXCLUSIVE_CONTAINER; -get(Type, tmp).name = "number-or-point"; -get(Type, tmp).elements.push_back(reagent("i:number")); -get(Type, tmp).elements.push_back(reagent("p:point")); -} - -//: Tests in this layer often explicitly setup memory before reading it as an -//: array. Don't do this in general. I'm tagging exceptions with /raw to -//: avoid errors. -:(scenario copy_exclusive_container) -# Copying exclusive containers copies all their contents and an extra location for the tag. -def main [ - 1:number <- copy 1 # 'point' variant - 2:number <- copy 34 - 3:number <- copy 35 - 4:number-or-point <- copy 1:number-or-point/unsafe -] -+mem: storing 1 in location 4 -+mem: storing 34 in location 5 -+mem: storing 35 in location 6 - -:(before "End size_of(type) Cases") -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; -} - -//:: To access variants of an exclusive container, use 'maybe-convert'. -//: It always returns an address (so that you can modify it) or null (to -//: signal that the conversion failed (because the container contains a -//: different variant). - -//: 'maybe-convert' requires a literal in ingredient 1. We'll use a synonym -//: called 'variant'. -:(before "End Mu Types Initialization") -put(Type_ordinal, "variant", 0); - -:(scenario maybe_convert) -def main [ - 12:number <- copy 1 - 13:number <- copy 35 - 14:number <- copy 36 - 20:point, 22:boolean <- maybe-convert 12:number-or-point/unsafe, 1:variant -] -# point -+mem: storing 35 in location 20 -+mem: storing 36 in location 21 -# boolean -+mem: storing 1 in location 22 - -:(scenario maybe_convert_fail) -def main [ - 12:number <- copy 1 - 13:number <- copy 35 - 14:number <- copy 36 - 20:number, 21:boolean <- maybe-convert 12:number-or-point/unsafe, 0:variant -] -# number: no write -# boolean -+mem: storing 0 in location 21 - -:(before "End Primitive Recipe Declarations") -MAYBE_CONVERT, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "maybe-convert", MAYBE_CONVERT); -:(before "End Primitive Recipe Checks") -case MAYBE_CONVERT: { - const recipe& caller = get(Recipe, r); - if (SIZE(inst.ingredients) != 2) { - raise << maybe(caller.name) << "'maybe-convert' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end(); - break; - } - reagent base = inst.ingredients.at(0); - canonize_type(base); - if (!base.type || !base.type->value || get(Type, base.type->value).kind != EXCLUSIVE_CONTAINER) { - raise << maybe(caller.name) << "first ingredient of 'maybe-convert' should be an exclusive-container, but got " << base.original_string << '\n' << end(); - break; - } - if (!is_literal(inst.ingredients.at(1))) { - raise << maybe(caller.name) << "second ingredient of 'maybe-convert' should have type 'variant', but got " << inst.ingredients.at(1).original_string << '\n' << end(); - break; - } - if (inst.products.empty()) break; - if (SIZE(inst.products) != 2) { - raise << maybe(caller.name) << "'maybe-convert' expects exactly 2 products in '" << to_original_string(inst) << "'\n" << end(); - break; - } - reagent product = inst.products.at(0); - if (!canonize_type(product)) break; - reagent& offset = inst.ingredients.at(1); - populate_value(offset); - if (offset.value >= SIZE(get(Type, base.type->value).elements)) { - raise << maybe(caller.name) << "invalid tag " << offset.value << " in '" << to_original_string(inst) << '\n' << end(); - break; - } - reagent variant = variant_type(base, offset.value); - if (!types_coercible(product, variant)) { - raise << maybe(caller.name) << "'maybe-convert " << base.original_string << ", " << inst.ingredients.at(1).original_string << "' should write to " << to_string(variant.type) << " but " << product.name << " has type " << to_string(product.type) << '\n' << end(); - break; - } - if (!is_mu_boolean(inst.products.at(1))) { - raise << maybe(get(Recipe, r).name) << "second product yielded by 'maybe-convert' should be a boolean, but tried to write to " << inst.products.at(1).original_string << '\n' << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case MAYBE_CONVERT: { - reagent base = current_instruction().ingredients.at(0); - canonize(base); - int base_address = base.value; - if (base_address == 0) { - raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end(); - break; - } - int tag = current_instruction().ingredients.at(1).value; - reagent product = current_instruction().products.at(0); - canonize(product); - reagent did_conversion_happen = current_instruction().products.at(1); - canonize(did_conversion_happen); - // optimization: directly write results to only update first product when necessary - if (tag == static_cast(get_or_insert(Memory, base_address))) { - const reagent variant = variant_type(base, tag); - for (int i = 0; i < size_of(variant); ++i) { - double val = get_or_insert(Memory, base_address+1+i); - trace(9999, "mem") << "storing " << no_scientific(val) << " in location " << product.value+i << end(); - put(Memory, product.value+i, val); - } - trace(9999, "mem") << "storing 1 in location " << did_conversion_happen.value << end(); - put(Memory, did_conversion_happen.value, 1); - } - else { - trace(9999, "mem") << "storing 0 in location " << did_conversion_happen.value << end(); - put(Memory, did_conversion_happen.value, 0); - } - goto finish_instruction; -} - -:(code) -const reagent variant_type(const reagent& canonized_base, int tag) { - assert(tag >= 0); - assert(contains_key(Type, canonized_base.type->value)); - assert(!get(Type, canonized_base.type->value).name.empty()); - const type_info& info = get(Type, canonized_base.type->value); - assert(info.kind == EXCLUSIVE_CONTAINER); - reagent element = info.elements.at(tag); - // End variant_type Special-cases - return element; -} - -:(scenario maybe_convert_product_type_mismatch) -% Hide_errors = true; -def main [ - 12:number <- copy 1 - 13:number <- copy 35 - 14:number <- copy 36 - 20:number, 21:boolean <- maybe-convert 12:number-or-point/unsafe, 1:variant -] -+error: main: 'maybe-convert 12:number-or-point/unsafe, 1:variant' should write to point but 20 has type number - -//:: Allow exclusive containers to be defined in mu code. - -:(scenario exclusive_container) -exclusive-container foo [ - x:number - y:number -] -+parse: --- defining exclusive-container foo -+parse: element: {x: "number"} -+parse: element: {y: "number"} - -:(before "End Command Handlers") -else if (command == "exclusive-container") { - insert_container(command, EXCLUSIVE_CONTAINER, in); -} - -//: arrays are disallowed inside exclusive containers unless their length is -//: fixed in advance - -:(scenario exclusive_container_contains_array) -exclusive-container foo [ - x:array:number:3 -] -$error: 0 - -:(scenario exclusive_container_disallows_dynamic_array_element) -% Hide_errors = true; -exclusive-container foo [ - x:array:number -] -+error: container 'foo' cannot determine size of element x - -//:: To construct exclusive containers out of variant types, use 'merge'. -:(scenario lift_to_exclusive_container) -exclusive-container foo [ - x:number - y:number -] - -def main [ - 1:number <- copy 34 - 2:foo <- merge 0/x, 1:number # tag must be a literal when merging exclusive containers - 4:foo <- merge 1/y, 1:number -] -+mem: storing 0 in location 2 -+mem: storing 34 in location 3 -+mem: storing 1 in location 4 -+mem: storing 34 in location 5 - -//: type-checking for 'merge' on exclusive containers - -:(scenario merge_handles_exclusive_container) -exclusive-container foo [ - x:number - y:bar -] -container bar [ - z:number -] -def main [ - 1:foo <- merge 0/x, 34 -] -+mem: storing 0 in location 1 -+mem: storing 34 in location 2 -$error: 0 - -:(scenario merge_requires_literal_tag_for_exclusive_container) -% Hide_errors = true; -exclusive-container foo [ - x:number - y:bar -] -container bar [ - z:number -] -def main [ - local-scope - 1:number <- copy 0 - 2:foo <- merge 1:number, 34 -] -+error: main: ingredient 0 of 'merge' should be a literal, for the tag of exclusive-container foo - -:(before "End valid_merge Cases") -case EXCLUSIVE_CONTAINER: { - assert(state.data.top().container_element_index == 0); - trace(9999, "transform") << "checking exclusive container " << to_string(container) << " vs ingredient " << ingredient_index << end(); - if (!is_literal(ingredients.at(ingredient_index))) { - raise << maybe(caller.name) << "ingredient " << ingredient_index << " of 'merge' should be a literal, for the tag of exclusive-container " << container_info.name << '\n' << end(); - return; - } - reagent ingredient = ingredients.at(ingredient_index); // unnecessary copy just to keep this function from modifying caller - populate_value(ingredient); - if (ingredient.value >= SIZE(container_info.elements)) { - raise << maybe(caller.name) << "invalid tag at " << ingredient_index << " for " << container_info.name << " in '" << to_original_string(inst) << '\n' << end(); - return; - } - reagent variant = variant_type(container, ingredient.value); - trace(9999, "transform") << "tag: " << ingredient.value << end(); - // replace union with its variant - state.data.pop(); - state.data.push(merge_check_point(variant, 0)); - ++ingredient_index; - break; -} - -:(scenario merge_check_container_containing_exclusive_container) -container foo [ - x:number - y:bar -] -exclusive-container bar [ - x:number - y:number -] -def main [ - 1:foo <- merge 23, 1/y, 34 -] -+mem: storing 23 in location 1 -+mem: storing 1 in location 2 -+mem: storing 34 in location 3 -$error: 0 - -:(scenario merge_check_container_containing_exclusive_container_2) -% Hide_errors = true; -container foo [ - x:number - y:bar -] -exclusive-container bar [ - x:number - y:number -] -def main [ - 1:foo <- merge 23, 1/y, 34, 35 -] -+error: main: too many ingredients in '1:foo <- merge 23, 1/y, 34, 35' - -:(scenario merge_check_exclusive_container_containing_container) -exclusive-container foo [ - x:number - y:bar -] -container bar [ - x:number - y:number -] -def main [ - 1:foo <- merge 1/y, 23, 34 -] -+mem: storing 1 in location 1 -+mem: storing 23 in location 2 -+mem: storing 34 in location 3 -$error: 0 - -:(scenario merge_check_exclusive_container_containing_container_2) -exclusive-container foo [ - x:number - y:bar -] -container bar [ - x:number - y:number -] -def main [ - 1:foo <- merge 0/x, 23 -] -$error: 0 - -:(scenario merge_check_exclusive_container_containing_container_3) -% Hide_errors = true; -exclusive-container foo [ - x:number - y:bar -] -container bar [ - x:number - y:number -] -def main [ - 1:foo <- merge 1/y, 23 -] -+error: main: too few ingredients in '1:foo <- merge 1/y, 23' - -:(scenario merge_check_exclusive_container_containing_container_4) -exclusive-container foo [ - x:number - y:bar -] -container bar [ - a:number - b:number -] -def main [ - 1:bar <- merge 23, 24 - 3:foo <- merge 1/y, 1:bar -] -$error: 0 - -//: Since the different variants of an exclusive-container might have -//: different sizes, relax the size mismatch check for 'merge' instructions. -:(before "End size_mismatch(x) Cases") -if (current_step_index() < SIZE(Current_routine->steps()) - && current_instruction().operation == MERGE - && !current_instruction().products.empty() - && current_instruction().products.at(0).type) { - reagent x = current_instruction().products.at(0); - canonize(x); - if (get(Type, x.type->value).kind == EXCLUSIVE_CONTAINER) - return size_of(x) < SIZE(data); -} - -:(scenario merge_exclusive_container_with_mismatched_sizes) -container foo [ - x:number - y:number -] - -exclusive-container bar [ - x:number - y:foo -] - -def main [ - 1:number <- copy 34 - 2:number <- copy 35 - 3:bar <- merge 0/x, 1:number - 6:bar <- merge 1/foo, 1:number, 2:number -] -+mem: storing 0 in location 3 -+mem: storing 34 in location 4 -# bar is always 3 large so location 5 is skipped -+mem: storing 1 in location 6 -+mem: storing 34 in location 7 -+mem: storing 35 in location 8 diff --git a/034new.cc b/034new.cc new file mode 100644 index 00000000..ec30fee1 --- /dev/null +++ b/034new.cc @@ -0,0 +1,686 @@ +//: Creating space for new variables at runtime. + +//: Mu has two primitives for managing allocations: +//: - 'allocate' reserves a specified amount of space +//: - 'abandon' returns allocated space to be reused by future calls to 'allocate' +//: +//: In practice it's useful to let programs copy addresses anywhere they want, +//: but a prime source of (particularly security) bugs is accessing memory +//: after it's been abandoned. To avoid this, mu programs use a safer +//: primitive called 'new', which adds two features: +//: +//: - it takes a type rather than a size, to save you the trouble of +//: calculating sizes of different variables. +//: - it allocates an extra location where it tracks so-called 'reference +//: counts' or refcounts: the number of address variables in your program that +//: point to this allocation. The initial refcount of an allocation starts out +//: at 1 (the product of the 'new' instruction). When other variables are +//: copied from it the refcount is incremented. When a variable stops pointing +//: at it the refcount is decremented. When the refcount goes to 0 the +//: allocation is automatically abandoned. +//: +//: Mu programs guarantee you'll have no memory corruption bugs as long as you +//: use 'new' and never use 'allocate' or 'abandon'. However, they don't help +//: you at all to remember to abandon memory after you're done with it. To +//: minimize memory use, be sure to reset allocated addresses to 0 when you're +//: done with them. + +//: interlude { +//: To help you distinguish addresses that point at allocations, 'new' returns +//: type address:shared:___. Think of 'shared' as a generic container that +//: contains one extra field: the refcount. However, lookup operations will +//: transparently drop the 'shared' and access to the refcount. Copying +//: between shared and non-shared addresses is forbidden. +:(before "End Mu Types Initialization") +type_ordinal shared = put(Type_ordinal, "shared", Next_type_ordinal++); +get_or_insert(Type, shared).name = "shared"; +:(before "End Drop Address In lookup_memory(x)") +if (x.type->name == "shared" && x.value != 0) { + trace(9999, "mem") << "skipping refcount at " << x.value << end(); + x.set_value(x.value+1); // skip refcount + drop_from_type(x, "shared"); +} +:(before "End Drop Address In canonize_type(r)") +if (r.type->name == "shared") { + drop_from_type(r, "shared"); +} + +:(code) +void test_lookup_shared_address() { + reagent x("*x:address:shared:number"); + x.set_value(34); // unsafe + put(Memory, 34, 1000); + lookup_memory(x); + CHECK_TRACE_CONTENTS("mem: skipping refcount at 1000"); + CHECK_EQ(x.value, 1001); +} + +void test_lookup_shared_address_skip_zero() { + reagent x("*x:address:shared:number"); + x.set_value(34); // unsafe + put(Memory, 34, 0); + lookup_memory(x); + CHECK_TRACE_DOESNT_CONTAIN("mem: skipping refcount at 0"); + CHECK_EQ(x.value, 0); +} + +//: } end interlude + +:(scenarios run) +:(scenario new) +# call new two times with identical arguments; you should get back different results +def main [ + 1:address:shared:number/raw <- new number:type + 2:address:shared:number/raw <- new number:type + 3:boolean/raw <- equal 1:address:shared:number/raw, 2:address:shared:number/raw +] ++mem: storing 0 in location 3 + +:(before "End Globals") +const int Reserved_for_tests = 1000; +int Memory_allocated_until = Reserved_for_tests; +int Initial_memory_per_routine = 100000; +:(before "End Setup") +Memory_allocated_until = Reserved_for_tests; +Initial_memory_per_routine = 100000; +:(before "End routine Fields") +int alloc, alloc_max; +:(before "End routine Constructor") +alloc = Memory_allocated_until; +Memory_allocated_until += Initial_memory_per_routine; +alloc_max = Memory_allocated_until; +trace(9999, "new") << "routine allocated memory from " << alloc << " to " << alloc_max << end(); + +//:: 'new' takes a weird 'type' as its first ingredient; don't error on it +:(before "End Mu Types Initialization") +put(Type_ordinal, "type", 0); + +//:: typecheck 'new' instructions +:(before "End Primitive Recipe Declarations") +NEW, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "new", NEW); +:(before "End Primitive Recipe Checks") +case NEW: { + const recipe& caller = get(Recipe, r); + if (inst.ingredients.empty() || SIZE(inst.ingredients) > 2) { + raise << maybe(caller.name) << "'new' requires one or two ingredients, but got " << to_original_string(inst) << '\n' << end(); + break; + } + // End NEW Check Special-cases + reagent type = inst.ingredients.at(0); + if (!is_mu_type_literal(type)) { + raise << maybe(caller.name) << "first ingredient of 'new' should be a type, but got " << type.original_string << '\n' << end(); + break; + } + if (inst.products.empty()) { + raise << maybe(caller.name) << "result of 'new' should never be ignored\n" << end(); + break; + } + if (!product_of_new_is_valid(inst)) { + raise << maybe(caller.name) << "product of 'new' has incorrect type: " << to_original_string(inst) << '\n' << end(); + break; + } + break; +} +:(code) +bool product_of_new_is_valid(const instruction& inst) { + reagent product = inst.products.at(0); + canonize_type(product); + if (!product.type || product.type->value != get(Type_ordinal, "address")) return false; + drop_from_type(product, "address"); + if (!product.type || product.type->value != get(Type_ordinal, "shared")) return false; + drop_from_type(product, "shared"); + if (SIZE(inst.ingredients) > 1) { + // array allocation + if (!product.type || product.type->value != get(Type_ordinal, "array")) return false; + drop_from_type(product, "array"); + } + reagent expected_product("x:"+inst.ingredients.at(0).name); + // End Post-processing(expected_product) When Checking 'new' + return types_strictly_match(product, expected_product); +} + +//:: translate 'new' to 'allocate' instructions that take a size instead of a type +:(after "Transform.push_back(check_instruction)") // check_instruction will guard against direct 'allocate' instructions below +Transform.push_back(transform_new_to_allocate); // idempotent + +:(code) +void transform_new_to_allocate(const recipe_ordinal r) { + trace(9991, "transform") << "--- convert 'new' to 'allocate' for recipe " << get(Recipe, r).name << end(); + for (int i = 0; i < SIZE(get(Recipe, r).steps); ++i) { + instruction& inst = get(Recipe, r).steps.at(i); + // Convert 'new' To 'allocate' + if (inst.name == "new") { + inst.operation = ALLOCATE; + string_tree* type_name = new string_tree(inst.ingredients.at(0).name); + // End Post-processing(type_name) When Converting 'new' + type_tree* type = new_type_tree(type_name); + inst.ingredients.at(0).set_value(size_of(type)); + trace(9992, "new") << "size of " << to_string(type_name) << " is " << inst.ingredients.at(0).value << end(); + delete type; + delete type_name; + } + } +} + +//:: implement 'allocate' based on size + +:(before "End Primitive Recipe Declarations") +ALLOCATE, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "allocate", ALLOCATE); +:(before "End Primitive Recipe Implementations") +case ALLOCATE: { + // compute the space we need + int size = ingredients.at(0).at(0); + if (SIZE(ingredients) > 1) { + // array + trace(9999, "mem") << "array size is " << ingredients.at(1).at(0) << end(); + size = /*space for length*/1 + size*ingredients.at(1).at(0); + } + // include space for refcount + size++; + trace(9999, "mem") << "allocating size " << size << end(); +//? Total_alloc += size; +//? Num_alloc++; + // compute the region of memory to return + // really crappy at the moment + ensure_space(size); + const int result = Current_routine->alloc; + trace(9999, "mem") << "new alloc: " << result << end(); + // save result + products.resize(1); + products.at(0).push_back(result); + // initialize allocated space + for (int address = result; address < result+size; ++address) + put(Memory, address, 0); + // initialize array length + if (SIZE(current_instruction().ingredients) > 1) { + trace(9999, "mem") << "storing " << ingredients.at(1).at(0) << " in location " << result+/*skip refcount*/1 << end(); + put(Memory, result+/*skip refcount*/1, ingredients.at(1).at(0)); + } + // bump + Current_routine->alloc += size; + // no support for reclaiming memory + assert(Current_routine->alloc <= Current_routine->alloc_max); + break; +} + +//:: ensure we never call 'allocate' directly; its types are not checked +:(before "End Primitive Recipe Checks") +case ALLOCATE: { + raise << "never call 'allocate' directly'; always use 'new'\n" << end(); + break; +} + +//:: ensure we never call 'new' without translating it (unless we add special-cases later) +:(before "End Primitive Recipe Implementations") +case NEW: { + raise << "no implementation for 'new'; why wasn't it translated to 'allocate'? Please save a copy of your program and send it to Kartik.\n" << end(); + break; +} + +//? :(before "End Globals") +//? int Total_alloc = 0; +//? int Num_alloc = 0; +//? int Total_free = 0; +//? int Num_free = 0; +//? :(before "End Setup") +//? Total_alloc = Num_alloc = Total_free = Num_free = 0; +//? :(before "End Teardown") +//? cerr << Total_alloc << "/" << Num_alloc +//? << " vs " << Total_free << "/" << Num_free << '\n'; +//? cerr << SIZE(Memory) << '\n'; + +:(code) +void ensure_space(int size) { + if (size > Initial_memory_per_routine) { + tb_shutdown(); + cerr << "can't allocate " << size << " locations, that's too much compared to " << Initial_memory_per_routine << ".\n"; + exit(0); + } + if (Current_routine->alloc + size > Current_routine->alloc_max) { + // waste the remaining space and create a new chunk + Current_routine->alloc = Memory_allocated_until; + Memory_allocated_until += Initial_memory_per_routine; + Current_routine->alloc_max = Memory_allocated_until; + trace(9999, "new") << "routine allocated memory from " << Current_routine->alloc << " to " << Current_routine->alloc_max << end(); + } +} + +:(scenario new_initializes) +% Memory_allocated_until = 10; +% put(Memory, Memory_allocated_until, 1); +def main [ + 1:address:shared:number <- new number:type + 2:number <- copy *1:address:shared:number +] ++mem: storing 0 in location 2 + +:(scenario new_error) +% Hide_errors = true; +def main [ + 1:address:number/raw <- new number:type +] ++error: main: product of 'new' has incorrect type: 1:address:number/raw <- new number:type + +:(scenario new_array) +def main [ + 1:address:shared:array:number/raw <- new number:type, 5 + 2:address:shared:number/raw <- new number:type + 3:number/raw <- subtract 2:address:shared:number/raw, 1:address:shared:array:number/raw +] ++run: {1: ("address" "shared" "array" "number"), "raw": ()} <- new {number: "type"}, {5: "literal"} ++mem: array size is 5 +# don't forget the extra location for array size, and the second extra location for the refcount ++mem: storing 7 in location 3 + +:(scenario new_empty_array) +def main [ + 1:address:shared:array:number/raw <- new number:type, 0 + 2:address:shared:number/raw <- new number:type + 3:number/raw <- subtract 2:address:shared:number/raw, 1:address:shared:array:number/raw +] ++run: {1: ("address" "shared" "array" "number"), "raw": ()} <- new {number: "type"}, {0: "literal"} ++mem: array size is 0 +# one location for array size, and one for the refcount ++mem: storing 2 in location 3 + +//: If a routine runs out of its initial allocation, it should allocate more. +:(scenario new_overflow) +% Initial_memory_per_routine = 3; // barely enough room for point allocation below +def main [ + 1:address:shared:number/raw <- new number:type + 2:address:shared:point/raw <- new point:type # not enough room in initial page +] ++new: routine allocated memory from 1000 to 1003 ++new: routine allocated memory from 1003 to 1006 + +//:: A way to return memory, and to reuse reclaimed memory. +//: todo: custodians, etc. Following malloc/free is a temporary hack. + +:(scenario new_reclaim) +def main [ + 1:address:shared:number <- new number:type + 2:address:shared:number <- copy 1:address:shared:number # because 1 will get reset during abandon below + abandon 1:address:shared:number # unsafe + 3:address:shared:number <- new number:type # must be same size as abandoned memory to reuse + 4:boolean <- equal 2:address:shared:number, 3:address:shared:number +] +# both allocations should have returned the same address ++mem: storing 1 in location 4 + +:(before "End routine Fields") +map free_list; + +:(before "End Primitive Recipe Declarations") +ABANDON, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "abandon", ABANDON); +:(before "End Primitive Recipe Checks") +case ABANDON: { + if (SIZE(inst.ingredients) != 1) { + raise << maybe(get(Recipe, r).name) << "'abandon' requires one ingredient, but got '" << to_original_string(inst) << "'\n" << end(); + break; + } + reagent types = inst.ingredients.at(0); + canonize_type(types); + if (!types.type || types.type->value != get(Type_ordinal, "address") || types.type->right->value != get(Type_ordinal, "shared")) { + raise << maybe(get(Recipe, r).name) << "first ingredient of 'abandon' should be an address:shared:___, but got " << inst.ingredients.at(0).original_string << '\n' << end(); + break; + } + break; +} +:(before "End Primitive Recipe Implementations") +case ABANDON: { + int address = ingredients.at(0).at(0); + trace(9999, "abandon") << "address to abandon is " << address << end(); + reagent types = current_instruction().ingredients.at(0); + trace(9999, "abandon") << "value of ingredient is " << types.value << end(); + canonize(types); + // lookup_memory without drop_one_lookup { + trace(9999, "abandon") << "value of ingredient after canonization is " << types.value << end(); + int address_location = types.value; + types.set_value(get_or_insert(Memory, types.value)+/*skip refcount*/1); + drop_from_type(types, "address"); + drop_from_type(types, "shared"); + // } + abandon(address, size_of(types)+/*refcount*/1); + // clear the address + trace(9999, "mem") << "resetting location " << address_location << end(); + put(Memory, address_location, 0); + break; +} + +:(code) +void abandon(int address, int size) { + trace(9999, "abandon") << "saving in free-list of size " << size << end(); +//? Total_free += size; +//? Num_free++; +//? cerr << "abandon: " << size << '\n'; + // clear memory + for (int curr = address; curr < address+size; ++curr) + put(Memory, curr, 0); + // append existing free list to address + put(Memory, address, get_or_insert(Current_routine->free_list, size)); + put(Current_routine->free_list, size, address); +} + +:(before "ensure_space(size)" following "case ALLOCATE") +if (get_or_insert(Current_routine->free_list, size)) { + trace(9999, "abandon") << "picking up space from free-list of size " << size << end(); + int result = get_or_insert(Current_routine->free_list, size); + trace(9999, "mem") << "new alloc from free list: " << result << end(); + put(Current_routine->free_list, size, get_or_insert(Memory, result)); + for (int curr = result+1; curr < result+size; ++curr) { + if (get_or_insert(Memory, curr) != 0) { + raise << maybe(current_recipe_name()) << "memory in free list was not zeroed out: " << curr << '/' << result << "; somebody wrote to us after free!!!\n" << end(); + break; // always fatal + } + } + if (SIZE(current_instruction().ingredients) > 1) + put(Memory, result+/*skip refcount*/1, ingredients.at(1).at(0)); + else + put(Memory, result, 0); + products.resize(1); + products.at(0).push_back(result); + break; +} + +:(scenario new_differing_size_no_reclaim) +def main [ + 1:address:shared:number <- new number:type + 2:address:shared:number <- copy 1:address:shared:number + abandon 1:address:shared:number + 3:address:shared:array:number <- new number:type, 2 # different size + 4:boolean <- equal 2:address:shared:number, 3:address:shared:array:number +] +# no reuse ++mem: storing 0 in location 4 + +:(scenario new_reclaim_array) +def main [ + 1:address:shared:array:number <- new number:type, 2 + 2:address:shared:array:number <- copy 1:address:shared:array:number + abandon 1:address:shared:array:number # unsafe + 3:address:shared:array:number <- new number:type, 2 + 4:boolean <- equal 2:address:shared:array:number, 3:address:shared:array:number +] +# reuse ++mem: storing 1 in location 4 + +:(scenario reset_on_abandon) +def main [ + 1:address:shared:number <- new number:type + abandon 1:address:shared:number +] +# reuse ++run: abandon {1: ("address" "shared" "number")} ++mem: resetting location 1 + +//:: Manage refcounts when copying addresses. + +:(scenario refcounts) +def main [ + 1:address:shared:number <- copy 1000/unsafe + 2:address:shared:number <- copy 1:address:shared:number + 1:address:shared:number <- copy 0 + 2:address:shared:number <- copy 0 +] ++run: {1: ("address" "shared" "number")} <- copy {1000: "literal", "unsafe": ()} ++mem: incrementing refcount of 1000: 0 -> 1 ++run: {2: ("address" "shared" "number")} <- copy {1: ("address" "shared" "number")} ++mem: incrementing refcount of 1000: 1 -> 2 ++run: {1: ("address" "shared" "number")} <- copy {0: "literal"} ++mem: decrementing refcount of 1000: 2 -> 1 ++run: {2: ("address" "shared" "number")} <- copy {0: "literal"} ++mem: decrementing refcount of 1000: 1 -> 0 +# the /unsafe corrupts memory but fortunately we won't be running any more 'new' in this scenario ++mem: automatically abandoning 1000 + +:(before "End write_memory(reagent x) Special-cases") +if (x.type->value == get(Type_ordinal, "address") + && x.type->right + && x.type->right->value == get(Type_ordinal, "shared")) { + // compute old address of x, as well as new address we want to write in + int old_address = get_or_insert(Memory, x.value); + assert(scalar(data)); + int new_address = data.at(0); + // decrement refcount of old address + if (old_address) { + int old_refcount = get_or_insert(Memory, old_address); + trace(9999, "mem") << "decrementing refcount of " << old_address << ": " << old_refcount << " -> " << (old_refcount-1) << end(); + put(Memory, old_address, old_refcount-1); + } + // perform the write + trace(9999, "mem") << "storing " << no_scientific(data.at(0)) << " in location " << x.value << end(); + put(Memory, x.value, new_address); + // increment refcount of new address + if (new_address) { + int new_refcount = get_or_insert(Memory, new_address); + assert(new_refcount >= 0); // == 0 only when new_address == old_address + trace(9999, "mem") << "incrementing refcount of " << new_address << ": " << new_refcount << " -> " << (new_refcount+1) << end(); + put(Memory, new_address, new_refcount+1); + } + // abandon old address if necessary + // do this after all refcount updates are done just in case old and new are identical + assert(old_address >= 0); + if (old_address == 0) return; + assert(get_or_insert(Memory, old_address) >= 0); + if (get_or_insert(Memory, old_address) > 0) return; + // lookup_memory without drop_one_lookup { + trace(9999, "mem") << "automatically abandoning " << old_address << end(); + trace(9999, "mem") << "computing size to abandon at " << x.value << end(); + x.set_value(old_address+/*skip refcount*/1); + drop_from_type(x, "address"); + drop_from_type(x, "shared"); + // } + abandon(old_address, size_of(x)+/*refcount*/1); + return; +} + +:(scenario refcounts_2) +def main [ + 1:address:shared:number <- new number:type + # over-writing one allocation with another + 1:address:shared:number <- new number:type + 1:address:shared:number <- copy 0 +] ++run: {1: ("address" "shared" "number")} <- new {number: "type"} ++mem: incrementing refcount of 1000: 0 -> 1 ++run: {1: ("address" "shared" "number")} <- new {number: "type"} ++mem: automatically abandoning 1000 + +:(scenario refcounts_3) +def main [ + 1:address:shared:number <- new number:type + # passing in addresses to recipes increments refcount + foo 1:address:shared:number + 1:address:shared:number <- copy 0 +] +def foo [ + 2:address:shared:number <- next-ingredient + # return does NOT yet decrement refcount; memory must be explicitly managed + 2:address:shared:number <- copy 0 +] ++run: {1: ("address" "shared" "number")} <- new {number: "type"} ++mem: incrementing refcount of 1000: 0 -> 1 ++run: {2: ("address" "shared" "number")} <- next-ingredient ++mem: incrementing refcount of 1000: 1 -> 2 ++run: {2: ("address" "shared" "number")} <- copy {0: "literal"} ++mem: decrementing refcount of 1000: 2 -> 1 ++run: {1: ("address" "shared" "number")} <- copy {0: "literal"} ++mem: decrementing refcount of 1000: 1 -> 0 ++mem: automatically abandoning 1000 + +:(scenario refcounts_4) +def main [ + 1:address:shared:number <- new number:type + # idempotent copies leave refcount unchanged + 1:address:shared:number <- copy 1:address:shared:number +] ++run: {1: ("address" "shared" "number")} <- new {number: "type"} ++mem: incrementing refcount of 1000: 0 -> 1 ++run: {1: ("address" "shared" "number")} <- copy {1: ("address" "shared" "number")} ++mem: decrementing refcount of 1000: 1 -> 0 ++mem: incrementing refcount of 1000: 0 -> 1 + +:(scenario refcounts_5) +def main [ + 1:address:shared:number <- new number:type + # passing in addresses to recipes increments refcount + foo 1:address:shared:number + # return does NOT yet decrement refcount; memory must be explicitly managed + 1:address:shared:number <- new number:type +] +def foo [ + 2:address:shared:number <- next-ingredient +] ++run: {1: ("address" "shared" "number")} <- new {number: "type"} ++mem: incrementing refcount of 1000: 0 -> 1 ++run: {2: ("address" "shared" "number")} <- next-ingredient ++mem: incrementing refcount of 1000: 1 -> 2 ++run: {1: ("address" "shared" "number")} <- new {number: "type"} ++mem: decrementing refcount of 1000: 2 -> 1 + +:(scenario refcounts_array) +def main [ + 1:number <- copy 30 + # allocate an array + 10:address:shared:array:number <- new number:type, 20 + 11:number <- copy 10:address:shared:array:number + # allocate another array in its place, implicitly freeing the previous allocation + 10:address:shared:array:number <- new number:type, 25 +] ++run: {10: ("address" "shared" "array" "number")} <- new {number: "type"}, {20: "literal"} +# abandoned array is of old size (20, not 25) ++abandon: saving in free-list of size 22 + +//:: Extend 'new' to handle a unicode string literal argument. + +:(scenario new_string) +def main [ + 1:address:shared:array:character <- new [abc def] + 2:character <- index *1:address:shared:array:character, 5 +] +# number code for 'e' ++mem: storing 101 in location 2 + +:(scenario new_string_handles_unicode) +def main [ + 1:address:shared:array:character <- new [a«c] + 2:number <- length *1:address:shared:array:character + 3:character <- index *1:address:shared:array:character, 1 +] ++mem: storing 3 in location 2 +# unicode for '«' ++mem: storing 171 in location 3 + +:(before "End NEW Check Special-cases") +if (is_literal_string(inst.ingredients.at(0))) break; +:(before "Convert 'new' To 'allocate'") +if (inst.name == "new" && is_literal_string(inst.ingredients.at(0))) continue; +:(after "case NEW" following "Primitive Recipe Implementations") + if (is_literal_string(current_instruction().ingredients.at(0))) { + products.resize(1); + products.at(0).push_back(new_mu_string(current_instruction().ingredients.at(0).name)); + trace(9999, "mem") << "new string alloc: " << products.at(0).at(0) << end(); + break; + } + +:(code) +int new_mu_string(const string& contents) { + // allocate an array just large enough for it + int string_length = unicode_length(contents); +//? Total_alloc += string_length+1; +//? Num_alloc++; + ensure_space(string_length+1); // don't forget the extra location for array size + // initialize string + int result = Current_routine->alloc; + // initialize refcount + put(Memory, Current_routine->alloc++, 0); + // store length + put(Memory, Current_routine->alloc++, string_length); + int curr = 0; + const char* raw_contents = contents.c_str(); + for (int i = 0; i < string_length; ++i) { + uint32_t curr_character; + assert(curr < SIZE(contents)); + tb_utf8_char_to_unicode(&curr_character, &raw_contents[curr]); + put(Memory, Current_routine->alloc, curr_character); + curr += tb_utf8_char_length(raw_contents[curr]); + ++Current_routine->alloc; + } + // mu strings are not null-terminated in memory + return result; +} + +//: stash recognizes strings + +:(scenario stash_string) +def main [ + 1:address:shared:array:character <- new [abc] + stash [foo:], 1:address:shared:array:character +] ++app: foo: abc + +:(before "End print Special-cases(reagent r, data)") +if (is_mu_string(r)) { + assert(scalar(data)); + return read_mu_string(data.at(0))+' '; +} + +:(scenario unicode_string) +def main [ + 1:address:shared:array:character <- new [♠] + stash [foo:], 1:address:shared:array:character +] ++app: foo: ♠ + +:(scenario stash_space_after_string) +def main [ + 1:address:shared:array:character <- new [abc] + stash 1:address:shared:array:character, [foo] +] ++app: abc foo + +//: Allocate more to routine when initializing a literal string +:(scenario new_string_overflow) +% Initial_memory_per_routine = 2; +def main [ + 1:address:shared:number/raw <- new number:type + 2:address:shared:array:character/raw <- new [a] # not enough room in initial page, if you take the array size into account +] ++new: routine allocated memory from 1000 to 1002 ++new: routine allocated memory from 1002 to 1004 + +//: helpers +:(code) +int unicode_length(const string& s) { + const char* in = s.c_str(); + int result = 0; + int curr = 0; + while (curr < SIZE(s)) { // carefully bounds-check on the string + // before accessing its raw pointer + ++result; + curr += tb_utf8_char_length(in[curr]); + } + return result; +} + +string read_mu_string(int address) { + if (address == 0) return ""; + address++; // skip refcount + int size = get_or_insert(Memory, address); + if (size == 0) return ""; + ostringstream tmp; + for (int curr = address+1; curr <= address+size; ++curr) { + tmp << to_unicode(static_cast(get_or_insert(Memory, curr))); + } + return tmp.str(); +} + +bool is_mu_type_literal(reagent r) { + return is_literal(r) && r.type && r.type->name == "type"; +} diff --git a/035location_array.cc b/035location_array.cc new file mode 100644 index 00000000..86cf8e97 --- /dev/null +++ b/035location_array.cc @@ -0,0 +1,42 @@ +:(before "End Primitive Recipe Declarations") +TO_LOCATION_ARRAY, +:(before "End Primitive Recipe Numbers") +put(Recipe_ordinal, "to-location-array", TO_LOCATION_ARRAY); +:(before "End Primitive Recipe Checks") +case TO_LOCATION_ARRAY: { + const recipe& caller = get(Recipe, r); + if (!is_shared_address_of_array_of_numbers(inst.products.at(0))) { + raise << maybe(caller.name) << "product of 'to-location-array' has incorrect type: " << to_original_string(inst) << '\n' << end(); + break; + } + break; +} +:(code) +bool is_shared_address_of_array_of_numbers(reagent product) { + canonize_type(product); + if (!product.type || product.type->value != get(Type_ordinal, "address")) return false; + drop_from_type(product, "address"); + if (!product.type || product.type->value != get(Type_ordinal, "shared")) return false; + drop_from_type(product, "shared"); + if (!product.type || product.type->value != get(Type_ordinal, "array")) return false; + drop_from_type(product, "array"); + if (!product.type || product.type->value != get(Type_ordinal, "number")) return false; + return true; +} +:(before "End Primitive Recipe Implementations") +case TO_LOCATION_ARRAY: { + int array_size = SIZE(ingredients.at(0)); + int allocation_size = array_size + /*refcount*/1 + /*length*/1; + ensure_space(allocation_size); + const int result = Current_routine->alloc; + products.resize(1); + products.at(0).push_back(result); + // initialize array refcount + put(Memory, result, 0); + // initialize array length + put(Memory, result+1, array_size); + // now copy over data + for (int i = 0; i < array_size; ++i) + put(Memory, result+2+i, ingredients.at(0).at(i)); + break; +} diff --git a/037new.cc b/037new.cc deleted file mode 100644 index ec30fee1..00000000 --- a/037new.cc +++ /dev/null @@ -1,686 +0,0 @@ -//: Creating space for new variables at runtime. - -//: Mu has two primitives for managing allocations: -//: - 'allocate' reserves a specified amount of space -//: - 'abandon' returns allocated space to be reused by future calls to 'allocate' -//: -//: In practice it's useful to let programs copy addresses anywhere they want, -//: but a prime source of (particularly security) bugs is accessing memory -//: after it's been abandoned. To avoid this, mu programs use a safer -//: primitive called 'new', which adds two features: -//: -//: - it takes a type rather than a size, to save you the trouble of -//: calculating sizes of different variables. -//: - it allocates an extra location where it tracks so-called 'reference -//: counts' or refcounts: the number of address variables in your program that -//: point to this allocation. The initial refcount of an allocation starts out -//: at 1 (the product of the 'new' instruction). When other variables are -//: copied from it the refcount is incremented. When a variable stops pointing -//: at it the refcount is decremented. When the refcount goes to 0 the -//: allocation is automatically abandoned. -//: -//: Mu programs guarantee you'll have no memory corruption bugs as long as you -//: use 'new' and never use 'allocate' or 'abandon'. However, they don't help -//: you at all to remember to abandon memory after you're done with it. To -//: minimize memory use, be sure to reset allocated addresses to 0 when you're -//: done with them. - -//: interlude { -//: To help you distinguish addresses that point at allocations, 'new' returns -//: type address:shared:___. Think of 'shared' as a generic container that -//: contains one extra field: the refcount. However, lookup operations will -//: transparently drop the 'shared' and access to the refcount. Copying -//: between shared and non-shared addresses is forbidden. -:(before "End Mu Types Initialization") -type_ordinal shared = put(Type_ordinal, "shared", Next_type_ordinal++); -get_or_insert(Type, shared).name = "shared"; -:(before "End Drop Address In lookup_memory(x)") -if (x.type->name == "shared" && x.value != 0) { - trace(9999, "mem") << "skipping refcount at " << x.value << end(); - x.set_value(x.value+1); // skip refcount - drop_from_type(x, "shared"); -} -:(before "End Drop Address In canonize_type(r)") -if (r.type->name == "shared") { - drop_from_type(r, "shared"); -} - -:(code) -void test_lookup_shared_address() { - reagent x("*x:address:shared:number"); - x.set_value(34); // unsafe - put(Memory, 34, 1000); - lookup_memory(x); - CHECK_TRACE_CONTENTS("mem: skipping refcount at 1000"); - CHECK_EQ(x.value, 1001); -} - -void test_lookup_shared_address_skip_zero() { - reagent x("*x:address:shared:number"); - x.set_value(34); // unsafe - put(Memory, 34, 0); - lookup_memory(x); - CHECK_TRACE_DOESNT_CONTAIN("mem: skipping refcount at 0"); - CHECK_EQ(x.value, 0); -} - -//: } end interlude - -:(scenarios run) -:(scenario new) -# call new two times with identical arguments; you should get back different results -def main [ - 1:address:shared:number/raw <- new number:type - 2:address:shared:number/raw <- new number:type - 3:boolean/raw <- equal 1:address:shared:number/raw, 2:address:shared:number/raw -] -+mem: storing 0 in location 3 - -:(before "End Globals") -const int Reserved_for_tests = 1000; -int Memory_allocated_until = Reserved_for_tests; -int Initial_memory_per_routine = 100000; -:(before "End Setup") -Memory_allocated_until = Reserved_for_tests; -Initial_memory_per_routine = 100000; -:(before "End routine Fields") -int alloc, alloc_max; -:(before "End routine Constructor") -alloc = Memory_allocated_until; -Memory_allocated_until += Initial_memory_per_routine; -alloc_max = Memory_allocated_until; -trace(9999, "new") << "routine allocated memory from " << alloc << " to " << alloc_max << end(); - -//:: 'new' takes a weird 'type' as its first ingredient; don't error on it -:(before "End Mu Types Initialization") -put(Type_ordinal, "type", 0); - -//:: typecheck 'new' instructions -:(before "End Primitive Recipe Declarations") -NEW, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "new", NEW); -:(before "End Primitive Recipe Checks") -case NEW: { - const recipe& caller = get(Recipe, r); - if (inst.ingredients.empty() || SIZE(inst.ingredients) > 2) { - raise << maybe(caller.name) << "'new' requires one or two ingredients, but got " << to_original_string(inst) << '\n' << end(); - break; - } - // End NEW Check Special-cases - reagent type = inst.ingredients.at(0); - if (!is_mu_type_literal(type)) { - raise << maybe(caller.name) << "first ingredient of 'new' should be a type, but got " << type.original_string << '\n' << end(); - break; - } - if (inst.products.empty()) { - raise << maybe(caller.name) << "result of 'new' should never be ignored\n" << end(); - break; - } - if (!product_of_new_is_valid(inst)) { - raise << maybe(caller.name) << "product of 'new' has incorrect type: " << to_original_string(inst) << '\n' << end(); - break; - } - break; -} -:(code) -bool product_of_new_is_valid(const instruction& inst) { - reagent product = inst.products.at(0); - canonize_type(product); - if (!product.type || product.type->value != get(Type_ordinal, "address")) return false; - drop_from_type(product, "address"); - if (!product.type || product.type->value != get(Type_ordinal, "shared")) return false; - drop_from_type(product, "shared"); - if (SIZE(inst.ingredients) > 1) { - // array allocation - if (!product.type || product.type->value != get(Type_ordinal, "array")) return false; - drop_from_type(product, "array"); - } - reagent expected_product("x:"+inst.ingredients.at(0).name); - // End Post-processing(expected_product) When Checking 'new' - return types_strictly_match(product, expected_product); -} - -//:: translate 'new' to 'allocate' instructions that take a size instead of a type -:(after "Transform.push_back(check_instruction)") // check_instruction will guard against direct 'allocate' instructions below -Transform.push_back(transform_new_to_allocate); // idempotent - -:(code) -void transform_new_to_allocate(const recipe_ordinal r) { - trace(9991, "transform") << "--- convert 'new' to 'allocate' for recipe " << get(Recipe, r).name << end(); - for (int i = 0; i < SIZE(get(Recipe, r).steps); ++i) { - instruction& inst = get(Recipe, r).steps.at(i); - // Convert 'new' To 'allocate' - if (inst.name == "new") { - inst.operation = ALLOCATE; - string_tree* type_name = new string_tree(inst.ingredients.at(0).name); - // End Post-processing(type_name) When Converting 'new' - type_tree* type = new_type_tree(type_name); - inst.ingredients.at(0).set_value(size_of(type)); - trace(9992, "new") << "size of " << to_string(type_name) << " is " << inst.ingredients.at(0).value << end(); - delete type; - delete type_name; - } - } -} - -//:: implement 'allocate' based on size - -:(before "End Primitive Recipe Declarations") -ALLOCATE, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "allocate", ALLOCATE); -:(before "End Primitive Recipe Implementations") -case ALLOCATE: { - // compute the space we need - int size = ingredients.at(0).at(0); - if (SIZE(ingredients) > 1) { - // array - trace(9999, "mem") << "array size is " << ingredients.at(1).at(0) << end(); - size = /*space for length*/1 + size*ingredients.at(1).at(0); - } - // include space for refcount - size++; - trace(9999, "mem") << "allocating size " << size << end(); -//? Total_alloc += size; -//? Num_alloc++; - // compute the region of memory to return - // really crappy at the moment - ensure_space(size); - const int result = Current_routine->alloc; - trace(9999, "mem") << "new alloc: " << result << end(); - // save result - products.resize(1); - products.at(0).push_back(result); - // initialize allocated space - for (int address = result; address < result+size; ++address) - put(Memory, address, 0); - // initialize array length - if (SIZE(current_instruction().ingredients) > 1) { - trace(9999, "mem") << "storing " << ingredients.at(1).at(0) << " in location " << result+/*skip refcount*/1 << end(); - put(Memory, result+/*skip refcount*/1, ingredients.at(1).at(0)); - } - // bump - Current_routine->alloc += size; - // no support for reclaiming memory - assert(Current_routine->alloc <= Current_routine->alloc_max); - break; -} - -//:: ensure we never call 'allocate' directly; its types are not checked -:(before "End Primitive Recipe Checks") -case ALLOCATE: { - raise << "never call 'allocate' directly'; always use 'new'\n" << end(); - break; -} - -//:: ensure we never call 'new' without translating it (unless we add special-cases later) -:(before "End Primitive Recipe Implementations") -case NEW: { - raise << "no implementation for 'new'; why wasn't it translated to 'allocate'? Please save a copy of your program and send it to Kartik.\n" << end(); - break; -} - -//? :(before "End Globals") -//? int Total_alloc = 0; -//? int Num_alloc = 0; -//? int Total_free = 0; -//? int Num_free = 0; -//? :(before "End Setup") -//? Total_alloc = Num_alloc = Total_free = Num_free = 0; -//? :(before "End Teardown") -//? cerr << Total_alloc << "/" << Num_alloc -//? << " vs " << Total_free << "/" << Num_free << '\n'; -//? cerr << SIZE(Memory) << '\n'; - -:(code) -void ensure_space(int size) { - if (size > Initial_memory_per_routine) { - tb_shutdown(); - cerr << "can't allocate " << size << " locations, that's too much compared to " << Initial_memory_per_routine << ".\n"; - exit(0); - } - if (Current_routine->alloc + size > Current_routine->alloc_max) { - // waste the remaining space and create a new chunk - Current_routine->alloc = Memory_allocated_until; - Memory_allocated_until += Initial_memory_per_routine; - Current_routine->alloc_max = Memory_allocated_until; - trace(9999, "new") << "routine allocated memory from " << Current_routine->alloc << " to " << Current_routine->alloc_max << end(); - } -} - -:(scenario new_initializes) -% Memory_allocated_until = 10; -% put(Memory, Memory_allocated_until, 1); -def main [ - 1:address:shared:number <- new number:type - 2:number <- copy *1:address:shared:number -] -+mem: storing 0 in location 2 - -:(scenario new_error) -% Hide_errors = true; -def main [ - 1:address:number/raw <- new number:type -] -+error: main: product of 'new' has incorrect type: 1:address:number/raw <- new number:type - -:(scenario new_array) -def main [ - 1:address:shared:array:number/raw <- new number:type, 5 - 2:address:shared:number/raw <- new number:type - 3:number/raw <- subtract 2:address:shared:number/raw, 1:address:shared:array:number/raw -] -+run: {1: ("address" "shared" "array" "number"), "raw": ()} <- new {number: "type"}, {5: "literal"} -+mem: array size is 5 -# don't forget the extra location for array size, and the second extra location for the refcount -+mem: storing 7 in location 3 - -:(scenario new_empty_array) -def main [ - 1:address:shared:array:number/raw <- new number:type, 0 - 2:address:shared:number/raw <- new number:type - 3:number/raw <- subtract 2:address:shared:number/raw, 1:address:shared:array:number/raw -] -+run: {1: ("address" "shared" "array" "number"), "raw": ()} <- new {number: "type"}, {0: "literal"} -+mem: array size is 0 -# one location for array size, and one for the refcount -+mem: storing 2 in location 3 - -//: If a routine runs out of its initial allocation, it should allocate more. -:(scenario new_overflow) -% Initial_memory_per_routine = 3; // barely enough room for point allocation below -def main [ - 1:address:shared:number/raw <- new number:type - 2:address:shared:point/raw <- new point:type # not enough room in initial page -] -+new: routine allocated memory from 1000 to 1003 -+new: routine allocated memory from 1003 to 1006 - -//:: A way to return memory, and to reuse reclaimed memory. -//: todo: custodians, etc. Following malloc/free is a temporary hack. - -:(scenario new_reclaim) -def main [ - 1:address:shared:number <- new number:type - 2:address:shared:number <- copy 1:address:shared:number # because 1 will get reset during abandon below - abandon 1:address:shared:number # unsafe - 3:address:shared:number <- new number:type # must be same size as abandoned memory to reuse - 4:boolean <- equal 2:address:shared:number, 3:address:shared:number -] -# both allocations should have returned the same address -+mem: storing 1 in location 4 - -:(before "End routine Fields") -map free_list; - -:(before "End Primitive Recipe Declarations") -ABANDON, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "abandon", ABANDON); -:(before "End Primitive Recipe Checks") -case ABANDON: { - if (SIZE(inst.ingredients) != 1) { - raise << maybe(get(Recipe, r).name) << "'abandon' requires one ingredient, but got '" << to_original_string(inst) << "'\n" << end(); - break; - } - reagent types = inst.ingredients.at(0); - canonize_type(types); - if (!types.type || types.type->value != get(Type_ordinal, "address") || types.type->right->value != get(Type_ordinal, "shared")) { - raise << maybe(get(Recipe, r).name) << "first ingredient of 'abandon' should be an address:shared:___, but got " << inst.ingredients.at(0).original_string << '\n' << end(); - break; - } - break; -} -:(before "End Primitive Recipe Implementations") -case ABANDON: { - int address = ingredients.at(0).at(0); - trace(9999, "abandon") << "address to abandon is " << address << end(); - reagent types = current_instruction().ingredients.at(0); - trace(9999, "abandon") << "value of ingredient is " << types.value << end(); - canonize(types); - // lookup_memory without drop_one_lookup { - trace(9999, "abandon") << "value of ingredient after canonization is " << types.value << end(); - int address_location = types.value; - types.set_value(get_or_insert(Memory, types.value)+/*skip refcount*/1); - drop_from_type(types, "address"); - drop_from_type(types, "shared"); - // } - abandon(address, size_of(types)+/*refcount*/1); - // clear the address - trace(9999, "mem") << "resetting location " << address_location << end(); - put(Memory, address_location, 0); - break; -} - -:(code) -void abandon(int address, int size) { - trace(9999, "abandon") << "saving in free-list of size " << size << end(); -//? Total_free += size; -//? Num_free++; -//? cerr << "abandon: " << size << '\n'; - // clear memory - for (int curr = address; curr < address+size; ++curr) - put(Memory, curr, 0); - // append existing free list to address - put(Memory, address, get_or_insert(Current_routine->free_list, size)); - put(Current_routine->free_list, size, address); -} - -:(before "ensure_space(size)" following "case ALLOCATE") -if (get_or_insert(Current_routine->free_list, size)) { - trace(9999, "abandon") << "picking up space from free-list of size " << size << end(); - int result = get_or_insert(Current_routine->free_list, size); - trace(9999, "mem") << "new alloc from free list: " << result << end(); - put(Current_routine->free_list, size, get_or_insert(Memory, result)); - for (int curr = result+1; curr < result+size; ++curr) { - if (get_or_insert(Memory, curr) != 0) { - raise << maybe(current_recipe_name()) << "memory in free list was not zeroed out: " << curr << '/' << result << "; somebody wrote to us after free!!!\n" << end(); - break; // always fatal - } - } - if (SIZE(current_instruction().ingredients) > 1) - put(Memory, result+/*skip refcount*/1, ingredients.at(1).at(0)); - else - put(Memory, result, 0); - products.resize(1); - products.at(0).push_back(result); - break; -} - -:(scenario new_differing_size_no_reclaim) -def main [ - 1:address:shared:number <- new number:type - 2:address:shared:number <- copy 1:address:shared:number - abandon 1:address:shared:number - 3:address:shared:array:number <- new number:type, 2 # different size - 4:boolean <- equal 2:address:shared:number, 3:address:shared:array:number -] -# no reuse -+mem: storing 0 in location 4 - -:(scenario new_reclaim_array) -def main [ - 1:address:shared:array:number <- new number:type, 2 - 2:address:shared:array:number <- copy 1:address:shared:array:number - abandon 1:address:shared:array:number # unsafe - 3:address:shared:array:number <- new number:type, 2 - 4:boolean <- equal 2:address:shared:array:number, 3:address:shared:array:number -] -# reuse -+mem: storing 1 in location 4 - -:(scenario reset_on_abandon) -def main [ - 1:address:shared:number <- new number:type - abandon 1:address:shared:number -] -# reuse -+run: abandon {1: ("address" "shared" "number")} -+mem: resetting location 1 - -//:: Manage refcounts when copying addresses. - -:(scenario refcounts) -def main [ - 1:address:shared:number <- copy 1000/unsafe - 2:address:shared:number <- copy 1:address:shared:number - 1:address:shared:number <- copy 0 - 2:address:shared:number <- copy 0 -] -+run: {1: ("address" "shared" "number")} <- copy {1000: "literal", "unsafe": ()} -+mem: incrementing refcount of 1000: 0 -> 1 -+run: {2: ("address" "shared" "number")} <- copy {1: ("address" "shared" "number")} -+mem: incrementing refcount of 1000: 1 -> 2 -+run: {1: ("address" "shared" "number")} <- copy {0: "literal"} -+mem: decrementing refcount of 1000: 2 -> 1 -+run: {2: ("address" "shared" "number")} <- copy {0: "literal"} -+mem: decrementing refcount of 1000: 1 -> 0 -# the /unsafe corrupts memory but fortunately we won't be running any more 'new' in this scenario -+mem: automatically abandoning 1000 - -:(before "End write_memory(reagent x) Special-cases") -if (x.type->value == get(Type_ordinal, "address") - && x.type->right - && x.type->right->value == get(Type_ordinal, "shared")) { - // compute old address of x, as well as new address we want to write in - int old_address = get_or_insert(Memory, x.value); - assert(scalar(data)); - int new_address = data.at(0); - // decrement refcount of old address - if (old_address) { - int old_refcount = get_or_insert(Memory, old_address); - trace(9999, "mem") << "decrementing refcount of " << old_address << ": " << old_refcount << " -> " << (old_refcount-1) << end(); - put(Memory, old_address, old_refcount-1); - } - // perform the write - trace(9999, "mem") << "storing " << no_scientific(data.at(0)) << " in location " << x.value << end(); - put(Memory, x.value, new_address); - // increment refcount of new address - if (new_address) { - int new_refcount = get_or_insert(Memory, new_address); - assert(new_refcount >= 0); // == 0 only when new_address == old_address - trace(9999, "mem") << "incrementing refcount of " << new_address << ": " << new_refcount << " -> " << (new_refcount+1) << end(); - put(Memory, new_address, new_refcount+1); - } - // abandon old address if necessary - // do this after all refcount updates are done just in case old and new are identical - assert(old_address >= 0); - if (old_address == 0) return; - assert(get_or_insert(Memory, old_address) >= 0); - if (get_or_insert(Memory, old_address) > 0) return; - // lookup_memory without drop_one_lookup { - trace(9999, "mem") << "automatically abandoning " << old_address << end(); - trace(9999, "mem") << "computing size to abandon at " << x.value << end(); - x.set_value(old_address+/*skip refcount*/1); - drop_from_type(x, "address"); - drop_from_type(x, "shared"); - // } - abandon(old_address, size_of(x)+/*refcount*/1); - return; -} - -:(scenario refcounts_2) -def main [ - 1:address:shared:number <- new number:type - # over-writing one allocation with another - 1:address:shared:number <- new number:type - 1:address:shared:number <- copy 0 -] -+run: {1: ("address" "shared" "number")} <- new {number: "type"} -+mem: incrementing refcount of 1000: 0 -> 1 -+run: {1: ("address" "shared" "number")} <- new {number: "type"} -+mem: automatically abandoning 1000 - -:(scenario refcounts_3) -def main [ - 1:address:shared:number <- new number:type - # passing in addresses to recipes increments refcount - foo 1:address:shared:number - 1:address:shared:number <- copy 0 -] -def foo [ - 2:address:shared:number <- next-ingredient - # return does NOT yet decrement refcount; memory must be explicitly managed - 2:address:shared:number <- copy 0 -] -+run: {1: ("address" "shared" "number")} <- new {number: "type"} -+mem: incrementing refcount of 1000: 0 -> 1 -+run: {2: ("address" "shared" "number")} <- next-ingredient -+mem: incrementing refcount of 1000: 1 -> 2 -+run: {2: ("address" "shared" "number")} <- copy {0: "literal"} -+mem: decrementing refcount of 1000: 2 -> 1 -+run: {1: ("address" "shared" "number")} <- copy {0: "literal"} -+mem: decrementing refcount of 1000: 1 -> 0 -+mem: automatically abandoning 1000 - -:(scenario refcounts_4) -def main [ - 1:address:shared:number <- new number:type - # idempotent copies leave refcount unchanged - 1:address:shared:number <- copy 1:address:shared:number -] -+run: {1: ("address" "shared" "number")} <- new {number: "type"} -+mem: incrementing refcount of 1000: 0 -> 1 -+run: {1: ("address" "shared" "number")} <- copy {1: ("address" "shared" "number")} -+mem: decrementing refcount of 1000: 1 -> 0 -+mem: incrementing refcount of 1000: 0 -> 1 - -:(scenario refcounts_5) -def main [ - 1:address:shared:number <- new number:type - # passing in addresses to recipes increments refcount - foo 1:address:shared:number - # return does NOT yet decrement refcount; memory must be explicitly managed - 1:address:shared:number <- new number:type -] -def foo [ - 2:address:shared:number <- next-ingredient -] -+run: {1: ("address" "shared" "number")} <- new {number: "type"} -+mem: incrementing refcount of 1000: 0 -> 1 -+run: {2: ("address" "shared" "number")} <- next-ingredient -+mem: incrementing refcount of 1000: 1 -> 2 -+run: {1: ("address" "shared" "number")} <- new {number: "type"} -+mem: decrementing refcount of 1000: 2 -> 1 - -:(scenario refcounts_array) -def main [ - 1:number <- copy 30 - # allocate an array - 10:address:shared:array:number <- new number:type, 20 - 11:number <- copy 10:address:shared:array:number - # allocate another array in its place, implicitly freeing the previous allocation - 10:address:shared:array:number <- new number:type, 25 -] -+run: {10: ("address" "shared" "array" "number")} <- new {number: "type"}, {20: "literal"} -# abandoned array is of old size (20, not 25) -+abandon: saving in free-list of size 22 - -//:: Extend 'new' to handle a unicode string literal argument. - -:(scenario new_string) -def main [ - 1:address:shared:array:character <- new [abc def] - 2:character <- index *1:address:shared:array:character, 5 -] -# number code for 'e' -+mem: storing 101 in location 2 - -:(scenario new_string_handles_unicode) -def main [ - 1:address:shared:array:character <- new [a«c] - 2:number <- length *1:address:shared:array:character - 3:character <- index *1:address:shared:array:character, 1 -] -+mem: storing 3 in location 2 -# unicode for '«' -+mem: storing 171 in location 3 - -:(before "End NEW Check Special-cases") -if (is_literal_string(inst.ingredients.at(0))) break; -:(before "Convert 'new' To 'allocate'") -if (inst.name == "new" && is_literal_string(inst.ingredients.at(0))) continue; -:(after "case NEW" following "Primitive Recipe Implementations") - if (is_literal_string(current_instruction().ingredients.at(0))) { - products.resize(1); - products.at(0).push_back(new_mu_string(current_instruction().ingredients.at(0).name)); - trace(9999, "mem") << "new string alloc: " << products.at(0).at(0) << end(); - break; - } - -:(code) -int new_mu_string(const string& contents) { - // allocate an array just large enough for it - int string_length = unicode_length(contents); -//? Total_alloc += string_length+1; -//? Num_alloc++; - ensure_space(string_length+1); // don't forget the extra location for array size - // initialize string - int result = Current_routine->alloc; - // initialize refcount - put(Memory, Current_routine->alloc++, 0); - // store length - put(Memory, Current_routine->alloc++, string_length); - int curr = 0; - const char* raw_contents = contents.c_str(); - for (int i = 0; i < string_length; ++i) { - uint32_t curr_character; - assert(curr < SIZE(contents)); - tb_utf8_char_to_unicode(&curr_character, &raw_contents[curr]); - put(Memory, Current_routine->alloc, curr_character); - curr += tb_utf8_char_length(raw_contents[curr]); - ++Current_routine->alloc; - } - // mu strings are not null-terminated in memory - return result; -} - -//: stash recognizes strings - -:(scenario stash_string) -def main [ - 1:address:shared:array:character <- new [abc] - stash [foo:], 1:address:shared:array:character -] -+app: foo: abc - -:(before "End print Special-cases(reagent r, data)") -if (is_mu_string(r)) { - assert(scalar(data)); - return read_mu_string(data.at(0))+' '; -} - -:(scenario unicode_string) -def main [ - 1:address:shared:array:character <- new [♠] - stash [foo:], 1:address:shared:array:character -] -+app: foo: ♠ - -:(scenario stash_space_after_string) -def main [ - 1:address:shared:array:character <- new [abc] - stash 1:address:shared:array:character, [foo] -] -+app: abc foo - -//: Allocate more to routine when initializing a literal string -:(scenario new_string_overflow) -% Initial_memory_per_routine = 2; -def main [ - 1:address:shared:number/raw <- new number:type - 2:address:shared:array:character/raw <- new [a] # not enough room in initial page, if you take the array size into account -] -+new: routine allocated memory from 1000 to 1002 -+new: routine allocated memory from 1002 to 1004 - -//: helpers -:(code) -int unicode_length(const string& s) { - const char* in = s.c_str(); - int result = 0; - int curr = 0; - while (curr < SIZE(s)) { // carefully bounds-check on the string - // before accessing its raw pointer - ++result; - curr += tb_utf8_char_length(in[curr]); - } - return result; -} - -string read_mu_string(int address) { - if (address == 0) return ""; - address++; // skip refcount - int size = get_or_insert(Memory, address); - if (size == 0) return ""; - ostringstream tmp; - for (int curr = address+1; curr <= address+size; ++curr) { - tmp << to_unicode(static_cast(get_or_insert(Memory, curr))); - } - return tmp.str(); -} - -bool is_mu_type_literal(reagent r) { - return is_literal(r) && r.type && r.type->name == "type"; -} diff --git a/038location_array.cc b/038location_array.cc deleted file mode 100644 index 86cf8e97..00000000 --- a/038location_array.cc +++ /dev/null @@ -1,42 +0,0 @@ -:(before "End Primitive Recipe Declarations") -TO_LOCATION_ARRAY, -:(before "End Primitive Recipe Numbers") -put(Recipe_ordinal, "to-location-array", TO_LOCATION_ARRAY); -:(before "End Primitive Recipe Checks") -case TO_LOCATION_ARRAY: { - const recipe& caller = get(Recipe, r); - if (!is_shared_address_of_array_of_numbers(inst.products.at(0))) { - raise << maybe(caller.name) << "product of 'to-location-array' has incorrect type: " << to_original_string(inst) << '\n' << end(); - break; - } - break; -} -:(code) -bool is_shared_address_of_array_of_numbers(reagent product) { - canonize_type(product); - if (!product.type || product.type->value != get(Type_ordinal, "address")) return false; - drop_from_type(product, "address"); - if (!product.type || product.type->value != get(Type_ordinal, "shared")) return false; - drop_from_type(product, "shared"); - if (!product.type || product.type->value != get(Type_ordinal, "array")) return false; - drop_from_type(product, "array"); - if (!product.type || product.type->value != get(Type_ordinal, "number")) return false; - return true; -} -:(before "End Primitive Recipe Implementations") -case TO_LOCATION_ARRAY: { - int array_size = SIZE(ingredients.at(0)); - int allocation_size = array_size + /*refcount*/1 + /*length*/1; - ensure_space(allocation_size); - const int result = Current_routine->alloc; - products.resize(1); - products.at(0).push_back(result); - // initialize array refcount - put(Memory, result, 0); - // initialize array length - put(Memory, result+1, array_size); - // now copy over data - for (int i = 0; i < array_size; ++i) - put(Memory, result+2+i, ingredients.at(0).at(i)); - break; -} diff --git a/057shape_shifting_container.cc b/057shape_shifting_container.cc index acb3c7cb..40ec3521 100644 --- a/057shape_shifting_container.cc +++ b/057shape_shifting_container.cc @@ -190,9 +190,9 @@ def main [ :(before "End element_type Special-cases") if (contains_type_ingredient(element)) { - if (!canonized_base.type->right) - raise << "illegal type " << names_to_string(canonized_base.type) << " seems to be missing a type ingredient or three\n" << end(); - replace_type_ingredients(element.type, canonized_base.type->right, info); + if (!base.type->right) + raise << "illegal type " << names_to_string(base.type) << " seems to be missing a type ingredient or three\n" << end(); + replace_type_ingredients(element.type, base.type->right, info); } :(code) @@ -541,7 +541,7 @@ def main [ :(before "End variant_type Special-cases") if (contains_type_ingredient(element)) { - if (!canonized_base.type->right) - raise << "illegal type '" << to_string(canonized_base.type) << "' seems to be missing a type ingredient or three\n" << end(); - replace_type_ingredients(element.type, canonized_base.type->right, info); + 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); } -- cgit 1.4.1-2-gfad0