#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
'''
calltree.py - Call tree manipulator

This script manipulates call tree generated by JASMIN CallTreeManager. It
prints, folds, and limit depth of the input call tree.
'''
from __future__ import division
from __future__ import print_function

from builtins import str
from builtins import range
from past.utils import old_div
from builtins import object
import argparse
import copy
import json
import fnmatch
import hashlib
import re

from collections import OrderedDict
from functools import reduce


def toposort(data):
    """ Dependencies are expressed as a dictionary whose keys are items and
    whose values are a set of dependent items. Output is a list of sets in
    topological order. The first set consists of items with no dependences,
    each subsequent set consists of items that depend upon items in the
    preceeding sets.  """

    # Special case empty input.
    if len(data) == 0:
        return

    # Copy the input so as to leave it unmodified.
    data = data.copy()

    # Ignore self dependencies.
    for k, v in list(data.items()):
        v.discard(k)

    # Find all items that don't depend on anything.
    extra_items_in_deps = reduce(set.union, list(data.values())) - set(data.keys())
    # Add empty dependences where needed.
    data.update({item: set() for item in extra_items_in_deps})
    while True:
        ordered = set(item for item, dep in list(data.items()) if len(dep) == 0)
        if not ordered:
            break
        yield ordered
        data = {item: (dep - ordered)
                for item, dep in data.items() if item not in ordered}
    if len(data) != 0:
        raise ValueError('Cyclic dependencies exist among the'
                         'se items: {}'.format(', '.join(repr(
                             x) for x in list(data.items()))))


def toposort_flatten(data, sort=True):
    result = []
    for d in toposort(data):
        result.extend((sorted if sort else list)(d))
    return result


class TreeNode(object):
    @classmethod
    def serialize(cls, node):
        if not node:
            return None
        data = OrderedDict()
        data["id"] = node.id
        data["cycle"] = node.cycle
        data["children"] = []
        for c in node.children:
            child = cls.serialize(c)
            data["children"].append(child)
        return data

    @classmethod
    def deserialize(cls, data):
        if not data:
            return None
        node = TreeNode(data["id"], data.get("cycle", 1))
        for c in data["children"]:
            child = cls.deserialize(c)
            node.append_child(child)
        return node

    @classmethod
    def from_ascii(cls, data):
        data = re.sub(r"#.*", "", data)
        tree_nodes = []
        for line in data.strip().split("\n"):
            line = line.strip()
            if not line:
                continue
            segs = [x.strip() for x in line.split()]
            assert (len(segs) >= 2)
            if len(segs) == 2:
                level = len(segs[0]) - 1
                content = (segs[1], 1)
            else:
                level = len(segs[0]) - 1
                content = (segs[1], segs[2])
            tree_nodes.append((level, content))

        def build_recursive(nodes):
            if not nodes:
                return []
            result = []
            min_level = min(x[0] for x in nodes)
            assert (nodes[0][0] == min_level)
            content, children = (nodes[0][1], [])
            for l, n in nodes[1:]:
                if l == min_level:
                    result.append({"id": content[0],
                                   "cycle": content[1],
                                   "children": build_recursive(children)})
                    content, children = (n, [])
                else:
                    children.append((l, n))
            result.append({"id": content[0],
                           "cycle": content[1],
                           "children": build_recursive(children)})
            return result

        data = build_recursive(tree_nodes)
        assert (len(data) == 1)
        return cls.deserialize(data[0])

    def __init__(self, id, cycle=1):
        self.id = id
        self.cycle = cycle
        self.children = []
        self.update_digest()

    def append_child(self, child):
        assert isinstance(child, TreeNode)
        self.children.append(child)
        self.update_digest()

    def update_digest(self):
        m = hashlib.md5()
        m.update(str(self.id))
        for c in self.children:
            m.update(str(c.digest))
        self.digest = m.digest()

    def __repr__(self):
        result = []
        result.append(" %s %s" % (self.id, self.cycle))
        for c in self.children:
            child_repr = repr(c).split("\n")
            result.extend(["-%s" % x for x in child_repr])
        return "\n".join(result)

    def __eq__(self, x):
        return self.digest == x.digest

    def __ne__(self, x):
        return self.digest != x.digest

    def __le__(self, x):
        if self.id != x.id:
            return False
        me = [c.digest for c in self.children]
        other = [c.digest for c in x.children]
        index = 0
        for item in me:
            if item not in other[index:]:
                return False
            index = other.index(item, index)
        return True

    def __lt__(self, x):
        if len(self.children) >= len(x.children):
            return False
        return self <= x

    def __ge__(self, x):
        if self.id != x.id:
            return False
        me = [c.digest for c in self.children]
        other = [c.digest for c in x.children]
        index = 0
        for item in other:
            if item not in me[index:]:
                return False
            index = me.index(item, index)
        return True

    def __gt__(self, x):
        if len(self.children) <= len(x.children):
            return False
        return self <= x


