Compilers: Unused and shadowing warnings

Build the warnings a linter gives about names.

What to build

A program that reports undeclared names, duplicates, shadowing and unused variables in a block-structured program.

Requirements

  • Lines are {, }, let NAME or use NAME, with the scope rules of the previous exercise. A use marks the declaration it resolves to as used.
  • Print, in the order they happen: line K: NAME is not declared; line K: NAME is already declared in this scope (the second declaration is ignored); line K: NAME shadows line D when a new declaration hides a visible one from an outer scope (D is the nearest one); and, when a scope closes (at }, or after the last line for the global scope), line D: NAME is never used for each of its unused declarations in declaration order. If there are none, print no warnings.

Input

Line 1: n. Then n lines; the braces are balanced.

Output

One warning per line, or no warnings.

Constraints

n ≤ 100.

Example

Input:

6
let x
let y
{
let x
use x
}

Output:

line 4: x shadows line 1
line 1: x is never used
line 2: y is never used

Why it works

A symbol table that records what happens to each name can explain mistakes that are legal but probably unintended, which is how linters work.

Examples

Example 1 · Input
6
let x
let y
{
let x
use x
}
Expected output
line 4: x shadows line 1
line 1: x is never used
line 2: y is never used
Example 2 · Input
3
let a
use a
use b
Expected output
line 3: b is not declared

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Store, for each declaration, its line and whether it has been used; mark it used when a use resolves to it.

Hint 2

When a scope is popped, and at the end for the global scope, report its unused declarations in the order they were declared.

Solution

Show one correct solution (try it yourself first)
scopes = [{}]
warnings = []


def close(scope):
    for name, entry in scope.items():
        if not entry["used"]:
            warnings.append(f"line {entry['line']}: {name} is never used")


def resolve(name):
    for scope in reversed(scopes):
        if name in scope:
            return scope[name]
    return None


for k in range(1, int(input()) + 1):
    parts = input().split()
    if parts == ["{"]:
        scopes.append({})
    elif parts == ["}"]:
        close(scopes.pop())
    elif parts[0] == "let":
        name = parts[1]
        if name in scopes[-1]:
            warnings.append(f"line {k}: {name} is already declared in this scope")
            continue
        outer = resolve(name)
        if outer is not None:
            warnings.append(f"line {k}: {name} shadows line {outer['line']}")
        scopes[-1][name] = {"line": k, "used": False}
    else:
        entry = resolve(parts[1])
        if entry is None:
            warnings.append(f"line {k}: {parts[1]} is not declared")
        else:
            entry["used"] = True
close(scopes.pop())
print("\n".join(warnings) if warnings else "no warnings")

Lesson: Symbol tables and scopes →