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