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