1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
|
/*
* Copyright 2013 Google Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.google.common.jimfs;
import static com.google.common.base.Preconditions.checkNotNull;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSortedMap;
import com.google.common.collect.ImmutableSortedSet;
import java.io.IOException;
import java.nio.file.LinkOption;
import java.nio.file.NoSuchFileException;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import org.checkerframework.checker.nullness.compatqual.NullableDecl;
/**
* The tree of directories and files for the file system. Contains the file system root directories
* and provides the ability to look up files by path. One piece of the file store implementation.
*
* @author Colin Decker
*/
final class FileTree {
/**
* Doesn't much matter, but this number comes from MIN_ELOOP_THRESHOLD <a
* href="https://sourceware.org/git/gitweb.cgi?p=glibc.git;a=blob_plain;f=sysdeps/generic/eloop-threshold.h;hb=HEAD">
* here</a>
*/
private static final int MAX_SYMBOLIC_LINK_DEPTH = 40;
private static final ImmutableList<Name> EMPTY_PATH_NAMES = ImmutableList.of(Name.SELF);
/** Map of root names to root directories. */
private final ImmutableSortedMap<Name, Directory> roots;
/** Creates a new file tree with the given root directories. */
FileTree(Map<Name, Directory> roots) {
this.roots = ImmutableSortedMap.copyOf(roots, Name.canonicalOrdering());
}
/** Returns the names of the root directories in this tree. */
public ImmutableSortedSet<Name> getRootDirectoryNames() {
return roots.keySet();
}
/**
* Gets the directory entry for the root with the given name or {@code null} if no such root
* exists.
*/
@NullableDecl
public DirectoryEntry getRoot(Name name) {
Directory dir = roots.get(name);
return dir == null ? null : dir.entryInParent();
}
/** Returns the result of the file lookup for the given path. */
public DirectoryEntry lookUp(
File workingDirectory, JimfsPath path, Set<? super LinkOption> options) throws IOException {
checkNotNull(path);
checkNotNull(options);
DirectoryEntry result = lookUp(workingDirectory, path, options, 0);
if (result == null) {
// an intermediate file in the path did not exist or was not a directory
throw new NoSuchFileException(path.toString());
}
return result;
}
@NullableDecl
private DirectoryEntry lookUp(
File dir, JimfsPath path, Set<? super LinkOption> options, int linkDepth) throws IOException {
ImmutableList<Name> names = path.names();
if (path.isAbsolute()) {
// look up the root directory
DirectoryEntry entry = getRoot(path.root());
if (entry == null) {
// root not found; always return null as no real parent directory exists
// this prevents new roots from being created in file systems supporting multiple roots
return null;
} else if (names.isEmpty()) {
// root found, no more names to look up
return entry;
} else {
// root found, more names to look up; set dir to the root directory for the path
dir = entry.file();
}
} else if (isEmpty(names)) {
// set names to the canonical list of names for an empty path (singleton list of ".")
names = EMPTY_PATH_NAMES;
}
return lookUp(dir, names, options, linkDepth);
}
/**
* Looks up the given names against the given base file. If the file is not a directory, the
* lookup fails.
*/
@NullableDecl
private DirectoryEntry lookUp(
File dir, Iterable<Name> names, Set<? super LinkOption> options, int linkDepth)
throws IOException {
Iterator<Name> nameIterator = names.iterator();
Name name = nameIterator.next();
while (nameIterator.hasNext()) {
Directory directory = toDirectory(dir);
if (directory == null) {
return null;
}
DirectoryEntry entry = directory.get(name);
if (entry == null) {
return null;
}
File file = entry.file();
if (file.isSymbolicLink()) {
DirectoryEntry linkResult = followSymbolicLink(dir, (SymbolicLink) file, linkDepth);
if (linkResult == null) {
return null;
}
dir = linkResult.fileOrNull();
} else {
dir = file;
}
name = nameIterator.next();
}
return lookUpLast(dir, name, options, linkDepth);
}
/** Looks up the last element of a path. */
@NullableDecl
private DirectoryEntry lookUpLast(
@NullableDecl File dir, Name name, Set<? super LinkOption> options, int linkDepth)
throws IOException {
Directory directory = toDirectory(dir);
if (directory == null) {
return null;
}
DirectoryEntry entry = directory.get(name);
if (entry == null) {
return new DirectoryEntry(directory, name, null);
}
File file = entry.file();
if (!options.contains(LinkOption.NOFOLLOW_LINKS) && file.isSymbolicLink()) {
return followSymbolicLink(dir, (SymbolicLink) file, linkDepth);
}
return getRealEntry(entry);
}
/**
* Returns the directory entry located by the target path of the given symbolic link, resolved
* relative to the given directory.
*/
@NullableDecl
private DirectoryEntry followSymbolicLink(File dir, SymbolicLink link, int linkDepth)
throws IOException {
if (linkDepth >= MAX_SYMBOLIC_LINK_DEPTH) {
throw new IOException("too many levels of symbolic links");
}
return lookUp(dir, link.target(), Options.FOLLOW_LINKS, linkDepth + 1);
}
/**
* Returns the entry for the file in its parent directory. This will be the given entry unless the
* name for the entry is "." or "..", in which the directory linking to the file is not the file's
* parent directory. In that case, we know the file must be a directory ("." and ".." can only
* link to directories), so we can just get the entry in the directory's parent directory that
* links to it. So, for example, if we have a directory "foo" that contains a directory "bar" and
* we find an entry [bar -> "." -> bar], we instead return the entry for bar in its parent, [foo
* -> "bar" -> bar].
*/
@NullableDecl
private DirectoryEntry getRealEntry(DirectoryEntry entry) {
Name name = entry.name();
if (name.equals(Name.SELF) || name.equals(Name.PARENT)) {
Directory dir = toDirectory(entry.file());
assert dir != null;
return dir.entryInParent();
} else {
return entry;
}
}
@NullableDecl
private Directory toDirectory(@NullableDecl File file) {
return file == null || !file.isDirectory() ? null : (Directory) file;
}
private static boolean isEmpty(ImmutableList<Name> names) {
// the empty path (created by FileSystem.getPath("")), has no root and a single name, ""
return names.isEmpty() || (names.size() == 1 && names.get(0).toString().isEmpty());
}
}
|
