1use std::cmp::Ordering;
4
5use rupg_common::SqlState;
6
7use crate::binary::Recv;
8use crate::error::TypeError;
9
10pub const TSVECTOR_MAX_WORD: usize = (1 << 11) - 1;
12
13pub const TSVECTOR_MAX_DATA: usize = (1 << 20) - 1;
15
16pub const TSVECTOR_MAX_POSITIONS: usize = 256;
18
19const MAX_ENTRY_POS: u16 = 1 << 14;
21
22#[derive(Clone, Debug, PartialEq, Eq)]
24pub struct Lexeme {
25 pub word: String,
26 pub positions: Vec<u16>,
27}
28
29pub fn position_of(pos: u16) -> u16 {
31 pos & 0x3fff
32}
33
34pub fn weight_of(pos: u16) -> u16 {
36 pos >> 14
37}
38
39pub fn with_weight(pos: u16, weight: u16) -> u16 {
41 position_of(pos) | ((weight & 3) << 14)
42}
43
44pub fn limit_position(pos: i32) -> u16 {
46 let limited = if pos >= i32::from(MAX_ENTRY_POS) { i32::from(MAX_ENTRY_POS) - 1 } else { pos };
47 u16::try_from(limited & 0x3fff).unwrap_or(0)
48}
49
50pub fn ts_compare_string(a: &[u8], b: &[u8]) -> i32 {
52 if a.is_empty() {
53 return if b.is_empty() { 0 } else { -1 };
54 }
55 if b.is_empty() {
56 return 1;
57 }
58 if let Some((x, y)) = a.iter().zip(b).find(|(x, y)| x != y) {
59 return i32::from(*x) - i32::from(*y);
60 }
61 match a.len().cmp(&b.len()) {
62 Ordering::Less => -1,
63 Ordering::Equal => 0,
64 Ordering::Greater => 1,
65 }
66}
67
68fn word_order(a: &str, b: &str) -> Ordering {
70 ts_compare_string(a.as_bytes(), b.as_bytes()).cmp(&0)
71}
72
73pub fn tsvector_data_len(lexemes: &[Lexeme]) -> usize {
75 lexemes.iter().fold(0, |len, lexeme| {
76 let len = len + lexeme.word.len();
77 if lexeme.positions.is_empty() {
78 len
79 } else {
80 len.next_multiple_of(2) + 2 + 2 * lexeme.positions.len()
81 }
82 })
83}
84
85pub fn tsvector_size(lexemes: &[Lexeme]) -> usize {
87 8 + 4 * lexemes.len() + tsvector_data_len(lexemes)
88}
89
90pub fn tsvector_cmp(a: &[Lexeme], b: &[Lexeme]) -> i32 {
92 let sign = |order: Ordering| match order {
93 Ordering::Less => -1,
94 Ordering::Equal => 0,
95 Ordering::Greater => 1,
96 };
97 let order = tsvector_size(a).cmp(&tsvector_size(b)).then(a.len().cmp(&b.len()));
98 if order.is_ne() {
99 return sign(order);
100 }
101 for (x, y) in a.iter().zip(b) {
102 let has = !x.positions.is_empty();
103 if has != !y.positions.is_empty() {
104 return if has { -1 } else { 1 };
105 }
106 let words = ts_compare_string(x.word.as_bytes(), y.word.as_bytes());
107 if words != 0 {
108 return words;
109 }
110 let order = y.positions.len().cmp(&x.positions.len());
111 if order.is_ne() {
112 return sign(order);
113 }
114 for (&p, &q) in x.positions.iter().zip(&y.positions) {
115 let order =
116 position_of(q).cmp(&position_of(p)).then_with(|| weight_of(q).cmp(&weight_of(p)));
117 if order.is_ne() {
118 return sign(order);
119 }
120 }
121 }
122 0
123}
124
125pub fn unique_positions(mut positions: Vec<u16>) -> Vec<u16> {
127 if positions.len() <= 1 {
128 return positions;
129 }
130 positions.sort_by_key(|&pos| position_of(pos));
131 let mut out: Vec<u16> = Vec::with_capacity(positions.len());
132 for pos in positions {
133 match out.last_mut() {
134 Some(last) if position_of(*last) == position_of(pos) => {
135 if weight_of(pos) > weight_of(*last) {
136 *last = with_weight(*last, weight_of(pos));
137 }
138 }
139 _ => {
140 out.push(pos);
141 if out.len() >= TSVECTOR_MAX_POSITIONS || position_of(pos) == MAX_ENTRY_POS - 1 {
142 break;
143 }
144 }
145 }
146 }
147 out
148}
149
150fn unique_entries(mut lexemes: Vec<Lexeme>) -> Vec<Lexeme> {
152 lexemes.sort_by(|a, b| word_order(&a.word, &b.word));
153 let mut out: Vec<Lexeme> = Vec::with_capacity(lexemes.len());
154 for lexeme in lexemes {
155 match out.last_mut() {
156 Some(last) if last.word == lexeme.word => last.positions.extend(lexeme.positions),
157 _ => out.push(lexeme),
158 }
159 }
160 for lexeme in &mut out {
161 lexeme.positions = unique_positions(std::mem::take(&mut lexeme.positions));
162 }
163 out
164}
165
166fn too_long(len: usize) -> TypeError {
168 TypeError::new(
169 SqlState::PROGRAM_LIMIT_EXCEEDED,
170 format!("string is too long for tsvector ({len} bytes, max {TSVECTOR_MAX_DATA} bytes)"),
171 )
172}
173
174pub fn word_too_long(len: usize) -> TypeError {
176 TypeError::new(
177 SqlState::PROGRAM_LIMIT_EXCEEDED,
178 format!("word is too long ({len} bytes, max {TSVECTOR_MAX_WORD} bytes)"),
179 )
180}
181
182pub(crate) fn is_space(c: char) -> bool {
184 matches!(c, ' ' | '\t' | '\n' | '\r' | '\u{0b}' | '\u{0c}')
185}
186
187#[derive(Clone, Copy, PartialEq, Eq)]
189enum State {
190 WaitWord,
191 WaitEndWord,
192 WaitNextChar,
193 WaitEndComplex,
194 WaitCharComplex,
195 WaitPosInfo,
196 InPosInfo,
197 WaitPosDelim,
198}
199
200struct Parser<'a> {
202 text: &'a str,
203 at: usize,
204}
205
206impl Parser<'_> {
207 fn syntax(&self) -> TypeError {
208 TypeError::new(
209 SqlState::SYNTAX_ERROR,
210 format!("syntax error in tsvector: \"{}\"", self.text),
211 )
212 }
213
214 fn atoi(&self) -> i32 {
216 let digits = self.text[self.at..].bytes().take_while(u8::is_ascii_digit);
217 let value =
218 digits.fold(0i64, |v, d| v.saturating_mul(10).saturating_add(i64::from(d - b'0')));
219 u32::try_from(value & 0xffff_ffff).unwrap_or(0).cast_signed()
220 }
221
222 fn token(&mut self) -> Result<Option<Lexeme>, TypeError> {
224 let mut word = String::new();
225 let mut positions: Vec<u16> = Vec::new();
226 let mut state = State::WaitWord;
227 let mut old = State::WaitEndWord;
228 loop {
229 let c = self.text[self.at..].chars().next();
230 match state {
231 State::WaitWord => match c {
232 None => return Ok(None),
233 Some('\'') => state = State::WaitEndComplex,
234 Some('\\') => {
235 state = State::WaitNextChar;
236 old = State::WaitEndWord;
237 }
238 Some(c) if is_space(c) => {}
239 Some(c) => {
240 word.push(c);
241 state = State::WaitEndWord;
242 }
243 },
244 State::WaitNextChar => match c {
245 None => {
246 return Err(TypeError::new(
247 SqlState::SYNTAX_ERROR,
248 format!("there is no escaped character: \"{}\"", self.text),
249 ));
250 }
251 Some(c) => {
252 word.push(c);
253 state = old;
254 }
255 },
256 State::WaitEndWord => match c {
257 Some('\\') => {
258 state = State::WaitNextChar;
259 old = State::WaitEndWord;
260 }
261 None => break,
262 Some(c) if is_space(c) => break,
263 Some(':') => state = State::InPosInfo,
264 Some(c) => word.push(c),
265 },
266 State::WaitEndComplex => match c {
267 Some('\'') => state = State::WaitCharComplex,
268 Some('\\') => {
269 state = State::WaitNextChar;
270 old = State::WaitEndComplex;
271 }
272 None => return Err(self.syntax()),
273 Some(c) => word.push(c),
274 },
275 State::WaitCharComplex => {
276 if c == Some('\'') {
277 word.push('\'');
278 state = State::WaitEndComplex;
279 } else {
280 if word.is_empty() {
281 return Err(self.syntax());
282 }
283 state = State::WaitPosInfo;
285 continue;
286 }
287 }
288 State::WaitPosInfo => {
289 if c != Some(':') {
290 break;
291 }
292 state = State::InPosInfo;
293 }
294 State::InPosInfo => match c {
295 Some(c) if c.is_ascii_digit() => {
296 let pos = limit_position(self.atoi());
297 if pos == 0 {
298 return Err(TypeError::new(
299 SqlState::SYNTAX_ERROR,
300 format!("wrong position info in tsvector: \"{}\"", self.text),
301 ));
302 }
303 positions.push(pos);
304 state = State::WaitPosDelim;
305 }
306 _ => return Err(self.syntax()),
307 },
308 State::WaitPosDelim => {
309 let weight = match c {
310 Some(',') => {
311 state = State::InPosInfo;
312 None
313 }
314 Some('a' | 'A' | '*') => Some(3),
315 Some('b' | 'B') => Some(2),
316 Some('c' | 'C') => Some(1),
317 Some('d' | 'D') => Some(0),
318 None => break,
319 Some(c) if is_space(c) => break,
320 Some(c) if c.is_ascii_digit() => None,
321 Some(_) => return Err(self.syntax()),
322 };
323 if let (Some(weight), Some(last)) = (weight, positions.last_mut()) {
324 if weight_of(*last) != 0 {
325 return Err(self.syntax());
326 }
327 *last = with_weight(*last, weight);
328 }
329 }
330 }
331 self.at += c.map_or(0, char::len_utf8);
332 }
333 Ok(Some(Lexeme { word, positions }))
334 }
335}
336
337pub fn tsvector_parse(text: &str) -> Result<Vec<Lexeme>, TypeError> {
343 let mut parser = Parser { text, at: 0 };
344 let mut lexemes = Vec::new();
345 let mut total = 0;
346 while let Some(lexeme) = parser.token()? {
347 if lexeme.word.len() > TSVECTOR_MAX_WORD {
348 return Err(word_too_long(lexeme.word.len()));
349 }
350 if total > TSVECTOR_MAX_DATA {
351 return Err(too_long(total));
352 }
353 total += lexeme.word.len();
354 lexemes.push(lexeme);
355 }
356 let lexemes = unique_entries(lexemes);
357 let len = tsvector_data_len(&lexemes);
358 if len > TSVECTOR_MAX_DATA {
359 return Err(too_long(len));
360 }
361 Ok(lexemes)
362}
363
364pub fn tsvector_deparse(lexemes: &[Lexeme], out: &mut Vec<u8>) {
366 for (i, lexeme) in lexemes.iter().enumerate() {
367 if i > 0 {
368 out.push(b' ');
369 }
370 out.push(b'\'');
371 for &b in lexeme.word.as_bytes() {
372 if b == b'\'' || b == b'\\' {
373 out.push(b);
374 }
375 out.push(b);
376 }
377 out.push(b'\'');
378 for (j, &pos) in lexeme.positions.iter().enumerate() {
379 out.push(if j == 0 { b':' } else { b',' });
380 out.extend_from_slice(position_of(pos).to_string().as_bytes());
381 match weight_of(pos) {
382 3 => out.push(b'A'),
383 2 => out.push(b'B'),
384 1 => out.push(b'C'),
385 _ => {}
386 }
387 }
388 }
389}
390
391pub fn tsvector_send(lexemes: &[Lexeme], out: &mut Vec<u8>) {
393 let count = i32::try_from(lexemes.len()).unwrap_or(i32::MAX);
394 out.extend_from_slice(&count.to_be_bytes());
395 for lexeme in lexemes {
396 out.extend_from_slice(lexeme.word.as_bytes());
397 out.push(0);
398 let npos = u16::try_from(lexeme.positions.len()).unwrap_or(u16::MAX);
399 out.extend_from_slice(&npos.to_be_bytes());
400 for pos in &lexeme.positions {
401 out.extend_from_slice(&pos.to_be_bytes());
402 }
403 }
404}
405
406fn invalid(message: &str) -> TypeError {
408 TypeError::new(SqlState::INTERNAL_ERROR, message.to_string())
409}
410
411pub fn tsvector_recv(recv: &mut Recv<'_>) -> Result<Vec<Lexeme>, TypeError> {
417 let count = recv.i32()?;
418 let count = match usize::try_from(count) {
419 Ok(count) if count <= TSVECTOR_MAX_DATA => count,
420 _ => return Err(invalid("invalid size of tsvector")),
421 };
422 let mut lexemes: Vec<Lexeme> = Vec::with_capacity(count.min(recv.remaining()));
423 let mut len = 0;
424 let mut sorted = true;
425 for _ in 0..count {
426 let word = recv.cstring()?;
427 let npos = usize::from(recv.i16()?.cast_unsigned());
428 if word.is_empty() {
429 return Err(invalid("invalid tsvector: empty lexeme"));
430 }
431 if word.len() > TSVECTOR_MAX_WORD {
432 return Err(invalid("invalid tsvector: lexeme too long"));
433 }
434 if len > TSVECTOR_MAX_DATA {
435 return Err(invalid("invalid tsvector: maximum total lexeme length exceeded"));
436 }
437 if npos > TSVECTOR_MAX_POSITIONS {
438 return Err(invalid("unexpected number of tsvector positions"));
439 }
440 len += word.len();
441 if lexemes.last().is_some_and(|last| word_order(word, &last.word).is_le()) {
442 sorted = false;
443 }
444 let mut positions: Vec<u16> = Vec::with_capacity(npos);
445 for _ in 0..npos {
446 let pos = recv.i16()?.cast_unsigned();
447 if positions.last().is_some_and(|&last| position_of(pos) <= position_of(last)) {
448 return Err(invalid("position information is misordered"));
449 }
450 positions.push(pos);
451 }
452 if npos > 0 {
453 len = len.next_multiple_of(2) + 2 + 2 * npos;
454 }
455 lexemes.push(Lexeme { word: word.to_string(), positions });
456 }
457 if len > TSVECTOR_MAX_DATA {
458 return Err(invalid("invalid tsvector: maximum total lexeme length exceeded"));
459 }
460 if !sorted {
461 lexemes.sort_by(|a, b| word_order(&a.word, &b.word));
462 }
463 Ok(lexemes)
464}
465
466#[cfg(test)]
467mod tests {
468 use super::*;
469
470 fn text(input: &str) -> String {
471 let lexemes = tsvector_parse(input).expect("parse");
472 let mut out = Vec::new();
473 tsvector_deparse(&lexemes, &mut out);
474 String::from_utf8(out).expect("utf8")
475 }
476
477 fn error(input: &str) -> (String, String) {
478 let error = tsvector_parse(input).expect_err("error");
479 (error.sqlstate.to_string(), error.message)
480 }
481
482 #[test]
483 fn parse_and_deparse() {
484 assert_eq!(
485 text("a fat cat sat on a mat and ate a fat rat"),
486 "'a' 'and' 'ate' 'cat' 'fat' 'mat' 'on' 'rat' 'sat'"
487 );
488 assert_eq!(
489 text(r"the 'quick brown' fox's \\ tail"),
490 r"'\\' 'fox''s' 'quick brown' 'tail' 'the'"
491 );
492 assert_eq!(
493 text("a:1 fat:2,4 cat:3A b:5B,6C,7D x:3,1,2,1"),
494 "'a':1 'b':5B,6C,7 'cat':3A 'fat':2,4 'x':1,2,3"
495 );
496 assert_eq!(text("a:1A,1B,1C a:1 b:2C,2A"), "'a':1A 'b':2A");
497 assert_eq!(text("z:5 y z:1,3B"), "'y' 'z':1,3B,5");
498 assert_eq!(text(" "), "");
499 assert_eq!(text(r"'it''s' 'a\'b' 'c\\d' e\ f"), r"'a''b' 'c\\d' 'e f' 'it''s'");
500 assert_eq!(text("a:1*,2a,3b"), "'a':1A,2A,3B");
501 assert_eq!(
502 text("a:20000 b:16383 c:16384 d:99999999999"),
503 "'a':16383 'b':16383 'c':16383 'd':16383"
504 );
505 assert_eq!(text("a:1A2"), "'a':1A");
506 assert_eq!(text("b:3DA"), "'b':3A");
507 assert_eq!(text("a:1DD"), "'a':1");
508 assert_eq!(text("d:5,5A,5,4C"), "'d':4C,5A");
509 assert_eq!(text("'a'b"), "'a' 'b'");
510 assert_eq!(text("a'b'"), "'a''b'''");
511 assert_eq!(text("'a':1 'a'"), "'a':1");
512 assert_eq!(text("'a' :1"), "':1' 'a'");
513 assert_eq!(text(":1"), "':1'");
514 assert_eq!(text("а б в ä é 中文:1"), "'ä' 'é' 'а' 'б' 'в' '中文':1");
515 }
516
517 #[test]
518 fn parse_errors() {
519 let syntax =
520 |input: &str| ("42601".to_string(), format!("syntax error in tsvector: \"{input}\""));
521 for input in ["a:1A2 b:3DA c:4,5x", "a:", "a:1AB", "'abc", "a: 1", "''", "a:1,2,3x", "a:1,"]
522 {
523 assert_eq!(error(input), syntax(input), "{input}");
524 }
525 for input in ["a:0", "a:4294967296"] {
526 assert_eq!(
527 error(input),
528 ("42601".to_string(), format!("wrong position info in tsvector: \"{input}\""))
529 );
530 }
531 assert_eq!(
532 error(r"abc\"),
533 ("42601".to_string(), r#"there is no escaped character: "abc\""#.to_string())
534 );
535 assert_eq!(
536 error(&"x".repeat(2048)),
537 ("54000".to_string(), "word is too long (2048 bytes, max 2047 bytes)".to_string())
538 );
539 assert!(tsvector_parse(&"x".repeat(2047)).is_ok());
540 }
541
542 #[test]
543 fn positions() {
544 let many: Vec<String> = (1..=300).map(|i| i.to_string()).collect();
545 let lexemes = tsvector_parse(&format!("a:{}", many.join(","))).expect("parse");
546 assert_eq!(lexemes[0].positions.len(), 256);
547 assert_eq!(lexemes[0].positions[255], 256);
548 }
549
550 #[test]
551 fn order() {
552 let v = |input: &str| tsvector_parse(input).expect("parse");
553 let mut values: Vec<Vec<Lexeme>> =
554 ["b", "a:1", "ab", "a b", "", "a:1A", "a:1,2", "aaa"].iter().map(|s| v(s)).collect();
555 values.sort_by(|a, b| tsvector_cmp(a, b).cmp(&0));
556 let texts: Vec<String> = values
557 .iter()
558 .map(|value| {
559 let mut out = Vec::new();
560 tsvector_deparse(value, &mut out);
561 String::from_utf8(out).expect("utf8")
562 })
563 .collect();
564 assert_eq!(texts, ["", "'b'", "'ab'", "'aaa'", "'a':1A", "'a':1", "'a' 'b'", "'a':1,2"]);
565 assert_eq!(tsvector_cmp(&v("a"), &v("c")), -2);
566 assert_eq!(tsvector_cmp(&v("c"), &v("a")), 2);
567 assert_eq!(tsvector_cmp(&v("a:1"), &v("a:3")), 1);
568 assert_eq!(tsvector_cmp(&v("a:1A"), &v("a:1C")), -1);
569 assert_eq!(tsvector_cmp(&v("a:1"), &v("a")), 1);
570 assert_eq!(tsvector_cmp(&v("x y"), &v("xy z")), -1);
571 assert_eq!(tsvector_cmp(&v("b a c"), &v("c b a")), 0);
572 }
573
574 #[test]
575 fn binary() {
576 let lexemes = tsvector_parse("a:1 fat:2,4A cat").expect("parse");
577 let mut out = Vec::new();
578 tsvector_send(&lexemes, &mut out);
579 assert_eq!(
580 out,
581 b"\x00\x00\x00\x03a\x00\x00\x01\x00\x01cat\x00\x00\x00fat\x00\x00\x02\x00\x02\xc0\x04"
582 );
583 assert_eq!(tsvector_recv(&mut Recv::new(&out)).expect("recv"), lexemes);
584 let mut out = Vec::new();
585 tsvector_send(&tsvector_parse("x:16383C").expect("parse"), &mut out);
586 assert_eq!(out, b"\x00\x00\x00\x01x\x00\x00\x01\x7f\xff");
587 let recv = |bytes: &[u8]| tsvector_recv(&mut Recv::new(bytes)).map_err(|e| e.message);
588 assert_eq!(recv(b"\xff\xff\xff\xff"), Err("invalid size of tsvector".to_string()));
589 assert_eq!(
590 recv(b"\x00\x00\x00\x01\x00\x00\x00"),
591 Err("invalid tsvector: empty lexeme".to_string())
592 );
593 assert_eq!(recv(b"\x00\x00\x00\x01ab"), Err("invalid string in message".to_string()));
594 assert_eq!(
595 recv(b"\x00\x00\x00\x01a\x00\x00\x02\x00\x02\x00\x01"),
596 Err("position information is misordered".to_string())
597 );
598 assert_eq!(
599 recv(b"\x00\x00\x00\x01a\x00\x01\x01"),
600 Err("unexpected number of tsvector positions".to_string())
601 );
602 let sorted = recv(b"\x00\x00\x00\x02b\x00\x00\x00a\x00\x00\x00").expect("recv");
603 assert_eq!(sorted.iter().map(|l| l.word.as_str()).collect::<Vec<_>>(), ["a", "b"]);
604 }
605}