|
//------------------------------------------------------------------------------
// <copyright file="RegexNode.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// </copyright>
//------------------------------------------------------------------------------
// This RegexNode class is internal to the Regex package.
// It is built into a parsed tree for a regular expression.
// Implementation notes:
//
// Since the node tree is a temporary data structure only used
// during compilation of the regexp to integer codes, it's
// designed for clarity and convenience rather than
// space efficiency.
//
// RegexNodes are built into a tree, linked by the _children list.
// Each node also has a _parent and _ichild member indicating
// its parent and which child # it is in its parent's list.
//
// RegexNodes come in as many types as there are constructs in
// a regular expression, for example, "concatenate", "alternate",
// "one", "rept", "group". There are also node types for basic
// peephole optimizations, e.g., "onerep", "notsetrep", etc.
//
// Because perl 5 allows "lookback" groups that scan backwards,
// each node also gets a "direction". Normally the value of
// boolean _backward = false.
//
// During parsing, top-level nodes are also stacked onto a parse
// stack (a stack of trees). For this purpose we have a _next
// pointer. [Note that to save a few bytes, we could overload the
// _parent pointer instead.]
//
// On the parse stack, each tree has a "role" - basically, the
// nonterminal in the grammar that the parser has currently
// assigned to the tree. That code is stored in _role.
//
// Finally, some of the different kinds of nodes have data.
// Two integers (for the looping constructs) are stored in
// _operands, an an object (either a string or a set)
// is stored in _data
namespace System.Text.RegularExpressions {
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
internal sealed class RegexNode {
/*
* RegexNode types
*/
// the following are leaves, and correspond to primitive operations
// static final int Onerep = RegexCode.Onerep; // c,n a {n}
// static final int Notonerep = RegexCode.Notonerep; // c,n .{n}
// static final int Setrep = RegexCode.Setrep; // set,n \d {n}
internal const int Oneloop = RegexCode.Oneloop; // c,n a*
internal const int Notoneloop = RegexCode.Notoneloop; // c,n .*
internal const int Setloop = RegexCode.Setloop; // set,n \d*
internal const int Onelazy = RegexCode.Onelazy; // c,n a*?
internal const int Notonelazy = RegexCode.Notonelazy; // c,n .*?
internal const int Setlazy = RegexCode.Setlazy; // set,n \d*?
internal const int One = RegexCode.One; // char a
internal const int Notone = RegexCode.Notone; // char . [^a]
internal const int Set = RegexCode.Set; // set [a-z] \w \s \d
internal const int Multi = RegexCode.Multi; // string abcdef
internal const int Ref = RegexCode.Ref; // index \1
internal const int Bol = RegexCode.Bol; // ^
internal const int Eol = RegexCode.Eol; // $
internal const int Boundary = RegexCode.Boundary; // \b
internal const int Nonboundary= RegexCode.Nonboundary;// \B
internal const int ECMABoundary = RegexCode.ECMABoundary; // \b
internal const int NonECMABoundary= RegexCode.NonECMABoundary; // \B
internal const int Beginning = RegexCode.Beginning; // \A
internal const int Start = RegexCode.Start; // \G
internal const int EndZ = RegexCode.EndZ; // \Z
internal const int End = RegexCode.End; // \z
// (note: End = 21;)
// interior nodes do not correpond to primitive operations, but
// control structures compositing other operations
// concat and alternate take n children, and can run forward or backwards
internal const int Nothing = 22; // []
internal const int Empty = 23; // ()
internal const int Alternate = 24; // a|b
internal const int Concatenate= 25; // ab
internal const int Loop = 26; // m,x * + ? {,}
internal const int Lazyloop = 27; // m,x *? +? ?? {,}?
internal const int Capture = 28; // n ()
internal const int Group = 29; // (?:)
internal const int Require = 30; // (?=) (?<=)
internal const int Prevent = 31; // (?!) (?<!)
internal const int Greedy = 32; // (?>) (?<)
internal const int Testref = 33; // (?(n) | )
internal const int Testgroup = 34; // (?(...) | )
/*
* RegexNode data members
*
*/
internal int _type;
internal List<RegexNode> _children;
internal String _str;
internal char _ch;
internal int _m;
internal int _n;
internal RegexOptions _options;
internal RegexNode _next;
internal RegexNode(int type, RegexOptions options) {
_type = type;
_options = options;
}
internal RegexNode(int type, RegexOptions options, char ch) {
_type = type;
_options = options;
_ch = ch;
}
internal RegexNode(int type, RegexOptions options, String str) {
_type = type;
_options = options;
_str = str;
}
internal RegexNode(int type, RegexOptions options, int m) {
_type = type;
_options = options;
_m = m;
}
internal RegexNode(int type, RegexOptions options, int m, int n) {
_type = type;
_options = options;
_m = m;
_n = n;
}
internal bool UseOptionR() {
return(_options & RegexOptions.RightToLeft) != 0;
}
internal RegexNode ReverseLeft() {
if (UseOptionR() && _type == Concatenate && _children != null) {
_children.Reverse(0, _children.Count);
}
return this;
}
// Pass type as OneLazy or OneLoop
internal void MakeRep(int type, int min, int max) {
_type += (type - One);
_m = min;
_n = max;
}
/*
* Reduce
*
* Removes redundant nodes from the subtree, and returns a reduced subtree.
*/
internal RegexNode Reduce() {
RegexNode n;
switch (Type()) {
case Alternate:
n = ReduceAlternation();
break;
case Concatenate:
n = ReduceConcatenation();
break;
case Loop:
case Lazyloop:
n = ReduceRep();
break;
case Group:
n = ReduceGroup();
break;
case Set:
case Setloop:
n = ReduceSet();
break;
default:
n = this;
break;
}
return n;
}
/*
* StripEnation:
*
* Simple optimization. If a concatenation or alternation has only
* one child strip out the intermediate node. If it has zero children,
* turn it into an empty.
*
*/
internal RegexNode StripEnation(int emptyType) {
switch (ChildCount()) {
case 0:
return new RegexNode(emptyType, _options);
case 1:
return Child(0);
default:
return this;
}
}
/*
* ReduceGroup:
*
* Simple optimization. Once parsed into a tree, noncapturing groups
* serve no function, so strip them out.
*/
internal RegexNode ReduceGroup() {
RegexNode u;
for (u = this; u.Type() == Group; )
u = u.Child(0);
return u;
}
/*
* ReduceRep:
*
* Nested repeaters just get multiplied with each other if they're not
* too lumpy
*/
internal RegexNode ReduceRep() {
RegexNode u;
RegexNode child;
int type;
int min;
int max;
u = this;
type = Type();
min = _m;
max = _n;
for (;;) {
if (u.ChildCount() == 0)
break;
child = u.Child(0);
// multiply reps of the same type only
if (child.Type() != type) {
int childType = child.Type();
if (!(childType >= Oneloop && childType <= Setloop && type == Loop ||
childType >= Onelazy && childType <= Setlazy && type == Lazyloop))
break;
}
// child can be too lumpy to blur, e.g., (a {100,105}) {3} or (a {2,})?
// [but things like (a {2,})+ are not too lumpy...]
if (u._m == 0 && child._m > 1 || child._n < child._m * 2)
break;
u = child;
if (u._m > 0)
u._m = min = ((Int32.MaxValue - 1) / u._m < min) ? Int32.MaxValue : u._m * min;
if (u._n > 0)
u._n = max = ((Int32.MaxValue - 1) / u._n < max) ? Int32.MaxValue : u._n * max;
}
return min == Int32.MaxValue ? new RegexNode(Nothing, _options) : u;
}
/*
* ReduceSet:
*
* Simple optimization. If a set is a singleton, an inverse singleton,
* or empty, it's transformed accordingly.
*/
internal RegexNode ReduceSet() {
// Extract empty-set, one and not-one case as special
if (RegexCharClass.IsEmpty(_str)) {
_type = Nothing;
_str = null;
}
else if (RegexCharClass.IsSingleton(_str)) {
_ch = RegexCharClass.SingletonChar(_str);
_str = null;
_type += (One - Set);
}
else if (RegexCharClass.IsSingletonInverse(_str)) {
_ch = RegexCharClass.SingletonChar(_str);
_str = null;
_type += (Notone - Set);
}
return this;
}
/*
* ReduceAlternation:
*
* Basic optimization. Single-letter alternations can be replaced
* by faster set specifications, and nested alternations with no
* intervening operators can be flattened:
*
* a|b|c|def|g|h -> [a-c]|def|[gh]
* apple|(?:orange|pear)|grape -> apple|orange|pear|grape
*
* <
*/
internal RegexNode ReduceAlternation() {
// Combine adjacent sets/chars
bool wasLastSet;
bool lastNodeCannotMerge;
RegexOptions optionsLast;
RegexOptions optionsAt;
int i;
int j;
RegexNode at;
RegexNode prev;
if (_children == null)
return new RegexNode(RegexNode.Nothing, _options);
wasLastSet = false;
lastNodeCannotMerge = false;
optionsLast = 0;
for (i = 0, j = 0; i < _children.Count; i++, j++) {
at = _children[i];
if (j < i)
_children[j] = at;
for (;;) {
if (at._type == Alternate) {
for (int k = 0; k < at._children.Count; k++)
at._children[k]._next = this;
_children.InsertRange(i + 1, at._children);
j--;
}
else if (at._type == Set || at._type == One) {
// Cannot merge sets if L or I options differ, or if either are negated.
optionsAt = at._options & (RegexOptions.RightToLeft | RegexOptions.IgnoreCase);
if (at._type == Set) {
if (!wasLastSet || optionsLast != optionsAt || lastNodeCannotMerge || !RegexCharClass.IsMergeable(at._str)) {
wasLastSet = true;
lastNodeCannotMerge = !RegexCharClass.IsMergeable(at._str);
optionsLast = optionsAt;
break;
}
}
else if (!wasLastSet || optionsLast != optionsAt || lastNodeCannotMerge) {
wasLastSet = true;
lastNodeCannotMerge = false;
optionsLast = optionsAt;
break;
}
// The last node was a Set or a One, we're a Set or One and our options are the same.
// Merge the two nodes.
j--;
prev = _children[j];
RegexCharClass prevCharClass;
if (prev._type == RegexNode.One) {
prevCharClass = new RegexCharClass();
prevCharClass.AddChar(prev._ch);
}
else {
prevCharClass = RegexCharClass.Parse(prev._str);
}
if (at._type == RegexNode.One) {
prevCharClass.AddChar(at._ch);
}
else {
RegexCharClass atCharClass = RegexCharClass.Parse(at._str);
prevCharClass.AddCharClass(atCharClass);
}
prev._type = RegexNode.Set;
prev._str = prevCharClass.ToStringClass();
}
else if (at._type == RegexNode.Nothing) {
j--;
}
else {
wasLastSet = false;
lastNodeCannotMerge = false;
}
break;
}
}
if (j < i)
_children.RemoveRange(j, i - j);
return StripEnation(RegexNode.Nothing);
}
/*
* ReduceConcatenation:
*
* Basic optimization. Adjacent strings can be concatenated.
*
* (?:abc)(?:def) -> abcdef
*/
internal RegexNode ReduceConcatenation() {
// Eliminate empties and concat adjacent strings/chars
bool wasLastString;
RegexOptions optionsLast;
RegexOptions optionsAt;
int i;
int j;
if (_children == null)
return new RegexNode(RegexNode.Empty, _options);
wasLastString = false;
optionsLast = 0;
for (i = 0, j = 0; i < _children.Count; i++, j++) {
RegexNode at;
RegexNode prev;
at = _children[i];
if (j < i)
_children[j] = at;
if (at._type == RegexNode.Concatenate &&
((at._options & RegexOptions.RightToLeft) == (_options & RegexOptions.RightToLeft))) {
for (int k = 0; k < at._children.Count; k++)
at._children[k]._next = this;
_children.InsertRange(i + 1, at._children);
j--;
}
else if (at._type == RegexNode.Multi ||
at._type == RegexNode.One) {
// Cannot merge strings if L or I options differ
optionsAt = at._options & (RegexOptions.RightToLeft | RegexOptions.IgnoreCase);
if (!wasLastString || optionsLast != optionsAt) {
wasLastString = true;
optionsLast = optionsAt;
continue;
}
prev = _children[--j];
if (prev._type == RegexNode.One) {
prev._type = RegexNode.Multi;
prev._str = Convert.ToString(prev._ch, CultureInfo.InvariantCulture);
}
if ((optionsAt & RegexOptions.RightToLeft) == 0) {
if (at._type == RegexNode.One)
prev._str += at._ch.ToString();
else
prev._str += at._str;
}
else {
if (at._type == RegexNode.One)
prev._str = at._ch.ToString() + prev._str;
else
prev._str = at._str + prev._str;
}
}
else if (at._type == RegexNode.Empty) {
j--;
}
else {
wasLastString = false;
}
}
if (j < i)
_children.RemoveRange(j, i - j);
return StripEnation(RegexNode.Empty);
}
internal RegexNode MakeQuantifier(bool lazy, int min, int max) {
RegexNode result;
if (min == 0 && max == 0)
return new RegexNode(RegexNode.Empty, _options);
if (min == 1 && max == 1)
return this;
switch (_type) {
case RegexNode.One:
case RegexNode.Notone:
case RegexNode.Set:
MakeRep(lazy ? RegexNode.Onelazy : RegexNode.Oneloop, min, max);
return this;
default:
result = new RegexNode(lazy ? RegexNode.Lazyloop : RegexNode.Loop, _options, min, max);
result.AddChild(this);
return result;
}
}
internal void AddChild(RegexNode newChild) {
RegexNode reducedChild;
if (_children == null)
_children = new List<RegexNode>(4);
reducedChild = newChild.Reduce();
_children.Add(reducedChild);
reducedChild._next = this;
}
internal RegexNode Child(int i) {
return _children[i];
}
internal int ChildCount() {
return _children == null ? 0 : _children.Count;
}
internal int Type() {
return _type;
}
#if DBG
internal static String[] TypeStr = new String[] {
"Onerep", "Notonerep", "Setrep",
"Oneloop", "Notoneloop", "Setloop",
"Onelazy", "Notonelazy", "Setlazy",
"One", "Notone", "Set",
"Multi", "Ref",
"Bol", "Eol", "Boundary", "Nonboundary",
"ECMABoundary", "NonECMABoundary",
"Beginning", "Start", "EndZ", "End",
"Nothing", "Empty",
"Alternate", "Concatenate",
"Loop", "Lazyloop",
"Capture", "Group", "Require", "Prevent", "Greedy",
"Testref", "Testgroup"};
internal String Description() {
StringBuilder ArgSb = new StringBuilder();
ArgSb.Append(TypeStr[_type]);
if ((_options & RegexOptions.ExplicitCapture) != 0)
ArgSb.Append("-C");
if ((_options & RegexOptions.IgnoreCase) != 0)
ArgSb.Append("-I");
if ((_options & RegexOptions.RightToLeft) != 0)
ArgSb.Append("-L");
if ((_options & RegexOptions.Multiline) != 0)
ArgSb.Append("-M");
if ((_options & RegexOptions.Singleline) != 0)
ArgSb.Append("-S");
if ((_options & RegexOptions.IgnorePatternWhitespace) != 0)
ArgSb.Append("-X");
if ((_options & RegexOptions.ECMAScript) != 0)
ArgSb.Append("-E");
switch (_type) {
case Oneloop:
case Notoneloop:
case Onelazy:
case Notonelazy:
case One:
case Notone:
ArgSb.Append("(Ch = " + RegexCharClass.CharDescription(_ch) + ")");
break;
case Capture:
ArgSb.Append("(index = " + _m.ToString(CultureInfo.InvariantCulture) + ", unindex = " + _n.ToString(CultureInfo.InvariantCulture) + ")");
break;
case Ref:
case Testref:
ArgSb.Append("(index = " + _m.ToString(CultureInfo.InvariantCulture) + ")");
break;
case Multi:
ArgSb.Append("(String = " + _str + ")");
break;
case Set:
case Setloop:
case Setlazy:
ArgSb.Append("(Set = " + RegexCharClass.SetDescription(_str) + ")");
break;
}
switch (_type) {
case Oneloop:
case Notoneloop:
case Onelazy:
case Notonelazy:
case Setloop:
case Setlazy:
case Loop:
case Lazyloop:
ArgSb.Append("(Min = " + _m.ToString(CultureInfo.InvariantCulture) + ", Max = " + (_n == Int32.MaxValue ? "inf" : Convert.ToString(_n, CultureInfo.InvariantCulture)) + ")");
break;
}
return ArgSb.ToString();
}
internal const String Space = " ";
internal void Dump() {
List<int> Stack = new List<int>();
RegexNode CurNode;
int CurChild;
CurNode = this;
CurChild = 0;
Debug.WriteLine(CurNode.Description());
for (;;) {
if (CurNode._children != null && CurChild < CurNode._children.Count) {
Stack.Add(CurChild + 1);
CurNode = CurNode._children[CurChild];
CurChild = 0;
int Depth = Stack.Count;
if (Depth > 32)
Depth = 32;
Debug.WriteLine(Space.Substring(0, Depth) + CurNode.Description());
}
else {
if (Stack.Count == 0)
break;
CurChild = Stack[Stack.Count - 1];
Stack.RemoveAt(Stack.Count - 1);
CurNode = CurNode._next;
}
}
}
#endif
}
}
|