Repository: DmitrySoshnikov/regexp-tree
Pull request #102 (2017-11-12 14:27:31)

Optimizer: remove unnecessary groups
This transform removes unnecessary groups:

`/a(?:bc)d/` -> `/abcd/`
`/(?:ab|bc)/` -> `/ab|bc/`
`/(?:a)+/` -> `/a+/`

It does not remove capturing groups, nor disjunctions other than top-level ones, nor complex groups with quantifier:
`/a(bc)d/`, `/a(?:ab|bc)d/`, `/(?:ab)+/` are left unchanged.


Patch:
diff --git a/src/optimizer/index.js b/src/optimizer/index.js
index 249e80f..8052655 100644
--- a/src/optimizer/index.js
+++ b/src/optimizer/index.js
@@ -26,19 +26,11 @@ module.exports = {
    *   /\w+e+/
    */
   optimize(regexp) {
-    let prevResult;
     let result;
-    do {
-      if (result) {
-        prevResult = result.toRegExp().toString();
-        regexp = result.toRegExp();
-      }
-      optimizationTransforms.forEach(transformer => {
-        result = transform.transform(regexp, transformer);
-        regexp = result.getAST();
-      });
-    } while (result.toRegExp().toString() !== prevResult);
-
+    optimizationTransforms.forEach(transformer => {
+      result = transform.transform(regexp, transformer);
+      regexp = result.getAST();
+    });
     return result;
   },
 };
\ No newline at end of file
diff --git a/src/optimizer/transforms/char-escape-unescape-transform.js b/src/optimizer/transforms/char-escape-unescape-transform.js
index 5e28ba0..00586ae 100644
--- a/src/optimizer/transforms/char-escape-unescape-transform.js
+++ b/src/optimizer/transforms/char-escape-unescape-transform.js
@@ -38,14 +38,13 @@ function shouldUnescape(path) {
 }
 
 /**
- * \], \\, \^, \-
+ * \], \\, \-
  *
  * Note: \- always preserved to avoid `[a\-z]` turning into `[a-z]`.
- * Note: \^ always preserved to avoid `[\^a]` turning into `[^a]`.
  * TODO: more sophisticated analisys.
  */
 function preservesInCharClass(value) {
-  return /[\]\\^-]/.test(value);
+  return /[\]\\\\-]/.test(value);
 }
 
 // Note: \{ and \} are always preserved to avoid `a\{2\}` turning
diff --git a/src/optimizer/transforms/disjunction-remove-duplicates-transform.js b/src/optimizer/transforms/disjunction-remove-duplicates-transform.js
deleted file mode 100644
index 759dc35..0000000
--- a/src/optimizer/transforms/disjunction-remove-duplicates-transform.js
+++ /dev/null
@@ -1,43 +0,0 @@
-/**
- * The MIT License (MIT)
- * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
- */
-
-'use strict';
-
-const NodePath = require('../../traverse/node-path');
-
-const {
-  disjunctionToList,
-  listToDisjunction,
-} = require('../../transform/utils');
-
-/**
- * Removes duplicates from a disjunction sequence:
- *
- * /(ab|bc|ab)+(xy|xy)+/ -> /(ab|bc)+(xy)+/
- */
-module.exports = {
-  Disjunction(path) {
-    const {node} = path;
-
-    // Make unique nodes.
-    const uniqueNodesMap = {};
-
-    const parts = disjunctionToList(node).filter(part => {
-      const encoded = NodePath.getForNode(part).jsonEncode();
-
-      // Already recorded this part, filter out.
-      if (uniqueNodesMap.hasOwnProperty(encoded)) {
-        return false;
-      }
-
-      uniqueNodesMap[encoded] = part;
-      return true;
-    });
-
-    // Replace with the optimized disjunction.
-    path.replace(listToDisjunction(parts));
-
-  }
-};
\ No newline at end of file
diff --git a/src/optimizer/transforms/index.js b/src/optimizer/transforms/index.js
index 0a90b02..e4ebd36 100644
--- a/src/optimizer/transforms/index.js
+++ b/src/optimizer/transforms/index.js
@@ -24,9 +24,9 @@ module.exports = [
   // \e -> e
   require('./char-escape-unescape-transform'),
 
-  // (ab|ab) -> (ab)
-  require('./disjunction-remove-duplicates-transform'),
-
   // (a|b|c) -> [abc]
-  require('./group-single-chars-to-char-class')
+  require('./group-single-chars-to-char-class'),
+
+  // (?:a) -> a
+  require('./ungroup-transform')
 ];
