Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #76521 > unrolled thread

Data IO for project

Back to article view | Back to comp.lang.c

Contents

  Data IO for project "Morten W. Petersen" <morphex@gmail.com> - 2015-11-19 16:03 +0100
    Re: Data IO for project Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-19 08:12 -0800
      Re: Data IO for project "Morten W. Petersen" <morphex@gmail.com> - 2015-11-19 18:42 +0100
        Re: Data IO for project Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-19 12:15 -0800
        Re: Data IO for project Robert Wessel <robertwessel2@yahoo.com> - 2015-11-19 16:17 -0600
          Re: Data IO for project "Morten W. Petersen" <morphex@gmail.com> - 2015-11-20 01:16 +0100
            Re: Data IO for project Robert Wessel <robertwessel2@yahoo.com> - 2015-11-20 00:15 -0600
              Re: Data IO for project "Morten W. Petersen" <morphex@gmail.com> - 2015-11-21 00:37 +0100
    Re: Data IO for project Nobody <nobody@nowhere.invalid> - 2015-11-19 19:59 +0000
      Re: Data IO for project "Morten W. Petersen" <morphex@gmail.com> - 2015-11-20 01:26 +0100
        Re: Data IO for project Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-19 16:46 -0800
        Re: Data IO for project Nobody <nobody@nowhere.invalid> - 2015-11-20 05:08 +0000
          Re: Data IO for project Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 02:21 -0800
    Re: Data IO for project Ian Collins <ian-news@hotmail.com> - 2015-11-20 12:00 +1300
      Re: Data IO for project "Morten W. Petersen" <morphex@gmail.com> - 2015-11-20 01:19 +0100
      Re: Data IO for project asetofsymbols@gmail.com - 2015-11-21 12:29 -0800
        Re: Data IO for project Ian Collins <ian-news@hotmail.com> - 2015-11-22 12:13 +1300

#76521 — Data IO for project

Hi there.

So I'm working on my XML parser, and a while back someone mentioned that
having a feed(parser, data) function would be a good idea.

But how do I make that work in practice?  The XML parser loop would have
to wait for new input, and what's a good way to design that?  Same goes
for output and waiting for write access.

I also thought about creating high-level functions that can accept IO
from either a file stream or a network stream.  This could be built on
top of the feed function.

Is there any kind of stream the project also should be able to handle?

-Morten

[toc] | [next] | [standalone]

#76533

On Thursday, November 19, 2015 at 3:03:17 PM UTC, Morten W. Petersen wrote:
> Hi there.
> 
> So I'm working on my XML parser, and a while back someone mentioned that
> having a feed(parser, data) function would be a good idea.
> 
> But how do I make that work in practice?  The XML parser loop would have
> to wait for new input, and what's a good way to design that?  Same goes
> for output and waiting for write access.
> 
> I also thought about creating high-level functions that can accept IO
> from either a file stream or a network stream.  This could be built on
> top of the feed function.
> 
> Is there any kind of stream the project also should be able to handle?
> 
You don't.

You provide the functions along the lines of

XMLParser *createparser(void);
xml_feed(XMLParser *parser, const char *data);

xml_query(XML_Parser *parser);

Now the issue you face is whether xml_query() can be called whilst the parser
is in a state of being fed, that is, between feed calls. But put that to one side
for the time being.

First thing is to get the feed() interface going. Now in reality the xml might be
hosted on an external website under an unreliable connection. But you don't
worry about that. Your test script is just open an xml file with open(),
create the parser, feed it lines (or part lines, or chunks, whatever you support),
and return to your feeding loop. In reality there could be delays of several seconds 
or even minutes between feed calls, but the socket code can worry about that.

If you support query operations before the full data is fed to the parser, then of
course you need to test that by artificially constructing feeds, and calling the
query function in between calls.
Whichever you decide, you'll need an abort of some sort on bad data feeds,
probably just a sticky error flag - if the error flag is set, just return on any
more data without attempting to process, then reject all queries.



 

[toc] | [prev] | [next] | [standalone]

#76539

On 19.11.2015 17:12, Malcolm McLean wrote:
> On Thursday, November 19, 2015 at 3:03:17 PM UTC, Morten W. Petersen wrote:
[...]
>> Is there any kind of stream the project also should be able to handle?
>>
> You don't.

