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

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