// Copyright 2016 The Fancy Regex Authors.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

/*!
An implementation of regexes, supporting a relatively rich set of features, including backreferences
and lookaround.

It builds on top of the excellent [regex] crate. If you are not
familiar with it, make sure you read its documentation and maybe you don't even need fancy-regex.

If your regex or parts of it does not use any special features, the matching is delegated to the
regex crate. That means it has linear runtime. But if you use "fancy" features such as
backreferences or look-around, an engine with backtracking needs to be used. In that case, the regex
can be slow and take exponential time to run because of what is called "catastrophic backtracking".
This depends on the regex and the input.

# Usage

The API should feel very similar to the regex crate, and involves compiling a regex and then using
it to find matches in text.

## Example: Matching text

An example with backreferences to check if a text consists of two identical words:

```rust
use fancy_regex::Regex;

let re = Regex::new(r"^(\w+) (\1)$").unwrap();
let result = re.is_match("foo foo");

assert!(result.is_ok());
let did_match = result.unwrap();
assert!(did_match);
```

Note that like in the regex crate, the regex needs anchors like `^` and `$` to match against the
entire input text.

## Example: Finding the position of matches

```rust
use fancy_regex::Regex;

let re = Regex::new(r"(\d)\1").unwrap();
let result = re.find("foo 22");

assert!(result.is_ok(), "execution was successful");
let match_option = result.unwrap();

assert!(match_option.is_some(), "found a match");
let m = match_option.unwrap();

assert_eq!(m.start(), 4);
assert_eq!(m.end(), 6);
assert_eq!(m.as_str(), "22");
```

## Example: Capturing groups

```rust
use fancy_regex::Regex;

let re = Regex::new(r"(?<!AU)\$(\d+)").unwrap();
let result = re.captures("AU$10, $20");

let captures = result.expect("Error running regex").expect("No match found");
let group = captures.get(1).expect("No group");
assert_eq!(group.as_str(), "20");
```

# Syntax

The regex syntax is based on the [regex] crate's, with some additional supported syntax.

Escapes:

`\h`
: hex digit (`[0-9A-Fa-f]`) \
`\H`
: not hex digit (`[^0-9A-Fa-f]`) \
`\e`
: escape control character (`\x1B`)

Backreferences:

`\1`
: match the exact string that the first capture group matched \
`\2`
: backref to the second capture group, etc

Named capture groups:

`(?<name>exp)`
: match *exp*, creating capture group named *name* \
`\k<name>`
: match the exact string that the capture group named *name* matched \
`(?P<name>exp)`
: same as `(?<name>exp)` for compatibility with Python, etc. \
`(?P=name)`
: same as `\k<name>` for compatibility with Python, etc.

Look-around assertions for matching without changing the current position:

`(?=exp)`
: look-ahead, succeeds if *exp* matches to the right of the current position \
`(?!exp)`
: negative look-ahead, succeeds if *exp* doesn't match to the right \
`(?<=exp)`
: look-behind, succeeds if *exp* matches to the left of the current position \
`(?<!exp)`
: negative look-behind, succeeds if *exp* doesn't match to the left

Atomic groups using `(?>exp)` to prevent backtracking within `exp`, e.g.:

```
# use fancy_regex::Regex;
let re = Regex::new(r"^a(?>bc|b)c$").unwrap();
assert!(re.is_match("abcc").unwrap());
// Doesn't match because `|b` is never tried because of the atomic group
assert!(!re.is_match("abc").unwrap());
```

[regex]: https://crates.io/crates/regex
*/

#![doc(html_root_url = "https://docs.rs/fancy-regex/0.5.0")]
#![deny(missing_docs)]
#![deny(missing_debug_implementations)]

use std::fmt;
use std::fmt::{Debug, Formatter};
use std::ops::Range;
use std::sync::Arc;
use std::usize;

mod analyze;
mod compile;
mod error;
mod expand;
mod parse;
mod vm;

use crate::analyze::analyze;
use crate::compile::compile;
use crate::parse::{ExprTree, NamedGroups, Parser};
use crate::vm::Prog;

pub use crate::error::{Error, Result};
pub use crate::expand::Expander;
use std::borrow::Cow;

const MAX_RECURSION: usize = 64;

// the public API

/// A builder for a `Regex` to allow configuring options.
#[derive(Debug)]
pub struct RegexBuilder(RegexOptions);

/// A compiled regular expression.
pub struct Regex {
    inner: RegexImpl,
    named_groups: Arc<NamedGroups>,
}

// Separate enum because we don't want to expose any of this
enum RegexImpl {
    // Do we want to box this? It's pretty big...
    Wrap {
        inner: regex::Regex,
        options: RegexOptions,
    },
    Fancy {
        prog: Prog,
        n_groups: usize,
        options: RegexOptions,
    },
}

/// A single match of a regex or group in an input text
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub struct Match<'t> {
    text: &'t str,
    start: usize,
    end: usize,
}

/// An iterator over all non-overlapping matches for a particular string.
///
/// The iterator yields a `Result<Match>`. The iterator stops when no more
/// matches can be found.
///
/// `'r` is the lifetime of the compiled regular expression and `'t` is the
/// lifetime of the matched string.
#[derive(Debug)]
pub struct Matches<'r, 't> {
    re: &'r Regex,
    text: &'t str,
    last_end: usize,
    last_match: Option<usize>,
}

