-
Notifications
You must be signed in to change notification settings - Fork 0
/
draw.c
192 lines (182 loc) · 8.37 KB
/
draw.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
/* draw.c
* Written by Daniel Kudrow, 04/30/12
* Last updated 05/17/12
*
* visual representation of abstrat syntax tree
* this file contains methods that create visual representations of the AST
* and CFG
*/
#include <stdio.h>
#include "cfg.h"
/* ast.h is included in cfg.h so it is not explicitly included here */
/* if a node has a label, return it as a string */
#define AST_LABEL(host) (host->label?host->label:"")
#define CFG_LABEL(host) (host->node->label?host->node->label:"")
/* traverse an AST and output GraphViz dot code for each node */
void ast_draw_node(ast_node* host, int parent, FILE* out) {
if (!host) return; /* return at list terminators */
static int node_count = 0; /* global node count */
int current = node_count++; /* id of current node */
switch (host->tag) {
case _prog: /* visit program node */
fprintf(out, "%i [label=\"Program\"];\n", current);
ast_draw_node(host->children[DECL_LIST_HEAD], current, out);
ast_draw_node(host->children[PROC_LIST_HEAD], current, out);
break;
case _decl: /* visit declaration node */
fprintf(out, "%i [label=\"Declaration\\n'%s'\"];\n", current, host->name);
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[NEXT_DECL], parent, out);
break;
case _proc: /* visit process node */
fprintf(out, "%i [label=Process];\n", current);
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[BLOCK], current, out);
ast_draw_node(host->children[NEXT_PROC], parent, out);
break;
case _block: /* visit block node */
ast_draw_node(host->children[STAT_LIST_HEAD], parent, out);
break;
case _assign_stat: /* visit assignment statement node */
fprintf(out, "%i [label=\"Assign\\nlabel: %s\"];\n", current, AST_LABEL(host), host->name);
fprintf(out, "%i -> %i;\n", parent, current);
fprintf(out, "%i [label=\"'%s'\"];\n", node_count, host->name);
fprintf(out, "%i -> %i;\n", current, node_count++);
ast_draw_node(host->children[EXPR], current, out);
ast_draw_node(host->children[NEXT_STAT], parent, out);
break;
case _skip_stat: /* visit skip statement node */
fprintf(out, "%i [label=\"Skip\\nlabel: %s\"];\n", current, AST_LABEL(host));
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[NEXT_STAT], parent, out);
break;
case _if_then_stat: /* visit if-then statement node */
fprintf(out, "%i [label=\"If-Then\\nlabel: %s\"];\n", current, AST_LABEL(host));
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[EXPR], current, out);
ast_draw_node(host->children[BLOCK1], current, out);
ast_draw_node(host->children[NEXT_STAT], current, out);
break;
case _if_else_stat: /* visit if-then-else statement node */
fprintf(out, "%i [label=\"If-Then\\nlabel: %s\"];\n", current, AST_LABEL(host));
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[EXPR], current, out);
ast_draw_node(host->children[BLOCK1], current, out);
ast_draw_node(host->children[BLOCK2], current, out);
ast_draw_node(host->children[NEXT_STAT], parent, out);
break;
case _while_stat: /* visit while statement node */
fprintf(out, "%i [label=\"While\\nlabel: %s\"];\n", current, AST_LABEL(host));
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[EXPR], current, out);
ast_draw_node(host->children[BLOCK1], current, out);
ast_draw_node(host->children[NEXT_STAT], parent, out);
break;
case _await_stat: /* visit await statement node */
fprintf(out, "%i [label=\"Await\\nlabel: %s\"];\n", current, AST_LABEL(host));
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[EXPR], current, out);
ast_draw_node(host->children[NEXT_STAT], parent, out);
break;
case _id_expr: /* visit id expression node */
fprintf(out, "%i [label=ID];\n", current);
fprintf(out, "%i -> %i;\n", parent, current);
fprintf(out, "%i [label=\"'%s'\"];\n", node_count, host->name);
fprintf(out, "%i -> %i;\n", current, node_count++);
break;
case _lit_expr: /* visit literal expression node */
fprintf(out, "%i [label=Literal];\n", current);
fprintf(out, "%i -> %i;\n", parent, current);
fprintf(out, "%i [label=%i];\n", node_count, host->val);
fprintf(out, "%i -> %i;\n", current, node_count++);
break;
case _not_expr: /* visit not expression node */
fprintf(out, "%i [label=Not];\n", current);
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[EXPR1], current, out);
break;
case _and_expr: /* visit and expression node */
fprintf(out, "%i [label=And];\n", current);
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[EXPR1], current, out);
ast_draw_node(host->children[EXPR2], current, out);
break;
case _or_expr: /* visit or expression node */
fprintf(out, "%i [label=Or];\n", current);
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[EXPR1], current, out);
ast_draw_node(host->children[EXPR2], current, out);
break;
case _eq_expr: /* visit equality expression node */
fprintf(out, "%i [label=Equals];\n", current);
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[EXPR1], current, out);
ast_draw_node(host->children[EXPR2], current, out);
break;
case _impl_expr: /* visit implication expression node */
fprintf(out, "%i [label=Implies];\n", current);
fprintf(out, "%i -> %i;\n", parent, current);
ast_draw_node(host->children[EXPR1], current, out);
ast_draw_node(host->children[EXPR2], current, out);
break;
}
}
/* initiate traversal of AST */
void ast_draw_tree(ast_node* tree, FILE* out) {
fprintf(out, "digraph {\n");
ast_draw_node(tree, 0, out);
fprintf(out, "}\n");
}
/* output string representation of AST statement node */
void cfg_to_string(cfg_node* host, FILE* out) {
switch(host->node->tag) {
case _assign_stat:
fprintf(out, "\"ASSIGN\\nlabel: %s\\npc: %i", CFG_LABEL(host), host->node->id);
break;
case _skip_stat:
fprintf(out, "\"SKIP\\nlabel: %s\\npc: %i", CFG_LABEL(host), host->node->id);
break;
case _if_then_stat:
fprintf(out, "\"IF-THEN\\nlabel: %s\\npc: %i", CFG_LABEL(host), host->node->id);
break;
case _if_else_stat:
fprintf(out, "\"IF-ELSE\\nlabel: %s\\npc: %i", CFG_LABEL(host), host->node->id);
break;
case _while_stat:
fprintf(out, "\"WHILE\\nlabel: %s\\npc: %i", CFG_LABEL(host), host->node->id);
break;
case _await_stat:
fprintf(out, "\"AWAIT\\nlabel: %s\\npc: %i", CFG_LABEL(host), host->node->id);
break;
}
}
/* draw CFG node and descend into succesors */
void cfg_draw_node(cfg_node* host, FILE* out, int proc, int parent) {
if (!host) return;
fprintf(out, "%i%i [label=", proc, host->node->id);
cfg_to_string(host, out);
fprintf(out, "\"];\n");
if (parent >= 0) /* root node has no parent */
fprintf(out, "%i%i -> %i%i;\n", proc, parent, proc, host->node->id);
/* the following tests prevent cfg_draw_node from moving backwards */
/* through the control flow */
if (host->succ[0] && host->node->id >= host->succ[0]->node->id)
fprintf(out, "%i%i -> %i%i;\n", proc, host->node->id, proc, host->succ[0]->node->id);
else
cfg_draw_node(host->succ[0], out, proc, host->node->id);
if (host->succ[1] && host->node->id >= host->succ[1]->node->id)
fprintf(out, "%i%i -> %i%i;\n", proc, host->node->id, proc, host->succ[1]->node->id);
else
cfg_draw_node(host->succ[1], out, proc, host->node->id);
}
/* initiate traversal of CFG */
void cfg_draw_graph(cfg_node* host, FILE* out) {
cfg_node* next = host;
int proc = 1;
fprintf(out, "digraph {\n");
while (next) {
cfg_draw_node(next, stdout, proc++, -1);
next = next->next_proc;
}
fprintf(out, "}\n");
}