Commit | Line | Data |
---|---|---|
f537ebc4 | 1 | (* |
17ba0788 C |
2 | * Copyright 2012, INRIA |
3 | * Julia Lawall, Gilles Muller | |
4 | * Copyright 2010-2011, INRIA, University of Copenhagen | |
f537ebc4 C |
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 | ||
d6ce1786 C |
27 | # 0 "./get_constants2.ml" |
28 | (* | |
29 | * Copyright 2012, INRIA | |
30 | * Julia Lawall, Gilles Muller | |
31 | * Copyright 2010-2011, INRIA, University of Copenhagen | |
32 | * Julia Lawall, Rene Rydhof Hansen, Gilles Muller, Nicolas Palix | |
33 | * Copyright 2005-2009, Ecole des Mines de Nantes, University of Copenhagen | |
34 | * Yoann Padioleau, Julia Lawall, Rene Rydhof Hansen, Henrik Stuart, Gilles Muller, Nicolas Palix | |
35 | * This file is part of Coccinelle. | |
36 | * | |
37 | * Coccinelle is free software: you can redistribute it and/or modify | |
38 | * it under the terms of the GNU General Public License as published by | |
39 | * the Free Software Foundation, according to version 2 of the License. | |
40 | * | |
41 | * Coccinelle is distributed in the hope that it will be useful, | |
42 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
43 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
44 | * GNU General Public License for more details. | |
45 | * | |
46 | * You should have received a copy of the GNU General Public License | |
47 | * along with Coccinelle. If not, see <http://www.gnu.org/licenses/>. | |
48 | * | |
49 | * The authors reserve the right to distribute this or future versions of | |
50 | * Coccinelle under other licenses. | |
51 | *) | |
52 | ||
53 | ||
feec80c3 | 54 | # 0 "./get_constants2.ml" |
34e49164 C |
55 | module Ast = Ast_cocci |
56 | module V = Visitor_ast | |
57 | module TC = Type_cocci | |
58 | ||
59 | (* Issues: | |
60 | ||
61 | 1. If a rule X depends on a rule Y (in a positive way), then we can ignore | |
62 | the constants in X. | |
63 | ||
64 | 2. If a rule X contains a metavariable that is not under a disjunction and | |
65 | that is inherited from rule Y, then we can ignore the constants in X. | |
66 | ||
67 | 3. If a rule contains a constant x in + code then subsequent rules that | |
68 | have it in - or context should not include it in their list of required | |
69 | constants. | |
70 | *) | |
71 | ||
90aeb998 C |
72 | (* This doesn't do the . -> trick of get_constants for record fields, as |
73 | that does not fit well with the recursive structure. It was not clear | |
74 | that that was completely safe either, although eg putting a newline | |
75 | after the . or -> is probably unusual. *) | |
76 | ||
34e49164 C |
77 | (* ----------------------------------------------------------------------- *) |
78 | (* This phase collects everything. One can then filter out what it not | |
79 | wanted *) | |
80 | ||
81 | (* True means nothing was found | |
82 | False should never drift to the top, it is the neutral element of or | |
83 | and an or is never empty *) | |
84 | type combine = | |
85 | And of combine list | Or of combine list | Elem of string | False | True | |
86 | ||
d6ce1786 C |
87 | let rec dep2c = function |
88 | And l -> Printf.sprintf "(%s)" (String.concat "&" (List.map dep2c l)) | |
89 | | Or l -> Printf.sprintf "(%s)" (String.concat "|" (List.map dep2c l)) | |
90 | | Elem x -> x | |
91 | | False -> "false" | |
92 | | True -> "true" | |
93 | ||
413ffc02 C |
94 | (* glimpse often fails on large queries. We can safely remove arguments of |
95 | && as long as we don't remove all of them (note that there is no negation). | |
96 | This tries just removing one of them and then orders the results by | |
97 | increasing number of ors (ors are long, increasing the chance of failure, | |
98 | and are less restrictive, possibly increasing the chance of irrelevant | |
99 | code. *) | |
100 | let reduce_glimpse x = | |
101 | let rec loop x k q = | |
102 | match x with | |
103 | Elem _ -> q() | |
104 | | And [x] -> loop x (function changed_l -> k (And [changed_l])) q | |
105 | | And l -> | |
106 | kloop l | |
107 | (function changed_l -> k (And changed_l)) | |
108 | (function _ -> | |
109 | let rec rloop l k = | |
110 | match l with | |
111 | [] -> q() | |
112 | | x::xs -> | |
113 | (k xs) :: | |
114 | rloop xs (function changed_xs -> k (x :: changed_xs)) in | |
115 | rloop l (function changed_l -> k (And changed_l))) | |
116 | | Or l -> kloop l (function changed_l -> k (Or changed_l)) q | |
117 | | _ -> failwith "not possible" | |
118 | and kloop l k q = | |
119 | match l with | |
120 | [] -> q() | |
121 | | x::xs -> | |
122 | loop x | |
123 | (function changed_x -> k (changed_x::xs)) | |
124 | (function _ -> | |
125 | kloop xs | |
126 | (function changed_xs -> k (x :: changed_xs)) | |
127 | q) in | |
128 | let rec count_ors = function | |
129 | Elem _ -> 0 | |
130 | | And l -> List.fold_left (+) 0 (List.map count_ors l) | |
131 | | Or l -> | |
132 | ((List.length l) - 1) + | |
133 | (List.fold_left (+) 0 (List.map count_ors l)) | |
134 | | _ -> failwith "not possible" in | |
135 | let res = loop x (function x -> x) (function _ -> []) in | |
136 | let res = List.map (function x -> (count_ors x,x)) res in | |
137 | let res = List.sort compare res in | |
138 | List.map (function (_,x) -> x) res | |
139 | ||
951c7801 | 140 | let interpret_glimpse strict x = |
34e49164 C |
141 | let rec loop = function |
142 | Elem x -> x | |
143 | | And [x] -> loop x | |
144 | | Or [x] -> loop x | |
145 | | And l -> Printf.sprintf "{%s}" (String.concat ";" (List.map loop l)) | |
146 | | Or l -> Printf.sprintf "{%s}" (String.concat "," (List.map loop l)) | |
90aeb998 C |
147 | | True -> |
148 | if strict | |
149 | then failwith "True should not be in the final result" | |
150 | else "True" | |
34e49164 C |
151 | | False -> |
152 | if strict | |
153 | then failwith "False should not be in the final result. Perhaps your rule doesn't contain any +/-/* code" | |
154 | else "False" in | |
155 | match x with | |
156 | True -> None | |
157 | | False when strict -> | |
158 | failwith "False should not be in the final result. Perhaps your rule doesn't contain any +/-/* code" | |
413ffc02 C |
159 | | _ -> |
160 | Some (if strict then List.map loop (x::reduce_glimpse x) else [loop x]) | |
951c7801 | 161 | |
90aeb998 C |
162 | (* grep only does or *) |
163 | let interpret_grep strict x = | |
164 | let rec loop = function | |
165 | Elem x -> [x] | |
166 | | And l -> List.concat (List.map loop l) | |
167 | | Or l -> List.concat (List.map loop l) | |
168 | | True -> | |
169 | if strict | |
170 | then failwith "True should not be in the final result" | |
171 | else ["True"] | |
172 | | False -> | |
173 | if strict | |
174 | then failwith "False should not be in the final result. Perhaps your rule doesn't contain any +/-/* code" | |
175 | else ["False"] in | |
176 | match x with | |
177 | True -> None | |
178 | | False when strict -> | |
179 | failwith "False should not be in the final result. Perhaps your rule doesn't contain any +/-/* code" | |
180 | | _ -> Some (loop x) | |
181 | ||
951c7801 C |
182 | let interpret_google strict x = |
183 | (* convert to dnf *) | |
184 | let rec dnf = function | |
185 | Elem x -> [x] | |
186 | | Or l -> List.fold_left Common.union_set [] (List.map dnf l) | |
187 | | And l -> | |
188 | let l = List.map dnf l in | |
189 | List.fold_left | |
190 | (function prev -> | |
191 | function cur -> | |
192 | List.fold_left Common.union_set [] | |
193 | (List.map | |
194 | (function x -> | |
195 | List.map (function y -> Printf.sprintf "%s %s" x y) prev) | |
196 | cur)) | |
197 | [] l | |
198 | | True -> ["True"] | |
199 | | False -> | |
200 | if strict | |
201 | then failwith "False should not be in the final result. Perhaps your rule doesn't contain any +/-/* code" | |
202 | else ["False"] in | |
203 | match x with | |
204 | True -> None | |
205 | | False when strict -> | |
206 | failwith "False should not be in the final result. Perhaps your rule doesn't contain any +/-/* code" | |
207 | | _ -> Some (dnf x) | |
208 | ||
34e49164 | 209 | let combine2c x = |
90aeb998 | 210 | match interpret_glimpse false x with |
34e49164 | 211 | None -> "None" |
951c7801 | 212 | | Some x -> String.concat " || " x |
34e49164 C |
213 | |
214 | let norm = function | |
215 | And l -> And (List.sort compare l) | |
216 | | Or l -> Or (List.sort compare l) | |
217 | | x -> x | |
218 | ||
219 | let rec merge l1 l2 = | |
220 | match (l1,l2) with | |
221 | ([],l2) -> l2 | |
222 | | (l1,[]) -> l1 | |
223 | | (x::xs,y::ys) -> | |
224 | (match compare x y with | |
225 | -1 -> x::(merge xs l2) | |
226 | | 0 -> x::(merge xs ys) | |
227 | | 1 -> y::(merge l1 ys) | |
228 | | _ -> failwith "not possible") | |
229 | ||
230 | let intersect l1 l2 = List.filter (function l1e -> List.mem l1e l2) l1 | |
231 | ||
232 | let minus_set l1 l2 = List.filter (function l1e -> not (List.mem l1e l2)) l1 | |
233 | ||
234 | let rec insert x l = merge [x] l | |
235 | ||
236 | let rec build_and x y = | |
237 | if x = y | |
238 | then x | |
239 | else | |
240 | match (x,y) with | |
241 | (True,x) | (x,True) -> x | |
242 | | (False,x) | (x,False) -> False | |
243 | | (And l1,And l2) -> And (merge l1 l2) | |
244 | | (x,Or l) when List.mem x l -> x | |
245 | | (Or l,x) when List.mem x l -> x | |
246 | | (Or l1,Or l2) when not ((intersect l1 l2) = []) -> | |
247 | let inner = | |
248 | build_and | |
249 | (List.fold_left build_or False (minus_set l1 l2)) | |
250 | (List.fold_left build_or False (minus_set l2 l1)) in | |
251 | List.fold_left build_or inner (intersect l1 l2) | |
252 | | (x,And l) | (And l,x) -> | |
253 | if List.mem x l | |
254 | then And l | |
255 | else | |
256 | let others = | |
257 | List.filter | |
258 | (function | |
259 | Or l -> not(List.mem x l) | |
260 | | _ -> true) | |
261 | l in | |
262 | And (insert x others) | |
263 | | (x,y) -> norm(And [x;y]) | |
264 | ||
265 | and build_or x y = | |
266 | if x = y | |
267 | then x | |
268 | else | |
269 | match (x,y) with | |
270 | (True,x) | (x,True) -> True | |
271 | | (False,x) | (x,False) -> x | |
272 | | (Or l1,Or l2) -> Or (merge l1 l2) | |
273 | | (x,And l) when List.mem x l -> x | |
274 | | (And l,x) when List.mem x l -> x | |
275 | | (And l1,And l2) when not ((intersect l1 l2) = []) -> | |
276 | let inner = | |
277 | build_or | |
278 | (List.fold_left build_and True (minus_set l1 l2)) | |
279 | (List.fold_left build_and True (minus_set l2 l1)) in | |
280 | List.fold_left build_and inner (intersect l1 l2) | |
281 | | (x,Or l) | (Or l,x) -> | |
282 | if List.mem x l | |
283 | then Or l | |
284 | else | |
285 | let others = | |
286 | List.filter | |
287 | (function | |
288 | And l -> not(List.mem x l) | |
289 | | _ -> true) | |
290 | l in | |
291 | Or (insert x others) | |
292 | | (x,y) -> norm(Or [x;y]) | |
293 | ||
294 | let keep x = Elem x | |
295 | let drop x = True | |
296 | ||
297 | let do_get_constants constants keywords env neg_pos = | |
298 | let donothing r k e = k e in | |
299 | let option_default = True in | |
d6ce1786 | 300 | let bad_default = False in |
34e49164 C |
301 | let bind = build_and in |
302 | let inherited ((nm1,_) as x) = | |
d6ce1786 C |
303 | (* ignore virtuals, can never match *) |
304 | if nm1 = "virtual" then bad_default | |
34e49164 | 305 | (* perhaps inherited, but value not required, so no constraints *) |
ae4735db C |
306 | else if List.mem x neg_pos then option_default |
307 | else (try List.assoc nm1 env with Not_found -> False) in | |
34e49164 C |
308 | let minherited name = inherited (Ast.unwrap_mcode name) in |
309 | let mcode _ x = | |
8f657093 C |
310 | List.fold_left bind option_default |
311 | (List.map | |
312 | (function Ast.MetaPos(name,constraints,_,keep,inh) -> minherited name) | |
313 | (Ast.get_pos_var x)) in | |
34e49164 C |
314 | |
315 | (* if one branch gives no information, then we have to take anything *) | |
316 | let disj_union_all = List.fold_left build_or False in | |
317 | ||
318 | let ident r k i = | |
319 | match Ast.unwrap i with | |
320 | Ast.Id(name) -> | |
321 | bind (k i) | |
322 | (match Ast.unwrap_mcode name with | |
323 | "NULL" -> keywords "NULL" | |
324 | | nm -> constants nm) | |
325 | | Ast.MetaId(name,_,_,_) | Ast.MetaFunc(name,_,_,_) | |
d6ce1786 C |
326 | | Ast.MetaLocalFunc(name,_,_,_) -> |
327 | bind (k i) (minherited name) | |
d3f655c6 | 328 | | Ast.DisjId(ids) -> disj_union_all (List.map r.V.combiner_ident ids) |
34e49164 C |
329 | | _ -> k i in |
330 | ||
331 | let rec type_collect res = function | |
332 | TC.ConstVol(_,ty) | TC.Pointer(ty) | TC.FunctionPointer(ty) | |
333 | | TC.Array(ty) -> type_collect res ty | |
ae4735db C |
334 | | TC.MetaType(tyname,_,_) -> |
335 | inherited tyname | |
34e49164 | 336 | | TC.TypeName(s) -> constants s |
e6509c05 C |
337 | | TC.EnumName(TC.Name s) -> constants s |
338 | | TC.StructUnionName(_,TC.Name s) -> constants s | |
34e49164 C |
339 | | ty -> res in |
340 | ||
341 | (* no point to do anything special for records because glimpse is | |
342 | word-oriented *) | |
343 | let expression r k e = | |
344 | match Ast.unwrap e with | |
345 | Ast.Constant(const) -> | |
346 | bind (k e) | |
347 | (match Ast.unwrap_mcode const with | |
348 | Ast.String s -> constants s | |
349 | | Ast.Char "\\0" -> option_default (* glimpse doesn't like it *) | |
fc1ad971 | 350 | | Ast.Char s -> option_default (* probably not chars either *) |
34e49164 | 351 | (* the following were eg keywords "1", but not good for glimpse *) |
fc1ad971 C |
352 | | Ast.Int s -> option_default (* glimpse doesn't index integers *) |
353 | | Ast.Float s -> option_default (* probably not floats either *)) | |
34e49164 C |
354 | | Ast.MetaExpr(name,_,_,Some type_list,_,_) -> |
355 | let types = List.fold_left type_collect option_default type_list in | |
356 | bind (k e) (bind (minherited name) types) | |
357 | | Ast.MetaErr(name,_,_,_) | Ast.MetaExpr(name,_,_,_,_,_) -> | |
358 | bind (k e) (minherited name) | |
88e71198 | 359 | | Ast.MetaExprList(name,Ast.MetaListLen (lenname,_,_),_,_) -> |
34e49164 | 360 | bind (k e) (bind (minherited name) (minherited lenname)) |
88e71198 | 361 | | Ast.MetaExprList(name,_,_,_) -> minherited name |
34e49164 C |
362 | | Ast.SizeOfExpr(sizeof,exp) -> bind (keywords "sizeof") (k e) |
363 | | Ast.SizeOfType(sizeof,lp,ty,rp) -> bind (keywords "sizeof") (k e) | |
5636bb2c C |
364 | | Ast.NestExpr(starter,expr_dots,ender,wc,false) -> option_default |
365 | | Ast.NestExpr(starter,expr_dots,ender,wc,true) -> | |
34e49164 C |
366 | r.V.combiner_expression_dots expr_dots |
367 | | Ast.DisjExpr(exps) -> | |
368 | disj_union_all (List.map r.V.combiner_expression exps) | |
369 | | Ast.OptExp(exp) -> option_default | |
370 | | Ast.Edots(_,_) | Ast.Ecircles(_,_) | Ast.Estars(_,_) -> option_default | |
371 | | _ -> k e in | |
faf9a90c | 372 | |
34e49164 C |
373 | let fullType r k ft = |
374 | match Ast.unwrap ft with | |
375 | Ast.DisjType(decls) -> | |
376 | disj_union_all (List.map r.V.combiner_fullType decls) | |
377 | | Ast.OptType(ty) -> option_default | |
378 | | _ -> k ft in | |
faf9a90c | 379 | |
34e49164 | 380 | let baseType = function |
8babbc8f C |
381 | Ast.VoidType -> keywords "void" |
382 | | Ast.CharType -> keywords "char" | |
383 | | Ast.ShortType -> keywords "short" | |
f3c4ece6 | 384 | | Ast.ShortIntType -> keywords "short" |
8babbc8f C |
385 | | Ast.IntType -> keywords "int" |
386 | | Ast.DoubleType -> keywords "double" | |
f3c4ece6 | 387 | | Ast.LongDoubleType -> keywords "double" |
8babbc8f | 388 | | Ast.FloatType -> keywords "float" |
f3c4ece6 C |
389 | | Ast.LongType | Ast.LongLongType |
390 | | Ast.LongIntType | Ast.LongLongIntType -> keywords "long" | |
8babbc8f C |
391 | | Ast.SizeType -> keywords "size_t" |
392 | | Ast.SSizeType -> keywords "ssize_t" | |
393 | | Ast.PtrDiffType -> keywords "ptrdiff_t" in | |
34e49164 C |
394 | |
395 | let typeC r k ty = | |
396 | match Ast.unwrap ty with | |
faf9a90c | 397 | Ast.BaseType(ty1,strings) -> bind (k ty) (baseType ty1) |
34e49164 C |
398 | | Ast.TypeName(name) -> bind (k ty) (constants (Ast.unwrap_mcode name)) |
399 | | Ast.MetaType(name,_,_) -> bind (minherited name) (k ty) | |
400 | | _ -> k ty in | |
401 | ||
402 | let declaration r k d = | |
403 | match Ast.unwrap d with | |
413ffc02 C |
404 | Ast.MetaDecl(name,_,_) | Ast.MetaField(name,_,_) -> |
405 | bind (k d) (minherited name) | |
190f1acf C |
406 | | Ast.MetaFieldList(name,Ast.MetaListLen(lenname,_,_),_,_) -> |
407 | bind (minherited name) (bind (minherited lenname) (k d)) | |
413ffc02 | 408 | | Ast.DisjDecl(decls) -> |
34e49164 C |
409 | disj_union_all (List.map r.V.combiner_declaration decls) |
410 | | Ast.OptDecl(decl) -> option_default | |
411 | | Ast.Ddots(dots,whencode) -> option_default | |
412 | | _ -> k d in | |
413 | ||
414 | let initialiser r k i = | |
415 | match Ast.unwrap i with | |
416 | Ast.OptIni(ini) -> option_default | |
417 | | _ -> k i in | |
418 | ||
419 | let parameter r k p = | |
420 | match Ast.unwrap p with | |
421 | Ast.OptParam(param) -> option_default | |
422 | | Ast.MetaParam(name,_,_) -> bind (k p) (minherited name) | |
88e71198 | 423 | | Ast.MetaParamList(name,Ast.MetaListLen(lenname,_,_),_,_) -> |
34e49164 | 424 | bind (minherited name) (bind (minherited lenname) (k p)) |
88e71198 | 425 | | Ast.MetaParamList(name,_,_,_) -> bind (k p) (minherited name) |
34e49164 | 426 | | _ -> k p in |
faf9a90c | 427 | |
34e49164 C |
428 | let rule_elem r k re = |
429 | match Ast.unwrap re with | |
430 | Ast.MetaRuleElem(name,_,_) | Ast.MetaStmt(name,_,_,_) | |
431 | | Ast.MetaStmtList(name,_,_) -> bind (minherited name) (k re) | |
432 | | Ast.WhileHeader(whl,lp,exp,rp) -> | |
433 | bind (keywords "while") (k re) | |
434 | | Ast.WhileTail(whl,lp,exp,rp,sem) -> | |
435 | bind (keywords "do") (k re) | |
436 | | Ast.ForHeader(fr,lp,e1,sem1,e2,sem2,e3,rp) -> | |
437 | bind (keywords "for") (k re) | |
438 | | Ast.SwitchHeader(switch,lp,exp,rp) -> | |
439 | bind (keywords "switch") (k re) | |
440 | | Ast.Break(br,sem) -> | |
441 | bind (keywords "break") (k re) | |
442 | | Ast.Continue(cont,sem) -> | |
443 | bind (keywords "continue") (k re) | |
444 | | Ast.Goto(_,i,_) -> | |
445 | bind (keywords "goto") (k re) | |
446 | | Ast.Default(def,colon) -> | |
447 | bind (keywords "default") (k re) | |
448 | | Ast.Include(inc,s) -> | |
449 | bind (k re) | |
450 | (match Ast.unwrap_mcode s with | |
451 | Ast.Local l | Ast.NonLocal l -> | |
452 | let strings = | |
453 | List.fold_left | |
454 | (function prev -> | |
455 | function | |
456 | (* just take the last thing, probably the most | |
457 | specific. everything is necessary anyway. *) | |
458 | Ast.IncPath s -> [Elem s] | |
459 | | Ast.IncDots -> prev) | |
460 | [] l in | |
461 | (match strings with | |
462 | [] -> True | |
463 | | x::xs -> List.fold_left bind x xs)) | |
464 | | Ast.DisjRuleElem(res) -> | |
465 | disj_union_all (List.map r.V.combiner_rule_elem res) | |
466 | | _ -> k re in | |
faf9a90c | 467 | |
34e49164 C |
468 | let statement r k s = |
469 | match Ast.unwrap s with | |
470 | Ast.Disj(stmt_dots) -> | |
471 | disj_union_all (List.map r.V.combiner_statement_dots stmt_dots) | |
5636bb2c C |
472 | | Ast.Nest(starter,stmt_dots,ender,whn,false,_,_) -> option_default |
473 | | Ast.Nest(starter,stmt_dots,ender,whn,true,_,_) -> | |
34e49164 C |
474 | r.V.combiner_statement_dots stmt_dots |
475 | | Ast.OptStm(s) -> option_default | |
476 | | Ast.Dots(d,whn,_,_) | Ast.Circles(d,whn,_,_) | Ast.Stars(d,whn,_,_) -> | |
477 | option_default | |
478 | | _ -> k s in | |
479 | ||
480 | V.combiner bind option_default | |
481 | mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode | |
c491d8ee | 482 | donothing donothing donothing donothing donothing |
34e49164 C |
483 | ident expression fullType typeC initialiser parameter declaration |
484 | rule_elem statement donothing donothing donothing | |
485 | ||
486 | (* ------------------------------------------------------------------------ *) | |
487 | ||
488 | let filter_combine combine to_drop = | |
489 | let rec and_loop = function | |
490 | Elem x when List.mem x to_drop -> True | |
491 | | Or l -> List.fold_left build_or False (List.map or_loop l) | |
492 | | x -> x | |
493 | and or_loop = function | |
494 | Elem x when List.mem x to_drop -> False | |
495 | | And l -> List.fold_left build_and True (List.map and_loop l) | |
496 | | x -> x in | |
497 | or_loop combine | |
498 | ||
499 | (* ------------------------------------------------------------------------ *) | |
500 | ||
501 | let get_all_constants minus_only = | |
502 | let donothing r k e = k e in | |
503 | let bind = Common.union_set in | |
504 | let option_default = [] in | |
505 | let mcode r (x,_,mcodekind,_) = | |
506 | match mcodekind with | |
708f4980 | 507 | Ast.MINUS(_,_,_,_) -> [x] |
34e49164 C |
508 | | _ when minus_only -> [] |
509 | | _ -> [x] in | |
510 | let other r _ = [] in | |
511 | ||
512 | V.combiner bind option_default | |
513 | other mcode other other other other other other other other other other | |
34e49164 | 514 | |
c491d8ee | 515 | donothing donothing donothing donothing donothing |
34e49164 C |
516 | donothing donothing donothing donothing donothing donothing donothing |
517 | donothing donothing donothing donothing donothing | |
518 | ||
519 | (* ------------------------------------------------------------------------ *) | |
520 | ||
521 | let get_plus_constants = | |
522 | let donothing r k e = k e in | |
523 | let bind = Common.union_set in | |
524 | let option_default = [] in | |
90aeb998 C |
525 | |
526 | let recurse l = | |
527 | List.fold_left | |
528 | (List.fold_left | |
529 | (function prev -> | |
530 | function cur -> | |
531 | bind ((get_all_constants false).V.combiner_anything cur) prev)) | |
532 | [] l in | |
533 | let process_mcodekind = function | |
8babbc8f | 534 | Ast.MINUS(_,_,_,Ast.REPLACEMENT(anythings,_)) -> recurse anythings |
951c7801 C |
535 | | Ast.CONTEXT(_,Ast.BEFORE(a,_)) -> recurse a |
536 | | Ast.CONTEXT(_,Ast.AFTER(a,_)) -> recurse a | |
537 | | Ast.CONTEXT(_,Ast.BEFOREAFTER(a1,a2,_)) -> | |
34e49164 C |
538 | Common.union_set (recurse a1) (recurse a2) |
539 | | _ -> [] in | |
540 | ||
90aeb998 C |
541 | let mcode r mc = process_mcodekind (Ast.get_mcodekind mc) in |
542 | let end_info (_,_,_,mc) = process_mcodekind mc in | |
543 | ||
544 | let rule_elem r k e = | |
545 | match Ast.unwrap e with | |
546 | Ast.FunHeader(bef,_,_,_,_,_,_) | |
547 | | Ast.Decl(bef,_,_) -> bind (process_mcodekind bef) (k e) | |
548 | | _ -> k e in | |
549 | ||
550 | let statement r k e = | |
551 | match Ast.unwrap e with | |
552 | Ast.IfThen(_,_,ei) | Ast.IfThenElse(_,_,_,_,ei) | |
553 | | Ast.While(_,_,ei) | Ast.For(_,_,ei) | |
554 | | Ast.Iterator(_,_,ei) -> bind (k e) (end_info ei) | |
555 | | _ -> k e in | |
556 | ||
34e49164 C |
557 | V.combiner bind option_default |
558 | mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode | |
c491d8ee | 559 | donothing donothing donothing donothing donothing |
34e49164 | 560 | donothing donothing donothing donothing donothing donothing donothing |
90aeb998 | 561 | rule_elem statement donothing donothing donothing |
34e49164 C |
562 | |
563 | (* ------------------------------------------------------------------------ *) | |
564 | ||
565 | (* true means the rule should be analyzed, false means it should be ignored *) | |
566 | let rec dependencies env = function | |
567 | Ast.Dep s -> (try List.assoc s env with Not_found -> False) | |
568 | | Ast.AntiDep s -> True | |
569 | | Ast.EverDep s -> (try List.assoc s env with Not_found -> False) | |
570 | | Ast.NeverDep s -> True | |
571 | | Ast.AndDep (d1,d2) -> build_and (dependencies env d1) (dependencies env d2) | |
572 | | Ast.OrDep (d1,d2) -> build_or (dependencies env d1) (dependencies env d2) | |
573 | | Ast.NoDep -> True | |
7f004419 | 574 | | Ast.FailDep -> False |
34e49164 C |
575 | |
576 | (* ------------------------------------------------------------------------ *) | |
577 | ||
578 | let all_context = | |
579 | let bind x y = x && y in | |
580 | let option_default = true in | |
581 | ||
582 | let donothing recursor k e = k e in | |
583 | ||
90aeb998 | 584 | let process_mcodekind = function |
34e49164 C |
585 | Ast.CONTEXT(_,Ast.NOTHING) -> true |
586 | | _ -> false in | |
587 | ||
90aeb998 C |
588 | let mcode r e = process_mcodekind (Ast.get_mcodekind e) in |
589 | ||
590 | let end_info (_,_,_,mc) = process_mcodekind mc in | |
591 | ||
592 | let initialiser r k e = | |
593 | match Ast.unwrap e with | |
c491d8ee | 594 | Ast.StrInitList(all_minus,_,_,_,_) -> |
90aeb998 C |
595 | not all_minus && k e |
596 | | _ -> k e in | |
597 | ||
598 | let rule_elem r k e = | |
599 | match Ast.unwrap e with | |
600 | Ast.FunHeader(bef,_,_,_,_,_,_) | |
601 | | Ast.Decl(bef,_,_) -> bind (process_mcodekind bef) (k e) | |
602 | | _ -> k e in | |
603 | ||
604 | let statement r k e = | |
605 | match Ast.unwrap e with | |
606 | Ast.IfThen(_,_,ei) | Ast.IfThenElse(_,_,_,_,ei) | |
607 | | Ast.While(_,_,ei) | Ast.For(_,_,ei) | |
608 | | Ast.Iterator(_,_,ei) -> bind (k e) (end_info ei) | |
609 | | _ -> k e in | |
610 | ||
34e49164 C |
611 | V.combiner bind option_default |
612 | mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode mcode | |
c491d8ee | 613 | donothing donothing donothing donothing donothing |
90aeb998 C |
614 | donothing donothing donothing donothing initialiser donothing |
615 | donothing rule_elem statement donothing donothing donothing | |
34e49164 C |
616 | |
617 | (* ------------------------------------------------------------------------ *) | |
618 | ||
619 | let rule_fn tls in_plus env neg_pos = | |
620 | List.fold_left | |
621 | (function (rest_info,in_plus) -> | |
622 | function (cur,neg_pos) -> | |
623 | let minuses = | |
ae4735db C |
624 | let getter = do_get_constants keep drop env neg_pos in |
625 | getter.V.combiner_top_level cur in | |
34e49164 C |
626 | let all_minuses = |
627 | if !Flag.sgrep_mode2 | |
628 | then [] (* nothing removed for sgrep *) | |
629 | else (get_all_constants true).V.combiner_top_level cur in | |
630 | let plusses = get_plus_constants.V.combiner_top_level cur in | |
631 | (* the following is for eg -foo(2) +foo(x) then in another rule | |
632 | -foo(10); don't want to consider that foo is guaranteed to be | |
633 | created by the rule. not sure this works completely: what if foo is | |
634 | in both - and +, but in an or, so the cases aren't related? | |
635 | not sure this whole thing is a good idea. how do we know that | |
636 | something that is only in plus is really freshly created? *) | |
637 | let plusses = Common.minus_set plusses all_minuses in | |
638 | let was_bot = minuses = True in | |
639 | let new_minuses = filter_combine minuses in_plus in | |
640 | let new_plusses = Common.union_set plusses in_plus in | |
641 | (* perhaps it should be build_and here? we don't realy have multiple | |
642 | minirules anymore anyway. *) | |
643 | match new_minuses with | |
644 | True -> | |
ae4735db C |
645 | let getter = do_get_constants drop keep env neg_pos in |
646 | let retry = getter.V.combiner_top_level cur in | |
34e49164 C |
647 | (match retry with |
648 | True when not was_bot -> (rest_info, new_plusses) | |
649 | | x -> (build_or x rest_info, new_plusses)) | |
650 | | x -> (build_or x rest_info, new_plusses)) | |
651 | (False,in_plus) (List.combine tls neg_pos) | |
652 | ||
90aeb998 C |
653 | let run rules neg_pos_vars = |
654 | let (info,_,_,_) = | |
655 | List.fold_left | |
656 | (function (rest_info,in_plus,env,locals(*dom of env*)) -> | |
657 | function | |
413ffc02 | 658 | (Ast.ScriptRule (nm,_,deps,mv,_,_),_) -> |
90aeb998 C |
659 | let extra_deps = |
660 | List.fold_left | |
661 | (function prev -> | |
174d1640 | 662 | function (_,(rule,_),_) -> |
90aeb998 C |
663 | if rule = "virtual" |
664 | then prev | |
665 | else Ast.AndDep (Ast.Dep rule,prev)) | |
666 | deps mv in | |
667 | (match dependencies env extra_deps with | |
d6ce1786 C |
668 | False -> |
669 | (rest_info, in_plus, (nm,True)::env, nm::locals) | |
90aeb998 C |
670 | | dependencies -> |
671 | (build_or dependencies rest_info, in_plus, env, locals)) | |
174d1640 C |
672 | | (Ast.InitialScriptRule (_,_,deps,_),_) |
673 | | (Ast.FinalScriptRule (_,_,deps,_),_) -> | |
aa721442 C |
674 | (* initialize and finalize dependencies are irrelevant to |
675 | get_constants *) | |
90aeb998 C |
676 | (rest_info, in_plus, env, locals) |
677 | | (Ast.CocciRule (nm,(dep,_,_),cur,_,_),neg_pos_vars) -> | |
678 | let (cur_info,cur_plus) = | |
f3c4ece6 | 679 | rule_fn cur in_plus ((nm,True)::env) neg_pos_vars in |
90aeb998 C |
680 | (match dependencies env dep with |
681 | False -> (rest_info,cur_plus,env,locals) | |
682 | | dependencies -> | |
683 | if List.for_all all_context.V.combiner_top_level cur | |
f3c4ece6 C |
684 | then |
685 | let cur_info = build_and dependencies cur_info in | |
686 | (rest_info,cur_plus,(nm,cur_info)::env,nm::locals) | |
90aeb998 | 687 | else |
34e49164 C |
688 | (* no constants if dependent on another rule; then we need to |
689 | find the constants of that rule *) | |
f3c4ece6 C |
690 | (build_or (build_and dependencies cur_info) rest_info, |
691 | cur_plus,(nm,cur_info)::env,locals))) | |
90aeb998 C |
692 | (False,[],[],[]) |
693 | (List.combine (rules : Ast.rule list) neg_pos_vars) in | |
694 | info | |
695 | ||
696 | let get_constants rules neg_pos_vars = | |
697 | match !Flag.scanner with | |
1eddfd50 | 698 | Flag.NoScanner -> (None,None,None) |
90aeb998 C |
699 | | Flag.Grep -> |
700 | let res = run rules neg_pos_vars in | |
1eddfd50 | 701 | (interpret_grep true res,None,None) |
90aeb998 C |
702 | | Flag.Glimpse -> |
703 | let res = run rules neg_pos_vars in | |
1eddfd50 | 704 | (interpret_grep true res,interpret_glimpse true res,None) |
90aeb998 C |
705 | | Flag.Google _ -> |
706 | let res = run rules neg_pos_vars in | |
1eddfd50 | 707 | (interpret_grep true res,interpret_google true res,None) |
3a314143 | 708 | | Flag.IdUtils -> |
1eddfd50 C |
709 | let res = run rules neg_pos_vars in |
710 | (interpret_grep true res,None,Some res) |