Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.46.0

0.46.0 / src / sema / check / mutation.lucb

#==============================================================================================
#
#   check/mutation - Which methods change their receiver
#
#   DESCRIPTION:
#       Nothing is written on a method about its receiver (§9.5): one that changes it is
#       found from its body. Before any body is checked, a walk of each method finds the
#       changes it spells out: an assignment to `self` or a part of it, a changing method
#       called on one, and the same through a local that holds its address; a method calling
#       another of the module on `self` follows that one, until nothing changes. The checker
#       then finds the rest where a body takes the receiver's address, or a part's, as
#       mutable. A call that leaned on a method of this module whose answer was not final yet
#       is kept and settled when the module's bodies are done.
#
#==============================================================================================

## A use that depended on whether `method` changes its receiver, before that was final:
## a call on a receiver that cannot change, or a view formed from one (§14.3). When
## `method` turns out to change it, the use is refused, or, when the receiver is part of
## the receiver of `caller`, `caller` changes its receiver too.
struct PendingChange:
    var at: ast.Node*
    var method: ast.Node*
    var caller: ast.Node*?
    ## The use is the method taken as a function value, typed as one that reads.
    var value: bool = false

## A requirement a generic body calls on a value of its parameter `param` that it may not
## change: an instantiation whose argument implements it by changing its receiver is
## refused (§13.1, §14.2).
struct ReadOnlyUse:
    var param: ast.Node*
    var requirement: str

## A generic passing a value of its parameter `to` on as another generic's parameter
## `passed`: what that one calls on a value it may not change, this one does too.
struct UseForward:
    var passed: ast.Node*
    var to: ast.Node*

## An instantiation of `param` with `argument` at `at`, settled when this module's methods
## are final.
struct PendingInstance:
    var at: ast.Node*
    var param: ast.Node*
    var argument: u32

## A local that holds the address of the receiver or a part of it, and the type of the
## place it reaches: what is written through it is written to the receiver.
struct ReceiverAlias:
    var name: str
    var place: u32

