Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.45.0

0.45.0 / src / sema / prune.lucb

#==============================================================================================
#
#   prune - Warnings and what the checker removes after them
#
#   DESCRIPTION:
#       The checker warns about what a program does not use and removes it from the tree,
#       so nothing after the checker sees an unused local, import, or private function, a
#       statement no path reaches, or a branch a literal condition rules out (base.md §19.6).
#       Every removal keeps the program's meaning: an unused binding whose initialiser may do
#       something stays as an expression statement. The checker marks; this module cuts and
#       reports through a `Reporter` positioned in the module's source.
#
#==============================================================================================

import front.ast
import front.source
import support.list
import memory
import sema.types
import strings

# mark: Reachability and pruning =============================================================

## The warnings of one module, each formatted with its position.
pub struct Reporter:
    ## The module's source path, for positions.
    pub var path: str
    ## Its source, for positions.
    pub var src: source.Source
    ## The program's warning list this module appends to.
    pub var warnings: list.List[str]*
    ## A standard module's warnings are nobody's business: it is pruned in silence.
    pub var silent: bool
    ## `--debug`: keep unused locals rather than pruning them.
    pub var keep_locals: bool

    ## Record a warning at `node` saying `what`, unless this module is silent.
    pub func warn(node: ast.Node*, what: str) -> !:
        if self.silent:
            return
        var buffer: u8[512]
        # a directory module's warning names its fragment and the fragment's line, as an error does
        let (name, line, column) = self.src.located(node.start)
        let text = try strings.format(buffer, f"{name}:{line}:{column}: warning: {what}")
        var kept = try new u8[text.length if text.length > 0 else 1] ---
        memory.copy(kept, text.bytes, text.length)
        try self.warnings.push((str)kept[..<text.length])

## Whether a block always leaves: its last statement does.
pub func always_leaves(block: ast.Node*) -> bool:
    var last: ast.Node*? = none
    var cursor = block.body
    while let s = cursor:
        last = s
        cursor = s.next
    let s = last else return false
    return statement_leaves(s)

## Whether control never continues past statement `s`: a `return`, a call that never
## returns, an `if` whose every branch leaves, a `match` whose every arm leaves, a
## `while true` without `break`.
pub func statement_leaves(s: ast.Node*) -> bool:
    match s.kind:
        .return_:
            return true
        .expr_stmt:
            let e = s.left else return false
            return e.type_id == types.never_id or (e.kind == ast.Kind.catch_ and never_completes(e))
        .let_, .var_:
            let e = s.left else return false
            return e.type_id == types.never_id
        .if_:
            let body = s.body else return false
            let rest = s.right else return false
            if not always_leaves(body):
                return false
            if rest.kind == ast.Kind.if_:
                var chain: ast.Node*? = rest
                while let c = chain:
                    let cb = c.body else return false
                    if not always_leaves(cb):
                        return false
                    let next = c.right else return false
                    if next.kind != ast.Kind.if_:
                        return always_leaves(next)
                    chain = next
                return false
            return always_leaves(rest)
        .match_:
            var arm = s.body
            var any = false
            while let a = arm:
                let body = a.body else return false
                if not always_leaves(body):
                    return false
                any = true
                arm = a.next
            return any
        .while_:
            let c = s.left else return false
            return c.kind == ast.Kind.literal and c.text == "true" and not breaks_out(s.body, s.text, false, s.body)
        .with_:
            let body = s.body else return false
            return always_leaves(body)
        .block:
            return always_leaves(s)
        _:
            return false

## A `catch` whose handler always leaves makes the statement never complete.
pub func never_completes(e: ast.Node*) -> bool:
    let body = e.body else return false
    return always_leaves(body)

## Whether a `break` occurs under `node`, a block or an `if` chain. Nested loops are
## searched too, since a labeled `break` may leave the outer loop: the answer errs towards
## "yes", which is the safe direction for what depends on it.
## Whether a `break` sits anywhere under `node`: in a statement, an arm, or an expression's
## `else break` (§8.5, §11.1). A nested loop's own breaks count too, which only keeps what
## follows the outer loop.
pub func contains_break(node: ast.Node*?) -> bool:
    var cursor = node
    while let n = cursor:
        if n.kind == ast.Kind.break_:
            return true
        if contains_break(n.left) or contains_break(n.right) or contains_break(n.body) or contains_break(n.ty):
            return true
        cursor = n.next
    return false

