1use std::borrow::Borrow;
9use std::collections::{hash_map, BTreeMap};
10use std::iter::FromIterator;
11use std::rc::Rc;
12use std::sync::LazyLock;
13
14use bstr::BStr;
15use itertools::Itertools as _;
16use rustc_hash::FxHashMap;
17use serde::de::{Deserializer, Error, Visitor};
18use serde::Deserialize;
19
20use super::string::NixString;
21use super::thunk::ThunkSet;
22use super::TotalDisplay;
23use super::Value;
24use crate::errors::ErrorKind;
25use crate::CatchableErrorKind;
26
27static NAME: LazyLock<NixString> = LazyLock::new(|| "name".into());
28static VALUE: LazyLock<NixString> = LazyLock::new(|| "value".into());
29
30#[cfg(test)]
31mod tests;
32
33#[derive(Clone, Debug, Deserialize, Default)]
34pub(super) enum AttrsRep {
35 #[default]
36 Empty,
37
38 Map(FxHashMap<NixString, Value>),
39
40 KV {
44 name: Value,
45 value: Value,
46 },
47}
48
49impl AttrsRep {
50 fn select(&self, key: &BStr) -> Option<&Value> {
51 match self {
52 AttrsRep::Empty => None,
53
54 AttrsRep::KV { name, value } => match &**key {
55 b"name" => Some(name),
56 b"value" => Some(value),
57 _ => None,
58 },
59
60 AttrsRep::Map(map) => map.get(key),
61 }
62 }
63
64 fn contains(&self, key: &BStr) -> bool {
65 match self {
66 AttrsRep::Empty => false,
67 AttrsRep::KV { .. } => key == "name" || key == "value",
68 AttrsRep::Map(map) => map.contains_key(key),
69 }
70 }
71}
72
73#[repr(transparent)]
74#[derive(Clone, Debug, Default)]
75pub struct NixAttrs(pub(super) Rc<AttrsRep>);
76
77impl From<AttrsRep> for NixAttrs {
78 fn from(rep: AttrsRep) -> Self {
79 NixAttrs(Rc::new(rep))
80 }
81}
82
83impl<K, V> FromIterator<(K, V)> for NixAttrs
84where
85 NixString: From<K>,
86 Value: From<V>,
87{
88 fn from_iter<T>(iter: T) -> NixAttrs
89 where
90 T: IntoIterator<Item = (K, V)>,
91 {
92 AttrsRep::Map(
93 iter.into_iter()
94 .map(|(k, v)| (k.into(), v.into()))
95 .collect(),
96 )
97 .into()
98 }
99}
100
101impl From<BTreeMap<NixString, Value>> for NixAttrs {
102 fn from(map: BTreeMap<NixString, Value>) -> Self {
103 AttrsRep::Map(map.into_iter().collect()).into()
104 }
105}
106
107impl From<FxHashMap<NixString, Value>> for NixAttrs {
108 fn from(map: FxHashMap<NixString, Value>) -> Self {
109 AttrsRep::Map(map).into()
110 }
111}
112
113impl TotalDisplay for NixAttrs {
114 fn total_fmt(&self, f: &mut std::fmt::Formatter<'_>, set: &mut ThunkSet) -> std::fmt::Result {
115 if let Some(Value::String(s)) = self.select("type") {
116 if *s == "derivation" {
117 write!(f, "«derivation ")?;
118 if let Some(p) = self.select("drvPath") {
119 p.total_fmt(f, set)?;
120 } else {
121 write!(f, "???")?;
122 }
123 return write!(f, "»");
124 }
125 }
126
127 f.write_str("{ ")?;
128
129 for (name, value) in self.iter_sorted() {
130 write!(f, "{} = ", name.ident_str())?;
131 value.total_fmt(f, set)?;
132 f.write_str("; ")?;
133 }
134
135 f.write_str("}")
136 }
137}
138
139impl<'de> Deserialize<'de> for NixAttrs {
140 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
141 where
142 D: Deserializer<'de>,
143 {
144 struct MapVisitor;
145
146 impl<'de> Visitor<'de> for MapVisitor {
147 type Value = NixAttrs;
148
149 fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
150 formatter.write_str("a valid Nix attribute set")
151 }
152
153 fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
154 where
155 A: serde::de::MapAccess<'de>,
156 {
157 let mut stack_array = Vec::with_capacity(map.size_hint().unwrap_or(0) * 2);
158
159 while let Some((key, value)) = map.next_entry()? {
160 stack_array.push(key);
161 stack_array.push(value);
162 }
163
164 Ok(NixAttrs::construct(stack_array.len() / 2, stack_array)
165 .map_err(A::Error::custom)?
166 .expect("Catchable values are unreachable here"))
167 }
168 }
169
170 deserializer.deserialize_map(MapVisitor)
171 }
172}
173
174impl NixAttrs {
175 pub fn empty() -> Self {
176 AttrsRep::Empty.into()
177 }
178
179 pub fn ptr_eq(&self, other: &Self) -> bool {
184 Rc::ptr_eq(&self.0, &other.0)
185 }
186
187 pub fn update(self, other: Self) -> Self {
190 match (self.0.as_ref(), other.0.as_ref()) {
192 (AttrsRep::Empty, AttrsRep::Empty) => return self,
193 (AttrsRep::Empty, _) => return other,
194 (_, AttrsRep::Empty) => return self,
195 (AttrsRep::KV { .. }, AttrsRep::KV { .. }) => return other,
196
197 (AttrsRep::Map(_), AttrsRep::Map(_))
201 | (AttrsRep::Map(_), AttrsRep::KV { .. })
202 | (AttrsRep::KV { .. }, AttrsRep::Map(_)) => {}
203 };
204
205 match (Rc::unwrap_or_clone(self.0), Rc::unwrap_or_clone(other.0)) {
207 (AttrsRep::Map(mut m), AttrsRep::KV { name, value }) => {
208 m.insert(NAME.clone(), name);
209 m.insert(VALUE.clone(), value);
210 AttrsRep::Map(m).into()
211 }
212
213 (AttrsRep::KV { name, value }, AttrsRep::Map(mut m)) => {
214 match m.entry(NAME.clone()) {
215 hash_map::Entry::Vacant(e) => {
216 e.insert(name);
217 }
218
219 hash_map::Entry::Occupied(_) => { }
220 };
221
222 match m.entry(VALUE.clone()) {
223 hash_map::Entry::Vacant(e) => {
224 e.insert(value);
225 }
226
227 hash_map::Entry::Occupied(_) => { }
228 };
229
230 AttrsRep::Map(m).into()
231 }
232
233 (AttrsRep::Map(mut m1), AttrsRep::Map(mut m2)) => {
235 let map = if m1.len() >= m2.len() {
236 m1.extend(m2);
237 m1
238 } else {
239 for (key, val) in m1.into_iter() {
240 m2.entry(key).or_insert(val);
241 }
242 m2
243 };
244 AttrsRep::Map(map).into()
245 }
246
247 _ => unreachable!(),
249 }
250 }
251
252 pub fn len(&self) -> usize {
254 match self.0.as_ref() {
255 AttrsRep::Map(map) => map.len(),
256 AttrsRep::Empty => 0,
257 AttrsRep::KV { .. } => 2,
258 }
259 }
260
261 pub fn is_empty(&self) -> bool {
262 match self.0.as_ref() {
263 AttrsRep::Map(map) => map.is_empty(),
264 AttrsRep::Empty => true,
265 AttrsRep::KV { .. } => false,
266 }
267 }
268
269 pub fn select<K>(&self, key: &K) -> Option<&Value>
271 where
272 K: Borrow<BStr> + ?Sized,
273 {
274 self.0.select(key.borrow())
275 }
276
277 pub fn select_required<K>(&self, key: &K) -> Result<&Value, ErrorKind>
280 where
281 K: Borrow<BStr> + ?Sized,
282 {
283 self.select(key)
284 .ok_or_else(|| ErrorKind::AttributeNotFound {
285 name: key.borrow().to_string(),
286 })
287 }
288
289 pub fn contains<'a, K: 'a>(&self, key: K) -> bool
290 where
291 &'a BStr: From<K>,
292 {
293 self.0.contains(key.into())
294 }
295
296 #[allow(clippy::needless_lifetimes)]
298 pub fn iter<'a>(&'a self) -> Iter<KeyValue<'a>> {
299 Iter(match &self.0.as_ref() {
300 AttrsRep::Map(map) => KeyValue::Map(map.iter()),
301 AttrsRep::Empty => KeyValue::Empty,
302
303 AttrsRep::KV {
304 ref name,
305 ref value,
306 } => KeyValue::KV {
307 name,
308 value,
309 at: IterKV::default(),
310 },
311 })
312 }
313
314 pub fn iter_sorted(&self) -> Iter<KeyValue<'_>> {
317 Iter(match self.0.as_ref() {
318 AttrsRep::Empty => KeyValue::Empty,
319 AttrsRep::Map(map) => {
320 let sorted = map.iter().sorted_by_key(|x| x.0);
321 KeyValue::Sorted(sorted)
322 }
323 AttrsRep::KV {
324 ref name,
325 ref value,
326 } => KeyValue::KV {
327 name,
328 value,
329 at: IterKV::default(),
330 },
331 })
332 }
333
334 pub fn into_iter_sorted(self) -> OwnedAttrsIterator {
337 let iter = match Rc::<AttrsRep>::try_unwrap(self.0) {
338 Ok(attrs) => match attrs {
339 AttrsRep::Empty => IntoIterRepr::Empty,
340 AttrsRep::Map(map) => {
341 IntoIterRepr::Finite(map.into_iter().sorted_by(|(a, _), (b, _)| a.cmp(b)))
342 }
343 AttrsRep::KV { name, value } => IntoIterRepr::Finite(
344 vec![(NAME.clone(), name), (VALUE.clone(), value)].into_iter(),
345 ),
346 },
347 Err(rc) => match rc.as_ref() {
348 AttrsRep::Empty => IntoIterRepr::Empty,
349 AttrsRep::Map(map) => IntoIterRepr::Finite(
350 map.iter()
351 .map(|(k, v)| (k.clone(), v.clone()))
352 .sorted_by(|(a, _), (b, _)| a.cmp(b)),
353 ),
354 AttrsRep::KV { name, value } => IntoIterRepr::Finite(
355 vec![(NAME.clone(), name.clone()), (VALUE.clone(), value.clone())].into_iter(),
356 ),
357 },
358 };
359 OwnedAttrsIterator(iter)
360 }
361
362 pub fn keys(&self) -> Keys {
364 Keys(match self.0.as_ref() {
365 AttrsRep::Empty => KeysInner::Empty,
366 AttrsRep::KV { .. } => KeysInner::KV(IterKV::default()),
367
368 AttrsRep::Map(m) => KeysInner::Map(m.keys()),
370 })
371 }
372
373 pub fn keys_sorted(&self) -> Keys {
376 Keys(match self.0.as_ref() {
377 AttrsRep::Map(map) => KeysInner::Sorted(map.keys().sorted()),
378 AttrsRep::Empty => KeysInner::Empty,
379 AttrsRep::KV { .. } => KeysInner::KV(IterKV::default()),
380 })
381 }
382
383 pub fn construct(
386 count: usize,
387 mut stack_slice: Vec<Value>,
388 ) -> Result<Result<Self, CatchableErrorKind>, ErrorKind> {
389 debug_assert!(
390 stack_slice.len() == count * 2,
391 "construct_attrs called with count == {}, but slice.len() == {}",
392 count,
393 stack_slice.len(),
394 );
395
396 if count == 0 {
398 return Ok(Ok(AttrsRep::Empty.into()));
399 }
400
401 if count == 2 {
403 if let Some(kv) = attempt_optimise_kv(&mut stack_slice) {
404 return Ok(Ok(kv));
405 }
406 }
407
408 let mut attrs_map = FxHashMap::with_capacity_and_hasher(count, rustc_hash::FxBuildHasher);
409
410 for _ in 0..count {
411 let value = stack_slice.pop().unwrap();
412 let key = stack_slice.pop().unwrap();
413
414 match key {
415 Value::String(ks) => set_attr(&mut attrs_map, ks, value)?,
416
417 Value::Null => {
418 continue;
422 }
423
424 Value::Catchable(err) => return Ok(Err(*err)),
425
426 other => return Err(ErrorKind::InvalidAttributeName(other)),
427 }
428 }
429
430 Ok(Ok(AttrsRep::Map(attrs_map).into()))
431 }
432
433 pub(crate) fn from_kv(name: Value, value: Value) -> Self {
436 AttrsRep::KV { name, value }.into()
437 }
438
439 pub(crate) fn intersect(&self, other: &Self) -> NixAttrs {
442 match (self.0.as_ref(), other.0.as_ref()) {
443 (AttrsRep::Empty, _) | (_, AttrsRep::Empty) => AttrsRep::Empty.into(),
444 (AttrsRep::Map(lhs), AttrsRep::Map(rhs)) => {
445 let mut out = FxHashMap::with_capacity_and_hasher(
446 std::cmp::min(lhs.len(), rhs.len()),
447 rustc_hash::FxBuildHasher,
448 );
449 if lhs.len() < rhs.len() {
450 for key in lhs.keys() {
451 if let Some(val) = rhs.get(key) {
452 out.insert(key.clone(), val.clone());
453 }
454 }
455 } else {
456 for (key, val) in rhs.iter() {
457 if lhs.contains_key(key) {
458 out.insert(key.clone(), val.clone());
459 }
460 }
461 };
462 out.into()
463 }
464 (AttrsRep::Map(map), AttrsRep::KV { name, value }) => {
465 let mut out = FxHashMap::with_capacity_and_hasher(2, rustc_hash::FxBuildHasher);
466 if map.contains_key(NAME.as_bstr()) {
467 out.insert(NAME.clone(), name.clone());
468 }
469 if map.contains_key(VALUE.as_bstr()) {
470 out.insert(VALUE.clone(), value.clone());
471 }
472
473 if out.is_empty() {
474 NixAttrs::empty()
475 } else {
476 out.into()
477 }
478 }
479 (AttrsRep::KV { .. }, AttrsRep::Map(map)) => {
480 let mut out = FxHashMap::with_capacity_and_hasher(2, rustc_hash::FxBuildHasher);
481 if let Some(name) = map.get(NAME.as_bstr()) {
482 out.insert(NAME.clone(), name.clone());
483 }
484 if let Some(value) = map.get(VALUE.as_bstr()) {
485 out.insert(VALUE.clone(), value.clone());
486 }
487
488 if out.is_empty() {
489 NixAttrs::empty()
490 } else {
491 out.into()
492 }
493 }
494 (AttrsRep::KV { .. }, AttrsRep::KV { .. }) => other.clone(),
495 }
496 }
497}
498
499impl IntoIterator for NixAttrs {
500 type Item = (NixString, Value);
501 type IntoIter = OwnedAttrsIterator;
502
503 fn into_iter(self) -> Self::IntoIter {
504 match Rc::unwrap_or_clone(self.0) {
505 AttrsRep::Empty => OwnedAttrsIterator(IntoIterRepr::Empty),
506 AttrsRep::KV { name, value } => OwnedAttrsIterator(IntoIterRepr::Finite(
507 vec![(NAME.clone(), name), (VALUE.clone(), value)].into_iter(),
508 )),
509 AttrsRep::Map(map) => OwnedAttrsIterator(IntoIterRepr::Map(map.into_iter())),
510 }
511 }
512}
513
514fn attempt_optimise_kv(slice: &mut [Value]) -> Option<NixAttrs> {
528 let (name_idx, value_idx) = {
529 match (&slice[2], &slice[0]) {
530 (Value::String(s1), Value::String(s2)) if (*s1 == *NAME && *s2 == *VALUE) => (3, 1),
531 (Value::String(s1), Value::String(s2)) if (*s1 == *VALUE && *s2 == *NAME) => (1, 3),
532
533 _ => return None,
537 }
538 };
539
540 Some(NixAttrs::from_kv(
541 slice[name_idx].clone(),
542 slice[value_idx].clone(),
543 ))
544}
545
546fn set_attr(
549 map: &mut FxHashMap<NixString, Value>,
550 key: NixString,
551 value: Value,
552) -> Result<(), ErrorKind> {
553 match map.entry(key) {
554 hash_map::Entry::Occupied(entry) => Err(ErrorKind::DuplicateAttrsKey {
555 key: entry.key().to_string(),
556 }),
557
558 hash_map::Entry::Vacant(entry) => {
559 entry.insert(value);
560 Ok(())
561 }
562 }
563}
564
565#[derive(Debug, Default)]
568pub enum IterKV {
569 #[default]
570 Name,
571 Value,
572 Done,
573}
574
575impl IterKV {
576 fn next(&mut self) {
577 match *self {
578 Self::Name => *self = Self::Value,
579 Self::Value => *self = Self::Done,
580 Self::Done => {}
581 }
582 }
583}
584
585pub enum KeyValue<'a> {
588 Empty,
589
590 KV {
591 name: &'a Value,
592 value: &'a Value,
593 at: IterKV,
594 },
595
596 Map(hash_map::Iter<'a, NixString, Value>),
597
598 Sorted(std::vec::IntoIter<(&'a NixString, &'a Value)>),
599}
600
601#[repr(transparent)]
605pub struct Iter<T>(T);
606
607impl<'a> Iterator for Iter<KeyValue<'a>> {
608 type Item = (&'a NixString, &'a Value);
609
610 fn next(&mut self) -> Option<Self::Item> {
611 match &mut self.0 {
612 KeyValue::Map(inner) => inner.next(),
613 KeyValue::Empty => None,
614 KeyValue::KV { name, value, at } => match at {
615 IterKV::Name => {
616 at.next();
617 Some((&NAME, name))
618 }
619
620 IterKV::Value => {
621 at.next();
622 Some((&VALUE, value))
623 }
624
625 IterKV::Done => None,
626 },
627 KeyValue::Sorted(inner) => inner.next(),
628 }
629 }
630}
631
632impl ExactSizeIterator for Iter<KeyValue<'_>> {
633 fn len(&self) -> usize {
634 match &self.0 {
635 KeyValue::Empty => 0,
636 KeyValue::KV { .. } => 2,
637 KeyValue::Map(inner) => inner.len(),
638 KeyValue::Sorted(inner) => inner.len(),
639 }
640 }
641}
642
643enum KeysInner<'a> {
644 Empty,
645 KV(IterKV),
646 Map(hash_map::Keys<'a, NixString, Value>),
647 Sorted(std::vec::IntoIter<&'a NixString>),
648}
649
650pub struct Keys<'a>(KeysInner<'a>);
651
652impl<'a> Iterator for Keys<'a> {
653 type Item = &'a NixString;
654
655 fn next(&mut self) -> Option<Self::Item> {
656 match &mut self.0 {
657 KeysInner::Empty => None,
658 KeysInner::KV(at @ IterKV::Name) => {
659 at.next();
660 Some(&NAME)
661 }
662 KeysInner::KV(at @ IterKV::Value) => {
663 at.next();
664 Some(&VALUE)
665 }
666 KeysInner::KV(IterKV::Done) => None,
667 KeysInner::Map(m) => m.next(),
668 KeysInner::Sorted(v) => v.next(),
669 }
670 }
671}
672
673impl<'a> IntoIterator for &'a NixAttrs {
674 type Item = (&'a NixString, &'a Value);
675
676 type IntoIter = Iter<KeyValue<'a>>;
677
678 fn into_iter(self) -> Self::IntoIter {
679 self.iter()
680 }
681}
682
683impl ExactSizeIterator for Keys<'_> {
684 fn len(&self) -> usize {
685 match &self.0 {
686 KeysInner::Empty => 0,
687 KeysInner::KV(_) => 2,
688 KeysInner::Map(m) => m.len(),
689 KeysInner::Sorted(v) => v.len(),
690 }
691 }
692}
693
694pub enum IntoIterRepr {
696 Empty,
697 Finite(std::vec::IntoIter<(NixString, Value)>),
698 Map(hash_map::IntoIter<NixString, Value>),
699}
700
701#[repr(transparent)]
704pub struct OwnedAttrsIterator(IntoIterRepr);
705
706impl Iterator for OwnedAttrsIterator {
707 type Item = (NixString, Value);
708
709 fn next(&mut self) -> Option<Self::Item> {
710 match &mut self.0 {
711 IntoIterRepr::Empty => None,
712 IntoIterRepr::Finite(inner) => inner.next(),
713 IntoIterRepr::Map(m) => m.next(),
714 }
715 }
716}
717
718impl ExactSizeIterator for OwnedAttrsIterator {
719 fn len(&self) -> usize {
720 match &self.0 {
721 IntoIterRepr::Empty => 0,
722 IntoIterRepr::Finite(inner) => inner.len(),
723 IntoIterRepr::Map(inner) => inner.len(),
724 }
725 }
726}
727
728impl DoubleEndedIterator for OwnedAttrsIterator {
729 fn next_back(&mut self) -> Option<Self::Item> {
730 match &mut self.0 {
731 IntoIterRepr::Empty => None,
732 IntoIterRepr::Finite(inner) => inner.next_back(),
733 IntoIterRepr::Map(inner) => inner.next(),
735 }
736 }
737}