Tools/Java/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.Iterator;
  22 import java.util.LinkedList;
  23 import java.util.List;
  24 import java.util.Map;
  25 import java.util.Stack;
  26 import java.util.HashSet;
  27
  28 import org.apache.xmlbeans.XmlObject;
  29 import org.tianocore.build.exception.AutoGenException;
  30 import org.tianocore.build.global.GlobalData;
  31 import org.tianocore.build.global.SurfaceAreaQuery;
  32 import org.tianocore.build.id.ModuleIdentification;
  33 import org.tianocore.common.exception.EdkException;
  34 import org.tianocore.common.logger.EdkLog;
  35 /**
  36   This class This class is to reorder library instance sequence according to
  37   library dependence.
  38 **/
  39 public class AutogenLibOrder {
  40     ///
  41     /// The map of library class and its library instance.
  42     ///
  43     private Map<String, ModuleIdentification> libClassMap = new HashMap<String, ModuleIdentification>();
  44
  45     ///
  46     /// The map of library instance and its implemet libraryClass.
  47     ///
  48     private Map<ModuleIdentification, String[]> libInstanceMap = new HashMap<ModuleIdentification, String[]>();
  49
  50     ///
  51     /// List of library instance. It is String[3] list, String[0] is libraryName,
  52     /// String[1] is libraryConstructor name, String[2] is libDestructor name.
  53     ///
  54     private List<LibraryInstanceNode> libInstanceList = new ArrayList<LibraryInstanceNode>();
  55
  56     /**
  57       Constructor function
  58
  59       This function mainly initialize some member variable.
  60
  61       @param  libraryList   List of the library instance.
  62       @throws Exception
  63     **/
  64     AutogenLibOrder(ModuleIdentification[] libraryList, String arch) throws EdkException {
  65         LibraryInstanceNode libInstanceNode;
  66         String[]       libClassDeclList = null;
  67         String[]       libClassConsmList = null;
  68
  69         for (int i = 0; i < libraryList.length; i++) {
  70             //
  71             // Add libraryInstance in to libInstanceList.
  72             //
  73             Map<String, XmlObject> libDoc = GlobalData.getDoc(libraryList[i], arch);
  74             SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc);
  75             libInstanceNode = new LibraryInstanceNode (libraryList[i],saq.getLibConstructorName(), saq.getLibDestructorName());
  76             libInstanceList.add(libInstanceNode);
  77
  78             //
  79             // Add library instance and consumed library class list to
  80             // libInstanceMap.
  81             //
  82             libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch);
  83             if (libClassConsmList != null) {
  84                 String[] classStr = new String[libClassConsmList.length];
  85                 for (int k = 0; k < libClassConsmList.length; k++) {
  86                     classStr[k] = libClassConsmList[k];
  87                 }
  88                 if (this.libInstanceMap.containsKey(libraryList[i])) {
  89                     throw new AutoGenException(
  90                             libraryList[i].getName()
  91                                     + "-- this library instance already exists, please check the library instance list!");
  92                 } else {
  93                     this.libInstanceMap.put(libraryList[i], classStr);
  94                 }
  95             }
  96
  97             //
  98             // Add library class and library instance map.
  99             //
 100             libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch);
 101             if (libClassDeclList != null) {
 102                 for (int j = 0; j < libClassDeclList.length; j++) {
 103                     if (this.libClassMap.containsKey(libClassDeclList[j])) {
 104                         EdkLog.log(EdkLog.EDK_ERROR,libClassDeclList[j]
 105                                 + " class is already implement by "
 106                                 + this.libClassMap.get(libClassDeclList[j]));
 107                         throw new AutoGenException("Library Class: " + libClassDeclList
 108                                 + " already has a library instance!");
 109                     } else {
 110                         this.libClassMap.put(libClassDeclList[j], libraryList[i]);
 111                     }
 112                 }
 113             }
 114         }
 115     }
 116
 117     /**
 118       orderLibInstance
 119
 120       This function reorder the library instance according the library class
 121       dependency.
 122
 123       @return     List which content the ordered library instance.
 124     **/
 125     List<ModuleIdentification> orderLibInstance() {
 126         LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();
 127         for (int i = 0; i < libInstanceList.size(); ++i) {
 128             ModuleIdentification current = libInstanceList.get(i).libId;
 129             int insertPoint = orderList.size();
 130             //
 131             // check current library instance against orderred ones in orderList
 132             //
 133             for (int j = 0; j < orderList.size(); ++j) {
 134                 ModuleIdentification old = orderList.get(j);
 135                 if (consumes(current, old)) {
 136                     //
 137                     // if current library instance consumes the one in orderList
 138                     // it must be put after
 139                     //
 140                     insertPoint = j + 1;
 141                 } else if (consumes(old, current)) {
 142                     //
 143                     // if current library instance is consumed by the one in orderList
 144                     // it must be put before. And no further check is needed.
 145                     //
 146                     insertPoint = j;
 147                     break;
 148                 }
 149             }
 150             orderList.add(insertPoint, current);
 151         }
 152
 153         return orderList;
 154     }
 155
 156     //
 157     // Test if one library consumes another library
 158     //
 159     private boolean consumes(ModuleIdentification lib1, ModuleIdentification lib2) {
 160         LinkedList<ModuleIdentification> stack = new LinkedList<ModuleIdentification>();
 161
 162         stack.add(lib1);
 163         int j = 0;
 164         while (j < stack.size()) {
 165             //
 166             // get the last library instance in stack, which hasn't been checked
 167             //
 168             ModuleIdentification lib = stack.get(j++);
 169             //
 170             // get the library classes consumed by it
 171             //
 172             String[] consumedClasses = libInstanceMap.get(lib);
 173             for (int i = 0; i < consumedClasses.length; ++i) {
 174                 //
 175                 // for each library class, find its corresponding library instance
 176                 //
 177                 ModuleIdentification consumedLib = libClassMap.get(consumedClasses[i]);
 178                 //
 179                 // if the corresponding instance is the "lib2", we can say that
 180                 // "lib1"  consumes "lib2"
 181                 //
 182                 if (consumedLib == lib2) {
 183                     EdkLog.log(EdkLog.EDK_DEBUG, lib1 + "\n   consumes\n" + lib2 + "\n");
 184                     return true;
 185                 }
 186                 //
 187                 // otherwise, we put it back into the stack to check it later
 188                 // to see if it consumes "lib2" or not. If the library instance
 189                 // consumed by "lib1" consumes "lib2", we can also say that "lib1"
 190                 // consumes "lib2"
 191                 //
 192                 if (consumedLib != null && !stack.contains(consumedLib)) {
 193                     stack.offer(consumedLib);
 194                 } else if (consumedLib == lib1) {
 195                     //
 196                     // found circular consume, do nothing now but just print
 197                     // out message for debugging
 198                     //
 199                     String msg = "!!! Library consumes circularly: ";
 200                     for (int k = 0; k < j; k++) {
 201                         msg += stack.get(k).getName() + "->";
 202                     }
 203                     msg += lib1.getName();
 204                     EdkLog.log(EdkLog.EDK_DEBUG, msg);
 205                 }
 206             }
 207         }
 208         return false;
 209     }
 210
 211     /**
 212       isInLibInstance
 213
 214       This function check does the library instance already in the list.
 215
 216       @param list             List of the library instance.
 217       @param instanceName     Name of library instance.
 218       @return                 "true" the library instance in list |
 219                               "false" the library instance is not in list.
 220     **/
 221     private boolean isInLibInstance(List<ModuleIdentification> list, ModuleIdentification instanceId) {
 222         for (int i = 0; i < list.size(); i++) {
 223
 224             if (instanceId.equals(list.get(i))) {
 225                 return true;
 226             }
 227         }
 228         return false;
 229     }
 230
 231     /**
 232       isInStackList
 233
 234       This function check if the node already in the stack.
 235
 236       @param list        Stack.
 237       @param nodeName    Name of node.
 238       @return            "true" if node have in stack |
 239                          "false" if node don't in stack.
 240     **/
 241     private boolean isInStackList(List<Node> list, ModuleIdentification instanceId) {
 242         for (int i = 0; i < list.size(); i++) {
 243             if (instanceId.equals(list.get(i).nodeId)) {
 244                 return true;
 245             }
 246         }
 247         return false;
 248     }
 249
 250     /**
 251       isHaveConsDestructor
 252
 253       This function check if the library have constructor or destructor
 254       function.
 255
 256       @param  libName    Name of library
 257       @return            "true" if library have constructor or desconstructor |
 258                          "false" if library don't have constructor
 259                          and desconstructor.
 260     **/
 261     private boolean isHaveConsDestructor (ModuleIdentification libNode){
 262         for (int i = 0; i < libInstanceList.size(); i++){
 263             if (libInstanceList.get(i).libId.equals(libNode)){
 264                 if (libInstanceList.get(i).constructorName != null || libInstanceList.get(i).deconstructorName != null){
 265                     return true;
 266                 }
 267             }
 268         }
 269         return false;
 270     }
 271 }
 272
 273 /**
 274   Node
 275
 276   This class is used as stack node.
 277
 278  **/
 279 class Node {
 280     ModuleIdentification nodeId;
 281
 282     boolean isVisit;
 283
 284     Node(ModuleIdentification nodeId, boolean isVisit) {
 285         this.nodeId = nodeId;
 286         this.isVisit = false;
 287     }
 288 }
 289 /**
 290   LibraryInstance Node
 291
 292   This class is used to store LibrayInstance and it's deconstructor and constructor
 293 **/
 294
 295 class LibraryInstanceNode {
 296     ModuleIdentification libId;
 297     String deconstructorName;
 298     String constructorName;
 299
 300     LibraryInstanceNode (ModuleIdentification libId, String deconstructor, String constructor){
 301         this.libId = libId;
 302         this.deconstructorName = deconstructor;
 303         this.constructorName   = constructor;
 304     }
 305 }