Evaluate Variables in a Simple Arithmetic DSL

You are tasked with implementing an evaluator for a small domain-specific language (DSL) that defines variable assignments.

DSL Specification

The DSL consists of variable assignments, one per line, each following this form:

<identifier> = <expression>

• <identifier>: Represents a variable name. It must conform to the regular expression [a-zA-Z_][a-zA-Z0-9_]*.
• <expression>: A mathematical expression involving sums and differences of integer literals and variable references.
• Operators: Only + (addition) and - (subtraction) are supported.
• Evaluation Order: There are no parentheses; expressions are evaluated strictly from left-to-right.
• Whitespace: Arbitrary whitespace may appear anywhere (around =, operators, identifiers, etc.) and must be ignored during parsing and evaluation.

All variables are of integer type. Variables can depend on other variables, which might be defined either before or after them in the input program. The dependency graph may contain chains (e.g., a depends on b, which depends on c, and so on), and all such dependencies must be resolved.

Task

Implement a function with the following pseudo-signature:

evaluate(program: string) -> Map<string, int>

• program: A multi-line string where each non-empty line represents one variable assignment.
• Return Value: A mapping from variable names to their computed integer values for all variables that can be successfully evaluated.

Requirements & Edge Cases

1. Basic Evaluation:

   • Example Input:

     foo = bar + 5
     bar = 2
     

   • Expected Output: { "bar": 2, "foo": 7 } (order not important)

2. Multi-level Dependencies:

   • Variables can depend on others that themselves depend on more variables.
   • Example Input:

     foo = bar + 1
     bar = baz + 1
     baz = 3
     

   • Expected Output: { "baz": 3, "bar": 4, "foo": 5 }

3. Whitespace Robustness: Your parser must correctly handle arbitrary spacing, including no spaces at all.

   • These examples should all be parsed equivalently:

     foo=bar+5-baz
     foo = bar + 5 - baz
     foo  =   bar  +  5 -   baz
     

   • Extra spaces around variable names in keys or expressions (e.g., "bar " ) must be trimmed so that variable lookup works correctly.

4. Undefined Variables:

   • If an expression references a variable that is never assigned anywhere in the program, that referencing variable cannot be evaluated.
   • Your function must detect undefined variables and handle this situation in a well-defined way (e.g., by throwing an exception or returning an error structure). Clearly document your chosen behavior.

5. Cyclic Dependencies:

   • If a cycle exists in the dependency graph (e.g., foo = bar + 1, bar = foo + 1), neither variable can be meaningfully evaluated.
   • Your function must detect cyclic dependencies (e.g., via graph-based cycle detection) and handle this in a well-defined way (e.g., report a cyclic dependency error).

6. Partial Evaluability:

   • Some variables might be evaluable even if others are not.
   • Example:

     ok  = 1
     bad = missing + 1
     

   • You must choose one of the following behaviors and document it clearly:
     • (a) Fail the entire evaluation if any variable is invalid (undefined or cyclic).
     • (b) Return values for all variables that can be evaluated and separately report the ones that cannot.

7. Constraints & Complexity:

   • Assume up to N variables and up to M total tokens across all expressions. N and M can be large.
   • Design your algorithm for efficiency in terms of time and space, targeting approximately O(N + M) time complexity if possible.

What to Provide

• Code (in a language of your choice) implementing evaluate(program: string) according to the rules above.
• A brief explanation covering:
  • How you build and represent the dependency graph.
  • How you determine the correct evaluation order for variables.
  • How you detect and handle undefined variables and cyclic dependencies.
  • The time and space complexity of your solution.