Enum BasicStrategyKind

pub enum BasicStrategyKind {
    Linear,
    LinearReverse,
    Binary,
}

The possible strategies for searching the graph.

Variants

Linear

Search the nodes in the order that they were provided.

LinearReverse

Search the nodes in the reverse order that they were provided.

Binary

Conduct a binary search on the nodes by partitioning the nodes into two groups of approximately equal size.

TODO: Partitioning into groups of approximately equal size isn’t actually optimal for the DAG case. Really, we want to maximize the information that we gain from each test. The git bisect algorithm at https://git-scm.com/docs/git-bisect-lk2009#_bisection_algorithm_discussed discusses a metric to find the best partition for the subgraph which remains to be tested.

See also git-bisect’s skip algorithm: https://git-scm.com/docs/git-bisect-lk2009#_skip_algorithm. This does not use the same skip algorithm, and instead uses a deterministic approach. In order to solve the following problem:

sometimes the best bisection points all happened to be in an area where all the commits are untestable. And in this case the user was asked to test many untestable commits, which could be very inefficient.

We instead consider the hypothetical case that the node is a success, and yield further nodes as if it were a success, and then interleave those nodes with the hypothetical failure case.

Resources:

• https://git-scm.com/docs/git-bisect-lk2009#_bisection_algorithm_discussed
• https://byorgey.wordpress.com/2023/01/01/competitive-programming-in-haskell-better-binary-search/
• https://julesjacobs.com/notes/binarysearch/binarysearch.pdf

Trait Implementations

impl Clone for BasicStrategyKind

fn clone(&self) -> BasicStrategyKind

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BasicStrategyKind

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Hash for BasicStrategyKind

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl PartialEq for BasicStrategyKind

fn eq(&self, other: &BasicStrategyKind) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Copy for BasicStrategyKind

impl Eq for BasicStrategyKind

impl StructuralPartialEq for BasicStrategyKind