\ No newline at end of file
diff --git a/src/optimizer/transforms/quantifier-range-to-symbol-transform.js b/src/optimizer/transforms/quantifier-range-to-symbol-transform.js
index 42503f5..1da04fc 100644
--- a/src/optimizer/transforms/quantifier-range-to-symbol-transform.js
+++ b/src/optimizer/transforms/quantifier-range-to-symbol-transform.js
@@ -9,7 +9,6 @@
  * A regexp-tree plugin to replace different range-based quantifiers
  * with their symbol equivalents.
  *
- * a{0,} -> a*
  * a{1,} -> a+
  * a{1} -> a
  *
@@ -25,9 +24,6 @@ module.exports = {
       return;
     }
 
-    // a{0,} -> a*
-    rewriteOpenZero(path);
-
     // a{1,} -> a+
     rewriteOpenOne(path);
 
@@ -36,17 +32,6 @@ module.exports = {
   }
 };
 
-function rewriteOpenZero(path) {
-  const {node} = path;
-
-  if (node.from !== 0 || node.to) {
-    return;
-  }
-
-  node.kind = '*';
-  delete node.from;
-}
-
 function rewriteOpenOne(path) {
   const {node} = path;
 
diff --git a/src/optimizer/transforms/ungroup-transform.js b/src/optimizer/transforms/ungroup-transform.js
new file mode 100644
index 0000000..490c423
--- /dev/null
+++ b/src/optimizer/transforms/ungroup-transform.js
@@ -0,0 +1,41 @@
+/**
+ * The MIT License (MIT)
+ * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ */
+
+'use strict';
+
+/**
+ * A regexp-tree plugin to remove unnecessary groups.
+ *
+ * /(?:a)/ -> /a/
+ */
+
+module.exports = {
+  Group(path) {
+    const {node, parent} = path;
+    const childPath = path.getChild();
+
+    if (node.capturing) {
+      return;
+    }
+
+    if (
+      childPath &&
+      childPath.node.type === 'Disjunction' &&
+      parent.type !== 'RegExp'
+    ) {
+      return;
+    }
+
+    if (
+      parent.type === 'Repetition' &&
+      childPath.node.type !== 'Char' &&
+      childPath.node.type !== 'CharacterClass'
+    ) {
+      return;
+    }
+
+    path.replace(childPath.node);
+  }
+};
\ No newline at end of file


Test patch:
diff --git a/src/optimizer/__tests__/optimizer-integration-test.js b/src/optimizer/__tests__/optimizer-integration-test.js
index 3a97e29..57fc2cf 100644
--- a/src/optimizer/__tests__/optimizer-integration-test.js
+++ b/src/optimizer/__tests__/optimizer-integration-test.js
@@ -27,7 +27,7 @@ describe('optimizer-integration-test', () => {
 
   it('preserve escape', () => {
     const original = /^[\^\*\$\(\)]\^\*\$\(\)\.\[\]\/\\$/;
-    const optimized = /^[\^*$()]\^\*\$\(\)\.\[\]\/\\$/;
+    const optimized = /^[^*$()]\^\*\$\(\)\.\[\]\/\\$/;
 
     expect(optimizer.optimize(original).toString())
       .toBe(optimized.toString());
@@ -73,12 +73,4 @@ describe('optimizer-integration-test', () => {
       .toBe(optimized.toString());
   });
 
-  it('finds the best optimization', () => {
-    const original = /a|a/;
-    const optimized = /a/;
-
-    expect(optimizer.optimize(original).toString())
-      .toBe(optimized.toString());
-  });
-
 });
\ No newline at end of file
diff --git a/src/optimizer/transforms/__tests__/char-escape-unescape-transform-test.js b/src/optimizer/transforms/__tests__/char-escape-unescape-transform-test.js
index 21c632f..90bc69d 100644
--- a/src/optimizer/transforms/__tests__/char-escape-unescape-transform-test.js
+++ b/src/optimizer/transforms/__tests__/char-escape-unescape-transform-test.js
@@ -28,7 +28,7 @@ describe('\e -> e', () => {
     const re = transform(/[\e\*\(\]\ \^\$\-]\(\n/, [
       charUnescape,
     ]);
-    expect(re.toString()).toBe(/[e*(\] \^$\-]\(\n/.toString());
+    expect(re.toString()).toBe(/[e*(\] ^$\-]\(\n/.toString());
   });
 
 });
\ No newline at end of file
diff --git a/src/optimizer/transforms/__tests__/disjunction-remove-duplicates-transform-test.js b/src/optimizer/transforms/__tests__/disjunction-remove-duplicates-transform-test.js
deleted file mode 100644
index 538bd33..0000000
--- a/src/optimizer/transforms/__tests__/disjunction-remove-duplicates-transform-test.js
+++ /dev/null
@@ -1,53 +0,0 @@
-/**
- * The MIT License (MIT)
- * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
- */
-
-'use strict';
-
-const {transform} = require('../../../transform');
-const disjunctionRemoveDuplicates = require('../disjunction-remove-duplicates-transform');
-
-describe('(ab|bc|ab) -> (ab|bc)', () => {
-
-  it('removes duplicates from disjunction', () => {
-    const re = transform(/ab|bc|ab/, [
-      disjunctionRemoveDuplicates
-    ]);
-    expect(re.toString()).toBe('/ab|bc/');
-  });
-
-  it('preserves order', () => {
-    const re = transform(/bc|bc|ab/, [
-      disjunctionRemoveDuplicates
-    ]);
-    expect(re.toString()).toBe('/bc|ab/');
-  });
-
-  it('replaces disjunction containing only one part', () => {
-    const re = transform(/ab|ab/, [
-      disjunctionRemoveDuplicates
-    ]);
-    expect(re.toString()).toBe('/ab/');
-  });
-
-  it('does not merge capturing groups', () => {
-    const re = transform(/(ab)|(ab)/, [
-      disjunctionRemoveDuplicates
-    ]);
-    expect(re.toString()).toBe('/(ab)|(ab)/');
-  });
-
-  it('handles recursion', () => {
-    const re = transform(/(ab|bc|ab)|(bc|cd|bc)/, [
-      disjunctionRemoveDuplicates
-    ]);
-    expect(re.toString()).toBe('/(ab|bc)|(bc|cd)/');
-
-    const re2 = transform(/(?:ab|bc|ab)|(?:ab|bc|ab)/, [
-      disjunctionRemoveDuplicates
-    ]);
-    expect(re2.toString()).toBe('/(?:ab|bc)/');
-  });
-
-});
\ No newline at end of file
diff --git a/src/optimizer/transforms/__tests__/quantifier-range-to-symbol-transform-test.js b/src/optimizer/transforms/__tests__/quantifier-range-to-symbol-transform-test.js
index 5cc0428..61a9314 100644
--- a/src/optimizer/transforms/__tests__/quantifier-range-to-symbol-transform-test.js
+++ b/src/optimizer/transforms/__tests__/quantifier-range-to-symbol-transform-test.js
@@ -10,13 +10,6 @@ const quantifierRangeToSymbol = require('../quantifier-range-to-symbol-transform
 
 describe('quantifier range to symbol', () => {
 
-  it('a{0,} -> a*', () => {
-    const re = transform(/[a-z]{0,}/, [
-      quantifierRangeToSymbol,
-    ]);
-    expect(re.toString()).toBe('/[a-z]*/');
-  });
-
   it('a{1,} -> a+', () => {
     const re = transform(/[a-z]{1,}/, [
       quantifierRangeToSymbol,
diff --git a/src/optimizer/transforms/__tests__/ungroup-transform-test.js b/src/optimizer/transforms/__tests__/ungroup-transform-test.js
new file mode 100644
index 0000000..fe61afe
--- /dev/null
+++ b/src/optimizer/transforms/__tests__/ungroup-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 ungroup = require('../ungroup-transform');
+
+describe('ungroup', () => {
+
+  it('ungroups simple groups', () => {
+    const re = transform(/(?:a)/, [
+      ungroup,
+    ]);
+    expect(re.toString()).toBe('/a/');
+
+    const re2 = transform(/a(?:[\da]b)c/, [
+      ungroup,
+    ]);
+    expect(re2.toString()).toBe('/a[\\da]bc/');
+  });
+
+  it('ungroups disjunctions if top-level', () => {
+    const re = transform(/(?:ab|bc)/, [
+      ungroup,
+    ]);
+    expect(re.toString()).toBe('/ab|bc/');
+  });
+
+  it('does not ungroup other disjunctions', () => {
+    const re = transform(/^(?:ab|bc)/, [
+      ungroup,
+    ]);
+    expect(re.toString()).toBe('/^(?:ab|bc)/');
+  });
+
+  it('ungroups groups with quantifier if child is a Char', () => {
+    const re = transform(/(?:a)+/, [
+      ungroup,
+    ]);
+    expect(re.toString()).toBe('/a+/');
+  });
+
+  it('ungroups groups with quantifier if child is a CharacterClass', () => {
+    const re = transform(/(?:[ab])+/, [
+      ungroup,
+    ]);
+    expect(re.toString()).toBe('/[ab]+/');
+  });
+
+  it('does not ungroup groups with quantifier otherwise', () => {
+    const re = transform(/(?:ab)+/, [
+      ungroup,
+    ]);
+    expect(re.toString()).toBe('/(?:ab)+/');
+  });
+
+  it('does not ungroup capturing groups', () => {
+    const re = transform(/(a)/, [
+      ungroup,
+    ]);
+    expect(re.toString()).toBe('/(a)/');
+  });
+
+});
\ No newline at end of file