/*
Copyright ⓒ 2015-2017 Daniel Keep.

Licensed under the MIT license (see LICENSE or <http://opensource.org
/licenses/MIT>) or the Apache License, Version 2.0 (see LICENSE of
<http://www.apache.org/licenses/LICENSE-2.0>), at your option. All
files in the project carrying such notice may not be copied, modified,
or distributed except according to those terms.
*/
/*!
This crate provides a "cursor" type for string slices.  It provides the ability to safely seek back and forth through a string without worrying about producing invalid UTF-8 sequences, or splitting grapheme clusters.

In addition, it provides types to represent single grapheme clusters ([`Gc`](struct.Gc.html) and [`GcBuf`](struct.GcBuf.html)) as distinct from arbitrary string slices.

See the [`StrCursor`](struct.StrCursor.html) type for details.

<style type="text/css">
.link-block { font-family: "Fira Sans"; }
.link-block > p { display: inline-block; }
.link-block > p > strong { font-weight: 500; margin-right: 1em; }
.link-block > ul { display: inline-block; padding: 0; list-style: none; }
.link-block > ul > li {
  font-size: 0.8em;
  background-color: #eee;
  border: 1px solid #ccc;
  padding: 0.3em;
  display: inline-block;
}
</style>
<span></span><div class="link-block">

**Links**

* [Latest Release](https://crates.io/crates/strcursor/)
* [Latest Docs](https://docs.rs/strcursor/%2A/strcursor/index.html)
* [Repository](https://github.com/DanielKeep/strcursor)

<span></span></div>

## Compatibility

`strcursor` is currently supported on `rustc` version 1.1.0 and higher.

* `rustc` < 1.4 will use a larger, less space-efficient implementation of `GcBuf`; rather than being the same size as `Box<str>`, it will be the same size as `String`.

* `rustc` < 1.1 is not supported, due to a mysterious compiler crash.

*/
extern crate unicode_segmentation as uniseg;

/**
Inserts a panic in debug builds, an optimisation hint in release builds.

**Do not replace this with the `debug_unreachable` crate.**  Recent versions of that crate do not build under Rust < 1.6, and old versions that used to no longer will, as they have sufficiently vague dependency version specifiers.
*/
#[doc(hidden)]
macro_rules! debug_unreachable {
    () => {
        if cfg!(ndebug) {
            ::util::unreachable()
        } else {
            panic!("entered unreachable code")
        }
    };
}

pub use grapheme::{Gc, GcBuf};

pub mod grapheme;
mod util;

use uniseg::UnicodeSegmentation as UniSeg;

/**
This type represents a cursor into a string slice; that is, in addition to having a beginning and end, it also has a current position between those two.  This position can be seeked left and right within those bounds.

> **Note**: the cursor may validly be positioned *at* the end of the string.  That is, in a position where there are no code points or grapheme clusters to the right of the cursor, and the entire contents of the string is to the left of the cursor.

The main reason for this is that *sometimes*, you want the ability to do things like "advance a character", and the existing APIs for this can be somewhat verbose.

In addition, *unstable* support for grapheme clusters is exposed by the standard library, which conflicts with the *stable* support provided by the `unicode-segmentation` crate, which makes doing "the right thing" painful.  `StrCursor` exposes grapheme clusters by default, and makes them cleaner to work with.

The cursor guarantees the following at all times:

* The cursor position *cannot* be outside of the original string slice it was constructed with.
* The cursor position *cannot* lie between Unicode code points, meaning that you *cannot* generate an invalid string slice from a cursor.
* If the code point-specific methods are *not* used, the cursor will always lie between grapheme clusters.

This last point is somewhat important: the cursor is designed to favour operating on grapheme clusters, rather than code points.  If you misalign the cursor with respect to grapheme clusters, the behaviour of methods that deal with grapheme clusters is officially *undefined*, but is generally well-behaved.

The methods that operate on the cursor will either return a fresh `Option<StrCursor>` (depending on whether the seek operation is valid or not), or mutate the existing cursor (in which case, they will *panic* if the seek operation is not valid).
*/
pub struct StrCursor<'a> {
    s: &'a str,
    at: *const u8,
}

