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

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