impl<'r, 't> Matches<'r, 't> {
    /// Return the text being searched.
    pub fn text(&self) -> &'t str {
        self.text
    }

    /// Return the underlying regex.
    pub fn regex(&self) -> &'r Regex {
        &self.re
    }
}

impl<'r, 't> Iterator for Matches<'r, 't> {
    type Item = Result<Match<'t>>;

    /// Adapted from the `regex` crate. Calls `find_from_pos` repeatedly.
    /// Ignores empty matches immediately after a match.
    fn next(&mut self) -> Option<Self::Item> {
        if self.last_end > self.text.len() {
            return None;
        }

        let mat = match self.re.find_from_pos(self.text, self.last_end) {
            Err(error) => return Some(Err(error)),
            Ok(None) => return None,
            Ok(Some(mat)) => mat,
        };

        if mat.start == mat.end {
            // This is an empty match. To ensure we make progress, start
            // the next search at the smallest possible starting position
            // of the next match following this one.
            self.last_end = next_utf8(self.text, mat.end);
            // Don't accept empty matches immediately following a match.
            // Just move on to the next match.
            if Some(mat.end) == self.last_match {
                return self.next();
            }
        } else {
            self.last_end = mat.end;
        }

        self.last_match = Some(mat.end);

        Some(Ok(mat))
    }
}

/// An iterator that yields all non-overlapping capture groups matching a
/// particular regular expression.
///
/// The iterator stops when no more matches can be found.
///
/// `'r` is the lifetime of the compiled regular expression and `'t` is the
/// lifetime of the matched string.
#[derive(Debug)]
pub struct CaptureMatches<'r, 't>(Matches<'r, 't>);

impl<'r, 't> CaptureMatches<'r, 't> {
    /// Return the text being searched.
    pub fn text(&self) -> &'t str {
        self.0.text
    }

    /// Return the underlying regex.
    pub fn regex(&self) -> &'r Regex {
        &self.0.re
    }
}

impl<'r, 't> Iterator for CaptureMatches<'r, 't> {
    type Item = Result<Captures<'t>>;

    /// Adapted from the `regex` crate. Calls `captures_from_pos` repeatedly.
    /// Ignores empty matches immediately after a match.
    fn next(&mut self) -> Option<Self::Item> {
        if self.0.last_end > self.0.text.len() {
            return None;
        }

        let captures = match self.0.re.captures_from_pos(self.0.text, self.0.last_end) {
            Err(error) => return Some(Err(error)),
            Ok(None) => return None,
            Ok(Some(captures)) => captures,
        };

        let mat = captures
            .get(0)
            .expect("`Captures` is expected to have entire match at 0th position");
        if mat.start == mat.end {
            self.0.last_end = next_utf8(self.0.text, mat.end);
            if Some(mat.end) == self.0.last_match {
                return self.next();
            }
        } else {
            self.0.last_end = mat.end;
        }

        self.0.last_match = Some(mat.end);

        Some(Ok(captures))
    }
}

/// A set of capture groups found for a regex.
#[derive(Debug)]
pub struct Captures<'t> {
    inner: CapturesImpl<'t>,
    named_groups: Arc<NamedGroups>,
}

#[derive(Debug)]
enum CapturesImpl<'t> {
    Wrap {
        text: &'t str,
        locations: regex::CaptureLocations,
    },
    Fancy {
        text: &'t str,
        saves: Vec<usize>,
    },
}

/// Iterator for captured groups in order in which they appear in the regex.
#[derive(Debug)]
pub struct SubCaptureMatches<'c, 't> {
    caps: &'c Captures<'t>,
    i: usize,
}

#[derive(Clone, Debug)]
struct RegexOptions {
    pattern: String,
    backtrack_limit: usize,
    delegate_size_limit: Option<usize>,
    delegate_dfa_size_limit: Option<usize>,
}

impl Default for RegexOptions {
    fn default() -> Self {
        RegexOptions {
            pattern: String::new(),
            backtrack_limit: 1_000_000,
            delegate_size_limit: None,
            delegate_dfa_size_limit: None,
        }
    }
}

impl RegexBuilder {
    /// Create a new regex builder with a regex pattern.
    ///
    /// If the pattern is invalid, the call to `build` will fail later.
    pub fn new(pattern: &str) -> Self {
        let mut builder = RegexBuilder(RegexOptions::default());
        builder.0.pattern = pattern.to_string();
        builder
    }

    /// Build the `Regex`.
    ///
    /// Returns an [`Error`](enum.Error.html) if the pattern could not be parsed.
    pub fn build(&self) -> Result<Regex> {
        Regex::new_options(self.0.clone())
    }

    /// Limit for how many times backtracking should be attempted for fancy regexes (where
    /// backtracking is used). If this limit is exceeded, execution returns an error with
    /// [`Error::BacktrackLimitExceeded`](enum.Error.html#variant.BacktrackLimitExceeded).
    /// This is for preventing a regex with catastrophic backtracking to run for too long.
    ///
    /// Default is `1_000_000` (1 million).
    pub fn backtrack_limit(&mut self, limit: usize) -> &mut Self {
        self.0.backtrack_limit = limit;
        self
    }

