class Metasm::Gui::Graph

Attributes

box[RW]
box_id[RW]
id[RW]
keep_split[RW]
root_addrs[RW]
view_x[RW]
view_y[RW]

Public Class Methods

new(id) click to toggle source
# File metasm/gui/dasm_graph.rb, line 26
def initialize(id)
        @id = id
        @root_addrs = []
        @view_x = @view_y = -0xfff_ffff
        clear
end

Public Instance Methods

auto_arrange_boxes() click to toggle source
# File metasm/gui/dasm_graph.rb, line 728
def auto_arrange_boxes
        auto_arrange_init
        nil while @groups.length > 1 and auto_arrange_step
        auto_arrange_post
        @groups = []
end
auto_arrange_init() click to toggle source

place boxes in a good-looking layout create artificial 'group' container for boxes, that will later be merged in geometrical patterns

# File metasm/gui/dasm_graph.rb, line 622
def auto_arrange_init
        # 'group' is an array of boxes
        # all groups are centered on the origin
        h = {}        # { box => group }
        @groups = @box.map { |b|
                b.x = -b.w/2
                b.y = -b.h/2
                g = Box.new(nil, [b])
                g.x = b.x - 8
                g.y = b.y - 9
                g.w = b.w + 16
                g.h = b.h + 18
                h[b] = g
                g
        }

        # init group.to/from
        # must always point to something that is in the 'groups' array
        # no self references
        # a box is in one and only one group in 'groups'
        @groups.each { |g|
                g.to   = g.content.first.to.map   { |t| h[t] if t != g }.compact
                g.from = g.content.first.from.map { |f| h[f] if f != g }.compact
        }

        # order boxes
        order = order_graph(@groups)

        # remove cycles from the graph
        make_tree(@groups, order)
end
auto_arrange_movebox() click to toggle source

actually move boxes inside the groups

# File metasm/gui/dasm_graph.rb, line 666
def auto_arrange_movebox
        @groups.each { |g|
                dx = (g.x + g.w/2).to_i
                dy = (g.y + g.h/2).to_i
                g.content.each { |b|
                        b.x += dx
                        b.y += dy
                }
        }
end
auto_arrange_post() click to toggle source
# File metasm/gui/dasm_graph.rb, line 660
def auto_arrange_post
        auto_arrange_movebox
        #auto_arrange_vertical_shrink
end
auto_arrange_step(groups=@groups) click to toggle source
# File metasm/gui/dasm_graph.rb, line 654
def auto_arrange_step(groups=@groups)
        pattern_layout_col(groups) or pattern_layout_line(groups) or
                pattern_layout_ifend(groups) or pattern_layout_complex(groups) or
                layout_layers(groups)
end
auto_arrange_vertical_shrink() click to toggle source
# File metasm/gui/dasm_graph.rb, line 677
def auto_arrange_vertical_shrink
        # vertical shrink
        # TODO stuff may shrink vertically more if we could move it slightly horizontally...
        @box.sort_by { |b| b.y }.each { |b|

                next if b.from.empty?
                # move box up to its from, unless something blocks the way

                min_y = b.from.map { |bb|
                                bb.y+bb.h
                        }.find_all { |by|
                                by <= b.y
                        }.max

                moo = []
                moo << 8*b.from.length
                moo << 8*b.from[0].to.length
                cx = b.x+b.w/2
                moo << b.from.map { |bb| (cx - (bb.x+bb.w/2)).abs }.max / 10
                cx = b.from[0].x+b.from[0].w/2
                moo << b.from[0].to.map { |bb| (cx - (bb.x+bb.w/2)).abs }.max / 10
                margin_y = 16 + moo.max

                next if not min_y or b.y <= min_y + margin_y

                blocking = @box.find_all { |bb|
                                next if bb == b
                                bb.y+bb.h > min_y and bb.y+bb.h < b.y and
                                bb.x-12 < b.x+b.w and bb.x+bb.w+12 > b.x
                        }

                may_y = blocking.map { |bb| bb.y+bb.h } << min_y

                do_y = may_y.sort.map { |by| by + margin_y }.find { |by|
                        # should not collision with b if moved to by+margin_y
                        not blocking.find { |bb|
                                bb.x-12 < b.x+b.w and bb.x+bb.w+12 > b.x and
                                bb.y-12 < by+b.h and bb.y+bb.h+12 > by
                        }
                }

                b.y = do_y if do_y < b.y

                # no need to re-sort outer loop
        }

        # TODO
        # energy-minimal positionning of boxes from this basic layout
        # avoid arrow confusions
