Implementing Non-Lexical Lifetimes (NLL) in Rust

Rust's borrow checker enforces memory safety by ensuring references are valid throughout their use. While powerful, the traditional borrow checker can sometimes be overly restrictive, preventing valid code from compiling. Non-Lexical Lifetimes (NLL) is an advanced borrow checking analysis that significantly relaxes these restrictions by understanding that a borrow's validity doesn't necessarily extend to the end of its lexical scope. This challenge asks you to implement a simplified version of NLL logic to determine the validity of borrows in a given Rust code snippet.

Problem Description

You will be given a simplified representation of Rust code that involves variables, mutable borrows, immutable borrows, and reassignments. Your task is to build a system that analyzes these operations and determines if the borrowing rules are violated according to NLL principles.

Specifically, you need to:

Represent Code Snippets: Model variables, their initial values, and sequences of operations (assignments, mutable borrows, immutable borrows).
Track Borrow Validity: For each borrow, determine its actual lifetime. NLL states that a borrow is valid as long as it's in use, not necessarily until the end of the scope where it was introduced.
Detect Violations: Identify situations where a variable is accessed (either mutated or immutably borrowed) while it's already borrowed mutably, or where a mutable borrow is attempted while it's already borrowed mutably or immutably. Crucially, NLL allows for re-borrowing if the previous borrow has ended.
Output Violation Status: For each provided code snippet, report whether it's valid according to NLL or not, and if not, pinpoint the specific violation.

Key Requirements:

A variable can have a value.
An immutable borrow (&) requires that the variable is not currently mutably borrowed.
A mutable borrow (&mut) requires that the variable is not currently mutably or immutably borrowed.
A reassignment to a variable is only possible if the variable is not currently borrowed (mutably or immutably).
The lifetime of a borrow is determined by its last use, not by the end of its lexical scope. If a borrow is not used after a certain point, its borrow "ends" there.

Expected Behavior:

Your program should process a series of code snippets. For each snippet, it should simulate the execution and borrowing rules. If a violation is found, it should output "Invalid" along with a description of the violation (e.g., "Mutable borrow of 'x' conflicts with existing mutable borrow"). If the entire snippet executes without violation, it should output "Valid".

Important Edge Cases:

A variable being reassigned after a previous borrow has ended.
Multiple distinct borrows of the same variable that do not overlap in their active periods.
Chained operations where borrows might appear to overlap lexically but do not overlap in actual usage.

Examples

Example 1: Input:

let x = 5;
let y = &x; // Immutable borrow of x
let z = &x; // Another immutable borrow of x

Output:

Valid

Explanation: Two immutable borrows of x are allowed simultaneously as long as x is not mutably borrowed. Both y and z are immutable borrows.

Example 2: Input:

let mut x = 5;
let y = &mut x; // Mutable borrow of x
let z = &x;     // Error: Cannot immutably borrow x while it's mutably borrowed by y

Output:

Invalid: Mutable borrow of 'x' conflicts with existing immutable borrow.

Explanation: y holds a mutable borrow of x. Attempting to create an immutable borrow z while y is still active is a violation.

Example 3: Input:

let mut x = 5;
let y = &mut x; // Mutable borrow of x
// y is not used after this point, so its borrow implicitly ends here.
let z = &x;     // Valid: The mutable borrow by y has ended.

Output:

Valid

Explanation: Although y is declared before z, y is not used after the point where z is created. Therefore, the mutable borrow of x by y is considered to have ended, allowing z to immutably borrow x.

Example 4: Input:

let mut x = 5;
let y = &mut x;
x = 10; // Error: Cannot reassign x while it is mutably borrowed by y

Output:

Invalid: Cannot reassign 'x' while it is mutably borrowed.

Explanation: x is mutably borrowed by y. Reassigning x while it's mutably borrowed is a violation.

Example 5: Input:

let mut x = 5;
let y = &mut x;
let z = y; // z now also refers to the mutable borrow. This is fine.
x = 10; // Error: Cannot reassign x while it is mutably borrowed by y and z

Output:

Invalid: Cannot reassign 'x' while it is mutably borrowed.

Explanation: Both y and z are pointing to the same mutable borrow. Reassigning x is not allowed.

Example 6: Input:

let mut x = 5;
let y = &x;      // Immutable borrow
let z = &mut x;  // Error: Cannot mutably borrow x while it is immutably borrowed by y

Output:

Invalid: Immutable borrow of 'x' conflicts with existing mutable borrow.

Explanation: y holds an immutable borrow. Attempting to create a mutable borrow z while y is still active is a violation.

Constraints

The code snippets will consist of a sequence of operations.
Variables will be named using lowercase letters (e.g., x, y, my_var).
Values will be simple integers.
Operations will be limited to:
- let var = value; (Initialization)
- let var = &other_var; (Immutable borrow)
- let var = &mut other_var; (Mutable borrow)
- var = new_value; (Reassignment)
- var = &other_var; (Reassignment to an immutable borrow - implies the previous borrow ends)
- var = &mut other_var; (Reassignment to a mutable borrow - implies the previous borrow ends)
- Any identifier used without & or &mut will be treated as a variable access for the purpose of checking if it's borrowed. For simplicity, we won't explicitly track usage of immutable borrows. The existence of an active immutable borrow is what matters for subsequent borrows.
The structure of a borrow's validity will be determined by its last use. You will need to infer this. For this challenge, assume that if an identifier bound to a borrow (y in let y = &x;) is not mentioned in any subsequent operation (either directly as a variable name or as the source of a new borrow), its borrow lifetime ends just before that subsequent operation. If it is used, its lifetime extends up to and including that use.
The core of NLL is identifying when a borrow is no longer active. This requires looking ahead to see if and when a variable is next used or re-borrowed.

