Module: TreeNodes

Defined in:
backend/app/model/mixins/tree_nodes.rb,
public/app/models/concerns/tree_nodes.rb

Overview

Mixin methods for objects that belong in an ordered hierarchy (archival objects, digital object components)

Defined Under Namespace

Modules: ClassMethods

Constant Summary collapse

POSITION_STEP =

We’ll space out our positions by this amount. This means we can insert log2(POSITION_STEP) nodes before any given node before needing to rebalance.

Sized according to the largest number of nodes we think we might see under a single parent. The size of the position column is 2^31, so position can be anywhere up to about 2 billion. For a step size of 1000, that means we can support (/ (expt 2 31) 1000) positions (around 2 million) before running out of numbers.

1000
DB_RETRIES =

The number of times we’ll retry an update that might transiently fail due to concurrent updates.

100

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.included(base) ⇒ Object 



21
22
23
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 21

def self.included(base)
  base.extend(ClassMethods)
end

Instance Method Details

#ancestors ⇒ Object 



54
55
56
57
58
59
60
61
62
 
# File 'public/app/models/concerns/tree_nodes.rb', line 54

def ancestors
  ancestor_uris = raw.fetch('ancestors', nil)

  return [] if ancestor_uris.blank? || raw['_resolved_ancestors'].nil?

  ASUtils.wrap(ancestor_uris.reverse.map {|uri|
    ASUtils.wrap(raw['_resolved_ancestors'].fetch(uri, nil)).first
  }).compact
end

#attempt_set_parent_and_position(parent_id, position) ⇒ Object 



205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 205

def attempt_set_parent_and_position(parent_id, position)
  root_uri = self.class.uri_for(self.class.root_record_type.intern, self[:root_record_id])

  if self.id == parent_id
    raise "Can't make a record into its own parent"
  end

  parent_name = if parent_id
                  "#{parent_id}@#{self.class.node_record_type}"
                else
                  "root@#{root_uri}"
                end

  new_values = {
    :parent_id => parent_id,
    :parent_name => parent_name,
    :system_mtime => Time.now
  }

  if parent_name == self.parent_name
    # Position is unchanged initially
    new_values[:position] = self.position
  else
    # Append this node to the new parent initially
    new_values[:position] = self.class.next_position_for_parent(root_record_id, parent_id)
  end

  # Run through the standard validation without actually saving
  self.set(new_values)
  self.validate

  if self.errors && !self.errors.empty?
    raise Sequel::ValidationFailed.new(self.errors)
  end

  self.class.dataset.filter(:id => self.id).update(new_values)
  self.refresh

  self.set_position_in_list(position)
end

#attempt_set_position_in_list(target_logical_position) ⇒ Object

A note on terminology: a logical position refers to the position of a node as observed by the user (0…RECORD_COUNT). A physical position is the position number stored in the database, which may have gaps.



56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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 'backend/app/model/mixins/tree_nodes.rb', line 56

