[FIX] models: use transitive triggers instead of recursion

On average, this reduces the total time spent in method `modified` by
half (times measured on invoice creation and post).

6 files changed, 102 insertions, 87 deletions

diff --git a/addons/sale_coupon/models/sale_order.py b/addons/sale_coupon/models/sale_order.py
index e1249c86abc..899f203ba0a 100644
--- a/addons/sale_coupon/models/sale_order.py
+++ b/addons/sale_coupon/models/sale_order.py
@@ -433,8 +433,8 @@ class SaleOrderLine(models.Model):
     # Another possibility is to add on product.product a one2many to sale.order.line 'order_line_ids',
     # and then add the depends @api.depends('discount_line_product_id.order_line_ids'),
     # but I am not sure this will as efficient as the below.
-    def modified(self, fnames, modified=None, create=False):
-        super(SaleOrderLine, self).modified(fnames, modified=modified)
+    def modified(self, fnames, create=False):
+        super(SaleOrderLine, self).modified(fnames, create)
         if 'product_id' in fnames:
             Program = self.env['sale.coupon.program']
             field_order_count = Program._fields['order_count']
diff --git a/odoo/addons/test_new_api/models.py b/odoo/addons/test_new_api/models.py
index d67f6749d55..79026a5cc13 100644
--- a/odoo/addons/test_new_api/models.py
+++ b/odoo/addons/test_new_api/models.py
@@ -608,7 +608,7 @@ class Attachment(models.Model):
             rec.name = self.env[rec.res_model].browse(rec.res_id).display_name
 
     # DLE P55: `test_cache_invalidation`
-    def modified(self, fnames, modified=None, create=False):
+    def modified(self, fnames, create=False):
         if not self:
             return
         comodel = self.env[self.res_model]
@@ -617,11 +617,7 @@ class Attachment(models.Model):
             record = comodel.browse(self.res_id)
             self.env.cache.invalidate([(field, record._ids)])
             record.modified(['attachment_ids'])
-            if modified is None:
-                modified = {field: record}
-            else:
-                modified[field] = modified.get(field, record) | record
-        return super(Attachment, self).modified(fnames, modified=modified)
+        return super(Attachment, self).modified(fnames, create)
 
 
 class AttachmentHost(models.Model):
diff --git a/odoo/api.py b/odoo/api.py
index efd1a748d3f..88cc4c9490c 100644
--- a/odoo/api.py
+++ b/odoo/api.py
@@ -636,14 +636,16 @@ class Environment(Mapping):
         """ Return whether ``field`` must be computed on ``record``. """
         return record.id in self.all.tocompute.get(field, ())
 
+    def not_to_compute(self, field, records):
+        """ Return the subset of ``records`` for which ``field`` must not be computed. """
+        ids = self.all.tocompute.get(field, ())
+        return records.browse(id_ for id_ in records._ids if id_ not in ids)
+
     def add_to_compute(self, field, records):
-        """ Mark ``field`` to be computed on ``records``, return newly added records. """
+        """ Mark ``field`` to be computed on ``records``. """
         if not records:
             return records
-        ids = self.all.tocompute[field]
-        added_ids = [id_ for id_ in records._ids if id_ not in ids]
-        ids.update(added_ids)
-        return records.browse(added_ids)
+        self.all.tocompute[field].update(records._ids)
 
     def remove_to_compute(self, field, records):
         """ Mark ``field`` as computed on ``records``. """
diff --git a/odoo/fields.py b/odoo/fields.py
index d658ad5782c..995a586739f 100644
--- a/odoo/fields.py
+++ b/odoo/fields.py
@@ -692,64 +692,33 @@ class Field(MetaField('DummyField', (object,), {})):
     #
     # Setup of field triggers
     #
-    # The triggers of a field F is a tree that contains the fields that depend
-    # on F, together with the fields to inverse to find out which records to
-    # recompute.
-    #
-    # For instance, assume that G depends on F, H depends on X.F, I depends on
-    # W.X.F, and J depends on Y.F. The triggers of F will be the tree:
-    #
-    #                                   [G]
-    #                                 X/   \Y
-    #                               [H]     [J]
-    #                             W/
-    #                           [I]
-    #
-    # This tree provides perfect support for the trigger mechanism:
-    # when F is # modified on records,
-    #  - mark G to recompute on records,
-    #  - mark H to recompute on inverse(X, records),
-    #  - mark I to recompute on inverse(W, inverse(X, records)),
-    #  - mark J to recompute on inverse(Y, records).
-
-    def setup_triggers(self, model):
-        def add_trigger(field, path):
-            """ add a trigger on field to recompute self """
-            field_model = model.env[field.model_name]
-            # trigger computations depending on one2many fields only at creation
-            nodes = [field_model._field_triggers_create.setdefault(field, {})]
-            if (field.type != 'one2many') or not field_model._field_inverses[field]:
-                nodes.append(field_model._field_triggers.setdefault(field, {}))
-            for node in nodes:
-                for f in reversed(path):
-                    node = node.setdefault(f, {})
-                n = node.setdefault(None, [])
-                if self not in n: n.append(self)
 
