\r
import java.util.ArrayList;\r
import java.util.HashMap;\r
+import java.util.Iterator;\r
+import java.util.LinkedList;\r
import java.util.List;\r
import java.util.Map;\r
+import java.util.Stack;\r
+import java.util.HashSet;\r
\r
import org.apache.xmlbeans.XmlObject;\r
import org.tianocore.build.exception.AutoGenException;\r
import org.tianocore.build.global.SurfaceAreaQuery;\r
import org.tianocore.build.id.ModuleIdentification;\r
import org.tianocore.common.exception.EdkException;\r
-\r
+import org.tianocore.common.logger.EdkLog;\r
/**\r
This class This class is to reorder library instance sequence according to\r
library dependence.\r
if (libClassDeclList != null) {\r
for (int j = 0; j < libClassDeclList.length; j++) {\r
if (this.libClassMap.containsKey(libClassDeclList[j])) {\r
- System.out.println(libClassDeclList[j]\r
+ EdkLog.log(EdkLog.EDK_ERROR,libClassDeclList[j]\r
+ " class is already implement by "\r
+ this.libClassMap.get(libClassDeclList[j]));\r
throw new AutoGenException("Library Class: " + libClassDeclList\r
}\r
}\r
}\r
-\r
- //\r
- // Check is the library instance list meet the require;\r
- //\r
- //for (int s = 0; s < this.libInstanceList.size(); s++) {\r
- // String[] libClass = this.libInstanceMap.get(this.libInstanceList\r
- // .get(s));\r
- // if (libClass != null) {\r
- // for (int t = 0; t < libClass.length; t++) {\r
- // if (this.libClassMap.get(libClass[t]) == null) {\r
- //\r
- // Note: There exist a kind of module which depend on \r
- // library class with no instance or whose instance will\r
- // never be linked into the module. \r
- // For this satuation, the module has the description of \r
- // library class in MSA file but no description of \r
- // corresponding library instance in MBD file. There \r
- // will be a warnig message given here after a standard \r
- // log way has been decided.\r
- //\r
- // }\r
- // }\r
- // }\r
- //}\r
}\r
\r
/**\r
@return List which content the ordered library instance.\r
**/\r
List<ModuleIdentification> orderLibInstance() {\r
- List<ModuleIdentification> orderList = new ArrayList<ModuleIdentification>();\r
- //\r
- // Stack of node which track the library instance name ant its visiting\r
- // flag.\r
- //\r
- List<Node> stackList = new ArrayList<Node>();\r
- int stackSize = 0;\r
- ModuleIdentification libInstanceId = null;\r
- if (libInstanceList.size() < 0) {\r
- return null;\r
- }\r
-\r
- //\r
- // Reorder the library instance.\r
- //\r
- for (int i = 0; i < libInstanceList.size(); i++) {\r
+ LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();\r
+ for (int i = 0; i < libInstanceList.size(); ++i) {\r
+ ModuleIdentification current = libInstanceList.get(i).libId;\r
+ int insertPoint = orderList.size();\r
//\r
- // If library instance is already in the order list skip it.\r
- //\r
- if (isInLibInstance(orderList, libInstanceList.get(i).libId)) {\r
- continue;\r
+ // check current library instance against orderred ones in orderList\r
+ // \r
+ for (int j = 0; j < orderList.size(); ++j) {\r
+ ModuleIdentification old = orderList.get(j);\r
+ if (consumes(current, old)) {\r
+ //\r
+ // if current library instance consumes the one in orderList\r
+ // it must be put after\r
+ // \r
+ insertPoint = j + 1;\r
+ } else if (consumes(old, current)) {\r
+ //\r
+ // if current library instance is consumed by the one in orderList\r
+ // it must be put before. And no further check is needed.\r
+ // \r
+ insertPoint = j;\r
+ break;\r
+ }\r
}\r
- \r
- Node node = new Node(libInstanceList.get(i).libId, false);\r
+ orderList.add(insertPoint, current);\r
+ }\r
+\r
+ return orderList;\r
+ }\r
+\r
+ //\r
+ // Test if one library consumes another library\r
+ // \r
+ private boolean consumes(ModuleIdentification lib1, ModuleIdentification lib2) {\r
+ LinkedList<ModuleIdentification> stack = new LinkedList<ModuleIdentification>();\r
+\r
+ stack.add(lib1);\r
+ int j = 0;\r
+ while (j < stack.size()) {\r
//\r
- // Use stack to reorder library instance.\r
- // Push node to stack.\r
+ // get the last library instance in stack, which hasn't been checked\r
+ // \r
+ ModuleIdentification lib = stack.get(j++);\r
//\r
- stackList.add(node);\r
- while (stackList.size() > 0) {\r
- stackSize = stackList.size() - 1;\r
+ // get the library classes consumed by it\r
+ // \r
+ String[] consumedClasses = libInstanceMap.get(lib);\r
+ for (int i = 0; i < consumedClasses.length; ++i) {\r
//\r
- // Pop the first node in stack. If the node flag has been visited\r
- // add this node to orderlist and remove it from stack.\r
+ // for each library class, find its corresponding library instance\r
+ // \r
+ ModuleIdentification consumedLib = libClassMap.get(consumedClasses[i]);\r
//\r
- if (stackList.get(stackSize).isVisit) {\r
- if (!isInLibInstance(orderList,\r
- stackList.get(stackSize).nodeId)) {\r
- orderList.add(stackList.get(stackSize).nodeId);\r
- stackList.remove(stackSize);\r
- }\r
- \r
- } else {\r
- //\r
- // Get the node value and set visit flag as true.\r
- //\r
- stackList.get(stackList.size() - 1).isVisit = true;\r
- String[] libClassList = this.libInstanceMap.get(stackList\r
- .get(stackSize).nodeId);\r
- //\r
- // Push the node dependence library instance to the stack.\r
+ // if the corresponding instance is the "lib2", we can say that\r
+ // "lib1" consumes "lib2"\r
+ // \r
+ if (consumedLib == lib2) {\r
+ EdkLog.log(EdkLog.EDK_DEBUG, lib1 + "\n consumes\n" + lib2 + "\n");\r
+ return true;\r
+ }\r
+ //\r
+ // otherwise, we put it back into the stack to check it later\r
+ // to see if it consumes "lib2" or not. If the library instance\r
+ // consumed by "lib1" consumes "lib2", we can also say that "lib1"\r
+ // consumes "lib2"\r
+ // \r
+ if (consumedLib != null && !stack.contains(consumedLib)) {\r
+ stack.offer(consumedLib);\r
+ } else if (consumedLib == lib1) {\r
//\r
- if (libClassList != null) {\r
- for (int j = 0; j < libClassList.length; j++) {\r
- libInstanceId = this.libClassMap.get(libClassList[j]);\r
- if (libInstanceId != null\r
- && !isInLibInstance(orderList, libInstanceId)) {\r
- //\r
- // If and only if the currently library instance\r
- // is not in stack and it have constructor or \r
- // destructor function, push this library \r
- // instacne in stack.\r
- //\r
- if (!isInStackList(stackList, this.libClassMap\r
- .get(libClassList[j])) && isHaveConsDestructor(libInstanceId)) {\r
- stackList.add(new Node(this.libClassMap\r
- .get(libClassList[j]), false));\r
- }\r
- }\r
- }\r
+ // found circular consume, do nothing now but just print\r
+ // out message for debugging\r
+ // \r
+ String msg = "!!! Library consumes circularly: ";\r
+ for (int k = 0; k < j; k++) {\r
+ msg += stack.get(k).getName() + "->";\r
}\r
+ msg += lib1.getName();\r
+ EdkLog.log(EdkLog.EDK_DEBUG, msg);\r
}\r
}\r
}\r
- return orderList;\r
+ return false;\r
}\r
\r
/**\r