## Whether a `break` under `node`, the body of the loop labeled `label` ("" for none),
## leaves that loop (§8.5): an unlabeled one not inside a nested loop (`nested`), or a
## labeled one unless it names a loop nested inside `root`, the body.
func breaks_out(node: ast.Node*?, label: str, nested: bool, root: ast.Node*?) -> bool:
    var cursor = node
    while let n = cursor:
        if n.kind == ast.Kind.break_:
            if n.text.length == 0 and not nested:
                return true
            if n.text.length > 0 and (n.text == label or not names_loop(root, n.text)):
                return true
        let loop = n.kind == ast.Kind.while_ or n.kind == ast.Kind.for_
        if breaks_out(n.left, label, nested, root) or breaks_out(n.right, label, nested, root) or breaks_out(n.body, label, nested or loop, root) or breaks_out(n.ty, label, nested, root):
            return true
        cursor = n.next
    return false

## Whether a loop labeled `name` lies under `node`.
func names_loop(node: ast.Node*?, name: str) -> bool:
    var cursor = node
    while let n = cursor:
        if (n.kind == ast.Kind.while_ or n.kind == ast.Kind.for_) and n.text == name:
            return true
        if names_loop(n.left, name) or names_loop(n.right, name) or names_loop(n.body, name) or names_loop(n.ty, name):
            return true
        cursor = n.next
    return false

## Whether control certainly never continues past statement `s`: the rule that cuts what
## follows. Unlike `statement_leaves`, which the function-end check uses, this one admits no
## doubt: a `catch` completes when its expression succeeds, and a `match` leaves only when
## a `_` arm makes it total.
pub func certainly_leaves(s: ast.Node*) -> bool:
    match s.kind:
        .return_, .break_, .continue_:
            return true
        .expr_stmt:
            let e = s.left else return false
            return e.type_id == types.never_id and e.kind != ast.Kind.catch_
        .let_, .var_:
            let e = s.left else return false
            return e.type_id == types.never_id and e.kind != ast.Kind.catch_
        .if_:
            if s.has(ast.flag_if_let):
                return false
            let body = s.body else return false
            let rest = s.right else return false
            if not certainly_leaves_block(body):
                return false
            if rest.kind == ast.Kind.if_:
                return certainly_leaves(rest)
            return certainly_leaves_block(rest)
        .match_:
            var arm = s.body
            var total = false
            while let a = arm:
                let body = a.body else return false
                if not certainly_leaves_block(body):
                    return false
                var pattern = a.left
                while let p = pattern:
                    if p.text == "_":
                        total = true
                    pattern = p.next
                arm = a.next
            return total
        .while_:
            let c = s.left else return false
            return c.kind == ast.Kind.literal and c.text == "true" and not breaks_out(s.body, s.text, false, s.body)
        .with_:
            let body = s.body else return false
            return certainly_leaves_block(body)
        .block:
            return certainly_leaves_block(s)
        _:
            return false

## Whether every path through `block` leaves it (returns, breaks, or traps).
pub func certainly_leaves_block(block: ast.Node*) -> bool:
    var last: ast.Node*? = none
    var cursor = block.body
    while let x = cursor:
        last = x
        cursor = x.next
    let s = last else return false
    return certainly_leaves(s)

## An expression whose evaluation neither traps nor has an effect, safe to drop unread.
pub func is_pure(e: ast.Node*?) -> bool:
    let x = e else return true
    match x.kind:
        .literal, .name, .self_:
            return true
        .group, .member:
            return is_pure(x.left)
        .unary:
            return x.text == "&" and is_pure(x.left)
        _:
            return false

## After a block is checked: unused bindings leave, or stay as the expression they
## evaluated when that expression may do something.
pub func prune_block(block: ast.Node*, reporter: Reporter*) -> !:
    var previous: ast.Node*? = none
    var cursor = block.body
    while let s = cursor:
        let binding = s.kind == ast.Kind.let_ or s.kind == ast.Kind.var_
        if binding and s.has(ast.flag_unused):
            var text: u8[512]
            try reporter.warn(s, try strings.format(text, f"unused local `{s.text}`"))
            if reporter.keep_locals:
                previous = s
                cursor = s.next
                continue
            if s.left == none or is_pure(s.left):
                if let p = previous:
                    p.next = s.next
                else:
                    block.body = s.next
                cursor = s.next
                continue
            s.kind = ast.Kind.expr_stmt
            s.text = ""
            s.ty = none
        previous = s
        cursor = s.next

