dymokomi/luce-base
Source of release 0.46.0
0.46.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