[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
	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, null);\r
	94	if (libClassConsmList.length > 0) {\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, null);\r
	108	if (libClassDeclList.length > 0) {\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	if (consumedClassList == null) {\r
	136	continue;\r
	137	}\r
	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
	142	}\r
	143	}\r
	144	}\r
	145	}\r
	146	}\r
	147	\r
	148	/**\r
	149	orderLibInstance\r
	150	\r
	151	This function reorder the library instance according the library class\r
	152	dependency, using DAG anaylysis algothim\r
	153	\r
	154	@return List which content the ordered library instance.\r
	155	**/\r
	156	List<ModuleIdentification> orderLibInstance() throws EdkException {\r
	157	LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();\r
	158	LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();\r
	159	\r
	160	//\r
	161	// First, add the library instance without consumers to the Q\r
	162	//\r
	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
	166	}\r
	167	}\r
	168	\r
	169	while (noConsumerList.size() > 0) {\r
	170	ModuleIdentification n = noConsumerList.poll();\r
	171	orderList.addFirst(n);\r
	172	\r
	173	String[] consumedClassList = libInstanceConsumes.get(n);\r
	174	if (consumedClassList == null) {\r
	175	continue;\r
	176	}\r
	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
	181	}\r
	182	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);\r
	183	if (consumedBy.size() == 0) {\r
	184	continue;\r
	185	}\r
	186	\r
	187	consumedBy.remove(n);\r
	188	if (consumedBy.size() == 0) {\r
	189	noConsumerList.addLast(m);\r
	190	}\r
	191	}\r
	192	\r
	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
	201	\r
	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
	213	\r
	214	//\r
	215	// if there's no constructor in the library instance's consumer,\r
	216	// remove it from the consumer list\r
	217	//\r
	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
	229	}\r
	230	\r
	231	if (noConsumerList.size() == 0 && !circularlyConsumed) {\r
	232	break;\r
	233	}\r
	234	}\r
	235	}\r
	236	\r
	237	//\r
	238	// Append the remaining library instance to the end of sorted list\r
	239	//\r
	240	boolean HasError = false;\r
	241	for (int i = 0; i < libInstanceList.length; ++i) {\r
	242	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstanceList[i]);\r
	243	if (consumedBy.size() > 0 && libInstanceList[i].hasConstructor()) {\r
	244	EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()\r
	245	+ " with constructor has a circular dependency!");\r
	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
	251	}\r
	252	\r
	253	if (!orderList.contains(libInstanceList[i])) {\r
	254	orderList.add(libInstanceList[i]);\r
	255	}\r
	256	}\r
	257	if (HasError) {\r
	258	throw new AutoGenException("Circular dependency in library instances is found!");\r
	259	}\r
	260	\r
	261	return orderList;\r
	262	}\r
	263	}\r