popl/insert_quantifiers.ml

   1 (*
   2  * Copyright 2012, INRIA
   3  * Julia Lawall, Gilles Muller
   4  * Copyright 2010-2011, INRIA, University of Copenhagen
   5  * Julia Lawall, Rene Rydhof Hansen, Gilles Muller, Nicolas Palix
   6  * Copyright 2005-2009, Ecole des Mines de Nantes, University of Copenhagen
   7  * Yoann Padioleau, Julia Lawall, Rene Rydhof Hansen, Henrik Stuart, Gilles Muller, Nicolas Palix
   8  * This file is part of Coccinelle.
   9  *
  10  * Coccinelle is free software: you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License as published by
  12  * the Free Software Foundation, according to version 2 of the License.
  13  *
  14  * Coccinelle is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with Coccinelle.  If not, see <http://www.gnu.org/licenses/>.
  21  *
  22  * The authors reserve the right to distribute this or future versions of
  23  * Coccinelle under other licenses.
  24  *)
  25
  26
  27 module Ast = Ast_cocci
  28 module Past = Ast_popl
  29
  30 (* --------------------------------------------------------------------- *)
  31
  32 let rec fvs_sequence = function
  33     Past.Seq(elem,seq) ->
  34       Common.union_set (fvs_element elem) (fvs_sequence seq)
  35   | Past.Empty -> []
  36   | Past.SExists(var,seq) -> failwith "not possible"
  37
  38 and fvs_element = function
  39     Past.Term(term) -> Ast.get_fvs term
  40   | Past.Or(seq1,seq2) ->
  41       Common.union_set (fvs_sequence seq1) (fvs_sequence seq2)
  42   | Past.DInfo(dots,seq_bef,seq_aft) ->
  43       List.fold_left
  44         (function prev ->
  45           function cur ->
  46             Common.union_set (fvs_element cur) prev)
  47       (fvs_dots dots) seq_bef
  48   | Past.EExists(var,seq) -> failwith "not possible"
  49
  50 and fvs_dots = function
  51     Past.Dots -> []
  52   | Past.Nest(seq) -> fvs_sequence seq
  53   | Past.When(dots,seq) -> Common.union_set (fvs_dots dots) (fvs_sequence seq)
  54   | Past.DExists(var,dots) -> failwith "not possible"
  55
  56 (* --------------------------------------------------------------------- *)
  57
  58 let rec quant_sequence bound = function
  59     Past.Seq(elem,seq) ->
  60       let fe = fvs_element elem in
  61       let fs = fvs_sequence seq in
  62       let inter = Common.inter_set fe fs in
  63       let free = Common.minus_set inter bound in
  64       let new_bound = free @ bound in
  65       List.fold_right (function cur -> function rest -> Past.SExists(cur,rest))
  66         free (Past.Seq(quant_element new_bound elem,
  67                        quant_sequence new_bound seq))
  68   | Past.Empty -> Past.Empty
  69   | Past.SExists(var,seq) -> failwith "not possible"
  70
  71 and quant_element bound = function
  72     Past.Term(term) as x ->
  73       let free = Common.minus_set (fvs_element x) bound in
  74       List.fold_right (function cur -> function rest -> Past.EExists(cur,rest))
  75         free x
  76   | Past.Or(seq1,seq2) ->
  77       Past.Or(quant_sequence bound seq1,quant_sequence bound seq2)
  78   | Past.DInfo(dots,seq_bef,seq_aft) ->
  79       Past.DInfo(quant_dots bound dots,seq_bef,
  80                  List.map (quant_element bound) seq_aft)
  81   | Past.EExists(var,seq) -> failwith "not possible"
  82
  83 and quant_dots bound = function
  84     Past.Dots -> Past.Dots
  85   | Past.Nest(seq) -> Past.Nest(quant_sequence bound seq)
  86   | Past.When(dots,seq) ->
  87       let fd = fvs_dots dots in
  88       let fs = fvs_sequence seq in
  89       let inter = Common.inter_set fd fs in
  90       let free = Common.minus_set inter bound in
  91       let new_bound = free @ bound in
  92       List.fold_right (function cur -> function rest -> Past.DExists(cur,rest))
  93         free (Past.When(quant_dots new_bound dots,
  94                         quant_sequence new_bound seq))
  95   | Past.DExists(var,dots) -> failwith "not possible"
  96
  97 (* --------------------------------------------------------------------- *)
  98
  99 let insert_quantifiers x = quant_sequence [] x