Pass through unexpanded

[jayvdb]

I am using sre_yield to expand regexes where the result is sane, and want the ridiculous parts of the regex passed through unexpanded in the results.

I am currently achieving it by pre-processing known ridiculous bits to be '~~', and I intend to improve that by subclassing and catching&replace them dynamically. I think this could be a common need, as a way to allow usage when some cases are too complex for sre_yield to generate all possibilities, but most times it is ok.

[thatch]

I hadn't thought of sre_yield as a regex-to-regex transformer before. I think where things were headed with check_anchor_state is to reject ones that have syntax that's problematic. With more flags though, there could be other behavior.

Can you share the examples of your more ridiculous bits? I'm assuming based on #13 that your primary interest is in lookaround; do you need positive and negative lookahead (of varying length) and lookbehind? While a general solution is difficult, there are some special cases that can be preprocessed efficiently enough, either by transforming to a DFA or altering neighbors on the tree.

One pretty straightforward idea would be an option to make lookaround contribute nothing, so that you (the caller) postprocess by checking whether each resulting item matches the original regex. This should mean that len is an overestimate, the hack works not just for (?=a)[a-z] and (?!a)[a-z], but also .\b. and others.

[jayvdb]

I'll get my code and data up shortly - just need to investigate some more data errors. #13 was another set of problems, not related to this issue. Here I have large expansions I need to prevent from occurring so that I can process the saner expansions. Also related, I want to stop processing the regex at a literal which I know always appears, as the part after it is junk - however, the literal could appear inside subpatterns before the literal occurs, usually in the form [^/]+/other expensive uninteresting pattern junk where / is where I want to split the pattern. Again I have pre-processing occurring correctly, but I was using a derivation of BJörn Lindqvist's "inverse regex" with a 'stop_at' added and it was much cleaner and more efficient than my current pre-processing.

[thatch]

I assume these thousands of patterns are for URL routing? Without the lookaround do they have just a single match? (Curious for examples, especially around whether the max repeat and charset makes sense for them)

[thatch]

@jayvdb I found EFForg/https-everywhere#18938 -- is the script up somewhere now?

[jayvdb]

You found the data, and now the code is up at https://github.com/jayvdb/https-everywhere-py .

[thatch]

@jayvdb I read through the linked issue, and I don't quite get what the concrete proposal is. Are you planning on adding a callback to determine whether pieces of the pattern are interesting or not?

[jayvdb]

https://github.com/jayvdb/https-everywhere-py/blob/master/https_everywhere/_fixme.py#L202 is most of the problematic patterns, especially those with ~~ in the replacement.

Many are very precise, and iirc any expansion of \d+ and variations are suppressed, and it would be useful to provide a list of patterns (a subset of those) where no expansion is desirable. That would only partially solve the problem, but it would hit 80% of the problems, and I would keep my custom solution for the remaining 20% and those are the cases where failure is also acceptable, and can be fixed up sending PRs upstream to tighten up their patterns to make them more sane to expand.

Another approach to the same problem: I am wanting expansion, but I want to limit expansion, but I want the limit to apply to the most volatile part of the regex, rather than allowing a early part of the regex to hit the limit of the expansions and thereby not get access to the other (less explosive) variations which appear later in the regex expansion sequence.

[thatch]

I'm guessing, but do you want to:

