1use std::cmp::Ordering;
21
22#[derive(Debug, Clone, PartialEq, Eq)]
27pub struct Resource {
28 pub name: String,
29 pub quantity: String,
30}
31
32impl Resource {
33 pub fn new(name: impl Into<String>, quantity: impl Into<String>) -> Self {
34 Self {
35 name: name.into(),
36 quantity: quantity.into(),
37 }
38 }
39}
40
41#[derive(Debug, Clone, PartialEq, Eq)]
44pub struct ResourceRequest {
45 pub name: String,
46 pub min_quantity: String,
47}
48
49impl ResourceRequest {
50 pub fn new(name: impl Into<String>, min_quantity: impl Into<String>) -> Self {
51 Self {
52 name: name.into(),
53 min_quantity: min_quantity.into(),
54 }
55 }
56
57 pub fn satisfied_by(&self, available: &str) -> bool {
60 match (
61 parse_k8s_quantity(available),
62 parse_k8s_quantity(&self.min_quantity),
63 ) {
64 (Some(have), Some(need)) => have >= need,
65 _ => false,
66 }
67 }
68}
69
70#[derive(Debug, Clone, Copy, PartialEq, Eq)]
72pub enum SelectorOp {
73 In,
74 NotIn,
75 Exists,
76 DoesNotExist,
77 Gt,
78 Lt,
79}
80
81#[derive(Debug, Clone, PartialEq, Eq)]
84pub struct LabelSelector {
85 pub key: String,
86 pub op: SelectorOp,
87 pub values: Vec<String>,
88}
89
90impl LabelSelector {
91 pub fn new(key: impl Into<String>, op: SelectorOp, values: Vec<String>) -> Self {
92 Self {
93 key: key.into(),
94 op,
95 values,
96 }
97 }
98
99 pub fn matches(&self, labels: &[(String, String)]) -> bool {
101 let entry = labels.iter().find(|(k, _)| k == &self.key);
102 match self.op {
103 SelectorOp::Exists => entry.is_some(),
104 SelectorOp::DoesNotExist => entry.is_none(),
105 SelectorOp::In => entry.is_some_and(|(_, v)| self.values.iter().any(|w| w == v)),
106 SelectorOp::NotIn => entry.is_none_or(|(_, v)| !self.values.iter().any(|w| w == v)),
107 SelectorOp::Gt => {
110 self.cmp_numeric(entry.map(|(_, v)| v.as_str()), |o| o == Ordering::Greater)
111 }
112 SelectorOp::Lt => {
113 self.cmp_numeric(entry.map(|(_, v)| v.as_str()), |o| o == Ordering::Less)
114 }
115 }
116 }
117
118 fn cmp_numeric(&self, have: Option<&str>, want: impl Fn(Ordering) -> bool) -> bool {
119 let have = match have.and_then(parse_k8s_quantity) {
120 Some(h) => h,
121 None => return false,
122 };
123 let need = match self.values.first().and_then(|v| parse_k8s_quantity(v)) {
125 Some(n) => n,
126 None => return false,
127 };
128 want(have.cmp(&need))
129 }
130}
131
132#[derive(Debug, Clone, PartialEq)]
134pub struct PlacementCandidate {
135 pub node: String,
136 pub record_uri: String,
137 pub load_fraction: f32,
138 pub allocatable: Vec<Resource>,
139 pub last_seen: i64,
140}
141
142#[derive(Debug, Clone)]
145pub struct PlacementCandidateSet {
146 pub candidates: Vec<PlacementCandidate>,
147 pub total_matching: u32,
148}
149
150pub fn parse_k8s_quantity(s: &str) -> Option<i128> {
165 let s = s.trim();
166 if s.is_empty() {
167 return None;
168 }
169 let split = s
172 .find(|c: char| !(c.is_ascii_digit() || c == '.' || c == '-' || c == '+'))
173 .unwrap_or(s.len());
174 let (num, suffix) = s.split_at(split);
175 let v: f64 = num.parse().ok()?;
176 let milli: i128 = match suffix {
179 "" => (v * 1_000.0) as i128,
180 "m" => v as i128, "u" | "µ" => (v / 1_000.0) as i128, "k" => (v * 1_000.0 * 1_000.0) as i128,
183 "M" => (v * 1_000_000.0 * 1_000.0) as i128,
184 "G" => (v * 1_000_000_000.0 * 1_000.0) as i128,
185 "T" => (v * 1_000_000_000_000.0 * 1_000.0) as i128,
186 "Ki" => (v * 1_024.0 * 1_000.0) as i128,
187 "Mi" => (v * 1_048_576.0 * 1_000.0) as i128,
188 "Gi" => (v * 1_073_741_824.0 * 1_000.0) as i128,
189 "Ti" => (v * 1_099_511_627_776.0 * 1_000.0) as i128,
190 _ => return None,
193 };
194 Some(milli)
195}
196
197#[derive(Debug, Clone)]
201pub struct RejectionReason(pub String);
202
203pub type Predicate<C> = Box<dyn Fn(&C) -> Option<RejectionReason>>;
207
208#[derive(Debug, Clone)]
211pub struct Outcome<'c, C> {
212 pub candidate: &'c C,
213 pub rejected: Option<RejectionReason>,
214}
215
216impl<'c, C> Outcome<'c, C> {
217 pub fn passed(&self) -> bool {
218 self.rejected.is_none()
219 }
220}
221
222#[allow(clippy::needless_lifetimes)] pub fn filter<'c, C>(candidates: &'c [C], predicates: &[Predicate<C>]) -> Vec<Outcome<'c, C>> {
227 candidates
228 .iter()
229 .map(|c| {
230 let rejected = predicates.iter().find_map(|p| p(c));
231 Outcome {
232 candidate: c,
233 rejected,
234 }
235 })
236 .collect()
237}
238
239pub fn rank<C>(mut survivors: Vec<&C>, by: impl Fn(&C, &C) -> Ordering) -> Vec<&C> {
242 survivors.sort_by(|a, b| by(a, b));
243 survivors
244}
245
246#[derive(Debug, Clone)]
249pub struct CandidateOutcome<C> {
250 pub candidate: C,
251 pub selected: bool,
252 pub rejection_reason: Option<String>,
253}
254
255#[derive(Debug, Clone)]
258pub struct SelectionReport<C> {
259 pub requested: String,
260 pub candidates: Vec<CandidateOutcome<C>>,
261 pub selected: Option<usize>, pub summary: String,
263}
264
265pub fn select<C>(
271 candidates: &[C],
272 predicates: &[Predicate<C>],
273 rank_by: impl Fn(&C, &C) -> Ordering,
274 max: usize,
275) -> SelectionReport<C>
276where
277 C: Clone,
278{
279 let outcomes = filter(candidates, predicates);
280 let mut survivors: Vec<&C> = outcomes
281 .iter()
282 .filter(|o| o.passed())
283 .map(|o| o.candidate)
284 .collect();
285 survivors = rank(survivors, rank_by);
286 let bound: Vec<&C> = survivors.into_iter().take(max).collect();
287 let chosen: Vec<&C> = bound.clone();
288 let summary = format!(
289 "{} considered, {} survived filters, {} selected (bound {max})",
290 candidates.len(),
291 outcomes.iter().filter(|o| o.passed()).count(),
292 chosen.len(),
293 );
294 let candidate_reports = candidates
295 .iter()
296 .map(|c| {
297 let is_selected = chosen.iter().any(|s| std::ptr::eq(*s, c));
298 let rejection = outcomes
299 .iter()
300 .find(|o| std::ptr::eq(o.candidate, c))
301 .and_then(|o| o.rejected.as_ref().map(|r| r.0.clone()));
302 CandidateOutcome {
303 candidate: c.clone(),
304 selected: is_selected,
305 rejection_reason: rejection,
306 }
307 })
308 .collect();
309 let selected_idx = bound.first().and_then(|b| {
310 candidates
311 .iter()
312 .position(|c| std::ptr::eq(c as *const _, *b as *const _))
313 });
314 SelectionReport {
315 requested: String::new(),
316 candidates: candidate_reports,
317 selected: selected_idx,
318 summary,
319 }
320}
321
322pub trait CapabilitySource {
335 fn capability_labels(&self) -> Vec<(String, String)>;
338 fn capability_resources(&self) -> Vec<Resource>;
342}
343
344#[cfg(test)]
345mod tests {
346 #![allow(clippy::unwrap_used)]
347 use super::*;
348
349 fn sel(key: &str, op: SelectorOp, values: &[&str]) -> LabelSelector {
350 LabelSelector::new(key, op, values.iter().map(|&s| s.to_owned()).collect())
351 }
352
353 #[test]
354 fn selector_in_not_in() {
355 let labels = vec![("env".into(), "prod".into()), ("gpu".into(), "h100".into())];
356 assert!(sel("env", SelectorOp::In, &["prod", "staging"]).matches(&labels));
357 assert!(!sel("env", SelectorOp::In, &["dev"]).matches(&labels));
358 assert!(sel("env", SelectorOp::NotIn, &["dev"]).matches(&labels));
359 assert!(!sel("env", SelectorOp::NotIn, &["prod"]).matches(&labels));
360 }
361
362 #[test]
363 fn selector_exists_does_not_exist() {
364 let labels = vec![("env".into(), "prod".into())];
365 assert!(sel("env", SelectorOp::Exists, &[]).matches(&labels));
366 assert!(!sel("missing", SelectorOp::Exists, &[]).matches(&labels));
367 assert!(sel("missing", SelectorOp::DoesNotExist, &[]).matches(&labels));
368 assert!(!sel("env", SelectorOp::DoesNotExist, &[]).matches(&labels));
369 }
370
371 #[test]
372 fn selector_gt_lt_numeric() {
373 let labels = vec![("gpu.count".into(), "8".into())];
374 assert!(sel("gpu.count", SelectorOp::Gt, &["4"]).matches(&labels));
375 assert!(!sel("gpu.count", SelectorOp::Gt, &["8"]).matches(&labels));
376 assert!(sel("gpu.count", SelectorOp::Lt, &["16"]).matches(&labels));
377 assert!(!sel("gpu.count", SelectorOp::Lt, &["8"]).matches(&labels));
378 assert!(!sel("absent", SelectorOp::Gt, &["1"]).matches(&labels));
380 }
381
382 #[test]
383 fn k8s_quantity_compares_across_suffixes() {
384 assert!(parse_k8s_quantity("8").unwrap() == parse_k8s_quantity("8000m").unwrap());
385 assert!(parse_k8s_quantity("1Gi").unwrap() > parse_k8s_quantity("512Mi").unwrap());
386 assert!(parse_k8s_quantity("2").unwrap() > parse_k8s_quantity("1").unwrap());
387 assert!(parse_k8s_quantity("100m").unwrap() < parse_k8s_quantity("1").unwrap());
388 assert!(parse_k8s_quantity("garbage").is_none());
389 assert!(parse_k8s_quantity("").is_none());
390 }
391
392 #[test]
393 fn resource_request_satisfied() {
394 let req = ResourceRequest::new("memory", "256Gi");
395 assert!(req.satisfied_by("512Gi"));
396 assert!(req.satisfied_by("256Gi"));
397 assert!(!req.satisfied_by("128Gi"));
398 assert!(!req.satisfied_by("garbage")); }
400
401 #[test]
402 fn filter_rank_select_pipeline() {
403 let cands = vec![
405 ("a".to_owned(), 1),
406 ("b".to_owned(), 3),
407 ("c".to_owned(), 2),
408 ("d".to_owned(), 2),
409 ];
410 let preds: Vec<Predicate<(String, i32)>> = vec![Box::new(|c| {
411 if c.1 >= 2 {
412 None
413 } else {
414 Some(RejectionReason("priority < 2".into()))
415 }
416 })];
417 let report = select(
418 &cands,
419 &preds,
420 |a, b| b.1.cmp(&a.1).then(a.0.cmp(&b.0)), 2, );
423 let selected: Vec<&String> = report
425 .candidates
426 .iter()
427 .filter(|o| o.selected)
428 .map(|o| &o.candidate.0)
429 .collect();
430 assert_eq!(selected, vec![&"b".to_owned(), &"c".to_owned()]);
431 let a = report
433 .candidates
434 .iter()
435 .find(|o| o.candidate.0 == "a")
436 .unwrap();
437 assert_eq!(a.rejection_reason.as_deref(), Some("priority < 2"));
438 assert!(report.summary.contains("4 considered") && report.summary.contains("3 survived"));
439 }
440
441 #[test]
442 fn filter_records_first_rejection_only() {
443 let cands = vec![1, 2, 3];
444 let preds: Vec<Predicate<i32>> = vec![
445 Box::new(|c| {
446 if c % 2 == 0 {
447 Some(RejectionReason("even".into()))
448 } else {
449 None
450 }
451 }),
452 Box::new(|c| {
453 if *c == 1 {
454 Some(RejectionReason("is-one".into()))
455 } else {
456 None
457 }
458 }),
459 ];
460 let out = filter(&cands, &preds);
461 assert_eq!(out[0].rejected.as_ref().unwrap().0, "is-one");
463 assert_eq!(out[1].rejected.as_ref().unwrap().0, "even");
465 assert!(out[2].passed());
467 }
468
469 #[test]
470 fn capability_source_trait() {
471 struct Gpu;
472 impl CapabilitySource for Gpu {
473 fn capability_labels(&self) -> Vec<(String, String)> {
474 vec![("gpu.arch".into(), "hopper".into())]
475 }
476 fn capability_resources(&self) -> Vec<Resource> {
477 vec![Resource::new("nvidia.com/gpu", "8")]
478 }
479 }
480 let g = Gpu;
481 assert_eq!(
482 g.capability_labels(),
483 vec![("gpu.arch".into(), "hopper".into())]
484 );
485 assert_eq!(g.capability_resources().len(), 1);
486 }
487}