There are too many ring buffer implementations in the standard library

[ifreund]

As of commit e2cbbd0 I count at least 4 separate ring buffer implementations:

• std.fifo.LinearFifo - most generic, longest existing.
• std.RingBuffer - used only by zstd implementation but part of the public std API.
• lib/std/compress/flate/CircularBuffer.zig - internal to inflate implementation.
• lib/std/compress/lzma/decode/lzbuffer.zig - internal to lzma implementation.

The current std.RingBuffer implementation is not generic and only supports buffers of u8. It also only supports fixed-length ring buffers while std.fifo.LinearFifo supports a dynamically growable buffer. I think one of two things needs to happen here:

• std.fifo.linearFifo and std.RingBuffer need to make clear the tradeoffs between the APIs/implementations and present a meaningful choice between the two.
• Either std.fifo.linearFifo or std.RingBuffer should have its functionality merged into the other and be deleted.

The flate and lzma internal ring buffer implementations are both specialized to the code using them which is fine. However, I suspect they could benefit by using a more generic implementation as a backing data structure.

I don't know exactly what the resolution to this issue should look like, quality API design is quite tricky. However, I think it is important to address before stabilizing the standard library.

[dweiller]

I think a good first step will be for someone (probably easiest for the implementers) to describe the requirements of ring buffers in the various compression implementations. We can then think about what a unified API for a ring buffer that satisfies all these use cases would look like. I think we should remain open to the possibility that a unified ring buffer supporting all the use cases we have may not make sense to implement as there are many trade-offs you can make that may be preferred by the different compression APIs or a 'generic' one like std.fifo.LinearFifo.

For a start, here are features of the std.RingBuffer API that I don't think std.fifo.LinearFifo adequately supports at present:

• retrieving an arbitrary region of the ring buffer that may wrap (see std.RingBuffer.sliceAt and std.RingBuffer.sliceLast)
• reading data multiple times (std.fifo.LinearFifo sets read items to undefined); note that a 'read' API isn't actually needed by the implementation but users may want it¹
• writing without concern for clobbering existing data (only std.RingBuffer.write*AssumeCapacity functions are used), i.e. the buffer is always considered to be full and it is on the caller to make sure they read all relevant data before decoding the next block; the assert in std.fifo.LinearFifo(…).writeAssumeCapacity means it is not appropriate

Note that std.RingBuffer was originally written for the Zstandard implementation and I'd consider it specialized for use cases desiring the above properties with a known (but not compile-time known) maximum size; perhaps it or something similar could be used for all LZ77-style compression schemes.

I think one of two things needs to happen here:

• std.fifo.linearFifo and std.RingBuffer need to make clear the tradeoffs between the APIs/implementations and present a meaningful choice between the two.

• Either std.fifo.linearFifo or std.RingBuffer should have its functionality merged into the other and be deleted.

A third option is to move std.RingBuffer to std.compress.zstd.RingBuffer.

Footnotes

1. The Zstandard implementation does not need anything like a 'read the next item' API—they are just convenience functions for users of low-level APIs that decode into a ring buffer. The Zstandard implementation does currently make a single call to std.RingBuffer.readFirstAssumeLength in the reader interface, though a minor refactor could remove this. As far as the internals of std.compress.zstd are concerned a ring buffer that only tracks a write position but not a read position would be fine. ↩

[andrewrk]

There were even more ring buffer implementations than you thought:

zig/lib/std/http/Server.zig

Lines 11 to 15 in c0ec264

	read_buffer: []u8,
	/// Amount of available data inside read_buffer.
	read_buffer_len: usize,
	/// Index into `read_buffer` of the first byte of the next HTTP request.
	next_request_start: usize,

zig/lib/std/http/Client.zig

Lines 212 to 216 in c0ec264

	read_start: BufferSize = 0,
	read_end: BufferSize = 0,
	write_end: BufferSize = 0,
	read_buf: [buffer_size]u8 = undefined,
	write_buf: [buffer_size]u8 = undefined,

zig/lib/std/crypto/tls.zig

Lines 629 to 639 in c0ec264

	buf: []u8,
	/// Points to the next byte in buffer that will be decoded.
	idx: usize = 0,
	/// Up to this point in `buf` we have already checked that `cap` is greater than it.
	our_end: usize = 0,
	/// Beyond this point in `buf` is extra tag-along bytes beyond the amount we
	/// requested with `readAtLeast`.
	their_end: usize = 0,
	/// Points to the end within buffer that has been filled. Beyond this point
	/// in buf is undefined bytes.
	cap: usize = 0,

zig/lib/std/debug/FixedBufferReader.zig

Lines 8 to 9 in c0ec264

	buf: []const u8,
	pos: usize = 0,