Class: Gisele::Analysis::Glts::Merge

Inherits:
Object
  • Object
show all
Defined in:
lib/gisele/analysis/glts/merge.rb

Constant Summary collapse

STATE_AGGREGATOR = 
Stamina::Utils::Aggregator.new{|g|
  g.ignore(:eclosure)
  g.register(:initial, &:|)
  g.register(:accepting, &:&)
  g.register(:error, &:|)
  g.register(:invariant){|v1,v2|
    (v1 | v2).ref
  }
  g.register(:origin){|v1, v2|
    v1, v2 = Array(v1), Array(v2)
    throw :incompatibility unless (v1 & v2).empty?
    v1 | v2
  }
  g.default{|v1,v2|
    raise "Unexpected state marks: #{v1} vs. #{v2}" unless v1==v2
    v1
  }
}
EDGE_AGGREGATOR = 
Stamina::Utils::Aggregator.new{|g|
  g.register(:guard){|v1,v2|
    (v1 | v2).ref
  }
  g.default{|v1,v2|
    raise "Unexpected edge marks: #{v1} vs. #{v2}" unless v1==v2
    v1
  }
}

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Merge

Returns a new instance of Merge.



35
36
37
 
# File 'lib/gisele/analysis/glts/merge.rb', line 35

def initialize
  @threshold = 2
end

Instance Attribute Details

#threshold ⇒ Object (readonly)

Returns the value of attribute threshold.



38
39
40
 
# File 'lib/gisele/analysis/glts/merge.rb', line 38

def threshold
  @threshold
end

Instance Method Details

#build_candidates(glts, candidates = []) ⇒ Object 



58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/gisele/analysis/glts/merge.rb', line 58

def build_candidates(glts, candidates = [])
  size = glts.states.size
  (0...size).each do |i|
    ((i+1)...size).each do |j|
      catch (:incompatibility) do
        candidate = glts.dup
        pair = candidate.ith_states(i, j)
        merge!(candidate, *pair)
        candidates << candidate
      end
    end
  end
  candidates
end

#call(glts) ⇒ Object 



40
41
42
43
44
45
 
# File 'lib/gisele/analysis/glts/merge.rb', line 40

def call(glts)
  while c = get_candidate(glts)
    glts = c
  end
  glts
end

#determinize(glts, s) ⇒ Object 



101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
# File 'lib/gisele/analysis/glts/merge.rb', line 101

def determinize(glts, s)
  delta = Hash.new{|h,k| h[k] = [] }
  s.out_edges.each{|e| delta[e[:event]] << e}
  delta.values.each do |(e,f)|
    next if f.nil?

    # take edge targets, through representors
    t1, t2 = e.target, f.target
    t1 = t1[:representor] while t1[:representor]
    t2 = t2[:representor] while t2[:representor]

    # drop edges and reconnect
    edge_data = EDGE_AGGREGATOR.merge(e.data, f.data)
    glts.drop_edges(e, f)
    new_target = (t1==t2 ? t1 : merge!(glts, t1, t2))
    glts.connect(s, new_target, edge_data)
  end
end

#get_candidate(glts) ⇒ Object 



47
48
49
50
51
52
53
54
55
56
 
# File 'lib/gisele/analysis/glts/merge.rb', line 47

def get_candidate(glts)
  best_candidate = glts
  build_candidates(glts).each do |candidate|
    next unless candidate.state_count < best_candidate.state_count
    next unless (glts.state_count - candidate.state_count) >= threshold
    best_candidate = candidate
    return candidate
  end
  best_candidate == glts ? nil : best_candidate
end

#merge!(glts, s, t) ⇒ Object 



73
74
75
76
77
 
# File 'lib/gisele/analysis/glts/merge.rb', line 73

def merge!(glts, s, t)
  merge_states(glts, s, t)
  determinize(glts, s)
  s
end

#merge_states(glts, s, t) ⇒ Object

Merge ‘s` and `t` the brute force way (non-recursive, no edge-merge)



80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/gisele/analysis/glts/merge.rb', line 80

def merge_states(glts, s, t)
  data = STATE_AGGREGATOR.merge(s.data, t.data)

  # reconnect `t`'s edges to s
  t.in_edges.each do |in_edge|
    source = (in_edge.source == t ? s : in_edge.source)
    glts.connect(source, s, in_edge.data)
  end
  t.out_edges.each do |out_edge|
    target = (out_edge.target == t ? s : out_edge.target)
    glts.connect(s, target, out_edge.data)
  end

  # drop `t` and mark `s` as its representor
  glts.drop_state(t)
  t[:representor] = s

  # set new marks on s
  data.each_pair{|k,v| s[k] = v}
end