use std::borrow::Borrow;
use std::collections::HashSet;
use std::sync::Arc;
use serde::{Deserialize, Serialize};
use super::{Author, Entry, MessageId, ResultFacts};
use crate::message::{
AssistantMessage, CallId, Message, Origin, StopReason, ToolCall, ToolName, UserContent,
};
use crate::tool::feedback::tool_result_message;
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum PairingError {
#[error("consecutive assistant messages at index {index}")]
ConsecutiveAssistant {
index: usize,
},
#[error("tool call `{call_id}` at index {index} has no result in the following message")]
UnansweredToolCall {
index: usize,
call_id: CallId,
},
#[error(
"tool result `{call_id}` at index {index} answers no call from the preceding assistant message"
)]
OrphanToolResult {
index: usize,
call_id: CallId,
},
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
pub struct CallRef {
pub reply: MessageId,
pub index: u32,
}
impl CallRef {
pub fn wire(&self) -> String {
format!("{}/{}", self.reply, self.index)
}
pub fn calls(
reply: MessageId,
message: &AssistantMessage,
) -> impl Iterator<Item = (Self, &ToolCall)> {
(0..).zip(message.tool_calls()).map(move |(index, call)| {
let at = Self { reply, index };
(at, call)
})
}
}
pub fn answered_by<'c, 'a, T>(
calls: impl IntoIterator<Item = &'c CallId>,
answers: impl IntoIterator<Item = (&'a CallId, T)>,
) -> Vec<Option<T>> {
let mut waiting: Vec<(usize, &CallId)> = calls.into_iter().enumerate().collect();
let mut found: Vec<Option<T>> = waiting.iter().map(|_| None).collect();
for (id, answer) in answers {
if let Some((at, _)) = take(&mut waiting, id, |(_, id)| id)
&& let Some(slot) = found.get_mut(at)
{
*slot = Some(answer);
}
}
found
}
pub fn placed<T: Copy>(
calls: &[(CallRef, &CallId)],
items: &[(&CallId, Option<CallRef>, T)],
) -> Vec<Option<T>> {
let kept: Vec<Option<usize>> = calls
.iter()
.map(|(place, call)| {
let here =
|(id, at, _): &(&CallId, Option<CallRef>, T)| *at == Some(*place) && id == call;
items.iter().position(here)
})
.collect();
let rest = (0..)
.zip(items)
.filter(|(at, _)| !kept.contains(&Some(*at)));
let waiting = calls.iter().zip(&kept).filter(|(_, kept)| kept.is_none());
let mut paired = answered_by(
waiting.map(|((_, id), _)| *id),
rest.map(|(_, &(id, _, item))| (id, item)),
)
.into_iter();
kept.into_iter()
.map(|kept| match kept {
Some(at) => items.get(at).map(|&(.., item)| item),
None => paired.next().flatten(),
})
.collect()
}
pub fn validate(messages: &[impl Borrow<Message>]) -> Result<(), PairingError> {
repair(
messages
.iter()
.map(|message| message.borrow().clone())
.collect(),
)
.repairs
.into_iter()
.next()
.map_or(Ok(()), Err)
}
pub const NO_RESULT_PROVIDED: &str = "No result provided";
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Pairing {
pub stored: bool,
pub answers: bool,
}
impl Pairing {
pub const fn canonical() -> Self {
Self {
stored: false,
answers: true,
}
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct Paired {
pub messages: Vec<Message>,
pub repairs: Vec<PairingError>,
}
pub fn repair(messages: Vec<Message>) -> Paired {
let shaped = shape(messages, true);
Paired {
messages: shaped.messages,
repairs: shaped.repairs,
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct Normalized {
pub entries: Vec<Entry>,
pub repairs: Vec<PairingError>,
pub merged: Vec<(MessageId, MessageId)>,
pub dropped: Vec<MessageId>,
}
pub fn normalize(entries: Vec<Entry>) -> Normalized {
let (messages, metas): (Vec<Message>, Vec<Meta>) = entries
.into_iter()
.map(|entry| {
let message = Arc::unwrap_or_clone(entry.message);
(message, (entry.author, entry.id, entry.made, entry.facts))
})
.unzip();
let shaped = shape(messages, false);
let mut used = HashSet::new();
let mut merged = Vec::new();
let mut entries = Vec::with_capacity(shaped.messages.len());
for (message, sources) in shaped.messages.into_iter().zip(shaped.sources) {
let facts = sources
.iter()
.filter_map(|source| metas.get(*source))
.fold(ResultFacts::default(), |facts, (.., more)| facts.and(more));
let mut free = sources.iter().filter(|source| used.insert(**source));
let kept = free.next().and_then(|source| metas.get(*source));
let into = kept.and_then(|(_, id, ..)| *id);
for gone in free.filter_map(|source| metas.get(*source)?.1) {
if let Some(into) = into {
merged.push((into, gone));
}
}
let entry = match kept {
Some((author, id, made, _)) => Entry {
message: Arc::new(message),
author: author.clone(),
id: *id,
made: *made,
facts,
},
None => {
let first = sources.first().and_then(|source| metas.get(*source));
Entry {
message: Arc::new(message),
author: first
.map_or_else(|| Some(Author::rig()), |(author, ..)| author.clone()),
id: None,
made: None,
facts,
}
}
};
entries.push(entry);
}
let dropped = metas.iter().enumerate();
let dropped = dropped.filter(|(source, _)| !used.contains(source));
Normalized {
entries,
repairs: shaped.repairs,
merged,
dropped: dropped.filter_map(|(_, (_, id, ..))| *id).collect(),
}
}
type Meta = (Option<Author>, Option<MessageId>, Option<u64>, ResultFacts);
struct Shaped {
messages: Vec<Message>,
sources: Vec<Vec<usize>>,
repairs: Vec<PairingError>,
}
fn shape(messages: Vec<Message>, merge_users: bool) -> Shaped {
let canonical = |messages: Vec<Message>| {
let history = messages.into_iter().map(Some).collect();
walk(history, Pairing::canonical(), merge_users, true)
};
let mut shaped = canonical(messages);
while merge_turns(&mut shaped) {
let again = canonical(std::mem::take(&mut shaped.messages));
let sources = again.sources.iter().map(|sources| {
let earlier = sources.iter().filter_map(|at| shaped.sources.get(*at));
earlier.flatten().copied().collect()
});
shaped.sources = sources.collect();
shaped.messages = again.messages;
}
shaped
}
fn share_origin(first: Option<&Origin>, later: Option<&Origin>) -> bool {
match (first, later) {
(Some(first), Some(later)) => {
first.same_model(&later.api, &later.provider, &later.model)
&& first.context == later.context
}
(None, None) => true,
_ => false,
}
}
struct TurnKind {
empty: bool,
failed: bool,
aborted: bool,
origin: Option<Origin>,
}
impl TurnKind {
fn of(turn: &AssistantMessage) -> Self {
Self {
empty: turn.content.is_empty(),
failed: matches!(turn.stop, Some(StopReason::Error(_))),
aborted: matches!(turn.stop, Some(StopReason::Aborted(_))),
origin: turn.origin.clone(),
}
}
fn merges(&self, later: &Self) -> bool {
self.empty
|| later.empty
|| (self.failed == later.failed
&& self.aborted == later.aborted
&& share_origin(self.origin.as_ref(), later.origin.as_ref()))
}
}
fn merge_turns(shaped: &mut Shaped) -> bool {
let before = shaped.messages.len();
let mut messages: Vec<Message> = Vec::with_capacity(before);
let mut sources: Vec<Vec<usize>> = Vec::with_capacity(before);
let all = shaped.messages.drain(..).zip(shaped.sources.drain(..));
for (mut message, mut from) in all {
if let Message::Assistant(turn) = &mut message
&& let Some(Message::Assistant(previous)) = messages.last_mut()
&& TurnKind::of(previous).merges(&TurnKind::of(turn))
{
let first_empty = previous.content.is_empty();
if first_empty {
previous.origin = turn.origin.take();
}
if first_empty || !turn.content.is_empty() {
previous.stop = turn.stop.take();
}
previous.content.append(&mut turn.content);
if let Some(into) = sources.last_mut() {
into.append(&mut from);
}
continue;
}
messages.push(message);
sources.push(from);
}
shaped.messages = messages;
shaped.sources = sources;
shaped.messages.len() < before
}
pub fn pair(history: Vec<Option<Message>>, pairing: Pairing) -> Paired {
let shaped = walk(history, pairing, true, false);
Paired {
messages: shaped.messages,
repairs: shaped.repairs,
}
}
fn walk(
history: Vec<Option<Message>>,
pairing: Pairing,
merge_users: bool,
sourced: bool,
) -> Shaped {
let mut stored = pairing.stored.then(Vec::new);
let mut walk = Walk {
answers: pairing.answers,
merge_users,
sourced,
..Walk::default()
};
let parting = if sourced {
parting_turns(&history)
} else {
Vec::new()
};
walk.repairs
.extend(parting.iter().map(|(_, why)| why.clone()));
for step in steps(history, &parting) {
match step {
Step::Turn(index, turn) => {
if let (Some(before), Some(turn)) = (&walk.after_turn, &turn)
&& before.merges(&TurnKind::of(turn))
{
walk.repairs
.push(PairingError::ConsecutiveAssistant { index });
}
walk.close();
stored = None;
walk.gap = turn.is_none();
walk.after_turn = match &turn {
Some(turn) if turn.content.is_empty() && walk.after_turn.is_some() => {
walk.after_turn.take()
}
turn => turn.as_ref().map(TurnKind::of),
};
let Some(turn) = turn else { continue };
if !turn.stop.as_ref().is_some_and(|stop| stop.is_failure()) {
let calls = turn.tool_calls();
let calls = calls.map(|call| (call.id.clone(), call.function.name.clone()));
walk.waiting = calls.collect();
walk.waiting_at = index;
}
walk.put(Message::Assistant(turn), [index]);
}
Step::System(index, system) => {
walk.after_turn = None;
if walk.waiting.is_empty() {
walk.gap = false;
walk.put(system, [index]);
} else {
walk.held.push((index, system));
}
}
Step::User(first, parts) => {
walk.after_turn = None;
if parts.is_empty() {
walk.close();
let empty = Message::User {
content: Vec::new(),
};
walk.put(empty, [first]);
walk.gap = false;
continue;
}
let mut content = Vec::with_capacity(parts.len());
for (index, part) in parts {
let UserContent::ToolResult(result) = part else {
content.push((Some(index), part));
continue;
};
let answers = match &mut stored {
Some(taken) if !taken.contains(&result.call) => {
taken.push(result.call.clone());
true
}
Some(_) => false,
None => take(&mut walk.waiting, &result.call, |(id, _)| id).is_some(),
};
if answers {
content.push((Some(index), UserContent::ToolResult(result)));
} else {
walk.repairs.push(PairingError::OrphanToolResult {
index,
call_id: result.call,
});
}
}
if content.is_empty() && walk.waiting.is_empty() {
continue;
}
let only_results =
!content.is_empty() && content.iter().all(|(_, part)| is_result(part));
if walk.pending.is_empty() {
walk.pending_gap = walk.gap;
}
walk.pending.extend(content);
walk.gap = false;
if only_results && !walk.waiting.is_empty() {
continue;
}
walk.close();
}
}
}
walk.close();
Shaped {
messages: walk.shaped,
sources: walk.sources,
repairs: walk.repairs,
}
}
pub(crate) fn is_result(part: &UserContent) -> bool {
matches!(part, UserContent::ToolResult(_))
}
pub fn close_pending<'a>(calls: impl IntoIterator<Item = &'a ToolCall>) -> Message {
close_pending_with(calls, NO_RESULT_PROVIDED)
}
pub fn close_pending_with<'a>(calls: impl IntoIterator<Item = &'a ToolCall>, why: &str) -> Message {
let calls = calls.into_iter();
Message::User {
content: unanswered(calls.map(|call| (&call.id, &call.function.name)), why),
}
}
fn unanswered<'a>(
calls: impl IntoIterator<Item = (&'a CallId, &'a ToolName)>,
why: &str,
) -> Vec<UserContent> {
calls
.into_iter()
.map(|(id, name)| tool_result_message(id.clone(), name.clone(), why.to_owned()))
.collect()
}
fn take<T>(waiting: &mut Vec<T>, id: &CallId, id_of: impl Fn(&T) -> &CallId) -> Option<T> {
let at = waiting.iter().position(|call| id_of(call) == id)?;
Some(waiting.remove(at))
}
enum Step {
Turn(usize, Option<AssistantMessage>),
System(usize, Message),
User(usize, Vec<(usize, UserContent)>),
}
fn parting_turns(history: &[Option<Message>]) -> Vec<(usize, PairingError)> {
let mut parting = Vec::new();
let mut result = None;
for (index, message) in history.iter().enumerate().rev() {
match message {
Some(Message::System { .. }) => {}
Some(Message::User { content }) => {
let found = content.iter().find_map(UserContent::as_tool_result);
let found = found.map(|found| (index, found.call.clone()));
result = found.or(result);
}
Some(Message::Assistant(turn)) if turn.content.is_empty() => {
if let Some((at, call_id)) = &result {
let why = PairingError::OrphanToolResult {
index: *at,
call_id: call_id.clone(),
};
parting.push((index, why));
}
}
_ => result = None,
}
}
parting
}
fn steps(history: Vec<Option<Message>>, left_out: &[(usize, PairingError)]) -> Vec<Step> {
let mut steps: Vec<Step> = Vec::with_capacity(history.len());
for (index, message) in history.into_iter().enumerate() {
if left_out.iter().any(|(at, _)| *at == index) {
continue;
}
match message {
None => steps.push(Step::Turn(index, None)),
Some(Message::Assistant(turn)) => steps.push(Step::Turn(index, Some(turn))),
Some(system @ Message::System { .. }) => steps.push(Step::System(index, system)),
Some(Message::User { content }) => {
let joins = !content.is_empty();
let parts = content.into_iter().map(|part| (index, part));
match steps.last_mut() {
Some(Step::User(_, previous)) if joins && !previous.is_empty() => {
previous.extend(parts)
}
_ => steps.push(Step::User(index, parts.collect())),
}
}
}
}
steps
}
#[derive(Default)]
struct Walk {
answers: bool,
merge_users: bool,
sourced: bool,
shaped: Vec<Message>,
sources: Vec<Vec<usize>>,
repairs: Vec<PairingError>,
waiting: Vec<(CallId, ToolName)>,
waiting_at: usize,
held: Vec<(usize, Message)>,
gap: bool,
pending: Vec<(Option<usize>, UserContent)>,
pending_gap: bool,
after_turn: Option<TurnKind>,
}
impl Walk {
fn put(&mut self, message: Message, sources: impl IntoIterator<Item = usize>) {
self.shaped.push(message);
if self.sourced {
self.sources.push(sources.into_iter().collect());
}
}
fn close(&mut self) {
let mut content = std::mem::take(&mut self.pending);
let merge = std::mem::take(&mut self.pending_gap);
let waiting = std::mem::take(&mut self.waiting);
let missing =
if self.answers {
let index = self.waiting_at;
self.repairs.extend(waiting.iter().map(|(id, _)| {
PairingError::UnansweredToolCall {
index,
call_id: id.clone(),
}
}));
unanswered(
waiting.iter().map(|(id, name)| (id, name)),
NO_RESULT_PROVIDED,
)
} else {
Vec::new()
};
if !self.merge_users {
self.close_apart(content, missing);
return;
}
let at = content
.iter()
.position(|(_, part)| !is_result(part))
.unwrap_or(content.len());
content.splice(at..at, missing.into_iter().map(|part| (None, part)));
content.sort_by_key(|(_, part)| !is_result(part));
let at = content
.iter()
.position(|(_, part)| !is_result(part))
.unwrap_or(content.len());
let text = if self.held.is_empty() {
Vec::new()
} else {
content.split_off(at)
};
if !content.is_empty() {
let (sources, content) = sourced(content);
match self.shaped.last_mut() {
Some(Message::User { content: previous }) if merge => previous.extend(content),
_ => self.put(Message::User { content }, sources),
}
}
for (index, system) in std::mem::take(&mut self.held) {
self.put(system, [index]);
}
if !text.is_empty() {
let (sources, content) = sourced(text);
self.put(Message::User { content }, sources);
}
}
fn close_apart(
&mut self,
content: Vec<(Option<usize>, UserContent)>,
missing: Vec<UserContent>,
) {
let mut messages: Vec<(Option<usize>, Vec<UserContent>)> = Vec::new();
for (source, part) in content {
match messages.last_mut() {
Some((last, parts)) if *last == source => parts.push(part),
_ => messages.push((source, vec![part])),
}
}
match messages.first_mut() {
Some((_, parts)) => {
let at = parts.iter().position(|part| !is_result(part));
let at = at.unwrap_or(parts.len());
parts.splice(at..at, missing);
}
None if !missing.is_empty() => messages.push((None, missing)),
None => {}
}
for (source, mut content) in messages {
content.sort_by_key(|part| !is_result(part));
self.put(Message::User { content }, source);
}
for (index, system) in std::mem::take(&mut self.held) {
self.put(system, [index]);
}
}
}
fn sourced(content: Vec<(Option<usize>, UserContent)>) -> (Vec<usize>, Vec<UserContent>) {
let mut sources: Vec<usize> = Vec::new();
let parts = content.into_iter().map(|(source, part)| {
if let Some(source) = source
&& !sources.contains(&source)
{
sources.push(source);
}
part
});
let parts = parts.collect();
(sources, parts)
}
pub fn pending_calls(messages: &[impl Borrow<Message>]) -> Vec<ToolCall> {
let pending = pending(messages);
let calls = pending.into_iter().flat_map(|(_, calls)| calls);
calls.map(|(_, call)| call.clone()).collect()
}
pub(crate) fn pending<M: Borrow<Message>>(
messages: &[M],
) -> Option<(usize, Vec<(u32, &ToolCall)>)> {
let (at, reply) = messages
.iter()
.map(Borrow::borrow)
.enumerate()
.rev()
.find_map(|(at, message)| match message {
Message::Assistant(reply) => Some((at, reply)),
_ => None,
})?;
if reply.stop.as_ref().is_some_and(|stop| stop.is_failure()) {
return None;
}
let results = messages
.iter()
.skip(at + 1)
.flat_map(|message| message.borrow().results())
.map(|result| (&result.call, ()));
let answered = answered_by(reply.tool_calls().map(|call| &call.id), results);
let calls = (0..).zip(reply.tool_calls()).zip(answered);
let calls = calls.filter_map(|(call, answer)| answer.is_none().then_some(call));
Some((at, calls.collect()))
}
pub fn safe_start(messages: &[impl Borrow<Message>], at: usize) -> usize {
let mut start = at.min(messages.len());
for (index, message) in messages.iter().enumerate().skip(at) {
match message.borrow() {
Message::Assistant(_) => break,
Message::User { content }
if content
.iter()
.any(|item| matches!(item, UserContent::ToolResult(_))) =>
{
start = index + 1;
}
_ => {}
}
}
start
}
#[cfg(test)]
mod tests;