Repository: DmitrySoshnikov/regexp-tree (js)

Issue:
Optimizer: Ungroup transform does not merge adjacent Alternatives
At the moment, when the Ungroup transform removes groups, it does not merge adjacent Alternatives, leading to an AST that should not naturally happen on parsing.

For example: `(?:abcd)(?:abcd)` is an Alternative containing two Groups.
When the Ungroup transform runs, it transforms it to an Alternative of two Alternatives. This gives the correct result when generated as a string or a regexp, but the AST should not contain this.

This issue leads to following transforms misinterpreting the AST:
`(?:abcd)(?:abcd)` -> `abcdabcd` -> `abcd{2}` instead of `(?:abcd){2}`.

Pull request:
Optimizer: Ungroup: Merge Group content of type Alternative with parent Alternative
Fixes #152.

Patch:
diff --git a/src/optimizer/transforms/ungroup-transform.js b/src/optimizer/transforms/ungroup-transform.js
index 11f8255..4971582 100644
--- a/src/optimizer/transforms/ungroup-transform.js
+++ b/src/optimizer/transforms/ungroup-transform.js
@@ -20,6 +20,8 @@ module.exports = {
       return;
     }
 
+    // Don't optimize /a(?:b|c)/ to /ab|c/
+    // but /(?:b|c)/ to /b|c/ is ok
     if (
       childPath.node.type === 'Disjunction' &&
       parent.type !== 'RegExp'
@@ -27,6 +29,9 @@ module.exports = {
       return;
     }
 
+    // Don't optimize /(?:ab)+/ to /ab+/
+    // but /(?:a)+/ to /a+/ is ok
+    // and /(?:[a-d])+/ to /[a-d]+/ is ok too
     if (
       parent.type === 'Repetition' &&
       childPath.node.type !== 'Char' &&
@@ -35,6 +40,24 @@ module.exports = {
       return;
     }
 
-    path.replace(childPath.node);
+    if (childPath.node.type === 'Alternative') {
+      const parentPath = path.getParent();
+      if (parentPath.node.type === 'Alternative') {
+
+        // /abc(?:def)ghi/ When (?:def) is ungrouped its content must be merged with parent alternative
+
+        parentPath.replace({
+          type: 'Alternative',
+          expressions: [
+            ...parent.expressions.slice(0, path.index),
+            ...childPath.node.expressions,
+            ...parent.expressions.slice(path.index + 1)
+          ]
+        });
+      }
+
+    } else {
+      path.replace(childPath.node);
+    }
   }
 };
\ No newline at end of file


Test patch:
diff --git a/src/optimizer/transforms/__tests__/ungroup-transform-test.js b/src/optimizer/transforms/__tests__/ungroup-transform-test.js
index 3d02d77..fc630fc 100644
--- a/src/optimizer/transforms/__tests__/ungroup-transform-test.js
+++ b/src/optimizer/transforms/__tests__/ungroup-transform-test.js
@@ -50,6 +50,20 @@ describe('ungroup', () => {
     expect(re.toString()).toBe('/[ab]+/');
   });
 
+  it('merges Group content of type Alternative with parent Alternative', () => {
+    const re = transform(/a(?:bc)d/, [
+      ungroup,
+    ]);
+    expect(re.toString()).toBe('/abcd/');
+    const ast = re.getAST();
+    expect(
+      ast.body.type === 'Alternative' &&
+      ast.body.expressions.every(function (expression) {
+        return expression.type === 'Char';
+      })
+    ).toBe(true);
+  });
+
   it('does not ungroup groups with quantifier otherwise', () => {
     const re = transform(/(?:ab)+/, [
       ungroup,