1/*
2 * Copyright (C) 2006, 2007 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 COMPUTER, 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#include "WebKitDLL.h"
28#include "WebHistory.h"
29
30#include "CFDictionaryPropertyBag.h"
31#include "MemoryStream.h"
32#include "WebKit.h"
33#include "MarshallingHelpers.h"
34#include "WebHistoryItem.h"
35#include "WebKit.h"
36#include "WebNotificationCenter.h"
37#include "WebPreferences.h"
38#include <CoreFoundation/CoreFoundation.h>
39#include <WebCore/HistoryItem.h>
40#include <WebCore/HistoryPropertyList.h>
41#include <WebCore/KURL.h>
42#include <WebCore/PageGroup.h>
43#include <WebCore/SharedBuffer.h>
44#include <functional>
45#include <wtf/StdLibExtras.h>
46#include <wtf/Vector.h>
47
48using namespace WebCore;
49using namespace std;
50
51CFStringRef DatesArrayKey = CFSTR("WebHistoryDates");
52CFStringRef FileVersionKey = CFSTR("WebHistoryFileVersion");
53
54#define currentFileVersion 1
55
56class WebHistoryWriter : public HistoryPropertyListWriter {
57public:
58    WebHistoryWriter(const WebHistory::DateToEntriesMap&);
59
60private:
61    virtual void writeHistoryItems(BinaryPropertyListObjectStream&);
62
63    const WebHistory::DateToEntriesMap& m_entriesByDate;
64    Vector<WebHistory::DateKey> m_dateKeys;
65};
66
67WebHistoryWriter::WebHistoryWriter(const WebHistory::DateToEntriesMap& entriesByDate)
68    : m_entriesByDate(entriesByDate)
69{
70    copyKeysToVector(m_entriesByDate, m_dateKeys);
71    sort(m_dateKeys.begin(), m_dateKeys.end());
72}
73
74void WebHistoryWriter::writeHistoryItems(BinaryPropertyListObjectStream& stream)
75{
76    for (int dateIndex = m_dateKeys.size() - 1; dateIndex >= 0; --dateIndex) {
77        // get the entries for that date
78        CFArrayRef entries = m_entriesByDate.get(m_dateKeys[dateIndex]).get();
79        CFIndex entriesCount = CFArrayGetCount(entries);
80        for (CFIndex j = entriesCount - 1; j >= 0; --j) {
81            IWebHistoryItem* item = (IWebHistoryItem*) CFArrayGetValueAtIndex(entries, j);
82            COMPtr<WebHistoryItem> webItem(Query, item);
83            if (!webItem)
84                continue;
85
86            writeHistoryItem(stream, webItem->historyItem());
87        }
88    }
89}
90
91static bool areEqualOrClose(double d1, double d2)
92{
93    double diff = d1-d2;
94    return (diff < .000001 && diff > -.000001);
95}
96
97static COMPtr<CFDictionaryPropertyBag> createUserInfoFromArray(BSTR notificationStr, CFArrayRef arrayItem)
98{
99    RetainPtr<CFMutableDictionaryRef> dictionary(AdoptCF,
100        CFDictionaryCreateMutable(0, 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks));
101
102    RetainPtr<CFStringRef> key(AdoptCF, MarshallingHelpers::BSTRToCFStringRef(notificationStr));
103    CFDictionaryAddValue(dictionary.get(), key.get(), arrayItem);
104
105    COMPtr<CFDictionaryPropertyBag> result = CFDictionaryPropertyBag::createInstance();
106    result->setDictionary(dictionary.get());
107    return result;
108}
109
110static COMPtr<CFDictionaryPropertyBag> createUserInfoFromHistoryItem(BSTR notificationStr, IWebHistoryItem* item)
111{
112    // reference counting of item added to the array is managed by the CFArray value callbacks
113    RetainPtr<CFArrayRef> itemList(AdoptCF, CFArrayCreate(0, (const void**) &item, 1, &MarshallingHelpers::kIUnknownArrayCallBacks));
114    COMPtr<CFDictionaryPropertyBag> info = createUserInfoFromArray(notificationStr, itemList.get());
115    return info;
116}
117
118// WebHistory -----------------------------------------------------------------
119
120WebHistory::WebHistory()
121: m_refCount(0)
122, m_preferences(0)
123{
124    gClassCount++;
125    gClassNameCount.add("WebHistory");
126
127    m_entriesByURL.adoptCF(CFDictionaryCreateMutable(0, 0, &kCFTypeDictionaryKeyCallBacks, &MarshallingHelpers::kIUnknownDictionaryValueCallBacks));
128
129    m_preferences = WebPreferences::sharedStandardPreferences();
130}
131
132WebHistory::~WebHistory()
133{
134    gClassCount--;
135    gClassNameCount.remove("WebHistory");
136}
137
138WebHistory* WebHistory::createInstance()
139{
140    WebHistory* instance = new WebHistory();
141    instance->AddRef();
142    return instance;
143}
144
145HRESULT WebHistory::postNotification(NotificationType notifyType, IPropertyBag* userInfo /*=0*/)
146{
147    IWebNotificationCenter* nc = WebNotificationCenter::defaultCenterInternal();
148    HRESULT hr = nc->postNotificationName(getNotificationString(notifyType), static_cast<IWebHistory*>(this), userInfo);
149    if (FAILED(hr))
150        return hr;
151
152    return S_OK;
153}
154
155BSTR WebHistory::getNotificationString(NotificationType notifyType)
156{
157    static BSTR keys[6] = {0};
158    if (!keys[0]) {
159        keys[0] = SysAllocString(WebHistoryItemsAddedNotification);
160        keys[1] = SysAllocString(WebHistoryItemsRemovedNotification);
161        keys[2] = SysAllocString(WebHistoryAllItemsRemovedNotification);
162        keys[3] = SysAllocString(WebHistoryLoadedNotification);
163        keys[4] = SysAllocString(WebHistoryItemsDiscardedWhileLoadingNotification);
164        keys[5] = SysAllocString(WebHistorySavedNotification);
165    }
166    return keys[notifyType];
167}
168
169// IUnknown -------------------------------------------------------------------
170
171HRESULT STDMETHODCALLTYPE WebHistory::QueryInterface(REFIID riid, void** ppvObject)
172{
173    *ppvObject = 0;
174    if (IsEqualGUID(riid, CLSID_WebHistory))
175        *ppvObject = this;
176    else if (IsEqualGUID(riid, IID_IUnknown))
177        *ppvObject = static_cast<IWebHistory*>(this);
178    else if (IsEqualGUID(riid, IID_IWebHistory))
179        *ppvObject = static_cast<IWebHistory*>(this);
180    else if (IsEqualGUID(riid, IID_IWebHistoryPrivate))
181        *ppvObject = static_cast<IWebHistoryPrivate*>(this);
182    else
183        return E_NOINTERFACE;
184
185    AddRef();
186    return S_OK;
187}
188
189ULONG STDMETHODCALLTYPE WebHistory::AddRef(void)
190{
191    return ++m_refCount;
192}
193
194ULONG STDMETHODCALLTYPE WebHistory::Release(void)
195{
196    ULONG newRef = --m_refCount;
197    if (!newRef)
198        delete(this);
199
200    return newRef;
201}
202
203// IWebHistory ----------------------------------------------------------------
204
205static inline COMPtr<WebHistory>& sharedHistoryStorage()
206{
207    DEFINE_STATIC_LOCAL(COMPtr<WebHistory>, sharedHistory, ());
208    return sharedHistory;
209}
210
211WebHistory* WebHistory::sharedHistory()
212{
213    return sharedHistoryStorage().get();
214}
215
216HRESULT STDMETHODCALLTYPE WebHistory::optionalSharedHistory(
217    /* [retval][out] */ IWebHistory** history)
218{
219    *history = sharedHistory();
220    if (*history)
221        (*history)->AddRef();
222    return S_OK;
223}
224
225HRESULT STDMETHODCALLTYPE WebHistory::setOptionalSharedHistory(
226    /* [in] */ IWebHistory* history)
227{
228    if (sharedHistoryStorage() == history)
229        return S_OK;
230    sharedHistoryStorage().query(history);
231    PageGroup::setShouldTrackVisitedLinks(sharedHistoryStorage());
232    PageGroup::removeAllVisitedLinks();
233    return S_OK;
234}
235
236HRESULT STDMETHODCALLTYPE WebHistory::loadFromURL(
237    /* [in] */ BSTR url,
238    /* [out] */ IWebError** error,
239    /* [retval][out] */ BOOL* succeeded)
240{
241    HRESULT hr = S_OK;
242    RetainPtr<CFMutableArrayRef> discardedItems(AdoptCF,
243        CFArrayCreateMutable(0, 0, &MarshallingHelpers::kIUnknownArrayCallBacks));
244
245    RetainPtr<CFURLRef> urlRef(AdoptCF, MarshallingHelpers::BSTRToCFURLRef(url));
246
247    hr = loadHistoryGutsFromURL(urlRef.get(), discardedItems.get(), error);
248    if (FAILED(hr))
249        goto exit;
250
251    hr = postNotification(kWebHistoryLoadedNotification);
252    if (FAILED(hr))
253        goto exit;
254
255    if (CFArrayGetCount(discardedItems.get()) > 0) {
256        COMPtr<CFDictionaryPropertyBag> userInfo = createUserInfoFromArray(getNotificationString(kWebHistoryItemsDiscardedWhileLoadingNotification), discardedItems.get());
257        hr = postNotification(kWebHistoryItemsDiscardedWhileLoadingNotification, userInfo.get());
258        if (FAILED(hr))
259            goto exit;
260    }
261
262exit:
263    if (succeeded)
264        *succeeded = SUCCEEDED(hr);
265    return hr;
266}
267
268static CFDictionaryRef createHistoryListFromStream(CFReadStreamRef stream, CFPropertyListFormat format)
269{
270    return (CFDictionaryRef)CFPropertyListCreateFromStream(0, stream, 0, kCFPropertyListImmutable, &format, 0);
271}
272
273HRESULT WebHistory::loadHistoryGutsFromURL(CFURLRef url, CFMutableArrayRef discardedItems, IWebError** /*error*/) //FIXME
274{
275    CFPropertyListFormat format = kCFPropertyListBinaryFormat_v1_0 | kCFPropertyListXMLFormat_v1_0;
276    HRESULT hr = S_OK;
277    int numberOfItemsLoaded = 0;
278
279    RetainPtr<CFReadStreamRef> stream(AdoptCF, CFReadStreamCreateWithFile(0, url));
280    if (!stream)
281        return E_FAIL;
282
283    if (!CFReadStreamOpen(stream.get()))
284        return E_FAIL;
285
286    RetainPtr<CFDictionaryRef> historyList(AdoptCF, createHistoryListFromStream(stream.get(), format));
287    CFReadStreamClose(stream.get());
288
289    if (!historyList)
290        return E_FAIL;
291
292    CFNumberRef fileVersionObject = (CFNumberRef)CFDictionaryGetValue(historyList.get(), FileVersionKey);
293    int fileVersion;
294    if (!CFNumberGetValue(fileVersionObject, kCFNumberIntType, &fileVersion))
295        return E_FAIL;
296
297    if (fileVersion > currentFileVersion)
298        return E_FAIL;
299
300    CFArrayRef datesArray = (CFArrayRef)CFDictionaryGetValue(historyList.get(), DatesArrayKey);
301
302    int itemCountLimit;
303    hr = historyItemLimit(&itemCountLimit);
304    if (FAILED(hr))
305        return hr;
306
307    CFAbsoluteTime limitDate;
308    hr = ageLimitDate(&limitDate);
309    if (FAILED(hr))
310        return hr;
311
312    bool ageLimitPassed = false;
313    bool itemLimitPassed = false;
314
315    CFIndex itemCount = CFArrayGetCount(datesArray);
316    for (CFIndex i = 0; i < itemCount; ++i) {
317        CFDictionaryRef itemAsDictionary = (CFDictionaryRef)CFArrayGetValueAtIndex(datesArray, i);
318        COMPtr<WebHistoryItem> item(AdoptCOM, WebHistoryItem::createInstance());
319        hr = item->initFromDictionaryRepresentation((void*)itemAsDictionary);
320        if (FAILED(hr))
321            return hr;
322
323        // item without URL is useless; data on disk must have been bad; ignore
324        BOOL hasURL;
325        hr = item->hasURLString(&hasURL);
326        if (FAILED(hr))
327            return hr;
328
329        if (hasURL) {
330            // Test against date limit. Since the items are ordered newest to oldest, we can stop comparing
331            // once we've found the first item that's too old.
332            if (!ageLimitPassed) {
333                DATE lastVisitedTime;
334                hr = item->lastVisitedTimeInterval(&lastVisitedTime);
335                if (FAILED(hr))
336                    return hr;
337                if (timeToDate(MarshallingHelpers::DATEToCFAbsoluteTime(lastVisitedTime)) <= limitDate)
338                    ageLimitPassed = true;
339            }
340            if (ageLimitPassed || itemLimitPassed)
341                CFArrayAppendValue(discardedItems, item.get());
342            else {
343                bool added;
344                addItem(item.get(), true, &added); // ref is added inside addItem
345                if (added)
346                    ++numberOfItemsLoaded;
347                if (numberOfItemsLoaded == itemCountLimit)
348                    itemLimitPassed = true;
349            }
350        }
351    }
352    return hr;
353}
354
355HRESULT STDMETHODCALLTYPE WebHistory::saveToURL(
356    /* [in] */ BSTR url,
357    /* [out] */ IWebError** error,
358    /* [retval][out] */ BOOL* succeeded)
359{
360    HRESULT hr = S_OK;
361    RetainPtr<CFURLRef> urlRef(AdoptCF, MarshallingHelpers::BSTRToCFURLRef(url));
362
363    hr = saveHistoryGuts(urlRef.get(), error);
364
365    if (succeeded)
366        *succeeded = SUCCEEDED(hr);
367    if (SUCCEEDED(hr))
368        hr = postNotification(kWebHistorySavedNotification);
369
370    return hr;
371}
372
373HRESULT WebHistory::saveHistoryGuts(CFURLRef url, IWebError** error)
374{
375    HRESULT hr = S_OK;
376
377    // FIXME: Correctly report error when new API is ready.
378    if (error)
379        *error = 0;
380
381    RetainPtr<CFDataRef> data = this->data();
382
383    RetainPtr<CFWriteStreamRef> stream(AdoptCF, CFWriteStreamCreateWithFile(kCFAllocatorDefault, url));
384    if (!stream)
385        return E_FAIL;
386
387    if (!CFWriteStreamOpen(stream.get()))
388        return E_FAIL;
389
390    const UInt8* dataPtr = CFDataGetBytePtr(data.get());
391    CFIndex length = CFDataGetLength(data.get());
392
393    while (length) {
394        CFIndex bytesWritten = CFWriteStreamWrite(stream.get(), dataPtr, length);
395        if (bytesWritten <= 0) {
396            hr = E_FAIL;
397            break;
398        }
399        dataPtr += bytesWritten;
400        length -= bytesWritten;
401    }
402
403    CFWriteStreamClose(stream.get());
404
405    return hr;
406}
407
408HRESULT STDMETHODCALLTYPE WebHistory::addItems(
409    /* [in] */ int itemCount,
410    /* [in] */ IWebHistoryItem** items)
411{
412    // There is no guarantee that the incoming entries are in any particular
413    // order, but if this is called with a set of entries that were created by
414    // iterating through the results of orderedLastVisitedDays and orderedItemsLastVisitedOnDay
415    // then they will be ordered chronologically from newest to oldest. We can make adding them
416    // faster (fewer compares) by inserting them from oldest to newest.
417
418    HRESULT hr;
419    for (int i = itemCount - 1; i >= 0; --i) {
420        hr = addItem(items[i], false, 0);
421        if (FAILED(hr))
422            return hr;
423    }
424
425    return S_OK;
426}
427
428HRESULT STDMETHODCALLTYPE WebHistory::removeItems(
429    /* [in] */ int itemCount,
430    /* [in] */ IWebHistoryItem** items)
431{
432    HRESULT hr;
433    for (int i = 0; i < itemCount; ++i) {
434        hr = removeItem(items[i]);
435        if (FAILED(hr))
436            return hr;
437    }
438
439    return S_OK;
440}
441
442HRESULT STDMETHODCALLTYPE WebHistory::removeAllItems( void)
443{
444    m_entriesByDate.clear();
445    m_orderedLastVisitedDays.clear();
446
447    CFIndex itemCount = CFDictionaryGetCount(m_entriesByURL.get());
448    Vector<IWebHistoryItem*> itemsVector(itemCount);
449    CFDictionaryGetKeysAndValues(m_entriesByURL.get(), 0, (const void**)itemsVector.data());
450    RetainPtr<CFArrayRef> allItems(AdoptCF, CFArrayCreate(kCFAllocatorDefault, (const void**)itemsVector.data(), itemCount, &MarshallingHelpers::kIUnknownArrayCallBacks));
451
452    CFDictionaryRemoveAllValues(m_entriesByURL.get());
453
454    PageGroup::removeAllVisitedLinks();
455
456    COMPtr<CFDictionaryPropertyBag> userInfo = createUserInfoFromArray(getNotificationString(kWebHistoryAllItemsRemovedNotification), allItems.get());
457    return postNotification(kWebHistoryAllItemsRemovedNotification, userInfo.get());
458}
459
460HRESULT STDMETHODCALLTYPE WebHistory::orderedLastVisitedDays(
461    /* [out][in] */ int* count,
462    /* [in] */ DATE* calendarDates)
463{
464    int dateCount = m_entriesByDate.size();
465    if (!calendarDates) {
466        *count = dateCount;
467        return S_OK;
468    }
469
470    if (*count < dateCount) {
471        *count = dateCount;
472        return E_FAIL;
473    }
474
475    *count = dateCount;
476    if (!m_orderedLastVisitedDays) {
477        m_orderedLastVisitedDays = adoptArrayPtr(new DATE[dateCount]);
478        DateToEntriesMap::const_iterator::Keys end = m_entriesByDate.end().keys();
479        int i = 0;
480        for (DateToEntriesMap::const_iterator::Keys it = m_entriesByDate.begin().keys(); it != end; ++it, ++i)
481            m_orderedLastVisitedDays[i] = MarshallingHelpers::CFAbsoluteTimeToDATE(*it);
482        // Use std::greater to sort the days in descending order (i.e., most-recent first).
483        sort(m_orderedLastVisitedDays.get(), m_orderedLastVisitedDays.get() + dateCount, greater<DATE>());
484    }
485
486    memcpy(calendarDates, m_orderedLastVisitedDays.get(), dateCount * sizeof(DATE));
487    return S_OK;
488}
489
490HRESULT STDMETHODCALLTYPE WebHistory::orderedItemsLastVisitedOnDay(
491    /* [out][in] */ int* count,
492    /* [in] */ IWebHistoryItem** items,
493    /* [in] */ DATE calendarDate)
494{
495    DateKey dateKey;
496    if (!findKey(&dateKey, MarshallingHelpers::DATEToCFAbsoluteTime(calendarDate))) {
497        *count = 0;
498        return 0;
499    }
500
501    CFArrayRef entries = m_entriesByDate.get(dateKey).get();
502    if (!entries) {
503        *count = 0;
504        return 0;
505    }
506
507    int newCount = CFArrayGetCount(entries);
508
509    if (!items) {
510        *count = newCount;
511        return S_OK;
512    }
513
514    if (*count < newCount) {
515        *count = newCount;
516        return E_FAIL;
517    }
518
519    *count = newCount;
520    for (int i = 0; i < newCount; i++) {
521        IWebHistoryItem* item = (IWebHistoryItem*)CFArrayGetValueAtIndex(entries, i);
522        item->AddRef();
523        items[i] = item;
524    }
525
526    return S_OK;
527}
528
529HRESULT STDMETHODCALLTYPE WebHistory::allItems(
530    /* [out][in] */ int* count,
531    /* [out][retval] */ IWebHistoryItem** items)
532{
533    int entriesByURLCount = CFDictionaryGetCount(m_entriesByURL.get());
534
535    if (!items) {
536        *count = entriesByURLCount;
537        return S_OK;
538    }
539
540    if (*count < entriesByURLCount) {
541        *count = entriesByURLCount;
542        return E_FAIL;
543    }
544
545    *count = entriesByURLCount;
546    CFDictionaryGetKeysAndValues(m_entriesByURL.get(), 0, (const void**)items);
547    for (int i = 0; i < entriesByURLCount; i++)
548        items[i]->AddRef();
549
550    return S_OK;
551}
552
553HRESULT WebHistory::data(IStream** stream)
554{
555    if (!stream)
556        return E_POINTER;
557
558    *stream = 0;
559
560    RetainPtr<CFDataRef> historyData = data();
561    if (!historyData)
562        return S_OK;
563
564    COMPtr<MemoryStream> result = MemoryStream::createInstance(SharedBuffer::wrapCFData(historyData.get()));
565    return result.copyRefTo(stream);
566}
567
568HRESULT WebHistory::setVisitedLinkTrackingEnabled(BOOL visitedLinkTrackingEnabled)
569{
570    PageGroup::setShouldTrackVisitedLinks(visitedLinkTrackingEnabled);
571    return S_OK;
572}
573
574HRESULT WebHistory::removeAllVisitedLinks()
575{
576    PageGroup::removeAllVisitedLinks();
577    return S_OK;
578}
579
580HRESULT STDMETHODCALLTYPE WebHistory::setHistoryItemLimit(
581    /* [in] */ int limit)
582{
583    if (!m_preferences)
584        return E_FAIL;
585    return m_preferences->setHistoryItemLimit(limit);
586}
587
588HRESULT STDMETHODCALLTYPE WebHistory::historyItemLimit(
589    /* [retval][out] */ int* limit)
590{
591    if (!m_preferences)
592        return E_FAIL;
593    return m_preferences->historyItemLimit(limit);
594}
595
596HRESULT STDMETHODCALLTYPE WebHistory::setHistoryAgeInDaysLimit(
597    /* [in] */ int limit)
598{
599    if (!m_preferences)
600        return E_FAIL;
601    return m_preferences->setHistoryAgeInDaysLimit(limit);
602}
603
604HRESULT STDMETHODCALLTYPE WebHistory::historyAgeInDaysLimit(
605    /* [retval][out] */ int* limit)
606{
607    if (!m_preferences)
608        return E_FAIL;
609    return m_preferences->historyAgeInDaysLimit(limit);
610}
611
612HRESULT WebHistory::removeItem(IWebHistoryItem* entry)
613{
614    HRESULT hr = S_OK;
615    BSTR urlBStr = 0;
616
617    hr = entry->URLString(&urlBStr);
618    if (FAILED(hr))
619        return hr;
620
621    RetainPtr<CFStringRef> urlString(AdoptCF, MarshallingHelpers::BSTRToCFStringRef(urlBStr));
622    SysFreeString(urlBStr);
623
624    // If this exact object isn't stored, then make no change.
625    // FIXME: Is this the right behavior if this entry isn't present, but another entry for the same URL is?
626    // Maybe need to change the API to make something like removeEntryForURLString public instead.
627    IWebHistoryItem *matchingEntry = (IWebHistoryItem*)CFDictionaryGetValue(m_entriesByURL.get(), urlString.get());
628    if (matchingEntry != entry)
629        return E_FAIL;
630
631    hr = removeItemForURLString(urlString.get());
632    if (FAILED(hr))
633        return hr;
634
635    COMPtr<CFDictionaryPropertyBag> userInfo = createUserInfoFromHistoryItem(
636        getNotificationString(kWebHistoryItemsRemovedNotification), entry);
637    hr = postNotification(kWebHistoryItemsRemovedNotification, userInfo.get());
638
639    return hr;
640}
641
642HRESULT WebHistory::addItem(IWebHistoryItem* entry, bool discardDuplicate, bool* added)
643{
644    HRESULT hr = S_OK;
645
646    if (!entry)
647        return E_FAIL;
648
649    BSTR urlBStr = 0;
650    hr = entry->URLString(&urlBStr);
651    if (FAILED(hr))
652        return hr;
653
654    RetainPtr<CFStringRef> urlString(AdoptCF, MarshallingHelpers::BSTRToCFStringRef(urlBStr));
655    SysFreeString(urlBStr);
656
657    COMPtr<IWebHistoryItem> oldEntry((IWebHistoryItem*) CFDictionaryGetValue(
658        m_entriesByURL.get(), urlString.get()));
659
660    if (oldEntry) {
661        if (discardDuplicate) {
662            if (added)
663                *added = false;
664            return S_OK;
665        }
666
667        removeItemForURLString(urlString.get());
668
669        // If we already have an item with this URL, we need to merge info that drives the
670        // URL autocomplete heuristics from that item into the new one.
671        IWebHistoryItemPrivate* entryPriv;
672        hr = entry->QueryInterface(IID_IWebHistoryItemPrivate, (void**)&entryPriv);
673        if (SUCCEEDED(hr)) {
674            entryPriv->mergeAutoCompleteHints(oldEntry.get());
675            entryPriv->Release();
676        }
677    }
678
679    hr = addItemToDateCaches(entry);
680    if (FAILED(hr))
681        return hr;
682
683    CFDictionarySetValue(m_entriesByURL.get(), urlString.get(), entry);
684
685    COMPtr<CFDictionaryPropertyBag> userInfo = createUserInfoFromHistoryItem(
686        getNotificationString(kWebHistoryItemsAddedNotification), entry);
687    hr = postNotification(kWebHistoryItemsAddedNotification, userInfo.get());
688
689    if (added)
690        *added = true;
691
692    return hr;
693}
694
695void WebHistory::visitedURL(const KURL& url, const String& title, const String& httpMethod, bool wasFailure, bool increaseVisitCount)
696{
697    RetainPtr<CFStringRef> urlString(AdoptCF, url.string().createCFString());
698
699    IWebHistoryItem* entry = (IWebHistoryItem*) CFDictionaryGetValue(m_entriesByURL.get(), urlString.get());
700    if (entry) {
701        COMPtr<IWebHistoryItemPrivate> entryPrivate(Query, entry);
702        if (!entryPrivate)
703            return;
704
705        // Remove the item from date caches before changing its last visited date.  Otherwise we might get duplicate entries
706        // as seen in <rdar://problem/6570573>.
707        removeItemFromDateCaches(entry);
708        entryPrivate->visitedWithTitle(BString(title), increaseVisitCount);
709    } else {
710        COMPtr<WebHistoryItem> item(AdoptCOM, WebHistoryItem::createInstance());
711        if (!item)
712            return;
713
714        entry = item.get();
715
716        SYSTEMTIME currentTime;
717        GetSystemTime(&currentTime);
718        DATE lastVisited;
719        if (!SystemTimeToVariantTime(&currentTime, &lastVisited))
720            return;
721
722        if (FAILED(entry->initWithURLString(BString(url.string()), BString(title), lastVisited)))
723            return;
724
725        item->recordInitialVisit();
726
727        CFDictionarySetValue(m_entriesByURL.get(), urlString.get(), entry);
728    }
729
730    addItemToDateCaches(entry);
731
732    COMPtr<IWebHistoryItemPrivate> entryPrivate(Query, entry);
733    if (!entryPrivate)
734        return;
735
736    entryPrivate->setLastVisitWasFailure(wasFailure);
737    if (!httpMethod.isEmpty())
738        entryPrivate->setLastVisitWasHTTPNonGet(!equalIgnoringCase(httpMethod, "GET") && url.protocolInHTTPFamily());
739
740    COMPtr<WebHistoryItem> item(Query, entry);
741    item->historyItem()->setRedirectURLs(0);
742
743    COMPtr<CFDictionaryPropertyBag> userInfo = createUserInfoFromHistoryItem(
744        getNotificationString(kWebHistoryItemsAddedNotification), entry);
745    postNotification(kWebHistoryItemsAddedNotification, userInfo.get());
746}
747
748HRESULT WebHistory::itemForURLString(
749    /* [in] */ CFStringRef urlString,
750    /* [retval][out] */ IWebHistoryItem** item) const
751{
752    if (!item)
753        return E_FAIL;
754    *item = 0;
755
756    IWebHistoryItem* foundItem = (IWebHistoryItem*) CFDictionaryGetValue(m_entriesByURL.get(), urlString);
757    if (!foundItem)
758        return E_FAIL;
759
760    foundItem->AddRef();
761    *item = foundItem;
762    return S_OK;
763}
764
765HRESULT STDMETHODCALLTYPE WebHistory::itemForURL(
766    /* [in] */ BSTR url,
767    /* [retval][out] */ IWebHistoryItem** item)
768{
769    RetainPtr<CFStringRef> urlString(AdoptCF, MarshallingHelpers::BSTRToCFStringRef(url));
770    return itemForURLString(urlString.get(), item);
771}
772
773HRESULT WebHistory::removeItemForURLString(CFStringRef urlString)
774{
775    IWebHistoryItem* entry = (IWebHistoryItem*) CFDictionaryGetValue(m_entriesByURL.get(), urlString);
776    if (!entry)
777        return E_FAIL;
778
779    HRESULT hr = removeItemFromDateCaches(entry);
780    CFDictionaryRemoveValue(m_entriesByURL.get(), urlString);
781
782    if (!CFDictionaryGetCount(m_entriesByURL.get()))
783        PageGroup::removeAllVisitedLinks();
784
785    return hr;
786}
787
788COMPtr<IWebHistoryItem> WebHistory::itemForURLString(const String& urlString) const
789{
790    RetainPtr<CFStringRef> urlCFString(AdoptCF, urlString.createCFString());
791    if (!urlCFString)
792        return 0;
793    COMPtr<IWebHistoryItem> item;
794    if (FAILED(itemForURLString(urlCFString.get(), &item)))
795        return 0;
796    return item;
797}
798
799HRESULT WebHistory::addItemToDateCaches(IWebHistoryItem* entry)
800{
801    HRESULT hr = S_OK;
802
803    DATE lastVisitedCOMTime;
804    entry->lastVisitedTimeInterval(&lastVisitedCOMTime);
805
806    DateKey dateKey;
807    if (findKey(&dateKey, MarshallingHelpers::DATEToCFAbsoluteTime(lastVisitedCOMTime))) {
808        // other entries already exist for this date
809        hr = insertItem(entry, dateKey);
810    } else {
811        ASSERT(!m_entriesByDate.contains(dateKey));
812        // no other entries exist for this date
813        RetainPtr<CFMutableArrayRef> entryArray(AdoptCF,
814            CFArrayCreateMutable(0, 0, &MarshallingHelpers::kIUnknownArrayCallBacks));
815        CFArrayAppendValue(entryArray.get(), entry);
816        m_entriesByDate.set(dateKey, entryArray);
817        // Clear m_orderedLastVisitedDays so it will be regenerated when next requested.
818        m_orderedLastVisitedDays.clear();
819    }
820
821    return hr;
822}
823
824HRESULT WebHistory::removeItemFromDateCaches(IWebHistoryItem* entry)
825{
826    HRESULT hr = S_OK;
827
828    DATE lastVisitedCOMTime;
829    entry->lastVisitedTimeInterval(&lastVisitedCOMTime);
830
831    DateKey dateKey;
832    if (!findKey(&dateKey, MarshallingHelpers::DATEToCFAbsoluteTime(lastVisitedCOMTime)))
833        return E_FAIL;
834
835    DateToEntriesMap::iterator found = m_entriesByDate.find(dateKey);
836    ASSERT(found != m_entriesByDate.end());
837    CFMutableArrayRef entriesForDate = found->second.get();
838
839    CFIndex count = CFArrayGetCount(entriesForDate);
840    for (int i = count - 1; i >= 0; --i) {
841        if ((IWebHistoryItem*)CFArrayGetValueAtIndex(entriesForDate, i) == entry)
842            CFArrayRemoveValueAtIndex(entriesForDate, i);
843    }
844
845    // remove this date entirely if there are no other entries on it
846    if (CFArrayGetCount(entriesForDate) == 0) {
847        m_entriesByDate.remove(found);
848        // Clear m_orderedLastVisitedDays so it will be regenerated when next requested.
849        m_orderedLastVisitedDays.clear();
850    }
851
852    return hr;
853}
854
855static void getDayBoundaries(CFAbsoluteTime day, CFAbsoluteTime& beginningOfDay, CFAbsoluteTime& beginningOfNextDay)
856{
857    RetainPtr<CFTimeZoneRef> timeZone(AdoptCF, CFTimeZoneCopyDefault());
858    CFGregorianDate date = CFAbsoluteTimeGetGregorianDate(day, timeZone.get());
859    date.hour = 0;
860    date.minute = 0;
861    date.second = 0;
862    beginningOfDay = CFGregorianDateGetAbsoluteTime(date, timeZone.get());
863    date.day += 1;
864    beginningOfNextDay = CFGregorianDateGetAbsoluteTime(date, timeZone.get());
865}
866
867static inline CFAbsoluteTime beginningOfDay(CFAbsoluteTime date)
868{
869    static CFAbsoluteTime cachedBeginningOfDay = numeric_limits<CFAbsoluteTime>::quiet_NaN();
870    static CFAbsoluteTime cachedBeginningOfNextDay;
871    if (!(date >= cachedBeginningOfDay && date < cachedBeginningOfNextDay))
872        getDayBoundaries(date, cachedBeginningOfDay, cachedBeginningOfNextDay);
873    return cachedBeginningOfDay;
874}
875
876static inline WebHistory::DateKey dateKey(CFAbsoluteTime date)
877{
878    // Converting from double (CFAbsoluteTime) to int64_t (WebHistoryDateKey) is
879    // safe here because all sensible dates are in the range -2**48 .. 2**47 which
880    // safely fits in an int64_t.
881    return beginningOfDay(date);
882}
883
884// Returns whether the day is already in the list of days,
885// and fills in *key with the found or proposed key.
886bool WebHistory::findKey(DateKey* key, CFAbsoluteTime forDay)
887{
888    ASSERT_ARG(key, key);
889
890    *key = dateKey(forDay);
891    return m_entriesByDate.contains(*key);
892}
893
894HRESULT WebHistory::insertItem(IWebHistoryItem* entry, DateKey dateKey)
895{
896    ASSERT_ARG(entry, entry);
897    ASSERT_ARG(dateKey, m_entriesByDate.contains(dateKey));
898
899    HRESULT hr = S_OK;
900
901    if (!entry)
902        return E_FAIL;
903
904    DATE entryTime;
905    entry->lastVisitedTimeInterval(&entryTime);
906    CFMutableArrayRef entriesForDate = m_entriesByDate.get(dateKey).get();
907    unsigned count = CFArrayGetCount(entriesForDate);
908
909    // The entries for each day are stored in a sorted array with the most recent entry first
910    // Check for the common cases of the entry being newer than all existing entries or the first entry of the day
911    bool isNewerThanAllEntries = false;
912    if (count) {
913        IWebHistoryItem* item = const_cast<IWebHistoryItem*>(static_cast<const IWebHistoryItem*>(CFArrayGetValueAtIndex(entriesForDate, 0)));
914        DATE itemTime;
915        isNewerThanAllEntries = SUCCEEDED(item->lastVisitedTimeInterval(&itemTime)) && itemTime < entryTime;
916    }
917    if (!count || isNewerThanAllEntries) {
918        CFArrayInsertValueAtIndex(entriesForDate, 0, entry);
919        return S_OK;
920    }
921
922    // .. or older than all existing entries
923    bool isOlderThanAllEntries = false;
924    if (count > 0) {
925        IWebHistoryItem* item = const_cast<IWebHistoryItem*>(static_cast<const IWebHistoryItem*>(CFArrayGetValueAtIndex(entriesForDate, count - 1)));
926        DATE itemTime;
927        isOlderThanAllEntries = SUCCEEDED(item->lastVisitedTimeInterval(&itemTime)) && itemTime >= entryTime;
928    }
929    if (isOlderThanAllEntries) {
930        CFArrayInsertValueAtIndex(entriesForDate, count, entry);
931        return S_OK;
932    }
933
934    unsigned low = 0;
935    unsigned high = count;
936    while (low < high) {
937        unsigned mid = low + (high - low) / 2;
938        IWebHistoryItem* item = const_cast<IWebHistoryItem*>(static_cast<const IWebHistoryItem*>(CFArrayGetValueAtIndex(entriesForDate, mid)));
939        DATE itemTime;
940        if (FAILED(item->lastVisitedTimeInterval(&itemTime)))
941            return E_FAIL;
942
943        if (itemTime >= entryTime)
944            low = mid + 1;
945        else
946            high = mid;
947    }
948
949    // low is now the index of the first entry that is older than entryDate
950    CFArrayInsertValueAtIndex(entriesForDate, low, entry);
951    return S_OK;
952}
953
954CFAbsoluteTime WebHistory::timeToDate(CFAbsoluteTime time)
955{
956    // can't just divide/round since the day boundaries depend on our current time zone
957    const double secondsPerDay = 60 * 60 * 24;
958    CFTimeZoneRef timeZone = CFTimeZoneCopySystem();
959    CFGregorianDate date = CFAbsoluteTimeGetGregorianDate(time, timeZone);
960    date.hour = date.minute = 0;
961    date.second = 0.0;
962    CFAbsoluteTime timeInDays = CFGregorianDateGetAbsoluteTime(date, timeZone);
963    if (areEqualOrClose(time - timeInDays, secondsPerDay))
964        timeInDays += secondsPerDay;
965    return timeInDays;
966}
967
968// Return a date that marks the age limit for history entries saved to or
969// loaded from disk. Any entry older than this item should be rejected.
970HRESULT WebHistory::ageLimitDate(CFAbsoluteTime* time)
971{
972    // get the current date as a CFAbsoluteTime
973    CFAbsoluteTime currentDate = timeToDate(CFAbsoluteTimeGetCurrent());
974
975    CFGregorianUnits ageLimit = {0};
976    int historyLimitDays;
977    HRESULT hr = historyAgeInDaysLimit(&historyLimitDays);
978    if (FAILED(hr))
979        return hr;
980    ageLimit.days = -historyLimitDays;
981    *time = CFAbsoluteTimeAddGregorianUnits(currentDate, CFTimeZoneCopySystem(), ageLimit);
982    return S_OK;
983}
984
985static void addVisitedLinkToPageGroup(const void* key, const void*, void* context)
986{
987    CFStringRef url = static_cast<CFStringRef>(key);
988    PageGroup* group = static_cast<PageGroup*>(context);
989
990    CFIndex length = CFStringGetLength(url);
991    const UChar* characters = reinterpret_cast<const UChar*>(CFStringGetCharactersPtr(url));
992    if (characters)
993        group->addVisitedLink(characters, length);
994    else {
995        Vector<UChar, 512> buffer(length);
996        CFStringGetCharacters(url, CFRangeMake(0, length), reinterpret_cast<UniChar*>(buffer.data()));
997        group->addVisitedLink(buffer.data(), length);
998    }
999}
1000
1001void WebHistory::addVisitedLinksToPageGroup(PageGroup& group)
1002{
1003    CFDictionaryApplyFunction(m_entriesByURL.get(), addVisitedLinkToPageGroup, &group);
1004}
1005
1006RetainPtr<CFDataRef> WebHistory::data() const
1007{
1008    if (m_entriesByDate.isEmpty())
1009        return 0;
1010
1011    WebHistoryWriter writer(m_entriesByDate);
1012    writer.writePropertyList();
1013    return writer.releaseData();
1014}
1015