WIP: Implement Filesystem TS

[Marc Glisse]

On Mon, 4 Aug 2014, Jonathan Wakely wrote:

>> (N4099 writes --end() in a few places, I don't remember seeing text 
>> explaining that this is ok even if end() returns a pointer, while we do 
>> have text explaining what end()-1 means)
>
> The synopsis in [class.path] declares path::iterator as a class type,
> so it can't be a pointer.

So we can't directly use list::iterator for instance because it is a 
typedef and not a new class? And even less vector::iterator which on some 
implementations is a pointer.

If we want to force iterators to be classes, why not, but sneakily 
starting with path seems strange. typedef unspecified would be more 
consistent with the current library.

Or are there functions overloaded on path::iterator that I missed?

>> I find it a bit scary that this wart in the standard (the iterator concepts 
>> mix traversal and access properties) has such an impact on the design of 
>> the rest of the library. We might still have kept a vector with the indices 
>> of the '/' or something, but having never looked at the FS proposals I was 
>> expecting iterators to return something similar to a string_view. Now I 
>> agree you have little choice with the current wording (I didn't check the 
>> status of the LWG issue about iterators returning references to themselves 
>> but you nicely added a reminder of what the conclusion was :-).
>
> Yes, while I was doing the final editorial review on the TS I realised
> the design meant path objects must contain other path objects.

In my opinion, the path iterator should be an input iterator that 
additionally supports operator-- etc (all properties of a bidirectional 
iterator except for return-a-reference). The concepts should adapt to what 
we want to do, we shouldn't try to shoehorn our designs into bogus 
concepts.

> I decided to implement the TS to make sure I wasn't missing anything
> else non-obvious. I struggled for a while to find some way to
> implement the path::iterator type without having paths contain other
> paths and couldn't find a solution. The enumeration identifying the
> path type is needed so that the child paths don't also try to fill a
> std::list of child paths and so on forever until either the stack or
> heap runs out of space!
>
> Boost's path::iterator uses the Boost bidirectional_traversal_tag and
> claims its category is bidirectional iterator, but as it returns a
> reference to a path object inside the iterator it fails to meet the
> forward iterator requirements (specifically [forward.iterators]/6).

