Skip to main content

rig_core/conversation/
mod.rs

1//! One conversation model for all of rig: [`Conversation`], its edits as
2//! [`Change`]s, [`TurnRecord`]s kept as asides, and [`pairing`] of tool
3//! calls with their results.
4//!
5//! ```
6//! use rig_core::conversation::{Author, Conversation, Entry, pairing};
7//! use rig_core::message::Message;
8//!
9//! let mut conversation = Conversation::new();
10//! let hello = conversation.push(Message::user("Hello"));
11//! conversation.push(Message::assistant("Hi"));
12//! // A plugin rewrites the greeting; the entry keeps its id.
13//! let mut greeting = conversation.entry(0).ok_or("no entry")?;
14//! greeting.message = Message::user("Hello there").into();
15//! conversation.splice(0..1, [greeting], Author::plugin("polite"));
16//! assert_eq!(conversation.index_of(hello), Some(0));
17//!
18//! // The outbox folds into the same value.
19//! let mut folded = Conversation::new();
20//! for change in conversation.take_unsaved() {
21//!     folded.apply(&change)?;
22//! }
23//! assert_eq!(folded, conversation);
24//! assert!(pairing::pending_calls(conversation.messages()).is_empty());
25//! # Ok::<(), Box<dyn std::error::Error>>(())
26//! ```
27
28use std::collections::{HashMap, HashSet};
29use std::fmt;
30use std::ops::{Bound, Range, RangeBounds};
31use std::str::FromStr;
32use std::sync::Arc;
33
34use serde::{Deserialize, Serialize, Serializer};
35
36use crate::completion::Message;
37use crate::message::{StopReason, ToolCall, UserContent};
38
39mod aside;
40mod author;
41mod facts;
42mod lineage;
43mod note;
44pub mod pairing;
45mod turn;
46
47pub use aside::{Aside, AsideId};
48pub use author::{Author, AuthorKind, RequestId};
49pub use facts::ResultFacts;
50pub use lineage::Lineage;
51pub use note::Note;
52pub use pairing::CallRef;
53pub use turn::{StopCause, TURN, TurnEnd, TurnRecord};
54
55use pairing::{Normalized, PairingError};
56
57/// How a text file attached to a user's message starts, followed by its
58/// label and `">`.
59pub const FILE_OPEN: &str = "<file path=\"";
60
61/// How a text file attached to a user's message ends.
62pub const FILE_CLOSE: &str = "</file>";
63
64/// The label and the contents of an attached text file, when `text` is
65/// one, so a view can show it without the markup around it.
66pub fn attached_file(text: &str) -> Option<(&str, &str)> {
67    let rest = text.strip_prefix(FILE_OPEN)?.strip_suffix(FILE_CLOSE)?;
68    rest.split_once("\">\n")
69}
70
71/// How a note that a path a user's message named is not attached starts,
72/// followed by its label and `">`.
73pub const UNATTACHED_OPEN: &str = "<unattached path=\"";
74
75/// How a note that a path a user's message named is not attached ends.
76pub const UNATTACHED_CLOSE: &str = "</unattached>";
77
78/// The label and the reason of a note that a path a user's message named
79/// is not attached, when `text` is one.
80pub fn unattached(text: &str) -> Option<(&str, &str)> {
81    let rest = text
82        .strip_prefix(UNATTACHED_OPEN)?
83        .strip_suffix(UNATTACHED_CLOSE)?;
84    rest.split_once("\">\n")
85}
86
87/// Whether `text` is what attaching put in a user's message, an
88/// [`attached_file`] or an [`unattached`] note, rather than the user's
89/// own typing.
90pub fn is_attachment_text(text: &str) -> bool {
91    attached_file(text).is_some() || unattached(text).is_some()
92}
93
94/// A conversation: its entries (each a message with an id and, when it is
95/// not the user's own or the model's, an author), its asides, why its last
96/// user message is unanswered, and the changes made to it that nobody has
97/// saved yet. Every edit builds a [`Change`], applies it with the same code
98/// a fold ([`apply`](Self::apply)) uses, and keeps it in the outbox
99/// ([`unsaved`](Self::unsaved)).
100///
101/// Two conversations are equal when their entries (messages, ids and
102/// authors), saved asides and halt are: the outbox, the revision, unsaved
103/// asides and when entries were made are not compared, so a value folded
104/// from a log equals the live one and two values built alike are equal.
105///
106/// Its serde form is its state: entries, saved asides, halt and the next
107/// ids, without the outbox, the revision or the lineage. A value read back
108/// from it is [`Lineage::DETACHED`].
109#[derive(Clone, Debug, Default, Serialize, Deserialize)]
110#[serde(try_from = "State")]
111pub struct Conversation {
112    /// What a request sends, so [`messages`](Self::messages) is a slice;
113    /// shared with the requests and records made from it.
114    messages: Vec<Arc<Message>>,
115    /// Parallel to `messages`.
116    meta: Vec<Meta>,
117    /// In the order put.
118    #[serde(serialize_with = "saved_asides")]
119    asides: Vec<(AsideId, Aside)>,
120    #[serde(skip_serializing_if = "Option::is_none")]
121    halted: Option<Halt>,
122    /// The id the next new entry gets; only rises, but for a reset to another value.
123    next_id: u64,
124    /// The id the next new aside gets; only rises, but for a reset to another value.
125    next_aside: u64,
126    /// The changes behind this value: those of the log it continues, then
127    /// its own.
128    #[serde(skip)]
129    revision: u64,
130    /// The log it continues.
131    #[serde(skip)]
132    lineage: Lineage,
133    #[serde(skip)]
134    unsaved: Vec<ChangeRecord>,
135    /// The time edits are made at, set by [`dated`](Self::dated); now when
136    /// `None`.
137    #[serde(skip)]
138    clock: Option<u64>,
139}
140
141/// An entry's id, author and when it was made, beside its message. Its
142/// serde form carries `made`, so a reset and a value read back keep it;
143/// equality leaves it out.
144#[derive(Clone, Debug, Serialize, Deserialize)]
145struct Meta {
146    id: MessageId,
147    #[serde(default, skip_serializing_if = "Option::is_none")]
148    author: Option<Author>,
149    /// Milliseconds since the Unix epoch: when the entry was first made.
150    #[serde(default)]
151    made: u64,
152    /// What the calls its results answer published.
153    #[serde(default, skip_serializing_if = "ResultFacts::is_empty")]
154    facts: ResultFacts,
155}
156
157/// A conversation as saved, checked before it becomes one.
158#[derive(Deserialize)]
159struct State {
160    #[serde(default)]
161    messages: Vec<Arc<Message>>,
162    #[serde(default)]
163    meta: Vec<Meta>,
164    #[serde(default)]
165    asides: Vec<(AsideId, Aside)>,
166    #[serde(default)]
167    halted: Option<Halt>,
168    #[serde(default)]
169    next_id: u64,
170    #[serde(default)]
171    next_aside: u64,
172}
173
174impl TryFrom<State> for Conversation {
175    type Error = ApplyError;
176
177    fn try_from(state: State) -> Result<Self, ApplyError> {
178        if state.meta.len() != state.messages.len() {
179            return Err(mismatch(format!(
180                "{} messages but {} ids",
181                state.messages.len(),
182                state.meta.len()
183            )));
184        }
185        let mut ids = HashSet::new();
186        if let Some(meta) = state
187            .meta
188            .iter()
189            .find(|meta| meta.id.0 >= state.next_id || !ids.insert(meta.id))
190        {
191            return Err(mismatch(format!("message id {} reused", meta.id.0)));
192        }
193        let mut asides = HashSet::new();
194        if let Some((id, _)) = state
195            .asides
196            .iter()
197            .find(|(id, _)| id.0 >= state.next_aside || !asides.insert(*id))
198        {
199            return Err(mismatch(format!("aside id {} reused", id.0)));
200        }
201        Ok(Self {
202            messages: state.messages,
203            meta: state.meta,
204            asides: state.asides,
205            halted: state.halted,
206            next_id: state.next_id,
207            next_aside: state.next_aside,
208            revision: 0,
209            lineage: Lineage::DETACHED,
210            unsaved: Vec::new(),
211            clock: None,
212        })
213    }
214}
215
216fn saved_asides<S: Serializer>(
217    asides: &[(AsideId, Aside)],
218    serializer: S,
219) -> Result<S::Ok, S::Error> {
220    serializer.collect_seq(asides.iter().filter(|(_, aside)| aside.saved))
221}
222
223impl PartialEq for Conversation {
224    fn eq(&self, other: &Self) -> bool {
225        let saved = |(_, aside): &&(AsideId, Aside)| aside.saved;
226        let same = |a: &Meta, b: &Meta| a.id == b.id && a.author == b.author && a.facts == b.facts;
227        self.messages == other.messages
228            && self.meta.len() == other.meta.len()
229            && self.meta.iter().zip(&other.meta).all(|(a, b)| same(a, b))
230            && self.halted == other.halted
231            && self
232                .asides
233                .iter()
234                .filter(saved)
235                .eq(other.asides.iter().filter(saved))
236    }
237}
238
239/// A message's identity in its conversation: kept while entries around it
240/// are added, cut or replaced, while it is spliced back changed, across a
241/// save and a fork. Ids rise in the order messages were first made.
242#[derive(
243    Clone, Copy, Debug, Default, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize,
244)]
245#[serde(transparent)]
246pub struct MessageId(u64);
247
248impl MessageId {
249    /// Its number: ids rise from 0 in the order messages were first made.
250    pub const fn get(self) -> u64 {
251        self.0
252    }
253}
254
255/// Its plain form, `m` and its number (`m4`): how commands name a message.
256impl fmt::Display for MessageId {
257    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
258        write!(f, "m{}", self.0)
259    }
260}
261
262/// Reads its plain form, `m4`, or the number alone.
263impl FromStr for MessageId {
264    type Err = ParseIdError;
265
266    fn from_str(text: &str) -> Result<Self, ParseIdError> {
267        parse_id(text, 'm').map(Self)
268    }
269}
270
271/// A [`MessageId`] or [`AsideId`] that could not be read from its plain form.
272#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
273#[error("{0:?} is not an id")]
274pub struct ParseIdError(pub String);
275
276/// The number of `text`, written with or without `prefix`.
277fn parse_id(text: &str, prefix: char) -> Result<u64, ParseIdError> {
278    let number = text.strip_prefix(prefix).unwrap_or(text);
279    number.parse().map_err(|_| ParseIdError(text.to_owned()))
280}
281
282/// A message's identity beyond its conversation: when it was made and its
283/// id. Equal for a message and its copy in a fork (a fork copies ids and
284/// made-times), different for one made since, unless both were made in
285/// the same millisecond with the same id.
286#[derive(
287    Clone, Copy, Debug, Default, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize,
288)]
289pub struct MessageKey {
290    /// When it was first made, in milliseconds since the Unix epoch.
291    pub made: u64,
292    /// Its id in its conversation.
293    pub id: MessageId,
294}
295
296/// A message as it goes into a conversation: the message, who wrote it,
297/// and, for a message taken out with [`Conversation::entry`], its id,
298/// which a [`splice`](Conversation::splice) keeps. A recorded change
299/// always carries every id.
300#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
301pub struct Entry {
302    /// The message, shared with the conversation it goes into.
303    pub message: Arc<Message>,
304    /// Who wrote it; `None` for the user's own text, the model's reply and
305    /// tool results.
306    #[serde(default, skip_serializing_if = "Option::is_none")]
307    pub author: Option<Author>,
308    /// Its id in the conversation, if it has one.
309    #[serde(default, skip_serializing_if = "Option::is_none")]
310    pub id: Option<MessageId>,
311    /// When it was first made, in milliseconds since the Unix epoch: set by
312    /// [`Conversation::entry`], kept by an entry put back as it was. A
313    /// recorded change carries it only for such an entry.
314    #[serde(default, skip_serializing_if = "Option::is_none")]
315    pub made: Option<u64>,
316    /// What the tool calls its results answer published, for a view to
317    /// draw them from; saved with it, never sent to a model.
318    #[serde(default, skip_serializing_if = "ResultFacts::is_empty")]
319    pub facts: ResultFacts,
320}
321
322impl Entry {
323    /// A new entry without an author.
324    pub fn new(message: impl Into<Arc<Message>>) -> Self {
325        Self {
326            message: message.into(),
327            author: None,
328            id: None,
329            made: None,
330            facts: ResultFacts::default(),
331        }
332    }
333
334    /// This entry, with what the calls its results answer published.
335    #[must_use]
336    pub fn with_facts(self, facts: ResultFacts) -> Self {
337        Self { facts, ..self }
338    }
339
340    /// Whether it is the [`STOPPED`] note, as
341    /// [`EntryRef::is_stop_marker`].
342    pub fn is_stop_marker(&self) -> bool {
343        is_stop_marker(&self.message, self.author.as_ref())
344    }
345
346    /// This entry, written by `author`.
347    #[must_use]
348    pub fn by(self, author: Author) -> Self {
349        Self {
350            author: Some(author),
351            ..self
352        }
353    }
354}
355
356impl From<Message> for Entry {
357    fn from(message: Message) -> Self {
358        Self::new(message)
359    }
360}
361
362impl From<Arc<Message>> for Entry {
363    fn from(message: Arc<Message>) -> Self {
364        Self::new(message)
365    }
366}
367
368/// Entry `index` of a conversation, borrowed.
369#[derive(Clone, Copy, Debug)]
370pub struct EntryRef<'c> {
371    /// Where it is.
372    pub index: usize,
373    /// Its id.
374    pub id: MessageId,
375    /// Its message.
376    pub message: &'c Message,
377    /// Who wrote it, when it is not the user's own or the model's.
378    pub author: Option<&'c Author>,
379    /// When it was first made, in milliseconds since the Unix epoch.
380    pub made: u64,
381    /// What the tool calls its results answer published.
382    pub facts: &'c ResultFacts,
383}
384
385impl EntryRef<'_> {
386    /// Its identity beyond its conversation.
387    pub fn key(&self) -> MessageKey {
388        MessageKey {
389            made: self.made,
390            id: self.id,
391        }
392    }
393
394    /// Whether it is a user message the user typed: text or attachments,
395    /// not only tool results, with no author or [`AuthorKind::User`] with
396    /// no title.
397    pub fn is_users_own(&self) -> bool {
398        self.says_something()
399            && self
400                .author
401                .is_none_or(|author| author.kind == AuthorKind::User && author.title.is_none())
402    }
403
404    /// Whether it asks something of the model: a user message with text
405    /// or attachments, not only tool results, that is not rig's own (the
406    /// [`STOPPED`] note). The user's, an agent's or a plugin's.
407    pub fn is_request(&self) -> bool {
408        self.says_something()
409            && self
410                .author
411                .is_none_or(|author| author.kind != AuthorKind::Rig)
412    }
413
414    /// Whether it is a user message with text or attachments, not only
415    /// tool results.
416    fn says_something(&self) -> bool {
417        match self.message {
418            Message::User { content } => content.iter().any(|item| !pairing::is_result(item)),
419            _ => false,
420        }
421    }
422
423    /// Whether it is the [`STOPPED`] note rig puts between a request the
424    /// user stopped and what came next.
425    pub fn is_stop_marker(&self) -> bool {
426        is_stop_marker(self.message, self.author)
427    }
428}
429
430/// Whether `message` by `author` is the [`STOPPED`] note.
431fn is_stop_marker(message: &Message, author: Option<&Author>) -> bool {
432    let by_rig = author.is_some_and(|author| author.kind == AuthorKind::Rig);
433    by_rig
434        && matches!(message, Message::User { content }
435            if matches!(content.as_slice(), [UserContent::Text(text)] if text.text == STOPPED))
436}
437
438/// The text of the entry that goes between a request the user stopped and
439/// the next entry, so the model does not carry the request out. rig pushes
440/// it as its own entry, by [`Author::rig`].
441pub const STOPPED: &str = "[The user stopped the request above before it was fully answered; \
442                           any reply to it above was cut off there. \
443                           Do not carry it out unless asked again.]";
444
445/// Why the user's last message is left without an answer, so a restore
446/// does not answer it. How a turn ended is its [`TurnRecord`].
447#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
448#[serde(rename_all = "snake_case")]
449pub enum Halt {
450    /// The user stopped the turn answering it: the next entry pushed goes
451    /// after [`STOPPED`].
452    Stopped,
453    /// It is left for the next turn: a note to an idle agent, a request a
454    /// plugin stopped, or another author's message a failed turn left.
455    #[default]
456    Kept,
457}
458
459/// One edit of a conversation. Its serde form is the conversation part of
460/// the saved format.
461#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
462#[serde(tag = "type", rename_all = "snake_case")]
463pub enum Change {
464    /// Entries added at the end, each with its id. It clears the halt.
465    Push {
466        /// The entries.
467        entries: Vec<Entry>,
468    },
469    /// Entries `from..to`, whose ids were `removed`, replaced by `with`
470    /// (each with its id). `removed` doubles as a check: applying it where
471    /// the range holds other ids fails. One that reaches the end clears the
472    /// halt.
473    Splice {
474        /// The first entry replaced.
475        from: usize,
476        /// The end of the range replaced.
477        to: usize,
478        /// The ids of entries `from..to` before the splice.
479        removed: Vec<MessageId>,
480        /// What replaces them.
481        with: Vec<Entry>,
482    },
483    /// The halt set, or with `None` cleared.
484    Halt {
485        /// The halt.
486        halt: Option<Halt>,
487    },
488    /// Aside `id` put or replaced (`Some`), or removed (`None`).
489    Aside {
490        /// The aside's id.
491        id: AsideId,
492        /// The aside.
493        aside: Option<Aside>,
494    },
495    /// The whole value replaced: a component inserted over another, or a
496    /// conversation built elsewhere and saved onto a log it was not read
497    /// from.
498    Reset {
499        /// The new value.
500        state: Box<Conversation>,
501    },
502}
503
504/// A change as kept in the outbox and saved: who made it and when.
505#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
506pub struct ChangeRecord {
507    /// The change.
508    #[serde(flatten)]
509    pub change: Change,
510    /// Who made it: a push's entry author, a splice's `by`, an aside's
511    /// author; `None` for rig's own.
512    #[serde(default, skip_serializing_if = "Option::is_none")]
513    pub by: Option<Author>,
514    /// Milliseconds since the Unix epoch; the writer stamps it when `None`.
515    #[serde(default, skip_serializing_if = "Option::is_none")]
516    pub at: Option<u64>,
517}
518
519/// What a splice changed.
520#[derive(Clone, Debug, Default, PartialEq, Eq)]
521pub struct Spliced {
522    /// The ids no longer in the conversation.
523    pub removed: Vec<MessageId>,
524    /// The ids of the entries it put in, kept, put back or new.
525    pub changed: Vec<MessageId>,
526    /// The ids [`restore`](Conversation::restore) put back.
527    pub restored: Vec<MessageId>,
528}
529
530/// Why a recorded change could not be applied: it does not fit the
531/// conversation, such as a splice of a range holding other ids.
532#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
533pub enum ApplyError {
534    /// The change does not match the conversation.
535    #[error("{0}")]
536    Mismatch(String),
537}
538
539fn mismatch(why: String) -> ApplyError {
540    ApplyError::Mismatch(why)
541}
542
543/// The first characters of the agent id `id`, enough to tell agents apart.
544pub fn short_id(id: &str) -> &str {
545    id.get(..8).unwrap_or(id)
546}
547
548impl Conversation {
549    /// An empty conversation.
550    pub fn new() -> Self {
551        Self::default()
552    }
553
554    /// A conversation of `messages`, each its own entry, recorded so that
555    /// saving it writes them (an import, a library user's history).
556    pub fn from_messages(messages: impl IntoIterator<Item = impl Into<Arc<Message>>>) -> Self {
557        let mut conversation = Self::new();
558        conversation.extend(messages);
559        conversation
560    }
561
562    // Reading.
563
564    /// The messages, oldest first: what a request sends.
565    pub fn messages(&self) -> &[Arc<Message>] {
566        &self.messages
567    }
568
569    /// The messages, oldest first, taken out of the conversation: what a
570    /// request sends, without a copy.
571    pub fn into_messages(self) -> Vec<Arc<Message>> {
572        self.messages
573    }
574
575    /// The entries, oldest first.
576    pub fn entries(&self) -> impl DoubleEndedIterator<Item = EntryRef<'_>> + ExactSizeIterator {
577        let entries = self.messages.iter().zip(&self.meta).enumerate();
578        entries.map(|(index, (message, meta))| EntryRef {
579            index,
580            id: meta.id,
581            message,
582            author: meta.author.as_ref(),
583            made: meta.made,
584            facts: &meta.facts,
585        })
586    }
587
588    /// Entry `at`, with its author, id and when it was made, to splice
589    /// back changed.
590    pub fn entry(&self, at: usize) -> Option<Entry> {
591        let meta = self.meta.get(at)?;
592        Some(Entry {
593            message: self.messages.get(at)?.clone(),
594            author: meta.author.clone(),
595            id: Some(meta.id),
596            made: Some(meta.made),
597            facts: meta.facts.clone(),
598        })
599    }
600
601    /// The id of entry `at`.
602    pub fn id(&self, at: usize) -> Option<MessageId> {
603        self.meta.get(at).map(|meta| meta.id)
604    }
605
606    /// The identity of entry `at` beyond this conversation.
607    pub fn key(&self, at: usize) -> Option<MessageKey> {
608        let meta = self.meta.get(at)?;
609        Some(MessageKey {
610            made: meta.made,
611            id: meta.id,
612        })
613    }
614
615    /// Where the entry with identity `key` is now; `None` when it is not
616    /// here, also when an entry with its id was made at another time.
617    pub fn index_of_key(&self, key: MessageKey) -> Option<usize> {
618        let at = self.index_of(key.id)?;
619        (self.meta.get(at)?.made == key.made).then_some(at)
620    }
621
622    /// Who wrote entry `at`; `None` for the user's own text, the model's
623    /// reply, a tool result, or no such entry.
624    pub fn author(&self, at: usize) -> Option<&Author> {
625        self.meta.get(at)?.author.as_ref()
626    }
627
628    /// Where entry `id` is now; `None` once an edit took it out.
629    pub fn index_of(&self, id: MessageId) -> Option<usize> {
630        self.meta.iter().position(|meta| meta.id == id)
631    }
632
633    /// The id the next entry made gets. Every id below it was given out
634    /// before, here or in the conversation this one was copied from.
635    pub fn next_id(&self) -> MessageId {
636        MessageId(self.next_id)
637    }
638
639    /// Where a span that began at entry `id` begins now, such as a turn:
640    /// its index while it is there; the end for an entry not made yet; 0
641    /// for one an edit took out, as a summary then stands for what came
642    /// before it.
643    pub fn start_of(&self, id: MessageId) -> usize {
644        self.index_of(id).unwrap_or(if id.0 >= self.next_id {
645            self.messages.len()
646        } else {
647            0
648        })
649    }
650
651    /// Where a turn starting now begins: the first of the user messages at
652    /// the end, which it answers, else the first entry it adds.
653    pub fn turn_start(&self) -> MessageId {
654        let trailing = self.messages.iter().rev();
655        let trailing = trailing
656            .take_while(|message| matches!(&***message, Message::User { .. }))
657            .count();
658        let first = self.messages.len().saturating_sub(trailing);
659        let answered = (trailing > 0).then(|| self.id(first)).flatten();
660        answered.unwrap_or(MessageId(self.next_id))
661    }
662
663    /// The entries a turn that began at `start` (its
664    /// [`turn_start`](Self::turn_start)) answers: the user messages in a
665    /// row from where it begins now ([`start_of`](Self::start_of)). After a
666    /// stopped turn they begin with that turn's tool results and the
667    /// [`STOPPED`] note, before what was sent next.
668    pub fn asked(&self, start: MessageId) -> impl Iterator<Item = EntryRef<'_>> {
669        let entries = self.entries().skip(self.start_of(start));
670        entries.take_while(|entry| matches!(entry.message, Message::User { .. }))
671    }
672
673    /// The message that asked for the turn that began at `start`: the
674    /// first of the entries it answers ([`asked`](Self::asked)) that is a
675    /// request ([`EntryRef::is_request`]).
676    pub fn request(&self, start: MessageId) -> Option<EntryRef<'_>> {
677        self.asked(start).find(EntryRef::is_request)
678    }
679
680    /// Why the user's last message is left unanswered, if it was halted.
681    /// Cleared when an entry is pushed or a splice reaches the end.
682    pub fn halted(&self) -> Option<Halt> {
683        self.halted
684    }
685
686    /// Whether the model owes an answer: the last message a model reads is
687    /// the user's, and it was not halted. A failed or stopped reply after it
688    /// is no answer ([`StopReason::is_failure`]), so the answer is still
689    /// owed.
690    pub fn awaits_model(&self) -> bool {
691        let read = self.messages.iter().rev().map(Arc::as_ref).find(|message| {
692            !matches!(message, Message::Assistant(turn)
693                if turn.stop.as_ref().is_some_and(StopReason::is_failure))
694        });
695        self.halted.is_none() && matches!(read, Some(Message::User { .. }))
696    }
697
698    /// The tool calls of the last assistant message that nothing answers
699    /// yet, each with its [`CallRef`]. See [`pairing::pending_calls`].
700    pub fn pending_calls(&self) -> Vec<(CallRef, ToolCall)> {
701        let Some((at, calls)) = pairing::pending(&self.messages) else {
702            return Vec::new();
703        };
704        let Some(reply) = self.id(at) else {
705            return Vec::new();
706        };
707        let calls = calls.into_iter();
708        calls
709            .map(|(index, call)| (CallRef { reply, index }, call.clone()))
710            .collect()
711    }
712
713    /// Whether the messages pair every tool call with its result. See
714    /// [`pairing::validate`].
715    pub fn validate(&self) -> Result<(), PairingError> {
716        pairing::validate(&self.messages)
717    }
718
719    /// The asides, in the order put.
720    pub fn asides(&self) -> impl DoubleEndedIterator<Item = (AsideId, &Aside)> {
721        self.asides.iter().map(|(id, aside)| (*id, aside))
722    }
723
724    /// Aside `id`.
725    pub fn aside(&self, id: AsideId) -> Option<&Aside> {
726        let mut asides = self.asides.iter();
727        asides
728            .find(|(known, _)| *known == id)
729            .map(|(_, aside)| aside)
730    }
731
732    // Editing: each builds a change with every id filled in, applies it and
733    // records it.
734
735    /// Pushes `entry`, after a [`STOPPED`] entry by [`Author::rig`] in the
736    /// same change when the user stopped the last request; a halt is
737    /// cleared. Returns the new entry's id; a pushed entry never reuses one.
738    pub fn push(&mut self, entry: impl Into<Entry>) -> MessageId {
739        let entry = entry.into();
740        let by = entry.author.clone();
741        let mut ids = self.push_entries(vec![entry], by);
742        ids.pop().unwrap_or(MessageId(self.next_id))
743    }
744
745    /// Pushes each of `messages` as its own entry without an author, in one
746    /// change, as [`push`](Self::push) does.
747    pub fn extend(&mut self, messages: impl IntoIterator<Item = impl Into<Arc<Message>>>) {
748        let entries = messages.into_iter().map(Entry::new).collect();
749        self.push_entries(entries, None);
750    }
751
752    fn push_entries(&mut self, entries: Vec<Entry>, by: Option<Author>) -> Vec<MessageId> {
753        if entries.is_empty() {
754            return Vec::new();
755        }
756        let stop = (self.halted == Some(Halt::Stopped))
757            .then(|| Entry::new(Message::user(STOPPED)).by(Author::rig()));
758        let mut next = self.next_id;
759        let mut ids = Vec::with_capacity(entries.len());
760        let mut fill = |mut entry: Entry| {
761            let id = MessageId(next);
762            next = next.saturating_add(1);
763            entry.id = Some(id);
764            entry.made = None;
765            (entry, id)
766        };
767        let stop = stop.map(|entry| fill(entry).0);
768        let entries = entries.into_iter().map(|entry| {
769            let (entry, id) = fill(entry);
770            ids.push(id);
771            entry
772        });
773        let entries = stop.into_iter().chain(entries).collect();
774        self.record(Change::Push { entries }, by);
775        ids
776    }
777
778    /// Replaces entries in `range`, clamped to the conversation, with
779    /// `with`, recorded as made by `by`. An entry of `with` keeps its id
780    /// when that id was in the range and no earlier entry of `with` kept
781    /// it; any other gets a new id. Nothing merges. A splice reaching the
782    /// end clears the halt. An empty range replaced by nothing changes and
783    /// records nothing. A provider's prompt cache is lost from the first
784    /// entry replaced on, so a splice before the end costs the requests
785    /// after it.
786    pub fn splice(
787        &mut self,
788        range: impl RangeBounds<usize>,
789        with: impl IntoIterator<Item = Entry>,
790        by: Author,
791    ) -> Spliced {
792        self.replace(range, with.into_iter().collect(), by, false)
793    }
794
795    /// As [`splice`](Self::splice), and an entry of `with` whose id this
796    /// conversation made (below the next id), that no entry outside the
797    /// range holds and no earlier entry of `with` took, keeps that id and
798    /// when it was made ([`Entry::made`], else now): entries put back as
799    /// they were, such as a summary's originals or an edit undone. Asides that followed such an entry follow it again.
800    /// Only for entries this conversation held: an entry from elsewhere
801    /// that carries an id would take one that meant another message here.
802    ///
803    /// ```
804    /// use rig_core::completion::Message;
805    /// use rig_core::conversation::{Author, Conversation, Entry};
806    ///
807    /// let mut conversation = Conversation::from_messages([
808    ///     Message::user("one"),
809    ///     Message::assistant("two"),
810    /// ]);
811    /// let ids: Vec<_> = conversation.entries().map(|entry| entry.id).collect();
812    /// let originals: Vec<Entry> = (0..2).filter_map(|at| conversation.entry(at)).collect();
813    /// let summary = Entry::new(Message::user("a summary"));
814    /// conversation.splice(.., [summary], Author::plugin("compact"));
815    /// let undone = conversation.restore(.., originals, Author::plugin("undo"));
816    /// assert_eq!(undone.restored, ids);
817    /// assert!(conversation.entries().map(|entry| entry.id).eq(ids));
818    /// ```
819    pub fn restore(
820        &mut self,
821        range: impl RangeBounds<usize>,
822        with: impl IntoIterator<Item = Entry>,
823        by: Author,
824    ) -> Spliced {
825        self.replace(range, with.into_iter().collect(), by, true)
826    }
827
828    /// Makes the conversation hold `entries`, as made by `by`: one
829    /// [`restore`](Self::restore) of the range between the longest start
830    /// and end it shares with them (the same messages, ids and authors), so
831    /// entries taken from it keep their ids. Nothing when they are equal.
832    pub fn set_entries(&mut self, entries: Vec<Entry>, by: Author) -> Spliced {
833        let same = |entry: &Entry, at: usize| {
834            entry.id.is_some()
835                && entry.id == self.id(at)
836                && entry.author.as_ref() == self.author(at)
837                && Some(&entry.message) == self.messages.get(at)
838                && Some(&entry.facts) == self.meta.get(at).map(|meta| &meta.facts)
839        };
840        let (len, count) = (self.messages.len(), entries.len());
841        let start = entries
842            .iter()
843            .enumerate()
844            .take_while(|(at, entry)| same(entry, *at))
845            .count();
846        let end = entries
847            .iter()
848            .rev()
849            .zip((0..len).rev())
850            .take(len.min(count).saturating_sub(start))
851            .take_while(|(entry, at)| same(entry, *at))
852            .count();
853        if start == len && start == count {
854            return Spliced::default();
855        }
856        let with = entries
857            .into_iter()
858            .skip(start)
859            .take(count.saturating_sub(start).saturating_sub(end));
860        self.restore(start..len.saturating_sub(end), with, by)
861    }
862
863    /// Replaces entries in `range` with `with`: [`splice`](Self::splice),
864    /// or with `restores`, [`restore`](Self::restore).
865    fn replace(
866        &mut self,
867        range: impl RangeBounds<usize>,
868        mut with: Vec<Entry>,
869        by: Author,
870        restores: bool,
871    ) -> Spliced {
872        let len = self.messages.len();
873        let to = match range.end_bound() {
874            Bound::Included(&end) => end.saturating_add(1),
875            Bound::Excluded(&end) => end,
876            Bound::Unbounded => len,
877        }
878        .min(len);
879        let from = match range.start_bound() {
880            Bound::Included(&start) => start,
881            Bound::Excluded(&start) => start.saturating_add(1),
882            Bound::Unbounded => 0,
883        }
884        .min(to);
885        if from == to && with.is_empty() {
886            return Spliced::default();
887        }
888        let replaced = self.meta.get(from..to).unwrap_or_default();
889        let removed: Vec<MessageId> = replaced.iter().map(|meta| meta.id).collect();
890        let in_range: HashSet<MessageId> = removed.iter().copied().collect();
891        let mut outside = None;
892        let mut taken = HashSet::new();
893        let mut restored = Vec::new();
894        let mut next = self.next_id;
895        for entry in &mut with {
896            let id = entry.id.filter(|id| !taken.contains(id));
897            if let Some(id) = id.filter(|id| in_range.contains(id)) {
898                taken.insert(id);
899                entry.made = None;
900                continue;
901            }
902            let back = id.filter(|id| {
903                restores
904                    && id.0 < self.next_id
905                    && !self.outside(from..to, &mut outside).contains(id)
906            });
907            if let Some(id) = back {
908                taken.insert(id);
909                restored.push(id);
910                continue;
911            }
912            entry.id = Some(MessageId(next));
913            entry.made = None;
914            next = next.saturating_add(1);
915        }
916        let changed = with.iter().filter_map(|entry| entry.id).collect();
917        let gone = removed.iter().filter(|id| !taken.contains(id)).copied();
918        let spliced = Spliced {
919            removed: gone.collect(),
920            changed,
921            restored,
922        };
923        let change = Change::Splice {
924            from,
925            to,
926            removed,
927            with,
928        };
929        self.record(change, Some(by));
930        spliced
931    }
932
933    /// The ids of the entries outside `range`, gathered into `outside` the
934    /// first time they are asked for.
935    fn outside<'s>(
936        &self,
937        range: Range<usize>,
938        outside: &'s mut Option<HashSet<MessageId>>,
939    ) -> &'s HashSet<MessageId> {
940        outside.get_or_insert_with(|| {
941            let before = self.meta.get(..range.start).unwrap_or_default();
942            let after = self.meta.get(range.end..).unwrap_or_default();
943            before.iter().chain(after).map(|meta| meta.id).collect()
944        })
945    }
946
947    /// Rewrites entries in place, as made by `by`: `edit` sees each entry,
948    /// oldest first, and returns the message to put in its place, or
949    /// `None` to leave it. The entries it rewrote keep their ids and
950    /// authors, and the whole edit is one change: a [`splice`](Self::splice)
951    /// of the entries from the first rewritten to the last. Nothing is
952    /// recorded when it rewrote none. Returns the ids of the entries it
953    /// rewrote.
954    ///
955    /// ```
956    /// use rig_core::completion::Message;
957    /// use rig_core::conversation::{Author, Conversation};
958    ///
959    /// let mut conversation = Conversation::from_messages([
960    ///     Message::user("one"),
961    ///     Message::user("two"),
962    /// ]);
963    /// let before = conversation.id(1);
964    /// let changed = conversation.edit_each(Author::plugin("shout"), |entry| {
965    ///     (entry.index == 1).then(|| Message::user("TWO"))
966    /// });
967    /// assert_eq!(changed, before.into_iter().collect::<Vec<_>>());
968    /// assert_eq!(conversation.messages().get(1).map(|message| &**message), Some(&Message::user("TWO")));
969    /// assert_eq!(conversation.id(1), before);
970    /// ```
971    pub fn edit_each(
972        &mut self,
973        by: Author,
974        mut edit: impl FnMut(EntryRef<'_>) -> Option<Message>,
975    ) -> Vec<MessageId> {
976        let rewritten: Vec<(usize, MessageId, Message)> = self
977            .entries()
978            .filter_map(|entry| {
979                let (at, id) = (entry.index, entry.id);
980                edit(entry).map(|message| (at, id, message))
981            })
982            .collect();
983        let (Some(&(first, ..)), Some(&(last, ..))) = (rewritten.first(), rewritten.last()) else {
984            return Vec::new();
985        };
986        let ids = rewritten.iter().map(|(_, id, _)| *id).collect();
987        let mut rewritten = rewritten.into_iter().peekable();
988        let entries: Vec<Entry> = (first..=last)
989            .filter_map(|at| match rewritten.next_if(|(next, ..)| *next == at) {
990                Some((_, id, message)) => Some(Entry {
991                    message: Arc::new(message),
992                    author: self.author(at).cloned(),
993                    id: Some(id),
994                    made: None,
995                    facts: self
996                        .meta
997                        .get(at)
998                        .map(|meta| meta.facts.clone())
999                        .unwrap_or_default(),
1000                }),
1001                None => self.entry(at),
1002            })
1003            .collect();
1004        self.splice(first..=last, entries, by);
1005        ids
1006    }
1007
1008    /// Repairs the entries as [`pairing::normalize`] does, saved with
1009    /// [`set_entries`](Self::set_entries) as made by `by`, so merged
1010    /// entries keep the first's id, author and made-time. An aside that
1011    /// followed an entry merged into another follows that one; one that
1012    /// followed a dropped entry follows the entry before it (each move
1013    /// recorded, by `by`). Returns what it repaired.
1014    pub fn normalize(&mut self, by: Author) -> Normalized {
1015        let entries = (0..self.messages.len()).filter_map(|at| self.entry(at));
1016        let normalized = pairing::normalize(entries.collect());
1017        let into: HashMap<MessageId, MessageId> = normalized
1018            .merged
1019            .iter()
1020            .map(|(kept, gone)| (*gone, *kept))
1021            .collect();
1022        let dropped: HashSet<MessageId> = normalized.dropped.iter().copied().collect();
1023        // Where an aside that followed `id` goes: the entry it went into,
1024        // or for a dropped one, the entry before it that stays.
1025        let anchor = |id: MessageId| -> Option<MessageId> {
1026            let before = self.meta.iter().rev().skip_while(|meta| meta.id != id);
1027            before
1028                .map(|meta| meta.id)
1029                .find_map(|id| match into.get(&id) {
1030                    Some(kept) => Some(*kept),
1031                    None => (!dropped.contains(&id)).then_some(id),
1032                })
1033        };
1034        let moves: Vec<(AsideId, Option<MessageId>)> = self
1035            .asides
1036            .iter()
1037            .filter_map(|(at, aside)| {
1038                let after = aside.after?;
1039                let moves = into.contains_key(&after) || dropped.contains(&after);
1040                moves.then(|| (*at, anchor(after)))
1041            })
1042            .collect();
1043        self.set_entries(normalized.entries.clone(), by.clone());
1044        for (id, after) in moves {
1045            self.move_aside(id, after, &by);
1046        }
1047        normalized
1048    }
1049
1050    /// Leaves the user's last message unanswered, for `halt`. Whether it
1051    /// was halted now: not when the model owes no answer.
1052    pub fn halt(&mut self, halt: Halt) -> bool {
1053        let halts = self.awaits_model();
1054        if halts {
1055            self.record(Change::Halt { halt: Some(halt) }, None);
1056        }
1057        halts
1058    }
1059
1060    /// Puts `aside` after the asides already put and returns its id. An
1061    /// unsaved aside is not recorded.
1062    pub fn add_aside(&mut self, aside: Aside) -> AsideId {
1063        let id = AsideId(self.next_aside);
1064        if aside.saved {
1065            let by = Some(aside.author.clone());
1066            let aside = Some(aside);
1067            self.record(Change::Aside { id, aside }, by);
1068        } else {
1069            self.place_aside(id, aside);
1070        }
1071        id
1072    }
1073
1074    /// Replaces aside `id` with `aside`, in its place; whether there was
1075    /// one. Replacing a saved aside with an unsaved one records its
1076    /// removal.
1077    pub fn replace_aside(&mut self, id: AsideId, aside: Aside) -> bool {
1078        let Some(was_saved) = self.aside(id).map(|old| old.saved) else {
1079            return false;
1080        };
1081        if aside.saved {
1082            let by = Some(aside.author.clone());
1083            let aside = Some(aside);
1084            self.record(Change::Aside { id, aside }, by);
1085        } else {
1086            // The saved value loses it; the live one keeps it in its place.
1087            self.place_aside(id, aside);
1088            if was_saved {
1089                self.log(Change::Aside { id, aside: None }, None);
1090            }
1091        }
1092        true
1093    }
1094
1095    /// Removes aside `id` and returns it, or `None` if there was none.
1096    pub fn remove_aside(&mut self, id: AsideId) -> Option<Aside> {
1097        let at = self.asides.iter().position(|(known, _)| *known == id)?;
1098        let (_, aside) = self.asides.remove(at);
1099        if aside.saved {
1100            self.log(Change::Aside { id, aside: None }, None);
1101        }
1102        Some(aside)
1103    }
1104
1105    /// Makes aside `id` follow `after`, recorded as made by `by` when it is
1106    /// saved.
1107    fn move_aside(&mut self, id: AsideId, after: Option<MessageId>, by: &Author) {
1108        let Some(aside) = self.aside(id).cloned() else {
1109            return;
1110        };
1111        let aside = aside.after(after);
1112        if aside.saved {
1113            let aside = Some(aside);
1114            self.record(Change::Aside { id, aside }, Some(by.clone()));
1115        } else {
1116            self.place_aside(id, aside);
1117        }
1118    }
1119
1120    /// Puts `aside` as `id` without recording it: in place of the aside
1121    /// with that id, else last.
1122    fn place_aside(&mut self, id: AsideId, aside: Aside) {
1123        self.next_aside = self.next_aside.max(id.0.saturating_add(1));
1124        match self.asides.iter_mut().find(|(known, _)| *known == id) {
1125            Some((_, slot)) => *slot = aside,
1126            None => self.asides.push((id, aside)),
1127        }
1128    }
1129
1130    // The record.
1131
1132    /// Applies a recorded change verbatim, such as one read from a log or
1133    /// sent by a process that mirrors this conversation. It is not put in
1134    /// the outbox. Fails, changing nothing, when it does not fit.
1135    pub fn apply(&mut self, change: &ChangeRecord) -> Result<(), ApplyError> {
1136        let at = change.at.unwrap_or_else(|| self.now());
1137        self.change(&change.change, at)?;
1138        self.revision = self.revision.saturating_add(1);
1139        Ok(())
1140    }
1141
1142    /// Makes the edits of `edit` as made at `at`, in milliseconds since the
1143    /// Unix epoch, such as messages imported at the times their source
1144    /// logged them: their records carry that time, which a writer keeps,
1145    /// and the entries they make were made then. An edit dated inside, by a
1146    /// nested call, keeps its own time.
1147    ///
1148    /// ```
1149    /// use rig_core::conversation::Conversation;
1150    /// use rig_core::message::Message;
1151    ///
1152    /// let mut conversation = Conversation::new();
1153    /// conversation.dated(1_790_848_800_000, |conversation| {
1154    ///     conversation.push(Message::user("Imported"))
1155    /// });
1156    /// let at = conversation.unsaved().first().and_then(|recorded| recorded.at);
1157    /// assert_eq!(at, Some(1_790_848_800_000));
1158    /// ```
1159    pub fn dated<R>(&mut self, at: u64, edit: impl FnOnce(&mut Self) -> R) -> R {
1160        let outer = self.clock.replace(at);
1161        let made = edit(self);
1162        self.clock = outer;
1163        made
1164    }
1165
1166    /// The time an edit is made at: the [`dated`](Self::dated) clock, else
1167    /// now.
1168    fn now(&self) -> u64 {
1169        self.clock.unwrap_or_else(crate::now_ms)
1170    }
1171
1172    /// The changes made that nobody has saved yet, oldest first.
1173    pub fn unsaved(&self) -> &[ChangeRecord] {
1174        &self.unsaved
1175    }
1176
1177    /// Takes the changes made that nobody has saved yet, to save them.
1178    pub fn take_unsaved(&mut self) -> Vec<ChangeRecord> {
1179        std::mem::take(&mut self.unsaved)
1180    }
1181
1182    /// The changes behind this value, one per record: those of the log it
1183    /// continues ([`lineage`](Self::lineage)) when it was last loaded or
1184    /// saved, then each applied or made since. An unsaved aside counts
1185    /// none.
1186    pub fn revision(&self) -> u64 {
1187        self.revision
1188    }
1189
1190    /// The saved log this value continues: [`Lineage::EMPTY`] when it was
1191    /// begun here from nothing and never saved, [`Lineage::DETACHED`] when
1192    /// it was read back from its serde form.
1193    pub fn lineage(&self) -> Lineage {
1194        self.lineage
1195    }
1196
1197    /// Whether this value's unsaved changes, appended to the log of
1198    /// `lineage` that holds `changes` changes, give this value: it
1199    /// continues that log, holding all of its changes and since then only
1200    /// its unsaved ones. A value begun here from nothing continues any
1201    /// empty log.
1202    pub fn continues(&self, lineage: Lineage, changes: u64) -> bool {
1203        let base = self.revision.saturating_sub(self.unsaved.len() as u64);
1204        base == changes
1205            && (self.lineage == lineage || (changes == 0 && self.lineage == Lineage::EMPTY))
1206    }
1207
1208    /// Marks this value as holding the `changes` changes of the log of
1209    /// `lineage`, then its unsaved ones: what a store does once it loaded
1210    /// the value from that log or saved it there.
1211    pub fn continue_log(&mut self, lineage: Lineage, changes: u64) {
1212        self.lineage = lineage;
1213        self.revision = changes.saturating_add(self.unsaved.len() as u64);
1214    }
1215
1216    /// A copy with an empty outbox, for edits never saved (a preview, a
1217    /// reset's state).
1218    pub fn view(&self) -> Self {
1219        Self {
1220            asides: self.asides.clone(),
1221            ..self.request_view()
1222        }
1223    }
1224
1225    /// A [`view`](Self::view) without the asides, for a model request's
1226    /// copy: a request never sends them, and one is built per model call.
1227    pub fn request_view(&self) -> Self {
1228        Self {
1229            messages: self.messages.clone(),
1230            meta: self.meta.clone(),
1231            asides: Vec::new(),
1232            halted: self.halted,
1233            next_id: self.next_id,
1234            next_aside: self.next_aside,
1235            revision: self.revision,
1236            lineage: self.lineage,
1237            unsaved: Vec::new(),
1238            clock: None,
1239        }
1240    }
1241
1242    /// Applies `change`, built live so it fits, as made now, and records it.
1243    fn record(&mut self, change: Change, by: Option<Author>) {
1244        let at = self.now();
1245        match self.change(&change, at) {
1246            Ok(()) => self.log_at(change, by, at),
1247            Err(error) => tracing::error!(%error, "a conversation edit did not fit; dropped"),
1248        }
1249    }
1250
1251    /// Records `change`, already applied, as made now.
1252    fn log(&mut self, change: Change, by: Option<Author>) {
1253        let at = self.now();
1254        self.log_at(change, by, at);
1255    }
1256
1257    fn log_at(&mut self, change: Change, by: Option<Author>, at: u64) {
1258        self.revision = self.revision.saturating_add(1);
1259        self.unsaved.push(ChangeRecord {
1260            change,
1261            by,
1262            at: Some(at),
1263        });
1264    }
1265
1266    /// Applies `change`, made at `at`, taking its ids verbatim, after
1267    /// checking it fits. An entry that keeps its id keeps when it was made;
1268    /// any other was made when its record says, else at `at`.
1269    fn change(&mut self, change: &Change, at: u64) -> Result<(), ApplyError> {
1270        let meta = |entry: &Entry, made: u64| Meta {
1271            id: entry.id.unwrap_or_default(),
1272            author: entry.author.clone(),
1273            made,
1274            facts: entry.facts.clone(),
1275        };
1276        match change {
1277            Change::Push { entries } => {
1278                let end = self.meta.len();
1279                let next = self.new_ids(entries, &HashSet::new(), end..end)?;
1280                for entry in entries {
1281                    self.messages.push(entry.message.clone());
1282                    self.meta.push(meta(entry, entry.made.unwrap_or(at)));
1283                }
1284                self.next_id = next;
1285                self.halted = None;
1286            }
1287            Change::Splice {
1288                from,
1289                to,
1290                removed,
1291                with,
1292            } => {
1293                let (from, to) = (*from, *to);
1294                let reaches_end = to == self.meta.len();
1295                let replaced = self.meta.get(from..to).ok_or_else(|| {
1296                    mismatch(format!(
1297                        "splice of {from}..{to} in {} entries",
1298                        self.meta.len()
1299                    ))
1300                })?;
1301                if !replaced.iter().map(|meta| &meta.id).eq(removed) {
1302                    return Err(mismatch(format!("splice of {from}..{to} names other ids")));
1303                }
1304                let kept: HashMap<MessageId, u64> =
1305                    replaced.iter().map(|meta| (meta.id, meta.made)).collect();
1306                let next = self.new_ids(with, &removed.iter().copied().collect(), from..to)?;
1307                let metas: Vec<Meta> = with
1308                    .iter()
1309                    .map(|entry| {
1310                        let made = entry.id.and_then(|id| kept.get(&id).copied());
1311                        meta(entry, made.or(entry.made).unwrap_or(at))
1312                    })
1313                    .collect();
1314                self.messages
1315                    .splice(from..to, with.iter().map(|entry| entry.message.clone()));
1316                self.meta.splice(from..to, metas);
1317                self.next_id = next;
1318                if reaches_end {
1319                    self.halted = None;
1320                }
1321            }
1322            Change::Halt { halt } => self.halted = *halt,
1323            Change::Aside {
1324                id,
1325                aside: Some(aside),
1326            } => self.place_aside(*id, aside.clone()),
1327            Change::Aside { id, aside: None } => {
1328                let at = self.asides.iter().position(|(known, _)| known == id);
1329                let at = at.ok_or_else(|| mismatch(format!("no aside {}", id.0)))?;
1330                self.asides.remove(at);
1331            }
1332            // Exactly the new value, its next ids too: the live value goes
1333            // on numbering from them, so a fold must as well.
1334            Change::Reset { state } => {
1335                let (unsaved, revision) = (std::mem::take(&mut self.unsaved), self.revision);
1336                let lineage = self.lineage;
1337                *self = state.view();
1338                self.unsaved = unsaved;
1339                self.revision = revision;
1340                self.lineage = lineage;
1341            }
1342        }
1343        Ok(())
1344    }
1345
1346    /// Checks that each of `entries`, which replace `range`, has an id
1347    /// that is, at most once, one of `reused` or an earlier id no entry
1348    /// outside `range` holds (put back), or else new: rising from the next
1349    /// id. Returns the next id after them.
1350    fn new_ids(
1351        &self,
1352        entries: &[Entry],
1353        reused: &HashSet<MessageId>,
1354        range: Range<usize>,
1355    ) -> Result<u64, ApplyError> {
1356        let mut next = self.next_id;
1357        let mut seen = HashSet::new();
1358        let mut outside = None;
1359        for entry in entries {
1360            let id = entry
1361                .id
1362                .ok_or_else(|| mismatch("a recorded entry without an id".to_owned()))?;
1363            if id.0 >= next {
1364                next = id.0.saturating_add(1);
1365                continue;
1366            }
1367            let fits = reused.contains(&id)
1368                || (id.0 < self.next_id
1369                    && !self.outside(range.clone(), &mut outside).contains(&id));
1370            if !fits || !seen.insert(id) {
1371                return Err(mismatch(format!("message id {} reused", id.0)));
1372            }
1373        }
1374        Ok(next)
1375    }
1376}
1377
1378#[cfg(test)]
1379mod tests;