1 // Copyright (c) Microsoft. All rights reserved. 2 // Licensed under the MIT license. See LICENSE file in the project root for full license information. 3 //----------------------------------------------------------------------- 4 // </copyright> 5 // <summary>Implementation a class which splits expressions to MSBuild rules.</summary> 6 //----------------------------------------------------------------------- 7 8 using System; 9 using System.Collections; 10 #if FEATURE_SECURITY_PERMISSIONS 11 using System.Security.Permissions; 12 #endif 13 using System.Diagnostics; 14 15 using Microsoft.Build.Framework; 16 using Microsoft.Build.Shared; 17 using System.Collections.Generic; 18 using Microsoft.Build.Collections; 19 20 namespace Microsoft.Build.Evaluation 21 { 22 /// <summary> 23 /// What the shredder should be looking for. 24 /// </summary> 25 [Flags] 26 internal enum ShredderOptions 27 { 28 /// <summary> 29 /// Don't use 30 /// </summary> 31 Invalid = 0x0, 32 33 /// <summary> 34 /// Shred item types 35 /// </summary> 36 ItemTypes = 0x1, 37 38 /// <summary> 39 /// Shred metadata not contained inside of a transform. 40 /// </summary> 41 MetadataOutsideTransforms = 0x2, 42 43 /// <summary> 44 /// Shred both items and metadata not contained in a transform. 45 /// </summary> 46 All = ItemTypes | MetadataOutsideTransforms 47 } 48 49 /// <summary> 50 /// A class which interprets and splits MSBuild expressions 51 /// </summary> 52 internal static class ExpressionShredder 53 { 54 /// <summary> 55 /// Splits an expression into fragments at semi-colons, except where the 56 /// semi-colons are in a macro or separator expression. 57 /// Fragments are trimmed and empty fragments discarded. 58 /// </summary> 59 /// <remarks> 60 /// See <see cref="SemiColonTokenizer"/> for rules. 61 /// </remarks> 62 /// <param name="expression">List expression to split</param> 63 /// <returns>Array of non-empty strings from split list.</returns> SplitSemiColonSeparatedList(string expression)64 internal static SemiColonTokenizer SplitSemiColonSeparatedList(string expression) 65 { 66 return new SemiColonTokenizer(expression); 67 } 68 69 /// <summary> 70 /// Given a list of expressions that may contain item list expressions, 71 /// returns a pair of tables of all item names found, as K=Name, V=String.Empty; 72 /// and all metadata not in transforms, as K=Metadata key, V=MetadataReference, 73 /// where metadata key is like "itemname.metadataname" or "metadataname". 74 /// PERF: Tables are null if there are no entries, because this is quite a common case. 75 /// </summary> GetReferencedItemNamesAndMetadata(List<string> expressions)76 internal static ItemsAndMetadataPair GetReferencedItemNamesAndMetadata(List<string> expressions) 77 { 78 ItemsAndMetadataPair pair = new ItemsAndMetadataPair(null, null); 79 80 foreach (string expression in expressions) 81 { 82 GetReferencedItemNamesAndMetadata(expression, 0, expression.Length, ref pair, ShredderOptions.All); 83 } 84 85 return pair; 86 } 87 88 /// <summary> 89 /// Returns true if there is a metadata expression (outside of a transform) in the expression. 90 /// </summary> ContainsMetadataExpressionOutsideTransform(string expression)91 internal static bool ContainsMetadataExpressionOutsideTransform(string expression) 92 { 93 ItemsAndMetadataPair pair = new ItemsAndMetadataPair(null, null); 94 95 GetReferencedItemNamesAndMetadata(expression, 0, expression.Length, ref pair, ShredderOptions.MetadataOutsideTransforms); 96 97 bool result = (pair.Metadata != null && pair.Metadata.Count > 0); 98 99 return result; 100 } 101 102 /// <summary> 103 /// Given a subexpression, finds referenced sub transform expressions 104 /// itemName and separator will be null if they are not found 105 /// return value will be null if no transform expressions are found 106 /// </summary> GetReferencedItemExpressions(string expression)107 internal static List<ItemExpressionCapture> GetReferencedItemExpressions(string expression) 108 { 109 return GetReferencedItemExpressions(expression, 0, expression.Length); 110 } 111 112 /// <summary> 113 /// Given a subexpression, finds referenced sub transform expressions 114 /// itemName and separator will be null if they are not found 115 /// return value will be null if no transform expressions are found 116 /// </summary> GetReferencedItemExpressions(string expression, int start, int end)117 internal static List<ItemExpressionCapture> GetReferencedItemExpressions(string expression, int start, int end) 118 { 119 List<ItemExpressionCapture> subExpressions = null; 120 121 if (expression.IndexOf('@') < 0) 122 { 123 return null; 124 } 125 126 for (int i = start; i < end; i++) 127 { 128 int restartPoint; 129 int startPoint; 130 131 if (Sink(expression, ref i, end, '@', '(')) 132 { 133 List<ItemExpressionCapture> transformExpressions = null; 134 string itemName = null; 135 string separator = null; 136 int separatorStart = -1; 137 int separatorLength = -1; 138 139 // Start of a possible item list expression 140 141 // Store the index to backtrack to if this doesn't turn out to be a well 142 // formed expression. (Subtract one for the increment when we loop around.) 143 restartPoint = i - 1; 144 145 // Store the expression's start point 146 startPoint = i - 2; 147 148 SinkWhitespace(expression, ref i); 149 150 int startOfName = i; 151 152 if (!SinkValidName(expression, ref i, end)) 153 { 154 i = restartPoint; 155 continue; 156 } 157 158 // '-' is a legitimate char in an item name, but we should match '->' as an arrow 159 // in '@(foo->'x')' rather than as the last char of the item name. 160 // The old regex accomplished this by being "greedy" 161 if (end > i && expression[i - 1] == '-' && expression[i] == '>') 162 { 163 i--; 164 } 165 166 // Grab the name, but continue to verify it's a well-formed expression 167 // before we store it. 168 string name = expression.Substring(startOfName, i - startOfName); 169 170 // return the item that we're working with 171 itemName = name; 172 173 SinkWhitespace(expression, ref i); 174 bool transformOrFunctionFound = true; 175 176 // If there's an '->' eat it and the subsequent quoted expression or transform function 177 while (Sink(expression, ref i, end, '-', '>') && transformOrFunctionFound) 178 { 179 SinkWhitespace(expression, ref i); 180 int startTransform = i; 181 182 bool isQuotedTransform = SinkSingleQuotedExpression(expression, ref i, end); 183 if (isQuotedTransform) 184 { 185 int startQuoted = startTransform + 1; 186 int endQuoted = i - 1; 187 if (transformExpressions == null) 188 { 189 transformExpressions = new List<ItemExpressionCapture>(); 190 } 191 192 transformExpressions.Add(new ItemExpressionCapture(startQuoted, endQuoted - startQuoted, expression.Substring(startQuoted, endQuoted - startQuoted))); 193 continue; 194 } 195 196 startTransform = i; 197 ItemExpressionCapture functionCapture = SinkItemFunctionExpression(expression, startTransform, ref i, end); 198 if (functionCapture != null) 199 { 200 if (transformExpressions == null) 201 { 202 transformExpressions = new List<ItemExpressionCapture>(); 203 } 204 205 transformExpressions.Add(functionCapture); 206 continue; 207 } 208 209 if (!isQuotedTransform && functionCapture == null) 210 { 211 i = restartPoint; 212 transformOrFunctionFound = false; 213 } 214 } 215 216 if (!transformOrFunctionFound) 217 { 218 continue; 219 } 220 221 SinkWhitespace(expression, ref i); 222 223 // If there's a ',', eat it and the subsequent quoted expression 224 if (Sink(expression, ref i, ',')) 225 { 226 SinkWhitespace(expression, ref i); 227 228 if (!Sink(expression, ref i, '\'')) 229 { 230 i = restartPoint; 231 continue; 232 } 233 234 int closingQuote = expression.IndexOf('\'', i); 235 if (closingQuote == -1) 236 { 237 i = restartPoint; 238 continue; 239 } 240 241 separatorStart = i - startPoint; 242 separatorLength = closingQuote - i; 243 separator = expression.Substring(i, separatorLength); 244 245 i = closingQuote + 1; 246 } 247 248 SinkWhitespace(expression, ref i); 249 250 if (!Sink(expression, ref i, ')')) 251 { 252 i = restartPoint; 253 continue; 254 } 255 256 int endPoint = i; 257 i--; 258 259 if (subExpressions == null) 260 { 261 subExpressions = new List<ItemExpressionCapture>(); 262 } 263 264 // Create an expression capture that encompases the entire expression between the @( and the ) 265 // with the item name and any separator contained within it 266 // and each transform expression contained within it (i.e. each ->XYZ) 267 ItemExpressionCapture expressionCapture = new ItemExpressionCapture(startPoint, endPoint - startPoint, expression.Substring(startPoint, endPoint - startPoint), itemName, separator, separatorStart, transformExpressions); 268 subExpressions.Add(expressionCapture); 269 270 continue; 271 } 272 } 273 274 return subExpressions; 275 } 276 277 /// <summary> 278 /// Given a subexpression, finds referenced item names and inserts them into the table 279 /// as K=Name, V=String.Empty. 280 /// </summary> 281 /// <remarks> 282 /// We can ignore any semicolons in the expression, since we're not itemizing it. 283 /// </remarks> GetReferencedItemNamesAndMetadata(string expression, int start, int end, ref ItemsAndMetadataPair pair, ShredderOptions whatToShredFor)284 private static void GetReferencedItemNamesAndMetadata(string expression, int start, int end, ref ItemsAndMetadataPair pair, ShredderOptions whatToShredFor) 285 { 286 for (int i = start; i < end; i++) 287 { 288 int restartPoint; 289 290 if (Sink(expression, ref i, end, '@', '(')) 291 { 292 // Start of a possible item list expression 293 294 // Store the index to backtrack to if this doesn't turn out to be a well 295 // formed metadata expression. (Subtract one for the increment when we loop around.) 296 restartPoint = i - 1; 297 298 SinkWhitespace(expression, ref i); 299 300 int startOfName = i; 301 302 if (!SinkValidName(expression, ref i, end)) 303 { 304 i = restartPoint; 305 continue; 306 } 307 308 // '-' is a legitimate char in an item name, but we should match '->' as an arrow 309 // in '@(foo->'x')' rather than as the last char of the item name. 310 // The old regex accomplished this by being "greedy" 311 if (end > i && expression[i - 1] == '-' && expression[i] == '>') 312 { 313 i--; 314 } 315 316 // Grab the name, but continue to verify it's a well-formed expression 317 // before we store it. 318 string name = expression.Substring(startOfName, i - startOfName); 319 320 SinkWhitespace(expression, ref i); 321 322 bool transformOrFunctionFound = true; 323 324 // If there's an '->' eat it and the subsequent quoted expression or transform function 325 while (Sink(expression, ref i, end, '-', '>') && transformOrFunctionFound) 326 { 327 SinkWhitespace(expression, ref i); 328 int startTransform = i; 329 330 bool isQuotedTransform = SinkSingleQuotedExpression(expression, ref i, end); 331 if (isQuotedTransform) 332 { 333 continue; 334 } 335 336 ItemExpressionCapture functionCapture = SinkItemFunctionExpression(expression, startTransform, ref i, end); 337 if (functionCapture != null) 338 { 339 continue; 340 } 341 342 if (!isQuotedTransform && functionCapture == null) 343 { 344 i = restartPoint; 345 transformOrFunctionFound = false; 346 } 347 } 348 349 if (!transformOrFunctionFound) 350 { 351 continue; 352 } 353 354 SinkWhitespace(expression, ref i); 355 356 // If there's a ',', eat it and the subsequent quoted expression 357 if (Sink(expression, ref i, ',')) 358 { 359 SinkWhitespace(expression, ref i); 360 361 if (!Sink(expression, ref i, '\'')) 362 { 363 i = restartPoint; 364 continue; 365 } 366 367 int closingQuote = expression.IndexOf('\'', i); 368 if (closingQuote == -1) 369 { 370 i = restartPoint; 371 continue; 372 } 373 374 // Look for metadata in the separator expression 375 // e.g., @(foo, '%(bar)') contains batchable metadata 'bar' 376 GetReferencedItemNamesAndMetadata(expression, i, closingQuote, ref pair, ShredderOptions.MetadataOutsideTransforms); 377 378 i = closingQuote + 1; 379 } 380 381 SinkWhitespace(expression, ref i); 382 383 if (!Sink(expression, ref i, ')')) 384 { 385 i = restartPoint; 386 continue; 387 } 388 389 // If we've got this far, we know the item expression was 390 // well formed, so make sure the name's in the table 391 if ((whatToShredFor & ShredderOptions.ItemTypes) != 0) 392 { 393 pair.Items = pair.Items ?? new HashSet<string>(MSBuildNameIgnoreCaseComparer.Default); 394 pair.Items.Add(name); 395 } 396 397 i--; 398 399 continue; 400 } 401 402 if (Sink(expression, ref i, end, '%', '(')) 403 { 404 // Start of a possible metadata expression 405 406 // Store the index to backtrack to if this doesn't turn out to be a well 407 // formed metadata expression. (Subtract one for the increment when we loop around.) 408 restartPoint = i - 1; 409 410 SinkWhitespace(expression, ref i); 411 412 int startOfText = i; 413 414 if (!SinkValidName(expression, ref i, end)) 415 { 416 i = restartPoint; 417 continue; 418 } 419 420 // Grab this, but we don't know if it's an item or metadata name yet 421 string firstPart = expression.Substring(startOfText, i - startOfText); 422 string itemName = null; 423 string metadataName; 424 string qualifiedMetadataName; 425 426 SinkWhitespace(expression, ref i); 427 428 bool qualified = Sink(expression, ref i, '.'); 429 430 if (qualified) 431 { 432 SinkWhitespace(expression, ref i); 433 434 startOfText = i; 435 436 if (!SinkValidName(expression, ref i, end)) 437 { 438 i = restartPoint; 439 continue; 440 } 441 442 itemName = firstPart; 443 metadataName = expression.Substring(startOfText, i - startOfText); 444 qualifiedMetadataName = itemName + "." + metadataName; 445 } 446 else 447 { 448 metadataName = firstPart; 449 qualifiedMetadataName = metadataName; 450 } 451 452 SinkWhitespace(expression, ref i); 453 454 if (!Sink(expression, ref i, ')')) 455 { 456 i = restartPoint; 457 continue; 458 } 459 460 if ((whatToShredFor & ShredderOptions.MetadataOutsideTransforms) != 0) 461 { 462 pair.Metadata = pair.Metadata ?? new Dictionary<string, MetadataReference>(MSBuildNameIgnoreCaseComparer.Default); 463 pair.Metadata[qualifiedMetadataName] = new MetadataReference(itemName, metadataName); 464 } 465 466 i--; 467 } 468 } 469 } 470 471 /// <summary> 472 /// Returns true if a single quoted subexpression begins at the specified index 473 /// and ends before the specified end index. 474 /// Leaves index one past the end of the second quote. 475 /// </summary> SinkSingleQuotedExpression(string expression, ref int i, int end)476 private static bool SinkSingleQuotedExpression(string expression, ref int i, int end) 477 { 478 if (!Sink(expression, ref i, '\'')) 479 { 480 return false; 481 } 482 483 while (i < end && expression[i] != '\'') 484 { 485 i++; 486 } 487 488 i++; 489 490 if (end <= i) 491 { 492 return false; 493 } 494 495 return true; 496 } 497 498 /// <summary> 499 /// Scan for the closing bracket that matches the one we've already skipped; 500 /// essentially, pushes and pops on a stack of parentheses to do this. 501 /// Takes the expression and the index to start at. 502 /// Returns the index of the matching parenthesis, or -1 if it was not found. 503 /// </summary> SinkArgumentsInParentheses(string expression, ref int i, int end)504 private static bool SinkArgumentsInParentheses(string expression, ref int i, int end) 505 { 506 int nestLevel = 0; 507 int length = expression.Length; 508 int restartPoint; 509 510 unsafe 511 { 512 fixed (char* pchar = expression) 513 { 514 if (pchar[i] == '(') 515 { 516 nestLevel++; 517 i++; 518 } 519 else 520 { 521 return false; 522 } 523 524 // Scan for our closing ')' 525 while (i < length && i < end && nestLevel > 0) 526 { 527 char character = pchar[i]; 528 529 if (character == '\'' || character == '`' || character == '"') 530 { 531 restartPoint = i; 532 if (!SinkUntilClosingQuote(character, expression, ref i, end)) 533 { 534 i = restartPoint; 535 return false; 536 } 537 } 538 else if (character == '(') 539 { 540 nestLevel++; 541 } 542 else if (character == ')') 543 { 544 nestLevel--; 545 } 546 547 i++; 548 } 549 } 550 } 551 552 if (nestLevel == 0) 553 { 554 return true; 555 } 556 else 557 { 558 return false; 559 } 560 } 561 562 /// <summary> 563 /// Skip all characters until we find the matching quote character 564 /// </summary> SinkUntilClosingQuote(char quoteChar, string expression, ref int i, int end)565 private static bool SinkUntilClosingQuote(char quoteChar, string expression, ref int i, int end) 566 { 567 unsafe 568 { 569 fixed (char* pchar = expression) 570 { 571 // We have already checked the first quote 572 i++; 573 574 // Scan for our closing quoteChar 575 while (i < expression.Length && i < end) 576 { 577 if (pchar[i] == quoteChar) 578 { 579 return true; 580 } 581 582 i++; 583 } 584 } 585 } 586 587 return false; 588 } 589 590 /// <summary> 591 /// Returns true if a item function subexpression begins at the specified index 592 /// and ends before the specified end index. 593 /// Leaves index one past the end of the closing paren. 594 /// </summary> SinkItemFunctionExpression(string expression, int startTransform, ref int i, int end)595 private static ItemExpressionCapture SinkItemFunctionExpression(string expression, int startTransform, ref int i, int end) 596 { 597 if (SinkValidName(expression, ref i, end)) 598 { 599 int endFunctionName = i; 600 601 // Eat any whitespace between the function name and its arguments 602 SinkWhitespace(expression, ref i); 603 int startFunctionArguments = i + 1; 604 605 if (SinkArgumentsInParentheses(expression, ref i, end)) 606 { 607 int endFunctionArguments = i - 1; 608 609 ItemExpressionCapture capture = new ItemExpressionCapture(startTransform, i - startTransform, expression.Substring(startTransform, i - startTransform)); 610 capture.FunctionName = expression.Substring(startTransform, endFunctionName - startTransform); 611 612 if (endFunctionArguments > startFunctionArguments) 613 { 614 capture.FunctionArguments = expression.Substring(startFunctionArguments, endFunctionArguments - startFunctionArguments); 615 } 616 617 return capture; 618 } 619 620 return null; 621 } 622 else 623 { 624 return null; 625 } 626 } 627 628 /// <summary> 629 /// Returns true if a valid name begins at the specified index. 630 /// Leaves index one past the end of the name. 631 /// </summary> SinkValidName(string expression, ref int i, int end)632 private static bool SinkValidName(string expression, ref int i, int end) 633 { 634 if (end <= i || !XmlUtilities.IsValidInitialElementNameCharacter(expression[i])) 635 { 636 return false; 637 } 638 639 i++; 640 641 while (end > i && XmlUtilities.IsValidSubsequentElementNameCharacter(expression[i])) 642 { 643 i++; 644 } 645 646 return true; 647 } 648 649 /// <summary> 650 /// Returns true if the character at the specified index 651 /// is the specified char. 652 /// Leaves index one past the character. 653 /// </summary> Sink(string expression, ref int i, char c)654 private static bool Sink(string expression, ref int i, char c) 655 { 656 if (i < expression.Length && expression[i] == c) 657 { 658 i++; 659 return true; 660 } 661 662 return false; 663 } 664 665 /// <summary> 666 /// Returns true if the next two characters at the specified index 667 /// are the specified sequence. 668 /// Leaves index one past the second character. 669 /// </summary> Sink(string expression, ref int i, int end, char c1, char c2)670 private static bool Sink(string expression, ref int i, int end, char c1, char c2) 671 { 672 if (i < end - 1 && expression[i] == c1 && expression[i + 1] == c2) 673 { 674 i = i + 2; 675 return true; 676 } 677 678 return false; 679 } 680 681 /// <summary> 682 /// Moves past all whitespace starting at the specified index. 683 /// Returns the next index, possibly the string length. 684 /// </summary> 685 /// <remarks> 686 /// Char.IsWhitespace() is not identical in behavior to regex's \s character class, 687 /// but it's extremely close, and it's what we use in conditional expressions. 688 /// </remarks> 689 /// <param name="expression">The expression to process.</param> 690 /// <param name="i">The start location for skipping whitespace, contains the next non-whitespace character on exit.</param> SinkWhitespace(string expression, ref int i)691 private static void SinkWhitespace(string expression, ref int i) 692 { 693 while (i < expression.Length && Char.IsWhiteSpace(expression[i])) 694 { 695 i++; 696 } 697 } 698 699 /// <summary> 700 /// Represents one substring for a single successful capture. 701 /// </summary> 702 internal class ItemExpressionCapture 703 { 704 /// <summary> 705 /// Captures within this capture 706 /// </summary> 707 private readonly List<ItemExpressionCapture> _captures; 708 709 /// <summary> 710 /// The position in the original string where the first character of the captured 711 /// substring was found. 712 /// </summary> 713 private readonly int _index; 714 715 /// <summary> 716 /// The length of the captured substring. 717 /// </summary> 718 private readonly int _length; 719 720 /// <summary> 721 /// The captured substring from the input string. 722 /// </summary> 723 private readonly string _value; 724 725 /// <summary> 726 /// The type of the item within this expression 727 /// </summary> 728 private readonly string _itemType; 729 730 /// <summary> 731 /// The separator, if any, within this expression 732 /// </summary> 733 private readonly string _separator; 734 735 /// <summary> 736 /// The starting character of the separator within the expression 737 /// </summary> 738 private readonly int _separatorStart; 739 740 /// <summary> 741 /// The function name, if any, within this expression 742 /// </summary> 743 private string _functionName; 744 745 /// <summary> 746 /// The function arguments, if any, within this expression 747 /// </summary> 748 private string _functionArguments; 749 750 /// <summary> 751 /// Create an Expression Capture instance 752 /// Represents a sub expression, shredded from a larger expression 753 /// </summary> ItemExpressionCapture(int index, int length, string subExpression)754 public ItemExpressionCapture(int index, int length, string subExpression) : this(index, length, subExpression, null, null, -1, null) 755 { 756 } 757 758 /// <summary> 759 /// Create an Expression Capture instance 760 /// Represents a sub expression, shredded from a larger expression 761 /// </summary> ItemExpressionCapture(int index, int length, string subExpression, string itemType, string separator, int separatorStart, List<ItemExpressionCapture> captures)762 public ItemExpressionCapture(int index, int length, string subExpression, string itemType, string separator, int separatorStart, List<ItemExpressionCapture> captures) 763 { 764 _index = index; 765 _length = length; 766 _value = subExpression; 767 _itemType = itemType; 768 _separator = separator; 769 _separatorStart = separatorStart; 770 _captures = captures; 771 } 772 773 /// <summary> 774 /// Captures within this capture 775 /// </summary> 776 public List<ItemExpressionCapture> Captures 777 { 778 get { return _captures; } 779 } 780 781 /// <summary> 782 /// The position in the original string where the first character of the captured 783 /// substring was found. 784 /// </summary> 785 public int Index 786 { 787 get { return _index; } 788 } 789 790 /// <summary> 791 /// The length of the captured substring. 792 /// </summary> 793 public int Length 794 { 795 get { return _length; } 796 } 797 798 /// <summary> 799 /// Gets the captured substring from the input string. 800 /// </summary> 801 public string Value 802 { 803 get { return _value; } 804 } 805 806 /// <summary> 807 /// Gets the captured itemtype. 808 /// </summary> 809 public string ItemType 810 { 811 get { return _itemType; } 812 } 813 814 /// <summary> 815 /// Gets the captured itemtype. 816 /// </summary> 817 public string Separator 818 { 819 get { return _separator; } 820 } 821 822 /// <summary> 823 /// The starting character of the separator. 824 /// </summary> 825 public int SeparatorStart 826 { 827 get { return _separatorStart; } 828 } 829 830 /// <summary> 831 /// The function name, if any, within this expression 832 /// </summary> 833 public string FunctionName 834 { 835 get { return _functionName; } 836 set { _functionName = value; } 837 } 838 839 /// <summary> 840 /// The function arguments, if any, within this expression 841 /// </summary> 842 public string FunctionArguments 843 { 844 get { return _functionArguments; } 845 set { _functionArguments = value; } 846 } 847 848 /// <summary> 849 /// Gets the captured substring from the input string. 850 /// </summary> ToString()851 public override string ToString() 852 { 853 return _value; 854 } 855 } 856 } 857 } 858