def revert_unrolled_loop(callseq):
    if len(callseq) <= 1:
        return (callseq, False)
    callseqlen = len(callseq)
    for subseqlen in range(1, old_div(callseqlen, 2) + 1):
        # skip bad subsequence length
        if callseqlen % subseqlen != 0:
            continue
        nsubseqs = old_div(callseqlen, subseqlen)
        assert (nsubseqs > 1)
        is_an_unroll = True
        for subseqid in range(1, nsubseqs):
            cs = subseqid * subseqlen
            ce = cs + subseqlen
            ps = cs - subseqlen
            if callseq[ps:cs] != callseq[cs:ce]:
                is_an_unroll = False
                break
        if is_an_unroll:
            return (list(callseq[:subseqlen]), True)
    return (callseq, False)


def prune_unrolled_loop(callseq):
    if len(callseq) <= 1:
        return (callseq, False)
    found_unrolled_loop = False
    do_unroll = True
    while do_unroll:
        callseqlen = len(callseq)
        found_unrolled_loop_this = False
        for start in range(callseqlen):
            for end in range(callseqlen, start + 1, -1):
                result, success = revert_unrolled_loop(callseq[start:end])
                if success:
                    found_unrolled_loop = True
                    found_unrolled_loop_this = True
                    callseq = callseq[:start] + result + callseq[end:]
                    break
            if found_unrolled_loop_this:
                break
        if not found_unrolled_loop_this:
            do_unroll = False
    return (callseq, found_unrolled_loop)


def prune_unrolled_loops(tree):
    if not tree:
        return None
    children = [prune_unrolled_loops(c) for c in tree.children]
    new_children, _ = prune_unrolled_loop(children)
    node = TreeNode(tree.id, tree.cycle)
    for c in new_children:
        node.append_child(c)
    return node


def remove_tree_nodes(tree, patterns):
    if not tree:
        return None
    for c in patterns:
        if fnmatch.fnmatch(tree.id, c):
            return None
    children = []
    for c in tree.children:
        child = remove_tree_nodes(c, patterns)
        if child:
            children.append(child)
    new_tree = TreeNode(tree.id, tree.cycle)
    for c in children:
        new_tree.append_child(c)
    return new_tree


def remove_tree_levels(tree, max_level):
    def remove_recursive(tree, curr_level, max_level):
        if not tree:
            return None
        if curr_level >= max_level:
            return None
        children = []
        for c in tree.children:
            child = remove_recursive(c, curr_level + 1, max_level)
            if child:
                children.append(child)
        new_tree = TreeNode(tree.id, tree.cycle)
        for c in children:
            new_tree.append_child(c)
        return new_tree

    return remove_recursive(tree, 0, max_level)


def merge_repeative_calls(calls):
    if not calls:
        return None
    # check the input to see if they are from the same call
    call_ids = set()
    for c in calls:
        call_ids.add(c.id)
    if len(call_ids) != 1:
        raise ValueError("Not repeative calls: {}".format(calls))
    # do current level
    childset = {}
    graph = {}
    for c in calls:
        for child in c.children:
            cid = child.id
            if cid not in childset:
                childset[cid] = list()
            childset[cid].append(child)
        child_ids = [child.id for child in c.children]
        if not child_ids:
            continue
        if child_ids[0] not in graph:
            graph[child_ids[0]] = set()
        for i in range(1, len(child_ids)):
            cid = child_ids[i]
            if cid in graph:
                graph[cid].add(child_ids[i - 1])
            else:
                graph[cid] = set([child_ids[i - 1]])
    cids = toposort_flatten(graph)
    node = TreeNode(calls[0].id, calls[0].cycle)
    for c in cids:
        node.append_child(merge_repeative_calls(childset[c]))
    return node


