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