impl<'a> StrCursor<'a> {
    /**
    Create a new cursor at the start of `s`.
    */
    #[inline]
    pub fn new_at_start(s: &'a str) -> StrCursor<'a> {
        StrCursor {
            s: s,
            at: s.as_ptr(),
        }
    }

    /**
    Create a new cursor past at the end of `s`.
    */
    #[inline]
    pub fn new_at_end(s: &'a str) -> StrCursor<'a> {
        StrCursor {
            s: s,
            at: byte_pos_to_ptr(s, s.len()),
        }
    }

    /**
    Create a new cursor at the first grapheme cluster which begins at or to the left of the given byte position.
    */
    #[inline]
    pub fn new_at_left_of_byte_pos(s: &'a str, byte_pos: usize) -> StrCursor<'a> {
        // Start at a codepoint.
        let cur = StrCursor::new_at_cp_left_of_byte_pos(s, byte_pos);

        // Seek back to the previous grapheme.
        let prev = cur.at_prev();

        let prev = match prev {
            None => return cur, // We were already at the start.
            Some(c) => c
        };

        // unwrap should be OK here.
        if prev.byte_pos() + prev.after().unwrap().len() > byte_pos {
            prev
        } else {
            cur
        }
    }

    /**
    Create a new cursor at the first grapheme cluster which begins at or to the right of the given byte position.
    */
    #[inline]
    pub fn new_at_right_of_byte_pos(s: &'a str, byte_pos: usize) -> StrCursor<'a> {
        // I don't know how robust the grapheme iteration rules are when trying to step forward from a (potentially) invalid position.  As such, I'm *instead* going to start from a known-good position.
        let cur = StrCursor::new_at_left_of_byte_pos(s, byte_pos);
        if cur.byte_pos() == byte_pos {
            return cur;
        }

        // This unwrap shouldn't be able to fail.
        cur.at_next().unwrap()
    }

    /**
    Create a new cursor at the first code point which begins at or to the left of the given byte position.

    # Note

    Where possible, you should prefer `new_at_left_of_byte_pos`.
    */
    #[inline]
    pub fn new_at_cp_left_of_byte_pos(s: &'a str, byte_pos: usize) -> StrCursor<'a> {
        StrCursor {
            s: s,
            at: unsafe { seek_utf8_cp_start_left(s, byte_pos_to_ptr(s, byte_pos)) },
        }
    }

    /**
    Create a new cursor at the first code point which begins at or to the right of the given byte position.

    # Note

    Where possible, you should prefer `new_at_right_of_byte_pos`.
    */
    #[inline]
    pub fn new_at_cp_right_of_byte_pos(s: &'a str, byte_pos: usize) -> StrCursor<'a> {
        StrCursor {
            s: s,
            at: unsafe { seek_utf8_cp_start_right(s, byte_pos_to_ptr(s, byte_pos)) },
        }
    }

    /**
    Returns a new cursor at the beginning of the previous grapheme cluster, or `None` if the cursor is currently positioned at the beginning of the string.
    */
    #[inline]
    pub fn at_prev(mut self) -> Option<StrCursor<'a>> {
        match self.try_seek_left_gr() {
            true => Some(self),
            false => None
        }
    }

    /**
    Returns a new cursor at the beginning of the next grapheme cluster, or `None` if the cursor is currently positioned at the end of the string.
    */
    #[inline]
    pub fn at_next(mut self) -> Option<StrCursor<'a>> {
        match self.try_seek_right_gr() {
            true => Some(self),
            false => None
        }
    }

    /**
    Returns a new cursor at the beginning of the previous code point, or `None` if the cursor is currently positioned at the beginning of the string.

    # Note

    Where possible, you should prefer `at_prev`.
    */
    #[inline]
    pub fn at_prev_cp(mut self) -> Option<StrCursor<'a>> {
        match self.try_seek_left_cp() {
            true => Some(self),
            false => None
        }
    }

    /**
    Returns a new cursor at the beginning of the next code point, or `None` if the cursor is currently positioned at the end of the string.

    # Note

    Where possible, you should prefer `at_next`.
    */
    #[inline]
    pub fn at_next_cp(mut self) -> Option<StrCursor<'a>> {
        match self.try_seek_right_cp() {
            true => Some(self),
            false => None
        }
    }

    /**
    Seeks the cursor to the beginning of the previous grapheme cluster.

    # Panics

    If the cursor is currently at the start of the string, then this function will panic.
    */
    #[inline]
    pub fn seek_prev(&mut self) {
        if !self.try_seek_left_gr() {
            panic!("cannot seek past the beginning of a string");
        }
    }

    /**
    Seeks the cursor to the beginning of the next grapheme cluster.

    # Panics

    If the cursor is currently at the end of the string, then this function will panic.
    */
    #[inline]
    pub fn seek_next(&mut self) {
        if !self.try_seek_right_gr() {
            panic!("cannot seek past the end of a string");
        }
    }

    /**
    Seeks the cursor to the beginning of the previous code point.

    # Panics

    If the cursor is currently at the start of the string, then this function will panic.

    # Note

    Where possible, you should prefer `seek_prev`.
    */
    #[inline]
    pub fn seek_prev_cp(&mut self) {
        if !self.try_seek_left_cp() {
            panic!("cannot seek past the beginning of a string");
        }
    }

    /**
    Seeks the cursor to the beginning of the next code point.

    # Panics

    If the cursor is currently at the end of the string, then this function will panic.

    # Note

    Where possible, you should prefer `seek_next`.
    */
    #[inline]
    pub fn seek_next_cp(&mut self) {
        if !self.try_seek_right_cp() {
            panic!("cannot seek past the end of a string");
        }
    }

    /**
    Returns both the previous grapheme cluster and the cursor having seeked before it.

    This may be more efficient than doing both operations individually.
    */
    #[inline]
    pub fn prev(mut self) -> Option<(&'a Gc, StrCursor<'a>)> {
        unsafe {
            let g = match self.before() {
                Some(g) => g,
                None => return None,
            };
            self.unsafe_set_at(g.as_str());
            Some((g, self))
        }
    }

    /**
    Returns both the previous code point and the cursor having seeked before it.

    This may be more efficient than doing both operations individually.

    # Note

    Where possible, you should prefer `prev`.
    */
    #[inline]
    pub fn prev_cp(mut self) -> Option<(char, StrCursor<'a>)> {
        unsafe {
            let cp = match self.cp_before() {
                Some(cp) => cp,
                None => return None,
            };
            self.unsafe_seek_left(cp.len_utf8());
            Some((cp, self))
        }
    }

    /**
    Returns both the next grapheme cluster and the cursor having seeked past it.

    This may be more efficient than doing both operations individually.
    */
    #[inline]
    pub fn next(mut self) -> Option<(&'a Gc, StrCursor<'a>)> {
        unsafe {
            let g = match self.after() {
                Some(g) => g,
                None => return None,
            };
            self.unsafe_seek_right(g.len());
            Some((g, self))
        }
    }

    /**
    Returns both the next code point and the cursor having seeked past it.

    This may be more efficient than doing both operations individually.

    # Note

    Where possible, you should prefer `next`.
    */
    #[inline]
    pub fn next_cp(mut self) -> Option<(char, StrCursor<'a>)> {
        unsafe {
            let cp = match self.cp_after() {
                Some(cp) => cp,
                None => return None,
            };
            self.unsafe_seek_right(cp.len_utf8());
            Some((cp, self))
        }
    }

    /**
    Returns the grapheme cluster immediately to the left of the cursor, or `None` is the cursor is at the start of the string.
    */
    #[inline]
    pub fn before(&self) -> Option<&'a Gc> {
        self.at_prev().and_then(|cur| cur.after())
    }

    /**
    Returns the grapheme cluster immediately to the right of the cursor, or `None` is the cursor is at the end of the string.
    */
    #[inline]
    pub fn after(&self) -> Option<&'a Gc> {
        Gc::split_from(self.slice_after()).map(|(gc, _)| gc)
    }

