[mirror_edk2.git] / Tools / 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.List;\r
import java.util.Map;\r
\r
import org.apache.xmlbeans.XmlObject;\r
import org.tianocore.build.global.GlobalData;\r
import org.tianocore.build.global.SurfaceAreaQuery;\r
import org.tianocore.build.id.ModuleIdentification;\r
\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> libClassMap = new HashMap<String, ModuleIdentification>();\r
\r
    ///\r
    /// The map of library instance and its implemet libraryClass.\r
    ///\r
    private Map<ModuleIdentification, String[]> libInstanceMap = new HashMap<ModuleIdentification, String[]>();\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 List<LibraryInstanceNode> libInstanceList = new ArrayList<LibraryInstanceNode>();\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 Exception {\r
        LibraryInstanceNode libInstanceNode;\r
        String[]       libClassDeclList = null;\r
        String[]       libClassConsmList = null;\r
        \r
        for (int i = 0; i < libraryList.length; i++) {\r
            //\r
            // Add libraryInstance in to libInstanceList.\r
            // \r
            Map<String, XmlObject> libDoc = GlobalData.getDoc(libraryList[i], arch);\r
            SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc);\r
            libInstanceNode = new LibraryInstanceNode (libraryList[i],saq.getLibConstructorName(), saq.getLibDestructorName());\r
            libInstanceList.add(libInstanceNode);\r
            \r
            //\r
            // Add library instance and consumed library class list to\r
            // libInstanceMap.\r
            //\r
            libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch);\r
            if (libClassConsmList != null) {\r
                String[] classStr = new String[libClassConsmList.length];\r
                for (int k = 0; k < libClassConsmList.length; k++) {\r
                    classStr[k] = libClassConsmList[k];\r
                }\r
                if (this.libInstanceMap.containsKey(libraryList[i])) {\r
                    throw new Exception(\r
                            libraryList[i].getName()\r
                                    + "this library instance already exists, please check the library instance list!");\r
                } else {\r
                    this.libInstanceMap.put(libraryList[i], classStr);\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
                for (int j = 0; j < libClassDeclList.length; j++) {\r
                    if (this.libClassMap.containsKey(libClassDeclList[j])) {\r
                        System.out.println(libClassDeclList[j]\r
                                + " class is already implement by "\r
                                + this.libClassMap.get(libClassDeclList[j]));\r
                        throw new Exception("Library Class: " + libClassDeclList\r
                                + " already has a library instance!");\r
                    } else {\r
                        this.libClassMap.put(libClassDeclList[j], libraryList[i]);\r
                    }\r
                }\r
            }\r
        }\r
\r
        //\r
        // Check is the library instance list meet the require;\r
        //\r
        //for (int s = 0; s < this.libInstanceList.size(); s++) {\r
        //    String[] libClass = this.libInstanceMap.get(this.libInstanceList\r
        //            .get(s));\r
        //    if (libClass != null) {\r
        //        for (int t = 0; t < libClass.length; t++) {\r
        //            if (this.libClassMap.get(libClass[t]) == null) {\r
                        //\r
                        // Note: There exist a kind of module which depend on \r
                        // library class with no instance or whose instance will\r
                        // never be linked into the module. \r
                        // For this satuation, the module has the description of \r
                        // library class in MSA file but no description of \r
                        // corresponding library instance in MBD file. There \r
                        // will be a warnig message given here after a standard \r
                        // log way has been decided.\r
                        //\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() {\r
        List<ModuleIdentification> orderList = new ArrayList<ModuleIdentification>();\r
        //\r
        // Stack of node which track the library instance name ant its visiting\r
        // flag.\r
        //\r
        List<Node> stackList = new ArrayList<Node>();\r
        int stackSize = 0;\r
        ModuleIdentification libInstanceId = null;\r
        if (libInstanceList.size() < 0) {\r
            return null;\r
        }\r
