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     eo[:rows].each do |obj|
174       parent_map[prkey_conv[obj]] = obj
175       (children_map[key_conv[obj]] ||= []) << obj
176       obj.associations[ancestors] = []
177       obj.associations[parent] = nil
178     end
179     r = model.association_reflection(ancestors)
180     base_case = model.where(prkey=>id_map.keys).
181      select(*ancestor_base_case_columns)
182     recursive_case = model.join(t, key_array.zip(prkey_array)).
183      select(*recursive_case_columns)
184     if c = r[:conditions]
185       (base_case, recursive_case) = [base_case, recursive_case].map do |ds|
186         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
187       end
188     end
189     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
190     ds = model.from(SQL::AliasedExpression.new(t, table_alias)).
191       with_recursive(t, base_case, recursive_case,
192        :args=>((key_aliases + col_aliases) if col_aliases))
193     ds = r.apply_eager_dataset_changes(ds)
194     ds = ds.select_append(ka) unless ds.opts[:select] == nil
195     model.eager_load_results(r, eo.merge(:loader=>false, :initalize_rows=>false, :dataset=>ds, :id_map=>nil)) do |obj|
196       opk = prkey_conv[obj]
197       if parent_map.has_key?(opk)
198         if idm_obj = parent_map[opk]
199           key_aliases.each{|ka_| idm_obj.values[ka_] = obj.values[ka_]}
200           obj = idm_obj
201         end
202       else
203         obj.associations[parent] = nil
204         parent_map[opk] = obj
205         (children_map[key_conv[obj]] ||= []) << obj
206       end
207       
208       if roots = id_map[extract_key_alias[obj]]
209         roots.each do |root|
210           root.associations[ancestors] << obj
211         end
212       end
213     end
214     parent_map.each do |parent_id, obj|
215       if children = children_map[parent_id]
216         children.each do |child|
217           child.associations[parent] = obj
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     eo[:rows].each do |obj|
276       parent_map[prkey_conv[obj]] = obj
277       obj.associations[descendants] = []
278       obj.associations[childrena] = []
279     end
280     r = model.association_reflection(descendants)
281     base_case = model.where(key=>id_map.keys).
282      select(*descendant_base_case_columns)
283     recursive_case = model.join(t, prkey_array.zip(key_array)).
284      select(*recursive_case_columns)
285     if c = r[:conditions]
286       (base_case, recursive_case) = [base_case, recursive_case].map do |ds|
287         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
288       end
289     end
290     if associations.is_a?(Integer)
291       level = associations
292       no_cache_level = level - 1
293       associations = {}
294       base_case = base_case.select_append(SQL::AliasedExpression.new(Sequel.cast(0, Integer), la))
295       recursive_case = recursive_case.select_append(SQL::AliasedExpression.new(SQL::QualifiedIdentifier.new(t, la) + 1, la)).where(SQL::QualifiedIdentifier.new(t, la) < level - 1)
296     end
297     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
298     ds = model.from(SQL::AliasedExpression.new(t, table_alias)).
299       with_recursive(t, base_case, recursive_case,
300         :args=>((key_aliases + col_aliases + (level ? [la] : [])) if col_aliases))
301     ds = r.apply_eager_dataset_changes(ds)
302     ds = ds.select_append(ka) unless ds.opts[:select] == nil
303     model.eager_load_results(r, eo.merge(:loader=>false, :initalize_rows=>false, :dataset=>ds, :id_map=>nil, :associations=>OPTS)) do |obj|
304       if level
305         no_cache = no_cache_level == obj.values.delete(la)
306       end
307       
308       opk = prkey_conv[obj]
309       if parent_map.has_key?(opk)
310         if idm_obj = parent_map[opk]
311           key_aliases.each{|ka_| idm_obj.values[ka_] = obj.values[ka_]}
312           obj = idm_obj
313         end
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     children_map.each do |parent_id, objs|
326       objs = objs.uniq
327       parent_obj = parent_map[parent_id]
328       parent_obj.associations[childrena] = objs
329       objs.each do |obj|
330         obj.associations[parent] = parent_obj
331       end
332     end
333   end
334   model.one_to_many descendants, d
335 end