OK.

> You provide the functions along the lines of
>
> XMLParser *createparser(void);
> xml_feed(XMLParser *parser, const char *data);
>
> xml_query(XML_Parser *parser);
>
> Now the issue you face is whether xml_query() can be called whilst the parser
> is in a state of being fed, that is, between feed calls. But put that to one side
> for the time being.
>
> First thing is to get the feed() interface going. Now in reality the xml might be
> hosted on an external website under an unreliable connection. But you don't
> worry about that. Your test script is just open an xml file with open(),
> create the parser, feed it lines (or part lines, or chunks, whatever you support),
> and return to your feeding loop. In reality there could be delays of several seconds
> or even minutes between feed calls, but the socket code can worry about that.
>
> If you support query operations before the full data is fed to the parser, then of
> course you need to test that by artificially constructing feeds, and calling the
> query function in between calls.

OK.  But what's a good way to design this?  A while ago I was thinking
of creating a buffer that is a linked list, that could be "fed" or built
as data came in, and the parser loop could block and wait for the
necessary data.

But this means that the parser loop has to run in its own thread, and it
should be possible to use the library without threading.

> Whichever you decide, you'll need an abort of some sort on bad data feeds,
> probably just a sticky error flag - if the error flag is set, just return on any
> more data without attempting to process, then reject all queries.

Well I was thinking of using setjmp/longjmp, to avoid passing back
status codes and checking these.

The library shouldn't be verbose, just a yes/no on success.

-Morten

[toc] | [prev] | [next] | [standalone]

#76550

On Thursday, November 19, 2015 at 5:42:54 PM UTC, Morten W. Petersen wrote:
>
> > If you support query operations before the full data is fed to the 
> > parser, then of course you need to test that by artificially
> > constructing feeds, and calling the query function in between calls.
> 
> OK.  But what's a good way to design this?  A while ago I was thinking
> of creating a buffer that is a linked list, that could be "fed" or built
> as data came in, and the parser loop could block and wait for the
> necessary data.
> 
> But this means that the parser loop has to run in its own thread, and it
> should be possible to use the library without threading.
> 
Lets say we decide that query operation shall not be allowed until
data is complete.
Now there's no problem whatsoever. xml_feed() takes in a line of data,#and returns when it has finished parsing it. It might well be running under
a multi-threaded environment, but the data reading loop is the proper
place to handle that.

Now let's make it more difficult. You want to allow some query operations,
before data reading is complete. Now we could simply say that the reads 
must be on the same thread as the xml_feed calls. But that might be a bit 
of a nuisance.
Really you need a mutex flag. When xml_feed is called, wait for the
semaphore to clear, set it, parse the line, then clear it. Similarly
with the query ops. Now threads will work as expected.
If you want to be really fancy, youy might be able to get way with
only setting the semaphore whilst actually modifying your xml_parser
object. But worry about that refinement after the rest of the system
works.

[toc] | [prev] | [next] | [standalone]

#76562

On Thu, 19 Nov 2015 18:42:51 +0100, "Morten W. Petersen"
<morphex@gmail.com> wrote:

>On 19.11.2015 17:12, Malcolm McLean wrote:
>> On Thursday, November 19, 2015 at 3:03:17 PM UTC, Morten W. Petersen wrote:
>[...]
>>> Is there any kind of stream the project also should be able to handle?
>>>
>> You don't.
>
>OK.
>
>> You provide the functions along the lines of
>>
>> XMLParser *createparser(void);
>> xml_feed(XMLParser *parser, const char *data);
>>
>> xml_query(XML_Parser *parser);
>>
>> Now the issue you face is whether xml_query() can be called whilst the parser
>> is in a state of being fed, that is, between feed calls. But put that to one side
>> for the time being.
>>
>> First thing is to get the feed() interface going. Now in reality the xml might be
>> hosted on an external website under an unreliable connection. But you don't
>> worry about that. Your test script is just open an xml file with open(),
>> create the parser, feed it lines (or part lines, or chunks, whatever you support),
>> and return to your feeding loop. In reality there could be delays of several seconds
>> or even minutes between feed calls, but the socket code can worry about that.
>>
>> If you support query operations before the full data is fed to the parser, then of
>> course you need to test that by artificially constructing feeds, and calling the
>> query function in between calls.
>
>OK.  But what's a good way to design this?  A while ago I was thinking
>of creating a buffer that is a linked list, that could be "fed" or built
>as data came in, and the parser loop could block and wait for the
>necessary data.
>
>But this means that the parser loop has to run in its own thread, and it
>should be possible to use the library without threading.


