[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 = new ModuleIdentification[libraryList.length];\r
        for (int i = 0; i < libraryList.length; i++) {\r
            libInstance = libraryList[i];\r
            libInstanceList[i] = libInstance;\r
            //\r
            // Add libraryInstance in to libInstanceList.\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
            // Add library instance and consumed library class list to\r
            // libInstanceConsumes.\r
            //\r
            libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch);\r
            if (libClassConsmList != null) {\r
                /*\r
                String[] classStr = new String[libClassConsmList.length];\r
                for (int k = 0; k < libClassConsmList.length; k++) {\r
                    classStr[k] = libClassConsmList[k];\r
                }\r
                */\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
            // Add library class and library instance map.\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
        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.\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
        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
        for (int i = 0; i < libInstanceList.length; ++i) {\r
            if (!orderList.contains(libInstanceList[i])) {\r
                orderList.add(libInstanceList[i]);\r
            }\r
        }\r
        return orderList;\r
    }\r
}\r
Commit	Line	Data
878ddf1f	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
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
878ddf1f	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
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
bc33b23d	79	libInstanceList = new ModuleIdentification[libraryList.length];\r
a29c47e0	80	for (int i = 0; i < libraryList.length; i++) {\r
bc33b23d	81	libInstance = libraryList[i];\r
bc33b23d	82	libInstanceList[i] = libInstance;\r
878ddf1f	83	//\r
878ddf1f	84	// Add libraryInstance in to libInstanceList.\r
a29c47e0	85	// \r
bc33b23d	86	Map<String, XmlObject> libDoc = GlobalData.getDoc(libInstance, arch);\r
83fba802	87	SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc);\r
bc33b23d	88	libInstance.setConstructor(saq.getLibConstructorName());\r
bc33b23d	89	libInstance.setDestructor(saq.getLibDestructorName());\r
878ddf1f	90	\r
	91	//\r
	92	// Add library instance and consumed library class list to\r
bc33b23d	93	// libInstanceConsumes.\r
878ddf1f	94	//\r
83fba802	95	libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch);\r
878ddf1f	96	if (libClassConsmList != null) {\r
bc33b23d	97	/*\r
878ddf1f	98	String[] classStr = new String[libClassConsmList.length];\r
878ddf1f	99	for (int k = 0; k < libClassConsmList.length; k++) {\r
a29c47e0	100	classStr[k] = libClassConsmList[k];\r
878ddf1f	101	}\r
bc33b23d	102	*/\r
bc33b23d	103	if (this.libInstanceConsumes.containsKey(libInstance)) {\r
61528a1b	104	throw new AutoGenException(\r
a29c47e0	105	libraryList[i].getName()\r
61528a1b	106	+ "-- this library instance already exists, please check the library instance list!");\r
878ddf1f	107	} else {\r
bc33b23d	108	this.libInstanceConsumes.put(libInstance, libClassConsmList);\r
878ddf1f	109	}\r
	110	}\r
	111	\r
	112	//\r
	113	// Add library class and library instance map.\r
	114	//\r
