Class: Modelist::PathFinder

Inherits:
Object
  • Object
show all
Defined in:
lib/modelist/path_finder.rb

Constant Summary collapse

DEFAULT_MAX_PATHS = 
35

Class Method Summary collapse

Class Method Details

.back(current_node_list, counts, processed_result_partials, from) ⇒ Object 



137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
 
# File 'lib/modelist/path_finder.rb', line 137

def self.back(current_node_list, counts, processed_result_partials, from)
  current_node_list.pop
  
  # if there is a count in the array less than two, keep removing them until they are gone
  while counts.last && counts.last < 2
    counts.pop
    c = current_node_list.pop

    # if this is direct/indirect circular reference, don't mark unprocessed origin as processed, because it isn't
    unless counts.size > 1 && c.start_with?("#{from}.")
      # completely processed this path, so don't process it again, and don't overwrite existing success if cached
      #puts "marking #{c} as done"
      processed_result_partials[c] = [] unless processed_result_partials[c]
    end
  end
  
  # either there are no counts, or we just need to decrement the last count
  if counts.last && counts.last > 1
    counts[counts.length-1] = counts[counts.length-1] - 1
  end
end

.cache_found_path_partials(found_path_arr, cache) ⇒ Object 



159
160
161
162
163
 
# File 'lib/modelist/path_finder.rb', line 159

def self.cache_found_path_partials(found_path_arr, cache)
  (found_path_arr.length-2).downto(0) do |i|
    cache[found_path_arr[i]] = found_path_arr[i+1..found_path_arr.length-1] if found_path_arr.length > 1
  end
end

.clean_underscore(classname) ⇒ Object 



5
6
7
8
 
# File 'lib/modelist/path_finder.rb', line 5

def self.clean_underscore(classname)
  classname = classname[2..classname.length] if classname.start_with?('::')
  classname.underscore
end

.find_all(*args) ⇒ Object

Raises:



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/modelist/path_finder.rb', line 10

def self.find_all(*args)
  raise ArgumentError.new("Please supply a search term") unless args.size != 0
  # less-dependent extract_options!
  options = args.last.is_a?(Hash) ? args.pop : {}
  
  from = args[0]
  to = args[1]

  puts "Checking for path from #{from} to #{to}..."
  relations = relationship_map_excluding(to)

  results = get_all_paths_via_iterative_depth_first_search(from, to, relations)
  puts
  puts

  matching_results = results.sort_by(&:length).reverse.collect{|arr|format_result_string(arr)}
  #TODO: make it actually not even search past N nodes
  if matching_results.length > 0
    puts "Paths from #{from} to #{to} (#{matching_results.length}):"
    # show the shortest path as the last item logged, for ease of use in CLI
    matching_results.each do |r|
      puts
      puts r
    end      
  else
    puts "No path found from #{from} to #{to}."
  end
  results
end

.format_result_string(*args) ⇒ Object 



165
166
167
 
# File 'lib/modelist/path_finder.rb', line 165

def self.format_result_string(*args)
  args.flatten.join(' -> ')
end

.forward(current_node_list, this_class_assoc, counts, children_count) ⇒ Object 



132
133
134
135
 
# File 'lib/modelist/path_finder.rb', line 132

def self.forward(current_node_list, this_class_assoc, counts, children_count)
  current_node_list.push(this_class_assoc)
  counts.push(children_count)
end

.get_all_paths_via_iterative_depth_first_search(from, to, directed_graph) ⇒ Object

e.g. from = ‘model_name_1’ to = ‘model_name_2’ directed_graph = => ‘model_name_2’, ‘model_name_1.assoc_name’ => ‘model_name_3’, ‘model_name_2.assoc_name’ => ‘model_name_3’, … returns: [[‘model_name_1.assoc_name’, ‘model_name_3.assoc_name’, ‘model_name_2’], …]



71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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
 
# File 'lib/modelist/path_finder.rb', line 71

