Merge lp:~openerp-dev/openobject-server/trunk-orm-resequence-method-xmo into lp:openobject-server

[Xavier (Open ERP)]

Adds a `resequence(ids, field='sequence')` to BaseModel. This is mostly used in drag&drop of the Kanban and List views, when the object has a sequencing field (which doesn't have to be named `sequence` though that's the most common case).

There are currently a pure-JS implementation in the list view and a basic Python implementation in a controller for the kanban view, both rewrite pretty much all records (not exactly true but close enough).

AL wanted resequencing to limit sequence number changes similar to the GTK client, which implements the behavior in `widget.model.group.ModelRecordGroup.set_sequence`, this was also the occasion to add the feature to the server so it doesn't have to be reimplemented everywhere all the time.

How the system works in the GTK client as far as I understood it:

* set_sequence gets the source and destination indexes for the moved record, and currently loaded records are set in `self.model`
* if there are duplicate sequence numbers across loaded models, all of `self.models` is resequenced by first taking existing unique sequence numbers then counting up from the biggest existing number (with an increment of 1).
* if there are no duplicates, find just the sub-sequence affected by the moved record (basically all records between the source and destination), rotate the sequence numbers (à la collections.deque.rotate) to match the move and write that out.

This both keeps sequence numbers more stable (especially if records are not moved around much) and optimizes the number of writes (the default length of a list view being 80 records…).

Theoretically, the optimization could be applied as long as there are no duplicates within the affected sub-sequence, but that's not implemented in the GTK client and there's more work to be done to avoid odd effects where the sub-sequence itself has no duplicates but there's a series of duplicates straddling the boundary (consecutive records with the same sequence number, but only the second one is included in the sub-sequence), since read() will order by oid (implicit) after having used _order, there's a risk of "shuffling" records as far as the user can see. So it's been left out for now.

[Vo Minh Thu (thu)]

You assume `read()` follows `_order`, which seems good. But this means that you can't choose the `field` parameter in `resequence()`: you make a diff between the given ids and the ids as returned by `read()`.

You raise ValueError on some conditions. If multiple `insert` and `delete` are returned by get_opcodes(), they will reuse the same ops dictionary entry, so the len(ops)!=2 doesn't seem the right way to assert what you want. (You want exactly one insert and one delete.) Maybe you can loop over get_opcodes and directly assign `source` and `dest`... Maybe something like:

>>> source = None
>>> for tag, (i1, _, _, _) in get_opcodes():
... if tag == 'insert':
... source, multiple_sources = i1, source
...
>>> assert source and multiple_sources is None

I think the code would be simpler by having a single if source < dest, without factoring out to and reusing a single slice object.

zip(seq, ids) is funny, I would have thought of zip(ids, seq) instead :)

Otherwise, seems good to me.

[Xavier (Open ERP) (xmo-deactivatedaccount)]

> You assume `read()` follows `_order`, which seems good. But this means that you can't choose the `field` parameter in `resequence()`: you make a diff between the given ids and the ids as returned by `read()`.

Yes, should probably assert that the provided field is the (first?) one in _order. Would that be enough?

> If multiple `insert` and `delete` are returned by get_opcodes(), they will reuse the same ops dictionary entry, so the len(ops)!=2 doesn't seem the right way to assert what you want.

That's why there's a second condition asserting the `delete` op only (re)moves a single element just below that: first assert there's only two operations (technically it should check that there's a single insert and a single delete but I'm assuming we won't be resequencing 2 removals, that would be weird), then assert that the deletion only affects a single record.

> I think the code would be simpler by having a single if source < dest, without factoring out to and reusing a single slice object.

Something along the lines of

    if source < dest:
        s = slice(source, dest)
        new_seq = seq[s]
        new_seq.insert(0, new_seq.pop())
    else:
        s = slice(dest, source + 1)
        new_seq = seq[s]
        new_seq.append(new_seq.pop(0))
    ids = record_ids[s]

?

> zip(seq, ids) is funny, I would have thought of zip(ids, seq) instead :)

I interpreted `seq` as an index number (which it fundamentally is) and modeled the order after `enumerate`.

[lp:~openerp-dev/openobject-server/trunk-orm-resequence-method-xmo]

4888. By Xavier (Open ERP) on 2013-07-26

[MERGE] from trunk

4889. By Xavier (Open ERP) on 2013-07-26

