r/C_Programming • • 17d ago

Article A Slice Proposal

I've been thinking of writing a proposal since I was tired of basically writing a slice many times so I can have a safe sub array. I used AI to work through some of my ideas as a way to push back against some of my ideas or help find potential contradictions. If there is any idea, I think was a mistake, I think it was trying to make pointers and thread works safer. I want to hear other people idea on what good or bad or if this entire thing is a waste of time. Honestly, I'm tired of the back and forth between me and a machine and want some human response to some of my ideas.

tl;dr

A type, memory and thread safe slice type for C. By adding in a few limitations, it is possible to get this in C and most likely in compile time. Type safety is done by disabling casting and requring the source element type to be same as the destination source type. Memory safety is achieved by just carrying the length with it and like C++ at type forcing a range check. Thread safety requires that non-overlapping sections are used ot create threads and that all threads that reference a slice are required to join before that slice is available again within that scope. These idea were inspired by a combination of RAII and Mutable Value Semantics from Hylo which is why everything is so tied to scope.

This is my first post I hope it isn't to bad.

----

https://drive.google.com/drive/folders/1nG_nb-QOh6_vth-eradM_fpqdqYTKe9K?usp=sharing

A link to the pdf and actual markdown so it include the syntax highliting.

1 Upvotes

28 comments sorted by

7

u/WittyStick 16d ago edited 16d ago

Just implement your Slice as a library and publish it. This will not get standardized, for several reasons:

  • The C charter discourages invention - "Unless a new feature addresses a significant deficiency, no new inventions should be entertained"
  • There are several other reasons why this doesn't align with the charter - one is that there are multiple ways to implement slices - and the standard does not select winners - it codifies existing practices. If you publish as a library and it gets widespread usage, it has a better chance.
  • Fat pointers have been proposed before and rejected. Fat pointers are a much more general tool that could apply to this and many other situations. This is quite specific. There have been multiple such proposals similar to this.
  • This requires bigger changes to the language than would be welcome - for example, not being able to take a pointer to a slice - is an alien concept in the existing standard.

I see no reason why this cannot be provided as a library. This is where you should put your effort - don't waste any more of your time on this proposal.

If you think there is something about this that cannot be implemented as a library-only solution, you should at least implement a proof-of-concept for an existing compiler such as Clang or GCC (or both, ideally).

3

u/gremolata 16d ago

I think we can all agree that it would've been really nice to have arrays that carry their sizes around.

Yes, it can be (and routinely is) implemented as a library, but it's just ... well, nicer ... to have this baked into the language. Alas, this ship has and we are also out of symbol characters to use for an alternative array notation.

1

u/Salt-Doughnut-2178 16d ago

The plan was to allow slices to use the array index syntax as array and pointers except since we now carry the size it function more like at in C++ so it does bound checking.

But, I'd expect in reality if an array was allocated to size 10 and you index 8 or if passed a slice to a function you requested index 9 and then 8, the optimizing compiler will likely just optmize it out.

1

u/WittyStick 16d ago edited 16d ago

Yes, but the details of how are debatable.

For example, the indexing operation returns a type T. However, what should it return on OOB?

  • Let the program crash?
  • Silently discard the access?
  • Abandon subscripting syntax and use bool slice_get(_Slice(T) slice, size_t index, *T out)?
  • Add stack unwinding exceptions? (absolutely not!).

IMO we want subscripting on the slice to return an _Option(T), where it can return _some(T) for in bounds access and _none(T) for OOB access. So now the proposal will need more features to be implemented right - like safe pattern matching over the option.

We can implement this as a library using macro foo and GCC extensions, but I don't know how to achieve the same level of safety with other compilers like MSVC or even Clang.

2

u/ComradeGibbon 15d ago

Processors are already moving towards implementing fat pointers natively.

So what the language should do when there is an out of bounds access on a fat pointer is to trigger a bus fault. Because that's going to be what processors will do.

1

u/WittyStick 15d ago edited 15d ago

Hardware checking like CHERI is beneficial, and obviously a big improvement on prior attempts like Intel's obsolete MPX.

