Repository: explosion/spaCy
Pull request: Addition of min_max quantifier in matcher {n,m}
<!--- Provide a general summary of your changes in the title. -->

## Description
<!--- Use this section to describe your changes. If your changes required
testing, include information about the testing environment and the tests you
ran. If your test fixes a bug reported in an issue, don't forget to include the
issue number. If your PR is still a work in progress, that's totally fine – just
include a note to let us know. -->
Reupload of #10919 
Resolved #5603 


Added min max quantifier {n,m}
![image](https://user-images.githubusercontent.com/82353723/174426573-7a208987-8bae-4a01-93bd-56d61b852597.png)

Summary
1. Modified API and Usage for spaCy website to include min_max operator
2. Modified matcher.pyx to include min_max function {n,m} and its variants
3. Modified schemas.py to include min_max validation error
4. Added test cases to test_matcher_api.py, test_matcher_logic.py and test_pattern_validation.py

### Types of change
<!-- What type of change does your PR cover? Is it a bug fix, an enhancement
or new feature, or a change to the documentation? -->
Min_max operator {n,m} for matcher
## Checklist
<!--- Before you submit the PR, go over this checklist and make sure you can
tick off all the boxes. [] -> [x] -->
- [x] I confirm that I have the right to submit this contribution under the project's MIT license.
- [x] I ran the tests, and all new and existing tests passed.
- [x] My changes don't require a change to the documentation, or if they do, I've added all required information.


Problem statement:
Is it possible to support quantifier (n,m) for rule matching? 

```
! | Negate the pattern, by requiring it to match exactly 0 times.
-- | --
? | Make the pattern optional, by allowing it to match 0 or 1 times.
+ | Require the pattern to match 1 or more times.
* | Allow the pattern to match zero or mo
```
In addition to the operators above, is it possible to support the {n,m} quantifier in the rule matcher? Or least {n} times. The reason is that, for linear matching, there is often a need to restrict how far two tokens occur in a piece of text. The shorter the distance, the more reliable the pattern. For example:

```
pattern = [{"LOWER": "hello"},
           {"LOWER": "world"}] 
```
For this pattern, I want to add an additional condition to require that the two words 'hello' and 'world' will be within a distance of no more than 12 words. Is there a way to express this logic for the current matcher? If not, how likely this can be supported by introducing the RE quantifier {n,m}? This is very useful for pattern matching in practical applications.

Hints from issue discussion:
If you have a simple pattern with one quantifier in the middle like  `A * B`, then we'd suggest using the `on_match` callback to filter matches based on length.

Since the `Matcher` doesn't support capturing groups, this is not going to help for more complicated patterns with multiple quantifiers, though.
Labeling this as "help wanted" - in case anyone is interested in implementing this feature, we'd accept a PR!
@lingvisa It it still matters to you, you can do it like so.

`
patterns = [TOKEN1] + [{"OP": "?"}] * num_of_padding + [TOKEN2]`

Hi @svlandeg I'd like to make my first contribution here if it is still opened...
Have the requirements changed since Sep 22, 2020 ?
Can you redirect me to the relevant code section ?

Hi! The matcher code can be found here: https://github.com/explosion/spaCy/blob/master/spacy/matcher/matcher.pyx
Thanks @svlandeg I am getting familiar with spacy codebase. I'll submit a PR as soon as possible

Commit message: formatting

Patch to review:
diff --git a/spacy/matcher/matcher.pyx b/spacy/matcher/matcher.pyx
index 981c5cdd265..5105f69edb8 100644
--- a/spacy/matcher/matcher.pyx
+++ b/spacy/matcher/matcher.pyx
@@ -86,10 +86,14 @@ cdef class Matcher:
         is a dictionary mapping attribute IDs to values, and optionally a
         quantifier operator under the key "op". The available quantifiers are:
 
-        '!': Negate the pattern, by requiring it to match exactly 0 times.
-        '?': Make the pattern optional, by allowing it to match 0 or 1 times.
-        '+': Require the pattern to match 1 or more times.
-        '*': Allow the pattern to zero or more times.
+        '!':      Negate the pattern, by requiring it to match exactly 0 times.
+        '?':      Make the pattern optional, by allowing it to match 0 or 1 times.
+        '+':      Require the pattern to match 1 or more times.
+        '*':      Allow the pattern to zero or more times.
+        '{n}':    Require the pattern to match exactly _n_ times.
+        '{n,m}':  Require the pattern to match at least _n_ but not more than _m_ times.
+        '{n,}':   Require the pattern to match at least _n_ times.
+        '{,m}':   Require the pattern to match at most _m_ times.
 
         The + and * operators return all possible matches (not just the greedy
         ones). However, the "greedy" argument can filter the final matches
@@ -1004,8 +1008,29 @@ def _get_operators(spec):
         return (ONE,)
     elif spec["OP"] in lookup:
         return lookup[spec["OP"]]
+    #Min_max {n,m}
+    elif spec["OP"].startswith("{") and spec["OP"].endswith("}"):
+        # {n}  --> {n,n}  exactly n                 ONE,(n)
+        # {n,m}--> {n,m}  min of n, max of m        ONE,(n),ZERO_ONE,(m)
+        # {,m} --> {0,m}  min of zero, max of m     ZERO_ONE,(m)
+        # {n,} --> {n,∞} min of n, max of inf       ONE,(n),ZERO_PLUS
+
+        min_max = spec["OP"][1:-1]
+        min_max = min_max if "," in min_max else f"{min_max},{min_max}"
+        n, m = min_max.split(",")
+
+        #1. Either n or m is a blank string and the other is numeric -->isdigit
+        #2. Both are numeric and n <= m
+        if (not n.isdecimal() and not m.isdecimal()) or (n.isdecimal() and m.isdecimal() and int(n) > int(m)):
+            keys = ", ".join(lookup.keys()) + ", {n}, {n,m}, {n,}, {,m} where n and m are integers and n <= m "
+            raise ValueError(Errors.E011.format(op=spec["OP"], opts=keys))
+
+        # if n is empty string, zero would be used
+        head = tuple(ONE for __ in range(int(n or 0)))
+        tail = tuple(ZERO_ONE for __ in range(int(m) - int(n or 0))) if m else (ZERO_PLUS,)
+        return head + tail
     else:
-        keys = ", ".join(lookup.keys())
+        keys = ", ".join(lookup.keys()) + ", {n}, {n,m}, {n,}, {,m} where n and m are integers and n <= m "
         raise ValueError(Errors.E011.format(op=spec["OP"], opts=keys))
 
 
diff --git a/spacy/schemas.py b/spacy/schemas.py
index b284b82e546..658e452688e 100644
--- a/spacy/schemas.py
+++ b/spacy/schemas.py
@@ -3,12 +3,13 @@
 from .compat import Literal
 from enum import Enum
 from pydantic import BaseModel, Field, ValidationError, validator, create_model
-from pydantic import StrictStr, StrictInt, StrictFloat, StrictBool
+from pydantic import StrictStr, StrictInt, StrictFloat, StrictBool, ConstrainedStr
 from pydantic.main import ModelMetaclass
 from thinc.api import Optimizer, ConfigValidationError, Model
 from thinc.config import Promise
 from collections import defaultdict
 import inspect
+import re
 
 from .attrs import NAMES
 from .lookups import Lookups
@@ -198,13 +199,18 @@ def raise_for_none(cls, v):
         return v
 
 
-class TokenPatternOperator(str, Enum):
+class TokenPatternOperatorSimple(str, Enum):
     plus: StrictStr = StrictStr("+")
-    start: StrictStr = StrictStr("*")
+    star: StrictStr = StrictStr("*")
     question: StrictStr = StrictStr("?")
     exclamation: StrictStr = StrictStr("!")
 
 
+class TokenPatternOperatorMinMax(ConstrainedStr):
+    regex = re.compile("^({\d+}|{\d+,\d*}|{\d*,\d+})$")
+
+
+TokenPatternOperator = Union[TokenPatternOperatorSimple, TokenPatternOperatorMinMax]
 StringValue = Union[TokenPatternString, StrictStr]
 NumberValue = Union[TokenPatternNumber, StrictInt, StrictFloat]
 UnderscoreValue = Union[
diff --git a/spacy/tests/matcher/test_matcher_api.py b/spacy/tests/matcher/test_matcher_api.py
index e8c3d53e833..2c2af6ce5f0 100644
--- a/spacy/tests/matcher/test_matcher_api.py
+++ b/spacy/tests/matcher/test_matcher_api.py
@@ -680,3 +680,38 @@ def test_matcher_ent_iob_key(en_vocab):
     assert matches[0] == "Maria"
     assert matches[1] == "Maria Esperanza"
     assert matches[2] == "Esperanza"
+
+
+def test_matcher_min_max_operator(en_vocab):
+    # Exactly n matches {n}
+    doc = Doc(
+        en_vocab, words=["foo", "bar", "foo", "foo", "bar",
+                         "foo", "foo", "foo", "bar", "bar"]
+    )
+    matcher = Matcher(en_vocab)
+    pattern = [{"ORTH": "foo", "OP": "{3}"}]
+    matcher.add("TEST", [pattern])
+
+    matches1 = [doc[start:end].text for _, start, end in matcher(doc)]
+    assert len(matches1) == 1
+
+    # At least n matches {n,}
+    matcher = Matcher(en_vocab)
+    pattern = [{"ORTH": "foo", "OP": "{2,}"}]
+    matcher.add("TEST", [pattern])
+    matches2 = [doc[start:end].text for _, start, end in matcher(doc)]
+    assert len(matches2) == 4
+
+    # At most m matches {,m}
+    matcher = Matcher(en_vocab)
+    pattern = [{"ORTH": "foo", "OP": "{,2}"}]
+    matcher.add("TEST", [pattern])
+    matches3 = [doc[start:end].text for _, start, end in matcher(doc)]
+    assert len(matches3) == 9
+
+    # At least n matches and most m matches {n,m}
+    matcher = Matcher(en_vocab)
+    pattern = [{"ORTH": "foo", "OP": "{2,3}"}]
+    matcher.add("TEST", [pattern])
+    matches4 = [doc[start:end].text for _, start, end in matcher(doc)]
+    assert len(matches4) == 4
diff --git a/spacy/tests/matcher/test_matcher_logic.py b/spacy/tests/matcher/test_matcher_logic.py
index 3649b07ed37..3b65fee23e4 100644
--- a/spacy/tests/matcher/test_matcher_logic.py
+++ b/spacy/tests/matcher/test_matcher_logic.py
@@ -699,6 +699,10 @@ def test_matcher_with_alignments_greedy_longest(en_vocab):
         ("aaaa", "a a a a a?", [0, 1, 2, 3]),
         ("aaab", "a+ a b", [0, 0, 1, 2]),
         ("aaab", "a+ a+ b", [0, 0, 1, 2]),
+        ("aaab", "a{2,} b", [0, 0, 0, 1]),
+        ("aaab", "a{,3} b", [0, 0, 0, 1]),
+        ("aaab", "a{2} b", [0, 0, 1]),
+        ("aaab", "a{2,3} b", [0, 0, 0, 1]),
     ]
     for string, pattern_str, result in cases:
         matcher = Matcher(en_vocab)
@@ -711,6 +715,8 @@ def test_matcher_with_alignments_greedy_longest(en_vocab):
                 pattern.append({"ORTH": part[0], "OP": "*"})
             elif part.endswith("?"):
                 pattern.append({"ORTH": part[0], "OP": "?"})
+            elif part.endswith("}"):
+                pattern.append({"ORTH": part[0], "OP": part[1:]})
             else:
                 pattern.append({"ORTH": part})
         matcher.add("PATTERN", [pattern], greedy="LONGEST")
@@ -722,7 +728,7 @@ def test_matcher_with_alignments_greedy_longest(en_vocab):
         assert expected == result, (string, pattern_str, s, e, n_matches)
 
 
-def test_matcher_with_alignments_nongreedy(en_vocab):
+def test_matcher_with_alignments_non_greedy(en_vocab):
     cases = [
         (0, "aaab", "a* b", [[0, 1], [0, 0, 1], [0, 0, 0, 1], [1]]),
         (1, "baab", "b a* b", [[0, 1, 1, 2]]),
@@ -752,6 +758,10 @@ def test_matcher_with_alignments_nongreedy(en_vocab):
         (15, "aaaa", "a a a a a?", [[0, 1, 2, 3]]),
         (16, "aaab", "a+ a b", [[0, 1, 2], [0, 0, 1, 2]]),
         (17, "aaab", "a+ a+ b", [[0, 1, 2], [0, 0, 1, 2]]),
+        (18, "aaab", "a{2,} b", [[0, 0, 1], [0, 0, 0, 1]]),
+        (19, "aaab", "a{3} b", [[0, 0, 0, 1]]),
+        (20, "aaab", "a{2} b", [[0, 0, 1]]),
+        (21, "aaab", "a{2,3} b", [[0, 0, 1], [0, 0, 0, 1]]),
     ]
     for case_id, string, pattern_str, results in cases:
         matcher = Matcher(en_vocab)
@@ -764,6 +774,8 @@ def test_matcher_with_alignments_nongreedy(en_vocab):
                 pattern.append({"ORTH": part[0], "OP": "*"})
             elif part.endswith("?"):
                 pattern.append({"ORTH": part[0], "OP": "?"})
+            elif part.endswith("}"):
+                pattern.append({"ORTH": part[0], "OP": part[1:]})
             else:
                 pattern.append({"ORTH": part})
 
diff --git a/spacy/tests/matcher/test_pattern_validation.py b/spacy/tests/matcher/test_pattern_validation.py
index 8c265785cc8..58d68bbd5a4 100644
--- a/spacy/tests/matcher/test_pattern_validation.py
+++ b/spacy/tests/matcher/test_pattern_validation.py
@@ -17,6 +17,8 @@
     # Bad patterns flagged outside of Matcher
     ([{"_": {"foo": "bar", "baz": {"IN": "foo"}}}], 2, 0),  # prev: (1, 0)
     # Bad patterns not flagged with minimal checks
+    ([{"TEXT": "foo", "OP": "{,}"}], 1, 1),
+    ([{"TEXT": "foo", "OP": "{,4}4"}], 1, 1),
     ([{"LENGTH": "2", "TEXT": 2}, {"LOWER": "test"}], 2, 0),
     ([{"LENGTH": {"IN": [1, 2, "3"]}}, {"POS": {"IN": "VERB"}}], 4, 0),  # prev: (2, 0)
     ([{"LENGTH": {"VALUE": 5}}], 2, 0),  # prev: (1, 0)
@@ -38,6 +40,7 @@
     ([{"SENT_START": True}], 0, 0),
     ([{"ENT_ID": "STRING"}], 0, 0),
     ([{"ENT_KB_ID": "STRING"}], 0, 0),
+    ([{"TEXT": "ha", "OP": "{3}"}], 0, 0),
 ]
 
 
