use crate::{

    dfa::DEAD,

    util::{

        bytes::{self, DeserializeError, Endian, SerializeError},

        id::StateID,

    },

};

macro_rules! err {

    ($msg:expr) => {

        return Err(DeserializeError::generic($msg));

    };

}

// Special represents the identifiers in a DFA that correspond to "special"

// states. If a state is one or more of the following, then it is considered

// special:

//

// * dead - A non-matching state where all outgoing transitions lead back to

//   itself. There is only one of these, regardless of whether minimization

//   has run. The dead state always has an ID of 0. i.e., It is always the

//   first state in a DFA.

// * quit - A state that is entered whenever a byte is seen that should cause

//   a DFA to give up and stop searching. This results in a MatchError::Quit

//   error being returned at search time. The default configuration for a DFA

//   has no quit bytes, which means this state is unreachable by default,

//   although it is always present for reasons of implementation simplicity.

//   This state is only reachable when the caller configures the DFA to quit

//   on certain bytes. There is always exactly one of these states and it

//   is always the second state. (Its actual ID depends on the size of the

//   alphabet in dense DFAs, since state IDs are premultiplied in order to

//   allow them to be used directly as indices into the transition table.)

// * match - An accepting state, i.e., indicative of a match. There may be

//   zero or more of these states.

// * accelerated - A state where all of its outgoing transitions, except a

//   few, loop back to itself. These states are candidates for acceleration

//   via memchr during search. There may be zero or more of these states.

// * start - A non-matching state that indicates where the automaton should

//   start during a search. There is always at least one starting state and

//   all are guaranteed to be non-match states. (A start state cannot be a

//   match state because the DFAs in this crate delay all matches by one byte.

//   So every search that finds a match must move through one transition to

//   some other match state, even when searching an empty string.)

//

// These are not mutually exclusive categories. Namely, the following

// overlappings can occur:

//

// * {dead, start} - If a DFA can never lead to a match and it is minimized,

//   then it will typically compile to something where all starting IDs point

//   to the DFA's dead state.

// * {match, accelerated} - It is possible for a match state to have the

//   majority of its transitions loop back to itself, which means it's

//   possible for a match state to be accelerated.

// * {start, accelerated} - Similarly, it is possible for a start state to be

//   accelerated. Note that it is possible for an accelerated state to be

//   neither a match or a start state. Also note that just because both match

//   and start states overlap with accelerated states does not mean that

//   match and start states overlap with each other. In fact, they are

//   guaranteed not to overlap.

//

// As a special mention, every DFA always has a dead and a quit state, even

// though from the perspective of the DFA, they are equivalent. (Indeed,

// minimization special cases them to ensure they don't get merged.) The

// purpose of keeping them distinct is to use the quit state as a sentinel to

// distguish between whether a search finished successfully without finding

// anything or whether it gave up before finishing.

//

// So the main problem we want to solve here is the *fast* detection of whether

// a state is special or not. And we also want to do this while storing as

// little extra data as possible. AND we want to be able to quickly determine

// which categories a state falls into above if it is special.

//

// We achieve this by essentially shuffling all special states to the beginning

// of a DFA. That is, all special states appear before every other non-special

// state. By representing special states this way, we can determine whether a

// state is special or not by a single comparison, where special.max is the

// identifier of the last special state in the DFA:

//

//     if current_state <= special.max:

//         ... do something with special state

//

// The only thing left to do is to determine what kind of special state

// it is. Because what we do next depends on that. Since special states

// are typically rare, we can afford to do a bit more extra work, but we'd

// still like this to be as fast as possible. The trick we employ here is to

// continue shuffling states even within the special state range. Such that

// one contiguous region corresponds to match states, another for start states

// and then an overlapping range for accelerated states. At a high level, our

// special state detection might look like this (for leftmost searching, where

// we continue searching even after seeing a match):

//

//     byte = input[offset]

//     current_state = next_state(current_state, byte)

//     offset += 1

//     if current_state <= special.max:

//         if current_state == 0:

//             # We can never leave a dead state, so this always marks the

//             # end of our search.

//             return last_match

//         if current_state == special.quit_id:

//             # A quit state means we give up. If he DFA has no quit state,

//             # then special.quit_id == 0 == dead, which is handled by the

//             # conditional above.

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

