Question: Does the regex-syntax crate optimize its HIR?

[ckaran]

Background

I'm working on writing yet another fuzzing framework (YAFF for short), but I'm doing it via an interesting twist. I'm using regular expressions (specifically, what regex-syntax supports) to describe the space of byte strings that a type suggests a fuzzer should explore. Roughly speaking, the idea is the following:

1. A type implements both Arbitrary and my own trait Semiarbitrary.
2. Semiarbitrary has an associated function defined that returns a &str, which is a regular expression that obeys the syntax of the regex crate.
3. I parse this expression using the regex-syntax crate, and I create strings that would match the regular expression given in step 2 (this is the fuzzing part).
4. These strings are used to create new instances of the type being tested via the type's implementation of Arbitrary.
   1. If Arbitrary returns an error of type IncorrectFormat, then I know that the original regex matched more strings than can be accepted. I start exploring the space around the rejected string to see if can improve the regular expression by subtracting out chunks of space that the type's implementation of Arbitrary will reject with an IncorrectFormat error.
   2. If I get a valid value, but the test fails I log the string in my fuzzing database and explore/reduce it to find the minimal regex that produces test failures.
   3. If the test passes, I try to find a point in byte-string space that is 'half-way' to another point, and if it can be matched by the type's original regex I run it through the tests. Otherwise I look for another point in space.
5. Repeat the above steps until I'm stopped, or I've found lots of bugs.

The Issue

Fuzzing rarely produces truly optimal output, and part of that problem is that it can generate regular expressions that are horribly inefficient. E.g., alternations that repeatedly sample the same region of byte string space, or have partitioned space into a billion small points which could all be joined into a much larger combined space. I want to know the following:

1. Does the regex-syntax crate optimize its Hir?
2. Is there a way of re-optimizing the Hir after mutating it?

Ideally for me, the answer to both questions would be 'yes.' That way I can mutate to my heart's content, but still have a way of reducing the regular expression down to the smallest subspace that a) contains valid instances only, and b) still causes a test failure.

I hope all of this makes sense.

[BurntSushi]

Does the regex-syntax crate optimize its Hir?

It does a little bit of optimization today. But very little. Here's one example:

regex/regex-syntax/src/hir/mod.rs

