1## @file
2# Common routines used by workspace
3#
4# Copyright (c) 2012, Intel Corporation. All rights reserved.<BR>
5# This program and the accompanying materials
6# are licensed and made available under the terms and conditions of the BSD License
7# which accompanies this distribution.  The full text of the license may be found at
8# http://opensource.org/licenses/bsd-license.php
9#
10# THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
11# WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
12#
13
14from Common.Misc import sdict
15from Common.DataType import SUP_MODULE_USER_DEFINED
16from BuildClassObject import LibraryClassObject
17
18## Get all packages from platform for specified arch, target and toolchain
19#
20#  @param Platform: DscBuildData instance
21#  @param BuildDatabase: The database saves all data for all metafiles
22#  @param Arch: Current arch
23#  @param Target: Current target
24#  @param Toolchain: Current toolchain
25#  @retval: List of packages which are DecBuildData instances
26#
27def GetPackageList(Platform, BuildDatabase, Arch, Target, Toolchain):
28    PkgSet = set()
29    for ModuleFile in Platform.Modules:
30        Data = BuildDatabase[ModuleFile, Arch, Target, Toolchain]
31        PkgSet.update(Data.Packages)
32        for Lib in GetLiabraryInstances(Data, Platform, BuildDatabase, Arch, Target, Toolchain):
33            PkgSet.update(Lib.Packages)
34    return list(PkgSet)
35
36## Get all declared PCD from platform for specified arch, target and toolchain
37#
38#  @param Platform: DscBuildData instance
39#  @param BuildDatabase: The database saves all data for all metafiles
40#  @param Arch: Current arch
41#  @param Target: Current target
42#  @param Toolchain: Current toolchain
43#  @retval: A dictionary contains instances of PcdClassObject with key (PcdCName, TokenSpaceGuid)
44#
45def GetDeclaredPcd(Platform, BuildDatabase, Arch, Target, Toolchain):
46    PkgList = GetPackageList(Platform, BuildDatabase, Arch, Target, Toolchain)
47    DecPcds = {}
48    for Pkg in PkgList:
49        for Pcd in Pkg.Pcds:
50            DecPcds[Pcd[0], Pcd[1]] = Pkg.Pcds[Pcd]
51    return DecPcds
52
53## Get all dependent libraries for a module
54#
55#  @param Module: InfBuildData instance
56#  @param Platform: DscBuildData instance
57#  @param BuildDatabase: The database saves all data for all metafiles
58#  @param Arch: Current arch
59#  @param Target: Current target
60#  @param Toolchain: Current toolchain
61#  @retval: List of dependent libraries which are InfBuildData instances
62#
63def GetLiabraryInstances(Module, Platform, BuildDatabase, Arch, Target, Toolchain):
64    if Module.AutoGenVersion >= 0x00010005:
65        return _GetModuleLibraryInstances(Module, Platform, BuildDatabase, Arch, Target, Toolchain)
66    else:
67        return _ResolveLibraryReference(Module, Platform)
68
69def _GetModuleLibraryInstances(Module, Platform, BuildDatabase, Arch, Target, Toolchain):
70    ModuleType = Module.ModuleType
71
72    # for overriding library instances with module specific setting
73    PlatformModule = Platform.Modules[str(Module)]
74
75    # add forced library instances (specified under LibraryClasses sections)
76    #
77    # If a module has a MODULE_TYPE of USER_DEFINED,
78    # do not link in NULL library class instances from the global [LibraryClasses.*] sections.
79    #
80    if Module.ModuleType != SUP_MODULE_USER_DEFINED:
81        for LibraryClass in Platform.LibraryClasses.GetKeys():
82            if LibraryClass.startswith("NULL") and Platform.LibraryClasses[LibraryClass, Module.ModuleType]:
83                Module.LibraryClasses[LibraryClass] = Platform.LibraryClasses[LibraryClass, Module.ModuleType]
84
85    # add forced library instances (specified in module overrides)
86    for LibraryClass in PlatformModule.LibraryClasses:
87        if LibraryClass.startswith("NULL"):
88            Module.LibraryClasses[LibraryClass] = PlatformModule.LibraryClasses[LibraryClass]
89
90    # EdkII module
91    LibraryConsumerList = [Module]
92    Constructor = []
93    ConsumedByList = sdict()
94    LibraryInstance = sdict()
95
96    while len(LibraryConsumerList) > 0:
97        M = LibraryConsumerList.pop()
98        for LibraryClassName in M.LibraryClasses:
99            if LibraryClassName not in LibraryInstance:
100                # override library instance for this module
101                if LibraryClassName in PlatformModule.LibraryClasses:
102                    LibraryPath = PlatformModule.LibraryClasses[LibraryClassName]
103                else:
104                    LibraryPath = Platform.LibraryClasses[LibraryClassName, ModuleType]
105                if LibraryPath == None or LibraryPath == "":
106                    LibraryPath = M.LibraryClasses[LibraryClassName]
107                    if LibraryPath == None or LibraryPath == "":
108                        return []
109
110                LibraryModule = BuildDatabase[LibraryPath, Arch, Target, Toolchain]
111                # for those forced library instance (NULL library), add a fake library class
112                if LibraryClassName.startswith("NULL"):
113                    LibraryModule.LibraryClass.append(LibraryClassObject(LibraryClassName, [ModuleType]))
114                elif LibraryModule.LibraryClass == None \
115                     or len(LibraryModule.LibraryClass) == 0 \
116                     or (ModuleType != 'USER_DEFINED'
117                         and ModuleType not in LibraryModule.LibraryClass[0].SupModList):
118                    # only USER_DEFINED can link against any library instance despite of its SupModList
119                    return []
120
121                LibraryInstance[LibraryClassName] = LibraryModule
122                LibraryConsumerList.append(LibraryModule)
123            else:
124                LibraryModule = LibraryInstance[LibraryClassName]
125
126            if LibraryModule == None:
127                continue
128
129            if LibraryModule.ConstructorList != [] and LibraryModule not in Constructor:
130                Constructor.append(LibraryModule)
131
132            if LibraryModule not in ConsumedByList:
133                ConsumedByList[LibraryModule] = []
134            # don't add current module itself to consumer list
135            if M != Module:
136                if M in ConsumedByList[LibraryModule]:
137                    continue
138                ConsumedByList[LibraryModule].append(M)
139    #
140    # Initialize the sorted output list to the empty set
141    #
142    SortedLibraryList = []
143    #
144    # Q <- Set of all nodes with no incoming edges
145    #
146    LibraryList = [] #LibraryInstance.values()
147    Q = []
148    for LibraryClassName in LibraryInstance:
149        M = LibraryInstance[LibraryClassName]
150        LibraryList.append(M)
151        if ConsumedByList[M] == []:
152            Q.append(M)
153
154    #
155    # start the  DAG algorithm
156    #
157    while True:
158        EdgeRemoved = True
159        while Q == [] and EdgeRemoved:
160            EdgeRemoved = False
161            # for each node Item with a Constructor
162            for Item in LibraryList:
163                if Item not in Constructor:
164                    continue
165                # for each Node without a constructor with an edge e from Item to Node
166                for Node in ConsumedByList[Item]:
167                    if Node in Constructor:
168                        continue
169                    # remove edge e from the graph if Node has no constructor
170                    ConsumedByList[Item].remove(Node)
171                    EdgeRemoved = True
172                    if ConsumedByList[Item] == []:
173                        # insert Item into Q
174                        Q.insert(0, Item)
175                        break
176                if Q != []:
177                    break
178        # DAG is done if there's no more incoming edge for all nodes
179        if Q == []:
180            break
181
182        # remove node from Q
183        Node = Q.pop()
184        # output Node
185        SortedLibraryList.append(Node)
186
187        # for each node Item with an edge e from Node to Item do
188        for Item in LibraryList:
189            if Node not in ConsumedByList[Item]:
190                continue
191            # remove edge e from the graph
192            ConsumedByList[Item].remove(Node)
193
194            if ConsumedByList[Item] != []:
195                continue
196            # insert Item into Q, if Item has no other incoming edges
197            Q.insert(0, Item)
198
199    #
200    # if any remaining node Item in the graph has a constructor and an incoming edge, then the graph has a cycle
201    #
202    for Item in LibraryList:
203        if ConsumedByList[Item] != [] and Item in Constructor and len(Constructor) > 1:
204            return []
205        if Item not in SortedLibraryList:
206            SortedLibraryList.append(Item)
207
208    #
209    # Build the list of constructor and destructir names
210    # The DAG Topo sort produces the destructor order, so the list of constructors must generated in the reverse order
211    #
212    SortedLibraryList.reverse()
213    return SortedLibraryList
214
215def _ResolveLibraryReference(Module, Platform):
216    LibraryConsumerList = [Module]
217
218    # "CompilerStub" is a must for Edk modules
219    if Module.Libraries:
220        Module.Libraries.append("CompilerStub")
221    LibraryList = []
222    while len(LibraryConsumerList) > 0:
223        M = LibraryConsumerList.pop()
224        for LibraryName in M.Libraries:
225            Library = Platform.LibraryClasses[LibraryName, ':dummy:']
226            if Library == None:
227                for Key in Platform.LibraryClasses.data.keys():
228                    if LibraryName.upper() == Key.upper():
229                        Library = Platform.LibraryClasses[Key, ':dummy:']
230                        break
231                if Library == None:
232                    continue
233
234            if Library not in LibraryList:
235                LibraryList.append(Library)
236                LibraryConsumerList.append(Library)
237    return LibraryList
238