    /**
    Returns the contents of the string to the left of the cursor.
    */
    #[inline]
    pub fn slice_before(&self) -> &'a str {
        unsafe {
            self.s.slice_unchecked(0, self.byte_pos())
        }
    }

    /**
    Returns the contents of the string to the right of the cursor.
    */
    #[inline]
    pub fn slice_after(&self) -> &'a str {
        unsafe {
            self.s.slice_unchecked(self.byte_pos(), self.s.len())
        }
    }

    /**
    Returns the contents of the string *between* this cursor and another cursor.

    Returns `None` if the cursors are from different strings (even different subsets of the same string).
    */
    #[inline]
    pub fn slice_between(&self, until: StrCursor<'a>) -> Option<&'a str> {
        if !str_eq_literal(self.s, until.s) {
            None
        } else {
            use std::cmp::{max, min};
            unsafe {
                let beg = min(self.at, until.at);
                let end = max(self.at, until.at);
                let len = end as usize - beg as usize;
                let bytes = ::std::slice::from_raw_parts(beg, len);
                Some(::std::str::from_utf8_unchecked(bytes))
            }
        }
    }

    /**
    Returns the code point immediately to the left of the cursor, or `None` is the cursor is at the start of the string.
    */
    #[inline]
    pub fn cp_before(&self) -> Option<char> {
        self.at_prev_cp().and_then(|cur| cur.cp_after())
    }

    /**
    Returns the code point immediately to the right of the cursor, or `None` is the cursor is at the end of the string.
    */
    #[inline]
    pub fn cp_after(&self) -> Option<char> {
        self.slice_after().chars().next()
    }

    /**
    Returns the entire string slice behind the cursor.
    */
    #[inline]
    pub fn slice_all(&self) -> &'a str {
        self.s
    }

    /**
    Returns the cursor's current position within the string as the number of UTF-8 code units from the beginning of the string.
    */
    #[inline]
    pub fn byte_pos(&self) -> usize {
        self.at as usize - self.s.as_ptr() as usize
    }

    #[inline]
    fn try_seek_left_cp(&mut self) -> bool {
        unsafe {
            // We just have to ensure that offsetting the `at` pointer *at all* is safe.
            if self.byte_pos() == 0 {
                return false;
            }
            self.at = seek_utf8_cp_start_left(self.s, self.at.offset(-1));
            true
        }
    }

    #[inline]
    fn try_seek_right_cp(&mut self) -> bool {
        unsafe {
            // We just have to ensure that offsetting the `at` pointer *at all* is safe.
            if self.byte_pos() == self.s.len() {
                return false;
            }
            self.at = seek_utf8_cp_start_right(self.s, self.at.offset(1));
            true
        }
    }

    #[inline]
    fn try_seek_left_gr(&mut self) -> bool {
        let len = {
            let gr = UniSeg::graphemes(self.slice_before(), /*is_extended:*/true).next_back();
            gr.map(|gr| gr.len())
        };
        match len {
            Some(len) => {
                unsafe {
                    self.at = self.at.offset(-(len as isize));
                }
                true
            },
            None => false
        }
    }

    #[inline]
    fn try_seek_right_gr(&mut self) -> bool {
        let len = {
            let gr = UniSeg::graphemes(self.slice_after(), /*is_extended:*/true).next();
            gr.map(|gr| gr.len())
        };
        match len {
            Some(len) => {
                unsafe {
                    self.at = self.at.offset(len as isize);
                }
                true
            },
            None => false
        }
    }

    /**
    Seeks exactly `bytes` left, without performing any bounds or validity checks.
    */
    #[inline]
    pub unsafe fn unsafe_seek_left(&mut self, bytes: usize) {
        self.at = self.at.offset(-(bytes as isize));
    }

    /**
    Seeks exactly `bytes` right, without performing any bounds or validity checks.
    */
    #[inline]
    pub unsafe fn unsafe_seek_right(&mut self, bytes: usize) {
        self.at = self.at.offset(bytes as isize);
    }

    /**
    Seeks to the start of `s`, without performing any bounds or validity checks.
    */
    #[inline]
    pub unsafe fn unsafe_set_at(&mut self, s: &'a str) {
        self.at = s.as_bytes().as_ptr();
    }
}

