4Paths are used by file systems as well as protocols to represent paths to files
5and other resources. We need a generic type safe way to represent paths in
6general and file system paths in particular.
11OS include files generally define PATH_MAX to 4K and NAME_MAX to 255,
12however, it is possible to create paths bigger than these depending on
18In general directory trees could be quite deep and a directory can contain
19millions of entries. A good benchmark to measure the efficiency of path
20representation would be to traverse a directory tree recursively and list all
21the nodes under the tree. We could do this many times so that we do not need a
22really big directory tree.
27A file system starts with just the root directory and then files are
28created in the file system by the user or by programs storing their data
29on the file system. When a directory or file is created, or when a directory is
30listed, the following operations are performed:
321. for lookups an existing directory name must be resolved based on the name
342. for creation the file name to be created is supplied by the user
36When the user asks the file system to lookup or create a file or
37directory in the file system:
391) The operating system passes the name, as it is without any changes
40 whatsoever, to the file system. or does it? Windows?
412) The file system may translate the name to its own conventions before a
42 lookup or create, e.g. it may
44 * change the name to upper case
45 * translate the name to 8.3 chars
46 * change the character encoding?
47 * change the unicode normalization form of the name (Apple)
49When resolving an existing directory name in the file system we need
50to supply a path which consists of component names separated by a separator
51byte. Separators are of no consequence to the file system, they are
52resolved by the OS and the path components are used to lookup the paths
53one components at a time. The path for lookup is acquired either by a
54user input, device input or by the program which previously got the path
55entries by traversing the file system itself.
571) When the path is acquired by a user input, the user input could be:
59 a) a literal string in the program
60 b) a path entered via an input device
61 c) a path coming from the network
632) If the path was previously acquired from the file system then the
64 best thing to do is to never change anything in the path and store it
65 as it is and supply exactly the same path when needed. That way we can
66 guarantee that the path remains exactly what it was in the file system.
68Handling String Literals
69========================
71The encoding of the source code file depends on the editor used and the
72encoding chosen when saving it. The string literals would be parsed
73by the GHC parser and then stored in the generated binaries as null
74terminated C string literals encoded in UTF-8 (see GHC reference). There are
75several possible points of failure here:
77a) GHC parser needs to interpret the source code encoding correctly.
78b) We assume that the editor does not perform any translation on the
79 literal as entered by the user e.g. it does not perform unicode
80 normalization on it. If it does then the string as entered by the user
81 won't remain the same when it reaches the file system.
82c) GHC parser stores the parsed string literal in UTF-8 encoding. We
83 assume that GHC does not perform any unicode normalization or any
84 other translation on the string.
86The UTF-8 encoded string literal can be passed as a blob of bytes to the file
87system or it can be converted to String type and re-encoded as UTF-8 both
88should work equivalently in this case.
90Handling Input From Devices
91===========================
93The path provided by the user would assume some encoding based on
94the terminal settings or the encoding assumed by the sender over the
95network. The correctness depends on the contract between the two parties
96e.g. the locale setting. We assume that we get a sequence of raw bytes
97from the input device. We need to use the sequence as raw bytes and send
98it as it is to the file system without any translation.
103We need to parse the path components by the separator bytes. We assume
104that the separator can be identified and removed correctly irrespective
105of the encoding. We also make sure that none of the bytes in the
106components is a separator byte.
108Also, we would join the path components by the separator byte
109irrespective of the encoding of the components. If the OS treats the
110path as a sequence of bytes and nothing else and the components do not
111have the separator byte then we are good, we know that the OS would also be
112parsing based on the separator as a raw byte.
114We may perform some validations on the paths such as the file names are
115not "." or "..". Such validations could be optional and we could also
116provide a way to not perform any validations and just blindly use the
117paths as provided by the user and let the file system/OS fail.
119File System Translations
120------------------------
122As we noted earlier, the file system may translate the paths before
123using them. For example, it may store the path after converting it to
124NFD unicode normalization. Translation may create some round tripping
125issues for programs. For example, a program may use a string literal
126which is stored in NFC and the file system converts it to NFD. Later,
127when the same path is retrieved from the file system and compared with
128the string literal that was to create it then it won't match. For such
129cases the programs need to understand the file system and perform
130comparisons by performing appropriate translations on the paths. To
131perform matching and translations correctly the program needs to
132correctly interpret the encoding specific to the file system.
137When we display the paths to the user then we are forced to interpret
138it according to some encoding, to display the path correctly we have to
139know exactly how the file system stores the path. Otherwise if we display
140it differently, the user may use the displayed result to find the file
143OS Specific Path Encodings
144--------------------------
146In general, the OS does not have to look inside the path components
147other than the ability to recognize the separator char to parse the
148path into components and to construct it from components. However, in
149some cases the OS may may have to look inside the path e.g. "." or ".."
150special paths on Unix.
152On Unix a path component is just a blob of bytes. The user can encode
153and decode this blob of bytes as they desire. All they need to care
154about is that the path separator byte is respected. However, the the
155path component blobs may be changed by the underlying filesystem
156e.g. apple HFS may normalize the path before storing, therefore, the
157representation may change when it is returned back to the user.
159On modern Windows systems a path component is UTF16-LE
160encoded. Theoretically, from the OS perspective, it does not have to
161look inside the path components other than determining whether a 16-bit
162unit represents the separator character, therefore, users can use any
163encoding as long as it encodes to 16-bit multiples and the separator is
164preserved as equivalent to the UTF16-LE representation.
166Type Safety Requirements
167------------------------
169* Safety against using an absolute path where a relative path is to be
172 * Validations for absolute or relative path when constructing a path.
173 * We cannot append an absolute path to another path
174* Safety against using a file name where a directory name is to be used and
177 * Certain validations can be performed e.g. file names cannot be "." or "..".
178 * We should not be appending more directory components to a file path
180In don't care situations we should be easily able to use any type
181conveniently or cast a type into another. It is desirable that the
182programmer can choose the safety level. For example, we should be able
183to instantiate a path type where we only worry about the distinction
184between Absolute and Relative paths but no distinction between files and
185directories or vice versa.
190* minimal dependencies, specifically streamly does not depend on bytestring
191* round-tripping safety wrt to file system returned paths
192* type safety for different path types
193* support Posix/Windows
194* support URI paths and other ways to represent paths where the separator could
200* Should we store path as separate components or single string with
203* Should we validate the paths returned from the file system or trust
204 those and use directly without any validations? Need to see if that makes
205 any difference to path heavy benchmarks. If we want to use it directly
206 then we have to store it as a single string.
208* Parameterize the low level APIs with the separator so that we can
209 support arbitrary separators when parsing or reconstructing paths.
211* The low level API can support path handling in trees/DAGs/Graphs in general.
212 For example, in trees we cannot have multiple parents of a child whereas in
213 DAGs that is allowed, in graphs we can have cycles. We may also need ways to
216* Do we need to support arbitrarily long paths i.e. streaming of path? We do
217 not need that for file system paths and file system paths are limited size
218 and operating system anyway requires them in strict buffers. In case of
219 graphs if we have cycles paths can be infinite, we could generate a stream of
220 path and the consumer could be traversing the graph according to the
221 generated stream. If we want to support streaming then we have to store paths
222 as a stream of chunks rather than a single string.
224* In general, paths need not be strings, e.g. they can be references to
225 locations in memory or they can be IP addresses of nodes. At an abstract
226 level, paths are just a stream of tokens that represent a certain traversal.
228* Relative paths are the most general representation. At a low level,
229 all paths are relative, absolute paths are relative to a specified root
230 whereas relative paths are relative to a dynamic root which is the
233* Windows can have the root as different drive letters. So to represent paths
234 with a root in general we can also store the specific root along with the
235 path. In case of POSIX this will always be "/". In general, it could be a
236 host name or IP address or dependent on the protocol whose path we are
239* We can parameterize the low level path type with the type of path e.g. POSIX,
240 WINDOWS, HTTP etc. In general, programs may have to manipulate different
241 types of paths at the same time. High level path types can be instantiated
242 using the low level type therefore they can be much simpler as desired.
247Some related links found by web search:
249* https://gitlab.haskell.org/ghc/ghc/issues/5218
250* https://nodejs.org/fr/docs/guides/working-with-different-filesystems/
251* https://unix.stackexchange.com/questions/2089/what-charset-encoding-is-used-for-filenames-and-paths-on-linux
252* https://docs.microsoft.com/en-us/windows/win32/intl/character-sets-used-in-file-names
253* https://beets.io/blog/paths.html
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list