#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
#![allow(unsafe_code)]
use std::borrow::Borrow;
use std::collections::hash_map::Entry;
use std::hash::{Hash, Hasher};
use std::sync::{Arc, OnceLock};
use crate::fasthash::Map;
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
use crate::lr::LrBackend;
use crate::memo::skew_cached;
use crate::partition::Partition;
#[derive(Clone, Copy, Debug, Default)]
pub struct SkewLr;
pub fn expand_skew(outer: &Partition, inner: &Partition) -> Vec<(Partition, u128)> {
(*expand_skew_shared(outer, inner)).clone()
}
pub fn expand_skew_shared(outer: &Partition, inner: &Partition) -> Arc<Vec<(Partition, u128)>> {
if !outer.contains(inner) {
return Arc::new(Vec::new());
}
skew_cached(outer, inner, || expand_skew_uncached(outer, inner))
}
trait LayerKey: Sized + Eq + Hash + Send + Sync + 'static {
type Scratch: Default + Send;
fn fits(outer: &Partition, inner: &Partition) -> bool;
fn root(elem_width: usize) -> Self;
fn decode(
&self,
elem_width: usize,
above_len: usize,
content: &mut Vec<u32>,
above: &mut Vec<u32>,
);
fn commit<C: Acc>(ctx: &mut RowCtx<'_, C, Self>);
}
trait Word: Copy + Eq + Hash + Send + Sync + 'static {
const BITS: usize;
const ZERO: Self;
fn set(self, pos: u32) -> Self;
fn is_zero(self) -> bool;
fn count_ones(self) -> u32;
fn trailing_zeros(self) -> u32;
fn clear_lowest(self) -> Self;
fn fold(self) -> u64;
}
impl Word for u64 {
const BITS: usize = 64;
const ZERO: Self = 0;
#[inline]
fn set(self, pos: u32) -> Self {
self | (1u64 << pos)
}
#[inline]
fn is_zero(self) -> bool {
self == 0
}
#[inline]
fn count_ones(self) -> u32 {
u64::count_ones(self)
}
#[inline]
fn trailing_zeros(self) -> u32 {
u64::trailing_zeros(self)
}
#[inline]
fn clear_lowest(self) -> Self {
self & self.wrapping_sub(1)
}
#[inline]
fn fold(self) -> u64 {
self
}
}
#[derive(Clone, Copy, PartialEq, Eq)]
struct W128([u64; 2]);
impl Hash for W128 {
#[inline]
fn hash<H: Hasher>(&self, state: &mut H) {
state.write_u64(self.0[0]);
state.write_u64(self.0[1]);
}
}
impl Word for W128 {
const BITS: usize = 128;
const ZERO: Self = W128([0, 0]);
#[inline]
fn set(self, pos: u32) -> Self {
let W128([lo, hi]) = self;
if pos < 64 {
W128([lo | (1u64 << pos), hi])
} else {
W128([lo, hi | (1u64 << (pos - 64))])
}
}
#[inline]
fn is_zero(self) -> bool {
self.0 == [0, 0]
}
#[inline]
fn count_ones(self) -> u32 {
self.0[0].count_ones() + self.0[1].count_ones()
}
#[inline]
fn trailing_zeros(self) -> u32 {
if self.0[0] != 0 {
self.0[0].trailing_zeros()
} else {
64 + self.0[1].trailing_zeros()
}
}
#[inline]
fn clear_lowest(self) -> Self {
let W128([lo, hi]) = self;
if lo != 0 {
W128([lo & lo.wrapping_sub(1), hi])
} else {
W128([lo, hi & hi.wrapping_sub(1)])
}
}
#[inline]
fn fold(self) -> u64 {
self.0[0] ^ self.0[1].rotate_left(32)
}
}
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
struct PackedKey<W: Word> {
content: W,
above: W,
}
fn packed_bits(outer: &Partition, _inner: &Partition) -> usize {
outer.len() + outer.part(0) as usize
}
#[inline]
fn unpack_partition<W: Word>(mut w: W, out: &mut Vec<u32>) {
let k = w.count_ones() as usize;
out.clear();
out.resize(k, 0);
let mut j = 0u32;
while !w.is_zero() {
out[k - 1 - j as usize] = w.trailing_zeros() - j;
w = w.clear_lowest();
j += 1;
}
}
#[inline]
fn unpack_row<W: Word>(mut w: W, out: &mut Vec<u32>) {
out.clear();
let mut j = 0u32;
while !w.is_zero() {
out.push(w.trailing_zeros() - j);
w = w.clear_lowest();
j += 1;
}
}
impl<W: Word> LayerKey for PackedKey<W> {
type Scratch = ();
fn fits(outer: &Partition, inner: &Partition) -> bool {
packed_bits(outer, inner) <= W::BITS
}
fn root(_elem_width: usize) -> Self {
PackedKey {
content: W::ZERO,
above: W::ZERO,
}
}
#[inline]
fn decode(
&self,
_elem_width: usize,
above_len: usize,
content: &mut Vec<u32>,
above: &mut Vec<u32>,
) {
unpack_partition(self.content, content);
unpack_row(self.above, above);
debug_assert_eq!(above.len(), above_len);
}
#[inline]
fn commit<C: Acc>(ctx: &mut RowCtx<'_, C, Self>) {
let clen = ctx.content.len();
let new = ctx.added[clen];
let k = clen + usize::from(new > 0);
let mut content = W::ZERO;
for (i, (&c, &a)) in ctx.content.iter().zip(ctx.added.iter()).enumerate() {
content = content.set(c + a + (k - 1 - i) as u32);
}
if new > 0 {
content = content.set(new);
}
let mut above = W::ZERO;
for j in 0..ctx.dn_hi - ctx.dn_lo {
above = above.set(ctx.row[ctx.dn_lo - ctx.lo + j] + j as u32);
}
let key = PackedKey { content, above };
let mixed =
(content.fold() ^ above.fold().rotate_left(29)).wrapping_mul(0x9e37_79b9_7f4a_7c15);
let shard = &mut ctx.out[((mixed >> 32) as usize) % ctx.out.len()];
match shard.entry(key) {
Entry::Occupied(mut e) => match e.get().checked_add(ctx.mult) {
Some(sum) => *e.get_mut() = sum,
None => *ctx.overflow = true,
},
Entry::Vacant(e) => {
e.insert(ctx.mult);
}
}
}
}
enum Key {
Inline(u8, [u8; INLINE]),
Heap(Box<[u8]>),
}
const INLINE: usize = 30;
const _: () = assert!(std::mem::size_of::<Key>() == 32);
const _: () = assert!(std::mem::size_of::<PackedKey<u64>>() == 16);
const _: () = assert!(std::mem::size_of::<PackedKey<W128>>() == 32);
const _: () = assert!(std::mem::align_of::<PackedKey<W128>>() == std::mem::align_of::<u64>());
#[derive(Default)]
struct ByteScratch {
key: Vec<u32>,
kbuf: Vec<u8>,
}
impl LayerKey for Key {
type Scratch = ByteScratch;
fn fits(_outer: &Partition, _inner: &Partition) -> bool {
true
}
fn root(elem_width: usize) -> Self {
Key::from_bytes(&vec![0u8; elem_width])
}
#[inline]
fn decode(
&self,
elem_width: usize,
above_len: usize,
content: &mut Vec<u32>,
above: &mut Vec<u32>,
) {
let bytes = self.bytes();
decode_into(content, &bytes[..elem_width], elem_width);
let split = elem_width * (1 + content[0] as usize);
decode_into(content, &bytes[elem_width..split], elem_width);
decode_into(above, &bytes[split..], elem_width);
debug_assert_eq!(above.len(), above_len);
}
#[inline]
fn commit<C: Acc>(ctx: &mut RowCtx<'_, C, Self>) {
let ByteScratch { key, kbuf } = &mut *ctx.scratch;
key.clear();
key.push(0); key.extend(
ctx.content
.iter()
.zip(ctx.added.iter())
.map(|(&c, &a)| c + a),
);
if let Some(&n) = ctx.added.get(ctx.content.len()) {
if n > 0 {
key.push(n);
}
}
key[0] = (key.len() - 1) as u32;
if ctx.dn_lo < ctx.dn_hi {
key.extend_from_slice(&ctx.row[ctx.dn_lo - ctx.lo..ctx.dn_hi - ctx.lo]);
}
encode_into(kbuf, key, ctx.width);
let shard = &mut ctx.out[shard_of(kbuf, ctx.out.len())];
match shard.get_mut(KeyBytes::new(kbuf)) {
Some(w) => match w.checked_add(ctx.mult) {
Some(sum) => *w = sum,
None => *ctx.overflow = true,
},
None => {
shard.insert(Key::from_bytes(kbuf), ctx.mult);
}
}
}
}
impl Key {
#[inline]
fn from_bytes(b: &[u8]) -> Key {
if b.len() <= INLINE {
let mut buf = [0u8; INLINE];
buf[..b.len()].copy_from_slice(b);
Key::Inline(b.len() as u8, buf)
} else {
Key::Heap(b.into())
}
}
#[inline]
fn bytes(&self) -> &[u8] {
match self {
Key::Inline(len, buf) => &buf[..*len as usize],
Key::Heap(b) => b,
}
}
}
impl PartialEq for Key {
#[inline]
fn eq(&self, other: &Key) -> bool {
self.bytes() == other.bytes()
}
}
impl Eq for Key {}
impl Hash for Key {
#[inline]
fn hash<H: Hasher>(&self, state: &mut H) {
state.write(self.bytes());
}
}
#[derive(PartialEq, Eq)]
#[repr(transparent)]
struct KeyBytes([u8]);
impl KeyBytes {
#[inline]
fn new(s: &[u8]) -> &KeyBytes {
unsafe { &*(s as *const [u8] as *const KeyBytes) }
}
}
impl Borrow<KeyBytes> for Key {
#[inline]
fn borrow(&self) -> &KeyBytes {
KeyBytes::new(self.bytes())
}
}
impl Hash for KeyBytes {
#[inline]
fn hash<H: Hasher>(&self, state: &mut H) {
state.write(&self.0);
}
}
static PEAK_LIVE_STATES: AtomicUsize = AtomicUsize::new(0);
pub fn take_peak_layer_states() -> usize {
PEAK_LIVE_STATES.swap(0, Ordering::Relaxed)
}
static PRODUCTIONS: AtomicU64 = AtomicU64::new(0);
pub fn take_productions() -> u64 {
PRODUCTIONS.swap(0, Ordering::Relaxed)
}
fn elem_width(outer: &Partition, inner: &Partition) -> usize {
let n = outer.size() - inner.size();
if n <= 0xFF {
1
} else if n <= 0xFFFF {
2
} else {
4
}
}
#[inline]
fn encode_into(dst: &mut Vec<u8>, src: &[u32], w: usize) {
dst.clear();
match w {
1 => {
debug_assert!(src.iter().all(|&x| x <= 0xFF));
dst.extend(src.iter().map(|&x| x as u8));
}
2 => {
debug_assert!(src.iter().all(|&x| x <= 0xFFFF));
for &x in src {
dst.extend_from_slice(&(x as u16).to_le_bytes());
}
}
_ => {
for &x in src {
dst.extend_from_slice(&x.to_le_bytes());
}
}
}
}
#[inline]
fn decode_into(dst: &mut Vec<u32>, src: &[u8], w: usize) {
dst.clear();
match w {
1 => dst.extend(src.iter().map(|&b| b as u32)),
2 => dst.extend(
src.chunks_exact(2)
.map(|c| u16::from_le_bytes([c[0], c[1]]) as u32),
),
_ => dst.extend(
src.chunks_exact(4)
.map(|c| u32::from_le_bytes([c[0], c[1], c[2], c[3]])),
),
}
}
trait Acc: Copy + Send + Sync {
const ONE: Self;
fn checked_add(self, other: Self) -> Option<Self>;
fn widen(self) -> u128;
}
impl Acc for u64 {
const ONE: Self = 1;
#[inline]
fn checked_add(self, other: Self) -> Option<Self> {
u64::checked_add(self, other)
}
#[inline]
fn widen(self) -> u128 {
self as u128
}
}
impl Acc for u128 {
const ONE: Self = 1;
#[inline]
fn checked_add(self, other: Self) -> Option<Self> {
u128::checked_add(self, other)
}
#[inline]
fn widen(self) -> u128 {
self
}
}
fn expand_skew_uncached(outer: &Partition, inner: &Partition) -> Vec<(Partition, u128)> {
expand_walk(outer, inner, prefer_conjugate(outer, inner))
}
fn expand_walk(outer: &Partition, inner: &Partition, conjugate: bool) -> Vec<(Partition, u128)> {
let (co, ci);
let (o, i) = if conjugate {
co = outer.conjugate();
ci = inner.conjugate();
(&co, &ci)
} else {
(outer, inner)
};
let mut out = expand_oriented::<u64>(o, i, conjugate)
.or_else(|| expand_oriented::<u128>(o, i, conjugate))
.expect("LR tableau multiplicity exceeded u128");
out.sort_by(|a, b| a.0.cmp(&b.0));
out
}
fn prefer_conjugate(outer: &Partition, inner: &Partition) -> bool {
match std::env::var_os("SKEW_ORIENT") {
Some(v) if v == "conj" => return true,
Some(v) if v == "direct" => return false,
_ => {}
}
let rows = outer.len();
let width = outer.part(0) as usize;
let cells = outer.size() - inner.size();
let gentle = outer.parts().windows(2).all(|w| w[0] - w[1] <= 1);
let band = outer.len().saturating_sub(inner.len()) <= 4;
rows >= 8 && width > rows && cells >= 60 && (gentle || band)
}
fn expand_oriented<C: Acc>(
outer: &Partition,
inner: &Partition,
conjugate_terms: bool,
) -> Option<Vec<(Partition, u128)>> {
let width = elem_width(outer, inner);
if PackedKey::<u64>::fits(outer, inner) {
expand_layer::<C, PackedKey<u64>>(outer, inner, width, conjugate_terms)
} else if PackedKey::<W128>::fits(outer, inner) {
expand_layer::<C, PackedKey<W128>>(outer, inner, width, conjugate_terms)
} else {
expand_layer::<C, Key>(outer, inner, width, conjugate_terms)
}
}
fn skew_trace() -> bool {
static TRACE: OnceLock<bool> = OnceLock::new();
*TRACE.get_or_init(|| std::env::var_os("SKEW_TRACE").is_some())
}
fn expand_layer<C: Acc, K: LayerKey>(
outer: &Partition,
inner: &Partition,
width: usize,
conjugate_terms: bool,
) -> Option<Vec<(Partition, u128)>> {
debug_assert!(
K::fits(outer, inner),
"layer key too narrow for {outer}/{inner}"
);
let rows = outer.len();
let trace = skew_trace();
let mut cur: Vec<(K, C)> = vec![(K::root(width), C::ONE)];
let mut content: Vec<u32> = Vec::new();
let mut above: Vec<u32> = Vec::new();
let mut overflow = false;
for r in 0..rows {
crate::interrupt::poll();
let lo = inner.part(r) as usize;
let hi = outer.part(r) as usize;
let (up_lo, up_hi) = overlap(inner, outer, r.wrapping_sub(1), r);
let (dn_lo, dn_hi) = overlap(inner, outer, r, r + 1);
let geom = RowGeom {
lo,
hi,
up_lo,
up_hi,
dn_lo,
dn_hi,
width,
};
let next: Vec<(K, C)> = fill_row(&cur, &geom, &mut overflow);
PEAK_LIVE_STATES.fetch_max(cur.len() + next.len(), Ordering::Relaxed);
if trace {
eprintln!("skew_lr row {r}: {} -> {} states", cur.len(), next.len());
}
if overflow {
return None;
}
cur = next;
if cur.is_empty() {
break;
}
}
Some(
cur.into_iter()
.map(|(key, c)| {
key.decode(width, 0, &mut content, &mut above);
debug_assert!(above.is_empty());
let parts = if conjugate_terms {
crate::partition::conjugate_parts(&content)
} else {
content.clone()
};
(Partition::from_sorted(parts), c.widen())
})
.collect(),
)
}
fn overlap(inner: &Partition, outer: &Partition, a: usize, b: usize) -> (usize, usize) {
if a >= outer.len() || b >= outer.len() {
return (0, 0);
}
let lo = (inner.part(a) as usize).max(inner.part(b) as usize);
let hi = (outer.part(a) as usize).min(outer.part(b) as usize);
if lo >= hi {
(0, 0)
} else {
(lo, hi)
}
}
#[derive(Clone, Copy)]
struct RowGeom {
lo: usize,
hi: usize,
up_lo: usize,
up_hi: usize,
dn_lo: usize,
dn_hi: usize,
width: usize,
}
const PARALLEL_MIN_STATES: usize = 24_576;
#[inline]
fn shard_of(bytes: &[u8], shards: usize) -> usize {
let n = bytes.len();
let mut w = n as u64;
for &b in bytes.iter().rev().take(8) {
w = (w << 8) | b as u64;
}
w = w.wrapping_mul(0x9e37_79b9_7f4a_7c15);
((w >> 32) as usize) % shards
}
fn fill_row<C: Acc, K: LayerKey>(
cur: &[(K, C)],
geom: &RowGeom,
overflow: &mut bool,
) -> Vec<(K, C)> {
const CHUNK: usize = 2_048;
let threads = worker_count(cur.len());
if threads <= 1 {
let mut out = vec![Map::with_capacity_and_hasher(cur.len(), Default::default())];
for lo in (0..cur.len()).step_by(CHUNK) {
crate::interrupt::poll();
fill_chunk(
&cur[lo..(lo + CHUNK).min(cur.len())],
geom,
&mut out,
overflow,
);
}
return out.into_iter().flatten().collect();
}
let shards = threads;
let nchunks = cur.len().div_ceil(CHUNK);
let cursor = AtomicUsize::new(0);
let parts: Vec<(Vec<Map<K, C>>, bool)> = std::thread::scope(|s| {
let handles: Vec<_> = (0..threads)
.map(|_| {
let cursor = &cursor;
s.spawn(move || {
let cap = cur.len() / (threads * shards) + 1;
let mut out: Vec<Map<K, C>> = (0..shards)
.map(|_| Map::with_capacity_and_hasher(cap, Default::default()))
.collect();
let mut of = false;
loop {
let i = cursor.fetch_add(1, Ordering::Relaxed);
if i >= nchunks {
break;
}
let lo = i * CHUNK;
let hi = (lo + CHUNK).min(cur.len());
fill_chunk(&cur[lo..hi], geom, &mut out, &mut of);
}
(out, of)
})
})
.collect();
handles
.into_iter()
.map(|h| {
h.join()
.expect("an LR fill worker panicked; its panic is the bug")
})
.collect()
});
let pre: usize = parts
.iter()
.map(|(ms, _)| ms.iter().map(|m| m.len()).sum::<usize>())
.sum();
PEAK_LIVE_STATES.fetch_max(cur.len() + pre, Ordering::Relaxed);
let mut columns: Vec<Vec<Map<K, C>>> =
(0..shards).map(|_| Vec::with_capacity(threads)).collect();
for (maps, of) in parts {
if of {
*overflow = true;
}
for (j, m) in maps.into_iter().enumerate() {
columns[j].push(m);
}
}
let merged: Vec<(Vec<(K, C)>, bool)> = std::thread::scope(|s| {
let handles: Vec<_> = columns
.into_iter()
.map(|mut group| {
s.spawn(move || {
let mut of = false;
let best = group
.iter()
.enumerate()
.max_by_key(|(_, m)| m.len())
.map(|(i, _)| i)
.unwrap_or(0);
let mut acc = group.swap_remove(best);
for m in group {
for (k, v) in m {
match acc.entry(k) {
Entry::Occupied(mut e) => match e.get().checked_add(v) {
Some(sum) => *e.get_mut() = sum,
None => of = true,
},
Entry::Vacant(e) => {
e.insert(v);
}
}
}
}
(acc.into_iter().collect::<Vec<_>>(), of)
})
})
.collect();
handles
.into_iter()
.map(|h| {
h.join()
.expect("an LR fill worker panicked; its panic is the bug")
})
.collect()
});
let mut out = Vec::with_capacity(merged.iter().map(|(v, _)| v.len()).sum());
for (v, of) in merged {
if of {
*overflow = true;
}
out.extend(v);
}
out
}
fn worker_count(states: usize) -> usize {
if states < PARALLEL_MIN_STATES {
return 1;
}
let avail = std::thread::available_parallelism()
.map(|n| n.get())
.unwrap_or(1);
avail.min(states / (PARALLEL_MIN_STATES / 2)).max(1)
}
fn fill_chunk<C: Acc, K: LayerKey>(
chunk: &[(K, C)],
geom: &RowGeom,
out: &mut [Map<K, C>],
overflow: &mut bool,
) {
let RowGeom {
lo,
hi,
up_lo,
up_hi,
dn_lo,
dn_hi,
width,
} = *geom;
let mut row: Vec<u32> = vec![0; hi.saturating_sub(lo)];
let mut added: Vec<u32> = Vec::new();
let mut cut: Vec<usize> = Vec::new();
let mut gap: Vec<u32> = Vec::new();
let mut scratch = K::Scratch::default();
let mut content: Vec<u32> = Vec::new();
let mut above: Vec<u32> = Vec::new();
let mut produced: u64 = 0;
for (state, mult) in chunk.iter() {
state.decode(width, up_hi - up_lo, &mut content, &mut above);
let clen = content.len();
let top = clen as u32 + 1;
cut.clear();
cut.push(0); let mut j = 0;
for v in 1..=top {
while j < above.len() && above[j] < v {
j += 1;
}
cut.push(if j < above.len() { up_lo + j } else { hi });
}
gap.clear();
gap.extend_from_slice(&[0, 0]); for v in 2..=top {
let vi = v as usize - 1;
gap.push(content[vi - 1] - content.get(vi).copied().unwrap_or(0));
}
added.clear();
added.resize(clen + 1, 0);
let mut ctx = RowCtx {
lo,
hi,
up_hi,
dn_lo,
dn_hi,
top,
content: &content,
cut: &cut,
gap: &gap,
added: &mut added,
row: &mut row,
scratch: &mut scratch,
width,
mult: *mult,
out,
overflow,
produced: &mut produced,
};
fill_runs(lo, 1, &mut ctx);
}
PRODUCTIONS.fetch_add(produced, Ordering::Relaxed);
}
struct RowCtx<'a, C, K: LayerKey> {
lo: usize,
hi: usize,
up_hi: usize,
dn_lo: usize,
dn_hi: usize,
top: u32,
content: &'a [u32],
cut: &'a [usize],
gap: &'a [u32],
added: &'a mut [u32],
row: &'a mut [u32],
scratch: &'a mut K::Scratch,
width: usize,
mult: C,
out: &'a mut [Map<K, C>],
overflow: &'a mut bool,
produced: &'a mut u64,
}
fn fill_runs<C: Acc, K: LayerKey>(a: usize, vmin: u32, ctx: &mut RowCtx<C, K>) {
if a == ctx.hi {
*ctx.produced += 1;
K::commit(ctx);
return;
}
for v in vmin..=ctx.top {
let emax = if a >= ctx.up_hi {
ctx.hi
} else {
ctx.cut[v as usize]
};
if emax <= a {
continue;
}
let mut cap = emax - a;
if v >= 2 {
let g = ctx.gap[v as usize] as usize;
if g == 0 {
continue;
}
cap = cap.min(g);
}
let vi = (v - 1) as usize;
for n in 1..=cap {
ctx.row[a - ctx.lo + n - 1] = v;
ctx.added[vi] = n as u32;
fill_runs(a + n, v + 1, ctx);
}
ctx.added[vi] = 0;
}
}
impl LrBackend for SkewLr {
fn lr_coeff(&self, lambda: &Partition, mu: &Partition, nu: &Partition) -> u128 {
if lambda.size() != mu.size() + nu.size() || !lambda.contains(mu) {
return 0;
}
let (outer, inner, _) = product_walk(mu, nu);
if let Some(product) = crate::memo::skew_cache_peek(&outer, &inner) {
return product
.binary_search_by(|(p, _)| p.cmp(lambda))
.map(|i| product[i].1)
.unwrap_or(0);
}
let (inner, want) = if mu.size() >= nu.size() {
(mu, nu)
} else {
(nu, mu)
};
let expansion = expand_skew_shared(lambda, inner);
expansion
.binary_search_by(|(p, _)| p.cmp(want))
.map(|i| expansion[i].1)
.unwrap_or(0)
}
fn schur_product(&self, mu: &Partition, nu: &Partition) -> Vec<(Partition, u128)> {
(*self.schur_product_shared(mu, nu)).clone()
}
fn schur_product_shared(&self, mu: &Partition, nu: &Partition) -> Arc<Vec<(Partition, u128)>> {
memoized_product(mu, nu, || None)
}
}
pub(crate) fn memoized_product(
mu: &Partition,
nu: &Partition,
shortcut: impl FnOnce() -> Option<Vec<(Partition, u128)>>,
) -> Arc<Vec<(Partition, u128)>> {
let (outer, inner, conjugate) = product_walk(mu, nu);
skew_cached(&outer, &inner, || {
shortcut().unwrap_or_else(|| expand_walk(&outer, &inner, conjugate))
})
}
fn product_walk(mu: &Partition, nu: &Partition) -> (Partition, Partition, bool) {
let (top, bottom) = if (mu.size(), mu.parts()) >= (nu.size(), nu.parts()) {
(mu, nu)
} else {
(nu, mu)
};
let (outer, inner) = juxtapose(top, bottom);
let rows = outer.len();
let width = outer.part(0) as usize;
let cells = top.size() + bottom.size();
let conjugate = top.len() == bottom.len()
&& 10 * bottom.size() >= 7 * top.size()
&& cells >= 72
&& rows >= 8
&& width > rows;
(outer, inner, conjugate)
}
fn juxtapose(mu: &Partition, nu: &Partition) -> (Partition, Partition) {
let shift = nu.part(0);
let mut outer = Vec::with_capacity(mu.len() + nu.len());
outer.extend(mu.parts().iter().map(|&p| p + shift));
outer.extend_from_slice(nu.parts());
let inner = vec![shift; if shift == 0 { 0 } else { mu.len() }];
(Partition::from_sorted(outer), Partition::from_sorted(inner))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::lr::NaiveLr;
use crate::partition::partitions_of;
fn p(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
fn reference_skew(outer: &Partition, inner: &Partition) -> Vec<(Partition, u128)> {
if !outer.contains(inner) {
return Vec::new();
}
let mut v: Vec<(Partition, u128)> = partitions_of(outer.size() - inner.size())
.into_iter()
.filter_map(|nu| {
let c = NaiveLr.lr_coeff(outer, inner, &nu);
(c != 0).then_some((nu, c))
})
.collect();
v.sort_by(|a, b| a.0.cmp(&b.0));
v
}
#[test]
fn degenerate_shapes() {
assert!(expand_skew(&p(&[2, 1]), &p(&[3])).is_empty());
assert!(expand_skew(&p(&[]), &p(&[1])).is_empty());
for sh in [&[][..], &[1], &[3, 2, 1], &[4, 4]] {
let l = p(sh);
assert_eq!(expand_skew(&l, &l), vec![(Partition::default(), 1)]);
}
for sh in [&[1][..], &[3, 2, 1], &[2, 2, 2], &[5]] {
let l = p(sh);
assert_eq!(expand_skew(&l, &Partition::default()), vec![(l.clone(), 1)]);
}
assert_eq!(expand_skew(&p(&[5]), &p(&[2])), vec![(p(&[3]), 1)]);
assert_eq!(
expand_skew(&p(&[1, 1, 1, 1]), &p(&[1])),
vec![(p(&[1, 1, 1]), 1)]
);
}
#[test]
fn very_deep_column() {
let col = Partition::from_sorted(vec![1; 300]);
assert_eq!(
expand_skew(&col, &Partition::default()),
vec![(col.clone(), 1)]
);
let inner = Partition::from_sorted(vec![1; 40]);
assert_eq!(
expand_skew(&col, &inner),
vec![(Partition::from_sorted(vec![1; 260]), 1)]
);
}
#[test]
fn disconnected_shape() {
let got = expand_skew(&p(&[4, 4, 2, 2]), &p(&[2, 2]));
let want = NaiveLr.schur_product(&p(&[2, 2]), &p(&[2, 2]));
assert_eq!(got, want);
assert_eq!(got, reference_skew(&p(&[4, 4, 2, 2]), &p(&[2, 2])));
}
#[test]
fn agrees_with_naive_on_every_small_skew_shape() {
let mut checked = 0;
for n in 0..=8u32 {
for outer in partitions_of(n) {
for k in 0..=n {
for inner in partitions_of(k) {
if !outer.contains(&inner) {
assert!(expand_skew(&outer, &inner).is_empty());
continue;
}
assert_eq!(
expand_skew(&outer, &inner),
reference_skew(&outer, &inner),
"s_{{{outer}/{inner}}}"
);
checked += 1;
}
}
}
}
assert!(checked > 300, "expected a real sweep, got {checked}");
}
#[test]
fn agrees_with_naive_on_every_small_product() {
let mut checked = 0;
for a in 0..=7u32 {
for b in 0..=(7 - a) {
for mu in partitions_of(a) {
for nu in partitions_of(b) {
assert_eq!(
SkewLr.schur_product(&mu, &nu),
NaiveLr.schur_product(&mu, &nu),
"s{mu}*s{nu}"
);
checked += 1;
}
}
}
}
assert!(checked > 200, "expected a real sweep, got {checked}");
}
#[test]
fn run_fill_boundaries() {
for (o, i) in [
(&[9, 2][..], &[][..]),
(&[9, 9, 2], &[]),
(&[9, 7], &[4]),
(&[9, 7, 5], &[4, 2]),
(&[8, 3], &[5]),
(&[8, 4, 2], &[6, 3]),
(&[12], &[]),
(&[12, 12], &[]),
(&[12, 11], &[3]),
(&[7, 3], &[]),
(&[3, 3, 7], &[]),
(&[10, 8, 5, 1], &[6, 3, 1]),
] {
let (outer, inner) = (p(o), p(i));
assert_eq!(
expand_skew(&outer, &inner),
reference_skew(&outer, &inner),
"s_{{{outer}/{inner}}}"
);
}
}
#[test]
fn empty_rows_are_traversed() {
for (o, i) in [
(&[4, 3, 3, 1][..], &[0, 3, 0, 0][..]), (&[4, 4], &[4, 0]), (&[5, 3, 3], &[2, 3, 3]), ] {
let (outer, inner) = (Partition::new(o.iter().copied()), p(i));
assert_eq!(
expand_skew(&outer, &inner),
reference_skew(&outer, &inner),
"s_{{{outer}/{inner}}}"
);
}
}
#[test]
fn packed_key_separates_states() {
for (o, i) in [
(&[6, 5, 4, 3][..], &[2, 1][..]),
(&[5, 5, 5, 5], &[]),
(&[7, 6, 4, 2], &[3, 2, 1]),
] {
let (outer, inner) = (p(o), p(i));
let got = expand_skew(&outer, &inner);
assert_eq!(got, reference_skew(&outer, &inner), "s_{{{outer}/{inner}}}");
let total: u128 = got.iter().map(|(_, c)| c).sum();
let want: u128 = reference_skew(&outer, &inner).iter().map(|(_, c)| c).sum();
assert_eq!(total, want, "tableau total for {outer}/{inner}");
}
}
#[test]
fn lr_coeff_matches_naive_including_zeros() {
for lambda in partitions_of(7) {
for mu in partitions_of(3) {
for nu in partitions_of(4) {
assert_eq!(
SkewLr.lr_coeff(&lambda, &mu, &nu),
NaiveLr.lr_coeff(&lambda, &mu, &nu),
"c^{lambda}_{{{mu},{nu}}}"
);
}
}
}
assert_eq!(SkewLr.lr_coeff(&p(&[3, 1]), &p(&[2]), &p(&[1])), 0);
assert_eq!(SkewLr.lr_coeff(&p(&[2, 2]), &p(&[3]), &p(&[1])), 0);
}
#[test]
fn lr_coeff_agrees_before_and_after_product_is_cached() {
let mu = p(&[4, 2, 1]);
let nu = p(&[3, 2]);
let n = mu.size() + nu.size();
let cold: Vec<u128> = partitions_of(n)
.iter()
.map(|l| SkewLr.lr_coeff(l, &mu, &nu))
.collect();
let product = SkewLr.schur_product(&mu, &nu); assert_eq!(product, NaiveLr.schur_product(&mu, &nu));
for (lambda, was) in partitions_of(n).iter().zip(&cold) {
assert_eq!(
SkewLr.lr_coeff(lambda, &mu, &nu),
*was,
"cached-product route diverged on c^{lambda}_{{{mu},{nu}}}"
);
assert_eq!(
SkewLr.lr_coeff(lambda, &nu, &mu),
*was,
"cached-product route diverged on c^{lambda}_{{{nu},{mu}}}"
);
let want = product
.iter()
.find(|(l, _)| l == lambda)
.map_or(0, |(_, c)| *c);
assert_eq!(*was, want, "vs product term for {lambda}");
}
}
#[test]
fn orientation_dispatch_preserves_expansions() {
let outer = p(&[14, 13, 12, 11, 10, 9, 8, 7]);
let inner = p(&[6, 5, 4, 3, 2, 1]);
assert!(prefer_conjugate(&outer, &inner), "test shape must dispatch");
let dispatched = expand_skew(&outer, &inner);
let mut direct = expand_oriented::<u64>(&outer, &inner, false).expect("no overflow");
direct.sort_by(|a, b| a.0.cmp(&b.0));
assert_eq!(dispatched, direct);
assert!(prefer_conjugate(
&p(&[16, 15, 14, 13, 12, 11, 10, 9]),
&p(&[8, 7, 6, 5, 4, 3, 2, 1])
));
assert!(prefer_conjugate(
&p(&[12, 11, 10, 9, 8, 7, 6, 5, 4, 3]),
&p(&[5, 4, 3, 2, 1])
));
assert!(prefer_conjugate(
&p(&[26, 23, 20, 17, 14, 11, 8, 5, 2]),
&p(&[14, 12, 10, 8, 6, 4, 2])
));
assert!(prefer_conjugate(
&p(&[26, 23, 20, 17, 14, 11, 8, 5, 2]),
&p(&[12, 10, 8, 6, 4])
));
assert!(prefer_conjugate(
&p(&[16, 15, 14, 12, 11, 10, 9, 8]),
&p(&[7, 6, 5, 4, 3, 2, 1])
));
assert!(!prefer_conjugate(
&p(&[20, 17, 14, 11, 8, 5, 2, 2]),
&p(&[8, 5, 2])
));
assert!(!prefer_conjugate(
&p(&[16, 14, 12, 10, 8, 6, 4, 2]),
&p(&[6, 4, 2])
));
assert!(!prefer_conjugate(
&p(&[30, 26, 22, 17, 13, 9, 5, 3, 1]),
&p(&[20, 16, 12, 8])
));
assert!(!prefer_conjugate(
&p(&[24, 20, 16, 12, 8, 4, 2]),
&p(&[12, 10, 8, 6, 4, 2])
));
assert!(!prefer_conjugate(&p(&[40, 36, 32]), &Partition::default()));
assert!(!prefer_conjugate(
&p(&[12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]),
&Partition::default()
));
assert!(!prefer_conjugate(
&p(&[9, 7, 5, 3, 2, 2, 1, 1]),
&Partition::default()
));
}
#[test]
fn product_walk_agrees_with_every_other_walk() {
for (a, b, conj) in [
(&[10u32, 10, 10, 10][..], &[9u32, 9, 9, 9][..], true),
(&[10, 8, 6, 4], &[8, 6, 4, 2], false),
] {
let (a, b) = (p(a), p(b));
let (outer, inner, chosen) = product_walk(&a, &b);
assert_eq!(chosen, conj, "dispatch for s{a}·s{b}");
let got = SkewLr.schur_product(&a, &b);
let (swapped_outer, swapped_inner) = juxtapose(&b, &a);
for (o, i, c) in [
(&outer, &inner, !conj),
(&swapped_outer, &swapped_inner, false),
(&swapped_outer, &swapped_inner, true),
] {
assert_eq!(
expand_walk(o, i, c),
got,
"walk {o}/{i} conj={c} on s{a}·s{b}"
);
}
}
}
#[test]
fn product_walk_is_symmetric_and_matches_the_calibration() {
let cases: &[(&[u32], &[u32], bool)] = &[
(&[16, 13, 10, 7], &[8, 6, 4, 2], false),
(&[20, 16, 12, 8], &[8, 6, 4, 2], false),
(&[18, 15, 12, 9], &[9, 7, 5, 3], false),
(&[24, 20, 16, 12], &[10, 8, 6, 4], false),
(&[20, 16, 12, 8], &[10, 8, 6, 4], false), (&[16, 13, 10, 7], &[10, 8, 6, 4], false), (&[16, 13, 10, 7], &[5, 4, 3, 2, 1], false),
(&[12, 11, 10, 9, 8, 7], &[6, 5, 4, 3], false),
(&[16, 13, 10, 7], &[8, 7, 6, 5, 4, 3], false),
(&[12, 10, 8, 6], &[9, 8, 7, 6, 5], false), (&[16, 13, 10, 7], &[10, 9, 8, 7, 6, 5], false),
(&[16, 13, 10, 7], &[12, 10, 8, 6], true),
(&[10, 9, 8, 7, 6, 5], &[9, 8, 7, 6, 5, 4], true),
(&[10, 9, 8, 7, 6, 5], &[8, 7, 6, 5, 4, 3], true),
(&[12, 10, 8, 6], &[10, 8, 6, 4], false),
(&[11, 9, 7, 5], &[10, 8, 6, 4], false),
(&[9, 8, 7, 6, 5], &[9, 7, 5, 3, 1], false),
(&[16, 13, 10, 7], &[16, 13, 10, 7], true),
(&[12, 10, 8, 6], &[12, 10, 8, 6], true),
(&[10, 9, 8, 7, 6, 5], &[10, 9, 8, 7, 6, 5], true),
(&[12, 9, 6, 3], &[12, 9, 6, 3], false),
(&[10, 8, 6, 4], &[10, 8, 6, 4], false),
(&[40, 32, 24], &[40, 32, 24], false),
(
&[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3],
&[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3],
false,
),
];
for (a, b, want) in cases {
let (a, b) = (p(a), p(b));
let (outer, inner, conj) = product_walk(&a, &b);
assert_eq!(conj, *want, "s{a}·s{b}");
let (outer_r, inner_r, conj_r) = product_walk(&b, &a);
assert_eq!(
(outer, inner, conj),
(outer_r, inner_r, conj_r),
"s{b}·s{a}"
);
}
let (outer, inner, _) = product_walk(&p(&[3, 2]), &p(&[6, 4, 2]));
assert_eq!(outer, p(&[9, 7, 5, 3, 2]));
assert_eq!(inner, p(&[3, 3, 3]));
}
#[test]
fn width_boundaries_match_pieri() {
for a in [254u32, 255, 256, 65534, 65535] {
let got = SkewLr.schur_product(&p(&[a]), &p(&[1]));
let mut want = vec![(p(&[a + 1]), 1), (p(&[a, 1]), 1)];
want.sort_by(|x, y| x.0.cmp(&y.0));
assert_eq!(got, want, "s[{a}]·s[1]");
}
}
fn sorted(v: Option<Vec<(Partition, u128)>>) -> Vec<(Partition, u128)> {
let mut v = v.expect("no overflow at u64");
v.sort_by(|a, b| a.0.cmp(&b.0));
v
}
#[test]
fn widths_agree_on_merging_shapes() {
for (o, i) in [
(&[10, 8, 5, 1][..], &[6, 3, 1][..]),
(&[6, 5, 4, 3], &[2, 1]),
(&[7, 6, 4, 2], &[3, 2, 1]),
] {
let (outer, inner) = (p(o), p(i));
let narrow = sorted(expand_layer::<u64, Key>(&outer, &inner, 1, false));
let mid = sorted(expand_layer::<u64, Key>(&outer, &inner, 2, false));
let wide = sorted(expand_layer::<u64, Key>(&outer, &inner, 4, false));
assert_eq!(narrow, mid, "widths 1 vs 2 on {outer}/{inner}");
assert_eq!(narrow, wide, "widths 1 vs 4 on {outer}/{inner}");
assert_eq!(narrow, reference_skew(&outer, &inner), "vs naive");
}
}
#[test]
fn key_representations_agree_on_merging_shapes() {
let small: &[(&[u32], &[u32])] = &[
(&[10, 8, 5, 1], &[6, 3, 1]),
(&[6, 5, 4, 3], &[2, 1]),
(&[7, 6, 4, 2], &[3, 2, 1]),
(&[9, 7, 5], &[4, 2]),
];
for &(o, i) in small {
let (outer, inner) = (p(o), p(i));
let w = elem_width(&outer, &inner);
let bytes = sorted(expand_layer::<u64, Key>(&outer, &inner, w, false));
let narrow = sorted(expand_layer::<u64, PackedKey<u64>>(
&outer, &inner, w, false,
));
let wide = sorted(expand_layer::<u64, PackedKey<W128>>(
&outer, &inner, w, false,
));
assert_eq!(narrow, bytes, "u64 bitmap vs bytes on {outer}/{inner}");
assert_eq!(wide, bytes, "128-bit bitmap vs bytes on {outer}/{inner}");
assert_eq!(bytes, reference_skew(&outer, &inner), "vs naive");
}
for m in [
&[6u32, 5, 4, 3, 2][..],
&[7, 6, 5, 4, 3],
&[10, 10, 10, 10, 10],
] {
let (outer, inner) = juxtapose(&p(m), &p(m));
let w = elem_width(&outer, &inner);
let bytes = sorted(expand_layer::<u64, Key>(&outer, &inner, w, false));
let narrow = sorted(expand_layer::<u64, PackedKey<u64>>(
&outer, &inner, w, false,
));
let wide = sorted(expand_layer::<u64, PackedKey<W128>>(
&outer, &inner, w, false,
));
assert_eq!(narrow, bytes, "u64 bitmap vs bytes on s{}²", p(m));
assert_eq!(wide, bytes, "128-bit bitmap vs bytes on s{}²", p(m));
assert_eq!(
SkewLr.schur_product(&p(m), &p(m)),
bytes,
"dispatched s{}²",
p(m)
);
}
}
#[test]
fn packed_bitmaps_round_trip_and_separate() {
fn pack_partition<W: Word>(parts: &[u32]) -> W {
let k = parts.len();
let mut w = W::ZERO;
for (i, &c) in parts.iter().enumerate() {
w = w.set(c + (k - 1 - i) as u32);
}
w
}
fn pack_row<W: Word>(cells: &[u32]) -> W {
let mut w = W::ZERO;
for (j, &v) in cells.iter().enumerate() {
w = w.set(v + j as u32);
}
w
}
let mut buf = Vec::new();
let mut seen64 = std::collections::HashSet::new();
let mut seen128 = std::collections::HashSet::new();
let mut count = 0;
for n in 0..=36u32 {
for q in partitions_of(n) {
if q.len() > 6 || q.part(0) > 6 {
continue;
}
let w64: u64 = pack_partition(q.parts());
unpack_partition(w64, &mut buf);
assert_eq!(buf, q.parts(), "u64 round trip of {q}");
assert!(seen64.insert(w64), "u64 word collision at {q}");
let w128: W128 = pack_partition(q.parts());
unpack_partition(w128, &mut buf);
assert_eq!(buf, q.parts(), "128-bit round trip of {q}");
assert!(seen128.insert(w128.0), "128-bit word collision at {q}");
count += 1;
}
}
assert_eq!(count, 924, "partitions in a 6 × 6 box");
fn rows_of(d: usize, min: u32, cur: &mut Vec<u32>, out: &mut Vec<Vec<u32>>) {
if cur.len() == d {
out.push(cur.clone());
return;
}
for v in min..=5 {
cur.push(v);
rows_of(d, v, cur, out);
cur.pop();
}
}
let mut rows = Vec::new();
for d in 0..=4 {
rows_of(d, 1, &mut Vec::new(), &mut rows);
}
assert_eq!(
rows.len(),
1 + 5 + 15 + 35 + 70,
"multisets of size ≤ 4 from 5 values"
);
let mut seen = std::collections::HashSet::new();
for cells in &rows {
let w: u64 = pack_row(cells);
unpack_row(w, &mut buf);
assert_eq!(&buf, cells, "row round trip of {cells:?}");
assert!(
seen.insert((cells.len(), w)),
"row word collision at {cells:?}"
);
}
let tall = vec![24u32; 40];
unpack_partition::<u64>(pack_partition(&tall), &mut buf);
assert_eq!(buf, tall);
let taller = vec![64u32; 64];
unpack_partition::<W128>(pack_partition(&taller), &mut buf);
assert_eq!(buf, taller);
let row = vec![56u32; 8];
unpack_row::<u64>(pack_row(&row), &mut buf);
assert_eq!(buf, row, "row bits up to position 63");
}
#[test]
fn packed_key_dispatch_boundaries() {
let e = Partition::default();
let l = p(&[62, 3]);
assert!(PackedKey::<u64>::fits(&l, &e));
assert_eq!(expand_skew(&l, &e), vec![(l.clone(), 1)]);
let l = p(&[63, 3]);
assert!(!PackedKey::<u64>::fits(&l, &e));
assert!(PackedKey::<W128>::fits(&l, &e));
assert_eq!(expand_skew(&l, &e), vec![(l.clone(), 1)]);
let l = p(&[126, 3]);
assert!(PackedKey::<W128>::fits(&l, &e));
assert_eq!(expand_skew(&l, &e), vec![(l.clone(), 1)]);
let l = p(&[127, 3]);
assert!(!PackedKey::<W128>::fits(&l, &e));
assert_eq!(expand_skew(&l, &e), vec![(l.clone(), 1)]);
for a in [60u32, 61, 62, 63] {
let got = SkewLr.schur_product(&p(&[a]), &p(&[1]));
let mut want = vec![(p(&[a + 1]), 1), (p(&[a, 1]), 1)];
want.sort_by(|x, y| x.0.cmp(&y.0));
assert_eq!(got, want, "s[{a}]·s[1]");
}
}
#[test]
fn byte_keys_merge_and_agree_with_conjugate_orientation() {
let wide = p(&[140, 136]);
assert!(!PackedKey::<W128>::fits(&wide, &Partition::default()));
assert_eq!(
expand_skew(&wide, &Partition::default()),
vec![(wide.clone(), 1)]
);
let m = p(&[33, 31]);
let (outer, inner) = juxtapose(&m, &m);
let w = elem_width(&outer, &inner);
let bytes = sorted(expand_layer::<u64, Key>(&outer, &inner, w, false));
let direct = SkewLr.schur_product(&m, &m);
assert_eq!(direct, bytes, "dispatched vs forced byte keys");
let mc = m.conjugate();
let mut via_conjugate: Vec<(Partition, u128)> = SkewLr
.schur_product(&mc, &mc)
.into_iter()
.map(|(l, c)| (l.conjugate(), c))
.collect();
via_conjugate.sort_by(|a, b| a.0.cmp(&b.0));
assert_eq!(direct, via_conjugate);
}
impl Acc for u8 {
const ONE: Self = 1;
fn checked_add(self, other: Self) -> Option<Self> {
u8::checked_add(self, other)
}
fn widen(self) -> u128 {
self as u128
}
}
#[test]
fn accumulator_overflow_is_detected_not_wrapped() {
let sorted = |v: Option<Vec<(Partition, u128)>>| {
v.map(|mut v| {
v.sort_by(|a, b| a.0.cmp(&b.0));
v
})
};
let (outer, inner) = juxtapose(&p(&[6, 5, 4, 3, 2]), &p(&[6, 5, 4, 3, 2]));
assert_eq!(expand_oriented::<u8>(&outer, &inner, false), None);
let full = sorted(expand_oriented::<u64>(&outer, &inner, false));
assert!(full.is_some(), "u64 must not saturate here");
assert_eq!(full, sorted(expand_oriented::<u128>(&outer, &inner, false)));
let (outer, inner) = juxtapose(&p(&[2, 1]), &p(&[2, 1]));
let small = sorted(expand_oriented::<u8>(&outer, &inner, false));
assert!(small.is_some());
assert_eq!(
small,
sorted(expand_oriented::<u128>(&outer, &inner, false))
);
}
}