buffered input (examples?)

[Michel Fortin]

On 2011-02-07 13:25:53 -0500, spir <denis.spir at gmail.com> said:

> On 02/07/2011 03:40 PM, Michel Fortin wrote:
>> On 2011-02-07 08:24:32 -0500, spir <denis.spir at gmail.com> said:
>> 
>>> Does this have anything to do with currently discussed buffered input ranges?
>>> If yes, how does such a design, or any alternative, fit their proposed
>>> interface?
>> 
>> You can build all of this on top of a buffered input range. The buffered input
>> range is not an alternative for your complex parsing algorithm, it's just the
>> component managing the buffer.
>> 
>> Having the underlying range manage the buffer (as opposed to having your parser
>> algorithm doing it) means that the buffer implementation can vary depending on
>> the type of range. For instance, if you're parsing directly data in memory, the
>> buffered range can use directly this data in memory as the buffer, requiring no
>> allocation and no copy; if you're parsing from a file or a network stream it'll
>> use a more standard buffer.
>> 
>> But how exactly the buffer is implemented does not affect your parsing
>> algorithm in any way. That's the great thing about it, separation of concerns:
>> your algorithm will work independently of the buffer implementation used. All
>> your parser algorithm has to do is say "shiftFront" and "appendToFront" to
>> control what's available in the buffer.
> 
> Right, that's nice. But I was certainly unclear. My question was in 
> fact how to make the lexeme stream be a buffered range. So that, 
> precisely, the parser does not have to cope about buffering (or rather 
> has to cope about it the std way clients will use to cope with buffered 
> ranges once they are standardised).
> In my hypothetical design, store() and unstore() are commands used to 
> manage buffering, thus similar in purpose, but different from what 
> Andrei's proposal provifdes. They just match the way I see a parser's 
> needs, naively. Now, how to translate this design to make the lexeme 
> stream a buffered range is very unclear for me; needed operations do 
> not directly translate to appendToFront / shiftFront (unless I do not 
> understand their action). I'm not even sure whether it would be simply 
> correct to use a buffered range.

You'd probably need a wrapper around the buffered range to handle 
backtracking nicely. Something like this:

	struct Backtracker(R) {
		R bufRange;
		size_t backtrackLength;

		ElementType!R front() @property {
			bufRange.front[0..$-backtrackLength];
		}

		void shiftFront(n) {
			bufRange.shiftFront(size_t n);
		}

		void backtrackFront(size_t n) {
			backtrackLength += n;
		}
		
		void appendToFront(size_t n) {
			if (backtrackLength <= n) {
				backtrackLength -= n;
			} else {
				bufRange.appendToFront(n-backtrackLength);
				backtrackLength = 0;
			}
		}

		void popFront() {
			assert(backtrackLength == 0, "mixin backtracking with by-chunk 
iteration not implemented");
			buffRange.popFront();
		}
	}

Perhaps this "backtrackFront()" function could be an optional part of 
the standard buffered range interface. If an algorithm requires a 
backtracking buffered input range and the input range you're provided 
with does not support backtracking, then you can use a wrapper like the 
one I drafted above to make the input acceptable to the algorithm.

-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/