[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
	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	consumedBy.remove(n);\r
	178	if (consumedBy.size() == 0) {\r
	179	noConsumerList.addLast(m);\r
	180	}\r
	181	}\r
	182	\r
	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
	191	\r
	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
	218	}\r
	219	}\r
	220	}\r
	221	\r
	222	//\r
	223	// Append the remaining library instance to the end of sorted list\r
	224	// \r
	225	for (int i = 0; i < libInstanceList.length; ++i) {\r
	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
	229	throw new AutoGenException("Circular dependency in library instances is found!");\r
	230	}\r
	231	\r
	232	if (!orderList.contains(libInstanceList[i])) {\r
	233	orderList.add(libInstanceList[i]);\r
	234	}\r
	235	}\r
	236	return orderList;\r
	237	}\r
	238	}\r