Comparison to writebook's positionable concern?

[nickjj]

Writebook is a tool designed by Basecamp as part of their "Once" line of tools. It's free.

It comes with a Positionable concern that you can use in a model such as positioned_within :book, association: :leaves, filter: :active.

Here's the concern's code:

module Positionable
  extend ActiveSupport::Concern

  REBALANCE_THRESHOLD = 1e-10
  ELEMENT_GAP         = 1

  included do
    scope :positioned, -> { order(:position_score, :id) }

    scope :before, ->(other) { positioned.where("position_score < ?", other.position_score) }
    scope :after,  ->(other) { positioned.where("position_score > ?", other.position_score) }

    around_create :insert_at_default_position
    after_save_commit :rebalance_positions, if: :rebalance_required?
  end

  class_methods do
    def positioned_within(parent, association:, filter:)
      define_method :positioning_parent do
        send(parent)
      end

      define_method :all_positioned_siblings do
        positioning_parent.send(association).send(filter).positioned
      end

      define_method :other_positioned_siblings do
        all_positioned_siblings.excluding(self)
      end

      private :positioning_parent, :all_positioned_siblings, :other_positioned_siblings
    end
  end

  def previous
    other_positioned_siblings.before(self).last
  end

  def next
    other_positioned_siblings.after(self).first
  end

  def move_to_position(offset, followed_by: [])
    with_positioning_lock do
      all_to_move = [ self, *followed_by ]
      before, after = before_and_after_for(offset: offset, moving: all_to_move)
      gap = (after - before) / (all_to_move.count + 1)

      all_to_move.each.with_index(1) do |item, index|
        item.update!(position_score: before + (index * gap))
      end

      remember_to_rebalance_positions if gap < REBALANCE_THRESHOLD
    end
  end

  def position_as_percentage
    100 * ordinal_position.to_f / all_positioned_siblings.count
  end

  private
    def ordinal_position
      other_positioned_siblings.before(self).count + 1
    end

    def insert_at_default_position
      with_positioning_lock do
        position_at_end
        yield
      end
    end

    def position_at_start
      self.position_score = (all_positioned_siblings.minimum(:position_score) || (2 * ELEMENT_GAP)) - ELEMENT_GAP
    end

    def position_at_end
      self.position_score = (all_positioned_siblings.maximum(:position_score) || 0) + ELEMENT_GAP
    end

    def before_and_after_for(offset:, moving:)
      other_items = all_positioned_siblings.excluding(moving)

      if offset < 1
        after = all_positioned_siblings.minimum(:position_score) || (2 * ELEMENT_GAP)
        before = after - ELEMENT_GAP
      else
        before, after = other_items.offset(offset - 1).limit(2).pluck(:position_score)
        before ||= all_positioned_siblings.maximum(:position_score)
        after ||= before + (moving.count.succ * ELEMENT_GAP)
      end

      [ before, after ]
    end

    def remember_to_rebalance_positions
      @rebalance_required = true
    end

    def rebalance_required?
      @rebalance_required
    end

    def rebalance_positions
      with_positioning_lock do
        odered = all_positioned_siblings.select("row_number() over (order by position_score, id) as new_score, id")
        sql = "update #{self.class.table_name} set position_score = new_score from (#{odered.to_sql}) as ordered where #{self.class.table_name}.id = ordered.id"

        self.class.connection.execute sql
      end
      @rebalance_required = false
    end

    def with_positioning_lock(&block)
      positioning_parent.with_lock &block
    end
end

Here's its test suite:

require "test_helper"

class Leaf::PositionableTest < ActiveSupport::TestCase
  setup do
    @leaves = books(:handbook).leaves.positioned
  end

  test "items are sorted in positioned order" do
    assert_equal [ leaves(:welcome_section), leaves(:welcome_page), leaves(:summary_page), leaves(:reading_picture) ], @leaves
  end

  test "items can be moved earlier" do
    leaves(:welcome_page).move_to_position(0)

    assert_equal [ leaves(:welcome_page), leaves(:welcome_section), leaves(:summary_page), leaves(:reading_picture) ], @leaves.reload
  end

  test "items can be moved beyond the start, which puts them at the start" do
    leaves(:welcome_page).move_to_position(-99)

    assert_equal [ leaves(:welcome_page), leaves(:welcome_section), leaves(:summary_page), leaves(:reading_picture) ], @leaves.reload
  end

  test "items can be moved later" do
    leaves(:welcome_section).move_to_position(2)

    assert_equal [ leaves(:welcome_page), leaves(:summary_page), leaves(:welcome_section), leaves(:reading_picture) ], @leaves.reload
  end

  test "items can be moved beyond the end, which puts them at the end" do
    leaves(:welcome_section).move_to_position(99)

    assert_equal [ leaves(:welcome_page), leaves(:summary_page), leaves(:reading_picture), leaves(:welcome_section) ], @leaves.reload
  end

  test "items can be moved to their existing position" do
    leaves(:welcome_page).move_to_position(1)

    assert_equal [ leaves(:welcome_section), leaves(:welcome_page), leaves(:summary_page), leaves(:reading_picture) ], @leaves.reload
  end

  test "items can be moved in blocks" do
    leaves(:welcome_section).move_to_position(1, followed_by: [ leaves(:welcome_page), leaves(:summary_page) ])

    assert_equal [ leaves(:reading_picture), leaves(:welcome_section), leaves(:welcome_page), leaves(:summary_page) ], @leaves.reload
  end

  test "new items are inserted at the end" do
    new_page = books(:handbook).press Page.new(body: "New Page"), title: "New Page"

    assert_equal new_page, books(:handbook).leaves.positioned.last
  end

  test "the first item in the collection has the expected score" do
    books(:handbook).leaves.destroy_all
    new_page = books(:handbook).press Page.new(body: "New Page"), title: "New Page"

    assert_equal 1, new_page.position_score
  end

  test "positioning is rebalanced when necessary" do
    leaves(:welcome_section).update!(position_score: 1e-11)
    leaves(:welcome_page).update!(position_score: 2e-11)

    leaves(:summary_page).move_to_position(1)

    assert_equal leaves(:summary_page), @leaves.reload.second
    assert_equal [ 1, 2, 3, 4 ], @leaves.pluck(:position_score)
  end

  test "items know their neighbours" do
    assert_equal leaves(:welcome_section), leaves(:welcome_page).previous
    assert_equal leaves(:summary_page), leaves(:welcome_page).next

    assert_nil leaves(:welcome_section).previous
    assert_nil leaves(:reading_picture).next
  end

  test "only active items are included as neighbours" do
    assert_equal leaves(:summary_page), leaves(:welcome_page).next

    leaves(:summary_page).trashed!

    assert_equal leaves(:reading_picture), leaves(:welcome_page).next
  end

  test "only active items are counted when determining position" do
    leaves(:welcome_page).trashed!

    leaves(:welcome_section).move_to_position(1)
    assert_equal [ leaves(:summary_page), leaves(:welcome_section), leaves(:reading_picture) ], @leaves.reload.active

    leaves(:welcome_section).move_to_position(0)
    assert_equal [ leaves(:welcome_section), leaves(:summary_page), leaves(:reading_picture) ], @leaves.reload.active
  end
