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