[IMP] simplify slicing of records to resequence

Unmerged revisions

4889. By Xavier (Open ERP) on 2013-07-26

[IMP] simplify slicing of records to resequence

4888. By Xavier (Open ERP) on 2013-07-26

[MERGE] from trunk

4887. By Xavier (Open ERP) on 2013-06-04

[IMP] check that the reseq optimization does indeed reduce the number of writes where it should

4886. By Xavier (Open ERP) on 2013-06-04

[IMP] add partial resequencing optimization

4885. By Xavier (Open ERP) on 2013-06-03

[ADD] basic resequencing

take all existing unique sequence numbers, set them on provided ids
list, extend with new sequence numbers (from biggest one available) if
there were seq num dupes.

4884. By Xavier (Open ERP) on 2013-06-03

[TESTS] check resequencing assumption about ordering of read result

4883. By Xavier (Open ERP) on 2013-06-03

[FIX] setting and cleanup of cr in TransactionCase

* set cr on current class, not TransactionCase itself, to better
  isolate various test cases

* delete cr attribute at the end of the test, so things blow up
  clearly when setUp was not correctly called (e.g. overridden but did
  not call its own parent), otherwise the result is an odd error about
  a cursor already closed within the test.

=== modified file 'openerp/osv/orm.py'
--- openerp/osv/orm.py	2013-07-25 10:49:14 +0000
+++ openerp/osv/orm.py	2013-07-26 13:08:25 +0000
@@ -44,6 +44,7 @@
 import collections
 import copy
 import datetime
+import difflib
 import itertools
 import logging
 import operator
@@ -5365,6 +5366,99 @@
         raise AttributeError(
             "'%s' object has no attribute '%s'" % (type(self).__name__, name))
 
+    def resequence(self, cr, uid, ids, field='sequence', context=None):
+        """ Re-sequences the records to the order specified by ``ids``
+        attempting to conserve existing order and sequence numbers
+
+        .. note::
+
+            the records will only be resequenced if they have been reordered,
+            if ``ids`` is in its "natural" order the reseq request will be
+            ignored
+
+        :param cr:
+        :param int uid:
+        :param list(int) ids: all ids available, after the record to move has
+                              been moved to its new position
+        :param str field: "sequencing" field, defaults to ``'sequence'``
+        :param dict context:
+        """
+        records = self.read(cr, uid, ids, [field], context=context)
+
+        record_ids = [record['id'] for record in records]
+
+        # record list was not reordered -> don't resequence
+        if ids == record_ids: return
+
+        seq = [record[field] for record in records]
+        # Get all non-repeating sequence numbers
+        unique_seq = sorted(set(seq))
+
+        if len(unique_seq) != len(ids):
+            # Re-sequence everything, start with non-repeating sequence numbers
+            # then count from the biggest existing sequence number to get
+            # missing due to dupes
+            seq_next = unique_seq[-1] + 1
+            new_seq = itertools.chain(unique_seq, itertools.count(seq_next))
+        else:
+            # All sequence numbers are unique, we can minimize writes by just
+            # swapping around sequence numbers between the source and
+            # destination of the moved record. Theoretically we could do that
+            # if the set between source and destination only had uniques,
+            # but things may get hairier if there are duplicates straddling
+            # the boundary so leave that case to generic handling of duplicate
+            # seqs for now
+            ops = dict(
+                (tag, (i1, i2, j1, j2))
+                for tag, i1, i2, j1, j2 in difflib.SequenceMatcher(None, record_ids, ids).get_opcodes()
+                if tag in ('insert', 'delete'))
+
+            if len(ops) != 2:
+                raise ValueError(_("Re-sequencing can only handle one moved record"))
+
+            source, source_, _1, _2 = ops['delete']
+            if source_ != source+1:
+                raise ValueError(_("Re-sequencing can only move one record at a time"))
+            dest = ops['insert'][0]
+
+            # if a record is moved from back to front we have to include his
+            # old position, and Python slices are half-open intervals
+            #
+            # index 2 -> index 5
+            # 1, 2, 3, 4, 5, 6, 7, 8
+            #       +       ^
+            #       |       |
+            #       +-------+
+            # to resequence:
+            # 1, 2, 4, 5, 3, 6, 7, 8
+            #       +-----+
+            #
+            # index 5 -> index 2
+            # 1, 2, 3, 4, 5, 6, 7, 8
+            #      ^         +
+            #      |         |
+            #      +---------+
+            # to resequence:
+            # 1, 2, 6, 3, 4, 5, 7, 8
+            #       +--------+
+
+            # select only the records (and seqs) between change boundaries for
+            # rewriting
+            if source < dest:
+                s = slice(source, dest)
+                new_seq = seq[s]
+                new_seq.insert(0, new_seq.pop())
+            else:
+                s = slice(dest, source + 1)
+                new_seq = seq[s]
+                new_seq.append(new_seq.pop(0))
+            ids = record_ids[s]
+
+        for i, id in itertools.izip(new_seq, ids):
+            self.write(cr, uid, id, {
+                field: i
+            }, context=context)
+
 # keep this import here, at top it will cause dependency cycle errors
 import expression
 
 
