Tools/Source/GenBuild/org/tianocore/build/autogen/AutogenLibOrder.java

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