Implementing Polonius: A Rust Borrow Checker Challenge

This challenge focuses on implementing a simplified version of Rust's borrow checker, often referred to as Polonius. Understanding how a borrow checker works is fundamental to comprehending Rust's memory safety guarantees. You will build a system that tracks ownership and borrow rules to determine if a given program segment is valid.

Problem Description

Your task is to create a Rust program that simulates a basic borrow checker. This checker will analyze a simplified representation of code that involves variables, mutable borrows, and immutable borrows. The goal is to determine if the sequence of operations adheres to Rust's borrowing rules.

Key Requirements:

1. Data Representation: You need to define data structures to represent:
   • Variables: Each variable has a unique identifier and an owner.
   • Scopes: Code is divided into scopes, which dictate the lifetime of variables and borrows.
   • Borrows: Track mutable (&mut) and immutable (&) borrows, including which variable they borrow from and their active scope.
2. Rule Enforcement: Implement logic to enforce the following core Rust borrowing rules:
   • One Mutable Borrow: At any given point, a variable can have at most one mutable borrow active.
   • Multiple Immutable Borrows: A variable can have multiple immutable borrows active simultaneously, but no mutable borrows.
   • No Mutable Borrow with Immutable Borrows: If a variable has any active immutable borrows, it cannot have a mutable borrow.
   • No Immutable Borrow with Mutable Borrow: If a variable has an active mutable borrow, it cannot have any immutable borrows.
   • Ownership Transfer: When a variable is assigned to another, its ownership transfers.
   • Borrow Scope: Borrows are only valid within their defined scope.
3. Analysis: Your program should take a sequence of operations (variable declarations, assignments, mutable borrows, immutable borrows, and scope entry/exit) and output whether the sequence is valid according to the rules.

Expected Behavior:

The program should process a series of operations. If at any point an operation violates a borrowing rule, the program should immediately identify it as invalid and stop. If all operations are processed without violations, the program should report the sequence as valid.

Edge Cases:

• Nested scopes.
• Reassigning a variable that is currently borrowed.
• Dropping variables or borrows at the end of their scope.
• Attempting to use a variable after its owner has gone out of scope.

Examples

Example 1:

Input:
[
    ("Declare", "x"),
    ("MutBorrow", "x", "b1"),
    ("ImmutableBorrow", "x", "b2"), // Invalid: Mutable borrow b1 exists
    ("EndScope", "b1"),
    ("EndScope", "b2")
]
Output:
Invalid sequence: Attempted immutable borrow 'b2' on 'x' while mutable borrow 'b1' is active.

Explanation: In this sequence, x is first mutably borrowed as b1. Then, an attempt is made to immutably borrow x as b2. This is invalid because a mutable borrow (b1) already exists, and immutable borrows are not allowed when a mutable borrow is active.

Example 2:

Input:
[
    ("Declare", "y"),
    ("ImmutableBorrow", "y", "b3"),
    ("ImmutableBorrow", "y", "b4"),
    ("EndScope", "b3"),
    ("EndScope", "b4"),
    ("MutBorrow", "y", "b5"),
    ("EndScope", "b5")
]
Output:
Valid sequence.

Explanation: y is declared. Two immutable borrows (b3, b4) are taken, which is allowed. After these borrows end, a mutable borrow (b5) is taken, which is also valid. The entire sequence adheres to the rules.

Example 3: (Nested Scopes and Reassignment)

Input:
[
    ("Declare", "z"),
    ("MutBorrow", "z", "mb1"),
    ("EnterScope", "inner_scope"),
    ("ImmutableBorrow", "z", "ib1"), // Invalid: Mutable borrow mb1 exists
    ("EndScope", "inner_scope"),
    ("EndScope", "mb1")
]
Output:
Invalid sequence: Attempted immutable borrow 'ib1' on 'z' while mutable borrow 'mb1' is active.

Explanation: z is declared and then mutably borrowed (mb1). Inside a nested scope, an attempt is made to immutably borrow z (ib1). This is invalid because the mutable borrow mb1 is still active in an outer scope.

Constraints

• The number of variables will not exceed 100.
• The number of scopes will not exceed 50.
• The total number of operations in a sequence will not exceed 1000.
• Input will be a JSON-like array of operations, each represented as a tuple or struct.
• Variable names and borrow IDs will be alphanumeric strings.
• The simulation should complete within 5 seconds for typical inputs.

Notes

• You can define your own input format or assume a predefined structure. A good starting point is an enum representing the different operations.
• Think about how to represent the "current" state of borrows and ownership. A stack of scopes is often a useful pattern.
• Consider how to manage the lifetime of borrows. A borrow is active from its creation until its corresponding EndScope or until the owner goes out of scope.
• This is a simplified model. Real borrow checkers handle many more complex scenarios (e.g., reborrowing, implicit drops). Focus on the core rules for this challenge.
• The goal is correctness in enforcing the stated rules, not necessarily the most optimized solution.