More contrib cleanout

[openldap] / libraries / librewrite / RATIONALE

/******************************************************************************
 *
 * Copyright (C) 2000 Pierangelo Masarati, <ando@sys-net.it>
 * All rights reserved.
 *
 * Permission is granted to anyone to use this software for any purpose
 * on any computer system, and to alter it and redistribute it, subject
 * to the following restrictions:
 *
 * 1. The author is not responsible for the consequences of use of this
 * software, no matter how awful, even if they arise from flaws in it.
 *
 * 2. The origin of this software must not be misrepresented, either by
 * explicit claim or by omission.  Since few users ever read sources,
 * credits should appear in the documentation.
 *
 * 3. Altered versions must be plainly marked as such, and must not be
 * misrepresented as being the original software.  Since few users
 * ever read sources, credits should appear in the documentation.
 * 
 * 4. This notice may not be removed or altered.
 *
 ******************************************************************************/

/*
 * Description
 *
 *      A string is rewritten according to a set of rules, called
 *      a `rewrite context'.
 *      The rules are based on Regular Expressions (POSIX regex) with
 *      substring matching; extensions are planned to allow basic variable
 *      substitution and map resolution of substrings.
 *      The behavior of pattern matching/substitution can be altered by a
 *      set of flags.
 *
 *      The underlying concept is to build a lightweight rewrite module
 *      for the slapd server (initially dedicated to the back-ldap module).
 *
 *
 * Passes
 *
 *      An incoming string is matched agains a set of rules. Rules are made
 *      of a match pattern, a substitution pattern and a set of actions.
 *      In case of match a string rewriting is performed according to the
 *      substitution pattern that allows to refer to substrings matched
 *      in the incoming string. The actions, if any, are finally performed.
 *      The substitution pattern allows map resolution of substrings.
 *      A map is a generic object that maps a substitution pattern to a
 *      value.
 *
 *
 * Pattern Matching Flags
 *
 *      'C'     honors case in matching (default is case insensitive)
 *      'R'     use POSIX Basic Regular Expressions (default is Extended)
 *
 *
 * Action Flags
 *
 *      ':'     apply the rule once only (default is recursive)
 *      '@'     stop applying rules in case of match.
 *      '#'     stop current operation if the rule matches, and issue an
 *              `unwilling to perform' error.
 *      'G{n}'  jump n rules back and forth (watch for loops!). Note that
 *              'G{1}' is implicit in every rule.
 *      'I'     ignores errors in rule; this means, in case of error, e.g.
 *              issued by a map, the error is treated as a missed match.
 *              The 'unwilling to perform' is not overridden.
 *
 *      the ordering of the flags is significant. For instance:
 *
 *      'IG{2}' means ignore errors and jump two lines ahead both in case
 *              of match and in case of error, while
 *      'G{2}I' means ignore errors, but jump thwo lines ahead only in case
 *              of match.
 *
 *      More flags (mainly Action Flags) will be added as needed.
 *
 *
 * Pattern matching: 
 *
 *      see regex(7)
 *
 *
 * String Substitution:
 *
 *      the string substitution happens according to a substitution pattern.
 *      -       susbtring substitution is allowed with the syntax '\d'
 *              where 'd' is a digit ranging 0-9 (0 is the full match).
 *              I see that 0-9 digit expansion is a widely accepted
 *              practise; however there is no technical reason to use
 *              such a strict limit. A syntax of the form '\{ddd}'
 *              should be fine if there is any need to use a higher
 *              number of possible submatches.
 *      -       variable substitution will be allowed (at least when I
 *              figure out which kind of variable could be proficiently
 *              substituted)
 *      -       map lookup will be allowed (map lookup of substring matches
 *              in gdbm, ldap(!), math(?) and so on maps 'a la sendmail'.
 *      -       subroutine invocation will make it possible to rewrite a
 *              submatch in terms of the output of another rewriteContext
 *
 *      Old syntax:
 *
 *              '\' {0-9} [ '{' <name> [ '(' <args> ')' ] '}' ]
 *
 *              where <name> is the name of a built-in map, and
 *              <args> are optional arguments to the map, if
 *              the map <name> requires them.
 *              The following experimental maps have been implemented:
 *
 *      \n{xpasswd}
 *                      maps the n-th substring match as uid to 
 *                      the gecos field in /etc/passwd;
 *
 *      \n{xfile(/absolute/path)}
 *                      maps the n-th substring match 
 *                      to a 'key value' style plain text file.
 *
 *      \n{xldap(ldap://url/with?%0?in?filter)
 *                      maps the n-th substring match to an
 *                      attribute retrieved by means of an LDAP
 *                      url with substitution of %0 in the filter
 *                      (NOT IMPL.)
 *
 *      New scheme:
 *
 *      -       everything starting with '\' requires substitution;
 *      -       the only obvious exception is '\\', which is left as is;
 *      -       the basic substitution is '\d', where 'd' is a digit;
 *              0 means the whole string, while 1-9 is a submatch;
 *      -       in the outdated schema, the digit may be optionally
 *              followed by a '{', which means pipe the submatch into
 *              the map described by the string up to the following '}';
 *      -       the output of the map is used instead of the submatch;
 *      -       in the new schema, a '\' followed by a '{' invokes an
 *              advanced substitution scheme. The pattern is:
 *
 *              '\' '{' [{ <op> }] <name> '(' <substitution schema> ')' '}'
 *
 *              where <name> must be a legal name for the map, i.e.
 *              
 *              <name> ::= [a-z][a-z0-9]* (case insensitive)
 *              <op> ::= '>' '|' '&' '&&' '*' '**' '$'
 *
 *              and <substitution schema> must be a legal substitution
 *              schema, with no limits on the nesting level.
 *              The operators are:
 *              >       sub context invocation; <name> must be a legal,
 *                      already defined rewrite context name
 *              |       external command invocation; <name> must refer
 *                      to a legal, already defined command name (NOT IMPL.)
 *              &       variable assignment; <name> defines a variable
 *                      in the running operation structure which can be
 *                      dereferenced later (NOT IMPL.)
 *              *       variable dereferencing; <name> must refer to a
 *                      variable that is defined and assigned for the
 *                      running operation (NOT IMPL.)
 *              $       parameter dereferencing; <name> must refer to
 *                      an existing parameter; the idea is to make
 *                      some run-time parameters set by the system
 *                      available to the rewrite engine, as the client
 *                      host name, the bind dn if any, constant
 *                      parameters initialized at config time, and so
 *                      on (NOT IMPL.)
 *
 *      Note: as the slapd parsing routines escape backslashes ('\'),
 *      a double backslash is required inside substitution patterns.
 *      To overcome the resulting heavy notation, the substitution escaping
 *      has been delegated to the '%' symbol, which should be used 
 *      instead of '\' in string substitution patterns. The symbol can
 *      be altered at will by redefining the related macro in "rewrite-int.h".
 *      In the current snapshot, all the '\' on the left side of each rule
 *      (the regex pattern) must be converted in '\\'; all the '\' on the
 *      right side of the rule (the substitution pattern) must be turned
 *      into '%'. In the following examples, the original (more readable)
 *      syntax is used; however, in the servers/slapd/back-ldap/slapd.conf
 *      example file, the working syntax is used.
 *
 *
 *
 * Rewrite context:
 *
 *      a rewrite context is a set of rules which are applied in sequence.
 *      The basic idea is to have an application initialize a rewrite
 *      engine (think of Apache's mod_rewrite ...) with a set of rewrite
 *      contexts; when string rewriting is required, one invokes the
 *      appropriate rewrite context with the input string and obtains the
 *      newly rewritten one if no errors occur.
 *      
 *      An interesting application, in back-ldap or in slapd itself,
 *      could associate each basic server operation to a rewrite context
 *      (most of them possibly aliasing the default one). Then, DN rewriting
 +      could take place at any invocation of a backend operation.
 *
 *      client -> server:
 *              default         if defined and no specific context is available
 *              bindDn          bind
 *              searchBase      search
 *              searchFilter    search
 *              compareDn       compare
 *              addDn           add
 *              modifyDn        modify
 *              modrDn          modrdn
 *              newSuperiorDn   modrdn
 *              deleteDn        delete
 *
 *      server -> client:
 *              searchResult    search (only if defined; no default)
 *
 *
 * Configuration syntax:
 *
 *              Basics:
 *
 *      rewriteEngine   { on | off }
 *
 *      rewriteContext  <context name> [ alias <aliased context name> ]
 *
 *      rewriteRule     <regex pattern> <substitution pattern> [ <flags> ]
 *
 *
 *              Additional:
 *
 *      rewriteMap      <map name> <map type> [ <map attrs> ]
 *
 *      rewriteParam    <param name> <param value>
 *
 *      rewriteMaxPasses <number of passes>
 *
 *
 *
 *      rewriteEngine:
 *
 *      if 'on', the requested rewriting is performed; if 'off', no
 *      rewriting takes place (an easy way to stop rewriting without
 *      altering too much the configuration file)
 *
 *      rewriteContext:
 *
 *      <context name> is the name that identifies the context, i.e.
 *      the name used by the application to refer to the set of rules
 *      it contains. It is used also to reference sub contexts in
 *      string rewriting. A context may aliase another one. In this
 *      case the alias context contains no rule, and any reference to
 *      it will result in accessing the aliased one.
 *
 *      rewriteRule:
 *
 *      determines how a tring can be rewritten if a pattern is matched.
 *      Examples are reported below.
 *
 *      rewriteMap:
 *
 *      allows to define a map that transforms substring rewriting into
 *      something else. The map is referenced inside the substitution
 *      pattern of a rule.
 *
 *      rewriteParam:
 *
 *      sets a value with global scope, that can be dereferenced by the
 *      command '\{$paramName}'.
 *
 *      rewriteMaxPasses:
 *
 *      sets the maximum number of total rewriting passes taht can be
 *      performed in a signle rewriting operation (to avoid loops).
 *
 *
 * Configuration examples:
 *
 *      # set to 'off' to disable rewriting
 *
 *      rewriteEngine   on
 *
 *
 *      # everything defined here goes into the 'default' context
 *      # this rule changes the naming context of anything sent to
 *      # 'dc=home,dc=net' to 'dc=OpenLDAP, dc=org'
 *
 *      rewriteRule     "(.*)dc=home,[ ]?dc=net" "\1dc=OpenLDAP, dc=org" ":"
 *
 *
 *      # start a new context (ends input of the previous one)
 *      # this rule adds blancs between dn parts if not present.
 *
 *      rewriteContext  addBlancs
 *      rewriteRule     "(.*),([^ ].*)" "\1, \2"
 *
 *
 *      # this one eats blancs
 *
 *      rewriteContext  eatBlancs
 *      rewriteRule     "(.*),[ ](.*)" "\1,\2"
 *
 *
 *      # here control goes back to the default rewrite context; rules are
 *      # appended to the existing ones.
 *      # anything that gets here is piped into rule 'addBlancs'
 *
 *      rewriteContext  default
 *      rewriteRule     ".*" "\{>addBlancs(\0)}" ":"
 *
 *
 *      # anything with 'uid=username' gets looked up in /etc/passwd for
 *      # gecos (I know it's nearly useless, but it is there just to
 *      # test something fancy!). Note the 'I' flag that leaves
 *      # 'uid=username' in place if 'username' does not have a valid
 *      # account. Note also the ':' that forces the rule to be processed
 *      # exactly once.
 *
 *      rewriteContext  uid2Gecos
 *      rewriteRule     "(.*)uid=([a-z0-9]+),(.+)" "\1cn=\2{xpasswd},\3" "I:"
 *
 *
 *      # finally, in case of bind, if one uses a 'uid=username' dn,
 *      # it is rewritten in 'cn=name surname' if possible.
 *
 *      rewriteContext  bindDn
 *      rewriteRule     ".*" "\{>addBlancs(\{>uid2Gecos(\0)})}" ":"
 *
 *
 *      # the search base is rewritten according to 'default' rules
 *
 *      rewriteContext  searchBase alias default
 *
 *
 *      # search results with OpenLDAP dn are rewritten back with
 *      # 'dc=home,dc=net' naming context, with spaces eaten.
 *
 *      rewriteContext  searchResult
 *      rewriteRule     "(.*[^ ]?)[ ]?dc=OpenLDAP,[ ]?dc=org" 
 *              "\{>eatBlancs(\1)}dc=home,dc=net" ":"
 *
 *      # bind with email instead of full dn: we first need an ldap map
 *      # that turns attributes into a dn (the filter is provided by the
 *      # substitution string):
 *
 *      rewriteMap      ldap attr2dn "ldap://host/dc=my,dc=org?dn?sub"
 *      
 *      # then we need to detect emails; note that the rule in case of match
 *      # stops rewriting; in case of error, it is ignored.
 *      # In case we are mapping virtual to real naming contexts, we also
 *      # need to rewrite regular dns, because the definition of a bindDn
 *      # rewrite context overrides the default definition.
 *
 *      rewriteContext bindDn
 *      rewriteRule     "(mail=[^,]+@[^,]+)" "\{attr2dn(\1)}" "@I"
 *
 *      # This is a rather sophisticate example. It massages a search filter
 *      # in case who performs the search has administrative privileges.
 *      # First we need to keep track of the bind dn of the incoming request:
 *
 *      rewriteContext  bindDn
 *      rewriteRule     ".+" "\{**&binddn(\0)}" ":"
 *
 *      # a search filter containing 'uid=' is rewritten only if an
 *      # appropriate dn is bound.
 *      # to do this, in the first rule the bound dn is dereferenced, while
 *      # the filter is decomposed in a prefix, the argument of the 'uid=',
 *      # and in a suffix. A tag '<>' is appended to the dn. If the dn 
 *      # refers to an entry in the 'ou=admin' subtree, the filter is
 *      # rewritten OR-ing the 'uid=<arg>' with 'cn=<arg>'; otherwise
 *      # it is left as is. This could be useful, for instance, to allow
 *      # apache's auth_ldap-1.4 module to authenticate users with both
 *      # 'uid' and 'cn', but only if the request comes from a possible
 *      # 'dn: cn=Web auth, ou=admin, dc=home, dc=net' user.
 *
 *      rewriteContext  searchFilter
 *      rewriteRule     "(.*\()uid=([a-z0-9_]+)(\).*)"
 *              "\{**binddn}<>\{&prefix(\1)}\{&arg(\2)}\{&suffix(\3)}" ":I"
 *      rewriteRule     "[^,]+,[ ]?ou=admin,[ ]?dc=home,[ ]?dc=net"
 *              "\{*prefix}|(uid=\{*arg})(cn=\{*arg})\{*suffix}" "@I"
 *      rewriteRule     ".*<>" "\{*prefix}uid=\{*arg}\{*suffix}"
 *
 *
 * LDAP Proxy resolution (a possible evolution of the back-ldap):
 *
 *      in case the rewritten dn is an LDAP URL, the operation is initiated
 *      towards the host[:port] indicated in the url, if it does not refer
 *      to the local server.
 *
 *      e.g.:
 *
 *      rewriteRule     '^cn=root,.*'   '\0'                            'G{3}'
 *      rewriteRule     '^cn=[a-l].*'   'ldap://ldap1.my.org/\0'        '@'
 *      rewriteRule     '^cn=[m-z].*'   'ldap://ldap2.my.org/\0'        '@'
 *      rewriteRule     '.*'            'ldap://ldap3.my.org/\0'        '@'
 *
 *      (rule 1 is simply there to illustrate the 'G{n}' action; it could
 *      have been written:
 *
 *      rewriteRule     '^cn=root,.*'   'ldap://ldap3.my.org/\0'        '@'
 *
 *      with the advantage of saving one rewrite pass ...)
 */