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