1 //:: Like container definitions, recipes too can contain type parameters.
   2 
   3 :(scenario shape_shifting_recipe)
   4 def main [
   5   10:point <- merge 14, 15
   6   11:point <- foo 10:point
   7 ]
   8 # non-matching variant
   9 def foo a:num -> result:num [
  10   local-scope
  11   load-ingredients
  12   result <- copy 34
  13 ]
  14 # matching shape-shifting variant
  15 def foo a:_t -> result:_t [
  16   local-scope
  17   load-ingredients
  18   result <- copy a
  19 ]
  20 +mem: storing 14 in location 11
  21 +mem: storing 15 in location 12
  22 
  23 //: Before anything else, disable transforms for shape-shifting recipes and
  24 //: make sure we never try to actually run a shape-shifting recipe. We should
  25 //: be rewriting such instructions to *specializations* with the type
  26 //: ingredients filled in.
  27 
  28 //: One exception (and this makes things very ugly): we need to expand type
  29 //: abbreviations in shape-shifting recipes because we need them types for
  30 //: deciding which variant to specialize.
  31 
  32 :(before "End Transform Checks")
  33 r.transformed_until = t;
  34 if (Transform.at(t) != static_cast<transform_fn>(expand_type_abbreviations) && any_type_ingredient_in_header(/*recipe_ordinal*/p->first)) continue;
  35 
  36 :(after "Running One Instruction")
  37 if (Current_routine->calls.front().running_step_index == 0
  38   ¦ && any_type_ingredient_in_header(Current_routine->calls.front().running_recipe)) {
  39 //?   DUMP("");
  40   raise << "ran into unspecialized shape-shifting recipe " << current_recipe_name() << '\n' << end();
  41 //?   exit(0);
  42 }
  43 
  44 //: Make sure we don't match up literals with type ingredients without
  45 //: specialization.
  46 :(before "End Matching Types For Literal(to)")
  47 if (contains_type_ingredient_name(to)) return false;
  48 
  49 //: save original name of specialized recipes
  50 :(before "End recipe Fields")
  51 string original_name;
  52 //: original name is only set during load
  53 :(before "End Load Recipe Name")
  54 result.original_name = result.name;
  55 
  56 :(after "Static Dispatch Phase 3")
  57 candidates = strictly_matching_shape_shifting_variants(inst, variants);
  58 if (!candidates.empty()) {
  59   recipe_ordinal exemplar = best_shape_shifting_variant(inst, candidates);
  60   trace(9992, "transform") << "found variant to specialize: " << exemplar << ' ' << get(Recipe, exemplar).name << end();
  61   recipe_ordinal new_recipe_ordinal = new_variant(exemplar, inst, caller_recipe);
  62   if (new_recipe_ordinal == 0) goto skip_shape_shifting_variants;
  63   variants.push_back(new_recipe_ordinal);  // side-effect
  64   recipe& variant = get(Recipe, new_recipe_ordinal);
  65   // perform all transforms on the new specialization
  66   if (!variant.steps.empty()) {
  67   ¦ trace(9992, "transform") << "transforming new specialization: " << variant.name << end();
  68   ¦ for (int t = 0;  t < SIZE(Transform);  ++t) {
  69   ¦ ¦ // one exception: skip tangle, which would have already occurred inside new_variant above
  70   ¦ ¦ if (Transform.at(t) == /*disambiguate overloading*/static_cast<transform_fn>(insert_fragments))
  71   ¦ ¦ ¦ continue;
  72   ¦ ¦ (*Transform.at(t))(new_recipe_ordinal);
  73   ¦ }
  74   }
  75   variant.transformed_until = SIZE(Transform)-1;
  76   trace(9992, "transform") << "new specialization: " << variant.name << end();
  77   return variant.name;
  78 }
  79 skip_shape_shifting_variants:;
  80 
  81 //: before running Mu programs, make sure no unspecialized shape-shifting
  82 //: recipes can be called
  83 
  84 :(before "End Instruction Operation Checks")
  85 if (contains_key(Recipe, inst.operation) && inst.operation >= MAX_PRIMITIVE_RECIPES
  86   ¦ && any_type_ingredient_in_header(inst.operation)) {
  87   raise << maybe(caller.name) << "instruction '" << inst.name << "' has no valid specialization\n" << end();
  88   return;
  89 }
  90 
  91 :(replace{} "bool types_strictly_match_except_literal_zero_against_address(const reagent& to, const reagent& from)")
  92 bool types_strictly_match_except_literal_zero_against_address(const reagent& to, const reagent& from) {
  93   if (is_literal(from) && is_mu_address(to))
  94   ¦ return from.name == "0" && !contains_type_ingredient_name(to);
  95   return types_strictly_match(to, from);
  96 }
  97 
  98 :(code)
  99 // phase 3 of static dispatch
 100 vector<recipe_ordinal> strictly_matching_shape_shifting_variants(const instruction& inst, vector<recipe_ordinal>& variants) {
 101   vector<recipe_ordinal> result;
 102   for (int i = 0;  i < SIZE(variants);  ++i) {
 103   ¦ if (variants.at(i) == -1) continue;
 104   ¦ if (!any_type_ingredient_in_header(variants.at(i))) continue;
 105   ¦ if (!all_concrete_header_reagents_strictly_match(inst, get(Recipe, variants.at(i)))) continue;
 106   ¦ result.push_back(variants.at(i));
 107   }
 108   return result;
 109 }
 110 
 111 bool all_concrete_header_reagents_strictly_match(const instruction& inst, const recipe& variant) {
 112   for (int i = 0;  i < min(SIZE(inst.ingredients), SIZE(variant.ingredients));  ++i) {
 113   ¦ if (!concrete_type_names_strictly_match(variant.ingredients.at(i), inst.ingredients.at(i))) {
 114   ¦ ¦ trace(9993, "transform") << "concrete-type match failed: ingredient " << i << end();
 115   ¦ ¦ return false;
 116   ¦ }
 117   }
 118   for (int i = 0;  i < min(SIZE(inst.products), SIZE(variant.ingredients));  ++i) {
 119   ¦ if (is_dummy(inst.products.at(i))) continue;
 120   ¦ if (!concrete_type_names_strictly_match(variant.products.at(i), inst.products.at(i))) {
 121   ¦ ¦ trace(9993, "transform") << "concrete-type match failed: product " << i << end();
 122   ¦ ¦ return false;
 123   ¦ }
 124   }
 125   return true;
 126 }
 127 
 128 // tie-breaker for phase 3
 129 recipe_ordinal best_shape_shifting_variant(const instruction& inst, vector<recipe_ordinal>& candidates) {
 130   assert(!candidates.empty());
 131   // primary score
 132   int max_score = -1;
 133   for (int i = 0;  i < SIZE(candidates);  ++i) {
 134   ¦ int score = number_of_concrete_type_names(candidates.at(i));
 135   ¦ assert(score > -1);
 136   ¦ if (score > max_score) max_score = score;
 137   }
 138   // break any ties at max_score by a secondary score
 139   int min_score2 = 999;
 140   int best_index = 0;
 141   for (int i = 0;  i < SIZE(candidates);  ++i) {
 142   ¦ int score1 = number_of_concrete_type_names(candidates.at(i));
 143   ¦ assert(score1 <= max_score);
 144   ¦ if (score1 != max_score) continue;
 145   ¦ const recipe& candidate = get(Recipe, candidates.at(i));
 146   ¦ int score2 = (SIZE(candidate.products)-SIZE(inst.products))
 147   ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦      + (SIZE(inst.ingredients)-SIZE(candidate.ingredients));
 148   ¦ assert(score2 < 999);
 149   ¦ if (score2 < min_score2) {
 150   ¦ ¦ min_score2 = score2;
 151   ¦ ¦ best_index = i;
 152   ¦ }
 153   }
 154   return candidates.at(best_index);
 155 }
 156 
 157 bool any_type_ingredient_in_header(recipe_ordinal variant) {
 158   const recipe& caller = get(Recipe, variant);
 159   for (int i = 0;  i < SIZE(caller.ingredients);  ++i) {
 160   ¦ if (contains_type_ingredient_name(caller.ingredients.at(i)))
 161   ¦ ¦ return true;
 162   }
 163   for (int i = 0;  i < SIZE(caller.products);  ++i) {
 164   ¦ if (contains_type_ingredient_name(caller.products.at(i)))
 165   ¦ ¦ return true;
 166   }
 167   return false;
 168 }
 169 
 170 bool concrete_type_names_strictly_match(reagent/*copy*/ to, reagent/*copy*/ from) {
 171   canonize_type(to);
 172   canonize_type(from);
 173   return concrete_type_names_strictly_match(to.type, from.type, from);
 174 }
 175 
 176 bool concrete_type_names_strictly_match(const type_tree* to, const type_tree* from, const reagent& rhs_reagent) {
 177   if (!to) return !from;
 178   if (!from) return !to;
 179   if (to->atom && is_type_ingredient_name(to->name)) return true;  // type ingredient matches anything
 180   if (!to->atom && to->right == NULL && to->left != NULL && to->left->atom && is_type_ingredient_name(to->left->name)) return true;
 181   if (from->atom && is_mu_address(to))
 182   ¦ return from->name == "literal" && rhs_reagent.name == "0";
 183   if (!from->atom && !to->atom)
 184   ¦ return concrete_type_names_strictly_match(to->left, from->left, rhs_reagent)
 185   ¦ ¦ ¦ && concrete_type_names_strictly_match(to->right, from->right, rhs_reagent);
 186   if (from->atom != to->atom) return false;
 187   // both from and to are atoms
 188   if (from->name == "literal")
 189   ¦ return Literal_type_names.find(to->name) != Literal_type_names.end();
 190   if (to->name == "literal")
 191   ¦ return Literal_type_names.find(from->name) != Literal_type_names.end();
 192   return to->name == from->name;
 193 }
 194 
 195 bool contains_type_ingredient_name(const reagent& x) {
 196   return contains_type_ingredient_name(x.type);
 197 }
 198 
 199 bool contains_type_ingredient_name(const type_tree* type) {
 200   if (!type) return false;
 201   if (is_type_ingredient_name(type->name)) return true;
 202   return contains_type_ingredient_name(type->left) || contains_type_ingredient_name(type->right);
 203 }
 204 
 205 int number_of_concrete_type_names(recipe_ordinal r) {
 206   const recipe& caller = get(Recipe, r);
 207   int result = 0;
 208   for (int i = 0;  i < SIZE(caller.ingredients);  ++i)
 209   ¦ result += number_of_concrete_type_names(caller.ingredients.at(i));
 210   for (int i = 0;  i < SIZE(caller.products);  ++i)
 211   ¦ result += number_of_concrete_type_names(caller.products.at(i));
 212   return result;
 213 }
 214 
 215 int number_of_concrete_type_names(const reagent& r) {
 216   return number_of_concrete_type_names(r.type);
 217 }
 218 
 219 int number_of_concrete_type_names(const type_tree* type) {
 220   if (!type) return 0;
 221   if (type->atom)
 222   ¦ return is_type_ingredient_name(type->name) ? 0 : 1;
 223   return number_of_concrete_type_names(type->left)
 224   ¦ ¦ ¦+ number_of_concrete_type_names(type->right);
 225 }
 226 
 227 recipe_ordinal new_variant(recipe_ordinal exemplar, const instruction& inst, const recipe& caller_recipe) {
 228   string new_name = next_unused_recipe_name(inst.name);
 229   assert(!contains_key(Recipe_ordinal, new_name));
 230   recipe_ordinal new_recipe_ordinal = put(Recipe_ordinal, new_name, Next_recipe_ordinal++);
 231   // make a copy
 232   assert(contains_key(Recipe, exemplar));
 233   assert(!contains_key(Recipe, new_recipe_ordinal));
 234   recipe new_recipe = get(Recipe, exemplar);
 235   new_recipe.name = new_name;
 236   new_recipe.is_autogenerated = true;
 237   trace(9993, "transform") << "switching " << inst.name << " to specialized " << header_label(new_recipe) << end();
 238 
 239   // Replace type ingredients with concrete types in new_recipe.
 240   //
 241   // preprocessing: micro-manage a couple of transforms
 242   // a) perform tangle *before* replacing type ingredients, just in case
 243   // inserted code involves type ingredients
 244   insert_fragments(new_recipe);
 245   // b) do the work of check_or_set_types_by_name (and its prerequisites)
 246   // while supporting type-ingredients
 247   expand_type_abbreviations(new_recipe);
 248   compute_type_names(new_recipe);
 249   // that gives enough information to replace type-ingredients with concrete types
 250   {
 251   ¦ map<string, const type_tree*> mappings;
 252   ¦ bool error = false;
 253   ¦ compute_type_ingredient_mappings(get(Recipe, exemplar), inst, mappings, caller_recipe, &error);
 254   ¦ if (!error) error = (SIZE(mappings) != type_ingredient_count_in_header(exemplar));
 255   ¦ if (!error) replace_type_ingredients(new_recipe, mappings);
 256   ¦ for (map<string, const type_tree*>::iterator p = mappings.begin();  p != mappings.end();  ++p)
 257   ¦ ¦ delete p->second;
 258   ¦ if (error) return 0;
 259   }
 260   ensure_all_concrete_types(new_recipe, get(Recipe, exemplar));
 261   put(Recipe, new_recipe_ordinal, new_recipe);
 262   return new_recipe_ordinal;
 263 }
 264 
 265 void compute_type_names(recipe& variant) {
 266   trace(9993, "transform") << "-- compute type names: " << variant.name << end();
 267   map<string, type_tree*> type_names;
 268   for (int i = 0;  i < SIZE(variant.ingredients);  ++i)
 269   ¦ save_or_deduce_type_name(variant.ingredients.at(i), type_names, variant, "");
 270   for (int i = 0;  i < SIZE(variant.products);  ++i)
 271   ¦ save_or_deduce_type_name(variant.products.at(i), type_names, variant, "");
 272   for (int i = 0;  i < SIZE(variant.steps);  ++i) {
 273   ¦ instruction& inst = variant.steps.at(i);
 274   ¦ trace(9993, "transform") << "  instruction: " << to_string(inst) << end();
 275   ¦ for (int in = 0;  in < SIZE(inst.ingredients);  ++in)
 276   ¦ ¦ save_or_deduce_type_name(inst.ingredients.at(in), type_names, variant, " in '" + inst.original_string + "'");
 277   ¦ for (int out = 0;  out < SIZE(inst.products);  ++out)
 278   ¦ ¦ save_or_deduce_type_name(inst.products.at(out), type_names, variant, " in '" + inst.original_string + "'");
 279   }
 280 }
 281 
 282 void save_or_deduce_type_name(reagent& x, map<string, type_tree*>& type, const recipe& variant, const string& context) {
 283   trace(9994, "transform") << "    checking " << to_string(x) << ": " << names_to_string(x.type) << end();
 284   if (!x.type && contains_key(type, x.name)) {
 285   ¦ x.type = new type_tree(*get(type, x.name));
 286   ¦ trace(9994, "transform") << "    deducing type to " << names_to_string(x.type) << end();
 287   ¦ return;
 288   }
 289   if (!x.type) {
 290   ¦ raise << maybe(variant.original_name) << "unknown type for '" << x.original_string << "'" << context << " (check the name for typos)\n" << end();
 291   ¦ return;
 292   }
 293   if (contains_key(type, x.name)) return;
 294   if (x.type->name == "offset" || x.type->name == "variant") return;  // special-case for container-access instructions
 295   put(type, x.name, x.type);
 296   trace(9993, "transform") << "type of '" << x.name << "' is " << names_to_string(x.type) << end();
 297 }
 298 
 299 void compute_type_ingredient_mappings(const recipe& exemplar, const instruction& inst, map<string, const type_tree*>& mappings, const recipe& caller_recipe, bool* error) {
 300   int limit = min(SIZE(inst.ingredients), SIZE(exemplar.ingredients));
 301   for (int i = 0;  i < limit;  ++i) {
 302   ¦ const reagent& exemplar_reagent = exemplar.ingredients.at(i);
 303   ¦ reagent/*copy*/ ingredient = inst.ingredients.at(i);
 304   ¦ canonize_type(ingredient);
 305   ¦ if (is_mu_address(exemplar_reagent) && ingredient.name == "0") continue;  // assume it matches
 306   ¦ accumulate_type_ingredients(exemplar_reagent, ingredient, mappings, exemplar, inst, caller_recipe, error);
 307   }
 308   limit = min(SIZE(inst.products), SIZE(exemplar.products));
 309   for (int i = 0;  i < limit;  ++i) {
 310   ¦ const reagent& exemplar_reagent = exemplar.products.at(i);
 311   ¦ reagent/*copy*/ product = inst.products.at(i);
 312   ¦ if (is_dummy(product)) continue;
 313   ¦ canonize_type(product);
 314   ¦ accumulate_type_ingredients(exemplar_reagent, product, mappings, exemplar, inst, caller_recipe, error);
 315   }
 316 }
 317 
 318 void accumulate_type_ingredients(const reagent& exemplar_reagent, reagent& refinement, map<string, const type_tree*>& mappings, const recipe& exemplar, const instruction& call_instruction, const recipe& caller_recipe, bool* error) {
 319   assert(refinement.type);
 320   accumulate_type_ingredients(exemplar_reagent.type, refinement.type, mappings, exemplar, exemplar_reagent, call_instruction, caller_recipe, error);
 321 }
 322 
 323 void accumulate_type_ingredients(const type_tree* exemplar_type, const type_tree* refinement_type, map<string, const type_tree*>& mappings, const recipe& exemplar, const reagent& exemplar_reagent, const instruction& call_instruction, const recipe& caller_recipe, bool* error) {
 324   if (!exemplar_type) return;
 325   if (!refinement_type) {
 326   ¦ // probably a bug in mu
 327   ¦ // todo: make this smarter; only flag an error if exemplar_type contains some *new* type ingredient
 328   ¦ raise << maybe(exemplar.name) << "missing type ingredient for " << exemplar_reagent.original_string << '\n' << end();
 329   ¦ raise << "  (called from '" << to_original_string(call_instruction) << "')\n" << end();
 330   ¦ return;
 331   }
 332   if (!exemplar_type->atom && exemplar_type->right == NULL && !refinement_type->atom && refinement_type->right != NULL) {
 333   ¦ exemplar_type = exemplar_type->left;
 334   ¦ assert_for_now(exemplar_type->atom);
 335   }
 336   if (exemplar_type->atom) {
 337   ¦ if (is_type_ingredient_name(exemplar_type->name)) {
 338   ¦ ¦ const type_tree* curr_refinement_type = NULL;  // temporary heap allocation; must always be deleted before it goes out of scope
 339   ¦ ¦ if (exemplar_type->atom)
 340   ¦ ¦ ¦ curr_refinement_type = new type_tree(*refinement_type);
 341   ¦ ¦ else {
 342   ¦ ¦ ¦ assert(!refinement_type->atom);
 343   ¦ ¦ ¦ curr_refinement_type = new type_tree(*refinement_type->left);
 344   ¦ ¦ }
 345   ¦ ¦ if (!contains_key(mappings, exemplar_type->name)) {
 346   ¦ ¦ ¦ trace(9993, "transform") << "adding mapping from " << exemplar_type->name << " to " << to_string(curr_refinement_type) << end();
 347   ¦ ¦ ¦ put(mappings, exemplar_type->name, new type_tree(*curr_refinement_type));
 348   ¦ ¦ }
 349   ¦ ¦ else {
 350   ¦ ¦ ¦ if (!deeply_equal_type_names(get(mappings, exemplar_type->name), curr_refinement_type)) {
 351   ¦ ¦ ¦ ¦ raise << maybe(caller_recipe.name) << "no call found for '" << to_original_string(call_instruction) << "'\n" << end();
 352   ¦ ¦ ¦ ¦ *error = true;
 353   ¦ ¦ ¦ ¦ delete curr_refinement_type;
 354   ¦ ¦ ¦ ¦ return;
 355   ¦ ¦ ¦ }
 356   ¦ ¦ ¦ if (get(mappings, exemplar_type->name)->name == "literal") {
 357   ¦ ¦ ¦ ¦ delete get(mappings, exemplar_type->name);
 358   ¦ ¦ ¦ ¦ put(mappings, exemplar_type->name, new type_tree(*curr_refinement_type));
 359   ¦ ¦ ¦ }
 360   ¦ ¦ }
 361   ¦ ¦ delete curr_refinement_type;
 362   ¦ }
 363   }
 364   else {
 365   ¦ accumulate_type_ingredients(exemplar_type->left, refinement_type->left, mappings, exemplar, exemplar_reagent, call_instruction, caller_recipe, error);
 366   ¦ accumulate_type_ingredients(exemplar_type->right, refinement_type->right, mappings, exemplar, exemplar_reagent, call_instruction, caller_recipe, error);
 367   }
 368 }
 369 
 370 void replace_type_ingredients(recipe& new_recipe, const map<string, const type_tree*>& mappings) {
 371   // update its header
 372   if (mappings.empty()) return;
 373   trace(9993, "transform") << "replacing in recipe header ingredients" << end();
 374   for (int i = 0;  i < SIZE(new_recipe.ingredients);  ++i)
 375   ¦ replace_type_ingredients(new_recipe.ingredients.at(i), mappings, new_recipe);
 376   trace(9993, "transform") << "replacing in recipe header products" << end();
 377   for (int i = 0;  i < SIZE(new_recipe.products);  ++i)
 378   ¦ replace_type_ingredients(new_recipe.products.at(i), mappings, new_recipe);
 379   // update its body
 380   for (int i = 0;  i < SIZE(new_recipe.steps);  ++i) {
 381   ¦ instruction& inst = new_recipe.steps.at(i);
 382   ¦ trace(9993, "transform") << "replacing in instruction '" << to_string(inst) << "'" << end();
 383   ¦ for (int j = 0;  j < SIZE(inst.ingredients);  ++j)
 384   ¦ ¦ replace_type_ingredients(inst.ingredients.at(j), mappings, new_recipe);
 385   ¦ for (int j = 0;  j < SIZE(inst.products);  ++j)
 386   ¦ ¦ replace_type_ingredients(inst.products.at(j), mappings, new_recipe);
 387   ¦ // special-case for new: replace type ingredient in first ingredient *value*
 388   ¦ if (inst.name == "new" && inst.ingredients.at(0).type->name != "literal-string") {
 389   ¦ ¦ type_tree* type = parse_type_tree(inst.ingredients.at(0).name);
 390   ¦ ¦ replace_type_ingredients(type, mappings);
 391   ¦ ¦ inst.ingredients.at(0).name = inspect(type);
 392   ¦ ¦ delete type;
 393   ¦ }
 394   }
 395 }
 396 
 397 void replace_type_ingredients(reagent& x, const map<string, const type_tree*>& mappings, const recipe& caller) {
 398   string before = to_string(x);
 399   trace(9993, "transform") << "replacing in ingredient " << x.original_string << end();
 400   if (!x.type) {
 401   ¦ raise << "specializing " << caller.original_name << ": missing type for '" << x.original_string << "'\n" << end();
 402   ¦ return;
 403   }
 404   replace_type_ingredients(x.type, mappings);
 405 }
 406 
 407 void replace_type_ingredients(type_tree* type, const map<string, const type_tree*>& mappings) {
 408   if (!type) return;
 409   if (!type->atom) {
 410   ¦ if (type->right == NULL && type->left != NULL && type->left->atom && contains_key(mappings, type->left->name) && !get(mappings, type->left->name)->atom && get(mappings, type->left->name)->right != NULL) {
 411   ¦ ¦ *type = *get(mappings, type->left->name);
 412   ¦ ¦ return;
 413   ¦ }
 414   ¦ replace_type_ingredients(type->left, mappings);
 415   ¦ replace_type_ingredients(type->right, mappings);
 416   ¦ return;
 417   }
 418   if (contains_key(Type_ordinal, type->name))  // todo: ugly side effect
 419   ¦ type->value = get(Type_ordinal, type->name);
 420   if (!contains_key(mappings, type->name))
 421   ¦ return;
 422   const type_tree* replacement = get(mappings, type->name);
 423   trace(9993, "transform") << type->name << " => " << names_to_string(replacement) << end();
 424   if (replacement->atom) {
 425   ¦ if (!contains_key(Type_ordinal, replacement->name)) {
 426   ¦ ¦ // error in program; should be reported elsewhere
 427   ¦ ¦ return;
 428   ¦ }
 429   ¦ type->name = (replacement->name == "literal") ? "number" : replacement->name;
 430   ¦ type->value = get(Type_ordinal, type->name);
 431   }
 432   else {
 433   ¦ *type = *replacement;
 434   }
 435 }
 436 
 437 int type_ingredient_count_in_header(recipe_ordinal variant) {
 438   const recipe& caller = get(Recipe, variant);
 439   set<string> type_ingredients;
 440   for (int i = 0;  i < SIZE(caller.ingredients);  ++i)
 441   ¦ accumulate_type_ingredients(caller.ingredients.at(i).type, type_ingredients);
 442   for (int i = 0;  i < SIZE(caller.products);  ++i)
 443   ¦ accumulate_type_ingredients(caller.products.at(i).type, type_ingredients);
 444   return SIZE(type_ingredients);
 445 }
 446 
 447 void accumulate_type_ingredients(const type_tree* type, set<string>& out) {
 448   if (!type) return;
 449   if (is_type_ingredient_name(type->name)) out.insert(type->name);
 450   accumulate_type_ingredients(type->left, out);
 451   accumulate_type_ingredients(type->right, out);
 452 }
 453 
 454 type_tree* parse_type_tree(const string& s) {
 455   string_tree* s2 = parse_string_tree(s);
 456   type_tree* result = new_type_tree(s2);
 457   delete s2;
 458   return result;
 459 }
 460 
 461 string inspect(const type_tree* x) {
 462   ostringstream out;
 463   dump_inspect(x, out);
 464   return out.str();
 465 }
 466 
 467 void dump_inspect(const type_tree* x, ostream& out) {
 468   if (!x->left && !x->right) {
 469   ¦ out << x->name;
 470   ¦ return;
 471   }
 472   out << '(';
 473   for (const type_tree* curr = x;  curr;  curr = curr->right) {
 474   ¦ if (curr != x) out << ' ';
 475   ¦ if (curr->left)
 476   ¦ ¦ dump_inspect(curr->left, out);
 477   ¦ else
 478   ¦ ¦ out << curr->name;
 479   }
 480   out << ')';
 481 }
 482 
 483 void ensure_all_concrete_types(/*const*/ recipe& new_recipe, const recipe& exemplar) {
 484   trace(9993, "transform") << "-- ensure all concrete types in recipe " << new_recipe.name << end();
 485   for (int i = 0;  i < SIZE(new_recipe.ingredients);  ++i)
 486   ¦ ensure_all_concrete_types(new_recipe.ingredients.at(i), exemplar);
 487   for (int i = 0;  i < SIZE(new_recipe.products);  ++i)
 488   ¦ ensure_all_concrete_types(new_recipe.products.at(i), exemplar);
 489   for (int i = 0;  i < SIZE(new_recipe.steps);  ++i) {
 490   ¦ instruction& inst = new_recipe.steps.at(i);
 491   ¦ for (int j = 0;  j < SIZE(inst.ingredients);  ++j)
 492   ¦ ¦ ensure_all_concrete_types(inst.ingredients.at(j), exemplar);
 493   ¦ for (int j = 0;  j < SIZE(inst.products);  ++j)
 494   ¦ ¦ ensure_all_concrete_types(inst.products.at(j), exemplar);
 495   }
 496 }
 497 
 498 void ensure_all_concrete_types(/*const*/ reagent& x, const recipe& exemplar) {
 499   if (!x.type || contains_type_ingredient_name(x.type)) {
 500   ¦ raise << maybe(exemplar.name) << "failed to map a type to " << x.original_string << '\n' << end();
 501   ¦ if (!x.type) x.type = new type_tree("", 0);  // just to prevent crashes later
 502   ¦ return;
 503   }
 504   if (x.type->value == -1) {
 505   ¦ raise << maybe(exemplar.name) << "failed to map a type to the unknown " << x.original_string << '\n' << end();
 506   ¦ return;
 507   }
 508 }
 509 
 510 :(scenario shape_shifting_recipe_2)
 511 def main [
 512   10:point <- merge 14, 15
 513   11:point <- foo 10:point
 514 ]
 515 # non-matching shape-shifting variant
 516 def foo a:_t, b:_t -> result:num [
 517   local-scope
 518   load-ingredients
 519   result <- copy 34
 520 ]
 521 # matching shape-shifting variant
 522 def foo a:_t -> result:_t [
 523   local-scope
 524   load-ingredients
 525   result <- copy a
 526 ]
 527 +mem: storing 14 in location 11
 528 +mem: storing 15 in location 12
 529 
 530 :(scenario shape_shifting_recipe_nonroot)
 531 def main [
 532   10:foo:point <- merge 14, 15, 16
 533   20:point/raw <- bar 10:foo:point
 534 ]
 535 # shape-shifting recipe with type ingredient following some other type
 536 def bar a:foo:_t -> result:_t [
 537   local-scope
 538   load-ingredients
 539   result <- get a, x:offset
 540 ]
 541 container foo:_t [
 542   x:_t
 543   y:num
 544 ]
 545 +mem: storing 14 in location 20
 546 +mem: storing 15 in location 21
 547 
 548 :(scenario shape_shifting_recipe_nested)
 549 container c:_a:_b [
 550   a:_a
 551   b:_b
 552 ]
 553 def main [
 554   s:text <- new [abc]
 555   {x: (c (address array character) number)} <- merge s, 34
 556   foo x
 557 ]
 558 def foo x:c:_bar:_baz [
 559   local-scope
 560   load-ingredients
 561 ]
 562 # no errors
 563 
 564 :(scenario shape_shifting_recipe_type_deduction_ignores_offsets)
 565 def main [
 566   10:foo:point <- merge 14, 15, 16
 567   20:point/raw <- bar 10:foo:point
 568 ]
 569 def bar a:foo:_t -> result:_t [
 570   local-scope
 571   load-ingredients
 572   x:num <- copy 1
 573   result <- get a, x:offset  # shouldn't collide with other variable
 574 ]
 575 container foo:_t [
 576   x:_t
 577   y:num
 578 ]
 579 +mem: storing 14 in location 20
 580 +mem: storing 15 in location 21
 581 
 582 :(scenario shape_shifting_recipe_empty)
 583 def main [
 584   foo 1
 585 ]
 586 # shape-shifting recipe with no body
 587 def foo a:_t [
 588 ]
 589 # shouldn't crash
 590 
 591 :(scenario shape_shifting_recipe_handles_shape_shifting_new_ingredient)
 592 def main [
 593   1:&:foo:point <- bar 3
 594   11:foo:point <- copy *1:&:foo:point
 595 ]
 596 container foo:_t [
 597   x:_t
 598   y:num
 599 ]
 600 def bar x:num -> result:&:foo:_t [
 601   local-scope
 602   load-ingredients
 603   # new refers to _t in its ingredient *value*
 604   result <- new {(foo _t) : type}
 605 ]
 606 +mem: storing 0 in location 11
 607 +mem: storing 0 in location 12
 608 +mem: storing 0 in location 13
 609 
 610 :(scenario shape_shifting_recipe_handles_shape_shifting_new_ingredient_2)
 611 def main [
 612   1:&:foo:point <- bar 3
 613   11:foo:point <- copy *1:&:foo:point
 614 ]
 615 def bar x:num -> result:&:foo:_t [
 616   local-scope
 617   load-ingredients
 618   # new refers to _t in its ingredient *value*
 619   result <- new {(foo _t) : type}
 620 ]
 621 # container defined after use
 622 container foo:_t [
 623   x:_t
 624   y:num
 625 ]
 626 +mem: storing 0 in location 11
 627 +mem: storing 0 in location 12
 628 +mem: storing 0 in location 13
 629 
 630 :(scenario shape_shifting_recipe_called_with_dummy)
 631 def main [
 632   _ <- bar 34
 633 ]
 634 def bar x:_t -> result:&:_t [
 635   local-scope
 636   load-ingredients
 637   result <- copy 0
 638 ]
 639 $error: 0
 640 
 641 :(code)
 642 // this one needs a little more fine-grained control
 643 void test_shape_shifting_new_ingredient_does_not_pollute_global_namespace() {
 644   // if you specialize a shape-shifting recipe that allocates a type-ingredient..
 645   transform("def barz x:_elem [\n"
 646   ¦ ¦ ¦ ¦ ¦ "  local-scope\n"
 647   ¦ ¦ ¦ ¦ ¦ "  load-ingredients\n"
 648   ¦ ¦ ¦ ¦ ¦ "  y:&:num <- new _elem:type\n"
 649   ¦ ¦ ¦ ¦ ¦ "]\n"
 650   ¦ ¦ ¦ ¦ ¦ "def fooz [\n"
 651   ¦ ¦ ¦ ¦ ¦ "  local-scope\n"
 652   ¦ ¦ ¦ ¦ ¦ "  barz 34\n"
 653   ¦ ¦ ¦ ¦ ¦ "]\n");
 654   // ..and if you then try to load a new shape-shifting container with that
 655   // type-ingredient
 656   run("container foo:_elem [\n"
 657   ¦ ¦ "  x:_elem\n"
 658   ¦ ¦ "  y:num\n"
 659   ¦ ¦ "]\n");
 660   // then it should work as usual
 661   reagent callsite("x:foo:point");
 662   reagent element = element_type(callsite.type, 0);
 663   CHECK_EQ(element.name, "x");
 664   CHECK_EQ(element.type->name, "point");
 665   CHECK(!element.type->right);
 666 }
 667 
 668 //: specializing a type ingredient with a compound type
 669 :(scenario shape_shifting_recipe_supports_compound_types)
 670 def main [
 671   1:&:point <- new point:type
 672   *1:&:point <- put *1:&:point, y:offset, 34
 673   3:&:point <- bar 1:&:point  # specialize _t to address:point
 674   4:point <- copy *3:&:point
 675 ]
 676 def bar a:_t -> result:_t [
 677   local-scope
 678   load-ingredients
 679   result <- copy a
 680 ]
 681 +mem: storing 34 in location 5
 682 
 683 //: specializing a type ingredient with a compound type -- while *inside* another compound type
 684 :(scenario shape_shifting_recipe_supports_compound_types_2)
 685 container foo:_t [
 686   value:_t
 687 ]
 688 def bar x:&:foo:_t -> result:_t [
 689   local-scope
 690   load-ingredients
 691   result <- get *x, value:offset
 692 ]
 693 def main [
 694   1:&:foo:&:point <- new {(foo address point): type}
 695   2:&:point <- bar 1:&:foo:&:point
 696 ]
 697 # no errors; call to 'bar' successfully specialized
 698 
 699 :(scenario shape_shifting_recipe_error)
 700 % Hide_errors = true;
 701 def main [
 702   a:num <- copy 3
 703   b:&:num <- foo a
 704 ]
 705 def foo a:_t -> b:_t [
 706   load-ingredients
 707   b <- copy a
 708 ]
 709 +error: main: no call found for 'b:&:num <- foo a'
 710 
 711 :(scenario specialize_inside_recipe_without_header)
 712 def main [
 713   foo 3
 714 ]
 715 def foo [
 716   local-scope
 717   x:num <- next-ingredient  # ensure no header
 718   1:num/raw <- bar x  # call a shape-shifting recipe
 719 ]
 720 def bar x:_elem -> y:_elem [
 721   local-scope
 722   load-ingredients
 723   y <- add x, 1
 724 ]
 725 +mem: storing 4 in location 1
 726 
 727 :(scenario specialize_with_literal)
 728 def main [
 729   local-scope
 730   # permit literal to map to number
 731   1:num/raw <- foo 3
 732 ]
 733 def foo x:_elem -> y:_elem [
 734   local-scope
 735   load-ingredients
 736   y <- add x, 1
 737 ]
 738 +mem: storing 4 in location 1
 739 
 740 :(scenario specialize_with_literal_2)
 741 def main [
 742   local-scope
 743   # permit literal to map to character
 744   1:char/raw <- foo 3
 745 ]
 746 def foo x:_elem -> y:_elem [
 747   local-scope
 748   load-ingredients
 749   y <- add x, 1
 750 ]
 751 +mem: storing 4 in location 1
 752 
 753 :(scenario specialize_with_literal_3)
 754 def main [
 755   local-scope
 756   # permit '0' to map to address to shape-shifting type-ingredient
 757   1:&:char/raw <- foo 0
 758 ]
 759 def foo x:&:_elem -> y:&:_elem [
 760   local-scope
 761   load-ingredients
 762   y <- copy x
 763 ]
 764 +mem: storing 0 in location 1
 765 $error: 0
 766 
 767 :(scenario specialize_with_literal_4)
 768 % Hide_errors = true;
 769 def main [
 770   local-scope
 771   # ambiguous call: what's the type of its ingredient?!
 772   foo 0
 773 ]
 774 def foo x:&:_elem -> y:&:_elem [
 775   local-scope
 776   load-ingredients
 777   y <- copy x
 778 ]
 779 +error: main: instruction 'foo' has no valid specialization
 780 
 781 :(scenario specialize_with_literal_5)
 782 def main [
 783   foo 3, 4  # recipe mapping two variables to literals
 784 ]
 785 def foo x:_elem, y:_elem [
 786   local-scope
 787   load-ingredients
 788   1:num/raw <- add x, y
 789 ]
 790 +mem: storing 7 in location 1
 791 
 792 :(scenario multiple_shape_shifting_variants)
 793 # try to call two different shape-shifting recipes with the same name
 794 def main [
 795   e1:d1:num <- merge 3
 796   e2:d2:num <- merge 4, 5
 797   1:num/raw <- foo e1
 798   2:num/raw <- foo e2
 799 ]
 800 # the two shape-shifting definitions
 801 def foo a:d1:_elem -> b:num [
 802   local-scope
 803   load-ingredients
 804   return 34
 805 ]
 806 def foo a:d2:_elem -> b:num [
 807   local-scope
 808   load-ingredients
 809   return 35
 810 ]
 811 # the shape-shifting containers they use
 812 container d1:_elem [
 813   x:_elem
 814 ]
 815 container d2:_elem [
 816   x:num
 817   y:_elem
 818 ]
 819 +mem: storing 34 in location 1
 820 +mem: storing 35 in location 2
 821 
 822 :(scenario multiple_shape_shifting_variants_2)
 823 # static dispatch between shape-shifting variants, _including pointer lookups_
 824 def main [
 825   e1:d1:num <- merge 3
 826   e2:&:d2:num <- new {(d2 number): type}
 827   1:num/raw <- foo e1
 828   2:num/raw <- foo *e2  # different from previous scenario
 829 ]
 830 def foo a:d1:_elem -> b:num [
 831   local-scope
 832   load-ingredients
 833   return 34
 834 ]
 835 def foo a:d2:_elem -> b:num [
 836   local-scope
 837   load-ingredients
 838   return 35
 839 ]
 840 container d1:_elem [
 841   x:_elem
 842 ]
 843 container d2:_elem [
 844   x:num
 845   y:_elem
 846 ]
 847 +mem: storing 34 in location 1
 848 +mem: storing 35 in location 2
 849 
 850 :(scenario missing_type_in_shape_shifting_recipe)
 851 % Hide_errors = true;
 852 def main [
 853   a:d1:num <- merge 3
 854   foo a
 855 ]
 856 def foo a:d1:_elem -> b:num [
 857   local-scope
 858   load-ingredients
 859   copy e  # no such variable
 860   return 34
 861 ]
 862 container d1:_elem [
 863   x:_elem
 864 ]
 865 +error: foo: unknown type for 'e' in 'copy e' (check the name for typos)
 866 +error: specializing foo: missing type for 'e'
 867 # and it doesn't crash
 868 
 869 :(scenario missing_type_in_shape_shifting_recipe_2)
 870 % Hide_errors = true;
 871 def main [
 872   a:d1:num <- merge 3
 873   foo a
 874 ]
 875 def foo a:d1:_elem -> b:num [
 876   local-scope
 877   load-ingredients
 878   get e, x:offset  # unknown variable in a 'get', which does some extra checking
 879   return 34
 880 ]
 881 container d1:_elem [
 882   x:_elem
 883 ]
 884 +error: foo: unknown type for 'e' in 'get e, x:offset' (check the name for typos)
 885 +error: specializing foo: missing type for 'e'
 886 # and it doesn't crash
 887 
 888 :(scenarios transform)
 889 :(scenario specialize_recursive_shape_shifting_recipe)
 890 def main [
 891   1:num <- copy 34
 892   2:num <- foo 1:num
 893 ]
 894 def foo x:_elem -> y:num [
 895   local-scope
 896   load-ingredients
 897   {
 898   ¦ break
 899   ¦ y:num <- foo x
 900   }
 901   return y
 902 ]
 903 +transform: new specialization: foo_2
 904 # transform terminates
 905 
 906 :(scenarios run)
 907 :(scenario specialize_most_similar_variant)
 908 def main [
 909   1:&:num <- new number:type
 910   2:num <- foo 1:&:num
 911 ]
 912 def foo x:_elem -> y:num [
 913   local-scope
 914   load-ingredients
 915   return 34
 916 ]
 917 def foo x:&:_elem -> y:num [
 918   local-scope
 919   load-ingredients
 920   return 35
 921 ]
 922 +mem: storing 35 in location 2
 923 
 924 :(scenario specialize_most_similar_variant_2)
 925 # version with headers padded with lots of unrelated concrete types
 926 def main [
 927   1:num <- copy 23
 928   2:&:@:num <- copy 0
 929   3:num <- foo 2:&:@:num, 1:num
 930 ]
 931 # variant with concrete type
 932 def foo dummy:&:@:num, x:num -> y:num, dummy:&:@:num [
 933   local-scope
 934   load-ingredients
 935   return 34
 936 ]
 937 # shape-shifting variant
 938 def foo dummy:&:@:num, x:_elem -> y:num, dummy:&:@:num [
 939   local-scope
 940   load-ingredients
 941   return 35
 942 ]
 943 # prefer the concrete variant
 944 +mem: storing 34 in location 3
 945 
 946 :(scenario specialize_most_similar_variant_3)
 947 def main [
 948   1:text <- new [abc]
 949   foo 1:text
 950 ]
 951 def foo x:text [
 952   2:num <- copy 34
 953 ]
 954 def foo x:&:_elem [
 955   2:num <- copy 35
 956 ]
 957 # make sure the more precise version was used
 958 +mem: storing 34 in location 2
 959 
 960 :(scenario specialize_literal_as_number)
 961 def main [
 962   1:num <- foo 23
 963 ]
 964 def foo x:_elem -> y:num [
 965   local-scope
 966   load-ingredients
 967   return 34
 968 ]
 969 def foo x:char -> y:num [
 970   local-scope
 971   load-ingredients
 972   return 35
 973 ]
 974 +mem: storing 34 in location 1
 975 
 976 :(scenario specialize_literal_as_number_2)
 977 # version calling with literal
 978 def main [
 979   1:num <- foo 0
 980 ]
 981 # variant with concrete type
 982 def foo x:num -> y:num [
 983   local-scope
 984   load-ingredients
 985   return 34
 986 ]
 987 # shape-shifting variant
 988 def foo x:&:_elem -> y:num [
 989   local-scope
 990   load-ingredients
 991   return 35
 992 ]
 993 # prefer the concrete variant, ignore concrete types in scoring the shape-shifting variant
 994 +mem: storing 34 in location 1
 995 
 996 :(scenario specialize_literal_as_address)
 997 def main [
 998   1:num <- foo 0
 999 ]
