Working with tyre

[Drup]

I'm currently considering taking a second look at tyre, and that involves writing a ppx for it. ppx_regexp does, as far as I'm concerned, many things right and I agree with the goal to make it accessible.
So I'm considering simply extending it. That involves two things:

1. Modifying the typing rules to return _ list for groups under repetitions and `Left of _ | `Right of _ for groups under alternatives. See if the result is sufficiently usable, and maybe modify Tyre so that it is.
2. Figuring out composition.

Now, I recently got a decent idea for 2: Reuse the syntax for recursion into named groups from PCRE2. (?&potato) would simply use the (typed) regular expression named potato. This would also allow to have more primitive datatypes, for example (?&int).

What do you think? Do you want to join forces? :)

[paurkedal]

Yes, this PPX would use a revisit too. My contribution will be scattered this week, but I should have more time after that. The current library could use a full RE parser, which hopefully will be usable for both tyre and the current Re.Pcre based patterns by keeping the syntax close enough.

About composition for tyre, do you have an idea what kind of value x should capture for a match of (?<x>T(?&int){2}:(?&float))? For a classic RE, it would of course capture whole group as a string, but for tyre the question is whether it would not be more natural to ignore the literal parts and bind x to an (int * int) * float or int list * float tuple.

[Drup]

Don't worry, in the future means "in the coming weeks" ;)

As for your example: Ignoring the literal parts is easy and so it'll definitely do one of those two types. The current version doesn't have bounded repetitions, precisely because it's not clear which version you want! int list is easier to implement, but I suppose int * int is more useful. I was considering providing a tuple module for these kind of things. Unfortunately you can't really implement tuple : int -> 'a t -> _ t.

[Drup]

By the way, this is buggy in the current version of ppx_regexp

let test3 s =
  (match%pcre s with
   | {|(?<a>[0-9]*)|(?<b>[a-z]*)|} -> assert (a ^ b = s)
   | s' -> assert (s = s'))

Tyre handles that by returning something of type [> `Left of int | `Right of string]. The fact that you can give different names to the groups in the various branches is slightly bothersome.

[paurkedal]

Yep, I realized that while commenting on your earlier post. It's one reason I need a proper parser. For %pcre it should just return an option, though. This semantic is not as nice as tyre, but I think it's a fairly faithful view of the built-in capabilities of re.

On a minor note, I think it would be good with a real either (or sum) type if we could guess what the stdlib might include in a future version.

Another trick question about the tyre variant: How should x be bound in a nested aggregation like (((?<x>[^;\n]+);)*\n)*? Should this be allowed at all? I think a sound interpretation is that x represents a suitable projection operator mapped though the surrounding aggregations. On the other hand, this is already accessible be explicit mapping if the capture is done at the topmost level.

[Drup]

Another trick question about the tyre variant: How should x be bound in a nested aggregation like (((?<x>[^;\n]+);)*\n)*?

# Tyre.(rep (rep (posix "[^;\n]+") <* str";") <* str "\n") ;;
- : string Tyre.gen Tyre.gen Tyre.t

a <*b matches a, then b, returns the result of the left and drops the result from the right.
This is barely tricky, it's what I build Tyre for :D

[paurkedal]

Yes, but the trick part was about how to intepret the variable binding under the two star operators. Note also that there could have been a second variable binding parallel to (?<x>...) or at a different level. If we only allow capturing the full result into a single variable, then the correspondence with tyre route is straight forward, but I can see tree levels of support for binding variables:

• Only the top-level tyre result can be captured.
• Any number of top-level groups can be bound to different variables.
• Any group can be bound to a variable, with the suggested semantics.

In the first case, the variable name [corr.: does not] need to be inside the regexp source.

[Drup]

Initially, I would suggest the following restriction: There can not be nested groups. That should solve these kind of issues, since it means Regexs inside groups are regular PCREs that can be given to Re. Constructs that are not inside a group are re-interpreted as Tyre operators.

Later, we could consider relaxing this restriction with a rather easy-to-add Tyre function with_str : 'a t -> ('a * string) t.

[paurkedal]

I added you as a collaborator, so that we can commit directly. Let's work on a separate branch tyre, as I link to keep master in good shape. I'll commit the non-tyre parts to the same branch, as they will likely be needed. Esp. I think we can share the same parse tree and parser, though I'll have some redundancy to support both the current and new flavours, maybe including positions to allow fine-grained error reporting.

