//! # Модуль анализа AST
//!
//! Линейный (без построения графа) анализ плоского списка `Statement`.
//! Содержит всё, что можно корректно проверить одним проходом с локальным
//! состоянием, сбрасываемым на границах базового блока (метка/переход/
//! директива) — то, для чего слияние состояний из нескольких предшественников
//! не требуется. Анализы, которым действительно нужен граф потока управления
//! (переход на неизвестную метку, недостижимость из-за отсутствия ссылок
//! откуда-либо в программе), находятся в `analysis::air`.
pub mod err;

use std::collections::HashMap;

use crate::{
    analysis::ast_analysis::err::{
        ASTAnalyseError, ASTAnalyseErrorKind, ASTAnalyseErrorVariant, ASTAnalyseWarningKind,
    },
    isa::{GPRs, Instruction, MnemonicKind, Operand, Registers},
    lexer::token::Span,
    parser::ast::{AST, Statement},
    str_pool::{StrId, StrPool},
};

/// Минимальная длина имени метки, при достижении которой выдаётся warning
/// [`ASTAnalyseWarningKind::LabelNameIsTooLong`].
const LONG_LABEL_NAME_THRESHOLD: usize = 40;

/// Мнемоники, которые **присваивают** значение своему первому операнду
/// без предварительного чтения старого значения (`mov`, `lea`, `pop`).
fn is_pure_write_mnemonic(mnemonic: MnemonicKind) -> bool {
    matches!(
        mnemonic,
        MnemonicKind::Mov | MnemonicKind::Lea | MnemonicKind::Pop
    )
}

/// Мнемоники, которые сначала **читают**, а потом **перезаписывают** свой
/// первый операнд (`add rax, 1` — читает старое `rax`, потом пишет новое).
fn is_read_write_mnemonic(mnemonic: MnemonicKind) -> bool {
    matches!(
        mnemonic,
        MnemonicKind::Add
            | MnemonicKind::Sub
            | MnemonicKind::Xor
            | MnemonicKind::And
            | MnemonicKind::Or
            | MnemonicKind::Shl
            | MnemonicKind::Shr
            | MnemonicKind::Sar
            | MnemonicKind::Inc
            | MnemonicKind::Dec
            | MnemonicKind::Neg
            | MnemonicKind::Not
    )
}

/// Условные переходы (`je`, `jne`, ...) — единственные инструкции, которые
/// "используют" результат предшествующего `cmp`/`test`.
fn is_conditional_jump(mnemonic: MnemonicKind) -> bool {
    matches!(
        mnemonic,
        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
    )
}

/// Является ли мнемоника терминатором базового блока: после неё (или после
/// её разветвления) дальнейший линейный dataflow по регистрам недействителен.
///
/// `call` и `syscall` тоже считаются терминаторами — после возврата состояние
/// регистров может быть произвольно изменено вызванным кодом/ядром ОС.
fn is_block_terminator(mnemonic: MnemonicKind) -> bool {
    is_conditional_jump(mnemonic)
        || matches!(
            mnemonic,
            MnemonicKind::Jmp | MnemonicKind::Call | MnemonicKind::Ret | MnemonicKind::Syscall
        )
}

/// Безусловный выход, после которого следующая инструкция (если перед ней
/// нет метки) гарантированно недостижима: `jmp` (переход всегда происходит)
/// и `ret` (выполнение покидает текущую подпрограмму).
///
/// `call`/условные переходы сюда не входят: `call` гарантированно
/// возвращается на следующую инструкцию, а условный переход с какой-то
/// вероятностью продолжает выполнение по fallthrough.
fn is_unconditional_exit(mnemonic: MnemonicKind) -> bool {
    matches!(mnemonic, MnemonicKind::Jmp | MnemonicKind::Ret)
}

/// Возвращает список регистров, которые инструкция читает неявно
/// (не через явные `operands`), согласно стандартной семантике x86_64.
fn implicit_reads(mnemonic: MnemonicKind) -> &'static [Registers] {
    const RAX: Registers = Registers::GPR(GPRs::Rax);
    const RDX: Registers = Registers::GPR(GPRs::Rdx);

    match mnemonic {
        MnemonicKind::Mul | MnemonicKind::Imul => &[RAX],
        MnemonicKind::Div | MnemonicKind::Idiv => &[RAX, RDX],
        MnemonicKind::Cqo => &[RAX],
        _ => &[],
    }
}

/// Возвращает список регистров, которые инструкция **перезаписывает** неявно
/// (не через явные `operands`), согласно стандартной семантике x86_64.
fn implicit_writes(mnemonic: MnemonicKind) -> &'static [Registers] {
    const RAX: Registers = Registers::GPR(GPRs::Rax);
    const RDX: Registers = Registers::GPR(GPRs::Rdx);

    match mnemonic {
        MnemonicKind::Mul | MnemonicKind::Div | MnemonicKind::Idiv => &[RAX, RDX],
        MnemonicKind::Imul => &[RAX, RDX],
        MnemonicKind::Cqo => &[RDX],
        _ => &[],
    }
}

