Part 2 of removing PlatformString.h, remove PlatformString.h
[WebKit-https.git] / Source / WebCore / platform / LinkHash.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  *           (C) 2001 Dirk Mueller (mueller@kde.org)
5  *           (C) 2006 Alexey Proskuryakov (ap@webkit.org)
6  * Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library 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 GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  */
23
24 #include "config.h"
25 #include "KURL.h"
26 #include "LinkHash.h"
27 #include <wtf/text/AtomicString.h>
28 #include <wtf/text/StringHash.h>
29 #include <wtf/text/WTFString.h>
30
31 namespace WebCore {
32
33 static inline size_t findSlashDotDotSlash(const UChar* characters, size_t length, size_t position)
34 {
35     if (length < 4)
36         return notFound;
37     size_t loopLimit = length - 3;
38     for (size_t i = position; i < loopLimit; ++i) {
39         if (characters[i] == '/' && characters[i + 1] == '.' && characters[i + 2] == '.' && characters[i + 3] == '/')
40             return i;
41     }
42     return notFound;
43 }
44
45 static inline size_t findSlashSlash(const UChar* characters, size_t length, size_t position)
46 {
47     if (length < 2)
48         return notFound;
49     size_t loopLimit = length - 1;
50     for (size_t i = position; i < loopLimit; ++i) {
51         if (characters[i] == '/' && characters[i + 1] == '/')
52             return i;
53     }
54     return notFound;
55 }
56
57 static inline size_t findSlashDotSlash(const UChar* characters, size_t length, size_t position)
58 {
59     if (length < 3)
60         return notFound;
61     size_t loopLimit = length - 2;
62     for (size_t i = position; i < loopLimit; ++i) {
63         if (characters[i] == '/' && characters[i + 1] == '.' && characters[i + 2] == '/')
64             return i;
65     }
66     return notFound;
67 }
68
69 static inline bool containsColonSlashSlash(const UChar* characters, unsigned length)
70 {
71     if (length < 3)
72         return false;
73     unsigned loopLimit = length - 2;
74     for (unsigned i = 0; i < loopLimit; ++i) {
75         if (characters[i] == ':' && characters[i + 1] == '/' && characters[i + 2] == '/')
76             return true;
77     }
78     return false;
79 }
80
81 static inline void squeezeOutNullCharacters(Vector<UChar, 512>& string)
82 {
83     size_t size = string.size();
84     size_t i = 0;
85     for (i = 0; i < size; ++i) {
86         if (!string[i])
87             break;
88     }
89     if (i == size)
90         return;
91     size_t j = i;
92     for (++i; i < size; ++i) {
93         if (UChar character = string[i])
94             string[j++] = character;
95     }
96     ASSERT(j < size);
97     string.shrink(j);
98 }
99
100 static void cleanSlashDotDotSlashes(Vector<UChar, 512>& path, size_t firstSlash)
101 {
102     size_t slash = firstSlash;
103     do {
104         size_t previousSlash = slash ? reverseFind(path.data(), path.size(), '/', slash - 1) : notFound;
105         // Don't remove the host, i.e. http://foo.org/../foo.html
106         if (previousSlash == notFound || (previousSlash > 3 && path[previousSlash - 2] == ':' && path[previousSlash - 1] == '/')) {
107             path[slash] = 0;
108             path[slash + 1] = 0;
109             path[slash + 2] = 0;
110         } else {
111             for (size_t i = previousSlash; i < slash + 3; ++i)
112                 path[i] = 0;
113         }
114         slash += 3;
115     } while ((slash = findSlashDotDotSlash(path.data(), path.size(), slash)) != notFound);
116     squeezeOutNullCharacters(path);
117 }
118
119 static void mergeDoubleSlashes(Vector<UChar, 512>& path, size_t firstSlash)
120 {
121     size_t refPos = find(path.data(), path.size(), '#');
122     if (!refPos || refPos == notFound)
123         refPos = path.size();
124
125     size_t slash = firstSlash;
126     while (slash < refPos) {
127         if (!slash || path[slash - 1] != ':')
128             path[slash++] = 0;
129         else
130             slash += 2;
131         if ((slash = findSlashSlash(path.data(), path.size(), slash)) == notFound)
132             break;
133     }
134     squeezeOutNullCharacters(path);
135 }
136
137 static void cleanSlashDotSlashes(Vector<UChar, 512>& path, size_t firstSlash)
138 {
139     size_t slash = firstSlash;
140     do {
141         path[slash] = 0;
142         path[slash + 1] = 0;
143         slash += 2;
144     } while ((slash = findSlashDotSlash(path.data(), path.size(), slash)) != notFound);
145     squeezeOutNullCharacters(path);
146 }
147
148 static inline void cleanPath(Vector<UChar, 512>& path)
149 {
150     // FIXME: Should not do this in the query or anchor part of the URL.
151     size_t firstSlash = findSlashDotDotSlash(path.data(), path.size(), 0);
152     if (firstSlash != notFound)
153         cleanSlashDotDotSlashes(path, firstSlash);
154
155     // FIXME: Should not do this in the query part.
156     firstSlash = findSlashSlash(path.data(), path.size(), 0);
157     if (firstSlash != notFound)
158         mergeDoubleSlashes(path, firstSlash);
159
160     // FIXME: Should not do this in the query or anchor part.
161     firstSlash = findSlashDotSlash(path.data(), path.size(), 0);
162     if (firstSlash != notFound)
163         cleanSlashDotSlashes(path, firstSlash);
164 }
165
166 static inline bool matchLetter(UChar c, UChar lowercaseLetter)
167 {
168     return (c | 0x20) == lowercaseLetter;
169 }
170
171 static inline bool needsTrailingSlash(const UChar* characters, unsigned length)
172 {
173     if (length < 6)
174         return false;
175     if (!matchLetter(characters[0], 'h')
176             || !matchLetter(characters[1], 't')
177             || !matchLetter(characters[2], 't')
178             || !matchLetter(characters[3], 'p'))
179         return false;
180     if (!(characters[4] == ':'
181             || (matchLetter(characters[4], 's') && characters[5] == ':')))
182         return false;
183
184     unsigned pos = characters[4] == ':' ? 5 : 6;
185
186     // Skip initial two slashes if present.
187     if (pos + 1 < length && characters[pos] == '/' && characters[pos + 1] == '/')
188         pos += 2;
189
190     // Find next slash.
191     while (pos < length && characters[pos] != '/')
192         ++pos;
193
194     return pos == length;
195 }
196
197 static ALWAYS_INLINE LinkHash visitedLinkHashInline(const UChar* url, unsigned length)
198 {
199     return AlreadyHashed::avoidDeletedValue(StringHasher::computeHash(url, length));
200 }
201
202 LinkHash visitedLinkHash(const UChar* url, unsigned length)
203 {
204     return visitedLinkHashInline(url, length);
205 }
206
207 static ALWAYS_INLINE void visitedURLInline(const KURL& base, const AtomicString& attributeURL, Vector<UChar, 512>& buffer)
208 {
209     if (attributeURL.isNull())
210         return;
211
212     const UChar* characters = attributeURL.characters();
213     unsigned length = attributeURL.length();
214
215     // This is a poor man's completeURL. Faster with less memory allocation.
216     // FIXME: It's missing a lot of what completeURL does and a lot of what KURL does.
217     // For example, it does not handle international domain names properly.
218
219     // FIXME: It is wrong that we do not do further processing on strings that have "://" in them:
220     //    1) The "://" could be in the query or anchor.
221     //    2) The URL's path could have a "/./" or a "/../" or a "//" sequence in it.
222
223     // FIXME: needsTrailingSlash does not properly return true for a URL that has no path, but does
224     // have a query or anchor.
225
226     bool hasColonSlashSlash = containsColonSlashSlash(characters, length);
227
228     if (hasColonSlashSlash && !needsTrailingSlash(characters, length)) {
229         buffer.append(attributeURL.characters(), attributeURL.length());
230         return;
231     }
232
233
234     if (hasColonSlashSlash) {
235         // FIXME: This is incorrect for URLs that have a query or anchor; the "/" needs to go at the
236         // end of the path, *before* the query or anchor.
237         buffer.append(characters, length);
238         buffer.append('/');
239         return;
240     }
241
242     if (!length)
243         buffer.append(base.string().characters(), base.string().length());
244     else {
245         switch (characters[0]) {
246             case '/':
247                 buffer.append(base.string().characters(), base.pathStart());
248                 break;
249             case '#':
250                 buffer.append(base.string().characters(), base.pathEnd());
251                 break;
252             default:
253                 buffer.append(base.string().characters(), base.pathAfterLastSlash());
254                 break;
255         }
256     }
257     buffer.append(characters, length);
258     cleanPath(buffer);
259     if (needsTrailingSlash(buffer.data(), buffer.size())) {
260         // FIXME: This is incorrect for URLs that have a query or anchor; the "/" needs to go at the
261         // end of the path, *before* the query or anchor.
262         buffer.append('/');
263     }
264
265     return;
266 }
267
268 void visitedURL(const KURL& base, const AtomicString& attributeURL, Vector<UChar, 512>& buffer)
269 {
270     return visitedURLInline(base, attributeURL, buffer);
271 }
272
273 LinkHash visitedLinkHash(const KURL& base, const AtomicString& attributeURL)
274 {
275     Vector<UChar, 512> url;
276     visitedURLInline(base, attributeURL, url);
277     if (url.isEmpty())
278         return 0;
279
280     return visitedLinkHashInline(url.data(), url.size());
281 }
282
283 }  // namespace WebCore