popl/insert_befaft.ml

   1 (*
   2  * Copyright 2005-2010, Ecole des Mines de Nantes, University of Copenhagen
   3  * Yoann Padioleau, Julia Lawall, Rene Rydhof Hansen, Henrik Stuart, Gilles Muller, Nicolas Palix
   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 (*
  24  * Copyright 2005-2010, Ecole des Mines de Nantes, University of Copenhagen
  25  * Yoann Padioleau, Julia Lawall, Rene Rydhof Hansen, Henrik Stuart, Gilles Muller, Nicolas Palix
  26  * This file is part of Coccinelle.
  27  *
  28  * Coccinelle is free software: you can redistribute it and/or modify
  29  * it under the terms of the GNU General Public License as published by
  30  * the Free Software Foundation, according to version 2 of the License.
  31  *
  32  * Coccinelle is distributed in the hope that it will be useful,
  33  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  34  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  35  * GNU General Public License for more details.
  36  *
  37  * You should have received a copy of the GNU General Public License
  38  * along with Coccinelle.  If not, see <http://www.gnu.org/licenses/>.
  39  *
  40  * The authors reserve the right to distribute this or future versions of
  41  * Coccinelle under other licenses.
  42  *)
  43
  44
  45 module Past = Ast_popl
  46
  47 (* --------------------------------------------------------------------- *)
  48
  49 let rec get_before a = function
  50     Past.Seq(elem,seq) ->
  51       let (elem,ea) = get_before_element a elem in
  52       let (seq,sla) = get_before ea seq in
  53       (Past.Seq(elem,seq),sla)
  54   | Past.Empty -> (Past.Empty,a)
  55   | Past.SExists(var,seq) -> failwith "not possible"
  56
  57 and get_before_element a = function
  58     Past.Term(term) as s -> (s,[s])
  59   | Past.Or(seq1,seq2) ->
  60       let (seq1,seq1a) = get_before a seq1 in
  61       let (seq2,seq2a) = get_before a seq2 in
  62       (Past.Or(seq1,seq2),Common.union_set seq1a seq2a)
  63   | Past.DInfo(dots,_,seq_aft) ->
  64       let dots = get_before_dots a dots in
  65       (Past.DInfo(dots,a,seq_aft),a)
  66   | Past.EExists(var,seq) -> failwith "not possible"
  67
  68 and get_before_dots a = function
  69     Past.Dots -> Past.Dots
  70   | Past.Nest(seq) ->
  71       let (seq,_) = get_before a seq in
  72       Past.Nest(seq)
  73   | Past.When(dots,seq) ->
  74       let dots = get_before_dots a dots in
  75       let (seq,_) = get_before [] seq in
  76       Past.When(dots,seq)
  77   | Past.DExists(var,dots) -> failwith "not possible"
  78
  79 (* --------------------------------------------------------------------- *)
  80
  81 let rec get_after a = function
  82     Past.Seq(elem,seq) ->
  83       let (seq,sla) = get_after a seq in
  84       let (elem,ea) = get_after_element sla elem in
  85       (Past.Seq(elem,seq),ea)
  86   | Past.Empty -> (Past.Empty,a)
  87   | Past.SExists(var,seq) -> failwith "not possible"
  88
  89 and get_after_element a = function
  90     Past.Term(term) as s -> (s,[s])
  91   | Past.Or(seq1,seq2) ->
  92       let (seq1,seq1a) = get_after a seq1 in
  93       let (seq2,seq2a) = get_after a seq2 in
  94       (Past.Or(seq1,seq2),Common.union_set seq1a seq2a)
  95   | Past.DInfo(dots,seq_bef,_) ->
  96       let dots = get_after_dots a dots in
  97       (Past.DInfo(dots,seq_bef,a),a)
  98   | Past.EExists(var,seq) -> failwith "not possible"
  99
 100 and get_after_dots a = function
 101     Past.Dots -> Past.Dots
 102   | Past.Nest(seq) ->
 103       let (seq,_) = get_after (Common.union_set (get_first [] seq) a) seq in
 104       Past.Nest(seq)
 105   | Past.When(dots,seq) ->
 106       let dots = get_after_dots a dots in
 107       let (seq,_) = get_after [] seq in
 108       Past.When(dots,seq)
 109   | Past.DExists(var,dots) -> failwith "not possible"
 110
 111 (* --------------------------------------------------------------------- *)
 112 (* like get_after, but just returns the a component; doesn't modify the term *)
 113
 114 and get_first a = function
 115     Past.Seq(elem,seq) ->
 116       let sla = get_first a seq in
 117       let ea  = get_first_element sla elem in
 118       ea
 119   | Past.Empty -> a
 120   | Past.SExists(var,seq) -> failwith "not possible"
 121
 122 and get_first_element a = function
 123     Past.Term(term) as s -> [s]
 124   | Past.Or(seq1,seq2) ->
 125       Common.union_set (get_first a seq1) (get_first a seq2)
 126   | Past.DInfo(dots,_,_) -> a
 127   | Past.EExists(var,seq) -> failwith "not possible"
 128
 129 (* --------------------------------------------------------------------- *)
 130 (* Entry point *)
 131
 132 let insert_befaft sl =
 133   let (sl,_) = get_before [] sl in
 134   let (sl,_) = get_after [] sl in
 135   sl