dymokomi/luce-base
Source of release 0.45.0
0.45.0 / src / back / ir / lower / branching.lucb
#==============================================================================================
#
# lower/branching - Failure and matching
#
# DESCRIPTION:
# `try`, `else`, and `catch` over fallible and optional values (§11), and `match`.
#
#==============================================================================================
extend Lowerer:
# mark: Failure and absence ================================================================
func try_expr(e: ast.Node*) -> LowerValue!:
let inner = e.left else return try self.fail(e, "no operand")
let ft = try self.ty(inner)
let payload = self.elem(ft)
let v = try self.expr(inner)
let failed = try self.f.load(ir.Op.loadub, ir.Class.w, try self.offset_address(v.ref, self.failed_offset(ft)))
let ok = self.f.label()
let bad = self.f.label()
try self.f.branch(failed, bad, ok)
try self.f.place_label(bad)
if e.has(ast.flag_crossing):
# the error comes into this package out of another's function (§11.3)
try self.store_called(try self.failure_address())
try self.propagate(v.ref, ft)
try self.f.place_label(ok)
if payload == types.unit_id or payload == types.never_id:
return LowerValue(ref = ir.const_ref(0), type_id = types.unit_id, in_memory = false)
return try self.load_from(v.ref, payload)
func else_expr(e: ast.Node*) -> LowerValue!:
let l = e.left else return try self.fail(e, "no operand")
let r = e.right else return try self.fail(e, "no alternative")
let lt = try self.ty(l)
let payload = self.elem(lt)
let v = try self.expr(l)
let leaves = r.kind == ast.Kind.return_ or r.kind == ast.Kind.break_ or r.kind == ast.Kind.continue_ or calls.is_error_call(r) or calls.is_trap_call(r) or r.type_id == types.never_id
let present_label = self.f.label()
let absent_label = self.f.label()
let done = self.f.label()
var slot: u32 = 0
if payload != types.unit_id and payload != types.never_id:
slot = try self.new_slot(payload)
if self.is_fail(lt):
let failed = try self.f.load(ir.Op.loadub, ir.Class.w, try self.offset_address(v.ref, self.failed_offset(lt)))
try self.f.branch(failed, absent_label, present_label)
elif self.is_tagged_opt(lt):
let present = try self.f.load(ir.Op.loadub, ir.Class.w, try self.offset_address(v.ref, self.c.table.size_of(payload)))
try self.f.branch(present, present_label, absent_label)
elif self.is_nullable_view(lt):
let word = try self.f.load(ir.Op.loadl, ir.Class.l, v.ref)
try self.f.branch(word, present_label, absent_label)
else:
try self.f.branch(v.ref, present_label, absent_label)
try self.f.place_label(present_label)
if payload != types.unit_id and payload != types.never_id:
let inner = try self.load_from(v.ref, payload) if not self.is_nullable_ptr(lt) else LowerValue(ref = v.ref, type_id = payload, in_memory = false)
try self.store_to(try self.slot_address(slot), inner)
try self.f.jump(done)
try self.f.place_label(absent_label)
if self.is_fail(lt):
# the operand's error is handled here: an `error` alternative takes its message's
# place, any other gives the message back (§11.3)
if calls.is_error_call(r):
let kept = try self.new_slot(types.str_id)
try self.f.copy_bytes(try self.slot_address(kept), (try self.failure_message()).ref, 16)
self.else_replaced = kept + 1
elif not calls.is_trap_call(r):
try self.message_handled(try self.failure_message())
if leaves:
if calls.is_error_call(r):
try self.error_return(r)
elif r.kind == ast.Kind.return_:
try self.return_stmt(r)
elif r.kind == ast.Kind.break_ or r.kind == ast.Kind.continue_:
try self.jump(r)
else:
_ = try self.expr(r)
try self.trap_with("unreachable")
else:
if payload != types.unit_id and payload != types.never_id:
let alt = try self.value(r, payload)
try self.store_to(try self.slot_address(slot), alt)
else:
_ = try self.expr(r)
try self.f.jump(done)
try self.f.place_label(done)
if payload == types.unit_id or payload == types.never_id:
return LowerValue(ref = ir.const_ref(0), type_id = types.unit_id, in_memory = false)
return try self.load_from(try self.slot_address(slot), payload)
func catch_expr(e: ast.Node*) -> LowerValue!:
let l = e.left else return try self.fail(e, "no operand")
let body = e.body else return try self.fail(e, "no handler")
let payload = try self.ty(l)
let result = try self.ty(e)
let has_value = payload != types.unit_id and payload != types.never_id
let slot = try self.new_slot(result) if has_value else 0
let error_slot = try self.new_slot(types.error_value_id)
let handler = self.f.label()
let done = self.f.label()
let saved_target = self.failure_target
let saved_error = self.failure_slot
let saved_failure_scope = self.failure_scope
let saved_failure_grown = self.failure_grown
self.failure_target = handler
self.failure_slot = error_slot
self.failure_scope = self.scopes.count
self.failure_grown = self.grown.count
let v = try self.value(l, result)
self.failure_target = saved_target
self.failure_slot = saved_error
self.failure_scope = saved_failure_scope
self.failure_grown = saved_failure_grown
if has_value:
try self.store_to(try self.slot_address(slot), v)
try self.f.jump(done)
try self.f.place_label(handler)
if e.text.length > 0:
try self.locals.push(LowerLocal(decl = e, slot = error_slot))
let saved_slot = self.catch_slot
let saved_done = self.catch_done
let saved_scope = self.catch_scope
let saved_payload = self.catch_payload
let saved_in = self.in_catch
self.catch_slot = slot
self.catch_done = done
self.catch_scope = self.scopes.count
self.catch_payload = result
self.in_catch = true
try self.handler_block(body, error_slot)
self.catch_slot = saved_slot
self.catch_done = saved_done
self.catch_scope = saved_scope
self.catch_payload = saved_payload
self.in_catch = saved_in
try self.f.jump(done)
try self.f.place_label(done)
if not has_value:
return LowerValue(ref = ir.const_ref(0), type_id = types.unit_id, in_memory = false)
return try self.load_from(try self.slot_address(slot), result)
## A `catch` handler's body: a scope that gives back the message of the error in
## `error_slot` on every exit but a failure's (§11.3).
func handler_block(b: ast.Node*, error_slot: u32) -> !:
try self.push_scope(false, "", 0, 0)
var sc = self.scopes.get(self.scopes.count - 1)
sc.handler = true
sc.handled = error_slot
self.scopes.set(self.scopes.count - 1, sc)
var cursor = b.body
while let s = cursor:
try self.stmt(s)
cursor = s.next
try self.unwind(self.scopes.count - 1, false)
self.pop_scope()
# -- match ----------------------------------------------------------------------------
## The body of match arm `a`, its value stored for a `match` expression, then out of the
## arm's scope to `done`.
func finish_arm(a: ast.Node*, is_expr: bool, done: u32) -> !:
if let body = a.body:
if is_expr:
let bv = try self.value(body, self.match_type)
try self.store_to(try self.slot_address(self.match_slot), bv)
else:
try self.block(body)
try self.unwind(self.scopes.count - 1, false)
self.pop_scope()
try self.f.jump(done)
func match_stmt(m: ast.Node*, is_expr: bool) -> !:
let scrutinee = m.left else return
let st = try self.ty(scrutinee)
let v = try self.expr(scrutinee)
let done = self.f.label()
# a match on constants dispatches on the value itself, which never goes to memory
if try self.dispatch(m, st, v, done, is_expr):
try self.f.place_label(done)
return
let keep = try self.materialise(v) if not v.in_memory else v.ref
let scrutinee_slot = try self.new_slot(st)
try self.f.copy_bytes(try self.slot_address(scrutinee_slot), keep, self.size(st))
var arm = m.body
while let a = arm:
let take = self.f.label()
let skip = self.f.label()
var pattern = a.left
while let p = pattern:
let next_pattern = self.f.label()
try self.pattern_test(p, st, scrutinee_slot, take, next_pattern)
try self.f.place_label(next_pattern)
pattern = p.next
try self.f.jump(skip)
try self.f.place_label(take)
try self.push_scope(false, "", 0, 0)
# bind the payload of the first payload pattern
var bound = a.left
while let p = bound:
if let pv = p.left:
if pv.kind == ast.Kind.case_value and pv.body != none:
try self.bind_payload(pv, st, scrutinee_slot)
break
bound = p.next
if let guard = a.right:
let g = try self.value(guard, types.bool_id)
let run = self.f.label()
let out = self.f.label()
try self.f.branch(g.ref, run, out)
try self.f.place_label(out)
try self.unwind(self.scopes.count - 1, false)
try self.f.jump(skip)
try self.f.place_label(run)
try self.finish_arm(a, is_expr, done)
try self.f.place_label(skip)
arm = a.next
try self.f.jump(done)
try self.f.place_label(done)
## A `match` on an integer, integer enum, char or bool whose arms have no guard and
## whose patterns are constants, four values or more, finds its arm from the sorted
## values (`search`): through a jump table where they are dense, by binary search where
## they are not, reading the scrutinee `v` where it is, where the chain of
## `pattern_test`s would store it and load and compare once per arm in turn. False,
## having emitted nothing, for any other `match`.
func dispatch(m: ast.Node*, st: u32, v: LowerValue, done: u32, is_expr: bool) -> bool!:
if not (self.is_int(st) or self.c.is_backed_enum(st) or st == types.char_id or st == types.bool_id):
return false
var values = try list.List[i64].create(16)
defer values.destroy()
var branches = try list.List[u32].create(16)
defer branches.destroy()
var takes = try list.List[u32].create(16)
defer takes.destroy()
# the first wildcard's arm takes what no value names; the arms after it never run
var fallback = done
var open = true
var arm = m.body
while let a = arm:
if a.right != none:
return false
let take = self.f.label()
try takes.push(take)
var pattern = a.left
while let p = pattern:
if p.has(ast.flag_wildcard):
if open:
fallback = take
open = false
elif open:
let value = try self.constant_pattern(p, st) else return false
if not holds(values.span(), value):
try values.push(value)
try branches.push(take)
pattern = p.next
arm = a.next
if values.count < 4:
return false
sort_cases(values.span(), branches.span(), self.signed_of(st) or st == types.char_id)
let current = (try self.load_from(v.ref, st)).ref if v.in_memory else v.ref
try self.search(current, st, values.span(), branches.span(), fallback)
var index: usize = 0
arm = m.body
while let a = arm:
try self.f.place_label(takes.get(index))
try self.push_scope(false, "", 0, 0)
try self.finish_arm(a, is_expr, done)
index += 1
arm = a.next
return true
## The value a pattern names when it is a constant of the scrutinee's type (a literal,
## an integer enum's case, a named constant), none for a range or anything computed.
## Whatever lowering it tried is taken back.
func constant_pattern(p: ast.Node*, st: u32) -> i64?!:
if p.right != none:
return none
let v = p.left else return none
if v.kind == ast.Kind.case_value:
let c = v.resolved else return none
let d = self.decl_of(st) else return none
if not self.c.is_backed_enum(st):
return none
return (i64)types.case_value(d, c)
let before = self.f.instrs.count
let lowered = try self.value(v, st)
let emitted = self.f.instrs.count != before
self.f.instrs.count = before
if emitted or lowered.ref.kind != ir.RefKind.constant:
return none
return lowered.ref.value
## Branch on `current` to the target of the value it equals among the sorted `values`,
## else to `fallback`: through a jump table when the values are dense enough
## (`dense_range`), else halve while more than three remain, then compare each.
func search(current: ir.Ref, st: u32, values: i64[], branches: u32[], fallback: u32) -> !:
let cls = self.class_of(st)
if let entries = ir.dense_range(values):
try self.jump_table(current, cls, values, branches, entries, fallback)
return
if values.length <= 3:
for k in 0..<values.length:
let next = self.f.label()
let hit = try self.f.binary(ir.Op.ceq, cls, current, ir.const_ref(values[k]))
try self.f.branch(hit, branches[k], next)
try self.f.place_label(next)
try self.f.jump(fallback)
return
let middle = values.length // 2
let lower = self.f.label()
let upper = self.f.label()
let signed = self.signed_of(st) or st == types.char_id
let below = try self.f.binary(ir.Op.cslt if signed else ir.Op.cult, cls, current, ir.const_ref(values[middle]))
try self.f.branch(below, lower, upper)
try self.f.place_label(lower)
try self.search(current, st, values[..<middle], branches[..<middle], fallback)
try self.f.place_label(upper)
try self.search(current, st, values[middle..], branches[middle..], fallback)
## Jump through a table of `entries` labels from the first of the sorted `values`: each
## value's entry is its target, every value between them none names goes to `fallback`,
## as does whatever lies outside the table.
func jump_table(current: ir.Ref, cls: ir.Class, values: i64[], branches: u32[], entries: usize, fallback: u32) -> !:
var labels = try new u32[entries] ---
defer free(labels)
for k in 0..<entries:
labels[k] = fallback
let low = values[0]
for k in 0..<values.length:
labels[(usize)((u64)values[k] -% (u64)low)] = branches[k]
try self.f.switch(current, cls, low, labels, fallback)
## Branch to `take` when the pattern matches the scrutinee in its slot.
func pattern_test(p: ast.Node*, st: u32, scrutinee_slot: u32, take: u32, miss: u32) -> !:
if p.has(ast.flag_wildcard):
try self.f.jump(take)
return
let v = p.left else return
let a = try self.slot_address(scrutinee_slot)
if v.kind == ast.Kind.case_value and v.resolved == none and self.kind(st) == types.Kind.optional:
# `.some` and `.none` test the optional's presence (§8.4)
let payload = self.elem(st)
let hit = take if v.text == "some" else miss
let other = miss if v.text == "some" else take
if self.is_tagged_opt(st):
let present = try self.f.load(ir.Op.loadub, ir.Class.w, try self.offset_address(a, self.c.table.size_of(payload)))
try self.f.branch(present, hit, other)
else:
let word = try self.f.load(ir.Op.loadl, ir.Class.l, a)
try self.f.branch(word, hit, other)
return
if v.kind == ast.Kind.case_value:
let c = v.resolved else return
let d = self.decl_of(st) else return
if self.c.is_backed_enum(st):
let current = try self.load_from(a, st)
let hit = try self.f.binary(ir.Op.ceq, self.class_of(st), current.ref, ir.const_ref((i64)types.case_value(d, c)))
try self.f.branch(hit, take, miss)
return
let tag = try self.f.load(ir.Op.loadsw, ir.Class.w, a)
let hit = try self.f.binary(ir.Op.ceq, ir.Class.w, tag, ir.const_ref((i64)instances.case_tag(d, c)))
try self.f.branch(hit, take, miss)
return
let current = try self.load_from(a, st)
if let hi = p.right:
let lo = try self.value(v, st)
let hv = try self.value(hi, st)
let signed = self.signed_of(st) or st == types.char_id
let above = try self.f.binary(ir.Op.csge if signed else ir.Op.cuge, self.class_of(st), current.ref, lo.ref)
let mid = self.f.label()
try self.f.branch(above, mid, miss)
try self.f.place_label(mid)
let upper = ir.Op.cslt if p.text == "..<" else ir.Op.csle
let uupper = ir.Op.cult if p.text == "..<" else ir.Op.cule
let below = try self.f.binary(upper if signed else uupper, self.class_of(st), current.ref, hv.ref)
try self.f.branch(below, take, miss)
return
if st == types.str_id:
let text = try self.value(v, st)
let same = try self.text_equal(a, text.ref)
try self.f.branch(same, take, miss)
return
let want = try self.value(v, st)
let hit = try self.f.binary(ir.Op.ceq, self.class_of(st), current.ref, want.ref)
try self.f.branch(hit, take, miss)
func bind_payload(v: ast.Node*, st: u32, scrutinee_slot: u32) -> !:
if v.resolved == none and self.kind(st) == types.Kind.optional:
# `.some(name)`: the value sits first in a tagged optional, and is the word itself
# of a nullable pointer
let payload = self.elem(st)
let at = try self.slot_address(scrutinee_slot)
if let nm = v.body:
if nm.text != "_":
let slot = try self.bind_local(nm, payload)
let value = try self.load_from(at, payload)
try self.store_to(try self.slot_address(slot), value)
return
let c = v.resolved else return
let d = self.decl_of(st) else return
let instance = self.c.table.get(st)
let a = try self.slot_address(scrutinee_slot)
let base = self.payload_offset(st)
var offset: u64 = 0
var name = v.body
var param = c.body
while let nm = name:
let q = param else break
let pt = try self.map(try self.c.substitute(q.type_id, d, instance.args))
offset = lower_round_up(offset, self.c.table.align_of(pt))
if nm.text != "_":
let slot = try self.bind_local(nm, pt)
let value = try self.load_from(try self.offset_address(a, base + offset), pt)
try self.store_to(try self.slot_address(slot), value)
offset += self.c.table.size_of(pt)
name = nm.next
param = q.next
func match_expr(m: ast.Node*) -> LowerValue!:
let t = try self.ty(m)
let saved_slot = self.match_slot
let saved_type = self.match_type
self.match_slot = try self.new_slot(t)
self.match_type = t
try self.f.zero_bytes(try self.slot_address(self.match_slot), self.size(t))
try self.match_stmt(m, true)
let out = try self.load_from(try self.slot_address(self.match_slot), t)
self.match_slot = saved_slot
self.match_type = saved_type
return out