[REF] models: refactor code to update parent_left/parent_right

Put the code to update the MPTT in specific methods, and reduce the number of
queries being made (from 5-6 queries to 2-3 queries).  Add test on MPTT to
validate the refactoring.

5 files changed, 277 insertions, 112 deletions

diff --git a/odoo/addons/base/tests/test_base.py b/odoo/addons/base/tests/test_base.py
index e39fb7d5b4c..b6bdfc33f85 100644
--- a/odoo/addons/base/tests/test_base.py
+++ b/odoo/addons/base/tests/test_base.py
@@ -443,6 +443,7 @@ class TestParentStore(TransactionCase):
         super(TestParentStore, self).setUp()
         # pretend the pool has finished loading to avoid deferring parent_store computation
         self.patch(self.registry, '_init', False)
+        self.registry.do_parent_store(self.cr)
 
         # force res_partner_category.copy() to copy children
         category = self.env['res.partner.category']
diff --git a/odoo/addons/test_new_api/models.py b/odoo/addons/test_new_api/models.py
index 7298bfbe01a..14712030dcc 100644
--- a/odoo/addons/test_new_api/models.py
+++ b/odoo/addons/test_new_api/models.py
@@ -10,10 +10,16 @@ from odoo.tools import pycompat
 
 class Category(models.Model):
     _name = 'test_new_api.category'
+    _order = 'name'
+    _parent_store = True
+    _parent_name = 'parent'
+    _parent_order = 'name'
 
     name = fields.Char(required=True)
     color = fields.Integer('Color Index')
-    parent = fields.Many2one('test_new_api.category')
+    parent = fields.Many2one('test_new_api.category', ondelete='cascade')
+    parent_left = fields.Integer("Left Parent", index=True)
+    parent_right = fields.Integer("Right Parent", index=True)
     root_categ = fields.Many2one(_name, compute='_compute_root_categ')
     display_name = fields.Char(compute='_compute_display_name', inverse='_inverse_display_name')
     dummy = fields.Char(store=False)
diff --git a/odoo/addons/test_new_api/tests/test_new_fields.py b/odoo/addons/test_new_api/tests/test_new_fields.py
index f8e60e23b6b..21d24d42724 100644
--- a/odoo/addons/test_new_api/tests/test_new_fields.py
+++ b/odoo/addons/test_new_api/tests/test_new_fields.py
@@ -3,7 +3,7 @@
 #
 from datetime import date, datetime
 
-from odoo.exceptions import AccessError, except_orm
+from odoo.exceptions import AccessError, UserError, except_orm
 from odoo.tests import common
 from odoo.tools import mute_logger, float_repr, pycompat
 
@@ -937,3 +937,123 @@ class TestMagicFields(common.TransactionCase):
         record = self.env['test_new_api.discussion'].create({'name': 'Booba'})
         self.assertEqual(record.create_uid, self.env.user)
         self.assertEqual(record.write_uid, self.env.user)
