wtf_size_t track_to_check_for_openings,
Celeste Pannext_track_index?
I think in this case the current variable name makes the most sense, since `next_track_index` would imply that this isn't the current track index we're working with. Will keep this for now, if I get other comments/you do think it's very confusing I'll change it!
wtf_size_t num_tracks_remaining_to_check,
Celeste PanMaybe just `track_count_remaining`
Done
bool FindPathOfTrackOpeningsToAccomodateItem(
Celeste PanI wonder if this should be AccumulateTrackOpeningsToAccomodateItem() since this only takes one track at a time
Done
// track openings which align to accomodate an item with the height
Celeste Panblock size, although in rows it would be the inline size, right, not the height/block size.
so maybe "with a contribution size in the stacking axis of `item_stacking_axis_contribution`"
Done
// Calculate the total size of the tracks across the given span.
LayoutUnit CalculateUsedTrackSize(const GridSpan& span);
Celeste PanI don't know that we can rely on the total. I think we need to guarantee that the span is placed in tracks of the exact same size in the same order as where it was originally laid out
So if we had tracks
50px 25px 25px 50pxAnd a 2 track spanner was placed in track 2 (i.e. 25px 50px), we would only look for openings starting at track 2 since that is the only way you'd get the same track sizes in the same order
Discussed this offline, but based on the CSSWG discussions it seems like only the total track size size and # of spans matter: https://github.com/w3c/csswg-drafts/issues/9326, but we are now tracking a task to confirm that the current behavior is what we are looking for.
wtf_size_t opening_index{0};
Celeste PanIs this an index or an offset?
This is an index, so it would be accessing the specific opening within the vector of track openings for each track.
wtf_size_t track_index{0};
Celeste PanDo we need to track index for each or just the index of the first track in the sequence (since they have to be consecutive)?
Good idea, we can definitely just track the first index!
// opening in `track_collection_openings_`. `start_position` refers to the
Celeste Pannit: extra space
Done
// `EligibleTrackOpeningPositions` holds the indices within for a track
Celeste Pannit: within what?
fixed comment.
// `EligibleTrackOpeningPositions` holds the indices within for a track
Celeste PanIs this defined anywhere?
It's supposed to be `EligibleTrackOpeningIndices `, will fix the comment!
LayoutUnit used_track_size;
Celeste PanCan this get called multiple times with the same span? If so, it might be worth adding a cache (as a TODO).
It's possible that we'll get the overlap just one time, but I'm not sure if it's worth adding a cache in that case.
For example, we calculate the used track size of `masonry_item_span_ref`, and then later when we're iterating through the tracks trying to find a path of track openings, we will end up hitting the same span again and we'll re-calculate for the same span in that case.
I'll resolve this for now, but if you do think a cache is a good idea, please re-open!
start_line++) {
Celeste Pan`++start_line` per https://google.github.io/styleguide/cppguide.html#Preincrement_and_Predecrement
(and in the loop in `FindPathOfTrackOpeningsToAccomodateItem)
Done
CHECK_LT(start_line, track_collection_sizes_.size());
Celeste PanThis seems unnecessary, given the `CHECK_LE` above on `end_line`.
Done
wtf_size_t num_tracks_remaining_to_check,
Celeste Pan`num_tracks_remaining`
Actually, I'll go with this suggestion instead of alison's!
LayoutUnit overlap_range_size;
Celeste PanThis doesn't need to be outside of the loop. Putting it in the loop will allow it to be `const`.
Done
Vector<TrackOpening> current_track_openings =
Celeste Pan`const` (can this be a `const&`?)
(a few more locals in this method can be `const` as well, like `overlap_start_position`, `overlap_end_position`, `found_eligible_track_opening_span `)
Done
// Calculate the overlap between the previous track's eligible opening and
// the current opening.
Celeste PanYou should add a comment explaining why the start position uses `max` and the end uses `min`.
Done
overlap_range_size = overlap_end_position - overlap_start_position;
Celeste PanIs this allowed to be negative? Or possible to be negative? Might be worth adding a `DCHECK`.
Yes, it's possible that it would be negatively, but in that case it would definitely be less than item_stacking_axis_contribution, and we would return false because there's not path that can fit the item.
const auto& masonry_item_span_ref =
Celeste Pannit: I'd use the actual value here since it will be easier to look up in code search later
Done
const auto& masonry_item_span_ref =
Celeste Pannit: ref not needed in the name
Done
const auto& masonry_item_span_ref =
Celeste Pana `GridSpan` is super light-weight, so you probably don't need a reference here.
Done
item_span.Translate(1)) {
Celeste PanMight be worth adding a `operator++` to `GridSpan` to make this cleaner.
Done
// If the item spans N tracks, only check for equivalent total track
Celeste PanAs mentioned in another comment, I don't think we can rely on the total here
Discussed offline; we think based on the CSSWG discussions that the current behavior, ie using the same number of tracks with the same total track size, should be fine, but will confirm with ian later.
auto current_track = item_span.StartLine();
if (CalculateUsedTrackSize(item_span) == used_track_size) {
Celeste PanA general comment on this algorithm - it would really help to add comments with verbatims from the masonry placement spec - https://www.w3.org/TR/css-grid-3/#running-position
e.g.
```
// "Repeat the previous step for each successive line number until the item would no longer fit inside the grid."
```(it can also help to use the same variable names as the spec does)
Okay, I did my best to map to similar language to the spec! But since there isn't a 1:1 mapping with the placement algorithm (I think the dense-packing search algorithm is pretty different from the placement algorithm) I couldn't quite pull everything from the spec.
if (CalculateUsedTrackSize(item_span) == used_track_size) {
Celeste Pannit: I'd swap the polarity of this and do:
```
if (CalculateUsedTrackSize(item_span) != used_track_size) {
continue;
}
```That way we don't need all the extra indentation
Done
track_collection_openings_[current_track];
Celeste PanI am curious, with how this is currently implemented, will we be checking every opening combination across tracks?
i.e. if track 1 has two openeings that overlap with one larger opening in track 2, but track 3 only overlaps the second opening in track one and the single opening in track two. Will we find this case? Trying to figure out where that iteration is happening
The loop here is choosing which track we want to start iterating through.
For each track, we then call `AccumulateTrackOpeningsToAccomodateItem`, which:
1. For each track opening:
a. iterates recursively to find a possible path
b. if no possible path is found, move to start the path using the next track
opening in the current track.
So the actual path-finding only starts in `AccumulateTrackOpeningsToAccomodateItem`.
The check highlighted here was just to save time by skipping iteration on the track items at all if we already know the current track is empty/the track openings aren't going to be higher than a path of track openings we already have anyways.
(highest_eligible_track_opening_result.IsValid() &&
Celeste PanWe don't seem to set this before the first time - is it valid by default?
It's invalid by default (the default value of start_position is LayoutUnit::Max())!
current_track_openings[0].start_position >=
highest_eligible_track_opening_result.start_position)) {
Celeste PanTo confirm, this is saying that if the current start track has openings that are below the highest eligible start, we will never overlap?
I'm kind of confused as to where highest_eligible_track_opening_result first gets set
This is saying that if our current track's first opening is going to be higher than our existing highest track opening, then there's no reason for us to start looking for path of track openings starting from this track, since it's going to be too low to add anyways. So we skip even trying to run `AccumulateTrackOpeningsToAccomodateItem` and move onto the next track.
The first instance highest_eligible_track_opening_result gets set is after we've run `AccumulateTrackOpeningsToAccomodateItem` for first time and successfully found a path of eligible track openings.
eligible_track_opening_result);
Celeste PanWill this always be "invalid" when we return false? If so, maybe that shoul be the return type instead of bool
Okay, I'll have the method return whether or not it's valid then!
if (found_eligible_track_opening_span &&
(!highest_eligible_track_opening_result.IsValid() ||
eligible_track_opening_result.start_position <
highest_eligible_track_opening_result.start_position)) {
Celeste PanThis check is complex and can probably use a comment
Done
}
Celeste PanI know we had discussed that do-while was advised against previously, but given how complex this is getting, I actually think it will be easier to reason about in a do-while loop
Done!
if (!highest_eligible_opening_span.IsTranslatedDefinite()) {
Celeste PanThis could use a comment - when is this not true?
this ended up being removed, so resolving this comment.
const wtf_size_t current_track_index =
eligible_track_opening_positions.track_index;
const wtf_size_t current_opening_index =
eligible_track_opening_positions.opening_index;
const TrackOpening eligible_track_opening =
track_collection_openings_[current_track_index][current_opening_index];
if (item_stacking_axis_contribution == eligible_track_opening.Size()) {
track_collection_openings_[current_track_index].EraseAt(
current_opening_index);
Celeste PanIsn't it possible for a track opening to be split in two when it comes to the spanning case?
Yes that's totally possible, added a test case for this + have fixed this issue!
display: grid;
background: gray;
position: relative;
grid-template-columns: repeat(3, 50px);
width: 170px;
grid-auto-flow: dense;
}
Celeste PanWould this test case be easier if the ref is identical but doesn't specify dense packing?
Good idea, will change it to that!
-ref.html">
Celeste PanThis added newline looks unintentional
Done
<p>Ensure that dense-packing does not affect the layout when all items are single-spanning.</p>
Celeste PanI would phrase this as "...has no impact when all items..."
Done
<p>Ensure dense-packing only lays items into gaps where the track size is the same as where the item would have been laid out WITHOUT dense packing.</p>
Celeste Panlays -> places
Done
<p>Ensure that dense-packing places multi-spanning item into highest eligible track opening. The yellow item is the item that should be placed in track opening.</p>
Celeste PanThis can go away
Done
<p>Ensure that dense-packing places multi-spanning item into highest eligible track opening. The yellow item is the item that should be placed in track opening.</p>
Celeste Pan"...in the track..."?
I mean track opening, since it's the item that because of dense-packing will go into a previous track opening.
<p>Ensure that dense-packing with multi-span items are placed into tracks with the same used size and the same number of tracks, and priority is given to tracks closest after the auto-placement cursor.</p>
Celeste PanThis is a little awkward, how about "closest (but after)"?
Done
<p>Ensure that dense-packing with multi-span items can find the right path of aligning gaps when there are multiple gaps in a track.</p>
Celeste PanThis could be rephrased as "follows the masonry dense packing algorithm"
Done
<link rel="help" href="https://drafts.csswg.org/css-grid-3">
Celeste PanI don't think ref files typically have help links
Done
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
bool AccumulateTrackOpeningsToAccomodateItem(
Instead of a bool, would it make sense to return EligibleTrackOpeningPath? If not, then it may be fine to just leave is as void and then utilize EligibleTrackOpeningPath as whether it was valid.
If we do need the bool, too, then would be worth noting what is being returned in the method comment
// vector of openings. `start_position` refers to the highest possible
nit: extra space
LayoutUnit MasonryRunningPositions::CalculateUsedTrackSize(
This method likely makes more sense in GridSpan in case it ends up being useful in other scenarios at some point
eligible_track_opening_result.track_opening_indices.emplace_back(i);
Will this be emplaced back in reverse order given this is recursive? I see this called out later - may be worth documenting that somewhere
GridSpan highest_eligible_opening_span = GridSpan::IndefiniteGridSpan();
This one could likely use a comment
if (item_span.EndLine() > running_positions_.size()) {
I'd add a comment here to note we are looping back to the start because the starting cursor did not start at index 0
// far, we won't want any result that comes from this track.
"end up finding any better results that start with this track"
// Starting at `current_track`, find a
nit: I'd add an extra line before this comment
This comment also looks like it can be re-wrapped
// series of adjacent track openings that the item could could into if
nit: double "could"
Also missing a verb (maybe "be placed into")
// series of adjacent track openings that the item could could into if
// placed at this line. If there is not previous result for the highest
"starting at this line"
} while (iterations <= max_iterations);
Instead of tracking iterations, is it possible to update as suggested in https://chromium-review.googlesource.com/c/chromium/src/+/6819879/8..28/third_party/blink/renderer/core/layout/masonry/masonry_running_positions.cc#b177?
If not, I think where we set max_iterations could use a comment
highest_eligible_track_opening_result.track_opening_indices.Reverse();
Can we just iterate through them in the opposite direction instead?
Another option is to make the openings vector always be the size of the span needed and that way we can place these in the vector at the correct index as we recurse instead of emplacing back
// If the item causes a split for the opening, create a new track opening
nit: "an opening to split"
if (highest_eligible_opening_span.IsTranslatedDefinite()) {
Can this ever not be the case? If so, what happens?
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Instead of a bool, would it make sense to return EligibleTrackOpeningPath? If not, then it may be fine to just leave is as void and then utilize EligibleTrackOpeningPath as whether it was valid.
If we do need the bool, too, then would be worth noting what is being returned in the method comment
I do have an existing comment line 88, "This method returns whether or not a path of eligible track openings were found."
The code is definitely cleaner with a boolean + the `eligible_track_opening_result` out param. If we were to return EligibleTrackOpeningPath, we'd have to have 2 separate conditionals on line 134, since we'd check for the number of tracks first, and only run `AccumulateTrackOpeningsToAccomodateItem` if we need to. The two conditions would have us performing the same action, so it would also lead to some code repeating.
// vector of openings. `start_position` refers to the highest possible
Celeste Pannit: extra space
Hm, I think there's only one space here, so resolving!
LayoutUnit MasonryRunningPositions::CalculateUsedTrackSize(
This method likely makes more sense in GridSpan in case it ends up being useful in other scenarios at some point
At the moment we could only do this in GridSpan if we pass in `track_collection_sizes_`, since GridSpan doesn't have access to the sizes of the tracks it spans.
I think it would make sense to have something like this where it can take in a GridLayoutTrackCollection and figure out the used size of the spans; but until we actually implement the ability to get individual track sizes in GridLayoutCollection, it wouldn't make sense to have something like this in GridSpan yet.
I'll add a TODO for this!
eligible_track_opening_result.track_opening_indices.emplace_back(i);
Will this be emplaced back in reverse order given this is recursive? I see this called out later - may be worth documenting that somewhere
I'll document this in the method description!
GridSpan highest_eligible_opening_span = GridSpan::IndefiniteGridSpan();
This one could likely use a comment
Done
if (item_span.EndLine() > running_positions_.size()) {
I'd add a comment here to note we are looping back to the start because the starting cursor did not start at index 0
I feel like this is covered in the comment in lines 171-174, so it might be repetitive to say again. Will resolve for now, but let me know if you feel strongly that a comment should be here as well!
// far, we won't want any result that comes from this track.
"end up finding any better results that start with this track"
Done
nit: I'd add an extra line before this comment
This comment also looks like it can be re-wrapped
Done
// series of adjacent track openings that the item could could into if
nit: double "could"
Also missing a verb (maybe "be placed into")
Done
// series of adjacent track openings that the item could could into if
// placed at this line. If there is not previous result for the highest
Celeste Pan"starting at this line"
Done
Instead of tracking iterations, is it possible to update as suggested in https://chromium-review.googlesource.com/c/chromium/src/+/6819879/8..28/third_party/blink/renderer/core/layout/masonry/masonry_running_positions.cc#b177?
If not, I think where we set max_iterations could use a comment
This was originally the intention, but it ended up becoming a lot more complex, and we end up having to keep track of other variables for breaking the loop; this ended up being the simplest solution.
I'll add a comment for where we're setting `max_iterations`!
highest_eligible_track_opening_result.track_opening_indices.Reverse();
Can we just iterate through them in the opposite direction instead?
Another option is to make the openings vector always be the size of the span needed and that way we can place these in the vector at the correct index as we recurse instead of emplacing back
Yup, I can just change this to iterate in the opposite direction!
// If the item causes a split for the opening, create a new track opening
nit: "an opening to split"
Done
if (highest_eligible_opening_span.IsTranslatedDefinite()) {
Can this ever not be the case? If so, what happens?
Ended up deleting this in favor of just creating a span using the highest_eligible_track_opening_result, so comment no longer relevant!
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Code-Review | +1 |
LGTM, but it looks like there is a test failure with the recent upload, so if I need to take a look another look after the fix is uploaded, feel free to lmk
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Looks great, just some minor issues.
LayoutUnit CalculateUsedTrackSize(const GridSpan& span);
Can this be `const` - e.g. `LayoutUnit CalculateUsedTrackSize(const GridSpan& span) const;`?
const Vector<TrackOpening> current_track_openings =
Can this be a reference? e.g. `const Vector<TrackOpening>&`? That'll avoid a vector copy.
num_tracks_remaining - 1, track_to_check_for_openings + 1,
If `num_tracks_remaining == 0`, this will underflow - this needs to be handled somewhere.
--current_track_index;
`DCHECK_GT(current_track_index, 0U);` to catch underflows
GridSpan& operator++() {
`DCHECK(IsTranslatedDefinite());`
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
LayoutUnit CalculateUsedTrackSize(const GridSpan& span);
Can this be `const` - e.g. `LayoutUnit CalculateUsedTrackSize(const GridSpan& span) const;`?
Done
const Vector<TrackOpening> current_track_openings =
Can this be a reference? e.g. `const Vector<TrackOpening>&`? That'll avoid a vector copy.
Done
num_tracks_remaining - 1, track_to_check_for_openings + 1,
If `num_tracks_remaining == 0`, this will underflow - this needs to be handled somewhere.
This case would be covered by the first part of the conditional, since if `num_track_remaining == 0`, we would skip the run of `AccumulateTrackOpeningsToAccomodateItem`.
`DCHECK_GT(current_track_index, 0U);` to catch underflows
Can't do this since at some point `current_track_index` will be 0; I added `DCHECK_GE(current_track_index, track_opening_indices.size());` before the beginning of the loop moved the subtraction to the beginning of the while loop, and this should cover the case of underflow.
GridSpan& operator++() {
Celeste Pan`DCHECK(IsTranslatedDefinite());`
Done
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Commit-Queue | +2 |
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
19 is the latest approved patch-set.
The change was submitted with unreviewed changes in the following files:
```
The name of the file: third_party/blink/web_tests/wpt_internal/css/css-masonry/row-dense-packing-multi-span-002.html
Insertions: 0, Deletions: 2.
@@ -3,7 +3,6 @@
<link rel="help" href="https://drafts.csswg.org/css-grid-3">
<link rel="match" href="row-dense-packing-multi-span-002-ref.html">
<link rel="author" title="Celeste Pan" href="mailto:celes...@microsoft.com">
-<link rel="stylesheet" href="/fonts/ahem.css">
<style>
.masonry {
display: masonry;
@@ -11,7 +10,6 @@
masonry-direction: row;
grid-template-rows: 10px 10px 20px 15px 5px;
grid-auto-flow: dense;
- font: 5px/1 "Ahem";
}
</style>
<body>
```
```
The name of the file: third_party/blink/web_tests/wpt_internal/css/css-masonry/row-dense-packing-multi-span-002-ref.html
Insertions: 10, Deletions: 16.
@@ -1,12 +1,10 @@
<!DOCTYPE html>
<html>
-<link rel="stylesheet" href="/fonts/ahem.css">
<style>
.grid {
display: grid;
grid-template-rows: 10px 10px 20px 15px 5px;
grid-auto-flow: dense;
- font: 5px/1 "Ahem";
}
.flex {
display: flex;
@@ -17,22 +15,18 @@
<p>Ensure that dense-packing with multi-span items are placed into tracks with the same used size and the same number of tracks, and priority is given to tracks closest after the auto-placement cursor.</p>
<div class="grid">
<div class="flex">
- <div style="display: flex; flex-direction: column; transform: translateY(20px);">
- <div style="background: lightskyblue; width: 20px; height: 40px;" >
- 1
- </div>
- <div style="background: yellow; width: 20px; height: 20px;" >
- 4
- </div>
+ <div style="background: lightskyblue; width: 20px; height: 20px; transform: translateY(20px);" >
+ 1
</div>
- <div class="flex">
- <div style="background: lightblue; width: 20px; height: 60px;" >
- 2
- </div>
- <div style="background: darkblue; width: 20px; height: 40px;">
- 3
- </div>
+ <div style="background: lightblue; width: 20px; height: 60px;" >
+ 2
</div>
+ <div style="background: darkblue; width: 20px; height: 40px;">
+ 3
+ </div>
+ </div>
+ <div style="background: yellow; width: 20px; height: 20px; transform: translateY(30px);" >
+ 4
</div>
</div>
</body>
```
[Masonry] Implement dense-packing for multi-spanning items
This change allows masonry to use dense-packing on multi-spanning items.
Items that span N tracks must be laid out across N tracks, regardless of
whether or not it is going into a track opening or not.
The rescursive method `FindPathOfTrackOpeningsToAccomodateItem` performs
backtracking search for a list of consecutive track openings that can
contain the item with the given height.
The only changes in the dense-packing single-spanning tests are renames,
as the contents of [row|column-dense-packing-003] were moved into
[row|column]-dense-packing-multi-span-003.html.
Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |