implement `reify` function

[agarwal]

val reify : (abs,'kind) path -> (abs,'kind) path Or_error.t Deferred.t

Should check that given path corresponds to an actual path on the file system. Instead of returning just a bool, also transform Dir and File components to Links corresponding to what the actual path on the file system has.

There is no follow links option. By definition, reification requires links to be followed.

[pveber]

I'm currently writing this function, which happens to be needed for fold. I encountered a very delicate issue though: what should reify do in presence of cycles? In principle it should build a path with mutually recursive parts in it, but I see no way of doing that with purely functional data types. Of course, building a particular ADT with mutually recursive parts can be done (see for instance in our tests), but doing it for cycles of dynamically-known size is another matter.

Any idea?

[agarwal]

Consider that we want to reify abs_dir "/a/b/c", and it turns out b is actually a link to /a. The answer (in pseudo-notation) is:

[Item Root; Dir "a"; Link ("b", [Item Root; Dir "a"]); Dir "c"]

The result represents a cyclic path, but we didn't have to construct a cyclic OCaml value. So there is no problem, or am I missing something?

What could happen is that in the process of reification, the traversal itself leads us into an infinite loop. I see this as no different than fold. Such a case should be detected, and we have to return an error. Is this the troublesome case? Were you thinking that ideally we could return a Path.t even here?

A related question. Are link targets in the result of reify themselves reified? It would be better if they were, which increases the chances that we hit infinite loops.

[pveber]

Well, you got the issue perfectly

Consider that we want to reify abs_dir "/a/b/c", and it turns out b is

actually a link to /a. The answer (in pseudo-notation) is:

[Item Root; Dir "a"; Link ("b", [Item Root; Dir "a"]); Dir "c"]

The result represents a cyclic path, but we didn't have to construct a cyclic OCaml value. So there is no problem, or am I missing something?

No problem, this will work properly. The problem comes when a link A has a link B in its target and B has A (or longer chains).

What could happen is that in the process of reification, the traversal itself leads us into an infinite loop. I see this as no different than fold. Such a case should be detected, and we have to return an error. Is this the troublesome case? Were you thinking that ideally we could return a Path.t even here?

Yes I thought so, but failed to see how to implement it. In principle you could build such a value (I think).

A related question. Are link targets in the result of reify themselves reified? It would be better if they were, which increases the chances that we hit infinite loops.

Yes, there is no choice but to reify their target if you want to reify a link.

I think I get the problem better now: a link in a path implies a rewrite (understood like in rewriting systems). If a link doesn't rewrite itself in a finite number of steps to a link-free path then it cannot identify an object in a filesystem and should be considered broken (intrisically broken, whatever the filesystem you query with it). In particular, resolution will fail on them (currently it loops endlessly!). Now we could decide that reify cannot work on paths that can't be resolved. fold will only call the accumulation function on path that contain links only as the last item. In case such a link cannot be resolved (because it would trigger an infinite loop of rewritings), then the accumulation function is called on a Broken_link case.

[pveber]

An implementation of reify is available since 9e983dd. It's been tested a lot already, so even though I can't guarantee it absolutely bug-free, I think it's reasonably ready.

[agarwal]

Okay, so closing this issue.