#WorkBuddy# 82,793 个公式里藏着 1,680 个循环引用：我用“引用解析 + Tarjan 建图”做到环召回 100%

import re
from collections import defaultdict, deque

STR = re.compile(r'"[^"]*"')   # 先挖掉字符串字面量，防止干扰
REF = re.compile(
    r"(?:(?:'(?P<qs>(?:\[[^\]]+\])?[^']+)'|(?P<us>[^\s!(),;+\-*/=<>&\"']+))!)?"
    r"(?P<c1>\$?[A-Z]{1,3}\$?\d{1,7})(?::(?P<c2>\$?[A-Z]{1,3}\$?\d{1,7}))?")

def parse_formula(f, cur_sheet, sheet_names, dn_map):
    """返回 (边集合, 风险集合)。edge: (源, 目标)；risk: 外部/动态/坏表/空引用"""
    edges, risk, body = set(), set(), STR.sub('""', f)
    for m in REF.finditer(body):
        sh = m.group("qs") or m.group("us") or cur_sheet
        if sh.startswith("["):
            risk.add("ext"); continue                     # 外部链接
        if sh not in sheet_names:
            risk.add("bad"); continue                     # 引用不存在的表
        for ck in ("c1", "c2"):
            raw = m.group(ck)
            if raw:
                co = raw.replace("$", "")
                edges.add((cur_sheet, f"{sh}!{co}"))
                if sheet_names[sh].get(co) is None:
                    risk.add("empty")                     # 引用空单元格
    for dn in dn_map:                                     # 命名区域
        if re.search(r"(?<![A-Za-z0-9_])" + re.escape(dn) + r"(?![A-Za-z0-9_])", body):
            sh, co = dn_map[dn]
            edges.add((cur_sheet, f"{sh}!{co}"))
    if re.search(r"\b(INDIRECT|OFFSET|NOW|RAND|TODAY)\b", body, re.I):
        risk.add("dyn")                                   # 动态/易失引用
    return edges, risk

def tarjan_scc(edges):
    """迭代式 Tarjan：返回 size>1 或带自环的强连通分量"""
    adj, nodes = defaultdict(set), set()
    for u, v in edges:
        adj[u].add(v); nodes |= {u, v}
    idx, low, on, stk, out, cnt = {}, {}, {}, [], [], [0]
    for s in nodes:
        if s in idx:
            continue
        idx[s] = low[s] = cnt[0]; cnt[0] += 1
        stk.append(s); on[s] = True
        work = [(s, iter(adj[s]))]
        while work:
            n, it = work[-1]
            pushed = False
            for w in it:
                if w not in idx:
                    idx[w] = low[w] = cnt[0]; cnt[0] += 1
                    stk.append(w); on[w] = True
                    work.append((w, iter(adj[w]))); pushed = True; break
                elif on.get(w):
                    low[n] = min(low[n], idx[w])
            if pushed:
                continue
            work.pop()
            if work:
                low[work[-1][0]] = min(low[work[-1][0]], low[n])
            if low[n] == idx[n]:
                comp = set()
                while True:
                    w = stk.pop(); on[w] = False; comp.add(w)
                    if w == n:
                        break
                if len(comp) > 1 or n in adj[n]:
                    out.append(comp)
    return out

def topo_order(edges, nodes):
    """Kahn：依赖者优先（先算被依赖者）"""
    adj, indeg = defaultdict(set), defaultdict(int)
    for u, v in edges:
        if v not in adj[u]:
            adj[u].add(v); indeg[v] += 1
    rev = defaultdict(set)
    for u in adj:
        for v in adj[u]:
            rev[v].add(u)
    depend = {n: len(adj[n]) for n in nodes}
    q = deque(sorted(n for n in nodes if depend[n] == 0))
    order = []
    while q:
        n = q.popleft(); order.append(n)
        for u in sorted(rev.get(n, ())):
            depend[u] -= 1
            if depend[u] == 0:
                q.append(u)
    return order

# 任务：Excel 公式依赖与循环引用体检
# 语料目录：<你的目录>，输出目录：<你的输出>
# 步骤：
# 1. 用 openpyxl(data_only=False) 遍历目录下全部 .xlsx，
#    抽出所有以 = 开头的字符串单元格作为公式清单；
# 2. 按"引用解析 + Tarjan SCC"方案建依赖图，节点 ID 用 工作簿|表名|坐标；
# 3. 输出四份产物：
#    a) 循环引用清单：每个 SCC 一行，含节点数、涉及工作表、单元格坐标；
#    b) 风险清单：外部链接 / INDIRECT·OFFSET·易失函数 / 引用不存在的表 / 引用空单元格；
#    c) 重算顺序：剔除环后 Kahn 拓扑序，按层输出（第 1 层 = 无依赖公式）；
#    d) 汇总统计：公式总数、依赖边数、环数、最大依赖深度、各风险项计数；
# 4. 先跑一遍"朴素表序"和"拓扑序"的离线重算对比，把两个成功率和耗时写进汇总；
# 5. 全部结果落成 CSV + 一份 Markdown 报告，报告里每个数字都要能追溯到明细行。
# 硬性要求：不得改动原文件；解析失败的公式单独列出来，不许静默跳过。