dymokomi/luce-base
Source of release 0.41.0
0.41.0 / src / back / native / stable_names.lucb
#==============================================================================================
#
# stable_names - Labels named by what they label, for an assembly cut into pieces
#
# DESCRIPTION:
# A split assembly (`support.pieces`) keeps each piece's object in the build cache
# under the hash of its text, so an edit reassembles only the pieces whose text
# changed. A label numbered by its function's place in the program, or a text literal
# by its place among the texts, would change in every piece when one function or
# literal comes or goes before it. With `split` the generators name a function's local
# labels by a tag of its symbol and a text literal by a tag of its bytes instead: the
# same in every build that has them. A tag is 48 bits of the name's hash, made unique
# within the program; the rare clash takes the next hash of the name, so the names
# stay deterministic.
#
#==============================================================================================
import back.ir.ir
import support.buffer
import support.hashed
## A tag for each function, by its symbol.
pub func function_tags(program: ir.Unit*) -> u64[]!:
let count = program.functions.count
var tags = try new u64[count] ---
var used = try hashed.Table[u64].create(count)
defer used.destroy()
for i in 0..<count:
tags[i] = try claim(&used, program.functions.items[i].name)
return tags
## A tag for each text literal, by its bytes; the unit's texts are distinct.
pub func text_tags(program: ir.Unit*) -> u64[]!:
let count = program.texts.count
var tags = try new u64[count] ---
var used = try hashed.Table[u64].create(count)
defer used.destroy()
for i in 0..<count:
tags[i] = try claim(&used, program.texts.get(i).bytes)
return tags
## Whether every tag is its name's first (`claim`): no two names clashed, so each tag is
## the same in every build that has its name, whatever else the build holds.
pub func first_tags(program: ir.Unit*, functions: const u64[], texts: const u64[]) -> bool:
for i in 0..<functions.length:
if functions[i] != first(program.functions.items[i].name):
return false
for i in 0..<texts.length:
if texts[i] != first(program.texts.get(i).bytes):
return false
return true
## The tag `claim` gives `name` when no other name took it.
func first(name: str) -> u64:
return name_hash(14695981039346656037, name) & 0xFFFFFFFFFFFF
## What names function `index`'s own labels: its index, or when `stable` its tag.
pub func put_function_label(out: buffer.Buffer*, index: usize, tags: const u64[], stable: bool) -> !:
if stable:
try put_tag(out, tags[index])
else:
try out.put_u64((u64)index)
## `tag` as twelve hex digits.
pub func put_tag(out: buffer.Buffer*, tag: u64) -> !:
let digits = "0123456789abcdef"
var room: u8[12] = ---
for k in 0..<room.length:
room[k] = digits.bytes[(usize)((tag >> (u64)(44 - 4 * k)) & 15)]
try out.put((str)room[..<room.length])
# mark: Unique tags ===========================================================================
## The tag of `name` among those `used` gives: its hash's low 48 bits, or the next hash's
## while that one is taken.
func claim(used: hashed.Table[u64]*, name: str) -> u64!:
var h = name_hash(14695981039346656037, name)
while true:
let tag = h & 0xFFFFFFFFFFFF
if tag != 0 and try used.add(tag, 0):
return tag
h = name_hash(h, name)
## FNV-1a of `name` from `h`, then a final mix, so the low bits depend on every byte.
func name_hash(h: u64, name: str) -> u64:
var r = h
for b in name.bytes:
r = (r ^ (u64)b) *% 1099511628211
r = (r ^ (r >> 33)) *% 0xff51afd7ed558ccd
return r ^ (r >> 33)
test "tags are twelve hex digits, distinct, and the same for the same names":
var used = try hashed.Table[u64].create(4)
defer used.destroy()
let a = try claim(&used, "lb_main")
let b = try claim(&used, "lb_main")
assert(a != b)
var again = try hashed.Table[u64].create(4)
defer again.destroy()
assert((try claim(&again, "lb_main")) == a)
var out = try buffer.Buffer.create(16)
try put_tag(&out, 0xabc)
assert(out.view() == "000000000abc")