R_igraph_restore_pointer() should validate vertex IDs

[szhorvat]

R_igraph_restore_pointer() creates an igraph_t from the R-side representation. After PR #813, this function got some error checking, but a bit more is needed.

On the R side, edge IDs are stored as doubles, which are the same in all platforms we support. However, on the C side, they may be of different types with a smaller range than a double:

• In C/igraph 0.9, they are doubles, however, some of the igraph code won't work correctly if the values exceed the 32-bit signed integer range
• In C/igraph 0.10 they can either be 32-bit or 64-bit integers, depending on the platform. 32-bit platforms are still in use, e.g. Raspberry Pi

R_igraph_restore_pointer() should validate that vertex IDs are within the allowed range and will fit the target type that they are being copied to.

@krlmlr @Antonov548

[szhorvat]

Suppose we go ahead with the current plan and change the igraph object format for the next release (bumping the format version), but do not again change the format when we move to 0.10. Then a graph created with a 0.10-based R/igraph may contain edge IDs which are too large to use by 0.9-based R/igraph. The simple and cheap validation I am suggesting here would protect us from such problems.

[szhorvat]

To make this concrete, this code:

  for (igraph_integer_t i = 0; i < no_of_edges; ++i) {
    VECTOR(edges)[2*i] = VECTOR(from)[i];
    VECTOR(edges)[2*i+1] = VECTOR(to)[i];
  }

should get checks as follows for 0.9:

    if (VECTOR(from)[i] < 0 || VECTOR(from)[i] >= INT_MAX) {
        IGRAPH_ERROR("Vertex ID out of range.", IGRAPH_EINVAL);
    }

(and the same for VECTOR(to)[i])

For 0.10, the upper bound check should be > IGRAPH_VCOUNT_MAX. Note > in 0.10 vs >= in 0.9.

[krlmlr]

Hijacking this thread to discuss if we should keep full compatibility with the graph format for this release.

I see two options:

• We change now a little bit, and we strive to keep the format unchanged for the foreseeable future. The format is "good enough", and interpretable from the R side. Downsides:
  • users can easily mess with the data, creating inconsistencies between the native igraph_t object and what's stored in R
  • we have two broken reverse dependencies now (plus one indirect)
  • we can't express graphs with more than 2^53-ish vertices, but we don't currently have computers with that much RAM [citation needed]
  • when recreating a native igraph object from the R data, we must copy from R to C, and we consume twice the memory
  • when serializing, we need to copy and consume twice the memory
• We don't change now, but we plan to change for igraph 0.10. We can pick an opaque zero-copy data structure on the R side, e.g., a byte (raw) array. Downsides:
  • we need to do a bit of extra work now, restoring oi, ii, os, is
  • users can still mess with our private data, but it's harder
  • what have I missed?

If we agree that an opaque data structure is better, I propose to wait with the data format change until we move to igraph/C 0.10. @szhorvat @ntamas @vtraag @Antonov548: Opinions?

[Antonov548]

Opinions?

For me both options are good. The 2nd for me sounds like extra work and rollback what we have now, but if you have ground of truth why this option if more preferable, I'm okay with this solution.

Do we really need care about private data? As example there is 2 packages which use copy of rigraph code to restore graph in C code, but we treet as something they need to change and don't do it again. As I understand we don't try to support such cases when user try to interupt in private internal representation.

[szhorvat]

First, as I said before, the versioning and upgrade mechanism should be properly documented, so that we all understand:

• What its capabilities and limitations are
• What breaks in case of a format change
• What needs to be done when the format is changed

There should also be a protocol for future format changes, so next time this needs to be done (which is unavoidable, realistically) nothing important gets forgotten or misunderstood.

---

Let me describe my (limited) understanding below, and hopefully others can correct me when I get something wrong, fill out any missing details, and answer the questions I have.

Format versions:

So far, there are three known format versions called "0.4.0", "0.7.999" and "0.8.0". Let's skip the discussion of 0.7.999 here.

Format versions are stored as strings, not numbers. This is a bit unfortunate because comparisons with < are character-wise lexicographic. For example, counterintuitively, "0.10.0" < "0.8.0").