def self.get_all_paths_via_iterative_depth_first_search(from, to, directed_graph)
  queue = directed_graph.keys.select {|k| k.split('.')[0] == from && directed_graph[k] != from}
  #puts "starting with #{queue.join(', ')}"
  queue.each {|k| print '+'; $stdout.flush}
  results = []
  processed_result_partials = {} # model.assoc to array of results
  current_node_list = []
  class_assocs_visited = []
  counts = [queue.length]

  while queue.length > 0
    #puts "queue(#{queue.length})=#{queue.inspect}"
    #visualize_queue(queue)
    this_class_assoc = queue.pop
    class_assocs_visited << this_class_assoc unless class_assocs_visited.include?(this_class_assoc)
    raise "FAILING! #{current_node_list[0].split('.')[0]} != #{from}" if current_node_list[0] && current_node_list[0].split('.')[0] != from
    print '-'; $stdout.flush
    next_class = directed_graph[this_class_assoc]
    #puts "processing #{this_class_assoc} => #{next_class}"
    current_node_list.push(this_class_assoc)
    #puts "current_node_list(#{current_node_list.length})=#{current_node_list.inspect}"
    #puts "counts: #{counts.join(',')}"
    
    step_back = true
    preprocessed_results = processed_result_partials[this_class_assoc]
    if preprocessed_results
      #puts "already processed #{this_class_assoc}"
      print '-'; $stdout.flush
      if preprocessed_results.length > 0
        results << (current_node_list + preprocessed_results)
        #raise "bug in preprocessed! should start with #{from} but have result #{format_result_string(results.last)}" if current_node_list[0].split('.')[0] != from
      end
    elsif next_class == to
      #puts "reached #{to} in #{current_node_list.length} steps"
      found_path = current_node_list + [next_class]
      results << found_path
      raise "oops! should start with #{from} but have result #{format_result_string(results.last)}" if current_node_list[0].split('.')[0] != from
      cache_found_path_partials(found_path, processed_result_partials)
    elsif !current_node_list.any?{|n| n.start_with?("#{next_class}.")}
      children_to_visit = directed_graph.select {|k,v| k.start_with?("#{next_class}.") && directed_graph[k] != from}.keys
      #puts "following (#{children_to_visit.length}): #{children_to_visit.join(', ')}"
      children_to_visit.each {|c|print '+'; $stdout.flush}
      if children_to_visit.length > 0
        step_back = false
        counts.push(children_to_visit.length)
        queue += children_to_visit
      end
    end

    back(current_node_list, counts, processed_result_partials, from) if step_back
  end

  #puts
  #puts
  #unvisited = directed_graph.keys - class_assocs_visited
  #puts "unvisited associations (#{unvisited.length}): #{unvisited.sort.join(', ')}"
  #puts

  results
end

.get_classname(association) ⇒ Object 



169
170
171
172
173
174
175
176
 
# File 'lib/modelist/path_finder.rb', line 169

def self.get_classname(association)
  association.options[:class_name] || case association.macro
  when :belongs_to, :has_one
    association.name.to_s
  when :has_and_belongs_to_many, :has_many
    association.name.to_s.singularize
  end
end

.relationship_map_excluding(exclude_name) ⇒ Object 



40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'lib/modelist/path_finder.rb', line 40

def self.relationship_map_excluding(exclude_name)
  Rails.application.eager_load!
  relations = {}
  
  m_to_a = {}
  ActiveRecord::Base.descendants.each do |m|
    m_to_a[m] = m.reflect_on_all_associations
  end

  m_to_a.each do |m,as|
    # don't try to link via composite primary keys until that is possible, which it isn't now afaik.
    next if m.primary_key.is_a?(Array)
    as.each do |association|
      c1_name = clean_underscore(m.name)
      next if c1_name == exclude_name
      #TODO: we could exclude c1/key that is "to"
      c1 = "#{c1_name}.#{association.name}"
      c2 = get_classname(association)
      if c2
        relations[c1] = clean_underscore(c2)
      end
    end unless as == nil
  end
  relations
end