1000 # variant with concrete address type
1001 def foo x:&:num -> y:num [
1002   local-scope
1003   load-ingredients
1004   return 34
1005 ]
1006 # shape-shifting variant
1007 def foo x:&:_elem -> y:num [
1008   local-scope
1009   load-ingredients
1010   return 35
1011 ]
1012 # prefer the concrete variant, ignore concrete types in scoring the shape-shifting variant
1013 +mem: storing 34 in location 1
1014 
1015 :(scenario missing_type_during_specialization)
1016 % Hide_errors = true;
1017 # define a shape-shifting recipe
1018 def foo a:_elem [
1019 ]
1020 # define a container with field 'z'
1021 container foo2 [
1022   z:num
1023 ]
1024 def main [
1025   local-scope
1026   x:foo2 <- merge 34
1027   y:num <- get x, z:offse  # typo in 'offset'
1028   # define a variable with the same name 'z'
1029   z:num <- copy 34
1030   # trigger specialization of the shape-shifting recipe
1031   foo z
1032 ]
1033 # shouldn't crash
1034 
1035 :(scenario missing_type_during_specialization2)
1036 % Hide_errors = true;
1037 # define a shape-shifting recipe
1038 def foo a:_elem [
1039 ]
1040 # define a container with field 'z'
1041 container foo2 [
1042   z:num
1043 ]
1044 def main [
1045   local-scope
1046   x:foo2 <- merge 34
1047   y:num <- get x, z:offse  # typo in 'offset'
1048   # define a variable with the same name 'z'
1049   z:&:num <- copy 34
1050   # trigger specialization of the shape-shifting recipe
1051   foo *z
1052 ]
1053 # shouldn't crash
1054 
1055 :(scenario tangle_shape_shifting_recipe)
1056 # shape-shifting recipe
1057 def foo a:_elem [
1058   local-scope
1059   load-ingredients
1060   <label1>
1061 ]
1062 # tangle some code that refers to the type ingredient
1063 after <label1> [
1064   b:_elem <- copy a
1065 ]
1066 # trigger specialization
1067 def main [
1068   local-scope
1069   foo 34
1070 ]
1071 $error: 0
1072 
1073 :(scenario tangle_shape_shifting_recipe_with_type_abbreviation)
1074 # shape-shifting recipe
1075 def foo a:_elem [
1076   local-scope
1077   load-ingredients
1078   <label1>
1079 ]
1080 # tangle some code that refers to the type ingredient
1081 after <label1> [
1082   b:bool <- copy 0  # type abbreviation
1083 ]
1084 # trigger specialization
1085 def main [
1086   local-scope
1087   foo 34
1088 ]
1089 $error: 0
1090 
1091 :(scenario shape_shifting_recipe_coexists_with_primitive)
1092 # recipe overloading a primitive with a generic type
1093 def add a:&:foo:_elem [
1094   assert 0, [should not get here]
1095 ]
1096 def main [
1097   # call primitive add with literal 0
1098   add 0, 0
1099 ]
1100 $error: 0