asltree.c revision 167802
1 2/****************************************************************************** 3 * 4 * Module Name: asltree - parse tree management 5 * $Revision: 1.63 $ 6 * 7 *****************************************************************************/ 8 9/****************************************************************************** 10 * 11 * 1. Copyright Notice 12 * 13 * Some or all of this work - Copyright (c) 1999 - 2007, 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 <contrib/dev/acpica/compiler/aslcompiler.h> 120#include "aslcompiler.y.h" 121 122#define _COMPONENT ACPI_COMPILER 123 ACPI_MODULE_NAME ("asltree") 124 125/* Local prototypes */ 126 127static ACPI_PARSE_OBJECT * 128TrGetNextNode ( 129 void); 130 131static char * 132TrGetNodeFlagName ( 133 UINT32 Flags); 134 135 136/******************************************************************************* 137 * 138 * FUNCTION: TrGetNextNode 139 * 140 * PARAMETERS: None 141 * 142 * RETURN: New parse node. Aborts on allocation failure 143 * 144 * DESCRIPTION: Allocate a new parse node for the parse tree. Bypass the local 145 * dynamic memory manager for performance reasons (This has a 146 * major impact on the speed of the compiler.) 147 * 148 ******************************************************************************/ 149 150static ACPI_PARSE_OBJECT * 151TrGetNextNode ( 152 void) 153{ 154 155 if (Gbl_NodeCacheNext >= Gbl_NodeCacheLast) 156 { 157 Gbl_NodeCacheNext = UtLocalCalloc (sizeof (ACPI_PARSE_OBJECT) * 158 ASL_NODE_CACHE_SIZE); 159 Gbl_NodeCacheLast = Gbl_NodeCacheNext + ASL_NODE_CACHE_SIZE; 160 } 161 162 return (Gbl_NodeCacheNext++); 163} 164 165 166/******************************************************************************* 167 * 168 * FUNCTION: TrAllocateNode 169 * 170 * PARAMETERS: ParseOpcode - Opcode to be assigned to the node 171 * 172 * RETURN: New parse node. Aborts on allocation failure 173 * 174 * DESCRIPTION: Allocate and initialize a new parse node for the parse tree 175 * 176 ******************************************************************************/ 177 178ACPI_PARSE_OBJECT * 179TrAllocateNode ( 180 UINT32 ParseOpcode) 181{ 182 ACPI_PARSE_OBJECT *Op; 183 184 185 Op = TrGetNextNode (); 186 187 Op->Asl.ParseOpcode = (UINT16) ParseOpcode; 188 Op->Asl.Filename = Gbl_Files[ASL_FILE_INPUT].Filename; 189 Op->Asl.LineNumber = Gbl_CurrentLineNumber; 190 Op->Asl.LogicalLineNumber = Gbl_LogicalLineNumber; 191 Op->Asl.LogicalByteOffset = Gbl_CurrentLineOffset; 192 Op->Asl.Column = Gbl_CurrentColumn; 193 194 UtSetParseOpName (Op); 195 return Op; 196} 197 198 199/******************************************************************************* 200 * 201 * FUNCTION: TrReleaseNode 202 * 203 * PARAMETERS: Op - Op to be released 204 * 205 * RETURN: None 206 * 207 * DESCRIPTION: "release" a node. In truth, nothing is done since the node 208 * is part of a larger buffer 209 * 210 ******************************************************************************/ 211 212void 213TrReleaseNode ( 214 ACPI_PARSE_OBJECT *Op) 215{ 216 217 return; 218} 219 220 221/******************************************************************************* 222 * 223 * FUNCTION: TrUpdateNode 224 * 225 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 226 * Op - An existing parse node 227 * 228 * RETURN: The updated node 229 * 230 * DESCRIPTION: Change the parse opcode assigned to a node. Usually used to 231 * change an opcode to DEFAULT_ARG so that the node is ignored 232 * during the code generation. Also used to set generic integers 233 * to a specific size (8, 16, 32, or 64 bits) 234 * 235 ******************************************************************************/ 236 237ACPI_PARSE_OBJECT * 238TrUpdateNode ( 239 UINT32 ParseOpcode, 240 ACPI_PARSE_OBJECT *Op) 241{ 242 243 if (!Op) 244 { 245 return NULL; 246 } 247 248 DbgPrint (ASL_PARSE_OUTPUT, 249 "\nUpdateNode: Old - %s, New - %s\n\n", 250 UtGetOpName (Op->Asl.ParseOpcode), 251 UtGetOpName (ParseOpcode)); 252 253 /* Assign new opcode and name */ 254 255 if (Op->Asl.ParseOpcode == PARSEOP_ONES) 256 { 257 switch (ParseOpcode) 258 { 259 case PARSEOP_BYTECONST: 260 Op->Asl.Value.Integer = 0xFF; 261 break; 262 263 case PARSEOP_WORDCONST: 264 Op->Asl.Value.Integer = 0xFFFF; 265 break; 266 267 case PARSEOP_DWORDCONST: 268 Op->Asl.Value.Integer = 0xFFFFFFFF; 269 break; 270 271 default: 272 /* Don't care about others, don't need to check QWORD */ 273 break; 274 } 275 } 276 277 Op->Asl.ParseOpcode = (UINT16) ParseOpcode; 278 UtSetParseOpName (Op); 279 280 /* 281 * For the BYTE, WORD, and DWORD constants, make sure that the integer 282 * that was passed in will actually fit into the data type 283 */ 284 switch (ParseOpcode) 285 { 286 case PARSEOP_BYTECONST: 287 Op = UtCheckIntegerRange (Op, 0x00, ACPI_UINT8_MAX); 288 break; 289 290 case PARSEOP_WORDCONST: 291 Op = UtCheckIntegerRange (Op, 0x00, ACPI_UINT16_MAX); 292 break; 293 294 case PARSEOP_DWORDCONST: 295 Op = UtCheckIntegerRange (Op, 0x00, ACPI_UINT32_MAX); 296 break; 297 298 default: 299 /* Don't care about others, don't need to check QWORD */ 300 break; 301 } 302 303 return Op; 304} 305 306 307/******************************************************************************* 308 * 309 * FUNCTION: TrGetNodeFlagName 310 * 311 * PARAMETERS: Flags - Flags word to be decoded 312 * 313 * RETURN: Name string. Always returns a valid string pointer. 314 * 315 * DESCRIPTION: Decode a flags word 316 * 317 ******************************************************************************/ 318 319static char * 320TrGetNodeFlagName ( 321 UINT32 Flags) 322{ 323 324 switch (Flags) 325 { 326 case NODE_VISITED: 327 return ("NODE_VISITED"); 328 329 case NODE_AML_PACKAGE: 330 return ("NODE_AML_PACKAGE"); 331 332 case NODE_IS_TARGET: 333 return ("NODE_IS_TARGET"); 334 335 case NODE_IS_RESOURCE_DESC: 336 return ("NODE_IS_RESOURCE_DESC"); 337 338 case NODE_IS_RESOURCE_FIELD: 339 return ("NODE_IS_RESOURCE_FIELD"); 340 341 case NODE_HAS_NO_EXIT: 342 return ("NODE_HAS_NO_EXIT"); 343 344 case NODE_IF_HAS_NO_EXIT: 345 return ("NODE_IF_HAS_NO_EXIT"); 346 347 case NODE_NAME_INTERNALIZED: 348 return ("NODE_NAME_INTERNALIZED"); 349 350 case NODE_METHOD_NO_RETVAL: 351 return ("NODE_METHOD_NO_RETVAL"); 352 353 case NODE_METHOD_SOME_NO_RETVAL: 354 return ("NODE_METHOD_SOME_NO_RETVAL"); 355 356 case NODE_RESULT_NOT_USED: 357 return ("NODE_RESULT_NOT_USED"); 358 359 case NODE_METHOD_TYPED: 360 return ("NODE_METHOD_TYPED"); 361 362 case NODE_IS_BIT_OFFSET: 363 return ("NODE_IS_BIT_OFFSET"); 364 365 case NODE_COMPILE_TIME_CONST: 366 return ("NODE_COMPILE_TIME_CONST"); 367 368 case NODE_IS_TERM_ARG: 369 return ("NODE_IS_TERM_ARG"); 370 371 case NODE_WAS_ONES_OP: 372 return ("NODE_WAS_ONES_OP"); 373 374 case NODE_IS_NAME_DECLARATION: 375 return ("NODE_IS_NAME_DECLARATION"); 376 377 default: 378 return ("Multiple Flags (or unknown flag) set"); 379 } 380} 381 382 383/******************************************************************************* 384 * 385 * FUNCTION: TrSetNodeFlags 386 * 387 * PARAMETERS: Op - An existing parse node 388 * Flags - New flags word 389 * 390 * RETURN: The updated parser op 391 * 392 * DESCRIPTION: Set bits in the node flags word. Will not clear bits, only set 393 * 394 ******************************************************************************/ 395 396ACPI_PARSE_OBJECT * 397TrSetNodeFlags ( 398 ACPI_PARSE_OBJECT *Op, 399 UINT32 Flags) 400{ 401 402 DbgPrint (ASL_PARSE_OUTPUT, 403 "\nSetNodeFlags: Op %p, %8.8X %s\n\n", Op, Flags, 404 TrGetNodeFlagName (Flags)); 405 406 if (!Op) 407 { 408 return NULL; 409 } 410 411 Op->Asl.CompileFlags |= Flags; 412 413 return Op; 414} 415 416 417/******************************************************************************* 418 * 419 * FUNCTION: TrSetEndLineNumber 420 * 421 * PARAMETERS: Op - An existing parse node 422 * 423 * RETURN: None. 424 * 425 * DESCRIPTION: Set the ending line numbers (file line and logical line) of a 426 * parse node to the current line numbers. 427 * 428 ******************************************************************************/ 429 430void 431TrSetEndLineNumber ( 432 ACPI_PARSE_OBJECT *Op) 433{ 434 435 /* If the end line # is already set, just return */ 436 437 if (Op->Asl.EndLine) 438 { 439 return; 440 } 441 442 Op->Asl.EndLine = Gbl_CurrentLineNumber; 443 Op->Asl.EndLogicalLine = Gbl_LogicalLineNumber; 444} 445 446 447/******************************************************************************* 448 * 449 * FUNCTION: TrCreateLeafNode 450 * 451 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 452 * 453 * RETURN: Pointer to the new node. Aborts on allocation failure 454 * 455 * DESCRIPTION: Create a simple leaf node (no children or peers, and no value 456 * assigned to the node) 457 * 458 ******************************************************************************/ 459 460ACPI_PARSE_OBJECT * 461TrCreateLeafNode ( 462 UINT32 ParseOpcode) 463{ 464 ACPI_PARSE_OBJECT *Op; 465 466 467 Op = TrAllocateNode (ParseOpcode); 468 469 DbgPrint (ASL_PARSE_OUTPUT, 470 "\nCreateLeafNode Ln/Col %d/%d NewNode %p Op %s\n\n", 471 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName(ParseOpcode)); 472 473 return Op; 474} 475 476 477/******************************************************************************* 478 * 479 * FUNCTION: TrCreateValuedLeafNode 480 * 481 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 482 * Value - Value to be assigned to the node 483 * 484 * RETURN: Pointer to the new node. Aborts on allocation failure 485 * 486 * DESCRIPTION: Create a leaf node (no children or peers) with a value 487 * assigned to it 488 * 489 ******************************************************************************/ 490 491ACPI_PARSE_OBJECT * 492TrCreateValuedLeafNode ( 493 UINT32 ParseOpcode, 494 ACPI_INTEGER Value) 495{ 496 ACPI_PARSE_OBJECT *Op; 497 498 499 Op = TrAllocateNode (ParseOpcode); 500 501 DbgPrint (ASL_PARSE_OUTPUT, 502 "\nCreateValuedLeafNode Ln/Col %d/%d NewNode %p Op %s Value %8.8X%8.8X ", 503 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName(ParseOpcode), 504 ACPI_FORMAT_UINT64 (Value)); 505 Op->Asl.Value.Integer = Value; 506 507 switch (ParseOpcode) 508 { 509 case PARSEOP_STRING_LITERAL: 510 DbgPrint (ASL_PARSE_OUTPUT, "STRING->%s", Value); 511 break; 512 513 case PARSEOP_NAMESEG: 514 DbgPrint (ASL_PARSE_OUTPUT, "NAMESEG->%s", Value); 515 break; 516 517 case PARSEOP_NAMESTRING: 518 DbgPrint (ASL_PARSE_OUTPUT, "NAMESTRING->%s", Value); 519 break; 520 521 case PARSEOP_EISAID: 522 DbgPrint (ASL_PARSE_OUTPUT, "EISAID->%s", Value); 523 break; 524 525 case PARSEOP_METHOD: 526 DbgPrint (ASL_PARSE_OUTPUT, "METHOD"); 527 break; 528 529 case PARSEOP_INTEGER: 530 DbgPrint (ASL_PARSE_OUTPUT, "INTEGER"); 531 break; 532 533 default: 534 break; 535 } 536 537 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 538 return Op; 539} 540 541 542/******************************************************************************* 543 * 544 * FUNCTION: TrCreateNode 545 * 546 * PARAMETERS: ParseOpcode - Opcode to be assigned to the node 547 * NumChildren - Number of children to follow 548 * ... - A list of child nodes to link to the new 549 * node. NumChildren long. 550 * 551 * RETURN: Pointer to the new node. Aborts on allocation failure 552 * 553 * DESCRIPTION: Create a new parse node and link together a list of child 554 * nodes underneath the new node. 555 * 556 ******************************************************************************/ 557 558ACPI_PARSE_OBJECT * 559TrCreateNode ( 560 UINT32 ParseOpcode, 561 UINT32 NumChildren, 562 ...) 563{ 564 ACPI_PARSE_OBJECT *Op; 565 ACPI_PARSE_OBJECT *Child; 566 ACPI_PARSE_OBJECT *PrevChild; 567 va_list ap; 568 UINT32 i; 569 BOOLEAN FirstChild; 570 571 572 va_start (ap, NumChildren); 573 574 /* Allocate one new node */ 575 576 Op = TrAllocateNode (ParseOpcode); 577 578 DbgPrint (ASL_PARSE_OUTPUT, 579 "\nCreateNode Ln/Col %d/%d NewParent %p Child %d Op %s ", 580 Op->Asl.LineNumber, Op->Asl.Column, Op, NumChildren, UtGetOpName(ParseOpcode)); 581 582 /* Some extra debug output based on the parse opcode */ 583 584 switch (ParseOpcode) 585 { 586 case PARSEOP_DEFINITIONBLOCK: 587 RootNode = Op; 588 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->"); 589 break; 590 591 case PARSEOP_OPERATIONREGION: 592 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->"); 593 break; 594 595 case PARSEOP_OR: 596 DbgPrint (ASL_PARSE_OUTPUT, "OR->"); 597 break; 598 599 default: 600 /* Nothing to do for other opcodes */ 601 break; 602 } 603 604 /* Link the new node to its children */ 605 606 PrevChild = NULL; 607 FirstChild = TRUE; 608 for (i = 0; i < NumChildren; i++) 609 { 610 /* Get the next child */ 611 612 Child = va_arg (ap, ACPI_PARSE_OBJECT *); 613 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child); 614 615 /* 616 * If child is NULL, this means that an optional argument 617 * was omitted. We must create a placeholder with a special 618 * opcode (DEFAULT_ARG) so that the code generator will know 619 * that it must emit the correct default for this argument 620 */ 621 if (!Child) 622 { 623 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG); 624 } 625 626 /* Link first child to parent */ 627 628 if (FirstChild) 629 { 630 FirstChild = FALSE; 631 Op->Asl.Child = Child; 632 } 633 634 /* Point all children to parent */ 635 636 Child->Asl.Parent = Op; 637 638 /* Link children in a peer list */ 639 640 if (PrevChild) 641 { 642 PrevChild->Asl.Next = Child; 643 }; 644 645 /* 646 * This child might be a list, point all nodes in the list 647 * to the same parent 648 */ 649 while (Child->Asl.Next) 650 { 651 Child = Child->Asl.Next; 652 Child->Asl.Parent = Op; 653 } 654 655 PrevChild = Child; 656 } 657 va_end(ap); 658 659 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 660 return Op; 661} 662 663 664/******************************************************************************* 665 * 666 * FUNCTION: TrLinkChildren 667 * 668 * PARAMETERS: Op - An existing parse node 669 * NumChildren - Number of children to follow 670 * ... - A list of child nodes to link to the new 671 * node. NumChildren long. 672 * 673 * RETURN: The updated (linked) node 674 * 675 * DESCRIPTION: Link a group of nodes to an existing parse node 676 * 677 ******************************************************************************/ 678 679ACPI_PARSE_OBJECT * 680TrLinkChildren ( 681 ACPI_PARSE_OBJECT *Op, 682 UINT32 NumChildren, 683 ...) 684{ 685 ACPI_PARSE_OBJECT *Child; 686 ACPI_PARSE_OBJECT *PrevChild; 687 va_list ap; 688 UINT32 i; 689 BOOLEAN FirstChild; 690 691 692 va_start (ap, NumChildren); 693 694 695 TrSetEndLineNumber (Op); 696 697 DbgPrint (ASL_PARSE_OUTPUT, 698 "\nLinkChildren Line [%d to %d] NewParent %p Child %d Op %s ", 699 Op->Asl.LineNumber, Op->Asl.EndLine, 700 Op, NumChildren, UtGetOpName(Op->Asl.ParseOpcode)); 701 702 switch (Op->Asl.ParseOpcode) 703 { 704 case PARSEOP_DEFINITIONBLOCK: 705 RootNode = Op; 706 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->"); 707 break; 708 709 case PARSEOP_OPERATIONREGION: 710 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->"); 711 break; 712 713 case PARSEOP_OR: 714 DbgPrint (ASL_PARSE_OUTPUT, "OR->"); 715 break; 716 717 default: 718 /* Nothing to do for other opcodes */ 719 break; 720 } 721 722 /* Link the new node to it's children */ 723 724 PrevChild = NULL; 725 FirstChild = TRUE; 726 for (i = 0; i < NumChildren; i++) 727 { 728 Child = va_arg (ap, ACPI_PARSE_OBJECT *); 729 730 if ((Child == PrevChild) && (Child != NULL)) 731 { 732 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Child, 733 "Child node list invalid"); 734 return Op; 735 } 736 737 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child); 738 739 /* 740 * If child is NULL, this means that an optional argument 741 * was omitted. We must create a placeholder with a special 742 * opcode (DEFAULT_ARG) so that the code generator will know 743 * that it must emit the correct default for this argument 744 */ 745 if (!Child) 746 { 747 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG); 748 } 749 750 /* Link first child to parent */ 751 752 if (FirstChild) 753 { 754 FirstChild = FALSE; 755 Op->Asl.Child = Child; 756 } 757 758 /* Point all children to parent */ 759 760 Child->Asl.Parent = Op; 761 762 /* Link children in a peer list */ 763 764 if (PrevChild) 765 { 766 PrevChild->Asl.Next = Child; 767 }; 768 769 /* 770 * This child might be a list, point all nodes in the list 771 * to the same parent 772 */ 773 while (Child->Asl.Next) 774 { 775 Child = Child->Asl.Next; 776 Child->Asl.Parent = Op; 777 } 778 PrevChild = Child; 779 } 780 va_end(ap); 781 782 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 783 return Op; 784} 785 786 787/******************************************************************************* 788 * 789 * FUNCTION: TrLinkPeerNode 790 * 791 * PARAMETERS: Op1 - First peer 792 * Op2 - Second peer 793 * 794 * RETURN: Op1 or the non-null node. 795 * 796 * DESCRIPTION: Link two nodes as peers. Handles cases where one peer is null. 797 * 798 ******************************************************************************/ 799 800ACPI_PARSE_OBJECT * 801TrLinkPeerNode ( 802 ACPI_PARSE_OBJECT *Op1, 803 ACPI_PARSE_OBJECT *Op2) 804{ 805 ACPI_PARSE_OBJECT *Next; 806 807 808 DbgPrint (ASL_PARSE_OUTPUT, 809 "\nLinkPeerNode: 1=%p (%s), 2=%p (%s)\n\n", 810 Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode) : NULL, 811 Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode) : NULL); 812 813 814 if ((!Op1) && (!Op2)) 815 { 816 DbgPrint (ASL_PARSE_OUTPUT, "\nTwo Null nodes!\n"); 817 return Op1; 818 } 819 820 /* If one of the nodes is null, just return the non-null node */ 821 822 if (!Op2) 823 { 824 return Op1; 825 } 826 827 if (!Op1) 828 { 829 return Op2; 830 } 831 832 if (Op1 == Op2) 833 { 834 DbgPrint (ASL_DEBUG_OUTPUT, 835 "\n\n************* Internal error, linking node to itself %p\n\n\n", 836 Op1); 837 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Op1, 838 "Linking node to itself"); 839 return Op1; 840 } 841 842 Op1->Asl.Parent = Op2->Asl.Parent; 843 844 /* 845 * Op 1 may already have a peer list (such as an IF/ELSE pair), 846 * so we must walk to the end of the list and attach the new 847 * peer at the end 848 */ 849 Next = Op1; 850 while (Next->Asl.Next) 851 { 852 Next = Next->Asl.Next; 853 } 854 855 Next->Asl.Next = Op2; 856 return Op1; 857} 858 859 860/******************************************************************************* 861 * 862 * FUNCTION: TrLinkPeerNodes 863 * 864 * PARAMETERS: NumPeers - The number of nodes in the list to follow 865 * ... - A list of nodes to link together as peers 866 * 867 * RETURN: The first node in the list (head of the peer list) 868 * 869 * DESCRIPTION: Link together an arbitrary number of peer nodes. 870 * 871 ******************************************************************************/ 872 873ACPI_PARSE_OBJECT * 874TrLinkPeerNodes ( 875 UINT32 NumPeers, 876 ...) 877{ 878 ACPI_PARSE_OBJECT *This; 879 ACPI_PARSE_OBJECT *Next; 880 va_list ap; 881 UINT32 i; 882 ACPI_PARSE_OBJECT *Start; 883 884 885 DbgPrint (ASL_PARSE_OUTPUT, 886 "\nLinkPeerNodes: (%d) ", NumPeers); 887 888 va_start (ap, NumPeers); 889 This = va_arg (ap, ACPI_PARSE_OBJECT *); 890 Start = This; 891 892 /* 893 * Link all peers 894 */ 895 for (i = 0; i < (NumPeers -1); i++) 896 { 897 DbgPrint (ASL_PARSE_OUTPUT, "%d=%p ", (i+1), This); 898 899 while (This->Asl.Next) 900 { 901 This = This->Asl.Next; 902 } 903 904 /* Get another peer node */ 905 906 Next = va_arg (ap, ACPI_PARSE_OBJECT *); 907 if (!Next) 908 { 909 Next = TrAllocateNode (PARSEOP_DEFAULT_ARG); 910 } 911 912 /* link new node to the current node */ 913 914 This->Asl.Next = Next; 915 This = Next; 916 } 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