From 35c7caba9a822a4ff101c032a78b9a339faa2aba Mon Sep 17 00:00:00 2001 From: Mike Bayer Date: Sat, 24 Dec 2005 17:37:11 +0000 Subject: [PATCH] comments re: partial ordering, association dependencies license for topological --- lib/sqlalchemy/mapping/properties.py | 19 +++++++----- lib/sqlalchemy/mapping/topological.py | 43 +++++++++++++++++++++++++++ 2 files changed, 54 insertions(+), 8 deletions(-) diff --git a/lib/sqlalchemy/mapping/properties.py b/lib/sqlalchemy/mapping/properties.py index 443f5eac86..cd04c0c642 100644 --- a/lib/sqlalchemy/mapping/properties.py +++ b/lib/sqlalchemy/mapping/properties.py @@ -387,20 +387,23 @@ class PropertyLoader(MapperProperty): they've been deleted. The process operation manages attributes and dependent operations upon the objects of one of the involved mappers.""" if self.association is not None: - # association object. our mapper is made to be dependent on our parent, - # as well as the object we associate to. when theyre done saving (or before they - # are deleted), we will process child items off objects managed by our parent mapper. - - # still working out how the dependencies should work here. - - # this seems to work: + # association object. our mapper should be dependent on both + # the parent mapper and the association object mapper. + + # this seems to work, association->parent->self, then + # we process the child elements after the 'parent' save. but + # then the parent is dependent on the association which is + # somewhat arbitrary, might compete with some other dependency: # uowcommit.register_dependency(self.association, self.parent) # uowcommit.register_dependency(self.parent, self.mapper) # #uowcommit.register_dependency(self.association, self.mapper) # uowcommit.register_processor(self.parent, self, self.parent, False) # uowcommit.register_processor(self.parent, self, self.parent, True) - # this seems to work too, using the "stub" as a marker + # this is where we put the "stub" as a marker, so we get + # association/parent->stub->self, then we process the child + # elments after the 'stub' save, which is before our own + # mapper's save. stub = PropertyLoader.MapperStub() uowcommit.register_dependency(self.parent, stub) uowcommit.register_dependency(self.association, stub) diff --git a/lib/sqlalchemy/mapping/topological.py b/lib/sqlalchemy/mapping/topological.py index ef3f102a9b..6001c79758 100644 --- a/lib/sqlalchemy/mapping/topological.py +++ b/lib/sqlalchemy/mapping/topological.py @@ -1,3 +1,46 @@ +# topological.py +# Copyright (C) 2005 Michael Bayer mike_mp@zzzcomputing.com +# +# This library is free software; you can redistribute it and/or +# modify it under the terms of the GNU Lesser General Public +# License as published by the Free Software Foundation; either +# version 2.1 of the License, or (at your option) any later version. +# +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU Lesser General Public License for more details. +# +# You should have received a copy of the GNU Lesser General Public License +# along with this library; if not, write to the Free Software +# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + +"""topological sorting algorithms. the key to the unit of work is to assemble a list +of dependencies amongst all the different mappers that have been defined for classes. +Related tables with foreign key constraints have a definite insert order, deletion order, +objects need dependent properties from parent objects set up before saved, etc. +These are all encoded as dependencies, in the form "mapper X is dependent on mapper Y", +meaning mapper Y's objects must be saved before those of mapper X, and mapper X's objects +must be deleted before those of mapper Y. + +The topological sort is an algorithm that receives this list of dependencies as a "partial +ordering", that is a list of pairs which might say, "X is dependent on Y", "Q is dependent +on Z", but does not necessarily tell you anything about Q being dependent on X. Therefore, +its not a straight sort where every element can be compared to another...only some of the +elements have any sorting preference, and then only towards just some of the other elements. +For a particular partial ordering, there can be many possible sorts that satisfy the +conditions. + +An intrinsic "gotcha" to this algorithm is that since there are many possible outcomes +to sorting a partial ordering, the algorithm can return any number of different results for the +same input; just running it on a different machine architecture, or just random differences +in the ordering of dictionaries, can change the result that is returned. While this result +is guaranteed to be true to the incoming partial ordering, if the partial ordering itself +does not properly represent the dependencies, code that works fine will suddenly break, then +work again, then break, etc. Most of the bugs I've chased down while developing the "unit of work" +have been of this nature - very tricky to reproduce and track down, particularly before I +realized this characteristic of the algorithm. +""" import string class QueueDependencySorter(object): -- 2.47.2