use crate::{

    dfa::{

        accel,

        automaton::{Automaton, OverlappingState, StateMatch},

    },

    util::{

        id::{PatternID, StateID},

        matchtypes::HalfMatch,

        prefilter, MATCH_OFFSET,

    },

    MatchError,

};

#[inline(never)]

pub fn find_earliest_fwd<A: Automaton + ?Sized>(

    pre: Option<&mut prefilter::Scanner>,

    dfa: &A,

    pattern_id: Option<PatternID>,

    bytes: &[u8],

    start: usize,

    end: usize,

) -> Result<Option<HalfMatch>, MatchError> {

    // Searching with a pattern ID is always anchored, so we should never use

    // a prefilter.

    if pre.is_some() && pattern_id.is_none() {

        find_fwd(pre, true, dfa, pattern_id, bytes, start, end)

    } else {

        find_fwd(None, true, dfa, pattern_id, bytes, start, end)

    }

}

#[inline(never)]

pub fn find_leftmost_fwd<A: Automaton + ?Sized>(

    pre: Option<&mut prefilter::Scanner>,

    dfa: &A,

    pattern_id: Option<PatternID>,

    bytes: &[u8],

    start: usize,

    end: usize,

) -> Result<Option<HalfMatch>, MatchError> {

    // Searching with a pattern ID is always anchored, so we should never use

    // a prefilter.

    if pre.is_some() && pattern_id.is_none() {

        find_fwd(pre, false, dfa, pattern_id, bytes, start, end)

    } else {

        find_fwd(None, false, dfa, pattern_id, bytes, start, end)

    }

}

/// This is marked as `inline(always)` specifically because it supports

/// multiple modes of searching. Namely, the 'pre' and 'earliest' parameters

/// getting inlined eliminate some critical branches. To avoid bloating binary

/// size, we only call this function in a fixed number of places.

#[inline(always)]

fn find_fwd<A: Automaton + ?Sized>(

    mut pre: Option<&mut prefilter::Scanner>,

    earliest: bool,

    dfa: &A,

    pattern_id: Option<PatternID>,

    haystack: &[u8],

    start: usize,

    end: usize,

) -> Result<Option<HalfMatch>, MatchError> {

    assert!(start <= end);

    assert!(start <= haystack.len());

    assert!(end <= haystack.len());

    // Why do this? This lets 'bytes[at]' work without bounds checks below.

    // It seems the assert on 'end <= haystack.len()' above is otherwise

    // not enough. Why not just make 'bytes' scoped this way anyway? Well,

    // 'eoi_fwd' (below) might actually want to try to access the byte at 'end'

    // for resolving look-ahead.

    let bytes = &haystack[..end];

    let mut state = init_fwd(dfa, pattern_id, haystack, start, end)?;

    let mut last_match = None;

    let mut at = start;

    if let Some(ref mut pre) = pre {

        // If a prefilter doesn't report false positives, then we don't need to

        // touch the DFA at all. However, since all matches include the pattern

        // ID, and the prefilter infrastructure doesn't report pattern IDs, we

        // limit this optimization to cases where there is exactly one pattern.

        // In that case, any match must be the 0th pattern.

        if dfa.pattern_count() == 1 && !pre.reports_false_positives() {

            return Ok(pre.next_candidate(bytes, at).into_option().map(

                |offset| HalfMatch { pattern: PatternID::ZERO, offset },

            ));

        } else if pre.is_effective(at) {

            match pre.next_candidate(bytes, at).into_option() {

                None => return Ok(None),

                Some(i) => {

                    at = i;

                }

            }

        }

    }

    while at < end {

        let byte = bytes[at];

        state = dfa.next_state(state, byte);

        at += 1;

        if dfa.is_special_state(state) {

            if dfa.is_start_state(state) {

                if let Some(ref mut pre) = pre {

                    if pre.is_effective(at) {

                        match pre.next_candidate(bytes, at).into_option() {

                            None => return Ok(None),

                            Some(i) => {

                                at = i;

                            }

                        }

                    }

                } else if dfa.is_accel_state(state) {

                    let needles = dfa.accelerator(state);

                    at = accel::find_fwd(needles, bytes, at)

                        .unwrap_or(bytes.len());

                }

            } else if dfa.is_match_state(state) {

                last_match = Some(HalfMatch {

                    pattern: dfa.match_pattern(state, 0),

                    offset: at - MATCH_OFFSET,

                });

                if earliest {

                    return Ok(last_match);

                }

                if dfa.is_accel_state(state) {

                    let needles = dfa.accelerator(state);

                    at = accel::find_fwd(needles, bytes, at)

                        .unwrap_or(bytes.len());

                }

            } else if dfa.is_accel_state(state) {

                let needs = dfa.accelerator(state);

                at = accel::find_fwd(needs, bytes, at).unwrap_or(bytes.len());

            } else if dfa.is_dead_state(state) {

                return Ok(last_match);

            } else {

                debug_assert!(dfa.is_quit_state(state));

                if last_match.is_some() {

                    return Ok(last_match);

                }

                return Err(MatchError::Quit { byte, offset: at - 1 });

            }

        }

        while at < end && dfa.next_state(state, bytes[at]) == state {

            at += 1;

        }

    }

    Ok(eoi_fwd(dfa, haystack, end, &mut state)?.or(last_match))

}