=== added directory 'openerp/tests/addons/test_resequence'
=== added file 'openerp/tests/addons/test_resequence/__init__.py'
--- openerp/tests/addons/test_resequence/__init__.py	1970-01-01 00:00:00 +0000
+++ openerp/tests/addons/test_resequence/__init__.py	2013-07-26 13:08:25 +0000
@@ -0,0 +1,2 @@
+# -*- coding: utf-8 -*-
+import models
 
=== added file 'openerp/tests/addons/test_resequence/__openerp__.py'
--- openerp/tests/addons/test_resequence/__openerp__.py	1970-01-01 00:00:00 +0000
+++ openerp/tests/addons/test_resequence/__openerp__.py	2013-07-26 13:08:25 +0000
@@ -0,0 +1,15 @@
+# -*- coding: utf-8 -*-
+{
+    'name': 'Resequence testing',
+    'version': '0.1',
+    'category': 'Tests',
+    'description': """Testing of resequencing method""",
+    'author': 'OpenERP SA',
+    'maintainer': 'OpenERP SA',
+    'website': 'http://www.openerp.com',
+    'depends': ['base'],
+    'data': ['ir.model.access.csv'],
+    'installable': True,
+    'auto_install': False,
+}
+# vim:expandtab:smartindent:tabstop=4:softtabstop=4:shiftwidth=4:
 
=== added file 'openerp/tests/addons/test_resequence/ir.model.access.csv'
--- openerp/tests/addons/test_resequence/ir.model.access.csv	1970-01-01 00:00:00 +0000
+++ openerp/tests/addons/test_resequence/ir.model.access.csv	2013-07-26 13:08:25 +0000
@@ -0,0 +1,2 @@
+"id","name","model_id:id","group_id:id","perm_read","perm_write","perm_create","perm_unlink"
+access_test_resequence_model,access_test_resequence_model,model_test_resequence_model,,1,1,1,1
 
=== added file 'openerp/tests/addons/test_resequence/models.py'
--- openerp/tests/addons/test_resequence/models.py	1970-01-01 00:00:00 +0000
+++ openerp/tests/addons/test_resequence/models.py	2013-07-26 13:08:25 +0000
@@ -0,0 +1,15 @@
+# -*- coding: utf-8 -*-
+from openerp.osv import orm, fields
+
+class Model(orm.Model):
+    _name = 'test_resequence.model'
+    _order = 'sequence'
+
+    _columns = {
+        'sequence': fields.integer(required=True)
+    }
+
+    def write(self, cr, user, ids, vals, context=None):
+        self.writes += 1
+        return super(Model, self).write(cr, user, ids, vals, context)
+
 
=== added directory 'openerp/tests/addons/test_resequence/tests'
=== added file 'openerp/tests/addons/test_resequence/tests/__init__.py'
--- openerp/tests/addons/test_resequence/tests/__init__.py	1970-01-01 00:00:00 +0000
+++ openerp/tests/addons/test_resequence/tests/__init__.py	2013-07-26 13:08:25 +0000
@@ -0,0 +1,13 @@
+# -*- coding: utf-8 -*-
+
+from . import test_assumptions, test_resequence
+
+fast_suite = [
+]
+
+checks = [
+    test_assumptions,
+    test_resequence,
+]
+
+# vim:expandtab:smartindent:tabstop=4:softtabstop=4:shiftwidth=4:
 
