+++ /dev/null
-/**@file\r
- AutogenLibOrder class.\r
-\r
- This class is to reorder library instance sequence according to library\r
- dependence.\r
-\r
- Copyright (c) 2006, Intel Corporation\r
- All rights reserved. This program and the accompanying materials\r
- are licensed and made available under the terms and conditions of the BSD License\r
- which accompanies this distribution. The full text of the license may be found at\r
- http://opensource.org/licenses/bsd-license.php\r
-\r
- THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
- WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
-\r
- **/\r
-package org.tianocore.build.autogen;\r
-\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.GlobalData;\r
-import org.tianocore.build.global.SurfaceAreaQuery;\r
-import org.tianocore.build.id.ModuleIdentification;\r
-import org.tianocore.common.exception.EdkException;\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
-**/\r
-public class AutogenLibOrder {\r
- ///\r
- /// The map of library class and its library instance.\r
- ///\r
- private Map<String, ModuleIdentification> libClassProducer = new HashMap<String, ModuleIdentification>();\r
-\r
- ///\r
- /// The map of library instance and its consumed Library Classes.\r
- ///\r
- private Map<ModuleIdentification, String[]> libInstanceConsumes = new HashMap<ModuleIdentification, String[]>();\r
-\r
- ///\r
- /// The map of library instance and its implemeted Library Classes.\r
- ///\r
- private Map<ModuleIdentification, String[]> libInstanceProduces = new HashMap<ModuleIdentification, String[]>();\r
-\r
- ///\r
- /// The map of library instance and its consumers.\r
- ///\r
- private Map<ModuleIdentification, HashSet<ModuleIdentification>> libInstanceConsumedBy = new HashMap<ModuleIdentification, HashSet<ModuleIdentification>>();\r
-\r
- ///\r
- /// List of library instance. It is String[3] list, String[0] is libraryName,\r
- /// String[1] is libraryConstructor name, String[2] is libDestructor name.\r
- ///\r
- private ModuleIdentification[] libInstanceList = null;\r
-\r
- /**\r
- Constructor function\r
-\r
- This function mainly initialize some member variable.\r
-\r
- @param libraryList List of the library instance.\r
- @throws Exception\r
- **/\r
- AutogenLibOrder(ModuleIdentification[] libraryList, String arch) throws EdkException {\r
- ModuleIdentification libInstance;\r
- String[] libClassDeclList = null;\r
- String[] libClassConsmList = null;\r
-\r
- libInstanceList = libraryList;\r
- for (int i = 0; i < libraryList.length; i++) {\r
- libInstance = libraryList[i];\r
- //\r
- // Fetch the constructor & destructor.\r
- //\r
- Map<String, XmlObject> libDoc = GlobalData.getDoc(libInstance, arch);\r
- SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc);\r
- libInstance.setConstructor(saq.getLibConstructorName());\r
- libInstance.setDestructor(saq.getLibDestructorName());\r
-\r
- //\r
- // Create library class consume database.\r
- //\r
- libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch, null);\r
- if (libClassConsmList != null) {\r
- if (this.libInstanceConsumes.containsKey(libInstance)) {\r
- throw new AutoGenException(\r
- libraryList[i].getName()\r
- + "-- this library instance already exists, please check the library instance list!");\r
- } else {\r
- this.libInstanceConsumes.put(libInstance, libClassConsmList);\r
- }\r
- }\r
-\r
- //\r
- // Create library class implementer database\r
- //\r
- libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch, null);\r
- if (libClassDeclList != null) {\r
- this.libInstanceProduces.put(libInstance, libClassDeclList);\r
- for (int j = 0; j < libClassDeclList.length; j++) {\r
- if (this.libClassProducer.containsKey(libClassDeclList[j])) {\r
- EdkLog.log(EdkLog.EDK_ERROR,libClassDeclList[j]\r
- + " class is already implemented by "\r
- + this.libClassProducer.get(libClassDeclList[j]));\r
- throw new AutoGenException("Library Class: " + libClassDeclList\r
- + " already has a library instance!");\r
- } else {\r
- this.libClassProducer.put(libClassDeclList[j], libInstance);\r
- }\r
- }\r
- }\r
- }\r
-\r
- //\r
- // Create a consumed-by database\r
- //\r
- for (Iterator it = libClassProducer.keySet().iterator(); it.hasNext();) {\r
- String className = (String)it.next();\r
- libInstance = libClassProducer.get(className);\r
- libInstanceConsumedBy.put(libInstance, new HashSet<ModuleIdentification>());\r
-\r
- for (int k = 0; k < libraryList.length; ++k) {\r
- ModuleIdentification consumer = libraryList[k];\r
- String[] consumedClassList = libInstanceConsumes.get(consumer);\r
-\r
- for (int l = 0; l < consumedClassList.length; ++l) {\r
- if (consumedClassList[l].equals(className)) {\r
- libInstanceConsumedBy.get(libInstance).add(consumer);\r
- }\r
- }\r
- }\r
- }\r
- }\r
-\r
- /**\r
- orderLibInstance\r
-\r
- This function reorder the library instance according the library class\r
- dependency, using DAG anaylysis algothim\r
-\r
- @return List which content the ordered library instance.\r
- **/\r
- List<ModuleIdentification> orderLibInstance() throws EdkException {\r
- LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();\r
- LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();\r
-\r
- //\r
- // First, add the library instance without consumers to the Q\r
- //\r
- for (int i = 0; i < libInstanceList.length; ++i) {\r
- if (libInstanceList[i] == null) {\r
- continue;\r
- }\r
- \r
- if (libInstanceConsumedBy.get(libInstanceList[i]) == null || libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) {\r
- noConsumerList.add(libInstanceList[i]);\r
- }\r
- }\r
-\r
- while (noConsumerList.size() > 0) {\r
- ModuleIdentification n = noConsumerList.poll();\r
- orderList.addFirst(n);\r
-\r
- String[] consumedClassList = libInstanceConsumes.get(n);\r
- for (int i = 0; i < consumedClassList.length; ++i) {\r
- ModuleIdentification m = libClassProducer.get(consumedClassList[i]);\r
- if (m == null) {\r
- continue;\r
- }\r
- HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);\r
- if (consumedBy == null || consumedBy.size() == 0) {\r
- continue;\r
- }\r
-\r
- consumedBy.remove(n);\r
- if (consumedBy.size() == 0) {\r
- noConsumerList.addLast(m);\r
- }\r
- }\r
-\r
- boolean circularlyConsumed = false;\r
- while (noConsumerList.size() == 0 && !circularlyConsumed) {\r
- circularlyConsumed = true;\r
- for (int i = 0; i < libInstanceList.length; ++i) {\r
- ModuleIdentification libInstance = libInstanceList[i];\r
- if (!libInstance.hasConstructor()) {\r
- continue;\r
- }\r
-\r
- HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);\r
- if (consumedBy == null || consumedBy.size() == 0) {\r
- continue;\r
- }\r
-\r
- ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
- for (int j = 0; j < consumedByList.length; ++j) {\r
- ModuleIdentification consumer = consumedByList[j];\r
- if (consumer.hasConstructor()) {\r
- continue;\r
- }\r
-\r
- //\r
- // if there's no constructor in the library instance's consumer,\r
- // remove it from the consumer list\r
- //\r
- consumedBy.remove(consumer);\r
- circularlyConsumed = false;\r
- if (consumedBy.size() == 0) {\r
- noConsumerList.addLast(libInstance);\r
- break;\r
- }\r
- }\r
-\r
- if (noConsumerList.size() > 0) {\r
- break;\r
- }\r
- }\r
-\r
- if (noConsumerList.size() == 0 && !circularlyConsumed) {\r
- break;\r
- }\r
- }\r
- }\r
-\r
- //\r
- // Append the remaining library instance to the end of sorted list\r
- //\r
- boolean HasError = false;\r
- for (int i = 0; i < libInstanceList.length; ++i) {\r
- HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstanceList[i]);\r
- if (consumedBy != null && consumedBy.size() > 0 && libInstanceList[i].hasConstructor()) {\r
- EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()\r
- + " with constructor has a circular dependency!");\r
- ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
- for (int j = 0; j < consumedByList.length; ++j) {\r
- EdkLog.log(EdkLog.EDK_ERROR, " consumed by " + consumedByList[j].getName());\r
- }\r
- HasError = true;\r
- }\r
-\r
- if (!orderList.contains(libInstanceList[i])) {\r
- orderList.add(libInstanceList[i]);\r
- }\r
- }\r
- if (HasError) {\r
- throw new AutoGenException("Circular dependency in library instances is found!");\r
- }\r
-\r
- return orderList;\r
- }\r
-}\r