2 * Copyright 2005-2008, Ecole des Mines de Nantes, University of Copenhagen
3 * Yoann Padioleau, Julia Lawall, Rene Rydhof Hansen, Henrik Stuart, Gilles Muller
4 * This file is part of Coccinelle.
6 * Coccinelle is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, according to version 2 of the License.
10 * Coccinelle is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with Coccinelle. If not, see <http://www.gnu.org/licenses/>.
18 * The authors reserve the right to distribute this or future versions of
19 * Coccinelle under other licenses.
23 module Ast = Ast_cocci
25 (* --------------------------------------------------------------------- *)
28 type arity = OPT | UNIQUE | NONE
31 { tline_start : int; tline_end : int;
32 left_offset : int; right_offset : int }
33 let default_token_info =
34 { tline_start = -1; tline_end = -1; left_offset = -1; right_offset = -1 }
36 (* MIXED is like CONTEXT, since sometimes MIXED things have to revert to
37 CONTEXT - see insert_plus.ml *)
39 MINUS of (Ast.anything list list * token_info) ref
41 | CONTEXT of (Ast.anything Ast.befaft * token_info * token_info) ref
42 | MIXED of (Ast.anything Ast.befaft * token_info * token_info) ref
44 type info = { line_start : int; line_end : int;
45 logical_start : int; logical_end : int;
46 attachable_start : bool; attachable_end : bool;
47 mcode_start : mcodekind list; mcode_end : mcodekind list;
48 column : int; offset : int;
49 (* the following are only for + code *)
50 strings_before : string list; strings_after : string list }
52 type 'a mcode = 'a * arity * info * mcodekind * meta_pos ref (* pos, - only *)
53 (* int ref is an index *)
58 mcodekind : mcodekind ref;
59 exp_ty : Type_cocci.typeC option ref; (* only for expressions *)
60 bef_aft : dots_bef_aft; (* only for statements *)
61 true_if_arg : bool; (* true if "arg_exp", only for exprs *)
62 true_if_test : bool; (* true if "test position", only for exprs *)
63 true_if_test_exp : bool;(* true if "test_exp from iso", only for exprs *)
64 (*nonempty if this represents the use of an iso*)
65 iso_info : (string*anything) list }
68 NoDots | AddingBetweenDots of statement | DroppingBetweenDots of statement
70 (* for iso metavariables, true if they can only match nonmodified terms with
71 all metavariables unitary
72 for SP metavariables, true if the metavariable is unitary (valid up to
73 isomorphism phase only)
74 In SP, the only options are impure and context
76 and pure = Impure | Pure | Context | PureContext (* pure and only context *)
78 (* --------------------------------------------------------------------- *)
79 (* --------------------------------------------------------------------- *)
87 and 'a dots = 'a base_dots wrap
89 (* --------------------------------------------------------------------- *)
94 | MetaId of Ast.meta_name mcode * ident list * pure
95 | MetaFunc of Ast.meta_name mcode * ident list * pure
96 | MetaLocalFunc of Ast.meta_name mcode * ident list * pure
98 | UniqueIdent of ident
100 and ident = base_ident wrap
102 (* --------------------------------------------------------------------- *)
105 and base_expression =
107 | Constant of Ast.constant mcode
108 | FunCall of expression * string mcode (* ( *) *
109 expression dots * string mcode (* ) *)
110 | Assignment of expression * Ast.assignOp mcode * expression *
111 bool (* true if it can match an initialization *)
112 | CondExpr of expression * string mcode (* ? *) * expression option *
113 string mcode (* : *) * expression
114 | Postfix of expression * Ast.fixOp mcode
115 | Infix of expression * Ast.fixOp mcode
116 | Unary of expression * Ast.unaryOp mcode
117 | Binary of expression * Ast.binaryOp mcode * expression
118 | Nested of expression * Ast.binaryOp mcode * expression
119 | Paren of string mcode (* ( *) * expression *
121 | ArrayAccess of expression * string mcode (* [ *) * expression *
123 | RecordAccess of expression * string mcode (* . *) * ident
124 | RecordPtAccess of expression * string mcode (* -> *) * ident
125 | Cast of string mcode (* ( *) * typeC * string mcode (* ) *) *
127 | SizeOfExpr of string mcode (* sizeof *) * expression
128 | SizeOfType of string mcode (* sizeof *) * string mcode (* ( *) *
129 typeC * string mcode (* ) *)
130 | TypeExp of typeC (* type name used as an expression, only in args *)
131 | MetaErr of Ast.meta_name mcode * expression list * pure
132 | MetaExpr of Ast.meta_name mcode * expression list *
133 Type_cocci.typeC list option * Ast.form * pure
134 | MetaExprList of Ast.meta_name mcode (* only in arg lists *) *
136 | EComma of string mcode (* only in arg lists *)
137 | DisjExpr of string mcode * expression list *
138 string mcode list (* the |s *) * string mcode
139 | NestExpr of string mcode * expression dots * string mcode *
140 expression option * Ast.multi
141 | Edots of string mcode (* ... *) * expression option
142 | Ecircles of string mcode (* ooo *) * expression option
143 | Estars of string mcode (* *** *) * expression option
144 | OptExp of expression
145 | UniqueExp of expression
147 and expression = base_expression wrap
149 and listlen = Ast.meta_name mcode option
151 (* --------------------------------------------------------------------- *)
155 ConstVol of Ast.const_vol mcode * typeC
156 | BaseType of Ast.baseType mcode * Ast.sign mcode option
157 | ImplicitInt of Ast.sign mcode
158 | Pointer of typeC * string mcode (* * *)
159 | FunctionPointer of typeC *
160 string mcode(* ( *)*string mcode(* * *)*string mcode(* ) *)*
161 string mcode (* ( *)*parameter_list*string mcode(* ) *)
162 | FunctionType of typeC option *
163 string mcode (* ( *) * parameter_list *
165 | Array of typeC * string mcode (* [ *) *
166 expression option * string mcode (* ] *)
167 | StructUnionName of Ast.structUnion mcode * ident option (* name *)
168 | StructUnionDef of typeC (* either StructUnionName or metavar *) *
169 string mcode (* { *) * declaration dots * string mcode (* } *)
170 | TypeName of string mcode
171 | MetaType of Ast.meta_name mcode * pure
172 | DisjType of string mcode * typeC list * (* only after iso *)
173 string mcode list (* the |s *) * string mcode
175 | UniqueType of typeC
177 and typeC = base_typeC wrap
179 (* --------------------------------------------------------------------- *)
180 (* Variable declaration *)
181 (* Even if the Cocci program specifies a list of declarations, they are
182 split out into multiple declarations of a single variable each. *)
184 and base_declaration =
185 Init of Ast.storage mcode option * typeC * ident * string mcode (*=*) *
186 initialiser * string mcode (*;*)
187 | UnInit of Ast.storage mcode option * typeC * ident * string mcode (* ; *)
188 | TyDecl of typeC * string mcode (* ; *)
189 | MacroDecl of ident (* name *) * string mcode (* ( *) *
190 expression dots * string mcode (* ) *) * string mcode (* ; *)
191 | Typedef of string mcode (* typedef *) * typeC * typeC * string mcode (*;*)
192 | DisjDecl of string mcode * declaration list *
193 string mcode list (* the |s *) * string mcode
194 (* Ddots is for a structure declaration *)
195 | Ddots of string mcode (* ... *) * declaration option (* whencode *)
196 | OptDecl of declaration
197 | UniqueDecl of declaration
199 and declaration = base_declaration wrap
201 (* --------------------------------------------------------------------- *)
204 and base_initialiser =
205 InitExpr of expression
206 | InitList of string mcode (*{*) * initialiser_list * string mcode (*}*)
208 string mcode (*.*) * ident (* name *) * string mcode (*=*) *
209 initialiser (* gccext: *)
210 | InitGccName of ident (* name *) * string mcode (*:*) *
213 string mcode (*[*) * expression * string mcode (*]*) *
214 string mcode (*=*) * initialiser
216 string mcode (*[*) * expression * string mcode (*...*) *
217 expression * string mcode (*]*) * string mcode (*=*) * initialiser
218 | IComma of string mcode (* , *)
219 | Idots of string mcode (* ... *) * initialiser option (* whencode *)
220 | OptIni of initialiser
221 | UniqueIni of initialiser
223 and initialiser = base_initialiser wrap
225 and initialiser_list = initialiser dots
227 (* --------------------------------------------------------------------- *)
230 and base_parameterTypeDef =
232 | Param of typeC * ident option
233 | MetaParam of Ast.meta_name mcode * pure
234 | MetaParamList of Ast.meta_name mcode * listlen * pure
235 | PComma of string mcode
236 | Pdots of string mcode (* ... *)
237 | Pcircles of string mcode (* ooo *)
238 | OptParam of parameterTypeDef
239 | UniqueParam of parameterTypeDef
241 and parameterTypeDef = base_parameterTypeDef wrap
243 and parameter_list = parameterTypeDef dots
245 (* --------------------------------------------------------------------- *)
246 (* #define Parameters *)
248 and base_define_param =
250 | DPComma of string mcode
251 | DPdots of string mcode (* ... *)
252 | DPcircles of string mcode (* ooo *)
253 | OptDParam of define_param
254 | UniqueDParam of define_param
256 and define_param = base_define_param wrap
258 and base_define_parameters =
260 | DParams of string mcode(*( *) * define_param dots * string mcode(* )*)
262 and define_parameters = base_define_parameters wrap
264 (* --------------------------------------------------------------------- *)
268 Decl of (info * mcodekind) (* before the decl *) * declaration
269 | Seq of string mcode (* { *) * statement dots *
271 | ExprStatement of expression * string mcode (*;*)
272 | IfThen of string mcode (* if *) * string mcode (* ( *) *
273 expression * string mcode (* ) *) *
274 statement * (info * mcodekind) (* after info *)
275 | IfThenElse of string mcode (* if *) * string mcode (* ( *) *
276 expression * string mcode (* ) *) *
277 statement * string mcode (* else *) * statement *
279 | While of string mcode (* while *) * string mcode (* ( *) *
280 expression * string mcode (* ) *) *
281 statement * (info * mcodekind) (* after info *)
282 | Do of string mcode (* do *) * statement *
283 string mcode (* while *) * string mcode (* ( *) *
284 expression * string mcode (* ) *) *
286 | For of string mcode (* for *) * string mcode (* ( *) *
287 expression option * string mcode (*;*) *
288 expression option * string mcode (*;*) *
289 expression option * string mcode (* ) *) * statement *
290 (info * mcodekind) (* after info *)
291 | Iterator of ident (* name *) * string mcode (* ( *) *
292 expression dots * string mcode (* ) *) *
293 statement * (info * mcodekind) (* after info *)
294 | Switch of string mcode (* switch *) * string mcode (* ( *) *
295 expression * string mcode (* ) *) * string mcode (* { *) *
296 case_line dots * string mcode (* } *)
297 | Break of string mcode (* break *) * string mcode (* ; *)
298 | Continue of string mcode (* continue *) * string mcode (* ; *)
299 | Label of ident * string mcode (* : *)
300 | Goto of string mcode (* goto *) * ident * string mcode (* ; *)
301 | Return of string mcode (* return *) * string mcode (* ; *)
302 | ReturnExpr of string mcode (* return *) * expression *
304 | MetaStmt of Ast.meta_name mcode * pure
305 | MetaStmtList of Ast.meta_name mcode(*only in statement lists*) * pure
306 | Exp of expression (* only in dotted statement lists *)
307 | TopExp of expression (* for macros body *)
308 | Ty of typeC (* only at top level *)
309 | Disj of string mcode * statement dots list *
310 string mcode list (* the |s *) * string mcode
311 | Nest of string mcode * statement dots * string mcode *
312 (statement dots,statement) whencode list * Ast.multi
313 | Dots of string mcode (* ... *) *
314 (statement dots,statement) whencode list
315 | Circles of string mcode (* ooo *) *
316 (statement dots,statement) whencode list
317 | Stars of string mcode (* *** *) *
318 (statement dots,statement) whencode list
319 | FunDecl of (info * mcodekind) (* before the function decl *) *
320 fninfo list * ident (* name *) *
321 string mcode (* ( *) * parameter_list * string mcode (* ) *) *
322 string mcode (* { *) * statement dots *
324 | Include of string mcode (* #include *) * Ast.inc_file mcode (* file *)
325 | Define of string mcode (* #define *) * ident (* name *) *
326 define_parameters (*params*) * statement dots
327 | OptStm of statement
328 | UniqueStm of statement
331 FStorage of Ast.storage mcode
333 | FInline of string mcode
334 | FAttr of string mcode
336 and ('a,'b) whencode =
339 | WhenModifier of Ast.when_modifier
340 | WhenNotTrue of expression
341 | WhenNotFalse of expression
343 and statement = base_statement wrap
346 Default of string mcode (* default *) * string mcode (*:*) * statement dots
347 | Case of string mcode (* case *) * expression * string mcode (*:*) *
349 | OptCase of case_line
351 and case_line = base_case_line wrap
353 (* --------------------------------------------------------------------- *)
357 MetaPos of Ast.meta_name mcode * Ast.meta_name list * Ast.meta_collect
360 (* --------------------------------------------------------------------- *)
365 | CODE of statement dots
366 | FILEINFO of string mcode (* old file *) * string mcode (* new file *)
367 | ERRORWORDS of expression list
368 | OTHER of statement (* temporary, disappears after top_level.ml *)
370 and top_level = base_top_level wrap
371 and rule = top_level list
375 (rule * Ast.metavar list *
376 (string list * string list * Ast.dependency * string * Ast.exists)) *
377 (rule * Ast.metavar list)
379 string * Ast.dependency * (string * Ast.meta_name) list * string
381 (* --------------------------------------------------------------------- *)
384 DotsExprTag of expression dots
385 | DotsInitTag of initialiser dots
386 | DotsParamTag of parameterTypeDef dots
387 | DotsStmtTag of statement dots
388 | DotsDeclTag of declaration dots
389 | DotsCaseTag of case_line dots
391 | ExprTag of expression
392 | ArgExprTag of expression (* for isos *)
393 | TestExprTag of expression (* for isos *)
395 | ParamTag of parameterTypeDef
396 | InitTag of initialiser
397 | DeclTag of declaration
398 | StmtTag of statement
399 | CaseLineTag of case_line
400 | TopTag of top_level
401 | IsoWhenTag of Ast.when_modifier
402 | IsoWhenTTag of expression
403 | IsoWhenFTag of expression
404 | MetaPosTag of meta_pos
406 let dotsExpr x = DotsExprTag x
407 let dotsParam x = DotsParamTag x
408 let dotsInit x = DotsInitTag x
409 let dotsStmt x = DotsStmtTag x
410 let dotsDecl x = DotsDeclTag x
411 let dotsCase x = DotsCaseTag x
412 let ident x = IdentTag x
413 let expr x = ExprTag x
414 let typeC x = TypeCTag x
415 let param x = ParamTag x
416 let ini x = InitTag x
417 let decl x = DeclTag x
418 let stmt x = StmtTag x
419 let case_line x = CaseLineTag x
422 (* --------------------------------------------------------------------- *)
423 (* Avoid cluttering the parser. Calculated in compute_lines.ml. *)
425 let default_info _ = (* why is this a function? *)
426 { line_start = -1; line_end = -1;
427 logical_start = -1; logical_end = -1;
428 attachable_start = true; attachable_end = true;
429 mcode_start = []; mcode_end = [];
430 column = -1; offset = -1; strings_before = []; strings_after = [] }
432 let default_befaft _ =
433 MIXED(ref (Ast.NOTHING,default_token_info,default_token_info))
434 let context_befaft _ =
435 CONTEXT(ref (Ast.NOTHING,default_token_info,default_token_info))
439 info = default_info();
441 mcodekind = ref (default_befaft());
445 true_if_test = false;
446 true_if_test_exp = false;
450 info = default_info();
452 mcodekind = ref (context_befaft());
456 true_if_test = false;
457 true_if_test_exp = false;
459 let unwrap x = x.node
460 let unwrap_mcode (x,_,_,_,_) = x
461 let rewrap model x = { model with node = x }
462 let rewrap_mcode (_,arity,info,mcodekind,pos) x = (x,arity,info,mcodekind,pos)
463 let copywrap model x =
464 { model with node = x; index = ref !(model.index);
465 mcodekind = ref !(model.mcodekind); exp_ty = ref !(model.exp_ty)}
466 let get_pos (_,_,_,_,x) = !x
467 let get_pos_ref (_,_,_,_,x) = x
468 let set_pos pos (m,arity,info,mcodekind,_) = (m,arity,info,mcodekind,ref pos)
469 let get_info x = x.info
470 let set_info x info = {x with info = info}
471 let get_line x = x.info.line_start
472 let get_line_end x = x.info.line_end
473 let get_index x = !(x.index)
474 let set_index x i = x.index := i
475 let get_mcodekind x = !(x.mcodekind)
476 let get_mcode_mcodekind (_,_,_,mcodekind,_) = mcodekind
477 let get_mcodekind_ref x = x.mcodekind
478 let set_mcodekind x mk = x.mcodekind := mk
479 let set_type x t = x.exp_ty := t
480 let get_type x = !(x.exp_ty)
481 let get_dots_bef_aft x = x.bef_aft
482 let set_dots_bef_aft x dots_bef_aft = {x with bef_aft = dots_bef_aft}
483 let get_arg_exp x = x.true_if_arg
484 let set_arg_exp x = {x with true_if_arg = true}
485 let get_test_pos x = x.true_if_test
486 let set_test_pos x = {x with true_if_test = true}
487 let get_test_exp x = x.true_if_test_exp
488 let set_test_exp x = {x with true_if_test_exp = true}
489 let get_iso x = x.iso_info
490 let set_iso x i = if !Flag.track_iso_usage then {x with iso_info = i} else x
491 let set_mcode_data data (_,ar,info,mc,pos) = (data,ar,info,mc,pos)
493 (* --------------------------------------------------------------------- *)
495 (* unique indices, for mcode and tree nodes *)
496 let index_counter = ref 0
497 let fresh_index _ = let cur = !index_counter in index_counter := cur + 1; cur
499 (* --------------------------------------------------------------------- *)
507 (* --------------------------------------------------------------------- *)
509 let rec ast0_type_to_type ty =
511 ConstVol(cv,ty) -> Type_cocci.ConstVol(const_vol cv,ast0_type_to_type ty)
512 | BaseType(bty,None) ->
513 Type_cocci.BaseType(baseType bty,None)
514 | BaseType(bty,Some sgn) ->
515 Type_cocci.BaseType(baseType bty,Some (sign sgn))
516 | ImplicitInt(sgn) ->
517 let bty = Type_cocci.IntType in
518 Type_cocci.BaseType(bty,Some (sign sgn))
519 | Pointer(ty,_) -> Type_cocci.Pointer(ast0_type_to_type ty)
520 | FunctionPointer(ty,_,_,_,_,params,_) ->
521 Type_cocci.FunctionPointer(ast0_type_to_type ty)
522 | FunctionType _ -> failwith "not supported"
523 | Array(ety,_,_,_) -> Type_cocci.Array(ast0_type_to_type ety)
524 | StructUnionName(su,Some tag) ->
525 (match unwrap tag with
527 Type_cocci.StructUnionName(structUnion su,false,unwrap_mcode tag)
530 "warning: struct/union with a metavariable name detected.\n";
532 "For type checking assuming the name of the metavariable is the name of the type\n";
533 let (rule,tag) = unwrap_mcode tag in
534 Type_cocci.StructUnionName(structUnion su,true,rule^tag))
535 | _ -> failwith "unexpected struct/union type name")
536 | StructUnionName(su,None) -> failwith "nameless structure - what to do???"
537 | StructUnionDef(ty,_,_,_) -> ast0_type_to_type ty
538 | TypeName(name) -> Type_cocci.TypeName(unwrap_mcode name)
539 | MetaType(name,_) ->
540 Type_cocci.MetaType(unwrap_mcode name,Type_cocci.Unitary,false)
541 | DisjType(_,types,_,_) -> failwith "unexpected DisjType"
542 | OptType(ty) | UniqueType(ty) ->
546 match unwrap_mcode t with
547 Ast.VoidType -> Type_cocci.VoidType
548 | Ast.CharType -> Type_cocci.CharType
549 | Ast.ShortType -> Type_cocci.ShortType
550 | Ast.IntType -> Type_cocci.IntType
551 | Ast.DoubleType -> Type_cocci.DoubleType
552 | Ast.FloatType -> Type_cocci.FloatType
553 | Ast.LongType -> Type_cocci.LongType
556 match unwrap_mcode t with
557 Ast.Struct -> Type_cocci.Struct
558 | Ast.Union -> Type_cocci.Union
561 match unwrap_mcode t with
562 Ast.Signed -> Type_cocci.Signed
563 | Ast.Unsigned -> Type_cocci.Unsigned
566 match unwrap_mcode t with
567 Ast.Const -> Type_cocci.Const
568 | Ast.Volatile -> Type_cocci.Volatile
570 (* --------------------------------------------------------------------- *)
571 (* this function is a rather minimal attempt. the problem is that information
572 has been lost. but since it is only used for metavariable types in the isos,
573 perhaps it doesn't matter *)
574 let make_mcode x = (x,NONE,default_info(),context_befaft(),ref NoMetaPos)
575 let make_mcode_info x info = (x,NONE,info,context_befaft(),ref NoMetaPos)
579 let rec reverse_type ty =
581 Type_cocci.ConstVol(cv,ty) ->
582 ConstVol(reverse_const_vol cv,wrap(reverse_type ty))
583 | Type_cocci.BaseType(bty,None) ->
584 BaseType(reverse_baseType bty,None)
585 | Type_cocci.BaseType(bty,Some sgn) ->
586 BaseType(reverse_baseType bty,Some (reverse_sign sgn))
587 | Type_cocci.Pointer(ty) ->
588 Pointer(wrap(reverse_type ty),make_mcode "*")
589 | Type_cocci.StructUnionName(su,mv,tag) ->
593 StructUnionName(reverse_structUnion su,
594 Some(wrap(MetaId(make_mcode ("",tag),[],Impure))))
596 StructUnionName(reverse_structUnion su,
597 Some (wrap(Id(make_mcode tag))))
598 | Type_cocci.TypeName(name) -> TypeName(make_mcode name)
599 | Type_cocci.MetaType(name,_,_) ->
600 MetaType(make_mcode name,Impure(*not really right*))
603 and reverse_baseType t =
606 Type_cocci.VoidType -> Ast.VoidType
607 | Type_cocci.CharType -> Ast.CharType
608 | Type_cocci.BoolType -> Ast.IntType
609 | Type_cocci.ShortType -> Ast.ShortType
610 | Type_cocci.IntType -> Ast.IntType
611 | Type_cocci.DoubleType -> Ast.DoubleType
612 | Type_cocci.FloatType -> Ast.FloatType
613 | Type_cocci.LongType -> Ast.LongType)
615 and reverse_structUnion t =
618 Type_cocci.Struct -> Ast.Struct
619 | Type_cocci.Union -> Ast.Union)
624 Type_cocci.Signed -> Ast.Signed
625 | Type_cocci.Unsigned -> Ast.Unsigned)
627 and reverse_const_vol t =
630 Type_cocci.Const -> Ast.Const
631 | Type_cocci.Volatile -> Ast.Volatile)
633 (* --------------------------------------------------------------------- *)
637 (Impure,_) | (_,Impure) -> Impure
638 | (Pure,Context) | (Context,Pure) -> Impure
639 | (Pure,_) | (_,Pure) -> Pure
640 | (_,Context) | (Context,_) -> Context
643 (* --------------------------------------------------------------------- *)
645 let rule_name = ref "" (* for the convenience of the parser *)