Support named capture groups #112

dyzsr · 2022-09-19T12:55:52Z

This PR tries to support named capture groups. Closes #5, closes #102.

Usages

In the example

(Plus '0'..'9') as digits

Variable digits is defined as a (pos, len) pair, which can be passed as arguments to Sedlexing.sub_lexeme to retrieve the group captured by digits.

The as syntax is only allowed in match%sedlex ... with ... constructs. You cannot provide an alias in let ... = [%sedlex.regexp? ...]. And it is not allowed inside constructors (i.e. Star, Plus, Rep, Opt, Compl, Sub, Intersect, Chars).

Plus ("ab" as a)  (* this is invalid *)

Implementation

We are trying to restore the NFA node transitions path with the information of the DFA state transitions path.

Explanation

And finally,

let sub (a, b) = Sedlexing.Latin1.sub_lexeme buf a b in
match%sedlex buf with
  | (sign as s), prefix_2, (num_2 as n) ->
      Printf.printf "Bin %s%s\n" (sub s) (sub n);
      token buf
  ...

is translated to

let sub (a, b) = Sedlexing.Latin1.sub_lexeme buf a b in
match __sedlex_result with
  | 0 ->
      let __sedlex_aliases_starts, __sedlex_aliases_stops =
        __sedlex_trace_0 buf __sedlex_path
      in
      let n = (__sedlex_aliases_starts.(0), __sedlex_aliases_stops.(0) - __sedlex_aliases_starts.(0))
      and s = (__sedlex_aliases_starts.(1), __sedlex_aliases_stops.(1) - __sedlex_aliases_starts.(1)) in
      Printf.printf "Bin %s%s\n" (sub s) (sub n);
      token buf
  ...

Note

When there are multiple available paths, any of them might be chosen. As in

(Plus "ab" as a), (Plus "ab" as b)

"abababab" => a:"ababab", b:"ab"

One of the possible combinations of a and b will be returned.

Others

There are some tests (test/number_lexer.ml, test/misc.ml) currently. More to be added.

src/syntax/ppx_sedlex.ml

dyzsr · 2022-09-20T15:43:32Z

Can anybody help add reviewers? (Also approve running workflows)

src/syntax/ppx_sedlex.ml

dyzsr · 2022-09-21T13:27:58Z

PTAL @alainfrisch @Drup @pmetzger

hhugo · 2022-09-21T15:37:49Z

src/syntax/ppx_sedlex.ml

          with Not_found ->
            err p.ppat_loc (Printf.sprintf "unbound regexp %s" x)
        end
+      | Ppat_alias (p, ({ txt = x } as x_loc)) when allow_alias ->


Can we give a better error for Ppat_alias _ when not allow_alias ?

This comment still stand

This has now been addressed.

hhugo · 2022-09-21T15:40:43Z

src/syntax/ppx_sedlex.ml

@@ -489,9 +667,13 @@ let mapper =
        let l, regexps' = sub#structure_with_regexps (!previous @ l) in
        let parts = List.map partition (get_partitions ()) in
        let tables = List.map table (get_tables ()) in
+        let funcs =
+          let loc = default_loc in
+          [%str let __sedlex_tl = function _ :: tl -> tl | _ -> assert false]


Can we put this in the lib, similar to what we do for Sedlexing.__private__next_int

This comment is not relevant anymore

hhugo · 2022-09-21T15:43:18Z

src/syntax/ppx_sedlex.ml

