Repository: DmitrySoshnikov/regexp-tree
Pull request #110 (2017-11-18 13:28:23)

Optimizer: Unescape ^ - { } when safe
This PR handles to TODOs in the `char-escape-unescape` transform.

It unescapes `\^` in character class except when it's in first position and the char class is not negative:
`/[\^a]/` -> `/[\^a]/`
`/[a\^]/` -> `/[a^]/`
`/[^\^]/` -> `/[^^]/`

It unescapes `\-` in character class when it's in first or last position:
`/[a\-z]/` -> `/[a\-z]/`
`/[\-a]/` -> `/[-a]/`
`/[a\-]/` -> `/[a-]/`

It unescapes `\{` except when it does look like a range quantifier:
`/\{/` -> `/{/`
`/\{3}/` -> `/\{3}/`
`/\{3,}/` -> `/\{3,}/`
`/\{3,4}/` -> `/\{3,4}/`

It unescapes `\}` except when it does look like a range quantifier:
`/\}/` -> `/}/`
`/{3\}/` -> `/{3\}/`
`/{3,\}/` -> `/{3,\}/`
`/{3,4\}/` -> `/{3,4\}/`


Patch:
diff --git a/src/optimizer/transforms/char-escape-unescape-transform.js b/src/optimizer/transforms/char-escape-unescape-transform.js
index 5e28ba0..75f7e03 100644
--- a/src/optimizer/transforms/char-escape-unescape-transform.js
+++ b/src/optimizer/transforms/char-escape-unescape-transform.js
@@ -27,30 +27,112 @@ module.exports = {
 };
 
 function shouldUnescape(path) {
-  const {node: {value}, parent} = path;
+  const {node: {value}, index, parent} = path;
 
   // In char class (, etc are allowed.
   if (parent.type !== 'CharacterClass') {
-    return !preservesEscape(value);
+    return !preservesEscape(value, index, parent);
   }
 
-  return !preservesInCharClass(value);
+  return !preservesInCharClass(value, index, parent);
 }
 
 /**
  * \], \\, \^, \-
- *
- * Note: \- always preserved to avoid `[a\-z]` turning into `[a-z]`.
- * Note: \^ always preserved to avoid `[\^a]` turning into `[^a]`.
- * TODO: more sophisticated analisys.
  */
-function preservesInCharClass(value) {
-  return /[\]\\^-]/.test(value);
+function preservesInCharClass(value, index, parent) {
+  if (value === '^') {
+    // Avoid [\^a] turning into [^a]
+    return index === 0 && !parent.negative;
+  }
+  if (value === '-') {
+    // Avoid [a\-z] turning into [a-z]
+    return index !== 0 && index !== parent.expressions.length - 1;
+  }
+  return /[\]\\]/.test(value);
+}
+
+function preservesEscape(value, index, parent) {
+  if (value === '{') {
+    return preservesOpeningCurlyBraceEscape(index, parent);
+  }
+
+  if (value === '}') {
+    return preservesClosingCurlyBraceEscape(index, parent);
+  }
+
+  return /[*[\]()+?^$./\\|]/.test(value);
+}
+
+function consumeNumbers(startIndex, parent, rtl) {
+  let i = startIndex;
+  let siblingNode = (rtl ? i >= 0 : i < parent.expressions.length) && parent.expressions[i];
+
+  while (
+    siblingNode &&
+    siblingNode.type === 'Char' &&
+    siblingNode.kind === 'simple' &&
+    !siblingNode.escaped &&
+    /\d/.test(siblingNode.value)
+  ) {
+    rtl ? i-- : i++;
+    siblingNode = (rtl ? i >= 0 : i < parent.expressions.length) && parent.expressions[i];
+  }
+
+  return Math.abs(startIndex - i);
+}
+
+function isSimpleChar(node, value) {
+  return node &&
+    node.type === 'Char' &&
+    node.kind === 'simple' &&
+    !node.escaped &&
+    node.value === value;
 }
 
