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         // Check is the library instance list meet the require;
 118         //
 119         //for (int s = 0; s < this.libInstanceList.size(); s++) {
 120         //    String[] libClass = this.libInstanceMap.get(this.libInstanceList
 121         //            .get(s));
 122         //    if (libClass != null) {
 123         //        for (int t = 0; t < libClass.length; t++) {
 124         //            if (this.libClassMap.get(libClass[t]) == null) {
 125                         //
 126                         // Note: There exist a kind of module which depend on
 127                         // library class with no instance or whose instance will
 128                         // never be linked into the module.
 129                         // For this satuation, the module has the description of
 130                         // library class in MSA file but no description of
 131                         // corresponding library instance in MBD file. There
 132                         // will be a warnig message given here after a standard
 133                         // log way has been decided.
 134                         //
 135         //           }
 136         //       }
 137         //   }
 138         //}
 139     }
 140
 141     /**
 142       orderLibInstance
 143
 144       This function reorder the library instance according the library class
 145       dependency.
 146
 147       @return     List which content the ordered library instance.
 148     **/
 149     List<ModuleIdentification> orderLibInstance1() {
 150         List<ModuleIdentification> orderList = new ArrayList<ModuleIdentification>();
 151         //
 152         // Stack of node which track the library instance name ant its visiting
 153         // flag.
 154         //
 155         List<Node> stackList = new ArrayList<Node>();
 156         int stackSize = 0;
 157         ModuleIdentification libInstanceId = null;
 158         if (libInstanceList.size() < 0) {
 159             return null;
 160         }
 161
 162         //
 163         // Reorder the library instance.
 164         //
 165         for (int i = 0; i < libInstanceList.size(); i++) {
 166             //
 167             // If library instance is already in the order list skip it.
 168             //
 169             if (isInLibInstance(orderList, libInstanceList.get(i).libId)) {
 170                 continue;
 171             }
 172
 173             Node node = new Node(libInstanceList.get(i).libId, false);
 174             //
 175             // Use stack to reorder library instance.
 176             // Push node to stack.
 177             //
 178             stackList.add(node);
 179             while (stackList.size() > 0) {
 180                 stackSize = stackList.size() - 1;
 181                 //
 182                 // Pop the first node in stack. If the node flag has been visited
 183                 // add this node to orderlist and remove it from stack.
 184                 //
 185                 if (stackList.get(stackSize).isVisit) {
 186                     if (!isInLibInstance(orderList,
 187                             stackList.get(stackSize).nodeId)) {
 188                         orderList.add(stackList.get(stackSize).nodeId);
 189                         stackList.remove(stackSize);
 190                     }
 191
 192                 } else {
 193                     //
 194                     // Get the node value and set visit flag as true.
 195                     //
 196                     stackList.get(stackList.size() - 1).isVisit = true;
 197                     String[] libClassList = this.libInstanceMap.get(stackList
 198                             .get(stackSize).nodeId);
 199                     //
 200                     // Push the node dependence library instance to the stack.
 201                     //
 202                     if (libClassList != null) {
 203                         for (int j = 0; j < libClassList.length; j++) {
 204                             libInstanceId = this.libClassMap.get(libClassList[j]);
 205                             if (libInstanceId != null
 206                                     && !isInLibInstance(orderList, libInstanceId)) {
 207                                 //
 208                                 // If and only if the currently library instance
 209                                 // is not in stack and it have constructor or
 210                                 // destructor function, push this library
 211                                 // instacne in stack.
 212                                 //
 213                                 if (!isInStackList(stackList, this.libClassMap
 214                                         .get(libClassList[j])) /* && isHaveConsDestructor(libInstanceId) */) {
 215                                     stackList.add(new Node(this.libClassMap
 216                                             .get(libClassList[j]), false));
 217                                 }
 218                             }
 219                         }
 220                     }
 221                 }
 222                 System.out.println("################################################");
 223                 for (int ii = 0; ii < orderList.size(); ++ii) {
 224                     System.out.println("  " + orderList.get(ii));
 225                 }
 226             }
 227         }
 228         return orderList;
 229     }
 230
 231     List<ModuleIdentification> orderLibInstance() {
 232         LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();
 233         for (int i = 0; i < libInstanceList.size(); ++i) {
 234             ModuleIdentification current = libInstanceList.get(i).libId;
 235             int insertPoint = orderList.size();
 236             for (int j = 0; j < orderList.size(); ++j) {
 237                 ModuleIdentification old = orderList.get(j);
 238                 //System.out.println("### old = " + old);
 239                 if (consumes(current, old)) {
 240                     insertPoint = j + 1;
 241                 } else if (consumes(old, current)) {
 242                     insertPoint = j;
 243                     break;
 244                 }
 245             }
 246             orderList.add(insertPoint, current);
 247 //             System.out.println("################################################");
 248 //             for (int ii = 0; ii < orderList.size(); ++ii) {
 249 //                 System.out.println("  " + orderList.get(ii));
 250 //             }
 251         }
 252
 253         return orderList;
 254     }
 255
 256     boolean consumes(ModuleIdentification lib1, ModuleIdentification lib2) {
 257         //System.out.println("$$$ lib1 = " + lib1);
 258         LinkedList<ModuleIdentification> stack = new LinkedList<ModuleIdentification>();
 259         stack.add(lib1);
 260         int j = 0;
 261         while (j < stack.size()) {
 262             ModuleIdentification lib = stack.get(j++);
 263             String[] consumedClasses = libInstanceMap.get(lib);
 264             for (int i = 0; i < consumedClasses.length; ++i) {
 265                 ModuleIdentification consumedLib = libClassMap.get(consumedClasses[i]);
 266                 //System.out.println("$$$ class = " + consumedClasses[i]);
 267                 //System.out.println("$$$ insta = " + consumedLib);
 268                 if (consumedLib == lib2) {
 269                     //System.out.println(lib1 + "\n   consumes\n" + lib2 + "\n");
 270                     return true;
 271                 }
 272                 if (consumedLib != null && !stack.contains(consumedLib)) {
 273                     stack.offer(consumedLib);
 274                 }
 275             }
 276         }
 277         return false;
 278     }
 279
 280     /**
 281       isInLibInstance
 282
 283       This function check does the library instance already in the list.
 284
 285       @param list             List of the library instance.
 286       @param instanceName     Name of library instance.
 287       @return                 "true" the library instance in list |
 288                               "false" the library instance is not in list.
 289     **/
 290     private boolean isInLibInstance(List<ModuleIdentification> list, ModuleIdentification instanceId) {
 291         for (int i = 0; i < list.size(); i++) {
 292
 293             if (instanceId.equals(list.get(i))) {
 294                 return true;
 295             }
 296         }
 297         return false;
 298     }
 299
 300     /**
 301       isInStackList
 302
 303       This function check if the node already in the stack.
 304
 305       @param list        Stack.
 306       @param nodeName    Name of node.
 307       @return            "true" if node have in stack |
 308                          "false" if node don't in stack.
 309     **/
 310     private boolean isInStackList(List<Node> list, ModuleIdentification instanceId) {
 311         for (int i = 0; i < list.size(); i++) {
 312             if (instanceId.equals(list.get(i).nodeId)) {
 313                 return true;
 314             }
 315         }
 316         return false;
 317     }
 318
 319     /**
 320       isHaveConsDestructor
 321
 322       This function check if the library have constructor or destructor
 323       function.
 324
 325       @param  libName    Name of library
 326       @return            "true" if library have constructor or desconstructor |
 327                          "false" if library don't have constructor
 328                          and desconstructor.
 329     **/
 330     private boolean isHaveConsDestructor (ModuleIdentification libNode){
 331         for (int i = 0; i < libInstanceList.size(); i++){
 332             if (libInstanceList.get(i).libId.equals(libNode)){
 333                 if (libInstanceList.get(i).constructorName != null || libInstanceList.get(i).deconstructorName != null){
 334                     return true;
 335                 }
 336             }
 337         }
 338         return false;
 339     }
 340 }
 341
 342 /**
 343   Node
 344
 345   This class is used as stack node.
 346
 347  **/
 348 class Node {
 349     ModuleIdentification nodeId;
 350
 351     boolean isVisit;
 352
 353     Node(ModuleIdentification nodeId, boolean isVisit) {
 354         this.nodeId = nodeId;
 355         this.isVisit = false;
 356     }
 357 }
 358 /**
 359   LibraryInstance Node
 360
 361   This class is used to store LibrayInstance and it's deconstructor and constructor
 362 **/
 363
 364 class LibraryInstanceNode {
 365     ModuleIdentification libId;
 366     String deconstructorName;
 367     String constructorName;
 368
 369     LibraryInstanceNode (ModuleIdentification libId, String deconstructor, String constructor){
 370         this.libId = libId;
 371         this.deconstructorName = deconstructor;
 372         this.constructorName   = constructor;
 373     }
 374 }