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.
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.
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.
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/>.
22 * The authors reserve the right to distribute this or future versions of
23 * Coccinelle under other licenses.
27 module Ast
= Ast_cocci
28 module V
= Visitor_ast
30 let disjmult2 e1 e2 k
=
32 (List.map
(function e1
-> List.map
(function e2
-> k e1 e2
) e2
) e1
)
34 let disjmult3 e1 e2 e3 k
=
40 (function e2
-> List.map
(function e3
-> k e1 e2 e3
) e3
)
44 let rec disjmult f
= function
48 let rest = disjmult f xs
in
49 disjmult2 cur rest (function cur -> function rest -> cur :: rest)
51 let disjoption f
= function
53 | Some x
-> List.map
(function x
-> Some x
) (f x
)
56 match Ast.unwrap d
with
58 List.map
(function l
-> Ast.rewrap d
(Ast.DOTS
(l
))) (disjmult f l
)
60 List.map
(function l
-> Ast.rewrap d
(Ast.CIRCLES
(l
))) (disjmult f l
)
62 List.map
(function l
-> Ast.rewrap d
(Ast.STARS
(l
))) (disjmult f l
)
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 *)
71 List.map
(function ty -> Ast.rewrap ft
(Ast.AsType
(ty,asty
))) ty
72 | Ast.DisjType
(types
) -> List.concat
(List.map
disjty types
)
75 List.map
(function ty -> Ast.rewrap ft
(Ast.OptType
(ty))) ty
76 | Ast.UniqueType
(ty) ->
78 List.map
(function ty -> Ast.rewrap ft
(Ast.UniqueType
(ty))) ty
81 match Ast.unwrap bty
with
82 Ast.BaseType
(_
) | Ast.SignedT
(_
,_
) -> [bty
]
83 | Ast.Pointer
(ty,star
) ->
85 List.map
(function ty -> Ast.rewrap bty
(Ast.Pointer
(ty,star
))) ty
86 | Ast.FunctionPointer
(ty,lp1
,star
,rp1
,lp2
,params
,rp2
) ->
90 Ast.rewrap bty
(Ast.FunctionPointer
(ty,lp1
,star
,rp1
,lp2
,params
,rp2
)))
92 | Ast.FunctionType
(s
,ty,lp1
,params
,rp1
) ->
93 let ty = disjoption disjty ty in
96 Ast.rewrap bty
(Ast.FunctionType
(s
,ty,lp1
,params
,rp1
)))
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
]
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
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
144 Ast.rewrap e
(Ast.CondExpr
(exp1
,why
,Some exp2
,colon
,exp3
))
145 | _
-> failwith
"not possible")
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
178 (function exp -> Ast.rewrap e
(Ast.RecordAccess
(exp,pt
,field
))) exp
179 | Ast.RecordPtAccess
(exp,ar
,field
) ->
180 let exp = disjexp
exp in
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
192 (function ty -> Ast.rewrap e
(Ast.SizeOfType
(szf
,lp
,ty,rp
))) 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
)
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 *)
209 | Ast.Edots
(dots
,_
) | Ast.Ecircles
(dots
,_
) | Ast.Estars
(dots
,_
) -> [e
]
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
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
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
) ->
243 (function initlist
->
244 Ast.rewrap i
(Ast.ArInitList
(lb
,initlist
,rb
)))
245 (disjdots disjini initlist
)
246 | Ast.StrInitList
(allminus
,lb
,initlist
,rb
,whencode
) ->
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
260 (function ini -> Ast.rewrap i
(Ast.InitGccName
(name
,eq
,ini)))
262 | Ast.IComma
(comma
) -> [i
]
263 | Ast.Idots
(dots
,_
) -> [i
]
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
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
))
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
) ->
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
318 let generic_orify_rule_elem f re
exp rebuild
=
321 | orexps
-> Ast.rewrap re
(Ast.DisjRuleElem
(List.map rebuild orexps
))
323 let orify_rule_elem re
exp rebuild
=
324 generic_orify_rule_elem disjexp re
exp rebuild
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
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
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
]
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
378 orify_rule_elem re
exp (function exp -> Ast.rewrap
exp (Ast.Exp
(exp)))
380 orify_rule_elem re
exp (function exp -> Ast.rewrap
exp (Ast.TopExp
(exp)))
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
))
399 let donothing r k e
= k e
in
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
406 (* ----------------------------------------------------------------------- *)
407 (* collect iso information at the rule_elem level *)
409 let collect_all_isos =
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
421 let collect_iso_info =
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
428 let isos = collect_all_isos.V.combiner_rule_elem e
in
429 Ast.set_isos e
isos in
431 mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode
432 donothing donothing donothing donothing donothing donothing donothing
434 donothing donothing donothing donothing rule_elem donothing donothing
437 (* ----------------------------------------------------------------------- *)
444 | Ast.InitialScriptRule _
| Ast.FinalScriptRule _
-> (mv
, r
)
445 | Ast.CocciRule
(nm
, rule_info
, r
, isexp
, ruletype
) ->
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
454 (mv
, Ast.CocciRule
(nm
,rule_info
,res,isexp
,ruletype
)))