github:[raphlinus, robinst]

github:[raphlinus, robinst, keith-hall]

This project adheres to[Semantic Versioning](http://semver.org/spec/v2.0.0.html),

with the exception that 0.x versions can break between minor versions.

- Add an optimization step after the pattern is parsed but before it is analyzed.

Currently it only optimizes one specific use-case - where the expression is easy except

for a trailing positive lookahead whose contents are also easy. The optimization is to avoid the VM.

- Support`\Z` - anchor to the end of the text before any trailing newlines. (#148)

[package]

name ="fancy-regex"

version ="0.15.0"

authors = ["Raph Levien <raph@google.com>","Robin Stocker <robin@nibor.org>"]

authors = ["Raph Levien <raph@google.com>","Robin Stocker <robin@nibor.org>","Keith Hall <keith.hall@available.systems>"]

edition ="2018"

license ="MIT"

description ="An implementation of regexes, supporting a relatively rich set of features, including backreferences and look-around."

Let's look at the regex from the README again:

And the input text:

Let's look at another regex, one that makes use of a "fancy" look-ahead:

When fancy-regex matches it against this input:

It's slow! The reason is that`(?=c)` is not supported by the regex

crate, so we need to handle it with backtracking. And because

`(a|b|ab)*` is before it, we need to do it with backtracking as well.

It's still fast! The reason is that although`(?=c)` is not supported

by the regex crate, fancy-regex detects the trailing positive lookahead

and is able to essentially rewrite the pattern into

and thus delegate the whole thing to the regex crate, and fixup the

captures/match boundaries after a match is found.

If, however, the lookahead didn't come at the end of the pattern,

it would be slow! The reason is that fancy-regex would need to handle

the lookahead with backtracking. And because`(a|b|ab)*` is before it,

that also needs to be done with backtracking as well.

Oniguruma doesn't have a problem with this particular case because its

optimization saves it again: It checks if there's a`c` in the input

* If the regex doesn't use fancy features, fancy-regex should have

linear runtime compared to Oniguruma's exponential worst-case.

* If the regex doesn't use fancy features, or the features used in the

pattern can be identified as being syntactic sugar and slightly

rewritten, fancy-regex should have linear runtime compared to

Oniguruma's exponential worst-case.

* Even if the regex doesn't use any fancy features, Oniguruma can be

faster because it is a mature and highly optimized engine.

* With fancy features, Oniguruma can be faster because of optimizations.

The main author is Raph Levien, with many contributions from Robin Stocker.

The main author is Raph Levien, with many contributions from Robin Stocker

and Keith Hall.

let tree =Expr::parse_tree("(?i)(a|b|ab)*(?=c)").unwrap();

let tree =Expr::parse_tree("(?i)(a|b|ab)*(?>c)").unwrap();

let a =analyze(&tree).unwrap();

let p =compile(&a).unwrap();

let s ="abababababababababababababababababababababababababababab";

use fancy_regex::internal::{analyze, compile, run_trace,Insn,Prog};

use fancy_regex::internal::{analyze, compile,optimize,run_trace,Insn,Prog};

use fancy_regex::*;

use std::env;

use std::fmt::{Display,Formatter,Result};

let re = args.next().expect("expected regexp argument");

let e =Expr::parse_tree(&re);

println!("{:#?}", e);

}elseif cmd =="optimize"{

let re = args.next().expect("expected regexp argument");

let e =Expr::parse_tree(&re).expect("expected regexp to be parsed successfully");

println!("{:#?}", optimize(wrap_tree(e)));

}elseif cmd =="analyze"{

let re = args.next().expect("expected regexp argument");

let stdout = io::stdout();

fnshow_analysis(re:&str,writer:&mutFormatter<'_>) ->Result{

let tree =Expr::parse_tree(&re).unwrap();

let wrapped_tree =wrap_tree(tree);

let a =analyze(&wrapped_tree);

let(optimized_tree, _) =optimize(wrapped_tree).expect("Expected optimization to succeed");

let a =analyze(&optimized_tree);

write!(writer,"{:#?}\n", a)

fnprog(re:&str) ->Prog{

let tree =Expr::parse_tree(re).expect("Expected parsing regex to work");

let wrapped_tree =wrap_tree(tree);

let result =analyze(&wrapped_tree).expect("Expected analyze to succeed");

let(optimized_tree, _) =optimize(wrapped_tree).expect("Expected optimization to succeed");

let result =analyze(&optimized_tree).expect("Expected analyze to succeed");

compile(&result).expect("Expected compile to succeed")

mod tests{

usesuper::analyze;

let info =analyze(&tree).unwrap();