substitutions

[Jim Dehnert]

I'll take a shot at this, but please correct me if I get it wrong.

> From: Alain Miniussi <alainm at cup.hp.com>
> 
> Suppose that we need to encode the following 
> 
> C1::C2
> C1::C3::C4
> C1::C3::C5
> 
> in a name, we'll get :
> 
> N2C12C2E .... NS<n1>_2C32C4E  NS<n2>_2C5E ......

So, the substitution dictionary that gets built up is:

C1
C1::C2
...
C1::C3
C1::C3::C4
...
C1::C3::C6

Assuming nothing in the ellipses, these are, at the point of the last
one:
  S2_
  S1_
  S0_
  S_

> The problem:
> 
> We accept the substitution only if the size of the encoded 
> substitution is strictly smaller than the size of the
> substituted entity.
> 
> Now, let's say that S<n2>_ is longuer than S<n1>_2C3, what should
> we do ? 

Ah, I think I see your problem.  The entity that we're considering for
substitution is 2C12C3, _not_ S<n1>_2C3.  Earlier substitutions don't
come into play.

> Clearly, we can't write NS<n1>_2C3 instead of S<n2>_ because
> n1 does not reffers to the same entity at that point.

Right.  Our choices at this point are (with the above numbering)
2C12C3 (no substitution), S2_2C3 (substitute for C1), or S0_
(substitute for C1::C3).  We wouldn't choose the second because it's
not shorter, and would choose the third unless <n> were > 3 digits.

> If we are
> ready to replace n1 with it's updated value n1+delta, the rule
> and the implementation becomes more complicated (imagine that 
> we have something more complex than S<n1>_2C3, with some 
> substitued template args and so on...).

I don't think this is true if you recognize that you're not
substituting for already-substituted strings.  Do you?

> Now, the typical size of a substitution will be 3, encoded source 
> names are at least 2 char long (and I don't think it's the typical 
> size).
> So the only "real world" (but every one has it's own, so...) 
> waste of space of more than 1 char/substitution I can think of 
> involve builtin type. What about supressing the "smaller size" 
> rule and saying that builtin types can't be source of further 
> substitution ?

I don't feel strongly about this.  Does anyone else?

Jim

-	    Jim Dehnert		dehnert at sgi.com
				(650)933-4272