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                 consumedBy.remove(n);
 178                 if (consumedBy.size() == 0) {
 179                     noConsumerList.addLast(m);
 180                 }
 181             }
 182
 183             boolean circularlyConsumed = false;
 184             while (noConsumerList.size() == 0 && !circularlyConsumed) {
 185                 circularlyConsumed = true;
 186                 for (int i = 0; i < libInstanceList.length; ++i) {
 187                     ModuleIdentification libInstance = libInstanceList[i];
 188                     if (!libInstance.hasConstructor()) {
 189                         continue;
 190                     }
 191
 192                     HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);
 193                     if (consumedBy.size() == 0) {
 194                         continue;
 195                     }
 196
 197                     ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);
 198                     for (int j = 0; j < consumedByList.length; ++j) {
 199                         ModuleIdentification consumer = consumedByList[j];
 200                         if (consumer.hasConstructor()) {
 201                             continue;
 202                         }
 203                         //
 204                         // if there's no constructor in the library instance's consumer,
 205                         // remove it from the consumer list
 206                         //
 207                         consumedBy.remove(consumer);
 208                         circularlyConsumed = false;
 209                         if (consumedBy.size() == 0) {
 210                             noConsumerList.addLast(libInstance);
 211                             break;
 212                         }
 213                     }
 214
 215                     if (noConsumerList.size() > 0) {
 216                         break;
 217                     }
 218                 }
 219             }
 220         }
 221
 222         //
 223         // Append the remaining library instance to the end of sorted list
 224         //
 225         for (int i = 0; i < libInstanceList.length; ++i) {
 226             if (!orderList.contains(libInstanceList[i])) {
 227                 orderList.add(libInstanceList[i]);
 228             }
 229         }
 230         return orderList;
 231     }
 232 }