end

Given the above, are there pros and cons of using that vs your gem? Both appear to support similar features of setting a position. Any performance gotchas or edge cases that you see in the concern that your gem is immune to?

[brendon]

Hi @nickjj, thanks for that. It's interesting to see other code around this problem :)

This positionable concern is more akin to ranked-model where items are inserted with the possibility of gaps between positions but looking at the tests it defaults to sequential integer positions. I guess when an item is inserted between two integer positions then a rebalance is triggered.

My gem certainly triggers more SQL and inverts the positions to be negative, then positive again (as its method of creating gaps) as a way to allow for unique position indexes.

Performance wise, you'd have to run some benchmarks that simulate how you'd use the list (always appending to the end, with infrequent reorderings?).

Usability wise, a gem is easier to include in your code and to keep up to date. You'd have to check in on the concern every now and then to see if they'd changed anything or fixed any bugs. My gem also has a bit more support around it for updating the value using relative positions and has the struct for making those workable within forms in Rails.

Hope that helps a bit. I always wondered what Basecamp did for positioning since they abandoned ActsAsList :) Thanks for posting this here :)

[brendon]

Hi @swrobel, we rely heavily on the position being unique, and ideally sequential with no gaps, so we rely a lot of the uniqueness constraint and locking to guarantee this. Some of the logic breaks down if the list is sparse (gaps between position integers). Let me know if you need more info than this :)

[swrobel]

Hey @brendon, really appreciate the response! We're long-time acts_as_list users, and attempted the move to positioning due to the need for multiple lists on a model, but had to revert because of performance issues. A lot of this may be special-case type stuff, but we have several models where we insert new items at the beginning, and do bulk inserts, which means we've gone from doing N*1 UPDATEs per bulk insertion to N*2, as positioning runs 2 queries per re-ordering operation.

I guess my question, specifically, is: what was the rationale behind moving to this 2-queries-per-re-ordering model? Are there some scenarios where it's more performant than the strategy used by acts_as_list? If not, was there some other tradeoff that was made, and if so, what was that tradeoff? I'm the type of person who appreciates clean data, but in practice, I'm wondering what benefit comes from enforcing uniqueness/no gaps, and if it's worth the performance trade-off, assuming there is one in all cases.

[brendon]

No worries @swrobel :) I found that the only wait to maintain uniqueness when shuffling the list was to invert positions into the negative integer space then re-invert them with the change in position (e.g. to make a gap). One of the database engines (I can't remember which) doesn't allow for ordered updates. If that were allowed then we'd just order the updates to ensure the uniqueness constraint wasn't violated.

I'm definitely open to improvements here. It's the only solution I could find that satisfied the requirements for uniqueness and non-sparseness.

Is it necessary to insert to the start of the list each time? Could you instead always append and then sort the list in reverse when accessing it? That would reduce the cost I think :)

[swrobel]

@brendon thanks again, and sorry to be a pedant, but I'd still like to dig into this:

the requirements for uniqueness and non-sparseness

What's the tangible benefit that comes from these requirements? Given that we're happy with the perf of acts_as_list, I'd be more keen to add support for multiple lists on a model to it, unless there's some major blocker to doing so that you're aware of. However, I also feel like I must be missing something about positioning that I'd be giving up, besides multiple lists support, which is why I've been trying to understand why you decided to create another gem around those requirements (appreciate how prolific you are in this space!), but I just can't grok it, no matter how many times I've read the README (and pretty much all of the issues for positioning as well, lol).

[brendon]

No worries at all :) I wrote this gem as I felt acts_as_list was just too far gone as a codebase to reform. It was originally written by DHH and then rewritten following changes in Rails 2 and 3 and a lot of the logic within it was very hard to follow and sometimes buggy. It actually doesn't cope 100% well with sparse position integers in some circumstances and isn't atomic in the way it updates things so you can end up with gaps as well as items with the same position integer in the same list.

The reason it can't support multiple lists in the same model is the way it pollutes the model's namespace with generic methods that assume one global list configuration. I took a different approach with positioning where there are just one or two generic methods and then the rest of the functionality is placed within a class that we instantiate to do things in the callbacks.

I originally created the code for this gem as a concern (similar to the write book one) and then turned it into a gem when I extracted it from my project.

Feel free to keep asking questions :D