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