[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 != 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, null);\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 (libInstanceList[i] == null) {\r
                continue;\r
            }\r
            \r
            if (libInstanceConsumedBy.get(libInstanceList[i]) == null ||  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 == null || 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 == null || 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 != null && 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 != 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, null);\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 (libInstanceList[i] == null) {\r
	162	continue;\r
	163	}\r
	164	\r
	165	if (libInstanceConsumedBy.get(libInstanceList[i]) == null \|\| libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) {\r
	166	noConsumerList.add(libInstanceList[i]);\r
	167	}\r
	168	}\r
	169	\r
	170	while (noConsumerList.size() > 0) {\r
	171	ModuleIdentification n = noConsumerList.poll();\r
	172	orderList.addFirst(n);\r
	173	\r
	174	String[] consumedClassList = libInstanceConsumes.get(n);\r
	175	for (int i = 0; i < consumedClassList.length; ++i) {\r
	176	ModuleIdentification m = libClassProducer.get(consumedClassList[i]);\r
	177	if (m == null) {\r
	178	continue;\r
	179	}\r
	180	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);\r
	181	if (consumedBy == null \|\| consumedBy.size() == 0) {\r
	182	continue;\r
	183	}\r
	184	\r
	185	consumedBy.remove(n);\r
	186	if (consumedBy.size() == 0) {\r
	187	noConsumerList.addLast(m);\r
	188	}\r
	189	}\r
	190	\r
	191	boolean circularlyConsumed = false;\r
	192	while (noConsumerList.size() == 0 && !circularlyConsumed) {\r
	193	circularlyConsumed = true;\r
	194	for (int i = 0; i < libInstanceList.length; ++i) {\r
	195	ModuleIdentification libInstance = libInstanceList[i];\r
	196	if (!libInstance.hasConstructor()) {\r
	197	continue;\r
	198	}\r
	199	\r
	200	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);\r
	201	if (consumedBy == null \|\| consumedBy.size() == 0) {\r
	202	continue;\r
	203	}\r
	204	\r
	205	ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
	206	for (int j = 0; j < consumedByList.length; ++j) {\r
	207	ModuleIdentification consumer = consumedByList[j];\r
	208	if (consumer.hasConstructor()) {\r
	209	continue;\r
	210	}\r
	211	\r
	212	//\r
	213	// if there's no constructor in the library instance's consumer,\r
	214	// remove it from the consumer list\r
	215	//\r
	216	consumedBy.remove(consumer);\r
	217	circularlyConsumed = false;\r
	218	if (consumedBy.size() == 0) {\r
	219	noConsumerList.addLast(libInstance);\r
	220	break;\r
	221	}\r
	222	}\r
	223	\r
	224	if (noConsumerList.size() > 0) {\r
	225	break;\r
	226	}\r
	227	}\r
	228	\r
	229	if (noConsumerList.size() == 0 && !circularlyConsumed) {\r
	230	break;\r
	231	}\r
	232	}\r
	233	}\r
	234	\r
	235	//\r
	236	// Append the remaining library instance to the end of sorted list\r
	237	//\r
	238	boolean HasError = false;\r
	239	for (int i = 0; i < libInstanceList.length; ++i) {\r
	240	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstanceList[i]);\r
	241	if (consumedBy != null && consumedBy.size() > 0 && libInstanceList[i].hasConstructor()) {\r
	242	EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()\r
	243	+ " with constructor has a circular dependency!");\r
	244	ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
	245	for (int j = 0; j < consumedByList.length; ++j) {\r
	246	EdkLog.log(EdkLog.EDK_ERROR, " consumed by " + consumedByList[j].getName());\r
	247	}\r
	248	HasError = true;\r
	249	}\r
	250	\r
	251	if (!orderList.contains(libInstanceList[i])) {\r
	252	orderList.add(libInstanceList[i]);\r
	253	}\r
	254	}\r
	255	if (HasError) {\r
	256	throw new AutoGenException("Circular dependency in library instances is found!");\r
	257	}\r
	258	\r
	259	return orderList;\r
	260	}\r
	261	}\r