def fold_tree(tree, cascade=False):
    def fold_tree_recursive(tree):
        if not tree:
            return None
        folded_children = []
        for c in tree.children:
            folded_children.append(fold_tree_recursive(c))
        new_children = []
        if folded_children:
            new_children = [folded_children[0]]
            for i in range(1, len(folded_children)):
                if folded_children[i] != new_children[-1]:
                    new_children.append(folded_children[i])
        new_tree = TreeNode(tree.id, tree.cycle)
        for c in new_children:
            new_tree.append_child(c)
        return new_tree

    def cascase_tree_recursive(tree):
        def in_full_order_set(elem, array):
            if not array:
                return True
            for c in array:
                if elem <= c or elem >= c:
                    return True
            return False

        def get_maximum(array):
            tmp = list(array)
            tmp.sort()
            return tmp[-1]

        if not tree:
            return None
        folded_children = []
        for c in tree.children:
            folded_children.append(cascase_tree_recursive(c))

        new_children = []
        if folded_children:
            poss = []
            pos = []
            for c in folded_children:
                if in_full_order_set(c, pos):
                    pos.append(c)
                else:
                    poss.append(pos)
                    pos = [c]
            poss.append(pos)
            for c in poss:
                new_children.append(get_maximum(c))

        new_tree = TreeNode(tree.id, tree.cycle)
        for c in new_children:
            new_tree.append_child(c)
        return new_tree

    if cascade:
        try:
            result = merge_repeative_calls([tree])
        except ValueError:
            resunt = tree
        return tree
    else:
        return fold_tree_recursive(tree)


def print_tree_plain(tree, max_level=None):
    def print_tree_recursive(tree, level, max_level):
        if max_level and level > max_level:
            return
        print("--" * level, tree.id, tree.cycle)
        for c in tree.children:
            print_tree_recursive(c, level + 1, max_level)

    print_tree_recursive(tree, 1, max_level)


def print_tree_salt(tree, max_level=None):
    def print_tree_salt_recursive(tree, level, max_level):
        if max_level and level > max_level:
            return
        print("+" * level, tree.id)
        for c in tree.children:
            print_tree_salt_recursive(c, level + 1, max_level)

    print("@startsalt")
    print("{")
    print("{T")
    print_tree_salt_recursive(tree, 1, max_level)
    print("}")
    print("}")
    print("@endsalt")


def print_tree_asciidoc(tree, max_level=None):
    def print_tree_adoc_recursive(tree, level, max_level):
        if max_level and level > max_level:
            return
        print("*" * level, tree.id)
        for c in tree.children:
            print_tree_adoc_recursive(c, level + 1, max_level)

    print_tree_adoc_recursive(tree, 1, max_level)


def count_nodes(tree, spec):
    def match(node):
        for ptn in spec:
            if fnmatch.fnmatch(node.id, ptn):
                return True
        return False

    counter = {}

    def count_recursive(tree, base):
        if not tree:
            return
        base = base * tree.cycle
        if match(tree):
            if tree.id not in counter:
                counter[tree.id] = 0
            counter[tree.id] += base
        for c in tree.children:
            count_recursive(c, base)

    count_recursive(tree, 1)
    for k, v in counter.items():
        print("{}: {}".format(k, v))


