Implement lookbehind in regexp engine

lib/core/regexp.dart

 // Copyright (c) 2015, the Fletch project authors. Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE.md file.
 
 part of dart.core_patch;
 
 class MiniExpLabel {
   // Initially points to -1 to indicate the label is neither linked (used) nor
   // bound (fixed to a location). When the label is linked, but not bound, it
   // has a negative value, determined by fixupLocation(l), that indicates the
@@ skipping 79 matching lines @@
 
 // Byte codes.
 const GOTO = 0;  // label
 const PUSH_REGISTER = 1;  // reg
 const PUSH_BACKTRACK = 2;  // const
 const POP_REGISTER = 3;  // reg
 const BACKTRACK_EQ = 4;  // reg reg
 const BACKTRACK_NE = 5;  // reg reg
 const BACKTRACK_GT = 6;  // reg reg
 const BACKTRACK_IF_NO_MATCH = 7;  // constant-pool-offset
-const BACKTRACK_IF_IN_RANGE = 8;  // from to
-const GOTO_IF_MATCH = 9;  // charCode label
-const GOTO_IF_IN_RANGE = 10;  // from to label
-const GOTO_EQ = 11; // reg reg label
-const GOTO_GE = 12; // reg reg label
-const GOTO_IF_WORD_CHARACTER = 13;  // position-offset label
-const ADD_TO_REGISTER = 14; // reg const
-const COPY_REGISTER = 15; // dest-reg source-reg
-const BACKTRACK_ON_BACK_REFERENCE = 16; // capture-reg
-const BACKTRACK = 17;
-const SUCCEED = 18;
-const FAIL = 19;
+const BACKTRACK_IF_PREVIOUS_NO_MATCH = 8;  // constant-pool-offset
+const BACKTRACK_IF_IN_RANGE = 9;  // from to
+const BACKTRACK_IF_PREVIOUS_IN_RANGE = 10;  // from to
+const GOTO_IF_MATCH = 11;  // charCode label
+const GOTO_IF_PREVIOUS_MATCH = 12;  // charCode label
+const GOTO_IF_IN_RANGE = 13;  // from to label
+const GOTO_IF_PREVIOUS_IN_RANGE = 14;  // from to label
+const GOTO_EQ = 15; // reg reg label
+const GOTO_GE = 16; // reg reg label
+const GOTO_IF_WORD_CHARACTER = 17;  // position-offset label
+const ADD_TO_REGISTER = 18; // reg const
+const COPY_REGISTER = 19; // dest-reg source-reg
+const BACKTRACK_ON_BACK_REFERENCE = 20; // capture-reg
+const BACKTRACK_ON_BACK_REFERENCE_BACKWARDS = 21; // capture-reg
+const BACKTRACK = 22;
+const SUCCEED = 23;
+const FAIL = 24;
 
 // Format is name, number of register arguments, number of other arguments.
 const BYTE_CODE_NAMES = const [
   "GOTO", 0, 1,
   "PUSH_REGISTER", 1, 0,
   "PUSH_BACKTRACK", 0, 1,
   "POP_REGISTER", 1, 0,
   "BACKTRACK_EQ", 2, 0,
   "BACKTRACK_NE", 2, 0,
   "BACKTRACK_GT", 2, 0,
   "BACKTRACK_IF_NO_MATCH", 0, 1,
+  "BACKTRACK_IF_PREVIOUS_NO_MATCH", 0, 1,
   "BACKTRACK_IF_IN_RANGE", 0, 2,
+  "BACKTRACK_IF_PREVIOUS_IN_RANGE", 0, 2,
   "GOTO_IF_MATCH", 0, 2,
+  "GOTO_IF_PREVIOUS_MATCH", 0, 2,
   "GOTO_IF_IN_RANGE", 0, 3,
+  "GOTO_IF_PREVIOUS_IN_RANGE", 0, 3,
   "GOTO_EQ", 2, 1,
   "GOTO_GE", 2, 1,
   "GOTO_IF_WORD_CHARACTER", 0, 2,
   "ADD_TO_REGISTER", 1, 1,
   "COPY_REGISTER", 2, 0,
   "BACKTRACK_ON_BACK_REFERENCE", 1, 1,
+  "BACKTRACK_ON_BACK_REFERENCE_BACKWARDS", 1, 1,
   "BACKTRACK", 0, 0,
   "SUCCEED", 0, 0,
   "FAIL", 0, 0];
 
 const CHAR_CODE_NUL = 0;
 const CHAR_CODE_BACKSPACE = 8;
 const CHAR_CODE_TAB = 9;
 const CHAR_CODE_NEWLINE = 10;
 const CHAR_CODE_VERTICAL_TAB = 11;
 const CHAR_CODE_FORM_FEED = 12;
 const CHAR_CODE_CARRIAGE_RETURN = 13;
 const CHAR_CODE_SPACE = 32;
 const CHAR_CODE_BANG = 33;
 const CHAR_CODE_ASTERISK = 42;
 const CHAR_CODE_PLUS = 43;
 const CHAR_CODE_COMMA = 44;
 const CHAR_CODE_DASH = 45;
 const CHAR_CODE_0 = 48;
 const CHAR_CODE_7 = 55;
 const CHAR_CODE_9 = 57;
 const CHAR_CODE_COLON = 58;
+const CHAR_CODE_LESS_THAN = 60;
 const CHAR_CODE_EQUALS = 61;
 const CHAR_CODE_QUERY = 63;
 const CHAR_CODE_UPPER_A = 65;
 const CHAR_CODE_UPPER_B = 66;
 const CHAR_CODE_UPPER_D = 68;
 const CHAR_CODE_UPPER_F = 70;
 const CHAR_CODE_UPPER_S = 83;
 const CHAR_CODE_UPPER_W = 87;
 const CHAR_CODE_UPPER_Z = 90;
 const CHAR_CODE_BACKSLASH = 92;
@@ skipping 30 matching lines @@
 class MiniExpCompiler {
   final String pattern;
   final bool caseSensitive;
   final List<int> registers = new List<int>();
   int captureRegisterCount = 0;
   int firstCaptureRegister;
   final List<int> _codes = new List<int>();
   final List<int> _extraConstants = new List<int>();
   final List<BackReference> _backReferences = new List<BackReference>();
   MiniExpLabel _pendingGoto;
+  bool stepBackwards = false;
+  int get oneIfBackwards => stepBackwards ? 1 : 0;
+  int get direction => stepBackwards ? -1 : 1;
 
   MiniExpCompiler(this.pattern, this.caseSensitive) {
     for (int i = 0; i < FIXED_REGISTERS; i++) {
       registers.add(i == NO_POSITION_REGISTER ? NO_POSITION : 0);
     }
   }
 
   List<int> get codes {
     flushPendingGoto();
+    //disassemble(_codes);
     return _codes;
   }
 
   String get constantPool {
     if (_extraConstants.isEmpty) {
       return pattern;
     } else {
       return pattern + new String.fromCharCodes(_extraConstants);
     }
   }
@@ skipping 150 matching lines @@
   void addToRegister(int reg, int offset) {
     _emit(ADD_TO_REGISTER, registerNumber(reg), offset);
   }
 
   void copyRegister(int destRegister, int sourceRegister) {
     _emit(COPY_REGISTER, registerNumber(destRegister),
         registerNumber(sourceRegister));
   }
 
   void backtrackOnBackReferenceFail(int register, bool caseSensitive) {
-    _emit(BACKTRACK_ON_BACK_REFERENCE,
+    _emit(BACKTRACK_ON_BACK_REFERENCE + oneIfBackwards,
           registerNumber(register), caseSensitive ? 1 : 0);
   }
 
   void backtrackIfGreater(int register1, int register2) {
     _emit(BACKTRACK_GT, registerNumber(register1), registerNumber(register2));
   }
 
   void gotoIfGreaterEqual(int register1, int register2, MiniExpLabel label) {
     _emit(GOTO_GE, registerNumber(register1), registerNumber(register2));
     link(label);
   }
 
   void backtrackIfNoMatch(int constant_pool_offset) {
-    _emit(BACKTRACK_IF_NO_MATCH, constant_pool_offset);
+    _emit(BACKTRACK_IF_NO_MATCH + oneIfBackwards, constant_pool_offset);
   }
 
   void backtrackIfInRange(int from, int to) {
-    _emit(BACKTRACK_IF_IN_RANGE, from, to);
+    _emit(BACKTRACK_IF_IN_RANGE + oneIfBackwards, from, to);
   }
 
   void gotoIfMatches(int charCode, MiniExpLabel label) {
-    _emit(GOTO_IF_MATCH, charCode);
+    _emit(GOTO_IF_MATCH + oneIfBackwards, charCode);
     link(label);
   }
 
   void gotoIfInRange(int from, int to, MiniExpLabel label) {
     if (from == to) {
       gotoIfMatches(from, label);
     } else {
-      _emit(GOTO_IF_IN_RANGE, from, to);
+      _emit(GOTO_IF_IN_RANGE + oneIfBackwards, from, to);
       link(label);
     }
   }
 
   void backtrackIfNotAtWordBoundary() {
     MiniExpLabel non_word_on_left = new MiniExpLabel();
     MiniExpLabel word_on_left = new MiniExpLabel();
     MiniExpLabel at_word_boundary = new MiniExpLabel();
     MiniExpLabel do_backtrack = new MiniExpLabel();
 
@@ skipping 80 matching lines @@
         fixedLength = 0,
         anchored = false,
         registersToSave = null;
 
   const MiniExpAnalysis.atStart()
       : canMatchEmpty = true,
         fixedLength = 0,
         anchored = true,
         registersToSave = null;
 
-  MiniExpAnalysis.lookahead(MiniExpAnalysis bodyAnalysis, bool positive)
+  MiniExpAnalysis.lookahead(
+      MiniExpAnalysis bodyAnalysis, bool positive, bool behind)
       : canMatchEmpty = true,
         fixedLength = 0,
-        anchored = positive && bodyAnalysis.anchored,
+        anchored = positive && !behind && bodyAnalysis.anchored,
         registersToSave = bodyAnalysis.registersToSave;
 
   MiniExpAnalysis.quantifier(
       MiniExpAnalysis bodyAnalysis, int min, int max, List<int> regs)
       : canMatchEmpty = min == 0 || bodyAnalysis.canMatchEmpty,
         fixedLength = (min == 1 && max == 1) ? bodyAnalysis.fixedLength : null,
         anchored = min > 0 && bodyAnalysis.anchored,
         registersToSave = combineRegisters(bodyAnalysis.registersToSave, regs);
 
   const MiniExpAnalysis.atom()
@@ skipping 67 matching lines @@
   }
 }
 
 class Alternative extends MiniExpAst {
   final MiniExpAst _left;
   final MiniExpAst _right;
 
   Alternative(this._left, this._right);
 
   void generate(MiniExpCompiler compiler, MiniExpLabel onSuccess) {
-    compiler.generate(_left, _right.label);
-    compiler.generate(_right, onSuccess);
+    MiniExpAst first = compiler.stepBackwards ? _right : _left;
+    MiniExpAst second = compiler.stepBackwards ? _left : _right;
+
+    compiler.generate(first, second.label);
+    compiler.generate(second, onSuccess);
   }
 
   MiniExpAnalysis analyze(MiniExpCompiler compiler) {
     return new MiniExpAnalysis.and(
         _left.analyze(compiler), _right.analyze(compiler));
   }
 }
 
 abstract class Assertion extends MiniExpAst {
   MiniExpAnalysis analyze(MiniExpCompiler) => const MiniExpAnalysis.empty();
@@ skipping 67 matching lines @@
       compiler.pop(CURRENT_POSITION);
       compiler.pop(CURRENT_POSITION);
       // This overwrites the current position with the correct value.
       compiler.backtrack();
     }
   }
 }
 
 class LookAhead extends Assertion {
   final bool _positive;
+  final bool _behind;
   final MiniExpAst _body;
   List<int> _subtreeRegisters;
 
   int _savedStackPointerRegister;
   int _savedPosition;
 
-  LookAhead(this._positive, this._body, MiniExpCompiler compiler) {
+  LookAhead(
+      this._positive, this._behind, this._body, MiniExpCompiler compiler) {
     _savedStackPointerRegister = compiler.allocateWorkingRegister();
     _savedPosition = compiler.allocateWorkingRegister();
   }
 
   void generate(MiniExpCompiler compiler, MiniExpLabel onSuccess) {
     // Lookahead.  Even if the subexpression succeeds, the current position is
     // reset, and the backtracking stack is unwound so that we can never
     // backtrack into the lookahead.  On a failure of the subexpression, the
     // stack will be naturally unwound.
     MiniExpLabel body_succeeded = new MiniExpLabel();
     MiniExpLabel succeed_on_failure = new MiniExpLabel();
     MiniExpLabel undoCaptures;
     compiler.copyRegister(_savedStackPointerRegister, STACK_POINTER);
     compiler.copyRegister(_savedPosition, CURRENT_POSITION);
     if (!_positive) {
       compiler.pushBacktrack(succeed_on_failure);
     }
+    bool stepBackwards = compiler.stepBackwards;
+    compiler.stepBackwards = _behind;
     compiler.generate(_body, body_succeeded);
+    compiler.stepBackwards = stepBackwards;
 
     compiler.bind(body_succeeded);
     compiler.copyRegister(STACK_POINTER, _savedStackPointerRegister);
     compiler.copyRegister(CURRENT_POSITION, _savedPosition);
     if (!_positive) {
       // For negative lookahead always zap the captures when the body succeeds
       // and the lookahead thus fails.  The captures are only needed for any
       // backrefs inside the negative lookahead.
       if (_subtreeRegisters != null) {
         for (int register in _subtreeRegisters) {
@@ skipping 20 matching lines @@
       for (int register in _subtreeRegisters) {
         compiler.copyRegister(register, NO_POSITION_REGISTER);
       }
       compiler.backtrack();
     }
   }
 
   MiniExpAnalysis analyze(compiler) {
     MiniExpAnalysis bodyAnalysis = _body.analyze(compiler);
     _subtreeRegisters = bodyAnalysis.registersToSave;
-    return new MiniExpAnalysis.lookahead(bodyAnalysis, _positive);
+    return new MiniExpAnalysis.lookahead(bodyAnalysis, _positive, _behind);
   }
 }
 
 class Quantifier extends MiniExpAst {
   final int _min;
   final int _max;
   final bool _greedy;
   final MiniExpAst _body;
   int _counterRegister;
   int _startOfMatchRegister;  // Implements 21.2.2.5.1 note 4.
@@ skipping 72 matching lines @@
   void generateFixedLengthGreedy(
       MiniExpCompiler compiler, MiniExpLabel onSuccess) {
     MiniExpLabel newIteration = new MiniExpLabel();
     MiniExpLabel cantAdvanceMore = new MiniExpLabel();
     MiniExpLabel continuationFailed = new MiniExpLabel();
 
     // Save the current position, so we know when the quantifier has been
     // unwound enough.
     compiler.copyRegister(_optimizedGreedyRegister, CURRENT_POSITION);
     if (_min != 0) {
-      compiler.addToRegister(_optimizedGreedyRegister, _min * _bodyLength);
+      int offset = compiler.direction * _bodyLength;
+      compiler.addToRegister(_optimizedGreedyRegister, _min * offset);
     }
 
     // This backtrack doesn't trigger until the quantifier has eaten as much as
     // possible.  Unfortunately, whenever we backtrack in this simple system,
     // the old current position in the subject string is also rewound.  That's
     // not so convenient here, so we will have to save the current position in
     // a special register.  It would be faster to generate the body in a
     // special mode where we use a different backtrack instruction that just
     // rewinds the current position a certain number of characters instead of
     // popping it.
     compiler.pushBacktrack(cantAdvanceMore);
 
     // The loop.
     compiler.bind(newIteration);
     compiler.copyRegister(_savePositionRegister, CURRENT_POSITION);
     compiler.generate(_body, newIteration);
 
     // The greedy quantifier has eaten as much as it can.  Time to try the
     // continuation of the regexp after the quantifier.
     compiler.bind(cantAdvanceMore);
 
     if (_min != 0) {
-      compiler.backtrackIfGreater(
-          _optimizedGreedyRegister, _savePositionRegister);
+      if (compiler.stepBackwards) {
+        compiler.backtrackIfGreater(
+            _savePositionRegister, _optimizedGreedyRegister);
+      } else {
+        compiler.backtrackIfGreater(
+            _optimizedGreedyRegister, _savePositionRegister);
+      }
     }
 
-    compiler.addToRegister(_savePositionRegister, _bodyLength);
+    compiler.addToRegister(
+        _savePositionRegister, compiler.direction * _bodyLength);
     compiler.copyRegister(CURRENT_POSITION, _savePositionRegister);
 
     // The continuation of the regexp failed.  We backtrack the greedy
     // quantifier by one step and retry.
     compiler.bind(continuationFailed);
-    compiler.addToRegister(CURRENT_POSITION, -_bodyLength);
+    compiler.addToRegister(
+        CURRENT_POSITION, compiler.direction * -_bodyLength);
     // If we got back to where the quantifier started matching, then jump
     // to the continuation (we haven't pushed a backtrack, so if that fails, it
     // will backtrack further).
     // We don't have gotoIfEqual, so use gotoIfGreaterEqual.
-    compiler.gotoIfGreaterEqual(
-        _optimizedGreedyRegister, CURRENT_POSITION, onSuccess);
+    if (compiler.stepBackwards) {
+      compiler.gotoIfGreaterEqual(
+          CURRENT_POSITION, _optimizedGreedyRegister, onSuccess);
+    } else {
+      compiler.gotoIfGreaterEqual(
+          _optimizedGreedyRegister, CURRENT_POSITION, onSuccess);
+    }
     compiler.pushBacktrack(continuationFailed);
     compiler.goto(onSuccess);
   }
 
   void generate(MiniExpCompiler compiler, MiniExpLabel onSuccess) {
     // We optimize loops of the form .* to avoid big backtrack stacks.
     if (_isOptimizedGreedy) {
       generateFixedLengthGreedy(compiler, onSuccess);
       return;
     }
@@ skipping 94 matching lines @@
            _subtreeRegistersThatNeedSaving.isNotEmpty;
   }
 }
 
 class Atom extends MiniExpAst {
   final int _constantIndex;
 
   Atom(this._constantIndex);
 
   void generate(MiniExpCompiler compiler, MiniExpLabel onSuccess) {
-    compiler.backtrackIfEqual(CURRENT_POSITION, STRING_LENGTH);
+    if (compiler.stepBackwards) {
+      compiler.backtrackIfEqual(CURRENT_POSITION, 0);
+    } else {
+      compiler.backtrackIfEqual(CURRENT_POSITION, STRING_LENGTH);
+    }
     MiniExpLabel match;
     int charCode = compiler.constantPoolEntry(_constantIndex);
     if (!compiler.caseSensitive) {
       List<int> equivalents = internalRegExpEquivalenceClass(charCode);
       if (equivalents != null && equivalents.length > 1) {
         match = new MiniExpLabel();
         for (int equivalent in equivalents) {
           if (equivalent == charCode) continue;
           compiler.gotoIfMatches(equivalent, match);
         }
       }
     }
     compiler.backtrackIfNoMatch(_constantIndex);
     if (match != null) compiler.bind(match);
-    compiler.addToRegister(CURRENT_POSITION, 1);
+    compiler.addToRegister(CURRENT_POSITION, compiler.direction);
     compiler.goto(onSuccess);
   }
 
   MiniExpAnalysis analyze(compiler) => const MiniExpAnalysis.atom();
 }
 
 class CharClass extends MiniExpAst {
   final List<int> _ranges = new List<int>();
   final bool _positive;
 
@@ skipping 81 matching lines @@
         }
       }
       ranges.add(start);
       ranges.add(end);
     }
     // TODO(erikcorry): Sort and merge ranges.
     return ranges;
   }
 
   void generate(MiniExpCompiler compiler, MiniExpLabel onSuccess) {
-    compiler.backtrackIfEqual(CURRENT_POSITION, STRING_LENGTH);
+    if (compiler.stepBackwards) {
+      compiler.backtrackIfEqual(CURRENT_POSITION, 0);
+    } else {
+      compiler.backtrackIfEqual(CURRENT_POSITION, STRING_LENGTH);
+    }
     List<int> ranges = _ranges;
     if (!compiler.caseSensitive) {
       ranges = caseInsensitiveRanges(_ranges);
     }
     MiniExpLabel match = new MiniExpLabel();
     if (_positive) {
       for (int i = 0; i < ranges.length; i += 2) {
         compiler.gotoIfInRange(ranges[i], ranges[i + 1], match);
       }
       compiler.backtrack();
       compiler.bind(match);
     } else {
       for (int i = 0; i < ranges.length; i += 2) {
         compiler.backtrackIfInRange(ranges[i], ranges[i + 1]);
       }
     }
-    compiler.addToRegister(CURRENT_POSITION, 1);
+    compiler.addToRegister(CURRENT_POSITION, compiler.direction);
     compiler.goto(onSuccess);
   }
 
   MiniExpAnalysis analyze(compiler) => const MiniExpAnalysis.atom();
 }
 
 // This class is used for all backslashes followed by numbers.  For web
 // compatibility, if the number (interpreted as decimal) is smaller than the
 // number of captures, then it will be interpreted as a back reference.
 // Otherwise the number will be interpreted as an octal character code escape.
