Fixed EDKT493. Added support to "SupModuleList" for checking if a library instance...
[mirror_edk2.git] / Tools / Java / Source / GenBuild / org / tianocore / build / autogen / AutogenLibOrder.java
CommitLineData
878ddf1f 1/**@file\r
2 AutogenLibOrder class.\r
3\r
e360ea4d 4 This class is to reorder library instance sequence according to library\r
878ddf1f 5 dependence.\r
e360ea4d 6\r
878ddf1f 7 Copyright (c) 2006, Intel Corporation\r
8 All rights reserved. This program and the accompanying materials\r
9 are licensed and made available under the terms and conditions of the BSD License\r
10 which accompanies this distribution. The full text of the license may be found at\r
11 http://opensource.org/licenses/bsd-license.php\r
e360ea4d 12\r
878ddf1f 13 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
14 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
15\r
16 **/\r
17package org.tianocore.build.autogen;\r
18\r
19import java.util.ArrayList;\r
20import java.util.HashMap;\r
3dc87a3e 21import java.util.Iterator;\r
22import java.util.LinkedList;\r
878ddf1f 23import java.util.List;\r
24import java.util.Map;\r
3dc87a3e 25import java.util.Stack;\r
26import java.util.HashSet;\r
a29c47e0 27\r
878ddf1f 28import org.apache.xmlbeans.XmlObject;\r
61528a1b 29import org.tianocore.build.exception.AutoGenException;\r
878ddf1f 30import org.tianocore.build.global.GlobalData;\r
31import org.tianocore.build.global.SurfaceAreaQuery;\r
a29c47e0 32import org.tianocore.build.id.ModuleIdentification;\r
61528a1b 33import org.tianocore.common.exception.EdkException;\r
192a42b4 34import org.tianocore.common.logger.EdkLog;\r
878ddf1f 35/**\r
36 This class This class is to reorder library instance sequence according to\r
37 library dependence.\r
38**/\r
39public class AutogenLibOrder {\r
40 ///\r
41 /// The map of library class and its library instance.\r
42 ///\r
bc33b23d 43 private Map<String, ModuleIdentification> libClassProducer = new HashMap<String, ModuleIdentification>();\r
878ddf1f 44\r
45 ///\r
bc33b23d 46 /// The map of library instance and its consumed Library Classes.\r
878ddf1f 47 ///\r
bc33b23d 48 private Map<ModuleIdentification, String[]> libInstanceConsumes = new HashMap<ModuleIdentification, String[]>();\r
49\r
50 ///\r
51 /// The map of library instance and its implemeted Library Classes.\r
52 ///\r
53 private Map<ModuleIdentification, String[]> libInstanceProduces = new HashMap<ModuleIdentification, String[]>();\r
54\r
55 ///\r
56 /// The map of library instance and its consumers.\r
57 ///\r
58 private Map<ModuleIdentification, HashSet<ModuleIdentification>> libInstanceConsumedBy = new HashMap<ModuleIdentification, HashSet<ModuleIdentification>>();\r
878ddf1f 59\r
60 ///\r
61 /// List of library instance. It is String[3] list, String[0] is libraryName,\r
62 /// String[1] is libraryConstructor name, String[2] is libDestructor name.\r
63 ///\r
bc33b23d 64 private ModuleIdentification[] libInstanceList = null;\r
e360ea4d 65\r
878ddf1f 66 /**\r
67 Constructor function\r
e360ea4d 68\r
878ddf1f 69 This function mainly initialize some member variable.\r
e360ea4d 70\r
878ddf1f 71 @param libraryList List of the library instance.\r
72 @throws Exception\r
73 **/\r
61528a1b 74 AutogenLibOrder(ModuleIdentification[] libraryList, String arch) throws EdkException {\r
bc33b23d 75 ModuleIdentification libInstance;\r
a29c47e0 76 String[] libClassDeclList = null;\r
77 String[] libClassConsmList = null;\r
bc33b23d 78\r
23849470 79 libInstanceList = libraryList;\r
a29c47e0 80 for (int i = 0; i < libraryList.length; i++) {\r
bc33b23d 81 libInstance = libraryList[i];\r
878ddf1f 82 //\r
23849470 83 // Fetch the constructor & destructor.\r
e360ea4d 84 //\r
bc33b23d 85 Map<String, XmlObject> libDoc = GlobalData.getDoc(libInstance, arch);\r
83fba802 86 SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc);\r
bc33b23d 87 libInstance.setConstructor(saq.getLibConstructorName());\r
88 libInstance.setDestructor(saq.getLibDestructorName());\r
e360ea4d 89\r
878ddf1f 90 //\r
23849470 91 // Create library class consume database.\r
878ddf1f 92 //\r
700279a9 93 libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch, null);\r
94 if (libClassConsmList.length > 0) {\r
bc33b23d 95 if (this.libInstanceConsumes.containsKey(libInstance)) {\r
61528a1b 96 throw new AutoGenException(\r
a29c47e0 97 libraryList[i].getName()\r
61528a1b 98 + "-- this library instance already exists, please check the library instance list!");\r
878ddf1f 99 } else {\r
bc33b23d 100 this.libInstanceConsumes.put(libInstance, libClassConsmList);\r
878ddf1f 101 }\r
102 }\r
103\r
104 //\r
23849470 105 // Create library class implementer database\r
878ddf1f 106 //\r
700279a9 107 libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch, null);\r
108 if (libClassDeclList.length > 0) {\r
bc33b23d 109 this.libInstanceProduces.put(libInstance, libClassDeclList);\r
878ddf1f 110 for (int j = 0; j < libClassDeclList.length; j++) {\r
bc33b23d 111 if (this.libClassProducer.containsKey(libClassDeclList[j])) {\r
192a42b4 112 EdkLog.log(EdkLog.EDK_ERROR,libClassDeclList[j]\r
bc33b23d 113 + " class is already implemented by "\r
114 + this.libClassProducer.get(libClassDeclList[j]));\r
61528a1b 115 throw new AutoGenException("Library Class: " + libClassDeclList\r
391dbbb1 116 + " already has a library instance!");\r
878ddf1f 117 } else {\r
bc33b23d 118 this.libClassProducer.put(libClassDeclList[j], libInstance);\r
119 }\r
120 }\r
121 }\r
122 }\r
123\r
23849470 124 //\r
e360ea4d 125 // Create a consumed-by database\r
126 //\r
bc33b23d 127 for (Iterator it = libClassProducer.keySet().iterator(); it.hasNext();) {\r
128 String className = (String)it.next();\r
129 libInstance = libClassProducer.get(className);\r
130 libInstanceConsumedBy.put(libInstance, new HashSet<ModuleIdentification>());\r
131\r
132 for (int k = 0; k < libraryList.length; ++k) {\r
133 ModuleIdentification consumer = libraryList[k];\r
134 String[] consumedClassList = libInstanceConsumes.get(consumer);\r
700279a9 135 if (consumedClassList == null) {\r
136 continue;\r
137 }\r
bc33b23d 138\r
139 for (int l = 0; l < consumedClassList.length; ++l) {\r
140 if (consumedClassList[l].equals(className)) {\r
141 libInstanceConsumedBy.get(libInstance).add(consumer);\r
878ddf1f 142 }\r
143 }\r
144 }\r
878ddf1f 145 }\r
878ddf1f 146 }\r
147\r
148 /**\r
149 orderLibInstance\r
bc33b23d 150\r
e360ea4d 151 This function reorder the library instance according the library class\r
23849470 152 dependency, using DAG anaylysis algothim\r
bc33b23d 153\r
878ddf1f 154 @return List which content the ordered library instance.\r
155 **/\r
bc33b23d 156 List<ModuleIdentification> orderLibInstance() throws EdkException {\r
3dc87a3e 157 LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();\r
bc33b23d 158 LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();\r
159\r
23849470 160 //\r
161 // First, add the library instance without consumers to the Q\r
e360ea4d 162 //\r
bc33b23d 163 for (int i = 0; i < libInstanceList.length; ++i) {\r
164 if (libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) {\r
165 noConsumerList.add(libInstanceList[i]);\r
3dc87a3e 166 }\r
3dc87a3e 167 }\r
168\r
bc33b23d 169 while (noConsumerList.size() > 0) {\r
170 ModuleIdentification n = noConsumerList.poll();\r
171 orderList.addFirst(n);\r
3dc87a3e 172\r
bc33b23d 173 String[] consumedClassList = libInstanceConsumes.get(n);\r
700279a9 174 if (consumedClassList == null) {\r
175 continue;\r
176 }\r
bc33b23d 177 for (int i = 0; i < consumedClassList.length; ++i) {\r
178 ModuleIdentification m = libClassProducer.get(consumedClassList[i]);\r
179 if (m == null) {\r
180 continue;\r
3dc87a3e 181 }\r
bc33b23d 182 HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);\r
e360ea4d 183 if (consumedBy.size() == 0) {\r
184 continue;\r
185 }\r
186\r
bc33b23d 187 consumedBy.remove(n);\r
188 if (consumedBy.size() == 0) {\r
189 noConsumerList.addLast(m);\r
3dc87a3e 190 }\r
191 }\r
3dc87a3e 192\r
bc33b23d 193 boolean circularlyConsumed = false;\r
194 while (noConsumerList.size() == 0 && !circularlyConsumed) {\r
195 circularlyConsumed = true;\r
196 for (int i = 0; i < libInstanceList.length; ++i) {\r
197 ModuleIdentification libInstance = libInstanceList[i];\r
198 if (!libInstance.hasConstructor()) {\r
199 continue;\r
200 }\r
878ddf1f 201\r
bc33b23d 202 HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);\r
203 if (consumedBy.size() == 0) {\r
204 continue;\r
205 }\r
206\r
207 ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
208 for (int j = 0; j < consumedByList.length; ++j) {\r
209 ModuleIdentification consumer = consumedByList[j];\r
210 if (consumer.hasConstructor()) {\r
211 continue;\r
212 }\r
e360ea4d 213\r
bc33b23d 214 //\r
e360ea4d 215 // if there's no constructor in the library instance's consumer,\r
bc33b23d 216 // remove it from the consumer list\r
e360ea4d 217 //\r
bc33b23d 218 consumedBy.remove(consumer);\r
219 circularlyConsumed = false;\r
220 if (consumedBy.size() == 0) {\r
221 noConsumerList.addLast(libInstance);\r
222 break;\r
223 }\r
224 }\r
225\r
226 if (noConsumerList.size() > 0) {\r
227 break;\r
228 }\r
878ddf1f 229 }\r
e360ea4d 230\r
231 if (noConsumerList.size() == 0 && !circularlyConsumed) {\r
232 break;\r
233 }\r
878ddf1f 234 }\r
235 }\r
878ddf1f 236\r
23849470 237 //\r
238 // Append the remaining library instance to the end of sorted list\r
e360ea4d 239 //\r
700279a9 240 boolean HasError = false;\r
bc33b23d 241 for (int i = 0; i < libInstanceList.length; ++i) {\r
700279a9 242 HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstanceList[i]);\r
b991a451 243 if (consumedBy.size() > 0 && libInstanceList[i].hasConstructor()) {\r
d919bb8c 244 EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()\r
245 + " with constructor has a circular dependency!");\r
700279a9 246 ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
247 for (int j = 0; j < consumedByList.length; ++j) {\r
248 EdkLog.log(EdkLog.EDK_ERROR, " consumed by " + consumedByList[j].getName());\r
249 }\r
250 HasError = true;\r
d919bb8c 251 }\r
252\r
bc33b23d 253 if (!orderList.contains(libInstanceList[i])) {\r
affa5a12 254 orderList.add(libInstanceList[i]);\r
bc33b23d 255 }\r
256 }\r
700279a9 257 if (HasError) {\r
258 throw new AutoGenException("Circular dependency in library instances is found!");\r
259 }\r
b991a451 260\r
bc33b23d 261 return orderList;\r
a29c47e0 262 }\r
263}\r