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