+
+
+class Tree(object):
+    def __init__(self, node, *children):
+        self.node = node
+        self.children = children
+
+    def __str__(self):
+        return "%s(%s, %s)" % (self.node.name, self.node.parent_left, self.node.parent_right)
+
+
+class TestParentStore(common.TransactionCase):
+
+    def setUp(self):
+        super(TestParentStore, self).setUp()
+        # pretend the pool has finished loading to avoid deferring parent_store
+        # computation
+        self.patch(self.registry, '_init', False)
+        self.registry.do_parent_store(self.cr)
+
+    def assertTree(self, tree):
+        self.assertLess(tree.node.parent_left, tree.node.parent_right,
+                        "incorrect node %s" % tree)
+        for child in tree.children:
+            self.assertLess(tree.node.parent_left, child.node.parent_left,
+                            "incorrect parent %s - child %s" % (tree, child))
+            self.assertLess(child.node.parent_right, tree.node.parent_right,
+                            "incorrect parent %s - child %s" % (tree, child))
+        self.assertTrees(*tree.children)
+
+    def assertTrees(self, *trees):
+        for tree in trees:
+            self.assertTree(tree)
+        for tree1, tree2 in pycompat.izip(trees, trees[1:]):
+            self.assertLess(tree1.node.parent_right, tree2.node.parent_left,
+                            "wrong node order: %s < %s" % (tree1, tree2))
+
+    def test_parent_store(self):
+        """ Test parent_left/parent_right computation. """
+        Category = self.env['test_new_api.category']
+
+        def descendants(recs):
+            return Category.search([('id', 'child_of', recs.ids)])
+
+        def ascendants(recs):
+            return Category.search([('id', 'parent_of', recs.ids)])
+
+        # create root nodes
+        c = Category.create({'name': 'c'})
+        a = Category.create({'name': 'a'})
+        b = Category.create({'name': 'b'})
+        self.assertTrees(Tree(a), Tree(b), Tree(c))
+
+        # create nodes d, e, f under b
+        f = Category.create({'name': 'f', 'parent': b.id})
+        d = Category.create({'name': 'd', 'parent': b.id})
+        e = Category.create({'name': 'e', 'parent': b.id})
+        self.assertTrees(Tree(a), Tree(b, Tree(d), Tree(e), Tree(f)), Tree(c))
+        self.assertEqual(descendants(a), a)
+        self.assertEqual(descendants(b), b + d + e + f)
+        self.assertEqual(descendants(c), c)
+        self.assertEqual(descendants(d), d)
+        self.assertEqual(descendants(e), e)
+        self.assertEqual(descendants(f), f)
+        self.assertEqual(ascendants(a), a)
+        self.assertEqual(ascendants(b), b)
+        self.assertEqual(ascendants(c), c)
+        self.assertEqual(ascendants(d), b + d)
+        self.assertEqual(ascendants(e), b + e)
+        self.assertEqual(ascendants(f), b + f)
+
+        # move d, f under c
+        (f + d).write({'parent': c.id})
+        self.assertTrees(Tree(a), Tree(b, Tree(e)), Tree(c, Tree(d), Tree(f)))
+        self.assertEqual(descendants(a), a)
+        self.assertEqual(descendants(b), b + e)
+        self.assertEqual(descendants(c), c + d + f)
+        self.assertEqual(descendants(d), d)
+        self.assertEqual(descendants(e), e)
+        self.assertEqual(descendants(f), f)
+        self.assertEqual(ascendants(a), a)
+        self.assertEqual(ascendants(b), b)
+        self.assertEqual(ascendants(c), c)
+        self.assertEqual(ascendants(d), c + d)
+        self.assertEqual(ascendants(e), b + e)
+        self.assertEqual(ascendants(f), c + f)
+
+        # move b, c under a
+        (b + c).write({'parent': a.id})
+        self.assertTrees(Tree(a, Tree(b, Tree(e)), Tree(c, Tree(d), Tree(f))))
+        self.assertEqual(descendants(a), a + b + c + d + e + f)
+        self.assertEqual(descendants(b), b + e)
+        self.assertEqual(descendants(c), c + d + f)
+        self.assertEqual(descendants(d), d)
+        self.assertEqual(descendants(e), e)
+        self.assertEqual(descendants(f), f)
+        self.assertEqual(ascendants(a), a)
+        self.assertEqual(ascendants(b), a + b)
+        self.assertEqual(ascendants(c), a + c)
+        self.assertEqual(ascendants(d), a + c + d)
+        self.assertEqual(ascendants(e), a + b + e)
+        self.assertEqual(ascendants(f), a + c + f)
+
+        # remove node d
+        d.unlink()
+        self.assertTrees(Tree(a, Tree(b, Tree(e)), Tree(c, Tree(f))))
+        self.assertEqual(descendants(a), a + b + c + e + f)
+        self.assertEqual(descendants(b), b + e)
+        self.assertEqual(descendants(c), c + f)
+        self.assertEqual(descendants(e), e)
+        self.assertEqual(descendants(f), f)
+        self.assertEqual(ascendants(a), a)
+        self.assertEqual(ascendants(b), a + b)
+        self.assertEqual(ascendants(c), a + c)
+        self.assertEqual(ascendants(e), a + b + e)
+        self.assertEqual(ascendants(f), a + c + f)
+
+        # not cycle should occur
+        with self.assertRaises(UserError):
+            a.parent = e
diff --git a/odoo/models.py b/odoo/models.py
index 6b7a48328b0..0af021810cc 100644
--- a/odoo/models.py
+++ b/odoo/models.py
@@ -3044,24 +3044,7 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
         cr = self._cr
 
         # determine records that require updating parent_left, parent_right
-        parents_changed = []
-        if self._parent_store and (self._parent_name in vals) and \
-                not self._context.get('defer_parent_store_computation'):
-            # The parent_left/right computation may take up to 5 seconds. No
-            # need to recompute the values if the parent is the same.
-            #
-            # Note: to respect parent_order, nodes must be processed in
-            # order, so ``parents_changed`` must be ordered properly.
-            parent_val = vals[self._parent_name]
-            if parent_val:
-                query = "SELECT id FROM %s WHERE id IN %%s AND (%s != %%s OR %s IS NULL) ORDER BY %s" % \
-                                (self._table, self._parent_name, self._parent_name, self._parent_order)
-                cr.execute(query, (tuple(self.ids), parent_val))
-            else:
-                query = "SELECT id FROM %s WHERE id IN %%s AND (%s IS NOT NULL) ORDER BY %s" % \
-                                (self._table, self._parent_name, self._parent_order)
-                cr.execute(query, (tuple(self.ids),))
-            parents_changed = [x[0] for x in cr.fetchall()]
+        parent_records = self._parent_store_update_prepare(vals)
 
         # determine SQL values
         columns = []                    # list of (column_name, format, value)
@@ -3149,63 +3132,9 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
         # check Python constraints
         self._validate_fields(vals)
 
-        # TODO: use _order to set dest at the right position and not first node of parent
-        # We can't defer parent_store computation because the stored function
-        # fields that are computer may refer (directly or indirectly) to
-        # parent_left/right (via a child_of domain)
-        if parents_changed:
-            if self.pool._init:
-                self.pool._init_parent[self._name] = True
-            else:
-                parent_val = vals[self._parent_name]
-                if parent_val:
-                    clause, params = '%s=%%s' % self._parent_name, (parent_val,)
-                else:
-                    clause, params = '%s IS NULL' % self._parent_name, ()
-
-                for id in parents_changed:
-                    # determine old parent_left, parent_right of current record
-                    cr.execute('SELECT parent_left, parent_right FROM %s WHERE id=%%s' % self._table, (id,))
-                    pleft0, pright0 = cr.fetchone()
-                    width = pright0 - pleft0 + 1
-
-                    # determine new parent_left of current record; it comes
-                    # right after the parent_right of its closest left sibling
-                    # (this CANNOT be fetched outside the loop, as it needs to
-                    # be refreshed after each update, in case several nodes are
-                    # sequentially inserted one next to the other)
-                    pleft1 = None
-                    cr.execute('SELECT id, parent_right FROM %s WHERE %s ORDER BY %s' % \
-                               (self._table, clause, self._parent_order), params)
-                    for (sibling_id, sibling_parent_right) in cr.fetchall():
-                        if sibling_id == id:
-                            break
-                        pleft1 = (sibling_parent_right or 0) + 1
-                    if not pleft1:
-                        # the current record is the first node of the parent
-                        if not parent_val:
-                            pleft1 = 0          # the first node starts at 0
-                        else:
-                            cr.execute('SELECT parent_left FROM %s WHERE id=%%s' % self._table, (parent_val,))
-                            pleft1 = cr.fetchone()[0] + 1
-
-                    if pleft0 < pleft1 <= pright0:
-                        raise UserError(_('Recursivity Detected.'))
-
-                    # make some room for parent_left and parent_right at the new position
-                    cr.execute('UPDATE %s SET parent_left=parent_left+%%s WHERE %%s<=parent_left' % self._table, (width, pleft1))
-                    cr.execute('UPDATE %s SET parent_right=parent_right+%%s WHERE %%s<=parent_right' % self._table, (width, pleft1))
-                    # slide the subtree of the current record to its new position
-                    if pleft0 < pleft1:
-                        cr.execute('''UPDATE %s SET parent_left=parent_left+%%s, parent_right=parent_right+%%s
-                                      WHERE %%s<=parent_left AND parent_left<%%s''' % self._table,
-                                   (pleft1 - pleft0, pleft1 - pleft0, pleft0, pright0))
-                    else:
-                        cr.execute('''UPDATE %s SET parent_left=parent_left-%%s, parent_right=parent_right-%%s
-                                      WHERE %%s<=parent_left AND parent_left<%%s''' % self._table,
-                                   (pleft0 - pleft1 + width, pleft0 - pleft1 + width, pleft0 + width, pright0 + width))
-
-                self.invalidate_cache(['parent_left', 'parent_right'])
+        # update parent_left/parent_right
+        if parent_records:
+            parent_records._parent_store_update(vals)
 
         return True
 
@@ -3296,12 +3225,16 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
     @api.model
     def _create(self, vals):
         self = self.browse()
+        cr = self.env.cr
 
         # set boolean fields to False by default (to make search more powerful)
         for name, field in self._fields.items():
             if field.type == 'boolean' and field.store:
                 vals.setdefault(name, False)
 