def main():
    parser = argparse.ArgumentParser(
        description=__doc__,
        formatter_class=argparse.RawDescriptionHelpFormatter)
    parser.add_argument("call_tree",
                        help="Call tree file (json) generated by JASMIN")
    parser.add_argument("--format",
                        choices=("json", "ascii"),
                        default="json",
                        help="Call tree file format (default: json)")
    parser.add_argument("--use-tree",
                        default=0,
                        type=int,
                        help="Tree to use when multiple trees (default: 0)")
    parser.add_argument("--print-depth",
                        default=None,
                        type=int,
                        help="Max depth to print")
    parser.add_argument("--print-style",
                        default="plain",
                        choices=["plain", "asciidoc", "plantuml"],
                        help="Print style (default: plain)")
    parser.add_argument("--remove-levels",
                        default=None,
                        type=int,
                        help="Remove tree nodes whose level is higher than "
                        "specified")
    parser.add_argument("--remove-nodes",
                        default=[],
                        nargs="+",
                        help="Remove tree nodes whose name match, "
                        "supports shell-style wildcards")
    parser.add_argument("--prune-unrolled-loops",
                        action="store_true",
                        help="Fold unrolled loops into one single block")
    parser.add_argument("--save",
                        default=None,
                        help="Save processed tree to file")
    parser.add_argument("--count", nargs="+", default=[],
                        help="Count call occurances only")
    grp = parser.add_mutually_exclusive_group()
    grp.add_argument("--fold", action="store_true", help="Fold tree")
    grp.add_argument("--cascade", action="store_true", help="Cascade tree")

    args = parser.parse_args()

    if args.format == "json":
        data = json.load(file(args.call_tree), object_hook=OrderedDict)
        tree = TreeNode.deserialize(data)
    elif args.format == "ascii":
        content = file(args.call_tree).read()
        tree = TreeNode.from_ascii(content)
    else:
        raise ValueError("Unknown calltree file format: '%s'" % args.format)
    if tree.id == "ROOT":
        tree = tree.children[args.use_tree]

    if args.count:
        count_nodes(tree, args.count)
        return

    if args.remove_nodes:
        tree = remove_tree_nodes(tree, args.remove_nodes)
    if args.remove_levels:
        tree = remove_tree_levels(tree, args.remove_levels)
    if args.prune_unrolled_loops:
        tree = prune_unrolled_loops(tree)
    if args.fold or args.cascade:
        tree = fold_tree(tree, args.cascade)
    if args.save:
        data = TreeNode.serialize(tree)
        json.dump(data, file(args.save, "w"), indent=2)

    if args.print_style == "plain":
        print_tree_plain(tree, args.print_depth)
    elif args.print_style == "asciidoc":
        print_tree_asciidoc(tree, args.print_depth)
    elif args.print_style == "plantuml":
        print_tree_salt(tree, args.print_depth)


if __name__ == "__main__":
    main()

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
'''
calltree.py - Call tree manipulator

This script manipulates call tree generated by JASMIN CallTreeManager. It
prints, folds, and limit depth of the input call tree.
'''
from __future__ import division
from __future__ import print_function

from builtins import str
from builtins import range
from past.utils import old_div
from builtins import object
import argparse
import copy
import json
import fnmatch
import hashlib
import re

from collections import OrderedDict
from functools import reduce


def toposort(data):
    """ Dependencies are expressed as a dictionary whose keys are items and
    whose values are a set of dependent items. Output is a list of sets in
    topological order. The first set consists of items with no dependences,
    each subsequent set consists of items that depend upon items in the
    preceeding sets.  """

    # Special case empty input.
    if len(data) == 0:
        return

    # Copy the input so as to leave it unmodified.
    data = data.copy()

    # Ignore self dependencies.
    for k, v in list(data.items()):
        v.discard(k)

    # Find all items that don't depend on anything.
    extra_items_in_deps = reduce(set.union, list(data.values())) - set(data.keys())
    # Add empty dependences where needed.
    data.update({item: set() for item in extra_items_in_deps})
    while True:
        ordered = set(item for item, dep in list(data.items()) if len(dep) == 0)
        if not ordered:
            break
        yield ordered
        data = {item: (dep - ordered)
                for item, dep in data.items() if item not in ordered}
    if len(data) != 0:
        raise ValueError('Cyclic dependencies exist among the'
                         'se items: {}'.format(', '.join(repr(
                             x) for x in list(data.items()))))


def toposort_flatten(data, sort=True):
    result = []
    for d in toposort(data):
        result.extend((sorted if sort else list)(d))
    return result


