sys/contrib/dev/acpica/compiler/asltree.c

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