Skip to main content

reflex/
dependency.rs

1//! Dependency tracking and graph analysis
2//!
3//! This module provides functionality for tracking file dependencies (imports/includes)
4//! and analyzing the dependency graph of a codebase.
5//!
6//! # Architecture
7//!
8//! The system uses a "depth-1 storage" approach:
9//! - Only direct dependencies are stored in the database
10//! - Deeper relationships are computed on-demand via graph traversal
11//! - This provides O(n) storage while enabling any-depth queries
12//!
13//! # Example
14//!
15//! ```no_run
16//! use reflex::dependency::DependencyIndex;
17//! use reflex::cache::CacheManager;
18//!
19//! let cache = CacheManager::new(".");
20//! let deps = DependencyIndex::new(cache);
21//!
22//! // Get direct dependencies of a file
23//! let file_deps = deps.get_dependencies(42)?;
24//!
25//! // Get files that import this file (reverse lookup)
26//! let dependents = deps.get_dependents(42)?;
27//!
28//! // Traverse dependency graph to depth 3
29//! let transitive = deps.get_transitive_deps(42, 3)?;
30//! # Ok::<(), anyhow::Error>(())
31//! ```
32
33use anyhow::{Context, Result};
34use rusqlite::Connection;
35use std::collections::{HashMap, HashSet, VecDeque};
36use std::path::PathBuf;
37
38use crate::cache::CacheManager;
39use crate::models::{Dependency, DependencyInfo, ImportType};
40
41/// In-memory `path → file_id` lookup for the indexer's dependency phase.
42///
43/// Built once from the `files` table after the files transaction commits, then
44/// answers the same question as [`DependencyIndex::get_file_id_by_path`] without
45/// a SQLite connection per call: exact match first, then a unique suffix match.
46/// Before 2.0.0 every miss ran `SELECT … WHERE path LIKE '%' || ?`, a full scan
47/// of the `files` table, and a Kubernetes-sized tree spent ~500 s of a ~530 s
48/// index in that loop.
49///
50/// The suffix match is ASCII-case-insensitive, like SQLite `LIKE`, but `_` and
51/// `%` in the probe are literal. `LIKE` treated them as wildcards, so a probe of
52/// `foo_bar.h` also matched `fooXbar.h` and reported a false ambiguity; a
53/// filename's underscore is a character, not a pattern.
54pub struct PathResolver {
55    /// `path → id`, case-sensitive, the `path = ?` fast path.
56    exact: HashMap<String, i64>,
57    /// `(ASCII-lowercased, byte-reversed path, id)`, sorted by key, so every path
58    /// ending in a probe is a contiguous run found by binary search.
59    suffix: Vec<(Vec<u8>, i64)>,
60}
61
62impl PathResolver {
63    /// Load every `(id, path)` row from `files`.
64    pub fn from_conn(conn: &Connection) -> Result<Self> {
65        let mut stmt = conn
66            .prepare("SELECT id, path FROM files")
67            .context("Failed to prepare files query")?;
68        let rows = stmt
69            .query_map([], |row| {
70                Ok((row.get::<_, i64>(0)?, row.get::<_, String>(1)?))
71            })
72            .context("Failed to read files table")?
73            .collect::<std::result::Result<Vec<_>, _>>()
74            .context("Failed to read files rows")?;
75        Ok(Self::from_rows(rows))
76    }
77
78    /// Build from `(id, path)` pairs.
79    pub fn from_rows(rows: impl IntoIterator<Item = (i64, String)>) -> Self {
80        let rows = rows.into_iter();
81        let (lower, _) = rows.size_hint();
82        let mut exact = HashMap::with_capacity(lower);
83        let mut suffix = Vec::with_capacity(lower);
84        for (id, path) in rows {
85            suffix.push((Self::suffix_key(&path), id));
86            exact.insert(path, id);
87        }
88        suffix.sort_unstable();
89        Self { exact, suffix }
90    }
91
92    /// Number of paths known to the resolver.
93    pub fn len(&self) -> usize {
94        self.exact.len()
95    }
96
97    /// Whether the resolver knows no paths.
98    pub fn is_empty(&self) -> bool {
99        self.exact.is_empty()
100    }
101
102    fn suffix_key(path: &str) -> Vec<u8> {
103        path.bytes().rev().map(|b| b.to_ascii_lowercase()).collect()
104    }
105
106    /// Add `path` with `id` (replacing the id a known path had).
107    pub fn insert(&mut self, id: i64, path: &str) {
108        if let Some(old) = self.exact.insert(path.to_string(), id) {
109            self.remove_suffix(path, old);
110        }
111        let entry = (Self::suffix_key(path), id);
112        let at = self.suffix.partition_point(|e| *e < entry);
113        self.suffix.insert(at, entry);
114    }
115
116    /// Forget `path`.
117    pub fn remove(&mut self, path: &str) {
118        if let Some(id) = self.exact.remove(path) {
119            self.remove_suffix(path, id);
120        }
121    }
122
123    fn remove_suffix(&mut self, path: &str, id: i64) {
124        let entry = (Self::suffix_key(path), id);
125        if let Ok(at) = self.suffix.binary_search(&entry) {
126            self.suffix.remove(at);
127        }
128    }
129
130    /// The id of exactly `path` (after `normalize_path_for_lookup`), no suffix match.
131    pub fn get_exact(&self, path: &str) -> Option<i64> {
132        self.exact.get(&normalize_path_for_lookup(path)).copied()
133    }
134
135    /// Same contract as [`DependencyIndex::get_file_id_by_path`]: `Ok(Some)` on an
136    /// exact or unique-suffix match, `Ok(None)` on no match, `Err` when the suffix
137    /// is ambiguous.
138    pub fn get_file_id_by_path(&self, path: &str) -> Result<Option<i64>> {
139        let normalized = normalize_path_for_lookup(path);
140        if let Some(&id) = self.exact.get(&normalized) {
141            return Ok(Some(id));
142        }
143
144        // The whole path or a suffix of whole segments, ASCII case-insensitive:
145        // `a.h` matches `include/a.h`, not `lib/xa.h`
146        let probe = Self::suffix_key(&normalized);
147        let start = self
148            .suffix
149            .partition_point(|(key, _)| key.as_slice() < probe.as_slice());
150        let mut matches = self.suffix[start..]
151            .iter()
152            .take_while(|(key, _)| key.starts_with(&probe))
153            .filter(|(key, _)| key.len() == probe.len() || key[probe.len()] == b'/');
154        match (matches.next(), matches.next()) {
155            (None, _) => Ok(None),
156            (Some((_, id)), None) => Ok(Some(*id)),
157            (Some(_), Some(_)) => anyhow::bail!(
158                "Ambiguous path '{}' matches multiple files\n\nPlease be more specific.",
159                path
160            ),
161        }
162    }
163}
164
165/// Writes dependency and export rows on a connection inside a transaction the
166/// caller holds (the index run commits `files`, dependency and export rows once).
167///
168/// Statements are prepared once and reused. Until 2.0.0 the indexer opened a
169/// fresh connection for each lookup, each per-file `DELETE` and each per-file
170/// insert batch, committing (and fsyncing) twice per file and once per export row.
171pub struct DependencyWriter<'c> {
172    tx: &'c Connection,
173    deps: usize,
174    exports: usize,
175}
176
177impl<'c> DependencyWriter<'c> {
178    const INSERT_DEPENDENCY: &'static str = "INSERT INTO file_dependencies \
179         (file_id, imported_path, resolved_file_id, import_type, line_number, imported_symbols, \
180          resolved_package, resolved_member) \
181         VALUES (?, ?, ?, ?, ?, ?, ?, ?)";
182    const INSERT_EXPORT: &'static str = "INSERT INTO file_exports \
183         (file_id, exported_symbol, source_path, resolved_source_id, line_number) \
184         VALUES (?, ?, ?, ?, ?)";
185
186    /// Write on `conn`, inside a transaction the caller holds.
187    pub fn new(conn: &'c Connection) -> Self {
188        Self {
189            tx: conn,
190            deps: 0,
191            exports: 0,
192        }
193    }
194
195    /// Drop every dependency row of `file_id`, then insert `deps`.
196    ///
197    /// Equivalent to `clear_dependencies` followed by `batch_insert_dependencies`.
198    pub fn replace_dependencies(&mut self, file_id: i64, deps: &[Dependency]) -> Result<()> {
199        self.tx
200            .prepare_cached("DELETE FROM file_dependencies WHERE file_id = ?")?
201            .execute([file_id])?;
202        if deps.is_empty() {
203            return Ok(());
204        }
205        let mut stmt = self.tx.prepare_cached(Self::INSERT_DEPENDENCY)?;
206        for dep in deps {
207            let symbols_json = dep
208                .imported_symbols
209                .as_ref()
210                .map(|syms| serde_json::to_string(syms).unwrap_or_else(|_| "[]".to_string()));
211            stmt.execute(rusqlite::params![
212                dep.file_id,
213                dep.imported_path,
214                dep.resolved_file_id,
215                import_type_str(&dep.import_type),
216                dep.line_number as i64,
217                symbols_json,
218                dep.resolved_package,
219                dep.resolved_member,
220            ])?;
221        }
222        self.deps += deps.len();
223        Ok(())
224    }
225
226    /// Drop every package membership of `file_id`, then record `members`
227    /// (`(package key, member)`; member `""` for a whole-directory package).
228    pub fn replace_members(&mut self, file_id: i64, members: &[(String, String)]) -> Result<()> {
229        self.tx
230            .prepare_cached("DELETE FROM package_members WHERE file_id = ?")?
231            .execute([file_id])?;
232        let mut stmt = self.tx.prepare_cached(
233            "INSERT OR IGNORE INTO package_members (package, member, file_id) VALUES (?, ?, ?)",
234        )?;
235        for (package, member) in members {
236            stmt.execute(rusqlite::params![package, member, file_id])?;
237        }
238        Ok(())
239    }
240
241    /// Drop every dependency, export and package-membership row (a full build
242    /// writes them all again).
243    pub fn clear_all(&mut self) -> Result<()> {
244        self.tx.execute_batch(
245            "DELETE FROM file_dependencies;
246             DELETE FROM file_exports;
247             DELETE FROM package_members;",
248        )?;
249        Ok(())
250    }
251
252    /// Drop every export row of `file_id` (exports have no key to replace them by).
253    pub fn clear_exports(&mut self, file_id: i64) -> Result<()> {
254        self.tx
255            .prepare_cached("DELETE FROM file_exports WHERE file_id = ?")?
256            .execute([file_id])?;
257        Ok(())
258    }
259
260    /// Insert one export row (same columns as [`DependencyIndex::insert_export`]).
261    pub fn insert_export(
262        &mut self,
263        file_id: i64,
264        exported_symbol: Option<&str>,
265        source_path: &str,
266        resolved_source_id: Option<i64>,
267        line_number: usize,
268    ) -> Result<()> {
269        self.tx
270            .prepare_cached(Self::INSERT_EXPORT)?
271            .execute(rusqlite::params![
272                file_id,
273                exported_symbol,
274                source_path,
275                resolved_source_id,
276                line_number as i64,
277            ])?;
278        self.exports += 1;
279        Ok(())
280    }
281
282    /// `(dependencies, exports)` written so far.
283    pub fn counts(&self) -> (usize, usize) {
284        (self.deps, self.exports)
285    }
286}
287
288fn import_type_str(import_type: &ImportType) -> &'static str {
289    match import_type {
290        ImportType::Internal => "internal",
291        ImportType::External => "external",
292        ImportType::Stdlib => "stdlib",
293        ImportType::ModDecl => "mod_decl",
294    }
295}
296
297/// Below this many internal imports a language's resolution rate is not reported.
298pub const LOW_RESOLUTION_MIN_IMPORTS: usize = 100;
299
300/// A language whose resolved share of internal imports is below this gets a warning.
301pub const LOW_RESOLUTION_RATE: f64 = 0.5;
302
303/// Internal imports of one language and how many resolve to an indexed file.
304#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize)]
305pub struct LanguageResolution {
306    /// The `files.language` name (`Go`, `CSharp`, …).
307    pub language: String,
308    pub internal: usize,
309    pub resolved: usize,
310}
311
312impl LanguageResolution {
313    pub fn rate(&self) -> f64 {
314        if self.internal == 0 {
315            1.0
316        } else {
317            self.resolved as f64 / self.internal as f64
318        }
319    }
320
321    pub fn is_low(&self) -> bool {
322        self.internal >= LOW_RESOLUTION_MIN_IMPORTS && self.rate() < LOW_RESOLUTION_RATE
323    }
324
325    pub fn warning(&self) -> String {
326        let name = match self.language.as_str() {
327            "CSharp" => "C#",
328            "Cpp" => "C++",
329            other => other,
330        };
331        format!(
332            "{name}: {} of {} internal imports ({:.1}%) resolve to indexed files; \
333             islands, unused files, hotspots, cycles and dependents for {name} files are incomplete",
334            self.resolved,
335            self.internal,
336            self.rate() * 100.0
337        )
338    }
339}
340
341/// Manages dependency storage and graph operations
342pub struct DependencyIndex {
343    cache: Option<CacheManager>,
344    db_path: PathBuf,
345}
346
347impl DependencyIndex {
348    /// Create a new dependency index for the given cache
349    pub fn new(cache: CacheManager) -> Self {
350        let db_path = cache.path().join("meta.db");
351        Self {
352            cache: Some(cache),
353            db_path,
354        }
355    }
356
357    /// Create a dependency index pointing directly at a database file.
358    ///
359    /// Used by Pulse to run analysis against snapshot databases.
360    pub fn from_db_path(db_path: impl Into<PathBuf>) -> Self {
361        Self {
362            cache: None,
363            db_path: db_path.into(),
364        }
365    }
366
367    /// Get a reference to the cache manager.
368    ///
369    /// Panics if this index was created via `from_db_path()`.
370    pub fn get_cache(&self) -> &CacheManager {
371        self.cache
372            .as_ref()
373            .expect("DependencyIndex created with from_db_path has no CacheManager")
374    }
375
376    /// Open a database connection to the backing store.
377    fn open_conn(&self) -> Result<Connection> {
378        crate::cache::open_meta_db(&self.db_path).context("Failed to open database")
379    }
380
381    /// Insert a dependency into the database
382    ///
383    /// # Arguments
384    ///
385    /// * `file_id` - Source file ID
386    /// * `imported_path` - Import path as written in source
387    /// * `resolved_file_id` - Resolved target file ID (None if external/stdlib)
388    /// * `import_type` - Type of import (internal/external/stdlib)
389    /// * `line_number` - Line where import appears
390    /// * `imported_symbols` - Optional list of imported symbols
391    pub fn insert_dependency(
392        &self,
393        file_id: i64,
394        imported_path: String,
395        resolved_file_id: Option<i64>,
396        import_type: ImportType,
397        line_number: usize,
398        imported_symbols: Option<Vec<String>>,
399    ) -> Result<()> {
400        let conn = self.open_conn()?;
401
402        let import_type_str = match import_type {
403            ImportType::Internal => "internal",
404            ImportType::External => "external",
405            ImportType::Stdlib => "stdlib",
406            ImportType::ModDecl => "mod_decl",
407        };
408
409        let symbols_json = imported_symbols
410            .as_ref()
411            .map(|syms| serde_json::to_string(syms).unwrap_or_else(|_| "[]".to_string()));
412
413        conn.execute(
414            "INSERT INTO file_dependencies (file_id, imported_path, resolved_file_id, import_type, line_number, imported_symbols)
415             VALUES (?, ?, ?, ?, ?, ?)",
416            rusqlite::params![
417                file_id,
418                imported_path,
419                resolved_file_id,
420                import_type_str,
421                line_number as i64,
422                symbols_json,
423            ],
424        )?;
425
426        Ok(())
427    }
428
429    /// Insert an export into the database
430    ///
431    /// # Arguments
432    ///
433    /// * `file_id` - Source file ID containing the export statement
434    /// * `exported_symbol` - Symbol name being exported (None for wildcard exports)
435    /// * `source_path` - Path where the symbol is re-exported from
436    /// * `resolved_source_id` - Resolved target file ID (None if unresolved)
437    /// * `line_number` - Line where export appears
438    pub fn insert_export(
439        &self,
440        file_id: i64,
441        exported_symbol: Option<String>,
442        source_path: String,
443        resolved_source_id: Option<i64>,
444        line_number: usize,
445    ) -> Result<()> {
446        let conn = self.open_conn()?;
447
448        conn.execute(
449            "INSERT INTO file_exports (file_id, exported_symbol, source_path, resolved_source_id, line_number)
450             VALUES (?, ?, ?, ?, ?)",
451            rusqlite::params![
452                file_id,
453                exported_symbol,
454                source_path,
455                resolved_source_id,
456                line_number as i64,
457            ],
458        )?;
459
460        Ok(())
461    }
462
463    /// Batch insert multiple dependencies in a single transaction
464    ///
465    /// More efficient than individual inserts for bulk operations.
466    pub fn batch_insert_dependencies(&self, dependencies: &[Dependency]) -> Result<()> {
467        if dependencies.is_empty() {
468            return Ok(());
469        }
470
471        let mut conn = self.open_conn()?;
472
473        let tx = conn.transaction()?;
474
475        for dep in dependencies {
476            let import_type_str = match dep.import_type {
477                ImportType::Internal => "internal",
478                ImportType::External => "external",
479                ImportType::Stdlib => "stdlib",
480                ImportType::ModDecl => "mod_decl",
481            };
482
483            let symbols_json = dep
484                .imported_symbols
485                .as_ref()
486                .map(|syms| serde_json::to_string(syms).unwrap_or_else(|_| "[]".to_string()));
487
488            tx.execute(
489                DependencyWriter::INSERT_DEPENDENCY,
490                rusqlite::params![
491                    dep.file_id,
492                    dep.imported_path,
493                    dep.resolved_file_id,
494                    import_type_str,
495                    dep.line_number as i64,
496                    symbols_json,
497                    dep.resolved_package,
498                    dep.resolved_member,
499                ],
500            )?;
501        }
502
503        tx.commit()?;
504        log::debug!("Batch inserted {} dependencies", dependencies.len());
505        Ok(())
506    }
507
508    /// Get all direct dependencies for a file
509    ///
510    /// Returns a list of files/modules that this file imports.
511    pub fn get_dependencies(&self, file_id: i64) -> Result<Vec<Dependency>> {
512        let conn = self.open_conn()?;
513
514        let mut stmt = conn.prepare(
515            "SELECT file_id, imported_path, resolved_file_id, import_type, line_number, imported_symbols,
516                    resolved_package, resolved_member
517             FROM file_dependencies
518             WHERE file_id = ?
519             ORDER BY line_number",
520        )?;
521
522        let deps = stmt
523            .query_map([file_id], |row| {
524                let import_type_str: String = row.get(3)?;
525                let import_type = match import_type_str.as_str() {
526                    "internal" => ImportType::Internal,
527                    "external" => ImportType::External,
528                    "stdlib" => ImportType::Stdlib,
529                    "mod_decl" => ImportType::ModDecl,
530                    _ => ImportType::External,
531                };
532
533                let symbols_json: Option<String> = row.get(5)?;
534                let imported_symbols =
535                    symbols_json.and_then(|json| serde_json::from_str(&json).ok());
536
537                Ok(Dependency {
538                    file_id: row.get(0)?,
539                    imported_path: row.get(1)?,
540                    resolved_file_id: row.get(2)?,
541                    resolved_package: row.get(6)?,
542                    resolved_member: row.get(7)?,
543                    import_type,
544                    line_number: row.get::<_, i64>(4)? as usize,
545                    imported_symbols,
546                })
547            })?
548            .collect::<Result<Vec<_>, _>>()?;
549
550        Ok(deps)
551    }
552
553    /// Get all files that depend on this file (reverse lookup)
554    ///
555    /// Returns a list of file IDs that import this file.
556    /// Uses `resolved_file_id` column for instant SQL lookup (sub-10ms).
557    pub fn get_dependents(&self, file_id: i64) -> Result<Vec<i64>> {
558        let conn = self.open_conn()?;
559
560        // Pure SQL query on resolved_file_id (instant). Walk order: a full build
561        // numbers files in walk order, and ids are stable across updates.
562        let mut stmt = conn.prepare(
563            "SELECT f.id
564             FROM files f
565             WHERE f.id IN (SELECT src FROM import_edges WHERE dst = ?)
566             ORDER BY f.walk_seq",
567        )?;
568
569        let dependents: Vec<i64> = stmt
570            .query_map([file_id], |row| row.get(0))?
571            .collect::<Result<Vec<_>, _>>()?;
572
573        Ok(dependents)
574    }
575
576    /// The files `file_id` imports, each once, in (import row, target walk) order.
577    fn direct_targets(&self, file_id: i64) -> Result<Vec<i64>> {
578        let conn = self.open_conn()?;
579        let mut stmt = conn.prepare_cached(
580            "SELECT e.dst FROM import_edges e JOIN files t ON t.id = e.dst
581             WHERE e.src = ? ORDER BY e.dep_id, t.walk_seq",
582        )?;
583        let mut seen = HashSet::new();
584        let targets = stmt
585            .query_map([file_id], |row| row.get::<_, i64>(0))?
586            .collect::<Result<Vec<_>, _>>()?;
587        Ok(targets.into_iter().filter(|id| seen.insert(*id)).collect())
588    }
589
590    /// For each import of `file_id`, keyed by `(line, imported path)`, the paths of
591    /// the files it reaches: the import's own target first, then in walk order.
592    fn package_targets(&self, file_id: i64) -> Result<HashMap<(usize, String), Vec<String>>> {
593        let conn = self.open_conn()?;
594        let mut stmt = conn.prepare(
595            "SELECT d.line_number, d.imported_path, t.path
596             FROM import_edges e
597             JOIN file_dependencies d ON d.id = e.dep_id
598             JOIN files t ON t.id = e.dst
599             WHERE e.src = ?
600             ORDER BY d.id, t.id != COALESCE(d.resolved_file_id, -1), t.path",
601        )?;
602        let mut out: HashMap<(usize, String), Vec<String>> = HashMap::new();
603        let rows = stmt.query_map([file_id], |row| {
604            Ok((
605                row.get::<_, i64>(0)? as usize,
606                row.get::<_, String>(1)?,
607                row.get::<_, String>(2)?,
608            ))
609        })?;
610        for row in rows {
611            let (line, imported, path) = row?;
612            out.entry((line, imported)).or_default().push(path);
613        }
614        Ok(out)
615    }
616
617    /// Get dependencies as DependencyInfo (for API output)
618    ///
619    /// Converts internal Dependency records to simplified DependencyInfo
620    /// suitable for JSON output.
621    pub fn get_dependencies_info(&self, file_id: i64) -> Result<Vec<DependencyInfo>> {
622        let deps = self.get_dependencies(file_id)?;
623
624        let mut packages = self.package_targets(file_id)?;
625        let dep_infos = deps
626            .into_iter()
627            .map(|dep| {
628                // A package import, or one that reaches several files (a Python
629                // package and its submodules), lists the files it reaches
630                let reached = packages.remove(&(dep.line_number, dep.imported_path.clone()));
631                let resolved_paths = if dep.resolved_package.is_some() {
632                    Some(reached.unwrap_or_default())
633                } else {
634                    reached.filter(|paths| paths.len() > 1)
635                };
636                // Try to get the resolved path (all deps are internal now)
637                let path = if let Some(resolved_id) = dep.resolved_file_id {
638                    // Try to get the actual file path
639                    self.get_file_path(resolved_id).unwrap_or(dep.imported_path)
640                } else {
641                    dep.imported_path
642                };
643
644                DependencyInfo {
645                    path,
646                    line: Some(dep.line_number),
647                    symbols: dep.imported_symbols,
648                    resolved_paths,
649                }
650            })
651            .collect();
652
653        Ok(dep_infos)
654    }
655
656    /// Get transitive dependencies up to a given depth
657    ///
658    /// Traverses the dependency graph using BFS to find all dependencies
659    /// reachable within the specified depth.
660    /// Uses `resolved_file_id` column for instant SQL lookup (sub-100ms).
661    ///
662    /// # Arguments
663    ///
664    /// * `file_id` - Starting file ID
665    /// * `max_depth` - Maximum traversal depth (0 = only direct deps)
666    ///
667    /// # Returns
668    ///
669    /// HashMap mapping file_id to depth (distance from start file)
670    pub fn get_transitive_deps(
671        &self,
672        file_id: i64,
673        max_depth: usize,
674    ) -> Result<HashMap<i64, usize>> {
675        let mut visited = HashMap::new();
676        let mut queue = VecDeque::new();
677
678        // Start with the initial file at depth 0
679        queue.push_back((file_id, 0));
680        visited.insert(file_id, 0);
681
682        while let Some((current_id, depth)) = queue.pop_front() {
683            if depth >= max_depth {
684                continue;
685            }
686
687            for resolved_id in self.direct_targets(current_id)? {
688                // Only visit if we haven't seen it or found a shorter path
689                if let std::collections::hash_map::Entry::Vacant(e) = visited.entry(resolved_id) {
690                    e.insert(depth + 1);
691                    queue.push_back((resolved_id, depth + 1));
692                }
693            }
694        }
695
696        Ok(visited)
697    }
698
699    /// [`get_transitive_deps`](Self::get_transitive_deps) as a list ordered by depth,
700    /// then walk order (the id order of a full build), so the same index always
701    /// prints the same list. The start file is the first entry, at depth 0.
702    pub fn get_transitive_deps_ordered(
703        &self,
704        file_id: i64,
705        max_depth: usize,
706    ) -> Result<Vec<(i64, usize)>> {
707        let transitive = self.get_transitive_deps(file_id, max_depth)?;
708        let ids: Vec<i64> = transitive.keys().copied().collect();
709        let ranks = self.walk_ranks(&ids)?;
710        let mut ordered: Vec<(i64, usize)> = transitive.into_iter().collect();
711        ordered.sort_unstable_by_key(|&(id, depth)| {
712            (depth, ranks.get(&id).copied().unwrap_or(i64::MAX), id)
713        });
714        Ok(ordered)
715    }
716
717    /// Detect circular dependencies in the entire codebase
718    ///
719    /// Uses depth-first search to find cycles in the dependency graph.
720    /// Uses `resolved_file_id` column for instant SQL lookup (sub-100ms).
721    ///
722    /// Returns a list of cycle paths, where each cycle is represented as
723    /// a vector of file IDs forming the cycle.
724    pub fn detect_circular_dependencies(&self) -> Result<Vec<Vec<i64>>> {
725        let conn = self.open_conn()?;
726
727        // Build in-memory dependency graph using resolved_file_id (instant)
728        let mut graph: HashMap<i64, Vec<i64>> = HashMap::new();
729
730        // Exclude mod_decl edges: `mod foo;` is parent→child ownership, not a usage dependency.
731        // Including them creates false positives when a child module uses `use crate::` (REF-88).
732        // Each file's edges in row order (= extraction order).
733        for (file_id, target_id) in load_edges(&conn, EdgeOrder::ImporterId, false)? {
734            graph.entry(file_id).or_default().push(target_id);
735        }
736
737        // Get all file IDs for traversal
738        let all_files = self.get_all_file_ids()?;
739
740        let mut visited = HashSet::new();
741        let mut rec_stack = HashSet::new();
742        let mut path = Vec::new();
743        let mut cycles = Vec::new();
744
745        for file_id in all_files {
746            if !visited.contains(&file_id) {
747                self.dfs_cycle_detect(
748                    file_id,
749                    &graph,
750                    &mut visited,
751                    &mut rec_stack,
752                    &mut path,
753                    &mut cycles,
754                )?;
755            }
756        }
757
758        Ok(cycles)
759    }
760
761    /// DFS for cycle detection over the pre-built graph. Iterative (a real Go or
762    /// Java graph is thousands of files deep), visiting in the order the recursive
763    /// version did, so the cycles come out the same.
764    fn dfs_cycle_detect(
765        &self,
766        start: i64,
767        graph: &HashMap<i64, Vec<i64>>,
768        visited: &mut HashSet<i64>,
769        rec_stack: &mut HashSet<i64>,
770        path: &mut Vec<i64>,
771        cycles: &mut Vec<Vec<i64>>,
772    ) -> Result<()> {
773        const NONE: &[i64] = &[];
774        // (node, index of its next neighbour)
775        let mut stack: Vec<(i64, usize)> = vec![(start, 0)];
776        visited.insert(start);
777        rec_stack.insert(start);
778        path.push(start);
779
780        while let Some((node, next)) = stack.last_mut() {
781            let neighbors = graph.get(node).map_or(NONE, Vec::as_slice);
782            if let Some(&target_id) = neighbors.get(*next) {
783                *next += 1;
784                if !visited.contains(&target_id) {
785                    visited.insert(target_id);
786                    rec_stack.insert(target_id);
787                    path.push(target_id);
788                    stack.push((target_id, 0));
789                } else if rec_stack.contains(&target_id) {
790                    // Found a cycle! Extract it from path
791                    if let Some(cycle_start) = path.iter().position(|&id| id == target_id) {
792                        cycles.push(path[cycle_start..].to_vec());
793                    }
794                }
795            } else {
796                let node = *node;
797                stack.pop();
798                path.pop();
799                rec_stack.remove(&node);
800            }
801        }
802
803        Ok(())
804    }
805
806    /// Get file paths for a list of file IDs
807    ///
808    /// Useful for converting file ID results to human-readable paths.
809    pub fn get_file_paths(&self, file_ids: &[i64]) -> Result<HashMap<i64, String>> {
810        let conn = self.open_conn()?;
811
812        let mut paths = HashMap::new();
813
814        for &file_id in file_ids {
815            if let Ok(path) =
816                conn.query_row("SELECT path FROM files WHERE id = ?", [file_id], |row| {
817                    row.get::<_, String>(0)
818                })
819            {
820                paths.insert(file_id, path);
821            }
822        }
823
824        Ok(paths)
825    }
826
827    /// `id → 1-based position in walk order` for the given ids: the id a full
828    /// build gives each file (it numbers files 1..N in walk order). Outputs that
829    /// sort or print ids use this, so they do not depend on update history.
830    pub fn walk_ranks(&self, file_ids: &[i64]) -> Result<HashMap<i64, i64>> {
831        let conn = self.open_conn()?;
832        let wanted: HashSet<i64> = file_ids.iter().copied().collect();
833        let mut stmt = conn.prepare("SELECT id FROM files ORDER BY walk_seq")?;
834        let mut ranks = HashMap::with_capacity(wanted.len());
835        let ids = stmt.query_map([], |row| row.get::<_, i64>(0))?;
836        for (i, id) in ids.enumerate() {
837            let id = id?;
838            if wanted.contains(&id) {
839                ranks.insert(id, i as i64 + 1);
840            }
841        }
842        Ok(ranks)
843    }
844
845    /// Get file path for a single file ID
846    fn get_file_path(&self, file_id: i64) -> Result<String> {
847        let conn = self.open_conn()?;
848
849        let path = conn.query_row("SELECT path FROM files WHERE id = ?", [file_id], |row| {
850            row.get::<_, String>(0)
851        })?;
852
853        Ok(path)
854    }
855
856    /// Get all file IDs in the database, in path order (the order the path index
857    /// has always returned them in; graph traversals start from them in this order)
858    fn get_all_file_ids(&self) -> Result<Vec<i64>> {
859        let conn = self.open_conn()?;
860
861        let mut stmt = conn.prepare(&format!(
862            "SELECT id FROM files WHERE {CODE_FILES} ORDER BY path"
863        ))?;
864        let file_ids = stmt
865            .query_map([], |row| row.get(0))?
866            .collect::<Result<Vec<_>, _>>()?;
867
868        Ok(file_ids)
869    }
870
871    /// Find hotspots (most imported files)
872    ///
873    /// Returns a list of (file_id, count) tuples sorted by import count descending.
874    ///
875    /// Uses `resolved_file_id` column for instant SQL aggregation (sub-100ms).
876    ///
877    /// # Arguments
878    ///
879    /// * `limit` - Maximum number of hotspots to return (None = all)
880    /// * `min_dependents` - Minimum number of imports required to be a hotspot (default: 2)
881    pub fn find_hotspots(
882        &self,
883        limit: Option<usize>,
884        min_dependents: usize,
885    ) -> Result<Vec<(i64, usize)>> {
886        let conn = self.open_conn()?;
887
888        // Distinct importers per file (a file importing a target twice counts once).
889        // Ties in walk order, which is the id order a full build produces.
890        let mut stmt = conn.prepare(
891            "SELECT e.dst, COUNT(DISTINCT e.src) as count, MIN(f.walk_seq) AS ws
892             FROM import_edges e
893             JOIN files f ON f.id = e.dst
894             GROUP BY e.dst
895             ORDER BY count DESC, ws",
896        )?;
897
898        // Get all hotspots and filter by minimum dependent count
899        let mut hotspots: Vec<(i64, usize)> = stmt
900            .query_map([], |row| {
901                Ok((row.get::<_, i64>(0)?, row.get::<_, i64>(1)? as usize))
902            })?
903            .collect::<Result<Vec<_>, _>>()?
904            .into_iter()
905            .filter(|(_, count)| *count >= min_dependents)
906            .collect();
907
908        // Apply limit if specified
909        if let Some(lim) = limit {
910            hotspots.truncate(lim);
911        }
912
913        Ok(hotspots)
914    }
915
916    /// Find unused files (files with no incoming dependencies)
917    ///
918    /// Files that are never imported are potential candidates for deletion.
919    /// Uses `resolved_file_id` column for instant SQL lookup (sub-10ms).
920    ///
921    /// **Barrel Export Resolution**: This function now follows barrel export chains
922    /// to detect files that are indirectly imported via re-exports. For example:
923    /// - `WithLabel.vue` exported by `packages/ui/components/index.ts`
924    /// - App imports `@packages/ui/components` (resolves to index.ts)
925    /// - This function follows the export chain and marks `WithLabel.vue` as used
926    pub fn find_unused_files(&self) -> Result<Vec<i64>> {
927        let conn = self.open_conn()?;
928
929        // Build set of used files by following barrel export chains
930        let mut used_files = HashSet::new();
931
932        // Step 1: Get all files directly referenced in resolved_file_id
933        let mut stmt = conn.prepare("SELECT DISTINCT dst FROM import_edges ORDER BY dst")?;
934
935        let direct_imports: Vec<i64> = stmt
936            .query_map([], |row| row.get(0))?
937            .collect::<Result<Vec<_>, _>>()?;
938
939        used_files.extend(&direct_imports);
940
941        // Step 2: For each direct import, follow barrel export chains
942        for file_id in direct_imports {
943            // Resolve through barrel exports to find all indirectly used files
944            let barrel_chain = self.resolve_through_barrel_exports(file_id)?;
945            used_files.extend(barrel_chain);
946        }
947
948        // Step 3: Get all files NOT in the used set, excluding known entry points.
949        // Entry points are always reachable by definition (they are the roots of the dep graph).
950        let mut stmt = conn.prepare(&format!(
951            "SELECT id, path FROM files WHERE {CODE_FILES} ORDER BY walk_seq"
952        ))?;
953        let all_files: Vec<(i64, String)> = stmt
954            .query_map([], |row| Ok((row.get(0)?, row.get(1)?)))?
955            .collect::<Result<Vec<_>, _>>()?;
956
957        // A package whose member is used or an entry point is used as a whole
958        // (`cmd/x/flags.go` beside `cmd/x/main.go`)
959        let mut entry_points: HashSet<i64> = all_files
960            .iter()
961            .filter(|(_, path)| is_entry_point(path))
962            .map(|(id, _)| *id)
963            .collect();
964        // A SwiftPM executable, test, plugin or macro target: its `@main` file can
965        // have any name
966        let mut stmt = conn.prepare("SELECT file_id FROM package_members WHERE member = ?1")?;
967        for id in stmt.query_map([crate::parsers::swift_imports::ENTRY_MEMBER], |row| {
968            row.get::<_, i64>(0)
969        })? {
970            entry_points.insert(id?);
971        }
972        for group in sibling_groups(&conn)? {
973            if group
974                .iter()
975                .any(|id| used_files.contains(id) || entry_points.contains(id))
976            {
977                used_files.extend(group);
978            }
979        }
980
981        let unused: Vec<i64> = all_files
982            .into_iter()
983            .filter(|(id, path)| !used_files.contains(id) && !is_entry_point(path))
984            .map(|(id, _)| id)
985            .collect();
986
987        Ok(unused)
988    }
989
990    /// Resolve barrel export chains to find all files transitively exported from a given file
991    ///
992    /// Given a barrel file (e.g., `index.ts` that re-exports from other files), this function
993    /// follows the export chain to find all source files that are transitively exported.
994    ///
995    /// # Example
996    ///
997    /// If `packages/ui/components/index.ts` contains:
998    /// ```typescript
999    /// export { default as WithLabel } from './WithLabel.vue';
1000    /// export { default as Button } from './Button.vue';
1001    /// ```
1002    ///
1003    /// Then calling this with the file_id of `index.ts` will return the file IDs of
1004    /// `WithLabel.vue` and `Button.vue`.
1005    ///
1006    /// # Arguments
1007    ///
1008    /// * `barrel_file_id` - File ID of the barrel file to start from
1009    ///
1010    /// # Returns
1011    ///
1012    /// Vec of file IDs that are transitively exported (includes the barrel file itself)
1013    pub fn resolve_through_barrel_exports(&self, barrel_file_id: i64) -> Result<Vec<i64>> {
1014        let conn = self.open_conn()?;
1015
1016        let mut resolved_files = Vec::new();
1017        let mut visited = HashSet::new();
1018        let mut queue = VecDeque::new();
1019
1020        // Start with the barrel file itself
1021        queue.push_back(barrel_file_id);
1022        visited.insert(barrel_file_id);
1023
1024        while let Some(current_id) = queue.pop_front() {
1025            resolved_files.push(current_id);
1026
1027            // Get all exports from this file
1028            let mut stmt = conn.prepare(
1029                "SELECT resolved_source_id
1030                 FROM file_exports
1031                 WHERE file_id = ? AND resolved_source_id IS NOT NULL",
1032            )?;
1033
1034            let exported_files: Vec<i64> = stmt
1035                .query_map([current_id], |row| row.get(0))?
1036                .collect::<Result<Vec<_>, _>>()?;
1037
1038            // Follow each exported file
1039            for exported_id in exported_files {
1040                if !visited.contains(&exported_id) {
1041                    visited.insert(exported_id);
1042                    queue.push_back(exported_id);
1043                }
1044            }
1045        }
1046
1047        Ok(resolved_files)
1048    }
1049
1050    /// Find disconnected components (islands) in the dependency graph
1051    ///
1052    /// An "island" is a connected component - a group of files that depend on each
1053    /// other (directly or transitively) but have no dependencies to files outside
1054    /// the group.
1055    ///
1056    /// This is useful for identifying:
1057    /// - Independent subsystems that could be extracted as separate modules
1058    /// - Unreachable code clusters that might be dead code
1059    /// - Microservice boundaries in a monolith
1060    ///
1061    /// Returns a list of islands, where each island is a vector of file IDs.
1062    /// Islands are sorted by size (largest first).
1063    pub fn find_islands(&self) -> Result<Vec<Vec<i64>>> {
1064        let conn = self.open_conn()?;
1065
1066        // Build undirected dependency graph (A imports B => edge A-B and B-A)
1067        let mut graph: HashMap<i64, Vec<i64>> = HashMap::new();
1068
1069        // Rows in (importer walk order, row order): the order a full build inserts
1070        // them in. Adjacency order decides each island's member order.
1071        // Build adjacency list (undirected) directly from resolved IDs
1072        for (file_id, target_id) in load_edges(&conn, EdgeOrder::ImporterWalk, true)? {
1073            // Add edge in both directions for undirected graph
1074            graph.entry(file_id).or_default().push(target_id);
1075            graph.entry(target_id).or_default().push(file_id);
1076        }
1077
1078        // Files of one package belong together even when none imports another
1079        for group in sibling_groups(&conn)? {
1080            for pair in group.windows(2) {
1081                graph.entry(pair[0]).or_default().push(pair[1]);
1082                graph.entry(pair[1]).or_default().push(pair[0]);
1083            }
1084        }
1085
1086        // Get all file IDs (including isolated files with no dependencies)
1087        let all_files = self.get_all_file_ids()?;
1088
1089        // Ensure all files are in the graph (even if they have no edges)
1090        for file_id in &all_files {
1091            graph.entry(*file_id).or_default();
1092        }
1093
1094        // Find connected components using DFS
1095        let mut visited = HashSet::new();
1096        let mut islands = Vec::new();
1097
1098        for &file_id in &all_files {
1099            if !visited.contains(&file_id) {
1100                let mut island = Vec::new();
1101                self.dfs_island(&file_id, &graph, &mut visited, &mut island);
1102                islands.push(island);
1103            }
1104        }
1105
1106        // Sort islands by size (largest first)
1107        islands.sort_by_key(|a: &Vec<_>| std::cmp::Reverse(a.len()));
1108
1109        log::info!("Found {} islands (connected components)", islands.len());
1110
1111        Ok(islands)
1112    }
1113
1114    /// DFS for finding connected components (islands). Iterative, in the
1115    /// preorder the recursive version produced.
1116    fn dfs_island(
1117        &self,
1118        start: &i64,
1119        graph: &HashMap<i64, Vec<i64>>,
1120        visited: &mut HashSet<i64>,
1121        island: &mut Vec<i64>,
1122    ) {
1123        const NONE: &[i64] = &[];
1124        visited.insert(*start);
1125        island.push(*start);
1126        let mut stack: Vec<(i64, usize)> = vec![(*start, 0)];
1127        while let Some((node, next)) = stack.last_mut() {
1128            let neighbors = graph.get(node).map_or(NONE, Vec::as_slice);
1129            match neighbors.get(*next) {
1130                Some(&neighbor) => {
1131                    *next += 1;
1132                    if visited.insert(neighbor) {
1133                        island.push(neighbor);
1134                        stack.push((neighbor, 0));
1135                    }
1136                }
1137                None => {
1138                    stack.pop();
1139                }
1140            }
1141        }
1142    }
1143
1144    /// Build a cache of imported_path → file_id mappings for efficient lookup
1145    ///
1146    /// This method queries all unique imported_path values from the database
1147    /// and resolves each one to a file_id using fuzzy matching. The resulting
1148    /// cache enables O(1) lookups instead of repeated database queries.
1149    ///
1150    /// This is used internally by graph analysis operations (hotspots, circular
1151    /// dependencies, reverse lookups, etc.) to avoid O(N*M*K) query complexity.
1152    ///
1153    /// # Performance
1154    ///
1155    /// Building the cache requires O(N*M) queries where:
1156    /// - N = number of unique imported_path values (~1,000-5,000)
1157    /// - M = average number of path variants tried per path (~10)
1158    ///
1159    /// However, this is done ONCE upfront, enabling O(1) lookups for all
1160    /// subsequent operations. Without caching, each operation would make
1161    /// 10,000-100,000+ queries.
1162    ///
1163    /// # Returns
1164    ///
1165    /// HashMap mapping imported_path to resolved file_id (only includes
1166    /// successfully resolved paths; external/unresolved paths are omitted)
1167    #[allow(dead_code)]
1168    fn build_resolution_cache(&self) -> Result<HashMap<String, i64>> {
1169        let conn = self.open_conn()?;
1170
1171        // Get all unique imported_path values (single query)
1172        let mut stmt = conn.prepare("SELECT DISTINCT imported_path FROM file_dependencies")?;
1173
1174        let imported_paths: Vec<String> = stmt
1175            .query_map([], |row| row.get(0))?
1176            .collect::<Result<Vec<_>, _>>()?;
1177
1178        let total_paths = imported_paths.len();
1179        log::info!(
1180            "Building resolution cache for {} unique imported paths",
1181            total_paths
1182        );
1183
1184        // Resolve each imported_path once
1185        let mut cache = HashMap::new();
1186
1187        for imported_path in imported_paths {
1188            if let Ok(Some(file_id)) = self.resolve_imported_path_to_file_id(&imported_path) {
1189                cache.insert(imported_path, file_id);
1190            }
1191        }
1192
1193        log::info!(
1194            "Resolution cache built: {} resolved, {} unresolved",
1195            cache.len(),
1196            total_paths - cache.len()
1197        );
1198
1199        Ok(cache)
1200    }
1201
1202    /// Clear all dependencies for a file (used during incremental reindexing)
1203    pub fn clear_dependencies(&self, file_id: i64) -> Result<()> {
1204        let conn = self.open_conn()?;
1205
1206        conn.execute("DELETE FROM file_dependencies WHERE file_id = ?", [file_id])?;
1207
1208        Ok(())
1209    }
1210
1211    /// Resolve an imported path to a file ID using fuzzy matching
1212    ///
1213    /// This method converts an import path (e.g., namespace, module path) to various
1214    /// file path variants and tries to find a matching file using fuzzy path matching.
1215    ///
1216    /// # Arguments
1217    ///
1218    /// * `imported_path` - The import path as stored in the database
1219    ///   (e.g., "Rcm\\Http\\Controllers\\Controller", "crate::models", etc.)
1220    ///
1221    /// # Returns
1222    ///
1223    /// `Some(file_id)` if exactly one matching file is found, `None` otherwise
1224    ///
1225    /// # Examples
1226    ///
1227    /// - `Rcm\\Http\\Controllers\\Controller` → finds `services/php/rcm-backend/app/Http/Controllers/Controller.php`
1228    /// - `crate::models` → finds `src/models.rs`
1229    pub fn resolve_imported_path_to_file_id(&self, imported_path: &str) -> Result<Option<i64>> {
1230        let path_variants = generate_path_variants(imported_path);
1231
1232        for variant in &path_variants {
1233            if let Ok(Some(file_id)) = self.get_file_id_by_path(variant) {
1234                log::trace!(
1235                    "Resolved '{}' → '{}' (file_id: {})",
1236                    imported_path,
1237                    variant,
1238                    file_id
1239                );
1240                return Ok(Some(file_id));
1241            }
1242        }
1243
1244        Ok(None)
1245    }
1246
1247    /// Get file ID by path with fuzzy matching support
1248    ///
1249    /// Supports various path formats:
1250    /// - Exact paths: `services/php/app/Http/Controllers/FooController.php`
1251    /// - Relative paths: `./services/php/app/Http/Controllers/FooController.php`
1252    /// - Path fragments: `Controllers/FooController.php` or `FooController.php`
1253    /// - Absolute paths: `/home/user/project/services/php/.../FooController.php`
1254    ///
1255    /// Returns None if no matches found.
1256    /// Returns error if multiple matches found (ambiguous path fragment).
1257    pub fn get_file_id_by_path(&self, path: &str) -> Result<Option<i64>> {
1258        let conn = self.open_conn()?;
1259
1260        // Normalize path: strip ./ prefix, ../ prefix, and convert absolute to relative
1261        let normalized_path = normalize_path_for_lookup(path);
1262
1263        // Try exact match first (fast path)
1264        match conn.query_row(
1265            "SELECT id FROM files WHERE path = ?",
1266            [&normalized_path],
1267            |row| row.get::<_, i64>(0),
1268        ) {
1269            Ok(id) => return Ok(Some(id)),
1270            Err(rusqlite::Error::QueryReturnedNoRows) => {
1271                // No exact match, try suffix match
1272            }
1273            Err(e) => return Err(e.into()),
1274        }
1275
1276        // Try suffix match: files whose path ends with `/` + the normalized path
1277        // (whole segments; ASCII case-insensitive, as `PathResolver` matches)
1278        let mut stmt = conn.prepare(
1279            "SELECT id, path FROM files
1280             WHERE lower(path) = lower(?1)
1281                OR lower(substr(path, -(length(?1) + 1))) = lower('/' || ?1)",
1282        )?;
1283
1284        let matches: Vec<(i64, String)> = stmt
1285            .query_map([&normalized_path], |row| Ok((row.get(0)?, row.get(1)?)))?
1286            .collect::<Result<Vec<_>, _>>()?;
1287
1288        match matches.len() {
1289            0 => Ok(None),
1290            1 => Ok(Some(matches[0].0)),
1291            _ => {
1292                // Multiple matches - return error with suggestions
1293                let paths: Vec<String> = matches.iter().map(|(_, p)| p.clone()).collect();
1294                anyhow::bail!(
1295                    "Ambiguous path '{}' matches multiple files:\n  {}\n\nPlease be more specific.",
1296                    path,
1297                    paths.join("\n  ")
1298                );
1299            }
1300        }
1301    }
1302
1303    /// Internal imports per language (the `files.language` name) and how many of them
1304    /// resolve to an indexed file, in language order.
1305    ///
1306    /// The graph `analyze` and `get_dependencies` answer from holds only resolved
1307    /// imports, so a low rate means those answers are incomplete for that language.
1308    pub fn internal_resolution_by_language(&self) -> Result<Vec<LanguageResolution>> {
1309        let conn = self.open_conn()?;
1310        let mut stmt = conn.prepare(
1311            "SELECT f.language, COUNT(*),
1312                    SUM(d.resolved_file_id IS NOT NULL
1313                        OR EXISTS (SELECT 1 FROM package_members m
1314                                    WHERE m.package = d.resolved_package
1315                                      AND m.member = COALESCE(d.resolved_member, '')
1316                                      AND m.file_id != d.file_id))
1317             FROM file_dependencies d
1318             JOIN files f ON d.file_id = f.id
1319             WHERE d.import_type = 'internal'
1320               -- vendored code's own imports are not the project's graph
1321               AND f.vendored = 0
1322               -- C# calls every non-System using internal: leave out the NuGet ones,
1323               -- whose root namespace (`Newtonsoft` of `Newtonsoft.Json`) no file declares
1324               AND NOT (COALESCE(d.resolved_package, '') LIKE 'cs:%' AND NOT EXISTS (
1325                   SELECT 1 FROM package_members m,
1326                       (SELECT 'cs:' || CASE WHEN instr(substr(d.resolved_package, 4), '.') > 0
1327                            THEN substr(d.resolved_package, 4, instr(substr(d.resolved_package, 4), '.') - 1)
1328                            ELSE substr(d.resolved_package, 4) END AS root)
1329                   WHERE m.package = root
1330                      OR (m.package > root || '.' AND m.package < root || '/')))
1331             GROUP BY f.language
1332             ORDER BY f.language",
1333        )?;
1334        let rows = stmt.query_map([], |row| {
1335            Ok(LanguageResolution {
1336                language: row.get(0)?,
1337                internal: row.get::<_, i64>(1)? as usize,
1338                resolved: row.get::<_, i64>(2)? as usize,
1339            })
1340        })?;
1341        Ok(rows.collect::<Result<Vec<_>, _>>()?)
1342    }
1343
1344    /// The low-resolution warning for the language of the file at `path`, if any.
1345    /// Vendored code files (`files.vendored`, text tiers left out): searchable, but
1346    /// not in the import graph (see [`crate::vendor`]).
1347    pub fn vendored_file_count(&self) -> Result<usize> {
1348        let conn = self.open_conn()?;
1349        let n: i64 = conn.query_row(
1350            "SELECT COUNT(*) FROM files
1351             WHERE vendored = 1 AND language NOT IN ('Text', 'Lock', 'Generated', 'Unknown')",
1352            [],
1353            |r| r.get(0),
1354        )?;
1355        Ok(n as usize)
1356    }
1357
1358    /// The warnings a `get_dependencies` answer about `path` carries: the file is
1359    /// vendored (so it has no edges), or its language's graph is mostly missing.
1360    pub fn graph_warnings_for(&self, path: &str) -> Result<Vec<String>> {
1361        let Some(id) = self.get_file_id_by_path(path).ok().flatten() else {
1362            return Ok(Vec::new());
1363        };
1364        let conn = self.open_conn()?;
1365        let vendored: bool =
1366            conn.query_row("SELECT vendored FROM files WHERE id = ?", [id], |r| {
1367                r.get(0)
1368            })?;
1369        if vendored {
1370            return Ok(vec![format!(
1371                "{path} is vendored; vendored files are not in the import graph"
1372            )]);
1373        }
1374        Ok(self.low_resolution_warning_for(path)?.into_iter().collect())
1375    }
1376
1377    pub fn low_resolution_warning_for(&self, path: &str) -> Result<Option<String>> {
1378        let Some(id) = self.get_file_id_by_path(path).ok().flatten() else {
1379            return Ok(None);
1380        };
1381        let conn = self.open_conn()?;
1382        let language: Option<String> = conn
1383            .query_row("SELECT language FROM files WHERE id = ?", [id], |row| {
1384                row.get(0)
1385            })
1386            .ok();
1387        Ok(language.and_then(|language| {
1388            self.internal_resolution_by_language()
1389                .ok()?
1390                .into_iter()
1391                .find(|l| l.language == language && l.is_low())
1392                .map(|l| l.warning())
1393        }))
1394    }
1395
1396    /// One warning per language whose graph is mostly missing: at least
1397    /// [`LOW_RESOLUTION_MIN_IMPORTS`] internal imports, under [`LOW_RESOLUTION_RATE`]
1398    /// of them resolved. Front ends attach these to `analyze` and `get_dependencies`
1399    /// answers so a graph built from 0.3 % of the edges is never presented as fact.
1400    pub fn low_resolution_warnings(&self) -> Result<Vec<String>> {
1401        Ok(self
1402            .internal_resolution_by_language()?
1403            .iter()
1404            .filter(|l| l.is_low())
1405            .map(LanguageResolution::warning)
1406            .collect())
1407    }
1408
1409    /// Get all internal dependencies with their resolution status
1410    ///
1411    /// Returns detailed information about each internal dependency including source file,
1412    /// imported path, and whether it was successfully resolved.
1413    ///
1414    /// # Returns
1415    ///
1416    /// A vector of tuples: (source_file, imported_path, resolved_file_path)
1417    /// where resolved_file_path is None if the dependency couldn't be resolved.
1418    pub fn get_all_internal_dependencies(&self) -> Result<Vec<(String, String, Option<String>)>> {
1419        let conn = self.open_conn()?;
1420
1421        let mut stmt = conn.prepare(
1422            "SELECT
1423                f.path,
1424                d.imported_path,
1425                f2.path as resolved_path
1426            FROM file_dependencies d
1427            JOIN files f ON d.file_id = f.id
1428            LEFT JOIN files f2 ON d.resolved_file_id = f2.id
1429            WHERE d.import_type = 'internal'
1430            ORDER BY f.path",
1431        )?;
1432
1433        let mut deps = Vec::new();
1434
1435        let rows = stmt.query_map([], |row| {
1436            Ok((
1437                row.get::<_, String>(0)?,
1438                row.get::<_, String>(1)?,
1439                row.get::<_, Option<String>>(2)?,
1440            ))
1441        })?;
1442
1443        for row in rows {
1444            deps.push(row?);
1445        }
1446
1447        Ok(deps)
1448    }
1449
1450    /// Get total count of dependencies by type (for debugging)
1451    pub fn get_dependency_count_by_type(&self) -> Result<Vec<(String, usize)>> {
1452        let conn = self.open_conn()?;
1453
1454        let mut stmt = conn.prepare(
1455            "SELECT import_type, COUNT(*) as count
1456             FROM file_dependencies
1457             GROUP BY import_type
1458             ORDER BY import_type",
1459        )?;
1460
1461        let mut counts = Vec::new();
1462
1463        let rows = stmt.query_map([], |row| {
1464            Ok((row.get::<_, String>(0)?, row.get::<_, i64>(1)? as usize))
1465        })?;
1466
1467        for row in rows {
1468            counts.push(row?);
1469        }
1470
1471        Ok(counts)
1472    }
1473}
1474
1475/// The order [`load_edges`] returns edges in: the row order each graph reader read
1476/// `file_dependencies` in before package edges existed, so outputs are unchanged.
1477#[derive(Clone, Copy)]
1478enum EdgeOrder {
1479    /// By importer id, then import row (cycle detection).
1480    ImporterId,
1481    /// By importer walk position, then import row (islands).
1482    ImporterWalk,
1483}
1484
1485/// Every import edge `(importer, imported file)` once, file-resolved and
1486/// package-expanded (`import_edges`), targets of one import in walk order.
1487/// With `every_edge` false (cycle detection), Rust `mod foo;` edges (ownership
1488/// rather than use) and C# whole-namespace edges are left out.
1489fn load_edges(conn: &Connection, order: EdgeOrder, every_edge: bool) -> Result<Vec<(i64, i64)>> {
1490    let order_by = match order {
1491        EdgeOrder::ImporterId => "e.src, e.dep_id, t.walk_seq",
1492        EdgeOrder::ImporterWalk => "s.walk_seq, e.dep_id, t.walk_seq",
1493    };
1494    let filter = if every_edge {
1495        ""
1496    } else {
1497        // Cycles: a C# `using` reaches every file of a namespace, which is no
1498        // evidence that this file uses that one, and namespaces commonly use each
1499        // other; as file edges they made 11,130 "cycles" of dotnet/runtime.
1500        "WHERE e.import_type != 'mod_decl' AND (e.package IS NULL OR e.package NOT LIKE 'cs:%')"
1501    };
1502    let mut stmt = conn.prepare(&format!(
1503        "SELECT e.src, e.dst FROM import_edges e
1504         JOIN files s ON s.id = e.src
1505         JOIN files t ON t.id = e.dst
1506         {filter}
1507         ORDER BY {order_by}"
1508    ))?;
1509    let mut seen = HashSet::new();
1510    let edges = stmt
1511        .query_map([], |row| Ok((row.get::<_, i64>(0)?, row.get::<_, i64>(1)?)))?
1512        .collect::<Result<Vec<_>, _>>()?;
1513    Ok(edges.into_iter().filter(|e| seen.insert(*e)).collect())
1514}
1515
1516/// The member files of each Go package and SwiftPM target, in walk order. They
1517/// compile as one unit and use each other with no import, so islands and unused
1518/// files treat each group as connected. (JVM and C# packages are not: a
1519/// namespace can span unrelated projects.)
1520fn sibling_groups(conn: &Connection) -> Result<Vec<Vec<i64>>> {
1521    let mut stmt = conn.prepare(
1522        "SELECT m.package, m.file_id FROM package_members m
1523         JOIN files f ON f.id = m.file_id
1524         WHERE (m.package LIKE 'go:%' OR m.package LIKE 'swift:%') AND m.member = ''
1525           AND f.vendored = 0
1526         ORDER BY m.package, f.walk_seq",
1527    )?;
1528    let mut groups: Vec<Vec<i64>> = Vec::new();
1529    let mut current: Option<String> = None;
1530    let rows = stmt.query_map([], |row| {
1531        Ok((row.get::<_, String>(0)?, row.get::<_, i64>(1)?))
1532    })?;
1533    for row in rows {
1534        let (package, id) = row?;
1535        if current.as_deref() != Some(package.as_str()) {
1536            groups.push(Vec::new());
1537            current = Some(package);
1538        }
1539        groups.last_mut().expect("pushed above").push(id);
1540    }
1541    Ok(groups)
1542}
1543
1544/// `files` rows that can take part in the import graph. Text, lock and generated
1545/// files have no import extraction, so as graph nodes they were only ever islands
1546/// and "unused" (every README and lock file on 2.1.0).
1547const CODE_FILES: &str =
1548    "language NOT IN ('Text', 'Lock', 'Generated', 'Unknown') AND vendored = 0";
1549
1550/// Return true if the given file path is a well-known project entry point.
1551///
1552/// Entry points are always reachable by definition and should never appear in the
1553/// "unused files" list even when nothing else imports them (REF-89).
1554fn is_entry_point(path: &str) -> bool {
1555    let p = path.replace('\\', "/");
1556    let p = p.as_str();
1557
1558    // Exact well-known Rust/generic entry points
1559    if matches!(
1560        p,
1561        "src/lib.rs" | "src/main.rs" | "build.rs" | "lib.rs" | "main.rs"
1562    ) {
1563        return true;
1564    }
1565
1566    // Test / bench / example / fixture directories, at any depth (`staging/x/test/`,
1567    // Maven's `src/test/`, a .NET `Foo.Tests/` project)
1568    let (dirs, filename) = match p.rsplit_once('/') {
1569        Some((dirs, name)) => (dirs, name),
1570        None => ("", p),
1571    };
1572    if dirs.split('/').any(|d| {
1573        matches!(
1574            d,
1575            "tests" | "Tests" | "test" | "benches" | "examples" | "testdata" | "__tests__"
1576        ) || d.ends_with(".Tests")
1577            || d.ends_with(".UnitTests")
1578    }) {
1579        return true;
1580    }
1581
1582    // Program entry points by language convention
1583    if matches!(
1584        filename,
1585        "main.go"
1586            | "Program.cs"
1587            | "__main__.py"
1588            | "manage.py"
1589            | "conftest.py"
1590            | "setup.py"
1591            | "main.swift"
1592            | "Package.swift"
1593    ) || (filename.starts_with("Package@swift-") && filename.ends_with(".swift"))
1594    {
1595        return true;
1596    }
1597
1598    // Files whose names follow common test/spec conventions
1599    let stem = filename.rsplit_once('.').map_or(filename, |(stem, _)| stem);
1600    filename.starts_with("test_")
1601        || filename.ends_with("_test.rs")
1602        || filename.ends_with("_spec.rs")
1603        || filename.ends_with("_test.go")
1604        || filename.ends_with("_test.py")
1605        || ((filename.ends_with(".java")
1606            || filename.ends_with(".kt")
1607            || filename.ends_with(".cs")
1608            || filename.ends_with(".swift"))
1609            && (stem.ends_with("Test")
1610                || stem.ends_with("Tests")
1611                // Maven Failsafe integration tests: `FooIT`, not `EXIT`
1612                || stem
1613                    .strip_suffix("IT")
1614                    .and_then(|s| s.chars().last())
1615                    .is_some_and(char::is_lowercase)))
1616}
1617
1618/// Generate path variants for an import path
1619///
1620/// Converts a namespace/import path to multiple file path variants for fuzzy matching.
1621/// Tries progressively shorter paths to handle custom PSR-4 mappings.
1622///
1623/// Examples:
1624/// - `Rcm\\Http\\Controllers\\Controller` →
1625///   - `Rcm/Http/Controllers/Controller.php`
1626///   - `Http/Controllers/Controller.php`
1627///   - `Controllers/Controller.php`
1628///   - `Controller.php`
1629fn generate_path_variants(import_path: &str) -> Vec<String> {
1630    // Convert namespace separators to path separators
1631    let path = import_path.replace('\\', "/").replace("::", "/");
1632
1633    // Remove quotes if present (some languages quote import paths)
1634    let path = path.trim_matches('"').trim_matches('\'');
1635
1636    // Split into components
1637    let components: Vec<&str> = path.split('/').filter(|s| !s.is_empty()).collect();
1638
1639    if components.is_empty() {
1640        return vec![];
1641    }
1642
1643    let mut variants = Vec::new();
1644
1645    // Generate progressively shorter paths
1646    // E.g., for "Rcm/Http/Controllers/Controller":
1647    // 1. Rcm/Http/Controllers/Controller.php (full path)
1648    // 2. Http/Controllers/Controller.php (without first component)
1649    // 3. Controllers/Controller.php (without first two)
1650    // 4. Controller.php (just the class name)
1651    for start_idx in 0..components.len() {
1652        let suffix = components[start_idx..].join("/");
1653
1654        // Try with .php extension (most common)
1655        if !suffix.ends_with(".php") {
1656            variants.push(format!("{}.php", suffix));
1657        } else {
1658            variants.push(suffix.clone());
1659        }
1660
1661        // Also try without extension (for languages that don't use extensions in imports)
1662        if !suffix.contains('.') {
1663            // Try common extensions
1664            variants.push(format!("{}.rs", suffix));
1665            variants.push(format!("{}.ts", suffix));
1666            variants.push(format!("{}.js", suffix));
1667            variants.push(format!("{}.py", suffix));
1668        }
1669    }
1670
1671    variants
1672}
1673
1674/// Normalize a path for fuzzy lookup
1675///
1676/// Strips common prefixes that might differ between query and database:
1677/// - `./` and `../` prefixes
1678/// - Absolute paths (converts to relative by taking only the path component)
1679///
1680/// Examples:
1681/// - `./services/foo.php` → `services/foo.php`
1682/// - `/home/user/project/services/foo.php` → `services/foo.php` (just filename portion)
1683/// - `GetCaseByBatchNumberController.php` → `GetCaseByBatchNumberController.php`
1684fn normalize_path_for_lookup(path: &str) -> String {
1685    // Strip ./ and ../ prefixes
1686    let mut normalized = path.trim_start_matches("./").to_string();
1687    if normalized.starts_with("../") {
1688        normalized = normalized.trim_start_matches("../").to_string();
1689    }
1690
1691    // If it's an absolute path, extract the relevant portion
1692    // This handles cases like `/home/user/Code/project/services/php/...`
1693    // We want to extract just `services/php/...` part
1694    if normalized.starts_with('/') || normalized.starts_with('\\') {
1695        // Common project markers (ordered by priority)
1696        let markers = ["services", "src", "app", "lib", "packages", "modules"];
1697
1698        let mut found_marker = false;
1699        for marker in &markers {
1700            if let Some(idx) = normalized.find(marker) {
1701                normalized = normalized[idx..].to_string();
1702                found_marker = true;
1703                break;
1704            }
1705        }
1706
1707        // If no marker found, just use the filename
1708        if !found_marker {
1709            use std::path::Path;
1710            let path_obj = Path::new(&normalized);
1711            if let Some(filename) = path_obj.file_name() {
1712                normalized = filename.to_string_lossy().to_string();
1713            }
1714        }
1715    }
1716
1717    normalized
1718}
1719
1720/// Resolve a Rust import path to an absolute file path
1721///
1722/// This function handles Rust-specific path resolution rules:
1723/// - `crate::` - Starts from crate root (src/lib.rs or src/main.rs)
1724/// - `super::` - Goes up one module level
1725/// - `self::` - Stays in current module
1726/// - `mod name` - Looks for name.rs or name/mod.rs
1727/// - External crates - Returns None
1728///
1729/// # Arguments
1730///
1731/// * `import_path` - The import path as written in source (e.g., "crate::models::Language")
1732/// * `current_file` - Path to the file containing the import (e.g., "src/query.rs")
1733/// * `project_root` - Root directory of the project
1734///
1735/// # Returns
1736///
1737/// `Some(path)` if the import resolves to a project file, `None` if it's external/stdlib
1738pub fn resolve_rust_import(
1739    import_path: &str,
1740    current_file: &str,
1741    project_root: &std::path::Path,
1742) -> Option<String> {
1743    use std::path::{Path, PathBuf};
1744
1745    // External crates and stdlib - don't resolve
1746    if !import_path.starts_with("crate::")
1747        && !import_path.starts_with("super::")
1748        && !import_path.starts_with("self::")
1749    {
1750        return None;
1751    }
1752
1753    let current_path = Path::new(current_file);
1754    let mut resolved_path: Option<PathBuf> = None;
1755
1756    if import_path.starts_with("crate::") {
1757        // Start from crate root (src/lib.rs or src/main.rs)
1758        let crate_root = if project_root.join("src/lib.rs").exists()
1759            || project_root.join("src/main.rs").exists()
1760        {
1761            project_root.join("src")
1762        } else {
1763            // Fallback to src/ directory
1764            project_root.join("src")
1765        };
1766
1767        let path_parts: Vec<&str> = import_path
1768            .strip_prefix("crate::")
1769            .unwrap()
1770            .split("::")
1771            .collect();
1772
1773        resolved_path = resolve_module_path(&crate_root, &path_parts);
1774    } else if import_path.starts_with("super::") {
1775        // Go up one directory from current file's parent (the current module's parent)
1776        if let Some(current_dir) = current_path.parent()
1777            && let Some(parent_dir) = current_dir.parent()
1778        {
1779            let path_parts: Vec<&str> = import_path
1780                .strip_prefix("super::")
1781                .unwrap()
1782                .split("::")
1783                .collect();
1784
1785            resolved_path = resolve_module_path(parent_dir, &path_parts);
1786        }
1787    } else if import_path.starts_with("self::") {
1788        // Stay in current directory
1789        if let Some(current_dir) = current_path.parent() {
1790            let path_parts: Vec<&str> = import_path
1791                .strip_prefix("self::")
1792                .unwrap()
1793                .split("::")
1794                .collect();
1795
1796            resolved_path = resolve_module_path(current_dir, &path_parts);
1797        }
1798    }
1799
1800    // Convert to string and make relative to project root.
1801    // Normalize to forward slashes so paths are deterministic across platforms.
1802    resolved_path.and_then(|p| {
1803        p.strip_prefix(project_root)
1804            .ok()
1805            .map(|rel| rel.to_string_lossy().replace('\\', "/"))
1806    })
1807}
1808
1809/// Resolve a module path given a starting directory and path components
1810///
1811/// Handles Rust's module system rules:
1812/// - `foo` → check foo.rs or foo/mod.rs
1813/// - `foo::bar` → check foo/bar.rs or foo/bar/mod.rs
1814fn resolve_module_path(
1815    start_dir: &std::path::Path,
1816    components: &[&str],
1817) -> Option<std::path::PathBuf> {
1818    if components.is_empty() {
1819        return None;
1820    }
1821
1822    let mut current = start_dir.to_path_buf();
1823
1824    // For all components except the last, they must be directories
1825    for &component in &components[..components.len() - 1] {
1826        // Try as a directory with mod.rs
1827        let dir_path = current.join(component);
1828        let mod_file = dir_path.join("mod.rs");
1829
1830        if mod_file.exists() {
1831            current = dir_path;
1832        } else {
1833            // Component must be a directory for nested paths
1834            return None;
1835        }
1836    }
1837
1838    // For the last component, try both file.rs and file/mod.rs
1839    let last_component = components.last().unwrap();
1840
1841    // Try as a single file
1842    let file_path = current.join(format!("{}.rs", last_component));
1843    if file_path.exists() {
1844        return Some(file_path);
1845    }
1846
1847    // Try as a directory with mod.rs
1848    let dir_path = current.join(last_component);
1849    let mod_file = dir_path.join("mod.rs");
1850    if mod_file.exists() {
1851        return Some(mod_file);
1852    }
1853
1854    None
1855}
1856
1857/// Resolve a `mod` declaration to a file path
1858///
1859/// For `mod parser;`, this checks for:
1860/// - `parser.rs` (sibling file)
1861/// - `parser/mod.rs` (directory module)
1862pub fn resolve_rust_mod_declaration(
1863    mod_name: &str,
1864    current_file: &str,
1865    _project_root: &std::path::Path,
1866) -> Option<String> {
1867    use std::path::Path;
1868
1869    let current_path = Path::new(current_file);
1870    let current_dir = current_path.parent()?;
1871
1872    // Try sibling file
1873    let sibling = current_dir.join(format!("{}.rs", mod_name));
1874    if sibling.exists() {
1875        return Some(sibling.to_string_lossy().replace('\\', "/"));
1876    }
1877
1878    // Try directory module
1879    let dir_mod = current_dir.join(mod_name).join("mod.rs");
1880    if dir_mod.exists() {
1881        return Some(dir_mod.to_string_lossy().replace('\\', "/"));
1882    }
1883
1884    None
1885}
1886
1887/// Resolve a PHP import path to a file path
1888///
1889/// This function handles PHP-specific namespace-to-file mapping:
1890/// - Converts backslash-separated namespaces to forward-slash paths
1891/// - Handles PSR-4 autoloading conventions
1892/// - Filters out external vendor namespaces (returns None for non-project code)
1893///
1894/// # Arguments
1895///
1896/// * `import_path` - PHP namespace path (e.g., "App\\Http\\Controllers\\UserController")
1897/// * `current_file` - Not used for PHP (PHP uses absolute namespaces)
1898/// * `project_root` - Root directory of the project
1899///
1900/// # Returns
1901///
1902/// `Some(path)` if the import resolves to a project file, `None` if it's external/stdlib
1903///
1904/// # Examples
1905///
1906/// - `App\\Http\\Controllers\\FooController` → `app/Http/Controllers/FooController.php`
1907/// - `App\\Models\\User` → `app/Models/User.php`
1908/// - `Illuminate\\Database\\Migration` → `None` (external vendor namespace)
1909pub fn resolve_php_import(
1910    import_path: &str,
1911    _current_file: &str,
1912    project_root: &std::path::Path,
1913) -> Option<String> {
1914    // External vendor namespaces (Laravel, Symfony, etc.) - don't resolve
1915    const VENDOR_NAMESPACES: &[&str] = &[
1916        "Illuminate\\",
1917        "Symfony\\",
1918        "Laravel\\",
1919        "Psr\\",
1920        "Doctrine\\",
1921        "Monolog\\",
1922        "PHPUnit\\",
1923        "Carbon\\",
1924        "GuzzleHttp\\",
1925        "Composer\\",
1926        "Predis\\",
1927        "League\\",
1928    ];
1929
1930    // Check if this is a vendor namespace
1931    for vendor_ns in VENDOR_NAMESPACES {
1932        if import_path.starts_with(vendor_ns) {
1933            return None;
1934        }
1935    }
1936
1937    // Convert namespace to file path
1938    // PHP namespaces use backslashes: App\Http\Controllers\FooController
1939    // Files use forward slashes: app/Http/Controllers/FooController.php
1940    let file_path = import_path.replace('\\', "/");
1941
1942    // Try common PSR-4 mappings (lowercase first component)
1943    // App\... → app/...
1944    // Database\... → database/...
1945    let path_candidates = vec![
1946        // Try with lowercase first component (PSR-4 standard)
1947        {
1948            let parts: Vec<&str> = file_path.split('/').collect();
1949            if let Some(first) = parts.first() {
1950                let mut result = vec![first.to_lowercase()];
1951                result.extend(parts[1..].iter().map(|s| s.to_string()));
1952                result.join("/") + ".php"
1953            } else {
1954                file_path.clone() + ".php"
1955            }
1956        },
1957        // Try exact path (some projects use exact case)
1958        file_path.clone() + ".php",
1959        // Try all lowercase (legacy projects)
1960        file_path.to_lowercase() + ".php",
1961    ];
1962
1963    // Check each candidate path
1964    for candidate in &path_candidates {
1965        let full_path = project_root.join(candidate);
1966        if full_path.exists() {
1967            // Return relative path
1968            return Some(candidate.clone());
1969        }
1970    }
1971
1972    // If no file found, return None (likely external or not yet created)
1973    None
1974}
1975
1976#[cfg(test)]
1977mod tests {
1978    use super::*;
1979    use tempfile::TempDir;
1980
1981    fn setup_test_cache() -> (TempDir, CacheManager) {
1982        let temp = TempDir::new().unwrap();
1983        let cache = CacheManager::new(temp.path());
1984        cache.init().unwrap();
1985
1986        // Add some test files
1987        cache.update_file("src/main.rs", "rust", 100).unwrap();
1988        cache.update_file("src/lib.rs", "rust", 50).unwrap();
1989        cache.update_file("src/utils.rs", "rust", 30).unwrap();
1990
1991        (temp, cache)
1992    }
1993
1994    /// A Go-style package import: one row keyed by package, expanded to every
1995    /// member file when the graph is read.
1996    #[test]
1997    fn package_import_links_every_member() {
1998        let temp = TempDir::new().unwrap();
1999        let cache = CacheManager::new(temp.path());
2000        cache.init().unwrap();
2001        cache.update_file("cmd/a.go", "Go", 10).unwrap();
2002        cache.update_file("pkg/b/b1.go", "Go", 10).unwrap();
2003        cache.update_file("pkg/b/b2.go", "Go", 10).unwrap();
2004        let index = DependencyIndex::new(cache);
2005        let id = |p: &str| index.get_file_id_by_path(p).unwrap().unwrap();
2006        let (a, b1, b2) = (id("cmd/a.go"), id("pkg/b/b1.go"), id("pkg/b/b2.go"));
2007        {
2008            let conn = index.open_conn().unwrap();
2009            let mut writer = DependencyWriter::new(&conn);
2010            for b in [b1, b2] {
2011                writer
2012                    .replace_members(b, &[("go:pkg/b".to_string(), String::new())])
2013                    .unwrap();
2014            }
2015            writer
2016                .replace_dependencies(
2017                    a,
2018                    &[Dependency {
2019                        file_id: a,
2020                        imported_path: "example.com/m/pkg/b".to_string(),
2021                        resolved_file_id: None,
2022                        resolved_package: Some("go:pkg/b".to_string()),
2023                        resolved_member: None,
2024                        import_type: ImportType::Internal,
2025                        line_number: 3,
2026                        imported_symbols: None,
2027                    }],
2028                )
2029                .unwrap();
2030        }
2031
2032        assert_eq!(index.get_dependents(b2).unwrap(), vec![a]);
2033        let mut reached: Vec<i64> = index
2034            .get_transitive_deps(a, 1)
2035            .unwrap()
2036            .into_keys()
2037            .collect();
2038        reached.sort();
2039        assert_eq!(reached, vec![a, b1, b2]);
2040        assert_eq!(index.find_islands().unwrap(), vec![vec![a, b1, b2]]);
2041        assert_eq!(
2042            index.find_hotspots(None, 1).unwrap(),
2043            vec![(b1, 1), (b2, 1)]
2044        );
2045        assert!(!index.find_unused_files().unwrap().contains(&b2));
2046        assert_eq!(
2047            index.internal_resolution_by_language().unwrap(),
2048            vec![LanguageResolution {
2049                language: "Go".to_string(),
2050                internal: 1,
2051                resolved: 1,
2052            }]
2053        );
2054        let info = index.get_dependencies_info(a).unwrap();
2055        assert_eq!(info.len(), 1, "one entry per import: {info:?}");
2056        assert_eq!(
2057            info[0].resolved_paths,
2058            Some(vec!["pkg/b/b1.go".to_string(), "pkg/b/b2.go".to_string()])
2059        );
2060    }
2061
2062    #[test]
2063    fn entry_points_cover_each_language() {
2064        for p in [
2065            "src/main.rs",
2066            "tests/a.rs",
2067            "staging/src/k8s.io/api/test/x.go",
2068            "cmd/kubelet/main.go",
2069            "pkg/a/a_test.go",
2070            "pkg/a/testdata/x.go",
2071            "module/src/test/java/org/x/FooTest.java",
2072            "module/src/main/java/org/x/FooIT.java",
2073            "app/src/main/kotlin/FooTests.kt",
2074            "src/App/Program.cs",
2075            "src/Foo.Tests/Bar.cs",
2076            "django/__main__.py",
2077            "manage.py",
2078            "pkg/conftest.py",
2079            "pkg/test_views.py",
2080            "pkg/views_test.py",
2081        ] {
2082            assert!(is_entry_point(p), "{p}");
2083        }
2084        for p in [
2085            "src/util.rs",
2086            "pkg/a/a.go",
2087            "pkg/latest/x.go",
2088            "src/main/java/org/x/EXIT.java",
2089            "src/main/java/org/x/Audit.java",
2090            "src/App/Contest.cs",
2091            "django/db/models.py",
2092        ] {
2093            assert!(!is_entry_point(p), "{p}");
2094        }
2095    }
2096
2097    #[test]
2098    fn test_insert_and_get_dependencies() {
2099        let (_temp, cache) = setup_test_cache();
2100        let deps_index = DependencyIndex::new(cache);
2101
2102        // Get file IDs
2103        let main_id = 1i64;
2104        let lib_id = 2i64;
2105
2106        // Insert a dependency: main.rs imports lib.rs
2107        deps_index
2108            .insert_dependency(
2109                main_id,
2110                "crate::lib".to_string(),
2111                Some(lib_id),
2112                ImportType::Internal,
2113                5,
2114                None,
2115            )
2116            .unwrap();
2117
2118        // Retrieve dependencies
2119        let deps = deps_index.get_dependencies(main_id).unwrap();
2120        assert_eq!(deps.len(), 1);
2121        assert_eq!(deps[0].imported_path, "crate::lib");
2122        assert_eq!(deps[0].resolved_file_id, Some(lib_id));
2123        assert_eq!(deps[0].import_type, ImportType::Internal);
2124    }
2125
2126    #[test]
2127    fn test_reverse_lookup() {
2128        let (_temp, cache) = setup_test_cache();
2129        let deps_index = DependencyIndex::new(cache);
2130
2131        let main_id = 1i64;
2132        let lib_id = 2i64;
2133        let utils_id = 3i64;
2134
2135        // main.rs imports lib.rs
2136        deps_index
2137            .insert_dependency(
2138                main_id,
2139                "crate::lib".to_string(),
2140                Some(lib_id),
2141                ImportType::Internal,
2142                5,
2143                None,
2144            )
2145            .unwrap();
2146
2147        // utils.rs also imports lib.rs
2148        deps_index
2149            .insert_dependency(
2150                utils_id,
2151                "crate::lib".to_string(),
2152                Some(lib_id),
2153                ImportType::Internal,
2154                3,
2155                None,
2156            )
2157            .unwrap();
2158
2159        // Get files that import lib.rs
2160        let dependents = deps_index.get_dependents(lib_id).unwrap();
2161        assert_eq!(dependents.len(), 2);
2162        assert!(dependents.contains(&main_id));
2163        assert!(dependents.contains(&utils_id));
2164    }
2165
2166    #[test]
2167    fn test_transitive_dependencies() {
2168        let (_temp, cache) = setup_test_cache();
2169        let deps_index = DependencyIndex::new(cache);
2170
2171        let file1 = 1i64;
2172        let file2 = 2i64;
2173        let file3 = 3i64;
2174
2175        // file1 → file2 → file3
2176        deps_index
2177            .insert_dependency(
2178                file1,
2179                "file2".to_string(),
2180                Some(file2),
2181                ImportType::Internal,
2182                1,
2183                None,
2184            )
2185            .unwrap();
2186
2187        deps_index
2188            .insert_dependency(
2189                file2,
2190                "file3".to_string(),
2191                Some(file3),
2192                ImportType::Internal,
2193                1,
2194                None,
2195            )
2196            .unwrap();
2197
2198        // Get transitive deps at depth 2
2199        let transitive = deps_index.get_transitive_deps(file1, 2).unwrap();
2200
2201        // Should include file1 (depth 0), file2 (depth 1), file3 (depth 2)
2202        assert_eq!(transitive.len(), 3);
2203        assert_eq!(transitive.get(&file1), Some(&0));
2204        assert_eq!(transitive.get(&file2), Some(&1));
2205        assert_eq!(transitive.get(&file3), Some(&2));
2206    }
2207
2208    /// Every transitive-deps output (CLI json/tree/table, MCP) printed `HashMap`
2209    /// order through 2.2.0. Within a depth the order is walk order, not id order.
2210    #[test]
2211    fn transitive_deps_ordered_by_depth_then_walk_order() {
2212        let (_temp, cache) = setup_test_cache();
2213        let deps_index = DependencyIndex::new(cache);
2214        let id = |p: &str| deps_index.get_file_id_by_path(p).unwrap().unwrap();
2215        let (main, lib, utils) = (id("src/main.rs"), id("src/lib.rs"), id("src/utils.rs"));
2216        {
2217            let conn = deps_index.open_conn().unwrap();
2218            for (file, seq) in [(main, 1), (lib, 3), (utils, 2)] {
2219                conn.execute("UPDATE files SET walk_seq = ? WHERE id = ?", [seq, file])
2220                    .unwrap();
2221            }
2222        }
2223        for target in [lib, utils] {
2224            deps_index
2225                .insert_dependency(
2226                    main,
2227                    "x".to_string(),
2228                    Some(target),
2229                    ImportType::Internal,
2230                    1,
2231                    None,
2232                )
2233                .unwrap();
2234        }
2235
2236        let ordered = deps_index.get_transitive_deps_ordered(main, 2).unwrap();
2237        assert_eq!(ordered, vec![(main, 0), (utils, 1), (lib, 1)]);
2238    }
2239
2240    #[test]
2241    fn test_batch_insert() {
2242        let (_temp, cache) = setup_test_cache();
2243        let deps_index = DependencyIndex::new(cache);
2244
2245        let deps = vec![
2246            Dependency {
2247                file_id: 1,
2248                imported_path: "std::collections".to_string(),
2249                resolved_file_id: None,
2250                resolved_package: None,
2251                resolved_member: None,
2252                import_type: ImportType::Stdlib,
2253                line_number: 1,
2254                imported_symbols: Some(vec!["HashMap".to_string()]),
2255            },
2256            Dependency {
2257                file_id: 1,
2258                imported_path: "crate::lib".to_string(),
2259                resolved_file_id: Some(2),
2260                resolved_package: None,
2261                resolved_member: None,
2262                import_type: ImportType::Internal,
2263                line_number: 2,
2264                imported_symbols: None,
2265            },
2266        ];
2267
2268        deps_index.batch_insert_dependencies(&deps).unwrap();
2269
2270        let retrieved = deps_index.get_dependencies(1).unwrap();
2271        assert_eq!(retrieved.len(), 2);
2272    }
2273
2274    #[test]
2275    fn test_clear_dependencies() {
2276        let (_temp, cache) = setup_test_cache();
2277        let deps_index = DependencyIndex::new(cache);
2278
2279        // Insert dependencies
2280        deps_index
2281            .insert_dependency(
2282                1,
2283                "crate::lib".to_string(),
2284                Some(2),
2285                ImportType::Internal,
2286                1,
2287                None,
2288            )
2289            .unwrap();
2290
2291        // Verify they exist
2292        assert_eq!(deps_index.get_dependencies(1).unwrap().len(), 1);
2293
2294        // Clear them
2295        deps_index.clear_dependencies(1).unwrap();
2296
2297        // Verify they're gone
2298        assert_eq!(deps_index.get_dependencies(1).unwrap().len(), 0);
2299    }
2300
2301    #[test]
2302    fn test_resolve_rust_import_crate() {
2303        use std::fs;
2304        use tempfile::TempDir;
2305
2306        let temp = TempDir::new().unwrap();
2307        let project_root = temp.path();
2308
2309        // Create directory structure
2310        fs::create_dir_all(project_root.join("src")).unwrap();
2311        fs::write(project_root.join("src/lib.rs"), "").unwrap();
2312        fs::write(project_root.join("src/models.rs"), "").unwrap();
2313
2314        // Test crate:: resolution
2315        let resolved = resolve_rust_import("crate::models", "src/query.rs", project_root);
2316
2317        assert_eq!(resolved, Some("src/models.rs".to_string()));
2318    }
2319
2320    #[test]
2321    fn test_resolve_rust_import_super() {
2322        use std::fs;
2323        use tempfile::TempDir;
2324
2325        let temp = TempDir::new().unwrap();
2326        let project_root = temp.path();
2327
2328        // Create directory structure: src/parsers/rust.rs needs to import src/models.rs
2329        fs::create_dir_all(project_root.join("src/parsers")).unwrap();
2330        fs::write(project_root.join("src/models.rs"), "").unwrap();
2331        fs::write(project_root.join("src/parsers/rust.rs"), "").unwrap();
2332
2333        // Test super:: resolution from parsers/rust.rs
2334        // Use absolute path for current_file
2335        let current_file = project_root.join("src/parsers/rust.rs");
2336        let resolved = resolve_rust_import(
2337            "super::models",
2338            &current_file.to_string_lossy(),
2339            project_root,
2340        );
2341
2342        assert_eq!(resolved, Some("src/models.rs".to_string()));
2343    }
2344
2345    #[test]
2346    fn test_resolve_rust_import_external() {
2347        use tempfile::TempDir;
2348
2349        let temp = TempDir::new().unwrap();
2350        let project_root = temp.path();
2351
2352        // External crates should return None
2353        let resolved = resolve_rust_import("serde::Serialize", "src/models.rs", project_root);
2354
2355        assert_eq!(resolved, None);
2356
2357        // Stdlib should return None
2358        let resolved =
2359            resolve_rust_import("std::collections::HashMap", "src/models.rs", project_root);
2360
2361        assert_eq!(resolved, None);
2362    }
2363
2364    #[test]
2365    fn test_resolve_rust_mod_declaration() {
2366        use std::fs;
2367        use tempfile::TempDir;
2368
2369        let temp = TempDir::new().unwrap();
2370        let project_root = temp.path();
2371
2372        // Create directory structure
2373        fs::create_dir_all(project_root.join("src")).unwrap();
2374        fs::write(project_root.join("src/lib.rs"), "").unwrap();
2375        fs::write(project_root.join("src/parser.rs"), "").unwrap();
2376
2377        // Test mod declaration resolution
2378        let resolved = resolve_rust_mod_declaration(
2379            "parser",
2380            &project_root.join("src/lib.rs").to_string_lossy(),
2381            project_root,
2382        );
2383
2384        assert!(resolved.is_some());
2385        assert!(resolved.unwrap().ends_with("src/parser.rs"));
2386    }
2387
2388    #[test]
2389    fn test_resolve_rust_import_nested() {
2390        use std::fs;
2391        use tempfile::TempDir;
2392
2393        let temp = TempDir::new().unwrap();
2394        let project_root = temp.path();
2395
2396        // Create directory structure: src/models/language.rs
2397        fs::create_dir_all(project_root.join("src/models")).unwrap();
2398        fs::write(project_root.join("src/models/mod.rs"), "").unwrap();
2399        fs::write(project_root.join("src/models/language.rs"), "").unwrap();
2400
2401        // Test nested module resolution
2402        let resolved = resolve_rust_import("crate::models::language", "src/query.rs", project_root);
2403
2404        assert_eq!(resolved, Some("src/models/language.rs".to_string()));
2405    }
2406}