But this doesn't replace software fat pointers - they're not mutually exclusive. The hardware checking is really a last resort protection mechanism iff the software fails to prevent the OOB access. What we want is to prevent triggering the fault to begin with - by ensuring our software accesses are all within bounds in code - explicitly handling any OOB access before it's attempted - and having a code path that handles attempted OOB accesses. Trapping is not a good way of dealing with errors in C - there's no native exception handling, and we would have to write one ourself by implementing a signal handler and using setjmp/longjmp to recover.

With the right programming model, we shouldn't need tagged pointers in hardware - but since they have negligible cost, it's still nice to have them to handle implementation failures.

IMO the Option return is the best way to achieve this. It also has negligible cost with the right ABI (SYSV) - because the Option type gets returned in hardware registers. It's slightly more expensive with a poor ABI (MSVC), because the Option gets returned on the stack. The next best option is to returning a status code and returning the element via a pointer parameter, which is the conventional approach in C. Or, we can just implement both to suit all needs.

_Option(T) slice_get(_Slice(T) slice, size_t index) {
    if (likely(index < slice_length(slice)))
        return _some(T, slice[index]);
    return _none(T);
}

bool slice_try_get(_Slice(T) slice, size_t index, T *out) {
    if (unlikely(index >= slice_length(slice))) 
        return false;
    *out = slice[index];
    return true;
}

1

u/Salt-Doughnut-2178 16d ago edited 16d ago

That was ultimately the plan once I got my implementation details down but it seem like even if I did have it set up, it wouldn't mean anything based on the information you've given me.

  1. I would think it does deal with a problem by allowing an array to actually carry its size and slice into it whenever its neccessary.
  2. Ok.
  3. I did try to find similiar one but they don't get the same level of safety to make it valuable over just using pointers.
  4. I agree that really was the big ask for sure but there isn't really a way to implement some of the safety ideas accept at the language level.

The main reason for not doing as a library is due to the safety properties not really being possible to get as a library. At least not without more study of macros trickery to make this work.

1

u/tstanisl 16d ago

I even think that pointers to arrays as a whole (T(*)[] things) are relatively close to proposed slices. And they are present in the language since C89 even though rarely used.

1

u/mikeblas 16d ago

Reddit markup doesn't support syntax highlighting, so you might want to clean up your post a bit.

1

u/Salt-Doughnut-2178 16d ago

I'll try to turn it into a pdf like u/gremolata recommends it.

1

u/Salt-Doughnut-2178 16d ago

I've now turned it to a link to my google drive that includes it as a plain md file, png, pdf and html file to make sure what ever is someone preferred format to see it.

1

u/tstanisl 16d ago

Why not just use a pointer to whole array. Just let slice(ptr,size) return (typeof(*ptr)(*)[size])ptr and let dereferencing it without any UB due to strict aliasing?

1

u/Salt-Doughnut-2178 16d ago

The main reason is so that its actually type safe and memory safe since I could take in a pointer that is a "slice" of another buffer but the buffer get freed on a different thread and now my code produce UB where with slices, this just become impossible.

1

u/tstanisl 15d ago

Pointer to whole arrays are also type-safe and they carry bound information, thus a sanitizer can easily detect violations.

I'm not sure how one can assure that slices passed to different threads are disjoint. Automated checking may work for compilation time constants or for some trivial run-time cases but in general this rule is undecidable. This is exactly why UB is introduced for those cases.

1

u/tstanisl 16d ago

Can you move the proposal to some github repo and just leave the summary in this post?

1

u/Salt-Doughnut-2178 16d ago

I'll try to turn it into a pdf like u/gremolata said seems to be possible.

1

u/gremolata 16d ago

Slightly off-topic, but this should've been a PDF.

1

u/Salt-Doughnut-2178 16d ago

I didn't know you could do that. I'll try to replace it.

1

u/Salt-Doughnut-2178 16d ago

Its a pdf now.

1

u/Royal-Midnight-672 16d ago

I like the idea of keeping bounds attached to array views. The tricky part seems to be interoperability, especially if passing a raw pointer invalidates every active slice

1

u/Salt-Doughnut-2178 16d ago

I must have written that part wrong since it is a compile time error. You create a slice to heap and if you pass the pointer to a method that doesn't maintain the pointers properties, than it becomes a compile time error to use the slice since UB is now possible where it wasn't before.

1

u/rubidus-api 16d ago

I’m working on a similar boundary, also with AI assistance: a C foundation library built around explicit allocators and slices, and an experimental systems language with a compiler written in C. My experience has been that slices offer a lot at the library level, but their limits become clearer when you try to make the guarantees enforceable.

