[PATCH v1 08/11] BaseTools: refactor to change object types

[Jaben Carsey <jaben.carsey@intel.com>]

change to object types that are closer to use case.  for example:
when using a list as a double ended queue, use the built in object.

Cc: Liming Gao <liming.gao@intel.com>
Cc: Yonghong Zhu <yonghong.zhu@intel.com>
Contributed-under: TianoCore Contribution Agreement 1.1
Signed-off-by: Jaben Carsey <jaben.carsey@intel.com>
---
 BaseTools/Source/Python/AutoGen/AutoGen.py           | 30 +++++++++++---------
 BaseTools/Source/Python/GenFds/FdfParser.py          |  5 ++--
 BaseTools/Source/Python/Workspace/WorkspaceCommon.py | 20 ++++++-------
 3 files changed, 29 insertions(+), 26 deletions(-)

diff --git a/BaseTools/Source/Python/AutoGen/AutoGen.py b/BaseTools/Source/Python/AutoGen/AutoGen.py
index 009e5c56781d..599331060187 100644
--- a/BaseTools/Source/Python/AutoGen/AutoGen.py
+++ b/BaseTools/Source/Python/AutoGen/AutoGen.py
@@ -45,10 +45,14 @@ import InfSectionParser
 import datetime
 import hashlib
 from GenVar import VariableMgr,var_info
-from collections import OrderedDict
-from collections import defaultdict
+from collections import OrderedDict,defaultdict,deque
 from abc import ABCMeta, abstractmethod
 
+class OrderedListDict(OrderedDict, defaultdict):
+    def __init__(self, *args, **kwargs):
+        super(OrderedListDict, self).__init__(*args, **kwargs)
+        self.default_factory = list
+
 ## Regular expression for splitting Dependency Expression string into tokens
 gDepexTokenPattern = re.compile("(\(|\)|\w+| \S+\.inf)")
 
@@ -2172,8 +2176,8 @@ class PlatformAutoGen(AutoGen):
 
         # EdkII module
         LibraryConsumerList = [Module]
-        Constructor         = []
-        ConsumedByList      = OrderedDict()
+        Constructor         = set()
+        ConsumedByList = OrderedListDict()
         LibraryInstance     = OrderedDict()
 
         EdkLogger.verbose("")
@@ -2219,10 +2223,8 @@ class PlatformAutoGen(AutoGen):
                     continue
 
                 if LibraryModule.ConstructorList != [] and LibraryModule not in Constructor:
-                    Constructor.append(LibraryModule)
+                    Constructor.add(LibraryModule)
 
-                if LibraryModule not in ConsumedByList:
-                    ConsumedByList[LibraryModule] = []
                 # don't add current module itself to consumer list
                 if M != Module:
                     if M in ConsumedByList[LibraryModule]:
@@ -2235,8 +2237,8 @@ class PlatformAutoGen(AutoGen):
         #
         # Q <- Set of all nodes with no incoming edges
         #
-        LibraryList = [] #LibraryInstance.values()
-        Q = []
+        LibraryList = []
+        Q = deque()
         for LibraryClassName in LibraryInstance:
             M = LibraryInstance[LibraryClassName]
             LibraryList.append(M)
@@ -2248,7 +2250,7 @@ class PlatformAutoGen(AutoGen):
         #
         while True:
             EdgeRemoved = True
-            while Q == [] and EdgeRemoved:
+            while not Q and EdgeRemoved:
                 EdgeRemoved = False
                 # for each node Item with a Constructor
                 for Item in LibraryList:
@@ -2263,12 +2265,12 @@ class PlatformAutoGen(AutoGen):
                         EdgeRemoved = True
                         if ConsumedByList[Item] == []:
                             # insert Item into Q
-                            Q.insert(0, Item)
+                            Q.appendleft(Item)
                             break
-                    if Q != []:
+                    if Q:
                         break
             # DAG is done if there's no more incoming edge for all nodes
-            if Q == []:
+            if not Q:
                 break
 
             # remove node from Q
@@ -2286,7 +2288,7 @@ class PlatformAutoGen(AutoGen):
                 if ConsumedByList[Item] != []:
                     continue
                 # insert Item into Q, if Item has no other incoming edges
-                Q.insert(0, Item)
+                Q.appendleft(Item)
 
         #
         # if any remaining node Item in the graph has a constructor and an incoming edge, then the graph has a cycle
diff --git a/BaseTools/Source/Python/GenFds/FdfParser.py b/BaseTools/Source/Python/GenFds/FdfParser.py
index 8d1a4b543f0e..d511cf4f9d5a 100644
--- a/BaseTools/Source/Python/GenFds/FdfParser.py
+++ b/BaseTools/Source/Python/GenFds/FdfParser.py
@@ -43,6 +43,7 @@ import OptionRom
 import OptRomInfStatement
 import OptRomFileStatement
 import string
