addons/isl/src/pathTree.tsblame
View source
b69ab311/**
b69ab312 * Copyright (c) Meta Platforms, Inc. and affiliates.
b69ab313 *
b69ab314 * This source code is licensed under the MIT license found in the
b69ab315 * LICENSE file in the root directory of this source tree.
b69ab316 */
b69ab317
b69ab318import type {RepoPath} from 'shared/types/common';
b69ab319import type {UseUncommittedSelection} from './partialSelection';
b69ab3110
b69ab3111export type PathTree<T> = Map<string, PathTree<T> | T>;
b69ab3112/**
b69ab3113 * Path tree reconstructs the tree structure from a set of paths,
b69ab3114 * then compresses path names for single-child directories.
b69ab3115 *
b69ab3116 * ```
b69ab3117 * buildPathTree({
b69ab3118 * 'a/b/file1.txt': {...},
b69ab3119 * 'a/b/file2.txt': {...},
b69ab3120 * 'a/file3.txt': {...},
b69ab3121 * 'a/d/e/f/file4.txt': {...},
b69ab3122 * 'q/file5.txt': {...},
b69ab3123 * })
b69ab3124 * Map{
b69ab3125 * a: Map{
b69ab3126 * b: Map{
b69ab3127 * 'file1.txt' : {...},
b69ab3128 * 'file2.txt' : {...},
b69ab3129 * },
b69ab3130 * 'file3.txt': {...},
b69ab3131 * 'd/e/f': Map{
b69ab3132 * 'file4.txt': {...}
b69ab3133 * }
b69ab3134 * },
b69ab3135 * q: Map{
b69ab3136 * 'file5.txt': {...},
b69ab3137 * }
b69ab3138 * }
b69ab3139 * ```
b69ab3140 */
b69ab3141export function buildPathTree<T>(paths: Record<RepoPath, T>): PathTree<T> {
b69ab3142 function recurse(input: Map<string, T>) {
b69ab3143 const intermediateTree: Map<string, Map<string, T>> = new Map();
b69ab3144 const plainFiles = new Map<string, T>();
b69ab3145
b69ab3146 // group files by common path
b69ab3147 for (const [path, data] of input.entries()) {
b69ab3148 const [folder] = path.split('/', 1);
b69ab3149 const rest = path.slice(folder.length + 1);
b69ab3150 if (rest === '') {
b69ab3151 // no more folders in this path, use the data directly
b69ab3152 plainFiles.set(folder, data);
b69ab3153 } else if (intermediateTree.has(folder)) {
b69ab3154 const existing = intermediateTree.get(folder);
b69ab3155 existing?.set(rest, data);
b69ab3156 } else {
b69ab3157 intermediateTree.set(folder, new Map([[rest, data]]));
b69ab3158 }
b69ab3159 }
b69ab3160
b69ab3161 // recurse into each grouping
b69ab3162 const tree: PathTree<T> = new Map();
b69ab3163 for (const [key, value] of intermediateTree.entries()) {
b69ab3164 const resultTree = recurse(value);
b69ab3165 // if a folder 'a' contains exactly one subfolder 'b', we can collapse it into just 'a/b'
b69ab3166 if (resultTree.size === 1) {
b69ab3167 const [innerkey, inner] = resultTree.entries().next().value;
b69ab3168 if (!(inner instanceof Map)) {
b69ab3169 // the single file is the bottom of the tree, don't absorb it
b69ab3170 tree.set(key, resultTree);
b69ab3171 } else {
b69ab3172 tree.set(key + '/' + innerkey, inner);
b69ab3173 }
b69ab3174 } else {
b69ab3175 tree.set(key, resultTree);
b69ab3176 }
b69ab3177 }
b69ab3178
b69ab3179 // re-add the file entries we found
b69ab3180 for (const [key, value] of plainFiles.entries()) {
b69ab3181 tree.set(key, value);
b69ab3182 }
b69ab3183
b69ab3184 return tree;
b69ab3185 }
b69ab3186
b69ab3187 return recurse(new Map(Object.entries(paths)));
b69ab3188}
b69ab3189
b69ab3190/**
b69ab3191 * Compute accumulated selected state of directory nodes in the tree, so we don't need to repeatedly
b69ab3192 * check isSelected among child nodes.
b69ab3193 * Note that this is only stored for directories (non-leaf), not files (leaves)
b69ab3194 * given tree like
b69ab3195 * Map{
b69ab3196 * a: Map{
b69ab3197 * b: Map{
b69ab3198 * 'file1.txt' : checked
b69ab3199 * 'file2.txt' : checked,
b69ab31100 * },
b69ab31101 * c: Map{
b69ab31102 * 'file1.txt' : checked
b69ab31103 * 'file2.txt' : unchecked,
b69ab31104 * },
b69ab31105 * d: Map{
b69ab31106 * 'file1.txt' : checked
b69ab31107 * 'file2.txt' : partiallyChecked,
b69ab31108 * },
b69ab31109 * },
b69ab31110 * q: Map{
b69ab31111 * 'file6.txt': unchecked
b69ab31112 * }
b69ab31113 * }
b69ab31114 * returns:
b69ab31115 * a -> 'indeterminate'
b69ab31116 * a/b -> true
b69ab31117 * a/c -> 'indeterminate'
b69ab31118 * a/d -> 'indeterminate'
b69ab31119 * q -> false
b69ab31120 */
b69ab31121export function calculateTreeSelectionStates<T extends {path: string}>(
b69ab31122 tree: PathTree<T>,
b69ab31123 selection: UseUncommittedSelection,
b69ab31124): Map<string, boolean | 'indeterminate'> {
b69ab31125 const checkedStates = new Map<string, boolean | 'indeterminate'>();
b69ab31126 function inner(key: string, node: PathTree<T> | T): boolean | 'indeterminate' {
b69ab31127 if (node instanceof Map) {
b69ab31128 // every child checked -> checked
b69ab31129 // any child partially checked -> indeterminate
b69ab31130 // no child checked -> unchecked
b69ab31131 let allChecked = true;
b69ab31132 let anyChecked = false;
b69ab31133 let anyPartiallyChecked = false;
b69ab31134
b69ab31135 for (const [childKey, child] of node.entries()) {
b69ab31136 const childChecked = inner(key + '/' + childKey, child);
b69ab31137 if (childChecked === false) {
b69ab31138 allChecked = false;
b69ab31139 } else if (childChecked === 'indeterminate') {
b69ab31140 anyPartiallyChecked = true;
b69ab31141 allChecked = false;
b69ab31142 anyChecked = true;
b69ab31143 } else {
b69ab31144 anyChecked = true;
b69ab31145 }
b69ab31146 }
b69ab31147 const checked = anyPartiallyChecked
b69ab31148 ? 'indeterminate'
b69ab31149 : allChecked
b69ab31150 ? true
b69ab31151 : anyChecked
b69ab31152 ? 'indeterminate'
b69ab31153 : false;
b69ab31154 checkedStates.set(key, checked);
b69ab31155 return checked;
b69ab31156 } else {
b69ab31157 const checked = selection.isFullySelected(node.path)
b69ab31158 ? true
b69ab31159 : selection.isFullyOrPartiallySelected(node.path)
b69ab31160 ? 'indeterminate'
b69ab31161 : false;
b69ab31162 return checked;
b69ab31163 }
b69ab31164 }
b69ab31165 inner('', tree);
b69ab31166 return checkedStates;
b69ab31167}