Skip to content
← Back

src/ir/wasmgc/wasmgc_strings.ghul

1
namespace IR.WasmGC is
2
use Wasm.MODULE
3
use Wasm.FUNCTION
4
use Wasm.FUNC_TYPE
5
use Wasm.GLOBAL
6
use Wasm.DATA_SEGMENT
7
use Wasm.VALUE_TYPE
8
use Wasm.HEAP_TYPE
9
use Wasm.NumericType
10
use Wasm.BLOCK_TYPE
11
use Wasm.INSTRUCTION
12
use Wasm.SIMPLE_INSTRUCTION
13
use Wasm.INDEX_INSTRUCTION
14
use Wasm.I32_CONSTANT
15
use Wasm.TYPE_INSTRUCTION
16
use Wasm.TYPE_FIELD_INSTRUCTION
17
use Wasm.TWO_TYPE_INSTRUCTION
18
use Wasm.HEAP_TYPE_INSTRUCTION
19
use Wasm.BLOCK_INSTRUCTION
20
use Wasm.IF_INSTRUCTION
21
use Wasm.Opcode
22
use Wasm.AbstractHeapType
23
24
use Collections.LIST
25
26
/// A string on the wasm target: a struct of the string type's
27
/// descriptor, a cached hash and an immutable array of UTF-16 code
28
/// units. This builds what strings need beyond their types: one
29
/// interned global per distinct literal, filled from a data segment
30
/// when the module starts, and the helper functions the string
31
/// operations call.
32
///
33
/// Helper functions are defined functions numbered after the program's
34
/// own, so the index of each is fixed when it is first asked for, and
35
/// `finish` adds the functions in that order.
36
class WASMGC_STRINGS is
37
_module: MODULE
38
_registry: WASMGC_TYPE_REGISTRY
39
40
_pool: WASMGC_LITERAL_POOL
41
_literal_globals: LIST[int]
42
43
_numbering: WASMGC_FUNCTION_NUMBERING?
44
45
_equals: int?
46
_concat: int?
47
_substring: int?
48
_from_chars: int?
49
_copy_to: int?
50
_to_host: int?
51
_from_host: int?
52
53
_from_char_code_array: int?
54
_length: int?
55
_into_char_code_array: int?
56
57
/// Strings for `module`, whose types `registry` holds. Their helper
58
/// functions are numbered once `use_numbering` gives the numbering.
59
init(module: MODULE, registry: WASMGC_TYPE_REGISTRY) is
60
_module = module
61
_registry = registry
62
63
_pool = WASMGC_LITERAL_POOL()
64
_literal_globals = LIST[int]()
65
si
66
67
/// Declares the host functions strings need: the builtins that make a
68
/// JavaScript string from an array of code units, and that read one
69
/// back. Call before the imports are frozen.
70
declare_imports(imports: WASMGC_IMPORTS) is
71
let chars = VALUE_TYPE.of_type_index(_registry.chars_type_index, true)
72
let i32 = VALUE_TYPE.of_numeric(NumericType.I32)
73
let extern = VALUE_TYPE.of_reference(HEAP_TYPE.of_abstract(AbstractHeapType.EXTERN), false)
74
75
_from_char_code_array =
76
imports.function(
77
"wasm:js-string",
78
"fromCharCodeArray",
79
_module.add_type(FUNC_TYPE([chars, i32, i32], [extern])))
80
81
let nullable_extern = VALUE_TYPE.of_abstract(AbstractHeapType.EXTERN)
82
83
_length =
84
imports.function(
85
"wasm:js-string",
86
"length",
87
_module.add_type(FUNC_TYPE([nullable_extern], [i32])))
88
89
_into_char_code_array =
90
imports.function(
91
"wasm:js-string",
92
"intoCharCodeArray",
93
_module.add_type(FUNC_TYPE([nullable_extern, chars, i32], [i32])))
94
si
95
96
/// Gives the function numbering helper functions are numbered
97
/// from when they are first asked for. Call before any helper is.
98
use_numbering(numbering: WASMGC_FUNCTION_NUMBERING) is
99
_numbering = numbering
100
si
101
102
/// The function making the JavaScript string a host import takes
103
/// from a string, or null from an absent one.
104
to_host_function: int is
105
if let index = _to_host then
106
return index
107
fi
108
109
assert _from_char_code_array? else "string imports not declared"
110
111
let index = _helper(() => _build_to_host())
112
113
_to_host = index
114
115
return index
116
si
117
118
/// The function making a string from the JavaScript string a host
119
/// import answers with, or an absent one from null.
120
from_host_function: int is
121
if let index = _from_host then
122
return index
123
fi
124
125
assert _length? /\ _into_char_code_array? else "string imports not declared"
126
127
let index = _helper(() => _build_from_host())
128
129
_from_host = index
130
131
return index
132
si
133
134
/// The struct type a string is held in.
135
string_type_index: int => _registry.string_type_index!
136
137
/// A nullable reference to a string.
138
string_reference: VALUE_TYPE => VALUE_TYPE.of_type_index(string_type_index, true)
139
140
_chars_reference: VALUE_TYPE => VALUE_TYPE.of_type_index(_registry.chars_type_index, true)
141
142
/// The global holding the literal `text`. Two literals with the
143
/// same text are the same global, so they are the same string.
144
literal(text: string) -> int is
145
let position = _pool.add(text)
146
147
if position < _literal_globals.count then
148
return _literal_globals[position]
149
fi
150
151
let index = _module.add_global(
152
GLOBAL(
153
string_reference,
154
true,
155
[HEAP_TYPE_INSTRUCTION(Opcode.REF_NULL, HEAP_TYPE.of_type_index(string_type_index))]))
156
157
_literal_globals.add(index)
158
159
return index
160
si
161
162
/// The function comparing two strings by their code units. Two
163
/// absent strings are equal, and an absent one equals no present
164
/// one.
165
equals_function: int is
166
if let index = _equals then
167
return index
168
fi
169
170
let index = _helper(() => _build_equals())
171
172
_equals = index
173
174
return index
175
si
176
177
/// The function joining two strings, reading an absent one as
178
/// empty.
179
concat_function: int is
180
if let index = _concat then
181
return index
182
fi
183
184
let index = _helper(() => _build_concat())
185
186
_concat = index
187
188
return index
189
si
190
191
/// The function making a new string of `length` code units of
192
/// `text` from `start` on. A range outside `text` traps.
193
substring_function: int is
194
if let index = _substring then
195
return index
196
fi
197
198
let index = _helper(() => _build_substring())
199
200
_substring = index
201
202
return index
203
si
204
205
/// The function making a new string of `length` code units of the
206
/// element array of a `char[]`, of type `data_index`, from `start`
207
/// on. A range outside it traps.
208
from_chars_function(data_index: int) -> int is
209
if let index = _from_chars then
210
return index
211
fi
212
213
let index = _helper(() => _build_from_chars(data_index))
214
215
_from_chars = index
216
217
return index
218
si
219
220
/// The function copying `count` code units of a string from `start`
221
/// into the element array of a `char[]`, of type `data_index`, from
222
/// `at` on. A range outside either traps.
223
copy_to_function(data_index: int) -> int is
224
if let index = _copy_to then
225
return index
226
fi
227
228
let index = _helper(() => _build_copy_to(data_index))
229
230
_copy_to = index
231
232
return index
233
si
234
235
_helper(build: () -> FUNCTION) -> int => _numbering!.reserve(build)
236
237
/// Adds the data segment holding every literal, and numbers the
238
/// start function that builds them. Call once, after every body has
239
/// been lowered and before the numbered functions are added.
240
finish() is
241
let entries = _pool.entries
242
243
if entries.count == 0 then
244
return
245
fi
246
247
let segment = _module.data_segments().count
248
let start = LIST[INSTRUCTION]()
249
250
for i in 0..entries.count do
251
let (text, offset) = entries[i]
252
253
start.add(INDEX_INSTRUCTION(Opcode.GLOBAL_GET, _registry.string_descriptor_global!))
254
start.add(I32_CONSTANT(0))
255
start.add(I32_CONSTANT(offset))
256
start.add(I32_CONSTANT(text.length))
257
start.add(TYPE_FIELD_INSTRUCTION(Opcode.ARRAY_NEW_DATA, _registry.chars_type_index, segment))
258
start.add(TYPE_INSTRUCTION(Opcode.STRUCT_NEW, string_type_index))
259
start.add(INDEX_INSTRUCTION(Opcode.GLOBAL_SET, _literal_globals[i]))
260
od
261
262
_module.add_data_segment(DATA_SEGMENT(_pool.bytes))
263
264
let start_type = _module.add_type(FUNC_TYPE([], []))
265
266
_module.set_start(_numbering!.reserve(() => FUNCTION(start_type, [], start)))
267
si
268
269
// (a, b) -> i32: equal when both are the same reference (both
270
// absent included), unequal when one is absent, and otherwise
271
// equal when their code units are.
272
_build_equals() -> FUNCTION is
273
let chars = _registry.chars_type_index
274
275
// parameters 0 and 1; locals: 2 and 3 the code units, 4 the
276
// length, 5 the position
277
let loop_body = LIST[INSTRUCTION]([
278
_get(5), _get(4), _op(Opcode.I32_GE_U),
279
INDEX_INSTRUCTION(Opcode.BR_IF, 1),
280
_get(2), _get(5), TYPE_INSTRUCTION(Opcode.ARRAY_GET_U, chars),
281
_get(3), _get(5), TYPE_INSTRUCTION(Opcode.ARRAY_GET_U, chars),
282
_op(Opcode.I32_NE),
283
_return_if(0),
284
_get(5), I32_CONSTANT(1), _op(Opcode.I32_ADD), _set(5),
285
INDEX_INSTRUCTION(Opcode.BR, 0)
286
]:INSTRUCTION)
287
288
let body = LIST[INSTRUCTION]([
289
_get(0), _get(1), _op(Opcode.REF_EQ),
290
_return_if(1),
291
_get(0), _op(Opcode.REF_IS_NULL),
292
_return_if(0),
293
_get(1), _op(Opcode.REF_IS_NULL),
294
_return_if(0),
295
_get(0), _chars_of(), _set(2),
296
_get(1), _chars_of(), _set(3),
297
_get(2), _op(Opcode.ARRAY_LEN), INDEX_INSTRUCTION(Opcode.LOCAL_TEE, 4),
298
_get(3), _op(Opcode.ARRAY_LEN), _op(Opcode.I32_NE),
299
_return_if(0),
300
BLOCK_INSTRUCTION(
301
Opcode.BLOCK,
302
BLOCK_TYPE(),
303
LIST[INSTRUCTION]([BLOCK_INSTRUCTION(Opcode.LOOP, BLOCK_TYPE(), loop_body)]:INSTRUCTION)),
304
I32_CONSTANT(1)
305
]:INSTRUCTION)
306
307
let i32 = VALUE_TYPE.of_numeric(NumericType.I32)
308
309
return FUNCTION(
310
_module.add_type(FUNC_TYPE([string_reference, string_reference], [i32])),
311
[_chars_reference, _chars_reference, i32, i32],
312
body)
313
si
314
315
// (text, start, length) -> string: a new string holding `length`
316
// code units of `text` from `start` on.
317
_build_substring() -> FUNCTION is
318
let chars = _registry.chars_type_index
319
let i32 = VALUE_TYPE.of_numeric(NumericType.I32)
320
321
// parameters 0 the string, 1 the start, 2 the length; local 3
322
// the result's code units
323
let body = LIST[INSTRUCTION]([
324
_get(2), TYPE_INSTRUCTION(Opcode.ARRAY_NEW_DEFAULT, chars), _set(3),
325
_get(3), I32_CONSTANT(0),
326
_get(0), _chars_of(), _get(1),
327
_get(2),
328
TWO_TYPE_INSTRUCTION(Opcode.ARRAY_COPY, chars, chars),
329
INDEX_INSTRUCTION(Opcode.GLOBAL_GET, _registry.string_descriptor_global!),
330
I32_CONSTANT(0),
331
_get(3), _op(Opcode.REF_AS_NON_NULL),
332
TYPE_INSTRUCTION(Opcode.STRUCT_NEW, string_type_index)
333
]:INSTRUCTION)
334
335
return FUNCTION(
336
_module.add_type(FUNC_TYPE([string_reference, i32, i32], [string_reference])),
337
[_chars_reference],
338
body)
339
si
340
341
_build_copy_to(data_index: int) -> FUNCTION is
342
let chars = _registry.chars_type_index
343
let i32 = VALUE_TYPE.of_numeric(NumericType.I32)
344
345
// A string holds its code units as a packed `i16` and an array of
346
// `char` each as an `i32`, so they are copied one at a time.
347
//
348
// parameters 0 the string, 1 the start, 2 the destination's
349
// elements, 3 where in them, 4 the count; locals 5 the index, 6
350
// the string's code units
351
let loop_body = LIST[INSTRUCTION]([
352
_get(5), _get(4), _op(Opcode.I32_GE_U),
353
INDEX_INSTRUCTION(Opcode.BR_IF, 1),
354
_get(2), _get(3), _get(5), _op(Opcode.I32_ADD),
355
_get(6), _get(1), _get(5), _op(Opcode.I32_ADD),
356
TYPE_INSTRUCTION(Opcode.ARRAY_GET_U, chars),
357
TYPE_INSTRUCTION(Opcode.ARRAY_SET, data_index),
358
_get(5), I32_CONSTANT(1), _op(Opcode.I32_ADD), _set(5),
359
INDEX_INSTRUCTION(Opcode.BR, 0)
360
]:INSTRUCTION)
361
362
let body = LIST[INSTRUCTION]([
363
_get(0), _chars_of(), _set(6),
364
BLOCK_INSTRUCTION(
365
Opcode.BLOCK,
366
BLOCK_TYPE(),
367
LIST[INSTRUCTION]([BLOCK_INSTRUCTION(Opcode.LOOP, BLOCK_TYPE(), loop_body)]:INSTRUCTION))
368
]:INSTRUCTION)
369
370
return FUNCTION(
371
_module.add_type(FUNC_TYPE([string_reference, i32, VALUE_TYPE.of_type_index(data_index, true), i32, i32], [])),
372
[i32, _chars_reference],
373
body)
374
si
375
376
_build_from_chars(data_index: int) -> FUNCTION is
377
let chars = _registry.chars_type_index
378
let i32 = VALUE_TYPE.of_numeric(NumericType.I32)
379
380
// An array of `char` holds each code unit as an `i32`, and a
381
// string as a packed `i16`, so the units are copied one at a time
382
// rather than by `array.copy`, which needs the two to match.
383
//
384
// parameters 0 the code units, 1 the start, 2 the length; locals
385
// 3 the result's code units, 4 the index
386
let loop_body = LIST[INSTRUCTION]([
387
_get(4), _get(2), _op(Opcode.I32_GE_U),
388
INDEX_INSTRUCTION(Opcode.BR_IF, 1),
389
_get(3), _get(4),
390
_get(0), _get(1), _get(4), _op(Opcode.I32_ADD),
391
TYPE_INSTRUCTION(Opcode.ARRAY_GET, data_index),
392
TYPE_INSTRUCTION(Opcode.ARRAY_SET, chars),
393
_get(4), I32_CONSTANT(1), _op(Opcode.I32_ADD), _set(4),
394
INDEX_INSTRUCTION(Opcode.BR, 0)
395
]:INSTRUCTION)
396
397
let body = LIST[INSTRUCTION]([
398
_get(2), TYPE_INSTRUCTION(Opcode.ARRAY_NEW_DEFAULT, chars), _set(3),
399
BLOCK_INSTRUCTION(
400
Opcode.BLOCK,
401
BLOCK_TYPE(),
402
LIST[INSTRUCTION]([BLOCK_INSTRUCTION(Opcode.LOOP, BLOCK_TYPE(), loop_body)]:INSTRUCTION)),
403
INDEX_INSTRUCTION(Opcode.GLOBAL_GET, _registry.string_descriptor_global!),
404
I32_CONSTANT(0),
405
_get(3), _op(Opcode.REF_AS_NON_NULL),
406
TYPE_INSTRUCTION(Opcode.STRUCT_NEW, string_type_index)
407
]:INSTRUCTION)
408
409
return FUNCTION(
410
_module.add_type(FUNC_TYPE([VALUE_TYPE.of_type_index(data_index, true), i32, i32], [string_reference])),
411
[_chars_reference, i32],
412
body)
413
si
414
415
// (a, b) -> string: a new string holding a's code units then b's.
416
_build_concat() -> FUNCTION is
417
let chars = _registry.chars_type_index
418
419
// parameters 0 and 1; locals: 2 and 3 the code units, 4 the
420
// result's code units
421
let body = LIST[INSTRUCTION]([
422
_get(0), _op(Opcode.REF_IS_NULL), _chars_or_empty(0), _set(2),
423
_get(1), _op(Opcode.REF_IS_NULL), _chars_or_empty(1), _set(3),
424
_get(2), _op(Opcode.ARRAY_LEN),
425
_get(3), _op(Opcode.ARRAY_LEN),
426
_op(Opcode.I32_ADD),
427
TYPE_INSTRUCTION(Opcode.ARRAY_NEW_DEFAULT, chars),
428
_set(4),
429
_get(4), I32_CONSTANT(0), _get(2), I32_CONSTANT(0), _get(2), _op(Opcode.ARRAY_LEN),
430
TWO_TYPE_INSTRUCTION(Opcode.ARRAY_COPY, chars, chars),
431
_get(4), _get(2), _op(Opcode.ARRAY_LEN), _get(3), I32_CONSTANT(0), _get(3), _op(Opcode.ARRAY_LEN),
432
TWO_TYPE_INSTRUCTION(Opcode.ARRAY_COPY, chars, chars),
433
INDEX_INSTRUCTION(Opcode.GLOBAL_GET, _registry.string_descriptor_global!),
434
I32_CONSTANT(0),
435
_get(4), _op(Opcode.REF_AS_NON_NULL),
436
TYPE_INSTRUCTION(Opcode.STRUCT_NEW, string_type_index)
437
]:INSTRUCTION)
438
439
return FUNCTION(
440
_module.add_type(FUNC_TYPE([string_reference, string_reference], [string_reference])),
441
[_chars_reference, _chars_reference, _chars_reference],
442
body)
443
si
444
445
// (s) -> externref: null for an absent string, otherwise the
446
// JavaScript string the host builtin makes from all its code units.
447
_build_to_host() -> FUNCTION is
448
let extern = VALUE_TYPE.of_abstract(AbstractHeapType.EXTERN)
449
450
// parameter 0; local 1 the code units
451
let body = LIST[INSTRUCTION]([
452
_get(0), _op(Opcode.REF_IS_NULL),
453
IF_INSTRUCTION(
454
BLOCK_TYPE(),
455
LIST[INSTRUCTION]([
456
HEAP_TYPE_INSTRUCTION(Opcode.REF_NULL, HEAP_TYPE.of_abstract(AbstractHeapType.EXTERN)),
457
_op(Opcode.RETURN)
458
]:INSTRUCTION),
459
LIST[INSTRUCTION]()),
460
_get(0), _chars_of(), INDEX_INSTRUCTION(Opcode.LOCAL_TEE, 1),
461
I32_CONSTANT(0),
462
_get(1), _op(Opcode.ARRAY_LEN),
463
INDEX_INSTRUCTION(Opcode.CALL, _from_char_code_array!)
464
]:INSTRUCTION)
465
466
return FUNCTION(
467
_module.add_type(FUNC_TYPE([string_reference], [extern])),
468
[_chars_reference],
469
body)
470
si
471
472
// (externref) -> string: null for null, otherwise a new string holding
473
// the JavaScript string's code units.
474
_build_from_host() -> FUNCTION is
475
let extern = VALUE_TYPE.of_abstract(AbstractHeapType.EXTERN)
476
let chars = _registry.chars_type_index
477
478
// parameter 0; local 1 the code units
479
let body = LIST[INSTRUCTION]([
480
_get(0), _op(Opcode.REF_IS_NULL),
481
IF_INSTRUCTION(
482
BLOCK_TYPE(),
483
LIST[INSTRUCTION]([
484
HEAP_TYPE_INSTRUCTION(Opcode.REF_NULL, HEAP_TYPE.of_type_index(string_type_index)),
485
_op(Opcode.RETURN)
486
]:INSTRUCTION),
487
LIST[INSTRUCTION]()),
488
_get(0), INDEX_INSTRUCTION(Opcode.CALL, _length!),
489
TYPE_INSTRUCTION(Opcode.ARRAY_NEW_DEFAULT, chars), _set(1),
490
_get(0), _get(1), I32_CONSTANT(0),
491
INDEX_INSTRUCTION(Opcode.CALL, _into_char_code_array!),
492
_op(Opcode.DROP),
493
INDEX_INSTRUCTION(Opcode.GLOBAL_GET, _registry.string_descriptor_global!),
494
I32_CONSTANT(0),
495
_get(1), _op(Opcode.REF_AS_NON_NULL),
496
TYPE_INSTRUCTION(Opcode.STRUCT_NEW, string_type_index)
497
]:INSTRUCTION)
498
499
return FUNCTION(
500
_module.add_type(FUNC_TYPE([extern], [string_reference])),
501
[_chars_reference],
502
body)
503
si
504
505
// The code units of the string on the stack.
506
_chars_of() -> INSTRUCTION =>
507
TYPE_FIELD_INSTRUCTION(Opcode.STRUCT_GET, string_type_index, WASMGC_TYPE_REGISTRY.STRING_CHARS)
508
509
// The code units of the string in local `index`, or an empty
510
// array where it is absent: an `if` on the null test of that local,
511
// which the caller pushes first.
512
_chars_or_empty(index: int) -> INSTRUCTION =>
513
IF_INSTRUCTION(
514
BLOCK_TYPE.of_value(_chars_reference),
515
LIST[INSTRUCTION]([
516
I32_CONSTANT(0),
517
TYPE_INSTRUCTION(Opcode.ARRAY_NEW_DEFAULT, _registry.chars_type_index)
518
]:INSTRUCTION),
519
LIST[INSTRUCTION]([_get(index), _chars_of()]:INSTRUCTION))
520
521
_return_if(value: int) -> INSTRUCTION =>
522
IF_INSTRUCTION(
523
BLOCK_TYPE(),
524
LIST[INSTRUCTION]([I32_CONSTANT(value), _op(Opcode.RETURN)]:INSTRUCTION),
525
LIST[INSTRUCTION]())
526
527
_get(index: int) -> INSTRUCTION => INDEX_INSTRUCTION(Opcode.LOCAL_GET, index)
528
_set(index: int) -> INSTRUCTION => INDEX_INSTRUCTION(Opcode.LOCAL_SET, index)
529
_op(opcode: Opcode) -> INSTRUCTION => SIMPLE_INSTRUCTION(opcode)
530
si
531
si