impl<'a> Copy for StrCursor<'a> {}

impl<'a> Clone for StrCursor<'a> {
    fn clone(&self) -> StrCursor<'a> {
        *self
    }
}

impl<'a> std::fmt::Debug for StrCursor<'a> {
	fn fmt(&self, fmt: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
        write!(fmt, "StrCursor({:?} | {:?})", self.slice_before(), self.slice_after())
    }
}

impl<'a> Eq for StrCursor<'a> {}

impl<'a> PartialEq for StrCursor<'a> {
    fn eq(&self, other: &StrCursor<'a>) -> bool {
        (self.at == other.at)
        && (self.s.as_ptr() == other.s.as_ptr())
        && (self.s.len() == other.s.len())
    }

    fn ne(&self, other: &StrCursor<'a>) -> bool {
        (self.at != other.at)
        || (self.s.as_ptr() != other.s.as_ptr())
        || (self.s.len() != other.s.len())
    }
}

impl<'a> PartialOrd for StrCursor<'a> {
    fn partial_cmp(&self, other: &StrCursor<'a>) -> Option<std::cmp::Ordering> {
        // If the cursors are from different strings, they are unordered.
        if (self.s.as_ptr() != other.s.as_ptr()) || (self.s.len() != other.s.len()) {
            None
        } else {
            self.at.partial_cmp(&other.at)
        }
    }
}

impl<'a> std::hash::Hash for StrCursor<'a> {
    fn hash<H>(&self, state: &mut H)
    where H: std::hash::Hasher {
        self.s.as_ptr().hash(state);
        self.s.len().hash(state);
        self.at.hash(state);
    }
}

#[cfg(test)]
#[test]
fn test_new_at_start() {
    let cur = StrCursor::new_at_start("abcdef");
    assert_eq!(cur.slice_before(), "");
    assert_eq!(cur.slice_after(), "abcdef");
}

#[cfg(test)]
#[test]
fn test_new_at_end() {
    let cur = StrCursor::new_at_end("abcdef");
    assert_eq!(cur.slice_before(), "abcdef");
    assert_eq!(cur.slice_after(), "");
}

#[cfg(test)]
#[test]
fn test_new_at_cp_left_of_byte_pos() {
    let s = "This is a 本当 test.";
    let cur = StrCursor::new_at_cp_left_of_byte_pos(s, 11);
    assert_eq!(cur.slice_before(), "This is a ");
    assert_eq!(cur.slice_after(), "本当 test.");
}

#[cfg(test)]
#[test]
fn test_new_at_cp_right_of_byte_pos() {
    let s = "This is a 本当 test.";
    let cur = StrCursor::new_at_cp_right_of_byte_pos(s, 11);
    assert_eq!(cur.slice_before(), "This is a 本");
    assert_eq!(cur.slice_after(), "当 test.");
}

