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 #include "aslcompiler.h"
  45 #include "aslcompiler.y.h"
  46 #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         ACPI_FREE (Path);
 534         Op->Asl.Value.String = Filename;
 535         break;
 536
 537     case PARSEOP___DATE__:
 538
 539         Op = TrAllocateNode (PARSEOP_STRING_LITERAL);
 540
 541         /* Get a copy of the current time */
 542
 543         CurrentTime = time (NULL);
 544         StaticTimeString = ctime (&CurrentTime);
 545         TimeString = UtLocalCalloc (strlen (StaticTimeString) + 1);
 546         strcpy (TimeString, StaticTimeString);
 547
 548         TimeString[strlen(TimeString) -1] = 0;  /* Remove trailing newline */
 549         Op->Asl.Value.String = TimeString;
 550         break;
 551
 552     default: /* This would be an internal error */
 553
 554         return (NULL);
 555     }
 556
 557     DbgPrint (ASL_PARSE_OUTPUT,
 558         "\nCreateConstantLeafNode  Ln/Col %u/%u NewNode %p  Op %s  Value %8.8X%8.8X  ",
 559         Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName (ParseOpcode),
 560         ACPI_FORMAT_UINT64 (Op->Asl.Value.Integer));
 561     return (Op);
 562 }
 563
 564
 565 /*******************************************************************************
 566  *
 567  * FUNCTION:    TrCreateValuedLeafNode
 568  *
 569  * PARAMETERS:  ParseOpcode         - New opcode to be assigned to the node
 570  *              Value               - Value to be assigned to the node
 571  *
 572  * RETURN:      Pointer to the new node. Aborts on allocation failure
 573  *
 574  * DESCRIPTION: Create a leaf node (no children or peers) with a value
 575  *              assigned to it
 576  *
 577  ******************************************************************************/
 578
 579 ACPI_PARSE_OBJECT *
 580 TrCreateValuedLeafNode (
 581     UINT32                  ParseOpcode,
 582     UINT64                  Value)
 583 {
 584     ACPI_PARSE_OBJECT       *Op;
 585
 586
 587     Op = TrAllocateNode (ParseOpcode);
 588
 589     DbgPrint (ASL_PARSE_OUTPUT,
 590         "\nCreateValuedLeafNode  Ln/Col %u/%u NewNode %p  Op %s  Value %8.8X%8.8X  ",
 591         Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName(ParseOpcode),
 592         ACPI_FORMAT_UINT64 (Value));
 593     Op->Asl.Value.Integer = Value;
 594
 595     switch (ParseOpcode)
 596     {
 597     case PARSEOP_STRING_LITERAL:
 598
 599         DbgPrint (ASL_PARSE_OUTPUT, "STRING->%s", Value);
 600         break;
 601
 602     case PARSEOP_NAMESEG:
 603
 604         DbgPrint (ASL_PARSE_OUTPUT, "NAMESEG->%s", Value);
 605         break;
 606
 607     case PARSEOP_NAMESTRING:
 608
 609         DbgPrint (ASL_PARSE_OUTPUT, "NAMESTRING->%s", Value);
 610         break;
 611
 612     case PARSEOP_EISAID:
 613
 614         DbgPrint (ASL_PARSE_OUTPUT, "EISAID->%s", Value);
 615         break;
 616
 617     case PARSEOP_METHOD:
 618
 619         DbgPrint (ASL_PARSE_OUTPUT, "METHOD");
 620         break;
 621
 622     case PARSEOP_INTEGER:
 623
 624         DbgPrint (ASL_PARSE_OUTPUT, "INTEGER");
 625         break;
 626
 627     default:
 628
 629         break;
 630     }
 631
 632     DbgPrint (ASL_PARSE_OUTPUT, "\n\n");
 633     return (Op);
 634 }
 635
 636
 637 /*******************************************************************************
 638  *
 639  * FUNCTION:    TrCreateNode
 640  *
 641  * PARAMETERS:  ParseOpcode         - Opcode to be assigned to the node
 642  *              NumChildren         - Number of children to follow
 643  *              ...                 - A list of child nodes to link to the new
 644  *                                    node. NumChildren long.
 645  *
 646  * RETURN:      Pointer to the new node. Aborts on allocation failure
 647  *
 648  * DESCRIPTION: Create a new parse node and link together a list of child
 649  *              nodes underneath the new node.
 650  *
 651  ******************************************************************************/
 652
 653 ACPI_PARSE_OBJECT *
 654 TrCreateNode (
 655     UINT32                  ParseOpcode,
 656     UINT32                  NumChildren,
 657     ...)
 658 {
 659     ACPI_PARSE_OBJECT       *Op;
 660     ACPI_PARSE_OBJECT       *Child;
 661     ACPI_PARSE_OBJECT       *PrevChild;
 662     va_list                 ap;
 663     UINT32                  i;
 664     BOOLEAN                 FirstChild;
 665
 666
 667     va_start (ap, NumChildren);
 668
 669     /* Allocate one new node */
 670
 671     Op = TrAllocateNode (ParseOpcode);
 672
 673     DbgPrint (ASL_PARSE_OUTPUT,
 674         "\nCreateNode  Ln/Col %u/%u NewParent %p Child %u Op %s  ",
 675         Op->Asl.LineNumber, Op->Asl.Column, Op, NumChildren, UtGetOpName(ParseOpcode));
 676
 677     /* Some extra debug output based on the parse opcode */
 678
 679     switch (ParseOpcode)
 680     {
 681     case PARSEOP_DEFINITIONBLOCK:
 682
 683         RootNode = Op;
 684         DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->");
 685         break;
 686
 687     case PARSEOP_OPERATIONREGION:
 688
 689         DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->");
 690         break;
 691
 692     case PARSEOP_OR:
 693
 694         DbgPrint (ASL_PARSE_OUTPUT, "OR->");
 695         break;
 696
 697     default:
 698
 699         /* Nothing to do for other opcodes */
 700
 701         break;
 702     }
 703
 704     /* Link the new node to its children */
 705
 706     PrevChild = NULL;
 707     FirstChild = TRUE;
 708     for (i = 0; i < NumChildren; i++)
 709     {
 710         /* Get the next child */
 711
 712         Child = va_arg (ap, ACPI_PARSE_OBJECT *);
 713         DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child);
 714
 715         /*
 716          * If child is NULL, this means that an optional argument
 717          * was omitted. We must create a placeholder with a special
 718          * opcode (DEFAULT_ARG) so that the code generator will know
 719          * that it must emit the correct default for this argument
 720          */
 721         if (!Child)
 722         {
 723             Child = TrAllocateNode (PARSEOP_DEFAULT_ARG);
 724         }
 725
 726         /* Link first child to parent */
 727
 728         if (FirstChild)
 729         {
 730             FirstChild = FALSE;
 731             Op->Asl.Child = Child;
 732         }
 733
 734         /* Point all children to parent */
 735
 736         Child->Asl.Parent = Op;
 737
 738         /* Link children in a peer list */
 739
 740         if (PrevChild)
 741         {
 742             PrevChild->Asl.Next = Child;
 743         };
 744
 745         /*
 746          * This child might be a list, point all nodes in the list
 747          * to the same parent
 748          */
 749         while (Child->Asl.Next)
 750         {
 751             Child = Child->Asl.Next;
 752             Child->Asl.Parent = Op;
 753         }
 754
 755         PrevChild = Child;
 756     }
 757     va_end(ap);
 758
 759     DbgPrint (ASL_PARSE_OUTPUT, "\n\n");
 760     return (Op);
 761 }
 762
 763
 764 /*******************************************************************************
 765  *
 766  * FUNCTION:    TrLinkChildren
 767  *
 768  * PARAMETERS:  Op                - An existing parse node
 769  *              NumChildren         - Number of children to follow
 770  *              ...                 - A list of child nodes to link to the new
 771  *                                    node. NumChildren long.
 772  *
 773  * RETURN:      The updated (linked) node
 774  *
 775  * DESCRIPTION: Link a group of nodes to an existing parse node
 776  *
 777  ******************************************************************************/
 778
 779 ACPI_PARSE_OBJECT *
 780 TrLinkChildren (
 781     ACPI_PARSE_OBJECT       *Op,
 782     UINT32                  NumChildren,
 783     ...)
 784 {
 785     ACPI_PARSE_OBJECT       *Child;
 786     ACPI_PARSE_OBJECT       *PrevChild;
 787     va_list                 ap;
 788     UINT32                  i;
 789     BOOLEAN                 FirstChild;
 790
 791
 792     va_start (ap, NumChildren);
 793
 794
 795     TrSetEndLineNumber (Op);
 796
 797     DbgPrint (ASL_PARSE_OUTPUT,
 798         "\nLinkChildren  Line [%u to %u] NewParent %p Child %u Op %s  ",
 799         Op->Asl.LineNumber, Op->Asl.EndLine,
 800         Op, NumChildren, UtGetOpName(Op->Asl.ParseOpcode));
 801
 802     switch (Op->Asl.ParseOpcode)
 803     {
 804     case PARSEOP_DEFINITIONBLOCK:
 805
 806         RootNode = Op;
 807         DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->");
 808         break;
 809
 810     case PARSEOP_OPERATIONREGION:
 811
 812         DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->");
 813         break;
 814
 815     case PARSEOP_OR:
 816
 817         DbgPrint (ASL_PARSE_OUTPUT, "OR->");
 818         break;
 819
 820     default:
 821
 822         /* Nothing to do for other opcodes */
 823
 824         break;
 825     }
 826
 827     /* Link the new node to it's children */
 828
 829     PrevChild = NULL;
 830     FirstChild = TRUE;
 831     for (i = 0; i < NumChildren; i++)
 832     {
 833         Child = va_arg (ap, ACPI_PARSE_OBJECT *);
 834
 835         if ((Child == PrevChild) && (Child != NULL))
 836         {
 837             AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Child,
 838                 "Child node list invalid");
 839             va_end(ap);
 840             return (Op);
 841         }
 842
 843         DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child);
 844
 845         /*
 846          * If child is NULL, this means that an optional argument
 847          * was omitted. We must create a placeholder with a special
 848          * opcode (DEFAULT_ARG) so that the code generator will know
 849          * that it must emit the correct default for this argument
 850          */
 851         if (!Child)
 852         {
 853             Child = TrAllocateNode (PARSEOP_DEFAULT_ARG);
 854         }
 855
 856         /* Link first child to parent */
 857
 858         if (FirstChild)
 859         {
 860             FirstChild = FALSE;
 861             Op->Asl.Child = Child;
 862         }
 863
 864         /* Point all children to parent */
 865
 866         Child->Asl.Parent = Op;
 867
 868         /* Link children in a peer list */
 869
 870         if (PrevChild)
 871         {
 872             PrevChild->Asl.Next = Child;
 873         };
 874
 875         /*
 876          * This child might be a list, point all nodes in the list
 877          * to the same parent
 878          */
 879         while (Child->Asl.Next)
 880         {
 881             Child = Child->Asl.Next;
 882             Child->Asl.Parent = Op;
 883         }
 884         PrevChild = Child;
 885     }
 886
 887     va_end(ap);
 888     DbgPrint (ASL_PARSE_OUTPUT, "\n\n");
 889     return (Op);
 890 }
 891
 892
 893 /*******************************************************************************
 894  *
 895  * FUNCTION:    TrLinkPeerNode
 896  *
 897  * PARAMETERS:  Op1           - First peer
 898  *              Op2           - Second peer
 899  *
 900  * RETURN:      Op1 or the non-null node.
 901  *
 902  * DESCRIPTION: Link two nodes as peers. Handles cases where one peer is null.
 903  *
 904  ******************************************************************************/
 905
 906 ACPI_PARSE_OBJECT *
 907 TrLinkPeerNode (
 908     ACPI_PARSE_OBJECT       *Op1,
 909     ACPI_PARSE_OBJECT       *Op2)
 910 {
 911     ACPI_PARSE_OBJECT       *Next;
 912
 913
 914     DbgPrint (ASL_PARSE_OUTPUT,
 915         "\nLinkPeerNode: 1=%p (%s), 2=%p (%s)\n\n",
 916         Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode) : NULL,
 917         Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode) : NULL);
 918
 919
 920     if ((!Op1) && (!Op2))
 921     {
 922         DbgPrint (ASL_PARSE_OUTPUT, "\nTwo Null nodes!\n");
 923         return (Op1);
 924     }
 925
 926     /* If one of the nodes is null, just return the non-null node */
 927
 928     if (!Op2)
 929     {
 930         return (Op1);
 931     }
 932
 933     if (!Op1)
 934     {
 935         return (Op2);
 936     }
 937
 938     if (Op1 == Op2)
 939     {
 940         DbgPrint (ASL_DEBUG_OUTPUT,
 941             "\n\n************* Internal error, linking node to itself %p\n\n\n",
 942             Op1);
 943         AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Op1,
 944             "Linking node to itself");
 945         return (Op1);
 946     }
 947
 948     Op1->Asl.Parent = Op2->Asl.Parent;
 949
 950     /*
 951      * Op 1 may already have a peer list (such as an IF/ELSE pair),
 952      * so we must walk to the end of the list and attach the new
 953      * peer at the end
 954      */
 955     Next = Op1;
 956     while (Next->Asl.Next)
 957     {
 958         Next = Next->Asl.Next;
 959     }
 960
 961     Next->Asl.Next = Op2;
 962     return (Op1);
 963 }
 964
 965
 966 /*******************************************************************************
 967  *
 968  * FUNCTION:    TrLinkPeerNodes
 969  *
 970  * PARAMETERS:  NumPeers            - The number of nodes in the list to follow
 971  *              ...                 - A list of nodes to link together as peers
 972  *
 973  * RETURN:      The first node in the list (head of the peer list)
 974  *
 975  * DESCRIPTION: Link together an arbitrary number of peer nodes.
 976  *
 977  ******************************************************************************/
 978
 979 ACPI_PARSE_OBJECT *
 980 TrLinkPeerNodes (
 981     UINT32                  NumPeers,
 982     ...)
 983 {
 984     ACPI_PARSE_OBJECT       *This;
 985     ACPI_PARSE_OBJECT       *Next;
 986     va_list                 ap;
 987     UINT32                  i;
 988     ACPI_PARSE_OBJECT       *Start;
 989
 990
 991     DbgPrint (ASL_PARSE_OUTPUT,
 992         "\nLinkPeerNodes: (%u) ", NumPeers);
 993
 994     va_start (ap, NumPeers);
 995     This = va_arg (ap, ACPI_PARSE_OBJECT *);
 996     Start = This;
 997
 998     /*
 999      * Link all peers
1000      */
1001     for (i = 0; i < (NumPeers -1); i++)
1002     {
1003         DbgPrint (ASL_PARSE_OUTPUT, "%u=%p ", (i+1), This);
1004
1005         while (This->Asl.Next)
1006         {
1007             This = This->Asl.Next;
1008         }
1009
1010         /* Get another peer node */
1011
1012         Next = va_arg (ap, ACPI_PARSE_OBJECT *);
1013         if (!Next)
1014         {
1015             Next = TrAllocateNode (PARSEOP_DEFAULT_ARG);
1016         }
1017
1018         /* link new node to the current node */
1019
1020         This->Asl.Next = Next;
1021         This = Next;
1022     }
1023     va_end (ap);
1024
1025     DbgPrint (ASL_PARSE_OUTPUT,"\n\n");
1026     return (Start);
1027 }
1028
1029
1030 /*******************************************************************************
1031  *
1032  * FUNCTION:    TrLinkChildNode
1033  *
1034  * PARAMETERS:  Op1           - Parent node
1035  *              Op2           - Op to become a child
1036  *
1037  * RETURN:      The parent node
1038  *
1039  * DESCRIPTION: Link two nodes together as a parent and child
1040  *
1041  ******************************************************************************/
1042
1043 ACPI_PARSE_OBJECT *
1044 TrLinkChildNode (
1045     ACPI_PARSE_OBJECT       *Op1,
1046     ACPI_PARSE_OBJECT       *Op2)
1047 {
1048     ACPI_PARSE_OBJECT       *Next;
1049
1050
1051     DbgPrint (ASL_PARSE_OUTPUT,
1052         "\nLinkChildNode: Parent=%p (%s), Child=%p (%s)\n\n",
1053         Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode): NULL,
1054         Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode): NULL);
1055
1056     if (!Op1 || !Op2)
1057     {
1058         return (Op1);
1059     }
1060
1061     Op1->Asl.Child = Op2;
1062
1063     /* Set the child and all peers of the child to point to the parent */
1064
1065     Next = Op2;
1066     while (Next)
1067     {
1068         Next->Asl.Parent = Op1;
1069         Next = Next->Asl.Next;
1070     }
1071
1072     return (Op1);
1073 }
1074
1075
1076 /*******************************************************************************
1077  *
1078  * FUNCTION:    TrWalkParseTree
1079  *
1080  * PARAMETERS:  Visitation              - Type of walk
1081  *              DescendingCallback      - Called during tree descent
1082  *              AscendingCallback       - Called during tree ascent
1083  *              Context                 - To be passed to the callbacks
1084  *
1085  * RETURN:      Status from callback(s)
1086  *
1087  * DESCRIPTION: Walk the entire parse tree.
1088  *
1089  ******************************************************************************/
1090
1091 ACPI_STATUS
1092 TrWalkParseTree (
1093     ACPI_PARSE_OBJECT       *Op,
1094     UINT32                  Visitation,
1095     ASL_WALK_CALLBACK       DescendingCallback,
1096     ASL_WALK_CALLBACK       AscendingCallback,
1097     void                    *Context)
1098 {
1099     UINT32                  Level;
1100     BOOLEAN                 NodePreviouslyVisited;
1101     ACPI_PARSE_OBJECT       *StartOp = Op;
1102     ACPI_STATUS             Status;
1103
1104
1105     if (!RootNode)
1106     {
1107         return (AE_OK);
1108     }
1109
1110     Level = 0;
1111     NodePreviouslyVisited = FALSE;
1112
1113     switch (Visitation)
1114     {
1115     case ASL_WALK_VISIT_DOWNWARD:
1116
1117         while (Op)
1118         {
1119             if (!NodePreviouslyVisited)
1120             {
1121                 /* Let the callback process the node. */
1122
1123                 Status = DescendingCallback (Op, Level, Context);
1124                 if (ACPI_SUCCESS (Status))
1125                 {
1126                     /* Visit children first, once */
1127
1128                     if (Op->Asl.Child)
1129                     {
1130                         Level++;
1131                         Op = Op->Asl.Child;
1132                         continue;
1133                     }
1134                 }
1135                 else if (Status != AE_CTRL_DEPTH)
1136                 {
1137                     /* Exit immediately on any error */
1138
1139                     return (Status);
1140                 }
1141             }
1142
1143             /* Terminate walk at start op */
1144
1145             if (Op == StartOp)
1146             {
1147                 break;
1148             }
1149
1150             /* No more children, visit peers */
1151
1152             if (Op->Asl.Next)
1153             {
1154                 Op = Op->Asl.Next;
1155                 NodePreviouslyVisited = FALSE;
1156             }
1157             else
1158             {
1159                 /* No children or peers, re-visit parent */
1160
1161                 if (Level != 0 )
1162                 {
1163                     Level--;
1164                 }
1165                 Op = Op->Asl.Parent;
1166                 NodePreviouslyVisited = TRUE;
1167             }
1168         }
1169         break;
1170
1171     case ASL_WALK_VISIT_UPWARD:
1172
1173         while (Op)
1174         {
1175             /* Visit leaf node (no children) or parent node on return trip */
1176
1177             if ((!Op->Asl.Child) ||
1178                 (NodePreviouslyVisited))
1179             {
1180                 /* Let the callback process the node. */
1181
1182                 Status = AscendingCallback (Op, Level, Context);
1183                 if (ACPI_FAILURE (Status))
1184                 {
1185                     return (Status);
1186                 }
1187             }
1188             else
1189             {
1190                 /* Visit children first, once */
1191
1192                 Level++;
1193                 Op = Op->Asl.Child;
1194                 continue;
1195             }
1196
1197             /* Terminate walk at start op */
1198
1199             if (Op == StartOp)
1200             {
1201                 break;
1202             }
1203
1204             /* No more children, visit peers */
1205
1206             if (Op->Asl.Next)
1207             {
1208                 Op = Op->Asl.Next;
1209                 NodePreviouslyVisited = FALSE;
1210             }
1211             else
1212             {
1213                 /* No children or peers, re-visit parent */
1214
1215                 if (Level != 0 )
1216                 {
1217                     Level--;
1218                 }
1219                 Op = Op->Asl.Parent;
1220                 NodePreviouslyVisited = TRUE;
1221             }
1222         }
1223         break;
1224
1225      case ASL_WALK_VISIT_TWICE:
1226
1227         while (Op)
1228         {
1229             if (NodePreviouslyVisited)
1230             {
1231                 Status = AscendingCallback (Op, Level, Context);
1232                 if (ACPI_FAILURE (Status))
1233                 {
1234                     return (Status);
1235                 }
1236             }
1237             else
1238             {
1239                 /* Let the callback process the node. */
1240
1241                 Status = DescendingCallback (Op, Level, Context);
1242                 if (ACPI_SUCCESS (Status))
1243                 {
1244                     /* Visit children first, once */
1245
1246                     if (Op->Asl.Child)
1247                     {
1248                         Level++;
1249                         Op = Op->Asl.Child;
1250                         continue;
1251                     }
1252                 }
1253                 else if (Status != AE_CTRL_DEPTH)
1254                 {
1255                     /* Exit immediately on any error */
1256
1257                     return (Status);
1258                 }
1259             }
1260
1261             /* Terminate walk at start op */
1262
1263             if (Op == StartOp)
1264             {
1265                 break;
1266             }
1267
1268             /* No more children, visit peers */
1269
1270             if (Op->Asl.Next)
1271             {
1272                 Op = Op->Asl.Next;
1273                 NodePreviouslyVisited = FALSE;
1274             }
1275             else
1276             {
1277                 /* No children or peers, re-visit parent */
1278
1279                 if (Level != 0 )
1280                 {
1281                     Level--;
1282                 }
1283                 Op = Op->Asl.Parent;
1284                 NodePreviouslyVisited = TRUE;
1285             }
1286         }
1287         break;
1288
1289     default:
1290         /* No other types supported */
1291         break;
1292     }
1293
1294     /* If we get here, the walk completed with no errors */
1295
1296     return (AE_OK);
1297 }