#!/usr/bin/python3
# Copyright 2013  William Cohen <wcohen@redhat.com>
# Copyright 2013 Red Hat, Inc.
# Copyright 2014 Red Hat, Inc.
# Copyright 2018 Red Hat, Inc.
#
#   This is free software: you can redistribute it and/or modify it
#   under the terms of the GNU General Public License as published by
#   the Free Software Foundation, either version 3 of the License, or
#   (at your option) any later version.
#
#   This program is distributed in the hope that it will be useful, but
#   WITHOUT ANY WARRANTY; without even the implied warranty of
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#   General Public License for more details.
#
#   You should have received a copy of the GNU General Public License
#   along with this program.  If not, see
#   <http://www.gnu.org/licenses/>.

# This simple script convert callgraph information in graphviz formated input
# into a link order

import sys
import gv
import fileinput
import heapq
import re
import getopt
import os

def usage(name):
    print(('''usage: %s [<options>] < call_graph_file > link_order_file
  options:
\t[-h|--help]''' \
        % (name)))

def read_graph():
    text =  ''
    for line in fileinput.input():
        text += line
    return gv.readstring (text)

def simple_order(in_graph):
    # just spit out list of nodes in some order
    func_order = []
    n = gv.firstnode(in_graph)
    while gv.ok(n):
        name = gv.nameof(n)
        func_order.append(name)
        n = gv.nextnode(in_graph, n)
    sbg = gv.firstsubg(in_graph)
    while gv.ok(sbg):
        n = gv.firstnode(sbg)
        while gv.ok(n):
            name = gv.nameof(n)
            func_order.append(name)
            n = gv.nextnode(sbg, n)
        sbg = gv.nextsubg(in_graph, sbg)
    return func_order

def extract_weight(label):
    # some munging of input to allow use of gprof2dot data
    label = re.sub(r'\d+\.\d*%\\n', "", label)
    label = re.sub(r'\D', "", label)
    weight = float(label)
    return weight

def group_order(in_graph):
    # put edges in priority queue
    heap = []
    # counter ensures edges in heap tuples are not compared
    counter = 0
    sbg = gv.firstsubg(in_graph)
    while gv.ok(sbg):
        e = gv.firstedge(sbg)
        while gv.ok(e):
            # add edge to priority queue
            label = gv.getv(e, "label")
            weight = - extract_weight(label)
            heapq.heappush(heap, (weight, counter, e))
            counter = counter + 1
            e = gv.nextedge(sbg, e)
        sbg = gv.nextsubg(in_graph, sbg)


    e = gv.firstedge(in_graph)
    while gv.ok(e):
        # add edge to priority queue
        label = gv.getv(e, "label")
        weight = - extract_weight(label)
        heapq.heappush(heap, (weight, counter, e))
        counter = counter + 1
        e = gv.nextedge(in_graph, e)

    # pull out edges and group functions together until all edges processed
    sn = int(0)
    super_node = {}
    super_node_rename = {}
    func_member = {}
    while heap:
        group = heapq.heappop(heap)
        head = gv.nameof(gv.headof(group[2]))
        tail = gv.nameof(gv.tailof(group[2]))
        # print ( '%s -> %s %3f' % (tail, head, group[0]))
        if not(head in func_member) and not(tail in func_member):
            # print "new supernode"
            sn += 1
            func_member[tail] = super_node_rename[tail] = sn
            func_member[head] = super_node_rename[head] = sn
            super_node[sn] = [tail]
            super_node[sn].append(head)
        elif (head in func_member) and (tail in func_member) and super_node_rename[head] != super_node_rename[tail]:
            # print "combine supernodes"
            super_node[super_node_rename[tail]].extend(super_node[super_node_rename[head]])
            super_node[super_node_rename[head]] = []
            super_node_rename[head] = super_node_rename[tail]
        elif not(head in func_member) and (tail in func_member):
            # print "append to supernode"
            super_node[super_node_rename[tail]].append(head)
            func_member[head] = func_member[tail]
            super_node_rename[head] = super_node_rename[tail]
        elif (head in func_member) and not(tail in func_member):
            # print "prepend to supernode"
            super_node[super_node_rename[head]].insert(0, tail)
            func_member[tail] = func_member[head]
            super_node_rename[tail] = super_node_rename[head]

            # otherwise nothing to do

    # concatenate the super nodes
    func_order = []
    for i in super_node:
        func_order.extend(super_node[i])

    return func_order


def gen_order(in_graph):
    #return simple_order(in_graph)
    return group_order(in_graph)

def strip_versioning(func):
    return func.split("@")[0]

def print_order(order):
    print(('.text : {'))
    for n in order:
        print(('  *(.text.%s)' % strip_versioning(n)))
    #everything else
    print ('  *(.text.*)')
    print(('}'))

argv0 = os.path.basename(sys.argv[0])

# parse options
try:
    (opt, args) = getopt.getopt(sys.argv[1:],
                              'h',
                              ['help',
                               ])
except getopt.GetoptError as e:
    print(("%s: %s" % (argv0, e)))
    usage(argv0)
    sys.exit(1)

# process command line options
for o in opt:
    if o[0] in ('-h', '--help'):
        usage(argv0)
        sys.exit(0)

the_graph = read_graph()
#gv.write(the_graph, "/tmp/output.log")
link_order = gen_order(the_graph)
print_order(link_order)
