1 //: Transform to maintain multiple variants of a recipe depending on the
  2 //: number and types of the ingredients and products. Allows us to use nice
  3 //: names like 'print' or 'length' in many mutually extensible ways.
  4 
  5 :(scenario static_dispatch)
  6 def main [
  7   7:num/raw <- test 3
  8 ]
  9 def test a:num -> z:num [
 10   z <- copy 1
 11 ]
 12 def test a:num, b:num -> z:num [
 13   z <- copy 2
 14 ]
 15 +mem: storing 1 in location 7
 16 
 17 //: When loading recipes, accumulate variants if headers don't collide, and
 18 //: flag an error if headers collide.
 19 
 20 :(before "End Globals")
 21 map<string, vector<recipe_ordinal> > Recipe_variants;
 22 :(before "End One-time Setup")
 23 put(Recipe_variants, "main", vector<recipe_ordinal>());  // since we manually added main to Recipe_ordinal
 24 
 25 :(before "End Globals")
 26 map<string, vector<recipe_ordinal> > Recipe_variants_snapshot;
 27 :(before "End save_snapshots")
 28 Recipe_variants_snapshot = Recipe_variants;
 29 :(before "End restore_snapshots")
 30 Recipe_variants = Recipe_variants_snapshot;
 31 
 32 :(before "End Load Recipe Header(result)")
 33 // there can only ever be one variant for main
 34 if (result.name != "main" && contains_key(Recipe_ordinal, result.name)) {
 35   const recipe_ordinal r = get(Recipe_ordinal, result.name);
 36   if (!contains_key(Recipe, r) || get(Recipe, r).has_header) {
 37     string new_name = matching_variant_name(result);
 38     if (new_name.empty()) {
 39       // variant doesn't already exist
 40       new_name = next_unused_recipe_name(result.name);
 41       put(Recipe_ordinal, new_name, Next_recipe_ordinal++);
 42       get_or_insert(Recipe_variants, result.name).push_back(get(Recipe_ordinal, new_name));
 43     }
 44     trace(9999, "load") << "switching " << result.name << " to " << new_name << end();
 45     result.name = new_name;
 46     result.is_autogenerated = true;
 47   }
 48 }
 49 else {
 50   // save first variant
 51   put(Recipe_ordinal, result.name, Next_recipe_ordinal++);
 52   get_or_insert(Recipe_variants, result.name).push_back(get(Recipe_ordinal, result.name));
 53 }
 54 
 55 :(code)
 56 string matching_variant_name(const recipe& rr) {
 57   const vector<recipe_ordinal>& variants = get_or_insert(Recipe_variants, rr.name);
 58   for (int i = 0;  i < SIZE(variants);  ++i) {
 59     if (!contains_key(Recipe, variants.at(i))) continue;
 60     const recipe& candidate = get(Recipe, variants.at(i));
 61     if (!all_reagents_match(rr, candidate)) continue;
 62     return candidate.name;
 63   }
 64   return "";
 65 }
 66 
 67 bool all_reagents_match(const recipe& r1, const recipe& r2) {
 68   if (SIZE(r1.ingredients) != SIZE(r2.ingredients)) return false;
 69   if (SIZE(r1.products) != SIZE(r2.products)) return false;
 70   for (int i = 0;  i < SIZE(r1.ingredients);  ++i) {
 71     expand_type_abbreviations(r1.ingredients.at(i).type);
 72     expand_type_abbreviations(r2.ingredients.at(i).type);
 73     if (!deeply_equal_type_names(r1.ingredients.at(i), r2.ingredients.at(i)))
 74       return false;
 75   }
 76   for (int i = 0;  i < SIZE(r1.products);  ++i) {
 77     expand_type_abbreviations(r1.products.at(i).type);
 78     expand_type_abbreviations(r2.products.at(i).type);
 79     if (!deeply_equal_type_names(r1.products.at(i), r2.products.at(i)))
 80       return false;
 81   }
 82   return true;
 83 }
 84 
 85 :(before "End Globals")
 86 set<string> Literal_type_names;
 87 :(before "End One-time Setup")
 88 Literal_type_names.insert("number");
 89 Literal_type_names.insert("character");
 90 :(code)
 91 bool deeply_equal_type_names(const reagent& a, const reagent& b) {
 92   return deeply_equal_type_names(a.type, b.type);
 93 }
 94 bool deeply_equal_type_names(const type_tree* a, const type_tree* b) {
 95   if (!a) return !b;
 96   if (!b) return !a;
 97   if (a->atom != b->atom) return false;
 98   if (a->atom) {
 99     if (a->name == "literal" && b->name == "literal")
100       return true;
101     if (a->name == "literal")
102       return Literal_type_names.find(b->name) != Literal_type_names.end();
103     if (b->name == "literal")
104       return Literal_type_names.find(a->name) != Literal_type_names.end();
105     return a->name == b->name;
106   }
107   return deeply_equal_type_names(a->left, b->left)
108       && deeply_equal_type_names(a->right, b->right);
109 }
110 
111 string next_unused_recipe_name(const string& recipe_name) {
112   for (int i = 2;  /*forever*/;  ++i) {
113     ostringstream out;
114     out << recipe_name << '_' << i;
115     if (!contains_key(Recipe_ordinal, out.str()))
116       return out.str();
117   }
118 }
119 
120 //: Once all the recipes are loaded, transform their bodies to replace each
121 //: call with the most suitable variant.
122 
123 :(scenario static_dispatch_picks_most_similar_variant)
124 def main [
125   7:num/raw <- test 3, 4, 5
126 ]
127 def test a:num -> z:num [
128   z <- copy 1
129 ]
130 def test a:num, b:num -> z:num [
131   z <- copy 2
132 ]
133 +mem: storing 2 in location 7
134 
135 //: support recipe headers in a previous transform to fill in missing types
136 :(before "End check_or_set_invalid_types")
137 for (int i = 0;  i < SIZE(caller.ingredients);  ++i)
138   check_or_set_invalid_types(caller.ingredients.at(i).type, maybe(caller.name), "recipe header ingredient");
139 for (int i = 0;  i < SIZE(caller.products);  ++i)
140   check_or_set_invalid_types(caller.products.at(i).type, maybe(caller.name), "recipe header product");
141 
142 //: after filling in all missing types (because we'll be introducing 'blank' types in this transform in a later layer, for shape-shifting recipes)
143 :(after "Transform.push_back(transform_names)")
144 Transform.push_back(resolve_ambiguous_calls);  // idempotent
145 
146 //: In a later layer we'll introduce recursion in resolve_ambiguous_calls, by
147 //: having it generate code for shape-shifting recipes and then transform such
148 //: code. This data structure will help error messages be more useful.
149 //:
150 //: We're punning the 'call' data structure just because it has slots for
151 //: calling recipe and calling instruction.
152 :(before "End Globals")
153 list<call> Resolve_stack;
154 
155 :(code)
156 void resolve_ambiguous_calls(const recipe_ordinal r) {
157   recipe& caller_recipe = get(Recipe, r);
158   trace(9991, "transform") << "--- resolve ambiguous calls for recipe " << caller_recipe.name << end();
159   for (int index = 0;  index < SIZE(caller_recipe.steps);  ++index) {
160     instruction& inst = caller_recipe.steps.at(index);
161     if (inst.is_label) continue;
162     if (non_ghost_size(get_or_insert(Recipe_variants, inst.name)) == 0) continue;
163     trace(9992, "transform") << "instruction " << inst.original_string << end();
164     Resolve_stack.push_front(call(r));
165     Resolve_stack.front().running_step_index = index;
166     string new_name = best_variant(inst, caller_recipe);
167     if (!new_name.empty())
168       inst.name = new_name;
169     assert(Resolve_stack.front().running_recipe == r);
170     assert(Resolve_stack.front().running_step_index == index);
171     Resolve_stack.pop_front();
172   }
173 }
174 
175 string best_variant(instruction& inst, const recipe& caller_recipe) {
176   vector<recipe_ordinal>& variants = get(Recipe_variants, inst.name);
177   vector<recipe_ordinal> candidates;
178 
179   // Static Dispatch Phase 1
180   candidates = strictly_matching_variants(inst, variants);
181   if (!candidates.empty()) return best_variant(inst, candidates).name;
182 
183   // Static Dispatch Phase 2
184   candidates = strictly_matching_variants_except_literal_zero_against_address(inst, variants);
185   if (!candidates.empty()) return best_variant(inst, candidates).name;
186 
187   // Static Dispatch Phase 3
188   //: (shape-shifting recipes in a later layer)
189   // End Static Dispatch Phase 3
190 
191   // Static Dispatch Phase 4
192   candidates = strictly_matching_variants_except_literal_against_address_or_boolean(inst, variants);
193   if (!candidates.empty()) return best_variant(inst, candidates).name;
194 
195   // Static Dispatch Phase 5
196   candidates = matching_variants(inst, variants);
197   if (!candidates.empty()) return best_variant(inst, candidates).name;
198 
199   // error messages
200   if (get(Recipe_ordinal, inst.name) >= MAX_PRIMITIVE_RECIPES) {  // we currently don't check types for primitive variants
201     raise << maybe(caller_recipe.name) << "failed to find a matching call for '" << inst.original_string << "'\n" << end();
202     for (list<call>::iterator p = /*skip*/++Resolve_stack.begin();  p != Resolve_stack.end();  ++p) {
203       const recipe& specializer_recipe = get(Recipe, p->running_recipe);
204       const instruction& specializer_inst = specializer_recipe.steps.at(p->running_step_index);
205       if (specializer_recipe.name != "interactive")
206         raise << "  (from '" << to_original_string(specializer_inst) << "' in " << specializer_recipe.name << ")\n" << end();
207       else
208         raise << "  (from '" << to_original_string(specializer_inst) << "')\n" << end();
209       // One special-case to help with the rewrite_stash transform. (cross-layer)
210       if (specializer_inst.products.at(0).name.find("stash_") == 0) {
211         instruction stash_inst;
212         if (next_stash(*p, &stash_inst)) {
213           if (specializer_recipe.name != "interactive")
214             raise << "  (part of '" << stash_inst.original_string << "' in " << specializer_recipe.name << ")\n" << end();
215           else
216             raise << "  (part of '" << stash_inst.original_string << "')\n" << end();
217         }
218       }
219     }
220   }
221   return "";
222 }
223 
224 // phase 1
225 vector<recipe_ordinal> strictly_matching_variants(const instruction& inst, vector<recipe_ordinal>& variants) {
226   vector<recipe_ordinal> result;
227   for (int i = 0;  i < SIZE(variants);  ++i) {
228     if (variants.at(i) == -1) continue;
229     trace(9992, "transform") << "checking variant (strict) " << i << ": " << header_label(variants.at(i)) << end();
230     if (all_header_reagents_strictly_match(inst, get(Recipe, variants.at(i))))
231       result.push_back(variants.at(i));
232   }
233   return result;
234 }
235 
236 bool all_header_reagents_strictly_match(const instruction& inst, const recipe& variant) {
237   for (int i = 0;  i < min(SIZE(inst.ingredients), SIZE(variant.ingredients));  ++i) {
238     if (!types_strictly_match(variant.ingredients.at(i), inst.ingredients.at(i))) {
239       trace(9993, "transform") << "strict match failed: ingredient " << i << end();
240       return false;
241     }
242   }
243   for (int i = 0;  i < min(SIZE(inst.products), SIZE(variant.products));  ++i) {
244     if (is_dummy(inst.products.at(i))) continue;
245     if (!types_strictly_match(variant.products.at(i), inst.products.at(i))) {
246       trace(9993, "transform") << "strict match failed: product " << i << end();
247       return false;
248     }
249   }
250   return true;
251 }
252 
253 // phase 2
254 vector<recipe_ordinal> strictly_matching_variants_except_literal_zero_against_address(const instruction& inst, vector<recipe_ordinal>& variants) {
255   vector<recipe_ordinal> result;
256   for (int i = 0;  i < SIZE(variants);  ++i) {
257     if (variants.at(i) == -1) continue;
258     trace(9992, "transform") << "checking variant (strict except literal-zero-against-address) " << i << ": " << header_label(variants.at(i)) << end();
259     if (all_header_reagents_strictly_match_except_literal_zero_against_address(inst, get(Recipe, variants.at(i))))
260       result.push_back(variants.at(i));
261   }
262   return result;
263 }
264 
265 bool all_header_reagents_strictly_match_except_literal_zero_against_address(const instruction& inst, const recipe& variant) {
266   for (int i = 0;  i < min(SIZE(inst.ingredients), SIZE(variant.ingredients));  ++i) {
267     if (!types_strictly_match_except_literal_zero_against_address(variant.ingredients.at(i), inst.ingredients.at(i))) {
268       trace(9993, "transform") << "match failed: ingredient " << i << end();
269       return false;
270     }
271   }
272   for (int i = 0;  i < min(SIZE(inst.products), SIZE(variant.products));  ++i) {
273     if (is_dummy(inst.products.at(i))) continue;
274     if (!types_strictly_match(variant.products.at(i), inst.products.at(i))) {
275       trace(9993, "transform") << "match failed: product " << i << end();
276       return false;
277     }
278   }
279   return true;
280 }
281 
282 bool types_strictly_match_except_literal_zero_against_address(const reagent& to, const reagent& from) {
283   if (is_literal(from) && is_mu_address(to))
284     return from.name == "0";
285   return types_strictly_match(to, from);
286 }
287 
288 // phase 4
289 vector<recipe_ordinal> strictly_matching_variants_except_literal_against_address_or_boolean(const instruction& inst, vector<recipe_ordinal>& variants) {
290   vector<recipe_ordinal> result;
291   for (int i = 0;  i < SIZE(variants);  ++i) {
292     if (variants.at(i) == -1) continue;
293     trace(9992, "transform") << "checking variant (strict except literal-against-boolean) " << i << ": " << header_label(variants.at(i)) << end();
294     if (all_header_reagents_strictly_match_except_literal_against_address_or_boolean(inst, get(Recipe, variants.at(i))))
295       result.push_back(variants.at(i));
296   }
297   return result;
298 }
299 
300 bool all_header_reagents_strictly_match_except_literal_against_address_or_boolean(const instruction& inst, const recipe& variant) {
301   for (int i = 0;  i < min(SIZE(inst.ingredients), SIZE(variant.ingredients));  ++i) {
302     if (!types_strictly_match_except_literal_against_address_or_boolean(variant.ingredients.at(i), inst.ingredients.at(i))) {
303       trace(9993, "transform") << "match failed: ingredient " << i << end();
304       return false;
305     }
306   }
307   for (int i = 0;  i < min(SIZE(variant.products), SIZE(inst.products));  ++i) {
308     if (is_dummy(inst.products.at(i))) continue;
309     if (!types_strictly_match_except_literal_against_address_or_boolean(variant.products.at(i), inst.products.at(i))) {
310       trace(9993, "transform") << "match failed: product " << i << end();
311       return false;
312     }
313   }
314   return true;
315 }
316 
317 bool types_strictly_match_except_literal_against_address_or_boolean(const reagent& to, const reagent& from) {
318   if (is_literal(from) && is_mu_boolean(to))
319     return from.name == "0" || from.name == "1";
320   return types_strictly_match_except_literal_zero_against_address(to, from);
321 }
322 
323 // phase 5
324 vector<recipe_ordinal> matching_variants(const instruction& inst, vector<recipe_ordinal>& variants) {
325   vector<recipe_ordinal> result;
326   for (int i = 0;  i < SIZE(variants);  ++i) {
327     if (variants.at(i) == -1) continue;
328     trace(9992, "transform") << "checking variant " << i << ": " << header_label(variants.at(i)) << end();
329     if (all_header_reagents_match(inst, get(Recipe, variants.at(i))))
330       result.push_back(variants.at(i));
331   }
332   return result;
333 }
334 
335 bool all_header_reagents_match(const instruction& inst, const recipe& variant) {
336   for (int i = 0;  i < min(SIZE(inst.ingredients), SIZE(variant.ingredients));  ++i) {
337     if (!types_match(variant.ingredients.at(i), inst.ingredients.at(i))) {
338       trace(9993, "transform") << "match failed: ingredient " << i << end();
339       return false;
340     }
341   }
342   for (int i = 0;  i < min(SIZE(variant.products), SIZE(inst.products));  ++i) {
343     if (is_dummy(inst.products.at(i))) continue;
344     if (!types_match(variant.products.at(i), inst.products.at(i))) {
345       trace(9993, "transform") << "match failed: product " << i << end();
346       return false;
347     }
348   }
349   return true;
350 }
351 
352 // tie-breaker for each phase
353 const recipe& best_variant(const instruction& inst, vector<recipe_ordinal>& candidates) {
354   assert(!candidates.empty());
355   int min_score = 999;
356   int min_index = 0;
357   for (int i = 0;  i < SIZE(candidates);  ++i) {
358     const recipe& candidate = get(Recipe, candidates.at(i));
359     int score = abs(SIZE(candidate.products)-SIZE(inst.products))
360                           + abs(SIZE(candidate.ingredients)-SIZE(inst.ingredients));
361     assert(score < 999);
362     if (score < min_score) {
363       min_score = score;
364       min_index = i;
365     }
366   }
367   return get(Recipe, candidates.at(min_index));
368 }
369 
370 int non_ghost_size(vector<recipe_ordinal>& variants) {
371   int result = 0;
372   for (int i = 0;  i < SIZE(variants);  ++i)
373     if (variants.at(i) != -1) ++result;
374   return result;
375 }
376 
377 bool next_stash(const call& c, instruction* stash_inst) {
378   const recipe& specializer_recipe = get(Recipe, c.running_recipe);
379   int index = c.running_step_index;
380   for (++index;  index < SIZE(specializer_recipe.steps);  ++index) {
381     const instruction& inst = specializer_recipe.steps.at(index);
382     if (inst.name == "stash") {
383       *stash_inst = inst;
384       return true;
385     }
386   }
387   return false;
388 }
389 
390 :(scenario static_dispatch_disabled_in_recipe_without_variants)
391 def main [
392   1:num <- test 3
393 ]
394 def test [
395   2:num <- next-ingredient  # ensure no header
396   return 34
397 ]
398 +mem: storing 34 in location 1
399 
400 :(scenario static_dispatch_disabled_on_headerless_definition)
401 % Hide_errors = true;
402 def test a:num -> z:num [
403   z <- copy 1
404 ]
405 def test [
406   return 34
407 ]
408 +error: redefining recipe test
409 
410 :(scenario static_dispatch_disabled_on_headerless_definition_2)
411 % Hide_errors = true;
412 def test [
413   return 34
414 ]
415 def test a:num -> z:num [
416   z <- copy 1
417 ]
418 +error: redefining recipe test
419 
420 :(scenario static_dispatch_on_primitive_names)
421 def main [
422   1:num <- copy 34
423   2:num <- copy 34
424   3:bool <- equal 1:num, 2:num
425   4:bool <- copy 0/false
426   5:bool <- copy 0/false
427   6:bool <- equal 4:bool, 5:bool
428 ]
429 # temporarily hardcode number equality to always fail
430 def equal x:num, y:num -> z:bool [
431   local-scope
432   load-ingredients
433   z <- copy 0/false
434 ]
435 # comparing numbers used overload
436 +mem: storing 0 in location 3
437 # comparing booleans continues to use primitive
438 +mem: storing 1 in location 6
439 
440 :(scenario static_dispatch_works_with_dummy_results_for_containers)
441 def main [
442   _ <- test 3, 4
443 ]
444 def test a:num -> z:point [
445   local-scope
446   load-ingredients
447   z <- merge a, 0
448 ]
449 def test a:num, b:num -> z:point [
450   local-scope
451   load-ingredients
452   z <- merge a, b
453 ]
454 $error: 0
455 
456 :(scenario static_dispatch_works_with_compound_type_containing_container_defined_after_first_use)
457 def main [
458   x:&:foo <- new foo:type
459   test x
460 ]
461 container foo [
462   x:num
463 ]
464 def test a:&:foo -> z:num [
465   local-scope
466   load-ingredients
467   z:num <- get *a, x:offset
468 ]
469 $error: 0
470 
471 :(scenario static_dispatch_works_with_compound_type_containing_container_defined_after_second_use)
472 def main [
473   x:&:foo <- new foo:type
474   test x
475 ]
476 def test a:&:foo -> z:num [
477   local-scope
478   load-ingredients
479   z:num <- get *a, x:offset
480 ]
481 container foo [
482   x:num
483 ]
484 $error: 0
485 
486 :(scenario static_dispatch_prefers_literals_to_be_numbers_rather_than_addresses)
487 def main [
488   1:num <- foo 0
489 ]
490 def foo x:&:num -> y:num [
491   return 34
492 ]
493 def foo x:num -> y:num [
494   return 35
495 ]
496 +mem: storing 35 in location 1
497 
498 :(scenario static_dispatch_on_non_literal_character_ignores_variant_with_numbers)
499 % Hide_errors = true;
500 def main [
501   local-scope
502   x:char <- copy 10/newline
503   1:num/raw <- foo x
504 ]
505 def foo x:num -> y:num [
506   load-ingredients
507   return 34
508 ]
509 +error: main: ingredient 0 has the wrong type at '1:num/raw <- foo x'
510 -mem: storing 34 in location 1
511 
512 :(scenario static_dispatch_dispatches_literal_to_boolean_before_character)
513 def main [
514   1:num/raw <- foo 0  # valid literal for boolean
515 ]
516 def foo x:char -> y:num [
517   local-scope
518   load-ingredients
519   return 34
520 ]
521 def foo x:bool -> y:num [
522   local-scope
523   load-ingredients
524   return 35
525 ]
526 # boolean variant is preferred
527 +mem: storing 35 in location 1
528 
529 :(scenario static_dispatch_dispatches_literal_to_character_when_out_of_boolean_range)
530 def main [
531   1:num/raw <- foo 97  # not a valid literal for boolean
532 ]
533 def foo x:char -> y:num [
534   local-scope
535   load-ingredients
536   return 34
537 ]
538 def foo x:bool -> y:num [
539   local-scope
540   load-ingredients
541   return 35
542 ]
543 # character variant is preferred
544 +mem: storing 34 in location 1
545 
546 :(scenario static_dispatch_dispatches_literal_to_number_if_at_all_possible)
547 def main [
548   1:num/raw <- foo 97
549 ]
550 def foo x:char -> y:num [
551   local-scope
552   load-ingredients
553   return 34
554 ]
555 def foo x:num -> y:num [
556   local-scope
557   load-ingredients
558   return 35
559 ]
560 # number variant is preferred
561 +mem: storing 35 in location 1
562 
563 :(code)
564 string header_label(const recipe_ordinal r) {
565   return header_label(get(Recipe, r));
566 }
567 string header_label(const recipe& caller) {
568   ostringstream out;
569   out << "recipe " << caller.name;
570   for (int i = 0;  i < SIZE(caller.ingredients);  ++i)
571     out << ' ' << to_string(caller.ingredients.at(i));
572   if (!caller.products.empty()) out << " ->";
573   for (int i = 0;  i < SIZE(caller.products);  ++i)
574     out << ' ' << to_string(caller.products.at(i));
575   return out.str();
576 }
577 
578 :(scenario reload_variant_retains_other_variants)
579 def main [
580   1:num <- copy 34
581   2:num <- foo 1:num
582 ]
583 def foo x:num -> y:num [
584   local-scope
585   load-ingredients
586   return 34
587 ]
588 def foo x:&:num -> y:num [
589   local-scope
590   load-ingredients
591   return 35
592 ]
593 def! foo x:&:num -> y:num [
594   local-scope
595   load-ingredients
596   return 36
597 ]
598 +mem: storing 34 in location 2
599 $error: 0
600 
601 :(scenario dispatch_errors_come_after_unknown_name_errors)
602 % Hide_errors = true;
603 def main [
604   y:num <- foo x
605 ]
606 def foo a:num -> b:num [
607   local-scope
608   load-ingredients
609   return 34
610 ]
611 def foo a:bool -> b:num [
612   local-scope
613   load-ingredients
614   return 35
615 ]
616 +error: main: missing type for 'x' in 'y:num <- foo x'
617 +error: main: failed to find a matching call for 'y:num <- foo x'
618 
619 :(scenario override_methods_with_type_abbreviations)
620 def main [
621   local-scope
622   s:text <- new [abc]
623   1:num/raw <- foo s
624 ]
625 def foo a:address:array:character -> result:number [
626   return 34
627 ]
628 # identical to previous variant once you take type abbreviations into account
629 def! foo a:text -> result:num [
630   return 35
631 ]
632 +mem: storing 35 in location 1
633 
634 :(before "End Includes")
635 using std::abs;