1 /* Copyright radare2 - 2014-2021 - pancake, ret2libc */
2
3 #include <r_core.h>
4 #include <r_cons.h>
5 #include <r_util/r_graph_drawable.h>
6 #include <ctype.h>
7 #include <limits.h>
8
9 static int mousemode = 0;
10 static int disMode = 0;
11 static int discroll = 0;
12 static bool graphCursor = false;
13 static const char *mousemodes[] = {
14 "canvas-y",
15 "canvas-x",
16 "node-y",
17 "node-x",
18 NULL
19 };
20
21 #define GRAPH_MERGE_FEATURE 0
22
23 #define BORDER 3
24 #define BORDER_WIDTH 4
25 #define BORDER_HEIGHT 3
26 #define MARGIN_TEXT_X 2
27 #define MARGIN_TEXT_Y 2
28 #define HORIZONTAL_NODE_SPACING 4
29 #define VERTICAL_NODE_SPACING 2
30 #define MIN_NODE_WIDTH 22
31 #define MIN_NODE_HEIGHT BORDER_HEIGHT
32 #define TITLE_LEN 128
33 #define DEFAULT_SPEED 1
34 #define PAGEKEY_SPEED (h / 2)
35 /* 15 */
36 #define MINIGRAPH_NODE_TEXT_CUR "<@@@@@@>"
37 #define MINIGRAPH_NODE_MIN_WIDTH 12
38 #define MINIGRAPH_NODE_TITLE_LEN 4
39 #define MINIGRAPH_NODE_CENTER_X 3
40 #define MININODE_MIN_WIDTH 16
41
42 #define ZOOM_STEP 10
43 #define ZOOM_DEFAULT 100
44
45 #define BODY_OFFSETS 0x1
46 #define BODY_SUMMARY 0x2
47 #define BODY_COMMENTS 0x4
48
49 #define NORMALIZE_MOV(x) ((x) < 0 ? -1 : ((x) > 0 ? 1 : 0))
50
51 #define hash_set(sdb, k, v) (sdb_num_set (sdb, sdb_fmt ("%"PFMT64u, (ut64) (size_t) (k)), (ut64) (size_t) (v), 0))
52 #define hash_get(sdb, k) (sdb_num_get (sdb, sdb_fmt ("%"PFMT64u, (ut64) (size_t) (k)), NULL))
53 #define hash_get_rnode(sdb, k) ((RGraphNode *) (size_t) hash_get (sdb, k))
54 #define hash_get_rlist(sdb, k) ((RList *) (size_t) hash_get (sdb, k))
55 #define hash_get_int(sdb, k) ((int) hash_get (sdb, k))
56 /* don't use macros for this */
57 #define get_anode(gn) ((gn)? (RANode *) (gn)->data: NULL)
58
59 #define graph_foreach_anode(list, it, pos, anode)\
60 if (list) for ((it) = (list)->head; (it) && ((pos) = (it)->data) && (pos) && ((anode) = (RANode *) (pos)->data); (it) = (it)->n)
61
62 struct len_pos_t {
63 int len;
64 int pos;
65 };
66
67 struct dist_t {
68 const RGraphNode *from;
69 const RGraphNode *to;
70 int dist;
71 };
72
73 struct g_cb {
74 RAGraph *graph;
75 RANodeCallback node_cb;
76 RAEdgeCallback edge_cb;
77 void *data;
78 };
79
80 typedef struct ascii_edge_t {
81 RANode *from;
82 RANode *to;
83 RList *x, *y;
84 int is_reversed;
85 } AEdge;
86
87 struct layer_t {
88 int n_nodes;
89 RGraphNode **nodes;
90 int position;
91 int height;
92 int width;
93 int gap;
94 };
95
96 struct agraph_refresh_data {
97 RCore *core;
98 RAGraph *g;
99 RAnalFunction **fcn;
100 bool follow_offset;
101 int fs;
102 };
103
104 struct r_agraph_location {
105 int x;
106 int y;
107 };
108
109 #define G(x, y) r_cons_canvas_gotoxy (g->can, x, y)
110 #define W(x) r_cons_canvas_write (g->can, x)
111 #define F(x, y, x2, y2, c) r_cons_canvas_fill (g->can, x, y, x2, y2, c)
112
is_offset(const RAGraph * g)113 static bool is_offset(const RAGraph *g) {
114 return g->mode == R_AGRAPH_MODE_OFFSET;
115 }
116
is_mini(const RAGraph * g)117 static bool is_mini(const RAGraph *g) {
118 return g->mode == R_AGRAPH_MODE_MINI;
119 }
120
is_tiny(const RAGraph * g)121 static bool is_tiny(const RAGraph *g) {
122 return g->is_tiny || g->mode == R_AGRAPH_MODE_TINY;
123 }
124
is_summary(const RAGraph * g)125 static bool is_summary(const RAGraph *g) {
126 return g->mode == R_AGRAPH_MODE_SUMMARY;
127 }
128
is_comments(const RAGraph * g)129 static bool is_comments(const RAGraph *g) {
130 return g->mode == R_AGRAPH_MODE_COMMENTS;
131 }
132
next_mode(int mode)133 static int next_mode(int mode) {
134 return (mode + 1) % R_AGRAPH_MODE_MAX;
135 }
136
prev_mode(int mode)137 static int prev_mode(int mode) {
138 return (mode + R_AGRAPH_MODE_MAX - 1) % R_AGRAPH_MODE_MAX;
139 }
140
agraph_get_title(const RAGraph * g,RANode * n,bool in)141 static RGraphNode *agraph_get_title(const RAGraph *g, RANode *n, bool in) {
142 if (!n) {
143 return NULL;
144 }
145 if (n->title && *n->title) {
146 return n->gnode;
147 }
148 const RList *outnodes = in? n->gnode->in_nodes : n->gnode->out_nodes;
149 RGraphNode *gn;
150 RListIter *iter;
151
152 r_list_foreach (outnodes, iter, gn) {
153 RANode *an = gn->data;
154 return agraph_get_title (g, an, in);
155 }
156 return NULL;
157 }
158
mode2opts(const RAGraph * g)159 static int mode2opts(const RAGraph *g) {
160 int opts = 0;
161 if (is_offset (g)) {
162 opts |= BODY_OFFSETS;
163 }
164 if (is_comments (g)) {
165 opts |= BODY_COMMENTS;
166 }
167 if (is_summary (g)) {
168 opts |= BODY_SUMMARY;
169 }
170 return opts;
171 }
172
173 // duplicated from visual.c
rotateAsmemu(RCore * core)174 static void rotateAsmemu(RCore *core) {
175 const bool isEmuStr = r_config_get_i (core->config, "emu.str");
176 const bool isEmu = r_config_get_i (core->config, "asm.emu");
177 if (isEmu) {
178 if (isEmuStr) {
179 r_config_set (core->config, "emu.str", "false");
180 } else {
181 r_config_set (core->config, "asm.emu", "false");
182 }
183 } else {
184 r_config_set (core->config, "emu.str", "true");
185 }
186 }
187
showcursor(RCore * core,int x)188 static void showcursor(RCore *core, int x) {
189 if (!x) {
190 int wheel = r_config_get_i (core->config, "scr.wheel");
191 if (wheel) {
192 r_cons_enable_mouse (true);
193 }
194 } else {
195 r_cons_enable_mouse (false);
196 }
197 r_cons_show_cursor (x);
198 }
199
get_title(ut64 addr)200 static char *get_title(ut64 addr) {
201 return r_str_newf ("0x%"PFMT64x, addr);
202 }
203
204 static int agraph_refresh(struct agraph_refresh_data *grd);
205
update_node_dimension(const RGraph * g,int is_mini,int zoom,int edgemode,bool callgraph,int layout)206 static void update_node_dimension(const RGraph *g, int is_mini, int zoom, int edgemode, bool callgraph, int layout) {
207 const RList *nodes = r_graph_get_nodes (g);
208 RGraphNode *gn;
209 RListIter *it;
210 RANode *n;
211 graph_foreach_anode (nodes, it, gn, n) {
212 if (is_mini) {
213 n->h = 1;
214 n->w = MINIGRAPH_NODE_MIN_WIDTH;
215 } else if (n->is_mini) {
216 n->h = 1;
217 n->w = MININODE_MIN_WIDTH;
218 } else {
219 n->w = r_str_bounds (n->body, (int *) &n->h);
220 ut32 len = strlen (n->title) + MARGIN_TEXT_X;
221 if (len > INT_MAX) {
222 len = INT_MAX;
223 }
224 if (len > n->w) {
225 n->w = len;
226 }
227 // n->w = n->w; //R_MIN (n->w, (int)len);
228 n->w += BORDER_WIDTH;
229 n->h += BORDER_HEIGHT;
230 /* scale node by zoom */
231 n->w = R_MAX (MIN_NODE_WIDTH, (n->w * zoom) / 100);
232 n->h = R_MAX (MIN_NODE_HEIGHT, (n->h * zoom) / 100);
233
234 if (edgemode == 2 && !callgraph) {
235 if (!layout) {
236 n->w = R_MAX (n->w, (r_list_length (n->gnode->out_nodes) * 2 + 1) + R_EDGES_X_INC * 2);
237 n->w = R_MAX (n->w, (r_list_length (n->gnode->in_nodes) * 2 + 1) + R_EDGES_X_INC * 2);
238 } else {
239 n->h = R_MAX (n->h, (r_list_length (n->gnode->out_nodes) + 1) + R_EDGES_X_INC);
240 n->h = R_MAX (n->h, (r_list_length (n->gnode->in_nodes) + 1) + R_EDGES_X_INC);
241 }
242 }
243 }
244 }
245 }
246
append_shortcut(const RAGraph * g,char * title,char * nodetitle,int left)247 static void append_shortcut (const RAGraph *g, char *title, char *nodetitle, int left) {
248 const char *shortcut = sdb_const_get (g->db, sdb_fmt ("agraph.nodes.%s.shortcut", nodetitle), 0);
249 if (shortcut) {
250 size_t n = strlen (title);
251 if (g->can->color) {
252 // XXX: do not hardcode color here
253 snprintf (title + n, left, "%s", sdb_fmt (Color_YELLOW"[o%s]"Color_RESET, shortcut));
254 } else {
255 snprintf (title + n, left, "%s", sdb_fmt ("[o%s]", shortcut));
256 }
257 }
258 }
259
mini_RANode_print(const RAGraph * g,const RANode * n,int cur,bool details)260 static void mini_RANode_print(const RAGraph *g, const RANode *n, int cur, bool details) {
261 char title[TITLE_LEN];
262 int x, delta_x = 0;
263
264 if (!G (n->x + MINIGRAPH_NODE_CENTER_X, n->y) &&
265 !G (n->x + MINIGRAPH_NODE_CENTER_X + n->w, n->y)) {
266 return;
267 }
268
269 x = n->x + MINIGRAPH_NODE_CENTER_X + g->can->sx;
270 if (x < 0) {
271 delta_x = -x;
272 }
273 if (!G (n->x + MINIGRAPH_NODE_CENTER_X + delta_x, n->y)) {
274 return;
275 }
276
277 if (details) {
278 if (cur) {
279 W (&MINIGRAPH_NODE_TEXT_CUR[delta_x]);
280 (void) G (-g->can->sx, -g->can->sy + 2);
281 snprintf (title, sizeof (title) - 1,
282 "[ %s ]", n->title);
283 W (title);
284 if (discroll > 0) {
285 char *body = r_str_ansi_crop (n->body, 0, discroll, -1, -1);
286 (void) G (-g->can->sx, -g->can->sy + 3);
287 W (body);
288 free (body);
289 } else {
290 (void) G (-g->can->sx, -g->can->sy + 3);
291 W (n->body);
292 }
293 } else {
294 char *str = "____";
295 if (n->title) {
296 int l = strlen (n->title);
297 str = n->title;
298 if (l > MINIGRAPH_NODE_TITLE_LEN) {
299 str += l - MINIGRAPH_NODE_TITLE_LEN;
300 }
301 }
302 if (g->can->color) {
303 snprintf (title, sizeof (title) - 1, "%s__%s__", Color_RESET, str);
304 } else {
305 snprintf (title, sizeof (title) - 1, "__%s__", str);
306 }
307 append_shortcut (g, title, n->title, sizeof (title) - strlen (title));
308 W (r_str_ansi_crop (title, delta_x, 0, 20, 1));
309 }
310 } else {
311 snprintf (title, sizeof (title) - 1,
312 cur? "[ %s ]": " %s ", n->title);
313 W (title);
314 }
315 return;
316 }
317
tiny_RANode_print(const RAGraph * g,const RANode * n,int cur)318 static void tiny_RANode_print(const RAGraph *g, const RANode *n, int cur) {
319 G (n->x, n->y);
320 RCons *cons = r_cons_singleton ();
321 char *circle = cons->use_utf8 ? UTF_CIRCLE :"()";
322 if (cur) {
323 W ("##");
324 } else {
325 W (circle);
326 }
327 }
328
get_node_color(int color,int cur)329 static char *get_node_color(int color, int cur) {
330 RCons *cons = r_cons_singleton ();
331 if (color == -1) {
332 return cur ? cons->context->pal.graph_box2 : cons->context->pal.graph_box;
333 }
334 return color ? (\
335 color==R_ANAL_DIFF_TYPE_MATCH ? cons->context->pal.graph_diff_match:
336 color==R_ANAL_DIFF_TYPE_UNMATCH? cons->context->pal.graph_diff_unmatch : cons->context->pal.graph_diff_new): cons->context->pal.graph_diff_unknown;
337 }
338
normal_RANode_print(const RAGraph * g,const RANode * n,int cur)339 static void normal_RANode_print(const RAGraph *g, const RANode *n, int cur) {
340 ut32 center_x = 0, center_y = 0;
341 ut32 delta_x = 0, delta_txt_x = 0;
342 ut32 delta_y = 0, delta_txt_y = 0;
343 char title[TITLE_LEN];
344 char *body;
345 int x, y;
346 int color = n->difftype;
347 const bool showTitle = g->show_node_titles;
348 const bool showBody = g->show_node_body;
349
350 x = n->x + g->can->sx;
351 y = n->y + g->can->sy;
352 if (x + MARGIN_TEXT_X < 0) {
353 delta_x = -(x + MARGIN_TEXT_X);
354 }
355 if (x + n->w < -MARGIN_TEXT_X) {
356 return;
357 }
358 if (y < -1) {
359 delta_y = R_MIN (n->h - BORDER_HEIGHT - 1, -y - MARGIN_TEXT_Y);
360 }
361 /* print the title */
362 if (showTitle) {
363 if (cur) {
364 snprintf (title, sizeof (title) - 1, "[%s]", n->title);
365 } else {
366 char *color = g->can->color ? Color_RESET : "";
367 snprintf (title, sizeof (title) - 1, " %s%s ", color, n->title);
368 append_shortcut (g, title, n->title, sizeof (title) - strlen (title));
369 }
370 if ((delta_x < strlen (title)) && G (n->x + MARGIN_TEXT_X + delta_x, n->y + 1)) {
371 char *res = r_str_ansi_crop (title, delta_x, 0, n->w - BORDER_WIDTH, 1);
372 W (res);
373 W (Color_RESET);
374 free (res);
375 }
376 }
377
378 /* print the body */
379 if (g->zoom > ZOOM_DEFAULT) {
380 center_x = (g->zoom - ZOOM_DEFAULT) / 10;
381 center_y = (g->zoom - ZOOM_DEFAULT) / 30;
382 delta_txt_x = R_MIN (delta_x, center_x);
383 delta_txt_y = R_MIN (delta_y, center_y);
384 }
385 if (showBody) {
386 if (G (n->x + MARGIN_TEXT_X + delta_x + center_x - delta_txt_x,
387 n->y + MARGIN_TEXT_Y + delta_y + center_y - delta_txt_y)) {
388 ut32 body_x = center_x >= delta_x? 0: delta_x - center_x;
389 ut32 body_y = center_y >= delta_y? 0: delta_y - center_y;
390 ut32 body_h = BORDER_HEIGHT >= n->h? 1: n->h - BORDER_HEIGHT;
391
392 if (g->zoom < ZOOM_DEFAULT) {
393 body_h--;
394 }
395 if (body_y + 1 <= body_h) {
396 body = r_str_ansi_crop (n->body,
397 body_x, body_y,
398 n->w - BORDER_WIDTH,
399 body_h);
400 if (body) {
401 W (body);
402 if (g->zoom < ZOOM_DEFAULT) {
403 W ("\n");
404 }
405 free (body);
406 } else {
407 W (n->body);
408 }
409 }
410 /* print some dots when the body is cropped because of zoom */
411 if (n->body && *n->body) {
412 if (body_y <= body_h && g->zoom < ZOOM_DEFAULT) {
413 char *dots = "...";
414 if (delta_x < strlen (dots)) {
415 dots += delta_x;
416 W (dots);
417 }
418 }
419 }
420 }
421 }
422
423 // TODO: check if node is traced or not and show proper color
424 // This info must be stored inside RANode* from RCore*
425 if (g->show_node_bubble) {
426 r_cons_canvas_circle (g->can, n->x, n->y, n->w, n->h, get_node_color (color, cur));
427 } else {
428 r_cons_canvas_box (g->can, n->x, n->y, n->w, n->h, get_node_color (color, cur));
429 }
430 if (n->color) {
431 const char *pad = r_str_pad ('#', n->w);
432 char *f = r_str_newf ("%s%s%s", n->color, pad, Color_RESET);
433 G (n->x, n->y);
434 W (f);
435 }
436 }
437
get_crossing_matrix(const RGraph * g,const struct layer_t layers[],int maxlayer,int i,int from_up,int * n_rows)438 static int **get_crossing_matrix(const RGraph *g,
439 const struct layer_t layers[],
440 int maxlayer, int i, int from_up,
441 int *n_rows) {
442 int j, len = layers[i].n_nodes;
443
444 int **m = R_NEWS0 (int *, len);
445 if (!m) {
446 return NULL;
447 }
448 for (j = 0; j < len; j++) {
449 m[j] = R_NEWS0 (int, len);
450 if (!m[j]) {
451 goto err_row;
452 }
453 }
454 /* calculate crossings between layer i and layer i-1 */
455 /* consider the crossings generated by each pair of edges */
456 if (i > 0 && from_up) {
457 if (r_cons_is_breaked ()) {
458 goto err_row;
459 }
460 for (j = 0; j < layers[i - 1].n_nodes; j++) {
461 const RGraphNode *gj = layers[i - 1].nodes[j];
462 const RList *neigh = r_graph_get_neighbours (g, gj);
463 RGraphNode *gk;
464 RListIter *itk;
465
466 r_list_foreach (neigh, itk, gk) {
467 int s;
468 // skip self-loop
469 if (gj == gk) {
470 continue;
471 }
472 for (s = 0; s < j; s++) {
473 const RGraphNode *gs = layers[i - 1].nodes[s];
474 const RList *neigh_s = r_graph_get_neighbours (g, gs);
475 RGraphNode *gt;
476 RListIter *itt;
477
478 r_list_foreach (neigh_s, itt, gt) {
479 const RANode *ak, *at; /* k and t should be "indexes" on layer i */
480 if (gt == gk || gt == gs) {
481 continue;
482 }
483 ak = get_anode (gk);
484 at = get_anode (gt);
485 if (ak->layer != i || at->layer != i) {
486 // this should never happen
487 // but it happens if we do graph.dummy = false, so better hide it for now
488 #if 0
489 eprintf ("(WARNING) \"%s\" (%d) or \"%s\" (%d) are not on the right layer (%d)\n",
490 ak->title, ak->layer,
491 at->title, at->layer,
492 i);
493 #endif
494 continue;
495 }
496 m[ak->pos_in_layer][at->pos_in_layer]++;
497 }
498 }
499 }
500 }
501 }
502
503 /* calculate crossings between layer i and layer i+1 */
504 if (i < maxlayer - 1 && !from_up) {
505 if (r_cons_is_breaked ()) {
506 goto err_row;
507 }
508 for (j = 0; j < layers[i].n_nodes; j++) {
509 const RGraphNode *gj = layers[i].nodes[j];
510 const RList *neigh = r_graph_get_neighbours (g, gj);
511 const RANode *ak, *aj = get_anode (gj);
512 RGraphNode *gk;
513 RListIter *itk;
514
515 if (r_cons_is_breaked ()) {
516 goto err_row;
517 }
518 graph_foreach_anode (neigh, itk, gk, ak) {
519 int s;
520 for (s = 0; s < layers[i].n_nodes; s++) {
521 const RGraphNode *gs = layers[i].nodes[s];
522 const RList *neigh_s;
523 RGraphNode *gt;
524 RListIter *itt;
525 const RANode *at, *as = get_anode (gs);
526
527 if (gs == gj) {
528 continue;
529 }
530 neigh_s = r_graph_get_neighbours (g, gs);
531 graph_foreach_anode (neigh_s, itt, gt, at) {
532 if (at->pos_in_layer < ak->pos_in_layer) {
533 m[aj->pos_in_layer][as->pos_in_layer]++;
534 }
535 }
536 }
537 }
538 }
539 }
540
541 if (n_rows) {
542 *n_rows = len;
543 }
544 return m;
545
546 err_row:
547 for (i = 0; i < len; i++) {
548 free (m[i]);
549 }
550 free (m);
551 return NULL;
552 }
553
layer_sweep(const RGraph * g,const struct layer_t layers[],int maxlayer,int i,int from_up)554 static int layer_sweep(const RGraph *g, const struct layer_t layers[],
555 int maxlayer, int i, int from_up) {
556 RGraphNode *u, *v;
557 const RANode *au, *av;
558 int n_rows, j, changed = false;
559 int len = layers[i].n_nodes;
560
561 int **cross_matrix = get_crossing_matrix (g, layers, maxlayer, i, from_up, &n_rows);
562 if (!cross_matrix) {
563 return -1; // ERROR HAPPENS
564 }
565
566 for (j = 0; j < len - 1; j++) {
567 int auidx, avidx;
568
569 u = layers[i].nodes[j];
570 v = layers[i].nodes[j + 1];
571 au = get_anode (u);
572 av = get_anode (v);
573 auidx = au->pos_in_layer;
574 avidx = av->pos_in_layer;
575
576 if (cross_matrix[auidx][avidx] > cross_matrix[avidx][auidx]) {
577 /* swap elements */
578 layers[i].nodes[j] = v;
579 layers[i].nodes[j + 1] = u;
580 changed = true;
581 }
582 }
583
584 /* update position in the layer of each node. During the swap of some
585 * elements we didn't swap also the pos_in_layer because the cross_matrix
586 * is indexed by it, so do it now! */
587 for (j = 0; j < layers[i].n_nodes; j++) {
588 RANode *n = get_anode (layers[i].nodes[j]);
589 n->pos_in_layer = j;
590 }
591
592 for (j = 0; j < n_rows; j++) {
593 free (cross_matrix[j]);
594 }
595 free (cross_matrix);
596 return changed;
597 }
598
view_cyclic_edge(const RGraphEdge * e,const RGraphVisitor * vis)599 static void view_cyclic_edge(const RGraphEdge *e, const RGraphVisitor *vis) {
600 const RAGraph *g = (RAGraph *) vis->data;
601 RGraphEdge *new_e = R_NEW0 (RGraphEdge);
602 if (!new_e) {
603 return;
604 }
605 new_e->from = e->from;
606 new_e->to = e->to;
607 new_e->nth = e->nth;
608 r_list_append (g->back_edges, new_e);
609 }
610
view_dummy(const RGraphEdge * e,const RGraphVisitor * vis)611 static void view_dummy(const RGraphEdge *e, const RGraphVisitor *vis) {
612 const RANode *a = get_anode (e->from);
613 const RANode *b = get_anode (e->to);
614 RList *long_edges = (RList *) vis->data;
615 if (!a || !b) {
616 return;
617 }
618 if (R_ABS (a->layer - b->layer) > 1) {
619 RGraphEdge *new_e = R_NEW0 (RGraphEdge);
620 if (!new_e) {
621 return;
622 }
623 new_e->from = e->from;
624 new_e->to = e->to;
625 new_e->nth = e->nth;
626 r_list_append (long_edges, new_e);
627 }
628 }
629
630 /* find a set of edges that, removed, makes the graph acyclic */
631 /* invert the edges identified in the previous step */
remove_cycles(RAGraph * g)632 static void remove_cycles(RAGraph *g) {
633 RGraphVisitor cyclic_vis = {
634 NULL, NULL, NULL, NULL, NULL, NULL
635 };
636 const RGraphEdge *e;
637 const RListIter *it;
638
639 g->back_edges = r_list_new ();
640 cyclic_vis.back_edge = (RGraphEdgeCallback) view_cyclic_edge;
641 cyclic_vis.data = g;
642 r_graph_dfs (g->graph, &cyclic_vis);
643
644 r_list_foreach (g->back_edges, it, e) {
645 RANode *from = e->from? get_anode (e->from): NULL;
646 RANode *to = e->to? get_anode (e->to): NULL;
647 if (from && to) {
648 r_agraph_del_edge (g, from, to);
649 r_agraph_add_edge_at (g, to, from, e->nth);
650 }
651 }
652 }
653
add_sorted(RGraphNode * n,RGraphVisitor * vis)654 static void add_sorted(RGraphNode *n, RGraphVisitor *vis) {
655 RList *l = (RList *) vis->data;
656 r_list_prepend (l, n);
657 }
658
659 /* assign a layer to each node of the graph.
660 *
661 * It visits the nodes of the graph in the topological sort, so that every time
662 * you visit a node, you can be sure that you have already visited all nodes
663 * that can lead to that node and thus you can easily compute the layer based
664 * on the layer of these "parent" nodes. */
assign_layers(const RAGraph * g)665 static void assign_layers(const RAGraph *g) {
666 RGraphVisitor layer_vis = {
667 NULL, NULL, NULL, NULL, NULL, NULL
668 };
669 const RGraphNode *gn;
670 const RListIter *it;
671 RANode *n;
672 RList *topological_sort = r_list_new ();
673
674 layer_vis.data = topological_sort;
675 layer_vis.finish_node = (RGraphNodeCallback) add_sorted;
676 r_graph_dfs (g->graph, &layer_vis);
677
678 graph_foreach_anode (topological_sort, it, gn, n) {
679 const RList *innodes = r_graph_innodes (g->graph, gn);
680 RListIter *it;
681 RGraphNode *prev;
682 RANode *preva;
683
684 n->layer = 0;
685 graph_foreach_anode (innodes, it, prev, preva) {
686 if (preva->layer + 1 > n->layer) {
687 n->layer = preva->layer + 1;
688 }
689 }
690 }
691
692 r_list_free (topological_sort);
693 }
694
find_edge(const RGraphEdge * a,const RGraphEdge * b)695 static int find_edge(const RGraphEdge *a, const RGraphEdge *b) {
696 return a->from == b->to && a->to == b->from? 0: 1;
697 }
698
is_reversed(const RAGraph * g,const RGraphEdge * e)699 static bool is_reversed(const RAGraph *g, const RGraphEdge *e) {
700 return (bool)r_list_find (g->back_edges, e, (RListComparator) find_edge);
701 }
702
703 /* add dummy nodes when there are edges that span multiple layers */
create_dummy_nodes(RAGraph * g)704 static void create_dummy_nodes(RAGraph *g) {
705 if (!g->dummy) {
706 return;
707 }
708 RGraphVisitor dummy_vis = {
709 NULL, NULL, NULL, NULL, NULL, NULL
710 };
711 const RListIter *it;
712 const RGraphEdge *e;
713
714 g->long_edges = r_list_newf ((RListFree)free);
715 dummy_vis.data = g->long_edges;
716 dummy_vis.tree_edge = (RGraphEdgeCallback) view_dummy;
717 dummy_vis.fcross_edge = (RGraphEdgeCallback) view_dummy;
718 r_graph_dfs (g->graph, &dummy_vis);
719
720 r_list_foreach (g->long_edges, it, e) {
721 RANode *from = get_anode (e->from);
722 RANode *to = get_anode (e->to);
723 int diff_layer = R_ABS (from->layer - to->layer);
724 RANode *prev = get_anode (e->from);
725 int i, nth = e->nth;
726
727 r_agraph_del_edge (g, from, to);
728 for (i = 1; i < diff_layer; i++) {
729 RANode *dummy = r_agraph_add_node (g, NULL, NULL, NULL);
730 if (!dummy) {
731 return;
732 }
733 dummy->is_dummy = true;
734 dummy->layer = from->layer + i;
735 dummy->is_reversed = is_reversed (g, e);
736 dummy->w = 1;
737 r_agraph_add_edge_at (g, prev, dummy, nth);
738
739 prev = dummy;
740 nth = -1;
741 }
742 r_graph_add_edge (g->graph, prev->gnode, e->to);
743 }
744 }
745
746 /* create layers and assign an initial ordering of the nodes into them */
create_layers(RAGraph * g)747 static void create_layers(RAGraph *g) {
748 const RList *nodes = r_graph_get_nodes (g->graph);
749 RGraphNode *gn;
750 const RListIter *it;
751 RANode *n;
752 int i;
753
754 /* identify max layer */
755 g->n_layers = 0;
756 graph_foreach_anode (nodes, it, gn, n) {
757 if (n->layer > g->n_layers) {
758 g->n_layers = n->layer;
759 }
760 }
761
762 /* create a starting ordering of nodes for each layer */
763 g->n_layers++;
764 if (sizeof (struct layer_t) * g->n_layers < g->n_layers) {
765 return;
766 }
767 g->layers = R_NEWS0 (struct layer_t, g->n_layers);
768
769 graph_foreach_anode (nodes, it, gn, n) {
770 g->layers[n->layer].n_nodes++;
771 }
772
773 for (i = 0; i < g->n_layers; i++) {
774 if (sizeof (RGraphNode *) * g->layers[i].n_nodes < g->layers[i].n_nodes) {
775 continue;
776 }
777 g->layers[i].nodes = R_NEWS0 (RGraphNode *,
778 1 + g->layers[i].n_nodes);
779 g->layers[i].position = 0;
780 }
781 graph_foreach_anode (nodes, it, gn, n) {
782 n->pos_in_layer = g->layers[n->layer].position;
783 g->layers[n->layer].nodes[g->layers[n->layer].position++] = gn;
784 }
785 }
786
787 /* layer-by-layer sweep */
788 /* it permutes each layer, trying to find the best ordering for each layer
789 * to minimize the number of crossing edges */
minimize_crossings(const RAGraph * g)790 static void minimize_crossings(const RAGraph *g) {
791 int i, cross_changed, max_changes = 4096;
792
793 do {
794 cross_changed = false;
795 max_changes--;
796
797 for (i = 0; i < g->n_layers; i++) {
798 int rc = layer_sweep (g->graph, g->layers, g->n_layers, i, true);
799 if (rc == -1) {
800 return;
801 }
802 cross_changed |= !!rc;
803 }
804 } while (cross_changed && max_changes);
805
806 max_changes = 4096;
807
808 do {
809 cross_changed = false;
810 max_changes--;
811
812 for (i = g->n_layers - 1; i >= 0; i--) {
813 int rc = layer_sweep (g->graph, g->layers, g->n_layers, i, false);
814 if (rc == -1) {
815 return;
816 }
817 cross_changed |= !!rc;
818 }
819 } while (cross_changed && max_changes);
820 }
821
find_dist(const struct dist_t * a,const struct dist_t * b)822 static int find_dist(const struct dist_t *a, const struct dist_t *b) {
823 return a->from == b->from && a->to == b->to? 0: 1;
824 }
825
826 /* returns the distance between two nodes */
827 /* if the distance between two nodes were explicitly set, returns that;
828 * otherwise calculate the distance of two nodes on the same layer */
dist_nodes(const RAGraph * g,const RGraphNode * a,const RGraphNode * b)829 static int dist_nodes(const RAGraph *g, const RGraphNode *a, const RGraphNode *b) {
830 struct dist_t d;
831 const RANode *aa, *ab;
832 RListIter *it;
833 int res = 0;
834
835 if (g->dists) {
836 d.from = a;
837 d.to = b;
838 it = r_list_find (g->dists, &d, (RListComparator) find_dist);
839 if (it) {
840 struct dist_t *old = (struct dist_t *) r_list_iter_get_data (it);
841 return old->dist;
842 }
843 }
844
845 aa = get_anode (a);
846 ab = get_anode (b);
847 if (aa && ab && aa->layer == ab->layer) {
848 int i;
849
850 res = aa == ab && !aa->is_reversed? HORIZONTAL_NODE_SPACING: 0;
851 for (i = aa->pos_in_layer; i < ab->pos_in_layer; i++) {
852 const RGraphNode *cur = g->layers[aa->layer].nodes[i];
853 const RGraphNode *next = g->layers[aa->layer].nodes[i + 1];
854 const RANode *anext = get_anode (next);
855 const RANode *acur = get_anode (cur);
856 int found = false;
857
858 if (g->dists) {
859 d.from = cur;
860 d.to = next;
861 it = r_list_find (g->dists, &d, (RListComparator) find_dist);
862 if (it) {
863 struct dist_t *old = (struct dist_t *) r_list_iter_get_data (it);
864 res += old->dist;
865 found = true;
866 }
867 }
868
869 if (acur && anext && !found) {
870 int space = HORIZONTAL_NODE_SPACING;
871 if (acur->is_reversed && anext->is_reversed) {
872 if (!acur->is_reversed) {
873 res += acur->w / 2;
874 } else if (!anext->is_reversed) {
875 res += anext->w / 2;
876 }
877 res += 1;
878 } else {
879 res += acur->w / 2 + anext->w / 2 + space;
880 }
881 }
882 }
883 }
884
885 return res;
886 }
887
888 /* explicitly set the distance between two nodes on the same layer */
set_dist_nodes(const RAGraph * g,int l,int cur,int next)889 static void set_dist_nodes(const RAGraph *g, int l, int cur, int next) {
890 struct dist_t *d, find_el;
891 const RGraphNode *vi, *vip;
892 const RANode *avi, *avip;
893 RListIter *it;
894
895 if (!g->dists) {
896 return;
897 }
898 vi = g->layers[l].nodes[cur];
899 vip = g->layers[l].nodes[next];
900 avi = get_anode (vi);
901 avip = get_anode (vip);
902
903 find_el.from = vi;
904 find_el.to = vip;
905 it = r_list_find (g->dists, &find_el, (RListComparator) find_dist);
906 d = it? (struct dist_t *) r_list_iter_get_data (it): R_NEW0 (struct dist_t);
907
908 d->from = vi;
909 d->to = vip;
910 d->dist = (avip && avi)? avip->x - avi->x: 0;
911 if (!it) {
912 r_list_push (g->dists, d);
913 }
914 }
915
is_valid_pos(const RAGraph * g,int l,int pos)916 static int is_valid_pos(const RAGraph *g, int l, int pos) {
917 return pos >= 0 && pos < g->layers[l].n_nodes;
918 }
919
920 /* computes the set of vertical classes in the graph */
921 /* if v is an original node, L(v) = { v }
922 * if v is a dummy node, L(v) is the set of all the dummies node that belongs
923 * to the same long edge */
compute_vertical_nodes(const RAGraph * g)924 static Sdb *compute_vertical_nodes(const RAGraph *g) {
925 Sdb *res = sdb_new0 ();
926 int i, j;
927
928 for (i = 0; i < g->n_layers; i++) {
929 for (j = 0; j < g->layers[i].n_nodes; j++) {
930 RGraphNode *gn = g->layers[i].nodes[j];
931 const RList *Ln = hash_get_rlist (res, gn);
932 const RANode *an = get_anode (gn);
933
934 if (!Ln) {
935 RList *vert = r_list_new ();
936 hash_set (res, gn, vert);
937 if (an->is_dummy) {
938 RGraphNode *next = gn;
939 const RANode *anext = get_anode (next);
940
941 while (anext->is_dummy) {
942 r_list_append (vert, next);
943 next = r_graph_nth_neighbour (g->graph, next, 0);
944 if (!next) {
945 break;
946 }
947 anext = get_anode (next);
948 }
949 } else {
950 r_list_append (vert, gn);
951 }
952 }
953 }
954 }
955
956 return res;
957 }
958
959 /* computes left or right classes, used to place dummies node */
960 /* classes respect three properties:
961 * - v E C
962 * - w E C => L(v) is a subset of C
963 * - w E C, the s+(w) exists and is not in any class yet => s+(w) E C */
compute_classes(const RAGraph * g,Sdb * v_nodes,int is_left,int * n_classes)964 static RList **compute_classes(const RAGraph *g, Sdb *v_nodes, int is_left, int *n_classes) {
965 int i, j, c;
966 RList **res = R_NEWS0 (RList *, g->n_layers);
967 RGraphNode *gn;
968 const RListIter *it;
969 RANode *n;
970
971 graph_foreach_anode (r_graph_get_nodes (g->graph), it, gn, n) {
972 n->klass = -1;
973 }
974
975 for (i = 0; i < g->n_layers; i++) {
976 c = i;
977
978 for (j = is_left? 0: g->layers[i].n_nodes - 1;
979 (is_left && j < g->layers[i].n_nodes) || (!is_left && j >= 0);
980 j = is_left? j + 1: j - 1) {
981 const RGraphNode *gj = g->layers[i].nodes[j];
982 const RANode *aj = get_anode (gj);
983
984 if (aj->klass == -1) {
985 const RList *laj = hash_get_rlist (v_nodes, gj);
986
987 if (!res[c]) {
988 res[c] = r_list_new ();
989 }
990 graph_foreach_anode (laj, it, gn, n) {
991 r_list_append (res[c], gn);
992 n->klass = c;
993 }
994 } else {
995 c = aj->klass;
996 }
997 }
998 }
999
1000 if (n_classes) {
1001 *n_classes = g->n_layers;
1002 }
1003 return res;
1004 }
1005
cmp_dist(const size_t a,const size_t b)1006 static int cmp_dist(const size_t a, const size_t b) {
1007 return (a < b) - (a > b);
1008 }
1009
get_sibling(const RAGraph * g,const RANode * n,int is_left,int is_adjust_class)1010 static RGraphNode *get_sibling(const RAGraph *g, const RANode *n, int is_left, int is_adjust_class) {
1011 RGraphNode *res = NULL;
1012 int pos = n->pos_in_layer;
1013
1014 if ((is_left && is_adjust_class) || (!is_left && !is_adjust_class)) {
1015 pos++;
1016 } else {
1017 pos--;
1018 }
1019
1020 if (is_valid_pos (g, n->layer, pos)) {
1021 res = g->layers[n->layer].nodes[pos];
1022 }
1023 return res;
1024 }
1025
adjust_class_val(const RAGraph * g,const RGraphNode * gn,const RGraphNode * sibl,Sdb * res,int is_left)1026 static int adjust_class_val(const RAGraph *g, const RGraphNode *gn, const RGraphNode *sibl, Sdb *res, int is_left) {
1027 if (is_left) {
1028 return hash_get_int (res, sibl) - hash_get_int (res, gn) - dist_nodes (g, gn, sibl);
1029 }
1030 return hash_get_int (res, gn) - hash_get_int (res, sibl) - dist_nodes (g, sibl, gn);
1031 }
1032
1033 /* adjusts the position of previously placed left/right classes */
1034 /* tries to place classes as close as possible */
adjust_class(const RAGraph * g,int is_left,RList ** classes,Sdb * res,int c)1035 static void adjust_class(const RAGraph *g, int is_left, RList **classes, Sdb *res, int c) {
1036 const RGraphNode *gn;
1037 const RListIter *it;
1038 const RANode *an;
1039 int dist = 0;
1040 bool is_first = true;
1041
1042 graph_foreach_anode (classes[c], it, gn, an) {
1043 const RGraphNode *sibling;
1044 const RANode *sibl_anode;
1045
1046 sibling = get_sibling (g, an, is_left, true);
1047 if (!sibling) {
1048 continue;
1049 }
1050 sibl_anode = get_anode (sibling);
1051 if (sibl_anode->klass == c) {
1052 continue;
1053 }
1054 int v = adjust_class_val (g, gn, sibling, res, is_left);
1055 dist = is_first? v: R_MIN (dist, v);
1056 is_first = false;
1057 }
1058
1059 if (is_first) {
1060 RList *heap = r_list_new ();
1061 int len;
1062
1063 graph_foreach_anode (classes[c], it, gn, an) {
1064 const RList *neigh = r_graph_all_neighbours (g->graph, gn);
1065 const RGraphNode *gk;
1066 const RListIter *itk;
1067 const RANode *ak;
1068
1069 graph_foreach_anode (neigh, itk, gk, ak) {
1070 if (ak->klass < c) {
1071 size_t d = (ak->x - an->x);
1072 if (d > 0) {
1073 r_list_append (heap, (void *) d);
1074 }
1075 }
1076 }
1077 }
1078
1079 len = r_list_length (heap);
1080 if (len == 0) {
1081 dist = 0;
1082 } else {
1083 r_list_sort (heap, (RListComparator) cmp_dist);
1084 dist = (int) (size_t) r_list_get_n (heap, len / 2);
1085 }
1086
1087 r_list_free (heap);
1088 }
1089
1090 graph_foreach_anode (classes[c], it, gn, an) {
1091 const int old_val = hash_get_int (res, gn);
1092 const int new_val = is_left? old_val + dist: old_val - dist;
1093 hash_set (res, gn, new_val);
1094 }
1095 }
1096
place_nodes_val(const RAGraph * g,const RGraphNode * gn,const RGraphNode * sibl,Sdb * res,int is_left)1097 static int place_nodes_val(const RAGraph *g, const RGraphNode *gn, const RGraphNode *sibl, Sdb *res, int is_left) {
1098 if (is_left) {
1099 return hash_get_int (res, sibl) + dist_nodes (g, sibl, gn);
1100 }
1101 return hash_get_int (res, sibl) - dist_nodes (g, gn, sibl);
1102 }
1103
place_nodes_sel_p(int newval,int oldval,int is_first,int is_left)1104 static int place_nodes_sel_p(int newval, int oldval, int is_first, int is_left) {
1105 if (is_first) {
1106 return newval;
1107 }
1108 if (is_left) {
1109 return R_MAX (oldval, newval);
1110 }
1111 return R_MIN (oldval, newval);
1112 }
1113
1114 /* places left/right the nodes of a class */
place_nodes(const RAGraph * g,const RGraphNode * gn,int is_left,Sdb * v_nodes,RList ** classes,Sdb * res,Sdb * placed)1115 static void place_nodes(const RAGraph *g, const RGraphNode *gn, int is_left, Sdb *v_nodes, RList **classes, Sdb *res, Sdb *placed) {
1116 const RList *lv = hash_get_rlist (v_nodes, gn);
1117 int p = 0, v, is_first = true;
1118 const RGraphNode *gk;
1119 const RListIter *itk;
1120 const RANode *ak;
1121
1122 graph_foreach_anode (lv, itk, gk, ak) {
1123 const RGraphNode *sibling;
1124 const RANode *sibl_anode;
1125
1126 sibling = get_sibling (g, ak, is_left, false);
1127 if (!sibling) {
1128 continue;
1129 }
1130 sibl_anode = get_anode (sibling);
1131 if (ak->klass == sibl_anode->klass) {
1132 if (!hash_get (placed, sibling)) {
1133 place_nodes (g, sibling, is_left, v_nodes, classes, res, placed);
1134 }
1135
1136 v = place_nodes_val (g, gk, sibling, res, is_left);
1137 p = place_nodes_sel_p (v, p, is_first, is_left);
1138 is_first = false;
1139 }
1140 }
1141
1142 if (is_first) {
1143 p = is_left? 0: 50;
1144 }
1145
1146 graph_foreach_anode (lv, itk, gk, ak) {
1147 hash_set (res, gk, p);
1148 hash_set (placed, gk, true);
1149 }
1150 }
1151
1152 /* computes the position to the left/right of all the nodes */
compute_pos(const RAGraph * g,int is_left,Sdb * v_nodes)1153 static Sdb *compute_pos(const RAGraph *g, int is_left, Sdb *v_nodes) {
1154 int n_classes, i;
1155
1156 RList **classes = compute_classes (g, v_nodes, is_left, &n_classes);
1157 if (!classes) {
1158 return NULL;
1159 }
1160
1161 Sdb *res = sdb_new0 ();
1162 Sdb *placed = sdb_new0 ();
1163 for (i = 0; i < n_classes; i++) {
1164 const RGraphNode *gn;
1165 const RListIter *it;
1166
1167 r_list_foreach (classes[i], it, gn) {
1168 if (!hash_get_rnode (placed, gn)) {
1169 place_nodes (g, gn, is_left, v_nodes, classes, res, placed);
1170 }
1171 }
1172
1173 adjust_class (g, is_left, classes, res, i);
1174 }
1175
1176 sdb_free (placed);
1177 for (i = 0; i < n_classes; i++) {
1178 if (classes[i]) {
1179 r_list_free (classes[i]);
1180 }
1181 }
1182 free (classes);
1183 return res;
1184 }
1185
free_vertical_nodes_cb(void * user UNUSED,const char * k UNUSED,const char * v)1186 static int free_vertical_nodes_cb(void *user UNUSED, const char *k UNUSED, const char *v) {
1187 r_list_free ((RList *) (size_t) sdb_atoi (v));
1188 return 1;
1189 }
1190
1191 /* calculates position of all nodes, but in particular dummies nodes */
1192 /* computes two different placements (called "left"/"right") and set the final
1193 * position of each node to the average of the values in the two placements */
place_dummies(const RAGraph * g)1194 static void place_dummies(const RAGraph *g) {
1195 const RList *nodes;
1196 const RGraphNode *gn;
1197 const RListIter *it;
1198 RANode *n;
1199
1200 Sdb *vertical_nodes = compute_vertical_nodes (g);
1201 if (!vertical_nodes) {
1202 return;
1203 }
1204 Sdb *xminus = compute_pos (g, true, vertical_nodes);
1205 if (!xminus) {
1206 goto xminus_err;
1207 }
1208 Sdb *xplus = compute_pos (g, false, vertical_nodes);
1209 if (!xplus) {
1210 goto xplus_err;
1211 }
1212
1213 nodes = r_graph_get_nodes (g->graph);
1214 graph_foreach_anode (nodes, it, gn, n) {
1215 n->x = (hash_get_int (xminus, gn) + hash_get_int (xplus, gn)) / 2;
1216 }
1217
1218 sdb_free (xplus);
1219 xplus_err:
1220 sdb_free (xminus);
1221 xminus_err:
1222 sdb_foreach (vertical_nodes, (SdbForeachCallback)free_vertical_nodes_cb, NULL);
1223 sdb_free (vertical_nodes);
1224 }
1225
get_right_dummy(const RAGraph * g,const RGraphNode * n)1226 static RGraphNode *get_right_dummy(const RAGraph *g, const RGraphNode *n) {
1227 const RANode *an = get_anode (n);
1228 if (!an) {
1229 return NULL;
1230 }
1231 int k, layer = an->layer;
1232
1233 for (k = an->pos_in_layer + 1; k < g->layers[layer].n_nodes; k++) {
1234 RGraphNode *gk = g->layers[layer].nodes[k];
1235 const RANode *ak = get_anode (gk);
1236 if (!ak) {
1237 break;
1238 }
1239
1240 if (ak->is_dummy) {
1241 return gk;
1242 }
1243 }
1244 return NULL;
1245 }
1246
adjust_directions(const RAGraph * g,int i,int from_up,Sdb * D,Sdb * P)1247 static void adjust_directions(const RAGraph *g, int i, int from_up, Sdb *D, Sdb *P) {
1248 const RGraphNode *vm = NULL, *wm = NULL;
1249 const RANode *vma = NULL, *wma = NULL;
1250 int j, d = from_up? 1: -1;
1251
1252 if (i + d < 0 || i + d >= g->n_layers) {
1253 return;
1254 }
1255 for (j = 0; j < g->layers[i + d].n_nodes; j++) {
1256 const RGraphNode *wp, *vp = g->layers[i + d].nodes[j];
1257 const RANode *wpa, *vpa = get_anode (vp);
1258
1259 if (!vpa || !vpa->is_dummy) {
1260 continue;
1261 }
1262 if (from_up) {
1263 wp = r_list_get_n (r_graph_innodes (g->graph, vp), 0);
1264 } else {
1265 wp = r_graph_nth_neighbour (g->graph, vp, 0);
1266 }
1267 wpa = get_anode (wp);
1268 if (!wpa || !wpa->is_dummy) {
1269 continue;
1270 }
1271 if (vm) {
1272 int p = hash_get_int (P, wm);
1273 int k;
1274
1275 for (k = wma->pos_in_layer + 1; k < wpa->pos_in_layer; k++) {
1276 const RGraphNode *w = g->layers[wma->layer].nodes[k];
1277 const RANode *aw = get_anode (w);
1278 if (aw && aw->is_dummy) {
1279 p &= hash_get_int (P, w);
1280 }
1281 }
1282 if (p) {
1283 hash_set (D, vm, from_up);
1284 for (k = vma->pos_in_layer + 1; k < vpa->pos_in_layer; k++) {
1285 const RGraphNode *v = g->layers[vma->layer].nodes[k];
1286 const RANode *av = get_anode (v);
1287 if (av && av->is_dummy) {
1288 hash_set (D, v, from_up);
1289 }
1290 }
1291 }
1292 }
1293 vm = vp;
1294 wm = wp;
1295 vma = get_anode (vm);
1296 wma = get_anode (wm);
1297 }
1298 }
1299
1300 /* find a placement for a single node */
place_single(const RAGraph * g,int l,const RGraphNode * bm,const RGraphNode * bp,int from_up,int va)1301 static void place_single(const RAGraph *g, int l, const RGraphNode *bm, const RGraphNode *bp, int from_up, int va) {
1302 const RGraphNode *gk, *v = g->layers[l].nodes[va];
1303 const RANode *ak;
1304 RANode *av = get_anode (v);
1305 if (!av) {
1306 return;
1307 }
1308 const RListIter *itk;
1309
1310 const RList *neigh = from_up
1311 ? r_graph_innodes (g->graph, v)
1312 : r_graph_get_neighbours (g->graph, v);
1313
1314 int len = r_list_length (neigh);
1315 if (len == 0) {
1316 return;
1317 }
1318
1319 int sum_x = 0;
1320 graph_foreach_anode (neigh, itk, gk, ak) {
1321 if (ak->is_reversed) {
1322 len--;
1323 continue;
1324 }
1325 sum_x += ak->x;
1326 }
1327
1328 if (len == 0) {
1329 return;
1330 }
1331 if (av) {
1332 av->x = sum_x / len;
1333 }
1334 if (bm) {
1335 const RANode *bma = get_anode (bm);
1336 av->x = R_MAX (av->x, bma->x + dist_nodes (g, bm, v));
1337 }
1338 if (bp) {
1339 const RANode *bpa = get_anode (bp);
1340 av->x = R_MIN (av->x, bpa->x - dist_nodes (g, v, bp));
1341 }
1342 }
1343
RM_listcmp(const struct len_pos_t * a,const struct len_pos_t * b)1344 static int RM_listcmp(const struct len_pos_t *a, const struct len_pos_t *b) {
1345 return (a->pos < b->pos) - (a->pos > b->pos);
1346 }
1347
RP_listcmp(const struct len_pos_t * a,const struct len_pos_t * b)1348 static int RP_listcmp(const struct len_pos_t *a, const struct len_pos_t *b) {
1349 return (a->pos > b->pos) - (a->pos < b->pos);
1350 }
1351
collect_changes(const RAGraph * g,int l,const RGraphNode * b,int from_up,int s,int e,RList * list,int is_left)1352 static void collect_changes(const RAGraph *g, int l, const RGraphNode *b, int from_up, int s, int e, RList *list, int is_left) {
1353 const RGraphNode *vt = g->layers[l].nodes[e - 1];
1354 const RGraphNode *vtp = g->layers[l].nodes[s];
1355 struct len_pos_t *cx;
1356 int i;
1357
1358 RListComparator lcmp = is_left? (RListComparator) RM_listcmp: (RListComparator) RP_listcmp;
1359
1360 for (i = is_left? s: e - 1; (is_left && i < e) || (!is_left && i >= s); i = is_left? i + 1: i - 1) {
1361 const RGraphNode *v, *vi = g->layers[l].nodes[i];
1362 const RANode *av, *avi = get_anode (vi);
1363 const RList *neigh;
1364 const RListIter *it;
1365 int c = 0;
1366
1367 if (!avi) {
1368 continue;
1369 }
1370 neigh = from_up
1371 ? r_graph_innodes (g->graph, vi)
1372 : r_graph_get_neighbours (g->graph, vi);
1373
1374 graph_foreach_anode (neigh, it, v, av) {
1375 if ((is_left && av->x >= avi->x) || (!is_left && av->x <= avi->x)) {
1376 c++;
1377 } else {
1378 cx = R_NEW (struct len_pos_t);
1379 c--;
1380 cx->len = 2;
1381 cx->pos = av->x;
1382 if (is_left) {
1383 cx->pos += dist_nodes (g, vi, vt);
1384 } else {
1385 cx->pos -= dist_nodes (g, vtp, vi);
1386 }
1387 r_list_add_sorted (list, cx, lcmp);
1388 }
1389 }
1390
1391 cx = R_NEW0 (struct len_pos_t);
1392 cx->len = c;
1393 cx->pos = avi->x;
1394 if (is_left) {
1395 cx->pos += dist_nodes (g, vi, vt);
1396 } else {
1397 cx->pos -= dist_nodes (g, vtp, vi);
1398 }
1399 r_list_add_sorted (list, cx, lcmp);
1400 }
1401
1402 if (b) {
1403 const RANode *ab = get_anode (b);
1404 cx = R_NEW (struct len_pos_t);
1405 if (cx) {
1406 cx->len = is_left? INT_MAX: INT_MIN;
1407 cx->pos = ab->x;
1408 if (is_left) {
1409 cx->pos += dist_nodes (g, b, vt);
1410 } else {
1411 cx->pos -= dist_nodes (g, vtp, b);
1412 }
1413 r_list_add_sorted (list, cx, lcmp);
1414 }
1415 }
1416 }
1417
combine_sequences(const RAGraph * g,int l,const RGraphNode * bm,const RGraphNode * bp,int from_up,int a,int r)1418 static void combine_sequences(const RAGraph *g, int l, const RGraphNode *bm, const RGraphNode *bp, int from_up, int a, int r) {
1419 RList *Rm = r_list_new (), *Rp = r_list_new ();
1420 const RGraphNode *vt, *vtp;
1421 RANode *at, *atp;
1422 int rm, rp, t, m, i;
1423 Rm->free = (RListFree) free;
1424 Rp->free = (RListFree) free;
1425
1426 t = (a + r) / 2;
1427 vt = g->layers[l].nodes[t - 1];
1428 vtp = g->layers[l].nodes[t];
1429 at = get_anode (vt);
1430 atp = get_anode (vtp);
1431
1432 collect_changes (g, l, bm, from_up, a, t, Rm, true);
1433 collect_changes (g, l, bp, from_up, t, r, Rp, false);
1434 rm = rp = 0;
1435
1436 m = dist_nodes (g, vt, vtp);
1437 if (at && atp) {
1438 while (atp->x - at->x < m) {
1439 if (atp->x == at->x) {
1440 int step = m / 2;
1441 at->x -= step;
1442 atp->x += m - step;
1443 } else {
1444 if (rm < rp) {
1445 if (r_list_empty (Rm)) {
1446 at->x = atp->x - m;
1447 } else {
1448 struct len_pos_t *cx = (struct len_pos_t *) r_list_pop (Rm);
1449 rm = rm + cx->len;
1450 at->x = R_MAX (cx->pos, atp->x - m);
1451 free (cx);
1452 }
1453 } else {
1454 if (r_list_empty (Rp)) {
1455 atp->x = at->x + m;
1456 } else {
1457 struct len_pos_t *cx = (struct len_pos_t *) r_list_pop (Rp);
1458 rp = rp + cx->len;
1459 atp->x = R_MIN (cx->pos, at->x + m);
1460 free (cx);
1461 }
1462 }
1463 }
1464 }
1465 }
1466
1467 r_list_free (Rm);
1468 r_list_free (Rp);
1469
1470 for (i = t - 2; i >= a; i--) {
1471 const RGraphNode *gv = g->layers[l].nodes[i];
1472 RANode *av = get_anode (gv);
1473 if (av && at) {
1474 av->x = R_MIN (av->x, at->x - dist_nodes (g, gv, vt));
1475 }
1476 }
1477
1478 for (i = t + 1; i < r; i++) {
1479 const RGraphNode *gv = g->layers[l].nodes[i];
1480 RANode *av = get_anode (gv);
1481 if (av && atp) {
1482 av->x = R_MAX (av->x, atp->x + dist_nodes (g, vtp, gv));
1483 }
1484 }
1485 }
1486
1487 /* places a sequence of consecutive original nodes */
1488 /* it tries to minimize the distance between each node in the sequence and its
1489 * neighbours in the "previous" layer. Those neighbours are considered as
1490 * "fixed". The previous layer depends on the direction used during the layers
1491 * traversal */
place_sequence(const RAGraph * g,int l,const RGraphNode * bm,const RGraphNode * bp,int from_up,int va,int vr)1492 static void place_sequence(const RAGraph *g, int l, const RGraphNode *bm, const RGraphNode *bp, int from_up, int va, int vr) {
1493 if (vr == va + 1) {
1494 place_single (g, l, bm, bp, from_up, va);
1495 } else if (vr > va + 1) {
1496 int vt = (vr + va) / 2;
1497 place_sequence (g, l, bm, bp, from_up, va, vt);
1498 place_sequence (g, l, bm, bp, from_up, vt, vr);
1499 combine_sequences (g, l, bm, bp, from_up, va, vr);
1500 }
1501 }
1502
1503 /* finds the placements of nodes while traversing the graph in the given
1504 * direction */
1505 /* places all the sequences of consecutive original nodes in each layer. */
original_traverse_l(const RAGraph * g,Sdb * D,Sdb * P,int from_up)1506 static void original_traverse_l(const RAGraph *g, Sdb *D, Sdb *P, int from_up) {
1507 int i, k, va, vr;
1508
1509 for (i = from_up? 0: g->n_layers - 1;
1510 (from_up && i < g->n_layers) || (!from_up && i >= 0);
1511 i = from_up? i + 1: i - 1) {
1512 int j;
1513 const RGraphNode *bm = NULL;
1514 const RANode *bma = NULL;
1515
1516 j = 0;
1517 while (j < g->layers[i].n_nodes && !bm) {
1518 const RGraphNode *gn = g->layers[i].nodes[j];
1519 const RANode *an = get_anode (gn);
1520 if (an && an->is_dummy) {
1521 va = 0;
1522 vr = j;
1523 bm = gn;
1524 bma = an;
1525 }
1526 j++;
1527 }
1528 if (!bm) {
1529 va = 0;
1530 vr = g->layers[i].n_nodes;
1531 }
1532 place_sequence (g, i, NULL, bm, from_up, va, vr);
1533 for (k = va; k < vr - 1; k++) {
1534 set_dist_nodes (g, i, k, k + 1);
1535 }
1536 if (is_valid_pos (g, i, vr - 1) && bm) {
1537 set_dist_nodes (g, i, vr - 1, bma->pos_in_layer);
1538 }
1539 while (bm) {
1540 const RGraphNode *bp = get_right_dummy (g, bm);
1541 const RANode *bpa = NULL;
1542 bma = get_anode (bm);
1543
1544 if (!bp) {
1545 va = bma->pos_in_layer + 1;
1546 vr = g->layers[bma->layer].n_nodes;
1547 place_sequence (g, i, bm, NULL, from_up, va, vr);
1548 for (k = va; k < vr - 1; k++) {
1549 set_dist_nodes (g, i, k, k + 1);
1550 }
1551
1552 if (is_valid_pos (g, i, va)) {
1553 set_dist_nodes (g, i, bma->pos_in_layer, va);
1554 }
1555 } else if (hash_get_int (D, bm) == from_up) {
1556 bpa = get_anode (bp);
1557 va = bma->pos_in_layer + 1;
1558 vr = bpa->pos_in_layer;
1559 place_sequence (g, i, bm, bp, from_up, va, vr);
1560 hash_set (P, bm, true);
1561 }
1562 bm = bp;
1563 }
1564 adjust_directions (g, i, from_up, D, P);
1565 }
1566 }
1567
1568 /* computes a final position of original nodes, considering dummies nodes as
1569 * fixed */
1570 /* set the node placements traversing the graph downward and then upward */
place_original(RAGraph * g)1571 static void place_original(RAGraph *g) {
1572 const RList *nodes = r_graph_get_nodes (g->graph);
1573 const RGraphNode *gn;
1574 const RListIter *itn;
1575 const RANode *an;
1576
1577 Sdb *D = sdb_new0 ();
1578 if (!D) {
1579 return;
1580 }
1581 Sdb *P = sdb_new0 ();
1582 if (!P) {
1583 sdb_free (D);
1584 return;
1585 }
1586 g->dists = r_list_newf ((RListFree) free);
1587 if (!g->dists) {
1588 sdb_free (D);
1589 sdb_free (P);
1590 return;
1591 }
1592
1593 graph_foreach_anode (nodes, itn, gn, an) {
1594 if (!an->is_dummy) {
1595 continue;
1596 }
1597 const RGraphNode *right_v = get_right_dummy (g, gn);
1598 const RANode *right = get_anode (right_v);
1599 if (right_v && right) {
1600 hash_set (D, gn, 0);
1601 int dt_eq = right->x - an->x == dist_nodes (g, gn, right_v);
1602 hash_set (P, gn, dt_eq);
1603 }
1604 }
1605
1606 original_traverse_l (g, D, P, true);
1607 original_traverse_l (g, D, P, false);
1608
1609 r_list_free (g->dists);
1610 g->dists = NULL;
1611 sdb_free (P);
1612 sdb_free (D);
1613 }
1614
1615 #if 0
1616 static void free_anode(RANode *n);
1617 static void remove_dummy_nodes(const RAGraph *g) {
1618 const RList *nodes = r_graph_get_nodes (g->graph);
1619 RGraphNode *gn;
1620 RListIter *it;
1621 RANode *n;
1622
1623 graph_foreach_anode (nodes, it, gn, n) {
1624 if (n->is_dummy) {
1625 r_graph_del_node (g->graph, gn);
1626 n->gnode = NULL;
1627 free_anode (n);
1628 }
1629 }
1630 }
1631 #endif
1632
set_layer_gap(RAGraph * g)1633 static void set_layer_gap (RAGraph *g) {
1634 int gap = 0;
1635 int i = 0, j = 0;
1636 RListIter *itn;
1637 RGraphNode *ga, *gb;
1638 RANode *a, *b;
1639 const RList *outnodes;
1640
1641 g->layers[0].gap = 0;
1642 for (i = 0; i < g->n_layers; i++) {
1643 gap = 0;
1644 if (i + 1 < g->n_layers) {
1645 g->layers[i+1].gap = gap;
1646 }
1647 for (j = 0; j < g->layers[i].n_nodes; j++) {
1648 ga = g->layers[i].nodes[j];
1649 if (!ga) {
1650 continue;
1651 }
1652 a = (RANode *) ga->data;
1653 outnodes = ga->out_nodes;
1654
1655 if (!outnodes || !a) {
1656 continue;
1657 }
1658 graph_foreach_anode (outnodes, itn, gb, b) {
1659 if (g->layout == 0) { // vertical layout
1660 if ((b->x != a->x) || b->layer <= a->layer) {
1661 gap += 1;
1662 if (b->layer <= a->layer) {
1663 g->layers[b->layer].gap += 1;
1664 }
1665 } else if ((!a->is_dummy && b->is_dummy) || (a->is_dummy && !b->is_dummy)) {
1666 gap += 1;
1667 }
1668 } else {
1669 if ((b->y == a->y && b->h != a->h) || b->y != a->y || b->layer <= a->layer) {
1670 gap += 1;
1671 if (b->layer <= a->layer) {
1672 g->layers[b->layer].gap += 1;
1673 }
1674 } else if ((!a->is_dummy && b->is_dummy) || (a->is_dummy && !b->is_dummy)) {
1675 gap += 1;
1676 }
1677 }
1678 }
1679 }
1680 if (i + 1 < g->n_layers) {
1681 g->layers[i+1].gap += gap;
1682 }
1683 }
1684 }
1685
fix_back_edge_dummy_nodes(RAGraph * g,RANode * from,RANode * to)1686 static void fix_back_edge_dummy_nodes(RAGraph *g, RANode *from, RANode *to) {
1687 RANode *v, *tmp = NULL;
1688 RGraphNode *gv = NULL;
1689 RListIter *it;
1690 int i;
1691 r_return_if_fail (g && from && to);
1692 const RList *neighbours = r_graph_get_neighbours (g->graph, to->gnode);
1693 graph_foreach_anode (neighbours, it, gv, v) {
1694 tmp = v;
1695 while (tmp->is_dummy) {
1696 tmp = (RANode *) (((RGraphNode *)r_list_first (tmp->gnode->out_nodes))->data);
1697 }
1698 if (tmp->gnode->idx == from->gnode->idx) {
1699 break;
1700 }
1701 tmp = NULL;
1702 }
1703 if (tmp) {
1704 tmp = v;
1705 v = to;
1706 while (tmp->gnode->idx != from->gnode->idx) {
1707 v = tmp;
1708 tmp = (RANode *) (((RGraphNode *)r_list_first (v->gnode->out_nodes))->data);
1709
1710 i = 0;
1711 while (v->gnode->idx != g->layers[v->layer].nodes[i]->idx) {
1712 i += 1;
1713 }
1714
1715 while (i + 1 < g->layers[v->layer].n_nodes) {
1716 g->layers[v->layer].nodes[i] = g->layers[v->layer].nodes[i+1];
1717 i++;
1718 }
1719 g->layers[v->layer].nodes[g->layers[v->layer].n_nodes - 1] = 0;
1720 g->layers[v->layer].n_nodes -= 1;
1721
1722 r_graph_del_node (g->graph, v->gnode);
1723 }
1724 }
1725 }
1726
get_edge_number(const RAGraph * g,RANode * src,RANode * dst,bool outgoing)1727 static int get_edge_number (const RAGraph *g, RANode *src, RANode *dst, bool outgoing) {
1728 RListIter *itn;
1729 RGraphNode *gv;
1730 int cur_nth = 0;
1731 int nth = 0;
1732 RANode *v;
1733
1734 if (outgoing && src->is_dummy) {
1735 RANode *in = (RANode *) (((RGraphNode *)r_list_first ((src->gnode)->in_nodes))->data);
1736 cur_nth = get_edge_number (g, in, src, outgoing);
1737 } else {
1738 const RList *neighbours = outgoing
1739 ? r_graph_get_neighbours (g->graph, src->gnode)
1740 : r_graph_innodes (g->graph, dst->gnode);
1741 const int exit_edges = r_list_length (neighbours);
1742 graph_foreach_anode (neighbours, itn, gv, v) {
1743 cur_nth = nth;
1744 if (g->is_callgraph) {
1745 cur_nth = 0;
1746 } else if (exit_edges == 1) {
1747 cur_nth = -1;
1748 }
1749 if (outgoing && gv->idx == (dst->gnode)->idx) {
1750 break;
1751 }
1752 if (!outgoing && gv->idx == (src->gnode)->idx) {
1753 break;
1754 }
1755 nth++;
1756 }
1757 }
1758 return cur_nth;
1759 }
1760
count_edges(const RAGraph * g,RANode * src,RANode * dst)1761 static int count_edges(const RAGraph *g, RANode *src, RANode *dst) {
1762 return get_edge_number (g, src, dst, true);
1763 }
1764
backedge_info(RAGraph * g)1765 static void backedge_info(RAGraph *g) {
1766 int i, j, k;
1767 int min, max;
1768 int inedge = 0;
1769 int outedge = 0;
1770 if (g->n_layers > ST16_MAX) {
1771 return;
1772 }
1773
1774 int **arr = R_NEWS0 (int *, g->n_layers);
1775 if (!arr) {
1776 return;
1777 }
1778 for (i = 0; i < g->n_layers; i++) {
1779 arr[i] = R_NEWS0 (int, 2);
1780 if (!arr[i]) {
1781 goto err;
1782 }
1783 }
1784
1785 for (i = 0; i < g->n_layers; i++) {
1786 for (j = 0; j < g->layers[i].n_nodes; j++) {
1787 RGraphNode *gt = g->layers[i].nodes[j];
1788 if (!gt) {
1789 continue;
1790 }
1791 RANode *t = (RANode *) gt->data;
1792 if (!t) {
1793 continue;
1794 }
1795 int tc = g->layout == 0 ? t->x : t->y;
1796 int tl = g->layout == 0 ? t->w : t->h;
1797 if (!j) {
1798 arr[i][0] = tc;
1799 arr[i][1] = tc + tl;
1800 }
1801
1802 if (arr[i][0] > tc) {
1803 arr[i][0] = tc;
1804 }
1805
1806 if (arr[i][1] < tc + tl) {
1807 arr[i][1] = tc + tl;
1808 }
1809 }
1810
1811 for (j = 0; j < g->layers[i].n_nodes; j++) {
1812 RANode *a = get_anode (g->layers[i].nodes[j]);
1813 if (!a || a->is_dummy) {
1814 continue;
1815 }
1816
1817 const RList *neighbours = r_graph_get_neighbours (g->graph, a->gnode);
1818 RGraphNode *gb;
1819 RANode *b;
1820 RListIter *itm;
1821
1822 if (i == 0) {
1823 inedge += r_list_length (r_graph_innodes (g->graph, a->gnode));
1824 } else if (i == g->n_layers - 1) {
1825 outedge += r_list_length (neighbours);
1826 }
1827
1828 graph_foreach_anode (neighbours, itm, gb, b) {
1829 if (b->layer > a->layer) {
1830 continue;
1831 }
1832
1833 int nth = count_edges (g, a, b);
1834 int xinc = R_EDGES_X_INC + 2 * (nth + 1);
1835
1836 int ax = g->layout == 0 ? a->x + xinc : a->y + (a->h / 2) + nth;
1837 int bx = g->layout == 0 ? b->x + xinc : b->y + (b->h / 2) + nth;
1838
1839 if (g->layout == 0 && nth == 0 && bx > ax) {
1840 ax += 4;
1841 }
1842
1843 min = arr[b->layer][0];
1844 max = arr[b->layer][1];
1845 for (k = b->layer; k <= a->layer; k++) {
1846 if (min > arr[k][0]) {
1847 min = arr[k][0];
1848 }
1849
1850 if (max < arr[k][1]) {
1851 max = arr[k][1];
1852 }
1853 }
1854
1855 int l = (ax - min) + (bx - min);
1856 int r = (max - ax) + (max - bx);
1857
1858 for (k = b->layer; k <= a->layer; k++) {
1859 if (r < l) {
1860 arr[k][1] = max + 1;
1861 } else {
1862 arr[k][0] = min - 1;
1863 }
1864 }
1865
1866 AEdge *e = R_NEW0 (AEdge);
1867 if (!e) {
1868 free (arr);
1869 return;
1870 }
1871
1872 e->is_reversed = true;
1873 e->from = a;
1874 e->to = b;
1875 e->x = r_list_new ();
1876 e->y = r_list_new ();
1877
1878 if (r < l) {
1879 r_list_append ((g->layout == 0 ? e->x : e->y), (void *) (size_t) (max + 1));
1880 } else {
1881 r_list_append ((g->layout == 0 ? e->x : e->y), (void *) (size_t) (min - 1));
1882 }
1883
1884 r_list_append(g->edges, e);
1885 }
1886 }
1887 }
1888
1889 //Assumption: layer layout is not changed w.r.t x-coordinate/y-coordinate for horizontal/vertical layout respectively.
1890 if (inedge) {
1891 RANode *n = (RANode *)g->layers[0].nodes[0]->data;
1892 AEdge *e = R_NEW0 (AEdge);
1893 if (!e) {
1894 free (arr);
1895 return;
1896 }
1897 e->is_reversed = true;
1898 e->from = NULL;
1899 e->to = NULL;
1900 e->x = r_list_new ();
1901 e->y = r_list_new ();
1902 if (g->layout == 0) {
1903 r_list_append (e->y, (void *) (size_t) (n->y - 1 - inedge));
1904 } else {
1905 r_list_append (e->x, (void *) (size_t) (n->x - 1 - inedge));
1906 }
1907 r_list_append (g->edges, e);
1908 }
1909
1910 if (outedge) {
1911 RANode *n = (RANode *)g->layers[g->n_layers - 1].nodes[0]->data;
1912 AEdge *e = R_NEW0 (AEdge);
1913 if (!e) {
1914 free (arr);
1915 return;
1916 }
1917
1918 e->is_reversed = true;
1919 e->from = NULL;
1920 e->to = NULL;
1921 e->x = r_list_new ();
1922 e->y = r_list_new ();
1923 if (g->layout == 0) {
1924 r_list_append (e->y, (void *) (size_t) (n->y + g->layers[g->n_layers - 1].height + 2 + outedge));
1925 } else {
1926 r_list_append (e->x, (void *) (size_t) (n->x + g->layers[g->n_layers - 1].width + 2 + outedge));
1927 }
1928 r_list_append (g->edges, e);
1929 }
1930 err:
1931 for (i = i - 1; i >= 0; i--) {
1932 free (arr[i]);
1933 }
1934 free (arr);
1935 return;
1936 }
1937
1938 /* 1) trasform the graph into a DAG
1939 * 2) partition the nodes in layers
1940 * 3) split long edges that traverse multiple layers
1941 * 4) reorder nodes in each layer to reduce the number of edge crossing
1942 * 5) assign x and y coordinates to each node
1943 * 6) restore the original graph, with long edges and cycles */
set_layout(RAGraph * g)1944 static void set_layout(RAGraph *g) {
1945 int i, j, k;
1946
1947 r_list_free (g->edges);
1948 g->edges = r_list_new ();
1949
1950 remove_cycles (g);
1951 assign_layers (g);
1952 create_dummy_nodes (g);
1953 create_layers (g);
1954 minimize_crossings (g);
1955
1956 if (r_cons_is_breaked ()) {
1957 r_cons_break_end ();
1958 return;
1959 }
1960 /* identify row height */
1961 for (i = 0; i < g->n_layers; i++) {
1962 int rh = 0;
1963 int rw = 0;
1964 for (j = 0; j < g->layers[i].n_nodes; j++) {
1965 const RANode *n = get_anode (g->layers[i].nodes[j]);
1966 if (n->h > rh) {
1967 rh = n->h;
1968 }
1969 if (n->w > rw) {
1970 rw = n->w;
1971 }
1972 }
1973 g->layers[i].height = rh;
1974 g->layers[i].width = rw;
1975 }
1976
1977 for (i = 0; i < g->n_layers; i++) {
1978 for (j = 0; j < g->layers[i].n_nodes; j++) {
1979 RANode *a = (RANode *) g->layers[i].nodes[j]->data;
1980 if (a->is_dummy) {
1981 if (g->layout == 0) {
1982 a->h = g->layers[i].height;
1983 } else {
1984 a->w = g->layers[i].width;
1985 }
1986 }
1987 a->layer_height = g->layers[i].height;
1988 a->layer_width = g->layers[i].width;
1989 }
1990 }
1991
1992 /* x-coordinate assignment: algorithm based on:
1993 * A Fast Layout Algorithm for k-Level Graphs
1994 * by C. Buchheim, M. Junger, S. Leipert */
1995 place_dummies (g);
1996 place_original (g);
1997
1998 /* IDEA: need to put this hack because of the way algorithm is implemented.
1999 * I think backedges should be restored to their original state instead of
2000 * converting them to longedges and adding dummy nodes. */
2001 const RListIter *it;
2002 const RGraphEdge *e;
2003 r_list_foreach (g->back_edges, it, e) {
2004 RANode *from = e->from? get_anode (e->from): NULL;
2005 RANode *to = e->to? get_anode (e->to): NULL;
2006 fix_back_edge_dummy_nodes (g, from, to);
2007 r_agraph_del_edge (g, to, from);
2008 r_agraph_add_edge_at (g, from, to, e->nth);
2009 }
2010
2011 switch (g->layout) {
2012 default:
2013 case 0: // vertical layout
2014 /* horizontal finalize x coordinate */
2015 for (i = 0; i < g->n_layers; i++) {
2016 for (j = 0; j < g->layers[i].n_nodes; j++) {
2017 RANode *n = get_anode (g->layers[i].nodes[j]);
2018 if (n) {
2019 n->x -= n->w / 2;
2020 if (g->is_tiny) {
2021 n->x /= 8;
2022 }
2023 }
2024 }
2025 }
2026
2027 set_layer_gap (g);
2028
2029 /* vertical align */
2030 for (i = 0; i < g->n_layers; i++) {
2031 int tmp_y = 0;
2032 tmp_y = g->layers[0].gap; //TODO: XXX: set properly
2033 for (k = 1; k <= i; k++) {
2034 tmp_y += g->layers[k-1].height + g->layers[k].gap + 3; //XXX: should be 4?
2035 }
2036 if (g->is_tiny) {
2037 tmp_y = i;
2038 }
2039 for (j = 0; j < g->layers[i].n_nodes; j++) {
2040 RANode *n = get_anode (g->layers[i].nodes[j]);
2041 if (n) {
2042 n->y = tmp_y;
2043 }
2044 }
2045 }
2046 break;
2047 /* experimental */
2048 case 1: // horizontal layout
2049 /* vertical y coordinate */
2050 for (i = 0; i < g->n_layers; i++) {
2051 for (j = 0; j < g->layers[i].n_nodes; j++) {
2052 RANode *n = get_anode (g->layers[i].nodes[j]);
2053 n->y = 1;
2054 for (k = 0; k < j; k++) {
2055 RANode *m = get_anode (g->layers[i].nodes[k]);
2056 n->y -= (m->h + VERTICAL_NODE_SPACING);
2057 }
2058 }
2059 }
2060
2061 set_layer_gap (g);
2062
2063 /* horizontal align */
2064 for (i = 0; i < g->n_layers; i++) {
2065 int xval = 1 + g->layers[0].gap + 1;
2066 for (k = 1; k <= i; k++) {
2067 xval += g->layers[k-1].width + g->layers[k].gap + 3;
2068 }
2069 for (j = 0; j < g->layers[i].n_nodes; j++) {
2070 RANode *n = get_anode (g->layers[i].nodes[j]);
2071 n->x = xval;
2072 }
2073 }
2074 break;
2075 }
2076
2077 backedge_info (g);
2078
2079 /* free all temporary structures used during layout */
2080 for (i = 0; i < g->n_layers; i++) {
2081 free (g->layers[i].nodes);
2082 }
2083
2084 free (g->layers);
2085 r_list_free (g->long_edges);
2086 r_list_free (g->back_edges);
2087 r_cons_break_pop ();
2088 }
2089
get_body(RCore * core,ut64 addr,int size,int opts)2090 static char *get_body(RCore *core, ut64 addr, int size, int opts) {
2091 char *body;
2092 RConfigHold *hc = r_config_hold_new (core->config);
2093 if (!hc) {
2094 return NULL;
2095 }
2096 r_config_hold (hc, "asm.lines", "asm.bytes",
2097 "asm.cmt.col", "asm.marks", "asm.offset",
2098 "asm.comments", "asm.cmt.right", "asm.bb.line", NULL);
2099 const bool o_comments = r_config_get_i (core->config, "graph.comments");
2100 const bool o_cmtright = r_config_get_i (core->config, "graph.cmtright");
2101 const bool o_bytes = r_config_get_i (core->config, "graph.bytes");
2102 const bool o_flags_in_bytes = r_config_get_i (core->config, "asm.flags.inbytes");
2103 const bool o_graph_offset = r_config_get_i (core->config, "graph.offset");
2104 int o_cursor = core->print->cur_enabled;
2105 if (opts & BODY_COMMENTS) {
2106 r_core_visual_toggle_decompiler_disasm (core, true, false);
2107 char * res = r_core_cmd_strf (core, "pD %d @ 0x%08"PFMT64x, size, addr);
2108 res = r_str_replace (res, "; ", "", true);
2109 // res = r_str_replace (res, "\n", "(\n)", true);
2110 r_str_trim (res);
2111 res = r_str_trim_lines (res);
2112 r_core_visual_toggle_decompiler_disasm (core, true, false);
2113 r_config_hold_restore (hc);
2114 r_config_hold_free (hc);
2115 return res;
2116 }
2117 const char *cmd = (opts & BODY_SUMMARY)? "pds": "pD";
2118
2119 // configure options
2120 r_config_set_i (core->config, "asm.bb.line", false);
2121 r_config_set_i (core->config, "asm.lines", false);
2122 r_config_set_i (core->config, "asm.cmt.col", 0);
2123 r_config_set_i (core->config, "asm.marks", false);
2124 r_config_set_i (core->config, "asm.cmt.right", (opts & BODY_SUMMARY) || o_cmtright);
2125 r_config_set_i (core->config, "asm.comments", (opts & BODY_SUMMARY) || o_comments);
2126 r_config_set_i (core->config, "asm.bytes",
2127 (opts & (BODY_SUMMARY | BODY_OFFSETS)) || o_bytes || o_flags_in_bytes);
2128 r_config_set_i (core->config, "asm.bb.middle", false);
2129 core->print->cur_enabled = false;
2130
2131 if (opts & BODY_OFFSETS || opts & BODY_SUMMARY || o_graph_offset) {
2132 r_config_set_i (core->config, "asm.offset", true);
2133 } else {
2134 r_config_set_i (core->config, "asm.offset", false);
2135 }
2136
2137 bool html = r_config_get_i (core->config, "scr.html");
2138 r_config_set_i (core->config, "scr.html", 0);
2139 if (r_config_get_i (core->config, "graph.aeab")) {
2140 body = r_core_cmd_strf (core, "%s 0x%08"PFMT64x, "aeab", addr);
2141 } else {
2142 body = r_core_cmd_strf (core, "%s %d @ 0x%08"PFMT64x, cmd, size, addr);
2143 }
2144 r_config_set_i (core->config, "scr.html", html);
2145
2146 // restore original options
2147 core->print->cur_enabled = o_cursor;
2148 r_config_hold_restore (hc);
2149 r_config_hold_free (hc);
2150 return body;
2151 }
2152
get_bb_body(RCore * core,RAnalBlock * b,int opts,RAnalFunction * fcn,bool emu,ut64 saved_gp,ut8 * saved_arena)2153 static char *get_bb_body(RCore *core, RAnalBlock *b, int opts, RAnalFunction *fcn, bool emu, ut64 saved_gp, ut8 *saved_arena) {
2154 if (emu) {
2155 core->anal->gp = saved_gp;
2156 if (b->parent_reg_arena) {
2157 r_reg_arena_poke (core->anal->reg, b->parent_reg_arena);
2158 R_FREE (b->parent_reg_arena);
2159 ut64 gp = r_reg_getv (core->anal->reg, "gp");
2160 if (gp) {
2161 core->anal->gp = gp;
2162 }
2163 } else {
2164 r_reg_arena_poke (core->anal->reg, saved_arena);
2165 }
2166 }
2167 if (b->parent_stackptr != INT_MAX) {
2168 core->anal->stackptr = b->parent_stackptr;
2169 }
2170 char *body = get_body (core, b->addr, b->size, opts);
2171 if (b->jump != UT64_MAX) {
2172 if (b->jump > b->addr) {
2173 RAnalBlock *jumpbb = r_anal_get_block_at (b->anal, b->jump);
2174 if (jumpbb && r_list_contains (jumpbb->fcns, fcn)) {
2175 if (emu && core->anal->last_disasm_reg != NULL && !jumpbb->parent_reg_arena) {
2176 jumpbb->parent_reg_arena = r_reg_arena_dup (core->anal->reg, core->anal->last_disasm_reg);
2177 }
2178 if (jumpbb->parent_stackptr == INT_MAX) {
2179 jumpbb->parent_stackptr = core->anal->stackptr + b->stackptr;
2180 }
2181 }
2182 }
2183 }
2184 if (b->fail != UT64_MAX) {
2185 if (b->fail > b->addr) {
2186 RAnalBlock *failbb = r_anal_get_block_at (b->anal, b->fail);
2187 if (failbb && r_list_contains (failbb->fcns, fcn)) {
2188 if (emu && core->anal->last_disasm_reg != NULL && !failbb->parent_reg_arena) {
2189 failbb->parent_reg_arena = r_reg_arena_dup (core->anal->reg, core->anal->last_disasm_reg);
2190 }
2191 if (failbb->parent_stackptr == INT_MAX) {
2192 failbb->parent_stackptr = core->anal->stackptr + b->stackptr;
2193 }
2194 }
2195 }
2196 }
2197 return body;
2198 }
2199
bbcmp(RAnalBlock * a,RAnalBlock * b)2200 static int bbcmp(RAnalBlock *a, RAnalBlock *b) {
2201 return a->addr - b->addr;
2202 }
2203
get_bbupdate(RAGraph * g,RCore * core,RAnalFunction * fcn)2204 static void get_bbupdate(RAGraph *g, RCore *core, RAnalFunction *fcn) {
2205 RAnalBlock *bb;
2206 RListIter *iter;
2207 bool emu = r_config_get_i (core->config, "asm.emu");
2208 ut64 saved_gp = core->anal->gp;
2209 ut8 *saved_arena = NULL;
2210 int saved_stackptr = core->anal->stackptr;
2211 char *shortcut = 0;
2212 int shortcuts = 0;
2213 core->keep_asmqjmps = false;
2214
2215 if (emu) {
2216 saved_arena = r_reg_arena_peek (core->anal->reg);
2217 }
2218 if (!fcn) {
2219 R_FREE (saved_arena);
2220 return;
2221 }
2222 r_list_sort (fcn->bbs, (RListComparator) bbcmp);
2223
2224 shortcuts = r_config_get_i (core->config, "graph.nodejmps");
2225 r_list_foreach (fcn->bbs, iter, bb) {
2226 if (bb->addr == UT64_MAX) {
2227 continue;
2228 }
2229 char *body = get_bb_body (core, bb, mode2opts (g), fcn, emu, saved_gp, saved_arena);
2230 char *title = get_title (bb->addr);
2231
2232 if (shortcuts) {
2233 shortcut = r_core_add_asmqjmp (core, bb->addr);
2234 if (shortcut) {
2235 sdb_set (g->db, sdb_fmt ("agraph.nodes.%s.shortcut", title), shortcut, 0);
2236 free (shortcut);
2237 }
2238 }
2239 RANode *node = r_agraph_get_node (g, title);
2240 if (node) {
2241 free (node->body);
2242 node->body = body;
2243 } else {
2244 free (body);
2245 }
2246 R_FREE (node->color);
2247 if (bb->color.r || bb->color.g || bb->color.b) {
2248 node->color = r_cons_rgb_str (NULL, -1, &bb->color);
2249 }
2250 free (title);
2251 core->keep_asmqjmps = true;
2252 }
2253
2254 if (emu) {
2255 core->anal->gp = saved_gp;
2256 if (saved_arena) {
2257 r_reg_arena_poke (core->anal->reg, saved_arena);
2258 R_FREE (saved_arena);
2259 }
2260 }
2261 core->anal->stackptr = saved_stackptr;
2262 }
2263
fold_asm_trace(RCore * core,RAGraph * g)2264 static void fold_asm_trace(RCore *core, RAGraph *g) {
2265 const RList *nodes = r_graph_get_nodes (g->graph);
2266 RGraphNode *gn;
2267 RListIter *it;
2268 RANode *n;
2269
2270 RANode *curnode = get_anode (g->curnode);
2271 graph_foreach_anode (nodes, it, gn, n) {
2272 if (curnode == n) {
2273 n->is_mini = false;
2274 g->need_reload_nodes = true;
2275 continue;
2276 }
2277 ut64 addr = r_num_get (NULL, n->title);
2278 RDebugTracepoint *tp = r_debug_trace_get (core->dbg, addr);
2279 n->is_mini = (tp == NULL);
2280 }
2281 g->need_update_dim = 1;
2282 //agraph_refresh (r_cons_singleton ()->event_data);
2283 }
2284
delete_dup_edges(RAGraph * g)2285 static void delete_dup_edges (RAGraph *g) {
2286 RListIter *it, *in_it, *in_it2, *in_it2_tmp;
2287 RGraphNode *n, *a, *b;
2288 r_list_foreach (g->graph->nodes, it, n) {
2289 r_list_foreach (n->out_nodes, in_it, a) {
2290 for (in_it2 = in_it->n; in_it2 && (b = in_it2->data, in_it2_tmp = in_it2->n, 1); in_it2 = in_it2_tmp) {
2291 if (a->idx == b->idx) {
2292 r_list_delete (n->out_nodes, in_it2);
2293 r_list_delete_data (n->all_neighbours, b);
2294 r_list_delete_data (b->in_nodes, n);
2295 r_list_delete_data (b->all_neighbours, n);
2296 g->graph->n_edges--;
2297 }
2298 }
2299 }
2300 }
2301 }
2302
isbbfew(RAnalBlock * curbb,RAnalBlock * bb)2303 static bool isbbfew(RAnalBlock *curbb, RAnalBlock *bb) {
2304 if (bb->addr == curbb->addr || bb->addr == curbb->jump || bb->addr == curbb->fail) {
2305 // do nothing
2306 return true;
2307 }
2308 if (curbb->switch_op) {
2309 RListIter *it;
2310 RAnalCaseOp *cop;
2311 r_list_foreach (curbb->switch_op->cases, it, cop) {
2312 if (cop->addr == bb->addr) {
2313 return true;
2314 }
2315 }
2316 }
2317 return false;
2318 }
2319
2320 /* build the RGraph inside the RAGraph g, starting from the Basic Blocks */
get_bbnodes(RAGraph * g,RCore * core,RAnalFunction * fcn)2321 static int get_bbnodes(RAGraph *g, RCore *core, RAnalFunction *fcn) {
2322 RAnalBlock *bb;
2323 RListIter *iter;
2324 char *shortcut = NULL;
2325 int shortcuts = 0;
2326 bool emu = r_config_get_i (core->config, "asm.emu");
2327 bool few = r_config_get_i (core->config, "graph.few");
2328 int ret = false;
2329 ut64 saved_gp = core->anal->gp;
2330 ut8 *saved_arena = NULL;
2331 int saved_stackptr = core->anal->stackptr;
2332 core->keep_asmqjmps = false;
2333
2334 if (!fcn) {
2335 return false;
2336 }
2337 if (emu) {
2338 saved_arena = r_reg_arena_peek (core->anal->reg);
2339 }
2340 r_list_sort (fcn->bbs, (RListComparator) bbcmp);
2341 RAnalBlock *curbb = NULL;
2342 if (few) {
2343 r_list_foreach (fcn->bbs, iter, bb) {
2344 if (!curbb) {
2345 curbb = bb;
2346 }
2347 if (r_anal_block_contains (bb, core->offset)) {
2348 curbb = bb;
2349 break;
2350 }
2351 }
2352 }
2353
2354 core->keep_asmqjmps = false;
2355 r_list_foreach (fcn->bbs, iter, bb) {
2356 if (bb->addr == UT64_MAX) {
2357 continue;
2358 }
2359 if (few && !isbbfew (curbb, bb)) {
2360 continue;
2361 }
2362 char *body = get_bb_body (core, bb, mode2opts (g), fcn, emu, saved_gp, saved_arena);
2363 char *title = get_title (bb->addr);
2364 char *color = (bb->color.r || bb->color.g || bb->color.b)? r_cons_rgb_str (NULL, -1, &bb->color): NULL;
2365 RANode *node = r_agraph_add_node (g, title, body, color);
2366 free (color);
2367 shortcuts = g->is_interactive ? r_config_get_i (core->config, "graph.nodejmps") : false;
2368
2369 if (shortcuts) {
2370 shortcut = r_core_add_asmqjmp (core, bb->addr);
2371 if (shortcut) {
2372 sdb_set (g->db, sdb_fmt ("agraph.nodes.%s.shortcut", title), shortcut, 0);
2373 free (shortcut);
2374 }
2375 }
2376 free (body);
2377 free (title);
2378 if (!node) {
2379 goto cleanup;
2380 }
2381 core->keep_asmqjmps = true;
2382 }
2383
2384 r_list_foreach (fcn->bbs, iter, bb) {
2385 if (bb->addr == UT64_MAX) {
2386 continue;
2387 }
2388 if (few && !isbbfew (curbb, bb)) {
2389 continue;
2390 }
2391
2392 char *title = get_title (bb->addr);
2393 RANode *u = r_agraph_get_node (g, title);
2394 RANode *v;
2395 free (title);
2396 if (bb->jump != UT64_MAX) {
2397 title = get_title (bb->jump);
2398 v = r_agraph_get_node (g, title);
2399 free (title);
2400 r_agraph_add_edge (g, u, v);
2401 }
2402 if (bb->fail != UT64_MAX) {
2403 title = get_title (bb->fail);
2404 v = r_agraph_get_node (g, title);
2405 free (title);
2406 r_agraph_add_edge (g, u, v);
2407 }
2408 if (bb->switch_op) {
2409 RListIter *it;
2410 RAnalCaseOp *cop;
2411 r_list_foreach (bb->switch_op->cases, it, cop) {
2412 title = get_title (cop->addr);
2413 v = r_agraph_get_node (g, title);
2414 free (title);
2415 r_agraph_add_edge (g, u, v);
2416 }
2417 }
2418 }
2419
2420 delete_dup_edges (g);
2421 ret = true;
2422
2423 cleanup:
2424 if (emu) {
2425 core->anal->gp = saved_gp;
2426 if (saved_arena) {
2427 r_reg_arena_poke (core->anal->reg, saved_arena);
2428 R_FREE (saved_arena);
2429 }
2430 }
2431 core->anal->stackptr = saved_stackptr;
2432 return ret;
2433 }
2434
2435 /* build the RGraph inside the RAGraph g, starting from the Call Graph
2436 * information */
get_cgnodes(RAGraph * g,RCore * core,RAnalFunction * fcn)2437 static bool get_cgnodes(RAGraph *g, RCore *core, RAnalFunction *fcn) {
2438 RAnalFunction *f = r_anal_get_fcn_in (core->anal, core->offset, 0);
2439 RANode *node, *fcn_anode;
2440 RListIter *iter;
2441 RAnalRef *ref;
2442 RList *refs;
2443 if (!f) {
2444 return false;
2445 }
2446 if (!fcn) {
2447 fcn = f;
2448 }
2449
2450 r_core_seek (core, f->addr, true);
2451
2452 char *title = get_title (fcn->addr);
2453 fcn_anode = r_agraph_add_node (g, title, "", NULL);
2454
2455 free (title);
2456 if (!fcn_anode) {
2457 return false;
2458 }
2459
2460 fcn_anode->x = 10;
2461 fcn_anode->y = 3;
2462
2463 refs = r_anal_function_get_refs (fcn);
2464 r_list_foreach (refs, iter, ref) {
2465 title = get_title (ref->addr);
2466 if (r_agraph_get_node (g, title) != NULL) {
2467 continue;
2468 }
2469 free (title);
2470
2471 int size = 0;
2472 RAnalBlock *bb = r_anal_bb_from_offset (core->anal, ref->addr);
2473 if (bb) {
2474 size = bb->size;
2475 }
2476
2477 char *body = get_body (core, ref->addr, size, mode2opts (g));
2478 title = get_title (ref->addr);
2479
2480 node = r_agraph_add_node (g, title, body, NULL);
2481 if (!node) {
2482 return false;
2483 }
2484
2485 free (title);
2486 free (body);
2487
2488 node->x = 10;
2489 node->y = 10;
2490
2491 r_agraph_add_edge (g, fcn_anode, node);
2492 }
2493 r_list_free (refs);
2494
2495 return true;
2496 }
2497
reload_nodes(RAGraph * g,RCore * core,RAnalFunction * fcn)2498 static bool reload_nodes(RAGraph *g, RCore *core, RAnalFunction *fcn) {
2499 const bool is_c = g->is_callgraph;
2500 return is_c? get_cgnodes (g, core, fcn): get_bbnodes (g, core, fcn);
2501 }
2502
update_seek(RConsCanvas * can,RANode * n,int force)2503 static void update_seek(RConsCanvas *can, RANode *n, int force) {
2504 if (!n) {
2505 return;
2506 }
2507 int x = n->x + can->sx;
2508 int y = n->y + can->sy;
2509 int w = can->w;
2510 int h = can->h;
2511
2512 const bool doscroll = force || y < 0 || y + 5 > h || x + 5 > w || x + n->w + 5 < 0;
2513 if (doscroll) {
2514 if (n->w > w) { //too big for centering
2515 can->sx = -n->x;
2516 } else {
2517 can->sx = -n->x - n->w / 2 + w / 2;
2518 }
2519 if (n->h > h) { //too big for centering
2520 can->sy = -n->y;
2521 } else {
2522 can->sy = -n->y - n->h / 8 + h / 4;
2523 }
2524 }
2525 }
2526
is_near(const RANode * n,int x,int y,int is_next)2527 static int is_near(const RANode *n, int x, int y, int is_next) {
2528 if (is_next) {
2529 return (n->y == y && n->x > x) || n->y > y;
2530 }
2531 return (n->y == y && n->x < x) || n->y < y;
2532 }
2533
2534 /// XXX is wrong
is_near_h(const RANode * n,int x,int y,int is_next)2535 static int is_near_h(const RANode *n, int x, int y, int is_next) {
2536 if (is_next) {
2537 return (n->x == x && n->y > y) || n->x > x;
2538 }
2539 return (n->x == x && n->y < y) || n->x < x;
2540 }
2541
find_near_of(const RAGraph * g,const RGraphNode * cur,int is_next)2542 static const RGraphNode *find_near_of(const RAGraph *g, const RGraphNode *cur, int is_next) {
2543 /* XXX: it's slow */
2544 const RList *nodes = r_graph_get_nodes (g->graph);
2545 const RListIter *it;
2546 const RGraphNode *gn, *resgn = NULL;
2547 const RANode *n, *acur = cur? get_anode (cur): NULL;
2548 const int default_v = is_next? INT_MIN: INT_MAX;
2549 const int start_x = acur? acur->x: default_v;
2550 const int start_y = acur? acur->y: default_v;
2551
2552 graph_foreach_anode (nodes, it, gn, n) {
2553 // tab in horizontal layout is not correct, lets force vertical nextnode for now (g->layout == 0)
2554 bool isNear = true
2555 ? is_near (n, start_x, start_y, is_next)
2556 : is_near_h (n, start_x, start_y, is_next);
2557 if (isNear) {
2558 const RANode *resn;
2559
2560 if (!resgn) {
2561 resgn = gn;
2562 continue;
2563 }
2564
2565 resn = get_anode (resgn);
2566 if ((is_next && resn->y > n->y) || (!is_next && resn->y < n->y)) {
2567 resgn = gn;
2568 } else if ((is_next && resn->y == n->y && resn->x > n->x) ||
2569 (!is_next && resn->y == n->y && resn->x < n->x)) {
2570 resgn = gn;
2571 }
2572 }
2573 }
2574 if (!resgn && cur) {
2575 resgn = find_near_of (g, NULL, is_next);
2576 }
2577 return resgn;
2578 }
2579
update_graph_sizes(RAGraph * g)2580 static void update_graph_sizes(RAGraph *g) {
2581 RListIter *it;
2582 RGraphNode *gk;
2583 RANode *ak, *min_gn, *max_gn;
2584 int max_x, max_y;
2585 int delta_x, delta_y;
2586 AEdge *e;
2587
2588 g->x = g->y = INT_MAX;
2589 max_x = max_y = INT_MIN;
2590 min_gn = max_gn = NULL;
2591
2592 graph_foreach_anode (r_graph_get_nodes (g->graph), it, gk, ak) {
2593 const RList *nd = NULL;
2594 int len;
2595 if (ak->x < g->x) {
2596 g->x = ak->x;
2597 }
2598
2599 nd = r_graph_innodes (g->graph, gk);
2600 len = nd ? r_list_length (nd) + 1 : 0;
2601 if (ak->y - len < g->y) {
2602 g->y = ak->y - len;
2603 min_gn = ak;
2604 }
2605
2606 if (ak->x + ak->w > max_x) {
2607 max_x = ak->x + ak->w;
2608 }
2609
2610 nd = NULL;
2611 nd = r_graph_get_neighbours (g->graph, gk);
2612 len = nd ? r_list_length (nd) + 2 : 0;
2613 if (ak->y + ak->h + len > max_y) {
2614 max_y = ak->y + ak->h + len;
2615 max_gn = ak;
2616 }
2617 }
2618 /* while calculating the graph size, take into account long edges */
2619 r_list_foreach (g->edges, it, e) {
2620 RListIter *kt;
2621 void *vv;
2622 int v;
2623 if (r_cons_is_breaked ()) {
2624 break;
2625 }
2626 r_list_foreach (e->x, kt, vv) {
2627 v = (int) (size_t) vv;
2628 if (v < g->x) {
2629 g->x = v;
2630 }
2631 if (v + 1 > max_x) {
2632 max_x = v + 1;
2633 }
2634 }
2635 r_list_foreach (e->y, kt, vv) {
2636 v = (int) (size_t) vv;
2637 if (v < g->y) {
2638 g->y = v;
2639 }
2640 if (v + 1 > max_y) {
2641 max_y = v + 1;
2642 }
2643 }
2644 }
2645 r_cons_break_pop ();
2646
2647 if (min_gn) {
2648 const RList *neigh = r_graph_innodes (g->graph, min_gn->gnode);
2649 if (r_list_length (neigh) > 0) {
2650 g->y--;
2651 max_y++;
2652 }
2653 if (max_gn) {
2654 const RList *neigh = r_graph_get_neighbours (g->graph, min_gn->gnode);
2655 if (r_list_length (neigh) > 0) {
2656 max_y++;
2657 }
2658 }
2659 }
2660
2661 if (g->x != INT_MAX && g->y != INT_MAX) {
2662 g->w = max_x - g->x;
2663 if (g->title) {
2664 size_t len = strlen (g->title);
2665 if (len > INT_MAX) {
2666 g->w = INT_MAX;
2667 }
2668 if ((int) len > g->w) {
2669 g->w = len;
2670 }
2671 }
2672 g->h = max_y - g->y;
2673 } else {
2674 g->x = g->y = 0;
2675 g->w = g->h = 0;
2676 }
2677
2678 sdb_num_set (g->db, "agraph.w", g->w, 0);
2679 sdb_num_set (g->db, "agraph.h", g->h, 0);
2680 /* delta_x, delta_y are needed to make every other x,y coordinates
2681 * unsigned, so that we can use sdb_num_ API */
2682 delta_x = g->x < 0? -g->x: 0;
2683 delta_y = g->y < 0? -g->y: 0;
2684 sdb_num_set (g->db, "agraph.delta_x", delta_x, 0);
2685 sdb_num_set (g->db, "agraph.delta_y", delta_y, 0);
2686 }
2687
r_agraph_set_curnode(RAGraph * g,RANode * a)2688 R_API void r_agraph_set_curnode(RAGraph *g, RANode *a) {
2689 if (!a) {
2690 return;
2691 }
2692 g->curnode = a->gnode;
2693 if (a->title) {
2694 sdb_set (g->db, "agraph.curnode", a->title, 0);
2695 if (g->on_curnode_change) {
2696 g->on_curnode_change (a, g->on_curnode_change_data);
2697 }
2698 }
2699 }
2700
rebase(RAGraph * g,int v)2701 static ut64 rebase(RAGraph *g, int v) {
2702 return g->x < 0? -g->x + v: v;
2703 }
2704
agraph_set_layout(RAGraph * g)2705 static void agraph_set_layout(RAGraph *g) {
2706 RListIter *it;
2707 RGraphNode *n;
2708 RANode *a;
2709
2710 set_layout (g);
2711
2712 update_graph_sizes (g);
2713 graph_foreach_anode (r_graph_get_nodes (g->graph), it, n, a) {
2714 if (a->is_dummy) {
2715 continue;
2716 }
2717 const char *k;
2718 k = sdb_fmt ("agraph.nodes.%s.x", a->title);
2719 sdb_num_set (g->db, k, rebase (g, a->x), 0);
2720 k = sdb_fmt ("agraph.nodes.%s.y", a->title);
2721 sdb_num_set (g->db, k, rebase (g, a->y), 0);
2722 k = sdb_fmt ("agraph.nodes.%s.w", a->title);
2723 sdb_num_set (g->db, k, a->w, 0);
2724 k = sdb_fmt ("agraph.nodes.%s.h", a->title);
2725 sdb_num_set (g->db, k, a->h, 0);
2726 }
2727 }
2728
2729 /* set the willing to center the screen on a particular node */
agraph_update_seek(RAGraph * g,RANode * n,int force)2730 static void agraph_update_seek(RAGraph *g, RANode *n, int force) {
2731 g->update_seek_on = n;
2732 g->force_update_seek = force;
2733 }
2734
agraph_print_node(const RAGraph * g,RANode * n)2735 static void agraph_print_node(const RAGraph *g, RANode *n) {
2736 if (n->is_dummy) {
2737 return;
2738 }
2739 const int cur = g->curnode && get_anode (g->curnode) == n;
2740 const bool isMini = is_mini (g);
2741 if (g->is_tiny) {
2742 tiny_RANode_print (g, n, cur);
2743 } else if (isMini || n->is_mini) {
2744 mini_RANode_print (g, n, cur, isMini);
2745 } else {
2746 normal_RANode_print (g, n, cur);
2747 }
2748 }
2749
agraph_print_nodes(const RAGraph * g)2750 static void agraph_print_nodes(const RAGraph *g) {
2751 const RList *nodes = r_graph_get_nodes (g->graph);
2752 RGraphNode *gn;
2753 RListIter *it;
2754 RANode *n;
2755
2756 graph_foreach_anode (nodes, it, gn, n) {
2757 if (gn != g->curnode) {
2758 agraph_print_node (g, n);
2759 }
2760 }
2761
2762 /* draw current node now to make it appear on top */
2763 if (g->curnode) {
2764 agraph_print_node (g, get_anode (g->curnode));
2765 }
2766 }
2767
2768 struct tmplayer {
2769 int layer;
2770 int edgectr;
2771 int revedgectr;
2772 int minx;
2773 int maxx;
2774 };
2775 struct tmpbackedgeinfo {
2776 int ax;
2777 int ay;
2778 int bx;
2779 int by;
2780 int edgectr;
2781 int fromlayer;
2782 int tolayer;
2783 RCanvasLineStyle style;
2784 };
2785
tmplayercmp(const void * a,const void * b)2786 int tmplayercmp (const void *a, const void *b) {
2787 return ((struct tmplayer *)a)->layer > ((struct tmplayer *)b)->layer;
2788 }
2789
agraph_print_edges_simple(RAGraph * g)2790 static void agraph_print_edges_simple(RAGraph *g) {
2791 RCanvasLineStyle style = {0};
2792 RANode *n, *n2;
2793 RGraphNode *gn, *gn2;
2794 RListIter *iter, *iter2;
2795 const RList *nodes = r_graph_get_nodes (g->graph);
2796 graph_foreach_anode (nodes, iter, gn, n) {
2797 const RList *outnodes = n->gnode->out_nodes;
2798 graph_foreach_anode (outnodes, iter2, gn2, n2) {
2799 int sx = n->w / 2;
2800 int sy = n->h;
2801 int sx2 = n2->w / 2;
2802 if (g->is_tiny) {
2803 sx = 0;
2804 sy = 0;
2805 sx2 = 0;
2806 }
2807 // TODO: better alignments here
2808 r_cons_canvas_line (g->can,
2809 n->x + sx, n->y + sy,
2810 n2->x + sx2, n2->y, &style);
2811
2812 if (n2->is_dummy) {
2813 r_cons_canvas_line (g->can,
2814 n2->x + sx2, n2->y - 1,
2815 n2->x + sx2, n2->y + n2->h, &style);
2816 }
2817 }
2818 }
2819 }
2820
first_x_cmp(const void * _a,const void * _b)2821 static int first_x_cmp (const void *_a, const void *_b) {
2822 RGraphNode *ga = (RGraphNode *)_a;
2823 RGraphNode *gb = (RGraphNode *)_b;
2824 RANode *a = (RANode*) ga->data;
2825 RANode *b = (RANode*) gb->data;
2826 if (b->y < a->y) {
2827 return -1;
2828 }
2829 if (b->y > a->y) {
2830 return 1;
2831 }
2832 if (a->x < b->x) {
2833 return 1;
2834 }
2835 if (a->x > b->x) {
2836 return -1;
2837 }
2838 return 0;
2839 }
2840
agraph_print_edges(RAGraph * g)2841 static void agraph_print_edges(RAGraph *g) {
2842 if (!g->edgemode) {
2843 return;
2844 }
2845 if (g->edgemode == 1) {
2846 agraph_print_edges_simple (g);
2847 return;
2848 }
2849 int out_nth, in_nth, bendpoint;
2850 RListIter *itn, *itm, *ito;
2851 RCanvasLineStyle style = {0};
2852 const RList *nodes = r_graph_get_nodes (g->graph);
2853 RGraphNode *ga;
2854 RANode *a;
2855
2856 RList *lyr = r_list_new ();
2857 RList *bckedges = r_list_new ();
2858 struct tmplayer *tl, *tm;
2859
2860 graph_foreach_anode (nodes, itm, ga, a) {
2861 const RGraphNode *gb;
2862 RANode *b;
2863 RList *neighbours = (RList *)r_graph_get_neighbours (g->graph, ga);
2864 int ax, ay, bx, by, a_x_inc, b_x_inc;
2865 tl = tm = NULL;
2866 if (r_cons_is_breaked ()) {
2867 break;
2868 }
2869
2870 r_list_foreach (lyr, ito, tl) {
2871 if (tl->layer == a->layer) {
2872 tm = tl;
2873 if (g->layout == 0) { //vertical layout
2874 if (tm->minx > a->x) {
2875 tm->minx = a->x;
2876 }
2877 if (tm->maxx < a->x + a->w) {
2878 tm->maxx = a->x + a->w;
2879 }
2880 } else {
2881 if (tm->minx > a->y) {
2882 tm->minx = a->y;
2883 }
2884 if (tm->maxx < a->y + a->h) {
2885 tm->maxx = a->y + a->h;
2886 }
2887 }
2888 break;
2889 }
2890 }
2891
2892 if (!tm) {
2893 tm = R_NEW0 (struct tmplayer);
2894 if (tm) {
2895 tm->layer = a->layer;
2896 tm->edgectr = 0;
2897 tm->revedgectr = 0;
2898 if (g->layout == 0) { //vertical layout
2899 tm->minx = a->x;
2900 tm->maxx = a->x + a->w;
2901 } else {
2902 tm->minx = a->y;
2903 tm->maxx = a->y + a->h;
2904 }
2905 r_list_add_sorted (lyr, tm, tmplayercmp);
2906 }
2907 }
2908
2909 bool many = r_list_length (neighbours) > 2;
2910
2911 if (many && !g->is_callgraph) {
2912 ga->out_nodes->sorted = false;
2913 r_list_sort (neighbours, first_x_cmp);
2914 }
2915
2916 graph_foreach_anode (neighbours, itn, gb, b) {
2917 out_nth = get_edge_number (g, a, b, true);
2918 in_nth = get_edge_number (g, a, b, false);
2919
2920 bool parent_many = false;
2921 if (a->is_dummy) {
2922 RANode *in = (RANode *) (((RGraphNode *)r_list_first (ga->in_nodes))->data);
2923 while (in && in->is_dummy) {
2924 in = (RANode *) (((RGraphNode *)r_list_first ((in->gnode)->in_nodes))->data);
2925 }
2926 if (in && in->gnode) {
2927 parent_many = r_list_length (in->gnode->out_nodes) > 2;
2928 } else {
2929 parent_many = false;
2930 }
2931 }
2932
2933 style.dot_style = DOT_STYLE_NORMAL;
2934 if (many || parent_many) {
2935 style.color = LINE_UNCJMP;
2936 } else {
2937 switch (out_nth) {
2938 case 0:
2939 style.color = LINE_TRUE;
2940 style.dot_style = DOT_STYLE_CONDITIONAL;
2941 break;
2942 case 1:
2943 style.color = LINE_FALSE;
2944 style.dot_style = DOT_STYLE_CONDITIONAL;
2945 break;
2946 case -1:
2947 style.color = LINE_UNCJMP;
2948 break;
2949 default:
2950 style.color = LINE_NONE;
2951 break;
2952 }
2953 }
2954
2955 switch (g->layout) {
2956 case 0:
2957 default:
2958 style.symbol = (!g->hints || a->is_dummy) ? LINE_NOSYM_VERT : style.color;
2959 if (a->y + a->h > b->y) {
2960 style.dot_style = DOT_STYLE_BACKEDGE;
2961 }
2962
2963 a_x_inc = R_EDGES_X_INC + 2 * (out_nth + 1);
2964 b_x_inc = R_EDGES_X_INC + 2 * (in_nth + 1);
2965
2966 bx = b->is_dummy ? b->x : (b->x + b_x_inc);
2967 ay = a->y + a->h;
2968 by = b->y - 1;
2969
2970 if (many && !g->is_callgraph) {
2971 int t = R_EDGES_X_INC + 2 * (neighbours->length + 1);
2972 ax = a->is_dummy ? a->x : (a->x + a->w/2 + (t/2 - a_x_inc));
2973 bendpoint = bx < ax ? neighbours->length - out_nth : out_nth;
2974 } else {
2975 ax = a->is_dummy ? a->x : (a->x + a_x_inc);
2976 bendpoint = tm->edgectr;
2977 }
2978
2979 if (!a->is_dummy && itn == neighbours->head && out_nth == 0 && bx > ax) {
2980 ax += (many && !g->is_callgraph) ? 0 : 4;
2981 }
2982 if (a->h < a->layer_height) {
2983 r_cons_canvas_line (g->can, ax, ay, ax, ay + a->layer_height - a->h, &style);
2984 ay = a->y + a->layer_height;
2985 style.symbol = LINE_NOSYM_VERT;
2986 }
2987 if (by >= ay) {
2988 r_cons_canvas_line_square_defined (g->can, ax, ay, bx, by, &style, bendpoint, true);
2989 } else {
2990 struct tmpbackedgeinfo *tmp = calloc (1, sizeof (struct tmpbackedgeinfo));
2991 tmp->ax = ax;
2992 tmp->bx = bx;
2993 tmp->ay = ay;
2994 tmp->by = by;
2995 tmp->edgectr = bendpoint;
2996 tmp->fromlayer = a->layer;
2997 tmp->tolayer = b->layer;
2998 tmp->style = style;
2999 r_list_append (bckedges, tmp);
3000 }
3001 if (b->is_dummy) {
3002 style.symbol = LINE_NOSYM_VERT;
3003 r_cons_canvas_line (g->can, bx, by, bx, b->y + b->h, &style);
3004 }
3005 if (b->x != a->x || b->layer <= a->layer || (!a->is_dummy && b->is_dummy) || (a->is_dummy && !b->is_dummy)) {
3006 if (tm) {
3007 tm->edgectr++;
3008 }
3009 }
3010 break;
3011 case 1:
3012 style.symbol = (!g->hints || a->is_dummy) ? LINE_NOSYM_HORIZ : style.color;
3013 if (a->x + a->w > b->x) {
3014 style.dot_style = DOT_STYLE_BACKEDGE;
3015 }
3016
3017 ax = a->x;
3018 if (g->zoom > 0) {
3019 ax += a->w;
3020 } else {
3021 ax ++;
3022 }
3023 ay = a->y;
3024 if (!a->is_dummy && g->zoom > 0) {
3025 ay += R_EDGES_X_INC + out_nth;
3026 }
3027 bx = b->x - 1;
3028 by = b->y;
3029 if (!b->is_dummy && g->zoom > 0) {
3030 by += R_EDGES_X_INC + out_nth;
3031 }
3032
3033 if (a->w < a->layer_width) {
3034 r_cons_canvas_line_square_defined (g->can, ax, ay, a->x + a->layer_width, ay, &style, 0, false);
3035 ax = a->x;
3036 if (g->zoom > 1) {
3037 ax += a->layer_width;
3038 } else {
3039 ax += 1;
3040 }
3041 style.symbol = LINE_NOSYM_HORIZ;
3042 }
3043 if (bx >= ax) {
3044 r_cons_canvas_line_square_defined (g->can, ax, ay, bx, by, &style, tm->edgectr, false);
3045 } else {
3046 struct tmpbackedgeinfo *tmp = calloc (1, sizeof (struct tmpbackedgeinfo));
3047 if (tmp) {
3048 tmp->ax = ax;
3049 tmp->bx = bx;
3050 tmp->ay = ay;
3051 tmp->by = by;
3052 tmp->edgectr = tm->edgectr;
3053 tmp->fromlayer = a->layer;
3054 tmp->tolayer = b->layer;
3055 tmp->style = style;
3056 r_list_append (bckedges, tmp);
3057 }
3058 }
3059 if (b->is_dummy) {
3060 style.symbol = LINE_NOSYM_HORIZ;
3061 r_cons_canvas_line_square_defined (g->can, bx, by, bx + b->layer_width, by, &style, 0, false);
3062 }
3063 if ((b->y == a->y && b->h != a->h) || b->y != a->y || b->layer <= a->layer || (!a->is_dummy && b->is_dummy) || (a->is_dummy && !b->is_dummy)) {
3064 tm->edgectr += 1;
3065 }
3066 break;
3067 }
3068 }
3069 }
3070
3071 struct tmpbackedgeinfo *temp;
3072 r_list_foreach (bckedges, itm, temp) {
3073 int leftlen, rightlen;
3074 int minx = 0, maxx = 0;
3075 struct tmplayer *tt = NULL;
3076 tl = r_list_get_n (lyr, temp->fromlayer);
3077 if (r_cons_is_breaked ()) {
3078 break;
3079 }
3080
3081 r_list_foreach (lyr, ito, tl) {
3082 if (tl->layer <= temp->tolayer) {
3083 tt = tl;
3084 minx = tl->minx;
3085 maxx = tl->maxx;
3086 continue;
3087 }
3088 minx = minx < tl->minx ? minx : tl->minx;
3089 maxx = maxx > tl->maxx ? maxx : tl->maxx;
3090 if (tl->layer >= temp->fromlayer) {
3091 break;
3092 }
3093 }
3094
3095 if (tt) {
3096 tt->revedgectr += 1;
3097 }
3098 if (g->layout == 0) {
3099 leftlen = (temp->ax - minx) + (temp->bx - minx);
3100 rightlen = (maxx - temp->ax) + (maxx - temp->bx);
3101 } else {
3102 leftlen = (temp->ay - minx) + (temp->by - minx);
3103 rightlen = (maxx - temp->ay) + (maxx - temp->by);
3104 }
3105
3106 if (tt) {
3107 int arg = (rightlen < leftlen)? maxx + 1: minx - 1;
3108 r_cons_canvas_line_back_edge (g->can, temp->ax, temp->ay, temp->bx, temp->by, &(temp->style), temp->edgectr, arg, tt->revedgectr, !g->layout);
3109 }
3110
3111 r_list_foreach (lyr, ito, tl) {
3112 if (tl->layer < temp->tolayer) {
3113 continue;
3114 }
3115 if (rightlen < leftlen) {
3116 tl->maxx = maxx + 1;
3117 } else {
3118 tl->minx = minx - 1;
3119 }
3120 if (tl->layer >= temp->fromlayer) {
3121 break;
3122 }
3123 }
3124 }
3125
3126 r_list_foreach (lyr, ito, tl) {
3127 free (tl);
3128 }
3129
3130 r_list_foreach (bckedges, ito, tl) {
3131 free (tl);
3132 }
3133
3134 r_list_free (lyr);
3135 r_list_free (bckedges);
3136 r_cons_break_pop ();
3137 }
3138
agraph_toggle_callgraph(RAGraph * g)3139 static void agraph_toggle_callgraph(RAGraph *g) {
3140 g->is_callgraph = !g->is_callgraph;
3141 g->need_reload_nodes = true;
3142 g->force_update_seek = true;
3143 }
3144
agraph_set_zoom(RAGraph * g,int v)3145 static void agraph_set_zoom(RAGraph *g, int v) {
3146 if (v >= -10) {
3147 g->is_tiny = false;
3148 if (v == 0) {
3149 g->mode = R_AGRAPH_MODE_MINI;
3150 } else if (v < 0) {
3151 g->mode = R_AGRAPH_MODE_TINY;
3152 g->is_tiny = true;
3153 } else {
3154 g->mode = R_AGRAPH_MODE_NORMAL;
3155 }
3156 const int K = 920;
3157 if (g->zoom < v) {
3158 g->can->sy = (g->can->sy * K) / 1000;
3159 }
3160 else {
3161 g->can->sy = (g->can->sy * 1000) / K;
3162 }
3163 g->zoom = v;
3164 g->need_update_dim = true;
3165 g->need_set_layout = true;
3166 }
3167 }
3168
3169 /* reload all the info in the nodes, depending on the type of the graph
3170 * (callgraph, CFG, etc.), set the default layout for these nodes and center
3171 * the screen on the selected one */
agraph_reload_nodes(RAGraph * g,RCore * core,RAnalFunction * fcn)3172 static bool agraph_reload_nodes(RAGraph *g, RCore *core, RAnalFunction *fcn) {
3173 r_agraph_reset (g);
3174 return reload_nodes (g, core, fcn);
3175 }
3176
follow_nth(RAGraph * g,int nth)3177 static void follow_nth(RAGraph *g, int nth) {
3178 const RGraphNode *cn = r_graph_nth_neighbour (g->graph, g->curnode, nth);
3179 RANode *a = get_anode (cn);
3180
3181 while (a && a->is_dummy) {
3182 cn = r_graph_nth_neighbour (g->graph, a->gnode, 0);
3183 a = get_anode (cn);
3184 }
3185 if (a) {
3186 r_agraph_set_curnode (g, a);
3187 }
3188 }
3189
move_current_node(RAGraph * g,int xdiff,int ydiff)3190 static void move_current_node(RAGraph *g, int xdiff, int ydiff) {
3191 RANode *n = get_anode (g->curnode);
3192 if (n) {
3193 if (is_tiny (g)) {
3194 xdiff = NORMALIZE_MOV (xdiff);
3195 ydiff = NORMALIZE_MOV (ydiff);
3196 }
3197 n->x += xdiff;
3198 n->y += ydiff;
3199 }
3200 }
3201
3202 #if GRAPH_MERGE_FEATURE
3203 #define K_NEIGHBOURS(x) (sdb_fmt ("agraph.nodes.%s.neighbours", x->title))
agraph_merge_child(RAGraph * g,int idx)3204 static void agraph_merge_child(RAGraph *g, int idx) {
3205 const RGraphNode *nn = r_graph_nth_neighbour (g->graph, g->curnode, idx);
3206 const RGraphNode *cn = g->curnode;
3207 if (cn && nn) {
3208 RANode *ann = get_anode (nn);
3209 RANode *acn = get_anode (cn);
3210 acn->body = r_str_append (acn->body, ann->title);
3211 acn->body = r_str_append (acn->body, "\n");
3212 acn->body = r_str_append (acn->body, ann->body);
3213 /* remove node from the graph */
3214 acn->h += ann->h - 3;
3215 free (ann->body);
3216 // TODO: do not merge nodes if those have edges targeting them
3217 // TODO: Add children neighbours to current one
3218 // nn->body
3219 // r_agraph_set_curnode (g, get_anode (cn));
3220 // agraph_refresh (grd);
3221 // r_agraph_add_edge (g, from, to);
3222 char *neis = sdb_get (g->db, K_NEIGHBOURS (ann), 0);
3223 if (neis) {
3224 sdb_set_owned (g->db, K_NEIGHBOURS (ann), neis, 0);
3225 r_agraph_del_node (g, ann->title);
3226 agraph_print_nodes (g);
3227 agraph_print_edges (g);
3228 }
3229 }
3230 // agraph_update_seek (g, get_anode (g->curnode), false);
3231 }
3232 #endif
3233
agraph_toggle_tiny(RAGraph * g)3234 static void agraph_toggle_tiny (RAGraph *g) {
3235 g->is_tiny = !g->is_tiny;
3236 g->need_update_dim = 1;
3237 agraph_refresh (r_cons_singleton ()->event_data);
3238 agraph_set_layout ((RAGraph *) g);
3239 //remove_dummy_nodes (g);
3240 }
3241
agraph_toggle_mini(RAGraph * g)3242 static void agraph_toggle_mini(RAGraph *g) {
3243 RANode *n = get_anode (g->curnode);
3244 if (n) {
3245 n->is_mini = !n->is_mini;
3246 }
3247 g->need_update_dim = 1;
3248 agraph_refresh (r_cons_singleton ()->event_data);
3249 agraph_set_layout ((RAGraph *) g);
3250 }
3251
agraph_follow_innodes(RAGraph * g,bool in)3252 static void agraph_follow_innodes(RAGraph *g, bool in) {
3253 int count = 0;
3254 RListIter *iter;
3255 RANode *an = get_anode (g->curnode);
3256 if (!an) {
3257 return;
3258 }
3259 const RList *list = in? an->gnode->in_nodes: an->gnode->out_nodes;
3260 int nth = -1;
3261 if (r_list_length (list) == 0) {
3262 return;
3263 }
3264 r_cons_gotoxy (0, 2);
3265 r_cons_printf (in? "Input nodes:\n": "Output nodes:\n");
3266 RList *options = r_list_newf (NULL);
3267 RList *gnodes = in? an->gnode->in_nodes: an->gnode->out_nodes;
3268 RGraphNode *gn;
3269 r_list_foreach (gnodes, iter, gn) {
3270 RANode *an = get_anode (gn);
3271 RGraphNode *gnn = agraph_get_title (g, an, in);
3272 if (gnn) {
3273 RANode *nnn = gnn->data;
3274 RANode *o;
3275 RListIter *iter2;
3276 // avoid dupes
3277 r_list_foreach (options, iter2, o) {
3278 if (!strcmp (o->title, nnn->title)) {
3279 continue;
3280 }
3281 }
3282 r_cons_printf ("%d %s\n", count, nnn->title);
3283 r_list_append (options, nnn);
3284 count++;
3285 }
3286 }
3287 r_cons_flush ();
3288 if (r_list_length (list) == 1) {
3289 nth = 0;
3290 } else if (r_list_length (list) < 10) {
3291 // just 1 key
3292 char ch = r_cons_readchar ();
3293 if (ch >= '0' && ch <= '9') {
3294 nth = ch - '0';
3295 }
3296 } else {
3297 r_cons_show_cursor (true);
3298 r_cons_enable_mouse (false);
3299 char *nth_string = r_cons_input ("index> ");
3300 nth = atoi (nth_string);
3301 if (nth == 0 && *nth_string != '0') {
3302 nth = -1;
3303 }
3304 free (nth_string);
3305 }
3306 if (nth != -1) {
3307 RANode *selected_node = r_list_get_n (options, nth);
3308 r_agraph_set_curnode (g, selected_node);
3309 }
3310 r_list_free (options);
3311 agraph_update_seek (g, get_anode (g->curnode), false);
3312 }
3313
agraph_follow_true(RAGraph * g)3314 static void agraph_follow_true(RAGraph *g) {
3315 follow_nth (g, 0);
3316 agraph_update_seek (g, get_anode (g->curnode), false);
3317 }
3318
agraph_follow_false(RAGraph * g)3319 static void agraph_follow_false(RAGraph *g) {
3320 follow_nth (g, 1);
3321 agraph_update_seek (g, get_anode (g->curnode), false);
3322 }
3323
3324 /* seek the next node in visual order */
agraph_next_node(RAGraph * g)3325 static void agraph_next_node(RAGraph *g) {
3326 RANode *a = get_anode (find_near_of (g, g->curnode, true));
3327 while (a && a->is_dummy) {
3328 a = get_anode (find_near_of (g, a->gnode, true));
3329 }
3330 r_agraph_set_curnode (g, a);
3331 agraph_update_seek (g, get_anode (g->curnode), false);
3332 }
3333
3334 /* seek the previous node in visual order */
agraph_prev_node(RAGraph * g)3335 static void agraph_prev_node(RAGraph *g) {
3336 RANode *a = get_anode (find_near_of (g, g->curnode, false));
3337 while (a && a->is_dummy) {
3338 a = get_anode (find_near_of (g, a->gnode, false));
3339 }
3340 r_agraph_set_curnode (g, a);
3341 agraph_update_seek (g, get_anode (g->curnode), false);
3342 }
3343
agraph_update_title(RCore * core,RAGraph * g,RAnalFunction * fcn)3344 static void agraph_update_title(RCore *core, RAGraph *g, RAnalFunction *fcn) {
3345 RANode *a = get_anode (g->curnode);
3346 char *sig = r_core_cmd_str (core, "afcf");
3347 char *new_title = r_str_newf (
3348 "%s[0x%08"PFMT64x "]> %s # %s ",
3349 graphCursor? "(cursor)": "",
3350 fcn->addr, a? a->title: "", sig);
3351 r_agraph_set_title (g, new_title);
3352 free (new_title);
3353 free (sig);
3354 }
3355
3356 /* look for any change in the state of the graph
3357 * and update what's necessary */
check_changes(RAGraph * g,int is_interactive,RCore * core,RAnalFunction * fcn)3358 static bool check_changes(RAGraph *g, int is_interactive, RCore *core, RAnalFunction *fcn) {
3359 int oldpos[2] = {
3360 0, 0
3361 };
3362 if (g->need_reload_nodes && core) {
3363 if (!g->update_seek_on && !g->force_update_seek) {
3364 // save scroll here
3365 oldpos[0] = g->can->sx;
3366 oldpos[1] = g->can->sy;
3367 }
3368 if (!agraph_reload_nodes (g, core, fcn)) {
3369 return false;
3370 }
3371 }
3372 if (fcn) {
3373 agraph_update_title (core, g, fcn);
3374 }
3375 if (core && core->config) {
3376 if (r_config_get_i (core->config, "graph.trace")) {
3377 // fold all bbs not traced
3378 fold_asm_trace (core, g);
3379 }
3380 }
3381 if (g->need_update_dim || g->need_reload_nodes || !is_interactive) {
3382 update_node_dimension (g->graph, is_mini (g), g->zoom, g->edgemode, g->is_callgraph, g->layout);
3383 }
3384 if (g->need_set_layout || g->need_reload_nodes || !is_interactive) {
3385 agraph_set_layout (g);
3386 }
3387 if (core) {
3388 ut64 off = r_anal_get_bbaddr (core->anal, core->offset);
3389 if (off != UT64_MAX) {
3390 char *title = get_title (off);
3391 RANode *cur_anode = get_anode (g->curnode);
3392 if (fcn && ((is_interactive && !cur_anode) || (cur_anode && strcmp (cur_anode->title, title)))) {
3393 g->update_seek_on = r_agraph_get_node (g, title);
3394 if (g->update_seek_on) {
3395 r_agraph_set_curnode (g, g->update_seek_on);
3396 g->force_update_seek = true;
3397 }
3398 }
3399 free (title);
3400 }
3401 g->can->color = r_config_get_i (core->config, "scr.color");
3402 g->hints = r_config_get_i (core->config, "graph.hints");
3403 }
3404 if (g->update_seek_on || g->force_update_seek) {
3405 RANode *n = g->update_seek_on;
3406 if (!n && g->curnode) {
3407 n = get_anode (g->curnode);
3408 }
3409 if (n) {
3410 update_seek (g->can, n, g->force_update_seek);
3411 }
3412 }
3413 if (oldpos[0] || oldpos[1]) {
3414 g->can->sx = oldpos[0];
3415 g->can->sy = oldpos[1];
3416 }
3417 g->need_reload_nodes = false;
3418 g->need_update_dim = false;
3419 g->need_set_layout = false;
3420 g->update_seek_on = NULL;
3421 g->force_update_seek = false;
3422 return true;
3423 }
3424
agraph_print(RAGraph * g,int is_interactive,RCore * core,RAnalFunction * fcn)3425 static int agraph_print(RAGraph *g, int is_interactive, RCore *core, RAnalFunction *fcn) {
3426 int h, w = r_cons_get_size (&h);
3427 bool ret = check_changes (g, is_interactive, core, fcn);
3428 if (!ret) {
3429 return false;
3430 }
3431
3432 if (is_interactive) {
3433 r_cons_clear00 ();
3434 } else {
3435 /* TODO: limit to screen size when the output is not redirected to file */
3436 update_graph_sizes (g);
3437 }
3438
3439 h = is_interactive? h: g->h + 1;
3440 w = is_interactive? w: g->w + 2;
3441 if (!r_cons_canvas_resize (g->can, w, h)) {
3442 return false;
3443 }
3444 // r_cons_canvas_clear (g->can);
3445 if (!is_interactive) {
3446 g->can->sx = -g->x;
3447 g->can->sy = -g->y - 1;
3448 }
3449 if (g->is_dis) {
3450 (void) G (-g->can->sx + 1, -g->can->sy + 2);
3451 int scr_utf8 = r_config_get_i (core->config, "scr.utf8");
3452 int asm_bytes = r_config_get_i (core->config, "asm.bytes");
3453 int asm_cmt_right = r_config_get_i (core->config, "asm.cmt.right");
3454 r_config_set_i (core->config, "scr.utf8", 0);
3455 r_config_set_i (core->config, "asm.bytes", 0);
3456 r_config_set_i (core->config, "asm.cmt.right", 0);
3457 char *str = r_core_cmd_str (core, "pd $r");
3458 if (str) {
3459 W (str);
3460 free (str);
3461 }
3462 r_config_set_i (core->config, "scr.utf8", scr_utf8);
3463 r_config_set_i (core->config, "asm.bytes", asm_bytes);
3464 r_config_set_i (core->config, "asm.cmt.right", asm_cmt_right);
3465 }
3466 if (g->title && *g->title) {
3467 g->can->sy ++;
3468 }
3469 agraph_print_edges (g);
3470 agraph_print_nodes (g);
3471 if (g->title && *g->title) {
3472 g->can->sy --;
3473 }
3474 /* print the graph title */
3475 (void) G (-g->can->sx, -g->can->sy);
3476 if (!g->is_tiny) {
3477 W (g->title);
3478 }
3479 if (is_interactive && g->title) {
3480 int title_len = strlen (g->title);
3481 r_cons_canvas_fill (g->can, -g->can->sx + title_len, -g->can->sy,
3482 w - title_len, 1, ' ');
3483 }
3484
3485 r_cons_canvas_print_region (g->can);
3486
3487 if (is_interactive) {
3488 r_cons_newline ();
3489 const char *cmdv = r_config_get (core->config, "cmd.gprompt");
3490 bool mustFlush = false;
3491 r_cons_visual_flush ();
3492 if (cmdv && *cmdv) {
3493 r_cons_gotoxy (0, 2);
3494 r_cons_strcat (Color_RESET);
3495 r_core_cmd0 (core, cmdv);
3496 mustFlush = true;
3497 }
3498 if (core && core->scr_gadgets) {
3499 r_core_cmd0 (core, "pg");
3500 }
3501 if (mustFlush) {
3502 r_cons_flush ();
3503 }
3504 }
3505 return true;
3506 }
3507
check_function_modified(RCore * core,RAnalFunction * fcn)3508 static void check_function_modified(RCore *core, RAnalFunction *fcn) {
3509 if (r_anal_function_was_modified (fcn)) {
3510 if (r_config_get_i (core->config, "anal.detectwrites")
3511 || r_cons_yesno ('y', "Function was modified. Reanalyze? (Y/n)")) {
3512 r_anal_function_update_analysis (fcn);
3513 }
3514 }
3515 }
3516
agraph_refresh(struct agraph_refresh_data * grd)3517 static int agraph_refresh(struct agraph_refresh_data *grd) {
3518 if (!grd) {
3519 return 0;
3520 }
3521 r_cons_singleton ()->event_data = grd;
3522 RCore *core = grd->core;
3523 RAGraph *g = grd->g;
3524 RAnalFunction *f = NULL;
3525 RAnalFunction **fcn = grd->fcn;
3526
3527 if (!fcn) {
3528 return agraph_print (g, grd->fs, core, NULL);
3529 }
3530
3531 // allow to change the current function during debugging
3532 if (g->is_instep && r_config_get_i (core->config, "cfg.debug")) {
3533 // seek only when the graph node changes
3534 const char *pc = r_reg_get_name (core->dbg->reg, R_REG_NAME_PC);
3535 RRegItem *r = r_reg_get (core->dbg->reg, pc, -1);
3536 ut64 addr = r_reg_get_value (core->dbg->reg, r);
3537 RANode *acur = get_anode (g->curnode);
3538
3539 addr = r_anal_get_bbaddr (core->anal, addr);
3540 char *title = get_title (addr);
3541 if (!acur || strcmp (acur->title, title)) {
3542 r_core_cmd0 (core, "sr PC");
3543 }
3544 free (title);
3545 g->is_instep = false;
3546 }
3547
3548 if (grd->follow_offset) {
3549 if (r_io_is_valid_offset (core->io, core->offset, 0)) {
3550 f = r_anal_get_fcn_in (core->anal, core->offset, 0);
3551 if (!f) {
3552 if (!g->is_dis) {
3553 if (!r_cons_yesno ('y', "\rNo function at 0x%08"PFMT64x". Define it here (Y/n)? ", core->offset)) {
3554 return 0;
3555 }
3556 r_core_cmd0 (core, "af");
3557 }
3558 f = r_anal_get_fcn_in (core->anal, core->offset, 0);
3559 g->need_reload_nodes = true;
3560 }
3561 if (f && fcn && f != *fcn) {
3562 *fcn = f;
3563 check_function_modified (core, *fcn);
3564 g->need_reload_nodes = true;
3565 g->force_update_seek = true;
3566 }
3567 } else {
3568 // TODO: maybe go back to avoid seeking from graph view to an scary place?
3569 r_cons_message ("This is not a valid offset\n");
3570 r_cons_flush ();
3571 }
3572 }
3573
3574 int res = agraph_print (g, grd->fs, core, *fcn);
3575
3576 if (r_config_get_i (core->config, "scr.scrollbar")) {
3577 r_core_print_scrollbar (core);
3578 }
3579
3580 return res;
3581 }
3582
agraph_refresh_oneshot(struct agraph_refresh_data * grd)3583 static void agraph_refresh_oneshot(struct agraph_refresh_data *grd) {
3584 r_core_task_enqueue_oneshot (&grd->core->tasks, (RCoreTaskOneShot) agraph_refresh, grd);
3585 }
3586
agraph_set_need_reload_nodes(struct agraph_refresh_data * grd)3587 static void agraph_set_need_reload_nodes(struct agraph_refresh_data *grd) {
3588 grd->g->need_reload_nodes = true;
3589 }
3590
agraph_toggle_speed(RAGraph * g,RCore * core)3591 static void agraph_toggle_speed(RAGraph *g, RCore *core) {
3592 const int alt = r_config_get_i (core->config, "graph.scroll");
3593 g->movspeed = g->movspeed == DEFAULT_SPEED? alt: DEFAULT_SPEED;
3594 }
3595
agraph_init(RAGraph * g)3596 static void agraph_init(RAGraph *g) {
3597 g->is_callgraph = false;
3598 g->is_instep = false;
3599 g->need_reload_nodes = true;
3600 g->show_node_titles = true;
3601 g->show_node_body = true;
3602 g->force_update_seek = true;
3603 g->graph = r_graph_new ();
3604 g->nodes = sdb_new0 ();
3605 g->edgemode = 2;
3606 g->zoom = ZOOM_DEFAULT;
3607 g->hints = 1;
3608 g->movspeed = DEFAULT_SPEED;
3609 g->db = sdb_new0 ();
3610 r_vector_init (&g->ghits.word_list, sizeof (struct r_agraph_location), NULL, NULL);
3611 }
3612
free_anode(RANode * n)3613 static void free_anode(RANode *n) {
3614 free (n->title);
3615 free (n->body);
3616 free (n);
3617 }
3618
graphNodeMove(RAGraph * g,int dir,int speed)3619 static void graphNodeMove(RAGraph *g, int dir, int speed) {
3620 int delta = (dir == 'k')? -1: 1;
3621 if (dir == 'H') {
3622 return;
3623 }
3624 if (dir == 'h' || dir == 'l') {
3625 // horizontal scroll
3626 if (is_mini (g)) {
3627 discroll = 0;
3628 } else {
3629 int delta = (dir == 'l')? 1: -1;
3630 move_current_node (g, speed * delta, 0);
3631 }
3632 return;
3633 }
3634 RCore *core = NULL;
3635 // vertical scroll
3636 if (is_mini (g)) {
3637 discroll += (delta * speed);
3638 } else if (g->is_dis) {
3639 r_core_cmdf (core, "so %d", (delta * 4) * speed);
3640 } else {
3641 move_current_node (g, 0, delta * speed);
3642 }
3643 }
3644
agraph_free_nodes(const RAGraph * g)3645 static void agraph_free_nodes(const RAGraph *g) {
3646 RListIter *it;
3647 RGraphNode *n;
3648 RANode *a;
3649
3650 graph_foreach_anode (r_graph_get_nodes (g->graph), it, n, a) {
3651 free_anode (a);
3652 }
3653
3654 sdb_free (g->nodes);
3655 }
3656
sdb_set_enc(Sdb * db,const char * key,const char * v,ut32 cas)3657 static void sdb_set_enc(Sdb *db, const char *key, const char *v, ut32 cas) {
3658 char *estr = sdb_encode ((const void *) v, -1);
3659 sdb_set (db, key, estr, cas);
3660 free (estr);
3661 }
3662
agraph_sdb_init(const RAGraph * g)3663 static void agraph_sdb_init(const RAGraph *g) {
3664 sdb_bool_set (g->db, "agraph.is_callgraph", g->is_callgraph, 0);
3665 RCons *cons = r_cons_singleton ();
3666 sdb_set_enc (g->db, "agraph.color_box", cons->context->pal.graph_box, 0);
3667 sdb_set_enc (g->db, "agraph.color_box2", cons->context->pal.graph_box2, 0);
3668 sdb_set_enc (g->db, "agraph.color_box3", cons->context->pal.graph_box3, 0);
3669 sdb_set_enc (g->db, "agraph.color_true", cons->context->pal.graph_true, 0);
3670 sdb_set_enc (g->db, "agraph.color_false", cons->context->pal.graph_false, 0);
3671 }
3672
r_agraph_get_sdb(RAGraph * g)3673 R_API Sdb *r_agraph_get_sdb(RAGraph *g) {
3674 g->need_update_dim = true;
3675 g->need_set_layout = true;
3676 (void)check_changes (g, false, NULL, NULL);
3677 // remove_dummy_nodes (g);
3678 return g->db;
3679 }
3680
r_agraph_print(RAGraph * g)3681 R_API void r_agraph_print(RAGraph *g) {
3682 agraph_print (g, false, NULL, NULL);
3683 if (g->graph->n_nodes > 0) {
3684 r_cons_newline ();
3685 }
3686 }
3687
r_agraph_print_json(RAGraph * g,PJ * pj)3688 R_API void r_agraph_print_json(RAGraph *g, PJ *pj) {
3689 RList *nodes = g->graph->nodes, *neighbours = NULL;
3690 RListIter *it, *itt;
3691 RGraphNode *node = NULL, *neighbour = NULL;
3692 if (!pj) {
3693 return;
3694 }
3695 r_list_foreach (nodes, it, node) {
3696 RANode *anode = (RANode *) node->data;
3697 char *label = strdup (anode->body);
3698 pj_o (pj);
3699 pj_ki (pj, "id", anode->gnode->idx);
3700 pj_ks (pj, "title", anode->title);
3701 pj_ks (pj, "body", label);
3702 pj_k (pj, "out_nodes");
3703 pj_a (pj);
3704 neighbours = anode->gnode->out_nodes;
3705 r_list_foreach (neighbours, itt, neighbour) {
3706 pj_i (pj, neighbour->idx);
3707 }
3708 pj_end (pj);
3709 pj_end (pj);
3710 free (label);
3711 }
3712 }
3713
r_agraph_set_title(RAGraph * g,const char * title)3714 R_API void r_agraph_set_title(RAGraph *g, const char *title) {
3715 free (g->title);
3716 g->title = title? strdup (title): NULL;
3717 sdb_set (g->db, "agraph.title", g->title, 0);
3718 }
3719
r_agraph_add_node(const RAGraph * g,const char * title,const char * body,const char * color)3720 R_API RANode *r_agraph_add_node(const RAGraph *g, const char *title, const char *body, const char *color) {
3721 RANode *res = r_agraph_get_node (g, title);
3722 if (res) {
3723 return res;
3724 }
3725 res = R_NEW0 (RANode);
3726 if (!res) {
3727 return NULL;
3728 }
3729
3730 res->title = title? r_str_trunc_ellipsis (title, 255) : strdup ("");
3731 res->body = body? strdup (body): strdup ("");
3732 res->layer = -1;
3733 res->pos_in_layer = -1;
3734 res->is_dummy = false;
3735 res->is_reversed = false;
3736 res->klass = -1;
3737 res->color = color? strdup (color): NULL;
3738 res->difftype = -1;
3739 res->gnode = r_graph_add_node (g->graph, res);
3740 sdb_num_set (g->nodes, res->title, (ut64) (size_t) res, 0);
3741 if (res->title) {
3742 char *s, *estr, *b;
3743 size_t len;
3744 sdb_array_add (g->db, "agraph.nodes", res->title, 0);
3745 b = strdup (res->body);
3746 len = strlen (b);
3747 if (len > 0 && b[len - 1] == '\n') {
3748 b[len - 1] = '\0';
3749 }
3750 estr = sdb_encode ((const void *) b, -1);
3751 //s = sdb_fmt ("base64:%s", estr);
3752 s = r_str_newf ("base64:%s", estr);
3753 free (estr);
3754 free (b);
3755 sdb_set_owned (g->db, sdb_fmt ("agraph.nodes.%s.body", res->title), s, 0);
3756 }
3757 return res;
3758 }
3759
r_agraph_del_node(const RAGraph * g,const char * title)3760 R_API bool r_agraph_del_node(const RAGraph *g, const char *title) {
3761 char *title_trunc = r_str_trunc_ellipsis (title, 255);
3762 RANode *an, *res = r_agraph_get_node (g, title_trunc);
3763 free (title_trunc);
3764 RGraphNode *gn;
3765 RListIter *it;
3766
3767 if (!res) {
3768 return false;
3769 }
3770 sdb_set (g->nodes, res->title, NULL, 0);
3771 sdb_array_remove (g->db, "agraph.nodes", res->title, 0);
3772 sdb_set (g->db, sdb_fmt ("agraph.nodes.%s", res->title), NULL, 0);
3773 sdb_set (g->db, sdb_fmt ("agraph.nodes.%s.body", res->title), 0, 0);
3774 sdb_set (g->db, sdb_fmt ("agraph.nodes.%s.x", res->title), NULL, 0);
3775 sdb_set (g->db, sdb_fmt ("agraph.nodes.%s.y", res->title), NULL, 0);
3776 sdb_set (g->db, sdb_fmt ("agraph.nodes.%s.w", res->title), NULL, 0);
3777 sdb_set (g->db, sdb_fmt ("agraph.nodes.%s.h", res->title), NULL, 0);
3778 sdb_set (g->db, sdb_fmt ("agraph.nodes.%s.neighbours", res->title), NULL, 0);
3779
3780 const RList *innodes = r_graph_innodes (g->graph, res->gnode);
3781 graph_foreach_anode (innodes, it, gn, an) {
3782 const char *key = sdb_fmt ("agraph.nodes.%s.neighbours", an->title);
3783 sdb_array_remove (g->db, key, res->title, 0);
3784 }
3785
3786 r_graph_del_node (g->graph, res->gnode);
3787 res->gnode = NULL;
3788
3789 free_anode (res);
3790 return true;
3791 }
3792
user_node_cb(struct g_cb * user,const char * k UNUSED,const char * v)3793 static int user_node_cb(struct g_cb *user, const char *k UNUSED, const char *v) {
3794 RANodeCallback cb = user->node_cb;
3795 void *user_data = user->data;
3796 RANode *n = (RANode *) (size_t) sdb_atoi (v);
3797 if (n) {
3798 cb (n, user_data);
3799 }
3800 return 1;
3801 }
3802
user_edge_cb(struct g_cb * user,const char * k UNUSED,const char * v)3803 static int user_edge_cb(struct g_cb *user, const char *k UNUSED, const char *v) {
3804 RAEdgeCallback cb = user->edge_cb;
3805 RAGraph *g = user->graph;
3806 void *user_data = user->data;
3807 RANode *an, *n = (RANode *) (size_t) sdb_atoi (v);
3808 if (!n) {
3809 return 0;
3810 }
3811 const RList *neigh = r_graph_get_neighbours (g->graph, n->gnode);
3812 RListIter *it;
3813 RGraphNode *gn;
3814
3815 graph_foreach_anode (neigh, it, gn, an) {
3816 cb (n, an, user_data);
3817 }
3818 return 1;
3819 }
3820
r_agraph_foreach(RAGraph * g,RANodeCallback cb,void * user)3821 R_API void r_agraph_foreach(RAGraph *g, RANodeCallback cb, void *user) {
3822 struct g_cb u = {
3823 .node_cb = cb,
3824 .data = user
3825 };
3826 sdb_foreach (g->nodes, (SdbForeachCallback) user_node_cb, &u);
3827 }
3828
r_agraph_foreach_edge(RAGraph * g,RAEdgeCallback cb,void * user)3829 R_API void r_agraph_foreach_edge(RAGraph *g, RAEdgeCallback cb, void *user) {
3830 struct g_cb u = {
3831 .graph = g,
3832 .edge_cb = cb,
3833 .data = user
3834 };
3835 sdb_foreach (g->nodes, (SdbForeachCallback) user_edge_cb, &u);
3836 }
3837
r_agraph_get_first_node(const RAGraph * g)3838 R_API RANode *r_agraph_get_first_node(const RAGraph *g) {
3839 const RList *l = r_graph_get_nodes (g->graph);
3840 RGraphNode *rgn = r_list_first (l);
3841 return get_anode (rgn);
3842 }
3843
r_agraph_get_node(const RAGraph * g,const char * title)3844 R_API RANode *r_agraph_get_node(const RAGraph *g, const char *title) {
3845 char *title_trunc = title ? r_str_trunc_ellipsis (title, 255) : NULL;
3846 RANode *node = (RANode *) (size_t) sdb_num_get (g->nodes, title_trunc, NULL);
3847 free (title_trunc);
3848 return node;
3849 }
3850
r_agraph_add_edge(const RAGraph * g,RANode * a,RANode * b)3851 R_API void r_agraph_add_edge(const RAGraph *g, RANode *a, RANode *b) {
3852 r_return_if_fail (g && a && b);
3853 r_graph_add_edge (g->graph, a->gnode, b->gnode);
3854 if (a->title && b->title) {
3855 const char *k = sdb_fmt ("agraph.nodes.%s.neighbours", a->title);
3856 sdb_array_add (g->db, k, b->title, 0);
3857 }
3858 }
3859
r_agraph_add_edge_at(const RAGraph * g,RANode * a,RANode * b,int nth)3860 R_API void r_agraph_add_edge_at(const RAGraph *g, RANode *a, RANode *b, int nth) {
3861 r_return_if_fail (g && a && b);
3862 if (a->title && b->title) {
3863 const char *k = sdb_fmt ("agraph.nodes.%s.neighbours", a->title);
3864 sdb_array_insert (g->db, k, nth, b->title, 0);
3865 }
3866 r_graph_add_edge_at (g->graph, a->gnode, b->gnode, nth);
3867 }
3868
r_agraph_del_edge(const RAGraph * g,RANode * a,RANode * b)3869 R_API void r_agraph_del_edge(const RAGraph *g, RANode *a, RANode *b) {
3870 r_return_if_fail (g && a && b);
3871 if (a->title && b->title) {
3872 const char *k = sdb_fmt ("agraph.nodes.%s.neighbours", a->title);
3873 sdb_array_remove (g->db, k, b->title, 0);
3874 }
3875 r_graph_del_edge (g->graph, a->gnode, b->gnode);
3876 }
3877
r_agraph_reset(RAGraph * g)3878 R_API void r_agraph_reset(RAGraph *g) {
3879 r_return_if_fail (g);
3880 agraph_free_nodes (g);
3881 r_graph_reset (g->graph);
3882 r_agraph_set_title (g, NULL);
3883 sdb_reset (g->db);
3884 if (g->edges) {
3885 r_list_purge (g->edges);
3886 }
3887 g->nodes = sdb_new0 ();
3888 g->update_seek_on = NULL;
3889 g->need_reload_nodes = false;
3890 g->need_set_layout = true;
3891 g->need_update_dim = true;
3892 g->x = g->y = g->w = g->h = 0;
3893 agraph_sdb_init (g);
3894 g->curnode = NULL;
3895 }
3896
r_agraph_free(RAGraph * g)3897 R_API void r_agraph_free(RAGraph *g) {
3898 if (g) {
3899 agraph_free_nodes (g);
3900 r_graph_free (g->graph);
3901 r_list_free (g->edges);
3902 r_agraph_set_title (g, NULL);
3903 sdb_free (g->db);
3904 r_cons_canvas_free (g->can);
3905 free (g);
3906 }
3907 }
3908
r_agraph_new(RConsCanvas * can)3909 R_API RAGraph *r_agraph_new(RConsCanvas *can) {
3910 RAGraph *g = R_NEW0 (RAGraph);
3911 if (!g) {
3912 return NULL;
3913 }
3914 g->can = can;
3915 g->dummy = true;
3916 agraph_init (g);
3917 agraph_sdb_init (g);
3918 return g;
3919 }
3920
visual_offset(RAGraph * g,RCore * core)3921 static void visual_offset(RAGraph *g, RCore *core) {
3922 char buf[256];
3923 int rows;
3924 r_cons_get_size (&rows);
3925 r_cons_gotoxy (0, rows);
3926 r_cons_flush ();
3927 core->cons->line->prompt_type = R_LINE_PROMPT_OFFSET;
3928 r_line_set_hist_callback (core->cons->line, &r_line_hist_offset_up, &r_line_hist_offset_down);
3929 r_line_set_prompt ("[offset]> ");
3930 strcpy (buf, "s ");
3931 if (r_cons_fgets (buf + 2, sizeof (buf) - 2, 0, NULL) > 0) {
3932 if (buf[2] == '.') {
3933 buf[1] = '.';
3934 }
3935 r_core_cmd0 (core, buf);
3936 r_line_set_hist_callback (core->cons->line, &r_line_hist_cmd_up, &r_line_hist_cmd_down);
3937 }
3938 core->cons->line->prompt_type = R_LINE_PROMPT_DEFAULT;
3939 }
3940
goto_asmqjmps(RAGraph * g,RCore * core)3941 static void goto_asmqjmps(RAGraph *g, RCore *core) {
3942 const char *h = "[Fast goto call/jmp]> ";
3943 char obuf[R_CORE_ASMQJMPS_LEN_LETTERS + 1];
3944 int rows, i = 0;
3945 bool cont;
3946
3947 r_cons_get_size (&rows);
3948 r_cons_gotoxy (0, rows);
3949 r_cons_clear_line (0);
3950 r_cons_print (Color_RESET);
3951 r_cons_print (h);
3952 r_cons_flush ();
3953
3954 do {
3955 char ch = r_cons_readchar ();
3956 obuf[i++] = ch;
3957 r_cons_printf ("%c", ch);
3958 cont = isalpha ((ut8) ch) && !islower ((ut8) ch);
3959 } while (i < R_CORE_ASMQJMPS_LEN_LETTERS && cont);
3960 r_cons_flush ();
3961
3962 obuf[i] = '\0';
3963 ut64 addr = r_core_get_asmqjmps (core, obuf);
3964 if (addr != UT64_MAX) {
3965 char *title = get_title (addr);
3966 RANode *addr_node = r_agraph_get_node (g, title);
3967 if (addr_node) {
3968 r_agraph_set_curnode (g, addr_node);
3969 r_core_seek (core, addr, false);
3970 agraph_update_seek (g, addr_node, true);
3971 } else {
3972 r_io_sundo_push (core->io, core->offset, 0);
3973 r_core_seek (core, addr, false);
3974 }
3975 free (title);
3976 }
3977 }
3978
seek_to_node(RANode * n,RCore * core)3979 static void seek_to_node(RANode *n, RCore *core) {
3980 ut64 off = r_anal_get_bbaddr (core->anal, core->offset);
3981 char *title = get_title (off);
3982
3983 if (title && strcmp (title, n->title)) {
3984 char *cmd = r_str_newf ("s %s", n->title);
3985 if (cmd) {
3986 if (*cmd) {
3987 r_core_cmd0 (core, cmd);
3988 }
3989 free (cmd);
3990 }
3991 }
3992 free (title);
3993 }
3994
graph_single_step_in(RCore * core,RAGraph * g)3995 static void graph_single_step_in(RCore *core, RAGraph *g) {
3996 if (r_config_get_i (core->config, "cfg.debug")) {
3997 if (core->print->cur_enabled) {
3998 // dcu 0xaddr
3999 r_core_cmdf (core, "dcu 0x%08"PFMT64x, core->offset + core->print->cur);
4000 core->print->cur_enabled = 0;
4001 } else {
4002 r_core_cmd (core, "ds", 0);
4003 r_core_cmd (core, ".dr*", 0);
4004 }
4005 } else {
4006 r_core_cmd (core, "aes", 0);
4007 r_core_cmd (core, ".ar*", 0);
4008 }
4009 g->is_instep = true;
4010 g->need_reload_nodes = true;
4011 }
4012
graph_single_step_over(RCore * core,RAGraph * g)4013 static void graph_single_step_over(RCore *core, RAGraph *g) {
4014 if (r_config_get_i (core->config, "cfg.debug")) {
4015 if (core->print->cur_enabled) {
4016 r_core_cmd (core, "dcr", 0);
4017 core->print->cur_enabled = 0;
4018 } else {
4019 r_core_cmd (core, "dso", 0);
4020 r_core_cmd (core, ".dr*", 0);
4021 }
4022 } else {
4023 r_core_cmd (core, "aeso", 0);
4024 r_core_cmd (core, ".ar*", 0);
4025 }
4026 g->is_instep = true;
4027 g->need_reload_nodes = true;
4028 }
4029
graph_breakpoint(RCore * core)4030 static void graph_breakpoint(RCore *core) {
4031 r_core_cmd (core, "dbs $$", 0);
4032 }
4033
graph_continue(RCore * core)4034 static void graph_continue(RCore *core) {
4035 r_core_cmd (core, "dc", 0);
4036 }
applyDisMode(RCore * core)4037 static void applyDisMode(RCore *core) {
4038 switch (disMode) {
4039 case 0:
4040 r_config_set (core->config, "asm.pseudo", "false");
4041 r_config_set (core->config, "asm.esil", "false");
4042 break;
4043 case 1:
4044 r_config_set (core->config, "asm.pseudo", "true");
4045 r_config_set (core->config, "asm.esil", "false");
4046 break;
4047 case 2:
4048 r_config_set (core->config, "asm.pseudo", "false");
4049 r_config_set (core->config, "asm.esil", "true");
4050 break;
4051 }
4052 }
4053
rotateColor(RCore * core)4054 static void rotateColor(RCore *core) {
4055 int color = r_config_get_i (core->config, "scr.color");
4056 if (++color > 2) {
4057 color = 0;
4058 }
4059 r_config_set_i (core->config, "scr.color", color);
4060 }
4061
4062 // dupe in visual.c
toggle_bb(RCore * core,ut64 addr)4063 static bool toggle_bb(RCore *core, ut64 addr) {
4064 RAnalFunction *fcn = r_anal_get_fcn_in (core->anal, addr, R_ANAL_FCN_TYPE_NULL);
4065 if (fcn) {
4066 RAnalBlock *bb = r_anal_fcn_bbget_in (core->anal, fcn, addr);
4067 if (bb) {
4068 bb->folded = !bb->folded;
4069 } else {
4070 r_warn_if_reached ();
4071 }
4072 return true;
4073 }
4074 return false;
4075 }
4076
get_graph_string(RCore * core,RAGraph * g)4077 static char *get_graph_string(RCore *core, RAGraph *g) {
4078 int c = r_config_get_i (core->config, "scr.color");
4079 int u = r_config_get_i (core->config, "scr.utf8");
4080 r_config_set_i (core->config, "scr.color", 0);
4081 r_config_set_i (core->config, "scr.utf8", 0);
4082 r_core_visual_graph (core, g, NULL, false);
4083 char *s = strdup (r_cons_get_buffer ());
4084 r_cons_reset ();
4085 r_config_set_i (core->config, "scr.color", c);
4086 r_config_set_i (core->config, "scr.utf8", u);
4087 return s;
4088 }
4089
nextword(RCore * core,RAGraph * g,const char * word)4090 static void nextword(RCore *core, RAGraph *g, const char *word) {
4091 r_return_if_fail (core && core->graph && g && g->can && word);
4092 if (R_STR_ISEMPTY (word)) {
4093 return;
4094 }
4095 RAGraphHits *gh = &g->ghits;
4096 RConsCanvas *can = g->can;
4097 if (gh->word_list.len && gh->old_word && !strcmp (word, gh->old_word)) {
4098 if (gh->word_nth >= gh->word_list.len) {
4099 gh->word_nth = 0;
4100 }
4101
4102 struct r_agraph_location *pos = r_vector_index_ptr (&gh->word_list, gh->word_nth);
4103 gh->word_nth++;
4104 if (pos) {
4105 can->sx = -pos->x + can->w / 2;
4106 can->sy = -pos->y + can->h / 2;
4107 }
4108 return;
4109 } else {
4110 r_vector_clear (&gh->word_list);
4111 }
4112 char *s = get_graph_string (core, g);
4113 r_cons_clear00 ();
4114 r_cons_flush ();
4115 const size_t MAX_COUNT = 4096;
4116 const char *a = NULL;
4117 size_t count = 0;
4118 int x = 0, y = 0;
4119 for (count = 0; count < MAX_COUNT; count++) {
4120 a = r_str_str_xy (s, word, a, &x, &y);
4121 if (!a) {
4122 break;
4123 }
4124 struct r_agraph_location *pos = r_vector_push (&gh->word_list, NULL);
4125 if (pos) {
4126 pos->x = x + g->x;
4127 pos->y = y + g->y;
4128 }
4129 }
4130 free (gh->old_word);
4131 gh->old_word = strdup (word);
4132 free (s);
4133 if (!a && count == 0) {
4134 return;
4135 }
4136 nextword (core, g, word);
4137 }
4138
4139 static const char *help_msg_visual_graph[] = {
4140 ":e cmd.gprompt=agft", "show tinygraph in one side",
4141 "@", "toggle graph.layout between 0 and 1",
4142 "+/-/0", "zoom in/out/default",
4143 ";", "add comment in current basic block",
4144 ". (dot)", "center graph to the current node",
4145 ", (comma)", "toggle graph.few",
4146 "^", "seek to the first bb of the function",
4147 "=", "toggle graph.layout",
4148 ":cmd", "run radare command",
4149 "'", "toggle graph.comments",
4150 "\"", "toggle graph.refs",
4151 "#", "toggle graph.hints",
4152 "/", "highlight text",
4153 "\\", "scroll the graph canvas to the next highlight location",
4154 "|", "set cmd.gprompt",
4155 "_", "enter hud selector",
4156 ">", "show function callgraph (see graph.refs)",
4157 "<", "show program callgraph (see graph.refs)",
4158 "(", "reverse conditional branch of last instruction in bb",
4159 ")", "rotate asm.emu and emu.str",
4160 "Home/End", "go to the top/bottom of the canvas",
4161 "Page-UP/DOWN", "scroll canvas up/down",
4162 "b", "visual browse things",
4163 "c", "toggle graph cursor mode",
4164 "C", "toggle scr.colors",
4165 "d", "rename function",
4166 "D", "toggle the mixed graph+disasm mode",
4167 "e", "rotate graph.edges (show/hide edges)",
4168 "E", "rotate graph.linemode (square/diagonal lines)",
4169 "F", "enter flag selector",
4170 "g", "go/seek to given offset",
4171 "G", "debug trace callgraph (generated with dtc)",
4172 "hjkl/HJKL", "scroll canvas or node depending on graph cursor (uppercase for faster)",
4173 "i", "select input nodes by index",
4174 "I", "select output node by index",
4175 "m/M", "change mouse modes",
4176 "n/N", "next/previous scr.nkey (function/flag..)",
4177 "o([A-Za-z]*)", "follow jmp/call identified by shortcut (like ;[oa])",
4178 "O", "toggle asm.pseudo and asm.esil",
4179 "p/P", "rotate graph modes (normal, display offsets, minigraph, summary)",
4180 "q", "back to Visual mode",
4181 "r", "toggle jmphints/leahints",
4182 "R", "randomize colors",
4183 "s/S", "step / step over",
4184 "tab", "select next node",
4185 "TAB", "select previous node",
4186 "t/f", "follow true/false edges",
4187 "u/U", "undo/redo seek",
4188 "V", "toggle basicblock / call graphs",
4189 "w", "toggle between movements speed 1 and graph.scroll",
4190 "x/X", "jump to xref/ref",
4191 "Y", "toggle tiny graph",
4192 "z", "toggle node folding",
4193 "Z", "toggle basic block folding",
4194 NULL
4195 };
4196
r_core_visual_graph(RCore * core,RAGraph * g,RAnalFunction * _fcn,int is_interactive)4197 R_API int r_core_visual_graph(RCore *core, RAGraph *g, RAnalFunction *_fcn, int is_interactive) {
4198 if (is_interactive && !r_cons_is_interactive ()) {
4199 eprintf ("Interactive graph mode requires scr.interactive=true.\n");
4200 return 0;
4201 }
4202 int o_asmqjmps_letter = core->is_asmqjmps_letter;
4203 int o_vmode = core->vmode;
4204 int exit_graph = false, is_error = false;
4205 int update_seek = false;
4206 struct agraph_refresh_data *grd;
4207 int okey, key;
4208 RAnalFunction *fcn = NULL;
4209 const char *key_s;
4210 RConsCanvas *can, *o_can = NULL;
4211 bool graph_allocated = false;
4212 int movspeed;
4213 int ret, invscroll;
4214 RConfigHold *hc = r_config_hold_new (core->config);
4215 if (!hc) {
4216 return false;
4217 }
4218 r_config_hold (hc, "asm.pseudo", "asm.esil", "asm.cmt.right", NULL);
4219
4220 int h, w = r_cons_get_size (&h);
4221 can = r_cons_canvas_new (w, h);
4222 if (!can) {
4223 w = 80;
4224 h = 25;
4225 can = r_cons_canvas_new (w, h);
4226 if (!can) {
4227 eprintf ("Cannot create RCons.canvas context. Invalid screen "
4228 "size? See scr.columns + scr.rows\n");
4229 r_config_hold_free (hc);
4230 return false;
4231 }
4232 }
4233 can->linemode = r_config_get_i (core->config, "graph.linemode");
4234 can->color = r_config_get_i (core->config, "scr.color");
4235
4236 if (!g) {
4237 graph_allocated = true;
4238 fcn = _fcn? _fcn: r_anal_get_fcn_in (core->anal, core->offset, 0);
4239 if (!fcn) {
4240 r_config_hold_restore (hc);
4241 r_config_hold_free (hc);
4242 r_cons_canvas_free (can);
4243 return false;
4244 }
4245 check_function_modified (core, fcn);
4246 g = r_agraph_new (can);
4247 if (!g) {
4248 r_cons_canvas_free (can);
4249 r_config_hold_restore (hc);
4250 r_config_hold_free (hc);
4251 return false;
4252 }
4253 g->is_tiny = is_interactive == 2;
4254 g->layout = r_config_get_i (core->config, "graph.layout");
4255 g->dummy = r_config_get_i (core->config, "graph.dummy");
4256 g->show_node_titles = r_config_get_i (core->config, "graph.ntitles");
4257 } else {
4258 o_can = g->can;
4259 }
4260 g->can = can;
4261 g->movspeed = r_config_get_i (core->config, "graph.scroll");
4262 g->show_node_titles = r_config_get_i (core->config, "graph.ntitles");
4263 g->show_node_body = r_config_get_i (core->config, "graph.body");
4264 g->show_node_bubble = r_config_get_i (core->config, "graph.bubble");
4265 g->on_curnode_change = (RANodeCallback) seek_to_node;
4266 g->on_curnode_change_data = core;
4267 g->edgemode = r_config_get_i (core->config, "graph.edges");
4268 g->hints = r_config_get_i (core->config, "graph.hints");
4269 g->is_interactive = is_interactive;
4270 bool asm_comments = r_config_get_i (core->config, "asm.comments");
4271 r_config_set (core->config, "asm.comments",
4272 r_str_bool (r_config_get_i (core->config, "graph.comments")));
4273
4274 /* we want letters as shortcuts for call/jmps */
4275 core->is_asmqjmps_letter = true;
4276 core->vmode = true;
4277
4278 grd = R_NEW0 (struct agraph_refresh_data);
4279 if (!grd) {
4280 r_cons_canvas_free (can);
4281 r_config_hold_restore (hc);
4282 r_config_hold_free (hc);
4283 r_agraph_free (g);
4284 return false;
4285 }
4286 grd->g = g;
4287 grd->fs = is_interactive == 1;
4288 grd->core = core;
4289 grd->follow_offset = _fcn == NULL;
4290 grd->fcn = fcn != NULL? &fcn: NULL;
4291 ret = agraph_refresh (grd);
4292 if (!ret || is_interactive != 1) {
4293 r_cons_newline ();
4294 exit_graph = true;
4295 is_error = !ret;
4296 }
4297 get_bbupdate (g, core, fcn);
4298
4299 core->cons->event_resize = NULL; // avoid running old event with new data
4300 core->cons->event_data = grd;
4301 core->cons->event_resize = (RConsEvent) agraph_refresh_oneshot;
4302
4303 r_cons_break_push (NULL, NULL);
4304
4305 while (!exit_graph && !is_error && !r_cons_is_breaked ()) {
4306 w = r_cons_get_size (&h);
4307 invscroll = r_config_get_i (core->config, "graph.invscroll");
4308 ret = agraph_refresh (grd);
4309
4310 if (!ret) {
4311 is_error = true;
4312 break;
4313 }
4314 showcursor (core, false);
4315
4316 // r_core_graph_inputhandle()
4317 okey = r_cons_readchar ();
4318 key = r_cons_arrow_to_hjkl (okey);
4319
4320 if (core->cons->mouse_event) {
4321 movspeed = r_config_get_i (core->config, "scr.wheel.speed");
4322 switch (key) {
4323 case 'j':
4324 case 'k':
4325 switch (mousemode) {
4326 case 0: break;
4327 case 1: key = key == 'k'? 'h': 'l'; break;
4328 case 2: key = key == 'k'? 'J': 'K'; break;
4329 case 3: key = key == 'k'? 'L': 'H'; break;
4330 }
4331 break;
4332 }
4333 } else {
4334 movspeed = g->movspeed;
4335 }
4336 const char *cmd;
4337 switch (key) {
4338 case '-':
4339 agraph_set_zoom (g, g->zoom - ZOOM_STEP);
4340 g->force_update_seek = true;
4341 break;
4342 case '+':
4343 agraph_set_zoom (g, g->zoom + ZOOM_STEP);
4344 g->force_update_seek = true;
4345 break;
4346 case '0':
4347 agraph_set_zoom (g, ZOOM_DEFAULT);
4348 agraph_update_seek (g, get_anode (g->curnode), true);
4349 // update scroll (with minor shift)
4350 break;
4351 // Those hardcoded keys are useful only for aegi, should add subcommand of ag to set key actions
4352 case '1':
4353 r_core_cmd0 (core, "so;.aeg*");
4354 break;
4355 case '2':
4356 r_core_cmd0 (core, "so -1;.aeg*");
4357 break;
4358 case '=':
4359 { // TODO: edit
4360 showcursor (core, true);
4361 const char *cmd = r_config_get (core->config, "cmd.gprompt");
4362 r_line_set_prompt ("cmd.gprompt> ");
4363 core->cons->line->contents = strdup (cmd);
4364 const char *buf = r_line_readline ();
4365 core->cons->line->contents = NULL;
4366 r_config_set (core->config, "cmd.gprompt", buf);
4367 showcursor (core, false);
4368 }
4369 break;
4370 case '|':
4371 {
4372 int e = r_config_get_i (core->config, "graph.layout");
4373 if (++e > 1) {
4374 e = 0;
4375 }
4376 r_config_set_i (core->config, "graph.layout", e);
4377 g->layout = r_config_get_i (core->config, "graph.layout");
4378 g->need_update_dim = true;
4379 g->need_set_layout = true;
4380 }
4381 discroll = 0;
4382 agraph_update_seek (g, get_anode (g->curnode), true);
4383 break;
4384 case 'e':
4385 {
4386 int e = r_config_get_i (core->config, "graph.edges");
4387 e++;
4388 if (e > 2) {
4389 e = 0;
4390 }
4391 r_config_set_i (core->config, "graph.edges", e);
4392 g->edgemode = e;
4393 g->need_update_dim = true;
4394 get_bbupdate (g, core, fcn);
4395 }
4396 break;
4397 case '\\':
4398 nextword (core, g, r_config_get (core->config, "scr.highlight"));
4399 break;
4400 case 'b':
4401 r_core_visual_browse (core, "");
4402 break;
4403 case 'E':
4404 {
4405 int e = r_config_get_i (core->config, "graph.linemode");
4406 e--;
4407 if (e < 0) {
4408 e = 1;
4409 }
4410 r_config_set_i (core->config, "graph.linemode", e);
4411 g->can->linemode = e;
4412 get_bbupdate (g, core, fcn);
4413 }
4414 break;
4415 case 13:
4416 agraph_update_seek (g, get_anode (g->curnode), true);
4417 update_seek = true;
4418 exit_graph = true;
4419 break;
4420 case '>':
4421 if (fcn && r_cons_yesno ('y', "Compute function callgraph? (Y/n)")) {
4422 r_core_cmd0 (core, "ag-;.agc* @$FB;.axfg @$FB;aggi");
4423 }
4424 break;
4425 case '<':
4426 // r_core_visual_refs (core, true, false);
4427 if (fcn) {
4428 r_core_cmd0 (core, "ag-;.axtg $FB;aggi");
4429 }
4430 break;
4431 case 'G':
4432 r_core_cmd0 (core, "ag-;.dtg*;aggi");
4433 break;
4434 case 'V':
4435 if (fcn) {
4436 agraph_toggle_callgraph (g);
4437 }
4438 break;
4439 case 'Z':
4440 if (okey == 27) { // shift-tab
4441 agraph_prev_node (g);
4442 } else {
4443 RANode *n = get_anode (g->curnode);
4444 if (n) {
4445 ut64 addr = r_num_get (NULL, n->title);
4446 toggle_bb (core, addr);
4447 g->need_reload_nodes = true;
4448 }
4449 }
4450 break;
4451 case 's':
4452 if (!fcn) {
4453 break;
4454 }
4455 key_s = r_config_get (core->config, "key.s");
4456 if (key_s && *key_s) {
4457 r_core_cmd0 (core, key_s);
4458 } else {
4459 graph_single_step_in (core, g);
4460 }
4461 discroll = 0;
4462 agraph_update_seek (g, get_anode (g->curnode), true);
4463 break;
4464 case 'S':
4465 if (fcn) {
4466 graph_single_step_over (core, g);
4467 }
4468 break;
4469 case 'x':
4470 case 'X':
4471 {
4472 if (!fcn) {
4473 break;
4474 }
4475 ut64 old_off = core->offset;
4476 ut64 off = r_anal_get_bbaddr (core->anal, core->offset);
4477 r_core_seek (core, off, false);
4478 if ((key == 'x' && !r_core_visual_refs (core, true, true)) ||
4479 (key == 'X' && !r_core_visual_refs (core, false, true))) {
4480 r_core_seek (core, old_off, false);
4481 }
4482 break;
4483 }
4484 case '@': // tab
4485 r_config_set_i (core->config, "graph.layout",
4486 r_config_get_i (core->config, "graph.layout")? 0: 1);
4487 discroll = 0;
4488 g->layout = r_config_get_i (core->config, "graph.layout");
4489 g->need_reload_nodes = true;
4490 agraph_update_seek (g, get_anode (g->curnode), true);
4491 break;
4492 case 9: // tab
4493 agraph_next_node (g);
4494 discroll = 0;
4495 break;
4496 case '?':
4497 r_cons_clear00 ();
4498 RStrBuf *rsb = r_strbuf_new ("");
4499 r_core_visual_append_help (rsb, "Visual Graph Mode (VV) Help", help_msg_visual_graph);
4500 ret = r_cons_less_str (r_strbuf_get (rsb), "?");
4501 r_strbuf_free (rsb);
4502 break;
4503 case '"':
4504 r_config_toggle (core->config, "graph.refs");
4505 break;
4506 case '#':
4507 if (g->mode == R_AGRAPH_MODE_COMMENTS) {
4508 g->mode = R_AGRAPH_MODE_NORMAL;
4509 } else {
4510 g->mode = R_AGRAPH_MODE_COMMENTS;
4511 }
4512 g->need_reload_nodes = true;
4513 discroll = 0;
4514 agraph_update_seek (g, get_anode (g->curnode), true);
4515 // r_config_toggle (core->config, "graph.hints");
4516 break;
4517 case 'p':
4518 g->mode = next_mode (g->mode);
4519 g->need_reload_nodes = true;
4520 agraph_update_seek (g, get_anode (g->curnode), true);
4521 break;
4522 case 'P':
4523 if (!fcn) {
4524 break;
4525 }
4526 g->mode = prev_mode (g->mode);
4527 g->need_reload_nodes = true;
4528 agraph_update_seek (g, get_anode (g->curnode), true);
4529 break;
4530 case 'o':
4531 goto_asmqjmps (g, core);
4532 break;
4533 case 'g':
4534 showcursor (core, true);
4535 visual_offset (g, core);
4536 showcursor (core, false);
4537 break;
4538 case 'O':
4539 if (!fcn) {
4540 break;
4541 }
4542 disMode = (disMode + 1) % 3;
4543 applyDisMode (core);
4544 g->need_reload_nodes = true;
4545 get_bbupdate (g, core, fcn);
4546 break;
4547 case 'u':
4548 {
4549 if (!fcn) {
4550 break;
4551 }
4552 RIOUndos *undo = r_io_sundo (core->io, core->offset);
4553 if (undo) {
4554 r_core_seek (core, undo->off, false);
4555 } else {
4556 eprintf ("Cannot undo\n");
4557 }
4558 if (r_config_get_i (core->config, "graph.few")) {
4559 g->need_reload_nodes = true;
4560 }
4561 break;
4562 }
4563 case 'U':
4564 {
4565 if (!fcn) {
4566 break;
4567 }
4568 RIOUndos *undo = r_io_sundo_redo (core->io);
4569 if (undo) {
4570 r_core_seek (core, undo->off, false);
4571 } else {
4572 eprintf ("Cannot redo\n");
4573 }
4574 break;
4575 }
4576 case 'r':
4577 if (fcn) {
4578 g->layout = r_config_get_i (core->config, "graph.layout");
4579 g->need_reload_nodes = true;
4580 }
4581 // TODO: toggle shortcut hotkeys
4582 if (r_config_get_i (core->config, "asm.hint.call")) {
4583 r_core_cmd0 (core, "e!asm.hint.call");
4584 r_core_cmd0 (core, "e!asm.hint.jmp");
4585 } else if (r_config_get_i (core->config, "asm.hint.jmp")) {
4586 r_core_cmd0 (core, "e!asm.hint.jmp");
4587 r_core_cmd0 (core, "e!asm.hint.lea");
4588 } else if (r_config_get_i (core->config, "asm.hint.lea")) {
4589 r_core_cmd0 (core, "e!asm.hint.lea");
4590 r_core_cmd0 (core, "e!asm.hint.call");
4591 }
4592 break;
4593 case 'R':
4594 if (r_config_get_i (core->config, "scr.randpal")) {
4595 r_core_cmd0 (core, "ecr");
4596 } else {
4597 r_core_cmd0 (core, "ecn");
4598 }
4599 if (!fcn) {
4600 break;
4601 }
4602 g->edgemode = r_config_get_i (core->config, "graph.edges");
4603 get_bbupdate (g, core, fcn);
4604 break;
4605 case '$':
4606 r_core_cmd (core, "dr PC=$$", 0);
4607 r_core_cmd (core, "sr PC", 0);
4608 g->need_reload_nodes = true;
4609 break;
4610 case '!':
4611 r_core_panels_root (core, core->panels_root);
4612 break;
4613 case '\'':
4614 if (fcn) {
4615 r_config_toggle (core->config, "graph.comments");
4616 g->need_reload_nodes = true;
4617 }
4618 break;
4619 case ';':
4620 if (fcn) {
4621 showcursor (core, true);
4622 char buf[256];
4623 r_line_set_prompt ("[comment]> ");
4624 if (r_cons_fgets (buf, sizeof (buf), 0, NULL) > 0) {
4625 r_core_cmdf (core, "\"CC %s\"", buf);
4626 }
4627 g->need_reload_nodes = true;
4628 showcursor (core, false);
4629 }
4630 break;
4631 case 'C':
4632 rotateColor (core);
4633 break;
4634 case 'm':
4635 mousemode++;
4636 if (!mousemodes[mousemode]) {
4637 mousemode = 0;
4638 }
4639 break;
4640 case 'M':
4641 mousemode--;
4642 if (mousemode < 0) {
4643 mousemode = 3;
4644 }
4645 break;
4646 case '(':
4647 if (fcn) {
4648 r_core_cmd0 (core, "wao recj@B:-1");
4649 g->need_reload_nodes = true;
4650 }
4651 break;
4652 case ')':
4653 if (fcn) {
4654 rotateAsmemu (core);
4655 g->need_reload_nodes = true;
4656 }
4657 break;
4658 case 'd':
4659 {
4660 showcursor (core, true);
4661 r_core_visual_define (core, "", 0);
4662 get_bbupdate (g, core, fcn);
4663 showcursor (core, false);
4664 }
4665 break;
4666 case 'D':
4667 g->is_dis = !g->is_dis;
4668 break;
4669 case 'n':
4670 r_core_seek_next (core, r_config_get (core->config, "scr.nkey"));
4671 break;
4672 case 'N':
4673 r_core_seek_previous (core, r_config_get (core->config, "scr.nkey"));
4674 break;
4675 case 'Y':
4676 agraph_toggle_tiny (g);
4677 agraph_update_seek (g, get_anode (g->curnode), true);
4678 break;
4679 case 'z':
4680 agraph_toggle_mini (g);
4681 discroll = 0;
4682 agraph_update_seek (g, get_anode (g->curnode), true);
4683 break;
4684 case 'v':
4685 r_core_visual_anal (core, NULL);
4686 break;
4687 case 'J':
4688 // copypaste from 'j'
4689 if (graphCursor) {
4690 int speed = (okey == 27)? PAGEKEY_SPEED: movspeed;
4691 graphNodeMove (g, 'j', speed * 2);
4692 } else {
4693 can->sy -= (5*movspeed) * (invscroll? -1: 1);
4694 }
4695 break;
4696 case 'K':
4697 if (graphCursor) {
4698 int speed = (okey == 27)? PAGEKEY_SPEED: movspeed;
4699 graphNodeMove (g, 'k', speed * 2);
4700 } else {
4701 can->sy += (5*movspeed) * (invscroll? -1: 1);
4702 }
4703 break;
4704 case 'H':
4705 if (graphCursor) {
4706 // move node canvas faster
4707 graphNodeMove (g, 'h', movspeed * 2);
4708 } else {
4709 // scroll canvas faster
4710 if (okey == 27) {
4711 // handle home key
4712 const RGraphNode *gn = find_near_of (g, NULL, true);
4713 g->update_seek_on = get_anode (gn);
4714 } else {
4715 can->sx += (5 * movspeed) * (invscroll? -1: 1);
4716 }
4717 }
4718 break;
4719 case 'L':
4720 if (graphCursor) {
4721 graphNodeMove (g, 'l', movspeed * 2);
4722 } else {
4723 can->sx -= (5 * movspeed) * (invscroll? -1: 1);
4724 }
4725 break;
4726 case 'c':
4727 graphCursor = !graphCursor;
4728 break;
4729 case 'j':
4730 if (g->is_dis) {
4731 r_core_cmd0 (core, "so 1");
4732 } else {
4733 if (graphCursor) {
4734 int speed = (okey == 27)? PAGEKEY_SPEED: movspeed;
4735 graphNodeMove (g, 'j', speed);
4736 } else {
4737 // scroll canvas
4738 can->sy -= movspeed * (invscroll? -1: 1);
4739 }
4740 }
4741 break;
4742 case 'k':
4743 if (g->is_dis) {
4744 r_core_cmd0 (core, "so -1");
4745 } else {
4746 if (graphCursor) {
4747 int speed = (okey == 27)? PAGEKEY_SPEED: movspeed;
4748 graphNodeMove (g, 'k', speed);
4749 } else {
4750 // scroll canvas
4751 can->sy += movspeed * (invscroll? -1: 1);
4752 }
4753 }
4754 break;
4755 case 'l':
4756 if (graphCursor) {
4757 int speed = (okey == 27)? PAGEKEY_SPEED: movspeed;
4758 graphNodeMove (g, 'l', speed);
4759 } else {
4760 can->sx -= movspeed * (invscroll? -1: 1);
4761 }
4762 break;
4763 case 'h':
4764 if (graphCursor) {
4765 int speed = (okey == 27)? PAGEKEY_SPEED: movspeed;
4766 graphNodeMove (g, 'h', speed);
4767 } else {
4768 can->sx += movspeed * (invscroll? -1: 1);
4769 }
4770 break;
4771 case '^':
4772 {
4773 RAnalFunction *fcn = r_anal_get_fcn_in (core->anal, core->offset, 0);
4774 if (fcn) {
4775 r_core_seek (core, fcn->addr, false);
4776 }
4777 }
4778 agraph_update_seek (g, get_anode (g->curnode), true);
4779 break;
4780 case ',':
4781 r_config_toggle (core->config, "graph.few");
4782 g->need_reload_nodes = true;
4783 agraph_update_seek (g, get_anode (g->curnode), true);
4784 break;
4785 case '.':
4786 discroll = 0;
4787 agraph_update_seek (g, get_anode (g->curnode), true);
4788 break;
4789 case 'i':
4790 agraph_follow_innodes (g, true);
4791 if (r_config_get_i (core->config, "graph.few")) {
4792 g->need_reload_nodes = true;
4793 }
4794 break;
4795 case 'I':
4796 agraph_follow_innodes (g, false);
4797 if (r_config_get_i (core->config, "graph.few")) {
4798 g->need_reload_nodes = true;
4799 }
4800 break;
4801 case 't':
4802 agraph_follow_true (g);
4803 if (r_config_get_i (core->config, "graph.few")) {
4804 g->need_reload_nodes = true;
4805 }
4806 break;
4807 case 'T':
4808 // XXX WIP agraph_merge_child (g, 0);
4809 break;
4810 case 'f':
4811 agraph_follow_false (g);
4812 if (r_config_get_i (core->config, "graph.few")) {
4813 g->need_reload_nodes = true;
4814 }
4815 break;
4816 case 'F':
4817 if (okey == 27) {
4818 // handle end key
4819 const RGraphNode *gn = find_near_of (g, NULL, false);
4820 g->update_seek_on = get_anode (gn);
4821 } else {
4822 // agraph_merge_child (g, 1);
4823 r_core_visual_trackflags (core);
4824 }
4825 break;
4826 case '/':
4827 showcursor (core, true);
4828 r_core_cmd0 (core, "?i highlight;e scr.highlight=`yp`");
4829 showcursor (core, false);
4830 break;
4831 case ':':
4832 core->cons->event_resize = (RConsEvent)agraph_set_need_reload_nodes;
4833 r_core_visual_prompt_input (core);
4834 core->cons->event_resize = (RConsEvent)agraph_refresh_oneshot;
4835 if (!g) {
4836 g->need_reload_nodes = true; // maybe too slow and unnecessary sometimes? better be safe and reload
4837 get_bbupdate (g, core, fcn);
4838 }
4839 break;
4840 case 'w':
4841 agraph_toggle_speed (g, core);
4842 break;
4843 case '_':
4844 r_core_visual_hudstuff (core);
4845 break;
4846 case R_CONS_KEY_F1:
4847 cmd = r_config_get (core->config, "key.f1");
4848 if (cmd && *cmd) {
4849 (void) r_core_cmd0 (core, cmd);
4850 }
4851 break;
4852 case R_CONS_KEY_F2:
4853 cmd = r_config_get (core->config, "key.f2");
4854 if (cmd && *cmd) {
4855 (void) r_core_cmd0 (core, cmd);
4856 } else {
4857 graph_breakpoint (core);
4858 }
4859 break;
4860 case R_CONS_KEY_F3:
4861 cmd = r_config_get (core->config, "key.f3");
4862 if (cmd && *cmd) {
4863 (void) r_core_cmd0 (core, cmd);
4864 }
4865 break;
4866 case R_CONS_KEY_F4:
4867 cmd = r_config_get (core->config, "key.f4");
4868 if (cmd && *cmd) {
4869 (void) r_core_cmd0 (core, cmd);
4870 }
4871 break;
4872 case R_CONS_KEY_F5:
4873 cmd = r_config_get (core->config, "key.f5");
4874 if (cmd && *cmd) {
4875 (void)r_core_cmd0 (core, cmd);
4876 }
4877 break;
4878 case R_CONS_KEY_F6:
4879 cmd = r_config_get (core->config, "key.f6");
4880 if (cmd && *cmd) {
4881 (void)r_core_cmd0 (core, cmd);
4882 }
4883 break;
4884 case R_CONS_KEY_F7:
4885 cmd = r_config_get (core->config, "key.f7");
4886 if (cmd && *cmd) {
4887 (void)r_core_cmd0 (core, cmd);
4888 } else {
4889 graph_single_step_in (core, g);
4890 }
4891 break;
4892 case R_CONS_KEY_F8:
4893 cmd = r_config_get (core->config, "key.f8");
4894 if (cmd && *cmd) {
4895 (void)r_core_cmd0 (core, cmd);
4896 } else {
4897 graph_single_step_over (core, g);
4898 }
4899 break;
4900 case R_CONS_KEY_F9:
4901 cmd = r_config_get (core->config, "key.f9");
4902 if (cmd && *cmd) {
4903 (void)r_core_cmd0 (core, cmd);
4904 } else {
4905 graph_continue (core);
4906 }
4907 break;
4908 case R_CONS_KEY_F10:
4909 cmd = r_config_get (core->config, "key.f10");
4910 if (cmd && *cmd) {
4911 (void)r_core_cmd0 (core, cmd);
4912 }
4913 break;
4914 case R_CONS_KEY_F11:
4915 cmd = r_config_get (core->config, "key.f11");
4916 if (cmd && *cmd) {
4917 (void)r_core_cmd0 (core, cmd);
4918 }
4919 break;
4920 case R_CONS_KEY_F12:
4921 cmd = r_config_get (core->config, "key.f12");
4922 if (cmd && *cmd) {
4923 (void)r_core_cmd0 (core, cmd);
4924 }
4925 break;
4926 case -1: // EOF
4927 case ' ':
4928 case 'Q':
4929 case 'q':
4930 if (g->is_callgraph) {
4931 agraph_toggle_callgraph (g);
4932 } else {
4933 exit_graph = true;
4934 }
4935 break;
4936 case 27: // ESC
4937 if (r_cons_readchar () == 91) {
4938 if (r_cons_readchar () == 90) {
4939 agraph_prev_node (g);
4940 }
4941 }
4942 break;
4943 default:
4944 break;
4945 }
4946 }
4947 r_vector_fini (&g->ghits.word_list);
4948 r_cons_break_pop ();
4949 r_config_set (core->config, "asm.comments", r_str_bool (asm_comments));
4950 core->cons->event_resize = NULL;
4951 core->cons->event_data = NULL;
4952 core->vmode = o_vmode;
4953 core->is_asmqjmps_letter = o_asmqjmps_letter;
4954 core->keep_asmqjmps = false;
4955
4956 free (grd);
4957 if (graph_allocated) {
4958 r_agraph_free (g);
4959 } else {
4960 g->can = o_can;
4961 }
4962 r_config_hold_restore (hc);
4963 r_config_hold_free (hc);
4964 if (update_seek) {
4965 return -1;
4966 }
4967 return !is_error;
4968 }
4969
4970 /**
4971 * @brief Create RAGraph from generic RGraph with RGraphNodeInfo as node data
4972 *
4973 * @param graph <RGraphNodeInfo>
4974 * @return RAGraph* NULL if failure
4975 */
create_agraph_from_graph(const RGraph * graph)4976 R_API RAGraph *create_agraph_from_graph(const RGraph/*<RGraphNodeInfo>*/ *graph) {
4977 r_return_val_if_fail (graph, NULL);
4978
4979 RAGraph *result_agraph = r_agraph_new (r_cons_canvas_new (1, 1));
4980 if (!result_agraph) {
4981 return NULL;
4982 }
4983 result_agraph->need_reload_nodes = false;
4984 // Cache lookup to build edges
4985 HtPPOptions pointer_options = { 0 };
4986 HtPP /*<RGraphNode *node, RANode *anode>*/ *hashmap = ht_pp_new_opt (&pointer_options);
4987
4988 if (!hashmap) {
4989 r_agraph_free (result_agraph);
4990 return NULL;
4991 }
4992 // List of the new RANodes
4993 RListIter *iter;
4994 RGraphNode *node;
4995 // Traverse the list, create new ANode for each Node
4996 r_list_foreach (graph->nodes, iter, node) {
4997 RGraphNodeInfo *info = node->data;
4998 RANode *a_node = r_agraph_add_node (result_agraph, info->title, info->body, NULL);
4999 if (!a_node) {
5000 goto failure;
5001 }
5002 ht_pp_insert (hashmap, node, a_node);
5003 }
5004
5005 // Traverse the nodes again, now build up the edges
5006 r_list_foreach (graph->nodes, iter, node) {
5007 RANode *a_node = ht_pp_find (hashmap, node, NULL);
5008 if (!a_node) {
5009 goto failure; // shouldn't happen in correct graph state
5010 }
5011
5012 RListIter *neighbour_iter;
5013 RGraphNode *neighbour;
5014 r_list_foreach (node->in_nodes, neighbour_iter, neighbour) {
5015 RANode *a_neighbour = ht_pp_find (hashmap, neighbour, NULL);
5016 if (!a_neighbour) {
5017 goto failure;
5018 }
5019 r_agraph_add_edge (result_agraph, a_neighbour, a_node);
5020 }
5021 }
5022
5023 ht_pp_free (hashmap);
5024 return result_agraph;
5025 failure:
5026 ht_pp_free (hashmap);
5027 r_agraph_free (result_agraph);
5028 return NULL;
5029 }
5030