[mirror_edk2.git] / Tools / Java / Source / GenBuild / org / tianocore / build / autogen / AutogenLibOrder.java

/**@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.length > 0) {\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.length > 0) {\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
                if (consumedClassList == null) {\r
                    continue;\r
                }\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 (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
            if (consumedClassList == null) {\r
                continue;\r
            }\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.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.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.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
Commit	Line	Data
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
	17	package org.tianocore.build.autogen;\r
	18	\r
	19	import java.util.ArrayList;\r
	20	import java.util.HashMap;\r
3dc87a3e	21	import java.util.Iterator;\r
3dc87a3e	22	import java.util.LinkedList;\r
878ddf1f	23	import java.util.List;\r
878ddf1f	24	import java.util.Map;\r
3dc87a3e	25	import java.util.Stack;\r
3dc87a3e	26	import java.util.HashSet;\r
a29c47e0	27	\r
878ddf1f	28	import org.apache.xmlbeans.XmlObject;\r
61528a1b	29	import org.tianocore.build.exception.AutoGenException;\r
878ddf1f	30	import org.tianocore.build.global.GlobalData;\r
878ddf1f	31	import org.tianocore.build.global.SurfaceAreaQuery;\r
a29c47e0	32	import org.tianocore.build.id.ModuleIdentification;\r
61528a1b	33	import org.tianocore.common.exception.EdkException;\r
192a42b4	34	import 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
	39	public 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
878ddf1f	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
878ddf1f	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
a29c47e0	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
bc33b23d	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
700279a9	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
700279a9	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
bc33b23d	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
e360ea4d	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
878ddf1f	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
bc33b23d	159	\r
23849470	160	//\r
23849470	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
3dc87a3e	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
3dc87a3e	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
878ddf1f	235	}\r
878ddf1f	236	\r
23849470	237	//\r
23849470	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
d919bb8c	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
d919bb8c	252	\r
bc33b23d	253	if (!orderList.contains(libInstanceList[i])) {\r
affa5a12	254	orderList.add(libInstanceList[i]);\r
bc33b23d	255	}\r
bc33b23d	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
a29c47e0	263	}\r