跳到主要內容

Resolve cycle

Resolve cycle#

之前用 astroid 寫的 tool pydependency， 將 dependency graph 匯出成 .dot 或是一些 .json 格式後， 就有幾個方便的 tool 可以來分析了。

以下的故事基本上都是在分析 junyi-academy 的 code，但大部分的壞味道，從 khan-academy 時代就有了。如果只看 dependency graph 沒感覺的話，也可以載 source code 來看看。

graph tools#

graphviz#

graphviz 為老牌的 graph 視覺化工具。 pylint 的內含的工具 pyreverse 就是拿 graphviz 來畫 UML 的圖的。好處就是簡單好上手，畫出第一張圖：

echo "digraph { hello->world }" | dot -Tpng -o dot.png

強大之處在於其 layout 演算法，但是如果 cycle 很多，畫出來就會全部結成一團， 也不知道能怎麼調整。

python 部分套件可以安裝 pygraphviz 或 pydot，讀寫 dot 會方便些。

pygraphviz 包裝原生 graphviz library 的 C api 到 python 中，所以對於 agraph 的操作是直接對應到 C 的 data structure 的。

而 pydot 對於 graph 的操作都還是在 python 當中。直到要找 graphviz tool 時， 才利用其中的 parser 作資料的轉換。

兩個在 layout/draw 時，都還是直接用 subprocess.Popen 呼叫 graphviz 的 command line tools。pygraphviz 也沒有因為直接呼叫 C，而直接用像 gvToolTred 這樣的 function。還是多了一層 serialize、deserialize 及 pipe。 在 tred 或是 layout (只需要多標上 position？) 這樣的功能上，感覺滿慘的。

tred 是一個 graphviz 的 transitive reduction tool。 比方說，一張圖長這樣：

di-graph

會被 tred 轉成

tred

如果沒有 cycle 的話，圖會在不影響 dependency 先後順序的情況下變得乾淨一點。 比較好做一些觀察。

不過如果有 cycle 的話，結果不會是唯一的。 例如 A->B->C; A->C; B->A 與 B->A; A->B->C; A->C 的結果就會不一樣。 猜測就是 graphviz 用 dfs 爬的順序來隨便決定是哪一個，先走到 B 就會把 B->C 拿掉，而先走到 A 的話，就會把 A->C 拿掉。

中間還踩到一個 pygraphviz 1.3.1 的 issue ，在有 cycle 時，會出現 warning，然後因為 data type 的關係，就丟出 exception 了...

networkx#

networkx 為 python 的 network (graph) 分析工具。可以把任何在 python 中有 hash 的 object 串接起來變成 graph。有內建很多演算法可以用。

視覺化的部分可接到 matplotlib 來呈現。也有 graphviz 的 plugin，可轉成 graphviz 來用 graphviz 的強大 layout engine。

graphviz 的轉接要多安裝 pygraphviz 或 pydot 然後透過 nx.nx_agraph 或是 nx.nx_pydot 來接到 graphviz。

兩個 module 都是在用到時才會嘗試 import，因此應該裝一個即可， 轉換的過程基本上就是讀舊的然後用新的 api 生成另一個 type 的 graph，因為兩邊 spec 不全相同，因此會有少一些東西，因此建議都在 networkx 上來做操作， 直到要 layout、draw 時再來考慮轉換。

cytoscape.js#

cytoscape 是一個生物資訊軟體，cytoscape.js 是它 js 版本。 在 js 中直接對 graph 做操作，並用 html5 canvas 來呈現視覺化效果。

比起 d3，可以不用管很多細節的部分，比較著重於 node、edge 的操作。 整個 API 很 jquery style，用類似的 selector 概念來選擇 node 上 style， 非常易於使用，調整一些簡單的 style 與做一些簡單的互動非常方便。

第一次用這來畫出 dependency graph 時真是嚇到了，看起來太複雜，不太有用。

cy_all_modules

這是用 concentric layout，並把 out degree 高的放在中間， 唯一有用的資訊只有中間是 main 與 api.v1，兩個的 out degree 最大。

如果改成 breadthfirst，由 main 做 root，可能是因為 cycle 太多， 計算是那一層的沒有辦法很準。全部排起來只有 6 層，中間穿插的情況很嚴重，也都看不清楚。

cose layout 會跑很久，畫起來就是一大坨，也是非常不好看。 需要找一些其他的指標來呈現才行。