@@ skipping 41 matching lines @@
     if (_startRegister == null) {
       _startRegister = compiler.allocateCaptureRegisters();
       _endRegister = _startRegister - 1;
     }
   }
 
   void generate(MiniExpCompiler compiler, MiniExpLabel onSuccess) {
     MiniExpLabel undoStart = new MiniExpLabel();
     MiniExpLabel writeEnd = new MiniExpLabel();
     MiniExpLabel undoEnd = new MiniExpLabel();
-    compiler.copyRegister(_startRegister, CURRENT_POSITION);
+    int firstRegister = compiler.stepBackwards ? _endRegister : _startRegister;
+    int lastRegister = compiler.stepBackwards ? _startRegister : _endRegister;
+    compiler.copyRegister(firstRegister, CURRENT_POSITION);
     compiler.pushBacktrack(undoStart);
 
     compiler.generate(_body, writeEnd);
 
     compiler.bind(writeEnd);
-    compiler.copyRegister(_endRegister, CURRENT_POSITION);
+    compiler.copyRegister(lastRegister, CURRENT_POSITION);
     compiler.pushBacktrack(undoEnd);
     compiler.goto(onSuccess);
 
     compiler.bind(undoStart);
-    compiler.copyRegister(_startRegister, NO_POSITION_REGISTER);
+    compiler.copyRegister(firstRegister, NO_POSITION_REGISTER);
     compiler.backtrack();
 
     compiler.bind(undoEnd);
-    compiler.copyRegister(_endRegister, NO_POSITION_REGISTER);
+    compiler.copyRegister(lastRegister, NO_POSITION_REGISTER);
     compiler.backtrack();
   }
 
   MiniExpAnalysis analyze(MiniExpCompiler compiler) {
     allocateRegisters(compiler);
     MiniExpAnalysis bodyAnalysis = _body.analyze(compiler);
     return new MiniExpAnalysis.capture(
         bodyAnalysis, _startRegister, _endRegister);
   }
 }