83fba802	115	libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch);\r
878ddf1f	116	if (libClassDeclList != null) {\r
bc33b23d	117	this.libInstanceProduces.put(libInstance, libClassDeclList);\r
878ddf1f	118	for (int j = 0; j < libClassDeclList.length; j++) {\r
bc33b23d	119	if (this.libClassProducer.containsKey(libClassDeclList[j])) {\r
192a42b4	120	EdkLog.log(EdkLog.EDK_ERROR,libClassDeclList[j]\r
bc33b23d	121	+ " class is already implemented by "\r
bc33b23d	122	+ this.libClassProducer.get(libClassDeclList[j]));\r
61528a1b	123	throw new AutoGenException("Library Class: " + libClassDeclList\r
391dbbb1	124	+ " already has a library instance!");\r
878ddf1f	125	} else {\r
bc33b23d	126	this.libClassProducer.put(libClassDeclList[j], libInstance);\r
	127	}\r
	128	}\r
	129	}\r
	130	}\r
	131	\r
	132	for (Iterator it = libClassProducer.keySet().iterator(); it.hasNext();) {\r
	133	String className = (String)it.next();\r
	134	libInstance = libClassProducer.get(className);\r
	135	libInstanceConsumedBy.put(libInstance, new HashSet<ModuleIdentification>());\r
	136	\r
	137	for (int k = 0; k < libraryList.length; ++k) {\r
	138	ModuleIdentification consumer = libraryList[k];\r
	139	String[] consumedClassList = libInstanceConsumes.get(consumer);\r
	140	\r
	141	for (int l = 0; l < consumedClassList.length; ++l) {\r
	142	if (consumedClassList[l].equals(className)) {\r
	143	libInstanceConsumedBy.get(libInstance).add(consumer);\r
878ddf1f	144	}\r
	145	}\r
	146	}\r
878ddf1f	147	}\r
878ddf1f	148	}\r
	149	\r
	150	/**\r
	151	orderLibInstance\r
bc33b23d	152	\r
878ddf1f	153	This function reorder the library instance according the library class \r
878ddf1f	154	dependency.\r
bc33b23d	155	\r
878ddf1f	156	@return List which content the ordered library instance.\r
878ddf1f	157	**/\r
bc33b23d	158	List<ModuleIdentification> orderLibInstance() throws EdkException {\r
3dc87a3e	159	LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();\r
bc33b23d	160	LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();\r
	161	\r
	162	for (int i = 0; i < libInstanceList.length; ++i) {\r
	163	if (libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) {\r
	164	noConsumerList.add(libInstanceList[i]);\r
3dc87a3e	165	}\r
3dc87a3e	166	}\r
3dc87a3e	167	\r
bc33b23d	168	while (noConsumerList.size() > 0) {\r
	169	ModuleIdentification n = noConsumerList.poll();\r
	170	orderList.addFirst(n);\r
3dc87a3e	171	\r
bc33b23d	172	String[] consumedClassList = libInstanceConsumes.get(n);\r
	173	for (int i = 0; i < consumedClassList.length; ++i) {\r
	174	ModuleIdentification m = libClassProducer.get(consumedClassList[i]);\r
	175	if (m == null) {\r
	176	continue;\r
3dc87a3e	177	}\r
bc33b23d	178	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);\r
	179	consumedBy.remove(n);\r
	180	if (consumedBy.size() == 0) {\r
	181	noConsumerList.addLast(m);\r
3dc87a3e	182	}\r
3dc87a3e	183	}\r
3dc87a3e	184	\r
bc33b23d	185	boolean circularlyConsumed = false;\r
	186	while (noConsumerList.size() == 0 && !circularlyConsumed) {\r
	187	circularlyConsumed = true;\r
	188	for (int i = 0; i < libInstanceList.length; ++i) {\r
	189	ModuleIdentification libInstance = libInstanceList[i];\r
	190	if (!libInstance.hasConstructor()) {\r
	191	continue;\r
	192	}\r
878ddf1f	193	\r
bc33b23d	194	HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);\r
	195	if (consumedBy.size() == 0) {\r
	196	continue;\r
	197	}\r
	198	\r
	199	ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
	200	for (int j = 0; j < consumedByList.length; ++j) {\r
	201	ModuleIdentification consumer = consumedByList[j];\r
	202	if (consumer.hasConstructor()) {\r
	203	continue;\r
	204	}\r
	205	//\r
	206	// if there's no constructor in the library instance's consumer, \r
	207	// remove it from the consumer list\r
	208	// \r
	209	consumedBy.remove(consumer);\r
	210	circularlyConsumed = false;\r
	211	if (consumedBy.size() == 0) {\r
	212	noConsumerList.addLast(libInstance);\r
	213	break;\r
	214	}\r
	215	}\r
	216	\r
	217	if (noConsumerList.size() > 0) {\r
	218	break;\r
	219	}\r
878ddf1f	220	}\r
	221	}\r
	222	}\r
878ddf1f	223	\r
bc33b23d	224	for (int i = 0; i < libInstanceList.length; ++i) {\r
	225	if (!orderList.contains(libInstanceList[i])) {\r
	226	orderList.add(libInstanceList[i]);\r
	227	}\r
	228	}\r
	229	return orderList;\r
a29c47e0	230	}\r
a29c47e0	231	}\r