Debian Codegraph @

scintilla/lexilla/lexlib/WordList.cxx

raw
1 // Scintilla source code edit control
2 /** @file WordList.cxx
3 ** Hold a list of words.
4 **/
5 // Copyright 1998-2002 by Neil Hodgson <[email protected]>
6 // The License.txt file describes the conditions under which this software may be distributed.
7
8 #include <cstdlib>
9 #include <cassert>
10 #include <cstring>
11
12 #include <string>
13 #include <algorithm>
14 #include <iterator>
15 #include <memory>
16
17 #include "WordList.h"
18 #include "CharacterSet.h"
19
20 using namespace Lexilla;
21
22 namespace {
23
24 /**
25 * Creates an array that points into each word in the string and puts \0 terminators
26 * after each word.
27 */
28 std::unique_ptr<char *[]> ArrayFromWordList(char *wordlist, size_t slen, size_t *len, bool onlyLineEnds = false) {
29 assert(wordlist);
30 size_t words = 0;
31 // For rapid determination of whether a character is a separator, build
32 // a look up table.
33 bool wordSeparator[256] = {}; // Initialise all to false.
34 wordSeparator[static_cast<unsigned int>('\r')] = true;
35 wordSeparator[static_cast<unsigned int>('\n')] = true;
36 if (!onlyLineEnds) {
37 wordSeparator[static_cast<unsigned int>(' ')] = true;
38 wordSeparator[static_cast<unsigned int>('\t')] = true;
39 }
40 unsigned char prev = '\n';
41 for (int j = 0; wordlist[j]; j++) {
42 const unsigned char curr = wordlist[j];
43 if (!wordSeparator[curr] && wordSeparator[prev])
44 words++;
45 prev = curr;
46 }
47 std::unique_ptr<char *[]> keywords = std::make_unique<char *[]>(words + 1);
48 size_t wordsStore = 0;
49 if (words) {
50 unsigned char previous = '\0';
51 for (size_t k = 0; k < slen; k++) {
52 if (!wordSeparator[static_cast<unsigned char>(wordlist[k])]) {
53 if (!previous) {
54 keywords[wordsStore] = &wordlist[k];
55 wordsStore++;
56 }
57 } else {
58 wordlist[k] = '\0';
59 }
60 previous = wordlist[k];
61 }
62 }
63 assert(wordsStore < (words + 1));
64 keywords[wordsStore] = &wordlist[slen];
65 *len = wordsStore;
66 return keywords;
67 }
68
69 bool cmpWords(const char *a, const char *b) noexcept {
70 return strcmp(a, b) < 0;
71 }
72
73 }
74
75 WordList::WordList(bool onlyLineEnds_) noexcept :
76 words(nullptr), list(nullptr), len(0), onlyLineEnds(onlyLineEnds_) {
77 // Prevent warnings by static analyzers about uninitialized starts.
78 starts[0] = -1;
79 }
80
81 WordList::~WordList() {
82 Clear();
83 }
84
85 WordList::operator bool() const noexcept {
86 return len != 0;
87 }
88
89 bool WordList::operator!=(const WordList &other) const noexcept {
90 if (len != other.len)
91 return true;
92 for (size_t i=0; i<len; i++) {
93 if (strcmp(words[i], other.words[i]) != 0)
94 return true;
95 }
96 return false;
97 }
98
99 int WordList::Length() const noexcept {
100 return static_cast<int>(len);
101 }
102
103 void WordList::Clear() noexcept {
104 delete []list;
105 list = nullptr;
106 delete []words;
107 words = nullptr;
108 len = 0;
109 }
110
111 bool WordList::Set(const char *s, bool lowerCase) {
112 const size_t lenS = strlen(s) + 1;
113 std::unique_ptr<char[]> listTemp = std::make_unique<char[]>(lenS);
114 memcpy(listTemp.get(), s, lenS);
115 if (lowerCase) {
116 for (size_t i = 0; i < lenS; i++) {
117 listTemp[i] = MakeLowerCase(listTemp[i]);
118 }
119 }
120 size_t lenTemp = 0;
121 std::unique_ptr<char *[]> wordsTemp = ArrayFromWordList(listTemp.get(), lenS - 1, &lenTemp, onlyLineEnds);
122 std::sort(wordsTemp.get(), wordsTemp.get() + lenTemp, cmpWords);
123
124 if (lenTemp == len) {
125 bool changed = false;
126 for (size_t i = 0; i < lenTemp; i++) {
127 if (strcmp(words[i], wordsTemp[i]) != 0) {
128 changed = true;
129 break;
130 }
131 }
132 if (!changed) {
133 return false;
134 }
135 }
136
137 Clear();
138 words = wordsTemp.release();
139 list = listTemp.release();
140 len = lenTemp;
141 std::fill(starts, std::end(starts), -1);
142 for (int l = static_cast<int>(len - 1); l >= 0; l--) {
143 unsigned char const indexChar = words[l][0];
144 starts[indexChar] = l;
145 }
146 return true;
147 }
148
149 /** Check whether a string is in the list.
150 * List elements are either exact matches or prefixes.
151 * Prefix elements start with '^' and match all strings that start with the rest of the element
152 * so '^GTK_' matches 'GTK_X', 'GTK_MAJOR_VERSION', and 'GTK_'.
153 */
154 bool WordList::InList(const char *s) const noexcept {
155 if (!words)
156 return false;
157 const char first = s[0];
158 const unsigned char firstChar = first;
159 int j = starts[firstChar];
160 if (j >= 0) {
161 while (words[j][0] == first) {
162 if (s[1] == words[j][1]) {
163 const char *a = words[j] + 1;
164 const char *b = s + 1;
165 while (*a && *a == *b) {
166 a++;
167 b++;
168 }
169 if (!*a && !*b)
170 return true;
171 }
172 j++;
173 }
174 }
175 j = starts[static_cast<unsigned int>('^')];
176 if (j >= 0) {
177 while (words[j][0] == '^') {
178 const char *a = words[j] + 1;
179 const char *b = s;
180 while (*a && *a == *b) {
181 a++;
182 b++;
183 }
184 if (!*a)
185 return true;
186 j++;
187 }
188 }
189 return false;
190 }
191
192 /** convenience overload so can easily call with std::string.
193 */
194 bool WordList::InList(const std::string &s) const noexcept {
195 return InList(s.c_str());
196 }
197
198 /** similar to InList, but word s can be a substring of keyword.
199 * eg. the keyword define is defined as def~ine. This means the word must start
200 * with def to be a keyword, but also defi, defin and define are valid.
201 * The marker is ~ in this case.
202 */
203 bool WordList::InListAbbreviated(const char *s, const char marker) const noexcept {
204 if (!words)
205 return false;
206 const char first = s[0];
207 const unsigned char firstChar = first;
208 int j = starts[firstChar];
209 if (j >= 0) {
210 while (words[j][0] == first) {
211 bool isSubword = false;
212 int start = 1;
213 if (words[j][1] == marker) {
214 isSubword = true;
215 start++;
216 }
217 if (s[1] == words[j][start]) {
218 const char *a = words[j] + start;
219 const char *b = s + 1;
220 while (*a && *a == *b) {
221 a++;
222 if (*a == marker) {
223 isSubword = true;
224 a++;
225 }
226 b++;
227 }
228 if ((!*a || isSubword) && !*b)
229 return true;
230 }
231 j++;
232 }
233 }
234 j = starts[static_cast<unsigned int>('^')];
235 if (j >= 0) {
236 while (words[j][0] == '^') {
237 const char *a = words[j] + 1;
238 const char *b = s;
239 while (*a && *a == *b) {
240 a++;
241 b++;
242 }
243 if (!*a)
244 return true;
245 j++;
246 }
247 }
248 return false;
249 }
250
251 /** similar to InListAbbreviated, but word s can be an abridged version of a keyword.
252 * eg. the keyword is defined as "after.~:". This means the word must have a prefix (begins with) of
253 * "after." and suffix (ends with) of ":" to be a keyword, Hence "after.field:" , "after.form.item:" are valid.
254 * Similarly "~.is.valid" keyword is suffix only... hence "field.is.valid" , "form.is.valid" are valid.
255 * The marker is ~ in this case.
256 * No multiple markers check is done and wont work.
257 */
258 bool WordList::InListAbridged(const char *s, const char marker) const noexcept {
259 if (!words)
260 return false;
261 const char first = s[0];
262 const unsigned char firstChar = first;
263 int j = starts[firstChar];
264 if (j >= 0) {
265 while (words[j][0] == first) {
266 const char *a = words[j];
267 const char *b = s;
268 while (*a && *a == *b) {
269 a++;
270 if (*a == marker) {
271 a++;
272 const size_t suffixLengthA = strlen(a);
273 const size_t suffixLengthB = strlen(b);
274 if (suffixLengthA >= suffixLengthB)
275 break;
276 b = b + suffixLengthB - suffixLengthA - 1;
277 }
278 b++;
279 }
280 if (!*a && !*b)
281 return true;
282 j++;
283 }
284 }
285
286 j = starts[static_cast<unsigned int>(marker)];
287 if (j >= 0) {
288 while (words[j][0] == marker) {
289 const char *a = words[j] + 1;
290 const char *b = s;
291 const size_t suffixLengthA = strlen(a);
292 const size_t suffixLengthB = strlen(b);
293 if (suffixLengthA > suffixLengthB) {
294 j++;
295 continue;
296 }
297 b = b + suffixLengthB - suffixLengthA;
298
299 while (*a && *a == *b) {
300 a++;
301 b++;
302 }
303 if (!*a && !*b)
304 return true;
305 j++;
306 }
307 }
308
309 return false;
310 }
311
312 const char *WordList::WordAt(int n) const noexcept {
313 return words[n];
314 }
315