module Sequel::Plugins::RcteTree

  1. lib/sequel/plugins/rcte_tree.rb

Overview ↑

The rcte_tree plugin deals with tree structured data stored in the database using the adjacency list model (where child rows have a foreign key pointing to the parent rows), using recursive common table expressions to load all ancestors in a single query, all descendants in a single query, and all descendants to a given level (where level 1 is children, level 2 is children and grandchildren etc.) in a single query.

Usage ↑

The rcte_tree plugin adds four associations to the model: parent, children, ancestors, and descendants. Both the parent and children are fairly standard many_to_one and one_to_many associations, respectively. However, the ancestors and descendants associations are special. Both the ancestors and descendants associations will automatically set the parent and children associations, respectively, for current object and all of the ancestor or descendant objects, whenever they are loaded (either eagerly or lazily). Additionally, the descendants association can take a level argument when called eagerly, which limits the returned objects to only that many levels in the tree (see the Overview).

Model.plugin :rcte_tree

# Lazy loading
model = Model.first
model.parent
model.children
model.ancestors # Populates :parent association for all ancestors
model.descendants # Populates :children association for all descendants

# Eager loading - also populates the :parent and children associations
# for all ancestors and descendants
Model.where(id: [1, 2]).eager(:ancestors, :descendants).all

# Eager loading children and grandchildren
Model.where(id: [1, 2]).eager(descendants: 2).all
# Eager loading children, grandchildren, and great grandchildren
Model.where(id: [1, 2]).eager(descendants: 3).all

Options ↑

You can override the options for any specific association by making sure the plugin options contain one of the following keys:

:parent

hash of options for the parent association

:children

hash of options for the children association

:ancestors

hash of options for the ancestors association

:descendants

hash of options for the descendants association

Note that you can change the name of the above associations by specifying a :name key in the appropriate hash of options above. For example:

Model.plugin :rcte_tree, parent: {name: :mother},
 children: {name: :daughters}, descendants: {name: :offspring}

Any other keys in the main options hash are treated as options shared by all of the associations. Here’s a few options that affect the plugin:

:key

The foreign key in the table that points to the primary key of the parent (default: :parent_id)

:primary_key

The primary key to use (default: the model’s primary key)

:key_alias

The symbol identifier to use for aliasing when eager loading (default: :x_root_x)

:cte_name

The symbol identifier to use for the common table expression (default: :t)

:level_alias

The symbol identifier to use when eagerly loading descendants up to a given level (default: :x_level_x)

Methods

Public Class

  1. apply

Public Class methods

apply(model, opts=OPTS)

Create the appropriate parent, children, ancestors, and descendants associations for the model.

[show source] 
    # File lib/sequel/plugins/rcte_tree.rb
 77 def self.apply(model, opts=OPTS)
 78   model.plugin :tree, opts
 79 
 80   opts = opts.dup
 81   opts[:class] = model
 82   opts[:methods_module] = Module.new
 83   model.send(:include, opts[:methods_module])
 84   
 85   key = opts[:key] ||= :parent_id
 86   prkey = opts[:primary_key] ||= model.primary_key
 87   ka = opts[:key_alias] ||= :x_root_x
 88   t = opts[:cte_name] ||= :t
 89   c_all = if model.dataset.recursive_cte_requires_column_aliases?
 90     # Work around Oracle/ruby-oci8 bug that returns integers as BigDecimals in recursive queries.
 91     conv_bd = model.db.database_type == :oracle
 92     col_aliases = model.dataset.columns
 93     model_table = model.table_name
 94     col_aliases.map{|c| SQL::QualifiedIdentifier.new(model_table, c)}
 95   else
 96     [SQL::ColumnAll.new(model.table_name)]
 97   end
 98   
 99   bd_conv = lambda{|v| conv_bd && v.is_a?(BigDecimal) ? v.to_i : v}