diff --git a/website/docs/api/matcher.md b/website/docs/api/matcher.md
index 9daa0658d8f..ab88c419417 100644
--- a/website/docs/api/matcher.md
+++ b/website/docs/api/matcher.md
@@ -59,15 +59,20 @@ matched:
 > [
 >   {"POS": "ADJ", "OP": "*"},
 >   {"POS": "NOUN", "OP": "+"}
+>   {"POS": "PROPN", "OP": "{2}"}
 > ]
 > ```
 
-| OP  | Description                                                      |
-| --- | ---------------------------------------------------------------- |
-| `!` | Negate the pattern, by requiring it to match exactly 0 times.    |
-| `?` | Make the pattern optional, by allowing it to match 0 or 1 times. |
-| `+` | Require the pattern to match 1 or more times.                    |
-| `*` | Allow the pattern to match 0 or more times.                      |
+| OP      | Description                                                            |
+|---------|------------------------------------------------------------------------|
+| `!`     | Negate the pattern, by requiring it to match exactly 0 times.          |
+| `?`     | Make the pattern optional, by allowing it to match 0 or 1 times.       |
+| `+`     | Require the pattern to match 1 or more times.                          |
+| `*`     | Allow the pattern to match 0 or more times.                            |
+| `{n}`   | Require the pattern to match exactly _n_ times.                        |
+| `{n,m}` | Require the pattern to match at least _n_ but not more than _m_ times. |
+| `{n,}`  | Require the pattern to match at least _n_ times.                       |
+| `{,m}`  | Require the pattern to match at most _m_ times.                        |
 
 Token patterns can also map to a **dictionary of properties** instead of a
 single value to indicate whether the expected value is a member of a list or how
diff --git a/website/docs/usage/rule-based-matching.md b/website/docs/usage/rule-based-matching.md
index e4ba4b2af74..f096890cba2 100644
--- a/website/docs/usage/rule-based-matching.md
+++ b/website/docs/usage/rule-based-matching.md
@@ -374,12 +374,16 @@ punctuation marks, or specify optional tokens. Note that there are no nested or
 scoped quantifiers – instead, you can build those behaviors with `on_match`
 callbacks.
 
-| OP  | Description                                                      |
-| --- | ---------------------------------------------------------------- |
-| `!` | Negate the pattern, by requiring it to match exactly 0 times.    |
-| `?` | Make the pattern optional, by allowing it to match 0 or 1 times. |
-| `+` | Require the pattern to match 1 or more times.                    |
-| `*` | Allow the pattern to match zero or more times.                   |
+| OP      | Description                                                            |
+|---------|------------------------------------------------------------------------|
+| `!`     | Negate the pattern, by requiring it to match exactly 0 times.          |
+| `?`     | Make the pattern optional, by allowing it to match 0 or 1 times.       |
+| `+`     | Require the pattern to match 1 or more times.                          |
+| `*`     | Allow the pattern to match zero or more times.                         |
+| `{n}`   | Require the pattern to match exactly _n_ times.                        |
+| `{n,m}` | Require the pattern to match at least _n_ but not more than _m_ times. |
+| `{n,}`  | Require the pattern to match at least _n_ times.                       |
+| `{,m}`  | Require the pattern to match at most _m_ times.                        |
 
 > #### Example
 >


Code review comments:
diff_hunk: @@ -17,6 +17,8 @@
     # Bad patterns flagged outside of Matcher
     ([{"_": {"foo": "bar", "baz": {"IN": "foo"}}}], 2, 0),  # prev: (1, 0)
     # Bad patterns not flagged with minimal checks
+    ([{"TEXT": "foo", "OP": "{,}"}], 1, 1),
+    ([{"TEXT": "foo", "OP": "{,4}4"}], 1, 1),
path: spacy/tests/matcher/test_pattern_validation.py
text: @user1:
```suggestion
    ([{"TEXT": "foo", "OP": "{,}"}], 1, 1),
    ([{"TEXT": "foo", "OP": "{,4}4"}], 1, 1),
    ([{"TEXT": "foo", "OP": "{a,3}"}], 1, 1),
    ([{"TEXT": "foo", "OP": "{a}"}], 1, 1),
    ([{"TEXT": "foo", "OP": "{,a}"}], 1, 1),
    ([{"TEXT": "foo", "OP": "{1,2,3}"}], 1, 1),
    ([{"TEXT": "foo", "OP": "{1, 3}"}], 1, 1),
    ([{"TEXT": "foo", "OP": "{-2}"}], 1, 1),
    # Bad patterns flagged outside of Matcher
    ([{"_": {"foo": "bar", "baz": {"IN": "foo"}}}], 2, 0),  # prev: (1, 0)
    # Bad patterns not flagged with minimal checks
```