context: //
  // assembly:	System
  // namespace:	System.Text.RegularExpressions
  // file:	syntax.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;
  
  namespace System.Text.RegularExpressions.Syntax {
  	// collection classes
  
  	class ExpressionCollection : CollectionBase {
  		public void Add (Expression e) {
  			List.Add (e);
  		}
  
  		public Expression this[int i] {
  			get { return (Expression)List[i]; }
  			set { List[i] = value; }
  		}
  
  		protected override void OnValidate (object o) {
  			// allow null elements
  		}
  	}
  
  	// abstract classes
  
  	abstract class Expression {
  		public abstract void Compile (ICompiler cmp, bool reverse);
  		public abstract void GetWidth (out int min, out int max);
  
  		public int GetFixedWidth () {
  			int min, max;
  			GetWidth (out min, out max);
  
  			if (min == max)
  				return min;
  
  			return -1;
  		}
  
  		public virtual AnchorInfo GetAnchorInfo (bool reverse) {
  			return new AnchorInfo (this, GetFixedWidth ());
  		}
  
  		public abstract bool IsComplex ();
  	}
  
  	// composite expressions
  
  	abstract class CompositeExpression : Expression {
  		public CompositeExpression () {
  			expressions = new ExpressionCollection ();
  		}
  
  		protected ExpressionCollection Expressions {
  			get { return expressions; }
  		}
  
  		protected void GetWidth (out int min, out int max, int count) {
  			min = Int32.MaxValue;
  			max = 0;
  			bool empty = true;
  
  			for (int i = 0; i < count; ++ i) {
  				Expression e = Expressions[i];
  				if (e == null)
  					continue;
  
  				empty = false;
  				int a, b;
  				e.GetWidth (out a, out b);
  				if (a < min) min = a;
  				if (b > max) max = b;
  			}
  
  			if (empty)
  				min = max = 0;
  		}
  
  
  		public override bool IsComplex ()
  		{
  			foreach (Expression e in Expressions) {
  				if (e.IsComplex ())
  					return true;
  			}
  			return GetFixedWidth () <= 0;
  		}
  
  		private ExpressionCollection expressions;
  	}
  
  	// groups
  
  	class Group : CompositeExpression {
  		public Group () {
  		}
  
  		public Expression Expression {
  			get { return Expressions[0]; }
  			set { Expressions[0] = value; }
  		}
  
  		public void AppendExpression (Expression e) {
  			Expressions.Add (e);
  		}
  
  		public override void Compile (ICompiler cmp, bool reverse) {
  			int count = Expressions.Count;
  			for (int i = 0; i < count; ++ i) {
  				Expression e;
  				if (reverse)
  					e = Expressions[count - i - 1];
  				else
  					e = Expressions[i];
  
  				e.Compile (cmp, reverse);
  			}
  		}
  
  		public override void GetWidth (out int min, out int max) {
  			min = 0;
  			max = 0;
  
  			foreach (Expression e in Expressions) {
  				int a, b;
  				e.GetWidth (out a, out b);
  				min += a;
  				if (max == Int32.MaxValue || b == Int32.MaxValue)
  					max = Int32.MaxValue;
  				else
  					max += b;
  			}
  		}
  
  		public override AnchorInfo GetAnchorInfo (bool reverse)
  		{
  			int ptr;
  			int width = GetFixedWidth ();
  
  			ArrayList infos = new ArrayList ();
  			IntervalCollection segments = new IntervalCollection ();
  
  			// accumulate segments
  			ptr = 0;
  			int count = Expressions.Count;
  			for (int i = 0; i < count; ++ i) {
  				Expression e;
  				if (reverse)
  					e = Expressions [count - i - 1];
  				else
  					e = Expressions [i];
  
  				AnchorInfo info = e.GetAnchorInfo (reverse);
  				infos.Add (info);
  
  				if (info.IsPosition)
  					return new AnchorInfo (this, ptr + info.Offset, width, info.Position);
  
  				if (info.IsSubstring)
  					segments.Add (info.GetInterval (ptr));
  
  				if (info.IsUnknownWidth)
  					break;
  
  				ptr += info.Width;
  			}
  
  			// normalize and find the longest segment
  			segments.Normalize ();
  
  			Interval longest = Interval.Empty;
  			foreach (Interval segment in segments) {
  				if (segment.Size > longest.Size)
  					longest = segment;
  			}
  
  			if (longest.IsEmpty)
  				return new AnchorInfo (this, width);
  
  			// now chain the substrings that made this segment together
  			bool ignore = false;
  			int n_strings = 0;
  
  			ptr = 0;
  			for (int i = 0; i < infos.Count; ++i) {
  				AnchorInfo info = (AnchorInfo) infos [i];
  
  				if (info.IsSubstring && longest.Contains (info.GetInterval (ptr))) {
  					ignore |= info.IgnoreCase;
  					infos [n_strings ++] = info;
  				}
  
  				if (info.IsUnknownWidth)
  					break;
  
  				ptr += info.Width;
  			}
  
  			StringBuilder sb = new StringBuilder ();
  			for (int i = 0; i < n_strings; ++i) {
  				AnchorInfo info;
  				if (reverse)
  					info = (AnchorInfo) infos [n_strings - i - 1];
  				else
  					info = (AnchorInfo) infos [i];
  				sb.Append (info.Substring);
  			}
  
  			if (sb.Length == longest.Size)
  				return new AnchorInfo (this, longest.low, width, sb.ToString (), ignore);
  			// were the string segments overlapping?
  			if (sb.Length > longest.Size) {
  				Console.Error.WriteLine ("overlapping?");
  				return new AnchorInfo (this, width);
  			}
  			throw new SystemException ("Shouldn't happen");
  		}
  	}
  
  	class RegularExpression : Group {
  		public RegularExpression () {
  			group_count = 0;
  		}
  
  		public int GroupCount {
  			get { return group_count; }
  			set { group_count = value; }
  		}
  
  		public override void Compile (ICompiler cmp, bool reverse) {
  			// info block
  
  			int min, max;
  			GetWidth (out min, out max);
  			cmp.EmitInfo (group_count, min, max);
  
  			// anchoring expression
  
  			AnchorInfo info = GetAnchorInfo (reverse);
  			//if (reverse)
  			//	info = new AnchorInfo (this, GetFixedWidth ());	// FIXME
  
  			LinkRef pattern = cmp.NewLink ();
  			cmp.EmitAnchor (reverse, info.Offset, pattern);
  
  			if (info.IsPosition)
  				cmp.EmitPosition (info.Position);
  			else if (info.IsSubstring)
  				cmp.EmitString (info.Substring, info.IgnoreCase, reverse);
  
  			cmp.EmitTrue ();
  
  			// pattern
  
  			cmp.ResolveLink (pattern);
  			base.Compile (cmp, reverse);
  			cmp.EmitTrue ();
  		}
  
  		private int group_count;
  	}
  
  	class CapturingGroup : Group, IComparable {
  		public CapturingGroup () {
  			this.gid = 0;
  			this.name = null;
  		}
  
  		public int Index {
  			get { return gid; }
  			set { gid = value; }
  		}
  
  		public string Name {
  			get { return name; }
  			set { name = value; }
  		}
  
  		public bool IsNamed {
  			get { return name != null; }
  		}
  
  		public override void Compile (ICompiler cmp, bool reverse) {
  			cmp.EmitOpen (gid);
  			base.Compile (cmp, reverse);
  			cmp.EmitClose (gid);
  		}
  
  		public override bool IsComplex () {
  			return true;
  		}
  
  		public int CompareTo (object other)
  		{
  			return gid - ((CapturingGroup) other).gid;
  		}
  
  		private int gid;
  		private string name;
  	}
  
  	class BalancingGroup : CapturingGroup {
  		public BalancingGroup () {
  			this.balance = null;
  		}
  
  		public CapturingGroup Balance {
  			get { return balance; }
  			set { balance = value; }
  		}
  
  		public override void Compile (ICompiler cmp, bool reverse) {
  			// can't invoke Group.Compile from here :(
  			// so I'll just repeat the code
  
  			LinkRef tail = cmp.NewLink ();
  
  			cmp.EmitBalanceStart (this.Index, balance.Index, this.IsNamed,  tail);
  
  			int count = Expressions.Count;
  			for (int i = 0; i < count; ++ i) {
  				Expression e;
  				if (reverse)
  					e = Expressions[count - i - 1];
  				else
  					e = Expressions[i];
  
  				e.Compile (cmp, reverse);
  			}
  
  			cmp.EmitBalance ();
  			cmp.ResolveLink(tail);
  		}
  
  		private CapturingGroup balance;
  	}
  
  	class NonBacktrackingGroup : Group {
  		public NonBacktrackingGroup () {
  		}
  
  		public override void Compile (ICompiler cmp, bool reverse) {
  			LinkRef tail = cmp.NewLink ();
  
  			cmp.EmitSub (tail);
  			base.Compile (cmp, reverse);
  			cmp.EmitTrue ();
  			cmp.ResolveLink (tail);
  		}
  
  		public override bool IsComplex () {
  			return true;
  		}
  	}
  
  	// repetition
  
  	class Repetition : CompositeExpression {
  		public Repetition (int min, int max, bool lazy) {
  			Expressions.Add (null);
  
  			this.min = min;
  			this.max = max;
  			this.lazy = lazy;
  		}
  
  		public Expression Expression {
  			get { return Expressions[0]; }
  			set { Expressions[0] = value; }
  		}
  
  		public int Minimum {
  			get { return min; }
  			set { min = value; }
  		}
  
  		public int Maximum {
  			get { return max; }
  			set { max = value; }
  		}
  
  		public bool Lazy {
  			get { return lazy; }
  			set { lazy = value; }
  		}
  
  		public override void Compile (ICompiler cmp, bool reverse) {
  			if (Expression.IsComplex ()) {
  				LinkRef until = cmp.NewLink ();
  
  				cmp.EmitRepeat (min, max, lazy, until);
  				Expression.Compile (cmp, reverse);
  				cmp.EmitUntil (until);
  			}
  			else {
  				LinkRef tail = cmp.NewLink ();
  
  				cmp.EmitFastRepeat (min, max, lazy, tail);
  				Expression.Compile (cmp, reverse);
  				cmp.EmitTrue ();
  				cmp.ResolveLink (tail);
  			}
  		}
  
  		public override void GetWidth (out int min, out int max) {
  			Expression.GetWidth (out min, out max);
  			min = min * this.min;
  			if (max == Int32.MaxValue || this.max == 0xffff)
  				max = Int32.MaxValue;
  			else
  				max = max * this.max;
  		}
  
  		public override AnchorInfo GetAnchorInfo (bool reverse) {
  			int width = GetFixedWidth ();
  			if (Minimum == 0)
  				return new AnchorInfo (this, width);
  
  			AnchorInfo info = Expression.GetAnchorInfo (reverse);
  			if (info.IsPosition)
  				return new AnchorInfo (this, info.Offset, width, info.Position);
  
  			if (info.IsSubstring) {
  				if (info.IsComplete) {
  					// Minimum > 0
  					string str = info.Substring;
  					StringBuilder sb = new StringBuilder (str);
  					for (int i = 1; i < Minimum; ++ i)
  						sb.Append (str);
  
  					return new AnchorInfo (this, 0, width, sb.ToString (), info.IgnoreCase);
  				}
  
  				return new AnchorInfo (this, info.Offset, width, info.Substring, info.IgnoreCase);
  			}
  
  			return new AnchorInfo (this, width);
  		}
  
  		private int min, max;
  		private bool lazy;
  	}
  
  	// assertions
  
  	abstract class Assertion : CompositeExpression {
  		public Assertion () {
  			Expressions.Add (null);		// true expression
  			Expressions.Add (null);		// false expression
  		}
  
  		public Expression TrueExpression {
  			get { return Expressions[0]; }
  			set { Expressions[0] = value; }
  		}
  
  		public Expression FalseExpression {
  			get { return Expressions[1]; }
  			set { Expressions[1] = value; }
  		}
  
  		public override void GetWidth (out int min, out int max) {
  			GetWidth (out min, out max, 2);
  
  			if (TrueExpression == null || FalseExpression == null)
  				min = 0;
  		}
  	}
  
  	class CaptureAssertion : Assertion {
  		public CaptureAssertion (Literal l) {
  			literal = l;
  		}
  
  		public CapturingGroup CapturingGroup {
  			get { return group; }
  			set { group = value; }
  		}
  
  		public override void Compile (ICompiler cmp, bool reverse) {
  			if (group == null) {
  				Alternate.Compile (cmp, reverse);
  				return;
  			}
  
  			int gid = group.Index;
  			LinkRef tail = cmp.NewLink ();
  
  			if (FalseExpression == null) {
  				//    IfDefined :1
  				//      <yes_exp>
  				// 1: <tail>
  
  				cmp.EmitIfDefined (gid, tail);
  				TrueExpression.Compile (cmp, reverse);
  			}
  			else {
  				//    IfDefined :1
  				//      <yes_expr>
  				//      Jump :2
  				// 1:   <no_expr>
  				// 2: <tail>
  
  				LinkRef false_expr = cmp.NewLink ();
  				cmp.EmitIfDefined (gid, false_expr);
  				TrueExpression.Compile (cmp, reverse);
  				cmp.EmitJump (tail);
  				cmp.ResolveLink (false_expr);
  				FalseExpression.Compile (cmp, reverse);
  			}
  
  			cmp.ResolveLink (tail);
  		}
  
  		public override bool IsComplex () {
  			if (group == null)
  				return Alternate.IsComplex ();
  			if (TrueExpression != null && TrueExpression.IsComplex ())
  				return true;
  			if (FalseExpression != null && FalseExpression.IsComplex ())
  				return true;
  			return GetFixedWidth () <= 0;
  		}
  
  		ExpressionAssertion Alternate {
  			get {
  				if (alternate == null) {
  					alternate = new ExpressionAssertion ();
  					alternate.TrueExpression = TrueExpression;
  					alternate.FalseExpression = FalseExpression;
  					alternate.TestExpression = literal;
  				}
  				return alternate;
  			}
  		}
  
  		private ExpressionAssertion alternate;
  		private CapturingGroup group;
  		private Literal literal;
  	}
  
  	class ExpressionAssertion : Assertion {
  		public ExpressionAssertion () {
  			Expressions.Add (null);		// test expression
  		}
  
  		public bool Reverse {
  			get { return reverse; }
  			set { reverse = value; }
  		}
  
  		public bool Negate {
  
gt: 			get { return negate; }