+    def resolve_depends(self, model):
+        """ Return the dependencies of `self` as a collection of field tuples. """
         for dotnames in self.depends:
+            field_seq = []
             field_model = model
-            path = []                   # fields from model to field_model
-            for fname in dotnames.split('.'):
-                field = field_model._fields[fname]
-
+            for index, fname in enumerate(dotnames.split('.')):
                 if model._transient and not field_model._transient:
                     # modifying fields on regular models should not trigger
                     # recomputations of fields on transient models
                     break
 
-                # Do not make self trigger itself
-                # e.g. `fields.One2many('stock.move.line', 'move_id', domain=[('product_qty', '=', 0.0)])`
-                # will have 'move_line_nosuggest_ids.product_qty' as a dependency
-                if (field is not self) or path:
-                    add_trigger(field, path)
-
-                if (field is self) and path:
+                field = field_model._fields[fname]
+                if field is self and index:
                     self.recursive = True
 
-                path.append(field)
+                field_seq.append(field)
+
+                # do not make self trigger itself: for instance, a one2many
+                # field line_ids with domain [('foo', ...)] will have
+                # 'line_ids.foo' as a dependency
+                if not (field is self and not index):
+                    yield tuple(field_seq)
+
                 if field.type in ('one2many', 'many2many'):
                     for inv_field in field_model._field_inverses[field]:
-                        add_trigger(inv_field, path)
+                        yield tuple(field_seq) + (inv_field,)
 
                 field_model = model.env.get(field.comodel_name)
 
diff --git a/odoo/models.py b/odoo/models.py
index 2e81d5b8b7b..d568e79d5e2 100644
--- a/odoo/models.py
+++ b/odoo/models.py
@@ -2587,8 +2587,6 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
         # 4. initialize more field metadata
         cls._field_computed = {}            # fields computed with the same method
         cls._field_inverses = Collector()   # inverse fields for related fields
-        cls._field_triggers = {}            # {depfield: {depfield: {...}, None: [compute_fields]}}
-        cls._field_triggers_create = {}     # {depfield: {depfield: {...}, None: [compute_fields]}}
 
         cls._setup_done = True
 
@@ -2633,13 +2631,27 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
         """ Setup recomputation triggers, and complete the model setup. """
         cls = type(self)
 
-        if isinstance(self, Model):
-            # set up field triggers (on database-persisted models only)
-            for field in cls._fields.values():
-                # dependencies of custom fields may not exist; ignore that case
-                exceptions = (Exception,) if field.manual else ()
-                with tools.ignore(*exceptions):
-                    field.setup_triggers(self)
+        # The triggers of a field F is a tree that contains the fields that
+        # depend on F, together with the fields to inverse to find out which
+        # records to recompute.
+        #
+        # For instance, assume that G depends on F, H depends on X.F, I depends
+        # on W.X.F, and J depends on Y.F. The triggers of F will be the tree:
+        #
+        #                              [G]
+        #                            X/   \Y
+        #                          [H]     [J]
+        #                        W/
+        #                      [I]
+        #
+        # This tree provides perfect support for the trigger mechanism:
+        # when F is # modified on records,
+        #  - mark G to recompute on records,
+        #  - mark H to recompute on inverse(X, records),
+        #  - mark I to recompute on inverse(W, inverse(X, records)),
+        #  - mark J to recompute on inverse(Y, records).
+        cls._field_triggers = cls.pool.field_triggers
+        cls._field_triggers_create = cls.pool.field_triggers_create
 
         # register constraints and onchange methods
         cls._init_constraints_onchanges()
@@ -5470,14 +5482,13 @@ Record ids: %(records)s
                [(invf, None) for f in fields for invf in self._field_inverses[f]]
         self.env.cache.invalidate(spec)
 
