Stringification - how does it work?

I know that:

#define foo 4  
#define str(s) #s

with str(foo) writes out: "foo", because stringify is executed first of text expansion, but this:

 #define xstr(s) str(s)
 #define str(s) #s
 #define foo 4

with xstr(foo) writes out: "4".

Why? What are the steps involved in the process?

The relevant steps of macro expansion are (per C 2011 [n1570] 6.10.3.1 and C++ 1998 16.3.1):

1. Process tokens that are preceded by # or ##.
2. Apply macro replacement to each argument.
3. Replace each parameter with the corresponding result of the above macro replacement.
4. Rescan for more macros.

Thus, with xstr(foo), we have:

1. The replacement text, str(s), contains no # or ##, so nothing happens.
2. The argument foo is replaced with 4, so it is as if xstr(4) had been used.
3. In the replacement text str(s), the parameter s is replaced with 4, producing str(4).
4. str(4) is rescanned. (The resulting steps produce ”4”.)

Note that the problem with str(foo) is that step 2, which would replace foo with 4, comes after step 1, which changes the argument to a string. In step 1, foo is still foo; it has not been replaced with 4, so the result is ”foo”.

This is why a helper macro is used. It allows us to get a step 2 performed, then use another macro to perform step 1.

First case

1. Evaluate str(foo): Substitute str(foo) with #foo, ie "foo"

Second case

1. Evaluate xstr(foo): Substitute xstr(foo) with str(<foo-value>), ie str(4)
2. Evaluate str(4): Substitute str(4) with #4, ie "4"

Generally,

preprocessor evaluates macro-functions expanding macro-variables, until it is nothing to evaluate:

If you define

#define xstr(s) str(s) + 1
#define str(s) s + 1

in the following code

#define foo 4

int main()
{
    std::cout << str(foo) << '\n' 
              << xstr(foo) << '\n' ;

} 

it would evaluate like

First string

1. Substitute str(foo) with <foo-value> + 1, ie 4 + 1
2. Nothing more to substitute. Finishing.

And result is 4 + 1

Second string

1. Substitute xstr(foo) with str(<foo-value>) + 1, ie str(4) + 1
2. Substitute str(4) with <4-value> + 1, ie 4 + 1
3. Nothing more to substitute.

And result is 4 + 1 + 1