3 * Copyright (C) 2006, 2007, 2008 Ecole des Mines de Nantes
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License (GPL)
7 * version 2 as published by the Free Software Foundation.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * file license.txt for more details.
18 (*****************************************************************************)
20 * There is more information in the CFG we build that in the CFG usually built
21 * in a compiler. This is because:
23 * - We need later to go back from flow to original ast, because we are
24 * doing a refactoring tool, so different context. So we have to add
25 * some nodes for '{' or '}' or goto that normally disapear in a CFG.
26 * We must keep those entities, in the same way that we must keep the parens
27 * (ParenExpr, ParenType) in the Ast_c during parsing.
29 * Moreover, the coccier can mention in his semantic patch those entities,
30 * so we must keep those entities in the CFG.
32 * We also have to add some extra nodes to make the process that goes from
33 * flow to ast deterministic with for instance the CaseNode, or easier
34 * with for instance the Fake node.
36 * - The coccinelle engine later transforms some nodes, and we need to rebuild
37 * the ast from a statement now defined and altered in different nodes.
38 * So we can't just put all the parsing info (Ast_c.il) in the top node of
39 * a statement. We have to split those Ast_c.il in different nodes, to
40 * later reconstruct a full Ast_c.il from different nodes. This is why
41 * we need the Else node, ...
43 * Note that at the same time, we also need to store the fullstatement
44 * in the top node, because the CTL engine need to get that information
45 * when dealing with MetaStatement (statement S; in a Semantic Patch).
48 * - The CTL engine needs more information than just the CFG, and we use
49 * tricks to encode those informations in the nodes:
51 * - We have some TrueNode, FalseNode to know in what branch we are.
52 * Normally we could achieve this by putting this information in the
53 * edges, but CTL engine know nothing about edges, it must do
54 * everything with only nodes information.
56 * - We need to mark each braces with an identifier so that the CTL
57 * can know if one specific '}' correspond to a specific '{'.
59 * - We add some labels to each node to handle the MetaRuleElem and
60 * MetaStatement. It allows to groups nodes that belong to the same
61 * statement. Normally CFG are there to abstract from this, but in
62 * Coccinelle we need sometimes the CFG view, and sometimes the Ast
63 * view and the labels allow that.
65 * - We even add nodes. We add '}', not only to be able to go back to AST
66 * but also because of the CTL engine. So one '}' may in fact be
67 * represented by multiple nodes, one in each CFG path.
71 * - Need know if ErrorExit,
73 * choice: Julia proposed that the flow is in fact just
74 * a view through the Ast, which means just Ocaml ref, so that when we
75 * modify some nodes, in fact it modifies the ast. But I prefer do it
76 * the functionnal way.
78 * The node2 type should be as close as possible to Ast_cocci.rule_elem to
79 * facilitate the job of cocci_vs_c.
83 (*****************************************************************************)
86 (* ---------------------------------------------------------------------- *)
87 (* The string is for debugging. Used by Ograph_extended.print_graph.
88 * The int list are Labels. Trick used for CTL engine. Must not
89 * transform that in a triple or record because print_graph would
92 type node
= node1
* string
93 and node1
= node2
* nodeinfo
96 bclabels
: int list
; (* parent of a break or continue node *)
102 (* ------------------------ *)
103 (* For CTL to work, we need that some nodes loop over itself. We
104 * need that every nodes have a successor. Julia also want to go back
105 * indefinitely. So must tag some nodes as the beginning and end of
106 * the graph so that some fix_ctl function can easily find those
109 * If have a function, then no need for EndNode; Exit and ErrorExit
110 * will play that role.
112 * When everything we analyze was a function there was no pb. We used
113 * FunHeader as a Topnode and Exit for EndNode but now that we also
114 * analyse #define body, so we need those nodes.
119 (* ------------------------ *)
120 | FunHeader
of definition
(* but empty body *)
122 | Decl
of declaration
124 (* ------------------------ *)
125 (* flow_to_ast: cocci: Need the { and } in the control flow graph also
126 * because the coccier can express patterns containing such { }.
128 * ctl: to make possible the forall (AX, A[...]), have to add more than
129 * one node sometimes for the same '}' (one in each CFG path) in the graph.
131 * ctl: Morover, the int in the type is here to indicate to what { }
132 * they correspond. Two pairwise { } share the same number. kind of
133 * "brace_identifier". Used for debugging or for checks and more importantly,
134 * needed by CTL engine.
136 * Because of those nodes, there is no equivalent for Compound.
138 * There was a problem with SeqEnd. Some info can be tagged on it
139 * but there is multiple SeqEnd that correspond to the same '}' even
140 * if they are in different nodes. Solved by using shared ref
141 * and allow the "already-tagged" token.
143 | SeqStart
of statement
* int * info
144 | SeqEnd
of int * info
147 | ExprStatement
of statement
* (expression
option) wrap
150 | IfHeader
of statement
* expression wrap
152 | WhileHeader
of statement
* expression wrap
153 | DoHeader
of statement
* info
154 | DoWhileTail
of expression wrap
155 | ForHeader
of statement
*
156 (exprStatement wrap
* exprStatement wrap
* exprStatement wrap
)
158 | SwitchHeader
of statement
* expression wrap
159 | MacroIterHeader
of statement
* (string * argument wrap2 list
) wrap
161 (* Used to mark the end of if, while, dowhile, for, switch. Later we
162 * will be able to "tag" some cocci code on this node.
168 * the S can be anything, including an if, and this is internally
169 * translated in a series of MetaRuleElem, and the last element is a
170 * EndStatement, and we must tag foo() to this EndStatement.
171 * Otherwise, without this last common node, we would tag foo() to 2
172 * nodes :( So having a unique node makes it correct, and in
173 * flow_to_ast we must propagate back this + foo() to the last token
174 * of an if (maybe a '}', maybe a ';')
176 * The problem is that this stuff should be in transformation.ml,
177 * but need information available in flow_to_ast, but we dont want
178 * to polluate both files.
182 * - soluce julia1, extend Ast_c by adding a fake token to the if
184 * - extend Ast with a Skip, and add this next to EndStatement node,
185 * and do special case in flow_to_ast to start from this node
186 * (not to get_next EndStatement, but from EndStatement directly)
187 * and so add a case when have directly a EndStatement node an extract
188 * the statement from it.
190 * - remonter dans le graphe pour accrocher le foo() non plus au
191 * EndStatement (qui n'a pas d'equivalent niveau token dans l'ast_c),
192 * mais au dernier token de la branche Else (ou Then si y'a pas de else).
194 * I first did solution 2 and then when we decided to use ref,
195 * I use julia'as solution. Have virtual-placeholders, the fakeInfo
196 * for the if, while, and put this shared ref in the EndStatement.
198 | EndStatement
of info
option (* fake_info *)
200 | Return
of statement
* unit wrap
201 | ReturnExpr
of statement
* expression wrap
203 (* ------------------------ *)
204 | IfdefHeader
of ifdef_directive
205 | IfdefElse
of ifdef_directive
206 | IfdefEndif
of ifdef_directive
209 (* ------------------------ *)
210 | DefineHeader
of string wrap
* define_kind
212 | DefineExpr
of expression
213 | DefineType
of fullType
214 | DefineDoWhileZeroHeader
of unit wrap
220 | MacroTop
of string * argument wrap2 list
* il
222 (* ------------------------ *)
223 | Case
of statement
* expression wrap
224 | Default
of statement
* unit wrap
226 | Continue
of statement
* unit wrap
227 | Break
of statement
* unit wrap
229 (* no counter part in cocci *)
230 | CaseRange
of statement
* (expression
* expression
) wrap
231 | Label
of statement
* string wrap
232 | Goto
of statement
* string wrap
235 | Asm
of statement
* asmbody wrap
236 | MacroStmt
of statement
* unit wrap
238 (* ------------------------ *)
239 (* some control nodes *)
244 (* Redundant nodes, often to mark the end of an if/switch.
245 * That makes it easier to do later the flow_to_ast.
246 * update: no more used for the end. see Endstatement. Just used
247 * to mark the start of the function, as required by julia.
248 * Maybe would be better to use instead a Enter2.
252 (* flow_to_ast: In this case, I need to know the order between the children
253 * of the switch in the graph.
257 (* ------------------------ *)
261 | InLoopNode
(* almost equivalent to TrueNode but just for loops *)
268 type edge
= Direct
(* Normal | Shadow *)
270 type cflow
= (node
, edge
) Ograph_extended.ograph_mutable
273 (* ------------------------------------------------------------------------ *)
274 let unwrap ((node
, info
), nodestr
) = node
275 let rewrap ((_node
, info
), nodestr
) node
= (node
, info
), nodestr
276 let extract_labels ((node
, info
), nodestr
) = info
.labels
277 let extract_bclabels ((node
, info
), nodestr
) = info
.bclabels
278 let extract_is_loop ((node
, info
), nodestr
) = info
.is_loop
279 let extract_is_fake ((node
, info
), nodestr
) = info
.is_fake
281 let mk_any_node is_fake node labels bclabels nodestr
=
283 if !Flag_parsing_c.show_flow_labels
284 then nodestr ^
("[" ^
(labels
+> List.map i_to_s
+> join
",") ^
"]")
287 ((node
, {labels
= labels
;is_loop
=false;bclabels
=bclabels
;is_fake
=is_fake
}),
290 let mk_node = mk_any_node false
291 let mk_fake_node = mk_any_node true (* for duplicated braces *)
293 (* ------------------------------------------------------------------------ *)
295 g#nodes#tolist
+> List.find
(fun (i
, node
) ->
296 match unwrap node
with TopNode
-> true | _
-> false
300 g#nodes#tolist
+> List.find
(fun (nodei
, node
) ->
305 (* remove an intermediate node and redirect the connexion *)
306 let remove_one_node nodei g
=
307 let preds = (g#predecessors nodei
)#tolist
in
308 let succs = (g#successors nodei
)#tolist
in
309 assert (not
(null
preds));
311 preds +> List.iter
(fun (predi
, Direct
) ->
312 g#del_arc
((predi
, nodei
), Direct
);
314 succs +> List.iter
(fun (succi
, Direct
) ->
315 g#del_arc
((nodei
, succi
), Direct
);
320 (* connect in-nodes to out-nodes *)
321 preds +> List.iter
(fun (pred
, Direct
) ->
322 succs +> List.iter
(fun (succ
, Direct
) ->
323 g#add_arc
((pred
, succ
), Direct
);
329 (* ------------------------------------------------------------------------ *)
331 let extract_fullstatement node
=
332 match unwrap node
with
334 (* new policy. no more considered as a statement *)
335 (* old: Some (Ast_c.Decl decl, []) *)
337 | MacroStmt
(st
, _
) -> Some st
338 | MacroIterHeader
(st
, _
) -> Some st
341 | DefineHeader _
| DefineType _
| DefineExpr _
| DefineDoWhileZeroHeader _
346 | IfdefHeader _
| IfdefElse _
| IfdefEndif _
350 | ExprStatement
(st
, _
)
352 | WhileHeader
(st
, _
)
355 | SwitchHeader
(st
, _
)
358 (* no counter part in cocci *)