class TreeNode(object):
    @classmethod
    def serialize(cls, node):
        if not node:
            return None
        data = OrderedDict()
        data["id"] = node.id
        data["cycle"] = node.cycle
        data["children"] = []
        for c in node.children:
            child = cls.serialize(c)
            data["children"].append(child)
        return data

    @classmethod
    def deserialize(cls, data):
        if not data:
            return None
        node = TreeNode(data["id"], data.get("cycle", 1))
        for c in data["children"]:
            child = cls.deserialize(c)
            node.append_child(child)
        return node

    @classmethod
    def from_ascii(cls, data):
        data = re.sub(r"#.*", "", data)
        tree_nodes = []
        for line in data.strip().split("\n"):
            line = line.strip()
            if not line:
                continue
            segs = [x.strip() for x in line.split()]
            assert (len(segs) >= 2)
            if len(segs) == 2:
                level = len(segs[0]) - 1
                content = (segs[1], 1)
            else:
                level = len(segs[0]) - 1
                content = (segs[1], segs[2])
            tree_nodes.append((level, content))

        def build_recursive(nodes):
            if not nodes:
                return []
            result = []
            min_level = min(x[0] for x in nodes)
            assert (nodes[0][0] == min_level)
            content, children = (nodes[0][1], [])
            for l, n in nodes[1:]:
                if l == min_level:
                    result.append({"id": content[0],
                                   "cycle": content[1],
                                   "children": build_recursive(children)})
                    content, children = (n, [])
                else:
                    children.append((l, n))
            result.append({"id": content[0],
                           "cycle": content[1],
                           "children": build_recursive(children)})
            return result

        data = build_recursive(tree_nodes)
        assert (len(data) == 1)
        return cls.deserialize(data[0])

    def __init__(self, id, cycle=1):
        self.id = id
        self.cycle = cycle
        self.children = []
        self.update_digest()

    def append_child(self, child):
        assert isinstance(child, TreeNode)
        self.children.append(child)
        self.update_digest()

    def update_digest(self):
        m = hashlib.md5()
        m.update(str(self.id))
        for c in self.children:
            m.update(str(c.digest))
        self.digest = m.digest()

    def __repr__(self):
        result = []
        result.append(" %s %s" % (self.id, self.cycle))
        for c in self.children:
            child_repr = repr(c).split("\n")
            result.extend(["-%s" % x for x in child_repr])
        return "\n".join(result)

    def __eq__(self, x):
        return self.digest == x.digest

    def __ne__(self, x):
        return self.digest != x.digest

    def __le__(self, x):
        if self.id != x.id:
            return False
        me = [c.digest for c in self.children]
        other = [c.digest for c in x.children]
        index = 0
        for item in me:
            if item not in other[index:]:
                return False
            index = other.index(item, index)
        return True

    def __lt__(self, x):
        if len(self.children) >= len(x.children):
            return False
        return self <= x

    def __ge__(self, x):
        if self.id != x.id:
            return False
        me = [c.digest for c in self.children]
        other = [c.digest for c in x.children]
        index = 0
        for item in other:
            if item not in me[index:]:
                return False
            index = me.index(item, index)
        return True

    def __gt__(self, x):
        if len(self.children) <= len(x.children):
            return False
        return self <= x


def revert_unrolled_loop(callseq):
    if len(callseq) <= 1:
        return (callseq, False)
    callseqlen = len(callseq)
    for subseqlen in range(1, old_div(callseqlen, 2) + 1):
        # skip bad subsequence length
        if callseqlen % subseqlen != 0:
            continue
        nsubseqs = old_div(callseqlen, subseqlen)
        assert (nsubseqs > 1)
        is_an_unroll = True
        for subseqid in range(1, nsubseqs):
            cs = subseqid * subseqlen
            ce = cs + subseqlen
            ps = cs - subseqlen
            if callseq[ps:cs] != callseq[cs:ce]:
                is_an_unroll = False
                break
        if is_an_unroll:
            return (list(callseq[:subseqlen]), True)
    return (callseq, False)


def prune_unrolled_loop(callseq):
    if len(callseq) <= 1:
        return (callseq, False)
    found_unrolled_loop = False
    do_unroll = True
    while do_unroll:
        callseqlen = len(callseq)
        found_unrolled_loop_this = False
        for start in range(callseqlen):
            for end in range(callseqlen, start + 1, -1):
                result, success = revert_unrolled_loop(callseq[start:end])
                if success:
                    found_unrolled_loop = True
                    found_unrolled_loop_this = True
                    callseq = callseq[:start] + result + callseq[end:]
                    break
            if found_unrolled_loop_this:
                break
        if not found_unrolled_loop_this:
            do_unroll = False
    return (callseq, found_unrolled_loop)


def prune_unrolled_loops(tree):
    if not tree:
        return None
    children = [prune_unrolled_loops(c) for c in tree.children]
    new_children, _ = prune_unrolled_loop(children)
    node = TreeNode(tree.id, tree.cycle)
    for c in new_children:
        node.append_child(c)
    return node


