backhopper_core/jigsaw/
anchor.rs

1// Copyright (C) 2026 Michael S. Klishin and Contributors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3// See LICENSE-APACHE and LICENSE-MIT for details.
4
5use std::collections::{BTreeMap, BTreeSet};
6use std::str::FromStr;
7use std::sync::LazyLock;
8
9use backhopper_erlang_scan::{ScanArity, scan_arity};
10use regex::Regex;
11
12use crate::jigsaw::plugin_set::{PluginFile, PluginSet};
13use crate::jigsaw::references::{
14    NotChecked, Reference, ReferenceSet, ReferenceSite, SiteDetail, UncheckedSite, UncheckedSymbol,
15};
16use crate::jigsaw::surface::{AppPresence, Lookup, OtpAppPresence, OtpSurface, ReleaseSurface};
17use crate::model::macro_decl::{MacroBody, MacroKey};
18use crate::model::names::{
19    ApplicationName, Arity, BehaviourName, ConfKey, FieldName, FunctionName, MacroName, Mfa,
20    ModuleName, RecordName, SpecText, TypeName, ValidatorName,
21};
22use crate::model::non_empty::NonEmpty;
23use crate::model::normalised::NormalisedDefault;
24use crate::model::schema_files::PartialRef;
25use crate::model::snapshot::{FunArity, HeaderRef, Module};
26
27/// What the build patch says about one reference, with the places the
28/// plugin set uses it.
29#[derive(Debug, Clone, PartialEq, Eq)]
30pub struct Anchor<K> {
31    pub kind: K,
32    pub sites: BTreeSet<ReferenceSite>,
33}
34
35#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
36pub struct CallAnchor {
37    pub mfa: Mfa,
38    pub spec: Option<SpecText>,
39}
40
41#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
42pub struct RecordAnchor {
43    pub roots: BTreeSet<HeaderRef>,
44    pub header: HeaderRef,
45    pub name: RecordName,
46    pub fields: Vec<FieldName>,
47    pub defaults: BTreeMap<FieldName, Option<NormalisedDefault>>,
48    pub unset: BTreeSet<FieldName>,
49}
50
51#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
52pub struct MacroAtBuild {
53    pub key: MacroKey,
54    pub header: HeaderRef,
55    pub body: MacroBody,
56}
57
58#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
59pub struct MacroAnchor {
60    pub roots: BTreeSet<HeaderRef>,
61    pub entries: Vec<MacroAtBuild>,
62}
63
64#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
65pub struct BehaviourAnchor {
66    pub implementer: ModuleName,
67    pub behaviour: BehaviourName,
68    pub module: ModuleName,
69    pub implementer_exports: BTreeSet<FunArity>,
70    pub build_required: BTreeSet<FunArity>,
71}
72
73#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
74pub struct PartialAnchor {
75    pub partial: PartialRef,
76    pub keys: BTreeSet<ConfKey>,
77}
78
79#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
80pub struct TypeAnchor {
81    pub module: ModuleName,
82    pub name: TypeName,
83    pub arity: Arity,
84}
85
86#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
87pub struct AppAnchor {
88    pub app: ApplicationName,
89    pub required_by: NonEmpty<ApplicationName>,
90}
91
92/// A reference the build patch satisfies, checked once per host release.
93#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
94pub enum HostAnchor {
95    Call(CallAnchor),
96    Header(HeaderRef),
97    Record(RecordAnchor),
98    Macro(MacroAnchor),
99    Behaviour(BehaviourAnchor),
100    Type(TypeAnchor),
101    Partial(PartialAnchor),
102    Validator(ValidatorName),
103    App(AppAnchor),
104}
105
106/// A reference only OTP satisfies, checked once per OTP tag. OTP has no
107/// build side, so these ask for presence only.
108#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
109pub enum OtpAnchor {
110    Call(Mfa),
111    Type(TypeAnchor),
112    Behaviour {
113        name: BehaviourName,
114        module: ModuleName,
115    },
116    App(AppAnchor),
117}
118
119/// An app the plugin set needs that the build patch does not ship either:
120/// missing at every target.
121pub type UnprovidedApp = AppAnchor;
122
123#[derive(Debug, Clone, Default, PartialEq, Eq)]
124pub struct Anchored {
125    pub host: Vec<Anchor<HostAnchor>>,
126    pub otp: Vec<Anchor<OtpAnchor>>,
127    pub unprovided: Vec<Anchor<UnprovidedApp>>,
128    pub not_checked: BTreeMap<NotChecked, usize>,
129    pub unchecked: BTreeSet<UncheckedSite>,
130}
131
132impl Anchored {
133    fn count(&mut self, reason: NotChecked) {
134        *self.not_checked.entry(reason).or_default() += 1;
135    }
136
137    fn list_unresolved(&mut self, reference: &Reference, sites: &BTreeSet<ReferenceSite>) {
138        self.unchecked
139            .extend(sites.iter().map(|site| UncheckedSite {
140                symbol: UncheckedSymbol::UnresolvedAtBuild(reference.clone()),
141                file: site.file.clone(),
142                line: site.line,
143            }));
144    }
145
146    /// Distinct references compared at every target.
147    #[must_use]
148    pub fn checked(&self) -> usize {
149        self.host.len() + self.otp.len() + self.unprovided.len()
150    }
151}
152
153static MACRO_USE: LazyLock<Regex> =
154    LazyLock::new(|| Regex::new(r"\?\s*([A-Za-z_][A-Za-z0-9_]*)").expect("regex"));
155
156const PREDEFINED_MACROS: &[&str] = &[
157    "MODULE",
158    "MODULE_STRING",
159    "FILE",
160    "LINE",
161    "MACHINE",
162    "FUNCTION_NAME",
163    "FUNCTION_ARITY",
164    "OTP_RELEASE",
165    "BASE_MODULE",
166    "BASE_MODULE_STRING",
167];
168
169#[must_use]
170pub fn is_predefined_macro(name: &str) -> bool {
171    PREDEFINED_MACROS.contains(&name)
172}
173
174#[must_use]
175pub fn find_spec(module: &Module, function: &FunctionName, arity: Arity) -> Option<SpecText> {
176    module
177        .specs
178        .iter()
179        .find(|spec| &spec.name == function && spec.arity == arity)
180        .and_then(|spec| SpecText::new(spec.signature.clone()).ok())
181}
182
183fn is_elixir(module: &ModuleName) -> bool {
184    let name = module.as_str().trim_matches('\'');
185    name.starts_with("Elixir.")
186}
187
188/// Splits what the build patch cannot satisfy into the three kinds the
189/// report counts apart.
190fn classify_unresolved(build: &ReleaseSurface<'_>, module: &ModuleName) -> NotChecked {
191    if is_elixir(module) {
192        NotChecked::Elixir
193    } else if build.untracked_owner(module).is_some() {
194        NotChecked::Untracked
195    } else {
196        NotChecked::UnresolvedAtBuild
197    }
198}
199
200/// Splits `references` into what the build patch satisfies and what it
201/// does not. An OTP export that the build patch lacks becomes an OTP
202/// anchor. Every host-owned anchor also needs the app that owns it.
203#[must_use]
204pub fn anchor(
205    plugins: &PluginSet,
206    references: &ReferenceSet,
207    build: &ReleaseSurface<'_>,
208    otp: &[OtpSurface<'_>],
209) -> Anchored {
210    let mut out = Anchored::default();
211    let mut found = Found::default();
212    let mut needs: BTreeMap<ApplicationName, BTreeSet<ReferenceSite>> = BTreeMap::new();
213    let mut anchoring = Anchoring {
214        plugins,
215        references,
216        build,
217        otp,
218        out: &mut out,
219        found: &mut found,
220        needs: &mut needs,
221    };
222    for (reference, sites) in references.external() {
223        anchoring.reference(reference, sites);
224    }
225    anchoring.apps();
226    out.host = found.host.into_iter().map(Anchor::from).collect();
227    out.otp = found.otp.into_iter().map(Anchor::from).collect();
228    out
229}
230
231/// Anchors by what they compare, so two references that ask the same
232/// question of the same targets (the same host macro used from two files
233/// that include the same headers) are one anchor with both sites.
234#[derive(Default)]
235struct Found {
236    host: BTreeMap<HostAnchor, BTreeSet<ReferenceSite>>,
237    otp: BTreeMap<OtpAnchor, BTreeSet<ReferenceSite>>,
238}
239
240impl<K> From<(K, BTreeSet<ReferenceSite>)> for Anchor<K> {
241    fn from((kind, sites): (K, BTreeSet<ReferenceSite>)) -> Self {
242        Self { kind, sites }
243    }
244}
245
246struct Anchoring<'a, 's> {
247    plugins: &'a PluginSet,
248    references: &'a ReferenceSet,
249    build: &'a ReleaseSurface<'s>,
250    otp: &'a [OtpSurface<'s>],
251    out: &'a mut Anchored,
252    found: &'a mut Found,
253    needs: &'a mut BTreeMap<ApplicationName, BTreeSet<ReferenceSite>>,
254}
255
256impl Anchoring<'_, '_> {
257    fn host(&mut self, kind: HostAnchor, sites: &BTreeSet<ReferenceSite>, owner: &ApplicationName) {
258        self.need(owner, sites);
259        self.found
260            .host
261            .entry(kind)
262            .or_default()
263            .extend(sites.iter().cloned());
264    }
265
266    fn otp(&mut self, kind: OtpAnchor, sites: &BTreeSet<ReferenceSite>) {
267        self.found
268            .otp
269            .entry(kind)
270            .or_default()
271            .extend(sites.iter().cloned());
272    }
273
274    fn need(&mut self, app: &ApplicationName, sites: &BTreeSet<ReferenceSite>) {
275        self.needs
276            .entry(app.clone())
277            .or_default()
278            .extend(sites.iter().cloned());
279    }
280
281    fn otp_exports(&self, mfa: &Mfa) -> bool {
282        self.otp.iter().any(|surface| {
283            surface
284                .module(&mfa.module)
285                .is_some_and(|m| m.exports_function(&mfa.function, mfa.arity))
286        })
287    }
288
289    fn otp_exports_type(&self, module: &ModuleName, name: &TypeName, arity: Arity) -> bool {
290        self.otp.iter().any(|surface| {
291            surface
292                .module(module)
293                .is_some_and(|m| m.exports_type(name, arity))
294        })
295    }
296
297    fn reference(&mut self, reference: &Reference, sites: &BTreeSet<ReferenceSite>) {
298        match reference {
299            Reference::Call(mfa) => self.call(mfa, sites),
300            Reference::Record { includer, name } => {
301                let roots = self.roots_of(includer);
302                self.record(&roots, includer, name, sites);
303            }
304            Reference::Macro { includer, key } => {
305                let roots = self.roots_of(includer);
306                self.macro_use(&roots, includer, key, sites);
307            }
308            Reference::Header(header) => self.header(header, sites),
309            Reference::Behaviour {
310                implementer,
311                behaviour,
312            } => self.behaviour(implementer, behaviour, sites),
313            Reference::Type {
314                module,
315                name,
316                arity,
317            } => self.type_ref(module, name, *arity, sites),
318            Reference::Partial { partial, keys } => self.partial(partial, keys, sites),
319            Reference::Validator(name) => self.validator(name, sites),
320            Reference::App(app) => self.need(app, sites),
321        }
322    }
323
324    fn roots_of(&self, includer: &PluginFile) -> BTreeSet<HeaderRef> {
325        self.references
326            .host_includes(includer)
327            .cloned()
328            .unwrap_or_default()
329    }
330
331    fn call(&mut self, mfa: &Mfa, sites: &BTreeSet<ReferenceSite>) {
332        if let Some(entry) = self.build.module(&mfa.module)
333            && entry.module.exports_function(&mfa.function, mfa.arity)
334        {
335            let spec = find_spec(entry.module, &mfa.function, mfa.arity);
336            let owner = entry.app.clone();
337            self.host(
338                HostAnchor::Call(CallAnchor {
339                    mfa: mfa.clone(),
340                    spec,
341                }),
342                sites,
343                &owner,
344            );
345        } else if self.otp_exports(mfa) {
346            self.otp(OtpAnchor::Call(mfa.clone()), sites);
347        } else {
348            self.unmatched(
349                classify_unresolved(self.build, &mfa.module),
350                &Reference::Call(mfa.clone()),
351                sites,
352            );
353        }
354    }
355
356    fn unmatched(
357        &mut self,
358        reason: NotChecked,
359        reference: &Reference,
360        sites: &BTreeSet<ReferenceSite>,
361    ) {
362        if reason == NotChecked::UnresolvedAtBuild {
363            self.out.list_unresolved(reference, sites);
364        } else {
365            self.out.count(reason);
366        }
367    }
368
369    fn header(&mut self, header: &HeaderRef, sites: &BTreeSet<ReferenceSite>) {
370        if self.build.header(header).is_some() {
371            self.host(HostAnchor::Header(header.clone()), sites, &header.app);
372        } else if !self
373            .otp
374            .iter()
375            .any(|surface| surface.app(&header.app) != OtpAppPresence::Absent)
376        {
377            self.out
378                .list_unresolved(&Reference::Header(header.clone()), sites);
379        }
380    }
381
382    /// A use found nowhere is the includer's problem to report when one of
383    /// its includes could not be read; otherwise it is a count.
384    fn not_found(
385        &mut self,
386        includer: &PluginFile,
387        reference: &Reference,
388        sites: &BTreeSet<ReferenceSite>,
389    ) {
390        if !self.references.has_unresolved_include(includer) {
391            self.out.list_unresolved(reference, sites);
392        }
393    }
394
395    fn record(
396        &mut self,
397        roots: &BTreeSet<HeaderRef>,
398        includer: &PluginFile,
399        name: &RecordName,
400        sites: &BTreeSet<ReferenceSite>,
401    ) {
402        let Some((header, decl)) = self.build.find_record(roots, name) else {
403            let reference = Reference::Record {
404                includer: includer.clone(),
405                name: name.clone(),
406            };
407            self.not_found(includer, &reference, sites);
408            return;
409        };
410        let unset = sites
411            .iter()
412            .filter_map(|site| match &site.detail {
413                SiteDetail::Construction(construction) => Some(&construction.unset),
414                SiteDetail::Plain | SiteDetail::Call(_) => None,
415            })
416            .flatten()
417            .cloned()
418            .collect();
419        let anchor = RecordAnchor {
420            roots: roots.clone(),
421            header: header.clone(),
422            name: name.clone(),
423            fields: decl.fields.iter().map(|f| f.name.clone()).collect(),
424            defaults: decl
425                .fields
426                .iter()
427                .map(|f| (f.name.clone(), f.default.clone()))
428                .collect(),
429            unset,
430        };
431        self.host(HostAnchor::Record(anchor), sites, &header.app);
432    }
433
434    fn macro_use(
435        &mut self,
436        roots: &BTreeSet<HeaderRef>,
437        includer: &PluginFile,
438        key: &MacroKey,
439        sites: &BTreeSet<ReferenceSite>,
440    ) {
441        let mut entries = Vec::new();
442        let mut visited = BTreeSet::new();
443        self.collect_macro(roots, key, &mut visited, &mut entries);
444        let Some(first) = entries.first() else {
445            let reference = Reference::Macro {
446                includer: includer.clone(),
447                key: key.clone(),
448            };
449            self.not_found(includer, &reference, sites);
450            return;
451        };
452        let owner = first.header.app.clone();
453        let anchor = MacroAnchor {
454            roots: roots.clone(),
455            entries,
456        };
457        self.host(HostAnchor::Macro(anchor), sites, &owner);
458    }
459
460    /// The macro and, transitively, every macro its body names, as the
461    /// build patch defines them: all of them are expanded into the plugin.
462    fn collect_macro(
463        &self,
464        roots: &BTreeSet<HeaderRef>,
465        key: &MacroKey,
466        visited: &mut BTreeSet<MacroKey>,
467        entries: &mut Vec<MacroAtBuild>,
468    ) {
469        let found = self.build.find_macro(roots, key).or_else(|| {
470            key.arity.and_then(|_| {
471                self.build
472                    .find_macro(roots, &MacroKey::object_like(key.name.clone()))
473            })
474        });
475        let Some((header, decl)) = found else {
476            return;
477        };
478        if !visited.insert(decl.key.clone()) {
479            return;
480        }
481        entries.push(MacroAtBuild {
482            key: decl.key.clone(),
483            header,
484            body: decl.body.clone(),
485        });
486        let MacroBody::Text(body) = &decl.body else {
487            return;
488        };
489        for used in macro_uses(body.as_str()) {
490            self.collect_macro(roots, &used, visited, entries);
491        }
492    }
493
494    fn behaviour(
495        &mut self,
496        implementer: &ModuleName,
497        behaviour: &BehaviourName,
498        sites: &BTreeSet<ReferenceSite>,
499    ) {
500        let Ok(module) = ModuleName::from_str(behaviour.as_str()) else {
501            return;
502        };
503        if let Some(entry) = self.build.module(&module) {
504            let required = required_callbacks(entry.module);
505            let anchor = BehaviourAnchor {
506                implementer: implementer.clone(),
507                behaviour: behaviour.clone(),
508                module,
509                implementer_exports: self
510                    .references
511                    .exports_of(implementer)
512                    .cloned()
513                    .unwrap_or_default(),
514                build_required: required,
515            };
516            let owner = entry.app.clone();
517            self.host(HostAnchor::Behaviour(anchor), sites, &owner);
518        } else if self
519            .otp
520            .iter()
521            .any(|surface| surface.module(&module).is_some())
522        {
523            self.otp(
524                OtpAnchor::Behaviour {
525                    name: behaviour.clone(),
526                    module,
527                },
528                sites,
529            );
530        } else {
531            self.unmatched(
532                classify_unresolved(self.build, &module),
533                &Reference::Behaviour {
534                    implementer: implementer.clone(),
535                    behaviour: behaviour.clone(),
536                },
537                sites,
538            );
539        }
540    }
541
542    fn type_ref(
543        &mut self,
544        module: &ModuleName,
545        name: &TypeName,
546        arity: Arity,
547        sites: &BTreeSet<ReferenceSite>,
548    ) {
549        let anchor = TypeAnchor {
550            module: module.clone(),
551            name: name.clone(),
552            arity,
553        };
554        if let Some(entry) = self.build.module(module)
555            && entry.module.exports_type(name, arity)
556        {
557            let owner = entry.app.clone();
558            self.host(HostAnchor::Type(anchor), sites, &owner);
559        } else if self.otp_exports_type(module, name, arity) {
560            self.otp(OtpAnchor::Type(anchor), sites);
561        } else {
562            self.unmatched(
563                classify_unresolved(self.build, module),
564                &Reference::Type {
565                    module: module.clone(),
566                    name: name.clone(),
567                    arity,
568                },
569                sites,
570            );
571        }
572    }
573
574    fn partial(
575        &mut self,
576        partial: &PartialRef,
577        keys: &BTreeSet<ConfKey>,
578        sites: &BTreeSet<ReferenceSite>,
579    ) {
580        match self.build.partial(partial) {
581            Lookup::Found(file) => {
582                let anchor = PartialAnchor {
583                    partial: partial.clone(),
584                    keys: keys.intersection(&file.mappings).cloned().collect(),
585                };
586                self.host(HostAnchor::Partial(anchor), sites, &partial.app);
587            }
588            Lookup::Missing | Lookup::Stopped(_) => {
589                if self.build.untracked_dependency(&partial.app) {
590                    self.out.count(NotChecked::Untracked);
591                } else {
592                    let reference = Reference::Partial {
593                        partial: partial.clone(),
594                        keys: keys.clone(),
595                    };
596                    self.out.list_unresolved(&reference, sites);
597                }
598            }
599        }
600    }
601
602    fn validator(&mut self, name: &ValidatorName, sites: &BTreeSet<ReferenceSite>) {
603        match self.build.validator(name) {
604            Lookup::Found(app) => {
605                let owner = app.clone();
606                self.host(HostAnchor::Validator(name.clone()), sites, &owner);
607            }
608            Lookup::Missing | Lookup::Stopped(_) => {
609                self.out
610                    .list_unresolved(&Reference::Validator(name.clone()), sites);
611            }
612        }
613    }
614
615    /// Settles every app the plugin set needs: OTP's if some OTP tag in the
616    /// run provides it, otherwise the host's, or missing everywhere when the
617    /// build patch itself does not ship it.
618    fn apps(&mut self) {
619        let needs = std::mem::take(self.needs);
620        for (app, sites) in needs {
621            if self.plugins.contains_app(&app) {
622                continue;
623            }
624            let required_by: BTreeSet<ApplicationName> =
625                sites.iter().map(|site| site.file.app.clone()).collect();
626            let Ok(required_by) = NonEmpty::try_from(required_by.into_iter().collect::<Vec<_>>())
627            else {
628                continue;
629            };
630            let anchor = AppAnchor { app, required_by };
631            if self
632                .otp
633                .iter()
634                .any(|surface| surface.app(&anchor.app) != OtpAppPresence::Absent)
635            {
636                self.otp(OtpAnchor::App(anchor), &sites);
637            } else if self.build.shipped().lookup(&anchor.app) == AppPresence::Absent {
638                self.out.unprovided.push(Anchor {
639                    kind: anchor,
640                    sites,
641                });
642            } else {
643                self.found
644                    .host
645                    .entry(HostAnchor::App(anchor))
646                    .or_default()
647                    .extend(sites);
648            }
649        }
650    }
651}
652
653/// The macros a body names with `?NAME`, with the arity of a use that has
654/// an argument list.
655fn macro_uses(body: &str) -> Vec<MacroKey> {
656    let mut keys = Vec::new();
657    for caps in MACRO_USE.captures_iter(body) {
658        let whole = caps.get(0).expect("capture");
659        let name = &caps[1];
660        if is_predefined_macro(name) {
661            continue;
662        }
663        let Ok(name) = MacroName::from_str(name) else {
664            continue;
665        };
666        let rest = &body[whole.end()..];
667        let arity = rest
668            .trim_start()
669            .strip_prefix('(')
670            .and_then(|after| match scan_arity(after) {
671                ScanArity::Exact(n) => Some(Arity::new(n)),
672                ScanArity::Unterminated => None,
673            });
674        keys.push(MacroKey { name, arity });
675    }
676    keys
677}
678
679/// The callbacks a behaviour module requires: declared and not optional.
680#[must_use]
681pub fn required_callbacks(module: &Module) -> BTreeSet<FunArity> {
682    let optional: BTreeSet<&FunArity> = module.optional_callbacks.iter().collect();
683    module
684        .callbacks
685        .iter()
686        .map(|callback| FunArity {
687            name: callback.name.clone(),
688            arity: callback.arity,
689        })
690        .filter(|callback| !optional.contains(callback))
691        .collect()
692}
backhopper_core/jigsaw/anchor.rs

backhopper_core/jigsaw/
anchor.rs
