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