[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 (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
        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
878ddf1f	1	/**@file\r
	2	AutogenLibOrder class.\r
	3	\r
e360ea4d	4	This class is to reorder library instance sequence according to library\r
878ddf1f	5	dependence.\r
e360ea4d	6	\r
878ddf1f	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
e360ea4d	12	\r
878ddf1f	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
e360ea4d	65	\r
878ddf1f	66	/**\r
878ddf1f	67	Constructor function\r
e360ea4d	68	\r
878ddf1f	69	This function mainly initialize some member variable.\r
e360ea4d	70	\r
878ddf1f	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
e360ea4d	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
e360ea4d	89	\r
878ddf1f	90	//\r
23849470	91	// Create library class consume database.\r
878ddf1f	92	//\r
700279a9	93	libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch, null);\r
9d3d149f	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
700279a9	107	libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch, null);\r
9d3d149f	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
e360ea4d	125	// Create a consumed-by database\r
e360ea4d	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
e360ea4d	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
23849470	158	// First, add the library instance without consumers to the Q\r
e360ea4d	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
e360ea4d	177	if (consumedBy.size() == 0) {\r
	178	continue;\r
	179	}\r
	180	\r
bc33b23d	181	consumedBy.remove(n);\r
	182	if (consumedBy.size() == 0) {\r
	183	noConsumerList.addLast(m);\r
3dc87a3e	184	}\r
3dc87a3e	185	}\r
3dc87a3e	186	\r
bc33b23d	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
878ddf1f	195	\r
bc33b23d	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
e360ea4d	207	\r
bc33b23d	208	//\r
e360ea4d	209	// if there's no constructor in the library instance's consumer,\r
bc33b23d	210	// remove it from the consumer list\r
e360ea4d	211	//\r
bc33b23d	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
878ddf1f	223	}\r
e360ea4d	224	\r
	225	if (noConsumerList.size() == 0 && !circularlyConsumed) {\r
	226	break;\r
	227	}\r
878ddf1f	228	}\r
878ddf1f	229	}\r
878ddf1f	230	\r
23849470	231	//\r
23849470	232	// Append the remaining library instance to the end of sorted list\r
e360ea4d	233	//\r
700279a9	234	boolean HasError = false;\r
bc33b23d	235	for (int i = 0; i < libInstanceList.length; ++i) {\r
700279a9	236	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstanceList[i]);\r
b991a451	237	if (consumedBy.size() > 0 && libInstanceList[i].hasConstructor()) {\r
d919bb8c	238	EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()\r
d919bb8c	239	+ " with constructor has a circular dependency!");\r
700279a9	240	ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
	241	for (int j = 0; j < consumedByList.length; ++j) {\r
	242	EdkLog.log(EdkLog.EDK_ERROR, " consumed by " + consumedByList[j].getName());\r
	243	}\r
	244	HasError = true;\r
d919bb8c	245	}\r
d919bb8c	246	\r
bc33b23d	247	if (!orderList.contains(libInstanceList[i])) {\r
affa5a12	248	orderList.add(libInstanceList[i]);\r
bc33b23d	249	}\r
bc33b23d	250	}\r
700279a9	251	if (HasError) {\r
	252	throw new AutoGenException("Circular dependency in library instances is found!");\r
	253	}\r
b991a451	254	\r
bc33b23d	255	return orderList;\r
a29c47e0	256	}\r
a29c47e0	257	}\r