5.0 KB129 lines
Blame
1/**
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 */
7
8type PathObject = {
9 depth: number | null;
10 parts: string[];
11 rootPrefix: string;
12 separator: string;
13 hadLeadingSeparator: boolean;
14};
15
16type Options = {
17 alwaysShowLeadingSeparator?: boolean;
18 maxDepth?: number;
19};
20
21/**
22 * Computes the minimally differentiable display path for each file.
23 *
24 * The algorithm is O(n*m^2) where n = paths.length and m = maximum number parts in a given path and the
25 * implementation is semi-optimized for performance.
26 *
27 * Note that this function only applies to absolute paths and does NOT dedupe paths, see the last example below.
28 *
29 * ['/a/b/c.js', '/a/d/c.js'] would return ['b/c.js', 'd/c.js']
30 * ['/a/b/c.js', '/a/b/d.js'] would return ['c.js', 'd.js']
31 * ['/a/b.js', '/c/a/b.js'] would return ['/a/b.js', 'c/a/b.js']
32 * ['/a/b.js', '/a/b.js'] would return ['/a/b.js', '/a/b.js'] since this function does not dedupe.
33 *
34 * @param paths a list of paths to compute the minimal disambiguation
35 * @param options.alwaysShowLeadingSeparator If true, all file paths will start with a leading
36 * separator (`/` on Unix, `\` on Windows). If false, only full file paths will start with a leading
37 * separator. Leading separators are never shown for paths that consist of only a filename, e.g.
38 * "foo.txt". Defaults to true.
39 * @param options.maxDepth maximum depth to truncate paths to, even if it doesn't fully disambiguate.
40
41 */
42export function minimalDisambiguousPaths(paths: string[], options: Options = {}): string[] {
43 const pathObjects: PathObject[] = paths.map(path => {
44 const separator = guessSeparator(path);
45 const rootPrefixResult = /^(\w:).*/.exec(path);
46 const rootPrefix = rootPrefixResult != null ? rootPrefixResult[1] : '';
47
48 return {
49 depth: null,
50 parts: path
51 .split(separator)
52 // Path parts are reversed for easier processing below.
53 .reverse()
54 .filter(part => part !== '' && part !== rootPrefix),
55 rootPrefix,
56 separator,
57 // paths which start with `/` or `\` or `C:\` should keep that prefix when they remain at the root level.
58 hadLeadingSeparator:
59 path.startsWith(separator) || (rootPrefix.length > 0 && path.startsWith(rootPrefix)),
60 };
61 });
62
63 const maxDepth =
64 options.maxDepth == null
65 ? Math.max(...pathObjects.map(pathObject => pathObject.parts.length))
66 : options.maxDepth;
67
68 const pathObjectsToProcess = new Set(pathObjects);
69 // eslint-disable-next-line @typescript-eslint/no-unsafe-assignment -- Please fix as you edit this code
70 const groupedPathObjects: Map<string, Set<PathObject>> = new Map();
71
72 for (let currentDepth = 1; currentDepth <= maxDepth; currentDepth++) {
73 // Group path objects by their path up to the current depth.
74 groupedPathObjects.clear();
75 for (const pathObject of pathObjectsToProcess) {
76 const path = pathObject.parts.slice(0, currentDepth).join(pathObject.separator);
77 if (!groupedPathObjects.has(path)) {
78 groupedPathObjects.set(path, new Set());
79 }
80 // eslint-disable-next-line @typescript-eslint/no-non-null-assertion -- Please fix as you edit this code
81 groupedPathObjects.get(path)!.add(pathObject);
82 }
83
84 // Mark the depth for unique path objects and remove them from the set of objects to process.
85 for (const pathObjectGroup of groupedPathObjects.values()) {
86 if (pathObjectGroup.size === 1) {
87 const pathObject = Array.from(pathObjectGroup)[0];
88 pathObject.depth = currentDepth;
89 pathObjectsToProcess.delete(pathObject);
90 }
91 }
92 }
93
94 return pathObjects.map(({depth, parts, rootPrefix, separator, hadLeadingSeparator}) => {
95 let resultPathParts = parts.slice(0, depth == null ? maxDepth : depth).reverse();
96
97 // Empty path ('/' or 'c:\') should return a separator to indicate root.
98 if (resultPathParts.length === 0) {
99 return `${rootPrefix}${separator}`;
100 }
101
102 // - Complex paths should always start with a separator, if the original paths started with a separator
103 // - Simple paths (e.g. single directory or file) should not start with a separator
104 // - If we show the full path (no truncation), include any prefix like 'C:' as well.
105 if (
106 (resultPathParts.length === 1 && resultPathParts[0] === '') ||
107 (resultPathParts.length > 1 && resultPathParts[0] !== '')
108 ) {
109 resultPathParts =
110 resultPathParts.length === parts.length
111 ? hadLeadingSeparator
112 ? [rootPrefix, ...resultPathParts]
113 : resultPathParts
114 : (options.alwaysShowLeadingSeparator ?? hadLeadingSeparator)
115 ? ['', ...resultPathParts]
116 : resultPathParts;
117 }
118
119 return resultPathParts.join(separator);
120 });
121}
122
123function guessSeparator(path: string): '/' | '\\' {
124 const windowsCount = path.replace(/[^\\]/g, '').length;
125 const unixCount = path.replace(/[^/]/g, '').length;
126
127 return windowsCount > unixCount ? '\\' : '/';
128}
129