NetBSD Problem Report #12838

Received: (qmail 9227 invoked from network); 4 May 2001 23:29:13 -0000
Message-Id: <200105042330.f44NU1Q08656@sigmet.ghs.com>
Date: Fri, 4 May 2001 16:30:01 -0700 (PDT)
From: Ross Harvey <ross@ghs.com>
Reply-To: ross@ghs.com
To: gnats-bugs@gnats.netbsd.org
Subject: new expr(1) is totally broken
X-Send-Pr-Version: 3.95

>Number:         12838
>Category:       bin
>Synopsis:       new expr(1) is totally broken
>Confidential:   no
>Severity:       critical
>Priority:       high
>Responsible:    jmc
>State:          closed
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Fri May 04 23:30:00 +0000 2001
>Closed-Date:    Sat May 05 06:58:50 +0000 2001
>Last-Modified:  Tue Mar 20 06:30:02 +0000 2012
>Originator:     Ross Harvey
>Release:        NetBSD-current
>Organization:

>Environment:

System: NetBSD sigmet 1.5U NetBSD 1.5U (skb) #28: Thu Apr 26 19:28:16 PDT 2001 ross@sigmet:/usr/ross/skb i386
Architecture: i386
Machine: i386
>Description:
	The new expr(1) implements priorities that are different from
	every other commonly used unix system. It broke a script used
	by my mailer.

	Software 
>How-To-Repeat:
	$ expr 2 \> 1 \* 17

	NetBSD returns 17, every one else returns 0.
>Fix:
	Don't replace software that has been tested for years with casually
	done rewrites. Fix the bugs. Change is the enemy of reliability.

	If a rewrite is necessary, have a senior developer do it. 

	If a rewrite is necessary, have it reviewed by several serious
	developers.

	Don't commit widely used tools in critical paths without basic
	testing. (Never mind, _serious_ testing.)

	Don't check in code just because it compiles and runs successfully
	once.

	If you rewrite or extensively change a core utility, include
	real regression tests. This change included a mere TWO calls
	to expr as regression tests, both of which tested only a
	completely obscure feature.

	Working on NetBSD is a _serious_ activity and must be done
	thoughtfully and with care. Find developers who understand this.
>Release-Note:
>Audit-Trail:

From: Andrew Brown <atatat@atatdot.net>
To: Ross Harvey <ross@ghs.com>
Cc: gnats-bugs@gnats.netbsd.org
Subject: Re: bin/12838: new expr(1) is totally broken
Date: Fri, 4 May 2001 19:36:35 -0400

 >>How-To-Repeat:
 >	$ expr 2 \> 1 \* 17
 >
 >	NetBSD returns 17, every one else returns 0.

 expr 2 + 4 \* 5

 NetBSD:  30
 solaris: 22
 darwin:  22

 -- 
 |-----< "CODE WARRIOR" >-----|
 codewarrior@daemon.org             * "ah!  i see you have the internet
 twofsonet@graffiti.com (Andrew Brown)                that goes *ping*!"
 andrew@crossbar.com       * "information is power -- share the wealth."

From: woods@weird.com (Greg A. Woods)
To: ross@ghs.com
Cc: netbsd-bugs@NetBSD.ORG (NetBSD Bugs and PR posting List),
	gnats-bugs@gnats.netbsd.org (NetBSD GNATS submissions and followups)
