"""
DeadlockDetection.py

The purpose of this programme is to experiment with
deadlock detection in Stackless Python

February 14th, 2009

<song>Swimming - Martha and the Muffins </song>
"""

import stackless

class Detector(object):
    def __init__(self):
        self.visits = {}
        self.graph = {}
        self.holding = {}
        return


    def __buildGraph__(self):
        for channel in self.holding:
            a,b,(balance, flag, queue) = channel.__reduce__()
            for task in queue:
                if channel.balance == 0:
                   continue
                for t in self.holding[channel]:
                    if t == task:
                       continue 
                    else:
                       self.add(task, t)
                       self.visits[task] = 0


    def add(self, vertex1, vertex2):
        if vertex1 not in self.graph:
           self.graph[vertex1] = []
        self.graph[vertex1].append(vertex2) 


    def dumpGraph(self):
        for i in self.graph:
            print i, '->', self.graph[i]


    def dumpHoldings(self):
        for i in self.holding:
            print i, self.holding[i] 


    def registerResources(self,channels):
        t = stackless.getcurrent()
        for c in channels:
            if c not in self.holding.keys():
               self.holding[c] = [] 
            self.holding[c].append(t) 


    def __visit__(self, list, parent):
        result = None
        for edge in list:
            if self.visits[edge] == 1:
               result = [edge]
               break 
            elif self.visits[edge] == 0:
               self.visits[edge] += 1
               result = self.__visit__(self.graph[edge], edge) 
               if result != None:
                  result.append(edge)
        return result


    def printCycle(self, root, cycle):
        last = root 
        while (len(cycle) != 0):
              node = cycle.pop()
              print last,'->',node
              last = node


    def detect(self):
        for key in self.graph.keys():
            if self.visits[key] == 0:
               self.visits[key] += 1
               result = self.__visit__(self.graph[key], key)
               if result != None: 
                  self.printCycle(key, result)
                  break


def T(name, receiving, sending):
    global detector

    detector.registerResources([receiving, sending])
    print name, "about to receive"
    receiving.receive()
    print name,"about to receive"
    sending.send()
    print "done"

if __name__  == "__main__":

   global detector
   detector = Detector()

   c1 = stackless.channel()
   c2 = stackless.channel()
   c3 = stackless.channel()
   channels = [c1, c2, c3]

   stackless.tasklet(T)("T1",c1,c3)
   stackless.tasklet(T)("T2",c2,c1)
   stackless.tasklet(T)("T3",c3,c2)

   stackless.run()

   detector.__buildGraph__()
   detector.detect()