Repository: DmitrySoshnikov/regexp-tree
Pull request #126 (2017-11-24 19:26:00)

Optimizer: Transform Char to lowercase when i flag is set
`/aA[bB]Ï/i` -> `/aa[bb]ï/i`

Golmote: I updated the PR to process more chars.

It now transforms to lowercase all characters it can, but keeps the Char kind.
`/A/i` -> `/a/i`
`/\65/i` -> `/\97/i`
`/\x41/i` -> `/\x61/i`
`/\u0041/i` -> `/\u0061/i`
`/\u{41}/i` -> `/\u{61}/i`

Surrogate pairs should be handled properly as well. I did not include a test, though, since Node 6 does not seem to map lower/upper values of characters above \u{10000}.
Running on Node 7, this transform should work:
`/\ud801\udc09/i` -> `/\ud801\udc31/i`

The transform now also does additional checks if the parent is a Class Range to not break ranges like `A-z`. Only ranges included inside `A-Z` are transformed.
mathiasbynens: Neat! Maybe add a test like

```js
/\u13AB/ui.test('\uAB7B');
// should be true before and after transformation
```
Golmote: @mathiasbynens I'm confused. Is the `u` flag required here for `\u13AB` to match `\uAB7B` case-insensitively? It appears to be the case on both NodeJS 6.8, NodeJS 7.4 and Google Chrome. Firefox, though, does not require the `u` flag for it to be true.
mathiasbynens: I agree it’s confusing. See https://mathiasbynens.be/demo/regex-i and https://github.com/Microsoft/ChakraCore/issues/517 for some background.
Golmote: @mathiasbynens So, as I understand it, it _is not_ safe to transform `/\u13AB/i` to `/\uAB7B/i` but it _is_ safe to transform `/\u13AB/iu` to `/\uAB7B/iu`? Yet, it is alsways safe to transform `/\u0045/i` to `/\u0065/i`... Do you happen to know where is the limit?
Golmote: I ran a few tests on my own. Browser support is kind of a mess...
Google Chrome requires the `u` flag for whole ranges of characters (`\u13a0-\u13f5`, `\ua7b2-\ua7b6`...).
Edge 16 fails to lowercase some chars (like `\u10cd` or `\ua69a`), but somehow still matches them properly with `iu` flag.

I updated the PR to require the `u` flag being set before lowercasing characters above `\u1000`.

Even with the `u` flag set, though, the optimisation will still depend on the engine's ability to lowercase the chars. That is, Node 6.8.0 won't optimize `/\u13ab/iu` to `/\uab7b/iu` because it's unable to lowercase `\u13ab` at all.
DmitrySoshnikov: > Even with the u flag set, though, the optimisation will still depend on the engine's ability to lowercase the chars

Yeah, that's a good decision.

I'm thinking whether we can already bump the engine number to 7 or 8 in the `package.json`. Current stable is 8, and the latest one is already 9.
Golmote: > I'm thinking whether we can already bump the engine number to 7 or 8 in the package.json.

Yeah, that would probably be ok.