\r
        //\r
        // Reorder the library instance.\r
        //\r
        for (int i = 0; i < libInstanceList.size(); i++) {\r
            //\r
            // If library instance is already in the order list skip it.\r
            //\r
            if (isInLibInstance(orderList, libInstanceList.get(i).libId)) {\r
                continue;\r
            }\r
            \r
            Node node = new Node(libInstanceList.get(i).libId, false);\r
            //\r
            // Use stack to reorder library instance.\r
            // Push node to stack.\r
            //\r
            stackList.add(node);\r
            while (stackList.size() > 0) {\r
                stackSize = stackList.size() - 1;\r
                //\r
                // Pop the first node in stack. If the node flag has been visited\r
                // add this node to orderlist and remove it from stack.\r
                //\r
                if (stackList.get(stackSize).isVisit) {\r
                    if (!isInLibInstance(orderList,\r
                            stackList.get(stackSize).nodeId)) {\r
                        orderList.add(stackList.get(stackSize).nodeId);\r
                        stackList.remove(stackSize);\r
                    }\r
                    \r
                } else {\r
                    //\r
                    // Get the node value and set visit flag as true.\r
                    //\r
                    stackList.get(stackList.size() - 1).isVisit = true;\r
                    String[] libClassList = this.libInstanceMap.get(stackList\r
                            .get(stackSize).nodeId);\r
                    //\r
                    // Push the node dependence library instance to the stack.\r
                    //\r
                    if (libClassList != null) {\r
                        for (int j = 0; j < libClassList.length; j++) {\r
                            libInstanceId = this.libClassMap.get(libClassList[j]);\r
                            if (libInstanceId != null\r
                                    && !isInLibInstance(orderList, libInstanceId)) {\r
                                //\r
                                // If and only if the currently library instance\r
                                // is not in stack and it have constructor or \r
                                // destructor function, push this library \r
                                // instacne in stack.\r
                                //\r
                                if (!isInStackList(stackList, this.libClassMap\r
                                        .get(libClassList[j])) && isHaveConsDestructor(libInstanceId)) {\r
                                    stackList.add(new Node(this.libClassMap\r
                                            .get(libClassList[j]), false));\r
                                }\r
                            }\r
                        }\r
                    }\r
                }\r
            }\r
        }\r
        return orderList;\r
    }\r
\r
    /**\r
      isInLibInstance\r
    \r
      This function check does the library instance already in the list.\r
    \r
      @param list             List of the library instance.\r
      @param instanceName     Name of library instance.\r
      @return                 "true" the library instance in list |\r
                              "false" the library instance is not in list.\r
    **/\r
    private boolean isInLibInstance(List<ModuleIdentification> list, ModuleIdentification instanceId) {\r
        for (int i = 0; i < list.size(); i++) {\r
            \r
            if (instanceId.equals(list.get(i))) {\r
                return true;\r
            }\r
        }\r
        return false;\r
    }\r
\r
    /**\r
      isInStackList \r
      \r
      This function check if the node already in the stack.\r
       \r
      @param list        Stack.\r
      @param nodeName    Name of node.\r
      @return            "true" if node have in stack |\r
                         "false" if node don't in stack.\r
    **/ \r
    private boolean isInStackList(List<Node> list, ModuleIdentification instanceId) {\r
        for (int i = 0; i < list.size(); i++) {\r
            if (instanceId.equals(list.get(i).nodeId)) {\r
                return true;\r
            }\r
        }\r
        return false;\r
    }\r
    \r
    /**\r
      isHaveConsDestructor\r
      \r
      This function check if the library have constructor or destructor \r
      function.\r
      \r
      @param  libName    Name of library\r
      @return            "true" if library have constructor or desconstructor |\r
                         "false" if library don't have constructor \r
                         and desconstructor.\r
    **/\r
    private boolean isHaveConsDestructor (ModuleIdentification libNode){\r
        for (int i = 0; i < libInstanceList.size(); i++){\r
            if (libInstanceList.get(i).libId.equals(libNode)){\r
                if (libInstanceList.get(i).constructorName != null || libInstanceList.get(i).deconstructorName != null){\r
                    return true;\r
                }\r
            }\r
        }\r
        return false;\r
    }\r
}\r
\r
/**\r
  Node \r
 \r
  This class is used as stack node.\r
 \r
 **/\r
