steid
Sign in

@jamesgill /

steid

steid/src/application/search.rs
21.1 KBCode·Blame·Raw
1b7587dfeat: finding a string in a repository, and landing on the line19h
1//! Searching a repository's code.
2//!
3//! `git grep` over one revision's tree, fixed-string. The parsing of git's output lives
4//! here rather than in the adapter because it is a parse of a documented text format,
5//! and a parse with tests on captured samples is worth more than one that can only be
6//! exercised by building a repository first.
7//!
8//! Authorization is not re-implemented: like everything in [`browse`](super::browse) it
9//! goes through [`view_repo`](super::repo::view_repo), so a repository invisible on its
10//! page cannot be searched either — including by guessing at the shape of its contents,
11//! which an unauthorized search would leak a byte at a time.
12
13use crate::domain::{
14 Actor, GrepHit, ObjectId, OrgName, RefName, RepoName, RepoPath,
15 repository::{MembershipRepository, OrgRepository, RepoRepository},
16};
17
18use super::{error::Result, port::GitQuery, repo::view_repo};
19
20/// How many matching lines a search shows.
21///
22/// A cap rather than paging, matching [`LOG_LIMIT`](super::browse::LOG_LIMIT): a search
23/// that needs its 201st result needs a narrower query, and the page says so rather than
24/// pretending the rest are not there.
25pub const SEARCH_LIMIT: usize = 200;
26
27/// The longest query accepted, in bytes.
28///
29/// Nothing anybody types is this long; what is this long is a paste, and it becomes an
30/// argument to a subprocess. Bytes rather than characters because that is what the
31/// argument list is measured in.
32pub const MAX_QUERY_BYTES: usize = 200;
33
34/// The longest line of a match carried back.
35///
36/// A minified bundle is one line, and a repository holding one should not be able to
37/// make a search page megabytes long. Cut lines are marked so the page is not silently
38/// lying about what is in the file.
39pub const MAX_LINE_CHARS: usize = 500;
40
41/// One file's matches, in the order git reported them.
42#[derive(Debug, Clone, PartialEq, Eq)]
43pub struct SearchFile {
44 pub path: RepoPath,
45 pub matches: Vec<GrepHit>,
46}
47
48/// What a search found.
49#[derive(Debug, Clone, PartialEq, Eq)]
50pub struct SearchResults {
51 /// The revision searched, resolved — so the page can link its results to blobs and
52 /// pre-fill its own form with a revision that is known to exist.
53 pub rev: RefName,
54 pub query: String,
55 /// Grouped by file, files in the order their first match appeared.
56 pub files: Vec<SearchFile>,
57 pub matches: usize,
58 /// Whether there were more matches than [`SEARCH_LIMIT`].
59 pub truncated: bool,
60}
61
62/// The states a search page can be in.
63///
64/// Every one of them is a page rather than an error, which is the point of the enum:
65/// a repository with nothing in it, a query nobody should have sent, and a repository
66/// too large to grep in the time allowed are all things to say, not 500s.
67#[derive(Debug, Clone, PartialEq, Eq)]
68pub enum Searched {
69 /// No commits, so nothing to search.
70 Empty,
71 /// Longer than [`MAX_QUERY_BYTES`]. Refused rather than quietly shortened —
72 /// searching for something other than what was typed and saying nothing is worse
73 /// than saying no.
74 QueryTooLong {
75 rev: RefName,
76 },
77 /// git was killed by the read timeout. The page says so and keeps the form filled,
78 /// because the answer to a search that took too long is a narrower search.
79 TimedOut {
80 rev: RefName,
81 query: String,
82 },
83 Found(SearchResults),
84}
85
86/// Searches one revision of a repository for a fixed string.
87///
88/// `rev` of `None` means the default branch, which is what the search box on a
89/// repository's page asks for.
90///
91/// **Two or three `git` processes**: resolving the revision, plus the default-branch
92/// lookup when the caller did not name one, plus the grep itself — and none of the last
93/// when the query is empty, which is the state the page opens in.
94///
95/// `Ok(None)` means the repository is invisible, absent, or the named revision is not
96/// there — one answer, for the reason [`view_repo`](super::repo::view_repo) gives.
97#[allow(clippy::too_many_arguments)]
98pub async fn search_repo(
99 handle: &OrgName,
100 name: &RepoName,
101 rev: Option<&RefName>,
102 query: &str,
103 actor: &Actor,
104 orgs: &impl OrgRepository,
105 memberships: &impl MembershipRepository,
106 repos: &impl RepoRepository,
107 queries: &impl GitQuery,
108) -> Result<Option<Searched>> {
109 if view_repo(handle, name, actor, orgs, memberships, repos)
110 .await?
111 .is_none()
112 {
113 return Ok(None);
114 }
115
116 let rev = match rev {
117 Some(rev) => rev.clone(),
118 None => match queries.default_branch(handle, name).await? {
119 Some(branch) => branch,
120 None => return Ok(Some(Searched::Empty)),
121 },
122 };
123
124 // Resolved before grepping: `git grep` on a revision that is not there is fatal, and
125 // this module's adapter treats a fatal git as a real fault. A revision that does not
126 // resolve is a 404, the same as it is on the tree pages.
127 let Some(commit) = queries.resolve(handle, name, &rev).await? else {
128 return Ok(None);
129 };
130
131 let query = query.trim();
132
133 if query.len() > MAX_QUERY_BYTES {
134 return Ok(Some(Searched::QueryTooLong { rev }));
135 }
136
137 // No query is the page's opening state, not a search for nothing. Spending a
138 // subprocess to learn that everything matches the empty string would be worse than
139 // useless: `git grep -F ""` matches every line of every file.
140 if query.is_empty() {
141 return Ok(Some(Searched::Found(SearchResults {
142 rev,
143 query: String::new(),
144 files: Vec::new(),
145 matches: 0,
146 truncated: false,
147 })));
148 }
149
150 // One more than is shown, which is how truncation is detected without a second
151 // question.
152 let hits = match queries
153 .grep(handle, name, &commit, query, SEARCH_LIMIT + 1)
154 .await
155 {
156 Ok(hits) => hits,
157 Err(error) if error.is_timeout() => {
158 return Ok(Some(Searched::TimedOut {
159 rev,
160 query: query.to_owned(),
161 }));
162 }
163 Err(error) => return Err(error.into()),
164 };
165
166 let truncated = hits.len() > SEARCH_LIMIT;
167 let mut hits = hits;
168 hits.truncate(SEARCH_LIMIT);
169
170 Ok(Some(Searched::Found(SearchResults {
171 rev,
172 query: query.to_owned(),
173 matches: hits.len(),
174 files: group_by_file(hits),
175 truncated,
176 })))
177}
178
179/// Collects hits into one entry per file, keeping git's order.
180///
181/// `git grep` already emits a file's matches together, so this is a fold rather than a
182/// sort — and keeping git's order means the first file on the page is the first file in
183/// the tree, which is at least a stable answer.
184fn group_by_file(hits: Vec<GrepHit>) -> Vec<SearchFile> {
185 let mut files: Vec<SearchFile> = Vec::new();
186
187 for hit in hits {
188 match files.last_mut() {
189 Some(file) if file.path == hit.path => file.matches.push(hit),
190 _ => files.push(SearchFile {
191 path: hit.path.clone(),
192 matches: vec![hit],
193 }),
194 }
195 }
196
197 files
198}
199
200/// Parses `git grep -z -n --column` output for one revision.
201///
202/// Each record is `<commit>:<path> NUL <line> NUL <column> NUL <text> LF`. `-z` is what
203/// makes this parseable at all: without it the separator is a colon, and a path may
204/// contain colons — so `src/a:b.rs:12:3:text` has no unambiguous reading. With it the
205/// only ambiguity left is a newline inside a *path*, which is why records are found by
206/// walking the NULs rather than by splitting on lines.
207///
208/// Anything unreadable ends the parse rather than failing it: a partial answer from a
209/// search is more use than an error page, and the alternative is one strange path in one
210/// repository breaking the whole feature.
211fn parse_grep(stdout: &[u8], prefix: &str, limit: usize) -> Vec<GrepHit> {
212 let mut hits = Vec::new();
213 let mut rest = stdout;
214
215 while hits.len() < limit && !rest.is_empty() {
216 let Some((path, after)) = take_field(rest) else {
217 break;
218 };
219 let Some((line, after)) = take_field(after) else {
220 break;
221 };
222 let Some((column, after)) = take_field(after) else {
223 break;
224 };
225
226 // The text runs to the end of the line, and a matched line cannot itself contain
227 // a newline — that is what makes it a line.
228 let (text, after) = match after.iter().position(|byte| *byte == b'\n') {
229 Some(end) => (&after[..end], &after[end + 1..]),
230 None => (after, &after[after.len()..]),
231 };
232
233 rest = after;
234
235 // Lossy: a path or a line that is not UTF-8 still gets shown, with replacement
236 // characters, rather than disappearing from the results. Dropping a match
237 // silently would make a search quietly incomplete, which is worse than ugly.
238 let path = String::from_utf8_lossy(path);
239 let Some(path) = path.strip_prefix(prefix) else {
240 continue;
241 };
242 let Ok(path) = RepoPath::new(path) else {
243 continue;
244 };
245
246 let Ok(line) = String::from_utf8_lossy(line).parse() else {
247 continue;
248 };
249 let Ok(column) = String::from_utf8_lossy(column).parse() else {
250 continue;
251 };
252
253 hits.push(GrepHit {
254 path,
255 line,
256 column,
257 text: cut(&String::from_utf8_lossy(text)),
258 });
259 }
260
261 hits
262}
263
264/// Splits off one NUL-terminated field.
265fn take_field(bytes: &[u8]) -> Option<(&[u8], &[u8])> {
266 let end = bytes.iter().position(|byte| *byte == 0)?;
267
268 Some((&bytes[..end], &bytes[end + 1..]))
269}
270
271/// A matched line, shortened if it is absurd.
272fn cut(line: &str) -> String {
273 if line.chars().count() <= MAX_LINE_CHARS {
274 return line.to_owned();
275 }
276
277 let mut cut: String = line.chars().take(MAX_LINE_CHARS).collect();
278 cut.push('…');
279 cut
280}
281
282/// Parses git's output for a resolved commit.
283///
284/// The prefix is `{commit}:`, which git puts before every path when it is grepping a
285/// tree rather than a working copy. Passed rather than derived so the parser has no
286/// opinion about what a commit id looks like.
287pub fn parse_grep_output(stdout: &[u8], commit: &ObjectId, limit: usize) -> Vec<GrepHit> {
288 parse_grep(stdout, &format!("{}:", commit.as_str()), limit)
289}
290
291#[cfg(test)]
292mod tests {
293 use std::time::SystemTime;
294
295 use super::*;
296 use crate::{
297 domain::{
298 Membership, MembershipId, OrgId, Organization, RepoId, Repository, UserId, Visibility,
299 },
300 infrastructure::{
301 git::InMemoryGitQuery,
302 repository::{InMemoryMembershipRepo, InMemoryOrgRepo, InMemoryRepoRepo},
303 },
304 };
305
306 const COMMIT: &str = "a1b2c3d4e5f6a7b8c9d0e1f2a3b4c5d6e7f8a9b0";
307
308 fn commit() -> ObjectId {
309 ObjectId::new(COMMIT).expect("a valid object id")
310 }
311
312 /// Builds the bytes git writes: `<commit>:<path> NUL <line> NUL <column> NUL <text> LF`.
313 fn record(path: &str, line: u32, column: u32, text: &str) -> Vec<u8> {
314 let mut bytes = format!("{COMMIT}:{path}").into_bytes();
315 bytes.push(0);
316 bytes.extend_from_slice(line.to_string().as_bytes());
317 bytes.push(0);
318 bytes.extend_from_slice(column.to_string().as_bytes());
319 bytes.push(0);
320 bytes.extend_from_slice(text.as_bytes());
321 bytes.push(b'\n');
322 bytes
323 }
324
325 // --- parsing ------------------------------------------------------------------
326
327 #[test]
328 fn a_match_is_a_path_a_line_a_column_and_the_line_itself() {
329 let out = record("src/main.rs", 12, 5, " let needle = 1;");
330
331 assert_eq!(
332 parse_grep_output(&out, &commit(), 10),
333 vec![GrepHit {
334 path: RepoPath::new("src/main.rs").expect("valid"),
335 line: 12,
336 column: 5,
337 text: " let needle = 1;".to_owned(),
338 }]
339 );
340 }
341
342 #[test]
343 fn a_path_with_a_space_survives() {
344 // The reason the separator is a NUL rather than a colon: a name may contain
345 // almost anything, and splitting on punctuation misreads real repositories.
346 let mut out = record("docs/design notes.md", 3, 1, "needle");
347 out.extend(record("src/b.rs", 9, 2, "needle again"));
348
349 let hits = parse_grep_output(&out, &commit(), 10);
350
351 assert_eq!(hits.len(), 2);
352 assert_eq!(hits[0].path.as_str(), "docs/design notes.md");
353 assert_eq!(hits[1].path.as_str(), "src/b.rs");
354 }
355
356 #[test]
357 fn a_path_steid_cannot_address_is_left_out_of_the_results() {
358 // `RepoPath` refuses a colon, because git reads one as "revision:path" — so a
359 // file named that way cannot be browsed either. A result linking to a page that
360 // must 404 is worse than a result that is not there.
361 let out = record("src/a:b.rs", 9, 2, "needle");
362
363 assert_eq!(parse_grep_output(&out, &commit(), 10), Vec::new());
364 }
365
366 #[test]
367 fn a_line_containing_colons_is_carried_whole() {
368 let out = record("Cargo.toml", 4, 1, "url = \"https://example.com:8443/x\"");
369
370 let hits = parse_grep_output(&out, &commit(), 10);
371
372 assert_eq!(hits[0].text, "url = \"https://example.com:8443/x\"");
373 }
374
375 #[test]
376 fn a_binary_file_is_simply_absent() {
377 // `-I` means git never reports one, so there is nothing to skip here — this
378 // pins the expectation rather than the code: output from a repository full of
379 // binaries is output with no records in it.
380 assert_eq!(parse_grep_output(b"", &commit(), 10), Vec::new());
381 }
382
383 #[test]
384 fn a_record_for_another_commit_is_ignored() {
385 // Cannot happen from one grep, and if it ever did it would put a result under a
386 // revision the page is not showing — which would link to the wrong file.
387 let out = record("src/main.rs", 1, 1, "needle");
388
389 assert_eq!(
390 parse_grep_output(&out, &ObjectId::new("0".repeat(40)).expect("valid"), 10),
391 Vec::new()
392 );
393 }
394
395 #[test]
396 fn the_limit_stops_the_parse_rather_than_the_output() {
397 let mut out = Vec::new();
398 for line in 1..=10 {
399 out.extend(record("src/main.rs", line, 1, "needle"));
400 }
401
402 assert_eq!(parse_grep_output(&out, &commit(), 3).len(), 3);
403 }
404
405 #[test]
406 fn an_absurdly_long_line_is_cut() {
407 let long = "x".repeat(MAX_LINE_CHARS + 50);
408 let out = record("bundle.js", 1, 1, &long);
409
410 let hits = parse_grep_output(&out, &commit(), 10);
411
412 assert_eq!(hits[0].text.chars().count(), MAX_LINE_CHARS + 1);
413 assert!(hits[0].text.ends_with('…'));
414 }
415
416 #[test]
417 fn truncated_output_stops_where_it_stops() {
418 // A killed git can leave a half-written record. Half a result is better than an
419 // error page.
420 let mut out = record("src/main.rs", 1, 1, "needle");
421 out.extend_from_slice(format!("{COMMIT}:src/other.rs").as_bytes());
422
423 assert_eq!(parse_grep_output(&out, &commit(), 10).len(), 1);
424 }
425
426 #[test]
427 fn matches_are_grouped_by_file_in_gits_order() {
428 let mut out = record("src/a.rs", 1, 1, "needle");
429 out.extend(record("src/a.rs", 9, 1, "needle"));
430 out.extend(record("src/b.rs", 2, 1, "needle"));
431
432 let files = group_by_file(parse_grep_output(&out, &commit(), 10));
433
434 assert_eq!(files.len(), 2);
435 assert_eq!(files[0].path.as_str(), "src/a.rs");
436 assert_eq!(files[0].matches.len(), 2);
437 assert_eq!(files[1].matches.len(), 1);
438 }
439
440 // --- the use case -------------------------------------------------------------
441
442 struct Fixture {
443 orgs: InMemoryOrgRepo,
444 memberships: InMemoryMembershipRepo,
445 repos: InMemoryRepoRepo,
446 handle: OrgName,
447 owner: Actor,
448 stranger: Actor,
449 }
450
451 async fn fixture(visibility: Visibility) -> Fixture {
452 let orgs = InMemoryOrgRepo::new();
453 let memberships = InMemoryMembershipRepo::new();
454 let repos = InMemoryRepoRepo::new();
455
456 let org = Organization::new(OrgId::generate(), "acme", None).expect("valid org");
457 orgs.save(&org).await.expect("save org");
458
459 let owner = UserId::generate();
460 memberships
461 .save(&Membership::new(
462 MembershipId::generate(),
463 org.id.clone(),
464 owner.clone(),
465 crate::domain::Role::Owner,
466 ))
467 .await
468 .expect("save membership");
469
470 repos
471 .save(
472 &Repository::new(
473 RepoId::generate(),
474 org.id.clone(),
475 "steid",
476 None,
477 visibility,
478 SystemTime::now(),
479 )
480 .expect("valid repository"),
481 )
482 .await
483 .expect("save repo");
484
485 Fixture {
486 orgs,
487 memberships,
488 repos,
489 handle: org.name,
490 owner: Actor::User(owner),
491 stranger: Actor::Anonymous,
492 }
493 }
494
495 fn repo_name() -> RepoName {
496 RepoName::new("steid").expect("valid repository name")
497 }
498
499 impl Fixture {
500 async fn search(
501 &self,
502 actor: &Actor,
503 query: &str,
504 queries: &InMemoryGitQuery,
505 ) -> Result<Option<Searched>> {
506 search_repo(
507 &self.handle,
508 &repo_name(),
509 None,
510 query,
511 actor,
512 &self.orgs,
513 &self.memberships,
514 &self.repos,
515 queries,
516 )
517 .await
518 }
519 }
520
521 fn hit(path: &str, line: u32) -> GrepHit {
522 GrepHit {
523 path: RepoPath::new(path).expect("valid"),
524 line,
525 column: 1,
526 text: "needle".to_owned(),
527 }
528 }
529
530 #[tokio::test]
531 async fn a_search_comes_back_grouped_by_file() {
532 let f = fixture(Visibility::Public).await;
533 let queries = InMemoryGitQuery::new().with_grep_hits(vec![
534 hit("src/a.rs", 1),
535 hit("src/a.rs", 4),
536 hit("b.rs", 2),
537 ]);
538
539 let Some(Searched::Found(results)) = f.search(&f.owner, "needle", &queries).await.unwrap()
540 else {
541 panic!("expected results");
542 };
543
544 assert_eq!(results.matches, 3);
545 assert_eq!(results.files.len(), 2);
546 assert!(!results.truncated);
547 }
548
549 #[tokio::test]
550 async fn more_matches_than_the_cap_are_reported_as_truncated() {
551 let f = fixture(Visibility::Public).await;
552 let hits = (1..=(SEARCH_LIMIT as u32 + 1))
553 .map(|line| hit("src/a.rs", line))
554 .collect();
555 let queries = InMemoryGitQuery::new().with_grep_hits(hits);
556
557 let Some(Searched::Found(results)) = f.search(&f.owner, "needle", &queries).await.unwrap()
558 else {
559 panic!("expected results");
560 };
561
562 assert!(results.truncated);
563 assert_eq!(results.matches, SEARCH_LIMIT);
564 }
565
566 #[tokio::test]
567 async fn an_empty_query_searches_nothing_at_all() {
568 // Not one subprocess: `-F ""` matches every line of every file, so the opening
569 // state of the page must not reach git.
570 let f = fixture(Visibility::Public).await;
571 let queries = InMemoryGitQuery::new().with_grep_hits(vec![hit("src/a.rs", 1)]);
572
573 let Some(Searched::Found(results)) = f.search(&f.owner, " ", &queries).await.unwrap()
574 else {
575 panic!("expected results");
576 };
577
578 assert_eq!(results.query, "");
579 assert!(results.files.is_empty());
580 }
581
582 #[tokio::test]
583 async fn an_over_long_query_is_refused_rather_than_shortened() {
584 let f = fixture(Visibility::Public).await;
585 let query = "x".repeat(MAX_QUERY_BYTES + 1);
586
587 assert!(matches!(
588 f.search(&f.owner, &query, &InMemoryGitQuery::new())
589 .await
590 .unwrap(),
591 Some(Searched::QueryTooLong { .. })
592 ));
593 }
594
595 #[tokio::test]
596 async fn an_empty_repository_has_nothing_to_search() {
597 let f = fixture(Visibility::Public).await;
598
599 assert_eq!(
600 f.search(&f.owner, "needle", &InMemoryGitQuery::empty())
601 .await
602 .unwrap(),
603 Some(Searched::Empty)
604 );
605 }
606
607 #[tokio::test]
608 async fn a_timeout_is_a_state_rather_than_a_failure() {
609 let f = fixture(Visibility::Public).await;
610 let queries = InMemoryGitQuery::new().with_slow_grep();
611
612 assert!(matches!(
613 f.search(&f.owner, "needle", &queries).await.unwrap(),
614 Some(Searched::TimedOut { .. })
615 ));
616 }
617
618 #[tokio::test]
619 async fn a_private_repository_cannot_be_searched_by_a_stranger() {
620 // A search that ran would leak file contents a line at a time, which is a
621 // worse leak than the page it is refused on.
622 let f = fixture(Visibility::Private).await;
623 let queries = InMemoryGitQuery::new().with_grep_hits(vec![hit("secret.txt", 1)]);
624
625 assert!(
626 f.search(&f.stranger, "needle", &queries)
627 .await
628 .unwrap()
629 .is_none()
630 );
631 assert!(
632 f.search(&f.owner, "needle", &queries)
633 .await
634 .unwrap()
635 .is_some()
636 );
637 }
638}