mu - Soul of a tiny new machine. More thorough tests → More comprehensible and rewrite-friendly software → More resilient society.

about summary refs log tree commit diff stats

diff options

Diffstat (limited to 'cpp/.traces/break_if')

0 files changed, 0 insertions, 0 deletions

37421f8a ^

3df1842c ^

37421f8a ^

3df1842c ^

37421f8a ^

78c50205 ^

37421f8a ^

b0bf5321 ^

067c8ed6 ^

b0bf5321 ^

37421f8a ^

b0bf5321 ^

37421f8a ^

78c50205 ^

b24eb476 ^

37421f8a ^

b24eb476 ^

3473c63a ^

f6c7b415 ^

3377364a ^

b24eb476 ^

3473c63a ^

067c8ed6 ^

37421f8a ^

37421f8a ^

af023b32 ^

b24eb476 ^

3473c63a ^

37e71785 ^

37421f8a ^

3adc9e08 ^

37421f8a ^

37421f8a ^

af023b32 ^

b24eb476 ^

3473c63a ^

05331766 ^

37e71785 ^

af023b32 ^

37421f8a ^

7a84094a ^

08f4628e ^

37421f8a ^

1ead3562 ^

37421f8a ^

7a84094a ^

37421f8a ^

7a84094a ^

37421f8a ^

7a84094a ^

37421f8a ^

7a84094a ^

37421f8a ^

1ead3562 ^

37421f8a ^

7a84094a ^

37421f8a ^

7a84094a ^

37421f8a ^

37e71785 ^

7a84094a ^

08f4628e ^

37e71785 ^

1ead3562 ^

37e71785 ^

7a84094a ^

37e71785 ^

7a84094a ^

37e71785 ^

37421f8a ^

1ead3562 ^

760f683f ^

37421f8a ^

1ead3562 ^

7a84094a ^

37421f8a ^

1ead3562 ^

7a84094a ^

a0331a9b ^

7a84094a ^

d559f68b ^

7a84094a ^

37421f8a ^

1ead3562 ^

760f683f ^

7a84094a ^

37421f8a ^

1ead3562 ^

760f683f ^

7a84094a ^

37421f8a ^

760f683f ^

7a84094a ^

37421f8a ^

7a84094a ^

08f4628e ^

37421f8a ^

7a84094a ^

08f4628e ^

37421f8a ^

1ead3562 ^

37421f8a ^

7a84094a ^

37421f8a ^

7a84094a ^

37421f8a ^

7a84094a ^

08f4628e ^

760f683f ^

37421f8a ^

1ead3562 ^

760f683f ^

7a84094a ^

760f683f ^

7a84094a ^

37421f8a ^

7a84094a ^

08f4628e ^

37421f8a ^

7a84094a ^

37421f8a ^

1ead3562 ^

37421f8a ^

7a84094a ^

37421f8a ^

7a84094a ^

37421f8a ^

7a84094a ^

37421f8a ^

7a84094a ^

37421f8a ^

1ead3562 ^

37421f8a ^

7a84094a ^

37421f8a ^

7a84094a ^

37421f8a ^

1ead3562 ^

d559f68b ^

7a84094a ^

37421f8a ^

8d72e565 ^

37421f8a ^

78c50205 ^

0f2781f8 ^

d5fe534d ^

37421f8a ^

78c50205 ^

d5fe534d ^

b24eb476 ^

d5fe534d ^

19
20

60
61
62

93
94
95

98
99
100

107
108

137
138

140
141
142

151
152

153
154

158
159

161
162
163

168
169

175
176

178
179
180

190
191

199
200
201

214
215
216

235
236
237

240
241

242
243

252
253

259
260

262
263
264

276
277
278

279
280

281
282
283

284
285
286

295
296
297

298
299

303
304

306
307
308

317
318

319
320

324
325

327
328
329

341
342
343

355
356

366
367

