Ah, I see: it matches zero occurances, succeeds, and stops looking. Changing it to s/x+//; shows that it does indeed march forward if it doesn't find a match; it just happens that * is always happy.