# -*- coding: utf-8 -*-
"""拓扑排序模块 — Kahn's algorithm

对任务列表按依赖关系执行拓扑排序：
- 显式依赖：TaskMeta.depends_on 声明的任务间依赖
- 隐含层级依赖：ODS → DWD → DWS → INDEX，同批任务中低层任务必须先于高层任务
- 仅对当前执行列表内的任务排序
- depends_on 中引用的任务不在列表内时记录警告
- 检测循环依赖并抛出 ValueError
"""
from collections import deque
import logging

logger = logging.getLogger(__name__)

# 层级优先级：数值越小越先执行
_LAYER_ORDER: dict[str, int] = {
    "ODS": 0,
    "DWD": 1,
    "DWS": 2,
    "INDEX": 3,
}


def topological_sort(task_codes: list[str], registry) -> list[str]:
    """对任务列表执行拓扑排序（Kahn's algorithm）。

    除了显式 depends_on 依赖外，还注入隐含的层级依赖：
    同批任务中，所有 ODS 任务排在 DWD 之前，DWD 排在 DWS 之前，
    DWS 排在 INDEX 之前。这确保跨层执行顺序正确。

    Args:
        task_codes: 待排序的任务代码列表
        registry: TaskRegistry 实例，提供 get_metadata() 查询依赖

    Returns:
        按依赖顺序排列的任务代码列表（被依赖方在前）

    Raises:
        ValueError: 检测到循环依赖时，错误信息包含涉及的任务代码
    """
    if not task_codes:
        return []

    in_degree = {code: 0 for code in task_codes}
    graph: dict[str, list[str]] = {code: [] for code in task_codes}
    task_set = set(task_codes)

    # 1. 显式依赖（depends_on）
    for code in task_codes:
        meta = registry.get_metadata(code)
        if meta and meta.depends_on:
            for dep in meta.depends_on:
                if dep in task_set:
                    graph[dep].append(code)
                    in_degree[code] += 1
                else:
                    logger.warning(
                        "任务 %s 依赖 %s，但后者不在当前执行列表中", code, dep
                    )

    # CHANGE [2026-02-24] intent: 注入隐含层级依赖，确保跨层执行顺序正确
    #   assumptions: 层级顺序固定为 ODS→DWD→DWS→INDEX；同层任务无隐含互相依赖
    #   prompt: "修复管理后台全选任务时不按层级顺序执行的问题"
    # 2. 隐含层级依赖：按层分组，相邻层之间建立边
    #    选择每层一个"代表节点"作为屏障，避免 O(n*m) 的全连接边
    layer_groups: dict[int, list[str]] = {}
    for code in task_codes:
        meta = registry.get_metadata(code)
        if meta and meta.layer:
            order = _LAYER_ORDER.get(meta.layer.upper())
            if order is not None:
                layer_groups.setdefault(order, []).append(code)

    sorted_layers = sorted(layer_groups.keys())
    for i in range(len(sorted_layers) - 1):
        lower_layer = sorted_layers[i]
        higher_layer = sorted_layers[i + 1]
        # 高层的每个任务都依赖低层的所有任务
        for higher_code in layer_groups[higher_layer]:
            for lower_code in layer_groups[lower_layer]:
                # 避免重复添加已有的显式依赖边
                if higher_code not in graph[lower_code]:
                    graph[lower_code].append(higher_code)
                    in_degree[higher_code] += 1

    queue = deque(code for code in task_codes if in_degree[code] == 0)
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != len(task_codes):
        cycle_tasks = [c for c in task_codes if c not in result]
        raise ValueError(f"检测到循环依赖: {cycle_tasks}")

    return result