/// Запись о последней инструкции, присвоившей значение конкретному регистру
/// без последующего чтения — кандидат на "ненужную инструкцию", если она
/// будет перезаписана ещё раз прежде, чем кто-то прочитает регистр.
#[derive(Clone)]
struct PendingWrite {
    instruction: Instruction,
    span: Span,
}

pub struct ASTAnalyser<'a> {
    ast: Vec<Statement>,
    pub errors: Vec<ASTAnalyseError>,
    pub str_pool: &'a StrPool,

    /// Состояние dataflow в пределах текущего линейного участка: какие
    /// регистры несут значение, записанное последний раз и ещё не
    /// прочитанное (см. [`ASTAnalyseWarningKind::UnneededInstruction`]).
    pending_writes: HashMap<Registers, PendingWrite>,

    /// Позиции первого определения каждой метки — для обнаружения повторных
    /// определений (см. [`ASTAnalyseErrorVariant::DuplicateLabel`]).
    label_positions: HashMap<StrId, Span>,

    /// Метки, объявленные подряд непосредственно перед текущей точкой, ещё
    /// без единой инструкции между ними. Используется для обнаружения
    /// [`ASTAnalyseWarningKind::SelfLoop`]: если первая же инструкция после
    /// такой группы меток — безусловный `jmp` на одну из них, это цикл без
    /// прогресса.
    labels_since_last_instruction: Vec<StrId>,

    /// Последний `cmp`/`test`, результат которого ещё не был "использован"
    /// условным переходом — кандидат на [`ASTAnalyseWarningKind::UnusedComparison`].
    pending_comparison: Option<(Instruction, Span)>,

    /// Последний безусловный выход (`jmp`/`ret`), после которого следующая
    /// инструкция (если перед ней нет метки) считается недостижимой —
    /// см. [`ASTAnalyseWarningKind::DeadCodeAfterTerminator`]. `Some`, только
    /// пока мы ещё не встретили ни метку, ни уже зарепортили мёртвый код
    /// для этого участка (чтобы не плодить warning на каждую недостижимую
    /// инструкцию подряд — достаточно одного на участок).
    pending_dead_code_after: Option<(Instruction, Span)>,

    /// Суммарное количество `push`/`pop` за всю программу (см.
    /// [`ASTAnalyseWarningKind::UnbalancedStack`]). Считается глобально, без
    /// сброса на метках/переходах — намеренная эвристика, не точный анализ
    /// баланса стека вызовов.
    stack_pushes: usize,
    stack_pops: usize,
    /// Позиция последней инструкции программы — куда указать
    /// `UnbalancedStack`, если баланс в итоге не сошёлся.
    last_instruction_span: Option<Span>,

    cursor: usize,
}

impl<'a> ASTAnalyser<'a> {
    pub fn new(ast: &AST, str_pool: &'a StrPool) -> Self {
        Self {
            ast: ast.program.clone(),
            errors: Vec::new(),
            str_pool,
            pending_writes: HashMap::new(),
            label_positions: HashMap::new(),
            labels_since_last_instruction: Vec::new(),
            pending_comparison: None,
            pending_dead_code_after: None,
            stack_pushes: 0,
            stack_pops: 0,
            last_instruction_span: None,
            cursor: 0,
        }
    }

    pub fn analyse(&mut self) {
        let ast = std::mem::take(&mut self.ast);
        while self.cursor < self.ast.len() {
            match &ast[self.cursor] {
                Statement::Instruction { span, instruction } => {
                    self.analyse_instruction(instruction, *span);
                }
                Statement::Label { span, name } => {
                    self.analyse_label(*name, *span);
                }
                Statement::Directive { .. } => {
                    // Смена секции (`.text`/`.data`/`.bss`) или любая другая
                    // директива обрывает все локальные участковые состояния:
                    // то, что было до неё, не гарантированно относится к
                    // тому же потоку выполнения.
                    self.pending_writes.clear();
                    self.pending_comparison = None;
                    self.pending_dead_code_after = None;
                    self.labels_since_last_instruction.clear();
                }
            }

            self.cursor += 1;
        }

        self.finish();
        self.ast = ast;
    }

    /// Финальные проверки, которые имеют смысл только после прохода по всей
    /// программе (глобальный баланс стека).
    fn finish(&mut self) {
        if self.stack_pushes != self.stack_pops {
            let span = self.last_instruction_span.unwrap_or_default();
            self.errors.push(ASTAnalyseError::new(
                ASTAnalyseErrorKind::Warning(ASTAnalyseWarningKind::UnbalancedStack {
                    pushes: self.stack_pushes,
                    pops: self.stack_pops,
                }),
                span,
            ));
        }
    }

