matter_kit/exchange/table.rs
1//! The set of open exchanges, sized by [`Config`].
2//!
3//! An exchange is identified by its id *and* by who initiated it (Core §4.10): two nodes
4//! that each start an exchange may each pick the number 7, and they are two different
5//! conversations. Keying the table on the pair is what keeps them apart — keying it on the
6//! id alone is a bug that only appears when both ends are busy.
7
8use core::marker::PhantomData;
9
10use heapless::Vec;
11
12use super::mrp::{Mrp, MrpParams};
13use crate::config::{AssertValid, Config};
14use crate::error::{Error, ErrorCode, Result};
15use crate::msg::{ExchangeId, ProtocolId, SessionId};
16use crate::platform::{Duration, Instant, Peer};
17
18/// Which end of an exchange a node is (Core §4.4.3.1, the **I** flag).
19#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
20pub enum Role {
21 /// This node started the exchange, and sets the **I** flag on what it sends.
22 Initiator,
23 /// The peer started it.
24 Responder,
25}
26
27impl Role {
28 /// The role of whoever is on the other end.
29 #[must_use]
30 pub const fn peer(self) -> Self {
31 match self {
32 Self::Initiator => Self::Responder,
33 Self::Responder => Self::Initiator,
34 }
35 }
36
37 /// Whether this node sets the **I** flag.
38 #[must_use]
39 pub const fn is_initiator(self) -> bool {
40 matches!(self, Self::Initiator)
41 }
42}
43
44/// What identifies an exchange within a node.
45#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
46pub struct ExchangeKey {
47 /// The session it lives on.
48 pub session: SessionId,
49 /// The 16-bit exchange id.
50 pub id: ExchangeId,
51 /// Which end this node is. Part of the key, not a property: the peer may be using the
52 /// same id for an exchange of its own.
53 pub role: Role,
54}
55
56/// One open exchange.
57#[derive(Debug, Clone, Copy, PartialEq, Eq)]
58pub struct Exchange {
59 /// What identifies it.
60 pub key: ExchangeKey,
61 /// Which protocol is speaking over it.
62 pub protocol: ProtocolId,
63 /// Its reliability state.
64 pub mrp: Mrp,
65 /// Where the peer is, once a message has arrived from it or the caller has said.
66 ///
67 /// It decides two things: where a reply goes, and — per Core §4.12.4 — whether MRP runs
68 /// on this exchange at all, since BTP and TCP carry their own reliability.
69 pub peer: Option<Peer>,
70 /// When it was opened.
71 pub opened: Instant,
72 /// When a message last arrived on it or went out on it.
73 ///
74 /// This, not [`Exchange::opened`], is what [`ExchangeTable::reap`] judges: a chunked read
75 /// or a BDX transfer is legitimately long-lived, and reaping by age would cut it off
76 /// mid-transfer. What must not survive is an exchange nothing is *using*.
77 pub last_activity: Instant,
78 /// Whether this is §4.10.5.2's *ephemeral* exchange.
79 ///
80 /// "Create an ephemeral exchange from the incoming message and send an immediate
81 /// standalone acknowledgement … The message SHALL NOT be forwarded to the upper layer …
82 /// The ephemeral exchange created for such duplicate or unknown messages with R Flag set
83 /// is automatically closed in Standalone acknowledgement processing."
84 ///
85 /// It exists for exactly one reason: a reliable message this node cannot act on still owes
86 /// its sender an acknowledgement, or the sender retransmits it five times. Holding a real
87 /// exchange open to do that is what lets a stranger fill the table.
88 pub ephemeral: bool,
89}
90
91impl Exchange {
92 /// Opens an exchange.
93 #[must_use]
94 pub fn new(key: ExchangeKey, protocol: ProtocolId, params: MrpParams, now: Instant) -> Self {
95 Self {
96 key,
97 protocol,
98 mrp: Mrp::new(params),
99 peer: None,
100 opened: now,
101 last_activity: now,
102 ephemeral: false,
103 }
104 }
105
106 /// The same exchange, marked ephemeral (§4.10.5.2).
107 #[must_use]
108 pub const fn ephemeral(mut self) -> Self {
109 self.ephemeral = true;
110 self
111 }
112
113 /// Records that a message arrived on this exchange or went out on it.
114 pub const fn touch(&mut self, now: Instant) {
115 self.last_activity = now;
116 }
117
118 /// Whether nothing has used this exchange for `idle` and nothing is pending on it.
119 ///
120 /// §4.10.5.3 step 2 is the second half: "Wait for all pending retransmissions associated
121 /// with the Exchange to complete. If the retransmission list for the Exchange is empty,
122 /// remove the Exchange. Otherwise, leave the Exchange open and only close it once the
123 /// retransmission list is empty." An exchange still trying to deliver something is not
124 /// abandoned, however quiet the peer has been.
125 #[must_use]
126 pub fn is_abandoned(&self, now: Instant, idle: Duration) -> bool {
127 // "the retransmission list" — a message still awaiting acknowledgement, not merely any
128 // timer. An exchange can also hold a standalone acknowledgement it owes the peer, and
129 // one still owed after the idle timeout means nobody drove the timers at all; letting
130 // that pin an entry forever is the leak this is here to close.
131 if self.mrp.is_awaiting_ack() {
132 return false;
133 }
134 // `>=`, matching `reap_deadline`: a deadline at which `reap` does nothing is a deadline a
135 // loop wakes for and then wakes for again, at the same instant, for ever.
136 now.as_micros()
137 .saturating_sub(self.last_activity.as_micros())
138 >= idle.as_micros()
139 }
140
141 /// The same exchange with its peer known from the start — what an initiator has, since
142 /// it chose who to talk to.
143 #[must_use]
144 pub fn to_peer(mut self, peer: Peer) -> Self {
145 self.peer = Some(peer);
146 self
147 }
148
149 /// Whether the transport underneath supplies its own reliability, so §4.12.4's "SHOULD
150 /// NOT set the R Flag" applies.
151 ///
152 /// An exchange whose peer is not yet known is assumed to be on UDP: MRP is the default
153 /// and the conservative choice, since an unnecessary acknowledgement costs a round trip
154 /// while a missing one costs the message.
155 #[must_use]
156 pub fn is_transport_reliable(&self) -> bool {
157 self.peer.is_some_and(|p| p.is_reliable())
158 }
159}
160
161/// How long an exchange may sit with nothing happening on it before it is reclaimed.
162///
163/// The specification gives no figure — §4.10.5.3 leaves closing to "the application layer or a
164/// fatal connection error" — but leaving that to the application is what makes an exchange
165/// table a remotely exhaustible resource. Every unsecured message with the I Flag set opens an
166/// exchange (§4.10.5.2), and an attacker who can reach the port can send them with any exchange
167/// id it likes. Without reclamation, `N` datagrams costing nothing fill the table for good, and
168/// a node that can no longer open an exchange can no longer establish a session — PASE or CASE,
169/// for the rest of its uptime. Existing sessions keep working, which is what makes it hard to
170/// notice.
171///
172/// Sixty seconds is taken from §5.5's bound on the one exchange most worth attacking: "a
173/// Commissionee SHALL expect a PASE session to be established within 60 seconds of receiving
174/// the initial request". An exchange idle for longer than the specification allows the whole
175/// handshake is not one anybody is still using.
176pub const EXCHANGE_IDLE_TIMEOUT: Duration = Duration::from_secs(60);
177
178/// The fixed-capacity set of open exchanges.
179///
180/// Capacity is `C::SESSIONS * C::EXCHANGES_PER_SESSION`, which is what
181/// [`Config`] says the node was built for. A full table is
182/// [`ErrorCode::NoSpace`] — a value the caller answers `BUSY` with, never an abort.
183#[derive(Debug)]
184pub struct ExchangeTable<C: Config, const N: usize = 64> {
185 open: Vec<Exchange, N>,
186 /// The next exchange id to hand out. §4.4.3.3 only requires that an id not collide
187 /// with a live exchange on the same session; a counter is the simplest thing that
188 /// achieves it.
189 next_id: u16,
190 _config: PhantomData<C>,
191}
192
193impl<C: Config, const N: usize> Default for ExchangeTable<C, N> {
194 fn default() -> Self {
195 Self::new(0)
196 }
197}
198
199impl<C: Config, const N: usize> crate::config::Capacity for ExchangeTable<C, N> {
200 const TOTAL: usize = N;
201 /// The specification sets no per-fabric exchange guarantee, so the whole table is the
202 /// answer: an exchange is opened and closed inside one interaction, and §4.10.5.3's
203 /// reclamation is what keeps a stranger from holding them.
204 const PER_FABRIC: usize = N;
205}
206
207impl<C: Config, const N: usize> ExchangeTable<C, N> {
208 /// An empty table whose first exchange id is `first_id`.
209 ///
210 /// `first_id` should come from [`Rng`](crate::platform::Rng): starting at zero every
211 /// boot makes a node's exchange ids predictable, and predictable ids make it cheaper
212 /// for an off-path attacker to guess one that is live.
213 #[must_use]
214 pub fn new(first_id: u16) -> Self {
215 // Instantiating the check is what makes a `Config` that breaks a specification
216 // minimum a compile error at this line rather than a certification failure later.
217 let () = AssertValid::<C>::CHECK;
218 Self {
219 open: Vec::new(),
220 next_id: first_id,
221 _config: PhantomData,
222 }
223 }
224
225 /// How many exchanges are open.
226 #[must_use]
227 pub fn len(&self) -> usize {
228 self.open.len()
229 }
230
231 /// Whether none are open.
232 #[must_use]
233 pub fn is_empty(&self) -> bool {
234 self.open.is_empty()
235 }
236
237 /// How many more will fit.
238 #[must_use]
239 pub fn capacity_remaining(&self) -> usize {
240 N.saturating_sub(self.open.len())
241 }
242
243 /// Opens an exchange this node initiates, choosing an unused id.
244 pub fn open_initiator(
245 &mut self,
246 session: SessionId,
247 protocol: ProtocolId,
248 params: MrpParams,
249 peer: Option<Peer>,
250 now: Instant,
251 ) -> Result<ExchangeKey> {
252 let id = self.allocate_id(session)?;
253 let key = ExchangeKey {
254 session,
255 id,
256 role: Role::Initiator,
257 };
258 let exchange = Exchange::new(key, protocol, params, now);
259 self.insert(match peer {
260 Some(peer) => exchange.to_peer(peer),
261 None => exchange,
262 })?;
263 Ok(key)
264 }
265
266 /// Opens an exchange the peer initiated.
267 ///
268 /// Returns [`ErrorCode::InvalidState`] if one with that key is already open — a peer
269 /// reusing a live id is either confused or hostile, and silently adopting the second
270 /// one would let it hijack the first.
271 pub fn open_responder(
272 &mut self,
273 session: SessionId,
274 id: ExchangeId,
275 protocol: ProtocolId,
276 params: MrpParams,
277 now: Instant,
278 ) -> Result<ExchangeKey> {
279 let key = ExchangeKey {
280 session,
281 id,
282 role: Role::Responder,
283 };
284 if self.find(key).is_some() {
285 return Err(Error::new(ErrorCode::InvalidState));
286 }
287 self.insert_under_pressure(Exchange::new(key, protocol, params, now), now)?;
288 Ok(key)
289 }
290
291 /// Opens §4.10.5.2's ephemeral exchange: one that exists only to carry a standalone
292 /// acknowledgement and is closed as soon as it has.
293 pub fn open_ephemeral(
294 &mut self,
295 session: SessionId,
296 id: ExchangeId,
297 protocol: ProtocolId,
298 params: MrpParams,
299 now: Instant,
300 ) -> Result<ExchangeKey> {
301 let key = ExchangeKey {
302 session,
303 id,
304 role: Role::Responder,
305 };
306 if let Some(existing) = self.find(key) {
307 return Ok(existing.key);
308 }
309 self.insert_under_pressure(Exchange::new(key, protocol, params, now).ephemeral(), now)?;
310 Ok(key)
311 }
312
313 /// Inserts, reclaiming abandoned entries first if the table is full.
314 ///
315 /// Reaping here as well as on the timer is what makes the bound hold for a node whose
316 /// timers are slow or stopped: the pressure that would have refused a legitimate peer is
317 /// the same pressure that proves some other entry has been idle too long.
318 fn insert_under_pressure(&mut self, exchange: Exchange, now: Instant) -> Result<()> {
319 if self.open.is_full() {
320 self.reap(now, EXCHANGE_IDLE_TIMEOUT);
321 }
322 self.insert(exchange)
323 }
324
325 fn insert(&mut self, exchange: Exchange) -> Result<()> {
326 self.open
327 .push(exchange)
328 .map_err(|_| Error::new(ErrorCode::NoSpace))
329 }
330
331 /// Closes every exchange nothing has used for `idle` and nothing is pending on.
332 ///
333 /// Returns how many went. [`Messaging::poll`](crate::messaging::Messaging::poll) calls
334 /// this, so a node that drives its timers at all gets it without asking — which is the
335 /// point: an exchange table that is only reclaimed when the application remembers to
336 /// reclaim it is one an attacker reclaims on its behalf.
337 pub fn reap(&mut self, now: Instant, idle: Duration) -> usize {
338 let before = self.open.len();
339 self.open.retain(|e| !e.is_abandoned(now, idle));
340 before.saturating_sub(self.open.len())
341 }
342
343 /// When [`ExchangeTable::reap`] would next have something to do.
344 #[must_use]
345 pub fn reap_deadline(&self, idle: Duration) -> Option<Instant> {
346 self.open
347 .iter()
348 .filter(|e| !e.mrp.is_awaiting_ack())
349 .map(|e| e.last_activity.saturating_add(idle))
350 .min()
351 }
352
353 fn allocate_id(&mut self, session: SessionId) -> Result<ExchangeId> {
354 // Try every id once before giving up, so a table that is merely fragmented still
355 // finds one.
356 for _ in 0..=u16::MAX {
357 let id = ExchangeId(self.next_id);
358 self.next_id = self.next_id.wrapping_add(1);
359 let key = ExchangeKey {
360 session,
361 id,
362 role: Role::Initiator,
363 };
364 if self.find(key).is_none() {
365 return Ok(id);
366 }
367 }
368 Err(Error::new(ErrorCode::NoSpace))
369 }
370
371 /// The exchange with this key, if it is open.
372 #[must_use]
373 pub fn find(&self, key: ExchangeKey) -> Option<&Exchange> {
374 self.open.iter().find(|e| e.key == key)
375 }
376
377 /// The exchange with this key, mutably.
378 pub fn find_mut(&mut self, key: ExchangeKey) -> Option<&mut Exchange> {
379 self.open.iter_mut().find(|e| e.key == key)
380 }
381
382 /// Finds the exchange an arriving message belongs to.
383 ///
384 /// `from_initiator` is the message's **I** flag. A message *from* the initiator
385 /// belongs to the exchange in which this node is the **responder**, and the other way
386 /// round — getting this inversion wrong is how a node answers its own request.
387 #[must_use]
388 pub fn find_for_message(
389 &self,
390 session: SessionId,
391 id: ExchangeId,
392 from_initiator: bool,
393 ) -> Option<&Exchange> {
394 let role = if from_initiator {
395 Role::Responder
396 } else {
397 Role::Initiator
398 };
399 self.find(ExchangeKey { session, id, role })
400 }
401
402 /// Closes an exchange, returning whether it was open.
403 pub fn close(&mut self, key: ExchangeKey) -> bool {
404 let Some(i) = self.open.iter().position(|e| e.key == key) else {
405 return false;
406 };
407 if let Some(e) = self.open.get_mut(i) {
408 e.mrp.close();
409 }
410 self.open.swap_remove(i);
411 true
412 }
413
414 /// Closes every exchange on a session — what tearing the session down does.
415 pub fn close_session(&mut self, session: SessionId) -> usize {
416 let before = self.open.len();
417 self.open.retain(|e| e.key.session != session);
418 before.saturating_sub(self.open.len())
419 }
420
421 /// The earliest deadline across every open exchange, which is when the caller's run
422 /// loop should next call [`ExchangeTable::on_timeout`].
423 #[must_use]
424 pub fn poll_deadline(&self) -> Option<Instant> {
425 self.open.iter().filter_map(|e| e.mrp.poll_deadline()).min()
426 }
427
428 /// Hands a passed deadline to every exchange that has one, calling `on_action` for
429 /// each thing that falls out.
430 ///
431 /// Returns how many actions were produced.
432 pub fn on_timeout(
433 &mut self,
434 now: Instant,
435 randomness: u32,
436 mut on_action: impl FnMut(ExchangeKey, super::OnTimeout),
437 ) -> usize {
438 let mut count = 0usize;
439 for exchange in &mut self.open {
440 loop {
441 let action = exchange.mrp.on_timeout(now, randomness);
442 if matches!(action, super::OnTimeout::Nothing) {
443 break;
444 }
445 on_action(exchange.key, action);
446 count = count.saturating_add(1);
447 }
448 }
449 count
450 }
451
452 /// Every open exchange.
453 pub fn iter(&self) -> impl Iterator<Item = &Exchange> {
454 self.open.iter()
455 }
456}
457
458#[cfg(test)]
459mod tests {
460 use super::*;
461 use crate::DefaultConfig;
462 use crate::exchange::OnTimeout;
463
464 type Table = ExchangeTable<DefaultConfig, 8>;
465
466 #[test]
467 fn an_initiated_exchange_gets_an_unused_id() {
468 let mut t = Table::new(100);
469 let a = t
470 .open_initiator(
471 SessionId(1),
472 ProtocolId::INTERACTION_MODEL,
473 MrpParams::default(),
474 None,
475 Instant::ZERO,
476 )
477 .expect("open");
478 let b = t
479 .open_initiator(
480 SessionId(1),
481 ProtocolId::INTERACTION_MODEL,
482 MrpParams::default(),
483 None,
484 Instant::ZERO,
485 )
486 .expect("open");
487 assert_ne!(a.id, b.id);
488 assert_eq!(a.id, ExchangeId(100));
489 assert_eq!(t.len(), 2);
490 }
491
492 #[test]
493 fn the_same_id_in_both_roles_is_two_exchanges() {
494 // Two nodes that each start an exchange may each choose 7. Keying on the id alone
495 // would merge them, and this node would answer its own request.
496 let mut t = Table::new(7);
497 let mine = t
498 .open_initiator(
499 SessionId(1),
500 ProtocolId::SECURE_CHANNEL,
501 MrpParams::default(),
502 None,
503 Instant::ZERO,
504 )
505 .expect("mine");
506 assert_eq!(mine.id, ExchangeId(7));
507 let theirs = t
508 .open_responder(
509 SessionId(1),
510 ExchangeId(7),
511 ProtocolId::SECURE_CHANNEL,
512 MrpParams::default(),
513 Instant::ZERO,
514 )
515 .expect("theirs");
516 assert_eq!(t.len(), 2, "two distinct exchanges");
517 assert_ne!(mine, theirs);
518 assert!(t.find(mine).is_some());
519 assert!(t.find(theirs).is_some());
520 }
521
522 #[test]
523 fn an_arriving_message_finds_the_opposite_role() {
524 let mut t = Table::new(0);
525 let mine = t
526 .open_initiator(
527 SessionId(1),
528 ProtocolId::SECURE_CHANNEL,
529 MrpParams::default(),
530 None,
531 Instant::ZERO,
532 )
533 .expect("open");
534 // The peer's reply carries I = 0, because the peer is not the initiator.
535 let found = t
536 .find_for_message(SessionId(1), mine.id, false)
537 .expect("the reply belongs to my exchange");
538 assert_eq!(found.key, mine);
539 // A message with I = 1 and the same id is a *different* exchange, which is not
540 // open.
541 assert!(t.find_for_message(SessionId(1), mine.id, true).is_none());
542 }
543
544 #[test]
545 fn a_peer_reusing_a_live_id_is_refused() {
546 let mut t = Table::new(0);
547 t.open_responder(
548 SessionId(1),
549 ExchangeId(3),
550 ProtocolId::SECURE_CHANNEL,
551 MrpParams::default(),
552 Instant::ZERO,
553 )
554 .expect("first");
555 assert_eq!(
556 t.open_responder(
557 SessionId(1),
558 ExchangeId(3),
559 ProtocolId::SECURE_CHANNEL,
560 MrpParams::default(),
561 Instant::ZERO,
562 )
563 .unwrap_err()
564 .code(),
565 ErrorCode::InvalidState
566 );
567 }
568
569 #[test]
570 fn the_same_id_on_two_sessions_is_two_exchanges() {
571 let mut t = Table::new(0);
572 t.open_responder(
573 SessionId(1),
574 ExchangeId(5),
575 ProtocolId::SECURE_CHANNEL,
576 MrpParams::default(),
577 Instant::ZERO,
578 )
579 .expect("session 1");
580 t.open_responder(
581 SessionId(2),
582 ExchangeId(5),
583 ProtocolId::SECURE_CHANNEL,
584 MrpParams::default(),
585 Instant::ZERO,
586 )
587 .expect("session 2");
588 assert_eq!(t.len(), 2);
589 }
590
591 #[test]
592 fn a_full_table_is_a_value_not_an_abort() {
593 let mut t = Table::new(0);
594 for _ in 0..8 {
595 t.open_initiator(
596 SessionId(1),
597 ProtocolId::SECURE_CHANNEL,
598 MrpParams::default(),
599 None,
600 Instant::ZERO,
601 )
602 .expect("fits");
603 }
604 assert_eq!(t.capacity_remaining(), 0);
605 assert_eq!(
606 t.open_initiator(
607 SessionId(1),
608 ProtocolId::SECURE_CHANNEL,
609 MrpParams::default(),
610 None,
611 Instant::ZERO,
612 )
613 .unwrap_err()
614 .code(),
615 ErrorCode::NoSpace
616 );
617 }
618
619 #[test]
620 fn closing_a_session_closes_its_exchanges() {
621 let mut t = Table::new(0);
622 for session in [1u16, 1, 2] {
623 t.open_initiator(
624 SessionId(session),
625 ProtocolId::SECURE_CHANNEL,
626 MrpParams::default(),
627 None,
628 Instant::ZERO,
629 )
630 .expect("open");
631 }
632 assert_eq!(t.close_session(SessionId(1)), 2);
633 assert_eq!(t.len(), 1);
634 assert_eq!(t.close_session(SessionId(1)), 0);
635 }
636
637 #[test]
638 fn close_reports_whether_it_did_anything() {
639 let mut t = Table::new(0);
640 let k = t
641 .open_initiator(
642 SessionId(1),
643 ProtocolId::SECURE_CHANNEL,
644 MrpParams::default(),
645 None,
646 Instant::ZERO,
647 )
648 .expect("open");
649 assert!(t.close(k));
650 assert!(!t.close(k));
651 assert!(t.is_empty());
652 }
653
654 #[test]
655 fn the_table_deadline_is_the_earliest_of_them() {
656 let mut t = Table::new(0);
657 let slow = t
658 .open_initiator(
659 SessionId(1),
660 ProtocolId::SECURE_CHANNEL,
661 MrpParams::default(),
662 None,
663 Instant::ZERO,
664 )
665 .expect("open");
666 let fast = t
667 .open_initiator(
668 SessionId(1),
669 ProtocolId::SECURE_CHANNEL,
670 MrpParams::default(),
671 None,
672 Instant::ZERO,
673 )
674 .expect("open");
675
676 assert_eq!(t.poll_deadline(), None, "nothing is in flight yet");
677 if let Some(e) = t.find_mut(slow) {
678 e.mrp.on_send(1, Instant::ZERO, 0).expect("send");
679 }
680 if let Some(e) = t.find_mut(fast) {
681 // An active peer retries sooner: 330 ms against 550 ms.
682 e.mrp.note_peer_activity(Instant::ZERO);
683 e.mrp.on_send(2, Instant::ZERO, 0).expect("send");
684 }
685 let deadline = t.poll_deadline().expect("a deadline");
686 assert_eq!(deadline.as_micros(), 330_000);
687 }
688
689 #[test]
690 fn timeouts_are_reported_per_exchange() {
691 let mut t = Table::new(0);
692 let k = t
693 .open_initiator(
694 SessionId(1),
695 ProtocolId::SECURE_CHANNEL,
696 MrpParams::default(),
697 None,
698 Instant::ZERO,
699 )
700 .expect("open");
701 if let Some(e) = t.find_mut(k) {
702 e.mrp.on_send(9, Instant::ZERO, 0).expect("send");
703 }
704 let deadline = t.poll_deadline().expect("a deadline");
705
706 let mut seen = heapless::Vec::<(ExchangeKey, u32), 4>::new();
707 let n = t.on_timeout(deadline, 0, |key, action| {
708 if let OnTimeout::Retransmit { counter, .. } = action {
709 let _ = seen.push((key, counter));
710 }
711 });
712 assert_eq!(n, 1);
713 assert_eq!(&seen[..], &[(k, 9)]);
714 }
715}