parsing_cocci/unitary_ast0.ml

   1 (*
   2  * Copyright 2010, INRIA, University of Copenhagen
   3  * Julia Lawall, Rene Rydhof Hansen, Gilles Muller, Nicolas Palix
   4  * Copyright 2005-2009, Ecole des Mines de Nantes, University of Copenhagen
   5  * Yoann Padioleau, Julia Lawall, Rene Rydhof Hansen, Henrik Stuart, Gilles Muller, Nicolas Palix
   6  * This file is part of Coccinelle.
   7  *
   8  * Coccinelle is free software: you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation, according to version 2 of the License.
  11  *
  12  * Coccinelle is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Coccinelle.  If not, see <http://www.gnu.org/licenses/>.
  19  *
  20  * The authors reserve the right to distribute this or future versions of
  21  * Coccinelle under other licenses.
  22  *)
  23
  24
  25 (* find unitary metavariables *)
  26 module Ast0 = Ast0_cocci
  27 module Ast = Ast_cocci
  28 module V0 = Visitor_ast0
  29 module VT0 = Visitor_ast0_types
  30
  31 let set_minus s minus = List.filter (function n -> not (List.mem n minus)) s
  32
  33 let rec nub = function
  34     [] -> []
  35   | (x::xs) when (List.mem x xs) -> nub xs
  36   | (x::xs) -> x::(nub xs)
  37
  38 (* ----------------------------------------------------------------------- *)
  39 (* Find the variables that occur free and occur free in a unitary way *)
  40
  41 (* take everything *)
  42 let minus_checker name = let id = Ast0.unwrap_mcode name in [id]
  43
  44 (* take only what is in the plus code *)
  45 let plus_checker (nm,_,_,mc,_,_) =
  46   match mc with Ast0.PLUS _ -> [nm] | _ -> []
  47
  48 let get_free checker t =
  49   let bind x y = x @ y in
  50   let option_default = [] in
  51
  52   (* considers a single list *)
  53   let collect_unitary_nonunitary free_usage =
  54     let free_usage = List.sort compare free_usage in
  55     let rec loop1 todrop = function
  56         [] -> []
  57       | (x::xs) as all -> if x = todrop then loop1 todrop xs else all in
  58     let rec loop2 = function
  59         [] -> ([],[])
  60       | [x] -> ([x],[])
  61       | x::y::xs ->
  62           if x = y
  63           then
  64             let (unitary,non_unitary) = loop2(loop1 x xs) in
  65             (unitary,x::non_unitary)
  66           else
  67             let (unitary,non_unitary) = loop2 (y::xs) in
  68             (x::unitary,non_unitary) in
  69     loop2 free_usage in
  70
  71   (* considers a list of lists *)
  72   let detect_unitary_frees l =
  73     let (unitary,nonunitary) =
  74       List.split (List.map collect_unitary_nonunitary l) in
  75     let unitary = nub (List.concat unitary) in
  76     let nonunitary = nub (List.concat nonunitary) in
  77     let unitary =
  78       List.filter (function x -> not (List.mem x nonunitary)) unitary in
  79     unitary@nonunitary@nonunitary in
  80
  81   let whencode afn bfn expression = function
  82       Ast0.WhenNot(a) -> afn a
  83     | Ast0.WhenAlways(b) -> bfn b
  84     | Ast0.WhenModifier(_) -> option_default
  85     | Ast0.WhenNotTrue(a) -> expression a
  86     | Ast0.WhenNotFalse(a) -> expression a in
  87
  88   let ident r k i =
  89     match Ast0.unwrap i with
  90       Ast0.MetaId(name,_,_) | Ast0.MetaFunc(name,_,_)
  91     | Ast0.MetaLocalFunc(name,_,_) -> checker name
  92     | _ -> k i in
  93
  94   let expression r k e =
  95     match Ast0.unwrap e with
  96       Ast0.MetaErr(name,_,_) | Ast0.MetaExpr(name,_,_,_,_)
  97     | Ast0.MetaExprList(name,_,_) -> checker name
  98     | Ast0.DisjExpr(starter,expr_list,mids,ender) ->
  99         detect_unitary_frees(List.map r.VT0.combiner_rec_expression expr_list)
 100     | _ -> k e in
 101
 102   let typeC r k t =
 103     match Ast0.unwrap t with
 104       Ast0.MetaType(name,_) -> checker name
 105     | Ast0.DisjType(starter,types,mids,ender) ->
 106         detect_unitary_frees(List.map r.VT0.combiner_rec_typeC types)
 107     | _ -> k t in
 108
 109   let parameter r k p =
 110     match Ast0.unwrap p with
 111       Ast0.MetaParam(name,_) | Ast0.MetaParamList(name,_,_) -> checker name
 112     | _ -> k p in
 113
 114   let declaration r k d =
 115     match Ast0.unwrap d with
 116       Ast0.MetaDecl(name,_) | Ast0.MetaField(name,_) -> checker name
 117     | Ast0.DisjDecl(starter,decls,mids,ender) ->
 118         detect_unitary_frees(List.map r.VT0.combiner_rec_declaration decls)
 119     | _ -> k d in
 120
 121   let case_line r k c =
 122     match Ast0.unwrap c with
 123       Ast0.DisjCase(starter,case_lines,mids,ender) ->
 124         detect_unitary_frees(List.map r.VT0.combiner_rec_case_line case_lines)
 125     | _ -> k c in
 126
 127   let statement r k s =
 128     match Ast0.unwrap s with
 129       Ast0.MetaStmt(name,_) | Ast0.MetaStmtList(name,_) -> checker name
 130     | Ast0.Disj(starter,stmt_list,mids,ender) ->
 131         detect_unitary_frees
 132           (List.map r.VT0.combiner_rec_statement_dots stmt_list)
 133     | Ast0.Nest(starter,stmt_dots,ender,whn,multi) ->
 134         bind (r.VT0.combiner_rec_statement_dots stmt_dots)
 135           (detect_unitary_frees
 136              (List.map
 137                 (whencode
 138                    r.VT0.combiner_rec_statement_dots
 139                    r.VT0.combiner_rec_statement
 140                     r.VT0.combiner_rec_expression)
 141                 whn))
 142     | Ast0.Dots(d,whn) | Ast0.Circles(d,whn) | Ast0.Stars(d,whn) ->
 143         detect_unitary_frees
 144           (List.map
 145              (whencode
 146                 r.VT0.combiner_rec_statement_dots r.VT0.combiner_rec_statement
 147                 r.VT0.combiner_rec_expression)
 148              whn)
 149     | _ -> k s in
 150
 151   let res = V0.combiner bind option_default
 152       {V0.combiner_functions with
 153         VT0.combiner_identfn = ident;
 154         VT0.combiner_exprfn = expression;
 155         VT0.combiner_tyfn = typeC;
 156         VT0.combiner_paramfn = parameter;
 157         VT0.combiner_declfn = declaration;
 158         VT0.combiner_stmtfn = statement;
 159         VT0.combiner_casefn = case_line} in
 160
 161   collect_unitary_nonunitary
 162     (List.concat (List.map res.VT0.combiner_rec_top_level t))
 163
 164 (* ----------------------------------------------------------------------- *)
 165 (* update the variables that are unitary *)
 166
 167 let update_unitary unitary =
 168   let is_unitary name =
 169     match (List.mem (Ast0.unwrap_mcode name) unitary,
 170            !Flag.sgrep_mode2, Ast0.get_mcode_mcodekind name) with
 171       (true,true,_) | (true,_,Ast0.CONTEXT(_)) -> Ast0.PureContext
 172     | (true,_,_) -> Ast0.Pure
 173     | (false,true,_) | (false,_,Ast0.CONTEXT(_)) -> Ast0.Context
 174     | (false,_,_) -> Ast0.Impure in
 175
 176   let ident r k i =
 177     match Ast0.unwrap i with
 178       Ast0.MetaId(name,constraints,_) ->
 179         Ast0.rewrap i (Ast0.MetaId(name,constraints,is_unitary name))
 180     | Ast0.MetaFunc(name,constraints,_) ->
 181         Ast0.rewrap i (Ast0.MetaFunc(name,constraints,is_unitary name))
 182     | Ast0.MetaLocalFunc(name,constraints,_) ->
 183         Ast0.rewrap i (Ast0.MetaLocalFunc(name,constraints,is_unitary name))
 184     | _ -> k i in
 185
 186   let expression r k e =
 187     match Ast0.unwrap e with
 188       Ast0.MetaErr(name,constraints,_) ->
 189         Ast0.rewrap e (Ast0.MetaErr(name,constraints,is_unitary name))
 190     | Ast0.MetaExpr(name,constraints,ty,form,_) ->
 191         Ast0.rewrap e (Ast0.MetaExpr(name,constraints,ty,form,is_unitary name))
 192     | Ast0.MetaExprList(name,lenname,_) ->
 193         Ast0.rewrap e (Ast0.MetaExprList(name,lenname,is_unitary name))
 194     | _ -> k e in
 195
 196   let typeC r k t =
 197     match Ast0.unwrap t with
 198       Ast0.MetaType(name,_) ->
 199         Ast0.rewrap t (Ast0.MetaType(name,is_unitary name))
 200     | _ -> k t in
 201
 202   let parameter r k p =
 203     match Ast0.unwrap p with
 204       Ast0.MetaParam(name,_) ->
 205         Ast0.rewrap p (Ast0.MetaParam(name,is_unitary name))
 206     | Ast0.MetaParamList(name,lenname,_) ->
 207         Ast0.rewrap p (Ast0.MetaParamList(name,lenname,is_unitary name))
 208     | _ -> k p in
 209
 210   let statement r k s =
 211     match Ast0.unwrap s with
 212       Ast0.MetaStmt(name,_) ->
 213         Ast0.rewrap s (Ast0.MetaStmt(name,is_unitary name))
 214     | Ast0.MetaStmtList(name,_) ->
 215         Ast0.rewrap s (Ast0.MetaStmtList(name,is_unitary name))
 216     | _ -> k s in
 217
 218   let res = V0.rebuilder
 219       {V0.rebuilder_functions with
 220         VT0.rebuilder_identfn = ident;
 221         VT0.rebuilder_exprfn = expression;
 222         VT0.rebuilder_tyfn = typeC;
 223         VT0.rebuilder_paramfn = parameter;
 224         VT0.rebuilder_stmtfn = statement} in
 225
 226   List.map res.VT0.rebuilder_rec_top_level
 227
 228 (* ----------------------------------------------------------------------- *)
 229
 230 let rec split3 = function
 231     [] -> ([],[],[])
 232   | (a,b,c)::xs -> let (l1,l2,l3) = split3 xs in (a::l1,b::l2,c::l3)
 233
 234 let rec combine3 = function
 235     ([],[],[]) -> []
 236   | (a::l1,b::l2,c::l3) -> (a,b,c) :: combine3 (l1,l2,l3)
 237   | _ -> failwith "not possible"
 238
 239 (* ----------------------------------------------------------------------- *)
 240 (* process all rules *)
 241
 242 let do_unitary rules =
 243   let rec loop = function
 244       [] -> ([],[])
 245     | (r::rules) ->
 246       match r with
 247         Ast0.ScriptRule (_,_,_,_,_,_)
 248       | Ast0.InitialScriptRule (_,_,_,_) | Ast0.FinalScriptRule (_,_,_,_) ->
 249           let (x,rules) = loop rules in
 250           (x, r::rules)
 251       | Ast0.CocciRule ((minus,metavars,chosen_isos),((plus,_) as plusz),rt) ->
 252           let mm1 = List.map Ast.get_meta_name metavars in
 253           let (used_after, rest) = loop rules in
 254           let (m_unitary, m_nonunitary) = get_free minus_checker minus in
 255           let (p_unitary, p_nonunitary) = get_free plus_checker plus in
 256           let p_free =
 257             if !Flag.sgrep_mode2 then []
 258             else p_unitary @ p_nonunitary in
 259           let (in_p, m_unitary) =
 260             List.partition (function x -> List.mem x p_free) m_unitary in
 261           let m_nonunitary = in_p @ m_nonunitary in
 262           let (m_unitary, not_local) =
 263             List.partition (function x -> List.mem x mm1) m_unitary in
 264           let m_unitary =
 265             List.filter (function x -> not (List.mem x used_after))
 266               m_unitary in
 267           let rebuilt = update_unitary m_unitary minus in
 268           (set_minus (m_nonunitary @ used_after) mm1,
 269              (Ast0.CocciRule
 270                 ((rebuilt, metavars, chosen_isos),plusz,rt))::rest) in
 271   let (_,rules) = loop rules in
 272   rules
 273
 274 (*
 275 let do_unitary minus plus =
 276   let (minus,metavars,chosen_isos) = split3 minus in
 277   let (plus,_) = List.split plus in
 278   let rec loop = function
 279       ([],[],[]) -> ([],[])
 280     | (mm1::metavars,m1::minus,p1::plus) ->
 281         let mm1 = List.map Ast.get_meta_name mm1 in
 282         let (used_after,rest) = loop (metavars,minus,plus) in
 283         let (m_unitary,m_nonunitary) = get_free minus_checker m1 in
 284         let (p_unitary,p_nonunitary) = get_free plus_checker p1 in
 285         let p_free =
 286           if !Flag.sgrep_mode2
 287           then []
 288           else p_unitary @ p_nonunitary in
 289         let (in_p,m_unitary) =
 290           List.partition (function x -> List.mem x p_free) m_unitary in
 291         let m_nonunitary = in_p@m_nonunitary in
 292         let (m_unitary,not_local) =
 293           List.partition (function x -> List.mem x mm1) m_unitary in
 294         let m_unitary =
 295           List.filter (function x -> not(List.mem x used_after)) m_unitary in
 296         let rebuilt = update_unitary m_unitary m1 in
 297         (set_minus (m_nonunitary @ used_after) mm1,
 298          rebuilt::rest)
 299     | _ -> failwith "not possible" in
 300   let (_,rules) = loop (metavars,minus,plus) in
 301   combine3 (rules,metavars,chosen_isos)
 302 *)