Repository: DmitrySoshnikov/regexp-tree
Pull request #99 (2017-11-12 13:26:36)

Add support for quantifiers merge in Optimizer
This transform will merge siblings quantifiers.

`/a+a+a+/` -> `/a{3,}/`
`/a+a*/` ->` /a+/`
`/a{4,5}a{2}a{1}/` -> `/a{7,8}/`
`/a??a??/` -> `/a{0,2}?/`

The process is aborted when the two quantifiers have a different greediness and none of them is an open greedy quantifier, because I couldn't think of a reliable way to merge them (if there is...):
`/a{1,2}?a{1,2}/` is left untouched (since it has not the same behaviour as `/a{2,4}/` nor `/a{2,4}?/`)


Patch:
diff --git a/src/optimizer/transforms/char-star-to-plus-transform.js b/src/optimizer/transforms/char-star-to-plus-transform.js
deleted file mode 100644
index df80685..0000000
--- a/src/optimizer/transforms/char-star-to-plus-transform.js
+++ /dev/null
@@ -1,39 +0,0 @@
-/**
- * The MIT License (MIT)
- * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
- */
-
-'use strict';
-
-/**
- * A regexp-tree plugin to replace `aa*` to `a+`.
- */
-module.exports = {
-
-  Repetition(path) {
-    const {node, parent} = path;
-
-    if (
-      node.quantifier.kind !== '*' ||
-      parent.type !== 'Alternative' ||
-      !path.index
-    ) {
-      return;
-    }
-
-    const previousSibling = path.getPreviousSibling();
-
-    if (
-      !previousSibling ||
-      !previousSibling.hasEqualSource(path.getChild())
-    ) {
-      return;
-    }
-
-    // Remove previous symbol. TODO, operate on NodePath for previous siblings.
-    previousSibling.remove();
-
-    // Change quantifier.
-    node.quantifier.kind = '+';
-  }
-};
\ No newline at end of file
diff --git a/src/optimizer/transforms/index.js b/src/optimizer/transforms/index.js
index 28e997c..7f074d8 100644
--- a/src/optimizer/transforms/index.js
+++ b/src/optimizer/transforms/index.js
@@ -9,6 +9,9 @@ module.exports = [
   // [\d\d] -> [\d]
   require('./char-class-remove-duplicates-transform'),
 
+  // a{1,2}a{2,3} -> a{3,5}
+  require('./quantifiers-merge-transform'),
+
   // a{1,} -> a+, a{3,3} -> a{3}, a{1} -> a
   require('./quantifier-range-to-symbol-transform'),
 
@@ -18,9 +21,6 @@ module.exports = [
   // [\d] -> \d, [^\w] -> \W
   require('./char-class-to-single-char-transform'),
 
-  // aa* -> a+
-  require('./char-star-to-plus-transform'),
-
   // \e -> e
   require('./char-escape-unescape-transform'),
 
diff --git a/src/optimizer/transforms/quantifiers-merge-transform.js b/src/optimizer/transforms/quantifiers-merge-transform.js
new file mode 100644
index 0000000..3c1eb19
--- /dev/null
+++ b/src/optimizer/transforms/quantifiers-merge-transform.js
@@ -0,0 +1,160 @@
+/**
+ * The MIT License (MIT)
+ * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ */
+
+'use strict';
+
+/**
+ * A regexp-tree plugin to merge quantifiers
+ *
+ * a+a+ -> a{2,}
+ * a{2}a{3} -> a{5}
+ * a{1,2}a{2,3} -> a{3,5}
+ */
+module.exports = {
+
+  Repetition(path) {
+    const {node, parent} = path;
+
+    if (
+      parent.type !== 'Alternative' ||
+      !path.index
+    ) {
+      return;
+    }
+
+    const previousSibling = path.getPreviousSibling();
+
+    if (!previousSibling) {
+      return;
+    }
+
+    if (previousSibling.node.type === 'Repetition') {
+      if (!previousSibling.getChild().hasEqualSource(path.getChild())) {
+        return;
+      }
+
+      let {
+        from: previousSiblingFrom,
+        to: previousSiblingTo
+      } = extractFromTo(previousSibling.node.quantifier);
+
+      let {
+        from: nodeFrom,
+        to: nodeTo
+      } = extractFromTo(node.quantifier);
+
+      // It's does not seem reliable to merge quantifiers with different greediness
+      // when none of both is a greedy open range
+      if (
+        previousSibling.node.quantifier.greedy !== node.quantifier.greedy &&
+        !isGreedyOpenRange(previousSibling.node.quantifier) &&
+        !isGreedyOpenRange(node.quantifier)
+      ) {
+        return;
+      }
+
+      // a*a* -> a*
+      // a*a+ -> a+
+      // a+a+ -> a{2,}
+      // a{2}a{4} -> a{6}
+      // a{1,2}a{2,3} -> a{3,5}
+      // a{1,}a{2,} -> a{3,}
+      // a+a{2,} -> a{3,}
+
+      // a??a{2,} -> a{2,}
+      // a*?a{2,} -> a{2,}
+      // a+?a{2,} -> a{3,}
+
+      node.quantifier.kind = 'Range';
+      node.quantifier.from = previousSiblingFrom + nodeFrom;
+      if (previousSiblingTo && nodeTo) {
+        node.quantifier.to = previousSiblingTo + nodeTo;
+      } else {
+        delete node.quantifier.to;
+      }
+      if (
+        isGreedyOpenRange(previousSibling.node.quantifier) ||
+        isGreedyOpenRange(node.quantifier)
+      ) {
+        node.quantifier.greedy = true;
+      }
+
+      previousSibling.remove();
+
+    } else {
+      if (!previousSibling.hasEqualSource(path.getChild())) {
+        return;
+      }
+
+      if (node.quantifier.kind === '*') {
+        // aa* -> a+
+        // aa*? -> a+?
+        node.quantifier.kind = '+';
+
+        previousSibling.remove();
+
+      } else if (node.quantifier.kind === '+') {
+        // aa+ -> a{2,}
+        // aa+? -> a{2,}?
+        node.quantifier.kind = 'Range';
+        node.quantifier.from = 2;
+        delete node.quantifier.to;
+
+        previousSibling.remove();
+
+      } else if (node.quantifier.kind === '?') {
+        // aa? -> a{1,2}
+        // aa?? -> a{1,2}?
+        node.quantifier.kind = 'Range';
+        node.quantifier.from = 1;
+        node.quantifier.to = 2;
+
+        previousSibling.remove();
+
+      } else if (node.quantifier.kind === 'Range') {
+        // aa{3} -> a{4}
+        // aa{3}? -> a{4}?
+        // aa{3,} -> a{4,}
+        // aa{3,}? -> a{4,}?
+        // aa{3,5} -> a{4,6}
+        // aa{3,5}? -> a{4,6}?
+        node.quantifier.from = node.quantifier.from + 1;
+        if (node.quantifier.to) {
+          node.quantifier.to = node.quantifier.to + 1;
+        }
+
+        previousSibling.remove();
+
+      }
+    }
+  }
+};
+
+function isGreedyOpenRange(quantifier) {
+  return quantifier.greedy &&
+    (
+      quantifier.kind === '+' ||
+      quantifier.kind === '*' ||
+      (quantifier.kind === 'Range' && !quantifier.to)
+    );
+}
+
+function extractFromTo(quantifier) {
+  let from, to;
+  if (quantifier.kind === '*') {
+    from = 0;
+  } else if (quantifier.kind === '+') {
+    from = 1;
+  } else if (quantifier.kind === '?') {
+    from = 0;
+    to = 1;
+  } else {
+    from = quantifier.from;
+    if (quantifier.to) {
+      to = quantifier.to;
+    }
+  }
+  return {from, to};
+}
\ No newline at end of file


Test patch:
diff --git a/src/optimizer/transforms/__tests__/char-star-to-plus-transform-test.js b/src/optimizer/transforms/__tests__/char-star-to-plus-transform-test.js
deleted file mode 100644
index 9071d7c..0000000
--- a/src/optimizer/transforms/__tests__/char-star-to-plus-transform-test.js
+++ /dev/null
@@ -1,27 +0,0 @@
-/**
- * The MIT License (MIT)
- * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
- */
-
-'use strict';
-
-const {transform} = require('../../../transform');
-const charStarToPlus = require('../char-star-to-plus-transform');
-
-describe('aa* -> a+', () => {
-
-  it('replaces simple chars', () => {
-    const re = transform(/aa*/, [
-      charStarToPlus,
-    ]);
-    expect(re.toString()).toBe('/a+/');
-  });
-
-  it('replaces complex patterns', () => {
-    const re = transform(/[a-zA-Z_0-9][a-zA-Z_0-9]*/, [
-      charStarToPlus,
-    ]);
-    expect(re.toString()).toBe('/[a-zA-Z_0-9]+/');
-  });
-
-});
\ No newline at end of file
diff --git a/src/optimizer/transforms/__tests__/quantifiers-merge-transform-test.js b/src/optimizer/transforms/__tests__/quantifiers-merge-transform-test.js
new file mode 100644
index 0000000..cfeedf0
--- /dev/null
+++ b/src/optimizer/transforms/__tests__/quantifiers-merge-transform-test.js
@@ -0,0 +1,991 @@
+/**
+ * The MIT License (MIT)
+ * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ */
+
+'use strict';
+
+const {transform} = require('../../../transform');
+const quantifiersMerge = require('../quantifiers-merge-transform');
+
+describe('merge quantifiers with simple previous sibling', () => {
+
+  it('aa* -> a+', () => {
+    const re = transform(/aa*/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a+/');
+
+    const re2 = transform(/aa*?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a+?/');
+  });
+
+  it('aa+ -> a{2,}', () => {
+    const re = transform(/aa+/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+
+    const re2 = transform(/aa+?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}?/');
+  });
+
+  it('aa? -> a{1,2}', () => {
+    const re = transform(/aa?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,2}/');
+
+    const re2 = transform(/aa??/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,2}?/');
+  });
+
+  it('aa{3} -> a{4}', () => {
+    const re = transform(/aa{3}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{4}/');
+
+    const re2 = transform(/aa{3}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{4}?/');
+  });
+
+  it('aa{3,} -> a{4,}', () => {
+    const re = transform(/aa{3,}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{4,}/');
+
+    const re2 = transform(/aa{3,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{4,}?/');
+  });
+
+  it('aa{3,5} -> a{4,6}', () => {
+    const re = transform(/aa{3,5}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{4,6}/');
+
+    const re2 = transform(/aa{3,5}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{4,6}?/');
+  });
+});
+
+describe('merge closed greedy quantifier with closed greedy quantifier', () => {
+
+  it('a?a?', () => {
+    const re = transform(/a?a?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{0,2}/');
+  });
+
+  it('a?a{2}', () => {
+    const re = transform(/a?a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,3}/');
+
+    const re2 = transform(/a{2}a?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,3}/');
+  });
+
+  it('a?a{1,2}', () => {
+    const re = transform(/a?a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,3}/');
+
+    const re2 = transform(/a{1,2}a?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,3}/');
+  });
+
+  it('a{2}a{2}', () => {
+    const re = transform(/a{2}a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{4}/');
+  });
+
+  it('a{2}a{1,2}', () => {
+    const re = transform(/a{2}a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,4}/');
+
+    const re2 = transform(/a{1,2}a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,4}/');
+  });
+
+  it('a{1,2}a{1,2}', () => {
+    const re = transform(/a{1,2}a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,4}/');
+  });
+});
+
+describe('do not merge closed greedy quantifier with closed ungreedy quantifier', () => {
+
+  it('a?a??', () => {
+    const re = transform(/a?a??/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a?a??/');
+
+    const re2 = transform(/a??a?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a??a?/');
+  });
+
+  it('a?a{2}?', () => {
+    const re = transform(/a?a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a?a{2}?/');
+
+    const re2 = transform(/a{2}?a?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2}?a?/');
+  });
+
+  it('a?a{1,2}?', () => {
+    const re = transform(/a?a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a?a{1,2}?/');
+
+    const re2 = transform(/a{1,2}?a?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,2}?a?/');
+  });
+
+  it('a{2}a??', () => {
+    const re = transform(/a{2}a??/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2}a??/');
+
+    const re2 = transform(/a??a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a??a{2}/');
+  });
+
+  it('a{2}a{2}?', () => {
+    const re = transform(/a{2}a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2}a{2}?/');
+
+    const re2 = transform(/a{2}?a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2}?a{2}/');
+  });
+
+  it('a{2}a{1,2}?', () => {
+    const re = transform(/a{2}a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2}a{1,2}?/');
+
+    const re2 = transform(/a{1,2}?a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,2}?a{2}/');
+  });
+
+  it('a{1,2}a??', () => {
+    const re = transform(/a{1,2}a??/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,2}a??/');
+
+    const re2 = transform(/a??a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a??a{1,2}/');
+  });
+
+  it('a{1,2}a{2}?', () => {
+    const re = transform(/a{1,2}a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,2}a{2}?/');
+
+    const re2 = transform(/a{2}?a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2}?a{1,2}/');
+  });
+
+  it('a{1,2}a{1,2}?', () => {
+    const re = transform(/a{1,2}a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,2}a{1,2}?/');
+
+    const re2 = transform(/a{1,2}?a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,2}?a{1,2}/');
+  });
+});
+
+describe('merge closed greedy quantifier with open greedy quantifier', () => {
+
+  it('a?a+', () => {
+    const re = transform(/a?a+/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,}/');
+
+    const re2 = transform(/a+a?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,}/');
+  });
+
+  it('a?a*', () => {
+    const re = transform(/a?a*/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{0,}/');
+
+    const re2 = transform(/a*a?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{0,}/');
+  });
+
+  it('a?a{2,}', () => {
+    const re = transform(/a?a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+
+    const re2 = transform(/a{2,}a?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}/');
+  });
+
+  it('a{2}a+', () => {
+    const re = transform(/a{2}a+/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,}/');
+
+    const re2 = transform(/a+a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,}/');
+  });
+
+  it('a{2}a*', () => {
+    const re = transform(/a{2}a*/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+
+    const re2 = transform(/a*a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}/');
+  });
+
+  it('a{2}a{2,}', () => {
+    const re = transform(/a{2}a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{4,}/');
+
+    const re2 = transform(/a{2,}a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{4,}/');
+  });
+
+  it('a{1,2}a+', () => {
+    const re = transform(/a{1,2}a+/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+
+    const re2 = transform(/a+a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}/');
+  });
+
+  it('a{1,2}a*', () => {
+    const re = transform(/a{1,2}a*/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,}/');
+
+    const re2 = transform(/a*a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,}/');
+  });
+
+  it('a{1,2}a{2,}', () => {
+    const re = transform(/a{1,2}a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,}/');
+
+    const re2 = transform(/a{2,}a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,}/');
+  });
+});
+
+describe('do not merge closed greedy quantifier with open ungreedy quantifier', () => {
+
+  it('a?a+?', () => {
+    const re = transform(/a?a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a?a+?/');
+
+    const re2 = transform(/a+?a?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a+?a?/');
+  });
+
+  it('a?a*?', () => {
+    const re = transform(/a?a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a?a*?/');
+
+    const re2 = transform(/a*?a?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a*?a?/');
+  });
+
+  it('a?a{2,}?', () => {
+    const re = transform(/a?a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a?a{2,}?/');
+
+    const re2 = transform(/a{2,}?a?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}?a?/');
+  });
+
+  it('a{2}a+?', () => {
+    const re = transform(/a{2}a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2}a+?/');
+
+    const re2 = transform(/a+?a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a+?a{2}/');
+  });
+
+  it('a{2}a*?', () => {
+    const re = transform(/a{2}a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2}a*?/');
+
+    const re2 = transform(/a*?a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a*?a{2}/');
+  });
+
+  it('a{2}a{2,}?', () => {
+    const re = transform(/a{2}a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2}a{2,}?/');
+
+    const re2 = transform(/a{2,}?a{2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}?a{2}/');
+  });
+
+  it('a{1,2}a+?', () => {
+    const re = transform(/a{1,2}a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,2}a+?/');
+
+    const re2 = transform(/a+?a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a+?a{1,2}/');
+  });
+
+  it('a{1,2}a*?', () => {
+    const re = transform(/a{1,2}a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,2}a*?/');
+
+    const re2 = transform(/a*?a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a*?a{1,2}/');
+  });
+
+  it('a{1,2}a{2,}?', () => {
+    const re = transform(/a{1,2}a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,2}a{2,}?/');
+
+    const re2 = transform(/a{2,}?a{1,2}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}?a{1,2}/');
+  });
+});
+
+describe('merge closed ungreedy quantifier with closed ungreedy quantifier', () => {
+
+  it('a??a??', () => {
+    const re = transform(/a??a??/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{0,2}?/');
+  });
+
+  it('a??a{2}?', () => {
+    const re = transform(/a??a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,3}?/');
+
+    const re2 = transform(/a{2}?a??/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,3}?/');
+  });
+
+  it('a??a{1,2}?', () => {
+    const re = transform(/a??a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,3}?/');
+
+    const re2 = transform(/a{1,2}?a??/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,3}?/');
+  });
+
+  it('a{2}?a{2}?', () => {
+    const re = transform(/a{2}?a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{4}?/');
+  });
+
+  it('a{2}?a{1,2}?', () => {
+    const re = transform(/a{2}?a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,4}?/');
+
+    const re2 = transform(/a{1,2}?a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,4}?/');
+  });
+
+  it('a{1,2}?a{1,2}?', () => {
+    const re = transform(/a{1,2}?a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,4}?/');
+  });
+});
+
+describe('merge closed ungreedy quantifier with open greedy quantifier', () => {
+
+  it('a??a+', () => {
+    const re = transform(/a??a+/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,}/');
+
+    const re2 = transform(/a+a??/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,}/');
+  });
+
+  it('a??a*', () => {
+    const re = transform(/a??a*/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{0,}/');
+
+    const re2 = transform(/a*a??/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{0,}/');
+  });
+
+  it('a??a{2,}', () => {
+    const re = transform(/a??a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+
+    const re2 = transform(/a{2,}a??/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}/');
+  });
+
+  it('a{2}?a+', () => {
+    const re = transform(/a{2}?a+/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,}/');
+
+    const re2 = transform(/a+a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,}/');
+  });
+
+  it('a{2}?a*', () => {
+    const re = transform(/a{2}?a*/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+
+    const re2 = transform(/a*a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}/');
+  });
+
+  it('a{2}?a{2,}', () => {
+    const re = transform(/a{2}?a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{4,}/');
+
+    const re2 = transform(/a{2,}a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{4,}/');
+  });
+
+  it('a{1,2}?a+', () => {
+    const re = transform(/a{1,2}?a+/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+
+    const re2 = transform(/a+a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}/');
+  });
+
+  it('a{1,2}?a*', () => {
+    const re = transform(/a{1,2}?a*/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,}/');
+
+    const re2 = transform(/a*a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,}/');
+  });
+
+  it('a{1,2}?a{2,}', () => {
+    const re = transform(/a{1,2}?a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,}/');
+
+    const re2 = transform(/a{2,}a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,}/');
+  });
+});
+
+describe('merge closed ungreedy quantifier with open ungreedy quantifier', () => {
+
+  it('a??a+?', () => {
+    const re = transform(/a??a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,}?/');
+
+    const re2 = transform(/a+?a??/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,}?/');
+  });
+
+  it('a??a*?', () => {
+    const re = transform(/a??a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{0,}?/');
+
+    const re2 = transform(/a*?a??/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{0,}?/');
+  });
+
+  it('a??a{2,}?', () => {
+    const re = transform(/a??a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}?/');
+
+    const re2 = transform(/a{2,}?a??/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}?/');
+  });
+
+  it('a{2}?a+?', () => {
+    const re = transform(/a{2}?a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,}?/');
+
+    const re2 = transform(/a+?a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,}?/');
+  });
+
+  it('a{2}?a*?', () => {
+    const re = transform(/a{2}?a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}?/');
+
+    const re2 = transform(/a*?a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}?/');
+  });
+
+  it('a{2}?a{2,}?', () => {
+    const re = transform(/a{2}?a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{4,}?/');
+
+    const re2 = transform(/a{2,}?a{2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{4,}?/');
+  });
+
+  it('a{1,2}?a+?', () => {
+    const re = transform(/a{1,2}?a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}?/');
+
+    const re2 = transform(/a+?a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}?/');
+  });
+
+  it('a{1,2}?a*?', () => {
+    const re = transform(/a{1,2}?a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,}?/');
+
+    const re2 = transform(/a*?a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,}?/');
+  });
+
+  it('a{1,2}?a{2,}?', () => {
+    const re = transform(/a{1,2}?a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,}?/');
+
+    const re2 = transform(/a{2,}?a{1,2}?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,}?/');
+  });
+});
+
+describe('merge open greedy quantifier with open greedy quantifier', () => {
+
+  it('a+a+', () => {
+    const re = transform(/a+a+/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+  });
+
+  it('a+a*', () => {
+    const re = transform(/a+a*/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,}/');
+
+    const re2 = transform(/a*a+/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,}/');
+  });
+
+  it('a+a{2,}', () => {
+    const re = transform(/a+a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,}/');
+
+    const re2 = transform(/a{2,}a+/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,}/');
+  });
+
+  it('a*a*', () => {
+    const re = transform(/a*a*/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{0,}/');
+  });
+
+  it('a*a{2,}', () => {
+    const re = transform(/a*a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+
+    const re2 = transform(/a{2,}a*/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}/');
+  });
+
+  it('a{2,}a{2,}', () => {
+    const re = transform(/a{2,}a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{4,}/');
+  });
+});
+
+describe('merge open greedy quantifier with open ungreedy quantifier', () => {
+
+  it('a+a+?', () => {
+    const re = transform(/a+a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+
+    const re2 = transform(/a+?a+/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}/');
+  });
+
+  it('a+a*?', () => {
+    const re = transform(/a+a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,}/');
+
+    const re2 = transform(/a*?a+/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,}/');
+  });
+
+  it('a+a{2,}?', () => {
+    const re = transform(/a+a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,}/');
+
+    const re2 = transform(/a{2,}?a+/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,}/');
+  });
+
+  it('a*a+?', () => {
+    const re = transform(/a*a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,}/');
+
+    const re2 = transform(/a+?a*/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,}/');
+  });
+
+  it('a*a*?', () => {
+    const re = transform(/a*a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{0,}/');
+
+    const re2 = transform(/a*?a*/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{0,}/');
+  });
+
+  it('a*a{2,}?', () => {
+    const re = transform(/a*a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+
+    const re2 = transform(/a{2,}?a*/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}/');
+  });
+
+  it('a{2,}a+?', () => {
+    const re = transform(/a{2,}a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,}/');
+
+    const re2 = transform(/a+?a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,}/');
+  });
+
+  it('a{2,}a*?', () => {
+    const re = transform(/a{2,}a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}/');
+
+    const re2 = transform(/a*?a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}/');
+  });
+
+  it('a{2,}a{2,}?', () => {
+    const re = transform(/a{2,}a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{4,}/');
+
+    const re2 = transform(/a{2,}?a{2,}/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{4,}/');
+  });
+});
+
+describe('merge open ungreedy quantifier with open ungreedy quantifier', () => {
+
+  it('a+?a+?', () => {
+    const re = transform(/a+?a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}?/');
+  });
+
+  it('a+?a*?', () => {
+    const re = transform(/a+?a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{1,}?/');
+
+    const re2 = transform(/a*?a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{1,}?/');
+  });
+
+  it('a+?a{2,}?', () => {
+    const re = transform(/a+?a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{3,}?/');
+
+    const re2 = transform(/a{2,}?a+?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{3,}?/');
+  });
+
+  it('a*?a*?', () => {
+    const re = transform(/a*?a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{0,}?/');
+  });
+
+  it('a*?a{2,}?', () => {
+    const re = transform(/a*?a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{2,}?/');
+
+    const re2 = transform(/a{2,}?a*?/, [
+      quantifiersMerge
+    ]);
+    expect(re2.toString()).toBe('/a{2,}?/');
+  });
+
+  it('a{2,}?a{2,}?', () => {
+    const re = transform(/a{2,}?a{2,}?/, [
+      quantifiersMerge
+    ]);
+    expect(re.toString()).toBe('/a{4,}?/');
+  });
+
+});
\ No newline at end of file