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

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