1/**
2 * Message branching utilities for conversation tree navigation.
3 *
4 * Conversation branching allows users to edit messages and create alternate paths
5 * while preserving the original conversation flow. Each message has parent/children
6 * relationships forming a tree structure.
7 *
8 * Example tree:
9 * root
10 * ├── message 1 (user)
11 * │ └── message 2 (assistant)
12 * │ ├── message 3 (user)
13 * │ └── message 6 (user) ← new branch
14 * └── message 4 (user)
15 * └── message 5 (assistant)
16 */
17
18/**
19 * Filters messages to get the conversation path from root to a specific leaf node.
20 * If the leafNodeId doesn't exist, returns the path with the latest timestamp.
21 *
22 * @param messages - All messages in the conversation
23 * @param leafNodeId - The target leaf node ID to trace back from
24 * @param includeRoot - Whether to include root messages in the result
25 * @returns Array of messages from root to leaf, sorted by timestamp
26 */
27export function filterByLeafNodeId(
28 messages: readonly DatabaseMessage[],
29 leafNodeId: string,
30 includeRoot: boolean = false
31): readonly DatabaseMessage[] {
32 const result: DatabaseMessage[] = [];
33 const nodeMap = new Map<string, DatabaseMessage>();
34
35 // Build node map for quick lookups
36 for (const msg of messages) {
37 nodeMap.set(msg.id, msg);
38 }
39
40 // Find the starting node (leaf node or latest if not found)
41 let startNode: DatabaseMessage | undefined = nodeMap.get(leafNodeId);
42 if (!startNode) {
43 // If leaf node not found, use the message with latest timestamp
44 let latestTime = -1;
45 for (const msg of messages) {
46 if (msg.timestamp > latestTime) {
47 startNode = msg;
48 latestTime = msg.timestamp;
49 }
50 }
51 }
52
53 // Traverse from leaf to root, collecting messages
54 let currentNode: DatabaseMessage | undefined = startNode;
55 while (currentNode) {
56 // Include message if it's not root, or if we want to include root
57 if (currentNode.type !== 'root' || includeRoot) {
58 result.push(currentNode);
59 }
60
61 // Stop traversal if parent is null (reached root)
62 if (currentNode.parent === null) {
63 break;
64 }
65 currentNode = nodeMap.get(currentNode.parent);
66 }
67
68 // Sort by timestamp to get chronological order (root to leaf)
69 result.sort((a, b) => a.timestamp - b.timestamp);
70 return result;
71}
72
73/**
74 * Finds the leaf node (message with no children) for a given message branch.
75 * Traverses down the tree following the last child until reaching a leaf.
76 *
77 * @param messages - All messages in the conversation
78 * @param messageId - Starting message ID to find leaf for
79 * @returns The leaf node ID, or the original messageId if no children
80 */
81export function findLeafNode(messages: readonly DatabaseMessage[], messageId: string): string {
82 const nodeMap = new Map<string, DatabaseMessage>();
83
84 // Build node map for quick lookups
85 for (const msg of messages) {
86 nodeMap.set(msg.id, msg);
87 }
88
89 let currentNode: DatabaseMessage | undefined = nodeMap.get(messageId);
90 while (currentNode && currentNode.children.length > 0) {
91 // Follow the last child (most recent branch)
92 const lastChildId = currentNode.children[currentNode.children.length - 1];
93 currentNode = nodeMap.get(lastChildId);
94 }
95
96 return currentNode?.id ?? messageId;
97}
98
99/**
100 * Finds all descendant messages (children, grandchildren, etc.) of a given message.
101 * This is used for cascading deletion to remove all messages in a branch.
102 *
103 * @param messages - All messages in the conversation
104 * @param messageId - The root message ID to find descendants for
105 * @returns Array of all descendant message IDs
106 */
107export function findDescendantMessages(
108 messages: readonly DatabaseMessage[],
109 messageId: string
110): string[] {
111 const nodeMap = new Map<string, DatabaseMessage>();
112
113 // Build node map for quick lookups
114 for (const msg of messages) {
115 nodeMap.set(msg.id, msg);
116 }
117
118 const descendants: string[] = [];
119 const queue: string[] = [messageId];
120
121 while (queue.length > 0) {
122 const currentId = queue.shift()!;
123 const currentNode = nodeMap.get(currentId);
124
125 if (currentNode) {
126 // Add all children to the queue and descendants list
127 for (const childId of currentNode.children) {
128 descendants.push(childId);
129 queue.push(childId);
130 }
131 }
132 }
133
134 return descendants;
135}
136
137/**
138 * Gets sibling information for a message, including all sibling IDs and current position.
139 * Siblings are messages that share the same parent.
140 *
141 * @param messages - All messages in the conversation
142 * @param messageId - The message to get sibling info for
143 * @returns Sibling information including leaf node IDs for navigation
144 */
145export function getMessageSiblings(
146 messages: readonly DatabaseMessage[],
147 messageId: string
148): ChatMessageSiblingInfo | null {
149 const nodeMap = new Map<string, DatabaseMessage>();
150
151 // Build node map for quick lookups
152 for (const msg of messages) {
153 nodeMap.set(msg.id, msg);
154 }
155
156 const message = nodeMap.get(messageId);
157 if (!message) {
158 return null;
159 }
160
161 // Handle null parent (root message) case
162 if (message.parent === null) {
163 // No parent means this is likely a root node with no siblings
164 return {
165 message,
166 siblingIds: [messageId],
167 currentIndex: 0,
168 totalSiblings: 1
169 };
170 }
171
172 const parentNode = nodeMap.get(message.parent);
173 if (!parentNode) {
174 // Parent not found - treat as single message
175 return {
176 message,
177 siblingIds: [messageId],
178 currentIndex: 0,
179 totalSiblings: 1
180 };
181 }
182
183 // Get all sibling IDs (including self)
184 const siblingIds = parentNode.children;
185
186 // Convert sibling message IDs to their corresponding leaf node IDs
187 // This allows navigation between different conversation branches
188 const siblingLeafIds = siblingIds.map((siblingId: string) => findLeafNode(messages, siblingId));
189
190 // Find current message's position among siblings
191 const currentIndex = siblingIds.indexOf(messageId);
192
193 return {
194 message,
195 siblingIds: siblingLeafIds,
196 currentIndex,
197 totalSiblings: siblingIds.length
198 };
199}
200
201/**
202 * Creates a display-ready list of messages with sibling information for UI rendering.
203 * This is the main function used by chat components to render conversation branches.
204 *
205 * @param messages - All messages in the conversation
206 * @param leafNodeId - Current leaf node being viewed
207 * @returns Array of messages with sibling navigation info
208 */
209export function getMessageDisplayList(
210 messages: readonly DatabaseMessage[],
211 leafNodeId: string
212): ChatMessageSiblingInfo[] {
213 // Get the current conversation path
214 const currentPath = filterByLeafNodeId(messages, leafNodeId, true);
215 const result: ChatMessageSiblingInfo[] = [];
216
217 // Add sibling info for each message in the current path
218 for (const message of currentPath) {
219 if (message.type === 'root') {
220 continue; // Skip root messages in display
221 }
222
223 const siblingInfo = getMessageSiblings(messages, message.id);
224 if (siblingInfo) {
225 result.push(siblingInfo);
226 }
227 }
228
229 return result;
230}
231
232/**
233 * Checks if a message has multiple siblings (indicating branching at that point).
234 *
235 * @param messages - All messages in the conversation
236 * @param messageId - The message to check
237 * @returns True if the message has siblings
238 */
239export function hasMessageSiblings(
240 messages: readonly DatabaseMessage[],
241 messageId: string
242): boolean {
243 const siblingInfo = getMessageSiblings(messages, messageId);
244 return siblingInfo ? siblingInfo.totalSiblings > 1 : false;
245}
246
247/**
248 * Gets the next sibling message ID for navigation.
249 *
250 * @param messages - All messages in the conversation
251 * @param messageId - Current message ID
252 * @returns Next sibling's leaf node ID, or null if at the end
253 */
254export function getNextSibling(
255 messages: readonly DatabaseMessage[],
256 messageId: string
257): string | null {
258 const siblingInfo = getMessageSiblings(messages, messageId);
259 if (!siblingInfo || siblingInfo.currentIndex >= siblingInfo.totalSiblings - 1) {
260 return null;
261 }
262
263 return siblingInfo.siblingIds[siblingInfo.currentIndex + 1];
264}
265
266/**
267 * Gets the previous sibling message ID for navigation.
268 *
269 * @param messages - All messages in the conversation
270 * @param messageId - Current message ID
271 * @returns Previous sibling's leaf node ID, or null if at the beginning
272 */
273export function getPreviousSibling(
274 messages: readonly DatabaseMessage[],
275 messageId: string
276): string | null {
277 const siblingInfo = getMessageSiblings(messages, messageId);
278 if (!siblingInfo || siblingInfo.currentIndex <= 0) {
279 return null;
280 }
281
282 return siblingInfo.siblingIds[siblingInfo.currentIndex - 1];
283}