oxygengine_script_flow/
vm.rs

1use crate::{ast, ast::*, Guid};
2use core::prefab::{PrefabNumber, PrefabValue};
3use petgraph::{
4    algo::{has_path_connecting, toposort},
5    Direction, Graph,
6};
7use std::{
8    collections::{BTreeMap, HashMap},
9    ops::{Deref, DerefMut},
10    sync::{Arc, RwLock, RwLockReadGuard, RwLockWriteGuard},
11};
12
13const VERSION: usize = 1;
14const VERSION_MIN: usize = 1;
15
16#[derive(Debug, Clone)]
17pub struct Reference(pub Arc<RwLock<Value>>);
18
19impl Reference {
20    pub fn new(inner: Arc<RwLock<Value>>) -> Self {
21        Self(inner)
22    }
23
24    pub fn value(value: Value) -> Self {
25        Self(Arc::new(RwLock::new(value)))
26    }
27
28    pub fn into_inner(self) -> Value {
29        (*self.read()).clone()
30    }
31
32    pub fn read(&self) -> RwLockReadGuard<Value> {
33        self.0.read().unwrap()
34    }
35
36    pub fn write(&mut self) -> RwLockWriteGuard<Value> {
37        self.0.write().unwrap()
38    }
39}
40
41impl PartialEq for Reference {
42    fn eq(&self, other: &Self) -> bool {
43        if let Ok(a) = self.0.try_read() {
44            if let Ok(b) = other.0.try_read() {
45                return *a == *b;
46            }
47        }
48        false
49    }
50}
51
52impl Deref for Reference {
53    type Target = Arc<RwLock<Value>>;
54
55    fn deref(&self) -> &Self::Target {
56        &self.0
57    }
58}
59
60impl DerefMut for Reference {
61    fn deref_mut(&mut self) -> &mut Self::Target {
62        &mut self.0
63    }
64}
65
66#[derive(Debug, Clone)]
67pub enum Value {
68    None,
69    Bool(bool),
70    Number(PrefabNumber),
71    String(String),
72    List(Vec<Reference>),
73    Object(BTreeMap<String, Reference>),
74}
75
76impl PartialEq for Value {
77    fn eq(&self, other: &Self) -> bool {
78        match (self, other) {
79            (Self::None, Self::None) => true,
80            (Self::Bool(a), Self::Bool(b)) => a == b,
81            (Self::Number(a), Self::Number(b)) => a == b,
82            (Self::String(a), Self::String(b)) => a == b,
83            (Self::List(a), Self::List(b)) => a == b,
84            (Self::Object(a), Self::Object(b)) => a == b,
85            _ => false,
86        }
87    }
88}
89
90impl From<PrefabValue> for Value {
91    fn from(value: PrefabValue) -> Self {
92        match value {
93            PrefabValue::Null => Value::None,
94            PrefabValue::Bool(v) => Value::Bool(v),
95            PrefabValue::Number(v) => Value::Number(v),
96            PrefabValue::String(v) => Value::String(v),
97            PrefabValue::Sequence(v) => {
98                Value::List(v.into_iter().map(|v| Reference::value(v.into())).collect())
99            }
100            PrefabValue::Mapping(v) => Value::Object(
101                v.into_iter()
102                    .map(|(k, v)| {
103                        // TODO: return error instead of panicking.
104                        let k = if let PrefabValue::String(k) = k {
105                            k
106                        } else {
107                            panic!("Mapping key is not a string: {:?}", k);
108                        };
109                        let v = Reference::value(v.into());
110                        (k, v)
111                    })
112                    .collect(),
113            ),
114        }
115    }
116}
117
118impl From<Value> for PrefabValue {
119    fn from(v: Value) -> Self {
120        match v {
121            Value::None => Self::Null,
122            Value::Bool(v) => Self::Bool(v),
123            Value::Number(v) => Self::Number(v),
124            Value::String(v) => Self::String(v),
125            Value::List(v) => {
126                Self::Sequence(v.into_iter().map(|v| v.read().clone().into()).collect())
127            }
128            Value::Object(v) => Self::Mapping(
129                v.into_iter()
130                    .map(|(k, v)| {
131                        let k = Self::String(k);
132                        let v = v.read().clone().into();
133                        (k, v)
134                    })
135                    .collect(),
136            ),
137        }
138    }
139}
140
141impl From<Value> for Reference {
142    fn from(v: Value) -> Self {
143        Self::value(v)
144    }
145}
146
147#[derive(Debug)]
148pub enum VmError {
149    /// (program version, virtual machine version)
150    ProgramCompiledForDifferentVersion(usize, usize),
151    Message(String),
152    FoundCycleInFlowGraph,
153    /// (expected, provided)
154    WrongNumberOfInputs(usize, usize),
155    /// (expected, provided)
156    WrongNumberOfOutputs(usize, usize),
157    CouldNotRunEvent(String),
158    CouldNotCallFunction(ast::Reference),
159    CouldNotCallMethod(ast::Reference, ast::Reference),
160    EventDoesNotExists(ast::Reference),
161    NodeDoesNotExists(ast::Reference),
162    TypeDoesNotExists(ast::Reference),
163    TraitDoesNotExists(ast::Reference),
164    MethodDoesNotExists(ast::Reference),
165    FunctionDoesNotExists(ast::Reference),
166    /// (type guid, method guid)
167    TypeDoesNotImplementMethod(ast::Reference, ast::Reference),
168    InstanceDoesNotExists,
169    GlobalVariableDoesNotExists(ast::Reference),
170    LocalVariableDoesNotExists(ast::Reference),
171    InputDoesNotExists(usize),
172    OutputDoesNotExists(usize),
173    StackUnderflow,
174    OperationDoesNotExists(ast::Reference),
175    OperationIsNotRegistered(String),
176    /// (expected, provided, list)
177    IndexOutOfBounds(usize, usize, Reference),
178    ObjectKeyDoesNotExists(String, Reference),
179    ValueIsNotAList(Reference),
180    ValueIsNotAnObject(Reference),
181    ValueIsNotABool(Reference),
182    TryingToPerformInvalidNodeType(NodeType),
183    /// (source value, destination value)
184    TryingToWriteBorrowedReference(Reference, Reference),
185    TryingToReadBorrowedReference(Reference),
186    NodeNotFoundInExecutionPipeline(ast::Reference),
187    NodeIsNotALoop(ast::Reference),
188    NodeIsNotAnIfElse(ast::Reference),
189    TryingToBreakIfElse,
190    TryingToContinueIfElse,
191    ThereAreNoCachedNodeOutputs(ast::Reference),
192    ThereIsNoCachedNodeIndexedOutput(Link),
193    FoundMultipleEntryNodes(Vec<ast::Reference>),
194    EntryNodeNotFound,
195    FoundNodeWithInvalidIdentifier,
196    NodeCannotFlowIn(ast::Reference),
197    NodeCannotFlowOut(ast::Reference),
198    NodeCannotTakeInput(ast::Reference),
199    NodeCannotGiveOutput(ast::Reference),
200}
201
202#[derive(Debug)]
203pub enum VmOperationError {
204    CouldNotPerformOperation {
205        message: String,
206        name: String,
207        inputs: Vec<Value>,
208    },
209}
210
211pub struct Vm {
212    ast: Program,
213    operations: HashMap<String, Box<dyn VmOperation>>,
214    variables: HashMap<String, Reference>,
215    running_events: HashMap<Guid, VmEvent>,
216    completed_events: HashMap<Guid, Vec<Reference>>,
217    /// {event name: [nodes reference]}
218    event_execution_order: HashMap<String, Vec<ast::Reference>>,
219    /// {(type name, method name): [node reference]}
220    method_execution_order: HashMap<(String, String), Vec<ast::Reference>>,
221    /// {event name: [nodes reference]}
222    function_execution_order: HashMap<String, Vec<ast::Reference>>,
223    /// {type name: {method name: (trait name, is implemented by type)}}
224    type_methods: HashMap<String, HashMap<String, (String, bool)>>,
225    end_nodes: Vec<ast::Reference>,
226}
227
228impl Vm {
229    pub fn new(ast: Program) -> Result<Self, VmError> {
230        if ast.version < VERSION_MIN || ast.version > VERSION {
231            return Err(VmError::ProgramCompiledForDifferentVersion(
232                ast.version,
233                VERSION,
234            ));
235        }
236        let type_methods = ast
237            .types
238            .iter()
239            .map(|type_| {
240                let mut map = HashMap::new();
241                for (trait_name, methods) in &type_.traits_implementation {
242                    if let Some(trait_) = ast.traits.iter().find(|t| &t.name == trait_name) {
243                        for trait_method in &trait_.methods {
244                            let b = methods.iter().any(|m| m.name == trait_method.name);
245                            map.insert(trait_method.name.clone(), (trait_name.clone(), b));
246                        }
247                    } else {
248                        return Err(VmError::TraitDoesNotExists(ast::Reference::Named(
249                            trait_name.clone(),
250                        )));
251                    }
252                }
253                Ok((type_.name.clone(), map))
254            })
255            .collect::<Result<HashMap<_, _>, _>>()?;
256        let mut end_nodes = vec![];
257        let event_execution_order = ast
258            .events
259            .iter()
260            .map(|event| {
261                let mut graph = Graph::<ast::Reference, ()>::new();
262                let nodes_map = event
263                    .nodes
264                    .iter()
265                    .map(|node| (node.id.clone(), graph.add_node(node.id.clone())))
266                    .collect::<HashMap<_, _>>();
267                for node in &event.nodes {
268                    if node.id == ast::Reference::None {
269                        return Err(VmError::FoundNodeWithInvalidIdentifier);
270                    }
271                    let (can_input, _, _, can_out) = node.node_type.is_input_output_flow_in_out();
272                    if node.next_node != ast::Reference::None {
273                        if !can_out {
274                            return Err(VmError::NodeCannotFlowOut(node.id.clone()));
275                        }
276                        if let Some(n) = event.nodes.iter().find(|n| n.id == node.next_node) {
277                            let (_, _, can_in2, _) = n.node_type.is_input_output_flow_in_out();
278                            if !can_in2 {
279                                return Err(VmError::NodeCannotFlowIn(n.id.clone()));
280                            }
281                        }
282                    }
283                    if !node.input_links.is_empty() {
284                        if !can_input {
285                            return Err(VmError::NodeCannotTakeInput(node.id.clone()));
286                        }
287                        for link in &node.input_links {
288                            match link {
289                                Link::NodeIndexed(id, _) => {
290                                    if let Some(n) = event.nodes.iter().find(|n| &n.id == id) {
291                                        let (_, can_output2, _, _) =
292                                            n.node_type.is_input_output_flow_in_out();
293                                        if !can_output2 {
294                                            return Err(VmError::NodeCannotGiveOutput(
295                                                n.id.clone(),
296                                            ));
297                                        }
298                                    }
299                                }
300                                Link::None => {}
301                            }
302                        }
303                    }
304                    let to = if let Some(node) = nodes_map.get(&node.next_node) {
305                        *node
306                    } else {
307                        continue;
308                    };
309                    let from = if let Some(node) = nodes_map.get(&node.id) {
310                        *node
311                    } else {
312                        return Err(VmError::NodeDoesNotExists(node.id.clone()));
313                    };
314                    graph.add_edge(from, to, ());
315                    for link in &node.input_links {
316                        match link {
317                            Link::NodeIndexed(id, _) => {
318                                let from = *nodes_map.get(id).unwrap();
319                                let to = *nodes_map.get(&node.id).unwrap();
320                                graph.add_edge(from, to, ());
321                            }
322                            Link::None => {}
323                        }
324                    }
325                }
326                let list = {
327                    let indices = match toposort(&graph, None) {
328                        Ok(list) => Ok(list),
329                        Err(_) => Err(VmError::FoundCycleInFlowGraph),
330                    }?;
331                    let list = indices
332                        .iter()
333                        .map(|index| {
334                            nodes_map
335                                .iter()
336                                .find(|(_, v)| *v == index)
337                                .unwrap()
338                                .0
339                                .clone()
340                        })
341                        .collect::<Vec<_>>();
342                    let entry_pos = {
343                        let entries = event
344                            .nodes
345                            .iter()
346                            .filter(|n| n.node_type.is_entry())
347                            .map(|n| n.id.clone())
348                            .collect::<Vec<_>>();
349                        if entries.is_empty() {
350                            return Err(VmError::EntryNodeNotFound);
351                        } else if entries.len() > 1 {
352                            return Err(VmError::FoundMultipleEntryNodes(entries));
353                        }
354                        list.iter().position(|n| n == &entries[0]).unwrap()
355                    };
356                    let mut from_pos = entry_pos;
357                    let mut to_pos = entry_pos;
358                    for i in (0..entry_pos).rev() {
359                        let idx = indices[i];
360                        if graph.externals(Direction::Incoming).any(|n| n == idx)
361                            && !has_path_connecting(&graph, idx, indices[entry_pos], None)
362                        {
363                            break;
364                        }
365                        from_pos = i;
366                    }
367                    for i in (entry_pos + 1)..list.len() {
368                        let idx = indices[i];
369                        if graph.externals(Direction::Outgoing).any(|n| n == idx)
370                            && !has_path_connecting(&graph, indices[entry_pos], indices[i], None)
371                        {
372                            break;
373                        }
374                        to_pos = i;
375                    }
376                    list[from_pos..=to_pos].to_vec()
377                };
378                end_nodes.extend(graph.externals(Direction::Outgoing).map(|index| {
379                    nodes_map
380                        .iter()
381                        .find(|(_, v)| **v == index)
382                        .unwrap()
383                        .0
384                        .clone()
385                }));
386                Ok((event.name.clone(), list))
387            })
388            .collect::<Result<HashMap<_, _>, _>>()?;
389        let method_execution_order = {
390            let mut result = HashMap::new();
391            for type_ in &ast.types {
392                for (trait_name, methods) in &type_.traits_implementation {
393                    if let Some(trait_) = ast.traits.iter().find(|t| &t.name == trait_name) {
394                        for method in &trait_.methods {
395                            let method = if let Some(method) =
396                                methods.iter().find(|m| m.name == method.name)
397                            {
398                                method
399                            } else {
400                                method
401                            };
402                            let mut graph = Graph::<ast::Reference, ()>::new();
403                            let nodes_map = method
404                                .nodes
405                                .iter()
406                                .map(|node| (node.id.clone(), graph.add_node(node.id.clone())))
407                                .collect::<HashMap<_, _>>();
408                            for node in &method.nodes {
409                                let to = *nodes_map.get(&node.next_node).unwrap();
410                                let from = *nodes_map.get(&node.id).unwrap();
411                                graph.add_edge(from, to, ());
412                                for link in &node.input_links {
413                                    match link {
414                                        Link::NodeIndexed(id, _) => {
415                                            let to = *nodes_map.get(&node.id).unwrap();
416                                            let from = *nodes_map.get(id).unwrap();
417                                            graph.add_edge(from, to, ());
418                                        }
419                                        Link::None => {}
420                                    }
421                                }
422                            }
423                            let list = {
424                                let indices = match toposort(&graph, None) {
425                                    Ok(list) => Ok(list),
426                                    Err(_) => Err(VmError::FoundCycleInFlowGraph),
427                                }?;
428                                let list = indices
429                                    .iter()
430                                    .map(|index| {
431                                        nodes_map
432                                            .iter()
433                                            .find(|(_, v)| *v == index)
434                                            .unwrap()
435                                            .0
436                                            .clone()
437                                    })
438                                    .collect::<Vec<_>>();
439                                let entry_pos = {
440                                    let entries = method
441                                        .nodes
442                                        .iter()
443                                        .filter(|n| n.node_type.is_entry())
444                                        .map(|n| n.id.clone())
445                                        .collect::<Vec<_>>();
446                                    if entries.is_empty() {
447                                        return Err(VmError::EntryNodeNotFound);
448                                    } else if entries.len() > 1 {
449                                        return Err(VmError::FoundMultipleEntryNodes(entries));
450                                    }
451                                    list.iter().position(|n| n == &entries[0]).unwrap()
452                                };
453                                let mut from_pos = entry_pos;
454                                let mut to_pos = entry_pos;
455                                for i in (0..entry_pos).rev() {
456                                    let idx = indices[i];
457                                    if graph.externals(Direction::Incoming).any(|n| n == idx)
458                                        && !has_path_connecting(
459                                            &graph,
460                                            idx,
461                                            indices[entry_pos],
462                                            None,
463                                        )
464                                    {
465                                        break;
466                                    }
467                                    from_pos = i;
468                                }
469                                for i in (entry_pos + 1)..list.len() {
470                                    let idx = indices[i];
471                                    if graph.externals(Direction::Outgoing).any(|n| n == idx)
472                                        && !has_path_connecting(
473                                            &graph,
474                                            indices[entry_pos],
475                                            indices[i],
476                                            None,
477                                        )
478                                    {
479                                        break;
480                                    }
481                                    to_pos = i;
482                                }
483                                list[from_pos..=to_pos].to_vec()
484                            };
485                            end_nodes.extend(graph.externals(Direction::Outgoing).map(|index| {
486                                nodes_map
487                                    .iter()
488                                    .find(|(_, v)| **v == index)
489                                    .unwrap()
490                                    .0
491                                    .clone()
492                            }));
493                            result.insert((type_.name.clone(), method.name.clone()), list);
494                        }
495                    }
496                }
497            }
498            result
499        };
500        let function_execution_order = ast
501            .functions
502            .iter()
503            .map(|function| {
504                let mut graph = Graph::<ast::Reference, ()>::new();
505                let nodes_map = function
506                    .nodes
507                    .iter()
508                    .map(|node| (node.id.clone(), graph.add_node(node.id.clone())))
509                    .collect::<HashMap<_, _>>();
510                for node in &function.nodes {
511                    let to = *nodes_map.get(&node.next_node).unwrap();
512                    let from = *nodes_map.get(&node.id).unwrap();
513                    graph.add_edge(from, to, ());
514                    for link in &node.input_links {
515                        match link {
516                            Link::NodeIndexed(id, _) => {
517                                let to = *nodes_map.get(&node.id).unwrap();
518                                let from = *nodes_map.get(id).unwrap();
519                                graph.add_edge(from, to, ());
520                            }
521                            Link::None => {}
522                        }
523                    }
524                }
525                let list = {
526                    let indices = match toposort(&graph, None) {
527                        Ok(list) => Ok(list),
528                        Err(_) => Err(VmError::FoundCycleInFlowGraph),
529                    }?;
530                    let list = indices
531                        .iter()
532                        .map(|index| {
533                            nodes_map
534                                .iter()
535                                .find(|(_, v)| *v == index)
536                                .unwrap()
537                                .0
538                                .clone()
539                        })
540                        .collect::<Vec<_>>();
541                    let entry_pos = {
542                        let entries = function
543                            .nodes
544                            .iter()
545                            .filter(|n| n.node_type.is_entry())
546                            .map(|n| n.id.clone())
547                            .collect::<Vec<_>>();
548                        if entries.is_empty() {
549                            return Err(VmError::EntryNodeNotFound);
550                        } else if entries.len() > 1 {
551                            return Err(VmError::FoundMultipleEntryNodes(entries));
552                        }
553                        list.iter().position(|n| n == &entries[0]).unwrap()
554                    };
555                    let mut from_pos = entry_pos;
556                    let mut to_pos = entry_pos;
557                    for i in (0..entry_pos).rev() {
558                        let idx = indices[i];
559                        if graph.externals(Direction::Incoming).any(|n| n == idx)
560                            && !has_path_connecting(&graph, idx, indices[entry_pos], None)
561                        {
562                            break;
563                        }
564                        from_pos = i;
565                    }
566                    for i in (entry_pos + 1)..list.len() {
567                        let idx = indices[i];
568                        if graph.externals(Direction::Outgoing).any(|n| n == idx)
569                            && !has_path_connecting(&graph, indices[entry_pos], indices[i], None)
570                        {
571                            break;
572                        }
573                        to_pos = i;
574                    }
575                    list[from_pos..=to_pos].to_vec()
576                };
577                end_nodes.extend(graph.externals(Direction::Outgoing).map(|index| {
578                    nodes_map
579                        .iter()
580                        .find(|(_, v)| **v == index)
581                        .unwrap()
582                        .0
583                        .clone()
584                }));
585                Ok((function.name.clone(), list))
586            })
587            .collect::<Result<HashMap<_, _>, _>>()?;
588        let variables = ast
589            .variables
590            .iter()
591            .map(|v| (v.name.clone(), Value::None.into()))
592            .collect();
593        let result = Self {
594            ast,
595            operations: Default::default(),
596            variables,
597            running_events: Default::default(),
598            completed_events: Default::default(),
599            event_execution_order,
600            method_execution_order,
601            function_execution_order,
602            type_methods,
603            end_nodes,
604        };
605        Ok(result)
606    }
607
608    pub fn version_range() -> (usize, usize) {
609        (VERSION_MIN, VERSION)
610    }
611
612    pub fn register_operation<T>(&mut self, name: &str, operator: T)
613    where
614        T: VmOperation + 'static,
615    {
616        self.operations.insert(name.to_owned(), Box::new(operator));
617    }
618
619    pub fn unregister_operator(&mut self, name: &str) -> bool {
620        self.operations.remove(name).is_some()
621    }
622
623    pub fn global_variable_value(&self, name: &str) -> Result<Reference, VmError> {
624        if let Some(value) = self.variables.get(name) {
625            Ok(value.clone())
626        } else {
627            Err(VmError::GlobalVariableDoesNotExists(ast::Reference::Named(
628                name.to_owned(),
629            )))
630        }
631    }
632
633    pub fn set_global_variable_value(
634        &mut self,
635        name: &str,
636        value: Reference,
637    ) -> Result<Reference, VmError> {
638        if let Some(v) = self.variables.get_mut(name) {
639            Ok(std::mem::replace(v, value))
640        } else {
641            Err(VmError::GlobalVariableDoesNotExists(ast::Reference::Named(
642                name.to_owned(),
643            )))
644        }
645    }
646
647    pub fn run_event(&mut self, name: &str, inputs: Vec<Reference>) -> Result<Guid, VmError> {
648        if let Some(e) = self.ast.events.iter().find(|e| e.name == name) {
649            if e.input_constrains.len() != inputs.len() {
650                return Err(VmError::WrongNumberOfInputs(
651                    e.input_constrains.len(),
652                    inputs.len(),
653                ));
654            }
655            let guid = Guid::default();
656            if let Some((_, execution)) = self
657                .event_execution_order
658                .iter()
659                .find(|(k, _)| e.name == **k)
660            {
661                let vars = e
662                    .variables
663                    .iter()
664                    .map(|v| v.name.clone())
665                    .collect::<Vec<_>>();
666                self.running_events.insert(
667                    guid,
668                    VmEvent::new(
669                        e.name.clone(),
670                        execution.clone(),
671                        vars,
672                        inputs,
673                        e.output_constrains.len(),
674                    ),
675                );
676            } else {
677                return Err(VmError::CouldNotRunEvent(name.to_owned()));
678            }
679            Ok(guid)
680        } else {
681            Err(VmError::CouldNotRunEvent(name.to_owned()))
682        }
683    }
684
685    pub fn destroy_event(&mut self, guid: Guid) -> Result<(), VmError> {
686        if self.running_events.remove(&guid).is_some() {
687            self.completed_events.insert(guid, vec![]);
688            Ok(())
689        } else {
690            Err(VmError::EventDoesNotExists(ast::Reference::Guid(guid)))
691        }
692    }
693
694    pub fn get_completed_event(&mut self, guid: Guid) -> Option<Vec<Reference>> {
695        self.completed_events.remove(&guid)
696    }
697
698    pub fn get_completed_events(&mut self) -> impl Iterator<Item = (Guid, Vec<Reference>)> {
699        std::mem::take(&mut self.completed_events).into_iter()
700    }
701
702    pub fn process_events(&mut self) -> Result<(), VmError> {
703        let count = self.running_events.len();
704        let events = std::mem::replace(&mut self.running_events, HashMap::with_capacity(count));
705        let mut error = None;
706        for (key, mut event) in events {
707            if error.is_some() {
708                self.running_events.insert(key, event);
709            } else {
710                match self.process_event(&mut event) {
711                    Ok(status) => {
712                        if status {
713                            self.running_events.insert(key, event);
714                        } else {
715                            self.completed_events.insert(key, event.outputs);
716                        }
717                    }
718                    Err(err) => error = Some(err),
719                }
720            }
721        }
722        if let Some(error) = error {
723            Err(error)
724        } else {
725            Ok(())
726        }
727    }
728
729    pub fn single_step_event(&mut self, guid: Guid) -> Result<(), VmError> {
730        if let Some(mut event) = self.running_events.remove(&guid) {
731            self.step_event(&mut event)?;
732            self.running_events.insert(guid, event);
733            Ok(())
734        } else {
735            Err(VmError::EventDoesNotExists(ast::Reference::Guid(guid)))
736        }
737    }
738
739    fn step_event(&mut self, event: &mut VmEvent) -> Result<VmStepStatus, VmError> {
740        // TODO: try avoid cloning.
741        if let Some(node) = event.get_current_node(self).cloned() {
742            match &node.node_type {
743                NodeType::Halt => {
744                    event.go_to_next_node();
745                    return Ok(VmStepStatus::Halt);
746                }
747                NodeType::Loop(loop_) => {
748                    event.push_jump_on_stack(VmJump::Loop(node.id.clone()));
749                    event.go_to_node(loop_, self)?;
750                }
751                NodeType::IfElse(if_else) => {
752                    let value = event.get_node_output(&node.input_links[0])?.clone();
753                    let value2 = value.clone();
754                    if let Ok(v) = value.try_read() {
755                        if let Value::Bool(v) = &*v {
756                            event.push_jump_on_stack(VmJump::IfElse(node.id.clone()));
757                            if *v {
758                                event.go_to_node(&if_else.next_node_true, self)?;
759                            } else {
760                                event.go_to_node(&if_else.next_node_false, self)?;
761                            }
762                        } else {
763                            return Err(VmError::ValueIsNotABool(value2));
764                        }
765                    } else {
766                        return Err(VmError::TryingToReadBorrowedReference(value2));
767                    }
768                    drop(value);
769                }
770                NodeType::Break => match event.pop_jump_from_stack()? {
771                    VmJump::Loop(id) => {
772                        let node = event.get_node(&id, self)?;
773                        if let NodeType::Loop(_) = &node.node_type {
774                            event.go_to_node(&node.next_node, self)?;
775                        } else {
776                            return Err(VmError::NodeIsNotALoop(id));
777                        }
778                    }
779                    VmJump::IfElse(_) => {
780                        return Err(VmError::TryingToBreakIfElse);
781                    }
782                    _ => {}
783                },
784                NodeType::Continue => match event.pop_jump_from_stack()? {
785                    VmJump::Loop(id) => {
786                        let node = event.get_node(&id, self)?;
787                        if let NodeType::Loop(loop_) = &node.node_type {
788                            event.go_to_node(loop_, self)?;
789                        } else {
790                            return Err(VmError::NodeIsNotALoop(id));
791                        }
792                    }
793                    VmJump::IfElse(_) => {
794                        return Err(VmError::TryingToContinueIfElse);
795                    }
796                    _ => {}
797                },
798                NodeType::GetInstance => {
799                    let value = event.instance_value()?;
800                    event.set_node_output(node.id.clone(), value);
801                }
802                NodeType::GetGlobalVariable(name) => {
803                    let value = self.global_variable_value(name)?;
804                    event.set_node_output(node.id.clone(), value);
805                }
806                NodeType::GetLocalVariable(name) => {
807                    let value = event.local_variable_value(name)?;
808                    event.set_node_output(node.id.clone(), value);
809                }
810                NodeType::GetInput(index) => {
811                    let value = event.input_value(*index)?;
812                    event.set_node_output(node.id.clone(), value);
813                }
814                NodeType::SetOutput(index) => {
815                    let value = event.get_node_output(&node.input_links[0])?.clone();
816                    event.set_output_value(*index, value)?;
817                }
818                NodeType::GetValue(value) => {
819                    let value: Value = value.data.clone().into();
820                    event.set_node_output(node.id.clone(), value.into());
821                }
822                NodeType::GetListItem(index) => {
823                    let value = event.get_node_output(&node.input_links[0])?.clone();
824                    let value2 = value.clone();
825                    if let Ok(v) = value.try_read() {
826                        if let Value::List(list) = &*v {
827                            if let Some(value) = list.get(*index) {
828                                event.set_node_output(node.id.clone(), value.clone());
829                            } else {
830                                return Err(VmError::IndexOutOfBounds(list.len(), *index, value2));
831                            }
832                        } else {
833                            return Err(VmError::ValueIsNotAList(value2));
834                        }
835                    } else {
836                        return Err(VmError::TryingToReadBorrowedReference(value2));
837                    }
838                    drop(value);
839                }
840                NodeType::GetObjectItem(key) => {
841                    let value = event.get_node_output(&node.input_links[0])?.clone();
842                    let value2 = value.clone();
843                    if let Ok(v) = value.try_read() {
844                        if let Value::Object(object) = &*v {
845                            if let Some(value) = object.get(key) {
846                                event.set_node_output(node.id.clone(), value.clone());
847                            } else {
848                                return Err(VmError::ObjectKeyDoesNotExists(
849                                    key.to_owned(),
850                                    value2,
851                                ));
852                            }
853                        } else {
854                            return Err(VmError::ValueIsNotAnObject(value2));
855                        }
856                    } else {
857                        return Err(VmError::TryingToReadBorrowedReference(value2));
858                    }
859                    drop(value);
860                }
861                NodeType::MutateValue => {
862                    let value_dst = event.get_node_output(&node.input_links[0])?;
863                    let value_dst2 = value_dst.clone();
864                    let value_src = event.get_node_output(&node.input_links[0])?;
865                    let value_src2 = value_src.clone();
866                    if let Ok(mut dst) = value_dst.try_write() {
867                        if let Ok(src) = value_src.try_read() {
868                            *dst = src.clone();
869                        } else {
870                            return Err(VmError::TryingToReadBorrowedReference(value_src2));
871                        }
872                    } else {
873                        return Err(VmError::TryingToWriteBorrowedReference(
874                            value_src2, value_dst2,
875                        ));
876                    }
877                }
878                NodeType::CallOperation(name) => {
879                    if let Some(op) = self.ast.operations.iter().find(|op| &op.name == name) {
880                        if let Some(op_impl) = self.operations.get_mut(&op.name) {
881                            let inputs = node
882                                .input_links
883                                .iter()
884                                .map(|link| match event.get_node_output(link) {
885                                    Ok(v) => Ok(v.clone()),
886                                    Err(e) => Err(e),
887                                })
888                                .collect::<Result<Vec<_>, _>>()?;
889                            if op.input_constrains.len() != inputs.len() {
890                                return Err(VmError::WrongNumberOfInputs(
891                                    op.input_constrains.len(),
892                                    inputs.len(),
893                                ));
894                            }
895                            let outputs = match op_impl.execute(inputs.as_slice()) {
896                                Ok(outputs) => outputs,
897                                Err(error) => {
898                                    return Err(VmError::Message(format!(
899                                        "Error during call to {:?} operation: {:?}",
900                                        op.name, error
901                                    )))
902                                }
903                            };
904                            if op.output_constrains.len() != outputs.len() {
905                                return Err(VmError::WrongNumberOfOutputs(
906                                    op.output_constrains.len(),
907                                    outputs.len(),
908                                ));
909                            }
910                            event.set_node_outputs(node.id.clone(), outputs);
911                        } else {
912                            return Err(VmError::OperationIsNotRegistered(op.name.clone()));
913                        }
914                    } else {
915                        return Err(VmError::OperationDoesNotExists(ast::Reference::Named(
916                            name.clone(),
917                        )));
918                    }
919                }
920                NodeType::CallFunction(name) => {
921                    if let Some(function) = self.ast.functions.iter().find(|f| &f.name == name) {
922                        if let Some((_, execution)) = self
923                            .function_execution_order
924                            .iter()
925                            .find(|(k, _)| function.name == **k)
926                        {
927                            let inputs = node
928                                .input_links
929                                .iter()
930                                .map(|link| match event.get_node_output(link) {
931                                    Ok(v) => Ok(v.clone()),
932                                    Err(e) => Err(e),
933                                })
934                                .collect::<Result<Vec<_>, _>>()?;
935                            if function.input_constrains.len() != inputs.len() {
936                                return Err(VmError::WrongNumberOfInputs(
937                                    function.input_constrains.len(),
938                                    inputs.len(),
939                                ));
940                            }
941                            event.contexts.push(VmContext {
942                                owner: VmContextOwner::Function(function.name.clone()),
943                                caller_node: Some(node.id.clone()),
944                                execution: execution.to_vec(),
945                                current: Some(0),
946                                instance: None,
947                                inputs,
948                                outputs: vec![Value::None.into(); function.output_constrains.len()],
949                                variables: function
950                                    .variables
951                                    .iter()
952                                    .map(|v| (v.name.clone(), Value::None.into()))
953                                    .collect::<HashMap<_, _>>(),
954                                jump_stack: vec![VmJump::None(None)],
955                                node_outputs: Default::default(),
956                            });
957                        } else {
958                            return Err(VmError::CouldNotCallFunction(ast::Reference::Named(
959                                name.clone(),
960                            )));
961                        }
962                    } else {
963                        return Err(VmError::FunctionDoesNotExists(ast::Reference::Named(
964                            name.clone(),
965                        )));
966                    }
967                }
968                NodeType::CallMethod(type_name, method_name) => {
969                    if let Some(type_) = self.ast.types.iter().find(|t| &t.name == type_name) {
970                        let method =
971                            type_
972                                .traits_implementation
973                                .iter()
974                                .find_map(|(trait_name, methods)| {
975                                    if let Some(method) =
976                                        methods.iter().find(|m| &m.name == method_name)
977                                    {
978                                        Some(method)
979                                    } else if let Some(trait_) =
980                                        self.ast.traits.iter().find(|t| &t.name == trait_name)
981                                    {
982                                        trait_.methods.iter().find(|m| &m.name == method_name)
983                                    } else {
984                                        None
985                                    }
986                                });
987                        let method = if let Some(method) = method {
988                            method
989                        } else {
990                            return Err(VmError::MethodDoesNotExists(ast::Reference::Named(
991                                method_name.clone(),
992                            )));
993                        };
994                        if let Some((_, execution)) = self
995                            .method_execution_order
996                            .iter()
997                            .find(|((_, k), _)| method.name == *k)
998                        {
999                            let inputs = node
1000                                .input_links
1001                                .iter()
1002                                .map(|link| match event.get_node_output(link) {
1003                                    Ok(v) => Ok(v.clone()),
1004                                    Err(e) => Err(e),
1005                                })
1006                                .collect::<Result<Vec<_>, _>>()?;
1007                            if method.input_constrains.len() != inputs.len() {
1008                                return Err(VmError::WrongNumberOfInputs(
1009                                    method.input_constrains.len(),
1010                                    inputs.len(),
1011                                ));
1012                            }
1013                            let instance =
1014                                Some(event.get_node_output(&node.input_links[0])?.clone());
1015                            event.contexts.push(VmContext {
1016                                owner: VmContextOwner::Method(
1017                                    type_.name.clone(),
1018                                    method.name.clone(),
1019                                ),
1020                                caller_node: Some(node.id.clone()),
1021                                execution: execution.to_vec(),
1022                                current: Some(0),
1023                                instance,
1024                                inputs,
1025                                outputs: vec![Value::None.into(); method.output_constrains.len()],
1026                                variables: method
1027                                    .variables
1028                                    .iter()
1029                                    .map(|v| (v.name.clone(), Value::None.into()))
1030                                    .collect::<HashMap<_, _>>(),
1031                                jump_stack: vec![VmJump::None(None)],
1032                                node_outputs: Default::default(),
1033                            });
1034                        } else {
1035                            return Err(VmError::CouldNotCallMethod(
1036                                ast::Reference::Named(type_name.clone()),
1037                                ast::Reference::Named(method_name.clone()),
1038                            ));
1039                        }
1040                    } else {
1041                        return Err(VmError::TypeDoesNotExists(ast::Reference::Named(
1042                            type_name.clone(),
1043                        )));
1044                    }
1045                }
1046                NodeType::Entry => {}
1047                _ => {
1048                    return Err(VmError::TryingToPerformInvalidNodeType(
1049                        node.node_type.clone(),
1050                    ))
1051                }
1052            }
1053            if self.end_nodes.contains(&node.id) {
1054                match event.pop_jump_from_stack()? {
1055                    VmJump::Loop(id) => {
1056                        let node = event.get_node(&id, self)?;
1057                        if let NodeType::Loop(_) = &node.node_type {
1058                            event.go_to_node(&id, self)?;
1059                        } else {
1060                            return Err(VmError::NodeIsNotALoop(id));
1061                        }
1062                    }
1063                    VmJump::IfElse(id) => {
1064                        let node = event.get_node(&id, self)?;
1065                        if let NodeType::IfElse(_) = &node.node_type {
1066                            event.go_to_node(&node.next_node, self)?;
1067                        } else {
1068                            return Err(VmError::NodeIsNotAnIfElse(id));
1069                        }
1070                    }
1071                    _ => {}
1072                }
1073                if event.is_jump_stack_empty() {
1074                    event.go_to_next_node();
1075                    return Ok(VmStepStatus::Stop);
1076                }
1077            }
1078            event.go_to_next_node();
1079            Ok(VmStepStatus::Continue)
1080        } else {
1081            Ok(VmStepStatus::Stop)
1082        }
1083    }
1084
1085    fn process_event(&mut self, event: &mut VmEvent) -> Result<bool, VmError> {
1086        loop {
1087            match self.step_event(event)? {
1088                VmStepStatus::Continue => continue,
1089                VmStepStatus::Halt => return Ok(true),
1090                VmStepStatus::Stop => break,
1091            }
1092        }
1093        Ok(false)
1094    }
1095}
1096
1097#[derive(Debug, Copy, Clone, PartialEq, Eq)]
1098enum VmStepStatus {
1099    Continue,
1100    Halt,
1101    Stop,
1102}
1103
1104pub trait VmOperation: Send + Sync {
1105    fn execute(&mut self, inputs: &[Reference]) -> Result<Vec<Reference>, VmOperationError>;
1106}
1107
1108#[derive(Debug, Clone)]
1109enum VmContextOwner {
1110    Event(String),
1111    // (type name, method name)
1112    Method(String, String),
1113    Function(String),
1114}
1115
1116#[derive(Debug, Clone)]
1117enum VmJump {
1118    /// calling node reference?
1119    None(Option<ast::Reference>),
1120    /// loop node reference
1121    Loop(ast::Reference),
1122    /// if-else node reference
1123    IfElse(ast::Reference),
1124}
1125
1126#[derive(Debug, Clone)]
1127struct VmContext {
1128    pub owner: VmContextOwner,
1129    pub caller_node: Option<ast::Reference>,
1130    pub execution: Vec<ast::Reference>,
1131    pub current: Option<usize>,
1132    pub instance: Option<Reference>,
1133    pub inputs: Vec<Reference>,
1134    pub outputs: Vec<Reference>,
1135    pub variables: HashMap<String, Reference>,
1136    pub jump_stack: Vec<VmJump>,
1137    pub node_outputs: HashMap<ast::Reference, Vec<Reference>>,
1138}
1139
1140#[derive(Debug, Clone)]
1141struct VmEvent {
1142    pub contexts: Vec<VmContext>,
1143    pub outputs: Vec<Reference>,
1144}
1145
1146impl VmEvent {
1147    pub fn new(
1148        owner_event: String,
1149        execution: Vec<ast::Reference>,
1150        variables: Vec<String>,
1151        inputs: Vec<Reference>,
1152        outputs: usize,
1153    ) -> Self {
1154        Self {
1155            contexts: vec![VmContext {
1156                owner: VmContextOwner::Event(owner_event),
1157                caller_node: None,
1158                execution,
1159                current: Some(0),
1160                instance: None,
1161                inputs,
1162                outputs: vec![Value::None.into(); outputs],
1163                variables: variables
1164                    .into_iter()
1165                    .map(|g| (g, Value::None.into()))
1166                    .collect::<HashMap<_, _>>(),
1167                jump_stack: vec![VmJump::None(None)],
1168                node_outputs: Default::default(),
1169            }],
1170            outputs: vec![],
1171        }
1172    }
1173
1174    fn get_node_outputs(&self, id: &ast::Reference) -> Result<&[Reference], VmError> {
1175        if let Some(context) = self.contexts.last() {
1176            if let Some(outputs) = context.node_outputs.get(id) {
1177                return Ok(outputs);
1178            }
1179        }
1180        Err(VmError::ThereAreNoCachedNodeOutputs(id.clone()))
1181    }
1182
1183    fn get_node_output(&self, link: &Link) -> Result<&Reference, VmError> {
1184        if let Link::NodeIndexed(id, index) = link {
1185            if let Some(output) = self.get_node_outputs(id)?.get(*index) {
1186                return Ok(output);
1187            }
1188        }
1189        Err(VmError::ThereIsNoCachedNodeIndexedOutput(link.clone()))
1190    }
1191
1192    fn set_node_outputs(&mut self, id: ast::Reference, values: Vec<Reference>) {
1193        if let Some(context) = self.contexts.last_mut() {
1194            context.node_outputs.insert(id, values);
1195        }
1196    }
1197
1198    fn set_node_output(&mut self, id: ast::Reference, value: Reference) {
1199        self.set_node_outputs(id, vec![value]);
1200    }
1201
1202    fn get_current_node<'a>(&self, vm: &'a Vm) -> Option<&'a Node> {
1203        if let Some(context) = self.contexts.last() {
1204            if let Some(current) = context.current {
1205                if let Some(node_ref) = context.execution.get(current) {
1206                    if let Ok(node) = self.get_node(node_ref, vm) {
1207                        return Some(node);
1208                    }
1209                }
1210            }
1211        }
1212        None
1213    }
1214
1215    fn get_node<'a>(&self, reference: &ast::Reference, vm: &'a Vm) -> Result<&'a Node, VmError> {
1216        if let Some(context) = self.contexts.last() {
1217            match &context.owner {
1218                VmContextOwner::Event(event_name) => {
1219                    if let Some(event) = vm.ast.events.iter().find(|e| &e.name == event_name) {
1220                        if let Some(node) = event.nodes.iter().find(|n| &n.id == reference) {
1221                            return Ok(node);
1222                        }
1223                    } else {
1224                        return Err(VmError::EventDoesNotExists(ast::Reference::Named(
1225                            event_name.clone(),
1226                        )));
1227                    }
1228                }
1229                VmContextOwner::Method(type_name, method_name) => {
1230                    if let Some(methods) = vm.type_methods.get(type_name) {
1231                        if let Some((trait_name, is_impl)) = methods.get(method_name) {
1232                            let type_ = if let Some(type_) =
1233                                vm.ast.types.iter().find(|t| &t.name == type_name)
1234                            {
1235                                type_
1236                            } else {
1237                                return Err(VmError::TypeDoesNotExists(ast::Reference::Named(
1238                                    type_name.clone(),
1239                                )));
1240                            };
1241                            if *is_impl {
1242                                if let Some(method) =
1243                                    type_.traits_implementation.iter().find_map(|(_, methods)| {
1244                                        methods.iter().find(|m| &m.name == method_name)
1245                                    })
1246                                {
1247                                    if let Some(node) =
1248                                        method.nodes.iter().find(|n| &n.id == reference)
1249                                    {
1250                                        return Ok(node);
1251                                    }
1252                                } else {
1253                                    return Err(VmError::MethodDoesNotExists(
1254                                        ast::Reference::Named(method_name.clone()),
1255                                    ));
1256                                }
1257                            } else if let Some(trait_) =
1258                                vm.ast.traits.iter().find(|t| &t.name == trait_name)
1259                            {
1260                                if let Some(method) =
1261                                    trait_.methods.iter().find(|m| &m.name == method_name)
1262                                {
1263                                    if let Some(node) =
1264                                        method.nodes.iter().find(|n| &n.id == reference)
1265                                    {
1266                                        return Ok(node);
1267                                    }
1268                                } else {
1269                                    return Err(VmError::MethodDoesNotExists(
1270                                        ast::Reference::Named(method_name.clone()),
1271                                    ));
1272                                }
1273                            } else {
1274                                return Err(VmError::TraitDoesNotExists(ast::Reference::Named(
1275                                    trait_name.clone(),
1276                                )));
1277                            }
1278                        } else {
1279                            return Err(VmError::TypeDoesNotImplementMethod(
1280                                ast::Reference::Named(type_name.clone()),
1281                                ast::Reference::Named(method_name.clone()),
1282                            ));
1283                        }
1284                    } else {
1285                        return Err(VmError::NodeDoesNotExists(ast::Reference::Named(
1286                            type_name.clone(),
1287                        )));
1288                    }
1289                }
1290                VmContextOwner::Function(function_name) => {
1291                    if let Some(function) =
1292                        vm.ast.functions.iter().find(|f| &f.name == function_name)
1293                    {
1294                        if let Some(node) = function.nodes.iter().find(|n| &n.id == reference) {
1295                            return Ok(node);
1296                        }
1297                    } else {
1298                        return Err(VmError::FunctionDoesNotExists(ast::Reference::Named(
1299                            function_name.clone(),
1300                        )));
1301                    }
1302                }
1303            }
1304        }
1305        Err(VmError::NodeDoesNotExists(reference.clone()))
1306    }
1307
1308    fn go_to_node(&mut self, reference: &ast::Reference, vm: &Vm) -> Result<(), VmError> {
1309        let id = self.get_node(reference, vm)?.id.clone();
1310        if let Some(context) = self.contexts.last() {
1311            if let Some(index) = context.execution.iter().position(|n| n == &id) {
1312                self.contexts.last_mut().unwrap().current = Some(index);
1313                return Ok(());
1314            }
1315        }
1316        Err(VmError::NodeNotFoundInExecutionPipeline(reference.clone()))
1317    }
1318
1319    fn go_to_next_node(&mut self) {
1320        if let Some(context) = self.contexts.last() {
1321            if let Some(mut current) = context.current {
1322                current += 1;
1323                if current < context.execution.len() {
1324                    self.contexts.last_mut().unwrap().current = Some(current);
1325                } else {
1326                    let context = self.contexts.pop();
1327                    self.go_to_next_node();
1328                    if let Some(context) = context {
1329                        if let Some(caller) = context.caller_node {
1330                            self.set_node_outputs(caller, context.outputs);
1331                        } else {
1332                            self.outputs = context.outputs;
1333                        }
1334                    }
1335                }
1336            }
1337        }
1338    }
1339
1340    fn push_jump_on_stack(&mut self, jump: VmJump) {
1341        if let Some(context) = self.contexts.last_mut() {
1342            context.jump_stack.push(jump);
1343        }
1344    }
1345
1346    fn pop_jump_from_stack(&mut self) -> Result<VmJump, VmError> {
1347        if let Some(context) = self.contexts.last_mut() {
1348            if let Some(jump) = context.jump_stack.pop() {
1349                return Ok(jump);
1350            }
1351        }
1352        Err(VmError::StackUnderflow)
1353    }
1354
1355    fn is_jump_stack_empty(&self) -> bool {
1356        if let Some(context) = self.contexts.last() {
1357            context.jump_stack.is_empty()
1358        } else {
1359            true
1360        }
1361    }
1362
1363    fn instance_value(&self) -> Result<Reference, VmError> {
1364        if let Some(context) = self.contexts.last() {
1365            if let Some(instance) = &context.instance {
1366                return Ok(instance.clone());
1367            }
1368        }
1369        Err(VmError::InstanceDoesNotExists)
1370    }
1371
1372    fn local_variable_value(&self, name: &str) -> Result<Reference, VmError> {
1373        if let Some(context) = self.contexts.last() {
1374            if let Some(value) = context.variables.get(name) {
1375                return Ok(value.clone());
1376            }
1377        }
1378        Err(VmError::LocalVariableDoesNotExists(ast::Reference::Named(
1379            name.to_owned(),
1380        )))
1381    }
1382
1383    fn input_value(&self, index: usize) -> Result<Reference, VmError> {
1384        if let Some(context) = self.contexts.last() {
1385            if let Some(input) = context.inputs.get(index) {
1386                return Ok(input.clone());
1387            }
1388        }
1389        Err(VmError::InputDoesNotExists(index))
1390    }
1391
1392    fn set_output_value(&mut self, index: usize, value: Reference) -> Result<Reference, VmError> {
1393        if let Some(context) = self.contexts.last_mut() {
1394            if let Some(output) = context.outputs.get_mut(index) {
1395                return Ok(std::mem::replace(output, value));
1396            }
1397        }
1398        Err(VmError::OutputDoesNotExists(index))
1399    }
1400}