From 3cfa56a923e2ff96c01ba932ecc9cc4ec38e616d Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Sat, 10 Sep 2016 09:59:32 -0700 Subject: 3313 Allow type-trees to be ordered in some consistent fashion. This could be quite inefficient since we often end up comparing the four sub-trees of the two arguments in 4 different ways. So far it isn't much of a time sink. --- 010vm.cc | 83 +++++++++++++++++++++++++++++++++++++++++++++++ 030container.cc | 18 +++------- 033exclusive_container.cc | 2 +- 3 files changed, 89 insertions(+), 14 deletions(-) diff --git a/010vm.cc b/010vm.cc index e03c9128..4c8298d4 100644 --- a/010vm.cc +++ b/010vm.cc @@ -83,6 +83,10 @@ struct type_tree { // tree of type ordinals type_tree(type_tree* l, type_tree* r) :atom(false), value(0), left(l), right(r) {} type_tree& operator=(const type_tree& old); + bool operator==(const type_tree& other) const; + bool operator!=(const type_tree& other) const { return !operator==(other); } + bool operator<(const type_tree& other) const; + bool operator>(const type_tree& other) const { return other.operator<(*this); } }; struct string_tree { @@ -350,6 +354,85 @@ type_tree& type_tree::operator=(const type_tree& old) { return *this; } +bool type_tree::operator==(const type_tree& other) const { + if (atom != other.atom) return false; + if (atom) + return name == other.name && value == other.value; + return (left == other.left || *left == *other.left) + && (right == other.right || *right == *other.right); +} + +// only constraint we care about: if a < b then !(b < a) +bool type_tree::operator<(const type_tree& other) const { + if (atom != other.atom) return atom > other.atom; // atoms before non-atoms + if (atom) return name < other.name; // sort atoms in lexical order + // first location in one that's missing in the other makes that side 'smaller' + if (left && !other.left) return false; + if (!left && other.left) return true; + if (right && !other.right) return false; + if (!right && other.right) return true; + // if one side is equal that's easy + if (left == other.left || *left == *other.left) return *right < *other.right; + if (right == other.right || *right == *other.right) return *left < *other.left; + // if the two sides criss-cross, pick the side with the smaller lhs + if ((left == other.right || *left == *other.right) + && (right == other.left || *right == *other.left)) + return *left < *other.left; + // now the hard case: both sides are not equal + // make sure we stay consistent between (a < b) and (b < a) + // just return the side with the smallest of the 4 branches + if (*left < *other.left && *left < *other.right) return true; + if (*right < *other.left && *right < *other.right) return true; + return false; +} +:(before "End Unit Tests") +// These unit tests don't always use valid types. +void test_compare_atom_types() { + reagent a("a:address"), b("b:boolean"); + CHECK(*a.type < *b.type); + CHECK(!(*b.type < *a.type)); +} +void test_compare_equal_atom_types() { + reagent a("a:address"), b("b:address"); + CHECK(!(*a.type < *b.type)); + CHECK(!(*b.type < *a.type)); +} +void test_compare_atom_with_non_atom() { + reagent a("a:address:number"), b("b:boolean"); + CHECK(!(*a.type < *b.type)); + CHECK(*b.type < *a.type); +} +void test_compare_lists_with_identical_structure() { + reagent a("a:address:address"), b("b:address:boolean"); + CHECK(*a.type < *b.type); + CHECK(!(*b.type < *a.type)); +} +void test_compare_identical_lists() { + reagent a("a:address:boolean"), b("b:address:boolean"); + CHECK(!(*a.type < *b.type)); + CHECK(!(*b.type < *a.type)); +} +void test_compare_list_with_extra_element() { + reagent a("a:address:address"), b("b:address:address:number"); + CHECK(*a.type < *b.type); + CHECK(!(*b.type < *a.type)); +} +void test_compare_list_with_smaller_left_but_larger_right() { + reagent a("a:address:number"), b("b:character:array"); + assert(a.type->left->atom && a.type->right->atom); + assert(b.type->left->atom && b.type->right->atom); + CHECK(*a.type < *b.type); + CHECK(!(*b.type < *a.type)); +} +void test_compare_list_with_smaller_left_but_larger_right_identical_types() { + reagent a("a:address:boolean"), b("b:boolean:address"); + assert(a.type->left->atom && a.type->right->atom); + assert(b.type->left->atom && b.type->right->atom); + CHECK(*a.type < *b.type); + CHECK(!(*b.type < *a.type)); +} + +:(code) string_tree::string_tree(const string_tree& old) { atom = old.atom; value = old.value; diff --git a/030container.cc b/030container.cc index bb7ce08f..33552ee8 100644 --- a/030container.cc +++ b/030container.cc @@ -194,34 +194,26 @@ void compute_container_sizes(reagent& r) { if (is_literal(r) || is_dummy(r)) return; reagent rcopy = r; // Compute Container Size(reagent rcopy) - set pending_metadata; + set pending_metadata; // might actually be faster to just convert to string rather than compare type_tree directly; so far the difference is negligible compute_container_sizes(rcopy.type, pending_metadata); if (contains_key(Container_metadata, rcopy.type)) r.metadata = get(Container_metadata, rcopy.type); } -void compute_container_sizes(const type_tree* type, set& pending_metadata) { +void compute_container_sizes(const type_tree* type, set& pending_metadata) { if (!type) return; trace(9993, "transform") << "compute container sizes for " << to_string(type) << end(); if (contains_key(Container_metadata, type)) return; - if (contains_key(pending_metadata, names_to_string_without_quotes(type))) return; - pending_metadata.insert(names_to_string_without_quotes(type)); -//? cerr << to_string(type) << '\n'; + if (contains_key(pending_metadata, *type)) return; + pending_metadata.insert(*type); if (!type->atom) { assert(type->left->atom); if (type->left->name == "address") { -//? cerr << " address\n"; compute_container_sizes(type->right, pending_metadata); } else if (type->left->name == "array") { const type_tree* element_type = type->right; // hack: support both array:number:3 and array:address:number -//? cerr << " array\n"; -//? cerr << " " << to_string(type) << '\n'; -//? cerr << " " << to_string(element_type) << ' ' << element_type->atom << ' ' << element_type->right; -//? if (element_type->right) -//? cerr << " -- " << to_string(element_type->right) << ' ' << element_type->right->atom << ' ' << is_integer(element_type->right->name); -//? cerr << '\n'; if (!element_type->atom && element_type->right && element_type->right->atom && is_integer(element_type->right->name)) element_type = element_type->left; compute_container_sizes(element_type, pending_metadata); @@ -238,7 +230,7 @@ void compute_container_sizes(const type_tree* type, set& pending_metadat // End compute_container_sizes Atom Cases } -void compute_container_sizes(const type_info& container_info, const type_tree* full_type, set& pending_metadata) { +void compute_container_sizes(const type_info& container_info, const type_tree* full_type, set& pending_metadata) { assert(container_info.kind == CONTAINER); // size of a container is the sum of the sizes of its element // (So it can only contain arrays if they're static and include their diff --git a/033exclusive_container.cc b/033exclusive_container.cc index 77968966..fd870789 100644 --- a/033exclusive_container.cc +++ b/033exclusive_container.cc @@ -41,7 +41,7 @@ if (info.kind == EXCLUSIVE_CONTAINER) { } :(code) -void compute_exclusive_container_sizes(const type_info& exclusive_container_info, const type_tree* full_type, set& pending_metadata) { +void compute_exclusive_container_sizes(const type_info& exclusive_container_info, const type_tree* full_type, set& pending_metadata) { // size of an exclusive container is the size of its largest variant // (So, like containers, it can only contain arrays if they're static and // include their length in the type.) -- cgit 1.4.1-2-gfad0