import { getReadableText, isUnreadableElement } from "../../../utils/lisio-readable-dom";
import { extractCardSlots } from "./card-slots";
import { BlockFeatures } from "./block-features";
import {
  BlockKind,
  CardSlots,
  DROPPED_KINDS,
  SerializedBlock,
  SerializedBlockTree,
  SINGLETON_KINDS,
  TERMINAL_KINDS,
} from "./block-types";
import {
  ASIDE_RE,
  classifyBlock,
  CONSENT_RE,
  FOOTER_RE,
  HEADER_RE,
  LOGO_RE,
  NAV_RE,
} from "./classify-block";
import { FingerprintNode, findRepeatGroups } from "./fingerprint";
import { detectGallery } from "./gallery-detect";
import { GeometryProvider, NullGeometryProvider } from "./geometry-provider";

const MAX_DEPTH = 12;
const MAX_BLOCKS = 800;
// Runs once, synchronously, before Reading Mode paints — not
// user-perceptible against the page-load time already elapsed. Bumped from
// 250ms: on div-soup pages with a large mega-menu, content-first ordering
// (see isLikelyChrome) means chrome now yields the budget to `main` first,
// but `main` itself can still be large enough that it needs more than
// 250ms to fully segment its own children (cardLists included).
const MAX_MS = 400;
const DROP_CONFIDENCE = 0.7;
const SPLIT_CONFIDENCE = 0.35;
const CARD_GROUP_MIN_MEMBERS = 3;
const CARD_GROUP_MIN_DOMINANCE = 0.6; // group must cover >=60% of the container's split points

interface InternalBlock {
  id: number;
  kind: BlockKind;
  confidence: number;
  el: Element;
  parentId: number | null;
  children: InternalBlock[];
  leaves: number[];
  label?: string;
  headingLevel?: number;
  fingerprint?: string;
  slots?: CardSlots;
  slideGroups?: number[][];
  activeSlide?: number;
  range: [number, number];
}

interface SegmentContext {
  nextId: number;
  allBlocks: InternalBlock[];
  preorderIndex: Map<Element, number>;
  totalElements: number;
  docTextLength: number;
  documentH1?: Element;
  geo: GeometryProvider;
  positionOf: Map<Element, number>;
  deadline: number;
  bailed?: string;
}

function now(): number {
  return typeof performance !== "undefined" ? performance.now() : Date.now();
}

function indexPreorder(root: HTMLElement): Map<Element, number> {
  const map = new Map<Element, number>();
  let i = 0;
  map.set(root, i++);
  const walker = document.createTreeWalker(root, NodeFilter.SHOW_ELEMENT);
  let node = walker.nextNode();
  while (node != undefined) {
    map.set(node as Element, i++);
    node = walker.nextNode();
  }
  return map;
}

function depthFromBody(el: Element, body: Element): number {
  let d = 0;
  let cur: Element | null = el;
  while (cur != undefined && cur !== body && d < 64) {
    cur = cur.parentElement;
    d++;
  }
  return d;
}

function toFingerprintNode(
  el: Element,
  elByNode: Map<FingerprintNode, Element>,
  depth = 3,
  breadth = 6,
): FingerprintNode {
  const kids =
    depth <= 0
      ? []
      : Array.from(el.children)
          .slice(0, breadth)
          .map((c) => toFingerprintNode(c, elByNode, depth - 1, breadth));
  const node: FingerprintNode = {
    localName: el.localName,
    className: typeof el.className === "string" ? el.className : "",
    children: kids,
  };
  elByNode.set(node, el);
  return node;
}

/**
 * Runs the full structural analysis of the current document and returns the
 * wire-format block tree. Total analysis time is capped (`MAX_MS`) and the
 * whole thing is wrapped in a try/catch: on any failure or budget breach,
 * `blocks` comes back empty and the reader falls back to the flat v1
 * rendering unchanged. Segmentation must never be the reason Reading Mode
 * fails to open.
 */
