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