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