Reduce nodes#

先簡化一下圖，要考慮的只有 cycle，先把不在 cycle 中的 node 拿掉。 無腦暴力做法，把所有 indegree、outdegree 為零的 node 拿掉。 這些並不可能是 cycle 的一部份。拿掉之後又可能會有一些 node 沒有 indegree、outdegree 就這樣拿到這些 node 都不見為止。

接著利用 graphviz dot 並設定 rankdir="LR" 來排，再將座標一起匯出成給 cytoscape 的 json 格式。

import networkx as nx
g = nx.nx_agraph.read_dot(sys.argv[1])
g = nx.DiGraph(g)
...

a = nx.nx_agraph.to_agraph(graph)
a.layout(prog='dot')

eles = []
for n in agraph.nodes_iter():
    node_data = {'id': str(n)}
    pos = tuple(map(float, n.attr['pos'].split(',')))
    pos = (pos[0] / 4, pos[1] / 2)
    eles.append({'group': 'nodes', 'data': node_data, 'position': {'x': pos[0], 'y': pos[1]}})

for e in agraph.edges_iter():
    eles.append({'group': 'edges', 'data': {'source': e[0], 'target': e[1]}})

再把從右到左的 link 標成紅色的，並手動的整理一下，

cy_removed

package "badges"#

分幾個群來看，只看 badges 內部的話，其實滿好的，可以直接分成大概 4 層

  1. models_badges database model 的定義。
  2. badges 定義所有 badges 的 abstract base class。 topic_badges、exercise_badges，一樣是 abstract class 的定義。
  3. 其他除了 util_badges 外的 module，真正的定義都放在這邊。

  4. util_badges 將所有實現的 badge modules 都 import 進來，應該為整個 package 對外的單一窗口。

     cy_all_modules.$(':selected').unselect();
 (els => {
     els.select();
     console.log(els.indegree());
     els.incomers('node').each(e=>console.log(e.id()));
 })(cy_all_modules.$id('badges.util_badges'));

    可得知有 12 個 module 會連到 util_badges，

整個 badges 的矛盾來自於 class_time 與 video_models 的矛盾。

classtime-video_models

add_entry()->commit_log_summary_coaches()->ClassDailyActivitySummary->VideoLog 這條路徑是 cycle 的主因。但很類似的 attempt_problem()->commit_log_summary_coaches()->ClassDailyActivitySummary->ProblemLog 則沒有問題。

在 exercise 部分的處理，bussiness layer 與 data access layer 兩塊是拆切開來的； 而 video 部分則是沒有區分 bussiness 與 data access layer，全部分在同一個 module 當中，這樣自然當中間的 bussiness logic 想要拆切出去時，必須要考慮在這時分家。 不然就會造成 circular dependency 了。這隻的 caller 也都只有 api 介面及 unittest， 不要動太大的話，將 add_entry 拆切出去即可移除 cycle。

看起來好像只是小惡，沒什麼關係是吧？為什麼要做這樣的 refactoring？不是還可以動嗎？ python 不是支援 circular import 嗎？

如果在 code 中，只寫了：

import badges.util_badges

就會噴出 exception

  File "./badges/util_badges.py", line 16, in <module>
    import badges
  File "./badges/badges.py", line 4, in <module>
    import models_badges
  File "./badges/models_badges.py", line 9, in <module>
    import util
  File "./util.py", line 1, in <module>
    import auth.cookies
  File "./auth/cookies.py", line 5, in <module>
    import user_models
  File "./user_models.py", line 39, in <module>
    import goals.models
  File "./goals/models.py", line 9, in <module>
    import exercise_models
  File "./exercise_models.py", line 39, in <module>
    from exercises import file_contents, stacks
  File "./exercises/stacks.py", line 5, in <module>
    import custom_stack_model
  File "./custom_stack_model.py", line 11, in <module>
    import topic_models
  File "./topic_models.py", line 31, in <module>
    import autocomplete
  File "./autocomplete.py", line 3, in <module>
    import video_models
  File "./video_models.py", line 34, in <module>
    import classtime
  File "./classtime.py", line 12, in <module>
    import profiles.activity_graph as activity_graph
  File "./profiles/activity_graph.py", line 7, in <module>
    from badges import models_badges, util_badges
ImportError: cannot import name models_badges

但是如果是：

import utils
import badges.util_badges

