Repository: DmitrySoshnikov/regexp-tree
Pull request #151 (2018-03-01 07:24:45)

Optimizer: Don't apply transform if result is longer
Related to #135 and more specifically https://github.com/DmitrySoshnikov/regexp-tree/issues/135#issuecomment-366053266, this PR prevents a transform from being applied if the result is longer that the original.




Patch:
diff --git a/src/optimizer/index.js b/src/optimizer/index.js
index c85c902..5e413c2 100644
--- a/src/optimizer/index.js
+++ b/src/optimizer/index.js
@@ -5,6 +5,8 @@
 
 'use strict';
 
+const clone = require('../utils/clone');
+const parser = require('../parser');
 const transform = require('../transform');
 const optimizationTransforms = require('./transforms');
 
@@ -30,13 +32,25 @@ module.exports = {
       ? transformsWhitelist
       : Object.keys(optimizationTransforms);
 
-    let prevResult;
-    let result;
+    let ast = regexp;
+    if (regexp instanceof RegExp) {
+      regexp = `${regexp}`;
+    }
+
+    if (typeof regexp === 'string') {
+      ast = parser.parse(regexp);
+    }
+
+    let result = new transform.TransformResult(ast);
+    let prevResultString;
+
     do {
-      if (result) {
-        prevResult = result.toString();
-        regexp = prevResult;
-      }
+      // Get a copy of the current state here so
+      // we can compare it with the state at the
+      // end of the loop.
+      prevResultString = result.toString();
+      ast = clone(result.getAST());
+
       transformToApply.forEach(transformName => {
 
         if (!optimizationTransforms.hasOwnProperty(transformName)) {
@@ -49,10 +63,24 @@ module.exports = {
 
         const transformer = optimizationTransforms[transformName];
 
-        result = transform.transform(regexp, transformer);
-        regexp = result.getAST();
+        // Don't override result just yet since we
+        // might want to rollback the transform
+        let newResult = transform.transform(ast, transformer);
+
+        if (newResult.toString() !== result.toString()) {
+          if (newResult.toString().length <= result.toString().length) {
+            result = newResult;
+          } else {
+            // Result has changed but is not shorter:
+            // restore ast to its previous state.
+            ast = clone(result.getAST());
+          }
+        }
       });
-    } while (result.toString() !== prevResult);
+
+      // Keep running the optimizer until it stops
+      // making any change to the regexp.
+    } while (result.toString() !== prevResultString);
 
     return result;
   },
diff --git a/src/utils/clone.js b/src/utils/clone.js
new file mode 100644
index 0000000..79bb4e8
--- /dev/null
+++ b/src/utils/clone.js
@@ -0,0 +1,28 @@
+/**
+ * The MIT License (MIT)
+ * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ */
+
+'use strict';
+
+/**
+ * Performs a deep copy of an simple object.
+ * Only handles scalar values, arrays and objects.
+ *
+ * @param obj Object
+ */
+module.exports = function clone (obj) {
+  if (obj === null || typeof obj !== 'object') {
+    return obj;
+  }
+  let res;
+  if (Array.isArray(obj)) {
+    res = [];
+  } else {
+    res = {};
+  }
+  for (let i in obj) {
+    res[i] = clone(obj[i]);
+  }
+  return res;
+};
\ No newline at end of file


Test patch:
diff --git a/src/utils/__tests__/utils-clone-test.js b/src/utils/__tests__/utils-clone-test.js
new file mode 100644
index 0000000..31b70d8
--- /dev/null
+++ b/src/utils/__tests__/utils-clone-test.js
@@ -0,0 +1,51 @@
+/**
+ * The MIT License (MIT)
+ * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ */
+
+const clone = require('../clone');
+
+describe('utils-clone', () => {
+
+  it('clones null', () => {
+    expect(clone(null)).toBe(null);
+  });
+
+  it('clones scalars', () => {
+    expect(clone(true)).toBe(true);
+    expect(clone(42.25)).toBe(42.25);
+    expect(clone('foobar')).toBe('foobar');
+  });
+
+  it('clones arrays', () => {
+    const arr = [
+      1,
+      [false],
+      ['string', {}],
+      'foo'
+    ];
+    const arrCopy = clone(arr);
+    expect(arrCopy).toEqual(arr);
+    expect(arrCopy).not.toBe(arr);
+    expect(arrCopy[1]).not.toBe(arr[1]);
+    expect(arrCopy[2]).not.toBe(arr[2]);
+    expect(arrCopy[2][1]).not.toBe(arr[2][1]);
+  });
+
+  it('clones objects', () => {
+    const obj = {
+      prop: {
+        arr: [{}, 1, true, ''],
+        prop: {}
+      },
+      arr: []
+    };
+    const objCopy = clone(obj);
+    expect(objCopy).toEqual(obj);
+    expect(objCopy).not.toBe(obj);
+    expect(objCopy.prop).not.toBe(obj.prop);
+    expect(objCopy.arr).not.toBe(obj.arr);
+    expect(objCopy.prop.arr[0]).not.toBe(obj.prop.arr[0]);
+  });
+
+});
\ No newline at end of file