Regex

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

import System;

into namespace System.Text
{
	/// A compiled pattern.
	public final class Regex
	{
		RegexNode root;
		i32 groups;
		str pattern;
		u8[] first;
		bool prefilter;
		bool anchored;
		i32 repeats;
		i32[] counts;
		i32[] iterationStarts;
		bool memoizable;
		i32 tails;
		u64[] failed;
		u8[] failedText;
		bool remember;
		u8[] s;
		i32[] starts;
		i32[] ends;
		i32 matchEnd;

		/// Whether a node can match without taking a unit; the units it can start with are added to `table`.
		static Scan(RegexNode node, u8[] table) : bool
		{
			i32 kind = node.Kind;
			if (kind == 1)
			{
				table[node.Literal] = 1;
				return false;
			}
			if (kind == 2)
			{
				loop (i32 i = 0..256)
				{
					if (node.Table[i] != 0)
						table[i] = 1;
				}
				return false;
			}
			if (kind == 3)
			{
				loop (i32 i = 0..256)
				{
					if (i != 10)
						table[i] = 1;
				}
				return false;
			}
			if (kind == 4)
			{
				{
					ListIterator<RegexNode> _iterator3 = node.Children.Iterator();
					loop (_iterator3.Next())
					{
						RegexNode child = _iterator3.Current;
						{
							if (!Scan(child, table))
								return false;
						}
					}
				}
				return true;
			}
			if (kind == 5)
			{
				bool empty = false;
				{
					ListIterator<RegexNode> _iterator6 = node.Children.Iterator();
					loop (_iterator6.Next())
					{
						RegexNode option = _iterator6.Current;
						{
							if (Scan(option, table))
								empty = true;
						}
					}
				}
				return empty;
			}
			if (kind == 6)
				return Scan(node.Child, table);
			if (kind == 8)
				return Scan(node.Child, table) || node.Min == 0;
			return true;
		}

		/// Links a parsed node to what follows it (`next`): its entry, the node matching starts it with.
		Link(RegexNode node, RegexNode next) : RegexNode
		{
			i32 kind = node.Kind;
			if (kind == 4)
			{
				RegexNode entry = next;
				i32 i = node.Children.Count - 1;
				loop (i >= 0)
				{
					entry = Link(node.Children[i], entry);
					i--;
				}
				return entry;
			}
			node.Next = next;
			if (kind == 5)
			{
				loop (i32 i = 0..node.Children.Count)
					node.Children[i] = Link(node.Children[i], next);
			}
			else if (kind == 6)
			{
				RegexNode close = new RegexNode(7);
				close.Index = node.Index;
				close.Next = next;
				node.Child = Link(node.Child, close);
			}
			else if (kind == 8)
			{
				i32 atom = node.Child.Kind;
				node.Units = atom == 1 || atom == 2 || atom == 3;
				if (!node.Units)
				{
					bool simple = node.Min <= 1 && (node.Max == -1 || node.Max == 1);
					if (!simple || Scan(node.Child, new u8[256]))
						memoizable = false;
					node.Count = repeats;
					repeats++;
					RegexNode tail = new RegexNode(9);
					tail.Repeat = node;
					tail.Index = tails;
					tails++;
					node.Child = Link(node.Child, tail);
				}
			}
			return node;
		}

		Run(RegexNode start, i32 at) : i32
		{
			RegexNode node = start;
			i32 pos = at;
			loop (true)
			{
				i32 kind = node.Kind;
				if (kind == 1)
				{
					if (pos >= s.Length || s[pos] != node.Literal)
						return -1;
					pos++;
				}
				else if (kind == 2)
				{
					if (pos >= s.Length || node.Table[s[pos]] == 0)
						return -1;
					pos++;
				}
				else if (kind == 3)
				{
					if (pos >= s.Length || s[pos] == 10)
						return -1;
					pos++;
				}
				else if (kind == 10)
				{
					if (pos != 0)
						return -1;
				}
				else if (kind == 11)
				{
					if (pos != s.Length)
						return -1;
				}
				else if (kind == 12 || kind == 13)
				{
					bool before = pos > 0 && RegexParser.IsWord(s[pos - 1]);
					bool after = pos < s.Length && RegexParser.IsWord(s[pos]);
					if (before != after != (kind == 12))
						return -1;
				}
				else
					return Branch(node, pos);
				node = node.Next;
			}
		}

		/// The nodes that may try more than one way on: the end, alternatives, groups and repeats.
		Branch(RegexNode node, i32 pos) : i32
		{
			i32 kind = node.Kind;
			if (kind == 0)
				return pos;
			if (kind == 5)
			{
				{
					ListIterator<RegexNode> _iterator1 = node.Children.Iterator();
					loop (_iterator1.Next())
					{
						RegexNode option = _iterator1.Current;
						{
							i32 r = Run(option, pos);
							if (r >= 0)
								return r;
						}
					}
				}
				return -1;
			}
			if (kind == 6)
			{
				i32 oldStart = starts[node.Index];
				i32 oldEnd = ends[node.Index];
				starts[node.Index] = pos;
				i32 r = Run(node.Child, pos);
				if (r < 0)
				{
					starts[node.Index] = oldStart;
					ends[node.Index] = oldEnd;
				}
				return r;
			}
			if (kind == 7)
			{
				i32 old = ends[node.Index];
				ends[node.Index] = pos;
				i32 r = Run(node.Next, pos);
				if (r < 0)
					ends[node.Index] = old;
				return r;
			}
			if (kind == 8)
			{
				if (node.Units)
					return RunUnits(node, pos);
				return Iterate(node, pos, 0, -1);
			}
			if (kind == 9)
			{
				RegexNode repeat = node.Repeat;
				i64 bit = 0;
				if (remember)
				{
					if (failed.Length == 0)
						failed = new u64[(i32)(((i64)tails * ((i64)s.Length + 1) + 63) / 64)];
					bit = (i64)node.Index * ((i64)s.Length + 1) + (i64)pos;
					if ((failed[(i32)(bit >> 6)] >> (u64)(bit & 63) & 1) != 0)
						return -1;
				}
				i32 r = Iterate(repeat, pos, counts[repeat.Count] + 1, iterationStarts[repeat.Count]);
				if (r < 0 && remember)
					failed[(i32)(bit >> 6)] = failed[(i32)(bit >> 6)] | 1 << (u64)(bit & 63);
				return r;
			}
			return -1;
		}

		/// Whether a single-unit atom (a literal, a class or `.`) takes the unit at `at`.
		Takes(RegexNode atom, i32 at) : bool
		{
			u8 c = s[at];
			if (atom.Kind == 1)
				return c == atom.Literal;
			if (atom.Kind == 2)
				return atom.Table[c] != 0;
			return c != 10;
		}

		/// A repeat of a single-unit atom, as a loop over the run of units it takes rather than a call per unit (a
		/// long text would exhaust the stack): greedy takes the longest run and backs off one unit at a time while
		/// the rest fails (only to where the next literal is, when a literal follows); lazy starts from the minimum
		/// and takes one more unit at a time.
		RunUnits(RegexNode node, i32 pos) : i32
		{
			RegexNode atom = node.Child;
			RegexNode next = node.Next;
			i32 limit = s.Length - pos;
			if (node.Max >= 0 && node.Max < limit)
				limit = node.Max;
			i32 n = 0;
			if (!node.Lazy)
			{
				loop (n < limit && Takes(atom, pos + n))
					n++;
				bool literal = next.Kind == 1;
				loop (n >= node.Min)
				{
					i32 at = pos + n;
					if (!literal || at < s.Length && s[at] == next.Literal)
					{
						i32 r = Run(next, at);
						if (r >= 0)
							return r;
					}
					n--;
				}
				return -1;
			}
			loop (n < node.Min)
			{
				if (n >= limit || !Takes(atom, pos + n))
					return -1;
				n++;
			}
			loop (true)
			{
				i32 r = Run(next, pos + n);
				if (r >= 0)
					return r;
				if (n >= limit || !Takes(atom, pos + n))
					return -1;
				n++;
			}
		}

		/// A repeat of more than one unit at `pos`: `count` iterations are done; `last` is where the last one started
		/// (-1 at first).
		Iterate(RegexNode node, i32 pos, i32 count, i32 last) : i32
		{
			bool more = (node.Max < 0 || count < node.Max) && !(count > node.Min && last == pos);
			if (!node.Lazy)
			{
				if (more)
				{
					i32 r = Again(node, pos, count);
					if (r >= 0)
						return r;
				}
				return count >= node.Min ? Run(node.Next, pos) : -1;
			}
			if (count >= node.Min)
			{
				i32 r = Run(node.Next, pos);
				if (r >= 0)
					return r;
			}
			return more ? Again(node, pos, count) : -1;
		}

		/// One more iteration of a repeat from `pos`, after `count` (put back when it fails).
		Again(RegexNode node, i32 pos, i32 count) : i32
		{
			i32 slot = node.Count;
			i32 oldCount = counts[slot];
			i32 oldStart = iterationStarts[slot];
			counts[slot] = count;
			iterationStarts[slot] = pos;
			i32 r = Run(node.Child, pos);
			if (r < 0)
			{
				counts[slot] = oldCount;
				iterationStarts[slot] = oldStart;
			}
			return r;
		}

		/// The first match from `from` on: its start (-1 when none); its end in matchEnd.
		Search(u8[] text, i32 from) : i32
		{
			s = text;
			starts = new i32[groups + 1];
			ends = new i32[groups + 1];
			if (text != failedText)
			{
				failedText = text;
				failed = new u64[0];
			}
			remember = memoizable && (i64)tails * ((i64)text.Length + 1) <= 268435456;
			i32 last = anchored ? from == 0 ? 0 : -1 : text.Length;
			i32 start = from;
			loop (start <= last)
			{
				if (prefilter)
				{
					loop (start < text.Length && first[text[start]] == 0)
						start++;
					if (start >= text.Length)
						break;
				}
				loop (i32 g = 0..starts.Length)
				{
					starts[g] = -1;
					ends[g] = -1;
				}
				i32 r = Run(root, start);
				if (r >= 0)
				{
					matchEnd = r;
					return start;
				}
				start++;
			}
			matchEnd = -1;
			return -1;
		}

		public:
			new(str pattern)
			{
				this.pattern = pattern;
				RegexParser parser = new RegexParser(pattern.Units());
				RegexNode parsed = parser.Parse();
				groups = parser.Groups;
				first = new u8[256];
				bool empty = Scan(parsed, first);
				i32 kinds = 0;
				loop (i32 i = 0..256)
				{
					if (first[i] != 0)
						kinds++;
				}
				prefilter = !empty && kinds < 256;
				memoizable = true;
				root = Link(parsed, new RegexNode(0));
				anchored = root.Kind == 10;
				counts = new i32[repeats];
				iterationStarts = new i32[repeats];
				failed = new u64[0];
				failedText = new u8[0];
				s = new u8[0];
				starts = new i32[0];
				ends = new i32[0];
			}

			/// Whether the pattern matches somewhere in `input`.
			IsMatch(str input) : bool => Search(input.Units(), 0) >= 0;

			static IsMatch(str input, str pattern) : bool => new Regex(pattern).IsMatch(input);

			/// The first match in `input` (Success false when there is none).
			Match(str input) : Match => Match(input, 0);

			/// The first match in `input` at or after `from`.
			Match(str input, i32 from) : Match
			{
				u8[] text = input.Units();
				i32 start = Search(text, from);
				return new Match(text, starts, ends, start, matchEnd);
			}

			/// Every match in `input`, left to right (an empty match moves on by one unit).
			Matches(str input) : List<Match>
			{
				List<Match> found = new List<Match>();
				u8[] text = input.Units();
				i32 from = 0;
				loop (from <= text.Length)
				{
					i32 start = Search(text, from);
					i32 end = matchEnd;
					if (start < 0)
						break;
					found.Add(new Match(text, starts, ends, start, end));
					from = end > start ? end : start + 1;
				}
				return found;
			}

			/// `input` with every match replaced by `replacement` (`$1`…`$9` in it stand for the groups, `$0` for the match).
			Replace(str input, str replacement) : str
			{
				u8[] text = input.Units();
				u8[] with = replacement.Units();
				StringBuilder result = new StringBuilder();
				i32 from = 0;
				i32 copied = 0;
				loop (from <= text.Length)
				{
					i32 start = Search(text, from);
					i32 end = matchEnd;
					if (start < 0)
						break;
					Match match = new Match(text, starts, ends, start, end);
					result.Append(Match.Slice(text, copied, start));
					i32 i = 0;
					loop (i < with.Length)
					{
						if (with[i] == 36 && i + 1 < with.Length && with[i + 1] >= 48 && with[i + 1] <= 57)
						{
							result.Append(match.Group((i32)with[i + 1] - 48));
							i += 2;
							continue;
						}
						result.Append(new str([with[i]]));
						i++;
					}
					copied = end;
					from = end > start ? end : start + 1;
				}
				result.Append(Match.Slice(text, copied, text.Length));
				return result.ToString();
			}

			str Pattern
			{
				get => pattern;
			}
	}
}