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);
  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);
 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 (libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) {
 162                 noConsumerList.add(libInstanceList[i]);
 163             }
 164         }
 165
 166         while (noConsumerList.size() > 0) {
 167             ModuleIdentification n = noConsumerList.poll();
 168             orderList.addFirst(n);
 169
 170             String[] consumedClassList = libInstanceConsumes.get(n);
 171             for (int i = 0; i < consumedClassList.length; ++i) {
 172                 ModuleIdentification m = libClassProducer.get(consumedClassList[i]);
 173                 if (m == null) {
 174                     continue;
 175                 }
 176                 HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);
 177                 if (consumedBy.size() == 0) {
 178                   continue;
 179                 }
 180
 181                 consumedBy.remove(n);
 182                 if (consumedBy.size() == 0) {
 183                     noConsumerList.addLast(m);
 184                 }
 185             }
 186
 187             boolean circularlyConsumed = false;
 188             while (noConsumerList.size() == 0 && !circularlyConsumed) {
 189                 circularlyConsumed = true;
 190                 for (int i = 0; i < libInstanceList.length; ++i) {
 191                     ModuleIdentification libInstance = libInstanceList[i];
 192                     if (!libInstance.hasConstructor()) {
 193                         continue;
 194                     }
 195
 196                     HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);
 197                     if (consumedBy.size() == 0) {
 198                         continue;
 199                     }
 200
 201                     ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);
 202                     for (int j = 0; j < consumedByList.length; ++j) {
 203                         ModuleIdentification consumer = consumedByList[j];
 204                         if (consumer.hasConstructor()) {
 205                             continue;
 206                         }
 207
 208                         //
 209                         // if there's no constructor in the library instance's consumer,
 210                         // remove it from the consumer list
 211                         //
 212                         consumedBy.remove(consumer);
 213                         circularlyConsumed = false;
 214                         if (consumedBy.size() == 0) {
 215                             noConsumerList.addLast(libInstance);
 216                             break;
 217                         }
 218                     }
 219
 220                     if (noConsumerList.size() > 0) {
 221                         break;
 222                     }
 223                 }
 224
 225                 if (noConsumerList.size() == 0 && !circularlyConsumed) {
 226                   break;
 227                 }
 228             }
 229         }
 230
 231         //
 232         // Append the remaining library instance to the end of sorted list
 233         //
 234         boolean HasError = false;
 235         for (int i = 0; i < libInstanceList.length; ++i) {
 236             HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstanceList[i]);
 237             if (consumedBy.size() > 0 && libInstanceList[i].hasConstructor()) {
 238                 EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()
 239                            + " with constructor has a circular dependency!");
 240                 ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);
 241                 for (int j = 0; j < consumedByList.length; ++j) {
 242                     EdkLog.log(EdkLog.EDK_ERROR,
 243                                " consumed by " + consumedByList[j].getName());
 244                 }
 245                 HasError = true;
 246             }
 247
 248             if (!orderList.contains(libInstanceList[i])) {
 249                 orderList.add(libInstanceList[i]);
 250             }
 251         }
 252         if (HasError) {
 253             throw new AutoGenException("Circular dependency in library instances is found!");
 254         }
 255
 256         return orderList;
 257     }
 258 }