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

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