core_api/repograph/

why.rs

//! `why` — what links two things, with the evidence.
//!
//! A derived edge is a claim, and a claim an assistant is going to act on
//! should come with what it was derived from. So every link this reports
//! carries the rule that wrote it, the score it was written with, and the lines
//! of the repository that make it true: the commits two files share, the line
//! an import sits on, the line a call is made from, the file an author knows
//! both through, the heading a document mentions something under.
//!
//! When no rule links the two at all, the commits they share are still an
//! answer — the co-change rule only writes an edge above a similarity floor,
//! and a pair that changes together often but also changes apart falls under
//! it. Failing that the answer is the shortest walk between them — see
//! [`shortest_path`](crate::repograph::shortest_path) — and when there is not
//! even one of those, `why` says so rather than implying a connection nobody
//! can name.

use crate::db::GraphDb;
use crate::repograph::facts::{
    commit_fact, evidence_line, evidence_lines, list_prop, neighbors, str_prop, CommitFact,
};
use crate::repograph::impact::MIN_SHARED_COMMITS;
use crate::repograph::owners::SHA_LEN;
use crate::repograph::path::{shortest_path, MAX_HOPS, PATH_EDGES};
use crate::repograph::render::{sanitize, ymd};
use crate::Direction;
use core_storage::fs::Fs;
use serde::Serialize;
use std::collections::BTreeSet;

/// Lines of evidence kept per link. Three commits say "these two move
/// together"; thirty say it no better and crowd out the next link.
const MAX_EVIDENCE: usize = 3;

/// How `a` and `b` are linked, if they are.
#[derive(Debug, Clone, PartialEq, Serialize)]
pub struct WhyReport {
    pub a: String,
    pub b: String,
    /// Every rule-written edge between them, in either direction.
    pub links: Vec<WhyLink>,
    /// `(edge type, node reached)` hops, filled only when no rule links them
    /// directly, they share too few commits to say anything, and a walk of at
    /// most [`MAX_HOPS`] edges connects them.
    pub path: Vec<(String, String)>,
    /// Commits both were touched by, filled only when no `CO_CHANGED` edge
    /// already carries them.
    ///
    /// The `co_changed` rule writes an edge on jaccard similarity, so two files
    /// that change together often and *also* change apart carry no edge at all
    /// and would otherwise be reported as unrelated — or as related only by
    /// whatever else happens to link them. See
    /// [`MIN_SHARED_COMMITS`](crate::repograph::MIN_SHARED_COMMITS).
    pub shared: Option<SharedCommits>,
    /// Whichever of `a` and `b` the store has never heard of.
    pub unknown: Vec<String>,
}

/// How often two files were touched by the same commit, and by which commits.
#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
pub struct SharedCommits {
    /// Commits that touched both.
    pub count: usize,
    /// The newest few of them, as a digest quotes a commit.
    pub evidence: Vec<String>,
}

/// One rule-written edge, and what makes it true.
#[derive(Debug, Clone, PartialEq, Serialize)]
pub struct WhyLink {
    /// The rule that wrote the edge.
    pub rule: String,
    pub edge_type: String,
    /// `a→b` or `b→a`, in terms of the keys the caller asked about.
    pub direction: String,
    /// The score the rule matched at. `None` for a rule that records none.
    pub score: Option<f64>,
    /// For a via-hop rule, the edge type the rule hopped over to find its
    /// candidates. The evidence names the node it hopped through.
    pub via: Option<String>,
    /// The repository facts behind the edge, strongest or newest first.
    pub evidence: Vec<String>,
}

