Where to get the code

I put a git repo with my work up on fedorapeople. It's been rebased against master, in the dn branch. To get the code:

git clone git://fedorapeople.org/~jdennis/freeipa.dn.git
git checkout dn

Suggested review strategy

The patch is huge as one would expect when changing the data type of the most heavily used data item in the project. 114 files were affected and 5,526 lines of code modified in some form. I don't think it's practical to review every changed line of code. Instead you should realize the bulk of the changes can be distilled into some basic patterns that were repeated frequently.

Changing dn's that were strings into DN objects was a big set of changes. Another frequent code change was the insertion of assert statements to verify routines that were expecting DN objects in fact were passed DN objects and not strings. Those two rather simple modifications account for a large part of the changed lines. Each change from string to DN was individually visited by me but was performed by an editor macro. This sped the process and eliminated human error during the edit. After the macro executed I visually verified the modification was correct. I don't think there is much value in trying to review all of those types of changes, it's unlikely there was a mistake in it due to the automation in conjunction with my review and the fact the code fully passes the unit tests and installs the server correctly. I'm not saying there couldn't be a lingering error, just that trying to eyeball every one of these in a review does not seem like a fruitful pursuit.

Another large collection of innocuous changes was simplifying how DN are checked in the unit tests. Formerly we used a lambda expression in the expected value to promote the returned value (e.g. the got value) into a DN object so the equality test could be performed by two DN's. That was fine when we only had a handful of DN's in the code. But now that everything is a DN all those lambda expressions in the test results got unwieldy, verbose and made the code hard to read. The promotion to DN now occurs automatically. Every place in the unit tests were we used a lambda expression to compare a DN has been removed and replaced with the simple expected value. As above I don't see much value in reviewing all the changes to lambda expressions in the unit tests.

Another large block of diffs in the patch come from moving a file or removing a file.

The above changes probably account for 80% of the patch.

The rest of the changes fall into some basic groups:

1. Changing how components of a dn are accessed and modified. String operations were replaced with the use of DN operators.
2. Refactoring some of the ldap objects to get all ldap operations to funnel through the same low level ldap code so we can use DN's through the entire pipeline and how data flowing in and out of LDAP is converted. This is explained in great detail below.

Reviewing changes from item 1 may help you better understand how DN's streamline the code by replacing (convoluted) string manipulation with concise Python operators that clearly expresses code logic (internally those simple operators assure escaping, encoding, formatting, etc. are properly handled). For review purposes the question arises if I sufficiently understood the exiting code logic and was able to replicate the logic with DN operators. There were definitely a number of places in the code where I had study the code long and hard to suss out it's actual logic. Were there mistakes in any of these conversions? Careful code review is one approach, but there are quite a few of them to look at. I'm more of the mind that if a logic error was introduced we're more likely to find it via the unit tests or other code exercise rather than having eyeballs on every one of these changes.

Item 2 is one area that is most deserving of a traditional code review. It's an architectural change. It attempts to push our code in a particular direction; the convergence on a single API for performing ldap operations and a reduction of duplicate code. This was perhaps the most difficult part of the entire task, we had so many different ways of doing the same thing and unfortunately DN's flowed through every one of those needlessly different code paths.

State of rebase

The repo is current with master as of Friday July 6th. FWIW keeping the branch current with master has been a significant time sink because the changes are spread out over the entire code base.

State of testing

As of Friday July 6th all unit tests pass. ipa-server-install runs without error and produces a server installation under which all unit tests run by lite-server passes.

FWIW during development I typically use RPM's from the devel repo to install the server components, this way I know the 389-ds, KDC, etc. install is clean. Then I run the unit tests under lite-server. Once all the unit tests run successfully I build RPM's from my tree and perform a new install using code from my tree, if there are no install errors I then re-run the unit tests using lite-server against the installed components from my tree. I've found this to be a good way to isolate the two major parts of our code, install code and run-time code, both of which share DN changes.

What needs testing

Obviously others should repeat the unit test and install testing I did as described in State of testing. However one critical area I have not tested are the command line utilities, especially those that set up replication, perform migration etc. If someone could help exercise those it would be a tremendous help.

Remaining things to clean up

I've got a few FIXME's sprinkled through the code that I need to go back and revisit (marked with my initials 'jrd').

There are a few places where code formatting or file layout are ugly. Since I was most focused on getting things to run cleanly I postponed making things pretty. Along these lines we should be careful with what we export from modules. Python provides the __all__ module export list, we really should be making better use of that.

I need to add documentation in places, it's not up to my usual standards of documenting everything (although I did document some stuff already).

