Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Position information for parsed regular expressions #174

Closed
nikomatsakis opened this issue Feb 22, 2016 · 4 comments · Fixed by #452
Closed

Position information for parsed regular expressions #174

nikomatsakis opened this issue Feb 22, 2016 · 4 comments · Fixed by #452

Comments

@nikomatsakis
Copy link

It's unfortunate that a parsed regular expression Expr contains no offset information from the original string. It just means that if you have to later give an error message about some particular part you can't pinpoint with a lot of precision. (In my case, I want to report that certain features -- such as word boundaries -- are not supported.)

@BurntSushi
Copy link
Member

That would definitely be very useful. I'd be fine adding this.

It would change the Expr type significantly, I think (which is fine). I don't have any experience building (or using) an AST with offset information inside of it. Do you have any advice on that front? What's convenient to use?

One approach I can think of is:

pub struct Spanned {
    expr: Expr,
    start: usize,
    end: usize,
}

And all of the recursive variants of Expr would then change to using Spanned instead.

Another approach would be to inline the offset information into every variant of Expr, but that seems more yucky.

@nikomatsakis
Copy link
Author

The Spanned variant is what we do in the compiler. It's not great, but it's the usual thing. I usually use names like this:

pub struct Expr {
    start: usize,
    end: usize,
    kind: Box<ExprKind>
}

pub enum ExprKind {
    ...
}

but this has the disadvantage that matching becomes a bit more verbose (ExprKind::Foo instead of Expr::Foo).

@nikomatsakis
Copy link
Author

This is one of those cases where having the ability to express common fields on enums would be really nice. But that'll be a while. :)

@BurntSushi
Copy link
Member

Hah, right, your blog post is ringing a bell!

Your Expr/ExprKind variant seems nice. Usually I have a use regex_syntax::Expr::* in the function scope when matching anyway.

BurntSushi added a commit to BurntSushi/regex that referenced this issue Mar 5, 2018
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, Fixes rust-lang#435
BurntSushi added a commit to BurntSushi/regex that referenced this issue Mar 5, 2018
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 added a commit to BurntSushi/regex that referenced this issue Mar 6, 2018
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 added a commit to BurntSushi/regex that referenced this issue Mar 7, 2018
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.
* Empty sub-expressions are now properly supported. Expressions like
  `()`, `|`, `a|` and `b|()+` are now valid syntax.

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 added a commit to BurntSushi/regex that referenced this issue Mar 7, 2018
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.
* Empty sub-expressions are now properly supported. Expressions like
  `()`, `|`, `a|` and `b|()+` are now valid syntax.

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 added a commit that referenced this issue Mar 8, 2018
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.
* Empty sub-expressions are now properly supported. Expressions like
  `()`, `|`, `a|` and `b|()+` are now valid syntax.

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 #174, Fixes #424
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants