// ppr-cascade.ts — v1.23.0 Graph Engine hybrid cascade
//
// Pure function. Per #198 / 2026-06-24 Q3 consensus (cold-start
// cascade), the query-time retrieval uses a 3-arm cascade that picks
// the right retrieval strategy based on graph maturity:
//
//   1. lex — when graph is below threshold or seed is isolated.
//   2. lex-seeded-ppr — when graph has neighbors but is below the
//      graph-first density threshold.
//   3. graph-first-ppr — when graph is mature (edges/nodes >= threshold
//      AND largest weak component > 50% of nodes).
//
// Each arm is annotated in the returned PageMatch.arm field, so the
// UI can show the user "Powered by graph-first PPR" or "Lex fallback
// (graph too sparse)" — making the cascade transparent.
//
// The cascade is a pure function. The graph is passed in by the caller
// (query-engine caches the graph and rebuilds it on ingest). This
// keeps the cascade testable without an Obsidian dependency.

import { personalizedPageRank, type Graph, type PPROptions } from './monte-carlo-ppr';

export type { Graph, PPROptions };

export interface PageRef {
  path: string;
  title: string;
  aliases: string[];
  /**
   * Optional text representation of the page — typically the summary
   * line from the wiki index. When provided, lexMatch uses this in
   * addition to title/aliases. The full text makes matching robust
   * across languages (e.g. CJK queries about English-topic pages still
   * match because the summary mentions the topic).
   */
  summary?: string;
}

/**
 * v1.24.1 PATCH Phase 5.5.0: render a PageRef as a compact markdown
 * line (`path — title | aliases: ...`) for LLM candidate lists and the
 * chat-prompt page-summary hint. Shared so the Stage 1.5 seed-selector
 * prompt and the Phase 5.5.0 pageSummaryHint emit an identical format
 * (one formatter, no drift). Pure function.
 */
export function formatPageRefSummary(p: PageRef): string {
  const aliasPart = p.aliases.length > 0
    ? ` | aliases: ${p.aliases.join(' / ')}`
    : '';
  return `- ${p.path} — ${p.title}${aliasPart}`;
}

/**
 * Score pages by per-needle overlap against title + aliases. Shared
 * primitive behind both Stage 1 (lex, needles = tokenized query) and
 * Stage 1.5b (LLM-generated keywords). Needles are expected
 * lowercased; each page's title + aliases are lowercased internally.
 *
 * Scoring per needle:
 *   - title hit: 3
 *   - alias hit: 2
 *
 * Returns pages with score > 0, sorted by score descending, with the
 * count of needles matched (`tokensFound`) so callers can apply a
 * multi-needle bonus. Pure function — no IO.
 */
export function scorePagesByNeedles(
  pages: PageRef[],
  needles: string[],
): Array<{ page: PageRef; score: number; tokensFound: number }> {
  const scored: Array<{ page: PageRef; score: number; tokensFound: number }> = [];
  for (const page of pages) {
    const titleLower = page.title.toLowerCase();
    const aliasLowers = page.aliases.map(a => a.toLowerCase());

    let score = 0;
    let tokensFound = 0;
    for (const kw of needles) {
      if (kw.length === 0) continue;
      if (titleLower.includes(kw)) {
        score += 3;
        tokensFound++;
      } else if (aliasLowers.some(a => a.includes(kw))) {
        score += 2;
        tokensFound++;
      }
    }
    if (score > 0) {
      scored.push({ page, score, tokensFound });
    }
  }
  scored.sort((a, b) => b.score - a.score);
  return scored;
}

/**
 * v1.24.1 PATCH Phase 5.5.0: lex match against TITLE + ALIASES only
 * (no summary). Powers the Stage 1 of the 4-stage seed-selection
 * pipeline.
 *
 * Why no summary: user vault pages frequently lack summary frontmatter
 * (e.g. entities/Janus.md has no `summary:` field but rich aliases).
 * Using summary in Stage 1 would silently drop many pages from
 * consideration — including the page the user just searched for.
 * Aliases carry the curated "what is this page" signal — stable,
 * short, and explicitly written.
 *
 * Scoring (per token, first matching location wins):
 *   - title hit: 3
 *   - alias hit: 2
 *
 * Multi-token bonus: when ALL tokens are found somewhere in the
 * page's title+aliases, +2 (strong relevance signal).
 *
 * Returns scored+ranked pages sorted by score descending. Pages
 * with zero overlap are NOT included. Pure function — no IO.
 */
