Warning to newbies

[Ben Bacarisse]

do you read me? someone read me?
this below is better
// ---------------------------------------------------------------
// Statement-format test macro
//
//
#define TESTER(resultPtr, master, target, replacement, expected) \
{ \
printf("Expect \"%s\":\n\"%s\"\n\n", \
(expected), \
resultPtr = replace((master), \
(target), \
(replacement))); \
free(resultPtr); \
}

because align the string expected to the result
and is easier to ceck

Surely it would be better still to have the program check that the
strings are the same?

int fail(const char *s, const char *t, const char *r, const char *e)
{
const char *result = replace(s, t, r);
return result && strcmp(result, e) == 0 ? (free(result), 0) : 1;
}

and then the number of failed tests can simply be accumulated by
adding the results with the sum being zero to indicate success. Of
course, a print can be added as well for visual inspection.

<snip>

 

[spinoza1111]

"io_x" <[email protected]> ha scritto nel messaggio

[...]

What about this?

I found some bugs
replace("string ", "", "append")
has to return "string append"
and not forever loop

Not in my code. If the target is null, I cause an error. Admittedly
the error handling is as Peter Seebach says, crude, so on my to-do
list is a less-crude error handler.

hope this post in not so much long and someone see it

#include <stdio.h>
#include <stdlib.h>
#define  P  printf

char* __stdcall  SostituisciPercS(char* origin, char*  whatSost, char*  sost);

// origin has to came from malloc memory
int  Print(char** origin, char*  whatSost, char*  sost)
{char  *p=SostituisciPercS(*origin, whatSost, sost);
 int   i;
 if(p==0)  return 0;
 P("Origin=%s|WhatS=%s|Sost=%s\n", *origin, whatSost, sost);
 P("Result=%s\n",  p);
 free(*origin); *origin=p;
 return  1;

}

int  test(void)
{int  r;
 char  *src, c;

 src=realloc(0, 1024);
 if(src==0)  return  0;
 for(r=0; ; ++r)
    {c="XYXYX--XYXYXY--XYXYXY"[r];
    // c="XY123XY456"[r];
     src[r]=c;
     if(c==0) break;
    }

 r = Print(&src, "", "append");
 if(r==0)   {free(src);  return  0;}

 r = Print(&src, "XY", "AB");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "--", "<-->");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "--", "<-->");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "<<", "|");
 if(r==0)   {free(src);return  0;}
 r = Print(&src, ">>", "|");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "ABABAB", "1234");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "ABABX", "ABCDEFG");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "-", "");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "||", "<<XXX>>");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "<X", "-");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, ">X", "--->");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "X>", "X--->");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "1234", "!");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "<-XX--->>!", "!");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "ABCD", "Hello");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "EFG", " World");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "!@#", "123456789");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "!!", "!");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "Hello", "Goodbye");
 if(r==0)   {free(src);  return  0;}
 r = Print(&src, "!", "! We are going to miss you!");
 if(r==0)   {free(src);  return  0;}

 r = Print(&src, "are", "");
 if(r==0)   {free(src);  return  0;}

 free(src);
 return 0;

}

// ---------------------------------------------------------------
// Statement-format test macro
//
//
#define TESTER(resultPtr, master, target, replacement, expected) \
{ \
    printf("Expect \"%s\":\n       \"%s\"\n\n", \
           (expected), \
           resultPtr = SostituisciPercS((master), \
                                 (target), \
                                 (replacement))); \
    free(resultPtr); \

}

// ---------------------------------------------------------------
// Main procedure
//
//
int test1(void)
{
    char *ptrResult;
    printf("\ntest1\n");
    TESTER(ptrResult,
           "a stupid error",
           "stupid error",
            "miracle",
           "a miracle")
    TESTER(ptrResult,
           "a stupid error",
           "stupid",
            "miracle",
           "a miracle error")
    TESTER(ptrResult,
           "the stupid error",
           "the stupid error",
            "a miracle",
           "a miracle")
    TESTER(ptrResult,
           "the miracle",
           "the",
            "a",
           "a miracle")
    TESTER(ptrResult,
           "a miraclsnirpKamunkle",
           "snirpKamunkle",
            "e",
           "a miracle")
    TESTER(ptrResult,
           "a miraclesnirpKamunkle",
           "a miracle",
            "",
           "snirpKamunkle")
    TESTER(ptrResult,
           " a miraclesnirpKamunkle",
           "a miracle",
            "",
           " snirpKamunkle")
    TESTER(ptrResult,
           " a miraclesnirpKamunklea miraclea miracle",
           "a miracle",
            "",
           " snirpKamunkle")
    TESTER(ptrResult,
           "a miracle a miraclesnirpKamunkle a Miraclea miraclea miracle",
           "a miracle",
            "",
           " snirpKamunkle a Miracle")
    TESTER(ptrResult,
           "a stupid errord",
           "stupid error",
            "miracle",
           "a miracled")
    TESTER(ptrResult,
           "a stupid errod",
           "stupid error",
            "miracle",
           "a stupid errod")
    TESTER(ptrResult,
           "a sstupid error",
           "stupid error",
            "miracle",
           "a smiracle")
    TESTER(ptrResult,
           "a stupid errorstupid error",
           "stupid error",
            "miracle",
           "a miraclemiracle")
    TESTER(ptrResult,
           "a stupid error stupiderror",
           "stupid error",
            "miracle",
           "a miracle stupiderror")
    TESTER(ptrResult,
           "bbbbbbbbbb",
           "b",
            "a",
           "aaaaaaaaaa")
    TESTER(ptrResult,
           "In the halls of R'yleh great %s lies dreaming",
           "%s",
            "Cthulu",
           "In the halls of R'yleh great Cthulu lies dreaming")
    TESTER(ptrResult,
           "%s%s%s%s%s%s",
           "%s",
            "Cthulu",
           "CthuluCthuluCthuluCthuluCthuluCthulu")
    TESTER(ptrResult,
           "banana",
           "ana",
            "oat",
           "boatna")
    TESTER(ptrResult,
           " a stupid errorstupid errorHeystupid errors",
           "stupid error",
            "+",
           " a ++Hey+s")
    TESTER(ptrResult,
           "foo barfoo barf",
           "foo bar",
            "bas",
           "basbasf")
    TESTER(ptrResult,
           "abab",
           "ba",
            "ba",
           "abab")
    printf("\n\nTesting complete: check output carefully!\n\n");
    return 0;

}

