Skip to main content

knowledge/
index.rs

1//! Indexing one revision of a repository: list its tree, read only the blobs the store has not seen, record the
2//! tree. A second index of a nearby revision reads a handful of blobs.
3
4use std::io::{BufRead, BufReader, Read, Write};
5use std::path::Path;
6use std::process::{Command, Stdio};
7use std::time::Instant;
8
9use crate::extract::{EXTRACTOR_VERSION, Extractor, MAX_BYTES, language};
10use crate::relations::{Kind, Pruned, RELATIONS_VERSION, prune, scanned};
11use crate::store::{Error, Store};
12
13#[derive(Clone, Debug, Default, PartialEq, Eq)]
14pub struct IndexStats {
15    /// The commit indexed (the full id).
16    pub rev: String,
17    /// Indexable files in the tree.
18    pub files: usize,
19    /// Blobs read this time; the others were already in the store.
20    pub read: usize,
21    pub ms: u128,
22}
23
24fn git(repo_dir: &Path, args: &[&str]) -> Result<Vec<u8>, Error> {
25    let output = Command::new("git")
26        .arg("-C")
27        .arg(repo_dir)
28        .args(args)
29        .stdin(Stdio::null())
30        .output()
31        .map_err(|error| Error(format!("git {}: {error}", args.join(" "))))?;
32    if !output.status.success() {
33        return Err(Error(format!(
34            "git {} failed: {}",
35            args.join(" "),
36            String::from_utf8_lossy(&output.stderr).trim()
37        )));
38    }
39    Ok(output.stdout)
40}
41
42/// (path, blob, size) of every file at `rev`.
43fn blobs_at(repo_dir: &Path, rev: &str) -> Result<Vec<(String, String, u64)>, Error> {
44    let listing = git(repo_dir, &["ls-tree", "-r", "-l", "-z", "--full-tree", rev])?;
45    let mut entries = Vec::new();
46    for record in listing.split(|&byte| byte == 0).filter(|record| !record.is_empty()) {
47        let record = String::from_utf8_lossy(record);
48        // `<mode> SP <type> SP <object> SP+ <size> TAB <path>`
49        let Some((meta, path)) = record.split_once('\t') else {
50            continue;
51        };
52        let fields: Vec<&str> = meta.split_whitespace().collect();
53        let [_mode, kind, oid, size] = fields[..] else { continue };
54        let Ok(size) = size.parse::<u64>() else { continue };
55        if kind == "blob" {
56            entries.push((path.to_string(), oid.to_string(), size));
57        }
58    }
59    Ok(entries)
60}
61
62/// (path, blob, size) of the indexable files at `rev`.
63fn tree_entries(repo_dir: &Path, rev: &str) -> Result<Vec<(String, String, u64)>, Error> {
64    let mut entries = blobs_at(repo_dir, rev)?;
65    entries.retain(|(path, _, size)| language(path).is_some() && *size <= MAX_BYTES);
66    Ok(entries)
67}
68
69/// The contents of `oids`, in order, through one `git cat-file --batch`.
70fn read_blobs(repo_dir: &Path, oids: &[String]) -> Result<Vec<Vec<u8>>, Error> {
71    if oids.is_empty() {
72        return Ok(Vec::new());
73    }
74    let mut child = Command::new("git")
75        .arg("-C")
76        .arg(repo_dir)
77        .args(["cat-file", "--batch"])
78        .stdin(Stdio::piped())
79        .stdout(Stdio::piped())
80        .stderr(Stdio::null())
81        .spawn()
82        .map_err(|error| Error(format!("git cat-file: {error}")))?;
83    let mut stdin = child
84        .stdin
85        .take()
86        .ok_or_else(|| Error("git cat-file: no stdin".into()))?;
87    let input = oids.join("\n") + "\n";
88    // Written from a thread: git answers while it reads, and a full pipe either way would deadlock.
89    let writer = std::thread::spawn(move || stdin.write_all(input.as_bytes()));
90    let stdout = child
91        .stdout
92        .take()
93        .ok_or_else(|| Error("git cat-file: no stdout".into()))?;
94    let mut reader = BufReader::new(stdout);
95    let mut contents = Vec::with_capacity(oids.len());
96    for oid in oids {
97        let mut header = String::new();
98        reader
99            .read_line(&mut header)
100            .map_err(|error| Error(format!("git cat-file: {error}")))?;
101        let fields: Vec<&str> = header.split_whitespace().collect();
102        let size = match fields[..] {
103            [_, "blob", size] => size
104                .parse::<usize>()
105                .map_err(|_| Error(format!("git cat-file: {header:?}")))?,
106            _ => return Err(Error(format!("git cat-file: {oid}: {}", header.trim()))),
107        };
108        let mut body = vec![0; size + 1];
109        reader
110            .read_exact(&mut body)
111            .map_err(|error| Error(format!("git cat-file: {error}")))?;
112        body.truncate(size);
113        contents.push(body);
114    }
115    let _ = writer.join();
116    let _ = child.wait();
117    Ok(contents)
118}
119
120/// Indexes `repo` (a stable name such as `github.com/owner/name`) at `rev` of the git checkout `repo_dir` into the
121/// store at `db`. Indexing the same revision again only refreshes its tree.
122pub fn index_tree(db: &Path, repo: &str, repo_dir: &Path, rev: &str) -> Result<IndexStats, Error> {
123    let started = Instant::now();
124    if rev.is_empty() || rev.starts_with('-') {
125        return Err(Error(format!("not a revision: {rev:?}")));
126    }
127    let commit = git(
128        repo_dir,
129        &["rev-parse", "--verify", "--quiet", &format!("{rev}^{{commit}}")],
130    )?;
131    let commit = String::from_utf8_lossy(&commit).trim().to_string();
132    let entries = tree_entries(repo_dir, &commit)?;
133    let mut store = Store::open(db)?;
134    let oids: Vec<&str> = entries.iter().map(|(_, oid, _)| oid.as_str()).collect();
135    let known = store.known_blobs(&oids, EXTRACTOR_VERSION)?;
136    let mut unread: Vec<(String, String)> = Vec::new();
137    let mut queued = std::collections::HashSet::new();
138    for (path, oid, _) in &entries {
139        if !known.contains(oid) && queued.insert(oid.clone()) {
140            unread.push((path.clone(), oid.clone()));
141        }
142    }
143    let mut extractor = Extractor::new().map_err(Error)?;
144    let mut blobs = Vec::with_capacity(unread.len());
145    let unread_oids: Vec<String> = unread.iter().map(|(_, oid)| oid.clone()).collect();
146    for ((path, oid), body) in unread.iter().zip(read_blobs(repo_dir, &unread_oids)?) {
147        let Some(lang) = language(path) else { continue };
148        // A file that is not UTF-8 is not source anyone reads; it is stored with nothing extracted.
149        let extracted = match String::from_utf8(body) {
150            Ok(text) => extractor.extract(lang, &text),
151            Err(_) => Default::default(),
152        };
153        blobs.push((oid.clone(), lang.name().to_string(), extracted));
154    }
155    let paths: Vec<(String, String)> = entries.into_iter().map(|(path, oid, _)| (path, oid)).collect();
156    let indexed_at = jsrt::date::now_ms();
157    store.record_tree(repo, &commit, &paths, &blobs, EXTRACTOR_VERSION, indexed_at)?;
158    Ok(IndexStats {
159        rev: commit,
160        files: paths.len(),
161        read: blobs.len(),
162        ms: started.elapsed().as_millis(),
163    })
164}
165
166/// Files read for relations in one call, at most: a bound on a monorepo asked about as a whole.
167pub const MAX_RELATION_FILES: usize = 5000;
168
169/// The relations a task asked for at one revision ([`relations`]).
170#[derive(Clone, Debug, PartialEq)]
171pub struct Relations {
172    /// The commit (the full id) and its tree in the store.
173    pub rev: String,
174    pub tree: i64,
175    /// What the task keeps, and what pruning dropped.
176    pub pruned: Pruned,
177    /// Files in scope, and blobs read this time (the others were read before, by this proposer version).
178    pub files: usize,
179    pub read: usize,
180    /// More files were in scope than [`MAX_RELATION_FILES`]: narrow `scope`.
181    pub truncated: bool,
182}
183
184/// Which files a task asked about: files and directories (`""` or `.` for all); everything when empty.
185struct Scope {
186    all: bool,
187    names: std::collections::HashSet<String>,
188}
189
190impl Scope {
191    fn new(scope: &[String]) -> Scope {
192        let names: std::collections::HashSet<String> =
193            scope.iter().map(|name| name.trim_matches('/').to_string()).collect();
194        Scope {
195            all: names.is_empty() || names.contains("") || names.contains("."),
196            names,
197        }
198    }
199
200    /// The path itself, or one of its directories, was named.
201    fn holds(&self, path: &str) -> bool {
202        self.all || self.names.contains(path) || path.match_indices('/').any(|(at, _)| self.names.contains(&path[..at]))
203    }
204}
205
206/// The relations of `kinds` (all when empty) among the files under `scope` of `repo` at `rev` of the git
207/// checkout `repo_dir`: the revision is indexed first (only blobs the store has not seen are read), the proposer
208/// reads only blobs it has not read at [`RELATIONS_VERSION`], and the result is pruned for the task. Verdicts the
209/// judge gave earlier come back with their relations.
210pub fn relations(
211    db: &Path,
212    repo: &str,
213    repo_dir: &Path,
214    rev: &str,
215    kinds: &[Kind],
216    scope: &[String],
217) -> Result<Relations, Error> {
218    let indexed = index_tree(db, repo, repo_dir, rev)?;
219    let all = blobs_at(repo_dir, &indexed.rev)?;
220    let paths: std::collections::BTreeSet<String> = all.iter().map(|(path, _, _)| path.clone()).collect();
221    let scope = Scope::new(scope);
222    let mut files: Vec<(String, String)> = all
223        .into_iter()
224        .filter(|(path, _, size)| scanned(path) && *size <= MAX_BYTES && scope.holds(path))
225        .map(|(path, oid, _)| (path, oid))
226        .collect();
227    let truncated = files.len() > MAX_RELATION_FILES;
228    files.truncate(MAX_RELATION_FILES);
229    let mut store = Store::open(db)?;
230    let tree = store
231        .tree_id(repo, &indexed.rev)?
232        .ok_or_else(|| Error(format!("{repo} at {} was not recorded", indexed.rev)))?;
233    let oids: Vec<&str> = files.iter().map(|(_, oid)| oid.as_str()).collect();
234    let known = store.scanned_blobs(&oids, RELATIONS_VERSION)?;
235    let mut unread: Vec<(String, String)> = Vec::new();
236    let mut queued = std::collections::HashSet::new();
237    for (path, oid) in &files {
238        if !known.contains(oid) && queued.insert(oid.clone()) {
239            unread.push((path.clone(), oid.clone()));
240        }
241    }
242    let unread_oids: Vec<String> = unread.iter().map(|(_, oid)| oid.clone()).collect();
243    let mut read = Vec::with_capacity(unread.len());
244    for ((path, oid), body) in unread.iter().zip(read_blobs(repo_dir, &unread_oids)?) {
245        // Text that is not UTF-8 is not source: recorded as read, with nothing in it.
246        let proposed = String::from_utf8(body)
247            .map(|text| crate::relations::propose(path, &text))
248            .unwrap_or_default();
249        read.push((oid.clone(), proposed));
250    }
251    store.record_relations(tree, &files, &read, RELATIONS_VERSION)?;
252    let in_files: Vec<String> = files.iter().map(|(path, _)| path.clone()).collect();
253    let rows = store.relations(tree, Some(&in_files))?;
254    Ok(Relations {
255        rev: indexed.rev,
256        tree,
257        pruned: prune(rows, kinds, &paths),
258        files: files.len(),
259        read: read.len(),
260        truncated,
261    })
262}