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