Repository: DmitrySoshnikov/regexp-tree
Pull request #73 (2017-05-06 18:49:14)

check for correct boundaries in char class range
refs #1

hg42: I think the parser should be tolerant or have a tolerant mode.
Otherwise we cannot write transformations that correct such things.

Perhaps such checks should be moved to a separate function like `check(...)`. Or `optimize` could have such rule sets.
silentroach: why? you just can't use `[z-a]` in your code, it will not compile
hg42: the parser can be used to write regexp extensions. An extension could allow this (and swap those characters).

But my concern is not about this particular case.
I just wanted to express, that a parser for general purposes should not be too picky, because it can be used for many things that may eventually break some rules.

I would put such a check in it's own pass or it could be placed in a generator for a specific target, because such rules depend on the target.

Example: you can parse named groups, even if the target does not allow them as long as you transform them to something else. If you would restrict the parser, you would not be able to do that.

You can also allow several syntax variants for named groups:
`(?<name>...)`, `(?P<name>...)`, `(?'name'...)` and generate whatever is supported by the target.

hg42: also, if the check is placed in the parser, it only checks the input. But you may create such illegal constructs in transformations. So it would be better to check the output. Seems like the generator would be the best place. A separate checking pass could be even better, because you could react on such failures very differently. May be you want to explicitely warn about it but correct the error.

Throwing an exception also stops processing.
In some cases you might want to report all errors instead of only the first.
It's not fatal to the parsing process, so why stop it?
DmitrySoshnikov: @hg42, yeah, I agreed on specifically extensions, that parser should not break them, however, in this specific case it's per ES-spec (it should be a parse error), and the `[z-a]` doesn't make sense, same as `{5,1}` for quantifier.

> Throwing an exception also stops processing.
In some cases you might want to report all errors instead of only the first.
It's not fatal to the parsing process, so why stop it?

I have a task opened in `Syntax` to implement error recovery: https://github.com/DmitrySoshnikov/syntax/issues/28, but for now it's not supported. Later we'll be able to collect all errors in one pass, and report them after parsing.

Anyways, for this specific case, we should definitely merge it, since it's per ES-spec.
hg42: I think it should be possible to get a list of errors **and** the AST in such cases.
E.g. for analyzers, linters or for teaching purposes.
Only errors fatal for parsing (like structural errors) should stop parsing.
There are cases when non-programmers make errors that can be corrected, then I would want to ask them and display corresponding parts of the tree (I'm talking about real cases I had in my jobs).

Patch:
diff --git a/src/parser/generated/regexp-tree.js b/src/parser/generated/regexp-tree.js
index 93edd4b..5979cfe 100644
--- a/src/parser/generated/regexp-tree.js
+++ b/src/parser/generated/regexp-tree.js
@@ -274,6 +274,8 @@ const productions = [[-1,1,(_1,_1loc) => { __loc = yyloc(_1loc, _1loc);__ = _1 }
 [19,1,(_1,_1loc) => { __loc = yyloc(_1loc, _1loc); __ = [_1]  }],
 [19,2,(_1,_2,_1loc,_2loc) => { __loc = yyloc(_1loc, _2loc); __ = [_1].concat(_2)  }],
 [19,4,(_1,_2,_3,_4,_1loc,_2loc,_3loc,_4loc) => { __loc = yyloc(_1loc, _4loc);
+      checkClassRange(_1.value, _3.value);
+
       __ = [
         Node({
           type: 'ClassRange',
@@ -289,6 +291,8 @@ const productions = [[-1,1,(_1,_1loc) => { __loc = yyloc(_1loc, _1loc);__ = _1 }
 [20,1,(_1,_1loc) => { __loc = yyloc(_1loc, _1loc);__ = _1 }],
 [20,2,(_1,_2,_1loc,_2loc) => { __loc = yyloc(_1loc, _2loc); __ = [_1].concat(_2)  }],
 [20,4,(_1,_2,_3,_4,_1loc,_2loc,_3loc,_4loc) => { __loc = yyloc(_1loc, _4loc);
+      checkClassRange(_1.value, _3.value);
+
       __ = [
         Node({
           type: 'ClassRange',
@@ -845,6 +849,15 @@ function getRange(text) {
   return range;
 }
 
+/**
+ * Checks class range
+ */
+function checkClassRange(from, to) {
+  if (from > to) {
+    throw new SyntaxError(`Range ${from}-${to} out of order in character class`);
+  }
+}
+
 /**
  * Creates a character node.
  */
diff --git a/src/parser/regexp.bnf b/src/parser/regexp.bnf
index 87fe582..a180fbc 100644
--- a/src/parser/regexp.bnf
+++ b/src/parser/regexp.bnf
@@ -174,6 +174,15 @@ function getRange(text) {
   return range;
 }
 
+/**
+ * Checks class range
+ */
+function checkClassRange(from, to) {
+  if (from > to) {
+    throw new SyntaxError(`Range ${from}-${to} out of order in character class`);
+  }
+}
+
 /**
  * Creates a character node.
  */
@@ -694,6 +703,8 @@ NonemptyClassRanges
 
   | ClassAtom DASH ClassAtom ClassRanges
     {
+      checkClassRange($1.value, $3.value);
+
       $$ = [
         Node({
           type: 'ClassRange',
@@ -715,6 +726,8 @@ NonemptyClassRangesNoDash
 
   | ClassAtomNoDash DASH ClassAtom ClassRanges
     {
+      checkClassRange($1.value, $3.value);
+
       $$ = [
         Node({
           type: 'ClassRange',


Test patch:
diff --git a/src/parser/__tests__/parser-test262-test.js b/src/parser/__tests__/parser-test262-test.js
index cbb82fa..031882f 100644
--- a/src/parser/__tests__/parser-test262-test.js
+++ b/src/parser/__tests__/parser-test262-test.js
@@ -33,7 +33,8 @@ describe('test262', () => {
 
   it('invalid char range', () => {
     // 15.10.2.15-6-1
-    // TODO: /^[z-a]$/ - should throw, 'a' is less than 'z'
+    invalid('/^[z-a]$/', 'out of order');
+    invalid('/^[-z-a]$/', 'out of order');
   });
 
   it('invalid quantifier range', () => {