//         if special.min_match <= current_state <= special.max_match:

//             last_match = Some(offset)

//             if special.min_accel <= current_state <= special.max_accel:

//                 offset = accelerate(input, offset)

//                 last_match = Some(offset)

//         elif special.min_start <= current_state <= special.max_start:

//             offset = prefilter.find(input, offset)

//             if special.min_accel <= current_state <= special.max_accel:

//                 offset = accelerate(input, offset)

//         elif special.min_accel <= current_state <= special.max_accel:

//             offset = accelerate(input, offset)

//

// There are some small details left out of the logic above. For example,

// in order to accelerate a state, we need to know which bytes to search for.

// This in turn implies some extra data we need to store in the DFA. To keep

// things compact, we would ideally only store

//

//     N = special.max_accel - special.min_accel + 1

//

// items. But state IDs are premultiplied, which means they are not contiguous.

// So in order to take a state ID and index an array of accelerated structures,

// we need to do:

//

//     i = (state_id - special.min_accel) / stride

//

// (N.B. 'stride' is always a power of 2, so the above can be implemented via

// '(state_id - special.min_accel) >> stride2', where 'stride2' is x in

// 2^x=stride.)

//

// Moreover, some of these specialty categories may be empty. For example,

// DFAs are not required to have any match states or any accelerated states.

// In that case, the lower and upper bounds are both set to 0 (the dead state

// ID) and the first `current_state == 0` check subsumes cases where the

// ranges are empty.

//

// Loop unrolling, if applicable, has also been left out of the logic above.

//

// Graphically, the ranges look like this, where asterisks indicate ranges

// that can be empty. Each 'x' is a state.

//

//      quit

//  dead|

//     ||

//     xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

//     | |             |    | start |                       |

//     | |-------------|    |-------|                       |

//     |   match*   |          |    |                       |

//     |            |          |    |                       |

//     |            |----------|    |                       |

//     |                accel*      |                       |

//     |                            |                       |

//     |                            |                       |

//     |----------------------------|------------------------

//              special                   non-special*

#[derive(Clone, Copy, Debug)]

pub struct Special {

    /// The identifier of the last special state in a DFA. A state is special

    /// if and only if its identifier is less than or equal to `max`.

    pub max: StateID,

    /// The identifier of the quit state in a DFA. (There is no analogous field

    /// for the dead state since the dead state's ID is always zero, regardless

    /// of state ID size.)

    pub quit_id: StateID,

    /// The identifier of the first match state.

    pub min_match: StateID,

    /// The identifier of the last match state.

    pub max_match: StateID,

    /// The identifier of the first accelerated state.

    pub min_accel: StateID,

    /// The identifier of the last accelerated state.

    pub max_accel: StateID,

    /// The identifier of the first start state.

    pub min_start: StateID,

    /// The identifier of the last start state.

    pub max_start: StateID,

}

impl Special {

    /// Creates a new set of special ranges for a DFA. All ranges are initially

    /// set to only contain the dead state. This is interpreted as an empty

    /// range.

    #[cfg(feature = "alloc")]

    pub fn new() -> Special {

        Special {

            max: DEAD,

            quit_id: DEAD,

            min_match: DEAD,

            max_match: DEAD,

            min_accel: DEAD,

            max_accel: DEAD,

            min_start: DEAD,

            max_start: DEAD,

        }

    }

    /// Remaps all of the special state identifiers using the function given.

    #[cfg(feature = "alloc")]

    pub fn remap(&self, map: impl Fn(StateID) -> StateID) -> Special {

        Special {

            max: map(self.max),

            quit_id: map(self.quit_id),

            min_match: map(self.min_match),

            max_match: map(self.max_match),

            min_accel: map(self.min_accel),

            max_accel: map(self.max_accel),

            min_start: map(self.min_start),

            max_start: map(self.max_start),

        }

    }

    /// Deserialize the given bytes into special state ranges. If the slice

    /// given is not big enough, then this returns an error. Similarly, if

    /// any of the expected invariants around special state ranges aren't

    /// upheld, an error is returned. Note that this does not guarantee that

    /// the information returned is correct.

    ///

    /// Upon success, this returns the number of bytes read in addition to the

    /// special state IDs themselves.

