sys/contrib/dev/acpica-unix-20061109/compiler/asltree.c

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