1 /****************************************************************************** 2 * 3 * Module Name: asltree - parse tree management 4 * 5 *****************************************************************************/ 6 7 /* 8 * Copyright (C) 2000 - 2014, Intel Corp. 9 * All rights reserved. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions, and the following disclaimer, 16 * without modification. 17 * 2. Redistributions in binary form must reproduce at minimum a disclaimer 18 * substantially similar to the "NO WARRANTY" disclaimer below 19 * ("Disclaimer") and any redistribution must be conditioned upon 20 * including a substantially similar Disclaimer requirement for further 21 * binary redistribution. 22 * 3. Neither the names of the above-listed copyright holders nor the names 23 * of any contributors may be used to endorse or promote products derived 24 * from this software without specific prior written permission. 25 * 26 * Alternatively, this software may be distributed under the terms of the 27 * GNU General Public License ("GPL") version 2 as published by the Free 28 * Software Foundation. 29 * 30 * NO WARRANTY 31 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 32 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 33 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR 34 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 35 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 36 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 37 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 38 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 40 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 41 * POSSIBILITY OF SUCH DAMAGES. 42 */ 43 44 #include "aslcompiler.h" 45 #include "aslcompiler.y.h" 46 #include "acapps.h" 47 #include <time.h> 48 49 #define _COMPONENT ACPI_COMPILER 50 ACPI_MODULE_NAME ("asltree") 51 52 /* Local prototypes */ 53 54 static ACPI_PARSE_OBJECT * 55 TrGetNextNode ( 56 void); 57 58 static char * 59 TrGetNodeFlagName ( 60 UINT32 Flags); 61 62 63 /******************************************************************************* 64 * 65 * FUNCTION: TrGetNextNode 66 * 67 * PARAMETERS: None 68 * 69 * RETURN: New parse node. Aborts on allocation failure 70 * 71 * DESCRIPTION: Allocate a new parse node for the parse tree. Bypass the local 72 * dynamic memory manager for performance reasons (This has a 73 * major impact on the speed of the compiler.) 74 * 75 ******************************************************************************/ 76 77 static ACPI_PARSE_OBJECT * 78 TrGetNextNode ( 79 void) 80 { 81 ASL_CACHE_INFO *Cache; 82 83 84 if (Gbl_ParseOpCacheNext >= Gbl_ParseOpCacheLast) 85 { 86 /* Allocate a new buffer */ 87 88 Cache = UtLocalCalloc (sizeof (Cache->Next) + 89 (sizeof (ACPI_PARSE_OBJECT) * ASL_PARSEOP_CACHE_SIZE)); 90 91 /* Link new cache buffer to head of list */ 92 93 Cache->Next = Gbl_ParseOpCacheList; 94 Gbl_ParseOpCacheList = Cache; 95 96 /* Setup cache management pointers */ 97 98 Gbl_ParseOpCacheNext = ACPI_CAST_PTR (ACPI_PARSE_OBJECT, Cache->Buffer); 99 Gbl_ParseOpCacheLast = Gbl_ParseOpCacheNext + ASL_PARSEOP_CACHE_SIZE; 100 } 101 102 Gbl_ParseOpCount++; 103 return (Gbl_ParseOpCacheNext++); 104 } 105 106 107 /******************************************************************************* 108 * 109 * FUNCTION: TrAllocateNode 110 * 111 * PARAMETERS: ParseOpcode - Opcode to be assigned to the node 112 * 113 * RETURN: New parse node. Aborts on allocation failure 114 * 115 * DESCRIPTION: Allocate and initialize a new parse node for the parse tree 116 * 117 ******************************************************************************/ 118 119 ACPI_PARSE_OBJECT * 120 TrAllocateNode ( 121 UINT32 ParseOpcode) 122 { 123 ACPI_PARSE_OBJECT *Op; 124 125 126 Op = TrGetNextNode (); 127 128 Op->Asl.ParseOpcode = (UINT16) ParseOpcode; 129 Op->Asl.Filename = Gbl_Files[ASL_FILE_INPUT].Filename; 130 Op->Asl.LineNumber = Gbl_CurrentLineNumber; 131 Op->Asl.LogicalLineNumber = Gbl_LogicalLineNumber; 132 Op->Asl.LogicalByteOffset = Gbl_CurrentLineOffset; 133 Op->Asl.Column = Gbl_CurrentColumn; 134 135 UtSetParseOpName (Op); 136 return (Op); 137 } 138 139 140 /******************************************************************************* 141 * 142 * FUNCTION: TrReleaseNode 143 * 144 * PARAMETERS: Op - Op to be released 145 * 146 * RETURN: None 147 * 148 * DESCRIPTION: "release" a node. In truth, nothing is done since the node 149 * is part of a larger buffer 150 * 151 ******************************************************************************/ 152 153 void 154 TrReleaseNode ( 155 ACPI_PARSE_OBJECT *Op) 156 { 157 158 return; 159 } 160 161 162 /******************************************************************************* 163 * 164 * FUNCTION: TrUpdateNode 165 * 166 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 167 * Op - An existing parse node 168 * 169 * RETURN: The updated node 170 * 171 * DESCRIPTION: Change the parse opcode assigned to a node. Usually used to 172 * change an opcode to DEFAULT_ARG so that the node is ignored 173 * during the code generation. Also used to set generic integers 174 * to a specific size (8, 16, 32, or 64 bits) 175 * 176 ******************************************************************************/ 177 178 ACPI_PARSE_OBJECT * 179 TrUpdateNode ( 180 UINT32 ParseOpcode, 181 ACPI_PARSE_OBJECT *Op) 182 { 183 184 if (!Op) 185 { 186 return (NULL); 187 } 188 189 DbgPrint (ASL_PARSE_OUTPUT, 190 "\nUpdateNode: Old - %s, New - %s\n\n", 191 UtGetOpName (Op->Asl.ParseOpcode), 192 UtGetOpName (ParseOpcode)); 193 194 /* Assign new opcode and name */ 195 196 if (Op->Asl.ParseOpcode == PARSEOP_ONES) 197 { 198 switch (ParseOpcode) 199 { 200 case PARSEOP_BYTECONST: 201 202 Op->Asl.Value.Integer = ACPI_UINT8_MAX; 203 break; 204 205 case PARSEOP_WORDCONST: 206 207 Op->Asl.Value.Integer = ACPI_UINT16_MAX; 208 break; 209 210 case PARSEOP_DWORDCONST: 211 212 Op->Asl.Value.Integer = ACPI_UINT32_MAX; 213 break; 214 215 /* Don't need to do the QWORD case */ 216 217 default: 218 219 /* Don't care about others */ 220 break; 221 } 222 } 223 224 Op->Asl.ParseOpcode = (UINT16) ParseOpcode; 225 UtSetParseOpName (Op); 226 227 /* 228 * For the BYTE, WORD, and DWORD constants, make sure that the integer 229 * that was passed in will actually fit into the data type 230 */ 231 switch (ParseOpcode) 232 { 233 case PARSEOP_BYTECONST: 234 235 UtCheckIntegerRange (Op, 0x00, ACPI_UINT8_MAX); 236 Op->Asl.Value.Integer &= ACPI_UINT8_MAX; 237 break; 238 239 case PARSEOP_WORDCONST: 240 241 UtCheckIntegerRange (Op, 0x00, ACPI_UINT16_MAX); 242 Op->Asl.Value.Integer &= ACPI_UINT16_MAX; 243 break; 244 245 case PARSEOP_DWORDCONST: 246 247 UtCheckIntegerRange (Op, 0x00, ACPI_UINT32_MAX); 248 Op->Asl.Value.Integer &= ACPI_UINT32_MAX; 249 break; 250 251 default: 252 253 /* Don't care about others, don't need to check QWORD */ 254 255 break; 256 } 257 258 return (Op); 259 } 260 261 262 /******************************************************************************* 263 * 264 * FUNCTION: TrGetNodeFlagName 265 * 266 * PARAMETERS: Flags - Flags word to be decoded 267 * 268 * RETURN: Name string. Always returns a valid string pointer. 269 * 270 * DESCRIPTION: Decode a flags word 271 * 272 ******************************************************************************/ 273 274 static char * 275 TrGetNodeFlagName ( 276 UINT32 Flags) 277 { 278 279 switch (Flags) 280 { 281 case NODE_VISITED: 282 283 return ("NODE_VISITED"); 284 285 case NODE_AML_PACKAGE: 286 287 return ("NODE_AML_PACKAGE"); 288 289 case NODE_IS_TARGET: 290 291 return ("NODE_IS_TARGET"); 292 293 case NODE_IS_RESOURCE_DESC: 294 295 return ("NODE_IS_RESOURCE_DESC"); 296 297 case NODE_IS_RESOURCE_FIELD: 298 299 return ("NODE_IS_RESOURCE_FIELD"); 300 301 case NODE_HAS_NO_EXIT: 302 303 return ("NODE_HAS_NO_EXIT"); 304 305 case NODE_IF_HAS_NO_EXIT: 306 307 return ("NODE_IF_HAS_NO_EXIT"); 308 309 case NODE_NAME_INTERNALIZED: 310 311 return ("NODE_NAME_INTERNALIZED"); 312 313 case NODE_METHOD_NO_RETVAL: 314 315 return ("NODE_METHOD_NO_RETVAL"); 316 317 case NODE_METHOD_SOME_NO_RETVAL: 318 319 return ("NODE_METHOD_SOME_NO_RETVAL"); 320 321 case NODE_RESULT_NOT_USED: 322 323 return ("NODE_RESULT_NOT_USED"); 324 325 case NODE_METHOD_TYPED: 326 327 return ("NODE_METHOD_TYPED"); 328 329 case NODE_COMPILE_TIME_CONST: 330 331 return ("NODE_COMPILE_TIME_CONST"); 332 333 case NODE_IS_TERM_ARG: 334 335 return ("NODE_IS_TERM_ARG"); 336 337 case NODE_WAS_ONES_OP: 338 339 return ("NODE_WAS_ONES_OP"); 340 341 case NODE_IS_NAME_DECLARATION: 342 343 return ("NODE_IS_NAME_DECLARATION"); 344 345 default: 346 347 return ("Multiple Flags (or unknown flag) set"); 348 } 349 } 350 351 352 /******************************************************************************* 353 * 354 * FUNCTION: TrSetNodeFlags 355 * 356 * PARAMETERS: Op - An existing parse node 357 * Flags - New flags word 358 * 359 * RETURN: The updated parser op 360 * 361 * DESCRIPTION: Set bits in the node flags word. Will not clear bits, only set 362 * 363 ******************************************************************************/ 364 365 ACPI_PARSE_OBJECT * 366 TrSetNodeFlags ( 367 ACPI_PARSE_OBJECT *Op, 368 UINT32 Flags) 369 { 370 371 DbgPrint (ASL_PARSE_OUTPUT, 372 "\nSetNodeFlags: Op %p, %8.8X %s\n\n", Op, Flags, 373 TrGetNodeFlagName (Flags)); 374 375 if (!Op) 376 { 377 return (NULL); 378 } 379 380 Op->Asl.CompileFlags |= Flags; 381 return (Op); 382 } 383 384 385 /******************************************************************************* 386 * 387 * FUNCTION: TrSetNodeAmlLength 388 * 389 * PARAMETERS: Op - An existing parse node 390 * Length - AML Length 391 * 392 * RETURN: The updated parser op 393 * 394 * DESCRIPTION: Set the AML Length in a node. Used by the parser to indicate 395 * the presence of a node that must be reduced to a fixed length 396 * constant. 397 * 398 ******************************************************************************/ 399 400 ACPI_PARSE_OBJECT * 401 TrSetNodeAmlLength ( 402 ACPI_PARSE_OBJECT *Op, 403 UINT32 Length) 404 { 405 406 DbgPrint (ASL_PARSE_OUTPUT, 407 "\nSetNodeAmlLength: Op %p, %8.8X\n", Op, Length); 408 409 if (!Op) 410 { 411 return (NULL); 412 } 413 414 Op->Asl.AmlLength = Length; 415 return (Op); 416 } 417 418 419 /******************************************************************************* 420 * 421 * FUNCTION: TrSetEndLineNumber 422 * 423 * PARAMETERS: Op - An existing parse node 424 * 425 * RETURN: None. 426 * 427 * DESCRIPTION: Set the ending line numbers (file line and logical line) of a 428 * parse node to the current line numbers. 429 * 430 ******************************************************************************/ 431 432 void 433 TrSetEndLineNumber ( 434 ACPI_PARSE_OBJECT *Op) 435 { 436 437 /* If the end line # is already set, just return */ 438 439 if (Op->Asl.EndLine) 440 { 441 return; 442 } 443 444 Op->Asl.EndLine = Gbl_CurrentLineNumber; 445 Op->Asl.EndLogicalLine = Gbl_LogicalLineNumber; 446 } 447 448 449 /******************************************************************************* 450 * 451 * FUNCTION: TrCreateLeafNode 452 * 453 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 454 * 455 * RETURN: Pointer to the new node. Aborts on allocation failure 456 * 457 * DESCRIPTION: Create a simple leaf node (no children or peers, and no value 458 * assigned to the node) 459 * 460 ******************************************************************************/ 461 462 ACPI_PARSE_OBJECT * 463 TrCreateLeafNode ( 464 UINT32 ParseOpcode) 465 { 466 ACPI_PARSE_OBJECT *Op; 467 468 469 Op = TrAllocateNode (ParseOpcode); 470 471 DbgPrint (ASL_PARSE_OUTPUT, 472 "\nCreateLeafNode Ln/Col %u/%u NewNode %p Op %s\n\n", 473 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName(ParseOpcode)); 474 475 return (Op); 476 } 477 478 479 /******************************************************************************* 480 * 481 * FUNCTION: TrCreateConstantLeafNode 482 * 483 * PARAMETERS: ParseOpcode - The constant opcode 484 * 485 * RETURN: Pointer to the new node. Aborts on allocation failure 486 * 487 * DESCRIPTION: Create a leaf node (no children or peers) for one of the 488 * special constants - __LINE__, __FILE__, and __DATE__. 489 * 490 * Note: An implemenation of __FUNC__ cannot happen here because we don't 491 * have a full parse tree at this time and cannot find the parent control 492 * method. If it is ever needed, __FUNC__ must be implemented later, after 493 * the parse tree has been fully constructed. 494 * 495 ******************************************************************************/ 496 497 ACPI_PARSE_OBJECT * 498 TrCreateConstantLeafNode ( 499 UINT32 ParseOpcode) 500 { 501 ACPI_PARSE_OBJECT *Op = NULL; 502 time_t CurrentTime; 503 char *StaticTimeString; 504 char *TimeString; 505 char *Path; 506 char *Filename; 507 508 509 switch (ParseOpcode) 510 { 511 case PARSEOP___LINE__: 512 513 Op = TrAllocateNode (PARSEOP_INTEGER); 514 Op->Asl.Value.Integer = Op->Asl.LineNumber; 515 break; 516 517 case PARSEOP___PATH__: 518 519 Op = TrAllocateNode (PARSEOP_STRING_LITERAL); 520 521 /* Op.Asl.Filename contains the full pathname to the file */ 522 523 Op->Asl.Value.String = Op->Asl.Filename; 524 break; 525 526 case PARSEOP___FILE__: 527 528 Op = TrAllocateNode (PARSEOP_STRING_LITERAL); 529 530 /* Get the simple filename from the full path */ 531 532 FlSplitInputPathname (Op->Asl.Filename, &Path, &Filename); 533 ACPI_FREE (Path); 534 Op->Asl.Value.String = Filename; 535 break; 536 537 case PARSEOP___DATE__: 538 539 Op = TrAllocateNode (PARSEOP_STRING_LITERAL); 540 541 /* Get a copy of the current time */ 542 543 CurrentTime = time (NULL); 544 StaticTimeString = ctime (&CurrentTime); 545 TimeString = UtLocalCalloc (strlen (StaticTimeString) + 1); 546 strcpy (TimeString, StaticTimeString); 547 548 TimeString[strlen(TimeString) -1] = 0; /* Remove trailing newline */ 549 Op->Asl.Value.String = TimeString; 550 break; 551 552 default: /* This would be an internal error */ 553 554 return (NULL); 555 } 556 557 DbgPrint (ASL_PARSE_OUTPUT, 558 "\nCreateConstantLeafNode Ln/Col %u/%u NewNode %p Op %s Value %8.8X%8.8X ", 559 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName (ParseOpcode), 560 ACPI_FORMAT_UINT64 (Op->Asl.Value.Integer)); 561 return (Op); 562 } 563 564 565 /******************************************************************************* 566 * 567 * FUNCTION: TrCreateValuedLeafNode 568 * 569 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 570 * Value - Value to be assigned to the node 571 * 572 * RETURN: Pointer to the new node. Aborts on allocation failure 573 * 574 * DESCRIPTION: Create a leaf node (no children or peers) with a value 575 * assigned to it 576 * 577 ******************************************************************************/ 578 579 ACPI_PARSE_OBJECT * 580 TrCreateValuedLeafNode ( 581 UINT32 ParseOpcode, 582 UINT64 Value) 583 { 584 ACPI_PARSE_OBJECT *Op; 585 586 587 Op = TrAllocateNode (ParseOpcode); 588 589 DbgPrint (ASL_PARSE_OUTPUT, 590 "\nCreateValuedLeafNode Ln/Col %u/%u NewNode %p Op %s Value %8.8X%8.8X ", 591 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName(ParseOpcode), 592 ACPI_FORMAT_UINT64 (Value)); 593 Op->Asl.Value.Integer = Value; 594 595 switch (ParseOpcode) 596 { 597 case PARSEOP_STRING_LITERAL: 598 599 DbgPrint (ASL_PARSE_OUTPUT, "STRING->%s", Value); 600 break; 601 602 case PARSEOP_NAMESEG: 603 604 DbgPrint (ASL_PARSE_OUTPUT, "NAMESEG->%s", Value); 605 break; 606 607 case PARSEOP_NAMESTRING: 608 609 DbgPrint (ASL_PARSE_OUTPUT, "NAMESTRING->%s", Value); 610 break; 611 612 case PARSEOP_EISAID: 613 614 DbgPrint (ASL_PARSE_OUTPUT, "EISAID->%s", Value); 615 break; 616 617 case PARSEOP_METHOD: 618 619 DbgPrint (ASL_PARSE_OUTPUT, "METHOD"); 620 break; 621 622 case PARSEOP_INTEGER: 623 624 DbgPrint (ASL_PARSE_OUTPUT, "INTEGER"); 625 break; 626 627 default: 628 629 break; 630 } 631 632 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 633 return (Op); 634 } 635 636 637 /******************************************************************************* 638 * 639 * FUNCTION: TrCreateNode 640 * 641 * PARAMETERS: ParseOpcode - Opcode to be assigned to the node 642 * NumChildren - Number of children to follow 643 * ... - A list of child nodes to link to the new 644 * node. NumChildren long. 645 * 646 * RETURN: Pointer to the new node. Aborts on allocation failure 647 * 648 * DESCRIPTION: Create a new parse node and link together a list of child 649 * nodes underneath the new node. 650 * 651 ******************************************************************************/ 652 653 ACPI_PARSE_OBJECT * 654 TrCreateNode ( 655 UINT32 ParseOpcode, 656 UINT32 NumChildren, 657 ...) 658 { 659 ACPI_PARSE_OBJECT *Op; 660 ACPI_PARSE_OBJECT *Child; 661 ACPI_PARSE_OBJECT *PrevChild; 662 va_list ap; 663 UINT32 i; 664 BOOLEAN FirstChild; 665 666 667 va_start (ap, NumChildren); 668 669 /* Allocate one new node */ 670 671 Op = TrAllocateNode (ParseOpcode); 672 673 DbgPrint (ASL_PARSE_OUTPUT, 674 "\nCreateNode Ln/Col %u/%u NewParent %p Child %u Op %s ", 675 Op->Asl.LineNumber, Op->Asl.Column, Op, NumChildren, UtGetOpName(ParseOpcode)); 676 677 /* Some extra debug output based on the parse opcode */ 678 679 switch (ParseOpcode) 680 { 681 case PARSEOP_DEFINITIONBLOCK: 682 683 RootNode = Op; 684 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->"); 685 break; 686 687 case PARSEOP_OPERATIONREGION: 688 689 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->"); 690 break; 691 692 case PARSEOP_OR: 693 694 DbgPrint (ASL_PARSE_OUTPUT, "OR->"); 695 break; 696 697 default: 698 699 /* Nothing to do for other opcodes */ 700 701 break; 702 } 703 704 /* Link the new node to its children */ 705 706 PrevChild = NULL; 707 FirstChild = TRUE; 708 for (i = 0; i < NumChildren; i++) 709 { 710 /* Get the next child */ 711 712 Child = va_arg (ap, ACPI_PARSE_OBJECT *); 713 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child); 714 715 /* 716 * If child is NULL, this means that an optional argument 717 * was omitted. We must create a placeholder with a special 718 * opcode (DEFAULT_ARG) so that the code generator will know 719 * that it must emit the correct default for this argument 720 */ 721 if (!Child) 722 { 723 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG); 724 } 725 726 /* Link first child to parent */ 727 728 if (FirstChild) 729 { 730 FirstChild = FALSE; 731 Op->Asl.Child = Child; 732 } 733 734 /* Point all children to parent */ 735 736 Child->Asl.Parent = Op; 737 738 /* Link children in a peer list */ 739 740 if (PrevChild) 741 { 742 PrevChild->Asl.Next = Child; 743 }; 744 745 /* 746 * This child might be a list, point all nodes in the list 747 * to the same parent 748 */ 749 while (Child->Asl.Next) 750 { 751 Child = Child->Asl.Next; 752 Child->Asl.Parent = Op; 753 } 754 755 PrevChild = Child; 756 } 757 va_end(ap); 758 759 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 760 return (Op); 761 } 762 763 764 /******************************************************************************* 765 * 766 * FUNCTION: TrLinkChildren 767 * 768 * PARAMETERS: Op - An existing parse node 769 * NumChildren - Number of children to follow 770 * ... - A list of child nodes to link to the new 771 * node. NumChildren long. 772 * 773 * RETURN: The updated (linked) node 774 * 775 * DESCRIPTION: Link a group of nodes to an existing parse node 776 * 777 ******************************************************************************/ 778 779 ACPI_PARSE_OBJECT * 780 TrLinkChildren ( 781 ACPI_PARSE_OBJECT *Op, 782 UINT32 NumChildren, 783 ...) 784 { 785 ACPI_PARSE_OBJECT *Child; 786 ACPI_PARSE_OBJECT *PrevChild; 787 va_list ap; 788 UINT32 i; 789 BOOLEAN FirstChild; 790 791 792 va_start (ap, NumChildren); 793 794 795 TrSetEndLineNumber (Op); 796 797 DbgPrint (ASL_PARSE_OUTPUT, 798 "\nLinkChildren Line [%u to %u] NewParent %p Child %u Op %s ", 799 Op->Asl.LineNumber, Op->Asl.EndLine, 800 Op, NumChildren, UtGetOpName(Op->Asl.ParseOpcode)); 801 802 switch (Op->Asl.ParseOpcode) 803 { 804 case PARSEOP_DEFINITIONBLOCK: 805 806 RootNode = Op; 807 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->"); 808 break; 809 810 case PARSEOP_OPERATIONREGION: 811 812 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->"); 813 break; 814 815 case PARSEOP_OR: 816 817 DbgPrint (ASL_PARSE_OUTPUT, "OR->"); 818 break; 819 820 default: 821 822 /* Nothing to do for other opcodes */ 823 824 break; 825 } 826 827 /* Link the new node to it's children */ 828 829 PrevChild = NULL; 830 FirstChild = TRUE; 831 for (i = 0; i < NumChildren; i++) 832 { 833 Child = va_arg (ap, ACPI_PARSE_OBJECT *); 834 835 if ((Child == PrevChild) && (Child != NULL)) 836 { 837 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Child, 838 "Child node list invalid"); 839 va_end(ap); 840 return (Op); 841 } 842 843 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child); 844 845 /* 846 * If child is NULL, this means that an optional argument 847 * was omitted. We must create a placeholder with a special 848 * opcode (DEFAULT_ARG) so that the code generator will know 849 * that it must emit the correct default for this argument 850 */ 851 if (!Child) 852 { 853 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG); 854 } 855 856 /* Link first child to parent */ 857 858 if (FirstChild) 859 { 860 FirstChild = FALSE; 861 Op->Asl.Child = Child; 862 } 863 864 /* Point all children to parent */ 865 866 Child->Asl.Parent = Op; 867 868 /* Link children in a peer list */ 869 870 if (PrevChild) 871 { 872 PrevChild->Asl.Next = Child; 873 }; 874 875 /* 876 * This child might be a list, point all nodes in the list 877 * to the same parent 878 */ 879 while (Child->Asl.Next) 880 { 881 Child = Child->Asl.Next; 882 Child->Asl.Parent = Op; 883 } 884 PrevChild = Child; 885 } 886 887 va_end(ap); 888 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 889 return (Op); 890 } 891 892 893 /******************************************************************************* 894 * 895 * FUNCTION: TrLinkPeerNode 896 * 897 * PARAMETERS: Op1 - First peer 898 * Op2 - Second peer 899 * 900 * RETURN: Op1 or the non-null node. 901 * 902 * DESCRIPTION: Link two nodes as peers. Handles cases where one peer is null. 903 * 904 ******************************************************************************/ 905 906 ACPI_PARSE_OBJECT * 907 TrLinkPeerNode ( 908 ACPI_PARSE_OBJECT *Op1, 909 ACPI_PARSE_OBJECT *Op2) 910 { 911 ACPI_PARSE_OBJECT *Next; 912 913 914 DbgPrint (ASL_PARSE_OUTPUT, 915 "\nLinkPeerNode: 1=%p (%s), 2=%p (%s)\n\n", 916 Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode) : NULL, 917 Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode) : NULL); 918 919 920 if ((!Op1) && (!Op2)) 921 { 922 DbgPrint (ASL_PARSE_OUTPUT, "\nTwo Null nodes!\n"); 923 return (Op1); 924 } 925 926 /* If one of the nodes is null, just return the non-null node */ 927 928 if (!Op2) 929 { 930 return (Op1); 931 } 932 933 if (!Op1) 934 { 935 return (Op2); 936 } 937 938 if (Op1 == Op2) 939 { 940 DbgPrint (ASL_DEBUG_OUTPUT, 941 "\n\n************* Internal error, linking node to itself %p\n\n\n", 942 Op1); 943 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Op1, 944 "Linking node to itself"); 945 return (Op1); 946 } 947 948 Op1->Asl.Parent = Op2->Asl.Parent; 949 950 /* 951 * Op 1 may already have a peer list (such as an IF/ELSE pair), 952 * so we must walk to the end of the list and attach the new 953 * peer at the end 954 */ 955 Next = Op1; 956 while (Next->Asl.Next) 957 { 958 Next = Next->Asl.Next; 959 } 960 961 Next->Asl.Next = Op2; 962 return (Op1); 963 } 964 965 966 /******************************************************************************* 967 * 968 * FUNCTION: TrLinkPeerNodes 969 * 970 * PARAMETERS: NumPeers - The number of nodes in the list to follow 971 * ... - A list of nodes to link together as peers 972 * 973 * RETURN: The first node in the list (head of the peer list) 974 * 975 * DESCRIPTION: Link together an arbitrary number of peer nodes. 976 * 977 ******************************************************************************/ 978 979 ACPI_PARSE_OBJECT * 980 TrLinkPeerNodes ( 981 UINT32 NumPeers, 982 ...) 983 { 984 ACPI_PARSE_OBJECT *This; 985 ACPI_PARSE_OBJECT *Next; 986 va_list ap; 987 UINT32 i; 988 ACPI_PARSE_OBJECT *Start; 989 990 991 DbgPrint (ASL_PARSE_OUTPUT, 992 "\nLinkPeerNodes: (%u) ", NumPeers); 993 994 va_start (ap, NumPeers); 995 This = va_arg (ap, ACPI_PARSE_OBJECT *); 996 Start = This; 997 998 /* 999 * Link all peers 1000 */ 1001 for (i = 0; i < (NumPeers -1); i++) 1002 { 1003 DbgPrint (ASL_PARSE_OUTPUT, "%u=%p ", (i+1), This); 1004 1005 while (This->Asl.Next) 1006 { 1007 This = This->Asl.Next; 1008 } 1009 1010 /* Get another peer node */ 1011 1012 Next = va_arg (ap, ACPI_PARSE_OBJECT *); 1013 if (!Next) 1014 { 1015 Next = TrAllocateNode (PARSEOP_DEFAULT_ARG); 1016 } 1017 1018 /* link new node to the current node */ 1019 1020 This->Asl.Next = Next; 1021 This = Next; 1022 } 1023 va_end (ap); 1024 1025 DbgPrint (ASL_PARSE_OUTPUT,"\n\n"); 1026 return (Start); 1027 } 1028 1029 1030 /******************************************************************************* 1031 * 1032 * FUNCTION: TrLinkChildNode 1033 * 1034 * PARAMETERS: Op1 - Parent node 1035 * Op2 - Op to become a child 1036 * 1037 * RETURN: The parent node 1038 * 1039 * DESCRIPTION: Link two nodes together as a parent and child 1040 * 1041 ******************************************************************************/ 1042 1043 ACPI_PARSE_OBJECT * 1044 TrLinkChildNode ( 1045 ACPI_PARSE_OBJECT *Op1, 1046 ACPI_PARSE_OBJECT *Op2) 1047 { 1048 ACPI_PARSE_OBJECT *Next; 1049 1050 1051 DbgPrint (ASL_PARSE_OUTPUT, 1052 "\nLinkChildNode: Parent=%p (%s), Child=%p (%s)\n\n", 1053 Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode): NULL, 1054 Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode): NULL); 1055 1056 if (!Op1 || !Op2) 1057 { 1058 return (Op1); 1059 } 1060 1061 Op1->Asl.Child = Op2; 1062 1063 /* Set the child and all peers of the child to point to the parent */ 1064 1065 Next = Op2; 1066 while (Next) 1067 { 1068 Next->Asl.Parent = Op1; 1069 Next = Next->Asl.Next; 1070 } 1071 1072 return (Op1); 1073 } 1074 1075 1076 /******************************************************************************* 1077 * 1078 * FUNCTION: TrWalkParseTree 1079 * 1080 * PARAMETERS: Visitation - Type of walk 1081 * DescendingCallback - Called during tree descent 1082 * AscendingCallback - Called during tree ascent 1083 * Context - To be passed to the callbacks 1084 * 1085 * RETURN: Status from callback(s) 1086 * 1087 * DESCRIPTION: Walk the entire parse tree. 1088 * 1089 ******************************************************************************/ 1090 1091 ACPI_STATUS 1092 TrWalkParseTree ( 1093 ACPI_PARSE_OBJECT *Op, 1094 UINT32 Visitation, 1095 ASL_WALK_CALLBACK DescendingCallback, 1096 ASL_WALK_CALLBACK AscendingCallback, 1097 void *Context) 1098 { 1099 UINT32 Level; 1100 BOOLEAN NodePreviouslyVisited; 1101 ACPI_PARSE_OBJECT *StartOp = Op; 1102 ACPI_STATUS Status; 1103 1104 1105 if (!RootNode) 1106 { 1107 return (AE_OK); 1108 } 1109 1110 Level = 0; 1111 NodePreviouslyVisited = FALSE; 1112 1113 switch (Visitation) 1114 { 1115 case ASL_WALK_VISIT_DOWNWARD: 1116 1117 while (Op) 1118 { 1119 if (!NodePreviouslyVisited) 1120 { 1121 /* Let the callback process the node. */ 1122 1123 Status = DescendingCallback (Op, Level, Context); 1124 if (ACPI_SUCCESS (Status)) 1125 { 1126 /* Visit children first, once */ 1127 1128 if (Op->Asl.Child) 1129 { 1130 Level++; 1131 Op = Op->Asl.Child; 1132 continue; 1133 } 1134 } 1135 else if (Status != AE_CTRL_DEPTH) 1136 { 1137 /* Exit immediately on any error */ 1138 1139 return (Status); 1140 } 1141 } 1142 1143 /* Terminate walk at start op */ 1144 1145 if (Op == StartOp) 1146 { 1147 break; 1148 } 1149 1150 /* No more children, visit peers */ 1151 1152 if (Op->Asl.Next) 1153 { 1154 Op = Op->Asl.Next; 1155 NodePreviouslyVisited = FALSE; 1156 } 1157 else 1158 { 1159 /* No children or peers, re-visit parent */ 1160 1161 if (Level != 0 ) 1162 { 1163 Level--; 1164 } 1165 Op = Op->Asl.Parent; 1166 NodePreviouslyVisited = TRUE; 1167 } 1168 } 1169 break; 1170 1171 case ASL_WALK_VISIT_UPWARD: 1172 1173 while (Op) 1174 { 1175 /* Visit leaf node (no children) or parent node on return trip */ 1176 1177 if ((!Op->Asl.Child) || 1178 (NodePreviouslyVisited)) 1179 { 1180 /* Let the callback process the node. */ 1181 1182 Status = AscendingCallback (Op, Level, Context); 1183 if (ACPI_FAILURE (Status)) 1184 { 1185 return (Status); 1186 } 1187 } 1188 else 1189 { 1190 /* Visit children first, once */ 1191 1192 Level++; 1193 Op = Op->Asl.Child; 1194 continue; 1195 } 1196 1197 /* Terminate walk at start op */ 1198 1199 if (Op == StartOp) 1200 { 1201 break; 1202 } 1203 1204 /* No more children, visit peers */ 1205 1206 if (Op->Asl.Next) 1207 { 1208 Op = Op->Asl.Next; 1209 NodePreviouslyVisited = FALSE; 1210 } 1211 else 1212 { 1213 /* No children or peers, re-visit parent */ 1214 1215 if (Level != 0 ) 1216 { 1217 Level--; 1218 } 1219 Op = Op->Asl.Parent; 1220 NodePreviouslyVisited = TRUE; 1221 } 1222 } 1223 break; 1224 1225 case ASL_WALK_VISIT_TWICE: 1226 1227 while (Op) 1228 { 1229 if (NodePreviouslyVisited) 1230 { 1231 Status = AscendingCallback (Op, Level, Context); 1232 if (ACPI_FAILURE (Status)) 1233 { 1234 return (Status); 1235 } 1236 } 1237 else 1238 { 1239 /* Let the callback process the node. */ 1240 1241 Status = DescendingCallback (Op, Level, Context); 1242 if (ACPI_SUCCESS (Status)) 1243 { 1244 /* Visit children first, once */ 1245 1246 if (Op->Asl.Child) 1247 { 1248 Level++; 1249 Op = Op->Asl.Child; 1250 continue; 1251 } 1252 } 1253 else if (Status != AE_CTRL_DEPTH) 1254 { 1255 /* Exit immediately on any error */ 1256 1257 return (Status); 1258 } 1259 } 1260 1261 /* Terminate walk at start op */ 1262 1263 if (Op == StartOp) 1264 { 1265 break; 1266 } 1267 1268 /* No more children, visit peers */ 1269 1270 if (Op->Asl.Next) 1271 { 1272 Op = Op->Asl.Next; 1273 NodePreviouslyVisited = FALSE; 1274 } 1275 else 1276 { 1277 /* No children or peers, re-visit parent */ 1278 1279 if (Level != 0 ) 1280 { 1281 Level--; 1282 } 1283 Op = Op->Asl.Parent; 1284 NodePreviouslyVisited = TRUE; 1285 } 1286 } 1287 break; 1288 1289 default: 1290 /* No other types supported */ 1291 break; 1292 } 1293 1294 /* If we get here, the walk completed with no errors */ 1295 1296 return (AE_OK); 1297 } 1298