context: //
  // assembly:	System
  // namespace:	System.Text.RegularExpressions
  // file:	interpreter.cs
  //
  // author:	Dan Lewis (dlewis@gmx.co.uk)
  // 		(c) 2002
  
  //
  // Permission is hereby granted, free of charge, to any person obtaining
  // a copy of this software and associated documentation files (the
  // "Software"), to deal in the Software without restriction, including
  // without limitation the rights to use, copy, modify, merge, publish,
  // distribute, sublicense, and/or sell copies of the Software, and to
  // permit persons to whom the Software is furnished to do so, subject to
  // the following conditions:
  // 
  // The above copyright notice and this permission notice shall be
  // included in all copies or substantial portions of the Software.
  // 
  // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  //
  
  using System;
  using System.Collections;
  using System.Diagnostics;
  using System.Globalization;
  
  namespace System.Text.RegularExpressions {
  
  	partial class Interpreter : BaseMachine {
  		private int ReadProgramCount (int ptr)
  		{
  			int ret = program [ptr + 1];
  			ret <<= 16;
  			ret += program [ptr];
  			return ret;
  		}
  
  		public Interpreter (ushort[] program) {
  			this.program = program;
  			this.qs = null;
  
  			// process info block
  			Debug.Assert ((OpCode)program[0] == OpCode.Info, "Regex", "Cant' find info block");
  			this.group_count = ReadProgramCount (1) + 1;
  			this.match_min = ReadProgramCount (3);
  			//this.match_max = ReadProgramCount (5);
  
  			// setup
  
  			this.program_start = 7;
  			this.groups = new int [group_count];
  		}
  
  		// IMachine implementation
  
  		public override Match Scan (Regex regex, string text, int start, int end) {
  			this.text = text;
  			this.text_end = end;
  			this.scan_ptr = start;
  
  			if (Eval (Mode.Match, ref scan_ptr, program_start))
  				return GenerateMatch (regex);
  
  			return Match.Empty;
  		}
  
  		// private methods
  
  		private void Reset () {
  			ResetGroups ();
  			fast = repeat = null;
  		}
  
  		private bool Eval (Mode mode, ref int ref_ptr, int pc) {
  			int ptr = ref_ptr;
  		Begin:
  			for (;;) {
  				ushort word = program[pc];
  				OpCode op = (OpCode)(word & 0x00ff);
  				OpFlags flags = (OpFlags)(word & 0xff00);
  
  				switch (op) {
  				case OpCode.Anchor: {
  					int skip = program[pc + 1];
  					
  					int anch_offset = program[pc + 2];
  					bool anch_reverse = (flags & OpFlags.RightToLeft) != 0;	
  					int anch_ptr = anch_reverse ?  ptr - anch_offset  : ptr + anch_offset;
  					int anch_end = text_end - match_min + anch_offset;	// maximum anchor position  
  					
  					
  					int anch_begin =  0;
  
  
  					// the general case for an anchoring expression is at the bottom, however we
  					// do some checks for the common cases before to save processing time. the current
  					// optimizer only outputs three types of anchoring expressions: fixed position,
  					// fixed substring, and no anchor.
  
  					OpCode anch_op = (OpCode)(program[pc + 3] & 0x00ff);					
  					if (anch_op == OpCode.Position && skip == 6) {				// position anchor
  						// Anchor
  						// 	Position
  						//	True
  
  						switch ((Position)program[pc + 4]) {
  						case Position.StartOfString:
  							if (anch_reverse || anch_offset == 0) {
  								if (anch_reverse)
  									ptr = anch_offset;
  								if (TryMatch (ref ptr, pc + skip))
  									goto Pass;
  							}
  							break;
  						
  						case Position.StartOfLine:
  							 if (anch_ptr == 0) {
  								ptr = 0;
  								if (TryMatch (ref ptr, pc + skip))
  									goto Pass;
  								
  								++ anch_ptr;
  							}
  
  							while ((anch_reverse && anch_ptr >= 0) || (!anch_reverse && anch_ptr <= anch_end)) {  
  								if (anch_ptr == 0 || text[anch_ptr - 1] == '\n') {
  									if (anch_reverse)
  										ptr = anch_ptr == anch_end ? anch_ptr : anch_ptr + anch_offset;
  									else
  										ptr = anch_ptr == 0 ? anch_ptr : anch_ptr - anch_offset;
  									if (TryMatch (ref ptr, pc + skip))
  										goto Pass;
  								}
  							
  								if (anch_reverse)
  									-- anch_ptr;
  								else
  									++ anch_ptr;
  							}
  							break;
  						
  						case Position.StartOfScan:
  							if (anch_ptr == scan_ptr) {							
  								ptr = anch_reverse ? scan_ptr + anch_offset : scan_ptr - anch_offset;
  								if (TryMatch (ref ptr, pc + skip))
  									goto Pass;
  							}
  							break;
  
  						default:
  							// FIXME
  							break;
  						}
  					}
  					else if (qs != null ||
  						(anch_op == OpCode.String && skip == 6 + program[pc + 4])) {	// substring anchor
  						// Anchor
  						//	String
  						//	True
  				 
  						bool reverse = ((OpFlags)program[pc + 3] & OpFlags.RightToLeft) != 0;
  
  						if (qs == null) {
  							bool ignore = ((OpFlags)program[pc + 3] & OpFlags.IgnoreCase) != 0;
  							string substring = GetString (pc + 3);
  							qs = new QuickSearch (substring, ignore, reverse);
  						}
  						while ((anch_reverse && anch_ptr >= anch_begin) 
  						       || (!anch_reverse && anch_ptr <= anch_end)) {
  
  							if (reverse) 	
  							{
  								anch_ptr = qs.Search (text, anch_ptr, anch_begin);
  								if (anch_ptr != -1)
  									anch_ptr += qs.Length ;
  								
  							}
  							else
  								anch_ptr = qs.Search (text, anch_ptr, anch_end);
  							if (anch_ptr < 0)
  								break;
  
  							ptr = reverse ? anch_ptr + anch_offset : anch_ptr - anch_offset;
  							if (TryMatch (ref ptr, pc + skip))
  								goto Pass;
  
  							if (reverse)
  								anch_ptr -= 2;
  							else 
  								++ anch_ptr;
  						}
  					}
  					else if (anch_op == OpCode.True) {					// no anchor
  						// Anchor
  						//	True
  
  					
  						while ((anch_reverse && anch_ptr >= anch_begin) 
  						       || (!anch_reverse && anch_ptr <= anch_end)) {
  
  							ptr = anch_ptr;
  							if (TryMatch (ref ptr, pc + skip))
  								goto Pass;
  							if (anch_reverse)
  								-- anch_ptr;
  							else 
  								++ anch_ptr;
  						}
  					}
  					else {									// general case
  						// Anchor
  						//	<expr>
  						//	True
  
  						while ((anch_reverse && anch_ptr >= anch_begin) 
  						       || (!anch_reverse && anch_ptr <= anch_end)) {
  
  							ptr = anch_ptr;
  							if (Eval (Mode.Match, ref ptr, pc + 3)) {
  								// anchor expression passed: try real expression at the correct offset
  
  								ptr = anch_reverse ? anch_ptr + anch_offset : anch_ptr - anch_offset;
  								if (TryMatch (ref ptr, pc + skip))
  									goto Pass;
  							}
  
  						    if (anch_reverse)
  								-- anch_ptr;
  							else 
  								++ anch_ptr;
  						}
  					}
  
  					goto Fail;
  				}
  				
  				case OpCode.False: {
  					goto Fail;
  				}
  
  				case OpCode.True: {
  					goto Pass;
  				}
  
  				case OpCode.Position: {
  					if (!IsPosition ((Position)program[pc + 1], ptr))
  						goto Fail;
  					pc += 2;
  					break;
  				}
  
  				case OpCode.String: {
  					bool reverse = (flags & OpFlags.RightToLeft) != 0;
  					bool ignore = (flags & OpFlags.IgnoreCase) != 0;
  					int len = program[pc + 1];
  
  					if (reverse) {
  						ptr -= len;
  						if (ptr < 0)
  							goto Fail;
  					}
  					else 
  
gt: 					if (ptr + len > text_end)