Class: RuleRewriter

Inherits:
Ruby2Ruby
  • Object
show all
Defined in:
lib/bud/rewrite.rb

Overview

:nodoc: all

Constant Summary collapse

OP_LIST = 
[:<<, :<, :<=].to_set
TEMP_OP_LIST = 
[:-@, :~, :+@].to_set
MONOTONE_WHITELIST = 
[:==, :+, :<=, :-, :<, :>, :*, :~, :+@,
:pairs, :matches, :combos, :flatten, :new,
:lefts, :rights, :map, :flat_map, :pro, :merge,
:schema, :cols, :key_cols, :val_cols, :payloads, :lambda,
:tabname, :current_value].to_set

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(bud_instance, rule_idx) ⇒ RuleRewriter

Returns a new instance of RuleRewriter.



14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/bud/rewrite.rb', line 14

def initialize(bud_instance, rule_idx)
  @bud_instance = bud_instance
  @tables = {}
  @nm = false
  @rule_idx = rule_idx
  @collect = false
  @rules = []
  @depends = []
  @iter_stack = []
  @refs_in_body = Set.new
  super()
end

Instance Attribute Details

#depends ⇒ Object

Returns the value of attribute depends.



4
5
6
 
# File 'lib/bud/rewrite.rb', line 4

def depends
  @depends
end

#rule_idx ⇒ Object

Returns the value of attribute rule_idx.



4
5
6
 
# File 'lib/bud/rewrite.rb', line 4

def rule_idx
  @rule_idx
end

#rules ⇒ Object

Returns the value of attribute rules.



4
5
6
 
# File 'lib/bud/rewrite.rb', line 4

def rules
  @rules
end

Class Method Details

.is_monotone(op) ⇒ Object 



193
194
195
196
197
 
# File 'lib/bud/rewrite.rb', line 193

def self.is_monotone(op)
  MONOTONE_WHITELIST.include?(op) ||
    is_morphism(op) ||
    Bud::Lattice.global_mfuncs.include?(op)
end

.is_morphism(op) ⇒ Object 



199
200
201
 
# File 'lib/bud/rewrite.rb', line 199

def self.is_morphism(op)
  Bud::Lattice.global_morphs.include?(op)
end

Instance Method Details

#call_to_id(exp) ⇒ Object

Raises:



57
58
59
60
61
62
63
64
65
66
 
# File 'lib/bud/rewrite.rb', line 57

def call_to_id(exp)
  # convert a series of nested calls, a sexp of the form
  #   s(:call,
  #       s(:call, s(:call, nil, :a), :b),
  #         :bar))
  # to the string "a.b.bar"
  raise Bud::CompileError, "malformed expression: #{exp}" unless exp.sexp_type == :call
  _, recv, op = exp
  return recv.nil? ? op.to_s : call_to_id(recv) + "." + op.to_s
end

#collect_rhs(exp) ⇒ Object 



225
226
227
228
229
230
231
232
 
# File 'lib/bud/rewrite.rb', line 225

def collect_rhs(exp)
  exp = lambda_rewrite(exp)

  @collect = true
  rhs = process exp
  @collect = false
  return rhs
end

#do_process_iter(iter, args, body) ⇒ Object 



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 
# File 'lib/bud/rewrite.rb', line 90

def do_process_iter(iter, args, body)
  args = case args
         when 0 then
           " ||"
         else
           a = process(args)[1..-2]
           a = " |#{a}|" unless a.empty?
           a
         end

  b, e = if iter == "END" then
           [ "{", "}" ]
         else
           [ "do", "end" ]
         end

  iter.sub!(/\(\)$/, '')

  # REFACTOR: ugh
  result = []
  result << "#{iter} {"
  result << args
  if body then
    result << " #{body.strip} "
  else
    result << ' '
  end
  result << "}"
  result = result.join
  return result if result !~ /\n/ and result.size < LINE_LENGTH

  result = []
  result << "#{iter} #{b}"
  result << args
  result << "\n"
  if body then
    result << indent(body.strip)
    result << "\n"
  end
  result << e
  result.join
end

#do_rule(exp) ⇒ Object 



261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
 
