mir-analyzer 0.80.0

//! Delta-maintained inverted inheritance index: resolved parent FQCN →
//! direct children, plus per-class declaration sites.
//!
//! The scan-based `class_subtype_files` query answered "who extends X" by
//! walking every class-like in the workspace and materializing each one's
//! ancestor chain — memoized per FQCN but invalidated wholesale whenever the
//! workspace class index changed, so under active editing every
//! goto-implementation re-paid an O(all classes) scan. This index is the
//! resolved inverse maintained incrementally: when a file's definitions are
//! (re)committed, its classes' old edges are removed and the new ones added,
//! so a query is a reverse-edge BFS in O(matching subtree) regardless of
//! edits elsewhere.
//!
//! Parent names are stored as resolved FQCNs (the collector applies
//! namespace + `use` aliases at collection time), lowercased for PHP's
//! case-insensitive class-name semantics.

use std::sync::Arc;

use rustc_hash::{FxHashMap, FxHashSet};

use mir_types::Location;

/// What kind of class-like declared the subtype (mirrors the four def
/// structs; there is no shared kind tag on them).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ClassLikeKind {
    Class,
    Interface,
    Trait,
    Enum,
}

/// One class-like declaration as recorded in the index.
#[derive(Debug, Clone, PartialEq)]
pub struct SubtypeEntry {
    /// Display-form FQCN (as collected, no leading `\`).
    pub fqcn: Arc<str>,
    pub kind: ClassLikeKind,
    pub is_abstract: bool,
    /// Direct parent edges, lowercased resolved FQCNs, extends/implements
    /// and trait uses alike.
    pub parents: Box<[ParentEdge]>,
    /// Declaration site (line 1-based, cols 0-based code points), when known.
    pub location: Option<Location>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ParentRelation {
    Super,
    TraitUse,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ParentEdge {
    pub fqcn: Arc<str>,
    pub relation: ParentRelation,
}

/// A resolved subtype hit returned by queries.
#[derive(Debug, Clone)]
pub struct SubtypeSite {
    pub fqcn: Arc<str>,
    pub kind: ClassLikeKind,
    pub is_abstract: bool,
    pub file: Arc<str>,
    pub location: Option<Location>,
}

/// Normalize an FQCN for use as an edge key.
pub fn edge_key(fqcn: &str) -> Arc<str> {
    Arc::from(fqcn.trim_start_matches('\\').to_ascii_lowercase())
}

/// The unqualified (short) name of an FQCN.
pub fn short_name_of(fqcn: &str) -> &str {
    fqcn.rsplit('\\').next().unwrap_or(fqcn)
}

/// Build the index entries for one file's collected definitions. Parent and
/// interface names in the slice are already resolved FQCNs (the collector
/// applies namespace + `use` aliases), so this is pure reshaping.
pub fn entries_from_slice(slice: &mir_codebase::definitions::StubSlice) -> Vec<SubtypeEntry> {
    let mut out: Vec<SubtypeEntry> =
        Vec::with_capacity(slice.classes.len() + slice.interfaces.len() + slice.enums.len());
    for c in &slice.classes {
        let mut parents: Vec<ParentEdge> =
            Vec::with_capacity(c.parent.iter().count() + c.interfaces.len() + c.traits.len());
        parents.extend(
            c.parent
                .iter()
                .chain(c.interfaces.iter())
                .map(|p| ParentEdge {
                    fqcn: edge_key(p),
                    relation: ParentRelation::Super,
                }),
        );
        parents.extend(c.traits.iter().map(|p| ParentEdge {
            fqcn: edge_key(p),
            relation: ParentRelation::TraitUse,
        }));
        out.push(SubtypeEntry {
            fqcn: c.fqcn.clone(),
            kind: ClassLikeKind::Class,
            is_abstract: c.is_abstract,
            parents: parents.into_boxed_slice(),
            location: c.location.clone(),
        });
    }
    for i in &slice.interfaces {
        out.push(SubtypeEntry {
            fqcn: i.fqcn.clone(),
            kind: ClassLikeKind::Interface,
            is_abstract: false,
            parents: i
                .extends
                .iter()
                .map(|p| ParentEdge {
                    fqcn: edge_key(p),
                    relation: ParentRelation::Super,
                })
                .collect(),
            location: i.location.clone(),
        });
    }
    for t in &slice.traits {
        out.push(SubtypeEntry {
            fqcn: t.fqcn.clone(),
            kind: ClassLikeKind::Trait,
            is_abstract: false,
            parents: t
                .traits
                .iter()
                .map(|p| ParentEdge {
                    fqcn: edge_key(p),
                    relation: ParentRelation::TraitUse,
                })
                .collect(),
            location: t.location.clone(),
        });
    }
    for e in &slice.enums {
        let mut parents: Vec<ParentEdge> = Vec::with_capacity(e.interfaces.len() + e.traits.len());
        parents.extend(e.interfaces.iter().map(|p| ParentEdge {
            fqcn: edge_key(p),
            relation: ParentRelation::Super,
        }));
        parents.extend(e.traits.iter().map(|p| ParentEdge {
            fqcn: edge_key(p),
            relation: ParentRelation::TraitUse,
        }));
        out.push(SubtypeEntry {
            fqcn: e.fqcn.clone(),
            kind: ClassLikeKind::Enum,
            is_abstract: false,
            parents: parents.into_boxed_slice(),
            location: e.location.clone(),
        });
    }
    out
}

/// Declaring entries for one FQCN: `(file, entry)` pairs. More than one file
/// can declare the same FQCN (duplicated symbol); keep all, keyed by file.
type EntryId = u32;
type KeyId = u32;
type DeclSites = Vec<EntryId>;

#[derive(Debug)]
struct StoredSubtypeEntry {
    file_path: Arc<str>,
    child_key: KeyId,
    fqcn: Arc<str>,
    kind: ClassLikeKind,
    is_abstract: bool,
    parents: Box<[StoredParentEdge]>,
    location: Option<Location>,
}

#[derive(Debug, Clone, Copy)]
struct StoredParentEdge {
    key: KeyId,
    relation: ParentRelation,
}

#[derive(Default, Debug)]
pub struct SubtypeIndex {
    /// parent (lowercased FQCN) → children (lowercased FQCN). Edge origin
    /// (extends/implements vs trait use) lives on the child's entry.
    children: FxHashMap<KeyId, FxHashSet<KeyId>>,
    /// Canonical declaration payloads. Secondary indexes store only ids into
    /// this arena so the same declaration body is not retained twice.
    entries: Vec<Option<StoredSubtypeEntry>>,
    free_entry_ids: Vec<EntryId>,
    /// file → class-likes it declared at last commit.
    by_file: FxHashMap<crate::db::FileNo, Vec<EntryId>>,
    /// class (lowercased FQCN) → declaring entries.
    decls: FxHashMap<KeyId, DeclSites>,
    /// Interned lowercased FQCN keys used by the graph. Public payloads keep
    /// display-form names, but hot subtype traversals compare and hash ids.
    key_by_name: FxHashMap<Arc<str>, KeyId>,
    key_names: Vec<Option<Arc<str>>>,
    free_key_ids: Vec<KeyId>,
    key_refcounts: Vec<u32>,
}

impl SubtypeIndex {
    fn intern_edge_key(&mut self, fqcn: &str) -> KeyId {
        let key = edge_key(fqcn);
        if let Some(id) = self.key_by_name.get(key.as_ref()) {
            return *id;
        }
        let id = if let Some(id) = self.free_key_ids.pop() {
            self.key_names[id as usize] = Some(key.clone());
            self.key_refcounts[id as usize] = 0;
            id
        } else {
            let id: KeyId = self
                .key_names
                .len()
                .try_into()
                .expect("subtype index key arena exhausted");
            self.key_names.push(Some(key.clone()));
            self.key_refcounts.push(0);
            id
        };
        self.key_by_name.insert(key.clone(), id);
        id
    }

    fn lookup_edge_key(&self, fqcn: &str) -> Option<KeyId> {
        let key = edge_key(fqcn);
        self.key_by_name.get(key.as_ref()).copied()
    }

    fn key_name(&self, id: KeyId) -> &str {
        self.key_names[id as usize]
            .as_ref()
            .expect("subtype index key id must be live")
            .as_ref()
    }

    fn retain_key(&mut self, id: KeyId) {
        let slot = &mut self.key_refcounts[id as usize];
        *slot = slot
            .checked_add(1)
            .expect("subtype index key refcount overflow");
    }

    fn release_key(&mut self, id: KeyId) {
        let slot = &mut self.key_refcounts[id as usize];
        *slot = slot
            .checked_sub(1)
            .expect("subtype index key refcount underflow");
        if *slot != 0 {
            return;
        }
        let key = self.key_names[id as usize]
            .take()
            .expect("subtype index key id must be live");
        self.key_by_name.remove(key.as_ref());
        self.free_key_ids.push(id);
    }

    fn alloc_entry(&mut self, file_path: Arc<str>, entry: SubtypeEntry) -> EntryId {
        let child_key = edge_key(&entry.fqcn);
        let child_key = self.intern_edge_key(&child_key);
        let parents: Box<[StoredParentEdge]> = entry
            .parents
            .iter()
            .map(|edge| StoredParentEdge {
                key: self.intern_edge_key(edge.fqcn.as_ref()),
                relation: edge.relation,
            })
            .collect();
        let stored = StoredSubtypeEntry {
            file_path,
            child_key,
            fqcn: entry.fqcn,
            kind: entry.kind,
            is_abstract: entry.is_abstract,
            parents,
            location: entry.location,
        };
        self.retain_key(child_key);
        for parent in &stored.parents {
            self.retain_key(parent.key);
        }
        if let Some(id) = self.free_entry_ids.pop() {
            self.entries[id as usize] = Some(stored);
            id
        } else {
            let id = self.entries.len() as EntryId;
            self.entries.push(Some(stored));
            id
        }
    }

    fn entry(&self, id: EntryId) -> &StoredSubtypeEntry {
        self.entries[id as usize]
            .as_ref()
            .expect("subtype index entry id must be live")
    }

    fn stored_entry_eq(&self, stored: &StoredSubtypeEntry, next: &SubtypeEntry) -> bool {
        stored.fqcn == next.fqcn
            && stored.kind == next.kind
            && stored.is_abstract == next.is_abstract
            && stored.location == next.location
            && stored.parents.len() == next.parents.len()
            && stored
                .parents
                .iter()
                .zip(next.parents.iter())
                .all(|(a, b)| self.key_name(a.key) == b.fqcn.as_ref() && a.relation == b.relation)
    }

    /// Replace `file`'s class-like declarations wholesale. Returns whether
    /// the index changed — a recommit of identical entries is a no-op, so
    /// callers can key epoch bumps on real edge changes only.
    pub fn set_file_classes(
        &mut self,
        file: crate::db::FileNo,
        file_path: Arc<str>,
        entries: Vec<SubtypeEntry>,
    ) -> bool {
        match self.by_file.get(&file) {
            Some(old)
                if old.len() == entries.len()
                    && old
                        .iter()
                        .zip(&entries)
                        .all(|(id, next)| self.stored_entry_eq(self.entry(*id), next)) =>
            {
                return false;
            }
            None if entries.is_empty() => return false,
            _ => {}
        }
        self.clear_file(file);
        if entries.is_empty() {
            return true;
        }
        let mut stored: Vec<EntryId> = Vec::with_capacity(entries.len());
        for entry in entries {
            let id = self.alloc_entry(file_path.clone(), entry);
            let (child_key, parents): (KeyId, Vec<KeyId>) = {
                let stored_entry = self.entry(id);
                (
                    stored_entry.child_key,
                    stored_entry.parents.iter().map(|edge| edge.key).collect(),
                )
            };
            for parent in &parents {
                self.children.entry(*parent).or_default().insert(child_key);
            }
            self.decls.entry(child_key).or_default().push(id);
            stored.push(id);
        }
        self.by_file.insert(file, stored);
        true
    }

    /// Remove every declaration recorded for `file`. Returns whether the
    /// index held (and dropped) any entry for it.
    pub fn clear_file(&mut self, file: crate::db::FileNo) -> bool {
        let Some(old) = self.by_file.remove(&file) else {
            return false;
        };
        for id in old {
            let (child_key, parents) = {
                let stored = self.entry(id);
                (stored.child_key, stored.parents.to_vec())
            };
            // Drop the child edge only when no other file still declares a
            // class-like with the same FQCN and the same parent.
            if let Some(sites) = self.decls.get_mut(&child_key) {
                sites.retain(|site_id| *site_id != id);
                if sites.is_empty() {
                    self.decls.remove(&child_key);
                }
            }
            let still_declared: Vec<EntryId> =
                self.decls.get(&child_key).cloned().unwrap_or_default();
            for parent in &parents {
                let survives = still_declared
                    .iter()
                    .map(|site_id| self.entry(*site_id))
                    .any(|entry| entry.parents.iter().any(|edge| edge.key == parent.key));
                if !survives {
                    if let Some(set) = self.children.get_mut(&parent.key) {
                        set.remove(&child_key);
                        if set.is_empty() {
                            self.children.remove(&parent.key);
                        }
                    }
                }
            }
            self.entries[id as usize] = None;
            self.free_entry_ids.push(id);
            self.release_key(child_key);
            for parent in &parents {
                self.release_key(parent.key);
            }
        }
        true
    }

    /// Transitive subtypes of `fqcn` (excluding `fqcn` itself), BFS over the
    /// reverse edges. `include_trait_users` controls whether an edge that
    /// exists only via `use Trait;` counts as a subtype relation.
    pub fn subtypes_of(&self, fqcn: &str, include_trait_users: bool) -> Vec<SubtypeSite> {
        let Some(root) = self.lookup_edge_key(fqcn) else {
            return Vec::new();
        };
        self.subtypes_of_key(root, include_trait_users)
    }

    fn subtypes_of_key(&self, root: KeyId, include_trait_users: bool) -> Vec<SubtypeSite> {
        let mut visited: FxHashSet<KeyId> = FxHashSet::default();
        visited.insert(root);
        let mut queue: Vec<KeyId> = vec![root];
        let mut out: Vec<SubtypeSite> = Vec::new();
        while let Some(parent) = queue.pop() {
            let Some(children) = self.children.get(&parent) else {
                continue;
            };
            for child in children {
                if visited.contains(child) {
                    continue;
                }
                let Some(sites) = self.decls.get(child) else {
                    // Edge to a class we have no declaration for (declared in
                    // an uncommitted file) — nothing to report or recurse into.
                    continue;
                };
                // The edge qualifies when any declaring site reaches `parent`
                // through extends/implements — or trait use when requested.
                // A child reached only through a non-qualifying edge is not a
                // subtype and must not be descended into from here; it stays
                // unvisited so a qualifying edge elsewhere can still reach it.
                let mut qualifies = false;
                for id in sites {
                    let stored = self.entry(*id);
                    let reaches_parent = stored.parents.iter().any(|edge| {
                        edge.key == parent
                            && (edge.relation == ParentRelation::Super || include_trait_users)
                    });
                    if !reaches_parent {
                        continue;
                    }
                    qualifies = true;
                    out.push(SubtypeSite {
                        fqcn: stored.fqcn.clone(),
                        kind: stored.kind,
                        is_abstract: stored.is_abstract,
                        file: stored.file_path.clone(),
                        location: stored.location.clone(),
                    });
                }
                if qualifies {
                    visited.insert(*child);
                    queue.push(*child);
                }
            }
        }
        out.sort_by(|a, b| {
            a.file.cmp(&b.file).then_with(|| {
                let la = a.location.as_ref().map(|l| l.line).unwrap_or(0);
                let lb = b.location.as_ref().map(|l| l.line).unwrap_or(0);
                la.cmp(&lb)
            })
        });
        out.dedup_by(|a, b| a.fqcn == b.fqcn && a.file == b.file);
        out
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn entry(fqcn: &str, supers: &[&str], traits: &[&str]) -> SubtypeEntry {
        let mut parents: Vec<ParentEdge> = Vec::with_capacity(supers.len() + traits.len());
        parents.extend(supers.iter().map(|s| ParentEdge {
            fqcn: edge_key(s),
            relation: ParentRelation::Super,
        }));
        parents.extend(traits.iter().map(|s| ParentEdge {
            fqcn: edge_key(s),
            relation: ParentRelation::TraitUse,
        }));
        SubtypeEntry {
            fqcn: Arc::from(fqcn),
            kind: ClassLikeKind::Class,
            is_abstract: false,
            parents: parents.into_boxed_slice(),
            location: None,
        }
    }

    #[test]
    fn direct_and_transitive_subtypes() {
        let mut idx = SubtypeIndex::default();
        let a: crate::db::FileNo = 0;
        let b: crate::db::FileNo = 1;
        idx.set_file_classes(
            a,
            Arc::from("a.php"),
            vec![entry("App\\Child", &["App\\Base"], &[])],
        );
        idx.set_file_classes(
            b,
            Arc::from("b.php"),
            vec![entry("App\\Grand", &["App\\Child"], &[])],
        );
        let subs = idx.subtypes_of("App\\Base", false);
        assert_eq!(subs.len(), 2);
        assert!(subs.iter().any(|s| s.fqcn.as_ref() == "App\\Child"));
        assert!(subs.iter().any(|s| s.fqcn.as_ref() == "App\\Grand"));
    }
    #[test]
    fn recommit_replaces_edges() {
        let mut idx = SubtypeIndex::default();
        let a: crate::db::FileNo = 0;
        idx.set_file_classes(
            a,
            Arc::from("a.php"),
            vec![entry("App\\Child", &["App\\Base"], &[])],
        );
        assert_eq!(idx.subtypes_of("App\\Base", false).len(), 1);
        idx.set_file_classes(
            a,
            Arc::from("a.php"),
            vec![entry("App\\Child", &["App\\Other"], &[])],
        );
        assert!(idx.subtypes_of("App\\Base", false).is_empty());
        assert_eq!(idx.subtypes_of("App\\Other", false).len(), 1);
    }
    #[test]
    fn trait_users_only_when_requested() {
        let mut idx = SubtypeIndex::default();
        let a: crate::db::FileNo = 0;
        idx.set_file_classes(
            a,
            Arc::from("a.php"),
            vec![entry("App\\User", &[], &["App\\Helper"])],
        );
        assert!(idx.subtypes_of("App\\Helper", false).is_empty());
        assert_eq!(idx.subtypes_of("App\\Helper", true).len(), 1);
    }
    #[test]
    fn clear_file_preserves_shared_parent_relation_kind() {
        let mut idx = SubtypeIndex::default();
        let a: crate::db::FileNo = 0;
        let b: crate::db::FileNo = 1;
        idx.set_file_classes(
            a,
            Arc::from("a.php"),
            vec![entry("App\\User", &[], &["App\\Helper"])],
        );
        idx.set_file_classes(
            b,
            Arc::from("b.php"),
            vec![entry("App\\User", &["App\\Helper"], &[])],
        );

        idx.clear_file(a);
        assert!(idx.subtypes_of("App\\Helper", false).len() == 1);
        assert!(idx.subtypes_of("App\\Helper", true).len() == 1);

        idx.clear_file(b);
        assert!(idx.subtypes_of("App\\Helper", false).is_empty());
        assert!(idx.subtypes_of("App\\Helper", true).is_empty());
    }

    #[test]
    fn case_insensitive_parent_match() {
        let mut idx = SubtypeIndex::default();
        let a: crate::db::FileNo = 0;
        idx.set_file_classes(
            a,
            Arc::from("a.php"),
            vec![entry("App\\Child", &["App\\BASE"], &[])],
        );
        assert_eq!(idx.subtypes_of("app\\base", false).len(), 1);
        assert_eq!(idx.subtypes_of("\\App\\Base", false).len(), 1);
    }
    #[test]
    fn diamond_hierarchy_visits_once() {
        let mut idx = SubtypeIndex::default();
        let a: crate::db::FileNo = 0;
        idx.set_file_classes(
            a,
            Arc::from("a.php"),
            vec![
                entry("I\\Left", &["I\\Top"], &[]),
                entry("I\\Right", &["I\\Top"], &[]),
                entry("I\\Bottom", &["I\\Left", "I\\Right"], &[]),
            ],
        );
        let subs = idx.subtypes_of("I\\Top", false);
        assert_eq!(subs.len(), 3);
    }
    #[test]
    fn clear_file_reclaims_unused_key_ids() {
        let mut idx = SubtypeIndex::default();
        let a: crate::db::FileNo = 0;

        idx.set_file_classes(
            a,
            Arc::from("a.php"),
            vec![entry("App\\Child", &["App\\Base"], &[])],
        );
        assert_eq!(idx.key_by_name.len(), 2);
        assert_eq!(idx.key_names.len(), 2);

        idx.clear_file(a);
        assert!(idx.key_by_name.is_empty());
        assert!(idx.key_names.iter().all(Option::is_none));
        assert_eq!(idx.free_key_ids.len(), 2);

        idx.set_file_classes(
            a,
            Arc::from("a.php"),
            vec![entry("App\\OtherChild", &["App\\OtherBase"], &[])],
        );
        assert_eq!(idx.key_by_name.len(), 2);
        assert_eq!(idx.key_names.len(), 2);
        assert_eq!(idx.free_key_ids.len(), 0);
        assert!(idx.lookup_edge_key("App\\OtherChild").is_some());
        assert!(idx.lookup_edge_key("App\\OtherBase").is_some());
    }
}