+  let brs =
+    Array.of_list
+      (List.map
+         (fun ((r, s), e) -> ((r, List.of_seq (StrLocSet.to_seq s)), e))


StrLocSet.elements ?

This has been applied

toots

I can't really comment on the implementation but, for the API, is there a benefit in exporting offset/length vs simply binding the resulting match string?

hhugo · 2022-09-21T20:09:22Z

Could you give more details about the current implementation ? Why is it done this way ? Can't we update positions as we traverse the automation, instead of doing a second pass based on some trace ? Why is the trace processed in reverse order ?

hhugo · 2022-09-21T20:18:26Z

There is a lot of room for optimization.

Offset tracking could be shared between bindings.

For example, in(Plus 'a' as a), (Plus 'b' as b), end of binding a equals start of binding b.

Some offset can be computer statically. In the regexp above, start of a is 0, end of b is the end of the lexeme.

Have you considered such optimizations ?

hhugo · 2022-09-22T09:19:51Z

let rec token buf =
  match%sedlex buf with
    | (Plus "a" as a), (Plus "b" as b), "c" ->
        ignore a;
        ignore b;
        Printf.printf "Op %s - %s\n"
          (Sedlexing.Latin1.sub_lexeme buf (fst a) (snd a))
          (Sedlexing.Latin1.sub_lexeme buf (fst b) (snd b));
        token buf
    | eof -> print_endline "EOF"
    | _ -> failwith "Unexpected character"

let () =
  let lexbuf = Sedlexing.Latin1.from_string "aaaabbbc" in
  token lexbuf

Returns an unexpected result:

Op aaaab - bb                       
EOF

hhugo · 2022-09-22T11:20:41Z

I think I would be easier if your trace was maintaining pairs of pos, instead of pos + len.

dyzsr · 2022-09-26T14:16:57Z

@hhugo Thanks for your considerate suggestions! Let me do it one by one and start from merging the alias offsets.

ocamllex has some optimization:
rule token = parse
  | ("a"+ as a) ("b" + as b) "d" { a,b }
only stores 2 integers
rule token = parse
  | (['-' '+'] as sign) (['0'-'9']+ as a) { a,b }
Doesn't store anything.

I'm not sure if I'm able to support optimizations in such static cases. I'll think about it.

Another thing yet to do is to stop tracking the path if the matching branches have no alias at all.

hhugo · 2022-09-27T10:44:15Z

src/syntax/ppx_sedlex.ml

+        (fun action offsets ->
+          try
+            let i = Hashtbl.find cases2offset offsets in
+            Hashtbl.replace cases2offset offsets i;


This Hashtbl.replace doesn't seem to be doing anything.

hhugo · 2022-09-27T10:46:24Z

src/syntax/sedlex.mli

+  prev_state : int;
+  prev_node : int;
+  char_set : Sedlex_cset.t;
+  actions : (string * bool) list;


maybe declare a separate type for action ?
type action = Start of string | End of string ?

hhugo · 2022-09-27T10:56:52Z

src/syntax/ppx_sedlex.ml

+  | [] -> e
+  | aliases ->
+      let loc = default_loc in
+      let _, action_offsets = Option.get offsets.(i) in


instead of matching on aliases above, we could directly match on offsets.(i)

let gen_aliases lexbuf offsets i e aliases = match offsets.(i) with | None -> e | Some (_, action_offsets) -> let loc = default_loc in pexp_let ~loc Nonrecursive [ value_binding ~loc ~pat:[%pat? __sedlex_offsets] ~expr: (appfun (trace_fun i) [evar ~loc lexbuf; [%expr __sedlex_path]]); ] @@ pexp_let ~loc Nonrecursive (List.map (fun { txt = alias; loc } -> let start = Hashtbl.find action_offsets (alias, true) in let stop = Hashtbl.find action_offsets (alias, false) in value_binding ~loc ~pat:(pvar ~loc alias) ~expr: [%expr __sedlex_offsets.([%e eint ~loc start]), __sedlex_offsets.([%e eint ~loc stop]) - __sedlex_offsets.([%e eint ~loc start])]) aliases) @@ e

hhugo · 2022-09-27T11:11:09Z

src/syntax/ppx_sedlex.ml

+              with Not_found -> Hashtbl.add action2cases action [i])
+            actions)
+        cases;
+      let counter = ref 0 in


~~counter could be replace by Hastbl.length alias2offset I think~~

hhugo · 2022-09-27T11:21:12Z

