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