    pub fn from_bytes(

        mut slice: &[u8],

    ) -> Result<(Special, usize), DeserializeError> {

        bytes::check_slice_len(slice, 8 * StateID::SIZE, "special states")?;

        let mut nread = 0;

        let mut read_id = |what| -> Result<StateID, DeserializeError> {

            let (id, nr) = bytes::try_read_state_id(slice, what)?;

            nread += nr;

            slice = &slice[StateID::SIZE..];

            Ok(id)

        };

        let max = read_id("special max id")?;

        let quit_id = read_id("special quit id")?;

        let min_match = read_id("special min match id")?;

        let max_match = read_id("special max match id")?;

        let min_accel = read_id("special min accel id")?;

        let max_accel = read_id("special max accel id")?;

        let min_start = read_id("special min start id")?;

        let max_start = read_id("special max start id")?;

        let special = Special {

            max,

            quit_id,

            min_match,

            max_match,

            min_accel,

            max_accel,

            min_start,

            max_start,

        };

        special.validate()?;

        assert_eq!(nread, special.write_to_len());

        Ok((special, nread))

    }

    /// Validate that the information describing special states satisfies

    /// all known invariants.

    pub fn validate(&self) -> Result<(), DeserializeError> {

        // Check that both ends of the range are DEAD or neither are.

        if self.min_match == DEAD && self.max_match != DEAD {

            err!("min_match is DEAD, but max_match is not");

        }

        if self.min_match != DEAD && self.max_match == DEAD {

            err!("max_match is DEAD, but min_match is not");

        }

        if self.min_accel == DEAD && self.max_accel != DEAD {

            err!("min_accel is DEAD, but max_accel is not");

        }

        if self.min_accel != DEAD && self.max_accel == DEAD {

            err!("max_accel is DEAD, but min_accel is not");

        }

        if self.min_start == DEAD && self.max_start != DEAD {

            err!("min_start is DEAD, but max_start is not");

        }

        if self.min_start != DEAD && self.max_start == DEAD {

            err!("max_start is DEAD, but min_start is not");

        }

        // Check that ranges are well formed.

        if self.min_match > self.max_match {

            err!("min_match should not be greater than max_match");

        }

        if self.min_accel > self.max_accel {

            err!("min_accel should not be greater than max_accel");

        }

        if self.min_start > self.max_start {

            err!("min_start should not be greater than max_start");

        }

        // Check that ranges are ordered with respect to one another.

        if self.matches() && self.quit_id >= self.min_match {

            err!("quit_id should not be greater than min_match");

        }

        if self.accels() && self.quit_id >= self.min_accel {

            err!("quit_id should not be greater than min_accel");

        }

        if self.starts() && self.quit_id >= self.min_start {

            err!("quit_id should not be greater than min_start");

        }

        if self.matches() && self.accels() && self.min_accel < self.min_match {

            err!("min_match should not be greater than min_accel");

        }

        if self.matches() && self.starts() && self.min_start < self.min_match {

            err!("min_match should not be greater than min_start");

        }

        if self.accels() && self.starts() && self.min_start < self.min_accel {

            err!("min_accel should not be greater than min_start");

        }

        // Check that max is at least as big as everything else.

        if self.max < self.quit_id {

            err!("quit_id should not be greater than max");

        }

        if self.max < self.max_match {

            err!("max_match should not be greater than max");

        }

        if self.max < self.max_accel {

            err!("max_accel should not be greater than max");

        }

        if self.max < self.max_start {

            err!("max_start should not be greater than max");

        }

        Ok(())

    }

    /// Validate that the special state information is compatible with the

    /// given state count.

    pub fn validate_state_count(

        &self,

        count: usize,

        stride2: usize,

    ) -> Result<(), DeserializeError> {

        // We assume that 'validate' has already passed, so we know that 'max'

        // is truly the max. So all we need to check is that the max state

        // ID is less than the state ID count. The max legal value here is

        // count-1, which occurs when there are no non-special states.

        if (self.max.as_usize() >> stride2) >= count {

            err!("max should not be greater than or equal to state count");

        }

        Ok(())

    }

    /// Write the IDs and ranges for special states to the given byte buffer.

    /// The buffer given must have enough room to store all data, otherwise

    /// this will return an error. The number of bytes written is returned

    /// on success. The number of bytes written is guaranteed to be a multiple

    /// of 8.

