in src/Avalonia.Controls/Grid.cs [1451:1739]
private void ResolveStarMaxDiscrepancy(
IReadOnlyList<DefinitionBase> definitions,
double availableSize)
{
int defCount = definitions.Count;
DefinitionBase?[] tempDefinitions = TempDefinitions;
int minCount = 0, maxCount = 0;
double takenSize = 0;
double totalStarWeight = 0.0;
int starCount = 0; // number of unresolved *-definitions
double scale = 1.0; // scale factor applied to each *-weight; negative means "Infinity is present"
// Phase 1. Determine the maximum *-weight and prepare to adjust *-weights
double maxStar = 0.0;
for (int i = 0; i < defCount; ++i)
{
DefinitionBase def = definitions[i];
if (def.SizeType == LayoutTimeSizeType.Star)
{
++starCount;
def.MeasureSize = 1.0; // meaning "not yet resolved in phase 3"
if (def.UserSize.Value > maxStar)
{
maxStar = def.UserSize.Value;
}
}
}
if (Double.IsPositiveInfinity(maxStar))
{
// negative scale means one or more of the weights was Infinity
scale = -1.0;
}
else if (starCount > 0)
{
// if maxStar * starCount > Double.Max, summing all the weights could cause
// floating-point overflow. To avoid that, scale the weights by a factor to keep
// the sum within limits. Choose a power of 2, to preserve precision.
double power = Math.Floor(Math.Log(Double.MaxValue / maxStar / starCount, 2.0));
if (power < 0.0)
{
scale = Math.Pow(2.0, power - 4.0); // -4 is just for paranoia
}
}
// normally Phases 2 and 3 execute only once. But certain unusual combinations of weights
// and constraints can defeat the algorithm, in which case we repeat Phases 2 and 3.
// More explanation below...
for (bool runPhase2and3 = true; runPhase2and3;)
{
// Phase 2. Compute total *-weight W and available space S.
// For *-items that have Min or Max constraints, compute the ratios used to decide
// whether proportional space is too big or too small and add the item to the
// corresponding list. (The "min" list is in the first half of tempDefinitions,
// the "max" list in the second half. TempDefinitions has capacity at least
// 2*defCount, so there's room for both lists.)
totalStarWeight = 0.0;
takenSize = 0.0;
minCount = maxCount = 0;
for (int i = 0; i < defCount; ++i)
{
DefinitionBase def = definitions[i];
switch (def.SizeType)
{
case (LayoutTimeSizeType.Auto):
takenSize += definitions[i].MinSize;
break;
case (LayoutTimeSizeType.Pixel):
takenSize += def.MeasureSize;
break;
case (LayoutTimeSizeType.Star):
if (def.MeasureSize < 0.0)
{
takenSize += -def.MeasureSize; // already resolved
}
else
{
double starWeight = StarWeight(def, scale);
totalStarWeight += starWeight;
if (def.MinSize > 0.0)
{
// store ratio w/min in MeasureSize (for now)
tempDefinitions[minCount++] = def;
def.MeasureSize = starWeight / def.MinSize;
}
double effectiveMaxSize = Math.Max(def.MinSize, def.UserMaxSize);
if (!Double.IsPositiveInfinity(effectiveMaxSize))
{
// store ratio w/max in SizeCache (for now)
tempDefinitions[defCount + maxCount++] = def;
def.SizeCache = starWeight / effectiveMaxSize;
}
}
break;
}
}
// Phase 3. Resolve *-items whose proportional sizes are too big or too small.
int minCountPhase2 = minCount, maxCountPhase2 = maxCount;
double takenStarWeight = 0.0;
double remainingAvailableSize = availableSize - takenSize;
double remainingStarWeight = totalStarWeight - takenStarWeight;
Array.Sort(tempDefinitions, 0, minCount, s_minRatioComparer);
Array.Sort(tempDefinitions, defCount, maxCount, s_maxRatioComparer);
while (minCount + maxCount > 0 && remainingAvailableSize > 0.0)
{
// the calculation
// remainingStarWeight = totalStarWeight - takenStarWeight
// is subject to catastrophic cancellation if the two terms are nearly equal,
// which leads to meaningless results. Check for that, and recompute from
// the remaining definitions. [This leads to quadratic behavior in really
// pathological cases - but they'd never arise in practice.]
const double starFactor = 1.0 / 256.0; // lose more than 8 bits of precision -> recalculate
if (remainingStarWeight < totalStarWeight * starFactor)
{
takenStarWeight = 0.0;
totalStarWeight = 0.0;
for (int i = 0; i < defCount; ++i)
{
DefinitionBase def = definitions[i];
if (def.SizeType == LayoutTimeSizeType.Star && def.MeasureSize > 0.0)
{
totalStarWeight += StarWeight(def, scale);
}
}
remainingStarWeight = totalStarWeight - takenStarWeight;
}
double minRatio = (minCount > 0) ? tempDefinitions[minCount - 1]!.MeasureSize : Double.PositiveInfinity;
double maxRatio = (maxCount > 0) ? tempDefinitions[defCount + maxCount - 1]!.SizeCache : -1.0;
// choose the def with larger ratio to the current proportion ("max discrepancy")
double proportion = remainingStarWeight / remainingAvailableSize;
bool? chooseMin = Choose(minRatio, maxRatio, proportion);
// if no def was chosen, advance to phase 4; the current proportion doesn't
// conflict with any min or max values.
if (!(chooseMin.HasValue))
{
break;
}
// get the chosen definition and its resolved size
DefinitionBase resolvedDef;
double resolvedSize;
if (chooseMin == true)
{
resolvedDef = tempDefinitions[minCount - 1]!;
resolvedSize = resolvedDef.MinSize;
--minCount;
}
else
{
resolvedDef = tempDefinitions[defCount + maxCount - 1]!;
resolvedSize = Math.Max(resolvedDef.MinSize, resolvedDef.UserMaxSize);
--maxCount;
}
// resolve the chosen def, deduct its contributions from W and S.
// Defs resolved in phase 3 are marked by storing the negative of their resolved
// size in MeasureSize, to distinguish them from a pending def.
takenSize += resolvedSize;
resolvedDef.MeasureSize = -resolvedSize;
takenStarWeight += StarWeight(resolvedDef, scale);
--starCount;
remainingAvailableSize = availableSize - takenSize;
remainingStarWeight = totalStarWeight - takenStarWeight;
// advance to the next candidate defs, removing ones that have been resolved.
// Both counts are advanced, as a def might appear in both lists.
while (minCount > 0 && tempDefinitions[minCount - 1]!.MeasureSize < 0.0)
{
--minCount;
tempDefinitions[minCount] = null!;
}
while (maxCount > 0 && tempDefinitions[defCount + maxCount - 1]!.MeasureSize < 0.0)
{
--maxCount;
tempDefinitions[defCount + maxCount] = null!;
}
}
// decide whether to run Phase2 and Phase3 again. There are 3 cases:
// 1. There is space available, and *-defs remaining. This is the
// normal case - move on to Phase 4 to allocate the remaining
// space proportionally to the remaining *-defs.
// 2. There is space available, but no *-defs. This implies at least one
// def was resolved as 'max', taking less space than its proportion.
// If there are also 'min' defs, reconsider them - we can give
// them more space. If not, all the *-defs are 'max', so there's
// no way to use all the available space.
// 3. We allocated too much space. This implies at least one def was
// resolved as 'min'. If there are also 'max' defs, reconsider
// them, otherwise the over-allocation is an inevitable consequence
// of the given min constraints.
// Note that if we return to Phase2, at least one *-def will have been
// resolved. This guarantees we don't run Phase2+3 infinitely often.
runPhase2and3 = false;
if (starCount == 0 && takenSize < availableSize)
{
// if no *-defs remain and we haven't allocated all the space, reconsider the defs
// resolved as 'min'. Their allocation can be increased to make up the gap.
for (int i = minCount; i < minCountPhase2; ++i)
{
if (tempDefinitions[i] is { } def)
{
def.MeasureSize = 1.0; // mark as 'not yet resolved'
++starCount;
runPhase2and3 = true; // found a candidate, so re-run Phases 2 and 3
}
}
}
if (takenSize > availableSize)
{
// if we've allocated too much space, reconsider the defs
// resolved as 'max'. Their allocation can be decreased to make up the gap.
for (int i = maxCount; i < maxCountPhase2; ++i)
{
if (tempDefinitions[defCount + i] is { } def)
{
def.MeasureSize = 1.0; // mark as 'not yet resolved'
++starCount;
runPhase2and3 = true; // found a candidate, so re-run Phases 2 and 3
}
}
}
}
// Phase 4. Resolve the remaining defs proportionally.
starCount = 0;
for (int i = 0; i < defCount; ++i)
{
DefinitionBase def = definitions[i];
if (def.SizeType == LayoutTimeSizeType.Star)
{
if (def.MeasureSize < 0.0)
{
// this def was resolved in phase 3 - fix up its measure size
def.MeasureSize = -def.MeasureSize;
}
else
{
// this def needs resolution, add it to the list, sorted by *-weight
tempDefinitions[starCount++] = def;
def.MeasureSize = StarWeight(def, scale);
}
}
}
if (starCount > 0)
{
Array.Sort(tempDefinitions, 0, starCount, s_starWeightComparer);
// compute the partial sums of *-weight, in increasing order of weight
// for minimal loss of precision.
totalStarWeight = 0.0;
for (int i = 0; i < starCount; ++i)
{
DefinitionBase def = tempDefinitions[i]!;
totalStarWeight += def.MeasureSize;
def.SizeCache = totalStarWeight;
}
// resolve the defs, in decreasing order of weight
for (int i = starCount - 1; i >= 0; --i)
{
DefinitionBase def = tempDefinitions[i]!;
double resolvedSize = (def.MeasureSize > 0.0) ? Math.Max(availableSize - takenSize, 0.0) * (def.MeasureSize / def.SizeCache) : 0.0;
// min and max should have no effect by now, but just in case...
resolvedSize = Math.Min(resolvedSize, def.UserMaxSize);
resolvedSize = Math.Max(def.MinSize, resolvedSize);
def.MeasureSize = resolvedSize;
takenSize += resolvedSize;
}
}
}