就會很神奇的沒事了。其實不管是先 import util、user_models、topic_models、 classtime 都會沒事。原因跟 from ... import 的寫法有關， 詳細可以參考之前的筆記 python import 。

因此，如果不想要發生：

  1. 移除 unused import 後，發現跑不起來。
  2. 改用 explicit relative import 後，發現跑不起來。
  3. 改用 absolute import 後，發現跑不起來。
  4. 修改了 import 順序後，發現跑不起來。

我想還是好好設計不要有 cycle 可能會比較簡單一點。這些聽起來都非常容易的發生， 等到發生時才來 refactoring 應該是更麻煩的事。

package "gandalf"#

gandalf 內部看起來也沒問題。gandalf.bridge 是一個開放給 bussiness layer 的有點像 AB-test 控管的東西入口，應該是這個 package 中， 唯一對外開放的 interface。

而 package 出口 gandalf.config，則指向了 user_models，乍看之下由 bussiness layer 指向 data access layer 好像不是什麼問題，但就一樣壞在 user_models 中，包含了 bussiness layer 與 data access layer 的責任， 因此又會指向其他的 bussiness layer，然後就回到 gandalf.bridge 這個入口了。

user_models 與 topic_models 看起來就是大部分問題中心， 在應該沒有簡單的搬移就可以馬上解決掉的好事。需要觀察更多跟他們相關的責任， 才知道要怎麼拆切會比較好。因此先來釐清 gandalf 的需求：

  1. get information about current user
  2. check current user is administrator or not

整個 package 特性應該跟 authorization 類型的 model 滿像的，之後跟其他同類型的一起討論。

"auth" modules#

不像上面兩個 package，auth 部分抽出來看就已經很混亂了。再加上 user_models、 nicknames、phantom_users 一起看的話，這根本是一個大坑。

發生 cycle 的部分，python 已經無法容忍，需要出一些怪招，才能繼續維持著這個恐怖平衡。 api/auth/auth_models.py 中，開始將 from ... import ... 寫在 file 的最後面，避免因 cycle 而導致 import 失敗。這樣寫取決於兩個 module import 及定義的順序，以及 function 中的 global 是在 run time 才 dereference 等特性。

如果什麼都不看，從頭想的話，應該會架構成這樣：

graphviz-6

中間因為希望能加入不同的 authentication provider，因此需要一個 extension 的機制， 做個 reverse dependency ，希望 extension 的邏輯能與其他東西分離，方便擴充。 不過同樣的 presentation layer 也可能需要建立一個 extension 機制才行。 到底要打穿到什麼程度，extension 的機制需要存在於每一個 layer 嗎？ 這就需要看中間的邏輯跟 auth 嵌多深了。

事與願違，api.auth.auth_models 中的 OAuthMap 就已經把 google、facebook 這樣的 name 直接寫在裡面了。一旦進入了 data access layer，要改動就很麻煩了。 如把這些 provider 的邏輯加入到這麼底層，除非將 provider 的 code 也拆切成不同 layer， 不然又注定要 cycle 了。還是先放棄 extension 機制，先確定 cycle 的問題可以解決。

TODO

  • util 被很多 data access layer 的連到，而 util 又會回到 api.auth.auth_util 等。其實 util 中的 auth 完全可以拆出去，因為這些相關 function 的 caller 其實很集中，其他人並沒有需要。
  • def current() 中有 cycle 須將 current user 的責任移出 user_models
  • user_util 與 api.auth.decorator 的分別? 一個給 falsk api，一個給 gae? user_util 中大致可以分三類，role util、auth decorator、???。

    "???" 的部分，就是造成 cycle 的來源，因 user_models.UserData.get_from_username_or_email 竟然去呼叫 user_util.get_possibly_current_user。

    乍看之下毫無關聯，get_from_username_or_email 像是一個 selector， 輸入的東西可能是 username 或是 email，然後希望取得一個 user 的 structure。 但原罪可能就是在 user 的資料很混亂，如果輸入的是 email，有可能是重複的...

    因此這邊的神邏輯就是先看看 current user，如果 current user 就已經滿足這個 selector，就直接 return current user 了。而如果沒滿足，才真的下 db query 去用 username 或是 email 去找看看。

    (看到 "possible"、"possibly" 頭就有點痛。這種字都有感染性，一旦有一隻在 最底層，caller 每一個都會是 "possibly"，possibly work。)

    只要將 get_possibly_current_user 搬到 user_models 當中，即可解決 cycle。 但這樣的搬移前提是建立在 current user 的責任是在 user_models 當中。

  • user_models 中的 phantom_users.phantom_util.is_phantom_id 只 import phantom_users 會 work? @@
  • user_models 中，import phantom_users，乍看之下只有 import package， 所以沒有 cycle。但仔細一看，發現都直接去 reference phatom_users.XXX， 這表示在 import user_models 之前，或是呼叫這些 function 之前， 一定要有一個地方有 import 過這些 XXX，不然呼叫下去就會找不到...

    最可怕的是這種東西 pylint 沒有抓...

    這種避開 cycle 的方法也真是太絕了...

  • topic_models

  • https://i11www.iti.kit.edu/_media/teaching/sommer2004/networkdrawing/spring.pdf
  • https://www.researchgate.net/publication/282504460_A_Decision_Support_System_to_Refactor_Class_Cycles
  • principle

