[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);\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);\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 (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
                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
                        // 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
        }\r
\r
        //\r
        // Append the remaining library instance to the end of sorted list\r
        // \r
        for (int i = 0; i < libInstanceList.length; ++i) {\r
            if (libInstanceConsumedBy.get(libInstanceList[i]).size() > 0 && libInstanceList[i].hasConstructor()) {\r
                EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()\r
                           + " with constructor has a circular dependency!");\r
                throw new AutoGenException("Circular dependency in library instances is found!");\r
            }\r
\r
            if (!orderList.contains(libInstanceList[i])) {\r
                orderList.add(libInstanceList[i]);\r
            }\r
        }\r
        return orderList;\r
    }\r
}\r
Commit	Line	Data
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
	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
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
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
a29c47e0	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
878ddf1f	89	\r
878ddf1f	90	//\r
23849470	91	// Create library class consume database.\r
878ddf1f	92	//\r
83fba802	93	libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch);\r
878ddf1f	94	if (libClassConsmList != null) {\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
83fba802	107	libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch);\r
878ddf1f	108	if (libClassDeclList != null) {\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
	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
	135	\r
	136	for (int l = 0; l < consumedClassList.length; ++l) {\r
	137	if (consumedClassList[l].equals(className)) {\r
	138	libInstanceConsumedBy.get(libInstance).add(consumer);\r
878ddf1f	139	}\r
	140	}\r
	141	}\r
878ddf1f	142	}\r
878ddf1f	143	}\r
	144	\r
	145	/**\r
	146	orderLibInstance\r
bc33b23d	147	\r
878ddf1f	148	This function reorder the library instance according the library class \r
23849470	149	dependency, using DAG anaylysis algothim\r
bc33b23d	150	\r
878ddf1f	151	@return List which content the ordered library instance.\r
878ddf1f	152	**/\r
bc33b23d	153	List<ModuleIdentification> orderLibInstance() throws EdkException {\r
3dc87a3e	154	LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();\r
bc33b23d	155	LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();\r
bc33b23d	156	\r
23849470	157	//\r
	158	// First, add the library instance without consumers to the Q\r
	159	// \r
bc33b23d	160	for (int i = 0; i < libInstanceList.length; ++i) {\r
	161	if (libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) {\r
	162	noConsumerList.add(libInstanceList[i]);\r
3dc87a3e	163	}\r
3dc87a3e	164	}\r
3dc87a3e	165	\r
bc33b23d	166	while (noConsumerList.size() > 0) {\r
	167	ModuleIdentification n = noConsumerList.poll();\r
	168	orderList.addFirst(n);\r
3dc87a3e	169	\r
bc33b23d	170	String[] consumedClassList = libInstanceConsumes.get(n);\r
	171	for (int i = 0; i < consumedClassList.length; ++i) {\r
	172	ModuleIdentification m = libClassProducer.get(consumedClassList[i]);\r
	173	if (m == null) {\r
	174	continue;\r
3dc87a3e	175	}\r
bc33b23d	176	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);\r
	177	consumedBy.remove(n);\r
	178	if (consumedBy.size() == 0) {\r
	179	noConsumerList.addLast(m);\r
3dc87a3e	180	}\r
3dc87a3e	181	}\r
3dc87a3e	182	\r
bc33b23d	183	boolean circularlyConsumed = false;\r
	184	while (noConsumerList.size() == 0 && !circularlyConsumed) {\r
	185	circularlyConsumed = true;\r
	186	for (int i = 0; i < libInstanceList.length; ++i) {\r
	187	ModuleIdentification libInstance = libInstanceList[i];\r
	188	if (!libInstance.hasConstructor()) {\r
	189	continue;\r
	190	}\r
878ddf1f	191	\r
bc33b23d	192	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);\r
	193	if (consumedBy.size() == 0) {\r
	194	continue;\r
	195	}\r
	196	\r
	197	ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
	198	for (int j = 0; j < consumedByList.length; ++j) {\r
	199	ModuleIdentification consumer = consumedByList[j];\r
	200	if (consumer.hasConstructor()) {\r
	201	continue;\r
	202	}\r
	203	//\r
	204	// if there's no constructor in the library instance's consumer, \r
	205	// remove it from the consumer list\r
	206	// \r
	207	consumedBy.remove(consumer);\r
	208	circularlyConsumed = false;\r
	209	if (consumedBy.size() == 0) {\r
	210	noConsumerList.addLast(libInstance);\r
	211	break;\r
	212	}\r
	213	}\r
	214	\r
	215	if (noConsumerList.size() > 0) {\r
	216	break;\r
	217	}\r
878ddf1f	218	}\r
	219	}\r
	220	}\r
878ddf1f	221	\r
23849470	222	//\r
	223	// Append the remaining library instance to the end of sorted list\r
	224	// \r
bc33b23d	225	for (int i = 0; i < libInstanceList.length; ++i) {\r
d919bb8c	226	if (libInstanceConsumedBy.get(libInstanceList[i]).size() > 0 && libInstanceList[i].hasConstructor()) {\r
	227	EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()\r
	228	+ " with constructor has a circular dependency!");\r
affa5a12	229	throw new AutoGenException("Circular dependency in library instances is found!");\r
d919bb8c	230	}\r
d919bb8c	231	\r
bc33b23d	232	if (!orderList.contains(libInstanceList[i])) {\r
affa5a12	233	orderList.add(libInstanceList[i]);\r
bc33b23d	234	}\r
	235	}\r
	236	return orderList;\r
a29c47e0	237	}\r
a29c47e0	238	}\r