We need to break the DN class into mutable and immutable variants. There is a lengthy discussion of this below, but I don't believe it's affecting anything at the moment.

Why did I use tuples instead of strings when initializing DN's?

I'm sure this question will come up. Why did you use individual tuples to initialize a DN when you could have used a string? It's a good question to ask.

Here's an example:

dn = 'cn=masters,cn=ipa,cn=etc,%s' % suffix

became:

dn = DN(('cn', 'masters'), ('cn', 'ipa'), ('cn', 'etc'), suffix)

but it could have been this:

dn = DN('cn=masters,cn=ipa,cn=etc', suffix)

Why not? Isn't easier to read and still produces the same DN object?

Yes, the last form will produce the same value because the DN constructor will parse the first string as dn string representation, breaking it into it's components and then appends the suffix dn components (here we assume suffix is already a DN object).

There are two issues with the above:

It's inefficient, it has to fully parse the string and produce tuples from the parsing, so why not feed it the tuples to begin with and avoid all the parsing work?

It's dependent upon the string being a correctly formatted and escaped string representation of a dn. For this particular simple dn it's not hard to get this right.

But now suppose someone comes along later and decides the first cn value (masters) needs to be parameterized. I can almost guarantee it will be done as string substitution (I've seen actual examples of this multiple times) where the above becomes this:

dn = DN('cn=%s,cn=ipa,cn=etc' % my_master, suffix)

This type of dn formation via string formatting is 100% wrong and is a large part of what motivated us to introduce DN objects in the first place. It's wrong because simple string substitution may not produce a valid dn string representation. Now we're back to the exact same problem we tried so hard to get rid of.

My belief is for best code practice with dn's one should use tuples for the following reasons:

• It's more efficient

• It expresses what DN's really are, a sequence of attribute/value pairs (technically that's not correct but it's a reasonable mental model in the majority of cases [4])

• It discourages the type of careless string formatting discussed above. If the original code had been:

  dn = DN(('cn', 'masters'), ('cn', 'ipa'), ('cn', 'etc'), suffix)
  

and the programmer needed to parameterize 'masters' the natural inclination would have been the correct formulation where the parameterized value was passed as a tuple member:

dn = DN(('cn', my_master), ('cn', 'ipa'), ('cn', 'etc'), suffix)

I personally find the tuple expression of a dn just as easy to read as a string formatted version, but I realize this may be an issue of personal taste. I believe code readability is an important factor to consider.

Motivation

DN's are compound binary objects with specific rules. DN's have a string representation defined by RFC 4514. There is more than one valid string representation for equivalent DN's. It is not possible to correctly manipulate DN's (extract components, perform comparisons, assemble components, etc.) using simple string operations on a given string representation. The string representation needs to be parsed into it's constituent components and operations performed on the normalized individual components. After manipulation the components can be reassembled back into one of the valid string representations for data exchange purposes.

In IPA we tried to treat DN's as simple strings, they aren't and this introduced problems.

Overarching Goal

Define a DN object class which properly implements DN behavior.

Inside of IPA code anything that is a DN will be a DN object 100% of the time

Quick overview of what changed

• Convert every string specifying a DN into a DN object

• Every place a dn was manipulated in some fashion it was replaced by the use of DN operators

• Add new DNParam parameter type for parameters which are DN's

• Require that every place a dn is used it must be a DN object. This translates into lot of:

  assert isinstance(dn, DN)
  

  sprinkled through out the code.

• Moved ipalib.dn to ipapython.dn because DN class is shared with all components, not just the server which uses ipalib.

• All API's now accept DN's natively, no need to convert to str

• unit test frame work now accepts DN's natively, no need for lambda expressions in the expected dicts

• removed ipalib.encoder (see below for details)

• Entity & Entry classes now utilize DN's

• Fix __getattr__ in Entity & Entity so that Python internal methods are not masked, e.g. those beginning and ending with double underscores.

• All certificate subject bases are now DN's

• Fixed ldapupdate to work with DN's. Rewrote a couple of functions in ldapupate and added documentation on the data structure being used. The goal was to be clearer and more Pythonic.

• Removed all usage of get_schema() which was being called prior to accessing the .schema attribute of an object. If a class is using internal lazy loading as an optimization it's not right to require users of the interface to be aware of internal optimization's. Instead the class should handle it's lazy loading completely internally by loading the data on first access. This is very easy to do with class properties. schema is now a property of the class instead of an attribute. When the schema property is accessed it actually calls a private internal method to perform the lazy loading.

• Added SchemaCache class to cache the schema's from individual servers. This was done because of the observation we talk to different LDAP servers, each of which may have it's own schema. Previously we globally cached the schema from the first server we connected to and returned that schema in all contexts.

• We are aware of the LDAP syntax of all LDAP attributes. Every attribute returned from an LDAP operation is passed through a central table look-up based on it's LDAP syntax. The table key is the LDAP syntax it's value is a Python callable that returns a Python object matching the LDAP syntax. There are a handful of LDAP attributes whose syntax is historically incorrect (e.g. DistguishedNames that are defined as DirectoryStrings). The table driven conversion mechanism is augmented with a table of hard coded exceptions.

  Currently only the following conversions occur via the table:

  • dn's are converted to DN objects
  • binary objects are converted to Python str objects (IPA convention).
  • everything else is converted to unicode using UTF-8 decoding (IPA convention).

  However, now that the table driven conversion mechanism is in place it would be trivial to do things such as converting attributes which have LDAP integer syntax into a Python integer, etc.

• Expected values in the unit tests which are a DN no longer need to use lambda expressions to promote the returned value to a DN for equality comparison. The return value is automatically promoted to a DN. The lambda expressions have been removed making the code much simpler and easier to read.

• Add class level logging to a number of classes which did not support logging, less need for use of root_logger.

• Remove ipaserver/conn.py, it was unused.

• Consolidated duplicate code wherever I found it.

Derived Goals

Goals

• Start to converge on type consistency in the IPA code domain. DN's will be an initial step in that direction.
• Anything that is logically a dn will be a DN object everywhere in IPA code.
  • DN's will be converted to DN objects when they enter the IPA domain via some type of data import at an API boundary. Examples include:
    • Reading data from an LDAP server via a native LDAP call.
    • Reading data from an RPC call.
    • Reading data from any non-IPA external API.
    • Reading data from user input.
    • Reading data from a file.
  • DN's will be converted to a string representation when they are exported from the IPA domain. Examples include:
    • Writing data to an LDAP server via a native LDAP call.
    • Writing data to an RPC call.
    • Writing data to any non-IPA external API.
    • Writing data to a user interface.
    • Writing data to a file.
• Converge on ldap2 as the IPA interface to LDAP (a stated project goal)

Existing problems in conflict with the goals

DN object implementation experience

DN objects were coded up well before they were widely utilized in the IPA code base. How did they hold up in the myriad ways IPA would utilize them? There is a big difference between using them in a few isolated places verses using them extensively.

Overall I was pretty happy, I didn't discover any bugs in the DN implementation [1]. However what I did discover was they needed some extra features for specific situations. The following enhancements were added:

• An insert() method to permit a RDN or DN to be inserted to inserted at an arbitrary location in an existing DN.
• The find() and rfind() methods (modeled after their string cousins) to locate a RDN or DN in an existing DN.
• The replace() method to allow replacing a sequence of RDN's with another RDN or DN within a DN.
• Locking to prevent modification. [1]
• __repr__() method to produce a value that can be read by the interpreter and so that when objects are printed you can distinguish if an item is a string, a string representation of a DN, or it's a DN object.
• Permitting a string to be compared for equality with a DN object. Formerly only two DN's could be compared which makes sense because two objects need to be of the same type to be equal. But it was worthwhile in practice to promote a string to a DN if it was being compared to a DN and perform the equality test between the two DN's. This is a form of automatic type promotion. Python already does automatic type promotion in a limited number of circumstances (but nothing like on the order of Perl). Originally I was against automatic type promotion on the belief if you were comparing a string to a DN it was a failure of program logic, but there were some circumstances where it was evil necessity. The equality test is the only place where an automatic type promotion occurs.

Overall, I found DN's easy to work with, Pythonic, and in many cases greatly simplified code so the intended logic was obvious and concise.

Why and how LDAP encode/decode was refactored

1. As noted in Multiple inconsistent LDAP interfaces it's important that all LDAP operations funnel through the same common code otherwise it's too difficult and error prone to provide the exact same type conversions universally throughout the IPA programming domain.

2. We also noted in Derived Goals that inside the IPA programming domain we would always utilize the same object types.

Issues 1 and 2 above presented a structural problem that forced some LDAP code refactoring.

The implemented solution for the python-ldap API boundary

We define a new IPA specific class called IPASimpleLDAPObject, it does not subclass anything (aside from the root object metaclass which makes it a new style Python class).

IPASimpleLDAPObject implements only those methods from SimpleLDAPObject that are used in IPA. Each method in IPASimpleLDAPObject explicitly converts it's parameters to python-ldap types, calls the corresponding SimpleLDAPObject method, and then converts the result back to an IPA type before returning.

Another nice feature of this approach is we can add class level logging and log the actual raw python-ldap operations.

IPASimpleLDAPObject is now used for all LDAP connections (typically called 'conn' in the code). This is what provides the uniformity despite still having multiple LDAP mechanisms.

str(var).encode(self.encoder_settings.encode_to)

import codecs
utf8_codec = codecs.lookup('utf-8')
value = utf8_codec.encode(unicode(value))[0]

@encode_args(1, 2, 3)
@decode_retval()
def find_entries(self, filter=None, attrs_list=None, base_dn='',
        scope=_ldap.SCOPE_SUBTREE, time_limit=None, size_limit=None,
        normalize=True, search_refs=False):

@encode_args(1, 2, 3)
def modify_password(self, dn, new_pass, old_pass=''):

@encode_args(1, 2)
def make_filter_from_attr(self, attr, value, rules='|', exact=True,

DN Mutability

There is one issue with DN objects. DN objects as originally implemented are mutable, i.e. you can modify them. Python makes a clear distinction between mutable and immutable objects. Examples of immutable Python objects are strings, integers and floats. Examples of mutable Python objects are lists, dicts, and sets.

Mutability has a direct impact on how objects are used as keys in Python dictionaries and sets. When a Python object is used as a key in a dict or as member of a set Python will compute a hash value for that object and use the object's hash value to access the item in the dict or set. For immutable objects the hash value is computed from the value of the object. Thus two strings that are equal will hash to the same hash value even though they are different objects. For example:

>>> A = 'some string'
>>> B = 'some string'
>>> hash(A)
-1704511165
>>> hash(B)
-1704511165
>>> hash(A) == hash(B)
True
>>> A == B
True
>>> id(A)
143567432
>>> id(B)
143567352
>>> id(A) == id(B)
False
>>> A is B
False
>>> d = {A: 1}
>>> A in d
True
>>> B in d
True
>>> d[B] = 2
>>> d
{'some string': 2}
>>> A in d
True

A and B are two different Python objects, however they are equal. Both A and B produce the same hash value. You can tell they are different objects because A and B have different id's. If you ask Python if A and B are equal Python says yes. If you ask Python if A and B are the same object Python says no [2]. For those familiar with Lisp this is the analog of equal vs. eq. If you use A as a key in a dict then A will hash to the same value, thus object A and object B are considered to be members of the dict (or members of a set) even though they are different objects. This is how you can use a dict (or set) to give you unique non-duplicate collections, because immutable objects hash to the same value. Note how either object A or object B can be used to change the value in the dict and the dict has just one entry no matter whether A or B is used as a key.

But consider the dilemma facing Python when a mutable object is used as a key in dict or member of a set. Since it's mutable it's hash value may be different at different moments in time, this leads to unpredictable results. The solution is simple, instead of using the object's value to compute the hash it's identity is used instead. Every Python object has a unique identity (most implementations use the pointer to the objects memory block as it's identity).

This means two mutable objects that are otherwise equal do not share the same hash value thus they do not share the same key in a dict and are considered different members in a Python set. This can produce counter-intuitive results. In general only Python native immutable types can be used in Python dicts and sets when uniqueness is desired. User defined types (i.e. classes defined in a program) are by default considered mutable and thus do not provide uniqueness when used as keys in a dict or members of a set.

Python determines if an object is hashable if the object contains a __hash__ method. The __hash__ method is invoked to obtain the object's hash value. For immutable objects the __hash__ method uses the object's value. For mutable objects the __hash__ method uses the object's identity. It is entirely possible to provide immutable semantics to user defined classes if the class defines it's own __hash__ method.

It's important to understand the difference in Python between hashing, equality, and identity.

Equality and inequality (i.e. the == operator implemented by a class via the __eq__ method and != operator implemented by the class __ne__ method respectively) compare values. The 'is' keyword is used to compare object identity. Thus when you see:

if foo is None:

in the code what is occurring is testing to see if the object the symbol foo is referring to is exactly the same object as the global object None. Why does this work? Because None is a singleton, there is exactly one None object. If you assign None to symbol you're assigning a reference to exactly the same None object used everywhere.

The 'in' operator, e.g.:

if foo in (bar, blatz, burfl):

uses the equality operator (e.g. ==) iteratively to test each member for equality (not identity). The above is equivalent to:

for x in (bar, blatz, burfl):
    if foo.__eq__(x):
        return True
return False

The distinction between membership testing using the 'in' operator verses using a hash value for dict keys or sets is critical to understand because the former uses the __eq__ method of an object and the later uses the __hash__ method of an object. In practical terms it's whether an object is mutable which determines if the 'in' operator and key index or set membership operate the same or differently.