syntax.cs

来自「没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没的 没」· CS 代码 · 共 977 行 · 第 1/2 页

//
// assembly:	System
// namespace:	System.Text.RegularExpressions
// file:	syntax.cs
//
// author:	Dan Lewis ([e-mail])
// 		(c) 2002

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 () {
			return new AnchorInfo (this, GetFixedWidth ());
		}

		public virtual bool IsComplex () {
			return true;
		}
	}

	// 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;
		}

		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 () {
			int ptr;
			int width = GetFixedWidth ();

			ArrayList infos = new ArrayList ();
			IntervalCollection segments = new IntervalCollection ();

			// accumulate segments

			ptr = 0;
			foreach (Expression e in Expressions) {
				AnchorInfo info = e.GetAnchorInfo ();
				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;
			}

			// now chain the substrings that made this segment together

			if (!longest.IsEmpty) {
				string str = "";
				bool ignore = false;

				ptr = 0;
				foreach (AnchorInfo info in infos) {
					if (info.IsSubstring && longest.Contains (info.GetInterval (ptr))) {
						str += info.Substring;	// TODO mark subexpressions
						ignore |= info.IgnoreCase;
					}

					if (info.IsUnknownWidth)
						break;

					ptr += info.Width;
				}

				return new AnchorInfo (this, longest.low, width, str, ignore);
			}

			return new AnchorInfo (this, width);
		}

		public override bool IsComplex () {
			bool comp = false;
			foreach (Expression e in Expressions) {
				comp |= e.IsComplex ();
			}

			return comp | GetFixedWidth () <= 0;
		}
	}

	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 ();
			if (reverse)
				info = new AnchorInfo (this, GetFixedWidth ());	// FIXME

			LinkRef pattern = cmp.NewLink ();
			cmp.EmitAnchor (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 {
		public CapturingGroup () {
			this.gid = 0;
			this.name = null;
		}

		public int Number {
			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;
		}

		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
		
			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 (this.Number, balance.Number);
		}

		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 () {
			int width = GetFixedWidth ();
			if (Minimum == 0)
				return new AnchorInfo (this, width);
			
			AnchorInfo info = Expression.GetAnchorInfo ();
			if (info.IsPosition)
				return new AnchorInfo (this, info.Offset, width, info.Position);
			
			if (info.IsSubstring) {
				if (info.IsComplete) {
					string str = "";
					for (int i = 0; i < Minimum; ++ i)
						str += info.Substring;

					return new AnchorInfo (this, 0, width, str, 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 () {
		}

		public CapturingGroup CapturingGroup {
			get { return group; }
			set { group = value; }
		}

		public override void Compile (ICompiler cmp, bool reverse) {
			int gid = group.Number;
			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 () {
			bool comp = false;
			if (TrueExpression != null)
				comp |= TrueExpression.IsComplex ();
			if (FalseExpression != null)
				comp |= FalseExpression.IsComplex ();

			return comp | GetFixedWidth () <= 0;
		}