int  main(void)
{test();
 test1();
 return 0;

}

-------------------
section _DATA use32 public class=DATA

global SostituisciPercS
extern _realloc
extern _free

section _BSS  use32 public class=BSS
section _TEXT use32 public class=CODE

; 0k,4j,8i,12b,16ra, 20P_fmt, 24P_WhatSost 28P_Sost + 64
;                    84       88           92
; 0inString, 4sizeResult, 8NowArg
SostituisciPercS:
          push    ebx
          push    esi
          push    edi
          push    ebp
          sub     esp,  64
          mov     esi,  dword[esp+  84]
          cmp     dword[esp+  88],  0
          je      .e0
          cmp     dword[esp+  92],  0
          je      .e0
          cmp     esi,  0
          je      .e0           ; k=current arg, j array
          mov     edi,  0
          mov     dword[esp+  0],  0
          mov     dword[esp+  4],  0
          mov     dword[esp+  8],  0 ; ^8==led string sub ==\0==""
          mov     ebx,  0
          jmp     short  .0     ; 0led_isstring b is index [len]
.e:       push    edi
          call    _free
.e0:      xor     eax,  eax
          stc
          jmp     .z
.0:       cmp     ebx,  dword[esp+  4]
          jb      .1
          mov     ecx,  ebx
          add     ecx,  32
          push    ecx
          push    ecx
          push    edi
          call    _realloc
          add     esp,  8
          pop     ecx
          cmp     eax,  0
          je      .e
          mov     edi,  eax
          mov     dword[esp+  4],  ecx
.1:       cmp     dword[esp],  1
          jne     .3
          xor     eax,  eax
          mov     al,  [ebp]
          cmp     eax,  0
          jne     .2
          mov     dword[esp+  0],  0
          cmp     dword[esp+  8],  1
          je      .7
          jmp     short  .0
.2:       mov     byte[edi+ebx],  al
          inc     ebp
          inc     ebx
          jmp     short  .0
.3:       mov     ebp,  dword[esp+  88]
          xor     eax,  eax
          mov     ecx,  esi     ; cerca di vedere se le stringhe sono uguali
.4:       mov     al,  [ebp]
          cmp     eax,  0
          je      .5
          cmp     al,  [ecx]
          jne     .7
          inc     ecx
          inc     ebp
          jmp     short  .4
.5:       cmp     ecx,  esi
          jne     .5a           ; stringa nulla da sostituire
          cmp     al,  [ecx]
          jne     .7            ; se B*c==0 allora sostituisci, altrimenti
continua
          mov     dword[esp+  8],  1
.5a:      mov     dword[esp+  0],  1
          mov     esi,  ecx
          mov     ebp,  dword[esp+  92]
          jmp     .0
.ee:      jmp     .e
.7:       mov     al,  [esi]
          mov     byte[edi+ebx],  al
          inc     esi
          inc     ebx
          cmp     eax,  0
          je      .8
          jmp     .0
.8:       push    ebx
          push    edi
          call    _realloc
          add     esp,  8
          cmp     eax,  0
          je      .ee
          clc
.z:
          lea     esp,  [esp+64]
          pop     ebp
          pop     edi
          pop     esi
          pop     ebx
          ret     12
---------------------
Origin=XYXYX--XYXYXY--XYXYXY|WhatS=|Sost=append
Result=XYXYX--XYXYXY--XYXYXYappend
Origin=XYXYX--XYXYXY--XYXYXYappend|WhatS=XY|Sost=AB
Result=ABABX--ABABAB--ABABABappend
Origin=ABABX--ABABAB--ABABABappend|WhatS=--|Sost=<-->
Result=ABABX<-->ABABAB<-->ABABABappend
Origin=ABABX<-->ABABAB<-->ABABABappend|WhatS=--|Sost=<-->
Result=ABABX<<-->>ABABAB<<-->>ABABABappend
Origin=ABABX<<-->>ABABAB<<-->>ABABABappend|WhatS=<<|Sost=|
Result=ABABX|-->>ABABAB|-->>ABABABappend
Origin=ABABX|-->>ABABAB|-->>ABABABappend|WhatS=>>|Sost=|
Result=ABABX|--|ABABAB|--|ABABABappend
Origin=ABABX|--|ABABAB|--|ABABABappend|WhatS=ABABAB|Sost=1234
Result=ABABX|--|1234|--|1234append
Origin=ABABX|--|1234|--|1234append|WhatS=ABABX|Sost=ABCDEFG...

read more »

 

[spinoza1111]

It is not obvious that replace("string ", "", "append") should
return "string append". According to the specification, it
should replace all occurrences of the empty pattern "" in "string "
with the substitute "append".

You seem to claim that the empty pattern only occurs once,
at the end of "string ", but it would be equally valid to say that
an empty pattern occurs, for instance, between the 'r' and the 'i'
of "string ", so the result "strappending " would be okay, too.

One might even argue that "string " contains the empty pattern infinitely
often, and in that case it's only natural that replacing them all will
take forever ;-)

I just crap out with a deliberate planned abort() (which I shall
refine per Seebach: his participation is welcome insofar as he learns
manners thereby). This is because as you say there is no meaning to a
null target.

There are other theoretical issues such as left to right versus right
to left and whether ana occurs once or twice in banana which shall be
addressed, hopefully.

 

[Walter Banks]

I just crap out with a deliberate planned abort()

There are other theoretical issues such as left to right versus right
to left and whether ana occurs once or twice in banana which shall be
addressed, hopefully.

I seem to have missed the design and test spec for this exercise.

w..

 

[Seebs]

I seem to have missed the design and test spec for this exercise.

There really wasn't one.

The original goal was to calculate a particular value, then insert it at
marked locations into strings. We seem to have generalized to:
replace(a, b, c);
=> A newly allocated pointer containing a copy of c in which each occurrence
of a has been replaced by the contents of b, not rescanning for occurrences of
a.