def attempt_set_position_in_list(target_logical_position)
  DB.open do |db|
    ordered_siblings = db[self.class.node_model.table_name].filter(
      :root_record_id => self.root_record_id, :parent_id => self.parent_id
    ).order(:position)
    siblings_count = ordered_siblings.count

    target_logical_position = [target_logical_position, siblings_count - 1].min

    current_physical_position = self.position
    current_logical_position = ordered_siblings.where { position < current_physical_position }.count

    # If we are already at the correct logical position, do nothing
    return if (target_logical_position == current_logical_position)

    # We'll determine which node will fall to the left of our moved node, and
    # which will fall to the right.  We're going to set our physical position to
    # the halfway point of those two nodes.  For example, if left node is
    # position 1000 and right node is position 2000, we'll take position 1500.
    # If there's no gap, we'll create one!
    #
    left_node_idx = target_logical_position - 1

    if current_logical_position < target_logical_position
      # If the node is being moved to the right, we need to adjust our index to
      # compensate for the fact that everything logically shifts to the left as we
      # pop it out.
      left_node_idx += 1
    end

    left_node_physical_position =
      if left_node_idx < 0
        # We'll be the first item in the list (nobody to the left of us)
        nil
      else
        ordered_siblings.offset(left_node_idx).get(:position)
      end

    right_node_idx = left_node_idx + 1

    right_node_physical_position =
      if right_node_idx >= siblings_count
        # We'll be the last item in the list (nobody to the right of us)
        nil
      else
        ordered_siblings.offset(right_node_idx).get(:position)
      end

    new_position =
      if left_node_physical_position.nil? && right_node_physical_position.nil?
        # We're first in the list!
        new_position = TreeNodes::POSITION_STEP
      else
        if right_node_physical_position.nil?
          # Add to the end
          left_node_physical_position + TreeNodes::POSITION_STEP
        else
          left_node_physical_position ||= 0

          if (right_node_physical_position - left_node_physical_position) <= 1
            # We need to create a gap to fit our moved node
            right_node_physical_position = ensure_gap(right_node_physical_position)
          end

          # Put the node we're moving halfway between the left and right nodes
          left_node_physical_position + ((right_node_physical_position - left_node_physical_position) / 2)
        end
      end

    self.class.dataset.db[self.class.table_name]
      .filter(:id => self.id)
      .update(:position => new_position,
              :system_mtime => Time.now)
  end
end

#breadcrumb ⇒ Object 



3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'public/app/models/concerns/tree_nodes.rb', line 3

def breadcrumb
  crumbs = []

  # add all ancestors to breadcrumb
  path_to_root.each_with_index do |node, level|
    crumbs << {
      :uri => breadcrumb_uri_for_node(node),
      :type => node['jsonmodel_type'],
      :crumb => breadcrumb_title_for_node(node, level),
      :identifier => breadcrumb_identifier(node, node['jsonmodel_type'])
    }
  end

  # and now yourself
  crumbs << {
    :uri => '',
    :type => primary_type,
    :crumb => display_string,
    :identifier => breadcrumb_identifier(self, primary_type)
  }

  crumbs
end

#breadcrumb_identifier(record, type) ⇒ Object 



28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'public/app/models/concerns/tree_nodes.rb', line 28

def breadcrumb_identifier(record, type)
  case type
  when 'resource'
    if resolved_resource
      id_0 = resolved_resource['id_0']
      id_1 = resolved_resource['id_1']
      id_2 = resolved_resource['id_2']
      id_3 = resolved_resource['id_3']

      id_components = [id_0, id_1, id_2, id_3].reject {|i| i.nil? }
      id_components.join("-")
    end
  end
end

#breadcrumb_title_for_node(node, _) ⇒ Object 



49
50
51
 
# File 'public/app/models/concerns/tree_nodes.rb', line 49

def breadcrumb_title_for_node(node, _)
  node.fetch('title')
end

#breadcrumb_uri_for_node(node) ⇒ Object 



44
45
46
 
# File 'public/app/models/concerns/tree_nodes.rb', line 44

def breadcrumb_uri_for_node(node)
  node['node'].nil? ? node.fetch('root_record_uri') : node.fetch('node')
end

#children ⇒ Object 



247
248
249
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 247

def children
  self.class.filter(:parent_id => self.id).order(:position)
end

#ensure_gap(start_physical_position) ⇒ Object 



132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 132

def ensure_gap(start_physical_position)
  siblings = self.class.dataset
             .filter(:root_record_id => self.root_record_id)
             .filter(:parent_id => self.parent_id)
             .filter { position >= start_physical_position }

  # Sigh.  Work around:
  # http://stackoverflow.com/questions/5403437/atomic-multi-row-update-with-a-unique-constraint
  siblings.update(:parent_name => Sequel.lit(DB.concat('CAST(id as CHAR(10))', "'_temp'")))

  # Do the real update
  siblings.update(:position => Sequel.lit('position + ' + TreeNodes::POSITION_STEP.to_s),
                  :system_mtime => Time.now)

  # Puts it back again
  siblings.update(:parent_name => self.parent_name)

  start_physical_position + TreeNodes::POSITION_STEP
