Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.43.0

0.43.0 / src / back / instances.lucb

#==============================================================================================
#
#   instances - What both backends share while generating bodies
#
#   DESCRIPTION:
#       The C emitter and the IR lowering walk the same checked tree for the same program,
#       and need the same bookkeeping to do it: the function instances the program reaches,
#       each once (ยง13); the generic context of the body being generated, whose type
#       arguments are substituted into every type the checker recorded; the source a
#       declaration came from; and the tag of an enum case. One copy here keeps the two
#       backends from drifting apart.
#
#==============================================================================================

import memory
import front.ast
import front.source as sources
import sema.check
import sema.types
import support.list

# mark: Function instances ====================================================================

## One monomorphised function or method: a declaration with concrete type arguments.
pub struct Instance:
    ## The function or method declaration.
    pub var decl: ast.Node*
    ## Its own type arguments.
    pub var args: u32[]
    ## For a method of a generic record: the record and its arguments.
    pub var owner: ast.Node*?
    ## The record's type arguments.
    pub var owner_args: u32[]
    ## Whether its body was generated.
    pub var done: bool

## The function instances a program needs, each once, in the order they were first needed,
## with an open-addressed index over a hash of the declaration and its arguments.
pub struct Instances:
    ## The instances, by index.
    pub var items: list.List[Instance]
    var slots: u32[]

    ## No instances yet.
    pub static func create() -> Instances!:
        return Instances(items = try list.List[Instance].create(64), slots = try empty_slots(256))

    ## Register a function instance; returns its index. An instance whose arguments nest
    ## past the checker's limit is an infinite chain of instantiations.
    pub func add(table: types.Table*, f: ast.Node*, args: u32[], owner: ast.Node*?, owner_args: u32[]) -> usize!:
        let mask = self.slots.length - 1
        var slot = instance_hash(f, args, owner, owner_args) & mask
        while self.slots[slot] != 0:
            let i = (usize)self.slots[slot] - 1
            # through a pointer: the comparison must not copy a record
            let r = &self.items.items[i]
            if r.decl == f and types.same_args(r.args, args) and r.owner == owner and types.same_args(r.owner_args, owner_args):
                return i
            slot = (slot + 1) & mask
        if check.nesting_of_all(table, args) > check.max_nesting or check.nesting_of_all(table, owner_args) > check.max_nesting:
            error(endless, "an infinite chain of instantiations")
        try self.items.push(Instance(decl = f, args = args, owner = owner, owner_args = owner_args, done = false))
        let index = self.items.count - 1
        if (self.items.count + 1) * 2 > self.slots.length:
            # grown: every instance placed again in a table twice the size
            let grown = try empty_slots(self.slots.length * 2)
            with memory.heap:
                free(self.slots)
            self.slots = grown
            for k in 0..<self.items.count:
                self.place(k)
        else:
            self.place(index)
        return index

    ## The next instance whose body is still to generate, from `*next` on, marked done; none
    ## when the list is drained. A body may need new instances, so generating goes on until
    ## this says none after the last one.
    pub func next_pending(next: usize*) -> Instance?:
        while *next < self.items.count:
            var inst = self.items.get(*next)
            *next += 1
            if not inst.done:
                inst.done = true
                self.items.set(*next - 1, inst)
                return inst
        return none

    ## Put instance `index` in the first free slot of its probe sequence.
    func place(index: usize):
        let r = &self.items.items[index]
        let mask = self.slots.length - 1
        var slot = instance_hash(r.decl, r.args, r.owner, r.owner_args) & mask
        while self.slots[slot] != 0:
            slot = (slot + 1) & mask
        self.slots[slot] = u32(index + 1)

## A failed `add`: the chain of instantiations never ends.
pub let endless: ErrorCode = ErrorCode.package(53)

## `size` free slots for the index, from the heap, where a grown table's old slots go back.
func empty_slots(size: usize) -> u32[]!:
    with memory.heap:
        var slots = try new u32[size] ---
        for k in 0..<size:
            slots[k] = 0
        return slots

## FNV-1a over an instance's declaration, owner and type arguments.
func instance_hash(f: ast.Node*, args: const u32[], owner: ast.Node*?, owner_args: const u32[]) -> usize:
    var h: u64 = 14695981039346656037
    h = (h ^ (u64)(usize)f) *% 1099511628211
    var owner_bits: u64 = 0
    if let o = owner:
        owner_bits = (u64)(usize)o
    h = (h ^ owner_bits) *% 1099511628211
    for a in args:
        h = (h ^ (u64)a) *% 1099511628211
    h = (h ^ 0xff) *% 1099511628211
    for a in owner_args:
        h = (h ^ (u64)a) *% 1099511628211
    return (usize)h

# mark: The body being generated ==============================================================

## The generic context of a body: the instance's own type arguments and, for a method of a
## generic record, the record's.
pub struct Generic:
    ## The function whose body it is.
    pub var fn_decl: ast.Node*?
    ## That function's type arguments.
    pub var fn_args: u32[]
    ## The generic record the function is a method of.
    pub var owner_decl: ast.Node*?
    ## That record's type arguments.
    pub var owner_args: u32[]

    ## The context before any body: no instance, no arguments.
    pub static func none_yet() -> Generic!:
        return Generic(fn_decl = none, fn_args = try types.no_args(), owner_decl = none, owner_args = try types.no_args())

    ## A type of the body, with the instance's arguments substituted.
    pub func map(c: check.Checker*, id: u32) -> u32!:
        var t = id
        if let o = self.owner_decl:
            if self.owner_args.length > 0:
                t = try c.substitute(t, o, self.owner_args)
        if let f = self.fn_decl:
            if self.fn_args.length > 0:
                t = try c.substitute(t, f, self.fn_args)
        return t

    ## The concrete type arguments recorded on a call or name.
    pub func type_args(c: check.Checker*, holder: ast.Node*) -> u32[]!:
        let n = ast.count(holder.body)
        if n == 0:
            return try types.no_args()
        var args = try new u32[n] ---
        var i: usize = 0
        var cursor = holder.body
        while let a = cursor:
            args[i] = try self.map(c, a.type_id)
            i += 1
            cursor = a.next
        return args

## The source a declaration came from, when the checker has it: the module it resolved to,
## else, for a declaration of the file being generated, that file's.
pub func source_unit_of(c: check.Checker*, decl: ast.Node*, file: str) -> sources.Source?:
    for module in c.modules.span():
        if let m = decl.resolved:
            if module.tree == m:
                return module.src
        elif module.src.path == file:
            return module.src
    return none

## Each method of record `d` that interface `iface` requires: what the record's witness
## table for it points at, so each needs an instance.
pub func witnessed(d: ast.Node*, iface: ast.Node*) -> list.List[ast.Node*]!:
    var methods = try list.List[ast.Node*].create(8)
    var req = iface.body
    while let r = req:
        if let m = check.find_member(d, r.text, ast.Kind.func_):
            try methods.push(m)
        req = r.next
    return methods

## The tag of a payload enum case: its position among the cases.
pub func case_tag(d: ast.Node*, target: ast.Node*) -> u32:
    var i: u32 = 0
    var cursor = d.body
    while let node = cursor:
        if node.kind == ast.Kind.enum_case:
            if node == target:
                return i
            i += 1
        cursor = node.next
    return 0