1use crate::stdlib::{collections::BTreeMap, prelude::*};
2use crate::types::builtin_name::BuiltinName;
3use crate::types::relocatable::{MaybeRelocatable, Relocatable};
4use crate::vm::errors::memory_errors::MemoryError;
5use crate::vm::errors::runner_errors::RunnerError;
6use crate::vm::runners::cairo_pie::{
7 Attributes, BuiltinAdditionalData, OutputBuiltinAdditionalData, Pages, PublicMemoryPage,
8};
9use crate::vm::vm_core::VirtualMachine;
10use crate::vm::vm_memory::memory_segments::MemorySegmentManager;
11
12#[derive(Debug, Clone, PartialEq)]
13pub struct OutputBuiltinState {
14 pub base: usize,
15 pub base_offset: usize,
16 pub pages: Pages,
17 pub attributes: Attributes,
18}
19
20#[derive(Debug, Clone)]
21pub struct OutputBuiltinRunner {
22 base: usize,
23 pub base_offset: usize,
24 pub(crate) pages: Pages,
25 pub(crate) attributes: Attributes,
26 pub(crate) stop_ptr: Option<usize>,
27 pub(crate) included: bool,
28}
29
30impl OutputBuiltinRunner {
31 pub fn new(included: bool) -> OutputBuiltinRunner {
32 OutputBuiltinRunner {
33 base: 0,
34 base_offset: 0,
35 pages: BTreeMap::default(),
36 attributes: BTreeMap::default(),
37 stop_ptr: None,
38 included,
39 }
40 }
41
42 pub fn new_state(&mut self, base: usize, base_offset: usize, included: bool) {
43 self.base = base;
44 self.base_offset = base_offset;
45 self.pages = BTreeMap::default();
46 self.attributes = BTreeMap::default();
47 self.stop_ptr = None;
48 self.included = included;
49 }
50
51 pub fn initialize_segments(&mut self, segments: &mut MemorySegmentManager) {
52 self.base = segments.add().segment_index as usize }
54
55 pub fn initial_stack(&self) -> Vec<MaybeRelocatable> {
56 if self.included {
57 vec![MaybeRelocatable::from((self.base as isize, 0))]
58 } else {
59 vec![]
60 }
61 }
62
63 pub fn base(&self) -> usize {
64 self.base
65 }
66
67 pub fn get_allocated_memory_units(&self, _vm: &VirtualMachine) -> Result<usize, MemoryError> {
68 Ok(0)
69 }
70
71 pub fn get_used_cells(&self, segments: &MemorySegmentManager) -> Result<usize, MemoryError> {
72 segments
73 .get_segment_used_size(self.base)
74 .ok_or(MemoryError::MissingSegmentUsedSizes)
75 }
76
77 pub fn get_used_instances(
78 &self,
79 segments: &MemorySegmentManager,
80 ) -> Result<usize, MemoryError> {
81 self.get_used_cells(segments)
82 }
83
84 pub fn final_stack(
85 &mut self,
86 segments: &MemorySegmentManager,
87 pointer: Relocatable,
88 ) -> Result<Relocatable, RunnerError> {
89 if self.included {
90 let stop_pointer_addr = (pointer - 1)
91 .map_err(|_| RunnerError::NoStopPointer(Box::new(BuiltinName::output)))?;
92 let stop_pointer = segments
93 .memory
94 .get_relocatable(stop_pointer_addr)
95 .map_err(|_| RunnerError::NoStopPointer(Box::new(BuiltinName::output)))?;
96 if self.base as isize != stop_pointer.segment_index {
97 return Err(RunnerError::InvalidStopPointerIndex(Box::new((
98 BuiltinName::output,
99 stop_pointer,
100 self.base,
101 ))));
102 }
103 let stop_ptr = stop_pointer.offset;
104 let used = self.get_used_cells(segments).map_err(RunnerError::Memory)?;
105 if stop_ptr != used {
106 return Err(RunnerError::InvalidStopPointer(Box::new((
107 BuiltinName::output,
108 Relocatable::from((self.base as isize, used)),
109 Relocatable::from((self.base as isize, stop_ptr)),
110 ))));
111 }
112 self.stop_ptr = Some(stop_ptr);
113 Ok(stop_pointer_addr)
114 } else {
115 self.stop_ptr = Some(0);
116 Ok(pointer)
117 }
118 }
119
120 pub fn add_attribute(&mut self, name: String, value: Vec<usize>) {
121 self.attributes.insert(name, value);
122 }
123
124 pub fn get_additional_data(&self) -> BuiltinAdditionalData {
125 BuiltinAdditionalData::Output(OutputBuiltinAdditionalData {
126 pages: self.pages.clone(),
127 attributes: self.attributes.clone(),
128 })
129 }
130
131 pub fn extend_additional_data(
132 &mut self,
133 additional_data: &BuiltinAdditionalData,
134 ) -> Result<(), RunnerError> {
135 let additional_data = match additional_data {
136 BuiltinAdditionalData::Output(d) => d,
137 _ => return Err(RunnerError::InvalidAdditionalData(BuiltinName::output)),
138 };
139 self.pages.extend(additional_data.pages.clone());
140 self.attributes.extend(additional_data.attributes.clone());
141 Ok(())
142 }
143
144 pub(crate) fn set_stop_ptr_offset(&mut self, offset: usize) {
145 self.stop_ptr = Some(offset)
146 }
147
148 pub fn set_state(&mut self, new_state: OutputBuiltinState) {
149 self.base = new_state.base;
150 self.base_offset = new_state.base_offset;
151 self.pages = new_state.pages;
152 self.attributes = new_state.attributes;
153 }
154
155 pub fn get_state(&mut self) -> OutputBuiltinState {
156 OutputBuiltinState {
157 base: self.base,
158 base_offset: self.base_offset,
159 pages: self.pages.clone(),
160 attributes: self.attributes.clone(),
161 }
162 }
163
164 pub fn add_page(
165 &mut self,
166 page_id: usize,
167 page_start: Relocatable,
168 page_size: usize,
169 ) -> Result<(), RunnerError> {
170 if page_start.segment_index as usize != self.base {
171 return Err(RunnerError::PageNotOnSegment(page_start, self.base));
172 }
173
174 self.pages.insert(
175 page_id,
176 PublicMemoryPage {
177 start: page_start.offset - self.base_offset,
178 size: page_size,
179 },
180 );
181
182 Ok(())
183 }
184
185 pub fn get_public_memory(
186 &self,
187 segments: &MemorySegmentManager,
188 ) -> Result<Vec<(usize, usize)>, RunnerError> {
189 let size = self.get_used_cells(segments)?;
190
191 let mut public_memory: Vec<(usize, usize)> = (0..size).map(|i| (i, 0)).collect();
192 for (page_id, page) in self.pages.iter() {
193 for index in 0..page.size {
194 public_memory[page.start + index].1 = *page_id;
195 }
196 }
197
198 Ok(public_memory)
199 }
200}
201
202impl Default for OutputBuiltinRunner {
203 fn default() -> Self {
204 Self::new(true)
205 }
206}
207
208#[cfg(test)]
209mod tests {
210 use super::*;
211 use crate::relocatable;
212
213 use crate::{
214 utils::test_utils::*,
215 vm::{errors::memory_errors::MemoryError, runners::builtin_runner::BuiltinRunner},
216 };
217
218 #[cfg(target_arch = "wasm32")]
219 use wasm_bindgen_test::*;
220
221 #[test]
222 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
223 fn get_used_instances() {
224 let builtin = OutputBuiltinRunner::new(true);
225
226 let mut vm = vm!();
227 vm.segments.segment_used_sizes = Some(vec![1]);
228
229 assert_eq!(builtin.get_used_instances(&vm.segments), Ok(1));
230 }
231
232 #[test]
233 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
234 fn final_stack() {
235 let mut builtin = OutputBuiltinRunner::new(true);
236
237 let mut vm = vm!();
238
239 vm.segments = segments![
240 ((0, 0), (0, 0)),
241 ((0, 1), (0, 1)),
242 ((2, 0), (0, 0)),
243 ((2, 1), (0, 0))
244 ];
245
246 vm.segments.segment_used_sizes = Some(vec![0]);
247
248 let pointer = Relocatable::from((2, 2));
249
250 assert_eq!(
251 builtin.final_stack(&vm.segments, pointer).unwrap(),
252 Relocatable::from((2, 1))
253 );
254 }
255
256 #[test]
257 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
258 fn final_stack_error_stop_pointer() {
259 let mut builtin = OutputBuiltinRunner::new(true);
260
261 let mut vm = vm!();
262
263 vm.segments = segments![
264 ((0, 0), (0, 0)),
265 ((0, 1), (0, 1)),
266 ((2, 0), (0, 0)),
267 ((2, 1), (0, 0))
268 ];
269
270 vm.segments.segment_used_sizes = Some(vec![998]);
271
272 let pointer = Relocatable::from((2, 2));
273
274 assert_eq!(
275 builtin.final_stack(&vm.segments, pointer),
276 Err(RunnerError::InvalidStopPointer(Box::new((
277 BuiltinName::output,
278 relocatable!(0, 998),
279 relocatable!(0, 0)
280 ))))
281 );
282 }
283
284 #[test]
285 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
286 fn final_stack_error_when_notincluded() {
287 let mut builtin = OutputBuiltinRunner::new(false);
288
289 let mut vm = vm!();
290
291 vm.segments = segments![
292 ((0, 0), (0, 0)),
293 ((0, 1), (0, 1)),
294 ((2, 0), (0, 0)),
295 ((2, 1), (0, 0))
296 ];
297
298 vm.segments.segment_used_sizes = Some(vec![0]);
299
300 let pointer = Relocatable::from((2, 2));
301
302 assert_eq!(
303 builtin.final_stack(&vm.segments, pointer).unwrap(),
304 Relocatable::from((2, 2))
305 );
306 }
307
308 #[test]
309 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
310 fn final_stack_error_non_relocatable() {
311 let mut builtin = OutputBuiltinRunner::new(true);
312
313 let mut vm = vm!();
314
315 vm.segments = segments![
316 ((0, 0), (0, 0)),
317 ((0, 1), (0, 1)),
318 ((2, 0), (0, 0)),
319 ((2, 1), 2)
320 ];
321
322 vm.segments.segment_used_sizes = Some(vec![0]);
323
324 let pointer = Relocatable::from((2, 2));
325
326 assert_eq!(
327 builtin.final_stack(&vm.segments, pointer),
328 Err(RunnerError::NoStopPointer(Box::new(BuiltinName::output)))
329 );
330 }
331
332 #[test]
333 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
334 fn get_used_cells_and_allocated_size_test() {
335 let builtin: BuiltinRunner = OutputBuiltinRunner::new(true).into();
336
337 let mut vm = vm!();
338
339 vm.segments.segment_used_sizes = Some(vec![0]);
340
341 assert_eq!(
342 builtin.get_used_cells_and_allocated_size(&vm),
343 Ok((0_usize, 0))
344 );
345 }
346
347 #[test]
348 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
349 fn get_allocated_memory_units() {
350 let builtin = OutputBuiltinRunner::new(true);
351
352 let vm = vm!();
353
354 assert_eq!(builtin.get_allocated_memory_units(&vm), Ok(0));
355 }
356
357 #[test]
358 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
359 fn initialize_segments_for_output() {
360 let mut builtin = OutputBuiltinRunner::new(true);
361 let mut segments = MemorySegmentManager::new();
362 builtin.initialize_segments(&mut segments);
363 assert_eq!(builtin.base, 0);
364 }
365
366 #[test]
367 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
368 fn get_initial_stack_for_output_with_base() {
369 let mut builtin = OutputBuiltinRunner::new(true);
370 builtin.base = 1;
371 let initial_stack = builtin.initial_stack();
372 assert_eq!(
373 initial_stack[0].clone(),
374 MaybeRelocatable::RelocatableValue((builtin.base() as isize, 0).into())
375 );
376 assert_eq!(initial_stack.len(), 1);
377 }
378
379 #[test]
380 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
381 fn get_used_cells_missing_segment_used_sizes() {
382 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
383 let vm = vm!();
384
385 assert_eq!(
386 builtin.get_used_cells(&vm.segments),
387 Err(MemoryError::MissingSegmentUsedSizes)
388 );
389 }
390
391 #[test]
392 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
393 fn get_used_cells_empty() {
394 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
395 let mut vm = vm!();
396
397 vm.segments.segment_used_sizes = Some(vec![0]);
398 assert_eq!(builtin.get_used_cells(&vm.segments), Ok(0));
399 }
400
401 #[test]
402 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
403 fn get_used_cells() {
404 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
405 let mut vm = vm!();
406
407 vm.segments.segment_used_sizes = Some(vec![4]);
408 assert_eq!(builtin.get_used_cells(&vm.segments), Ok(4));
409 }
410
411 #[test]
412 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
413 fn test_get_used_instances_missing_segments() {
414 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
415 let memory_segment_manager = MemorySegmentManager::new();
416
417 assert_eq!(
418 builtin.get_used_instances(&memory_segment_manager),
419 Err(MemoryError::MissingSegmentUsedSizes)
420 );
421 }
422
423 #[test]
424 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
425 fn test_get_used_instances_valid() {
426 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
427 let mut memory_segment_manager = MemorySegmentManager::new();
428 memory_segment_manager.segment_used_sizes = Some(vec![0]);
429
430 assert_eq!(builtin.get_used_instances(&memory_segment_manager), Ok(0));
431 }
432
433 #[test]
434 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
435 fn test_deduce_memory_cell_output_builtin() {
436 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
437 let mut vm = vm!();
438
439 vm.segments = segments![
440 ((0, 0), (0, 0)),
441 ((0, 1), (0, 1)),
442 ((2, 0), (0, 0)),
443 ((2, 1), 2)
444 ];
445
446 vm.segments.segment_used_sizes = Some(vec![0]);
447
448 let pointer = Relocatable::from((2, 2));
449
450 assert_eq!(
451 builtin.deduce_memory_cell(pointer, &vm.segments.memory),
452 Ok(None)
453 );
454 }
455
456 #[test]
457 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
458 fn test_add_validation_rule() {
459 let builtin: BuiltinRunner = OutputBuiltinRunner::new(true).into();
460 let mut vm = vm!();
461
462 vm.segments = segments![
463 ((0, 0), (0, 0)),
464 ((0, 1), (0, 1)),
465 ((2, 0), (0, 0)),
466 ((2, 1), 2)
467 ];
468
469 vm.segments.segment_used_sizes = Some(vec![0]);
470 builtin.add_validation_rule(&mut vm.segments.memory);
471 }
472
473 #[test]
474 fn get_additional_data_no_pages_no_attributes() {
475 let builtin = OutputBuiltinRunner::new(true);
476 assert_eq!(
477 builtin.get_additional_data(),
478 BuiltinAdditionalData::Output(OutputBuiltinAdditionalData {
479 pages: BTreeMap::default(),
480 attributes: BTreeMap::default()
481 })
482 )
483 }
484
485 #[test]
486 #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
487 fn get_air_private_input() {
488 let builtin: BuiltinRunner = OutputBuiltinRunner::new(true).into();
489
490 let segments = segments![((0, 0), 0), ((0, 1), 1), ((0, 2), 2), ((0, 3), 3)];
491 assert!(builtin.air_private_input(&segments).is_empty());
492 }
493
494 #[test]
495 fn set_state() {
496 let mut builtin = OutputBuiltinRunner::new(true);
497 assert_eq!(builtin.base, 0);
498
499 let new_state = OutputBuiltinState {
500 base: 10,
501 base_offset: 0,
502 pages: BTreeMap::from([(1, PublicMemoryPage { start: 0, size: 3 })]),
503 attributes: BTreeMap::from([("gps_fact_topology".to_string(), vec![0, 2, 0])]),
504 };
505 builtin.set_state(new_state.clone());
506
507 assert_eq!(builtin.base, new_state.base);
508 assert_eq!(builtin.pages, new_state.pages);
509 assert_eq!(builtin.attributes, new_state.attributes);
510
511 let state = builtin.get_state();
512 assert_eq!(state, new_state);
513 }
514
515 #[test]
516 fn new_state() {
517 let mut builtin = OutputBuiltinRunner {
518 base: 10,
519 base_offset: 0,
520 pages: BTreeMap::from([(1, PublicMemoryPage { start: 0, size: 3 })]),
521 attributes: BTreeMap::from([("gps_fact_topology".to_string(), vec![0, 2, 0])]),
522 stop_ptr: Some(10),
523 included: true,
524 };
525
526 let new_base = 11;
527 let new_included = false;
528 builtin.new_state(new_base, 2, new_included);
529
530 assert_eq!(builtin.base, new_base);
531 assert_eq!(builtin.base_offset, 2);
532 assert!(builtin.pages.is_empty());
533 assert!(builtin.attributes.is_empty());
534 assert_eq!(builtin.stop_ptr, None);
535 assert_eq!(builtin.included, new_included);
536 }
537
538 #[test]
539 fn add_page() {
540 let mut builtin = OutputBuiltinRunner::new(true);
541 assert_eq!(
542 builtin.add_page(
543 1,
544 Relocatable {
545 segment_index: builtin.base() as isize,
546 offset: 0
547 },
548 3
549 ),
550 Ok(())
551 );
552
553 assert_eq!(
554 builtin.pages,
555 BTreeMap::from([(1, PublicMemoryPage { start: 0, size: 3 }),])
556 )
557 }
558
559 #[test]
560 fn add_page_wrong_segment() {
561 let mut builtin = OutputBuiltinRunner::new(true);
562 let page_start = Relocatable {
563 segment_index: 18,
564 offset: 0,
565 };
566
567 let result = builtin.add_page(1, page_start, 3);
568 assert!(
569 matches!(result, Err(RunnerError::PageNotOnSegment(relocatable, base)) if relocatable == page_start && base == builtin.base())
570 )
571 }
572
573 #[test]
574 pub fn add_attribute() {
575 let mut builtin = OutputBuiltinRunner::new(true);
576 assert!(builtin.attributes.is_empty());
577
578 let name = "gps_fact_topology".to_string();
579 let values = vec![0, 12, 30];
580 builtin.add_attribute(name.clone(), values.clone());
581
582 assert_eq!(builtin.attributes, BTreeMap::from([(name, values)]));
583 }
584
585 #[test]
586 fn get_public_memory() {
587 let mut builtin = OutputBuiltinRunner::new(true);
588
589 builtin
590 .add_page(
591 1,
592 Relocatable {
593 segment_index: builtin.base() as isize,
594 offset: 2,
595 },
596 2,
597 )
598 .unwrap();
599
600 builtin
601 .add_page(
602 2,
603 Relocatable {
604 segment_index: builtin.base() as isize,
605 offset: 4,
606 },
607 3,
608 )
609 .unwrap();
610
611 let mut segments = MemorySegmentManager::new();
612 segments.segment_used_sizes = Some(vec![7]);
613
614 let public_memory = builtin.get_public_memory(&segments).unwrap();
615 assert_eq!(
616 public_memory,
617 vec![(0, 0), (1, 0), (2, 1), (3, 1), (4, 2), (5, 2), (6, 2)]
618 );
619 }
620
621 #[test]
622 fn get_and_extend_additional_data() {
623 let builtin_a = OutputBuiltinRunner {
624 base: 0,
625 base_offset: 0,
626 pages: BTreeMap::from([(1, PublicMemoryPage { start: 0, size: 3 })]),
627 attributes: BTreeMap::from([("gps_fact_topology".to_string(), vec![0, 2, 0])]),
628 stop_ptr: None,
629 included: true,
630 };
631 let additional_data = builtin_a.get_additional_data();
632 let mut builtin_b = OutputBuiltinRunner {
633 base: 0,
634 base_offset: 0,
635 pages: Default::default(),
636 attributes: Default::default(),
637 stop_ptr: None,
638 included: true,
639 };
640 builtin_b.extend_additional_data(&additional_data).unwrap();
641 assert_eq!(builtin_a.attributes, builtin_b.attributes);
642 assert_eq!(builtin_a.pages, builtin_b.pages);
643 }
644}