eab08b656bd3fdfcf533fe9bbdb523b1d37ad4f6
[WebKit-https.git] / Source / WebKit / mac / History / WebHistory.mm
1 /*
2  * Copyright (C) 2005, 2008, 2009 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  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer. 
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution. 
13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission. 
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #import "WebHistoryInternal.h"
30
31 #import "HistoryPropertyList.h"
32 #import "WebHistoryItemInternal.h"
33 #import "WebKitLogging.h"
34 #import "WebNSURLExtras.h"
35 #import "WebTypesInternal.h"
36 #import <WebCore/HistoryItem.h>
37 #import <WebCore/PageGroup.h>
38
39 using namespace WebCore;
40
41 typedef int64_t WebHistoryDateKey;
42 typedef HashMap<WebHistoryDateKey, RetainPtr<NSMutableArray>> DateToEntriesMap;
43
44 NSString *WebHistoryItemsAddedNotification = @"WebHistoryItemsAddedNotification";
45 NSString *WebHistoryItemsRemovedNotification = @"WebHistoryItemsRemovedNotification";
46 NSString *WebHistoryAllItemsRemovedNotification = @"WebHistoryAllItemsRemovedNotification";
47 NSString *WebHistoryLoadedNotification = @"WebHistoryLoadedNotification";
48 NSString *WebHistoryItemsDiscardedWhileLoadingNotification = @"WebHistoryItemsDiscardedWhileLoadingNotification";
49 NSString *WebHistorySavedNotification = @"WebHistorySavedNotification";
50 NSString *WebHistoryItemsKey = @"WebHistoryItems";
51
52 static WebHistory *_sharedHistory = nil;
53
54 NSString *FileVersionKey = @"WebHistoryFileVersion";
55 NSString *DatesArrayKey = @"WebHistoryDates";
56
57 #define currentFileVersion 1
58
59 class WebHistoryWriter : public HistoryPropertyListWriter {
60 public:
61     WebHistoryWriter(DateToEntriesMap*);
62
63 private:
64     virtual void writeHistoryItems(BinaryPropertyListObjectStream&);
65
66     DateToEntriesMap* m_entriesByDate;
67     Vector<int> m_dateKeys;
68 };
69
70 @interface WebHistory ()
71 - (void)_sendNotification:(NSString *)name entries:(NSArray *)entries;
72 @end
73
74 @interface WebHistoryPrivate : NSObject {
75 @private
76     NSMutableDictionary *_entriesByURL;
77     std::unique_ptr<DateToEntriesMap> _entriesByDate;
78     NSMutableArray *_orderedLastVisitedDays;
79     BOOL itemLimitSet;
80     int itemLimit;
81     BOOL ageInDaysLimitSet;
82     int ageInDaysLimit;
83 }
84
85 - (WebHistoryItem *)visitedURL:(NSURL *)url withTitle:(NSString *)title increaseVisitCount:(BOOL)increaseVisitCount;
86
87 - (BOOL)addItem:(WebHistoryItem *)entry discardDuplicate:(BOOL)discardDuplicate;
88 - (void)addItems:(NSArray *)newEntries;
89 - (BOOL)removeItem:(WebHistoryItem *)entry;
90 - (BOOL)removeItems:(NSArray *)entries;
91 - (BOOL)removeAllItems;
92 - (void)rebuildHistoryByDayIfNeeded:(WebHistory *)webHistory;
93
94 - (NSArray *)orderedLastVisitedDays;
95 - (BOOL)containsURL:(NSURL *)URL;
96 - (WebHistoryItem *)itemForURL:(NSURL *)URL;
97 - (WebHistoryItem *)itemForURLString:(NSString *)URLString;
98 - (NSArray *)allItems;
99
100 - (BOOL)loadFromURL:(NSURL *)URL collectDiscardedItemsInto:(NSMutableArray *)discardedItems error:(NSError **)error;
101 - (BOOL)saveToURL:(NSURL *)URL error:(NSError **)error;
102
103 - (void)setHistoryItemLimit:(int)limit;
104 - (int)historyItemLimit;
105 - (void)setHistoryAgeInDaysLimit:(int)limit;
106 - (int)historyAgeInDaysLimit;
107
108 - (void)addVisitedLinksToPageGroup:(PageGroup&)group;
109
110 @end
111
112 @implementation WebHistoryPrivate
113
114 // MARK: OBJECT FRAMEWORK
115
116 + (void)initialize
117 {
118     [[NSUserDefaults standardUserDefaults] registerDefaults:
119         [NSDictionary dictionaryWithObjectsAndKeys:
120             @"1000", @"WebKitHistoryItemLimit",
121             @"7", @"WebKitHistoryAgeInDaysLimit",
122             nil]];    
123 }
124
125 - (id)init
126 {
127     self = [super init];
128     if (!self)
129         return nil;
130     
131     _entriesByURL = [[NSMutableDictionary alloc] init];
132     _entriesByDate = std::make_unique<DateToEntriesMap>();
133
134     return self;
135 }
136
137 - (void)dealloc
138 {
139     [_entriesByURL release];
140     [_orderedLastVisitedDays release];
141     [super dealloc];
142 }
143
144 - (void)finalize
145 {
146     [super finalize];
147 }
148
149 // MARK: MODIFYING CONTENTS
150
151 static void getDayBoundaries(NSTimeInterval interval, NSTimeInterval& beginningOfDay, NSTimeInterval& beginningOfNextDay)
152 {
153 #if __MAC_OS_X_VERSION_MIN_REQUIRED >= 1090
154     NSDate *date = [NSDate dateWithTimeIntervalSinceReferenceDate:interval];
155     
156     NSCalendar *calendar = [NSCalendar calendarWithIdentifier:NSCalendarIdentifierGregorian];
157     
158     NSDate *beginningOfDayDate = nil;
159     NSTimeInterval dayLength;
160     [calendar rangeOfUnit:NSCalendarUnitDay startDate:&beginningOfDayDate interval:&dayLength forDate:date];
161     
162     beginningOfDay = beginningOfDayDate.timeIntervalSinceReferenceDate;
163     beginningOfNextDay = beginningOfDay + dayLength;
164 #else
165     CFTimeZoneRef timeZone = CFTimeZoneCopyDefault();
166     CFGregorianDate date = CFAbsoluteTimeGetGregorianDate(interval, timeZone);
167     date.hour = 0;
168     date.minute = 0;
169     date.second = 0;
170     beginningOfDay = CFGregorianDateGetAbsoluteTime(date, timeZone);
171     date.day += 1;
172     beginningOfNextDay = CFGregorianDateGetAbsoluteTime(date, timeZone);
173     CFRelease(timeZone);
174 #endif
175 }
176
177 static inline NSTimeInterval beginningOfDay(NSTimeInterval date)
178 {
179     static NSTimeInterval cachedBeginningOfDay = NAN;
180     static NSTimeInterval cachedBeginningOfNextDay;
181     if (!(date >= cachedBeginningOfDay && date < cachedBeginningOfNextDay))
182         getDayBoundaries(date, cachedBeginningOfDay, cachedBeginningOfNextDay);
183     return cachedBeginningOfDay;
184 }
185
186 static inline WebHistoryDateKey dateKey(NSTimeInterval date)
187 {
188     // Converting from double (NSTimeInterval) to int64_t (WebHistoryDateKey) is
189     // safe here because all sensible dates are in the range -2**48 .. 2**47 which
190     // safely fits in an int64_t.
191     return beginningOfDay(date);
192 }
193
194 // Returns whether the day is already in the list of days,
195 // and fills in *key with the key used to access its location
196 - (BOOL)findKey:(WebHistoryDateKey*)key forDay:(NSTimeInterval)date
197 {
198     ASSERT_ARG(key, key);
199     *key = dateKey(date);
200     return _entriesByDate->contains(*key);
201 }
202
203 - (void)insertItem:(WebHistoryItem *)entry forDateKey:(WebHistoryDateKey)dateKey
204 {
205     ASSERT_ARG(entry, entry != nil);
206     ASSERT(_entriesByDate->contains(dateKey));
207
208     NSMutableArray *entriesForDate = _entriesByDate->get(dateKey).get();
209     NSTimeInterval entryDate = [entry lastVisitedTimeInterval];
210
211     unsigned count = [entriesForDate count];
212
213     // The entries for each day are stored in a sorted array with the most recent entry first
214     // Check for the common cases of the entry being newer than all existing entries or the first entry of the day
215     if (!count || [[entriesForDate objectAtIndex:0] lastVisitedTimeInterval] < entryDate) {
216         [entriesForDate insertObject:entry atIndex:0];
217         return;
218     }
219     // .. or older than all existing entries
220     if (count > 0 && [[entriesForDate objectAtIndex:count - 1] lastVisitedTimeInterval] >= entryDate) {
221         [entriesForDate insertObject:entry atIndex:count];
222         return;
223     }
224
225     unsigned low = 0;
226     unsigned high = count;
227     while (low < high) {
228         unsigned mid = low + (high - low) / 2;
229         if ([[entriesForDate objectAtIndex:mid] lastVisitedTimeInterval] >= entryDate)
230             low = mid + 1;
231         else
232             high = mid;
233     }
234
235     // low is now the index of the first entry that is older than entryDate
236     [entriesForDate insertObject:entry atIndex:low];
237 }
238
239 - (BOOL)removeItemFromDateCaches:(WebHistoryItem *)entry
240 {
241     WebHistoryDateKey dateKey;
242     BOOL foundDate = [self findKey:&dateKey forDay:[entry lastVisitedTimeInterval]];
243  
244     if (!foundDate)
245         return NO;
246
247     DateToEntriesMap::iterator it = _entriesByDate->find(dateKey);
248     NSMutableArray *entriesForDate = it->value.get();
249     [entriesForDate removeObjectIdenticalTo:entry];
250     
251     // remove this date entirely if there are no other entries on it
252     if ([entriesForDate count] == 0) {
253         _entriesByDate->remove(it);
254         // Clear _orderedLastVisitedDays so it will be regenerated when next requested.
255         [_orderedLastVisitedDays release];
256         _orderedLastVisitedDays = nil;
257     }
258     
259     return YES;
260 }
261
262 - (BOOL)removeItemForURLString:(NSString *)URLString
263 {
264     WebHistoryItem *entry = [_entriesByURL objectForKey:URLString];
265     if (!entry)
266         return NO;
267
268     [_entriesByURL removeObjectForKey:URLString];
269     
270 #if ASSERT_DISABLED
271     [self removeItemFromDateCaches:entry];
272 #else
273     BOOL itemWasInDateCaches = [self removeItemFromDateCaches:entry];
274     ASSERT(itemWasInDateCaches);
275 #endif
276
277     if (![_entriesByURL count])
278         PageGroup::removeAllVisitedLinks();
279
280     return YES;
281 }
282
283 - (void)addItemToDateCaches:(WebHistoryItem *)entry
284 {
285     WebHistoryDateKey dateKey;
286     if ([self findKey:&dateKey forDay:[entry lastVisitedTimeInterval]])
287         // other entries already exist for this date
288         [self insertItem:entry forDateKey:dateKey];
289     else {
290         // no other entries exist for this date
291         NSMutableArray *entries = [[NSMutableArray alloc] initWithObjects:&entry count:1];
292         _entriesByDate->set(dateKey, entries);
293         [entries release];
294         // Clear _orderedLastVisitedDays so it will be regenerated when next requested.
295         [_orderedLastVisitedDays release];
296         _orderedLastVisitedDays = nil;
297     }
298 }
299
300 - (WebHistoryItem *)visitedURL:(NSURL *)url withTitle:(NSString *)title increaseVisitCount:(BOOL)increaseVisitCount
301 {
302     ASSERT(url);
303     ASSERT(title);
304     
305     NSString *URLString = [url _web_originalDataAsString];
306     if (!URLString)
307         URLString = @"";
308     WebHistoryItem *entry = [_entriesByURL objectForKey:URLString];
309
310     if (entry) {
311         LOG(History, "Updating global history entry %@", entry);
312         // Remove the item from date caches before changing its last visited date.  Otherwise we might get duplicate entries
313         // as seen in <rdar://problem/6570573>.
314         BOOL itemWasInDateCaches = [self removeItemFromDateCaches:entry];
315         ASSERT_UNUSED(itemWasInDateCaches, itemWasInDateCaches);
316
317         [entry _visitedWithTitle:title increaseVisitCount:increaseVisitCount];
318     } else {
319         LOG(History, "Adding new global history entry for %@", url);
320         entry = [[WebHistoryItem alloc] initWithURLString:URLString title:title lastVisitedTimeInterval:[NSDate timeIntervalSinceReferenceDate]];
321         [entry _recordInitialVisit];
322         [_entriesByURL setObject:entry forKey:URLString];
323         [entry release];
324     }
325     
326     [self addItemToDateCaches:entry];
327
328     return entry;
329 }
330
331 - (BOOL)addItem:(WebHistoryItem *)entry discardDuplicate:(BOOL)discardDuplicate
332 {
333     ASSERT_ARG(entry, entry);
334     ASSERT_ARG(entry, [entry lastVisitedTimeInterval] != 0);
335
336     NSString *URLString = [entry URLString];
337
338     WebHistoryItem *oldEntry = [_entriesByURL objectForKey:URLString];
339     if (oldEntry) {
340         if (discardDuplicate)
341             return NO;
342
343         // The last reference to oldEntry might be this dictionary, so we hold onto a reference
344         // until we're done with oldEntry.
345         [oldEntry retain];
346         [self removeItemForURLString:URLString];
347
348         // If we already have an item with this URL, we need to merge info that drives the
349         // URL autocomplete heuristics from that item into the new one.
350         [entry _mergeAutoCompleteHints:oldEntry];
351         [oldEntry release];
352     }
353
354     [self addItemToDateCaches:entry];
355     [_entriesByURL setObject:entry forKey:URLString];
356     
357     return YES;
358 }
359
360 - (void)rebuildHistoryByDayIfNeeded:(WebHistory *)webHistory
361 {
362     // We clear all the values to present a consistent state when sending the notifications.
363     // We keep a reference to the entries for rebuilding the history after the notification.
364     Vector <RetainPtr<NSMutableArray>> entryArrays;
365     copyValuesToVector(*_entriesByDate, entryArrays);
366     _entriesByDate->clear();
367     
368     NSMutableDictionary *entriesByURL = _entriesByURL;
369     _entriesByURL = nil;
370     
371     [_orderedLastVisitedDays release];
372     _orderedLastVisitedDays = nil;
373     
374     NSArray *allEntries = [entriesByURL allValues];
375     [webHistory _sendNotification:WebHistoryAllItemsRemovedNotification entries:allEntries];
376     
377     // Next, we rebuild the history, restore the states, and notify the clients.
378     _entriesByURL = entriesByURL;
379     for (size_t dayIndex = 0; dayIndex < entryArrays.size(); ++dayIndex) {
380         for (WebHistoryItem *entry in (entryArrays[dayIndex]).get())
381             [self addItemToDateCaches:entry];
382     }
383     [webHistory _sendNotification:WebHistoryItemsAddedNotification entries:allEntries];
384 }
385
386 - (BOOL)removeItem:(WebHistoryItem *)entry
387 {
388     NSString *URLString = [entry URLString];
389
390     // If this exact object isn't stored, then make no change.
391     // FIXME: Is this the right behavior if this entry isn't present, but another entry for the same URL is?
392     // Maybe need to change the API to make something like removeEntryForURLString public instead.
393     WebHistoryItem *matchingEntry = [_entriesByURL objectForKey:URLString];
394     if (matchingEntry != entry)
395         return NO;
396
397     [self removeItemForURLString:URLString];
398
399     return YES;
400 }
401
402 - (BOOL)removeItems:(NSArray *)entries
403 {
404     NSUInteger count = [entries count];
405     if (!count)
406         return NO;
407
408     for (NSUInteger index = 0; index < count; ++index)
409         [self removeItem:[entries objectAtIndex:index]];
410     
411     return YES;
412 }
413
414 - (BOOL)removeAllItems
415 {
416     if (_entriesByDate->isEmpty())
417         return NO;
418
419     _entriesByDate->clear();
420     [_entriesByURL removeAllObjects];
421
422     // Clear _orderedLastVisitedDays so it will be regenerated when next requested.
423     [_orderedLastVisitedDays release];
424     _orderedLastVisitedDays = nil;
425
426     PageGroup::removeAllVisitedLinks();
427
428     return YES;
429 }
430
431 - (void)addItems:(NSArray *)newEntries
432 {
433     // There is no guarantee that the incoming entries are in any particular
434     // order, but if this is called with a set of entries that were created by
435     // iterating through the results of orderedLastVisitedDays and orderedItemsLastVisitedOnDayy
436     // then they will be ordered chronologically from newest to oldest. We can make adding them
437     // faster (fewer compares) by inserting them from oldest to newest.
438     NSEnumerator *enumerator = [newEntries reverseObjectEnumerator];
439     while (WebHistoryItem *entry = [enumerator nextObject])
440         [self addItem:entry discardDuplicate:NO];
441 }
442
443 // MARK: DATE-BASED RETRIEVAL
444
445 #pragma clang diagnostic push
446 #pragma clang diagnostic ignored "-Wdeprecated-declarations"
447
448 - (NSArray *)orderedLastVisitedDays
449 {
450     if (!_orderedLastVisitedDays) {
451         Vector<int> daysAsTimeIntervals;
452         daysAsTimeIntervals.reserveCapacity(_entriesByDate->size());
453         DateToEntriesMap::const_iterator end = _entriesByDate->end();
454         for (DateToEntriesMap::const_iterator it = _entriesByDate->begin(); it != end; ++it)
455             daysAsTimeIntervals.append(it->key);
456
457         std::sort(daysAsTimeIntervals.begin(), daysAsTimeIntervals.end());
458         size_t count = daysAsTimeIntervals.size();
459         _orderedLastVisitedDays = [[NSMutableArray alloc] initWithCapacity:count];
460         for (int i = count - 1; i >= 0; i--) {
461             NSTimeInterval interval = daysAsTimeIntervals[i];
462             NSCalendarDate *date = [[NSCalendarDate alloc] initWithTimeIntervalSinceReferenceDate:interval];
463             [_orderedLastVisitedDays addObject:date];
464             [date release];
465         }
466     }
467     return _orderedLastVisitedDays;
468 }
469
470 - (NSArray *)orderedItemsLastVisitedOnDay:(NSCalendarDate *)date
471 {
472     WebHistoryDateKey dateKey;
473     if (![self findKey:&dateKey forDay:[date timeIntervalSinceReferenceDate]])
474         return nil;
475     return _entriesByDate->get(dateKey).get();
476 }
477
478 #pragma clang diagnostic pop
479
480 // MARK: URL MATCHING
481
482 - (WebHistoryItem *)itemForURLString:(NSString *)URLString
483 {
484     return [_entriesByURL objectForKey:URLString];
485 }
486
487 - (BOOL)containsURL:(NSURL *)URL
488 {
489     return [self itemForURLString:[URL _web_originalDataAsString]] != nil;
490 }
491
492 - (WebHistoryItem *)itemForURL:(NSURL *)URL
493 {
494     return [self itemForURLString:[URL _web_originalDataAsString]];
495 }
496
497 - (NSArray *)allItems
498 {
499     return [_entriesByURL allValues];
500 }
501
502 // MARK: ARCHIVING/UNARCHIVING
503
504 - (void)setHistoryAgeInDaysLimit:(int)limit
505 {
506     ageInDaysLimitSet = YES;
507     ageInDaysLimit = limit;
508 }
509
510 - (int)historyAgeInDaysLimit
511 {
512     if (ageInDaysLimitSet)
513         return ageInDaysLimit;
514     return [[NSUserDefaults standardUserDefaults] integerForKey:@"WebKitHistoryAgeInDaysLimit"];
515 }
516
517 - (void)setHistoryItemLimit:(int)limit
518 {
519     itemLimitSet = YES;
520     itemLimit = limit;
521 }
522
523 - (int)historyItemLimit
524 {
525     if (itemLimitSet)
526         return itemLimit;
527     return [[NSUserDefaults standardUserDefaults] integerForKey:@"WebKitHistoryItemLimit"];
528 }
529
530 #pragma clang diagnostic push
531 #pragma clang diagnostic ignored "-Wdeprecated-declarations"
532
533 // Return a date that marks the age limit for history entries saved to or
534 // loaded from disk. Any entry older than this item should be rejected.
535 - (NSCalendarDate *)ageLimitDate
536 {
537     return [[NSCalendarDate calendarDate] dateByAddingYears:0 months:0 days:-[self historyAgeInDaysLimit]
538                                                       hours:0 minutes:0 seconds:0];
539 }
540
541 #pragma clang diagnostic pop
542
543 - (BOOL)loadHistoryGutsFromURL:(NSURL *)URL savedItemsCount:(int *)numberOfItemsLoaded collectDiscardedItemsInto:(NSMutableArray *)discardedItems error:(NSError **)error
544 {
545     *numberOfItemsLoaded = 0;
546     NSDictionary *dictionary = nil;
547
548     // Optimize loading from local file, which is faster than using the general URL loading mechanism
549     if ([URL isFileURL]) {
550         dictionary = [NSDictionary dictionaryWithContentsOfFile:[URL path]];
551         if (!dictionary) {
552 #if !LOG_DISABLED
553             if ([[NSFileManager defaultManager] fileExistsAtPath:[URL path]])
554                 LOG_ERROR("unable to read history from file %@; perhaps contents are corrupted", [URL path]);
555 #endif
556             // else file doesn't exist, which is normal the first time
557             return NO;
558         }
559     } else {
560         NSData *data = [NSURLConnection sendSynchronousRequest:[NSURLRequest requestWithURL:URL] returningResponse:nil error:error];
561         if (data.length)
562             dictionary = [NSPropertyListSerialization propertyListWithData:data options:NSPropertyListImmutable format:nullptr error:nullptr];
563     }
564
565     // We used to support NSArrays here, but that was before Safari 1.0 shipped. We will no longer support
566     // that ancient format, so anything that isn't an NSDictionary is bogus.
567     if (![dictionary isKindOfClass:[NSDictionary class]])
568         return NO;
569
570     NSNumber *fileVersionObject = [dictionary objectForKey:FileVersionKey];
571     int fileVersion;
572     // we don't trust data obtained from elsewhere, so double-check
573     if (!fileVersionObject || ![fileVersionObject isKindOfClass:[NSNumber class]]) {
574         LOG_ERROR("history file version can't be determined, therefore not loading");
575         return NO;
576     }
577     fileVersion = [fileVersionObject intValue];
578     if (fileVersion > currentFileVersion) {
579         LOG_ERROR("history file version is %d, newer than newest known version %d, therefore not loading", fileVersion, currentFileVersion);
580         return NO;
581     }    
582
583     NSArray *array = [dictionary objectForKey:DatesArrayKey];
584
585     int itemCountLimit = [self historyItemLimit];
586     NSTimeInterval ageLimitDate = [[self ageLimitDate] timeIntervalSinceReferenceDate];
587     NSEnumerator *enumerator = [array objectEnumerator];
588     BOOL ageLimitPassed = NO;
589     BOOL itemLimitPassed = NO;
590     ASSERT(*numberOfItemsLoaded == 0);
591
592     NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
593     NSDictionary *itemAsDictionary;
594     while ((itemAsDictionary = [enumerator nextObject]) != nil) {
595         WebHistoryItem *item = [[WebHistoryItem alloc] initFromDictionaryRepresentation:itemAsDictionary];
596
597         // item without URL is useless; data on disk must have been bad; ignore
598         if ([item URLString]) {
599             // Test against date limit. Since the items are ordered newest to oldest, we can stop comparing
600             // once we've found the first item that's too old.
601             if (!ageLimitPassed && [item lastVisitedTimeInterval] <= ageLimitDate)
602                 ageLimitPassed = YES;
603
604             if (ageLimitPassed || itemLimitPassed)
605                 [discardedItems addObject:item];
606             else {
607                 if ([self addItem:item discardDuplicate:YES])
608                     ++(*numberOfItemsLoaded);
609                 if (*numberOfItemsLoaded == itemCountLimit)
610                     itemLimitPassed = YES;
611
612                 // Draining the autorelease pool every 50 iterations was found by experimentation to be optimal
613                 if (*numberOfItemsLoaded % 50 == 0) {
614                     [pool drain];
615                     pool = [[NSAutoreleasePool alloc] init];
616                 }
617             }
618         }
619         [item release];
620     }
621     [pool drain];
622
623     return YES;
624 }
625
626 - (BOOL)loadFromURL:(NSURL *)URL collectDiscardedItemsInto:(NSMutableArray *)discardedItems error:(NSError **)error
627 {
628 #if !LOG_DISABLED
629     double start = CFAbsoluteTimeGetCurrent();
630 #endif
631
632     int numberOfItems;
633     if (![self loadHistoryGutsFromURL:URL savedItemsCount:&numberOfItems collectDiscardedItemsInto:discardedItems error:error])
634         return NO;
635
636 #if !LOG_DISABLED
637     double duration = CFAbsoluteTimeGetCurrent() - start;
638     LOG(Timing, "loading %d history entries from %@ took %f seconds", numberOfItems, URL, duration);
639 #endif
640
641     return YES;
642 }
643
644 - (NSData *)data
645 {
646     if (_entriesByDate->isEmpty()) {
647         static NSData *emptyHistoryData = (NSData *)CFDataCreate(0, 0, 0);
648         return emptyHistoryData;
649     }
650     
651     // Ignores the date and item count limits; these are respected when loading instead of when saving, so
652     // that clients can learn of discarded items by listening to WebHistoryItemsDiscardedWhileLoadingNotification.
653     WebHistoryWriter writer(_entriesByDate.get());
654     writer.writePropertyList();
655     return [[(NSData *)writer.releaseData().get() retain] autorelease];
656 }
657
658 - (BOOL)saveToURL:(NSURL *)URL error:(NSError **)error
659 {
660 #if !LOG_DISABLED
661     double start = CFAbsoluteTimeGetCurrent();
662 #endif
663
664     BOOL result = [[self data] writeToURL:URL options:0 error:error];
665
666 #if !LOG_DISABLED
667     double duration = CFAbsoluteTimeGetCurrent() - start;
668     LOG(Timing, "saving history to %@ took %f seconds", URL, duration);
669 #endif
670
671     return result;
672 }
673
674 - (void)addVisitedLinksToPageGroup:(PageGroup&)group
675 {
676     NSEnumerator *enumerator = [_entriesByURL keyEnumerator];
677     while (NSString *url = [enumerator nextObject]) {
678         size_t length = [url length];
679         const UChar* characters = CFStringGetCharactersPtr(reinterpret_cast<CFStringRef>(url));
680         if (characters)
681             group.addVisitedLink(characters, length);
682         else {
683             Vector<UChar, 512> buffer(length);
684             [url getCharacters:buffer.data()];
685             group.addVisitedLink(buffer.data(), length);
686         }
687     }
688 }
689
690 @end
691
692 @implementation WebHistory
693
694 + (WebHistory *)optionalSharedHistory
695 {
696     return _sharedHistory;
697 }
698
699 + (void)setOptionalSharedHistory:(WebHistory *)history
700 {
701     if (_sharedHistory == history)
702         return;
703     // FIXME: Need to think about multiple instances of WebHistory per application
704     // and correct synchronization of history file between applications.
705     [_sharedHistory release];
706     _sharedHistory = [history retain];
707     PageGroup::setShouldTrackVisitedLinks(history);
708     PageGroup::removeAllVisitedLinks();
709 }
710
711 - (void)timeZoneChanged:(NSNotification *)notification
712 {
713     [_historyPrivate rebuildHistoryByDayIfNeeded:self];
714 }
715
716 - (id)init
717 {
718     self = [super init];
719     if (!self)
720         return nil;
721     _historyPrivate = [[WebHistoryPrivate alloc] init];
722     [[NSNotificationCenter defaultCenter] addObserver:self
723                                              selector:@selector(timeZoneChanged:)
724                                                  name:NSSystemTimeZoneDidChangeNotification
725                                                object:nil];
726     return self;
727 }
728
729 - (void)dealloc
730 {
731     [[NSNotificationCenter defaultCenter] removeObserver:self
732                                                     name:NSSystemTimeZoneDidChangeNotification
733                                                   object:nil];
734     [_historyPrivate release];
735     [super dealloc];
736 }
737
738 - (void)finalize
739 {
740     [[NSNotificationCenter defaultCenter] removeObserver:self
741                                                     name:NSSystemTimeZoneDidChangeNotification
742                                                   object:nil];
743     [super finalize];
744 }
745
746 // MARK: MODIFYING CONTENTS
747
748 - (void)_sendNotification:(NSString *)name entries:(NSArray *)entries
749 {
750     NSDictionary *userInfo = [NSDictionary dictionaryWithObjectsAndKeys:entries, WebHistoryItemsKey, nil];
751     [[NSNotificationCenter defaultCenter]
752         postNotificationName:name object:self userInfo:userInfo];
753 }
754
755 - (void)removeItems:(NSArray *)entries
756 {
757     if ([_historyPrivate removeItems:entries]) {
758         [self _sendNotification:WebHistoryItemsRemovedNotification
759                         entries:entries];
760     }
761 }
762
763 - (void)removeAllItems
764 {
765     NSArray *entries = [_historyPrivate allItems];
766     if ([_historyPrivate removeAllItems])
767         [self _sendNotification:WebHistoryAllItemsRemovedNotification entries:entries];
768 }
769
770 - (void)addItems:(NSArray *)newEntries
771 {
772     [_historyPrivate addItems:newEntries];
773     [self _sendNotification:WebHistoryItemsAddedNotification
774                     entries:newEntries];
775 }
776
777 // MARK: DATE-BASED RETRIEVAL
778
779 - (NSArray *)orderedLastVisitedDays
780 {
781     return [_historyPrivate orderedLastVisitedDays];
782 }
783
784 #pragma clang diagnostic push
785 #pragma clang diagnostic ignored "-Wdeprecated-declarations"
786
787 - (NSArray *)orderedItemsLastVisitedOnDay:(NSCalendarDate *)date
788 {
789     return [_historyPrivate orderedItemsLastVisitedOnDay:date];
790 }
791
792 #pragma clang diagnostic pop
793
794 // MARK: URL MATCHING
795
796 - (BOOL)containsURL:(NSURL *)URL
797 {
798     return [_historyPrivate containsURL:URL];
799 }
800
801 - (WebHistoryItem *)itemForURL:(NSURL *)URL
802 {
803     return [_historyPrivate itemForURL:URL];
804 }
805
806 // MARK: SAVING TO DISK
807
808 - (BOOL)loadFromURL:(NSURL *)URL error:(NSError **)error
809 {
810     NSMutableArray *discardedItems = [[NSMutableArray alloc] init];    
811     if (![_historyPrivate loadFromURL:URL collectDiscardedItemsInto:discardedItems error:error]) {
812         [discardedItems release];
813         return NO;
814     }
815
816     [[NSNotificationCenter defaultCenter]
817         postNotificationName:WebHistoryLoadedNotification
818                       object:self];
819
820     if ([discardedItems count])
821         [self _sendNotification:WebHistoryItemsDiscardedWhileLoadingNotification entries:discardedItems];
822
823     [discardedItems release];
824     return YES;
825 }
826
827 - (BOOL)saveToURL:(NSURL *)URL error:(NSError **)error
828 {
829     if (![_historyPrivate saveToURL:URL error:error])
830         return NO;
831     [[NSNotificationCenter defaultCenter]
832         postNotificationName:WebHistorySavedNotification
833                       object:self];
834     return YES;
835 }
836
837 - (void)setHistoryItemLimit:(int)limit
838 {
839     [_historyPrivate setHistoryItemLimit:limit];
840 }
841
842 - (int)historyItemLimit
843 {
844     return [_historyPrivate historyItemLimit];
845 }
846
847 - (void)setHistoryAgeInDaysLimit:(int)limit
848 {
849     [_historyPrivate setHistoryAgeInDaysLimit:limit];
850 }
851
852 - (int)historyAgeInDaysLimit
853 {
854     return [_historyPrivate historyAgeInDaysLimit];
855 }
856
857 @end
858
859 @implementation WebHistory (WebPrivate)
860
861 - (WebHistoryItem *)_itemForURLString:(NSString *)URLString
862 {
863     return [_historyPrivate itemForURLString:URLString];
864 }
865
866 - (NSArray *)allItems
867 {
868     return [_historyPrivate allItems];
869 }
870
871 - (NSData *)_data
872 {
873     return [_historyPrivate data];
874 }
875
876 + (void)_setVisitedLinkTrackingEnabled:(BOOL)visitedLinkTrackingEnabled
877 {
878     PageGroup::setShouldTrackVisitedLinks(visitedLinkTrackingEnabled);
879 }
880
881 + (void)_removeAllVisitedLinks
882 {
883     PageGroup::removeAllVisitedLinks();
884 }
885
886 @end
887
888 @implementation WebHistory (WebInternal)
889
890 - (void)_visitedURL:(NSURL *)url withTitle:(NSString *)title method:(NSString *)method wasFailure:(BOOL)wasFailure increaseVisitCount:(BOOL)increaseVisitCount
891 {
892     WebHistoryItem *entry = [_historyPrivate visitedURL:url withTitle:title increaseVisitCount:increaseVisitCount];
893
894     HistoryItem* item = core(entry);
895     item->setLastVisitWasFailure(wasFailure);
896
897     if ([method length])
898         item->setLastVisitWasHTTPNonGet([method caseInsensitiveCompare:@"GET"] && (![[url scheme] caseInsensitiveCompare:@"http"] || ![[url scheme] caseInsensitiveCompare:@"https"]));
899
900     item->setRedirectURLs(nullptr);
901
902     NSArray *entries = [[NSArray alloc] initWithObjects:entry, nil];
903     [self _sendNotification:WebHistoryItemsAddedNotification entries:entries];
904     [entries release];
905 }
906
907 - (void)_addVisitedLinksToPageGroup:(WebCore::PageGroup&)group
908 {
909     [_historyPrivate addVisitedLinksToPageGroup:group];
910 }
911
912 @end
913
914 WebHistoryWriter::WebHistoryWriter(DateToEntriesMap* entriesByDate)
915     : m_entriesByDate(entriesByDate)
916 {
917     m_dateKeys.reserveCapacity(m_entriesByDate->size());
918     DateToEntriesMap::const_iterator end = m_entriesByDate->end();
919     for (DateToEntriesMap::const_iterator it = m_entriesByDate->begin(); it != end; ++it)
920         m_dateKeys.append(it->key);
921     std::sort(m_dateKeys.begin(), m_dateKeys.end());
922 }
923
924 void WebHistoryWriter::writeHistoryItems(BinaryPropertyListObjectStream& stream)
925 {
926     for (int dateIndex = m_dateKeys.size() - 1; dateIndex >= 0; dateIndex--) {
927         NSArray *entries = m_entriesByDate->get(m_dateKeys[dateIndex]).get();
928         NSUInteger entryCount = [entries count];
929         for (NSUInteger entryIndex = 0; entryIndex < entryCount; ++entryIndex)
930             writeHistoryItem(stream, core([entries objectAtIndex:entryIndex]));
931     }
932 }