1 /** @file steminternal.cc
2 * @brief Base class for implementations of stemming algorithms
4 /* Derived from snowball's runtime/api.c:
6 * Copyright (c) 2001, Dr Martin Porter
7 * Copyright (c) 2004,2005, Richard Boulton
8 * Copyright (c) 2006,2007,2008,2009,2016 Olly Betts
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions are met:
14 * * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
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.
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.
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.
37 /* Copyright (C) 2007,2010 Olly Betts
38 * Copyright (C) 2010 Evgeny Sizikov
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.
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.
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
57 #include "steminternal.h"
59 #include <xapian/error.h>
70 #define CREATE_SIZE 16
72 extern symbol
* create_s() {
73 void * mem
= malloc(HEAD
+ (CREATE_SIZE
+ 1) * sizeof(symbol
));
74 if (mem
== NULL
) throw std::bad_alloc();
75 symbol
* p
= reinterpret_cast<symbol
*>(HEAD
+ static_cast<char *>(mem
));
76 SET_CAPACITY(p
, CREATE_SIZE
);
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.
86 -- used to implement hop and next in the utf8 case.
89 extern int skip_utf8(const symbol
* p
, int c
, int lb
, int l
, int n
) {
92 if (c
>= l
) return -1;
93 if (p
[c
++] >= 0xC0) { /* 1100 0000 */
95 /* break unless p[c] is 10------ */
96 if (p
[c
] >> 6 != 2) break;
103 if (c
<= lb
) return -1;
104 if (p
[--c
] >= 0x80) { /* 1000 0000 */
106 if (p
[c
] >= 0xC0) break; /* 1100 0000 */
116 /* Increase the size of the buffer pointed to by p to at least n symbols.
117 * If insufficient memory, throw std::bad_alloc().
119 static symbol
* increase_size(symbol
* p
, int n
) {
120 int new_size
= n
+ 20;
121 void * mem
= realloc(reinterpret_cast<char *>(p
) - HEAD
,
122 HEAD
+ (new_size
+ 1) * sizeof(symbol
));
124 throw std::bad_alloc();
126 symbol
* q
= reinterpret_cast<symbol
*>(HEAD
+ static_cast<char *>(mem
));
127 SET_CAPACITY(q
, new_size
);
133 StemImplementation::~StemImplementation() { }
135 SnowballStemImplementation::~SnowballStemImplementation()
141 SnowballStemImplementation::operator()(const string
& word
)
143 const symbol
* s
= reinterpret_cast<const symbol
*>(word
.data());
144 replace_s(0, l
, word
.size(), s
);
147 // FIXME: Is there a better choice of exception class?
148 throw Xapian::InternalError("stemming exception!");
150 return string(reinterpret_cast<const char *>(p
), l
);
153 /* Code for character groupings: utf8 cases */
155 int SnowballStemImplementation::get_utf8(int * slot
) {
158 if (tmp
>= l
) return 0;
160 if (b0
< 0xC0 || tmp
== l
) { /* 1100 0000 */
161 * slot
= b0
; return 1;
164 if (b0
< 0xE0 || tmp
== l
) { /* 1110 0000 */
165 * slot
= (b0
& 0x1F) << 6 | (b1
& 0x3F); return 2;
167 * slot
= (b0
& 0xF) << 12 | (b1
& 0x3F) << 6 | (p
[tmp
] & 0x3F); return 3;
170 int SnowballStemImplementation::get_b_utf8(int * slot
) {
173 if (tmp
<= lb
) return 0;
175 if (b0
< 0x80 || tmp
== lb
) { /* 1000 0000 */
176 * slot
= b0
; return 1;
179 if (b1
>= 0xC0 || tmp
== lb
) { /* 1100 0000 */
180 * slot
= (b1
& 0x1F) << 6 | (b0
& 0x3F); return 2;
182 * slot
= (p
[tmp
] & 0xF) << 12 | (b1
& 0x3F) << 6 | (b0
& 0x3F); return 3;
186 SnowballStemImplementation::in_grouping_U(const unsigned char * s
, int min
,
191 int w
= get_utf8(&ch
);
193 if (ch
> max
|| (ch
-= min
) < 0 || (s
[ch
>> 3] & (0X1 << (ch
& 0X7))) == 0)
201 SnowballStemImplementation::in_grouping_b_U(const unsigned char * s
, int min
,
206 int w
= get_b_utf8(&ch
);
208 if (ch
> max
|| (ch
-= min
) < 0 || (s
[ch
>> 3] & (0X1 << (ch
& 0X7))) == 0)
216 SnowballStemImplementation::out_grouping_U(const unsigned char * s
, int min
,
221 int w
= get_utf8(&ch
);
223 if (!(ch
> max
|| (ch
-= min
) < 0 || (s
[ch
>> 3] & (0X1 << (ch
& 0X7))) == 0))
224 /* FIXME: try adding this so gopast in generated code is simpler: if (repeat == 2) c += w; */ return w
;
231 SnowballStemImplementation::out_grouping_b_U(const unsigned char * s
, int min
,
236 int w
= get_b_utf8(&ch
);
238 if (!(ch
> max
|| (ch
-= min
) < 0 || (s
[ch
>> 3] & (0X1 << (ch
& 0X7))) == 0))
245 int SnowballStemImplementation::eq_s(int s_size
, const symbol
* s
) {
246 if (l
- c
< s_size
|| memcmp(p
+ c
, s
, s_size
* sizeof(symbol
)) != 0)
252 int SnowballStemImplementation::eq_s_b(int s_size
, const symbol
* s
) {
253 if (c
- lb
< s_size
|| memcmp(p
+ c
- s_size
, s
, s_size
* sizeof(symbol
)) != 0)
260 SnowballStemImplementation::find_among(const symbol
* pool
,
261 const struct among
* v
, int v_size
,
262 const unsigned char * fnum
,
263 const among_function
* f
)
268 const symbol
* q
= p
+ c
;
274 int first_key_inspected
= 0;
277 int k
= i
+ ((j
- i
) >> 1);
279 int common
= common_i
< common_j
? common_i
: common_j
; /* smaller */
280 const struct among
* w
= v
+ k
;
281 for (int x
= common
; x
< w
->s_size
; x
++) {
282 if (c_orig
+ common
== l
) { diff
= -1; break; }
283 diff
= q
[common
] - (pool
+ w
->s
)[x
];
284 if (diff
!= 0) break;
287 if (diff
< 0) { j
= k
; common_j
= common
; }
288 else { i
= k
; common_i
= common
; }
290 if (i
> 0) break; /* v->s has been inspected */
291 if (j
== i
) break; /* only one item in v */
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. */
297 if (first_key_inspected
) break;
298 first_key_inspected
= 1;
302 const struct among
* w
= v
+ i
;
303 if (common_i
>= w
->s_size
) {
304 c
= c_orig
+ w
->s_size
;
305 if (!fnum
|| !fnum
[i
]) return w
->result
;
307 int res
= f
[fnum
[i
] - 1](this);
308 c
= c_orig
+ w
->s_size
;
309 if (res
) return w
->result
;
317 /* find_among_b is for backwards processing. Same comments apply */
319 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
)
327 const symbol
* q
= p
+ c
- 1;
333 int first_key_inspected
= 0;
336 int k
= i
+ ((j
- i
) >> 1);
338 int common
= common_i
< common_j
? common_i
: common_j
;
339 const struct among
* w
= v
+ k
;
340 for (int x
= w
->s_size
- 1 - common
; x
>= 0; x
--) {
341 if (c_orig
- common
== lb
) { diff
= -1; break; }
342 diff
= q
[- common
] - (pool
+ w
->s
)[x
];
343 if (diff
!= 0) break;
346 if (diff
< 0) { j
= k
; common_j
= common
; }
347 else { i
= k
; common_i
= common
; }
351 if (first_key_inspected
) break;
352 first_key_inspected
= 1;
356 const struct among
* w
= v
+ i
;
357 if (common_i
>= w
->s_size
) {
358 c
= c_orig
- w
->s_size
;
359 if (!fnum
|| !fnum
[i
]) return w
->result
;
361 int res
= f
[fnum
[i
] - 1](this);
362 c
= c_orig
- w
->s_size
;
363 if (res
) return w
->result
;
372 SnowballStemImplementation::replace_s(int c_bra
, int c_ket
, int s_size
,
378 adjustment
= s_size
- (c_ket
- c_bra
);
380 if (adjustment
!= 0) {
381 if (adjustment
+ len
> CAPACITY(p
)) {
382 p
= increase_size(p
, adjustment
+ len
);
384 memmove(p
+ c_ket
+ adjustment
,
386 (len
- c_ket
) * sizeof(symbol
));
387 SET_SIZE(p
, adjustment
+ len
);
395 if (s_size
!= 0) memmove(p
+ c_bra
, s
, s_size
* sizeof(symbol
));
399 int SnowballStemImplementation::slice_check() {
401 if (bra
< 0 || bra
> ket
|| ket
> l
) {
403 fprintf(stderr
, "faulty slice operation:\n");
411 int SnowballStemImplementation::slice_from_s(int s_size
, const symbol
* s
) {
412 if (slice_check()) return -1;
413 replace_s(bra
, ket
, s_size
, s
);
418 SnowballStemImplementation::insert_s(int c_bra
, int c_ket
, int s_size
,
421 int adjustment
= replace_s(c_bra
, c_ket
, s_size
, s
);
422 if (c_bra
<= bra
) bra
+= adjustment
;
423 if (c_bra
<= ket
) ket
+= adjustment
;
426 symbol
* SnowballStemImplementation::slice_to(symbol
* v
) {
427 if (slice_check()) return NULL
;
430 if (CAPACITY(v
) < len
) {
431 v
= increase_size(v
, len
);
433 memmove(v
, p
+ bra
, len
* sizeof(symbol
));
439 symbol
* SnowballStemImplementation::assign_to(symbol
* v
) {
441 if (CAPACITY(v
) < len
) {
442 v
= increase_size(v
, len
);
444 memmove(v
, p
, len
* sizeof(symbol
));
449 int SnowballStemImplementation::len_utf8(const symbol
* v
) {
454 if (b
>= 0xC0 || b
< 0x80) ++len
;
460 void SnowballStemImplementation::debug(int number
, int line_count
) {
463 /*if (number >= 0) printf("%3d (line %4d): '", number, line_count);*/
464 if (number
>= 0) printf("%3d (line %4d): [%d]'", number
, line_count
, limit
);
465 for (i
= 0; i
<= limit
; i
++) {
466 if (lb
== i
) printf("{");
467 if (bra
== i
) printf("[");
468 if (c
== i
) printf("|");
469 if (ket
== i
) printf("]");
470 if (l
== i
) printf("}");
473 if (ch
== 0) ch
= '#';