// A universal hash function that can handle objects of any type.
//
// The way it's currently implemented, two objects will have the same hash if
// all their non-address fields (all the way down) expand to the same sequence
// of scalar values. In particular, a container with all zero addresses hashes
// to 0. Hopefully this won't be an issue because we are usually hashing
// objects of a single type in any given hash table.
//
// Based on http://burtleburtle.net/bob/hash/hashfaq.html

:(before "End Primitive Recipe Declarations")
HASH,
:(before "End Primitive Recipe Numbers")
put(Recipe_ordinal, "hash", HASH);
:(before "End Primitive Recipe Checks")
case HASH: {
  if (SIZE(inst.ingredients) != 1) {
    raise << maybe(get(Recipe, r).name) << "'hash' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end();
    break;
  }
  break;
}
:(before "End Primitive Recipe Implementations")
case HASH: {
  const reagent& input = current_instruction().ingredients.at(0);
  products.resize(1);
  products.at(0).push_back(hash(0, input));
  break;
}

//: in all the code below, the intermediate results of hashing are threaded through 'h'

:(code)
size_t hash(size_t h, reagent/*copy*/ r) {
  canonize(r);
  if (is_mu_text(r))  // optimization
    return hash_mu_string(h, r);
  else if (is_mu_address(r))
    return hash_mu_address(h, r);
  else if (is_mu_scalar(r))
    return hash_mu_scalar(h, r);
  else if (is_mu_array(r))
    return hash_mu_array(h, r);
  else if (is_mu_container(r))
    return hash_mu_container(h, r);
  else if (is_mu_exclusive_container(r))
    return hash_mu_exclusive_container(h, r);
  assert(false);
}

size_t hash_mu_scalar(size_t h, const reagent& r) {
  double input = is_literal(r) ? r.value : get_or_insert(Memory, r.value);
  return hash_iter(h, static_cast<size_t>(input));
}

size_t hash_mu_address(size_t h, reagent& r) {
  if (r.value == 0) return 0;
  trace(9999, "mem") << "location " << r.value << " is " << no_scientific(get_or_insert(Memory, r.value)) << end();
  r.set_value(get_or_insert(Memory, r.value));
  if (r.value != 0) {
    trace(9999, "mem") << "skipping refcount at " << r.value << end();
    r.set_value(r.value+1);  // skip refcount
  }
  drop_from_type(r, "address");
  return hash(h, r);
}

size_t hash_mu_string(size_t h, const reagent& r) {
  string input = read_mu_text(get_or_insert(Memory, r.value));
  for (int i = 0; i < SIZE(input); ++i) {
    h = hash_iter(h, static_cast<size_t>(input.at(i)));
//?     cerr << i << ": " << h << '\n';
  }
  return h;
}

size_t hash_mu_array(size_t h, const reagent& r) {
  int size = get_or_insert(Memory, r.value);
  reagent/*copy*/ elem = r;
  delete elem.type;
  elem.type = copy_array_element(r.type);
  for (int i=0, address = r.value+1; i < size; ++i, address += size_of(elem)) {
    reagent/*copy*/ tmp = elem;
    tmp.set_value(address);
    h = hash(h, tmp);
//?     cerr << i << " (" << address << "): " << h << '\n';
  }
  return h;
}

size_t hash_mu_container(size_t h, const reagent& r) {
  type_info& info = get(Type, root_type(r.type)->value);
  int address = r.value;
  int offset = 0;
  for (int i = 0; i < SIZE(info.elements); ++i) {
    reagent/*copy*/ element = element_type(r.type, i);
    if (has_property(element, "ignore-for-hash")) continue;
    element.set_value(address+offset);
    h = hash(h, element);
//?     cerr << i << ": " << h << '\n';
    offset += size_of(info.elements.at(i).type);
  }
  return h;
}

