//! # Граф потока управления (Control Flow Graph)
//!
//! Базовые блоки и рёбра между ними, построенные из плоского списка
//! [`Statement`](crate::parser::ast::Statement) программы.
//!
//! ## Что считается границей базового блока
//! - Любая метка (`Statement::Label`) начинает новый блок — она может быть
//!   целью перехода откуда угодно, поэтому предыдущий поток исполнения
//!   нельзя считать гарантированно продолжающимся в следующую инструкцию
//!   без учёта этого факта.
//! - Любая директива (`Statement::Directive`) также завершает текущий блок:
//!   смена секции (`.text`/`.data`/`.bss`) означает, что код физически
//!   прерывается.
//! - Инструкция-терминатор (переход, `call`, `syscall`, `ret`) завершает
//!   блок и определяет его исходящие рёбра.
use std::collections::HashMap;

use crate::{
    analysis::air::err::{AIRError, AIRErrorKind},
    isa::{Instruction, MnemonicKind, Operand},
    lexer::token::Span,
    parser::ast::{AST, Statement},
    str_pool::StrId,
};

/// Идентификатор базового блока — индекс в [`Cfg::blocks`].
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct BlockId(pub usize);

/// Одна инструкция внутри базового блока вместе с её позицией в исходнике.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BlockInstruction {
    pub instruction: Instruction,
    pub span: Span,
}

/// Способ, которым управление покидает базовый блок.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Terminator {
    /// Безусловный переход на известный блок (`jmp label`).
    Goto { target: BlockId },

    /// Условный переход (`je`, `jne`, ...): если условие выполняется —
    /// управление уходит на `target`, иначе продолжается на `fallthrough`
    /// (следующий блок по тексту программы).
    Branch {
        target: BlockId,
        fallthrough: BlockId,
    },

    /// Вызов (`call label`): управление временно уходит на `target`, но
    /// гарантированно возвращается на `fallthrough` (следующую инструкцию
    /// после `call`), если вызванный код когда-либо выполнит `ret`.
    Call {
        target: BlockId,
        fallthrough: BlockId,
    },

    /// Переход/вызов с динамически вычисляемой целью (`jmp rax`,
    /// `call [rax]`), либо переход на метку, для которой не удалось
    /// построить рёбро (конец программы сразу после условного перехода).
    /// Статически неизвестно, на какой блок ведёт рёбро.
    Indirect,

    /// `ret` — выход из текущей подпрограммы, исходящих рёбер нет.
    Return,

    /// Управление дошло до конца программы (после последней инструкции
    /// блока физически больше ничего нет, и явного `ret` не было).
    FallOff,
}

/// Базовый блок: непрерывная последовательность инструкций без переходов
/// внутри, с единственной точкой входа (началом) и единственным способом
/// покинуть блок (терминатором).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct BasicBlock {
    pub id: BlockId,
    /// Метки, под которыми начинается этот блок (обычно одна, но несколько
    /// меток подряд перед одной и той же инструкцией дают несколько
    /// алиасов для одного и того же блока).
    pub labels: Vec<StrId>,
    pub instructions: Vec<BlockInstruction>,
    pub terminator: Terminator,
    /// Блоки, из которых есть рёбра, ведущие в этот блок.
    pub predecessors: Vec<BlockId>,
}

impl BasicBlock {
    /// Исходящие рёбра этого блока (без учёта `Indirect`/`Return`/`FallOff`,
    /// у которых нет статически известных целей).
    pub fn successors(&self) -> Vec<BlockId> {
        match &self.terminator {
            Terminator::Goto { target } => vec![*target],
            Terminator::Branch {
                target,
                fallthrough,
            } => vec![*target, *fallthrough],
            Terminator::Call {
                target,
                fallthrough,
            } => vec![*target, *fallthrough],
            Terminator::Indirect | Terminator::Return | Terminator::FallOff => vec![],
        }
    }
}

/// Граф потока управления для всей программы.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct Cfg {
    pub blocks: Vec<BasicBlock>,
    /// Блоки, являющиеся точками входа: первый блок программы и любой блок,
    /// на который нет ни одного статически известного рёбра (потенциальная
    /// внешняя точка входа, например `_start`, или просто мёртвый код).
    pub entry_blocks: Vec<BlockId>,
}

impl Cfg {
    pub fn block(&self, id: BlockId) -> &BasicBlock {
        &self.blocks[id.0]
    }

