parsing_cocci/unitary_ast0.ml

   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 (* find unitary metavariables *)
  24 module Ast0 = Ast0_cocci
  25 module Ast = Ast_cocci
  26 module V0 = Visitor_ast0
  27 module VT0 = Visitor_ast0_types
  28
  29 let set_minus s minus = List.filter (function n -> not (List.mem n minus)) s
  30
  31 let rec nub = function
  32     [] -> []
  33   | (x::xs) when (List.mem x xs) -> nub xs
  34   | (x::xs) -> x::(nub xs)
  35
  36 (* ----------------------------------------------------------------------- *)
  37 (* Find the variables that occur free and occur free in a unitary way *)
  38
  39 (* take everything *)
  40 let minus_checker name = let id = Ast0.unwrap_mcode name in [id]
  41
  42 (* take only what is in the plus code *)
  43 let plus_checker (nm,_,_,mc,_,_) =
  44   match mc with Ast0.PLUS -> [nm] | _ -> []
  45
  46 let get_free checker t =
  47   let bind x y = x @ y in
  48   let option_default = [] in
  49
  50   (* considers a single list *)
  51   let collect_unitary_nonunitary free_usage =
  52     let free_usage = List.sort compare free_usage in
  53     let rec loop1 todrop = function
  54         [] -> []
  55       | (x::xs) as all -> if x = todrop then loop1 todrop xs else all in
  56     let rec loop2 = function
  57         [] -> ([],[])
  58       | [x] -> ([x],[])
  59       | x::y::xs ->
  60           if x = y
  61           then
  62             let (unitary,non_unitary) = loop2(loop1 x xs) in
  63             (unitary,x::non_unitary)
  64           else
  65             let (unitary,non_unitary) = loop2 (y::xs) in
  66             (x::unitary,non_unitary) in
  67     loop2 free_usage in
  68
  69   (* considers a list of lists *)
  70   let detect_unitary_frees l =
  71     let (unitary,nonunitary) =
  72       List.split (List.map collect_unitary_nonunitary l) in
  73     let unitary = nub (List.concat unitary) in
  74     let nonunitary = nub (List.concat nonunitary) in
  75     let unitary =
  76       List.filter (function x -> not (List.mem x nonunitary)) unitary in
  77     unitary@nonunitary@nonunitary in
  78
  79   let whencode afn bfn expression = function
  80       Ast0.WhenNot(a) -> afn a
  81     | Ast0.WhenAlways(b) -> bfn b
  82     | Ast0.WhenModifier(_) -> option_default
  83     | Ast0.WhenNotTrue(a) -> expression a
  84     | Ast0.WhenNotFalse(a) -> expression a in
  85
  86   let ident r k i =
  87     match Ast0.unwrap i with
  88       Ast0.MetaId(name,_,_) | Ast0.MetaFunc(name,_,_)
  89     | Ast0.MetaLocalFunc(name,_,_) -> checker name
  90     | _ -> k i in
  91
  92   let expression r k e =
  93     match Ast0.unwrap e with
  94       Ast0.MetaErr(name,_,_) | Ast0.MetaExpr(name,_,_,_,_)
  95     | Ast0.MetaExprList(name,_,_) -> checker name
  96     | Ast0.DisjExpr(starter,expr_list,mids,ender) ->
  97         detect_unitary_frees(List.map r.VT0.combiner_rec_expression expr_list)
  98     | _ -> k e in
  99
 100   let typeC r k t =
 101     match Ast0.unwrap t with
 102       Ast0.MetaType(name,_) -> checker name
 103     | Ast0.DisjType(starter,types,mids,ender) ->
 104         detect_unitary_frees(List.map r.VT0.combiner_rec_typeC types)
 105     | _ -> k t in
 106
 107   let parameter r k p =
 108     match Ast0.unwrap p with
 109       Ast0.MetaParam(name,_) | Ast0.MetaParamList(name,_,_) -> checker name
 110     | _ -> k p in
 111
 112   let declaration r k d =
 113     match Ast0.unwrap d with
 114       Ast0.DisjDecl(starter,decls,mids,ender) ->
 115         detect_unitary_frees(List.map r.VT0.combiner_rec_declaration decls)
 116     | _ -> k d in
 117
 118   let statement r k s =
 119     match Ast0.unwrap s with
 120       Ast0.MetaStmt(name,_) | Ast0.MetaStmtList(name,_) -> checker name
 121     | Ast0.Disj(starter,stmt_list,mids,ender) ->
 122         detect_unitary_frees
 123           (List.map r.VT0.combiner_rec_statement_dots stmt_list)
 124     | Ast0.Nest(starter,stmt_dots,ender,whn,multi) ->
 125         bind (r.VT0.combiner_rec_statement_dots stmt_dots)
 126           (detect_unitary_frees
 127              (List.map
 128                 (whencode
 129                    r.VT0.combiner_rec_statement_dots
 130                    r.VT0.combiner_rec_statement
 131                     r.VT0.combiner_rec_expression)
 132                 whn))
 133     | Ast0.Dots(d,whn) | Ast0.Circles(d,whn) | Ast0.Stars(d,whn) ->
 134         detect_unitary_frees
 135           (List.map
 136              (whencode
 137                 r.VT0.combiner_rec_statement_dots r.VT0.combiner_rec_statement
 138                 r.VT0.combiner_rec_expression)
 139              whn)
 140     | _ -> k s in
 141
 142   let res = V0.combiner bind option_default
 143       {V0.combiner_functions with
 144         VT0.combiner_identfn = ident;
 145         VT0.combiner_exprfn = expression;
 146         VT0.combiner_tyfn = typeC;
 147         VT0.combiner_paramfn = parameter;
 148         VT0.combiner_declfn = declaration;
 149         VT0.combiner_stmtfn = statement} in
 150
 151   collect_unitary_nonunitary
 152     (List.concat (List.map res.VT0.combiner_rec_top_level t))
 153
 154 (* ----------------------------------------------------------------------- *)
 155 (* update the variables that are unitary *)
 156
 157 let update_unitary unitary =
 158   let is_unitary name =
 159     match (List.mem (Ast0.unwrap_mcode name) unitary,
 160            !Flag.sgrep_mode2, Ast0.get_mcode_mcodekind name) with
 161       (true,true,_) | (true,_,Ast0.CONTEXT(_)) -> Ast0.PureContext
 162     | (true,_,_) -> Ast0.Pure
 163     | (false,true,_) | (false,_,Ast0.CONTEXT(_)) -> Ast0.Context
 164     | (false,_,_) -> Ast0.Impure in
 165
 166   let ident r k i =
 167     match Ast0.unwrap i with
 168       Ast0.MetaId(name,constraints,_) ->
 169         Ast0.rewrap i (Ast0.MetaId(name,constraints,is_unitary name))
 170     | Ast0.MetaFunc(name,constraints,_) ->
 171         Ast0.rewrap i (Ast0.MetaFunc(name,constraints,is_unitary name))
 172     | Ast0.MetaLocalFunc(name,constraints,_) ->
 173         Ast0.rewrap i (Ast0.MetaLocalFunc(name,constraints,is_unitary name))
 174     | _ -> k i in
 175
 176   let expression r k e =
 177     match Ast0.unwrap e with
 178       Ast0.MetaErr(name,constraints,_) ->
 179         Ast0.rewrap e (Ast0.MetaErr(name,constraints,is_unitary name))
 180     | Ast0.MetaExpr(name,constraints,ty,form,_) ->
 181         Ast0.rewrap e (Ast0.MetaExpr(name,constraints,ty,form,is_unitary name))
 182     | Ast0.MetaExprList(name,lenname,_) ->
 183         Ast0.rewrap e (Ast0.MetaExprList(name,lenname,is_unitary name))
 184     | _ -> k e in
 185
 186   let typeC r k t =
 187     match Ast0.unwrap t with
 188       Ast0.MetaType(name,_) ->
 189         Ast0.rewrap t (Ast0.MetaType(name,is_unitary name))
 190     | _ -> k t in
 191
 192   let parameter r k p =
 193     match Ast0.unwrap p with
 194       Ast0.MetaParam(name,_) ->
 195         Ast0.rewrap p (Ast0.MetaParam(name,is_unitary name))
 196     | Ast0.MetaParamList(name,lenname,_) ->
 197         Ast0.rewrap p (Ast0.MetaParamList(name,lenname,is_unitary name))
 198     | _ -> k p in
 199
 200   let statement r k s =
 201     match Ast0.unwrap s with
 202       Ast0.MetaStmt(name,_) ->
 203         Ast0.rewrap s (Ast0.MetaStmt(name,is_unitary name))
 204     | Ast0.MetaStmtList(name,_) ->
 205         Ast0.rewrap s (Ast0.MetaStmtList(name,is_unitary name))
 206     | _ -> k s in
 207
 208   let res = V0.rebuilder
 209       {V0.rebuilder_functions with
 210         VT0.rebuilder_identfn = ident;
 211         VT0.rebuilder_exprfn = expression;
 212         VT0.rebuilder_tyfn = typeC;
 213         VT0.rebuilder_paramfn = parameter;
 214         VT0.rebuilder_stmtfn = statement} in
 215
 216   List.map res.VT0.rebuilder_rec_top_level
 217
 218 (* ----------------------------------------------------------------------- *)
 219
 220 let rec split3 = function
 221     [] -> ([],[],[])
 222   | (a,b,c)::xs -> let (l1,l2,l3) = split3 xs in (a::l1,b::l2,c::l3)
 223
 224 let rec combine3 = function
 225     ([],[],[]) -> []
 226   | (a::l1,b::l2,c::l3) -> (a,b,c) :: combine3 (l1,l2,l3)
 227   | _ -> failwith "not possible"
 228
 229 (* ----------------------------------------------------------------------- *)
 230 (* process all rules *)
 231
 232 let do_unitary rules =
 233   let rec loop = function
 234       [] -> ([],[])
 235     | (r::rules) ->
 236       match r with
 237         Ast0.ScriptRule (_,_,_,_)
 238       | Ast0.InitialScriptRule (_,_) | Ast0.FinalScriptRule (_,_) ->
 239           let (x,rules) = loop rules in
 240           (x, r::rules)
 241       | Ast0.CocciRule ((minus,metavars,chosen_isos),((plus,_) as plusz),rt) ->
 242           let mm1 = List.map Ast.get_meta_name metavars in
 243           let (used_after, rest) = loop rules in
 244           let (m_unitary, m_nonunitary) = get_free minus_checker minus in
 245           let (p_unitary, p_nonunitary) = get_free plus_checker plus in
 246           let p_free =
 247             if !Flag.sgrep_mode2 then []
 248             else p_unitary @ p_nonunitary in
 249           let (in_p, m_unitary) =
 250             List.partition (function x -> List.mem x p_free) m_unitary in
 251           let m_nonunitary = in_p @ m_nonunitary in
 252           let (m_unitary, not_local) =
 253             List.partition (function x -> List.mem x mm1) m_unitary in
 254           let m_unitary =
 255             List.filter (function x -> not (List.mem x used_after))
 256               m_unitary in
 257           let rebuilt = update_unitary m_unitary minus in
 258           (set_minus (m_nonunitary @ used_after) mm1,
 259              (Ast0.CocciRule
 260                 ((rebuilt, metavars, chosen_isos),plusz,rt))::rest) in
 261   let (_,rules) = loop rules in
 262   rules
 263
 264 (*
 265 let do_unitary minus plus =
 266   let (minus,metavars,chosen_isos) = split3 minus in
 267   let (plus,_) = List.split plus in
 268   let rec loop = function
 269       ([],[],[]) -> ([],[])
 270     | (mm1::metavars,m1::minus,p1::plus) ->
 271         let mm1 = List.map Ast.get_meta_name mm1 in
 272         let (used_after,rest) = loop (metavars,minus,plus) in
 273         let (m_unitary,m_nonunitary) = get_free minus_checker m1 in
 274         let (p_unitary,p_nonunitary) = get_free plus_checker p1 in
 275         let p_free =
 276           if !Flag.sgrep_mode2
 277           then []
 278           else p_unitary @ p_nonunitary in
 279         let (in_p,m_unitary) =
 280           List.partition (function x -> List.mem x p_free) m_unitary in
 281         let m_nonunitary = in_p@m_nonunitary in
 282         let (m_unitary,not_local) =
 283           List.partition (function x -> List.mem x mm1) m_unitary in
 284         let m_unitary =
 285           List.filter (function x -> not(List.mem x used_after)) m_unitary in
 286         let rebuilt = update_unitary m_unitary m1 in
 287         (set_minus (m_nonunitary @ used_after) mm1,
 288          rebuilt::rest)
 289     | _ -> failwith "not possible" in
 290   let (_,rules) = loop (metavars,minus,plus) in
 291   combine3 (rules,metavars,chosen_isos)
 292 *)