In this particular case there's possibly a faster method though:

s/^(?!(?>.*?toto.*?foo))(.*?)foo/${1}bar/s;

If toto or foo can be found in the near beginning, Abigail's pattern is a winner. This is, I guess, due to the overhead of the (?>) assertion. But the farther away toto or foo is the worse it gets for the step-by-step method (/(?:(?!foo).)*/), and the (?>) pattern gets faster. (This isn't just a theoretical win. Even though the overhead due to (?>), that pattern might very well win in a real-life situation.)

But if I shall look at the big picture for a while though; in this case I find it hard to believe that any pattern can beat the plain and simple

s/foo/bar/ unless /toto.*?foo/s;

Even silly constructions like

s/foo(?(?{index($`, 'toto') != -1})(?!))/bar/;

is faster than the more generic solutions.

Cheers,
-Anomo