#[cfg(test)]
#[test]
fn test_new_at_left_of_byte_pos() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let r = (0..s.len()+1).map(|i| (i, StrCursor::new_at_left_of_byte_pos(s, i)))
        .map(|(i, cur)| (i, cur.byte_pos(), cur.after().map(Gc::as_str)))
        .collect::<Vec<_>>();
    assert_eq!(r, vec![
        (0, 0, Some("J")),
        (1, 1, Some("ä")),
        (2, 1, Some("ä")),
        (3, 3, Some("g")),
        (4, 4, Some("e")),
        (5, 5, Some("r")),
        (6, 6, Some(",")),
        (7, 7, Some("J")),
        (8, 8, Some("ä")),
        (9, 8, Some("ä")),
        (10, 8, Some("ä")),
        (11, 11, Some("g")),
        (12, 12, Some("e")),
        (13, 13, Some("r")),
        (14, 14, Some(",")),
        (15, 15, Some("大")),
        (16, 15, Some("大")),
        (17, 15, Some("大")),
        (18, 18, Some("嫌")),
        (19, 18, Some("嫌")),
        (20, 18, Some("嫌")),
        (21, 21, Some("い")),
        (22, 21, Some("い")),
        (23, 21, Some("い")),
        (24, 24, Some(",")),
        (25, 25, Some("💪")),
        (26, 25, Some("💪")),
        (27, 25, Some("💪")),
        (28, 25, Some("💪")),
        (29, 29, Some("❤")),
        (30, 29, Some("❤")),
        (31, 29, Some("❤")),
        (32, 32, Some("!")),
        (33, 33, None),
    ]);
}

#[cfg(test)]
#[test]
fn test_new_at_right_of_byte_pos() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let r = (0..s.len()+1).map(|i| (i, StrCursor::new_at_right_of_byte_pos(s, i)))
        .map(|(i, cur)| (i, cur.byte_pos(), cur.after().map(Gc::as_str)))
        .collect::<Vec<_>>();
    assert_eq!(r, vec![
        (0, 0, Some("J")),
        (1, 1, Some("ä")),
        (2, 3, Some("g")),
        (3, 3, Some("g")),
        (4, 4, Some("e")),
        (5, 5, Some("r")),
        (6, 6, Some(",")),
        (7, 7, Some("J")),
        (8, 8, Some("ä")),
        (9, 11, Some("g")),
        (10, 11, Some("g")),
        (11, 11, Some("g")),
        (12, 12, Some("e")),
        (13, 13, Some("r")),
        (14, 14, Some(",")),
        (15, 15, Some("大")),
        (16, 18, Some("嫌")),
        (17, 18, Some("嫌")),
        (18, 18, Some("嫌")),
        (19, 21, Some("い")),
        (20, 21, Some("い")),
        (21, 21, Some("い")),
        (22, 24, Some(",")),
        (23, 24, Some(",")),
        (24, 24, Some(",")),
        (25, 25, Some("💪")),
        (26, 29, Some("❤")),
        (27, 29, Some("❤")),
        (28, 29, Some("❤")),
        (29, 29, Some("❤")),
        (30, 32, Some("!")),
        (31, 32, Some("!")),
        (32, 32, Some("!")),
        (33, 33, None),
    ]);
}

#[cfg(test)]
#[test]
fn test_at_prev_cp() {
    let s = "大嫌い,💪❤";
    let cur = StrCursor::new_at_end(s);
    let bps = test_util::finite_iterate(cur, StrCursor::at_prev_cp)
        .map(|cur| cur.byte_pos())
        .collect::<Vec<_>>();
    assert_eq!(bps, vec![14, 10, 9, 6, 3, 0]);
}

#[cfg(test)]
#[test]
fn test_at_next_cp() {
    let s = "大嫌い,💪❤";
    let cur = StrCursor::new_at_start(s);
    let bps = test_util::finite_iterate(cur, StrCursor::at_next_cp)
        .map(|cur| cur.byte_pos())
        .collect::<Vec<_>>();
    assert_eq!(bps, vec![3, 6, 9, 10, 14, 17]);
}

#[cfg(test)]
#[test]
fn test_at_prev_and_before() {
    let s = "noe\u{0308}l";
    let cur = StrCursor::new_at_end(s);
    let bps = test_util::finite_iterate_lead(cur, StrCursor::at_prev)
        .map(|cur| (cur.byte_pos(), cur.after().map(Gc::as_str)))
        .collect::<Vec<_>>();
    assert_eq!(bps, vec![
        (6, None),
        (5, Some("l")),
        (2, Some("e\u{0308}")),
        (1, Some("o")),
        (0, Some("n")),
    ]);
}

#[cfg(test)]
#[test]
fn test_at_next_and_after() {
    let s = "noe\u{0308}l";
    let cur = StrCursor::new_at_start(s);
    let bps = test_util::finite_iterate_lead(cur, StrCursor::at_next)
        .map(|cur| (cur.byte_pos(), cur.after().map(Gc::as_str)))
        .collect::<Vec<_>>();
    assert_eq!(bps, vec![
        (0, Some("n")),
        (1, Some("o")),
        (2, Some("e\u{0308}")),
        (5, Some("l")),
        (6, None),
    ]);
}

