#!/usr/bin/python

import sys
import re

def dot_label(lc_name):
    return lc_name.replace('>', r'\>')

class lock_class(object):
    def __init__(self, m):
        object.__init__(self)
        (key, nfd, nbd, usage, name) = m.groups()
        self.key = key
        self.nfd = int(nfd)
        self.nbd = int(nbd)
        self.usage = usage
        self.name = name
        self.fdks = set()
        self.fds = []
        self.bds = []
    def append_fdk(self, fdk):
        self.fdks.add(fdk)
    def append_fd(self, fd):
        self.fds.append(fd)
    def append_bd(self, bd):
        self.bds.append(bd)
    def resolve_fd(self, lc_map):
        for fdk in self.fdks:
            if not lc_map.has_key(fdk):
                print >> sys.stderr, 'WARNING: not lock_class for %s' % (fdk,)
                continue
            lc = lc_map[fdk]
            self.append_fd(lc)
            lc.append_bd(self)

class lockdep(object):
    re_lock_fd = re.compile(r'^ -> \[([a-f0-9]+)\] (\S+)\s*$')
    re_lock_class = re.compile(r'^([a-f0-9]+) FD:\s*(\d+) ' +
                               r'BD:\s*(\d+) (....): (\S+)\s*$')
    def __init__(self):
        object.__init__(self)
        self.lock_classes = {}
    def parse(self, f):
        lc = None
        for l in f:
            mlc = lockdep.re_lock_class.match(l)
            if mlc:
                lc = lock_class(mlc)
                self.lock_classes[lc.key] = lc
                continue
            mfd = lockdep.re_lock_fd.match(l)
            if (mfd):
                lc.append_fdk(mfd.group(1))
        for lc in self.lock_classes.values():
            lc.resolve_fd(self.lock_classes)
    def dump_dot(self, fout, lc):
        touched = set()
        fout.write('''digraph Lockdep {
rankdir = LR ;
node [ shape = record, fontname = Courier ] ;
''')
        def do_dump(lc):
            fout.write('%s [ label="%s$%s" ] ;\n' % \
                           (lc.key, dot_label(lc.name), dot_label(lc.usage)))
            touched.add(lc.key)
            for fd in lc.fds:
                fout.write('"%s" -> "%s" ;\n' % (lc.key, fd.key))
                if fd.key not in touched:
                    do_dump(fd)
        do_dump(lc)
        fout.write('}\n')
    def dump_dots(self, prefix):
        n = 0
        for lc in self.lock_classes.values():
            if len(lc.bds) == 0:
                fout = file('%s-%d.dot' % (prefix, n), 'w')
                n = n + 1
                self.dump_dot(fout, lc)
    def dump_chains(self, fout):
        def do_dump(lc, stack):
            if len(lc.fds) == 0:
                for l in stack:
                    fout.write('%s : ' % (l.name,))
                fout.write('%s\n' % (lc.name,))
                return
            stack.append(lc)
            for fd in lc.fds:
                do_dump(fd, stack)
            del stack[-1]
        for lc in self.lock_classes.values():
            if len(lc.bds) == 0:
                do_dump(lc, [])
    def dump(self):
        for lc in self.lock_classes.values():
            print lc.name, lc.fds

class lock_chain(object):
    def __init__(self, ic, lcs):
        object.__init__(self)
        self.irq_context = ic
        self.class_keys = lcs[:]
        self.classes = []
    def resolve_class(self, lc_map):
        for k in self.class_keys:
            c = lc_map[k]
            self.classes.append(c)
    def add_to_tree(self, trees):
        def classes_add_to_tree(classes, tree_node):
            if len(classes) == 0:
                return
            lc = classes[0]
            if not tree_node.children.has_key(lc.key):
                tree_node.children[lc.key] = lch_tree_node(lc)
            classes_add_to_tree(classes[1:], tree_node.children[lc.key])
        classes_add_to_tree(self.classes, trees)
    def dump(self, fout):
        fout.write('ic = %d: ' % (self.irq_context,))
        for c in self.classes:
            fout.write('%s,' % (c.name,))
        fout.write('\n')

class lch_tree_node(object):
    next_id = 0

    def __init__(self, lc):
        object.__init__(self)
        self.cls = lc
        self.children = {}
        self.id = lch_tree_node.next_id
        lch_tree_node.next_id = lch_tree_node.next_id + 1

class lock_chains(object):
    re_lch_head = re.compile(r'^irq_context: (\d)$')
    re_lch_class = re.compile(r'\[([a-f0-9]+)\]\s*(\S+)\s*$')

    def __init__(self, lockdep):
        object.__init__(self)
        self.lockdep = lockdep
        self.chains = []
        self.lch_trees = lch_tree_node(None)
    def parse(self, f):
        ic = 0
        lcs = []
        for l in f:
            mc = lock_chains.re_lch_class.match(l)
            if mc:
                lcs.append(mc.group(1))
            mh = lock_chains.re_lch_head.match(l)
            if mh:
                ic = int(mh.group(1))
                if len(lcs) != 0:
                    lch = lock_chain(ic, lcs)
                    self.chains.append(lch)
                    lcs = []
        lc_map = self.lockdep.lock_classes
        for ch in self.chains:
            ch.resolve_class(lc_map)
        self.build_tree()
    def build_tree(self):
        trees = self.lch_trees
        for ch in self.chains:
            ch.add_to_tree(trees)
    def dump(self, fout):
        for ch in self.chains:
            ch.dump(fout)
    def dump_tree_dot(self, fout, root):
        fout.write('''digraph Lockdep {
rankdir = LR ;
node [ shape = record, fontname = Courier ] ;
''')
        def do_dump(node, parent):
            lc = node.cls
            fout.write('%d [ label = "%s" ] ;\n' %
                       (node.id, dot_label(lc.name)))
            if parent:
                fout.write('"%d" -> "%d" ;\n' % (parent.id, node.id))
            children = sorted(node.children.values(), None,
                              lambda n: n.cls.name)
            for child in children:
                do_dump(child, node)
        do_dump(root, None)
        fout.write('}\n')
    def dump_trees_dot(self, prefix):
        n = 0
        for lch_root in self.lch_trees.children.values():
            fout = file('%s-%d.dot' % (prefix, n), 'w')
            n = n + 1
            self.dump_tree_dot(fout, lch_root)

def test(fin):
    ld = lockdep()
    ld.parse(fin)
    ld.dump_dots('out/lockdep')

def test2(fin):
    ld = lockdep()
    ld.parse(fin)
    lc = ld.lock_classes['ffff81000108eae0']
    ld.dump_dot(file('out/a.dot', 'w'), lc)

def test3(fin, fout):
    ld = lockdep()
    ld.parse(fin)
    ld.dump_chains(fout)

def test4():
    ld = lockdep()
    ld.parse(file('lockdep'))
    lchs = lock_chains(ld)
    lchs.parse(file('lockdep_chains'))
    #lchs.dump(sys.stdout)
    lchs.dump_trees_dot('out/lch')


if __name__ == '__main__':
    test4()