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