The earlier format simply mirrors the contents of the C-side igraph_t (8 entries), and adds attribute storage (9th entry). The latter format does not change or remove anything from the earlier one. It simply adds an environment (10th entry), containing an UUID and the format version.

What is the purpose of the UUID, when is it used/needed?

Is it correct that nothing changed in the attribute storage?

Backward compatibility:

As far as I can tell, the latter format (0.8) is still usable with old igraph versions (0.4), and nothing was changed or removed. Only additions were made. Correct? This is something that may get broken with the next format change.

Forward compatibility:

• Under what circumstances is the old format not usable with current igraph versions? Is there any case when using an old format causes igraph to malfunction? Example?
• Is there any case when using the old format triggers an error message cleanly? Example? The check_version() function in versions.R would do this, but as far as I can tell it is never used.
• Is there any case when the format is automatically upgraded? When? Example? (warn_version() suggests that there is.)

My understanding is that the format version is not generally checked by igraph functions, except in special circumstances. Thus unfortunately there is no mechanism in place to reject future format versions, e.g. an igraph object with a version number 0.9.0 would not be cleanly rejected by the current igraph. Correct?

---

Let's continue after we are sure that we are all on the same page, and after we have the answers to the questions I asked above.

[szhorvat]

It would have been better to start this discussion elsewhere (e.g. in a new issue or the forum) since it is unrelated to the topic of this issue. Unfortunately I can't see a way to move it, so let's keep it here now.

---

Assuming that what I wrote in the previous comment is correct (though some questions from that comment still need answers), I think the situation is as follows:

The current format versioning system is inadequate for the kinds of changes that we are planning to do—that we cannot reasonably avoid doing in the long run, since igraph_t in C has already changed, and will change further. The current system only allows for adding to the igraph object, not removing elements or making changes. In other words, it is assumed that backward compatibility will be maintained forever, which is not sustainable.

We change now a little bit, and we strive to keep the format unchanged for the foreseeable future.

What the above means to me is that slight changes are not feasible. We either maintain full backwards compatibility, or have a clean start. Only partial backwards compatibility is not a good idea, it's a mess—it should be all or nothing. It should absolutely be avoided that newer format igraph objects cause serious yet not always immediately apparent malfunction in older igraph versions.

Since maintaining the current format won't be sustainable in the long term, it's clear to me that eventually there will need to be:

• A completely new format that will trigger an immediate error in old versions, under all circumstances. It should never happen that a new format is accepted, yet misinterpreted in old versions.
• A revamped and improved format versioning system so these issues would never come up again in the future. In particular, igraph should always do a check on the format version of objects, and reject anything that is incompatible. This includes a check whether the format is too new. Ideally, old formats should be upgraded automatically, or if this is not possible, the user should get an informative message with clear instructions for performing a manual format upgrade. This is all feasible by adding the format version checks to the function that translates the R-side igraph object to the C-side one.

@krlmlr, you suggested that if we create a new format, it should be opaque and use a raw byte array. In the meeting, you used the term "obfuscation" as a means of discouraging users from modifying the internal structure. I strongly disagree with the idea of obfuscation, as it makes our job much harder and increases the chance of mistakes.

Why can't we start with a clean, non-obfuscated object format that encodes the graph in a compact and R-compatible representation that is actually long-term sustainable even if igraph_t changes? The following seems reasonable:

• Format version should be encoded into the first entry as a simple integer (not string). This allows checking format compatibility even if the number of entries is changed in the future.
• Number of vertices as double
• Directedness as logical
• Edge list as double
• Attributes

This is compact and takes less than half the memory than an igraph_t would, as only the edge list is stored, not any of the internal indexing information.

Then just as you suggested originally, an associated igraph_t would be created dynamically upon first need, and maintained as needed. The reverse conversion from C -> R would also be done only when needed, you mentioned that this is possible using ALTREP. Thus the R-side edge list wouldn't even need to take up memory unless the object is serialized.

• when recreating a native igraph object from the R data, we must copy from R to C, and we consume twice the memory

• when serializing, we need to copy and consume twice the memory

With the above, we only use 1.5 extra memory instead of 2x.

