Repository: DmitrySoshnikov/regexp-tree
Pull request #117 (2017-11-20 23:43:52)

Optimizer: Merge class ranges
The transform is this PR processes character classes to merge class ranges.

It merges chars in class ranges:
`/[a-fe]/` -> `/[a-f]/`

It merges class ranges one into another:
`/[a-zc-g]/` -> `/[a-z]/`

It expends class ranges to include chars:
`/[a-cd]` -> `[a-d]/`
`/[ab-d]` -> `[a-d]/`

It combines class ranges that overlap or are contiguous:
`/[a-fc-k]` -> `[a-k]/`
`/[a-cd-k]` -> `[a-k]/`

It merges chars and class ranges into meta classes:
`/[\wac-f$]/` -> `/[\w$]/`
`/[\w\u017f$/iu` -> `/[\w$]/iu`

It merges meta classes one into another:
`/[\w\d$]/` -> `/[\w$]/`
`/[\D\W\s9]/` -> `/[\D9]/`


Patch:
diff --git a/src/optimizer/transforms/char-class-classranges-merge-transform.js b/src/optimizer/transforms/char-class-classranges-merge-transform.js
new file mode 100644
index 0000000..7c6183b
--- /dev/null
+++ b/src/optimizer/transforms/char-class-classranges-merge-transform.js
@@ -0,0 +1,314 @@
+/**
+ * The MIT License (MIT)
+ * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ */
+
+'use strict';
+
+/**
+ * A regexp-tree plugin to merge class ranges.
+ *
+ * [a-ec] -> [a-e]
+ * [a-ec-e] -> [a-e]
+ * [\w\da-f] -> [\w]
+ */
+module.exports = {
+  _hasIUFlags: false,
+  init(ast) {
+    this._hasIUFlags = ast.flags.includes('i') && ast.flags.includes('u');
+  },
+  CharacterClass(path) {
+    const {node} = path;
+    let expressions = node.expressions;
+
+    const metas = [];
+    // Extract metas
+    expressions.forEach(expression => {
+      if (isMeta(expression)) {
+        metas.push(expression.value);
+      }
+    });
+
+    expressions.sort(sortCharClass);
+
+    for (let i = 0; i < expressions.length; i++) {
+      let expression = expressions[i];
+      if (
+        fitsInMetas(expression, metas, this._hasIUFlags) ||
+        combinesWithPrecedingClassRange(expression, expressions[i - 1]) ||
+        combinesWithFollowingClassRange(expression, expressions[i + 1])
+      ) {
+        expressions.splice(i, 1);
+        i--;
+      }
+    }
+  }
+};
+
+/**
+ * Sorts expressions in char class in the following order:
+ * - meta chars, ordered alphabetically by value
+ * - chars (except `control` kind) and class ranges, ordered alphabetically (`from` char is used for class ranges)
+ * - if ambiguous, class range comes before char
+ * - if ambiguous between two class ranges, orders alphabetically by `to` char
+ * - control chars, ordered alphabetically by value
+ * @param {Object} a - Left Char or ClassRange node
+ * @param {Object} b - Right Char or ClassRange node
+ * @returns {number}
+ */
+function sortCharClass(a, b) {
+  const aValue = getSortValue(a);
+  const bValue = getSortValue(b);
+
+  if (aValue === bValue) {
+    // We want ClassRange before Char
+    // [bb-d] -> [b-db]
+    if (a.type === 'ClassRange' && b.type !== 'ClassRange') {
+      return -1;
+    }
+    if (b.type === 'ClassRange' && a.type !== 'ClassRange') {
+      return 1;
+    }
+    if (a.type === 'ClassRange' && b.type === 'ClassRange') {
+      return getSortValue(a.to) - getSortValue(b.to);
+    }
+    if (
+      (isMeta(a) && isMeta(b)) ||
+      (isControl(a) && isControl(b))
+    ) {
+      return a.value < b.value ? -1 : 1;
+    }
+  }
+  return aValue - bValue;
+}
+
+/**
+ * @param {Object} expression - Char or ClassRange node
+ * @returns {number}
+ */
+function getSortValue(expression) {
+  if (expression.type === 'Char') {
+    if (expression.kind === 'control') {
+      return Infinity;
+    }
+    if (expression.kind === 'meta' && isNaN(expression.codePoint)) {
+      return -1;
+    }
+    return expression.codePoint;
+  }
+  // ClassRange
+  return expression.from.codePoint;
+}
+
+/**
+ * Checks if a node is a meta char from the set \d\w\s\D\W\S
+ * @param {Object} expression - Char or ClassRange node
+ * @param {?string} value
+ * @returns {boolean}
+ */
+function isMeta(expression, value = null) {
+  return expression.type === 'Char' &&
+    expression.kind === 'meta' &&
+    (value ? expression.value === value : /^\\[dws]$/i.test(expression.value));
+}
+
+/**
+ * @param {Object} expression - Char or ClassRange node
+ * @returns {boolean}
+ */
+function isControl(expression) {
+  return expression.type === 'Char' &&
+    expression.kind === 'control';
+}
+
+/**
+ * @param {Object} expression - Char or ClassRange node
+ * @param {string[]} metas - Array of meta chars, e.g. ["\\w", "\\s"]
+ * @param {boolean} hasIUFlags
+ * @returns {boolean}
+ */
+function fitsInMetas(expression, metas, hasIUFlags) {
+  for (let i = 0; i < metas.length; i++) {
+    if (fitsInMeta(expression, metas[i], hasIUFlags)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+/**
+ * @param {Object} expression - Char or ClassRange node
+ * @param {string} meta - e.g. "\\w"
+ * @param {boolean} hasIUFlags
+ * @returns {boolean}
+ */
+function fitsInMeta(expression, meta, hasIUFlags) {
+  if (expression.type === 'ClassRange') {
+    return fitsInMeta(expression.from, meta, hasIUFlags) && fitsInMeta(expression.to, meta, hasIUFlags);
+  }
+
+  // Special cases:
+  // \S contains \w and \d
+  if (meta === '\\S' && (isMeta(expression, '\\w') || isMeta(expression, '\\d'))) {
+    return true;
+  }
+  // \D contains \W and \s
+  if (meta === '\\D' && (isMeta(expression, '\\W') || isMeta(expression, '\\s'))) {
+    return true;
+  }
+  // \w contains \d
+  if (meta === '\\w' && isMeta(expression, '\\d')) {
+    return true;
+  }
+  // \W contains \s
+  if (meta === '\\W' && isMeta(expression, '\\s')) {
+    return true;
+  }
+
+  if (expression.type !== 'Char' || isNaN(expression.codePoint)) {
+    return false;
+  }
+
+  if (meta === '\\s') {
+    return fitsInMetaS(expression);
+  }
+  if (meta === '\\S') {
+    return !fitsInMetaS(expression);
+  }
+  if (meta === '\\d') {
+    return fitsInMetaD(expression);
+  }
+  if (meta === '\\D') {
+    return !fitsInMetaD(expression);
+  }
+  if (meta === '\\w') {
+    return fitsInMetaW(expression, hasIUFlags);
+  }
+  if (meta === '\\W') {
+    return !fitsInMetaW(expression, hasIUFlags);
+  }
+  return false;
+}
+
+/**
+ * @param {Object} expression - Char node with codePoint
+ * @returns {boolean}
+ */
+function fitsInMetaS(expression) {
+  return expression.codePoint === 0x0009 || // \t
+    expression.codePoint === 0x000a || // \n
+    expression.codePoint === 0x000b || // \v
+    expression.codePoint === 0x000c || // \f
+    expression.codePoint === 0x000d || // \r
+    expression.codePoint === 0x0020 || // space
+    expression.codePoint === 0x00a0 || // nbsp
+    expression.codePoint === 0x1680 || // part of Zs
+    (expression.codePoint >= 0x2000 && expression.codePoint <= 0x200a) || // part of Zs
+    expression.codePoint === 0x2028 || // line separator
+    expression.codePoint === 0x2029 || // paragraph separator
+    expression.codePoint === 0x202f || // part of Zs
+    expression.codePoint === 0x205f || // part of Zs
+    expression.codePoint === 0x3000 || // part of Zs
+    expression.codePoint === 0xfeff; // zwnbsp
+}
+
+/**
+ * @param {Object} expression - Char node with codePoint
+ * @returns {boolean}
+ */
+function fitsInMetaD(expression) {
+  return expression.codePoint >= 0x30 && expression.codePoint <= 0x39; // 0-9
+}
+
+/**
+ * @param {Object} expression - Char node with codePoint
+ * @param {boolean} hasIUFlags
+ * @returns {boolean}
+ */
+function fitsInMetaW(expression, hasIUFlags) {
+  return fitsInMetaD(expression) ||
+    (expression.codePoint >= 0x41 && expression.codePoint <= 0x5a) || // a-z
+    (expression.codePoint >= 0x61 && expression.codePoint <= 0x7a) || // A-Z
+    expression.value === '_' ||
+    (hasIUFlags && (expression.codePoint === 0x017f || expression.codePoint === 0x212a));
+}
+
+/**
+ * @param {Object} expression - Char or ClassRange node
+ * @param {Object} classRange - Char or ClassRange node
+ * @returns {boolean}
+ */
+function combinesWithPrecedingClassRange(expression, classRange) {
+  if (classRange && classRange.type === 'ClassRange') {
+
+    if (fitsInClassRange(expression, classRange)) {
+      // [a-gc] -> [a-g]
+      // [a-gc-e] -> [a-g]
+      return true;
+
+    } else if (
+      expression.type === 'Char' &&
+      !isNaN(expression.codePoint) &&
+      classRange.to.codePoint === expression.codePoint - 1
+    ) {
+      // [a-de] -> [a-e]
+      classRange.to = expression;
+      return true;
+
+    } else if (
+      expression.type === 'ClassRange' &&
+      expression.from.codePoint <= classRange.to.codePoint + 1 &&
+      expression.to.codePoint >= classRange.from.codePoint - 1
+    ) {
+      // [a-db-f] -> [a-f]
+      // [b-fa-d] -> [a-f]
+      // [a-cd-f] -> [a-f]
+      if (expression.from.codePoint < classRange.from.codePoint) {
+        classRange.from = expression.from;
+      }
+      if (expression.to.codePoint > classRange.to.codePoint) {
+        classRange.to = expression.to;
+      }
+      return true;
+    }
+  }
+  return false;
+}
+
+/**
+ * @param {Object} expression - Char or ClassRange node
+ * @param {Object} classRange - Char or ClassRange node
+ * @returns {boolean}
+ */
+function combinesWithFollowingClassRange(expression, classRange) {
+  if (classRange && classRange.type === 'ClassRange') {
+    // Considering the elements were ordered alphabetically,
+    // there is only one case to handle
+    // [ab-e] -> [b-e]
+    if (
+      expression.type === 'Char' &&
+      !isNaN(expression.codePoint) &&
+      classRange.from.codePoint === expression.codePoint + 1
+    ) {
+      classRange.from = expression;
+      return true;
+    }
+  }
+
+  return false;
+}
+
+/**
+ * @param {Object} expression - Char or ClassRange node
+ * @param {Object} classRange - ClassRange node
+ * @returns {boolean}
+ */
+function fitsInClassRange(expression, classRange) {
+  if (expression.type === 'Char' && isNaN(expression.codePoint)) {
+    return false;
+  }
+  if (expression.type === 'ClassRange') {
+    return fitsInClassRange(expression.from, classRange) && fitsInClassRange(expression.to, classRange);
+  }
+  return expression.codePoint >= classRange.from.codePoint && expression.codePoint <= classRange.to.codePoint;
+}
\ No newline at end of file
diff --git a/src/optimizer/transforms/index.js b/src/optimizer/transforms/index.js
index 05bf8b9..790c377 100644
--- a/src/optimizer/transforms/index.js
+++ b/src/optimizer/transforms/index.js
@@ -15,6 +15,9 @@ module.exports = {
   // a{1,} -> a+, a{3,3} -> a{3}, a{1} -> a
   'quantifierRangeToSymbol': require('./quantifier-range-to-symbol-transform'),
 
+  // [a-de-f] -> [a-f]
+  'charClassClassrangesMerge': require('./char-class-classranges-merge-transform'),
+
   // [0-9] -> [\d]
   'charClassToMeta': require('./char-class-to-meta-transform'),
 


Test patch:
diff --git a/src/optimizer/__tests__/optimizer-integration-test.js b/src/optimizer/__tests__/optimizer-integration-test.js
index 7825f4a..d7021fd 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());
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
new file mode 100644
index 0000000..70590f9
--- /dev/null
+++ b/src/optimizer/transforms/__tests__/char-class-classranges-merge-transform-test.js
@@ -0,0 +1,125 @@
+/**
+ * The MIT License (MIT)
+ * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ */
+
+'use strict';
+
+const {transform} = require('../../../transform');
+const charClassClassrangesMerge = require('../char-class-classranges-merge-transform');
+
+describe('char-class-classranges-merge', () => {
+
+  it('merges chars in meta', () => {
+    let re = transform(/[\wa_z]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\w]/');
+
+    re = transform(/[\d1509]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\d]/');
+
+    re = transform(/[\s\t\u2000 ]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\s]/');
+  });
+
+  it('merges chars in \w with i and u flags', () => {
+    const re = transform(/[\u212a\w\u017fa]/iu, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\w]/iu');
+  });
+
+  it('merges class ranges in meta', () => {
+    let re = transform(/[\wa-dh-u]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\w]/');
+
+    re = transform(/[\d1-5]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\d]/');
+
+    re = transform(/[\s\u2000-\u2007]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\s]/');
+  });
+
+  it('merges meta in meta', () => {
+    let re = transform(/[\w\d]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\w]/');
+
+    re = transform(/[\W\D\s]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\D]/');
+
+    re = transform(/[\W\s]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\W]/');
+
+    re = transform(/[\w\S\d]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\S]/');
+  });
+
+  it('merges chars in class ranges', () => {
+    let re = transform(/[fb-eg]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[b-g]/');
+
+    re = transform(/[bva-g15dt-z0-7]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[0-7a-gt-z]/');
+
+    re = transform(/[\u0024-\u0035\u0027]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\u0024-\\u0035]/');
+
+    re = transform(/[\u{24}-\u{35}\u0027\u{28}]/u, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\u{24}-\\u{35}]/u');
+
+    re = transform(/[\ud83d\ude80-\ud83d\ude88\ud83d\ude83]/u, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\ud83d\\ude80-\\ud83d\\ude88]/u');
+  });
+
+  it('merges ranges together', () => {
+    let re = transform(/[a-fc-u0-56-8]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[0-8a-u]/');
+
+    re = transform(/[\u0024-\u0035\u0036-\u0042]/, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\u0024-\\u0042]/');
+
+    re = transform(/[\u{24}-\u{35}\u0036-\u0042]/u, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\u{24}-\\u0042]/u');
+
+    re = transform(/[\u{1F680}-\ud83d\ude88\ud83d\ude89-\ud83d\ude9b]/u, [
+      charClassClassrangesMerge,
+    ]);
+    expect(re.toString()).toBe('/[\\u{1F680}-\\ud83d\\ude9b]/u');
+  });
+
+});
\ No newline at end of file