Hi Joel, "Joel de Guzman" <joel@boost-consulting.com> wrote in message news:40B57D2D.6070905@boost-consulting.com... | > 2. if we shouldn't copy a rule, why is copying not disabled? It has been a source of errors in my code that | > I forgot & on my return value. | | I believe http://www.boost.org/libs/spirit/doc/stored_rule.html | answers this question. "The rule is a wierd C++ citizen, unlike any other C++ object. It does not have the proper copy and assignment semantics and cannot be stored and passed around by value. You cannot store rules in STL containers (vector, stack, etc) for later use and you cannot pass and return rules to and from functions by value." I have read this page before, but I still don't get why the rule has copy and assignment semantics at all. Afterall, you admit copying and assignment does not make sense, yet it is still defined :-) What am I overlooking? Why do we need the current copy/assignment semantics? br Thorsten

Joel de Guzman wrote:

Consider:

rule<> a = x;

or:

rule<> a; a = x;

How should this behave if x is an int_p?

The int_p gets stored in an object on the heap, and the rule<> stores a shared_ptr to a polymorphic base.

Now how should it behave if x is another rule? Consider a concrete example (snipped from the pascal parser):

rule<> identifier; rule<> fileIdentifier;

identifier = ....

fileIdentifier = identifier; // an alias

The shared_ptr's reference count goes up. What's the problem? -- Eric Niebler Boost Consulting www.boost-consulting.com

Joel de Guzman wrote:

Simply, "=" in Spirit should not be confused with assignment. This behavior in fact killed the pascal grammar. Consider this:

rule<> a; rule<> b;

a = b; // alias. a shares b // (points to nothing_p since b is still undefined)

b = int_p; // now b is an int_p

// at this point, a still refers a points to nothing_p // and did not (cannot) follow b's change.

Why is that confusing? That's how most other types in C++ behave: int a,b; // a and b are undefined a = b; // a and b are still undefined b = 1; // a is undefined, b is 1

Also, be wary of cycles. It is quite common that a rule references another rule which indirectly references the start rule, in a cycle. No, share_ptr can't handle this common situation. This scheme (using shared_ptr) can't handle forward declared rules like the humble calculator:

group = '(' >> expression >> ')'; factor = integer | group; term = factor >> *(('*' >> factor) | ('/' >> factor)); expression = term >> *(('+' >> term) | ('-' >> term));

Note that group is defined *before* expresion is defined. Note too that this is cyclic. expression indirectly references group, while group references expression.

There's only one solution: use plain references. When a rule is referenced in the RHS of another rule, it is held by reference.

There is another solution. Give rules value semantics by default as I suggest, but require people to use special syntax to get reference semantics. Your example becomes: group = '(' >> &expression >> ')'; factor = integer | group; term = factor >> *(('*' >> factor) | ('/' >> factor)); expression = term >> *(('+' >> term) | ('-' >> term)); When referencing a rule that has not yet been initialized, it gets included by-reference by applying the address-of operator (or by wrapping it in a call to ref() if that's more palatable). This is currently how xpressive behaves, BTW. I suppose it comes down to expectations and common usage. Will people have to wrap everything in ref() because they can't figure out when it's not needed? Do people expect reference semantics from a DSL for EBNF in C++, even though C++ has value semantics by default? The answers may be different in the regular expression domain, where there is not a long tradition of regexes referring to other regexes. I dunno. I like value semantics. -- Eric Niebler Boost Consulting www.boost-consulting.com

Eric Niebler wrote:

There is another solution. Give rules value semantics by default as I suggest, but require people to use special syntax to get reference semantics.

I hate replying to myself. ;-) I realize this doesn't give true value semantics. A rule which refers to itself (that is, it indirectly stores a pointer to itself) cannot be copied around and put inside containers and whatnot. Then I thought that it could be solved with an extra layer of indirection -- shared_ptr to a shared_ptr (ugh!) but then you have problems with cyclic references. Hence Joel's comment about garbage collection -- he's probably been through this thought process before. I think I need to think it out again. -- Eric Niebler Boost Consulting www.boost-consulting.com

On Jun 6, 2004, at 10:12 AM, Eric Niebler wrote:

Eric Niebler wrote:

...

Eric Niebler wrote:

...

There is another solution. Give rules value semantics by default as I suggest, but require people to use special syntax to get reference semantics.

