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 = new ModuleIdentification[libraryList.length];
  80         for (int i = 0; i < libraryList.length; i++) {
  81             libInstance = libraryList[i];
  82             libInstanceList[i] = libInstance;
  83             //
  84             // Add libraryInstance in to libInstanceList.
  85             //
  86             Map<String, XmlObject> libDoc = GlobalData.getDoc(libInstance, arch);
  87             SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc);
  88             libInstance.setConstructor(saq.getLibConstructorName());
  89             libInstance.setDestructor(saq.getLibDestructorName());
  90
  91             //
  92             // Add library instance and consumed library class list to
  93             // libInstanceConsumes.
  94             //
  95             libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch);
  96             if (libClassConsmList != null) {
  97                 /*
  98                 String[] classStr = new String[libClassConsmList.length];
  99                 for (int k = 0; k < libClassConsmList.length; k++) {
 100                     classStr[k] = libClassConsmList[k];
 101                 }
 102                 */
 103                 if (this.libInstanceConsumes.containsKey(libInstance)) {
 104                     throw new AutoGenException(
 105                             libraryList[i].getName()
 106                                     + "-- this library instance already exists, please check the library instance list!");
 107                 } else {
 108                     this.libInstanceConsumes.put(libInstance, libClassConsmList);
 109                 }
 110             }
 111
 112             //
 113             // Add library class and library instance map.
 114             //
 115             libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch);
 116             if (libClassDeclList != null) {
 117                 this.libInstanceProduces.put(libInstance, libClassDeclList);
 118                 for (int j = 0; j < libClassDeclList.length; j++) {
 119                     if (this.libClassProducer.containsKey(libClassDeclList[j])) {
 120                         EdkLog.log(EdkLog.EDK_ERROR,libClassDeclList[j]
 121                                 + " class is already implemented by "
 122                                 + this.libClassProducer.get(libClassDeclList[j]));
 123                         throw new AutoGenException("Library Class: " + libClassDeclList
 124                                 + " already has a library instance!");
 125                     } else {
 126                         this.libClassProducer.put(libClassDeclList[j], libInstance);
 127                     }
 128                 }
 129             }
 130         }
 131
 132         for (Iterator it = libClassProducer.keySet().iterator(); it.hasNext();) {
 133             String className = (String)it.next();
 134             libInstance = libClassProducer.get(className);
 135             libInstanceConsumedBy.put(libInstance, new HashSet<ModuleIdentification>());
 136
 137             for (int k = 0; k < libraryList.length; ++k) {
 138                 ModuleIdentification consumer = libraryList[k];
 139                 String[] consumedClassList = libInstanceConsumes.get(consumer);
 140
 141                 for (int l = 0; l < consumedClassList.length; ++l) {
 142                     if (consumedClassList[l].equals(className)) {
 143                         libInstanceConsumedBy.get(libInstance).add(consumer);
 144                     }
 145                 }
 146             }
 147         }
 148     }
 149
 150     /**
 151       orderLibInstance
 152
 153       This function reorder the library instance according the library class
 154       dependency.
 155
 156       @return     List which content the ordered library instance.
 157     **/
 158     List<ModuleIdentification> orderLibInstance() throws EdkException {
 159         LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();
 160         LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();
 161
 162         for (int i = 0; i < libInstanceList.length; ++i) {
 163             if (libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) {
 164                 noConsumerList.add(libInstanceList[i]);
 165             }
 166         }
 167
 168         while (noConsumerList.size() > 0) {
 169             ModuleIdentification n = noConsumerList.poll();
 170             orderList.addFirst(n);
 171
 172             String[] consumedClassList = libInstanceConsumes.get(n);
 173             for (int i = 0; i < consumedClassList.length; ++i) {
 174                 ModuleIdentification m = libClassProducer.get(consumedClassList[i]);
 175                 if (m == null) {
 176                     continue;
 177                 }
 178                 HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);
 179                 consumedBy.remove(n);
 180                 if (consumedBy.size() == 0) {
 181                     noConsumerList.addLast(m);
 182                 }
 183             }
 184
 185             boolean circularlyConsumed = false;
 186             while (noConsumerList.size() == 0 && !circularlyConsumed) {
 187                 circularlyConsumed = true;
 188                 for (int i = 0; i < libInstanceList.length; ++i) {
 189                     ModuleIdentification libInstance = libInstanceList[i];
 190                     if (!libInstance.hasConstructor()) {
 191                         continue;
 192                     }
 193
 194                     HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);
 195                     if (consumedBy.size() == 0) {
 196                         continue;
 197                     }
 198
 199                     ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);
 200                     for (int j = 0; j < consumedByList.length; ++j) {
 201                         ModuleIdentification consumer = consumedByList[j];
 202                         if (consumer.hasConstructor()) {
 203                             continue;
 204                         }
 205                         //
 206                         // if there's no constructor in the library instance's consumer,
 207                         // remove it from the consumer list
 208                         //
 209                         consumedBy.remove(consumer);
 210                         circularlyConsumed = false;
 211                         if (consumedBy.size() == 0) {
 212                             noConsumerList.addLast(libInstance);
 213                             break;
 214                         }
 215                     }
 216
 217                     if (noConsumerList.size() > 0) {
 218                         break;
 219                     }
 220                 }
 221             }
 222         }
 223
 224         for (int i = 0; i < libInstanceList.length; ++i) {
 225             if (!orderList.contains(libInstanceList[i])) {
 226                 orderList.add(libInstanceList[i]);
 227             }
 228         }
 229         return orderList;
 230     }
 231 }