char/sorcery

static-files based git repo viewer

git clone https://git.t4t.associates/char/sorcery

Charlotte Somexperiment: support sha-256 oids in git repos42f80d8

main
branchesmainall refs →
17.6 KiB557 linesraw
1use std::collections::{HashMap, HashSet, VecDeque};
2
3use anyhow::Result;
4use axum::body::{Body, to_bytes};
5use axum::extract::{Path as AxumPath, State};
6use axum::http::{HeaderValue, Request, StatusCode, header};
7use axum::response::{IntoResponse, Response};
8
9use crate::history;
10
11use super::{AppState, WebResult, internal};
12
13const MAX_OBJECT_QUERY_OBJECTS: usize = 128;
14const MAX_OBJECT_QUERY_BYTES: usize = 16 << 20;
15const MAX_COMMIT_PREFETCH: usize = 25;
16const MAX_HISTORY_FRONTIER: usize = 4096;
17/// Commits examined per path-history request; the client loops on the frontier.
18const HISTORY_SCAN_LIMIT: usize = 5000;
19
20#[derive(Clone, Copy, serde::Deserialize)]
21#[serde(rename_all = "kebab-case")]
22enum SmartObjectQuery {
23    Tree,
24    CommitDiff,
25    CommitPagination,
26    PathHistory,
27}
28
29#[derive(serde::Deserialize)]
30struct ObjectQuery {
31    oids: Vec<String>,
32    #[serde(default)]
33    depth: usize,
34    smart: Option<SmartObjectQuery>,
35    limit: Option<usize>,
36    path: Option<Vec<String>>,
37}
38
39enum ObjectQueryMode {
40    Generic(usize),
41    Tree,
42    CommitDiff,
43    CommitPagination(usize),
44    PathHistory { limit: usize, path: Vec<String> },
45}
46
47struct ObjectBundle {
48    data: Vec<u8>,
49    seen: HashSet<gix::ObjectId>,
50    full: bool,
51}
52
53impl ObjectBundle {
54    fn new() -> Self {
55        Self {
56            // SOBJ, version, flags (bit 0 = truncated), then
57            // oid-length/oid/kind/u32be-size/data frames. Kinds 1-4 are git
58            // objects; kind 5 is a payload-less "resume from here" marker.
59            data: b"SOBJ\x01\0".to_vec(),
60            seen: HashSet::new(),
61            full: false,
62        }
63    }
64
65    fn object<'repo>(
66        &mut self,
67        repo: &'repo gix::Repository,
68        oid: gix::ObjectId,
69    ) -> Option<gix::Object<'repo>> {
70        if self.full {
71            return None;
72        }
73        let object = repo.find_object(oid).ok()?;
74        if self.seen.contains(&oid) {
75            return Some(object);
76        }
77        let oid_bytes = oid.as_bytes();
78        let frame_bytes = 1 + oid_bytes.len() + 1 + 4 + object.data.len();
79        if self.seen.len() == MAX_OBJECT_QUERY_OBJECTS
80            || self
81                .data
82                .len()
83                .checked_add(frame_bytes)
84                .is_none_or(|size| size > MAX_OBJECT_QUERY_BYTES)
85        {
86            self.data[5] = 1;
87            self.full = true;
88            return None;
89        }
90        let kind = match object.kind {
91            gix::object::Kind::Commit => 1,
92            gix::object::Kind::Tree => 2,
93            gix::object::Kind::Blob => 3,
94            gix::object::Kind::Tag => 4,
95        };
96        self.seen.insert(oid);
97        self.data.push(oid_bytes.len() as u8);
98        self.data.extend_from_slice(oid_bytes);
99        self.data.push(kind);
100        self.data
101            .extend_from_slice(&(object.data.len() as u32).to_be_bytes());
102        self.data.extend_from_slice(&object.data);
103        Some(object)
104    }
105
106    fn frontier(&mut self, oid: gix::ObjectId) {
107        let oid_bytes = oid.as_bytes();
108        self.data.push(oid_bytes.len() as u8);
109        self.data.extend_from_slice(oid_bytes);
110        self.data.push(5);
111        self.data.extend_from_slice(&0u32.to_be_bytes());
112    }
113}
114
115fn generic_object_bundle(
116    repo: &gix::Repository,
117    roots: Vec<gix::ObjectId>,
118    depth: usize,
119) -> Result<Vec<u8>> {
120    let mut bundle = ObjectBundle::new();
121    let mut queue = roots
122        .into_iter()
123        .map(|oid| (oid, 0usize))
124        .collect::<VecDeque<_>>();
125    while let Some((oid, object_depth)) = queue.pop_front() {
126        if bundle.full {
127            break;
128        }
129        if bundle.seen.contains(&oid) {
130            continue;
131        }
132        let Some(object) = bundle.object(repo, oid) else {
133            continue;
134        };
135        if object_depth == depth {
136            continue;
137        }
138        let mut remaining =
139            MAX_OBJECT_QUERY_OBJECTS.saturating_sub(bundle.seen.len() + queue.len());
140        let mut enqueue = |oid| {
141            if remaining == 0 {
142                bundle.data[5] = 1;
143                return false;
144            }
145            remaining -= 1;
146            queue.push_back((oid, object_depth + 1));
147            true
148        };
149        match object.kind {
150            gix::object::Kind::Commit => {
151                let commit = object.into_commit();
152                if enqueue(commit.tree_id()?.detach()) {
153                    for parent in commit.parent_ids() {
154                        if !enqueue(parent.detach()) {
155                            break;
156                        }
157                    }
158                }
159            }
160            gix::object::Kind::Tree => {
161                for entry in object.into_tree().iter() {
162                    if !enqueue(entry?.oid().to_owned()) {
163                        break;
164                    }
165                }
166            }
167            gix::object::Kind::Tag => {
168                enqueue(object.into_tag().target_id()?.detach());
169            }
170            gix::object::Kind::Blob => {}
171        }
172    }
173    Ok(bundle.data)
174}
175
176fn commit_pagination_object_bundle(
177    repo: &gix::Repository,
178    roots: Vec<gix::ObjectId>,
179    limit: usize,
180) -> Result<Vec<u8>> {
181    let mut bundle = ObjectBundle::new();
182    let mut queue = VecDeque::from(roots);
183    let mut commits = 0;
184
185    while commits < limit {
186        let Some(oid) = queue.pop_front() else {
187            break;
188        };
189        if bundle.seen.contains(&oid) {
190            continue;
191        }
192        let Some(object) = bundle.object(repo, oid) else {
193            continue;
194        };
195        match object.kind {
196            gix::object::Kind::Commit => {
197                commits += 1;
198                queue.extend(object.into_commit().parent_ids().map(|id| id.detach()));
199            }
200            gix::object::Kind::Tag => {
201                queue.push_front(object.into_tag().target_id()?.detach());
202            }
203            _ => {}
204        }
205    }
206    Ok(bundle.data)
207}
208
209/// The commits of `git log -- path` from `frontier`, in order, then the
210/// frontier to resume from, then (best effort) each commit's trees along the
211/// path so the client can locate the object without further requests.
212fn path_history_object_bundle(
213    repo: &gix::Repository,
214    frontier: &[gix::ObjectId],
215    path: &[String],
216    limit: usize,
217) -> Result<Vec<u8>> {
218    let page = history::page(repo, frontier, path, limit, HISTORY_SCAN_LIMIT)?;
219    let mut bundle = ObjectBundle::new();
220    for &oid in &page.changes {
221        bundle.object(repo, oid);
222    }
223    for oid in page.frontier {
224        bundle.frontier(oid);
225    }
226    'commits: for &oid in &page.changes {
227        let Some(commit) = bundle.object(repo, oid) else {
228            break;
229        };
230        let mut tree_oid = commit.into_commit().tree_id()?.detach();
231        for component in path {
232            let Some(tree) = bundle.object(repo, tree_oid) else {
233                break 'commits;
234            };
235            let next = tree.into_tree().iter().find_map(|entry| {
236                let entry = entry.ok()?;
237                (entry.filename() == component.as_bytes() && entry.mode().is_tree())
238                    .then(|| entry.oid().to_owned())
239            });
240            let Some(next) = next else {
241                break;
242            };
243            tree_oid = next;
244        }
245    }
246    Ok(bundle.data)
247}
248
249fn tree_object_bundle(repo: &gix::Repository, roots: Vec<gix::ObjectId>) -> Result<Vec<u8>> {
250    let mut bundle = ObjectBundle::new();
251    let mut queue = VecDeque::from(roots);
252
253    while let Some(oid) = queue.pop_front() {
254        if bundle.full {
255            break;
256        }
257        if bundle.seen.contains(&oid) {
258            continue;
259        }
260        let Some(object) = bundle.object(repo, oid) else {
261            continue;
262        };
263        match object.kind {
264            gix::object::Kind::Commit => queue.push_back(object.into_commit().tree_id()?.detach()),
265            gix::object::Kind::Tree => {
266                for entry in object.into_tree().iter() {
267                    let entry = entry?;
268                    if entry.mode().is_tree() {
269                        if bundle.seen.len() + queue.len() == MAX_OBJECT_QUERY_OBJECTS {
270                            bundle.data[5] = 1;
271                            break;
272                        }
273                        queue.push_back(entry.oid().to_owned());
274                    }
275                }
276            }
277            gix::object::Kind::Tag => queue.push_back(object.into_tag().target_id()?.detach()),
278            gix::object::Kind::Blob => {}
279        }
280    }
281    Ok(bundle.data)
282}
283
284#[derive(Clone, Copy)]
285struct DiffEntry {
286    oid: gix::ObjectId,
287    mode: u16,
288    tree: bool,
289    gitlink: bool,
290}
291
292fn bundle_tree_entries(
293    repo: &gix::Repository,
294    bundle: &mut ObjectBundle,
295    oid: Option<gix::ObjectId>,
296) -> Result<HashMap<Vec<u8>, DiffEntry>> {
297    let Some(oid) = oid else {
298        return Ok(HashMap::new());
299    };
300    let Some(object) = bundle.object(repo, oid) else {
301        return Ok(HashMap::new());
302    };
303    let mut entries = HashMap::new();
304    for entry in object.into_tree().iter() {
305        let entry = entry?;
306        let mode = entry.mode();
307        entries.insert(
308            entry.filename().to_vec(),
309            DiffEntry {
310                oid: entry.oid().to_owned(),
311                mode: mode.value(),
312                tree: mode.is_tree(),
313                gitlink: mode.is_commit(),
314            },
315        );
316    }
317    Ok(entries)
318}
319
320fn commit_diff_object_bundle(repo: &gix::Repository, roots: Vec<gix::ObjectId>) -> Result<Vec<u8>> {
321    let mut bundle = ObjectBundle::new();
322    let mut trees = VecDeque::new();
323
324    for mut oid in roots {
325        if bundle.full {
326            break;
327        }
328        loop {
329            let Some(object) = bundle.object(repo, oid) else {
330                break;
331            };
332            match object.kind {
333                gix::object::Kind::Tag => oid = object.into_tag().target_id()?.detach(),
334                gix::object::Kind::Commit => {
335                    let commit = object.into_commit();
336                    let new_tree = commit.tree_id()?.detach();
337                    let old_tree = if let Some(parent) = commit.parent_ids().next() {
338                        let parent = parent.detach();
339                        bundle
340                            .object(repo, parent)
341                            .map(|object| object.into_commit().tree_id().map(|id| id.detach()))
342                            .transpose()?
343                    } else {
344                        None
345                    };
346                    trees.push_back((old_tree, Some(new_tree)));
347                    break;
348                }
349                _ => break,
350            }
351        }
352    }
353
354    let mut visited = HashSet::new();
355    while let Some((old_tree, new_tree)) = trees.pop_front() {
356        if bundle.full {
357            break;
358        }
359        if old_tree == new_tree || !visited.insert((old_tree, new_tree)) {
360            continue;
361        }
362        let mut old_entries = bundle_tree_entries(repo, &mut bundle, old_tree)?;
363        let new_entries = bundle_tree_entries(repo, &mut bundle, new_tree)?;
364
365        let mut changed = |old: Option<DiffEntry>, new: Option<DiffEntry>| -> Result<()> {
366            if old
367                .zip(new)
368                .is_some_and(|(old, new)| old.oid == new.oid && old.mode == new.mode)
369            {
370                return Ok(());
371            }
372            if old.is_some_and(|entry| entry.tree) || new.is_some_and(|entry| entry.tree) {
373                trees.push_back((
374                    old.filter(|entry| entry.tree).map(|entry| entry.oid),
375                    new.filter(|entry| entry.tree).map(|entry| entry.oid),
376                ));
377            }
378            if old.is_some_and(|entry| entry.gitlink) || new.is_some_and(|entry| entry.gitlink) {
379                return Ok(());
380            }
381            for entry in [old, new].into_iter().flatten() {
382                if !entry.tree {
383                    let _ = bundle.object(repo, entry.oid);
384                }
385            }
386            Ok(())
387        };
388
389        for (name, new) in new_entries {
390            changed(old_entries.remove(&name), Some(new))?;
391        }
392        for old in old_entries.into_values() {
393            changed(Some(old), None)?;
394        }
395    }
396    Ok(bundle.data)
397}
398
399pub(super) async fn query(
400    State(state): State<AppState>,
401    AxumPath((user, repo)): AxumPath<(String, String)>,
402    request: Request<Body>,
403) -> WebResult<Response> {
404    if request.method().as_str() != "QUERY" {
405        return Err((StatusCode::METHOD_NOT_ALLOWED, "QUERY required".into()));
406    }
407    if request
408        .headers()
409        .get(header::CONTENT_TYPE)
410        .and_then(|value| value.to_str().ok())
411        .and_then(|value| value.split(';').next())
412        != Some("application/json")
413    {
414        return Err((
415            StatusCode::UNSUPPORTED_MEDIA_TYPE,
416            "expected application/json".into(),
417        ));
418    }
419    let body = to_bytes(request.into_body(), 256 << 10)
420        .await
421        .map_err(|_| {
422            (
423                StatusCode::PAYLOAD_TOO_LARGE,
424                "object query is too large".into(),
425            )
426        })?;
427    let ObjectQuery {
428        oids,
429        depth,
430        smart,
431        limit,
432        path,
433    } = serde_json::from_slice(&body)
434        .map_err(|_| (StatusCode::BAD_REQUEST, "invalid object query".into()))?;
435    let mode = match (smart, limit, path) {
436        (None, None, None) if depth <= 2 => ObjectQueryMode::Generic(depth),
437        (Some(SmartObjectQuery::Tree), None, None) if depth == 0 => ObjectQueryMode::Tree,
438        (Some(SmartObjectQuery::CommitDiff), None, None) if depth == 0 => {
439            ObjectQueryMode::CommitDiff
440        }
441        (Some(SmartObjectQuery::CommitPagination), Some(limit), None)
442            if depth == 0 && (1..=MAX_COMMIT_PREFETCH).contains(&limit) =>
443        {
444            ObjectQueryMode::CommitPagination(limit)
445        }
446        (Some(SmartObjectQuery::PathHistory), Some(limit), Some(path))
447            if depth == 0
448                && (1..=MAX_COMMIT_PREFETCH).contains(&limit)
449                && path.iter().all(|component| {
450                    !component.is_empty()
451                        && component != "."
452                        && component != ".."
453                        && !component.contains('/')
454                        && !component.contains('\0')
455                }) =>
456        {
457            ObjectQueryMode::PathHistory { limit, path }
458        }
459        _ => {
460            return Err((
461                StatusCode::UNPROCESSABLE_ENTITY,
462                "invalid object query bounds".into(),
463            ));
464        }
465    };
466    // a path-history frontier can fan out past the object cap; it's oids only
467    let max_oids = match mode {
468        ObjectQueryMode::PathHistory { .. } => MAX_HISTORY_FRONTIER,
469        _ => MAX_OBJECT_QUERY_OBJECTS,
470    };
471    if oids.is_empty() || oids.len() > max_oids {
472        return Err((
473            StatusCode::UNPROCESSABLE_ENTITY,
474            "invalid object query bounds".into(),
475        ));
476    }
477    let roots = oids
478        .iter()
479        .map(|oid| {
480            gix::ObjectId::from_hex(oid.as_bytes())
481                .map_err(|_| (StatusCode::UNPROCESSABLE_ENTITY, "invalid object id".into()))
482        })
483        .collect::<WebResult<Vec<_>>>()?;
484
485    let path = state.resolve(&user, &repo)?.repository.path;
486    let permit = state.git_permit()?;
487    let data = tokio::task::spawn_blocking(move || -> Result<Vec<u8>> {
488        let _permit = permit;
489        let mut repo = gix::open(path)?;
490        // deep tree delta chains in large repos make repeated lookups expensive
491        repo.object_cache_size_if_unset(64 << 20);
492        match mode {
493            ObjectQueryMode::Generic(depth) => generic_object_bundle(&repo, roots, depth),
494            ObjectQueryMode::Tree => tree_object_bundle(&repo, roots),
495            ObjectQueryMode::CommitDiff => commit_diff_object_bundle(&repo, roots),
496            ObjectQueryMode::CommitPagination(limit) => {
497                commit_pagination_object_bundle(&repo, roots, limit)
498            }
499            ObjectQueryMode::PathHistory { limit, path } => {
500                path_history_object_bundle(&repo, &roots, &path, limit)
501            }
502        }
503    })
504    .await
505    .map_err(internal)?
506    .map_err(internal)?;
507
508    let mut response = Body::from(data).into_response();
509    response.headers_mut().insert(
510        header::CONTENT_TYPE,
511        HeaderValue::from_static("application/x-git-object-bundle"),
512    );
513    response
514        .headers_mut()
515        .insert(header::CACHE_CONTROL, HeaderValue::from_static("no-store"));
516    response
517        .headers_mut()
518        .insert("accept-query", HeaderValue::from_static("application/json"));
519    Ok(response)
520}
521
522#[cfg(test)]
523mod tests {
524    use std::fs;
525
526    use anyhow::Result;
527
528    use crate::testutil::{TempDir, commit, init_sha256_repo};
529
530    use super::generic_object_bundle;
531
532    #[test]
533    fn bundles_sha256_object_ids() -> Result<()> {
534        let root = TempDir::new("sha256-bundle");
535        let repo_path = root.join("repo");
536        init_sha256_repo(&repo_path)?;
537        fs::write(repo_path.join("file"), "contents")?;
538        let head = commit(&repo_path, "initial")?;
539
540        let repo = gix::open(repo_path)?;
541        let bundle =
542            generic_object_bundle(&repo, vec![gix::ObjectId::from_hex(head.as_bytes())?], 2)?;
543        let mut position = 6;
544        let mut frames = 0;
545        while position < bundle.len() {
546            let oid_bytes = bundle[position] as usize;
547            assert_eq!(oid_bytes, 32);
548            let size_at = position + 1 + oid_bytes + 1;
549            let size = u32::from_be_bytes(bundle[size_at..size_at + 4].try_into()?) as usize;
550            position = size_at + 4 + size;
551            frames += 1;
552        }
553        assert_eq!(position, bundle.len());
554        assert_eq!(frames, 3);
555        Ok(())
556    }
557}