end
boundingbox() click to toggle source

returns the [x1, y1, x2, y2] of the rectangle encompassing all boxes

# File metasm/gui/dasm_graph.rb, line 57
def boundingbox
        minx = @box.map { |b| b.x }.min.to_i
        miny = @box.map { |b| b.y }.min.to_i
        maxx = @box.map { |b| b.x + b.w }.max.to_i
        maxy = @box.map { |b| b.y + b.h }.max.to_i
        [minx, miny, maxx, maxy]
end
can_find_path(src, dst, done={}) click to toggle source

checks if there is a path from src to dst avoiding stuff in 'done'

# File metasm/gui/dasm_graph.rb, line 397
def can_find_path(src, dst, done={})
        todo = [src]
        while g = todo.pop
                next if done[g]
                return true if g == dst
                done[g] = true
                todo.concat g.to
        end
        false
end
clear() click to toggle source

empty @box

# File metasm/gui/dasm_graph.rb, line 34
def clear
        @box = []
        @box_id = {}
end
create_layers(groups, order) click to toggle source

group groups in layers of same order create dummy groups along long edges so that no path exists between non-contiguous layers

# File metasm/gui/dasm_graph.rb, line 438
def create_layers(groups, order)
        newemptybox = lambda {
                b = Box.new(nil, [])
                b.x = -8
                b.y = -9
                b.w = 16
                b.h = 18
                groups << b
                b
        }

        newboxo = {}

        order.each_key { |g|
                og = order[g] || newboxo[g]
                g.to.dup.each { |gg|
                        ogg = order[gg] || newboxo[gg]
                        if ogg > og+1
                                # long edge, expand
                                sq = [g]
                                (ogg - 1 - og).times { |i| sq << newemptybox[] }
                                sq << gg
                                gg.from.delete g
                                g.to.delete gg
                                newboxo[g] ||= order[g]
                                sq.inject { |g1, g2|
                                        g1.to |= [g2]
                                        g2.from |= [g1]
                                        newboxo[g2] = newboxo[g1]+1
                                        g2
                                }
                                raise if newboxo[gg] != ogg
                        end
                }
        }

        order.update newboxo

        # layers[o] = [list of nodes of order o]
        layers = []
        groups.each { |g|
                (layers[order[g]] ||= []) << g
        }

        layers
end
dump_layout(groups=@groups) click to toggle source

gives a text representation of the current graph state

# File metasm/gui/dasm_graph.rb, line 736
def dump_layout(groups=@groups)
        groups.map { |g| "#{groups.index(g)} -> #{g.to.map { |t| groups.index(t) }.sort.inspect}" }
end
group_remove_hz_margin(g, maxw=16) click to toggle source

if a group has no content close to its x/x+w borders, shrink it

# File metasm/gui/dasm_graph.rb, line 110
def group_remove_hz_margin(g, maxw=16)
        if g.content.empty?
                g.x = -maxw/2 if g.x < -maxw/2
                g.w = maxw if g.w > maxw
                return
        end

        margin_left = g.content.map { |b| b.x }.min - g.x
        margin_right = g.x+g.w - g.content.map { |b| b.x+b.w }.max
        if margin_left + margin_right > maxw
                g.w -= margin_left + margin_right - maxw
                dx = (maxw/2 + margin_right - margin_left)/2
                g.content.each { |b| b.x += dx }
                g.x = -g.w/2
        end
end
layout_layers(groups) click to toggle source

take all groups, order them by order, layout as layers always return a single group holding everything

