contrib/pep8analysis/src/flow_analysis/framework.nit

   1 import cfg
   2 import advanced_collections
   3
   4 class FlowAnalysis[S]
   5         super Visitor
   6
   7         var current_in:  nullable S writable
   8         var current_out: nullable S writable
   9
  10         fun in_set(bb: BasicBlock): nullable S is abstract
  11         fun out_set(bb: BasicBlock): nullable S is abstract
  12         fun in_set=(bb: BasicBlock, s: S) is abstract
  13         fun out_set=(bb: BasicBlock, s: S) is abstract
  14
  15         init
  16         do
  17                 current_in = default_in_set
  18                 current_out = default_in_set
  19         end
  20
  21         redef fun visit( node ) do node.visit_all(self)
  22
  23         # If false, it is a backwards analysis
  24         fun is_forward: Bool is abstract
  25
  26         # ex: do return in1.union( in2 )
  27         # ex: do return in1.intersection( in2 )
  28         fun merge( in1, in2: nullable S): nullable S is abstract
  29
  30         fun default_in_set: nullable S do return null
  31         fun empty_set: S is abstract
  32
  33         fun analyze(cfg: CFG)
  34         do
  35                 # set defaults
  36                 var current_in: nullable S
  37                 var current_out: nullable S
  38
  39                 # set current input as default start case
  40                 var todo = new List[BasicBlock]
  41                 todo.add_all(cfg.blocks)
  42
  43                 # iterate until fixed point reached
  44                 while not todo.is_empty do
  45
  46                         var block = todo.shift
  47
  48                         if block == cfg.start then
  49                                 continue
  50                         else if block.predecessors.is_empty then
  51                                 # get default in (the most safe one)
  52                                 current_in = default_in_set
  53                         else
  54                                 current_in = out_set(block.predecessors.first)
  55                                 for l in [1..block.predecessors.length[ do
  56                                         var b = block.predecessors[l]
  57                                         current_in = merge(current_in, out_set(b))
  58                                 end
  59                         end
  60
  61                         if current_in != null then
  62                                 in_set(block) = current_in.as(not null)
  63                         else
  64                                 continue
  65                         end
  66
  67                         if block == cfg.finish then continue
  68
  69                         var old_out = out_set(block)
  70                         for line in block.lines do
  71                                 self.current_in = current_in.as(not null)
  72                                 self.current_out = empty_set
  73                                 pre_line_visit(line)
  74                                 enter_visit(line)
  75                                 post_line_visit(line)
  76                                 current_out = self.current_out
  77                                 current_in = self.current_out.as(not null)
  78                                 #self.current_in = current_in
  79                         end
  80
  81                         current_out = self.current_out
  82                         if old_out != current_out then
  83                                 out_set(block) = current_out.as(not null)
  84                                 if is_forward then
  85                                         for b in block.successors do todo.add(b)
  86                                 else
  87                                         for b in block.predecessors do todo.add(b)
  88                                 end
  89                         end
  90                 end
  91         end
  92
  93         fun pre_line_visit(l: ALine) do end
  94         fun post_line_visit(l: ALine) do end
  95 end
  96
  97 class FineFlowAnalysis[V]
  98         super FlowAnalysis[V]
  99
 100         redef fun in_set(bb)
 101         do
 102                 if bb.lines.is_empty then return backup_in(bb)
 103                 return line_in( bb.lines.first )
 104         end
 105
 106         redef fun in_set=(bb, v)
 107         do
 108                 if bb.lines.is_empty then
 109                         backup_in(bb) = v
 110                 else line_in( bb.lines.first ) = v
 111         end
 112
 113         redef fun out_set(bb)
 114         do
 115                 if bb.lines.is_empty then return backup_out(bb)
 116                 return line_out( bb.lines.last )
 117         end
 118
 119         redef fun out_set=(bb, v)
 120         do
 121                 if bb.lines.is_empty then
 122                         backup_out(bb) = v
 123                 else line_out( bb.lines.last ) = v
 124         end
 125
 126         fun backup_in(l: BasicBlock): nullable V is abstract
 127         fun backup_out(l: BasicBlock): nullable V is abstract
 128         fun backup_in=(l: BasicBlock, v: nullable V) is abstract
 129         fun backup_out=(l: BasicBlock, v: nullable V) is abstract
 130
 131         fun line_in(l: ALine): nullable V is abstract
 132         fun line_out(l: ALine): nullable V is abstract
 133         fun line_in=(l: ALine, v: nullable V) is abstract
 134         fun line_out=(l: ALine, v: nullable V) is abstract
 135
 136         redef fun pre_line_visit(line) do line_in(line) = current_in
 137         redef fun post_line_visit(line) do line_out(line) = current_out
 138 end
 139
 140 class StaticAnalysis[S]
 141         super Visitor
 142
 143         var set: S
 144         init (set: S) do self.set = set
 145
 146         redef fun visit( node ) do node.visit_all(self)
 147         fun analyze(ast: AListing): S
 148         do
 149                 enter_visit(ast)
 150                 return set
 151         end
 152 end