from copy import deepcopy

import torch
import torch.nn as nn
from torch.distributions import Categorical


def group_advantages(rewards):
    # rewards: [B, G]，每道题单独计算均值和总体标准差
    centered = rewards - rewards.mean(dim=1, keepdim=True)
    std = rewards.std(dim=1, keepdim=True, unbiased=False)
    return (centered / (std + 1e-8)).detach()


def grpo_loss(new_logp, old_logp, ref_logp, advantages, mask,
              clip_epsilon=0.2, beta=0.02):
    # logp、mask: [B, G, T]；advantages: [B, G]
    # 先清除无效位置，避免 padding 处的数值进入 exp。
    valid = mask.bool()
    log_ratio = torch.where(valid, new_logp - old_logp.detach(), 0.0)
    ratio = log_ratio.exp()
    advantage = advantages.detach().unsqueeze(-1)
    unclipped = ratio * advantage
    clipped = ratio.clamp(1 - clip_epsilon, 1 + clip_epsilon) * advantage
    policy_loss = -torch.minimum(unclipped, clipped)

    log_ref_ratio = torch.where(valid, ref_logp.detach() - new_logp, 0.0)
    kl_estimate = torch.expm1(log_ref_ratio) - log_ref_ratio
    token_loss = policy_loss + beta * kl_estimate

    # 先在每条回答内部平均，再对回答和问题平均。
    lengths = mask.sum(dim=-1).clamp_min(1)
    return ((token_loss * mask).sum(dim=-1) / lengths).mean()


class TinyPolicy(nn.Module):
    def __init__(self):
        super().__init__()
        self.question = nn.Embedding(7, 16)
        self.previous = nn.Embedding(6, 16)  # 0..4 是数字，5 是 BOS
        self.head = nn.Sequential(
            nn.Linear(32, 32), nn.Tanh(), nn.Linear(32, 5)
        )

    def forward(self, questions, previous_tokens):
        # questions: [N]；previous_tokens: [N, T]
        q = self.question(questions).unsqueeze(1)
        q = q.expand(-1, previous_tokens.shape[1], -1)
        previous = self.previous(previous_tokens)
        return self.head(torch.cat([q, previous], dim=-1))


def token_log_probs(model, questions, previous_tokens, answers):
    logits = model(questions, previous_tokens)
    return logits.log_softmax(dim=-1).gather(
        -1, answers.unsqueeze(-1)
    ).squeeze(-1)


@torch.no_grad()
def collect_rollout(policy, reference, questions, group_size):
    batch_size = len(questions)
    repeated_questions = questions.repeat_interleave(group_size)
    previous = torch.full((len(repeated_questions), 1), 5, dtype=torch.long)
    inputs, actions = [], []
    for _ in range(2):
        inputs.append(previous)
        distribution = Categorical(logits=policy(repeated_questions, previous))
        action = distribution.sample()
        actions.append(action)
        previous = action

    previous_tokens = torch.cat(inputs, dim=1)
    answers = torch.cat(actions, dim=1)
    old_logp = token_log_probs(policy, repeated_questions, previous_tokens, answers)
    ref_logp = token_log_probs(reference, repeated_questions, previous_tokens, answers)
    rewards = (answers.sum(dim=1) == repeated_questions).float()
    shape = (batch_size, group_size, 2)
    return (repeated_questions, previous_tokens, answers,
            old_logp.reshape(shape), ref_logp.reshape(shape),
            rewards.reshape(batch_size, group_size))


@torch.no_grad()
def exact_success_rate(policy, questions):
    # 枚举 5 × 5 种回答，计算模型答对的概率，无需再采样。
    rates = []
    for question in questions.tolist():
        q = torch.tensor([question])
        first_probs = policy(q, torch.tensor([[5]])).softmax(-1)[0, 0]
        success = 0.0
        for first in range(5):
            second = question - first
            if 0 <= second < 5:
                second_probs = policy(q, torch.tensor([[first]])).softmax(-1)[0, 0]
                success += float(first_probs[first] * second_probs[second])
        rates.append(success)
    return sum(rates) / len(rates)


def main():
    torch.manual_seed(0)
    torch.set_num_threads(1)
    policy = TinyPolicy()
    reference = deepcopy(policy).eval()
    reference.requires_grad_(False)
    optimizer = torch.optim.Adam(policy.parameters(), lr=0.01)
    questions = torch.arange(2, 7)
    group_size = 16
    history = [(0, exact_success_rate(policy, questions))]
    print(f"Update   0 | Exact success {history[-1][1]:.4f}")

    for update in range(1, 121):
        q, previous, answers, old_logp, ref_logp, rewards = collect_rollout(
            policy, reference, questions, group_size
        )
        advantages = group_advantages(rewards)
        mask = torch.ones_like(old_logp)  # 本例每条回答恰好有 2 个 token

        for _ in range(2):
            new_logp = token_log_probs(policy, q, previous, answers)
            new_logp = new_logp.reshape_as(old_logp)
            loss = grpo_loss(new_logp, old_logp, ref_logp, advantages, mask)
            optimizer.zero_grad()
            loss.backward()
            torch.nn.utils.clip_grad_norm_(policy.parameters(), 1.0)
            optimizer.step()

        history.append((update, exact_success_rate(policy, questions)))
        if update in (1, 10, 30, 60, 120):
            print(f"Update {update:3d} | Exact success {history[-1][1]:.4f}")
    return history


if __name__ == "__main__":
    main()