# File metasm/gui/dasm_graph.rb, line 487
def layout_layers(groups)
        order = order_graph(groups)
        # already a tree
        layers = create_layers(groups, order)
        return if layers.empty?

        layers.each { |l| l.each { |g| group_remove_hz_margin(g) } }

        # widest layer width
        maxlw = layers.map { |l| l.inject(0) { |ll, g| ll + g.w } }.max

        # center the 1st layer boxes on a segment that large
        x0 = -maxlw/2.0
        curlw = layers[0].inject(0) { |ll, g| ll + g.w }
        dx0 = (maxlw - curlw) / (2.0*layers[0].length)
        layers[0].each { |g|
                x0 += dx0
                g.x = x0
                x0 += g.w + dx0
        }

        # at this point, the goal is to reorder the most populated layer the best we can, and
        # move other layers' boxes accordingly
        layers[1..-1].each { |l|
                # for each subsequent layer, reorder boxes based on their ties with the previous layer
                i = 0
                l.replace l.sort_by { |g|
                        # we know g.from is not empty (g would be in @layer[0])
                        medfrom = g.from.inject(0.0) { |mx, gg| mx + (gg.x + gg.w/2.0) } / g.from.length
                        # on ties, keep original order
                        [medfrom, i]
                }
                # now they are reordered, update their #x accordingly
                # evenly distribute them in the layer
                x0 = -maxlw/2.0
                curlw = l.inject(0) { |ll, g| ll + g.w }
                dx0 = (maxlw - curlw) / (2.0*l.length)
                l.each { |g|
                        x0 += dx0
                        g.x = x0
                        x0 += g.w + dx0
                }
        }

        layers[0...-1].reverse_each { |l|
                # for each subsequent layer, reorder boxes based on their ties with the previous layer
                i = 0
                l.replace l.sort_by { |g|
                        if g.to.empty?
                                # TODO floating end
                                medfrom = 0
                        else
                                medfrom = g.to.inject(0.0) { |mx, gg| mx + (gg.x + gg.w/2.0) } / g.to.length
                        end
                        # on ties, keep original order
                        [medfrom, i]
                }
                # now they are reordered, update their #x accordingly
                x0 = -maxlw/2.0
                curlw = l.inject(0) { |ll, g| ll + g.w }
                dx0 = (maxlw - curlw) / (2.0*l.length)
                l.each { |g|
                        x0 += dx0
                        g.x = x0
                        x0 += g.w + dx0
                }
        }

        # now the boxes are (hopefully) sorted correctly
        # position them according to their ties with prev/next layer
        # from the maxw layer (positionning = packed), propagate adjacent layers positions
        maxidx = (0..layers.length).find { |i| l = layers[i] ; l.inject(0) { |ll, g| ll + g.w } == maxlw }
        # list of layer indexes to walk
        ilist = [maxidx]
        ilist.concat((maxidx+1...layers.length).to_a) if maxidx < layers.length-1
        ilist.concat((0..maxidx-1).to_a.reverse) if maxidx > 0
        layerbox = []
        ilist.each { |i|
                l = layers[i]
                curlw = l.inject(0) { |ll, g| ll + g.w }
                # left/rightmost acceptable position for the current box w/o overflowing on the right side
                minx = -maxlw/2.0
                maxx = minx + (maxlw-curlw)

                # replace whole layer with a box
                newg = layerbox[i] = Box.new(nil, l.map { |g| g.content }.flatten)
                newg.w = maxlw
                newg.h = l.map { |g| g.h }.max
                newg.x = -newg.w/2
                newg.y = -newg.h/2
                # dont care for from/to, we'll return a single box anyway

                l.each { |g|
                        ref = (i < maxidx) ? g.to : g.from
                        # TODO elastic positionning around the ideal position
                        # (g and g+1 may have the same med, then center both on it)
                        if i == maxidx
                                nx = minx
                        elsif ref.empty?
                                nx = (minx+maxx)/2
                        else
                                # center on the outline of rx
                                # may want to center on rx center's center ?
                                rx = ref.sort_by { |gg| gg.x }
                                med = (rx.first.x + rx.last.x + rx.last.w - g.w) / 2.0
                                nx = [[med, minx].max, maxx].min
                        end
                        dx = nx+g.w/2
                        g.content.each { |b| b.x += dx }
                        minx = nx+g.w
                        maxx += g.w
                }
        }

        newg = Box.new(nil, layerbox.map { |g| g.content }.flatten)
        newg.w = layerbox.map { |g| g.w }.max
        newg.h = layerbox.inject(0) { |h, g| h + g.h }
        newg.x = -newg.w/2
        newg.y = -newg.h/2

        # vertical: just center each box on its layer
        y0 = newg.y
        layerbox.each { |lg|
                lg.content.each { |b|
                        b.y += y0-lg.y
                }
                y0 += lg.h
        }

        groups.replace [newg]