That would be the classic use case for a coroutine.  That doesn't
help, of course, with coroutines being so sadly undersupported.


>> Whichever you decide, you'll need an abort of some sort on bad data feeds,
>> probably just a sticky error flag - if the error flag is set, just return on any
>> more data without attempting to process, then reject all queries.
>
>Well I was thinking of using setjmp/longjmp, to avoid passing back
>status codes and checking these.


Unfortunately while that can get you out of the parser, it really
can't get you back in.  setjmp/longjmp provide about half of a
coroutine implementation.

But the usual approach is to create the top as a state machine, which
you can leave and reenter.  Sure it can get ugly, but...  With
something like a parser, you might store some kind of checkpoint, so
that if you get halfway through something and realize you can't
continue without more input, you can "back up", and return control to
the caller, and wait for the next "feed" call.

And if you didn't plan for this from the start, this will probably do
more than a bit of violence to the existing structure of your code.

[toc] | [prev] | [next] | [standalone]

#76575

On 19.11.2015 23:17, Robert Wessel wrote:
> On Thu, 19 Nov 2015 18:42:51 +0100, "Morten W. Petersen"
> <morphex@gmail.com> wrote:
>
>> On 19.11.2015 17:12, Malcolm McLean wrote:
[...]
>>> Whichever you decide, you'll need an abort of some sort on bad data feeds,
>>> probably just a sticky error flag - if the error flag is set, just return on any
>>> more data without attempting to process, then reject all queries.
>>
>> Well I was thinking of using setjmp/longjmp, to avoid passing back
>> status codes and checking these.
>
>
> Unfortunately while that can get you out of the parser, it really
> can't get you back in.  setjmp/longjmp provide about half of a
> coroutine implementation.
>
> But the usual approach is to create the top as a state machine, which
> you can leave and reenter.  Sure it can get ugly, but...  With
> something like a parser, you might store some kind of checkpoint, so
> that if you get halfway through something and realize you can't
> continue without more input, you can "back up", and return control to
> the caller, and wait for the next "feed" call.
>
> And if you didn't plan for this from the start, this will probably do
> more than a bit of violence to the existing structure of your code.

Yes, this is the issue.  If a user controls the network connection for
example, and feeds 1024 bytes at a time to the feed function, this is
what needs to be handled.

But maybe a choice can be made, so that the library can be compiled
without integrator-level control of streams, so that if a user does
need to feed the parser, the parser can run in a thread and check
for new input via some queue or linked list.

-Morten

[toc] | [prev] | [next] | [standalone]

#76605

On Fri, 20 Nov 2015 01:16:41 +0100, "Morten W. Petersen"
<morphex@gmail.com> wrote:

>On 19.11.2015 23:17, Robert Wessel wrote:
>> On Thu, 19 Nov 2015 18:42:51 +0100, "Morten W. Petersen"
>> <morphex@gmail.com> wrote:
>>
>>> On 19.11.2015 17:12, Malcolm McLean wrote:
>[...]
>>>> Whichever you decide, you'll need an abort of some sort on bad data feeds,
>>>> probably just a sticky error flag - if the error flag is set, just return on any
>>>> more data without attempting to process, then reject all queries.
>>>
>>> Well I was thinking of using setjmp/longjmp, to avoid passing back
>>> status codes and checking these.
>>
>>
>> Unfortunately while that can get you out of the parser, it really
>> can't get you back in.  setjmp/longjmp provide about half of a
>> coroutine implementation.
>>
>> But the usual approach is to create the top as a state machine, which
>> you can leave and reenter.  Sure it can get ugly, but...  With
>> something like a parser, you might store some kind of checkpoint, so
>> that if you get halfway through something and realize you can't
>> continue without more input, you can "back up", and return control to
>> the caller, and wait for the next "feed" call.
>>
>> And if you didn't plan for this from the start, this will probably do
>> more than a bit of violence to the existing structure of your code.
>
>Yes, this is the issue.  If a user controls the network connection for
>example, and feeds 1024 bytes at a time to the feed function, this is
>what needs to be handled.
>
>But maybe a choice can be made, so that the library can be compiled
>without integrator-level control of streams, so that if a user does
>need to feed the parser, the parser can run in a thread and check
>for new input via some queue or linked list.