class Node {\r
    ModuleIdentification nodeId;\r
\r
    boolean isVisit;\r
\r
    Node(ModuleIdentification nodeId, boolean isVisit) {\r
        this.nodeId = nodeId;\r
        this.isVisit = false;\r
    }\r
}  \r
/**\r
  LibraryInstance Node   \r
  \r
  This class is used to store LibrayInstance and it's deconstructor and constructor\r
**/\r
    \r
class LibraryInstanceNode {\r
    ModuleIdentification libId;\r
    String deconstructorName;\r
    String constructorName;\r
    \r
    LibraryInstanceNode (ModuleIdentification libId, String deconstructor, String constructor){\r
        this.libId = libId;\r
        this.deconstructorName = deconstructor;\r
        this.constructorName   = constructor;\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.List;\r
	22	import java.util.Map;\r
	23	\r
	24	import org.apache.xmlbeans.XmlObject;\r
	25	import org.tianocore.build.global.GlobalData;\r
	26	import org.tianocore.build.global.SurfaceAreaQuery;\r
	27	import org.tianocore.build.id.ModuleIdentification;\r
	28	\r
	29	/**\r
	30	This class This class is to reorder library instance sequence according to\r
	31	library dependence.\r
	32	**/\r
	33	public class AutogenLibOrder {\r
	34	///\r
	35	/// The map of library class and its library instance.\r
	36	///\r
	37	private Map<String, ModuleIdentification> libClassMap = new HashMap<String, ModuleIdentification>();\r
	38	\r
	39	///\r
	40	/// The map of library instance and its implemet libraryClass.\r
	41	///\r
	42	private Map<ModuleIdentification, String[]> libInstanceMap = new HashMap<ModuleIdentification, String[]>();\r
	43	\r
	44	///\r
	45	/// List of library instance. It is String[3] list, String[0] is libraryName,\r
	46	/// String[1] is libraryConstructor name, String[2] is libDestructor name.\r
	47	///\r
	48	private List<LibraryInstanceNode> libInstanceList = new ArrayList<LibraryInstanceNode>();\r
	49	\r
	50	/**\r
	51	Constructor function\r
	52	\r
	53	This function mainly initialize some member variable.\r
	54	\r
	55	@param libraryList List of the library instance.\r
	56	@throws Exception\r
	57	**/\r
	58	AutogenLibOrder(ModuleIdentification[] libraryList, String arch) throws Exception {\r
	59	LibraryInstanceNode libInstanceNode;\r
	60	String[] libClassDeclList = null;\r
	61	String[] libClassConsmList = null;\r
	62	\r
	63	for (int i = 0; i < libraryList.length; i++) {\r
	64	//\r
	65	// Add libraryInstance in to libInstanceList.\r
	66	// \r
	67	Map<String, XmlObject> libDoc = GlobalData.getDoc(libraryList[i], arch);\r
	68	SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc);\r
	69	libInstanceNode = new LibraryInstanceNode (libraryList[i],saq.getLibConstructorName(), saq.getLibDestructorName());\r
	70	libInstanceList.add(libInstanceNode);\r
	71	\r
	72	//\r
	73	// Add library instance and consumed library class list to\r
	74	// libInstanceMap.\r
	75	//\r
	76	libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch);\r
	77	if (libClassConsmList != null) {\r
	78	String[] classStr = new String[libClassConsmList.length];\r
	79	for (int k = 0; k < libClassConsmList.length; k++) {\r
	80	classStr[k] = libClassConsmList[k];\r
	81	}\r
	82	if (this.libInstanceMap.containsKey(libraryList[i])) {\r
	83	throw new Exception(\r
	84	libraryList[i].getName()\r
	85	+ "this library instance already exists, please check the library instance list!");\r
	86	} else {\r
	87	this.libInstanceMap.put(libraryList[i], classStr);\r
	88	}\r
	89	}\r
	90	\r
	91	//\r
	92	// Add library class and library instance map.\r
	93	//\r
	94	libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch);\r
	95	if (libClassDeclList != null) {\r
	96	for (int j = 0; j < libClassDeclList.length; j++) {\r
	97	if (this.libClassMap.containsKey(libClassDeclList[j])) {\r
	98	System.out.println(libClassDeclList[j]\r
	99	+ " class is already implement by "\r
	100	+ this.libClassMap.get(libClassDeclList[j]));\r
	101	throw new Exception("Library Class: " + libClassDeclList\r
	102	+ " already has a library instance!");\r
	103	} else {\r
	104	this.libClassMap.put(libClassDeclList[j], libraryList[i]);\r
	105	}\r
	106	}\r
	107	}\r
	108	}\r
	109	\r
	110	//\r
	111	// Check is the library instance list meet the require;\r
	112	//\r
	113	//for (int s = 0; s < this.libInstanceList.size(); s++) {\r
	114	// String[] libClass = this.libInstanceMap.get(this.libInstanceList\r
	115	// .get(s));\r
	116	// if (libClass != null) {\r
	117	// for (int t = 0; t < libClass.length; t++) {\r
	118	// if (this.libClassMap.get(libClass[t]) == null) {\r
	119	//\r
	120	// Note: There exist a kind of module which depend on \r
	121	// library class with no instance or whose instance will\r
	122	// never be linked into the module. \r
	123	// For this satuation, the module has the description of \r
	124	// library class in MSA file but no description of \r
	125	// corresponding library instance in MBD file. There \r
	126	// will be a warnig message given here after a standard \r
	127	// log way has been decided.\r
	128	//\r
	129	// }\r
	130	// }\r
	131	// }\r
	132	//}\r
	133	}\r
	134	\r
	135	/**\r
	136	orderLibInstance\r
	137	\r
	138	This function reorder the library instance according the library class \r
	139	dependency.\r
	140	\r
	141	@return List which content the ordered library instance.\r
	142	**/\r
	143	List<ModuleIdentification> orderLibInstance() {\r
	144	List<ModuleIdentification> orderList = new ArrayList<ModuleIdentification>();\r
	145	//\r
	146	// Stack of node which track the library instance name ant its visiting\r
	147	// flag.\r
	148	//\r
	149	List<Node> stackList = new ArrayList<Node>();\r
	150	int stackSize = 0;\r
	151	ModuleIdentification libInstanceId = null;\r
	152	if (libInstanceList.size() < 0) {\r
	153	return null;\r
	154	}\r
	155	\r
	156	//\r
	157	// Reorder the library instance.\r
	158	//\r
	159	for (int i = 0; i < libInstanceList.size(); i++) {\r
	160	//\r
	161	// If library instance is already in the order list skip it.\r
	162	//\r
	163	if (isInLibInstance(orderList, libInstanceList.get(i).libId)) {\r
	164	continue;\r
	165	}\r
	166	\r
	167	Node node = new Node(libInstanceList.get(i).libId, false);\r
	168	//\r
	169	// Use stack to reorder library instance.\r
	170	// Push node to stack.\r
	171	//\r
	172	stackList.add(node);\r
	173	while (stackList.size() > 0) {\r
	174	stackSize = stackList.size() - 1;\r
	175	//\r
	176	// Pop the first node in stack. If the node flag has been visited\r
	177	// add this node to orderlist and remove it from stack.\r
	178	//\r
	179	if (stackList.get(stackSize).isVisit) {\r
	180	if (!isInLibInstance(orderList,\r
	181	stackList.get(stackSize).nodeId)) {\r
	182	orderList.add(stackList.get(stackSize).nodeId);\r
	183	stackList.remove(stackSize);\r
	184	}\r
	185	\r
	186	} else {\r
	187	//\r
	188	// Get the node value and set visit flag as true.\r
	189	//\r
	190	stackList.get(stackList.size() - 1).isVisit = true;\r
	191	String[] libClassList = this.libInstanceMap.get(stackList\r
	192	.get(stackSize).nodeId);\r
	193	//\r
	194	// Push the node dependence library instance to the stack.\r
	195	//\r
	196	if (libClassList != null) {\r
	197	for (int j = 0; j < libClassList.length; j++) {\r
	198	libInstanceId = this.libClassMap.get(libClassList[j]);\r
	199	if (libInstanceId != null\r
	200	&& !isInLibInstance(orderList, libInstanceId)) {\r
	201	//\r
	202	// If and only if the currently library instance\r
	203	// is not in stack and it have constructor or \r
	204	// destructor function, push this library \r
	205	// instacne in stack.\r
	206	//\r
	207	if (!isInStackList(stackList, this.libClassMap\r
	208	.get(libClassList[j])) && isHaveConsDestructor(libInstanceId)) {\r
	209	stackList.add(new Node(this.libClassMap\r
	210	.get(libClassList[j]), false));\r
	211	}\r
	212	}\r
	213	}\r
	214	}\r
	215	}\r
	216	}\r
	217	}\r
	218	return orderList;\r
	219	}\r
	220	\r
	221	/**\r
	222	isInLibInstance\r
	223	\r
	224	This function check does the library instance already in the list.\r
	225	\r
	226	@param list List of the library instance.\r
	227	@param instanceName Name of library instance.\r
	228	@return "true" the library instance in list \|\r
	229	"false" the library instance is not in list.\r
	230	**/\r
	231	private boolean isInLibInstance(List<ModuleIdentification> list, ModuleIdentification instanceId) {\r
	232	for (int i = 0; i < list.size(); i++) {\r
	233	\r
	234	if (instanceId.equals(list.get(i))) {\r
	235	return true;\r
	236	}\r
	237	}\r
	238	return false;\r
	239	}\r
	240	\r
	241	/**\r
	242	isInStackList \r
	243	\r
	244	This function check if the node already in the stack.\r
	245	\r
	246	@param list Stack.\r
	247	@param nodeName Name of node.\r
	248	@return "true" if node have in stack \|\r
	249	"false" if node don't in stack.\r
	250	**/ \r
	251	private boolean isInStackList(List<Node> list, ModuleIdentification instanceId) {\r
	252	for (int i = 0; i < list.size(); i++) {\r
	253	if (instanceId.equals(list.get(i).nodeId)) {\r
	254	return true;\r
	255	}\r
	256	}\r
	257	return false;\r
	258	}\r
	259	\r
	260	/**\r
	261	isHaveConsDestructor\r
	262	\r
	263	This function check if the library have constructor or destructor \r
	264	function.\r
	265	\r
	266	@param libName Name of library\r
	267	@return "true" if library have constructor or desconstructor \|\r
	268	"false" if library don't have constructor \r
	269	and desconstructor.\r
	270	**/\r
	271	private boolean isHaveConsDestructor (ModuleIdentification libNode){\r
	272	for (int i = 0; i < libInstanceList.size(); i++){\r
	273	if (libInstanceList.get(i).libId.equals(libNode)){\r
	274	if (libInstanceList.get(i).constructorName != null \|\| libInstanceList.get(i).deconstructorName != null){\r
	275	return true;\r
	276	}\r
	277	}\r
	278	}\r
	279	return false;\r
	280	}\r
	281	}\r
	282	\r
	283	/**\r
	284	Node \r
	285	\r
	286	This class is used as stack node.\r
	287	\r
	288	**/\r
	289	class Node {\r
	290	ModuleIdentification nodeId;\r
	291	\r
	292	boolean isVisit;\r
	293	\r
	294	Node(ModuleIdentification nodeId, boolean isVisit) {\r
	295	this.nodeId = nodeId;\r
	296	this.isVisit = false;\r
	297	}\r
	298	} \r
	299	/**\r
	300	LibraryInstance Node \r
	301	\r
	302	This class is used to store LibrayInstance and it's deconstructor and constructor\r
	303	**/\r
	304	\r
	305	class LibraryInstanceNode {\r
	306	ModuleIdentification libId;\r
	307	String deconstructorName;\r
	308	String constructorName;\r
	309	\r
	310	LibraryInstanceNode (ModuleIdentification libId, String deconstructor, String constructor){\r
	311	this.libId = libId;\r
	312	this.deconstructorName = deconstructor;\r
	313	this.constructorName = constructor;\r
	314	}\r
	315	}\r