home *** CD-ROM | disk | FTP | other *** search
/ PC Online 1999 April / PCO0499.ISO / filesbbs / os2 / apach134.arj / APACH134.ZIP / src / modules / standard / mod_speling.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-01-01  |  18.6 KB  |  541 lines
  1. #define WANT_BASENAME_MATCH
  2. /* ====================================================================
  3.  * Copyright (c) 1996-1999 The Apache Group.  All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  *
  9.  * 1. Redistributions of source code must retain the above copyright
  10.  *    notice, this list of conditions and the following disclaimer.
  11.  *
  12.  * 2. Redistributions in binary form must reproduce the above copyright
  13.  *    notice, this list of conditions and the following disclaimer in
  14.  *    the documentation and/or other materials provided with the
  15.  *    distribution.
  16.  *
  17.  * 3. All advertising materials mentioning features or use of this
  18.  *    software must display the following acknowledgment:
  19.  *    "This product includes software developed by the Apache Group
  20.  *    for use in the Apache HTTP server project (http://www.apache.org/)."
  21.  *
  22.  * 4. The names "Apache Server" and "Apache Group" must not be used to
  23.  *    endorse or promote products derived from this software without
  24.  *    prior written permission. For written permission, please contact
  25.  *    apache@apache.org.
  26.  *
  27.  * 5. Products derived from this software may not be called "Apache"
  28.  *    nor may "Apache" appear in their names without prior written
  29.  *    permission of the Apache Group.
  30.  *
  31.  * 6. Redistributions of any form whatsoever must retain the following
  32.  *    acknowledgment:
  33.  *    "This product includes software developed by the Apache Group
  34.  *    for use in the Apache HTTP server project (http://www.apache.org/)."
  35.  *
  36.  * THIS SOFTWARE IS PROVIDED BY THE APACHE GROUP ``AS IS'' AND ANY
  37.  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  38.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  39.  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE APACHE GROUP OR
  40.  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  41.  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  42.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  43.  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  44.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  45.  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  46.  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  47.  * OF THE POSSIBILITY OF SUCH DAMAGE.
  48.  * ====================================================================
  49.  *
  50.  * This software consists of voluntary contributions made by many
  51.  * individuals on behalf of the Apache Group and was originally based
  52.  * on public domain software written at the National Center for
  53.  * Supercomputing Applications, University of Illinois, Urbana-Champaign.
  54.  * For more information on the Apache Group and the Apache HTTP server
  55.  * project, please see <http://www.apache.org/>.
  56.  *
  57.  */
  58.  
  59. #include "httpd.h"
  60. #include "http_core.h"
  61. #include "http_config.h"
  62. #include "http_log.h"
  63.  
  64. /* mod_speling.c - by Alexei Kosut <akosut@organic.com> June, 1996
  65.  *
  66.  * This module is transparent, and simple. It attempts to correct
  67.  * misspellings of URLs that users might have entered, namely by checking
  68.  * capitalizations. If it finds a match, it sends a redirect.
  69.  *
  70.  * 08-Aug-1997 <Martin.Kraemer@Mch.SNI.De>
  71.  * o Upgraded module interface to apache_1.3a2-dev API (more NULL's in
  72.  *   speling_module).
  73.  * o Integrated tcsh's "spelling correction" routine which allows one
  74.  *   misspelling (character insertion/omission/typo/transposition).
  75.  *   Rewrote it to ignore case as well. This ought to catch the majority
  76.  *   of misspelled requests.
  77.  * o Commented out the second pass where files' suffixes are stripped.
  78.  *   Given the better hit rate of the first pass, this rather ugly
  79.  *   (request index.html, receive index.db ?!?!) solution can be
  80.  *   omitted.
  81.  * o wrote a "kind of" html page for mod_speling
  82.  *
  83.  * Activate it with "CheckSpelling On"
  84.  */
  85.  
  86. MODULE_VAR_EXPORT module speling_module;
  87.  
  88. typedef struct {
  89.     int enabled;
  90. } spconfig;
  91.  
  92. /*
  93.  * Create a configuration specific to this module for a server or directory
  94.  * location, and fill it with the default settings.
  95.  *
  96.  * The API says that in the absence of a merge function, the record for the
  97.  * closest ancestor is used exclusively.  That's what we want, so we don't
  98.  * bother to have such a function.
  99.  */
  100.  
  101. static void *mkconfig(pool *p)
  102. {
  103.     spconfig *cfg = ap_pcalloc(p, sizeof(spconfig));
  104.  
  105.     cfg->enabled = 0;
  106.     return cfg;
  107. }
  108.  
  109. /*
  110.  * Respond to a callback to create configuration record for a server or
  111.  * vhost environment.
  112.  */
  113. static void *create_mconfig_for_server(pool *p, server_rec *s)
  114. {
  115.     return mkconfig(p);
  116. }
  117.  
  118. /*
  119.  * Respond to a callback to create a config record for a specific directory.
  120.  */
  121. static void *create_mconfig_for_directory(pool *p, char *dir)
  122. {
  123.     return mkconfig(p);
  124. }
  125.  
  126. /*
  127.  * Handler for the CheckSpelling directive, which is FLAG.
  128.  */
  129. static const char *set_speling(cmd_parms *cmd, void *mconfig, int arg)
  130. {
  131.     spconfig *cfg = (spconfig *) mconfig;
  132.  
  133.     cfg->enabled = arg;
  134.     return NULL;
  135. }
  136.  
  137. /*
  138.  * Define the directives specific to this module.  This structure is referenced
  139.  * later by the 'module' structure.
  140.  */
  141. static const command_rec speling_cmds[] =
  142. {
  143.     { "CheckSpelling", set_speling, NULL, OR_OPTIONS, FLAG,
  144.       "whether or not to fix miscapitalized/misspelled requests" },
  145.     { NULL }
  146. };
  147.  
  148. typedef enum {
  149.     SP_IDENTICAL = 0,
  150.     SP_MISCAPITALIZED = 1,
  151.     SP_TRANSPOSITION = 2,
  152.     SP_MISSINGCHAR = 3,
  153.     SP_EXTRACHAR = 4,
  154.     SP_SIMPLETYPO = 5,
  155.     SP_VERYDIFFERENT = 6
  156. } sp_reason;
  157.  
  158. static const char *sp_reason_str[] =
  159. {
  160.     "identical",
  161.     "miscapitalized",
  162.     "transposed characters",
  163.     "character missing",
  164.     "extra character",
  165.     "mistyped character",
  166.     "common basename",
  167. };
  168.  
  169. typedef struct {
  170.     const char *name;
  171.     sp_reason quality;
  172. } misspelled_file;
  173.  
  174. /*
  175.  * spdist() is taken from Kernighan & Pike,
  176.  *  _The_UNIX_Programming_Environment_
  177.  * and adapted somewhat to correspond better to psychological reality.
  178.  * (Note the changes to the return values)
  179.  *
  180.  * According to Pollock and Zamora, CACM April 1984 (V. 27, No. 4),
  181.  * page 363, the correct order for this is:
  182.  * OMISSION = TRANSPOSITION > INSERTION > SUBSTITUTION
  183.  * thus, it was exactly backwards in the old version. -- PWP
  184.  *
  185.  * This routine was taken out of tcsh's spelling correction code
  186.  * (tcsh-6.07.04) and re-converted to apache data types ("char" type
  187.  * instead of tcsh's NLS'ed "Char"). Plus it now ignores the case
  188.  * during comparisons, so is a "approximate strcasecmp()".
  189.  * NOTE that is still allows only _one_ real "typo",
  190.  * it does NOT try to correct multiple errors.
  191.  */
  192.  
  193. static sp_reason spdist(const char *s, const char *t)
  194. {
  195.     for (; ap_tolower(*s) == ap_tolower(*t); t++, s++) {
  196.         if (*t == '\0') {
  197.             return SP_MISCAPITALIZED;   /* exact match (sans case) */
  198.     }
  199.     }
  200.     if (*s) {
  201.         if (*t) {
  202.             if (s[1] && t[1] && ap_tolower(*s) == ap_tolower(t[1])
  203.         && ap_tolower(*t) == ap_tolower(s[1])
  204.         && strcasecmp(s + 2, t + 2) == 0) {
  205.                 return SP_TRANSPOSITION;        /* transposition */
  206.         }
  207.             if (strcasecmp(s + 1, t + 1) == 0) {
  208.                 return SP_SIMPLETYPO;   /* 1 char mismatch */
  209.         }
  210.         }
  211.         if (strcasecmp(s + 1, t) == 0) {
  212.             return SP_EXTRACHAR;        /* extra character */
  213.     }
  214.     }
  215.     if (*t && strcasecmp(s, t + 1) == 0) {
  216.         return SP_MISSINGCHAR;  /* missing character */
  217.     }
  218.     return SP_VERYDIFFERENT;    /* distance too large to fix. */
  219. }
  220.  
  221. static int sort_by_quality(const void *left, const void *rite)
  222. {
  223.     return (int) (((misspelled_file *) left)->quality)
  224.         - (int) (((misspelled_file *) rite)->quality);
  225. }
  226.  
  227. static int check_speling(request_rec *r)
  228. {
  229.     spconfig *cfg;
  230.     char *good, *bad, *postgood, *url;
  231.     int filoc, dotloc, urlen, pglen;
  232.     DIR *dirp;
  233.     struct DIR_TYPE *dir_entry;
  234.     array_header *candidates = NULL;
  235.  
  236.     cfg = ap_get_module_config(r->per_dir_config, &speling_module);
  237.     if (!cfg->enabled) {
  238.         return DECLINED;
  239.     }
  240.  
  241.     /* We only want to worry about GETs */
  242.     if (r->method_number != M_GET) {
  243.         return DECLINED;
  244.     }
  245.  
  246.     /* We've already got a file of some kind or another */
  247.     if (r->proxyreq || (r->finfo.st_mode != 0)) {
  248.         return DECLINED;
  249.     }
  250.  
  251.     /* This is a sub request - don't mess with it */
  252.     if (r->main) {
  253.         return DECLINED;
  254.     }
  255.  
  256.     /*
  257.      * The request should end up looking like this:
  258.      * r->uri: /correct-url/mispelling/more
  259.      * r->filename: /correct-file/mispelling r->path_info: /more
  260.      *
  261.      * So we do this in steps. First break r->filename into two pieces
  262.      */
  263.  
  264.     filoc = ap_rind(r->filename, '/');
  265.     /*
  266.      * Don't do anything if the request doesn't contain a slash, or
  267.      * requests "/" 
  268.      */
  269.     if (filoc == -1 || strcmp(r->uri, "/") == 0) {
  270.         return DECLINED;
  271.     }
  272.  
  273.     /* good = /correct-file */
  274.     good = ap_pstrndup(r->pool, r->filename, filoc);
  275.     /* bad = mispelling */
  276.     bad = ap_pstrdup(r->pool, r->filename + filoc + 1);
  277.     /* postgood = mispelling/more */
  278.     postgood = ap_pstrcat(r->pool, bad, r->path_info, NULL);
  279.  
  280.     urlen = strlen(r->uri);
  281.     pglen = strlen(postgood);
  282.  
  283.     /* Check to see if the URL pieces add up */
  284.     if (strcmp(postgood, r->uri + (urlen - pglen))) {
  285.         return DECLINED;
  286.     }
  287.  
  288.     /* url = /correct-url */
  289.     url = ap_pstrndup(r->pool, r->uri, (urlen - pglen));
  290.  
  291.     /* Now open the directory and do ourselves a check... */
  292.     dirp = ap_popendir(r->pool, good);
  293.     if (dirp == NULL) {          /* Oops, not a directory... */
  294.         return DECLINED;
  295.     }
  296.  
  297.     candidates = ap_make_array(r->pool, 2, sizeof(misspelled_file));
  298.  
  299.     dotloc = ap_ind(bad, '.');
  300.     if (dotloc == -1) {
  301.         dotloc = strlen(bad);
  302.     }
  303.  
  304.     while ((dir_entry = readdir(dirp)) != NULL) {
  305.         sp_reason q;
  306.  
  307.         /*
  308.          * If we end up with a "fixed" URL which is identical to the
  309.          * requested one, we must have found a broken symlink or some such.
  310.          * Do _not_ try to redirect this, it causes a loop!
  311.          */
  312.         if (strcmp(bad, dir_entry->d_name) == 0) {
  313.             ap_pclosedir(r->pool, dirp);
  314.             return OK;
  315.         }
  316.         /*
  317.          * miscapitalization errors are checked first (like, e.g., lower case
  318.          * file, upper case request)
  319.          */
  320.         else if (strcasecmp(bad, dir_entry->d_name) == 0) {
  321.             misspelled_file *sp_new;
  322.  
  323.         sp_new = (misspelled_file *) ap_push_array(candidates);
  324.             sp_new->name = ap_pstrdup(r->pool, dir_entry->d_name);
  325.             sp_new->quality = SP_MISCAPITALIZED;
  326.         }
  327.         /*
  328.          * simple typing errors are checked next (like, e.g.,
  329.          * missing/extra/transposed char)
  330.          */
  331.         else if ((q = spdist(bad, dir_entry->d_name)) != SP_VERYDIFFERENT) {
  332.             misspelled_file *sp_new;
  333.  
  334.         sp_new = (misspelled_file *) ap_push_array(candidates);
  335.             sp_new->name = ap_pstrdup(r->pool, dir_entry->d_name);
  336.             sp_new->quality = q;
  337.         }
  338.         /*
  339.      * The spdist() should have found the majority of the misspelled
  340.      * requests.  It is of questionable use to continue looking for
  341.      * files with the same base name, but potentially of totally wrong
  342.      * type (index.html <-> index.db).
  343.      * I would propose to not set the WANT_BASENAME_MATCH define.
  344.          *      08-Aug-1997 <Martin.Kraemer@Mch.SNI.De>
  345.          *
  346.          * However, Alexei replied giving some reasons to add it anyway:
  347.          * > Oh, by the way, I remembered why having the
  348.          * > extension-stripping-and-matching stuff is a good idea:
  349.          * >
  350.          * > If you're using MultiViews, and have a file named foobar.html,
  351.      * > which you refer to as "foobar", and someone tried to access
  352.      * > "Foobar", mod_speling won't find it, because it won't find
  353.      * > anything matching that spelling. With the extension-munging,
  354.      * > it would locate "foobar.html". Not perfect, but I ran into
  355.      * > that problem when I first wrote the module.
  356.      */
  357.         else {
  358. #ifdef WANT_BASENAME_MATCH
  359.             /*
  360.              * Okay... we didn't find anything. Now we take out the hard-core
  361.              * power tools. There are several cases here. Someone might have
  362.              * entered a wrong extension (.htm instead of .html or vice
  363.              * versa) or the document could be negotiated. At any rate, now
  364.              * we just compare stuff before the first dot. If it matches, we
  365.              * figure we got us a match. This can result in wrong things if
  366.              * there are files of different content types but the same prefix
  367.              * (e.g. foo.gif and foo.html) This code will pick the first one
  368.              * it finds. Better than a Not Found, though.
  369.              */
  370.             int entloc = ap_ind(dir_entry->d_name, '.');
  371.             if (entloc == -1) {
  372.                 entloc = strlen(dir_entry->d_name);
  373.         }
  374.  
  375.             if ((dotloc == entloc)
  376.                 && !strncasecmp(bad, dir_entry->d_name, dotloc)) {
  377.                 misspelled_file *sp_new;
  378.  
  379.         sp_new = (misspelled_file *) ap_push_array(candidates);
  380.                 sp_new->name = ap_pstrdup(r->pool, dir_entry->d_name);
  381.                 sp_new->quality = SP_VERYDIFFERENT;
  382.             }
  383. #endif
  384.         }
  385.     }
  386.     ap_pclosedir(r->pool, dirp);
  387.  
  388.     if (candidates->nelts != 0) {
  389.         /* Wow... we found us a mispelling. Construct a fixed url */
  390.         char *nuri;
  391.     const char *ref;
  392.         misspelled_file *variant = (misspelled_file *) candidates->elts;
  393.         int i;
  394.  
  395.         ref = ap_table_get(r->headers_in, "Referer");
  396.  
  397.         qsort((void *) candidates->elts, candidates->nelts,
  398.               sizeof(misspelled_file), sort_by_quality);
  399.  
  400.         /*
  401.          * Conditions for immediate redirection: 
  402.          *     a) the first candidate was not found by stripping the suffix 
  403.          * AND b) there exists only one candidate OR the best match is not
  404.      *        ambiguous
  405.          * then return a redirection right away.
  406.          */
  407.         if (variant[0].quality != SP_VERYDIFFERENT
  408.         && (candidates->nelts == 1
  409.         || variant[0].quality != variant[1].quality)) {
  410.  
  411.             nuri = ap_pstrcat(r->pool, url, variant[0].name, r->path_info,
  412.                   r->parsed_uri.query ? "?" : "",
  413.                   r->parsed_uri.query ? r->parsed_uri.query : "",
  414.                   NULL);
  415.  
  416.             ap_table_setn(r->headers_out, "Location",
  417.               ap_construct_url(r->pool, nuri, r));
  418.  
  419.             ap_log_rerror(APLOG_MARK, APLOG_NOERRNO | APLOG_INFO, r,
  420.              ref ? "Fixed spelling: %s to %s from %s"
  421.                  : "Fixed spelling: %s to %s",
  422.              r->uri, nuri, ref);
  423.  
  424.             return HTTP_MOVED_PERMANENTLY;
  425.         }
  426.         /*
  427.          * Otherwise, a "[300] Multiple Choices" list with the variants is
  428.          * returned.
  429.          */
  430.         else {
  431.             char *t;
  432.             pool *p;
  433.             table *notes;
  434.  
  435.             if (r->main == NULL) {
  436.                 p = r->pool;
  437.                 notes = r->notes;
  438.             }
  439.             else {
  440.                 p = r->main->pool;
  441.                 notes = r->main->notes;
  442.             }
  443.  
  444.             /* Generate the response text. */
  445.             /*
  446.          * Since the text is expanded by repeated calls of
  447.              * t = pstrcat(p, t, ".."), we can avoid a little waste
  448.              * of memory by adding the header AFTER building the list.
  449.              * XXX: FIXME: find a way to build a string concatenation
  450.              *             without repeatedly requesting new memory
  451.              * XXX: FIXME: Limit the list to a maximum number of entries
  452.              */
  453.             t = "";
  454.  
  455.             for (i = 0; i < candidates->nelts; ++i) {
  456.         char *vuri;
  457.         const char *reason;
  458.  
  459.         reason = sp_reason_str[(int) (variant[i].quality)];
  460.                 /* The format isn't very neat... */
  461.         vuri = ap_pstrcat(p, url, variant[i].name, r->path_info,
  462.                   (r->parsed_uri.query != NULL) ? "?" : "",
  463.                   (r->parsed_uri.query != NULL)
  464.                       ? r->parsed_uri.query : "",
  465.                   NULL);
  466.         ap_table_mergen(r->subprocess_env, "VARIANTS",
  467.                 ap_pstrcat(p, "\"", vuri, "\";\"",
  468.                        reason, "\"", NULL));
  469.                 t = ap_pstrcat(p, t, "<li><a href=\"", vuri,
  470.                    "\">", vuri, "</a> (", reason, ")\n", NULL);
  471.  
  472.                 /*
  473.                  * when we have printed the "close matches" and there are
  474.                  * more "distant matches" (matched by stripping the suffix),
  475.                  * then we insert an additional separator text to suggest
  476.                  * that the user LOOK CLOSELY whether these are really the
  477.                  * files she wanted.
  478.                  */
  479.                 if (i > 0 && i < candidates->nelts - 1
  480.                     && variant[i].quality != SP_VERYDIFFERENT
  481.                     && variant[i + 1].quality == SP_VERYDIFFERENT) {
  482.                     t = ap_pstrcat(p, t, 
  483.                    "</ul>\nFurthermore, the following related "
  484.                    "documents were found:\n<ul>\n", NULL);
  485.                 }
  486.             }
  487.             t = ap_pstrcat(p, "The document name you requested (<code>",
  488.                r->uri,
  489.                "</code>) could not be found on this server.\n"
  490.                "However, we found documents with names similar "
  491.                "to the one you requested.<p>"
  492.                "Available documents:\n<ul>\n", t, "</ul>\n", NULL);
  493.  
  494.             /* If we know there was a referring page, add a note: */
  495.             if (ref != NULL) {
  496.                 t = ap_pstrcat(p, t,
  497.                    "Please consider informing the owner of the "
  498.                    "<a href=\"", ref, 
  499.                    "\">referring page</a> "
  500.                    "about the broken link.\n",
  501.                    NULL);
  502.         }
  503.  
  504.             /* Pass our table to http_protocol.c (see mod_negotiation): */
  505.             ap_table_setn(notes, "variant-list", t);
  506.  
  507.             ap_log_rerror(APLOG_MARK, APLOG_NOERRNO | APLOG_INFO, r,
  508.              ref ? "Spelling fix: %s: %d candidates from %s"
  509.                  : "Spelling fix: %s: %d candidates",
  510.              r->uri, candidates->nelts, ref);
  511.  
  512.             return HTTP_MULTIPLE_CHOICES;
  513.         }
  514.     }
  515.  
  516.     return OK;
  517. }
  518.  
  519. module MODULE_VAR_EXPORT speling_module =
  520. {
  521.     STANDARD_MODULE_STUFF,
  522.     NULL,                       /* initializer */
  523.     create_mconfig_for_directory,  /* create per-dir config */
  524.     NULL,                       /* merge per-dir config */
  525.     create_mconfig_for_server,  /* server config */
  526.     NULL,                       /* merge server config */
  527.     speling_cmds,               /* command table */
  528.     NULL,                       /* handlers */
  529.     NULL,                       /* filename translation */
  530.     NULL,                       /* check_user_id */
  531.     NULL,                       /* check auth */
  532.     NULL,                       /* check access */
  533.     NULL,                       /* type_checker */
  534.     check_speling,              /* fixups */
  535.     NULL,                       /* logger */
  536.     NULL,                       /* header parser */
  537.     NULL,                       /* child_init */
  538.     NULL,                       /* child_exit */
  539.     NULL                        /* post read-request */
  540. };
  541.