def remove_tree_nodes(tree, patterns):
    if not tree:
        return None
    for c in patterns:
        if fnmatch.fnmatch(tree.id, c):
            return None
    children = []
    for c in tree.children:
        child = remove_tree_nodes(c, patterns)
        if child:
            children.append(child)
    new_tree = TreeNode(tree.id, tree.cycle)
    for c in children:
        new_tree.append_child(c)
    return new_tree


def remove_tree_levels(tree, max_level):
    def remove_recursive(tree, curr_level, max_level):
        if not tree:
            return None
        if curr_level >= max_level:
            return None
        children = []
        for c in tree.children:
            child = remove_recursive(c, curr_level + 1, max_level)
            if child:
                children.append(child)
        new_tree = TreeNode(tree.id, tree.cycle)
        for c in children:
            new_tree.append_child(c)
        return new_tree

    return remove_recursive(tree, 0, max_level)


def merge_repeative_calls(calls):
    if not calls:
        return None
    # check the input to see if they are from the same call
    call_ids = set()
    for c in calls:
        call_ids.add(c.id)
    if len(call_ids) != 1:
        raise ValueError("Not repeative calls: {}".format(calls))
    # do current level
    childset = {}
    graph = {}
    for c in calls:
        for child in c.children:
            cid = child.id
            if cid not in childset:
                childset[cid] = list()
            childset[cid].append(child)
        child_ids = [child.id for child in c.children]
        if not child_ids:
            continue
        if child_ids[0] not in graph:
            graph[child_ids[0]] = set()
        for i in range(1, len(child_ids)):
            cid = child_ids[i]
            if cid in graph:
                graph[cid].add(child_ids[i - 1])
            else:
                graph[cid] = set([child_ids[i - 1]])
    cids = toposort_flatten(graph)
    node = TreeNode(calls[0].id, calls[0].cycle)
    for c in cids:
        node.append_child(merge_repeative_calls(childset[c]))
    return node


def fold_tree(tree, cascade=False):
    def fold_tree_recursive(tree):
        if not tree:
            return None
        folded_children = []
        for c in tree.children:
            folded_children.append(fold_tree_recursive(c))
        new_children = []
        if folded_children:
            new_children = [folded_children[0]]
            for i in range(1, len(folded_children)):
                if folded_children[i] != new_children[-1]:
                    new_children.append(folded_children[i])
        new_tree = TreeNode(tree.id, tree.cycle)
        for c in new_children:
            new_tree.append_child(c)
        return new_tree

    def cascase_tree_recursive(tree):
        def in_full_order_set(elem, array):
            if not array:
                return True
            for c in array:
                if elem <= c or elem >= c:
                    return True
            return False

        def get_maximum(array):
            tmp = list(array)
            tmp.sort()
            return tmp[-1]

        if not tree:
            return None
        folded_children = []
        for c in tree.children:
            folded_children.append(cascase_tree_recursive(c))

        new_children = []
        if folded_children:
            poss = []
            pos = []
            for c in folded_children:
                if in_full_order_set(c, pos):
                    pos.append(c)
                else:
                    poss.append(pos)
                    pos = [c]
            poss.append(pos)
            for c in poss:
                new_children.append(get_maximum(c))

        new_tree = TreeNode(tree.id, tree.cycle)
        for c in new_children:
            new_tree.append_child(c)
        return new_tree

    if cascade:
        try:
            result = merge_repeative_calls([tree])
        except ValueError:
            resunt = tree
        return tree
    else:
        return fold_tree_recursive(tree)


def print_tree_plain(tree, max_level=None):
    def print_tree_recursive(tree, level, max_level):
        if max_level and level > max_level:
            return
        print("--" * level, tree.id, tree.cycle)
        for c in tree.children:
            print_tree_recursive(c, level + 1, max_level)

    print_tree_recursive(tree, 1, max_level)


def print_tree_salt(tree, max_level=None):
    def print_tree_salt_recursive(tree, level, max_level):
        if max_level and level > max_level:
            return
        print("+" * level, tree.id)
        for c in tree.children:
            print_tree_salt_recursive(c, level + 1, max_level)

    print("@startsalt")
    print("{")
    print("{T")
    print_tree_salt_recursive(tree, 1, max_level)
    print("}")
    print("}")
    print("@endsalt")


