Skip to content

Commit d032336

Browse files
AArnottAArnott
committed
Enhanced path shrinking to be more resilient with small path length requirements.
1 parent 2fe1ac9 commit d032336

1 file changed

Lines changed: 64 additions & 26 deletions

File tree

‎src/DotNetOpenAuth.BuildTasks/PathSegment.cs‎

Lines changed: 64 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -19,10 +19,12 @@ internal class PathSegment {
1919
private readonly PathSegment parent;
2020
private readonly string originalName;
2121
private string currentName;
22+
private bool minimized;
2223

2324
internal PathSegment() {
2425
this.currentName = string.Empty;
2526
this.originalName = string.Empty;
27+
this.minimized = true;
2628
this.Children = new Collection<PathSegment>();
2729
}
2830

@@ -32,6 +34,7 @@ private PathSegment(string originalName, PathSegment parent)
3234
Contract.Requires<ArgumentNullException>(parent != null);
3335
this.currentName = this.originalName = originalName;
3436
this.parent = parent;
37+
this.minimized = false;
3538
}
3639

3740
internal string OriginalPath {
@@ -72,7 +75,11 @@ private int SegmentCount {
7275
internal int FullLength {
7376
get {
7477
if (this.parent != null) {
75-
return this.parent.FullLength + 1/*slash*/ + this.currentName.Length;
78+
int parentLength = this.parent.FullLength;
79+
if (parentLength > 0) {
80+
parentLength++; // allow for an in between slash
81+
}
82+
return parentLength + this.currentName.Length;
7683
} else {
7784
return this.currentName.Length;
7885
}
@@ -98,6 +105,16 @@ internal IEnumerable<PathSegment> Descendents {
98105
}
99106
}
100107

108+
internal IEnumerable<PathSegment> Ancestors {
109+
get {
110+
PathSegment parent = this.parent;
111+
while (parent != null) {
112+
yield return parent;
113+
parent = parent.parent;
114+
}
115+
}
116+
}
117+
101118
internal IEnumerable<PathSegment> SelfAndDescendents {
102119
get {
103120
yield return this;
@@ -107,6 +124,15 @@ internal IEnumerable<PathSegment> SelfAndDescendents {
107124
}
108125
}
109126

127+
internal IEnumerable<PathSegment> SelfAndAncestors {
128+
get {
129+
yield return this;
130+
foreach (var parent in this.Ancestors) {
131+
yield return parent;
132+
}
133+
}
134+
}
135+
110136
internal IEnumerable<PathSegment> LeafChildren {
111137
get { return this.Children.Where(child => child.IsLeaf); }
112138
}
@@ -157,32 +183,35 @@ internal int EnsureSelfAndChildrenNoLongerThan(int maxLength) {
157183
Contract.Requires<ArgumentOutOfRangeException>(maxLength > 0, "A path can only have a positive length.");
158184
Contract.Requires<ArgumentOutOfRangeException>(this.parent == null || maxLength > this.parent.FullLength + 1, "A child path cannot possibly be made shorter than its parent.");
159185
Contract.Ensures(Contract.Result<int>() <= maxLength);
160-
161-
// First check whether this segment itself is too long.
162-
if (this.FullLength > maxLength) {
163-
int tooLongBy = this.FullLength - maxLength;
164-
this.currentName = CreateUniqueShortFileName(this.originalName, this.currentName.Length - tooLongBy);
165-
}
166-
167-
// Now check whether children are too long.
168-
if (this.Children.Count > 0) {
169-
var longChildren = this.Children.Where(path => path.FullLength > maxLength).ToList();
170-
if (longChildren.Any()) {
171-
// If this segment's name is longer than the longest child that is too long, we need to
172-
// shorten THIS segment's name.
173-
if (longChildren.Max(child => child.CurrentName.Length) < this.CurrentName.Length) {
174-
int tooLongBy = this.FullLength - maxLength;
175-
this.currentName = CreateUniqueShortFileName(this.originalName, this.currentName.Length - tooLongBy);
186+
const int uniqueBase = 16;
187+
188+
// Find the items that are too long, and always work on the longest one
189+
var longPaths = this.SelfAndDescendents.Where(path => path.FullLength > maxLength).OrderByDescending(path => path.FullLength);
190+
PathSegment longPath;
191+
while ((longPath = longPaths.FirstOrDefault()) != null) {
192+
// Keep working on this one until it's short enough.
193+
do {
194+
int tooLongBy = longPath.FullLength - maxLength;
195+
var longSegments = longPath.SelfAndAncestors.Where(segment => !segment.minimized).OrderByDescending(segment => segment.CurrentName.Length);
196+
PathSegment longestSegment = longSegments.FirstOrDefault();
197+
if (longestSegment == null) {
198+
throw new InvalidOperationException("Unable to shrink path length sufficiently.");
199+
}
200+
PathSegment secondLongestSegment = longSegments.Skip(1).FirstOrDefault();
201+
int shortenByUpTo;
202+
if (secondLongestSegment != null) {
203+
shortenByUpTo = Math.Min(tooLongBy, Math.Max(1, longestSegment.CurrentName.Length - secondLongestSegment.CurrentName.Length));
176204
} else {
177-
// The children need to be shortened.
178-
longChildren.ForEach(child => child.EnsureSelfAndChildrenNoLongerThan(maxLength));
205+
shortenByUpTo = tooLongBy;
179206
}
180-
}
181-
}
182-
183-
// Give each child a chance to check on their own children.
184-
foreach (var child in this.Children) {
185-
child.EnsureSelfAndChildrenNoLongerThan(maxLength);
207+
int minimumGuaranteedUniqueLength = Math.Max(1, RoundUp(Math.Log(longestSegment.Siblings.Count(), uniqueBase)));
208+
int allowableSegmentLength = Math.Max(minimumGuaranteedUniqueLength, longestSegment.CurrentName.Length - shortenByUpTo);
209+
if (allowableSegmentLength >= longestSegment.CurrentName.Length) {
210+
// We can't make this segment any shorter.
211+
longestSegment.minimized = true;
212+
}
213+
longestSegment.currentName = longestSegment.CreateUniqueShortFileName(longestSegment.CurrentName, allowableSegmentLength);
214+
} while (longPath.FullLength > maxLength);
186215
}
187216

188217
// Return the total length of self or longest child.
@@ -203,7 +232,7 @@ private string GetUniqueShortName(string preferredPrefix, string preferredSuffix
203232
Contract.Ensures(Contract.Result<string>().Length <= allowableLength);
204233
string candidateName = string.Empty;
205234
int i;
206-
for (i = -1; i < 0 || this.Siblings.Any(child => string.Equals(child.CurrentName, candidateName, StringComparison.OrdinalIgnoreCase)); i++) {
235+
for (i = -1; candidateName.Length == 0 || this.Siblings.Any(child => string.Equals(child.CurrentName, candidateName, StringComparison.OrdinalIgnoreCase)); i++) {
207236
string unique = i < 0 ? string.Empty : i.ToString("x");
208237
if (allowableLength < unique.Length) {
209238
throw new InvalidOperationException("Unable to shorten path sufficiently to fit constraints.");
@@ -223,6 +252,15 @@ private string GetUniqueShortName(string preferredPrefix, string preferredSuffix
223252
return candidateName;
224253
}
225254

255+
private static int RoundUp(double value) {
256+
int roundedValue = (int)value;
257+
if (roundedValue < value) {
258+
roundedValue++;
259+
}
260+
261+
return roundedValue;
262+
}
263+
226264
private string CreateUniqueShortFileName(string fileName, int targetLength) {
227265
Contract.Requires<ArgumentException>(!string.IsNullOrEmpty(fileName));
228266
Contract.Ensures(!string.IsNullOrEmpty(Contract.Result<string>()));

0 commit comments

Comments
 (0)