I hate replying to myself. ;-) I realize this doesn't give true value semantics. A rule which refers to itself (that is, it indirectly stores a pointer to itself) cannot be copied around and put inside containers and whatnot. Then I thought that it could be solved with an extra layer of indirection -- shared_ptr to a shared_ptr (ugh!) but then you have problems with cyclic references. Hence Joel's comment about garbage collection -- he's probably been through this thought process before. I think I need to think it out again.

Here I go, replying to myself *again*. I've rethought this and come up with a new scheme whereby rules (or in xpressive's case regexes) can have both value *and* reference semantics. A good analogy would be a pointer. You can copy pointers freely, creating aliases. You can dereference the pointer and assign through it, changing all the aliases. This is how regex objects in xpressive work right now (it's an experiment).

In addition, I have solved the cyclic/dangling reference problem. A regex can refer to other regexes or itself and it tracks changes to its referenced regexes. It lets you copy regex objects freely, even putting them in containers, and they keep their references alive. It works with nothing more sophisticated than shared_ptr and weak_ptr -- no garbage collection is necessary. No cycles are created ever, so no cycles need to be collected.

There are only two questions: (1) is the rule-as-pointer metaphor acceptable? and (2) can we find a palatable syntax?

The syntax issue is this: if we take assign to be shallow (creating aliases) we need a different syntax for deep assign. I am using *= to mean deep-assign. Perhaps there is a better solution.

*x = *y ?

"Eric Niebler" <eric@boost-consulting.com> wrote in message news:40C3684F.6040000@boost-consulting.com... | | Gregory Colvin wrote: [snip] | > *x = *y [snip] | I thought about this. I wasn't sure how well it would be received. | People would have to write their grammars like: | | rule<> a, b; | *a = parser >> that >> refers >> to >> b; | *b = parser >> that >> refers >> to >> a; [snip] | That's why I have been | considering this: | | rule<> a, b; | a *= parser >> that >> refers >> to >> b; | b *= parser >> that >> refers >> to >> a; maybe rule<> a, b; a = parser >> that >> refers >> to >> b; b = parser >> that >> refers >> to >> a; a = a.clone(); ? | I don't know. Another question is: would spirit's users accept any | amount of syntactic/conceptual overhead to have a rule with standard | copy semantics and that was able to track its references and avoid | cyclic dependencies? I'm not an expert spirit user, but the current semantics already carries some conceptual overhead with it. Anything that can reduce surprises would help. And I can replace this code template< int > rule<>& some_rule(...) { static rule<> r = ...; return r; } rule<> r1 = some_rule<1>(...) rule<> r2 = some_rule<2>(...) with rule<> some_rule(...) { return ...; } rule<> r1 = some_rule(...) rule<> r2 = some_rule(...) br Thorsten

"Eric Niebler" <eric@boost-consulting.com> writes:

I have a new idea. Deep copy can be triggered by assigning to a dummy member:

rule<> a, b; a.rule = parser >> that >> refers >> to >> b; b.rule = parser >> that >> refers >> to >> a;

This allows: a = b; // shallow copy, creates alias a.rule = b.rule; // deep copy, modifies 'a' and all its aliases

xpressive now works this way. It's heavier syntactically, but far less confusing then using a special deep-assign operator.

I think a->rule = b->rule would be much more consistent with the other semantics of this thing. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com

On 06/06/2004 11:12 AM, Eric Niebler wrote: [snip]

In addition, I have solved the cyclic/dangling reference problem. A regex can refer to other regexes or itself and it tracks changes to its referenced regexes. It lets you copy regex objects freely, even putting them in containers, and they keep their references alive. It works with nothing more sophisticated than shared_ptr and weak_ptr -- no garbage collection is necessary. No cycles are created ever, so no cycles need to be collected.

There are only two questions: (1) is the rule-as-pointer metaphor acceptable? and (2) can we find a palatable syntax?

The syntax issue is this: if we take assign to be shallow (creating aliases) we need a different syntax for deep assign. I am using *= to mean deep-assign. Perhaps there is a better solution.

The grammar_pipeline/{base,eff}/productions avoids the cycle problem by just using indexes into a vector of "grammar expressions". IOW, a non-terminal expression is create with nt_exp(unsigned nt_id), where nt_id is an index into a vector of sole_ptr smart pointers to the grammar expression defining the rhs of the non-terminal. You might think this would lead to a "semi-dangling pointer" (a nt_exp whose index points to a deleted vector of sole_ptr's); however, deletion of the sole_ptr's delete's the rhs. Hence, the only way to create such a semi-dangling pointer would be to create a nt_exp somewhere other than on the rhs of a non-terminal. There's that danger; however, I don't know that it's that significant. If one want's to do that, he/she must clone the rhs. Anyway, I may discover this won't work in the future, but right now it looks OK to me.

David Abrahams wrote:

"Eric Niebler" <eric@boost-consulting.com> writes:

...

Why is that confusing? That's how most other types in C++ behave:

int a,b; // a and b are undefined a = b; // a and b are still undefined

^^^^^ This is undefined behavior, actually.

Oops, you're right. Bad example. How about: int a=0,b=0; a=b; b=1; // b is 1, a is still 0 My point was that rule<> doesn't "do as the ints do", which can be surprising to some. I would love for this to work: rule<> a; { rule <> b; // match balanced, nested parens. // b refers to itself by reference // (Note: ! means optional, no special syntax // required to get by-ref semantics here) b = '(' >> !b >> ')'; // a assumes b's behavior a = b; } // a still has b's behavior. // this matches balanced, nested parens parse( "(())", a ); Currently, this crashes because 'a' holds 'b' by reference and tries to access it after 'b' has gone out of scope and been destroyed. I haven't yet thought of a way to make this work, but I'm not convinced it's impossible. I now agree that rules should have by-ref semantics when embedded in another rule. But in simple assignment statements ("a=b;"), it would be nice if rules behaved as the ints do. I'm sure this will draw fire from the EBNF purists who want rule assignment to have by-ref semantics, but IMO C++ types that don't have normal copy and assignment semantics are just hard to work with. -- Eric Niebler Boost Consulting www.boost-consulting.com

On 05/27/2004 08:04 PM, Joel de Guzman wrote:

Eric Niebler wrote: [snip] and, yes, stored_rule(s) use shared_ptr. So, again, be wary of cycles. I was so eager when Lary Evans hinted at a shared_ptr implementatiion with GC. I'm still so eager! I'm having problems with it. I could upload the files to sandbox; however, I don't think anybody would be eager to debug it.

My reply to a private email from Eric contained:

Well, after I read the recent mention of this problem, I started going back to work on managed_ptr which is Held's policy_ptr with cycle collection. Unfortunately, I'm having problems: <----------------- cd /home/evansl/prog_dev/boost-root.ln/development/libs/managed_ptr/test/ make run /opt/intel_cc_80/bin/icc -c -MMD -g -I/home/evansl/prog_dev/boost-root.ln/development -I/home/evansl/prog_dev/boost-root.ln smart_ptr_test.cpp

... ===>Enter:<refcycle_counted_node_scalar_type>::refcycle_enum_children_test +owner::CTOR(void):overhead=0 ===>Enter:sp_parent=i.as_basis_source() make: *** [run] Interrupt

...

------------------- I

I'm also working on the deterministic parser. I also described in that reply to Eric the use of a symbol class: class exp_tree:: symbol //Purpose: // Represents "symbols", i.e. // inputs and variables. : public exp_tree::top { public: typedef unsigned id_type ; symbol(id_type a_id) : my_id(a_id) {} ... }; to represent occurences of inputs(terminals) and variables (non-terminals). The my_id serves as an index into a std:vector of right-hand-sides for the variables and as argument to bitset<NumInputs>::test in the case of inputs to test whether the next input from the lexer belongs to the "direction set" for a variable. Currently I'm trying to solve for the first and follow sets which are used to determine the direction set.

Thorsten Ottosen wrote:

"The rule is a wierd C++ citizen, unlike any other C++ object. It does not have the proper copy and assignment semantics and cannot be stored and passed around by value. You cannot store rules in STL containers (vector, stack, etc) for later use and you cannot pass and return rules to and from functions by value."

I have read this page before, but I still don't get why the rule has copy and assignment semantics at all. Afterall, you admit copying and assignment does not make sense, yet it is still defined :-) What am I overlooking? Why do we need the current copy/assignment semantics?

That's to allow to write: rule<> a = /* some spirit parser here */; rule<> b = a; Which is needed (or at least handy) in some parser contexts. Regards Hartmut