Restructuring as a state machine has the advantage that you end up
with only one version of the code with two small wrappers.  You also
avoid the portability issues of threads, and the inter-thread
communications performance issues if the chunks being read are small.

[toc] | [prev] | [next] | [standalone]

#76693

On 20.11.2015 07:15, Robert Wessel wrote:
> On Fri, 20 Nov 2015 01:16:41 +0100, "Morten W. Petersen"
> <morphex@gmail.com> wrote:
>
>> On 19.11.2015 23:17, Robert Wessel wrote:
[...]
>>> And if you didn't plan for this from the start, this will probably do
>>> more than a bit of violence to the existing structure of your code.
>>
>> Yes, this is the issue.  If a user controls the network connection for
>> example, and feeds 1024 bytes at a time to the feed function, this is
>> what needs to be handled.
>>
>> But maybe a choice can be made, so that the library can be compiled
>> without integrator-level control of streams, so that if a user does
>> need to feed the parser, the parser can run in a thread and check
>> for new input via some queue or linked list.
>
>
> Restructuring as a state machine has the advantage that you end up
> with only one version of the code with two small wrappers.  You also
> avoid the portability issues of threads, and the inter-thread
> communications performance issues if the chunks being read are small.

OK.  I'll give this some thought.

-Morten

[toc] | [prev] | [next] | [standalone]

#76546

On Thu, 19 Nov 2015 16:03:10 +0100, Morten W. Petersen wrote:

> So I'm working on my XML parser, and a while back someone mentioned that
> having a feed(parser, data) function would be a good idea.
> 
> But how do I make that work in practice?  The XML parser loop would have
> to wait for new input, and what's a good way to design that?  Same goes
> for output and waiting for write access.

What is this "parser loop" of which you speak?

The feed(parser, data) idiom only makes sense in the context of a "push"
parser, where you push data into it and the parser invokes callbacks as
complete terms (attributes, tags, elements, etc) are parsed.

For a "pull" parser, the data flow is reversed: you provide a stream and
the parser pulls data from it as it sees fit.

A push parser is typically implemented as a pushdown automaton.

A pull parser may be implemented as a recursive-descent parser, or as as a
pushdown automaton plus a loop which reads chunks of input which is fed
into the automaton a character at a time until reaching a state
corresponding to a complete element, at which point it returns the element
to the caller. Or it may just build the entire tree in memory and return
the root node to the caller.

Push parsers tend to be more useful in the case where the program can't
just block until all of the data has been received. In that situation, a
recursive-descent parser would need to use some kind of threading: either
actual OS threads or an equivalent such as coroutines or lightweight
threads (e.g. Windows "fibers" or POSIX' swapcontext()).

[toc] | [prev] | [next] | [standalone]

#76578

On 19.11.2015 20:59, Nobody wrote:
> On Thu, 19 Nov 2015 16:03:10 +0100, Morten W. Petersen wrote:
>
>> So I'm working on my XML parser, and a while back someone mentioned that
>> having a feed(parser, data) function would be a good idea.
>>
>> But how do I make that work in practice?  The XML parser loop would have
>> to wait for new input, and what's a good way to design that?  Same goes
>> for output and waiting for write access.
>
> What is this "parser loop" of which you speak?
>
> The feed(parser, data) idiom only makes sense in the context of a "push"
> parser, where you push data into it and the parser invokes callbacks as
> complete terms (attributes, tags, elements, etc) are parsed.
>
> For a "pull" parser, the data flow is reversed: you provide a stream and
> the parser pulls data from it as it sees fit.
>
> A push parser is typically implemented as a pushdown automaton.
>
> A pull parser may be implemented as a recursive-descent parser, or as as a
> pushdown automaton plus a loop which reads chunks of input which is fed
> into the automaton a character at a time until reaching a state
> corresponding to a complete element, at which point it returns the element
> to the caller. Or it may just build the entire tree in memory and return
> the root node to the caller.
>
> Push parsers tend to be more useful in the case where the program can't
> just block until all of the data has been received. In that situation, a
> recursive-descent parser would need to use some kind of threading: either
> actual OS threads or an equivalent such as coroutines or lightweight
> threads (e.g. Windows "fibers" or POSIX' swapcontext()).

Well there has been talk on whether it should be possible to make use
of an incomplete document in this thread by Malcolm, and I think that's
a nice feature to have.  If it isn't too difficult to implement or
expensive at run-time.

The design today is a loop that "pulls" characters from a buffer, and
that's an OK design..  so something that enables retrieving characters
from a source is what fits with the code as it is now.

-Morten

[toc] | [prev] | [next] | [standalone]

#76585

On Friday, November 20, 2015 at 12:26:20 AM UTC, Morten W. Petersen wrote:
>
> Well there has been talk on whether it should be possible to make use
> of an incomplete document in this thread by Malcolm, and I think that's
> a nice feature to have.  If it isn't too difficult to implement or
> expensive at run-time.
> 
> The design today is a loop that "pulls" characters from a buffer, and
> that's an OK design..  so something that enables retrieving characters
> from a source is what fits with the code as it is now.
> 
If you build up the document from nodes containing a "next" pointer,
a "child" pointer, and a "previous" pointer (won't call it the parent to
avoid confusion), then your parser will have a pointer to the root
node, obviously.
However you also keep a "tip", which represents the insert position.
When you hit a opening tag, you insert the new node at the tip,
then push, that is, put the tip to the child member of the current
node. Then you insert any children, and finally pop. The pop is why
you need the "previous" pointer, you need to move the tip backwards
through the siblings, then up. It will then be pointing to the
end of the layer above.
So there's no need to make the parser itself recursive, and the tree
is always a true binary tree, except at the moment you are actually
manipulating the pointers.
Of course if the tip is under a node, you can't fully query that
node, some of its descendants are still to be read.

[toc] | [prev] | [next] | [standalone]

#76598

On Fri, 20 Nov 2015 01:26:18 +0100, Morten W. Petersen wrote:

> The design today is a loop that "pulls" characters from a buffer,

Until ... what?

With a push parser, the feed() method retrieves characters until there
aren't any more, at which point it returns. Then the next time you call
feed() it continues from where it left off. It doesn't matter if the
characters comprising a token (e.g. a tag, tag name, attribute name, etc)
are split across multiple feed() calls.

This is trivial with a pushdown automaton (bottom-up) design, where you
have a single outer loop which consumes one character on each iteration,
but it's the wrong way around for a top-down (e.g. recursive-descent)
parser which expects to be able to read ahead until some particular point
in the structure (e.g. the end of a tag or the end of an element).

Providing a "push" interface to a top-down parser typically requires
either

1. using threads/fibers/coroutines/etc, so the feed() function just
appends characters to the back of the input queue while the parser itself
reads from the front in a separate thread, or

2. having each feed() call run the parser until either

a) it has enough data to return an "item" (e.g. tag or element), in which
case it removes the corresponding data from the input (leaving any
following data) and returns the item, or

b) it reaches the end of the input without having seen a complete item, in
which case it leaves all of the data in the input stream and returns
nothing; on the next feed() it tries again with the now-enlarged input.

Option 2 is inefficient, as you can end up having to repeat the parsing
until it completes. Option 1 avoids that but requires some means to
suspend execution whenever you run out of data and resume it later.

[toc] | [prev] | [next] | [standalone]

#76612