ref:

標籤：

留言

張貼留言

這個網誌中的熱門文章

Blogger tool

Blogger tool # 不懂為什麼，對於所見即所得的編輯器不太會用（少了 vim 加持??） 直接寫 html 又太痛苦。那要寫 markdown 嗎？ 希望在文件中方便插入 code、流程圖等。 找其他 blog？就只是記記東西還要去找，有點懶。 如果透過 markdown tool，再貼到 blogger，html tag 很髒，有些東西也可能會跑掉。 目前 markdown 也不符合需求，需要小改。未來如果不滿意，還是可以隨時調整。 因此就決定自己 render 然後推上 blogger。 How to push posts # 1. 申請一個 app id/secret # 不知道有沒有別的申請方法，目前是直接登入 console.cloud.google.com 來申請。 然後隨便找一個 project (這樣對嗎？邏輯上這樣比較像是要把存取 blogger 的權限放到這個 web application 當中一樣。但其實暫時還只打算先跑 CLI)。 先把 blogger API 打開，然後到 "API 和服務" > "憑證" 去建立。 申請過程中會問一下是要幹什麼用的，還有填個 app 的名字， 然後就可以下載 client_id.json 裡面帶有 api id/secret 了。 如果弄丟了，或要修改，之後也可回到這個頁面當中做後續的維護動作。 2. install API client # 沒有其實也可以啦，手動打 REST API 而已。只是有好像比較方便一些。 python 版 pip install --upgrade google-api-python-client nodejs 版 (alpha) npm install googleapis --save 最後選用了 nodejs，因為 python-markdown 出來的結果不是很滿意 （另一個 misaka 沒試過） ， marked 之前用起來感覺還不錯。只用同一種 language 之後在修改時應該比較方便擴充。 3. get access token # 因為需要操作 ...
張貼留言
閱讀完整內容

Python - import

Python - import # 當 code 變多，需要更好的整理和封裝，因此 python 提供了 package、module 的功能， 及 import 的語法來調用這些包裝好的元件。 python 中，一個 .py 的檔案即為一個 module。而存放 module 的目錄，則稱為一個 package。 在 import 過程中，module 會被編譯、執行，並在 import 後， 被放入 caller 的 local symbol table 當中。 之後可透過 module.symbol 來調用這個 module 下的 symbol。 如此簡單、似是而非的描述，距離實際上實作細節還很遙遠。 在深入一個個機制之前，先列一下希望能回答的問題。 package 與 module 的定義是什麼？有什麼分別嗎？責任的界定是什麼呢？ 傳說在 package 的目錄當中，必須要有一個 __init__.py 的存在？這是做什麼用的？ 我的 python interpreter 去哪邊找 package 的，什麼是 sys.path ？ 這些package、module 是一個物件嗎？是的話他們的生命週期是怎樣呢？ 會不會有 circular import 的發生？有什麼限制？ import 的基本語法 # 在 python3 - module (or python2 - module ) 中，介紹得滿清楚的。複習一下這些內容： import mod 最簡單的型式，找到 module 後，在 local symbol table 中建立 (bind) 名為 mod 的變數，reference 到 module mod 。 import pkg.mod 找到 package pkg 後，找到 module mod ，在 local symbol table 中建立 pkg 。之後可以透過 pkg.mod.X 去調用下面的東西。 import pkg.mod as mod 匯入後改變在 local symbol table 中的名稱。在 pkg.mod import 後，可用 mod 去存取。 from pkg import mod 、 fro...
張貼留言
閱讀完整內容