12e34bd8efc71b61a52d528dfddef9bb8622d6dd
[WebKit-https.git] / WebCore / platform / KURL.cpp
1 /*
2  * Copyright (C) 2004, 2007, 2008 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "config.h"
27
28 #if !USE(GOOGLEURL)
29
30 #include "KURL.h"
31
32 #include "CString.h"
33 #include "StringHash.h"
34 #include "TextEncoding.h"
35 #include <wtf/StdLibExtras.h>
36
37 #if USE(ICU_UNICODE)
38 #include <unicode/uidna.h>
39 #elif USE(QT4_UNICODE)
40 #include <QUrl>
41 #endif
42
43 #include <stdio.h>
44
45 using namespace std;
46 using namespace WTF;
47
48 namespace WebCore {
49
50 typedef Vector<char, 512> CharBuffer;
51 typedef Vector<UChar, 512> UCharBuffer;
52
53 // FIXME: This file makes too much use of the + operator on String.
54 // We either have to optimize that operator so it doesn't involve
55 // so many allocations, or change this to use Vector<UChar> instead.
56
57 enum URLCharacterClasses {
58     // alpha 
59     SchemeFirstChar = 1 << 0,
60
61     // ( alpha | digit | "+" | "-" | "." )
62     SchemeChar = 1 << 1,
63
64     // mark        = "-" | "_" | "." | "!" | "~" | "*" | "'" | "(" | ")"
65     // unreserved  = alphanum | mark
66     // ( unreserved | escaped | ";" | ":" | "&" | "=" | "+" | "$" | "," )
67     UserInfoChar = 1 << 2,
68
69     // alnum | "." | "-" | "%"
70     // The above is what the specification says, but we are lenient to
71     // match existing practice and also allow:
72     // "_"
73     HostnameChar = 1 << 3,
74
75     // hexdigit | ":" | "%"
76     IPv6Char = 1 << 4,
77
78     // "#" | "?" | "/" | nul
79     PathSegmentEndChar = 1 << 5,
80
81     // not allowed in path
82     BadChar = 1 << 6
83 };
84
85 static const char hexDigits[17] = "0123456789ABCDEF";
86
87 static const unsigned char characterClassTable[256] = {
88     /* 0 nul */ PathSegmentEndChar,    /* 1 soh */ BadChar,
89     /* 2 stx */ BadChar,    /* 3 etx */ BadChar,
90     /* 4 eot */ BadChar,    /* 5 enq */ BadChar,    /* 6 ack */ BadChar,    /* 7 bel */ BadChar,
91     /* 8 bs */ BadChar,     /* 9 ht */ BadChar,     /* 10 nl */ BadChar,    /* 11 vt */ BadChar,
92     /* 12 np */ BadChar,    /* 13 cr */ BadChar,    /* 14 so */ BadChar,    /* 15 si */ BadChar,
93     /* 16 dle */ BadChar,   /* 17 dc1 */ BadChar,   /* 18 dc2 */ BadChar,   /* 19 dc3 */ BadChar,
94     /* 20 dc4 */ BadChar,   /* 21 nak */ BadChar,   /* 22 syn */ BadChar,   /* 23 etb */ BadChar,
95     /* 24 can */ BadChar,   /* 25 em */ BadChar,    /* 26 sub */ BadChar,   /* 27 esc */ BadChar,
96     /* 28 fs */ BadChar,    /* 29 gs */ BadChar,    /* 30 rs */ BadChar,    /* 31 us */ BadChar,
97     /* 32 sp */ BadChar,    /* 33  ! */ UserInfoChar,
98     /* 34  " */ BadChar,    /* 35  # */ PathSegmentEndChar | BadChar,
99     /* 36  $ */ UserInfoChar,    /* 37  % */ UserInfoChar | HostnameChar | IPv6Char | BadChar,
100     /* 38  & */ UserInfoChar,    /* 39  ' */ UserInfoChar,
101     /* 40  ( */ UserInfoChar,    /* 41  ) */ UserInfoChar,
102     /* 42  * */ UserInfoChar,    /* 43  + */ SchemeChar | UserInfoChar,
103     /* 44  , */ UserInfoChar,
104     /* 45  - */ SchemeChar | UserInfoChar | HostnameChar,
105     /* 46  . */ SchemeChar | UserInfoChar | HostnameChar,
106     /* 47  / */ PathSegmentEndChar,
107     /* 48  0 */ SchemeChar | UserInfoChar | HostnameChar | IPv6Char, 
108     /* 49  1 */ SchemeChar | UserInfoChar | HostnameChar | IPv6Char,    
109     /* 50  2 */ SchemeChar | UserInfoChar | HostnameChar | IPv6Char, 
110     /* 51  3 */ SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
111     /* 52  4 */ SchemeChar | UserInfoChar | HostnameChar | IPv6Char, 
112     /* 53  5 */ SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
113     /* 54  6 */ SchemeChar | UserInfoChar | HostnameChar | IPv6Char, 
114     /* 55  7 */ SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
115     /* 56  8 */ SchemeChar | UserInfoChar | HostnameChar | IPv6Char, 
116     /* 57  9 */ SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
117     /* 58  : */ UserInfoChar | IPv6Char,    /* 59  ; */ UserInfoChar,
118     /* 60  < */ BadChar,    /* 61  = */ UserInfoChar,
119     /* 62  > */ BadChar,    /* 63  ? */ PathSegmentEndChar | BadChar,
120     /* 64  @ */ 0,
121     /* 65  A */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char,    
122     /* 66  B */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
123     /* 67  C */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
124     /* 68  D */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
125     /* 69  E */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
126     /* 70  F */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
127     /* 71  G */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
128     /* 72  H */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
129     /* 73  I */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
130     /* 74  J */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
131     /* 75  K */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
132     /* 76  L */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
133     /* 77  M */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
134     /* 78  N */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
135     /* 79  O */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
136     /* 80  P */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
137     /* 81  Q */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
138     /* 82  R */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
139     /* 83  S */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
140     /* 84  T */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
141     /* 85  U */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
142     /* 86  V */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
143     /* 87  W */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
144     /* 88  X */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar, 
145     /* 89  Y */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
146     /* 90  Z */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
147     /* 91  [ */ 0,
148     /* 92  \ */ 0,    /* 93  ] */ 0,
149     /* 94  ^ */ 0,
150     /* 95  _ */ UserInfoChar | HostnameChar,
151     /* 96  ` */ 0,
152     /* 97  a */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
153     /* 98  b */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char, 
154     /* 99  c */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
155     /* 100  d */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char, 
156     /* 101  e */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char,
157     /* 102  f */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar | IPv6Char, 
158     /* 103  g */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
159     /* 104  h */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar, 
160     /* 105  i */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
161     /* 106  j */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar, 
162     /* 107  k */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
163     /* 108  l */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar, 
164     /* 109  m */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
165     /* 110  n */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar, 
166     /* 111  o */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
167     /* 112  p */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar, 
168     /* 113  q */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
169     /* 114  r */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar, 
170     /* 115  s */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
171     /* 116  t */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar, 
172     /* 117  u */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
173     /* 118  v */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar, 
174     /* 119  w */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
175     /* 120  x */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar, 
176     /* 121  y */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar,
177     /* 122  z */ SchemeFirstChar | SchemeChar | UserInfoChar | HostnameChar, 
178     /* 123  { */ 0,
179     /* 124  | */ 0,   /* 125  } */ 0,   /* 126  ~ */ UserInfoChar,   /* 127 del */ BadChar,
180     /* 128 */ BadChar, /* 129 */ BadChar, /* 130 */ BadChar, /* 131 */ BadChar,
181     /* 132 */ BadChar, /* 133 */ BadChar, /* 134 */ BadChar, /* 135 */ BadChar,
182     /* 136 */ BadChar, /* 137 */ BadChar, /* 138 */ BadChar, /* 139 */ BadChar,
183     /* 140 */ BadChar, /* 141 */ BadChar, /* 142 */ BadChar, /* 143 */ BadChar,
184     /* 144 */ BadChar, /* 145 */ BadChar, /* 146 */ BadChar, /* 147 */ BadChar,
185     /* 148 */ BadChar, /* 149 */ BadChar, /* 150 */ BadChar, /* 151 */ BadChar,
186     /* 152 */ BadChar, /* 153 */ BadChar, /* 154 */ BadChar, /* 155 */ BadChar,
187     /* 156 */ BadChar, /* 157 */ BadChar, /* 158 */ BadChar, /* 159 */ BadChar,
188     /* 160 */ BadChar, /* 161 */ BadChar, /* 162 */ BadChar, /* 163 */ BadChar,
189     /* 164 */ BadChar, /* 165 */ BadChar, /* 166 */ BadChar, /* 167 */ BadChar,
190     /* 168 */ BadChar, /* 169 */ BadChar, /* 170 */ BadChar, /* 171 */ BadChar,
191     /* 172 */ BadChar, /* 173 */ BadChar, /* 174 */ BadChar, /* 175 */ BadChar,
192     /* 176 */ BadChar, /* 177 */ BadChar, /* 178 */ BadChar, /* 179 */ BadChar,
193     /* 180 */ BadChar, /* 181 */ BadChar, /* 182 */ BadChar, /* 183 */ BadChar,
194     /* 184 */ BadChar, /* 185 */ BadChar, /* 186 */ BadChar, /* 187 */ BadChar,
195     /* 188 */ BadChar, /* 189 */ BadChar, /* 190 */ BadChar, /* 191 */ BadChar,
196     /* 192 */ BadChar, /* 193 */ BadChar, /* 194 */ BadChar, /* 195 */ BadChar,
197     /* 196 */ BadChar, /* 197 */ BadChar, /* 198 */ BadChar, /* 199 */ BadChar,
198     /* 200 */ BadChar, /* 201 */ BadChar, /* 202 */ BadChar, /* 203 */ BadChar,
199     /* 204 */ BadChar, /* 205 */ BadChar, /* 206 */ BadChar, /* 207 */ BadChar,
200     /* 208 */ BadChar, /* 209 */ BadChar, /* 210 */ BadChar, /* 211 */ BadChar,
201     /* 212 */ BadChar, /* 213 */ BadChar, /* 214 */ BadChar, /* 215 */ BadChar,
202     /* 216 */ BadChar, /* 217 */ BadChar, /* 218 */ BadChar, /* 219 */ BadChar,
203     /* 220 */ BadChar, /* 221 */ BadChar, /* 222 */ BadChar, /* 223 */ BadChar,
204     /* 224 */ BadChar, /* 225 */ BadChar, /* 226 */ BadChar, /* 227 */ BadChar,
205     /* 228 */ BadChar, /* 229 */ BadChar, /* 230 */ BadChar, /* 231 */ BadChar,
206     /* 232 */ BadChar, /* 233 */ BadChar, /* 234 */ BadChar, /* 235 */ BadChar,
207     /* 236 */ BadChar, /* 237 */ BadChar, /* 238 */ BadChar, /* 239 */ BadChar,
208     /* 240 */ BadChar, /* 241 */ BadChar, /* 242 */ BadChar, /* 243 */ BadChar,
209     /* 244 */ BadChar, /* 245 */ BadChar, /* 246 */ BadChar, /* 247 */ BadChar,
210     /* 248 */ BadChar, /* 249 */ BadChar, /* 250 */ BadChar, /* 251 */ BadChar,
211     /* 252 */ BadChar, /* 253 */ BadChar, /* 254 */ BadChar, /* 255 */ BadChar
212 };
213
214 static int copyPathRemovingDots(char* dst, const char* src, int srcStart, int srcEnd);
215 static void encodeRelativeString(const String& rel, const TextEncoding&, CharBuffer& ouput);
216 static String substituteBackslashes(const String&);
217
218 static inline bool isSchemeFirstChar(char c) { return characterClassTable[static_cast<unsigned char>(c)] & SchemeFirstChar; }
219 static inline bool isSchemeFirstChar(UChar c) { return c <= 0xff && (characterClassTable[c] & SchemeFirstChar); }
220 static inline bool isSchemeChar(char c) { return characterClassTable[static_cast<unsigned char>(c)] & SchemeChar; }
221 static inline bool isSchemeChar(UChar c) { return c <= 0xff && (characterClassTable[c] & SchemeChar); }
222 static inline bool isUserInfoChar(unsigned char c) { return characterClassTable[c] & UserInfoChar; }
223 static inline bool isHostnameChar(unsigned char c) { return characterClassTable[c] & HostnameChar; }
224 static inline bool isIPv6Char(unsigned char c) { return characterClassTable[c] & IPv6Char; }
225 static inline bool isPathSegmentEndChar(char c) { return characterClassTable[static_cast<unsigned char>(c)] & PathSegmentEndChar; }
226 static inline bool isPathSegmentEndChar(UChar c) { return c <= 0xff && (characterClassTable[c] & PathSegmentEndChar); }
227 static inline bool isBadChar(unsigned char c) { return characterClassTable[c] & BadChar; }
228
229 static inline int hexDigitValue(UChar c)
230 {
231     ASSERT(isASCIIHexDigit(c));
232     if (c < 'A')
233         return c - '0';
234     return (c - 'A' + 10) & 0xF; // handle both upper and lower case without a branch
235 }
236
237 // Copies the source to the destination, assuming all the source characters are
238 // ASCII. The destination buffer must be large enough. Null characters are allowed
239 // in the source string, and no attempt is made to null-terminate the result.
240 static void copyASCII(const UChar* src, int length, char* dest)
241 {
242     for (int i = 0; i < length; i++)
243         dest[i] = static_cast<char>(src[i]);
244 }
245
246 static void appendASCII(const String& base, const char* rel, size_t len, CharBuffer& buffer)
247 {
248     buffer.resize(base.length() + len + 1);
249     copyASCII(base.characters(), base.length(), buffer.data());
250     memcpy(buffer.data() + base.length(), rel, len);
251     buffer[buffer.size() - 1] = '\0';
252 }
253
254 // FIXME: Move to PlatformString.h eventually.
255 // Returns the index of the first index in string |s| of any of the characters
256 // in |toFind|. |toFind| should be a null-terminated string, all characters up
257 // to the null will be searched. Returns int if not found.
258 static int findFirstOf(const UChar* s, int sLen, int startPos, const char* toFind)
259 {
260     for (int i = startPos; i < sLen; i++) {
261         const char* cur = toFind;
262         while (*cur) {
263             if (s[i] == *(cur++))
264                 return i;
265         }
266     }
267     return -1;
268 }
269
270 #ifndef NDEBUG
271 static void checkEncodedString(const String& url)
272 {
273     for (unsigned i = 0; i < url.length(); ++i)
274         ASSERT(!(url[i] & ~0x7F));
275
276     ASSERT(!url.length() || isSchemeFirstChar(url[0]));
277 }
278 #else
279 static inline void checkEncodedString(const String&)
280 {
281 }
282 #endif
283
284 inline bool KURL::protocolIs(const String& string, const char* protocol)
285 {
286     return WebCore::protocolIs(string, protocol);
287 }
288
289 void KURL::invalidate()
290 {
291     m_isValid = false;
292     m_protocolInHTTPFamily = false;
293     m_schemeEnd = 0;
294     m_userStart = 0;
295     m_userEnd = 0;
296     m_passwordEnd = 0;
297     m_hostEnd = 0;
298     m_portEnd = 0;
299     m_pathEnd = 0;
300     m_pathAfterLastSlash = 0;
301     m_queryEnd = 0;
302     m_fragmentEnd = 0;
303 }
304
305 KURL::KURL(ParsedURLStringTag, const char* url)
306 {
307     parse(url, 0);
308     ASSERT(url == m_string);
309 }
310
311 KURL::KURL(ParsedURLStringTag, const String& url)
312 {
313     parse(url);
314     ASSERT(url == m_string);
315 }
316
317 KURL::KURL(const KURL& base, const String& relative)
318 {
319     init(base, relative, UTF8Encoding());
320 }
321
322 KURL::KURL(const KURL& base, const String& relative, const TextEncoding& encoding)
323 {
324     // For UTF-{7,16,32}, we want to use UTF-8 for the query part as 
325     // we do when submitting a form. A form with GET method
326     // has its contents added to a URL as query params and it makes sense
327     // to be consistent.
328     init(base, relative, encoding.encodingForFormSubmission());
329 }
330
331 void KURL::init(const KURL& base, const String& relative, const TextEncoding& encoding)
332 {
333     // Allow resolutions with a null or empty base URL, but not with any other invalid one.
334     // FIXME: Is this a good rule?
335     if (!base.m_isValid && !base.isEmpty()) {
336         m_string = relative;
337         invalidate();
338         return;
339     }
340
341     // For compatibility with Win IE, treat backslashes as if they were slashes,
342     // as long as we're not dealing with javascript: or data: URLs.
343     String rel = relative;
344     if (rel.contains('\\') && !(protocolIsJavaScript(rel) || protocolIs(rel, "data")))
345         rel = substituteBackslashes(rel);
346
347     String* originalString = &rel;
348
349     bool allASCII = charactersAreAllASCII(rel.characters(), rel.length());
350     CharBuffer strBuffer;
351     char* str;
352     size_t len;
353     if (allASCII) {
354         len = rel.length();
355         strBuffer.resize(len + 1);
356         copyASCII(rel.characters(), len, strBuffer.data());
357         strBuffer[len] = 0;
358         str = strBuffer.data();
359     } else {
360         originalString = 0;
361         encodeRelativeString(rel, encoding, strBuffer);
362         str = strBuffer.data();
363         len = strlen(str);
364     }
365
366     // Get rid of leading whitespace.
367     while (*str == ' ') {
368         originalString = 0;
369         str++;
370         --len;
371     }
372
373     // Get rid of trailing whitespace.
374     while (len && str[len - 1] == ' ') {
375         originalString = 0;
376         str[--len] = '\0';
377     }
378
379     // According to the RFC, the reference should be interpreted as an
380     // absolute URI if possible, using the "leftmost, longest"
381     // algorithm. If the URI reference is absolute it will have a
382     // scheme, meaning that it will have a colon before the first
383     // non-scheme element.
384     bool absolute = false;
385     char* p = str;
386     if (isSchemeFirstChar(*p)) {
387         ++p;
388         while (isSchemeChar(*p)) {
389             ++p;
390         }
391         if (*p == ':') {
392             if (p[1] != '/' && equalIgnoringCase(base.protocol(), String(str, p - str)) && base.isHierarchical()) {
393                 str = p + 1;
394                 originalString = 0;
395             } else
396                 absolute = true;
397         }
398     }
399
400     CharBuffer parseBuffer;
401
402     if (absolute) {
403         parse(str, originalString);
404     } else {
405         // If the base is empty or opaque (e.g. data: or javascript:), then the URL is invalid
406         // unless the relative URL is a single fragment.
407         if (!base.isHierarchical()) {
408             if (str[0] == '#') {
409                 appendASCII(base.m_string.left(base.m_queryEnd), str, len, parseBuffer);
410                 parse(parseBuffer.data(), 0);
411             } else {
412                 m_string = relative;
413                 invalidate();
414             }
415             return;
416         }
417
418         switch (str[0]) {
419         case '\0':
420             // the reference must be empty - the RFC says this is a
421             // reference to the same document
422             *this = base;
423             break;
424         case '#': {
425             // must be fragment-only reference
426             appendASCII(base.m_string.left(base.m_queryEnd), str, len, parseBuffer);
427             parse(parseBuffer.data(), 0);
428             break;
429         }
430         case '?': {
431             // query-only reference, special case needed for non-URL results
432             appendASCII(base.m_string.left(base.m_pathEnd), str, len, parseBuffer);
433             parse(parseBuffer.data(), 0);
434             break;
435         }
436         case '/':
437             // must be net-path or absolute-path reference
438             if (str[1] == '/') {
439                 // net-path
440                 appendASCII(base.m_string.left(base.m_schemeEnd + 1), str, len, parseBuffer);
441                 parse(parseBuffer.data(), 0);
442             } else {
443                 // abs-path
444                 appendASCII(base.m_string.left(base.m_portEnd), str, len, parseBuffer);
445                 parse(parseBuffer.data(), 0);
446             }
447             break;
448         default:
449             {
450                 // must be relative-path reference
451
452                 // Base part plus relative part plus one possible slash added in between plus terminating \0 byte.
453                 parseBuffer.resize(base.m_pathEnd + 1 + len + 1);
454
455                 char* bufferPos = parseBuffer.data();
456
457                 // first copy everything before the path from the base
458                 unsigned baseLength = base.m_string.length();
459                 const UChar* baseCharacters = base.m_string.characters();
460                 CharBuffer baseStringBuffer(baseLength);
461                 copyASCII(baseCharacters, baseLength, baseStringBuffer.data());
462                 const char* baseString = baseStringBuffer.data();
463                 const char* baseStringStart = baseString;
464                 const char* pathStart = baseStringStart + base.m_portEnd;
465                 while (baseStringStart < pathStart)
466                     *bufferPos++ = *baseStringStart++;
467                 char* bufferPathStart = bufferPos;
468
469                 // now copy the base path
470                 const char* baseStringEnd = baseString + base.m_pathEnd;
471
472                 // go back to the last slash
473                 while (baseStringEnd > baseStringStart && baseStringEnd[-1] != '/')
474                     baseStringEnd--;
475
476                 if (baseStringEnd == baseStringStart) {
477                     // no path in base, add a path separator if necessary
478                     if (base.m_schemeEnd + 1 != base.m_pathEnd && *str && *str != '?' && *str != '#')
479                         *bufferPos++ = '/';
480                 } else {
481                     bufferPos += copyPathRemovingDots(bufferPos, baseStringStart, 0, baseStringEnd - baseStringStart);
482                 }
483
484                 const char* relStringStart = str;
485                 const char* relStringPos = relStringStart;
486
487                 while (*relStringPos && *relStringPos != '?' && *relStringPos != '#') {
488                     if (relStringPos[0] == '.' && bufferPos[-1] == '/') {
489                         if (isPathSegmentEndChar(relStringPos[1])) {
490                             // skip over "." segment
491                             relStringPos += 1;
492                             if (relStringPos[0] == '/')
493                                 relStringPos++;
494                             continue;
495                         } else if (relStringPos[1] == '.' && isPathSegmentEndChar(relStringPos[2])) {
496                             // skip over ".." segment and rewind the last segment
497                             // the RFC leaves it up to the app to decide what to do with excess
498                             // ".." segments - we choose to drop them since some web content
499                             // relies on this.
500                             relStringPos += 2;
501                             if (relStringPos[0] == '/')
502                                 relStringPos++;
503                             if (bufferPos > bufferPathStart + 1)
504                                 bufferPos--;
505                             while (bufferPos > bufferPathStart + 1  && bufferPos[-1] != '/')
506                                 bufferPos--;
507                             continue;
508                         }
509                     }
510
511                     *bufferPos = *relStringPos;
512                     relStringPos++;
513                     bufferPos++;
514                 }
515
516                 // all done with the path work, now copy any remainder
517                 // of the relative reference; this will also add a null terminator
518                 strcpy(bufferPos, relStringPos);
519
520                 parse(parseBuffer.data(), 0);
521
522                 ASSERT(strlen(parseBuffer.data()) + 1 <= parseBuffer.size());
523                 break;
524             }
525         }
526     }
527 }
528
529 KURL KURL::copy() const
530 {
531     KURL result = *this;
532     result.m_string = result.m_string.crossThreadString();
533     return result;
534 }
535
536 bool KURL::hasPath() const
537 {
538     return m_pathEnd != m_portEnd;
539 }
540
541 String KURL::lastPathComponent() const
542 {
543     if (!hasPath())
544         return String();
545
546     int end = m_pathEnd - 1;
547     if (m_string[end] == '/')
548         --end;
549
550     int start = m_string.reverseFind('/', end);
551     if (start < m_portEnd)
552         return String();
553     ++start;
554
555     return m_string.substring(start, end - start + 1);
556 }
557
558 String KURL::protocol() const
559 {
560     return m_string.left(m_schemeEnd);
561 }
562
563 String KURL::host() const
564 {
565     int start = hostStart();
566     return decodeURLEscapeSequences(m_string.substring(start, m_hostEnd - start));
567 }
568
569 unsigned short KURL::port() const
570 {
571     if (m_hostEnd == m_portEnd)
572         return 0;
573
574     int number = m_string.substring(m_hostEnd + 1, m_portEnd - m_hostEnd - 1).toInt();
575     if (number < 0 || number > 0xFFFF)
576         return 0;
577     return number;
578 }
579
580 String KURL::pass() const
581 {
582     if (m_passwordEnd == m_userEnd)
583         return String();
584
585     return decodeURLEscapeSequences(m_string.substring(m_userEnd + 1, m_passwordEnd - m_userEnd - 1)); 
586 }
587
588 String KURL::user() const
589 {
590     return decodeURLEscapeSequences(m_string.substring(m_userStart, m_userEnd - m_userStart));
591 }
592
593 String KURL::fragmentIdentifier() const
594 {
595     if (m_fragmentEnd == m_queryEnd)
596         return String();
597
598     return m_string.substring(m_queryEnd + 1, m_fragmentEnd - (m_queryEnd + 1));
599 }
600
601 bool KURL::hasFragmentIdentifier() const
602 {
603     return m_fragmentEnd != m_queryEnd;
604 }
605
606 String KURL::baseAsString() const
607 {
608     return m_string.left(m_pathAfterLastSlash);
609 }
610
611 #ifdef NDEBUG
612
613 static inline void assertProtocolIsGood(const char*)
614 {
615 }
616
617 #else
618
619 static void assertProtocolIsGood(const char* protocol)
620 {
621     const char* p = protocol;
622     while (*p) {
623         ASSERT(*p > ' ' && *p < 0x7F && !(*p >= 'A' && *p <= 'Z'));
624         ++p;
625     }
626 }
627
628 #endif
629
630 bool KURL::protocolIs(const char* protocol) const
631 {
632     assertProtocolIsGood(protocol);
633
634     // JavaScript URLs are "valid" and should be executed even if KURL decides they are invalid.
635     // The free function protocolIsJavaScript() should be used instead. 
636     ASSERT(!equalIgnoringCase(protocol, String("javascript")));
637
638     if (!m_isValid)
639         return false;
640
641     // Do the comparison without making a new string object.
642     for (int i = 0; i < m_schemeEnd; ++i) {
643         if (!protocol[i] || toASCIILower(m_string[i]) != protocol[i])
644             return false;
645     }
646     return !protocol[m_schemeEnd]; // We should have consumed all characters in the argument.
647 }
648
649 String KURL::query() const
650 {
651     if (m_queryEnd == m_pathEnd)
652         return String();
653
654     return m_string.substring(m_pathEnd + 1, m_queryEnd - (m_pathEnd + 1)); 
655 }
656
657 String KURL::path() const
658 {
659     return decodeURLEscapeSequences(m_string.substring(m_portEnd, m_pathEnd - m_portEnd)); 
660 }
661
662 void KURL::setProtocol(const String& s)
663 {
664     // FIXME: Non-ASCII characters must be encoded and escaped to match parse() expectations,
665     // and to avoid changing more than just the protocol.
666
667     if (!m_isValid) {
668         parse(s + ":" + m_string);
669         return;
670     }
671
672     parse(s + m_string.substring(m_schemeEnd));
673 }
674
675 void KURL::setHost(const String& s)
676 {
677     if (!m_isValid)
678         return;
679
680     // FIXME: Non-ASCII characters must be encoded and escaped to match parse() expectations,
681     // and to avoid changing more than just the host.
682
683     bool slashSlashNeeded = m_userStart == m_schemeEnd + 1;
684
685     parse(m_string.left(hostStart()) + (slashSlashNeeded ? "//" : "") + s + m_string.substring(m_hostEnd));
686 }
687
688 void KURL::removePort()
689 {
690     if (m_hostEnd == m_portEnd)
691         return;
692     parse(m_string.left(m_hostEnd) + m_string.substring(m_portEnd));
693 }
694
695 void KURL::setPort(unsigned short i)
696 {
697     if (!m_isValid)
698         return;
699
700     bool colonNeeded = m_portEnd == m_hostEnd;
701     int portStart = (colonNeeded ? m_hostEnd : m_hostEnd + 1);
702
703     parse(m_string.left(portStart) + (colonNeeded ? ":" : "") + String::number(i) + m_string.substring(m_portEnd));
704 }
705
706 void KURL::setHostAndPort(const String& hostAndPort)
707 {
708     if (!m_isValid)
709         return;
710
711     // FIXME: Non-ASCII characters must be encoded and escaped to match parse() expectations,
712     // and to avoid changing more than just host and port.
713
714     bool slashSlashNeeded = m_userStart == m_schemeEnd + 1;
715
716     parse(m_string.left(hostStart()) + (slashSlashNeeded ? "//" : "") + hostAndPort + m_string.substring(m_portEnd));
717 }
718
719 void KURL::setUser(const String& user)
720 {
721     if (!m_isValid)
722         return;
723
724     // FIXME: Non-ASCII characters must be encoded and escaped to match parse() expectations,
725     // and to avoid changing more than just the user login.
726     String u;
727     int end = m_userEnd;
728     if (!user.isEmpty()) {
729         u = user;
730         if (m_userStart == m_schemeEnd + 1)
731             u = "//" + u;
732         // Add '@' if we didn't have one before.
733         if (end == m_hostEnd || (end == m_passwordEnd && m_string[end] != '@'))
734             u.append('@');
735     } else {
736         // Remove '@' if we now have neither user nor password.
737         if (m_userEnd == m_passwordEnd && end != m_hostEnd && m_string[end] == '@')
738             end += 1;
739     }
740     parse(m_string.left(m_userStart) + u + m_string.substring(end));
741 }
742
743 void KURL::setPass(const String& password)
744 {
745     if (!m_isValid)
746         return;
747
748     // FIXME: Non-ASCII characters must be encoded and escaped to match parse() expectations,
749     // and to avoid changing more than just the user password.
750     String p;
751     int end = m_passwordEnd;
752     if (!password.isEmpty()) {
753         p = ":" + password + "@";
754         if (m_userEnd == m_schemeEnd + 1)
755             p = "//" + p;
756         // Eat the existing '@' since we are going to add our own.
757         if (end != m_hostEnd && m_string[end] == '@')
758             end += 1;
759     } else {
760         // Remove '@' if we now have neither user nor password.
761         if (m_userStart == m_userEnd && end != m_hostEnd && m_string[end] == '@')
762             end += 1;
763     }
764     parse(m_string.left(m_userEnd) + p + m_string.substring(end));
765 }
766
767 void KURL::setFragmentIdentifier(const String& s)
768 {
769     if (!m_isValid)
770         return;
771
772     // FIXME: Non-ASCII characters must be encoded and escaped to match parse() expectations.
773     parse(m_string.left(m_queryEnd) + "#" + s);
774 }
775
776 void KURL::removeFragmentIdentifier()
777 {
778     if (!m_isValid)
779         return;
780     parse(m_string.left(m_queryEnd));
781 }
782     
783 void KURL::setQuery(const String& query)
784 {
785     if (!m_isValid)
786         return;
787
788     // FIXME: '#' and non-ASCII characters must be encoded and escaped.
789     // Usually, the query is encoded using document encoding, not UTF-8, but we don't have
790     // access to the document in this function.
791     if ((query.isEmpty() || query[0] != '?') && !query.isNull())
792         parse(m_string.left(m_pathEnd) + "?" + query + m_string.substring(m_queryEnd));
793     else
794         parse(m_string.left(m_pathEnd) + query + m_string.substring(m_queryEnd));
795
796 }
797
798 void KURL::setPath(const String& s)
799 {
800     if (!m_isValid)
801         return;
802
803     // FIXME: encodeWithURLEscapeSequences does not correctly escape '#' and '?', so fragment and query parts
804     // may be inadvertently affected.
805     parse(m_string.left(m_portEnd) + encodeWithURLEscapeSequences(s) + m_string.substring(m_pathEnd));
806 }
807
808 String KURL::prettyURL() const
809 {
810     if (!m_isValid)
811         return m_string;
812
813     Vector<UChar> result;
814
815     append(result, protocol());
816     result.append(':');
817
818     Vector<UChar> authority;
819
820     if (m_hostEnd != m_passwordEnd) {
821         if (m_userEnd != m_userStart) {
822             append(authority, user());
823             authority.append('@');
824         }
825         append(authority, host());
826         if (hasPort()) {
827             authority.append(':');
828             append(authority, String::number(port()));
829         }
830     }
831
832     if (!authority.isEmpty()) {
833         result.append('/');
834         result.append('/');
835         result.append(authority);
836     } else if (protocolIs("file")) {
837         result.append('/');
838         result.append('/');
839     }
840
841     append(result, path());
842
843     if (m_pathEnd != m_queryEnd) {
844         result.append('?');
845         append(result, query());
846     }
847
848     if (m_fragmentEnd != m_queryEnd) {
849         result.append('#');
850         append(result, fragmentIdentifier());
851     }
852
853     return String::adopt(result);
854 }
855
856 String decodeURLEscapeSequences(const String& str)
857 {
858     return decodeURLEscapeSequences(str, UTF8Encoding());
859 }
860
861 String decodeURLEscapeSequences(const String& str, const TextEncoding& encoding)
862 {
863     Vector<UChar> result;
864
865     CharBuffer buffer;
866
867     int length = str.length();
868     int decodedPosition = 0;
869     int searchPosition = 0;
870     int encodedRunPosition;
871     while ((encodedRunPosition = str.find('%', searchPosition)) >= 0) {
872         // Find the sequence of %-escape codes.
873         int encodedRunEnd = encodedRunPosition;
874         while (length - encodedRunEnd >= 3
875                 && str[encodedRunEnd] == '%'
876                 && isASCIIHexDigit(str[encodedRunEnd + 1])
877                 && isASCIIHexDigit(str[encodedRunEnd + 2]))
878             encodedRunEnd += 3;
879         if (encodedRunEnd == encodedRunPosition) {
880             ++searchPosition;
881             continue;
882         }
883         searchPosition = encodedRunEnd;
884
885         // Decode the %-escapes into bytes.
886         unsigned runLength = (encodedRunEnd - encodedRunPosition) / 3;
887         buffer.resize(runLength);
888         char* p = buffer.data();
889         const UChar* q = str.characters() + encodedRunPosition;
890         for (unsigned i = 0; i < runLength; ++i) {
891             *p++ = (hexDigitValue(q[1]) << 4) | hexDigitValue(q[2]);
892             q += 3;
893         }
894
895         // Decode the bytes into Unicode characters.
896         String decoded = (encoding.isValid() ? encoding : UTF8Encoding()).decode(buffer.data(), p - buffer.data());
897         if (decoded.isEmpty())
898             continue;
899
900         // Build up the string with what we just skipped and what we just decoded.
901         result.append(str.characters() + decodedPosition, encodedRunPosition - decodedPosition);
902         result.append(decoded.characters(), decoded.length());
903         decodedPosition = encodedRunEnd;
904     }
905
906     result.append(str.characters() + decodedPosition, length - decodedPosition);
907
908     return String::adopt(result);
909 }
910
911 bool KURL::isLocalFile() const
912 {
913     // Including feed here might be a bad idea since drag and drop uses this check
914     // and including feed would allow feeds to potentially let someone's blog
915     // read the contents of the clipboard on a drag, even without a drop.
916     // Likewise with using the FrameLoader::shouldTreatURLAsLocal() function.
917     return protocolIs("file");
918 }
919
920 static void appendEscapingBadChars(char*& buffer, const char* strStart, size_t length)
921 {
922     char* p = buffer;
923
924     const char* str = strStart;
925     const char* strEnd = strStart + length;
926     while (str < strEnd) {
927         unsigned char c = *str++;
928         if (isBadChar(c)) {
929             if (c == '%' || c == '?') {
930                 *p++ = c;
931             } else if (c != 0x09 && c != 0x0a && c != 0x0d) {
932                 *p++ = '%';
933                 *p++ = hexDigits[c >> 4];
934                 *p++ = hexDigits[c & 0xF];
935             }
936         } else {
937             *p++ = c;
938         }
939     }
940
941     buffer = p;
942 }
943
944 // copy a path, accounting for "." and ".." segments
945 static int copyPathRemovingDots(char* dst, const char* src, int srcStart, int srcEnd)
946 {
947     char* bufferPathStart = dst;
948
949     // empty path is a special case, and need not have a leading slash
950     if (srcStart != srcEnd) {
951         const char* baseStringStart = src + srcStart;
952         const char* baseStringEnd = src + srcEnd;
953         const char* baseStringPos = baseStringStart;
954
955         // this code is unprepared for paths that do not begin with a
956         // slash and we should always have one in the source string
957         ASSERT(baseStringPos[0] == '/');
958
959         // copy the leading slash into the destination
960         *dst = *baseStringPos;
961         baseStringPos++;
962         dst++;
963
964         while (baseStringPos < baseStringEnd) {
965             if (baseStringPos[0] == '.' && dst[-1] == '/') {
966                 if (baseStringPos[1] == '/' || baseStringPos + 1 == baseStringEnd) {
967                     // skip over "." segment
968                     baseStringPos += 2;
969                     continue;
970                 } else if (baseStringPos[1] == '.' && (baseStringPos[2] == '/' ||
971                                        baseStringPos + 2 == baseStringEnd)) {
972                     // skip over ".." segment and rewind the last segment
973                     // the RFC leaves it up to the app to decide what to do with excess
974                     // ".." segments - we choose to drop them since some web content
975                     // relies on this.
976                     baseStringPos += 3;
977                     if (dst > bufferPathStart + 1)
978                         dst--;
979                     // Note that these two while blocks differ subtly.
980                     // The first helps to remove multiple adjoining slashes as we rewind.
981                     // The +1 to bufferPathStart in the first while block prevents eating a leading slash
982                     while (dst > bufferPathStart + 1 && dst[-1] == '/')
983                         dst--;
984                     while (dst > bufferPathStart && dst[-1] != '/')
985                         dst--;
986                     continue;
987                 }
988             }
989
990             *dst = *baseStringPos;
991             baseStringPos++;
992             dst++;
993         }
994     }
995     *dst = '\0';
996     return dst - bufferPathStart;
997 }
998
999 static inline bool hasSlashDotOrDotDot(const char* str)
1000 {
1001     const unsigned char* p = reinterpret_cast<const unsigned char*>(str);
1002     if (!*p)
1003         return false;
1004     unsigned char pc = *p;
1005     while (unsigned char c = *++p) {
1006         if (c == '.' && (pc == '/' || pc == '.'))
1007             return true;
1008         pc = c;
1009     }
1010     return false;
1011 }
1012
1013 static inline bool matchLetter(char c, char lowercaseLetter)
1014 {
1015     return (c | 0x20) == lowercaseLetter;
1016 }
1017
1018 void KURL::parse(const String& string)
1019 {
1020     checkEncodedString(string);
1021
1022     CharBuffer buffer(string.length() + 1);
1023     copyASCII(string.characters(), string.length(), buffer.data());
1024     buffer[string.length()] = '\0';
1025     parse(buffer.data(), &string);
1026 }
1027
1028 void KURL::parse(const char* url, const String* originalString)
1029 {
1030     if (!url || url[0] == '\0') {
1031         // valid URL must be non-empty
1032         m_string = originalString ? *originalString : url;
1033         invalidate();
1034         return;
1035     }
1036
1037     if (!isSchemeFirstChar(url[0])) {
1038         // scheme must start with an alphabetic character
1039         m_string = originalString ? *originalString : url;
1040         invalidate();
1041         return;
1042     }
1043
1044     int schemeEnd = 0;
1045     while (isSchemeChar(url[schemeEnd]))
1046         schemeEnd++;
1047
1048     if (url[schemeEnd] != ':') {
1049         m_string = originalString ? *originalString : url;
1050         invalidate();
1051         return;
1052     }
1053
1054     int userStart = schemeEnd + 1;
1055     int userEnd;
1056     int passwordStart;
1057     int passwordEnd;
1058     int hostStart;
1059     int hostEnd;
1060     int portStart;
1061     int portEnd;
1062
1063     bool hierarchical = url[schemeEnd + 1] == '/';
1064
1065     bool isFile = schemeEnd == 4
1066         && matchLetter(url[0], 'f')
1067         && matchLetter(url[1], 'i')
1068         && matchLetter(url[2], 'l')
1069         && matchLetter(url[3], 'e');
1070
1071     m_protocolInHTTPFamily = matchLetter(url[0], 'h')
1072         && matchLetter(url[1], 't')
1073         && matchLetter(url[2], 't')
1074         && matchLetter(url[3], 'p')
1075         && (url[4] == ':' || (matchLetter(url[4], 's') && url[5] == ':'));
1076
1077     if (hierarchical && url[schemeEnd + 2] == '/') {
1078         // The part after the scheme is either a net_path or an abs_path whose first path segment is empty.
1079         // Attempt to find an authority.
1080
1081         // FIXME: Authority characters may be scanned twice, and it would be nice to be faster.
1082         userStart += 2;
1083         userEnd = userStart;
1084
1085         int colonPos = 0;
1086         while (isUserInfoChar(url[userEnd])) {
1087             if (url[userEnd] == ':' && colonPos == 0)
1088                 colonPos = userEnd;
1089             userEnd++;
1090         }
1091
1092         if (url[userEnd] == '@') {
1093             // actual end of the userinfo, start on the host
1094             if (colonPos != 0) {
1095                 passwordEnd = userEnd;
1096                 userEnd = colonPos;
1097                 passwordStart = colonPos + 1;
1098             } else
1099                 passwordStart = passwordEnd = userEnd;
1100
1101             hostStart = passwordEnd + 1;
1102         } else if (url[userEnd] == '[' || isPathSegmentEndChar(url[userEnd])) {
1103             // hit the end of the authority, must have been no user
1104             // or looks like an IPv6 hostname
1105             // either way, try to parse it as a hostname
1106             userEnd = userStart;
1107             passwordStart = passwordEnd = userEnd;
1108             hostStart = userStart;
1109         } else {
1110             // invalid character
1111             m_string = originalString ? *originalString : url;
1112             invalidate();
1113             return;
1114         }
1115
1116         hostEnd = hostStart;
1117
1118         // IPV6 IP address
1119         if (url[hostEnd] == '[') {
1120             hostEnd++;
1121             while (isIPv6Char(url[hostEnd]))
1122                 hostEnd++;
1123             if (url[hostEnd] == ']')
1124                 hostEnd++;
1125             else {
1126                 // invalid character
1127                 m_string = originalString ? *originalString : url;
1128                 invalidate();
1129                 return;
1130             }
1131         } else {
1132             while (isHostnameChar(url[hostEnd]))
1133                 hostEnd++;
1134         }
1135         
1136         if (url[hostEnd] == ':') {
1137             portStart = portEnd = hostEnd + 1;
1138  
1139             // possible start of port
1140             portEnd = portStart;
1141             while (isASCIIDigit(url[portEnd]))
1142                 portEnd++;
1143         } else
1144             portStart = portEnd = hostEnd;
1145
1146         if (!isPathSegmentEndChar(url[portEnd])) {
1147             // invalid character
1148             m_string = originalString ? *originalString : url;
1149             invalidate();
1150             return;
1151         }
1152
1153         if (userStart == portEnd && !m_protocolInHTTPFamily && !isFile) {
1154             // No authority found, which means that this is not a net_path, but rather an abs_path whose first two
1155             // path segments are empty. For file, http and https only, an empty authority is allowed.
1156             userStart -= 2;
1157             userEnd = userStart;
1158             passwordStart = userEnd;
1159             passwordEnd = passwordStart;
1160             hostStart = passwordEnd;
1161             hostEnd = hostStart;
1162             portStart = hostEnd;
1163             portEnd = hostEnd;
1164         }
1165     } else {
1166         // the part after the scheme must be an opaque_part or an abs_path
1167         userEnd = userStart;
1168         passwordStart = passwordEnd = userEnd;
1169         hostStart = hostEnd = passwordEnd;
1170         portStart = portEnd = hostEnd;
1171     }
1172
1173     int pathStart = portEnd;
1174     int pathEnd = pathStart;
1175     while (url[pathEnd] && url[pathEnd] != '?' && url[pathEnd] != '#')
1176         pathEnd++;
1177
1178     int queryStart = pathEnd;
1179     int queryEnd = queryStart;
1180     if (url[queryStart] == '?') {
1181         while (url[queryEnd] && url[queryEnd] != '#')
1182             queryEnd++;
1183     }
1184
1185     int fragmentStart = queryEnd;
1186     int fragmentEnd = fragmentStart;
1187     if (url[fragmentStart] == '#') {
1188         fragmentStart++;
1189         fragmentEnd = fragmentStart;
1190         while (url[fragmentEnd])
1191             fragmentEnd++;
1192     }
1193
1194     // assemble it all, remembering the real ranges
1195
1196     Vector<char, 4096> buffer(fragmentEnd * 3 + 1);
1197
1198     char *p = buffer.data();
1199     const char *strPtr = url;
1200
1201     // copy in the scheme
1202     const char *schemeEndPtr = url + schemeEnd;
1203     while (strPtr < schemeEndPtr)
1204         *p++ = *strPtr++;
1205     m_schemeEnd = p - buffer.data();
1206
1207     bool hostIsLocalHost = portEnd - userStart == 9
1208         && matchLetter(url[userStart], 'l')
1209         && matchLetter(url[userStart+1], 'o')
1210         && matchLetter(url[userStart+2], 'c')
1211         && matchLetter(url[userStart+3], 'a')
1212         && matchLetter(url[userStart+4], 'l')
1213         && matchLetter(url[userStart+5], 'h')
1214         && matchLetter(url[userStart+6], 'o')
1215         && matchLetter(url[userStart+7], 's')
1216         && matchLetter(url[userStart+8], 't');
1217
1218     // File URLs need a host part unless it is just file:// or file://localhost
1219     bool degenFilePath = pathStart == pathEnd && (hostStart == hostEnd || hostIsLocalHost);
1220
1221     bool haveNonHostAuthorityPart = userStart != userEnd || passwordStart != passwordEnd || portStart != portEnd;
1222
1223     // add ":" after scheme
1224     *p++ = ':';
1225
1226     // if we have at least one authority part or a file URL - add "//" and authority
1227     if (isFile ? !degenFilePath : (haveNonHostAuthorityPart || hostStart != hostEnd)) {
1228         *p++ = '/';
1229         *p++ = '/';
1230
1231         m_userStart = p - buffer.data();
1232
1233         // copy in the user
1234         strPtr = url + userStart;
1235         const char* userEndPtr = url + userEnd;
1236         while (strPtr < userEndPtr)
1237             *p++ = *strPtr++;
1238         m_userEnd = p - buffer.data();
1239
1240         // copy in the password
1241         if (passwordEnd != passwordStart) {
1242             *p++ = ':';
1243             strPtr = url + passwordStart;
1244             const char* passwordEndPtr = url + passwordEnd;
1245             while (strPtr < passwordEndPtr)
1246                 *p++ = *strPtr++;
1247         }
1248         m_passwordEnd = p - buffer.data();
1249
1250         // If we had any user info, add "@"
1251         if (p - buffer.data() != m_userStart)
1252             *p++ = '@';
1253
1254         // copy in the host, except in the case of a file URL with authority="localhost"
1255         if (!(isFile && hostIsLocalHost && !haveNonHostAuthorityPart)) {
1256             strPtr = url + hostStart;
1257             const char* hostEndPtr = url + hostEnd;
1258             while (strPtr < hostEndPtr)
1259                 *p++ = *strPtr++;
1260         }
1261         m_hostEnd = p - buffer.data();
1262
1263         // copy in the port
1264         if (hostEnd != portStart) {
1265             *p++ = ':';
1266             strPtr = url + portStart;
1267             const char *portEndPtr = url + portEnd;
1268             while (strPtr < portEndPtr)
1269                 *p++ = *strPtr++;
1270         }
1271         m_portEnd = p - buffer.data();
1272     } else
1273         m_userStart = m_userEnd = m_passwordEnd = m_hostEnd = m_portEnd = p - buffer.data();
1274
1275     // For canonicalization, ensure we have a '/' for no path.
1276     // Do this only for hierarchical URL with protocol http or https.
1277     if (m_protocolInHTTPFamily && hierarchical && pathEnd == pathStart)
1278         *p++ = '/';
1279
1280     // add path, escaping bad characters
1281     if (!hierarchical || !hasSlashDotOrDotDot(url))
1282         appendEscapingBadChars(p, url + pathStart, pathEnd - pathStart);
1283     else {
1284         CharBuffer pathBuffer(pathEnd - pathStart + 1);
1285         size_t length = copyPathRemovingDots(pathBuffer.data(), url, pathStart, pathEnd);
1286         appendEscapingBadChars(p, pathBuffer.data(), length);
1287     }
1288
1289     m_pathEnd = p - buffer.data();
1290
1291     // Find the position after the last slash in the path, or
1292     // the position before the path if there are no slashes in it.
1293     int i;
1294     for (i = m_pathEnd; i > m_portEnd; --i) {
1295         if (buffer[i - 1] == '/')
1296             break;
1297     }
1298     m_pathAfterLastSlash = i;
1299
1300     // add query, escaping bad characters
1301     appendEscapingBadChars(p, url + queryStart, queryEnd - queryStart);
1302     m_queryEnd = p - buffer.data();
1303
1304     // add fragment, escaping bad characters
1305     if (fragmentEnd != queryEnd) {
1306         *p++ = '#';
1307         appendEscapingBadChars(p, url + fragmentStart, fragmentEnd - fragmentStart);
1308     }
1309     m_fragmentEnd = p - buffer.data();
1310
1311     ASSERT(p - buffer.data() <= static_cast<int>(buffer.size()));
1312
1313     // If we didn't end up actually changing the original string and
1314     // it was already in a String, reuse it to avoid extra allocation.
1315     if (originalString && originalString->length() == static_cast<unsigned>(m_fragmentEnd) && strncmp(buffer.data(), url, m_fragmentEnd) == 0)
1316         m_string = *originalString;
1317     else
1318         m_string = String(buffer.data(), m_fragmentEnd);
1319
1320     m_isValid = true;
1321 }
1322
1323 bool equalIgnoringFragmentIdentifier(const KURL& a, const KURL& b)
1324 {
1325     if (a.m_queryEnd != b.m_queryEnd)
1326         return false;
1327     unsigned queryLength = a.m_queryEnd;
1328     for (unsigned i = 0; i < queryLength; ++i)
1329         if (a.string()[i] != b.string()[i])
1330             return false;
1331     return true;
1332 }
1333
1334 bool protocolHostAndPortAreEqual(const KURL& a, const KURL& b)
1335 {
1336     if (a.m_schemeEnd != b.m_schemeEnd)
1337         return false;
1338     int hostStartA = a.hostStart();
1339     int hostStartB = b.hostStart();
1340     if (a.m_hostEnd - hostStartA != b.m_hostEnd - hostStartB)
1341         return false;
1342
1343     // Check the scheme
1344     for (int i = 0; i < a.m_schemeEnd; ++i)
1345         if (a.string()[i] != b.string()[i])
1346             return false;
1347     
1348     // And the host
1349     for (int i = hostStartA; i < a.m_hostEnd; ++i)
1350         if (a.string()[i] != b.string()[i])
1351             return false;
1352     
1353     if (a.port() != b.port())
1354         return false;
1355
1356     return true;
1357 }
1358     
1359
1360 String encodeWithURLEscapeSequences(const String& notEncodedString)
1361 {
1362     CString asUTF8 = notEncodedString.utf8();
1363
1364     CharBuffer buffer(asUTF8.length() * 3 + 1);
1365     char* p = buffer.data();
1366
1367     const char* str = asUTF8.data();
1368     const char* strEnd = str + asUTF8.length();
1369     while (str < strEnd) {
1370         unsigned char c = *str++;
1371         if (isBadChar(c)) {
1372             *p++ = '%';
1373             *p++ = hexDigits[c >> 4];
1374             *p++ = hexDigits[c & 0xF];
1375         } else
1376             *p++ = c;
1377     }
1378
1379     ASSERT(p - buffer.data() <= static_cast<int>(buffer.size()));
1380
1381     return String(buffer.data(), p - buffer.data());
1382 }
1383
1384 // Appends the punycoded hostname identified by the given string and length to
1385 // the output buffer. The result will not be null terminated.
1386 static void appendEncodedHostname(UCharBuffer& buffer, const UChar* str, unsigned strLen)
1387 {
1388     // Needs to be big enough to hold an IDN-encoded name.
1389     // For host names bigger than this, we won't do IDN encoding, which is almost certainly OK.
1390     const unsigned hostnameBufferLength = 2048;
1391
1392     if (strLen > hostnameBufferLength || charactersAreAllASCII(str, strLen)) {
1393         buffer.append(str, strLen);
1394         return;
1395     }
1396
1397 #if USE(ICU_UNICODE)
1398     UChar hostnameBuffer[hostnameBufferLength];
1399     UErrorCode error = U_ZERO_ERROR;
1400     int32_t numCharactersConverted = uidna_IDNToASCII(str, strLen, hostnameBuffer,
1401         hostnameBufferLength, UIDNA_ALLOW_UNASSIGNED, 0, &error);
1402     if (error == U_ZERO_ERROR)
1403         buffer.append(hostnameBuffer, numCharactersConverted);
1404 #elif USE(QT4_UNICODE)
1405     QByteArray result = QUrl::toAce(String(str, strLen));
1406     buffer.append(result.constData(), result.length());
1407 #endif
1408 }
1409
1410 static void findHostnamesInMailToURL(const UChar* str, int strLen, Vector<pair<int, int> >& nameRanges)
1411 {
1412     // In a mailto: URL, host names come after a '@' character and end with a '>' or ',' or '?' or end of string character.
1413     // Skip quoted strings so that characters in them don't confuse us.
1414     // When we find a '?' character, we are past the part of the URL that contains host names.
1415
1416     nameRanges.clear();
1417
1418     int p = 0;
1419     while (1) {
1420         // Find start of host name or of quoted string.
1421         int hostnameOrStringStart = findFirstOf(str, strLen, p, "\"@?");
1422         if (hostnameOrStringStart == -1)
1423             return;
1424         UChar c = str[hostnameOrStringStart];
1425         p = hostnameOrStringStart + 1;
1426
1427         if (c == '?')
1428             return;
1429
1430         if (c == '@') {
1431             // Find end of host name.
1432             int hostnameStart = p;
1433             int hostnameEnd = findFirstOf(str, strLen, p, ">,?");
1434             bool done;
1435             if (hostnameEnd == -1) {
1436                 hostnameEnd = strLen;
1437                 done = true;
1438             } else {
1439                 p = hostnameEnd;
1440                 done = false;
1441             }
1442
1443             nameRanges.append(make_pair(hostnameStart, hostnameEnd));
1444
1445             if (done)
1446                 return;
1447         } else {
1448             // Skip quoted string.
1449             ASSERT(c == '"');
1450             while (1) {
1451                 int escapedCharacterOrStringEnd = findFirstOf(str, strLen, p, "\"\\");
1452                 if (escapedCharacterOrStringEnd == -1)
1453                     return;
1454
1455                 c = str[escapedCharacterOrStringEnd];
1456                 p = escapedCharacterOrStringEnd + 1;
1457
1458                 // If we are the end of the string, then break from the string loop back to the host name loop.
1459                 if (c == '"')
1460                     break;
1461
1462                 // Skip escaped character.
1463                 ASSERT(c == '\\');
1464                 if (p == strLen)
1465                     return;
1466
1467                 ++p;
1468             }
1469         }
1470     }
1471 }
1472
1473 static bool findHostnameInHierarchicalURL(const UChar* str, int strLen, int& startOffset, int& endOffset)
1474 {
1475     // Find the host name in a hierarchical URL.
1476     // It comes after a "://" sequence, with scheme characters preceding, and
1477     // this should be the first colon in the string.
1478     // It ends with the end of the string or a ":" or a path segment ending character.
1479     // If there is a "@" character, the host part is just the part after the "@".
1480     int separator = findFirstOf(str, strLen, 0, ":");
1481     if (separator == -1 || separator + 2 >= strLen ||
1482         str[separator + 1] != '/' || str[separator + 2] != '/')
1483         return false;
1484
1485     // Check that all characters before the :// are valid scheme characters.
1486     if (!isSchemeFirstChar(str[0]))
1487         return false;
1488     for (int i = 1; i < separator; ++i) {
1489         if (!isSchemeChar(str[i]))
1490             return false;
1491     }
1492
1493     // Start after the separator.
1494     int authorityStart = separator + 3;
1495
1496     // Find terminating character.
1497     int hostnameEnd = strLen;
1498     for (int i = authorityStart; i < strLen; ++i) {
1499         UChar c = str[i];
1500         if (c == ':' || (isPathSegmentEndChar(c) && c != 0)) {
1501             hostnameEnd = i;
1502             break;
1503         }
1504     }
1505
1506     // Find "@" for the start of the host name.
1507     int userInfoTerminator = findFirstOf(str, strLen, authorityStart, "@");
1508     int hostnameStart;
1509     if (userInfoTerminator == -1 || userInfoTerminator > hostnameEnd)
1510         hostnameStart = authorityStart;
1511     else
1512         hostnameStart = userInfoTerminator + 1;
1513
1514     startOffset = hostnameStart;
1515     endOffset = hostnameEnd;
1516     return true;
1517 }
1518
1519 // Converts all hostnames found in the given input to punycode, preserving the
1520 // rest of the URL unchanged. The output will NOT be null-terminated.
1521 static void encodeHostnames(const String& str, UCharBuffer& output)
1522 {
1523     output.clear();
1524
1525     if (protocolIs(str, "mailto")) {
1526         Vector<pair<int, int> > hostnameRanges;
1527         findHostnamesInMailToURL(str.characters(), str.length(), hostnameRanges);
1528         int n = hostnameRanges.size();
1529         int p = 0;
1530         for (int i = 0; i < n; ++i) {
1531             const pair<int, int>& r = hostnameRanges[i];
1532             output.append(&str.characters()[p], r.first - p);
1533             appendEncodedHostname(output, &str.characters()[r.first], r.second - r.first);
1534             p = r.second;
1535         }
1536         // This will copy either everything after the last hostname, or the
1537         // whole thing if there is no hostname.
1538         output.append(&str.characters()[p], str.length() - p);
1539     } else {
1540         int hostStart, hostEnd;
1541         if (findHostnameInHierarchicalURL(str.characters(), str.length(), hostStart, hostEnd)) {
1542             output.append(str.characters(), hostStart); // Before hostname.
1543             appendEncodedHostname(output, &str.characters()[hostStart], hostEnd - hostStart);
1544             output.append(&str.characters()[hostEnd], str.length() - hostEnd); // After hostname.
1545         } else {
1546             // No hostname to encode, return the input.
1547             output.append(str.characters(), str.length());
1548         }
1549     }
1550 }
1551
1552 static void encodeRelativeString(const String& rel, const TextEncoding& encoding, CharBuffer& output)
1553 {
1554     UCharBuffer s;
1555     encodeHostnames(rel, s);
1556
1557     TextEncoding pathEncoding(UTF8Encoding()); // Path is always encoded as UTF-8; other parts may depend on the scheme.
1558
1559     int pathEnd = -1;
1560     if (encoding != pathEncoding && encoding.isValid() && !protocolIs(rel, "mailto") && !protocolIs(rel, "data") && !protocolIsJavaScript(rel)) {
1561         // Find the first instance of either # or ?, keep pathEnd at -1 otherwise.
1562         pathEnd = findFirstOf(s.data(), s.size(), 0, "#?");
1563     }
1564
1565     if (pathEnd == -1) {
1566         CString decoded = pathEncoding.encode(s.data(), s.size(), URLEncodedEntitiesForUnencodables);
1567         output.resize(decoded.length());
1568         memcpy(output.data(), decoded.data(), decoded.length());
1569     } else {
1570         CString pathDecoded = pathEncoding.encode(s.data(), pathEnd, URLEncodedEntitiesForUnencodables);
1571         // Unencodable characters in URLs are represented by converting
1572         // them to XML entities and escaping non-alphanumeric characters.
1573         CString otherDecoded = encoding.encode(s.data() + pathEnd, s.size() - pathEnd, URLEncodedEntitiesForUnencodables);
1574
1575         output.resize(pathDecoded.length() + otherDecoded.length());
1576         memcpy(output.data(), pathDecoded.data(), pathDecoded.length());
1577         memcpy(output.data() + pathDecoded.length(), otherDecoded.data(), otherDecoded.length());
1578     }
1579     output.append('\0'); // null-terminate the output.
1580 }
1581
1582 static String substituteBackslashes(const String& string)
1583 {
1584     int questionPos = string.find('?');
1585     int hashPos = string.find('#');
1586     int pathEnd;
1587
1588     if (hashPos >= 0 && (questionPos < 0 || questionPos > hashPos))
1589         pathEnd = hashPos;
1590     else if (questionPos >= 0)
1591         pathEnd = questionPos;
1592     else
1593         pathEnd = string.length();
1594
1595     return string.left(pathEnd).replace('\\','/') + string.substring(pathEnd);
1596 }
1597
1598 bool KURL::isHierarchical() const
1599 {
1600     if (!m_isValid)
1601         return false;
1602     ASSERT(m_string[m_schemeEnd] == ':');
1603     return m_string[m_schemeEnd + 1] == '/';
1604 }
1605
1606 void KURL::copyToBuffer(CharBuffer& buffer) const
1607 {
1608     // FIXME: This throws away the high bytes of all the characters in the string!
1609     // That's fine for a valid URL, which is all ASCII, but not for invalid URLs.
1610     buffer.resize(m_string.length());
1611     copyASCII(m_string.characters(), m_string.length(), buffer.data());
1612 }
1613
1614 bool protocolIs(const String& url, const char* protocol)
1615 {
1616     // Do the comparison without making a new string object.
1617     assertProtocolIsGood(protocol);
1618     for (int i = 0; ; ++i) {
1619         if (!protocol[i])
1620             return url[i] == ':';
1621         if (toASCIILower(url[i]) != protocol[i])
1622             return false;
1623     }
1624 }
1625
1626 bool protocolIsJavaScript(const String& url)
1627 {
1628     return protocolIs(url, "javascript");
1629 }
1630
1631 bool isValidProtocol(const String& protocol)
1632 {
1633     if (!isSchemeFirstChar(protocol[0]))
1634         return false;
1635     unsigned protocolLength = protocol.length();
1636     for (unsigned i = 1; i < protocolLength; i++) {
1637         if (!isSchemeChar(protocol[i]))
1638             return false;
1639     }
1640     return true;
1641 }
1642
1643 bool isDefaultPortForProtocol(unsigned short port, const String& protocol)
1644 {
1645     if (protocol.isEmpty())
1646         return false;
1647
1648     typedef HashMap<String, unsigned, CaseFoldingHash> DefaultPortsMap;
1649     DEFINE_STATIC_LOCAL(DefaultPortsMap, defaultPorts, ());
1650     if (defaultPorts.isEmpty()) {
1651         defaultPorts.set("http", 80);
1652         defaultPorts.set("https", 443);
1653         defaultPorts.set("ftp", 21);
1654         defaultPorts.set("ftps", 990);
1655     }
1656     return defaultPorts.get(protocol) == port;
1657 }
1658
1659 bool portAllowed(const KURL& url)
1660 {
1661     unsigned short port = url.port();
1662
1663     // Since most URLs don't have a port, return early for the "no port" case.
1664     if (!port)
1665         return true;
1666
1667     // This blocked port list matches the port blocking that Mozilla implements.
1668     // See http://www.mozilla.org/projects/netlib/PortBanning.html for more information.
1669     static const unsigned short blockedPortList[] = {
1670         1,    // tcpmux
1671         7,    // echo
1672         9,    // discard
1673         11,   // systat
1674         13,   // daytime
1675         15,   // netstat
1676         17,   // qotd
1677         19,   // chargen
1678         20,   // FTP-data
1679         21,   // FTP-control
1680         22,   // SSH
1681         23,   // telnet
1682         25,   // SMTP
1683         37,   // time
1684         42,   // name
1685         43,   // nicname
1686         53,   // domain
1687         77,   // priv-rjs
1688         79,   // finger
1689         87,   // ttylink
1690         95,   // supdup
1691         101,  // hostriame
1692         102,  // iso-tsap
1693         103,  // gppitnp
1694         104,  // acr-nema
1695         109,  // POP2
1696         110,  // POP3
1697         111,  // sunrpc
1698         113,  // auth
1699         115,  // SFTP
1700         117,  // uucp-path
1701         119,  // nntp
1702         123,  // NTP
1703         135,  // loc-srv / epmap
1704         139,  // netbios
1705         143,  // IMAP2
1706         179,  // BGP
1707         389,  // LDAP
1708         465,  // SMTP+SSL
1709         512,  // print / exec
1710         513,  // login
1711         514,  // shell
1712         515,  // printer
1713         526,  // tempo
1714         530,  // courier
1715         531,  // Chat
1716         532,  // netnews
1717         540,  // UUCP
1718         556,  // remotefs
1719         563,  // NNTP+SSL
1720         587,  // ESMTP
1721         601,  // syslog-conn
1722         636,  // LDAP+SSL
1723         993,  // IMAP+SSL
1724         995,  // POP3+SSL
1725         2049, // NFS
1726         3659, // apple-sasl / PasswordServer [Apple addition]
1727         4045, // lockd
1728         6000, // X11
1729     };
1730     const unsigned short* const blockedPortListEnd = blockedPortList + sizeof(blockedPortList) / sizeof(blockedPortList[0]);
1731
1732 #ifndef NDEBUG
1733     // The port list must be sorted for binary_search to work.
1734     static bool checkedPortList = false;
1735     if (!checkedPortList) {
1736         for (const unsigned short* p = blockedPortList; p != blockedPortListEnd - 1; ++p)
1737             ASSERT(*p < *(p + 1));
1738         checkedPortList = true;
1739     }
1740 #endif
1741
1742     // If the port is not in the blocked port list, allow it.
1743     if (!binary_search(blockedPortList, blockedPortListEnd, port))
1744         return true;
1745
1746     // Allow ports 21 and 22 for FTP URLs, as Mozilla does.
1747     if ((port == 21 || port == 22) && url.protocolIs("ftp"))
1748         return true;
1749
1750     // Allow any port number in a file URL, since the port number is ignored.
1751     if (url.protocolIs("file"))
1752         return true;
1753
1754     return false;
1755 }
1756
1757 String mimeTypeFromDataURL(const String& url)
1758 {
1759     ASSERT(protocolIs(url, "data"));
1760     int index = url.find(';');
1761     if (index == -1)
1762         index = url.find(',');
1763     if (index != -1) {
1764         int len = index - 5;
1765         if (len > 0)
1766             return url.substring(5, len);
1767         return "text/plain"; // Data URLs with no MIME type are considered text/plain.
1768     }
1769     return "";
1770 }
1771
1772 const KURL& blankURL()
1773 {
1774     DEFINE_STATIC_LOCAL(KURL, staticBlankURL, (ParsedURLString, "about:blank"));
1775     return staticBlankURL;
1776 }
1777
1778 #ifndef NDEBUG
1779 void KURL::print() const
1780 {
1781     printf("%s\n", m_string.utf8().data());
1782 }
1783 #endif
1784
1785 }
1786
1787 #endif  // !USE(GOOGLEURL)