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 (*****************************************************************************)
85 type fullstatement
= statement
87 (* ---------------------------------------------------------------------- *)
88 (* The string is for debugging. Used by Ograph_extended.print_graph.
89 * The int list are Labels. Trick used for CTL engine. Must not
90 * transform that in a triple or record because print_graph would
93 type node
= node1
* string
94 and node1
= node2
* nodeinfo
97 bclabels
: int list
; (* parent of a break or continue node *)
103 (* ------------------------ *)
104 (* For CTL to work, we need that some nodes loop over itself. We
105 * need that every nodes have a successor. Julia also want to go back
106 * indefinitely. So must tag some nodes as the beginning and end of
107 * the graph so that some fix_ctl function can easily find those
110 * If have a function, then no need for EndNode; Exit and ErrorExit
111 * will play that role.
113 * When everything we analyze was a function there was no pb. We used
114 * FunHeader as a Topnode and Exit for EndNode but now that we also
115 * analyse #define body, so we need those nodes.
120 (* ------------------------ *)
121 | FunHeader
of definition
(* but empty body *)
123 | Decl
of declaration
125 (* ------------------------ *)
126 (* flow_to_ast: cocci: Need the { and } in the control flow graph also
127 * because the coccier can express patterns containing such { }.
129 * ctl: to make possible the forall (AX, A[...]), have to add more than
130 * one node sometimes for the same '}' (one in each CFG path) in the graph.
132 * ctl: Morover, the int in the type is here to indicate to what { }
133 * they correspond. Two pairwise { } share the same number. kind of
134 * "brace_identifier". Used for debugging or for checks and more importantly,
135 * needed by CTL engine.
137 * Because of those nodes, there is no equivalent for Compound.
139 * There was a problem with SeqEnd. Some info can be tagged on it
140 * but there is multiple SeqEnd that correspond to the same '}' even
141 * if they are in different nodes. Solved by using shared ref
142 * and allow the "already-tagged" token.
144 | SeqStart
of fullstatement
* int * info
145 | SeqEnd
of int * info
148 | ExprStatement
of fullstatement
* (expression
option) wrap
151 | IfHeader
of fullstatement
* expression wrap
153 | WhileHeader
of fullstatement
* expression wrap
154 | DoHeader
of fullstatement
* info
155 | DoWhileTail
of expression wrap
156 | ForHeader
of fullstatement
*
157 (exprStatement wrap
* exprStatement wrap
* exprStatement wrap
)
159 | SwitchHeader
of fullstatement
* expression wrap
160 | MacroIterHeader
of fullstatement
* (string * argument wrap2 list
) wrap
162 (* Used to mark the end of if, while, dowhile, for, switch. Later we
163 * will be able to "tag" some cocci code on this node.
169 * the S can be anything, including an if, and this is internally
170 * translated in a series of MetaRuleElem, and the last element is a
171 * EndStatement, and we must tag foo() to this EndStatement.
172 * Otherwise, without this last common node, we would tag foo() to 2
173 * nodes :( So having a unique node makes it correct, and in
174 * flow_to_ast we must propagate back this + foo() to the last token
175 * of an if (maybe a '}', maybe a ';')
177 * The problem is that this stuff should be in transformation.ml,
178 * but need information available in flow_to_ast, but we dont want
179 * to polluate both files.
183 * - soluce julia1, extend Ast_c by adding a fake token to the if
185 * - extend Ast with a Skip, and add this next to EndStatement node,
186 * and do special case in flow_to_ast to start from this node
187 * (not to get_next EndStatement, but from EndStatement directly)
188 * and so add a case when have directly a EndStatement node an extract
189 * the statement from it.
191 * - remonter dans le graphe pour accrocher le foo() non plus au
192 * EndStatement (qui n'a pas d'equivalent niveau token dans l'ast_c),
193 * mais au dernier token de la branche Else (ou Then si y'a pas de else).
195 * I first did solution 2 and then when we decided to use ref,
196 * I use julia'as solution. Have virtual-placeholders, the fakeInfo
197 * for the if, while, and put this shared ref in the EndStatement.
199 | EndStatement
of info
option (* fake_info *)
201 | Return
of fullstatement
* unit wrap
202 | ReturnExpr
of fullstatement
* expression wrap
204 (* ------------------------ *)
205 | IfdefHeader
of ifdef_directive
206 | IfdefElse
of ifdef_directive
207 | IfdefEndif
of ifdef_directive
210 (* ------------------------ *)
211 | DefineHeader
of string wrap
* define_kind
213 | DefineExpr
of expression
214 | DefineType
of fullType
215 | DefineDoWhileZeroHeader
of unit wrap
221 | MacroTop
of string * argument wrap2 list
* il
223 (* ------------------------ *)
224 | Case
of fullstatement
* expression wrap
225 | Default
of fullstatement
* unit wrap
227 | Continue
of fullstatement
* unit wrap
228 | Break
of fullstatement
* unit wrap
230 (* no counter part in cocci *)
231 | CaseRange
of fullstatement
* (expression
* expression
) wrap
232 | Label
of fullstatement
* name
* unit wrap
(* : *)
233 | Goto
of fullstatement
* name
* unit wrap
(* goto *)
236 | Asm
of fullstatement
* asmbody wrap
237 | MacroStmt
of fullstatement
* unit wrap
239 (* ------------------------ *)
240 (* some control nodes *)
245 (* Redundant nodes, often to mark the end of an if/switch.
246 * That makes it easier to do later the flow_to_ast.
247 * update: no more used for the end. see Endstatement. Just used
248 * to mark the start of the function, as required by julia.
249 * Maybe would be better to use instead a Enter2.
253 (* flow_to_ast: In this case, I need to know the order between the children
254 * of the switch in the graph.
258 (* ------------------------ *)
262 | InLoopNode
(* almost equivalent to TrueNode but just for loops *)
269 type edge
= Direct
(* Normal | Shadow *)
271 type cflow
= (node
, edge
) Ograph_extended.ograph_mutable
274 (* ------------------------------------------------------------------------ *)
275 let unwrap ((node
, info
), nodestr
) = node
276 let rewrap ((_node
, info
), nodestr
) node
= (node
, info
), nodestr
277 let extract_labels ((node
, info
), nodestr
) = info
.labels
278 let extract_bclabels ((node
, info
), nodestr
) = info
.bclabels
279 let extract_is_loop ((node
, info
), nodestr
) = info
.is_loop
280 let extract_is_fake ((node
, info
), nodestr
) = info
.is_fake
282 let mk_any_node is_fake node labels bclabels nodestr
=
284 if !Flag_parsing_c.show_flow_labels
285 then nodestr ^
("[" ^
(labels
+> List.map i_to_s
+> join
",") ^
"]")
288 ((node
, {labels
= labels
;is_loop
=false;bclabels
=bclabels
;is_fake
=is_fake
}),
291 let mk_node = mk_any_node false
292 let mk_fake_node = mk_any_node true (* for duplicated braces *)
294 (* ------------------------------------------------------------------------ *)
296 g#nodes#tolist
+> List.find
(fun (i
, node
) ->
297 match unwrap node
with TopNode
-> true | _
-> false
301 g#nodes#tolist
+> List.find
(fun (nodei
, node
) ->
306 (* remove an intermediate node and redirect the connexion *)
307 let remove_one_node nodei g
=
308 let preds = (g#predecessors nodei
)#tolist
in
309 let succs = (g#successors nodei
)#tolist
in
310 assert (not
(null
preds));
312 preds +> List.iter
(fun (predi
, Direct
) ->
313 g#del_arc
((predi
, nodei
), Direct
);
315 succs +> List.iter
(fun (succi
, Direct
) ->
316 g#del_arc
((nodei
, succi
), Direct
);
321 (* connect in-nodes to out-nodes *)
322 preds +> List.iter
(fun (pred
, Direct
) ->
323 succs +> List.iter
(fun (succ
, Direct
) ->
324 g#add_arc
((pred
, succ
), Direct
);
330 (* ------------------------------------------------------------------------ *)
332 let extract_fullstatement node
=
333 match unwrap node
with
335 (* new policy. no more considered as a statement *)
336 (* old: Some (Ast_c.Decl decl, []) *)
338 | MacroStmt
(st
, _
) -> Some st
339 | MacroIterHeader
(st
, _
) -> Some st
342 | DefineHeader _
| DefineType _
| DefineExpr _
| DefineDoWhileZeroHeader _
347 | IfdefHeader _
| IfdefElse _
| IfdefEndif _
351 | ExprStatement
(st
, _
)
353 | WhileHeader
(st
, _
)
356 | SwitchHeader
(st
, _
)
359 (* no counter part in cocci *)