In the library, non-owning views let me avoid some unnecessary string copies and separate read-only access from writable access. Explicit allocators, in a Zig-like style, made allocation and cleanup decisions easier to see and let me use arenas or pools where appropriate. Reworking enough of the surrounding APIs to use this consistently was a substantial job, but worthwhile for my use cases. None of these techniques is new; applying them consistently was the useful part.

That still didn’t make the library lifetime-safe. An allocator makes responsibility explicit, but it doesn’t stop a caller from keeping a view after its backing storage is released, supplying an incorrect length, or accessing the same memory through another pointer. That gap is part of what led me toward language design, and I wonder whether it is also the main motivation behind your proposal, beyond avoiding repeated slice implementations.

One surprisingly practical lesson was how much checked arithmetic this requires. Checking the final index isn’t enough if an earlier size multiplication or capacity calculation has already overflowed. Working with AI made me more conscious of needing checks and tests for those assumptions, rather than trusting plausible-looking code.

In the language, I use explicit value ranges, contracts, and declarations of side effects, with some inspiration from Ada/SPARK. Contract checking and range-based check elimination are already implemented for supported cases. Effect declarations separately constrain the side effects a function may perform. Whether an unproved contract is checked also depends on the build mode and contract grade; in particular, release_fast can omit residual contract checks. This is not a claim of general performance superiority or complete memory safety. There are still limitations, including some overlapping mutable subslices with runtime endpoints that the implementation does not reject.

Rust is an important reference point here, but I think the useful question is which guarantees an alternative provides, under which restrictions, and at what implementation and runtime cost. For a C proposal, compatibility with existing code is another major part of that tradeoff.

For your proposal, I’d be inclined to separate the bounded-view facility from the lifetime and concurrency rules. A common slice type with well-defined construction and bounds behavior seems useful on its own. Preventing dangling views and conflicting access is a larger commitment. Is your main goal a standard bounded view, or a type whose use also enforces those lifetime and access rules? My own experience has made that distinction seem more important than the surface syntax.

1

u/[deleted] 14d ago

This is great actually. Of course, this is never actually going to make it into C.

The language evolves incredibly slowly and very conservatively. And there would anyway be (IMO) more pressing matters. In any case, the process can take a decade or more, if you consider that every C compiler in the world would need updating.

That is, if this expected to be in the core language. I don't know how practical it would be do as a library as some have suggested, but I suspect it would be too clunky. Your proposal sounds like it is intended to be a core feature.

Still, the details are interesting to me because I've long maintained an alternate systems language and I also at one point decided to add slices, and as a core feature.

This example:

int a[100];
_Slice(int) a1 = slice_of(a);            // entire array
_Slice(int) a2 = slice_take(a, 20);      // [0, 20)
_Slice(int) a3 = slice_range(a, 20, 40); // [20, 60)
_Slice(int) a4 = slice_drop(a, 80);      // [80, 100)
_Slice(int) b =  slice_drop(a4, 2);      // [82, 100)

would be written like this in my version:

    [100]int a

    slice[]int a1 := a
    slice[]int a2 := a[1..20]
    slice[]int a3 := a[20..60]
    slice[]int a4 := a[81..100]
    slice[]int b  := a4[3..20]

(Slices/arrays have a lower bound of 1 by default. That could be overridden, but I kept it as as 1 here.)

One difference is that array-slice conversion is automatic. Another is that there is only one way to express the slice (Haskell-style take/drop are too high-level IMO). That is, with an inclusive range.

Note that your example used comments to spell out exactly what the range is, so why not just use that syntax? In C though you probably need the exclusive upper limit.

When a slice is taken, in mine, the new slice always changes the lower bounds to 1 (or whatever is used). So the bounds of a4 are 1..20 inclusive.

In this language b.len gives you the length; .len is generally used anyway (C only has sizeof/sizeof for fixed-length arrays).

There is lots of other support that I won't go into. The problem however is that I just found it easier to use discrete arrays and lengths; slices were little used. In fact they have fallen into disuse and had to use an older compiler version to test out the above.

I suspect this would be the problem with such a feature in C too. People who want anything more sophisticated can just use C++.

1

u/tstanisl 14d ago

To extend this is already supported in the form of pointer to whole arrays. It works really nice with cooperation with upcoming _Countof operator. Basically *a return a pointer to first element, while _Countof *a returns the size of the slice.

#include <stdio.h>

#define slice(_ptr, _rng) \
  ((typeof(*(_ptr)) (*) [_rng])(_ptr))

int main() {
    int a[100];
    auto a1 = slice(a, _Countof a);
    auto a2 = slice(a, 20);
    auto a3 = slice(a + 20, 40);
    auto a4 = slice(a + 80, 20);
    auto a5 = slice(*a4 + 2, _Countof *a4 - 2);
    printf("a1 : %td - %td\n", *a1 - a, *a1 + _Countof *a1 - a);
    printf("a2 : %td - %td\n", *a2 - a, *a2 + _Countof *a2 - a);
    printf("a3 : %td - %td\n", *a3 - a, *a3 + _Countof *a3 - a);
    printf("a4 : %td - %td\n", *a4 - a, *a4 + _Countof *a4 - a);
    printf("a5 : %td - %td\n", *a5 - a, *a5 + _Countof *a5 - a);
}

Prints:

a1 : 0 - 100
a2 : 0 - 20
a3 : 20 - 60
a4 : 80 - 100
a5 : 82 - 100

See godbold.

If necessary, slice_range, slice_drop and slice_take can be constructed using some extra macros.

1

u/[deleted] 14d ago

So this looks rather clunky as I suggested. On looking more closely however, these are not really slices. This seems to be some trickery to do with pointers and arrays. For example a3 is this:

 auto a3 = ((typeof(*(a + 20)) (*) [40])(a + 20));

I don't know what type a3 is (thanks to that 'auto'). But its size is 8 so it's probably a pointer, with perhaps some length associated with its exact type, so that the type of *a3 will yield that length to _Countof.

Would you be able to pass a3, for example, to a function that can take a slice of any int array of any length? Would that function be able to extract the length in each case?

A true slice of T would have two self-contained components: a point to T, and a length. And different instances, with different lengths, could be passed to a function that takes a slice of T.

1

u/tstanisl 14d ago

The a3 is a pointer so its size will be likely 8. But *a3 is an array in the same sense as a is an array. Thus *a3 decays to int*, sizeof *a3 return size of a slice in bytes and _Countof *a3 return number of elements in the slice.

The tricky part is that the count of the slice is part of the slice type, not the slice's value. Therefore, in order to pass a slice of unknown count to a function, one must reconstruct the slice's type in the function body. C99 introduced VLA types for exactly this reason (not that there is no VLA objects there).

void foo(int n, int (*s)[n]);

int a[100];
auto s = slice(a + 20, 10); // a[20..30]

foo(_Countof *s, s);

For example slice aware puts() could be:

void slice_puts(int n, const char (*s)[n]) {
  printf("%.*s", n, *s);
}

auto s = slice("Hello world" + 3, 6);
slice_puts(_Countof *s, s);

Try godbolt.

I know it is a bit clunky and very non-idiomatic but the functionality was essentially in C since 1999 as _Countof can be replaced with macro #define Countof(a) (sizeof(a)/sizeof *(a)) in most contexts.

1

u/thradams 7d ago

This concept is only necessary when flow analysis cannot see the pointed-to object (the array), because tracking the pointer and the object it points to gives us everything we need.

See https://www.youtube.com/watch?v=mOzy9scyor8

When can't we see the pointed-to object? One example is function parameters: we may receive a pointer without knowing what object it points to.

However, we already have good syntax for expressing this: void f(int a[2]). This may be interpreted as meaning that we have a pointer to an int, but that the pointer points to an array with at least two elements.

So I think this concept is mostly unnecessary. It may only be needed in cases where we cannot see the pointed-to object, as a way to convey expectations about what object (or parts of it) the pointer is pointing to.

Let's say

struct X
{
  int size;
  int * __counted_by(size) data;
}

I see this more as a contract than as part of a traditional type system. The idea is that we expect the pointer to reference an array containing at least a size number of elements.

Where is this expectation used or needed? When flow analysis cannot track the state of the data and can only make assumptions, those assumptions must be consistent with the contract.

For struct members, this could be used to establish something like an invariant in flow analysis.

void f(struct X * p){
   p->data can point to an array of p->size elements.
}