API tools faq
paste
Falexom

Untitled

Falexom
Dec 23rd, 2024
95
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 16.92 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <stdbool.h>
  5. #include <antlr3.h>
  6.  
  7. #include "graphStructures.h"
  8.  
  9. #include "misc.h"
  10.  
  11. int nodeId = 0;
  12.  
  13. static struct cfgNode **allNodes = NULL;
  14. static int allNodesCount = 0;
  15.  
  16. struct breakStack {
  17. struct cfgNode *breakTarget;
  18. struct breakStack *next;
  19. };
  20.  
  21. // ------------------------------------------------------------------------
  22. // Utils
  23. // ------------------------------------------------------------------------
  24. static char* safeStrdup(const char *s) {
  25. return s ? strdup(s) : NULL;
  26. }
  27.  
  28. static void addNodeToGlobalList(struct cfgNode *node) {
  29. struct cfgNode **tmp = realloc(allNodes, sizeof(struct cfgNode*)*(allNodesCount+1));
  30. if (!tmp) {
  31. fprintf(stderr,"Error: realloc for allNodes failed\n");
  32. exit(1);
  33. }
  34. allNodes = tmp;
  35. allNodes[allNodesCount++] = node;
  36. }
  37.  
  38. static bool isNodeInList(struct cfgNode *candidate) {
  39. if (!candidate) return false;
  40. for (int i=0; i<allNodesCount; i++) {
  41. if (allNodes[i] == candidate) {
  42. return true;
  43. }
  44. }
  45. return false;
  46. }
  47.  
  48. // ------------------------------------------------------------------------
  49. // Создание узлов и функций
  50. // ------------------------------------------------------------------------
  51. struct cfgNode* createCfgNode(pANTLR3_BASE_TREE tree) {
  52. struct cfgNode *node = calloc(1, sizeof(struct cfgNode));
  53. if (!node) {
  54. fprintf(stderr,"Error: Allocation for cfgNode failed\n");
  55. return NULL;
  56. }
  57. node->id = nodeId++;
  58. node->ast = (struct astNode*)tree;
  59. node->isProcessed = false; // Инициализируем как необработанный
  60. addNodeToGlobalList(node);
  61. return node;
  62. }
  63.  
  64.  
  65. struct funcNode* processFunction(pANTLR3_BASE_TREE funcTree, char* name) {
  66. struct funcNode *f = calloc(1, sizeof(struct funcNode));
  67. f->identifier = safeStrdup(name? name : "unknown_func");
  68.  
  69. f->cfgEntry = createCfgNode(funcTree);
  70. f->cfgEntry->name = safeStrdup(f->identifier);
  71.  
  72. f->cfgExit = createCfgNode(NULL);
  73. f->cfgExit->name = safeStrdup("func_exit");
  74.  
  75. return f;
  76. }
  77.  
  78. // ------------------------------------------------------------------------
  79. // Работа с break
  80. // ------------------------------------------------------------------------
  81. static void pushBreak(struct context *ctx, struct cfgNode *breakTarget) {
  82. struct breakStack *bs = malloc(sizeof(struct breakStack));
  83. bs->breakTarget = breakTarget;
  84. bs->next = ctx->breakStack;
  85. ctx->breakStack = bs;
  86. }
  87. static struct cfgNode* topBreak(struct context *ctx) {
  88. return ctx->breakStack? ctx->breakStack->breakTarget : NULL;
  89. }
  90. static void popBreak(struct context *ctx) {
  91. if (ctx->breakStack) {
  92. struct breakStack* tmp = ctx->breakStack;
  93. ctx->breakStack = tmp->next;
  94. free(tmp);
  95. }
  96. }
  97.  
  98. // ------------------------------------------------------------------------
  99. // Проверка узлов (if/while/break) не лезут в строку выражения
  100. // ------------------------------------------------------------------------
  101. static bool isControlNode(const char* n) {
  102. if (!n) return true;
  103. if (!strcmp(n,"CondToken")) return true;
  104. if (!strcmp(n,"LoopToken")) return true;
  105. if (!strcmp(n,"BreakToken")) return true;
  106. if (!strcmp(n,"VarDeclToken")) return true;
  107. // ... дополняйте при желании
  108. return false;
  109. }
  110.  
  111. // ------------------------------------------------------------------------
  112. // Сборка строки выражения (if((expr)), while((expr)))
  113. // ------------------------------------------------------------------------
  114. static void getExpressionString(pANTLR3_BASE_TREE tree, char* buf, size_t sz) {
  115. if (!tree || sz<2) return;
  116. pANTLR3_STRING s = tree->toString(tree);
  117. const char* nm = (s&&s->chars)? s->chars:"";
  118. unsigned cc = tree->getChildCount(tree);
  119.  
  120. if (isControlNode(nm)) {
  121. for (unsigned i=0; i<cc; i++) {
  122. getExpressionString(tree->getChild(tree,i), buf, sz);
  123. }
  124. return;
  125. }
  126.  
  127. if (cc==0) {
  128. if (strlen(buf)+strlen(nm)+2 < sz) {
  129. strcat(buf,nm);
  130. }
  131. }
  132. else if (cc==2 && (
  133. !strcmp(nm,"==")||!strcmp(nm,"!=")||
  134. !strcmp(nm,"+") ||!strcmp(nm,"-") ||
  135. !strcmp(nm,"*") ||!strcmp(nm,"/") ||
  136. !strcmp(nm,"%")))
  137. {
  138. strcat(buf,"(");
  139. getExpressionString(tree->getChild(tree,0), buf, sz);
  140. strcat(buf,nm);
  141. getExpressionString(tree->getChild(tree,1), buf, sz);
  142. strcat(buf,")");
  143. } else {
  144. for (unsigned i=0; i<cc; i++) {
  145. getExpressionString(tree->getChild(tree,i), buf, sz);
  146. }
  147. }
  148. }
  149.  
  150. // ------------------------------------------------------------------------
  151. // processTreeNode + обработчики if/while/break/return
  152. // ------------------------------------------------------------------------
  153.  
  154. static void processTreeNode(pANTLR3_BASE_TREE tree, struct context *ctx);
  155.  
  156. static void processConditional(pANTLR3_BASE_TREE ifTree, struct context *ctx) {
  157. struct cfgNode *ifNode = createCfgNode(ifTree);
  158.  
  159. char expr[256];
  160. expr[0] = '\0';
  161. unsigned cc = ifTree->getChildCount(ifTree);
  162. pANTLR3_BASE_TREE exprChild = NULL;
  163. pANTLR3_BASE_TREE thenBody = NULL;
  164. pANTLR3_BASE_TREE elseBody = NULL;
  165. if (cc > 0) exprChild = ifTree->getChild(ifTree, 0);
  166. if (cc > 1) thenBody = ifTree->getChild(ifTree, 1);
  167. if (cc > 2) elseBody = ifTree->getChild(ifTree, 2);
  168. if (exprChild) {
  169. getExpressionString(exprChild, expr, sizeof(expr));
  170. }
  171. if (expr[0]) {
  172. char tmp[300];
  173. snprintf(tmp, sizeof(tmp), "if ((%s))", expr);
  174. ifNode->name = safeStrdup(tmp);
  175. } else {
  176. ifNode->name = safeStrdup("if (?)");
  177. }
  178. if (ctx->curr) {
  179. ctx->curr->defaultBranch = ifNode;
  180. }
  181. ctx->curr = ifNode;
  182.  
  183. struct cfgNode* endIf = createCfgNode(NULL);
  184. endIf->name = safeStrdup("endif");
  185.  
  186. if (thenBody) {
  187. struct cfgNode* thenStart = createCfgNode(thenBody);
  188. thenStart->name = safeStrdup("thenBlock");
  189. ifNode->conditionalBranch = thenStart;
  190. ctx->curr = thenStart;
  191. unsigned tCount = thenBody->getChildCount(thenBody);
  192. for (unsigned i = 0; i < tCount; i++) {
  193. pANTLR3_BASE_TREE ch = thenBody->getChild(thenBody, i);
  194. char* childNodeStr = (char*)ch->toString(ch)->chars;
  195. }
  196. processTreeNode(thenBody, ctx);
  197. if (ctx->curr && ctx->curr->defaultBranch == NULL) {
  198. ctx->curr->defaultBranch = endIf;
  199. }
  200. } else {
  201. ifNode->conditionalBranch = endIf;
  202. }
  203.  
  204. // --- else-ветка ---
  205. if (elseBody) {
  206. struct cfgNode* elseStart = createCfgNode(elseBody);
  207. elseStart->name = safeStrdup("elseBlock");
  208. ifNode->defaultBranch = elseStart;
  209. ctx->curr = elseStart;
  210. unsigned eCount = elseBody->getChildCount(elseBody);
  211. for (unsigned i = 0; i < eCount; i++) {
  212. pANTLR3_BASE_TREE ch = elseBody->getChild(elseBody, i);
  213. char* childNodeStr = (char*)ch->toString(ch)->chars;
  214. }
  215.  
  216. processTreeNode(elseBody, ctx);
  217.  
  218. if (ctx->curr && ctx->curr->defaultBranch==NULL) {
  219. ctx->curr->defaultBranch = endIf;
  220. }
  221. } else {
  222. if (!ifNode->defaultBranch) {
  223. ifNode->defaultBranch = endIf;
  224. }
  225. }
  226. ctx->curr = endIf;
  227. }
  228.  
  229. struct cfgNode* findCfgNodeByAST(pANTLR3_BASE_TREE tree) {
  230. for (int i = 0; i < allNodesCount; i++) {
  231. if (allNodes[i]->ast == (struct astNode*)tree) {
  232. return allNodes[i];
  233. }
  234. }
  235. return NULL;
  236. }
  237.  
  238.  
  239. static void processLoop(pANTLR3_BASE_TREE loopTree, struct context *ctx) {
  240. struct cfgNode* existingNode = findCfgNodeByAST(loopTree);
  241. if (existingNode && existingNode->isProcessed) {
  242. printf(" LoopToken Node%d уже обработан. Пропускаем.\n", existingNode->id);
  243. ctx->curr = existingNode;
  244. return;
  245. }
  246.  
  247. struct cfgNode* loopNode = createCfgNode(loopTree);
  248. char expr[256] = {0};
  249.  
  250. unsigned cc = loopTree->getChildCount(loopTree);
  251. pANTLR3_BASE_TREE exprChild = NULL, bodyChild = NULL;
  252. if (cc > 0) exprChild = loopTree->getChild(loopTree, 0);
  253. if (cc > 1) bodyChild = loopTree->getChild(loopTree, 1);
  254.  
  255. if (exprChild) {
  256. getExpressionString(exprChild, expr, sizeof(expr));
  257. }
  258. if (expr[0]) {
  259. char tmp[300];
  260. snprintf(tmp, sizeof(tmp), "loop %s", expr);
  261. loopNode->name = safeStrdup(tmp);
  262. }
  263. else {
  264. loopNode->name = safeStrdup("(?)");
  265. }
  266.  
  267. if (ctx->curr) {
  268. ctx->curr->defaultBranch = loopNode;
  269. }
  270. struct cfgNode *loopExit = createCfgNode(NULL);
  271. loopExit->name = safeStrdup("loop_exit");
  272. loopNode->isProcessed = true;
  273.  
  274. pushBreak(ctx, loopExit);
  275.  
  276. if (bodyChild) {
  277. struct cfgNode *bodyStart = createCfgNode(bodyChild);
  278. bodyStart->name = safeStrdup("loop_body");
  279. loopNode->conditionalBranch = bodyStart;
  280. ctx->curr = bodyStart;
  281.  
  282. unsigned bodyChildCount = bodyChild->getChildCount(bodyChild);
  283. for (unsigned i = 0; i < bodyChildCount; i++) {
  284. pANTLR3_BASE_TREE child = bodyChild->getChild(bodyChild, i);
  285. char* childName = (char*)child->toString(child)->chars;
  286. }
  287.  
  288. processTreeNode(bodyChild, ctx);
  289. if (ctx->curr && ctx->curr->defaultBranch == NULL) {
  290. ctx->curr->defaultBranch = loopExit;
  291. }
  292. }
  293.  
  294. loopNode->defaultBranch = loopExit;
  295. ctx->curr = loopExit;
  296. popBreak(ctx);
  297. }
  298.  
  299.  
  300. static void processBreak(pANTLR3_BASE_TREE bkTree, struct context *ctx) {
  301. struct cfgNode *bkNode = createCfgNode(bkTree);
  302. bkNode->name = safeStrdup("break");
  303. if (ctx->curr) {
  304. ctx->curr->defaultBranch = bkNode;
  305. }
  306. struct cfgNode* exitNode = topBreak(ctx);
  307. if (exitNode) {
  308. bkNode->defaultBranch = exitNode;
  309. } else {
  310. fprintf(stderr,"Warning: break outside loop\n");
  311. }
  312. ctx->curr = bkNode;
  313. }
  314.  
  315. static void processReturn(pANTLR3_BASE_TREE retTree, struct context *ctx) {
  316. struct cfgNode* r = createCfgNode(retTree);
  317. char expr[256]; expr[0]='\0';
  318.  
  319. if (retTree->getChildCount(retTree)>0) {
  320. getExpressionString(retTree->getChild(retTree,0), expr,sizeof(expr));
  321. }
  322. if (expr[0]) {
  323. char tmp[300];
  324. snprintf(tmp,sizeof(tmp),"return (%s)",expr);
  325. r->name = safeStrdup(tmp);
  326. } else {
  327. r->name = safeStrdup("return");
  328. }
  329. if (ctx->curr) {
  330. ctx->curr->defaultBranch = r;
  331. }
  332. ctx->curr = r;
  333. }
  334.  
  335. static bool isTrivialNode(const char* n) {
  336. if (!n) return true;
  337. if (!strcmp(n,"Identifier")) return true;
  338. if (!strcmp(n,"Literal")) return true;
  339. if (!strcmp(n,"Builtin")) return true;
  340. if (!strcmp(n,"TypeRefToken")) return true;
  341. if (!strcmp(n,"VarDeclToken")) return true;
  342. if (!strcmp(n,"ArrayToken")) return true;
  343. if (!strcmp(n,"ArrayTokenSuffix")) return true;
  344. if (!strcmp(n,"FuncSignatureToken")) return true;
  345. if (!strcmp(n,"ArgListToken")) return true;
  346. if (!strcmp(n,"Body")) return true;
  347. return false;
  348. }
  349.  
  350. static void processGenericNode(pANTLR3_BASE_TREE tree, struct context *ctx) {
  351. if (!tree) return;
  352. pANTLR3_STRING s = tree->toString(tree);
  353. const char* nm = (s && s->chars) ? s->chars : "";
  354.  
  355. if (isTrivialNode(nm)) {
  356. unsigned cc = tree->getChildCount(tree);
  357. for (unsigned i=0; i<cc; i++) {
  358. processTreeNode(tree->getChild(tree,i), ctx);
  359. }
  360. return;
  361. }
  362. struct cfgNode* g = createCfgNode(tree);
  363. g->name = safeStrdup(nm);
  364.  
  365. if (ctx->curr) {
  366. ctx->curr->defaultBranch = g;
  367. }
  368. ctx->curr = g;
  369.  
  370. unsigned cc=tree->getChildCount(tree);
  371. for (unsigned i=0;i<cc;i++) {
  372. pANTLR3_BASE_TREE ch=tree->getChild(tree,i);
  373. processTreeNode(ch, ctx);
  374. }
  375. }
  376.  
  377. static void processTreeNode(pANTLR3_BASE_TREE tree, struct context *ctx) {
  378. if (!tree) return;
  379.  
  380. pANTLR3_STRING s = tree->toString(tree);
  381. const char* nm = (s && s->chars) ? s->chars : "";
  382.  
  383. if (!strcmp(nm, "CondToken")) {
  384. processConditional(tree, ctx);
  385. }
  386. else if (!strcmp(nm, "LoopToken")) {
  387. processLoop(tree, ctx);
  388. }
  389. else if (!strcmp(nm, "BreakToken")) {
  390. processBreak(tree, ctx);
  391. }
  392. else if (!strcmp(nm, "ReturnToken")) {
  393. processReturn(tree, ctx);
  394. }
  395. else {
  396. processGenericNode(tree, ctx);
  397. }
  398. }
  399.  
  400.  
  401. // -------------------------------------------------------------
  402. // resetTraversal, printCFGNode, drawCFG
  403. // -------------------------------------------------------------
  404. static void resetTraversal(struct cfgNode *node) {
  405. if (!node) return;
  406. if (node->isTraversed) return;
  407. node->isTraversed=true;
  408.  
  409. if (node->conditionalBranch && !isNodeInList(node->conditionalBranch)) {
  410. node->conditionalBranch=NULL;
  411. }
  412. if (node->defaultBranch && !isNodeInList(node->defaultBranch)) {
  413. node->defaultBranch=NULL;
  414. }
  415. if (node->conditionalBranch) resetTraversal(node->conditionalBranch);
  416. if (node->defaultBranch) resetTraversal(node->defaultBranch);
  417.  
  418. node->isTraversed=false;
  419. }
  420.  
  421. static void printCFGNode(FILE *f, struct cfgNode *node) {
  422. if (!node||node->isTraversed) return;
  423. node->isTraversed=true;
  424.  
  425. fprintf(f," Node%d [label=\"%s\"];\n",node->id,node->name?node->name:"");
  426.  
  427. if (node->conditionalBranch && !isNodeInList(node->conditionalBranch)) {
  428. node->conditionalBranch=NULL;
  429. }
  430. if (node->defaultBranch && !isNodeInList(node->defaultBranch)) {
  431. node->defaultBranch=NULL;
  432. }
  433.  
  434. bool isIf=false,isWhile=false;
  435. if (node->name) {
  436. if (!strncmp(node->name,"if ((",4)) isIf=true;
  437. else if (!strncmp(node->name,"while ((",7)) isWhile=true;
  438. }
  439.  
  440. if (node->conditionalBranch) {
  441. const char* lab = isIf? "then": (isWhile? "true":"");
  442. fprintf(f," Node%d -> Node%d [label=\"%s\"];\n",
  443. node->id,node->conditionalBranch->id,lab);
  444. printCFGNode(f,node->conditionalBranch);
  445. }
  446. if (node->defaultBranch) {
  447. const char* lab = isIf? "else": (isWhile? "false":"");
  448. fprintf(f," Node%d -> Node%d [label=\"%s\"];\n",
  449. node->id,node->defaultBranch->id,lab);
  450. printCFGNode(f,node->defaultBranch);
  451. }
  452. }
  453.  
  454. static void drawCFG(struct programGraph *graph) {
  455. if (!graph) return;
  456. for (int i=0; i<graph->funcCount; i++) {
  457. struct funcNode *fn = graph->functions[i];
  458. if (!fn || !fn->cfgEntry) continue;
  459.  
  460. char fname[256];
  461. snprintf(fname,sizeof(fname),"%s.dot", fn->identifier);
  462. FILE *fp = fopen(fname,"w");
  463. if (!fp) {
  464. fprintf(stderr,"Error: cannot open %s\n",fname);
  465. continue;
  466. }
  467. resetTraversal(fn->cfgEntry);
  468.  
  469. fprintf(fp,"digraph CFG {\n");
  470. fprintf(fp," node [shape=box];\n");
  471. printCFGNode(fp, fn->cfgEntry);
  472. fprintf(fp,"}\n");
  473. fclose(fp);
  474.  
  475. char cmd[512];
  476. snprintf(cmd,sizeof(cmd),"dot -Tpng %s -o %s.png", fname, fn->identifier);
  477. system(cmd);
  478. }
  479. }
  480.  
  481. // -------------------------------------------------------------
  482. // processTree
  483. // -------------------------------------------------------------
  484. void processTree(pANTLR3_BASE_TREE tree) {
  485. struct programGraph *graph = calloc(1,sizeof(struct programGraph));
  486. unsigned topCount = tree->getChildCount(tree);
  487.  
  488. for (unsigned i=0; i<topCount; i++) {
  489. pANTLR3_BASE_TREE child = tree->getChild(tree,i);
  490. pANTLR3_STRING s = child->toString(child);
  491. const char* nm = (s&&s->chars)? s->chars:"";
  492. if (!strcmp(nm,"FuncDefToken")) {
  493. struct funcNode *func = processFunction(child,"calculate");
  494. graph->functions = realloc(graph->functions,
  495. sizeof(struct funcNode*)*(graph->funcCount+1));
  496. graph->functions[graph->funcCount++] = func;
  497.  
  498. struct context ctx;
  499. memset(&ctx,0,sizeof(ctx));
  500. ctx.curr = func->cfgEntry;
  501. ctx.entryNode = func->cfgEntry;
  502. ctx.exitNode = func->cfgExit;
  503. ctx.loopDepth = 0;
  504. ctx.breakStack= NULL;
  505. ctx.function = func;
  506.  
  507. unsigned c2 = child->getChildCount(child);
  508. for (unsigned j=0; j<c2; j++) {
  509. pANTLR3_BASE_TREE st = child->getChild(child,j);
  510. processTreeNode(st,&ctx);
  511. }
  512.  
  513. if (ctx.curr && ctx.curr!=func->cfgExit && ctx.curr->defaultBranch==NULL) {
  514. ctx.curr->defaultBranch = func->cfgExit;
  515. }
  516. }
  517. }
  518.  
  519. drawCFG(graph);
  520. }
  521.  
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!