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