This is a interesting problem. You could create your own function to do the insert into which works as expected [I think], for all cases except the last one from @hogi. For that case though the function returns the same result as when that expression is called using Name Expr directly, so one could argue that this is the 'correct' result.
Update: the function below has a bug, only the first instance should be replaced..
Names default to here(1);
// Make a new function to show each step of Insert Into:
New Insert Into = function( {exp, newarg, debug = 0 }, local({hd, ar, ne},
//Get the outermost function
hd = Head(exp);
if(debug, show(name expr( hd ) ) );
//Replace that function with a list so insert into works as expected
ar = substitute(name expr( exp ), name expr( hd ), {});
if(debug, show(name expr( ar ) ) );
//Now add the new argument
Insert Into( ar, name expr( newarg ) );
if(debug, show(name expr( ar ) ) );
//and put the orignial function back
ne = substitute(name expr( ar ), {}, name expr( hd ));
if(debug, show(name expr( ne ) ) );
Name expr( ne );
) );
// Test with the examples in the original post, note that they match:
Show( New Insert Into( Expr( If( a ) ), Expr( If( b, c ) ) ) ); // If(a, If(b, c))
Show( New Insert Into( Expr( Not an If( a ) ), Expr( If( b, c ) ) ) ); // Not an If(a, If(b, c))
// Additional examples from hogi post
Show( New Insert Into( Expr( If( a, x ) ), Expr( If( b, c ) ) ) ); // If(a, x, If(b, c))
Show( New Insert Into( Expr( If( a ) ), Expr( If( b ) ) ) ); // If(a, If
Show( New Insert Into( Expr( List( a ) ), Expr( List( b ) ) ) ); // List(a, b)
Show( New Insert Into( Expr( Graph Builder( a ) ), Expr( Graph Builder( b ) ) ) ); // Graph Builder(a, Graph Builder(b))
Show( New Insert Into( Expr( Head( a ) ), Expr( Head( b ) ) ) ); // Head(a, Head(b))
Show( New Insert Into( Expr( Not( a ) ), Expr( Not( b ) ) ) ); // !a
// The last one doesn't seem right but that it is actually being 'fixed' after as it is created:
Show( New Insert Into( Expr( Not( a ) ), Expr( Not( b ) ), debug = 1 ) ); // !a
// This is the same result as if you just call that directly, so I think this is the 'correct' result
Name Expr( Not(a, !b) ); // !a
// **BUG**
// This function replaces all the Head expressions, note this line:
// Name Expr(ar) = {a, {b, c}}
Show( New Insert Into( Expr( If( a, If( b, c ) ) ), Expr( If( d, e ) ), 1 ) ); // If(a, If(b, c), If(d, e))
// So this is wrong:
Show( New Insert Into( Expr( If( a, { b, c } ) ), Expr( If( d, e ) ), 1 ) ); // If(a, If(b, c), If(d, e))
Here is the same function without the debug stuff:
New Insert Into = function( {exp, newarg }, local({hd, ar, ne},
hd = Head(exp);
ar = substitute(name expr( exp ), name expr( hd ), {});
Insert Into( ar, name expr( newarg ) );
ne = substitute(name expr( ar ), {}, name expr( hd ));
name expr( ne );
) );