/// Why `a` and `b` are linked.
///
/// Deterministic: links come back in the engine's `(rule, edge type)` order,
/// evidence is sorted before it is cut, and the path — when there is one — is
/// the same shortest walk every time.
#[must_use]
pub fn why<F: Fs>(db: &GraphDb<F>, a: &str, b: &str) -> WhyReport {
    let mut report = WhyReport {
        a: sanitize(a),
        b: sanitize(b),
        links: Vec::new(),
        path: Vec::new(),
        shared: None,
        unknown: Vec::new(),
    };
    for key in [a, b] {
        if !db.has_node(key) {
            report.unknown.push(sanitize(key));
        }
    }
    report.unknown.sort();
    report.unknown.dedup();
    if !report.unknown.is_empty() {
        return report;
    }

    for e in db.explain(a, b).unwrap_or_default() {
        let forward = e.src_key == a;
        report.links.push(WhyLink {
            evidence: evidence(db, &e.edge_type, &e.src_key, &e.dst_key),
            rule: sanitize(&e.rule),
            edge_type: sanitize(&e.edge_type),
            direction: if forward { "a→b" } else { "b→a" }.to_string(),
            score: e.weight,
            via: e.via_edge.as_deref().map(sanitize),
        });
    }
    // The engine returns provenance in its own stable order; sorting on the
    // fields themselves means the answer depends on what the links *are*
    // rather than on the order two stores happened to intern their ids in.
    report.links.sort_by(|x, y| {
        x.direction
            .cmp(&y.direction)
            .then(x.edge_type.cmp(&y.edge_type))
            .then(x.rule.cmp(&y.rule))
            .then(
                y.score
                    .partial_cmp(&x.score)
                    .unwrap_or(std::cmp::Ordering::Equal),
            )
            .then(x.evidence.cmp(&y.evidence))
    });
    // No `CO_CHANGED` edge is not the same as no co-change: the rule only
    // writes one above a similarity floor, and a pair that changes together
    // often but also changes apart falls under it. That the two import each
    // other says nothing about how often they move together, so the commits are
    // reported alongside whatever links there are — and, when there are none,
    // instead of a three-hop walk that says less.
    if !report.links.iter().any(|l| l.edge_type == "CO_CHANGED") {
        report.shared = shared_commit_count(db, a, b);
    }
    if report.links.is_empty() && report.shared.is_none() {
        report.path = shortest_path(db, a, b, &PATH_EDGES, MAX_HOPS);
    }
    report
}

/// The commits `a` and `b` share, when there are at least
/// [`MIN_SHARED_COMMITS`] of them. `None` for anything else — a pair that
/// shares one commit shares a coincidence, and a node with no `commits` list
/// (a symbol, an author) shares nothing.
fn shared_commit_count<F: Fs>(db: &GraphDb<F>, a: &str, b: &str) -> Option<SharedCommits> {
    let theirs: BTreeSet<String> = list_prop(db, b, "commits").into_iter().collect();
    let count = list_prop(db, a, "commits")
        .into_iter()
        .collect::<BTreeSet<String>>()
        .intersection(&theirs)
        .count();
    (count >= MIN_SHARED_COMMITS).then(|| SharedCommits {
        count,
        evidence: shared_commits(db, a, b),
    })
}

/// The repository facts behind one edge, in the form its kind is read in.
///
/// An edge type nothing is recorded for — an auto-FK edge such as `DEFINES`,
/// whose evidence is the prop it was derived from and is already in the key —
/// gets none, and the digest prints the link alone.
fn evidence<F: Fs>(db: &GraphDb<F>, edge_type: &str, src: &str, dst: &str) -> Vec<String> {
    match edge_type {
        "CO_CHANGED" => shared_commits(db, src, dst),
        "IMPORTS" => match evidence_line(&list_prop(db, src, "import_lines"), dst) {
            Some(line) => vec![sanitize(&format!("{src} line {line}: import {dst}"))],
            None => vec![sanitize(&format!("{src} imports {dst}"))],
        },
        // Every site, not the first: one edge stands for however many times the
        // call is written, and the lines are what a change has to visit.
        "CALLS" => match evidence_lines(&list_prop(db, src, "call_lines"), dst) {
            lines if lines.is_empty() => vec![sanitize(&format!("{src} calls {dst}"))],
            lines => {
                let shown: Vec<String> = lines.iter().map(u32::to_string).collect();
                vec![sanitize(&format!(
                    "{src} calls {dst} at {} {}",
                    if lines.len() == 1 { "line" } else { "lines" },
                    shown.join(", ")
                ))]
            }
        },
        "KNOWS" => via_files(db, src, dst),
        "MENTIONS" => vec![mention(db, src, dst)],
        _ => Vec::new(),
    }
}