-s

 

[spinoza1111]

There really wasn't one.

The original goal was to calculate a particular value, then insert it at
marked locations into strings.  We seem to have generalized to:
        replace(a, b, c);
=> A newly allocated pointer containing a copy of c in which each occurrence
of a has been replaced by the contents of b, not rescanning for occurrences of
a.

Das ist ein Anders, yet another consideration.

Repeat the replace until the number of replacements comes back as
zero. I suggest that there is no reason why this could not be built on
top of a one shot replace, with a name like rereplace or
mungUntilZero.

Certainly a consideration for my Issues list: should replace() provide
this, or is it really a separate function point? I am obliged to you
for a change.

It would probably be a mistake to overload replace() with a lot of
options. But given that we have seen that the function and its name
are so very polysemic, having multiple meanings, it is important to
clarify which of the particular styles of replace is supported.

Which the C libraries so signally fail to do. Instead, they present a
hegemonic view of reality, in which strings are "normally" terminated
with Nul, etc.

We have: left to right, right to left, some other order including
inside out and random, and repeated.

Ham.
Well said old Mole, can'st worke i'th' ground so fast?
A worthy Pioner, once more remoue good friends.

Hor.
Oh day and night: but this is wondrous strange.

Ham.
And therefore as a stranger giue it welcome.
There are more things in Heauen and Earth, Horatio,
Then are dream't of in our Philosophy.

An arrogant silence however reigns in the computing discourse which
proclaims that the solution is easy, simple, and unitary. Rather like
Tea Party politics.

 

[spinoza1111]

spinoza1111wrote:


I seem to have missed the design and test spec for this exercise.

Are you kidding? This is Extreme Programming. I just said to myself a
few days ago that it was time to show Peter how it's done. I sorta
decided, screw string.h. So the design contract was "develop a simple
replace() without using the string library". Which has been done.

I would like to return this newsgroup to collaborative work in an
atmosphere of civil discourse and common problem solving, as opposed
to the usual sniping. I did so in the Shakespeare group by getting my
enemies there to help me write a sonnet.

Richard Heathfield is probably closeted with Dr. Evil at this point,
getting yelled at for losing control of the group.

It's all good.

 

[spinoza1111]

Allow me to quote my post to clarify:


(line breaks altered from the original).

Note:  "something like this" is clearly intended to demonstrate that I am
talking about the *style* or *manner* of the Nilges code we've seen, such
as a hundred lines of extraordinarily bad code trying to solve a problem
that could easily be solved in about fifteen lines of code... and it
didn't even work after three or four edits to fix bugs introduced by
an overly baroque style.

