use std::borrow::Cow;
use std::cell::RefCell;
use std::rc::Rc;
use std::sync::Arc;
const STAND_IN_BASE: u32 = 0x10_F800;
pub fn is_reserved(cp: u32) -> bool {
(STAND_IN_BASE..=0x10_FFFF).contains(&cp)
}
pub fn is_surrogate(u: u32) -> bool {
(0xD800..=0xDFFF).contains(&u)
}
fn stand_in(u: u16) -> char {
char::from_u32(STAND_IN_BASE + u32::from(u - 0xD800)).expect("stand-in range is scalar")
}
pub fn unpaired(c: char) -> Option<u16> {
is_reserved(c as u32).then(|| (c as u32 - STAND_IN_BASE + 0xD800) as u16)
}
pub fn char_value(c: char) -> u32 {
unpaired(c).map_or(c as u32, u32::from)
}
pub fn char_of(unit_or_cp: u32) -> Option<char> {
if is_surrogate(unit_or_cp) {
Some(stand_in(unit_or_cp as u16))
} else {
char::from_u32(unit_or_cp)
}
}
pub fn checked_code_point(cp: i64) -> Result<Option<char>, String> {
match u32::try_from(cp) {
Ok(c) if is_reserved(c) => Err(reserved_message(c)),
Ok(c) => Ok(char_of(c)),
Err(_) => Ok(None),
}
}
pub fn reserved_message(cp: u32) -> String {
format!(
"javars: code point U+{cp:X} is reserved: javars stores an unpaired surrogate there, so it cannot hold the character itself"
)
}
fn units_of(c: char) -> (u16, Option<u16>) {
if let Some(u) = unpaired(c) {
return (u, None);
}
let mut buf = [0u16; 2];
let enc = c.encode_utf16(&mut buf);
(enc[0], enc.get(1).copied())
}
fn width(c: char) -> usize {
if c as u32 > 0xFFFF && unpaired(c).is_none() {
2
} else {
1
}
}
pub fn units(s: &str) -> impl Iterator<Item = u16> + '_ {
s.chars().flat_map(|c| {
let (a, b) = units_of(c);
std::iter::once(a).chain(b)
})
}
pub fn has_stand_in(s: &str) -> bool {
let b = s.as_bytes();
b.iter().enumerate().any(|(i, &x)| {
x == 0xF4 && b.get(i + 1) == Some(&0x8F) && b.get(i + 2).is_some_and(|y| *y >= 0xA0)
})
}
pub fn len(s: &str) -> usize {
let b = s.as_bytes();
let n: usize = b
.iter()
.map(|&x| usize::from((x & 0xC0) != 0x80) + usize::from(x >= 0xF0))
.sum();
if b.contains(&0xF4) {
n - s.chars().filter(|c| unpaired(*c).is_some()).count()
} else {
n
}
}
pub fn from_units(units: impl IntoIterator<Item = u16>) -> String {
let mut out = String::new();
for u in units {
push_unit(&mut out, u);
}
out
}
pub fn push_unit(out: &mut String, u: u16) {
if (0xDC00..=0xDFFF).contains(&u) {
if let Some(hi) = out.chars().next_back().and_then(unpaired) {
if (0xD800..=0xDBFF).contains(&hi) {
out.pop();
out.push(char::from_u32(pair(hi, u)).expect("a surrogate pair is a scalar"));
return;
}
}
}
out.push(char_of(u32::from(u)).expect("a UTF-16 unit is storable"));
}
pub fn push_str(out: &mut String, s: &str) {
let mut rest = s;
if let Some(first) = s.chars().next() {
if let Some(lo) = unpaired(first) {
push_unit(out, lo);
rest = &s[first.len_utf8()..];
}
}
out.push_str(rest);
}
pub fn concat(a: &str, b: &str) -> String {
let mut out = String::with_capacity(a.len() + b.len());
out.push_str(a);
push_str(&mut out, b);
out
}
pub fn canon(s: String) -> String {
if !has_stand_in(&s) {
return s;
}
from_units(units(&s))
}
pub fn encoded(s: &str) -> Cow<'_, str> {
if !has_stand_in(s) {
return Cow::Borrowed(s);
}
Cow::Owned(
s.chars()
.map(|c| if unpaired(c).is_some() { '?' } else { c })
.collect(),
)
}
pub fn compare(a: &str, b: &str) -> i64 {
let mut x = units(a);
let mut y = units(b);
loop {
match (x.next(), y.next()) {
(Some(p), Some(q)) if p != q => return i64::from(p) - i64::from(q),
(Some(_), Some(_)) => {}
_ => return len(a) as i64 - len(b) as i64,
}
}
}
pub fn order(a: &str, b: &str) -> std::cmp::Ordering {
let wide = |s: &str| s.as_bytes().iter().any(|&x| x >= 0xEE);
if !wide(a) && !wide(b) {
return a.cmp(b);
}
units(a).cmp(units(b))
}
pub fn hash(s: &str) -> i32 {
units(s).fold(0i32, |h, u| h.wrapping_mul(31).wrapping_add(i32::from(u)))
}
pub fn is_pair(hi: u16, lo: u16) -> bool {
(0xD800..=0xDBFF).contains(&hi) && (0xDC00..=0xDFFF).contains(&lo)
}
pub fn pair(hi: u16, lo: u16) -> u32 {
0x10000 + ((u32::from(hi) - 0xD800) << 10) + (u32::from(lo) - 0xDC00)
}
pub fn code_point_at(units: &[u16], i: usize, limit: usize) -> u32 {
match units.get(i + 1) {
Some(&lo) if i + 1 < limit && is_pair(units[i], lo) => pair(units[i], lo),
_ => u32::from(units[i]),
}
}
pub fn code_point_before(units: &[u16], i: usize, start: usize) -> u32 {
let lo = units[i - 1];
if i >= start + 2 && is_pair(units[i - 2], lo) {
return pair(units[i - 2], lo);
}
u32::from(lo)
}
pub fn code_point_count(units: &[u16]) -> usize {
char::decode_utf16(units.iter().copied()).count()
}
pub fn offset_by_code_points(units: &[u16], index: usize, offset: i64) -> Option<usize> {
let is_hi = |u: u16| (0xD800..=0xDBFF).contains(&u);
let is_lo = |u: u16| (0xDC00..=0xDFFF).contains(&u);
let mut x = index;
if offset >= 0 {
for _ in 0..offset {
if x >= units.len() {
return None;
}
x += 1;
if is_hi(units[x - 1]) && x < units.len() && is_lo(units[x]) {
x += 1;
}
}
} else {
for _ in 0..offset.unsigned_abs() {
if x == 0 {
return None;
}
x -= 1;
if is_lo(units[x]) && x > 0 && is_hi(units[x - 1]) {
x -= 1;
}
}
}
Some(x)
}
pub fn reverse_units(units: &mut [u16]) {
units.reverse();
let mut i = 0;
while i + 1 < units.len() {
if (0xDC00..=0xDFFF).contains(&units[i]) && (0xD800..=0xDBFF).contains(&units[i + 1]) {
units.swap(i, i + 1);
i += 2;
} else {
i += 1;
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum At {
Byte(usize),
Inside(usize),
}
#[derive(Debug)]
pub struct Index {
len: usize,
starts: Vec<u32>,
}
impl Index {
fn build(s: &str) -> Index {
if s.is_ascii() {
return Index {
len: s.len(),
starts: Vec::new(),
};
}
let mut starts = Vec::with_capacity(s.len());
for (b, c) in s.char_indices() {
for _ in 0..width(c) {
starts.push(b as u32);
}
}
Index {
len: starts.len(),
starts,
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn is_ascii(&self) -> bool {
self.starts.is_empty()
}
pub fn at(&self, s: &str, i: usize) -> At {
if self.is_ascii() || i >= self.len {
return At::Byte(if self.is_ascii() {
i.min(s.len())
} else {
s.len()
});
}
let b = self.starts[i] as usize;
if i > 0 && self.starts[i - 1] as usize == b {
At::Inside(b)
} else {
At::Byte(b)
}
}
pub fn unit(&self, s: &str, i: usize) -> u16 {
match self.at(s, i) {
At::Byte(b) if self.is_ascii() => u16::from(s.as_bytes()[b]),
At::Byte(b) => units_of(s[b..].chars().next().expect("in range")).0,
At::Inside(b) => units_of(s[b..].chars().next().expect("in range"))
.1
.expect("astral"),
}
}
pub fn unit_of_byte(&self, s: &str, b: usize) -> usize {
if self.is_ascii() {
return b;
}
if b >= s.len() {
return self.len;
}
self.starts.partition_point(|&x| (x as usize) < b)
}
pub fn slice(&self, s: &str, b: usize, e: usize) -> String {
if b >= e {
return String::new();
}
let (bb, head) = match self.at(s, b) {
At::Byte(x) => (x, None),
At::Inside(x) => {
let c = s[x..].chars().next().expect("in range");
(x + c.len_utf8(), units_of(c).1)
}
};
let (eb, tail) = match self.at(s, e) {
At::Byte(x) => (x, None),
At::Inside(x) => (
x,
Some(units_of(s[x..].chars().next().expect("in range")).0),
),
};
if bb > eb {
return stand_in(head.or(tail).expect("a split pair")).to_string();
}
let mut out = String::with_capacity(eb - bb + 8);
if let Some(h) = head {
out.push(stand_in(h));
}
out.push_str(&s[bb..eb]);
if let Some(t) = tail {
out.push(stand_in(t));
}
out
}
}
pub fn index_of(s: &str, ix: &Index, needle: &str, from: i64) -> i64 {
let from = from.clamp(0, ix.len() as i64) as usize;
if needle.is_empty() {
return from as i64;
}
if has_stand_in(needle) {
let (h, n): (Vec<u16>, Vec<u16>) = (units(s).collect(), units(needle).collect());
return (from..h.len())
.find(|&i| h[i..].starts_with(&n))
.map_or(-1, |i| i as i64);
}
let start = match ix.at(s, from) {
At::Byte(b) => b,
At::Inside(b) => b + s[b..].chars().next().map_or(0, char::len_utf8),
};
s[start..]
.find(needle)
.map_or(-1, |p| ix.unit_of_byte(s, start + p) as i64)
}
pub fn last_index_of(s: &str, ix: &Index, needle: &str, from: i64) -> i64 {
let n_len = len(needle);
let start = from.min(ix.len() as i64 - n_len as i64);
if start < 0 {
return -1;
}
if needle.is_empty() {
return start;
}
let start = start as usize;
if ix.is_ascii() && needle.is_ascii() {
return s[..start + n_len].rfind(needle).map_or(-1, |p| p as i64);
}
let (h, n): (Vec<u16>, Vec<u16>) = (units(s).collect(), units(needle).collect());
(0..=start)
.rev()
.find(|&i| h[i..].starts_with(&n))
.map_or(-1, |i| i as i64)
}
const CACHE_MIN_BYTES: usize = 64;
const CACHE_SLOTS: usize = 4;
thread_local! {
static CACHE: RefCell<Vec<(Arc<String>, Rc<Index>)>> = const { RefCell::new(Vec::new()) };
static ADOPTED: RefCell<Option<Arc<String>>> = const { RefCell::new(None) };
}
pub fn adopt(owner: &Arc<String>) {
if owner.len() >= CACHE_MIN_BYTES {
ADOPTED.with(|a| *a.borrow_mut() = Some(Arc::clone(owner)));
}
}
pub fn index(s: &str) -> Rc<Index> {
if s.len() < CACHE_MIN_BYTES {
return Rc::new(Index::build(s));
}
let key = (s.as_ptr(), s.len());
let hit = CACHE.with(|c| {
let mut c = c.borrow_mut();
let pos = c.iter().position(|(a, _)| (a.as_ptr(), a.len()) == key)?;
let entry = c.remove(pos);
let idx = Rc::clone(&entry.1);
c.insert(0, entry);
Some(idx)
});
if let Some(idx) = hit {
return idx;
}
let idx = Rc::new(Index::build(s));
let owner = ADOPTED.with(|a| {
a.borrow()
.as_ref()
.filter(|o| (o.as_ptr(), o.len()) == key)
.cloned()
});
if let Some(owner) = owner {
CACHE.with(|c| {
let mut c = c.borrow_mut();
c.insert(0, (owner, Rc::clone(&idx)));
c.truncate(CACHE_SLOTS);
});
}
idx
}
#[cfg(test)]
mod tests {
use super::*;
fn grin() -> String {
char::from_u32(0x1F600).unwrap().to_string()
}
#[test]
fn length_counts_units() {
let s = format!("a{}b", grin());
assert_eq!(len(&s), 4);
assert_eq!(index(&s).len(), 4);
let hi = from_units([0xD83D]);
assert_eq!(len(&hi), 1);
}
#[test]
fn halves_rejoin_into_the_character() {
let hi = from_units([0xD83D]);
let lo = from_units([0xDE00]);
assert_eq!(concat(&hi, &lo), grin());
assert_eq!(canon(format!("{hi}{lo}")), grin());
assert_eq!(concat(&lo, &hi).chars().count(), 2);
}
#[test]
fn slicing_a_pair_keeps_each_half() {
let s = format!("x{}y", grin());
let ix = index(&s);
assert_eq!(units(&ix.slice(&s, 1, 2)).collect::<Vec<_>>(), [0xD83D]);
assert_eq!(
units(&ix.slice(&s, 2, 4)).collect::<Vec<_>>(),
[0xDE00, b'y' as u16]
);
assert_eq!(ix.slice(&s, 1, 3), grin());
assert_eq!(ix.unit(&s, 2), 0xDE00);
}
#[test]
fn order_is_utf16_order() {
let a = grin();
let b = "\u{FFFD}".to_string();
assert_eq!(order(&a, &b), std::cmp::Ordering::Less);
assert!(compare(&a, &b) < 0);
}
#[test]
fn output_replaces_unpaired_halves() {
let s = format!("a{}b", from_units([0xDE00]));
assert_eq!(encoded(&s), "a?b");
}
}