export function lexMatchByTitleAndAliases(
  query: string,
  pages: PageRef[],
): Array<{ page: PageRef; score: number; arm: 'lex' }> {
  const tokens = tokenizeQuery(query);
  if (tokens.length === 0) return [];

  return scorePagesByNeedles(pages, tokens).map(s => {
    let score = s.score;
    if (s.tokensFound === tokens.length && tokens.length > 1) {
      score += 2;
    }
    return { page: s.page, score, arm: 'lex' as const };
  });
}

export interface PageMatch {
  page: PageRef;
  score: number;
  arm: 'lex' | 'lex-seeded-ppr' | 'graph-first-ppr';
}

export interface PPRCascadeOptions {
  graph?: Graph;
  minPages?: number;
  minEdges?: number;
  minEdgeDensity?: number;
  seedMinDegree?: number;
  topN?: number;
  pprOptions?: PPROptions;
  /**
   * Explicit seed list (typically from LLM semantic selection).
   * When provided AND non-empty, these seeds drive PPR walks instead of
   * the implicit lex top-3. Validated against graph.nodes; invalid seeds
   * (not in graph) are silently dropped.
   */
  seeds?: string[];
  /** Optional RNG (mulberry32 helper) for deterministic PPR sampling. */
  rng?: () => number;
}

const DEFAULT_MIN_PAGES = 30;
const DEFAULT_MIN_EDGES = 30;
const DEFAULT_MIN_EDGE_DENSITY = 1.0;
const DEFAULT_SEED_MIN_DEGREE = 1;
const DEFAULT_TOP_N = 10;

/**
 * Tokenize a query into individual searchable terms. Language-aware:
 *
 * - ASCII runs of length ≥ 2 are extracted (handles mixed-language queries
 *   like "什么是Obsidian？" → "obsidian")
 * - Whitespace-split tokens (length ≥ 2) are kept
 * - **CJK runs of length ≥ 2** are extracted (handles "深度学习" → "深度学习")
 * - Single-character tokens (ASCII or CJK) are NOT extracted — they are
 *   noise that produces spurious matches (e.g. "深" hits any page with
 *   "深" anywhere). Per first-principles (2026-07-13 user direction):
 *   text segmentation should be by meaningful run, not by character.
 *
 * All tokens are lowercased and de-duplicated.
 */
export function tokenizeQuery(query: string): string[] {
  if (!query) return [];
  const tokens = new Set<string>();
  const queryLower = query.toLowerCase();

  // ASCII runs of length ≥ 2.
  const asciiRuns = queryLower.match(/[a-z0-9]{2,}/g);
  if (asciiRuns) for (const r of asciiRuns) tokens.add(r);

  // Whitespace-split tokens of length ≥ 2 (catches words with CJK
  // mixed in: "InterVL和Janus" → "intervl和janus", "和" rejected by length).
  for (const t of queryLower.split(/\s+/)) {
    if (t.length >= 2) tokens.add(t);
  }

  // CJK Unified Ideographs (Chinese, Japanese Kanji) + Hiragana +
  // Katakana (Japanese) + Hangul Syllables / Jamo (Korean) +
  // CJK Ext A (rare Chinese). Extract CONTINUOUS runs of length ≥ 2
  // (single CJK characters are noise: they match too widely and
  // dilute lex precision — the substring "深" hits "深度", "深思",
  // "深色" etc. with equal weight, all spurious).
  const cjkRun = query.match(
    /[一-鿿぀-ゟ゠-ヿ가-힯ퟀ-퟿㐀-䶿]{2,}/g,
  );
  if (cjkRun) for (const r of cjkRun) tokens.add(r.toLowerCase());

  return [...tokens];
}