#[inline(never)]

pub fn find_earliest_rev<A: Automaton + ?Sized>(

    dfa: &A,

    pattern_id: Option<PatternID>,

    bytes: &[u8],

    start: usize,

    end: usize,

) -> Result<Option<HalfMatch>, MatchError> {

    find_rev(true, dfa, pattern_id, bytes, start, end)

}

#[inline(never)]

pub fn find_leftmost_rev<A: Automaton + ?Sized>(

    dfa: &A,

    pattern_id: Option<PatternID>,

    bytes: &[u8],

    start: usize,

    end: usize,

) -> Result<Option<HalfMatch>, MatchError> {

    find_rev(false, dfa, pattern_id, bytes, start, end)

}

/// This is marked as `inline(always)` specifically because it supports

/// multiple modes of searching. Namely, the 'earliest' boolean getting inlined

/// permits eliminating a few crucial branches.

#[inline(always)]

fn find_rev<A: Automaton + ?Sized>(

    earliest: bool,

    dfa: &A,

    pattern_id: Option<PatternID>,

    bytes: &[u8],

    start: usize,

    end: usize,

) -> Result<Option<HalfMatch>, MatchError> {

    assert!(start <= end);

    assert!(start <= bytes.len());

    assert!(end <= bytes.len());

    let mut state = init_rev(dfa, pattern_id, bytes, start, end)?;

    let mut last_match = None;

    let mut at = end;

    while at > start {

        at -= 1;

        while at > start && dfa.next_state(state, bytes[at]) == state {

            at -= 1;

        }

        let byte = bytes[at];

        state = dfa.next_state(state, byte);

        if dfa.is_special_state(state) {

            if dfa.is_start_state(state) {

                if dfa.is_accel_state(state) {

                    let needles = dfa.accelerator(state);

                    at = accel::find_rev(needles, bytes, at)

                        .map(|i| i + 1)

                        .unwrap_or(0);

                }

            } else if dfa.is_match_state(state) {

                last_match = Some(HalfMatch {

                    pattern: dfa.match_pattern(state, 0),

                    offset: at + MATCH_OFFSET,

                });

                if earliest {

                    return Ok(last_match);

                }

                if dfa.is_accel_state(state) {

                    let needles = dfa.accelerator(state);

                    at = accel::find_rev(needles, bytes, at)

                        .map(|i| i + 1)

                        .unwrap_or(0);

                }

            } else if dfa.is_accel_state(state) {

                let needles = dfa.accelerator(state);

                at = accel::find_rev(needles, bytes, at)

                    .map(|i| i + 1)

                    .unwrap_or(0);

            } else if dfa.is_dead_state(state) {

                return Ok(last_match);

            } else {

                debug_assert!(dfa.is_quit_state(state));

                if last_match.is_some() {

                    return Ok(last_match);

                }

                return Err(MatchError::Quit { byte, offset: at });

            }

        }

    }

    Ok(eoi_rev(dfa, bytes, start, state)?.or(last_match))

}

