use alloc::boxed::Box;
use alloc::collections::BTreeMap;
use alloc::collections::btree_map::Entry;
use alloc::vec::Vec;
use core::sync::atomic::{AtomicU64, Ordering};
use crate::err::{BackwardError, NonFiniteSite, Result};
use crate::exec::policy::{GradMode, NanPolicy};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct TensorId(u64);
static NEXT_TENSOR_ID: AtomicU64 = AtomicU64::new(0);
impl TensorId {
#[must_use]
pub fn next() -> Self {
Self(NEXT_TENSOR_ID.fetch_add(1, Ordering::Relaxed))
}
#[must_use]
pub const fn get(self) -> u64 {
self.0
}
}
pub trait TapeStorage: Clone + 'static {
fn id(&self) -> TensorId;
fn ones_like(&self) -> Result<Self>;
fn accumulate(&self, contribution: &Self) -> Result<Self>;
fn has_non_finite(&self) -> Result<bool>;
}
pub type BackwardFn<S> = Box<dyn Fn(&S) -> Result<Vec<S>> + Send + Sync>;
pub struct TapeNode<S> {
pub output_id: TensorId,
pub input_ids: Vec<TensorId>,
pub backward: BackwardFn<S>,
}
impl<S> core::fmt::Debug for TapeNode<S> {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.debug_struct("TapeNode")
.field("output_id", &self.output_id)
.field("input_ids", &self.input_ids)
.finish_non_exhaustive()
}
}
pub struct GradientMap<S> {
grads: BTreeMap<TensorId, S>,
}
impl<S> GradientMap<S> {
pub fn get(&self, id: TensorId) -> Option<&S> {
self.grads.get(&id)
}
pub fn insert(&mut self, id: TensorId, grad: S) -> Option<S> {
self.grads.insert(id, grad)
}
#[must_use]
pub fn len(&self) -> usize {
self.grads.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.grads.is_empty()
}
pub fn iter(&self) -> impl Iterator<Item = (TensorId, &S)> {
self.grads.iter().map(|(id, g)| (*id, g))
}
}
impl<S> Default for GradientMap<S> {
fn default() -> Self {
Self {
grads: BTreeMap::new(),
}
}
}
pub struct Tape<S> {
nodes: Vec<TapeNode<S>>,
}
impl<S> Default for Tape<S> {
fn default() -> Self {
Self::new()
}
}
impl<S> Tape<S> {
#[must_use]
pub const fn new() -> Self {
Self { nodes: Vec::new() }
}
pub fn push(&mut self, node: TapeNode<S>) {
if !GradMode::current().records() {
return;
}
self.nodes.push(node);
}
#[must_use]
pub fn depth(&self) -> usize {
self.nodes.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
#[must_use]
pub fn drain(&mut self) -> Vec<TapeNode<S>> {
core::mem::take(&mut self.nodes)
}
#[must_use]
pub fn drain_reachable(&mut self, root: TensorId) -> Vec<TapeNode<S>> {
let mut reachable_ids = alloc::vec![root];
for node in self.nodes.iter().rev() {
if reachable_ids.contains(&node.output_id) {
for input in &node.input_ids {
if !reachable_ids.contains(input) {
reachable_ids.push(*input);
}
}
}
}
let mut reachable = Vec::new();
let mut remaining = Vec::new();
for node in self.nodes.drain(..) {
if reachable_ids.contains(&node.output_id) {
reachable.push(node);
} else {
remaining.push(node);
}
}
self.nodes = remaining;
reachable
}
}
pub fn backward<S: TapeStorage>(nodes: Vec<TapeNode<S>>, loss: &S) -> Result<GradientMap<S>> {
let seed = loss.ones_like()?;
backward_with_seed(nodes, loss, &seed)
}
pub fn backward_with_seed<S: TapeStorage>(
nodes: Vec<TapeNode<S>>,
loss: &S,
seed: &S,
) -> Result<GradientMap<S>> {
let checked = NanPolicy::current().checks();
let mut grads: BTreeMap<TensorId, S> = BTreeMap::new();
grads.insert(loss.id(), seed.clone());
for node in nodes.into_iter().rev() {
let Some(grad_out) = grads.get(&node.output_id).cloned() else {
continue;
};
let contributions = (node.backward)(&grad_out)?;
for (input, contribution) in node.input_ids.into_iter().zip(contributions) {
if checked {
check_finite(&contribution, input, NonFiniteSite::Contribution)?;
}
match grads.entry(input) {
Entry::Occupied(mut slot) => {
let summed = slot.get().accumulate(&contribution)?;
if checked {
check_finite(&summed, input, NonFiniteSite::Accumulation)?;
}
slot.insert(summed);
}
Entry::Vacant(slot) => {
slot.insert(contribution);
}
}
}
}
Ok(GradientMap { grads })
}
fn check_finite<S: TapeStorage>(grad: &S, id: TensorId, site: NonFiniteSite) -> Result<()> {
if grad.has_non_finite()? {
return Err(BackwardError::NonFinite {
tensor: id.get(),
operation: site,
}
.into());
}
Ok(())
}