Internally they usually check the traversal tag and whether operator* 
returns a reference to deduce the iterator category, they can't really do 
much more, programmatically. Maybe they could specify things explicitly in 
this case though (I didn't check their implementation).

>>> * It might be possible to optimize path by lazily populating the
>>> std::list, so that copying paths and passing them around by value
>>> just copies the basic_string containing the native path, and it only
>>> gets parsed to find the individual components as needed.
>> 
>> Or we could parse eagerly and not need to store the full string, but that's 
>> probably less efficient if we are going to need the string soon to pass it 
>> to the system.
>
> I believe the generic_string() members defined in
> http://cplusplus.github.io/filesystem-ts/working-draft.html#path-generic-obs
> could be reconstructed from the individual components, but not the
> native() string.
>
> http://cplusplus.github.io/filesystem-ts/working-draft.html#path-append 
> defines operations in terms of concatenating the native() strings, not on 
> normalized forms.
>
> IIUC the full string must be kept around, it might contain information
> not in the parsed version, e.g. path("foo//bar") and path("foo/bar")
> have the same individual components, but different values for
> native().

Ah, indeed they chose to do things this way (there were a number of other 
possibilities, including empty components).

>>> * directory_iterator holds a shared_ptr<_Dir> where _Dir is a pimpl
>>> class containing a DIR* returned by opendir(), a path object
>>> containing the path the dir was opened with, and a directory_entry
>>> object that gets returned by dereferencing the iterator. It also
>>> contained a file_type enumeration, which gets used on GNU and BSD
>>> platforms where the dirent struct contains the file type, which
>>> means no stat() system call is needed to find out whether the
>>> current entry is a directory and should be recursed into.
>>> 
>>> * recursive_directory_iterator holds a shared_ptr to a
>>> stack<pair<_Dir, directory_iterator>> representing each directory
>>> recursed into and the position within that directory. The
>>> shared_ptr<_Dir>s belong to the directory_iterator objects in the
>>> stack alias the shared_ptr held by the parent
>>> recursive_directory_iterator, so the reference counts are shared by
>>> the whole stack.
>> 
>> I don't understand the last sentence of this paragraph.
>
> Sorry, it should have said "... belonging to the directory_iterator
> objects in the stack ..."
>
>> I don't know what a parent recursive_directory_iterator is, and from what I 
>> understand each directory_iterator in the stack iterates on a different 
>> directory so there is nothing to share.
>
> Every directory_iterator contains a shared_ptr<_Dir>. This is good for
> users working with directory_iterator explicitly, because copies of
> the same directory_iterator refer to the same underlying "sequence",
> and all the state is stored in the _Dir object (directory_iterators
> are single-pass input iterators, like the DIR struct operated on by
> readdir()).

Yes, this seems to be a common way to implement iterators in terms of a 
stateful range.

> A recursive_directory_iterator contains a shared_ptr<_Dir_stack>,
> where the stack contains N directory_iterators (one for each directory
> level that has been recursed into). Again, sharing the underlying
> state between different recursive_directory_iterator objects is
> desirable, and having the underlying state live external to the
> recursive_directory_iterator objects themselves is necessary.
>
> A naive recursive_directory_iterator implementation such as
> std::shared_ptr<std::stack<directory_iterator>> would have N+1
> different shared_ptr control blocks with separate reference counts.
>
> However, those directory_iterators in the stack owned by a
> recursive_directory_iterator will never be shared, because they are
> not exposed directly to users, so their shared_ptr members would
> always have use_count()==1. Having N reference counts that are always
> equal to 1 is wasteful.
>
> One solution would be for recursive_directory_iterator to not use
> directory_iterator, but work with a stack of unique_ptr<_Dir> objects
> instead, re-implementing the required directory_iterator members that
> operate on the _Dir object. I didn't try that, but I think it would
> work.
>
> My recursive_directory_iterator implementation instead uses
> shared_ptr<stack<pair<_Dir, directory_iterator>>>, where the
> shared_ptr<_Dir> held by each directory_iterator shares ownership with
> the shared_ptr<stack<...>> (using the shared_ptr aliasing constructor)
> so there is only a single control block for the whole group of
> objects.

Ah, ok, I really should pay attention to new classes, I had made some 
assumptions on how shared_ptr works that don't match reality and thus I 
didn't realize this was possible.

It looks like, as is often the case, the iterator interface is a pain to 
implement, where a range interface would be a bit easier (the stack 
doesn't need to be in a shared_ptr), and a foreach interface (or output 
iterator) would be trivial (especially if we don't mind recursive calls 
crashing for huge directory depths). It is a good thing there will be slow 
system calls in the middle or all this overhead might be a bit painful.

The range interface looks strange. Not sure why they are reusing 
directory_iterator instead of creating a separate directory_range. It 
doesn't matter much though.

> Does that make it clearer?

Yes, thanks a lot for the explanations.

On Tue, 5 Aug 2014, Jonathan Wakely wrote:

> On 04/08/14 23:36 +0100, Jonathan Wakely wrote:
>> One solution would be for recursive_directory_iterator to not use
>> directory_iterator, but work with a stack of unique_ptr<_Dir> objects
>> instead, re-implementing the required directory_iterator members that
>> operate on the _Dir object. I didn't try that, but I think it would
>> work.
>
> Or it could just use std::stack<_Dir> ... but I think I did try that
> and hit some issues. Maybe I should try again because ...

stack<_Dir> makes sense to me...

> I've realised there's a problem with this code, I'm not correctly
> breaking the reference cycles when a recursive_directory_iterator is
> destroyed with depth() != 0, so leaking memory. I'll fix that ...

Sounds more like a detail than a true design issue.

-- 
Marc Glisse