Subject: Re: bin/12838: new expr(1) is totally broken
Date: Fri,  4 May 2001 21:14:34 -0400 (EDT)

 [ On Friday, May 4, 2001 at 16:30:01 (-0700), Ross Harvey wrote: ]
 > Subject: bin/12838: new expr(1) is totally broken

 Actually `expr' is not "totally broken" -- it simply has an operator
 precedence error.

 This seems to fix the bug, though only using your one example to test:

 Index: expr.y
 ===================================================================
 RCS file: /cvs/NetBSD/src/bin/expr/expr.y,v
 retrieving revision 1.1.1.2
 diff -c -r1.1.1.2 expr.y
 *** expr.y      2001/03/25 05:48:23     1.1.1.2
 --- expr.y      2001/05/05 01:09:52
 ***************
 *** 66,72 ****
   %token STRING
   %left SPEC_OR
   %left SPEC_AND
 ! %left COMPARE ARITH_OPERATOR SPEC_REG
   %left LEFT_PARENT RIGHT_PARENT

   %%
 --- 66,73 ----
   %token STRING
   %left SPEC_OR
   %left SPEC_AND
 ! %left COMPARE
 ! %left ARITH_OPERATOR SPEC_REG
   %left LEFT_PARENT RIGHT_PARENT

   %%

 > 	Don't replace software that has been tested for years with casually
 > 	done rewrites. Fix the bugs. Change is the enemy of reliability.

 That's pretty funny!  :-)  NOT!

 Seriously speaking all complex software should be re-written from
 scratch as often as humanly and economically possible.  And maybe even
 more often than that.  (of course `expr' is not exactly "complex",
 but...)

 Seriously, the old `expr' did need replacing.  It had bugs of its own
 and broke several of my own scripts -- scripts that had worked on many
 other unix and unix-like systems.

 The new version is now at a point where bug reports like yours can be
 used to improve it.

 > 	Don't commit widely used tools in critical paths without basic
 > 	testing. (Never mind, _serious_ testing.)

 Perhaps you're willing to write some test harnesses, test cases, etc.?

 Not everyone in the world does everything possible with even a
 relatively simple tool such as expr.  Dozens, and maybe even hundreds,
 of us have been using the enw version of expr for quite some time now
 and few have had any complaints about it.  The bugs that have been
 reported have been fixed so far as I can see.

 In any case I'm quite sure that the new version did go through extensive
 and very serious testing even before it was committed.

 It is interesting to note that the FreeBSD folks never took JTC's
 initial rewrite as a hand-coded recursive descent parser but instead of
 just incrementally improved the original 1993 version.

 -- 
 							Greg A. Woods

 +1 416 218-0098      VE3TCP      <gwoods@acm.org>     <woods@robohack.ca>
 Planix, Inc. <woods@planix.com>;   Secrets of the Weird <woods@weird.com>

From: Ross Harvey <ross@ghs.com>
To: woods@weird.com
Cc: gnats-bugs@gnats.netbsd.org, netbsd-bugs@netbsd.org
Subject: Re: bin/12838: new expr(1) is totally broken
Date: Fri, 4 May 2001 20:25:35 -0700 (PDT)

 > From: woods@weird.com (Greg A. Woods)
 :::
 > Perhaps you're willing to write some test harnesses, test cases, etc.?
 :::

 Oh, you don't think I contrib to src/regress? (As if that would justify
 ignoring basic quality principles?)  I think you missed by a mile...

 There are thousands of lines of code under src/regress that are only there
 because I integrated and tested them.

 And I have in fact written specifically for NetBSD a "test harness" that
 uses the crypto hash functions to enable arbitrarily lengthy tests to be
 checked into src/regress with only a handful of bytes of framework, and to
 enable library functions to be tested on millions of inputs, instead of
 just inputs that produce easily predicted outputs, or outputs recorded in
 cvs src/regress files. (It also checks all the crypto hash functions.)

 I haven't checked this in, yet, but since I've mentioned it, I've put
 a preview copy of most of it in:

 	ftp://ftp.netbsd.org/pub/NetBSD/arch/alpha/misc/regress/

 //
Responsible-Changed-From-To: bin-bug-people->jmc 
Responsible-Changed-By: jmc 
Responsible-Changed-When: Fri May 4 21:56:58 PDT 2001 
Responsible-Changed-Why:  
Taking ownership for now (I have the code fixed. Just need to add a regress 
suite) 
State-Changed-From-To: open->closed 
State-Changed-By: jmc 
State-Changed-When: Fri May 4 23:57:35 PDT 2001 
State-Changed-Why:  
Checked in changes to fix these problems (and a few others we found in testing). 

Had Christos double-check the code as a safety check and also made sure the 
new regress tests all passed. 

From: Jaromír Dolecek <jdolecek@NetBSD.org>
To: ross@ghs.com
Cc: gnats-bugs@gnats.netbsd.org
Subject: Re: bin/12838: new expr(1) is totally broken
Date: Sat, 5 May 2001 19:00:30 +0200 (CEST)

 The primary goal of the rewrite was to improve maintainability
 of the utility (and support for arbitrarily long expressions).
 Have you ever looked at the previous version?

 Jaromir

From: Jaromír Dolecek <jdolecek@netbsd.org>
To: jchacon@genuity.net
Cc: Ross Harvey <ross@ghs.com>, mkb@mukappabeta.de, gnats-bugs@netbsd.org
Subject: Re: bin/12838: new expr(1) is totally broken
Date: Sat, 5 May 2001 19:36:58 +0200 (CEST)

 jchacon@genuity.net wrote:
 > Having just fixed the code for expr I have to definitly agree here. The yacc
 > code is small in this case so fixing it was simple enough (knowing basic
 > parser concepts and precendence rules helps if you're gonna use yacc), but
 > patching a large grammer file would have been a lot nastier.

 Now imagine - how hard would the fix be if the expr(1) code would
 use the recursive descend and contain the same precedence bug ?

 Jaromir

From: Ross Harvey <ross@ghs.com>
To: jchacon@genuity.net, jdolecek@netbsd.org
Cc: gnats-bugs@netbsd.org, mkb@mukappabeta.de
Subject: Re: bin/12838: new expr(1) is totally broken
Date: Sat, 5 May 2001 13:10:44 -0700 (PDT)

 > From jdolecek@netbsd.org Sat May  5 10:37:09 2001
 > From: Jarommr Dolecek <jdolecek@netbsd.org>
 > Subject: Re: bin/12838: new expr(1) is totally broken
 > To: jchacon@genuity.net
 > Date: Sat, 5 May 2001 19:36:58 +0200 (CEST)
 > CC: Ross Harvey <ross@ghs.com>, mkb@mukappabeta.de, gnats-bugs@netbsd.org
 >
 > jchacon@genuity.net wrote:
 > > Having just fixed the code for expr I have to definitly agree here. The yacc
 > > code is small in this case so fixing it was simple enough (knowing basic
 > > parser concepts and precendence rules helps if you're gonna use yacc), but
 > > patching a large grammer file would have been a lot nastier.
 >
 > Now imagine - how hard would the fix be if the expr(1) code would
 > use the recursive descend and contain the same precedence bug ?
 >
 > Jaromir
 >

 I've implemented lots of parsers both large and small in both yacc and
 recursive descent.  Many of them are in commercial use now.

 I think the problem starts with thinking that the parser is the hard part
 of the project. In a classroom assignment, it may be the _entire_ project,
 but IRL I've always found the parser to be the easy, almost trivial part,
 in RD. In yacc, it really depends. Yacc can put you into parsing hell where
 the input isn't recognized or parsed right, yet you can see nothing wrong
 with your rules. This doesn't happy with toy grammars and toy projects.

 Part of the problem is that the textbook examples for recursive descent
 all seem to copy the same poor style, before moving on to the theory part.
 A good RD parser is organized differently than the usual textbook ones.

 For example, a real-world nicely-done RD parser might use just one function
 for expressions, and look up operator priorities in a table, whereas the
 textbook ones usually put a different function in for each priority level.

 The real answer is that it's just a choice. Reasonable arguments can be
 made on both sides. The yacc parser has fewer lines, but it has wierd and
 subtle bugs that are hard to find, and there are some things that is really
 hard to make it do. A toy grammar makes yacc look good, a real-world grammar
 can lead to a yacc nightmare. Sometimes, you have to hack yacc to make your
 language work. That really slows you down, because if you are any good at
 writing code the parser is always the easy part of the project.

 The RD parser has more lines, but they are easy to write, and the bugs are
 almost always instantly obvious. It's more flexible, too. You can make it
 parse anything with just a little more code. Now, if you don't program very
 well, then yacc may be a necessity. The RD parser can have a lot of lines
 and you may not finish.

 So, yacc has its merits and demerits. I disagree with the generalities,
 and I particularly disagree that the yacc parser makes bug fixing easier.
 I say, it makes it harder. Certainly, any _one_ example in yacc might be
 written better and have generally nicer qualities than any _one_ example
 in RD.

 I'm sure you can do a bad job with either approach. A really badly done RD
 parser will be harder to fix bugs in than a reasonable yacc parser. What's
 funny, is, on one consulting job I did a compiler for dBASE III. I did the
 parser in in yacc because the original dBASE author and company chief
 scientist ordered me to.  The funny part is that his parser was RD.

 //
From: "Jukka Ruohonen" <jruoho@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/12838 CVS commit: src/tests/bin/expr
Date: Tue, 20 Mar 2012 06:30:03 +0000

 Module Name:	src
 Committed By:	jruoho
 Date:		Tue Mar 20 06:30:02 UTC 2012

 Modified Files:
 	src/tests/bin/expr: t_expr.sh

 Log Message:
 Note PR bin/12838.


 To generate a diff of this commit:
 cvs rdiff -u -r1.1 -r1.2 src/tests/bin/expr/t_expr.sh

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

>Unformatted:

Home	PR Database Search