    /// Set the approximate size limit of the compiled regular expression.
    ///
    /// This option is forwarded from the wrapped `regex` crate. Note that depending on the used
    /// regex features there may be multiple delegated sub-regexes fed to the `regex` crate. As
    /// such the actual limit is closer to `<number of delegated regexes> * delegate_size_limit`.
    pub fn delegate_size_limit(&mut self, limit: usize) -> &mut Self {
        self.0.delegate_size_limit = Some(limit);
        self
    }

    /// Set the approximate size of the cache used by the DFA.
    ///
    /// This option is forwarded from the wrapped `regex` crate. Note that depending on the used
    /// regex features there may be multiple delegated sub-regexes fed to the `regex` crate. As
    /// such the actual limit is closer to `<number of delegated regexes> *
    /// delegate_dfa_size_limit`.
    pub fn delegate_dfa_size_limit(&mut self, limit: usize) -> &mut Self {
        self.0.delegate_dfa_size_limit = Some(limit);
        self
    }
}

impl fmt::Debug for Regex {
    /// Shows the original regular expression.
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.as_str())
    }
}

impl Regex {
    /// Parse and compile a regex with default options, see `RegexBuilder`.
    ///
    /// Returns an [`Error`](enum.Error.html) if the pattern could not be parsed.
    pub fn new(re: &str) -> Result<Regex> {
        let options = RegexOptions {
            pattern: re.to_string(),
            ..RegexOptions::default()
        };
        Self::new_options(options)
    }

    fn new_options(options: RegexOptions) -> Result<Regex> {
        let raw_tree = Expr::parse_tree(&options.pattern)?;

        // wrapper to search for re at arbitrary start position,
        // and to capture the match bounds
        let tree = ExprTree {
            expr: Expr::Concat(vec![
                Expr::Repeat {
                    child: Box::new(Expr::Any { newline: true }),
                    lo: 0,
                    hi: usize::MAX,
                    greedy: false,
                },
                Expr::Group(Box::new(raw_tree.expr)),
            ]),
            ..raw_tree
        };

        let info = analyze(&tree)?;

        let inner_info = &info.children[1].children[0]; // references inner expr
        if !inner_info.hard {
            // easy case, wrap regex

            // we do our own to_str because escapes are different
            let mut re_cooked = String::new();
            // same as raw_tree.expr above, but it was moved, so traverse to find it
            let raw_e = match tree.expr {
                Expr::Concat(ref v) => match v[1] {
                    Expr::Group(ref child) => child,
                    _ => unreachable!(),
                },
                _ => unreachable!(),
            };
            raw_e.to_str(&mut re_cooked, 0);
            let inner = compile::compile_inner(&re_cooked, &options)?;
            return Ok(Regex {
                inner: RegexImpl::Wrap { inner, options },
                named_groups: Arc::new(tree.named_groups),
            });
        }

        let prog = compile(&info)?;
        Ok(Regex {
            inner: RegexImpl::Fancy {
                prog,
                n_groups: info.end_group,
                options,
            },
            named_groups: Arc::new(tree.named_groups),
        })
    }

    /// Returns the original string of this regex.
    pub fn as_str(&self) -> &str {
        match &self.inner {
            RegexImpl::Wrap { options, .. } => &options.pattern,
            RegexImpl::Fancy { options, .. } => &options.pattern,
        }
    }

    /// Check if the regex matches the input text.
    ///
    /// # Example
    ///
    /// Test if some text contains the same word twice:
    ///
    /// ```rust
    /// # use fancy_regex::Regex;
    ///
    /// let re = Regex::new(r"(\w+) \1").unwrap();
    /// assert!(re.is_match("mirror mirror on the wall").unwrap());
    /// ```
    pub fn is_match(&self, text: &str) -> Result<bool> {
        match &self.inner {
            RegexImpl::Wrap { ref inner, .. } => Ok(inner.is_match(text)),
            RegexImpl::Fancy {
                ref prog, options, ..
            } => {
                let result = vm::run(prog, text, 0, 0, options)?;
                Ok(result.is_some())
            }
        }
    }

    /// Returns an iterator for each successive non-overlapping match in `text`.
    ///
    /// If you have capturing groups in your regex that you want to extract, use the [Regex::captures_iter()]
    /// method.
    ///
    /// # Example
    ///
    /// Find all words followed by an exclamation point:
    ///
    /// ```rust
    /// # use fancy_regex::Regex;
    ///
    /// let re = Regex::new(r"\w+(?=!)").unwrap();
    /// let mut matches = re.find_iter("so fancy! even with! iterators!");
    /// assert_eq!(matches.next().unwrap().unwrap().as_str(), "fancy");
    /// assert_eq!(matches.next().unwrap().unwrap().as_str(), "with");
    /// assert_eq!(matches.next().unwrap().unwrap().as_str(), "iterators");
    /// assert!(matches.next().is_none());
    /// ```
    pub fn find_iter<'r, 't>(&'r self, text: &'t str) -> Matches<'r, 't> {
        Matches {
            re: &self,
            text,
            last_end: 0,
            last_match: None,
        }
    }

