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