backhopper_core/jigsaw/
surface.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, VecDeque};
6use std::iter;
7
8use crate::jigsaw::findings::Stop;
9use crate::jigsaw::plan::JigsawPlan;
10use crate::model::app_manifest::{ManifestDeps, ManifestUnreadable};
11use crate::model::macro_decl::{MacroDecl, MacroKey};
12use crate::model::names::{ApplicationName, DependencyName, ModuleName, RecordName, ValidatorName};
13use crate::model::pin::Pin;
14use crate::model::schema_files::{PartialFile, PartialRef};
15use crate::model::snapshot::{HeaderRef, HrlFile, Module, RecordDecl, Snapshot, state};
16
17/// The app of every module and header of one snapshot, in snapshot order.
18/// `load` makes one per snapshot, and only for a snapshot where no entry
19/// lacks an app.
20#[derive(Debug, Clone, PartialEq, Eq)]
21pub struct PinApps {
22    modules: Vec<ApplicationName>,
23    headers: Vec<ApplicationName>,
24}
25
26impl PinApps {
27    #[must_use]
28    pub fn of(snapshot: &Snapshot<state::Canonical>) -> Option<Self> {
29        let modules = snapshot
30            .modules()
31            .iter()
32            .map(|m| m.app.clone())
33            .collect::<Option<Vec<_>>>()?;
34        let headers = snapshot
35            .headers()
36            .iter()
37            .map(|h| h.app.clone())
38            .collect::<Option<Vec<_>>>()?;
39        Some(Self { modules, headers })
40    }
41}
42
43#[derive(Debug, Clone, Copy)]
44pub struct SurfaceSource<'s> {
45    pub snapshot: &'s Snapshot<state::Canonical>,
46    pub apps: &'s PinApps,
47}
48
49/// Whether an app is among the apps a side provides. Closures stop at
50/// apps they cannot read through, which makes "not in the closure" an
51/// answer of its own.
52#[derive(Debug, Clone, Copy, PartialEq, Eq)]
53pub enum AppPresence {
54    Provided,
55    Absent,
56    Stopped(Stop),
57}
58
59/// An app the snapshot leaves out by configuration ships with OTP all the same.
60#[derive(Debug, Clone, Copy, PartialEq, Eq)]
61pub enum OtpAppPresence {
62    Provided,
63    Absent,
64    Excluded,
65}
66
67/// Why the closure over manifests could not continue through an app.
68#[derive(Debug, Clone, PartialEq, Eq)]
69pub enum Blocker {
70    Manifest(ManifestUnreadable),
71    Untracked,
72}
73
74impl Blocker {
75    #[must_use]
76    pub fn stop(&self) -> Stop {
77        match self {
78            Self::Manifest(_) => Stop::UnreadableManifest,
79            Self::Untracked => Stop::UntrackedApp,
80        }
81    }
82}
83
84/// The apps a host release ships: the closure of its release roots over the
85/// manifests of the host and its pinned dependencies. There is no
86/// `contains`, so a closure that stopped short cannot be read as a `bool`.
87#[derive(Debug, Clone, PartialEq, Eq)]
88pub struct ShippedApps {
89    provided: BTreeSet<ApplicationName>,
90    blockers: BTreeMap<ApplicationName, Blocker>,
91}
92
93impl ShippedApps {
94    fn closure(
95        roots: &[ApplicationName],
96        manifests: &BTreeMap<&ApplicationName, &ManifestDeps>,
97        untracked: &BTreeSet<DependencyName>,
98    ) -> Self {
99        let mut provided = BTreeSet::new();
100        let mut blockers = BTreeMap::new();
101        let mut queue: VecDeque<&ApplicationName> = roots.iter().collect();
102        while let Some(app) = queue.pop_front() {
103            if !provided.insert(app.clone()) {
104                continue;
105            }
106            match manifests.get(app) {
107                Some(ManifestDeps::Listed(requires)) => queue.extend(requires),
108                Some(ManifestDeps::Unreadable(reason)) => {
109                    blockers.insert(app.clone(), Blocker::Manifest(reason.clone()));
110                }
111                None if untracked.iter().any(|dep| dep.as_str() == app.as_str()) => {
112                    blockers.insert(app.clone(), Blocker::Untracked);
113                }
114                None => {}
115            }
116        }
117        Self { provided, blockers }
118    }
119
120    #[must_use]
121    pub fn lookup(&self, app: &ApplicationName) -> AppPresence {
122        if self.provided.contains(app) {
123            AppPresence::Provided
124        } else {
125            self.stopped()
126                .map_or(AppPresence::Absent, AppPresence::Stopped)
127        }
128    }
129
130    #[must_use]
131    pub fn stopped(&self) -> Option<Stop> {
132        self.blockers.values().map(Blocker::stop).min()
133    }
134
135    /// The apps the closure stopped at, with why.
136    #[must_use]
137    pub fn blockers(&self) -> &BTreeMap<ApplicationName, Blocker> {
138        &self.blockers
139    }
140}
141
142#[derive(Debug, Clone, Copy)]
143pub struct ModuleEntry<'s> {
144    pub module: &'s Module,
145    pub app: &'s ApplicationName,
146}
147
148/// What a schema-element lookup found, or why it could not tell.
149#[derive(Debug, Clone, Copy, PartialEq, Eq)]
150pub enum Lookup<T> {
151    Found(T),
152    Missing,
153    Stopped(Stop),
154}
155
156/// One host release as the analysis reads it: the host snapshot and its
157/// pinned dependency snapshots, indexed.
158#[derive(Debug)]
159pub struct ReleaseSurface<'s> {
160    modules: BTreeMap<&'s ModuleName, ModuleEntry<'s>>,
161    headers: BTreeMap<HeaderRef, &'s HrlFile>,
162    partials: BTreeMap<PartialRef, &'s PartialFile>,
163    validators: BTreeMap<&'s ValidatorName, Vec<&'s ApplicationName>>,
164    apps: BTreeSet<&'s ApplicationName>,
165    shipped: ShippedApps,
166    untracked: &'s BTreeSet<DependencyName>,
167}
168
169impl<'s> ReleaseSurface<'s> {
170    #[must_use]
171    pub fn new(
172        sources: &[SurfaceSource<'s>],
173        roots: &[ApplicationName],
174        untracked: &'s BTreeSet<DependencyName>,
175    ) -> Self {
176        let mut modules = BTreeMap::new();
177        let mut headers = BTreeMap::new();
178        let mut partials = BTreeMap::new();
179        let mut validators: BTreeMap<&ValidatorName, Vec<&ApplicationName>> = BTreeMap::new();
180        let mut manifests: BTreeMap<&ApplicationName, &ManifestDeps> = BTreeMap::new();
181        for source in sources {
182            let snapshot = source.snapshot;
183            for (module, app) in snapshot.modules().iter().zip(&source.apps.modules) {
184                modules
185                    .entry(&module.name)
186                    .or_insert(ModuleEntry { module, app });
187            }
188            for (header, app) in snapshot.headers().iter().zip(&source.apps.headers) {
189                let reference = HeaderRef {
190                    app: app.clone(),
191                    app_path: header.app_path().unwrap_or_else(|| header.path.clone()),
192                };
193                headers.entry(reference).or_insert(header);
194            }
195            for partial in snapshot.partials() {
196                partials.entry(partial.partial_ref()).or_insert(partial);
197                for name in &partial.validators {
198                    validators.entry(name).or_default().push(&partial.app);
199                }
200            }
201            for schema in snapshot.schemas() {
202                for name in &schema.validators {
203                    validators.entry(name).or_default().push(&schema.app);
204                }
205            }
206            for manifest in snapshot.apps() {
207                manifests
208                    .entry(&manifest.name)
209                    .or_insert(&manifest.requires);
210            }
211        }
212        let apps = manifests.keys().copied().collect();
213        Self {
214            modules,
215            headers,
216            partials,
217            validators,
218            apps,
219            shipped: ShippedApps::closure(roots, &manifests, untracked),
220            untracked,
221        }
222    }
223
224    #[must_use]
225    pub fn module(&self, name: &ModuleName) -> Option<&ModuleEntry<'s>> {
226        self.modules.get(name)
227    }
228
229    #[must_use]
230    pub fn header(&self, reference: &HeaderRef) -> Option<&'s HrlFile> {
231        self.headers.get(reference).copied()
232    }
233
234    #[must_use]
235    pub fn shipped(&self) -> &ShippedApps {
236        &self.shipped
237    }
238
239    /// The headers reachable from `roots` through their `-include` lines,
240    /// roots first. A header the release lacks ends its branch.
241    #[must_use]
242    pub fn header_closure(&self, roots: &BTreeSet<HeaderRef>) -> Vec<(HeaderRef, &'s HrlFile)> {
243        let mut seen: BTreeSet<HeaderRef> = BTreeSet::new();
244        let mut queue: VecDeque<HeaderRef> = roots.iter().cloned().collect();
245        let mut out = Vec::new();
246        while let Some(reference) = queue.pop_front() {
247            if !seen.insert(reference.clone()) {
248                continue;
249            }
250            let Some(header) = self.header(&reference) else {
251                continue;
252            };
253            queue.extend(header.includes.iter().cloned());
254            out.push((reference, header));
255        }
256        out
257    }
258
259    #[must_use]
260    pub fn find_record(
261        &self,
262        roots: &BTreeSet<HeaderRef>,
263        name: &RecordName,
264    ) -> Option<(HeaderRef, &'s RecordDecl)> {
265        self.header_closure(roots)
266            .into_iter()
267            .find_map(|(reference, header)| {
268                header
269                    .records
270                    .iter()
271                    .find(|record| &record.name == name)
272                    .map(|record| (reference, record))
273            })
274    }
275
276    #[must_use]
277    pub fn find_macro(
278        &self,
279        roots: &BTreeSet<HeaderRef>,
280        key: &MacroKey,
281    ) -> Option<(HeaderRef, &'s MacroDecl)> {
282        self.header_closure(roots)
283            .into_iter()
284            .find_map(|(reference, header)| {
285                header
286                    .defines
287                    .iter()
288                    .find(|decl| &decl.key == key)
289                    .map(|decl| (reference, decl))
290            })
291    }
292
293    /// Whether any root header exists in the release.
294    #[must_use]
295    pub fn has_any_header(&self, roots: &BTreeSet<HeaderRef>) -> bool {
296        roots.iter().any(|root| self.headers.contains_key(root))
297    }
298
299    #[must_use]
300    pub fn untracked_dependency(&self, app: &ApplicationName) -> bool {
301        self.untracked
302            .iter()
303            .any(|dep| dep.as_str() == app.as_str())
304    }
305
306    /// Every app the release's snapshots carry a manifest for, shipped or
307    /// not.
308    #[must_use]
309    pub fn tree_apps(&self) -> &BTreeSet<&'s ApplicationName> {
310        &self.apps
311    }
312
313    /// Cuttlefish loads only the schemas of the apps on the node, so a
314    /// partial is found only in an app the release ships.
315    #[must_use]
316    pub fn partial(&self, reference: &PartialRef) -> Lookup<&'s PartialFile> {
317        match self.shipped.lookup(&reference.app) {
318            AppPresence::Provided => self
319                .partials
320                .get(reference)
321                .map_or(Lookup::Missing, |file| Lookup::Found(*file)),
322            AppPresence::Absent => Lookup::Missing,
323            AppPresence::Stopped(stop) => Lookup::Stopped(stop),
324        }
325    }
326
327    /// The shipped app that defines a validator. A closure that stopped
328    /// short may have missed the app that does.
329    #[must_use]
330    pub fn validator(&self, name: &ValidatorName) -> Lookup<&'s ApplicationName> {
331        let owners = self.validators.get(name).map_or(&[][..], Vec::as_slice);
332        if let Some(app) = owners
333            .iter()
334            .find(|app| self.shipped.lookup(app) == AppPresence::Provided)
335        {
336            return Lookup::Found(app);
337        }
338        self.shipped
339            .stopped()
340            .map_or(Lookup::Missing, Lookup::Stopped)
341    }
342
343    /// A module the host's snapshots lack, owned by a dependency the plan
344    /// does not track: the module is the dependency's name, or starts with
345    /// it and an underscore.
346    #[must_use]
347    pub fn untracked_owner(&self, module: &ModuleName) -> Option<&'s DependencyName> {
348        let name = module.as_str();
349        self.untracked.iter().find(|dep| {
350            name == dep.as_str()
351                || name
352                    .strip_prefix(dep.as_str())
353                    .is_some_and(|rest| rest.starts_with('_'))
354        })
355    }
356}
357
358/// One OTP tag: modules, exports and apps only.
359#[derive(Debug)]
360pub struct OtpSurface<'s> {
361    snapshot: &'s Snapshot<state::Canonical>,
362    apps: BTreeSet<&'s ApplicationName>,
363    excluded: &'s BTreeSet<ApplicationName>,
364}
365
366impl<'s> OtpSurface<'s> {
367    #[must_use]
368    pub fn new(
369        snapshot: &'s Snapshot<state::Canonical>,
370        excluded: &'s BTreeSet<ApplicationName>,
371    ) -> Self {
372        Self {
373            snapshot,
374            apps: snapshot.apps().iter().map(|app| &app.name).collect(),
375            excluded,
376        }
377    }
378
379    #[must_use]
380    pub fn module(&self, name: &ModuleName) -> Option<&'s Module> {
381        self.snapshot.module_named(name)
382    }
383
384    /// An OTP app the snapshot leaves out by configuration ships with OTP
385    /// all the same, so it is not absent.
386    #[must_use]
387    pub fn app(&self, app: &ApplicationName) -> OtpAppPresence {
388        if self.apps.contains(app) {
389            OtpAppPresence::Provided
390        } else if self.excluded.contains(app) {
391            OtpAppPresence::Excluded
392        } else {
393            OtpAppPresence::Absent
394        }
395    }
396}
397
398/// Every release and OTP tag of a loaded plan, in plan order.
399#[derive(Debug)]
400pub struct PlanSurfaces<'s> {
401    releases: Vec<ReleaseSurface<'s>>,
402    otp: Vec<OtpSurface<'s>>,
403}
404
405impl<'s> PlanSurfaces<'s> {
406    pub(crate) fn new(
407        plan: &'s JigsawPlan,
408        snapshots: &'s BTreeMap<Pin, Snapshot<state::Canonical>>,
409        pin_apps: &'s BTreeMap<Pin, PinApps>,
410    ) -> Self {
411        let source = |pin: &Pin| {
412            Some(SurfaceSource {
413                snapshot: snapshots.get(pin)?,
414                apps: pin_apps.get(pin)?,
415            })
416        };
417        let releases = plan
418            .releases()
419            .iter()
420            .map(|release| {
421                let host_pin = Pin::new(plan.host_project().clone(), release.tag.tag().clone());
422                let roots: &[ApplicationName] = snapshots
423                    .get(&host_pin)
424                    .and_then(|snapshot| snapshot.header().host_facts.as_ref())
425                    .map_or(&[], |facts| facts.release_roots.as_slice());
426                let pins = release
427                    .pins
428                    .iter()
429                    .map(|(project, tag)| Pin::new(project.clone(), tag.clone()));
430                let sources: Vec<_> = iter::once(host_pin)
431                    .chain(pins)
432                    .filter_map(|pin| source(&pin))
433                    .collect();
434                ReleaseSurface::new(&sources, roots, plan.untracked_dependencies())
435            })
436            .collect();
437        let otp = plan
438            .otp_lines()
439            .iter()
440            .flat_map(|line| line.tags().iter())
441            .filter_map(|tag| {
442                let pin = Pin::new(plan.otp_project().clone(), tag.tag().clone());
443                snapshots
444                    .get(&pin)
445                    .map(|snapshot| OtpSurface::new(snapshot, plan.excluded_otp_apps()))
446            })
447            .collect();
448        Self { releases, otp }
449    }
450
451    /// The build patch: the newest release of the series.
452    #[must_use]
453    pub fn build(&self) -> &ReleaseSurface<'s> {
454        &self.releases[self.releases.len() - 1]
455    }
456
457    #[must_use]
458    pub fn releases(&self) -> &[ReleaseSurface<'s>] {
459        &self.releases
460    }
461
462    #[must_use]
463    pub fn otp(&self) -> &[OtpSurface<'s>] {
464        &self.otp
465    }
466}
backhopper_core/jigsaw/surface.rs

backhopper_core/jigsaw/
surface.rs
