class Metasm::Gui::Graph
Attributes
Public Class Methods
# 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
# 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
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
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
# File metasm/gui/dasm_graph.rb, line 660 def auto_arrange_post auto_arrange_movebox #auto_arrange_vertical_shrink end
# 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
# 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
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
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
empty @box
# File metasm/gui/dasm_graph.rb, line 34 def clear @box = [] @box_id = {} end
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
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
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
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
link the two boxes (by id)
# File metasm/gui/dasm_graph.rb, line 40 def link_boxes(id1, id2) raise "unknown index 1 #{id1}" if not b1 = @box_id[id1] raise "unknown index 2 #{id2}" if not b2 = @box_id[id2] b1.to |= [b2] b2.from |= [b1] end
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
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
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
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
# 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
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
# 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
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
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