engine/pattern3.ml

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