• always expand something like a|b or (?:www\.)foo.com ?
• never expand \d or \wor.` ?

[jayvdb]

I would like the limited sequence of results to have a distribution that includes some expansions from each of the sub-patterns inside the pattern, instead of a sequential order that is cut at the limit.

The easiest approach is to invoke the expansion with a set of subpatterns that I do not want expanded at all, so that after invocation I can recognise input patterns which contained those patterns, and I then handle the output in some other way, either erroring, or post-processing, such as selectively pushing those sub-patterns into the expansion engine in some sensible way that avoids uncontrolled execution.

A basic approach is to allow applying a limit to each expansion of subpatterns found. i.e. subpattern_expansion_limit=100, limit=1000 which would allow only 100 expansions for each sub-pattern encountered, and stop expanding at 1000 items.

A slightly more balanced and dynamic approach would be expanding based the size of the expansion size of each sub-patterns results: Assuming the pattern is https?://(www\.)?\d\d\d\.(foo|bar)\.\w\w , (foo|bar) (2) should be expanded first for each \w\w next (30-ish if I limit the char space), for each \d\d\d (999).

i.e.

• www.000.foo.aa
• www.000.bar.aa
• www.000.foo.ab
• www.000.bar.ab
• ...
• www.000.foo.zz
• www.000.bar.zz
• www.001.foo.aa
• www.001.bar.aa
• ...

The rationale is that \d\d\d is usually shorthand for any three digit host name, even though it is known that the domain only has 000-010 currently, but it is expected they will add more nodes to their rack as required.

\.\w\w/ is usually shorthand for country code, and this is a candidate for having a callback to provide a custom expansion algorithm to supply only valid country codes.

[thatch]

If you want a regex-to-regex transform, that's not something we had in mind when writing sre_yield. I think you could walk the parse tree and replace subpatterns with other class instances without modifying sre_yield, but the matching to find your subpatterns feel like it might be tedious.

I think what you want is outside of the scope of sre_yield; it does one little thing and does it efficiently. I realize that might be unhelpful, but if you have a PR or want to go the subclass route I'm happy to review. Otherwise, this issue has been open long enough, and I'd like to close it out soon.

Another option would be use the more cst-like parse tree from my other regex project regexlint, which was designed around linting regular expressions and can reconstruct the original pattern after making changes. It doesn't have tree matching right now either, but has traversal functions that make writing your own matcher simple enough each time.

(.venv) [tim@rygel regexlint]$ python -m regexlint.parser 'https?://(www\.)?\d\d\d\.foo.com/'
/usr/lib/python3.8/runpy.py:127: RuntimeWarning: 'regexlint.parser' found in sys.modules after import of package 'regexlint', but prior to execution of 'regexlint.parser'; this may result in unpredictable behaviour
  warn(RuntimeWarning(msg))
<RootNode type=Token.Other.Progression data=''>
  <Node type=Token.Other.Literal data='h'>
  <Node type=Token.Other.Literal data='t'>
  <Node type=Token.Other.Literal data='t'>
  <Node type=Token.Other.Literal data='p'>
  <Repetition type=Token.Other.Repetition.Question data=''>
    <Node type=Token.Other.Literal data='s'>
  <Node type=Token.Other.Literal data=':'>
  <Node type=Token.Other.Literal data='/'>
  <Node type=Token.Other.Literal data='/'>
  <Repetition type=Token.Other.Repetition.Question data=''>
    <Node type=Token.Other.Open.Capturing data='('>
      <Node type=Token.Other.Literal data='w'>
      <Node type=Token.Other.Literal data='w'>
      <Node type=Token.Other.Literal data='w'>
      <Node type=Token.Other.Literal.Dot data='\\.'>
  <Node type=Token.Other.BuiltinCharclass data='\\d'>
  <Node type=Token.Other.BuiltinCharclass data='\\d'>
  <Node type=Token.Other.BuiltinCharclass data='\\d'>
  <Node type=Token.Other.Literal.Dot data='\\.'>
  <Node type=Token.Other.Literal data='f'>
  <Node type=Token.Other.Literal data='o'>
  <Node type=Token.Other.Literal data='o'>
  <Node type=Token.Other.Dot data='.'>
  <Node type=Token.Other.Literal data='c'>
  <Node type=Token.Other.Literal data='o'>
  <Node type=Token.Other.Literal data='m'>
  <Node type=Token.Other.Literal data='/'>

(to a first approximation, there's a recursive reconstruct method on nodes that either have children or data; the types are to aid walking to find what you want)

[jayvdb]

I do not want a regex output; that is exactly what I want to avoid. This discussion has been very useful, forcing me to think about the underlying requirement more and how to achieve it by allowing more control over how to limit the emitted values. It makes sense to implement it as a new WrappedSequence subclass, and it feels like it would be quite small. I'll get something together this week, and we'll work out whether it belongs here or outside of this project.