    /// Find the first match in the input text.
    ///
    /// If you have capturing groups in your regex that you want to extract, use the [Regex::captures()]
    /// method.
    ///
    /// # Example
    ///
    /// Find a word that is followed by an exclamation point:
    ///
    /// ```rust
    /// # use fancy_regex::Regex;
    ///
    /// let re = Regex::new(r"\w+(?=!)").unwrap();
    /// assert_eq!(re.find("so fancy!").unwrap().unwrap().as_str(), "fancy");
    /// ```
    pub fn find<'t>(&self, text: &'t str) -> Result<Option<Match<'t>>> {
        self.find_from_pos(text, 0)
    }

    /// Returns the first match in `text`, starting from the specified byte position `pos`.
    ///
    /// # Examples
    ///
    /// Finding match starting at a position:
    ///
    /// ```
    /// # use fancy_regex::Regex;
    /// let re = Regex::new(r"(?m:^)(\d+)").unwrap();
    /// let text = "1 test 123\n2 foo";
    /// let mat = re.find_from_pos(text, 7).unwrap().unwrap();
    ///
    /// assert_eq!(mat.start(), 11);
    /// assert_eq!(mat.end(), 12);
    /// ```
    ///
    /// Note that in some cases this is not the same as using the `find`
    /// method and passing a slice of the string, see [Regex::captures_from_pos()] for details.
    pub fn find_from_pos<'t>(&self, text: &'t str, pos: usize) -> Result<Option<Match<'t>>> {
        match &self.inner {
            RegexImpl::Wrap { inner, .. } => Ok(inner
                .find_at(text, pos)
                .map(|m| Match::new(text, m.start(), m.end()))),
            RegexImpl::Fancy { prog, options, .. } => {
                let result = vm::run(prog, text, pos, 0, options)?;
                Ok(result.map(|saves| Match::new(text, saves[0], saves[1])))
            }
        }
    }

    /// Returns an iterator over all the non-overlapping capture groups matched in `text`.
    ///
    /// # Examples
    ///
    /// Finding all matches and capturing parts of each:
    ///
    /// ```rust
    /// # use fancy_regex::Regex;
    ///
    /// let re = Regex::new(r"(\d{4})-(\d{2})").unwrap();
    /// let text = "It was between 2018-04 and 2020-01";
    /// let mut all_captures = re.captures_iter(text);
    ///
    /// let first = all_captures.next().unwrap().unwrap();
    /// assert_eq!(first.get(1).unwrap().as_str(), "2018");
    /// assert_eq!(first.get(2).unwrap().as_str(), "04");
    /// assert_eq!(first.get(0).unwrap().as_str(), "2018-04");
    ///
    /// let second = all_captures.next().unwrap().unwrap();
    /// assert_eq!(second.get(1).unwrap().as_str(), "2020");
    /// assert_eq!(second.get(2).unwrap().as_str(), "01");
    /// assert_eq!(second.get(0).unwrap().as_str(), "2020-01");
    ///
    /// assert!(all_captures.next().is_none());
    /// ```
    pub fn captures_iter<'r, 't>(&'r self, text: &'t str) -> CaptureMatches<'r, 't> {
        CaptureMatches(self.find_iter(text))
    }

    /// Returns the capture groups for the first match in `text`.
    ///
    /// If no match is found, then `Ok(None)` is returned.
    ///
    /// # Examples
    ///
    /// Finding matches and capturing parts of the match:
    ///
    /// ```rust
    /// # use fancy_regex::Regex;
    ///
    /// let re = Regex::new(r"(\d{4})-(\d{2})-(\d{2})").unwrap();
    /// let text = "The date was 2018-04-07";
    /// let captures = re.captures(text).unwrap().unwrap();
    ///
    /// assert_eq!(captures.get(1).unwrap().as_str(), "2018");
    /// assert_eq!(captures.get(2).unwrap().as_str(), "04");
    /// assert_eq!(captures.get(3).unwrap().as_str(), "07");
    /// assert_eq!(captures.get(0).unwrap().as_str(), "2018-04-07");
    /// ```
    pub fn captures<'t>(&self, text: &'t str) -> Result<Option<Captures<'t>>> {
        self.captures_from_pos(text, 0)
    }

    /// Returns the capture groups for the first match in `text`, starting from
    /// the specified byte position `pos`.
    ///
    /// # Examples
    ///
    /// Finding captures starting at a position:
    ///
    /// ```
    /// # use fancy_regex::Regex;
    /// let re = Regex::new(r"(?m:^)(\d+)").unwrap();
    /// let text = "1 test 123\n2 foo";
    /// let captures = re.captures_from_pos(text, 7).unwrap().unwrap();
    ///
    /// let group = captures.get(1).unwrap();
    /// assert_eq!(group.as_str(), "2");
    /// assert_eq!(group.start(), 11);
    /// assert_eq!(group.end(), 12);
    /// ```
    ///
    /// Note that in some cases this is not the same as using the `captures`
    /// method and passing a slice of the string, see the capture that we get
    /// when we do this:
    ///
    /// ```
    /// # use fancy_regex::Regex;
    /// let re = Regex::new(r"(?m:^)(\d+)").unwrap();
    /// let text = "1 test 123\n2 foo";
    /// let captures = re.captures(&text[7..]).unwrap().unwrap();
    /// assert_eq!(captures.get(1).unwrap().as_str(), "123");
    /// ```
    ///
    /// This matched the number "123" because it's at the beginning of the text
    /// of the string slice.
    ///
    pub fn captures_from_pos<'t>(&self, text: &'t str, pos: usize) -> Result<Option<Captures<'t>>> {
        let named_groups = self.named_groups.clone();
        match &self.inner {
            RegexImpl::Wrap { inner, .. } => {
                let mut locations = inner.capture_locations();
                let result = inner.captures_read_at(&mut locations, text, pos);
                Ok(result.map(|_| Captures {
                    inner: CapturesImpl::Wrap { text, locations },
                    named_groups,
                }))
            }
            RegexImpl::Fancy {
                prog,
                n_groups,
                options,
                ..
            } => {
                let result = vm::run(prog, text, pos, 0, options)?;
                Ok(result.map(|mut saves| {
                    saves.truncate(n_groups * 2);
                    Captures {
                        inner: CapturesImpl::Fancy { text, saves },
                        named_groups,
                    }
                }))
            }
        }
    }

    /// Returns the number of captures, including the implicit capture of the entire expression.
    pub fn captures_len(&self) -> usize {
        match &self.inner {
            RegexImpl::Wrap { inner, .. } => inner.captures_len(),
            RegexImpl::Fancy { n_groups, .. } => *n_groups,
        }
    }

    /// Returns an iterator over the capture names.
    pub fn capture_names(&self) -> CaptureNames {
        let mut names = Vec::new();
        names.resize(self.captures_len(), None);
        for (name, &i) in self.named_groups.iter() {
            names[i] = Some(name.as_str());
        }
        CaptureNames(names.into_iter())
    }

    // for debugging only
    #[doc(hidden)]
    pub fn debug_print(&self) {
        match &self.inner {
            RegexImpl::Wrap { inner, .. } => println!("wrapped {:?}", inner),
            RegexImpl::Fancy { prog, .. } => prog.debug_print(),
        }
    }
}

