Coccinelle release-1.0.0-rc11
[bpt/coccinelle.git] / parsing_cocci / disjdistr.ml
1 (*
2 * Copyright 2012, INRIA
3 * Julia Lawall, Gilles Muller
4 * Copyright 2010-2011, INRIA, University of Copenhagen
5 * Julia Lawall, Rene Rydhof Hansen, Gilles Muller, Nicolas Palix
6 * Copyright 2005-2009, Ecole des Mines de Nantes, University of Copenhagen
7 * Yoann Padioleau, Julia Lawall, Rene Rydhof Hansen, Henrik Stuart, Gilles Muller, Nicolas Palix
8 * This file is part of Coccinelle.
9 *
10 * Coccinelle is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, according to version 2 of the License.
13 *
14 * Coccinelle is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with Coccinelle. If not, see <http://www.gnu.org/licenses/>.
21 *
22 * The authors reserve the right to distribute this or future versions of
23 * Coccinelle under other licenses.
24 *)
25
26
27 module Ast = Ast_cocci
28 module V = Visitor_ast
29
30 let disjmult2 e1 e2 k =
31 List.concat
32 (List.map (function e1 -> List.map (function e2 -> k e1 e2) e2) e1)
33
34 let disjmult3 e1 e2 e3 k =
35 List.concat
36 (List.map
37 (function e1 ->
38 List.concat
39 (List.map
40 (function e2 -> List.map (function e3 -> k e1 e2 e3) e3)
41 e2))
42 e1)
43
44 let rec disjmult f = function
45 [] -> [[]]
46 | x::xs ->
47 let cur = f x in
48 let rest = disjmult f xs in
49 disjmult2 cur rest (function cur -> function rest -> cur :: rest)
50
51 let disjoption f = function
52 None -> [None]
53 | Some x -> List.map (function x -> Some x) (f x)
54
55 let disjdots f d =
56 match Ast.unwrap d with
57 Ast.DOTS(l) ->
58 List.map (function l -> Ast.rewrap d (Ast.DOTS(l))) (disjmult f l)
59 | Ast.CIRCLES(l) ->
60 List.map (function l -> Ast.rewrap d (Ast.CIRCLES(l))) (disjmult f l)
61 | Ast.STARS(l) ->
62 List.map (function l -> Ast.rewrap d (Ast.STARS(l))) (disjmult f l)
63
64 let rec disjty ft =
65 match Ast.unwrap ft with
66 Ast.Type(allminus,cv,ty) ->
67 let ty = disjtypeC ty in
68 List.map (function ty -> Ast.rewrap ft (Ast.Type(allminus,cv,ty))) ty
69 | Ast.AsType(ty,asty) -> (* as ty doesn't contain disj *)
70 let ty = disjty ty in
71 List.map (function ty -> Ast.rewrap ft (Ast.AsType(ty,asty))) ty
72 | Ast.DisjType(types) -> List.concat (List.map disjty types)
73 | Ast.OptType(ty) ->
74 let ty = disjty ty in
75 List.map (function ty -> Ast.rewrap ft (Ast.OptType(ty))) ty
76 | Ast.UniqueType(ty) ->
77 let ty = disjty ty in
78 List.map (function ty -> Ast.rewrap ft (Ast.UniqueType(ty))) ty
79
80 and disjtypeC bty =
81 match Ast.unwrap bty with
82 Ast.BaseType(_) | Ast.SignedT(_,_) -> [bty]
83 | Ast.Pointer(ty,star) ->
84 let ty = disjty ty in
85 List.map (function ty -> Ast.rewrap bty (Ast.Pointer(ty,star))) ty
86 | Ast.FunctionPointer(ty,lp1,star,rp1,lp2,params,rp2) ->
87 let ty = disjty ty in
88 List.map
89 (function ty ->
90 Ast.rewrap bty (Ast.FunctionPointer(ty,lp1,star,rp1,lp2,params,rp2)))
91 ty
92 | Ast.FunctionType (s,ty,lp1,params,rp1) ->
93 let ty = disjoption disjty ty in
94 List.map
95 (function ty ->
96 Ast.rewrap bty (Ast.FunctionType (s,ty,lp1,params,rp1)))
97 ty
98 | Ast.Array(ty,lb,size,rb) ->
99 disjmult2 (disjty ty) (disjoption disjexp size)
100 (function ty -> function size ->
101 Ast.rewrap bty (Ast.Array(ty,lb,size,rb)))
102 | Ast.EnumName(_,_) | Ast.StructUnionName(_,_) -> [bty]
103 | Ast.EnumDef(ty,lb,ids,rb) ->
104 disjmult2 (disjty ty) (disjdots disjexp ids)
105 (function ty -> function ids ->
106 Ast.rewrap bty (Ast.EnumDef(ty,lb,ids,rb)))
107 | Ast.StructUnionDef(ty,lb,decls,rb) ->
108 disjmult2 (disjty ty) (disjdots disjdecl decls)
109 (function ty -> function decls ->
110 Ast.rewrap bty (Ast.StructUnionDef(ty,lb,decls,rb)))
111 | Ast.TypeName(_) | Ast.MetaType(_,_,_) -> [bty]
112
113 and disjident e =
114 match Ast.unwrap e with
115 Ast.DisjId(id_list) -> List.concat (List.map disjident id_list)
116 | Ast.OptIdent(id) ->
117 let id = disjident id in
118 List.map (function id -> Ast.rewrap e (Ast.OptIdent(id))) id
119 | Ast.UniqueIdent(id) ->
120 let id = disjident id in
121 List.map (function id -> Ast.rewrap e (Ast.UniqueIdent(id))) id
122 | _ -> [e]
123
124 and disjexp e =
125 match Ast.unwrap e with
126 Ast.Ident(_) | Ast.Constant(_) -> [e] (* even Ident can't contain disj *)
127 | Ast.FunCall(fn,lp,args,rp) ->
128 disjmult2 (disjexp fn) (disjdots disjexp args)
129 (function fn -> function args ->
130 Ast.rewrap e (Ast.FunCall(fn,lp,args,rp)))
131 | Ast.Assignment(left,op,right,simple) ->
132 disjmult2 (disjexp left) (disjexp right)
133 (function left -> function right ->
134 Ast.rewrap e (Ast.Assignment(left,op,right,simple)))
135 | Ast.Sequence(left,op,right) ->
136 disjmult2 (disjexp left) (disjexp right)
137 (function left -> function right ->
138 Ast.rewrap e (Ast.Sequence(left,op,right)))
139 | Ast.CondExpr(exp1,why,Some exp2,colon,exp3) ->
140 let res = disjmult disjexp [exp1;exp2;exp3] in
141 List.map
142 (function
143 [exp1;exp2;exp3] ->
144 Ast.rewrap e (Ast.CondExpr(exp1,why,Some exp2,colon,exp3))
145 | _ -> failwith "not possible")
146 res
147 | Ast.CondExpr(exp1,why,None,colon,exp3) ->
148 disjmult2 (disjexp exp1) (disjexp exp3)
149 (function exp1 -> function exp3 ->
150 Ast.rewrap e (Ast.CondExpr(exp1,why,None,colon,exp3)))
151 | Ast.Postfix(exp,op) ->
152 let exp = disjexp exp in
153 List.map (function exp -> Ast.rewrap e (Ast.Postfix(exp,op))) exp
154 | Ast.Infix(exp,op) ->
155 let exp = disjexp exp in
156 List.map (function exp -> Ast.rewrap e (Ast.Infix(exp,op))) exp
157 | Ast.Unary(exp,op) ->
158 let exp = disjexp exp in
159 List.map (function exp -> Ast.rewrap e (Ast.Unary(exp,op))) exp
160 | Ast.Binary(left,op,right) ->
161 disjmult2 (disjexp left) (disjexp right)
162 (function left -> function right ->
163 Ast.rewrap e (Ast.Binary(left,op,right)))
164 | Ast.Nested(exp,op,right) ->
165 (* disj not possible in right *)
166 let exp = disjexp exp in
167 List.map (function exp -> Ast.rewrap e (Ast.Nested(exp,op,right))) exp
168 | Ast.Paren(lp,exp,rp) ->
169 let exp = disjexp exp in
170 List.map (function exp -> Ast.rewrap e (Ast.Paren(lp,exp,rp))) exp
171 | Ast.ArrayAccess(exp1,lb,exp2,rb) ->
172 disjmult2 (disjexp exp1) (disjexp exp2)
173 (function exp1 -> function exp2 ->
174 Ast.rewrap e (Ast.ArrayAccess(exp1,lb,exp2,rb)))
175 | Ast.RecordAccess(exp,pt,field) ->
176 let exp = disjexp exp in
177 List.map
178 (function exp -> Ast.rewrap e (Ast.RecordAccess(exp,pt,field))) exp
179 | Ast.RecordPtAccess(exp,ar,field) ->
180 let exp = disjexp exp in
181 List.map
182 (function exp -> Ast.rewrap e (Ast.RecordPtAccess(exp,ar,field))) exp
183 | Ast.Cast(lp,ty,rp,exp) ->
184 disjmult2 (disjty ty) (disjexp exp)
185 (function ty -> function exp -> Ast.rewrap e (Ast.Cast(lp,ty,rp,exp)))
186 | Ast.SizeOfExpr(szf,exp) ->
187 let exp = disjexp exp in
188 List.map (function exp -> Ast.rewrap e (Ast.SizeOfExpr(szf,exp))) exp
189 | Ast.SizeOfType(szf,lp,ty,rp) ->
190 let ty = disjty ty in
191 List.map
192 (function ty -> Ast.rewrap e (Ast.SizeOfType(szf,lp,ty,rp))) ty
193 | Ast.TypeExp(ty) ->
194 let ty = disjty ty in
195 List.map (function ty -> Ast.rewrap e (Ast.TypeExp(ty))) ty
196 | Ast.Constructor(lp,ty,rp,init) ->
197 disjmult2 (disjty ty) (disjini init)
198 (function ty ->
199 function exp -> Ast.rewrap e (Ast.Constructor(lp,ty,rp,init)))
200 | Ast.MetaErr(_,_,_,_) | Ast.MetaExpr(_,_,_,_,_,_)
201 | Ast.MetaExprList(_,_,_,_) | Ast.EComma(_) -> [e]
202 | Ast.AsExpr(exp,asexp) -> (* as exp doesn't contain disj *)
203 let exp = disjexp exp in
204 List.map (function exp -> Ast.rewrap e (Ast.AsExpr(exp,asexp))) exp
205 | Ast.DisjExpr(exp_list) -> List.concat (List.map disjexp exp_list)
206 | Ast.NestExpr(starter,expr_dots,ender,whencode,multi) ->
207 (* not sure what to do here, so ambiguities still possible *)
208 [e]
209 | Ast.Edots(dots,_) | Ast.Ecircles(dots,_) | Ast.Estars(dots,_) -> [e]
210 | Ast.OptExp(exp) ->
211 let exp = disjexp exp in
212 List.map (function exp -> Ast.rewrap e (Ast.OptExp(exp))) exp
213 | Ast.UniqueExp(exp) ->
214 let exp = disjexp exp in
215 List.map (function exp -> Ast.rewrap e (Ast.UniqueExp(exp))) exp
216
217 and disjparam p =
218 match Ast.unwrap p with
219 Ast.VoidParam(ty) -> [p] (* void is the only possible value *)
220 | Ast.Param(ty,id) ->
221 let ty = disjty ty in
222 List.map (function ty -> Ast.rewrap p (Ast.Param(ty,id))) ty
223 | Ast.MetaParam(_,_,_) | Ast.MetaParamList(_,_,_,_) | Ast.PComma(_) -> [p]
224 | Ast.Pdots(dots) | Ast.Pcircles(dots) -> [p]
225 | Ast.OptParam(param) ->
226 let param = disjparam param in
227 List.map (function param -> Ast.rewrap p (Ast.OptParam(param))) param
228 | Ast.UniqueParam(param) ->
229 let param = disjparam param in
230 List.map (function param -> Ast.rewrap p (Ast.UniqueParam(param))) param
231
232 and disjini i =
233 match Ast.unwrap i with
234 Ast.MetaInit(_,_,_) | Ast.MetaInitList(_,_,_,_) -> [i]
235 | Ast.AsInit(ini,asini) ->
236 let ini = disjini ini in
237 List.map (function ini -> Ast.rewrap i (Ast.AsInit(ini,asini))) ini
238 | Ast.InitExpr(exp) ->
239 let exp = disjexp exp in
240 List.map (function exp -> Ast.rewrap i (Ast.InitExpr(exp))) exp
241 | Ast.ArInitList(lb,initlist,rb) ->
242 List.map
243 (function initlist ->
244 Ast.rewrap i (Ast.ArInitList(lb,initlist,rb)))
245 (disjdots disjini initlist)
246 | Ast.StrInitList(allminus,lb,initlist,rb,whencode) ->
247 List.map
248 (function initlist ->
249 Ast.rewrap i (Ast.StrInitList(allminus,lb,initlist,rb,whencode)))
250 (disjmult disjini initlist)
251 | Ast.InitGccExt(designators,eq,ini) ->
252 let designators = disjmult designator designators in
253 let ini = disjini ini in
254 disjmult2 designators ini
255 (function designators -> function ini ->
256 Ast.rewrap i (Ast.InitGccExt(designators,eq,ini)))
257 | Ast.InitGccName(name,eq,ini) ->
258 let ini = disjini ini in
259 List.map
260 (function ini -> Ast.rewrap i (Ast.InitGccName(name,eq,ini)))
261 ini
262 | Ast.IComma(comma) -> [i]
263 | Ast.Idots(dots,_) -> [i]
264 | Ast.OptIni(ini) ->
265 let ini = disjini ini in
266 List.map (function ini -> Ast.rewrap i (Ast.OptIni(ini))) ini
267 | Ast.UniqueIni(ini) ->
268 let ini = disjini ini in
269 List.map (function ini -> Ast.rewrap i (Ast.UniqueIni(ini))) ini
270
271 and designator = function
272 Ast.DesignatorField(dot,id) -> [Ast.DesignatorField(dot,id)]
273 | Ast.DesignatorIndex(lb,exp,rb) ->
274 let exp = disjexp exp in
275 List.map (function exp -> Ast.DesignatorIndex(lb,exp,rb)) exp
276 | Ast.DesignatorRange(lb,min,dots,max,rb) ->
277 disjmult2 (disjexp min) (disjexp max)
278 (function min -> function max ->
279 Ast.DesignatorRange(lb,min,dots,max,rb))
280
281 and disjdecl d =
282 match Ast.unwrap d with
283 Ast.MetaDecl(_,_,_) | Ast.MetaField(_,_,_)
284 | Ast.MetaFieldList(_,_,_,_) -> [d]
285 | Ast.AsDecl(decl,asdecl) ->
286 let decl = disjdecl decl in
287 List.map (function decl -> Ast.rewrap d (Ast.AsDecl(decl,asdecl))) decl
288 | Ast.Init(stg,ty,id,eq,ini,sem) ->
289 disjmult2 (disjty ty) (disjini ini)
290 (function ty -> function ini ->
291 Ast.rewrap d (Ast.Init(stg,ty,id,eq,ini,sem)))
292 | Ast.UnInit(stg,ty,id,sem) ->
293 let ty = disjty ty in
294 List.map (function ty -> Ast.rewrap d (Ast.UnInit(stg,ty,id,sem))) ty
295 | Ast.MacroDecl(name,lp,args,rp,sem) ->
296 List.map
297 (function args -> Ast.rewrap d (Ast.MacroDecl(name,lp,args,rp,sem)))
298 (disjdots disjexp args)
299 | Ast.MacroDeclInit(name,lp,args,rp,eq,ini,sem) ->
300 disjmult2 (disjdots disjexp args) (disjini ini)
301 (function args -> function ini ->
302 Ast.rewrap d (Ast.MacroDeclInit(name,lp,args,rp,eq,ini,sem)))
303 | Ast.TyDecl(ty,sem) ->
304 let ty = disjty ty in
305 List.map (function ty -> Ast.rewrap d (Ast.TyDecl(ty,sem))) ty
306 | Ast.Typedef(stg,ty,id,sem) ->
307 let ty = disjty ty in (* disj not allowed in id *)
308 List.map (function ty -> Ast.rewrap d (Ast.Typedef(stg,ty,id,sem))) ty
309 | Ast.DisjDecl(decls) -> List.concat (List.map disjdecl decls)
310 | Ast.Ddots(_,_) -> [d]
311 | Ast.OptDecl(decl) ->
312 let decl = disjdecl decl in
313 List.map (function decl -> Ast.rewrap d (Ast.OptDecl(decl))) decl
314 | Ast.UniqueDecl(decl) ->
315 let decl = disjdecl decl in
316 List.map (function decl -> Ast.rewrap d (Ast.UniqueDecl(decl))) decl
317
318 let generic_orify_rule_elem f re exp rebuild =
319 match f exp with
320 [exp] -> re
321 | orexps -> Ast.rewrap re (Ast.DisjRuleElem (List.map rebuild orexps))
322
323 let orify_rule_elem re exp rebuild =
324 generic_orify_rule_elem disjexp re exp rebuild
325
326 let orify_rule_elem_ty = generic_orify_rule_elem disjty
327 let orify_rule_elem_param = generic_orify_rule_elem disjparam
328 let orify_rule_elem_decl = generic_orify_rule_elem disjdecl
329 let orify_rule_elem_ini = generic_orify_rule_elem disjini
330
331 let rec disj_rule_elem r k re =
332 match Ast.unwrap re with
333 Ast.FunHeader(bef,allminus,fninfo,name,lp,params,rp) ->
334 generic_orify_rule_elem (disjdots disjparam) re params
335 (function params ->
336 Ast.rewrap re
337 (Ast.FunHeader(bef,allminus,fninfo,name,lp,params,rp)))
338 | Ast.Decl(bef,allminus,decl) ->
339 orify_rule_elem_decl re decl
340 (function decl -> Ast.rewrap re (Ast.Decl(bef,allminus,decl)))
341 | Ast.SeqStart(brace) -> re
342 | Ast.SeqEnd(brace) -> re
343 | Ast.ExprStatement(Some exp,sem) ->
344 orify_rule_elem re exp
345 (function exp -> Ast.rewrap re (Ast.ExprStatement(Some exp,sem)))
346 | Ast.ExprStatement(None,sem) -> re
347 | Ast.IfHeader(iff,lp,exp,rp) ->
348 orify_rule_elem re exp
349 (function exp -> Ast.rewrap re (Ast.IfHeader(iff,lp,exp,rp)))
350 | Ast.Else(els) -> re
351 | Ast.WhileHeader(whl,lp,exp,rp) ->
352 orify_rule_elem re exp
353 (function exp -> Ast.rewrap re (Ast.WhileHeader(whl,lp,exp,rp)))
354 | Ast.DoHeader(d) -> re
355 | Ast.WhileTail(whl,lp,exp,rp,sem) ->
356 orify_rule_elem re exp
357 (function exp -> Ast.rewrap re (Ast.WhileTail(whl,lp,exp,rp,sem)))
358 | Ast.ForHeader(fr,lp,e1,sem1,e2,sem2,e3,rp) ->
359 generic_orify_rule_elem (disjmult (disjoption disjexp)) re [e1;e2;e3]
360 (function
361 [exp1;exp2;exp3] ->
362 Ast.rewrap re (Ast.ForHeader(fr,lp,exp1,sem1,exp2,sem2,exp3,rp))
363 | _ -> failwith "not possible")
364 | Ast.IteratorHeader(whl,lp,args,rp) ->
365 generic_orify_rule_elem (disjdots disjexp) re args
366 (function args -> Ast.rewrap re (Ast.IteratorHeader(whl,lp,args,rp)))
367 | Ast.SwitchHeader(switch,lp,exp,rp) ->
368 orify_rule_elem re exp
369 (function exp -> Ast.rewrap re (Ast.SwitchHeader(switch,lp,exp,rp)))
370 | Ast.Break(_,_) | Ast.Continue(_,_) | Ast.Label(_,_) | Ast.Goto(_,_,_)
371 | Ast.Return(_,_) -> re
372 | Ast.ReturnExpr(ret,exp,sem) ->
373 orify_rule_elem re exp
374 (function exp -> Ast.rewrap re (Ast.ReturnExpr(ret,exp,sem)))
375 | Ast.MetaRuleElem(_,_,_) | Ast.MetaStmt(_,_,_,_)
376 | Ast.MetaStmtList(_,_,_) -> re
377 | Ast.Exp(exp) ->
378 orify_rule_elem re exp (function exp -> Ast.rewrap exp (Ast.Exp(exp)))
379 | Ast.TopExp(exp) ->
380 orify_rule_elem re exp (function exp -> Ast.rewrap exp (Ast.TopExp(exp)))
381 | Ast.Ty(ty) ->
382 orify_rule_elem_ty re ty (function ty -> Ast.rewrap ty (Ast.Ty(ty)))
383 | Ast.TopInit(init) ->
384 orify_rule_elem_ini re init
385 (function init -> Ast.rewrap init (Ast.TopInit(init)))
386 | Ast.Include(inc,s) -> re
387 | Ast.Undef(def,id) -> re
388 | Ast.DefineHeader(def,id,params) -> re
389 | Ast.Default(def,colon) -> re
390 | Ast.Case(case,exp,colon) ->
391 orify_rule_elem re exp
392 (function exp -> Ast.rewrap re (Ast.Case(case,exp,colon)))
393 | Ast.DisjRuleElem(l) ->
394 (* only case lines *)
395 Ast.rewrap re(Ast.DisjRuleElem(List.map (disj_rule_elem r k) l))
396
397 let disj_all =
398 let mcode x = x in
399 let donothing r k e = k e in
400 V.rebuilder
401 mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode
402 donothing donothing donothing donothing donothing
403 donothing donothing donothing donothing donothing donothing donothing
404 disj_rule_elem donothing donothing donothing donothing
405
406 (* ----------------------------------------------------------------------- *)
407 (* collect iso information at the rule_elem level *)
408
409 let collect_all_isos =
410 let bind = (@) in
411 let option_default = [] in
412 let mcode r x = [] in
413 let donothing r k e = Common.union_set (Ast.get_isos e) (k e) in
414 let doanything r k e = k e in
415 V.combiner bind option_default
416 mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode
417 donothing donothing donothing donothing donothing donothing donothing
418 donothing donothing donothing donothing donothing donothing donothing
419 donothing donothing doanything
420
421 let collect_iso_info =
422 let mcode x = x in
423 let donothing r k e = k e in
424 let rule_elem r k e =
425 match Ast.unwrap e with
426 Ast.DisjRuleElem(l) -> k e
427 | _ ->
428 let isos = collect_all_isos.V.combiner_rule_elem e in
429 Ast.set_isos e isos in
430 V.rebuilder
431 mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode
432 donothing donothing donothing donothing donothing donothing donothing
433 donothing
434 donothing donothing donothing donothing rule_elem donothing donothing
435 donothing donothing
436
437 (* ----------------------------------------------------------------------- *)
438
439 let disj rules =
440 List.map
441 (function (mv,r) ->
442 match r with
443 Ast.ScriptRule _
444 | Ast.InitialScriptRule _ | Ast.FinalScriptRule _ -> (mv, r)
445 | Ast.CocciRule (nm, rule_info, r, isexp, ruletype) ->
446 let res =
447 List.map
448 (function x ->
449 let res = disj_all.V.rebuilder_top_level x in
450 if !Flag.track_iso_usage
451 then collect_iso_info.V.rebuilder_top_level res
452 else res)
453 r in
454 (mv, Ast.CocciRule (nm,rule_info,res,isexp,ruletype)))
455 rules