Repository: DmitrySoshnikov/regexp-tree (js)

Issue:
Optimizer: implement "remove duplicates" transform for disjunction
It would be nice if the optimizer removed duplicates in disjunctions:

`/ab|ab/ -> /ab/`

Pull request description:
Remove duplicates in disjunctions Fix #94
Hi! This is an attempt to fix #94.

The issue I'm facing is that it only replaces one duplicate at a time.
Thus calling `regexp-tree -e "/(ab|ab|ab|ab)/" -o` returns `/(ab|ab|ab)/`, which is kind of annoying.

Any idea to make it more useful?

Patch:
diff --git a/src/optimizer/transforms/disjunction-remove-duplicates-transform.js b/src/optimizer/transforms/disjunction-remove-duplicates-transform.js
new file mode 100644
index 0000000..759dc35
--- /dev/null
+++ b/src/optimizer/transforms/disjunction-remove-duplicates-transform.js
@@ -0,0 +1,43 @@
+/**
+ * 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 28e997c..0a90b02 100644
--- a/src/optimizer/transforms/index.js
+++ b/src/optimizer/transforms/index.js
@@ -24,6 +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')
 ];
\ No newline at end of file


Test patch:
diff --git a/src/optimizer/transforms/__tests__/disjunction-remove-duplicates-transform-test.js b/src/optimizer/transforms/__tests__/disjunction-remove-duplicates-transform-test.js
new file mode 100644
index 0000000..538bd33
--- /dev/null
+++ b/src/optimizer/transforms/__tests__/disjunction-remove-duplicates-transform-test.js
@@ -0,0 +1,53 @@
+/**
+ * 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