use crate::charset::builtin::{self, EmojiSequence, SequenceKind};
use std::cmp::Reverse;
use std::collections::{BTreeMap, BTreeSet};
use std::sync::LazyLock;
const ZWJ: char = '\u{200D}';
const TAGS: std::ops::RangeInclusive<char> = '\u{E0000}'..='\u{E007F}';
const VS16: char = '\u{FE0F}';
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub(super) struct Sequences {
by_first: BTreeMap<char, Vec<String>>,
widest: usize,
deferred: bool,
}
static BUILTIN: LazyLock<Sequences> = LazyLock::new(Sequences::builtin);
impl Sequences {
pub(super) fn deferred() -> Self {
Self {
deferred: true,
..Self::default()
}
}
pub(super) fn builtin() -> Self {
let by_first = listed();
let widest = by_first.values().flatten().map(String::len).max();
Self {
by_first,
widest: widest.unwrap_or(0),
deferred: false,
}
}
pub(super) fn exempt(&self, text: &str) -> Vec<usize> {
if self.deferred {
let wanted = next_joined(text, 0).is_some();
return if wanted {
BUILTIN.exempt(text)
} else {
Vec::new()
};
}
self.walk(text)
}
fn walk(&self, text: &str) -> Vec<usize> {
let mut found = Vec::new();
let mut at = 0_usize;
while let Some(next) = next_joined(text, at) {
at = at.max(self.window(text, next));
while at <= next {
let rest = text.get(at..).unwrap_or_default();
at = at.saturating_add(self.step(rest, at, &mut found));
}
}
found
}
fn window(&self, text: &str, next: usize) -> usize {
let reach = self.widest.saturating_sub(1);
text.ceil_char_boundary(next.saturating_sub(reach))
}
fn step(&self, rest: &str, at: usize, found: &mut Vec<usize>) -> usize {
if let Some(held) = self.longest(rest) {
found.extend(inner(held).map(|i| at.saturating_add(i)));
return held.len();
}
rest.chars().next().map_or(1, char::len_utf8)
}
fn longest(&self, rest: &str) -> Option<&str> {
let first = rest.chars().next()?;
let held = self.by_first.get(&first)?;
held.iter()
.map(String::as_str)
.find(|s| rest.starts_with(s))
}
}
const VS15: char = '\u{FE0E}';
static VARYING: LazyLock<BTreeSet<char>> = LazyLock::new(|| {
let presentation = builtin::emoji_sequences()
.filter(|s| s.kind == SequenceKind::Presentation);
presentation.filter_map(|s| s.text.chars().next()).collect()
});
pub(super) fn selectors(
text: &str,
granted: impl Fn(char) -> bool,
) -> Vec<usize> {
let mut found = Vec::new();
let mut before: Option<char> = None;
for (at, c) in text.char_indices() {
let base = before.filter(|b| granted(*b) && VARYING.contains(b));
if (c == VS16 || c == VS15) && base.is_some() {
found.push(at);
}
before = Some(c);
}
found
}
fn listed() -> BTreeMap<char, Vec<String>> {
let mut by_first: BTreeMap<char, Vec<String>> = BTreeMap::new();
for text in builtin::emoji_sequences().filter_map(exempting) {
if let Some(first) = text.chars().next() {
by_first.entry(first).or_default().push(text);
}
}
for held in by_first.values_mut() {
held.sort_by_key(|text| Reverse(text.len()));
}
by_first
}
fn joined(c: char) -> bool {
c == ZWJ || c == VS16 || TAGS.contains(&c)
}
fn next_joined(text: &str, at: usize) -> Option<usize> {
let rest = text.get(at..)?;
let (offset, _) = rest.char_indices().find(|(_, c)| joined(*c))?;
at.checked_add(offset)
}
fn inner(held: &str) -> impl Iterator<Item = usize> + '_ {
held.char_indices()
.filter(|(_, c)| joined(*c))
.map(|(i, _)| i)
}
fn exempting(sequence: EmojiSequence) -> Option<String> {
use SequenceKind::{Keycap, Presentation, Tag, Zwj};
let holds = matches!(sequence.kind, Zwj | Tag | Keycap | Presentation);
holds.then_some(sequence.text)
}
#[cfg(test)]
mod tests {
use super::Sequences;
const FAMILY: &str = "\u{1F468}\u{200D}\u{1F469}\u{200D}\u{1F467}";
const ENGLAND: &str =
"\u{1F3F4}\u{E0067}\u{E0062}\u{E0065}\u{E006E}\u{E0067}\u{E007F}";
fn exempt(text: &str) -> Vec<usize> {
Sequences::builtin().exempt(text)
}
#[test]
fn every_listed_sequence_is_read() {
let held = Sequences::builtin();
let count: usize = held.by_first.values().map(Vec::len).sum();
assert_eq!(count, 1836);
}
#[test]
fn the_joiners_of_a_listed_sequence_are_exempt() {
assert_eq!(exempt(&format!("a{FAMILY}")), vec![5, 12]);
}
#[test]
fn vs16_in_a_listed_presentation_is_exempt_and_elsewhere_is_not() {
assert_eq!(exempt("\u{2764}\u{FE0F}"), vec![3]);
assert_eq!(exempt("1\u{FE0F}\u{20E3}"), vec![1]);
assert!(exempt("\u{1F600}\u{FE0F}").is_empty());
}
#[test]
fn the_tags_of_a_listed_flag_are_exempt() {
let found = exempt(ENGLAND);
assert_eq!(found.len(), 6);
assert_eq!(found.first(), Some(&4));
}
#[test]
fn a_joiner_in_no_listed_sequence_is_not_exempt() {
assert!(exempt("\u{1F600}\u{200D}\u{1F600}").is_empty());
assert!(exempt("a\u{200D}b").is_empty());
}
#[test]
fn tags_smuggled_after_a_black_flag_are_not_exempt() {
let smuggled: String = std::iter::once('\u{1F3F4}')
.chain("ignore".chars().filter_map(tag))
.chain(std::iter::once('\u{E007F}'))
.collect();
assert!(exempt(&smuggled).is_empty());
}
#[test]
fn a_payload_after_a_listed_flag_is_not_exempt() {
let payload: String = "rm".chars().filter_map(tag).collect();
let found = exempt(&format!("{ENGLAND}{payload}"));
assert_eq!(found.len(), 6);
}
fn tag(c: char) -> Option<char> {
char::from_u32(u32::from(c).checked_add(0xE0000)?)
}
}
#[cfg(test)]
mod windowed {
use super::{Sequences, joined};
fn everywhere(held: &Sequences, text: &str) -> Vec<usize> {
let mut found = Vec::new();
if !text.contains(joined) {
return found;
}
let mut at = 0_usize;
while let Some(rest) = text.get(at..).filter(|r| !r.is_empty()) {
at = at.saturating_add(held.step(rest, at, &mut found));
}
found
}
const PIECES: [&str; 20] = [
"a",
"\u{e9}",
"\u{4E2D}",
"\u{1F468}",
"\u{1F469}",
"\u{1F467}",
"\u{200D}",
"\u{FE0F}",
"\u{2764}",
"\u{1F3F4}",
"\u{E0067}",
"\u{E0062}",
"\u{E0065}",
"\u{E006E}",
"\u{E007F}",
"1",
"\u{20E3}",
"\u{1F3FB}",
"\u{1F600}",
"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx",
];
struct Draw(u64);
impl Draw {
fn below(&mut self, n: usize) -> usize {
self.0 = self
.0
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1_442_695_040_888_963_407);
let high = usize::try_from(self.0 >> 33).unwrap_or(0);
high.checked_rem(n).unwrap_or(0)
}
}
fn text(draw: &mut Draw, listed: &[&str]) -> String {
let mut text = String::new();
for _ in 0..draw.below(24) {
let piece = match draw.below(4) {
0 => listed.get(draw.below(listed.len())),
_ => PIECES.get(draw.below(PIECES.len())),
};
text.push_str(piece.copied().unwrap_or_default());
}
text
}
fn same(held: &Sequences, text: &str) {
let found = held.exempt(text);
assert_eq!(found, everywhere(held, text), "{text:?}");
assert_eq!(found, Sequences::deferred().exempt(text), "{text:?}");
}
#[test]
fn the_window_finds_what_trying_everywhere_finds() {
let held = Sequences::builtin();
let listed: Vec<&str> = held
.by_first
.values()
.flatten()
.map(String::as_str)
.collect();
let mut draw = Draw(0x2545_F491_4F6C_DD1D);
for _ in 0..4000 {
same(&held, &text(&mut draw, &listed));
}
}
#[test]
fn every_listed_sequence_is_found_behind_padding_and_cut_short() {
let held = Sequences::builtin();
let pad = "y".repeat(held.widest.saturating_add(3));
for listed in held.by_first.values().flatten() {
let mut cut = listed.clone();
cut.pop();
same(&held, &format!("{pad}{listed}"));
same(&held, &format!("{pad}{cut}"));
same(&held, &listed.repeat(2));
}
}
#[test]
fn every_listed_sequence_holds_a_joinable_character() {
let held = Sequences::builtin();
let bare = held
.by_first
.values()
.flatten()
.find(|s| !s.contains(joined));
assert_eq!(bare, None);
}
}