1 //:: Container definitions can contain 'type ingredients'
  2 
  3 //: pre-requisite: extend our notion of containers to not necessarily be
  4 //: atomic types
  5 :(after "Update GET base_type in Check")
  6 base_type = get_base_type(base_type);
  7 :(after "Update GET base_type in Run")
  8 base_type = get_base_type(base_type);
  9 :(after "Update PUT base_type in Check")
 10 base_type = get_base_type(base_type);
 11 :(after "Update PUT base_type in Run")
 12 base_type = get_base_type(base_type);
 13 :(after "Update MAYBE_CONVERT base_type in Check")
 14 base_type = get_base_type(base_type);
 15 :(after "Update base_type in element_type")
 16 base_type = get_base_type(base_type);
 17 :(after "Update base_type in skip_addresses")
 18 base_type = get_base_type(base_type);
 19 :(replace{} "const type_tree* get_base_type(const type_tree* t)")
 20 const type_tree* get_base_type(const type_tree* t) {
 21   const type_tree* result = t->atom ? t : t->left;
 22   if (!result->atom)
 23     raise << "invalid type " << to_string(t) << '\n' << end();
 24   return result;
 25 }
 26 
 27 :(scenario ill_formed_container)
 28 % Hide_errors = true;
 29 def main [
 30   {1: ((foo) num)} <- copy 0
 31 ]
 32 # no crash
 33 
 34 //: update size_of to handle non-atom container types
 35 
 36 :(scenario size_of_shape_shifting_container)
 37 container foo:_t [
 38   x:_t
 39   y:num
 40 ]
 41 def main [
 42   1:foo:num <- merge 12, 13
 43   3:foo:point <- merge 14, 15, 16
 44 ]
 45 +mem: storing 12 in location 1
 46 +mem: storing 13 in location 2
 47 +mem: storing 14 in location 3
 48 +mem: storing 15 in location 4
 49 +mem: storing 16 in location 5
 50 
 51 :(scenario size_of_shape_shifting_container_2)
 52 # multiple type ingredients
 53 container foo:_a:_b [
 54   x:_a
 55   y:_b
 56 ]
 57 def main [
 58   1:foo:num:bool <- merge 34, true
 59 ]
 60 $error: 0
 61 
 62 :(scenario size_of_shape_shifting_container_3)
 63 container foo:_a:_b [
 64   x:_a
 65   y:_b
 66 ]
 67 def main [
 68   1:text <- new [abc]
 69   # compound types for type ingredients
 70   {3: (foo number (address array character))} <- merge 34/x, 1:text/y
 71 ]
 72 $error: 0
 73 
 74 :(scenario size_of_shape_shifting_container_4)
 75 container foo:_a:_b [
 76   x:_a
 77   y:_b
 78 ]
 79 container bar:_a:_b [
 80   # dilated element
 81   {data: (foo _a (address _b))}
 82 ]
 83 def main [
 84   1:text <- new [abc]
 85   3:bar:num:@:char <- merge 34/x, 1:text/y
 86 ]
 87 $error: 0
 88 
 89 :(scenario shape_shifting_container_extend)
 90 container foo:_a [
 91   x:_a
 92 ]
 93 container foo:_a [
 94   y:_a
 95 ]
 96 $error: 0
 97 
 98 :(scenario shape_shifting_container_extend_error)
 99 % Hide_errors = true;
