Branch data Line data Source code
1 : : /** @file steminternal.cc
2 : : * @brief Base class for implementations of stemming algorithms
3 : : */
4 : : /* Derived from snowball's runtime/api.c:
5 : : *
6 : : * Copyright (c) 2001, Dr Martin Porter
7 : : * Copyright (c) 2004,2005, Richard Boulton
8 : : * Copyright (c) 2006,2007,2008,2009 Olly Betts
9 : : * All rights reserved.
10 : : *
11 : : * Redistribution and use in source and binary forms, with or without
12 : : * modification, are permitted provided that the following conditions are met:
13 : : *
14 : : * * Redistributions of source code must retain the above copyright notice,
15 : : * this list of conditions and the following disclaimer.
16 : : *
17 : : * * Redistributions in binary form must reproduce the above copyright
18 : : * notice, this list of conditions and the following disclaimer in the
19 : : * documentation and/or other materials provided with the distribution.
20 : : *
21 : : * * Neither the name of the <ORGANIZATION> nor the names of its contributors
22 : : * may be used to endorse or promote products derived from this software
23 : : * without specific prior written permission.
24 : : *
25 : : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
26 : : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 : : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 : : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
29 : : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 : : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 : : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 : : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 : : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 : : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 : : * POSSIBILITY OF SUCH DAMAGE.
36 : : */
37 : : /* Copyright (C) 2007,2010 Olly Betts
38 : : * Copyright (C) 2010 Evgeny Sizikov
39 : : *
40 : : * This program is free software; you can redistribute it and/or
41 : : * modify it under the terms of the GNU General Public License as
42 : : * published by the Free Software Foundation; either version 2 of the
43 : : * License, or (at your option) any later version.
44 : : *
45 : : * This program is distributed in the hope that it will be useful,
46 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
47 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
48 : : * GNU General Public License for more details.
49 : : *
50 : : * You should have received a copy of the GNU General Public License
51 : : * along with this program; if not, write to the Free Software
52 : : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
53 : : */
54 : :
55 : : #include <config.h>
56 : :
57 : : #include "steminternal.h"
58 : :
59 : : #include <xapian/error.h>
60 : :
61 : : #include "omassert.h"
62 : :
63 : : #include <cstdlib>
64 : : #include <cstring>
65 : :
66 : : #include <string>
67 : :
68 : : using namespace std;
69 : :
70 : : #define CREATE_SIZE 16
71 : :
72 : 32951 : extern symbol * create_s() {
73 : 32951 : void * mem = malloc(HEAD + (CREATE_SIZE + 1) * sizeof(symbol));
74 [ - + ]: 32951 : if (mem == NULL) throw std::bad_alloc();
75 : 32951 : symbol * p = reinterpret_cast<symbol*>(HEAD + static_cast<char *>(mem));
76 : 32951 : SET_CAPACITY(p, CREATE_SIZE);
77 : 32951 : SET_SIZE(p, CREATE_SIZE);
78 : 32951 : return p;
79 : : }
80 : :
81 : : /*
82 : : new_c = skip_utf8(p, c, lb, l, n); skips n characters forwards from p + c
83 : : if n +ve, or n characters backwards from p + c - 1 if n -ve. new_c is the new
84 : : value of the cursor c, or -1 on failure.
85 : :
86 : : -- used to implement hop and next in the utf8 case.
87 : : */
88 : :
89 : 120295619 : extern int skip_utf8(const symbol * p, int c, int lb, int l, int n) {
90 [ + + ]: 120295619 : if (n >= 0) {
91 [ + + ]: 239384279 : for (; n > 0; n--) {
92 [ + + ]: 123634517 : if (c >= l) return -1;
93 [ + + ]: 119482879 : if (p[c++] >= 0xC0) { /* 1100 0000 */
94 [ + + ]: 18023838 : while (c < l) {
95 : : /* break unless p[c] is 10------ */
96 [ + + ]: 17910865 : if (p[c] >> 6 != 2) break;
97 : 4637104 : c++;
98 : : }
99 : : }
100 : : }
101 : : } else {
102 [ + + ]: 843808 : for (; n < 0; n++) {
103 [ + + ]: 451990 : if (c <= lb) return -1;
104 [ + + ]: 449589 : if (p[--c] >= 0x80) { /* 1000 0000 */
105 [ + + ]: 32097 : while (c > lb) {
106 [ + + ]: 32042 : if (p[c] >= 0xC0) break; /* 1100 0000 */
107 : 18433 : c--;
108 : : }
109 : : }
110 : : }
111 : : }
112 : 120295619 : return c;
113 : : }
114 : :
115 : :
116 : : /* Increase the size of the buffer pointed to by p to at least n symbols.
117 : : * If insufficient memory, throw std::bad_alloc().
118 : : */
119 : 31772 : static symbol * increase_size(symbol * p, int n) {
120 : 31772 : int new_size = n + 20;
121 : : void * mem = realloc(reinterpret_cast<char *>(p) - HEAD,
122 : 31772 : HEAD + (new_size + 1) * sizeof(symbol));
123 [ - + ]: 31772 : if (mem == NULL) {
124 : 0 : throw std::bad_alloc();
125 : : }
126 : 31772 : symbol * q = reinterpret_cast<symbol*>(HEAD + static_cast<char *>(mem));
127 : 31772 : SET_CAPACITY(q, new_size);
128 : 31772 : return q;
129 : : }
130 : :
131 : : namespace Xapian {
132 : :
133 [ # # ][ # # ]: 32944 : StemImplementation::~StemImplementation() { }
[ - + ]
134 : :
135 : 32943 : SnowballStemImplementation::~SnowballStemImplementation()
136 : : {
137 : 32943 : lose_s(p);
138 [ # # ][ # # ]: 32943 : }
[ - + ]
139 : :
140 : : string
141 : 3367955 : SnowballStemImplementation::operator()(const string & word)
142 : : {
143 : 3367955 : const symbol * s = reinterpret_cast<const symbol *>(word.data());
144 : 3367955 : replace_s(0, l, word.size(), s);
145 : 3367955 : c = 0;
146 [ - + ]: 3367955 : if (stem() < 0) {
147 : : // FIXME: Is there a better choice of exception class?
148 : 0 : throw Xapian::InternalError("stemming exception!");
149 : : }
150 : 3367955 : return string(reinterpret_cast<const char *>(p), l);
151 : : }
152 : :
153 : : /* Code for character groupings: utf8 cases */
154 : :
155 : 86449087 : int SnowballStemImplementation::get_utf8(int * slot) {
156 : : int b0, b1;
157 : 86449087 : int tmp = c;
158 [ + + ]: 86449087 : if (tmp >= l) return 0;
159 : 83122780 : b0 = p[tmp++];
160 [ + + ][ + + ]: 83122780 : if (b0 < 0xC0 || tmp == l) { /* 1100 0000 */
161 : 74769208 : * slot = b0; return 1;
162 : : }
163 : 8353572 : b1 = p[tmp++];
164 [ + + ][ + + ]: 8353572 : if (b0 < 0xE0 || tmp == l) { /* 1110 0000 */
165 : 4471100 : * slot = (b0 & 0x1F) << 6 | (b1 & 0x3F); return 2;
166 : : }
167 : 86449087 : * slot = (b0 & 0xF) << 12 | (b1 & 0x3F) << 6 | (p[tmp] & 0x3F); return 3;
168 : : }
169 : :
170 : 37699600 : int SnowballStemImplementation::get_b_utf8(int * slot) {
171 : : int b0, b1;
172 : 37699600 : int tmp = c;
173 [ + + ]: 37699600 : if (tmp <= lb) return 0;
174 : 37144952 : b0 = p[--tmp];
175 [ + + ][ + + ]: 37144952 : if (b0 < 0x80 || tmp == lb) { /* 1000 0000 */
176 : 30340985 : * slot = b0; return 1;
177 : : }
178 : 6803967 : b1 = p[--tmp];
179 [ + + ][ + + ]: 6803967 : if (b1 >= 0xC0 || tmp == lb) { /* 1100 0000 */
180 : 2490015 : * slot = (b1 & 0x1F) << 6 | (b0 & 0x3F); return 2;
181 : : }
182 : 37699600 : * slot = (p[tmp] & 0xF) << 12 | (b1 & 0x3F) << 6 | (b0 & 0x3F); return 3;
183 : : }
184 : :
185 : : int
186 : 52801437 : SnowballStemImplementation::in_grouping_U(const unsigned char * s, int min,
187 : : int max, int repeat)
188 : : {
189 [ + + ]: 8692410 : do {
190 : : int ch;
191 : 52801437 : int w = get_utf8(&ch);
192 [ + + ]: 52801437 : if (!w) return -1;
193 [ + + ][ + + ]: 50462942 : if (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
[ + + ][ + + ]
194 : 41770532 : return w;
195 : 8692410 : c += w;
196 : : } while (repeat);
197 : 51759824 : return 0;
198 : : }
199 : :
200 : : int
201 : 876375 : SnowballStemImplementation::in_grouping_b_U(const unsigned char * s, int min,
202 : : int max, int repeat)
203 : : {
204 [ + + ]: 333134 : do {
205 : : int ch;
206 : 876375 : int w = get_b_utf8(&ch);
207 [ + + ]: 876375 : if (!w) return -1;
208 [ + + ][ + + ]: 861126 : if (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
[ + + ][ + + ]
209 : 527992 : return w;
210 : 333134 : c -= w;
211 : : } while (repeat);
212 : 848586 : return 0;
213 : : }
214 : :
215 : : int
216 : 33647650 : SnowballStemImplementation::out_grouping_U(const unsigned char * s, int min,
217 : : int max, int repeat)
218 : : {
219 [ + + ]: 27248927 : do {
220 : : int ch;
221 : 33647650 : int w = get_utf8(&ch);
222 [ + + ]: 33647650 : if (!w) return -1;
223 [ + + ][ + + ]: 32659838 : if (!(ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0))
[ + + ][ + + ]
224 : 5410911 : /* FIXME: try adding this so gopast in generated code is simpler: if (repeat == 2) c += w; */ return w;
225 : 27248927 : c += w;
226 : : } while (repeat);
227 : 8401737 : return 0;
228 : : }
229 : :
230 : : int
231 : 36823225 : SnowballStemImplementation::out_grouping_b_U(const unsigned char * s, int min,
232 : : int max, int repeat)
233 : : {
234 [ + + ]: 30863838 : do {
235 : : int ch;
236 : 36823225 : int w = get_b_utf8(&ch);
237 [ + + ]: 36823225 : if (!w) return -1;
238 [ + + ][ + + ]: 36283826 : if (!(ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0))
[ + + ][ + + ]
239 : 5419988 : return w;
240 : 30863838 : c -= w;
241 : : } while (repeat);
242 : 7099540 : return 0;
243 : : }
244 : :
245 : 17852313 : int SnowballStemImplementation::eq_s(int s_size, const symbol * s) {
246 [ + + ][ + + ]: 17852313 : if (l - c < s_size || memcmp(p + c, s, s_size * sizeof(symbol)) != 0)
247 : 17837567 : return 0;
248 : 14746 : c += s_size;
249 : 17852313 : return 1;
250 : : }
251 : :
252 : 3982151 : int SnowballStemImplementation::eq_s_b(int s_size, const symbol * s) {
253 [ + + ][ + + ]: 3982151 : if (c - lb < s_size || memcmp(p + c - s_size, s, s_size * sizeof(symbol)) != 0)
254 : 3599334 : return 0;
255 : 382817 : c -= s_size;
256 : 3982151 : return 1;
257 : : }
258 : :
259 : : int
260 : 18294112 : SnowballStemImplementation::find_among(const symbol * pool,
261 : : const struct among * v, int v_size,
262 : : const unsigned char * fnum,
263 : : const among_function * f)
264 : : {
265 : 18294112 : int i = 0;
266 : 18294112 : int j = v_size;
267 : :
268 : 18294112 : const symbol * q = p + c;
269 : 18294112 : int c_orig = c;
270 : :
271 : 18294112 : int common_i = 0;
272 : 18294112 : int common_j = 0;
273 : :
274 : 18294112 : int first_key_inspected = 0;
275 : :
276 : 36793451 : while (1) {
277 : 55087563 : int k = i + ((j - i) >> 1);
278 : 55087563 : int diff = 0;
279 [ + + ]: 55087563 : int common = common_i < common_j ? common_i : common_j; /* smaller */
280 : 55087563 : const struct among * w = v + k;
281 [ + + ]: 56443563 : for (int x = common; x < w->s_size; x++) {
282 [ + + ]: 49947374 : if (c_orig + common == l) { diff = -1; break; }
283 : 49048832 : diff = q[common] - (pool + w->s)[x];
284 [ + + ]: 49048832 : if (diff != 0) break;
285 : 1356000 : common++;
286 : : }
287 [ + + ]: 55087563 : if (diff < 0) { j = k; common_j = common; }
288 : 29573758 : else { i = k; common_i = common; }
289 [ + + ]: 55087563 : if (j - i <= 1) {
290 [ + + ]: 24676610 : if (i > 0) break; /* v->s has been inspected */
291 [ + + ]: 12764996 : if (j == i) break; /* only one item in v */
292 : :
293 : : /* - but now we need to go round once more to get
294 : : v->s inspected. This looks messy, but is actually
295 : : the optimal approach. */
296 : :
297 [ + + ]: 12692714 : if (first_key_inspected) break;
298 : 6382498 : first_key_inspected = 1;
299 : : }
300 : : }
301 : 29422527 : while (1) {
302 : 29422527 : const struct among * w = v + i;
303 [ + + ]: 29422527 : if (common_i >= w->s_size) {
304 : 17624604 : c = c_orig + w->s_size;
305 [ - + ][ # # ]: 17624604 : if (!fnum || !fnum[i]) return w->result;
306 : : {
307 : 0 : int res = f[fnum[i] - 1](this);
308 : 0 : c = c_orig + w->s_size;
309 [ # # ]: 0 : if (res) return w->result;
310 : : }
311 : : }
312 : 11797923 : i = w->substring_i;
313 [ + + ]: 11797923 : if (i < 0) return 0;
314 : : }
315 : : }
316 : :
317 : : /* find_among_b is for backwards processing. Same comments apply */
318 : : int
319 : 7583640 : SnowballStemImplementation::find_among_b(const symbol * pool,
320 : : const struct among * v, int v_size,
321 : : const unsigned char * fnum,
322 : : const among_function * f)
323 : : {
324 : 7583640 : int i = 0;
325 : 7583640 : int j = v_size;
326 : :
327 : 7583640 : const symbol * q = p + c - 1;
328 : 7583640 : int c_orig = c;
329 : :
330 : 7583640 : int common_i = 0;
331 : 7583640 : int common_j = 0;
332 : :
333 : 7583640 : int first_key_inspected = 0;
334 : :
335 : 22906612 : while (1) {
336 : 30490252 : int k = i + ((j - i) >> 1);
337 : 30490252 : int diff = 0;
338 [ + + ]: 30490252 : int common = common_i < common_j ? common_i : common_j;
339 : 30490252 : const struct among * w = v + k;
340 [ + + ]: 42690405 : for (int x = w->s_size - 1 - common; x >= 0; x--) {
341 [ + + ]: 41404924 : if (c_orig - common == lb) { diff = -1; break; }
342 : 38712036 : diff = q[- common] - (pool + w->s)[x];
343 [ + + ]: 38712036 : if (diff != 0) break;
344 : 12200153 : common++;
345 : : }
346 [ + + ]: 30490252 : if (diff < 0) { j = k; common_j = common; }
347 : 13110578 : else { i = k; common_i = common; }
348 [ + + ]: 30490252 : if (j - i <= 1) {
349 [ + + ]: 9932226 : if (i > 0) break;
350 [ + + ]: 4697172 : if (j == i) break;
351 [ + + ]: 3312010 : if (first_key_inspected) break;
352 : 2348586 : first_key_inspected = 1;
353 : : }
354 : : }
355 : 8940679 : while (1) {
356 : 8940679 : const struct among * w = v + i;
357 [ + + ]: 8940679 : if (common_i >= w->s_size) {
358 : 1522338 : c = c_orig - w->s_size;
359 [ + + ][ + + ]: 1522338 : if (!fnum || !fnum[i]) return w->result;
360 : : {
361 : 38415 : int res = f[fnum[i] - 1](this);
362 : 38415 : c = c_orig - w->s_size;
363 [ + + ]: 38415 : if (res) return w->result;
364 : : }
365 : : }
366 : 7422464 : i = w->substring_i;
367 [ + + ]: 7422464 : if (i < 0) return 0;
368 : : }
369 : : }
370 : :
371 : : int
372 : 5000850 : SnowballStemImplementation::replace_s(int c_bra, int c_ket, int s_size,
373 : : const symbol * s)
374 : : {
375 : : int adjustment;
376 : : int len;
377 : : Assert(p);
378 : 5000850 : adjustment = s_size - (c_ket - c_bra);
379 : 5000850 : len = SIZE(p);
380 [ + + ]: 5000850 : if (adjustment != 0) {
381 [ + + ]: 4291858 : if (adjustment + len > CAPACITY(p)) {
382 : 31771 : p = increase_size(p, adjustment + len);
383 : : }
384 : : memmove(p + c_ket + adjustment,
385 : : p + c_ket,
386 : 4291858 : (len - c_ket) * sizeof(symbol));
387 : 4291858 : SET_SIZE(p, adjustment + len);
388 : 4291858 : l += adjustment;
389 [ + + ]: 4291858 : if (c >= c_ket)
390 : 88059 : c += adjustment;
391 : : else
392 [ + + ]: 4203799 : if (c > c_bra)
393 : 10813 : c = c_bra;
394 : : }
395 [ + + ]: 5000850 : if (s_size != 0) memmove(p + c_bra, s, s_size * sizeof(symbol));
396 : 5000850 : return adjustment;
397 : : }
398 : :
399 : 1805865 : int SnowballStemImplementation::slice_check() {
400 : : Assert(p);
401 [ + - ][ + - ]: 1805865 : if (bra < 0 || bra > ket || ket > l) {
[ - + ]
402 : : #if 0
403 : : fprintf(stderr, "faulty slice operation:\n");
404 : : debug(z, -1, 0);
405 : : #endif
406 : 0 : return -1;
407 : : }
408 : 1805865 : return 0;
409 : : }
410 : :
411 : 1614265 : int SnowballStemImplementation::slice_from_s(int s_size, const symbol * s) {
412 [ - + ]: 1614265 : if (slice_check()) return -1;
413 : 1614265 : replace_s(bra, ket, s_size, s);
414 : 1614265 : return 0;
415 : : }
416 : :
417 : : void
418 : 18630 : SnowballStemImplementation::insert_s(int c_bra, int c_ket, int s_size,
419 : : const symbol * s)
420 : : {
421 : 18630 : int adjustment = replace_s(c_bra, c_ket, s_size, s);
422 [ + + ]: 18630 : if (c_bra <= bra) bra += adjustment;
423 [ + - ]: 18630 : if (c_bra <= ket) ket += adjustment;
424 : 18630 : }
425 : :
426 : 191600 : symbol * SnowballStemImplementation::slice_to(symbol * v) {
427 [ - + ]: 191600 : if (slice_check()) return NULL;
428 : : {
429 : 191600 : int len = ket - bra;
430 [ + + ]: 191600 : if (CAPACITY(v) < len) {
431 : 1 : v = increase_size(v, len);
432 : : }
433 : 191600 : memmove(v, p + bra, len * sizeof(symbol));
434 : 191600 : SET_SIZE(v, len);
435 : : }
436 : 191600 : return v;
437 : : }
438 : :
439 : 0 : symbol * SnowballStemImplementation::assign_to(symbol * v) {
440 : 0 : int len = l;
441 [ # # ]: 0 : if (CAPACITY(v) < len) {
442 : 0 : v = increase_size(v, len);
443 : : }
444 : 0 : memmove(v, p, len * sizeof(symbol));
445 : 0 : SET_SIZE(v, len);
446 : 0 : return v;
447 : : }
448 : :
449 : : #if 0
450 : : void SnowballStemImplementation::debug(int number, int line_count) {
451 : : int i;
452 : : int limit = SIZE(p);
453 : : /*if (number >= 0) printf("%3d (line %4d): '", number, line_count);*/
454 : : if (number >= 0) printf("%3d (line %4d): [%d]'", number, line_count,limit);
455 : : for (i = 0; i <= limit; i++) {
456 : : if (lb == i) printf("{");
457 : : if (bra == i) printf("[");
458 : : if (c == i) printf("|");
459 : : if (ket == i) printf("]");
460 : : if (l == i) printf("}");
461 : : if (i < limit)
462 : : { int ch = p[i];
463 : : if (ch == 0) ch = '#';
464 : : printf("%c", ch);
465 : : }
466 : : }
467 : : printf("'\n");
468 : : }
469 : : #endif
470 : : }
|