#[cfg(test)]
#[test]
fn test_prev() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let cur = StrCursor::new_at_end(s);
    let r = test_util::finite_iterate_lead(cur, StrCursor::at_prev)
        .map(|cur| cur.prev().map(|(gr, cur)| (gr.as_str(), cur.byte_pos())))
        .collect::<Vec<_>>();
    assert_eq!(r, vec![
        Some(("!", 32)),
        Some(("❤", 29)),
        Some(("💪", 25)),
        Some((",", 24)),
        Some(("い", 21)),
        Some(("嫌", 18)),
        Some(("大", 15)),
        Some((",", 14)),
        Some(("r", 13)),
        Some(("e", 12)),
        Some(("g", 11)),
        Some(("ä", 8)),
        Some(("J", 7)),
        Some((",", 6)),
        Some(("r", 5)),
        Some(("e", 4)),
        Some(("g", 3)),
        Some(("ä", 1)),
        Some(("J", 0)),
        None,
    ]);
}

#[cfg(test)]
#[test]
fn test_prev_cp() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let cur = StrCursor::new_at_end(s);
    let r = test_util::finite_iterate_lead(cur, StrCursor::at_prev_cp)
        .map(|cur| cur.prev_cp().map(|(cp, cur)| (cp, cur.byte_pos())))
        .collect::<Vec<_>>();
    assert_eq!(r, vec![
        Some(('!', 32)),
        Some(('❤', 29)),
        Some(('💪', 25)),
        Some((',', 24)),
        Some(('い', 21)),
        Some(('嫌', 18)),
        Some(('大', 15)),
        Some((',', 14)),
        Some(('r', 13)),
        Some(('e', 12)),
        Some(('g', 11)),
        Some(('̈', 9)),
        Some(('a', 8)),
        Some(('J', 7)),
        Some((',', 6)),
        Some(('r', 5)),
        Some(('e', 4)),
        Some(('g', 3)),
        Some(('ä', 1)),
        Some(('J', 0)),
        None,
    ]);
}

#[cfg(test)]
#[test]
fn test_next() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let cur = StrCursor::new_at_start(s);
    let r = test_util::finite_iterate_lead(cur, StrCursor::at_next)
        .map(|cur| cur.next().map(|(gr, cur)| (gr.as_str(), cur.byte_pos())))
        .collect::<Vec<_>>();
    assert_eq!(r, vec![
        Some(("J", 1)),
        Some(("ä", 3)),
        Some(("g", 4)),
        Some(("e", 5)),
        Some(("r", 6)),
        Some((",", 7)),
        Some(("J", 8)),
        Some(("ä", 11)),
        Some(("g", 12)),
        Some(("e", 13)),
        Some(("r", 14)),
        Some((",", 15)),
        Some(("大", 18)),
        Some(("嫌", 21)),
        Some(("い", 24)),
        Some((",", 25)),
        Some(("💪", 29)),
        Some(("❤", 32)),
        Some(("!", 33)),
        None,
    ]);
}

#[cfg(test)]
#[test]
fn test_next_cp() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let cur = StrCursor::new_at_start(s);
    let r = test_util::finite_iterate_lead(cur, StrCursor::at_next_cp)
        .map(|cur| cur.next_cp().map(|(cp, cur)| (cp, cur.byte_pos())))
        .collect::<Vec<_>>();
    assert_eq!(r, vec![
        Some(('J', 1)),
        Some(('ä', 3)),
        Some(('g', 4)),
        Some(('e', 5)),
        Some(('r', 6)),
        Some((',', 7)),
        Some(('J', 8)),
        Some(('a', 9)),
        Some(('̈', 11)),
        Some(('g', 12)),
        Some(('e', 13)),
        Some(('r', 14)),
        Some((',', 15)),
        Some(('大', 18)),
        Some(('嫌', 21)),
        Some(('い', 24)),
        Some((',', 25)),
        Some(('💪', 29)),
        Some(('❤', 32)),
        Some(('!', 33)),
        None,
    ]);
}

#[cfg(test)]
#[test]
fn test_seek_prev() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let mut cur = StrCursor::new_at_end(s);
    let mut r = vec![];
    for i in 0..19 {
        println!("i: {:?}", i);
        println!("cur.byte_pos(): {:?}", cur.byte_pos());
        cur.seek_prev();
        r.push((cur.after().unwrap().as_str(), cur.byte_pos()));
    }
    assert_eq!(r, vec![
        ("!", 32),
        ("❤", 29),
        ("💪", 25),
        (",", 24),
        ("い", 21),
        ("嫌", 18),
        ("大", 15),
        (",", 14),
        ("r", 13),
        ("e", 12),
        ("g", 11),
        ("ä", 8),
        ("J", 7),
        (",", 6),
        ("r", 5),
        ("e", 4),
        ("g", 3),
        ("ä", 1),
        ("J", 0),
    ]);
}

