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