/// The commits both files were touched by, newest first.
fn shared_commits<F: Fs>(db: &GraphDb<F>, a: &str, b: &str) -> Vec<String> {
    let theirs: BTreeSet<String> = list_prop(db, b, "commits").into_iter().collect();
    let mut shared: Vec<CommitFact> = list_prop(db, a, "commits")
        .into_iter()
        .filter(|sha| theirs.contains(sha))
        .filter_map(|sha| commit_fact(db, &sha))
        .collect();
    shared.sort_by(|x, y| y.ts.cmp(&x.ts).then(x.sha.cmp(&y.sha)));
    shared.dedup_by(|x, y| x.sha == y.sha);
    shared
        .into_iter()
        .take(MAX_EVIDENCE)
        .map(|c| {
            let short: String = c.sha.chars().take(SHA_LEN).collect();
            sanitize(&format!("{short} {} {}", ymd(c.ts), c.subject))
        })
        .collect()
}

/// The files an author knows `file` through: the ones they own that share
/// commits with it, which is what the `knows` rule hopped over to find them.
fn via_files<F: Fs>(db: &GraphDb<F>, author: &str, file: &str) -> Vec<String> {
    let theirs: BTreeSet<String> = list_prop(db, file, "commits").into_iter().collect();
    let mut scored: Vec<(usize, String)> = neighbors(db, author, "TOP_AUTHOR", Direction::In)
        .into_iter()
        .filter(|owned| owned != file)
        .map(|owned| {
            let shared = list_prop(db, &owned, "commits")
                .into_iter()
                .filter(|sha| theirs.contains(sha))
                .count();
            (shared, owned)
        })
        .filter(|(shared, _)| *shared > 0)
        .collect();
    // Most shared commits first, ties on the key: the same order the digest
    // would rank any other association in.
    scored.sort_by(|x, y| y.0.cmp(&x.0).then(x.1.cmp(&y.1)));
    scored
        .into_iter()
        .take(MAX_EVIDENCE)
        .map(|(shared, owned)| {
            sanitize(&format!(
                "via {owned} ({shared} shared commit{})",
                if shared == 1 { "" } else { "s" }
            ))
        })
        .collect()
}

/// Where in a document a file is mentioned: the heading it sits under.
///
/// The mention itself carries no line, so the line is found in the document's
/// stored `body` — the first one naming the file — and the heading is the
/// nearest one above it. A document whose body was not stored still has its
/// headings, and the first of those is what it is about.
fn mention<F: Fs>(db: &GraphDb<F>, doc: &str, file: &str) -> String {
    let headings = list_prop(db, doc, "headings");
    let nearest = str_prop(db, doc, "body").and_then(|body| {
        let lines: Vec<&str> = body.lines().collect();
        let at = lines.iter().position(|l| l.contains(file))?;
        lines[..=at]
            .iter()
            .rev()
            .find_map(|l| heading_text(l).map(str::to_string))
    });
    match nearest.or_else(|| headings.first().cloned()) {
        Some(heading) => sanitize(&format!("{doc} mentions {file} under \"{heading}\"")),
        None => sanitize(&format!("{doc} mentions {file}")),
    }
}

/// The text of a Markdown ATX heading, if the line is one.
fn heading_text(line: &str) -> Option<&str> {
    let trimmed = line.trim_start();
    let hashes = trimmed.chars().take_while(|c| *c == '#').count();
    if hashes == 0 || hashes > 6 {
        return None;
    }
    let rest = trimmed.get(hashes..)?;
    if !rest.starts_with(char::is_whitespace) {
        return None;
    }
    let title = rest.trim().trim_end_matches('#').trim();
    (!title.is_empty()).then_some(title)
}

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

    #[test]
    fn a_heading_is_hashes_a_space_and_a_title() {
        assert_eq!(heading_text("## Rules"), Some("Rules"));
        assert_eq!(heading_text("  # Top  "), Some("Top"));
        assert_eq!(heading_text("### Closed ###"), Some("Closed"));
        assert_eq!(heading_text("#no-space"), None);
        assert_eq!(heading_text("####### too deep"), None);
        assert_eq!(heading_text("plain text"), None);
        assert_eq!(heading_text("#"), None);
    }
}