On Friday, November 20, 2015 at 5:07:37 AM UTC, Nobody wrote:
> On Fri, 20 Nov 2015 01:26:18 +0100, Morten W. Petersen wrote:
> 
> > The design today is a loop that "pulls" characters from a buffer,
> 
> Until ... what?
> 
> With a push parser, the feed() method retrieves characters until there
> aren't any more, at which point it returns. Then the next time you call
> feed() it continues from where it left off. It doesn't matter if the
> characters comprising a token (e.g. a tag, tag name, attribute name, etc)
> are split across multiple feed() calls.
> 
> This is trivial with a pushdown automaton (bottom-up) design, where you
> have a single outer loop which consumes one character on each iteration,
> but it's the wrong way around for a top-down (e.g. recursive-descent)
> parser which expects to be able to read ahead until some particular point
> in the structure (e.g. the end of a tag or the end of an element).
> 
> Providing a "push" interface to a top-down parser typically requires
> either
> 
> 1. using threads/fibers/coroutines/etc, so the feed() function just
> appends characters to the back of the input queue while the parser itself
> reads from the front in a separate thread, or
> 
> 2. having each feed() call run the parser until either
> 
> a) it has enough data to return an "item" (e.g. tag or element), in which
> case it removes the corresponding data from the input (leaving any
> following data) and returns the item, or
> 
> b) it reaches the end of the input without having seen a complete item, in
> which case it leaves all of the data in the input stream and returns
> nothing; on the next feed() it tries again with the now-enlarged input.
> 
> Option 2 is inefficient, as you can end up having to repeat the parsing
> until it completes. Option 1 avoids that but requires some means to
> suspend execution whenever you run out of data and resume it later.
>
There's no reason to be especially complicated or inefficient.

The parser can process a tag whenever it encounters a '>' character
(I'd have to check the spec for escapes). So it needs a buffer, which
can grow, but won't get too big on normal input.
You've got three states, 1) having encounters a "<", waiting for the ">"
before you can process the tag, 2) adding text data to the current tag,
3) having just encountered a ">" character, you need to parse the
tag and, if it is closing tag, pop the tree, otherwise make the tag the
current parent tag.
 

[toc] | [prev] | [next] | [standalone]

#76566

Morten W. Petersen wrote:
> Hi there.
>
> So I'm working on my XML parser, and a while back someone mentioned that
> having a feed(parser, data) function would be a good idea.
>
> But how do I make that work in practice?  The XML parser loop would have
> to wait for new input, and what's a good way to design that?  Same goes
> for output and waiting for write access.
>
> I also thought about creating high-level functions that can accept IO
> from either a file stream or a network stream.  This could be built on
> top of the feed function.

what is wrong with a simple loop:

while( get data )
{
   feed(parser, data)
}

?

the "get data" code can be what ever you decide to use to read the XML 
data.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#76577

On 20.11.2015 00:00, Ian Collins wrote:
> Morten W. Petersen wrote:
>> Hi there.
>>
>> So I'm working on my XML parser, and a while back someone mentioned that
>> having a feed(parser, data) function would be a good idea.
>>
>> But how do I make that work in practice?  The XML parser loop would have
>> to wait for new input, and what's a good way to design that?  Same goes
>> for output and waiting for write access.
>>
>> I also thought about creating high-level functions that can accept IO
>> from either a file stream or a network stream.  This could be built on
>> top of the feed function.
>
> what is wrong with a simple loop:
>
> while( get data )
> {
>    feed(parser, data)
> }
>
> ?
>
> the "get data" code can be what ever you decide to use to read the XML
> data.

Well this could work if a function is passed to the parser function, so
that the main parser loop calls that function, which reads from an open
network socket or other OS-level feature for example.

-Morten

[toc] | [prev] | [next] | [standalone]

#76799

what is wrong with a simple loop: 

while( get data ) 
{ 
   feed(parser, data) 
} 

? 

the "get data" code can be what ever you decide to use to read the XML 
data. 

Ian Collins
-----
The problem could be if the input 
is not all
for example not all html page
 the computation can not
be ok

[toc] | [prev] | [next] | [standalone]

#76810

asetofsymbols@gmail.com wrote:

Can't you at least try and quote correctly?  It's not rocket science.

> what is wrong with a simple loop:
>
> while( get data )
> {
>     feed(parser, data)
> }
>
> ?
>
> the "get data" code can be what ever you decide to use to read the XML
> data.
>
> Ian Collins
> -----
> The problem could be if the input
> is not all
> for example not all html page
>   the computation can not
> be ok

Which is why there is a loop.

-- 
Ian Collins

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web