export function segmentPage(
  body: HTMLElement,
  leaves: (HTMLElement | SVGElement)[],
  geo: GeometryProvider = NullGeometryProvider,
): SerializedBlockTree {
  const startedAt = now();
  try {
    return runSegmentation(body, leaves, geo, startedAt);
  } catch (error) {
    console.debug(
      "[reading-mode] structure analysis failed, falling back to flat rendering",
      error,
    );
    return {
      version: 1,
      blocks: [],
      dropped: [],
      stats: { blocks: 0, dropped: 0, ms: Math.round(now() - startedAt), bailed: String(error) },
    };
  } finally {
    // Self-contained cleanup: `data-lisio-block` is transient scratch state,
    // fully consumed into the returned tree by the time we get here (or
    // abandoned on throw/budget bail). Never leave it stamped on the user's
    // live page, regardless of how segmentation ended.
    for (const el of Array.from(body.querySelectorAll<HTMLElement>("[data-lisio-block]"))) {
      delete el.dataset.lisioBlock;
    }
    if (body.dataset.lisioBlock != undefined) delete body.dataset.lisioBlock;
  }
}

function runSegmentation(
  body: HTMLElement,
  leaves: (HTMLElement | SVGElement)[],
  geo: GeometryProvider,
  startedAt: number,
): SerializedBlockTree {
  const textCache = new WeakMap<Element, string>();
  const readableTextOf = (el: Element): string => {
    if (!(el instanceof HTMLElement) && !(el instanceof SVGElement)) return "";
    let cached = textCache.get(el);
    if (cached == undefined) {
      cached = getReadableText(el);
      textCache.set(el, cached);
    }
    return cached;
  };

  const positionOf = new Map<Element, number>();
  leaves.forEach((el, i) => positionOf.set(el, i));

  const preorderIndex = indexPreorder(body);
  const documentH1 = Array.from(document.querySelectorAll<HTMLElement>("h1")).find(
    (el) => !isUnreadableElement(el),
  );

  const ctx: SegmentContext = {
    nextId: 0,
    allBlocks: [],
    preorderIndex,
    totalElements: preorderIndex.size,
    docTextLength: readableTextOf(body).length,
    documentH1,
    geo,
    positionOf,
    deadline: startedAt + MAX_MS,
  };

  function newBlock(kind: BlockKind, confidence: number, el: Element): InternalBlock {
    const block: InternalBlock = {
      id: ctx.nextId++,
      kind,
      confidence,
      el,
      parentId: null,
      children: [],
      leaves: [],
      range: [-1, -1],
    };
    ctx.allBlocks.push(block);
    return block;
  }

  function isSplitCandidate(child: Element): child is HTMLElement {
    if (!(child instanceof HTMLElement)) return false;
    if (isUnreadableElement(child)) return false;
    const hasText = readableTextOf(child).trim() !== "";
    const hasMedia =
      /^(img|svg|video|picture)$/.test(child.localName) ||
      child.querySelector("img, svg, video, picture") != undefined;
    const hasFormControl =
      /^(input|select|textarea|button)$/.test(child.localName) ||
      child.querySelector("input, select, textarea, button") != undefined;
    return hasText || hasMedia || hasFormControl;
  }

  function splitPoints(el: Element): HTMLElement[] {
    const out = Array.from(el.children).filter(isSplitCandidate);
    if (out.length === 1) {
      const only = out[0];
      const elLen = readableTextOf(el).length;
      const onlyLen = readableTextOf(only).length;
      if (elLen > 0 && onlyLen >= elLen * 0.95) {
        return splitPoints(only);
      }
    }
    return out;
  }

  function collectStructuralStats(el: Element) {
    const stats = {
      linkTextLength: 0,
      linkCount: 0,
      shortLinkCount: 0,
      pCount: 0,
      headingCount: 0,
      minHeadingLevel: 7,
      listItemCount: 0,
      imageCount: 0,
      formControlCount: 0,
      buttonCount: 0,
      containsLogoImage: false,
    };
    const stack: Element[] = [el];
    while (stack.length > 0) {
      const node = stack.pop() as Element;
      if (
        node !== el &&
        (node instanceof HTMLElement || node instanceof SVGElement) &&
        isUnreadableElement(node)
      ) {
        continue;
      }
      const tag = node.localName;
      if (tag === "p") stats.pCount++;
      const hMatch = /^h([1-6])$/.exec(tag);
      if (hMatch) {
        stats.headingCount++;
        stats.minHeadingLevel = Math.min(stats.minHeadingLevel, Number(hMatch[1]));
      }
      if (tag === "li") stats.listItemCount++;
      if (tag === "img" || tag === "svg" || tag === "picture") stats.imageCount++;
      if (tag === "input" || tag === "select" || tag === "textarea") stats.formControlCount++;
      if (tag === "button") stats.buttonCount++;
      if (
        (tag === "img" || tag === "svg") &&
        LOGO_RE.test(
          `${node.getAttribute("alt") || ""} ${node.getAttribute("src") || ""} ${
            typeof node.className === "string" ? node.className : ""
          }`,
        )
      ) {
        stats.containsLogoImage = true;
      }
      if (tag === "a") {
        stats.linkCount++;
        const text = readableTextOf(node).trim();
        stats.linkTextLength += text.length;
        const words = text.split(/\s+/).filter(Boolean).length;
        if (words > 0 && words <= 4) stats.shortLinkCount++;
      }
      for (const child of Array.from(node.children)) stack.push(child);
    }
    return stats;
  }

  function extractFeatures(el: HTMLElement, childBlockCount: number): BlockFeatures {
    const idClass = `${el.id} ${typeof el.className === "string" ? el.className : ""}`
      .trim()
      .toLowerCase();
    const ariaLabel = (el.getAttribute("aria-label") || "").toLowerCase();
    const role = (el.getAttribute("role") || "").toLowerCase();
    const stats = collectStructuralStats(el);
    const text = readableTextOf(el);
    const textLength = text.length;
    const trimmed = text.trim();
    const wordCount = trimmed === "" ? 0 : trimmed.split(/\s+/).length;
    const commaCount = (text.match(/,/g) || []).length;
    const linkDensity = textLength > 0 ? Math.min(1, stats.linkTextLength / textLength) : 0;
    const shortLinkRatio = stats.linkCount > 0 ? stats.shortLinkCount / stats.linkCount : 0;
    const preorderPos = ctx.preorderIndex.get(el) ?? 0;
    const domOrderRatio = ctx.totalElements > 0 ? preorderPos / ctx.totalElements : 0;
    const docTextShare = ctx.docTextLength > 0 ? textLength / ctx.docTextLength : 0;
    const textDensity = wordCount / Math.max(1, stats.pCount + childBlockCount);

    return {
      tagName: el.localName,
      role,
      idClass,
      ariaLabel,
      depth: depthFromBody(el, body),
      domOrderRatio,
      textLength,
      wordCount,
      commaCount,
      linkTextLength: stats.linkTextLength,
      linkDensity,
      linkCount: stats.linkCount,
      shortLinkRatio,
      pCount: stats.pCount,
      headingCount: stats.headingCount,
      minHeadingLevel: stats.minHeadingLevel,
      listItemCount: stats.listItemCount,
      imageCount: stats.imageCount,
      formControlCount: stats.formControlCount,
      buttonCount: stats.buttonCount,
      childElementCount: el.children.length,
      childBlockCount,
      leafCount: 0,
      minPosition: -1,
      maxPosition: -1,
      textDensity,
      docTextShare,
      siblingRepeatCount: 0,
      siblingSimilarity: 0,
      // Calendar detection is owned by ExploreCalendarHelper, which only
      // runs AFTER segmentation (see lisio-reader-adapter.ts). Coordinating
      // the two is deferred to stage 2; `calendar` is not scored by
      // classifyBlock in the meantime.
      containsCalendarLeaf: false,
      containsDocumentH1: ctx.documentH1 != undefined && el.contains(ctx.documentH1),
      containsLogoImage: stats.containsLogoImage,
      containsNavChild: el.querySelector('nav, [role="navigation"]') != undefined,
      geometry: ctx.geo.measure(el),
    };
  }

  function detectCardGroup(
    points: HTMLElement[],
  ): { members: HTMLElement[]; fingerprint: string; similarity: number } | undefined {
    if (points.length < CARD_GROUP_MIN_MEMBERS) return undefined;
    const elByNode = new Map<FingerprintNode, Element>();
    const nodes = points.map((el) => toFingerprintNode(el, elByNode));
    const groups = findRepeatGroups(nodes, {
      textLengthOf: (n) => {
        const el = elByNode.get(n);
        return el ? readableTextOf(el).length : 0;
      },
      wordCountOf: (n) => {
        const el = elByNode.get(n);
        if (el == undefined) return 0;
        const t = readableTextOf(el).trim();
        return t === "" ? 0 : t.split(/\s+/).length;
      },
      linkDensityOf: (n) => {
        const el = elByNode.get(n);
        if (el == undefined) return 0;
        const text = readableTextOf(el);
        if (text.length === 0) return 0;
        const linkText = Array.from(el.querySelectorAll("a"))
          .map((a) => readableTextOf(a))
          .join("");
        return linkText.length / text.length;
      },
    });
    const best = groups[0];
    if (best == undefined) return undefined;
    if (best.members.length < CARD_GROUP_MIN_MEMBERS) return undefined;
    if (best.members.length / points.length < CARD_GROUP_MIN_DOMINANCE) return undefined;
    const members = best.members
      .map((n) => elByNode.get(n))
      .filter((e): e is HTMLElement => e instanceof HTMLElement);
    if (members.length < CARD_GROUP_MIN_MEMBERS) return undefined;
    return { members, fingerprint: best.fingerprint, similarity: best.similarity };
  }

  function extractLabel(el: Element): string | undefined {
    const ariaLabel = el.getAttribute("aria-label");
    if (ariaLabel != undefined && ariaLabel.trim() !== "") return ariaLabel.trim();
    const heading = el.querySelector("h1,h2,h3,h4,h5,h6");
    if (heading != undefined) {
      const text = readableTextOf(heading).trim();
      if (text !== "") return text;
    }
    return undefined;
  }

  /**
   * Cheap (tag name + id/class regex only — no subtree walk, no layout
   * read) guess at "this is chrome, not content". Used ONLY to order a
   * level's split points so the expensive per-point work below (full
   * subtree text/stat scan in extractFeatures, forced-layout geometry
   * reads) hits likely main-content candidates before likely nav/header/
   * footer/aside ones. Real classification still runs on every point
   * regardless of this guess — it only affects order.
   *
   * Why this matters: a big mega-menu `<nav>` can fan out into hundreds of
   * split points, each expensive to feature-extract, easily consuming the
   * whole MAX_MS budget by itself. Without reordering, a `<nav>` sibling
   * that happens to come before `<main>` in DOM order starves `main` of
   * its own turn entirely — segmentation bails before ever looking at
   * main's children, so nothing inside it (cardLists included) gets
   * analysed. Processing likely-chrome candidates last means a budget
   * bail costs precision on collapsed chrome, never on the content the
   * feature exists for.
   */
  function isLikelyChrome(el: Element): boolean {
    const tag = el.localName;
    if (tag === "nav" || tag === "header" || tag === "footer" || tag === "aside") return true;
    const idClass = `${el.id} ${typeof el.className === "string" ? el.className : ""}`
      .toLowerCase()
      .replace(/[-_]/g, " ");
    return (
      NAV_RE.test(idClass) ||
      HEADER_RE.test(idClass) ||
      FOOTER_RE.test(idClass) ||
      ASIDE_RE.test(idClass) ||
      CONSENT_RE.test(idClass)
    );
  }

  function descend(el: Element, currentBlock: InternalBlock, depth: number): void {
    if (depth >= MAX_DEPTH || ctx.nextId >= MAX_BLOCKS) return;
    if (now() > ctx.deadline) {
      ctx.bailed = "budget";
      return;
    }

    const points = splitPoints(el);
    if (points.length === 0) return;

    if (!["nav", "toolbar", "pagination"].includes(currentBlock.kind)) {
      // Carousel check runs first: a slider has the exact same "repeated
      // similar children" shape a cardList looks for, but a fundamentally
      // different intent (one slide visible at a time, not a list to
      // scan) — it must win the ambiguity outright, never be scored
      // against cardList's rules.
      const gallery = detectGallery(el, points, ctx.geo, (e) => ctx.positionOf.get(e));
      if (gallery != undefined) {
        const galleryBlock = newBlock("gallery", 0.85, el);
        galleryBlock.label = extractLabel(el);
        galleryBlock.slideGroups = gallery.slideGroups;
        galleryBlock.activeSlide = gallery.activeIndex;
        (el as HTMLElement).dataset.lisioBlock = String(galleryBlock.id);
        galleryBlock.parentId = currentBlock.id;
        currentBlock.children.push(galleryBlock);
        return;
      }

      const group = detectCardGroup(points);
      if (group != undefined) {
        const listBlock = newBlock("cardList", 0.8, el);
        listBlock.fingerprint = group.fingerprint;
        listBlock.label = extractLabel(el);
        (el as HTMLElement).dataset.lisioBlock = String(listBlock.id);
        listBlock.parentId = currentBlock.id;
        currentBlock.children.push(listBlock);
        for (const member of group.members) {
          const cardBlock = newBlock("card", 1, member);
          cardBlock.parentId = listBlock.id;
          member.dataset.lisioBlock = String(cardBlock.id);
          cardBlock.slots = extractCardSlots(member, (e) => ctx.positionOf.get(e), ctx.geo);
          listBlock.children.push(cardBlock);
        }
        return;
      }
    }

    // Stable sort: content-shaped candidates keep their relative DOM order
    // and go first; nav/header/footer/aside-shaped ones are deferred to the
    // end of this level (see isLikelyChrome's docstring).
    const orderedPoints = [...points].sort(
      (a, b) => Number(isLikelyChrome(a)) - Number(isLikelyChrome(b)),
    );

    for (const c of orderedPoints) {
      if (ctx.nextId >= MAX_BLOCKS) return;
      if (now() > ctx.deadline) {
        ctx.bailed = "budget";
        return;
      }
      const f = extractFeatures(c, points.length);
      const r = classifyBlock(f);

      if (DROPPED_KINDS.has(r.kind) && r.confidence >= DROP_CONFIDENCE) {
        c.dataset.lisioBlock = "-1";
        continue;
      }
      if (r.kind === "contentGroup" && r.confidence < SPLIT_CONFIDENCE) {
        // Not worth a wrapper — keep descending under the SAME block.
        descend(c, currentBlock, depth + 1);
        continue;
      }

      if (r.kind === "nav" && currentBlock.kind === "nav") {
        // Sites whose BEM naming repeats "menu"/"nav" at every wrapper
        // level (e.g. `.menu > .menu__wrapper > .menu__wrapper__pages`)
        // would otherwise re-trigger the nav rule at each level, nesting
        // nav blocks inside nav blocks. renderNav() only renders a block's
        // OWN direct leaves (see reader-view/renderers/chrome.ts) — it
        // never descends into children — so anything bucketed into a
        // nested nav child would silently never reach the reader. Flatten
        // instead: keep descending under the SAME outer nav block so all
        // the links end up as its direct leaves.
        descend(c, currentBlock, depth + 1);
        continue;
      }

      const b = newBlock(r.kind, r.confidence, c);
      b.label = extractLabel(c);
      b.parentId = currentBlock.id;
      c.dataset.lisioBlock = String(b.id);
      currentBlock.children.push(b);

      if (!TERMINAL_KINDS.has(r.kind)) {
        descend(c, b, depth + 1);
      }
    }
  }

  function enforceUniqueness(): void {
    for (const kind of SINGLETON_KINDS) {
      const matches = ctx.allBlocks.filter((b) => b.kind === kind);
      if (matches.length <= 1) continue;
      matches.sort((a, b) => b.confidence - a.confidence);
      for (const loser of matches.slice(1)) loser.kind = "section";
    }
  }

  function assignLeaves(root: InternalBlock, dropped: Set<number>): void {
    const byId = new Map<number, InternalBlock>();
    for (const b of ctx.allBlocks) byId.set(b.id, b);
    leaves.forEach((el, position) => {
      const host = el.closest<HTMLElement>("[data-lisio-block]");
      if (host == undefined) {
        root.leaves.push(position);
        return;
      }
      const idAttr = host.dataset.lisioBlock;
      if (idAttr === "-1") {
        dropped.add(position);
        return;
      }
      const block = idAttr != undefined ? byId.get(Number(idAttr)) : undefined;
      if (block != undefined) block.leaves.push(position);
      else root.leaves.push(position);
    });
    for (const b of ctx.allBlocks) b.leaves.sort((a, b2) => a - b2);
    root.leaves.sort((a, b) => a - b);
  }

  function isEmpty(block: InternalBlock): boolean {
    if (block.leaves.length > 0) return false;
    return block.children.every(isEmpty);
  }

  function pruneEmpty(block: InternalBlock): void {
    block.children = block.children.filter((c) => {
      pruneEmpty(c);
      return !isEmpty(c);
    });
  }

  function computeRanges(block: InternalBlock): [number, number] {
    let min = Number.POSITIVE_INFINITY;
    let max = Number.NEGATIVE_INFINITY;
    for (const pos of block.leaves) {
      if (pos < min) min = pos;
      if (pos > max) max = pos;
    }
    for (const child of block.children) {
      const [cMin, cMax] = computeRanges(child);
      if (cMin < min) min = cMin;
      if (cMax > max) max = cMax;
    }
    block.range = min === Number.POSITIVE_INFINITY ? [-1, -1] : [min, max];
    return block.range;
  }

  /**
   * Unlike a typical tree serialisation, the synthetic root block IS
   * included in the output (kind "root", p: null) rather than skipped —
   * its own direct `leaves` are exactly the positions no other block
   * claimed (see assignLeaves: `body` always carries the id=0 sentinel, so
   * `closest()` resolves to root for anything not wrapped by a real
   * block). Dropping those from the wire format would silently lose
   * whatever fraction of the page the classifier left unclassified —
   * often a large fraction on div-soup pages. The reader treats "root" as
   * a transparent container too, so this changes nothing for callers that
   * only care about `blocks` being non-empty.
   */
  function flatten(root: InternalBlock): SerializedBlock[] {
    const out: SerializedBlock[] = [];
    function visit(block: InternalBlock) {
      const serialized: SerializedBlock = {
        i: block.id,
        p: block.parentId,
        k: block.kind,
        c: Math.round(block.confidence * 100) / 100,
        l: block.leaves,
        r: block.range,
      };
      if (block.label != undefined) serialized.n = block.label;
      if (block.headingLevel != undefined) serialized.h = block.headingLevel;
      if (block.fingerprint != undefined) serialized.f = block.fingerprint;
      if (block.slots != undefined) serialized.s = block.slots;
      if (block.slideGroups != undefined) serialized.gs = block.slideGroups;
      if (block.activeSlide != undefined) serialized.ga = block.activeSlide;
      out.push(serialized);
      for (const child of block.children) visit(child);
    }
    visit(root);
    return out;
  }

  const root = newBlock("root", 1, body);
  body.dataset.lisioBlock = "0";
  descend(body, root, 0);
  enforceUniqueness();

  const dropped = new Set<number>();
  assignLeaves(root, dropped);
  pruneEmpty(root);
  computeRanges(root);

  const blocks = flatten(root);
  return {
    version: 1,
    blocks,
    dropped: Array.from(dropped).sort((a, b) => a - b),
    stats: {
      blocks: blocks.length,
      dropped: dropped.size,
      ms: Math.round(now() - startedAt),
      ...(ctx.bailed != undefined ? { bailed: ctx.bailed } : {}),
    },
  };
}
