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