cut_header.py

#!/usr/bin/env python3

import argparse
import csv
import curses
import io
import json
import logging
import os
import platform
import re
import subprocess
import sys
import urllib.request
from collections import defaultdict
from itertools import batched
from typing import List, Optional, Set, Tuple

import networkx as nx
from dotenv import load_dotenv
from networkx.algorithms.connectivity import minimum_st_edge_cut
from networkx.algorithms.flow import build_residual_network

from count_reachable_roots import count_reachable_roots
from include_analysis import IncludeAnalysisOutput, ParseError, load_include_analysis
from utils import create_graph_from_include_analysis


def copy_to_clipboard(text):
    system = platform.system()
    if system == "Windows":
        cmd = "clip"
    elif system == "Darwin":  # macOS
        cmd = "pbcopy"
    else:  # Linux
        cmd = "xclip -selection clipboard"

    subprocess.run(cmd, input=text.encode("utf-8"), shell=True, check=True)


def open_url(url):
    system = platform.system()
    if system == "Windows":
        os.startfile(url)
    elif system == "Darwin":  # macOS
        subprocess.run(["open", url], check=True)
    else:  # Linux
        subprocess.run(["xdg-open", url], check=True)


def create_include_graph(
    include_analysis: IncludeAnalysisOutput,
    target: str,
    ignores: Optional[Tuple[Tuple[str, str]]],
    removes: Optional[Tuple[Tuple[str, str]]],
) -> nx.DiGraph:
    DG: nx.DiGraph = create_graph_from_include_analysis(include_analysis)
    files = include_analysis["files"]
    files_set = set(files)
    file_idx_lookup = {filename: idx for idx, filename in enumerate(files)}

    if removes:
        for includer, included in removes:
            if includer in files_set and included in files_set:
                includer_idx = file_idx_lookup[includer]
                included_idx = file_idx_lookup[included]

                if DG.has_edge(includer_idx, included_idx):
                    DG.remove_edge(includer_idx, included_idx)
                else:
                    logging.warning(f"Remove edge {includer} -> {included} not found in include graph")
            else:
                logging.warning(f"Remove edge {includer} -> {included} not found in include analysis")

    if ignores:
        # Set capacity high for ignored edges to prevent cutting them
        for includer, included in ignores:
            if includer in files_set and included in files_set:
                includer_idx = file_idx_lookup[includer]
                included_idx = file_idx_lookup[included]

                if DG.has_edge(includer_idx, included_idx):
                    DG[includer_idx][included_idx]["capacity"] = float("inf")
                else:
                    logging.warning(f"Ignore edge {includer} -> {included} not found in include graph")
            elif includer in files_set and included == "*":
                includer_idx = file_idx_lookup[includer]
                for _, included_idx in DG.out_edges(includer_idx):
                    DG[includer_idx][included_idx]["capacity"] = float("inf")
            else:
                logging.warning(f"Ignore edge {includer} -> {included} not found in include analysis")

    # Set capacity high for edges inside generated files to prevent cutting them
    # TODO - make this optional
    for edge in DG.edges():
        filename = files[edge[0]]

        if filename.startswith("out/"):
            DG[edge[0]][edge[1]]["capacity"] = float("inf")
        elif filename.startswith("build/linux/debian_bullseye_amd64-sysroot/"):
            DG[edge[0]][edge[1]]["capacity"] = float("inf")
        elif filename.startswith("third_party/llvm-build/Release+Asserts/"):
            DG[edge[0]][edge[1]]["capacity"] = float("inf")
        elif filename.startswith("third_party/abseil-cpp/"):
            DG[edge[0]][edge[1]]["capacity"] = float("inf")
        elif filename.startswith("v8/include/"):
            DG[edge[0]][edge[1]]["capacity"] = float("inf")

    # Remove everything in the graph that's not reachable from the target to speed up analysis
    return DG.subgraph(nx.dfs_postorder_nodes(DG.reverse(False), source=file_idx_lookup[target])).copy()


def compute_direct_cuts_floor(
    include_analysis: IncludeAnalysisOutput,
    DG: nx.DiGraph,
    target: str,
) -> int:
    """Compute the floor of reachable roots if all possible direct cuts are made.

    Direct cuts are edges that include the target header directly. Edges
    with infinite capacity (from ignores) are not cut.
    """
    files = include_analysis["files"]
    target_idx = files.index(target)
    DG2 = DG.copy()

    # Remove all direct includes of target that are not ignored (infinite capacity)
    for includer_idx, _, capacity in list(DG2.in_edges(target_idx, "capacity", 1)):
        if capacity != float("inf"):
            DG2.remove_edge(includer_idx, target_idx)

    return count_reachable_roots(include_analysis, DG2, target)


def compute_all_cuts_floor(
    include_analysis: IncludeAnalysisOutput,
    DG: nx.DiGraph,
    target: str,
) -> int:
    """Compute the floor of reachable roots if all possible cuts are made, including direct and indirect cuts.

    Indirect cuts are edges that do not directly include the target header
    but are on a path to the target. Edges with infinite capacity (from ignores)
    are not cut.
    """
    DG2 = DG.copy()

    # Remove all edges that are not ignored (infinite capacity)
    for includer_idx, included_idx, capacity in DG.edges(None, "capacity", 1):
        if capacity != float("inf"):
            DG2.remove_edge(includer_idx, included_idx)

    return count_reachable_roots(include_analysis, DG2, target)


