taffy/compute/grid/types/
named.rs

1//! Code for resolving name grid lines and areas
2
3use crate::{
4    CheapCloneStr, GenericGridTemplateComponent, GenericRepetition as _, GridAreaAxis, GridAreaEnd, GridContainerStyle,
5    GridPlacement, GridTemplateArea, Line, NonNamedGridPlacement, RepetitionCount,
6};
7use core::{borrow::Borrow, cmp::Ordering, fmt::Debug};
8
9use super::GridLine;
10// use alloc::fmt::format;
11use crate::sys::{format, single_value_vec, Map, Vec};
12
13/// Wrap an `AsRef<str>` type with a type which implements Hash by first
14/// deferring to the underlying `&str`'s implementation of Hash.
15#[derive(Debug, Clone)]
16pub(crate) struct StrHasher<T: CheapCloneStr>(pub T);
17impl<T: CheapCloneStr> PartialOrd for StrHasher<T> {
18    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
19        Some(self.cmp(other))
20    }
21}
22impl<T: CheapCloneStr> Ord for StrHasher<T> {
23    fn cmp(&self, other: &Self) -> Ordering {
24        self.0.as_ref().cmp(other.0.as_ref())
25    }
26}
27impl<T: CheapCloneStr> PartialEq for StrHasher<T> {
28    fn eq(&self, other: &Self) -> bool {
29        other.0.as_ref() == self.0.as_ref()
30    }
31}
32impl<T: CheapCloneStr> Eq for StrHasher<T> {}
33#[cfg(feature = "std")]
34impl<T: CheapCloneStr> std::hash::Hash for StrHasher<T> {
35    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
36        self.0.as_ref().hash(state)
37    }
38}
39impl<T: CheapCloneStr> Borrow<str> for StrHasher<T> {
40    fn borrow(&self) -> &str {
41        self.0.as_ref()
42    }
43}
44
45/// Resolver that takes grid lines names and area names as input and can then be used to
46/// resolve line names of grid placement properties into line numbers.
47pub(crate) struct NamedLineResolver<S: CheapCloneStr> {
48    /// Map of row line names to line numbers. Each line name may correspond to multiple lines
49    /// so we store a `Vec`
50    row_lines: Map<StrHasher<S>, Vec<u16>>,
51    /// Map of column line names to line numbers. Each line name may correspond to multiple lines
52    /// so we store a `Vec`
53    column_lines: Map<StrHasher<S>, Vec<u16>>,
54    /// Map of area names to area definitions (start and end lines numbers in each axis)
55    areas: Map<StrHasher<S>, GridTemplateArea<S>>,
56    /// Number of columns implied by grid area definitions
57    area_column_count: u16,
58    /// Number of rows implied by grid area definitions
59    area_row_count: u16,
60    /// The number of explicit columns in the grid. This is an *input* to the `NamedLineResolver` and is
61    /// used when computing the fallback line when a non-existent named line is specified.
62    explicit_column_count: u16,
63    /// The number of explicit rows in the grid. This is an *input* to the `NamedLineResolver` and is
64    /// used when computing the fallback line when a non-existent named line is specified.
65    explicit_row_count: u16,
66}
67
68/// Utility function to create or update an entry in a line name map
69fn upsert_line_name_map<S: CheapCloneStr>(map: &mut Map<StrHasher<S>, Vec<u16>>, key: S, value: u16) {
70    map.entry(StrHasher(key)).and_modify(|lines| lines.push(value)).or_insert_with(|| single_value_vec(value));
71}
72
73impl<S: CheapCloneStr> NamedLineResolver<S> {
74    /// Create and initialise a new `NamedLineResolver`
75    pub(crate) fn new(
76        style: &impl GridContainerStyle<CustomIdent = S>,
77        column_auto_repetitions: u16,
78        row_auto_repetitions: u16,
79    ) -> Self {
80        let mut areas: Map<StrHasher<S>, GridTemplateArea<_>> = Map::new();
81        let mut column_lines: Map<StrHasher<S>, Vec<u16>> = Map::new();
82        let mut row_lines: Map<StrHasher<S>, Vec<u16>> = Map::new();
83
84        let mut area_column_count = 0;
85        let mut area_row_count = 0;
86        if let Some(area_iter) = style.grid_template_areas() {
87            for area in area_iter.into_iter() {
88                // TODO: Investigate eliminating clones
89                areas.insert(StrHasher(area.name.clone()), area.clone());
90
91                area_column_count = area_column_count.max(area.column_end.max(1) - 1);
92                area_row_count = area_row_count.max(area.row_end.max(1) - 1);
93
94                let col_start_name = S::from(format!("{}-start", area.name.as_ref()));
95                upsert_line_name_map(&mut column_lines, col_start_name, area.column_start);
96                let col_end_name = S::from(format!("{}-end", area.name.as_ref()));
97                upsert_line_name_map(&mut column_lines, col_end_name, area.column_end);
98                let row_start_name = S::from(format!("{}-start", area.name.as_ref()));
99                upsert_line_name_map(&mut row_lines, row_start_name, area.row_start);
100                let row_end_name = S::from(format!("{}-end", area.name.as_ref()));
101                upsert_line_name_map(&mut row_lines, row_end_name, area.row_end);
102            }
103        }
104
105        // ---
106
107        let mut current_line = 0;
108        if let Some(mut column_tracks) = style.grid_template_columns() {
109            if let Some(column_line_names_iter) = style.grid_template_column_names() {
110                for line_names in column_line_names_iter {
111                    current_line += 1;
112                    for line_name in line_names.into_iter() {
113                        column_lines
114                            .entry(StrHasher(line_name.clone()))
115                            .and_modify(|lines: &mut Vec<u16>| lines.push(current_line))
116                            .or_insert_with(|| single_value_vec(current_line));
117                    }
118
119                    if let Some(GenericGridTemplateComponent::Repeat(repeat)) = column_tracks.next() {
120                        let repeat_count = match repeat.count() {
121                            RepetitionCount::Count(count) => count,
122                            RepetitionCount::AutoFill | RepetitionCount::AutoFit => column_auto_repetitions,
123                        };
124
125                        for _ in 0..repeat_count {
126                            for line_name_set in repeat.lines_names() {
127                                for line_name in line_name_set {
128                                    upsert_line_name_map(&mut column_lines, line_name.clone(), current_line);
129                                }
130                                current_line += 1;
131                            }
132                            // Last line name set collapses with following line name set
133                            current_line -= 1;
134                        }
135                        // Last line name set collapses with following line name set
136                        current_line -= 1;
137                    }
138                }
139            }
140        }
141        // Sort and dedup lines for each column name
142        for lines in column_lines.values_mut() {
143            lines.sort_unstable();
144            lines.dedup();
145        }
146
147        let mut current_line = 0;
148        if let Some(mut row_tracks) = style.grid_template_rows() {
149            if let Some(row_line_names_iter) = style.grid_template_row_names() {
150                for line_names in row_line_names_iter {
151                    current_line += 1;
152                    for line_name in line_names.into_iter() {
153                        row_lines
154                            .entry(StrHasher(line_name.clone()))
155                            .and_modify(|lines: &mut Vec<u16>| lines.push(current_line))
156                            .or_insert_with(|| single_value_vec(current_line));
157                    }
158
159                    if let Some(GenericGridTemplateComponent::Repeat(repeat)) = row_tracks.next() {
160                        let repeat_count = match repeat.count() {
161                            RepetitionCount::Count(count) => count,
162                            RepetitionCount::AutoFill | RepetitionCount::AutoFit => row_auto_repetitions,
163                        };
164
165                        for _ in 0..repeat_count {
166                            for line_name_set in repeat.lines_names() {
167                                for line_name in line_name_set {
168                                    upsert_line_name_map(&mut row_lines, line_name.clone(), current_line);
169                                }
170                                current_line += 1;
171                            }
172                            // Last line name set collapses with following line name set
173                            current_line -= 1;
174                        }
175                        // Last line name set collapses with following line name set
176                        current_line -= 1;
177                    }
178                }
179            }
180        }
181        // Sort and dedup lines for each row name
182        for lines in row_lines.values_mut() {
183            lines.sort_unstable();
184            lines.dedup();
185        }
186
187        Self {
188            area_column_count,
189            area_row_count,
190            explicit_column_count: 0, // Overwritten later
191            explicit_row_count: 0,    // Overwritten later
192            areas,
193            row_lines,
194            column_lines,
195        }
196    }
197
198    /// Resolve named lines for both the `start` and `end` of a row-axis grid placement
199    #[inline(always)]
200    pub(crate) fn resolve_row_names(&self, line: &Line<GridPlacement<S>>) -> Line<NonNamedGridPlacement> {
201        self.resolve_line_names(line, GridAreaAxis::Row)
202    }
203
204    /// Resolve named lines for both the `start` and `end` of a column-axis grid placement
205    #[inline(always)]
206    pub(crate) fn resolve_column_names(&self, line: &Line<GridPlacement<S>>) -> Line<NonNamedGridPlacement> {
207        self.resolve_line_names(line, GridAreaAxis::Column)
208    }
209
210    /// Resolve named lines for both the `start` and `end` of a grid placement
211    #[inline(always)]
212    pub(crate) fn resolve_line_names(
213        &self,
214        line: &Line<GridPlacement<S>>,
215        axis: GridAreaAxis,
216    ) -> Line<NonNamedGridPlacement> {
217        let start_holder;
218        let start_line_resolved = if let GridPlacement::NamedLine(name, idx) = &line.start {
219            start_holder =
220                GridPlacement::Line(self.find_line_index(name, *idx, axis, GridAreaEnd::Start, &|lines| lines));
221            &start_holder
222        } else {
223            &line.start
224        };
225
226        let end_holder;
227        let end_line_resolved = if let GridPlacement::NamedLine(name, idx) = &line.end {
228            end_holder = GridPlacement::Line(self.find_line_index(name, *idx, axis, GridAreaEnd::End, &|lines| lines));
229            &end_holder
230        } else {
231            &line.end
232        };
233
234        // If both the *-start and *-end values of its grid-placement properties specify a line, its grid span is implicit.
235        // If it has an explicit span value, its grid span is explicit.
236        // Otherwise, its grid span is automatic:
237        //   - if it is subgridded in that axis, its grid span is determined from its <line-name-list>;
238        //   - otherwise its grid span is 1.
239        //
240        // <https://drafts.csswg.org/css-grid-2/#grid-span>
241        match (&start_line_resolved, &end_line_resolved) {
242            (GridPlacement::Line(start_line), GridPlacement::NamedSpan(name, idx)) => {
243                let explicit_track_count = match axis {
244                    GridAreaAxis::Row => self.explicit_row_count as i16,
245                    GridAreaAxis::Column => self.explicit_column_count as i16,
246                };
247                let normalized_start_line = if start_line.as_i16() > 0 {
248                    start_line.as_i16() as u16
249                } else {
250                    (explicit_track_count + 1 + start_line.as_i16()).max(0) as u16
251                };
252                let end_line = self.find_line_index(name, *idx as i16, axis, GridAreaEnd::End, &|lines| {
253                    let point = lines.partition_point(|line| *line <= normalized_start_line);
254                    &lines[point..]
255                });
256                Line { start: NonNamedGridPlacement::Line(*start_line), end: NonNamedGridPlacement::Line(end_line) }
257            }
258            (GridPlacement::NamedSpan(name, idx), GridPlacement::Line(end_line)) => {
259                let explicit_track_count = match axis {
260                    GridAreaAxis::Row => self.explicit_row_count as i16,
261                    GridAreaAxis::Column => self.explicit_column_count as i16,
262                };
263                let normalized_end_line = if end_line.as_i16() > 0 {
264                    end_line.as_i16() as u16
265                } else {
266                    (explicit_track_count + 1 + end_line.as_i16()).max(0) as u16
267                };
268                let start_line = self.find_line_index(name, *idx as i16, axis, GridAreaEnd::Start, &|lines| {
269                    let point = lines.partition_point(|line| *line < normalized_end_line);
270                    &lines[..point]
271                });
272                Line { start: NonNamedGridPlacement::Line(start_line), end: NonNamedGridPlacement::Line(*end_line) }
273            }
274            (start, end) => Line {
275                start: match start {
276                    GridPlacement::Auto => NonNamedGridPlacement::Auto,
277                    GridPlacement::Line(grid_line) => NonNamedGridPlacement::Line(*grid_line),
278                    GridPlacement::Span(span) => NonNamedGridPlacement::Span(*span),
279                    GridPlacement::NamedSpan(_, _) => NonNamedGridPlacement::Span(1),
280                    _ => unreachable!(),
281                },
282                end: match end {
283                    GridPlacement::Auto => NonNamedGridPlacement::Auto,
284                    GridPlacement::Line(grid_line) => NonNamedGridPlacement::Line(*grid_line),
285                    GridPlacement::Span(span) => NonNamedGridPlacement::Span(*span),
286                    GridPlacement::NamedSpan(_, _) => NonNamedGridPlacement::Span(1),
287                    _ => unreachable!(),
288                },
289            },
290        }
291    }
292
293    /// Resolve the grid line for a named grid line or span
294    fn find_line_index(
295        &self,
296        name: &S,
297        idx: i16,
298        axis: GridAreaAxis,
299        end: GridAreaEnd,
300        filter_lines: &dyn Fn(&[u16]) -> &[u16],
301    ) -> GridLine {
302        let name = name.as_ref();
303        let mut idx = idx;
304        let explicit_track_count = match axis {
305            GridAreaAxis::Row => self.explicit_row_count as i16,
306            GridAreaAxis::Column => self.explicit_column_count as i16,
307        };
308
309        // An index of 0 is used to represent "no index specified".
310        if idx == 0 {
311            idx = 1;
312        }
313
314        fn get_line(lines: &[u16], explicit_track_count: i16, idx: i16) -> i16 {
315            let abs_idx = idx.abs();
316            let enough_lines = abs_idx <= lines.len() as i16;
317            if enough_lines {
318                if idx > 0 {
319                    lines[(abs_idx - 1) as usize] as i16
320                } else {
321                    lines[lines.len() - (abs_idx) as usize] as i16
322                }
323            } else {
324                let remaining_lines = (abs_idx - lines.len() as i16) * idx.signum();
325                if idx > 0 {
326                    (explicit_track_count + 1) + remaining_lines
327                } else {
328                    -((explicit_track_count + 1) + remaining_lines)
329                }
330            }
331        }
332
333        // Lookup lines
334        let line_lookup = match axis {
335            GridAreaAxis::Row => &self.row_lines,
336            GridAreaAxis::Column => &self.column_lines,
337        };
338        if let Some(lines) = line_lookup.get(name) {
339            return GridLine::from(get_line(filter_lines(lines), explicit_track_count, idx));
340        } else {
341            // TODO: eliminate string allocations
342            match end {
343                GridAreaEnd::Start => {
344                    let implicit_name = format!("{name}-start");
345                    if let Some(lines) = line_lookup.get(&*implicit_name) {
346                        // println!("IMPLICIT COL {implicit_name}");
347                        return GridLine::from(get_line(filter_lines(lines), explicit_track_count, idx));
348                    }
349                }
350                GridAreaEnd::End => {
351                    let implicit_name = format!("{name}-end");
352                    if let Some(lines) = line_lookup.get(&*implicit_name) {
353                        // println!("IMPLICIT ROW {implicit_name}");
354                        return GridLine::from(get_line(filter_lines(lines), explicit_track_count, idx));
355                    }
356                }
357            }
358        }
359
360        // The CSS Grid specification has a weird quirk where it matches non-existent line names
361        // to the first (positive) implicit line in the grid
362        //
363        // We add/subtract 2 to the explicit track count because (in each axis) a grid has one more explicit
364        // grid line than it has tracks. And the fallback line is the line *after* that.
365        //
366        // See: <https://github.com/w3c/csswg-drafts/issues/966#issuecomment-277042153>
367        let line = if idx > 0 { (explicit_track_count + 1) + idx } else { -((explicit_track_count + 1) + idx) };
368
369        GridLine::from(line)
370    }
371
372    /// Get the number of columns defined by the grid areas
373    pub(crate) fn area_column_count(&self) -> u16 {
374        self.area_column_count
375    }
376
377    /// Get the number of rows defined by the grid areas
378    pub(crate) fn area_row_count(&self) -> u16 {
379        self.area_row_count
380    }
381
382    /// Set the number of columns in the explicit grid
383    pub(crate) fn set_explicit_column_count(&mut self, count: u16) {
384        self.explicit_column_count = count;
385    }
386
387    /// Set the number of rows in the explicit grid
388    pub(crate) fn set_explicit_row_count(&mut self, count: u16) {
389        self.explicit_row_count = count;
390    }
391}
392
393impl<S: CheapCloneStr> Debug for NamedLineResolver<S> {
394    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
395        writeln!(f, "Grid Areas:")?;
396        for area in self.areas.values() {
397            writeln!(
398                f,
399                "{}: row:{}/{} col: {}/{}",
400                area.name.as_ref(),
401                area.row_start,
402                area.row_end,
403                area.column_start,
404                area.column_end
405            )?;
406        }
407
408        writeln!(f, "Grid Rows:")?;
409        for (name, lines) in self.row_lines.iter() {
410            write!(f, "{}: ", name.0.as_ref())?;
411            for line in lines {
412                write!(f, "{line}  ")?;
413            }
414            writeln!(f)?;
415        }
416
417        writeln!(f, "Grid Columns:")?;
418        for (name, lines) in self.column_lines.iter() {
419            write!(f, "{}: ", name.0.as_ref())?;
420            for line in lines {
421                write!(f, "{line}  ")?;
422            }
423            writeln!(f)?;
424        }
425
426        Ok(())
427    }
428}
taffy/compute/grid/types/named.rs

taffy/compute/grid/types/
named.rs
