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