fluidattacks-blends-domain 0.40.0

//! Deterministic resolution helpers for the multifile cfg.
//!
//! Resolve symbols along backward paths to the literal values of their
//! definitions and fold constant conditions by value type so a
//! dispatcher can commit to a single branch.

use alloc::collections::{BTreeMap, BTreeSet};
use alloc::string::String;
use alloc::vec;
use alloc::vec::Vec;

use crate::query::{
    adj_ast, adj_cfg, lookup_first_cfg_parent, match_ast_group_d, pred_ast, pred_cfg,
};
use crate::syntax::fold::{fold, fold_leaf, strip_quotes, Folded};
use crate::syntax::{SyntaxGraph, SyntaxNode};
use crate::{CodeGraph, NodeId};

/// The deepest a path search descends before giving up.
pub const RECURSION_LIMIT: usize = 100;

/// A chain of node ids from one node to another.
pub type Path = Vec<NodeId>;

/// Lazily yields every CFG path backward from a node, one predecessor chain
/// at a time, terminating at roots and at cycles.
pub struct BackwardPaths<'a> {
    graph: &'a SyntaxGraph,
    stack: Vec<Path>,
}

impl Iterator for BackwardPaths<'_> {
    type Item = Path;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(path) = self.stack.pop() {
            let Some(&tail) = path.last() else {
                continue;
            };
            let parents: Vec<NodeId> = pred_cfg(self.graph, tail, None)
                .into_iter()
                .filter(|parent| !path.contains(parent))
                .collect();
            if parents.is_empty() {
                return Some(path);
            }
            for parent in parents.into_iter().rev() {
                let mut next = path.clone();
                next.push(parent);
                self.stack.push(next);
            }
        }
        None
    }
}

/// Every CFG path backward from `cfg_n_id`, lazily.
#[must_use]
pub fn iter_backward_paths(graph: &SyntaxGraph, cfg_n_id: NodeId) -> BackwardPaths<'_> {
    BackwardPaths {
        graph,
        stack: vec![vec![cfg_n_id]],
    }
}

/// CFG paths backward from `n_id`'s nearest CFG-connected node, up to `limit`
/// paths (unbounded when `None` or `0`).
#[must_use]
pub fn get_backward_paths(graph: &SyntaxGraph, n_id: NodeId, limit: Option<usize>) -> Vec<Path> {
    let cfg_id = lookup_first_cfg_parent(graph, n_id);
    let paths = iter_backward_paths(graph, cfg_id);
    match limit.filter(|&value| value != 0) {
        Some(value) => paths.take(value.saturating_sub(1)).collect(),
        None => paths.collect(),
    }
}

/// Finds the definitions of a symbol within one node of a given kind.
type Searcher = fn(&SyntaxGraph, NodeId, &str) -> Vec<NodeId>;

const COMPOUND_OPERATORS: [&str; 3] = ["+=", "*=", "/="];