extend Checker:
    # mark: Changes written out ================================================================

    ## Mark every method of `tree`'s types whose body changes its receiver by what it
    ## spells out, following calls between them until nothing changes.
    func infer_receiver_changes(tree: ast.Node*) -> !:
        var aliases = try list.List[ReceiverAlias].create(8)
        var changed = true
        while changed:
            changed = false
            var cursor = tree.body
            while let d = cursor:
                if d.kind == ast.Kind.struct_ or d.kind == ast.Kind.enum_ or d.kind == ast.Kind.union_:
                    var member = d.body
                    while let m = member:
                        if m.kind == ast.Kind.func_ and not m.has(ast.flag_static) and not m.has(ast.flag_mutating) and m.text != "init":
                            aliases.count = 0
                            if try self.body_changes(d, m.body, &aliases):
                                m.flags |= ast.flag_mutating
                                changed = true
                        member = m.next
                cursor = d.next

    ## Whether the statements and expressions from `n` on, siblings included, change the
    ## receiver of a method of `d`.
    func body_changes(d: ast.Node*, n: ast.Node*?, aliases: list.List[ReceiverAlias]*) -> bool!:
        var cursor = n
        while let s = cursor:
            if try self.node_changes(d, s, aliases):
                return true
            cursor = s.next
        return false

    func node_changes(d: ast.Node*, s: ast.Node*, aliases: list.List[ReceiverAlias]*) -> bool!:
        match s.kind:
            .lambda:
                # a lambda's body is a function of its own, with no receiver (§9.6)
                return false
            .assign:
                if let place = s.left:
                    if try self.receiver_place(d, place, aliases) != types.none_id:
                        return true
            .let_, .var_:
                try self.note_alias(d, s, aliases)
            .for_:
                # the loop's binding is noted here, not walked as a `let` of its own
                try self.note_loop_alias(d, s, aliases)
                if let iterable = s.right:
                    if try self.node_changes(d, iterable, aliases):
                        return true
                return try self.body_changes(d, s.body, aliases)
            .call:
                if try self.changing_call(d, s, aliases) or try self.passes_receiver(d, s, aliases):
                    return true
            .with_, .new_, .new_unwritten, .free_:
                # allocating from an allocator the receiver holds changes it (§12.3)
                let allocator = s.left if s.kind == ast.Kind.with_ else s.right
                if let a = allocator:
                    let place = try self.receiver_place(d, a, aliases)
                    if place != types.none_id and self.table.kind(place) == types.Kind.struct_:
                        return true
            _:
                _ = 0
        if let l = s.left:
            if try self.node_changes(d, l, aliases):
                return true
        if let r = s.right:
            if try self.node_changes(d, r, aliases):
                return true
        return try self.body_changes(d, s.body, aliases)

    ## `recv.name(...)` where `recv` is the receiver or a part of it and `name` changes it.
    func changing_call(d: ast.Node*, call: ast.Node*, aliases: list.List[ReceiverAlias]*) -> bool!:
        let callee = call.left else return false
        if callee.kind != ast.Kind.member:
            return false
        let receiver = callee.left else return false
        let place = try self.receiver_place(d, receiver, aliases)
        if place == types.none_id:
            return false
        let t = self.table.get(place)
        if t.kind == types.Kind.atomic:
            # an atomic's operations store, its `load` and `wait` aside (§15.1)
            return callee.text != "load" and callee.text != "wait"
        if t.kind != types.Kind.struct_ and t.kind != types.Kind.enum_ and t.kind != types.Kind.union_:
            return false
        let owner = t.decl else return false
        let m = find_member(owner, callee.text, ast.Kind.func_) else return false
        return m.has(ast.flag_mutating) and not m.has(ast.flag_static)

    ## `f(p)` where `p` holds the address of the receiver or a part of it, `f(&self.part)`,
    ## `f(self.cells[..])`: the receiver reaches a parameter that may change it, a mutable
    ## pointer or span, of a function or method this pass can name.
    func passes_receiver(d: ast.Node*, call: ast.Node*, aliases: list.List[ReceiverAlias]*) -> bool!:
        let callee = call.left else return false
        let target = try self.called_function(d, callee, aliases) else return false
        let ft = self.table.get(target.type_id)
        if ft.kind != types.Kind.func_:
            return false
        var position: usize = 0
        var cursor = call.body
        while let a = cursor:
            cursor = a.next
            var index = position
            if a.text.length > 0:
                if let named = param_index(target, a.text):
                    index = named
                else:
                    continue
            else:
                position += 1
            let value = a.left else continue
            if index < ft.args.length and self.wants_change(ft.args[index]) and try self.reaches_receiver(d, value, aliases):
                return true
        return false

    ## The function a call's callee names before bodies are checked: one of the module or
    ## an import, `module.f`, `Type.f`, or a method of the receiver or a part of it.
    func called_function(d: ast.Node*, callee: ast.Node*, aliases: list.List[ReceiverAlias]*) -> ast.Node*?!:
        if callee.kind == ast.Kind.name:
            let b = self.lookup(callee.text) else return none
            let decl = b.decl else return none
            return decl if decl.kind == ast.Kind.func_ else none
        if callee.kind != ast.Kind.member:
            return none
        let owner = callee.left else return none
        var holder: ast.Node*? = none
        let place = try self.receiver_place(d, owner, aliases)
        if place != types.none_id:
            holder = self.table.get(place).decl
        elif owner.kind == ast.Kind.name:
            let b = self.lookup(owner.text) else return none
            if self.table.kind(b.type_id) == types.Kind.module:
                let tree = self.table.get(b.type_id).decl else return none
                let decl = self.module_decl(tree, callee.text) else return none
                return decl if decl.kind == ast.Kind.func_ else none
            holder = b.decl
        let h = holder else return none
        if not is_type_decl(h):
            return none
        return find_member(h, callee.text, ast.Kind.func_)

    ## Whether a parameter of type `id` may change what it is given: a mutable pointer or
    ## span, or an optional one.
    func wants_change(id: u32) -> bool:
        var t = self.table.get(id)
        if t.kind == types.Kind.optional:
            t = self.table.get(t.elem)
        return (t.kind == types.Kind.pointer or t.kind == types.Kind.span) and not t.is_const

    ## Whether `value` is the address of the receiver or a part of it, a span of its array,
    ## or a local holding either.
    func reaches_receiver(d: ast.Node*, value: ast.Node*, aliases: list.List[ReceiverAlias]*) -> bool!:
        match value.kind:
            .name:
                return try self.receiver_place(d, value, aliases) != types.none_id
            .group:
                let inner = value.left else return false
                return try self.reaches_receiver(d, inner, aliases)
            .unary:
                let inner = value.left else return false
                return value.text == "&" and try self.receiver_place(d, inner, aliases) != types.none_id
            .slice:
                let owner = value.left else return false
                return self.table.kind(try self.receiver_place(d, owner, aliases)) == types.Kind.array
            _:
                return false

    ## `let p = &self.part`, `let row = self.cells[..]`: a local that reaches the receiver.
    func note_alias(d: ast.Node*, s: ast.Node*, aliases: list.List[ReceiverAlias]*) -> !:
        forget_alias(aliases, s.text)
        if s.ty != none:
            return
        let init = s.left else return
        var place = types.none_id
        if init.kind == ast.Kind.unary and init.text == "&":
            if let inner = init.left:
                place = try self.receiver_place(d, inner, aliases)
        elif init.kind == ast.Kind.slice:
            if let owner = init.left:
                let whole = try self.receiver_place(d, owner, aliases)
                if self.table.kind(whole) == types.Kind.array:
                    place = whole
        if place != types.none_id:
            try aliases.push(ReceiverAlias(name = s.text, place = place))

    ## `for p in &self.items`: each `p` reaches an element of the receiver.
    func note_loop_alias(d: ast.Node*, s: ast.Node*, aliases: list.List[ReceiverAlias]*) -> !:
        let binding = s.left else return
        forget_alias(aliases, binding.text)
        if not s.has(ast.flag_by_pointer) or binding.body != none:
            return
        let iterable = s.right else return
        let whole = try self.receiver_place(d, iterable, aliases)
        if self.table.kind(whole) == types.Kind.array:
            try aliases.push(ReceiverAlias(name = binding.text, place = self.table.get(whole).elem))

    ## The type of place `e` when it is the receiver of a method of `d` or a part of it,
    ## reached through fields and array elements and never through a pointer or a span, or
    ## through a local holding such an address; `none_id` otherwise.
    func receiver_place(d: ast.Node*, e: ast.Node*, aliases: list.List[ReceiverAlias]*) -> u32!:
        match e.kind:
            .self_:
                return d.type_id
            .name:
                for a in aliases.span():
                    if a.name == e.text:
                        return a.place
                return types.none_id
            .group:
                let inner = e.left else return types.none_id
                return try self.receiver_place(d, inner, aliases)
            .unary:
                # `*p` where `p` holds the receiver's address
                let inner = e.left else return types.none_id
                if e.text != "*" or inner.kind != ast.Kind.name:
                    return types.none_id
                return try self.receiver_place(d, inner, aliases)
            .member:
                let owner = e.left else return types.none_id
                let whole = try self.receiver_place(d, owner, aliases)
                if whole == types.none_id:
                    return types.none_id
                return try self.part_type(whole, e.text)
            .index:
                let owner = e.left else return types.none_id
                let whole = try self.receiver_place(d, owner, aliases)
                let t = self.table.get(whole)
                return t.elem if whole != types.none_id and t.kind == types.Kind.array else types.none_id
            _:
                return types.none_id

    ## The type of field or tuple member `name` of a value of type `whole`; `none_id` for
    ## anything a value does not hold in place.
    func part_type(whole: u32, name: str) -> u32!:
        let t = self.table.get(whole)
        if t.kind == types.Kind.tuple:
            var index: usize = 0
            for b in name.bytes:
                if b < '0' or b > '9':
                    return types.none_id
                index = index * 10 + (usize)(b - '0')
            return t.args[index] if index < t.args.length else types.none_id
        if t.kind != types.Kind.struct_ and t.kind != types.Kind.union_:
            return types.none_id
        let owner = t.decl else return types.none_id
        let field = find_member(owner, name, ast.Kind.field) else return types.none_id
        return try self.substitute(field.type_id, owner, t.args)

    # mark: Changes the checker finds ===========================================================

    ## Whether `e` is the receiver of the method being checked or a part of it, reached
    ## through fields and array elements, never through a pointer or a span (§9.5).
    func rooted_at_self(e: ast.Node*) -> bool:
        match e.kind:
            .self_:
                return self.self_type != types.none_id
            .group:
                let inner = e.left else return false
                return self.rooted_at_self(inner)
            .member:
                let owner = e.left else return false
                let k = self.table.kind(owner.type_id)
                if k == types.Kind.pointer or k == types.Kind.module:
                    return false
                if let field = e.resolved:
                    if field.kind == ast.Kind.global or field.kind == ast.Kind.extern_var:
                        return false
                return self.rooted_at_self(owner)
            .index:
                let owner = e.left else return false
                return self.table.kind(owner.type_id) == types.Kind.array and self.rooted_at_self(owner)
            _:
                return false

    ## `e` must change and is not mutable here. When it is the receiver of the method being
    ## checked, or a part of it, the method changes its receiver from here on (§9.5): true.
    func changes_receiver(e: ast.Node*) -> bool:
        let f = self.current_func else return false
        if self.self_type == types.none_id or f.has(ast.flag_static) or not self.rooted_at_self(e):
            return false
        f.flags |= ast.flag_mutating
        self.self_mutable = true
        return true

    ## Whether `hint` wants a pointer to `pointee` that may change it: a mutable pointer, or
    ## a view whose conformer's methods change their receiver (§6.6, §14.3); `place` is
    ## what the address is taken of.
    func wants_changing_view(hint: u32, pointee: u32, place: ast.Node*) -> bool!:
        var wanted = hint
        if self.table.kind(wanted) == types.Kind.optional:
            wanted = self.table.get(wanted).elem
        let h = self.table.get(wanted)
        if h.kind == types.Kind.pointer:
            return not h.is_const
        if h.kind == types.Kind.interface_ and self.rooted_at_self(place):
            # a view of anything else is settled where it is checked against the view
            return try self.implementation_changes(place, pointee, wanted)
        return false

    ## Whether `hint` wants a span that may change its elements.
    func wants_mutable_span(hint: u32) -> bool:
        var h = self.table.get(hint)
        if h.kind == types.Kind.optional:
            h = self.table.get(h.elem)
        return h.kind == types.Kind.span and not h.is_const

    ## Before `e` of type `got` is checked against `target` or an optional of it: the
    ## receiver's array where a mutable span is wanted changes the receiver, and a view
    ## formed from a read-only pointer waits on the conformer's methods while they are not
    ## final. (`&self.part` settled this where its address was taken.)
    func note_change_of(e: ast.Node*, got: u32, target: u32) -> !:
        var wanted = target
        if self.table.kind(wanted) == types.Kind.optional and self.table.kind(got) != types.Kind.optional:
            wanted = self.table.get(wanted).elem
        let t = self.table.get(wanted)
        let s = self.table.get(got)
        if t.kind == types.Kind.span and not t.is_const and s.kind == types.Kind.array and not self.is_mutable_place(e):
            _ = self.changes_receiver(e)
        elif t.kind == types.Kind.interface_ and s.kind == types.Kind.pointer and s.is_const:
            if e.kind == ast.Kind.unary and e.text == "&":
                if let inner = e.left:
                    if self.rooted_at_self(inner):
                        return
            _ = try self.implementation_changes(e, s.elem, wanted)

    ## Whether any method of conformer `id` implementing a requirement of `iface` changes its
    ## receiver; one of this module's not yet final is kept to settle at `at` (§14.3).
    func implementation_changes(at: ast.Node*, id: u32, iface: u32) -> bool!:
        let t = self.table.get(id)
        let d = t.decl else return false
        let i = self.table.get(iface).decl else return false
        var requirement = i.body
        while let r = requirement:
            if let m = find_member(d, r.text, ast.Kind.func_):
                if m.has(ast.flag_mutating):
                    return true
                try self.keep_pending_change(at, m, d)
            requirement = r.next
        return false

    ## `method` taken as a function value at `at` and typed as one that reads its receiver,
    ## while it may still turn out to change it: kept when `owner` is a type of this module.
    func keep_pending_value(at: ast.Node*, method: ast.Node*, owner: ast.Node*) -> !:
        if method.has(ast.flag_mutating) or method.has(ast.flag_static) or method.body == none:
            return
        let module = try self.owner_of(owner) else return
        if module == self.current:
            try self.pending_changes.push(PendingChange(at = at, method = method, caller = none, value = true))

    ## A use of `method` on a receiver that cannot change, at `at`, while `method` may still
    ## turn out to change its receiver: kept when `owner` is a type of this module.
    func keep_pending_change(at: ast.Node*, method: ast.Node*, owner: ast.Node*) -> !:
        if method.has(ast.flag_mutating) or method.has(ast.flag_static) or method.body == none:
            return
        let module = try self.owner_of(owner) else return
        if module != self.current:
            return
        var caller: ast.Node*? = none
        if self.rooted_at_self(at):
            caller = self.current_func
        try self.pending_changes.push(PendingChange(at = at, method = method, caller = caller))

    ## Settle the uses kept while this module's methods were being checked: a method whose
    ## receiver's part met a changing method changes its receiver too, until nothing does;
    ## then every other use of a changing method on a receiver that cannot change is refused.
    func settle_pending_changes() -> !:
        var changed = true
        while changed:
            changed = false
            for p in self.pending_changes.span():
                if let caller = p.caller:
                    if p.method.has(ast.flag_mutating) and not caller.has(ast.flag_mutating):
                        caller.flags |= ast.flag_mutating
                        changed = true
        for p in self.pending_changes.span():
            if p.caller == none and p.method.has(ast.flag_mutating):
                let (name, line, column) = self.located(p.at)
                var text: u8[512]
                if p.value:
                    try self.keep_error(said(text, f"{name}:{line}:{column}: `{p.method.text}` changes its receiver, which its body showed only after its value was taken here as a function that reads it; take the value below the method's own uses (§9.5)"))
                else:
                    try self.keep_error(said(text, f"{name}:{line}:{column}: `{p.method.text}` changes its receiver, so it needs a `var` or a mutable pointer here (§9.5)"))
        self.pending_changes.count = 0

    # mark: Generic instances =================================================================

    ## A requirement called on a value of generic parameter `id` that may not change there.
    func note_read_only_use(id: u32, requirement: str) -> !:
        let g = self.generic_param_node(id) else return
        for u in self.read_only_uses.span():
            if u.param == g and u.requirement == requirement:
                return
        try self.read_only_uses.push(ReadOnlyUse(param = g, requirement = requirement))

    ## Generic parameter `g` takes `argument` at `at`: a parameter of the generic being
    ## checked passes its uses on; a type is settled with this module's methods.
    func note_instance(g: ast.Node*, argument: u32, at: ast.Node*) -> !:
        let t = self.table.get(argument)
        if t.kind == types.Kind.param:
            if let to = self.generic_param_node(argument):
                try self.use_forwards.push(UseForward(passed = g, to = to))
            return
        let instance = t.elem if t.kind == types.Kind.pointer and t.is_const else argument
        if self.table.get(instance).decl != none:
            try self.pending_instances.push(PendingInstance(at = at, param = g, argument = instance))

    ## Every instantiation of this module against what its generic calls on values it may
    ## not change, the parameters it passes on included.
    func settle_pending_instances() -> !:
        for p in self.pending_instances.span():
            var seen = try list.List[ast.Node*].create(4)
            try self.settle_instance(p, p.param, &seen)
        self.pending_instances.count = 0

    func settle_instance(p: PendingInstance, param: ast.Node*, seen: list.List[ast.Node*]*) -> !:
        for s in seen.span():
            if s == param:
                return
        try seen.push(param)
        let d = self.table.get(p.argument).decl else return
        for u in self.read_only_uses.span():
            if u.param == param:
                if let m = find_member(d, u.requirement, ast.Kind.func_):
                    if m.has(ast.flag_mutating):
                        let generic = self.table.get(param.type_id).decl
                        let (name, line, column) = self.located(p.at)
                        var text: u8[512]
                        try self.keep_error(said(text, f"{name}:{line}:{column}: `{d.text}.{m.text}` changes its receiver, and `{(generic else param).text}` calls it on a value it may not change (§13.1)"))
                        return
        for f in self.use_forwards.span():
            if f.to == param:
                try self.settle_instance(p, f.passed, seen)

## Drop the alias named `name`: a new binding of that name holds something else.
func forget_alias(aliases: list.List[ReceiverAlias]*, name: str):
    var i: usize = 0
    while i < aliases.count:
        if aliases.get(i).name == name:
            aliases.set(i, aliases.get(aliases.count - 1))
            aliases.count -= 1
        else:
            i += 1