def do_minimum_edge_cut(
    DG: nx.DiGraph,
    source: int,
    target: int,
) -> Tuple[Tuple[int, int], ...]:
    """Compute the minimum edge cut between source and target using min-cut partitioning."""
    _, partition = nx.minimum_cut(DG, source, target)
    reachable, non_reachable = partition

    cutset = set()
    for u, nbrs in ((n, DG[n]) for n in reachable):
        cutset.update((u, v) for v in nbrs if v in non_reachable)

    return tuple(cutset)


def find_cuttable_sources(args):
    """Find which sources have a finite minimum cut to the target."""
    PSEUDO_NODE = 8888888888

    sources, DG, target = args
    cuttable_sources = []

    # Try cutting all sources at once first as a shortcut
    DG2 = DG.copy()
    DG2.add_node(PSEUDO_NODE)

    for source in sources:
        DG2.add_edge(PSEUDO_NODE, source, capacity=float("inf"))

    R2 = build_residual_network(DG2, "capacity")

    try:
        minimum_st_edge_cut(DG2, PSEUDO_NODE, target, residual=R2)
        return sources
    except nx.NetworkXUnbounded:
        pass

    R = build_residual_network(DG, "capacity")

    # Otherwise try each source individually
    for source in sources:
        try:
            minimum_st_edge_cut(DG, source, target, residual=R)
            cuttable_sources.append(source)
        except nx.NetworkXUnbounded:
            continue

    return cuttable_sources


def compute_top_indirect_cuts(
    include_analysis: IncludeAnalysisOutput,
    DG: nx.DiGraph,
    target: str,
    edge_dominations: dict,
) -> List[Tuple[str, str, float, int]]:
    """Compute the top indirect cuts ranked by prevalence of the includer file.

    Indirect cuts are edges in the minimum edge cut from all reachable roots
    to the target that do NOT directly include the target header. These are
    edges on transitive paths to the target whose removal would disconnect
    roots from reaching the target.

    Uses the same minimum edge cut approach as `minimum_edge_cut.py`:
    a pseudo-source node is connected to all cuttable reachable roots, and the
    minimum cut between the pseudo-source and the target is computed.

    Before connecting roots to the pseudo-source, each root is tested for
    cuttability (whether a finite min-cut exists to the target), following
    the `find_cuttable_sources` pattern from `minimum_edge_cut.py`.
    """
    files = include_analysis["files"]
    target_idx = files.index(target)
    total_roots = len(include_analysis["roots"])

    PSEUDO_SOURCE = 99999999

    DG2 = DG.copy()
    DG2.add_node(PSEUDO_SOURCE)

    # Find reachable roots
    reachable_nodes = set(files[idx] for idx in nx.dfs_postorder_nodes(DG2.reverse(False), source=target_idx))
    reachable_roots = [
        root
        for root in include_analysis["roots"]
        if root in reachable_nodes and not root.startswith("out/") and files.index(root) != target_idx
    ]

    if not reachable_roots:
        return []

    import concurrent.futures
    from tqdm import tqdm
    from tqdm.contrib.logging import logging_redirect_tqdm

    # Filter to only cuttable sources using batched checks
    chunk_size = 8
    cuttable_count = 0

    chunked = list(batched((files.index(root) for root in reachable_roots), chunk_size))

    with logging_redirect_tqdm(), tqdm(
        disable=len(reachable_roots) == 1, total=len(reachable_roots), unit="file"
    ) as progress_output:
        with concurrent.futures.ProcessPoolExecutor() as pool:
            DG_copy = DG2.copy()

            for cuttable_sources in pool.map(
                find_cuttable_sources,
                ((chunk, DG_copy, target_idx) for chunk in chunked),
            ):
                progress_output.update(min(chunk_size, progress_output.total - progress_output.n))

                for source_idx in cuttable_sources:
                    cuttable_count += 1
                    DG2.add_edge(PSEUDO_SOURCE, source_idx, capacity=float("inf"))

        logging.debug(f"Cuttable sources: {cuttable_count} / {len(reachable_roots)}")

    if cuttable_count == 0:
        return []

    try:
        edge_cut = do_minimum_edge_cut(DG2, PSEUDO_SOURCE, target_idx)
    except nx.NetworkXUnbounded:
        return []

    # Filter to only indirect cuts (edges that do NOT point directly to the target)
    indirect_cuts = []
    for includer_idx, included_idx in edge_cut:
        if included_idx == target_idx:
            continue  # This is a direct cut, skip it
        if includer_idx == PSEUDO_SOURCE:
            continue  # Skip pseudo-node edges

        includer_file = files[includer_idx]
        included_file = files[included_idx]

        # Skip ignored edges (infinite capacity)
        if DG2[includer_idx][included_idx].get("capacity", 1) == float("inf"):
            continue

        includer_prevalence = 100.0 * (include_analysis["prevalence"][includer_file] / total_roots)
        dominated_edges = edge_dominations[(includer_file, included_file)]
        indirect_cuts.append((includer_file, included_file, includer_prevalence, dominated_edges))

    return indirect_cuts


def compute_direct_cuts(
    include_analysis: IncludeAnalysisOutput,
    DG: nx.DiGraph,
    target: str,
    edge_dominations: dict,
) -> List[Tuple[str, str, float, int]]:
    files = include_analysis["files"]
    total_roots = len(include_analysis["roots"])

    target_idx = files.index(target)
    direct_includers = []

    for includer_idx, _, capacity in DG.in_edges(target_idx, "capacity", 1):
        # Skip ignored edges (infinite capacity)
        if capacity == float("inf"):
            continue

        includer_file = files[includer_idx]
        includer_prevalence = 100.0 * (include_analysis["prevalence"][includer_file] / total_roots)
        direct_includers.append(
            (includer_file, target, includer_prevalence, edge_dominations[(includer_file, target)])
        )

    return direct_includers


