{"version":3,"file":"graph.d.ts","sourceRoot":"","sources":["../../../src/core/mission/graph.ts"],"names":[],"mappings":"AAAA;;;;;GAKG;AAIH,OAAO,KAAK,EACX,kBAAkB,EAClB,qBAAqB,EACrB,eAAe,EACf,sBAAsB,EACtB,gBAAgB,EAChB,YAAY,EAEZ,MAAM,YAAY,CAAC;AAOpB;;;;GAIG;AACH,wBAAgB,yBAAyB,CACxC,KAAK,EAAE,YAAY,EACnB,UAAU,EAAE,gBAAgB,EAAE,EAC9B,SAAS,EAAE,eAAe,EAAE,GAC1B,MAAM,CASR;AAcD,wBAAgB,YAAY,CAAC,OAAO,EAAE,IAAI,CAAC,sBAAsB,EAAE,YAAY,CAAC,GAAG,GAAG,CAAC,MAAM,CAAC,CAI7F;AAED,MAAM,WAAW,eAAe;IAC/B,mDAAmD;IACnD,cAAc,EAAE,GAAG,CAAC,MAAM,EAAE,MAAM,EAAE,CAAC,CAAC;IACtC,4EAA4E;IAC5E,YAAY,EAAE,GAAG,CAAC,MAAM,EAAE,MAAM,EAAE,CAAC,CAAC;CACpC;AAED,wBAAgB,oBAAoB,CAAC,UAAU,EAAE,gBAAgB,EAAE,GAAG,eAAe,CAYpF;AAMD;;;;;GAKG;AACH,wBAAgB,oBAAoB,CAAC,OAAO,EAAE,sBAAsB,GAAG,qBAAqB,CA2H3F;AAED;;;GAGG;AACH,wBAAgB,YAAY,CAAC,OAAO,EAAE,IAAI,CAAC,sBAAsB,EAAE,YAAY,CAAC,GAAG,MAAM,EAAE,EAAE,CAiC5F;AAMD;;;GAGG;AACH,wBAAgB,oBAAoB,CAAC,OAAO,EAAE,IAAI,CAAC,sBAAsB,EAAE,YAAY,CAAC,GAAG,MAAM,EAAE,CA8BlG;AAMD;;;;GAIG;AACH,wBAAgB,mBAAmB,CAAC,OAAO,EAAE,IAAI,CAAC,sBAAsB,EAAE,YAAY,CAAC,GAAG,kBAAkB,CAkD3G;AAED;;;GAGG;AACH,wBAAgB,oBAAoB,CACnC,SAAS,EAAE,MAAM,EACjB,KAAK,EAAE,YAAY,EACnB,UAAU,EAAE,gBAAgB,EAAE,EAC9B,SAAS,EAAE,eAAe,EAAE,EAC5B,QAAQ,SAAI,EACZ,MAAM,GAAE,sBAAsB,CAAC,QAAQ,CAAW,EAClD,KAAK,SAAa,GAChB,sBAAsB,CAcxB","sourcesContent":["/**\n * Durable Mission Graph — graph construction, validation, hashing,\n * critical-path analysis and topological ordering (2.0.0).\n *\n * Pure, deterministic functions. No I/O.\n */\n\nimport { createHash } from \"node:crypto\";\nimport { toCanonicalJson } from \"../long-horizon/canonical-json.js\";\nimport type {\n\tCriticalPathResult,\n\tGraphValidationResult,\n\tMissionContract,\n\tMissionGraphDocumentV1,\n\tMissionObjective,\n\tMissionScope,\n\tValidationIssue,\n} from \"./types.js\";\nimport { MISSION_SCHEMA_VERSION } from \"./types.js\";\n\n// =============================================================================\n// Canonical digest\n// =============================================================================\n\n/**\n * Compute the canonical semantic digest of a mission's scope, objectives and\n * contracts. Non-semantic fields (status, timestamps, observed repositories)\n * are excluded so that the digest is stable across execution bookkeeping.\n */\nexport function computeMissionGraphDigest(\n\tscope: MissionScope,\n\tobjectives: MissionObjective[],\n\tcontracts: MissionContract[],\n): string {\n\tconst payload = {\n\t\tschemaVersion: MISSION_SCHEMA_VERSION,\n\t\tscope,\n\t\tobjectives: sortObjectivesById(objectives),\n\t\tcontracts: sortContractsById(contracts),\n\t};\n\tconst canonical = toCanonicalJson(payload);\n\treturn createHash(\"sha256\").update(canonical, \"utf8\").digest(\"hex\");\n}\n\nfunction sortObjectivesById(objectives: MissionObjective[]): MissionObjective[] {\n\treturn [...objectives].sort((a, b) => (a.id < b.id ? -1 : a.id > b.id ? 1 : 0));\n}\n\nfunction sortContractsById(contracts: MissionContract[]): MissionContract[] {\n\treturn [...contracts].sort((a, b) => (a.id < b.id ? -1 : a.id > b.id ? 1 : 0));\n}\n\n// =============================================================================\n// Dependency indexing\n// =============================================================================\n\nexport function objectiveIds(mission: Pick<MissionGraphDocumentV1, \"objectives\">): Set<string> {\n\tconst ids = new Set<string>();\n\tfor (const o of mission.objectives) ids.add(o.id);\n\treturn ids;\n}\n\nexport interface DependencyIndex {\n\t/** For each objective, its direct dependencies. */\n\tdependenciesBy: Map<string, string[]>;\n\t/** For each objective, the objectives that depend on it (reverse edges). */\n\tdependentsBy: Map<string, string[]>;\n}\n\nexport function buildDependencyIndex(objectives: MissionObjective[]): DependencyIndex {\n\tconst dependenciesBy = new Map<string, string[]>();\n\tconst dependentsBy = new Map<string, string[]>();\n\tfor (const o of objectives) {\n\t\tdependenciesBy.set(o.id, [...o.dependencies]);\n\t\tfor (const dep of o.dependencies) {\n\t\t\tconst list = dependentsBy.get(dep) ?? [];\n\t\t\tlist.push(o.id);\n\t\t\tdependentsBy.set(dep, list);\n\t\t}\n\t}\n\treturn { dependenciesBy, dependentsBy };\n}\n\n// =============================================================================\n// Graph validation\n// =============================================================================\n\n/**\n * Validate a mission graph document deterministically.\n *\n * Checks: unique ids, missing dependencies, dependency cycles, explicit\n * acceptance criteria, declared repositories, scope integrity, self-approval.\n */\nexport function validateMissionGraph(mission: MissionGraphDocumentV1): GraphValidationResult {\n\tconst issues: ValidationIssue[] = [];\n\tconst ids = objectiveIds(mission);\n\n\t// Unique objective ids\n\t{\n\t\tconst seen = new Set<string>();\n\t\tfor (const o of mission.objectives) {\n\t\t\tif (seen.has(o.id)) {\n\t\t\t\tissues.push({ path: `objectives[${o.id}]`, message: `duplicate objective id`, severity: \"error\" });\n\t\t\t}\n\t\t\tseen.add(o.id);\n\t\t}\n\t}\n\n\t// Missing dependencies\n\tconst missingDependencies: string[] = [];\n\tfor (const o of mission.objectives) {\n\t\tfor (const dep of o.dependencies) {\n\t\t\tif (!ids.has(dep)) {\n\t\t\t\tmissingDependencies.push(`${o.id}->${dep}`);\n\t\t\t}\n\t\t}\n\t\tfor (const branch of [...o.dependencies]) {\n\t\t\tvoid branch;\n\t\t}\n\t}\n\tif (missingDependencies.length > 0) {\n\t\tissues.push({\n\t\t\tpath: \"dependencies\",\n\t\t\tmessage: `missing dependencies: ${missingDependencies.join(\", \")}`,\n\t\t\tseverity: \"error\",\n\t\t});\n\t}\n\n\t// Cycles via DFS\n\tconst cycles = detectCycles(mission);\n\tif (cycles.length > 0) {\n\t\tfor (const cycle of cycles) {\n\t\t\tissues.push({\n\t\t\t\tpath: \"dependencies.cycles\",\n\t\t\t\tmessage: `dependency cycle detected: ${cycle.join(\" -> \")}`,\n\t\t\t\tseverity: \"error\",\n\t\t\t});\n\t\t}\n\t}\n\n\t// Acceptance criteria explicit\n\tfor (const o of mission.objectives) {\n\t\tif (o.acceptanceCriteria.length === 0) {\n\t\t\tissues.push({\n\t\t\t\tpath: `objectives[${o.id}].acceptanceCriteria`,\n\t\t\t\tmessage: `objective '${o.id}' has no explicit acceptance criteria`,\n\t\t\t\tseverity: \"error\",\n\t\t\t});\n\t\t}\n\t}\n\n\t// Declared repositories within scope\n\tconst undeclaredRepositories: string[] = [];\n\tif (mission.scope.requireDeclaredRepositories) {\n\t\tconst declared = new Set(mission.scope.repositories);\n\t\tfor (const o of mission.objectives) {\n\t\t\tfor (const repo of o.declaredRepositories) {\n\t\t\t\tif (!declared.has(repo)) {\n\t\t\t\t\tconst key = `${o.id}__${repo}`;\n\t\t\t\t\tif (!undeclaredRepositories.includes(key)) undeclaredRepositories.push(key);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tif (undeclaredRepositories.length > 0) {\n\t\tissues.push({\n\t\t\tpath: \"scope.repositories\",\n\t\t\tmessage: `undeclared repositories: ${undeclaredRepositories.join(\", \")}`,\n\t\t\tseverity: \"error\",\n\t\t});\n\t}\n\n\t// No self-approval: an objective requiring approval must not grant itself.\n\tlet noSelfApproval = true;\n\tfor (const o of mission.objectives) {\n\t\tif (o.approvalGate?.requiredPrincipals.includes(o.id)) {\n\t\t\tnoSelfApproval = false;\n\t\t\tissues.push({\n\t\t\t\tpath: `objectives[${o.id}].approvalGate`,\n\t\t\t\tmessage: `objective '${o.id}' is its own approval principal`,\n\t\t\t\tseverity: \"error\",\n\t\t\t});\n\t\t}\n\t}\n\n\t// Contract producer/consumer linkage\n\tfor (const c of mission.contracts) {\n\t\tif (c.producerObjective && !ids.has(c.producerObjective)) {\n\t\t\tissues.push({\n\t\t\t\tpath: `contracts[${c.id}].producerObjective`,\n\t\t\t\tmessage: `contract '${c.id}' references unknown producer '${c.producerObjective}'`,\n\t\t\t\tseverity: \"error\",\n\t\t\t});\n\t\t}\n\t\tif (!ids.has(c.consumerObjective)) {\n\t\t\tissues.push({\n\t\t\t\tpath: `contracts[${c.id}].consumerObjective`,\n\t\t\t\tmessage: `contract '${c.id}' references unknown consumer '${c.consumerObjective}'`,\n\t\t\t\tseverity: \"error\",\n\t\t\t});\n\t\t}\n\t}\n\n\tconst valid = issues.every((i) => i.severity === \"warning\");\n\tconst digest = computeMissionGraphDigest(mission.scope, mission.objectives, mission.contracts);\n\n\treturn {\n\t\tvalid,\n\t\tdigest,\n\t\trevision: mission.revision,\n\t\terrors: issues,\n\t\tcycles,\n\t\tmissingDependencies,\n\t\tundeclaredRepositories,\n\t\tnoSelfApproval,\n\t};\n}\n\n/**\n * Detect all strongly-connected dependency cycles.\n * Returns one representative path per cycle.\n */\nexport function detectCycles(mission: Pick<MissionGraphDocumentV1, \"objectives\">): string[][] {\n\tconst index = buildDependencyIndex(mission.objectives);\n\tconst cycles: string[][] = [];\n\tconst state = new Map<string, number>(); // 0=unvisited,1=visiting,2=done\n\tconst stack: string[] = [];\n\n\tconst visit = (id: string): void => {\n\t\tconst st = state.get(id) ?? 0;\n\t\tif (st === 2) return;\n\t\tif (st === 1) {\n\t\t\t// Found a back edge: the cycle is from current position in stack back to id\n\t\t\tconst start = stack.indexOf(id);\n\t\t\tconst cycle = start >= 0 ? stack.slice(start).concat(id) : [id];\n\t\t\t// Only record minimal cycles\n\t\t\tif (!cycles.some((c) => c.join(\",\") === cycle.join(\",\"))) {\n\t\t\t\tcycles.push(cycle);\n\t\t\t}\n\t\t\treturn;\n\t\t}\n\t\tstate.set(id, 1);\n\t\tstack.push(id);\n\t\tconst deps = index.dependenciesBy.get(id) ?? [];\n\t\tfor (const dep of deps) {\n\t\t\tvisit(dep);\n\t\t}\n\t\tstack.pop();\n\t\tstate.set(id, 2);\n\t};\n\n\tfor (const o of mission.objectives) {\n\t\tif ((state.get(o.id) ?? 0) === 0) visit(o.id);\n\t}\n\treturn cycles;\n}\n\n// =============================================================================\n// Topological order\n// =============================================================================\n\n/**\n * Produce a deterministic topological order of objectives (dependency-first).\n * Returns only objectives whose declared dependencies exist and are acyclic.\n */\nexport function topologicallyOrdered(mission: Pick<MissionGraphDocumentV1, \"objectives\">): string[] {\n\tconst ids = objectiveIds(mission);\n\tconst index = buildDependencyIndex(mission.objectives);\n\tconst order: string[] = [];\n\tconst state = new Map<string, number>();\n\tconst sortedIds = [...ids].sort();\n\n\t// Kahn's algorithm with deterministic (sorted) ordering.\n\tconst indegree = new Map<string, number>();\n\tfor (const id of sortedIds) {\n\t\tconst deps = (index.dependenciesBy.get(id) ?? []).filter((d) => ids.has(d));\n\t\tindegree.set(id, deps.length);\n\t}\n\tconst ready: string[] = sortedIds.filter((id) => (indegree.get(id) ?? 0) === 0);\n\tconst queue = [...ready].sort();\n\n\twhile (queue.length > 0) {\n\t\tconst id = queue.shift() as string;\n\t\torder.push(id);\n\t\tstate.set(id, 2);\n\t\tconst dependents = (index.dependentsBy.get(id) ?? []).filter((d) => ids.has(d)).sort();\n\t\tfor (const dep of dependents) {\n\t\t\tconst deg = (indegree.get(dep) ?? 0) - 1;\n\t\t\tindegree.set(dep, deg);\n\t\t\tif (deg === 0) queue.push(dep);\n\t\t}\n\t\tqueue.sort();\n\t}\n\n\treturn order;\n}\n\n// =============================================================================\n// Critical path\n// =============================================================================\n\n/**\n * Longest dependency chain (by summed estimate). Deterministic tie-breaking\n * by objective id. Ignores missing/cyclic references; only considers\n * dependencies present in the graph.\n */\nexport function computeCriticalPath(mission: Pick<MissionGraphDocumentV1, \"objectives\">): CriticalPathResult {\n\tconst ids = objectiveIds(mission);\n\tconst byId = new Map(mission.objectives.map((o) => [o.id, o]));\n\tconst index = buildDependencyIndex(mission.objectives);\n\tconst distance = new Map<string, number>();\n\tconst predecessor = new Map<string, string | undefined>();\n\n\tconst compute = (id: string): number => {\n\t\tconst cached = distance.get(id);\n\t\tif (cached !== undefined) return cached;\n\t\tconst node = byId.get(id);\n\t\tif (!node) {\n\t\t\tdistance.set(id, 0);\n\t\t\treturn 0;\n\t\t}\n\t\tconst deps = (index.dependenciesBy.get(id) ?? []).filter((d) => ids.has(d));\n\t\tlet bestDist = 0;\n\t\tlet bestPred: string | undefined;\n\t\tfor (const dep of deps) {\n\t\t\tconst d = compute(dep);\n\t\t\t// Prefer larger distance, then smaller predecessor id for determinism.\n\t\t\tif (d > bestDist || (d === bestDist && (bestPred === undefined || dep < bestPred))) {\n\t\t\t\tbestDist = d;\n\t\t\t\tbestPred = dep;\n\t\t\t}\n\t\t}\n\t\tdistance.set(id, bestDist + (node.estimate || 0));\n\t\tpredecessor.set(id, bestPred);\n\t\treturn bestDist + (node.estimate || 0);\n\t};\n\n\tlet maxDist = -1;\n\tlet endNode: string | undefined;\n\tfor (const id of ids) {\n\t\tconst d = compute(id);\n\t\tif (d > maxDist) {\n\t\t\tmaxDist = d;\n\t\t\tendNode = id;\n\t\t}\n\t}\n\n\t// Reconstruct path\n\tconst path: string[] = [];\n\tlet cur: string | undefined = endNode;\n\twhile (cur !== undefined) {\n\t\tpath.unshift(cur);\n\t\tcur = predecessor.get(cur);\n\t}\n\n\treturn { path, weight: maxDist < 0 ? 0 : maxDist };\n}\n\n/**\n * Build a fresh MissionGraphDocumentV1 from parts, computing digest and\n * enforcing the canonical schema version.\n */\nexport function buildMissionDocument(\n\tmissionId: string,\n\tscope: MissionScope,\n\tobjectives: MissionObjective[],\n\tcontracts: MissionContract[],\n\trevision = 1,\n\tstatus: MissionGraphDocumentV1[\"status\"] = \"DRAFT\",\n\tnowMs = Date.now(),\n): MissionGraphDocumentV1 {\n\tconst digest = computeMissionGraphDigest(scope, objectives, contracts);\n\treturn {\n\t\tschemaVersion: MISSION_SCHEMA_VERSION,\n\t\tmissionId,\n\t\trevision,\n\t\tdigest,\n\t\tscope,\n\t\tobjectives,\n\t\tcontracts,\n\t\tstatus,\n\t\tcreatedAtMs: nowMs,\n\t\tupdatedAtMs: nowMs,\n\t};\n}\n"]}