lemma/planning/
discovery.rs

1use crate::engine::Context;
2use crate::parsing::ast::{DataValue, DateTimeValue, EffectiveDate, LemmaSpec, SpecRef};
3use crate::parsing::source::Source;
4use crate::Error;
5use std::collections::{BTreeMap, BTreeSet, VecDeque};
6use std::sync::Arc;
7
8// ---------------------------------------------------------------------------
9// Shared SpecRef resolution (used by graph builder and discovery)
10// ---------------------------------------------------------------------------
11
12/// Resolve a `SpecRef` against `Context` at the given planning `effective`.
13/// Returns the resolved `Arc<LemmaSpec>` or a contextual validation error.
14pub(crate) fn resolve_spec_ref(
15    context: &Context,
16    spec_ref: &SpecRef,
17    effective: &EffectiveDate,
18    consumer_name: &str,
19    ref_source: Option<Source>,
20    spec_context: Option<Arc<LemmaSpec>>,
21) -> Result<Arc<LemmaSpec>, Error> {
22    let instant = spec_ref.at(effective);
23    context
24        .spec_sets()
25        .get(spec_ref.name.as_str())
26        .and_then(|ss| ss.spec_at(&instant))
27        .ok_or_else(|| {
28            let (message, suggestion) = format_missing_spec_ref(
29                consumer_name,
30                spec_ref.name.as_str(),
31                &spec_ref.effective,
32                &instant,
33                context,
34            );
35            Error::validation_with_context(
36                message,
37                ref_source,
38                Some(suggestion),
39                spec_context,
40                None,
41            )
42        })
43}
44
45fn format_missing_spec_ref(
46    consumer_name: &str,
47    dep_name: &str,
48    qualified_at: &Option<DateTimeValue>,
49    dep_effective: &EffectiveDate,
50    context: &Context,
51) -> (String, String) {
52    if let Some(ref dt) = qualified_at {
53        let message = format!(
54            "'{}' references '{}' at {}, but no '{}' is active at that instant",
55            consumer_name, dep_name, dt, dep_name
56        );
57        let suggestion = format!(
58            "Add '{}' with effective_from on or before {}, or change the reference instant.",
59            dep_name, dt
60        );
61        return if dep_name.starts_with('@') {
62            (
63                message,
64                format!(
65                    "{} Or run `lemma get {}` to fetch it.",
66                    suggestion, dep_name
67                ),
68            )
69        } else {
70            (message, suggestion)
71        };
72    }
73
74    let dep_ss = context.spec_sets().get(dep_name);
75    let dep_exists = dep_ss.is_some_and(|ss| !ss.is_empty());
76
77    if !dep_exists {
78        let message = format!(
79            "'{}' depends on '{}', but '{}' does not exist",
80            consumer_name, dep_name, dep_name
81        );
82        let suggestion = if dep_name.starts_with('@') {
83            format!(
84                "Run `lemma get` or `lemma get {}` to fetch this dependency.",
85                dep_name
86            )
87        } else {
88            format!("Create a spec named '{}'.", dep_name)
89        };
90        return (message, suggestion);
91    }
92
93    let message = format!(
94        "'{}' depends on '{}', but no '{}' is active at {}",
95        consumer_name, dep_name, dep_name, dep_effective
96    );
97    let suggestion = format!(
98        "Add '{}' with effective_from covering {}, or adjust effective_from on '{}'.",
99        dep_name, dep_effective, consumer_name
100    );
101    (message, suggestion)
102}
103
104// ---------------------------------------------------------------------------
105// Dependency edge extraction
106// ---------------------------------------------------------------------------
107
108/// `(dep_name, optional explicit effective on reference, source location)`.
109pub(crate) fn dependency_edges(
110    spec: &Arc<LemmaSpec>,
111) -> Vec<(String, Option<DateTimeValue>, Source)> {
112    let mut out = Vec::new();
113
114    for data in &spec.data {
115        match &data.value {
116            DataValue::SpecReference(spec_ref) => {
117                out.push((
118                    spec_ref.name.clone(),
119                    spec_ref.effective.clone(),
120                    data.source_location.clone(),
121                ));
122            }
123            DataValue::TypeDeclaration {
124                from: Some(from_ref),
125                ..
126            } => {
127                out.push((
128                    from_ref.name.clone(),
129                    from_ref.effective.clone(),
130                    data.source_location.clone(),
131                ));
132            }
133            _ => {}
134        }
135    }
136
137    out
138}
139
140// ---------------------------------------------------------------------------
141// Unqualified dep interface validation
142// ---------------------------------------------------------------------------
143
144/// For each spec with unqualified deps, verify that the dep's interface
145/// (schema) is type-compatible across all dep specs active within the
146/// consumer's effective range. Qualified deps are pinned and skip this check.
147pub fn validate_dependency_interfaces(
148    context: &Context,
149    results: &BTreeMap<String, super::SpecSetPlanningResult>,
150) -> Vec<(String, Error)> {
151    let mut errors: Vec<(String, Error)> = Vec::new();
152
153    for set_result in results.values() {
154        for spec_result in &set_result.specs {
155            let spec = &spec_result.spec;
156            let consumer_ss = context
157                .spec_sets()
158                .get(&spec.name)
159                .expect("spec must be in context");
160            let (eff_from, eff_to) = consumer_ss.effective_range(spec);
161
162            for (dep_name, qualified_at, ref_source) in dependency_edges(spec) {
163                if qualified_at.is_some() {
164                    continue;
165                }
166
167                if context.spec_sets().get(&dep_name).is_none() {
168                    errors.push((
169                        set_result.name.clone(),
170                        Error::validation_with_context(
171                            format!(
172                                "'{}' depends on '{}', but '{}' does not exist",
173                                spec.name, dep_name, dep_name
174                            ),
175                            Some(ref_source.clone()),
176                            None::<String>,
177                            Some(Arc::clone(spec)),
178                            None,
179                        ),
180                    ));
181                    continue;
182                }
183                let dep_set_result = results.get(&dep_name).expect("BUG: dependency is in context but has no planning result — plan() must insert every context spec into results");
184
185                if dep_set_result.schema_over(&eff_from, &eff_to).is_none() {
186                    errors.push((
187                        set_result.name.clone(),
188                        Error::validation_with_context(
189                            format!(
190                                "'{}' depends on '{}' without pinning an effective date, but '{}' changed its interface between temporal slices",
191                                spec.name, dep_name, dep_name
192                            ),
193                            Some(ref_source.clone()),
194                            Some(format!(
195                                "Pin '{}' to a specific effective date, or make '{}' interface-compatible across specs.",
196                                dep_name, dep_name
197                            )),
198                            Some(Arc::clone(spec)),
199                            None,
200                        ),
201                    ));
202                }
203            }
204        }
205    }
206
207    errors
208}
209
210// ---------------------------------------------------------------------------
211// Spec DAG: DFS discovery + Kahn's topological sort
212// ---------------------------------------------------------------------------
213
214/// Errors from DAG construction, distinguishing cycles (global) from other errors (per-spec).
215#[derive(Debug)]
216pub(crate) enum DagError {
217    /// Dependency cycle detected -- global structural error.
218    Cycle(Vec<Error>),
219    /// Missing deps, resolution failures, etc. -- per-spec errors.
220    Other(Vec<Error>),
221}
222
223/// Single-root DFS dependency discovery. Returns topo-sorted DAG containing
224/// `root` and its transitive deps, or a typed error on cycles / missing deps.
225pub(crate) fn build_dag_for_spec(
226    context: &Context,
227    root: &Arc<LemmaSpec>,
228    effective: &EffectiveDate,
229) -> Result<Vec<Arc<LemmaSpec>>, DagError> {
230    let mut visited: BTreeSet<Arc<LemmaSpec>> = BTreeSet::new();
231    let mut edges: Vec<(Arc<LemmaSpec>, Arc<LemmaSpec>)> = Vec::new();
232    let mut nodes: BTreeMap<Arc<LemmaSpec>, Arc<LemmaSpec>> = BTreeMap::new();
233    let mut errors: Vec<Error> = Vec::new();
234
235    dfs_discover(
236        context,
237        Arc::clone(root),
238        effective,
239        &mut visited,
240        &mut edges,
241        &mut nodes,
242        &mut errors,
243    );
244
245    if errors.is_empty() {
246        kahns_topo_sort(&nodes, &edges).map_err(|err| DagError::Cycle(vec![err]))
247    } else {
248        Err(DagError::Other(errors))
249    }
250}
251
252fn dfs_discover(
253    context: &Context,
254    spec: Arc<LemmaSpec>,
255    effective: &EffectiveDate,
256    visited: &mut BTreeSet<Arc<LemmaSpec>>,
257    edges: &mut Vec<(Arc<LemmaSpec>, Arc<LemmaSpec>)>,
258    nodes: &mut BTreeMap<Arc<LemmaSpec>, Arc<LemmaSpec>>,
259    errors: &mut Vec<Error>,
260) {
261    if !visited.insert(Arc::clone(&spec)) {
262        return;
263    }
264    nodes.insert(Arc::clone(&spec), Arc::clone(&spec));
265
266    for (dep_name, qualified_at, ref_source) in dependency_edges(&spec) {
267        let dep_effective = qualified_at
268            .clone()
269            .map_or_else(|| effective.clone(), EffectiveDate::DateTimeValue);
270
271        match context
272            .spec_sets()
273            .get(&dep_name)
274            .and_then(|ss| ss.spec_at(&dep_effective))
275        {
276            Some(dependency) => {
277                edges.push((Arc::clone(&dependency), Arc::clone(&spec)));
278                dfs_discover(
279                    context,
280                    dependency,
281                    &dep_effective,
282                    visited,
283                    edges,
284                    nodes,
285                    errors,
286                );
287            }
288            None => {
289                let (message, suggestion) = format_missing_spec_ref(
290                    &spec.name,
291                    &dep_name,
292                    &qualified_at,
293                    &dep_effective,
294                    context,
295                );
296                errors.push(Error::validation_with_context(
297                    message,
298                    Some(ref_source),
299                    Some(suggestion),
300                    Some(Arc::clone(&spec)),
301                    None,
302                ));
303            }
304        }
305    }
306}
307
308fn kahns_topo_sort(
309    nodes: &BTreeMap<Arc<LemmaSpec>, Arc<LemmaSpec>>,
310    edges: &[(Arc<LemmaSpec>, Arc<LemmaSpec>)],
311) -> Result<Vec<Arc<LemmaSpec>>, Error> {
312    let mut in_degree: BTreeMap<Arc<LemmaSpec>, usize> = BTreeMap::new();
313    let mut adjacency: BTreeMap<Arc<LemmaSpec>, Vec<Arc<LemmaSpec>>> = BTreeMap::new();
314
315    for key in nodes.keys() {
316        in_degree.entry(key.clone()).or_insert(0);
317        adjacency.entry(key.clone()).or_default();
318    }
319
320    for (from, to) in edges {
321        if nodes.contains_key(from) && nodes.contains_key(to) {
322            adjacency.entry(from.clone()).or_default().push(to.clone());
323            *in_degree.entry(to.clone()).or_insert(0) += 1;
324        }
325    }
326
327    let mut queue: VecDeque<Arc<LemmaSpec>> = in_degree
328        .iter()
329        .filter(|(_, &deg)| deg == 0)
330        .map(|(k, _)| Arc::clone(k))
331        .collect();
332
333    let mut result = Vec::new();
334    while let Some(key) = queue.pop_front() {
335        if let Some(spec) = nodes.get(&key) {
336            result.push(Arc::clone(spec));
337        }
338        if let Some(neighbors) = adjacency.get(&key) {
339            for neighbor in neighbors {
340                if let Some(deg) = in_degree.get_mut(neighbor) {
341                    *deg -= 1;
342                    if *deg == 0 {
343                        queue.push_back(neighbor.clone());
344                    }
345                }
346            }
347        }
348    }
349
350    if result.len() != nodes.len() {
351        let mut cycle_nodes: Vec<String> = in_degree
352            .iter()
353            .filter(|(_, &deg)| deg > 0)
354            .map(|(k, _)| Arc::clone(k).name.clone())
355            .collect::<BTreeSet<_>>()
356            .into_iter()
357            .collect();
358        cycle_nodes.sort();
359        let cycle_path = if cycle_nodes.len() > 1 {
360            let mut path = cycle_nodes.clone();
361            path.push(cycle_nodes[0].clone());
362            path.join(" -> ")
363        } else {
364            cycle_nodes.join(" -> ")
365        };
366        return Err(Error::validation(
367            format!("Spec dependency cycle: {}", cycle_path),
368            None,
369            None::<String>,
370        ));
371    }
372
373    Ok(result)
374}
375
376#[cfg(test)]
377mod tests {
378    use super::*;
379    use crate::parsing::ast::{
380        DataValue as AstDataValue, LemmaData, LemmaSpec, Reference, SpecRef,
381    };
382    use crate::parsing::source::Source;
383    use crate::Span;
384
385    fn dag_errors(e: DagError) -> Vec<Error> {
386        match e {
387            DagError::Cycle(e) | DagError::Other(e) => e,
388        }
389    }
390
391    fn date(year: i32, month: u32, day: u32) -> DateTimeValue {
392        DateTimeValue {
393            year,
394            month,
395            day,
396            hour: 0,
397            minute: 0,
398            second: 0,
399            microsecond: 0,
400            timezone: None,
401        }
402    }
403
404    fn dummy_source() -> Source {
405        Source::new(
406            "test",
407            Span {
408                start: 0,
409                end: 0,
410                line: 1,
411                col: 0,
412            },
413        )
414    }
415
416    fn spec_with_dep(
417        name: &str,
418        eff: Option<DateTimeValue>,
419        dep: &str,
420        qualified_at: Option<DateTimeValue>,
421    ) -> LemmaSpec {
422        let mut s = LemmaSpec::new(name.to_string());
423        s.effective_from = EffectiveDate::from_option(eff);
424        s.data.push(LemmaData {
425            reference: Reference::local("d".to_string()),
426            value: AstDataValue::SpecReference(SpecRef {
427                name: dep.to_string(),
428                from_registry: dep.starts_with('@'),
429                effective: qualified_at,
430            }),
431            source_location: dummy_source(),
432        });
433        s
434    }
435
436    #[test]
437    fn dag_error_unqualified_missing_dep_includes_parent_and_resolve_instant() {
438        let mut ctx = Context::new();
439        let consumer = Arc::new(spec_with_dep(
440            "consumer",
441            Some(date(2025, 1, 1)),
442            "dep",
443            None,
444        ));
445        ctx.insert_spec(Arc::clone(&consumer), false).unwrap();
446
447        let effective = EffectiveDate::DateTimeValue(date(2025, 1, 1));
448        let errs = dag_errors(build_dag_for_spec(&ctx, &consumer, &effective).unwrap_err());
449
450        assert_eq!(errs.len(), 1);
451        let msg = errs[0].message();
452        assert!(msg.contains("'consumer'"), "should name parent spec: {msg}");
453        assert!(msg.contains("'dep'"), "should name missing dep: {msg}");
454        assert!(
455            msg.contains("does not exist"),
456            "should say dep doesn't exist: {msg}"
457        );
458
459        let suggestion = errs[0].suggestion().expect("should have suggestion");
460        assert!(
461            suggestion.contains("dep"),
462            "suggestion should name dep: {suggestion}"
463        );
464    }
465
466    #[test]
467    fn dag_error_qualified_missing_dep_mentions_qualifier_instant() {
468        let mut ctx = Context::new();
469        let consumer = Arc::new(spec_with_dep(
470            "consumer",
471            Some(date(2025, 1, 1)),
472            "dep",
473            Some(date(2025, 8, 1)),
474        ));
475        ctx.insert_spec(Arc::clone(&consumer), false).unwrap();
476
477        let effective = EffectiveDate::DateTimeValue(date(2025, 1, 1));
478        let errs = dag_errors(build_dag_for_spec(&ctx, &consumer, &effective).unwrap_err());
479
480        assert_eq!(errs.len(), 1);
481        let msg = errs[0].message();
482        assert!(msg.contains("'consumer'"), "should name parent: {msg}");
483        assert!(msg.contains("'dep'"), "should name dep: {msg}");
484        assert!(
485            msg.contains("2025"),
486            "should mention qualifier instant: {msg}"
487        );
488        assert!(
489            msg.contains("at that instant"),
490            "should use qualified wording: {msg}"
491        );
492
493        let suggestion = errs[0].suggestion().expect("should have suggestion");
494        assert!(
495            suggestion.contains("effective_from") || suggestion.contains("reference instant"),
496            "suggestion should guide fix: {suggestion}"
497        );
498    }
499
500    #[test]
501    fn dag_error_registry_dep_suggests_lemma_get() {
502        let mut ctx = Context::new();
503        let consumer = Arc::new(spec_with_dep(
504            "consumer",
505            Some(date(2025, 1, 1)),
506            "@org/pkg",
507            None,
508        ));
509        ctx.insert_spec(Arc::clone(&consumer), false).unwrap();
510
511        let effective = EffectiveDate::DateTimeValue(date(2025, 1, 1));
512        let errs = dag_errors(build_dag_for_spec(&ctx, &consumer, &effective).unwrap_err());
513
514        assert_eq!(errs.len(), 1);
515        let suggestion = errs[0].suggestion().expect("should have suggestion");
516        assert!(
517            suggestion.contains("lemma get"),
518            "registry dep suggestion should include 'lemma get': {suggestion}"
519        );
520    }
521
522    #[test]
523    fn dag_error_has_source_location() {
524        let mut ctx = Context::new();
525        let consumer = Arc::new(spec_with_dep(
526            "consumer",
527            Some(date(2025, 1, 1)),
528            "dep",
529            None,
530        ));
531        ctx.insert_spec(Arc::clone(&consumer), false).unwrap();
532
533        let effective = EffectiveDate::DateTimeValue(date(2025, 1, 1));
534        let errs = dag_errors(build_dag_for_spec(&ctx, &consumer, &effective).unwrap_err());
535
536        let display = format!("{}", errs[0]);
537        assert!(
538            display.contains("test") || display.contains("line"),
539            "error should carry source context: {display}"
540        );
541    }
542}
lemma/planning/discovery.rs

lemma/planning/
discovery.rs
