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