# File 'lib/bud/rewrite.rb', line 261

def do_rule(exp)
  tag, lhs, op, rhs_ast = exp
  lhs = process(lhs)

  rhs_ast = MapRewriter.new.process(rhs_ast)
  rhs_ast = RenameRewriter.new(@bud_instance).process(rhs_ast)
  rhs_ast = LatticeRefRewriter.new(@bud_instance).process(rhs_ast)
  ufr = UnsafeFuncRewriter.new(@bud_instance)
  rhs_ast = ufr.process(rhs_ast)

  if @bud_instance.options[:no_attr_rewrite]
    rhs = collect_rhs(rhs_ast)
    rhs_pos = rhs
  else
    # need a deep copy of the rules so we can keep a version without AttrName
    # Rewrite
    rhs_ast_dup = Marshal.load(Marshal.dump(rhs_ast))
    rhs = collect_rhs(rhs_ast)
    reset_instance_vars
    rhs_pos = collect_rhs(AttrNameRewriter.new(@bud_instance).process(rhs_ast_dup))
  end
  record_rule(lhs, op, rhs_pos, rhs, ufr.unsafe_func_called)
  drain(exp)
end

#drain(exp) ⇒ Object 



286
287
288
289
 
# File 'lib/bud/rewrite.rb', line 286

def drain(exp)
  exp.shift until exp.empty?
  return ""
end

#exp_id_type(recv, name, args) ⇒ Object

call only if sexp type is :call



40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/bud/rewrite.rb', line 40

def exp_id_type(recv, name, args) # call only if sexp type is :call
  return $not_id unless args.empty?
  ty = $not_id
  if recv
    if recv.first == :call
      # possibly nested reference
      # rty, rqn, .. = receiver's type, qual name etc.
      rty, rqn, robj = exp_id_type(recv[1], recv[2], recv[3..-1])
      ty = resolve(robj, rqn, name) if rty == :import
    end
  else
    # plain, un-prefixed name. See if it refers to a collection or import spec
    ty = resolve(@bud_instance, nil, name)
  end
  ty
end

#is_rhs_literal(e) ⇒ Object 



221
222
223
 
# File 'lib/bud/rewrite.rb', line 221

def is_rhs_literal(e)
  [:array, :hash, :lit].include? e
end

#lambda_rewrite(rhs) ⇒ Object

Rewrite top-level rhs literal expressions into lambdas. During wiring, these are turned into coll_expr collections. For normal relational Bloom, the only literal we expect to see is an array literal, but lattices can be initialized with other kinds of literals (e.g., integers for lmax).



207
208
209
210
211
212
213
214
215
216
217
218
219
 
# File 'lib/bud/rewrite.rb', line 207

def lambda_rewrite(rhs)
  # the <= case
  if is_rhs_literal(rhs[0])
    return s(:iter, s(:call, nil, :lambda), s(:args), rhs)
  # the superator case
  elsif rhs[0] == :call \
    and rhs[1] and rhs[1][0] and is_rhs_literal(rhs[1][0]) \
    and rhs[2] and (rhs[2] == :+@ or rhs[2] == :-@ or rhs[2] == :~@)
    return s(rhs[0], s(:iter, s(:call, nil, :lambda), s(:args), rhs[1]), rhs[2], *rhs[3..-1])
  else
    return rhs
  end
end

#process_call(exp) ⇒ Object 



133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
 
# File 'lib/bud/rewrite.rb', line 133

