brokk_bifrost_cpp/
imports.rs

1//! `#include` parsing and the workspace-wide include-target index.
2//!
3//! `analyzer/cpp/imports.rs` in `brokk-bifrost-analysis` keeps the
4//! `ImportAnalysisProvider` / `TestDetectionProvider` impls and the `OnceLock` /
5//! `PoolSafeMemo` cells that memoize [`IncludeTargetIndex`] and the reverse
6//! include map on the analyzer; every decision they make is a function here.
7
8use brokk_bifrost_core::analyzer::ProjectFile;
9use brokk_bifrost_core::analyzer::model::ImportInfo;
10use brokk_bifrost_core::analyzer::project::Project;
11use brokk_bifrost_core::hash::{HashMap, HashSet};
12use regex::Regex;
13use std::collections::BTreeSet;
14use std::path::{Path, PathBuf};
15use std::sync::OnceLock;
16
17/// Workspace-wide resolution table for `#include` targets: every analyzable file
18/// keyed both by its full workspace-relative path and by its bare file name.
19///
20/// Built once per analyzer generation from `all_files()` and consulted by every
21/// include-visibility walk, so a header's dependents resolve without a
22/// filesystem probe per include line.
23pub struct IncludeTargetIndex {
24    by_rel_path: HashMap<PathBuf, Vec<ProjectFile>>,
25    by_file_name: HashMap<String, Vec<ProjectFile>>,
26}
27
28impl IncludeTargetIndex {
29    pub fn build<'a>(files: impl IntoIterator<Item = &'a ProjectFile>) -> Self {
30        let mut by_rel_path: HashMap<PathBuf, Vec<ProjectFile>> = HashMap::default();
31        let mut by_file_name: HashMap<String, Vec<ProjectFile>> = HashMap::default();
32        for file in files {
33            by_rel_path
34                .entry(file.rel_path().to_path_buf())
35                .or_default()
36                .push(file.clone());
37            if let Some(file_name) = file.rel_path().file_name().and_then(|value| value.to_str()) {
38                by_file_name
39                    .entry(file_name.to_string())
40                    .or_default()
41                    .push(file.clone());
42            }
43        }
44        Self {
45            by_rel_path,
46            by_file_name,
47        }
48    }
49
50    pub fn resolve_indexed(&self, include: &str) -> Vec<ProjectFile> {
51        let include_path = Path::new(include);
52        let mut matched = HashSet::default();
53        let mut resolved = Vec::new();
54        if let Some(targets) = self.by_rel_path.get(include_path) {
55            for target in targets {
56                if matched.insert(target.clone()) {
57                    resolved.push(target.clone());
58                }
59            }
60        }
61        for suffix in string_suffixes(include) {
62            if let Some(targets) = self.by_file_name.get(suffix) {
63                for target in targets {
64                    if matched.insert(target.clone()) {
65                        resolved.push(target.clone());
66                    }
67                }
68            }
69        }
70        resolved
71    }
72
73    fn resolve_direct(&self, source_file: &ProjectFile, include: &str) -> Vec<ProjectFile> {
74        let include_path = Path::new(include);
75        let mut matched = HashSet::default();
76        let mut resolved = Vec::new();
77        if include_path.is_absolute() {
78            if let Some(rel_path) = project_relative_include_path(source_file.root(), include_path)
79            {
80                self.extend_rel_path(&rel_path, &mut matched, &mut resolved);
81            }
82            return resolved;
83        }
84
85        let source_relative = ProjectFile::new(
86            source_file.root().to_path_buf(),
87            source_file.parent().join(include_path),
88        );
89        self.extend_rel_path(source_relative.rel_path(), &mut matched, &mut resolved);
90
91        let project_relative =
92            ProjectFile::new(source_file.root().to_path_buf(), include_path.to_path_buf());
93        self.extend_rel_path(project_relative.rel_path(), &mut matched, &mut resolved);
94        resolved
95    }
96
97    fn extend_rel_path(
98        &self,
99        rel_path: &Path,
100        matched: &mut HashSet<ProjectFile>,
101        out: &mut Vec<ProjectFile>,
102    ) {
103        if let Some(targets) = self.by_rel_path.get(rel_path) {
104            for target in targets {
105                if matched.insert(target.clone()) {
106                    out.push(target.clone());
107                }
108            }
109        }
110    }
111
112    fn resolve_unique_fallback(
113        &self,
114        source_file: &ProjectFile,
115        include: &str,
116    ) -> Vec<ProjectFile> {
117        let include_path = Path::new(include);
118        let matches: Vec<_> = self
119            .resolve_indexed(include)
120            .into_iter()
121            .filter(|file| {
122                if include_path.components().count() > 1 {
123                    file.rel_path().ends_with(include_path)
124                } else {
125                    file.rel_path()
126                        .file_name()
127                        .is_some_and(|name| name == include_path)
128                }
129            })
130            .collect();
131        if matches.len() == 1 {
132            return matches;
133        }
134        let source_reachable = matches
135            .into_iter()
136            .filter(|file| {
137                (0..include_path.components().count())
138                    .try_fold(file.rel_path(), |path, _| path.parent())
139                    .is_some_and(|root| source_file.rel_path().starts_with(root))
140            })
141            .collect::<Vec<_>>();
142        if source_reachable.len() == 1 {
143            source_reachable
144        } else {
145            Vec::new()
146        }
147    }
148}
149
150fn string_suffixes(value: &str) -> impl Iterator<Item = &str> {
151    value.char_indices().map(|(index, _)| &value[index..])
152}
153
154pub fn parse_quoted_include(line: &str) -> Option<String> {
155    let trimmed = line.trim();
156    let quote_start = trimmed.find('"')?;
157    let quote_end = trimmed[quote_start + 1..].find('"')?;
158    Some(trimmed[quote_start + 1..quote_start + 1 + quote_end].to_string())
159}
160
161pub fn parse_include_path(line: &str) -> Option<String> {
162    if let Some(path) = parse_quoted_include(line) {
163        return Some(path);
164    }
165    let trimmed = line.trim();
166    let angle_start = trimmed.find('<')?;
167    let angle_end = trimmed[angle_start + 1..].find('>')?;
168    Some(trimmed[angle_start + 1..angle_start + 1 + angle_end].to_string())
169}
170
171pub fn resolve_include_targets(
172    project: &dyn Project,
173    source_file: &ProjectFile,
174    include: &str,
175) -> Vec<ProjectFile> {
176    let mut candidates = Vec::new();
177    let include_path = Path::new(include);
178    let source_root = project.root().to_path_buf();
179    let relative_path = if include_path.is_absolute() {
180        match project_relative_include_path(project.root(), include_path) {
181            Some(path) => path,
182            None => return candidates,
183        }
184    } else {
185        source_file.parent().join(include_path)
186    };
187    let relative_file = ProjectFile::new(source_root.clone(), relative_path);
188    if relative_file.exists() {
189        candidates.push(relative_file);
190    }
191    if !include_path.is_absolute() {
192        let project_relative_file = ProjectFile::new(source_root.clone(), include_path);
193        if project_relative_file.exists() {
194            candidates.push(project_relative_file);
195        }
196    }
197
198    candidates.sort();
199    candidates.dedup();
200    candidates
201}
202
203pub fn resolve_include_targets_with_index(
204    source_file: &ProjectFile,
205    include: &str,
206    include_targets: &IncludeTargetIndex,
207) -> Vec<ProjectFile> {
208    let mut candidates = include_targets.resolve_direct(source_file, include);
209    if !candidates.is_empty() {
210        return candidates;
211    }
212    if Path::new(include).is_absolute() {
213        return candidates;
214    }
215    candidates.extend(include_targets.resolve_unique_fallback(source_file, include));
216    if candidates.is_empty()
217        && let Some(template) = header_template_include_spelling(include)
218    {
219        candidates = include_targets.resolve_direct(source_file, &template);
220        if candidates.is_empty() {
221            candidates.extend(include_targets.resolve_unique_fallback(source_file, &template));
222        }
223    }
224    candidates
225}
226
227/// The `.hin` header-template spelling of an `.h` include, or `None` for any
228/// other include. A `.hin` file is the committed template the build turns
229/// into the like-named public header in the same directory -- krb5 generates
230/// `include/krb5/krb5.h` from `include/krb5/krb5.hin` (#2372) -- so in a tree
231/// without build artifacts the template is the only file holding those
232/// declarations. The retry runs only after every `.h` rule has failed, so a
233/// real header always wins over its template.
234fn header_template_include_spelling(include: &str) -> Option<String> {
235    let path = Path::new(include);
236    (path.extension() == Some(std::ffi::OsStr::new("h")))
237        .then(|| path.with_extension("hin").to_string_lossy().into_owned())
238}
239
240pub fn resolve_direct_include_targets_with_index(
241    source_file: &ProjectFile,
242    include: &str,
243    include_targets: &IncludeTargetIndex,
244) -> Vec<ProjectFile> {
245    include_targets.resolve_direct(source_file, include)
246}
247
248fn project_relative_include_path(project_root: &Path, include_path: &Path) -> Option<PathBuf> {
249    let canonical_root = project_root
250        .canonicalize()
251        .unwrap_or_else(|_| project_root.to_path_buf());
252    let canonical_include = include_path
253        .canonicalize()
254        .unwrap_or_else(|_| include_path.to_path_buf());
255    canonical_include
256        .strip_prefix(&canonical_root)
257        .map(Path::to_path_buf)
258        .or_else(|_| {
259            include_path
260                .strip_prefix(project_root)
261                .map(Path::to_path_buf)
262        })
263        .ok()
264        .or_else(|| lexical_project_relative_include_path(&canonical_root, &canonical_include))
265        .or_else(|| lexical_project_relative_include_path(project_root, include_path))
266}
267
268/// The claim edges `sources` contribute: for each source file, the workspace
269/// files it pulls in by quoted `#include` that no language's extension registry
270/// claims (#1837).
271///
272/// `sources` pairs each already-analyzed C++ file with the `ImportInfo` rows
273/// recorded for it; `claimable` is the caller's set of workspace files with an
274/// extension no language owns. `abseil`'s `.inc` translation-unit fragments are
275/// the motivating case: nothing indexes them today, so every declaration they
276/// hold is invisible in both directions.
277///
278/// Only quoted includes participate. An angled include names a search path the
279/// analyzer does not model, so resolving one against workspace file names would
280/// claim files the compiler would never reach.
281///
282/// Edges rather than a flat set, because the caller both closes the relation
283/// transitively and drops a claim when the last `#include` naming it goes away;
284/// both need to know which source contributed which target. A source with no
285/// claimable include contributes no entry.
286///
287/// The result depends only on `sources`, `claimable` and the resolution rules
288/// in this module -- never on the order either collection arrives in.
289pub fn included_claimable_files(
290    sources: &[(ProjectFile, Vec<ImportInfo>)],
291    claimable: &BTreeSet<ProjectFile>,
292) -> HashMap<ProjectFile, BTreeSet<ProjectFile>> {
293    let mut edges: HashMap<ProjectFile, BTreeSet<ProjectFile>> = HashMap::default();
294    if claimable.is_empty() || sources.is_empty() {
295        return edges;
296    }
297    let index = IncludeTargetIndex::build(claimable.iter());
298    for (source_file, imports) in sources {
299        let mut targets = BTreeSet::new();
300        for include in imports
301            .iter()
302            .filter_map(|import| parse_quoted_include(&import.raw_snippet))
303        {
304            targets.extend(resolve_include_targets_with_index(
305                source_file,
306                &include,
307                &index,
308            ));
309        }
310        if !targets.is_empty() {
311            edges.insert(source_file.clone(), targets);
312        }
313    }
314    edges
315}
316
317pub fn quoted_include_paths(parsed: &[String]) -> Vec<String> {
318    parsed
319        .iter()
320        .filter_map(|line| parse_quoted_include(line))
321        .collect()
322}
323
324pub fn include_paths(parsed: &[String]) -> Vec<String> {
325    parsed
326        .iter()
327        .filter_map(|line| parse_include_path(line))
328        .collect()
329}
330
331/// The capitalized identifiers a C++ source mentions, used to decide which of a
332/// declaration's `#include` lines are relevant to it.
333///
334/// Deliberately lexical, and the only place in this crate that is: the input is
335/// a rendered source excerpt whose enclosing translation unit is not available
336/// to parse, and the output feeds a *filter* over already-resolved includes, so
337/// an over-broad token set costs recall on the filter rather than inventing a
338/// declaration. Every fleet language has this same shape
339/// (`brokk_bifrost_python::graph_support::extract_type_identifiers` is the
340/// closest sibling).
341pub fn extract_type_identifiers(source: &str) -> BTreeSet<String> {
342    static IDENT_RE: OnceLock<Regex> = OnceLock::new();
343    let regex =
344        IDENT_RE.get_or_init(|| Regex::new(r"[A-Za-z_][A-Za-z0-9_:<>]*").expect("valid regex"));
345    regex
346        .find_iter(source)
347        .map(|m| m.as_str())
348        .filter(|token| {
349            token
350                .chars()
351                .next()
352                .is_some_and(|ch| ch.is_ascii_uppercase())
353        })
354        .map(|token| token.trim_matches(':').to_string())
355        .collect()
356}
357
358/// Whether the structural receiver queries apply to `file`.
359///
360/// `Language::Cpp` also covers plain `.c`, which has no member-call receivers
361/// for those queries to resolve, so the route is gated on the extension.
362pub fn receiver_query_supported(file: &ProjectFile) -> bool {
363    file.rel_path()
364        .extension()
365        .and_then(|extension| extension.to_str())
366        != Some("c")
367}
368
369fn lexical_project_relative_include_path(
370    project_root: &Path,
371    include_path: &Path,
372) -> Option<PathBuf> {
373    let root = slash_path(project_root);
374    let include = slash_path(include_path);
375    strip_slash_prefix(&include, &root).map(PathBuf::from)
376}
377
378fn slash_path(path: &Path) -> String {
379    let raw = path.to_string_lossy();
380    let raw = raw.strip_prefix(r"\\?\").unwrap_or(&raw);
381    raw.replace('\\', "/").trim_end_matches('/').to_string()
382}
383
384#[cfg(windows)]
385fn strip_slash_prefix<'a>(path: &'a str, root: &str) -> Option<&'a str> {
386    if path.eq_ignore_ascii_case(root) {
387        return Some("");
388    }
389    if path.len() > root.len()
390        && path.as_bytes().get(root.len()) == Some(&b'/')
391        && path[..root.len()].eq_ignore_ascii_case(root)
392    {
393        return Some(&path[root.len() + 1..]);
394    }
395    None
396}
397
398#[cfg(not(windows))]
399fn strip_slash_prefix<'a>(path: &'a str, root: &str) -> Option<&'a str> {
400    if path == root {
401        return Some("");
402    }
403    path.strip_prefix(root)
404        .and_then(|rest| rest.strip_prefix('/'))
405}
406
407#[cfg(test)]
408mod tests {
409    use super::*;
410    use std::fs;
411    use tempfile::TempDir;
412
413    fn write_file(root: &Path, rel: &str) -> ProjectFile {
414        let path = root.join(rel);
415        fs::create_dir_all(path.parent().expect("test file has parent")).unwrap();
416        fs::write(&path, "").unwrap();
417        ProjectFile::new(root.to_path_buf(), rel)
418    }
419
420    #[test]
421    fn indexed_include_resolution_uses_unique_suffix_fallback() {
422        let temp = TempDir::new().unwrap();
423        let root = temp.path().canonicalize().unwrap();
424        let source = write_file(&root, "src/lib.c");
425        let target = write_file(&root, "include/git2/sys/credential.h");
426        let duplicate = write_file(&root, "vendor/credential.h");
427        let index = IncludeTargetIndex::build([&source, &target, &duplicate]);
428
429        let resolved = resolve_include_targets_with_index(&source, "git2/sys/credential.h", &index);
430        assert_eq!(resolved, vec![target]);
431
432        let ambiguous = resolve_include_targets_with_index(&source, "credential.h", &index);
433        assert!(ambiguous.is_empty());
434    }
435
436    #[test]
437    fn indexed_include_resolution_prefers_unique_source_reachable_root() {
438        let temp = TempDir::new().unwrap();
439        let root = temp.path().canonicalize().unwrap();
440        let source = write_file(&root, "src/config/parse.c");
441        let target = write_file(&root, "src/config/parse.h");
442        let nested_decoy = write_file(&root, "src/build/config/parse.h");
443        let unrelated_source = write_file(&root, "app/main.c");
444        let index = IncludeTargetIndex::build([&source, &target, &nested_decoy, &unrelated_source]);
445
446        let resolved = resolve_include_targets_with_index(&source, "config/parse.h", &index);
447        assert_eq!(resolved, vec![target.clone()]);
448
449        let unrelated =
450            resolve_include_targets_with_index(&unrelated_source, "config/parse.h", &index);
451        assert!(unrelated.is_empty());
452
453        let ambiguous_source = write_file(&root, "src/config/deeper/main.c");
454        let second_reachable = write_file(&root, "src/config/config/parse.h");
455        let ambiguous_index = IncludeTargetIndex::build([
456            &ambiguous_source,
457            &target,
458            &nested_decoy,
459            &second_reachable,
460        ]);
461        let ambiguous = resolve_include_targets_with_index(
462            &ambiguous_source,
463            "config/parse.h",
464            &ambiguous_index,
465        );
466        assert!(ambiguous.is_empty());
467    }
468
469    #[test]
470    fn unresolved_h_include_falls_back_to_hin_template() {
471        let temp = TempDir::new().unwrap();
472        let root = temp.path().canonicalize().unwrap();
473        let stub = write_file(&root, "src/include/krb5.h");
474        let template = write_file(&root, "src/include/krb5/krb5.hin");
475        let index = IncludeTargetIndex::build([&stub, &template]);
476
477        let resolved = resolve_include_targets_with_index(&stub, "krb5/krb5.h", &index);
478        assert_eq!(resolved, vec![template]);
479    }
480
481    #[test]
482    fn real_header_wins_over_hin_template() {
483        let temp = TempDir::new().unwrap();
484        let root = temp.path().canonicalize().unwrap();
485        let stub = write_file(&root, "src/include/krb5.h");
486        let generated = write_file(&root, "src/include/krb5/krb5.h");
487        let template = write_file(&root, "src/include/krb5/krb5.hin");
488        let index = IncludeTargetIndex::build([&stub, &generated, &template]);
489
490        let resolved = resolve_include_targets_with_index(&stub, "krb5/krb5.h", &index);
491        assert_eq!(resolved, vec![generated]);
492    }
493}
brokk_bifrost_cpp/imports.rs

brokk_bifrost_cpp/
imports.rs