-// Note: \{ and \} are always preserved to avoid `a\{2\}` turning
-// into `a{2}`. TODO: more sophisticated analisys.
+function preservesOpeningCurlyBraceEscape(index, parent) {
+  let nbFollowingNumbers = consumeNumbers(index + 1, parent);
+  let i = index + nbFollowingNumbers + 1;
+  let nextSiblingNode = i < parent.expressions.length && parent.expressions[i];
 
-function preservesEscape(value) {
-  return /[*\[\]()+?^$.\/\\\{\}\|]/.test(value);
+  if (nbFollowingNumbers) {
+
+    // Avoid \{3} turning into {3}
+    if (isSimpleChar(nextSiblingNode, '}')) {
+      return true;
+    }
+
+    if (isSimpleChar(nextSiblingNode, ',')) {
+
+      nbFollowingNumbers = consumeNumbers(i + 1, parent);
+      i = i + nbFollowingNumbers + 1;
+      nextSiblingNode = i < parent.expressions.length && parent.expressions[i];
+
+      // Avoid \{3,} turning into {3,}
+      return isSimpleChar(nextSiblingNode, '}');
+    }
+  }
+  return false;
+}
+
+function preservesClosingCurlyBraceEscape(index, parent) {
+  let nbPrecedingNumbers = consumeNumbers(index - 1, parent, true);
+  let i = index - nbPrecedingNumbers - 1;
+  let previousSiblingNode = i >= 0 && parent.expressions[i];
+
+  // Avoid {3\} turning into {3}
+  if (nbPrecedingNumbers && isSimpleChar(previousSiblingNode, '{')) {
+    return true;
+  }
+
+  if (isSimpleChar(previousSiblingNode, ',')) {
+
+    nbPrecedingNumbers = consumeNumbers(i - 1, parent, true);
+    i = i - nbPrecedingNumbers - 1;
+    previousSiblingNode = i < parent.expressions.length && parent.expressions[i];
+
+    // Avoid {3,\} turning into {3,}
+    return nbPrecedingNumbers && isSimpleChar(previousSiblingNode, '{');
+  }
+  return false;
 }
\ No newline at end of file


Test patch:
diff --git a/src/optimizer/transforms/__tests__/char-escape-unescape-transform-test.js b/src/optimizer/transforms/__tests__/char-escape-unescape-transform-test.js
index 21c632f..b2d398b 100644
--- a/src/optimizer/transforms/__tests__/char-escape-unescape-transform-test.js
+++ b/src/optimizer/transforms/__tests__/char-escape-unescape-transform-test.js
@@ -18,17 +18,72 @@ describe('\e -> e', () => {
   });
 
   it('preserve escape', () => {
-    const re = transform(/\*\^\$\(\)\[\{\}\|/, [
+    const re = transform(/\*\^\$\(\)\[\|/, [
       charUnescape,
     ]);
-    expect(re.toString()).toBe(/\*\^\$\(\)\[\{\}\|/.toString());
+    expect(re.toString()).toBe(/\*\^\$\(\)\[\|/.toString());
+  });
+
+  it('unescapes curly braces', () => {
+    const re = transform(/\{\}/, [
+      charUnescape,
+    ]);
+    expect(re.toString()).toBe(/{}/.toString());
+  });
+
+  it('does not unescape \{ when looking like a quantifier', () => {
+    let re = transform(/a\{3}/, [
+      charUnescape,
+    ]);
+    expect(re.toString()).toBe(/a\{3}/.toString());
+
+    re = transform(/a\{3,}/, [
+      charUnescape,
+    ]);
+    expect(re.toString()).toBe(/a\{3,}/.toString());
+
+    re = transform(/a\{10,12}/, [
+      charUnescape,
+    ]);
+    expect(re.toString()).toBe(/a\{10,12}/.toString());
+  });
+
+  it('does not unescape \} when looking like a quantifier', () => {
+    let re = transform(/a{3\}/, [
+      charUnescape,
+    ]);
+    expect(re.toString()).toBe(/a{3\}/.toString());
+
+    re = transform(/a{3,\}/, [
+      charUnescape,
+    ]);
+    expect(re.toString()).toBe(/a{3,\}/.toString());
+
+    re = transform(/a{10,12\}/, [
+      charUnescape,
+    ]);
+    expect(re.toString()).toBe(/a{10,12\}/.toString());
   });
 
   it('char class', () => {
     const re = transform(/[\e\*\(\]\ \^\$\-]\(\n/, [
       charUnescape,
     ]);
-    expect(re.toString()).toBe(/[e*(\] \^$\-]\(\n/.toString());
+    expect(re.toString()).toBe(/[e*(\] ^$-]\(\n/.toString());
+  });
+
+  it('does not unescape \^ in char class when in first position', () => {
+    const re = transform(/[\^a]/, [
+      charUnescape,
+    ]);
+    expect(re.toString()).toBe(/[\^a]/.toString());
+  });
+
+  it('does not unescape \- in char class when not in first or last position', () => {
+    const re = transform(/[a\-z]/, [
+      charUnescape,
+    ]);
+    expect(re.toString()).toBe(/[a\-z]/.toString());
   });
 
 });
\ No newline at end of file