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