1use crate::{
18 finality_loop::SyncInfo, finality_proofs::FinalityProofsBuf, Error, FinalitySyncPipeline,
19 HeadersToRelay, SourceClient, SourceHeader, TargetClient,
20};
21
22use bp_header_chain::FinalityProof;
23use num_traits::Saturating;
24use std::cmp::Ordering;
25
26pub type UnjustifiedHeaders<H> = Vec<H>;
28
29#[derive(Debug)]
30#[cfg_attr(test, derive(Clone, PartialEq))]
31pub struct JustifiedHeader<P: FinalitySyncPipeline> {
32 pub header: P::Header,
33 pub proof: P::FinalityProof,
34}
35
36impl<P: FinalitySyncPipeline> JustifiedHeader<P> {
37 pub fn number(&self) -> P::Number {
38 self.header.number()
39 }
40}
41
42pub enum JustifiedHeaderSelector<P: FinalitySyncPipeline> {
44 Mandatory(JustifiedHeader<P>),
46 Regular(UnjustifiedHeaders<P::Header>, JustifiedHeader<P>),
49 None(UnjustifiedHeaders<P::Header>),
51}
52
53impl<P: FinalitySyncPipeline> JustifiedHeaderSelector<P> {
54 pub(crate) async fn new<SC: SourceClient<P>, TC: TargetClient<P>>(
57 source_client: &SC,
58 info: &SyncInfo<P>,
59 headers_to_relay: HeadersToRelay,
60 free_headers_interval: Option<P::Number>,
61 ) -> Result<Self, Error<P, SC::Error, TC::Error>> {
62 let mut unjustified_headers = Vec::new();
63 let mut maybe_justified_header = None;
64
65 let mut header_number = info.best_number_at_target + 1.into();
66 while header_number <= info.best_number_at_source {
67 let (header, maybe_proof) = source_client
68 .header_and_finality_proof(header_number)
69 .await
70 .map_err(Error::Source)?;
71
72 match (header.is_mandatory(), maybe_proof) {
73 (true, Some(proof)) => {
74 log::trace!(target: "bridge", "Header {:?} is mandatory", header_number);
75 return Ok(Self::Mandatory(JustifiedHeader { header, proof }))
76 },
77 (true, None) => return Err(Error::MissingMandatoryFinalityProof(header.number())),
78 (false, Some(proof))
79 if need_to_relay::<P>(
80 info,
81 headers_to_relay,
82 free_headers_interval,
83 &header,
84 ) =>
85 {
86 log::trace!(target: "bridge", "Header {:?} has persistent finality proof", header_number);
87 unjustified_headers.clear();
88 maybe_justified_header = Some(JustifiedHeader { header, proof });
89 },
90 _ => {
91 unjustified_headers.push(header);
92 },
93 }
94
95 header_number = header_number + 1.into();
96 }
97
98 log::trace!(
99 target: "bridge",
100 "Read {} {} headers. Selected finality proof for header: {:?}",
101 info.num_headers(),
102 P::SOURCE_NAME,
103 maybe_justified_header.as_ref().map(|justified_header| &justified_header.header),
104 );
105
106 Ok(match maybe_justified_header {
107 Some(justified_header) => Self::Regular(unjustified_headers, justified_header),
108 None => Self::None(unjustified_headers),
109 })
110 }
111
112 pub fn select_mandatory(self) -> Option<JustifiedHeader<P>> {
114 match self {
115 JustifiedHeaderSelector::Mandatory(header) => Some(header),
116 _ => None,
117 }
118 }
119
120 pub fn select(
123 self,
124 info: &SyncInfo<P>,
125 headers_to_relay: HeadersToRelay,
126 free_headers_interval: Option<P::Number>,
127 buf: &FinalityProofsBuf<P>,
128 ) -> Option<JustifiedHeader<P>> {
129 let (unjustified_headers, maybe_justified_header) = match self {
130 JustifiedHeaderSelector::Mandatory(justified_header) => return Some(justified_header),
131 JustifiedHeaderSelector::Regular(unjustified_headers, justified_header) =>
132 (unjustified_headers, Some(justified_header)),
133 JustifiedHeaderSelector::None(unjustified_headers) => (unjustified_headers, None),
134 };
135
136 let mut finality_proofs_iter = buf.buf().iter().rev();
137 let mut maybe_finality_proof = finality_proofs_iter.next();
138
139 let mut unjustified_headers_iter = unjustified_headers.iter().rev();
140 let mut maybe_unjustified_header = unjustified_headers_iter.next();
141
142 while let (Some(finality_proof), Some(unjustified_header)) =
143 (maybe_finality_proof, maybe_unjustified_header)
144 {
145 match finality_proof.target_header_number().cmp(&unjustified_header.number()) {
146 Ordering::Equal
147 if need_to_relay::<P>(
148 info,
149 headers_to_relay,
150 free_headers_interval,
151 &unjustified_header,
152 ) =>
153 {
154 log::trace!(
155 target: "bridge",
156 "Managed to improve selected {} finality proof {:?} to {:?}.",
157 P::SOURCE_NAME,
158 maybe_justified_header.as_ref().map(|justified_header| justified_header.number()),
159 finality_proof.target_header_number()
160 );
161 return Some(JustifiedHeader {
162 header: unjustified_header.clone(),
163 proof: finality_proof.clone(),
164 })
165 },
166 Ordering::Equal => {
167 maybe_finality_proof = finality_proofs_iter.next();
168 maybe_unjustified_header = unjustified_headers_iter.next();
169 },
170 Ordering::Less => maybe_unjustified_header = unjustified_headers_iter.next(),
171 Ordering::Greater => {
172 maybe_finality_proof = finality_proofs_iter.next();
173 },
174 }
175 }
176
177 log::trace!(
178 target: "bridge",
179 "Could not improve selected {} finality proof {:?}.",
180 P::SOURCE_NAME,
181 maybe_justified_header.as_ref().map(|justified_header| justified_header.number())
182 );
183 maybe_justified_header
184 }
185}
186
187fn need_to_relay<P: FinalitySyncPipeline>(
189 info: &SyncInfo<P>,
190 headers_to_relay: HeadersToRelay,
191 free_headers_interval: Option<P::Number>,
192 header: &P::Header,
193) -> bool {
194 match headers_to_relay {
195 HeadersToRelay::All => true,
196 HeadersToRelay::Mandatory => header.is_mandatory(),
197 HeadersToRelay::Free =>
198 header.is_mandatory() ||
199 free_headers_interval
200 .map(|free_headers_interval| {
201 header.number().saturating_sub(info.best_number_at_target) >=
202 free_headers_interval
203 })
204 .unwrap_or(false),
205 }
206}
207
208#[cfg(test)]
209mod tests {
210 use super::*;
211 use crate::mock::*;
212
213 #[test]
214 fn select_better_recent_finality_proof_works() {
215 let info = SyncInfo {
216 best_number_at_source: 10,
217 best_number_at_target: 5,
218 is_using_same_fork: true,
219 };
220
221 let finality_proofs_buf =
223 FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![TestFinalityProof(5)]);
224 let justified_header =
225 JustifiedHeader { header: TestSourceHeader(false, 2, 2), proof: TestFinalityProof(2) };
226 let selector = JustifiedHeaderSelector::Regular(vec![], justified_header.clone());
227 assert_eq!(
228 selector.select(&info, HeadersToRelay::All, None, &finality_proofs_buf),
229 Some(justified_header)
230 );
231
232 let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![]);
234 let justified_header =
235 JustifiedHeader { header: TestSourceHeader(false, 2, 2), proof: TestFinalityProof(2) };
236 let selector = JustifiedHeaderSelector::Regular(
237 vec![TestSourceHeader(false, 5, 5)],
238 justified_header.clone(),
239 );
240 assert_eq!(
241 selector.select(&info, HeadersToRelay::All, None, &finality_proofs_buf),
242 Some(justified_header)
243 );
244
245 let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
248 TestFinalityProof(1),
249 TestFinalityProof(4),
250 ]);
251 let justified_header =
252 JustifiedHeader { header: TestSourceHeader(false, 2, 2), proof: TestFinalityProof(2) };
253 let selector = JustifiedHeaderSelector::Regular(
254 vec![TestSourceHeader(false, 9, 9), TestSourceHeader(false, 10, 10)],
255 justified_header.clone(),
256 );
257 assert_eq!(
258 selector.select(&info, HeadersToRelay::All, None, &finality_proofs_buf),
259 Some(justified_header)
260 );
261
262 let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
265 TestFinalityProof(7),
266 TestFinalityProof(11),
267 ]);
268 let justified_header =
269 JustifiedHeader { header: TestSourceHeader(false, 2, 2), proof: TestFinalityProof(2) };
270 let selector = JustifiedHeaderSelector::Regular(
271 vec![
272 TestSourceHeader(false, 8, 8),
273 TestSourceHeader(false, 9, 9),
274 TestSourceHeader(false, 10, 10),
275 ],
276 justified_header.clone(),
277 );
278 assert_eq!(
279 selector.select(&info, HeadersToRelay::All, None, &finality_proofs_buf),
280 Some(justified_header)
281 );
282
283 let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
288 TestFinalityProof(7),
289 TestFinalityProof(9),
290 ]);
291 let justified_header =
292 JustifiedHeader { header: TestSourceHeader(false, 2, 2), proof: TestFinalityProof(2) };
293 let selector = JustifiedHeaderSelector::Regular(
294 vec![
295 TestSourceHeader(false, 8, 8),
296 TestSourceHeader(false, 9, 9),
297 TestSourceHeader(false, 10, 10),
298 ],
299 justified_header,
300 );
301 assert_eq!(
302 selector.select(&info, HeadersToRelay::All, None, &finality_proofs_buf),
303 Some(JustifiedHeader {
304 header: TestSourceHeader(false, 9, 9),
305 proof: TestFinalityProof(9)
306 })
307 );
308
309 let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
311 TestFinalityProof(7),
312 TestFinalityProof(9),
313 ]);
314 let selector = JustifiedHeaderSelector::None(vec![
315 TestSourceHeader(false, 8, 8),
316 TestSourceHeader(false, 9, 9),
317 TestSourceHeader(false, 10, 10),
318 ]);
319 assert_eq!(
320 selector.select(&info, HeadersToRelay::Free, Some(7), &finality_proofs_buf),
321 None,
322 );
323
324 let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
326 TestFinalityProof(6),
327 TestFinalityProof(9),
328 ]);
329 let selector = JustifiedHeaderSelector::None(vec![
330 TestSourceHeader(false, 8, 8),
331 TestSourceHeader(true, 9, 9),
332 TestSourceHeader(false, 10, 10),
333 ]);
334 assert_eq!(
335 selector.select(&info, HeadersToRelay::Free, Some(7), &finality_proofs_buf),
336 Some(JustifiedHeader {
337 header: TestSourceHeader(true, 9, 9),
338 proof: TestFinalityProof(9)
339 })
340 );
341
342 let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
344 TestFinalityProof(7),
345 TestFinalityProof(9),
346 TestFinalityProof(14),
347 ]);
348 let selector = JustifiedHeaderSelector::None(vec![
349 TestSourceHeader(false, 7, 7),
350 TestSourceHeader(false, 10, 10),
351 TestSourceHeader(false, 14, 14),
352 ]);
353 assert_eq!(
354 selector.select(&info, HeadersToRelay::Free, Some(7), &finality_proofs_buf),
355 Some(JustifiedHeader {
356 header: TestSourceHeader(false, 14, 14),
357 proof: TestFinalityProof(14)
358 })
359 );
360 }
361}