contrib/pep8analysis/src/flow_analysis/framework.nit

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