#[cfg(test)]
#[test]
#[should_panic]
fn test_seek_prev_panic() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let mut cur = StrCursor::new_at_start(s);
    cur.seek_prev();
}

#[cfg(test)]
#[test]
fn test_seek_prev_cp() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let mut cur = StrCursor::new_at_end(s);
    let mut r = vec![];
    for _ in 0..20 {
        cur.seek_prev_cp();
        r.push((cur.cp_after().unwrap(), cur.byte_pos()));
    }
    assert_eq!(r, vec![
        ('!', 32),
        ('❤', 29),
        ('💪', 25),
        (',', 24),
        ('い', 21),
        ('嫌', 18),
        ('大', 15),
        (',', 14),
        ('r', 13),
        ('e', 12),
        ('g', 11),
        ('̈', 9),
        ('a', 8),
        ('J', 7),
        (',', 6),
        ('r', 5),
        ('e', 4),
        ('g', 3),
        ('ä', 1),
        ('J', 0),
    ]);
}

#[cfg(test)]
#[test]
#[should_panic]
fn test_seek_prev_cp_panic() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let mut cur = StrCursor::new_at_start(s);
    cur.seek_prev_cp();
}

#[cfg(test)]
#[test]
fn test_seek_next() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let mut cur = StrCursor::new_at_start(s);
    let mut r = vec![];
    for _ in 0..19 {
        cur.seek_next();
        r.push((cur.before().unwrap().as_str(), cur.byte_pos()));
    }
    assert_eq!(r, vec![
        ("J", 1),
        ("ä", 3),
        ("g", 4),
        ("e", 5),
        ("r", 6),
        (",", 7),
        ("J", 8),
        ("ä", 11),
        ("g", 12),
        ("e", 13),
        ("r", 14),
        (",", 15),
        ("大", 18),
        ("嫌", 21),
        ("い", 24),
        (",", 25),
        ("💪", 29),
        ("❤", 32),
        ("!", 33),
    ]);
}

#[cfg(test)]
#[test]
#[should_panic]
fn test_seek_next_panic() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let mut cur = StrCursor::new_at_end(s);
    cur.seek_next();
}

#[cfg(test)]
#[test]
fn test_seek_next_cp() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let mut cur = StrCursor::new_at_start(s);
    let mut r = vec![];
    for _ in 0..20 {
        cur.seek_next_cp();
        r.push((cur.cp_before().unwrap(), cur.byte_pos()));
    }
    assert_eq!(r, vec![
        ('J', 1),
        ('ä', 3),
        ('g', 4),
        ('e', 5),
        ('r', 6),
        (',', 7),
        ('J', 8),
        ('a', 9),
        ('̈', 11),
        ('g', 12),
        ('e', 13),
        ('r', 14),
        (',', 15),
        ('大', 18),
        ('嫌', 21),
        ('い', 24),
        (',', 25),
        ('💪', 29),
        ('❤', 32),
        ('!', 33),
    ]);
}

#[cfg(test)]
#[test]
#[should_panic]
fn test_seek_next_cp_panic() {
    let s = "Jäger,Jäger,大嫌い,💪❤!";
    let mut cur = StrCursor::new_at_end(s);
    cur.seek_next_cp();
}

#[cfg(test)]
#[test]
fn test_char_before_and_after() {
    let s = "大嫌い,💪❤";
    let cur = StrCursor::new_at_start(s);
    let r = test_util::finite_iterate_lead(cur, StrCursor::at_next_cp)
        .map(|cur| (cur.byte_pos(), cur.cp_before(), cur.cp_after()))
        .collect::<Vec<_>>();
    assert_eq!(r, vec![
        (0, None, Some('大')),
        (3, Some('大'), Some('嫌')),
        (6, Some('嫌'), Some('い')),
        (9, Some('い'), Some(',')),
        (10, Some(','), Some('💪')),
        (14, Some('💪'), Some('❤')),
        (17, Some('❤'), None)
    ]);
}

#[cfg(test)]
#[test]
fn test_slice_between() {
    let s = "they hit, fight, kick, wreak havoc, and rejoice";
    let cur0 = StrCursor::new_at_start(s);
    let cur1 = StrCursor::new_at_end(s);
    let cur2 = StrCursor::new_at_end("nobody knows what they're lookin' for");
    let cur3 = StrCursor::new_at_end(&s[1..]);
    assert_eq!(cur0.slice_between(cur1), Some(s));
    assert_eq!(cur1.slice_between(cur0), Some(s));
    assert_eq!(cur0.slice_between(cur2), None);
    assert_eq!(cur0.slice_between(cur3), None);
}

