4.7 KB168 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
8import type {RepoPath} from 'shared/types/common';
9import type {UseUncommittedSelection} from './partialSelection';
10
11export type PathTree<T> = Map<string, PathTree<T> | T>;
12/**
13 * Path tree reconstructs the tree structure from a set of paths,
14 * then compresses path names for single-child directories.
15 *
16 * ```
17 * buildPathTree({
18 * 'a/b/file1.txt': {...},
19 * 'a/b/file2.txt': {...},
20 * 'a/file3.txt': {...},
21 * 'a/d/e/f/file4.txt': {...},
22 * 'q/file5.txt': {...},
23 * })
24 * Map{
25 * a: Map{
26 * b: Map{
27 * 'file1.txt' : {...},
28 * 'file2.txt' : {...},
29 * },
30 * 'file3.txt': {...},
31 * 'd/e/f': Map{
32 * 'file4.txt': {...}
33 * }
34 * },
35 * q: Map{
36 * 'file5.txt': {...},
37 * }
38 * }
39 * ```
40 */
41export function buildPathTree<T>(paths: Record<RepoPath, T>): PathTree<T> {
42 function recurse(input: Map<string, T>) {
43 const intermediateTree: Map<string, Map<string, T>> = new Map();
44 const plainFiles = new Map<string, T>();
45
46 // group files by common path
47 for (const [path, data] of input.entries()) {
48 const [folder] = path.split('/', 1);
49 const rest = path.slice(folder.length + 1);
50 if (rest === '') {
51 // no more folders in this path, use the data directly
52 plainFiles.set(folder, data);
53 } else if (intermediateTree.has(folder)) {
54 const existing = intermediateTree.get(folder);
55 existing?.set(rest, data);
56 } else {
57 intermediateTree.set(folder, new Map([[rest, data]]));
58 }
59 }
60
61 // recurse into each grouping
62 const tree: PathTree<T> = new Map();
63 for (const [key, value] of intermediateTree.entries()) {
64 const resultTree = recurse(value);
65 // if a folder 'a' contains exactly one subfolder 'b', we can collapse it into just 'a/b'
66 if (resultTree.size === 1) {
67 const [innerkey, inner] = resultTree.entries().next().value;
68 if (!(inner instanceof Map)) {
69 // the single file is the bottom of the tree, don't absorb it
70 tree.set(key, resultTree);
71 } else {
72 tree.set(key + '/' + innerkey, inner);
73 }
74 } else {
75 tree.set(key, resultTree);
76 }
77 }
78
79 // re-add the file entries we found
80 for (const [key, value] of plainFiles.entries()) {
81 tree.set(key, value);
82 }
83
84 return tree;
85 }
86
87 return recurse(new Map(Object.entries(paths)));
88}
89
90/**
91 * Compute accumulated selected state of directory nodes in the tree, so we don't need to repeatedly
92 * check isSelected among child nodes.
93 * Note that this is only stored for directories (non-leaf), not files (leaves)
94 * given tree like
95 * Map{
96 * a: Map{
97 * b: Map{
98 * 'file1.txt' : checked
99 * 'file2.txt' : checked,
100 * },
101 * c: Map{
102 * 'file1.txt' : checked
103 * 'file2.txt' : unchecked,
104 * },
105 * d: Map{
106 * 'file1.txt' : checked
107 * 'file2.txt' : partiallyChecked,
108 * },
109 * },
110 * q: Map{
111 * 'file6.txt': unchecked
112 * }
113 * }
114 * returns:
115 * a -> 'indeterminate'
116 * a/b -> true
117 * a/c -> 'indeterminate'
118 * a/d -> 'indeterminate'
119 * q -> false
120 */
121export function calculateTreeSelectionStates<T extends {path: string}>(
122 tree: PathTree<T>,
123 selection: UseUncommittedSelection,
124): Map<string, boolean | 'indeterminate'> {
125 const checkedStates = new Map<string, boolean | 'indeterminate'>();
126 function inner(key: string, node: PathTree<T> | T): boolean | 'indeterminate' {
127 if (node instanceof Map) {
128 // every child checked -> checked
129 // any child partially checked -> indeterminate
130 // no child checked -> unchecked
131 let allChecked = true;
132 let anyChecked = false;
133 let anyPartiallyChecked = false;
134
135 for (const [childKey, child] of node.entries()) {
136 const childChecked = inner(key + '/' + childKey, child);
137 if (childChecked === false) {
138 allChecked = false;
139 } else if (childChecked === 'indeterminate') {
140 anyPartiallyChecked = true;
141 allChecked = false;
142 anyChecked = true;
143 } else {
144 anyChecked = true;
145 }
146 }
147 const checked = anyPartiallyChecked
148 ? 'indeterminate'
149 : allChecked
150 ? true
151 : anyChecked
152 ? 'indeterminate'
153 : false;
154 checkedStates.set(key, checked);
155 return checked;
156 } else {
157 const checked = selection.isFullySelected(node.path)
158 ? true
159 : selection.isFullyOrPartiallySelected(node.path)
160 ? 'indeterminate'
161 : false;
162 return checked;
163 }
164 }
165 inner('', tree);
166 return checkedStates;
167}
168