syntax: rewrite the regex-syntax crate

This commit represents a ground up rewrite of the regex-syntax crate. This commit is also an intermediate state. That is, it adds a new regex-syntax-2 crate without making any serious changes to any other code. Subsequent commits will cover the integration of the rewrite and the removal of the old crate. The rewrite is intended to be the first phase in an effort to overhaul the entire regex crate. To that end, this rewrite takes steps in that direction: * The principle change in the public API is an explicit split between a regular expression's abstract syntax (AST) and a high-level intermediate representation (HIR) that is easier to analyze. The old version of this crate mixes these two concepts, but leaned heavily towards an HIR. The AST in the rewrite has a much closer correspondence with the concrete syntax than the old `Expr` type does. The new HIR embraces its role; all flags are now compiled away (including the `i` flag), which will simplify subsequent passes, including literal detection and the compiler. ASTs are produced by ast::parse and HIR is produced by hir::translate. A top-level parser is provided that combines these so that callers can skip straight from concrete syntax to HIR. * Error messages are vastly improved thanks to the span information that is now embedded in the AST. In addition to better formatting, error messages now also include helpful hints when trying to use features that aren't supported (like backreferences and look-around). In particular, octal support is now an opt-in option. (Octal support will continue to be enabled in regex proper to support backwards compatibility, but will be disabled in 1.0.) * More robust support for Unicode Level 1 as described in UTS#18. In particular, we now fully support Unicode character classes including set notation (difference, intersection, symmetric difference) and correct support for named general categories, scripts, script extensions and age. That is, `\p{scx:Hira}` and `p{age:3.0}` now work. To make this work, we introduce an internal interval set data structure. * With the exception of literal extraction (which will be overhauled in a later phase), all code in the rewrite uses constant stack space, even while performing analysis that requires structural induction over the AST or HIR. This is done by pushing the call stack onto the heap, and is abstracted by the `ast::Visitor` and `hir::Visitor` traits. The point of this method is to eliminate stack overflows in the general case. The principle downsides of these changes are parse time and binary size. Both seemed to have increased (slower and bigger) by about 1.5x. Parse time is generally peanuts compared to the compiler, so we mostly don't care about that. Binary size is mildly unfortunate, and if it becomes a serious issue, it should be possible to introduce a feature that disables some level of Unicode support and/or work on compressing the Unicode tables. Compile times have increased slightly, but are still a very small fraction of the overall time it takes to compile `regex`. Fixes rust-lang#174, Fixes rust-lang#424
BurntSushi · Mar 5, 2018 · 974e667 · 974e667
1 parent 43bb64b
commit 974e667
Show file tree

Hide file tree

Showing 29 changed files with 23,660 additions and 1 deletion.
diff --git a/regex-debug/Cargo.toml b/regex-debug/Cargo.toml
@@ -14,5  14,6 @@ workspace = ".."
 docopt = "0.8"
 regex = { version = "0.2", path = ".." }
 regex-syntax = { version = "0.4.0", path = "../regex-syntax" }
 regex-syntax2 = { version = "0.5.0", path = "../regex-syntax-2" }
 serde = "1"
 serde_derive = "1"
diff --git a/regex-debug/src/main.rs b/regex-debug/src/main.rs
@@ -1,6  1,7 @@
 extern crate docopt;
 extern crate regex;
 extern crate regex_syntax as syntax;
 extern crate regex_syntax2;
 extern crate serde;
 #[macro_use]
 extern crate serde_derive;
@@ -17,6  18,8 @@ use syntax::{ExprBuilder, Expr, Literals};
 const USAGE: &'static str = "
 Usage:
     regex-debug [options] ast <pattern>
     regex-debug [options] ast2 <pattern>
     regex-debug [options] hir2 <pattern>
     regex-debug [options] prefixes <patterns> ...
     regex-debug [options] suffixes <patterns> ...
     regex-debug [options] anchors <pattern>