size_t hash_mu_exclusive_container(size_t h, const reagent& r) {
  const type_tree* type = root_type(r.type);
  assert(type->value);
  int tag = get(Memory, r.value);
  reagent/*copy*/ variant = variant_type(r, tag);
  // todo: move this error to container definition time
  if (has_property(variant, "ignore-for-hash"))
    raise << get(Type, type->value).name << ": /ignore-for-hash won't work in exclusive containers\n" << end();
  variant.set_value(r.value + /*skip tag*/1);
  h = hash(h, variant);
  return h;
}

size_t hash_iter(size_t h, size_t input) {
  h += input;
  h += (h<<10);
  h ^= (h>>6);

  h += (h<<3);
  h ^= (h>>11);
  h += (h<<15);
  return h;
}

:(scenario hash_container_checks_all_elements)
container foo [
  x:num
  y:char
]
def main [
  1:foo <- merge 34, 97/a
  3:num <- hash 1:foo
  return-unless 3:num
  4:foo <- merge 34, 98/a
  6:num <- hash 4:foo
  return-unless 6:num
  7:bool <- equal 3:num, 6:num
]
# hash on containers includes all elements
+mem: storing 0 in location 7

:(scenario hash_exclusive_container_checks_all_elements)
exclusive-container foo [
  x:bar
  y:num
]
container bar [
  a:num
  b:num
]
def main [
  1:foo <- merge 0/x, 34, 35
  4:num <- hash 1:foo
  return-unless 4:num
  5:foo <- merge 0/x, 34, 36
  8:num <- hash 5:foo
  return-unless 8:num
  9:bool <- equal 4:num, 8:num
]
# hash on containers includes all elements
+mem: storing 0 in location 9

:(scenario hash_can_ignore_container_elements)
container foo [
  x:num
  y:char/ignore-for-hash
]
def main [
  1:foo <- merge 34, 97/a
  3:num <- hash 1:foo
  return-unless 3:num
  4:foo <- merge 34, 98/a
  6:num <- hash 4:foo
  return-unless 6:num
  7:bool <- equal 3:num, 6:num
]
# hashes match even though y is different
+mem: storing 1 in location 7

//: These properties aren't necessary for hash, they just test that the
//: current implementation works like we think it does.

:(scenario hash_of_zero_address)
def main [
  1:&:num <- copy 0
  2:num <- hash 1:&:num
]
+mem: storing 0 in location 2

//: This is probably too aggressive, but we need some way to avoid depending
//: on the precise bit pattern of a floating-point number.
:(scenario hash_of_numbers_ignores_fractional_part)
def main [
  1:num <- hash 1.5
  2:num <- hash 1
  3:bool <- equal 1:num, 2:num
]
+mem: storing 1 in location 3

:(scenario hash_of_array_same_as_string)
def main [
  10:num <- copy 3
  11:num <- copy 97
  12:num <- copy 98
  13:num <- copy 99
  2:num <- hash 10:@:num/unsafe
  return-unless 2:num
  3:text <- new [abc]
  4:num <- hash 3:text
  return-unless 4:num
  5:bool <- equal 2:num, 4:num
]
+mem: storing 1 in location 5

:(scenario hash_ignores_address_value)
def main [
  1:&:num <- new number:type
  *1:&:num <- copy 34
  2:num <- hash 1:&:num
  3:&:num <- new number:type
  *3:&:num <- copy 34
  4:num <- hash 3:&:num
  5:bool <- equal 2:num, 4:num
]
# different addresses hash to the same result as long as the values the point to do so
+mem: storing 1 in location 5

:(scenario hash_ignores_address_refcount)
def main [
  1:&:num <- new number:type
  *1:&:num <- copy 34
  2:num <- hash 1:&:num
  return-unless 2:num
  # increment refcount
  3:&:num <- copy 1:&:num
  4:num <- hash 3:&:num
  return-unless 4:num
  5:bool <- equal 2:num, 4:num
]
# hash doesn't change when refcount changes
+mem: storing 1 in location 5