impl<'t> Match<'t> {
    /// Returns the starting byte offset of the match in the text.
    #[inline]
    pub fn start(&self) -> usize {
        self.start
    }

    /// Returns the ending byte offset of the match in the text.
    #[inline]
    pub fn end(&self) -> usize {
        self.end
    }

    /// Returns the range over the starting and ending byte offsets of the match in text.
    #[inline]
    pub fn range(&self) -> Range<usize> {
        self.start..self.end
    }

    /// Returns the matched text.
    #[inline]
    pub fn as_str(&self) -> &'t str {
        &self.text[self.start..self.end]
    }

    /// Creates a new match from the given text and byte offsets.
    fn new(text: &'t str, start: usize, end: usize) -> Match<'t> {
        Match { text, start, end }
    }
}

impl<'t> From<Match<'t>> for &'t str {
    fn from(m: Match<'t>) -> &'t str {
        m.as_str()
    }
}

impl<'t> From<Match<'t>> for Range<usize> {
    fn from(m: Match<'t>) -> Range<usize> {
        m.range()
    }
}

#[allow(clippy::len_without_is_empty)] // follow regex's API
impl<'t> Captures<'t> {
    /// Get the capture group by its index in the regex.
    ///
    /// If there is no match for that group or the index does not correspond to a group, `None` is
    /// returned. The index 0 returns the whole match.
    pub fn get(&self, i: usize) -> Option<Match<'t>> {
        match &self.inner {
            CapturesImpl::Wrap { text, locations } => {
                locations
                    .get(i)
                    .map(|(start, end)| Match { text, start, end })
            }
            CapturesImpl::Fancy { text, ref saves } => {
                let slot = i * 2;
                if slot >= saves.len() {
                    return None;
                }
                let lo = saves[slot];
                if lo == std::usize::MAX {
                    return None;
                }
                let hi = saves[slot + 1];
                Some(Match {
                    text,
                    start: lo,
                    end: hi,
                })
            }
        }
    }

    /// Returns the match for a named capture group.  Returns `None` the capture
    /// group did not match or if there is no group with the given name.
    pub fn name(&self, name: &str) -> Option<Match<'t>> {
        self.named_groups.get(name).and_then(|i| self.get(*i))
    }

    /// Expands all instances of `$group` in `replacement` to the corresponding
    /// capture group `name`, and writes them to the `dst` buffer given.
    ///
    /// `group` may be an integer corresponding to the index of the
    /// capture group (counted by order of opening parenthesis where `\0` is the
    /// entire match) or it can be a name (consisting of letters, digits or
    /// underscores) corresponding to a named capture group.
    ///
    /// If `group` isn't a valid capture group (whether the name doesn't exist
    /// or isn't a valid index), then it is replaced with the empty string.
    ///
    /// The longest possible name is used. e.g., `$1a` looks up the capture
    /// group named `1a` and not the capture group at index `1`. To exert more
    /// precise control over the name, use braces, e.g., `${1}a`.
    ///
    /// To write a literal `$`, use `$$`.
    ///
    /// For more control over expansion, see [`Expander`].
    ///
    /// [`Expander`]: expand/struct.Expander.html
    pub fn expand(&self, replacement: &str, dst: &mut String) {
        Expander::default().append_expansion(dst, replacement, self);
    }

    /// Iterate over the captured groups in order in which they appeared in the regex. The first
    /// capture corresponds to the whole match.
    pub fn iter<'c>(&'c self) -> SubCaptureMatches<'c, 't> {
        SubCaptureMatches { caps: self, i: 0 }
    }

    /// How many groups were captured. This is always at least 1 because group 0 returns the whole
    /// match.
    pub fn len(&self) -> usize {
        match &self.inner {
            CapturesImpl::Wrap { locations, .. } => locations.len(),
            CapturesImpl::Fancy { saves, .. } => saves.len() / 2,
        }
    }
}

