lib/std/lang/il/binary/collect.rad 4.3 KiB raw
1
//! Deterministic symbol collection for package-local IL.
2
3
use std::collections::dict;
4
use std::lang::alloc;
5
use std::lang::il;
6
use std::lang::il::binary;
7
use std::mem;
8
use std::mem::heap;
9
10
/// Number of slots of the name index. It must be a power of two. The index
11
/// takes at most half of its slots, which bounds the names of one package.
12
export constant INDEX_SLOTS: u32 = 32768;
13
14
/// Storage for a package's indexed names. Tables grow in the allocator that
15
/// each operation receives, so one allocator must serve a whole collection.
16
/// Names are copied into that allocator, so callers may release their own
17
/// storage after each call.
18
export record Names {
19
    /// Unique names in first-use order.
20
    symbols: *mut [*[u8]],
21
    /// Maps each name to its position in `symbols`.
22
    index: dict::Dict,
23
}
24
25
/// Start collection with empty tables.
26
/// `slots` is the number of index slots, a power of two of at least two.
27
export fn new(slots: u32, a: &heap::Heap) -> Names throws (binary::Error) {
28
    let mut table: *mut [dict::Entry] = &mut [];
29
    try table.resize(slots, dict::Entry { key: &[], value: 0 }, a) catch {
30
        throw binary::Error::Storage;
31
    };
32
    return Names { symbols: &mut [], index: dict::fresh(table) };
33
}
34
35
/// Add a unique name and return its first-use index.
36
export fn intern(names: &mut Names, name: *[u8], a: &heap::Heap) -> u32
37
    throws (binary::Error)
38
{
39
    if name.len == 0 {
40
        throw binary::Error::Invalid;
41
    }
42
    if let i = dict::get(&names.index, name) {
43
        return i as u32;
44
    }
45
    let copy = try alloc::copyBytes(a, name) catch {
46
        throw binary::Error::Storage;
47
    };
48
    let stored: *[u8] = &copy[..];
49
    let index = names.symbols.len;
50
    try names.symbols.append(stored, a) catch {
51
        throw binary::Error::Storage;
52
    };
53
    try dict::insert(&mut names.index, stored, index as i32) catch {
54
        // Shrinking a reserved slice cannot allocate.
55
        try! names.symbols.resize(index, "", a);
56
        throw binary::Error::Storage;
57
    };
58
    return index;
59
}
60
61
/// Add a qualified reference with a nonempty package and local name, returning its index.
62
export fn reference(names: &mut Names, name: *[u8], a: &heap::Heap) -> u32
63
    throws (binary::Error)
64
{
65
    let separator = mem::find(name, "::") else throw binary::Error::Invalid;
66
    if separator == 0 or separator + 2 == name.len {
67
        throw binary::Error::Invalid;
68
    }
69
    return try intern(names, name, a);
70
}
71
72
/// Check that a definition belongs to the selected package.
73
export fn definition(
74
    names: &mut Names, owner: *[u8], name: *[u8], a: &heap::Heap
75
) -> *[u8] throws (binary::Error) {
76
    let rest = mem::stripPrefix(owner, name) else {
77
        throw binary::Error::Invalid;
78
    };
79
    if rest.len < 3 or rest[0] <> ':' or rest[1] <> ':' {
80
        throw binary::Error::Invalid;
81
    }
82
    let index = try intern(names, name, a);
83
    return names.symbols[index];
84
}
85
86
/// Add the package name before its definitions and references.
87
export fn start(names: &mut Names, owner: *[u8], a: &heap::Heap)
88
    throws (binary::Error)
89
{
90
    try intern(names, owner, a);
91
}
92
93
/// Build package tables from explicit dependencies and local definitions.
94
/// The tables move out of `names`, but its name index stays valid.
95
/// Function names and symbolic operands must already be interned.
96
export fn finish(
97
    names: &mut Names,
98
    owner: *[u8],
99
    dependencies: *[*[u8]],
100
    program: il::Program,
101
    exports: *[binary::Export],
102
    entry: ?*[u8],
103
    a: &heap::Heap
104
) -> binary::Package throws (binary::Error) {
105
    for dependency in dependencies {
106
        try intern(names, dependency, a);
107
    }
108
    for item in exports {
109
        try definition(names, owner, item.name, a);
110
    }
111
    if let name = entry {
112
        try definition(names, owner, name, a);
113
    }
114
    for item in program.data {
115
        try definition(names, owner, item.name, a);
116
        for data in item.values {
117
            match data.item {
118
                case il::DataItem::Sym(name) => try reference(names, name, a),
119
                case il::DataItem::Fn(name)  => try reference(names, name, a),
120
                else                         => {}
121
            }
122
        }
123
    }
124
    let symbols = names.symbols.take();
125
    return binary::Package {
126
        version: nil,
127
        symbols: &symbols[..],
128
        name: owner,
129
        dependencies,
130
        exports,
131
        entry,
132
        program,
133
        links: binary::EMPTY_LINKS,
134
    };
135
}