    pub fn write_to<E: Endian>(

        &self,

        dst: &mut [u8],

    ) -> Result<usize, SerializeError> {

        use crate::util::bytes::write_state_id as write;

        if dst.len() < self.write_to_len() {

            return Err(SerializeError::buffer_too_small("special state ids"));

        }

        let mut nwrite = 0;

        nwrite += write::<E>(self.max, &mut dst[nwrite..]);

        nwrite += write::<E>(self.quit_id, &mut dst[nwrite..]);

        nwrite += write::<E>(self.min_match, &mut dst[nwrite..]);

        nwrite += write::<E>(self.max_match, &mut dst[nwrite..]);

        nwrite += write::<E>(self.min_accel, &mut dst[nwrite..]);

        nwrite += write::<E>(self.max_accel, &mut dst[nwrite..]);

        nwrite += write::<E>(self.min_start, &mut dst[nwrite..]);

        nwrite += write::<E>(self.max_start, &mut dst[nwrite..]);

        assert_eq!(

            self.write_to_len(),

            nwrite,

            "expected to write certain number of bytes",

        );

        assert_eq!(

            nwrite % 8,

            0,

            "expected to write multiple of 8 bytes for special states",

        );

        Ok(nwrite)

    }

    /// Returns the total number of bytes written by `write_to`.

    pub fn write_to_len(&self) -> usize {

        8 * StateID::SIZE

    }

    /// Sets the maximum special state ID based on the current values. This

    /// should be used once all possible state IDs are set.

    #[cfg(feature = "alloc")]

    pub fn set_max(&mut self) {

        use core::cmp::max;

        self.max = max(

            self.quit_id,

            max(self.max_match, max(self.max_accel, self.max_start)),

        );

    }

    /// Returns true if and only if the given state ID is a special state.

    #[inline]

    pub fn is_special_state(&self, id: StateID) -> bool {

        id <= self.max

    }

    /// Returns true if and only if the given state ID is a dead state.

    #[inline]

    pub fn is_dead_state(&self, id: StateID) -> bool {

        id == DEAD

    }

Unexecuted instantiation: <regex_automata::dfa::special::Special>::is_dead_state

Unexecuted instantiation: <regex_automata::dfa::special::Special>::is_dead_state

    /// Returns true if and only if the given state ID is a quit state.

    #[inline]

    pub fn is_quit_state(&self, id: StateID) -> bool {

        !self.is_dead_state(id) && self.quit_id == id

    }

    /// Returns true if and only if the given state ID is a match state.

    #[inline]

    pub fn is_match_state(&self, id: StateID) -> bool {

        !self.is_dead_state(id) && self.min_match <= id && id <= self.max_match

    }

Unexecuted instantiation: <regex_automata::dfa::special::Special>::is_match_state

Unexecuted instantiation: <regex_automata::dfa::special::Special>::is_match_state

    /// Returns true if and only if the given state ID is an accel state.

    #[inline]

    pub fn is_accel_state(&self, id: StateID) -> bool {

        !self.is_dead_state(id) && self.min_accel <= id && id <= self.max_accel

    }

    /// Returns true if and only if the given state ID is a start state.

    #[inline]

    pub fn is_start_state(&self, id: StateID) -> bool {

        !self.is_dead_state(id) && self.min_start <= id && id <= self.max_start

    }

    /// Returns the total number of match states for a dense table based DFA.

    #[inline]

    pub fn match_len(&self, stride: usize) -> usize {

        if self.matches() {

            (self.max_match.as_usize() - self.min_match.as_usize() + stride)

                / stride

        } else {

            0

        }

    }

    /// Returns true if and only if there is at least one match state.

    #[inline]

    pub fn matches(&self) -> bool {

        self.min_match != DEAD

    }

    /// Returns the total number of accel states.

    #[cfg(feature = "alloc")]

    pub fn accel_len(&self, stride: usize) -> usize {

        if self.accels() {

            (self.max_accel.as_usize() - self.min_accel.as_usize() + stride)

                / stride

        } else {

            0

        }

    }

    /// Returns true if and only if there is at least one accel state.

    #[inline]

    pub fn accels(&self) -> bool {

        self.min_accel != DEAD

    }

    /// Returns true if and only if there is at least one start state.

    #[inline]

    pub fn starts(&self) -> bool {

        self.min_start != DEAD

    }

}