X-Git-Url: https://git.proxmox.com/?a=blobdiff_plain;f=Tools%2FJava%2FSource%2FGenBuild%2Forg%2Ftianocore%2Fbuild%2Fautogen%2FAutogenLibOrder.java;h=4cf8c3caf250949c51720b9a7b2a2d46507f6a5a;hb=34dca9d54add012aee9ed2db7f7ce6fd932a0c5a;hp=9674c5de0882951bb7c66cee794d1968de60ab8c;hpb=3dc87a3e784234dbab51cb57ade43417af987167;p=mirror_edk2.git diff --git a/Tools/Java/Source/GenBuild/org/tianocore/build/autogen/AutogenLibOrder.java b/Tools/Java/Source/GenBuild/org/tianocore/build/autogen/AutogenLibOrder.java index 9674c5de08..4cf8c3caf2 100644 --- a/Tools/Java/Source/GenBuild/org/tianocore/build/autogen/AutogenLibOrder.java +++ b/Tools/Java/Source/GenBuild/org/tianocore/build/autogen/AutogenLibOrder.java @@ -40,18 +40,28 @@ public class AutogenLibOrder { /// /// The map of library class and its library instance. /// - private Map libClassMap = new HashMap(); + private Map libClassProducer = new HashMap(); /// - /// The map of library instance and its implemet libraryClass. + /// The map of library instance and its consumed Library Classes. /// - private Map libInstanceMap = new HashMap(); + private Map libInstanceConsumes = new HashMap(); + + /// + /// The map of library instance and its implemeted Library Classes. + /// + private Map libInstanceProduces = new HashMap(); + + /// + /// The map of library instance and its consumers. + /// + private Map> libInstanceConsumedBy = new HashMap>(); /// /// List of library instance. It is String[3] list, String[0] is libraryName, /// String[1] is libraryConstructor name, String[2] is libDestructor name. /// - private List libInstanceList = new ArrayList(); + private ModuleIdentification[] libInstanceList = null; /** Constructor function @@ -62,313 +72,167 @@ public class AutogenLibOrder { @throws Exception **/ AutogenLibOrder(ModuleIdentification[] libraryList, String arch) throws EdkException { - LibraryInstanceNode libInstanceNode; + ModuleIdentification libInstance; String[] libClassDeclList = null; String[] libClassConsmList = null; - + + libInstanceList = libraryList; for (int i = 0; i < libraryList.length; i++) { + libInstance = libraryList[i]; // - // Add libraryInstance in to libInstanceList. + // Fetch the constructor & destructor. // - Map libDoc = GlobalData.getDoc(libraryList[i], arch); + Map libDoc = GlobalData.getDoc(libInstance, arch); SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc); - libInstanceNode = new LibraryInstanceNode (libraryList[i],saq.getLibConstructorName(), saq.getLibDestructorName()); - libInstanceList.add(libInstanceNode); + libInstance.setConstructor(saq.getLibConstructorName()); + libInstance.setDestructor(saq.getLibDestructorName()); // - // Add library instance and consumed library class list to - // libInstanceMap. + // Create library class consume database. // libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch); if (libClassConsmList != null) { - String[] classStr = new String[libClassConsmList.length]; - for (int k = 0; k < libClassConsmList.length; k++) { - classStr[k] = libClassConsmList[k]; - } - if (this.libInstanceMap.containsKey(libraryList[i])) { + if (this.libInstanceConsumes.containsKey(libInstance)) { throw new AutoGenException( libraryList[i].getName() + "-- this library instance already exists, please check the library instance list!"); } else { - this.libInstanceMap.put(libraryList[i], classStr); + this.libInstanceConsumes.put(libInstance, libClassConsmList); } } // - // Add library class and library instance map. + // Create library class implementer database // libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch); if (libClassDeclList != null) { + this.libInstanceProduces.put(libInstance, libClassDeclList); for (int j = 0; j < libClassDeclList.length; j++) { - if (this.libClassMap.containsKey(libClassDeclList[j])) { + if (this.libClassProducer.containsKey(libClassDeclList[j])) { EdkLog.log(EdkLog.EDK_ERROR,libClassDeclList[j] - + " class is already implement by " - + this.libClassMap.get(libClassDeclList[j])); + + " class is already implemented by " + + this.libClassProducer.get(libClassDeclList[j])); throw new AutoGenException("Library Class: " + libClassDeclList + " already has a library instance!"); } else { - this.libClassMap.put(libClassDeclList[j], libraryList[i]); + this.libClassProducer.put(libClassDeclList[j], libInstance); } } } } // - // Check is the library instance list meet the require; - // - //for (int s = 0; s < this.libInstanceList.size(); s++) { - // String[] libClass = this.libInstanceMap.get(this.libInstanceList - // .get(s)); - // if (libClass != null) { - // for (int t = 0; t < libClass.length; t++) { - // if (this.libClassMap.get(libClass[t]) == null) { - // - // Note: There exist a kind of module which depend on - // library class with no instance or whose instance will - // never be linked into the module. - // For this satuation, the module has the description of - // library class in MSA file but no description of - // corresponding library instance in MBD file. There - // will be a warnig message given here after a standard - // log way has been decided. - // - // } - // } - // } - //} + // Create a consumed-by database + // + for (Iterator it = libClassProducer.keySet().iterator(); it.hasNext();) { + String className = (String)it.next(); + libInstance = libClassProducer.get(className); + libInstanceConsumedBy.put(libInstance, new HashSet()); + + for (int k = 0; k < libraryList.length; ++k) { + ModuleIdentification consumer = libraryList[k]; + String[] consumedClassList = libInstanceConsumes.get(consumer); + + for (int l = 0; l < consumedClassList.length; ++l) { + if (consumedClassList[l].equals(className)) { + libInstanceConsumedBy.get(libInstance).add(consumer); + } + } + } + } } /** orderLibInstance - + This function reorder the library instance according the library class - dependency. - + dependency, using DAG anaylysis algothim + @return List which content the ordered library instance. **/ - List orderLibInstance1() { - List orderList = new ArrayList(); - // - // Stack of node which track the library instance name ant its visiting - // flag. - // - List stackList = new ArrayList(); - int stackSize = 0; - ModuleIdentification libInstanceId = null; - if (libInstanceList.size() < 0) { - return null; - } + List orderLibInstance() throws EdkException { + LinkedList orderList = new LinkedList(); + LinkedList noConsumerList = new LinkedList(); // - // Reorder the library instance. - // - for (int i = 0; i < libInstanceList.size(); i++) { - // - // If library instance is already in the order list skip it. - // - if (isInLibInstance(orderList, libInstanceList.get(i).libId)) { - continue; - } - - Node node = new Node(libInstanceList.get(i).libId, false); - // - // Use stack to reorder library instance. - // Push node to stack. - // - stackList.add(node); - while (stackList.size() > 0) { - stackSize = stackList.size() - 1; - // - // Pop the first node in stack. If the node flag has been visited - // add this node to orderlist and remove it from stack. - // - if (stackList.get(stackSize).isVisit) { - if (!isInLibInstance(orderList, - stackList.get(stackSize).nodeId)) { - orderList.add(stackList.get(stackSize).nodeId); - stackList.remove(stackSize); - } - - } else { - // - // Get the node value and set visit flag as true. - // - stackList.get(stackList.size() - 1).isVisit = true; - String[] libClassList = this.libInstanceMap.get(stackList - .get(stackSize).nodeId); - // - // Push the node dependence library instance to the stack. - // - if (libClassList != null) { - for (int j = 0; j < libClassList.length; j++) { - libInstanceId = this.libClassMap.get(libClassList[j]); - if (libInstanceId != null - && !isInLibInstance(orderList, libInstanceId)) { - // - // If and only if the currently library instance - // is not in stack and it have constructor or - // destructor function, push this library - // instacne in stack. - // - if (!isInStackList(stackList, this.libClassMap - .get(libClassList[j])) /* && isHaveConsDestructor(libInstanceId) */) { - stackList.add(new Node(this.libClassMap - .get(libClassList[j]), false)); - } - } - } - } - } - System.out.println("################################################"); - for (int ii = 0; ii < orderList.size(); ++ii) { - System.out.println(" " + orderList.get(ii)); - } + // First, add the library instance without consumers to the Q + // + for (int i = 0; i < libInstanceList.length; ++i) { + if (libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) { + noConsumerList.add(libInstanceList[i]); } } - return orderList; - } - List orderLibInstance() { - LinkedList orderList = new LinkedList(); - for (int i = 0; i < libInstanceList.size(); ++i) { - ModuleIdentification current = libInstanceList.get(i).libId; - int insertPoint = orderList.size(); - for (int j = 0; j < orderList.size(); ++j) { - ModuleIdentification old = orderList.get(j); - //System.out.println("### old = " + old); - if (consumes(current, old)) { - insertPoint = j + 1; - } else if (consumes(old, current)) { - insertPoint = j; - break; + while (noConsumerList.size() > 0) { + ModuleIdentification n = noConsumerList.poll(); + orderList.addFirst(n); + + String[] consumedClassList = libInstanceConsumes.get(n); + for (int i = 0; i < consumedClassList.length; ++i) { + ModuleIdentification m = libClassProducer.get(consumedClassList[i]); + if (m == null) { + continue; + } + HashSet consumedBy = libInstanceConsumedBy.get(m); + consumedBy.remove(n); + if (consumedBy.size() == 0) { + noConsumerList.addLast(m); } } - orderList.add(insertPoint, current); -// System.out.println("################################################"); -// for (int ii = 0; ii < orderList.size(); ++ii) { -// System.out.println(" " + orderList.get(ii)); -// } - } - return orderList; - } + boolean circularlyConsumed = false; + while (noConsumerList.size() == 0 && !circularlyConsumed) { + circularlyConsumed = true; + for (int i = 0; i < libInstanceList.length; ++i) { + ModuleIdentification libInstance = libInstanceList[i]; + if (!libInstance.hasConstructor()) { + continue; + } - boolean consumes(ModuleIdentification lib1, ModuleIdentification lib2) { - //System.out.println("$$$ lib1 = " + lib1); - LinkedList stack = new LinkedList(); - stack.add(lib1); - int j = 0; - while (j < stack.size()) { - ModuleIdentification lib = stack.get(j++); - String[] consumedClasses = libInstanceMap.get(lib); - for (int i = 0; i < consumedClasses.length; ++i) { - ModuleIdentification consumedLib = libClassMap.get(consumedClasses[i]); - //System.out.println("$$$ class = " + consumedClasses[i]); - //System.out.println("$$$ insta = " + consumedLib); - if (consumedLib == lib2) { - //System.out.println(lib1 + "\n consumes\n" + lib2 + "\n"); - return true; - } - if (consumedLib != null && !stack.contains(consumedLib)) { - stack.offer(consumedLib); + HashSet consumedBy = libInstanceConsumedBy.get(libInstance); + if (consumedBy.size() == 0) { + continue; + } + + ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]); + for (int j = 0; j < consumedByList.length; ++j) { + ModuleIdentification consumer = consumedByList[j]; + if (consumer.hasConstructor()) { + continue; + } + // + // if there's no constructor in the library instance's consumer, + // remove it from the consumer list + // + consumedBy.remove(consumer); + circularlyConsumed = false; + if (consumedBy.size() == 0) { + noConsumerList.addLast(libInstance); + break; + } + } + + if (noConsumerList.size() > 0) { + break; + } } } } - return false; - } - /** - isInLibInstance - - This function check does the library instance already in the list. - - @param list List of the library instance. - @param instanceName Name of library instance. - @return "true" the library instance in list | - "false" the library instance is not in list. - **/ - private boolean isInLibInstance(List list, ModuleIdentification instanceId) { - for (int i = 0; i < list.size(); i++) { - - if (instanceId.equals(list.get(i))) { - return true; + // + // Append the remaining library instance to the end of sorted list + // + for (int i = 0; i < libInstanceList.length; ++i) { + if (libInstanceConsumedBy.get(libInstanceList[i]).size() > 0 && libInstanceList[i].hasConstructor()) { + EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName() + + " with constructor has a circular dependency!"); + throw new AutoGenException("Circular dependency in library instances is found!"); } - } - return false; - } - /** - isInStackList - - This function check if the node already in the stack. - - @param list Stack. - @param nodeName Name of node. - @return "true" if node have in stack | - "false" if node don't in stack. - **/ - private boolean isInStackList(List list, ModuleIdentification instanceId) { - for (int i = 0; i < list.size(); i++) { - if (instanceId.equals(list.get(i).nodeId)) { - return true; - } - } - return false; - } - - /** - isHaveConsDestructor - - This function check if the library have constructor or destructor - function. - - @param libName Name of library - @return "true" if library have constructor or desconstructor | - "false" if library don't have constructor - and desconstructor. - **/ - private boolean isHaveConsDestructor (ModuleIdentification libNode){ - for (int i = 0; i < libInstanceList.size(); i++){ - if (libInstanceList.get(i).libId.equals(libNode)){ - if (libInstanceList.get(i).constructorName != null || libInstanceList.get(i).deconstructorName != null){ - return true; - } + if (!orderList.contains(libInstanceList[i])) { + orderList.add(libInstanceList[i]); } } - return false; - } -} - -/** - Node - - This class is used as stack node. - - **/ -class Node { - ModuleIdentification nodeId; - - boolean isVisit; - - Node(ModuleIdentification nodeId, boolean isVisit) { - this.nodeId = nodeId; - this.isVisit = false; - } -} -/** - LibraryInstance Node - - This class is used to store LibrayInstance and it's deconstructor and constructor -**/ - -class LibraryInstanceNode { - ModuleIdentification libId; - String deconstructorName; - String constructorName; - - LibraryInstanceNode (ModuleIdentification libId, String deconstructor, String constructor){ - this.libId = libId; - this.deconstructorName = deconstructor; - this.constructorName = constructor; + return orderList; } }