更多相依性處理解析¶
本文詳細說明關於 PIP 的相依性處理解析演算法。在某些情況下，PIP 可能會需要花很長的時間來判斷要安裝什麼，而本文旨在幫助讀者瞭解該過程中在「幕後」發生的情況。
注意
本文檔仍在制定中。內文所含的詳細資訊是正確的（於撰寫時），但其中有額外的資訊，特別是 PIP 與 resolvelib 的介面，尚未收錄在內。
歡迎提出改善此文件檔的意見。
相依性處理解析問題¶
在給定一組套件間的相依性條件後，找到一組要安裝的套件，是已知的 NP 難題。其在實際用途中的意義大致上是指，此程序會隨著問題規模的增加而呈極端程度的擴充。因此，當你擁有大量的相依性時，求出要安裝什麼，在最壞的情況下，會花上非常長一段時間。
實際的影響是，在某些情況下，PIP 無法在合理的時間內判斷要安裝什麼。我們盡一切努力，以確保此類情況的發生率很低，但從理論上來說要完全消除它們是不可能的。我們稍後將討論，如果你遇到了此類問題狀況，有哪些應對選擇。
Python 特有的問題¶
許多處理相依性解析的演算法都假設一開始你就已知道此問題中的所有細節，亦即你事先知道所有的相依性。很不幸地，對於 Python 套件來說並非如此。由於目前的套件索引結構，相依性 metadata 僅能透過下載套件檔案，並從其中擷取資料。而在原始碼發行版的情況下，狀況更糟，因為建置專案必須在下載後才能判斷相依性。
我們正在持續努力，希望能以更低的成本讓 metadata 更容易取得，但截至撰寫本文時，此工作尚未完成。
由於下載專案是一項需要付出成本的作業，因此 PIP 無法預先計算完整相依性樹狀圖。這表示我們無法使用多種技術來解決相依性解析問題。實際上，我們必須使用 backtracking 演算法。
相依性 metadata¶
值得討論的是，需要確切的什麼元資料才能驅動套件解析程序。基本上有 3 個關鍵資訊
專案名稱
發行版本
相依性本身
還有其他一些資料（例如附加元件、Python 版本限制、輪子相容性標籤），它們也可以用，但並未從根本上改變程序，因此我們會在這邊忽略它們。
最重要的資訊是專案名稱和版本。那兩個資訊會識別單一的「候選人」進行安裝，且必須唯一識別出該候選人。從候選物件建立的那一刻後，必須提供名稱和版本。這對於配發檔案（sdists 和 wheels）來說不是問題，因為資料可以從檔名取得，但對於未打包的原始碼樹，pip 則需要呼叫建置後端來要求該資料。這是在解析適當開始前就做好的。
相依性資料不是事前要求（如上所述，這麼做會造成價格過高，而且對於回溯演算法來說沒必要）。相反地，pip 在演算法開始檢查特定候選人時，會「按需」要求相依性資料。
延遲擷取相依性資料的一個特別意涵是，通常 pip 不知道在整體上檢視相依性樹時對人來說可能很明顯的事。例如，如果套件 A 相依於套件 B 的版本 1.0，對人來說很明顯的是，查看其他版本套件 B 沒有意義。但是，如果 pip 在考慮 A 之前就開始查看 B，它無法存取 A 的相依性資料，因此無法知道查看其他 B 版本是白費功夫。更糟糕的是，pip 甚至不知道 A 的相依性中有重要資訊。
在 pip 花費很长时间來完成解析的許多情況中，後者都是常見的主題 - 當 pip 做出「錯誤」選擇時，有資訊是 pip 不知道的。加入解析器以引導演算法的大多數啟發法，都旨在在缺乏知識的情況下做出正確的猜測。
解析器和查找器¶
到目前為止，我們一直將「解析器」當作單一實體來討論。雖然大部分都屬實，但從索引取得套件資料的程序由 pip 的另一個元件「查找器」處理。查找器負責將候選人提供給解析器，並且在選擇合適的候選人時扮演要角。
請注意解析器僅與從索引中擷取的套件相關。來自其他來源的候選項目 (本機來源目錄、直接 URL 參照) 不會經過尋找器，並會與尋找器提供的候選項目合併為解析器「提供者」實作的一部分。
除了決定特定專案的索引中存在哪些版本外，尋找器會選擇最適合該候選項要使用的配發檔案。這可能是輪子或來源配發，而精確的選擇標準是由輪子相容性標記、pip 選項 (優先採用二進位或來源) 與索引提供的詮釋資料控制的。特別是，如果標記檔案僅適用於特定 Python 版本，則檔案會被尋找器忽略 (而解析器甚至可能永遠看不到該版本)。
尋找器也會按偏好順序提供候選項目給解析器，例如，提供者會實作規則，較新的版本偏好於舊版本。
解析器演算法¶
解析器本身是基於個別套件 resolvelib。這實作一項抽象回溯解析演算法，其方式獨立於 Python 套件的具體細節—那些具體細節在呼叫解析器之前由 pip 抽象出來。
Pip 的 resolvelib 介面採用「提供者」形式，這是 pip 的套件模型與解析演算法之間的介面。提供者處理「候選項目」和「需求」，並實作下列運算
identify- 實作候選項和需求的身分。例如，這個運算就是實作規則，即候選項目由其名稱和版本標識。get_preference- 這會提供資料給解析器，協助它在執行解析程序時選擇下一個應觀察的「需求」。find_matches- 給定一組約束條件，決定有哪些候選項目能符合這些條件。這基本上就是尋找器與解析器互動之處。is_satisfied_by- 檢查候選項目是否符合需求。這基本上是需求意義的實作。get_dependencies- 取得候選項的依賴性詮釋資料。這是取得並讀取套件詮釋資料的程序實作。
在這些方法中，唯一非平凡的是 get_preference 方法。它實作用於引導解析的啟發法，告訴解析要接著嘗試滿足哪項需求。此方法負責猜測在相依樹中哪條路徑將會是最有生產力的。如上所述，它在資訊有限的情況下進行此作業。請參閱下列圖表
當要求供應商從紅色需求（A->B 及 A->C）中選擇時，它對於 B 或 C 的相依性（例如圖表中灰色部分）一無所知。
Pip 的目前供應商實作會實作 get_preference 如下
偏好任何已知需求為「直接」，例如指向明確的 URL。
如果相等，偏好任何需求「固定」，例如包含運算元
===或==。如果相等，計算近似的「深度」，並優先解析較接近使用者指定需求的需求。
依照指定順序編排使用者指定的順序。
如果相等，偏好「非免費」需求，例如包含至少一個運算元，例如
>=或<。如果相等，基於一致性考量以字母順序排序（有助於除錯）。