[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
                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
        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
	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
	21	import java.util.Iterator;\r
	22	import java.util.LinkedList;\r
	23	import java.util.List;\r
	24	import java.util.Map;\r
	25	import java.util.Stack;\r
	26	import java.util.HashSet;\r
	27	\r
	28	import org.apache.xmlbeans.XmlObject;\r
	29	import org.tianocore.build.exception.AutoGenException;\r
	30	import org.tianocore.build.global.GlobalData;\r
	31	import org.tianocore.build.global.SurfaceAreaQuery;\r
	32	import org.tianocore.build.id.ModuleIdentification;\r
	33	import org.tianocore.common.exception.EdkException;\r
	34	import org.tianocore.common.logger.EdkLog;\r
	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
	43	private Map<String, ModuleIdentification> libClassProducer = new HashMap<String, ModuleIdentification>();\r
	44	\r
	45	///\r
	46	/// The map of library instance and its consumed Library Classes.\r
	47	///\r
	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
	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
	64	private ModuleIdentification[] libInstanceList = null;\r
	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
	74	AutogenLibOrder(ModuleIdentification[] libraryList, String arch) throws EdkException {\r
	75	ModuleIdentification libInstance;\r
	76	String[] libClassDeclList = null;\r
	77	String[] libClassConsmList = null;\r
	78	\r
	79	libInstanceList = libraryList;\r
	80	for (int i = 0; i < libraryList.length; i++) {\r
	81	libInstance = libraryList[i];\r
	82	//\r
	83	// Fetch the constructor & destructor.\r
	84	//\r
	85	Map<String, XmlObject> libDoc = GlobalData.getDoc(libInstance, arch);\r
	86	SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc);\r
	87	libInstance.setConstructor(saq.getLibConstructorName());\r
	88	libInstance.setDestructor(saq.getLibDestructorName());\r
	89	\r
	90	//\r
	91	// Create library class consume database.\r
	92	//\r
	93	libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch);\r
	94	if (libClassConsmList != null) {\r
	95	if (this.libInstanceConsumes.containsKey(libInstance)) {\r
	96	throw new AutoGenException(\r
	97	libraryList[i].getName()\r
	98	+ "-- this library instance already exists, please check the library instance list!");\r
	99	} else {\r
	100	this.libInstanceConsumes.put(libInstance, libClassConsmList);\r
	101	}\r
	102	}\r
	103	\r
	104	//\r
	105	// Create library class implementer database\r
	106	//\r
	107	libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch);\r
	108	if (libClassDeclList != null) {\r
	109	this.libInstanceProduces.put(libInstance, libClassDeclList);\r
	110	for (int j = 0; j < libClassDeclList.length; j++) {\r
	111	if (this.libClassProducer.containsKey(libClassDeclList[j])) {\r
	112	EdkLog.log(EdkLog.EDK_ERROR,libClassDeclList[j]\r
	113	+ " class is already implemented by "\r
	114	+ this.libClassProducer.get(libClassDeclList[j]));\r
	115	throw new AutoGenException("Library Class: " + libClassDeclList\r
	116	+ " already has a library instance!");\r
	117	} else {\r
	118	this.libClassProducer.put(libClassDeclList[j], libInstance);\r
	119	}\r
	120	}\r
	121	}\r
	122	}\r
	123	\r
	124	//\r
	125	// Create a consumed-by database\r
	126	//\r
	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
	139	}\r
	140	}\r
	141	}\r
	142	}\r
	143	}\r
	144	\r
	145	/**\r
	146	orderLibInstance\r
	147	\r
	148	This function reorder the library instance according the library class\r
	149	dependency, using DAG anaylysis algothim\r
	150	\r
	151	@return List which content the ordered library instance.\r
	152	**/\r
	153	List<ModuleIdentification> orderLibInstance() throws EdkException {\r
	154	LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();\r
	155	LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();\r
	156	\r
	157	//\r
	158	// First, add the library instance without consumers to the Q\r
	159	//\r
	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
	163	}\r
	164	}\r
	165	\r
	166	while (noConsumerList.size() > 0) {\r
	167	ModuleIdentification n = noConsumerList.poll();\r
	168	orderList.addFirst(n);\r
	169	\r
	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
	175	}\r
	176	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);\r
	177	if (consumedBy.size() == 0) {\r
	178	continue;\r
	179	}\r
	180	\r
	181	consumedBy.remove(n);\r
	182	if (consumedBy.size() == 0) {\r
	183	noConsumerList.addLast(m);\r
	184	}\r
	185	}\r
	186	\r
	187	boolean circularlyConsumed = false;\r
	188	while (noConsumerList.size() == 0 && !circularlyConsumed) {\r
	189	circularlyConsumed = true;\r
	190	for (int i = 0; i < libInstanceList.length; ++i) {\r
	191	ModuleIdentification libInstance = libInstanceList[i];\r
	192	if (!libInstance.hasConstructor()) {\r
	193	continue;\r
	194	}\r
	195	\r
	196	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);\r
	197	if (consumedBy.size() == 0) {\r
	198	continue;\r
	199	}\r
	200	\r
	201	ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
	202	for (int j = 0; j < consumedByList.length; ++j) {\r
	203	ModuleIdentification consumer = consumedByList[j];\r
	204	if (consumer.hasConstructor()) {\r
	205	continue;\r
	206	}\r
	207	\r
	208	//\r
	209	// if there's no constructor in the library instance's consumer,\r
	210	// remove it from the consumer list\r
	211	//\r
	212	consumedBy.remove(consumer);\r
	213	circularlyConsumed = false;\r
	214	if (consumedBy.size() == 0) {\r
	215	noConsumerList.addLast(libInstance);\r
	216	break;\r
	217	}\r
	218	}\r
	219	\r
	220	if (noConsumerList.size() > 0) {\r
	221	break;\r
	222	}\r
	223	}\r
	224	\r
	225	if (noConsumerList.size() == 0 && !circularlyConsumed) {\r
	226	break;\r
	227	}\r
	228	}\r
	229	}\r
	230	\r
	231	//\r
	232	// Append the remaining library instance to the end of sorted list\r
	233	//\r
	234	for (int i = 0; i < libInstanceList.length; ++i) {\r
	235	if (libInstanceConsumedBy.get(libInstanceList[i]).size() > 0 && libInstanceList[i].hasConstructor()) {\r
	236	EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()\r
	237	+ " with constructor has a circular dependency!");\r
	238	throw new AutoGenException("Circular dependency in library instances is found!");\r
	239	}\r
	240	\r
	241	if (!orderList.contains(libInstanceList[i])) {\r
	242	orderList.add(libInstanceList[i]);\r
	243	}\r
	244	}\r
	245	return orderList;\r
	246	}\r
	247	}\r