Does anyone know how R computes the model matrix from a formula in aov() or lm()?

I wonder about some things. Just assume the models below makes sense (although it might not). You have factor S with 3 levels and 2 regression variables, x1 & x2. Printing model.matrix gives me 1st row output as below. I would like to know what R does when reading in the formula (taking into account the formula terms which are either factors or regression variables).

~S+x1+x2
(Intercept) S2 S3 x1 x2


The first case, R assumes S1 to be the intercept and fits the main effects each level of S and each of the regression variables. I think this should be correct.

~S:(x1+x2)
(Intercept) S1:x1 S2:x1 S3:x1 S1:x2 S2:x2 S3:x2


The second case, R expands the formula such that ~S:x1+S:x2. It considers S1:x1 which is the first term of the formula as a regression coefficient so it fits an ordinary intercept. Also, it fits all the linear combinations of levels of S and the regression variables.

~S*(x1+x2)
(Intercept) S2 S3 x1 x2 S2:x1 S3:x1 S2:x2 S3:x2


The third case, R expands the formula such that ~S+x1+x2+S:x1+S:x2. It considers S1 as the first term of the formula so it makes it its intercept. The main effects are fit first. Then something weird happens. Why does S2:x1 appear but not S1:x1 first? Furthermore, why does S2:x2 appear but not S1:x2 first?.

~S*(x1+x2)+F
(Intercept) S2 S3 x1 x2 F2 F3 S2:x1 S3:x1 S2:x2 S3:x2


The fourth case, I added a factor F with 3 levels into the equation. The formula expands so ~S+x1+x2+F. It appears that all main effect terms are brought forward but the order in which they appear in the equation is preserved. Then followed by interaction terms and after that higher order interaction terms(if there are). Since S1 appears first I would assume that S1 is the intercept. But why doesn't F1 appear before F2 , why doesn't S1:x1 appear before S2:x1 and why doesn't S1:x2 appear before S2:x2?

I may have a conceptual misunderstanding with intercepts and how it relates to how the coefficients are fitted. Thanks for the help in advance.