1"use strict";(globalThis.webpackChunkrascal_website=globalThis.webpackChunkrascal_website||[]).push([[7441],{15680(n,e,t){t.d(e,{xA:()=>p,yg:()=>h});var a=t(96540);function o(n,e,t){return e in n?Object.defineProperty(n,e,{value:t,enumerable:!0,configurable:!0,writable:!0}):n[e]=t,n}function r(n,e){var t=Object.keys(n);if(Object.getOwnPropertySymbols){var a=Object.getOwnPropertySymbols(n);e&&(a=a.filter((function(e){return Object.getOwnPropertyDescriptor(n,e).enumerable}))),t.push.apply(t,a)}return t}function i(n){for(var e=1;e<arguments.length;e++){var t=null!=arguments[e]?arguments[e]:{};e%2?r(Object(t),!0).forEach((function(e){o(n,e,t[e])})):Object.getOwnPropertyDescriptors?Object.defineProperties(n,Object.getOwnPropertyDescriptors(t)):r(Object(t)).forEach((function(e){Object.defineProperty(n,e,Object.getOwnPropertyDescriptor(t,e))}))}return n}function l(n,e){if(null==n)return{};var t,a,o=function(n,e){if(null==n)return{};var t,a,o={},r=Object.keys(n);for(a=0;a<r.length;a++)t=r[a],e.indexOf(t)>=0||(o[t]=n[t]);return o}(n,e);if(Object.getOwnPropertySymbols){var r=Object.getOwnPropertySymbols(n);for(a=0;a<r.length;a++)t=r[a],e.indexOf(t)>=0||Object.prototype.propertyIsEnumerable.call(n,t)&&(o[t]=n[t])}return o}var s=a.createContext({}),c=function(n){var e=a.useContext(s),t=e;return n&&(t="function"==typeof n?n(e):i(i({},e),n)),t},p=function(n){var e=c(n.components);return a.createElement(s.Provider,{value:e},n.children)},m={inlineCode:"code",wrapper:function(n){var e=n.children;return a.createElement(a.Fragment,{},e)}},g=a.forwardRef((function(n,e){var t=n.components,o=n.mdxType,r=n.originalType,s=n.parentName,p=l(n,["components","mdxType","originalType","parentName"]),g=c(t),h=o,u=g["".concat(s,".").concat(h)]||g[h]||m[h]||r;return t?a.createElement(u,i(i({ref:e},p),{},{components:t})):a.createElement(u,i({ref:e},p))}));function h(n,e){var t=arguments,o=e&&e.mdxType;if("string"==typeof n||o){var r=t.length,i=new Array(r);i[0]=g;var l={};for(var s in e)hasOwnProperty.call(e,s)&&(l[s]=e[s]);l.originalType=n,l.mdxType="string"==typeof n?n:o,i[1]=l;for(var c=2;c<r;c++)i[c]=t[c];return a.createElement.apply(null,i)}return a.createElement.apply(null,t)}g.displayName="MDXCreateElement"},53040(n,e,t){t.r(e),t.d(e,{assets:()=>s,contentTitle:()=>i,default:()=>m,frontMatter:()=>r,metadata:()=>l,toc:()=>c});var a=t(58168),o=(t(96540),t(15680));const r={title:"ControlFlow"},i=void 0,l={unversionedId:"Recipes/Languages/Pico/ControlFlow/index",id:"Recipes/Languages/Pico/ControlFlow/index",title:"ControlFlow",description:"rascal-0.42.2",source:"@site/docs/Recipes/Languages/Pico/ControlFlow/index.md",sourceDirName:"Recipes/Languages/Pico/ControlFlow",slug:"/Recipes/Languages/Pico/ControlFlow/",permalink:"/docs/Recipes/Languages/Pico/ControlFlow/",draft:!1,tags:[],version:"current",frontMatter:{title:"ControlFlow"},sidebar:"tutorialSidebar",previous:{title:"Compile",permalink:"/docs/Recipes/Languages/Pico/Compile/"},next:{title:"Evaluate",permalink:"/docs/Recipes/Languages/Pico/Evaluate/"}},s={},c=[{value:"Synopsis",id:"synopsis",level:4},{value:"Examples",id:"examples",level:4}],p={toc:c};function m(n){let{components:e,...t}=n;return(0,o.yg)("wrapper",(0,a.A)({},p,t,{components:e,mdxType:"MDXLayout"}),(0,o.yg)("div",{class:"theme-doc-version-badge badge badge--secondary"},"rascal-0.42.2"),(0,o.yg)("h4",{id:"synopsis"},"Synopsis"),(0,o.yg)("p",null,"Compute the control flow graph for a Pico program."),(0,o.yg)("h4",{id:"examples"},"Examples"),(0,o.yg)("p",null,"A control flow graph shows how the entry and exit points of a program are connected with each other via all\ndecision points and statements in the program. Typically, an assignment statement is a single node in the graph\nand an if-then-else statement creates a decision point (its test) that connects the then branch and the else branch.\nThe exits of each branch are connected to the exit of the if-then-else statement as a whole."),(0,o.yg)("p",null,"A control flow graph for Pico programs can be created as follows:"),(0,o.yg)("pre",null,(0,o.yg)("code",{parentName:"pre",className:"language-rascal"},"module demo::lang::Pico::ControlFlow\n\nimport analysis::graphs::Graph;\nimport demo::lang::Pico::Abstract;\nimport demo::lang::Pico::Load;\nimport List;\n\ndata CFNode \u2776 \n = entry(loc location)\n | exit(
1)\n | choice(loc location, EXP exp)\n | statement(loc location, STATEMENT stat)\n ;\n\n// highlight-next-line\nalias CFGraph = tuple[set[CFNode] entry, Graph[CFNode] graph, set[CFNode] exit]; \u2777 \n\n// highlight-next-line\nCFGraph cflowStat(s:asgStat(PicoId Id, EXP Exp)) { \u2778 \n S = statement(s.src, s);\n return <{S}, {}, {S}>;\n}\n\n// highlight-next-line\nCFGraph cflowStat(ifElseStat(EXP Exp, \u2779 \n list[STATEMENT] Stats1,\n list[STATEMENT] Stats2)) {\n CF1 = cflowStats(Stats1); \n CF2 = cflowStats(Stats2); \n E = {choice(Exp.src, Exp)}; \n return < E, (E * CF1.entry) + (E * CF2.entry) + CF1.graph + CF2.graph, CF1.exit + CF2.exit >;\n}\n\n// highlight-next-line\nCFGraph cflowStat(whileStat(EXP Exp, list[STATEMENT] Stats)) { \u277a \n CF = cflowStats(Stats); \n E = {choice(Exp.src, Exp)}; \n return < E, (E * CF.entry) + CF.graph + (CF.exit * E), E >;\n}\n\n// highlight-next-line\nCFGraph cflowStats(list[STATEMENT] Stats) { \u277b \n if(size(Stats) == 1) {\n return cflowStat(Stats[0]);\n }\n \n CF1 = cflowStat(Stats[0]);\n CF2 = cflowStats(tail(Stats));\n \n return < CF1.entry, CF1.graph + CF2.graph + (CF1.exit * CF2.entry), CF2.exit >;\n}\n\n// highlight-next-line\nCFGraph cflowProgram(PROGRAM P:program(list[DECL] _, list[STATEMENT] Series)) { \u277c \n CF = cflowStats(Series);\n Entry = entry(P.src);\n Exit = exit();\n \n return <{Entry}, ({Entry} * CF.entry) + CF.graph + (CF.exit * {Exit}), {Exit}>;\n}\n\n// highlight-next-line\nCFGraph cflowProgram(str txt) = cflowProgram(load(txt)); \u277d \n\n")),(0,o.yg)("p",null,"Notes:"),(0,o.yg)("ul",null,(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("p",{parentName:"li"},"\u2776 First we define a data type ",(0,o.yg)("inlineCode",{parentName:"p"},"CFNODE")," that represents the various elements of a control flow graph:"),(0,o.yg)("ul",{parentName:"li"},(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("inlineCode",{parentName:"li"},"entry"),": the entry point of the program."),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("inlineCode",{parentName:"li"},"exit")," the exit point of the program."),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("inlineCode",{parentName:"li"},"choice"),": a decision point in the control flow."),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("inlineCode",{parentName:"li"},"statement"),": a statement in the control flow."))),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("p",{parentName:"li"},"\u2777 Next we define ",(0,o.yg)("inlineCode",{parentName:"p"},"CFGRAPH")," , an alias for a tuple consisting of the following three elements:"),(0,o.yg)("ul",{parentName:"li"},(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("p",{parentName:"li"},(0,o.yg)("inlineCode",{parentName:"p"},"entry"),": the set of entry nodes of the graph.")),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("p",{parentName:"li"},(0,o.yg)("inlineCode",{parentName:"p"},"graph"),": the actual graph of ",(0,o.yg)("inlineCode",{parentName:"p"},"CFNODE"),"s.")),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("p",{parentName:"li"},(0,o.yg)("inlineCode",{parentName:"p"}
1,"exit"),": the set of exit nodes."),(0,o.yg)("p",{parentName:"li"}," The computation of the control flow graph is defined by the functions\n",(0,o.yg)("inlineCode",{parentName:"p"},"cflowStat"),", ",(0,o.yg)("inlineCode",{parentName:"p"},"cflowStats"),", ",(0,o.yg)("inlineCode",{parentName:"p"},"cflowDecls")," and ",(0,o.yg)("inlineCode",{parentName:"p"},"cflowProgram"),".")))),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("p",{parentName:"li"},"\u2778 The control flow of an assignment statement is computed by wrapping\nthe assignment statement as a ",(0,o.yg)("inlineCode",{parentName:"p"},"CFNODE")," and return a ",(0,o.yg)("inlineCode",{parentName:"p"},"CFGRAPH")," with the assignment\nstatement as entry and exit node, and no internal connections.")),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("p",{parentName:"li"},"\u2779 The control flow of an if-then-else statement is computed as follows:"),(0,o.yg)("ul",{parentName:"li"},(0,o.yg)("li",{parentName:"ul"},"First the control flows of the then part and the else part are computed,\nyielding ",(0,o.yg)("inlineCode",{parentName:"li"},"CF1")," and ",(0,o.yg)("inlineCode",{parentName:"li"},"CF2"),"."),(0,o.yg)("li",{parentName:"ul"},"Next a set ",(0,o.yg)("inlineCode",{parentName:"li"},"E")," is created that consist of a the test of the if-then-else statement\nwrapped as choice node."),(0,o.yg)("li",{parentName:"ul"},"Finally, a ",(0,o.yg)("inlineCode",{parentName:"li"},"CFGRAPH")," is returned consisting of the followng three elements:",(0,o.yg)("ul",{parentName:"li"},(0,o.yg)("li",{parentName:"ul"},"The entry point set ",(0,o.yg)("inlineCode",{parentName:"li"},"E"),"."),(0,o.yg)("li",{parentName:"ul"},"A graph consisting of the connections between the entry point and both\nbranches (",(0,o.yg)("inlineCode",{parentName:"li"},"E * CF1.entry + E * CF2.entry"),") and the internal graphs of both branches\n(",(0,o.yg)("inlineCode",{parentName:"li"},"CF1.graph + CF2.graph"),")."),(0,o.yg)("li",{parentName:"ul"},"The union of exit nodes of both branches (",(0,o.yg)("inlineCode",{parentName:"li"},"CF1.exit + CF2.exit"),")."))))),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("p",{parentName:"li"},"\u277a The control flow of while-statement is computed in a similar fashion,\nexcept that the exit of the loop body has to be connected with the entry\nof the while loop.")),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("p",{parentName:"li"},"\u277b The control flow graph for a series of statements is obtained by connecting\nthe exits and entries of consecutive statements.")),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("p",{parentName:"li"},"\u277c The control flow graph of a complete program is obtained by\ncreating an entry and an exit node and connecting them to the graph of\nthe statements of the program.")),(0,o.yg)("li",{parentName:"ul"},(0,o.yg)("p",{parentName:"li"},"\u277d Shows the steps from text to control flow graph."))),(0,o.yg)("p",null,"We can now create a CFG for a small Pico program:"),(0,o.yg)("pre",null,(0,o.yg)("code",{parentName:"pre",className:"language-rascal-shell"},'rascal>import demo::lang::Pico::ControlFlow;\nok\nrascal>cflowProgram("begin declare n : natural, s : string; n := 10; s := \\"a\\"; while n do s := s + \\"a\\"; n := n - 1 od end");\ntuple[set[CFNode] entry,Graph[CFNode] graph,set[CFNode] exit]: <{entry(|unknown:///|(0,100,<1,0>,<1,100>))},{\n <statement(\n |unknown:///|(39,7,<1,39>,<1,46>),\n asgStat(\n "n",\n natCon(\n 10,\n src=|unknown:///|(44,2,<1,44>,<1,46>),\n comments=()),\n src=|unknown:///|(39,7,<1,39>,<1,46>),\n comments=())),statement(\n |unknown:///|(48,8,<1,48>,<1,56>),\n asgStat(\n "s",\n strCon(\n "\\"a\\"",\n src=|unknown:///|(53,3,<1,53>,<1,56>),\n comments=()),\n src=|unknown:///|(48,8,<1,48>,<1,56>),\n comments=()))>,\n <statement(\n |unknown:///|(48,8,<1,48>,<1,56>),\n asgStat(\n "s",\n strCon(\n "\\"a\\"",\n src=|unknown:///|(53,3,<1,53>,<1,56>),\n comments=()),\n src=|unknown:///|(48,8,<1,48>,<1,56>),\n comments=())),choice(\n |unknown:///|(64,1,<1,64>,<1,65>),\n id(\n "n",\n src=|unknown:///|(64,1,<1,64>,<1,65>),\n comments=()))>
1,\n <statement(\n |unknown:///|(69,12,<1,69>,<1,81>),\n asgStat(\n "s",\n add(\n id(\n "s",\n src=|unknown:///|(74,1,<1,74>,<1,75>),\n comments=()),\n strCon(\n "\\"a\\"",\n src=|unknown:///|(78,3,<1,78>,<1,81>),\n comments=()),\n src=|unknown:///|(74,7,<1,74>,<1,81>),\n comments=()),\n src=|unknown:///|(69,12,<1,69>,<1,81>),\n comments=())),statement(\n |unknown:///|(83,10,<1,83>,<1,93>),\n asgStat(\n "n",\n sub(\n id(\n "n",\n src=|unknown:///|(88,1,<1,88>,<1,89>),\n comments=()),\n natCon(\n 1,\n src=|unknown:///|(92,1,<1,92>,<1,93>),\n comments=()),\n src=|unknown:///|(88,5,<1,88>,<1,93>),\n comments=()),\n src=|unknown:///|(83,10,<1,83>,<1,93>),\n comments=()))>,\n <entry(|unknown:///|(0,100,<1,0>,<1,100>)),statement(\n |unknown:///|(39,7,<1,39>,<1,46>),\n asgStat(\n "n",\n natCon(\n 10,\n src=|unknown:///|(44,2,<1,44>,<1,46>),\n comments=()),\n src=|unknown:///|(39,7,<1,39>,<1,46>),\n comments=()))>,\n <statement(\n |unknown:///|(83,10,<1,83>,<1,93>),\n asgStat(\n "n",\n sub(\n id(\n "n",\n src=|unknown:///|(88,1,<1,88>,<1,89>),\n comments=()),\n natCon(\n 1,\n src=|unknown:///|(92,1,<1,92>,<1,93>),\n comments=()),\n src=|unknown:///|(88,5,<1,88>,<1,93>),\n comments=()),\n src=|unknown:///|(83,10,<1,83>,<1,93>),\n comments=())),choice(\n |unknown:///|(64,1,<1,64>,<1,65>),\n id(\n "n",\n src=|unknown:///|(64,1,<1,64>,<1,65>),\n comments=()))>,\n <choice(\n |unknown:///|(64,1,<1,64>,<1,65>),\n id(\n "n",\n src=|unknown:///|(64,1,<1,64>,<1,65>),\n comments=())),exit()>,\n <choice(\n |unknown:///|(64,1,<1,64>,<1,65>),\n id(\n "n",\n src=|unknown:///|(64,1,<1,64>,<1,65>),\n comments=())),statement(\n |unknown:///|(69,12,<1,69>,<1,81>),\n asgStat(\n "s",\n add(\n id(\n "s",\n src=|unknown:///|(74,1,<1,74>,<1,75>),\n comments=()),\n strCon(\n "\\"a\\"",\n src=|unknown:///|(78,3,<1,78>,<1,81>),\n comments=()),\n src=|unknown:///|(74,7,<1,74>,<1,81>),\n comments=()),\n src=|unknown:///|(69,12,<1,69>,<1,81>),\n comments=()))>\n},{exit()}>\n')))}m.isMDXComponent=!0}}]);
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.