Skip to main content

knowledge/
relations.rs

1//! Relations across files, read on demand for a task: which code reads which configuration key, which handler
2//! serves which route, which code touches which table, which test exercises which file.
3//!
4//! The schema is small and closed ([`Kind`]), versioned by [`RELATIONS_VERSION`], and grows only when a recorded
5//! failure needs a distinction (a just-in-time ontology: built when a task asks, kept with its evidence, reused).
6//! Each relation passes three rungs, cheapest first:
7//!
8//! 1. The proposer ([`propose`]): plain code over one blob's text. A pattern that cannot mean anything else
9//!    (`std::env::var("HOME")`, `@app.get("/users")`, SQL in a `.sql` file) is settled here (`certain`); a
10//!    pattern that only looks like one (`config.get("x.y")`, a lowercase `from users` in a string) is proposed.
11//! 2. Pruning ([`prune`]): only the kinds the task asked for; a test import must name a file of the same tree;
12//!    duplicates and relations the judge refused are dropped. No model is asked about what plain code can drop.
13//! 3. The judge (`judge.decide`, asked by the REPL client): one yes/no per proposed relation, over its lines.
14//!
15//! What the proposer reads depends on the blob alone, so proposals and verdicts are cached by blob and
16//! [`RELATIONS_VERSION`]: the next task over the same files asks nothing again.
17
18use std::collections::{BTreeMap, BTreeSet};
19use std::sync::LazyLock;
20
21use regex::Regex;
22
23use crate::extract::vendored;
24
25/// The version of the proposer's rules and of the schema of kinds. Bump it whenever what is proposed changes: every
26/// blob is then read again, and its earlier proposals and verdicts are dropped.
27pub const RELATIONS_VERSION: i64 = 1;
28
29/// Proposals kept per blob, in order: a bound on generated files.
30pub const MAX_PER_BLOB: usize = 300;
31
32/// Lines of context around a proposal, each way, and the characters of context and quote kept.
33const CONTEXT_LINES: usize = 3;
34const CONTEXT_CHARS: usize = 800;
35const QUOTE_CHARS: usize = 200;
36
37#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
38pub enum Kind {
39    /// Code → a configuration key (an environment variable, a setting).
40    ReadsConfig,
41    /// A handler → the route it serves (`GET /users`).
42    ServesRoute,
43    /// Code → a database table it reads, writes or defines.
44    TouchesTable,
45    /// A test file → a file of the repository it imports.
46    Tests,
47}
48
49impl Kind {
50    pub const ALL: [Kind; 4] = [Kind::ReadsConfig, Kind::ServesRoute, Kind::TouchesTable, Kind::Tests];
51
52    pub fn name(self) -> &'static str {
53        match self {
54            Kind::ReadsConfig => "reads_config",
55            Kind::ServesRoute => "serves_route",
56            Kind::TouchesTable => "touches_table",
57            Kind::Tests => "tests",
58        }
59    }
60
61    pub fn parse(name: &str) -> Option<Kind> {
62        Kind::ALL.into_iter().find(|kind| kind.name() == name)
63    }
64
65    /// The relationship type of a graph mirror (Neo4j).
66    pub fn edge(self) -> &'static str {
67        match self {
68            Kind::ReadsConfig => "READS_CONFIG",
69            Kind::ServesRoute => "SERVES_ROUTE",
70            Kind::TouchesTable => "TOUCHES_TABLE",
71            Kind::Tests => "TESTS",
72        }
73    }
74
75    /// The node label of a relation's object in a graph mirror; the subject is always `Code`.
76    pub fn object_label(self) -> &'static str {
77        match self {
78            Kind::ReadsConfig => "ConfigKey",
79            Kind::ServesRoute => "Route",
80            Kind::TouchesTable => "Table",
81            Kind::Tests => "Code",
82        }
83    }
84
85    /// The yes/no question the judge is asked of a proposed relation, over its lines.
86    pub fn question(self, subject: &str, object: &str) -> String {
87        match self {
88            Kind::ReadsConfig => format!(
89                "Does `{subject}` read `{object}` as a configuration value here (an environment variable, a \
90                 setting or a config entry), not some other lookup that only looks like one?"
91            ),
92            Kind::ServesRoute => format!("Is `{subject}` the handler that serves the HTTP route `{object}` here?"),
93            Kind::TouchesTable => format!(
94                "Is `{object}` a database table that `{subject}` reads, writes or defines through the SQL here, \
95                 not a word in prose or a non-SQL string?"
96            ),
97            Kind::Tests => format!("Does the test file `{subject}` exercise code of `{object}`?"),
98        }
99    }
100}
101
102/// A relation the proposer read from one blob. It depends on the blob's text only: the file's path is joined in
103/// when it is read back ([`Relation`]).
104#[derive(Clone, Debug, PartialEq, Eq)]
105pub struct Proposed {
106    pub kind: Kind,
107    /// The definition it is made from (a function, method or class name); empty for the file itself.
108    pub subject: String,
109    /// What it relates to: the key, `METHOD /route`, the table, or (for a test) the module as imported.
110    pub object: String,
111    pub line: i64,
112    /// The line, trimmed.
113    pub quote: String,
114    /// The lines around it, for the judge.
115    pub context: String,
116    /// Settled by plain code: nothing else could mean this.
117    pub certain: bool,
118}
119
120/// A relation of one file at one revision, as the store keeps it.
121#[derive(Clone, Debug, PartialEq)]
122pub struct Relation {
123    pub id: i64,
124    pub kind: Kind,
125    /// `path::definition`, or the path for the file itself.
126    pub subject: String,
127    pub object: String,
128    pub path: String,
129    pub blob: String,
130    pub line: i64,
131    pub quote: String,
132    pub context: String,
133    /// `accepted`, `rejected`, `review` (the judge was not sure) or `proposed` (not judged yet).
134    pub status: String,
135    /// `code` (the proposer or pruning settled it) or the judge backend that answered.
136    pub checked_by: Option<String>,
137    pub rung: Option<String>,
138    pub model: Option<String>,
139    pub confidence: Option<f64>,
140}
141
142impl Relation {
143    /// Where it was read: `repo://<path>#L<line>` (the file at the blob of this revision).
144    pub fn evidence(&self) -> String {
145        format!("repo://{}#L{}", self.path, self.line)
146    }
147}
148
149/// Whether the proposer reads `path`: source and SQL outside vendored and built trees.
150pub fn scanned(path: &str) -> bool {
151    if vendored(path) {
152        return false;
153    }
154    let name = path.rsplit('/').next().unwrap_or(path);
155    let extension = name.rsplit_once('.').map_or("", |(_, extension)| extension);
156    matches!(
157        extension,
158        "rs" | "py" | "ts" | "tsx" | "mts" | "cts" | "js" | "jsx" | "mjs" | "cjs" | "sql"
159    )
160}
161
162#[derive(Clone, Copy, PartialEq, Eq)]
163enum Source {
164    Rust,
165    Python,
166    Script,
167    Sql,
168}
169
170fn source(path: &str) -> Source {
171    let extension = path.rsplit_once('.').map_or("", |(_, extension)| extension);
172    match extension {
173        "rs" => Source::Rust,
174        "py" => Source::Python,
175        "sql" => Source::Sql,
176        _ => Source::Script,
177    }
178}
179
180fn regex(pattern: &str) -> Regex {
181    Regex::new(pattern).expect("a valid built-in pattern")
182}
183
184/// A definition line: `fn`, `def`, `function`, `class`, a TypeScript method or arrow function.
185static DEFINITION: LazyLock<Regex> = LazyLock::new(|| {
186    regex(
187        r"^\s*(?:export\s+)?(?:default\s+)?(?:pub(?:\([^)]*\))?\s+)?(?:async\s+)?(?:unsafe\s+)?(?:const\s+)?(?:fn|def|function|class)\s+([A-Za-z_][A-Za-z0-9_]*)",
188    )
189});
190static ARROW: LazyLock<Regex> = LazyLock::new(|| {
191    regex(r"^\s*(?:export\s+)?(?:const|let)\s+([A-Za-z_$][\w$]*)\s*(?::[^=]+)?=\s*(?:async\s*)?(?:\(|function)")
192});
193static METHOD: LazyLock<Regex> = LazyLock::new(|| {
194    regex(
195        r"^\s+(?:(?:public|private|protected|static|async|override)\s+)*([A-Za-z_$][\w$]*)\s*\([^)]*\)\s*(?::\s*[^={]+)?\{\s*$",
196    )
197});
198const NOT_METHODS: [&str; 7] = ["if", "for", "while", "switch", "catch", "return", "function"];
199
200fn definition(line: &str) -> Option<String> {
201    if let Some(found) = DEFINITION.captures(line).or_else(|| ARROW.captures(line)) {
202        return Some(found[1].to_string());
203    }
204    let found = METHOD.captures(line)?;
205    (!NOT_METHODS.contains(&&found[1])).then(|| found[1].to_string())
206}
207
208fn comment(line: &str, from: Source) -> bool {
209    let line = line.trim_start();
210    line.starts_with("//")
211        || line.starts_with("/*")
212        || line.starts_with('*')
213        || (line.starts_with('#') && !line.starts_with("#[") && !line.starts_with("#!"))
214        || (from == Source::Sql && line.starts_with("--"))
215}
216
217static ENV_CERTAIN: LazyLock<Vec<Regex>> = LazyLock::new(|| {
218    [
219        r#"\benv::var(?:_os)?\(\s*"([A-Za-z_][A-Za-z0-9_]*)""#,
220        r#"\benv!\(\s*"([A-Za-z_][A-Za-z0-9_]*)""#,
221        r#"\bos\.environ(?:\.get)?\s*[\[(]\s*['"]([A-Za-z_][A-Za-z0-9_]*)['"]"#,
222        r#"\bos\.getenv\(\s*['"]([A-Za-z_][A-Za-z0-9_]*)['"]"#,
223        r#"\bprocess\.env\.([A-Za-z_][A-Za-z0-9_]*)"#,
224        r#"\bprocess\.env\[\s*['"]([A-Za-z_][A-Za-z0-9_]*)['"]"#,
225    ]
226    .iter()
227    .map(|pattern| regex(pattern))
228    .collect()
229});
230/// A lookup that may be configuration: a `var("NAME")` closure, a settings or config object's getter.
231static CONFIG_MAYBE: LazyLock<Vec<Regex>> = LazyLock::new(|| {
232    [
233        r#"\bvar\)?\(\s*"([A-Z][A-Z0-9_]{2,})""#,
234        r#"\b(?:settings|config|cfg|conf|options)\w*(?:\(\))?\.get(?:_\w+)?\(\s*['"]([A-Za-z][\w.-]*)['"]"#,
235    ]
236    .iter()
237    .map(|pattern| regex(pattern))
238    .collect()
239});
240
241static PY_ROUTE: LazyLock<Regex> = LazyLock::new(|| {
242    regex(r#"^\s*@(\w+)\.(get|post|put|patch|delete|head|options|route|api_route)\(\s*['"]([^'"]+)['"]"#)
243});
244static PY_METHODS: LazyLock<Regex> = LazyLock::new(|| regex(r#"methods\s*=\s*\[\s*['"](\w+)['"]"#));
245static NEST_ROUTE: LazyLock<Regex> =
246    LazyLock::new(|| regex(r#"^\s*@(Get|Post|Put|Patch|Delete|Head|Options|All)\(\s*(?:['"]([^'"]*)['"])?\s*\)"#));
247static EXPRESS_ROUTE: LazyLock<Regex> =
248    LazyLock::new(|| regex(r#"\b(\w+)\.(get|post|put|patch|delete|all)\(\s*['"](/[^'"]*)['"]\s*,(.*)$"#));
249static LAST_HANDLER: LazyLock<Regex> = LazyLock::new(|| regex(r"([A-Za-z_$][\w$.]*)\s*\)\s*;?\s*$"));
250static AXUM_ROUTE: LazyLock<Regex> = LazyLock::new(|| {
251    regex(r#"\.route\(\s*"([^"]+)"\s*,\s*(get|post|put|patch|delete|head|options|any)\(\s*([A-Za-z_][\w:]*)\s*\)"#)
252});
253static RUST_ROUTE: LazyLock<Regex> =
254    LazyLock::new(|| regex(r#"^\s*#\[(get|post|put|patch|delete|head|options)\(\s*"([^"]+)""#));
255static NEXT_HANDLER: LazyLock<Regex> = LazyLock::new(|| {
256    regex(
257        r"^\s*(?:pub(?:\([^)]*\))?\s+)?(?:(?:public|private|protected|static|async)\s+)*(?:fn\s+|def\s+)?([A-Za-z_$][\w$]*)\s*[(<]",
258    )
259});
260/// Receivers whose `get("/path", handler)` is a route.
261const ROUTERS: [&str; 6] = ["app", "router", "server", "api", "routes", "bp"];
262
263static SQL_TABLE: LazyLock<Vec<Regex>> = LazyLock::new(|| {
264    [
265        r#"(?i)\b(from|join)\s+[`"]?([A-Za-z_][\w]*(?:\.[A-Za-z_]\w*)?)"#,
266        r#"(?i)\b(insert\s+into)\s+[`"]?([A-Za-z_][\w]*(?:\.[A-Za-z_]\w*)?)"#,
267        r#"(?i)\b(update)\s+[`"]?([A-Za-z_][\w]*(?:\.[A-Za-z_]\w*)?)[`"]?\s+set\b"#,
268        r#"(?i)\b((?:create|alter|drop|truncate)\s+table)\s+(?:if\s+(?:not\s+)?exists\s+)?[`"]?([A-Za-z_][\w]*(?:\.[A-Za-z_]\w*)?)"#,
269    ]
270    .iter()
271    .map(|pattern| regex(pattern))
272    .collect()
273});
274static TABLENAME: LazyLock<Regex> = LazyLock::new(|| regex(r#"\b__tablename__\s*=\s*['"](\w+)['"]"#));
275/// A line of SQL by itself (a continuation of a multi-line SQL string).
276static SQL_LINE: LazyLock<Regex> = LazyLock::new(|| {
277    regex(
278        r"^(?:SELECT|FROM|JOIN|LEFT|RIGHT|INNER|OUTER|WHERE|INSERT|UPDATE|DELETE|CREATE|ALTER|DROP|VALUES|SET|RETURNING|ON|WITH|USING)\b",
279    )
280});
281/// Words after `from` or `join` that are not tables.
282const NOT_TABLES: [&str; 22] = [
283    "a",
284    "an",
285    "the",
286    "this",
287    "that",
288    "it",
289    "each",
290    "every",
291    "all",
292    "any",
293    "select",
294    "where",
295    "values",
296    "as",
297    "on",
298    "lateral",
299    "unnest",
300    "json_each",
301    "generate_series",
302    "dual",
303    "here",
304    "there",
305];
306
307static TEST_FILE: LazyLock<Regex> = LazyLock::new(|| {
308    regex(
309        r"(?m)#\[test\]|#\[tokio::test|^\s*(?:async\s+)?def test_|^\s*(?:describe|it|test)\(|^\s*import pytest|^\s*import unittest",
310    )
311});
312static RUST_USE: LazyLock<Regex> =
313    LazyLock::new(|| regex(r"^\s*(?:pub\s+)?use\s+((?:::)?[A-Za-z_]\w*(?:::[A-Za-z_]\w*)*)"));
314static PY_FROM: LazyLock<Regex> = LazyLock::new(|| regex(r"^\s*from\s+(\.*[\w.]*)\s+import\s+\(?([^#]+)"));
315static PY_IMPORT: LazyLock<Regex> = LazyLock::new(|| regex(r"^\s*import\s+([\w.]+)"));
316static SCRIPT_IMPORT: LazyLock<Regex> =
317    LazyLock::new(|| regex(r#"(?:\bfrom\s+|^\s*import\s+|\brequire\(\s*)['"]([^'"]+)['"]"#));
318
319fn clip(text: &str, chars: usize) -> String {
320    if text.chars().count() <= chars {
321        return text.to_string();
322    }
323    text.chars().take(chars).collect::<String>() + "..."
324}
325
326/// Everything the proposer reads in `text` (the file at `path`), in line order, at most [`MAX_PER_BLOB`].
327pub fn propose(path: &str, text: &str) -> Vec<Proposed> {
328    let from = source(path);
329    let lines: Vec<&str> = text.lines().collect();
330    let tests = from != Source::Sql && TEST_FILE.is_match(text);
331    let mut current = String::new();
332    let mut out = Vec::new();
333    for (index, line) in lines.iter().enumerate() {
334        if let Some(name) = definition(line) {
335            current = name;
336        }
337        if comment(line, from) {
338            continue;
339        }
340        let mut found: Vec<(Kind, String, String, bool)> = Vec::new();
341        reads_config(line, &current, &mut found);
342        serves_route(line, &lines[index + 1..], &mut found);
343        touches_table(line, from, &current, &mut found);
344        if tests {
345            imports(line, from, &mut found);
346        }
347        for (kind, subject, object, certain) in found {
348            let start = index.saturating_sub(CONTEXT_LINES);
349            let end = (index + CONTEXT_LINES + 1).min(lines.len());
350            out.push(Proposed {
351                kind,
352                subject,
353                object,
354                line: index as i64 + 1,
355                quote: clip(line.trim(), QUOTE_CHARS),
356                context: clip(&lines[start..end].join("\n"), CONTEXT_CHARS),
357                certain,
358            });
359            if out.len() == MAX_PER_BLOB {
360                return out;
361            }
362        }
363    }
364    out
365}
366
367fn reads_config(line: &str, current: &str, found: &mut Vec<(Kind, String, String, bool)>) {
368    let mut seen = BTreeSet::new();
369    for (patterns, certain) in [(&*ENV_CERTAIN, true), (&*CONFIG_MAYBE, false)] {
370        for pattern in patterns.iter() {
371            for captures in pattern.captures_iter(line) {
372                let key = captures[1].to_string();
373                if seen.insert(key.clone()) {
374                    found.push((Kind::ReadsConfig, current.to_string(), key, certain));
375                }
376            }
377        }
378    }
379}
380
381/// The handler a decorator or attribute line stands over: the next definition within a few lines.
382fn handler_below(below: &[&str]) -> Option<String> {
383    below
384        .iter()
385        .take(6)
386        .map(|line| line.trim_start())
387        .find(|line| !line.starts_with('@') && !line.starts_with("#[") && !line.is_empty())
388        .and_then(|line| NEXT_HANDLER.captures(line))
389        .map(|found| found[1].to_string())
390}
391
392fn serves_route(line: &str, below: &[&str], found: &mut Vec<(Kind, String, String, bool)>) {
393    let route = |method: &str, path: &str| {
394        let method = match method.to_ascii_uppercase().as_str() {
395            "ROUTE" | "API_ROUTE" | "ALL" => "ANY".to_string(),
396            other => other.to_string(),
397        };
398        format!("{method} {path}")
399    };
400    // A decorator or attribute stands over its handler; the three forms never share a line.
401    if let Some(captures) = PY_ROUTE.captures(line)
402        && let Some(handler) = handler_below(below)
403    {
404        let method = PY_METHODS
405            .captures(line)
406            .map_or_else(|| captures[2].to_string(), |m| m[1].to_string());
407        let receiver = captures[1].to_ascii_lowercase();
408        let known = ROUTERS.iter().any(|name| receiver == *name || receiver.ends_with(name));
409        found.push((Kind::ServesRoute, handler, route(&method, &captures[3]), known));
410    }
411    if let Some(captures) = NEST_ROUTE.captures(line)
412        && let Some(handler) = handler_below(below)
413    {
414        let path = captures.get(2).map_or("", |m| m.as_str()).trim_start_matches('/');
415        found.push((
416            Kind::ServesRoute,
417            handler,
418            route(&captures[1], &format!("/{path}")),
419            true,
420        ));
421    }
422    if let Some(captures) = RUST_ROUTE.captures(line)
423        && let Some(handler) = handler_below(below)
424    {
425        found.push((Kind::ServesRoute, handler, route(&captures[1], &captures[2]), true));
426    }
427    for captures in AXUM_ROUTE.captures_iter(line) {
428        let handler = captures[3].rsplit("::").next().unwrap_or(&captures[3]).to_string();
429        found.push((Kind::ServesRoute, handler, route(&captures[2], &captures[1]), true));
430    }
431    if let Some(captures) = EXPRESS_ROUTE.captures(line)
432        && let Some(handler) = LAST_HANDLER.captures(&captures[4])
433    {
434        let handler = handler[1].rsplit('.').next().unwrap_or(&handler[1]).to_string();
435        let receiver = captures[1].to_ascii_lowercase();
436        let known = ROUTERS.iter().any(|name| receiver == *name || receiver.ends_with(name));
437        found.push((Kind::ServesRoute, handler, route(&captures[2], &captures[3]), known));
438    }
439}
440
441fn touches_table(line: &str, from: Source, current: &str, found: &mut Vec<(Kind, String, String, bool)>) {
442    if let Some(captures) = TABLENAME.captures(line) {
443        found.push((Kind::TouchesTable, current.to_string(), captures[1].to_string(), true));
444    }
445    let sql_line = SQL_LINE.is_match(line.trim_start());
446    let mut seen = BTreeSet::new();
447    for pattern in SQL_TABLE.iter() {
448        for captures in pattern.captures_iter(line) {
449            let (keyword, table) = (captures.get(1).expect("group 1"), captures[2].to_string());
450            if NOT_TABLES.contains(&table.to_ascii_lowercase().as_str()) || !seen.insert(table.clone()) {
451                continue;
452            }
453            let upper = keyword.as_str() == keyword.as_str().to_ascii_uppercase();
454            let quotes = line[..keyword.start()]
455                .chars()
456                .filter(|c| matches!(c, '"' | '\'' | '`'))
457                .count();
458            let certain = match (from == Source::Sql, quotes % 2 == 1) {
459                (true, _) => true,
460                (false, quoted) if upper && (quoted || sql_line) => true,
461                (false, true) => false,
462                // Not SQL: `from x import y`, prose. Dropped here, no model asked.
463                (false, false) => continue,
464            };
465            found.push((Kind::TouchesTable, current.to_string(), table, certain));
466        }
467    }
468}
469
470fn imports(line: &str, from: Source, found: &mut Vec<(Kind, String, String, bool)>) {
471    let mut push = |module: String| found.push((Kind::Tests, String::new(), module, true));
472    match from {
473        Source::Rust => {
474            if let Some(captures) = RUST_USE.captures(line) {
475                push(captures[1].trim_start_matches("::").to_string());
476            }
477        }
478        Source::Python => {
479            if let Some(captures) = PY_FROM.captures(line) {
480                let module = captures[1].to_string();
481                for name in captures[2].split(',') {
482                    let name = name
483                        .split_whitespace()
484                        .next()
485                        .unwrap_or("")
486                        .trim_matches(|c| c == '(' || c == ')');
487                    if name.is_empty() || name == "*" {
488                        continue;
489                    }
490                    let joined = if module.ends_with('.') {
491                        format!("{module}{name}")
492                    } else {
493                        format!("{module}.{name}")
494                    };
495                    push(joined);
496                }
497            } else if let Some(captures) = PY_IMPORT.captures(line) {
498                push(captures[1].to_string());
499            }
500        }
501        Source::Script => {
502            for captures in SCRIPT_IMPORT.captures_iter(line) {
503                push(captures[1].to_string());
504            }
505        }
506        Source::Sql => {}
507    }
508}
509
510/// The repository file a test's import names, when it is one: Rust `use` paths (`crate::`, a workspace crate's
511/// name), Python modules (dotted, relative), relative TypeScript and JavaScript specifiers.
512pub fn resolve_import(path: &str, module: &str, paths: &BTreeSet<String>) -> Option<String> {
513    match source(path) {
514        Source::Rust => resolve_rust(path, module, paths),
515        Source::Python => resolve_python(path, module, paths),
516        Source::Script => resolve_script(path, module, paths),
517        Source::Sql => None,
518    }
519}
520
521fn parent(path: &str) -> &str {
522    path.rsplit_once('/').map_or("", |(dir, _)| dir)
523}
524
525fn joined(dir: &str, rest: &str) -> String {
526    if dir.is_empty() {
527        rest.to_string()
528    } else {
529        format!("{dir}/{rest}")
530    }
531}
532
533/// The deepest module file of `segments` under `root` (`<root>/a/b.rs`, `<root>/a/b/mod.rs`), else `fallback`.
534fn rust_module(root: &str, segments: &[&str], fallback: Option<String>, paths: &BTreeSet<String>) -> Option<String> {
535    let mut best = fallback.filter(|file| paths.contains(file));
536    for depth in 1..=segments.len() {
537        let stem = joined(root, &segments[..depth].join("/"));
538        for file in [format!("{stem}.rs"), format!("{stem}/mod.rs")] {
539            if paths.contains(&file) {
540                best = Some(file);
541            }
542        }
543    }
544    best
545}
546
547fn resolve_rust(path: &str, module: &str, paths: &BTreeSet<String>) -> Option<String> {
548    let segments: Vec<&str> = module.split("::").collect();
549    let (first, rest) = segments.split_first()?;
550    match *first {
551        "crate" => {
552            // The crate a file belongs to: `<dir>/src/` for its sources, `<dir>/tests/` for an integration test.
553            let root = ["src", "tests"].iter().find_map(|dir| {
554                let marker = format!("/{dir}/");
555                path.find(&marker)
556                    .map(|at| path[..at + marker.len() - 1].to_string())
557                    .or_else(|| path.starts_with(&format!("{dir}/")).then(|| dir.to_string()))
558            })?;
559            rust_module(&root, rest, None, paths)
560        }
561        "self" | "super" | "std" | "core" | "alloc" => None,
562        name => {
563            let dashed = name.replace('_', "-");
564            let lib = paths.iter().find(|file| {
565                [name, dashed.as_str()].iter().any(|crate_dir| {
566                    *file == &format!("{crate_dir}/src/lib.rs") || file.ends_with(&format!("/{crate_dir}/src/lib.rs"))
567                })
568            })?;
569            let root = parent(lib).to_string();
570            rust_module(&root, rest, Some(lib.clone()), paths)
571        }
572    }
573}
574
575fn resolve_python(path: &str, module: &str, paths: &BTreeSet<String>) -> Option<String> {
576    let dots = module.len() - module.trim_start_matches('.').len();
577    let rest = module.trim_start_matches('.');
578    let candidates = |base: &str| [format!("{base}.py"), format!("{base}/__init__.py")];
579    if dots > 0 {
580        let mut dir = parent(path).to_string();
581        for _ in 1..dots {
582            dir = parent(&dir).to_string();
583        }
584        // `from .a import b`: `b` may be a module of `a`, else a name defined in `a`.
585        let parts: Vec<&str> = rest.split('.').filter(|part| !part.is_empty()).collect();
586        for keep in (0..=parts.len()).rev() {
587            let base = joined(&dir, &parts[..keep].join("/"));
588            if let Some(found) = candidates(&base).into_iter().find(|file| paths.contains(file)) {
589                return Some(found);
590            }
591        }
592        return None;
593    }
594    let parts: Vec<&str> = rest.split('.').collect();
595    for keep in (1..=parts.len()).rev() {
596        let suffix = parts[..keep].join("/");
597        for file in candidates(&suffix) {
598            if let Some(found) = paths.iter().find(|p| **p == file || p.ends_with(&format!("/{file}"))) {
599                return Some(found.clone());
600            }
601        }
602    }
603    None
604}
605
606fn resolve_script(path: &str, module: &str, paths: &BTreeSet<String>) -> Option<String> {
607    if !module.starts_with('.') {
608        return None;
609    }
610    let mut parts: Vec<&str> = parent(path).split('/').filter(|part| !part.is_empty()).collect();
611    for part in module.split('/') {
612        match part {
613            "." | "" => {}
614            ".." => {
615                parts.pop()?;
616            }
617            part => parts.push(part),
618        }
619    }
620    let base = parts.join("/");
621    let mut candidates = vec![base.clone()];
622    for extension in ["ts", "tsx", "js", "jsx", "mjs", "cjs"] {
623        candidates.push(format!("{base}.{extension}"));
624    }
625    for extension in ["ts", "tsx", "js"] {
626        candidates.push(format!("{base}/index.{extension}"));
627    }
628    candidates.into_iter().find(|file| paths.contains(file))
629}
630
631/// What a task keeps of a revision's relations, and how many were dropped, by reason.
632#[derive(Clone, Debug, Default, PartialEq)]
633pub struct Pruned {
634    pub kept: Vec<Relation>,
635    pub dropped: BTreeMap<&'static str, usize>,
636}
637
638/// The relations a task asked for (`kinds`, all when empty), pruned with plain code: another kind (`kind`), a
639/// test's import that names no file of the tree (`unresolved`; a resolved one names the file), one the judge
640/// refused (`rejected`), and the same (kind, subject, object) again (`duplicate`). `paths` is every file of the
641/// tree.
642pub fn prune(rows: Vec<Relation>, kinds: &[Kind], paths: &BTreeSet<String>) -> Pruned {
643    let mut pruned = Pruned::default();
644    let mut seen = BTreeSet::new();
645    let mut drop = |reason: &'static str| *pruned.dropped.entry(reason).or_insert(0) += 1;
646    let mut kept = Vec::new();
647    for mut relation in rows {
648        if !kinds.is_empty() && !kinds.contains(&relation.kind) {
649            drop("kind");
650            continue;
651        }
652        if relation.kind == Kind::Tests {
653            match resolve_import(&relation.path, &relation.object, paths) {
654                Some(file) if file != relation.path => relation.object = file,
655                _ => {
656                    drop("unresolved");
657                    continue;
658                }
659            }
660        }
661        if relation.status == "rejected" {
662            drop("rejected");
663            continue;
664        }
665        if !seen.insert((relation.kind, relation.subject.clone(), relation.object.clone())) {
666            drop("duplicate");
667            continue;
668        }
669        kept.push(relation);
670    }
671    pruned.kept = kept;
672    pruned
673}