test_fig_scc.py

# Figure 4 of the paper
from byteflow2 import ByteFlow, ByteFlowRenderer, FlowInfo
import logging
# logging.basicConfig(level=logging.DEBUG)


def scc(G):
    preorder = {}
    lowlink = {}
    scc_found = set()
    scc_queue = []
    out = []
    i = 0  # Preorder counter
    for source in G:
        if source not in scc_found:
            queue = [source]
            while queue:
                v = queue[-1]
                if v not in preorder:
                    i = i + 1
                    preorder[v] = i
                done = True
                for w in G[v]:
                    if w not in preorder:
                        queue.append(w)
                        done = False
                        break
                if done:
                    lowlink[v] = preorder[v]
                    for w in G[v]:
                        if w not in scc_found:
                            if preorder[w] > preorder[v]:
                                lowlink[v] = min([lowlink[v], lowlink[w]])
                            else:
                                lowlink[v] = min([lowlink[v], preorder[w]])
                    queue.pop()
                    if lowlink[v] == preorder[v]:
                        scc = {v}
                        while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
                            k = scc_queue.pop()
                            scc.add(k)
                        scc_found.update(scc)
                        out.append(scc)
                    else:
                        scc_queue.append(v)
    return out


def make_flow():
    # flowinfo = FlowInfo()
    import dis
    # fake bytecode just good enough for FlowInfo
    bc = dis.Bytecode(scc)
    flow = FlowInfo.from_bytecode(bc)
    bbmap = flow.build_basicblocks()
    return ByteFlow(bc=bc, bbmap=bbmap)

flow = make_flow()
#ByteFlowRenderer().render_byteflow(flow).view("before")
#
#flow = flow.restructure()
#ByteFlowRenderer().render_byteflow(flow).view("after")
#
#
#flow = ByteFlow.from_bytecode(foo)
ByteFlowRenderer().render_byteflow(flow).view("before")

cflow = flow._join_returns()
ByteFlowRenderer().render_byteflow(cflow).view("closed")

lflow = cflow._restructure_loop()
ByteFlowRenderer().render_byteflow(lflow).view("loop restructured")

bflow = lflow._restructure_branch()
ByteFlowRenderer().render_byteflow(bflow).view("branch restructured")