Re: scm_bits_t / scm_ubits_t

[Dirk Herrmann]

On Sun, 10 Jun 2001, Jacques A. Vidrine wrote:

> On Sun, Jun 10, 2001 at 07:36:00PM +0300, Michael Livshin wrote:
> > "Jacques A. Vidrine" <address@hidden> writes:
> > 
> > > On Sun, Jun 10, 2001 at 03:04:09PM +0300, Michael Livshin wrote:
> > > > size_t is fine for
> > > > vector lengths, but might not be enough for list and (bit) array
> > > > lengths.  
> > > 
> > > This may be true [1], but...
> > > 
> > > > we should use uintptr_t (or unsigned long) for those.
> > >                 ^^^^^^^^^
> > > 
> > > This is  wrong. uintptr_t should really  only be used to  hold pointer
> > > values.  If one  is looking for the largest unsigned  integer, then it
> > > would be  pretty safe to  have configure  check for the  following, in
> > > order:
> > 
> > this is not wrong because we don't look for the largest unsigned
> > integer type (well, in the case of list length, bit-array lengths are
> > trickier).  we are looking precisely for an integer type that has the
> > same width as a pointer (to be even more precise, same width as a
> > pointer to cell, but at this point the C standard stops cooperating
> > ;))
> 
> I hope I haven't got confused, but reading above I see two things:
>  
>    1. ``size_t is fine for vector _lengths_, but might not be enough
>       for list and (bit) array _lengths_.'' (emphasis mine).
> 
>    2. ``we are looking precisely for an integer type that has the same
>       width as a pointer''
> 
> These  are  different requirements.   I'm  suggesting  (1) should  use
> uintmax_t, and that (2) should use uintptr_t.  What am I missing?

I think the confusion is about the role of uintptr_t.

* Michael's position is the following:  uintptr_t is, at first, an
integral type, which can be used _exactly_ like, for example, unsigned
long.  The _only_ difference is the fact, that uintptr_t is _guaranteed_
to be wide enough to hold any pointer.  This information is not available
for the type unsigned long.  Thus, uintptr_t can be used to replace
unsigned long at places, where we demand that the type be _also_ wide
enough to hold any pointer type, independent of whether the actual
computation does involve anything dealing with pointers.

* Your position is instead:  uintptr_t is _intended_ to be used to store
pointers.  Nothing else should normally be stored in a uintptr_t.

In guile, we have the following situation:  The type of cell entries is
scm_t_bits, which we define based on uintptr_t.  Why is that?  A cell
entry must be wide enough to hold a pointer to another cell entry.  This
is scheme's mechanism to build lists.  Thus, we need a type that is wide
enough to store pointers.  This leads to our decision to use uintptr_t for
cell entries, even if there is _no_ pointer information stored in
there.  (Please note that this is already a kind of misuse with respect
to your position.)

Now looking into vectors, we find that:  Vector lengths are stored in a
cell entry.  Consequently, a vector length must fit into a scm_t_bits
type, which is uintptr_t.  Here, Michael does not care about any
_intended_ use of uintptr_t, but only about the guarantee about the type
width.  "Whatever integral type uintptr_t may be, we know that it is
large enough to hold any vector length."  On the other hand, to give
account to your position, it may confuse people if vector lengths are
stored in a variable of type uintptr_t, because that is not the way it
would normally be used.

Looking into list lengths:  A list in scheme is a sequence of pairs, each
pair is a cell, and the list is made up by having each cell's cdr hold a
pointer to the subsequent cell.  The consequence is, that a list of length
n is guaranteed to hold n different pointers to cells.  In the extreme
case, all cells in guile are connected in a single long list.  Thus, no
matter how much heap guile allocates, it must be possible to represent the
length of a list in a data type that is able to represent all pointers to
cells.  Thus, again we know that uintptr_t is sufficiently wide to store
list lengths.

Finally strings:  Guile's strings consist of a continuous memory region of
characters obtained from malloc.  That is an implementation detail and
might change, but as long as it is true we know that a string's length
must fit into a variable of type size_t.

Summarized:  Michael argues based on the type widths.  He does not take
any 'intended usage' recommendations into account.  Thus, formally, his
observations are correct.  But, using uintptr_t for list lengths and for
vector lengths may be confusing, since it is a somewhat non-conventional
use of these types.  Thus, according to your position, Michael's type
suggestions are not 'good style'.  They should work, however.

The suggestion to use size_t for all length types is for the sake of good
style, not for the sake of correctness with respect to the guaranteed type
widths:
* It is OK to use size_t to represent string lengths, as long as we
  don't change the string representation.
* Using size_t to indicate vector lengths is not strictly accurate
  (because of bitvectors) but still seems natural, because it matches the
  assumption that vectors are obtained via malloc.
* Using size_t for list lengths, well, is questionable, but for 
  the sake of symmetry with the other length types, it should be OK.  We
  could also have configure checks that verify that
  sizeof(size_t)==sizeof(uintptr_t) and otherwise refuse to build guile.

Best regards,
Dirk Herrmann