end
list_reachable(src, done={}) click to toggle source

returns a hash with true for every node reachable from src (included)

# File metasm/gui/dasm_graph.rb, line 409
def list_reachable(src, done={})
        todo = [src]
        while g = todo.pop
                next if done[g]
                done[g] = true
                todo.concat g.to
        end
        done
end
make_tree(groups, order) click to toggle source

revert looping edges in groups

# File metasm/gui/dasm_graph.rb, line 420
def make_tree(groups, order)
        # now we have the roots and node orders
        #  revert cycling edges - o(chld) < o(parent)
        order.each_key { |g|
                g.to.dup.each { |gg|
                        if order[gg] < order[g]
                                # cycling edge, revert
                                g.to.delete gg
                                gg.from.delete g
                                g.from |= [gg]
                                gg.to |= [g]
                        end
                }
        }
end
new_box(id, content=nil) click to toggle source

creates a new box, ensures id is not already taken

# File metasm/gui/dasm_graph.rb, line 48
def new_box(id, content=nil)
        raise "duplicate id #{id}" if @box_id[id]
        b = Box.new(id, content)
        @box << b
        @box_id[id] = b
        b
end
order_graph(groups) click to toggle source

find the minimal set of nodes from which we can reach all others this is done before removing cycles in the graph returns the order (Hash group => group_order) roots have an order of 0

# File metasm/gui/dasm_graph.rb, line 317
def order_graph(groups)
        roots = groups.find_all { |g| g.from.empty? }
        o = {}        # tentative order
        todo = []

        loop do
                roots.each { |g|
                        o[g] ||= 0
                        todo |= g.to.find_all { |gg| not o[gg] }
                }

                # order nodes from the tentative roots
                until todo.empty?
                        n = todo.find { |g| g.from.all? { |gg| o[gg] } } || order_solve_cycle(todo, o)
                        todo.delete n
                        o[n] = n.from.map { |g| o[g] }.compact.max + 1
                        todo |= n.to.find_all { |g| not o[g] }
                end
                break if o.length >= groups.length

                # pathological cases

                if noroot = groups.find_all { |g| o[g] and g.from.find { |gg| not o[gg] } }.sort_by { |g| o[g] }.first
                        # we picked a root in the middle of the graph, walk up
                        todo |= noroot.from.find_all { |g| not o[g] }
                        until todo.empty?
                                n = todo.find { |g| g.to.all? { |gg| o[gg] } } ||
                                    todo.sort_by { |g| g.to.map { |gg| o[gg] }.compact.min }.first
                                todo.delete n
                                o[n] = n.to.map { |g| o[g] }.compact.min - 1
                                todo |= n.from.find_all { |g| not o[g] }
                        end
                        # setup todo for next fwd iteration
                        todo |= groups.find_all { |g| not o[g] and g.from.find { |gg| o[gg] } }
                else
                        # disjoint graph, start over from one other random node
                        roots << groups.find { |g| not o[g] }
                end
        end

        if o.values.find { |rank| rank < 0 }
                # did hit a pathological case, restart with found real roots
                roots = groups.find_all { |g| not g.from.find { |gg| o[gg] < o[g] } }
                o = {}
                todo = []
                roots.each { |g|
                        o[g] ||= 0
                        todo |= g.to.find_all { |gg| not o[gg] }
                }
                until todo.empty?
                        n = todo.find { |g| g.from.all? { |gg| o[gg] } } || order_solve_cycle(todo, o)
                        todo.delete n
                        o[n] = n.from.map { |g| o[g] }.compact.max + 1
                        todo |= n.to.find_all { |g| not o[g] }
                end

                # there's something screwy around here !
                raise "moo" if o.length < groups.length
        end

        o
