import t, c
from stdint import *
import string
import viperlib
import memhub
from linkedlist import GSListNode, GSList
from .__function import Function, BasicBlock, Line, Param
from .__module import LLVMModule


# ============================================================
# SSA 验证器
#
# 检查项:
#   1. 块终止: 每个基本块必须以终止指令结尾 (ret/br/switch/unreachable)
#   2. SSA 唯一性: 每个 %name 只能被定义一次
#   3. 未定义引用: 所有 %name 使用必须有对应定义
#   4. Phi 位置: phi 指令只能出现在块首（非 phi 指令之前）
# ============================================================

# 错误码
VERIFY_OK:               t.CDefine = 0
VERIFY_ERR_NO_TERMINATOR:  t.CDefine = 1
VERIFY_ERR_DUPLICATE_DEF:  t.CDefine = 2
VERIFY_ERR_UNDEFINED_USE:  t.CDefine = 3
VERIFY_ERR_PHI_NOT_FIRST:  t.CDefine = 4


# ============================================================
# NameEntry: 已定义 SSA 名条目（链表节点）
#
# 注意: 必须加 @t.NoVTable（理由见 __function.py 的 Line 注释）。
# ============================================================
@t.NoVTable
class NameEntry(GSListNode[NameEntry]):
    Name: t.CChar | t.CPtr          # SSA 名（如 "%0"/"%result"）


# ============================================================
# VerifyResult: 验证结果
# ============================================================
class VerifyResult:
    ErrorCount: t.CInt              # 错误总数
    WarningCount: t.CInt            # 警告总数
    ErrorCode: t.CInt               # 第一个错误码
    ErrorBuf: t.CChar | t.CPtr      # 错误消息缓冲区
    ErrorBufSize: t.CSizeT          # 缓冲区大小


# ============================================================
# 辅助函数
# ============================================================
def _new_verify_result(pool: memhub.MemBuddy | t.CPtr,
                       buf_size: t.CSizeT) -> VerifyResult | t.CPtr:
    """创建验证结果对象"""
    ptr: VerifyResult | t.CPtr = pool.alloc(VerifyResult.__sizeof__())
    if ptr is None: return None
    string.memset(ptr, 0, VerifyResult.__sizeof__())
    ptr.ErrorCount = 0
    ptr.WarningCount = 0
    ptr.ErrorCode = VERIFY_OK
    buf: t.CChar | t.CPtr = pool.alloc(buf_size)
    if buf is not None:
        buf[0] = '\0'
        ptr.ErrorBuf = buf
        ptr.ErrorBufSize = buf_size
    return ptr


def _report_error(result: VerifyResult | t.CPtr, code: t.CInt, msg: t.CChar | t.CPtr):
    """记录一个错误"""
    if result is None: return
    result.ErrorCount += 1
    if result.ErrorCode == VERIFY_OK:
        result.ErrorCode = code
    if result.ErrorBuf is not None and msg is not None:
        _append_cstr(result.ErrorBuf, result.ErrorBufSize, msg)
        _append_cstr(result.ErrorBuf, result.ErrorBufSize, "\n")


def _append_cstr(dst: t.CChar | t.CPtr, dst_size: t.CSizeT, src: t.CChar | t.CPtr):
    """将 src 追加到 dst 末尾"""
    if dst is None or src is None: return
    dlen: t.CSizeT = string.strlen(dst)
    slen: t.CSizeT = string.strlen(src)
    remain: t.CSizeT = dst_size - dlen
    if remain <= 0: return
    i: t.CSizeT = 0
    while i < slen and i + 1 < remain:
        dst[dlen + i] = src[i]
        i += 1
    dst[dlen + i] = '\0'


# ============================================================
# SSA 名表操作
# ============================================================
def _new_name_table(pool: memhub.MemBuddy | t.CPtr) -> GSList[NameEntry] | t.CPtr:
    """创建空名表"""
    gsl: GSList[NameEntry] | t.CPtr = pool.alloc(24)  # GSList: Head+Tail+Count
    if gsl is None: return None
    string.memset(gsl, 0, 24)
    return gsl


# NameEntry 硬编码大小: Next(8) + Name(8) = 16 字节
NENTRY_SIZE: t.CDefine = 16

def _name_table_add(table: GSList[NameEntry] | t.CPtr,
                    pool: memhub.MemBuddy | t.CPtr,
                    name: t.CChar | t.CPtr) -> t.CInt:
    """添加名到表。返回 1=重复, 0=成功添加"""
    if table is None or name is None: return 0
    # 检查重复
    cur: NameEntry | t.CPtr = table.Head
    while cur is not None:
        if string.strcmp(cur.Name, name) == 0:
            return 1
        cur = cur.Next
    # 添加新条目
    entry: NameEntry | t.CPtr = pool.alloc(NENTRY_SIZE)
    if entry is None: return 0
    string.memset(entry, 0, NENTRY_SIZE)
    entry.Name = name
    table.append(entry)
    return 0