Notes

This challenge requires a state-tracking mechanism. You'll need to keep track of which variables are currently mutably and immutably borrowed. The key to NLL is realizing that a borrow can end before its lexical scope finishes. This means you can't just check for borrows within a fixed block. You'll need to analyze the sequence of operations and determine the "active" period of each borrow.

Consider how to represent the state of each variable: unborrowed, immutably borrowed (by whom/how many), or mutably borrowed (by whom). The concept of "last use" is crucial here for determining when a borrow is no longer active. For this challenge, you can infer the "last use" by looking at the next operation that involves the variable or the borrow itself. If an identifier bound to a borrow is simply unused afterwards, its borrow ends. If it is used in a later operation, its lifetime extends to that point.

Implementing Non-Lexical Lifetimes (NLL) in Rust

Problem Description

Specifically, you need to:

Represent Code Snippets: Model variables, their initial values, and sequences of operations (assignments, mutable borrows, immutable borrows).
Track Borrow Validity: For each borrow, determine its actual lifetime. NLL states that a borrow is valid as long as it's in use, not necessarily until the end of the scope where it was introduced.
Detect Violations: Identify situations where a variable is accessed (either mutated or immutably borrowed) while it's already borrowed mutably, or where a mutable borrow is attempted while it's already borrowed mutably or immutably. Crucially, NLL allows for re-borrowing if the previous borrow has ended.
Output Violation Status: For each provided code snippet, report whether it's valid according to NLL or not, and if not, pinpoint the specific violation.

Key Requirements:

A variable can have a value.
An immutable borrow (&) requires that the variable is not currently mutably borrowed.
A mutable borrow (&mut) requires that the variable is not currently mutably or immutably borrowed.
A reassignment to a variable is only possible if the variable is not currently borrowed (mutably or immutably).
The lifetime of a borrow is determined by its last use, not by the end of its lexical scope. If a borrow is not used after a certain point, its borrow "ends" there.

Expected Behavior:

Important Edge Cases:

A variable being reassigned after a previous borrow has ended.
Multiple distinct borrows of the same variable that do not overlap in their active periods.
Chained operations where borrows might appear to overlap lexically but do not overlap in actual usage.

Examples

Example 1: Input:

let x = 5;
let y = &x; // Immutable borrow of x
let z = &x; // Another immutable borrow of x

Output:

Valid

Explanation: Two immutable borrows of x are allowed simultaneously as long as x is not mutably borrowed. Both y and z are immutable borrows.

Example 2: Input:

let mut x = 5;
let y = &mut x; // Mutable borrow of x
let z = &x;     // Error: Cannot immutably borrow x while it's mutably borrowed by y

Output:

Invalid: Mutable borrow of 'x' conflicts with existing immutable borrow.

Explanation: y holds a mutable borrow of x. Attempting to create an immutable borrow z while y is still active is a violation.

Example 3: Input:

let mut x = 5;
let y = &mut x; // Mutable borrow of x
// y is not used after this point, so its borrow implicitly ends here.
let z = &x;     // Valid: The mutable borrow by y has ended.

Output:

Valid

Example 4: Input:

let mut x = 5;
let y = &mut x;
x = 10; // Error: Cannot reassign x while it is mutably borrowed by y

Output:

Invalid: Cannot reassign 'x' while it is mutably borrowed.

Explanation: x is mutably borrowed by y. Reassigning x while it's mutably borrowed is a violation.

Example 5: Input:

let mut x = 5;
let y = &mut x;
let z = y; // z now also refers to the mutable borrow. This is fine.
x = 10; // Error: Cannot reassign x while it is mutably borrowed by y and z

Output:

Invalid: Cannot reassign 'x' while it is mutably borrowed.

Explanation: Both y and z are pointing to the same mutable borrow. Reassigning x is not allowed.

Example 6: Input:

let mut x = 5;
let y = &x;      // Immutable borrow
let z = &mut x;  // Error: Cannot mutably borrow x while it is immutably borrowed by y

Output:

Invalid: Immutable borrow of 'x' conflicts with existing mutable borrow.

Explanation: y holds an immutable borrow. Attempting to create a mutable borrow z while y is still active is a violation.

Constraints

The code snippets will consist of a sequence of operations.
Variables will be named using lowercase letters (e.g., x, y, my_var).
Values will be simple integers.
Operations will be limited to:
- let var = value; (Initialization)
- let var = &other_var; (Immutable borrow)
- let var = &mut other_var; (Mutable borrow)
- var = new_value; (Reassignment)
- var = &other_var; (Reassignment to an immutable borrow - implies the previous borrow ends)
- var = &mut other_var; (Reassignment to a mutable borrow - implies the previous borrow ends)
- Any identifier used without & or &mut will be treated as a variable access for the purpose of checking if it's borrowed. For simplicity, we won't explicitly track usage of immutable borrows. The existence of an active immutable borrow is what matters for subsequent borrows.
The structure of a borrow's validity will be determined by its last use. You will need to infer this. For this challenge, assume that if an identifier bound to a borrow (y in let y = &x;) is not mentioned in any subsequent operation (either directly as a variable name or as the source of a new borrow), its borrow lifetime ends just before that subsequent operation. If it is used, its lifetime extends up to and including that use.
The core of NLL is identifying when a borrow is no longer active. This requires looking ahead to see if and when a variable is next used or re-borrowed.