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.
28 module Ast
= Ast_cocci
29 module V
= Visitor_ast
31 let disjmult2 e1 e2 k
=
33 (List.map
(function e1
-> List.map
(function e2
-> k e1 e2
) e2
) e1
)
35 let disjmult3 e1 e2 e3 k
=
41 (function e2
-> List.map
(function e3
-> k e1 e2 e3
) e3
)
45 let rec disjmult f
= function
49 let rest = disjmult f xs
in
50 disjmult2 cur rest (function cur -> function rest -> cur :: rest)
52 let disjoption f
= function
54 | Some x
-> List.map
(function x
-> Some x
) (f x
)
57 match Ast.unwrap d
with
59 List.map
(function l
-> Ast.rewrap d
(Ast.DOTS
(l
))) (disjmult f l
)
61 List.map
(function l
-> Ast.rewrap d
(Ast.CIRCLES
(l
))) (disjmult f l
)
63 List.map
(function l
-> Ast.rewrap d
(Ast.STARS
(l
))) (disjmult f l
)
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 *)
72 List.map
(function ty -> Ast.rewrap ft
(Ast.AsType
(ty,asty
))) ty
73 | Ast.DisjType
(types
) -> List.concat
(List.map
disjty types
)
76 List.map
(function ty -> Ast.rewrap ft
(Ast.OptType
(ty))) ty
77 | Ast.UniqueType
(ty) ->
79 List.map
(function ty -> Ast.rewrap ft
(Ast.UniqueType
(ty))) ty
82 match Ast.unwrap bty
with
83 Ast.BaseType
(_
) | Ast.SignedT
(_
,_
) -> [bty
]
84 | Ast.Pointer
(ty,star
) ->
86 List.map
(function ty -> Ast.rewrap bty
(Ast.Pointer
(ty,star
))) ty
87 | Ast.FunctionPointer
(ty,lp1
,star
,rp1
,lp2
,params
,rp2
) ->
91 Ast.rewrap bty
(Ast.FunctionPointer
(ty,lp1
,star
,rp1
,lp2
,params
,rp2
)))
93 | Ast.FunctionType
(s
,ty,lp1
,params
,rp1
) ->
94 let ty = disjoption disjty ty in
97 Ast.rewrap bty
(Ast.FunctionType
(s
,ty,lp1
,params
,rp1
)))
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
]
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
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
145 Ast.rewrap e
(Ast.CondExpr
(exp1
,why
,Some exp2
,colon
,exp3
))
146 | _
-> failwith
"not possible")
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
179 (function exp -> Ast.rewrap e
(Ast.RecordAccess
(exp,pt
,field
))) exp
180 | Ast.RecordPtAccess
(exp,ar
,field
) ->
181 let exp = disjexp
exp in
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
193 (function ty -> Ast.rewrap e
(Ast.SizeOfType
(szf
,lp
,ty,rp
))) 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
)
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 *)
210 | Ast.Edots
(dots
,_
) | Ast.Ecircles
(dots
,_
) | Ast.Estars
(dots
,_
) -> [e
]
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
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
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
) ->
244 (function initlist
->
245 Ast.rewrap i
(Ast.ArInitList
(lb
,initlist
,rb
)))
246 (disjdots disjini initlist
)
247 | Ast.StrInitList
(allminus
,lb
,initlist
,rb
,whencode
) ->
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
261 (function ini -> Ast.rewrap i
(Ast.InitGccName
(name
,eq
,ini)))
263 | Ast.IComma
(comma
) -> [i
]
264 | Ast.Idots
(dots
,_
) -> [i
]
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
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
))
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
) ->
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
319 let generic_orify_rule_elem f re
exp rebuild
=
322 | orexps
-> Ast.rewrap re
(Ast.DisjRuleElem
(List.map rebuild orexps
))
324 let orify_rule_elem re
exp rebuild
=
325 generic_orify_rule_elem disjexp re
exp rebuild
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
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
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
]
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
379 orify_rule_elem re
exp (function exp -> Ast.rewrap
exp (Ast.Exp
(exp)))
381 orify_rule_elem re
exp (function exp -> Ast.rewrap
exp (Ast.TopExp
(exp)))
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
))
400 let donothing r k e
= k e
in
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
407 (* ----------------------------------------------------------------------- *)
408 (* collect iso information at the rule_elem level *)
410 let collect_all_isos =
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
422 let collect_iso_info =
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
429 let isos = collect_all_isos.V.combiner_rule_elem e
in
430 Ast.set_isos e
isos in
432 mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode
433 donothing donothing donothing donothing donothing donothing donothing
435 donothing donothing donothing donothing rule_elem donothing donothing
438 (* ----------------------------------------------------------------------- *)
445 | Ast.InitialScriptRule _
| Ast.FinalScriptRule _
-> (mv
, r
)
446 | Ast.CocciRule
(nm
, rule_info
, r
, isexp
, ruletype
) ->
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
455 (mv
, Ast.CocciRule
(nm
,rule_info
,res,isexp
,ruletype
)))