Repository: DmitrySoshnikov/regexp-tree
Pull request #122 (2017-11-23 07:31:14)

Optimizer: Combine chars sequences into class ranges in char-class-classranges-merge transform
This PR updates the char-class-classranges-merge transform to handle sequences of chars:

`/[abcdef]/` -> `/[a-f]/`

For the sake of readability, I chose to only merge chars being in `\w` or being coded (either unicode, hex, octal or decimal). I'm not sure about this choice though.

Should the optimizer transform `/[<=>?]/` into `/[<-?]/`?


Patch:
diff --git a/src/optimizer/transforms/char-class-classranges-merge-transform.js b/src/optimizer/transforms/char-class-classranges-merge-transform.js
index 72f88eb..4a45cdb 100644
--- a/src/optimizer/transforms/char-class-classranges-merge-transform.js
+++ b/src/optimizer/transforms/char-class-classranges-merge-transform.js
@@ -11,6 +11,7 @@
  * [a-ec] -> [a-e]
  * [a-ec-e] -> [a-e]
  * [\w\da-f] -> [\w]
+ * [abcdef] -> [a-f]
  */
 module.exports = {
   _hasIUFlags: false,
@@ -40,6 +41,10 @@ module.exports = {
       ) {
         expressions.splice(i, 1);
         i--;
+      } else {
+        const nbMergedChars = charCombinesWithPrecedingChars(expression, i, expressions);
+        expressions.splice(i - nbMergedChars + 1, nbMergedChars);
+        i -= nbMergedChars;
       }
     }
   }
@@ -311,4 +316,53 @@ function fitsInClassRange(expression, classRange) {
     return fitsInClassRange(expression.from, classRange) && fitsInClassRange(expression.to, classRange);
   }
   return expression.codePoint >= classRange.from.codePoint && expression.codePoint <= classRange.to.codePoint;
+}
+
+/**
+ * @param {Object} expression - Char or ClassRange node
+ * @param {Number} index
+ * @param {Object[]} expressions - expressions in CharClass
+ * @returns {number} - Number of characters combined with expression
+ */
+function charCombinesWithPrecedingChars(expression, index, expressions) {
+  if (!isMetaWCharOrCode(expression)) {
+    return 0;
+  }
+  let nbMergedChars = 0;
+  while (index > 0) {
+    let currentExpression = expressions[index];
+    let precedingExpresion = expressions[index - 1];
+    if (
+      isMetaWCharOrCode(precedingExpresion) &&
+      precedingExpresion.codePoint === currentExpression.codePoint - 1
+    ) {
+      nbMergedChars++;
+      index--;
+    } else {
+      break;
+    }
+  }
+
+  if (nbMergedChars > 1) {
+    expressions[index] = {
+      type: 'ClassRange',
+      from: expressions[index],
+      to: expression
+    };
+    return nbMergedChars;
+  }
+  return 0;
+}
+
+function isMetaWCharOrCode(expression) {
+  return expression &&
+    expression.type === 'Char' &&
+    !isNaN(expression.codePoint) &&
+    (
+      fitsInMetaW(expression, false) ||
+      expression.kind === 'unicode' ||
+      expression.kind === 'hex' ||
+      expression.kind === 'oct' ||
+      expression.kind === 'decimal'
+    );
 }
\ No newline at end of file


Test patch:
diff --git a/src/optimizer/transforms/__tests__/char-class-classranges-merge-transform-test.js b/src/optimizer/transforms/__tests__/char-class-classranges-merge-transform-test.js
index 70590f9..37d90a7 100644
--- a/src/optimizer/transforms/__tests__/char-class-classranges-merge-transform-test.js
+++ b/src/optimizer/transforms/__tests__/char-class-classranges-merge-transform-test.js
@@ -122,4 +122,38 @@ describe('char-class-classranges-merge', () => {
     expect(re.toString()).toBe('/[\\u{1F680}-\\ud83d\\ude9b]/u');
   });
 
+  it('combines sequential chars into class ranges', () => {
+    let re = transform(/[facbdemlpqno]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[a-fl-q]/');
+
+    re = transform(/[\u0014\u0015\u0016]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\u0014-\\u0016]/');
+
+    re = transform(/[a\u0062c\u0064]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[a-\\u0064]/');
+
+    re = transform(/[a\u{62}c\u{64}]/u, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[a-\\u{64}]/u');
+
+    re = transform(/[\ud83d\ude88\ud83d\ude89\ud83d\ude8a]/u, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\ud83d\\ude88-\\ud83d\\ude8a]/u');
+  });
+
+  it('does not combine sequential chars that are nor in \\w nor number-coded', () => {
+    const re = transform(/[<=>?]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[<=>?]/');
+  });
+
 });
\ No newline at end of file