MegaBites-AI/Windows-powershell
0308
1// Copyright (c) Microsoft Corporation.2// Licensed under the MIT License.3 4#pragma warning disable 1634, 16915 6using System.Buffers;7using System.Collections.Generic;8using System.Diagnostics.Contracts;9using System.Globalization;10using System.Linq;11using System.Text;12using System.Text.RegularExpressions;13using System.Management.Automation.Internal;14using System.Runtime.Serialization;15using Dbg = System.Management.Automation.Diagnostics;16 17namespace System.Management.Automation18{19 /// <summary>20 /// Provides enumerated values to use to set wildcard pattern21 /// matching options.22 /// </summary>23 [Flags]24 public enum WildcardOptions25 {26 /// <summary>27 /// Indicates that no special processing is required.28 /// </summary>29 None = 0,30 31 /// <summary>32 /// Specifies that the wildcard pattern is compiled to an assembly.33 /// This yields faster execution but increases startup time.34 /// </summary>35 Compiled = 1,36 37 /// <summary>38 /// Specifies case-insensitive matching.39 /// </summary>40 IgnoreCase = 2,41 42 /// <summary>43 /// Specifies culture-invariant matching.44 /// </summary>45 CultureInvariant = 446 }47 48 /// <summary>49 /// Represents a wildcard pattern.50 /// </summary>51 public sealed class WildcardPattern52 {53 // char that escapes special chars54 private const char escapeChar = '`';55 56 // Threshold for stack allocation.57 // The size is less than MaxShortPath = 260.58 private const int StackAllocThreshold = 256;59 60 // chars that are considered special in a wildcard pattern61 private const string SpecialChars = "*?[]`";62 63 // we convert a wildcard pattern to a predicate64 private Predicate<string> _isMatch;65 66 // static match-all delegate that is shared by all WildcardPattern instances67 private static readonly Predicate<string> s_matchAll = _ => true;68 69 // wildcard pattern70 internal string Pattern { get; }71 72 // Options that control match behavior.73 // Default is WildcardOptions.None.74 internal WildcardOptions Options { get; }75 76 /// <summary>77 /// Initializes and instance of the WildcardPattern class78 /// for the specified wildcard pattern.79 /// </summary>80 /// <param name="pattern">The wildcard pattern to match.</param>81 /// <returns>The constructed WildcardPattern object.</returns>82 public WildcardPattern(string pattern) : this(pattern, WildcardOptions.None)83 {84 }85 86 /// <summary>87 /// Initializes an instance of the WildcardPattern class for88 /// the specified wildcard pattern expression, with options89 /// that modify the pattern.90 /// </summary>91 /// <param name="pattern">The wildcard pattern to match.</param>92 /// <param name="options">Wildcard options.</param>93 /// <returns>The constructed WildcardPattern object.</returns>94 public WildcardPattern(string pattern, WildcardOptions options)95 {96 if (pattern == null)97 {98 throw PSTraceSource.NewArgumentNullException(nameof(pattern));99 }100 101 Pattern = pattern;102 Options = options;103 }104 105 private static readonly WildcardPattern s_matchAllIgnoreCasePattern = new WildcardPattern("*", WildcardOptions.None);106 107 /// <summary>108 /// Create a new WildcardPattern, or return an already created one.109 /// </summary>110 /// <param name="pattern">The pattern.</param>111 /// <param name="options"></param>112 /// <returns></returns>113 public static WildcardPattern Get(string pattern, WildcardOptions options)114 {115 if (pattern == null)116 throw PSTraceSource.NewArgumentNullException(nameof(pattern));117 118 if (pattern.Length == 1 && pattern[0] == '*')119 return s_matchAllIgnoreCasePattern;120 121 return new WildcardPattern(pattern, options);122 }123 124 /// <summary>125 /// Instantiate internal regex member if not already done.126 /// </summary>127 /// <returns>True on success, false otherwise.</returns>128 private void Init()129 {130 StringComparison GetStringComparison()131 {132 StringComparison stringComparison;133 if (Options.HasFlag(WildcardOptions.IgnoreCase))134 {135 stringComparison = Options.HasFlag(WildcardOptions.CultureInvariant)136 ? StringComparison.InvariantCultureIgnoreCase137 : CultureInfo.CurrentCulture.Name.Equals("en-US-POSIX", StringComparison.OrdinalIgnoreCase)138 // The collation behavior of the POSIX locale (also known as the C locale) is case sensitive.139 // For this specific locale, we use 'OrdinalIgnoreCase'.140 ? StringComparison.OrdinalIgnoreCase141 : StringComparison.CurrentCultureIgnoreCase;142 }143 else144 {145 stringComparison = Options.HasFlag(WildcardOptions.CultureInvariant)146 ? StringComparison.InvariantCulture147 : StringComparison.CurrentCulture;148 }149 150 return stringComparison;151 }152 153 if (_isMatch != null)154 {155 return;156 }157 158 if (Pattern.Length == 1 && Pattern[0] == '*')159 {160 _isMatch = s_matchAll;161 return;162 }163 164 int index = Pattern.AsSpan().IndexOfAny(SpecialChars);165 if (index < 0)166 {167 // No special characters present in the pattern, so we can just do a string comparison.168 _isMatch = str => string.Equals(str, Pattern, GetStringComparison());169 return;170 }171 172 if (index == Pattern.Length - 1 && Pattern[index] == '*')173 {174 // No special characters present in the pattern before last position and last character is asterisk.175 var patternWithoutAsterisk = Pattern.AsMemory(0, index);176 _isMatch = str => str.AsSpan().StartsWith(patternWithoutAsterisk.Span, GetStringComparison());177 return;178 }179 180 var matcher = new WildcardPatternMatcher(this);181 _isMatch = matcher.IsMatch;182 }183 184 /// <summary>185 /// Indicates whether the wildcard pattern specified in the WildcardPattern186 /// constructor finds a match in the input string.187 /// </summary>188 /// <param name="input">The string to search for a match.</param>189 /// <returns>True if the wildcard pattern finds a match; otherwise, false.</returns>190 public bool IsMatch(string input)191 {192 Init();193 return input != null && _isMatch(input);194 }195 196 /// <summary>197 /// Converts the wildcard pattern to its regular expression equivalent.198 /// </summary>199 /// <returns>200 /// A <see cref="Regex"/> object that represents the regular expression equivalent of the wildcard pattern.201 /// The regex is configured with options matching the wildcard pattern's options.202 /// </returns>203 /// <remarks>204 /// This method converts a wildcard pattern to a regular expression.205 /// The conversion follows these rules:206 /// <list type="bullet">207 /// <item><description>* (asterisk) converts to .* (matches any string)</description></item>208 /// <item><description>? (question mark) converts to . (matches any single character)</description></item>209 /// <item><description>[abc] (bracket expression) converts to [abc] (matches any character in the set)</description></item>210 /// <item><description>Literal characters are escaped as needed for regex</description></item>211 /// </list>212 /// </remarks>213 /// <example>214 /// <code>215 /// var pattern = new WildcardPattern("*.txt");216 /// Regex regex = pattern.ToRegex();217 /// // regex.ToString() returns: "\.txt$"218 /// </code>219 /// </example>220 public Regex ToRegex()221 {222 return WildcardPatternToRegexParser.Parse(this);223 }224 225 /// <summary>226 /// Escape special chars, except for those specified in <paramref name="charsNotToEscape"/>, in a string by replacing them with their escape codes.227 /// </summary>228 /// <param name="pattern">The input string containing the text to convert.</param>229 /// <param name="charsNotToEscape">Array of characters that not to escape.</param>230 /// <returns>231 /// A string of characters with any metacharacters, except for those specified in <paramref name="charsNotToEscape"/>, converted to their escaped form.232 /// </returns>233 internal static string Escape(string pattern, char[] charsNotToEscape)234 {235 if (pattern == null)236 {237 throw PSTraceSource.NewArgumentNullException(nameof(pattern));238 }239 240 if (charsNotToEscape == null)241 {242 throw PSTraceSource.NewArgumentNullException(nameof(charsNotToEscape));243 }244 245 if (pattern == string.Empty)246 {247 return pattern;248 }249 250 Span<char> temp = pattern.Length < StackAllocThreshold ? stackalloc char[pattern.Length * 2 + 1] : new char[pattern.Length * 2 + 1];251 int tempIndex = 0;252 253 for (int i = 0; i < pattern.Length; i++)254 {255 char ch = pattern[i];256 257 //258 // if it is a special char, escape it259 //260 if (SpecialChars.Contains(ch) && !charsNotToEscape.Contains(ch))261 {262 temp[tempIndex++] = escapeChar;263 }264 265 temp[tempIndex++] = ch;266 }267 268 string s = null;269 270 if (tempIndex == pattern.Length)271 {272 s = pattern;273 }274 else275 {276 s = new string(temp.Slice(0, tempIndex));277 }278 279 return s;280 }281 282 /// <summary>283 /// Escape special chars in a string by replacing them with their escape codes.284 /// </summary>285 /// <param name="pattern">The input string containing the text to convert.</param>286 /// <returns>287 /// A string of characters with any metacharacters converted to their escaped form.288 /// </returns>289 public static string Escape(string pattern)290 {291 return Escape(pattern, Array.Empty<char>());292 }293 294 /// <summary>295 /// Checks to see if the given string has any wild card characters in it.296 /// </summary>297 /// <param name="pattern">298 /// String which needs to be checked for the presence of wildcard chars299 /// </param>300 /// <returns>True if the string has wild card chars, false otherwise..</returns>301 /// <remarks>302 /// Currently { '*', '?', '[' } are considered wild card chars and303 /// '`' is the escape character.304 /// </remarks>305 public static bool ContainsWildcardCharacters(string pattern)306 {307 if (string.IsNullOrEmpty(pattern))308 {309 return false;310 }311 312 bool result = false;313 314 for (int index = 0; index < pattern.Length; ++index)315 {316 if (IsWildcardChar(pattern[index]))317 {318 result = true;319 break;320 }321 322 // If it is an escape character then advance past323 // the next character324 325 if (pattern[index] == escapeChar)326 {327 ++index;328 }329 }330 331 return result;332 }333 334 /// <summary>335 /// Checks if the string contains a left bracket "[" followed by a right bracket "]" after any number of characters.336 /// </summary>337 /// <param name="pattern"> The string to check.</param>338 /// <returns>Returns true if the string contains both a left and right bracket "[" "]" and if the right bracket comes after the left bracket.</returns>339 internal static bool ContainsRangeWildcard(string pattern)340 {341 if (string.IsNullOrEmpty(pattern))342 {343 return false;344 }345 346 bool foundStart = false;347 bool result = false;348 for (int index = 0; index < pattern.Length; ++index)349 {350 if (pattern[index] is '[')351 {352 foundStart = true;353 continue;354 }355 356 if (foundStart && pattern[index] is ']')357 {358 result = true;359 break;360 }361 362 if (pattern[index] == escapeChar)363 {364 ++index;365 }366 }367 368 return result;369 }370 371 /// <summary>372 /// Unescapes any escaped characters in the input string.373 /// </summary>374 /// <param name="pattern">375 /// The input string containing the text to convert.376 /// </param>377 /// <returns>378 /// A string of characters with any escaped characters379 /// converted to their unescaped form.380 /// </returns>381 /// <exception cref="ArgumentNullException">382 /// If <paramref name="pattern"/> is null.383 /// </exception>384 public static string Unescape(string pattern)385 {386 if (pattern == null)387 {388 throw PSTraceSource.NewArgumentNullException(nameof(pattern));389 }390 391 if (pattern == string.Empty)392 {393 return pattern;394 }395 396 Span<char> temp = pattern.Length < StackAllocThreshold ? stackalloc char[pattern.Length] : new char[pattern.Length];397 398 int tempIndex = 0;399 bool prevCharWasEscapeChar = false;400 401 for (int i = 0; i < pattern.Length; i++)402 {403 char ch = pattern[i];404 405 if (ch == escapeChar)406 {407 if (prevCharWasEscapeChar)408 {409 temp[tempIndex++] = ch;410 prevCharWasEscapeChar = false;411 }412 else413 {414 prevCharWasEscapeChar = true;415 }416 417 continue;418 }419 420 if (prevCharWasEscapeChar)421 {422 if (!IsWildcardChar(ch))423 {424 temp[tempIndex++] = escapeChar;425 }426 }427 428 temp[tempIndex++] = ch;429 prevCharWasEscapeChar = false;430 }431 432 // Need to account for a trailing escape character as a real433 // character434 435 if (prevCharWasEscapeChar)436 {437 temp[tempIndex++] = escapeChar;438 prevCharWasEscapeChar = false;439 }440 441 string s = null;442 443 if (tempIndex == pattern.Length)444 {445 s = pattern;446 }447 else448 {449 s = new string(temp.Slice(0, tempIndex));450 }451 452 return s;453 }454 455 private static bool IsWildcardChar(char ch)456 {457 return (ch == '*') || (ch == '?') || (ch == '[') || (ch == ']');458 }459 460 /// <summary>461 /// Converts this wildcard to a string that can be used as a right-hand-side operand of the LIKE operator of WQL.462 /// For example: "a*" will be converted to "a%".463 /// </summary>464 /// <returns></returns>465 public string ToWql()466 {467 bool needsClientSideFiltering;468 string likeOperand = Microsoft.PowerShell.Cmdletization.Cim.WildcardPatternToCimQueryParser.Parse(this, out needsClientSideFiltering);469 if (!needsClientSideFiltering)470 {471 return likeOperand;472 }473 else474 {475 throw new PSInvalidCastException(476 "UnsupportedWildcardToWqlConversion",477 null,478 ExtendedTypeSystem.InvalidCastException,479 this.Pattern,480 this.GetType().FullName,481 "WQL");482 }483 }484 }485 486 /// <summary>487 /// Thrown when a wildcard pattern is invalid.488 /// </summary>489 public class WildcardPatternException : RuntimeException490 {491 /// <summary>492 /// Constructor for class WildcardPatternException that takes493 /// an ErrorRecord to use in constructing this exception.494 /// </summary>495 /// <remarks>This is the recommended constructor to use for this exception.</remarks>496 /// <param name="errorRecord">497 /// ErrorRecord object containing additional information about the error condition.498 /// </param>499 /// <returns>Constructed object.</returns>500 internal WildcardPatternException(ErrorRecord errorRecord)501 : base(RetrieveMessage(errorRecord))502 {503 ArgumentNullException.ThrowIfNull(errorRecord);504 505 _errorRecord = errorRecord;506 }507 508 [NonSerialized]509 private readonly ErrorRecord _errorRecord;510 511 /// <summary>512 /// Constructs an instance of the WildcardPatternException object.513 /// </summary>514 public WildcardPatternException()515 {516 }517 518 /// <summary>519 /// Constructs an instance of the WildcardPatternException object taking520 /// a message parameter to use in constructing the exception.521 /// </summary>522 /// <param name="message">The string to use as the exception message.</param>523 public WildcardPatternException(string message) : base(message)524 {525 }526 527 /// <summary>528 /// Constructor for class WildcardPatternException that takes both a message to use529 /// and an inner exception to include in this object.530 /// </summary>531 /// <param name="message">The exception message to use.</param>532 /// <param name="innerException">The innerException object to encapsulate.</param>533 public WildcardPatternException(string message,534 Exception innerException)535 : base(message, innerException)536 {537 }538 539 /// <summary>540 /// Constructor for class WildcardPatternException for serialization.541 /// </summary>542 /// <param name="info">Serialization information.</param>543 /// <param name="context">Streaming context.</param>544 [Obsolete("Legacy serialization support is deprecated since .NET 8", DiagnosticId = "SYSLIB0051")]545 protected WildcardPatternException(SerializationInfo info,546 StreamingContext context)547 {548 throw new NotSupportedException();549 }550 }551 552 /// <summary>553 /// A base class for parsers of <see cref="WildcardPattern"/> patterns.554 /// </summary>555 internal abstract class WildcardPatternParser556 {557 /// <summary>558 /// Called from <see cref="Parse"/> method to indicate559 /// the beginning of the wildcard pattern.560 /// Default implementation simply returns.561 /// </summary>562 /// <param name="pattern">563 /// <see cref="WildcardPattern"/> object that includes both564 /// the text of the pattern (<see cref="WildcardPattern.Pattern"/>)565 /// and the pattern options (<see cref="WildcardPattern.Options"/>)566 /// </param>567 protected virtual void BeginWildcardPattern(WildcardPattern pattern)568 {569 }570 571 /// <summary>572 /// Called from <see cref="Parse"/> method to indicate that the next573 /// part of the pattern should match574 /// a literal character <paramref name="c"/>.575 /// </summary>576 protected abstract void AppendLiteralCharacter(char c);577 578 /// <summary>579 /// Called from <see cref="Parse"/> method to indicate that the next580 /// part of the pattern should match581 /// any string, including an empty string.582 /// </summary>583 protected abstract void AppendAsterix();584 585 /// <summary>586 /// Called from <see cref="Parse"/> method to indicate that the next587 /// part of the pattern should match588 /// any single character.589 /// </summary>590 protected abstract void AppendQuestionMark();591 592 /// <summary>593 /// Called from <see cref="Parse"/> method to indicate the end of the wildcard pattern.594 /// Default implementation simply returns.595 /// </summary>596 protected virtual void EndWildcardPattern()597 {598 }599 600 /// <summary>601 /// Called from <see cref="Parse"/> method to indicate602 /// the beginning of a bracket expression.603 /// </summary>604 /// <remarks>605 /// Bracket expressions of <see cref="WildcardPattern"/> are606 /// a greatly simplified version of bracket expressions of POSIX wildcards607 /// (https://www.opengroup.org/onlinepubs/9699919799/functions/fnmatch.html).608 /// Only literal characters and character ranges are supported.609 /// Negation (with either '!' or '^' characters),610 /// character classes ([:alpha:])611 /// and other advanced features are not supported.612 /// </remarks>613 protected abstract void BeginBracketExpression();614 615 /// <summary>616 /// Called from <see cref="Parse"/> method to indicate that the bracket expression617 /// should include a literal character <paramref name="c"/>.618 /// </summary>619 protected abstract void AppendLiteralCharacterToBracketExpression(char c);620 621 /// <summary>622 /// Called from <see cref="Parse"/> method to indicate that the bracket expression623 /// should include all characters from character range624 /// starting at <paramref name="startOfCharacterRange"/>625 /// and ending at <paramref name="endOfCharacterRange"/>626 /// </summary>627 protected abstract void AppendCharacterRangeToBracketExpression(628 char startOfCharacterRange,629 char endOfCharacterRange);630 631 /// <summary>632 /// Called from <see cref="Parse"/> method to indicate the end of a bracket expression.633 /// </summary>634 protected abstract void EndBracketExpression();635 636 /// <summary>637 /// PowerShell v1 and v2 treats all characters inside638 /// <paramref name="brackedExpressionContents"/> as literal characters,639 /// except '-' sign which denotes a range. In particular it means that640 /// '^', '[', ']' are escaped within the bracket expression and don't641 /// have their regex-y meaning.642 /// </summary>643 /// <param name="brackedExpressionContents"></param>644 /// <param name="bracketExpressionOperators"></param>645 /// <param name="pattern"></param>646 /// <remarks>647 /// This method should be kept "internal"648 /// </remarks>649 internal void AppendBracketExpression(string brackedExpressionContents, string bracketExpressionOperators, string pattern)650 {651 this.BeginBracketExpression();652 653 int i = 0;654 while (i < brackedExpressionContents.Length)655 {656 if (((i + 2) < brackedExpressionContents.Length) &&657 (bracketExpressionOperators[i + 1] == '-'))658 {659 char lowerBound = brackedExpressionContents[i];660 char upperBound = brackedExpressionContents[i + 2];661 i += 3;662 663 if (lowerBound > upperBound)664 {665 throw NewWildcardPatternException(pattern);666 }667 668 this.AppendCharacterRangeToBracketExpression(lowerBound, upperBound);669 }670 else671 {672 this.AppendLiteralCharacterToBracketExpression(brackedExpressionContents[i]);673 i++;674 }675 }676 677 this.EndBracketExpression();678 }679 680 /// <summary>681 /// Parses <paramref name="pattern"/>, calling appropriate overloads682 /// in <paramref name="parser"/>683 /// </summary>684 /// <param name="pattern">Pattern to parse.</param>685 /// <param name="parser">Parser to call back.</param>686 public static void Parse(WildcardPattern pattern, WildcardPatternParser parser)687 {688 parser.BeginWildcardPattern(pattern);689 690 bool previousCharacterIsAnEscape = false;691 bool previousCharacterStartedBracketExpression = false;692 bool insideCharacterRange = false;693 StringBuilder characterRangeContents = null;694 StringBuilder characterRangeOperators = null;695 foreach (char c in pattern.Pattern)696 {697 if (insideCharacterRange)698 {699 if (c == ']' && !previousCharacterStartedBracketExpression && !previousCharacterIsAnEscape)700 {701 // An unescaped closing square bracket closes the character set. In other702 // words, there are no nested square bracket expressions703 // This is different than the POSIX spec704 // (at https://www.opengroup.org/onlinepubs/9699919799/functions/fnmatch.html),705 // but we are keeping this behavior for back-compatibility.706 707 insideCharacterRange = false;708 parser.AppendBracketExpression(characterRangeContents.ToString(), characterRangeOperators.ToString(), pattern.Pattern);709 characterRangeContents = null;710 characterRangeOperators = null;711 }712 else if (c != '`' || previousCharacterIsAnEscape)713 {714 characterRangeContents.Append(c);715 characterRangeOperators.Append((c == '-') && !previousCharacterIsAnEscape ? '-' : ' ');716 }717 718 previousCharacterStartedBracketExpression = false;719 }720 else721 {722 if (c == '*' && !previousCharacterIsAnEscape)723 {724 parser.AppendAsterix();725 }726 else if (c == '?' && !previousCharacterIsAnEscape)727 {728 parser.AppendQuestionMark();729 }730 else if (c == '[' && !previousCharacterIsAnEscape)731 {732 insideCharacterRange = true;733 characterRangeContents = new StringBuilder();734 characterRangeOperators = new StringBuilder();735 previousCharacterStartedBracketExpression = true;736 }737 else if (c != '`' || previousCharacterIsAnEscape)738 {739 parser.AppendLiteralCharacter(c);740 }741 }742 743 previousCharacterIsAnEscape = (c == '`') && (!previousCharacterIsAnEscape);744 }745 746 if (insideCharacterRange)747 {748 throw NewWildcardPatternException(pattern.Pattern);749 }750 751 if (previousCharacterIsAnEscape)752 {753 if (!pattern.Pattern.Equals("`", StringComparison.Ordinal)) // Win7 backcompatibility requires treating '`' pattern as '' pattern754 {755 parser.AppendLiteralCharacter(pattern.Pattern[pattern.Pattern.Length - 1]);756 }757 }758 759 parser.EndWildcardPattern();760 }761 762 internal static WildcardPatternException NewWildcardPatternException(string invalidPattern)763 {764 string message =765 StringUtil.Format(WildcardPatternStrings.InvalidPattern,766 invalidPattern767 );768 769 ParentContainsErrorRecordException pce =770 new ParentContainsErrorRecordException(message);771 772 ErrorRecord er =773 new ErrorRecord(pce,774 "WildcardPattern_Invalid",775 ErrorCategory.InvalidArgument,776 null);777 778 WildcardPatternException e =779 new WildcardPatternException(er);780 781 return e;782 }783 }784 785 /// <summary>786 /// Convert a string with wild cards into its equivalent regex.787 /// </summary>788 /// <remarks>789 /// A list of glob patterns and their equivalent regexes790 ///791 /// glob pattern regex792 /// ------------- -------793 /// *foo* foo794 /// foo ^foo$795 /// foo*bar ^foo.*bar$796 /// foo`*bar ^foo\*bar$797 ///798 /// for a more cases see the unit-test file RegexTest.cs799 /// </remarks>800 internal class WildcardPatternToRegexParser : WildcardPatternParser801 {802 private StringBuilder _regexPattern;803 private RegexOptions _regexOptions;804 805 private const string regexChars = "()[.?*{}^$+|\\"; // ']' is missing on purpose806 807 private static bool IsRegexChar(char ch)808 {809 for (int i = 0; i < regexChars.Length; i++)810 {811 if (ch == regexChars[i])812 {813 return true;814 }815 }816 817 return false;818 }819 820 internal static RegexOptions TranslateWildcardOptionsIntoRegexOptions(WildcardOptions options)821 {822 RegexOptions regexOptions = RegexOptions.Singleline;823 824 if ((options & WildcardOptions.Compiled) != 0)825 {826 regexOptions |= RegexOptions.Compiled;827 }828 829 if ((options & WildcardOptions.IgnoreCase) != 0)830 {831 regexOptions |= RegexOptions.IgnoreCase;832 }833 834 if ((options & WildcardOptions.CultureInvariant) == WildcardOptions.CultureInvariant)835 {836 regexOptions |= RegexOptions.CultureInvariant;837 }838 839 return regexOptions;840 }841 842 protected override void BeginWildcardPattern(WildcardPattern pattern)843 {844 _regexPattern = new StringBuilder(pattern.Pattern.Length * 2 + 2);845 _regexPattern.Append('^');846 847 _regexOptions = TranslateWildcardOptionsIntoRegexOptions(pattern.Options);848 }849 850 internal static void AppendLiteralCharacter(StringBuilder regexPattern, char c)851 {852 if (IsRegexChar(c))853 {854 regexPattern.Append('\\');855 }856 857 regexPattern.Append(c);858 }859 860 protected override void AppendLiteralCharacter(char c)861 {862 AppendLiteralCharacter(_regexPattern, c);863 }864 865 protected override void AppendAsterix()866 {867 _regexPattern.Append(".*");868 }869 870 protected override void AppendQuestionMark()871 {872 _regexPattern.Append('.');873 }874 875 protected override void EndWildcardPattern()876 {877 _regexPattern.Append('$');878 879 // lines below are not strictly necessary and are included to preserve880 // wildcard->regex conversion from PS v1 (i.e. not to break unit tests881 // and not to break backcompatibility).882 string regexPatternString = _regexPattern.ToString();883 if (regexPatternString.Equals("^.*$", StringComparison.Ordinal))884 {885 _regexPattern.Remove(0, 4);886 }887 else888 {889 if (regexPatternString.StartsWith("^.*", StringComparison.Ordinal))890 {891 _regexPattern.Remove(0, 3);892 }893 894 if (regexPatternString.EndsWith(".*$", StringComparison.Ordinal))895 {896 _regexPattern.Remove(_regexPattern.Length - 3, 3);897 }898 }899 }900 901 protected override void BeginBracketExpression()902 {903 _regexPattern.Append('[');904 }905 906 internal static void AppendLiteralCharacterToBracketExpression(StringBuilder regexPattern, char c)907 {908 if (c == '[')909 {910 regexPattern.Append('[');911 }912 else if (c == ']')913 {914 regexPattern.Append(@"\]");915 }916 else if (c == '-')917 {918 regexPattern.Append(@"\x2d");919 }920 else921 {922 AppendLiteralCharacter(regexPattern, c);923 }924 }925 926 protected override void AppendLiteralCharacterToBracketExpression(char c)927 {928 AppendLiteralCharacterToBracketExpression(_regexPattern, c);929 }930 931 internal static void AppendCharacterRangeToBracketExpression(932 StringBuilder regexPattern,933 char startOfCharacterRange,934 char endOfCharacterRange)935 {936 AppendLiteralCharacterToBracketExpression(regexPattern, startOfCharacterRange);937 regexPattern.Append('-');938 AppendLiteralCharacterToBracketExpression(regexPattern, endOfCharacterRange);939 }940 941 protected override void AppendCharacterRangeToBracketExpression(942 char startOfCharacterRange,943 char endOfCharacterRange)944 {945 AppendCharacterRangeToBracketExpression(_regexPattern, startOfCharacterRange, endOfCharacterRange);946 }947 948 protected override void EndBracketExpression()949 {950 _regexPattern.Append(']');951 }952 953 /// <summary>954 /// Parses a <paramref name="wildcardPattern"/> into a <see cref="Regex"/>955 /// </summary>956 /// <param name="wildcardPattern">Wildcard pattern to parse.</param>957 /// <returns>Regular expression equivalent to <paramref name="wildcardPattern"/></returns>958 public static Regex Parse(WildcardPattern wildcardPattern)959 {960 WildcardPatternToRegexParser parser = new WildcardPatternToRegexParser();961 WildcardPatternParser.Parse(wildcardPattern, parser);962 try963 {964 return ParserOps.NewRegex(parser._regexPattern.ToString(), parser._regexOptions);965 }966 catch (ArgumentException)967 {968 throw WildcardPatternParser.NewWildcardPatternException(wildcardPattern.Pattern);969 }970 }971 }972 973 internal class WildcardPatternMatcher974 {975 private readonly PatternElement[] _patternElements;976 private readonly CharacterNormalizer _characterNormalizer;977 978 internal WildcardPatternMatcher(WildcardPattern wildcardPattern)979 {980 _characterNormalizer = new CharacterNormalizer(wildcardPattern.Options);981 _patternElements = MyWildcardPatternParser.Parse(982 wildcardPattern,983 _characterNormalizer);984 }985 986 internal bool IsMatch(string str)987 {988 // - each state of NFA is represented by (patternPosition, stringPosition) tuple989 // - state transitions are documented in990 // ProcessStringCharacter and ProcessEndOfString methods991 // - the algorithm below tries to see if there is a path992 // from (0, 0) to (lengthOfPattern, lengthOfString)993 // - this is a regular graph traversal994 // - there are O(1) edges per node (at most 2 edges)995 // so the whole graph traversal takes O(number of nodes in the graph) =996 // = O(lengthOfPattern * lengthOfString) time997 // - for efficient remembering which states have already been visited,998 // the traversal goes methodically from beginning to end of the string999 // therefore requiring only O(lengthOfPattern) memory for remembering1000 // which states have been already visited1001 // - Wikipedia calls this algorithm the "NFA" algorithm at1002 // https://en.wikipedia.org/wiki/Regular_expression#Implementations_and_running_times1003 1004 var patternPositionsForCurrentStringPosition =1005 new PatternPositionsVisitor(_patternElements.Length);1006 patternPositionsForCurrentStringPosition.Add(0);1007 1008 var patternPositionsForNextStringPosition =1009 new PatternPositionsVisitor(_patternElements.Length);1010 1011 try1012 {1013 for (int currentStringPosition = 0;1014 currentStringPosition < str.Length;1015 currentStringPosition++)1016 {1017 char currentStringCharacter = _characterNormalizer.Normalize(str[currentStringPosition]);1018 patternPositionsForCurrentStringPosition.StringPosition = currentStringPosition;1019 patternPositionsForNextStringPosition.StringPosition = currentStringPosition + 1;1020 1021 int patternPosition;1022 while (patternPositionsForCurrentStringPosition.MoveNext(out patternPosition))1023 {1024 _patternElements[patternPosition].ProcessStringCharacter(1025 currentStringCharacter,1026 patternPosition,1027 patternPositionsForCurrentStringPosition,1028 patternPositionsForNextStringPosition);1029 }1030 1031 // swap patternPositionsForCurrentStringPosition1032 // with patternPositionsForNextStringPosition1033 var tmp = patternPositionsForCurrentStringPosition;1034 patternPositionsForCurrentStringPosition = patternPositionsForNextStringPosition;1035 patternPositionsForNextStringPosition = tmp;1036 }1037 1038 int patternPosition2;1039 while (patternPositionsForCurrentStringPosition.MoveNext(out patternPosition2))1040 {1041 _patternElements[patternPosition2].ProcessEndOfString(1042 patternPosition2,1043 patternPositionsForCurrentStringPosition);1044 }1045 1046 return patternPositionsForCurrentStringPosition.ReachedEndOfPattern;1047 }1048 finally1049 {1050 patternPositionsForCurrentStringPosition.Dispose();1051 patternPositionsForNextStringPosition.Dispose();1052 }1053 }1054 1055 private sealed class PatternPositionsVisitor : IDisposable1056 {1057 private readonly int _lengthOfPattern;1058 1059 private readonly int[] _isPatternPositionVisitedMarker;1060 1061 private readonly int[] _patternPositionsForFurtherProcessing;1062 private int _patternPositionsForFurtherProcessingCount;1063 1064 public PatternPositionsVisitor(int lengthOfPattern)1065 {1066 Dbg.Assert(lengthOfPattern >= 0, "Caller should verify lengthOfPattern >= 0");1067 1068 _lengthOfPattern = lengthOfPattern;1069 1070 _isPatternPositionVisitedMarker = ArrayPool<int>.Shared.Rent(_lengthOfPattern + 1);1071 for (int i = 0; i <= _lengthOfPattern; i++)1072 {1073 _isPatternPositionVisitedMarker[i] = -1;1074 }1075 1076 _patternPositionsForFurtherProcessing = ArrayPool<int>.Shared.Rent(_lengthOfPattern);1077 _patternPositionsForFurtherProcessingCount = 0;1078 }1079 1080 public void Dispose()1081 {1082 ArrayPool<int>.Shared.Return(_isPatternPositionVisitedMarker, clearArray: true);1083 ArrayPool<int>.Shared.Return(_patternPositionsForFurtherProcessing, clearArray: true);1084 }1085 1086 public int StringPosition { private get; set; }1087 1088 public void Add(int patternPosition)1089 {1090 Dbg.Assert(patternPosition >= 0, "Caller should verify patternPosition >= 0");1091 Dbg.Assert(1092 patternPosition <= _lengthOfPattern,1093 "Caller should verify patternPosition <= this._lengthOfPattern");1094 1095 // is patternPosition already visited?1096 if (_isPatternPositionVisitedMarker[patternPosition] == this.StringPosition)1097 {1098 return;1099 }1100 1101 // mark patternPosition as visited1102 _isPatternPositionVisitedMarker[patternPosition] = this.StringPosition;1103 1104 // add patternPosition to the queue for further processing1105 if (patternPosition < _lengthOfPattern)1106 {1107 _patternPositionsForFurtherProcessing[_patternPositionsForFurtherProcessingCount] = patternPosition;1108 _patternPositionsForFurtherProcessingCount++;1109 Dbg.Assert(1110 _patternPositionsForFurtherProcessingCount <= _lengthOfPattern,1111 "There should never be more elements in the queue than the length of the pattern");1112 }1113 }1114 1115 public bool ReachedEndOfPattern1116 {1117 get1118 {1119 return _isPatternPositionVisitedMarker[_lengthOfPattern] >= this.StringPosition;1120 }1121 }1122 1123 // non-virtual MoveNext is more performant1124 // than implementing IEnumerable / virtual MoveNext1125 public bool MoveNext(out int patternPosition)1126 {1127 Dbg.Assert(1128 _patternPositionsForFurtherProcessingCount >= 0,1129 "There should never be more elements in the queue than the length of the pattern");1130 1131 if (_patternPositionsForFurtherProcessingCount == 0)1132 {1133 patternPosition = -1;1134 return false;1135 }1136 1137 _patternPositionsForFurtherProcessingCount--;1138 patternPosition = _patternPositionsForFurtherProcessing[_patternPositionsForFurtherProcessingCount];1139 return true;1140 }1141 }1142 1143 private abstract class PatternElement1144 {1145 public abstract void ProcessStringCharacter(1146 char currentStringCharacter,1147 int currentPatternPosition,1148 PatternPositionsVisitor patternPositionsForCurrentStringPosition,1149 PatternPositionsVisitor patternPositionsForNextStringPosition);1150 1151 public abstract void ProcessEndOfString(1152 int currentPatternPosition,1153 PatternPositionsVisitor patternPositionsForEndOfStringPosition);1154 }1155 1156 private class QuestionMarkElement : PatternElement1157 {1158 public override void ProcessStringCharacter(1159 char currentStringCharacter,1160 int currentPatternPosition,1161 PatternPositionsVisitor patternPositionsForCurrentStringPosition,1162 PatternPositionsVisitor patternPositionsForNextStringPosition)1163 {1164 // '?' : (patternPosition, stringPosition) => (patternPosition + 1, stringPosition + 1)1165 patternPositionsForNextStringPosition.Add(currentPatternPosition + 1);1166 }1167 1168 public override void ProcessEndOfString(1169 int currentPatternPosition,1170 PatternPositionsVisitor patternPositionsForEndOfStringPosition)1171 {1172 // '?' : (patternPosition, endOfString) => <no transitions out of this state - cannot move beyond end of string>1173 }1174 }1175 1176 private sealed class LiteralCharacterElement : QuestionMarkElement1177 {1178 private readonly char _literalCharacter;1179 1180 public LiteralCharacterElement(char literalCharacter)1181 {1182 _literalCharacter = literalCharacter;1183 }1184 1185 public override void ProcessStringCharacter(1186 char currentStringCharacter,1187 int currentPatternPosition,1188 PatternPositionsVisitor patternPositionsForCurrentStringPosition,1189 PatternPositionsVisitor patternPositionsForNextStringPosition)1190 {1191 if (_literalCharacter == currentStringCharacter)1192 {1193 base.ProcessStringCharacter(1194 currentStringCharacter,1195 currentPatternPosition,1196 patternPositionsForCurrentStringPosition,1197 patternPositionsForNextStringPosition);1198 }1199 }1200 }