#[inline]
fn byte_pos_to_ptr(s: &str, byte_pos: usize) -> *const u8 {
    if s.len() < byte_pos {
        panic!("byte position out of bounds: the len is {} but the position is {}",
            s.len(), byte_pos);
    }
    unsafe { s.as_ptr().offset(byte_pos as isize) }
}

#[inline]
unsafe fn seek_utf8_cp_start_left(s: &str, mut from: *const u8) -> *const u8 {
    let beg = s.as_ptr();
    while from > beg && (*from & 0b11_00_0000 == 0b10_00_0000) {
        from = from.offset(-1);
    }
    from
}

#[cfg(test)]
#[test]
fn test_seek_utf8_cp_start_left() {
    let s = "カブム！";
    let b = s.as_bytes();
    assert_eq!(unsafe { seek_utf8_cp_start_left(s, &b[0]) }, &b[0]);
    assert_eq!(unsafe { seek_utf8_cp_start_left(s, &b[1]) }, &b[0]);
    assert_eq!(unsafe { seek_utf8_cp_start_left(s, &b[2]) }, &b[0]);
    assert_eq!(unsafe { seek_utf8_cp_start_left(s, &b[3]) }, &b[3]);
    assert_eq!(unsafe { seek_utf8_cp_start_left(s, &b[4]) }, &b[3]);
    assert_eq!(unsafe { seek_utf8_cp_start_left(s, &b[5]) }, &b[3]);
}

#[inline]
unsafe fn seek_utf8_cp_start_right(s: &str, mut from: *const u8) -> *const u8 {
    let end = s.as_ptr().offset(s.len() as isize);
    while from < end && (*from & 0b11_00_0000 == 0b10_00_0000) {
        from = from.offset(1);
    }
    from
}

#[cfg(test)]
#[test]
fn test_seek_utf8_cp_start_right() {
    let s = "カブム！";
    let b = s.as_bytes();
    assert_eq!(unsafe { seek_utf8_cp_start_right(s, &b[0]) }, &b[0]);
    assert_eq!(unsafe { seek_utf8_cp_start_right(s, &b[1]) }, &b[3]);
    assert_eq!(unsafe { seek_utf8_cp_start_right(s, &b[2]) }, &b[3]);
    assert_eq!(unsafe { seek_utf8_cp_start_right(s, &b[3]) }, &b[3]);
    assert_eq!(unsafe { seek_utf8_cp_start_right(s, &b[4]) }, &b[6]);
    assert_eq!(unsafe { seek_utf8_cp_start_right(s, &b[5]) }, &b[6]);
}

#[inline]
fn str_eq_literal(a: &str, b: &str) -> bool {
    a.as_bytes().as_ptr() == b.as_bytes().as_ptr()
        && a.len() == b.len()
}

#[cfg(test)]
#[test]
fn test_str_eq_literal() {
    let s = "hare hare yukai";
    assert!(str_eq_literal(s, s));
    assert!(str_eq_literal(&s[0..4], &s[0..4]));
    assert!(!str_eq_literal(&s[0..4], &s[5..9]));
    assert!(!str_eq_literal(&s[0..4], &s[0..3]));
}

#[cfg(test)]
mod test_util {
    pub struct FiniteIter<T, F>(Option<T>, F);

    impl<T, F> Iterator for FiniteIter<T, F>
    where
        F: FnMut(T) -> Option<T>,
        T: Clone,
    {
        type Item = T;

        fn next(&mut self) -> Option<Self::Item> {
            self.0.take().and_then(|last| {
                match (self.1)(last) {
                    Some(e) => {
                        self.0 = Some(e);
                        self.0.clone()
                    },
                    None => None
                }
            })
        }
    }

    pub fn finite_iterate<T, F>(seed: T, f: F) -> FiniteIter<T, F>
    where
        F: FnMut(T) -> Option<T>,
        T: Clone,
    {
        FiniteIter(Some(seed), f)
    }
    pub struct FiniteIterLead<T, F>(Option<T>, F, bool);

    impl<T, F> Iterator for FiniteIterLead<T, F>
    where
        F: FnMut(T) -> Option<T>,
        T: Clone,
    {
        type Item = T;

        fn next(&mut self) -> Option<Self::Item> {
            if !self.2 {
                self.2 = true;
                return self.0.clone();
            }

            self.0.take().and_then(|last| {
                match (self.1)(last) {
                    Some(e) => {
                        self.0 = Some(e);
                        self.0.clone()
                    },
                    None => None
                }
            })
        }
    }

    pub fn finite_iterate_lead<T, F>(seed: T, f: F) -> FiniteIterLead<T, F>
    where
        F: FnMut(T) -> Option<T>,
        T: Clone,
    {
        FiniteIterLead(Some(seed), f, false)
    }
}