/**
 * v1.24.1 PATCH Phase 5.5.0: decide whether lex scoring is statistically
 * reliable for a given tokenized query.
 *
 * Per user direction (2026-07-13): avoid hardcoded CJK regex
 * detection. The fundamental signal is the distribution of token
 * LENGTHS in the tokenized query, not the character ranges
 * themselves.
 *
 * Lex scoring is reliable when:
 *   1. At least 2 tokens are multi-character (≥ 2 chars). A single
 *      multi-char token can only substring-match page titles with no
 *      way to break ties — the score collapses to "matched / not
 *      matched" with no granularity.
 *   2. AND most tokens are multi-character (≥ 50%). A query that
 *      tokenizes to 1 multi-char + 10 single-char tokens (typical
 *      for CJK-heavy queries with embedded Latin keywords) is
 *      dominated by low-discrimination single-char matches.
 *
 * Both conditions together — count AND proportion — give a robust
 * "is this lex-query worth trusting?" signal without enumerating
 * any character range.
 *
 * Examples:
 *   "DeepSeek DSA HCA" → 3 multi-char tokens (100%) → reliable
 *   "DSA" → 1 multi-char token → unreliable (single signal)
 *   "为我梳理DeepSeek的DSA和HCA" → 4 multi-char / 21 total (19%) → unreliable
 *   "你好世界" → 1 multi-char / 5 total (20%) → unreliable
 *   "???!!" → 1 multi-char token → unreliable
 *
 * Pure function. No IO. Use after tokenizeQuery.
 */
export function lexIsReliable(tokens: string[]): boolean {
  if (tokens.length === 0) return false;
  let multiCharCount = 0;
  for (const t of tokens) {
    if (t.length >= 2) multiCharCount++;
  }
  // Need BOTH at least 2 multi-char tokens AND ≥ 50% multi-char ratio.
  return multiCharCount >= 2 && multiCharCount / tokens.length >= 0.5;
}

/**
 * Lex-only match: scores pages by per-token keyword overlap against the
 * page's full text representation (title + aliases + optional summary).
 *
 * Robust across languages because:
 * - The summary provides context the LLM also uses
 * - tokenizeQuery extracts ASCII runs from mixed-language queries
 *
 * Scoring per query token (first matching location wins):
 * - title match: 3
 * - alias match: 2
 * - summary match: 1
 *
 * Page-level bonus:
 * - all query tokens found in page text: +2 (strong relevance signal)
 */
function lexMatch(query: string, pages: PageRef[]): PageRef[] {
  const tokens = tokenizeQuery(query);
  if (tokens.length === 0) return [];
  const scored: { page: PageRef; score: number }[] = [];
  for (const page of pages) {
    const titleLower = page.title.toLowerCase();
    const aliasLowers = page.aliases.map(a => a.toLowerCase());
    const summaryLower = (page.summary ?? '').toLowerCase();

    let score = 0;
    let tokensFound = 0;
    for (const kw of tokens) {
      if (titleLower.includes(kw)) { score += 3; tokensFound++; }
      else if (aliasLowers.some(a => a.includes(kw))) { score += 2; tokensFound++; }
      else if (summaryLower.includes(kw)) { score += 1; tokensFound++; }
    }
    if (tokensFound === tokens.length && tokens.length > 1) score += 2;
    if (score > 0) scored.push({ page, score });
  }
  return scored.sort((a, b) => b.score - a.score).map(s => s.page);
}

/**
 * Quick graph-maturity probe: returns true if the graph qualifies for
 * the graph-first PPR arm (per @GioiaZheng's consensus thresholds).
 */
function isGraphMature(graph: Graph, options: PPRCascadeOptions): boolean {
  const minPages = options.minPages ?? DEFAULT_MIN_PAGES;
  const minEdges = options.minEdges ?? DEFAULT_MIN_EDGES;
  const minEdgeDensity = options.minEdgeDensity ?? DEFAULT_MIN_EDGE_DENSITY;
  if (graph.nodes.length < minPages) return false;
  // Count edges (sum of out-degrees).
  let edgeCount = 0;
  for (const targets of graph.edges.values()) edgeCount += targets.length;
  if (edgeCount < minEdges) return false;
  // Edge density: edges/nodes ratio.
  if (edgeCount / graph.nodes.length < minEdgeDensity) return false;
  // Largest weak component: BFS from any node, count reachable.
  // (We do a single BFS from the first node; if it reaches > 50%
  // of nodes, the graph is connected-enough.)
  if (graph.nodes.length === 0) return false;
  const firstNode = graph.nodes[0];
  const visited = new Set<string>([firstNode]);
  const queue: string[] = [firstNode];
  while (queue.length > 0) {
    const node = queue.shift()!;
    for (const next of graph.edges.get(node) ?? []) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next);
      }
    }
    // Reverse edges: also follow incoming edges (treat as undirected
    // for connectivity).
    for (const [from, targets] of graph.edges) {
      if (targets.includes(node) && !visited.has(from)) {
        visited.add(from);
        queue.push(from);
      }
    }
  }
  return visited.size / graph.nodes.length > 0.5;
}