    fn analyse_label(&mut self, name: StrId, span: Span) {
        // Метка — потенциальная точка входа извне, поэтому обрываем все
        // dataflow-состояния, привязанные к линейному участку.
        self.pending_writes.clear();
        self.pending_comparison = None;
        self.pending_dead_code_after = None;

        // Метка попадает в группу "меток подряд без инструкций между ними",
        // используемую для SelfLoop. Группа очищается при первой же
        // встреченной инструкции (см. `analyse_instruction`).
        self.labels_since_last_instruction.push(name);

        if let Some(&first_pos) = self.label_positions.get(&name) {
            self.errors.push(ASTAnalyseError::new(
                ASTAnalyseErrorKind::Error(ASTAnalyseErrorVariant::DuplicateLabel {
                    name,
                    first_pos,
                }),
                span,
            ));
        } else {
            self.label_positions.insert(name, span);
        }

        let label_name = self.str_pool.get(name);
        if label_name.len() >= LONG_LABEL_NAME_THRESHOLD {
            self.errors.push(ASTAnalyseError::new(
                ASTAnalyseErrorKind::Warning(ASTAnalyseWarningKind::LabelNameIsTooLong(
                    label_name.to_string(),
                )),
                span,
            ));
        }
    }

    fn analyse_instruction(&mut self, instruction: &Instruction, span: Span) {
        self.last_instruction_span = Some(span);

        // --- Недостижимый код в пределах линейного участка ---
        // Проверяем это первым и независимо от остальных чеков: даже если
        // эта же инструкция параллельно триггерит что-то ещё (например,
        // сама являясь мёртвым `mov rax, rax`), мёртвый код всё равно стоит
        // отметить один раз для участка.
        if let Some((terminator, terminator_pos)) = self.pending_dead_code_after.take() {
            self.errors.push(ASTAnalyseError::new(
                ASTAnalyseErrorKind::Warning(ASTAnalyseWarningKind::DeadCodeAfterTerminator {
                    terminator,
                    terminator_pos,
                    dead_instruction: instruction.clone(),
                    dead_pos: span,
                }),
                span,
            ));
            // Не репортим повторно для каждой следующей инструкции того же
            // недостижимого участка — `pending_dead_code_after` уже `None`
            // после `.take()`, новый репорт появится только после
            // следующего безусловного выхода.
        }

        // --- Самозацикливание: `label: jmp label` без инструкций между ---
        if !self.labels_since_last_instruction.is_empty() {
            if instruction.mnemonic == MnemonicKind::Jmp
                && let Some(Operand::Label(target)) = instruction.operands.first()
                && self.labels_since_last_instruction.contains(target)
            {
                self.errors.push(ASTAnalyseError::new(
                    ASTAnalyseErrorKind::Warning(ASTAnalyseWarningKind::SelfLoop {
                        label: *target,
                        jmp_pos: span,
                    }),
                    span,
                ));
            }
            self.labels_since_last_instruction.clear();
        }

        // --- Деление на ноль ---
        if matches!(instruction.mnemonic, MnemonicKind::Div | MnemonicKind::Idiv)
            && let Some(Operand::Immediate(0)) = instruction.operands.first()
        {
            self.errors.push(ASTAnalyseError::new(
                ASTAnalyseErrorKind::Error(ASTAnalyseErrorVariant::DivisionByZero(
                    instruction.clone(),
                )),
                span,
            ));
        }

        // --- Самоприсваивание: `mov reg, reg` ---
        if instruction.mnemonic == MnemonicKind::Mov
            && let [Operand::Register(dst), Operand::Register(src)] =
                instruction.operands.as_slice()
            && dst == src
        {
            self.errors.push(ASTAnalyseError::new(
                ASTAnalyseErrorKind::Warning(ASTAnalyseWarningKind::RedundantSelfAssign(
                    instruction.clone(),
                )),
                span,
            ));
        }

        // --- Бессмысленная арифметика: `add`/`sub` reg, 0 ---
        if matches!(instruction.mnemonic, MnemonicKind::Add | MnemonicKind::Sub)
            && let [_, Operand::Immediate(0)] = instruction.operands.as_slice()
        {
            self.errors.push(ASTAnalyseError::new(
                ASTAnalyseErrorKind::Warning(ASTAnalyseWarningKind::NoOpArithmetic(
                    instruction.clone(),
                )),
                span,
            ));
        }

        // --- Баланс стека (глобальный счётчик, без сброса) ---
        match instruction.mnemonic {
            MnemonicKind::Push => self.stack_pushes += 1,
            MnemonicKind::Pop => self.stack_pops += 1,
            _ => {}
        }

        // --- Неиспользованное сравнение ---
        // Условный переход "использует" самый последний pending `cmp`/`test`.
        // Любая другая инструкция между `cmp`/`test` и условным переходом не
        // отменяет это намерение (например, `cmp rax, 5` / `mov rdi, 1` /
        // `je label` — `mov` не трогает флаги ALU в этой модели ISA).
        if is_conditional_jump(instruction.mnemonic) {
            self.pending_comparison = None;
        } else if matches!(instruction.mnemonic, MnemonicKind::Cmp | MnemonicKind::Test) {
            // Если предыдущий `cmp`/`test` так и не был использован —
            // он сам был бессмысленным, репортим прежде чем завести новый.
            if let Some((prev_instr, prev_span)) = self.pending_comparison.take() {
                self.errors.push(ASTAnalyseError::new(
                    ASTAnalyseErrorKind::Warning(ASTAnalyseWarningKind::UnusedComparison(
                        prev_instr,
                    )),
                    prev_span,
                ));
            }
            self.pending_comparison = Some((instruction.clone(), span));
        }

        // --- Linear dataflow для UnneededInstruction ---
        // 1. Сначала читаем — порядок важен для инструкций вида `add rax, 1`,
        //    где `rax` является и источником, и приёмником одновременно.
        for reg in self.read_registers(instruction) {
            self.pending_writes.remove(&reg);
        }
        // 2. Затем пишем.
        for reg in self.write_registers(instruction) {
            self.register_write(reg, instruction, span);
        }

        // --- Границы участка ---
        if is_block_terminator(instruction.mnemonic) {
            self.pending_writes.clear();

            // Незавершённое сравнение перед безусловным переходом/выходом —
            // тоже бессмысленно (условный переход уже не последует).
            if let Some((prev_instr, prev_span)) = self.pending_comparison.take() {
                self.errors.push(ASTAnalyseError::new(
                    ASTAnalyseErrorKind::Warning(ASTAnalyseWarningKind::UnusedComparison(
                        prev_instr,
                    )),
                    prev_span,
                ));
            }
        }

        if is_unconditional_exit(instruction.mnemonic) {
            self.pending_dead_code_after = Some((instruction.clone(), span));
        }
    }

