using random pointers, but only guarded by an if comparison

[nikomatsakis]

In #26, @arielb1 gave this example code. It takes a random *mut and dereferences it -- but only after double checking that it is a valid value:

fn example(foo_addr: *mut usize) -> usize {
    let mut data = 0;
    if pointers_equal(&mut data as *mut _, foo_addr) {
        unsafe { *foo_addr = 42; }
    }
    data
}

The challenge here is that we are using a *mut -- but only after (dynamically) comparing it for correctness. This seems to get at a key question: the extent to which users are permitted to think of the actions of the code as a kind of "turing machine".

Many legit (or potentially legit) uses of uninitialized memory have this general feeling.

Random but maybe unrelated example: I have at times used sets that require only O(1) initialization. For example, a set consisting of the integers 0..N might work like:

• index: [usize; N] // uninitialized
• members: [usize; N] // uninitialized
• count: usize

To add a new item i, you do:

• self.index[i] = self.count; self.members[self.count] = i; self.count += 1

To check if item i is present you do:

• let m = self.index[i]; m < self.count && self.members[m] == i

[arielb1]

gave this example code

Your specific example code is unlikely to be optimized because pointers_equal might access data. With a write inside the if-condition LLVM optimizes the code.

Random but maybe unrelated example

That's more about whether undef values can be "tamed".

[arielb1]

C's restrict is similar (https://gist.github.com/ubsan/780831ac58a281f131da2b461bc576d8), but rather vague on the subject:

Note the counterfactual:

a pointer expression E is said to be based on object P if ... modifying P
... would change the value of E.

6.7.3.1 Formal definition of restrict

1

Let D be a declaration of an ordinary identifier that provides a means of designating an
object P as a restrict-qualified pointer to type T.

2

If D appears inside a block and does not have storage class extern, let B denote the
block. If D appears in the list of parameter declarations of a function definition, let B
denote the associated block. Otherwise, let B denote the block of main (or the block of whatever
function is called at program startup in a freestanding environment).

3

In what follows, a pointer expression E is said to be based on object P if (at some sequence
point in the execution of B prior to the evaluation of E) modifying P to point to a copy of the array
object into which it formerly pointed would change the value of E. Note that "based" is defined only for
expressions with pointer types.

Note 119 - In other words, E depends on the value of P itself rather than on the value of
an object referenced indirectly through P. For example, if identifier p has type
(int **restrict), then the pointer expressions p and p+1 are based on the restricted pointer
object designated by p, but the pointer expressions *p and p[1] are not.

4

During each execution of B, let L be any lvalue that has &L based on P. If L is used to
access the value of the object X that it designates, and X is also modified (by any means), then the
following requirements apply:

• T shall not be const-qualified. Every other lvalue used to access the value of X shall also
  have its address based on P. Every access that modifies X shall be considered also to modify
  P, for the purposes of this subclause. If P is assigned the value of a pointer expression E that
  is based on another restricted pointer object P2, associated with block B2, then either the
  execution of B2 shall begin before the execution of B, or the execution of B2 shall
  end prior to the assignment. If these requirements are not met, then the behavior is undefined.

5

Here an execution of B means that portion of the execution of the program that would
correspond to the lifetime of an object with scalar type and automatic storage duration

6

A translator is free to ignore any or all aliasing implications of uses of restrict.

7 EXAMPLE 1

The file scope declarations

int * restrict a;
int * restrict b;
extern int c[];

assert that if an object is accessed using one of a, b, or c, and that object is
modified anywhere in the program, then it is never accessed using either of the other two.

8 EXAMPLE 2

The function parameter declarations in the following example

void f(int n, int * restrict p, int * restrict q)
{
    while (n-- > 0)
    *p++ = *q++;
}

assert that, during each execution of the function, if an object is accessed through
one of the pointer parameters, then it is not also accessed through the other.

9

The benefit of the restrict qualifiers is that they enable a translator to make an
effective dependence analysis of function f without examining any of the calls of
f in the program. The cost is that the programmer has to examine all of those calls
to ensure that none give undefined behavior. For example, the second call of f in g
has undefined behavior because each of d[1] through d[49] is accessed through both
p and q.

void g(void)
{
    extern int d[100];
    f(50, d + 50, d); // valid
    f(50, d +  1, d); // undefined behavior
}

10 EXAMPLE 3

The function parameter declarations

void h(int n, int * restrict p, int * restrict q, int * restrict r)
{
    int i;
    for (i = 0; i < n; i++)
        p[i] = q[i] + r[i];
}

illustrate how an unmodified object can be aliased through two restricted pointers. In particular, if
a and b are disjoint arrays, a call of the form h(100, a, b, b) has defined behavior,
because array b is not modified within function h.

11 EXAMPLE 4

The rule limiting assignments between restricted pointers does not distinguish between a
function call and an equivalent nested block. With one exception, only ‘‘outer-to-inner’’ assignments
between restricted pointers declared in nested blocks have defined behavior.

{
    int * restrict p1;
    int * restrict q1;
    p1 = q1; // undefined behavior
    {
        int * restrict p2 = p1; // valid
        int * restrict q2 = q1; // valid
        p1 = q2;                // undefined behavior
        p2 = q2;                // undefined behavior
    }
}

12

The one exception allows the value of a restricted pointer to be carried out of the
block in which it (or, more precisely, the ordinary identifier used to designate
it) is declared when that block finishes execution. For example, this permits
new_vector to return a vector.

typedef struct { int n; float * restrict v; } vector;
vector new_vector(int n)
{
    vector t;
    t.n = n;
    t.v = malloc(n * sizeof (float));
    return t;
}