-    def modified(self, fnames, modified=None, create=False):
+    def modified(self, fnames, create=False):
         """ Notify that fields have been modified on ``self``. This invalidates
             the cache, and prepares the recomputation of stored function fields
             (new-style fields only).
 
             :param fnames: iterable of field names that have been modified on
                 records ``self``
-            :param modified: don't use this
             :param create: whether modified is called in the context of record creation
         """
         if not self or not fnames:
@@ -5493,38 +5504,32 @@ Record ids: %(records)s
                 if node:
                     trigger_tree_merge(tree, node)
         if tree:
-            self.sudo()._modified_triggers(tree, modified=modified)
+            self.sudo()._modified_triggers(tree)
 
-    def _modified_triggers(self, tree, modified=None):
+    def _modified_triggers(self, tree):
         """ Process a tree of field triggers on ``self``. """
         if not self:
             return
         for key, val in tree.items():
             if key is None:
                 # val is a list of fields to mark as todo
-                todo = defaultdict(list)
-                modified = modified or {}
                 for field in val:
                     records = self - self.env.protected(field)
-                    if modified and field in modified:
-                        records -= modified[field]
                     if not records:
                         continue
                     # Dont force the recomputation of compute fields which are
                     # not stored as this is not really necessary.
                     if field.compute and field.store:
+                        if field.recursive:
+                            added = self.env.not_to_compute(field, records)
                         self.env.add_to_compute(field, records)
                     else:
+                        if field.recursive:
+                            added = self & self.env.cache.get_records(self, field)
                         self.env.cache.invalidate([(field, records._ids)])
                     # recursively trigger recomputation of field's dependents
-                    todo[records].append(field.name)
-                for records, fieldnames in todo.items():
-                    for fname in fieldnames:
-                        if records._fields[fname] in modified:
-                            modified[records._fields[fname]] += records
-                        else:
-                            modified[records._fields[fname]] = records
-                    records.modified(fieldnames, modified=modified)
+                    if field.recursive:
+                        added.modified([field.name])
             else:
                 # val is another tree of dependencies
                 model = self.env[key.model_name]
@@ -5539,9 +5544,9 @@ Record ids: %(records)s
                             records = model.browse(rec_ids)
                         else:
                             try:
-                                records = self.mapped(invf.name)
+                                records = self[invf.name]
                             except MissingError:
-                                records = self.exists().mapped(invf.name)
+                                records = self.exists()[invf.name]
 
                         # TODO: find a better fix
                         if key.model_name == records._name:
@@ -5555,7 +5560,7 @@ Record ids: %(records)s
                     if new_records:
                         cache_records = self.env.cache.get_records(model, key)
                         records |= cache_records.filtered(lambda r: set(r[key.name]._ids) & set(self._ids))
-                records._modified_triggers(val, modified=modified)
+                records._modified_triggers(val)
 
     @api.model
     def recompute(self, fnames=None, records=None):
diff --git a/odoo/modules/registry.py b/odoo/modules/registry.py
index c3930d3f425..8a70b8d7582 100644
--- a/odoo/modules/registry.py
+++ b/odoo/modules/registry.py
@@ -247,6 +247,49 @@ class Registry(Mapping):
         for model in models:
             model._setup_fields()
 
+        # determine field dependencies
+        Model = odoo.models.Model
+        dependencies = {
+            field: set(field.resolve_depends(model))
+            for model in models
+            if isinstance(model, Model)
+            for field in model._fields.values()
+        }
+
+        # determine transitive dependencies
+        def transitive_dependencies(field, seen=[]):
+            if field in seen:
+                return
+            for seq1 in dependencies[field]:
+                yield seq1
+                for seq2 in transitive_dependencies(seq1[-1], seen + [field]):
+                    yield concat(seq1[:-1], seq2)
+
+        def concat(seq1, seq2):
+            if seq1 and seq2:
+                f1, f2 = seq1[-1], seq2[0]
+                if f1.type == 'one2many' and f2.type == 'many2one' and \
+                        f1.model_name == f2.comodel_name and f1.inverse_name == f2.name:
+                    return concat(seq1[:-1], seq2[1:])
+            return seq1 + seq2
+
+        # determine triggers based on transitive dependencies
+        triggers = {}
+        for field in dependencies:
+            for path in transitive_dependencies(field):
+                if path:
+                    tree = triggers
+                    for label in reversed(path):
+                        tree = tree.setdefault(label, {})
+                    tree.setdefault(None, set()).add(field)
+
+        self.field_triggers_create = triggers
+        self.field_triggers = {
+            field: tree
+            for field, tree in triggers.items()
+            if not (field.type == 'one2many' and field.inverse)
+        }
+
         for model in models:
             model._setup_complete()