Add test case for moving items between lists with unique constraint

[StefSchenkelaars]

This PR is maybe more of an issue than an actual PR but since I wrote a test case to validate the problem for myself before opening an issue, I thought let's just include that in a PR.

So the issue is when you have two scoped lists and you move an item between two lists, the database will complain about a unique constraint (if you have one of course).

It fails since the gem wants to move all the lower items in the old list up by 1 before the item has actually switched the list. I had a quick trial en error way of trying to fix this. It is all about the List#check_scope method where the order is basically wrong but just changing the order fails a lot of other specs. So some help here would be really helpful 😄

In addition to this, if I remove the unique constraint, the 'old' list has positions [1, 3] instead of [1, 2]. Guess that's also not what is expected right?

[brendon]

Hi @StefSchenkelaars, meet @swelther! :) It seems you two are struggling with unique constraints! The library wasn't built with these in mind and various people have tried to fix this over time. Currently there is an averagely functioning :sequential_updates option that updates everything one-by-one. @swelther, was investigating whether we could just utilise reordering to shift things around (within UPDATE statements) in an orderly fashion. It might be useful for you two to compare notes.

In my uses of acts_as_list I don't use constraints and I also know my positioning gets mucked up, especially when it comes to concurrent requests.

For your use case @StefSchenkelaars, the optimal way to update would be something that does this?:

Within one transaction:

1. Identify new scope
2. On the new scope, punch a hole by selecting greater list items (in reverse order) and updating them all by incrementing their position by 1. The last item in the list should be moved first so as not to violate any constraints.
3. Update the moved items id and scope to the new list.
4. Decrement greater items in the old list (in normal order) so the closest to the moved item moves first to avoid constraints. End transaction

The other failing tests might just be to do with an expected explicit order of items (though the order might not actually matter?)

[swelther]

@StefSchenkelaars Did you try with the sequential_updates: true option? It wasn't documented in the readme until a few days ago, so you might have missed it? - same as me :D

Using one update-stmt did work when using mysql, but Postgresql still complained. As I'm currently not using pg I didn't investigate further if there might be a trick. It felt too buggy to me to follow this path further down. I fear a different mysq/pg version might change the behaviour and it will fail again. Not sure about two lists, I didn't check that.

Using the sequential update option worked for me because the lists are not very big. Executing like 10 update stmts in some rarely cases doesn't hurt much :)

[StefSchenkelaars]

@swelther I did try it with sequential updates. They are also enabled in the test case but it still crashes. So I've added the constraints on my database, everything went fine until someone tried to move items to another list.

I think if we want to solve this properly, we end up with basically redesigning the entire gem logic. But I am not sure how people use this gem but I see myself mainly setting the position directly and let acts_as_list handle the other items. I don't use many of the helper methods like move_higher etc.

So if there are more people struggling with this, I don't mind putting some effort into fixing this but not sure if that's possible with keeping the entire API the same. And of course redesigning a gem like this with loads of fixes over time is way more tricky that it seems. So like to hear your opinions on this, is it worth it to starting working on this?

[StefSchenkelaars]

@brendon And what do think about this if you compare it to ranked-model? It seems that in the way they handle the positions in the database, it will not have these problems.

[brendon]

@StefSchenkelaars, funnily enough I'm the maintainer for ranked-model too! :D I also get tickets there for deadlocks and uniqueness constraints. We just solved a recent rebalancing uniqueness issue by blanking the ranks for a scope then reassigning them within a transaction.

I use both of these gems on different projects. Given @dhh originally developed this code, I'd be super interested to know what they do these days for positioning given I'm pretty sure they don't use this gem.

ranked-model has a quirk where after adding about 30 records to the end of the list, it exhausts the free space available and the list needs rebalancing. This is because when an item is added to the start or end of the list, it is positioned at 50% of the remaining gap at the end of the integer range. I guess I'm trying to say both gems aren't perfect and perhaps there's another way to do positioning that doesn't suffer from all these downsides. :)