end

#has_children? ⇒ Boolean

Returns:

  • (Boolean) 


252
253
254
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 252

def has_children?
  self.class.filter(:parent_id => self.id).count > 0
end

#logical_position ⇒ Object 



153
154
155
156
157
158
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 153

def logical_position
  relative_position = self.position
  self.class.dataset.filter(
    :root_record_id => self.root_record_id, :parent_id => self.parent_id
  ).where { position < relative_position }.count
end

#previous_node ⇒ Object 



257
258
259
260
261
262
263
264
265
266
267
268
269
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 257

def previous_node
  pos = self.position
  node = self.class.filter(:parent_id => self.parent_id)
                   .filter(:root_record_id => self.root_record_id)
                   .where { position < pos }
                   .reverse(:position).limit(1).first

  if !node && !self.parent_id
    raise NotFoundException.new("No previous node")
  end

  node || self.class[self.parent_id]
end

#set_parent_and_position(parent_id, position) ⇒ Object 



198
199
200
201
202
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 198

def set_parent_and_position(parent_id, position)
  self.class.retry_db_update do
    attempt_set_parent_and_position(parent_id, position)
  end
end

#set_position_in_list(target_logical_position) ⇒ Object 



46
47
48
49
50
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 46

def set_position_in_list(target_logical_position)
  self.class.retry_db_update do
    attempt_set_position_in_list(target_logical_position)
  end
end

#set_root(new_root) ⇒ Object

Move this node (and all records under it) to a new tree.



26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 26

def set_root(new_root)
  self.root_record_id = new_root.id

  if self.parent_id.nil?
    # This top-level node has been moved to a new tree.  Append it to the end of the list.
    root_uri = self.class.uri_for(self.class.root_record_type.intern, self.root_record_id)
    self.parent_name = "root@#{root_uri}"

    self.position = self.class.next_position_for_parent(self.root_record_id, self.parent_id)
  end

  save
  refresh

  children.each do |child|
    child.set_root(new_root)
  end
end

#transfer_to_repository(repository, transfer_group = []) ⇒ Object 



272
273
274
275
276
277
278
279
280
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 272

def transfer_to_repository(repository, transfer_group = [])
  # All records under this one will be transferred too
  children.each_with_index do |child, i|
    child.transfer_to_repository(repository, transfer_group + [self])
  end

  # ensure that the sequence if updated
  super
end

#trigger_index_of_child_nodes ⇒ Object 



192
193
194
195
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 192

def trigger_index_of_child_nodes
  self.children.update(:system_mtime => Time.now)
  self.children.each(&:trigger_index_of_child_nodes)
end

#update_from_json(json, extra_values = {}, apply_nested_records = true) ⇒ Object 



161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
 
# File 'backend/app/model/mixins/tree_nodes.rb', line 161

def update_from_json(json, extra_values = {}, apply_nested_records = true)
  root_uri = self.class.uri_for(self.class.root_record_type, self.root_record_id)

  do_position_override = json[self.class.root_record_type]['ref'] != root_uri || extra_values[:force_reposition]

  if do_position_override
    extra_values.delete(:force_reposition)
    json.position = nil
    # Through some inexplicable sequence of events, the update is allowed to
    # change the root record on the fly.  I guess we'll allow this...
    extra_values = extra_values.merge(self.class.determine_tree_position_for_new_node(json))
  else
    # ensure we retain the current (physical) position when updating the record
    extra_values['position'] = self.position
  end

  obj = super(json, extra_values, apply_nested_records)

  if json.position
    # Our incoming JSON wants to set the position.  That's fine
    set_position_in_list(json.position)
  end

  self.class.ensure_consistent_tree(obj)

  trigger_index_of_child_nodes

  obj
end