def _name_table_contains(table: GSList[NameEntry] | t.CPtr,
                         name: t.CChar | t.CPtr) -> t.CInt:
    """检查名是否在表中。返回 1=存在, 0=不存在"""
    if table is None or name is None: return 0
    cur: NameEntry | t.CPtr = table.Head
    while cur is not None:
        if string.strcmp(cur.Name, name) == 0:
            return 1
        cur = cur.Next
    return 0


# ============================================================
# 文本分析辅助
# ============================================================
def _is_char_name(ch: t.CChar) -> t.CInt:
    """判断字符是否为 SSA 名字符 [a-zA-Z0-9._]"""
    if ch >= 'a' and ch <= 'z': return 1
    if ch >= 'A' and ch <= 'Z': return 1
    if ch >= '0' and ch <= '9': return 1
    if ch == '.' or ch == '_': return 1
    return 0


def _extract_def_name(pool: memhub.MemBuddy | t.CPtr,
                      text: t.CChar | t.CPtr) -> t.CChar | t.CPtr:
    """从定义行提取被定义的 SSA 名。

    定义行格式: "%<name> = <instruction>"
    返回分配的 NUL 结尾名串（如 "%0"），或 None 若非定义行。
    """
    if text is None: return None
    if text[0] != '%': return None
    # 扫描 " = " 模式
    i: t.CInt = 1
    while text[i] != '\0':
        if text[i] == ' ' and text[i + 1] == '=' and text[i + 2] == ' ':
            # 找到 " = " 在位置 i
            name_len: t.CInt = i
            name: t.CChar | t.CPtr = pool.alloc(name_len + 1)
            if name is None: return None
            j: t.CInt = 0
            while j < name_len:
                name[j] = text[j]
                j += 1
            name[name_len] = '\0'
            return name
        i += 1
    return None


def _is_terminator(text: t.CChar | t.CPtr) -> t.CInt:
    """判断文本是否为终止指令"""
    if text is None: return 0
    if string.strncmp(text, "ret", 3) == 0: return 1
    if string.strncmp(text, "br ", 3) == 0: return 1
    if string.strncmp(text, "switch ", 7) == 0: return 1
    if string.strncmp(text, "unreachable", 11) == 0: return 1
    if string.strncmp(text, "indirectbr ", 11) == 0: return 1
    if string.strncmp(text, "resume ", 7) == 0: return 1
    return 0


def _is_phi(text: t.CChar | t.CPtr) -> t.CInt:
    """判断文本是否为 phi 指令"""
    if text is None: return 0
    if string.strstr(text, " = phi ") is not None: return 1
    return 0


def _check_uses_in_line(table: GSList[NameEntry] | t.CPtr,
                        text: t.CChar | t.CPtr,
                        def_name: t.CChar | t.CPtr) -> t.CInt:
    """检查行中所有 SSA 名使用是否已定义。

    跳过 def_name（定义位置的名字）。
    返回未定义使用数量。
    """
    if text is None: return 0
    i: t.CInt = 0
    undef_count: t.CInt = 0
    while text[i] != '\0':
        if text[i] == '%':
            # 提取名
            name_start: t.CInt = i
            i += 1
            while text[i] != '\0' and _is_char_name(text[i]) == 1:
                i += 1
            name_len: t.CInt = i - name_start
            if name_len > 1:
                # 构建临时名串进行比较
                # 由于无法在栈上分配，用 strstr 进行简化检查
                # 这里采用逐字符比较方式
                if _name_matches_at(text, name_start, name_len, table) == 0:
                    # 检查是否是 def_name（定义本身的位置）
                    if def_name is not None:
                        if _str_matches_at(text, name_start, name_len, def_name) == 0:
                            undef_count += 1
                    else:
                        undef_count += 1
        else:
            i += 1
    return undef_count


def _name_matches_at(text: t.CChar | t.CPtr, start: t.CInt, length: t.CInt,
                     table: GSList[NameEntry] | t.CPtr) -> t.CInt:
    """检查 text[start:start+length] 是否匹配名表中的某个条目。
    返回 1=匹配, 0=不匹配
    """
    if table is None: return 0
    cur: NameEntry | t.CPtr = table.Head
    while cur is not None:
        if cur.Name is not None:
            if _str_matches_at(text, start, length, cur.Name) == 1:
                return 1
        cur = cur.Next
    return 0


def _str_matches_at(text: t.CChar | t.CPtr, start: t.CInt, length: t.CInt,
                    target: t.CChar | t.CPtr) -> t.CInt:
    """检查 text[start:start+length] 是否等于 target 字符串。
    返回 1=匹配, 0=不匹配
    """
    if text is None or target is None: return 0
    # 检查 target 长度
    target_len: t.CInt = string.strlen(target)
    if target_len != length: return 0
    i: t.CInt = 0
    while i < length:
        if text[start + i] != target[i]: return 0
        i += 1
    return 1


