WebKit should support HTML entities that expand to more than one character
[WebKit-https.git] / Source / WebCore / html / parser / HTMLEntitySearch.cpp
1 /*
2  * Copyright (C) 2010 Google, Inc. All Rights Reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE 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 "HTMLEntitySearch.h"
28
29 #include "HTMLEntityTable.h"
30
31 namespace WebCore {
32
33 namespace {
34     
35 const HTMLEntityTableEntry* halfway(const HTMLEntityTableEntry* left, const HTMLEntityTableEntry* right)
36 {
37     return &left[(right - left) / 2];
38 }
39
40 }
41     
42 HTMLEntitySearch::HTMLEntitySearch()
43     : m_currentLength(0)
44     , m_mostRecentMatch(0)
45     , m_first(HTMLEntityTable::firstEntry())
46     , m_last(HTMLEntityTable::lastEntry())
47 {
48 }
49
50 HTMLEntitySearch::CompareResult HTMLEntitySearch::compare(const HTMLEntityTableEntry* entry, UChar nextCharacter) const
51 {
52     if (entry->length < m_currentLength + 1)
53         return Before;
54     UChar entryNextCharacter = entry->entity[m_currentLength];
55     if (entryNextCharacter == nextCharacter)
56         return Prefix;
57     return entryNextCharacter < nextCharacter ? Before : After;
58 }
59
60 const HTMLEntityTableEntry* HTMLEntitySearch::findFirst(UChar nextCharacter) const
61 {
62     const HTMLEntityTableEntry* left = m_first;
63     const HTMLEntityTableEntry* right = m_last;
64     if (left == right)
65         return left;
66     CompareResult result = compare(left, nextCharacter);
67     if (result == Prefix)
68         return left;
69     if (result == After)
70         return right;
71     while (left + 1 < right) {
72         const HTMLEntityTableEntry* probe = halfway(left, right);
73         result = compare(probe, nextCharacter);
74         if (result == Before)
75             left = probe;
76         else {
77             ASSERT(result == After || result == Prefix);
78             right = probe;
79         }
80     }
81     ASSERT(left + 1 == right);
82     return right;
83 }
84
85 const HTMLEntityTableEntry* HTMLEntitySearch::findLast(UChar nextCharacter) const
86 {
87     const HTMLEntityTableEntry* left = m_first;
88     const HTMLEntityTableEntry* right = m_last;
89     if (left == right)
90         return right;
91     CompareResult result = compare(right, nextCharacter);
92     if (result == Prefix)
93         return right;
94     if (result == Before)
95         return left;
96     while (left + 1 < right) {
97         const HTMLEntityTableEntry* probe = halfway(left, right);
98         result = compare(probe, nextCharacter);
99         if (result == After)
100             right = probe;
101         else {
102             ASSERT(result == Before || result == Prefix);
103             left = probe;
104         }
105     }
106     ASSERT(left + 1 == right);
107     return left;
108 }
109
110 void HTMLEntitySearch::advance(UChar nextCharacter)
111 {
112     ASSERT(isEntityPrefix());
113     if (!m_currentLength) {
114         m_first = HTMLEntityTable::firstEntryStartingWith(nextCharacter);
115         m_last = HTMLEntityTable::lastEntryStartingWith(nextCharacter);
116         if (!m_first || !m_last)
117             return fail();
118     } else {
119         m_first = findFirst(nextCharacter);
120         m_last = findLast(nextCharacter);
121         if (m_first == m_last && compare(m_first, nextCharacter) != Prefix)
122             return fail();
123     }
124     ++m_currentLength;
125     if (m_first->length != m_currentLength) {
126         return;
127     }
128     m_mostRecentMatch = m_first;
129 }
130
131 }