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