/**
 * Build a path → PPR score map by running PPR for each seed and
 * merging (max score per node).
 */
function pprFromSeeds(
  graph: Graph,
  seeds: string[],
  pprOptions: PPROptions | undefined,
  rng: (() => number) | undefined,
): Map<string, number> {
  const merged = new Map<string, number>();
  for (const seed of seeds) {
    if (!graph.nodes.includes(seed)) continue;
    const result = personalizedPageRank(graph, seed, { ...(pprOptions ?? {}), ...(rng ? { rng } : {}) });
    for (const [node, score] of result) {
      const existing = merged.get(node) ?? 0;
      if (score > existing) merged.set(node, score);
    }
  }
  return merged;
}

/**
 * Filter user-provided seeds to those present in the graph. Returns an
 * empty array if no valid seeds (caller should fall back to other arms).
 */
function filterSeedsToGraph(seeds: string[], graph: Graph): string[] {
  const nodeSet = new Set(graph.nodes);
  return seeds.filter(s => nodeSet.has(s));
}

export function pprCascade(
  query: string,
  pages: PageRef[],
  options: PPRCascadeOptions = {},
): PageMatch[] {
  const topN = options.topN ?? DEFAULT_TOP_N;
  const lex = lexMatch(query, pages);
  const graph = options.graph;
  // Explicit seeds (from LLM) take precedence over implicit lex seeds.
  // Filter to graph nodes upfront — invalid seeds silently dropped.
  const explicitSeeds = options.seeds && graph
    ? filterSeedsToGraph(options.seeds, graph)
    : [];

  // v1.23.0 P2: When there's no graph yet (first query) but LLM provided
  // explicit seeds, those seeds should be returned directly as lex matches
  // rather than silently dropped. The seeds arrived via LLM semantic selection
  // which is a stronger signal than empty lex.
  if (!graph && explicitSeeds.length === 0 && options.seeds && options.seeds.length > 0) {
    const fallbackMatches: { page: PageRef; score: number; arm: 'lex' }[] = [];
    const seedPaths = new Set(options.seeds);
    for (const page of pages) {
      if (seedPaths.has(page.path)) {
        fallbackMatches.push({ page, score: 2, arm: 'lex' });
      }
    }
    if (fallbackMatches.length > 0) {
      return fallbackMatches;
    }
  }

  // Arm 1: pure lex if no graph or graph not mature.
  if (!graph || !isGraphMature(graph, options)) {
    // For the sparse arm, prefer explicit seeds if provided and they
    // have graph neighbors; otherwise fall back to lex-derived seeds.
    if (graph && explicitSeeds.length > 0) {
      const seedMinDegree = options.seedMinDegree ?? DEFAULT_SEED_MIN_DEGREE;
      const validSeeds = explicitSeeds.filter(s => (graph.edges.get(s)?.length ?? 0) >= seedMinDegree);
      if (validSeeds.length > 0) {
        const pprScores = pprFromSeeds(graph, validSeeds, options.pprOptions, options.rng);
        return mergeWithPPR(lex, pprScores, pages, topN, 'lex-seeded-ppr');
      }
    }
    if (graph && lex.length > 0) {
      const seedMinDegree = options.seedMinDegree ?? DEFAULT_SEED_MIN_DEGREE;
      const seedPaths = lex.slice(0, 3).map(p => p.path);
      const validSeeds = seedPaths.filter(s => (graph.edges.get(s)?.length ?? 0) >= seedMinDegree);
      if (validSeeds.length > 0) {
        const pprScores = pprFromSeeds(graph, validSeeds, options.pprOptions, options.rng);
        return mergeWithPPR(lex, pprScores, pages, topN, 'lex-seeded-ppr');
      }
    }
    // No usable graph seeds AND no lex matches → return what lex has,
    // or empty. (Degree-rank fallback removed: the LLM seeds path in
    // buildWikiContext now handles this case upstream.)
    return lex.slice(0, topN).map(page => ({ page, score: lexScoreOf(page, lex), arm: 'lex' }));
  }

  // Arm 3: graph-expanded PPR. PPR's value is graph-based recall
  // expansion — given query-relevant seeds, walk the graph to find
  // graph-adjacent pages.
  //
  // v1.24.1 PATCH Phase 5.5.0 user direction (2026-07-13): PPR from
  // an ARBITRARY seed (e.g. `pages[0]`) is query-irrelevant noise — a
  // random walk from "the wiki index's first page" produces graph-
  // neighbors of that page, not pages related to the query. The
  // pre-fix code did exactly that and surfaced "concepts/自我修正算法"
  // for a "DeepSeek DSA HCA" query.
  //
  // New rule: PPR only fires when there are QUERY-RELEVANT seeds:
  //   1. explicitSeeds (LLM-provided) — strongest signal.
  //   2. lex hits — top of the keyword-matched pages, since these
  //      are query-relevant by construction. PPR amplifies recall
  //      from lex-discovered seeds (this is what PPR is for).
  //   3. No lex hits AND no explicit seeds → return empty (caller
  //      should escalate to LLM seed selector). Running PPR with
  //      no query-relevant seed is wasted compute + noise.
  let seedList: string[];
  if (explicitSeeds.length > 0) {
    seedList = explicitSeeds;
  } else if (lex.length > 0) {
    const seedMinDegree = options.seedMinDegree ?? DEFAULT_SEED_MIN_DEGREE;
    const lexSeedPaths = lex.slice(0, 3).map(p => p.path);
    const validSeeds = lexSeedPaths.filter(s => (graph.edges.get(s)?.length ?? 0) >= seedMinDegree);
    if (validSeeds.length === 0) {
      // Lex hits exist but none have graph neighbors worth expanding
      // from (small vault or all orphan pages). Skip PPR — return
      // pure lex ordering. Better relevance than random walk from
      // an arbitrary seed.
      return lex.slice(0, topN).map(page => ({ page, score: lexScoreOf(page, lex), arm: 'lex' }));
    }
    seedList = validSeeds;
  } else {
    return [];
  }
  const pprScores = pprFromSeeds(graph, seedList, options.pprOptions, options.rng);
  return mergeWithPPR(lex, pprScores, pages, topN, 'graph-first-ppr');
}