#[inline(never)]

pub fn find_overlapping_fwd<A: Automaton + ?Sized>(

    pre: Option<&mut prefilter::Scanner>,

    dfa: &A,

    pattern_id: Option<PatternID>,

    bytes: &[u8],

    start: usize,

    end: usize,

    caller_state: &mut OverlappingState,

) -> Result<Option<HalfMatch>, MatchError> {

    // Searching with a pattern ID is always anchored, so we should only ever

    // use a prefilter when no pattern ID is given.

    if pre.is_some() && pattern_id.is_none() {

        find_overlapping_fwd_imp(

            pre,

            dfa,

            pattern_id,

            bytes,

            start,

            end,

            caller_state,

        )

    } else {

        find_overlapping_fwd_imp(

            None,

            dfa,

            pattern_id,

            bytes,

            start,

            end,

            caller_state,

        )

    }

}

/// This is marked as `inline(always)` specifically because it supports

/// multiple modes of searching. Namely, the 'pre' prefilter getting inlined

/// permits eliminating a few crucial branches and reduces code size when it is

/// not used.

#[inline(always)]

fn find_overlapping_fwd_imp<A: Automaton + ?Sized>(

    mut pre: Option<&mut prefilter::Scanner>,

    dfa: &A,

    pattern_id: Option<PatternID>,

    bytes: &[u8],

    mut start: usize,

    end: usize,

    caller_state: &mut OverlappingState,

) -> Result<Option<HalfMatch>, MatchError> {

    assert!(start <= end);

    assert!(start <= bytes.len());

    assert!(end <= bytes.len());

    let mut state = match caller_state.id() {

        None => init_fwd(dfa, pattern_id, bytes, start, end)?,

        Some(id) => {

            if let Some(last) = caller_state.last_match() {

                let match_count = dfa.match_count(id);

                if last.match_index < match_count {

                    let m = HalfMatch {

                        pattern: dfa.match_pattern(id, last.match_index),

                        offset: last.offset,

                    };

                    last.match_index += 1;

                    return Ok(Some(m));

                }

            }

            // This is a subtle but critical detail. If the caller provides a

            // non-None state ID, then it must be the case that the state ID

            // corresponds to one set by this function. The state ID therefore

            // corresponds to a match state, a dead state or some other state.

            // However, "some other" state _only_ occurs when the input has

            // been exhausted because the only way to stop before then is to

            // see a match or a dead/quit state.

            //

            // If the input is exhausted or if it's a dead state, then

            // incrementing the starting position has no relevance on

            // correctness, since the loop below will either not execute

            // at all or will immediately stop due to being in a dead state.

            // (Once in a dead state it is impossible to leave it.)

            //

            // Therefore, the only case we need to consider is when

            // caller_state is a match state. In this case, since our machines

            // support the ability to delay a match by a certain number of

            // bytes (to support look-around), it follows that we actually

            // consumed that many additional bytes on our previous search. When

            // the caller resumes their search to find subsequent matches, they

            // will use the ending location from the previous match as the next

            // starting point, which is `MATCH_OFFSET` bytes PRIOR to where

            // we scanned to on the previous search. Therefore, we need to

            // compensate by bumping `start` up by `MATCH_OFFSET` bytes.

            //

            // Incidentally, since MATCH_OFFSET is non-zero, this also makes

            // dealing with empty matches convenient. Namely, callers needn't

            // special case them when implementing an iterator. Instead, this

            // ensures that forward progress is always made.

            start += MATCH_OFFSET;

            id

        }

    };

    let mut at = start;

    while at < end {

        let byte = bytes[at];

        state = dfa.next_state(state, byte);

        at += 1;

        if dfa.is_special_state(state) {

            caller_state.set_id(state);

            if dfa.is_start_state(state) {

                if let Some(ref mut pre) = pre {

                    if pre.is_effective(at) {

                        match pre.next_candidate(bytes, at).into_option() {

                            None => return Ok(None),

                            Some(i) => {

                                at = i;

                            }

                        }

                    }

                } else if dfa.is_accel_state(state) {

                    let needles = dfa.accelerator(state);

                    at = accel::find_fwd(needles, bytes, at)

                        .unwrap_or(bytes.len());

                }

            } else if dfa.is_match_state(state) {

                let offset = at - MATCH_OFFSET;

                caller_state

                    .set_last_match(StateMatch { match_index: 1, offset });

                return Ok(Some(HalfMatch {

                    pattern: dfa.match_pattern(state, 0),

                    offset,

                }));

            } else if dfa.is_accel_state(state) {

                let needs = dfa.accelerator(state);

                at = accel::find_fwd(needs, bytes, at).unwrap_or(bytes.len());

            } else if dfa.is_dead_state(state) {

                return Ok(None);

            } else {

                debug_assert!(dfa.is_quit_state(state));

                return Err(MatchError::Quit { byte, offset: at - 1 });

            }

        }

    }

    let result = eoi_fwd(dfa, bytes, end, &mut state);

    caller_state.set_id(state);

    if let Ok(Some(ref last_match)) = result {

        caller_state.set_last_match(StateMatch {

            match_index: 1,

            offset: last_match.offset(),

        });

    }

    result

}

