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