@@ skipping 189 matching lines @@
   notWordBoundary,
   wordCharacter,
   notWordCharacter,
   digit,
   notDigit,
   whitespace,
   notWhitespace,
   nonCapturing,
   lookAhead,
   negativeLookAhead,
+  lookBehind,
+  negativeLookBehind,
   other
 }
 
 class MiniExpParser {
   // The constant pool is used to look up character data when the regexp is
   // running.  It consists of the regexp source with some characters appended
   // to handle escapes that are not literally present in the regexp input.
   final MiniExpCompiler _compiler;
   final String _source;
   final bool _isMultiLine;
@@ skipping 57 matching lines @@
 
   MiniExpAst tryParseAssertion() {
     if (acceptToken(Token.hat)) {
       return _isMultiLine ? new AtBeginningOfLine() : new AtStart();
     }
     if (acceptToken(Token.dollar)) {
       return _isMultiLine ? new AtEndOfLine() : new AtEnd();
     }
     if (acceptToken(Token.wordBoundary)) return new WordBoundary(true);
     if (acceptToken(Token.notWordBoundary)) return new WordBoundary(false);
-    var lookaheadAst;
+    var lookAst;
     if (acceptToken(Token.lookAhead)) {
-      lookaheadAst = new LookAhead(true, parseDisjunction(), _compiler);
+      lookAst = new LookAhead(true, false, parseDisjunction(), _compiler);
     } else if (acceptToken(Token.negativeLookAhead)) {
-      lookaheadAst = new LookAhead(false, parseDisjunction(), _compiler);
+      lookAst = new LookAhead(false, false, parseDisjunction(), _compiler);
+    } else if (acceptToken(Token.lookBehind)) {
+      lookAst = new LookAhead(true, true, parseDisjunction(), _compiler);
+    } else if (acceptToken(Token.negativeLookBehind)) {
+      lookAst = new LookAhead(false, true, parseDisjunction(), _compiler);
     }
-    if (lookaheadAst != null) {
+    if (lookAst != null) {
       expectToken(Token.rParen);
       // The normal syntax does not allow a quantifier here, but the web
       // compatible one does.  Slightly nasty hack for compatibility:
       if (peekToken(Token.quant)) {
         MiniExpAst quant = new Quantifier(
             _minimumRepeats, _maximumRepeats, _lastWasGreedy,
-            lookaheadAst, _compiler);
+            lookAst, _compiler);
         expectToken(Token.quant);
         return quant;
       }
-      return lookaheadAst;
+      return lookAst;
     }
     return null;
   }
 
   MiniExpAst parseTerm() {
     MiniExpAst ast = tryParseAssertion();
     if (ast == null) {
       ast = parseAtom();
       if (peekToken(Token.quant)) {
         MiniExpAst quant = new Quantifier(
@@ skipping 398 matching lines @@
     if (!_has(_position + 1)) error("unterminated group");
     if (_at(_position + 1) == CHAR_CODE_QUERY) {
       if (!_has(_position + 2)) error("unterminated group");
       int parenthesisModifier = _at(_position + 2);
       if (parenthesisModifier == CHAR_CODE_EQUALS) {
         _lastToken = Token.lookAhead;
       } else if (parenthesisModifier == CHAR_CODE_COLON) {
         _lastToken = Token.nonCapturing;
       } else if (parenthesisModifier == CHAR_CODE_BANG) {
         _lastToken = Token.negativeLookAhead;
+      } else if (parenthesisModifier == CHAR_CODE_LESS_THAN) {
+        if (!_has(_position + 3)) error("unterminated group");
+        int lookBehindModifier = _at(_position + 3);
+        _position++;
+        if (lookBehindModifier == CHAR_CODE_EQUALS) {
+          _lastToken = Token.lookBehind;
+        } else if (lookBehindModifier == CHAR_CODE_BANG) {
+          _lastToken = Token.negativeLookBehind;
+        } else {
+          error("invalid group");
+        }
       } else {
         error("invalid group");
       }
       _position += 2;
       return;
     }
   }
 
   void lexQuantifier() {
     int quantifierCode = _at(_position);
@@ skipping 158 matching lines @@
           break;
         case BACKTRACK_GT:
           int reg1 = _registers[_byteCodes[programCounter++]];
           int reg2 = _registers[_byteCodes[programCounter++]];
           if (reg1 > reg2) {
             _registers[CURRENT_POSITION] = stack[--stackPointer];
             programCounter = stack[--stackPointer];
           }
           break;
         case BACKTRACK_IF_NO_MATCH:
-          if (subject.codeUnitAt(_registers[CURRENT_POSITION]) !=
+        case BACKTRACK_IF_PREVIOUS_NO_MATCH:
+          int offset = byteCode - BACKTRACK_IF_NO_MATCH;
+          if (subject.codeUnitAt(_registers[CURRENT_POSITION] - offset) !=
               _constantPool.codeUnitAt(_byteCodes[programCounter++])) {
             _registers[CURRENT_POSITION] = stack[--stackPointer];
             programCounter = stack[--stackPointer];
           }
           break;
         case BACKTRACK_IF_IN_RANGE:
-          int code = subject.codeUnitAt(_registers[CURRENT_POSITION]);
+        case BACKTRACK_IF_PREVIOUS_IN_RANGE:
+          int offset = byteCode - BACKTRACK_IF_IN_RANGE;
+          int code = subject.codeUnitAt(_registers[CURRENT_POSITION] - offset);
           int from = _byteCodes[programCounter++];
           int to = _byteCodes[programCounter++];
           if (from <= code && code <= to) {
             _registers[CURRENT_POSITION] = stack[--stackPointer];
             programCounter = stack[--stackPointer];
           }
           break;
         case GOTO_IF_MATCH:
-          int code = subject.codeUnitAt(_registers[CURRENT_POSITION]);
+        case GOTO_IF_PREVIOUS_MATCH:
+          int offset = byteCode - GOTO_IF_MATCH;
+          int code = subject.codeUnitAt(_registers[CURRENT_POSITION] - offset);
           int expected = _byteCodes[programCounter++];
           int dest = _byteCodes[programCounter++];
           if (code == expected) programCounter = dest;
           break;
         case GOTO_IF_IN_RANGE:
-          int code = subject.codeUnitAt(_registers[CURRENT_POSITION]);
+        case GOTO_IF_PREVIOUS_IN_RANGE:
+          int offset = byteCode - GOTO_IF_IN_RANGE;
+          int code = subject.codeUnitAt(_registers[CURRENT_POSITION] - offset);
           int from = _byteCodes[programCounter++];
           int to = _byteCodes[programCounter++];
           int dest = _byteCodes[programCounter++];
           if (from <= code && code <= to) programCounter = dest;
           break;
         case GOTO_EQ:
           int reg1 = _registers[_byteCodes[programCounter++]];
           int reg2 = _registers[_byteCodes[programCounter++]];
           int dest = _byteCodes[programCounter++];
           if (reg1 == reg2) programCounter = dest;
@@ skipping 31 matching lines @@
         case COPY_REGISTER:
           // We don't normally keep the stack pointer in sync with its slot in
           // the _registers, but we have to have it in sync here.
           _registers[STACK_POINTER] = stackPointer;
           int registerIndex = _byteCodes[programCounter++];
           int value = _registers[_byteCodes[programCounter++]];
           _registers[registerIndex] = value;
           stackPointer = _registers[STACK_POINTER];
           break;
         case BACKTRACK_ON_BACK_REFERENCE:
+        case BACKTRACK_ON_BACK_REFERENCE_BACKWARDS:
           int registerIndex = _byteCodes[programCounter++];
           bool case_sensitive = _byteCodes[programCounter++] != 0;
-          if (!checkBackReference(subject, case_sensitive, registerIndex)) {
+          if (!checkBackReference(
+                subject, case_sensitive, registerIndex,
+                byteCode == BACKTRACK_ON_BACK_REFERENCE_BACKWARDS)) {
             // Backtrack.
             _registers[CURRENT_POSITION] = stack[--stackPointer];
             programCounter = stack[--stackPointer];
           }
           break;
         case BACKTRACK:
           _registers[CURRENT_POSITION] = stack[--stackPointer];
           programCounter = stack[--stackPointer];
           break;
         case SUCCEED:
           return true;
         case FAIL:
           return false;
         default:
           assert(false);
           break;
       }
     }
   }
 
   bool checkBackReference(
-      String subject, bool caseSensitive, int registerIndex) {
+      String subject, bool caseSensitive, int registerIndex, bool backwards) {
     int start = _registers[registerIndex];
     int end = _registers[registerIndex + 1];
     if (end == NO_POSITION) return true;
     int length = end - start;
     int currentPosition = _registers[CURRENT_POSITION];
-    if (currentPosition + end - start > subject.length) return false;
+    if (backwards) {
+      if (currentPosition < length) return false;
+      currentPosition -= length;
+    } else {
+      if (currentPosition + length > subject.length) return false;
+    }
     for (int i = 0; i < length; i++) {
       int x = subject.codeUnitAt(start + i);
       int y = subject.codeUnitAt(currentPosition + i);
       if (!caseSensitive) {
         x = internalRegExpCanonicalize(x);
         y = internalRegExpCanonicalize(y);
       }
       if (x != y) return false;
     }
-    _registers[CURRENT_POSITION] += length;
+    _registers[CURRENT_POSITION] += backwards ? -length : length;
     return true;
   }
 }