• users can easily mess with the data, creating inconsistencies between the native igraph_t object and what's stored in R

There is no evidence that this has happened in the past.

leidenAlg and leidenbase are a special and rare situation, they simply did not see a different efficient way of doing what they wanted. Addressing this is a different discussion.

• we can't express graphs with more than 2^53-ish vertices, but we don't currently have computers with that much RAM [citation needed]

This is not a real concern for the time being. It's not only that the majority of current hardware can't even address that much memory, parts of C/igraph assume that integers can be represented in doubles (so this would need fixing first) and more important: R invested heavily in doubles and uses them for indexing vectors. R itself would need significant changes to handle that much memory.

• We can pick an opaque zero-copy data structure on the R side, e.g., a byte (raw) array.

I'm not sure if here you meant to copy the igraph_t bit-by-bit into a byte array. If so, that's not possible because:

• An igraph_t contains multiple pointers, i.e. it is not laid out contiguously in memory
• The bitwise representation is not the same across platforms (think e.g. 32-bit vs 64-bit)
• The internals of igraph_t will almost certainly change in the future, and this must not induce major and difficult changes in the R side. Ideally it should require no changes at all on the R side.

So the remaining motivation for the byte array, if I understood you, is obfuscation, which is a bad approach for preventing user-modification. See the arguments I gave above.

---

As for the timeline of when the new format should be implemented, this depends on your workload @krlmlr, so no input from me. It does make sense to verify that the new format is usable with both 0.9 and 0.10, as this proves that it's suitable for long-term use. But that does not mean that we need a release with 0.9. Overall, while not a small project, it seems to me it also won't be too much work and we can use most of what's already been implement by @Antonov548.

[ntamas]

What is the purpose of the UUID, when is it used/needed?

I think (but I don't know for sure) is that the UUID serves the purpose of identifying a specific graph without holding an explicit reference to it. For instance, a vertex selector created from a graph can hold the UUID of the graph that it belongs to so we can easily identify cases when a user tries to use a vertex selector with a different graph, without preventing R from garbage-collecting the graph when there are no references to it any more. (Standard R weakrefs probably won't do because it seems like R cleans up objects having weakrefs only when it returns to the top-level REPL).

Format versions are stored as strings, not numbers. This is a bit unfortunate because comparisons with < are character-wise lexicographic.

Again, I think that we can simply switch to a plain version number instaed of a major.minor.patch structure, starting from version "0001" (as a string) now. This way we can keep the version number as a string but we are safe for the foreseeable future (until version 9999). Or, we can start using semver from metacran (or something similar) and parse the version number on-the-fly into major.minor.patch versions for comparison.

Also, I would simply assume that all the igraph objects in the wild now are essentially at the latest version. It's been literally years since the storage format of igraph changed for the last time. So I don't think it's worth spending a lot of time in thinking about "Under what circumstances is the old format not usable with current igraph versions?".

Is there any case when using the old format triggers an error message cleanly?

There are unit tests for the upgrading process in tests/testthat/test-versions.R and tests/testthat/test-old-data-type.R. I don't know how extensive those tests are, but there have clearly been attempts to make sure that this works reliably.

Is there any case when the format is automatically upgraded? When? Example?

I don't think there is.

Format version should be encoded into the first entry as a simple integer (not string).

I fully support this idea. In my experience there has rarely been a need to use proper semantic versioning for formats of data structures.

Ideally, old formats should be upgraded automatically

I don't think this is possible with R's pass-by-value semantics. Basically, if you pass a graph into a function and that function upgrades the graph representation internally, it means that an invisible, internal copy of the graph is created, upgraded, and then thrown away.

That being said, and all things considered, I support @szhorvat 's idea about creating a new data structure that contains the number of vertices, directedness, an edge list and an attribute table only. Not sure what to do with the version number, though. Currently the first element of a graph (as a list) is the number of vertices. It can easily be mistaken for a version number in the time period when the old and the new formats co-exist. But we could make it so that the first element is NULL or NA, the second element is the version number, then the number of vertifes, directedness, edge list and then an attribute table.

[maelle]

@schochastics is this relevant for the ISC milestone?