Repository: DmitrySoshnikov/regexp-tree
Pull request #107 (2017-11-17 21:29:47)

Combine repeating patterns transform
This transform combines repeating patterns in alternatives. It is divided in three parts:

Look for two repeating patterns and combine them in a Repetition:
`/abcabc/` -> `/(?:abc){2}/`

Look for a pattern existing in a Repetition on the left:
`/(?:abc){2}abc/` -> `/(?:abc){3}/`

Look for a pattern on the left that matches a Repetition:
`/abc(?:abc){2}/` -> `/(?:abc){3}/`

**Note that this PR depends on (and includes) PR #106.**


Patch:
diff --git a/src/optimizer/transforms/combine-repeating-patterns-transform.js b/src/optimizer/transforms/combine-repeating-patterns-transform.js
new file mode 100644
index 0000000..6d56a4c
--- /dev/null
+++ b/src/optimizer/transforms/combine-repeating-patterns-transform.js
@@ -0,0 +1,206 @@
+/**
+ * The MIT License (MIT)
+ * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ */
+
+'use strict';
+
+const NodePath = require('../../traverse/node-path');
+
+/**
+ * A regexp-tree plugin to combine repeating patterns.
+ *
+ * /^abcabcabc/ -> /^abc{3}/
+ * /^(?:abc){2}abc/ -> /^(?:abc){3}/
+ * /^abc(?:abc){2}/ -> /^(?:abc){3}/
+ */
+
+module.exports = {
+  Alternative(path) {
+    const {node} = path;
+
+    // We can skip the first child
+    let index = 1;
+    while (index < node.expressions.length) {
+      let child = path.getChild(index);
+      index = Math.max(1, combineRepeatingPatternLeft(path, child, index));
+
+      if (index >= node.expressions.length) {
+        break;
+      }
+
+      child = path.getChild(index);
+      index = Math.max(1, combineWithPreviousRepetition(path, child, index));
+
+      if (index >= node.expressions.length) {
+        break;
+      }
+
+      child = path.getChild(index);
+      index = Math.max(1, combineRepetitionWithPrevious(path, child, index));
+
+      index++;
+    }
+  }
+};
+
+// abcabc -> (?:abc){2}
+function combineRepeatingPatternLeft(alternative, child, index) {
+  const {node} = alternative;
+
+  const nbPossibleLengths = Math.ceil(index / 2);
+  let i = 0;
+
+  while (i < nbPossibleLengths) {
+    const startIndex = index - 2 * i - 1;
+    let right, left;
+
+    if (i === 0) {
+      right = child;
+      left = alternative.getChild(startIndex);
+    } else {
+      right = NodePath.getForNode({
+        type: 'Alternative',
+        expressions: [...node.expressions.slice(index - i, index), child.node]
+      });
+
+      left = NodePath.getForNode({
+        type: 'Alternative',
+        expressions: [...node.expressions.slice(startIndex, index - i)]
+      });
+    }
+
+    if (right.hasEqualSource(left)) {
+      for (let j = 0; j < 2 * i + 1; j++) {
+        alternative.getChild(startIndex).remove();
+      }
+
+      child.replace({
+        type: 'Repetition',
+        expression: i === 0 ? right.node : {
+          type: 'Group',
+          capturing: false,
+          expression: right.node
+        },
+        quantifier: {
+          type: 'Quantifier',
+          kind: 'Range',
+          from: 2,
+          to: 2,
+          greedy: true
+        }
+      });
+      return startIndex;
+    }
+
+    i++;
+  }
+
+  return index;
+}
+
+// (?:abc){2}abc -> (?:abc){3}
+function combineWithPreviousRepetition(alternative, child, index) {
+  const {node} = alternative;
+
+  let i = 0;
+  while (i < index) {
+    let previousChild = alternative.getChild(i);
+
+    if (previousChild.node.type === 'Repetition' && previousChild.node.quantifier.greedy) {
+      let left = previousChild.getChild();
+      let right;
+
+      if (left.node.type === 'Group' && !left.node.capturing) {
+        left = left.getChild();
+      }
+
+      if (i + 1 === index) {
+        right = child;
+        if (right.node.type === 'Group' && !right.node.capturing) {
+          right = right.getChild();
+        }
+      } else {
+        right = NodePath.getForNode({
+          type: 'Alternative',
+          expressions: [...node.expressions.slice(i + 1, index + 1)]
+        });
+      }
+
+      if (left.hasEqualSource(right)) {
+
+        for (let j = i; j < index; j++) {
+          alternative.getChild(i + 1).remove();
+        }
+
+        increaseQuantifierByOne(previousChild.node.quantifier);
+
+        return i;
+      }
+    }
+
+    i++;
+  }
+  return index;
+}
+
+// abc(?:abc){2} -> (?:abc){3}
+function combineRepetitionWithPrevious(alternative, child, index) {
+  const {node} = alternative;
+
+  if (child.node.type === 'Repetition' && child.node.quantifier.greedy) {
+    let right = child.getChild();
+    let left;
+
+    if (right.node.type === 'Group' && !right.node.capturing) {
+      right = right.getChild();
+    }
+
+    let rightLength;
+    if (right.node.type === 'Alternative') {
+      rightLength = right.node.expressions.length;
+      left = NodePath.getForNode({
+        type: 'Alternative',
+        expressions: [...node.expressions.slice(index - rightLength, index)]
+      });
+    } else {
+      rightLength = 1;
+      left = alternative.getChild(index - 1);
+      if (left.node.type === 'Group' && !left.node.capturing) {
+        left = left.getChild();
+      }
+    }
+
+    if (left.hasEqualSource(right)) {
+      for (let j = index - rightLength; j < index; j++) {
+        alternative.getChild(index - rightLength).remove();
+      }
+
+      increaseQuantifierByOne(child.node.quantifier);
+
+      return index - rightLength;
+    }
+  }
+  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/index.js b/src/optimizer/transforms/index.js
index e04f411..3b37113 100644
--- a/src/optimizer/transforms/index.js
+++ b/src/optimizer/transforms/index.js
@@ -34,5 +34,8 @@ module.exports = [
   require('./remove-empty-group-transform'),
 
   // (?:a) -> a
-  require('./ungroup-transform')
+  require('./ungroup-transform'),
+
+  // abcabcabc -> (?:abc){3}
+  require('./combine-repeating-patterns-transform')
 ];
\ No newline at end of file
diff --git a/src/traverse/node-path.js b/src/traverse/node-path.js
index debeaa5..7785ca6 100644
--- a/src/traverse/node-path.js
+++ b/src/traverse/node-path.js
@@ -122,6 +122,7 @@ class NodePath {
     if (this.isRemoved()) {
       return;
     }
+    NodePath.registry.delete(this.node);
 
     this.node = null;
 


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
new file mode 100644
index 0000000..a556bc0
--- /dev/null
+++ b/src/optimizer/transforms/__tests__/combine-repeating-patterns-transform-test.js
@@ -0,0 +1,67 @@
+/**
+ * The MIT License (MIT)
+ * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ */
+
+'use strict';
+
+const {transform} = require('../../../transform');
+const combineRepeatingPatterns = require('../combine-repeating-patterns-transform');
+
+describe('abcdefabcdef -> (?:abcdef){2}', () => {
+
+  it('combines repeating patterns', () => {
+    const re = transform(/abcdefabcdef/, [
+      combineRepeatingPatterns
+    ]);
+    expect(re.toString()).toBe('/(?:abcdef){2}/');
+  });
+
+  it('combines complex repeating patterns', () => {
+    const re = transform(/a{5,}[\d\W]{3}a{5,}[\d\W]{3}/, [
+      combineRepeatingPatterns
+    ]);
+    expect(re.toString()).toBe('/(?:a{5,}[\\d\\W]{3}){2}/');
+  });
+
+  it('combines multiple repeating patterns', () => {
+    const re = transform(/(?:a|bc)(?:a|bc)(?:a|bc)defdefdef/, [
+      combineRepeatingPatterns
+    ]);
+    expect(re.toString()).toBe('/(?:a|bc){3}(?:def){3}/');
+  });
+
+});
+
+describe('(?:abc){4}abc -> (?:abc){5}', () => {
+
+  it('combines pattern with repetition on the left', () => {
+    const re = transform(/(?:abc){4}abc/, [
+      combineRepeatingPatterns
+    ]);
+    expect(re.toString()).toBe('/(?:abc){5}/');
+  });
+
+});
+
+describe('abc(?:abc){4} -> (?:abc){5}', () => {
+
+  it('combines repetition with pattern on the left', () => {
+    const re = transform(/abc(?:abc){4}/, [
+      combineRepeatingPatterns
+    ]);
+    expect(re.toString()).toBe('/(?:abc){5}/');
+  });
+
+});
+
+describe('abc(?:abc){4}abcabc -> (?:abc){7}', () => {
+
+  it('combine all those repeating patterns at once', () => {
+    const re = transform(/abc(?:abc){4}abcabc/, [
+      combineRepeatingPatterns
+    ]);
+    expect(re.toString()).toBe('/(?:abc){7}/');
+  });
+
+});
\ No newline at end of file