Patch:
diff --git a/src/optimizer/transforms/char-case-insensitive-lowercase-transform.js b/src/optimizer/transforms/char-case-insensitive-lowercase-transform.js
new file mode 100644
index 0000000..e72581d
--- /dev/null
+++ b/src/optimizer/transforms/char-case-insensitive-lowercase-transform.js
@@ -0,0 +1,104 @@
+/**
+ * The MIT License (MIT)
+ * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ */
+
+'use strict';
+
+const UPPER_A_CP = 'A'.codePointAt(0);
+const UPPER_Z_CP = 'Z'.codePointAt(0);
+/**
+ * Transforms case-insensitive regexp to lowercase
+ *
+ * /AaBbÏ/i -> /aabbï/i
+ */
+module.exports = {
+  _AZClassRanges: null,
+  _hasUFlag: false,
+  init(ast) {
+    this._AZClassRanges = new Set();
+    this._hasUFlag = ast.flags.includes('u');
+  },
+  shouldRun(ast) {
+    return ast.flags.includes('i');
+  },
+  Char(path) {
+    const {node, parent} = path;
+    if (isNaN(node.codePoint)) {
+      return;
+    }
+
+    // Engine support for case-insensitive matching without the u flag
+    // for characters above \u1000 does not seem reliable.
+    if (!this._hasUFlag && node.codePoint >= 0x1000) {
+      return;
+    }
+
+    if (parent.type === 'ClassRange') {
+      // The only class ranges we handle must be inside A-Z.
+      // After the `from` char is processed, the isAZClassRange test
+      // will be false, so we use a Set to keep track of parents and
+      // process the `to` char.
+      if (!this._AZClassRanges.has(parent) && !isAZClassRange(parent)) {
+        return;
+      }
+      this._AZClassRanges.add(parent);
+    }
+
+    const lower = node.symbol.toLowerCase();
+    if (lower !== node.symbol) {
+      node.value = displaySymbolAsValue(lower, node);
+      node.symbol = lower;
+      node.codePoint = lower.codePointAt(0);
+    }
+  }
+};
+
+function isAZClassRange(classRange) {
+  const {from, to} = classRange;
+  // A-Z
+  return from.codePoint >= UPPER_A_CP && from.codePoint <= UPPER_Z_CP &&
+    to.codePoint >= UPPER_A_CP && to.codePoint <= UPPER_Z_CP;
+}
+
+function displaySymbolAsValue(symbol, node) {
+  const codePoint = symbol.codePointAt(0);
+  if (node.kind === 'decimal') {
+    return '\\' + codePoint;
+  }
+  if (node.kind === 'oct') {
+    return '\\0' + codePoint.toString(8);
+  }
+  if (node.kind === 'hex') {
+    return '\\x' + codePoint.toString(16);
+  }
+  if (node.kind === 'unicode') {
+    if (node.isSurrogatePair) {
+      const {lead, trail} = getSurrogatePairFromCodePoint(codePoint);
+      return '\\u' + '0'.repeat(4 - lead.length) + lead + '\\u' + '0'.repeat(4 - trail.length) + trail;
+    } else if (node.value.includes('{')) {
+      return '\\u{' + codePoint.toString(16) + '}';
+    } else {
+      const code = codePoint.toString(16);
+      return '\\u' + '0'.repeat(4 - code.length) + code;
+    }
+  }
+  // simple
+  return symbol;
+}
+
+/**
+ * Converts a code point to a surrogate pair.
+ * Conversion algorithm is taken from The Unicode Standard 3.0 Section 3.7
+ * (https://www.unicode.org/versions/Unicode3.0.0/ch03.pdf)
+ * @param {number} codePoint - Between 0x10000 and 0x10ffff
+ * @returns {{lead: string, trail: string}}
+ */
+function getSurrogatePairFromCodePoint(codePoint) {
+  const lead = Math.floor((codePoint - 0x10000) / 0x400) + 0xd800;
+  const trail = (codePoint - 0x10000) % 0x400 + 0xdc00;
+  return {
+    lead: lead.toString(16),
+    trail: trail.toString(16)
+  };
+}
\ No newline at end of file
diff --git a/src/optimizer/transforms/index.js b/src/optimizer/transforms/index.js
index 9704a2a..6a2bb44 100644
--- a/src/optimizer/transforms/index.js
+++ b/src/optimizer/transforms/index.js
@@ -9,6 +9,9 @@ module.exports = {
   // \ud83d\ude80 -> \u{1f680}
   'charSurrogatePairToSingleUnicode': require('./char-surrogate-pair-to-single-unicode-transform'),
 
+  // /Aa/i -> /aa/i
+  'charCaseInsensitiveLowerCaseTransform': require('./char-case-insensitive-lowercase-transform'),
+
   // [\d\d] -> [\d]
   'charClassRemoveDuplicates': require('./char-class-remove-duplicates-transform'),
 


Test patch:
diff --git a/src/optimizer/transforms/__tests__/char-case-insensitive-lowercase-transform-test.js b/src/optimizer/transforms/__tests__/char-case-insensitive-lowercase-transform-test.js
new file mode 100644
index 0000000..a49b34f
--- /dev/null
+++ b/src/optimizer/transforms/__tests__/char-case-insensitive-lowercase-transform-test.js
@@ -0,0 +1,94 @@
+/**
+ * The MIT License (MIT)
+ * Copyright (c) 2017-present Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
+ */
+
+'use strict';
+
+const {transform} = require('../../../transform');
+const charCaseInsensitiveLowercase = require('../char-case-insensitive-lowercase-transform');
+
+describe('char-case-insensitive-lowercase', () => {
+
+  it('lowercases chars when i flag is set', () => {
+    let re = transform(/aA[bB]Ï/i, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/aa[bb]ï/i');
+
+    re = transform(/\65/i, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/\\97/i');
+
+    re = transform(/\x41/i, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/\\x61/i');
+
+    re = transform(/\u0041/i, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/\\u0061/i');
+
+    re = transform(/\u{41}/iu, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/\\u{61}/iu');
+  });
+
+  it('lowercases char >= \\u1000 when u flag is set', () => {
+    const re = transform(/\u10a0/iu, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/\\u2d00/iu');
+  });
+
+  it('does not lowercase char >= \\u1000 without u flag set', () => {
+    const re = transform(/\u10a0/i, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/\\u10a0/i');
+  });
+
+  it('lowercases chars in A-Z class ranges when i flag is set', () => {
+    let re = transform(/[A-ZB-H]/i, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/[a-zb-h]/i');
+
+    re = transform(/[\65-\90\66-\72]/i, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/[\\97-\\122\\98-\\104]/i');
+
+    re = transform(/[\x41-\x5a\x42-\x48]/i, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/[\\x61-\\x7a\\x62-\\x68]/i');
+
+    re = transform(/[\u0041-\u005a\u0042-\u0048]/i, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/[\\u0061-\\u007a\\u0062-\\u0068]/i');
+
+    re = transform(/[\u{41}-\u{5a}\u{42}-\u{48}]/iu, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/[\\u{61}-\\u{7a}\\u{62}-\\u{68}]/iu');
+  });
+
+  it('does not run when i flag is absent', () => {
+    const re = transform(/aA[bB]Ï/, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/aA[bB]Ï/');
+  });
+
+  it('ignores class ranges outside A-Z', () => {
+    const re = transform(/[0-BA-z]/i, [
+      charCaseInsensitiveLowercase,
+    ]);
+    expect(re.toString()).toBe('/[0-BA-z]/i');
+  });
+});
\ No newline at end of file