:(scenario hash_container_depends_only_on_elements)
container foo [
  x:num
  y:char
]
container bar [
  x:num
  y:char
]
def main [
  1:foo <- merge 34, 97/a
  3:num <- hash 1:foo
  return-unless 3:num
  4:bar <- merge 34, 97/a
  6:num <- hash 4:bar
  return-unless 6:num
  7:bool <- equal 3:num, 6:num
]
# containers with identical elements return identical hashes
+mem: storing 1 in location 7

:(scenario hash_container_depends_only_on_elements_2)
container foo [
  x:num
  y:char
  z:&:num
]
def main [
  1:&:num <- new number:type
  *1:&:num <- copy 34
  2:foo <- merge 34, 97/a, 1:&:num
  5:num <- hash 2:foo
  return-unless 5:num
  6:&:num <- new number:type
  *6:&:num <- copy 34
  7:foo <- merge 34, 97/a, 6:&:num
  10:num <- hash 7:foo
  return-unless 10:num
  11:bool <- equal 5:num, 10:num
]
# containers with identical 'leaf' elements return identical hashes
+mem: storing 1 in location 11

:(scenario hash_container_depends_only_on_elements_3)
container foo [
  x:num
  y:char
  z:bar
]
container bar [
  x:num
  y:num
]
def main [
  1:foo <- merge 34, 97/a, 47, 48
  6:num <- hash 1:foo
  return-unless 6:num
  7:foo <- merge 34, 97/a, 47, 48
  12:num <- hash 7:foo
  return-unless 12:num
  13:bool <- equal 6:num, 12:num
]
# containers with identical 'leaf' elements return identical hashes
+mem: storing 1 in location 13

:(scenario hash_exclusive_container_ignores_tag)
exclusive-container foo [
  x:bar
  y:num
]
container bar [
  a:num
  b:num
]
def main [
  1:foo <- merge 0/x, 34, 35
  4:num <- hash 1:foo
  return-unless 4:num
  5:bar <- merge 34, 35
  7:num <- hash 5:bar
  return-unless 7:num
  8:bool <- equal 4:num, 7:num
]
# hash on containers includes all elements
+mem: storing 1 in location 8

//: An older version that supported only strings.
//: Hash functions are subtle and easy to get wrong, so we keep the old
//: version around and check that the new one is consistent with it.

:(scenario hash_matches_old_version)
def main [
  1:text <- new [abc]
  2:num <- hash 1:text
  3:num <- hash_old 1:text
  4:bool <- equal 2:num, 3:num
]
+mem: storing 1 in location 4

:(before "End Primitive Recipe Declarations")
HASH_OLD,
:(before "End Primitive Recipe Numbers")
put(Recipe_ordinal, "hash_old", HASH_OLD);
:(before "End Primitive Recipe Checks")
case HASH_OLD: {
  if (SIZE(inst.ingredients) != 1) {
    raise << maybe(get(Recipe, r).name) << "'hash_old' takes exactly one ingredient rather than '" << inst.original_string << "'\n" << end();
    break;
  }
  if (!is_mu_text(inst.ingredients.at(0))) {
    raise << maybe(get(Recipe, r).name) << "'hash_old' currently only supports texts (address array character), but got '" << inst.ingredients.at(0).original_string << "'\n" << end();
    break;
  }
  break;
}
:(before "End Primitive Recipe Implementations")
case HASH_OLD: {
  string input = read_mu_text(ingredients.at(0).at(0));
  size_t h = 0 ;

  for (int i = 0; i < SIZE(input); ++i) {
    h += static_cast<size_t>(input.at(i));
    h += (h<<10);
    h ^= (h>>6);

    h += (h<<3);
    h ^= (h>>11);
    h += (h<<15);
  }

  products.resize(1);
  products.at(0).push_back(h);
  break;
}


context:
space:
mode: