Clarify relational operators (>,<,>=,<=) applied to PTS operands

[Former user]

Originally reported on Google Code with ID 104

Steve noted in our last telecon that the UPC spec is currently silent on the topic of
relational operators (ie >,<,>=,<=) on PTS operands. I suspect we all have a similar
intuition on how this should behave, but I believe the text inherited from C99 leaves
some ambiguities, at least in the presence of definitely-blocked PTS.

Here is the relevant text from C99 6.5.8:
-------------------------------
Constraints:
— both operands are pointers to qualified or unqualified versions of compatible object
types; or
— both operands are pointers to qualified or unqualified versions of compatible incomplete
types.

Semantics:
When two pointers are compared, the result depends on the relative locations in the
address space of the objects pointed to. If two pointers to object or incomplete types
both point to the same object, or both point one past the last element of the same
array object, they compare equal. If the objects pointed to are members of the same
aggregate object, pointers to structure members declared later compare greater than
pointers to members declared earlier in the structure, and pointers to array elements
with larger subscript values compare greater than pointers to elements of the same
array with lower subscript values. All pointers to members of the same union object
compare equal. If the expression P points to an element of an array object and the
expression Q points to the last element of the same array object, the pointer expression
Q+1 compares greater than P. In all other cases, the behavior is undefined.
-------------------------------

There are several ambiguities here, arising from the existence of blocked shared arrays.
Specifically, unlike in C99, UPC lacks a tidy, predetermined total order over every
element of memory (because of the multiple shared heaps across threads), and with blocked
arrays it's possible for an element with a "higher" array index to correspond to a
"lower" addrfield on another thread (whose threadid may or may not be "higher" than
the thread with affinity to the current element). Consequently it's not enough to know
the two operands point to elements of the same array object - you also need to know
something about the phasing and blocking factor of the operands to provide a meaningful
comparison; see the related discussion on PTS subtraction in issue 73.

The second clause of the C99 constraints allows comparison of incomplete types, thereby
allowing expressions of the form:  
              (shared void *) < (shared void *)
Lacking any type information, this expression cannot provide a sensible answer when
the operands point to different threads. I believe the best fix is to simply prohibit
this case. Specifically, add a constraint that UPC PTS can only be compared using (>,<,>=,<=)
if both operands are pointers to compatible object types (ie adhere to the first case
in the C99 constraints and disallow the second).

Proposal part 1:
----------------
Add constraint to 6.4.2:

  Relational operators (as defined in [ISO/IEC00 Sec 6.5.8]) shall not be applied to
a pointer-to-shared with incomplete type.
  \footnote{Eg. The (>,<,>=,<=) operators may not have an operand with (shared void
*) type.}
----------------

We also need to add some text to clarify the semantics of PTS comparison, to account
for blocked PTS. I think the simplest fix is to add a semantic paragrah defining the
semantics in terms of PTS subtraction, which already provide the necessary behavior.
Specifically, define (pts1 OP pts2) equivalent to ((pts1 - pts2) OP 0).

Proposal part 2:
----------------
Add semantic to 6.4.2:

  When two pointers-to-shared are compared using a relational operator, as described
in [ISO/IEC00 Sec 6.5.8], 
  the expression {\tt pts1 $\oplus$ pts2} where {\tt $\oplus$ $\in$ \{>,<,>=,<=\}}

  is equivalent to: {\tt (pts1 - pts2) $\oplus$ 0}. 
  If the result of the subtraction is undefined, so is the result of the relational
operator.
----------------     

Reported by danbonachea on 2012-11-29 16:28:08

[Former user]

It's worth noting that under this proposal, if you compare two out-of-phase pointers
into the same shared array using (>,<,>=,<=), you will get an undefined result, whereas
comparing them using == or != gives a well-defined result. However, as described in
issue 73, applying binary operators to combine out-of-phase PTS is already a very "sketchy"
programming practice that we want to strongly discourage, so I don't see this as a
problem.

The == and != operators are also more permissive in that they allow (shared void *)
operands (and other incomplete types).

Reported by danbonachea on 2012-11-29 16:42:44

[Former user]

Proposal mailed 1/16/2013:

--- upc-language.tex    (revision 199)
+++ upc-language.tex    (working copy)
@@ -239,6 +239,13 @@
 \npf No binary operators shall be applied to one pointer-to-shared
     and one pointer-to-local.

+\xadded[id=DB]{104}{
+\np Relational operators (as defined in [ISO/IEC00 Sec 6.5.8]) 
+    shall not be applied to a pointer-to-shared with incomplete type.%
+    \truefootnote{Eg. The (>,<,>=,<=) operators may not have an operand 
+    with {\tt (shared void *)} type.}
+}
+
 {\bf Semantics}

 \np When an expression that has integer type is added to or
@@ -311,6 +318,13 @@
     AND {\tt upc\_phaseof(pts1 + x) == upc\_phaseof(pts2)}.
     In this case (pts2 - pts1) evaluates to x.

+\xadded[id=DB]{104}{
+\np When two pointers-to-shared are compared using a relational operator, 
+    as described in [ISO/IEC00 Sec 6.5.8], 
+    the expression {\tt pts1 $\oplus$ pts2} where {\tt $\oplus$ $\in$ \{>,<,>=,<=\}}

+    is equivalent to: {\tt (pts1 - pts2) $\oplus$ 0}. 
+    If the result of the subtraction is undefined, so is the result of the relational
operator.
+}

 {\bf Forward references:}  {\tt upc\_threadof} (\ref{upc_threadof}),
           {\tt upc\_phaseof} (\ref{upc_phaseof}), {\tt upc\_addrfield} (\ref{upc_addrfield}).

Reported by danbonachea on 2013-01-17 03:01:10 - Status changed: PendingApproval - Labels added: Consensus-High - Labels removed: Consensus-Low

[Former user]

Ratified at the 2/11/13 telecon and committed as SVN 203

Reported by danbonachea on 2013-02-11 22:55:02 - Status changed: Ratified