Repository: DmitrySoshnikov/regexp-tree
Pull request #119 (2017-11-21 07:59:20)

Optimizer: Fix (?:abc)+abc optimization in combine-repeating-patterns
I forgot a case in the `increaseQuantifierByOne` function in the `combine-repeating-patterns` transform leading to incorrect optimization of `/(?:abc)+abc/` into `/(?:abc)+/` instead of `/(?:abc){2,}/`.

This PR fixes the case and moves the function to the `utils.js` file since the same behaviour is used in the `quantifiers-merge` transform.


Patch:
diff --git a/src/optimizer/transforms/combine-repeating-patterns-transform.js b/src/optimizer/transforms/combine-repeating-patterns-transform.js
index 6d56a4c..3dd23ec 100644
--- a/src/optimizer/transforms/combine-repeating-patterns-transform.js
+++ b/src/optimizer/transforms/combine-repeating-patterns-transform.js
@@ -7,6 +7,8 @@
 
 const NodePath = require('../../traverse/node-path');
 
+const {increaseQuantifierByOne} = require('../../transform/utils');
+
 /**
  * A regexp-tree plugin to combine repeating patterns.
  *
@@ -182,25 +184,4 @@ function combineRepetitionWithPrevious(alternative, child, index) {
     }
   }
   return index;
-}
-
-function increaseQuantifierByOne(quantifier) {
-  if (quantifier.kind === '*') {
-
-    quantifier.kind = '+';
-
-  } else if (quantifier.kind === '?') {
-
-    quantifier.kind = 'Range';
-    quantifier.from = 1;
-    quantifier.to = 2;
-
-  } else if (quantifier.kind === 'Range') {
-
-    quantifier.from += 1;
-    if (quantifier.to) {
-      quantifier.to += 1;
-    }
-
-  }
 }
\ No newline at end of file
diff --git a/src/optimizer/transforms/quantifiers-merge-transform.js b/src/optimizer/transforms/quantifiers-merge-transform.js
index 3c1eb19..9832870 100644
--- a/src/optimizer/transforms/quantifiers-merge-transform.js
+++ b/src/optimizer/transforms/quantifiers-merge-transform.js
@@ -5,6 +5,8 @@
 
 'use strict';
 
+const {increaseQuantifierByOne} = require('../../transform/utils');
+
 /**
  * A regexp-tree plugin to merge quantifiers
  *
@@ -88,46 +90,8 @@ module.exports = {
         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();
-
-      }
+      increaseQuantifierByOne(node.quantifier);
+      previousSibling.remove();
     }
   }
 };
diff --git a/src/transform/utils.js b/src/transform/utils.js
index 20b2d22..68e6d43 100644
--- a/src/transform/utils.js
+++ b/src/transform/utils.js
@@ -45,7 +45,45 @@ function listToDisjunction(list) {
   });
 }
 
+/**
+ * Increases a quantifier by one.
+ * Does not change greediness.
+ * * -> +
+ * + -> {2,}
+ * ? -> {1,2}
+ * {2} -> {3}
+ * {2,} -> {3,}
+ * {2,3} -> {3,4}
+ */
+function increaseQuantifierByOne(quantifier) {
+  if (quantifier.kind === '*') {
+
+    quantifier.kind = '+';
+
+  } else if (quantifier.kind === '+') {
+
+    quantifier.kind = 'Range';
+    quantifier.from = 2;
+    delete quantifier.to;
+
+  } else if (quantifier.kind === '?') {
+
+    quantifier.kind = 'Range';
+    quantifier.from = 1;
+    quantifier.to = 2;
+
+  } else if (quantifier.kind === 'Range') {
+
+    quantifier.from += 1;
+    if (quantifier.to) {
+      quantifier.to += 1;
+    }
+
+  }
+}
+
 module.exports = {
   disjunctionToList,
   listToDisjunction,
+  increaseQuantifierByOne,
 };
\ No newline at end of file


Test patch:
diff --git a/src/optimizer/transforms/__tests__/combine-repeating-patterns-transform-test.js b/src/optimizer/transforms/__tests__/combine-repeating-patterns-transform-test.js
index a556bc0..98f1ad2 100644
--- a/src/optimizer/transforms/__tests__/combine-repeating-patterns-transform-test.js
+++ b/src/optimizer/transforms/__tests__/combine-repeating-patterns-transform-test.js
@@ -36,10 +36,15 @@ describe('abcdefabcdef -> (?:abcdef){2}', () => {
 describe('(?:abc){4}abc -> (?:abc){5}', () => {
 
   it('combines pattern with repetition on the left', () => {
-    const re = transform(/(?:abc){4}abc/, [
+    let re = transform(/(?:abc){4}abc/, [
       combineRepeatingPatterns
     ]);
     expect(re.toString()).toBe('/(?:abc){5}/');
+
+    re = transform(/(?:abc)+abc/, [
+      combineRepeatingPatterns
+    ]);
+    expect(re.toString()).toBe('/(?:abc){2,}/');
   });
 
 });
diff --git a/src/transform/__tests__/transform-utils-test.js b/src/transform/__tests__/transform-utils-test.js
index b3f75fc..cfc9bf0 100644
--- a/src/transform/__tests__/transform-utils-test.js
+++ b/src/transform/__tests__/transform-utils-test.js
@@ -43,4 +43,75 @@ describe('transform-utils', () => {
     expect(disjunction).toEqual(expected);
   });
 
+  it('increaseQuantifierByOne', () => {
+    const quantifiers = [{
+        type: 'Quantifier',
+        kind: '*',
+        greedy: true
+    }, {
+      type: 'Quantifier',
+      kind: '+',
+      greedy: false
+    }, {
+      type: 'Quantifier',
+      kind: '?',
+      greedy: true
+    }, {
+      type: 'Quantifier',
+      kind: 'Range',
+      from: 2,
+      to: 2,
+      greedy: true
+    }, {
+      type: 'Quantifier',
+      kind: 'Range',
+      from: 2,
+      greedy: false
+    }, {
+      type: 'Quantifier',
+      kind: 'Range',
+      from: 2,
+      to: 3,
+      greedy: true
+    }];
+    const quantifiersIncreased = [{
+      type: 'Quantifier',
+      kind: '+',
+      greedy: true
+    }, {
+      type: 'Quantifier',
+      kind: 'Range',
+      from: 2,
+      greedy: false
+    }, {
+      type: 'Quantifier',
+      kind: 'Range',
+      from: 1,
+      to: 2,
+      greedy: true
+    }, {
+      type: 'Quantifier',
+      kind: 'Range',
+      from: 3,
+      to: 3,
+      greedy: true
+    }, {
+      type: 'Quantifier',
+      kind: 'Range',
+      from: 3,
+      greedy: false
+    }, {
+      type: 'Quantifier',
+      kind: 'Range',
+      from: 3,
+      to: 4,
+      greedy: true
+    }];
+
+    quantifiers.forEach((quantifier, i) => {
+      transformUtils.increaseQuantifierByOne(quantifier);
+      expect(quantifier).toEqual(quantifiersIncreased[i])
+    });
+  });
+
 });
\ No newline at end of file