Initial commit

4 files changed, 843 insertions, 0 deletions

diff --git a/LICENSES/EUPL-1.2.txt b/LICENSES/EUPL-1.2.txt
new file mode 100644
index 0000000..4153cd3
--- /dev/null
+++ b/LICENSES/EUPL-1.2.txt
@@ -0,0 +1,287 @@
+                      EUROPEAN UNION PUBLIC LICENCE v. 1.2
+                      EUPL © the European Union 2007, 2016
+
+This European Union Public Licence (the ‘EUPL’) applies to the Work (as defined
+below) which is provided under the terms of this Licence. Any use of the Work,
+other than as authorised under this Licence is prohibited (to the extent such
+use is covered by a right of the copyright holder of the Work).
+
+The Work is provided under the terms of this Licence when the Licensor (as
+defined below) has placed the following notice immediately following the
+copyright notice for the Work:
+
+        Licensed under the EUPL
+
+or has expressed by any other means his willingness to license under the EUPL.
+
+1. Definitions
+
+In this Licence, the following terms have the following meaning:
+
+- ‘The Licence’: this Licence.
+
+- ‘The Original Work’: the work or software distributed or communicated by the
+  Licensor under this Licence, available as Source Code and also as Executable
+  Code as the case may be.
+
+- ‘Derivative Works’: the works or software that could be created by the
+  Licensee, based upon the Original Work or modifications thereof. This Licence
+  does not define the extent of modification or dependence on the Original Work
+  required in order to classify a work as a Derivative Work; this extent is
+  determined by copyright law applicable in the country mentioned in Article 15.
+
+- ‘The Work’: the Original Work or its Derivative Works.
+
+- ‘The Source Code’: the human-readable form of the Work which is the most
+  convenient for people to study and modify.
+
+- ‘The Executable Code’: any code which has generally been compiled and which is
+  meant to be interpreted by a computer as a program.
+
+- ‘The Licensor’: the natural or legal person that distributes or communicates
+  the Work under the Licence.
+
+- ‘Contributor(s)’: any natural or legal person who modifies the Work under the
+  Licence, or otherwise contributes to the creation of a Derivative Work.
+
+- ‘The Licensee’ or ‘You’: any natural or legal person who makes any usage of
+  the Work under the terms of the Licence.
+
+- ‘Distribution’ or ‘Communication’: any act of selling, giving, lending,
+  renting, distributing, communicating, transmitting, or otherwise making
+  available, online or offline, copies of the Work or providing access to its
+  essential functionalities at the disposal of any other natural or legal
+  person.
+
+2. Scope of the rights granted by the Licence
+
+The Licensor hereby grants You a worldwide, royalty-free, non-exclusive,
+sublicensable licence to do the following, for the duration of copyright vested
+in the Original Work:
+
+- use the Work in any circumstance and for all usage,
+- reproduce the Work,
+- modify the Work, and make Derivative Works based upon the Work,
+- communicate to the public, including the right to make available or display
+  the Work or copies thereof to the public and perform publicly, as the case may
+  be, the Work,
+- distribute the Work or copies thereof,
+- lend and rent the Work or copies thereof,
+- sublicense rights in the Work or copies thereof.
+
+Those rights can be exercised on any media, supports and formats, whether now
+known or later invented, as far as the applicable law permits so.
+
+In the countries where moral rights apply, the Licensor waives his right to
+exercise his moral right to the extent allowed by law in order to make effective
+the licence of the economic rights here above listed.
+
+The Licensor grants to the Licensee royalty-free, non-exclusive usage rights to
+any patents held by the Licensor, to the extent necessary to make use of the
+rights granted on the Work under this Licence.
+
+3. Communication of the Source Code
+
+The Licensor may provide the Work either in its Source Code form, or as
+Executable Code. If the Work is provided as Executable Code, the Licensor
+provides in addition a machine-readable copy of the Source Code of the Work
+along with each copy of the Work that the Licensor distributes or indicates, in
+a notice following the copyright notice attached to the Work, a repository where
+the Source Code is easily and freely accessible for as long as the Licensor
+continues to distribute or communicate the Work.
+
+4. Limitations on copyright
+
+Nothing in this Licence is intended to deprive the Licensee of the benefits from
+any exception or limitation to the exclusive rights of the rights owners in the
+Work, of the exhaustion of those rights or of other applicable limitations
+thereto.
+
+5. Obligations of the Licensee
+
+The grant of the rights mentioned above is subject to some restrictions and
+obligations imposed on the Licensee. Those obligations are the following:
+
+Attribution right: The Licensee shall keep intact all copyright, patent or
+trademarks notices and all notices that refer to the Licence and to the
+disclaimer of warranties. The Licensee must include a copy of such notices and a
+copy of the Licence with every copy of the Work he/she distributes or
+communicates. The Licensee must cause any Derivative Work to carry prominent
+notices stating that the Work has been modified and the date of modification.
+
+Copyleft clause: If the Licensee distributes or communicates copies of the
+Original Works or Derivative Works, this Distribution or Communication will be
+done under the terms of this Licence or of a later version of this Licence
+unless the Original Work is expressly distributed only under this version of the
+Licence — for example by communicating ‘EUPL v. 1.2 only’. The Licensee
+(becoming Licensor) cannot offer or impose any additional terms or conditions on
+the Work or Derivative Work that alter or restrict the terms of the Licence.
+
+Compatibility clause: If the Licensee Distributes or Communicates Derivative
+Works or copies thereof based upon both the Work and another work licensed under
+a Compatible Licence, this Distribution or Communication can be done under the
+terms of this Compatible Licence. For the sake of this clause, ‘Compatible
+Licence’ refers to the licences listed in the appendix attached to this Licence.
+Should the Licensee's obligations under the Compatible Licence conflict with
+his/her obligations under this Licence, the obligations of the Compatible
+Licence shall prevail.
+
+Provision of Source Code: When distributing or communicating copies of the Work,
+the Licensee will provide a machine-readable copy of the Source Code or indicate
+a repository where this Source will be easily and freely available for as long
+as the Licensee continues to distribute or communicate the Work.
+
+Legal Protection: This Licence does not grant permission to use the trade names,
+trademarks, service marks, or names of the Licensor, except as required for
+reasonable and customary use in describing the origin of the Work and
+reproducing the content of the copyright notice.
+
+6. Chain of Authorship
+
+The original Licensor warrants that the copyright in the Original Work granted
+hereunder is owned by him/her or licensed to him/her and that he/she has the
+power and authority to grant the Licence.
+
+Each Contributor warrants that the copyright in the modifications he/she brings
+to the Work are owned by him/her or licensed to him/her and that he/she has the
+power and authority to grant the Licence.
+
+Each time You accept the Licence, the original Licensor and subsequent
+Contributors grant You a licence to their contributions to the Work, under the
+terms of this Licence.
+
+7. Disclaimer of Warranty
+
+The Work is a work in progress, which is continuously improved by numerous
+Contributors. It is not a finished work and may therefore contain defects or
+‘bugs’ inherent to this type of development.
+
+For the above reason, the Work is provided under the Licence on an ‘as is’ basis
+and without warranties of any kind concerning the Work, including without
+limitation merchantability, fitness for a particular purpose, absence of defects
+or errors, accuracy, non-infringement of intellectual property rights other than
+copyright as stated in Article 6 of this Licence.
+
+This disclaimer of warranty is an essential part of the Licence and a condition
+for the grant of any rights to the Work.
+
+8. Disclaimer of Liability
+
+Except in the cases of wilful misconduct or damages directly caused to natural
+persons, the Licensor will in no event be liable for any direct or indirect,
+material or moral, damages of any kind, arising out of the Licence or of the use
+of the Work, including without limitation, damages for loss of goodwill, work
+stoppage, computer failure or malfunction, loss of data or any commercial
+damage, even if the Licensor has been advised of the possibility of such damage.
+However, the Licensor will be liable under statutory product liability laws as
+far such laws apply to the Work.
+
+9. Additional agreements
+
+While distributing the Work, You may choose to conclude an additional agreement,
+defining obligations or services consistent with this Licence. However, if
+accepting obligations, You may act only on your own behalf and on your sole
+responsibility, not on behalf of the original Licensor or any other Contributor,
+and only if You agree to indemnify, defend, and hold each Contributor harmless
+for any liability incurred by, or claims asserted against such Contributor by
+the fact You have accepted any warranty or additional liability.
+
+10. Acceptance of the Licence
+
+The provisions of this Licence can be accepted by clicking on an icon ‘I agree’
+placed under the bottom of a window displaying the text of this Licence or by
+affirming consent in any other similar way, in accordance with the rules of
+applicable law. Clicking on that icon indicates your clear and irrevocable
+acceptance of this Licence and all of its terms and conditions.
+
+Similarly, you irrevocably accept this Licence and all of its terms and
+conditions by exercising any rights granted to You by Article 2 of this Licence,
+such as the use of the Work, the creation by You of a Derivative Work or the
+Distribution or Communication by You of the Work or copies thereof.
+
+11. Information to the public
+
+In case of any Distribution or Communication of the Work by means of electronic
+communication by You (for example, by offering to download the Work from a
+remote location) the distribution channel or media (for example, a website) must
+at least provide to the public the information requested by the applicable law
+regarding the Licensor, the Licence and the way it may be accessible, concluded,
+stored and reproduced by the Licensee.
+
+12. Termination of the Licence
+
+The Licence and the rights granted hereunder will terminate automatically upon
+any breach by the Licensee of the terms of the Licence.
+
+Such a termination will not terminate the licences of any person who has
+received the Work from the Licensee under the Licence, provided such persons
+remain in full compliance with the Licence.
+
+13. Miscellaneous
+
+Without prejudice of Article 9 above, the Licence represents the complete
+agreement between the Parties as to the Work.
+
+If any provision of the Licence is invalid or unenforceable under applicable
+law, this will not affect the validity or enforceability of the Licence as a
+whole. Such provision will be construed or reformed so as necessary to make it
+valid and enforceable.
+
+The European Commission may publish other linguistic versions or new versions of
+this Licence or updated versions of the Appendix, so far this is required and
+reasonable, without reducing the scope of the rights granted by the Licence. New
+versions of the Licence will be published with a unique version number.
+
+All linguistic versions of this Licence, approved by the European Commission,
+have identical value. Parties can take advantage of the linguistic version of
+their choice.
+
+14. Jurisdiction
+
+Without prejudice to specific agreement between parties,
+
+- any litigation resulting from the interpretation of this License, arising
+  between the European Union institutions, bodies, offices or agencies, as a
+  Licensor, and any Licensee, will be subject to the jurisdiction of the Court
+  of Justice of the European Union, as laid down in article 272 of the Treaty on
+  the Functioning of the European Union,
+
+- any litigation arising between other parties and resulting from the
+  interpretation of this License, will be subject to the exclusive jurisdiction
+  of the competent court where the Licensor resides or conducts its primary
+  business.
+
+15. Applicable Law
+
+Without prejudice to specific agreement between parties,
+
+- this Licence shall be governed by the law of the European Union Member State
+  where the Licensor has his seat, resides or has his registered office,
+
+- this licence shall be governed by Belgian law if the Licensor has no seat,
+  residence or registered office inside a European Union Member State.
+
+Appendix
+
+‘Compatible Licences’ according to Article 5 EUPL are:
+
+- GNU General Public License (GPL) v. 2, v. 3
+- GNU Affero General Public License (AGPL) v. 3
+- Open Software License (OSL) v. 2.1, v. 3.0
+- Eclipse Public License (EPL) v. 1.0
+- CeCILL v. 2.0, v. 2.1
+- Mozilla Public Licence (MPL) v. 2
+- GNU Lesser General Public Licence (LGPL) v. 2.1, v. 3
+- Creative Commons Attribution-ShareAlike v. 3.0 Unported (CC BY-SA 3.0) for
+  works other than software
+- European Union Public Licence (EUPL) v. 1.1, v. 1.2
+- Québec Free and Open-Source Licence — Reciprocity (LiLiQ-R) or Strong
+  Reciprocity (LiLiQ-R+).
+
+The European Commission may update this Appendix to later versions of the above
+licences without producing a new version of the EUPL, as long as they provide
+the rights granted in Article 2 of this Licence and protect the covered Source
+Code from exclusive appropriation.
+
+All other changes or additions to this Appendix require the production of a new
+EUPL version.
diff --git a/hydrasect-search.rs b/hydrasect-search.rs
new file mode 100644
index 0000000..751005e
--- /dev/null
+++ b/hydrasect-search.rs
@@ -0,0 +1,526 @@
+// SPDX-FileCopyrightText: 2022 Alyssa Ross <hi@alyssa.is>
+// SPDX-License-Identifier: EUPL-1.2
+
+use std::cmp::min;
+use std::collections::{BTreeMap, BTreeSet};
+use std::env;
+use std::ffi::OsStr;
+use std::fmt::{self, Debug, Display, Formatter};
+use std::fs::{create_dir_all, rename, File};
+use std::io::{self, BufRead, BufReader, ErrorKind, Read, Seek, SeekFrom};
+use std::os::unix::prelude::*;
+use std::path::{Path, PathBuf};
+use std::process::{Command, ExitStatus, Stdio};
+use std::str;
+use std::time::{Duration, SystemTime};
+
+struct OidParseError([u8; 2]);
+
+impl Display for OidParseError {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        let s = String::from_utf8_lossy(&self.0);
+        write!(f, "{:?} cannot be parsed as an octet", s)
+    }
+}
+
+#[test]
+fn test_oid_parse_error_to_string() {
+    let actual = OidParseError([b'g', b'h']).to_string();
+    assert_eq!(actual, r#""gh" cannot be parsed as an octet"#);
+}
+
+impl Debug for OidParseError {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        write!(f, "OidParseError({:?})", String::from_utf8_lossy(&self.0))
+    }
+}
+
+#[test]
+fn test_oid_parse_error_debug() {
+    let actual = format!("{:?}", OidParseError([b'g', b'h']));
+    assert_eq!(actual, r#"OidParseError("gh")"#);
+}
+
+#[derive(Clone, Eq, Ord, PartialEq, PartialOrd)]
+struct Oid(Vec<u8>);
+
+impl Oid {
+    fn parse(bytes: &[u8]) -> Result<Self, OidParseError> {
+        let inner = bytes
+            .chunks(2)
+            .map(|pair| {
+                str::from_utf8(pair)
+                    .ok()
+                    .and_then(|s| u8::from_str_radix(s, 16).ok())
+                    .ok_or(OidParseError([pair[0], pair[1]]))
+            })
+            .collect::<Result<_, _>>()?;
+
+        Ok(Self(inner))
+    }
+}
+
+impl Display for Oid {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        for byte in &self.0 {
+            write!(f, "{:02x}", byte)?;
+        }
+        Ok(())
+    }
+}
+
+#[test]
+fn test_oid_display() {
+    let oid = Oid::parse(b"0011f9065a1ad1da4db67bec8d535d91b0a78fba").unwrap();
+    assert_eq!(oid.to_string(), "0011f9065a1ad1da4db67bec8d535d91b0a78fba");
+}
+
+impl Debug for Oid {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        write!(f, "Oid({})", self)
+    }
+}
+
+#[test]
+fn test_oid_debug() {
+    let oid = Oid::parse(b"0011f9065a1ad1da4db67bec8d535d91b0a78fba").unwrap();
+    let debug = format!("{:?}", oid);
+    assert_eq!(debug, "Oid(0011f9065a1ad1da4db67bec8d535d91b0a78fba)");
+}
+
+#[derive(Debug, Eq, PartialEq)]
+struct Commit {
+    parents: BTreeSet<Oid>,
+    children: BTreeSet<Oid>,
+}
+
+fn commit_graph(input: impl BufRead) -> Result<BTreeMap<Oid, Commit>, String> {
+    fn parse_oid(s: &[u8]) -> Result<Oid, String> {
+        Oid::parse(s).map_err(|e| e.to_string())
+    }
+
+    let dag = input
+        .split(b'\n')
+        .map(|line| {
+            let line = line.map_err(|e| format!("reading commit graph: {}", e))?;
+            let mut fields = line.split(|b| *b == b' ');
+            let oid = fields.next().ok_or_else(|| "empty line".to_string())?;
+            let parents = fields.map(parse_oid).collect::<Result<_, _>>()?;
+            Ok((parse_oid(oid)?, parents))
+        })
+        .collect::<Result<BTreeMap<_, BTreeSet<_>>, String>>()?;
+
+    // Create a mapping from parent commits to their children.
+    let mut paternities = BTreeMap::<_, BTreeSet<_>>::new();
+    for (oid, parents) in &dag {
+        for parent in parents {
+            paternities
+                .entry(parent.clone())
+                .or_default()
+                .insert(oid.clone());
+        }
+    }
+
+    let considered_oids: BTreeSet<_> = dag.keys().map(Clone::clone).collect();
+
+    let undirected_graph = dag
+        .into_iter()
+        .map(|(oid, parents)| {
+            let commit = Commit {
+                parents: parents
+                    .intersection(&considered_oids)
+                    .map(Clone::clone)
+                    .collect(),
+                children: paternities.remove(&oid).unwrap_or_default(),
+            };
+            (oid, commit)
+        })
+        .collect();
+
+    Ok(undirected_graph)
+}
+
+#[test]
+fn test_commit_graph() {
+    assert_eq!(
+        commit_graph(&*b"AA BB CC\nCC DD\n".to_vec()).unwrap(),
+        vec![
+            (
+                Oid::parse(b"AA").unwrap(),
+                Commit {
+                    parents: [b"CC"]
+                        .into_iter()
+                        .map(|o| Oid::parse(o).unwrap())
+                        .collect(),
+                    children: BTreeSet::new(),
+                }
+            ),
+            (
+                Oid::parse(b"CC").unwrap(),
+                Commit {
+                    parents: BTreeSet::new(),
+                    children: [Oid::parse(b"AA").unwrap()].into_iter().collect(),
+                }
+            ),
+        ]
+        .into_iter()
+        .collect()
+    );
+}
+
+fn status_to_result(status: ExitStatus, name: &'static str) -> Result<(), String> {
+    if let Some(signal) = status.signal() {
+        return Err(format!("{} killed by signal {}", name, signal));
+    }
+    if !status.success() {
+        return Err(format!("{} exited {}", name, status.code().unwrap()));
+    }
+    Ok(())
+}
+
+fn bisect_graph() -> Result<BTreeMap<Oid, Commit>, String> {
+    let mut child = Command::new("git")
+        .args(&["log", "--format=%H %P", "--bisect"])
+        .stdout(Stdio::piped())
+        .spawn()
+        .map_err(|e| format!("failed to spawn git log: {}", e))?;
+
+    let graph_result = commit_graph(BufReader::new(child.stdout.take().unwrap()));
+
+    let status = child
+        .wait()
+        .map_err(|e| format!("waiting for git: {}", e))?;
+    status_to_result(status, "git log")?;
+
+    graph_result.map_err(|e| format!("parsing git log output: {}", e))
+}
+
+fn parse_history_line(line: Vec<u8>) -> Oid {
+    let oid_str = line
+        .into_iter()
+        .take_while(u8::is_ascii_hexdigit)
+        .collect::<Vec<_>>();
+    Oid::parse(&oid_str).unwrap()
+}
+
+fn read_history(input: impl BufRead) -> io::Result<BTreeSet<Oid>> {
+    input
+        .split(b'\n')
+        .map(|line| Ok(parse_history_line(line?)))
+        .collect()
+}
+
+#[test]
+fn test_read_history() {
+    let input = b"0011f9065a1ad1da4db67bec8d535d91b0a78fba 1496527122\n\
+                  0d4431cfe90b2242723ccb1ccc90714f2f68a609 1497692199\n";
+    let expected = [
+        b"0011f9065a1ad1da4db67bec8d535d91b0a78fba",
+        b"0d4431cfe90b2242723ccb1ccc90714f2f68a609",
+    ]
+    .into_iter()
+    .map(|o| Oid::parse(o).unwrap())
+    .collect();
+    assert_eq!(read_history(&*input.to_vec()).unwrap(), expected);
+}
+
+fn closest_commits(
+    start: Oid,
+    graph: BTreeMap<Oid, Commit>,
+    targets: BTreeSet<Oid>,
+) -> BTreeSet<Oid> {
+    let mut candidates: BTreeSet<_> = [start].into_iter().collect();
+    let mut checked = BTreeSet::<Oid>::new();
+
+    loop {
+        if candidates.is_empty() {
+            return candidates;
+        }
+
+        let matches: BTreeSet<_> = candidates
+            .intersection(&targets)
+            .map(Clone::clone)
+            .collect();
+        if !matches.is_empty() {
+            return matches;
+        }
+
+        let new_candidates = candidates
+            .iter()
+            .flat_map(|candidate| {
+                let commit = graph.get(&candidate).unwrap();
+                commit.children.union(&commit.parents)
+            })
+            .map(Clone::clone)
+            .collect::<BTreeSet<_>>()
+            .difference(&checked)
+            .map(Clone::clone)
+            .collect();
+        checked.append(&mut candidates);
+        candidates = new_candidates;
+    }
+}
+
+#[test]
+fn test_closest_commits() {
+    let graph = b"AA BB\n\
+                  BB CC\n\
+                  CC DD EE\n\
+                  EE FF\n\
+                  FF 00";
+    let history = read_history(&*b"AA 0\nFF 0\n00 0\n".to_vec()).unwrap();
+    let graph = commit_graph(&*graph.to_vec()).unwrap();
+
+    let actual = closest_commits(Oid::parse(b"CC").unwrap(), graph, history);
+    let expected = [b"AA", b"FF"]
+        .into_iter()
+        .map(|o| Oid::parse(o).unwrap())
+        .collect();
+
+    assert_eq!(actual, expected);
+}
+
+fn git_rev_parse(commit: impl AsRef<OsStr>) -> Result<Oid, String> {
+    let out = Command::new("git")
+        .arg("rev-parse")
+        .arg(commit)
+        .stderr(Stdio::inherit())
+        .output()
+        .map_err(|e| format!("spawning git: {}", e))?;
+    status_to_result(out.status, "git rev-parse")?;
+    let mut stdout = out.stdout;
+    stdout.pop();
+    Oid::parse(&stdout).map_err(|e| format!("parsing git rev-parse output: {}", e))
+}
+
+fn last_line(reader: &mut (impl Read + Seek)) -> io::Result<Vec<u8>> {
+    let mut buf = vec![0; 4096];
+    // Skip an extra character the first time to avoid considering a
+    // trailing newline.
+    let mut from_end = buf.len() as i64 + 1;
+
+    loop {
+        match reader.seek(SeekFrom::End(-from_end)) {
+            // EINVAL means we tried to seek to before the beginning.
+            Err(e) if e.kind() == ErrorKind::InvalidInput => {
+                // Avoid trying to read past the end, for the case
+                // where the file is smaller than buf.
+                let file_len = reader.seek(SeekFrom::End(0))? as usize;
+                buf.resize(min(file_len, buf.len()), 0);
+
+                // Clamp our position to the start of the file.
+                reader.rewind()?;
+            }
+            r => {
+                r?;
+            }
+        }
+
+        reader.read_exact(&mut buf)?;
+
+        // Rewind to one character after the last newline we found, if any.
+        if let Some(i) = buf.iter().rposition(|b| b == &b'\n') {
+            reader.seek(SeekFrom::Current(-(buf.len() as i64) + i as i64 + 1))?;
+            break;
+        }
+
+        // If we're at the start of the stream, this is the only line
+        // in the file, and we're done.
+        if reader.stream_position()? as usize - buf.len() == 0 {
+            reader.rewind()?;
+            break;
+        }
+
+        from_end += buf.len() as i64;
+    }
+
+    buf.resize(0, 0);
+    reader.read_to_end(&mut buf)?;
+
+    if buf.last() == Some(&b'\n') {
+        buf.pop();
+    }
+
+    Ok(buf)
+}
+
+#[cfg(test)]
+fn tmpfile() -> io::Result<File> {
+    use std::os::raw::c_int;
+
+    extern "C" {
+        fn tmpfd() -> c_int;
+    }
+
+    let fd = unsafe { tmpfd() };
+    if fd == -1 {
+        return Err(io::Error::last_os_error());
+    }
+    unsafe { Ok(File::from_raw_fd(fd)) }
+}
+
+#[test]
+fn test_last_line_empty() {
+    let mut file = tmpfile().unwrap();
+    let line = last_line(&mut file).unwrap();
+    assert!(line.is_empty());
+}
+
+#[test]
+fn test_last_line_first() {
+    use std::io::{Seek, Write};
+
+    let len = 4096 * 3;
+    let mut data = vec![b'a'; len];
+    *data.last_mut().unwrap() = b'\n';
+
+    let mut file = tmpfile().unwrap();
+    file.write_all(&data).unwrap();
+    file.rewind().unwrap();
+
+    let line = last_line(&mut file).unwrap();
+    assert_eq!(data[..(len - 1)], line);
+}
+
+#[test]
+fn test_last_line_short() {
+    use std::io::{Seek, Write};
+
+    let len = 1024;
+    let mut data = vec![b'a'; len];
+    data[len - 10] = b'\n';
+    data[len - 9] = b'b';
+
+    let mut file = tmpfile().unwrap();
+    file.write_all(&data).unwrap();
+    file.rewind().unwrap();
+
+    let line = last_line(&mut file).unwrap();
+    assert_eq!(data[(len - 9)..], line);
+}
+
+#[test]
+fn test_last_line_long() {
+    use std::io::{Seek, Write};
+
+    let len = 4096 * 3;
+    let mut data = vec![b'a'; len];
+    *data.last_mut().unwrap() = b'\n';
+    data[len / 2] = b'\n';
+    data[len / 2 + 1] = b'b';
+
+    let mut file = tmpfile().unwrap();
+    file.write_all(&data).unwrap();
+    file.rewind().unwrap();
+
+    let line = last_line(&mut file).unwrap();
+    assert_eq!(data[(len / 2 + 1)..(len - 1)], line);
+}
+
+fn git_is_ancestor(lhs: &dyn AsRef<OsStr>, rhs: &dyn AsRef<OsStr>) -> Result<bool, String> {
+    let status = Command::new("git")
+        .args(&["merge-base", "--is-ancestor"])
+        .arg(lhs)
+        .arg(rhs)
+        .status()
+        .map_err(|e| format!("spawning git merge-base --is-ancestor: {}", e))?;
+
+    if status.code() == Some(1) {
+        return Ok(false);
+    }
+    status_to_result(status, "git merge-base --is-ancestor")?;
+    Ok(true)
+}
+
+fn update_history_file(path: &Path) -> Result<File, String> {
+    if let Some(parent) = path.parent() {
+        let _ = create_dir_all(parent);
+    }
+
+    let tmp_path = path.with_extension("tmp");
+
+    let status = Command::new("curl")
+        .arg("-fLsSo")
+        .arg(&tmp_path)
+        .arg("-z")
+        .arg(path)
+        .arg("https://channels.nix.gsc.io/nixpkgs-unstable/history")
+        .status()
+        .map_err(|e| format!("spawning curl: {}", e))?;
+
+    if let Some(code) = status.code() {
+        if code > 4 && code != 48 {
+            eprintln!("Warning: failed to update the Hydra evaluation history file.");
+        }
+    }
+    status_to_result(status, "curl")?;
+
+    match rename(&tmp_path, path) {
+        // If the source file doesn't exist, we got a 304 Not Modified,
+        // so the existing file is up to date.
+        Err(e) if e.kind() == ErrorKind::NotFound => Ok(()),
+        r => r.map_err(|e| format!("moving new history file into place: {}", e)),
+    }?;
+
+    File::open(&path).map_err(|e| format!("opening updated history file: {}", e))
+}
+
+fn open_history_file() -> Result<File, String> {
+    let mut path: PathBuf = match env::var_os("XDG_CACHE_HOME") {
+        Some(v) if !v.is_empty() => v.into(),
+        _ => match env::var_os("HOME") {
+            Some(v) if !v.is_empty() => {
+                let mut path_buf = PathBuf::from(v);
+                path_buf.push(".cache");
+                path_buf
+            }
+            _ => {
+                return Err("XDG_CACHE_HOME and HOME are both unset or empty".to_string());
+            }
+        },
+    };
+    path.push("hydrasect/hydra-eval-history");
+
+    let mut file = match File::open(&path) {
+        Ok(f) => f,
+        Err(e) if e.kind() == ErrorKind::NotFound => {
+            return update_history_file(&path).map_err(|e| format!("updating history file: {}", e))
+        }
+        Err(e) => {
+            return Err(format!("opening history file: {}", e));
+        }
+    };
+
+    let most_recent_eval = last_line(&mut file)
+        .map(parse_history_line)
+        .map_err(|e| format!("reading last line of history file: {}", e))?;
+    file.rewind().unwrap();
+
+    if !git_is_ancestor(&"refs/bisect/bad", &most_recent_eval.to_string())
+        .map_err(|e| format!("checking history freshness: {}", e))?
+    {
+        let mtime = file
+            .metadata()
+            .map_err(|e| format!("checking history file metadata: {}", e))?
+            .modified()
+            .map_err(|e| format!("checking history file modified date: {}", e))?;
+        if SystemTime::now()
+            .duration_since(mtime)
+            .map_err(|e| format!("checking time since history file modification: {}", e))?
+            > Duration::from_secs(15 * 60)
+        {
+            file = update_history_file(&path)?;
+        }
+    }
+
+    Ok(file)
+}
+
+fn main() {
+    let history = read_history(BufReader::new(open_history_file().unwrap())).unwrap();
+    let head = git_rev_parse("HEAD").unwrap();
+
+    for commit in closest_commits(head, bisect_graph().unwrap(), history) {
+        println!("{}", commit);
+    }
+}
diff --git a/meson.build b/meson.build
new file mode 100644
index 0000000..54677a8
--- /dev/null
+++ b/meson.build
@@ -0,0 +1,13 @@
+# SPDX-FileCopyrightText: 2022 Alyssa Ross <hi@alyssa.is>
+# SPDX-License-Identifier: EUPL-1.2
+
+project('hydrasect', 'rust', 'c',
+  default_options : ['rust_std=2021', 'warning_level=3'])
+
+c_lib = static_library('hydrasect', 'tmpfd.c')
+
+executable('hydrasect-search', 'hydrasect-search.rs', install : true)
+
+test('Rust unit tests', executable('hydrasect-search-test', 'hydrasect-search.rs',
+  link_with : c_lib,
+  rust_args : '--test'))
diff --git a/tmpfd.c b/tmpfd.c
new file mode 100644
index 0000000..193fa90
--- /dev/null
+++ b/tmpfd.c
@@ -0,0 +1,17 @@
+// SPDX-FileCopyrightText: 2022 Alyssa Ross <hi@alyssa.is>
+// SPDX-License-Identifier: EUPL-1.2
+
+#include <stdio.h>
+#include <unistd.h>
+
+int tmpfd(void)
+{
+	int fd = -1;
+	FILE *f = tmpfile();
+	if (!f)
+		return -1;
+	if ((fd = fileno(f)) != -1)
+		fd = dup(fd);
+	fclose(f);
+	return fd;
+}