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> libClassProducer = new HashMap<String, ModuleIdentification>();
  44
  45     ///
  46     /// The map of library instance and its consumed Library Classes.
  47     ///
  48     private Map<ModuleIdentification, String[]> libInstanceConsumes = new HashMap<ModuleIdentification, String[]>();
  49
  50     ///
  51     /// The map of library instance and its implemeted Library Classes.
  52     ///
  53     private Map<ModuleIdentification, String[]> libInstanceProduces = new HashMap<ModuleIdentification, String[]>();
  54
  55     ///
  56     /// The map of library instance and its consumers.
  57     ///
  58     private Map<ModuleIdentification, HashSet<ModuleIdentification>> libInstanceConsumedBy = new HashMap<ModuleIdentification, HashSet<ModuleIdentification>>();
  59
  60     ///
  61     /// List of library instance. It is String[3] list, String[0] is libraryName,
  62     /// String[1] is libraryConstructor name, String[2] is libDestructor name.
  63     ///
  64     private ModuleIdentification[] libInstanceList = null;
  65
  66     /**
  67       Constructor function
  68
  69       This function mainly initialize some member variable.
  70
  71       @param  libraryList   List of the library instance.
  72       @throws Exception
  73     **/
  74     AutogenLibOrder(ModuleIdentification[] libraryList, String arch) throws EdkException {
  75         ModuleIdentification libInstance;
  76         String[]       libClassDeclList = null;
  77         String[]       libClassConsmList = null;
  78
  79         libInstanceList = libraryList;
  80         for (int i = 0; i < libraryList.length; i++) {
  81             libInstance = libraryList[i];
  82             //
  83             // Fetch the constructor & destructor.
  84             //
  85             Map<String, XmlObject> libDoc = GlobalData.getDoc(libInstance, arch);
  86             SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc);
  87             libInstance.setConstructor(saq.getLibConstructorName());
  88             libInstance.setDestructor(saq.getLibDestructorName());
  89
  90             //
  91             // Create library class consume database.
  92             //
  93             libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch, null);
  94             if (libClassConsmList.length > 0) {
  95                 if (this.libInstanceConsumes.containsKey(libInstance)) {
  96                     throw new AutoGenException(
  97                             libraryList[i].getName()
  98                                     + "-- this library instance already exists, please check the library instance list!");
  99                 } else {
 100                     this.libInstanceConsumes.put(libInstance, libClassConsmList);
 101                 }
 102             }
 103
 104             //
 105             // Create library class implementer database
 106             //
 107             libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch, null);
 108             if (libClassDeclList.length > 0) {
 109                 this.libInstanceProduces.put(libInstance, libClassDeclList);
 110                 for (int j = 0; j < libClassDeclList.length; j++) {
 111                     if (this.libClassProducer.containsKey(libClassDeclList[j])) {
 112                         EdkLog.log(EdkLog.EDK_ERROR,libClassDeclList[j]
 113                                 + " class is already implemented by "
 114                                 + this.libClassProducer.get(libClassDeclList[j]));
 115                         throw new AutoGenException("Library Class: " + libClassDeclList
 116                                 + " already has a library instance!");
 117                     } else {
 118                         this.libClassProducer.put(libClassDeclList[j], libInstance);
 119                     }
 120                 }
 121             }
 122         }
 123
 124         //
 125         // Create a consumed-by database
 126         //
 127         for (Iterator it = libClassProducer.keySet().iterator(); it.hasNext();) {
 128             String className = (String)it.next();
 129             libInstance = libClassProducer.get(className);
 130             libInstanceConsumedBy.put(libInstance, new HashSet<ModuleIdentification>());
 131
 132             for (int k = 0; k < libraryList.length; ++k) {
 133                 ModuleIdentification consumer = libraryList[k];
 134                 String[] consumedClassList = libInstanceConsumes.get(consumer);
 135                 if (consumedClassList == null) {
 136                     continue;
 137                 }
 138
 139                 for (int l = 0; l < consumedClassList.length; ++l) {
 140                     if (consumedClassList[l].equals(className)) {
 141                         libInstanceConsumedBy.get(libInstance).add(consumer);
 142                     }
 143                 }
 144             }
 145         }
 146     }
 147
 148     /**
 149       orderLibInstance
 150
 151       This function reorder the library instance according the library class
 152       dependency, using DAG anaylysis algothim
 153
 154       @return     List which content the ordered library instance.
 155     **/
 156     List<ModuleIdentification> orderLibInstance() throws EdkException {
 157         LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();
 158         LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();
 159
 160         //
 161         // First, add the library instance without consumers to the Q
 162         //
 163         for (int i = 0; i < libInstanceList.length; ++i) {
 164             if (libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) {
 165                 noConsumerList.add(libInstanceList[i]);
 166             }
 167         }
 168
 169         while (noConsumerList.size() > 0) {
 170             ModuleIdentification n = noConsumerList.poll();
 171             orderList.addFirst(n);
 172
 173             String[] consumedClassList = libInstanceConsumes.get(n);
 174             if (consumedClassList == null) {
 175                 continue;
 176             }
 177             for (int i = 0; i < consumedClassList.length; ++i) {
 178                 ModuleIdentification m = libClassProducer.get(consumedClassList[i]);
 179                 if (m == null) {
 180                     continue;
 181                 }
 182                 HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);
 183                 if (consumedBy.size() == 0) {
 184                   continue;
 185                 }
 186
 187                 consumedBy.remove(n);
 188                 if (consumedBy.size() == 0) {
 189                     noConsumerList.addLast(m);
 190                 }
 191             }
 192
 193             boolean circularlyConsumed = false;
 194             while (noConsumerList.size() == 0 && !circularlyConsumed) {
 195                 circularlyConsumed = true;
 196                 for (int i = 0; i < libInstanceList.length; ++i) {
 197                     ModuleIdentification libInstance = libInstanceList[i];
 198                     if (!libInstance.hasConstructor()) {
 199                         continue;
 200                     }
 201
 202                     HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);
 203                     if (consumedBy.size() == 0) {
 204                         continue;
 205                     }
 206
 207                     ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);
 208                     for (int j = 0; j < consumedByList.length; ++j) {
 209                         ModuleIdentification consumer = consumedByList[j];
 210                         if (consumer.hasConstructor()) {
 211                             continue;
 212                         }
 213
 214                         //
 215                         // if there's no constructor in the library instance's consumer,
 216                         // remove it from the consumer list
 217                         //
 218                         consumedBy.remove(consumer);
 219                         circularlyConsumed = false;
 220                         if (consumedBy.size() == 0) {
 221                             noConsumerList.addLast(libInstance);
 222                             break;
 223                         }
 224                     }
 225
 226                     if (noConsumerList.size() > 0) {
 227                         break;
 228                     }
 229                 }
 230
 231                 if (noConsumerList.size() == 0 && !circularlyConsumed) {
 232                   break;
 233                 }
 234             }
 235         }
 236
 237         //
 238         // Append the remaining library instance to the end of sorted list
 239         //
 240         boolean HasError = false;
 241         for (int i = 0; i < libInstanceList.length; ++i) {
 242             HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstanceList[i]);
 243             if (consumedBy.size() > 0 && libInstanceList[i].hasConstructor()) {
 244                 EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()
 245                            + " with constructor has a circular dependency!");
 246                 ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);
 247                 for (int j = 0; j < consumedByList.length; ++j) {
 248                     EdkLog.log(EdkLog.EDK_ERROR, " consumed by " + consumedByList[j].getName());
 249                 }
 250                 HasError = true;
 251             }
 252
 253             if (!orderList.contains(libInstanceList[i])) {
 254                 orderList.add(libInstanceList[i]);
 255             }
 256         }
 257         if (HasError) {
 258             throw new AutoGenException("Circular dependency in library instances is found!");
 259         }
 260
 261         return orderList;
 262     }
 263 }