# From analyze_includes.py in Chromium
def compute_doms(root, includes):
    """Compute the dominators for all nodes reachable from root. Node A dominates
    node B if all paths from the root to B go through A. Returns a dict from
    filename to the set of dominators of that filename (including itself).

    The implementation follows the "simple" version of Lengauer & Tarjan "A Fast
    Algorithm for Finding Dominators in a Flowgraph" (TOPLAS 1979).
    """

    parent = {}
    ancestor = {}
    vertex = []
    label = {}
    semi = {}
    pred = defaultdict(list)
    bucket = defaultdict(list)
    dom = {}

    def dfs(v):
        semi[v] = len(vertex)
        vertex.append(v)
        label[v] = v

        for w in includes[v]:
            if w not in semi:
                parent[w] = v
                dfs(w)
            pred[w].append(v)

    def compress(v):
        if ancestor[v] in ancestor:
            compress(ancestor[v])
            if semi[label[ancestor[v]]] < semi[label[v]]:
                label[v] = label[ancestor[v]]
            ancestor[v] = ancestor[ancestor[v]]

    def evaluate(v):
        if v not in ancestor:
            return v
        compress(v)
        return label[v]

    def link(v, w):
        ancestor[w] = v

    # Step 1: Initialization.
    dfs(root)

    for w in reversed(vertex[1:]):
        # Step 2: Compute semidominators.
        for v in pred[w]:
            u = evaluate(v)
            if semi[u] < semi[w]:
                semi[w] = semi[u]

        bucket[vertex[semi[w]]].append(w)
        link(parent[w], w)

        # Step 3: Implicitly define the immediate dominator for each node.
        for v in bucket[parent[w]]:
            u = evaluate(v)
            dom[v] = u if semi[u] < semi[v] else parent[w]
        bucket[parent[w]] = []

    # Step 4: Explicitly define the immediate dominator for each node.
    for w in vertex[1:]:
        if dom[w] != vertex[semi[w]]:
            dom[w] = dom[dom[w]]

    # Get the full dominator set for each node.
    all_doms = {}
    all_doms[root] = {root}

    def dom_set(node):
        if node not in all_doms:
            # node's dominators is itself and the dominators of its immediate
            # dominator.
            all_doms[node] = {node}
            all_doms[node].update(dom_set(dom[node]))

        return all_doms[node]

    return {n: dom_set(n) for n in vertex}


# From analyze_includes.py in Chromium
def compute_added_sizes(args):
    """Helper to compute added sizes from the given root."""

    roots, includes, sizes = args
    added_sizes = {node: 0 for node in includes}

    for root in roots:
        doms = compute_doms(root, includes)

        for node in doms:
            if node not in sizes:
                # Skip the (src,dst) pseudo nodes.
                continue
            for dom in doms[node]:
                added_sizes[dom] += sizes[node]

    return added_sizes


# Adapted from analyze_includes.py in Chromium
def compute_doms_to_target(include_analysis: IncludeAnalysisOutput, DG: nx.DiGraph, target: str):
    files = include_analysis["files"]
    target_idx = files.index(target)

    # Find reachable roots
    reachable_nodes = set(files[idx] for idx in nx.dfs_postorder_nodes(DG.reverse(False), source=target_idx))
    roots = [
        root
        for root in include_analysis["roots"]
        if root in reachable_nodes and not root.startswith("out/") and files.index(root) != target_idx
    ]

    # Give each node a zero size, except for the target node
    sizes = {data["filename"]: 0 for _, data in DG.nodes(data=True) if "filename" in data}

    # Set size to be one, which means added size will effectively count the number
    # of roots that are dominated by any given edge from roots to the target node
    sizes[target] = 1

    # Split each src -> dst edge in includes into src -> (src,dst) -> dst, so that
    # we can compute how much each include graph edge adds to the size by doing
    # dominance analysis on the (src,dst) nodes.
    augmented_includes = {}
    for src_node_id, src_data in DG.nodes(data=True):
        if "filename" not in src_data:
            continue

        src = src_data["filename"]
        if src not in augmented_includes:
            augmented_includes[src] = set()

        for dst_node_id in DG.successors(src_node_id):
            dst = DG.nodes(data=True)[dst_node_id]["filename"]
            augmented_includes[src].add((src, dst))
            augmented_includes[(src, dst)] = {dst}

    return compute_added_sizes((roots, augmented_includes, sizes))


