Module: CommandSearch::Optimizer

Defined in:
lib/command_search/optimizer.rb

Class Method Summary collapse

Class Method Details

.ands_and_ors(ast) ⇒ Object 



5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
# File 'lib/command_search/optimizer.rb', line 5

def ands_and_ors(ast)
  ast.uniq.map do |node|
    next node unless node[:nest_type]
    next node if node[:nest_type] == :compare
    node[:value] = ands_and_ors(node[:value])
    node[:value] = node[:value].flat_map do |kid|
      next kid[:value] if kid[:nest_type] == :pipe
      kid
    end
    if node[:nest_type] == :pipe && node[:value].length == 1
      next node[:value].first
    end
    node
  end
end

.denest_parens(ast, parent_type = :root) ⇒ Object 



34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/command_search/optimizer.rb', line 34

def denest_parens(ast, parent_type = :root)
  ast.flat_map do |node|
    next node unless node[:nest_type]

    node[:value] = denest_parens(node[:value], node[:nest_type])

    valid_self = node[:nest_type] == :paren
    valid_parent = parent_type != :pipe
    valid_child = node[:value].count < 2

    next node[:value] if valid_self && valid_parent
    next node[:value] if valid_self && valid_child
    node
  end
end

.negate_negate(ast) ⇒ Object 



21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/command_search/optimizer.rb', line 21

def negate_negate(ast)
  ast.flat_map do |node|
    next node unless node[:nest_type]
    node[:value] = negate_negate(node[:value])
    next [] if node[:value] == []
    next node if node[:value].count > 1
    type = node[:nest_type]
    child_type = node[:value].first[:nest_type]
    next node unless type == :minus && child_type == :minus
    node[:value].first[:value]
  end
end

.optimization_pass(ast) ⇒ Object 



60
61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/command_search/optimizer.rb', line 60

def optimization_pass(ast)
  # '(a b)|(c d)' is the  only current
  # situation where parens are needed.
  # 'a|(b|(c|d))' can be flattened by
  # repeated application of "ands_and_or"
  # and "denest_parens".
  out = ast
  out = denest_parens(out)
  out = negate_negate(out)
  out = ands_and_ors(out)
  out = remove_empty_strings(out)
  out
end

.optimize(ast) ⇒ Object 



74
75
76
77
78
79
80
81
82
 
# File 'lib/command_search/optimizer.rb', line 74

def optimize(ast)
  out_a = optimization_pass(ast)
  out_b = optimization_pass(out_a)
  until out_a == out_b
    out_a = out_b
    out_b = optimization_pass(out_b)
  end
  out_b
end

.remove_empty_strings(ast) ⇒ Object 



50
51
52
53
54
55
56
57
58
 
# File 'lib/command_search/optimizer.rb', line 50

def remove_empty_strings(ast)
  out = ast.flat_map do |node|
    next if node[:type] == :quoted_str && node[:value] == ''
    next node unless node[:nest_type]
    node[:value] = remove_empty_strings(node[:value])
    node
  end
  out.compact
end