dymokomi/luce-base
Source of release 0.41.0
0.41.0 / src / sema / name_index.lucb
#==============================================================================================
#
# name_index - Where each name is bound in the checker's scope list
#
# DESCRIPTION:
# An open-addressed table from a name to its innermost binding. Each binding records
# the one of the same name it hides, so a lookup walks only that name's chain instead
# of every binding in scope: a program's top level holds thousands of names, and a
# linear scan per identifier was most of the checker's time.
#
#==============================================================================================
import memory
import strings
## A name's innermost binding, as its index in the scope list plus one; 0 when unbound.
pub struct NameIndex:
## Slot keys; the empty string marks a slot never used. A slot keeps its name once
## used, with head 0 when nothing binds it now, so probing never breaks.
var names: str[]
var heads: u32[]
## Slots with a key.
var used: usize
## The allocator the slots were made with, which their growth goes on using.
var allocator: memory.Allocator
## An empty index, with room for five hundred names before it grows.
pub static func create() -> NameIndex!:
let names = try new str[1024] ---
let heads = try new u32[1024] ---
for i in 0..<names.length:
names[i] = ""
heads[i] = 0
return NameIndex(names = names, heads = heads, used = 0, allocator = memory.allocator)
## The innermost binding of `name`, its scope index plus one, or 0.
pub func head(name: str) -> u32:
let mask = self.names.length - 1
var slot = spread(name) & mask
while true:
let key = self.names[slot]
if key.length == 0 and self.heads[slot] == 0:
return 0
if key == name:
return self.heads[slot]
slot = (slot + 1) & mask
## Make `head` the innermost binding of `name` (0 when none is left).
pub func set(name: str, head: u32) -> !:
if (self.used + 1) * 2 > self.names.length:
try self.grow()
let mask = self.names.length - 1
var slot = spread(name) & mask
while true:
let key = self.names[slot]
if key == name:
self.heads[slot] = head
return
if key.length == 0 and self.heads[slot] == 0:
self.names[slot] = name
self.heads[slot] = head
self.used += 1
return
slot = (slot + 1) & mask
## A copy in the current allocator, which its growth goes on using: a name set in one
## is not set in the other.
pub func copied() -> NameIndex!:
let names = try new str[self.names.length] ---
let heads = try new u32[self.heads.length] ---
memory.copy(names, self.names, names.length)
memory.copy(heads, self.heads, heads.length)
return NameIndex(names = names, heads = heads, used = self.used, allocator = memory.allocator)
func grow() -> !:
let old_names = self.names
let old_heads = self.heads
self.names = try new str[old_names.length * 2] --- in self.allocator
self.heads = try new u32[old_names.length * 2] --- in self.allocator
for i in 0..<self.names.length:
self.names[i] = ""
self.heads[i] = 0
self.used = 0
for i in 0..<old_names.length:
if old_names[i].length > 0 and old_heads[i] != 0:
try self.set(old_names[i], old_heads[i])
free(old_names) in self.allocator
free(old_heads) in self.allocator
## FNV-1a over the name's bytes.
func spread(name: str) -> usize:
var h: u64 = 14695981039346656037
for byte in name.bytes:
h = (h ^ (u64)byte) *% 1099511628211
return (usize)h
test "a name's head follows its bindings and survives growth":
var index = try NameIndex.create()
assert(index.head("a") == 0)
try index.set("a", 1)
try index.set("b", 2)
try index.set("a", 3)
assert(index.head("a") == 3 and index.head("b") == 2)
try index.set("a", 1)
assert(index.head("a") == 1)
try index.set("b", 0)
assert(index.head("b") == 0)
var buffer: u8[16]
for i in 0..<2000:
let name = try strings.format(buffer, f"n{i}")
var owned = try new u8[name.length] ---
for j in 0..<name.length:
owned[j] = name.bytes[j]
try index.set((str)owned, (u32)i + 10)
assert(index.head("a") == 1 and index.head("n1999") == 2009 and index.head("n0") == 10)