Validate Evaluation Chains and Resolve Boolean Outcomes

Problem Statement

You are building a rule engine for evaluating dependency chains in financial compliance checks. Each rule is represented by a unique string identifier and is defined by one of the following expressions:

• Literal: "TRUE" or "FALSE"
• Direct reference: "" (evaluates to the value of rule ``)
• Negated reference: "NOT " (evaluates to the logical negation of rule ``)

Rules may depend on other rules, forming evaluation chains across possibly disconnected components. However, circular dependencies can occur (e.g., A depends on B, and B depends on A). Any rule that is part of a cycle, points directly to a cycle, or points to an undefined rule cannot be resolved.

Write a function resolve_chains(definitions: dict[str, str]) -> dict[str, Optional[bool]] that resolves every rule in definitions to True, False, or None if it cannot be determined.

Function Signature

from typing import Optional

def resolve_chains(definitions: dict[str, str]) -> dict[str, Optional[bool]]:
    pass

Input

• definitions: A dictionary mapping rule names (str) to expression strings (str).
  • An expression is either "TRUE", "FALSE", "", or "NOT ", where `` is a string token.

Output

• A dictionary mapping every key present in definitions to True, False, or None.

Constraints

• 1 <= len(definitions) <= 10^5
• Rule names contain only alphanumeric characters and underscores.
• The time complexity must be O(V + E), where V is the number of rules.

Examples

Example 1

input_data = {
    "A": "NOT B",
    "B": "C",
    "C": "TRUE",
    "D": "NOT C"
}
# Output:
# {"A": False, "B": True, "C": True, "D": False}

Explanation: C is True. B references C, so B = True. A is NOT B, so A = False. D is NOT C, so D = False.

Example 2

input_data = {
    "X": "NOT Y",
    "Y": "X",
    "Z": "Y",
    "W": "TRUE"
}
# Output:
# {"X": None, "Y": None, "Z": None, "W": True}

Explanation: X and Y form a cycle. Z points into the cycle through Y. None of X, Y, or Z can be resolved. W is independent and resolves to True.

Example 3

input_data = {
    "A": "B",
    "B": "NOT MISSING_VAR"
}
# Output:
# {"A": None, "B": None}

Explanation: B references MISSING_VAR, which is not in definitions. Therefore, both B and A resolve to None.