end
order_solve_cycle(todo, o) click to toggle source
# File metasm/gui/dasm_graph.rb, line 380
def order_solve_cycle(todo, o)
        # 'todo' has no trivial candidate
        # pick one node from todo which no other todo can reach
        # exclude pathing through already ordered nodes
        todo.find { |t1|
                not todo.find { |t2| t1 != t2 and can_find_path(t2, t1, o.dup) }
        } ||
        # some cycle heads are mutually recursive
        todo.sort_by { |t1|
                # find the one who can reach the most others
                [todo.find_all { |t2| t1 != t2 and can_find_path(t1, t2, o.dup) }.length,
                # and with the highest rank
                 t1.from.map { |gg| o[gg] }.compact.max]
        }.last
end
pattern_layout_col(groups) click to toggle source

a -> b -> c -> d (no other in/outs)

# File metasm/gui/dasm_graph.rb, line 66
def pattern_layout_col(groups)
        # find head
        return if not head = groups.find { |g|
                g.to.length == 1 and
                g.to[0].from.length == 1 and
                (g.from.length != 1 or g.from[0].to.length != 1)
        }

        # find full sequence
        ar = [head]
        while head.to.length == 1 and head.to[0].from.length == 1
                head = head.to[0]
                ar << head
        end

        # move boxes inside this group
        maxw = ar.map { |g| g.w }.max
        fullh = ar.inject(0) { |h, g| h + g.h }
        cury = -fullh/2
        ar.each { |g|
                dy = cury - g.y
                g.content.each { |b| b.y += dy }
                cury += g.h
        }

        # create remplacement group
        newg = Box.new(nil, ar.map { |g| g.content }.flatten)
        newg.w = maxw
        newg.h = fullh
        newg.x = -newg.w/2
        newg.y = -newg.h/2
        newg.from = ar.first.from - ar
        newg.to = ar.last.to - ar
        # fix xrefs
        newg.from.each { |g| g.to -= ar ; g.to << newg }
        newg.to.each { |g| g.from -= ar ; g.from << newg }
        # fix groups
        groups[groups.index(head)] = newg
        ar.each { |g| groups.delete g }

        true
end
pattern_layout_complex(groups) click to toggle source
# File metasm/gui/dasm_graph.rb, line 234
def pattern_layout_complex(groups)
        order = order_graph(groups)
        uniq = nil
        if groups.sort_by { |g| order[g] }.find { |g|
                next if g.to.length <= 1
                # list all nodes reachable for every 'to'
                reach = g.to.map { |t| list_reachable(t) }
                # list all nodes reachable only from a single 'to'
                uniq = []
                reach.each_with_index { |r, i|
                        # take all nodes reachable from there ...
                        u = uniq[i] = r.dup
                        u.delete_if { |k, v| k.content.empty? }     # ignore previous layout_complex artifacts
                        reach.each_with_index { |rr, ii|
                                next if i == ii
                                # ... and delete nodes reachable from anywhere else
                                rr.each_key { |k| u.delete k }
                        }
                }
                uniq.delete_if { |u| u.length <= 1 }
                !uniq.empty?
        }
                # now layout every uniq subgroup independently
                uniq.each { |u|
                        subgroups = groups.find_all { |g| u[g] }

                        # isolate subgroup from external links
                        # change all external links into a single empty box
                        newtop = Box.new(nil, [])
                        newtop.x = -8 ; newtop.y = -9
                        newtop.w = 16 ; newtop.h = 18
                        newbot = Box.new(nil, [])
                        newbot.x = -8 ; newbot.y = -9
                        newbot.w = 16 ; newbot.h = 18
                        hadfrom = [] ; hadto = []
                        subgroups.each { |g|
                                g.to.dup.each { |t|
                                        next if u[t]
                                        newbot.from |= [g]
                                        g.to.delete t
                                        hadto << t
                                        g.to |= [newbot]
                                }
                                g.from.dup.each { |f|
                                        next if u[f]
                                        newtop.to |= [g]
                                        g.from.delete f
                                        hadfrom << f
                                        g.from |= [newtop]
                                }
                        }
                        subgroups << newtop << newbot

                        # subgroup layout
                        auto_arrange_step(subgroups) while subgroups.length > 1
                        newg = subgroups[0]

                        # patch 'groups'
                        idx = groups.index { |g| u[g] }
                        groups.delete_if { |g| u[g] }
                        groups[idx, 0] = [newg]

                        # restore external links & fix xrefs
                        hadfrom.uniq.each { |f|
                                f.to.delete_if { |t| u[t] }
                                f.to |= [newg]
                                newg.from |= [f]
                        }
                        hadto.uniq.each { |t|
                                t.from.delete_if { |f| u[f] }
                                t.from |= [newg]
                                newg.to |= [t]
                        }
                }

                true
        end
