sjero.net Git - wget/blob - src/recur.c

   1 /* Handling of recursive HTTP retrieving.
   2    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003,
   3    2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
   4
   5 This file is part of GNU Wget.
   6
   7 GNU Wget is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3 of the License, or
  10  (at your option) any later version.
  11
  12 GNU Wget is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Wget.  If not, see <http://www.gnu.org/licenses/>.
  19
  20 Additional permission under GNU GPL version 3 section 7
  21
  22 If you modify this program, or any covered work, by linking or
  23 combining it with the OpenSSL project's OpenSSL library (or a
  24 modified version of that library), containing parts covered by the
  25 terms of the OpenSSL or SSLeay licenses, the Free Software Foundation
  26 grants you additional permission to convey the resulting work.
  27 Corresponding Source for a non-source form of such a combination
  28 shall include the source code for the parts of OpenSSL used as well
  29 as that of the covered work.  */
  30
  31 #include "wget.h"
  32
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35 #include <string.h>
  36 #ifdef HAVE_UNISTD_H
  37 # include <unistd.h>
  38 #endif /* HAVE_UNISTD_H */
  39 #include <errno.h>
  40 #include <assert.h>
  41
  42 #include "url.h"
  43 #include "recur.h"
  44 #include "utils.h"
  45 #include "retr.h"
  46 #include "ftp.h"
  47 #include "host.h"
  48 #include "hash.h"
  49 #include "res.h"
  50 #include "convert.h"
  51 #include "html-url.h"
  52 #include "css-url.h"
  53 #include "spider.h"
  54 #include "iri.h"
  55 \f
  56 /* Functions for maintaining the URL queue.  */
  57
  58 struct queue_element {
  59   const char *url;              /* the URL to download */
  60   const char *referer;          /* the referring document */
  61   int depth;                    /* the depth */
  62   bool html_allowed;            /* whether the document is allowed to
  63                                    be treated as HTML. */
  64   char *remote_encoding;
  65   bool css_allowed;             /* whether the document is allowed to
  66                                    be treated as CSS. */
  67   struct queue_element *next;   /* next element in queue */
  68 };
  69
  70 struct url_queue {
  71   struct queue_element *head;
  72   struct queue_element *tail;
  73   int count, maxcount;
  74 };
  75
  76 /* Create a URL queue. */
  77
  78 static struct url_queue *
  79 url_queue_new (void)
  80 {
  81   struct url_queue *queue = xnew0 (struct url_queue);
  82   return queue;
  83 }
  84
  85 /* Delete a URL queue. */
  86
  87 static void
  88 url_queue_delete (struct url_queue *queue)
  89 {
  90   xfree (queue);
  91 }
  92
  93 /* Enqueue a URL in the queue.  The queue is FIFO: the items will be
  94    retrieved ("dequeued") from the queue in the order they were placed
  95    into it.  */
  96
  97 static void
  98 url_enqueue (struct url_queue *queue,
  99              const char *url, const char *referer, int depth,
 100              bool html_allowed, bool css_allowed)
 101 {
 102   struct queue_element *qel = xnew (struct queue_element);
 103   char *charset = get_current_charset ();
 104   qel->url = url;
 105   qel->referer = referer;
 106   qel->depth = depth;
 107   qel->html_allowed = html_allowed;
 108   qel->css_allowed = css_allowed;
 109   qel->next = NULL;
 110
 111   if (charset)
 112     qel->remote_encoding = xstrdup (charset);
 113   else
 114     qel->remote_encoding = NULL;
 115
 116   ++queue->count;
 117   if (queue->count > queue->maxcount)
 118     queue->maxcount = queue->count;
 119
 120   DEBUGP (("Enqueuing %s at depth %d\n", url, depth));
 121   DEBUGP (("Queue count %d, maxcount %d.\n", queue->count, queue->maxcount));
 122
 123   /*printf ("[Enqueuing %s with %s\n", url, qel->remote_encoding);*/
 124
 125   if (queue->tail)
 126     queue->tail->next = qel;
 127   queue->tail = qel;
 128
 129   if (!queue->head)
 130     queue->head = queue->tail;
 131 }
 132
 133 /* Take a URL out of the queue.  Return true if this operation
 134    succeeded, or false if the queue is empty.  */
 135
 136 static bool
 137 url_dequeue (struct url_queue *queue,
 138              const char **url, const char **referer, int *depth,
 139              bool *html_allowed, bool *css_allowed)
 140 {
 141   struct queue_element *qel = queue->head;
 142
 143   if (!qel)
 144     return false;
 145
 146   queue->head = queue->head->next;
 147   if (!queue->head)
 148     queue->tail = NULL;
 149
 150   set_remote_charset (qel->remote_encoding);
 151   if (qel->remote_encoding)
 152     xfree (qel->remote_encoding);
 153
 154   *url = qel->url;
 155   *referer = qel->referer;
 156   *depth = qel->depth;
 157   *html_allowed = qel->html_allowed;
 158   *css_allowed = qel->css_allowed;
 159
 160   --queue->count;
 161
 162   DEBUGP (("Dequeuing %s at depth %d\n", qel->url, qel->depth));
 163   DEBUGP (("Queue count %d, maxcount %d.\n", queue->count, queue->maxcount));
 164
 165   xfree (qel);
 166   return true;
 167 }
 168 \f
 169 static bool download_child_p (const struct urlpos *, struct url *, int,
 170                               struct url *, struct hash_table *);
 171 static bool descend_redirect_p (const char *, const char *, int,
 172                                 struct url *, struct hash_table *);
 173
 174
 175 /* Retrieve a part of the web beginning with START_URL.  This used to
 176    be called "recursive retrieval", because the old function was
 177    recursive and implemented depth-first search.  retrieve_tree on the
 178    other hand implements breadth-search traversal of the tree, which
 179    results in much nicer ordering of downloads.
 180
 181    The algorithm this function uses is simple:
 182
 183    1. put START_URL in the queue.
 184    2. while there are URLs in the queue:
 185
 186      3. get next URL from the queue.
 187      4. download it.
 188      5. if the URL is HTML and its depth does not exceed maximum depth,
 189         get the list of URLs embedded therein.
 190      6. for each of those URLs do the following:
 191
 192        7. if the URL is not one of those downloaded before, and if it
 193           satisfies the criteria specified by the various command-line
 194           options, add it to the queue. */
 195
 196 uerr_t
 197 retrieve_tree (const char *start_url)
 198 {
 199   uerr_t status = RETROK;
 200
 201   /* The queue of URLs we need to load. */
 202   struct url_queue *queue;
 203
 204   /* The URLs we do not wish to enqueue, because they are already in
 205      the queue, but haven't been downloaded yet.  */
 206   struct hash_table *blacklist;
 207
 208   int up_error_code;
 209   struct url *start_url_parsed;
 210
 211   set_ugly_no_encode (true);
 212   start_url_parsed= url_parse (start_url, &up_error_code);
 213   set_ugly_no_encode (false);
 214   if (!start_url_parsed)
 215     {
 216       logprintf (LOG_NOTQUIET, "%s: %s.\n", start_url,
 217                  url_error (up_error_code));
 218       return URLERROR;
 219     }
 220
 221   queue = url_queue_new ();
 222   blacklist = make_string_hash_table (0);
 223
 224   /* Enqueue the starting URL.  Use start_url_parsed->url rather than
 225      just URL so we enqueue the canonical form of the URL.  */
 226   url_enqueue (queue, xstrdup (start_url_parsed->url), NULL, 0, true, false);
 227   string_set_add (blacklist, start_url_parsed->url);
 228
 229   while (1)
 230     {
 231       bool descend = false;
 232       char *url, *referer, *file = NULL;
 233       int depth;
 234       bool html_allowed, css_allowed;
 235       bool is_css = false;
 236       bool dash_p_leaf_HTML = false;
 237
 238       if (opt.quota && total_downloaded_bytes > opt.quota)
 239         break;
 240       if (status == FWRITEERR)
 241         break;
 242
 243       /* Get the next URL from the queue... */
 244
 245       if (!url_dequeue (queue,
 246                         (const char **)&url, (const char **)&referer,
 247                         &depth, &html_allowed, &css_allowed))
 248         break;
 249
 250       /* ...and download it.  Note that this download is in most cases
 251          unconditional, as download_child_p already makes sure a file
 252          doesn't get enqueued twice -- and yet this check is here, and
 253          not in download_child_p.  This is so that if you run `wget -r
 254          URL1 URL2', and a random URL is encountered once under URL1
 255          and again under URL2, but at a different (possibly smaller)
 256          depth, we want the URL's children to be taken into account
 257          the second time.  */
 258       if (dl_url_file_map && hash_table_contains (dl_url_file_map, url))
 259         {
 260           file = xstrdup (hash_table_get (dl_url_file_map, url));
 261
 262           DEBUGP (("Already downloaded \"%s\", reusing it from \"%s\".\n",
 263                    url, file));
 264
 265           /* this sucks, needs to be combined! */
 266           if (html_allowed
 267               && downloaded_html_set
 268               && string_set_contains (downloaded_html_set, file))
 269             {
 270               descend = true;
 271               is_css = false;
 272             }
 273           if (css_allowed
 274               && downloaded_css_set
 275               && string_set_contains (downloaded_css_set, file))
 276             {
 277               descend = true;
 278               is_css = true;
 279             }
 280         }
 281       else
 282         {
 283           int dt = 0;
 284           char *redirected = NULL;
 285
 286           status = retrieve_url (url, &file, &redirected, referer, &dt, false);
 287
 288           if (html_allowed && file && status == RETROK
 289               && (dt & RETROKF) && (dt & TEXTHTML))
 290             {
 291               descend = true;
 292               is_css = false;
 293             }
 294
 295           /* a little different, css_allowed can override content type
 296              lots of web servers serve css with an incorrect content type
 297           */
 298           if (file && status == RETROK
 299               && (dt & RETROKF) &&
 300               ((dt & TEXTCSS) || css_allowed))
 301             {
 302               descend = true;
 303               is_css = true;
 304             }
 305
 306           if (redirected)
 307             {
 308               /* We have been redirected, possibly to another host, or
 309                  different path, or wherever.  Check whether we really
 310                  want to follow it.  */
 311               if (descend)
 312                 {
 313                   if (!descend_redirect_p (redirected, url, depth,
 314                                            start_url_parsed, blacklist))
 315                     descend = false;
 316                   else
 317                     /* Make sure that the old pre-redirect form gets
 318                        blacklisted. */
 319                     string_set_add (blacklist, url);
 320                 }
 321
 322               xfree (url);
 323               url = redirected;
 324             }
 325         }
 326
 327       if (opt.spider)
 328         {
 329           visited_url (url, referer);
 330         }
 331
 332       if (descend
 333           && depth >= opt.reclevel && opt.reclevel != INFINITE_RECURSION)
 334         {
 335           if (opt.page_requisites
 336               && (depth == opt.reclevel || depth == opt.reclevel + 1))
 337             {
 338               /* When -p is specified, we are allowed to exceed the
 339                  maximum depth, but only for the "inline" links,
 340                  i.e. those that are needed to display the page.
 341                  Originally this could exceed the depth at most by
 342                  one, but we allow one more level so that the leaf
 343                  pages that contain frames can be loaded
 344                  correctly.  */
 345               dash_p_leaf_HTML = true;
 346             }
 347           else
 348             {
 349               /* Either -p wasn't specified or it was and we've
 350                  already spent the two extra (pseudo-)levels that it
 351                  affords us, so we need to bail out. */
 352               DEBUGP (("Not descending further; at depth %d, max. %d.\n",
 353                        depth, opt.reclevel));
 354               descend = false;
 355             }
 356         }
 357
 358       /* If the downloaded document was HTML or CSS, parse it and enqueue the
 359          links it contains. */
 360
 361       if (descend)
 362         {
 363           bool meta_disallow_follow = false;
 364           struct urlpos *children
 365             = is_css ? get_urls_css_file (file, url) :
 366                        get_urls_html (file, url, &meta_disallow_follow);
 367
 368           if (opt.use_robots && meta_disallow_follow)
 369             {
 370               free_urlpos (children);
 371               children = NULL;
 372             }
 373
 374           if (children)
 375             {
 376               struct urlpos *child = children;
 377               set_ugly_no_encode (true);
 378               struct url *url_parsed = url_parse (url, NULL);
 379               set_ugly_no_encode (false);
 380               char *referer_url = url;
 381               bool strip_auth = (url_parsed != NULL
 382                                  && url_parsed->user != NULL);
 383               assert (url_parsed != NULL);
 384
 385               /* Strip auth info if present */
 386               if (strip_auth)
 387                 referer_url = url_string (url_parsed, URL_AUTH_HIDE);
 388
 389               for (; child; child = child->next)
 390                 {
 391                   if (child->ignore_when_downloading)
 392                     continue;
 393                   if (dash_p_leaf_HTML && !child->link_inline_p)
 394                     continue;
 395                   if (download_child_p (child, url_parsed, depth, start_url_parsed,
 396                                         blacklist))
 397                     {
 398                       url_enqueue (queue, xstrdup (child->url->url),
 399                                    xstrdup (referer_url), depth + 1,
 400                                    child->link_expect_html,
 401                                    child->link_expect_css);
 402                       /* We blacklist the URL we have enqueued, because we
 403                          don't want to enqueue (and hence download) the
 404                          same URL twice.  */
 405                       string_set_add (blacklist, child->url->url);
 406                     }
 407                 }
 408
 409               if (strip_auth)
 410                 xfree (referer_url);
 411               url_free (url_parsed);
 412               free_urlpos (children);
 413             }
 414         }
 415
 416       if (file
 417           && (opt.delete_after
 418               || opt.spider /* opt.recursive is implicitely true */
 419               || !acceptable (file)))
 420         {
 421           /* Either --delete-after was specified, or we loaded this
 422              (otherwise unneeded because of --spider or rejected by -R)
 423              HTML file just to harvest its hyperlinks -- in either case,
 424              delete the local file. */
 425           DEBUGP (("Removing file due to %s in recursive_retrieve():\n",
 426                    opt.delete_after ? "--delete-after" :
 427                    (opt.spider ? "--spider" :
 428                     "recursive rejection criteria")));
 429           logprintf (LOG_VERBOSE,
 430                      (opt.delete_after || opt.spider
 431                       ? _("Removing %s.\n")
 432                       : _("Removing %s since it should be rejected.\n")),
 433                      file);
 434           if (unlink (file))
 435             logprintf (LOG_NOTQUIET, "unlink: %s\n", strerror (errno));
 436           logputs (LOG_VERBOSE, "\n");
 437           register_delete_file (file);
 438         }
 439
 440       xfree (url);
 441       xfree_null (referer);
 442       xfree_null (file);
 443     }
 444
 445   /* If anything is left of the queue due to a premature exit, free it
 446      now.  */
 447   {
 448     char *d1, *d2;
 449     int d3;
 450     bool d4, d5;
 451     while (url_dequeue (queue,
 452                         (const char **)&d1, (const char **)&d2, &d3, &d4, &d5))
 453       {
 454         xfree (d1);
 455         xfree_null (d2);
 456       }
 457   }
 458   url_queue_delete (queue);
 459
 460   if (start_url_parsed)
 461     url_free (start_url_parsed);
 462   string_set_free (blacklist);
 463
 464   if (opt.quota && total_downloaded_bytes > opt.quota)
 465     return QUOTEXC;
 466   else if (status == FWRITEERR)
 467     return FWRITEERR;
 468   else
 469     return RETROK;
 470 }
 471
 472 /* Based on the context provided by retrieve_tree, decide whether a
 473    URL is to be descended to.  This is only ever called from
 474    retrieve_tree, but is in a separate function for clarity.
 475
 476    The most expensive checks (such as those for robots) are memoized
 477    by storing these URLs to BLACKLIST.  This may or may not help.  It
 478    will help if those URLs are encountered many times.  */
 479
 480 static bool
 481 download_child_p (const struct urlpos *upos, struct url *parent, int depth,
 482                   struct url *start_url_parsed, struct hash_table *blacklist)
 483 {
 484   struct url *u = upos->url;
 485   const char *url = u->url;
 486   bool u_scheme_like_http;
 487
 488   DEBUGP (("Deciding whether to enqueue \"%s\".\n", url));
 489
 490   if (string_set_contains (blacklist, url))
 491     {
 492       if (opt.spider)
 493         {
 494           char *referrer = url_string (parent, URL_AUTH_HIDE_PASSWD);
 495           DEBUGP (("download_child_p: parent->url is: %s\n", quote (parent->url)));
 496           visited_url (url, referrer);
 497           xfree (referrer);
 498         }
 499       DEBUGP (("Already on the black list.\n"));
 500       goto out;
 501     }
 502
 503   /* Several things to check for:
 504      1. if scheme is not http, and we don't load it
 505      2. check for relative links (if relative_only is set)
 506      3. check for domain
 507      4. check for no-parent
 508      5. check for excludes && includes
 509      6. check for suffix
 510      7. check for same host (if spanhost is unset), with possible
 511      gethostbyname baggage
 512      8. check for robots.txt
 513
 514      Addendum: If the URL is FTP, and it is to be loaded, only the
 515      domain and suffix settings are "stronger".
 516
 517      Note that .html files will get loaded regardless of suffix rules
 518      (but that is remedied later with unlink) unless the depth equals
 519      the maximum depth.
 520
 521      More time- and memory- consuming tests should be put later on
 522      the list.  */
 523
 524   /* Determine whether URL under consideration has a HTTP-like scheme. */
 525   u_scheme_like_http = schemes_are_similar_p (u->scheme, SCHEME_HTTP);
 526
 527   /* 1. Schemes other than HTTP are normally not recursed into. */
 528   if (!u_scheme_like_http && !(u->scheme == SCHEME_FTP && opt.follow_ftp))
 529     {
 530       DEBUGP (("Not following non-HTTP schemes.\n"));
 531       goto out;
 532     }
 533
 534   /* 2. If it is an absolute link and they are not followed, throw it
 535      out.  */
 536   if (u_scheme_like_http)
 537     if (opt.relative_only && !upos->link_relative_p)
 538       {
 539         DEBUGP (("It doesn't really look like a relative link.\n"));
 540         goto out;
 541       }
 542
 543   /* 3. If its domain is not to be accepted/looked-up, chuck it
 544      out.  */
 545   if (!accept_domain (u))
 546     {
 547       DEBUGP (("The domain was not accepted.\n"));
 548       goto out;
 549     }
 550
 551   /* 4. Check for parent directory.
 552
 553      If we descended to a different host or changed the scheme, ignore
 554      opt.no_parent.  Also ignore it for documents needed to display
 555      the parent page when in -p mode.  */
 556   if (opt.no_parent
 557       && schemes_are_similar_p (u->scheme, start_url_parsed->scheme)
 558       && 0 == strcasecmp (u->host, start_url_parsed->host)
 559       && u->port == start_url_parsed->port
 560       && !(opt.page_requisites && upos->link_inline_p))
 561     {
 562       if (!subdir_p (start_url_parsed->dir, u->dir))
 563         {
 564           DEBUGP (("Going to \"%s\" would escape \"%s\" with no_parent on.\n",
 565                    u->dir, start_url_parsed->dir));
 566           goto out;
 567         }
 568     }
 569
 570   /* 5. If the file does not match the acceptance list, or is on the
 571      rejection list, chuck it out.  The same goes for the directory
 572      exclusion and inclusion lists.  */
 573   if (opt.includes || opt.excludes)
 574     {
 575       if (!accdir (u->dir))
 576         {
 577           DEBUGP (("%s (%s) is excluded/not-included.\n", url, u->dir));
 578           goto out;
 579         }
 580     }
 581
 582   /* 6. Check for acceptance/rejection rules.  We ignore these rules
 583      for directories (no file name to match) and for non-leaf HTMLs,
 584      which can lead to other files that do need to be downloaded.  (-p
 585      automatically implies non-leaf because with -p we can, if
 586      necesary, overstep the maximum depth to get the page requisites.)  */
 587   if (u->file[0] != '\0'
 588       && !(has_html_suffix_p (u->file)
 589            /* The exception only applies to non-leaf HTMLs (but -p
 590               always implies non-leaf because we can overstep the
 591               maximum depth to get the requisites): */
 592            && (/* non-leaf */
 593                opt.reclevel == INFINITE_RECURSION
 594                /* also non-leaf */
 595                || depth < opt.reclevel - 1
 596                /* -p, which implies non-leaf (see above) */
 597                || opt.page_requisites)))
 598     {
 599       if (!acceptable (u->file))
 600         {
 601           DEBUGP (("%s (%s) does not match acc/rej rules.\n",
 602                    url, u->file));
 603           goto out;
 604         }
 605     }
 606
 607   /* 7. */
 608   if (schemes_are_similar_p (u->scheme, parent->scheme))
 609     if (!opt.spanhost && 0 != strcasecmp (parent->host, u->host))
 610       {
 611         DEBUGP (("This is not the same hostname as the parent's (%s and %s).\n",
 612                  u->host, parent->host));
 613         goto out;
 614       }
 615
 616   /* 8. */
 617   if (opt.use_robots && u_scheme_like_http)
 618     {
 619       struct robot_specs *specs = res_get_specs (u->host, u->port);
 620       if (!specs)
 621         {
 622           char *rfile;
 623           if (res_retrieve_file (url, &rfile))
 624             {
 625               specs = res_parse_from_file (rfile);
 626
 627               /* Delete the robots.txt file if we chose to either delete the
 628                  files after downloading or we're just running a spider. */
 629               if (opt.delete_after || opt.spider)
 630                 {
 631                   logprintf (LOG_VERBOSE, "Removing %s.\n", rfile);
 632                   if (unlink (rfile))
 633                       logprintf (LOG_NOTQUIET, "unlink: %s\n",
 634                                  strerror (errno));
 635                 }
 636
 637               xfree (rfile);
 638             }
 639           else
 640             {
 641               /* If we cannot get real specs, at least produce
 642                  dummy ones so that we can register them and stop
 643                  trying to retrieve them.  */
 644               specs = res_parse ("", 0);
 645             }
 646           res_register_specs (u->host, u->port, specs);
 647         }
 648
 649       /* Now that we have (or don't have) robots.txt specs, we can
 650          check what they say.  */
 651       if (!res_match_path (specs, u->path))
 652         {
 653           DEBUGP (("Not following %s because robots.txt forbids it.\n", url));
 654           string_set_add (blacklist, url);
 655           goto out;
 656         }
 657     }
 658
 659   /* The URL has passed all the tests.  It can be placed in the
 660      download queue. */
 661   DEBUGP (("Decided to load it.\n"));
 662
 663   return true;
 664
 665  out:
 666   DEBUGP (("Decided NOT to load it.\n"));
 667
 668   return false;
 669 }
 670
 671 /* This function determines whether we will consider downloading the
 672    children of a URL whose download resulted in a redirection,
 673    possibly to another host, etc.  It is needed very rarely, and thus
 674    it is merely a simple-minded wrapper around download_child_p.  */
 675
 676 static bool
 677 descend_redirect_p (const char *redirected, const char *original, int depth,
 678                     struct url *start_url_parsed, struct hash_table *blacklist)
 679 {
 680   struct url *orig_parsed, *new_parsed;
 681   struct urlpos *upos;
 682   bool success;
 683
 684   set_ugly_no_encode (true);
 685   orig_parsed = url_parse (original, NULL);
 686   assert (orig_parsed != NULL);
 687
 688   new_parsed = url_parse (redirected, NULL);
 689   assert (new_parsed != NULL);
 690   set_ugly_no_encode (false);
 691
 692   upos = xnew0 (struct urlpos);
 693   upos->url = new_parsed;
 694
 695   success = download_child_p (upos, orig_parsed, depth,
 696                               start_url_parsed, blacklist);
 697
 698   url_free (orig_parsed);
 699   url_free (new_parsed);
 700   xfree (upos);
 701
 702   if (!success)
 703     DEBUGP (("Redirection \"%s\" failed the test.\n", redirected));
 704
 705   return success;
 706 }
 707
 708 /* vim:set sts=2 sw=2 cino+={s: */