vendor/gix-revwalk/src/lib.rs

   1 //! Utility types for traversing the git commit-graph.
   2 //!
   3 //! This crate considers itself very much *plumbing* and is meant for consumption by other plumbing crates.
   4 #![deny(missing_docs, rust_2018_idioms)]
   5 #![forbid(unsafe_code)]
   6
   7 /// A graph of commits which additionally allows to associate data with commits.
   8 ///
   9 /// It starts empty, but each access may fill it with commit information.
  10 /// Note that the traversal can be accelerated if a [commit-graph][gix_commitgraph::Graph] is also made available.
  11 ///
  12 /// ### About replacements
  13 ///
  14 /// Object replacements is an object database feature to substitute one object with another. We assume that this is transparently
  15 /// implemented by the `find` function that returns objects. Also we assume that the commitgraph as been written with replacements
  16 /// active to provide a consistent view.
  17 ///
  18 /// ### Odb or `find` configuration
  19 ///
  20 /// The `find` handle should be setup to *quickly determine if an object exists or not* to assure quick operation *on shallow repositories*.
  21 /// This typically means that it should not re-read the odb if there is an object miss.
  22 ///
  23 /// Most usage of the Graph will benefit from fast ODB lookups, so setting up an object cache will be beneficial. If that's not the case,
  24 /// the method docs will inform about that.
  25 ///
  26 /// Additionally, and only if `T` is [`Commit<T>`][graph::Commit], there is *no need for an object cache* as we keep track of
  27 /// everything related to commit traversal in our own hashmap.
  28 pub struct Graph<'find, T> {
  29     /// A way to resolve a commit from the object database.
  30     find: Box<graph::FindFn<'find>>,
  31     /// A way to speedup commit access, essentially a multi-file commit database.
  32     cache: Option<gix_commitgraph::Graph>,
  33     /// The set of cached commits that we have seen once, along with data associated with them.
  34     map: graph::IdMap<T>,
  35     /// A buffer for writing commit data into.
  36     buf: Vec<u8>,
  37     /// Another buffer we typically use to store parents.
  38     parent_buf: Vec<u8>,
  39 }
  40
  41 ///
  42 pub mod graph;
  43
  44 /// A utility type implementing a queue which can be used to automatically sort data by its time in ascending order.
  45 ///
  46 /// Note that the performance of this queue is very relevant to overall algorithm performance of many graph-walking algorithms,
  47 /// and as it stands our implementation is about 6% slower in practice, probably also depending on the size of the stored data.
  48 #[derive(Default)]
  49 pub struct PriorityQueue<K: Ord, T>(std::collections::BinaryHeap<queue::Item<K, T>>);
  50 mod queue;