[StefSchenkelaars]

Hi there, it has been some time since there was some activity here but maybe we can get some discussion started again. I would like to 'fix' this by putting everything in a single transaction with a fixed number of queries. So in your first comment you basically write down what I also thought:

Within one transaction:

1. Identify new scope
2. On the new scope, punch a hole by selecting greater list items (in reverse order) and updating them all by incrementing their position by 1. The last item in the list should be moved first so as not to violate any constraints.
3. Update the moved items id and scope to the new list.
4. Decrement greater items in the old list (in normal order) so the closest to the moved item moves first to avoid constraints. End transaction

The problem however already raises at point 2. Since as I understand most SQL DB systems, you can't define the order of the update. So say you have a list of items with position 1 to 4 and you want to punch a hole at position 2, the sequential updates starts to create the hole by moving 4 to 5, 3 to 4 etc. I tried to achieve the same in a single query but I think that's not possible (but please prove me wrong ;)).

So an idea I worked with was to first multiply everything with -1 and then perform a * -1 + 1 to move the items the the correct position. So within 1 transaction do this:

1. You have list 1,2,3,4
2. You move the items you need to move to far away to obtain 1,-2,-3,-4
3. You multiply and move items to new position 1,3,4,5

The used operator in this example (*-1) could also be something else like adding the highest number of the list if you don't want negative numbers:

1. You have list 1,2,3,4
2. You move the items you need to move to far away to obtain 1,6,7,8
3. You multiply and move items to new position 1,3,4,5

Another think I looked at was using deferred constraints. This way you only check the unique constraint after the transaction. However, I don't think all DB systems offer this and I am also not sure how to nicely integrate this into rails / schema / ...

So what do you think about these options? Does this even make sense to work on one of those? Are there any other / better options?

[StefSchenkelaars]

Ok, had a day off today so did some quick tests. Basically I removed all methods and callbacks and created 4 callbacks that should handle the big chunks of logic:

See code

[Also available in gist](https://gist.github.com/StefSchenkelaars/b249ee9aaeb17c9f0a9ca802a932538d) ```ruby before_create :set_default_position before_save :prepare_new_position after_save :cleanup_new_position after_save :cleanup_old_position def set_default_position return if self[position_column] bottom_item = acts_as_list_class .unscope(:select, :where) .where(scope_condition) .where.not(position_column => nil) .reorder(position_column => :desc) .limit(1) .pluck(position_column) .try(:first) if bottom_item self[position_column] = bottom_item + 1 else self[position_column] = acts_as_list_top end # Don't halt the callback chain true end def prepare_new_position old_position, new_position = changes[position_column] new_position ||= self[position_column] scope = acts_as_list_class .unscope(:select, :where) .where(scope_condition) .where(self.class.arel_table[position_column].gteq(new_position)) scope = scope.where(self.class.arel_table[position_column].lt(old_position)) if old_position scope.update_all("#{position_column} = (#{position_column} + 1) * -1") end def cleanup_new_position old_position, new_position = changes[position_column] new_position ||= self[position_column] acts_as_list_class .unscope(:select, :where) .where(scope_condition) .where(self.class.arel_table[position_column].lt(0)) .update_all("#{position_column} = #{position_column} * -1") end def cleanup_old_position old_position, _new_position = saved_changes[position_column] old_scope_value, new_scope_value = saved_changes[scope_name.to_s] return unless old_scope_value && old_scope_value != new_scope_value acts_as_list_class .unscope(:select, :where) .where(scope_name => old_scope_value) .where(self.class.arel_table[position_column].gteq(old_position)) .update_all("#{position_column} = #{position_column} - 1") end ```

It handles inserts, moving within a list and moving between lists. So there are many options / methods that do not work yet but I wonder what you think about this.

[brendon]

Hi @StefSchenkelaars, this is great work! The issues area for this gem have gone mental over the Easter weekend! Still catching up :) I guess people have a lot of time on their hands now :D

