tosca_solver/
topology.rs

1// Copyright (c) 2024 Adam Souzis
2// SPDX-License-Identifier: MIT
3#![allow(clippy::let_unit_value)] // ignore for ascent!
4#![allow(clippy::collapsible_if)] // ignore for ascent!
5#![allow(clippy::clone_on_copy)] // ignore for ascent!
6#![allow(clippy::unused_enumerate_index)] // ignore for ascent!
7#![allow(clippy::type_complexity)] // ignore for ascent!
8
9use ascent::{ascent, lattice::set::Set};
10use std::convert::{From, Into};
11use std::{cmp::Ordering, collections::BTreeMap, fmt::Debug, hash::Hash};
12
13#[cfg(feature = "python")]
14use pyo3::prelude::*;
15
16pub type Symbol = String;
17
18type EntityName = Symbol;
19type NodeName = EntityName;
20type AnonEntityId = EntityName;
21type CapabilityName = Symbol;
22type PropName = Symbol;
23type ReqName = Symbol;
24pub type TypeName = Symbol;
25type QueryId = usize;
26
27#[inline]
28pub(crate) fn sym(s: &str) -> Symbol {
29    // XXX make Symbol a real symbol, e.g. maybe use https://github.com/CAD97/strena/blob/main/src/lib.rs#L329C12-L329C25
30    s.to_string()
31}
32
33/// Represents the match criteria for a requirement.
34///
35/// Corresponds to "node", "capability", and "node_filter"
36/// fields on a TOSCA requirement and "valid_target_types" on relationship types.
37#[cfg_attr(feature = "python", pyclass)]
38#[derive(Clone, PartialOrd, Ord, PartialEq, Eq, Hash, Debug)]
39
40pub enum CriteriaTerm {
41    NodeName {
42        n: Symbol,
43    },
44    NodeType {
45        n: Symbol,
46    },
47    CapabilityName {
48        n: Symbol,
49    },
50    CapabilityTypeGroup {
51        names: Vec<Symbol>,
52    },
53    PropFilter {
54        n: Symbol,
55        capability: Option<Symbol>,
56        constraints: Vec<Constraint>,
57    },
58    NodeMatch {
59        query: Vec<(QueryType, Symbol)>,
60    },
61}
62
63impl CriteriaTerm {
64    #[allow(unused)]
65    fn variant_id(&self) -> usize {
66        match self {
67            CriteriaTerm::NodeName { .. } => 1,
68            CriteriaTerm::NodeType { .. } => 2,
69            CriteriaTerm::CapabilityName { .. } => 3,
70            CriteriaTerm::CapabilityTypeGroup { .. } => 4,
71            CriteriaTerm::PropFilter { .. } => 5,
72            CriteriaTerm::NodeMatch { .. } => 6,
73        }
74    }
75
76    fn match_property(&self, t: &ToscaValue) -> bool {
77        match self {
78            CriteriaTerm::PropFilter { constraints, .. } => {
79                !constraints.is_empty()
80                    && constraints.iter().all(|i| i.matches(t).is_some_and(|s| s))
81            }
82            _ => false, // always false if we're not a CriteriaTerm::PropFilter
83                        // CriteriaTerm::NodeName { n } => match (t.v) { TValue::string { v,} => v == *n, _ => false },
84                        // CriteriaTerm::NodeType { n } => match (t.v) { TValue::string { v,} => v == *n, _ => false },
85                        // CriteriaTerm::CapabilityName { n } => match (t.v) { TValue::string { v,} => v == *n, _ => false },
86        }
87    }
88}
89
90#[cfg_attr(feature = "python", pyclass(eq, eq_int))]
91#[derive(Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Hash, Debug)]
92pub enum QueryType {
93    TransitiveRelation,
94    TransitiveRelationType,
95    RequiredBy,
96    RequiredByType,
97    Sources,
98    Targets,
99    PropSource,
100}
101
102/// Constraints used in node filters
103#[allow(non_camel_case_types)]
104#[cfg_attr(feature = "python", pyclass)]
105#[derive(Clone, PartialEq, Eq, Hash, Debug)]
106pub enum Constraint {
107    equal { v: ToscaValue },
108    greater_than { v: ToscaValue },
109    greater_or_equal { v: ToscaValue },
110    less_than { v: ToscaValue },
111    less_or_equal { v: ToscaValue },
112    in_range { v: ToscaValue },
113    valid_values { v: ToscaValue },
114    length { v: ToscaValue },
115    min_length { v: ToscaValue },
116    max_length { v: ToscaValue },
117    // pattern, // XXX
118    // schema,  // XXX
119}
120
121impl Constraint {
122    fn get_value(&self) -> &ToscaValue {
123        match self {
124            Constraint::equal { v } => v,
125            Constraint::greater_than { v } => v,
126            Constraint::greater_or_equal { v } => v,
127            Constraint::less_than { v } => v,
128            Constraint::less_or_equal { v } => v,
129            Constraint::in_range { v } => v,
130            Constraint::valid_values { v } => v,
131            Constraint::length { v } => v,
132            Constraint::min_length { v } => v,
133            Constraint::max_length { v } => v,
134        }
135    }
136
137    fn matches(&self, t: &ToscaValue) -> Option<bool> {
138        // XXX validate self.v is compatibility with v
139        // let v = self.get_value();
140        // let t = tc.v;
141        match self {
142            Constraint::equal { v } => Some(t == v),
143            Constraint::greater_than { v } => Some(t > v),
144            Constraint::greater_or_equal { v } => Some(t >= v),
145            Constraint::less_than { v } => Some(t < v),
146            Constraint::less_or_equal { v } => Some(t <= v),
147            Constraint::in_range {
148                v:
149                    ToscaValue {
150                        v: SimpleValue::range { v: sv },
151                        ..
152                    },
153            } => Some(
154                t.v >= SimpleValue::integer { v: sv.0 } && t.v <= SimpleValue::integer { v: sv.1 },
155            ),
156            Constraint::valid_values {
157                v:
158                    ToscaValue {
159                        v: SimpleValue::list { v: sv },
160                        ..
161                    },
162            } => {
163                let found = sv.iter().position(|x| *x == *t);
164                Some(found.is_some())
165            }
166            Constraint::length {
167                v:
168                    ToscaValue {
169                        v: SimpleValue::integer { v: vv },
170                        ..
171                    },
172            } => {
173                let len = t.v.len()?;
174                Some(*vv == len as i128)
175            }
176            Constraint::min_length {
177                v:
178                    ToscaValue {
179                        v: SimpleValue::integer { v: vv },
180                        ..
181                    },
182            } => {
183                let len = t.v.len()?;
184                Some(*vv >= len as i128)
185            }
186            Constraint::max_length {
187                v:
188                    ToscaValue {
189                        v: SimpleValue::integer { v: vv },
190                        ..
191                    },
192            } => {
193                let len = t.v.len()?;
194                Some(*vv <= len as i128)
195            }
196            _ => None, // type mismatch
197        }
198    }
199}
200
201impl PartialOrd for Constraint {
202    #[inline]
203    fn partial_cmp(&self, other: &Constraint) -> Option<Ordering> {
204        Some(self.cmp(other))
205    }
206}
207
208// we need Ord for the lattice
209impl Ord for Constraint {
210    fn cmp(&self, other: &Constraint) -> Ordering {
211        let v = self.get_value();
212        let ov = other.get_value();
213        match v.partial_cmp(ov) {
214            Some(cmp) => cmp,
215            // different types of SimpleValues don't compare, so do it here
216            // note: this implies NaN == NaN if SimpleValue is a float, which is fine for our usage.
217            None => Ord::cmp(&v.v.variant_id(), &ov.v.variant_id()),
218        }
219    }
220}
221
222/// Set of CriteriaTerms
223pub type Criteria = Set<CriteriaTerm>;
224pub type Restrictions = Vec<Field>;
225
226#[inline]
227fn match_criteria(full: &Criteria, current: &Criteria) -> bool {
228    full == current
229}
230
231/// Simple TOSCA value
232#[allow(non_camel_case_types)]
233#[cfg_attr(feature = "python", pyclass)]
234#[derive(Clone, PartialEq, Debug)]
235pub enum SimpleValue {
236    // tosca simple values
237    integer { v: i128 },
238    string { v: String },
239    boolean { v: bool },
240    float { v: f64 },
241    list { v: Vec<ToscaValue> },
242    range { v: (i128, i128) },
243    map { v: BTreeMap<String, ToscaValue> },
244    // XXX "timestamp",
245}
246
247impl SimpleValue {
248    fn variant_id(&self) -> usize {
249        match self {
250            SimpleValue::integer { .. } => 1,
251            SimpleValue::string { .. } => 2,
252            SimpleValue::boolean { .. } => 3,
253            SimpleValue::float { .. } => 4,
254            SimpleValue::list { .. } => 5,
255            SimpleValue::range { .. } => 6,
256            SimpleValue::map { .. } => 7,
257        }
258    }
259
260    fn len(&self) -> Option<usize> {
261        match self {
262            SimpleValue::string { v } => Some(v.len()),
263            SimpleValue::list { v } => Some(v.len()),
264            SimpleValue::map { v } => Some(v.len()),
265            _ => None,
266        }
267    }
268}
269
270impl PartialOrd for SimpleValue {
271    fn partial_cmp(&self, other: &SimpleValue) -> Option<Ordering> {
272        match (self, other) {
273            (SimpleValue::integer { v }, SimpleValue::integer { v: v2 }) => v.partial_cmp(v2),
274            (SimpleValue::string { v }, SimpleValue::string { v: v2 }) => v.partial_cmp(v2),
275            (SimpleValue::boolean { v }, SimpleValue::boolean { v: v2 }) => v.partial_cmp(v2),
276            (SimpleValue::float { v }, SimpleValue::float { v: v2 }) => v.partial_cmp(v2),
277            (SimpleValue::list { v }, SimpleValue::list { v: v2 }) => v.partial_cmp(v2),
278            (SimpleValue::range { v }, SimpleValue::range { v: v2 }) => v.partial_cmp(v2),
279            (SimpleValue::map { v }, SimpleValue::map { v: v2 }) => v.partial_cmp(v2),
280            _ => None, // different types of SimpleValues are not comparable
281        }
282    }
283}
284
285impl Eq for SimpleValue {
286    fn assert_receiver_is_total_eq(&self) {
287        // skip this check so we can pretend f64 are Eq
288        // XXX fix this (use float_eq::FloatEq? or ordered-float
289    }
290}
291
292impl Hash for SimpleValue {
293    #[inline]
294    fn hash<__H: ::core::hash::Hasher>(&self, state: &mut __H) {
295        let __self_tag = std::mem::discriminant(self);
296        Hash::hash(&__self_tag, state);
297        match self {
298            SimpleValue::integer { v: __self_0 } => Hash::hash(__self_0, state),
299            SimpleValue::string { v: __self_0 } => Hash::hash(__self_0, state),
300            SimpleValue::boolean { v: __self_0 } => Hash::hash(__self_0, state),
301            SimpleValue::float { v: __self_0 } => Hash::hash(&__self_0.to_bits(), state),
302            SimpleValue::list { v: __self_0 } => Hash::hash(__self_0, state),
303            SimpleValue::range { v: __self_0 } => Hash::hash(__self_0, state),
304            SimpleValue::map { v: __self_0 } => Hash::hash(__self_0, state),
305        }
306    }
307}
308
309macro_rules! sv_from {
310    ($type:ty, $variant:ident) => {
311        impl From<$type> for SimpleValue {
312            fn from(item: $type) -> Self {
313                SimpleValue::$variant { v: item }
314            }
315        }
316    };
317}
318
319sv_from!(i128, integer);
320sv_from!(f64, float);
321sv_from!(bool, boolean);
322sv_from!(String, string);
323sv_from!((i128, i128), range);
324sv_from!(Vec<ToscaValue>, list);
325sv_from!(BTreeMap<String, ToscaValue>, map);
326
327/// A TOSCA value. If a complex value or typed scalar, type_name will be set.
328#[cfg_attr(feature = "python", pyclass)]
329#[derive(Clone, PartialOrd, PartialEq, Eq, Hash, Debug)]
330pub struct ToscaValue {
331    #[cfg(feature = "python")]
332    #[pyo3(get, set)]
333    pub type_name: Option<Symbol>,
334
335    #[cfg(not(feature = "python"))]
336    pub type_name: Option<Symbol>,
337
338    #[cfg(feature = "python")]
339    #[pyo3(get)]
340    pub v: SimpleValue,
341
342    #[cfg(not(feature = "python"))]
343    pub v: SimpleValue,
344}
345
346#[cfg(feature = "python")]
347#[pymethods]
348impl ToscaValue {
349    #[new]
350    #[pyo3(signature = (value, name=None))]
351    fn new(value: SimpleValue, name: Option<String>) -> Self {
352        ToscaValue {
353            type_name: name.map(|n| sym(&n)),
354            v: value,
355        }
356    }
357
358    #[setter]
359    fn set_v(&mut self, value: SimpleValue) -> PyResult<()> {
360        self.v = value;
361        Ok(())
362    }
363}
364
365macro_rules! tv_from {
366    ($type:ty) => {
367        impl From<$type> for ToscaValue {
368            fn from(item: $type) -> Self {
369                ToscaValue {
370                    type_name: None,
371                    v: SimpleValue::from(item),
372                }
373            }
374        }
375    };
376}
377
378tv_from!(i128);
379tv_from!(f64);
380tv_from!(bool);
381tv_from!(String);
382tv_from!((i128, i128));
383tv_from!(Vec<ToscaValue>);
384tv_from!(BTreeMap<String, ToscaValue>);
385
386/// Value of a [Node](crate::Node) field.
387#[cfg_attr(feature = "python", pyclass)]
388#[derive(Clone, PartialOrd, PartialEq, Eq, Hash, Debug)]
389pub enum FieldValue {
390    Property {
391        value: ToscaValue,
392        // Expr(Vec<QuerySegment>),
393    },
394    Capability {
395        tosca_type: String, // the capability type
396        properties: Vec<Field>,
397    },
398    Requirement {
399        terms: Vec<CriteriaTerm>,
400        tosca_type: Option<String>, // the relationship type
401        restrictions: Vec<Field>, // node_filter requirement or property constraints to apply to the match
402    },
403}
404
405/// [Node](crate::Node) field.
406#[cfg_attr(feature = "python", pyclass)]
407#[derive(Clone, PartialOrd, PartialEq, Eq, Hash, Debug)]
408pub struct Field {
409    #[cfg(feature = "python")]
410    #[pyo3(get, set)]
411    pub name: String,
412    #[cfg(not(feature = "python"))]
413    pub name: String,
414
415    #[cfg(feature = "python")]
416    #[pyo3(get)]
417    pub value: FieldValue,
418    #[cfg(not(feature = "python"))]
419    pub value: FieldValue,
420}
421
422#[cfg(feature = "python")]
423#[pymethods]
424impl Field {
425    #[new]
426    fn new(name: String, value: FieldValue) -> Self {
427        Field { name, value }
428    }
429
430    #[setter]
431    fn set_value(&mut self, value: FieldValue) -> PyResult<()> {
432        self.value = value;
433        Ok(())
434    }
435
436    fn __repr__(&self) -> String {
437        format!("{self:?}")
438    }
439}
440
441#[derive(Clone, PartialEq, Eq, Hash)]
442pub enum EntityRef {
443    Node(NodeName),
444    Capability(AnonEntityId),
445    Datatype(AnonEntityId),
446}
447
448fn choose_cap(a: Option<CapabilityName>, b: Option<CapabilityName>) -> Option<CapabilityName> {
449    match (a, b) {
450        (Some(x), Some(y)) => {
451            if x == "feature" {
452                Some(y)
453            } else {
454                Some(x)
455            }
456        }
457        (Some(x), None) => Some(x),
458        (None, Some(y)) => Some(y),
459        _ => None,
460    }
461}
462
463ascent! {
464    #![generate_run_timeout]
465    pub(crate) struct Topology;
466
467    relation entity(EntityRef, TypeName);
468    relation node(NodeName, TypeName);
469    relation property_value (NodeName, Option<CapabilityName>, PropName, ToscaValue);
470    // if a computed property is referenced in a node_filter match, translate a computed property's eval expression into set of these:
471    relation property_expr (EntityRef, PropName, ReqName, PropName);
472    // relation property_source (NodeName, Option<CapabilityName>, PropName, EntityRef); // transitive source from (property_expr, property_value) and (property_expr, property_source)
473
474    // node_template definition
475    relation capability (NodeName, CapabilityName, EntityRef);
476    relation requirement(NodeName, ReqName, Criteria, Restrictions);
477    relation relationship(NodeName, ReqName, TypeName);
478    relation req_term_node_name(NodeName, ReqName, CriteriaTerm, NodeName);
479    relation req_term_node_type(NodeName, ReqName, CriteriaTerm, TypeName);
480    relation req_term_cap_type(NodeName, ReqName, CriteriaTerm, TypeName);
481    relation req_term_cap_name(NodeName, ReqName, CriteriaTerm, CapabilityName);
482    relation req_term_prop_filter(NodeName, ReqName, CriteriaTerm, Option<CapabilityName>, PropName);
483    relation req_term_query(NodeName, ReqName, CriteriaTerm, QueryId);
484    relation term_match(NodeName, ReqName, Criteria, CriteriaTerm, NodeName, Option<CapabilityName>);
485    lattice filtered(NodeName, ReqName, NodeName, Option<CapabilityName>, Criteria, Criteria);
486    relation requirement_match(NodeName, ReqName, NodeName, CapabilityName);
487
488    term_match(source, req, criteria, ct, target, None) <--
489        node(target, typename), requirement(source, req, criteria, restrictions),
490        req_term_node_name(source, req, ct, target) if source != target;
491
492    term_match(source, req, criteria, ct, target, None) <--
493        node(target, typename), requirement(source, req, criteria, restrictions),
494        req_term_node_type(source, req, ct, typename) if source != target;
495
496    term_match(source, req, criteria, ct, target, Some(cap_name.clone())) <--
497        capability(target, cap_name, cap_id), entity(cap_id, typename),
498        requirement(source, req, criteria, restrictions),
499        req_term_cap_type(source, req, ct, typename) if source != target;
500
501    term_match(source, req, criteria, ct, target, Some(cap_name.clone())) <--
502        capability(target, cap_name, _), requirement(source, req, criteria, restrictions),
503        term_match(source, req, criteria, _, target, _),  // only match req_term_capname after we found candidate target nodes
504        req_term_cap_name(source, req, ct, cap_name);
505
506    term_match(source, req, criteria, ct, target, None) <--
507        property_value (target, capname, propname, value),
508        requirement(source, req, criteria, restrictions),
509        req_term_prop_filter(source, req, ct, capname, propname) if source != target && ct.match_property(value);
510
511    term_match(source, req, criteria, ct, target, None) <--
512        result(source, req, q_id, target, true), requirement(source, req, criteria, restrictions),
513        req_term_query(node, req, ct, q_id);
514
515    filtered(name, req_name, target, cn, criteria, Criteria::singleton(term.clone())) <--
516        term_match(name, req_name, criteria, term, target, cn);
517
518    filtered(name, req_name, target, choose_cap(tcn.clone(), fcn.clone()), criteria,
519            Set({let mut fc = f.0.clone(); fc.insert(term.clone()); fc})) <--
520        term_match(name, req_name, criteria, term, target, tcn),
521        filtered(name, req_name, target, fcn, criteria, ?f);
522
523    // if all the criteria have been found, create a requirement_match
524    requirement_match(name, req_name, target, fcn.clone().unwrap_or("feature".into())) <--
525        filtered(name, req_name, target, fcn, criteria, filter) if match_criteria(filter, criteria);
526
527    // graph navigation
528    relation required_by(NodeName, ReqName, NodeName);
529    relation transitive_match(NodeName, ReqName, NodeName);
530
531    required_by(y, r, x) <-- requirement_match(x, r, y, c);
532    required_by(x, r, z) <-- requirement_match(y, r, x, c), required_by(y, r, z);
533
534    transitive_match(x, r, y) <-- requirement_match(x, r, y, c);
535    transitive_match(x, r, z) <-- requirement_match(x, r, y, c), transitive_match(y, r, z);
536
537    // querying
538    relation query(NodeName, ReqName, QueryId, QueryType, ReqName, bool);
539    relation result(NodeName, ReqName, QueryId, NodeName, bool);
540
541    // rules for generating for each query type:
542    result(n, r, q_id + 1, t ,last) <-- transitive_match(s, a, t),
543                              query(n, r, q_id, QueryType::TransitiveRelation, a, last),
544                              result(n, r, q_id, s, false);
545
546    result(n, r, q_id + 1, s, last) <-- required_by(s, a, t),
547                              query(n, r, q_id, QueryType::RequiredBy, a, last),
548                              result(n, r, q_id, t, false);
549
550    result(n, r2, q_id + 1, s, last) <-- required_by(s, r2, t),
551          query(n, r, q_id, QueryType::RequiredByType, a, last),
552          relationship(n, r, a),
553          result(n, r, q_id, t, false);
554
555    result(n, r2, q_id + 1, t ,last) <-- transitive_match(s, r2, t),
556        query(n, r, q_id, QueryType::TransitiveRelationType, a, last),
557        relationship(n, r, a),
558        result(n, r, q_id, s, false);
559
560    result(node_name, req_name, q_id + 1, source, last) <-- requirement_match(source, a, target, ?cap),
561          query(node_name, req_name, q_id, QueryType::Sources, a, last),
562          result(node_name, req_name, q_id, target, false);
563
564    result(node_name, req_name, q_id + 1, target, last) <-- requirement_match(source, a, target, ?cap),
565          query(node_name, req_name, q_id, QueryType::Targets, a, last),
566          result(node_name, req_name, q_id, source, false);
567
568   // result(t, q_id, final) <-- property_source(s, None, prop_name, t), query(q_id, QueryType::PropertySource"), prop_name, last), result(s, q_id, false);
569   // given an expression like configured_by::property, generate:
570   // [result(source_node, 1, false), query(1, "required_by", "configured_by", false), property_source_query(1, property, true)]
571}
572
573#[cfg(test)]
574mod tests {
575    use super::*;
576
577    #[allow(clippy::field_reassign_with_default)]
578    pub fn make_topology() -> Topology {
579        let mut prog = Topology::default();
580        prog.node = vec![("n1".into(), "Root".into())];
581        prog.requirement_match = vec![
582            (sym("n1"), sym("host"), sym("n2"), sym("feature")),
583            (sym("n2"), sym("host"), sym("n3"), sym("feature")),
584            (sym("n3"), sym("connect"), sym("n4"), sym("feature")),
585        ];
586        prog.run();
587        prog
588    }
589
590    fn tvalue_lessthan(a: SimpleValue, b: SimpleValue) -> bool {
591        a < b
592    }
593
594    #[test]
595    fn test_tvalue() {
596        assert!(!tvalue_lessthan(
597            SimpleValue::integer { v: 1 },
598            SimpleValue::string { v: "ssss".into() }
599        ));
600        assert!(tvalue_lessthan(
601            SimpleValue::integer { v: 1 },
602            SimpleValue::integer { v: 2 }
603        ));
604
605        let range = Constraint::in_range {
606            v: ToscaValue::from((1, 4)),
607        };
608        assert!(range.matches(&ToscaValue::from(1)).unwrap());
609        assert!(!range.matches(&ToscaValue::from(6)).unwrap());
610    }
611
612    #[test]
613    fn test_make_topology() {
614        let prog = make_topology();
615
616        // test transitive closure by relationship
617        assert_eq!(
618            prog.transitive_match,
619            [
620                (sym("n1"), sym("host"), sym("n2")),
621                (sym("n2"), sym("host"), sym("n3")),
622                (sym("n3"), sym("connect"), sym("n4")),
623                (sym("n1"), sym("host"), sym("n3")),
624            ]
625        );
626
627        // test reverse transitive closure by relationship
628        assert_eq!(
629            prog.required_by,
630            [
631                (sym("n2"), sym("host"), sym("n1")),
632                (sym("n3"), sym("host"), sym("n2")),
633                (sym("n4"), sym("connect"), sym("n3")),
634                (sym("n3"), sym("host"), sym("n1")),
635            ]
636        );
637    }
638}
tosca_solver/topology.rs

tosca_solver/
topology.rs
