#!/usr/bin/env python3
# Source: q4-ml-coding.html
import numpy as np


def softmax(z: np.ndarray, axis: int = -1) -> np.ndarray:
    e = np.exp(z - z.max(axis=axis, keepdims=True))
    return e / e.sum(axis=axis, keepdims=True)


def attention(Q: np.ndarray, K: np.ndarray, V: np.ndarray,
              causal: bool = False) -> np.ndarray:
    """Scaled dot-product attention. Q, K, V: (..., T, d). Returns (..., T, d_v)."""
    d = Q.shape[-1]
    scores = Q @ np.swapaxes(K, -1, -2) / np.sqrt(d)      # (..., T, T)
    if causal:
        T = scores.shape[-1]
        mask = np.triu(np.ones((T, T), dtype=bool), k=1)  # True above the diagonal
        scores = np.where(mask, -np.inf, scores)          # block future positions
    return softmax(scores, axis=-1) @ V


def multi_head_attention(X: np.ndarray, Wq: np.ndarray, Wk: np.ndarray, Wv: np.ndarray,
                         Wo: np.ndarray, n_heads: int, causal: bool = False) -> np.ndarray:
    """X: (B, T, D). All W: (D, D). D must divide by n_heads. Returns (B, T, D)."""
    B, T, D = X.shape
    hd = D // n_heads

    def split(M: np.ndarray) -> np.ndarray:               # (B, T, D) -> (B, H, T, hd)
        return M.reshape(B, T, n_heads, hd).transpose(0, 2, 1, 3)

    Q, K, V = split(X @ Wq), split(X @ Wk), split(X @ Wv)
    out = attention(Q, K, V, causal=causal)               # (B, H, T, hd)
    out = out.transpose(0, 2, 1, 3).reshape(B, T, D)      # concat heads
    return out @ Wo


if __name__ == "__main__":
    rng = np.random.default_rng(5)
    B, T, D, H = 2, 4, 8, 2
    X = rng.normal(size=(B, T, D))
    W = [rng.normal(size=(D, D)) / np.sqrt(D) for _ in range(4)]
    out = multi_head_attention(X, *W, n_heads=H, causal=True)
    assert out.shape == (B, T, D)
    # Causal check: changing the last token must not change earlier outputs.
    X2 = X.copy()
    X2[:, -1] += 10.0
    out2 = multi_head_attention(X2, *W, n_heads=H, causal=True)
    assert np.allclose(out[:, :-1], out2[:, :-1]) and not np.allclose(out[:, -1], out2[:, -1])
    # One head equals plain attention on the projections.
    one = multi_head_attention(X, W[0], W[1], W[2], np.eye(D), n_heads=1)
    assert np.allclose(one, attention(X @ W[0], X @ W[1], X @ W[2]))
    print("ok", out.shape)