I've had a quick look through the code and it's nice and clean and straightforward. Just a few comments, especially around the ordered updates concept:

• Can we guarantee that all of these callbacks operate within one database transaction? Is it possible for a user to accidentally kill the transaction half way through by adding a before_save callback of their own that uses a method incompatible with an open transaction? I'm just brainstorming here :)
• It seems it might be possible to do ordered updates via views: https://www.myintervals.com/blog/2007/07/23/postgresql-update-a-table-using-order-by/ though it's a bit longwinded. If the same approach worked for both MySQL and Postgres (we could skip it for Sqlite?) then that might be a viable alternative. We can hide the messiness within the gem and create/drop the view on the fly as we need it?
• I like the idea of limiting the interface to the minimum number of methods required. acts_as_list has a bunch of methods that are confusing and can break things (like insert_at). I like how ranked-model makes it nearly impossible to manually mess with the position column, though I think that's a bit too difficult to do with acts_as_list due to its history of direct manipulation where necessary.

Let me know I you need any more thoughts :)

[StefSchenkelaars]

Hi @brendon,

Transactions I have to look into this but I think in general it shouldn't be too big of a problem. Basically if someone kills the transaction, everything is reverted anyway. For me, the open question here is especially about nested transactions. I always get crazy if I have to deal with them, it's not always clear what transaction is rolled back, and will the parent be also rolled back etc. But I think that all of the ActiveRecord callbacks run in a single (main) transaction.

Updates through views I actually think that this is not a viable option if you really have to write a view to the database. This will give concurrency problems and I think also speed wise it will not be so good. Maybe it's also possible with dynamic SQL functions but then I think you can't use Arel which is something I would really like to hold on to.

Limiting instance methods Since if something like this will result in a major version anyway, we could only include them if you pass an option:

acts_as_list instance_methods: true

It will be a braking change but it can then easily be 'fixed'.

[brendon]

That's what I was meaning around transactions. I worry that users might explicitly start a new transaction in their callbacks and then I wonder what happens to our transaction? From memory MySQL doesn't support nested transactions so does it close our transaction (successfully)? It's been a long time since I've looked at the problem so Rails may have worked around this now? I suppose we can add tests for those scenarios to ensure it all works :)

Just a quick note, you could use pick instead of pluck to grab a single value from an assumed:

def pick(*column_names)
  limit(1).pluck(*column_names).first
end

not sure how far back support for that goes :D

Fair point on the views approach. Certainly feels hacky :)

Also good point about allowing for backward compatibility. I guess the ideal is to reduce the interface to just being able to manipulate the position column directly, plus optionally the scope. We should probably keep the introspection methods like first? etc...

---

Just to muddy the waters slightly, I came across a technique to allow for the reordering of items without needing to touch surrounding items. Instead of using sparse integers (like ranked-model) it uses normal integers to start with, but then if you position something between items 1 and 2, it'll set the position column to 1.5. It'd probably still have the same flaw as ranked-model where a gap can be exhausted quite quickly due to precision and rounding, but for the common case of appending to the end of the list, exhaustion would likely never happen. You could allow for negative numbers to prevent exhaustion if always prepending to the list.

Another approach I saw used strings as the ordering value. They'd then manipulate the strings to order the items alphabetically. The limitation in this case would be the length of the string column.

I only mention these as they allow for ordering without worrying about updating surrounding siblings.

[brendon]

As this PR went cold, I'm going to close it for now. I suggest looking at my new gem: https://github.com/brendon/positioning.

It solves the scope issue by first inverting all the positions of items to be moved out of the way to be negative versions of themselves. It then inverts them again with the appropriate adjustment (+1 or -1) so that the gap is filled. Feels a little brutish but it works well. We use an advisory lock to ensure only one process is doing this at a time.