100 container foo:_a [
101   x:_a
102 ]
103 container foo:_b [
104   y:_b
105 ]
106 +error: headers of container 'foo' must use identical type ingredients
107 
108 :(scenario type_ingredient_must_start_with_underscore)
109 % Hide_errors = true;
110 container foo:t [
111   x:num
112 ]
113 +error: foo: type ingredient 't' must begin with an underscore
114 
115 :(before "End Globals")
116 // We'll use large type ordinals to mean "the following type of the variable".
117 // For example, if we have a generic type called foo:_elem, the type
118 // ingredient _elem in foo's type_info will have value START_TYPE_INGREDIENTS,
119 // and we'll handle it by looking in the current reagent for the next type
120 // that appears after foo.
121 extern const int START_TYPE_INGREDIENTS = 2000;
122 :(before "End Commandline Parsing")  // after loading .mu files
123 assert(Next_type_ordinal < START_TYPE_INGREDIENTS);
124 
125 :(before "End type_info Fields")
126 map<string, type_ordinal> type_ingredient_names;
127 
128 //: Suppress unknown type checks in shape-shifting containers.
129 
130 :(before "Check Container Field Types(info)")
131 if (!info.type_ingredient_names.empty()) continue;
132 
133 :(before "End container Name Refinements")
134 if (name.find(':') != string::npos) {
135   trace("parse") << "container has type ingredients; parsing" << end();
136   if (!read_type_ingredients(name, command)) {
137     // error; skip rest of the container definition and continue
138     slurp_balanced_bracket(in);
139     return;
140   }
141 }
142 
143 :(code)
144 bool read_type_ingredients(string& name, const string& command) {
145   string save_name = name;
146   istringstream in(save_name);
147   name = slurp_until(in, ':');
148   map<string, type_ordinal> type_ingredient_names;
149   if (!slurp_type_ingredients(in, type_ingredient_names, name)) {
150     return false;
151   }
152   if (contains_key(Type_ordinal, name)
153       && contains_key(Type, get(Type_ordinal, name))) {
154     const type_info& previous_info = get(Type, get(Type_ordinal, name));
155     // we've already seen this container; make sure type ingredients match
156     if (!type_ingredients_match(type_ingredient_names, previous_info.type_ingredient_names)) {
157       raise << "headers of " << command << " '" << name << "' must use identical type ingredients\n" << end();
158       return false;
159     }
160     return true;
161   }
162   // we haven't seen this container before
163   if (!contains_key(Type_ordinal, name) || get(Type_ordinal, name) == 0)
164     put(Type_ordinal, name, Next_type_ordinal++);
165   type_info& info = get_or_insert(Type, get(Type_ordinal, name));
166   info.type_ingredient_names.swap(type_ingredient_names);
167   return true;
168 }
169 
170 bool slurp_type_ingredients(istream& in, map<string, type_ordinal>& out, const string& container_name) {
171   int next_type_ordinal = START_TYPE_INGREDIENTS;
172   while (has_data(in)) {
173     string curr = slurp_until(in, ':');
174     if (curr.empty()) {
175       raise << container_name << ": empty type ingredients not permitted\n" << end();
176       return false;
177     }
178     if (!starts_with(curr, "_")) {
179       raise << container_name << ": type ingredient '" << curr << "' must begin with an underscore\n" << end();
180       return false;
181     }
182     if (out.find(curr) != out.end()) {
183       raise << container_name << ": can't repeat type ingredient name'" << curr << "' in a single container definition\n" << end();
184       return false;
185     }
186     put(out, curr, next_type_ordinal++);
187   }
188   return true;
189 }
190 
191 bool type_ingredients_match(const map<string, type_ordinal>& a, const map<string, type_ordinal>& b) {
192   if (SIZE(a) != SIZE(b)) return false;
193   for (map<string, type_ordinal>::const_iterator p = a.begin();  p != a.end();  ++p) {
194     if (!contains_key(b, p->first)) return false;
195     if (p->second != get(b, p->first)) return false;
196   }
197   return true;
198 }
199 
200 :(before "End insert_container Special-cases")
201 // check for use of type ingredients
202 else if (is_type_ingredient_name(type->name)) {
203   type->value = get(info.type_ingredient_names, type->name);
204 }
205 :(code)
206 bool is_type_ingredient_name(const string& type) {
207   return starts_with(type, "_");
208 }
209 
210 :(before "End Container Type Checks")
211 if (type->value >= START_TYPE_INGREDIENTS
212     && (type->value - START_TYPE_INGREDIENTS) < SIZE(get(Type, type->value).type_ingredient_names))
213   return;
214 
215 :(scenario size_of_shape_shifting_exclusive_container)
216 exclusive-container foo:_t [
217   x:_t
218   y:num
219 ]
220 def main [
221   1:foo:num <- merge 0/x, 34
222   3:foo:point <- merge 0/x, 15, 16
223   6:foo:point <- merge 1/y, 23
224 ]
225 +run: {1: ("foo" "number")} <- merge {0: "literal", "x": ()}, {34: "literal"}
226 +mem: storing 0 in location 1
227 +mem: storing 34 in location 2
228 +run: {3: ("foo" "point")} <- merge {0: "literal", "x": ()}, {15: "literal"}, {16: "literal"}
229 +mem: storing 0 in location 3
230 +mem: storing 15 in location 4
231 +mem: storing 16 in location 5
232 +run: {6: ("foo" "point")} <- merge {1: "literal", "y": ()}, {23: "literal"}
233 +mem: storing 1 in location 6
234 +mem: storing 23 in location 7
235 +run: return
236 # no other stores
237 % CHECK_EQ(trace_count_prefix("mem", "storing"), 7);
238 
239 :(before "End variant_type Special-cases")
240 if (contains_type_ingredient(element))
241   replace_type_ingredients(element.type, type->right, info, " while computing variant type of exclusive-container");
242 
243 :(scenario get_on_shape_shifting_container)
244 container foo:_t [
245   x:_t
246   y:num
247 ]
248 def main [
249   1:foo:point <- merge 14, 15, 16
250   4:num <- get 1:foo:point, y:offset
251 ]
252 +mem: storing 16 in location 4
253 
254 :(scenario get_on_shape_shifting_container_2)
255 container foo:_t [
256   x:_t
257   y:num
258 ]
259 def main [
260   1:foo:point <- merge 14, 15, 16
261   4:point <- get 1:foo:point, x:offset
262 ]
263 +mem: storing 14 in location 4
264 +mem: storing 15 in location 5
265 
266 :(scenario get_on_shape_shifting_container_3)
267 container foo:_t [
268   x:_t
269   y:num
270 ]
271 def main [
272   1:num/alloc-id, 2:num <- copy 0, 34
273   3:foo:&:point <- merge 1:&:point, 48
274   6:&:point <- get 1:foo:&:point, x:offset
275 ]
276 +mem: storing 0 in location 6
277 +mem: storing 34 in location 7
278 
279 :(scenario get_on_shape_shifting_container_inside_container)
280 container foo:_t [
281   x:_t
282   y:num
283 ]
284 container bar [
285   x:foo:point
286   y:num
287 ]
288 def main [
289   1:bar <- merge 14, 15, 16, 17
290   5:num <- get 1:bar, 1:offset
291 ]
292 +mem: storing 17 in location 5
293 
294 :(scenario get_on_complex_shape_shifting_container)
295 container foo:_a:_b [
296   x:_a
297   y:_b
298 ]
299 def main [
300   1:text <- new [abc]
301   {3: (foo number (address array character))} <- merge 34/x, 1:text/y
302   6:text <- get {3: (foo number (address array character))}, y:offset
303   8:bool <- equal 1:text, 6:text
304 ]
305 +mem: storing 1 in location 8
306 
307 :(before "End element_type Special-cases")
308 replace_type_ingredients(element, type, info, " while computing element type of container");
309 
310 :(before "End size_of(type) Non-atom Special-cases")
311 assert(type->left->atom);
312 if (!contains_key(Type, type->left->value)) {
313   raise << "no such type " << type->left->value << '\n' << end();
314   return 0;
315 }
316 type_info t = get(Type, type->left->value);
317 if (t.kind == CONTAINER) {
318   // size of a container is the sum of the sizes of its elements
319   int result = 0;
320   for (int i = 0; i < SIZE(t.elements); ++i) {
321     // todo: strengthen assertion to disallow mutual type recursion
322     if (get_base_type(t.elements.at(i).type)->value == get_base_type(type)->value) {
323       raise << "container " << t.name << " can't include itself as a member\n" << end();
324       return 0;
325     }
326     result += size_of(element_type(type, i));
327   }
328   return result;
329 }
330 if (t.kind == EXCLUSIVE_CONTAINER) {
331   // size of an exclusive container is the size of its largest variant
332   // (So like containers, it can't contain arrays.)
333   int result = 0;
334   for (int i = 0; i < SIZE(t.elements); ++i) {
335     reagent tmp;
336     tmp.type = new type_tree(*type);
337     int size = size_of(variant_type(tmp, i));
338     if (size > result) result = size;
339   }
340   // ...+1 for its tag.
341   return result+1;
342 }
343 
344 :(scenario complex_shape_shifting_exclusive_container)
345 exclusive-container foo:_a [
346   x:_a
347   y:num
348 ]
349 def main [
350   1:text <- new [abc]
351   3:foo:point <- merge 0/variant, 34/xx, 35/xy
352   10:point, 20:bool <- maybe-convert 3:foo:point, 0/variant
353 ]
354 +mem: storing 1 in location 20
355 +mem: storing 35 in location 11
356 
357 :(code)
358 bool contains_type_ingredient(const reagent& x) {
359   return contains_type_ingredient(x.type);
360 }
361 
362 bool contains_type_ingredient(const type_tree* type) {
363   if (!type) return false;
364   if (type->atom) return type->value >= START_TYPE_INGREDIENTS;
365   return contains_type_ingredient(type->left) || contains_type_ingredient(type->right);
366 }
367 
368 void replace_type_ingredients(reagent& element, const type_tree* caller_type, const type_info& info, const string& location_for_error_messages) {
369   if (contains_type_ingredient(element)) {
370     if (!caller_type->right)
371       raise << "illegal type " << names_to_string(caller_type) << " seems to be missing a type ingredient or three" << location_for_error_messages << '\n' << end();
372     replace_type_ingredients(element.type, caller_type->right, info, location_for_error_messages);
373   }
374 }
375 
376 // replace all type_ingredients in element_type with corresponding elements of callsite_type
377 void replace_type_ingredients(type_tree* element_type, const type_tree* callsite_type, const type_info& container_info, const string& location_for_error_messages) {
378   if (!callsite_type) return;  // error but it's already been raised above
379   if (!element_type) return;
380   if (!element_type->atom) {
381     if (element_type->right == NULL && is_type_ingredient(element_type->left)) {
382       int type_ingredient_index = to_type_ingredient_index(element_type->left);
383       if (corresponding(callsite_type, type_ingredient_index, is_final_type_ingredient(type_ingredient_index, container_info))->right) {
384         // replacing type ingredient at end of list, and replacement is a non-degenerate compound type -- (a b) but not (a)
385         replace_type_ingredient_at(type_ingredient_index, element_type, callsite_type, container_info, location_for_error_messages);
386         return;
387       }
388     }
389     replace_type_ingredients(element_type->left, callsite_type, container_info, location_for_error_messages);
390     replace_type_ingredients(element_type->right, callsite_type, container_info, location_for_error_messages);
391     return;
392   }
393   if (is_type_ingredient(element_type))
394     replace_type_ingredient_at(to_type_ingredient_index(element_type), element_type, callsite_type, container_info, location_for_error_messages);
395 }
396 
397 const type_tree* corresponding(const type_tree* type, int index, bool final) {
398   for (const type_tree* curr = type;  curr;  curr = curr->right, --index) {
399     assert_for_now(!curr->atom);
400     if (index == 0)
401       return final ? curr : curr->left;
402   }
403   assert_for_now(false);
404 }
405 
406 bool is_type_ingredient(const type_tree* type) {
407   return type->atom && type->value >= START_TYPE_INGREDIENTS;
408 }
409 
410 int to_type_ingredient_index(const type_tree* type) {
411   assert(type->atom);
412   return type->value-START_TYPE_INGREDIENTS;
413 }
414 
415 void replace_type_ingredient_at(const int type_ingredient_index, type_tree* element_type, const type_tree* callsite_type, const type_info& container_info, const string& location_for_error_messages) {
416   if (!has_nth_type(callsite_type, type_ingredient_index)) {
417     raise << "illegal type " << names_to_string(callsite_type) << " seems to be missing a type ingredient or three" << location_for_error_messages << '\n' << end();
418     return;
419   }
420   *element_type = *nth_type_ingredient(callsite_type, type_ingredient_index, container_info);
421 }
422 
423 const type_tree* nth_type_ingredient(const type_tree* callsite_type, int type_ingredient_index, const type_info& container_info) {
424   bool final = is_final_type_ingredient(type_ingredient_index, container_info);
425   const type_tree* curr = callsite_type;
426   for (int i = 0;  i < type_ingredient_index;  ++i) {
427     assert(curr);
428     assert(!curr->atom);
429 //?     cerr << "type ingredient " << i << " is " << to_string(curr->left) << '\n';
430     curr = curr->right;
431   }
432   assert(curr);
433   if (curr->atom) return curr;
434   if (!final) return curr->left;
435   if (!curr->right) return curr->left;
436   return curr;
437 }
438 
439 bool is_final_type_ingredient(int type_ingredient_index, const type_info& container_info) {
440   for (map<string, type_ordinal>::const_iterator p = container_info.type_ingredient_names.begin();
441        p != container_info.type_ingredient_names.end();
442        ++p) {
443     if (p->second > START_TYPE_INGREDIENTS+type_ingredient_index) return false;
444   }
445   return true;
446 }
447 
448 :(before "End Unit Tests")
449 void test_replace_type_ingredients_entire() {
450   run("container foo:_elem [\n"
451       "  x:_elem\n"
452       "  y:num\n"
453       "]\n");
454   reagent callsite("x:foo:point");
455   reagent element = element_type(callsite.type, 0);
456   CHECK_EQ(to_string(element), "{x: \"point\"}");
457 }
458 
459 void test_replace_type_ingredients_tail() {
460   run("container foo:_elem [\n"
461       "  x:_elem\n"
462       "]\n"
463       "container bar:_elem [\n"
464       "  x:foo:_elem\n"
465       "]\n");
466   reagent callsite("x:bar:point");
467   reagent element = element_type(callsite.type, 0);
468   CHECK_EQ(to_string(element), "{x: (\"foo\" \"point\")}");
469 }
470 
471 void test_replace_type_ingredients_head_tail_multiple() {
472   run("container foo:_elem [\n"
473       "  x:_elem\n"
474       "]\n"
475       "container bar:_elem [\n"
476       "  x:foo:_elem\n"
477       "]\n");
478   reagent callsite("x:bar:address:array:character");
479   reagent element = element_type(callsite.type, 0);
480   CHECK_EQ(to_string(element), "{x: (\"foo\" \"address\" \"array\" \"character\")}");
481 }
482 
483 void test_replace_type_ingredients_head_middle() {
484   run("container foo:_elem [\n"
485       "  x:_elem\n"
486       "]\n"
487       "container bar:_elem [\n"
488       "  x:foo:_elem:num\n"
489       "]\n");
490   reagent callsite("x:bar:address");
491   reagent element = element_type(callsite.type, 0);
492   CHECK_EQ(to_string(element), "{x: (\"foo\" \"address\" \"number\")}");
493 }
494 
495 void test_replace_last_type_ingredient_with_multiple() {
496   run("container foo:_a:_b [\n"
497       "  x:_a\n"
498       "  y:_b\n"
499       "]\n");
500   reagent callsite("{f: (foo number (address array character))}");
501   reagent element1 = element_type(callsite.type, 0);
502   CHECK_EQ(to_string(element1), "{x: \"number\"}");
503   reagent element2 = element_type(callsite.type, 1);
504   CHECK_EQ(to_string(element2), "{y: (\"address\" \"array\" \"character\")}");
505 }
506 
507 void test_replace_last_type_ingredient_inside_compound() {
508   run("container foo:_a:_b [\n"
509       "  {x: (bar _a (address _b))}\n"
510       "]\n");
511   reagent callsite("f:foo:number:array:character");
512   reagent element = element_type(callsite.type, 0);
513   CHECK_EQ(names_to_string_without_quotes(element.type), "(bar number (address array character))");
514 }
515 
516 void test_replace_middle_type_ingredient_with_multiple() {
517   run("container foo:_a:_b:_c [\n"
518       "  x:_a\n"
519       "  y:_b\n"
520       "  z:_c\n"
521       "]\n");
522   reagent callsite("{f: (foo number (address array character) boolean)}");
523   reagent element1 = element_type(callsite.type, 0);
524   CHECK_EQ(to_string(element1), "{x: \"number\"}");
525   reagent element2 = element_type(callsite.type, 1);
526   CHECK_EQ(to_string(element2), "{y: (\"address\" \"array\" \"character\")}");
527   reagent element3 = element_type(callsite.type, 2);
528   CHECK_EQ(to_string(element3), "{z: \"boolean\"}");
529 }
530 
531 void test_replace_middle_type_ingredient_with_multiple2() {
532   run("container foo:_key:_value [\n"
533       "  key:_key\n"
534       "  value:_value\n"
535       "]\n");
536   reagent callsite("{f: (foo (address array character) number)}");
537   reagent element = element_type(callsite.type, 0);
538   CHECK_EQ(to_string(element), "{key: (\"address\" \"array\" \"character\")}");
539 }
540 
541 void test_replace_middle_type_ingredient_with_multiple3() {
542   run("container foo_table:_key:_value [\n"
543       "  data:&:@:foo_table_row:_key:_value\n"
544       "]\n"
545       "\n"
546       "container foo_table_row:_key:_value [\n"
547       "  key:_key\n"
548       "  value:_value\n"
549       "]\n");
550   reagent callsite("{f: (foo_table (address array character) number)}");
551   reagent element = element_type(callsite.type, 0);
552   CHECK_EQ(to_string(element), "{data: (\"address\" \"array\" \"foo_table_row\" (\"address\" \"array\" \"character\") \"number\")}");
553 }
554 
555 :(code)
556 bool has_nth_type(const type_tree* base, int n) {
557   assert(n >= 0);
558   if (!base) return false;
559   if (n == 0) return true;
560   return has_nth_type(base->right, n-1);
561 }
562 
563 :(scenario get_on_shape_shifting_container_error)
564 % Hide_errors = true;
565 container foo:_t [
566   x:_t
567   y:num
568 ]
569 def main [
570   1:foo:point <- merge 14, 15, 16
571   10:num <- get 1:foo, 1:offset
572 ]
573 # todo: improve error message
574 +error: illegal type "foo" seems to be missing a type ingredient or three while computing element type of container
575 
576 :(scenario typos_in_container_definitions)
577 % Hide_errors = true;
578 container foo:_t [
579   x:adress:_t  # typo
580 ]
581 def main [
582   local-scope
583   x:address:foo:num <- new {(foo num): type}
584 ]
585 # no crash
586 
587 :(scenario typos_in_recipes)
588 % Hide_errors = true;
589 def foo [
590   local-scope
591   x:adress:array:number <- copy null  # typo
592 ]
593 # shouldn't crash
594 
595 //:: 'merge' on shape-shifting containers
596 
597 :(scenario merge_check_shape_shifting_container_containing_exclusive_container)
598 container foo:_elem [
599   x:num
600   y:_elem
601 ]
602 exclusive-container bar [
603   x:num
604   y:num
605 ]
606 def main [
607   1:foo:bar <- merge 23, 1/y, 34
608 ]
609 +mem: storing 23 in location 1
610 +mem: storing 1 in location 2
611 +mem: storing 34 in location 3
612 $error: 0
613 
614 :(scenario merge_check_shape_shifting_container_containing_exclusive_container_2)
615 % Hide_errors = true;
616 container foo:_elem [
617   x:num
618   y:_elem
619 ]
620 exclusive-container bar [
621   x:num
622   y:num
623 ]
624 def main [
625   1:foo:bar <- merge 23, 1/y, 34, 35
626 ]
627 +error: main: too many ingredients in '1:foo:bar <- merge 23, 1/y, 34, 35'
628 
629 :(scenario merge_check_shape_shifting_exclusive_container_containing_container)
630 exclusive-container foo:_elem [
631   x:num
632   y:_elem
633 ]
634 container bar [
635   x:num
636   y:num
637 ]
638 def main [
639   1:foo:bar <- merge 1/y, 23, 34
640 ]
641 +mem: storing 1 in location 1
642 +mem: storing 23 in location 2
643 +mem: storing 34 in location 3
644 $error: 0
645 
646 :(scenario merge_check_shape_shifting_exclusive_container_containing_container_2)
647 exclusive-container foo:_elem [
648   x:num
649   y:_elem
650 ]
651 container bar [
652   x:num
653   y:num
654 ]
655 def main [
656   1:foo:bar <- merge 0/x, 23
657 ]
658 $error: 0
659 
660 :(scenario merge_check_shape_shifting_exclusive_container_containing_container_3)
661 % Hide_errors = true;
662 exclusive-container foo:_elem [
663   x:num
664   y:_elem
665 ]
666 container bar [
667   x:num
668   y:num
669 ]
670 def main [
671   1:foo:bar <- merge 1/y, 23
672 ]
673 +error: main: too few ingredients in '1:foo:bar <- merge 1/y, 23'