fn search_assignment(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Vec<NodeId> {
    let Some(SyntaxNode::Assignment {
        variable_id,
        operator,
        ..
    }) = graph.nodes.get(&n_id)
    else {
        return Vec::new();
    };
    let assign_id = *variable_id;

    if graph.nodes.get(&assign_id).and_then(SyntaxNode::symbol) == Some(symbol) {
        let compound = operator
            .as_deref()
            .is_some_and(|value| COMPOUND_OPERATORS.contains(&value));
        if compound {
            return Vec::new();
        }
        return vec![n_id];
    }

    if graph.label_type(assign_id) == Some("ArrayInitializer") {
        let mut out: Vec<NodeId> = Vec::new();
        for c_id in adj_ast(graph, assign_id, Some(1), &["SymbolLookup"]) {
            if graph.nodes.get(&c_id).and_then(SyntaxNode::symbol) == Some(symbol) {
                out.push(n_id);
            }
        }
        return out;
    }

    Vec::new()
}

fn search_catch_clause(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Vec<NodeId> {
    let Some(SyntaxNode::CatchClause {
        catch_declaration: Some(c_id),
        ..
    }) = graph.nodes.get(&n_id)
    else {
        return Vec::new();
    };
    if graph.nodes.get(c_id).and_then(SyntaxNode::variable) == Some(symbol) {
        return vec![*c_id];
    }
    Vec::new()
}

fn search_class_body(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Vec<NodeId> {
    for c_id in adj_cfg(graph, n_id, None, &[]) {
        if graph.label_type(c_id) == Some("VariableDeclaration")
            && graph.nodes.get(&c_id).and_then(SyntaxNode::variable) == Some(symbol)
        {
            return vec![c_id];
        }
    }
    Vec::new()
}

fn search_declaration_block(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Vec<NodeId> {
    for c_id in adj_cfg(graph, n_id, None, &[]) {
        let child = graph.nodes.get(&c_id);
        if child.and_then(SyntaxNode::name) == Some(symbol)
            || child.and_then(SyntaxNode::variable) == Some(symbol)
        {
            return vec![c_id];
        }
    }
    Vec::new()
}

fn search_file_node(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Vec<NodeId> {
    for c_id in adj_cfg(graph, n_id, None, &[]) {
        let Some(node) = graph.nodes.get(&c_id) else {
            continue;
        };
        let mapped = match node {
            SyntaxNode::VariableDeclaration { .. } => node.variable(),
            SyntaxNode::MethodDeclaration { .. } => node.name(),
            SyntaxNode::Import { .. } | SyntaxNode::ModuleImport { .. } => node.expression(),
            _ => continue,
        };
        if mapped == Some(symbol) || node.alias() == Some(symbol) {
            return vec![c_id];
        }
    }
    Vec::new()
}

fn search_for_each(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Vec<NodeId> {
    let Some(SyntaxNode::ForEachStatement { variable_id, .. }) = graph.nodes.get(&n_id) else {
        return Vec::new();
    };
    if graph.nodes.get(variable_id).and_then(SyntaxNode::symbol) == Some(symbol) {
        return vec![n_id];
    }
    Vec::new()
}

fn search_for_statement(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Vec<NodeId> {
    let Some(SyntaxNode::ForStatement {
        initializer_id: Some(init_id),
        ..
    }) = graph.nodes.get(&n_id)
    else {
        return Vec::new();
    };
    let init_id = *init_id;

    let matches_directly = graph.label_type(init_id) == Some("SymbolLookup")
        && graph.nodes.get(&init_id).and_then(SyntaxNode::symbol) == Some(symbol);
    if matches_directly {
        return vec![n_id];
    }

    for c_id in adj_ast(graph, init_id, None, &["SymbolLookup"]) {
        if graph.nodes.get(&c_id).and_then(SyntaxNode::symbol) == Some(symbol) {
            return vec![n_id];
        }
    }
    Vec::new()
}

fn search_method_declaration(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Vec<NodeId> {
    let Some(SyntaxNode::MethodDeclaration {
        name,
        parameters_id,
        ..
    }) = graph.nodes.get(&n_id)
    else {
        return Vec::new();
    };

    if name.as_deref() == Some(symbol) {
        return vec![n_id];
    }

    let pl_id = parameters_id.unwrap_or(n_id);
    if graph.label_type(pl_id) == Some("Parameter") {
        if graph.nodes.get(&pl_id).and_then(SyntaxNode::variable) == Some(symbol) {
            return vec![pl_id];
        }
        return Vec::new();
    }

    for c_id in adj_ast(graph, pl_id, None, &["Parameter"]) {
        if graph.nodes.get(&c_id).and_then(SyntaxNode::variable) == Some(symbol) {
            return vec![c_id];
        }
    }
    Vec::new()
}

fn search_try_statement(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Vec<NodeId> {
    let Some(SyntaxNode::TryStatement {
        resources_id: Some(resources_id),
        ..
    }) = graph.nodes.get(&n_id)
    else {
        return Vec::new();
    };
    let mut out: Vec<NodeId> = Vec::new();
    for resource_id in adj_ast(graph, *resources_id, None, &[]) {
        if graph
            .nodes
            .get(&resource_id)
            .and_then(SyntaxNode::variable)
            .unwrap_or_default()
            == symbol
        {
            out.push(resource_id);
        }
    }
    out
}

fn search_using_statement(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Vec<NodeId> {
    let Some(SyntaxNode::UsingStatement {
        declaration_id: Some(var_id),
        ..
    }) = graph.nodes.get(&n_id)
    else {
        return Vec::new();
    };
    let var_id = *var_id;
    let mut out: Vec<NodeId> = Vec::new();

    if graph.nodes.get(&var_id).and_then(SyntaxNode::variable) == Some(symbol) {
        out.push(n_id);
    }

    if let Some(SyntaxNode::Assignment { variable_id, .. }) = graph.nodes.get(&var_id) {
        if graph.nodes.get(variable_id).and_then(SyntaxNode::symbol) == Some(symbol) {
            out.push(n_id);
        }
    }
    out
}

fn search_variable_declaration(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Vec<NodeId> {
    let variable = graph
        .nodes
        .get(&n_id)
        .and_then(SyntaxNode::variable)
        .unwrap_or_default();
    if variable.split(',').any(|part| part == symbol) {
        return vec![n_id];
    }
    Vec::new()
}

fn searcher_for(label: &str) -> Option<Searcher> {
    match label {
        "Assignment" => Some(search_assignment),
        "CatchClause" => Some(search_catch_clause),
        "ClassBody" => Some(search_class_body),
        "DeclarationBlock" => Some(search_declaration_block),
        "File" => Some(search_file_node),
        "ForEachStatement" => Some(search_for_each),
        "ForStatement" => Some(search_for_statement),
        "MethodDeclaration" => Some(search_method_declaration),
        "TryStatement" => Some(search_try_statement),
        "UsingStatement" => Some(search_using_statement),
        "VariableDeclaration" => Some(search_variable_declaration),
        _ => None,
    }
}

/// `symbol`'s definition node along `path`, if `path` reaches one.
#[must_use]
pub fn definition_search(graph: &SyntaxGraph, path: &Path, symbol: &str) -> Option<NodeId> {
    path.iter().find_map(|&n_id| {
        let searcher = graph.label_type(n_id).and_then(searcher_for)?;
        searcher(graph, n_id, symbol).into_iter().next()
    })
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum CondBranch {
    TrueId,
    FalseId,
}

fn char_at(text: &str, index: i64) -> Option<char> {
    if index >= 0 {
        usize::try_from(index)
            .ok()
            .and_then(|i| text.chars().nth(i))
    } else {
        index
            .checked_neg()
            .and_then(|positive| usize::try_from(positive).ok())
            .and_then(|i| i.checked_sub(1))
            .and_then(|i| text.chars().rev().nth(i))
    }
}

#[must_use]
pub fn search_value(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Option<NodeId> {
    adj_ast(graph, n_id, None, &[]).into_iter().find(|c_id| {
        matches!(
            graph.nodes.get(c_id),
            Some(SyntaxNode::SwitchSection { case_expression })
                if strip_quotes(case_expression) == symbol
        )
    })
}

#[must_use]
pub fn guess_char(graph: &SyntaxGraph, path: &Path, n_id: NodeId) -> Option<String> {
    let node = graph.nodes.get(&n_id)?;
    if let Some(val_id) = node.value_id() {
        return graph
            .nodes
            .get(&val_id)
            .and_then(SyntaxNode::value)
            .map(String::from);
    }

    let SyntaxNode::MethodInvocation {
        expression,
        object_id,
        arguments_id,
        ..
    } = node
    else {
        return None;
    };
    if expression != "charAt" {
        return None;
    }
    let obj_symbol = object_id
        .and_then(|obj_id| graph.nodes.get(&obj_id))
        .and_then(SyntaxNode::symbol)?;
    let val_id = definition_search(graph, path, obj_symbol)?;
    let args_id = (*arguments_id)?;
    let char_pos_id = adj_ast(graph, args_id, None, &[]).first().copied()?;
    let char_pos = graph
        .nodes
        .get(&char_pos_id)
        .and_then(SyntaxNode::value)?
        .parse::<i64>()
        .ok()
        .filter(|position| *position != 0)?;
    let guess_val_id = graph.nodes.get(&val_id).and_then(SyntaxNode::value_id)?;
    let guess_value = graph
        .nodes
        .get(&guess_val_id)
        .and_then(SyntaxNode::value)
        .filter(|value| !value.is_empty())?;
    char_at(strip_quotes(guess_value), char_pos).map(String::from)
}

#[must_use]
pub fn get_symbol_assignment(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Option<String> {
    for path in get_backward_paths(graph, n_id, Some(RECURSION_LIMIT)) {
        let value = definition_search(graph, &path, symbol)
            .and_then(|var_def_id| graph.nodes.get(&var_def_id))
            .and_then(SyntaxNode::value_id)
            .and_then(|val_id| guess_char(graph, &path, val_id))
            .filter(|value| !value.is_empty());
        if let Some(value) = value {
            return Some(String::from(strip_quotes(&value)));
        }
    }
    None
}

#[must_use]
pub fn get_deterministic_path_id(graph: &SyntaxGraph, n_id: NodeId) -> Option<NodeId> {
    let parent_id = pred_ast(graph, n_id, None).first().copied()?;
    let val_id = graph.nodes.get(&parent_id).and_then(SyntaxNode::value_id)?;
    let symbol = graph
        .nodes
        .get(&val_id)
        .and_then(SyntaxNode::symbol)
        .filter(|symbol| !symbol.is_empty())?;
    let var_definition =
        get_symbol_assignment(graph, parent_id, symbol).filter(|value| !value.is_empty())?;
    search_value(graph, n_id, &var_definition)
}

#[must_use]
pub fn get_return_literal(graph: &SyntaxGraph, n_id: NodeId, symbol: &str) -> Option<String> {
    let mut literal_values: BTreeSet<String> = BTreeSet::new();
    for path in get_backward_paths(graph, n_id, Some(RECURSION_LIMIT)) {
        let return_value = definition_search(graph, &path, symbol)
            .and_then(|var_def_id| graph.nodes.get(&var_def_id))
            .and_then(SyntaxNode::value_id)
            .and_then(|val_id| {
                graph
                    .nodes
                    .get(&val_id)
                    .filter(|node| matches!(node, SyntaxNode::Literal { .. }))
            })
            .and_then(SyntaxNode::value)
            .filter(|value| !value.is_empty())?;
        literal_values.insert(String::from(strip_quotes(return_value)));
    }
    literal_values.last().cloned()
}

#[must_use]
pub fn search_symbol_val_id(graph: &SyntaxGraph, n_id: NodeId) -> Option<NodeId> {
    let symbol = graph.nodes.get(&n_id).and_then(SyntaxNode::symbol)?;
    for path in get_backward_paths(graph, n_id, Some(RECURSION_LIMIT)) {
        if let Some(node) = definition_search(graph, &path, symbol)
            .and_then(|var_def_id| graph.nodes.get(&var_def_id))
        {
            if matches!(node, SyntaxNode::VariableDeclaration { .. }) {
                return node.value_id();
            }
        }
    }
    None
}

#[must_use]
pub fn get_condition_deterministic_result(
    graph: &mut SyntaxGraph,
    cond_id: NodeId,
) -> Option<CondBranch> {
    let symbol_ids = if graph.label_type(cond_id) == Some("SymbolLookup") {
        vec![cond_id]
    } else {
        match_ast_group_d(&*graph, cond_id, "SymbolLookup", Some(-1))
    };

    let mut resolved: BTreeMap<NodeId, Folded> = BTreeMap::new();
    for var_id in symbol_ids {
        let (var_value, var_type) = search_symbol_val_id(graph, var_id).and_then(|val_id| {
            match graph.nodes.get(&val_id) {
                Some(SyntaxNode::Literal { value, value_type }) if !value.is_empty() => {
                    Some((value.clone(), value_type.clone()))
                }
                _ => None,
            }
        })?;
        if let Some(folded) = fold_leaf(&var_value, &var_type) {
            resolved.insert(var_id, folded);
        }
        let Some(SyntaxNode::SymbolLookup { value, .. }) = graph.nodes.get_mut(&var_id) else {
            return None;
        };
        *value = Some(var_value);
    }

    match fold(graph, &resolved, cond_id)? {
        Folded::Truth(true) => Some(CondBranch::TrueId),
        Folded::Truth(false) => Some(CondBranch::FalseId),
        Folded::Int(_) | Folded::Float(_) | Folded::Text(_) => None,
    }
}

fn get_element_in_hashmap(
    graph: &SyntaxGraph,
    path: &Path,
    var_name: &str,
    access_key: &str,
) -> Option<NodeId> {
    for &n_id in path {
        let Some(SyntaxNode::MethodInvocation {
            expression,
            object_id: Some(object_id),
            arguments_id: Some(arguments_id),
            ..
        }) = graph.nodes.get(&n_id)
        else {
            continue;
        };
        if expression != "put"
            || graph.nodes.get(object_id).and_then(SyntaxNode::symbol) != Some(var_name)
        {
            continue;
        }
        let arg_ids = adj_ast(graph, *arguments_id, None, &[]);
        if arg_ids.len() < 2 {
            continue;
        }
        let key_matches = arg_ids
            .first()
            .and_then(|first| graph.nodes.get(first))
            .and_then(SyntaxNode::value)
            == Some(access_key);
        if key_matches {
            return arg_ids.get(1).copied();
        }
    }
    None
}

fn element_at(d_nodes: &[NodeId], access_val: i64) -> Option<NodeId> {
    let magnitude = usize::try_from(access_val.unsigned_abs()).ok()?;
    if d_nodes.is_empty() || d_nodes.len() < magnitude {
        return None;
    }
    if access_val >= 0 {
        d_nodes.get(magnitude).copied()
    } else {
        d_nodes.get(d_nodes.len().checked_sub(magnitude)?).copied()
    }
}

fn remove_replayed_element(
    graph: &SyntaxGraph,
    d_nodes: &mut Vec<NodeId>,
    index_value: &str,
) -> Option<()> {
    let Ok(index) = index_value.parse::<i64>() else {
        let matching = d_nodes.iter().position(|element| {
            graph.nodes.get(element).and_then(SyntaxNode::value) == Some(index_value)
        });
        if let Some(position) = matching {
            d_nodes.remove(position);
        }
        return Some(());
    };
    let magnitude = usize::try_from(index.unsigned_abs()).ok()?;
    let position = if index >= 0 {
        magnitude
    } else {
        d_nodes.len().checked_sub(magnitude)?
    };
    if position >= d_nodes.len() {
        return None;
    }
    d_nodes.remove(position);
    Some(())
}

fn get_element_in_array(
    graph: &SyntaxGraph,
    path: &Path,
    var_name: &str,
    access_val: i64,
) -> Option<NodeId> {
    let mut d_nodes: Vec<NodeId> = Vec::new();
    for &n_id in path.iter().rev() {
        let Some(SyntaxNode::MethodInvocation {
            expression,
            object_id: Some(object_id),
            arguments_id: Some(arguments_id),
            ..
        }) = graph.nodes.get(&n_id)
        else {
            continue;
        };
        if graph.nodes.get(object_id).and_then(SyntaxNode::symbol) != Some(var_name) {
            continue;
        }
        let Some(arg_id) = adj_ast(graph, *arguments_id, None, &[]).first().copied() else {
            continue;
        };
        match expression.as_str() {
            "add" | "push" => d_nodes.push(arg_id),
            "remove" => {
                let index_value = graph
                    .nodes
                    .get(&arg_id)
                    .and_then(SyntaxNode::value)
                    .filter(|value| !value.is_empty())?;
                remove_replayed_element(graph, &mut d_nodes, index_value)?;
            }
            _ => {}
        }
    }
    element_at(&d_nodes, access_val)
}

fn search_data_element(graph: &SyntaxGraph, method_id: NodeId) -> Option<NodeId> {
    let Some(SyntaxNode::MethodInvocation {
        object_id: Some(object_id),
        arguments_id: Some(arguments_id),
        ..
    }) = graph.nodes.get(&method_id)
    else {
        return None;
    };
    let var_name = graph
        .nodes
        .get(object_id)
        .and_then(SyntaxNode::symbol)
        .filter(|symbol| !symbol.is_empty())?;
    let args_ids = adj_ast(graph, *arguments_id, None, &[]);
    let [access_id] = args_ids.as_slice() else {
        return None;
    };
    let Some(SyntaxNode::Literal { value, value_type }) = graph.nodes.get(access_id) else {
        return None;
    };

    let access_val = match value_type.as_str() {
        "number" => Some(value.parse::<i64>().ok()?),
        "string" => None,
        _ => return None,
    };
    let path = get_backward_paths(graph, method_id, Some(RECURSION_LIMIT))
        .into_iter()
        .next()?;
    access_val.map_or_else(
        || get_element_in_hashmap(graph, &path, var_name, value),
        |index| get_element_in_array(graph, &path, var_name, index),
    )
}

fn get_node_access_method(graph: &SyntaxGraph, n_id: NodeId) -> Option<NodeId> {
    let method_id = match graph.nodes.get(&n_id) {
        Some(SyntaxNode::VariableDeclaration {
            value_id: Some(val_id),
            ..
        }) => *val_id,
        _ => n_id,
    };
    matches!(
        graph.nodes.get(&method_id),
        Some(SyntaxNode::MethodInvocation { expression, .. }) if expression == "get"
    )
    .then_some(method_id)
}

fn rewire_assignment_value(
    graph: &mut SyntaxGraph,
    n_id: NodeId,
    old_value_id: NodeId,
    c_id: NodeId,
    detached_parent: NodeId,
) {
    graph.remove_edge(n_id, old_value_id);
    graph.remove_edge(detached_parent, c_id);
    if let Some(SyntaxNode::Assignment { value_id, .. }) = graph.nodes.get_mut(&n_id) {
        *value_id = Some(c_id);
    }
    graph.add_ast_edge(n_id, c_id);
}

pub fn adjust_assignment_ast_edges(graph: &mut SyntaxGraph, n_id: NodeId) {
    let Some(SyntaxNode::Assignment {
        value_id: Some(value_id),
        ..
    }) = graph.nodes.get(&n_id)
    else {
        return;
    };
    let value_id = *value_id;

    if let Some(SyntaxNode::TernaryOperation {
        condition_id,
        true_id,
        false_id,
    }) = graph.nodes.get(&value_id)
    {
        let (condition_id, true_id, false_id) = (*condition_id, *true_id, *false_id);
        if let Some(branch) = get_condition_deterministic_result(graph, condition_id) {
            let c_id = match branch {
                CondBranch::TrueId => true_id,
                CondBranch::FalseId => false_id,
            };
            rewire_assignment_value(graph, n_id, value_id, c_id, value_id);
        }
    }

    if let Some(c_id) = get_node_access_method(graph, value_id)
        .and_then(|method_id| search_data_element(graph, method_id))
    {
        let Some(parent_id) = pred_ast(graph, c_id, None).first().copied() else {
            return;
        };
        rewire_assignment_value(graph, n_id, value_id, c_id, parent_id);
    }
}

pub fn adjust_return_value(graph: &mut SyntaxGraph, n_id: NodeId) {
    let resolved = graph
        .nodes
        .get(&n_id)
        .and_then(SyntaxNode::value_id)
        .and_then(|val_id| {
            let symbol = graph
                .nodes
                .get(&val_id)
                .and_then(SyntaxNode::symbol)
                .filter(|symbol| !symbol.is_empty())?;
            let ret_val =
                get_return_literal(graph, val_id, symbol).filter(|value| !value.is_empty())?;
            Some((val_id, ret_val))
        });
    if let Some((val_id, ret_val)) = resolved {
        graph.add_node(
            val_id,
            SyntaxNode::Literal {
                value: ret_val,
                value_type: String::new(),
            },
        );
    }
}

#[cfg(test)]
mod tests {
    use super::{
        adjust_assignment_ast_edges, adjust_return_value, char_at, definition_search, element_at,
        get_backward_paths, get_condition_deterministic_result, get_deterministic_path_id,
        get_element_in_array, get_element_in_hashmap, get_node_access_method, get_return_literal,
        get_symbol_assignment, guess_char, iter_backward_paths, remove_replayed_element,
        search_value, CondBranch,
    };
    use crate::syntax::{SyntaxGraph, SyntaxNode};
    use crate::CodeGraph;
    use crate::NodeId;
    use alloc::borrow::ToOwned;
    use alloc::string::String;
    use alloc::vec;
    use alloc::vec::Vec;

    fn literal(value: &str, value_type: &str) -> SyntaxNode {
        SyntaxNode::Literal {
            value: value.to_owned(),
            value_type: value_type.to_owned(),
        }
    }

    fn symbol_lookup(symbol: &str) -> SyntaxNode {
        SyntaxNode::SymbolLookup {
            symbol: symbol.to_owned(),
            symbol_scope: None,
            value: None,
        }
    }

    fn variable_declaration(name: &str, value_id: NodeId) -> SyntaxNode {
        SyntaxNode::VariableDeclaration {
            variable: name.to_owned(),
            variable_type: None,
            value_id: Some(value_id),
            variable_id: None,
            access_modifier: None,
        }
    }

    fn char_at_graph(invoked_method: &str, position: &str) -> SyntaxGraph {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), variable_declaration("s", NodeId(2)));
        graph.add_node(NodeId(2), literal("\"hello\"", "string"));
        graph.add_node(
            NodeId(3),
            SyntaxNode::MethodInvocation {
                expression: String::from(invoked_method),
                object: None,
                symbol_scope: None,
                expression_id: None,
                arguments_id: Some(NodeId(5)),
                object_id: Some(NodeId(4)),
                block_id: None,
                receiver_type_fqn: None,
            },
        );
        graph.add_node(NodeId(4), symbol_lookup("s"));
        graph.add_node(NodeId(5), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(6), literal(position, "number"));
        graph.add_ast_edge(NodeId(5), NodeId(6));
        graph
    }

    #[test]
    fn guess_char_resolves_a_char_at_call_over_the_definition() {
        // Index 1 of "hello" is the only position whose neighbours differ, so an
        // off-by-one in char_at cannot hide behind the repeated `l`.
        let graph = char_at_graph("charAt", "1");
        let path = vec![NodeId(1)];

        assert_eq!(
            guess_char(&graph, &path, NodeId(3)),
            Some(String::from("e"))
        );
    }

    #[test]
    fn guess_char_mirrors_the_python_zero_index_falsiness() {
        let graph = char_at_graph("charAt", "0");
        let path = vec![NodeId(1)];

        assert_eq!(guess_char(&graph, &path, NodeId(3)), None);
    }

    #[test]
    fn guess_char_ignores_an_invocation_that_is_not_char_at() {
        let graph = char_at_graph("substring", "1");
        let path = vec![NodeId(1)];

        assert_eq!(guess_char(&graph, &path, NodeId(3)), None);
    }

    #[test]
    fn get_symbol_assignment_strips_the_quotes_of_the_resolved_value() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), variable_declaration("c", NodeId(2)));
        graph.add_node(NodeId(2), variable_declaration("inner", NodeId(3)));
        graph.add_node(NodeId(3), literal("\"quoted\"", "string"));
        graph.add_node(NodeId(4), SyntaxNode::ExecutionBlock);
        graph.add_cfg_edge(NodeId(1), NodeId(4));

        assert_eq!(
            get_symbol_assignment(&graph, NodeId(4), "c"),
            Some(String::from("quoted"))
        );
    }

    #[test]
    fn get_return_literal_takes_the_greatest_value_across_paths() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), variable_declaration("x", NodeId(2)));
        graph.add_node(NodeId(2), literal("\"a\"", "string"));
        graph.add_node(NodeId(3), variable_declaration("x", NodeId(4)));
        graph.add_node(NodeId(4), literal("\"b\"", "string"));
        graph.add_node(NodeId(5), SyntaxNode::ExecutionBlock);
        graph.add_cfg_edge(NodeId(1), NodeId(5));
        graph.add_cfg_edge(NodeId(3), NodeId(5));

        assert_eq!(
            get_return_literal(&graph, NodeId(5), "x"),
            Some(String::from("b"))
        );
    }

    #[test]
    fn get_return_literal_ignores_a_definition_that_is_not_a_literal() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), variable_declaration("x", NodeId(2)));
        graph.add_node(
            NodeId(2),
            SyntaxNode::ReservedWord {
                value: "null".to_owned(),
            },
        );
        graph.add_node(NodeId(3), SyntaxNode::ExecutionBlock);
        graph.add_cfg_edge(NodeId(1), NodeId(3));

        assert_eq!(get_return_literal(&graph, NodeId(3), "x"), None);
    }

    fn binary_operation(operator: &str, left_id: NodeId, right_id: NodeId) -> SyntaxNode {
        SyntaxNode::BinaryOperation {
            operator: operator.to_owned(),
            left_id: Some(left_id),
            right_id: Some(right_id),
        }
    }

    fn method_invocation(
        expression: &str,
        object_id: NodeId,
        arguments_id: Option<NodeId>,
    ) -> SyntaxNode {
        SyntaxNode::MethodInvocation {
            expression: expression.to_owned(),
            object: None,
            symbol_scope: None,
            expression_id: None,
            arguments_id,
            object_id: Some(object_id),
            block_id: None,
            receiver_type_fqn: None,
        }
    }

    #[test]
    fn resolves_a_symbol_to_its_literal_definition_before_folding() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), variable_declaration("x", NodeId(2)));
        graph.add_node(NodeId(2), literal("1", "number"));
        graph.add_node(NodeId(3), binary_operation("==", NodeId(4), NodeId(5)));
        graph.add_node(NodeId(4), symbol_lookup("x"));
        graph.add_node(NodeId(5), literal("1", "number"));
        graph.add_ast_edge(NodeId(3), NodeId(4));
        graph.add_ast_edge(NodeId(3), NodeId(5));
        graph.add_cfg_edge(NodeId(1), NodeId(3));

        assert_eq!(
            get_condition_deterministic_result(&mut graph, NodeId(3)),
            Some(CondBranch::TrueId)
        );
        assert_eq!(
            graph.nodes.get(&NodeId(4)).and_then(SyntaxNode::value),
            Some("1")
        );
    }

    #[test]
    fn adjust_assignment_rewires_a_deterministic_ternary() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(
            NodeId(1),
            SyntaxNode::Assignment {
                variable_id: NodeId(6),
                value_id: Some(NodeId(2)),
                operator: None,
            },
        );
        graph.add_node(
            NodeId(2),
            SyntaxNode::TernaryOperation {
                condition_id: NodeId(3),
                true_id: NodeId(4),
                false_id: NodeId(5),
            },
        );
        graph.add_node(NodeId(3), literal("true", "boolean"));
        graph.add_node(NodeId(4), literal("\"a\"", "string"));
        graph.add_node(NodeId(5), literal("\"b\"", "string"));
        graph.add_node(NodeId(6), symbol_lookup("x"));
        graph.add_ast_edge(NodeId(1), NodeId(2));
        graph.add_ast_edge(NodeId(2), NodeId(3));
        graph.add_ast_edge(NodeId(2), NodeId(4));
        graph.add_ast_edge(NodeId(2), NodeId(5));

        adjust_assignment_ast_edges(&mut graph, NodeId(1));

        assert_eq!(graph.children(NodeId(1)), [NodeId(4)]);
        assert_eq!(graph.children(NodeId(2)), [NodeId(3), NodeId(5)]);
        assert_eq!(
            graph.nodes.get(&NodeId(1)).and_then(SyntaxNode::value_id),
            Some(NodeId(4))
        );
    }

    fn collection_access_graph(access: (&str, &str), stored_key: &str) -> SyntaxGraph {
        let mut graph = SyntaxGraph::new();
        graph.add_node(
            NodeId(1),
            SyntaxNode::Assignment {
                variable_id: NodeId(12),
                value_id: Some(NodeId(2)),
                operator: None,
            },
        );
        graph.add_node(
            NodeId(2),
            SyntaxNode::MethodInvocation {
                expression: String::from("get"),
                object: None,
                symbol_scope: None,
                expression_id: None,
                arguments_id: Some(NodeId(4)),
                object_id: Some(NodeId(3)),
                block_id: None,
                receiver_type_fqn: None,
            },
        );
        graph.add_node(NodeId(3), symbol_lookup("items"));
        graph.add_node(NodeId(4), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(5), literal(access.0, access.1));
        graph.add_node(
            NodeId(6),
            SyntaxNode::MethodInvocation {
                expression: String::from(if access.1 == "number" { "add" } else { "put" }),
                object: None,
                symbol_scope: None,
                expression_id: None,
                arguments_id: Some(NodeId(8)),
                object_id: Some(NodeId(7)),
                block_id: None,
                receiver_type_fqn: None,
            },
        );
        graph.add_node(NodeId(7), symbol_lookup("items"));
        graph.add_node(NodeId(8), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(9), literal(stored_key, "string"));
        graph.add_node(NodeId(10), symbol_lookup("stored"));
        graph.add_node(NodeId(12), symbol_lookup("x"));
        graph.add_ast_edge(NodeId(1), NodeId(2));
        graph.add_ast_edge(NodeId(4), NodeId(5));
        graph.add_ast_edge(NodeId(8), NodeId(9));
        graph.add_ast_edge(NodeId(8), NodeId(10));
        graph.add_cfg_edge(NodeId(6), NodeId(1));
        graph
    }

    #[test]
    fn adjust_assignment_rewires_a_replayed_list_access() {
        let mut graph = collection_access_graph(("0", "number"), "\"first\"");

        adjust_assignment_ast_edges(&mut graph, NodeId(1));

        assert_eq!(graph.children(NodeId(1)), [NodeId(9)]);
        assert_eq!(graph.children(NodeId(8)), [NodeId(10)]);
        assert_eq!(
            graph.nodes.get(&NodeId(1)).and_then(SyntaxNode::value_id),
            Some(NodeId(9))
        );
    }

    #[test]
    fn adjust_assignment_rewires_a_replayed_map_access() {
        let mut graph = collection_access_graph(("\"k\"", "string"), "\"k\"");

        adjust_assignment_ast_edges(&mut graph, NodeId(1));

        assert_eq!(graph.children(NodeId(1)), [NodeId(10)]);
        assert_eq!(graph.children(NodeId(8)), [NodeId(9)]);
        assert_eq!(
            graph.nodes.get(&NodeId(1)).and_then(SyntaxNode::value_id),
            Some(NodeId(10))
        );
    }

    #[test]
    fn an_unmodelable_remove_call_aborts_the_replay() {
        let mut graph = collection_access_graph(("0", "number"), "\"first\"");
        graph.add_node(
            NodeId(13),
            SyntaxNode::MethodInvocation {
                expression: String::from("remove"),
                object: None,
                symbol_scope: None,
                expression_id: None,
                arguments_id: Some(NodeId(15)),
                object_id: Some(NodeId(14)),
                block_id: None,
                receiver_type_fqn: None,
            },
        );
        graph.add_node(NodeId(14), symbol_lookup("items"));
        graph.add_node(NodeId(15), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(16), symbol_lookup("victim"));
        graph.add_ast_edge(NodeId(15), NodeId(16));
        graph.remove_edge(NodeId(6), NodeId(1));
        graph.add_cfg_edge(NodeId(6), NodeId(13));
        graph.add_cfg_edge(NodeId(13), NodeId(1));

        adjust_assignment_ast_edges(&mut graph, NodeId(1));

        assert_eq!(graph.children(NodeId(1)), [NodeId(2)]);
        assert_eq!(
            graph.nodes.get(&NodeId(1)).and_then(SyntaxNode::value_id),
            Some(NodeId(2))
        );
    }

    #[test]
    fn a_two_argument_get_is_not_a_collection_read() {
        let mut graph = collection_access_graph(("0", "number"), "\"first\"");
        graph.add_node(NodeId(11), literal("\"extra\"", "string"));
        graph.add_ast_edge(NodeId(4), NodeId(11));

        adjust_assignment_ast_edges(&mut graph, NodeId(1));

        assert_eq!(graph.children(NodeId(1)), [NodeId(2)]);
        assert_eq!(
            graph.nodes.get(&NodeId(1)).and_then(SyntaxNode::value_id),
            Some(NodeId(2))
        );
    }

    #[test]
    fn adjust_return_value_retypes_the_symbol_into_a_literal() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(
            NodeId(1),
            SyntaxNode::Return {
                value_id: Some(NodeId(2)),
            },
        );
        graph.add_node(NodeId(2), symbol_lookup("x"));
        graph.add_node(NodeId(3), variable_declaration("x", NodeId(4)));
        graph.add_node(NodeId(4), literal("\"ok\"", "string"));
        graph.add_ast_edge(NodeId(1), NodeId(2));
        graph.add_cfg_edge(NodeId(3), NodeId(1));

        adjust_return_value(&mut graph, NodeId(1));

        assert_eq!(
            graph.nodes.get(&NodeId(2)),
            Some(&SyntaxNode::Literal {
                value: "ok".to_owned(),
                value_type: String::new(),
            })
        );
    }

    #[test]
    fn char_at_reads_from_the_end_on_a_negative_index() {
        assert_eq!(char_at("hello", -1), Some('o'));
        assert_eq!(char_at("hello", -100), None);
    }

    #[test]
    fn search_value_finds_the_matching_switch_section_by_case_expression() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), SyntaxNode::ExecutionBlock);
        graph.add_node(
            NodeId(2),
            SyntaxNode::SwitchSection {
                case_expression: "\"case1\"".to_owned(),
            },
        );
        graph.add_node(
            NodeId(3),
            SyntaxNode::SwitchSection {
                case_expression: "\"case2\"".to_owned(),
            },
        );
        graph.add_ast_edge(NodeId(1), NodeId(2));
        graph.add_ast_edge(NodeId(1), NodeId(3));

        assert_eq!(search_value(&graph, NodeId(1), "case2"), Some(NodeId(3)));
        assert_eq!(search_value(&graph, NodeId(1), "missing"), None);
    }

    #[test]
    fn guess_char_follows_a_value_id_indirection_before_dispatching_on_char_at() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), literal("\"z\"", "string"));
        graph.add_node(NodeId(2), variable_declaration("alias", NodeId(1)));
        let path: Vec<NodeId> = vec![];

        assert_eq!(
            guess_char(&graph, &path, NodeId(2)),
            Some(String::from("\"z\""))
        );
    }

    fn switch_over_char_at_result() -> SyntaxGraph {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), variable_declaration("s", NodeId(2)));
        graph.add_node(NodeId(2), literal("\"hello\"", "string"));
        graph.add_node(
            NodeId(3),
            SyntaxNode::MethodInvocation {
                expression: String::from("charAt"),
                object: None,
                symbol_scope: None,
                expression_id: None,
                arguments_id: Some(NodeId(5)),
                object_id: Some(NodeId(4)),
                block_id: None,
                receiver_type_fqn: None,
            },
        );
        graph.add_node(NodeId(4), symbol_lookup("s"));
        graph.add_node(NodeId(5), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(6), literal("1", "number"));
        graph.add_ast_edge(NodeId(5), NodeId(6));
        graph.add_node(NodeId(7), variable_declaration("c", NodeId(3)));
        graph.add_node(
            NodeId(8),
            SyntaxNode::SwitchStatement {
                block_id: NodeId(10),
                value_id: NodeId(9),
            },
        );
        graph.add_node(NodeId(9), symbol_lookup("c"));
        graph.add_node(NodeId(10), SyntaxNode::ExecutionBlock);
        graph.add_node(
            NodeId(11),
            SyntaxNode::SwitchSection {
                case_expression: "\"e\"".to_owned(),
            },
        );
        graph.add_node(
            NodeId(12),
            SyntaxNode::SwitchSection {
                case_expression: "\"other\"".to_owned(),
            },
        );
        graph.add_ast_edge(NodeId(8), NodeId(10));
        graph.add_ast_edge(NodeId(10), NodeId(11));
        graph.add_ast_edge(NodeId(10), NodeId(12));
        graph.add_cfg_edge(NodeId(1), NodeId(7));
        graph.add_cfg_edge(NodeId(7), NodeId(8));
        graph
    }

    #[test]
    fn get_symbol_assignment_resolves_a_char_at_definition_to_its_literal() {
        let graph = switch_over_char_at_result();

        assert_eq!(
            get_symbol_assignment(&graph, NodeId(8), "c"),
            Some(String::from("e"))
        );
    }

    #[test]
    fn get_deterministic_path_id_resolves_a_switch_through_a_char_at_definition() {
        let graph = switch_over_char_at_result();

        assert_eq!(
            get_deterministic_path_id(&graph, NodeId(10)),
            Some(NodeId(11))
        );
    }

    #[test]
    fn resolves_a_false_condition_to_the_false_branch() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), variable_declaration("x", NodeId(2)));
        graph.add_node(NodeId(2), literal("2", "number"));
        graph.add_node(NodeId(3), binary_operation("==", NodeId(4), NodeId(5)));
        graph.add_node(NodeId(4), symbol_lookup("x"));
        graph.add_node(NodeId(5), literal("1", "number"));
        graph.add_ast_edge(NodeId(3), NodeId(4));
        graph.add_ast_edge(NodeId(3), NodeId(5));
        graph.add_cfg_edge(NodeId(1), NodeId(3));

        assert_eq!(
            get_condition_deterministic_result(&mut graph, NodeId(3)),
            Some(CondBranch::FalseId)
        );
    }

    #[test]
    fn a_non_boolean_fold_result_is_not_a_deterministic_branch() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), binary_operation("+", NodeId(2), NodeId(3)));
        graph.add_node(NodeId(2), literal("2", "number"));
        graph.add_node(NodeId(3), literal("3", "number"));

        assert_eq!(
            get_condition_deterministic_result(&mut graph, NodeId(1)),
            None
        );
    }

    /// Only a declaration is treated as the value of a symbol.
    ///
    /// A reassignment carries a `value_id` too, so without the
    /// `VariableDeclaration` filter the condition below would fold to true.
    #[test]
    fn a_condition_over_a_symbol_defined_by_a_reassignment_is_not_deterministic() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(
            NodeId(1),
            SyntaxNode::Assignment {
                variable_id: NodeId(2),
                value_id: Some(NodeId(3)),
                operator: None,
            },
        );
        graph.add_node(NodeId(2), symbol_lookup("x"));
        graph.add_node(NodeId(3), literal("1", "number"));
        graph.add_node(NodeId(4), binary_operation("==", NodeId(5), NodeId(6)));
        graph.add_node(NodeId(5), symbol_lookup("x"));
        graph.add_node(NodeId(6), literal("1", "number"));
        graph.add_ast_edge(NodeId(4), NodeId(5));
        graph.add_ast_edge(NodeId(4), NodeId(6));
        graph.add_cfg_edge(NodeId(1), NodeId(4));

        assert_eq!(
            get_condition_deterministic_result(&mut graph, NodeId(4)),
            None
        );
    }

    #[test]
    fn an_unresolvable_symbol_definition_aborts_folding() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), variable_declaration("x", NodeId(2)));
        graph.add_node(NodeId(2), symbol_lookup("y"));
        graph.add_node(NodeId(3), binary_operation("==", NodeId(4), NodeId(5)));
        graph.add_node(NodeId(4), symbol_lookup("x"));
        graph.add_node(NodeId(5), literal("1", "number"));
        graph.add_ast_edge(NodeId(3), NodeId(4));
        graph.add_ast_edge(NodeId(3), NodeId(5));
        graph.add_cfg_edge(NodeId(1), NodeId(3));

        assert_eq!(
            get_condition_deterministic_result(&mut graph, NodeId(3)),
            None
        );
    }

    /// A `put(key, value)` on the path resolves a later read of that key.
    ///
    /// The negative rows matter because the function returns None for almost
    /// any input; without the positive row, gutting it would go unnoticed.
    #[test]
    fn get_element_in_hashmap_resolves_the_value_stored_under_the_requested_key() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(
            NodeId(1),
            method_invocation("put", NodeId(2), Some(NodeId(3))),
        );
        graph.add_node(NodeId(2), symbol_lookup("items"));
        graph.add_node(NodeId(3), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(4), literal("\"k\"", "string"));
        graph.add_node(NodeId(5), literal("\"stored\"", "string"));
        graph.add_ast_edge(NodeId(3), NodeId(4));
        graph.add_ast_edge(NodeId(3), NodeId(5));

        // A read of the same key on the same map must not shadow the put: only
        // the `put` guard separates the two, since both carry two arguments.
        graph.add_node(
            NodeId(6),
            method_invocation("get", NodeId(7), Some(NodeId(8))),
        );
        graph.add_node(NodeId(7), symbol_lookup("items"));
        graph.add_node(NodeId(8), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(9), literal("\"k\"", "string"));
        graph.add_node(NodeId(10), literal("\"shadow\"", "string"));
        graph.add_ast_edge(NodeId(8), NodeId(9));
        graph.add_ast_edge(NodeId(8), NodeId(10));

        let path = vec![NodeId(6), NodeId(1)];

        assert_eq!(
            get_element_in_hashmap(&graph, &path, "items", "\"k\""),
            Some(NodeId(5))
        );
        assert_eq!(
            get_element_in_hashmap(&graph, &path, "items", "\"missing\""),
            None,
            "a key that was never put must not resolve"
        );
        assert_eq!(
            get_element_in_hashmap(&graph, &path, "other_map", "\"k\""),
            None,
            "a put on a different map must not resolve"
        );
    }

    #[test]
    fn element_at_counts_from_the_end_for_negative_offsets() {
        let nodes = vec![NodeId(1), NodeId(2), NodeId(3)];

        assert_eq!(element_at(&nodes, -1), Some(NodeId(3)), "-1 is the last");
        assert_eq!(element_at(&nodes, -3), Some(NodeId(1)), "-3 is the first");
        assert_eq!(element_at(&nodes, 1), Some(NodeId(2)), "1 indexes forward");
        assert_eq!(element_at(&nodes, 5), None, "past the end resolves to None");
        assert_eq!(element_at(&[], 0), None, "an empty list has no elements");
    }

    #[test]
    fn remove_replayed_element_drops_the_entry_named_by_index_or_by_value() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), literal("\"a\"", "string"));
        graph.add_node(NodeId(2), literal("\"b\"", "string"));
        graph.add_node(NodeId(3), literal("\"c\"", "string"));

        let mut by_positive_index = vec![NodeId(1), NodeId(2), NodeId(3)];
        assert_eq!(
            remove_replayed_element(&graph, &mut by_positive_index, "1"),
            Some(())
        );
        assert_eq!(by_positive_index, vec![NodeId(1), NodeId(3)]);

        let mut by_negative_index = vec![NodeId(1), NodeId(2), NodeId(3)];
        assert_eq!(
            remove_replayed_element(&graph, &mut by_negative_index, "-1"),
            Some(())
        );
        assert_eq!(by_negative_index, vec![NodeId(1), NodeId(2)]);

        let mut out_of_range = vec![NodeId(1)];
        assert_eq!(
            remove_replayed_element(&graph, &mut out_of_range, "5"),
            None
        );

        let mut negative_out_of_range = vec![NodeId(1)];
        assert_eq!(
            remove_replayed_element(&graph, &mut negative_out_of_range, "-5"),
            None
        );

        let mut by_value_match = vec![NodeId(1), NodeId(2)];
        assert_eq!(
            remove_replayed_element(&graph, &mut by_value_match, "\"b\""),
            Some(())
        );
        assert_eq!(by_value_match, vec![NodeId(1)]);

        let mut by_value_no_match = vec![NodeId(1)];
        assert_eq!(
            remove_replayed_element(&graph, &mut by_value_no_match, "\"missing\""),
            Some(())
        );
        assert_eq!(by_value_no_match, vec![NodeId(1)]);

        // One past the end is the boundary the bounds check exists for: Vec
        // panics on remove(len), so this must be rejected rather than replayed.
        let mut one_past_the_end = vec![NodeId(1)];
        assert_eq!(
            remove_replayed_element(&graph, &mut one_past_the_end, "1"),
            None
        );
        assert_eq!(one_past_the_end, vec![NodeId(1)]);
    }

    #[test]
    fn get_element_in_array_resolves_the_last_push_that_reaches_the_index() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(
            NodeId(1),
            method_invocation("add", NodeId(2), Some(NodeId(3))),
        );
        graph.add_node(NodeId(2), symbol_lookup("other"));
        graph.add_node(NodeId(3), SyntaxNode::ArgumentList);
        graph.add_node(
            NodeId(4),
            method_invocation("add", NodeId(5), Some(NodeId(6))),
        );
        graph.add_node(NodeId(5), symbol_lookup("items"));
        graph.add_node(NodeId(6), SyntaxNode::ArgumentList);
        graph.add_node(
            NodeId(7),
            method_invocation("size", NodeId(8), Some(NodeId(9))),
        );
        graph.add_node(NodeId(8), symbol_lookup("items"));
        graph.add_node(NodeId(9), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(10), literal("0", "number"));
        graph.add_ast_edge(NodeId(9), NodeId(10));
        graph.add_node(
            NodeId(11),
            method_invocation("push", NodeId(12), Some(NodeId(13))),
        );
        graph.add_node(NodeId(12), symbol_lookup("items"));
        graph.add_node(NodeId(13), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(14), literal("\"only\"", "string"));
        graph.add_ast_edge(NodeId(13), NodeId(14));
        graph.add_node(NodeId(15), literal("\"foreign\"", "string"));
        graph.add_ast_edge(NodeId(3), NodeId(15));

        let path = vec![NodeId(1), NodeId(4), NodeId(7), NodeId(11)];

        assert_eq!(
            get_element_in_array(&graph, &path, "items", 0),
            Some(NodeId(14))
        );
        assert_eq!(
            get_element_in_array(&graph, &path, "items", 1),
            None,
            "an append on another collection must not extend this one"
        );
    }

    #[test]
    fn get_element_in_array_aborts_when_a_replayed_remove_falls_outside_the_list() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(
            NodeId(1),
            method_invocation("add", NodeId(2), Some(NodeId(3))),
        );
        graph.add_node(NodeId(2), symbol_lookup("items"));
        graph.add_node(NodeId(3), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(4), literal("\"first\"", "string"));
        graph.add_ast_edge(NodeId(3), NodeId(4));
        graph.add_node(
            NodeId(5),
            method_invocation("remove", NodeId(6), Some(NodeId(7))),
        );
        graph.add_node(NodeId(6), symbol_lookup("items"));
        graph.add_node(NodeId(7), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(8), literal("5", "number"));
        graph.add_ast_edge(NodeId(7), NodeId(8));

        let path = vec![NodeId(5), NodeId(1)];

        assert_eq!(get_element_in_array(&graph, &path, "items", 0), None);
    }

    #[test]
    fn get_element_in_array_replays_a_valid_remove_call() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(
            NodeId(1),
            method_invocation("add", NodeId(2), Some(NodeId(3))),
        );
        graph.add_node(NodeId(2), symbol_lookup("items"));
        graph.add_node(NodeId(3), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(4), literal("\"first\"", "string"));
        graph.add_ast_edge(NodeId(3), NodeId(4));
        graph.add_node(
            NodeId(5),
            method_invocation("add", NodeId(6), Some(NodeId(7))),
        );
        graph.add_node(NodeId(6), symbol_lookup("items"));
        graph.add_node(NodeId(7), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(8), literal("\"second\"", "string"));
        graph.add_ast_edge(NodeId(7), NodeId(8));
        graph.add_node(
            NodeId(9),
            method_invocation("remove", NodeId(10), Some(NodeId(11))),
        );
        graph.add_node(NodeId(10), symbol_lookup("items"));
        graph.add_node(NodeId(11), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(12), literal("0", "number"));
        graph.add_ast_edge(NodeId(11), NodeId(12));

        let path = vec![NodeId(9), NodeId(5), NodeId(1)];

        assert_eq!(
            get_element_in_array(&graph, &path, "items", 0),
            Some(NodeId(8))
        );
    }

    #[test]
    fn get_node_access_method_follows_a_variable_declaration_indirection() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(
            NodeId(1),
            method_invocation("get", NodeId(2), Some(NodeId(3))),
        );
        graph.add_node(NodeId(2), symbol_lookup("items"));
        graph.add_node(NodeId(3), SyntaxNode::ArgumentList);
        graph.add_node(NodeId(4), variable_declaration("alias", NodeId(1)));

        graph.add_node(
            NodeId(5),
            method_invocation("size", NodeId(2), Some(NodeId(3))),
        );

        assert_eq!(get_node_access_method(&graph, NodeId(4)), Some(NodeId(1)));
        assert_eq!(get_node_access_method(&graph, NodeId(1)), Some(NodeId(1)));
        assert_eq!(
            get_node_access_method(&graph, NodeId(5)),
            None,
            "only a get call reads an element out of a collection"
        );
    }

    #[test]
    fn adjust_assignment_rewires_a_false_ternary_to_its_false_branch() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(
            NodeId(1),
            SyntaxNode::Assignment {
                variable_id: NodeId(6),
                value_id: Some(NodeId(2)),
                operator: None,
            },
        );
        graph.add_node(
            NodeId(2),
            SyntaxNode::TernaryOperation {
                condition_id: NodeId(3),
                true_id: NodeId(4),
                false_id: NodeId(5),
            },
        );
        graph.add_node(NodeId(3), literal("false", "boolean"));
        graph.add_node(NodeId(4), literal("\"a\"", "string"));
        graph.add_node(NodeId(5), literal("\"b\"", "string"));
        graph.add_node(NodeId(6), symbol_lookup("x"));
        graph.add_ast_edge(NodeId(1), NodeId(2));
        graph.add_ast_edge(NodeId(2), NodeId(3));
        graph.add_ast_edge(NodeId(2), NodeId(4));
        graph.add_ast_edge(NodeId(2), NodeId(5));

        adjust_assignment_ast_edges(&mut graph, NodeId(1));

        assert_eq!(graph.children(NodeId(1)), [NodeId(5)]);
        assert_eq!(
            graph.nodes.get(&NodeId(1)).and_then(SyntaxNode::value_id),
            Some(NodeId(5))
        );
    }

    fn cfg_block(graph: &mut SyntaxGraph, id: u64) {
        graph.add_node(NodeId(id), SyntaxNode::ExecutionBlock);
    }

    #[test]
    fn linear_chain_yields_one_path_to_the_root() {
        let mut graph = SyntaxGraph::new();
        cfg_block(&mut graph, 1);
        cfg_block(&mut graph, 2);
        cfg_block(&mut graph, 3);
        graph.add_cfg_edge(NodeId(1), NodeId(2));
        graph.add_cfg_edge(NodeId(2), NodeId(3));

        assert_eq!(
            get_backward_paths(&graph, NodeId(3), Some(100)),
            [[NodeId(3), NodeId(2), NodeId(1)]]
        );
    }

    #[test]
    fn iter_yields_every_path_unbounded_from_the_given_cfg_node() {
        let mut graph = SyntaxGraph::new();
        cfg_block(&mut graph, 1);
        cfg_block(&mut graph, 2);
        cfg_block(&mut graph, 3);
        graph.add_cfg_edge(NodeId(1), NodeId(3));
        graph.add_cfg_edge(NodeId(2), NodeId(3));

        let paths: Vec<_> = iter_backward_paths(&graph, NodeId(3)).collect();
        assert_eq!(
            paths,
            [vec![NodeId(3), NodeId(1)], vec![NodeId(3), NodeId(2)]]
        );
    }

    #[test]
    fn a_branch_upstream_yields_one_path_per_predecessor_in_id_order() {
        let mut graph = SyntaxGraph::new();
        for id in 1..=4 {
            cfg_block(&mut graph, id);
        }
        graph.add_cfg_edge(NodeId(1), NodeId(3));
        graph.add_cfg_edge(NodeId(2), NodeId(3));
        graph.add_cfg_edge(NodeId(3), NodeId(4));

        assert_eq!(
            get_backward_paths(&graph, NodeId(4), Some(100)),
            [
                vec![NodeId(4), NodeId(3), NodeId(1)],
                vec![NodeId(4), NodeId(3), NodeId(2)],
            ]
        );
    }

    #[test]
    fn a_back_edge_cycle_terminates() {
        let mut graph = SyntaxGraph::new();
        cfg_block(&mut graph, 1);
        cfg_block(&mut graph, 2);
        graph.add_cfg_edge(NodeId(1), NodeId(2));
        graph.add_cfg_edge(NodeId(2), NodeId(1));

        assert_eq!(
            get_backward_paths(&graph, NodeId(2), Some(100)),
            [[NodeId(2), NodeId(1)]]
        );
    }

    #[test]
    fn the_limit_caps_the_number_of_paths() {
        let mut graph = SyntaxGraph::new();
        for id in 1..=4 {
            cfg_block(&mut graph, id);
        }
        graph.add_cfg_edge(NodeId(1), NodeId(4));
        graph.add_cfg_edge(NodeId(2), NodeId(4));
        graph.add_cfg_edge(NodeId(3), NodeId(4));

        assert_eq!(get_backward_paths(&graph, NodeId(4), Some(3)).len(), 2);
    }

    #[test]
    fn a_none_limit_returns_every_path_unbounded() {
        let mut graph = SyntaxGraph::new();
        cfg_block(&mut graph, 1);
        cfg_block(&mut graph, 2);
        cfg_block(&mut graph, 3);
        graph.add_cfg_edge(NodeId(1), NodeId(3));
        graph.add_cfg_edge(NodeId(2), NodeId(3));

        assert_eq!(
            get_backward_paths(&graph, NodeId(3), None),
            [vec![NodeId(3), NodeId(1)], vec![NodeId(3), NodeId(2)]]
        );
    }

    fn assignment(variable_id: NodeId, operator: Option<&str>) -> SyntaxNode {
        SyntaxNode::Assignment {
            variable_id,
            value_id: None,
            operator: operator.map(String::from),
        }
    }

    #[test]
    fn finds_a_variable_declaration_definition() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), variable_declaration("x", NodeId(9)));
        let path = vec![NodeId(1)];

        assert_eq!(definition_search(&graph, &path, "x"), Some(NodeId(1)));
        assert_eq!(definition_search(&graph, &path, "y"), None);
    }

    #[test]
    fn compound_assignment_is_not_a_definition() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(2), symbol_lookup("x"));
        graph.add_node(NodeId(1), assignment(NodeId(2), Some("+=")));
        let path = vec![NodeId(1)];

        assert_eq!(definition_search(&graph, &path, "x"), None);
    }

    #[test]
    fn plain_assignment_is_a_definition() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(2), symbol_lookup("x"));
        graph.add_node(NodeId(1), assignment(NodeId(2), None));
        let path = vec![NodeId(1)];

        assert_eq!(definition_search(&graph, &path, "x"), Some(NodeId(1)));
    }

    #[test]
    fn compound_assignment_does_not_hide_a_later_definition() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(3), symbol_lookup("x"));
        graph.add_node(NodeId(1), assignment(NodeId(3), Some("+=")));
        graph.add_node(NodeId(2), variable_declaration("x", NodeId(9)));
        let path = vec![NodeId(1), NodeId(2)];

        assert_eq!(definition_search(&graph, &path, "x"), Some(NodeId(2)));
    }

    #[test]
    fn file_node_matches_an_import_alias() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), SyntaxNode::File);
        graph.add_node(
            NodeId(2),
            SyntaxNode::Import {
                expression: Some(String::from("os.path")),
                alias: Some(String::from("p")),
                method_name: None,
                import_type: None,
                module_name: None,
            },
        );
        graph.add_cfg_edge(NodeId(1), NodeId(2));
        let path = vec![NodeId(1)];

        assert_eq!(definition_search(&graph, &path, "p"), Some(NodeId(2)));
    }

    fn resolve_lookup(graph: &SyntaxGraph, lookup_id: NodeId, symbol: &str) -> Option<NodeId> {
        get_backward_paths(graph, lookup_id, None)
            .iter()
            .find_map(|path| definition_search(graph, path, symbol))
    }

    // Shape of `String car = "a", plane = "b", boat = "c"; use(plane);` in Java:
    // one declaration per declarator, chained in the CFG.
    #[test]
    fn definition_search_resolves_the_second_local_declarator() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), variable_declaration("car", NodeId(9)));
        graph.add_node(NodeId(2), variable_declaration("plane", NodeId(9)));
        graph.add_node(NodeId(3), variable_declaration("boat", NodeId(9)));
        graph.add_node(NodeId(4), SyntaxNode::ExecutionBlock);
        graph.add_node(NodeId(5), symbol_lookup("plane"));
        graph.add_cfg_edge(NodeId(1), NodeId(2));
        graph.add_cfg_edge(NodeId(2), NodeId(3));
        graph.add_cfg_edge(NodeId(3), NodeId(4));
        graph.add_ast_edge(NodeId(4), NodeId(5));

        assert_eq!(resolve_lookup(&graph, NodeId(5), "plane"), Some(NodeId(2)));
    }

    // Shape of `a, b := 1, 2` in Go and `a, b = 1, 2` in Python: one assignment
    // whose target is an array of lookups.
    #[test]
    fn definition_search_resolves_a_name_declared_beside_another() {
        let mut graph = SyntaxGraph::new();
        graph.add_node(NodeId(1), assignment(NodeId(2), None));
        graph.add_node(
            NodeId(2),
            SyntaxNode::ArrayInitializer {
                variable_type: None,
            },
        );
        graph.add_node(NodeId(3), symbol_lookup("a"));
        graph.add_node(NodeId(4), symbol_lookup("b"));
        graph.add_node(NodeId(5), SyntaxNode::ExecutionBlock);
        graph.add_node(NodeId(6), symbol_lookup("b"));
        graph.add_ast_edge(NodeId(1), NodeId(2));
        graph.add_ast_edge(NodeId(2), NodeId(3));
        graph.add_ast_edge(NodeId(2), NodeId(4));
        graph.add_cfg_edge(NodeId(1), NodeId(5));
        graph.add_ast_edge(NodeId(5), NodeId(6));

        assert_eq!(resolve_lookup(&graph, NodeId(6), "b"), Some(NodeId(1)));
    }
}