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

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