New Right service implementation

The implementation still needs more unit testing, but I'm uploading it in case anyone has some time to look at it and give feedback.

• The mapping of actions was incomplete and defaulted to "edit"-rights. Thus I added "edit", "lock", and "cancel" (cancel should only require "view"-right?). Are there more actions that should be mapped to EDIT? I have been stricter and am mapping any unknown action to the special ILLEGAL right which will always be denied.
• I have have used the table on the page http://dev.xwiki.org/xwiki/bin/view/Drafts/Access%20Rights rather than analysing the code of XWikiRightServiceImpl to implement the rights resolution, with the exception of the implicit "deny" behavior. It is possible that the behavior differs from the original implementation. In particular, how the rights are inherited from the main wiki to virtual wiki I have not investigated closely yet.
• There are three checkstyle errors, all for exceeding the "max fan-out" metric.
• The implementation can be tested by putting the built jar-file in WEB-INF/lib and setting xwiki.authentication.rightsclass=org.xwiki.security.XWikiCachingRightService in xwiki.cfg

The basic design of the right service implementation consists of four parts: API adaptor, cache, loader, and resolver.

The cache part is fairly generic and should be reusable for any implementation, as long as the basic structure of the wiki does not change in any fundamental fashion. The actual policies on how rights are inherited, how conflicts between rights objects are resolved and such are handled mostly by the loader, but also, some special cases are handled by the API adapter.

API adaptor

Here cache entries are looked up and the loader is called to insert required cache entries. Also, some special cases are handled up-front, such as redirecting to login-page and allowing the page creator delete rights.

Right cache

The right cache is loaded with four categories of entries: entity entries, user-at-entity entries, user and group entries. These are arranged into a hierarchy so that dependent entries can be removed on updates.

Assuming that the cache is loaded with all required entries for a particular query, the lookup proceedure is as follows:

                            have rights object
  lookup document entry     ---------------->   lookup user-at-document entry
      |
      | have no rights object
      | 
      v                     have rights object
  lookup sub-space entry    ---------------->   lookup user-at-space entry
      |
      | have no rights object
      |
      .
      .
      .
      |
      |
      v                     have rights object
  lookup space entry        ---------------->   lookup user-at-space entry
      |
      | have no rights object
      |
      v                     have rights object
  lookup wiki entry         ---------------->   lookup user-at-wiki entry
      |
      | have no rights object
      |
      v                     have rights object
  lookup main wiki entry    ---------------->   lookup user-at-wiki entry
      |
      | have no rights object
      |
      v
  use default access levels.

I believe that the lookup path 'document entry -> space entry -> wiki entry -> user-at-wiki entry' will be very common.

If a requested entry is missing, the right loader is called for loading it.

The user-at-entity entries holds a complete map of that user's rights when accessing documents that are children of the entity, and that do not overload the rights. Inheritance of rights, group memberships etc. are resolved by the right loader before inserting the entry.

The entity entries stores information on whether the entry is associated with any rights object, and if so, the rights object is cached in the entry.

A user entry is the same as the document entry for the document where the user object is stored. The only special thing about user entries is their role in the parent-child hierarchy as defined below.

The group entries are entity entries that also store group objects. These are also subject of a subtle special case: when a new member is added to a group, cached entries for the new member will not have the group as their parents and will therefore not be invalidated correctly. Special treatment is required.

The parent-child relationships between entries are defined as follows:

1. The main wiki entry is the root entity, it does not have a parent.
2. Virtual wiki entries have the main wiki entry as parent.
3. Entries for spaces without parent space have a virtual wiki or the main wiki entry as parent
4. Entries for subspaces have the respective parent space as parent entry. (The right loader may resolve loops and max recursive spaces limit by setting the wiki as parent instead, where appropriate.)
5. Document entries have the corresponding space entry as parent entry.
6. User entries have, in addition to the corresponding space entry, a set of group entries for all groups where the user is a member as parent entries. (Subtle special case: when a user and group object is located in the same document and the user is a member of the group.)
7. User-at-entity entries have both the user entry and the entity entry as parents.

The rights cache will remove all child entries along with their parent, and will refuse to insert an entry whose parent is not already in the cache. This guarantees (with the exception of the special case where a user is added to a group) that the contents of the cache is up-to-date, as long as document update events are catched and the entries corresponding to the document are removed. It also guarantees that loops cannot be formed within the parent-child hierarchy.

This also means that the cache must have capacity to store all parent entries, in addition to the desired entry, or the lookup will fail. How many are these?

Let Sd be the largest space depth.

Let D be the number of entries for a document entry. D <= 1 + 1 + Sd + 1 (main wiki entry + virtual wiki entry + space entries + the document entry itself) = 3 + Sd

Let G be the highest number of groups any user is a member of.

Then a user-at-entity entry will at the worst possible case require D + D + G * D (entries for document entry + entries for user entry + entries for group entries) = (G + 2) * (3 + Sd) entries. However, normally, all user and group documents are located in the same space, thereby sharing the same parents, so under normal curcumstances the worst case require a much smaller capacity.

The right loader

The right loader is responsible for loading entries into the cache, and also for listening to document updates and invalidating cache entries.

The right loader first prepares a list of sets, corresponding to the document hierarchy, where there are one set of rights objects per level in the hierarchy, and a set of groups for the user. These lists are then passed to the right resolver.

The right resolver

The right resolver will take as input the quintuple (user, entity, hierarchy, list of groups, list of sets of rights objects) and give as output an AccessLevel object that encodes all rights for the user with respect to the entity.