MegaBites-AI/Windows-powershell
0372
1// Copyright (c) Microsoft Corporation.2// Licensed under the MIT License.3 4using System.Collections.Generic;5using System.Diagnostics;6using System.Globalization;7using System.Reflection;8using System.Text;9 10using Dbg = System.Management.Automation;11 12namespace System.Management.Automation13{14 /// <summary>15 /// Takes as input a collection of strings and builds an expression tree from the input.16 /// At the evaluation stage, it walks down the tree and evaluates the result.17 /// </summary>18 public sealed class FlagsExpression<T> where T : struct, IConvertible19 {20 #region Constructors21 22 /// <summary>23 /// Construct the expression from a single string.24 /// </summary>25 /// <param name="expression">26 /// The specified flag attribute expression string.27 /// </param>28 public FlagsExpression(string expression)29 {30 if (!typeof(T).IsEnum)31 {32 throw InterpreterError.NewInterpreterException(expression, typeof(RuntimeException),33 null, "InvalidGenericType", EnumExpressionEvaluatorStrings.InvalidGenericType);34 }35 36 _underType = Enum.GetUnderlyingType(typeof(T));37 38 if (string.IsNullOrWhiteSpace(expression))39 {40 throw InterpreterError.NewInterpreterException(expression, typeof(RuntimeException),41 null, "EmptyInputString", EnumExpressionEvaluatorStrings.EmptyInputString);42 }43 44 List<Token> tokenList = TokenizeInput(expression);45 // Append an OR at the end of the list for construction46 tokenList.Add(new Token(TokenKind.Or));47 48 CheckSyntaxError(tokenList);49 50 Root = ConstructExpressionTree(tokenList);51 }52 53 /// <summary>54 /// Construct the tree from an object collection when arguments are comma separated.55 /// If valid, all elements are OR separated.56 /// </summary>57 /// <param name="expression">58 /// The array of specified flag attribute subexpression strings.59 /// </param>60 public FlagsExpression(object[] expression)61 {62 if (!typeof(T).IsEnum)63 {64 throw InterpreterError.NewInterpreterException(expression, typeof(RuntimeException),65 null, "InvalidGenericType", EnumExpressionEvaluatorStrings.InvalidGenericType);66 }67 68 _underType = Enum.GetUnderlyingType(typeof(T));69 70 if (expression == null)71 {72 throw InterpreterError.NewInterpreterException(null, typeof(ArgumentNullException),73 null, "EmptyInputString", EnumExpressionEvaluatorStrings.EmptyInputString);74 }75 76 foreach (string inputClause in expression)77 {78 if (string.IsNullOrWhiteSpace(inputClause))79 {80 throw InterpreterError.NewInterpreterException(expression, typeof(RuntimeException),81 null, "EmptyInputString", EnumExpressionEvaluatorStrings.EmptyInputString);82 }83 }84 85 List<Token> tokenList = new List<Token>();86 87 foreach (string orClause in expression)88 {89 tokenList.AddRange(TokenizeInput(orClause));90 tokenList.Add(new Token(TokenKind.Or));91 }92 // Unnecessary OR at the end not removed for tree construction93 94 Debug.Assert(tokenList.Count > 0, "Input must not all be white characters.");95 96 CheckSyntaxError(tokenList);97 98 Root = ConstructExpressionTree(tokenList);99 }100 101 #endregion102 103 #region parser tokens104 105 internal enum TokenKind106 {107 Identifier,108 And,109 Or,110 Not111 }112 113 internal class Token114 {115 public string Text { get; set; }116 117 public TokenKind Kind { get; set; }118 119 internal Token(TokenKind kind)120 {121 Kind = kind;122 switch (kind)123 {124 case TokenKind.Or:125 Text = "OR";126 break;127 case TokenKind.And:128 Text = "AND";129 break;130 case TokenKind.Not:131 Text = "NOT";132 break;133 default:134 Debug.Fail("Invalid token kind passed in.");135 break;136 }137 }138 139 internal Token(string identifier)140 {141 Kind = TokenKind.Identifier;142 Text = identifier;143 }144 }145 146 #endregion147 148 #region tree nodes149 150 /// <summary>151 /// Abstract base type for other types of nodes in the tree.152 /// </summary>153 internal abstract class Node154 {155 // Only used in internal nodes holding operators.156 157 public Node Operand1 { get; set; }158 159 internal abstract bool Eval(object val);160 161 internal abstract bool ExistEnum(object enumVal);162 }163 164 /// <summary>165 /// OR node for attributes separated by a comma.166 /// </summary>167 internal class OrNode : Node168 {169 public Node Operand2 { get; set; }170 171 public OrNode(Node n)172 {173 Operand2 = n;174 }175 176 internal override bool Eval(object val)177 {178 // bitwise OR179 bool satisfy = Operand1.Eval(val) || Operand2.Eval(val);180 return satisfy;181 }182 183 internal override bool ExistEnum(object enumVal)184 {185 bool exist = Operand1.ExistEnum(enumVal) || Operand2.ExistEnum(enumVal);186 return exist;187 }188 }189 190 /// <summary>191 /// AND node for attributes separated by a plus(+) operator.192 /// </summary>193 internal class AndNode : Node194 {195 public Node Operand2 { get; set; }196 197 public AndNode(Node n)198 {199 Operand2 = n;200 }201 202 internal override bool Eval(object val)203 {204 // bitwise AND205 bool satisfy = Operand1.Eval(val) && Operand2.Eval(val);206 return satisfy;207 }208 209 internal override bool ExistEnum(object enumVal)210 {211 bool exist = Operand1.ExistEnum(enumVal) || Operand2.ExistEnum(enumVal);212 return exist;213 }214 }215 216 /// <summary>217 /// NOT node for attribute preceded by an exclamation(!) operator.218 /// </summary>219 internal class NotNode : Node220 {221 internal override bool Eval(object val)222 {223 // bitwise NOT224 bool satisfy = !(Operand1.Eval(val));225 return satisfy;226 }227 228 internal override bool ExistEnum(object enumVal)229 {230 bool exist = Operand1.ExistEnum(enumVal);231 return exist;232 }233 }234 235 /// <summary>236 /// Leaf nodes of the expression tree.237 /// </summary>238 internal class OperandNode : Node239 {240 internal object _operandValue;241 242 public object OperandValue243 {244 get245 {246 return _operandValue;247 }248 249 set250 {251 _operandValue = value;252 }253 }254 255 /// <summary>256 /// Takes a string value and converts to corresponding enum value.257 /// The string value should be checked at parsing stage prior to258 /// tree construction to ensure it is valid.259 /// </summary>260 internal OperandNode(string enumString)261 {262 Type enumType = typeof(T);263 Type underType = Enum.GetUnderlyingType(enumType);264 FieldInfo enumItem = enumType.GetField(enumString);265 _operandValue = LanguagePrimitives.ConvertTo(enumItem.GetValue(enumType), underType, CultureInfo.InvariantCulture);266 }267 268 internal override bool Eval(object val)269 {270 Type underType = Enum.GetUnderlyingType(typeof(T));271 // bitwise AND checking272 bool satisfy = false;273 if (isUnsigned(underType))274 {275 ulong valueToCheck = (ulong)LanguagePrimitives.ConvertTo(val, typeof(ulong), CultureInfo.InvariantCulture);276 ulong operandValue = (ulong)LanguagePrimitives.ConvertTo(_operandValue, typeof(ulong), CultureInfo.InvariantCulture);277 satisfy = (operandValue == (valueToCheck & operandValue));278 }279 // allow for negative enum value input (though it's not recommended practice for flags attribute)280 else281 {282 long valueToCheck = (long)LanguagePrimitives.ConvertTo(val, typeof(long), CultureInfo.InvariantCulture);283 long operandValue = (long)LanguagePrimitives.ConvertTo(_operandValue, typeof(long), CultureInfo.InvariantCulture);284 satisfy = (operandValue == (valueToCheck & operandValue));285 }286 287 return satisfy;288 }289 290 internal override bool ExistEnum(object enumVal)291 {292 Type underType = Enum.GetUnderlyingType(typeof(T));293 // bitwise AND checking294 bool exist = false;295 if (isUnsigned(underType))296 {297 ulong valueToCheck = (ulong)LanguagePrimitives.ConvertTo(enumVal, typeof(ulong), CultureInfo.InvariantCulture);298 ulong operandValue = (ulong)LanguagePrimitives.ConvertTo(_operandValue, typeof(ulong), CultureInfo.InvariantCulture);299 exist = valueToCheck == (valueToCheck & operandValue);300 }301 // allow for negative enum value input (though it's not recommended practice for flags attribute)302 else303 {304 long valueToCheck = (long)LanguagePrimitives.ConvertTo(enumVal, typeof(long), CultureInfo.InvariantCulture);305 long operandValue = (long)LanguagePrimitives.ConvertTo(_operandValue, typeof(long), CultureInfo.InvariantCulture);306 exist = valueToCheck == (valueToCheck & operandValue);307 }308 309 return exist;310 }311 312 private static bool isUnsigned(Type type)313 {314 return (type == typeof(ulong) || type == typeof(uint) || type == typeof(ushort) || type == typeof(byte));315 }316 }317 318 #endregion319 320 #region private members321 322 private readonly Type _underType = null;323 324 #endregion325 326 #region properties327 328 internal Node Root { get; set; } = null;329 330 #endregion331 332 #region public methods333 334 /// <summary>335 /// Evaluate a given flag enum value against the expression.336 /// </summary>337 /// <param name="value">338 /// The flag enum value to be evaluated.339 /// </param>340 /// <returns>341 /// Whether the enum value satisfy the expression.342 /// </returns>343 public bool Evaluate(T value)344 {345 object val = LanguagePrimitives.ConvertTo(value, _underType, CultureInfo.InvariantCulture);346 return Root.Eval(val);347 }348 349 #endregion350 351 #region internal methods352 353 /// <summary>354 /// Given an enum element, check if the element is present in the expression tree,355 /// which is also present in the input expression.356 /// </summary>357 /// <param name="flagName">358 /// The enum element to be examined.359 /// </param>360 /// <returns>361 /// Whether the enum element is present in the expression.362 /// </returns>363 /// <remarks>364 /// The enum value passed in should be a single enum element value,365 /// not a flag enum value with multiple bits set.366 /// </remarks>367 internal bool ExistsInExpression(T flagName)368 {369 bool exist = false;370 object val = LanguagePrimitives.ConvertTo(flagName, _underType, CultureInfo.InvariantCulture);371 exist = Root.ExistEnum(val);372 return exist;373 }374 375 #endregion376 377 #region parser methods378 379 /// <summary>380 /// Takes a string of input tokenize into a list of ordered tokens.381 /// </summary>382 /// <param name="input">383 /// The input argument string,384 /// could be partial input (one element from the argument collection).385 /// </param>386 /// <returns>387 /// A generic list of tokenized input.388 /// </returns>389 private static List<Token> TokenizeInput(string input)390 {391 List<Token> tokenList = new List<Token>();392 int _offset = 0;393 394 while (_offset < input.Length)395 {396 FindNextToken(input, ref _offset);397 if (_offset < input.Length)398 {399 tokenList.Add(GetNextToken(input, ref _offset));400 }401 }402 403 return tokenList;404 }405 406 /// <summary>407 /// Find the start of the next token, skipping white spaces.408 /// </summary>409 /// <param name="input">410 /// Input string411 /// </param>412 /// <param name="_offset">413 /// Current offset position for the string parser.414 /// </param>415 private static void FindNextToken(string input, ref int _offset)416 {417 while (_offset < input.Length)418 {419 char cc = input[_offset++];420 if (!char.IsWhiteSpace(cc))421 {422 _offset--;423 break;424 }425 }426 }427 428 /// <summary>429 /// Given the start (offset) of the next token, traverse through430 /// the string to find the next token, stripping correctly431 /// enclosed quotes.432 /// </summary>433 /// <param name="input">434 /// Input string435 /// </param>436 /// <param name="_offset">437 /// Current offset position for the string parser.438 /// </param>439 /// <returns>440 /// The next token on the input string441 /// </returns>442 private static Token GetNextToken(string input, ref int _offset)443 {444 StringBuilder sb = new StringBuilder();445 // bool singleQuoted = false;446 // bool doubleQuoted = false;447 bool readingIdentifier = false;448 while (_offset < input.Length)449 {450 char cc = input[_offset++];451 if ((cc == ',') || (cc == '+') || (cc == '!'))452 {453 if (!readingIdentifier)454 {455 sb.Append(cc);456 }457 else458 {459 _offset--;460 }461 462 break;463 }464 else465 {466 sb.Append(cc);467 readingIdentifier = true;468 }469 }470 471 string result = sb.ToString().Trim();472 // If resulting identifier is enclosed in paired quotes,473 // remove the only the first pair of quotes from the string474 if (result.Length >= 2 &&475 ((result[0] == '\'' && result[result.Length - 1] == '\'') ||476 (result[0] == '\"' && result[result.Length - 1] == '\"')))477 {478 result = result.Substring(1, result.Length - 2);479 }480 481 result = result.Trim();482 483 // possible empty token because white spaces are enclosed in quotation marks.484 if (string.IsNullOrWhiteSpace(result))485 {486 throw InterpreterError.NewInterpreterException(input, typeof(RuntimeException),487 null, "EmptyTokenString", EnumExpressionEvaluatorStrings.EmptyTokenString,488 EnumMinimumDisambiguation.EnumAllValues(typeof(T)));489 }490 else if (result[0] == '(')491 {492 int matchIndex = input.IndexOf(')', _offset);493 if (result[result.Length - 1] == ')' || matchIndex >= 0)494 {495 throw InterpreterError.NewInterpreterException(input, typeof(RuntimeException),496 null, "NoIdentifierGroupingAllowed", EnumExpressionEvaluatorStrings.NoIdentifierGroupingAllowed);497 }498 }499 500 if (result.Equals(","))501 {502 return (new Token(TokenKind.Or));503 }504 else if (result.Equals("+"))505 {506 return (new Token(TokenKind.And));507 }508 else if (result.Equals("!"))509 {510 return (new Token(TokenKind.Not));511 }512 else513 {514 return (new Token(result));515 }516 }517 518 /// <summary>519 /// Checks syntax errors on input expression,520 /// as well as performing disambiguation for identifiers.521 /// </summary>522 /// <param name="tokenList">523 /// A list of tokenized input.524 /// </param>525 private static void CheckSyntaxError(List<Token> tokenList)526 {527 // Initialize, assuming preceded by OR528 TokenKind previous = TokenKind.Or;529 530 for (int i = 0; i < tokenList.Count; i++)531 {532 Token token = tokenList[i];533 // Not allowed: ... AND/OR AND/OR ...534 // Allowed: ... AND/OR NOT/ID ...535 if (previous == TokenKind.Or || previous == TokenKind.And)536 {537 if ((token.Kind == TokenKind.Or) || (token.Kind == TokenKind.And))538 {539 throw InterpreterError.NewInterpreterException(null, typeof(RuntimeException),540 null, "SyntaxErrorUnexpectedBinaryOperator", EnumExpressionEvaluatorStrings.SyntaxErrorUnexpectedBinaryOperator);541 }542 }543 // Not allowed: ... NOT AND/OR/NOT ...544 // Allowed: ... NOT ID ...545 else if (previous == TokenKind.Not)546 {547 if (token.Kind != TokenKind.Identifier)548 {549 throw InterpreterError.NewInterpreterException(null, typeof(RuntimeException),550 null, "SyntaxErrorIdentifierExpected", EnumExpressionEvaluatorStrings.SyntaxErrorIdentifierExpected);551 }552 }553 // Not allowed: ... ID NOT/ID ...554 // Allowed: ... ID AND/OR ...555 else if (previous == TokenKind.Identifier)556 {557 if ((token.Kind == TokenKind.Identifier) || (token.Kind == TokenKind.Not))558 {559 throw InterpreterError.NewInterpreterException(null, typeof(RuntimeException),560 null, "SyntaxErrorBinaryOperatorExpected", EnumExpressionEvaluatorStrings.SyntaxErrorBinaryOperatorExpected);561 }562 }563 564 if (token.Kind == TokenKind.Identifier)565 {566 string text = token.Text;567 token.Text = EnumMinimumDisambiguation.EnumDisambiguate(text, typeof(T));568 }569 570 previous = token.Kind;571 }572 }573 574 /// <summary>575 /// Takes a list of tokenized input and create the corresponding expression tree.576 /// </summary>577 /// <param name="tokenList">578 /// Tokenized list of the input string.579 /// </param>580 private static Node ConstructExpressionTree(List<Token> tokenList)581 {582 bool notFlag = false;583 Queue<Node> andQueue = new Queue<Node>();584 Queue<Node> orQueue = new Queue<Node>();585 586 for (int i = 0; i < tokenList.Count; i++)587 {588 Token token = tokenList[i];589 TokenKind kind = token.Kind;590 if (kind == TokenKind.Identifier)591 {592 Node idNode = new OperandNode(token.Text);593 if (notFlag) // identifier preceded by NOT594 {595 Node notNode = new NotNode();596 notNode.Operand1 = idNode;597 notFlag = false;598 andQueue.Enqueue(notNode);599 }600 else601 {602 andQueue.Enqueue(idNode);603 }604 }605 else if (kind == TokenKind.Not)606 {607 notFlag = true;608 }609 else if (kind == TokenKind.And)610 {611 // do nothing612 }613 else if (kind == TokenKind.Or)614 {615 // Dequeue all nodes from AND queue,616 // create the AND tree, then add to the OR queue.617 Node andCurrent = andQueue.Dequeue();618 while (andQueue.Count > 0)619 {620 Node andNode = new AndNode(andCurrent);621 andNode.Operand1 = andQueue.Dequeue();622 andCurrent = andNode;623 }624 625 orQueue.Enqueue(andCurrent);626 }627 }628 629 // Dequeue all nodes from OR queue,630 // create the OR tree (final expression tree)631 Node orCurrent = orQueue.Dequeue();632 while (orQueue.Count > 0)633 {634 Node orNode = new OrNode(orCurrent);635 orNode.Operand1 = orQueue.Dequeue();636 orCurrent = orNode;637 }638 639 return orCurrent;640 }641 642 #endregion643 }644}645