fn init_fwd<A: Automaton + ?Sized>(

    dfa: &A,

    pattern_id: Option<PatternID>,

    bytes: &[u8],

    start: usize,

    end: usize,

) -> Result<StateID, MatchError> {

    let state = dfa.start_state_forward(pattern_id, bytes, start, end);

    // Start states can never be match states, since all matches are delayed

    // by 1 byte.

    assert!(!dfa.is_match_state(state));

    Ok(state)

}

fn init_rev<A: Automaton + ?Sized>(

    dfa: &A,

    pattern_id: Option<PatternID>,

    bytes: &[u8],

    start: usize,

    end: usize,

) -> Result<StateID, MatchError> {

    let state = dfa.start_state_reverse(pattern_id, bytes, start, end);

    // Start states can never be match states, since all matches are delayed

    // by 1 byte.

    assert!(!dfa.is_match_state(state));

    Ok(state)

}

fn eoi_fwd<A: Automaton + ?Sized>(

    dfa: &A,

    bytes: &[u8],

    end: usize,

    state: &mut StateID,

) -> Result<Option<HalfMatch>, MatchError> {

    match bytes.get(end) {

        Some(&b) => {

            *state = dfa.next_state(*state, b);

            if dfa.is_match_state(*state) {

                Ok(Some(HalfMatch {

                    pattern: dfa.match_pattern(*state, 0),

                    offset: end,

                }))

            } else {

                Ok(None)

            }

        }

        None => {

            *state = dfa.next_eoi_state(*state);

            if dfa.is_match_state(*state) {

                Ok(Some(HalfMatch {

                    pattern: dfa.match_pattern(*state, 0),

                    offset: bytes.len(),

                }))

            } else {

                Ok(None)

            }

        }

    }

}

fn eoi_rev<A: Automaton + ?Sized>(

    dfa: &A,

    bytes: &[u8],

    start: usize,

    state: StateID,

) -> Result<Option<HalfMatch>, MatchError> {

    if start > 0 {

        let state = dfa.next_state(state, bytes[start - 1]);

        if dfa.is_match_state(state) {

            Ok(Some(HalfMatch {

                pattern: dfa.match_pattern(state, 0),

                offset: start,

            }))

        } else {

            Ok(None)

        }

    } else {

        let state = dfa.next_eoi_state(state);

        if dfa.is_match_state(state) {

            Ok(Some(HalfMatch {

                pattern: dfa.match_pattern(state, 0),

                offset: 0,

            }))

        } else {

            Ok(None)

        }

    }

}

// Currently unused, but is useful to keep around. This was originally used

// when the code above used raw pointers for its main loop.

// /// Returns the distance between the given pointer and the start of `bytes`.

// /// This assumes that the given pointer points to somewhere in the `bytes`

// /// slice given.

// fn offset(bytes: &[u8], p: *const u8) -> usize {

// debug_assert!(bytes.as_ptr() <= p);

// debug_assert!(bytes[bytes.len()..].as_ptr() >= p);

// ((p as isize) - (bytes.as_ptr() as isize)) as usize

// }