src/syntax/ppx_sedlex.ml

+      let offset_array =
+        value_binding ~loc
+          ~pat:[%pat? __sedlex_offsets]
+          ~expr:(pexp_array ~loc (List.init offsets_num (fun _ -> [%expr 0])))


I would use an invalid position here (e.g. '-1`) as it would make it more obvious if we ever encounter a bug where position are not updated.

This is done

hhugo · 2022-09-27T11:24:38Z

src/syntax/sedlex.ml

+                  let node_j = Hashtbl.find nodes_idx from_node in
+                  let rec dfs cset actions to_node =
+                    let node_i = Hashtbl.find nodes_idx to_node in
+                    try ignore (Hashtbl.find cases (i, node_i, j, cset))


Hashtbl.mem

This is done

hhugo · 2022-09-27T14:08:14Z

src/syntax/sedlex.ml

+
+let compile_traces states (start, final) =
+  let counter = ref 0 in
+  let nodes_idx = Hashtbl.create 31 in


How are nodes_idx different from node.id ?

Right. I forgot there's already an id in node.

hhugo · 2022-09-27T14:12:27Z

src/syntax/sedlex.ml

+      let i = Hashtbl.find nodes_idx node in
+      let actions = append_action actions node.action in
+      let cases =
+        if node.trans <> [] || node == final then


Can you add a comment explaining these conditions ?

Will add it later.

hhugo · 2022-09-27T14:46:02Z

src/syntax/ppx_sedlex.ml

+          let r1, s1 = aux allow_alias p1 in
+          let r2, s2 = aux allow_alias p2 in
+          if not (StrLocSet.equal s1 s2) then begin
+            let x =


What about providing the full list of problematic bindings ?
(e.g StrLocSet.(diff (union s1 s2) (inter s1 s2)))

hhugo · 2022-09-27T14:47:09Z

src/syntax/ppx_sedlex.ml

+            (fun (r1, s1) p ->
+              let r2, s2 = aux allow_alias p in
+              if not (StrLocSet.disjoint s1 s2) then begin
+                let x = StrLocSet.choose (StrLocSet.inter s1 s2) in


Same here, we could return the full list of duplicated bindings

I think it's OK to report one location at a time, just like the OCaml compiler behaves. (One name corresponds to one location)

hhugo · 2022-09-27T14:48:11Z

src/syntax/sedlex.ml

+          (fun to_state i ->
+            List.iter
+              (fun from_node ->
+                try


is this try-with necessary ?

It caused some problem when I removed nodes_idx. Now it's fixed.

Can you elaborate on the issue and explain what are the irrelevant nodes ?

hhugo · 2022-09-27T15:35:59Z

src/syntax/ppx_sedlex.ml

+                  [
+                    pint ~loc curr_state;
+                    pint ~loc curr_node;
+                    pint ~loc prev_state;


is prev_state ever needed to choose the action ?
On a trivial example

let rec token buf = match%sedlex buf with | (Star "a" as a), (Plus "b" as b), "c" -> print_alias buf "a" a; print_alias buf "b" b; token buf | eof -> print_endline "EOF" | _ -> failwith "Unexpected character"

curr_state and curr_node are enough for choosing the action.
The following

let __sedlex_code = Sedlexing.lexeme_code buf (__sedlex_pos - 1) in (match (__sedlex_curr_state, __sedlex_curr_node, __sedlex_prev_state) with | (2, 6, 0) -> (__sedlex_offsets.(2) <- __sedlex_pos; __sedlex_aux (__sedlex_pos - 1) 0 10 __sedlex_rest) | (0, 6, 2) -> (__sedlex_offsets.(2) <- __sedlex_pos; __sedlex_aux (__sedlex_pos - 1) 2 10 __sedlex_rest) | (3, 6, 2) -> __sedlex_aux (__sedlex_pos - 1) 2 6 __sedlex_rest | (4, 1, 3) -> __sedlex_aux (__sedlex_pos - 1) 3 2 __sedlex_rest | (3, 2, 0) -> (__sedlex_offsets.(1) <- __sedlex_pos; __sedlex_aux (__sedlex_pos - 1) 0 6 __sedlex_rest) | (3, 6, 0) -> __sedlex_aux (__sedlex_pos - 1) 0 6 __sedlex_rest | (2, 6, 2) -> (__sedlex_offsets.(2) <- __sedlex_pos; __sedlex_aux (__sedlex_pos - 1) 2 10 __sedlex_rest) | (3, 2, 2) -> (__sedlex_offsets.(1) <- __sedlex_pos; __sedlex_aux (__sedlex_pos - 1) 2 6 __sedlex_rest) | (3, 2, 3) -> (__sedlex_offsets.(1) <- __sedlex_pos; __sedlex_aux (__sedlex_pos - 1) 3 6 __sedlex_rest) | (3, 6, 3) -> __sedlex_aux (__sedlex_pos - 1) 3 6 __sedlex_rest | (0, 10, 2) -> __sedlex_aux (__sedlex_pos - 1) 2 10 __sedlex_rest | (0, 6, 0) -> (__sedlex_offsets.(2) <- __sedlex_pos; __sedlex_aux (__sedlex_pos - 1) 0 10 __sedlex_rest) | (2, 10, 2) -> __sedlex_aux (__sedlex_pos - 1) 2 10 __sedlex_rest | (0, 10, 0) -> __sedlex_aux (__sedlex_pos - 1) 0 10 __sedlex_rest | (2, 10, 0) -> __sedlex_aux (__sedlex_pos - 1) 0 10 __sedlex_rest | _ -> assert false) in

can be rewritten into

let __sedlex_code = Sedlexing.lexeme_code buf (__sedlex_pos - 1) in (match (__sedlex_curr_state, __sedlex_curr_node) with | (2, 6) -> (__sedlex_offsets.(2) <- __sedlex_pos; __sedlex_aux (__sedlex_pos - 1) __sedlex_prev_state 10 __sedlex_rest) | (0, 6) -> (__sedlex_offsets.(2) <- __sedlex_pos; __sedlex_aux (__sedlex_pos - 1) __sedlex_prev_state 10 __sedlex_rest) | (3, 6) -> __sedlex_aux (__sedlex_pos - 1) __sedlex_prev_state 6 __sedlex_rest | (4, 1) -> __sedlex_aux (__sedlex_pos - 1) __sedlex_prev_state 2 __sedlex_rest | (3, 2) -> (__sedlex_offsets.(1) <- __sedlex_pos; __sedlex_aux (__sedlex_pos - 1) __sedlex_prev_state 6 __sedlex_rest) | (0, 10) -> __sedlex_aux (__sedlex_pos - 1) __sedlex_prev_state 10 __sedlex_rest | (2, 10) -> __sedlex_aux (__sedlex_pos - 1) __sedlex_prev_state 10 __sedlex_rest | _ -> assert false) in

if prev_state is sometime useful, we could include it inside a guard only when needed.

~~The prev_state is still useful. It's a good idea to make it a guard.~~

Let me make more tests.

pmetzger · 2022-09-29T13:26:46Z

FYI, if one really wants to support capture groups correctly: https://re2c.org/#papers has several must-read papers.

dyzsr · 2022-09-29T14:36:06Z

@pmetzger Thanks for the link!

hhugo · 2022-10-03T08:30:13Z

src/syntax/ppx_sedlex.ml

+          let r2, s2 = aux allow_alias p2 in
+          if not (StrLocSet.equal s1 s2) then begin
+            let x =
+              try StrLocSet.choose (StrLocSet.diff s1 s2)


I would avoid the exception based selection. and use
StrLocSet.choose StrLocSet.(diff (union s1 s2) (inter s1 s2))

hhugo · 2022-10-04T09:32:55Z

I think it would be nice to commit the post-processed version of your test (like you did before) with the corresponding dune stanza so that the file is kept up to date automatically. I think this really helps when reviewing changes.

I've added this in hhugo@0284bfd

toots · 2022-10-22T14:25:29Z

Hey there! Do we want to try & come to a consensus on wether this could be merged?

pmetzger · 2022-10-24T14:47:05Z

@toots I think there's at least one code review comment above that hasn't yet been addressed? Generally I think we should merge though?

hhugo · 2022-10-24T17:45:27Z

I currently can't close/resolve threads. There are still a bunch unaddressed ones.

dyzsr added 7 commits August 25, 2022 21:23

Update .ocamlformat

8cda4b6

Add field alias to Sedlex.node

62b678a

Update regexp_of_pattern to analyze aliases

73e31fa

Refactor tracking path

2144578

Implement path tracing

d2b29d9

Fix location messages

5f3dea9

Fix version number

8f741b2

hhugo reviewed Sep 19, 2022

View reviewed changes

src/syntax/ppx_sedlex.ml Show resolved Hide resolved

dyzsr added 2 commits September 20, 2022 21:52

Bug fixes & Add testcases

ad3d0a0

Optimize traces generation

8e706d9

dyzsr marked this pull request as ready for review September 20, 2022 15:25

dyzsr requested review from alainfrisch, Drup and pmetzger as code owners September 20, 2022 15:25

dyzsr requested review from hhugo and removed request for Drup, pmetzger and alainfrisch September 20, 2022 15:38

hhugo reviewed Sep 20, 2022

View reviewed changes

src/syntax/ppx_sedlex.ml Outdated Show resolved Hide resolved

Make allow_alias a mandatory argument

214f689

hhugo reviewed Sep 21, 2022

View reviewed changes

toots reviewed Sep 21, 2022

View reviewed changes

hhugo reviewed Sep 27, 2022

View reviewed changes

dyzsr added 3 commits September 27, 2022 19:46

Update gen_alias & gen_offsets

1a2961a

Update actions

23bf119

Updates

e7258ef

hhugo reviewed Sep 27, 2022

View reviewed changes

Remove nodes_idx

5ae1589

hhugo reviewed Sep 27, 2022

View reviewed changes

dyzsr added 3 commits September 28, 2022 00:12

Optimize tracking path

5b63621

Update tracking path

c8224bf

Fix the use of try with

c63ff90

dyzsr force-pushed the support-as branch from 82bc82a to c63ff90 Compare September 28, 2022 15:04

Update tests

5f0bad9

Fix is_relevant

f54e94d

hhugo reviewed Oct 3, 2022

View reviewed changes

Support named capture groups #112

Are you sure you want to change the base?

Support named capture groups #112

Conversation

dyzsr commented Sep 19, 2022 • edited Loading

Usages

Implementation

Note

Others

dyzsr commented Sep 20, 2022 • edited Loading

dyzsr commented Sep 21, 2022

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

toots left a comment

Choose a reason for hiding this comment

hhugo commented Sep 21, 2022 • edited Loading

hhugo commented Sep 21, 2022

hhugo commented Sep 22, 2022

hhugo commented Sep 22, 2022

dyzsr commented Sep 26, 2022

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

hhugo Sep 27, 2022 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dyzsr Sep 28, 2022 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dyzsr Sep 28, 2022 • edited Loading

Choose a reason for hiding this comment

pmetzger commented Sep 29, 2022

dyzsr commented Sep 29, 2022

Choose a reason for hiding this comment

hhugo commented Oct 4, 2022

toots commented Oct 22, 2022

pmetzger commented Oct 24, 2022

hhugo commented Oct 24, 2022

dyzsr commented Sep 19, 2022 •

edited

Loading

dyzsr commented Sep 20, 2022 •

edited

Loading

hhugo commented Sep 21, 2022 •

edited

Loading

hhugo Sep 27, 2022 •

edited

Loading

dyzsr Sep 28, 2022 •

edited

Loading

dyzsr Sep 28, 2022 •

edited

Loading