+from collections import deque
 
 from GenFdsGlobalVariable import GenFdsGlobalVariable
 from Common.BuildToolError import *
@@ -89,7 +90,7 @@ BaseAddrValuePattern = re.compile('^0[xX][0-9a-fA-F]+')
 FileExtensionPattern = re.compile(r'([a-zA-Z][a-zA-Z0-9]*)')
 TokenFindPattern = re.compile(r'([a-zA-Z0-9\-]+|\$\(TARGET\)|\*)_([a-zA-Z0-9\-]+|\$\(TOOL_CHAIN_TAG\)|\*)_([a-zA-Z0-9\-]+|\$\(ARCH\)|\*)')
 
-AllIncludeFileList = []
+AllIncludeFileList = deque()
 
 # Get the closest parent
 def GetParentAtLine (Line):
@@ -685,7 +686,7 @@ class FdfParser:
                     InsertAtLine += 1
 
                 # reversely sorted to better determine error in file
-                AllIncludeFileList.insert(0, IncFileProfile)
+                AllIncludeFileList.appendleft(IncFileProfile)
 
                 # comment out the processed include file statement
                 TempList = list(self.Profile.FileLinesList[IncludeLine - 1])
diff --git a/BaseTools/Source/Python/Workspace/WorkspaceCommon.py b/BaseTools/Source/Python/Workspace/WorkspaceCommon.py
index 573100081815..a793055b6d18 100644
--- a/BaseTools/Source/Python/Workspace/WorkspaceCommon.py
+++ b/BaseTools/Source/Python/Workspace/WorkspaceCommon.py
@@ -11,7 +11,7 @@
 # WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
 #
 
-from collections import OrderedDict, defaultdict
+from collections import OrderedDict, defaultdict, deque
 from Common.DataType import SUP_MODULE_USER_DEFINED
 from BuildClassObject import LibraryClassObject
 import Common.GlobalData as GlobalData
@@ -110,7 +110,7 @@ def _GetModuleLibraryInstances(Module, Platform, BuildDatabase, Arch, Target, To
 
     # EdkII module
     LibraryConsumerList = [Module]
-    Constructor = []
+    Constructor = set()
     ConsumedByList = OrderedListDict()
     LibraryInstance = OrderedDict()
 
@@ -148,7 +148,7 @@ def _GetModuleLibraryInstances(Module, Platform, BuildDatabase, Arch, Target, To
                 continue
 
             if LibraryModule.ConstructorList != [] and LibraryModule not in Constructor:
-                Constructor.append(LibraryModule)
+                Constructor.add(LibraryModule)
 
             # don't add current module itself to consumer list
             if M != Module:
@@ -162,8 +162,8 @@ def _GetModuleLibraryInstances(Module, Platform, BuildDatabase, Arch, Target, To
     #
     # Q <- Set of all nodes with no incoming edges
     #
-    LibraryList = [] #LibraryInstance.values()
-    Q = []
+    LibraryList = []
+    Q = deque()
     for LibraryClassName in LibraryInstance:
         M = LibraryInstance[LibraryClassName]
         LibraryList.append(M)
@@ -175,7 +175,7 @@ def _GetModuleLibraryInstances(Module, Platform, BuildDatabase, Arch, Target, To
     #
     while True:
         EdgeRemoved = True
-        while Q == [] and EdgeRemoved:
+        while not Q and EdgeRemoved:
             EdgeRemoved = False
             # for each node Item with a Constructor
             for Item in LibraryList:
@@ -190,12 +190,12 @@ def _GetModuleLibraryInstances(Module, Platform, BuildDatabase, Arch, Target, To
                     EdgeRemoved = True
                     if len(ConsumedByList[Item]) == 0:
                         # insert Item into Q
-                        Q.insert(0, Item)
+                        Q.appendleft(Item)
                         break
-                if Q != []:
+                if Q:
                     break
         # DAG is done if there's no more incoming edge for all nodes
-        if Q == []:
+        if not Q:
             break
 
         # remove node from Q
@@ -213,7 +213,7 @@ def _GetModuleLibraryInstances(Module, Platform, BuildDatabase, Arch, Target, To
             if len(ConsumedByList[Item]) != 0:
                 continue
             # insert Item into Q, if Item has no other incoming edges
-            Q.insert(0, Item)
+            Q.appendleft(Item)
 
     #
     # if any remaining node Item in the graph has a constructor and an incoming edge, then the graph has a cycle
-- 
2.16.2.windows.1