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<u32>>,
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<u32>>,
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<u32>>, key: S, value: u32) {
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<u32>> = Map::new();
82        let mut row_lines: Map<StrHasher<S>, Vec<u32>> = Map::new();
83
84        // The size of the area template may be larger than the extents of the named areas
85        // due to unnamed (`.`) cells, so it is taken from the style rather than being derived
86        // from the areas themselves.
87        let area_column_count = style.grid_template_area_column_count();
88        let area_row_count = style.grid_template_area_row_count();
89        if let Some(area_iter) = style.grid_template_areas() {
90            for area in area_iter.into_iter() {
91                // TODO: Investigate eliminating clones
92                areas.insert(StrHasher(area.name.clone()), area.clone());
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 as u32);
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 as u32);
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 as u32);
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 as u32);
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<u32>| 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                        if repeat_count > 0 {
137                            current_line -= 1;
138                        }
139                    }
140                }
141            }
142        }
143        // Sort and dedup lines for each column name
144        for lines in column_lines.values_mut() {
145            lines.sort_unstable();
146            lines.dedup();
147        }
148
149        let mut current_line = 0;
150        if let Some(mut row_tracks) = style.grid_template_rows() {
151            if let Some(row_line_names_iter) = style.grid_template_row_names() {
152                for line_names in row_line_names_iter {
153                    current_line += 1;
154                    for line_name in line_names.into_iter() {
155                        row_lines
156                            .entry(StrHasher(line_name.clone()))
157                            .and_modify(|lines: &mut Vec<u32>| lines.push(current_line))
158                            .or_insert_with(|| single_value_vec(current_line));
159                    }
160
161                    if let Some(GenericGridTemplateComponent::Repeat(repeat)) = row_tracks.next() {
162                        let repeat_count = match repeat.count() {
163                            RepetitionCount::Count(count) => count,
164                            RepetitionCount::AutoFill | RepetitionCount::AutoFit => row_auto_repetitions,
165                        };
166
167                        for _ in 0..repeat_count {
168                            for line_name_set in repeat.lines_names() {
169                                for line_name in line_name_set {
170                                    upsert_line_name_map(&mut row_lines, line_name.clone(), current_line);
171                                }
172                                current_line += 1;
173                            }
174                            // Last line name set collapses with following line name set
175                            current_line -= 1;
176                        }
177                        // Last line name set collapses with following line name set
178                        if repeat_count > 0 {
179                            current_line -= 1;
180                        }
181                    }
182                }
183            }
184        }
185        // Sort and dedup lines for each row name
186        for lines in row_lines.values_mut() {
187            lines.sort_unstable();
188            lines.dedup();
189        }
190
191        Self {
192            area_column_count,
193            area_row_count,
194            explicit_column_count: 0, // Overwritten later
195            explicit_row_count: 0,    // Overwritten later
196            areas,
197            row_lines,
198            column_lines,
199        }
200    }
201
202    /// Resolve named lines for both the `start` and `end` of a row-axis grid placement
203    #[inline(always)]
204    pub(crate) fn resolve_row_names(&self, line: &Line<GridPlacement<S>>) -> Line<NonNamedGridPlacement> {
205        self.resolve_line_names(line, GridAreaAxis::Row)
206    }
207
208    /// Resolve named lines for both the `start` and `end` of a column-axis grid placement
209    #[inline(always)]
210    pub(crate) fn resolve_column_names(&self, line: &Line<GridPlacement<S>>) -> Line<NonNamedGridPlacement> {
211        self.resolve_line_names(line, GridAreaAxis::Column)
212    }
213
214    /// Resolve named lines for both the `start` and `end` of a grid placement
215    #[inline(always)]
216    pub(crate) fn resolve_line_names(
217        &self,
218        line: &Line<GridPlacement<S>>,
219        axis: GridAreaAxis,
220    ) -> Line<NonNamedGridPlacement> {
221        let start_holder;
222        let start_line_resolved = if let GridPlacement::NamedLine(name, idx) = &line.start {
223            start_holder =
224                GridPlacement::Line(self.find_line_index(name, *idx as i32, axis, GridAreaEnd::Start, &|lines| lines));
225            &start_holder
226        } else {
227            &line.start
228        };
229
230        let end_holder;
231        let end_line_resolved = if let GridPlacement::NamedLine(name, idx) = &line.end {
232            end_holder =
233                GridPlacement::Line(self.find_line_index(name, *idx as i32, axis, GridAreaEnd::End, &|lines| lines));
234            &end_holder
235        } else {
236            &line.end
237        };
238
239        // If both the *-start and *-end values of its grid-placement properties specify a line, its grid span is implicit.
240        // If it has an explicit span value, its grid span is explicit.
241        // Otherwise, its grid span is automatic:
242        //   - if it is subgridded in that axis, its grid span is determined from its <line-name-list>;
243        //   - otherwise its grid span is 1.
244        //
245        // <https://drafts.csswg.org/css-grid-2/#grid-span>
246        match (&start_line_resolved, &end_line_resolved) {
247            (GridPlacement::Line(start_line), GridPlacement::NamedSpan(name, idx)) => {
248                let explicit_track_count = match axis {
249                    GridAreaAxis::Row => self.explicit_row_count as i32,
250                    GridAreaAxis::Column => self.explicit_column_count as i32,
251                };
252                let normalized_start_line = if start_line.as_i16() > 0 {
253                    start_line.as_i16() as u32
254                } else {
255                    (explicit_track_count + 1 + start_line.as_i16() as i32).max(0) as u32
256                };
257                let end_line = self.find_line_index(name, *idx as i32, axis, GridAreaEnd::End, &|lines| {
258                    let point = lines.partition_point(|line| *line <= normalized_start_line);
259                    &lines[point..]
260                });
261                Line { start: NonNamedGridPlacement::Line(*start_line), end: NonNamedGridPlacement::Line(end_line) }
262            }
263            (GridPlacement::NamedSpan(name, idx), GridPlacement::Line(end_line)) => {
264                let explicit_track_count = match axis {
265                    GridAreaAxis::Row => self.explicit_row_count as i32,
266                    GridAreaAxis::Column => self.explicit_column_count as i32,
267                };
268                let normalized_end_line = if end_line.as_i16() > 0 {
269                    end_line.as_i16() as u32
270                } else {
271                    (explicit_track_count + 1 + end_line.as_i16() as i32).max(0) as u32
272                };
273                let start_line = self.find_line_index(name, *idx as i32, axis, GridAreaEnd::Start, &|lines| {
274                    let point = lines.partition_point(|line| *line < normalized_end_line);
275                    &lines[..point]
276                });
277                Line { start: NonNamedGridPlacement::Line(start_line), end: NonNamedGridPlacement::Line(*end_line) }
278            }
279            (start, end) => Line {
280                start: match start {
281                    GridPlacement::Auto => NonNamedGridPlacement::Auto,
282                    GridPlacement::Line(grid_line) => NonNamedGridPlacement::Line(*grid_line),
283                    GridPlacement::Span(span) => NonNamedGridPlacement::Span(*span),
284                    GridPlacement::NamedSpan(_, _) => NonNamedGridPlacement::Span(1),
285                    _ => unreachable!(),
286                },
287                end: match end {
288                    GridPlacement::Auto => NonNamedGridPlacement::Auto,
289                    GridPlacement::Line(grid_line) => NonNamedGridPlacement::Line(*grid_line),
290                    GridPlacement::Span(span) => NonNamedGridPlacement::Span(*span),
291                    GridPlacement::NamedSpan(_, _) => NonNamedGridPlacement::Span(1),
292                    _ => unreachable!(),
293                },
294            },
295        }
296    }
297
298    /// Resolve the grid line for a named grid line or span
299    fn find_line_index(
300        &self,
301        name: &S,
302        idx: i32,
303        axis: GridAreaAxis,
304        end: GridAreaEnd,
305        filter_lines: &dyn Fn(&[u32]) -> &[u32],
306    ) -> GridLine {
307        let name = name.as_ref();
308        let mut idx = idx;
309        let explicit_track_count = match axis {
310            GridAreaAxis::Row => self.explicit_row_count as i32,
311            GridAreaAxis::Column => self.explicit_column_count as i32,
312        };
313
314        // An index of 0 is used to represent "no index specified".
315        if idx == 0 {
316            idx = 1;
317        }
318
319        fn get_line(lines: &[u32], explicit_track_count: i32, idx: i32) -> i16 {
320            let abs_idx = idx.unsigned_abs() as usize;
321            let line = if abs_idx <= lines.len() {
322                if idx > 0 {
323                    lines[abs_idx - 1] as i64
324                } else {
325                    lines[lines.len() - abs_idx] as i64
326                }
327            } else {
328                let remaining_lines = (abs_idx - lines.len()) as i64 * idx.signum() as i64;
329                if idx > 0 {
330                    explicit_track_count as i64 + 1 + remaining_lines
331                } else {
332                    -(explicit_track_count as i64 + 1 + remaining_lines)
333                }
334            };
335            line.clamp(i16::MIN as i64, i16::MAX as i64) as i16
336        }
337
338        // Lookup lines
339        let line_lookup = match axis {
340            GridAreaAxis::Row => &self.row_lines,
341            GridAreaAxis::Column => &self.column_lines,
342        };
343        if let Some(lines) = line_lookup.get(name) {
344            return GridLine::from(get_line(filter_lines(lines), explicit_track_count, idx));
345        } else {
346            // TODO: eliminate string allocations
347            match end {
348                GridAreaEnd::Start => {
349                    let implicit_name = format!("{name}-start");
350                    if let Some(lines) = line_lookup.get(&*implicit_name) {
351                        // println!("IMPLICIT COL {implicit_name}");
352                        return GridLine::from(get_line(filter_lines(lines), explicit_track_count, idx));
353                    }
354                }
355                GridAreaEnd::End => {
356                    let implicit_name = format!("{name}-end");
357                    if let Some(lines) = line_lookup.get(&*implicit_name) {
358                        // println!("IMPLICIT ROW {implicit_name}");
359                        return GridLine::from(get_line(filter_lines(lines), explicit_track_count, idx));
360                    }
361                }
362            }
363        }
364
365        // The CSS Grid specification has a weird quirk where it matches non-existent line names
366        // to the first (positive) implicit line in the grid
367        //
368        // We add/subtract 2 to the explicit track count because (in each axis) a grid has one more explicit
369        // grid line than it has tracks. And the fallback line is the line *after* that.
370        //
371        // See: <https://github.com/w3c/csswg-drafts/issues/966#issuecomment-277042153>
372        let line = if idx > 0 {
373            explicit_track_count as i64 + 1 + idx as i64
374        } else {
375            -(explicit_track_count as i64 + 1 + idx as i64)
376        };
377
378        GridLine::from(line.clamp(i16::MIN as i64, i16::MAX as i64) as i16)
379    }
380
381    /// Get the number of columns defined by the grid areas
382    pub(crate) fn area_column_count(&self) -> u16 {
383        self.area_column_count
384    }
385
386    /// Get the number of rows defined by the grid areas
387    pub(crate) fn area_row_count(&self) -> u16 {
388        self.area_row_count
389    }
390
391    /// Set the number of columns in the explicit grid
392    pub(crate) fn set_explicit_column_count(&mut self, count: u16) {
393        self.explicit_column_count = count;
394    }
395
396    /// Set the number of rows in the explicit grid
397    pub(crate) fn set_explicit_row_count(&mut self, count: u16) {
398        self.explicit_row_count = count;
399    }
400}
401
402impl<S: CheapCloneStr> Debug for NamedLineResolver<S> {
403    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
404        writeln!(f, "Grid Areas:")?;
405        for area in self.areas.values() {
406            writeln!(
407                f,
408                "{}: row:{}/{} col: {}/{}",
409                area.name.as_ref(),
410                area.row_start,
411                area.row_end,
412                area.column_start,
413                area.column_end
414            )?;
415        }
416
417        writeln!(f, "Grid Rows:")?;
418        for (name, lines) in self.row_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        writeln!(f, "Grid Columns:")?;
427        for (name, lines) in self.column_lines.iter() {
428            write!(f, "{}: ", name.0.as_ref())?;
429            for line in lines {
430                write!(f, "{line}  ")?;
431            }
432            writeln!(f)?;
433        }
434
435        Ok(())
436    }
437}
438
439#[cfg(test)]
440mod tests {
441    use super::*;
442    use crate::style::GenericGridPlacement;
443    use crate::sys::DefaultCheapStr;
444    use crate::GridTemplateAreas;
445    use crate::Style;
446
447    fn resolver(explicit_track_count: u16) -> NamedLineResolver<DefaultCheapStr> {
448        let mut resolver = NamedLineResolver::new(&Style::DEFAULT, 0, 0);
449        resolver.set_explicit_column_count(explicit_track_count);
450        resolver
451    }
452
453    fn resolved_start_line(
454        resolver: &NamedLineResolver<DefaultCheapStr>,
455        placement: GridPlacement<DefaultCheapStr>,
456    ) -> i16 {
457        let resolved = resolver.resolve_column_names(&Line { start: placement, end: GridPlacement::Auto });
458        match resolved.start {
459            GenericGridPlacement::Line(line) => line.as_i16(),
460            _ => panic!("expected a resolved line"),
461        }
462    }
463
464    #[test]
465    fn extreme_missing_named_line_indices_do_not_overflow() {
466        let resolver = resolver(10_000);
467        assert_eq!(
468            resolved_start_line(&resolver, GridPlacement::NamedLine(DefaultCheapStr::from("missing"), i16::MAX)),
469            i16::MAX
470        );
471        assert_eq!(
472            resolved_start_line(&resolver, GridPlacement::NamedLine(DefaultCheapStr::from("missing"), i16::MIN)),
473            22_767
474        );
475    }
476
477    #[test]
478    fn large_named_span_does_not_wrap_negative() {
479        let resolver = resolver(10_000);
480        let resolved = resolver.resolve_column_names(&Line {
481            start: GridPlacement::Line(GridLine::from(1)),
482            end: GridPlacement::NamedSpan(DefaultCheapStr::from("missing"), u16::MAX),
483        });
484        match resolved.end {
485            GenericGridPlacement::Line(line) => assert_eq!(line.as_i16(), i16::MAX),
486            _ => panic!("expected a resolved line"),
487        }
488    }
489
490    #[test]
491    fn area_lines_saturate_when_converted_to_grid_lines() {
492        let style = Style {
493            grid_template_areas: Some(GridTemplateAreas {
494                areas: vec![GridTemplateArea {
495                    name: DefaultCheapStr::from("area"),
496                    row_start: 1,
497                    row_end: 2,
498                    column_start: u16::MAX,
499                    column_end: u16::MAX,
500                }],
501                row_count: 1,
502                column_count: u16::MAX,
503            }),
504            ..Style::DEFAULT
505        };
506        let resolver = NamedLineResolver::new(&style, 0, 0);
507        assert_eq!(
508            resolved_start_line(&resolver, GridPlacement::NamedLine(DefaultCheapStr::from("area-start"), 1)),
509            i16::MAX
510        );
511    }
512}
taffy/compute/grid/types/named.rs

taffy/compute/grid/types/
named.rs
