Skip to main content

code_system_graph_core/
linker.rs

1use std::collections::{BTreeMap, BTreeSet};
2
3use code_system_graph_model::{
4    Edge, EdgeId, EdgeKind, EpistemicStatus, Evidence, EvidenceId, EvidenceRef, HttpLinkReport, LinkDecision, LinkStatus, Node, NodeId, Provenance, stable_id
5};
6use semver::Version;
7use thiserror::Error;
8
9use crate::{ManifestError, ManualLinkConfig, validate_manual_links};
10
11const MANUAL_LINK_MATCHER: &str = "manual_exact";
12const MANUAL_LINK_EXTRACTOR: &str = "code-system-graph.manual-link";
13
14/// One exact HTTP contract that could not be linked because several providers matched.
15#[derive(Debug, Clone, PartialEq, Eq)]
16pub struct HttpLinkAmbiguity {
17    /// Canonical HTTP method.
18    pub method: String,
19    /// Canonical path template.
20    pub path: String,
21    /// Stable candidate node identifiers in deterministic order.
22    pub candidates: Vec<String>,
23}
24
25/// Deterministic automatic HTTP links plus unresolved exact-provider ambiguities.
26#[derive(Debug, Clone, PartialEq)]
27pub struct HttpLinkResolution {
28    /// Unambiguous automatic relationships.
29    pub edges: Vec<Edge>,
30    /// Source-free ambiguous contract identities omitted from the edge set.
31    pub ambiguities: Vec<HttpLinkAmbiguity>,
32    /// Consumer and test calls left without a provider edge, with outcome counts.
33    pub report: HttpLinkReport,
34}
35
36/// Endpoint field being resolved for a manual relationship.
37#[derive(Debug, Clone, Copy, PartialEq, Eq)]
38pub enum ManualLinkEndpoint {
39    /// The `from` endpoint.
40    From,
41    /// The `to` endpoint.
42    To,
43}
44
45impl std::fmt::Display for ManualLinkEndpoint {
46    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
47        match self {
48            Self::From => formatter.write_str("from"),
49            Self::To => formatter.write_str("to"),
50        }
51    }
52}
53
54/// Error returned while resolving exact manual relationships.
55#[derive(Debug, Error)]
56pub enum ManualLinkError {
57    /// A manually constructed declaration violates manifest invariants.
58    #[error(transparent)]
59    InvalidDeclaration(#[from] ManifestError),
60    /// No node has the exact requested identifier or stable key.
61    #[error(
62        "manualLinks[{index}].{endpoint} `{value}` did not match any exact node ID or stable key"
63    )]
64    MissingEndpoint {
65        /// Zero-based declaration index.
66        index: usize,
67        /// Endpoint field.
68        endpoint: ManualLinkEndpoint,
69        /// Requested exact identity.
70        value: String,
71    },
72    /// More than one node has the exact requested identifier or stable key.
73    #[error(
74        "manualLinks[{index}].{endpoint} `{value}` is ambiguous across exact candidates {candidates:?}"
75    )]
76    AmbiguousEndpoint {
77        /// Zero-based declaration index.
78        index: usize,
79        /// Endpoint field.
80        endpoint: ManualLinkEndpoint,
81        /// Requested exact identity.
82        value: String,
83        /// Stable candidate identities in deterministic order.
84        candidates: Vec<NodeId>,
85    },
86    /// Distinct endpoint literals resolved to the same node.
87    #[error("manualLinks[{index}] resolves both endpoints to `{node}`")]
88    ResolvedSelfLink {
89        /// Zero-based declaration index.
90        index: usize,
91        /// Resolved node identity.
92        node: String,
93    },
94    /// Distinct declarations resolved to the same graph relationship.
95    #[error(
96        "manualLinks[{duplicate}] resolves to the same relationship as manualLinks[{first}]: {source_node:?} -> {target_node:?} ({relation:?})"
97    )]
98    DuplicateResolvedLink {
99        /// Index of the first declaration.
100        first: usize,
101        /// Index of the repeated declaration.
102        duplicate: usize,
103        /// Resolved source node.
104        source_node: NodeId,
105        /// Resolved target node.
106        target_node: NodeId,
107        /// Repeated concrete relationship.
108        relation: EdgeKind,
109    },
110    /// A suppression did not identify an existing exact automatic relationship.
111    #[error(
112        "manualLinks[{index}] cannot suppress missing automatic relationship {source_node:?} -> {target_node:?} ({relation:?})"
113    )]
114    MissingSuppressionTarget {
115        /// Zero-based declaration index.
116        index: usize,
117        /// Resolved source node.
118        source_node: NodeId,
119        /// Resolved target node.
120        target_node: NodeId,
121        /// Requested concrete relationship.
122        relation: EdgeKind,
123    },
124}
125
126/// Graph facts and audit records produced after applying manual declarations.
127#[derive(Debug, Clone, PartialEq)]
128pub struct ManualLinkResolution {
129    /// Automatic edges after exact suppressions and manual replacements.
130    pub edges: Vec<Edge>,
131    /// Manual evidence emitted for created edges and successful suppressions.
132    pub evidence: Vec<Evidence>,
133    /// Versioned decisions in deterministic relationship order.
134    pub decisions: Vec<LinkDecision>,
135}
136
137pub(crate) fn http_link_ambiguity<'a>(
138    method: &str,
139    path: &str,
140    candidates: impl IntoIterator<Item = &'a NodeId>,
141) -> HttpLinkAmbiguity {
142    let mut candidates = candidates
143        .into_iter()
144        .map(|candidate| candidate.as_str().to_owned())
145        .collect::<Vec<_>>();
146    candidates.sort();
147    candidates.dedup();
148    HttpLinkAmbiguity {
149        method: method.to_owned(),
150        path: path.to_owned(),
151        candidates,
152    }
153}
154
155pub(crate) fn sort_http_ambiguities(ambiguities: &mut Vec<HttpLinkAmbiguity>) {
156    ambiguities.sort_by(|left, right| {
157        (&left.method, &left.path, &left.candidates).cmp(&(
158            &right.method,
159            &right.path,
160            &right.candidates,
161        ))
162    });
163    ambiguities.dedup();
164}
165
166/// Resolves and applies exact manual relationships to an automatic edge set.
167///
168/// Endpoint values match only [`NodeId`] text or [`Node::stable_key`] text. A creation replaces an
169/// automatic edge with the same source, target, and relation so the resulting edge is backed only
170/// by explicit manual evidence. A suppression removes every automatic edge with that exact triple;
171/// the optional contract is audit context and never broadens or narrows edge matching.
172///
173/// # Errors
174///
175/// Returns [`ManualLinkError`] for invalid declarations, missing or ambiguous endpoints, resolved
176/// self-links, duplicate resolved relationships, or suppressions that match no automatic edge.
177pub fn resolve_manual_links(
178    links: &[ManualLinkConfig],
179    nodes: &[Node],
180    automatic_edges: &[Edge],
181) -> Result<ManualLinkResolution, ManualLinkError> {
182    validate_manual_links(links)?;
183    let mut resolved = Vec::with_capacity(links.len());
184    let mut identities = BTreeMap::new();
185    for (index, link) in links.iter().enumerate() {
186        let source = resolve_manual_endpoint(nodes, index, ManualLinkEndpoint::From, &link.from)?;
187        let target = resolve_manual_endpoint(nodes, index, ManualLinkEndpoint::To, &link.to)?;
188        if source == target {
189            return Err(ManualLinkError::ResolvedSelfLink {
190                index,
191                node: source.as_str().to_owned(),
192            });
193        }
194        let identity = (source.clone(), target.clone(), link.relation);
195        if let Some(first) = identities.insert(identity, index) {
196            return Err(ManualLinkError::DuplicateResolvedLink {
197                first,
198                duplicate: index,
199                source_node: source,
200                target_node: target,
201                relation: link.relation,
202            });
203        }
204        resolved.push(ResolvedManualLink {
205            index,
206            link,
207            source,
208            target,
209        });
210    }
211    resolved.sort_by(|left, right| {
212        (
213            &left.source,
214            &left.target,
215            left.link.relation,
216            left.link.suppress,
217        )
218            .cmp(&(
219                &right.source,
220                &right.target,
221                right.link.relation,
222                right.link.suppress,
223            ))
224    });
225
226    let mut edges = automatic_edges.to_vec();
227    edges.sort_by(|left, right| left.id.cmp(&right.id));
228    let mut evidence = Vec::with_capacity(resolved.len());
229    let mut decisions = Vec::with_capacity(resolved.len());
230    for item in resolved {
231        let manual_evidence = manual_link_evidence(&item);
232        let evidence_ref = EvidenceRef {
233            id: manual_evidence.id.clone(),
234            provenance: Provenance::Manual,
235        };
236        let status = if item.link.suppress {
237            let before = edges.len();
238            edges.retain(|edge| !edge_matches(&item, edge));
239            let removed = before - edges.len();
240            if removed == 0 {
241                return Err(ManualLinkError::MissingSuppressionTarget {
242                    index: item.index,
243                    source_node: item.source,
244                    target_node: item.target,
245                    relation: item.link.relation,
246                });
247            }
248            LinkStatus::Suppressed
249        } else {
250            edges.retain(|edge| !edge_matches(&item, edge));
251            edges.push(manual_link_edge(&item, &manual_evidence));
252            LinkStatus::Confirmed
253        };
254        decisions.push(manual_link_decision(&item, evidence_ref, status));
255        evidence.push(manual_evidence);
256    }
257    edges.sort_by(|left, right| left.id.cmp(&right.id));
258    evidence.sort_by(|left, right| left.id.cmp(&right.id));
259    decisions.sort_by(|left, right| {
260        (&left.source, &left.target, left.relation, left.status).cmp(&(
261            &right.source,
262            &right.target,
263            right.relation,
264            right.status,
265        ))
266    });
267    Ok(ManualLinkResolution {
268        edges,
269        evidence,
270        decisions,
271    })
272}
273
274#[derive(Debug)]
275struct ResolvedManualLink<'a> {
276    index: usize,
277    link: &'a ManualLinkConfig,
278    source: NodeId,
279    target: NodeId,
280}
281
282fn resolve_manual_endpoint(
283    nodes: &[Node],
284    index: usize,
285    endpoint: ManualLinkEndpoint,
286    value: &str,
287) -> Result<NodeId, ManualLinkError> {
288    let candidates = nodes
289        .iter()
290        .filter(|node| node.id.as_str() == value || node.stable_key == value)
291        .map(|node| node.id.clone())
292        .collect::<BTreeSet<_>>();
293    match candidates.len() {
294        0 => Err(ManualLinkError::MissingEndpoint {
295            index,
296            endpoint,
297            value: value.to_owned(),
298        }),
299        1 => candidates
300            .into_iter()
301            .next()
302            .ok_or_else(|| ManualLinkError::MissingEndpoint {
303                index,
304                endpoint,
305                value: value.to_owned(),
306            }),
307        _ => Err(ManualLinkError::AmbiguousEndpoint {
308            index,
309            endpoint,
310            value: value.to_owned(),
311            candidates: candidates.into_iter().collect(),
312        }),
313    }
314}
315
316fn edge_matches(link: &ResolvedManualLink<'_>, edge: &Edge) -> bool {
317    edge.source == link.source && edge.target == link.target && edge.kind == link.link.relation
318}
319
320fn manual_link_edge(link: &ResolvedManualLink<'_>, evidence: &Evidence) -> Edge {
321    let key = format!(
322        "{}:{:?}:{}",
323        link.source.as_str(),
324        link.link.relation,
325        link.target.as_str()
326    );
327    Edge {
328        id: EdgeId::new(stable_id("edge", &key)),
329        source: link.source.clone(),
330        target: link.target.clone(),
331        kind: link.link.relation,
332        confidence: 1.0,
333        status: EpistemicStatus::Confirmed,
334        evidence: vec![evidence.id.clone()],
335    }
336}
337
338fn manual_link_evidence(link: &ResolvedManualLink<'_>) -> Evidence {
339    let contract = link.link.contract.as_deref().unwrap_or("");
340    let key = format!(
341        "{}:{}:{:?}:{contract}:{}:{}",
342        link.source.as_str(),
343        link.target.as_str(),
344        link.link.relation,
345        link.link.suppress,
346        link.link.reason
347    );
348    Evidence {
349        id: EvidenceId::new(stable_id("evidence", &key)),
350        repo_id: None,
351        file_path: None,
352        start_line: None,
353        end_line: None,
354        extractor: MANUAL_LINK_EXTRACTOR.to_owned(),
355        extractor_version: "1.0.0".to_owned(),
356        provenance: Provenance::Manual,
357        confidence: 1.0,
358        observed_at_commit: None,
359        content_hash: Some(stable_id("manual-link-declaration", &key)),
360        note: Some(link.link.reason.clone()),
361    }
362}
363
364fn manual_link_decision(
365    link: &ResolvedManualLink<'_>,
366    evidence: EvidenceRef,
367    status: LinkStatus,
368) -> LinkDecision {
369    let mut reasons = vec![
370        link.link.reason.clone(),
371        "both endpoints matched an exact node ID or stable key".to_owned(),
372    ];
373    if let Some(contract) = &link.link.contract {
374        reasons.push(format!("declared contract: {contract}"));
375    }
376    reasons.push(match status {
377        LinkStatus::Confirmed => "manual declaration created the exact relationship".to_owned(),
378        LinkStatus::Suppressed => {
379            "manual declaration removed the exact automatic relationship".to_owned()
380        }
381        LinkStatus::Ambiguous | LinkStatus::Rejected => {
382            "manual declaration was not applied".to_owned()
383        }
384    });
385    LinkDecision {
386        source: link.source.clone(),
387        target: link.target.clone(),
388        relation: link.link.relation,
389        matcher: MANUAL_LINK_MATCHER.to_owned(),
390        matcher_version: Version::new(1, 0, 0),
391        score: 1.0,
392        confidence: 1.0,
393        reasons,
394        rejected_alternatives: Vec::new(),
395        evidence: vec![evidence],
396        status,
397    }
398}
399
400#[cfg(test)]
401mod tests {
402
403    use code_system_graph_model::{
404        Edge, EdgeId, EdgeKind, EpistemicStatus, LinkStatus, Node, NodeId, NodeKind, Provenance, RepoId
405    };
406
407    use super::{ManualLinkEndpoint, ManualLinkError, resolve_manual_links};
408    use crate::{
409        AuthorityMap, HttpConsumerConfig, ManualLinkConfig, extract_openapi, link_http_routes
410    };
411
412    fn consumer() -> crate::HttpBoundary {
413        crate::HttpBoundary::consumer(
414            RepoId::new("repo:web"),
415            &HttpConsumerConfig {
416                method: "POST".to_owned(),
417                path: "/api/orders".to_owned(),
418                source: "src/checkout.ts".to_owned(),
419            },
420        )
421    }
422
423    fn provider(repo: &str) -> crate::HttpBoundary {
424        let input = r"
425openapi: 3.0.3
426paths:
427  /api/orders:
428    post:
429      operationId: createOrder
430";
431        let result = extract_openapi(&RepoId::new(repo), "openapi.yaml", input);
432        match result {
433            Ok(mut boundaries) => boundaries.remove(0),
434            Err(error) => panic!("test fixture must be valid: {error}"),
435        }
436    }
437
438    fn graph_node(id: &str, stable_key: &str) -> Node {
439        Node {
440            id: NodeId::new(id),
441            kind: NodeKind::Service,
442            repo_id: None,
443            stable_key: stable_key.to_owned(),
444            label: stable_key.to_owned(),
445        }
446    }
447
448    fn manual_link(from: &str, to: &str, relation: EdgeKind, suppress: bool) -> ManualLinkConfig {
449        ManualLinkConfig {
450            from: from.to_owned(),
451            to: to.to_owned(),
452            relation,
453            contract: Some("POST /orders".to_owned()),
454            reason: "Explicit manual boundary".to_owned(),
455            suppress,
456        }
457    }
458
459    fn automatic_edge(id: &str, source: &str, target: &str, kind: EdgeKind) -> Edge {
460        Edge {
461            id: EdgeId::new(id),
462            source: NodeId::new(source),
463            target: NodeId::new(target),
464            kind,
465            confidence: 0.8,
466            status: EpistemicStatus::Inferred,
467            evidence: Vec::new(),
468        }
469    }
470
471    #[test]
472    fn link_http_boundaries_should_require_bilateral_evidence() {
473        let result = link_http_routes(
474            &[consumer(), provider("repo:api")],
475            &[],
476            &[],
477            &AuthorityMap::new(),
478        );
479
480        assert_eq!(result.edges[0].evidence.len(), 2);
481    }
482
483    #[test]
484    fn link_http_boundaries_should_preserve_duplicate_providers_as_ambiguity() {
485        let result = link_http_routes(
486            &[consumer(), provider("repo:api-a"), provider("repo:api-b")],
487            &[],
488            &[],
489            &AuthorityMap::new(),
490        );
491
492        assert_eq!(result.edges, Vec::new());
493        assert_eq!(result.ambiguities.len(), 1);
494        assert_eq!(result.ambiguities[0].method, "POST");
495        assert_eq!(result.ambiguities[0].path, "/api/orders");
496        assert_eq!(result.ambiguities[0].candidates.len(), 2);
497    }
498
499    #[test]
500    fn resolve_manual_links_should_create_confirmed_exact_edge_with_manual_evidence() {
501        let nodes = [
502            graph_node("node:web", "service:web"),
503            graph_node("node:api", "service:api"),
504        ];
505        let links = [manual_link(
506            "node:web",
507            "service:api",
508            EdgeKind::Consumes,
509            false,
510        )];
511
512        let result = resolve_manual_links(&links, &nodes, &[])
513            .unwrap_or_else(|error| panic!("manual link should resolve: {error}"));
514
515        assert!(
516            result.edges.len() == 1
517                && result.edges[0].source == NodeId::new("node:web")
518                && result.edges[0].target == NodeId::new("node:api")
519                && result.edges[0].kind == EdgeKind::Consumes
520                && (result.edges[0].confidence - 1.0).abs() < f32::EPSILON
521                && result.edges[0].status == EpistemicStatus::Confirmed
522                && result.evidence.len() == 1
523                && result.evidence[0].provenance == Provenance::Manual
524                && result.decisions.len() == 1
525                && result.decisions[0].status == LinkStatus::Confirmed
526                && (result.decisions[0].score - 1.0).abs() < f32::EPSILON
527        );
528    }
529
530    #[test]
531    fn resolve_manual_links_should_suppress_only_exact_automatic_relationship() {
532        let nodes = [
533            graph_node("node:web", "service:web"),
534            graph_node("node:api", "service:api"),
535        ];
536        let links = [manual_link(
537            "node:web",
538            "node:api",
539            EdgeKind::CallsRemote,
540            true,
541        )];
542        let automatic = [
543            automatic_edge("edge:exact", "node:web", "node:api", EdgeKind::CallsRemote),
544            automatic_edge(
545                "edge:reverse",
546                "node:api",
547                "node:web",
548                EdgeKind::CallsRemote,
549            ),
550            automatic_edge("edge:relation", "node:web", "node:api", EdgeKind::Consumes),
551        ];
552
553        let result = resolve_manual_links(&links, &nodes, &automatic)
554            .unwrap_or_else(|error| panic!("suppression should resolve: {error}"));
555
556        assert!(
557            result.edges.len() == 2
558                && result
559                    .edges
560                    .iter()
561                    .all(|edge| edge.id.as_str() != "edge:exact")
562                && result
563                    .edges
564                    .iter()
565                    .any(|edge| edge.id.as_str() == "edge:reverse")
566                && result
567                    .edges
568                    .iter()
569                    .any(|edge| edge.id.as_str() == "edge:relation")
570                && result.decisions[0].status == LinkStatus::Suppressed
571        );
572    }
573
574    #[test]
575    fn resolve_manual_links_should_fail_for_missing_endpoint() {
576        let nodes = [graph_node("node:web", "service:web")];
577        let links = [manual_link(
578            "node:web",
579            "service:missing",
580            EdgeKind::Consumes,
581            false,
582        )];
583
584        let result = resolve_manual_links(&links, &nodes, &[]);
585
586        assert!(matches!(
587            result,
588            Err(ManualLinkError::MissingEndpoint {
589                endpoint: ManualLinkEndpoint::To,
590                value,
591                ..
592            }) if value == "service:missing"
593        ));
594    }
595
596    #[test]
597    fn resolve_manual_links_should_fail_for_ambiguous_exact_endpoint() {
598        let nodes = [
599            graph_node("node:web", "service:web"),
600            graph_node("node:api-b", "service:shared"),
601            graph_node("node:api-a", "service:shared"),
602        ];
603        let links = [manual_link(
604            "node:web",
605            "service:shared",
606            EdgeKind::Consumes,
607            false,
608        )];
609
610        let result = resolve_manual_links(&links, &nodes, &[]);
611
612        assert!(matches!(
613            result,
614            Err(ManualLinkError::AmbiguousEndpoint { candidates, .. })
615                if candidates
616                    == vec![NodeId::new("node:api-a"), NodeId::new("node:api-b")]
617        ));
618    }
619
620    #[test]
621    fn resolve_manual_links_should_be_independent_of_input_order() {
622        let nodes = vec![
623            graph_node("node:web", "service:web"),
624            graph_node("node:api", "service:api"),
625            graph_node("node:worker", "service:worker"),
626        ];
627        let links = vec![
628            manual_link("service:web", "service:api", EdgeKind::CallsRemote, false),
629            manual_link("service:worker", "service:api", EdgeKind::Consumes, false),
630        ];
631        let mut reversed_nodes = nodes.clone();
632        reversed_nodes.reverse();
633        let mut reversed_links = links.clone();
634        reversed_links.reverse();
635
636        let first = resolve_manual_links(&links, &nodes, &[]);
637        let second = resolve_manual_links(&reversed_links, &reversed_nodes, &[]);
638
639        assert_eq!(
640            first.unwrap_or_else(|error| panic!("first resolution should succeed: {error}")),
641            second.unwrap_or_else(|error| panic!("second resolution should succeed: {error}"))
642        );
643    }
644}