1 //: Arrays contain a variable number of elements of the same type. Their value
  2 //: starts with the length of the array.
  3 //:
  4 //: You can create arrays of containers, but containers can only contain
  5 //: elements of a fixed size, so you can't create containers containing arrays.
  6 //: Create containers containing addresses to arrays instead.
  7 
  8 //: You can create arrays using 'create-array'.
  9 :(scenario create_array)
 10 def main [
 11   # create an array occupying locations 1 (for the size) and 2-4 (for the elements)
 12   1:array:num:3 <- create-array
 13 ]
 14 +run: creating array from 4 locations
 15 
 16 :(before "End Primitive Recipe Declarations")
 17 CREATE_ARRAY,
 18 :(before "End Primitive Recipe Numbers")
 19 put(Recipe_ordinal, "create-array", CREATE_ARRAY);
 20 :(before "End Primitive Recipe Checks")
 21 case CREATE_ARRAY: {
 22   if (inst.products.empty()) {
 23     raise << maybe(get(Recipe, r).name) << "'create-array' needs one product and no ingredients but got '" << to_original_string(inst) << '\n' << end();
 24     break;
 25   }
 26   reagent/*copy*/ product = inst.products.at(0);
 27   // Update CREATE_ARRAY product in Check
 28   if (!is_mu_array(product)) {
 29     raise << maybe(get(Recipe, r).name) << "'create-array' cannot create non-array '" << product.original_string << "'\n" << end();
 30     break;
 31   }
 32   if (!product.type->right) {
 33     raise << maybe(get(Recipe, r).name) << "create array of what? '" << to_original_string(inst) << "'\n" << end();
 34     break;
 35   }
 36   // 'create-array' will need to check properties rather than types
 37   type_tree* array_length_from_type = product.type->right->right;
 38   if (!array_length_from_type) {
 39     raise << maybe(get(Recipe, r).name) << "create array of what size? '" << to_original_string(inst) << "'\n" << end();
 40     break;
 41   }
 42   if (!product.type->right->right->atom)
 43     array_length_from_type = array_length_from_type->left;
 44   if (!is_integer(array_length_from_type->name)) {
 45     raise << maybe(get(Recipe, r).name) << "'create-array' product should specify size of array after its element type, but got '" << product.type->right->right->name << "'\n" << end();
 46     break;
 47   }
 48   break;
 49 }
 50 :(before "End Primitive Recipe Implementations")
 51 case CREATE_ARRAY: {
 52   reagent/*copy*/ product = current_instruction().products.at(0);
 53   // Update CREATE_ARRAY product in Run
 54   int base_address = product.value;
 55   type_tree* array_length_from_type = product.type->right->right;
 56   if (!product.type->right->right->atom)
 57     array_length_from_type = array_length_from_type->left;
 58   int array_length = to_integer(array_length_from_type->name);
 59   // initialize array length, so that size_of will work
 60   trace("mem") << "storing " << array_length << " in location " << base_address << end();
 61   put(Memory, base_address, array_length);  // in array elements
 62   int size = size_of(product);  // in locations
 63   trace(9998, "run") << "creating array from " << size << " locations" << end();
 64   // initialize array
 65   for (int i = 1;  i <= size_of(product);  ++i)
 66     put(Memory, base_address+i, 0);
 67   // no need to update product
 68   write_products = false;
 69   break;
 70 }
 71 
 72 :(scenario copy_array)
 73 # Arrays can be copied around with a single instruction just like numbers,
 74 # no matter how large they are.
 75 # You don't need to pass the size around, since each array variable stores its
 76 # size in memory at run-time. We'll call a variable with an explicit size a
 77 # 'static' array, and one without a 'dynamic' array since it can contain
 78 # arrays of many different sizes.
 79 def main [
 80   1:array:num:3 <- create-array
 81   2:num <- copy 14
 82   3:num <- copy 15
 83   4:num <- copy 16
 84   5:array:num <- copy 1:array:num:3
 85 ]
 86 +mem: storing 3 in location 5
 87 +mem: storing 14 in location 6
 88 +mem: storing 15 in location 7
 89 +mem: storing 16 in location 8
 90 
 91 :(scenario stash_array)
 92 def main [
 93   1:array:num:3 <- create-array
 94   2:num <- copy 14
 95   3:num <- copy 15
 96   4:num <- copy 16
 97   stash [foo:], 1:array:num:3
 98 ]
 99 +app: foo: 3 14 15 16