100 
101   key_array = Array(key)
102   prkey_array = Array(prkey)
103   if key.is_a?(Array)
104     key_conv = lambda{|m| key_array.map{|k| m[k]}}
105     key_present = lambda{|m| key_conv[m].all?}
106     prkey_conv = lambda{|m| prkey_array.map{|k| m[k]}}
107     key_aliases = (0...key_array.length).map{|i| :"#{ka}_#{i}"}
108     ancestor_base_case_columns = prkey_array.zip(key_aliases).map{|k, ka_| SQL::AliasedExpression.new(k, ka_)} + c_all
109     descendant_base_case_columns = key_array.zip(key_aliases).map{|k, ka_| SQL::AliasedExpression.new(k, ka_)} + c_all
110     recursive_case_columns = prkey_array.zip(key_aliases).map{|k, ka_| SQL::QualifiedIdentifier.new(t, ka_)} + c_all
111     extract_key_alias = lambda{|m| key_aliases.map{|ka_| bd_conv[m.values.delete(ka_)]}}
112   else
113     key_present = key_conv = lambda{|m| m[key]}
114     prkey_conv = lambda{|m| m[prkey]}
115     key_aliases = [ka]
116     ancestor_base_case_columns = [SQL::AliasedExpression.new(prkey, ka)] + c_all
117     descendant_base_case_columns = [SQL::AliasedExpression.new(key, ka)] + c_all
118     recursive_case_columns = [SQL::QualifiedIdentifier.new(t, ka)] + c_all
119     extract_key_alias = lambda{|m| bd_conv[m.values.delete(ka)]}
120   end
121   
122   parent = opts.merge(opts.fetch(:parent, OPTS)).fetch(:name, :parent)
123   childrena = opts.merge(opts.fetch(:children, OPTS)).fetch(:name, :children)
124   
125   opts[:reciprocal] = nil
126   a = opts.merge(opts.fetch(:ancestors, OPTS))
127   ancestors = a.fetch(:name, :ancestors)
128   a[:read_only] = true unless a.has_key?(:read_only)
129   a[:eager_grapher] = proc do |_|
130     raise Sequel::Error, "the #{ancestors} association for #{self} does not support eager graphing"
131   end
132   a[:eager_loader_key] = key
133   a[:dataset] ||= proc do
134     base_ds = model.where(prkey_array.zip(key_array.map{|k| get_column_value(k)}))
135     recursive_ds = model.join(t, key_array.zip(prkey_array))
136     if c = a[:conditions]
137       (base_ds, recursive_ds) = [base_ds, recursive_ds].map do |ds|
138         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
139       end
140     end
141     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
142     model.from(SQL::AliasedExpression.new(t, table_alias)).
143      with_recursive(t, col_aliases ? base_ds.select(*col_aliases) : base_ds.select_all,
144       recursive_ds.select(*c_all),
145       :args=>col_aliases)
146   end
147   aal = Array(a[:after_load])
148   aal << proc do |m, ancs|
149     unless m.associations.has_key?(parent)
150       parent_map = {prkey_conv[m]=>m}
151       child_map = {}
152       child_map[key_conv[m]] = m if key_present[m]
153       m.associations[parent] = nil
154       ancs.each do |obj|
155         obj.associations[parent] = nil
156         parent_map[prkey_conv[obj]] = obj
157         if ok = key_conv[obj]
158           child_map[ok] = obj
159         end
160       end
161       parent_map.each do |parent_id, obj|
162         if child = child_map[parent_id]
163           child.associations[parent] = obj
164         end
165       end
166     end
167   end
168   a[:after_load] ||= aal
169   a[:eager_loader] ||= proc do |eo|
170     id_map = eo[:id_map]
171     parent_map = {}
172     children_map = {}
173     Sequel.synchronize_with(eo[:mutex]) do
174       eo[:rows].each do |obj|
175         parent_map[prkey_conv[obj]] = obj
176         (children_map[key_conv[obj]] ||= []) << obj
177         obj.associations[ancestors] = []
178         obj.associations[parent] = nil
179       end
180     end
181     r = model.association_reflection(ancestors)
182     base_case = model.where(prkey=>id_map.keys).
183      select(*ancestor_base_case_columns)
184     recursive_case = model.join(t, key_array.zip(prkey_array)).
185      select(*recursive_case_columns)
186     if c = r[:conditions]
187       (base_case, recursive_case) = [base_case, recursive_case].map do |ds|
188         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
189       end
190     end
191     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
192     ds = model.from(SQL::AliasedExpression.new(t, table_alias)).
193       with_recursive(t, base_case, recursive_case,
194        :args=>((key_aliases + col_aliases) if col_aliases))
195     ds = r.apply_eager_dataset_changes(ds)
196     ds = ds.select_append(ka) unless ds.opts[:select] == nil
197     model.eager_load_results(r, eo.merge(:loader=>false, :initialize_rows=>false, :dataset=>ds, :id_map=>nil)) do |obj|
198       opk = prkey_conv[obj]
199       if idm_obj = parent_map[opk]
200         key_aliases.each{|ka_| idm_obj.values[ka_] = obj.values[ka_]}
201         obj = idm_obj
202       else
203         obj.associations[parent] = nil
204         parent_map[opk] = obj
205         (children_map[key_conv[obj]] ||= []) << obj
206       end
207       
208       id_map[extract_key_alias[obj]].each do |root|
209         root.associations[ancestors] << obj
210       end
211     end
212     Sequel.synchronize_with(eo[:mutex]) do
213       parent_map.each do |parent_id, obj|
214         if children = children_map[parent_id]
215           children.each do |child|
216             child.associations[parent] = obj
217           end
218         end
219       end
220     end
221   end
222   model.one_to_many ancestors, a
223   
224   d = opts.merge(opts.fetch(:descendants, OPTS))
225   descendants = d.fetch(:name, :descendants)
226   d[:read_only] = true unless d.has_key?(:read_only)
227   d[:eager_grapher] = proc do |_|
228     raise Sequel::Error, "the #{descendants} association for #{self} does not support eager graphing"
229   end
230   la = d[:level_alias] ||= :x_level_x
231   d[:dataset] ||= proc do
232     base_ds = model.where(key_array.zip(prkey_array.map{|k| get_column_value(k)}))
233     recursive_ds = model.join(t, prkey_array.zip(key_array))
234     if c = d[:conditions]
235       (base_ds, recursive_ds) = [base_ds, recursive_ds].map do |ds|
236         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
237       end
238     end
239     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
240     model.from(SQL::AliasedExpression.new(t, table_alias)).
241      with_recursive(t, col_aliases ? base_ds.select(*col_aliases) : base_ds.select_all,
242       recursive_ds.select(*c_all),
243       :args=>col_aliases)
244     end
245   dal = Array(d[:after_load])
246   dal << proc do |m, descs|
247     unless m.associations.has_key?(childrena)
248       parent_map = {prkey_conv[m]=>m}
249       children_map = {}
250       m.associations[childrena] = []
251       descs.each do |obj|
252         obj.associations[childrena] = []
253         if opk = prkey_conv[obj]
254           parent_map[opk] = obj
255         end
256         if ok = key_conv[obj]
257           (children_map[ok] ||= []) << obj
258         end
259       end
260       children_map.each do |parent_id, objs|
261         parent_obj = parent_map[parent_id]
262         parent_obj.associations[childrena] = objs
263         objs.each do |obj|
264           obj.associations[parent] = parent_obj
265         end
266       end
267     end
268   end
269   d[:after_load] = dal
270   d[:eager_loader] ||= proc do |eo|
271     id_map = eo[:id_map]
272     associations = eo[:associations]
273     parent_map = {}
274     children_map = {}
275     Sequel.synchronize_with(eo[:mutex]) do
276       eo[:rows].each do |obj|
277         parent_map[prkey_conv[obj]] = obj
278         obj.associations[descendants] = []
279         obj.associations[childrena] = []
280       end
281     end
282     r = model.association_reflection(descendants)
283     base_case = model.where(key=>id_map.keys).
284      select(*descendant_base_case_columns)
285     recursive_case = model.join(t, prkey_array.zip(key_array)).
286      select(*recursive_case_columns)
287     if c = r[:conditions]
288       (base_case, recursive_case) = [base_case, recursive_case].map do |ds|
289         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
290       end
291     end
292     if associations.is_a?(Integer)
293       level = associations
294       no_cache_level = level - 1
295       associations = {}
296       base_case = base_case.select_append(SQL::AliasedExpression.new(Sequel.cast(0, Integer), la))
297       recursive_case = recursive_case.select_append(SQL::AliasedExpression.new(SQL::QualifiedIdentifier.new(t, la) + 1, la)).where(SQL::QualifiedIdentifier.new(t, la) < level - 1)
298     end
299     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
300     ds = model.from(SQL::AliasedExpression.new(t, table_alias)).
301       with_recursive(t, base_case, recursive_case,
302         :args=>((key_aliases + col_aliases + (level ? [la] : [])) if col_aliases))
303     ds = r.apply_eager_dataset_changes(ds)
304     ds = ds.select_append(ka) unless ds.opts[:select] == nil
305     model.eager_load_results(r, eo.merge(:loader=>false, :initialize_rows=>false, :dataset=>ds, :id_map=>nil, :associations=>OPTS)) do |obj|
306       if level
307         no_cache = no_cache_level == obj.values.delete(la)
308       end
309       
310       opk = prkey_conv[obj]
311       if idm_obj = parent_map[opk]
312         key_aliases.each{|ka_| idm_obj.values[ka_] = obj.values[ka_]}
313         obj = idm_obj
314       else
315         obj.associations[childrena] = [] unless no_cache
316         parent_map[opk] = obj
317       end
318       
319       if root = id_map[extract_key_alias[obj]].first
320         root.associations[descendants] << obj
321       end
322       
323       (children_map[key_conv[obj]] ||= []) << obj
324     end
325     Sequel.synchronize_with(eo[:mutex]) do
326       children_map.each do |parent_id, objs|
327         objs = objs.uniq
328         parent_obj = parent_map[parent_id]
329         parent_obj.associations[childrena] = objs
330         objs.each do |obj|
331           obj.associations[parent] = parent_obj
332         end
333       end
334     end
335   end
336   model.one_to_many descendants, d
337 end