end
pattern_layout_ifend(groups) click to toggle source

a -> b -> c & a -> c

# File metasm/gui/dasm_graph.rb, line 189
def pattern_layout_ifend(groups)
        # find head
        return if not head = groups.find { |g|
                g.to.length == 2 and
                ((g.to[0].from.length == 1 and g.to[0].to.length == 1 and g.to[0].to[0] == g.to[1]) or
                 (g.to[1].from.length == 1 and g.to[1].to.length == 1 and g.to[1].to[0] == g.to[0]))
        }

        if head.to[0].to.include?(head.to[1])
                ten = head.to[0]
        else
                ten = head.to[1]
        end

        # stuff 'then' inside the 'if'
        # move 'if' up, 'then' down
        head.content.each { |g| g.y -= ten.h/2 }
        ten.content.each { |g| g.y += head.h/2 }
        head.h += ten.h
        head.y -= ten.h/2

        # widen 'if'
        # this adds a phantom left side
        # drop existing margins first
        group_remove_hz_margin(ten)
        dw = ten.w - head.w/2
        if dw > 0
                # need to widen head to fit ten
                head.w += 2*dw
                head.x -= dw
        end

        # merge
        ten.content.each { |g| g.x += -ten.x }
        head.content.concat ten.content

        head.to.delete ten
        head.to[0].from.delete ten

        groups.delete ten

        true

end
pattern_layout_line(groups) click to toggle source

a -> [b, c, d] -> e

# File metasm/gui/dasm_graph.rb, line 128
def pattern_layout_line(groups)
        # find head
        ar = []
        groups.each { |g|
                if g.from.length == 1 and g.to.length <= 1 and g.from.first.to.length > 1
                        ar = g.from.first.to.find_all { |gg| gg.from == g.from and gg.to == g.to }
                elsif g.from.empty? and g.to.length == 1 and g.to.first.from.length > 1
                        ar = g.to.first.from.find_all { |gg| gg.from == g.from and gg.to == g.to }
                else ar = []
                end
                break if ar.length > 1
        }
        return if ar.length <= 1

        ar.each { |g| group_remove_hz_margin(g) }

        # move boxes inside this group
        #ar = ar.sort_by { |g| -g.h }
        maxh = ar.map { |g| g.h }.max
        fullw = ar.inject(0) { |w, g| w + g.w }
        curx = -fullw/2
        ar.each { |g|
                # if no to, put all boxes at bottom ; if no from, put them at top
                case [g.from.length, g.to.length]
                when [1, 0]; dy = (g.h - maxh)/2
                when [0, 1]; dy = (maxh - g.h)/2
                else dy = 0
                end

                dx = curx - g.x
                g.content.each { |b| b.x += dx ; b.y += dy }
                curx += g.w
        }
        # add a 'margin-top' proportionnal to the ar width
        # this gap should be relative to the real boxes and not possible previous gaps when
        # merging lines (eg long line + many if patterns -> dont duplicate gaps)
        boxen = ar.map { |g| g.content }.flatten
        realh = boxen.map { |g| g.y + g.h }.max - boxen.map { |g| g.y }.min
        if maxh < realh + fullw/4
                maxh = realh + fullw/4
        end

        # create remplacement group
        newg = Box.new(nil, ar.map { |g| g.content }.flatten)
        newg.w = fullw
        newg.h = maxh
        newg.x = -newg.w/2
        newg.y = -newg.h/2
        newg.from = ar.first.from
        newg.to = ar.first.to
        # fix xrefs
        newg.from.each { |g| g.to -= ar ; g.to << newg }
        newg.to.each { |g| g.from -= ar ; g.from << newg }
        # fix groups
        groups[groups.index(ar.first)] = newg
        ar.each { |g| groups.delete g }

        true
end