impl<'c, 't> Iterator for SubCaptureMatches<'c, 't> {
    type Item = Option<Match<'t>>;

    fn next(&mut self) -> Option<Option<Match<'t>>> {
        if self.i < self.caps.len() {
            let result = self.caps.get(self.i);
            self.i += 1;
            Some(result)
        } else {
            None
        }
    }
}

// TODO: might be nice to implement ExactSizeIterator etc for SubCaptures

/// Regular expression AST. This is public for now but may change.
#[derive(Debug, PartialEq, Eq)]
pub enum Expr {
    /// An empty expression, e.g. the last branch in `(a|b|)`
    Empty,
    /// Any character, regex `.`
    Any {
        /// Whether it also matches newlines or not
        newline: bool,
    },
    /// Start of input text
    StartText,
    /// End of input text
    EndText,
    /// Start of a line
    StartLine,
    /// End of a line
    EndLine,
    /// The string as a literal, e.g. `a`
    Literal {
        /// The string to match
        val: String,
        /// Whether match is case-insensitive or not
        casei: bool,
    },
    /// Concatenation of multiple expressions, must match in order, e.g. `a.` is a concatenation of
    /// the literal `a` and `.` for any character
    Concat(Vec<Expr>),
    /// Alternative of multiple expressions, one of them must match, e.g. `a|b` is an alternative
    /// where either the literal `a` or `b` must match
    Alt(Vec<Expr>),
    /// Capturing group of expression, e.g. `(a.)` matches `a` and any character and "captures"
    /// (remembers) the match
    Group(Box<Expr>),
    /// Look-around (e.g. positive/negative look-ahead or look-behind) with an expression, e.g.
    /// `(?=a)` means the next character must be `a` (but the match is not consumed)
    LookAround(Box<Expr>, LookAround),
    /// Repeat of an expression, e.g. `a*` or `a+` or `a{1,3}`
    Repeat {
        /// The expression that is being repeated
        child: Box<Expr>,
        /// The minimum number of repetitions
        lo: usize,
        /// The maximum number of repetitions (or `usize::MAX`)
        hi: usize,
        /// Greedy means as much as possible is matched, e.g. `.*b` would match all of `abab`.
        /// Non-greedy means as little as possible, e.g. `.*?b` would match only `ab` in `abab`.
        greedy: bool,
    },
    /// Delegate a regex to the regex crate. This is used as a simplification so that we don't have
    /// to represent all the expressions in the AST, e.g. character classes.
    Delegate {
        /// The regex
        inner: String,
        /// How many characters the regex matches
        size: usize, // TODO: move into analysis result
        /// Whether the matching is case-insensitive or not
        casei: bool,
    },
    /// Back reference to a capture group, e.g. `\1` in `(abc|def)\1` references the captured group
    /// and the whole regex matches either `abcabc` or `defdef`.
    Backref(usize),
    /// Back reference to a named capture group.
    NamedBackref(String),
    /// Atomic non-capturing group, e.g. `(?>ab|a)` in text that contains `ab` will match `ab` and
    /// never backtrack and try `a`, even if matching fails after the atomic group.
    AtomicGroup(Box<Expr>),
}

/// Type of look-around assertion as used for a look-around expression.
#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum LookAround {
    /// Look-ahead assertion, e.g. `(?=a)`
    LookAhead,
    /// Negative look-ahead assertion, e.g. `(?!a)`
    LookAheadNeg,
    /// Look-behind assertion, e.g. `(?<=a)`
    LookBehind,
    /// Negative look-behind assertion, e.g. `(?<!a)`
    LookBehindNeg,
}

/// An iterator over capture names in a [Regex].  The iterator
/// returns the name of each group, or [None] if the group has
/// no name.  Because capture group 0 cannot have a name, the
/// first item returned is always [None].
pub struct CaptureNames<'r>(std::vec::IntoIter<Option<&'r str>>);

impl Debug for CaptureNames<'_> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        f.write_str("<CaptureNames>")
    }
}

impl<'r> Iterator for CaptureNames<'r> {
    type Item = Option<&'r str>;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }
}