100 
101 :(before "End types_coercible Special-cases")
102 if (is_mu_array(from) && is_mu_array(to))
103   return types_strictly_match(array_element(from.type), array_element(to.type));
104 
105 :(before "End size_of(reagent r) Special-cases")
106 if (!r.type->atom && r.type->left->atom && r.type->left->value == Array_type_ordinal) {
107   if (!r.type->right) {
108     raise << maybe(current_recipe_name()) << "'" << r.original_string << "' is an array of what?\n" << end();
109     return 1;
110   }
111   return /*space for length*/1 + array_length(r)*size_of(array_element(r.type));
112 }
113 
114 :(before "End size_of(type) Non-atom Special-cases")
115 if (type->left->value == Array_type_ordinal) return static_array_length(type);
116 :(code)
117 int static_array_length(const type_tree* type) {
118   if (!type->atom && type->right && !type->right->atom && type->right->right && !type->right->right->atom && !type->right->right->right  // exactly 3 types
119       && type->right->right->left && type->right->right->left->atom && is_integer(type->right->right->left->name)) {  // third 'type' is a number
120     // get size from type
121     return to_integer(type->right->right->left->name);
122   }
123   cerr << to_string(type) << '\n';
124   assert(false);
125 }
126 
127 //: disable the size mismatch check for arrays since the destination array
128 //: need not be initialized
129 :(before "End size_mismatch(x) Special-cases")
130 if (x.type && !x.type->atom && x.type->left->value == Array_type_ordinal) return false;
131 
132 //:: arrays inside containers
133 //: arrays are disallowed inside containers unless their length is fixed in
134 //: advance
135 
136 :(scenario container_permits_static_array_element)
137 container foo [
138   x:array:num:3
139 ]
140 $error: 0
141 
142 :(before "End insert_container Special-cases")
143 else if (is_integer(type->name)) {  // sometimes types will contain non-type tags, like numbers for the size of an array
144   type->value = 0;
145 }
146 
147 :(scenario container_disallows_dynamic_array_element)
148 % Hide_errors = true;
149 container foo [
150   x:array:num
151 ]
152 +error: container 'foo' cannot determine size of element 'x'
153 
154 :(before "End Load Container Element Definition")
155 {
156   const type_tree* type = info.elements.back().type;
157   if (type && type->atom && type->name == "array") {
158     raise << "container '" << name << "' doesn't specify type of array elements for '" << info.elements.back().name << "'\n" << end();
159     continue;
160   }
161   if (type && !type->atom && type->left->atom && type->left->name == "array") {
162     if (!type->right) {
163       raise << "container '" << name << "' doesn't specify type of array elements for '" << info.elements.back().name << "'\n" << end();
164       continue;
165     }
166     if (!type->right->right || !is_integer(type->right->right->left->name)) {  // array has no length
167       raise << "container '" << name << "' cannot determine size of element '" << info.elements.back().name << "'\n" << end();
168       continue;
169     }
170   }
171 }
172 
173 //: disable the size mismatch check for 'merge' instructions since containers
174 //: can contain arrays, and since we already do plenty of checking for them
175 :(before "End size_mismatch(x) Special-cases")
176 if (current_call().running_step_index < SIZE(get(Recipe, current_call().running_recipe).steps)
177     && current_instruction().operation == MERGE) {
178   return false;
179 }
180 
181 :(scenario merge_static_array_into_container)
182 container foo [
183   x:num
184   y:array:num:3
185 ]
186 def main [
187   1:array:num:3 <- create-array
188   10:foo <- merge 34, 1:array:num:3
189 ]
190 # no errors
191 
192 :(scenario code_inside_container)
193 % Hide_errors = true;
194 container card [
195   rank:num <- next-ingredient
196 ]
197 def foo [
198   1:card <- merge 3
199   2:num <- get 1:card rank:offset
200 ]
201 # shouldn't die
202 
203 //:: To access elements of an array, use 'index'
204 
205 :(scenario index)
206 def main [
207   1:array:num:3 <- create-array
208   2:num <- copy 14
209   3:num <- copy 15
210   4:num <- copy 16
211   10:num <- index 1:array:num:3, 0/index  # the index must be a non-negative whole number
212 ]
213 +mem: storing 14 in location 10
214 
215 :(scenario index_compound_element)
216 def main [
217   {1: (array (address number) 3)} <- create-array
218   # skip alloc id
219   3:num <- copy 14
220   # skip alloc id
221   5:num <- copy 15
222   # skip alloc id
223   7:num <- copy 16
224   10:address:num <- index {1: (array (address number) 3)}, 0
225 ]
226 # skip alloc id
227 +mem: storing 14 in location 11
228 
229 :(scenario index_direct_offset)
230 def main [
231   1:array:num:3 <- create-array
232   2:num <- copy 14
233   3:num <- copy 15
234   4:num <- copy 16
235   10:num <- copy 0
236   20:num <- index 1:array:num, 10:num
237 ]
238 +mem: storing 14 in location 20
239 
240 :(before "End Primitive Recipe Declarations")
241 INDEX,
242 :(before "End Primitive Recipe Numbers")
243 put(Recipe_ordinal, "index", INDEX);
244 :(before "End Primitive Recipe Checks")
245 case INDEX: {
246   if (SIZE(inst.ingredients) != 2) {
247     raise << maybe(get(Recipe, r).name) << "'index' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end();
248     break;
249   }
250   reagent/*copy*/ base = inst.ingredients.at(0);
251   // Update INDEX base in Check
252   if (!is_mu_array(base)) {
253     raise << maybe(get(Recipe, r).name) << "'index' on a non-array '" << base.original_string << "'\n" << end();
254     break;
255   }
256   reagent/*copy*/ index = inst.ingredients.at(1);
257   // Update INDEX index in Check
258   if (!is_mu_number(index)) {
259     raise << maybe(get(Recipe, r).name) << "second ingredient of 'index' should be a number, but got '" << index.original_string << "'\n" << end();
260     break;
261   }
262   if (inst.products.empty()) break;
263   reagent/*copy*/ product = inst.products.at(0);
264   // Update INDEX product in Check
265   reagent/*local*/ element(copy_array_element(base.type));
266   if (!types_coercible(product, element)) {
267     raise << maybe(get(Recipe, r).name) << "'index' on '" << base.original_string << "' can't be saved in '" << product.original_string << "'; type should be '" << names_to_string_without_quotes(element.type) << "'\n" << end();
268     break;
269   }
270   break;
271 }
272 :(before "End Primitive Recipe Implementations")
273 case INDEX: {
274   reagent/*copy*/ base = current_instruction().ingredients.at(0);
275   // Update INDEX base in Run
276   int base_address = base.value;
277   trace(9998, "run") << "base address is " << base_address << end();
278   if (base_address == 0) {
279     raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end();
280     break;
281   }
282   reagent/*copy*/ index = current_instruction().ingredients.at(1);
283   // Update INDEX index in Run
284   vector<double> index_val(read_memory(index));
285   if (index_val.at(0) < 0 || index_val.at(0) >= get_or_insert(Memory, base_address)) {
286     raise << maybe(current_recipe_name()) << "invalid index " << no_scientific(index_val.at(0)) << " in '" << to_original_string(current_instruction()) << "'\n" << end();
287     break;
288   }
289   reagent/*local*/ element(copy_array_element(base.type));
290   element.set_value(base_address + /*skip length*/1 + index_val.at(0)*size_of(element.type));
291   trace(9998, "run") << "address to copy is " << element.value << end();
292   trace(9998, "run") << "its type is " << to_string(element.type) << end();
293   // Read element
294   products.push_back(read_memory(element));
295   break;
296 }
297 
298 :(code)
299 type_tree* copy_array_element(const type_tree* type) {
300   return new type_tree(*array_element(type));
301 }
302 
303 type_tree* array_element(const type_tree* type) {
304   assert(type->right);
305   if (type->right->atom) {
306     return type->right;
307   }
308   else if (!type->right->right) {
309     return type->right->left;
310   }
311   // hack: support array:num:3 without requiring extra parens
312   else if (type->right->right->left && type->right->right->left->atom && is_integer(type->right->right->left->name)) {
313     assert(!type->right->right->right);
314     return type->right->left;
315   }
316   return type->right;
317 }
318 
319 int array_length(const reagent& x) {
320   // x should already be canonized.
321   // hack: look for length in type
322   if (!x.type->atom && x.type->right && !x.type->right->atom && x.type->right->right && !x.type->right->right->atom && !x.type->right->right->right  // exactly 3 types
323       && x.type->right->right->left && x.type->right->right->left->atom && is_integer(x.type->right->right->left->name)) {  // third 'type' is a number
324     // get size from type
325     return to_integer(x.type->right->right->left->name);
326   }
327   // this should never happen at transform time
328   return get_or_insert(Memory, x.value);
329 }
330 
331 :(before "End Unit Tests")
332 void test_array_length_compound() {
333   put(Memory, 1, 3);
334   put(Memory, 2, 14);
335   put(Memory, 3, 15);
336   put(Memory, 4, 16);
337   reagent x("1:array:address:num");  // 3 types, but not a static array
338   populate_value(x);
339   CHECK_EQ(array_length(x), 3);
340 }
341 
342 void test_array_length_static() {
343   reagent x("1:array:num:3");
344   CHECK_EQ(array_length(x), 3);
345 }
346 
347 :(scenario index_truncates)
348 def main [
349   1:array:num:3 <- create-array
350   2:num <- copy 14
351   3:num <- copy 15
352   4:num <- copy 16
353   10:num <- index 1:array:num:3, 1.5  # non-whole number
354 ]
355 # fraction is truncated away
356 +mem: storing 15 in location 10
357 
358 :(scenario index_out_of_bounds)
359 % Hide_errors = true;
360 def main [
361   1:array:point:3 <- create-array
362   index 1:array:point:3, 4  # less than size of array in locations, but larger than its length in elements
363 ]
364 +error: main: invalid index 4 in 'index 1:array:point:3, 4'
365 
366 :(scenario index_out_of_bounds_2)
367 % Hide_errors = true;
368 def main [
369   1:array:num:3 <- create-array
370   index 1:array:num, -1
371 ]
372 +error: main: invalid index -1 in 'index 1:array:num, -1'
373 
374 :(scenario index_product_type_mismatch)
375 % Hide_errors = true;
376 def main [
377   1:array:point:3 <- create-array
378   10:num <- index 1:array:point, 0
379 ]
380 +error: main: 'index' on '1:array:point' can't be saved in '10:num'; type should be 'point'
381 
382 //: we might want to call 'index' without saving the results, say in a sandbox
383 
384 :(scenario index_without_product)
385 def main [
386   1:array:num:3 <- create-array
387   index 1:array:num:3, 0
388 ]
389 # just don't die
390 
391 //:: To write to elements of arrays, use 'put'.
392 
393 :(scenario put_index)
394 def main [
395   1:array:num:3 <- create-array
396   1:array:num <- put-index 1:array:num, 1, 34
397 ]
398 +mem: storing 34 in location 3
399 
400 :(before "End Primitive Recipe Declarations")
401 PUT_INDEX,
402 :(before "End Primitive Recipe Numbers")
403 put(Recipe_ordinal, "put-index", PUT_INDEX);
404 :(before "End Primitive Recipe Checks")
405 case PUT_INDEX: {
406   if (SIZE(inst.ingredients) != 3) {
407     raise << maybe(get(Recipe, r).name) << "'put-index' expects exactly 3 ingredients in '" << to_original_string(inst) << "'\n" << end();
408     break;
409   }
410   reagent/*copy*/ base = inst.ingredients.at(0);
411   // Update PUT_INDEX base in Check
412   if (!is_mu_array(base)) {
413     raise << maybe(get(Recipe, r).name) << "'put-index' on a non-array '" << base.original_string << "'\n" << end();
414     break;
415   }
416   reagent/*copy*/ index = inst.ingredients.at(1);
417   // Update PUT_INDEX index in Check
418   if (!is_mu_number(index)) {
419     raise << maybe(get(Recipe, r).name) << "second ingredient of 'put-index' should have type 'number', but got '" << inst.ingredients.at(1).original_string << "'\n" << end();
420     break;
421   }
422   reagent/*copy*/ value = inst.ingredients.at(2);
423   // Update PUT_INDEX value in Check
424   reagent/*local*/ element(copy_array_element(base.type));
425   if (!types_coercible(element, value)) {
426     raise << maybe(get(Recipe, r).name) << "'put-index " << base.original_string << ", " << inst.ingredients.at(1).original_string << "' should store " << names_to_string_without_quotes(element.type) << " but '" << value.name << "' has type " << names_to_string_without_quotes(value.type) << '\n' << end();
427     break;
428   }
429   if (inst.products.empty()) break;  // no more checks necessary
430   if (inst.products.at(0).name != inst.ingredients.at(0).name) {
431     raise << maybe(get(Recipe, r).name) << "product of 'put-index' must be first ingredient '" << inst.ingredients.at(0).original_string << "', but got '" << inst.products.at(0).original_string << "'\n" << end();
432     break;
433   }
434   // End PUT_INDEX Product Checks
435   break;
436 }
437 :(before "End Primitive Recipe Implementations")
438 case PUT_INDEX: {
439   reagent/*copy*/ base = current_instruction().ingredients.at(0);
440   // Update PUT_INDEX base in Run
441   int base_address = base.value;
442   if (base_address == 0) {
443     raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end();
444     break;
445   }
446   reagent/*copy*/ index = current_instruction().ingredients.at(1);
447   // Update PUT_INDEX index in Run
448   vector<double> index_val(read_memory(index));
449   if (index_val.at(0) < 0 || index_val.at(0) >= get_or_insert(Memory, base_address)) {
450     raise << maybe(current_recipe_name()) << "invalid index " << no_scientific(index_val.at(0)) << " in '" << to_original_string(current_instruction()) << "'\n" << end();
451     break;
452   }
453   int address = base_address + /*skip length*/1 + index_val.at(0)*size_of(array_element(base.type));
454   trace(9998, "run") << "address to copy to is " << address << end();
455   // optimization: directly write the element rather than updating 'product'
456   // and writing the entire array
457   write_products = false;
458   vector<double> value = read_memory(current_instruction().ingredients.at(2));
459   // Write Memory in PUT_INDEX in Run
460   for (int i = 0;  i < SIZE(value);  ++i) {
461     trace("mem") << "storing " << no_scientific(value.at(i)) << " in location " << address+i << end();
462     put(Memory, address+i, value.at(i));
463   }
464   break;
465 }
466 
467 :(scenario put_index_out_of_bounds)
468 % Hide_errors = true;
469 def main [
470   1:array:point:3 <- create-array
471   8:point <- merge 34, 35
472   1:array:point <- put-index 1:array:point, 4, 8:point  # '4' is less than size of array in locations, but larger than its length in elements
473 ]
474 +error: main: invalid index 4 in '1:array:point <- put-index 1:array:point, 4, 8:point'
475 
476 :(scenario put_index_out_of_bounds_2)
477 % Hide_errors = true;
478 def main [
479   1:array:point:3 <- create-array
480   10:point <- merge 34, 35
481   1:array:point <- put-index 1:array:point, -1, 10:point
482 ]
483 +error: main: invalid index -1 in '1:array:point <- put-index 1:array:point, -1, 10:point'
484 
485 :(scenario put_index_product_error)
486 % Hide_errors = true;
487 def main [
488   1:array:num:3 <- create-array
489   4:array:num:3 <- put-index 1:array:num:3, 0, 34
490 ]
491 +error: main: product of 'put-index' must be first ingredient '1:array:num:3', but got '4:array:num:3'
492 
493 //:: compute the length of an array
494 
495 :(scenario array_length)
496 def main [
497   1:array:num:3 <- create-array
498   10:num <- length 1:array:num
499 ]
500 +mem: storing 3 in location 10
501 
502 :(before "End Primitive Recipe Declarations")
503 LENGTH,
504 :(before "End Primitive Recipe Numbers")
505 put(Recipe_ordinal, "length", LENGTH);
506 :(before "End Primitive Recipe Checks")
507 case LENGTH: {
508   if (SIZE(inst.ingredients) != 1) {
509     raise << maybe(get(Recipe, r).name) << "'length' expects exactly 2 ingredients in '" << to_original_string(inst) << "'\n" << end();
510     break;
511   }
512   reagent/*copy*/ array = inst.ingredients.at(0);
513   // Update LENGTH array in Check
514   if (!is_mu_array(array)) {
515     raise << "tried to calculate length of non-array '" << array.original_string << "'\n" << end();
516     break;
517   }
518   break;
519 }
520 :(before "End Primitive Recipe Implementations")
521 case LENGTH: {
522   reagent/*copy*/ array = current_instruction().ingredients.at(0);
523   // Update LENGTH array in Run
524   if (array.value == 0) {
525     raise << maybe(current_recipe_name()) << "tried to access location 0 in '" << to_original_string(current_instruction()) << "'\n" << end();
526     break;
527   }
528   products.resize(1);
529   products.at(0).push_back(get_or_insert(Memory, array.value));
530   break;
531 }
532 
533 //: optimization: none of the instructions in this layer use 'ingredients' so
534 //: stop copying potentially huge arrays into it.
535 :(before "End should_copy_ingredients Special-cases")
536 recipe_ordinal r = current_instruction().operation;
537 if (r == CREATE_ARRAY || r == INDEX || r == PUT_INDEX || r == LENGTH)
538   return false;