2 /******************************************************************************
4 * Module Name: asltree - parse tree management
6 *****************************************************************************/
8 /******************************************************************************
12 * Some or all of this work - Copyright (c) 1999 - 2009, Intel Corp.
13 * All rights reserved.
17 * 2.1. This is your license from Intel Corp. under its intellectual property
18 * rights. You may have additional license terms from the party that provided
19 * you this software, covering your right to use that party's intellectual
22 * 2.2. Intel grants, free of charge, to any person ("Licensee") obtaining a
23 * copy of the source code appearing in this file ("Covered Code") an
24 * irrevocable, perpetual, worldwide license under Intel's copyrights in the
25 * base code distributed originally by Intel ("Original Intel Code") to copy,
26 * make derivatives, distribute, use and display any portion of the Covered
27 * Code in any form, with the right to sublicense such rights; and
29 * 2.3. Intel grants Licensee a non-exclusive and non-transferable patent
30 * license (with the right to sublicense), under only those claims of Intel
31 * patents that are infringed by the Original Intel Code, to make, use, sell,
32 * offer to sell, and import the Covered Code and derivative works thereof
33 * solely to the minimum extent necessary to exercise the above copyright
34 * license, and in no event shall the patent license extend to any additions
35 * to or modifications of the Original Intel Code. No other license or right
36 * is granted directly or by implication, estoppel or otherwise;
38 * The above copyright and patent license is granted only if the following
43 * 3.1. Redistribution of Source with Rights to Further Distribute Source.
44 * Redistribution of source code of any substantial portion of the Covered
45 * Code or modification with rights to further distribute source must include
46 * the above Copyright Notice, the above License, this list of Conditions,
47 * and the following Disclaimer and Export Compliance provision. In addition,
48 * Licensee must cause all Covered Code to which Licensee contributes to
49 * contain a file documenting the changes Licensee made to create that Covered
50 * Code and the date of any change. Licensee must include in that file the
51 * documentation of any changes made by any predecessor Licensee. Licensee
52 * must include a prominent statement that the modification is derived,
53 * directly or indirectly, from Original Intel Code.
55 * 3.2. Redistribution of Source with no Rights to Further Distribute Source.
56 * Redistribution of source code of any substantial portion of the Covered
57 * Code or modification without rights to further distribute source must
58 * include the following Disclaimer and Export Compliance provision in the
59 * documentation and/or other materials provided with distribution. In
60 * addition, Licensee may not authorize further sublicense of source of any
61 * portion of the Covered Code, and must include terms to the effect that the
62 * license from Licensee to its licensee is limited to the intellectual
63 * property embodied in the software Licensee provides to its licensee, and
64 * not to intellectual property embodied in modifications its licensee may
67 * 3.3. Redistribution of Executable. Redistribution in executable form of any
68 * substantial portion of the Covered Code or modification must reproduce the
69 * above Copyright Notice, and the following Disclaimer and Export Compliance
70 * provision in the documentation and/or other materials provided with the
73 * 3.4. Intel retains all right, title, and interest in and to the Original
76 * 3.5. Neither the name Intel nor any other trademark owned or controlled by
77 * Intel shall be used in advertising or otherwise to promote the sale, use or
78 * other dealings in products derived from or relating to the Covered Code
79 * without prior written authorization from Intel.
81 * 4. Disclaimer and Export Compliance
83 * 4.1. INTEL MAKES NO WARRANTY OF ANY KIND REGARDING ANY SOFTWARE PROVIDED
84 * HERE. ANY SOFTWARE ORIGINATING FROM INTEL OR DERIVED FROM INTEL SOFTWARE
85 * IS PROVIDED "AS IS," AND INTEL WILL NOT PROVIDE ANY SUPPORT, ASSISTANCE,
86 * INSTALLATION, TRAINING OR OTHER SERVICES. INTEL WILL NOT PROVIDE ANY
87 * UPDATES, ENHANCEMENTS OR EXTENSIONS. INTEL SPECIFICALLY DISCLAIMS ANY
88 * IMPLIED WARRANTIES OF MERCHANTABILITY, NONINFRINGEMENT AND FITNESS FOR A
91 * 4.2. IN NO EVENT SHALL INTEL HAVE ANY LIABILITY TO LICENSEE, ITS LICENSEES
92 * OR ANY OTHER THIRD PARTY, FOR ANY LOST PROFITS, LOST DATA, LOSS OF USE OR
93 * COSTS OF PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, OR FOR ANY INDIRECT,
94 * SPECIAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THIS AGREEMENT, UNDER ANY
95 * CAUSE OF ACTION OR THEORY OF LIABILITY, AND IRRESPECTIVE OF WHETHER INTEL
96 * HAS ADVANCE NOTICE OF THE POSSIBILITY OF SUCH DAMAGES. THESE LIMITATIONS
97 * SHALL APPLY NOTWITHSTANDING THE FAILURE OF THE ESSENTIAL PURPOSE OF ANY
100 * 4.3. Licensee shall not export, either directly or indirectly, any of this
101 * software or system incorporating such software without first obtaining any
102 * required license or other approval from the U. S. Department of Commerce or
103 * any other agency or department of the United States Government. In the
104 * event Licensee exports any such software from the United States or
105 * re-exports any such software from a foreign destination, Licensee shall
106 * ensure that the distribution and export/re-export of the software is in
107 * compliance with all laws, regulations, orders, or other restrictions of the
108 * U.S. Export Administration Regulations. Licensee agrees that neither it nor
109 * any of its subsidiaries will export/re-export any technical data, process,
110 * software, or service, directly or indirectly, to any country for which the
111 * United States government or any agency thereof requires an export license,
112 * other governmental approval, or letter of assurance, without first obtaining
113 * such license, approval or letter.
115 *****************************************************************************/
118 #include <contrib/dev/acpica/compiler/aslcompiler.h>
119 #include "aslcompiler.y.h"
121 #define _COMPONENT ACPI_COMPILER
122 ACPI_MODULE_NAME ("asltree")
124 /* Local prototypes */
126 static ACPI_PARSE_OBJECT *
135 /*******************************************************************************
137 * FUNCTION: TrGetNextNode
141 * RETURN: New parse node. Aborts on allocation failure
143 * DESCRIPTION: Allocate a new parse node for the parse tree. Bypass the local
144 * dynamic memory manager for performance reasons (This has a
145 * major impact on the speed of the compiler.)
147 ******************************************************************************/
149 static ACPI_PARSE_OBJECT *
154 if (Gbl_NodeCacheNext >= Gbl_NodeCacheLast)
156 Gbl_NodeCacheNext = UtLocalCalloc (sizeof (ACPI_PARSE_OBJECT) *
157 ASL_NODE_CACHE_SIZE);
158 Gbl_NodeCacheLast = Gbl_NodeCacheNext + ASL_NODE_CACHE_SIZE;
161 return (Gbl_NodeCacheNext++);
165 /*******************************************************************************
167 * FUNCTION: TrAllocateNode
169 * PARAMETERS: ParseOpcode - Opcode to be assigned to the node
171 * RETURN: New parse node. Aborts on allocation failure
173 * DESCRIPTION: Allocate and initialize a new parse node for the parse tree
175 ******************************************************************************/
181 ACPI_PARSE_OBJECT *Op;
184 Op = TrGetNextNode ();
186 Op->Asl.ParseOpcode = (UINT16) ParseOpcode;
187 Op->Asl.Filename = Gbl_Files[ASL_FILE_INPUT].Filename;
188 Op->Asl.LineNumber = Gbl_CurrentLineNumber;
189 Op->Asl.LogicalLineNumber = Gbl_LogicalLineNumber;
190 Op->Asl.LogicalByteOffset = Gbl_CurrentLineOffset;
191 Op->Asl.Column = Gbl_CurrentColumn;
193 UtSetParseOpName (Op);
198 /*******************************************************************************
200 * FUNCTION: TrReleaseNode
202 * PARAMETERS: Op - Op to be released
206 * DESCRIPTION: "release" a node. In truth, nothing is done since the node
207 * is part of a larger buffer
209 ******************************************************************************/
213 ACPI_PARSE_OBJECT *Op)
220 /*******************************************************************************
222 * FUNCTION: TrUpdateNode
224 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node
225 * Op - An existing parse node
227 * RETURN: The updated node
229 * DESCRIPTION: Change the parse opcode assigned to a node. Usually used to
230 * change an opcode to DEFAULT_ARG so that the node is ignored
231 * during the code generation. Also used to set generic integers
232 * to a specific size (8, 16, 32, or 64 bits)
234 ******************************************************************************/
239 ACPI_PARSE_OBJECT *Op)
247 DbgPrint (ASL_PARSE_OUTPUT,
248 "\nUpdateNode: Old - %s, New - %s\n\n",
249 UtGetOpName (Op->Asl.ParseOpcode),
250 UtGetOpName (ParseOpcode));
252 /* Assign new opcode and name */
254 if (Op->Asl.ParseOpcode == PARSEOP_ONES)
258 case PARSEOP_BYTECONST:
259 Op->Asl.Value.Integer = 0xFF;
262 case PARSEOP_WORDCONST:
263 Op->Asl.Value.Integer = 0xFFFF;
266 case PARSEOP_DWORDCONST:
267 Op->Asl.Value.Integer = 0xFFFFFFFF;
271 /* Don't care about others, don't need to check QWORD */
276 Op->Asl.ParseOpcode = (UINT16) ParseOpcode;
277 UtSetParseOpName (Op);
280 * For the BYTE, WORD, and DWORD constants, make sure that the integer
281 * that was passed in will actually fit into the data type
285 case PARSEOP_BYTECONST:
286 Op = UtCheckIntegerRange (Op, 0x00, ACPI_UINT8_MAX);
289 case PARSEOP_WORDCONST:
290 Op = UtCheckIntegerRange (Op, 0x00, ACPI_UINT16_MAX);
293 case PARSEOP_DWORDCONST:
294 Op = UtCheckIntegerRange (Op, 0x00, ACPI_UINT32_MAX);
298 /* Don't care about others, don't need to check QWORD */
306 /*******************************************************************************
308 * FUNCTION: TrGetNodeFlagName
310 * PARAMETERS: Flags - Flags word to be decoded
312 * RETURN: Name string. Always returns a valid string pointer.
314 * DESCRIPTION: Decode a flags word
316 ******************************************************************************/
326 return ("NODE_VISITED");
328 case NODE_AML_PACKAGE:
329 return ("NODE_AML_PACKAGE");
332 return ("NODE_IS_TARGET");
334 case NODE_IS_RESOURCE_DESC:
335 return ("NODE_IS_RESOURCE_DESC");
337 case NODE_IS_RESOURCE_FIELD:
338 return ("NODE_IS_RESOURCE_FIELD");
340 case NODE_HAS_NO_EXIT:
341 return ("NODE_HAS_NO_EXIT");
343 case NODE_IF_HAS_NO_EXIT:
344 return ("NODE_IF_HAS_NO_EXIT");
346 case NODE_NAME_INTERNALIZED:
347 return ("NODE_NAME_INTERNALIZED");
349 case NODE_METHOD_NO_RETVAL:
350 return ("NODE_METHOD_NO_RETVAL");
352 case NODE_METHOD_SOME_NO_RETVAL:
353 return ("NODE_METHOD_SOME_NO_RETVAL");
355 case NODE_RESULT_NOT_USED:
356 return ("NODE_RESULT_NOT_USED");
358 case NODE_METHOD_TYPED:
359 return ("NODE_METHOD_TYPED");
361 case NODE_IS_BIT_OFFSET:
362 return ("NODE_IS_BIT_OFFSET");
364 case NODE_COMPILE_TIME_CONST:
365 return ("NODE_COMPILE_TIME_CONST");
367 case NODE_IS_TERM_ARG:
368 return ("NODE_IS_TERM_ARG");
370 case NODE_WAS_ONES_OP:
371 return ("NODE_WAS_ONES_OP");
373 case NODE_IS_NAME_DECLARATION:
374 return ("NODE_IS_NAME_DECLARATION");
377 return ("Multiple Flags (or unknown flag) set");
382 /*******************************************************************************
384 * FUNCTION: TrSetNodeFlags
386 * PARAMETERS: Op - An existing parse node
387 * Flags - New flags word
389 * RETURN: The updated parser op
391 * DESCRIPTION: Set bits in the node flags word. Will not clear bits, only set
393 ******************************************************************************/
397 ACPI_PARSE_OBJECT *Op,
401 DbgPrint (ASL_PARSE_OUTPUT,
402 "\nSetNodeFlags: Op %p, %8.8X %s\n\n", Op, Flags,
403 TrGetNodeFlagName (Flags));
410 Op->Asl.CompileFlags |= Flags;
416 /*******************************************************************************
418 * FUNCTION: TrSetEndLineNumber
420 * PARAMETERS: Op - An existing parse node
424 * DESCRIPTION: Set the ending line numbers (file line and logical line) of a
425 * parse node to the current line numbers.
427 ******************************************************************************/
431 ACPI_PARSE_OBJECT *Op)
434 /* If the end line # is already set, just return */
441 Op->Asl.EndLine = Gbl_CurrentLineNumber;
442 Op->Asl.EndLogicalLine = Gbl_LogicalLineNumber;
446 /*******************************************************************************
448 * FUNCTION: TrCreateLeafNode
450 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node
452 * RETURN: Pointer to the new node. Aborts on allocation failure
454 * DESCRIPTION: Create a simple leaf node (no children or peers, and no value
455 * assigned to the node)
457 ******************************************************************************/
463 ACPI_PARSE_OBJECT *Op;
466 Op = TrAllocateNode (ParseOpcode);
468 DbgPrint (ASL_PARSE_OUTPUT,
469 "\nCreateLeafNode Ln/Col %d/%d NewNode %p Op %s\n\n",
470 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName(ParseOpcode));
476 /*******************************************************************************
478 * FUNCTION: TrCreateValuedLeafNode
480 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node
481 * Value - Value to be assigned to the node
483 * RETURN: Pointer to the new node. Aborts on allocation failure
485 * DESCRIPTION: Create a leaf node (no children or peers) with a value
488 ******************************************************************************/
491 TrCreateValuedLeafNode (
495 ACPI_PARSE_OBJECT *Op;
498 Op = TrAllocateNode (ParseOpcode);
500 DbgPrint (ASL_PARSE_OUTPUT,
501 "\nCreateValuedLeafNode Ln/Col %d/%d NewNode %p Op %s Value %8.8X%8.8X ",
502 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName(ParseOpcode),
503 ACPI_FORMAT_UINT64 (Value));
504 Op->Asl.Value.Integer = Value;
508 case PARSEOP_STRING_LITERAL:
509 DbgPrint (ASL_PARSE_OUTPUT, "STRING->%s", Value);
512 case PARSEOP_NAMESEG:
513 DbgPrint (ASL_PARSE_OUTPUT, "NAMESEG->%s", Value);
516 case PARSEOP_NAMESTRING:
517 DbgPrint (ASL_PARSE_OUTPUT, "NAMESTRING->%s", Value);
521 DbgPrint (ASL_PARSE_OUTPUT, "EISAID->%s", Value);
525 DbgPrint (ASL_PARSE_OUTPUT, "METHOD");
528 case PARSEOP_INTEGER:
529 DbgPrint (ASL_PARSE_OUTPUT, "INTEGER");
536 DbgPrint (ASL_PARSE_OUTPUT, "\n\n");
541 /*******************************************************************************
543 * FUNCTION: TrCreateNode
545 * PARAMETERS: ParseOpcode - Opcode to be assigned to the node
546 * NumChildren - Number of children to follow
547 * ... - A list of child nodes to link to the new
548 * node. NumChildren long.
550 * RETURN: Pointer to the new node. Aborts on allocation failure
552 * DESCRIPTION: Create a new parse node and link together a list of child
553 * nodes underneath the new node.
555 ******************************************************************************/
563 ACPI_PARSE_OBJECT *Op;
564 ACPI_PARSE_OBJECT *Child;
565 ACPI_PARSE_OBJECT *PrevChild;
571 va_start (ap, NumChildren);
573 /* Allocate one new node */
575 Op = TrAllocateNode (ParseOpcode);
577 DbgPrint (ASL_PARSE_OUTPUT,
578 "\nCreateNode Ln/Col %d/%d NewParent %p Child %d Op %s ",
579 Op->Asl.LineNumber, Op->Asl.Column, Op, NumChildren, UtGetOpName(ParseOpcode));
581 /* Some extra debug output based on the parse opcode */
585 case PARSEOP_DEFINITIONBLOCK:
587 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->");
590 case PARSEOP_OPERATIONREGION:
591 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->");
595 DbgPrint (ASL_PARSE_OUTPUT, "OR->");
599 /* Nothing to do for other opcodes */
603 /* Link the new node to its children */
607 for (i = 0; i < NumChildren; i++)
609 /* Get the next child */
611 Child = va_arg (ap, ACPI_PARSE_OBJECT *);
612 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child);
615 * If child is NULL, this means that an optional argument
616 * was omitted. We must create a placeholder with a special
617 * opcode (DEFAULT_ARG) so that the code generator will know
618 * that it must emit the correct default for this argument
622 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG);
625 /* Link first child to parent */
630 Op->Asl.Child = Child;
633 /* Point all children to parent */
635 Child->Asl.Parent = Op;
637 /* Link children in a peer list */
641 PrevChild->Asl.Next = Child;
645 * This child might be a list, point all nodes in the list
648 while (Child->Asl.Next)
650 Child = Child->Asl.Next;
651 Child->Asl.Parent = Op;
658 DbgPrint (ASL_PARSE_OUTPUT, "\n\n");
663 /*******************************************************************************
665 * FUNCTION: TrLinkChildren
667 * PARAMETERS: Op - An existing parse node
668 * NumChildren - Number of children to follow
669 * ... - A list of child nodes to link to the new
670 * node. NumChildren long.
672 * RETURN: The updated (linked) node
674 * DESCRIPTION: Link a group of nodes to an existing parse node
676 ******************************************************************************/
680 ACPI_PARSE_OBJECT *Op,
684 ACPI_PARSE_OBJECT *Child;
685 ACPI_PARSE_OBJECT *PrevChild;
691 va_start (ap, NumChildren);
694 TrSetEndLineNumber (Op);
696 DbgPrint (ASL_PARSE_OUTPUT,
697 "\nLinkChildren Line [%d to %d] NewParent %p Child %d Op %s ",
698 Op->Asl.LineNumber, Op->Asl.EndLine,
699 Op, NumChildren, UtGetOpName(Op->Asl.ParseOpcode));
701 switch (Op->Asl.ParseOpcode)
703 case PARSEOP_DEFINITIONBLOCK:
705 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->");
708 case PARSEOP_OPERATIONREGION:
709 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->");
713 DbgPrint (ASL_PARSE_OUTPUT, "OR->");
717 /* Nothing to do for other opcodes */
721 /* Link the new node to it's children */
725 for (i = 0; i < NumChildren; i++)
727 Child = va_arg (ap, ACPI_PARSE_OBJECT *);
729 if ((Child == PrevChild) && (Child != NULL))
731 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Child,
732 "Child node list invalid");
736 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child);
739 * If child is NULL, this means that an optional argument
740 * was omitted. We must create a placeholder with a special
741 * opcode (DEFAULT_ARG) so that the code generator will know
742 * that it must emit the correct default for this argument
746 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG);
749 /* Link first child to parent */
754 Op->Asl.Child = Child;
757 /* Point all children to parent */
759 Child->Asl.Parent = Op;
761 /* Link children in a peer list */
765 PrevChild->Asl.Next = Child;
769 * This child might be a list, point all nodes in the list
772 while (Child->Asl.Next)
774 Child = Child->Asl.Next;
775 Child->Asl.Parent = Op;
781 DbgPrint (ASL_PARSE_OUTPUT, "\n\n");
786 /*******************************************************************************
788 * FUNCTION: TrLinkPeerNode
790 * PARAMETERS: Op1 - First peer
793 * RETURN: Op1 or the non-null node.
795 * DESCRIPTION: Link two nodes as peers. Handles cases where one peer is null.
797 ******************************************************************************/
801 ACPI_PARSE_OBJECT *Op1,
802 ACPI_PARSE_OBJECT *Op2)
804 ACPI_PARSE_OBJECT *Next;
807 DbgPrint (ASL_PARSE_OUTPUT,
808 "\nLinkPeerNode: 1=%p (%s), 2=%p (%s)\n\n",
809 Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode) : NULL,
810 Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode) : NULL);
813 if ((!Op1) && (!Op2))
815 DbgPrint (ASL_PARSE_OUTPUT, "\nTwo Null nodes!\n");
819 /* If one of the nodes is null, just return the non-null node */
833 DbgPrint (ASL_DEBUG_OUTPUT,
834 "\n\n************* Internal error, linking node to itself %p\n\n\n",
836 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Op1,
837 "Linking node to itself");
841 Op1->Asl.Parent = Op2->Asl.Parent;
844 * Op 1 may already have a peer list (such as an IF/ELSE pair),
845 * so we must walk to the end of the list and attach the new
849 while (Next->Asl.Next)
851 Next = Next->Asl.Next;
854 Next->Asl.Next = Op2;
859 /*******************************************************************************
861 * FUNCTION: TrLinkPeerNodes
863 * PARAMETERS: NumPeers - The number of nodes in the list to follow
864 * ... - A list of nodes to link together as peers
866 * RETURN: The first node in the list (head of the peer list)
868 * DESCRIPTION: Link together an arbitrary number of peer nodes.
870 ******************************************************************************/
877 ACPI_PARSE_OBJECT *This;
878 ACPI_PARSE_OBJECT *Next;
881 ACPI_PARSE_OBJECT *Start;
884 DbgPrint (ASL_PARSE_OUTPUT,
885 "\nLinkPeerNodes: (%d) ", NumPeers);
887 va_start (ap, NumPeers);
888 This = va_arg (ap, ACPI_PARSE_OBJECT *);
894 for (i = 0; i < (NumPeers -1); i++)
896 DbgPrint (ASL_PARSE_OUTPUT, "%d=%p ", (i+1), This);
898 while (This->Asl.Next)
900 This = This->Asl.Next;
903 /* Get another peer node */
905 Next = va_arg (ap, ACPI_PARSE_OBJECT *);
908 Next = TrAllocateNode (PARSEOP_DEFAULT_ARG);
911 /* link new node to the current node */
913 This->Asl.Next = Next;
918 DbgPrint (ASL_PARSE_OUTPUT,"\n\n");
923 /*******************************************************************************
925 * FUNCTION: TrLinkChildNode
927 * PARAMETERS: Op1 - Parent node
928 * Op2 - Op to become a child
930 * RETURN: The parent node
932 * DESCRIPTION: Link two nodes together as a parent and child
934 ******************************************************************************/
938 ACPI_PARSE_OBJECT *Op1,
939 ACPI_PARSE_OBJECT *Op2)
941 ACPI_PARSE_OBJECT *Next;
944 DbgPrint (ASL_PARSE_OUTPUT,
945 "\nLinkChildNode: Parent=%p (%s), Child=%p (%s)\n\n",
946 Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode): NULL,
947 Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode): NULL);
954 Op1->Asl.Child = Op2;
956 /* Set the child and all peers of the child to point to the parent */
961 Next->Asl.Parent = Op1;
962 Next = Next->Asl.Next;
969 /*******************************************************************************
971 * FUNCTION: TrWalkParseTree
973 * PARAMETERS: Visitation - Type of walk
974 * DescendingCallback - Called during tree descent
975 * AscendingCallback - Called during tree ascent
976 * Context - To be passed to the callbacks
978 * RETURN: Status from callback(s)
980 * DESCRIPTION: Walk the entire parse tree.
982 ******************************************************************************/
986 ACPI_PARSE_OBJECT *Op,
988 ASL_WALK_CALLBACK DescendingCallback,
989 ASL_WALK_CALLBACK AscendingCallback,
993 BOOLEAN NodePreviouslyVisited;
994 ACPI_PARSE_OBJECT *StartOp = Op;
1004 NodePreviouslyVisited = FALSE;
1008 case ASL_WALK_VISIT_DOWNWARD:
1012 if (!NodePreviouslyVisited)
1014 /* Let the callback process the node. */
1016 Status = DescendingCallback (Op, Level, Context);
1017 if (ACPI_SUCCESS (Status))
1019 /* Visit children first, once */
1028 else if (Status != AE_CTRL_DEPTH)
1030 /* Exit immediately on any error */
1036 /* Terminate walk at start op */
1043 /* No more children, visit peers */
1048 NodePreviouslyVisited = FALSE;
1052 /* No children or peers, re-visit parent */
1058 Op = Op->Asl.Parent;
1059 NodePreviouslyVisited = TRUE;
1065 case ASL_WALK_VISIT_UPWARD:
1069 /* Visit leaf node (no children) or parent node on return trip */
1071 if ((!Op->Asl.Child) ||
1072 (NodePreviouslyVisited))
1074 /* Let the callback process the node. */
1076 Status = AscendingCallback (Op, Level, Context);
1077 if (ACPI_FAILURE (Status))
1084 /* Visit children first, once */
1091 /* Terminate walk at start op */
1098 /* No more children, visit peers */
1103 NodePreviouslyVisited = FALSE;
1107 /* No children or peers, re-visit parent */
1113 Op = Op->Asl.Parent;
1114 NodePreviouslyVisited = TRUE;
1120 case ASL_WALK_VISIT_TWICE:
1124 if (NodePreviouslyVisited)
1126 Status = AscendingCallback (Op, Level, Context);
1127 if (ACPI_FAILURE (Status))
1134 /* Let the callback process the node. */
1136 Status = DescendingCallback (Op, Level, Context);
1137 if (ACPI_SUCCESS (Status))
1139 /* Visit children first, once */
1148 else if (Status != AE_CTRL_DEPTH)
1150 /* Exit immediately on any error */
1156 /* Terminate walk at start op */
1163 /* No more children, visit peers */
1168 NodePreviouslyVisited = FALSE;
1172 /* No children or peers, re-visit parent */
1178 Op = Op->Asl.Parent;
1179 NodePreviouslyVisited = TRUE;
1185 /* No other types supported */
1189 /* If we get here, the walk completed with no errors */