// silly to write my own, but this is super-fast for the common 1-digit
// case.
fn push_usize(s: &mut String, x: usize) {
    if x >= 10 {
        push_usize(s, x / 10);
        s.push((b'0' + (x % 10) as u8) as char);
    } else {
        s.push((b'0' + (x as u8)) as char);
    }
}

fn is_special(c: char) -> bool {
    match c {
        '\\' | '.' | '+' | '*' | '?' | '(' | ')' | '|' | '[' | ']' | '{' | '}' | '^' | '$'
        | '#' => true,
        _ => false,
    }
}

fn push_quoted(buf: &mut String, s: &str) {
    for c in s.chars() {
        if is_special(c) {
            buf.push('\\');
        }
        buf.push(c);
    }
}

/// Escapes special characters in `text` with '\\'.  Returns a string which, when interpreted
/// as a regex, matches exactly `text`.
pub fn escape(text: &str) -> Cow<str> {
    // Using bytes() is OK because all special characters are single bytes.
    match text.bytes().filter(|&b| is_special(b as char)).count() {
        0 => Cow::Borrowed(text),
        n => {
            // The capacity calculation is exact because '\\' is a single byte.
            let mut buf = String::with_capacity(text.len() + n);
            push_quoted(&mut buf, text);
            Cow::Owned(buf)
        }
    }
}

impl Expr {
    /// Parse the regex and return an expression (AST) and a bit set with the indexes of groups
    /// that are referenced by backrefs.
    pub fn parse_tree(re: &str) -> Result<ExprTree> {
        Parser::parse(re)
    }

    /// Convert expression to a regex string in the regex crate's syntax.
    ///
    /// # Panics
    ///
    /// Panics for expressions that are hard, i.e. can not be handled by the regex crate.
    pub fn to_str(&self, buf: &mut String, precedence: u8) {
        match *self {
            Expr::Empty => (),
            Expr::Any { newline } => buf.push_str(if newline { "(?s:.)" } else { "." }),
            Expr::Literal { ref val, casei } => {
                if casei {
                    buf.push_str("(?i:");
                }
                push_quoted(buf, val);
                if casei {
                    buf.push_str(")");
                }
            }
            Expr::StartText => buf.push('^'),
            Expr::EndText => buf.push('$'),
            Expr::StartLine => buf.push_str("(?m:^)"),
            Expr::EndLine => buf.push_str("(?m:$)"),
            Expr::Concat(ref children) => {
                if precedence > 1 {
                    buf.push_str("(?:");
                }
                for child in children {
                    child.to_str(buf, 2);
                }
                if precedence > 1 {
                    buf.push(')')
                }
            }
            Expr::Alt(ref children) => {
                if precedence > 0 {
                    buf.push_str("(?:");
                }

                let is_empty = |e: &Expr| match e {
                    Expr::Empty => true,
                    _ => false,
                };

                let contains_empty = children.iter().any(is_empty);
                if contains_empty {
                    buf.push_str("(?:");
                }
                for (i, child) in children.iter().filter(|&c| !is_empty(c)).enumerate() {
                    if i != 0 {
                        buf.push('|');
                    }
                    child.to_str(buf, 1);
                }
                if contains_empty {
                    // regex fails with `(a|b|)`, so transform to `((?:a|b)?)`
                    buf.push_str(")?");
                }

                if precedence > 0 {
                    buf.push(')');
                }
            }
            Expr::Group(ref child) => {
                buf.push('(');
                child.to_str(buf, 0);
                buf.push(')');
            }
            Expr::Repeat {
                ref child,
                lo,
                hi,
                greedy,
            } => {
                if precedence > 2 {
                    buf.push_str("(?:");
                }
                child.to_str(buf, 3);
                match (lo, hi) {
                    (0, 1) => buf.push('?'),
                    (0, usize::MAX) => buf.push('*'),
                    (1, usize::MAX) => buf.push('+'),
                    (lo, hi) => {
                        buf.push('{');
                        push_usize(buf, lo);
                        if lo != hi {
                            buf.push(',');
                            if hi != usize::MAX {
                                push_usize(buf, hi);
                            }
                        }
                        buf.push('}');
                    }
                }
                if !greedy {
                    buf.push('?');
                }
                if precedence > 2 {
                    buf.push(')');
                }
            }
            Expr::Delegate {
                ref inner, casei, ..
            } => {
                // at the moment, delegate nodes are just atoms
                if casei {
                    buf.push_str("(?i:");
                }
                buf.push_str(inner);
                if casei {
                    buf.push_str(")");
                }
            }
            _ => panic!("attempting to format hard expr"),
        }
    }
}

// precondition: ix > 0
fn prev_codepoint_ix(s: &str, mut ix: usize) -> usize {
    let bytes = s.as_bytes();
    loop {
        ix -= 1;
        // fancy bit magic for ranges 0..0x80 + 0xc0..
        if (bytes[ix] as i8) >= -0x40 {
            break;
        }
    }
    ix
}

fn codepoint_len(b: u8) -> usize {
    match b {
        b if b < 0x80 => 1,
        b if b < 0xe0 => 2,
        b if b < 0xf0 => 3,
        _ => 4,
    }
}

