RegexParser

// System.Text.RegexParser — System.Core (decompiled from Larva HIR)

import System;

into namespace System.Text
{
	/// A pattern's text to its nodes.
	public final class RegexParser
	{
		u8[] p;
		i32 at;
		i32 groups;

		Fail(str what) : RegexNode
		{
			throw new ArgumentError("regex: " + what);
		}

		ParseAlt() : RegexNode
		{
			RegexNode first = ParseSeq();
			if (at < p.Length && p[at] == 124)
			{
				RegexNode alt = new RegexNode(5);
				alt.Children.Add(first);
				loop (at < p.Length && p[at] == 124)
				{
					at++;
					alt.Children.Add(ParseSeq());
				}
				return alt;
			}
			return first;
		}

		ParseSeq() : RegexNode
		{
			RegexNode seq = new RegexNode(4);
			loop (at < p.Length && p[at] != 124 && p[at] != 41)
				seq.Children.Add(ParseQuantifier(ParseAtom()));
			return seq;
		}

		ParseAtom() : RegexNode
		{
			u32 c = p[at];
			if (c == 40)
			{
				at++;
				if (at + 1 < p.Length && p[at] == 63 && p[at + 1] == 58)
				{
					at += 2;
					RegexNode inner = ParseAlt();
					Expect(41);
					return inner;
				}
				groups = groups + 1;
				RegexNode group = new RegexNode(6);
				group.Index = groups;
				group.Child = ParseAlt();
				Expect(41);
				return group;
			}
			if (c == 91)
				return ParseClass();
			if (c == 46)
			{
				at++;
				return new RegexNode(3);
			}
			if (c == 94)
			{
				at++;
				return new RegexNode(10);
			}
			if (c == 36)
			{
				at++;
				return new RegexNode(11);
			}
			if (c == 92)
			{
				at++;
				if (at >= p.Length)
					return Fail("the pattern ends after \\");
				return ParseEscape();
			}
			if (c == 42 || c == 43 || c == 63)
				return Fail("a quantifier with nothing before it");
			at++;
			RegexNode literal = new RegexNode(1);
			literal.Literal = (u8)c;
			return literal;
		}

		Expect(u32 c)
		{
			if (at >= p.Length || p[at] != c)
				Fail("missing `" + new str([(u8)c]) + "`");
			at++;
		}

		/// After `\`: a class escape (`\d` `\w` `\s` and the negations), a word boundary (`\b` `\B`), or a character.
		ParseEscape() : RegexNode
		{
			u32 c = p[at];
			at++;
			if (c == 100 || c == 119 || c == 115 || c == 68 || c == 87 || c == 83)
			{
				RegexNode cls = new RegexNode(2);
				cls.Table = new u8[256];
				FillEscape(cls.Table, c);
				return cls;
			}
			if (c == 98 || c == 66)
				return new RegexNode(c == 98 ? 12 : 13);
			RegexNode literal = new RegexNode(1);
			literal.Literal = (u8)EscapedUnit(c);
			return literal;
		}

		/// The unit an escaped character stands for: `\n \t \r \f \v`, or a character that is no letter or digit
		/// (itself); any other escape is an error (`\1`, `\x41`, `\u0041` and the like are not supported).
		EscapedUnit(u32 c) : u32
		{
			if (c == 110)
				return 10;
			if (c == 116)
				return 9;
			if (c == 114)
				return 13;
			if (c == 102)
				return 12;
			if (c == 118)
				return 11;
			if (IsWord((u8)c))
				Fail("unsupported escape `\\" + new str([(u8)c]) + "`");
			return c;
		}

		static FillEscape(u8[] table, u32 c)
		{
			u8[] own = new u8[256];
			if (c == 100 || c == 68)
			{
				loop (i32 i = 48..=57)
					own[i] = 1;
			}
			else if (c == 119 || c == 87)
			{
				loop (i32 i = 97..=122)
					own[i] = 1;
				loop (i32 i = 65..=90)
					own[i] = 1;
				loop (i32 i = 48..=57)
					own[i] = 1;
				own[95] = 1;
			}
			else
			{
				own[32] = 1;
				own[9] = 1;
				own[10] = 1;
				own[13] = 1;
				own[12] = 1;
				own[11] = 1;
			}
			bool negate = c == 68 || c == 87 || c == 83;
			loop (i32 i = 0..256)
			{
				if (own[i] != 0 != negate)
					table[i] = 1;
			}
		}

		ParseClass() : RegexNode
		{
			at++;
			bool negate = at < p.Length && p[at] == 94;
			if (negate)
				at++;
			RegexNode cls = new RegexNode(2);
			cls.Table = new u8[256];
			bool first = true;
			loop (true)
			{
				if (at >= p.Length)
					return Fail("missing `]`");
				u32 c = p[at];
				if (c == 93 && !first)
					break;
				first = false;
				at++;
				if (c == 92)
				{
					if (at >= p.Length)
						return Fail("the class ends after \\");
					u32 e = p[at];
					at++;
					if (e == 100 || e == 119 || e == 115 || e == 68 || e == 87 || e == 83)
					{
						FillEscape(cls.Table, e);
						continue;
					}
					c = e == 98 ? 8 : EscapedUnit(e);
				}
				u32 high = c;
				if (at + 1 < p.Length && p[at] == 45 && p[at + 1] != 93)
				{
					at++;
					high = p[at];
					at++;
					if (high == 92 && at < p.Length)
					{
						high = p[at] == 98 ? 8 : EscapedUnit(p[at]);
						at++;
					}
					if (high < c)
						return Fail("a class range goes backwards");
				}
				loop (i32 i = (i32)c..=(i32)high)
					cls.Table[i] = 1;
			}
			at++;
			if (negate)
			{
				loop (i32 i = 0..256)
					cls.Table[i] = cls.Table[i] != 0 ? 0 : 1;
			}
			return cls;
		}

		ParseQuantifier(RegexNode atom) : RegexNode
		{
			if (at >= p.Length)
				return atom;
			u32 c = p[at];
			i32 min = 0;
			i32 max = -1;
			if (c == 42)
				at++;
			else if (c == 43)
			{
				at++;
				min = 1;
			}
			else if (c == 63)
			{
				at++;
				max = 1;
			}
			else if (c == 123)
			{
				i32 save = at;
				at++;
				i32 n = Digits();
				if (n < 0)
				{
					at = save;
					return atom;
				}
				min = n;
				max = n;
				if (at < p.Length && p[at] == 44)
				{
					at++;
					max = Digits();
				}
				if (at >= p.Length || p[at] != 125)
					return Fail("missing `}`");
				at++;
			}
			else
				return atom;
			loop (atom.Kind == 4 && atom.Children.Count == 1)
				atom = atom.Children[0];
			RegexNode repeat = new RegexNode(8);
			repeat.Child = atom;
			repeat.Min = min;
			repeat.Max = max;
			if (at < p.Length && p[at] == 63)
			{
				at++;
				repeat.Lazy = true;
			}
			return repeat;
		}

		/// A decimal number at the position, or -1 when there is none.
		Digits() : i32
		{
			i32 value = -1;
			loop (at < p.Length && p[at] >= 48 && p[at] <= 57)
			{
				value = (value < 0 ? 0 : value) * 10 + ((i32)p[at] - 48);
				at++;
			}
			return value;
		}

		public:
			new(u8[] pattern)
			{
				p = pattern;
			}

			/// Whether a unit is a word character (`\w`: a letter, a digit or `_`).
			static IsWord(u8 c) : bool => c >= 97 && c <= 122 || c >= 65 && c <= 90 || c >= 48 && c <= 57 || c == 95;

			Parse() : RegexNode
			{
				RegexNode root = ParseAlt();
				if (at < p.Length)
					Fail("unexpected `)`");
				return root;
			}

			i32 Groups
			{
				get => groups;
			}
	}
}