Hi, We have been discussing the algorithm used for memberof and how to make it faster. We've had a number of discussions about it, and Thierry and Ludwig both have made some great comments, and discussions of the problem cases. For more, see http://www.port389.org/docs/389ds/design/memberof-scalability.html#reusing-memberof-current-values-to-compute-the-new-ones The main problematic case, was if you have multiple paths to a node, then delete one of the paths, ensuring that children do not have the memberof invalidated. Here is the reference implementation in python, that proves the correctness of the algorithm, and that it works even for the problematic cases that Thierry discovered. It handles recursions, branch additions, deletions, replaces and more. Additionally, it shows how the fixup task will work, and how the fixup task is actually an extension of the add/delete/replace case. The majority of the algorithm is in update_memberof() of MoDb and fixup_subtree() also on MoDb. The code is commented extensively, so I hope it explains it. This is a patch to DS.git, and part of the memberof test suite. I look forwards to your comments, -- Sincerely, William Brown Software Engineer Red Hat, Brisbane
From 4e911c578f3d6c9f6308602123fdb4b090944545 Mon Sep 17 00:00:00 2001 From: William Brown <firstyear@xxxxxxxxxx> Date: Tue, 8 Nov 2016 11:03:21 +1000 Subject: [PATCH] Ticket 48856 - Reference implementation in python of the new memberof algo Bug Description: Member of is slow! Fix it! :) Fix Description: This is the reference implementation of the algorithm that re-uses existing memberof information to accelerate addition and removal of memberof. It works for complex branching and recursion cases, while limiting operations and depth of traversals. It's implemented using sets and lists, so there is no stack depth limit of recursion. Additionally, we show complex cases, add, delete, replace, and even the fixup for subtree and whole tree. https://fedorahosted.org/389/ticket/48856 Author: wibrown Review by: ??? --- .../memberof_design_reference_test.py | 828 +++++++++++++++++++++ 1 file changed, 828 insertions(+) create mode 100644 dirsrvtests/tests/suites/memberof_plugin/memberof_design_reference_test.py diff --git a/dirsrvtests/tests/suites/memberof_plugin/memberof_design_reference_test.py b/dirsrvtests/tests/suites/memberof_plugin/memberof_design_reference_test.py new file mode 100644 index 0000000..ed3cf38 --- /dev/null +++ b/dirsrvtests/tests/suites/memberof_plugin/memberof_design_reference_test.py @@ -0,0 +1,828 @@ +# --- BEGIN COPYRIGHT BLOCK --- +# Copyright (C) 2016 Red Hat, Inc. +# All rights reserved. +# +# License: GPL (version 3 or any later version). +# See LICENSE for details. +# --- END COPYRIGHT BLOCK --- +# + +# +# This test is a bit different to our normal Dirsrv tests. This does not test +# DS, but tests the reference implementation of memberOf designed by wibrown +# and tbordaz. +# +# Please see: http://www.port389.org/docs/389ds/design/memberof-scalability.html +# +# The key idea of this design is that when we have a set of nested groups, +# the membershif of A -- member -> B, is reflected in A's memberOf field. +# Provided the set of operations proceeding are valid and correct, the memberOf +# field of A can be transposed to it's members. IE +# +# C -- member -> A, no need to read B. C just add's memberOf A, and memberOf B +# discovered from A. +# +# + +import pytest + +class MoGroup(object): + def __init__(self, name, db): + self.name = name + self.member = set() + self.member_of = set() + self.db = db + + def __str__(self): + return self.name + + def __unicode__(self): + return self.name + + def __repr__(self): + return self.name + + def add_member(self, new_member): + # First, we add this member to our group of members. + print("==> starting add_member for %s" % self) + print(" adding %s to %s" % (new_member, self)) + self.member.add(new_member) + + # Now "trigger the post op". We trigger it on the new_member, not ourselves! + self.db.update_memberof([new_member,]) + print("<== add_member ended") + + def rename_member(self): + pass + # We can't actually simulate this in python. But it's easy anyway: + # Because a modrdn is source_dn -> target_dn, we can just do: + # search '(memberOf=source_dn)', then replace that value with target_dn + # on all the objects. Done! No recompute needed :) + + def delete_member(self, rem_member): + # In DS there are actually two cases here. + # Here, we are simulating the removal of the memberShip between group X and Y. + # In DS this would be a MODIFY operation on a group to MOD_DELETE / MOD_REPLACE the membership. + # for a true ldap DELETE operation, similar to rename, we can just do a mod_delete on anything + # that contains (memberOf=cn=deleted_thing) + print("==> starting delete_member for %s" % self) + print(" removing %s from %s" % (rem_member, self)) + self.member.remove(rem_member) + + # Now "trigger the post op" + self.db.update_memberof([rem_member,]) + print("<== delete_member ended") + + + def replace_member(self, to_add_member, to_rem_member): + # This is meant to simulate a MODIFY where MOD_ADD and MOD_DELETE happens in the ONE operation. + # The reason this is different to add and delete member, is that those happen in individual + # atomic actions. This happens at the *same time*, so memberOf has to be able to resolve it + # efficiently. + # + # Now, a naive approach is to treat this as a delete, followed by an add, but then we touch + # every node twice to achieve it. + # Instead, we just do it as one operation, then run the update_memberof, which resolves both! + print("==> starting replace_member for %s" % self) + print(" adding %s to %s" % (to_add_member, self)) + print(" removing %s from %s" % (to_rem_member, self)) + + self.member.remove(to_rem_member) + self.member.add(to_add_member) + + # Now "trigger the post op" + self.db.update_memberof([to_rem_member, to_add_member]) + print("<== replace_member ended") + + +class MoDb(object): + # Pretend to be a directory server! + # We allow filtering, and retrieval of groups. + + def __init__(self): + self.groups = [] + + def create_group(self, name): + new_group = MoGroup(name, self) + self.groups.append(new_group) + return new_group + + def search_group_memberships(self, group): + """ + This is the equivalent to ldapsearch '(member=cn= ... self)' + + Find everything that GROUP is a member-of! + """ + results = [] + for g in self.groups: + if group in g.member and g not in results: + results.append(g) + return results + + def search_group_members(self, group): + """ + This is the equivalent to ldapsearch '(|(member=cn=....)(...))' + + For the group, we find and return an array of it's member groups. + + Depending on how this is done in DS, it may already be in memory + if we retrieved the object. + """ + return group.member + + def update_memberof(self, modified_groups): + """ + This represents the algorithm for how memberof will actually work. + + When a group is modified, it will trigger this statement. This is + basically the post op. + + For this, we take a list of groups that changed in the operation, but + for this example, it's only going to be one. + + This is the first variant, which does not maintain a processed list. + """ + # These counters are reset between invocations, allows us to show + # the number of operations "in theory". + operation_count = 0 + search_count = 0 + # We could do this with recursion, but it's easier with a processing list. + unprocessed = [] + + # First, we have a list of modified groups. We now initiate the unprocessed list + # We need to update the groups that were modified to correct their memberOf attrs. + for group in modified_groups: + if group not in unprocessed: + unprocessed.append(group) + + # We now have a list of groups to fix up :) + + while len(unprocessed) > 0: + # Grab our target group. + tgroup = unprocessed.pop() + + operation_count += 1 + print(" --> updating memberof for %s" % tgroup) + # We create a working "member of set" + working_member_of = set() + # First, find who tgroup is a member of. + search_count += 1 + memberships = self.search_group_memberships(tgroup) + # Push them to the working set + for membership in memberships: + if membership not in working_member_of: + working_member_of.add(membership) + # Now for each of those memberships, get their member_of lists + parent_memberofs = membership.member_of + # In DS we would already have this from the previous search, so + # no extra cost yet ... + # We inherit this from the parent, so push it to our set. + for parent_memberof in parent_memberofs: + if parent_memberof not in working_member_of: + working_member_of.add(parent_memberof) + + # Now we have a "tentative" memberof set. + + # This statement is key. It means if we don't update our member_of, we don't need to trigger our + # update, nor the updates of any child members! This is what terminates any recursion from occuring, + # once we reach a stable state. It also means that with SUPER WEIRD paths through the tree, we will + # ALWAYS find a stable, and correct state. + # + print(" current memberof %s" % tgroup.member_of) + print(" proposed memberof %s" % working_member_of) + if tgroup.member_of != working_member_of: + print(" The current memberof set is not correct!") + # Update the tgroup member_of set to be the proposed one. In python + # we do a simple replace, but in DS, this would probably be some other form of action to + # diff the sets. + tgroup.member_of = working_member_of + # + # NOTE: In a recursive case this WILL add a group to be a memberOf itself! + # this isn't a bug, it means we've correctly resolved the path through the three to our node. + # and accurately reflects, that yes, I am indeed a memberOf myself. + # When the recursive link is removed it should be removed! + # + # Now, because we have changed OUR memberof list, we must tell our members to update, because + # theirs is now likely invalid also! + search_count += 1 + # This isn't really a search in python, but for DS it would be. + for member in self.search_group_members(tgroup): + if member not in unprocessed: + print(" adding member %s for update..." % member) + unprocessed.append(member) + else: + print(" member of information is unchanged! Operation complete ...") + print(" update memberof complete, operation_count = %s, search_count = %s" % (operation_count, search_count)) + + def fixup_task(self): + """ + This will go through everything in the tree and fix them all up. There + is no start point defined. + + Consider the fixup task is actually fixup subtree, but with a filter of *. + """ + self.fixup_subtree(self.groups) + + def fixup_subtree(self, yet_to_fix): + """ + In this, we are fixing up part of the tree. For this, we take a group + set as the "start point", but in the real DS code this would be a filter. + + From that start point, we descend to find the leaves of the tree, which + is either the group that only contains members (does not belong to another + group) or is a + """ + operation_count = 0 + search_count = 0 + print("==> starting fixup subtree") + + # The leaves we are going to look at. + leaves = [] + # Need to copy here, as yet_to_fix may be a ref to self.groups + unprocessed = [] + for n in yet_to_fix: + unprocessed.append(n) + processed = [] + # From our group, we could be group B at say: + # + # A --> B --> C --> D --> E + # + # For the fix up to work we descend to E, then we trigger a memberof + # Update on D! This will naturally begin to work backup the tree! + # + # The hardest part is recursion. We need to detect we are in a loop + # and prevent looking further into it, while declaring this node as + # "the leaf". + + while len(unprocessed) > 0: + operation_count += 1 + working_group = unprocessed.pop() + print(" working_group is %s" % working_group) + search_count += 1 + group_memberships = self.search_group_memberships(working_group) + print(" we belong to %s" % group_memberships ) + if len(group_memberships) == 0 or working_group in processed: + # This means we are a leaf! + if working_group not in leaves: + leaves.append(working_group) + # Add nothing else to the unprocessed group, we are done here! + else: + # We are an intermediate, keep going! + for g in group_memberships: + # This is important, as it prevents recursion. + if g not in processed and g not in unprocessed: + unprocessed.append(g) + # Say we have already been here! + processed.append(working_group) + + ## Right! We've found all all leaves that match our group we want to eventually + # fix up. Trigger the fixes! + print(" found graph leaves %s" % leaves) + # We trigger the fixes not on the leaves, but on the "members" of the leaves. + # So from out leaves, find all their members, and make this the set of nodes + # to send to update memberof. + members_to_fix = [] + for leaf in leaves: + search_count += 1 + for g in self.search_group_members(leaf): + if g not in members_to_fix: + members_to_fix.append(g) + + # This actually triggers the fixup! + self.update_memberof(members_to_fix) + print(" fixup complete, operation_count = %s, search_count = %s" %( operation_count, search_count)) + + print("<== fixup subtree ended") + +### Add cases + +def test_memberof_reference_add_1(): + """ + This tests a simple add chain. --> represents "memberof". + At the end we should see A memberof B, C, + + A B C + A B --> C + A --> B --> C + + """ + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + + group_c.add_member(group_b) + group_b.add_member(group_a) + + # We test this to ensure we have the members in the sets, but also that + # we do not have EXCESS members ... + assert(group_a.member_of == set([group_b, group_c])) + assert(group_b.member_of == set([group_c,])) + assert(group_c.member_of == set()) + + # Now we begin the delete phase. + # We are going to do the operations in reverse. + group_b.delete_member(group_a) + assert(group_a.member_of == set()) + assert(group_b.member_of == set([group_c,])) + assert(group_c.member_of == set()) + + group_c.delete_member(group_b) + + assert(group_a.member_of == set()) + assert(group_b.member_of == set()) + assert(group_c.member_of == set()) + +def test_memberof_reference_add_2(): + """ + Similar to the first test, this is an add chain, but we add the memberships + in reverse. + + A B C + A --> B C + A --> B --> C + + This means that when we update B to be a member of C, we must then go BACK + and update the memberOf of all our members. + """ + + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + + group_b.add_member(group_a) + group_c.add_member(group_b) + + assert(group_a.member_of == set([group_b, group_c])) + assert(group_b.member_of == set([group_c,])) + assert(group_c.member_of == set()) + + # Begin the delete phase. + group_c.delete_member(group_b) + assert(group_a.member_of == set([group_b,])) + assert(group_b.member_of == set()) + assert(group_c.member_of == set()) + + group_b.delete_member(group_a) + assert(group_a.member_of == set()) + assert(group_b.member_of == set()) + assert(group_c.member_of == set()) + + +def test_memberof_reference_add_3(): + """ + This is our first recursion case. We want to make sure that we do not end + up spiraling to a ball of destructions and flames. + + A B C + A --> B C + A --> B --> C + A --> B --> C - + ^----------- / + + """ + + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + + group_b.add_member(group_a) + group_c.add_member(group_b) + group_a.add_member(group_c) + + assert(group_a.member_of == set([group_a, group_b, group_c])) + assert(group_b.member_of == set([group_a, group_b, group_c])) + assert(group_c.member_of == set([group_a, group_b, group_c])) + + # Begin deletion. The moment you break the recursion, this should clean up lots of memberships. + group_a.delete_member(group_c) + assert(group_a.member_of == set([group_b, group_c])) + assert(group_b.member_of == set([group_c,])) + assert(group_c.member_of == set()) + # At this the deletions are the same as before: + group_b.delete_member(group_a) + group_c.delete_member(group_b) + assert(group_a.member_of == set()) + assert(group_b.member_of == set()) + assert(group_c.member_of == set()) + +def test_memberof_reference_add_4(): + """ + This test shows that when we have: + + A --> B + C --> D + + When we add E, and make it + + E --> A, E --> C + That E should contain the correct memberships attrs. + """ + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + group_d = db.create_group("d") + group_e = db.create_group("e") + + group_b.add_member(group_a) + group_d.add_member(group_c) + group_c.add_member(group_e) + group_a.add_member(group_e) + + assert(group_a.member_of == set([group_b,])) + assert(group_b.member_of == set()) + assert(group_c.member_of == set([group_d,])) + assert(group_d.member_of == set()) + assert(group_e.member_of == set([group_a, group_b, group_c, group_d])) + + # Begin to delete. + # Show we can delete A --> B, and reflects in E. + group_b.delete_member(group_a) + assert(group_a.member_of == set()) + assert(group_b.member_of == set()) + assert(group_c.member_of == set([group_d,])) + assert(group_d.member_of == set()) + assert(group_e.member_of == set([group_a, group_c, group_d])) + + # Now delete c + group_c.delete_member(group_e) + assert(group_a.member_of == set()) + assert(group_b.member_of == set()) + assert(group_c.member_of == set([group_d,])) + assert(group_d.member_of == set()) + assert(group_e.member_of == set([group_a,])) + # At this point, the remaining deletions are simple. + +def test_memberof_reference_add_5(): + """ + This test shows that when we have multiple paths through the tree, we correctly + update our references. + + Consider: + + A --> B --> C + ^ + D --> E -/ + + Now, we add the membership of D to A, so that A now is a MemberOf D. + """ + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + group_d = db.create_group("d") + group_e = db.create_group("e") + + group_b.add_member(group_a) + group_c.add_member(group_b) + group_b.add_member(group_e) + group_e.add_member(group_d) + group_d.add_member(group_a) + + assert(group_a.member_of == set([group_b, group_c, group_d, group_e])) + assert(group_b.member_of == set([group_c,])) + assert(group_c.member_of == set()) + assert(group_d.member_of == set([group_e, group_b, group_c])) + assert(group_e.member_of == set([group_b, group_c])) + + # Now begin to undo the operations. + group_d.delete_member(group_a) + assert(group_a.member_of == set([group_b, group_c])) + assert(group_b.member_of == set([group_c,])) + assert(group_c.member_of == set()) + assert(group_d.member_of == set([group_e, group_b, group_c])) + assert(group_e.member_of == set([group_b, group_c])) + # After this it's simple operations we already have proven. + +def test_memberof_reference_add_6(): + """ + This is a similar recursion case. but we add a branch of groups after. + + A B C + A --> B C + A --> B --> C + A --> B --> C - + ^----------- / + + Then to B: + + B --> D --> E + + """ + + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + group_d = db.create_group("d") + group_e = db.create_group("e") + + group_b.add_member(group_a) + group_c.add_member(group_b) + group_a.add_member(group_c) + group_e.add_member(group_d) + group_d.add_member(group_b) + + assert(group_a.member_of == set([group_a, group_b, group_c, group_d, group_e])) + assert(group_b.member_of == set([group_a, group_b, group_c, group_d, group_e])) + assert(group_c.member_of == set([group_a, group_b, group_c, group_d, group_e])) + assert(group_d.member_of == set([group_e, ])) + assert(group_e.member_of == set()) + + # Now begin to delete. + group_a.delete_member(group_c) + assert(group_a.member_of == set([group_b, group_c, group_d, group_e])) + assert(group_b.member_of == set([group_c, group_d, group_e])) + assert(group_c.member_of == set()) + assert(group_d.member_of == set([group_e, ])) + assert(group_e.member_of == set()) + # Now break D off. + group_d.delete_member(group_b) + assert(group_a.member_of == set([group_b, group_c,])) + assert(group_b.member_of == set([group_c,])) + assert(group_c.member_of == set()) + assert(group_d.member_of == set([group_e, ])) + assert(group_e.member_of == set()) + # We are back to a simple chain again. + +def test_memberof_reference_add_7(): + """ + This is a similar recursion case. but we add a branch of groups before. + to B: + + B --> D --> E + + Then: + A B C + A --> B C + A --> B --> C + A --> B --> C - + ^----------- / + """ + + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + group_d = db.create_group("d") + group_e = db.create_group("e") + + group_e.add_member(group_d) + group_d.add_member(group_b) + group_b.add_member(group_a) + group_c.add_member(group_b) + group_a.add_member(group_c) + + assert(group_a.member_of == set([group_a, group_b, group_c, group_d, group_e])) + assert(group_b.member_of == set([group_a, group_b, group_c, group_d, group_e])) + assert(group_c.member_of == set([group_a, group_b, group_c, group_d, group_e])) + assert(group_d.member_of == set([group_e, ])) + assert(group_e.member_of == set()) + + # Deletion test already done above. + +def test_memberof_reference_delete_1(): + """ + This is similar to Thierry's problematic case, and shows the solutions. + + We have the following: + + A --> B --> C --> D + | ^ + \---> E ---/ + + When we delete B --> E, this means that E: moD would be removed as it's a + possible path of inheritence from B. However, because of C --> D, we need to + retain D. + + At the same time, A must remove moE, and retain D. + """ + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + group_d = db.create_group("d") + group_e = db.create_group("e") + + group_d.add_member(group_c) + group_d.add_member(group_e) + group_c.add_member(group_b) + group_e.add_member(group_b) + group_b.add_member(group_a) + + group_e.delete_member(group_b) + + assert(group_a.member_of == set([group_b, group_c, group_d])) + assert(group_b.member_of == set([group_c, group_d])) + assert(group_c.member_of == set([group_d,])) + assert(group_d.member_of == set()) + assert(group_e.member_of == set([group_d,])) + +def test_memberof_reference_delete_2(): + """ + This is similar to Thierry's problematic case, but expands on it. + + We have the following: + + A --> B --> C --> D --> F + | | ^ + | \---> E ---/ + | ^ + \-----------/ + + When we delete C --> E, this means that E: moD would be removed as it's a + possible path of inheritence from C. However, because of B --> E, only memberof + C should change: Member of B stays the same! + + This should show an interesting optimisation of the algorithm: When B does + not need to change it's MO, it should *not* trigger the event on A during processing. + """ + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + group_d = db.create_group("d") + group_e = db.create_group("e") + group_f = db.create_group("f") + + group_f.add_member(group_e) + group_f.add_member(group_d) + group_d.add_member(group_c) + group_e.add_member(group_c) + group_e.add_member(group_b) + group_c.add_member(group_b) + group_b.add_member(group_a) + + group_e.delete_member(group_c) + + assert(group_a.member_of == set([group_b, group_c, group_d, group_e, group_f])) + assert(group_b.member_of == set([group_c, group_d, group_e, group_f])) + assert(group_c.member_of == set([group_d, group_f])) + assert(group_d.member_of == set([group_f,])) + assert(group_e.member_of == set([group_f,])) + assert(group_f.member_of == set()) + +def test_memberof_reference_replace_1(): + """ + The replacement case is internally just an add / delete, followed by updating + all the touched group nodes. + + We use a rather large tree, but proving that it works for replace, implies + all other designs of tree work also given the algo is already proven for + recursive, multipath and branch cases. + + We start with: + + A --> B --> C + + D --> E + + Now we replace the membership of A in B, with E. + + A B --> C + ^ + D --> E --/ + + """ + + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + group_d = db.create_group("d") + group_e = db.create_group("e") + + group_c.add_member(group_b) + group_b.add_member(group_a) + group_e.add_member(group_d) + group_b.replace_member(group_e, group_a) + + assert(group_a.member_of == set()) + assert(group_b.member_of == set([group_c])) + assert(group_c.member_of == set()) + assert(group_d.member_of == set([group_b, group_e, group_c])) + assert(group_e.member_of == set([group_b, group_c])) + +def test_memberof_reference_fixup_1(): + """ + This is a full tree fixup. We blow away all the memberof attributes, + and expect them to be rebuilt. + + We reuse the tree from an earlier test, as it's complex enough to + prove correct fixing. + + A --> B --> C --> D --> F + | | ^ + | \---> E ---/ + | ^ + \-----------/ + """ + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + group_d = db.create_group("d") + group_e = db.create_group("e") + group_f = db.create_group("f") + + group_f.add_member(group_e) + group_f.add_member(group_d) + group_d.add_member(group_c) + group_e.add_member(group_c) + group_e.add_member(group_b) + group_c.add_member(group_b) + group_b.add_member(group_a) + + # Purge all the memberof data .... + for group in db.groups: + group.member_of = set() + + db.fixup_task() + + assert(group_a.member_of == set([group_b, group_c, group_d, group_e, group_f])) + assert(group_b.member_of == set([group_c, group_d, group_e, group_f])) + assert(group_c.member_of == set([group_d, group_e, group_f])) + assert(group_d.member_of == set([group_f,])) + assert(group_e.member_of == set([group_f,])) + assert(group_f.member_of == set()) + +def test_memberof_reference_fixup_2(): + """ + This is proof of the subtree fixup. We create two trees, and destroy + memberof attrs in both. Then we only target a single tree for fixing. + + A --> B --> C + + D --> E --> F + """ + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + group_d = db.create_group("d") + group_e = db.create_group("e") + group_f = db.create_group("f") + + group_b.add_member(group_a) + group_c.add_member(group_b) + group_e.add_member(group_d) + group_f.add_member(group_e) + + # Purge all the memberof data .... + for group in db.groups: + group.member_of = set() + + # Note, we don't need to list B, but it will be fixed! + db.fixup_subtree([group_a, group_c]) + + assert(group_a.member_of == set([group_b, group_c,])) + assert(group_b.member_of == set([group_c,])) + assert(group_c.member_of == set()) + # Remember, these were NOT run in the fixup!!!! + assert(group_d.member_of == set()) + assert(group_e.member_of == set()) + assert(group_f.member_of == set()) + +def test_memberof_reference_fixup_3(): + """ + Show that in a recursive case, fixup still works! + A B C + A --> B C + A --> B --> C + A --> B --> C - + ^----------- / + + Then to B: + + B --> D --> E + + """ + + db = MoDb() + group_a = db.create_group("a") + group_b = db.create_group("b") + group_c = db.create_group("c") + group_d = db.create_group("d") + group_e = db.create_group("e") + + group_b.add_member(group_a) + group_c.add_member(group_b) + group_a.add_member(group_c) + group_e.add_member(group_d) + group_d.add_member(group_b) + + # Purge all the memberof data .... + for group in db.groups: + group.member_of = set() + + db.fixup_task() + + assert(group_a.member_of == set([group_a, group_b, group_c, group_d, group_e])) + assert(group_b.member_of == set([group_a, group_b, group_c, group_d, group_e])) + assert(group_c.member_of == set([group_a, group_b, group_c, group_d, group_e])) + assert(group_d.member_of == set([group_e, ])) + assert(group_e.member_of == set()) + -- 1.8.3.1
Attachment:
signature.asc
Description: This is a digitally signed message part
_______________________________________________ 389-devel mailing list -- 389-devel@xxxxxxxxxxxxxxxxxxxxxxx To unsubscribe send an email to 389-devel-leave@xxxxxxxxxxxxxxxxxxxxxxx