I'm not quite sure what you had in mind yet for the tyre syntax, including the use of with_str. My though after your last comment would be to allow nested groups, which would produce tuples, lists, and options for tyre, but with only top-level named capture. E.g. (?<x>a*(b(c+)d+(?&int)?)*))f would bind x to (string * int option) list because:

• a*, b, and f are not directly grouped, so they will not be captured, even though the first is variable.
• c+ is captured and will produce the string part of the tuple.
• (?&int) is captured as the second part of the tuple, the ? makes it optional.
• and * turns the tuples into a list.

There will be some details to resolve if we go with this plan.

In addition to function%tyre and match%tyre, we might want to support constructing new converting regular expressions with something like

let%tyre qname = fun {|(?<x0>\w+)(?<xs>(\.(\w+))+)|} -> x0 :: xs

Notes on this:

• I placed %tyre on the let to indicate that it is meant to be referred to as (?&qname) in another regular expression, reserving function%tyre and match%tyre for ready-to-call functions and expressions.
• The (\.(w+))-group could have used non-capturing syntax, since the capture is implied by the inner group. We could enforce either-or here.
• Of course it would be nice to support routes here, using function, but that will require some elaborate route composition and matching up groups, so we can check later if it's feasible.

Are we on the same page? Or what are your thoughts?

[Drup]

hmmm, your semantics for capturing might work. I'm always highly annoyed by the fact that parens-for-priority and parens-for-groups are overloaded. I was going to take the opposite stance, which is that only named groups are captured, including when nested. Other parens are only used for priority, not capturing.

More concretely, your example would be written a*(b(?<foo>c+)d+(?<bar>(?&int)?))*f and would return an element of type < foo : string ; bar : int option> list. Either that, or some form of hmap. This allows to nest things easily. We could consider having toplevel names bound directly to variables instead of using something structural. I'm not completely sure yet.

As for defining new regular expressions. Just [%tyre {|....|}] will do. With let%tyre foo = {|...|} as a shortcut. foo will be a real identifier of type Tyre.t anyway.

[paurkedal]

I agree! It's better if the short-syntax grouping is non-capturing. I was going to suggest (?<>...) or even (+...) for positional capture, but I like the idea of using objects for naming, as well. I can see at least Tyre.conv should allow support both for objects and tuples by conversion from pairs, so we can support both (eventually).

[paurkedal]

Another thing which bothered me after my suggestion was the fact that capturing grouping behaves different whether it contains nested captures. My suggestion was that, if not, then the whole content extracts the matched string as usual, otherwise it extract the properly typed tuple of subgroups. That was the point of the second last bullet, if not expressed clearly. I think this will be resolved by using the now non-capturing default groups for aggregation.

I think this will be fairly tidy when we impose a few sensible constraints. In particular a group used for aggregation should contain either named-only or unnamed-only immediate subgroups. There are thus a few uses of such groups:

• (re1(?<v1>...)...reN(?<vN>)reNp1) creates an object.
• (re1(+...)...reN(+...)re) creates an N-tuple.
• When (re1(+...)re2) is just a special case of the above since the 1-tuple in ocaml is the value itself. This allows delimiting the operand of ?, +, *, and {...} where needed.
• (?&...) and is allowed in the same contexts as (+...) above, and the latter is just a (?&string) from the type point of view.

The (+...) syntax is still tentative. I am not aware of any conflicts, but we could use (?X...) for some X to spend less of the available operator namespace.

About [%tyre {|...|}]: Yes, this would suffice for what can be expressed by predefined conversions. I tried to also support Tyre.conv but realise that it would require two callbacks, and thus a different and non-obvious syntax.

[paurkedal]

I think the parse tree might look something like

type t =
  | Re of Re.t
  | Seq of t list
  | Alt of t list
  | Repeat of int * int option * t
  | Capture of t
  | Capture_as of string * t
  | Case_sense of t
  | Case_blind of t

In case we want to distinguish ? from {0,1}, we'll also add an Opt constructor. I started writing a parser; it should be easy to adjust the details later.

[Drup]

I would remove the Re case (we will detect when it's appropriate to lower to Re) and you need Call of string loc

[Drup]

Also, you definitely need an Opt constructor, the semantics of Opt and repetition is slightly different regarding lazyness.

[paurkedal]

The Re case is only used to avoid representing and parsing various non-recursive constructs including character sets including character classes, assertions including a list of escape sequences, and also for string literals. I think it's a convenient simplification to start with at least, we can expand the parse tree if we need to.

I'll add Call and Opt.