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 != null) {
  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 != null) {
 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
 136                 for (int l = 0; l < consumedClassList.length; ++l) {
 137                     if (consumedClassList[l].equals(className)) {
 138                         libInstanceConsumedBy.get(libInstance).add(consumer);
 139                     }
 140                 }
 141             }
 142         }
 143     }
 144
 145     /**
 146       orderLibInstance
 147
 148       This function reorder the library instance according the library class
 149       dependency, using DAG anaylysis algothim
 150
 151       @return     List which content the ordered library instance.
 152     **/
 153     List<ModuleIdentification> orderLibInstance() throws EdkException {
 154         LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();
 155         LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();
 156
 157         //
 158         // First, add the library instance without consumers to the Q
 159         //
 160         for (int i = 0; i < libInstanceList.length; ++i) {
 161             if (libInstanceList[i] == null) {
 162                 continue;
 163             }
 164
 165             if (libInstanceConsumedBy.get(libInstanceList[i]) == null ||  libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) {
 166                 noConsumerList.add(libInstanceList[i]);
 167             }
 168         }
 169
 170         while (noConsumerList.size() > 0) {
 171             ModuleIdentification n = noConsumerList.poll();
 172             orderList.addFirst(n);
 173
 174             String[] consumedClassList = libInstanceConsumes.get(n);
 175             for (int i = 0; i < consumedClassList.length; ++i) {
 176                 ModuleIdentification m = libClassProducer.get(consumedClassList[i]);
 177                 if (m == null) {
 178                     continue;
 179                 }
 180                 HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);
 181                 if (consumedBy == null || consumedBy.size() == 0) {
 182                   continue;
 183                 }
 184
 185                 consumedBy.remove(n);
 186                 if (consumedBy.size() == 0) {
 187                     noConsumerList.addLast(m);
 188                 }
 189             }
 190
 191             boolean circularlyConsumed = false;
 192             while (noConsumerList.size() == 0 && !circularlyConsumed) {
 193                 circularlyConsumed = true;
 194                 for (int i = 0; i < libInstanceList.length; ++i) {
 195                     ModuleIdentification libInstance = libInstanceList[i];
 196                     if (!libInstance.hasConstructor()) {
 197                         continue;
 198                     }
 199
 200                     HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);
 201                     if (consumedBy == null || consumedBy.size() == 0) {
 202                         continue;
 203                     }
 204
 205                     ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);
 206                     for (int j = 0; j < consumedByList.length; ++j) {
 207                         ModuleIdentification consumer = consumedByList[j];
 208                         if (consumer.hasConstructor()) {
 209                             continue;
 210                         }
 211
 212                         //
 213                         // if there's no constructor in the library instance's consumer,
 214                         // remove it from the consumer list
 215                         //
 216                         consumedBy.remove(consumer);
 217                         circularlyConsumed = false;
 218                         if (consumedBy.size() == 0) {
 219                             noConsumerList.addLast(libInstance);
 220                             break;
 221                         }
 222                     }
 223
 224                     if (noConsumerList.size() > 0) {
 225                         break;
 226                     }
 227                 }
 228
 229                 if (noConsumerList.size() == 0 && !circularlyConsumed) {
 230                   break;
 231                 }
 232             }
 233         }
 234
 235         //
 236         // Append the remaining library instance to the end of sorted list
 237         //
 238         boolean HasError = false;
 239         for (int i = 0; i < libInstanceList.length; ++i) {
 240             HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstanceList[i]);
 241             if (consumedBy != null && consumedBy.size() > 0 && libInstanceList[i].hasConstructor()) {
 242                 EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()
 243                            + " with constructor has a circular dependency!");
 244                 ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);
 245                 for (int j = 0; j < consumedByList.length; ++j) {
 246                     EdkLog.log(EdkLog.EDK_ERROR, " consumed by " + consumedByList[j].getName());
 247                 }
 248                 HasError = true;
 249             }
 250
 251             if (!orderList.contains(libInstanceList[i])) {
 252                 orderList.add(libInstanceList[i]);
 253             }
 254         }
 255         if (HasError) {
 256             throw new AutoGenException("Circular dependency in library instances is found!");
 257         }
 258
 259         return orderList;
 260     }
 261 }