def calculate_floors(
    include_analysis: IncludeAnalysisOutput,
    target: str,
    ignores: Optional[Tuple[Tuple[str, str]]] = None,
    removes: Optional[Tuple[Tuple[str, str]]] = None,
):
    total_roots = len(include_analysis["roots"])

    # Remaining: reachable roots after removes are applied
    DG = create_include_graph(include_analysis, target, ignores=ignores, removes=removes)
    remaining_reachable = count_reachable_roots(include_analysis, DG, target)

    # Get original prevalence for the target header (reachable roots without any removes)
    DG_original = create_graph_from_include_analysis(include_analysis)
    original_reachable = count_reachable_roots(include_analysis, DG_original, target)

    if original_reachable == 0:
        remaining_pct = 0.0
    else:
        remaining_pct = 100.0 * remaining_reachable / original_reachable

    remaining_prevalence = 100.0 * remaining_reachable / total_roots

    # Direct cuts floor
    direct_floor = compute_direct_cuts_floor(include_analysis, DG, target)

    if original_reachable == 0:
        direct_floor_pct = 0.0
    else:
        direct_floor_pct = 100.0 * direct_floor / original_reachable

    direct_floor_prevalence = 100.0 * direct_floor / total_roots

    # All cuts floor
    all_cuts_floor = compute_all_cuts_floor(include_analysis, DG, target)

    if original_reachable == 0:
        all_cuts_floor_pct = 0.0
    else:
        all_cuts_floor_pct = 100.0 * all_cuts_floor / original_reachable

    all_cuts_floor_prevalence = 100.0 * all_cuts_floor / total_roots

    # Root direct includes floor: count of roots that directly include the target
    roots_set = set(include_analysis["roots"])
    root_direct_includes_floor = sum(
        1 for includer in include_analysis["included_by"].get(target, []) if includer in roots_set
    )

    if original_reachable == 0:
        root_direct_includes_floor_pct = 0.0
    else:
        root_direct_includes_floor_pct = 100.0 * root_direct_includes_floor / original_reachable

    return {
        "all_cuts_floor_pct": all_cuts_floor_pct,
        "all_cuts_floor_prevalence": all_cuts_floor_prevalence,
        "DG": DG,
        "direct_floor_pct": direct_floor_pct,
        "direct_floor_prevalence": direct_floor_prevalence,
        "original_reachable": original_reachable,
        "remaining_pct": remaining_pct,
        "remaining_prevalence": remaining_prevalence,
        "root_direct_includes_floor": root_direct_includes_floor,
        "root_direct_includes_floor_pct": root_direct_includes_floor_pct,
    }


def is_gist_url(path: str) -> bool:
    """Check if a path is a GitHub gist URL."""
    return bool(re.match(r"https?://gist\.github(?:usercontent)?\.com/", path))


def gist_to_raw_url(url: str) -> str:
    """Convert a GitHub gist URL to its raw content URL."""
    # Already a raw gist URL
    if "gist.githubusercontent.com" in url:
        return url
    # Convert https://gist.github.com/{user}/{id} or .../raw etc.
    match = re.match(r"https?://gist\.github\.com/([^/]+)/([a-f0-9]+)(?:/raw)?/?$", url)
    if match:
        return f"https://gist.githubusercontent.com/{match.group(1)}/{match.group(2)}/raw"
    return url


def extract_gist_id(url: str) -> Optional[str]:
    """Extract the gist ID from a GitHub gist URL."""
    match = re.match(r"https?://gist\.github(?:usercontent)?\.com/[^/]+/([a-f0-9]+)", url)
    if match:
        return match.group(1)
    return None


def update_gist_file(gist_url: str, new_content: str, gh_token: str):
    """Update a gist file via the GitHub API."""
    gist_id = extract_gist_id(gist_url)
    if not gist_id:
        raise ValueError(f"Could not extract gist ID from URL: {gist_url}")

    # GET the gist to find the filename
    req = urllib.request.Request(
        f"https://api.github.com/gists/{gist_id}",
        headers={
            "Authorization": f"Bearer {gh_token}",
            "Accept": "application/vnd.github+json",
            "X-GitHub-Api-Version": "2022-11-28",
        },
    )
    with urllib.request.urlopen(req) as response:
        gist_data = json.loads(response.read().decode("utf-8"))

    filename = next(iter(gist_data["files"]))

    # PATCH the gist with updated content
    patch_data = json.dumps(
        {
            "files": {
                filename: {
                    "content": new_content,
                }
            }
        }
    ).encode("utf-8")

    req = urllib.request.Request(
        f"https://api.github.com/gists/{gist_id}",
        data=patch_data,
        headers={
            "Authorization": f"Bearer {gh_token}",
            "Accept": "application/vnd.github+json",
            "X-GitHub-Api-Version": "2022-11-28",
            "Content-Type": "application/json",
        },
        method="PATCH",
    )
    urllib.request.urlopen(req)


def load_edges_from_file(filepath: str) -> Set[Tuple[str, str]]:
    edges: Set[Tuple[str, str]] = set()

    if is_gist_url(filepath):
        raw_url = gist_to_raw_url(filepath)
        response = urllib.request.urlopen(raw_url)
        content = response.read().decode("utf-8")
        reader = csv.reader(io.StringIO(content))
        edges.update(tuple(row) for row in reader if row and row[0].strip() and not row[0].startswith("#"))
    else:
        with open(filepath, "r", newline="") as f:
            edges.update(tuple(row) for row in csv.reader(f) if row and row[0].strip() and not row[0].startswith("#"))

    return edges


class ListHandler(logging.Handler):
    """A logging handler that collects log records into a list."""

    def __init__(self):
        super().__init__()
        self.records: List[logging.LogRecord] = []

    def emit(self, record):
        self.records.append(record)

    def clear(self):
        self.records.clear()


