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