Used the DAG algorithm given by Mike to re-implemented library constructor sorting...
[mirror_edk2.git] / Tools / Java / Source / GenBuild / org / tianocore / build / autogen / AutogenLibOrder.java
CommitLineData
878ddf1f 1/**@file\r
2 AutogenLibOrder class.\r
3\r
4 This class is to reorder library instance sequence according to library \r
5 dependence.\r
6 \r
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
12 \r
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
878ddf1f 65 \r
66 /**\r
67 Constructor function\r
68 \r
69 This function mainly initialize some member variable.\r
70 \r
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
79 libInstanceList = new ModuleIdentification[libraryList.length];\r
a29c47e0 80 for (int i = 0; i < libraryList.length; i++) {\r
bc33b23d 81 libInstance = libraryList[i];\r
82 libInstanceList[i] = libInstance;\r
878ddf1f 83 //\r
84 // Add libraryInstance in to libInstanceList.\r
a29c47e0 85 // \r
bc33b23d 86 Map<String, XmlObject> libDoc = GlobalData.getDoc(libInstance, arch);\r
83fba802 87 SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc);\r
bc33b23d 88 libInstance.setConstructor(saq.getLibConstructorName());\r
89 libInstance.setDestructor(saq.getLibDestructorName());\r
878ddf1f 90 \r
91 //\r
92 // Add library instance and consumed library class list to\r
bc33b23d 93 // libInstanceConsumes.\r
878ddf1f 94 //\r
83fba802 95 libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch);\r
878ddf1f 96 if (libClassConsmList != null) {\r
bc33b23d 97 /*\r
878ddf1f 98 String[] classStr = new String[libClassConsmList.length];\r
99 for (int k = 0; k < libClassConsmList.length; k++) {\r
a29c47e0 100 classStr[k] = libClassConsmList[k];\r
878ddf1f 101 }\r
bc33b23d 102 */\r
103 if (this.libInstanceConsumes.containsKey(libInstance)) {\r
61528a1b 104 throw new AutoGenException(\r
a29c47e0 105 libraryList[i].getName()\r
61528a1b 106 + "-- this library instance already exists, please check the library instance list!");\r
878ddf1f 107 } else {\r
bc33b23d 108 this.libInstanceConsumes.put(libInstance, libClassConsmList);\r
878ddf1f 109 }\r
110 }\r
111\r
112 //\r
113 // Add library class and library instance map.\r
114 //\r
83fba802 115 libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch);\r
878ddf1f 116 if (libClassDeclList != null) {\r
bc33b23d 117 this.libInstanceProduces.put(libInstance, libClassDeclList);\r
878ddf1f 118 for (int j = 0; j < libClassDeclList.length; j++) {\r
bc33b23d 119 if (this.libClassProducer.containsKey(libClassDeclList[j])) {\r
192a42b4 120 EdkLog.log(EdkLog.EDK_ERROR,libClassDeclList[j]\r
bc33b23d 121 + " class is already implemented by "\r
122 + this.libClassProducer.get(libClassDeclList[j]));\r
61528a1b 123 throw new AutoGenException("Library Class: " + libClassDeclList\r
391dbbb1 124 + " already has a library instance!");\r
878ddf1f 125 } else {\r
bc33b23d 126 this.libClassProducer.put(libClassDeclList[j], libInstance);\r
127 }\r
128 }\r
129 }\r
130 }\r
131\r
132 for (Iterator it = libClassProducer.keySet().iterator(); it.hasNext();) {\r
133 String className = (String)it.next();\r
134 libInstance = libClassProducer.get(className);\r
135 libInstanceConsumedBy.put(libInstance, new HashSet<ModuleIdentification>());\r
136\r
137 for (int k = 0; k < libraryList.length; ++k) {\r
138 ModuleIdentification consumer = libraryList[k];\r
139 String[] consumedClassList = libInstanceConsumes.get(consumer);\r
140\r
141 for (int l = 0; l < consumedClassList.length; ++l) {\r
142 if (consumedClassList[l].equals(className)) {\r
143 libInstanceConsumedBy.get(libInstance).add(consumer);\r
878ddf1f 144 }\r
145 }\r
146 }\r
878ddf1f 147 }\r
878ddf1f 148 }\r
149\r
150 /**\r
151 orderLibInstance\r
bc33b23d 152\r
878ddf1f 153 This function reorder the library instance according the library class \r
154 dependency.\r
bc33b23d 155\r
878ddf1f 156 @return List which content the ordered library instance.\r
157 **/\r
bc33b23d 158 List<ModuleIdentification> orderLibInstance() throws EdkException {\r
3dc87a3e 159 LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();\r
bc33b23d 160 LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();\r
161\r
162 for (int i = 0; i < libInstanceList.length; ++i) {\r
163 if (libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) {\r
164 noConsumerList.add(libInstanceList[i]);\r
3dc87a3e 165 }\r
3dc87a3e 166 }\r
167\r
bc33b23d 168 while (noConsumerList.size() > 0) {\r
169 ModuleIdentification n = noConsumerList.poll();\r
170 orderList.addFirst(n);\r
3dc87a3e 171\r
bc33b23d 172 String[] consumedClassList = libInstanceConsumes.get(n);\r
173 for (int i = 0; i < consumedClassList.length; ++i) {\r
174 ModuleIdentification m = libClassProducer.get(consumedClassList[i]);\r
175 if (m == null) {\r
176 continue;\r
3dc87a3e 177 }\r
bc33b23d 178 HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);\r
179 consumedBy.remove(n);\r
180 if (consumedBy.size() == 0) {\r
181 noConsumerList.addLast(m);\r
3dc87a3e 182 }\r
183 }\r
3dc87a3e 184\r
bc33b23d 185 boolean circularlyConsumed = false;\r
186 while (noConsumerList.size() == 0 && !circularlyConsumed) {\r
187 circularlyConsumed = true;\r
188 for (int i = 0; i < libInstanceList.length; ++i) {\r
189 ModuleIdentification libInstance = libInstanceList[i];\r
190 if (!libInstance.hasConstructor()) {\r
191 continue;\r
192 }\r
878ddf1f 193\r
bc33b23d 194 HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);\r
195 if (consumedBy.size() == 0) {\r
196 continue;\r
197 }\r
198\r
199 ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
200 for (int j = 0; j < consumedByList.length; ++j) {\r
201 ModuleIdentification consumer = consumedByList[j];\r
202 if (consumer.hasConstructor()) {\r
203 continue;\r
204 }\r
205 //\r
206 // if there's no constructor in the library instance's consumer, \r
207 // remove it from the consumer list\r
208 // \r
209 consumedBy.remove(consumer);\r
210 circularlyConsumed = false;\r
211 if (consumedBy.size() == 0) {\r
212 noConsumerList.addLast(libInstance);\r
213 break;\r
214 }\r
215 }\r
216\r
217 if (noConsumerList.size() > 0) {\r
218 break;\r
219 }\r
878ddf1f 220 }\r
221 }\r
222 }\r
878ddf1f 223\r
bc33b23d 224 for (int i = 0; i < libInstanceList.length; ++i) {\r
225 if (!orderList.contains(libInstanceList[i])) {\r
226 orderList.add(libInstanceList[i]);\r
227 }\r
228 }\r
229 return orderList;\r
a29c47e0 230 }\r
231}\r