Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.44.0

0.44.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")