    /// Регистрирует запись в регистр: если по нему уже висит непрочитанная
    /// запись от чисто присваивающей инструкции (`mov`/`lea`/`pop`), эта
    /// старая запись была лишней — выдаём warning.
    fn register_write(&mut self, reg: Registers, instruction: &Instruction, span: Span) {
        if let Some(pending) = self.pending_writes.get(&reg)
            && is_pure_write_mnemonic(pending.instruction.mnemonic)
        {
            self.errors.push(ASTAnalyseError::new(
                ASTAnalyseErrorKind::Warning(ASTAnalyseWarningKind::UnneededInstruction {
                    unneeded: pending.instruction.clone(),
                    unneeded_pos: pending.span,
                    useful: instruction.clone(),
                    useful_pos: span,
                }),
                span,
            ));
        }

        if is_pure_write_mnemonic(instruction.mnemonic) {
            self.pending_writes.insert(
                reg,
                PendingWrite {
                    instruction: instruction.clone(),
                    span,
                },
            );
        } else {
            self.pending_writes.remove(&reg);
        }
    }

    /// Регистры, которые инструкция читает явно (операнды) и неявно
    /// (архитектурные эффекты вроде `mul`/`div`/`cqo`).
    fn read_registers(&self, instruction: &Instruction) -> Vec<Registers> {
        let mut regs = Vec::new();

        for (idx, operand) in instruction.operands.iter().enumerate() {
            let is_destination = idx == 0;
            let reads_as_source = !is_destination
                || is_read_write_mnemonic(instruction.mnemonic)
                || !is_pure_write_mnemonic(instruction.mnemonic);

            match operand {
                Operand::Register(reg) if reads_as_source => regs.push(*reg),
                Operand::Memory(mem) => {
                    if let Some(base) = mem.base {
                        regs.push(base);
                    }
                    if let Some(index) = mem.index {
                        regs.push(Registers::GPR(index));
                    }
                }
                _ => {}
            }
        }

        regs.extend_from_slice(implicit_reads(instruction.mnemonic));
        regs
    }

    /// Регистры, в которые инструкция пишет (явно через первый операнд, либо
    /// неявно через архитектурные эффекты).
    fn write_registers(&self, instruction: &Instruction) -> Vec<Registers> {
        let mut regs = Vec::new();

        let writes_destination = is_pure_write_mnemonic(instruction.mnemonic)
            || is_read_write_mnemonic(instruction.mnemonic);

        if writes_destination && let Some(Operand::Register(reg)) = instruction.operands.first() {
            regs.push(*reg);
        }

        regs.extend_from_slice(implicit_writes(instruction.mnemonic));
        regs
    }
}
