)\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