=== added file 'openerp/tests/addons/test_resequence/tests/test_assumptions.py'
--- openerp/tests/addons/test_resequence/tests/test_assumptions.py	1970-01-01 00:00:00 +0000
+++ openerp/tests/addons/test_resequence/tests/test_assumptions.py	2013-07-26 13:08:25 +0000
@@ -0,0 +1,37 @@
+# -*- coding: utf-8 -*-
+import operator
+import random
+
+from openerp.tests import common
+
+class TestAssumptions(common.TransactionCase):
+    def setUp(self):
+        super(TestAssumptions, self).setUp()
+        self.Model = self.registry('test_resequence.model')
+    def create(self, values):
+        return self.Model.create(self.cr, self.uid, values)
+
+    def test_read_order(self):
+        """
+        The re-sequencing method assumes read() always returns its records
+        according to ``_order``, regardless of input ordering.
+        """
+        # generate a bunch of sequence numbers
+        seqs = sorted(set(random.sample(range(100), 20)))
+        # create corresponding records, ids ordering <=> seqs ordering
+        ids = [self.create({'sequence': i}) for i in seqs]
+
+        reverse = list(reversed(ids))
+        ids_reversed = map(
+            operator.itemgetter('id'),
+            self.Model.read(self.cr, self.uid, reverse))
+
+        self.assertEqual(ids_reversed, ids)
+
+        shuffled = list(ids)
+        random.shuffle(shuffled)
+        ids_shuffled = map(
+            operator.itemgetter('id'),
+            self.Model.read(self.cr, self.uid, shuffled))
+
+        self.assertEqual(ids_shuffled, ids)
 
