engine/.#pattern_c.ml.1.3

   1 (*
   2 * Copyright 2005-2009, 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.
   5 *
   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.
   9 *
  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.
  14 *
  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/>.
  17 *
  18 * The authors reserve the right to distribute this or future versions of
  19 * Coccinelle under other licenses.
  20 *)
  21
  22
  23 open Common
  24
  25 module Flag_engine = Flag_matcher
  26 (*****************************************************************************)
  27 (* The functor argument  *)
  28 (*****************************************************************************)
  29
  30 (* info passed recursively in monad in addition to binding *)
  31 type xinfo = {
  32   optional_storage_iso : bool;
  33   optional_qualifier_iso : bool;
  34   value_format_iso : bool;
  35 }
  36
  37 module XMATCH = struct
  38
  39   (* ------------------------------------------------------------------------*)
  40   (* Combinators history *)
  41   (* ------------------------------------------------------------------------*)
  42   (*
  43    * version0:
  44    *   type ('a, 'b) matcher = 'a -> 'b -> bool
  45    *
  46    * version1: same but with a global variable holding the current binding
  47    *  BUT bug
  48    *   - can have multiple possibilities
  49    *   - globals sux
  50    *   - sometimes have to undo, cos if start match, then it binds,
  51    *     and if later it does not match, then must undo the first binds.
  52    *     ex: when match parameters, can  try to match, but then we found far
  53    *     later that the last argument of a function does not match
  54    *      => have to uando the binding !!!
  55    *      (can handle that too with a global, by saving the
  56    *      global, ... but sux)
  57    *   => better not use global
  58    *
  59    * version2:
  60    *    type ('a, 'b) matcher = binding -> 'a -> 'b -> binding list
  61    *
  62    * Empty list mean failure (let matchfailure = []).
  63    * To be able to have pretty code, have to use partial application
  64    * powa, and so the type is in fact
  65    *
  66    * version3:
  67    *    type ('a, 'b) matcher =  'a -> 'b -> binding -> binding list
  68    *
  69    * Then by defining the correct combinators, can have quite pretty code (that
  70    * looks like the clean code of version0).
  71    *
  72    * opti: return a lazy list of possible matchs ?
  73    *
  74    * version4: type tin = Lib_engine.metavars_binding
  75    *)
  76
  77   (* ------------------------------------------------------------------------*)
  78   (* Standard type and operators  *)
  79   (* ------------------------------------------------------------------------*)
  80
  81   type tin = {
  82     extra: xinfo;
  83     binding: Lib_engine.metavars_binding;
  84     binding0: Lib_engine.metavars_binding; (* inherited bindings *)
  85   }
  86   (* 'x is a ('a * 'b) but in fact dont care about 'b, we just tag the SP *)
  87   (* opti? use set instead of list *)
  88   type 'x tout = ('x * Lib_engine.metavars_binding) list
  89
  90   type ('a, 'b) matcher = 'a -> 'b  -> tin -> ('a * 'b) tout
  91
  92   (* was >&&> *)
  93   let (>>=) m1 m2 = fun tin ->
  94     let xs = m1 tin in
  95     let xxs = xs +> List.map (fun ((a,b), binding) ->
  96       m2 a b {tin with binding = binding}
  97     ) in
  98     List.flatten xxs
  99
 100   (* Je compare les bindings retournés par les differentes branches.
 101    * Si la deuxieme branche amene a des bindings qui sont deja presents
 102    * dans la premiere branche, alors je ne les accepte pas.
 103    *
 104    * update: still useful now that julia better handle Exp directly via
 105    * ctl tricks using positions ?
 106    *)
 107   let (>|+|>) m1 m2 = fun tin ->
 108 (* CHOICE
 109       let xs = m1 tin in
 110       if null xs
 111       then m2 tin
 112       else xs
 113 *)
 114     let res1 = m1 tin in
 115     let res2 = m2 tin in
 116     let list_bindings_already = List.map snd res1 in
 117     res1 ++
 118       (res2 +> List.filter (fun (x, binding) ->
 119         not
 120           (list_bindings_already +> List.exists (fun already ->
 121             Lib_engine.equal_binding binding already))
 122       ))
 123
 124
 125
 126
 127   let (>||>) m1 m2 = fun tin ->
 128 (* CHOICE
 129       let xs = m1 tin in
 130       if null xs
 131       then m2 tin
 132       else xs
 133 *)
 134     (* opti? use set instead of list *)
 135     m1 tin ++ m2 tin
 136
 137
 138   let return res = fun tin ->
 139     [res, tin.binding]
 140
 141   let fail = fun tin ->
 142     []
 143
 144   let (>&&>) f m = fun tin ->
 145     if f tin
 146     then m tin
 147     else fail tin
 148
 149
 150   let mode = Cocci_vs_c.PatternMode
 151
 152   (* ------------------------------------------------------------------------*)
 153   (* Exp  *)
 154   (* ------------------------------------------------------------------------*)
 155   let cocciExp = fun expf expa node -> fun tin ->
 156
 157     let globals = ref [] in
 158     let bigf = {
 159       (* julia's style *)
 160       Visitor_c.default_visitor_c with
 161       Visitor_c.kexpr = (fun (k, bigf) expb ->
 162         match expf expa expb tin with
 163         | [] -> (* failed *) k expb
 164         | xs ->
 165             globals := xs @ !globals;
 166             if not !Flag_engine.disallow_nested_exps then k expb (* CHOICE *)
 167       );
 168       (* pad's style.
 169        * push2 expr globals;  k expr
 170        *  ...
 171        *  !globals +> List.fold_left (fun acc e -> acc >||> match_e_e expr e)
 172        * (return false)
 173        *
 174        *)
 175     }
 176     in
 177     Visitor_c.vk_node bigf node;
 178     !globals +> List.map (fun ((a, _exp), binding) ->
 179       (a, node), binding
 180     )
 181
 182   (* same as cocciExp, but for expressions in an expression, not expressions
 183      in a node *)
 184   let cocciExpExp = fun expf expa expb -> fun tin ->
 185
 186     let globals = ref [] in
 187     let bigf = {
 188       (* julia's style *)
 189       Visitor_c.default_visitor_c with
 190       Visitor_c.kexpr = (fun (k, bigf) expb ->
 191         match expf expa expb tin with
 192         | [] -> (* failed *) k expb
 193         | xs ->
 194             globals := xs @ !globals;
 195             if not !Flag_engine.disallow_nested_exps then k expb (* CHOICE *)
 196       );
 197       (* pad's style.
 198        * push2 expr globals;  k expr
 199        *  ...
 200        *  !globals +> List.fold_left (fun acc e -> acc >||> match_e_e expr e)
 201        * (return false)
 202        *
 203        *)
 204     }
 205     in
 206     Visitor_c.vk_expr bigf expb;
 207     !globals +> List.map (fun ((a, _exp), binding) ->
 208       (a, expb), binding
 209     )
 210
 211   let cocciTy = fun expf expa node -> fun tin ->
 212
 213     let globals = ref [] in
 214     let bigf = {
 215       Visitor_c.default_visitor_c with
 216         Visitor_c.ktype = (fun (k, bigf) expb ->
 217         match expf expa expb tin with
 218         | [] -> (* failed *) k expb
 219         | xs -> globals := xs @ !globals);
 220
 221     }
 222     in
 223     Visitor_c.vk_node bigf node;
 224     !globals +> List.map (fun ((a, _exp), binding) ->
 225       (a, node), binding
 226     )
 227
 228   let cocciInit = fun expf expa node -> fun tin ->
 229
 230     let globals = ref [] in
 231     let bigf = {
 232       Visitor_c.default_visitor_c with
 233         Visitor_c.kini = (fun (k, bigf) expb ->
 234         match expf expa expb tin with
 235         | [] -> (* failed *) k expb
 236         | xs -> globals := xs @ !globals);
 237
 238     }
 239     in
 240     Visitor_c.vk_node bigf node;
 241     !globals +> List.map (fun ((a, _exp), binding) ->
 242       (a, node), binding
 243     )
 244
 245
 246   (* ------------------------------------------------------------------------*)
 247   (* Distribute mcode *)
 248   (* ------------------------------------------------------------------------*)
 249   let tag_mck_pos mck posmck =
 250     match mck with
 251     | Ast_cocci.PLUS -> Ast_cocci.PLUS
 252     | Ast_cocci.CONTEXT (pos, xs) ->
 253         assert (pos = Ast_cocci.NoPos || pos = Ast_cocci.DontCarePos);
 254         Ast_cocci.CONTEXT (posmck, xs)
 255     | Ast_cocci.MINUS (pos, xs) ->
 256         assert (pos = Ast_cocci.NoPos || pos = Ast_cocci.DontCarePos);
 257         Ast_cocci.MINUS (posmck, xs)
 258
 259
 260   let tag_mck_pos_mcode (x,info,mck,pos) posmck stuff = fun tin ->
 261     [((x, info, tag_mck_pos mck posmck, pos),stuff), tin.binding]
 262
 263
 264   let distrf (ii_of_x_f) =
 265     fun mcode x -> fun tin ->
 266     let (max, min) = Lib_parsing_c.max_min_by_pos (ii_of_x_f x)
 267     in
 268     let posmck = Ast_cocci.FixPos (min, max) (* subtil: and not max, min !!*)
 269     in
 270     tag_mck_pos_mcode mcode posmck x tin
 271
 272   let distrf_e    = distrf (Lib_parsing_c.ii_of_expr)
 273   let distrf_args = distrf (Lib_parsing_c.ii_of_args)
 274   let distrf_type = distrf (Lib_parsing_c.ii_of_type)
 275   let distrf_param = distrf (Lib_parsing_c.ii_of_param)
 276   let distrf_params = distrf (Lib_parsing_c.ii_of_params)
 277   let distrf_ini   = distrf (Lib_parsing_c.ii_of_ini)
 278   let distrf_node   = distrf (Lib_parsing_c.ii_of_node)
 279   let distrf_struct_fields   = distrf (Lib_parsing_c.ii_of_struct_fields)
 280   let distrf_cst = distrf (Lib_parsing_c.ii_of_cst)
 281   let distrf_define_params = distrf (Lib_parsing_c.ii_of_define_params)
 282
 283
 284   (* ------------------------------------------------------------------------*)
 285   (* Constraints on metavariable values *)
 286   (* ------------------------------------------------------------------------*)
 287   let check_constraints matcher constraints exp = fun f tin ->
 288     let rec loop = function
 289         [] -> f () tin (* success *)
 290       | c::cs ->
 291           match matcher c exp tin with
 292             [] (* failure *) -> loop cs
 293           | _ (* success *) -> fail tin in
 294     loop constraints
 295
 296   let check_pos_constraints constraints pvalu f tin =
 297     check_constraints
 298       (fun c exp tin ->
 299         let success = [[]] in
 300         let failure = [] in
 301         (* relies on the fact that constraints on pos variables must refer to
 302            inherited variables *)
 303         (match Common.optionise (fun () -> tin.binding0 +> List.assoc c) with
 304           Some valu' ->
 305             if Cocci_vs_c.equal_metavarval exp valu'
 306             then success else failure
 307         | None ->
 308             (* if the variable is not there, it puts no constraints *)
 309             (* not sure this is still useful *)
 310             failure))
 311       constraints pvalu f tin
 312
 313   (* ------------------------------------------------------------------------*)
 314   (* Environment *)
 315   (* ------------------------------------------------------------------------*)
 316   (* pre: if have declared a new metavar that hide another one, then
 317    * must be passed with a binding that deleted this metavar
 318    *
 319    * Here we dont use the keep argument of julia. cf f(X,X), J'ai
 320    * besoin de garder le X en interne, meme si julia s'en fout elle du
 321    * X et qu'elle a mis X a DontSaved.
 322    *)
 323   let check_add_metavars_binding strip _keep inherited = fun (k, valu) tin ->
 324     if inherited
 325     then
 326       match Common.optionise (fun () -> tin.binding0 +> List.assoc k) with
 327       | Some (valu') ->
 328           if Cocci_vs_c.equal_metavarval valu valu'
 329           then Some tin.binding
 330           else None
 331       | None -> None
 332     else
 333       match Common.optionise (fun () -> tin.binding +> List.assoc k) with
 334       | Some (valu') ->
 335           if Cocci_vs_c.equal_metavarval valu valu'
 336           then Some tin.binding
 337           else None
 338
 339       | None ->
 340           let valu' =
 341             match valu with
 342               Ast_c.MetaIdVal a        -> Ast_c.MetaIdVal a
 343             | Ast_c.MetaFuncVal a      -> Ast_c.MetaFuncVal a
 344             | Ast_c.MetaLocalFuncVal a -> Ast_c.MetaLocalFuncVal a (*more?*)
 345             | Ast_c.MetaExprVal a ->
 346                 Ast_c.MetaExprVal
 347                   (if strip
 348                   then Lib_parsing_c.al_expr a
 349                   else Lib_parsing_c.semi_al_expr a)
 350             | Ast_c.MetaExprListVal a ->
 351                 Ast_c.MetaExprListVal
 352                   (if strip
 353                   then Lib_parsing_c.al_arguments a
 354                   else Lib_parsing_c.semi_al_arguments a)
 355
 356             | Ast_c.MetaStmtVal a ->
 357                 Ast_c.MetaStmtVal
 358                   (if strip
 359                   then Lib_parsing_c.al_statement a
 360                   else Lib_parsing_c.semi_al_statement a)
 361             | Ast_c.MetaTypeVal a ->
 362                 Ast_c.MetaTypeVal
 363                   (if strip
 364                   then Lib_parsing_c.al_type a
 365                   else Lib_parsing_c.semi_al_type a)
 366
 367             | Ast_c.MetaListlenVal a -> Ast_c.MetaListlenVal a
 368
 369             | Ast_c.MetaParamVal a -> failwith "not handling MetaParamVal"
 370             | Ast_c.MetaParamListVal a ->
 371                 Ast_c.MetaParamListVal
 372                   (if strip
 373                   then Lib_parsing_c.al_params a
 374                   else Lib_parsing_c.semi_al_params a)
 375
 376             | Ast_c.MetaPosVal (pos1,pos2) -> Ast_c.MetaPosVal (pos1,pos2)
 377             | Ast_c.MetaPosValList l -> Ast_c.MetaPosValList l
 378           in Some (tin.binding +> Common.insert_assoc (k, valu'))
 379
 380   let envf keep inherited = fun (k, valu, get_max_min) f tin ->
 381     let x = Ast_cocci.unwrap_mcode k in
 382     match check_add_metavars_binding true keep inherited (x, valu) tin with
 383     | Some binding ->
 384         let new_tin = {tin with binding = binding} in
 385         (match Ast_cocci.get_pos_var k with
 386           Ast_cocci.MetaPos(name,constraints,per,keep,inherited) ->
 387             let pvalu =
 388               let (file,current_element,min,max) = get_max_min() in
 389               Ast_c.MetaPosValList[(file,current_element,min,max)] in
 390             (* check constraints.  success means that there is a match with
 391                one of the constraints, which will ultimately result in
 392                failure. *)
 393             check_pos_constraints constraints pvalu
 394               (function () ->
 395                 (* constraints are satisfied, now see if we are compatible
 396                    with existing bindings *)
 397                 function new_tin ->
 398                   let x = Ast_cocci.unwrap_mcode name in
 399                   (match
 400                     check_add_metavars_binding false keep inherited (x, pvalu)
 401                       new_tin with
 402                   | Some binding ->
 403                       f () {new_tin with binding = binding}
 404                   | None -> fail tin))
 405               new_tin
 406         | Ast_cocci.NoMetaPos -> f () new_tin)
 407     | None -> fail tin
 408
 409   (* ------------------------------------------------------------------------*)
 410   (* Environment, allbounds *)
 411   (* ------------------------------------------------------------------------*)
 412   (* all referenced inherited variables have to be bound. This would
 413    * be naturally checked for the minus or context ones in the
 414    * matching process, but have to check the plus ones as well. The
 415    * result of get_inherited contains all of these, but the potential
 416    * redundant checking for the minus and context ones is probably not
 417    * a big deal. If it's a problem, could fix free_vars to distinguish
 418    * between + variables and the other ones. *)
 419
 420   let (all_bound : Ast_cocci.meta_name list -> tin -> bool) = fun l tin ->
 421     l +> List.for_all (fun inhvar ->
 422       match Common.optionise (fun () -> tin.binding0 +> List.assoc inhvar) with
 423       | Some _ -> true
 424       | None -> false
 425     )
 426
 427   let optional_storage_flag f = fun tin ->
 428     f (tin.extra.optional_storage_iso) tin
 429
 430   let optional_qualifier_flag f = fun tin ->
 431     f (tin.extra.optional_qualifier_iso) tin
 432
 433   let value_format_flag f = fun tin ->
 434     f (tin.extra.value_format_iso) tin
 435
 436
 437   (* ------------------------------------------------------------------------*)
 438   (* Tokens *)
 439   (* ------------------------------------------------------------------------*)
 440   let tokenf ia ib = fun tin ->
 441     let pos = Ast_c.info_to_fixpos ib in
 442     let posmck = Ast_cocci.FixPos (pos, pos) in
 443     let finish tin = tag_mck_pos_mcode ia posmck ib tin in
 444     match Ast_cocci.get_pos_var ia with
 445       Ast_cocci.MetaPos(name,constraints,per,keep,inherited) ->
 446         let mpos = Lib_parsing_c.lin_col_by_pos [ib] in
 447         let pvalu = Ast_c.MetaPosValList [mpos] in
 448         check_pos_constraints constraints pvalu
 449           (function () ->
 450             (* constraints are satisfied, now see if we are compatible
 451                with existing bindings *)
 452             function new_tin ->
 453               let x = Ast_cocci.unwrap_mcode name in
 454               (match
 455                 check_add_metavars_binding false keep inherited (x, pvalu) tin
 456               with
 457                 Some binding -> finish {tin with binding = binding}
 458               | None -> fail tin))
 459           tin
 460     | _ -> finish tin
 461
 462   let tokenf_mck mck ib = fun tin ->
 463     let pos = Ast_c.info_to_fixpos ib in
 464     let posmck = Ast_cocci.FixPos (pos, pos) in
 465     [(tag_mck_pos mck posmck, ib), tin.binding]
 466
 467 end
 468
 469 (*****************************************************************************)
 470 (* Entry point  *)
 471 (*****************************************************************************)
 472 module MATCH  = Cocci_vs_c.COCCI_VS_C (XMATCH)
 473
 474
 475 let match_re_node2 dropped_isos a b binding0 =
 476
 477   let tin = {
 478     XMATCH.extra = {
 479       optional_storage_iso   = not(List.mem "optional_storage"   dropped_isos);
 480       optional_qualifier_iso = not(List.mem "optional_qualifier" dropped_isos);
 481       value_format_iso       = not(List.mem "value_format"       dropped_isos);
 482     };
 483     XMATCH.binding = [];
 484     XMATCH.binding0 = binding0;
 485   } in
 486
 487   MATCH.rule_elem_node a b tin
 488   (* take only the tagged-SP, the 'a' *)
 489   +> List.map (fun ((a,_b), binding) -> a, binding)
 490
 491
 492 let match_re_node a b c d =
 493   Common.profile_code "Pattern3.match_re_node"
 494     (fun () -> match_re_node2 a b c d)