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_loader_key] = key
130   a[:dataset] ||= proc do
131     base_ds = model.where(prkey_array.zip(key_array.map{|k| get_column_value(k)}))
132     recursive_ds = model.join(t, key_array.zip(prkey_array))
133     if c = a[:conditions]
134       (base_ds, recursive_ds) = [base_ds, recursive_ds].map do |ds|
135         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
136       end
137     end
138     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
139     model.from(SQL::AliasedExpression.new(t, table_alias)).
140      with_recursive(t, col_aliases ? base_ds.select(*col_aliases) : base_ds.select_all,
141       recursive_ds.select(*c_all),
142       :args=>col_aliases)
143   end
144   aal = Array(a[:after_load])
145   aal << proc do |m, ancs|
146     unless m.associations.has_key?(parent)
147       parent_map = {prkey_conv[m]=>m}
148       child_map = {}
149       child_map[key_conv[m]] = m if key_present[m]
150       m.associations[parent] = nil
151       ancs.each do |obj|
152         obj.associations[parent] = nil
153         parent_map[prkey_conv[obj]] = obj
154         if ok = key_conv[obj]
155           child_map[ok] = obj
156         end
157       end
158       parent_map.each do |parent_id, obj|
159         if child = child_map[parent_id]
160           child.associations[parent] = obj
161         end
162       end
163     end
164   end
165   a[:after_load] ||= aal
166   a[:eager_loader] ||= proc do |eo|
167     id_map = eo[:id_map]
168     parent_map = {}
169     children_map = {}
170     eo[:rows].each do |obj|
171       parent_map[prkey_conv[obj]] = obj
172       (children_map[key_conv[obj]] ||= []) << obj
173       obj.associations[ancestors] = []
174       obj.associations[parent] = nil
175     end
176     r = model.association_reflection(ancestors)
177     base_case = model.where(prkey=>id_map.keys).
178      select(*ancestor_base_case_columns)
179     recursive_case = model.join(t, key_array.zip(prkey_array)).
180      select(*recursive_case_columns)
181     if c = r[:conditions]
182       (base_case, recursive_case) = [base_case, recursive_case].map do |ds|
183         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
184       end
185     end
186     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
187     ds = model.from(SQL::AliasedExpression.new(t, table_alias)).
188       with_recursive(t, base_case, recursive_case,
189        :args=>((key_aliases + col_aliases) if col_aliases))
190     ds = r.apply_eager_dataset_changes(ds)
191     ds = ds.select_append(ka) unless ds.opts[:select] == nil
192     model.eager_load_results(r, eo.merge(:loader=>false, :initalize_rows=>false, :dataset=>ds, :id_map=>nil)) do |obj|
193       opk = prkey_conv[obj]
194       if parent_map.has_key?(opk)
195         if idm_obj = parent_map[opk]
196           key_aliases.each{|ka_| idm_obj.values[ka_] = obj.values[ka_]}
197           obj = idm_obj
198         end
199       else
200         obj.associations[parent] = nil
201         parent_map[opk] = obj
202         (children_map[key_conv[obj]] ||= []) << obj
203       end
204       
205       if roots = id_map[extract_key_alias[obj]]
206         roots.each do |root|
207           root.associations[ancestors] << obj
208         end
209       end
210     end
211     parent_map.each do |parent_id, obj|
212       if children = children_map[parent_id]
213         children.each do |child|
214           child.associations[parent] = obj
215         end
216       end
217     end
218   end
219   model.one_to_many ancestors, a
220   
221   d = opts.merge(opts.fetch(:descendants, OPTS))
222   descendants = d.fetch(:name, :descendants)
223   d[:read_only] = true unless d.has_key?(:read_only)
224   la = d[:level_alias] ||= :x_level_x
225   d[:dataset] ||= proc do
226     base_ds = model.where(key_array.zip(prkey_array.map{|k| get_column_value(k)}))
227     recursive_ds = model.join(t, prkey_array.zip(key_array))
228     if c = d[:conditions]
229       (base_ds, recursive_ds) = [base_ds, recursive_ds].map do |ds|
230         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
231       end
232     end
233     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
234     model.from(SQL::AliasedExpression.new(t, table_alias)).
235      with_recursive(t, col_aliases ? base_ds.select(*col_aliases) : base_ds.select_all,
236       recursive_ds.select(*c_all),
237       :args=>col_aliases)
238     end
239   dal = Array(d[:after_load])
240   dal << proc do |m, descs|
241     unless m.associations.has_key?(childrena)
242       parent_map = {prkey_conv[m]=>m}
243       children_map = {}
244       m.associations[childrena] = []
245       descs.each do |obj|
246         obj.associations[childrena] = []
247         if opk = prkey_conv[obj]
248           parent_map[opk] = obj
249         end
250         if ok = key_conv[obj]
251           (children_map[ok] ||= []) << obj
252         end
253       end
254       children_map.each do |parent_id, objs|
255         parent_obj = parent_map[parent_id]
256         parent_obj.associations[childrena] = objs
257         objs.each do |obj|
258           obj.associations[parent] = parent_obj
259         end
260       end
261     end
262   end
263   d[:after_load] = dal
264   d[:eager_loader] ||= proc do |eo|
265     id_map = eo[:id_map]
266     associations = eo[:associations]
267     parent_map = {}
268     children_map = {}
269     eo[:rows].each do |obj|
270       parent_map[prkey_conv[obj]] = obj
271       obj.associations[descendants] = []
272       obj.associations[childrena] = []
273     end
274     r = model.association_reflection(descendants)
275     base_case = model.where(key=>id_map.keys).
276      select(*descendant_base_case_columns)
277     recursive_case = model.join(t, prkey_array.zip(key_array)).
278      select(*recursive_case_columns)
279     if c = r[:conditions]
280       (base_case, recursive_case) = [base_case, recursive_case].map do |ds|
281         (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.where(*c) : ds.where(c)
282       end
283     end
284     if associations.is_a?(Integer)
285       level = associations
286       no_cache_level = level - 1
287       associations = {}
288       base_case = base_case.select_append(SQL::AliasedExpression.new(Sequel.cast(0, Integer), la))
289       recursive_case = recursive_case.select_append(SQL::AliasedExpression.new(SQL::QualifiedIdentifier.new(t, la) + 1, la)).where(SQL::QualifiedIdentifier.new(t, la) < level - 1)
290     end
291     table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
292     ds = model.from(SQL::AliasedExpression.new(t, table_alias)).
293       with_recursive(t, base_case, recursive_case,
294         :args=>((key_aliases + col_aliases + (level ? [la] : [])) if col_aliases))
295     ds = r.apply_eager_dataset_changes(ds)
296     ds = ds.select_append(ka) unless ds.opts[:select] == nil
297     model.eager_load_results(r, eo.merge(:loader=>false, :initalize_rows=>false, :dataset=>ds, :id_map=>nil, :associations=>OPTS)) do |obj|
298       if level
299         no_cache = no_cache_level == obj.values.delete(la)
300       end
301       
302       opk = prkey_conv[obj]
303       if parent_map.has_key?(opk)
304         if idm_obj = parent_map[opk]
305           key_aliases.each{|ka_| idm_obj.values[ka_] = obj.values[ka_]}
306           obj = idm_obj
307         end
308       else
309         obj.associations[childrena] = [] unless no_cache
310         parent_map[opk] = obj
311       end
312       
313       if root = id_map[extract_key_alias[obj]].first
314         root.associations[descendants] << obj
315       end
316       
317       (children_map[key_conv[obj]] ||= []) << obj
318     end
319     children_map.each do |parent_id, objs|
320       objs = objs.uniq
321       parent_obj = parent_map[parent_id]
322       parent_obj.associations[childrena] = objs
323       objs.each do |obj|
324         obj.associations[parent] = parent_obj
325       end
326     end
327   end
328   model.one_to_many descendants, d
329 end