def run_interactive(
    include_analysis,
    target: str,
    ignores_files: List[str],
    removes_files: List[str],
    top_n: int,
    sort_by: str,
    gh_token: Optional[str] = None,
    nested: bool = False,
):
    """Run the interactive curses-based TUI for cut_header."""

    # The first file in each list is the one that gets written to
    ignores_output_file = ignores_files[0]
    removes_output_file = removes_files[0]

    def prepend_to_file(filepath: str, includer: str, included: str):
        """Prepend a CSV row to the given file (local or gist)."""
        new_line = f"{includer},{included}\n"

        if is_gist_url(filepath) and gh_token:
            raw_url = gist_to_raw_url(filepath)
            try:
                response = urllib.request.urlopen(raw_url)
                existing = response.read().decode("utf-8")
            except Exception:
                existing = ""
            update_gist_file(filepath, new_line + existing, gh_token)
        else:
            try:
                with open(filepath, "r") as f:
                    existing = f.read()
            except FileNotFoundError:
                existing = ""

            with open(filepath, "w") as f:
                f.write(new_line + existing)

    def compute_data(include_analysis, target, ignores, removes):
        """Compute floors, direct cuts, and indirect cuts. Returns a dict of all results."""
        total_roots = len(include_analysis["roots"])
        floors = calculate_floors(include_analysis, target, ignores=tuple(ignores), removes=tuple(removes))
        DG = floors["DG"]
        original_reachable = floors["original_reachable"]
        original_prevalence = 100.0 * original_reachable / total_roots

        edge_dominations = compute_doms_to_target(include_analysis, DG, target)

        direct_includers = compute_direct_cuts(include_analysis, DG, target, edge_dominations)
        all_indirect = compute_top_indirect_cuts(include_analysis, DG, target, edge_dominations)

        return {
            "floors": floors,
            "total_roots": total_roots,
            "original_reachable": original_reachable,
            "original_prevalence": original_prevalence,
            "all_direct": direct_includers,
            "all_indirect": all_indirect,
        }

    def strikethrough(text):
        """Apply Unicode strikethrough to text."""
        return "".join(ch + "\u0336" for ch in text)

    def render(stdscr, data, selected_idx, action_mode, action_selected, acted_on, sort_by, top_n):
        """Render the TUI. Returns the total number of selectable lines."""
        stdscr.erase()
        max_y, max_x = stdscr.getmaxyx()

        floors = data["floors"]
        total_roots = data["total_roots"]
        original_prevalence = data["original_prevalence"]

        sort_key = (lambda x: x[3]) if sort_by == "dominated" else (lambda x: x[2])
        top_direct = sorted(data["all_direct"], key=sort_key, reverse=True)[:top_n]
        top_indirect = sorted(data["all_indirect"], key=sort_key, reverse=True)[:top_n]

        remaining_pct = floors["remaining_pct"]
        remaining_prevalence = floors["remaining_prevalence"]
        direct_floor_pct = floors["direct_floor_pct"]
        direct_floor_prevalence = floors["direct_floor_prevalence"]
        all_cuts_floor_pct = floors["all_cuts_floor_pct"]
        all_cuts_floor_prevalence = floors["all_cuts_floor_prevalence"]
        root_direct_includes_floor = floors["root_direct_includes_floor"]
        root_direct_includes_floor_pct = floors["root_direct_includes_floor_pct"]

        remaining_delta = remaining_prevalence - original_prevalence
        direct_floor_delta = direct_floor_prevalence - original_prevalence
        all_cuts_floor_delta = all_cuts_floor_prevalence - original_prevalence
        root_direct_includes_floor_prevalence = 100.0 * root_direct_includes_floor / total_roots
        root_direct_includes_floor_delta = root_direct_includes_floor_prevalence - original_prevalence

        row = 0

        def addstr(y, x, text, attr=0):
            if y < max_y:
                try:
                    stdscr.addnstr(y, x, text, max_x - x - 1, attr)
                except curses.error:
                    pass

        def addstr_line(y, x, includer_file, included_file, prevalence, dominated_edges, base_attr=0):
            """Render a line with color-coded prevalence and dominated edges."""
            edge_text = f"  {includer_file},{included_file},"
            prev_text = f"{prevalence:.2f}"
            comma = ","
            dom_text = f"{dominated_edges}"
            col = x
            addstr(y, col, edge_text, base_attr)
            col += len(edge_text)
            addstr(y, col, prev_text, curses.color_pair(4) | base_attr)
            col += len(prev_text)
            addstr(y, col, comma, base_attr)
            col += len(comma)
            addstr(y, col, dom_text, curses.color_pair(5) | base_attr)

        # Title
        addstr(row, 0, f"Target: {target}", curses.A_BOLD)
        row += 1

        # Floors
        if remaining_delta:
            addstr(
                row,
                0,
                f"Remaining: {remaining_pct:.2f}% ({remaining_prevalence:.2f}% prevalence, {remaining_delta:+.2f}%%)",
            )
        else:
            addstr(row, 0, f"Remaining: {remaining_pct:.2f}% ({remaining_prevalence:.2f}% prevalence)")
        row += 1
        addstr(
            row,
            0,
            f"Only direct cuts floor: {direct_floor_pct:.2f}% ({direct_floor_prevalence:.2f}% prevalence, {direct_floor_delta:+.2f}%%)",
        )
        row += 1
        addstr(
            row,
            0,
            f"All cuts floor: {all_cuts_floor_pct:.2f}% ({all_cuts_floor_prevalence:.2f}% prevalence, {all_cuts_floor_delta:+.2f}%%)",
        )
        row += 1
        addstr(
            row,
            0,
            f"Root direct includes floor: {root_direct_includes_floor_pct:.2f}% ({root_direct_includes_floor_prevalence:.2f}% prevalence, {root_direct_includes_floor_delta:+.2f}%%)",
        )
        row += 1
        row += 1  # blank line

        # Direct includers
        addstr(row, 0, f"Top {top_n} direct includers (by {sort_by})", curses.A_BOLD | curses.A_UNDERLINE)
        row += 1

        selectable_lines = []

        for includer_file, included_file, prevalence, dominated_edges in top_direct:
            is_selected = selected_idx == len(selectable_lines)
            action = acted_on.get((includer_file, included_file))
            selectable_lines.append((includer_file, included_file))

            if action:
                addstr(
                    row,
                    1,
                    f"  {strikethrough(f'{includer_file},{included_file},{prevalence:.2f},{dominated_edges}')}  [{action}]",
                    curses.color_pair(3) | curses.A_DIM,
                )
            elif is_selected:
                addstr(row, 0, "*", curses.color_pair(1) | curses.A_BOLD)
                addstr_line(row, 1, includer_file, included_file, prevalence, dominated_edges, curses.A_BOLD)
            else:
                addstr_line(row, 1, includer_file, included_file, prevalence, dominated_edges)
            row += 1

        if not top_direct:
            addstr(row, 2, "(none available to show)")
            row += 1

        row += 1  # blank line

        # Indirect cuts
        addstr(row, 0, f"Top {top_n} indirect cuts (by {sort_by})", curses.A_BOLD | curses.A_UNDERLINE)
        row += 1

        for includer_file, included_file, prevalence, dominated_edges in top_indirect:
            is_selected = selected_idx == len(selectable_lines)
            action = acted_on.get((includer_file, included_file))
            selectable_lines.append((includer_file, included_file))

            if action:
                addstr(
                    row,
                    1,
                    f"  {strikethrough(f'{includer_file},{included_file},{prevalence:.2f},{dominated_edges}')}  [{action}]",
                    curses.color_pair(3) | curses.A_DIM,
                )
            elif is_selected:
                addstr(row, 0, "*", curses.color_pair(1) | curses.A_BOLD)
                addstr_line(row, 1, includer_file, included_file, prevalence, dominated_edges, curses.A_BOLD)
            else:
                addstr_line(row, 1, includer_file, included_file, prevalence, dominated_edges)
            row += 1

        if not top_indirect:
            addstr(row, 2, "(none available to show)")
            row += 1

        row += 1  # blank line

        # Action mode overlay
        if action_mode and 0 <= selected_idx < len(selectable_lines):
            includer, included = selectable_lines[selected_idx]
            action_row = row
            addstr(action_row, 0, f"Action for: {includer} -> {included}", curses.A_BOLD)
            action_row += 1

            options = [
                ("i", "Ignore", f"prepend to {ignores_output_file}"),
                ("r", "Remove", f"prepend to {removes_output_file}"),
            ]
            for oi, (key, label, desc) in enumerate(options):
                prefix = "> " if action_selected == oi else "  "
                attr = curses.A_BOLD | curses.color_pair(2) if action_selected == oi else 0
                addstr(action_row, 0, f"{prefix}[{key}] {label} ({desc})", attr)
                action_row += 1

            addstr(action_row, 0, "  [Esc] Cancel", curses.A_DIM)
            action_row += 1
            row = action_row
        else:
            # Footer help
            quit_hint = "[b] Back" if nested else "[q] Quit"
            addstr(
                row,
                0,
                f"[↑/↓] Select  [Enter] Action  [c] Copy  [o] Open  [r] Refresh  [s] Sort: {sort_by}  {quit_hint}",
                curses.A_DIM,
            )
            row += 1

        # Warnings
        for warning in data.get("warnings", []):
            row += 1
            addstr(row, 0, warning, curses.color_pair(3) | curses.A_BOLD)

        stdscr.refresh()
        return selectable_lines

    def curses_main(stdscr):
        curses.curs_set(0)  # Hide cursor
        stdscr.keypad(True)

        # Init colors
        curses.start_color()
        curses.use_default_colors()
        curses.init_pair(1, curses.COLOR_GREEN, -1)  # Selected asterisk
        curses.init_pair(2, curses.COLOR_CYAN, -1)  # Action highlight
        curses.init_pair(3, curses.COLOR_RED, -1)  # Crossed out lines
        curses.init_pair(4, curses.COLOR_YELLOW, -1)  # Prevalence
        curses.init_pair(5, curses.COLOR_MAGENTA, -1)  # Dominated edges

        selected_idx = 0
        action_mode = False
        action_selected = 0
        needs_refresh = True
        data = None
        acted_on = {}  # (includer, included) -> "ignored" | "removed"
        any_action_taken = False
        current_sort_by = sort_by

        while True:
            if needs_refresh:
                # Show a loading message
                stdscr.erase()
                stdscr.addstr(0, 0, "Computing... please wait", curses.A_BOLD)
                stdscr.refresh()

                ignores: Set[Tuple[str, str]] = set()
                for f in ignores_files:
                    ignores.update(load_edges_from_file(f))
                removes: Set[Tuple[str, str]] = set()
                for f in removes_files:
                    removes.update(load_edges_from_file(f))

                # Capture all warnings from the logger during computation,
                # silencing them from stderr so they only show in the TUI
                list_handler = ListHandler()
                list_handler.setLevel(logging.WARNING)
                logger = logging.getLogger()
                logger.addHandler(list_handler)
                saved_levels = [(h, h.level) for h in logger.handlers if h is not list_handler]
                for h, _ in saved_levels:
                    h.setLevel(max(h.level, logging.ERROR))
                try:
                    for includer, included in ignores.intersection(removes):
                        logging.warning(
                            f"edge {includer} -> {included} is in both ignores and removes, it will be treated as removed"
                        )
                    data = compute_data(include_analysis, target, ignores, removes)
                finally:
                    for h, level in saved_levels:
                        h.setLevel(level)
                    logger.removeHandler(list_handler)

                data["warnings"] = sorted(set(f"warning: {r.getMessage()}" for r in list_handler.records))[:5]
                stdscr.redrawwin()
                stdscr.refresh()
                needs_refresh = False
                selected_idx = 0
                action_mode = False
                acted_on = {}

            selectable_lines = render(
                stdscr, data, selected_idx, action_mode, action_selected, acted_on, current_sort_by, top_n
            )
            total_selectable = len(selectable_lines)

            key = stdscr.getch()

            if action_mode:
                action_taken = False

                if key == 27:  # Escape
                    action_mode = False
                elif key == curses.KEY_UP:
                    action_selected = max(0, action_selected - 1)
                elif key == curses.KEY_DOWN:
                    action_selected = min(1, action_selected + 1)
                elif key in (curses.KEY_ENTER, 10, 13):
                    includer, included = selectable_lines[selected_idx]
                    if action_selected == 0:  # Ignore
                        prepend_to_file(ignores_output_file, includer, included)
                        acted_on[(includer, included)] = "ignored"
                    else:  # Remove
                        prepend_to_file(removes_output_file, includer, included)
                        acted_on[(includer, included)] = "removed"
                    action_mode = False
                    action_taken = True
                elif key == ord("i"):
                    includer, included = selectable_lines[selected_idx]
                    prepend_to_file(ignores_output_file, includer, included)
                    acted_on[(includer, included)] = "ignored"
                    action_mode = False
                    action_taken = True
                elif key == ord("r"):
                    includer, included = selectable_lines[selected_idx]
                    prepend_to_file(removes_output_file, includer, included)
                    acted_on[(includer, included)] = "removed"
                    action_mode = False
                    action_taken = True

                if action_taken:
                    any_action_taken = True
                    if (total_selectable - len(acted_on)) > 0:
                        while True:
                            selected_idx = (selected_idx + 1) % total_selectable
                            includer, included = selectable_lines[selected_idx]
                            if (includer, included) not in acted_on:
                                break
            else:
                if key == ord("b" if nested else "q"):
                    break
                elif key == ord("r"):
                    needs_refresh = True
                elif key == ord("s"):
                    current_sort_by = "dominated" if current_sort_by == "prevalence" else "prevalence"
                    selected_idx = 0
                elif key == ord("c"):
                    if (total_selectable - len(acted_on)) > 0 and 0 <= selected_idx < total_selectable:
                        includer, included = selectable_lines[selected_idx]
                        copy_to_clipboard(f"{includer},{included}")
                elif key == ord("o"):
                    if (total_selectable - len(acted_on)) > 0 and 0 <= selected_idx < total_selectable:
                        includer, included = selectable_lines[selected_idx]
                        open_url(f"https://source.chromium.org/chromium/chromium/src/+/main:{includer}")
                elif key == curses.KEY_UP:
                    if (total_selectable - len(acted_on)) > 0:
                        while True:
                            selected_idx = (selected_idx - 1) % total_selectable
                            includer, included = selectable_lines[selected_idx]
                            if (includer, included) not in acted_on:
                                break
                elif key == curses.KEY_DOWN:
                    if (total_selectable - len(acted_on)) > 0:
                        while True:
                            selected_idx = (selected_idx + 1) % total_selectable
                            includer, included = selectable_lines[selected_idx]
                            if (includer, included) not in acted_on:
                                break
                elif key in (curses.KEY_ENTER, 10, 13):
                    if (total_selectable - len(acted_on)) > 0 and 0 <= selected_idx < total_selectable:
                        action_mode = True
                        action_selected = 0

        return any_action_taken

    return curses.wrapper(curses_main)


