Skip to main content

file_identify/
tags.rs

1//! Tags, tag sets and identify's tag-group constants.
2//!
3//! A [`Tag`] is one of the [`TAG_COUNT`] names in
4//! [`ALL_TAGS`]; a [`TagSet`] is a `Copy` bitset over them. Neither allocates,
5//! and every set operation is a handful of word operations — cheap enough to
6//! evaluate pre-commit's `types` / `types_or` / `exclude_types` filters for
7//! every file of a large repository.
8//!
9//! ```
10//! use file_identify::{Tag, TagSet};
11//!
12//! let tags: TagSet = "file, non-executable, python, text".parse()?;
13//! assert!(tags.contains(Tag::TEXT));
14//! assert!(tags.contains("python"));
15//!
16//! let types = TagSet::from_names(["python"])?;
17//! let exclude = TagSet::from_names(["binary"])?;
18//! assert!(tags.matches_types(&types, &TagSet::EMPTY, &exclude));
19//!
20//! // Iteration (and `Display`) follow tag-name order.
21//! assert_eq!(tags.to_string(), "file, non-executable, python, text");
22//! # Ok::<(), file_identify::UnknownTagError>(())
23//! ```
24
25use core::fmt;
26use core::iter::FusedIterator;
27use core::ops::{
28    BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Not, Sub, SubAssign,
29};
30use core::str::FromStr;
31
32use crate::generated::{TAG_COUNT, TAG_INDEX, WORDS};
33
34pub use crate::generated::ALL_TAGS;
35pub use crate::meta::FileKind;
36
37/// Name of the `directory` tag.
38pub const DIRECTORY: &str = "directory";
39/// Name of the `symlink` tag.
40pub const SYMLINK: &str = "symlink";
41/// Name of the `socket` tag.
42pub const SOCKET: &str = "socket";
43/// Name of the `file` tag.
44pub const FILE: &str = "file";
45/// Name of the `executable` tag.
46pub const EXECUTABLE: &str = "executable";
47/// Name of the `non-executable` tag.
48pub const NON_EXECUTABLE: &str = "non-executable";
49/// Name of the `text` tag.
50pub const TEXT: &str = "text";
51/// Name of the `binary` tag.
52pub const BINARY: &str = "binary";
53
54/// `identify.TYPE_TAGS`: `directory`, `file`, `symlink`, `socket`.
55pub const TYPE_TAGS: TagSet = TagSet::EMPTY
56    .with(Tag::DIRECTORY)
57    .with(Tag::FILE)
58    .with(Tag::SYMLINK)
59    .with(Tag::SOCKET);
60
61/// `identify.MODE_TAGS`: `executable`, `non-executable`.
62pub const MODE_TAGS: TagSet = TagSet::EMPTY
63    .with(Tag::EXECUTABLE)
64    .with(Tag::NON_EXECUTABLE);
65
66/// `identify.ENCODING_TAGS`: `binary`, `text`.
67pub const ENCODING_TAGS: TagSet = TagSet::EMPTY.with(Tag::BINARY).with(Tag::TEXT);
68
69/// Whether `tag` is one of [`TYPE_TAGS`].
70#[must_use]
71pub fn is_type_tag(tag: &str) -> bool {
72    matches!(tag, DIRECTORY | FILE | SYMLINK | SOCKET)
73}
74
75/// Whether `tag` is one of [`MODE_TAGS`].
76#[must_use]
77pub fn is_mode_tag(tag: &str) -> bool {
78    matches!(tag, EXECUTABLE | NON_EXECUTABLE)
79}
80
81/// Whether `tag` is one of [`ENCODING_TAGS`].
82#[must_use]
83pub fn is_encoding_tag(tag: &str) -> bool {
84    matches!(tag, BINARY | TEXT)
85}
86
87/// One identify tag, such as `python`, `text` or `executable`.
88///
89/// A `Tag` is a 2-byte handle: its [`id`](Tag::id) is the tag's position in
90/// the sorted [`ALL_TAGS`] array, so comparing tags compares their names.
91/// Only the eight file-system tags have named constants ([`Tag::FILE`],
92/// [`Tag::TEXT`], …); look any other tag up by name:
93///
94/// ```
95/// use file_identify::Tag;
96///
97/// let python: Tag = "python".parse()?;
98/// assert_eq!(python.as_str(), "python");
99/// assert_eq!(Tag::from_name("python"), Some(python));
100/// assert_eq!(Tag::from_name("pythn"), None);
101/// assert!(Tag::FILE < Tag::TEXT); // name order
102/// # Ok::<(), file_identify::UnknownTagError>(())
103/// ```
104#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
105pub struct Tag(u16);
106
107impl Tag {
108    /// Construct from a generated id. Only used by `generated.rs`, whose ids
109    /// are `< TAG_COUNT` by construction.
110    pub(crate) const fn from_id_const(id: u16) -> Self {
111        Self(id)
112    }
113
114    /// The tag with the given [`id`](Tag::id), if `id < TAG_COUNT`.
115    #[must_use]
116    pub fn from_id(id: usize) -> Option<Self> {
117        if id < TAG_COUNT {
118            u16::try_from(id).ok().map(Self)
119        } else {
120            None
121        }
122    }
123
124    /// Look a tag up by its exact (case-sensitive) name.
125    ///
126    /// This is a hash lookup with no allocation.
127    #[must_use]
128    pub fn from_name(name: &str) -> Option<Self> {
129        TAG_INDEX
130            .find(name.as_bytes(), |i| ALL_TAGS.get(i).copied())
131            .and_then(Self::from_id)
132    }
133
134    /// The tag's position in [`ALL_TAGS`] (`0..TAG_COUNT`).
135    #[must_use]
136    pub const fn id(self) -> usize {
137        self.0 as usize
138    }
139
140    /// The tag's name, e.g. `"python"`.
141    #[must_use]
142    pub fn as_str(self) -> &'static str {
143        ALL_TAGS.get(self.id()).copied().unwrap_or_default()
144    }
145
146    /// Whether this is one of [`TYPE_TAGS`].
147    #[must_use]
148    pub const fn is_type_tag(self) -> bool {
149        TYPE_TAGS.contains_tag(self)
150    }
151
152    /// Whether this is one of [`MODE_TAGS`].
153    #[must_use]
154    pub const fn is_mode_tag(self) -> bool {
155        MODE_TAGS.contains_tag(self)
156    }
157
158    /// Whether this is one of [`ENCODING_TAGS`].
159    #[must_use]
160    pub const fn is_encoding_tag(self) -> bool {
161        ENCODING_TAGS.contains_tag(self)
162    }
163
164    /// Iterate over every known tag in name order.
165    #[must_use]
166    pub const fn all() -> Iter {
167        TagSet::ALL.iter()
168    }
169
170    /// Word index and bit mask of this tag inside a [`TagSet`].
171    const fn bit(self) -> (usize, u64) {
172        ((self.0 / 64) as usize, 1u64 << (self.0 % 64))
173    }
174}
175
176impl fmt::Debug for Tag {
177    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
178        f.debug_tuple("Tag").field(&self.as_str()).finish()
179    }
180}
181
182impl fmt::Display for Tag {
183    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
184        f.write_str(self.as_str())
185    }
186}
187
188impl AsRef<str> for Tag {
189    fn as_ref(&self) -> &str {
190        self.as_str()
191    }
192}
193
194impl FromStr for Tag {
195    type Err = UnknownTagError;
196
197    fn from_str(s: &str) -> Result<Self, Self::Err> {
198        Self::from_name(s).ok_or_else(|| UnknownTagError::new(vec![s.to_owned()]))
199    }
200}
201
202impl TryFrom<&str> for Tag {
203    type Error = UnknownTagError;
204
205    fn try_from(s: &str) -> Result<Self, Self::Error> {
206        s.parse()
207    }
208}
209
210impl PartialEq<str> for Tag {
211    fn eq(&self, other: &str) -> bool {
212        self.as_str() == other
213    }
214}
215
216impl PartialEq<&str> for Tag {
217    fn eq(&self, other: &&str) -> bool {
218        self.as_str() == *other
219    }
220}
221
222impl PartialEq<Tag> for str {
223    fn eq(&self, other: &Tag) -> bool {
224        self == other.as_str()
225    }
226}
227
228impl PartialEq<Tag> for &str {
229    fn eq(&self, other: &Tag) -> bool {
230        *self == other.as_str()
231    }
232}
233
234/// Error returned when parsing names that are not in [`ALL_TAGS`].
235///
236/// The `Display` text is `unknown tag "x"` (or `unknown tags "x", "y"`);
237/// callers that need identify/pre-commit's exact wording should build it from
238/// [`names`](UnknownTagError::names).
239#[derive(Clone, Debug, PartialEq, Eq)]
240pub struct UnknownTagError {
241    names: Vec<String>,
242}
243
244impl UnknownTagError {
245    fn new(names: Vec<String>) -> Self {
246        Self { names }
247    }
248
249    /// The unrecognized names, in input order (never empty).
250    #[must_use]
251    pub fn names(&self) -> &[String] {
252        &self.names
253    }
254}
255
256impl fmt::Display for UnknownTagError {
257    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
258        f.write_str(if self.names.len() == 1 {
259            "unknown tag "
260        } else {
261            "unknown tags "
262        })?;
263        for (i, name) in self.names.iter().enumerate() {
264            if i > 0 {
265                f.write_str(", ")?;
266            }
267            write!(f, "{name:?}")?;
268        }
269        Ok(())
270    }
271}
272
273impl std::error::Error for UnknownTagError {}
274
275mod sealed {
276    pub trait Sealed {}
277    impl Sealed for super::Tag {}
278    impl Sealed for &super::Tag {}
279    impl Sealed for &str {}
280    impl Sealed for String {}
281    impl Sealed for &String {}
282}
283
284/// A [`Tag`] or a tag name; accepted by [`TagSet::contains`].
285///
286/// This trait is sealed. Looking up a name costs one hash lookup; unknown
287/// names are never contained in any set.
288pub trait IntoTag: sealed::Sealed {
289    /// The tag this value denotes, if any.
290    fn into_tag(self) -> Option<Tag>;
291}
292
293impl IntoTag for Tag {
294    fn into_tag(self) -> Option<Tag> {
295        Some(self)
296    }
297}
298
299impl IntoTag for &Tag {
300    fn into_tag(self) -> Option<Tag> {
301        Some(*self)
302    }
303}
304
305impl IntoTag for &str {
306    fn into_tag(self) -> Option<Tag> {
307        Tag::from_name(self)
308    }
309}
310
311impl IntoTag for String {
312    fn into_tag(self) -> Option<Tag> {
313        Tag::from_name(&self)
314    }
315}
316
317impl IntoTag for &String {
318    fn into_tag(self) -> Option<Tag> {
319        Tag::from_name(self)
320    }
321}
322
323/// A set of [`Tag`]s: a `Copy` bitset with one bit per known tag.
324///
325/// All operations are allocation-free; the binary operators `|`, `&`, `-`,
326/// `^` and `!` (complement relative to all known tags) are available as well
327/// as the named methods. Iteration, [`Debug`](fmt::Debug) and
328/// [`Display`](fmt::Display) list tags in name order.
329#[derive(Clone, Copy, PartialEq, Eq, Hash, Default)]
330pub struct TagSet {
331    words: [u64; WORDS],
332}
333
334// All indexing below is `words[i]` with `i < WORDS`, guarded by the loop
335// condition or an explicit check, so it cannot panic. Const fns cannot use
336// iterators, hence the manual loops.
337#[allow(clippy::indexing_slicing)]
338impl TagSet {
339    /// The empty set.
340    pub const EMPTY: Self = Self { words: [0; WORDS] };
341
342    /// Every known tag (`identify.ALL_TAGS`).
343    pub const ALL: Self = {
344        let mut words = [0u64; WORDS];
345        let mut i = 0;
346        while i < WORDS {
347            let start = i * 64;
348            words[i] = if TAG_COUNT >= start + 64 {
349                u64::MAX
350            } else if TAG_COUNT > start {
351                (1u64 << (TAG_COUNT - start)) - 1
352            } else {
353                0
354            };
355            i += 1;
356        }
357        Self { words }
358    };
359
360    /// The empty set (same as [`TagSet::EMPTY`]).
361    #[must_use]
362    pub const fn new() -> Self {
363        Self::EMPTY
364    }
365
366    /// Build a set from tag ids; ids `>= TAG_COUNT` are ignored. Used by the
367    /// generated tables.
368    pub(crate) const fn from_ids(ids: &[u16]) -> Self {
369        let mut set = Self::EMPTY;
370        let mut i = 0;
371        while i < ids.len() {
372            if (ids[i] as usize) < TAG_COUNT {
373                set = set.with(Tag(ids[i]));
374            }
375            i += 1;
376        }
377        set
378    }
379
380    /// The set containing only `tag`.
381    #[must_use]
382    pub const fn from_tag(tag: Tag) -> Self {
383        Self::EMPTY.with(tag)
384    }
385
386    /// Build a set from tag names, failing with every unknown name.
387    ///
388    /// # Errors
389    ///
390    /// Returns [`UnknownTagError`] listing all names not in [`ALL_TAGS`].
391    pub fn from_names<I, S>(names: I) -> Result<Self, UnknownTagError>
392    where
393        I: IntoIterator<Item = S>,
394        S: AsRef<str>,
395    {
396        let mut set = Self::EMPTY;
397        let mut unknown = Vec::new();
398        for name in names {
399            let name = name.as_ref();
400            match Tag::from_name(name) {
401                Some(tag) => {
402                    set.insert(tag);
403                }
404                None => unknown.push(name.to_owned()),
405            }
406        }
407        if unknown.is_empty() {
408            Ok(set)
409        } else {
410            Err(UnknownTagError::new(unknown))
411        }
412    }
413
414    /// This set plus `tag`.
415    #[must_use]
416    pub const fn with(self, tag: Tag) -> Self {
417        let (w, bit) = tag.bit();
418        let mut words = self.words;
419        if w < WORDS {
420            words[w] |= bit;
421        }
422        Self { words }
423    }
424
425    /// This set minus `tag`.
426    #[must_use]
427    pub const fn without(self, tag: Tag) -> Self {
428        let (w, bit) = tag.bit();
429        let mut words = self.words;
430        if w < WORDS {
431            words[w] &= !bit;
432        }
433        Self { words }
434    }
435
436    /// Whether `tag` is in the set (`const` version of
437    /// [`contains`](TagSet::contains) for [`Tag`] values).
438    #[must_use]
439    pub const fn contains_tag(&self, tag: Tag) -> bool {
440        let (w, bit) = tag.bit();
441        w < WORDS && self.words[w] & bit != 0
442    }
443
444    /// Whether the set contains `tag`, given as a [`Tag`] or a tag name.
445    ///
446    /// ```
447    /// use file_identify::{Tag, tags_from_filename};
448    ///
449    /// let tags = tags_from_filename("setup.py");
450    /// assert!(tags.contains("python"));
451    /// assert!(tags.contains(Tag::TEXT));
452    /// assert!(!tags.contains("no-such-tag"));
453    /// ```
454    #[must_use]
455    pub fn contains(&self, tag: impl IntoTag) -> bool {
456        tag.into_tag().is_some_and(|t| self.contains_tag(t))
457    }
458
459    /// Add `tag`; returns whether it was newly inserted.
460    pub fn insert(&mut self, tag: Tag) -> bool {
461        let was = self.contains_tag(tag);
462        *self = self.with(tag);
463        !was
464    }
465
466    /// Remove `tag`; returns whether it was present.
467    pub fn remove(&mut self, tag: Tag) -> bool {
468        let was = self.contains_tag(tag);
469        *self = self.without(tag);
470        was
471    }
472
473    /// Remove every tag.
474    pub fn clear(&mut self) {
475        *self = Self::EMPTY;
476    }
477
478    /// Number of tags in the set.
479    #[must_use]
480    pub const fn len(&self) -> usize {
481        let mut n = 0;
482        let mut i = 0;
483        while i < WORDS {
484            n += self.words[i].count_ones() as usize;
485            i += 1;
486        }
487        n
488    }
489
490    /// Whether the set is empty.
491    #[must_use]
492    pub const fn is_empty(&self) -> bool {
493        let mut i = 0;
494        while i < WORDS {
495            if self.words[i] != 0 {
496                return false;
497            }
498            i += 1;
499        }
500        true
501    }
502
503    /// `self ∪ other`.
504    #[must_use]
505    pub const fn union(self, other: Self) -> Self {
506        let mut words = self.words;
507        let mut i = 0;
508        while i < WORDS {
509            words[i] |= other.words[i];
510            i += 1;
511        }
512        Self { words }
513    }
514
515    /// `self ∩ other`.
516    #[must_use]
517    pub const fn intersection(self, other: Self) -> Self {
518        let mut words = self.words;
519        let mut i = 0;
520        while i < WORDS {
521            words[i] &= other.words[i];
522            i += 1;
523        }
524        Self { words }
525    }
526
527    /// `self \ other`.
528    #[must_use]
529    pub const fn difference(self, other: Self) -> Self {
530        let mut words = self.words;
531        let mut i = 0;
532        while i < WORDS {
533            words[i] &= !other.words[i];
534            i += 1;
535        }
536        Self { words }
537    }
538
539    /// Tags in exactly one of `self` and `other`.
540    #[must_use]
541    pub const fn symmetric_difference(self, other: Self) -> Self {
542        let mut words = self.words;
543        let mut i = 0;
544        while i < WORDS {
545            words[i] ^= other.words[i];
546            i += 1;
547        }
548        Self { words }
549    }
550
551    /// Every known tag that is not in `self`.
552    #[must_use]
553    pub const fn complement(self) -> Self {
554        Self::ALL.difference(self)
555    }
556
557    /// Whether every tag of `self` is in `other`.
558    #[must_use]
559    pub const fn is_subset(&self, other: &Self) -> bool {
560        let mut i = 0;
561        while i < WORDS {
562            if self.words[i] & !other.words[i] != 0 {
563                return false;
564            }
565            i += 1;
566        }
567        true
568    }
569
570    /// Whether every tag of `other` is in `self` (Python's `self >= other`).
571    #[must_use]
572    pub const fn is_superset(&self, other: &Self) -> bool {
573        other.is_subset(self)
574    }
575
576    /// Whether `self` and `other` share no tag.
577    #[must_use]
578    pub const fn is_disjoint(&self, other: &Self) -> bool {
579        !self.intersects(other)
580    }
581
582    /// Whether `self` and `other` share at least one tag.
583    #[must_use]
584    pub const fn intersects(&self, other: &Self) -> bool {
585        let mut i = 0;
586        while i < WORDS {
587            if self.words[i] & other.words[i] != 0 {
588                return true;
589            }
590            i += 1;
591        }
592        false
593    }
594
595    /// pre-commit's file-type filter (`Classifier.by_types`) applied to the
596    /// tags of one file:
597    ///
598    /// `self ⊇ types && (types_or = ∅ || self ∩ types_or ≠ ∅) && self ∩ exclude_types = ∅`
599    ///
600    /// ```
601    /// use file_identify::TagSet;
602    ///
603    /// let file: TagSet = "file, non-executable, python, text".parse()?;
604    /// let none = TagSet::EMPTY;
605    /// let types: TagSet = "file".parse()?;
606    /// let types_or: TagSet = "python, pyi".parse()?;
607    /// let exclude: TagSet = "binary".parse()?;
608    /// assert!(file.matches_types(&types, &types_or, &exclude));
609    /// assert!(!file.matches_types(&types, &none, &"python".parse()?));
610    /// # Ok::<(), file_identify::UnknownTagError>(())
611    /// ```
612    #[must_use]
613    pub const fn matches_types(&self, types: &Self, types_or: &Self, exclude_types: &Self) -> bool {
614        self.is_superset(types)
615            && (types_or.is_empty() || self.intersects(types_or))
616            && self.is_disjoint(exclude_types)
617    }
618
619    /// Whether the set contains `text` or `binary` (identify's invariant for
620    /// a classified regular file).
621    #[must_use]
622    pub const fn has_encoding(&self) -> bool {
623        self.intersects(&ENCODING_TAGS)
624    }
625
626    /// Iterate over the tags in name order.
627    #[must_use]
628    pub const fn iter(&self) -> Iter {
629        Iter {
630            words: self.words,
631            front: 0,
632            back: WORDS,
633        }
634    }
635
636    /// Iterate over the tag names in sorted order.
637    #[must_use = "iterators are lazy and do nothing unless consumed"]
638    pub fn names(&self) -> impl DoubleEndedIterator<Item = &'static str> + ExactSizeIterator {
639        self.iter().map(Tag::as_str)
640    }
641
642    /// The first tag in name order.
643    #[must_use]
644    pub fn first(&self) -> Option<Tag> {
645        self.iter().next()
646    }
647
648    /// The last tag in name order.
649    #[must_use]
650    pub fn last(&self) -> Option<Tag> {
651        self.iter().next_back()
652    }
653}
654
655impl fmt::Debug for TagSet {
656    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
657        f.debug_set().entries(self.names()).finish()
658    }
659}
660
661/// Tag names in name order separated by `", "`, e.g.
662/// `file, non-executable, python, text` (the empty set prints nothing).
663/// [`FromStr`] accepts the same format.
664impl fmt::Display for TagSet {
665    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
666        for (i, name) in self.names().enumerate() {
667            if i > 0 {
668                f.write_str(", ")?;
669            }
670            f.write_str(name)?;
671        }
672        Ok(())
673    }
674}
675
676/// Parse comma-separated tag names (surrounding whitespace is ignored, empty
677/// items are skipped), the format produced by [`Display`](fmt::Display).
678impl FromStr for TagSet {
679    type Err = UnknownTagError;
680
681    fn from_str(s: &str) -> Result<Self, Self::Err> {
682        Self::from_names(s.split(',').map(str::trim).filter(|n| !n.is_empty()))
683    }
684}
685
686impl TryFrom<&[&str]> for TagSet {
687    type Error = UnknownTagError;
688
689    fn try_from(names: &[&str]) -> Result<Self, Self::Error> {
690        Self::from_names(names)
691    }
692}
693
694impl From<Tag> for TagSet {
695    fn from(tag: Tag) -> Self {
696        Self::from_tag(tag)
697    }
698}
699
700impl<const N: usize> From<[Tag; N]> for TagSet {
701    fn from(tags: [Tag; N]) -> Self {
702        tags.into_iter().collect()
703    }
704}
705
706impl FromIterator<Tag> for TagSet {
707    fn from_iter<I: IntoIterator<Item = Tag>>(iter: I) -> Self {
708        let mut set = Self::EMPTY;
709        set.extend(iter);
710        set
711    }
712}
713
714impl Extend<Tag> for TagSet {
715    fn extend<I: IntoIterator<Item = Tag>>(&mut self, iter: I) {
716        for tag in iter {
717            self.insert(tag);
718        }
719    }
720}
721
722impl IntoIterator for TagSet {
723    type Item = Tag;
724    type IntoIter = Iter;
725
726    fn into_iter(self) -> Iter {
727        self.iter()
728    }
729}
730
731impl IntoIterator for &TagSet {
732    type Item = Tag;
733    type IntoIter = Iter;
734
735    fn into_iter(self) -> Iter {
736        self.iter()
737    }
738}
739
740macro_rules! set_op {
741    ($trait:ident, $method:ident, $assign_trait:ident, $assign_method:ident, $op:ident) => {
742        impl $trait for TagSet {
743            type Output = TagSet;
744
745            fn $method(self, rhs: TagSet) -> TagSet {
746                self.$op(rhs)
747            }
748        }
749
750        impl $trait<Tag> for TagSet {
751            type Output = TagSet;
752
753            fn $method(self, rhs: Tag) -> TagSet {
754                self.$op(TagSet::from_tag(rhs))
755            }
756        }
757
758        impl $assign_trait for TagSet {
759            fn $assign_method(&mut self, rhs: TagSet) {
760                *self = self.$op(rhs);
761            }
762        }
763
764        impl $assign_trait<Tag> for TagSet {
765            fn $assign_method(&mut self, rhs: Tag) {
766                *self = self.$op(TagSet::from_tag(rhs));
767            }
768        }
769    };
770}
771
772set_op!(BitOr, bitor, BitOrAssign, bitor_assign, union);
773set_op!(BitAnd, bitand, BitAndAssign, bitand_assign, intersection);
774set_op!(
775    BitXor,
776    bitxor,
777    BitXorAssign,
778    bitxor_assign,
779    symmetric_difference
780);
781set_op!(Sub, sub, SubAssign, sub_assign, difference);
782
783impl Not for TagSet {
784    type Output = TagSet;
785
786    fn not(self) -> TagSet {
787        self.complement()
788    }
789}
790
791/// Iterator over the tags of a [`TagSet`] in name order (see
792/// [`TagSet::iter`]). Owns a copy of the set.
793#[derive(Clone, Debug)]
794pub struct Iter {
795    words: [u64; WORDS],
796    /// Index of the lowest word that may still have bits.
797    front: usize,
798    /// One past the highest word that may still have bits.
799    back: usize,
800}
801
802impl Iter {
803    fn tag(word: usize, bit: u32) -> Option<Tag> {
804        let id = word.checked_mul(64)?.checked_add(bit as usize)?;
805        Tag::from_id(id)
806    }
807}
808
809impl Iterator for Iter {
810    type Item = Tag;
811
812    fn next(&mut self) -> Option<Tag> {
813        while self.front < self.back {
814            let w = self.words.get_mut(self.front)?;
815            if *w != 0 {
816                let bit = w.trailing_zeros();
817                *w &= *w - 1;
818                return Self::tag(self.front, bit);
819            }
820            self.front += 1;
821        }
822        None
823    }
824
825    fn size_hint(&self) -> (usize, Option<usize>) {
826        let n = self
827            .words
828            .get(self.front..self.back)
829            .unwrap_or_default()
830            .iter()
831            .map(|w| w.count_ones() as usize)
832            .sum();
833        (n, Some(n))
834    }
835}
836
837impl DoubleEndedIterator for Iter {
838    fn next_back(&mut self) -> Option<Tag> {
839        while self.back > self.front {
840            let idx = self.back - 1;
841            let w = self.words.get_mut(idx)?;
842            if *w != 0 {
843                let bit = 63 - w.leading_zeros();
844                *w &= !(1u64 << bit);
845                return Self::tag(idx, bit);
846            }
847            self.back = idx;
848        }
849        None
850    }
851}
852
853impl ExactSizeIterator for Iter {}
854
855impl FusedIterator for Iter {}
856
857#[cfg(test)]
858mod tests {
859    use super::*;
860
861    #[test]
862    fn all_tags_sorted_unique_and_indexed() {
863        assert_eq!(ALL_TAGS.len(), TAG_COUNT);
864        assert!(ALL_TAGS.windows(2).all(|w| w[0] < w[1]));
865        for (i, name) in ALL_TAGS.iter().enumerate() {
866            let tag = Tag::from_name(name).expect("indexed");
867            assert_eq!(tag.id(), i);
868            assert_eq!(tag.as_str(), *name);
869        }
870        assert_eq!(TagSet::ALL.len(), TAG_COUNT);
871        assert_eq!(Tag::all().count(), TAG_COUNT);
872    }
873
874    #[test]
875    fn base_tag_constants() {
876        for (tag, name) in [
877            (Tag::DIRECTORY, DIRECTORY),
878            (Tag::SYMLINK, SYMLINK),
879            (Tag::SOCKET, SOCKET),
880            (Tag::FILE, FILE),
881            (Tag::EXECUTABLE, EXECUTABLE),
882            (Tag::NON_EXECUTABLE, NON_EXECUTABLE),
883            (Tag::TEXT, TEXT),
884            (Tag::BINARY, BINARY),
885        ] {
886            assert_eq!(tag.as_str(), name);
887        }
888        assert_eq!(TYPE_TAGS.len(), 4);
889        assert_eq!(MODE_TAGS.len(), 2);
890        assert_eq!(ENCODING_TAGS.len(), 2);
891        assert!(TYPE_TAGS.is_disjoint(&MODE_TAGS));
892        assert!(MODE_TAGS.is_disjoint(&ENCODING_TAGS));
893        assert!(Tag::FILE.is_type_tag());
894        assert!(Tag::TEXT.is_encoding_tag());
895        assert!(Tag::EXECUTABLE.is_mode_tag());
896        assert!(is_type_tag("socket") && is_mode_tag("executable") && is_encoding_tag("binary"));
897        assert!(!is_type_tag("python"));
898    }
899
900    #[test]
901    fn unknown_names() {
902        assert_eq!(Tag::from_name(""), None);
903        assert_eq!(Tag::from_name("Python"), None);
904        assert_eq!(Tag::from_id(TAG_COUNT), None);
905        let err = "python, nope, nada".parse::<TagSet>().expect_err("unknown");
906        assert_eq!(err.names(), ["nope", "nada"]);
907        assert_eq!(err.to_string(), r#"unknown tags "nope", "nada""#);
908        let err = "zzz".parse::<Tag>().expect_err("unknown");
909        assert_eq!(err.to_string(), r#"unknown tag "zzz""#);
910    }
911
912    #[test]
913    fn set_operations() {
914        let a: TagSet = "python, text, file".parse().expect("valid");
915        let b: TagSet = "text, binary".parse().expect("valid");
916        assert_eq!((a | b).to_string(), "binary, file, python, text");
917        assert_eq!((a & b).to_string(), "text");
918        assert_eq!((a - b).to_string(), "file, python");
919        assert_eq!((a ^ b).to_string(), "binary, file, python");
920        assert_eq!((!a).len(), TAG_COUNT - 3);
921        assert!((a | b).is_superset(&a));
922        assert!(a.is_subset(&(a | b)));
923        assert!(a.intersects(&b));
924        assert!(!a.is_disjoint(&b));
925        let mut c = a;
926        assert!(!c.insert(Tag::TEXT));
927        assert!(c.remove(Tag::TEXT));
928        assert!(!c.contains(Tag::TEXT));
929        c |= Tag::BINARY;
930        assert!(c.contains("binary"));
931        c.clear();
932        assert!(c.is_empty());
933        assert_eq!(TagSet::from([Tag::TEXT, Tag::FILE]).len(), 2);
934        assert_eq!(format!("{:?}", TagSet::from(Tag::TEXT)), r#"{"text"}"#);
935        assert_eq!(format!("{:?}", Tag::TEXT), r#"Tag("text")"#);
936        assert_eq!(TagSet::EMPTY.to_string(), "");
937        assert_eq!("".parse::<TagSet>(), Ok(TagSet::EMPTY));
938    }
939
940    #[test]
941    fn iteration_order_and_double_ended() {
942        let set = TagSet::ALL;
943        let forward: Vec<_> = set.names().collect();
944        assert_eq!(forward, ALL_TAGS);
945        let mut backward: Vec<_> = set.names().rev().collect();
946        backward.reverse();
947        assert_eq!(backward, ALL_TAGS);
948        let mut it = set.iter();
949        assert_eq!(it.len(), TAG_COUNT);
950        assert_eq!(it.next().map(Tag::id), Some(0));
951        assert_eq!(it.next_back().map(Tag::id), Some(TAG_COUNT - 1));
952        assert_eq!(it.len(), TAG_COUNT - 2);
953        assert_eq!(it.by_ref().count(), TAG_COUNT - 2);
954        assert_eq!(it.next(), None);
955        assert_eq!(it.next_back(), None);
956    }
957
958    #[test]
959    fn send_sync_copy() {
960        fn assert_traits<T: Send + Sync + Copy + 'static>() {}
961        assert_traits::<Tag>();
962        assert_traits::<TagSet>();
963        assert_eq!(core::mem::size_of::<Tag>(), 2);
964        assert_eq!(core::mem::size_of::<TagSet>(), WORDS * 8);
965    }
966}