/// Returns the smallest possible index of the next valid UTF-8 sequence
/// starting after `i`.
/// Adapted from a function with the same name in the `regex` crate.
fn next_utf8(text: &str, i: usize) -> usize {
    let b = match text.as_bytes().get(i) {
        None => return i + 1,
        Some(&b) => b,
    };
    i + codepoint_len(b)
}

// If this returns false, then there is no possible backref in the re

// Both potential implementations are turned off, because we currently
// always need to do a deeper analysis because of 1-character
// look-behind. If we could call a find_from_pos method of regex::Regex,
// it would make sense to bring this back.
/*
pub fn detect_possible_backref(re: &str) -> bool {
    let mut last = b'\x00';
    for b in re.as_bytes() {
        if b'0' <= *b && *b <= b'9' && last == b'\\' { return true; }
        last = *b;
    }
    false
}

pub fn detect_possible_backref(re: &str) -> bool {
    let mut bytes = re.as_bytes();
    loop {
        match memchr::memchr(b'\\', &bytes[..bytes.len() - 1]) {
            Some(i) => {
                bytes = &bytes[i + 1..];
                let c = bytes[0];
                if b'0' <= c && c <= b'9' { return true; }
            }
            None => return false
        }
    }
}
*/

/// The internal module only exists so that the toy example can access internals for debugging and
/// experimenting.
#[doc(hidden)]
pub mod internal {
    pub use crate::analyze::analyze;
    pub use crate::compile::compile;
    pub use crate::vm::{run_default, run_trace, Insn, Prog};
}

#[cfg(test)]
mod tests {
    use crate::parse::make_literal;
    use crate::Expr;
    use crate::Regex;
    use std::borrow::Cow;
    use std::usize;
    //use detect_possible_backref;

    // tests for to_str

    fn to_str(e: Expr) -> String {
        let mut s = String::new();
        e.to_str(&mut s, 0);
        s
    }

    #[test]
    fn to_str_concat_alt() {
        let e = Expr::Concat(vec![
            Expr::Alt(vec![make_literal("a"), make_literal("b")]),
            make_literal("c"),
        ]);
        assert_eq!(to_str(e), "(?:a|b)c");
    }

    #[test]
    fn to_str_rep_concat() {
        let e = Expr::Repeat {
            child: Box::new(Expr::Concat(vec![make_literal("a"), make_literal("b")])),
            lo: 2,
            hi: 3,
            greedy: true,
        };
        assert_eq!(to_str(e), "(?:ab){2,3}");
    }

    #[test]
    fn to_str_group_alt() {
        let e = Expr::Group(Box::new(Expr::Alt(vec![
            make_literal("a"),
            make_literal("b"),
        ])));
        assert_eq!(to_str(e), "(a|b)");
    }

    #[test]
    fn as_str_debug() {
        let s = r"(a+)b\1";
        let regex = Regex::new(s).unwrap();
        assert_eq!(s, regex.as_str());
        assert_eq!(s, format!("{:?}", regex));
    }

    #[test]
    fn to_str_repeat() {
        fn repeat(lo: usize, hi: usize, greedy: bool) -> Expr {
            Expr::Repeat {
                child: Box::new(make_literal("a")),
                lo,
                hi,
                greedy,
            }
        }

        assert_eq!(to_str(repeat(2, 2, true)), "a{2}");
        assert_eq!(to_str(repeat(2, 2, false)), "a{2}?");
        assert_eq!(to_str(repeat(2, 3, true)), "a{2,3}");
        assert_eq!(to_str(repeat(2, 3, false)), "a{2,3}?");
        assert_eq!(to_str(repeat(2, usize::MAX, true)), "a{2,}");
        assert_eq!(to_str(repeat(2, usize::MAX, false)), "a{2,}?");
        assert_eq!(to_str(repeat(0, 1, true)), "a?");
        assert_eq!(to_str(repeat(0, 1, false)), "a??");
        assert_eq!(to_str(repeat(0, usize::MAX, true)), "a*");
        assert_eq!(to_str(repeat(0, usize::MAX, false)), "a*?");
        assert_eq!(to_str(repeat(1, usize::MAX, true)), "a+");
        assert_eq!(to_str(repeat(1, usize::MAX, false)), "a+?");
    }

    #[test]
    fn escape() {
        // Check that strings that need no quoting are borrowed, and that non-special punctuation
        // is not quoted.
        match crate::escape("@foo") {
            Cow::Borrowed(s) => assert_eq!(s, "@foo"),
            _ => panic!("Value should be borrowed."),
        }

        // Check typical usage.
        assert_eq!(crate::escape("fo*o").into_owned(), "fo\\*o");

        // Check that multibyte characters are handled correctly.
        assert_eq!(crate::escape("fø*ø").into_owned(), "fø\\*ø");
    }

    /*
    #[test]
    fn detect_backref() {
        assert_eq!(detect_possible_backref("a0a1a2"), false);
        assert_eq!(detect_possible_backref("a0a1\\a2"), false);
        assert_eq!(detect_possible_backref("a0a\\1a2"), true);
        assert_eq!(detect_possible_backref("a0a1a2\\"), false);
    }
    */
}