@@ -51,6  54,8 @@ Options:
 #[derive(Deserialize)]
 struct Args {
     cmd_ast: bool,
     cmd_ast2: bool,
     cmd_hir2: bool,
     cmd_prefixes: bool,
     cmd_suffixes: bool,
     cmd_anchors: bool,
@@ -93,6  98,10 @@ fn main() {
 fn run(args: &Args) -> Result<()> {
     if args.cmd_ast {
         cmd_ast(args)
     } else if args.cmd_ast2 {
         cmd_ast2(args)
     } else if args.cmd_hir2 {
         cmd_hir2(args)
     } else if args.cmd_prefixes {
         cmd_literals(args)
     } else if args.cmd_suffixes {
@@ -109,7  118,28 @@ fn run(args: &Args) -> Result<()> {
 }
 
 fn cmd_ast(args: &Args) -> Result<()> {
-    println!("{:#?}", try!(args.parse_one()));
     let ast = try!(args.parse_one());
     println!("{:#?}", ast);
     Ok(())
 }
 
 fn cmd_ast2(args: &Args) -> Result<()> {
     use regex_syntax2::ast::parse::Parser;
 
     let mut parser = Parser::new();
     let ast = try!(parser.parse(&args.arg_pattern));
     println!("{:#?}", ast);
     Ok(())
 }
 
 fn cmd_hir2(args: &Args) -> Result<()> {
     use regex_syntax2::ParserBuilder;
 
     let mut parser = ParserBuilder::new()
         .allow_invalid_utf8(false)
         .build();
     let hir = try!(parser.parse(&args.arg_pattern));
     println!("{:#?}", hir);
     Ok(())
 }
 

diff --git a/regex-syntax-2/Cargo.toml b/regex-syntax-2/Cargo.toml
@@ -0,0  1,13 @@
 [package]
 name = "regex-syntax2"
 version = "0.5.0"  #:version
 authors = ["The Rust Project Developers"]
 license = "MIT/Apache-2.0"
 repository = "https://github.com/rust-lang/regex"
 documentation = "https://docs.rs/regex-syntax"
 homepage = "https://github.com/rust-lang/regex"
 description = "A regular expression parser."
 workspace = ".."
 
 [dependencies]
 ucd-util = { version = "*", path = "/home/andrew/rust/rucd/ucd-util" }
diff --git a/regex-syntax-2/benches/bench.rs b/regex-syntax-2/benches/bench.rs
@@ -0,0  1,73 @@
 // Copyright 2018 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
 #![feature(test)]
 
 extern crate regex_syntax2;
 extern crate test;
 
 use regex_syntax2::Parser;
 use test::Bencher;
 
 #[bench]
 fn parse_simple1(b: &mut Bencher) {
     b.iter(|| {
         let re = r"^bc(d|e)*$";
         Parser::new().parse(re).unwrap()
     });
 }
 
 #[bench]
 fn parse_simple2(b: &mut Bencher) {
     b.iter(|| {
         let re = r"'[a-zA-Z_][a-zA-Z0-9_]*(')\b";
         Parser::new().parse(re).unwrap()
     });
 }
 
 #[bench]
 fn parse_small1(b: &mut Bencher) {
     b.iter(|| {
         let re = r"\p{L}|\p{N}|\s|.|\d";
         Parser::new().parse(re).unwrap()
     });
 }
 
 #[bench]
 fn parse_medium1(b: &mut Bencher) {
     b.iter(|| {
         let re = r"\pL\p{Greek}\p{Hiragana}\p{Alphabetic}\p{Hebrew}\p{Arabic}";
         Parser::new().parse(re).unwrap()
     });
 }
 
 #[bench]
 fn parse_medium2(b: &mut Bencher) {
     b.iter(|| {
         let re = r"\s\S\w\W\d\D";
         Parser::new().parse(re).unwrap()
     });
 }
 
 #[bench]
 fn parse_medium3(b: &mut Bencher) {
     b.iter(|| {
         let re = r"\p{age:3.2}\p{hira}\p{scx:hira}\p{alphabetic}\p{sc:Greek}\pL";
         Parser::new().parse(re).unwrap()
     });
 }
 
 #[bench]
 fn parse_huge(b: &mut Bencher) {
     b.iter(|| {
         let re = r"\p{L}{100}";
         Parser::new().parse(re).unwrap()
     });
 }