Lines 398 to 402 in 4075d39

	pub fn concat(mut exprs: Vec<Hir>) -> Hir {
	match exprs.len() {
	0 => Hir::empty(),
	1 => exprs.pop().unwrap(),
	_ => {

I do have a rather large WIP patchset (that will become regex-syntax 0.8 at some point) that beefs up the optimizations. Example 1:

regex/regex-syntax/src/hir/mod.rs

Lines 342 to 405 in 7ecd9ff

	pub fn concat(hirs: Vec<Hir>) -> Hir {
	// We rebuild the concatenation by simplifying it. Would be nice to do
	// it in place, but that seems a little tricky?
	let mut new = vec![];
	// This gobbles up any adjacent literals in a concatenation and smushes
	// them together. Basically, when we see a literal, we add its bytes
	// to 'prior_lit', and whenever we see anything else, we first take
	// any bytes in 'prior_lit' and add it to the 'new' concatenation.
	let mut prior_lit: Option<Vec<u8>> = None;
	for hir in hirs {
	let (kind, props) = hir.into_parts();
	match kind {
	HirKind::Literal(Literal(bytes)) => {
	if let Some(ref mut prior_bytes) = prior_lit {
	prior_bytes.extend_from_slice(&bytes);
	} else {
	prior_lit = Some(bytes.to_vec());
	}
	}
	// We also flatten concats that are direct children of another
	// concat. We only need to do this one level deep since
	// Hir::concat is the only way to build concatenations, and so
	// flattening happens inductively.
	HirKind::Concat(hirs2) => {
	for hir2 in hirs2 {
	let (kind2, props2) = hir2.into_parts();
	match kind2 {
	HirKind::Literal(Literal(bytes)) => {
	if let Some(ref mut prior_bytes) = prior_lit {
	prior_bytes.extend_from_slice(&bytes);
	} else {
	prior_lit = Some(bytes.to_vec());
	}
	}
	kind2 => {
	if let Some(prior_bytes) = prior_lit.take() {
	new.push(Hir::literal(prior_bytes));
	}
	new.push(Hir { kind: kind2, props: props2 });
	}
	}
	}
	}
	// We can just skip empty HIRs.
	HirKind::Empty => {}
	kind => {
	if let Some(prior_bytes) = prior_lit.take() {
	new.push(Hir::literal(prior_bytes));
	}
	new.push(Hir { kind, props });
	}
	}
	}
	if let Some(prior_bytes) = prior_lit.take() {
	new.push(Hir::literal(prior_bytes));
	}
	if new.is_empty() {
	return Hir::empty();
	} else if new.len() == 1 {
	return new.pop().unwrap();
	}
	let props = Properties::concat(&new);
	Hir { kind: HirKind::Concat(new), props }
	}

Example 2:

regex/regex-syntax/src/hir/mod.rs

Lines 410 to 460 in 7ecd9ff

	pub fn alternation(hirs: Vec<Hir>) -> Hir {
	// We rebuild the alternation by simplifying it. We proceed similarly
	// as the concatenation case. But in this case, there's no literal
	// simplification happening. We're just flattening alternations.
	let mut new = vec![];
	for hir in hirs {
	let (kind, props) = hir.into_parts();
	match kind {
	HirKind::Alternation(hirs2) => {
	new.extend(hirs2);
	}
	kind => {
	new.push(Hir { kind, props });
	}
	}
	}
	if new.is_empty() {
	return Hir::fail();
	} else if new.len() == 1 {
	return new.pop().unwrap();
	}
	// Now that it's completely flattened, look for the special case of
	// 'char1|char2|...|charN' and collapse that into a class. Note that we
	// look for 'char' first and then bytes. The issue here is that if we
	// find both non-ASCII codepoints and non-ASCII singleton bytes, then
	// it isn't actually possible to smush them into a single class. So we
	// look for all chars and then all bytes, and don't handle anything
	// else.
	if let Some(singletons) = singleton_chars(&new) {
	let it = singletons
	.into_iter()
	.map(|ch| ClassUnicodeRange { start: ch, end: ch });
	return Hir::class(Class::Unicode(ClassUnicode::new(it)));
	}
	if let Some(singletons) = singleton_bytes(&new) {
	let it = singletons
	.into_iter()
	.map(|b| ClassBytesRange { start: b, end: b });
	return Hir::class(Class::Bytes(ClassBytes::new(it)));
	}
	// Similar to singleton chars, we can also look for alternations of
	// classes. Those can be smushed into a single class.
	if let Some(cls) = class_chars(&new) {
	return Hir::class(cls);
	}
	if let Some(cls) = class_bytes(&new) {
	return Hir::class(cls);
	}
	let props = Properties::alternation(&new);
	Hir { kind: HirKind::Alternation(new), props }
	}

But... It looks like you're asking about particular optimizations. For example:

alternations that repeatedly sample the same region of byte string space, or have partitioned space into a billion small points which could all be joined into a much larger combined space

I actually need to see examples of this to be honest. I bet I could make a good guess at what you're saying. I would say that regex-syntax does not do this kind of optimization today. I suspect it might not ever. I have some optimizations like this in another WIP branch for regex-automata, but those are being applied while compiling an NFA. I don't have any plans to port those to the HIR. The principle reason is that once you get into things like "reducing the size of alternations based on literals," things get quite complex and there has to be a balance between "produce the simplest possible HIR" and "don't take too much time building an HIR."

There are other complexities. For example, regex-syntax doesn't know anything about match semantics. In some regex engines, sam|samwise will match sam in samwise, and in other regex engines, it will match samwise. The match semantics of the former are what the regex crate implements, and they directly imply that the order of literals in an alternation matters. So for example, if you have zap|z|zapper, you might think an equivalent regex is z(ap(per)?)?, but it actually isn't, because that regex will match zapper in zapper when it should have matched zap when using the regex crate. So the simplified regex in that case would be z(ap||apper).

So I think in order to really consider your question, it would be best to provide specifics. :-)

Is there a way of re-optimizing the Hir after mutating it?

Can you show me your code that mutates an Hir? :-) I contend that such things are impossible, and that is by design. The only thing you can do is structural induction over the Hir and produce a new Hir. And the only way to produce an Hir is through its "smart" constructors. And those "smart" constructors are what is responsible for doing the optimizations. This makes it, for example, impossible to build an Hir with an alternation containing fewer than 2 sub-expressions. You can't even remove those sub-expressions after the Hir is built because there are no mutating APIs.

[ckaran]

I actually need to see examples of this to be honest. I bet I could make a good guess at what you're saying.

(a|b|c|d|e) could be simplified to [a-e]. ([a-y]|[b-z]) could be simplified to [a-z]. I'm not after full, perfect optimizations, more like anything that helps reduce stuff

Can you show me your code that mutates an Hir?

Sorry, you're right, you cannot mutate it in-place, so my 'mutations' are always new Hir that are 'mutations' of the original. I got sloppy with my language, which is a bad thing to do when dealing with the author of a regex crate! 😅

[BurntSushi]

(a|b|c|d|e) could be simplified to [a-e]. ([a-y]|[b-z]) could be simplified to [a-z]. I'm not after full, perfect optimizations, more like anything that helps reduce stuff

Both of those will be in regex-syntax 0.8. Actually, those are exactly the two optimizations present in my "Example 2" above. :-)

Sorry, you're right, you cannot mutate it in-place, so my 'mutations' are always new Hir that are 'mutations' of the original. I got sloppy with my language, which is a bad thing to do when dealing with the author of a regex crate! sweat_smile

Ah I see yes. In that case, the answer is yes, the optimizations will be applied automatically. I specifically made the optimizations part of the construction of Hir itself, so that anyone using it, no matter how they build it, benefits from them. There isn't a separate "optimization pass" on HIR.

[ckaran]

Thank you for answering my questions, and thank you for making this crate! I'm still hacking around on my own crate, but regex-syntax has already made my life much easier!