    /// Блоки, у которых нет входящих рёбер и которые не являются первым
    /// блоком программы — потенциально недостижимый код.
    pub fn unreachable_blocks(&self) -> Vec<BlockId> {
        self.blocks
            .iter()
            .filter(|b| b.predecessors.is_empty() && b.id != BlockId(0))
            .map(|b| b.id)
            .collect()
    }
}

/// Извлекает целевую метку перехода/вызова из инструкции, если она
/// статически известна (`Operand::Label`). Возвращает `None` для косвенных
/// переходов (`jmp rax`, `call [rax]`).
fn static_target(instruction: &Instruction) -> Option<StrId> {
    match instruction.operands.first() {
        Some(Operand::Label(id)) => Some(*id),
        _ => None,
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum TerminatorKind {
    Goto,
    Branch,
    Call,
    Return,

    /// Не терминатор — обычная инструкция.
    None,
}

fn terminator_kind(mnemonic: MnemonicKind) -> TerminatorKind {
    match mnemonic {
        MnemonicKind::Jmp => TerminatorKind::Goto,
        MnemonicKind::Je
        | MnemonicKind::Jne
        | MnemonicKind::Jg
        | MnemonicKind::Jge
        | MnemonicKind::Jl
        | MnemonicKind::Jle
        | MnemonicKind::Ja
        | MnemonicKind::Jae
        | MnemonicKind::Jb
        | MnemonicKind::Jbe
        | MnemonicKind::Jo
        | MnemonicKind::Jno
        | MnemonicKind::Js
        | MnemonicKind::Jns
        | MnemonicKind::Jp
        | MnemonicKind::Jnp => TerminatorKind::Branch,
        MnemonicKind::Call | MnemonicKind::Syscall => TerminatorKind::Call,
        MnemonicKind::Ret => TerminatorKind::Return,
        _ => TerminatorKind::None,
    }
}

/// Промежуточное (до связывания рёбер) представление блока во время
/// построения графа.
struct RawBlock {
    labels: Vec<StrId>,
    instructions: Vec<BlockInstruction>,
    /// `(вид терминатора, span терминирующей инструкции, статическая цель)`.
    /// `None`, если блок заканчивается потому что упёрся в конец программы.
    terminator_info: Option<(TerminatorKind, Span, Option<StrId>)>,
}

/// Строит [`Cfg`] из AST. Возвращает ошибки, если переход ссылается на
/// неизвестную метку, или если одна и та же метка определена дважды.
pub fn build_cfg(ast: &AST) -> Result<Cfg, Vec<AIRError>> {
    let mut errors = Vec::new();

    // ---- Проход 1: разбиваем плоский список Statement на сырые блоки ----
    //
    // Дублирующиеся метки (одно имя определено более одного раза) здесь
    // умышленно не проверяются — это AST-уровневая находка
    // (см. `ASTAnalyseErrorVariant::DuplicateLabel`), не требующая графа.
    // Если в программе есть дубликат, индекс `label_to_block` ниже просто
    // запомнит последнее по тексту определение — граф всё равно строится,
    // просто на основе этого (не идеально строгого) выбора.
    let mut raw_blocks: Vec<RawBlock> = Vec::new();
    let mut current = RawBlock {
        labels: Vec::new(),
        instructions: Vec::new(),
        terminator_info: None,
    };

    macro_rules! finish_block {
        () => {{
            let finished = std::mem::replace(
                &mut current,
                RawBlock {
                    labels: Vec::new(),
                    instructions: Vec::new(),
                    terminator_info: None,
                },
            );
            // Не сохраняем полностью пустые блоки без меток — они появляются,
            // например, между двумя директивами подряд и не несут смысла.
            if !finished.instructions.is_empty() || !finished.labels.is_empty() {
                raw_blocks.push(finished);
            }
        }};
    }

    for statement in &ast.program {
        match statement {
            Statement::Label { span: _, name } => {
                // Метка начинает новый блок, если в текущем уже есть
                // инструкции; если блок пуст (метка сразу за меткой),
                // присоединяем имя к тому же блоку — это алиас.
                if !current.instructions.is_empty() {
                    finish_block!();
                }

                current.labels.push(*name);
            }
            Statement::Instruction { span, instruction } => {
                let kind = terminator_kind(instruction.mnemonic);
                current.instructions.push(BlockInstruction {
                    instruction: instruction.clone(),
                    span: *span,
                });

                if kind != TerminatorKind::None {
                    let target = static_target(instruction);
                    current.terminator_info = Some((kind, *span, target));
                    finish_block!();
                }
            }
            Statement::Directive { .. } => {
                // Смена секции (или любая директива) обрывает блок: код по
                // обе стороны от директивы не считается одним потоком.
                finish_block!();
            }
        }
    }
    finish_block!();

    // ---- Проход 2: индексируем, какой блок начинается с какой метки ----
    let mut label_to_block: HashMap<StrId, BlockId> = HashMap::new();
    for (idx, block) in raw_blocks.iter().enumerate() {
        for label in &block.labels {
            label_to_block.insert(*label, BlockId(idx));
        }
    }

    // ---- Проход 3: собираем финальные BasicBlock с разрешёнными рёбрами ----
    let mut blocks: Vec<BasicBlock> = Vec::with_capacity(raw_blocks.len());

    for (idx, raw) in raw_blocks.iter().enumerate() {
        let next_block_id = if idx + 1 < raw_blocks.len() {
            Some(BlockId(idx + 1))
        } else {
            None
        };

        let mut resolve = |label: StrId, span: Span| -> Option<BlockId> {
            match label_to_block.get(&label) {
                Some(id) => Some(*id),
                None => {
                    errors.push(AIRError::new(AIRErrorKind::UnknownLabel(label), span));
                    None
                }
            }
        };

        let terminator = match &raw.terminator_info {
            None => Terminator::FallOff,
            Some((TerminatorKind::Return, _, _)) => Terminator::Return,
            Some((TerminatorKind::Goto, span, target)) => match target {
                Some(label) => match resolve(*label, *span) {
                    Some(block_id) => Terminator::Goto { target: block_id },
                    None => Terminator::Indirect,
                },
                None => Terminator::Indirect,
            },
            Some((TerminatorKind::Branch, span, target)) => match (target, next_block_id) {
                (Some(label), Some(fallthrough)) => match resolve(*label, *span) {
                    Some(block_id) => Terminator::Branch {
                        target: block_id,
                        fallthrough,
                    },
                    None => Terminator::Indirect,
                },
                // Условный переход в самом конце программы без продолжения —
                // нет блока, на который указал бы fallthrough.
                (Some(label), None) => match resolve(*label, *span) {
                    Some(block_id) => Terminator::Goto { target: block_id },
                    None => Terminator::Indirect,
                },
                (None, _) => Terminator::Indirect,
            },
            Some((TerminatorKind::Call, span, target)) => match (target, next_block_id) {
                (Some(label), Some(fallthrough)) => match resolve(*label, *span) {
                    Some(block_id) => Terminator::Call {
                        target: block_id,
                        fallthrough,
                    },
                    None => Terminator::Indirect,
                },
                // `call`/`syscall` в самом конце программы: нет блока, куда
                // вернуться после возврата — граф не может это выразить.
                (Some(_), None) => Terminator::Indirect,
                (None, _) => Terminator::Indirect,
            },
            Some((TerminatorKind::None, _, _)) => unreachable!(
                "терминатор блока не может иметь TerminatorKind::None — \
                 это означало бы, что блок не был на самом деле завершён"
            ),
        };

        blocks.push(BasicBlock {
            id: BlockId(idx),
            labels: raw.labels.clone(),
            instructions: raw.instructions.clone(),
            terminator,
            predecessors: Vec::new(),
        });
    }

    if !errors.is_empty() {
        return Err(errors);
    }

    // ---- Проход 4: заполняем predecessors на основе successors() ----
    let successors: Vec<Vec<BlockId>> = blocks.iter().map(|b| b.successors()).collect();
    for (from_idx, succs) in successors.iter().enumerate() {
        for to in succs {
            blocks[to.0].predecessors.push(BlockId(from_idx));
        }
    }

    // Точки входа: первый блок программы (если есть) плюс любой блок без
    // входящих рёбер (потенциальная внешняя точка входа или мёртвый код —
    // различить их на этом уровне нельзя без таблицы `.global`).
    let mut entry_blocks: Vec<BlockId> = Vec::new();
    if !blocks.is_empty() {
        entry_blocks.push(BlockId(0));
    }
    for block in &blocks {
        if block.id != BlockId(0) && block.predecessors.is_empty() {
            entry_blocks.push(block.id);
        }
    }

    Ok(Cfg {
        blocks,
        entry_blocks,
    })
}
