#![stable(feature = "rust1", since = "1.0.0")]

use crate::cmp::Ordering::{self, Equal, Greater, Less};

use crate::intrinsics::{exact_div, unchecked_sub};

use crate::intrinsics::{exact_div, select_unpredictable, unchecked_sub};

use crate::mem::{self, SizedTypeProperties};

use crate::num::NonZero;

use crate::ops::{Bound, OneSidedRange, Range, RangeBounds};

where

F: FnMut(&'a T) -> Ordering,

{

// INVARIANTS:

// - 0 <= left <= left + size = right <= self.len()

// - f returns Less for everything in self[..left]

// - f returns Greater for everything in self[right..]

let mut size = self.len();

let mut left = 0;

let mut right = size;

while left < right {

let mid = left + size / 2;

// SAFETY: the while condition means `size` is strictly positive, so

// `size/2 < size`. Thus `left + size/2 < left + size`, which

// coupled with the `left + size <= self.len()` invariant means

// we have `left + size/2 < self.len()`, and this is in-bounds.

if size == 0 {

return Err(0);

}

let mut base = 0usize;

// This loop intentionally doesn't have an early exit if the comparison

// returns Equal. We want the number of loop iterations to depend *only*

// on the size of the input slice so that the CPU can reliably predict

// the loop count.

while size > 1 {

let half = size / 2;

let mid = base + half;

// SAFETY: the call is made safe by the following inconstants:

// - `mid >= 0`: by definition

// - `mid < size`: `mid = size / 2 + size / 4 + size / 8 ...`

let cmp = f(unsafe { self.get_unchecked(mid) });

// This control flow produces conditional moves, which results in

// fewer branches and instructions than if/else or matching on

// cmp::Ordering.

// This is x86 asm for u8: https://rust.godbolt.org/z/698eYffTx.

left = if cmp == Less { mid + 1 } else { left };

right = if cmp == Greater { mid } else { right };

if cmp == Equal {

// SAFETY: same as the `get_unchecked` above

unsafe { hint::assert_unchecked(mid < self.len()) };

return Ok(mid);

}

size = right - left;

// Binary search interacts poorly with branch prediction, so force

// the compiler to use conditional moves if supported by the target

// architecture.

base = select_unpredictable(cmp == Greater, base, mid);

// This is imprecise in the case where `size` is odd and the

// comparison returns Greater: the mid element still gets included

// by `size` even though it's known to be larger than the element

// being searched for.

//

// This is fine though: we gain more performance by keeping the

// loop iteration count invariant (and thus predictable) than we

// lose from considering one additional element.

size -= half;

}

// SAFETY: directly true from the overall invariant.

// Note that this is `<=`, unlike the assume in the `Ok` path.

unsafe { hint::assert_unchecked(left <= self.len()) };

Err(left)

// SAFETY: base is always in [0, size) because base <= mid.

let cmp = f(unsafe { self.get_unchecked(base) });

if cmp == Equal {

// SAFETY: same as the `get_unchecked` above.

unsafe { hint::assert_unchecked(base < self.len()) };

Ok(base)

} else {

let result = base + (cmp == Less) as usize;

// SAFETY: same as the `get_unchecked` above.

// Note that this is `<=`, unlike the assume in the `Ok` path.

unsafe { hint::assert_unchecked(result <= self.len()) };

Err(result)

}

}

/// Binary searches this slice with a key extraction function.