I do not have any worries about people mistaking my parody code for
actual Nilges code, nor did I present it as such.  For one thing, I
didn't use the sort of bastardized and botched systems Hungarian Nilges
uses.  I can do a lot for art, but there are limits.  For another thing,
I did manage in a few places to go beyond the level of insanity we
normally see in his code.  For instance, <malloc.h> is silly, but
<emmintrin.h> is ridiculous.  (It's, so far as I can tell, a gcc internal).

I also cleaned it up some by using ~0 rather than -1 as "true" -- I figure
if you're going to ask for all-bits-one, you might as well do it explicitly.

In short, to some extent, it's not a very good caricature; I didn't really
pick up some of the most odious stuff, but I think I did a reasonable job
of capturing the essence of over-engineering informed by mind-numbing
ignorance, coupled with random and misdirected vitriol and name dropping.

-s

No, you did it for the same reason Richard claimed that I'd never been
accepted in the moderated group comp.risks. You hoped that people
would understand that your "parody" was representative of my code and
would be remembered instead. You threw shit at the wall to see what
would stick like an enraged toddler.

You see, Fascists and Nazis have no sense of humor whatsoever. The
Nazis highjacked cabaret satire of the Weimar era for their own
purposes. The progressive artists that created Weimar satire meant to
poke fun at the Establishment: the Nazis on the other hand wanted
their caricature of "der ewige Juden" to become the reality in the
public mind.

(Yeah, Godwin. As I have said before, Godwin doesn't know his ass from
a hole in the ground, because he doesn't know that the real tendency
in the downsized technical lower middle class is indeed towards
Fascism, and in many cases, the Hitler comparision is apt.)

In a grim little fashion, in the grim little way you "made fun of"
Herb Schildt to advance your career by destroying his (at which
project you failed), you're not having any fun at all. The way you
frantically posted Monday morning my time showed you were having a
panic attack because your pathetic little code had been carpet bombed
by a correct solution.

Your caricature isn't reality. The reality is that working a few hours
after not using C for near to twenty hours, I coded a far more
competent program. The style you call "baroque" is in fact a more
careful and precise layout and your term, "baroque", is used in the
slop corporate way, where "baroque", like "verbose", means, "I don't
have time to shave, so how does this unknown clown with a funny name,
how does this Nilges find the time to construct a complete sentence or
format code as to meaning?"

Finally, dear little Peter, my code works thanks to my efforts and the
testing of santosh and Ike Naar. You have yet to fix your original
solution. If this is "over-engineering", so be it.

You want the lazy and attention disordered, the creepy and the rude,
to just glance at this thread and see my name associated with the
caricature. Unfortunately the truth will out.

 

[spinoza1111]

spinoza1111wrote:

[...]
I don't know what's more funny- Spinoza's inability to get this simple
problem right, or Seebs' continued childish insistence that he only

As I said, I posted the code for COLLABORATIVE development and
testing,

If that's true, why did you make it so hard to read? Or, if you think it
*should* be hard to read, why didn't you make it harder to read?

and I received professional assistance from Santosh and Ike
Naar, which helped me to complete the project.

If that's a complete project, I'm a Dutchman.

That is what this ng was meant for: not for posting "satiric" code as
mine in an actionably libelous lie.

Santosh and Ike Naar found problems which I fixed in a few hours on
Sunday.

And I found a problem that took you several hours to fix all by itself.

You're Bedlam.

The "problems" to which you refer are "problems" only to fools like
you who irresponsibly believe that C code can be ported without line
by line review! Whereas in the past and up until Sunday I accepted
this trivial "portability of #include" points, I now realize you make
them because you're not qualified.

There are in fact strong arguments for keeping #include usage
idiomatic to a particular compiler, because code that has NOT been
reviewed line by line should not compile.

You don't understand that the worst bug is the one you don't know
about (such as the bugs you've left behind you at your clients). If a
"standard" approach is used with the "correct" includes, the code
below the includes can be in fact complete crap.

It is in fact, in C, malpractice to at any time claim "my code is
truly portable because it is standard, and I know all the fashionable
shibboleths". This is because there are hundreds, perhaps thousands,
of compilers for what is commonly understood to be C which violate
your standard. To make the claim without having several machines and
several compilers to hand, and without testing the code on each, is
irresponsible.

Yet this is what you recommend. It is very possible, of course, that
you have several machines and compilers in your rec room amidst the
pizza boxes and beer cans, and for your clients you may multitest. But
it's insane for you to think that everyone can or should do this.

I started out in computing long before you, in all probability. I find
it's "matured" to sclerosis, for it's become a field wherein people
think they're indemnified against the mess they make by rules
following, and refuse to take responsibility either for the problems
they cause or the malicious falsehoods they purvey.

Deleting a single line can be terribly, terribly, difficult, can't it?



That's up to him, but I can't say I'm overly excited by the idea of
being in the same comparison as you, and I don't suppose Seebs is either.

You are welcome to consider yourself a different order of being. Such
as Homunculus or Troglodyte. Or just plain blowhard and fool.

 

[spinoza1111]

spinoza1111wrote:

[...]
I don't know what's more funny- Spinoza's inability to get this simple
problem right, or Seebs' continued childish insistence that he only
As I said, I posted the code for COLLABORATIVE development and
testing,

If that's true, why did you make it so hard to read? Or, if you think it
*should* be hard to read, why didn't you make it harder to read?

If that's a complete project, I'm a Dutchman.

And I found a problem that took you several hours to fix all by itself.

You're Bedlam.

The "problems" to which you refer are "problems" only to fools like
you who irresponsibly believe that C code can be ported without line
by line review! Whereas in the past and up until Sunday I accepted
this trivial "portability of #include" points, I now realize you make
them because you're not qualified.

There are in fact strong arguments for keeping #include usage
idiomatic to a particular compiler, because code that has NOT been
reviewed line by line should not compile.

You don't understand that the worst bug is the one you don't know
about (such as the bugs you've left behind you at your clients). If a
"standard" approach is used with the "correct" includes, the code
below the includes can be in fact complete crap.

It is in fact, in C, malpractice to at any time claim "my code is
truly portable because it is standard, and I know all the fashionable
shibboleths". This is because there are hundreds, perhaps thousands,
of compilers for what is commonly understood to be C which violate
your standard. To make the claim without having several machines and
several compilers to hand, and without testing the code on each, is
irresponsible.

Yet this is what you recommend. It is very possible, of course, that
you have several machines and compilers in your rec room amidst the
pizza boxes and beer cans, and for your clients you may multitest. But
it's insane for you to think that everyone can or should do this.

I started out in computing long before you, in all probability. I find
it's "matured" to sclerosis, for it's become a field wherein people
think they're indemnified against the mess they make by rules
following, and refuse to take responsibility either for the problems
they cause or the malicious falsehoods they purvey.

Deleting a single line can be terribly, terribly, difficult, can't it?

That's up to him, but I can't say I'm overly excited by the idea of
being in the same comparison as you, and I don't suppose Seebs is either.

You are welcome to consider yourself a different order of being. Such
as Homunculus or Troglodyte. Or just plain blowhard and fool.

<snip>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within

Did anybody find this bug in my code? If you have already, please post
a link or time and date so I can credit you. I will also scan posts
for a previous report after I post a fix following this bug report. I
am particularly interested to know if Peter Seebach can prove he found
it before this time, since his day job seems to be bug finding, and he
is motivated through malice to find fault.

I was sitting on the subway thinking about improvements, and it hit
me: it is a MISTAKE to index as I index starting one past the end of a
partial match since a full match might start between that point and
the start of the partial match.

I pulled out my netbook and sure enough:

Replace "111123" by "ono" in "bbb1111123bbbbb"
Expect "bbbonobbbbb":
"bbb1111123bbbbb"
Replacements expected: 2: replacements: 0

I will post the fix and then check previous posts for someone else
finding this bug before me.

 

[santosh]

spinoza1111 wrote:
[...]

Did anybody find this bug in my code? If you have already, please post
a link or time and date so I can credit you. I will also scan posts
for a previous report after I post a fix following this bug report. I
am particularly interested to know if Peter Seebach can prove he found
it before this time, since his day job seems to be bug finding, and he
is motivated through malice to find fault.

I was sitting on the subway thinking about improvements, and it hit
me: it is a MISTAKE to index as I index starting one past the end of a
partial match since a full match might start between that point and
the start of the partial match.

I pulled out my netbook and sure enough:

Replace "111123" by "ono" in "bbb1111123bbbbb"
Expect "bbbonobbbbb":
"bbb1111123bbbbb"
Replacements expected: 2: replacements: 0

I will post the fix and then check previous posts for someone else
finding this bug before me.

This is a major bug! Actually this bug bit me about a couple of years
earlier, when I did a somewhat similar function. I think it's a common
"optimisation" mistake to make. Surprising that it wasn't found
earlier (in this instance I mean), but I'm pretty sure a bug report
hasn't been posted elsethread.

 

[Seebs]

This is a major bug! Actually this bug bit me about a couple of years
earlier, when I did a somewhat similar function. I think it's a common
"optimisation" mistake to make. Surprising that it wasn't found
earlier (in this instance I mean), but I'm pretty sure a bug report
hasn't been posted elsethread.

I don't think I noticed it. But yes, once you look, it's "obvious". Except
for being carefully buried under a sea of poorly-chosen variable names.

This was in the hand-written replacement for strstr(), which is a great
example of why you should just about ALWAYS use the standard library functions
when they have the right spec.

-s

 

[spinoza1111]

spinoza1111wrote:

[...]

Did anybody find this bug in my code? If you have already, please post
a link or time and date so I can credit you. I will also scan posts
for a previous report after I post a fix following this bug report. I
am particularly interested to know if Peter Seebach can prove he found
it before this time, since his day job seems to be bug finding, and he
is motivated through malice to find fault.

I was sitting on the subway thinking about improvements, and it hit
me: it is a MISTAKE to index as I index starting one past the end of a
partial match since a full match might start between that point and
the start of the partial match.

I pulled out my netbook and sure enough:

Replace "111123" by "ono" in "bbb1111123bbbbb"
Expect "bbbonobbbbb":
"bbb1111123bbbbb"
Replacements expected: 2: replacements: 0

I will post the fix and then check previous posts for someone else
finding this bug before me.

This is a major bug! Actually this bug bit me about a couple of years
earlier, when I did a somewhat similar function. I think it's a common
"optimisation" mistake to make. Surprising that it wasn't found
earlier (in this instance I mean), but I'm pretty sure a bug report
hasn't been posted elsethread.

The fix and latest regression tests are at the end of this post.

Strangely, although collaborative development from which grandstanding
and bullying are excluded finds a lot of bugs, I "found" this bug the
old fashioned way. I was on my way to work and pondering the Cormen
Algorithms chapter I'd reread last night on string searching.

The algorithms depend on "what you know" at any given time (and
unfortunately use tables which are a danger in C because of C's poor
ability to handle static data, but which are a natural for an OO
language like C Sharp).

I realized with a start that when I find a partial match (at the point
of failure) there are cases where one does not know whether a full
match starts between inputString[0] and inputString[j]!

I have fixed and fully regression tested this code.

Let the love begin, as Kenny would say. I am certain that Seebach
(although he doesn't seem to have found this error: I will check this
claim) and Heathfield will start capering and gibbering on cue (I am
more certain that Heathfield didn't find the error, being too busy
with Trivial Pursuits).

But my experience programming in the Seventies, when we often had to
write this type of code, is that (as is confirmed by Knuth) bugs
decrease logarithmically, but also that this doesn't imply that the
infrequent bugs later on in the curve won't be embarassing.



// ***************************************************************
// * *
// * replace() demo *
// * *
// * Demonstrates how to replace non-NUL-defined strings in C *
// * using a simple function, and bypassing string.h. *
// * *
// * C H A N G E R E C O R D --------------------------------- *
// * DATE PROGRAMMER DESCRIPTION OF CHANGE *
// * -------- ---------- --------------------------------- *
// * 02 07 10 Nilges Version 1.0 *
// * *
// * 02 07 10 Nilges Bug: partial matches not handled *
// * correctly: need to iterate search *
// * for match. *
// * *
// * 02 07 10 Nilges 1. Santosh suggested tests *
// * 2. Heathfield put the boot in re *
// * including malloc *
// * *
// * 02 07 10 Nilges 1. Remove string.h use and code *
// * strlen by hand *
// * 2. Add comment block and comments*
// * inline. *
// * 3. free() storage *
// * 4. Use macro for testing *
// * 5. Bug: calculation of *
// * lngNewLength used incorrect *
// * index (intIndex3 instead of 2)*
// * which caused a memory leak. *
// * *
// * 02 07 10 Nilges 1. Bug: Ike Naar test failed. *
// * At end of scan loop, main *
// * string pointer was not *
// * correctly updated from index3 *
// * *
// * 02 07 10 Nilges Added new Santosh test *
// * *
// * 02 07 10 Nilges Added new Ike Naar test *
// * *
// * 02 08 10 Nilges 1. Added some new comments *
// * 2. Make "check for a complete *
// * match "structured" by means *
// * of a tested assignment *
// * 3. Get rid of "replace at end" *
// * evilness: the only time this *
// * flag is meaningful is in the *
// * LAST segment. *
// * 4. Return replace count *
// * 5. TESTER macro assertion added *
// * *
// * 02 10 10 Nilges 1. Bug fix: in a partial match, *
// * the main scan index is set to *
// * one past the end, which misses*
// * full matches that start *
// * between the first character of*
// * the partial match and its end.*
// * *
// * No longer updating the main *
// * scan index (ptrIndex1) to the *
// * point of partial match *
// * failure: setting it one past *
// * the first character of the *
// * partial match. *
// * *
// * ----------------------------------------------------------- *
// * *
// * "In the near future we shall have to live with the *
// * superstition that programming is 'so easy that even a *
// * Republican can do it!'" *
// * *
// * - E. W. Dijkstra *
// * *
// * *
// ***************************************************************

#include <stdio.h>
#include <stdlib.h>

// ***** Segmentation *****
struct TYPsegmentstruct
{ char * strSegment;
long lngSegmentLength;
struct TYPsegmentstruct * ptrNext; };

// ---------------------------------------------------------------
// Calculate string length
//
//
long strLength(char *strInstring)
{
char *ptrInstring;
for (ptrInstring = strInstring; *ptrInstring; ptrInstring++);
return ptrInstring - strInstring;
}

// ---------------------------------------------------------------
// Replace target by replacement string in master string
//
//
// Caution: the string returned by this function should be freed.
//
//
char * replace(char * strMaster,
char * strTarget,
char * strReplacement,
long * ptrReplacements)
{
char * ptrIndex0;
char * ptrIndex1;
char * ptrIndex2;
char * ptrIndex3;
char * strNew;
char * strNewStart;
long lngNewLength;
long lngCount;
long lngReplacementLength;
struct TYPsegmentstruct * ptrSegmentStructStarts;
struct TYPsegmentstruct * ptrSegmentStruct;
struct TYPsegmentstruct * ptrSegmentStructPrev;
lngReplacementLength = strLength(strReplacement);
if (!*strTarget)
{
printf("Error in calling replace(): target can't be null");
abort();
}
ptrIndex1 = strMaster;
ptrSegmentStructPrev = 0;
lngNewLength = 0;
*ptrReplacements = 0;
while(*ptrIndex1)
{
ptrIndex0 = ptrIndex1;
while (-1)
{
// --- Check for (one character) handle
for(;
*ptrIndex1 && *ptrIndex1 != *strTarget;
ptrIndex1++);
// --- Check for complete match
for(ptrIndex2 = strTarget, ptrIndex3 = ptrIndex1;
*ptrIndex3
&&
*ptrIndex2
&&
*ptrIndex3 == *ptrIndex2;
ptrIndex3++, ptrIndex2++);
// End test: check complete match, update main ptr past
// partial match while checking for end of loop
if ((!*ptrIndex2 ? ((*ptrReplacements)++, -1) : 0)
||
(!*ptrIndex3 ? (ptrIndex1 = ptrIndex3, -1) : 0))
break;
ptrIndex1++;
}
// --- Create new segment
if (!(ptrSegmentStruct =
malloc(sizeof(struct TYPsegmentstruct))))
abort();
ptrSegmentStruct->strSegment = ptrIndex0;
ptrSegmentStruct->lngSegmentLength =
ptrIndex1 - ptrIndex0;
ptrSegmentStruct->ptrNext = 0;
if (ptrSegmentStructPrev != 0)
ptrSegmentStructPrev->ptrNext = ptrSegmentStruct;
else
ptrSegmentStructStarts = ptrSegmentStruct;
ptrSegmentStructPrev = ptrSegmentStruct;
// --- Update mallocation length
lngNewLength += ptrSegmentStruct->lngSegmentLength +
(!*ptrIndex2
?
lngReplacementLength
:
0);
// --- Get past end of target string & iterate
ptrIndex1 = ptrIndex3;
}
// --- Allocate just enough storage for the new string
if (!(strNewStart = malloc(lngNewLength + 1))) abort();
// --- Build the new string whilst freeing the list
strNew = strNewStart;
ptrSegmentStruct = ptrSegmentStructStarts;
while (ptrSegmentStruct)
{
for (ptrIndex1 = ptrSegmentStruct->strSegment,
lngCount = 0;
lngCount < ptrSegmentStruct->lngSegmentLength;
ptrIndex1++, lngCount++, strNew++)
*strNew = *ptrIndex1;
if (ptrSegmentStruct->ptrNext || !*ptrIndex2)
for (ptrIndex1 = strReplacement;
*ptrIndex1;
ptrIndex1++, ++strNew)
*strNew = *ptrIndex1;
ptrSegmentStructPrev = ptrSegmentStruct;
ptrSegmentStruct = ptrSegmentStruct->ptrNext;
free(ptrSegmentStructPrev);
}
*strNew = '\0';
return strNewStart;
}

// ---------------------------------------------------------------
// Statement-format test macro
//
//
#define TESTER(resultPtr, master, target, replacement, expected,
expectedReplacements, replacements) \
{ \
printf("Replace \"%s\" by \"%s\" in \"%s\"\n", \
(target), (replacement), (master)); \
printf("Expect \"%s\":\n\"%s\"\n", \
(expected), \
resultPtr = replace((master), \
(target), \
(replacement), \
&(replacements))); \
printf("Replacements expected: %d: replacements: %d\n", \
(expectedReplacements), \
(replacements)); \
if (!(strLength(resultPtr) \
== \
strLength(master) \
+ \
(strLength(replacement)-strLength(target)) \
* \
replacements)) \
printf("Assertion failed\n"); \
printf("\n\n"); \
free(resultPtr); \
}

// ---------------------------------------------------------------
// Main procedure
//
//
int main()
{
char *ptrResult;
long lngReplacements;
printf("\nReplace\n\n\n");
TESTER(ptrResult,
"a stupid error",
"stupid error",
"miracle",
"a miracle",
1,
lngReplacements)
TESTER(ptrResult,
"a stupid error",
"stupid",
"miracle",
"a miracle error",
1,
lngReplacements)
TESTER(ptrResult,
"the stupid error",
"the stupid error",
"a miracle",
"a miracle",
1,
lngReplacements)
TESTER(ptrResult,
"the miracle",
"the",
"a",
"a miracle",
1,
lngReplacements)
TESTER(ptrResult,
"a miraclsnirpKamunkle",
"snirpKamunkle",
"e",
"a miracle",
1,
lngReplacements)
TESTER(ptrResult,
"a miraclesnirpKamunkle",
"a miracle",
"",
"snirpKamunkle",
1,
lngReplacements)
TESTER(ptrResult,
" a miraclesnirpKamunkle",
"a miracle",
"",
" snirpKamunkle",
1,
lngReplacements)
TESTER(ptrResult,
" a miraclesnirpKamunklea miraclea miracle",
"a miracle",
"",
" snirpKamunkle",
3,
lngReplacements)
TESTER(ptrResult,
"a miracle a miraclesnirpKamunkle a Miraclea miraclea
miracle",
"a miracle",
"",
" snirpKamunkle a Miracle",
4,
lngReplacements)
TESTER(ptrResult,
"a stupid errord",
"stupid error",
"miracle",
"a miracled",
1,
lngReplacements)
TESTER(ptrResult,
"a stupid errod",
"stupid error",
"miracle",
"a stupid errod",
0,
lngReplacements)
TESTER(ptrResult,
"a sstupid error",
"stupid error",
"miracle",
"a smiracle",
1,
lngReplacements)
TESTER(ptrResult,
"a stupid errorstupid error",
"stupid error",
"miracle",
"a miraclemiracle",
2,
lngReplacements)
TESTER(ptrResult,
"a stupid error stupiderror",
"stupid error",
"miracle",
"a miracle stupiderror",
1,
lngReplacements)
TESTER(ptrResult,
"bbbbbbbbbb",
"b",
"a",
"aaaaaaaaaa",
10,
lngReplacements)
TESTER(ptrResult,
"In the halls of R'yleh great %s lies dreaming",
"%s",
"Cthulu",
"In the halls of R'yleh great Cthulu lies dreaming",
1,
lngReplacements)
TESTER(ptrResult,
"%s%s%s%s%s%s",
"%s",
"Cthulu",
"CthuluCthuluCthuluCthuluCthuluCthulu",
6,
lngReplacements)
TESTER(ptrResult,
"banana",
"ana",
"oat",
"boatna",
1,
lngReplacements)
TESTER(ptrResult,
" a stupid errorstupid errorHeystupid errors",
"stupid error",
"+",
" a ++Hey+s",
3,
lngReplacements)
TESTER(ptrResult,
"foo barfoo barf",
"foo bar",
"bas",
"basbasf",
2,
lngReplacements)
TESTER(ptrResult,
"abab",
"ba",
"ba",
"abab",
1,
lngReplacements)
TESTER(ptrResult,
"abab",
"bab",
"boop",
"aboop",
1,
lngReplacements)
TESTER(ptrResult,
"banana",
"ana",
"ono",
"bonona",
1,
lngReplacements)
TESTER(ptrResult,
"bbb1111123bbbbb",
"111123",
"ono",
"bbb1onobbbbb",
1,
lngReplacements)
printf("\n\nTesting complete: check output carefully: \"Assertion
failed\" should not occur!\n\n");
return 0;
}



Replace


Replace "stupid error" by "miracle" in "a stupid error"
Expect "a miracle":
"a miracle"
Replacements expected: 1: replacements: 1


Replace "stupid" by "miracle" in "a stupid error"
Expect "a miracle error":
"a miracle error"
Replacements expected: 1: replacements: 1


Replace "the stupid error" by "a miracle" in "the stupid error"
Expect "a miracle":
"a miracle"
Replacements expected: 1: replacements: 1


Replace "the" by "a" in "the miracle"
Expect "a miracle":
"a miracle"
Replacements expected: 1: replacements: 1


Replace "snirpKamunkle" by "e" in "a miraclsnirpKamunkle"
Expect "a miracle":
"a miracle"
Replacements expected: 1: replacements: 1


Replace "a miracle" by "" in "a miraclesnirpKamunkle"
Expect "snirpKamunkle":
"snirpKamunkle"
Replacements expected: 1: replacements: 1


Replace "a miracle" by "" in " a miraclesnirpKamunkle"
Expect " snirpKamunkle":
" snirpKamunkle"
Replacements expected: 1: replacements: 1


Replace "a miracle" by "" in " a miraclesnirpKamunklea miraclea
miracle"
Expect " snirpKamunkle":
" snirpKamunkle"
Replacements expected: 3: replacements: 3


Replace "a miracle" by "" in "a miracle a miraclesnirpKamunkle a
Miraclea miraclea miracle"
Expect " snirpKamunkle a Miracle":
" snirpKamunkle a Miracle"
Replacements expected: 4: replacements: 4


Replace "stupid error" by "miracle" in "a stupid errord"
Expect "a miracled":
"a miracled"
Replacements expected: 1: replacements: 1


Replace "stupid error" by "miracle" in "a stupid errod"
Expect "a stupid errod":
"a stupid errod"
Replacements expected: 0: replacements: 0


Replace "stupid error" by "miracle" in "a sstupid error"
Expect "a smiracle":
"a smiracle"
Replacements expected: 1: replacements: 1


Replace "stupid error" by "miracle" in "a stupid errorstupid error"
Expect "a miraclemiracle":
"a miraclemiracle"
Replacements expected: 2: replacements: 2


Replace "stupid error" by "miracle" in "a stupid error stupiderror"
Expect "a miracle stupiderror":
"a miracle stupiderror"
Replacements expected: 1: replacements: 1


Replace "b" by "a" in "bbbbbbbbbb"
Expect "aaaaaaaaaa":
"aaaaaaaaaa"
Replacements expected: 10: replacements: 10


Replace "%s" by "Cthulu" in "In the halls of R'yleh great %s lies
dreaming"
Expect "In the halls of R'yleh great Cthulu lies dreaming":
"In the halls of R'yleh great Cthulu lies dreaming"
Replacements expected: 1: replacements: 1


Replace "%s" by "Cthulu" in "%s%s%s%s%s%s"
Expect "CthuluCthuluCthuluCthuluCthuluCthulu":
"CthuluCthuluCthuluCthuluCthuluCthulu"
Replacements expected: 6: replacements: 6


Replace "ana" by "oat" in "banana"
Expect "boatna":
"boatna"
Replacements expected: 1: replacements: 1


Replace "stupid error" by "+" in " a stupid errorstupid errorHeystupid
errors"
Expect " a ++Hey+s":
" a ++Hey+s"
Replacements expected: 3: replacements: 3


Replace "foo bar" by "bas" in "foo barfoo barf"
Expect "basbasf":
"basbasf"
Replacements expected: 2: replacements: 2


Replace "ba" by "ba" in "abab"
Expect "abab":
"abab"
Replacements expected: 1: replacements: 1


Replace "bab" by "boop" in "abab"
Expect "aboop":
"aboop"
Replacements expected: 1: replacements: 1


Replace "ana" by "ono" in "banana"
Expect "bonona":
"bonona"
Replacements expected: 1: replacements: 1


Replace "111123" by "ono" in "bbb1111123bbbbb"
Expect "bbb1onobbbbb":
"bbb1onobbbbb"
Replacements expected: 1: replacements: 1




Testing complete: check output carefully: "Assertion failed" should
not occur!

 

[spinoza1111]

My mistake, you meant read-only const qualifiers. My apologies for
this misunderstanding. I will add the const  qualifiers to the next
version. Do you want to be credited?

Wait a minute, I recall a discussion in which the jury seems to be out
on const qualifiers.

 

[spinoza1111]

I don't agree. Use of const slightly improves the code, but I probably
wouldn't reject code at a walkthru for lack of const (I might comment
though).



"const" not "constants". "const" is a C keyword that indicates to the
compiler that the function isn't going to change the value. It labels
the parameters as strictly input only (it also the function using the
parameters as temporary variables- which should please you!). It has
semantics (in this case) of something like Ada's "in" parameters.
"const" is a bit like "assert" its much more powerful than you at
first appreciate.

OK, sounds like a good idea. I remember an earlier discussion on this.

 

[spinoza1111]

Fractionally before my time (I think).

I saw Dudley Moore in some film (Arthur??) in which he is by a swimming
pool where there is a small table with a phone on it (not in the pool

Needless to say, and entirely predictably, he tangles himself up in the
phone line and goes into the pool. With the phone.

It was very well done, I have to say, it looked almost entirely natural.
But the predictability of it turned it into a yawn.

These idiots are airing their deep knowledge of TV. Meanwhile there
was as they wrote a massive bug in my code just waiting, like a nubile
female, for them to find her, and garner glory and get a reason to
caper and gibber, and laugh at me to their heart's content. This was
the "misses full match that starts before the end of a partial match
bug" that I found by myself while brooding about my code.

I suppose I could claim to have planted the bug like a wiseguy and
troll, but gentlemen don't pull Sokal hoaxes on other people.

If you can't participate properly, scram.

 

[spinoza1111]

Seebie and Dicky are nodding gravely at each other. Meanwhile, both
seem to be missing the major bug I found.

News flash. This isn't the nasty little business office you are
probably seeking to return to as an extremely supernumerary
"consultant" you are. For all you know, I might work a bit and then
jerk off, work a little bit and then work out, work a bit and go to
ballet practice and then go to my real job, which is far more
rewarding than working with twerps like you.

I don't work for you and I shall never. Nor shall I ever hire you to
change a flat tire, much less code.

In your world, from which I've escaped, One Dimensional Men are
reduced to simple numbers, and managers and "senior programmers",
being in fact profoundly ignorant of the basics of their calling, have
only time to something that seems to work as a crude and brutal
metric.

 

[spinoza1111]

The original one (which was, admittedly, a hack) can't have been much more,
it was part of a much larger program that I think took about half an hour
total.  The one I posted that addressed that issue (but still had buggy
behavior for an empty find string) took around 10 minutes before breakfast --
it absolutely took less time than the interval between putting a frozen pizza
in the oven and taking it out, and the pizza was not burned.

Nasty little clerks hustle and bustle,
And rate themselves solely by the time it takes
Nasty little clerks make nasty mistakes
And refuse to fix them at all.

Why should it take more than five minutes?  It's very close to being
completely trivial.

Up next:  My astounding bragging continues as I claim to have spent "less
than an hour" writing a program to multiply corresponding numbers in two
arrays of equal length together, storing the results in a third array of
the same length.

(for (int i = 0; i < len; ++i) { c = a * b; })

-s
p.s.:  Someone let me know if Nilges tries to "improve" that, I'll have
to read it.

 

[spinoza1111]

To fix that you need Boyer-Moore, IIRC (which I think strstr uses ?)

It may or may not.  I'd guess most don't bother; it's more expensive for
the most common cases, and requires additional storage.

I got curious, and implemented one of these.  Mine's using the same
spec as the Nilges one, I think (I have no idea what he means by not
NUL terminated, all the strings are, although substrings aren't necessarily),
and passes common input cases.

FWIW, this took me about ten minutes total.  Errors:
        * Missing quote in one of the strings (caught by compiler)
        * const poisoning required me to redeclare s as a const char *
        * missed a quote in the Makefile for my test cases, which caused
          surprising (but correct for the input) results
        * initially wrote "u = resultlen" rather than "u = result" (caught
          by compiler)

The actual algorithm worked the first time.  

I'm not trying especially hard to optimize stuff away here, on the grounds
that for most real inputs, the cost of the string functions is probably
dwarfed by the cost of a single malloc/free.  I lack Nilges' strange fear
of <string.h>, but all I use is strlen, strstr, strcpy, and memcpy, all
of which are trivial to implement in a few lines of code.

I am genuinely amazed that the Nilges version is on its fourth or so iteration
and doesn't yet work.  I won't be surprised if someone finds a boundary
condition I missed... well, actually, I'll be a little surprised, because this
is a pretty simple algorithm.  In my preemptive defense, I just woke up less
than half an hour ago and haven't had breakfast yet.

        #include <stdio.h>
        #include <stdlib.h>
        #include <string.h>

        #define DEBUG

        char *
        rep(const char *in, const char *out, const char *target) {
                char *result = 0;
                const char *s;
                char *t, *u;
                size_t inlen, outlen, targetlen, resultlen;
                int count;

                if (!in || !out || !target)
                        return 0;
                inlen = strlen(in);
                outlen = strlen(out);
                targetlen = strlen(target);

                for (count = 0, t = strstr(target, in); t; t = strstr(t, in)) {
                        ++count;
                        t += inlen;
                }
                resultlen = targetlen + (outlen * count) - (inlen * count);
                result = malloc(resultlen + 1);
                if (!result)
                        return result;
                u = result;
                *u = '\0';
                s = target;
                for (t = strstr(target, in); t; t = strstr(t, in)) {
                        memcpy(u, s, (t - s));
                        u += (t - s);
                        memcpy(u, out, outlen + 1);
                        u += outlen;
                        t += inlen;
                        s = t;
                }
                strcpy(u, s);
        #ifdef DEBUG
                fprintf(stderr, "replaced %d occurrences, new length %d, actual %d\n",
                        count, (int) resultlen, (int) strlen(result));
        #endif

                return result;
        }

        int
        main(int argc, char **argv) {
                int i;
                if (argc < 4) {
                        fprintf(stderr, "usage: rep in out test ...\n");
                        exit(EXIT_FAILURE);
                }
                for (i = 3; i < argc; ++i) {
                        char *result = rep(argv[1], argv[2], argv);
                        printf("%s => %s\n", argv, result ? result : "<null>");
                        free(result);
                }
                return 0;
        }

-s

But later on you said this fails for a null string. So what's your
point? That you can write code with bugs in ten minutes? So can I.

I don't like your code and don't have the time to compile and test it,
so if I am incorrect in saying, based on your later claim, that the
specific code above doesn't work for null target, please correct me.
And do me the fucking courtesy of some of the diligence I and others
have shown in this thread, which is the collaborative development of a
simple piece of code, by coding, as I have, a decent regression test.
Stop wasting my time and that of others with "satire" which like the
Nazi use of satire in Weimar, is so utterly malicious as to be very
not funny.

 

[spinoza1111]

My code for this was written in about five minutes, I have not yet found a bug
in it (although it does have the documented limitation that, as of this
writing, it simply assumes that "%" will be the first character of "%s";

But THAT IS A BUG.

How dare you, how dare you, hold yourself to a different and lower
standard than you held Herb Schildt, a hard-working computer scientist
with a BS and MSCS in computer science?

Have you no sense of decency? At long last, have you no sense of
decency?