function lexScoreOf(page: PageRef, ranked: PageRef[]): number {
  // Placeholder score: highest-ranked = 1.0, descending by rank.
  const idx = ranked.indexOf(page);
  if (idx === -1) return 0;
  return Math.max(1, ranked.length - idx) / ranked.length;
}

function mergeWithPPR(
  lex: PageRef[],
  pprScores: Map<string, number>,
  pages: PageRef[],
  topN: number,
  arm: 'lex-seeded-ppr' | 'graph-first-ppr',
): PageMatch[] {
  // Build a path → PageRef index for O(1) lookup.
  const byPath = new Map<string, PageRef>();
  for (const p of pages) byPath.set(p.path, p);

  // Merge: each page gets a composite score = max(lexScore, pprScore).
  // PPR is the dominant signal (ranker); lex is the fallback hint.
  const merged = new Map<string, { page: PageRef; score: number; arm: PageMatch['arm'] }>();

  for (const page of lex) {
    const ppr = pprScores.get(page.path) ?? 0;
    const score = Math.max(lexScoreOf(page, lex), ppr);
    merged.set(page.path, { page, score, arm });
  }
  for (const [path, ppr] of pprScores) {
    if (merged.has(path)) continue;
    const page = byPath.get(path);
    if (!page) continue;
    merged.set(path, { page, score: ppr, arm });
  }

  return [...merged.values()]
    .sort((a, b) => b.score - a.score)
    .slice(0, topN)
    .map(({ page, score }) => ({ page, score, arm }));
}