# ============================================================
# 主验证函数
# ============================================================
def verify_function(pool: memhub.MemBuddy | t.CPtr,
                    func: Function | t.CPtr,
                    result: VerifyResult | t.CPtr) -> t.CInt:
    """验证函数的 SSA 正确性。

    参数:
        pool:   内存池
        func:   要验证的函数
        result: 验证结果（调用前需用 _new_verify_result 创建）

    返回: 错误数量（0 = 验证通过）
    """
    if func is None or result is None: return 1

    # 创建名表
    name_table: GSList[NameEntry] | t.CPtr = _new_name_table(pool)
    if name_table is None: return 1

    # 1. 将函数参数加入名表（参数是已定义的）
    param: Param | t.CPtr = None
    if func.Params is not None:
        param = func.Params.Head
    while param is not None:
        if param.Name is not None:
            _name_table_add(name_table, pool, param.Name)
        param = param.Next

    # 1b. 将基本块名加入名表（块标签如 %then 是 br/phi 的合法引用目标）
    blk_iter: BasicBlock | t.CPtr = None
    if func.Blocks is not None:
        blk_iter = func.Blocks.Head
    while blk_iter is not None:
        if blk_iter.Name is not None:
            blk_name_len: t.CSizeT = string.strlen(blk_iter.Name)
            blk_ref: t.CChar | t.CPtr = pool.alloc(blk_name_len + 2)
            if blk_ref is not None:
                # 构造 "%<name>" 字符串
                blk_ref[0] = '%'
                k: t.CSizeT = 0
                while k < blk_name_len:
                    blk_ref[k + 1] = blk_iter.Name[k]
                    k += 1
                blk_ref[blk_name_len + 1] = '\0'
                _name_table_add(name_table, pool, blk_ref)
        blk_iter = blk_iter.Next

    # 2. 遍历所有块
    blk: BasicBlock | t.CPtr = None
    if func.Blocks is not None:
        blk = func.Blocks.Head
    while blk is not None:
        # 检查终止指令
        if blk.IsTerminated == 0:
            # 进一步检查最后一行是否为终止指令
            has_term: t.CInt = 0
            line_check: Line | t.CPtr = None
            if blk.Lines is not None:
                line_check = blk.Lines.Head
            while line_check is not None:
                if line_check.Buf is not None:
                    if _is_terminator(line_check.Buf) == 1:
                        has_term = 1
                line_check = line_check.Next
            if has_term == 0:
                blk_name: t.CChar | t.CPtr = "<unnamed>"
                if blk.Name is not None:
                    blk_name = blk.Name
                err_buf: t.CChar | t.CPtr = pool.alloc(128)
                if err_buf is not None:
                    viperlib.snprintf(err_buf, 128, "ERROR: block '%s' missing terminator", blk_name)
                    _report_error(result, VERIFY_ERR_NO_TERMINATOR, err_buf)

        # 遍历块内指令行
        seen_non_phi: t.CInt = 0
        line: Line | t.CPtr = None
        if blk.Lines is not None:
            line = blk.Lines.Head
        while line is not None:
            if line.Buf is not None:
                text: t.CChar | t.CPtr = line.Buf

                # 检查 phi 位置
                if _is_phi(text) == 1:
                    if seen_non_phi == 1:
                        phi_err: t.CChar | t.CPtr = pool.alloc(128)
                        if phi_err is not None:
                            viperlib.snprintf(phi_err, 128, "ERROR: phi not at block start")
                            _report_error(result, VERIFY_ERR_PHI_NOT_FIRST, phi_err)
                else:
                    # 非空行且非 phi 标记为已见非 phi
                    if string.strlen(text) > 0:
                        seen_non_phi = 1

                # 提取定义名
                def_name: t.CChar | t.CPtr = _extract_def_name(pool, text)
                if def_name is not None:
                    # 检查重复定义
                    dup: t.CInt = _name_table_add(name_table, pool, def_name)
                    if dup == 1:
                        dup_err: t.CChar | t.CPtr = pool.alloc(128)
                        if dup_err is not None:
                            viperlib.snprintf(dup_err, 128, "ERROR: duplicate definition '%s'", def_name)
                            _report_error(result, VERIFY_ERR_DUPLICATE_DEF, dup_err)

                # 检查未定义使用
                undef: t.CInt = _check_uses_in_line(name_table, text, def_name)
                if undef > 0:
                    use_err: t.CChar | t.CPtr = pool.alloc(128)
                    if use_err is not None:
                        viperlib.snprintf(use_err, 128, "ERROR: %d undefined use(s) in: %s", undef, text)
                        _report_error(result, VERIFY_ERR_UNDEFINED_USE, use_err)

            line = line.Next

        blk = blk.Next

    return result.ErrorCount


def verify_module(pool: memhub.MemBuddy | t.CPtr, mod: LLVMModule | t.CPtr, result: VerifyResult | t.CPtr) -> t.CInt:
    """验证模块中所有函数的 SSA 正确性。

    返回: 错误总数
    """
    if mod is None or result is None: return 1
    func: Function | t.CPtr = mod.FuncHead
    while func is not None:
        if func.IsDeclared == 0:
            # 只验证有函数体的定义，跳过声明
            verify_function(pool, func, result)
        func = func.Next
    return result.ErrorCount
