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