=== added file 'openerp/tests/addons/test_resequence/tests/test_resequence.py'
--- openerp/tests/addons/test_resequence/tests/test_resequence.py	1970-01-01 00:00:00 +0000
+++ openerp/tests/addons/test_resequence/tests/test_resequence.py	2013-07-26 13:08:25 +0000
@@ -0,0 +1,158 @@
+# -*- coding: utf-8 -*-
+from openerp.tests import common
+
+class SequenceCase(common.TransactionCase):
+    def setUp(self):
+        super(SequenceCase, self).setUp()
+        self.Model = self.registry('test_resequence.model')
+        self.Model.writes = 0
+
+    def make(self, sequences):
+        return [
+            self.Model.create(self.cr, self.uid, {'sequence': s})
+            for s in sequences
+        ]
+
+    def assertSeq(self, ids, seqs):
+        """ Asserts that reading ``ids`` yields the same sequence numbers as
+        ``seq``
+        """
+        self.assertEqual(
+            self.Model.read(self.cr, self.uid, ids),
+            map(lambda id, seq: {'id': id, 'sequence': seq},
+                ids,
+                seqs))
+
+def rotate(seq): return seq[-1:] + seq[:-1]
+
+class TestCompleteResequence(SequenceCase):
+    """ Tests resequencing with multiple identical sequence values: should
+    resequence the whole ids list provided
+    """
+
+    def test_noop(self):
+        """ When the input list has not been altered from its original order,
+        nothing should be done
+        """
+        ids = self.make([1, 1])
+
+        self.assertIsNone(self.Model.resequence(self.cr, self.uid, ids))
+
+        self.assertSeq(ids, [1, 1])
+
+    def test_trivial(self):
+        """ If all records have the same sequence number, just resequence
+        everything
+        """
+        ids = self.make([1, 1])
+
+        rids = rotate(ids)
+        self.assertIsNone(self.Model.resequence(self.cr, self.uid, rids))
+
+        self.assertSeq(rids, [1, 2])
+
+        ids = self.make([1, 1, 1, 1])
+
+        rids = rotate(ids)
+        self.assertIsNone(self.Model.resequence(self.cr, self.uid, rids))
+
+        self.assertSeq(rids, [1, 2, 3, 4])
+
+    def test_start(self):
+        """ Should use the seq of the first record as its starting point
+        """
+        ids = self.make([45, 45])
+
+        rids = rotate(ids)
+        self.assertIsNone(self.Model.resequence(self.cr, self.uid, rids))
+
+        self.assertSeq(rids, [45, 46])
+
+    def test_reuse_existing(self):
+        """ Should reuse all existing unique sequence numbers before starting
+        its own counter
+        """
+        ids = self.make([5, 5, 8, 9, 9, 9, 9, 15, 16, 17, 42])
+
+        rids = rotate(ids)
+        self.assertIsNone(self.Model.resequence(self.cr, self.uid, rids))
+
+        self.assertSeq(rids, [5, 8, 9, 15, 16, 17, 42, 43, 44, 45, 46])
+        self.assertEqual(self.Model.writes, len(ids))
+
+    def test_move(self):
+        """ Technically could do a partial reseq since there are no duplicates
+        in the move range of the record
+        """
+        #                            |  ->  |
+        ids = self.make([1, 2, 2, 2, 3, 5, 8, 9, 9])
+
+        rids = list(ids)
+        rids.insert(6, rids.pop(4))
+        self.assertIsNone(self.Model.resequence(self.cr, self.uid, rids))
+
+        self.assertSeq(rids, [1, 2, 3, 5, 8, 9, 10, 11, 12])
+        self.assertEqual(self.Model.writes, len(ids))
+
+    def test_move_duplicate_straddling(self):
+        """ Complication on previous case: duplicate seq numbers just on the
+        boundary of moved object. Would it be possible to do partial reseqs
+        here or is there no choice but to do a full reseq?
+        """
+        #                            |  ->  |
+        ids = self.make([1, 2, 2, 3, 5, 8, 9, 9, 9])
+
+        rids = list(ids)
+        rids.insert(6, rids.pop(4))
+        self.assertIsNone(self.Model.resequence(self.cr, self.uid, rids))
+
+        self.assertSeq(rids, [1, 2, 3, 5, 8, 9, 10, 11, 12])
+        self.assertEqual(self.Model.writes, len(ids))
+
+        #                            |  ->  |
+        ids = self.make([1, 1, 1, 2, 2, 3, 5, 8, 9])
+
+        rids = list(ids)
+        rids.insert(6, rids.pop(4))
+        self.assertIsNone(self.Model.resequence(self.cr, self.uid, rids))
+
+        self.assertSeq(rids, [1, 2, 3, 5, 8, 9, 10, 11, 12])
+
+class TestPartialResequence(SequenceCase):
+    """ When the sub-sequence comprising the original and final indices of a
+    moved record only holds unique sequence ids, no need to write new ids from
+    scratch, can just rotate the existing one on the sub-sequence.
+    """
+    def test_move_down(self):
+        #            |        ->       |
+        seq = [2, 4, 5, 12, 13, 24, 26, 31, 32, 34]
+        ids = self.make(seq)
+
+        rids = list(ids)
+        rids.insert(6, rids.pop(2))
+        self.assertIsNone(self.Model.resequence(self.cr, self.uid, rids))
+
+        self.assertSeq(rids, seq)
+        self.assertEqual(self.Model.writes, 5)
+
+    def test_move_up(self):
+        seq = [2, 4, 5, 12, 13, 24, 26, 31, 32, 34]
+        ids = self.make(seq)
+
+        rids = list(ids)
+        rids.insert(5, rids.pop(8))
+        self.assertIsNone(self.Model.resequence(self.cr, self.uid, rids))
+
+        self.assertSeq(rids, seq)
+        self.assertEqual(self.Model.writes, 4)
+
+    def test_swap(self):
+        seq = [2, 5, 8, 12]
+        ids = self.make(seq)
+
+        rids = list(ids)
+        rids.insert(1, rids.pop(2))
+        self.assertIsNone(self.Model.resequence(self.cr, self.uid, rids))
+
+        self.assertSeq(rids, seq)
+        self.assertEqual(self.Model.writes, 2)
 
=== modified file 'openerp/tests/common.py'
--- openerp/tests/common.py	2013-01-31 13:10:51 +0000
+++ openerp/tests/common.py	2013-07-26 13:08:25 +0000
@@ -91,12 +91,13 @@
     def setUp(self):
         # Store cr and uid in class variables, to allow ref() and browse_ref to be BaseCase @classmethods
         # and still access them
-        TransactionCase.cr = self.cursor()
-        TransactionCase.uid = openerp.SUPERUSER_ID
+        type(self).cr = self.cursor()
+        type(self).uid = openerp.SUPERUSER_ID
 
     def tearDown(self):
         self.cr.rollback()
         self.cr.close()
+        del type(self).cr
 
 
 class SingleTransactionCase(BaseCase):
@@ -114,6 +115,7 @@
     def tearDownClass(cls):
         cls.cr.rollback()
         cls.cr.close()
+        del cls.cr
 
 
 class RpcCase(unittest2.TestCase):