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