def print_tree_asciidoc(tree, max_level=None):
    def print_tree_adoc_recursive(tree, level, max_level):
        if max_level and level > max_level:
            return
        print("*" * level, tree.id)
        for c in tree.children:
            print_tree_adoc_recursive(c, level + 1, max_level)

    print_tree_adoc_recursive(tree, 1, max_level)


def count_nodes(tree, spec):
    def match(node):
        for ptn in spec:
            if fnmatch.fnmatch(node.id, ptn):
                return True
        return False

    counter = {}

    def count_recursive(tree, base):
        if not tree:
            return
        base = base * tree.cycle
        if match(tree):
            if tree.id not in counter:
                counter[tree.id] = 0
            counter[tree.id] += base
        for c in tree.children:
            count_recursive(c, base)

    count_recursive(tree, 1)
    for k, v in counter.items():
        print("{}: {}".format(k, v))


def main():
    parser = argparse.ArgumentParser(
        description=__doc__,
        formatter_class=argparse.RawDescriptionHelpFormatter)
    parser.add_argument("call_tree",
                        help="Call tree file (json) generated by JASMIN")
    parser.add_argument("--format",
                        choices=("json", "ascii"),
                        default="json",
                        help="Call tree file format (default: json)")
    parser.add_argument("--use-tree",
                        default=0,
                        type=int,
                        help="Tree to use when multiple trees (default: 0)")
    parser.add_argument("--print-depth",
                        default=None,
                        type=int,
                        help="Max depth to print")
    parser.add_argument("--print-style",
                        default="plain",
                        choices=["plain", "asciidoc", "plantuml"],
                        help="Print style (default: plain)")
    parser.add_argument("--remove-levels",
                        default=None,
                        type=int,
                        help="Remove tree nodes whose level is higher than "
                        "specified")
    parser.add_argument("--remove-nodes",
                        default=[],
                        nargs="+",
                        help="Remove tree nodes whose name match, "
                        "supports shell-style wildcards")
    parser.add_argument("--prune-unrolled-loops",
                        action="store_true",
                        help="Fold unrolled loops into one single block")
    parser.add_argument("--save",
                        default=None,
                        help="Save processed tree to file")
    parser.add_argument("--count", nargs="+", default=[],
                        help="Count call occurances only")
    grp = parser.add_mutually_exclusive_group()
    grp.add_argument("--fold", action="store_true", help="Fold tree")
    grp.add_argument("--cascade", action="store_true", help="Cascade tree")

    args = parser.parse_args()

    if args.format == "json":
        data = json.load(file(args.call_tree), object_hook=OrderedDict)
        tree = TreeNode.deserialize(data)
    elif args.format == "ascii":
        content = file(args.call_tree).read()
        tree = TreeNode.from_ascii(content)
    else:
        raise ValueError("Unknown calltree file format: '%s'" % args.format)
    if tree.id == "ROOT":
        tree = tree.children[args.use_tree]

    if args.count:
        count_nodes(tree, args.count)
        return

    if args.remove_nodes:
        tree = remove_tree_nodes(tree, args.remove_nodes)
    if args.remove_levels:
        tree = remove_tree_levels(tree, args.remove_levels)
    if args.prune_unrolled_loops:
        tree = prune_unrolled_loops(tree)
    if args.fold or args.cascade:
        tree = fold_tree(tree, args.cascade)
    if args.save:
        data = TreeNode.serialize(tree)
        json.dump(data, file(args.save, "w"), indent=2)

    if args.print_style == "plain":
        print_tree_plain(tree, args.print_depth)
    elif args.print_style == "asciidoc":
        print_tree_asciidoc(tree, args.print_depth)
    elif args.print_style == "plantuml":
        print_tree_salt(tree, args.print_depth)


if __name__ == "__main__":
    main()

#!/usr/bin/env python # -*- coding: utf-8 -*- # calltree.py - Call tree manipulator  This script manipulates call tree generated by JASMIN CallTreeManager. It prints, folds, and limit depth of the input call tree. Dependencies are expressed as a dictionary whose keys are items and     whose values are a set of dependent items. Output is a list of sets in     topological order. The first set consists of items with no dependences,     each subsequent set consists of items that depend upon items in the     preceeding sets. # Special case empty input. # Copy the input so as to leave it unmodified. # Ignore self dependencies. # Find all items that don't depend on anything. # Add empty dependences where needed. # skip bad subsequence length # check the input to see if they are from the same call # do current level