Fixed DAG algorithm hole in re-ordering library instances of a module, if there's...

git-svn-id: https://buildtools.tianocore.org/svn/buildtools/trunk/BaseTools@1117 7335b38e-4728-0410-8992-fb3ffe349368

diff --git a/Source/Python/Workspace/WorkspaceDatabase.py b/Source/Python/Workspace/WorkspaceDatabase.py
index f2ba531..f9cf137 100644 (file)
--- a/Source/Python/Workspace/WorkspaceDatabase.py
+++ b/Source/Python/Workspace/WorkspaceDatabase.py
@@ -383,72 +383,60 @@ class DscBuildData(PlatformBuildClassObject):
                                     )\r
             if ConsumedByList[M] == []:\r
                 Q.insert(0, M)\r
+\r
         #\r
-        # while Q is not empty do\r
+        # start the  DAG algorithm\r
         #\r
-        while Q != []:\r
-            #\r
+        while True:\r
+            EdgeRemoved = True\r
+            while Q == [] and EdgeRemoved:\r
+                EdgeRemoved = False\r
+                # for each node Item with a Constructor\r
+                for Item in LibraryList:\r
+                    if Item not in Constructor:\r
+                        continue\r
+                    # for each Node without a constructor with an edge e from Item to Node\r
+                    for Node in ConsumedByList[Item]:\r
+                        if Node in Constructor:\r
+                            continue\r
+                        # remove edge e from the graph if Node has no constructor\r
+                        ConsumedByList[Item].remove(Node)\r
+                        EdgeRemoved = True\r
+                        if ConsumedByList[Item] == []:\r
+                            # insert Item into Q\r
+                            Q.insert(0, Item)\r
+                            break\r
+                    if Q != []:\r
+                        break\r
+            # DAG is done if there's no more incoming edge for all nodes\r
+            if Q == []:\r
+                break\r
+\r
             # remove node from Q\r
-            #\r
             Node = Q.pop()\r
-            #\r
             # output Node\r
-            #\r
             SortedLibraryList.append(Node)\r
-            #\r
+\r
             # for each node Item with an edge e from Node to Item do\r
-            #\r
             for Item in LibraryList:\r
                 if Node not in ConsumedByList[Item]:\r
                     continue\r
-                #\r
                 # remove edge e from the graph\r
-                #\r
                 ConsumedByList[Item].remove(Node)\r
-                #\r
-                # If Item has no other incoming edges then\r
-                #\r
-                if ConsumedByList[Item] == []:\r
-                    #\r
-                    # insert Item into Q\r
-                    #\r
-                    Q.insert(0, Item)\r
 \r
-            EdgeRemoved = True\r
-            while Q == [] and EdgeRemoved:\r
-                EdgeRemoved = False\r
-                #\r
-                # for each node Item with a Constructor\r
-                #\r
-                for Item in LibraryList:\r
-                    if Item in Constructor:\r
-                        #\r
-                        # for each Node without a constructor with an edge e from Item to Node\r
-                        #\r
-                        for Node in ConsumedByList[Item]:\r
-                            if Node not in Constructor:\r
-                                #\r
-                                # remove edge e from the graph\r
-                                #\r
-                                ConsumedByList[Item].remove(Node)\r
-                                EdgeRemoved = True\r
-                                if ConsumedByList[Item] == []:\r
-                                    #\r
-                                    # insert Item into Q\r
-                                    #\r
-                                    Q.insert(0, Item)\r
-                                    break\r
-                    if Q != []:\r
-                        break\r
+                if ConsumedByList[Item] != []:\r
+                    continue\r
+                # insert Item into Q, if Item has no other incoming edges\r
+                Q.insert(0, Item)\r
 \r
         #\r
         # if any remaining node Item in the graph has a constructor and an incoming edge, then the graph has a cycle\r
         #\r
         for Item in LibraryList:\r
             if ConsumedByList[Item] != [] and Item in Constructor and len(Constructor) > 1:\r
-                ErrorMessage = 'Library [%s] with constructors has a cycle' % str(Item)\r
-                EdkLogger.error("AutoGen", AUTOGEN_ERROR, ErrorMessage,\r
-                                "\tconsumed by " + "\n\tconsumed by ".join([str(L) for L in ConsumedByList[Item]]))\r
+                ErrorMessage = "\tconsumed by " + "\n\tconsumed by ".join([str(L) for L in ConsumedByList[Item]])\r
+                EdkLogger.error("build", AUTOGEN_ERROR, 'Library [%s] with constructors has a cycle' % str(Item),\r
+                                ExtraData=ErrorMessage)\r
             if Item not in SortedLibraryList:\r
                 SortedLibraryList.append(Item)\r
 \r