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