+        # prepare the update of parent_left, parent_right
+        parent_store = self._parent_store_create_prepare(vals)
+
         # determine SQL values
         columns = []                    # list of (column_name, format, value)
         other_fields = []               # list of non-column fields
@@ -3332,7 +3265,6 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
             columns.append(('write_date', '%s', AsIs("(now() at time zone 'UTC')")))
 
         # insert a row for this record
-        cr = self._cr
         query = """INSERT INTO "%s" (%s) VALUES(%s) RETURNING id""" % (
                 self._table,
                 ', '.join('"%s"' % column[0] for column in columns),
@@ -3344,39 +3276,8 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
         self = self.browse(cr.fetchone()[0])
 
         # update parent_left, parent_right
-        if self._parent_store and not self._context.get('defer_parent_store_computation'):
-            if self.pool._init:
-                self.pool._init_parent[self._name] = True
-            else:
-                parent_val = vals.get(self._parent_name)
-                if parent_val:
-                    # determine parent_left: it comes right after the
-                    # parent_right of its closest left sibling
-                    pleft = None
-                    cr.execute("SELECT parent_right FROM %s WHERE %s=%%s ORDER BY %s" % \
-                                    (self._table, self._parent_name, self._parent_order),
-                               (parent_val,))
-                    for (pright,) in cr.fetchall():
-                        if not pright:
-                            break
-                        pleft = pright + 1
-                    if not pleft:
-                        # this is the leftmost child of its parent
-                        cr.execute("SELECT parent_left FROM %s WHERE id=%%s" % self._table, (parent_val,))
-                        pleft = cr.fetchone()[0] + 1
-                else:
-                    # determine parent_left: it comes after all top-level parent_right
-                    cr.execute("SELECT MAX(parent_right) FROM %s" % self._table)
-                    pleft = (cr.fetchone()[0] or 0) + 1
-
-                # make some room for the new node, and insert it in the MPTT
-                cr.execute("UPDATE %s SET parent_left=parent_left+2 WHERE parent_left>=%%s" % self._table,
-                           (pleft,))
-                cr.execute("UPDATE %s SET parent_right=parent_right+2 WHERE parent_right>=%%s" % self._table,
-                           (pleft,))
-                cr.execute("UPDATE %s SET parent_left=%%s, parent_right=%%s WHERE id=%%s" % self._table,
-                           (pleft, pleft + 1, record_id))
-                self.invalidate_cache(['parent_left', 'parent_right'])
+        if parent_store:
+            self._parent_store_update(vals)
 
         with self.env.protecting(protected_fields, self):
             # mark fields to recompute; do this before setting other fields,
@@ -3417,6 +3318,143 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
 
         return self
 
+    def _parent_store_create_prepare(self, vals):
+        """ Prepare the creation of a record, and return whether its
+            parent_left/parent_right fields must be updated after creation.
+        """
+        if not self._parent_store or self._context.get('defer_parent_store_computation'):
+            return False
+
+        if self.pool._init:
+            self.pool._init_parent.add(self._name)
+            return False
+
+        # temporarily put the node at the top-level rightmost position
+        query = "SELECT COALESCE(MAX(parent_right) + 1, 0) FROM {}"
+        self._cr.execute(query.format(self._table))
+        parent_left = self._cr.fetchone()[0]
+        vals.setdefault(self._parent_name, False)
+        vals['parent_left'] = parent_left
+        vals['parent_right'] = parent_left + 1
+        return True
+
+    def _parent_store_update_prepare(self, vals):
+        """ Return the records in ``self`` that must update their parent_left,
+            parent_right fields, in their sibling order. This must be called
+            before updating the parent field.
+        """
+        if not self._parent_store or self._parent_name not in vals or \
+                self._context.get('defer_parent_store_computation'):
+            return self.browse()
+
+        if self.pool._init:
+            self.pool._init_parent.add(self._name)
+            return self.browse()
+
+        # The parent_left/right computation may take up to 5 seconds. No need to
+        # recompute the values if the parent is the same.
+        #
+        # Note: to respect parent_order, nodes must be processed in order, so
+        # the result must be ordered properly.
+        parent_val = vals[self._parent_name]
+        if parent_val:
+            query = """ SELECT id FROM {0}
+                        WHERE id IN %s AND ({1} != %s OR {1} IS NULL)
+                        ORDER BY {2} """
+            params = [tuple(self.ids), parent_val]
+        else:
+            query = """ SELECT id FROM {0}
+                        WHERE id IN %s AND {1} IS NOT NULL
+                        ORDER BY {2} """
+            params = [tuple(self.ids)]
+        query = query.format(self._table, self._parent_name, self._parent_order)
+        self._cr.execute(query, params)
+        return self.browse([row[0] for row in self._cr.fetchall()])
+
+    def _parent_store_update(self, vals):
+        """ Update the parent_left/parent_right fields of ``self``. """
+        cr = self.env.cr
+        parent_val = vals[self._parent_name]
+        if parent_val:
+            clause, params = '{}=%s'.format(self._parent_name), [parent_val]
+        else:
+            clause, params = '{} IS NULL'.format(self._parent_name), []
+
+        modified_ids = set()
+        for record in self:
+            # retrieve record's siblings data (this CANNOT be fetched
+            # outside the loop, as it needs to be refreshed after each
+            # update, in case several nodes are sequentially inserted one
+            # next to the other)
+            query = """ SELECT id, parent_left, parent_right FROM {}
+                        WHERE {} ORDER BY {} """
+            cr.execute(query.format(self._table, clause, self._parent_order), params)
+            siblings = cr.fetchall()
+
+            # determine record's position among its siblings
+            index = next(pos
+                         for pos, data in enumerate(siblings)
+                         if data[0] == record.id)
+
+            # retrieve record's current data
+            pleft0, pright0 = siblings[index][1:]
+            width = pright0 - pleft0 + 1
+
+            # determine new parent_left of current record
+            if index:
+                # record comes right after its closest left sibling
+                pleft1 = (siblings[index - 1][2] or 0) + 1
+            else:
+                # record is the first node of its parent
+                if not parent_val:
+                    pleft1 = 0          # the first node starts at 0
+                else:
+                    query = "SELECT parent_left FROM {} WHERE id=%s"
+                    cr.execute(query.format(self._table), [parent_val])
+                    pleft1 = cr.fetchone()[0] + 1
+
+            if pleft0 == pleft1:
+                continue
+
+            if pleft0 < pleft1 <= pright0:
+                raise UserError(_('Recursivity Detected.'))
+
+            # We have to slide values in the interval [x,x+a+b) in order to
+            # swap the subsets in [x,x+a) and [x+a,x+a+b), respectively.
+            #
+            #             x          x+a         x+b        x+a+b
+            #             |-----------|-----------|-----------|
+            #     before: A A A A A A B B B B B B B B B B B B
+            #      after: B B B B B B B B B B B B A A A A A A
+            #
+            query1 = """
+                UPDATE {}
+                SET parent_left = parent_left + (CASE
+                        WHEN parent_left<%(x)s THEN 0
+                        WHEN parent_left<%(x)s+%(a)s THEN %(b)s
+                        WHEN parent_left<%(x)s+%(a)s+%(b)s THEN -%(a)s
+                        ELSE 0 END),
+                    parent_right = parent_right + (CASE
+                        WHEN parent_right<%(x)s THEN 0
+                        WHEN parent_right<%(x)s+%(a)s THEN %(b)s
+                        WHEN parent_right<%(x)s+%(a)s+%(b)s THEN -%(a)s
+                        ELSE 0 END)
+                WHERE (parent_left BETWEEN %(x)s AND %(x)s+%(a)s+%(b)s-1)
+                   OR (parent_right BETWEEN %(x)s AND %(x)s+%(a)s+%(b)s-1)
+                RETURNING id
+            """
+            if pleft0 < pleft1:
+                # x = pleft0, a = width, x+a+b = pleft1
+                params1 = dict(x=pleft0, a=width, b=pleft1 - pleft0 - width)
+            else:
+                # x = pleft1, x+a = pleft0, b = width
+                params1 = dict(x=pleft1, a=pleft0 - pleft1, b=width)
+
+            cr.execute(query1.format(self._table), params1)
+            modified_ids.update(row[0] for row in cr.fetchall())
+
+        self.browse(modified_ids).modified(['parent_left', 'parent_right'])
+
     # TODO: ameliorer avec NULL
     @api.model
     def _where_calc(self, domain, active_test=True):
diff --git a/odoo/modules/registry.py b/odoo/modules/registry.py
index 5c1c5111cf0..1d6dbe69726 100644
--- a/odoo/modules/registry.py
+++ b/odoo/modules/registry.py
@@ -111,7 +111,7 @@ class Registry(Mapping):
         self.models = {}    # model name/model instance mapping
         self._sql_error = {}
         self._init = True
-        self._init_parent = {}
+        self._init_parent = set()
         self._assertion_report = assertion_report.assertion_report()
         self._fields_by_model = None
         self._post_init_queue = deque()