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, Line, NonNamedGridPlacement, RepetitionCount,
6};
7use core::{borrow::Borrow, cmp::Ordering, fmt::Debug};
8
9use super::{GridLine, OriginZeroLine, MAX_GRID_TRACKS};
10use crate::geometry::AbsoluteAxis;
11use crate::sys::DefaultCheapStr;
12use crate::sys::{Map, Vec};
13use smallvec::{smallvec, SmallVec};
14
15/// Wrap an `AsRef<str>` type with a type which implements Hash by first
16/// deferring to the underlying `&str`'s implementation of Hash.
17#[derive(Debug, Clone)]
18pub(crate) struct StrHasher<T: CheapCloneStr>(pub T);
19impl<T: CheapCloneStr> PartialOrd for StrHasher<T> {
20    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
21        Some(self.cmp(other))
22    }
23}
24impl<T: CheapCloneStr> Ord for StrHasher<T> {
25    fn cmp(&self, other: &Self) -> Ordering {
26        self.0.as_ref().cmp(other.0.as_ref())
27    }
28}
29impl<T: CheapCloneStr> PartialEq for StrHasher<T> {
30    fn eq(&self, other: &Self) -> bool {
31        other.0.as_ref() == self.0.as_ref()
32    }
33}
34impl<T: CheapCloneStr> Eq for StrHasher<T> {}
35#[cfg(feature = "std")]
36impl<T: CheapCloneStr> std::hash::Hash for StrHasher<T> {
37    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
38        self.0.as_ref().hash(state)
39    }
40}
41impl<T: CheapCloneStr> Borrow<str> for StrHasher<T> {
42    fn borrow(&self) -> &str {
43        self.0.as_ref()
44    }
45}
46
47/// The one-indexed line positions of a single grid line name. Inline capacity of 4 keeps the
48/// type the same size as `Vec<u32>` (24 bytes) while avoiding a heap allocation for names
49/// mapping to at most 4 lines (the common case)
50pub(crate) type LinePositions = SmallVec<[u32; 4]>;
51
52/// Map from a grid line name to its one-indexed line positions
53type NamedGridLinesMap<S> = Map<StrHasher<S>, LinePositions>;
54
55/// The one-indexed positions of the first line that starts and the first line that ends a named grid area in
56/// each axis, i.e. the first line named `<area-name>-start`/`<area-name>-end` (explicitly or by
57/// `grid-template-areas`). A value of 0 means that there is no such line.
58#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
59pub(crate) struct AreaLines {
60    /// The first line that starts the area in the row axis
61    row_start: u32,
62    /// The first line that ends the area in the row axis
63    row_end: u32,
64    /// The first line that starts the area in the column axis
65    column_start: u32,
66    /// The first line that ends the area in the column axis
67    column_end: u32,
68}
69
70impl AreaLines {
71    /// The line for the passed edge of the area (if there is one)
72    fn line(&self, axis: GridAreaAxis, end: GridAreaEnd) -> Option<&u32> {
73        let line = match (axis, end) {
74            (GridAreaAxis::Row, GridAreaEnd::Start) => &self.row_start,
75            (GridAreaAxis::Row, GridAreaEnd::End) => &self.row_end,
76            (GridAreaAxis::Column, GridAreaEnd::Start) => &self.column_start,
77            (GridAreaAxis::Column, GridAreaEnd::End) => &self.column_end,
78        };
79        Some(line).filter(|line| **line != 0)
80    }
81
82    /// The line for the passed edge of the area (0 if there is none)
83    fn line_mut(&mut self, axis: GridAreaAxis, end: GridAreaEnd) -> &mut u32 {
84        match (axis, end) {
85            (GridAreaAxis::Row, GridAreaEnd::Start) => &mut self.row_start,
86            (GridAreaAxis::Row, GridAreaEnd::End) => &mut self.row_end,
87            (GridAreaAxis::Column, GridAreaEnd::Start) => &mut self.column_start,
88            (GridAreaAxis::Column, GridAreaEnd::End) => &mut self.column_end,
89        }
90    }
91}
92
93/// Map from the name of a grid area to the lines of its edges.
94///
95/// This is how the `<area-name>-start` and `<area-name>-end` line names that `grid-template-areas` implicitly
96/// generates are represented: storing them as line names would require allocating a string for each of them.
97pub(crate) type GridAreasMap<S> = Map<StrHasher<S>, AreaLines>;
98
99/// Split a line name of the form `<area-name>-start` or `<area-name>-end` into the area name and the edge
100fn split_area_edge_name(name: &str) -> Option<(&str, GridAreaEnd)> {
101    if let Some(area_name) = name.strip_suffix("-start") {
102        Some((area_name, GridAreaEnd::Start))
103    } else if let Some(area_name) = name.strip_suffix("-end") {
104        Some((area_name, GridAreaEnd::End))
105    } else {
106        None
107    }
108}
109
110/// Resolver for named placements in one grid axis
111struct NamedLineResolverAxis<'a, S: CheapCloneStr> {
112    /// Named lines and their one-indexed positions
113    lines: &'a NamedGridLinesMap<S>,
114    /// The edges of named grid areas (in both axes)
115    areas: &'a GridAreasMap<S>,
116    /// The axis being resolved
117    axis: GridAreaAxis,
118    /// Number of explicit tracks in this axis
119    explicit_track_count: u16,
120}
121
122/// Resolver that takes grid lines names and area names as input and can then be used to
123/// resolve line names of grid placement properties into line numbers.
124pub(crate) struct NamedLineResolver<S: CheapCloneStr> {
125    /// Map of row line names to line numbers. Each line name may correspond to multiple lines
126    /// so we store a `SmallVec`
127    row_lines: NamedGridLinesMap<S>,
128    /// Map of column line names to line numbers. Each line name may correspond to multiple lines
129    /// so we store a `SmallVec`
130    column_lines: NamedGridLinesMap<S>,
131    /// Map of area names to the lines of the area's edges
132    areas: GridAreasMap<S>,
133    /// Number of columns implied by grid area definitions
134    area_column_count: u16,
135    /// Number of rows implied by grid area definitions
136    area_row_count: u16,
137    /// The number of explicit columns in the grid. This is an *input* to the `NamedLineResolver` and is
138    /// used when computing the fallback line when a non-existent named line is specified.
139    explicit_column_count: u16,
140    /// The number of explicit rows in the grid. This is an *input* to the `NamedLineResolver` and is
141    /// used when computing the fallback line when a non-existent named line is specified.
142    explicit_row_count: u16,
143    /// The (1-indexed line number, name) pairs of every column line named in the track template,
144    /// in source order (excludes the implicit names generated by `grid-template-areas`)
145    column_line_name_pairs: Vec<(u32, S)>,
146    /// The (1-indexed line number, name) pairs of every row line named in the track template,
147    /// in source order (excludes the implicit names generated by `grid-template-areas`)
148    row_line_name_pairs: Vec<(u32, S)>,
149}
150
151/// Utility function to create or update an entry in a line name map
152///
153/// `areas` must already contain the edges of the areas defined by `grid-template-areas`
154fn upsert_line_name_map<S: CheapCloneStr>(
155    map: &mut NamedGridLinesMap<S>,
156    areas: &mut GridAreasMap<S>,
157    axis: GridAreaAxis,
158    key: S,
159    value: u32,
160) {
161    // A line named `foo-start` or `foo-end` is also an edge of the (implicitly) named area `foo`. Record it as such
162    // if it is the first such line. If `foo` is also an area defined by `grid-template-areas`, then the line which
163    // that area generated also has this name.
164    let mut area_line = 0;
165    if let Some((area_name, end)) = split_area_edge_name(key.as_ref()) {
166        // The key is only created if the area is not already in the map
167        if !areas.contains_key(area_name) {
168            areas.insert(StrHasher(S::from(area_name)), AreaLines::default());
169        }
170        let edge = areas.get_mut(area_name).unwrap().line_mut(axis, end);
171        area_line = *edge;
172        *edge = if *edge == 0 { value } else { (*edge).min(value) };
173    }
174
175    map.entry(StrHasher(key)).and_modify(|lines| lines.push(value)).or_insert_with(|| {
176        // Until this entry is created, the only line that can have been recorded for this edge is the area's own
177        if area_line == 0 {
178            smallvec![value]
179        } else {
180            smallvec![area_line, value]
181        }
182    });
183}
184
185impl<S: CheapCloneStr> NamedLineResolverAxis<'_, S> {
186    /// The line for the passed edge of the named grid area in this axis (if there is one)
187    fn area_line(&self, area_name: &str, end: GridAreaEnd) -> Option<&u32> {
188        self.areas.get(area_name)?.line(self.axis, end)
189    }
190
191    /// Resolve named lines and spans into numeric placements
192    fn resolve_line_names(&self, line: &Line<GridPlacement<S>>) -> Line<NonNamedGridPlacement> {
193        let start_holder;
194        let start_line_resolved = if let GridPlacement::NamedLine(name, idx) = &line.start {
195            start_holder = GridPlacement::Line(self.find_named_line(name, *idx, GridAreaEnd::Start));
196            &start_holder
197        } else {
198            &line.start
199        };
200
201        let end_holder;
202        let end_line_resolved = if let GridPlacement::NamedLine(name, idx) = &line.end {
203            end_holder = GridPlacement::Line(self.find_named_line(name, *idx, GridAreaEnd::End));
204            &end_holder
205        } else {
206            &line.end
207        };
208
209        // If both the *-start and *-end values of its grid-placement properties specify a line, its grid span is implicit.
210        // If it has an explicit span value, its grid span is explicit.
211        // Otherwise, its grid span is automatic:
212        //   - if it is subgridded in that axis, its grid span is determined from its <line-name-list>;
213        //   - otherwise its grid span is 1.
214        //
215        // <https://drafts.csswg.org/css-grid-2/#grid-span>
216        match (&start_line_resolved, &end_line_resolved) {
217            (GridPlacement::Line(start_line), GridPlacement::NamedSpan(name, idx)) if start_line.as_i16() != 0 => {
218                let after_start_line = start_line.into_origin_zero_line(self.explicit_track_count) + 1;
219                let end_line =
220                    self.nth_line_forwards(self.lines_named(name.as_ref()), after_start_line, (*idx).max(1) as i32);
221                Line {
222                    start: NonNamedGridPlacement::Line(*start_line),
223                    end: NonNamedGridPlacement::Line(end_line.into_grid_line(self.explicit_track_count)),
224                }
225            }
226            (GridPlacement::NamedSpan(name, idx), GridPlacement::Line(end_line)) if end_line.as_i16() != 0 => {
227                let before_end_line = end_line.into_origin_zero_line(self.explicit_track_count) - 1;
228                let start_line =
229                    self.nth_line_backwards(self.lines_named(name.as_ref()), before_end_line, (*idx).max(1) as i32);
230                Line {
231                    start: NonNamedGridPlacement::Line(start_line.into_grid_line(self.explicit_track_count)),
232                    end: NonNamedGridPlacement::Line(*end_line),
233                }
234            }
235            (start, end) => Line {
236                start: match start {
237                    GridPlacement::Auto => NonNamedGridPlacement::Auto,
238                    GridPlacement::Line(grid_line) => NonNamedGridPlacement::Line(*grid_line),
239                    GridPlacement::Span(span) => NonNamedGridPlacement::Span(*span),
240                    GridPlacement::NamedSpan(_, _) => NonNamedGridPlacement::Span(1),
241                    _ => unreachable!(),
242                },
243                end: match end {
244                    GridPlacement::Auto => NonNamedGridPlacement::Auto,
245                    GridPlacement::Line(grid_line) => NonNamedGridPlacement::Line(*grid_line),
246                    GridPlacement::Span(span) => NonNamedGridPlacement::Span(*span),
247                    GridPlacement::NamedSpan(_, _) => NonNamedGridPlacement::Span(1),
248                    _ => unreachable!(),
249                },
250            },
251        }
252    }
253
254    /// Resolve the grid line for a named grid line (`<custom-ident>` or `<integer> <custom-ident>`).
255    /// An index of 0 is used to represent "no index specified".
256    ///
257    /// <https://drafts.csswg.org/css-grid-2/#line-placement>
258    fn find_named_line(&self, name: &S, idx: i16, end: GridAreaEnd) -> GridLine {
259        let name = name.as_ref();
260
261        // A `<custom-ident>` on its own first attempts to match the edge of a named grid area:
262        // the first line named `<custom-ident>-start` (or `<custom-ident>-end` for an end line).
263        // Otherwise it is treated as if the integer 1 had been specified along with it.
264        if idx == 0 {
265            if let Some(first_line) = self.area_line(name, end) {
266                return OriginZeroLine::clamped(oz_line(*first_line)).into_grid_line(self.explicit_track_count);
267            }
268        }
269
270        let lines = self.lines_named(name);
271        let line = if idx >= 0 {
272            self.nth_line_forwards(lines, OriginZeroLine(0), (idx as i32).max(1))
273        } else {
274            self.nth_line_backwards(lines, self.last_explicit_line(), -(idx as i32))
275        };
276        line.into_grid_line(self.explicit_track_count)
277    }
278
279    /// The sorted line numbers of the lines with the passed name
280    ///
281    /// A line generated by a grid area is included in the lines of its name if any line has been explicitly
282    /// given the same name. Otherwise it is found from the area's edges.
283    fn lines_named(&self, name: &str) -> &[u32] {
284        match self.lines.get(name) {
285            Some(lines) => lines.as_slice(),
286            None => split_area_edge_name(name)
287                .and_then(|(area_name, area_end)| self.area_line(area_name, area_end))
288                .map(core::slice::from_ref)
289                .unwrap_or(&[]),
290        }
291    }
292
293    /// The line at the end edge of the explicit grid
294    fn last_explicit_line(&self) -> OriginZeroLine {
295        OriginZeroLine(self.explicit_track_count as i16)
296    }
297
298    /// Find the `n`th line in `lines` (searching forwards) that is not before `first_line`.
299    ///
300    /// If there are not enough such lines, then all implicit lines after the explicit grid are
301    /// assumed to be in `lines` for the purpose of counting
302    ///
303    /// <https://drafts.csswg.org/css-grid-2/#grid-placement-int>
304    fn nth_line_forwards(&self, lines: &[u32], first_line: OriginZeroLine, n: i32) -> OriginZeroLine {
305        let first_line = first_line.0.max(0) as i32;
306        let lines = &lines[lines.partition_point(|line| oz_line(*line) < first_line)..];
307        let line = match lines.get(n as usize - 1) {
308            Some(line) => oz_line(*line),
309            None => first_line.max(self.last_explicit_line().0 as i32 + 1) + (n - lines.len() as i32) - 1,
310        };
311        OriginZeroLine::clamped(line)
312    }
313
314    /// Find the `n`th line in `lines` (searching backwards) that is not after `last_line`.
315    ///
316    /// If there are not enough such lines, then all implicit lines before the explicit grid are
317    /// assumed to be in `lines` for the purpose of counting
318    ///
319    /// <https://drafts.csswg.org/css-grid-2/#grid-placement-int>
320    fn nth_line_backwards(&self, lines: &[u32], last_line: OriginZeroLine, n: i32) -> OriginZeroLine {
321        let last_line = last_line.0.min(self.last_explicit_line().0) as i32;
322        let lines = &lines[..lines.partition_point(|line| oz_line(*line) <= last_line)];
323        let line = match lines.len().checked_sub(n as usize) {
324            Some(index) => oz_line(lines[index]),
325            None => last_line.min(-1) - (n - lines.len() as i32) + 1,
326        };
327        OriginZeroLine::clamped(line)
328    }
329}
330
331/// The named line maps store lines as 1-based "CSS Grid Line" numbers (which are always within the
332/// explicit grid). Convert one to OriginZero coordinates.
333fn oz_line(line: u32) -> i32 {
334    line as i32 - 1
335}
336
337impl<S: CheapCloneStr> NamedLineResolver<S> {
338    /// Create and initialise a new `NamedLineResolver`
339    pub(crate) fn new(
340        style: &impl GridContainerStyle<CustomIdent = S>,
341        column_auto_repetitions: u16,
342        row_auto_repetitions: u16,
343    ) -> Self {
344        let mut column_lines: NamedGridLinesMap<S> = Map::new();
345        let mut row_lines: NamedGridLinesMap<S> = Map::new();
346        let mut areas: GridAreasMap<S> = Map::new();
347
348        let mut column_line_name_pairs: Vec<(u32, S)> = Vec::new();
349        let mut row_line_name_pairs: Vec<(u32, S)> = Vec::new();
350
351        // The size of the area template may be larger than the extents of the named areas
352        // due to unnamed (`.`) cells, so it is taken from the style rather than being derived
353        // from the areas themselves.
354        let area_column_count = style.grid_template_area_column_count();
355        let area_row_count = style.grid_template_area_row_count();
356        if let Some(area_iter) = style.grid_template_areas() {
357            for area in area_iter.into_iter() {
358                let lines = AreaLines {
359                    row_start: area.row_start as u32,
360                    row_end: area.row_end as u32,
361                    column_start: area.column_start as u32,
362                    column_end: area.column_end as u32,
363                };
364                areas.insert(StrHasher(area.name.clone()), lines);
365            }
366        }
367
368        let mut current_line = 0;
369        if let Some(mut column_tracks) = style.grid_template_columns() {
370            if let Some(column_line_names_iter) = style.grid_template_column_names() {
371                for line_names in column_line_names_iter {
372                    current_line += 1;
373                    for line_name in line_names.into_iter() {
374                        column_line_name_pairs.push((current_line, line_name.clone()));
375                        upsert_line_name_map(
376                            &mut column_lines,
377                            &mut areas,
378                            GridAreaAxis::Column,
379                            line_name.clone(),
380                            current_line,
381                        );
382                    }
383
384                    if let Some(GenericGridTemplateComponent::Repeat(repeat)) = column_tracks.next() {
385                        let repeat_count = match repeat.count() {
386                            RepetitionCount::Count(count) => count,
387                            RepetitionCount::AutoFill | RepetitionCount::AutoFit => column_auto_repetitions,
388                        };
389
390                        // Line name sets are positional: set `i` names the `i`th line of each
391                        // repetition, and the final line name set of each repetition collapses
392                        // with the first line name set of the following one. An empty list means
393                        // the repetition's lines are unnamed; any other length must be exactly
394                        // `track_count + 1` (one set per line, including both edge lines).
395                        let line_name_set_count = repeat.lines_names().len() as u32;
396                        let lines_per_repetition = repeat.track_count() as u32;
397                        assert!(
398                            line_name_set_count == 0 || line_name_set_count == lines_per_repetition + 1,
399                            "grid template repetition must have no line name sets or exactly track count + 1 of them ({} tracks but {} line name sets)",
400                            lines_per_repetition,
401                            line_name_set_count,
402                        );
403
404                        for _ in 0..repeat_count {
405                            for (line, line_name_set) in (current_line..).zip(repeat.lines_names()) {
406                                for line_name in line_name_set {
407                                    column_line_name_pairs.push((line, line_name.clone()));
408                                    upsert_line_name_map(
409                                        &mut column_lines,
410                                        &mut areas,
411                                        GridAreaAxis::Column,
412                                        line_name.clone(),
413                                        line,
414                                    );
415                                }
416                            }
417                            current_line += lines_per_repetition;
418
419                            // Names for lines beyond the maximum track limit are never resolvable:
420                            // stop generating them (the explicit grid is clamped to MAX_GRID_TRACKS)
421                            if current_line > MAX_GRID_TRACKS as u32 {
422                                break;
423                            }
424                        }
425                        // Last line name set collapses with following line name set
426                        if repeat_count > 0 {
427                            current_line = current_line.saturating_sub(1);
428                        }
429                    }
430                }
431            }
432        }
433
434        let mut current_line = 0;
435        if let Some(mut row_tracks) = style.grid_template_rows() {
436            if let Some(row_line_names_iter) = style.grid_template_row_names() {
437                for line_names in row_line_names_iter {
438                    current_line += 1;
439                    for line_name in line_names.into_iter() {
440                        row_line_name_pairs.push((current_line, line_name.clone()));
441                        upsert_line_name_map(
442                            &mut row_lines,
443                            &mut areas,
444                            GridAreaAxis::Row,
445                            line_name.clone(),
446                            current_line,
447                        );
448                    }
449
450                    if let Some(GenericGridTemplateComponent::Repeat(repeat)) = row_tracks.next() {
451                        let repeat_count = match repeat.count() {
452                            RepetitionCount::Count(count) => count,
453                            RepetitionCount::AutoFill | RepetitionCount::AutoFit => row_auto_repetitions,
454                        };
455
456                        // Line name sets are positional: set `i` names the `i`th line of each
457                        // repetition, and the final line name set of each repetition collapses
458                        // with the first line name set of the following one. An empty list means
459                        // the repetition's lines are unnamed; any other length must be exactly
460                        // `track_count + 1` (one set per line, including both edge lines).
461                        let line_name_set_count = repeat.lines_names().len() as u32;
462                        let lines_per_repetition = repeat.track_count() as u32;
463                        assert!(
464                            line_name_set_count == 0 || line_name_set_count == lines_per_repetition + 1,
465                            "grid template repetition must have no line name sets or exactly track count + 1 of them ({} tracks but {} line name sets)",
466                            lines_per_repetition,
467                            line_name_set_count,
468                        );
469
470                        for _ in 0..repeat_count {
471                            for (line, line_name_set) in (current_line..).zip(repeat.lines_names()) {
472                                for line_name in line_name_set {
473                                    row_line_name_pairs.push((line, line_name.clone()));
474                                    upsert_line_name_map(
475                                        &mut row_lines,
476                                        &mut areas,
477                                        GridAreaAxis::Row,
478                                        line_name.clone(),
479                                        line,
480                                    );
481                                }
482                            }
483                            current_line += lines_per_repetition;
484
485                            // Names for lines beyond the maximum track limit are never resolvable:
486                            // stop generating them (the explicit grid is clamped to MAX_GRID_TRACKS)
487                            if current_line > MAX_GRID_TRACKS as u32 {
488                                break;
489                            }
490                        }
491                        // Last line name set collapses with following line name set
492                        if repeat_count > 0 {
493                            current_line = current_line.saturating_sub(1);
494                        }
495                    }
496                }
497            }
498        }
499        // Sort and dedup lines for each column name
500        for lines in column_lines.values_mut() {
501            lines.sort_unstable();
502            lines.dedup();
503        }
504        // Sort and dedup lines for each row name
505        for lines in row_lines.values_mut() {
506            lines.sort_unstable();
507            lines.dedup();
508        }
509
510        Self {
511            area_column_count,
512            area_row_count,
513            explicit_column_count: 0, // Overwritten later
514            explicit_row_count: 0,    // Overwritten later
515            row_lines,
516            column_lines,
517            areas,
518            column_line_name_pairs,
519            row_line_name_pairs,
520        }
521    }
522
523    /// Build the per-line name groups of the explicit grid in the passed axis as a
524    /// [`GridLineNames`], with `repeat()`s expanded. Only names given explicitly in the track
525    /// template are included; the implicit `<name>-start`/`<name>-end` names generated by
526    /// `grid-template-areas` are omitted (matching the resolved value of
527    /// `grid-template-rows`/`grid-template-columns` in browsers) but remain resolvable for
528    /// placement via [`GridLineNames::resolve_line_names`].
529    ///
530    /// Line indices are relative to the explicit grid (line 0 = start of the first explicit track).
531    pub(crate) fn detailed_line_names(&self, axis: AbsoluteAxis) -> GridLineNames<S> {
532        let (pairs, explicit_track_count) = match axis {
533            AbsoluteAxis::Horizontal => (&self.column_line_name_pairs, self.explicit_column_count),
534            AbsoluteAxis::Vertical => (&self.row_line_name_pairs, self.explicit_row_count),
535        };
536
537        if pairs.is_empty() {
538            return GridLineNames::default();
539        }
540
541        // Stable sort by line number preserves the source order of names within each line
542        let mut sorted_pairs: Vec<&(u32, S)> = pairs.iter().collect();
543        sorted_pairs.sort_by_key(|(line, _)| *line);
544
545        let line_count = explicit_track_count as usize + 1;
546        let mut line_names = GridLineNames::with_capacity(sorted_pairs.len(), line_count + 1);
547        let mut pair_iter = sorted_pairs.into_iter().peekable();
548        for line in 1..=(line_count as u32) {
549            line_names.start_line();
550            while let Some(&&(pair_line, ref name)) = pair_iter.peek() {
551                if pair_line != line {
552                    break;
553                }
554                pair_iter.next();
555                if !line_names.current_line_contains(name.as_ref()) {
556                    line_names.push_name(name.clone());
557                }
558            }
559        }
560        line_names
561    }
562
563    /// Resolve named lines for both the `start` and `end` of a row-axis grid placement
564    #[inline(always)]
565    pub(crate) fn resolve_row_names(&self, line: &Line<GridPlacement<S>>) -> Line<NonNamedGridPlacement> {
566        self.resolve_line_names(line, GridAreaAxis::Row)
567    }
568
569    /// Resolve named lines for both the `start` and `end` of a column-axis grid placement
570    #[inline(always)]
571    pub(crate) fn resolve_column_names(&self, line: &Line<GridPlacement<S>>) -> Line<NonNamedGridPlacement> {
572        self.resolve_line_names(line, GridAreaAxis::Column)
573    }
574
575    /// Resolve named lines for both the `start` and `end` of a grid placement
576    #[inline(always)]
577    pub(crate) fn resolve_line_names(
578        &self,
579        line: &Line<GridPlacement<S>>,
580        axis: GridAreaAxis,
581    ) -> Line<NonNamedGridPlacement> {
582        let (lines, explicit_track_count) = match axis {
583            GridAreaAxis::Row => (&self.row_lines, self.explicit_row_count),
584            GridAreaAxis::Column => (&self.column_lines, self.explicit_column_count),
585        };
586        NamedLineResolverAxis { lines, areas: &self.areas, axis, explicit_track_count }.resolve_line_names(line)
587    }
588
589    /// Move the row and column line-name maps into the detailed grid information, and return the grid area map
590    /// for the same purpose
591    pub(crate) fn populate_detailed_line_resolvers(
592        self,
593        rows: &mut GridLineNames<S>,
594        columns: &mut GridLineNames<S>,
595    ) -> GridAreasMap<S> {
596        rows.resolver = self.row_lines;
597        columns.resolver = self.column_lines;
598        self.areas
599    }
600
601    /// Get the number of columns defined by the grid areas
602    pub(crate) fn area_column_count(&self) -> u16 {
603        self.area_column_count
604    }
605
606    /// Get the number of rows defined by the grid areas
607    pub(crate) fn area_row_count(&self) -> u16 {
608        self.area_row_count
609    }
610
611    /// Set the number of columns in the explicit grid
612    pub(crate) fn set_explicit_column_count(&mut self, count: u16) {
613        self.explicit_column_count = count;
614    }
615
616    /// Set the number of rows in the explicit grid
617    pub(crate) fn set_explicit_row_count(&mut self, count: u16) {
618        self.explicit_row_count = count;
619    }
620}
621
622impl<S: CheapCloneStr> Debug for NamedLineResolver<S> {
623    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
624        writeln!(f, "Grid Areas (row-start / column-start / row-end / column-end):")?;
625        for (name, area) in self.areas.iter() {
626            let AreaLines { row_start, column_start, row_end, column_end } = area;
627            writeln!(f, "{}: {row_start} / {column_start} / {row_end} / {column_end}", name.0.as_ref())?;
628        }
629
630        writeln!(f, "Grid Rows:")?;
631        for (name, lines) in self.row_lines.iter() {
632            write!(f, "{}: ", name.0.as_ref())?;
633            for line in lines {
634                write!(f, "{line}  ")?;
635            }
636            writeln!(f)?;
637        }
638
639        writeln!(f, "Grid Columns:")?;
640        for (name, lines) in self.column_lines.iter() {
641            write!(f, "{}: ", name.0.as_ref())?;
642            for line in lines {
643                write!(f, "{line}  ")?;
644            }
645            writeln!(f)?;
646        }
647
648        Ok(())
649    }
650}
651
652/// The names of each explicit grid line in a single axis, stored in CSR (compressed sparse
653/// row) format: a single flat `Vec` of names plus a `Vec` of offsets into it (one more offset
654/// than there are lines). The names of line `i` (0-indexed) are `names[offsets[i]..offsets[i + 1]]`.
655///
656/// Line indices here are relative to the explicit grid;
657/// [`DetailedGridTracksInfo`](crate::DetailedGridTracksInfo) provides accessors with indices
658/// relative to the full grid (including implicit tracks).
659///
660/// Iterate over per-line name groups with [`GridLineNames::iter`], or access a single line's
661/// names with [`GridLineNames::line`]. A grid with no named lines is represented by two empty
662/// `Vec`s (see [`GridLineNames::is_empty`]).
663#[derive(Debug, Clone, PartialEq, Default)]
664pub struct GridLineNames<S: CheapCloneStr = DefaultCheapStr> {
665    /// The names of every grid line in the axis, concatenated in line order
666    names: Vec<S>,
667    /// Offsets into `names`: line `i`'s names are `names[offsets[i]..offsets[i + 1]]`.
668    /// Either empty (no named lines) or of length `line count + 1`.
669    offsets: Vec<u32>,
670    /// Named line lookup used to resolve arbitrary grid placements
671    resolver: NamedGridLinesMap<S>,
672}
673
674impl<S: CheapCloneStr> GridLineNames<S> {
675    /// Create an empty `GridLineNames` with pre-allocated capacity
676    pub(crate) fn with_capacity(name_capacity: usize, offset_capacity: usize) -> Self {
677        let mut offsets = Vec::with_capacity(offset_capacity);
678        offsets.push(0);
679        Self { names: Vec::with_capacity(name_capacity), offsets, resolver: Map::new() }
680    }
681
682    /// Start a new (initially empty) line
683    pub(crate) fn start_line(&mut self) {
684        self.offsets.push(self.names.len() as u32);
685    }
686
687    /// Append a name to the current (last) line
688    pub(crate) fn push_name(&mut self, name: S) {
689        self.names.push(name);
690        *self.offsets.last_mut().unwrap() = self.names.len() as u32;
691    }
692
693    /// Whether the current (last) line already contains the passed name
694    pub(crate) fn current_line_contains(&self, name: &str) -> bool {
695        self.line(self.line_count().wrapping_sub(1)).iter().any(|n| n.as_ref() == name)
696    }
697
698    /// Resolve named lines and spans using the retained line-name map and the passed grid area map
699    pub(crate) fn resolve_line_names(
700        &self,
701        line: &Line<GridPlacement<S>>,
702        areas: &GridAreasMap<S>,
703        axis: GridAreaAxis,
704        explicit_track_count: u16,
705    ) -> Line<NonNamedGridPlacement> {
706        NamedLineResolverAxis { lines: &self.resolver, areas, axis, explicit_track_count }.resolve_line_names(line)
707    }
708
709    /// Whether the axis has any named lines at all
710    pub fn is_empty(&self) -> bool {
711        self.names.is_empty()
712    }
713
714    /// The number of grid lines represented (zero if the grid has no named lines)
715    pub fn line_count(&self) -> usize {
716        self.offsets.len().saturating_sub(1)
717    }
718
719    /// The names of the line with the passed 0-indexed line index.
720    /// Returns an empty slice if the line has no names or the index is out of range.
721    pub fn line(&self, line_index: usize) -> &[S] {
722        match (self.offsets.get(line_index), self.offsets.get(line_index + 1)) {
723            (Some(&start), Some(&end)) => &self.names[start as usize..end as usize],
724            _ => &[],
725        }
726    }
727
728    /// Iterate over the name group (`&[S]`) of each grid line in line order
729    pub fn iter(&self) -> GridLineNamesIter<'_, S> {
730        self.iter_padded(0, 0)
731    }
732
733    /// Iterate over the name group (`&[S]`) of each grid line in line order, additionally
734    /// yielding `leading_empty` empty groups before the stored lines and `trailing_empty`
735    /// empty groups after them (representing unnamed implicit grid lines)
736    pub(crate) fn iter_padded(&self, leading_empty: usize, trailing_empty: usize) -> GridLineNamesIter<'_, S> {
737        GridLineNamesIter { names: &self.names, offsets: self.offsets.windows(2), leading_empty, trailing_empty }
738    }
739}
740
741impl<'a, S: CheapCloneStr> IntoIterator for &'a GridLineNames<S> {
742    type Item = &'a [S];
743    type IntoIter = GridLineNamesIter<'a, S>;
744    fn into_iter(self) -> Self::IntoIter {
745        self.iter()
746    }
747}
748
749/// Iterator over the per-line name groups of a [`GridLineNames`]. Yields one `&[S]` per grid
750/// line (which is empty for unnamed lines)
751#[derive(Debug, Clone)]
752pub struct GridLineNamesIter<'a, S: CheapCloneStr> {
753    /// The flat name storage being iterated over
754    names: &'a [S],
755    /// Iterator over adjacent pairs of offsets into `names`
756    offsets: core::slice::Windows<'a, u32>,
757    /// Number of (unnamed, implicit) lines remaining before the stored lines
758    leading_empty: usize,
759    /// Number of (unnamed, implicit) lines remaining after the stored lines
760    trailing_empty: usize,
761}
762
763impl<'a, S: CheapCloneStr> Iterator for GridLineNamesIter<'a, S> {
764    type Item = &'a [S];
765
766    fn next(&mut self) -> Option<Self::Item> {
767        if self.leading_empty > 0 {
768            self.leading_empty -= 1;
769            return Some(&[]);
770        }
771        if let Some(window) = self.offsets.next() {
772            return Some(&self.names[window[0] as usize..window[1] as usize]);
773        }
774        if self.trailing_empty > 0 {
775            self.trailing_empty -= 1;
776            return Some(&[]);
777        }
778        None
779    }
780
781    fn size_hint(&self) -> (usize, Option<usize>) {
782        let len = self.leading_empty + self.offsets.len() + self.trailing_empty;
783        (len, Some(len))
784    }
785}
786
787impl<S: CheapCloneStr> ExactSizeIterator for GridLineNamesIter<'_, S> {}
788
789#[cfg(test)]
790mod tests {
791    use super::super::{MAX_OZ_LINE, MIN_OZ_LINE};
792    use super::*;
793    use crate::style::GenericGridPlacement;
794    use crate::sys::DefaultCheapStr;
795    use crate::GridTemplateAreas;
796    use crate::Style;
797    use crate::{GridTemplateArea, NonNamedGridPlacement};
798
799    fn resolver(explicit_track_count: u16) -> NamedLineResolver<DefaultCheapStr> {
800        let mut resolver = NamedLineResolver::new(&Style::DEFAULT, 0, 0);
801        resolver.set_explicit_column_count(explicit_track_count);
802        resolver
803    }
804
805    fn resolved_start_line(
806        resolver: &NamedLineResolver<DefaultCheapStr>,
807        placement: GridPlacement<DefaultCheapStr>,
808    ) -> i16 {
809        let resolved = resolver.resolve_column_names(&Line { start: placement, end: GridPlacement::Auto });
810        match resolved.start {
811            GenericGridPlacement::Line(line) => line.as_i16(),
812            _ => panic!("expected a resolved line"),
813        }
814    }
815
816    #[test]
817    fn extreme_missing_named_line_indices_do_not_overflow() {
818        // Lines are clamped to the limits of the grid, in the same way as `GridLine::into_origin_zero_line`
819        let resolver = resolver(10_000);
820        assert_eq!(
821            resolved_start_line(&resolver, GridPlacement::NamedLine(DefaultCheapStr::from("missing"), i16::MAX)),
822            OriginZeroLine(MAX_OZ_LINE).into_grid_line(10_000).as_i16()
823        );
824        assert_eq!(
825            resolved_start_line(&resolver, GridPlacement::NamedLine(DefaultCheapStr::from("missing"), i16::MIN)),
826            OriginZeroLine(MIN_OZ_LINE).into_grid_line(10_000).as_i16()
827        );
828    }
829
830    #[test]
831    fn large_named_span_does_not_wrap_negative() {
832        let resolver = resolver(10_000);
833        let resolved = resolver.resolve_column_names(&Line {
834            start: GridPlacement::Line(GridLine::from(1)),
835            end: GridPlacement::NamedSpan(DefaultCheapStr::from("missing"), u16::MAX),
836        });
837        match resolved.end {
838            GenericGridPlacement::Line(line) => assert_eq!(line, OriginZeroLine(MAX_OZ_LINE).into_grid_line(10_000)),
839            _ => panic!("expected a resolved line"),
840        }
841    }
842
843    #[test]
844    fn area_lines_saturate_when_converted_to_grid_lines() {
845        let style = Style {
846            grid_template_areas: Some(GridTemplateAreas {
847                areas: vec![GridTemplateArea {
848                    name: DefaultCheapStr::from("area"),
849                    row_start: 1,
850                    row_end: 2,
851                    column_start: u16::MAX,
852                    column_end: u16::MAX,
853                }],
854                row_count: 1,
855                column_count: u16::MAX,
856            }),
857            ..Style::DEFAULT
858        };
859        let resolver = NamedLineResolver::new(&style, 0, 0);
860        assert_eq!(
861            resolved_start_line(&resolver, GridPlacement::NamedLine(DefaultCheapStr::from("area-start"), 1)),
862            OriginZeroLine(MAX_OZ_LINE).into_grid_line(0).as_i16()
863        );
864        assert_eq!(
865            resolved_start_line(&resolver, GridPlacement::NamedLine(DefaultCheapStr::from("area"), 0)),
866            OriginZeroLine(MAX_OZ_LINE).into_grid_line(0).as_i16()
867        );
868    }
869
870    /// A resolver for a grid with 4 explicit columns, the passed names for each of the 5 column lines, and a
871    /// single grid area named "area" which spans columns 2 and 3 (lines 2 to 4)
872    fn area_resolver(column_line_names: [&[&str]; 5]) -> NamedLineResolver<DefaultCheapStr> {
873        let style = Style {
874            grid_template_column_names: column_line_names
875                .iter()
876                .map(|names| names.iter().map(|name| DefaultCheapStr::from(*name)).collect())
877                .collect(),
878            grid_template_areas: Some(GridTemplateAreas {
879                areas: vec![GridTemplateArea {
880                    name: DefaultCheapStr::from("area"),
881                    row_start: 1,
882                    row_end: 2,
883                    column_start: 2,
884                    column_end: 4,
885                }],
886                row_count: 1,
887                column_count: 4,
888            }),
889            ..Style::DEFAULT
890        };
891        let mut resolver = NamedLineResolver::new(&style, 0, 0);
892        resolver.set_explicit_column_count(4);
893        resolver.set_explicit_row_count(1);
894        resolver
895    }
896
897    fn named_line(name: &str, index: i16) -> GridPlacement<DefaultCheapStr> {
898        GridPlacement::NamedLine(DefaultCheapStr::from(name), index)
899    }
900
901    fn resolved_end_line(
902        resolver: &NamedLineResolver<DefaultCheapStr>,
903        placement: GridPlacement<DefaultCheapStr>,
904    ) -> i16 {
905        let resolved = resolver.resolve_column_names(&Line { start: GridPlacement::Auto, end: placement });
906        match resolved.end {
907            GenericGridPlacement::Line(line) => line.as_i16(),
908            _ => panic!("expected a resolved line"),
909        }
910    }
911
912    #[test]
913    fn bare_ident_resolves_to_area_edge() {
914        let resolver = area_resolver([&[], &[], &[], &[], &[]]);
915        assert_eq!(resolved_start_line(&resolver, named_line("area", 0)), 2);
916        assert_eq!(resolved_end_line(&resolver, named_line("area", 0)), 4);
917
918        let rows = resolver.resolve_row_names(&Line { start: named_line("area", 0), end: named_line("area", 0) });
919        assert_eq!(rows.start, NonNamedGridPlacement::Line(GridLine::from(1)));
920        assert_eq!(rows.end, NonNamedGridPlacement::Line(GridLine::from(2)));
921    }
922
923    #[test]
924    fn bare_ident_resolves_to_edge_of_implicitly_named_area() {
925        let resolver = area_resolver([&[], &["foo-start"], &["foo-start"], &["foo-end"], &["foo-end"]]);
926        assert_eq!(resolved_start_line(&resolver, named_line("foo", 0)), 2);
927        assert_eq!(resolved_end_line(&resolver, named_line("foo", 0)), 4);
928    }
929
930    #[test]
931    fn area_edges_are_lines_named_with_start_and_end_suffixes() {
932        let resolver = area_resolver([&[], &[], &[], &[], &[]]);
933        assert_eq!(resolved_start_line(&resolver, named_line("area-start", 0)), 2);
934        assert_eq!(resolved_start_line(&resolver, named_line("area-start", 1)), 2);
935        assert_eq!(resolved_start_line(&resolver, named_line("area-end", 1)), 4);
936        assert_eq!(resolved_start_line(&resolver, named_line("area-end", -1)), 4);
937        // There is only one such line, so the second is the first implicit line after the grid
938        assert_eq!(resolved_start_line(&resolver, named_line("area-start", 2)), 6);
939    }
940
941    #[test]
942    fn area_edges_are_merged_with_explicitly_named_lines() {
943        // The area's start edge is line 2 and its end edge is line 4
944        let resolver = area_resolver([&["area-start"], &[], &["area-start"], &["area-end"], &["area-end"]]);
945        assert_eq!(resolved_start_line(&resolver, named_line("area-start", 1)), 1);
946        assert_eq!(resolved_start_line(&resolver, named_line("area-start", 2)), 2);
947        assert_eq!(resolved_start_line(&resolver, named_line("area-start", 3)), 3);
948        assert_eq!(resolved_start_line(&resolver, named_line("area-start", -1)), 3);
949        assert_eq!(resolved_start_line(&resolver, named_line("area-start", 4)), 6);
950        // The area's end edge has the same line number as an explicitly named line
951        assert_eq!(resolved_start_line(&resolver, named_line("area-end", 1)), 4);
952        assert_eq!(resolved_start_line(&resolver, named_line("area-end", 2)), 5);
953        assert_eq!(resolved_start_line(&resolver, named_line("area-end", 3)), 6);
954        // A bare ident matches the first line of the edge
955        assert_eq!(resolved_start_line(&resolver, named_line("area", 0)), 1);
956        assert_eq!(resolved_end_line(&resolver, named_line("area", 0)), 4);
957
958        let span = resolver.resolve_column_names(&Line {
959            start: GridPlacement::Line(GridLine::from(1)),
960            end: GridPlacement::NamedSpan(DefaultCheapStr::from("area-start"), 2),
961        });
962        assert_eq!(span.end, NonNamedGridPlacement::Line(GridLine::from(3)));
963    }
964
965    #[test]
966    fn area_edges_are_only_matched_by_bare_idents() {
967        let resolver = area_resolver([&[], &[], &[], &[], &[]]);
968        // There are no lines named "area", so these resolve to implicit lines after the grid
969        assert_eq!(resolved_start_line(&resolver, named_line("area", 1)), 6);
970        assert_eq!(resolved_start_line(&resolver, named_line("area", 2)), 7);
971
972        let span = resolver.resolve_column_names(&Line {
973            start: GridPlacement::Line(GridLine::from(1)),
974            end: GridPlacement::NamedSpan(DefaultCheapStr::from("area"), 0),
975        });
976        assert_eq!(span.end, NonNamedGridPlacement::Line(GridLine::from(6)));
977    }
978
979    #[test]
980    fn area_edge_is_the_first_line_with_the_edge_name() {
981        // Explicit lines named after the area's edges which come after the area's generated lines (lines 2 and
982        // 4) don't replace them
983        let resolver = area_resolver([&[], &[], &["area-start"], &[], &["area-end"]]);
984        assert_eq!(resolved_start_line(&resolver, named_line("area", 0)), 2);
985        assert_eq!(resolved_end_line(&resolver, named_line("area", 0)), 4);
986        assert_eq!(resolved_start_line(&resolver, named_line("area-start", 1)), 2);
987        assert_eq!(resolved_start_line(&resolver, named_line("area-start", 2)), 3);
988        assert_eq!(resolved_start_line(&resolver, named_line("area-end", 2)), 5);
989
990        // An explicit line with the same number as the generated line is the same line
991        let resolver = area_resolver([&[], &["area-start"], &[], &["area-end"], &[]]);
992        assert_eq!(resolved_start_line(&resolver, named_line("area", 0)), 2);
993        assert_eq!(resolved_end_line(&resolver, named_line("area", 0)), 4);
994        assert_eq!(resolved_start_line(&resolver, named_line("area-start", 1)), 2);
995        assert_eq!(resolved_start_line(&resolver, named_line("area-start", 2)), 6);
996        assert_eq!(resolved_start_line(&resolver, named_line("area-end", 2)), 6);
997    }
998}
taffy/compute/grid/types/named.rs

taffy/compute/grid/types/
named.rs