def main():
    parser = argparse.ArgumentParser(description="Output information about potential cuts of a target header.")
    parser.add_argument("target", nargs="?", help="Target header file.")
    parser.add_argument(
        "--include-analysis",
        type=str,
        help="The include analysis output to use (can be a file path or URL). If not specified, pulls the latest.",
    )
    ignores_group = parser.add_mutually_exclusive_group()
    ignores_group.add_argument("--ignores", action="append", default=[], help="Edges to ignore when determining cuts.")
    ignores_group.add_argument("--ignores-file", type=str, help="File containing edges to ignore (one per line).")

    removes_group = parser.add_mutually_exclusive_group()
    removes_group.add_argument("--removes", action="append", default=[], help="Edges to remove when determining cuts.")
    removes_group.add_argument("--removes-file", type=str, help="File containing edges to remove (one per line).")
    parser.add_argument("--verbose", action="store_true", default=False, help="Enable verbose logging.")
    parser.add_argument("--top", type=int, default=5, help="Number of top cuts to display (default: 5).")
    parser.add_argument(
        "--sort-by",
        choices=["prevalence", "dominated"],
        default="prevalence",
        help="Sort results by prevalence (default) or dominated edges count.",
    )
    parser.add_argument("--interactive", action="store_true", default=False, help="Run in interactive mode.")
    args = parser.parse_args()

    if args.ignores_file:
        with open(args.ignores_file) as f:
            args.ignores = [line.strip() for line in f if line.strip()]

    if args.removes_file:
        with open(args.removes_file) as f:
            args.removes = [line.strip() for line in f if line.strip()]

    try:
        include_analysis = load_include_analysis(args.include_analysis)
    except ParseError as e:
        message = str(e)
        print("error: Could not parse include analysis output file")
        if message:
            print(message)
        return 2

    if args.verbose:
        logging.basicConfig(level=logging.DEBUG)

    if args.interactive:
        if len(args.ignores) == 0:
            print("error: interactive mode requires at least one ignores file")
            return 1

        if len(args.removes) == 0:
            print("error: interactive mode requires at least one removes file")
            return 1

        load_dotenv()  # Load environment variables from .env file if present
        gh_token = os.environ.get("GH_TOKEN")

        if is_gist_url(args.ignores[0]) and not gh_token:
            print("error: the first ignores is a gist URL but GH_TOKEN environment variable is not set")
            return 1

        if is_gist_url(args.removes[0]) and not gh_token:
            print("error: the first removes is a gist URL but GH_TOKEN environment variable is not set")
            return 1

    if not args.target:
        import atexit
        import readline
        from pathlib import Path

        history_file = Path(__file__).parent / ".cut_header_history"

        try:
            readline.read_history_file(history_file)
        except FileNotFoundError:
            pass

        readline.set_history_length(100)
        atexit.register(readline.write_history_file, history_file)

        args.target = input("Enter target filename: ").strip()

    if args.target not in include_analysis["files"]:
        print(f"error: {args.target} is not a known file")
        return 1

    if args.interactive:
        # NOTE: the first --ignores and --removes files are the ones updated
        run_interactive(
            include_analysis=include_analysis,
            target=args.target,
            ignores_files=args.ignores,
            removes_files=args.removes,
            top_n=args.top,
            sort_by=args.sort_by,
            gh_token=gh_token,
        )
        return 0

    ignores: Set[Tuple[str, str]] = set()
    removes: Set[Tuple[str, str]] = set()

    for ignores_file in args.ignores:
        ignores.update(load_edges_from_file(ignores_file))

    for removes_file in args.removes:
        removes.update(load_edges_from_file(removes_file))

    for edge in ignores.intersection(removes):
        logging.warning(
            f"warning: edge {edge[0]} -> {edge[1]} is in both ignores and removes, it will be treated as removed"
        )

    total_roots = len(include_analysis["roots"])

    floors = calculate_floors(include_analysis, args.target, ignores=tuple(ignores), removes=tuple(removes))

    all_cuts_floor_pct = floors["all_cuts_floor_pct"]
    all_cuts_floor_prevalence = floors["all_cuts_floor_prevalence"]
    DG = floors["DG"]
    direct_floor_pct = floors["direct_floor_pct"]
    direct_floor_prevalence = floors["direct_floor_prevalence"]
    original_reachable = floors["original_reachable"]
    remaining_pct = floors["remaining_pct"]
    remaining_prevalence = floors["remaining_prevalence"]
    root_direct_includes_floor = floors["root_direct_includes_floor"]
    root_direct_includes_floor_pct = floors["root_direct_includes_floor_pct"]

    root_direct_includes_floor_prevalence = 100.0 * root_direct_includes_floor / total_roots

    original_prevalence = 100.0 * original_reachable / total_roots
    remaining_delta = remaining_prevalence - original_prevalence
    direct_floor_delta = direct_floor_prevalence - original_prevalence
    all_cuts_floor_delta = all_cuts_floor_prevalence - original_prevalence
    root_direct_includes_floor_delta = root_direct_includes_floor_prevalence - original_prevalence

    # Output to stderr
    if remaining_delta:
        print(
            f"Remaining: {remaining_pct:.2f}% ({remaining_prevalence:.2f}% prevalence, {remaining_delta:+.2f}%%)",
            file=sys.stderr,
        )
    else:
        print(f"Remaining: {remaining_pct:.2f}% ({remaining_prevalence:.2f}% prevalence)", file=sys.stderr)
    print(
        f"Only direct cuts floor: {direct_floor_pct:.2f}% ({direct_floor_prevalence:.2f}% prevalence, {direct_floor_delta:+.2f}%%)",
        file=sys.stderr,
    )
    print(
        f"All cuts floor: {all_cuts_floor_pct:.2f}% ({all_cuts_floor_prevalence:.2f}% prevalence, {all_cuts_floor_delta:+.2f}%%)",
        file=sys.stderr,
    )
    print(
        f"Root direct includes floor: {root_direct_includes_floor_pct:.2f}% ({root_direct_includes_floor_prevalence:.2f}% prevalence, {root_direct_includes_floor_delta:+.2f}%%)",
        file=sys.stderr,
    )

    edge_dominations = compute_doms_to_target(include_analysis, DG, args.target)

    # Sort and take top N
    sort_key = (lambda x: x[3]) if args.sort_by == "dominated" else (lambda x: x[2])

    # Compute top N direct cuts
    direct_includers = compute_direct_cuts(include_analysis, DG, args.target, edge_dominations)
    direct_includers.sort(key=sort_key, reverse=True)
    top_direct = direct_includers[: args.top]

    print(f"\nTop {args.top} direct includers (by {args.sort_by})")
    writer = csv.writer(sys.stdout)
    for includer_file, included_file, prevalence, dominated_edges in top_direct:
        writer.writerow([includer_file, included_file, f"{prevalence:.2f}", dominated_edges])

    # Compute top N indirect cuts
    all_indirect = compute_top_indirect_cuts(include_analysis, DG, args.target, edge_dominations)
    all_indirect.sort(key=sort_key, reverse=True)
    top_indirect = all_indirect[: args.top]

    print(f"\nTop {args.top} indirect cuts (by {args.sort_by})")
    for includer_file, included_file, prevalence, dominated_edges in top_indirect:
        writer.writerow([includer_file, included_file, f"{prevalence:.2f}", dominated_edges])

    return 0


if __name__ == "__main__":
    try:
        sys.exit(main())
    except KeyboardInterrupt:
        pass  # Don't show the user anything