1use crate::types::builtin_name::BuiltinName;
2use crate::types::relocatable::{MaybeRelocatable, Relocatable};
3use crate::vm::errors::memory_errors::MemoryError;
4use crate::vm::errors::runner_errors::RunnerError;
5use crate::vm::runners::cairo_pie::{
6 Attributes, BuiltinAdditionalData, OutputBuiltinAdditionalData, Pages, PublicMemoryPage,
7};
8use crate::vm::vm_core::VirtualMachine;
9use crate::vm::vm_memory::memory_segments::MemorySegmentManager;
10use std::collections::BTreeMap;
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 #[test]
219 fn get_used_instances() {
220 let builtin = OutputBuiltinRunner::new(true);
221
222 let mut vm = vm!();
223 vm.segments.segment_used_sizes = Some(vec![1]);
224
225 assert_eq!(builtin.get_used_instances(&vm.segments), Ok(1));
226 }
227
228 #[test]
229 fn final_stack() {
230 let mut builtin = OutputBuiltinRunner::new(true);
231
232 let mut vm = vm!();
233
234 vm.segments = segments![
235 ((0, 0), (0, 0)),
236 ((0, 1), (0, 1)),
237 ((2, 0), (0, 0)),
238 ((2, 1), (0, 0))
239 ];
240
241 vm.segments.segment_used_sizes = Some(vec![0]);
242
243 let pointer = Relocatable::from((2, 2));
244
245 assert_eq!(
246 builtin.final_stack(&vm.segments, pointer).unwrap(),
247 Relocatable::from((2, 1))
248 );
249 }
250
251 #[test]
252 fn final_stack_error_stop_pointer() {
253 let mut builtin = OutputBuiltinRunner::new(true);
254
255 let mut vm = vm!();
256
257 vm.segments = segments![
258 ((0, 0), (0, 0)),
259 ((0, 1), (0, 1)),
260 ((2, 0), (0, 0)),
261 ((2, 1), (0, 0))
262 ];
263
264 vm.segments.segment_used_sizes = Some(vec![998]);
265
266 let pointer = Relocatable::from((2, 2));
267
268 assert_eq!(
269 builtin.final_stack(&vm.segments, pointer),
270 Err(RunnerError::InvalidStopPointer(Box::new((
271 BuiltinName::output,
272 relocatable!(0, 998),
273 relocatable!(0, 0)
274 ))))
275 );
276 }
277
278 #[test]
279 fn final_stack_error_when_notincluded() {
280 let mut builtin = OutputBuiltinRunner::new(false);
281
282 let mut vm = vm!();
283
284 vm.segments = segments![
285 ((0, 0), (0, 0)),
286 ((0, 1), (0, 1)),
287 ((2, 0), (0, 0)),
288 ((2, 1), (0, 0))
289 ];
290
291 vm.segments.segment_used_sizes = Some(vec![0]);
292
293 let pointer = Relocatable::from((2, 2));
294
295 assert_eq!(
296 builtin.final_stack(&vm.segments, pointer).unwrap(),
297 Relocatable::from((2, 2))
298 );
299 }
300
301 #[test]
302 fn final_stack_error_non_relocatable() {
303 let mut builtin = OutputBuiltinRunner::new(true);
304
305 let mut vm = vm!();
306
307 vm.segments = segments![
308 ((0, 0), (0, 0)),
309 ((0, 1), (0, 1)),
310 ((2, 0), (0, 0)),
311 ((2, 1), 2)
312 ];
313
314 vm.segments.segment_used_sizes = Some(vec![0]);
315
316 let pointer = Relocatable::from((2, 2));
317
318 assert_eq!(
319 builtin.final_stack(&vm.segments, pointer),
320 Err(RunnerError::NoStopPointer(Box::new(BuiltinName::output)))
321 );
322 }
323
324 #[test]
325 fn get_used_cells_and_allocated_size_test() {
326 let builtin: BuiltinRunner = OutputBuiltinRunner::new(true).into();
327
328 let mut vm = vm!();
329
330 vm.segments.segment_used_sizes = Some(vec![0]);
331
332 assert_eq!(
333 builtin.get_used_cells_and_allocated_size(&vm),
334 Ok((0_usize, 0))
335 );
336 }
337
338 #[test]
339 fn get_allocated_memory_units() {
340 let builtin = OutputBuiltinRunner::new(true);
341
342 let vm = vm!();
343
344 assert_eq!(builtin.get_allocated_memory_units(&vm), Ok(0));
345 }
346
347 #[test]
348 fn initialize_segments_for_output() {
349 let mut builtin = OutputBuiltinRunner::new(true);
350 let mut segments = MemorySegmentManager::new();
351 builtin.initialize_segments(&mut segments);
352 assert_eq!(builtin.base, 0);
353 }
354
355 #[test]
356 fn get_initial_stack_for_output_with_base() {
357 let mut builtin = OutputBuiltinRunner::new(true);
358 builtin.base = 1;
359 let initial_stack = builtin.initial_stack();
360 assert_eq!(
361 initial_stack[0].clone(),
362 MaybeRelocatable::RelocatableValue((builtin.base() as isize, 0).into())
363 );
364 assert_eq!(initial_stack.len(), 1);
365 }
366
367 #[test]
368 fn get_used_cells_missing_segment_used_sizes() {
369 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
370 let vm = vm!();
371
372 assert_eq!(
373 builtin.get_used_cells(&vm.segments),
374 Err(MemoryError::MissingSegmentUsedSizes)
375 );
376 }
377
378 #[test]
379 fn get_used_cells_empty() {
380 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
381 let mut vm = vm!();
382
383 vm.segments.segment_used_sizes = Some(vec![0]);
384 assert_eq!(builtin.get_used_cells(&vm.segments), Ok(0));
385 }
386
387 #[test]
388 fn get_used_cells() {
389 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
390 let mut vm = vm!();
391
392 vm.segments.segment_used_sizes = Some(vec![4]);
393 assert_eq!(builtin.get_used_cells(&vm.segments), Ok(4));
394 }
395
396 #[test]
397 fn test_get_used_instances_missing_segments() {
398 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
399 let memory_segment_manager = MemorySegmentManager::new();
400
401 assert_eq!(
402 builtin.get_used_instances(&memory_segment_manager),
403 Err(MemoryError::MissingSegmentUsedSizes)
404 );
405 }
406
407 #[test]
408 fn test_get_used_instances_valid() {
409 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
410 let mut memory_segment_manager = MemorySegmentManager::new();
411 memory_segment_manager.segment_used_sizes = Some(vec![0]);
412
413 assert_eq!(builtin.get_used_instances(&memory_segment_manager), Ok(0));
414 }
415
416 #[test]
417 fn test_deduce_memory_cell_output_builtin() {
418 let builtin = BuiltinRunner::Output(OutputBuiltinRunner::new(true));
419 let mut vm = vm!();
420
421 vm.segments = segments![
422 ((0, 0), (0, 0)),
423 ((0, 1), (0, 1)),
424 ((2, 0), (0, 0)),
425 ((2, 1), 2)
426 ];
427
428 vm.segments.segment_used_sizes = Some(vec![0]);
429
430 let pointer = Relocatable::from((2, 2));
431
432 assert_eq!(
433 builtin.deduce_memory_cell(pointer, &vm.segments.memory),
434 Ok(None)
435 );
436 }
437
438 #[test]
439 fn test_add_validation_rule() {
440 let builtin: BuiltinRunner = OutputBuiltinRunner::new(true).into();
441 let mut vm = vm!();
442
443 vm.segments = segments![
444 ((0, 0), (0, 0)),
445 ((0, 1), (0, 1)),
446 ((2, 0), (0, 0)),
447 ((2, 1), 2)
448 ];
449
450 vm.segments.segment_used_sizes = Some(vec![0]);
451 builtin.add_validation_rule(&mut vm.segments.memory);
452 }
453
454 #[test]
455 fn get_additional_data_no_pages_no_attributes() {
456 let builtin = OutputBuiltinRunner::new(true);
457 assert_eq!(
458 builtin.get_additional_data(),
459 BuiltinAdditionalData::Output(OutputBuiltinAdditionalData {
460 pages: BTreeMap::default(),
461 attributes: BTreeMap::default()
462 })
463 )
464 }
465
466 #[test]
467 fn get_air_private_input() {
468 let builtin: BuiltinRunner = OutputBuiltinRunner::new(true).into();
469
470 let segments = segments![((0, 0), 0), ((0, 1), 1), ((0, 2), 2), ((0, 3), 3)];
471 assert!(builtin.air_private_input(&segments).is_empty());
472 }
473
474 #[test]
475 fn set_state() {
476 let mut builtin = OutputBuiltinRunner::new(true);
477 assert_eq!(builtin.base, 0);
478
479 let new_state = OutputBuiltinState {
480 base: 10,
481 base_offset: 0,
482 pages: BTreeMap::from([(1, PublicMemoryPage { start: 0, size: 3 })]),
483 attributes: BTreeMap::from([("gps_fact_topology".to_string(), vec![0, 2, 0])]),
484 };
485 builtin.set_state(new_state.clone());
486
487 assert_eq!(builtin.base, new_state.base);
488 assert_eq!(builtin.pages, new_state.pages);
489 assert_eq!(builtin.attributes, new_state.attributes);
490
491 let state = builtin.get_state();
492 assert_eq!(state, new_state);
493 }
494
495 #[test]
496 fn new_state() {
497 let mut builtin = OutputBuiltinRunner {
498 base: 10,
499 base_offset: 0,
500 pages: BTreeMap::from([(1, PublicMemoryPage { start: 0, size: 3 })]),
501 attributes: BTreeMap::from([("gps_fact_topology".to_string(), vec![0, 2, 0])]),
502 stop_ptr: Some(10),
503 included: true,
504 };
505
506 let new_base = 11;
507 let new_included = false;
508 builtin.new_state(new_base, 2, new_included);
509
510 assert_eq!(builtin.base, new_base);
511 assert_eq!(builtin.base_offset, 2);
512 assert!(builtin.pages.is_empty());
513 assert!(builtin.attributes.is_empty());
514 assert_eq!(builtin.stop_ptr, None);
515 assert_eq!(builtin.included, new_included);
516 }
517
518 #[test]
519 fn add_page() {
520 let mut builtin = OutputBuiltinRunner::new(true);
521 assert_eq!(
522 builtin.add_page(
523 1,
524 Relocatable {
525 segment_index: builtin.base() as isize,
526 offset: 0
527 },
528 3
529 ),
530 Ok(())
531 );
532
533 assert_eq!(
534 builtin.pages,
535 BTreeMap::from([(1, PublicMemoryPage { start: 0, size: 3 }),])
536 )
537 }
538
539 #[test]
540 fn add_page_wrong_segment() {
541 let mut builtin = OutputBuiltinRunner::new(true);
542 let page_start = Relocatable {
543 segment_index: 18,
544 offset: 0,
545 };
546
547 let result = builtin.add_page(1, page_start, 3);
548 assert!(
549 matches!(result, Err(RunnerError::PageNotOnSegment(relocatable, base)) if relocatable == page_start && base == builtin.base())
550 )
551 }
552
553 #[test]
554 pub fn add_attribute() {
555 let mut builtin = OutputBuiltinRunner::new(true);
556 assert!(builtin.attributes.is_empty());
557
558 let name = "gps_fact_topology".to_string();
559 let values = vec![0, 12, 30];
560 builtin.add_attribute(name.clone(), values.clone());
561
562 assert_eq!(builtin.attributes, BTreeMap::from([(name, values)]));
563 }
564
565 #[test]
566 fn get_public_memory() {
567 let mut builtin = OutputBuiltinRunner::new(true);
568
569 builtin
570 .add_page(
571 1,
572 Relocatable {
573 segment_index: builtin.base() as isize,
574 offset: 2,
575 },
576 2,
577 )
578 .unwrap();
579
580 builtin
581 .add_page(
582 2,
583 Relocatable {
584 segment_index: builtin.base() as isize,
585 offset: 4,
586 },
587 3,
588 )
589 .unwrap();
590
591 let mut segments = MemorySegmentManager::new();
592 segments.segment_used_sizes = Some(vec![7]);
593
594 let public_memory = builtin.get_public_memory(&segments).unwrap();
595 assert_eq!(
596 public_memory,
597 vec![(0, 0), (1, 0), (2, 1), (3, 1), (4, 2), (5, 2), (6, 2)]
598 );
599 }
600
601 #[test]
602 fn get_and_extend_additional_data() {
603 let builtin_a = OutputBuiltinRunner {
604 base: 0,
605 base_offset: 0,
606 pages: BTreeMap::from([(1, PublicMemoryPage { start: 0, size: 3 })]),
607 attributes: BTreeMap::from([("gps_fact_topology".to_string(), vec![0, 2, 0])]),
608 stop_ptr: None,
609 included: true,
610 };
611 let additional_data = builtin_a.get_additional_data();
612 let mut builtin_b = OutputBuiltinRunner {
613 base: 0,
614 base_offset: 0,
615 pages: Default::default(),
616 attributes: Default::default(),
617 stop_ptr: None,
618 included: true,
619 };
620 builtin_b.extend_additional_data(&additional_data).unwrap();
621 assert_eq!(builtin_a.attributes, builtin_b.attributes);
622 assert_eq!(builtin_a.pages, builtin_b.pages);
623 }
624}