syntax.cs

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

		private CapturingGroup group;
	}

	class ExpressionAssertion : Assertion {
		public ExpressionAssertion () {
			Expressions.Add (null);		// test expression
		}

		public bool Reverse {
			get { return reverse; }
			set { reverse = value; }
		}

		public bool Negate {
			get { return negate; }
			set { negate = value; }
		}

		public Expression TestExpression {
			get { return Expressions[2]; }
			set { Expressions[2] = value; }
		}

		public override void Compile (ICompiler cmp, bool reverse) {
			LinkRef true_expr = cmp.NewLink ();
			LinkRef false_expr = cmp.NewLink ();

			// test op: positive / negative

			if (!negate)
				cmp.EmitTest (true_expr, false_expr);
			else
				cmp.EmitTest (false_expr, true_expr);
			
			// test expression: lookahead / lookbehind

			TestExpression.Compile (cmp, reverse ^ this.reverse);
			cmp.EmitTrue ();

			// target expressions

			if (TrueExpression == null) {			// (?= ...)
				//    Test :1, :2
				//      <test_expr>
				// :2   False
				// :1   <tail>
			
				cmp.ResolveLink (false_expr);
				cmp.EmitFalse ();
				cmp.ResolveLink (true_expr);
			}
			else {
				cmp.ResolveLink (true_expr);
				TrueExpression.Compile (cmp, reverse);
				
				if (FalseExpression == null) {		// (?(...) ...)
					//    Test :1, :2
					//      <test_expr>
					// :1   <yes_expr>
					// :2   <tail>

					cmp.ResolveLink (false_expr);
				}
				else {					// (?(...) ... | ...)
					//    Test :1, :2
					//      <test_expr>
					// :1   <yes_expr>
					//      Jump :3
					// :2   <no_expr>
					// :3   <tail>
				
					LinkRef tail = cmp.NewLink ();
				
					cmp.EmitJump (tail);
					cmp.ResolveLink (false_expr);
					FalseExpression.Compile (cmp, reverse);
					cmp.ResolveLink (tail);
				}
			}
		}

		private bool reverse, negate;
	}

	// alternation

	class Alternation : CompositeExpression {
		public Alternation () {
		}

		public ExpressionCollection Alternatives {
			get { return Expressions; }
		}

		public void AddAlternative (Expression e) {
			Alternatives.Add (e);
		}

		public override void Compile (ICompiler cmp, bool reverse) {
			LinkRef next = cmp.NewLink ();
			LinkRef tail = cmp.NewLink ();
		
			foreach (Expression e in Alternatives) {
				cmp.EmitBranch (next);
				e.Compile (cmp, reverse);
				cmp.EmitJump (tail);
				cmp.ResolveLink (next);
			}

			cmp.EmitFalse ();
			cmp.ResolveLink (tail);
		}

		public override void GetWidth (out int min, out int max) {
			GetWidth (out min, out max, Alternatives.Count);
		}

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

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

	// terminal expressions

	class Literal : Expression {
		public Literal (string str, bool ignore) {
			this.str = str;
			this.ignore = ignore;
		}

		public string String {
			get { return str; }
			set { str = value; }
		}

		public bool IgnoreCase {
			get { return ignore; }
			set { ignore = value; }
		}

		public override void Compile (ICompiler cmp, bool reverse) {
			if (str.Length == 0)
				return;

			if (str.Length == 1)
				cmp.EmitCharacter (str[0], false, ignore, reverse);
			else
				cmp.EmitString (str, ignore, reverse);
		}

		public override void GetWidth (out int min, out int max) {
			min = max = str.Length;
		}

		public override AnchorInfo GetAnchorInfo () {
			return new AnchorInfo (this, 0, str.Length, str, ignore);
		}

		public override bool IsComplex () {
			return false;
		}

		private string str;
		private bool ignore;
	}

	class PositionAssertion : Expression {
		public PositionAssertion (Position pos) {
			this.pos = pos;
		}

		public Position Position {
			get { return pos; }
			set { pos = value; }
		}

		public override void Compile (ICompiler cmp, bool reverse) {
			cmp.EmitPosition (pos);
		}

		public override void GetWidth (out int min, out int max) {
			min = max = 0;
		}

		public override bool IsComplex () {
			return false;
		}

		public override AnchorInfo GetAnchorInfo () {
			switch (pos) {
			case Position.StartOfString: case Position.StartOfLine: case Position.StartOfScan:
				return new AnchorInfo (this, 0, 0, pos);

			default:
				return new AnchorInfo (this, 0);
			}
		}

		private Position pos;
	}

	class Reference : Expression {
		public Reference (bool ignore) {
			this.ignore = ignore;
		}

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

		public bool IgnoreCase {
			get { return ignore; }
			set { ignore = value; }
		}

		public override void Compile (ICompiler cmp, bool reverse) {
			cmp.EmitReference (group.Number, ignore, reverse);
		}

		public override void GetWidth (out int min, out int max) {
			//group.GetWidth (out min, out max);
			// TODO set width to referenced group for non-cyclical references
			min = 0;
			max = Int32.MaxValue;
		}

		public override bool IsComplex () {
			return true;	// FIXME incorporate cyclic check
		}

		private CapturingGroup group;
		private bool ignore;
	}

	class CharacterClass : Expression {
		public CharacterClass (bool negate, bool ignore) {
			this.negate = negate;
			this.ignore = ignore;

			intervals = new IntervalCollection ();

			// initialize pos/neg category arrays

			Array cat_values = Enum.GetValues (typeof (Category));
			int cat_size = (int)(Category)cat_values.GetValue (cat_values.Length - 1) + 1;
			pos_cats = new bool[cat_size];
			neg_cats = new bool[cat_size];
			for (int i = 0; i < cat_size; ++ i) {
				pos_cats[i] = false;
				neg_cats[i] = false;
			}
		}

		public CharacterClass (Category cat, bool negate) : this (false, false) {
			this.AddCategory (cat, negate);
		}

		public bool Negate {
			get { return negate; }
			set { negate = value; }
		}

		public bool IgnoreCase {
			get { return ignore; }
			set { ignore = value; }
		}

		public void AddCategory (Category cat, bool negate) {
			int n = (int)cat;
			
			if (negate) {
				if (pos_cats[n])
					pos_cats[n] = false;

				neg_cats[n] = true;
			}
			else {
				if (neg_cats[n])
					neg_cats[n] = false;

				pos_cats[n] = true;
			}
		}

		public void AddCharacter (char c) {
			intervals.Add (new Interval (c, c));
		}

		public void AddRange (char lo, char hi) {
			intervals.Add (new Interval (lo, hi));
		}

		public override void Compile (ICompiler cmp, bool reverse) {
			// create the meta-collection

			IntervalCollection meta =
				intervals.GetMetaCollection (new IntervalCollection.CostDelegate (GetIntervalCost));

			// count ops
			
			int count = meta.Count;
			for (int i = 0; i < pos_cats.Length; ++ i) {
				if (pos_cats[i]) ++ count;
				if (neg_cats[i]) ++ count;
			}

			if (count == 0)
				return;

			// emit in op for |meta| > 1

			LinkRef tail = cmp.NewLink ();
			if (count > 1)
				cmp.EmitIn (tail);

			// emit categories

			for (int i = 0; i < pos_cats.Length; ++ i) {
				if (pos_cats[i])
					cmp.EmitCategory ((Category)i, negate, reverse);
				else if (neg_cats[i])
					cmp.EmitCategory ((Category)i, !negate, reverse);
			}

			// emit character/range/sets from meta-collection

			foreach (Interval a in meta) {
				if (a.IsDiscontiguous) {			// Set
					BitArray bits = new BitArray (a.Size);
					foreach (Interval b in intervals) {
						if (a.Contains (b)) {
							for (int i = b.low; i <= b.high; ++ i)
								bits[i - a.low] = true;
						}
					}

					cmp.EmitSet ((char)a.low, bits, negate, ignore, reverse);
				}
				else if (a.IsSingleton)				// Character
					cmp.EmitCharacter ((char)a.low, negate, ignore, reverse);
				else						// Range
					cmp.EmitRange ((char)a.low, (char)a.high, negate, ignore, reverse);
			}
			
			// finish up

			if (count > 1) {
				if (negate)
					cmp.EmitTrue ();
				else
					cmp.EmitFalse ();

				cmp.ResolveLink (tail);
			}
		}

		public override void GetWidth (out int min, out int max) {
			min = max = 1;
		}

		public override bool IsComplex () {
			return false;
		}

		// private

		private static double GetIntervalCost (Interval i) {
			// use op length as cost metric (=> optimize for space)
		
			if (i.IsDiscontiguous)
				return 3 + ((i.Size + 0xf) >> 4);		// Set
			else if (i.IsSingleton)
				return 2;					// Character
			else
				return 3;					// Range
		}

		private bool negate, ignore;
		private bool[] pos_cats, neg_cats;
		private IntervalCollection intervals;
	}

	class AnchorInfo {
		private Expression expr;

		private Position pos;
		private int offset;

		private string str;
		private int width;
		private bool ignore;

		public AnchorInfo (Expression expr, int width) {
			this.expr = expr;
			this.offset = 0;
			this.width = width;

			this.str = null;
			this.ignore = false;
			this.pos = Position.Any;
		}
		
		public AnchorInfo (Expression expr, int offset, int width, string str, bool ignore) {
			this.expr = expr;
			this.offset = offset;
			this.width = width;

			this.str = ignore ? str.ToLower () : str;

			this.ignore = ignore;
			this.pos = Position.Any;
		}

		public AnchorInfo (Expression expr, int offset, int width, Position pos) {
			this.expr = expr;
			this.offset = offset;
			this.width = width;

			this.pos = pos;

			this.str = null;
			this.ignore = false;
		}

		public Expression Expression {
			get { return expr; }
		}

		public int Offset {
			get { return offset; }
		}

		public int Width {
			get { return width; }
		}

		public int Length {
			get { return (str != null) ? str.Length : 0; }
		}

		public bool IsUnknownWidth {
			get { return width < 0; }
		}

		public bool IsComplete {
			get { return Length == Width; }
		}

		public string Substring {
			get { return str; }
		}

		public bool IgnoreCase {
			get { return ignore; }
		}

		public Position Position {
			get { return pos; }
		}

		public bool IsSubstring {
			get { return str != null; }
		}

		public bool IsPosition {
			get { return pos != Position.Any; }
		}

		public Interval GetInterval () {
			return GetInterval (0);
		}

		public Interval GetInterval (int start) {
			if (!IsSubstring)
				return Interval.Empty;

			return new Interval (start + Offset, start + Offset + Length - 1);
		}
	}
}