## `if true:` keeps its body and `if false:` its alternative; `while false:` is nothing.
## `quiet` says the literal stood for a named constant, `if os.arm64:`, whose ruled-out
## branch is meant to go and draws no warning.
pub func fold_constant_branch(s: ast.Node*, reporter: Reporter*, quiet: bool) -> !:
    let c = s.left else return
    if c.kind != ast.Kind.literal or (c.text != "true" and c.text != "false"):
        return
    let truth = c.text == "true"
    if s.kind == ast.Kind.while_:
        if truth:
            return
        if not quiet:
            try reporter.warn(s, "this loop never runs: its condition is `false`")
        s.kind = ast.Kind.block
        s.body = none
        s.left = none
        return
    let taken = s.body if truth else s.right
    let dropped = s.right if truth else s.body
    if let d = dropped:
        if not quiet:
            try reporter.warn(d, "this branch never runs: the condition is `true`" if truth else "this branch never runs: the condition is `false`")
    s.kind = ast.Kind.block
    s.left = none
    s.right = none
    if let t = taken:
        if t.kind == ast.Kind.block:
            s.body = t.body
        else:
            t.next = none
            s.body = t
    else:
        s.body = none

## A private function the module's live code does not reach leaves the module. `main`,
## `answer`, tests, exports, hidden lambdas, and anything with an attribute stay, as do
## methods and the standard modules' own functions, which the backends may name directly;
## they and every other declaration are the roots, and a private function stays when a
## root's tree, or the tree of one that stays, names it. What the checker cut before this,
## a branch another target's constant rules out and the code after it, names nothing, so a
## function only that code reached goes, and so does one only such a function reached,
## and so on. A function nothing named at all is warned about; one only cut code named is
## gone in silence, as the code that named it is.
pub func prune_unused_functions(tree: ast.Node*, reporter: Reporter*, is_prelude: bool) -> !:
    if is_prelude:
        return
    # the candidates' names as the checker saw them, then each marked again when reached
    var named = try list.List[bool].create(16)
    defer named.destroy()
    var cursor = tree.body
    while let d = cursor:
        if is_prunable(d):
            try named.push(d.has(ast.flag_referenced))
            d.flags &= ~ast.flag_referenced
        cursor = d.next
    var reached = try list.List[ast.Node*].create(16)
    defer reached.destroy()
    cursor = tree.body
    while let d = cursor:
        if not is_prunable(d):
            try reach_names(d, tree, &reached)
        cursor = d.next
    var next: usize = 0
    while next < reached.count:
        try reach_names(reached.get(next), tree, &reached)
        next += 1
    var previous: ast.Node*? = none
    var index: usize = 0
    cursor = tree.body
    while let d = cursor:
        if is_prunable(d):
            let was_named = named.get(index)
            index += 1
            if not d.has(ast.flag_referenced):
                if not was_named:
                    var text: u8[512]
                    try reporter.warn(d, try strings.format(text, f"unused function `{d.text}`"))
                if let p = previous:
                    p.next = d.next
                else:
                    tree.body = d.next
                cursor = d.next
                continue
        previous = d
        cursor = d.next

## Whether top-level declaration `d` is a private function that leaves the module unless
## something live names it.
func is_prunable(d: ast.Node*) -> bool:
    return d.kind == ast.Kind.func_ and not d.has(ast.flag_pub) and not d.has(ast.flag_export) and not d.has(ast.flag_lambda) and d.attrs == none and d.text != "main" and d.text != "answer"

## Every prunable function of module `tree` that the tree of `node` names, marked
## referenced and queued on `reached` the first time; `node`'s own siblings are not part
## of its tree, and another module's functions are that module's business.
func reach_names(node: ast.Node*, tree: ast.Node*, reached: list.List[ast.Node*]*) -> !:
    if let d = node.resolved:
        if d.resolved == tree and is_prunable(d) and not d.has(ast.flag_referenced):
            d.flags |= ast.flag_referenced
            try reached.push(d)
    if let x = node.left:
        try reach_list(x, tree, reached)
    if let x = node.right:
        try reach_list(x, tree, reached)
    if let x = node.body:
        try reach_list(x, tree, reached)
    if let x = node.ty:
        try reach_list(x, tree, reached)
    if let x = node.attrs:
        try reach_list(x, tree, reached)

## `reach_names` over `first` and the siblings after it.
func reach_list(first: ast.Node*, tree: ast.Node*, reached: list.List[ast.Node*]*) -> !:
    var cursor: ast.Node*? = first
    while let n = cursor:
        try reach_names(n, tree, reached)
        cursor = n.next

## An import nothing resolved through leaves the tree here, so nothing after the checker
## sees it (§16.3).
pub func prune_unused_imports(tree: ast.Node*, reporter: Reporter*) -> !:
    var previous: ast.Node*? = none
    var cursor = tree.body
    while let d = cursor:
        let unused = (d.kind == ast.Kind.import_ or d.kind == ast.Kind.from_import) and not d.has(ast.flag_referenced)
        if unused:
            var text: u8[512]
            try reporter.warn(d, try strings.format(text, f"unused import `{d.text}`"))
            if let p = previous:
                p.next = d.next
            else:
                tree.body = d.next
        else:
            previous = d
        cursor = d.next