bloom-lang/bud — Issue #261: Notin not working properly
Author: andyisimprovised
Created: 2012-02-22 20:14:15+00:00
State: open

Peter and I ran into a case where "notin" is not outputing the correct results. Here is the example program, as tiny as I though I could make it. In summary, it uses the bud meta-table t_depends to compute the strongly connected components of the predicate dependency graph.

We use "notin" when we calculate the edges in the dependency graph that have neither of their vertexes contained in a strongly connected component:

```ruby
no_scc_intmd <= t_depends.notin(scc, :lhs => :predicate)
no_scc <= no_scc_intmd.notin(scc, :body => :predicate)
```

However, this is not returning the proper results. The equivalent way of performing this computation contains the right results:

```ruby
temp :matches <= (no_scc_intmd * scc).lefts(:body => :predicate)
temp :correct_no_scc <= no_scc_intmd do |x|
x unless matches.include? x
end
```

I've copied and pasted the test program below:

```ruby
require 'rubygems'
require 'bud'
require 'set'

module Paths

state do
# table :t_depends, [:rule_id, :lhs, :op, :body] => [:nm]

# SCC stuff
scratch :dep_tc, [:from, :to, :path]
scratch :cycle, [:predicate, :path]
scratch :scc, [:predicate] => [:path]
scratch :all_scc, [:path]

# new dependency relationship stuff
scratch :no_scc_intmd, t_depends.schema
scratch :no_scc, t_depends.schema
table :labels, [:rule_id, :lhs, :body, :label, :scc]
end

bloom :redun do
# finds all "paths" in bud collection dependency graph
dep_tc <= t_depends {|d| [d.body, d.lhs, [d.lhs]]}
dep_tc <= (dep_tc * t_depends).pairs(:to => :body) do |t, d|
[t.from, d.lhs, Set.new([d.lhs]) | t.path]
end

# finds all cycles in the set of paths
cycle <= dep_tc{|d| [d.from, d.path] if d.from == d.to}

# finds all strongly connected components from known cycles
scc <= cycle.reduce({}) do |memo, i|
memo[i.predicate] ||= Set.new
memo[i.predicate] = memo[i.predicate] | i.path
memo
end
all_scc <= scc{|s| [s.path]}

stdio <~ all_scc.inspected
end

bloom :make_dag do
# HERE IS THE BUG
# finds all edges that don't participate in a SCC
no_scc_intmd <= t_depends.notin(scc, :lhs => :predicate)
no_scc <= no_scc_intmd.notin(scc, :body => :predicate)

# Here is the correct output
temp :matches <= (no_scc_intmd * scc).lefts(:body => :predicate)
temp :correct_no_scc <= no_scc_intmd do |x|
x unless matches.include? x
end
stdio <~ correct_no_scc.inspected
stdio <~ no_scc.inspected
end

end

class TestPaths
include Paths
include Bud
end

a = TestPaths.new
a.tick
```