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