substrate/layout/
tracks.rs

1//! Routing track management.
2
3use geometry::span::Span;
4use num::integer::{div_ceil, div_floor};
5use serde::{Deserialize, Serialize};
6
7/// A uniform set of tracks.
8///
9/// The track line and space must be even.
10///
11/// Track 0 is centered at `offset`.
12/// Track 1 is centered at `offset + line + space`.
13/// Track -1 is centered at `offset - (line + space)`.
14#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash, Serialize, Deserialize)]
15pub struct UniformTracks {
16    /// The width of each track.
17    line: i64,
18    /// Spacing between adjacent track edges.
19    space: i64,
20    /// An offset that translates all tracks.
21    offset: i64,
22}
23
24impl UniformTracks {
25    /// Create a uniform track set with the given line and space.
26    pub fn new(line: i64, space: i64) -> Self {
27        Self::with_offset(line, space, 0)
28    }
29
30    /// Create a uniform track set with the given line, space, and offset.
31    pub fn with_offset(line: i64, space: i64, offset: i64) -> Self {
32        assert_eq!(line & 1, 0, "track width must be even");
33        assert_eq!(space & 1, 0, "track spacing must be even");
34        assert!(line > 0);
35        assert!(space > 0);
36        Self {
37            line,
38            space,
39            offset,
40        }
41    }
42
43    /// Gets the coordinates of the `i`-th track.
44    pub fn get(&self, idx: i64) -> Span {
45        let start = self.offset + idx * self.pitch() - self.line / 2;
46        Span::new(start, start + self.line)
47    }
48
49    /// The pitch (line + space) of the tracks.
50    #[inline]
51    pub fn pitch(&self) -> i64 {
52        self.line + self.space
53    }
54
55    /// Iterates over a range of adjacent tracks.
56    pub fn get_tracks(
57        &self,
58        range: impl Into<std::ops::Range<i64>>,
59    ) -> impl Iterator<Item = Span> + '_ {
60        range.into().map(|i| self.get(i))
61    }
62
63    /// Explicitly enumerates a range of adjacent tracks, returning an [`EnumeratedTracks`].
64    ///
65    /// Note that this uses `O(N)` storage, where `N` is the length of the range.
66    pub fn enumerate(&self, range: impl Into<std::ops::Range<i64>>) -> EnumeratedTracks {
67        self.get_tracks(range).collect()
68    }
69
70    /// Converts a geometric coordinate to the index of the nearest track.
71    pub fn to_track_idx(&self, coord: i64, mode: RoundingMode) -> i64 {
72        match mode {
73            RoundingMode::Down => div_floor(coord - self.offset + self.line / 2, self.pitch()),
74            RoundingMode::Up => div_ceil(coord - self.offset - self.line / 2, self.pitch()),
75            RoundingMode::Nearest => div_floor(
76                coord - self.offset + self.pitch() / 2 + self.line / 2,
77                self.pitch(),
78            ),
79        }
80    }
81}
82
83/// Rounding options.
84#[derive(Copy, Clone, Eq, PartialEq, Default, Debug, Serialize, Deserialize)]
85pub enum RoundingMode {
86    /// Round to the nearest number.
87    #[default]
88    Nearest,
89    /// Round down.
90    Down,
91    /// Round up.
92    Up,
93}
94
95/// A set of explicitly listed, ordered tracks.
96#[derive(Debug, Clone, Eq, PartialEq, Hash, Serialize, Deserialize)]
97pub struct EnumeratedTracks {
98    tracks: Vec<Span>,
99}
100
101impl EnumeratedTracks {
102    /// Iterates over the tracks in this [`EnumeratedTracks`].
103    pub fn tracks(&self) -> impl Iterator<Item = Span> + '_ {
104        self.tracks.iter().copied()
105    }
106
107    /// Construct a new [`EnumeratedTracks`] from an iterator.
108    ///
109    /// # Panics
110    ///
111    /// Panics if the tracks are not in order.
112    pub fn new(iter: impl IntoIterator<Item = Span>) -> Self {
113        iter.into_iter().collect()
114    }
115
116    /// Returns the number of tracks in the set.
117    pub fn len(&self) -> usize {
118        self.tracks.len()
119    }
120
121    /// Returns `true` if the set of tracks is empty.
122    #[inline]
123    pub fn is_empty(&self) -> bool {
124        self.tracks.is_empty()
125    }
126}
127
128impl FromIterator<Span> for EnumeratedTracks {
129    fn from_iter<T: IntoIterator<Item = Span>>(iter: T) -> Self {
130        let tracks: Vec<Span> = iter.into_iter().collect();
131        // check that tracks are ordered and valid
132        for (track, next) in tracks.iter().zip(tracks.iter().skip(1)) {
133            assert!(next.start() > track.stop());
134        }
135        Self { tracks }
136    }
137}
138
139impl IntoIterator for EnumeratedTracks {
140    type Item = Span;
141    type IntoIter = std::vec::IntoIter<Span>;
142    fn into_iter(self) -> Self::IntoIter {
143        self.tracks.into_iter()
144    }
145}
146
147/// A set of tracks.
148pub trait Tracks {
149    /// The track at the given index.
150    fn try_track(&self, idx: i64) -> Option<Span>;
151
152    /// The range of valid indices, as a tuple `(min, max)`.
153    ///
154    /// If there is no min/max index, implementers should return `None`.
155    fn try_range(&self) -> (Option<i64>, Option<i64>);
156
157    /// The track at the given index, panicking if the index is out of bounds.
158    #[inline]
159    fn track(&self, idx: i64) -> Span {
160        self.try_track(idx).expect("track index out of bounds")
161    }
162}
163
164/// A finite set of tracks.
165pub trait FiniteTracks {
166    /// The range of valid indices, as a tuple `(min, max)`.
167    ///
168    /// The minimum acceptable index is `min`; the maximum acceptable index is `max-1`,
169    /// which must be greater than or equal to `min`.
170    fn range(&self) -> (i64, i64);
171}
172
173impl Tracks for EnumeratedTracks {
174    fn try_track(&self, idx: i64) -> Option<Span> {
175        let idx = usize::try_from(idx).ok()?;
176        self.tracks.get(idx).copied()
177    }
178
179    fn try_range(&self) -> (Option<i64>, Option<i64>) {
180        let range = <Self as FiniteTracks>::range(self);
181        (Some(range.0), Some(range.1))
182    }
183}
184
185impl FiniteTracks for EnumeratedTracks {
186    fn range(&self) -> (i64, i64) {
187        let max = i64::try_from(self.tracks.len()).expect("track list length is too long");
188        (0, max)
189    }
190}
191
192impl Tracks for UniformTracks {
193    fn try_track(&self, idx: i64) -> Option<Span> {
194        Some(self.get(idx))
195    }
196
197    fn try_range(&self) -> (Option<i64>, Option<i64>) {
198        (None, None)
199    }
200}
201
202#[cfg(test)]
203mod tests {
204    use geometry::span::Span;
205
206    use super::*;
207
208    #[test]
209    fn enumerated_tracks() {
210        let tracks: EnumeratedTracks = [Span::new(10, 20), Span::new(30, 40), Span::new(80, 100)]
211            .into_iter()
212            .collect();
213
214        assert_eq!(tracks.track(0), Span::new(10, 20));
215        assert_eq!(tracks.track(1), Span::new(30, 40));
216        assert_eq!(tracks.track(2), Span::new(80, 100));
217        assert_eq!(tracks.range(), (0, 3));
218        assert_eq!(tracks.try_track(-1), None);
219        assert_eq!(tracks.try_track(3), None);
220    }
221
222    #[test]
223    #[should_panic]
224    fn enumerated_tracks_panics_when_tracks_are_out_of_order() {
225        let _: EnumeratedTracks = [Span::new(10, 20), Span::new(15, 30), Span::new(80, 100)]
226            .into_iter()
227            .collect();
228    }
229
230    #[test]
231    fn uniform_tracks() {
232        let tracks = UniformTracks::new(20, 40);
233
234        assert_eq!(tracks.track(-2), Span::new(-130, -110));
235        assert_eq!(tracks.track(-1), Span::new(-70, -50));
236        assert_eq!(tracks.track(0), Span::new(-10, 10));
237        assert_eq!(tracks.track(1), Span::new(50, 70));
238        assert_eq!(tracks.track(2), Span::new(110, 130));
239        assert_eq!(tracks.try_range(), (None, None));
240    }
241
242    #[test]
243    fn uniform_tracks_with_offset() {
244        let tracks = UniformTracks::with_offset(20, 40, 15);
245
246        assert_eq!(tracks.track(-2), Span::new(-115, -95));
247        assert_eq!(tracks.track(-1), Span::new(-55, -35));
248        assert_eq!(tracks.track(0), Span::new(5, 25));
249        assert_eq!(tracks.track(1), Span::new(65, 85));
250        assert_eq!(tracks.track(2), Span::new(125, 145));
251        assert_eq!(tracks.try_range(), (None, None));
252    }
253
254    #[test]
255    #[should_panic]
256    fn uniform_tracks_requires_even_line_width() {
257        UniformTracks::new(5, 40);
258    }
259
260    #[test]
261    #[should_panic]
262    fn uniform_tracks_requires_even_spacing() {
263        UniformTracks::new(320, 645);
264    }
265
266    #[test]
267    fn uniform_tracks_to_track_idx() {
268        let tracks = UniformTracks::with_offset(260, 140, 130);
269        assert_eq!(tracks.to_track_idx(-20, RoundingMode::Down), -1);
270        assert_eq!(tracks.to_track_idx(-550, RoundingMode::Down), -2);
271        assert_eq!(tracks.to_track_idx(-200, RoundingMode::Down), -1);
272        assert_eq!(tracks.to_track_idx(-20, RoundingMode::Up), 0);
273        assert_eq!(tracks.to_track_idx(-530, RoundingMode::Up), -1);
274        assert_eq!(tracks.to_track_idx(-550, RoundingMode::Up), -2);
275    }
276}
substrate/layout/tracks.rs

substrate/layout/
tracks.rs