def process_call(exp)
  tag, recv, op, *args = exp
  if OP_LIST.include?(op) and @context[1] == :defn and @context.length == 2
    # NB: context.length is 2 when see a method call at the top-level of a
    # :defn block -- this is where we expect Bloom statements to appear
    do_rule(exp)
  elsif op == :notin
    # Special case. In the rule "z <= x.notin(y)", z depends positively on x,
    # but negatively on y. See further explanation in the "else" section for
    # why this is a special case.
    if args.first.sexp_type != :call
      raise Bud::CompileError, "illegal argument to notin: #{args.first}"
    end
    notintab = call_to_id(args[0])   # args expected to be of the form (:call nil :y ...)
    @tables[notintab] = true    # "true" denotes non-monotonic dependency
    super
  else
    # Parse a call of the form a.b.c.foo
    #
    # In the most general case, a.b is a nested module, a.b.c is a collection
    # in that module, and a.b.c.foo is either a method or a field. If it is a
    # method, and non-monotonic at that, we register a dependency between lhs
    # and the table a.b.c.  Note that notin is treated differently because in
    # a.b.c.notin(d.e.f), we register a non-monotonic dependency of lhs on
    # "d.e.f", not with "a.b.c"
    ty, qn, _ = exp_id_type(recv, op, args) # qn = qualified name
    if ty == :collection or ty == :lattice
      (@tables[qn] = @nm if @collect) unless @tables[qn]
      @refs_in_body << qn unless @iter_stack.empty?
    #elsif ty == :import .. do nothing
    elsif ty == :not_coll_id
      # Check if receiver is a collection, and further if the current exp
      # represents a field lookup
      op_is_field_name = false
      if recv and recv.first == :call
        rty, _, robj = exp_id_type(recv[1], recv[2], recv[3..-1])
        if rty == :collection
          cols = robj.cols
          op_is_field_name = true if cols and cols.include?(op)
        end
      end
      # For CALM analysis, mark deletion rules as non-monotonic
      @nm = true if op == :-@

      # Don't worry about monotone ops, table names, table.attr calls, or
      # accessors of iterator variables
      if recv
        unless RuleRewriter.is_monotone(op) or op_is_field_name or
               recv.first == :lvar or op.to_s.start_with?("__")
          @nm = true
        end
      end
    end
    if TEMP_OP_LIST.include? op
      @temp_op = op.to_s.gsub("@", "")
    end
    super
  end
end

#process_iter(exp) ⇒ Object

We want to distinguish between collection dependencies that occur in top-level expressions versus collections that are referenced inside rule bodies. We just want to set a flag when processing the :iter body, but annoyingly it seems that is hard to do without duplicating the implementation of process_iter().

XXX: the whole RuleRewriter approach is wrong because it conflates converting ASTs to strings with doing analysis on ASTs. Those should be split into two separate passes.



77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/bud/rewrite.rb', line 77

def process_iter(exp)
  # first field of exp is tag; shift it
  exp.shift
  iter = process exp.shift
  args = exp.shift

  @iter_stack.push(true)
  body = exp.empty? ? nil : process(exp.shift)
  @iter_stack.pop

  do_process_iter(iter, args, body)
end

#record_rule(lhs, op, rhs_pos, rhs, unsafe_funcs_called) ⇒ Object 



241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
 
# File 'lib/bud/rewrite.rb', line 241

def record_rule(lhs, op, rhs_pos, rhs, unsafe_funcs_called)
  rule_txt_orig = "#{lhs} #{op} (#{rhs})"
  rule_txt = "#{lhs} #{op} (#{rhs_pos})"
  if op == :<
    op = "<#{@temp_op}"
  else
    op = op.to_s
  end

  @rules << [@bud_instance, @rule_idx, lhs, op, rule_txt,
             rule_txt_orig, unsafe_funcs_called]
  @tables.each_pair do |t, nm|
    in_rule_body = @refs_in_body.include? t
    @depends << [@bud_instance, @rule_idx, lhs, op, t, nm, in_rule_body]
  end

  reset_instance_vars
  @rule_idx += 1
end

#reset_instance_vars ⇒ Object 



234
235
236
237
238
239
 
# File 'lib/bud/rewrite.rb', line 234

def reset_instance_vars
  @refs_in_body = Set.new
  @tables = {}
  @nm = false
  @temp_op = nil
end

#resolve(obj, prefix, name) ⇒ Object 



28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/bud/rewrite.rb', line 28

def resolve(obj, prefix, name)
  qn = prefix ? prefix + "." + name.to_s : name.to_s
  return [:collection, qn, obj.tables[name]] if obj.tables.has_key? name
  return [:lattice, qn, obj.lattices[name]] if obj.lattices.has_key? name

  # does name refer to an import name?
  iobj = obj.import_instance name
  return [:import, qn, iobj] if iobj and iobj.respond_to? :tables

  return $not_id
end