1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

//! A mechanism for allocating XIDs.

use crate::errors::ConnectError;
use crate::protocol::xc_misc::GetXIDRangeReply;

#[cfg(feature = "std")]
use std::error::Error;

use core::fmt;

/// An allocator for X11 IDs.
///
/// This struct handles the client-side generation of X11 IDs. The ID allocation is based on a
/// range of IDs that the server assigned us. This range is described by a base and a mask. From
/// the X11 protocol reference manual:
///
/// > The resource-id-mask contains a single contiguous set of bits (at least 18). The client
/// > allocates resource IDs [..] by choosing a value with only some subset of these bits set and
/// > ORing it with resource-id-base.
#[derive(Debug, Clone, Copy)]
pub struct IdAllocator {
    next_id: u32,
    max_id: u32,
    increment: u32,
}

impl IdAllocator {
    /// Create a new instance of an ID allocator.
    ///
    /// The arguments should be the `resource_id_base` and `resource_id_mask` values that the X11
    /// server sent in a `Setup` response.
    pub fn new(id_base: u32, id_mask: u32) -> Result<Self, ConnectError> {
        if id_mask == 0 {
            return Err(ConnectError::ZeroIdMask);
        }
        // Find the right-most set bit in id_mask, e.g. for 0b110, this results in 0b010.
        let increment = id_mask & (1 + !id_mask);
        Ok(Self {
            next_id: id_base,
            max_id: id_base | id_mask,
            increment,
        })
    }

    /// Update the available range of IDs based on a GetXIDRangeReply
    pub fn update_xid_range(&mut self, xidrange: &GetXIDRangeReply) -> Result<(), IdsExhausted> {
        let (start, count) = (xidrange.start_id, xidrange.count);
        // Apparently (0, 1) is how the server signals "I am out of IDs".
        // The second case avoids an underflow below and should never happen.
        if (start, count) == (0, 1) || count == 0 {
            return Err(IdsExhausted);
        }
        self.next_id = start;
        self.max_id = start + (count - 1) * self.increment;
        Ok(())
    }

    /// Generate the next ID.
    pub fn generate_id(&mut self) -> Option<u32> {
        if self.next_id > self.max_id {
            None
        } else {
            let id = self.next_id;
            self.next_id += self.increment;
            Some(id)
        }
    }
}

/// The XID range has been exhausted.
#[derive(Debug, Copy, Clone)]
pub struct IdsExhausted;

impl fmt::Display for IdsExhausted {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "XID range has been exhausted")
    }
}

#[cfg(feature = "std")]
impl Error for IdsExhausted {}

#[cfg(test)]
mod test {
    use super::{GetXIDRangeReply, IdAllocator, IdsExhausted};

    #[test]
    fn exhaustive() {
        let mut allocator = IdAllocator::new(0x2800, 0x1ff).unwrap();
        for expected in 0x2800..=0x29ff {
            assert_eq!(Some(expected), allocator.generate_id());
        }
        assert_eq!(None, allocator.generate_id());
    }

    #[test]
    fn increment() {
        let mut allocator = IdAllocator::new(0, 0b1100).unwrap();
        assert_eq!(Some(0b0000), allocator.generate_id());
        assert_eq!(Some(0b0100), allocator.generate_id());
        assert_eq!(Some(0b1000), allocator.generate_id());
        assert_eq!(Some(0b1100), allocator.generate_id());
        assert_eq!(None, allocator.generate_id());
    }

    #[test]
    fn new_range() {
        let mut allocator = IdAllocator::new(0x420, 2).unwrap();
        assert_eq!(Some(0x420), allocator.generate_id());
        assert_eq!(Some(0x422), allocator.generate_id());
        // At this point the range is exhausted and a GetXIDRange request needs to be sent
        assert_eq!(None, allocator.generate_id());
        allocator
            .update_xid_range(&generate_get_xid_range_reply(0x13370, 3))
            .unwrap();
        assert_eq!(Some(0x13370), allocator.generate_id());
        assert_eq!(Some(0x13372), allocator.generate_id());
        assert_eq!(Some(0x13374), allocator.generate_id());
        // At this point the range is exhausted and a GetXIDRange request needs to be sent
        assert_eq!(None, allocator.generate_id());
        allocator
            .update_xid_range(&generate_get_xid_range_reply(0x13370, 3))
            .unwrap();
        assert_eq!(Some(0x13370), allocator.generate_id());
    }

    #[test]
    fn invalid_new_arg() {
        let err = IdAllocator::new(1234, 0).unwrap_err();
        if let super::ConnectError::ZeroIdMask = err {
        } else {
            panic!("Wrong error: {:?}", err);
        }
    }

    #[test]
    fn invalid_update_arg() {
        fn check_ids_exhausted(arg: &Result<(), IdsExhausted>) {
            if let Err(IdsExhausted) = arg {
            } else {
                panic!("Expected IdsExhausted, got {:?}", arg);
            }
        }

        let mut allocator = IdAllocator::new(0x420, 2).unwrap();
        check_ids_exhausted(&allocator.update_xid_range(&generate_get_xid_range_reply(0, 1)));
        check_ids_exhausted(&allocator.update_xid_range(&generate_get_xid_range_reply(1, 0)));
    }

    fn generate_get_xid_range_reply(start_id: u32, count: u32) -> GetXIDRangeReply {
        GetXIDRangeReply {
            sequence: 0,
            length: 0,
            start_id,
            count,
        }
    }
}