diagnostics_hierarchy/
lib.rs

1// Copyright 2019 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5//! Diagnostics hierarchy
6//!
7//! This library provides a tree strcture used to store diagnostics data such as inspect and logs,
8//! as well as utilities for reading from it, serializing and deserializing it and testing it.
9
10use base64::display::Base64Display;
11use fidl_fuchsia_diagnostics::{
12    PropertySelector, Selector, StringSelector, StringSelectorUnknown, SubtreeSelector,
13    TreeSelector,
14};
15use num_derive::{FromPrimitive, ToPrimitive};
16use num_traits::bounds::Bounded;
17use selectors::ValidateExt;
18use serde::{Deserialize, Serialize};
19use std::borrow::{Borrow, Cow};
20use std::cmp::Ordering;
21use std::collections::BTreeMap;
22use std::fmt::{Display, Formatter, Result as FmtResult};
23use std::ops::{Add, AddAssign, MulAssign};
24use thiserror::Error;
25
26pub mod macros;
27pub mod serialization;
28
29/// Extra slots for a linear histogram: 2 parameter slots (floor, step size) and
30/// 2 overflow slots.
31pub const LINEAR_HISTOGRAM_EXTRA_SLOTS: usize = 4;
32
33/// Extra slots for an exponential histogram: 3 parameter slots (floor, initial
34/// step and step multiplier) and 2 overflow slots.
35pub const EXPONENTIAL_HISTOGRAM_EXTRA_SLOTS: usize = 5;
36
37/// Format in which the array will be read.
38#[derive(Copy, Clone, Debug, PartialEq, Eq, FromPrimitive, ToPrimitive)]
39#[repr(u8)]
40pub enum ArrayFormat {
41    /// Regular array, it stores N values in N slots.
42    Default = 0,
43
44    /// The array is a linear histogram with N buckets and N+4 slots, which are:
45    /// - param_floor_value
46    /// - param_step_size
47    /// - underflow_bucket
48    /// - ...N buckets...
49    /// - overflow_bucket
50    LinearHistogram = 1,
51
52    /// The array is an exponential histogram with N buckets and N+5 slots, which are:
53    /// - param_floor_value
54    /// - param_initial_step
55    /// - param_step_multiplier
56    /// - underflow_bucket
57    /// - ...N buckets...
58    /// - overflow_bucket
59    ExponentialHistogram = 2,
60}
61
62/// A hierarchy of nodes representing structured data, such as Inspect or
63/// structured log data.
64///
65/// Each hierarchy consists of properties, and a map of named child hierarchies.
66#[derive(Clone, Debug, PartialEq)]
67pub struct DiagnosticsHierarchy<Key = String> {
68    /// The name of this node.
69    pub name: String,
70
71    /// The properties for the node.
72    pub properties: Vec<Property<Key>>,
73
74    /// The children of this node.
75    pub children: Vec<DiagnosticsHierarchy<Key>>,
76
77    /// Values that were impossible to load.
78    pub missing: Vec<MissingValue>,
79}
80
81/// A value that couldn't be loaded in the hierarchy and the reason.
82#[derive(Clone, Debug, PartialEq)]
83pub struct MissingValue {
84    /// Specific reason why the value couldn't be loaded.
85    pub reason: MissingValueReason,
86
87    /// The name of the value.
88    pub name: String,
89}
90
91/// Reasons why the value couldn't be loaded.
92#[derive(Clone, Debug, PartialEq)]
93pub enum MissingValueReason {
94    /// A referenced hierarchy in the link was not found.
95    LinkNotFound,
96
97    /// A linked hierarchy couldn't be parsed.
98    LinkParseFailure,
99
100    /// A linked hierarchy was invalid.
101    LinkInvalid,
102
103    /// There was no attempt to read the link.
104    LinkNeverExpanded,
105
106    /// There was a timeout while reading.
107    Timeout,
108}
109
110/// Compares the names of two properties or nodes. If both are unsigned integers, then it compares
111/// their numerical value.
112fn name_partial_cmp(a: &str, b: &str) -> Ordering {
113    match (a.parse::<u64>(), b.parse::<u64>()) {
114        (Ok(n), Ok(m)) => n.partial_cmp(&m).unwrap(),
115        _ => a.partial_cmp(b).unwrap(),
116    }
117}
118
119impl<Key> DiagnosticsHierarchy<Key>
120where
121    Key: AsRef<str>,
122{
123    /// Sorts the properties and children of the diagnostics hierarchy by name.
124    pub fn sort(&mut self) {
125        self.properties.sort_by(|p1, p2| name_partial_cmp(p1.name(), p2.name()));
126        self.children.sort_by(|c1, c2| name_partial_cmp(&c1.name, &c2.name));
127        for child in self.children.iter_mut() {
128            child.sort();
129        }
130    }
131
132    /// Creates a new empty diagnostics hierarchy with the root node named "root".
133    pub fn new_root() -> Self {
134        DiagnosticsHierarchy::new("root", vec![], vec![])
135    }
136
137    /// Creates a new diagnostics hierarchy with the given `name` for the root and the given
138    /// `properties` and `children` under that root.
139    pub fn new(
140        name: impl Into<String>,
141        properties: Vec<Property<Key>>,
142        children: Vec<DiagnosticsHierarchy<Key>>,
143    ) -> Self {
144        Self { name: name.into(), properties, children, missing: vec![] }
145    }
146
147    /// Either returns an existing child of `self` with name `name` or creates
148    /// a new child with name `name`.
149    pub fn get_or_add_child_mut<T>(&mut self, name: T) -> &mut DiagnosticsHierarchy<Key>
150    where
151        T: AsRef<str>,
152    {
153        // We have to use indices to iterate here because the borrow checker cannot
154        // deduce that there are no borrowed values in the else-branch.
155        // TODO(https://fxbug.dev/42122598): We could make this cleaner by changing the DiagnosticsHierarchy
156        // children to hashmaps.
157        match (0..self.children.len()).find(|&i| self.children[i].name == name.as_ref()) {
158            Some(matching_index) => &mut self.children[matching_index],
159            None => {
160                self.children.push(DiagnosticsHierarchy::new(name.as_ref(), vec![], vec![]));
161                self.children
162                    .last_mut()
163                    .expect("We just added an entry so we cannot get None here.")
164            }
165        }
166    }
167
168    /// Add a child to this DiagnosticsHierarchy.
169    ///
170    /// Note: It is possible to create multiple children with the same name using this method, but
171    /// readers may not support such a case.
172    pub fn add_child(&mut self, insert: DiagnosticsHierarchy<Key>) {
173        self.children.push(insert);
174    }
175
176    /// Creates and returns a new Node whose location in a hierarchy
177    /// rooted at `self` is defined by node_path.
178    ///
179    /// Requires: that node_path is not empty.
180    /// Requires: that node_path begin with the key fragment equal to the name of the node
181    ///           that add is being called on.
182    ///
183    /// NOTE: Inspect VMOs may allow multiple nodes of the same name. In this case,
184    ///        the first node found is returned.
185    pub fn get_or_add_node<T>(&mut self, node_path: &[T]) -> &mut DiagnosticsHierarchy<Key>
186    where
187        T: AsRef<str>,
188    {
189        assert!(!node_path.is_empty());
190        let mut iter = node_path.iter();
191        let first_path_string = iter.next().unwrap().as_ref();
192        // It is an invariant that the node path start with the key fragment equal to the
193        // name of the node that get_or_add_node is called on.
194        assert_eq!(first_path_string, &self.name);
195        let mut curr_node = self;
196        for node_path_entry in iter {
197            curr_node = curr_node.get_or_add_child_mut(node_path_entry);
198        }
199        curr_node
200    }
201
202    /// Inserts a new Property into this hierarchy.
203    pub fn add_property(&mut self, property: Property<Key>) {
204        self.properties.push(property);
205    }
206
207    /// Inserts a new Property into a Node whose location in a hierarchy
208    /// rooted at `self` is defined by node_path.
209    ///
210    /// Requires: that node_path is not empty.
211    /// Requires: that node_path begin with the key fragment equal to the name of the node
212    ///           that add is being called on.
213    ///
214    /// NOTE: Inspect VMOs may allow multiple nodes of the same name. In this case,
215    ///       the property is added to the first node found.
216    pub fn add_property_at_path<T>(&mut self, node_path: &[T], property: Property<Key>)
217    where
218        T: AsRef<str>,
219    {
220        self.get_or_add_node(node_path).properties.push(property);
221    }
222
223    /// Provides an iterator over the diagnostics hierarchy returning properties in pre-order.
224    pub fn property_iter(&self) -> DiagnosticsHierarchyIterator<'_, Key> {
225        DiagnosticsHierarchyIterator::new(self)
226    }
227
228    /// Adds a value that couldn't be read. This can happen when loading a lazy child.
229    pub fn add_missing(&mut self, reason: MissingValueReason, name: String) {
230        self.missing.push(MissingValue { reason, name });
231    }
232    /// Returns the property of the given |name| if one exists.
233    pub fn get_property(&self, name: &str) -> Option<&Property<Key>> {
234        self.properties.iter().find(|prop| prop.name() == name)
235    }
236
237    /// Returns the child of the given |name| if one exists.
238    pub fn get_child(&self, name: &str) -> Option<&DiagnosticsHierarchy<Key>> {
239        self.children.iter().find(|node| node.name == name)
240    }
241
242    /// Returns a mutable reference to the child of the given |name| if one exists.
243    pub fn get_child_mut(&mut self, name: &str) -> Option<&mut DiagnosticsHierarchy<Key>> {
244        self.children.iter_mut().find(|node| node.name == name)
245    }
246
247    /// Returns the child of the given |path| if one exists.
248    pub fn get_child_by_path(&self, path: &[&str]) -> Option<&DiagnosticsHierarchy<Key>> {
249        let mut result = Some(self);
250        for name in path {
251            result = result.and_then(|node| node.get_child(name));
252        }
253        result
254    }
255
256    /// Returns a mutable reference to the child of the given |path| if one exists.
257    pub fn get_child_by_path_mut(
258        &mut self,
259        path: &[&str],
260    ) -> Option<&mut DiagnosticsHierarchy<Key>> {
261        let mut result = Some(self);
262        for name in path {
263            result = result.and_then(|node| node.get_child_mut(name));
264        }
265        result
266    }
267
268    /// Returns the property of the given |name| if one exists.
269    pub fn get_property_by_path(&self, path: &[&str]) -> Option<&Property<Key>> {
270        let node = self.get_child_by_path(&path[..path.len() - 1]);
271        node.and_then(|node| node.get_property(path[path.len() - 1]))
272    }
273}
274
275macro_rules! property_type_getters_ref {
276    ($([$variant:ident, $fn_name:ident, $type:ty]),*) => {
277        paste::item! {
278          impl<Key> Property<Key> {
279              $(
280                  #[doc = "Returns the " $variant " value or `None` if the property isn't of that type"]
281                  pub fn $fn_name(&self) -> Option<&$type> {
282                      match self {
283                          Property::$variant(_, value) => Some(value),
284                          _ => None,
285                      }
286                  }
287              )*
288          }
289        }
290    }
291}
292
293macro_rules! property_type_getters_copy {
294    ($([$variant:ident, $fn_name:ident, $type:ty]),*) => {
295        paste::item! {
296          impl<Key> Property<Key> {
297              $(
298                  #[doc = "Returns the " $variant " value or `None` if the property isn't of that type"]
299                  pub fn $fn_name(&self) -> Option<$type> {
300                      match self {
301                          Property::$variant(_, value) => Some(*value),
302                          _ => None,
303                      }
304                  }
305              )*
306          }
307        }
308    }
309}
310
311property_type_getters_copy!(
312    [Int, int, i64],
313    [Uint, uint, u64],
314    [Double, double, f64],
315    [Bool, boolean, bool]
316);
317
318property_type_getters_ref!(
319    [String, string, str],
320    [Bytes, bytes, [u8]],
321    [DoubleArray, double_array, ArrayContent<f64>],
322    [IntArray, int_array, ArrayContent<i64>],
323    [UintArray, uint_array, ArrayContent<u64>],
324    [StringList, string_list, [String]]
325);
326
327struct WorkStackEntry<'a, Key> {
328    node: &'a DiagnosticsHierarchy<Key>,
329    key: Vec<&'a str>,
330}
331
332pub struct DiagnosticsHierarchyIterator<'a, Key> {
333    work_stack: Vec<WorkStackEntry<'a, Key>>,
334    current_key: Vec<&'a str>,
335    current_node: Option<&'a DiagnosticsHierarchy<Key>>,
336    current_property_index: usize,
337}
338
339impl<'a, Key> DiagnosticsHierarchyIterator<'a, Key> {
340    /// Creates a new iterator for the given `hierarchy`.
341    fn new(hierarchy: &'a DiagnosticsHierarchy<Key>) -> Self {
342        DiagnosticsHierarchyIterator {
343            work_stack: vec![WorkStackEntry { node: hierarchy, key: vec![&hierarchy.name] }],
344            current_key: vec![],
345            current_node: None,
346            current_property_index: 0,
347        }
348    }
349}
350
351impl<'a, Key> Iterator for DiagnosticsHierarchyIterator<'a, Key> {
352    /// Each item is a path to the node holding the resulting property.
353    /// If a node has no properties, a `None` will be returned for it.
354    /// If a node has properties a `Some` will be returned for each property and no `None` will be
355    /// returned.
356    type Item = (Vec<&'a str>, Option<&'a Property<Key>>);
357
358    fn next(&mut self) -> Option<Self::Item> {
359        loop {
360            let node = match self.current_node {
361                // If we are going through a node properties, that node will be set here.
362                Some(node) => node,
363                None => {
364                    // If we don't have a node we are currently working with, then go to the next
365                    // node in our stack.
366                    let WorkStackEntry { node, key } = self.work_stack.pop()?;
367
368                    // Push to the stack all children of the new node.
369                    for child in node.children.iter() {
370                        let mut child_key = key.clone();
371                        child_key.push(&child.name);
372                        self.work_stack.push(WorkStackEntry { node: child, key: child_key })
373                    }
374
375                    // If this node doesn't have any properties, we still want to return that it
376                    // exists, so we return with a property=None.
377                    if node.properties.is_empty() {
378                        return Some((key.clone(), None));
379                    }
380
381                    self.current_property_index = 0;
382                    self.current_key = key;
383
384                    node
385                }
386            };
387
388            // We were already done with this node. Try the next item in our stack.
389            if self.current_property_index == node.properties.len() {
390                self.current_node = None;
391                continue;
392            }
393
394            // Return the current property and advance our index to the next property we want to
395            // explore.
396            let property = &node.properties[self.current_property_index];
397            self.current_property_index += 1;
398            self.current_node = Some(node);
399
400            return Some((self.current_key.clone(), Some(property)));
401        }
402    }
403}
404
405/// A named property. Each of the fields consists of (name, value).
406///
407/// Key is the type of the property's name and is typically a string. In cases where
408/// there are well known, common property names, an alternative may be used to
409/// reduce copies of the name.
410#[derive(Debug, PartialEq, Clone)]
411pub enum Property<Key = String> {
412    /// The value is a string.
413    String(Key, String),
414
415    /// The value is a bytes vector.
416    Bytes(Key, Vec<u8>),
417
418    /// The value is an integer.
419    Int(Key, i64),
420
421    /// The value is an unsigned integer.
422    Uint(Key, u64),
423
424    /// The value is a double.
425    Double(Key, f64),
426
427    /// The value is a boolean.
428    Bool(Key, bool),
429
430    /// The value is a double array.
431    DoubleArray(Key, ArrayContent<f64>),
432
433    /// The value is an integer array.
434    IntArray(Key, ArrayContent<i64>),
435
436    /// The value is an unsigned integer array.
437    UintArray(Key, ArrayContent<u64>),
438
439    /// The value is a list of strings.
440    StringList(Key, Vec<String>),
441}
442
443impl<K> Property<K> {
444    /// Returns the key of a property
445    pub fn key(&self) -> &K {
446        match self {
447            Property::String(k, _) => k,
448            Property::Bytes(k, _) => k,
449            Property::Int(k, _) => k,
450            Property::Uint(k, _) => k,
451            Property::Double(k, _) => k,
452            Property::Bool(k, _) => k,
453            Property::DoubleArray(k, _) => k,
454            Property::IntArray(k, _) => k,
455            Property::UintArray(k, _) => k,
456            Property::StringList(k, _) => k,
457        }
458    }
459
460    /// Returns a string indicating which variant of property this is, useful for printing
461    /// debug values.
462    pub fn discriminant_name(&self) -> &'static str {
463        match self {
464            Property::String(_, _) => "String",
465            Property::Bytes(_, _) => "Bytes",
466            Property::Int(_, _) => "Int",
467            Property::IntArray(_, _) => "IntArray",
468            Property::Uint(_, _) => "Uint",
469            Property::UintArray(_, _) => "UintArray",
470            Property::Double(_, _) => "Double",
471            Property::DoubleArray(_, _) => "DoubleArray",
472            Property::Bool(_, _) => "Bool",
473            Property::StringList(_, _) => "StringList",
474        }
475    }
476
477    /// Return a a numeric property as a signed integer. Useful for having a single function to call
478    /// when a property has been passed through JSON, potentially losing its original signedness.
479    ///
480    /// Note: unsigned integers larger than `isize::MAX` will be returned as `None`. If you expect
481    /// values that high, consider calling `Property::int()` and `Property::uint()` directly.
482    pub fn number_as_int(&self) -> Option<i64> {
483        match self {
484            Property::Int(_, i) => Some(*i),
485            Property::Uint(_, u) => i64::try_from(*u).ok(),
486            Property::String(..)
487            | Property::Bytes(..)
488            | Property::Double(..)
489            | Property::Bool(..)
490            | Property::DoubleArray(..)
491            | Property::IntArray(..)
492            | Property::UintArray(..)
493            | Property::StringList(..) => None,
494        }
495    }
496}
497
498impl<K> Display for Property<K>
499where
500    K: AsRef<str>,
501{
502    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
503        macro_rules! pair {
504            ($fmt:literal, $val:expr) => {
505                write!(f, "{}={}", self.key().as_ref(), format_args!($fmt, $val))
506            };
507        }
508        match self {
509            Property::String(_, v) => pair!("{}", v),
510            Property::Bytes(_, v) => {
511                pair!("b64:{}", Base64Display::new(v, &base64::engine::general_purpose::STANDARD))
512            }
513            Property::Int(_, v) => pair!("{}", v),
514            Property::Uint(_, v) => pair!("{}", v),
515            Property::Double(_, v) => pair!("{}", v),
516            Property::Bool(_, v) => pair!("{}", v),
517            Property::DoubleArray(_, v) => pair!("{:?}", v),
518            Property::IntArray(_, v) => pair!("{:?}", v),
519            Property::UintArray(_, v) => pair!("{:?}", v),
520            Property::StringList(_, v) => pair!("{:?}", v),
521        }
522    }
523}
524
525/// Errors that can happen in this library.
526#[derive(Debug, Error)]
527pub enum Error {
528    #[error(
529        "Missing elements for {histogram_type:?} histogram. Expected {expected}, got {actual}"
530    )]
531    MissingHistogramElements { histogram_type: ArrayFormat, expected: usize, actual: usize },
532
533    #[error("TreeSelector only supports property and subtree selection.")]
534    InvalidTreeSelector,
535
536    #[error(transparent)]
537    Selectors(#[from] selectors::Error),
538
539    #[error(transparent)]
540    InvalidSelector(#[from] selectors::ValidationError),
541}
542
543impl Error {
544    fn missing_histogram_elements(
545        histogram_type: ArrayFormat,
546        actual: usize,
547        expected: usize,
548    ) -> Self {
549        Self::MissingHistogramElements { histogram_type, actual, expected }
550    }
551}
552
553/// A linear histogram property.
554#[cfg_attr(feature = "json_schema", derive(schemars::JsonSchema))]
555#[derive(Debug, Serialize, Deserialize, PartialEq, Clone)]
556pub struct LinearHistogram<T> {
557    /// The number of buckets. If indexes is None this should equal counts.len().
558    pub size: usize,
559
560    /// The floor of the lowest bucket (not counting the negative-infinity bucket).
561    pub floor: T,
562
563    /// The increment for each bucket range.
564    pub step: T,
565
566    /// The number of items in each bucket.
567    pub counts: Vec<T>,
568
569    /// If Some<_>, the indexes of nonzero counts.
570    #[serde(skip_serializing_if = "Option::is_none")]
571    pub indexes: Option<Vec<usize>>,
572}
573
574/// An exponential histogram property.
575#[cfg_attr(feature = "json_schema", derive(schemars::JsonSchema))]
576#[derive(Debug, Serialize, Deserialize, PartialEq, Clone)]
577pub struct ExponentialHistogram<T> {
578    /// The number of buckets. If indexes is None this should equal counts.len().
579    pub size: usize,
580
581    /// The floor of the lowest bucket (not counting the negative-infinity bucket).
582    pub floor: T,
583
584    /// The increment for the second floor.
585    pub initial_step: T,
586
587    /// The multiplier for each successive floor.
588    pub step_multiplier: T,
589
590    /// The number of items in each bucket.
591    pub counts: Vec<T>,
592
593    /// If Some<_>, the indexes of nonzero counts.
594    #[serde(skip_serializing_if = "Option::is_none")]
595    pub indexes: Option<Vec<usize>>,
596}
597
598/// Represents the content of a DiagnosticsHierarchy array property: a regular array or a
599/// linear/exponential histogram.
600#[derive(Debug, PartialEq, Clone)]
601pub enum ArrayContent<T> {
602    /// The contents of an array.
603    Values(Vec<T>),
604
605    /// The data for a linear histogram.
606    LinearHistogram(LinearHistogram<T>),
607
608    // The data for an exponential histogram.
609    ExponentialHistogram(ExponentialHistogram<T>),
610}
611
612impl<T> ArrayContent<T>
613where
614    T: Add<Output = T> + num_traits::Zero + AddAssign + Copy + MulAssign + PartialEq + Bounded,
615{
616    /// Creates a new ArrayContent parsing the `values` based on the given `format`.
617    pub fn new(values: Vec<T>, format: ArrayFormat) -> Result<Self, Error> {
618        match format {
619            ArrayFormat::Default => Ok(Self::Values(values)),
620            ArrayFormat::LinearHistogram => {
621                // Check that the minimum required values are available:
622                // floor, stepsize, underflow, bucket 0, overflow
623                if values.len() < 5 {
624                    return Err(Error::missing_histogram_elements(
625                        ArrayFormat::LinearHistogram,
626                        values.len(),
627                        5,
628                    ));
629                }
630                let original_counts = &values[2..];
631                let (counts, indexes) =
632                    match serialization::maybe_condense_histogram(original_counts, &None) {
633                        None => (original_counts.to_vec(), None),
634                        Some((counts, indexes)) => (counts, Some(indexes)),
635                    };
636                Ok(Self::LinearHistogram(LinearHistogram {
637                    floor: values[0],
638                    step: values[1],
639                    counts,
640                    indexes,
641                    size: values.len() - 2,
642                }))
643            }
644            ArrayFormat::ExponentialHistogram => {
645                // Check that the minimum required values are available:
646                // floor, initial step, step multiplier, underflow, bucket 0, overflow
647                if values.len() < 6 {
648                    return Err(Error::missing_histogram_elements(
649                        ArrayFormat::LinearHistogram,
650                        values.len(),
651                        5,
652                    ));
653                }
654                let original_counts = &values[3..];
655                let (counts, indexes) =
656                    match serialization::maybe_condense_histogram(original_counts, &None) {
657                        None => (original_counts.to_vec(), None),
658                        Some((counts, indexes)) => (counts, Some(indexes)),
659                    };
660                Ok(Self::ExponentialHistogram(ExponentialHistogram {
661                    floor: values[0],
662                    initial_step: values[1],
663                    step_multiplier: values[2],
664                    counts,
665                    indexes,
666                    size: values.len() - 3,
667                }))
668            }
669        }
670    }
671
672    /// Returns the number of items in the array.
673    pub fn len(&self) -> usize {
674        match self {
675            Self::Values(vals) => vals.len(),
676            Self::LinearHistogram(LinearHistogram { size, .. })
677            | Self::ExponentialHistogram(ExponentialHistogram { size, .. }) => *size,
678        }
679    }
680
681    /// Returns whether the array is empty or not.
682    pub fn is_empty(&self) -> bool {
683        self.len() == 0
684    }
685
686    /// Returns the raw values of this Array content. In the case of a histogram, returns the
687    /// bucket counts.
688    pub fn raw_values(&self) -> Cow<'_, Vec<T>> {
689        match self {
690            Self::Values(values) => Cow::Borrowed(values),
691            Self::LinearHistogram(LinearHistogram { size, counts, indexes, .. })
692            | Self::ExponentialHistogram(ExponentialHistogram { size, counts, indexes, .. }) => {
693                if let Some(indexes) = indexes {
694                    let mut values = vec![T::zero(); *size];
695                    for (count, index) in counts.iter().zip(indexes.iter()) {
696                        if index <= size {
697                            values[*index] = *count;
698                        }
699                    }
700                    Cow::Owned(values)
701                } else {
702                    Cow::Borrowed(counts)
703                }
704            }
705        }
706    }
707}
708
709pub mod testing {
710    use crate::ArrayContent;
711    use num_traits::bounds::Bounded;
712    use std::ops::{Add, AddAssign, MulAssign};
713
714    // Require test code to import CondensableOnDemand to access the
715    // condense_histogram() associated function.
716    pub trait CondensableOnDemand {
717        fn condense_histogram(&mut self);
718    }
719
720    fn condense_counts<T: num_traits::Zero + Copy + PartialEq>(
721        counts: &[T],
722    ) -> (Vec<T>, Vec<usize>) {
723        let mut condensed_counts = vec![];
724        let mut indexes = vec![];
725        for (index, count) in counts.iter().enumerate() {
726            if *count != T::zero() {
727                condensed_counts.push(*count);
728                indexes.push(index);
729            }
730        }
731        (condensed_counts, indexes)
732    }
733
734    impl<T> CondensableOnDemand for ArrayContent<T>
735    where
736        T: Add<Output = T> + num_traits::Zero + AddAssign + Copy + MulAssign + PartialEq + Bounded,
737    {
738        fn condense_histogram(&mut self) {
739            match self {
740                Self::Values(_) => (),
741                Self::LinearHistogram(histogram) => {
742                    if histogram.indexes.is_some() {
743                        return;
744                    }
745                    let (counts, indexes) = condense_counts(&histogram.counts);
746                    histogram.counts = counts;
747                    histogram.indexes = Some(indexes);
748                }
749                Self::ExponentialHistogram(histogram) => {
750                    if histogram.indexes.is_some() {
751                        return;
752                    }
753                    let (counts, indexes) = condense_counts(&histogram.counts);
754                    histogram.counts = counts;
755                    histogram.indexes = Some(indexes);
756                }
757            }
758        }
759    }
760}
761
762impl<Key> Property<Key>
763where
764    Key: AsRef<str>,
765{
766    /// Returns the key of a property.
767    pub fn name(&self) -> &str {
768        match self {
769            Property::String(name, _)
770            | Property::Bytes(name, _)
771            | Property::Int(name, _)
772            | Property::IntArray(name, _)
773            | Property::Uint(name, _)
774            | Property::UintArray(name, _)
775            | Property::Double(name, _)
776            | Property::Bool(name, _)
777            | Property::DoubleArray(name, _)
778            | Property::StringList(name, _) => name.as_ref(),
779        }
780    }
781}
782
783impl<T: Borrow<Selector>> TryFrom<&[T]> for HierarchyMatcher {
784    type Error = Error;
785
786    fn try_from(selectors: &[T]) -> Result<Self, Self::Error> {
787        // TODO(https://fxbug.dev/42069126: remove cloning, the archivist can probably hold
788        // HierarchyMatcher<'static>
789        let mut matcher = HierarchyMatcher::default();
790        for selector in selectors {
791            let selector = selector.borrow();
792            selector.validate().map_err(|e| Error::Selectors(e.into()))?;
793
794            // Safe to unwrap since we already validated the selector.
795            // TODO(https://fxbug.dev/42069126): instead of doing this over Borrow<Selector> do it over
796            // Selector.
797            match selector.tree_selector.clone().unwrap() {
798                TreeSelector::SubtreeSelector(subtree_selector) => {
799                    matcher.insert_subtree(subtree_selector.clone());
800                }
801                TreeSelector::PropertySelector(property_selector) => {
802                    matcher.insert_property(property_selector.clone());
803                }
804                _ => return Err(Error::Selectors(selectors::Error::InvalidTreeSelector)),
805            }
806        }
807        Ok(matcher)
808    }
809}
810
811impl<T: Borrow<Selector>> TryFrom<Vec<T>> for HierarchyMatcher {
812    type Error = Error;
813
814    fn try_from(selectors: Vec<T>) -> Result<Self, Self::Error> {
815        selectors[..].try_into()
816    }
817}
818
819#[derive(Debug)]
820struct OrdStringSelector(StringSelector);
821
822impl From<StringSelector> for OrdStringSelector {
823    fn from(selector: StringSelector) -> Self {
824        Self(selector)
825    }
826}
827
828impl Ord for OrdStringSelector {
829    fn cmp(&self, other: &OrdStringSelector) -> Ordering {
830        match (&self.0, &other.0) {
831            (StringSelector::ExactMatch(s), StringSelector::ExactMatch(o)) => s.cmp(o),
832            (StringSelector::StringPattern(s), StringSelector::StringPattern(o)) => s.cmp(o),
833            (StringSelector::ExactMatch(_), StringSelector::StringPattern(_)) => Ordering::Less,
834            (StringSelector::StringPattern(_), StringSelector::ExactMatch(_)) => Ordering::Greater,
835            (StringSelectorUnknown!(), StringSelector::ExactMatch(_)) => Ordering::Less,
836            (StringSelectorUnknown!(), StringSelector::StringPattern(_)) => Ordering::Less,
837            (StringSelectorUnknown!(), StringSelectorUnknown!()) => Ordering::Equal,
838        }
839    }
840}
841
842impl PartialOrd for OrdStringSelector {
843    fn partial_cmp(&self, other: &OrdStringSelector) -> Option<Ordering> {
844        Some(self.cmp(other))
845    }
846}
847
848impl PartialEq for OrdStringSelector {
849    fn eq(&self, other: &OrdStringSelector) -> bool {
850        match (&self.0, &other.0) {
851            (StringSelector::ExactMatch(s), StringSelector::ExactMatch(o)) => s.eq(o),
852            (StringSelector::StringPattern(s), StringSelector::StringPattern(o)) => s.eq(o),
853            (StringSelector::ExactMatch(_), StringSelector::StringPattern(_)) => false,
854            (StringSelector::StringPattern(_), StringSelector::ExactMatch(_)) => false,
855            (StringSelectorUnknown!(), StringSelectorUnknown!()) => true,
856        }
857    }
858}
859
860impl Eq for OrdStringSelector {}
861
862#[derive(Default, Debug)]
863pub struct HierarchyMatcher {
864    nodes: BTreeMap<OrdStringSelector, HierarchyMatcher>,
865    properties: Vec<OrdStringSelector>,
866    subtree: bool,
867}
868
869impl HierarchyMatcher {
870    pub fn new<I>(selectors: I) -> Result<Self, Error>
871    where
872        I: Iterator<Item = Selector>,
873    {
874        let mut matcher = HierarchyMatcher::default();
875        for selector in selectors {
876            selector.validate().map_err(|e| Error::Selectors(e.into()))?;
877
878            // Safe to unwrap since we already validated the selector.
879            match selector.tree_selector.unwrap() {
880                TreeSelector::SubtreeSelector(subtree_selector) => {
881                    matcher.insert_subtree(subtree_selector);
882                }
883                TreeSelector::PropertySelector(property_selector) => {
884                    matcher.insert_property(property_selector);
885                }
886                _ => return Err(Error::Selectors(selectors::Error::InvalidTreeSelector)),
887            }
888        }
889        Ok(matcher)
890    }
891
892    fn insert_subtree(&mut self, selector: SubtreeSelector) {
893        self.insert(selector.node_path, None);
894    }
895
896    fn insert_property(&mut self, selector: PropertySelector) {
897        self.insert(selector.node_path, Some(selector.target_properties));
898    }
899
900    fn insert(&mut self, node_path: Vec<StringSelector>, property: Option<StringSelector>) {
901        // Note: this could have additional optimization so that branches are collapsed into a
902        // single one (for example foo/bar is included by f*o/bar), however, in practice, we don't
903        // hit that edge case.
904        let mut matcher = self;
905        for node in node_path {
906            matcher = matcher.nodes.entry(node.into()).or_default();
907        }
908        match property {
909            Some(property) => {
910                matcher.properties.push(property.into());
911            }
912            None => matcher.subtree = true,
913        }
914    }
915}
916
917#[derive(Debug, PartialEq)]
918pub enum SelectResult<'a, Key> {
919    Properties(Vec<&'a Property<Key>>),
920    Nodes(Vec<&'a DiagnosticsHierarchy<Key>>),
921}
922
923impl<'a, Key> SelectResult<'a, Key> {
924    /// Returns Err(()) if `self` is `Self::Nodes`. Otherwise, adds to property list.
925    fn add_property(&mut self, prop: &'a Property<Key>) {
926        let Self::Properties(v) = self else {
927            panic!("must be Self::Properties to call add_property");
928        };
929        v.push(prop);
930    }
931
932    /// Returns Err(()) if `self` is `Self::Properties`. Otherwise, adds to property list.
933    fn add_node(&mut self, node: &'a DiagnosticsHierarchy<Key>) {
934        let Self::Nodes(v) = self else {
935            panic!("must be Self::Nodes to call add_node");
936        };
937        v.push(node);
938    }
939}
940
941pub fn select_from_hierarchy<'a, 'b, Key>(
942    root_node: &'a DiagnosticsHierarchy<Key>,
943    selector: &'b Selector,
944) -> Result<SelectResult<'a, Key>, Error>
945where
946    Key: AsRef<str>,
947    'a: 'b,
948{
949    selector.validate()?;
950
951    struct StackEntry<'a, Key> {
952        node: &'a DiagnosticsHierarchy<Key>,
953        node_path_index: usize,
954        explored_path: Vec<&'a str>,
955    }
956
957    // Safe to unwrap since we validated above.
958    let (node_path, property_selector, stack_entry) = match selector.tree_selector.as_ref().unwrap()
959    {
960        TreeSelector::SubtreeSelector(ref subtree_selector) => (
961            &subtree_selector.node_path,
962            None,
963            StackEntry { node: root_node, node_path_index: 0, explored_path: vec![] },
964        ),
965        TreeSelector::PropertySelector(ref property_selector) => (
966            &property_selector.node_path,
967            Some(&property_selector.target_properties),
968            StackEntry { node: root_node, node_path_index: 0, explored_path: vec![] },
969        ),
970        _ => return Err(Error::InvalidTreeSelector),
971    };
972
973    let mut stack = vec![stack_entry];
974    let mut result = if property_selector.is_some() {
975        SelectResult::Properties(vec![])
976    } else {
977        SelectResult::Nodes(vec![])
978    };
979
980    while let Some(StackEntry { node, node_path_index, mut explored_path }) = stack.pop() {
981        // Unwrap is safe since we validate is_empty right above.
982        if !selectors::match_string(&node_path[node_path_index], &node.name) {
983            continue;
984        }
985        explored_path.push(&node.name);
986
987        // If we are at the last node in the path, then we just need to explore the properties.
988        // Otherwise, we explore the children of the current node and the properties.
989        if node_path_index != node_path.len() - 1 {
990            // If this node matches the next selector we are looking at, then explore its children.
991            for child in node.children.iter() {
992                stack.push(StackEntry {
993                    node: child,
994                    node_path_index: node_path_index + 1,
995                    explored_path: explored_path.clone(),
996                });
997            }
998        } else if let Some(s) = property_selector {
999            // If we have a property selector, then add any properties matching it to our result.
1000            for property in &node.properties {
1001                if selectors::match_string(s, property.key()) {
1002                    result.add_property(property);
1003                }
1004            }
1005        } else {
1006            // If we don't have a property selector and we reached the end of the node path, then
1007            // we should add the current node to the result.
1008            result.add_node(node);
1009        }
1010    }
1011
1012    Ok(result)
1013}
1014
1015/// Filters a hierarchy given a tree selector.
1016pub fn filter_tree<Key>(
1017    root_node: DiagnosticsHierarchy<Key>,
1018    selectors: &[TreeSelector],
1019) -> Option<DiagnosticsHierarchy<Key>>
1020where
1021    Key: AsRef<str>,
1022{
1023    let mut matcher = HierarchyMatcher::default();
1024    for selector in selectors {
1025        match selector {
1026            TreeSelector::SubtreeSelector(subtree_selector) => {
1027                matcher.insert_subtree(subtree_selector.clone());
1028            }
1029            TreeSelector::PropertySelector(property_selector) => {
1030                matcher.insert_property(property_selector.clone());
1031            }
1032            _ => {}
1033        }
1034    }
1035    filter_hierarchy(root_node, &matcher)
1036}
1037
1038/// Filters a diagnostics hierarchy using a set of path selectors and their associated property
1039/// selectors.
1040///
1041/// If the return type is None that implies that the filter encountered no errors AND the tree was
1042/// filtered to be empty at the end.
1043pub fn filter_hierarchy<Key>(
1044    mut root_node: DiagnosticsHierarchy<Key>,
1045    hierarchy_matcher: &HierarchyMatcher,
1046) -> Option<DiagnosticsHierarchy<Key>>
1047where
1048    Key: AsRef<str>,
1049{
1050    let starts_empty = root_node.children.is_empty() && root_node.properties.is_empty();
1051    if filter_hierarchy_helper(&mut root_node, &[hierarchy_matcher]) {
1052        if !starts_empty && root_node.children.is_empty() && root_node.properties.is_empty() {
1053            return None;
1054        }
1055        return Some(root_node);
1056    }
1057    None
1058}
1059
1060fn filter_hierarchy_helper<Key>(
1061    node: &mut DiagnosticsHierarchy<Key>,
1062    hierarchy_matchers: &[&HierarchyMatcher],
1063) -> bool
1064where
1065    Key: AsRef<str>,
1066{
1067    let child_matchers = eval_matchers_on_node_name(&node.name, hierarchy_matchers);
1068    if child_matchers.is_empty() {
1069        node.children.clear();
1070        node.properties.clear();
1071        return false;
1072    }
1073
1074    if child_matchers.iter().any(|m| m.subtree) {
1075        return true;
1076    }
1077
1078    node.children.retain_mut(|child| filter_hierarchy_helper(child, &child_matchers));
1079    node.properties.retain_mut(|prop| eval_matchers_on_property(prop.name(), &child_matchers));
1080
1081    !(node.children.is_empty() && node.properties.is_empty())
1082}
1083
1084fn eval_matchers_on_node_name<'a>(
1085    node_name: &'a str,
1086    matchers: &'a [&'a HierarchyMatcher],
1087) -> Vec<&'a HierarchyMatcher> {
1088    let mut result = vec![];
1089    for matcher in matchers {
1090        for (node_pattern, tree_matcher) in matcher.nodes.iter() {
1091            if selectors::match_string(&node_pattern.0, node_name) {
1092                result.push(tree_matcher);
1093            }
1094        }
1095    }
1096    result
1097}
1098
1099fn eval_matchers_on_property(property_name: &str, matchers: &[&HierarchyMatcher]) -> bool {
1100    matchers.iter().any(|matcher| {
1101        matcher
1102            .properties
1103            .iter()
1104            .any(|property_pattern| selectors::match_string(&property_pattern.0, property_name))
1105    })
1106}
1107
1108/// The parameters of an exponential histogram.
1109#[derive(Clone)]
1110pub struct ExponentialHistogramParams<T: Clone> {
1111    /// The floor of the exponential histogram.
1112    pub floor: T,
1113
1114    /// The initial step of the exponential histogram.
1115    pub initial_step: T,
1116
1117    /// The step multiplier of the exponential histogram.
1118    pub step_multiplier: T,
1119
1120    /// The number of buckets that the exponential histogram can have. This doesn't include the
1121    /// overflow and underflow buckets.
1122    pub buckets: usize,
1123}
1124
1125/// The parameters of a linear histogram.
1126#[derive(Clone)]
1127pub struct LinearHistogramParams<T: Clone> {
1128    /// The floor of the linear histogram.
1129    pub floor: T,
1130
1131    /// The step size of the linear histogram.
1132    pub step_size: T,
1133
1134    /// The number of buckets that the linear histogram can have. This doesn't include the overflow
1135    /// and underflow buckets.
1136    pub buckets: usize,
1137}
1138
1139/// A type which can function as a "view" into a diagnostics hierarchy, optionally allocating a new
1140/// instance to service a request.
1141pub trait DiagnosticsHierarchyGetter<K: Clone> {
1142    fn get_diagnostics_hierarchy<'a>(
1143        &'a self,
1144    ) -> impl std::future::Future<Output = Cow<'_, DiagnosticsHierarchy<K>>>
1145    where
1146        K: 'a;
1147}
1148
1149impl<K: Clone> DiagnosticsHierarchyGetter<K> for DiagnosticsHierarchy<K> {
1150    async fn get_diagnostics_hierarchy<'a>(&'a self) -> Cow<'_, DiagnosticsHierarchy<K>>
1151    where
1152        K: 'a,
1153    {
1154        Cow::Borrowed(self)
1155    }
1156}
1157
1158#[cfg(test)]
1159mod tests {
1160    use super::*;
1161    use crate::testing::CondensableOnDemand;
1162    use test_case::test_case;
1163
1164    use assert_matches::assert_matches;
1165    use selectors::VerboseError;
1166    use std::sync::Arc;
1167
1168    fn validate_hierarchy_iteration(
1169        mut results_vec: Vec<(Vec<String>, Option<Property>)>,
1170        test_hierarchy: DiagnosticsHierarchy,
1171    ) {
1172        let expected_num_entries = results_vec.len();
1173        let mut num_entries = 0;
1174        for (key, val) in test_hierarchy.property_iter() {
1175            num_entries += 1;
1176            let (expected_key, expected_property) = results_vec.pop().unwrap();
1177            assert_eq!(key.to_vec().join("/"), expected_key.to_vec().join("/"));
1178            assert_eq!(val, expected_property.as_ref());
1179        }
1180
1181        assert_eq!(num_entries, expected_num_entries);
1182    }
1183
1184    #[fuchsia::test]
1185    fn test_diagnostics_hierarchy_iteration() {
1186        let double_array_data = vec![-1.2, 2.3, 3.4, 4.5, -5.6];
1187        let chars = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
1188        let string_data = chars.iter().cycle().take(6000).collect::<String>();
1189        let bytes_data = (0u8..=9u8).cycle().take(5000).collect::<Vec<u8>>();
1190
1191        let test_hierarchy = DiagnosticsHierarchy::new(
1192            "root".to_string(),
1193            vec![
1194                Property::Int("int-root".to_string(), 3),
1195                Property::DoubleArray(
1196                    "property-double-array".to_string(),
1197                    ArrayContent::Values(double_array_data.clone()),
1198                ),
1199            ],
1200            vec![DiagnosticsHierarchy::new(
1201                "child-1".to_string(),
1202                vec![
1203                    Property::Uint("property-uint".to_string(), 10),
1204                    Property::Double("property-double".to_string(), -3.4),
1205                    Property::String("property-string".to_string(), string_data.clone()),
1206                    Property::IntArray(
1207                        "property-int-array".to_string(),
1208                        ArrayContent::new(vec![1, 2, 1, 1, 1, 1, 1], ArrayFormat::LinearHistogram)
1209                            .unwrap(),
1210                    ),
1211                ],
1212                vec![DiagnosticsHierarchy::new(
1213                    "child-1-1".to_string(),
1214                    vec![
1215                        Property::Int("property-int".to_string(), -9),
1216                        Property::Bytes("property-bytes".to_string(), bytes_data.clone()),
1217                        Property::UintArray(
1218                            "property-uint-array".to_string(),
1219                            ArrayContent::new(
1220                                vec![1, 1, 2, 0, 1, 1, 2, 0, 0],
1221                                ArrayFormat::ExponentialHistogram,
1222                            )
1223                            .unwrap(),
1224                        ),
1225                    ],
1226                    vec![],
1227                )],
1228            )],
1229        );
1230
1231        let results_vec = vec![
1232            (
1233                vec!["root".to_string(), "child-1".to_string(), "child-1-1".to_string()],
1234                Some(Property::UintArray(
1235                    "property-uint-array".to_string(),
1236                    ArrayContent::new(
1237                        vec![1, 1, 2, 0, 1, 1, 2, 0, 0],
1238                        ArrayFormat::ExponentialHistogram,
1239                    )
1240                    .unwrap(),
1241                )),
1242            ),
1243            (
1244                vec!["root".to_string(), "child-1".to_string(), "child-1-1".to_string()],
1245                Some(Property::Bytes("property-bytes".to_string(), bytes_data)),
1246            ),
1247            (
1248                vec!["root".to_string(), "child-1".to_string(), "child-1-1".to_string()],
1249                Some(Property::Int("property-int".to_string(), -9)),
1250            ),
1251            (
1252                vec!["root".to_string(), "child-1".to_string()],
1253                Some(Property::IntArray(
1254                    "property-int-array".to_string(),
1255                    ArrayContent::new(vec![1, 2, 1, 1, 1, 1, 1], ArrayFormat::LinearHistogram)
1256                        .unwrap(),
1257                )),
1258            ),
1259            (
1260                vec!["root".to_string(), "child-1".to_string()],
1261                Some(Property::String("property-string".to_string(), string_data)),
1262            ),
1263            (
1264                vec!["root".to_string(), "child-1".to_string()],
1265                Some(Property::Double("property-double".to_string(), -3.4)),
1266            ),
1267            (
1268                vec!["root".to_string(), "child-1".to_string()],
1269                Some(Property::Uint("property-uint".to_string(), 10)),
1270            ),
1271            (
1272                vec!["root".to_string()],
1273                Some(Property::DoubleArray(
1274                    "property-double-array".to_string(),
1275                    ArrayContent::Values(double_array_data),
1276                )),
1277            ),
1278            (vec!["root".to_string()], Some(Property::Int("int-root".to_string(), 3))),
1279        ];
1280
1281        validate_hierarchy_iteration(results_vec, test_hierarchy);
1282    }
1283
1284    #[fuchsia::test]
1285    fn test_getters() {
1286        let a_prop = Property::Int("a".to_string(), 1);
1287        let b_prop = Property::Uint("b".to_string(), 2);
1288        let child2 = DiagnosticsHierarchy::new("child2".to_string(), vec![], vec![]);
1289        let child = DiagnosticsHierarchy::new(
1290            "child".to_string(),
1291            vec![b_prop.clone()],
1292            vec![child2.clone()],
1293        );
1294        let mut hierarchy = DiagnosticsHierarchy::new(
1295            "root".to_string(),
1296            vec![a_prop.clone()],
1297            vec![child.clone()],
1298        );
1299        assert_matches!(hierarchy.get_child("child"), Some(node) if *node == child);
1300        assert_matches!(hierarchy.get_child_mut("child"), Some(node) if *node == child);
1301        assert_matches!(hierarchy.get_child_by_path(&["child", "child2"]),
1302                        Some(node) if *node == child2);
1303        assert_matches!(hierarchy.get_child_by_path_mut(&["child", "child2"]),
1304                        Some(node) if *node == child2);
1305        assert_matches!(hierarchy.get_property("a"), Some(prop) if *prop == a_prop);
1306        assert_matches!(hierarchy.get_property_by_path(&["child", "b"]),
1307                        Some(prop) if *prop == b_prop);
1308    }
1309
1310    #[fuchsia::test]
1311    fn test_edge_case_hierarchy_iteration() {
1312        let root_only_with_one_property_hierarchy = DiagnosticsHierarchy::new(
1313            "root".to_string(),
1314            vec![Property::Int("property-int".to_string(), -9)],
1315            vec![],
1316        );
1317
1318        let results_vec =
1319            vec![(vec!["root".to_string()], Some(Property::Int("property-int".to_string(), -9)))];
1320
1321        validate_hierarchy_iteration(results_vec, root_only_with_one_property_hierarchy);
1322
1323        let empty_hierarchy = DiagnosticsHierarchy::new("root".to_string(), vec![], vec![]);
1324
1325        let results_vec = vec![(vec!["root".to_string()], None)];
1326
1327        validate_hierarchy_iteration(results_vec, empty_hierarchy);
1328
1329        let empty_root_populated_child = DiagnosticsHierarchy::new(
1330            "root",
1331            vec![],
1332            vec![DiagnosticsHierarchy::new(
1333                "foo",
1334                vec![Property::Int("11".to_string(), -4)],
1335                vec![],
1336            )],
1337        );
1338
1339        let results_vec = vec![
1340            (
1341                vec!["root".to_string(), "foo".to_string()],
1342                Some(Property::Int("11".to_string(), -4)),
1343            ),
1344            (vec!["root".to_string()], None),
1345        ];
1346
1347        validate_hierarchy_iteration(results_vec, empty_root_populated_child);
1348
1349        let empty_root_empty_child = DiagnosticsHierarchy::new(
1350            "root",
1351            vec![],
1352            vec![DiagnosticsHierarchy::new("foo", vec![], vec![])],
1353        );
1354
1355        let results_vec = vec![
1356            (vec!["root".to_string(), "foo".to_string()], None),
1357            (vec!["root".to_string()], None),
1358        ];
1359
1360        validate_hierarchy_iteration(results_vec, empty_root_empty_child);
1361    }
1362
1363    #[fuchsia::test]
1364    fn array_value() {
1365        let values = vec![1, 2, 5, 7, 9, 11, 13];
1366        let array = ArrayContent::<u64>::new(values.clone(), ArrayFormat::Default);
1367        assert_matches!(array, Ok(ArrayContent::Values(vals)) if vals == values);
1368    }
1369
1370    #[fuchsia::test]
1371    fn linear_histogram_array_value() {
1372        let values = vec![1, 2, 5, 7, 9, 11, 13];
1373        let array = ArrayContent::<i64>::new(values, ArrayFormat::LinearHistogram);
1374        assert_matches!(array, Ok(ArrayContent::LinearHistogram(hist))
1375            if hist == LinearHistogram {
1376                floor: 1,
1377                step: 2,
1378                counts: vec![5, 7, 9, 11, 13],
1379                indexes: None,
1380                size: 5,
1381            }
1382        );
1383    }
1384
1385    #[fuchsia::test]
1386    fn exponential_histogram_array_value() {
1387        let values = vec![1.0, 2.0, 5.0, 7.0, 9.0, 11.0, 15.0];
1388        let array = ArrayContent::<f64>::new(values, ArrayFormat::ExponentialHistogram);
1389        assert_matches!(array, Ok(ArrayContent::ExponentialHistogram(hist))
1390            if hist == ExponentialHistogram {
1391                floor: 1.0,
1392                initial_step: 2.0,
1393                step_multiplier: 5.0,
1394                counts: vec![7.0, 9.0, 11.0, 15.0],
1395                indexes: None,
1396                size: 4,
1397            }
1398        );
1399    }
1400
1401    #[fuchsia::test]
1402    fn deserialize_linear_int_histogram() -> Result<(), serde_json::Error> {
1403        let json = r#"{
1404            "root": {
1405                "histogram": {
1406                    "floor": -2,
1407                    "step": 3,
1408                    "counts": [4, 5, 6],
1409                    "size": 3
1410                }
1411            }
1412        }"#;
1413        let parsed: DiagnosticsHierarchy = serde_json::from_str(json)?;
1414        let expected = DiagnosticsHierarchy::new(
1415            "root".to_string(),
1416            vec![Property::IntArray(
1417                "histogram".to_string(),
1418                ArrayContent::new(vec![-2, 3, 4, 5, 6], ArrayFormat::LinearHistogram).unwrap(),
1419            )],
1420            vec![],
1421        );
1422        assert_eq!(parsed, expected);
1423        Ok(())
1424    }
1425
1426    #[fuchsia::test]
1427    fn deserialize_exponential_int_histogram() -> Result<(), serde_json::Error> {
1428        let json = r#"{
1429            "root": {
1430                "histogram": {
1431                    "floor": 1,
1432                    "initial_step": 3,
1433                    "step_multiplier": 2,
1434                    "counts": [4, 5, 6],
1435                    "size": 3
1436                }
1437            }
1438        }"#;
1439        let parsed: DiagnosticsHierarchy = serde_json::from_str(json)?;
1440        let expected = DiagnosticsHierarchy::new(
1441            "root".to_string(),
1442            vec![Property::IntArray(
1443                "histogram".to_string(),
1444                ArrayContent::new(vec![1, 3, 2, 4, 5, 6], ArrayFormat::ExponentialHistogram)
1445                    .unwrap(),
1446            )],
1447            vec![],
1448        );
1449        assert_eq!(parsed, expected);
1450        Ok(())
1451    }
1452
1453    #[fuchsia::test]
1454    fn deserialize_linear_uint_histogram() -> Result<(), serde_json::Error> {
1455        let json = r#"{
1456            "root": {
1457                "histogram": {
1458                    "floor": 2,
1459                    "step": 3,
1460                    "counts": [4, 9223372036854775808, 6],
1461                    "size": 3
1462                }
1463            }
1464        }"#;
1465        let parsed: DiagnosticsHierarchy = serde_json::from_str(json)?;
1466        let expected = DiagnosticsHierarchy::new(
1467            "root".to_string(),
1468            vec![Property::UintArray(
1469                "histogram".to_string(),
1470                ArrayContent::new(
1471                    vec![2, 3, 4, 9_223_372_036_854_775_808, 6],
1472                    ArrayFormat::LinearHistogram,
1473                )
1474                .unwrap(),
1475            )],
1476            vec![],
1477        );
1478        assert_eq!(parsed, expected);
1479        Ok(())
1480    }
1481
1482    #[fuchsia::test]
1483    fn deserialize_linear_double_histogram() -> Result<(), serde_json::Error> {
1484        let json = r#"{
1485            "root": {
1486                "histogram": {
1487                    "floor": 2.0,
1488                    "step": 3.0,
1489                    "counts": [4.0, 5.0, 6.0],
1490                    "size": 3
1491                }
1492            }
1493        }"#;
1494        let parsed: DiagnosticsHierarchy = serde_json::from_str(json)?;
1495        let expected = DiagnosticsHierarchy::new(
1496            "root".to_string(),
1497            vec![Property::DoubleArray(
1498                "histogram".to_string(),
1499                ArrayContent::new(vec![2.0, 3.0, 4.0, 5.0, 6.0], ArrayFormat::LinearHistogram)
1500                    .unwrap(),
1501            )],
1502            vec![],
1503        );
1504        assert_eq!(parsed, expected);
1505        Ok(())
1506    }
1507
1508    #[fuchsia::test]
1509    fn deserialize_sparse_histogram() -> Result<(), serde_json::Error> {
1510        let json = r#"{
1511            "root": {
1512                "histogram": {
1513                    "floor": 2,
1514                    "step": 3,
1515                    "counts": [4, 5, 6],
1516                    "indexes": [1, 2, 4],
1517                    "size": 8
1518                }
1519            }
1520        }"#;
1521        let parsed: DiagnosticsHierarchy = serde_json::from_str(json)?;
1522
1523        let mut histogram =
1524            ArrayContent::new(vec![2, 3, 0, 4, 5, 0, 6, 0, 0, 0], ArrayFormat::LinearHistogram)
1525                .unwrap();
1526        histogram.condense_histogram();
1527        let expected = DiagnosticsHierarchy::new(
1528            "root".to_string(),
1529            vec![Property::IntArray("histogram".to_string(), histogram)],
1530            vec![],
1531        );
1532        assert_eq!(parsed, expected);
1533        Ok(())
1534    }
1535
1536    // If a struct can't be parsed as a valid histogram, it will be created as a Node. So if
1537    // there's a node "histogram" (as opposed to a property "histogram") then it didn't parse
1538    // as a histogram.
1539
1540    #[fuchsia::test]
1541    fn reject_histogram_incompatible_values() -> Result<(), serde_json::Error> {
1542        let json = r#"{
1543            "root": {
1544                "histogram": {
1545                    "floor": -2,
1546                    "step": 3,
1547                    "counts": [4, 9223372036854775808, 6],
1548                    "size": 3
1549                }
1550            }
1551        }"#;
1552        let parsed: DiagnosticsHierarchy = serde_json::from_str(json)?;
1553        assert_eq!(parsed.children.len(), 1);
1554        assert_eq!(&parsed.children[0].name, "histogram");
1555        Ok(())
1556    }
1557
1558    #[fuchsia::test]
1559    fn reject_histogram_bad_sparse_list() -> Result<(), serde_json::Error> {
1560        let json = r#"{
1561            "root": {
1562                "histogram": {
1563                    "floor": -2,
1564                    "step": 3,
1565                    "counts": [4, 5, 6],
1566                    "indexes": [0, 1, 2, 3],
1567                    "size": 8
1568                }
1569            }
1570        }"#;
1571        let parsed: DiagnosticsHierarchy = serde_json::from_str(json)?;
1572        assert_eq!(parsed.children.len(), 1);
1573        assert_eq!(&parsed.children[0].name, "histogram");
1574        Ok(())
1575    }
1576
1577    #[fuchsia::test]
1578    fn reject_histogram_bad_index() -> Result<(), serde_json::Error> {
1579        let json = r#"{
1580            "root": {
1581                "histogram": {
1582                    "floor": -2,
1583                    "step": 3,
1584                    "counts": [4, 5, 6],
1585                    "indexes": [0, 1, 4],
1586                    "size": 4
1587                }
1588            }
1589        }"#;
1590        let parsed: DiagnosticsHierarchy = serde_json::from_str(json)?;
1591        assert_eq!(parsed.children.len(), 1);
1592        assert_eq!(&parsed.children[0].name, "histogram");
1593        Ok(())
1594    }
1595
1596    #[fuchsia::test]
1597    fn reject_histogram_wrong_field() -> Result<(), serde_json::Error> {
1598        let json = r#"{
1599            "root": {
1600                "histogram": {
1601                    "floor": 2,
1602                    "step": 3,
1603                    "counts": [4, 5, 6],
1604                    "incorrect": [0, 1, 3],
1605                    "size": 4
1606                }
1607            }
1608        }"#;
1609        let parsed: DiagnosticsHierarchy = serde_json::from_str(json)?;
1610        assert_eq!(parsed.children.len(), 1);
1611        assert_eq!(&parsed.children[0].name, "histogram");
1612        Ok(())
1613    }
1614
1615    #[fuchsia::test]
1616    fn exponential_histogram() {
1617        let values = vec![0, 2, 4, 0, 1, 2, 3, 4, 5];
1618        let array = ArrayContent::new(values, ArrayFormat::ExponentialHistogram);
1619        assert_matches!(array, Ok(ArrayContent::ExponentialHistogram(hist))
1620            if hist == ExponentialHistogram {
1621                floor: 0,
1622                initial_step: 2,
1623                step_multiplier: 4,
1624                counts: vec![0, 1, 2, 3, 4, 5],
1625                indexes: None,
1626                size: 6,
1627            }
1628        );
1629    }
1630
1631    #[fuchsia::test]
1632    fn add_to_hierarchy() {
1633        let mut hierarchy = DiagnosticsHierarchy::new_root();
1634        let prop_1 = Property::String("x".to_string(), "foo".to_string());
1635        let path_1 = vec!["root", "one"];
1636        let prop_2 = Property::Uint("c".to_string(), 3);
1637        let path_2 = vec!["root", "two"];
1638        let prop_2_prime = Property::Int("z".to_string(), -4);
1639        hierarchy.add_property_at_path(&path_1, prop_1.clone());
1640        hierarchy.add_property_at_path(&path_2.clone(), prop_2.clone());
1641        hierarchy.add_property_at_path(&path_2, prop_2_prime.clone());
1642
1643        assert_eq!(
1644            hierarchy,
1645            DiagnosticsHierarchy {
1646                name: "root".to_string(),
1647                children: vec![
1648                    DiagnosticsHierarchy {
1649                        name: "one".to_string(),
1650                        properties: vec![prop_1],
1651                        children: vec![],
1652                        missing: vec![],
1653                    },
1654                    DiagnosticsHierarchy {
1655                        name: "two".to_string(),
1656                        properties: vec![prop_2, prop_2_prime],
1657                        children: vec![],
1658                        missing: vec![],
1659                    }
1660                ],
1661                properties: vec![],
1662                missing: vec![],
1663            }
1664        );
1665    }
1666
1667    #[fuchsia::test]
1668    fn string_lists() {
1669        let mut hierarchy = DiagnosticsHierarchy::new_root();
1670        let prop_1 =
1671            Property::StringList("x".to_string(), vec!["foo".to_string(), "bar".to_string()]);
1672        let path_1 = vec!["root", "one"];
1673        hierarchy.add_property_at_path(&path_1, prop_1.clone());
1674
1675        assert_eq!(
1676            hierarchy,
1677            DiagnosticsHierarchy {
1678                name: "root".to_string(),
1679                children: vec![DiagnosticsHierarchy {
1680                    name: "one".to_string(),
1681                    properties: vec![prop_1],
1682                    children: vec![],
1683                    missing: vec![],
1684                },],
1685                properties: vec![],
1686                missing: vec![],
1687            }
1688        );
1689    }
1690
1691    #[fuchsia::test]
1692    // TODO(https://fxbug.dev/42169733): delete the below
1693    #[cfg_attr(feature = "variant_asan", ignore)]
1694    #[cfg_attr(feature = "variant_hwasan", ignore)]
1695    #[should_panic]
1696    // Empty paths are meaningless on insertion and break the method invariant.
1697    fn no_empty_paths_allowed() {
1698        let mut hierarchy = DiagnosticsHierarchy::<String>::new_root();
1699        let path_1: Vec<&String> = vec![];
1700        hierarchy.get_or_add_node(&path_1);
1701    }
1702
1703    #[fuchsia::test]
1704    #[should_panic]
1705    // Paths provided to add must begin at the node we're calling
1706    // add() on.
1707    fn path_must_start_at_self() {
1708        let mut hierarchy = DiagnosticsHierarchy::<String>::new_root();
1709        let path_1 = vec!["not_root", "a"];
1710        hierarchy.get_or_add_node(&path_1);
1711    }
1712
1713    #[fuchsia::test]
1714    fn sort_hierarchy() {
1715        let mut hierarchy = DiagnosticsHierarchy::new(
1716            "root",
1717            vec![
1718                Property::String("x".to_string(), "foo".to_string()),
1719                Property::Uint("c".to_string(), 3),
1720                Property::Int("z".to_string(), -4),
1721            ],
1722            vec![
1723                DiagnosticsHierarchy::new(
1724                    "foo",
1725                    vec![
1726                        Property::Int("11".to_string(), -4),
1727                        Property::Bytes("123".to_string(), "foo".bytes().collect()),
1728                        Property::Double("0".to_string(), 8.1),
1729                    ],
1730                    vec![],
1731                ),
1732                DiagnosticsHierarchy::new("bar", vec![], vec![]),
1733            ],
1734        );
1735
1736        hierarchy.sort();
1737
1738        let sorted_hierarchy = DiagnosticsHierarchy::new(
1739            "root",
1740            vec![
1741                Property::Uint("c".to_string(), 3),
1742                Property::String("x".to_string(), "foo".to_string()),
1743                Property::Int("z".to_string(), -4),
1744            ],
1745            vec![
1746                DiagnosticsHierarchy::new("bar", vec![], vec![]),
1747                DiagnosticsHierarchy::new(
1748                    "foo",
1749                    vec![
1750                        Property::Double("0".to_string(), 8.1),
1751                        Property::Int("11".to_string(), -4),
1752                        Property::Bytes("123".to_string(), "foo".bytes().collect()),
1753                    ],
1754                    vec![],
1755                ),
1756            ],
1757        );
1758        assert_eq!(sorted_hierarchy, hierarchy);
1759    }
1760
1761    fn parse_selectors_and_filter_hierarchy(
1762        hierarchy: DiagnosticsHierarchy,
1763        test_selectors: Vec<&str>,
1764    ) -> Option<DiagnosticsHierarchy> {
1765        let parsed_test_selectors = test_selectors
1766            .into_iter()
1767            .map(|selector_string| {
1768                Arc::new(
1769                    selectors::parse_selector::<VerboseError>(selector_string)
1770                        .expect("All test selectors are valid and parsable."),
1771                )
1772            })
1773            .collect::<Vec<Arc<Selector>>>();
1774
1775        let hierarchy_matcher: HierarchyMatcher = parsed_test_selectors.try_into().unwrap();
1776
1777        filter_hierarchy(hierarchy, &hierarchy_matcher).map(|mut hierarchy| {
1778            hierarchy.sort();
1779            hierarchy
1780        })
1781    }
1782
1783    fn get_test_hierarchy() -> DiagnosticsHierarchy {
1784        DiagnosticsHierarchy::new(
1785            "root",
1786            vec![
1787                Property::String("x".to_string(), "foo".to_string()),
1788                Property::Uint("c".to_string(), 3),
1789                Property::Int("z".to_string(), -4),
1790            ],
1791            vec![
1792                make_foo(),
1793                DiagnosticsHierarchy::new(
1794                    "bar",
1795                    vec![Property::Int("12".to_string(), -4)],
1796                    vec![DiagnosticsHierarchy::new(
1797                        "zed",
1798                        vec![Property::Int("13/:".to_string(), -4)],
1799                        vec![],
1800                    )],
1801                ),
1802            ],
1803        )
1804    }
1805
1806    fn make_all_foo_props() -> Vec<Property> {
1807        vec![
1808            Property::Int("11".to_string(), -4),
1809            Property::Bytes("123".to_string(), b"foo".to_vec()),
1810            Property::Double("0".to_string(), 8.1),
1811        ]
1812    }
1813
1814    fn make_zed() -> Vec<DiagnosticsHierarchy> {
1815        vec![DiagnosticsHierarchy::new("zed", vec![Property::Int("13".to_string(), -4)], vec![])]
1816    }
1817
1818    fn make_foo() -> DiagnosticsHierarchy {
1819        DiagnosticsHierarchy::new("foo", make_all_foo_props(), make_zed())
1820    }
1821
1822    #[fuchsia::test]
1823    fn test_filter_hierarchy() {
1824        let test_selectors = vec!["*:root/foo:11", "*:root:z", r#"*:root/bar/zed:13\/\:"#];
1825
1826        assert_eq!(
1827            parse_selectors_and_filter_hierarchy(get_test_hierarchy(), test_selectors),
1828            Some(DiagnosticsHierarchy::new(
1829                "root",
1830                vec![Property::Int("z".to_string(), -4),],
1831                vec![
1832                    DiagnosticsHierarchy::new(
1833                        "bar",
1834                        vec![],
1835                        vec![DiagnosticsHierarchy::new(
1836                            "zed",
1837                            vec![Property::Int("13/:".to_string(), -4)],
1838                            vec![],
1839                        )],
1840                    ),
1841                    DiagnosticsHierarchy::new(
1842                        "foo",
1843                        vec![Property::Int("11".to_string(), -4),],
1844                        vec![],
1845                    )
1846                ],
1847            ))
1848        );
1849
1850        let test_selectors = vec!["*:root"];
1851        let mut sorted_expected = get_test_hierarchy();
1852        sorted_expected.sort();
1853        assert_eq!(
1854            parse_selectors_and_filter_hierarchy(get_test_hierarchy(), test_selectors),
1855            Some(sorted_expected)
1856        );
1857    }
1858
1859    #[fuchsia::test]
1860    fn test_filter_does_not_include_empty_node() {
1861        let test_selectors = vec!["*:root/foo:blorg"];
1862
1863        assert_eq!(
1864            parse_selectors_and_filter_hierarchy(get_test_hierarchy(), test_selectors),
1865            None,
1866        );
1867    }
1868
1869    #[fuchsia::test]
1870    fn test_filter_empty_hierarchy() {
1871        let test_selectors = vec!["*:root"];
1872
1873        assert_eq!(
1874            parse_selectors_and_filter_hierarchy(
1875                DiagnosticsHierarchy::new("root", vec![], vec![]),
1876                test_selectors
1877            ),
1878            Some(DiagnosticsHierarchy::new("root", vec![], vec![])),
1879        );
1880    }
1881
1882    #[fuchsia::test]
1883    fn test_full_filtering() {
1884        // If we select a non-existent root, then we return a fully filtered hierarchy.
1885        let test_selectors = vec!["*:non-existent-root"];
1886        assert_eq!(
1887            parse_selectors_and_filter_hierarchy(get_test_hierarchy(), test_selectors),
1888            None,
1889        );
1890
1891        // If we select a non-existent child of the root, then we return a fully filtered hierarchy.
1892        let test_selectors = vec!["*:root/i-dont-exist:foo"];
1893        assert_eq!(
1894            parse_selectors_and_filter_hierarchy(get_test_hierarchy(), test_selectors),
1895            None,
1896        );
1897
1898        // Even if the root exists, but we don't include any property, we consider the hierarchy
1899        // fully filtered. This is aligned with the previous case.
1900        let test_selectors = vec!["*:root:i-dont-exist"];
1901        assert_eq!(
1902            parse_selectors_and_filter_hierarchy(get_test_hierarchy(), test_selectors),
1903            None,
1904        );
1905    }
1906
1907    #[fuchsia::test]
1908    fn test_subtree_selection_includes_empty_nodes() {
1909        let test_selectors = vec!["*:root"];
1910        let mut empty_hierarchy = DiagnosticsHierarchy::new(
1911            "root",
1912            vec![],
1913            vec![
1914                DiagnosticsHierarchy::new(
1915                    "foo",
1916                    vec![],
1917                    vec![DiagnosticsHierarchy::new("zed", vec![], vec![])],
1918                ),
1919                DiagnosticsHierarchy::new(
1920                    "bar",
1921                    vec![],
1922                    vec![DiagnosticsHierarchy::new("zed", vec![], vec![])],
1923                ),
1924            ],
1925        );
1926
1927        empty_hierarchy.sort();
1928
1929        assert_eq!(
1930            parse_selectors_and_filter_hierarchy(empty_hierarchy.clone(), test_selectors),
1931            Some(empty_hierarchy)
1932        );
1933    }
1934
1935    #[fuchsia::test]
1936    fn test_empty_tree_filtering() {
1937        // Subtree selection on the empty tree should produce the empty tree.
1938        let mut empty_hierarchy = DiagnosticsHierarchy::new("root", vec![], vec![]);
1939        empty_hierarchy.sort();
1940
1941        let subtree_selector = vec!["*:root"];
1942        assert_eq!(
1943            parse_selectors_and_filter_hierarchy(empty_hierarchy.clone(), subtree_selector),
1944            Some(empty_hierarchy.clone())
1945        );
1946
1947        // Selecting a property on the root, even if it doesn't exist, should produce nothing.
1948        let fake_property_selector = vec!["*:root:blorp"];
1949        assert_eq!(
1950            parse_selectors_and_filter_hierarchy(empty_hierarchy.clone(), fake_property_selector),
1951            None,
1952        );
1953    }
1954
1955    #[test_case(vec![Property::Int("11".to_string(), -4)], "root/foo:11" ; "specific_property")]
1956    #[test_case(make_all_foo_props(), "root/foo:*" ; "many_properties")]
1957    #[test_case(vec![], "root/foo:none" ; "property_not_there")]
1958    #[fuchsia::test]
1959    fn test_select_from_hierarchy_property_selectors(expected: Vec<Property>, tree_selector: &str) {
1960        let hierarchy = get_test_hierarchy();
1961        let parsed_selector =
1962            selectors::parse_selector::<VerboseError>(&format!("*:{tree_selector}"))
1963                .expect("All test selectors are valid and parsable.");
1964        let Ok(SelectResult::Properties(mut property_entry_vec)) =
1965            select_from_hierarchy(&hierarchy, &parsed_selector)
1966        else {
1967            panic!("must be properties");
1968        };
1969
1970        property_entry_vec.sort_by(|p1, p2| p1.name().cmp(p2.name()));
1971        let mut expected = expected.iter().map(Borrow::borrow).collect::<Vec<_>>();
1972        expected.sort_by(|p1, p2| p1.name().cmp(p2.name()));
1973
1974        assert_eq!(property_entry_vec, expected);
1975    }
1976
1977    #[test_case(vec![], "root/none" ; "node_not_there")]
1978    #[test_case(make_zed(), "root/foo/zed" ; "properties_only")]
1979    #[test_case(vec![make_foo()], "root/foo" ; "nodes_and_properties")]
1980    #[test_case(vec![get_test_hierarchy()], "root" ; "select_root")]
1981    #[fuchsia::test]
1982    fn test_select_from_hierarchy_tree_selectors(
1983        expected: Vec<DiagnosticsHierarchy>,
1984        tree_selector: &str,
1985    ) {
1986        let hierarchy = get_test_hierarchy();
1987        let parsed_selector =
1988            selectors::parse_selector::<VerboseError>(&format!("*:{tree_selector}"))
1989                .expect("All test selectors are valid and parsable.");
1990        let Ok(SelectResult::Nodes(node_vec)) = select_from_hierarchy(&hierarchy, &parsed_selector)
1991        else {
1992            panic!("must be nodes");
1993        };
1994
1995        let expected = expected.iter().map(Borrow::borrow).collect::<Vec<_>>();
1996
1997        assert_eq!(node_vec, expected);
1998    }
1999
2000    #[fuchsia::test]
2001    fn sort_numerical_value() {
2002        let mut diagnostics_hierarchy = DiagnosticsHierarchy::new(
2003            "root",
2004            vec![
2005                Property::Double("2".to_string(), 2.3),
2006                Property::Int("0".to_string(), -4),
2007                Property::Uint("10".to_string(), 3),
2008                Property::String("1".to_string(), "test".to_string()),
2009            ],
2010            vec![
2011                DiagnosticsHierarchy::new("123", vec![], vec![]),
2012                DiagnosticsHierarchy::new("34", vec![], vec![]),
2013                DiagnosticsHierarchy::new("4", vec![], vec![]),
2014                DiagnosticsHierarchy::new("023", vec![], vec![]),
2015                DiagnosticsHierarchy::new("12", vec![], vec![]),
2016                DiagnosticsHierarchy::new("1", vec![], vec![]),
2017            ],
2018        );
2019        diagnostics_hierarchy.sort();
2020        assert_eq!(
2021            diagnostics_hierarchy,
2022            DiagnosticsHierarchy::new(
2023                "root",
2024                vec![
2025                    Property::Int("0".to_string(), -4),
2026                    Property::String("1".to_string(), "test".to_string()),
2027                    Property::Double("2".to_string(), 2.3),
2028                    Property::Uint("10".to_string(), 3),
2029                ],
2030                vec![
2031                    DiagnosticsHierarchy::new("1", vec![], vec![]),
2032                    DiagnosticsHierarchy::new("4", vec![], vec![]),
2033                    DiagnosticsHierarchy::new("12", vec![], vec![]),
2034                    DiagnosticsHierarchy::new("023", vec![], vec![]),
2035                    DiagnosticsHierarchy::new("34", vec![], vec![]),
2036                    DiagnosticsHierarchy::new("123", vec![], vec![]),
2037                ]
2038            )
2039        );
2040    }
2041
2042    #[fuchsia::test]
2043    fn filter_hierarchy_doesnt_return_partial_matches() {
2044        let hierarchy = DiagnosticsHierarchy::new(
2045            "root",
2046            vec![],
2047            vec![DiagnosticsHierarchy::new("session_started_at", vec![], vec![])],
2048        );
2049        let test_selectors = vec!["*:root/session_started_at/0"];
2050        assert_eq!(parse_selectors_and_filter_hierarchy(hierarchy, test_selectors), None);
2051    }
2052
2053    #[fuchsia::test]
2054    fn test_filter_tree() {
2055        let test_selectors = vec!["root/foo:11", "root:z", r#"root/bar/zed:13\/\:"#];
2056        let parsed_test_selectors = test_selectors
2057            .into_iter()
2058            .map(|s| {
2059                selectors::parse_tree_selector::<VerboseError>(s)
2060                    .expect("All test selectors are valid and parsable.")
2061            })
2062            .collect::<Vec<_>>();
2063
2064        let result =
2065            filter_tree(get_test_hierarchy(), &parsed_test_selectors).map(|mut hierarchy| {
2066                hierarchy.sort();
2067                hierarchy
2068            });
2069        assert_eq!(
2070            result,
2071            Some(DiagnosticsHierarchy::new(
2072                "root",
2073                vec![Property::Int("z".to_string(), -4),],
2074                vec![
2075                    DiagnosticsHierarchy::new(
2076                        "bar",
2077                        vec![],
2078                        vec![DiagnosticsHierarchy::new(
2079                            "zed",
2080                            vec![Property::Int("13/:".to_string(), -4)],
2081                            vec![],
2082                        )],
2083                    ),
2084                    DiagnosticsHierarchy::new(
2085                        "foo",
2086                        vec![Property::Int("11".to_string(), -4),],
2087                        vec![],
2088                    )
2089                ],
2090            ))
2091        );
2092    }
2093
2094    #[fuchsia::test]
2095    fn test_matcher_from_iterator() {
2096        let matcher = HierarchyMatcher::new(
2097            ["*:root/foo:11", "*:root:z", r#"*:root/bar/zed:13\/\:"#].into_iter().map(|s| {
2098                selectors::parse_selector::<VerboseError>(s)
2099                    .expect("All test selectors are valid and parsable.")
2100            }),
2101        )
2102        .expect("create matcher from iterator of selectors");
2103        let result = filter_hierarchy(get_test_hierarchy(), &matcher).map(|mut hierarchy| {
2104            hierarchy.sort();
2105            hierarchy
2106        });
2107        assert_eq!(
2108            result,
2109            Some(DiagnosticsHierarchy::new(
2110                "root",
2111                vec![Property::Int("z".to_string(), -4),],
2112                vec![
2113                    DiagnosticsHierarchy::new(
2114                        "bar",
2115                        vec![],
2116                        vec![DiagnosticsHierarchy::new(
2117                            "zed",
2118                            vec![Property::Int("13/:".to_string(), -4)],
2119                            vec![],
2120                        )],
2121                    ),
2122                    DiagnosticsHierarchy::new(
2123                        "foo",
2124                        vec![Property::Int("11".to_string(), -4),],
2125                        vec![],
2126                    )
2127                ],
2128            ))
2129        );
2130    }
2131}