Surprising precedence when stringifying concatenations of alternations

[exists-forall]

In the hir module of the regex-syntax crate, concatenating onto an alternation and calling to_string on the resulting concatenation currently produces a pattern string where the concatenation binds more tightly than the alternation. This is most easily understood with an example: https://play.rust-lang.org/?gist=36767c381c97f169e219c8c707c001ad&version=stable&mode=debug&edition=2015

I don't know if this current behavior is intended or not, but I originally expected that the pattern string printed in the example above would look something like A(?:B|C), not AB|C, as the concatenation is logically the root of the HIR tree. Would it be possible to at least document this behavior?

[BurntSushi]

Hmm, yeah, I agree, that does not look right to me. Looking at the HIR, this looks like it might be a bug in the printer because the HIR looks right to me: https://play.rust-lang.org/?gist=cea5cb88a7985fc36a94e73bcc221c7a&version=stable&mode=debug&edition=2015

It seems plausible that the printer is probably resisting putting a non-capturing group into the concrete syntax that does not itself exist in the HIR. So the question here is whether the HIR construction should be updated to insert a group itself or if the printer should recognize that Hir::Something followed by a Hir::Alternation requires a non-capturing group.

When faced with these decisions, I think I've generally leaned towards fixing this at construction time, such that certain combinations of HIR are never possible. For example, it should be impossible to get a Concat(Expr) since it is always equivalent to just Expr.

[ethanpailes]

For what it's worth I've encountered this when playing around with regex syntax and found the behavior surprising. My assumption was that the printer would take care of extra noncaptapturing groups. When that didn't happen I just injected a bunch of extra noncapturing groups at construction time. For my use case (dynamically assembling arbitrarily user supplied regex) I don't think those groups were always required. If consideration of groups gets pushed to construction time, it would be nice to help the caller avoid these extra groups by handling them automatically or something. On Sep 18, 2018 6:50 AM, "Andrew Gallant" <notifications@github.com> wrote: Hmm, yeah, I agree, that does not look right to me. Looking at the HIR, this looks like it might be a bug in the printer because the HIR looks right to me: https://play.rust-lang.org/?gist=cea5cb88a7985fc36a94e73bcc221c7a&version=stable&mode=debug&edition=2015 It seems plausible that the printer is probably resisting putting a non-capturing group into the concrete syntax that does not itself exist in the HIR. So the question here is whether the HIR construction should be updated to insert a group itself or if the printer should recognize that Hir::Something followed by a Hir::Alternation requires a non-capturing group. When faced with these decisions, I think I've generally leaned towards fixing this at construction time, such that certain combinations of HIR are never possible. For example, it should be impossible to get a Concat(Expr) since it is always equivalent to just Expr. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#516 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AEGx5f5jPennIQD5gllnvJxw5W7uEIm1ks5ucNAIgaJpZM4WtSxN> .

[BurntSushi]

I have a fix incoming that will land as part of the #656 work. Here's the commit message that explains everything and my fix. TL;DR - I tweaked the printer.

syntax: fix HIR printer

This fixes some corner cases in the HIR printer where it would print the
concrete syntax of a regex that does not match the natural
interpretation of the HIR. One such example of this is:

    concat(a, alt(b, c))

This would get printed as

    ab|c

But clearly, it should be printed as:

    a(?:b|c)

The issue here is that the printer only considers the current HirKind
when determining how to print it. Sometimes a group is needed to print
an alt (and even a concat, in the case of 'rep(+, concat(a, b))'), but
sometimes it isn't.

We could address this in a few different ways:

1) Always print concats and alts inside a non-capturing group.
2) Make the printer detect precisely the cases where a non-capturing
   group is needed.
3) Make the HIR smart constructors insert non-capturing groups when
   needed.
4) Do some other thing to change the HIR to prevent these sorts of
   things by construction.

This patch goes with (1). The reason in favor of it is that HIR printer
was always about printing an equivalent regex and never about trying to
print a "nice" regex. Indeed, the HIR printer can't print a nice regex,
because the HIR represents a rigorously simplifed view of a regex to
make analysis easier. (The most obvious such example are Unicode
character classes. For example, the HIR printer never prints '\w'.) So
inserting some extra groups (which it already does) even when they
aren't strictly needed is perfectly okay.

But still, it's useful to say why we didn't do the other choices:

2) Modifying the printer to only print groups when they're actually
   needed is pretty difficult. I tried this briefly, and handling this
   case requires some notion of what the parent expression is. This
   winds up being a possible but hairy change.
3) Making the HIR more complicated to make the printer correct seems
   like it's optimizing for the wrong thing. Inserting extra groups in
   places just obfuscates HIR values that already have clear semantics.
   That is, use concat(a, alt(b, c)) over concat(a, group(alt(b, c))).
4) It's not clear how we would change the HIR to guarantee this sort of
   thing wouldn't happen. At the very least, it seems likely it would
   require a more complex data type.

At first, I had thought (1) seemed inelegant. But the more I thought
about it, the more it seemed quite consistent with how the HIR printer
already worked. So that's the path I took here.

Closes #516, Closes #731