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