Pijul

Asymmetry between contexts above and contexts below?

I just read the nice, detailed blog article Towards 1.0. One thing described there seemed strange to me, namely the fact that deletions are made by marking edges. I had expected the vertices to be the objects to be marked, since they correspond to content and it’s content that is deleted.

What is the reason for marking edges instead of vertices? Moreover, what is the reason for marking incoming edges instead of outgoing edges? Doesn’t this introduce an asymmetry between contexts above and contexts below? If I would add changes to an empty repository A and add the reverse changes to an empty repository B, where “reverse” means that all contents run backwards, would it be guaranteed that B behaves analogously to A with respect to things like merging?

This is because marking the edges allows to have conflicting markers, since a vertex can have multiple incoming edges.

And yes, it introduces an asymmetry, but that’s ok. The choice of the incoming vertex rather than outgoing is somewhat arbitrary, although there is a root vertex at the root of the filesystem, with no incoming edge, which is right since it doesn’t make sense to mark it.

1 Like

Is the asymmetry only in the data structure or also in the externally observable behavior of Pijul? If the latter, what exactly is this asymmetry and why is it considered to be okay?

It used to be externally observable (in Pijul 0.12, for example in deleted contexts), but I don’t think it is observable now.

1 Like

So if I would work with some repository A in some way and would work with another repository B in the “reverse way”, meaning I would do the exact same things except that all file contents would be reversed, I would get the same result in B as I would get in A, modulo reversal?

I’d say for a single file, probably. But then for multiple files, an upside down directed tree isn’t a directed tree.

Hmm, that sounds a bit worrying. An ordinary user certainly won’t think about repositories in terms of their internal representations and will probably expect Pijul’s behavior to be symmetric.

What would be a concrete example where a repository and its reversed version (like A and B above behave differently? Can they differ only in situations where there are two possible notions of the “right” behavior and you have to make a decision about what Pijul’s behavior should be anyhow? In this case, having a bias towards the top or the bottom of the file might be okay.

Sorry, I misunderstood that. Pijul doesn’t look at the contents of lines to perform its operations (except diff and output, obviously), so yes, in that sense, it is symmetric.

I guess now a misunderstanding has been introduced. :wink:

Let me try to describe what I mean with an example. It involves two repositories, A and B, where B is supposed to be the reverse variant of A. Each of these repositories contains only one file. I will describe the contents of this file using strings whose characters denote whole lines, so that, for example, the string XYZ denotes three lines with contents X, Y, and Z, respectively. The actual contents of the lines do not really matter, because, as you pointed out, operations like merging are content-agnostic. I’m rather using these letters to relate the contents of repository A to the contents of repository B: the line X in A, for example, plays the same role as the line X in B.

The initial contents of the file are XYZ in repository A and ZYX in repository B. The internal representation is XYZ in A and ZYX in B. Let’s call the state with the initial contents “state 1” for each of the repositories.

Now we insert a line U between X and Y in both repositories to arrive at what I call “state 2a”. The contents become XUYZ and ZYUX, respectively. Internally, the paths XUY and YUX are added to the respective representations. Each of these paths has an edge before and an edge after U, which stresses the fact that U is inserted between X and Y as opposed to it being inserted after X (or Y) or before Y (or X). We see that the representation of file contents supports a direction-agnostic view of insertion (although edges still point in a certain direction, of course).

In parallel to making the change just described, we change state 1 in a different way. We delete Y, which leads us to what I call “state 2b”. The contents become XZ and ZX, respectively. Internally, the edges XY and ZY are marked as “deleted”. The line Y together with its immediate context is now represented by XYZ and ZYX, respectively. We see that the representation has a bias, as it favors the incoming edge over the outgoing edge for marking the deletion. As a result, the lines that are connected to Y via the “deleted” edge are not the same in A and B (X vs. Z).

Finally, we merge states 2a and 2b to get into what I call “state 3”. I don’t know what kind of state the real Pijul would produce. However, it is at least conceivable to have a merging operation that treats repositories A and B differently at this point. The reason is that U in state 2a sits between X and Y, which are connected by a “deleted” edge in repository A but by an ordinary edge in repository B. A merge operation might, for example, introduce a conflict in repository A but happily place U before X in repository B, leading to ZUX.

Of course, I’m not claiming that this is indeed the way Pijul works. However, I’m wondering whether there are situations where Pijul shows such asymmetric behavior. That would be really unfortunate, in my opinion.

The representation of repository states has a bias for “deleted” markings, attaching them to incoming instead of outgoing edges. Since such a bias is not inherent to deletion as such, the current representation looks somehow wrong to me. That said, it might be perfectly okay to use it, but then it should be made sure, in my opinion, that the bias of the representation does not result in a bias of the observable behavior of Pijul.

Ok, so that was my first understanding, and I maintain what I said: I can’t think of an example where the asymmetry would be observable (it was the case before for context deletion conflicts, but this is now fixed).
However, as I said before, you are describing a single file, and as Pijul handles many files, I don’t quite know what it would mean to do that for folders, since deleting a folder also deletes the files below it, and this is not symmetric.

1 Like

Great to hear that everything should work out nicely for file contents.

Regarding the interaction of files and folders, you’re saying that “below” would now mean that a file or folder is inside some folder? Well, I think in this case an asymmetric handling isn’t really a problem. After all, it’s not just the representation that has a bias here. Instead the relationship between a folder and its contents is inherently asymmetric, independently of any representation. I think it’s only file contents that should be treated in a symmetric way, meaning that working with reversed contents shouldn’t result in a different behavior.