1

I'm looking for an algorithm that can generate optimized syntactically valid variable names (for javascript in this case) without collisions.

So as general rule I would want something that generated

aa, ab, ac .... az, a1, a2, a3, a4, a5, a6, a7, a8, a9 ba, bb, bc.... bz, b1.... zz...z9... aaa,aab....

it does not generate them at once, it does it going through a code base and does it whenever certain conditions are found (This will actually be done using a gulp plugin so this doesn't need to take walking the AST into account). Therefore it needs to be able to know what the current variable to be generated should be based on what the last variable was.

So that if the last variable is aaz it would know to do aa1 and if the last variable is azz it would know to do az1 and so forth.

  • 2
    So basically, you want to recreate the normal decimal number system, but with a larger alphabet? – Kilian Foth Sep 30 '15 at 8:43
  • I guess that's an accurate summation. although when you put it that way it starts to give me a solution. Probably not the most optimal though. – user254694 Sep 30 '15 at 9:07
3

There are many more valid variable names than those generated by the series in your question, but I'll be going along with it because it is simple and might be good enough.

Ideally we would to keep track of how many variables have been generated and simply map that number to the next variable name. Dealing with the incrementing nameSeed variable should be easy, and there's a very handy function for the next step in JavaScript, which matches our desired functionality almost exactly: Number#toString(radix). radix is 10 by default (giving the decimal representation of the number) but can be up to 36, which includes not only the digits 0-9 but also the letters a-z.

For example, (30).toString(36) gives u. (400).toString(36) gives b4. Unfortunately, (1).toString(36) gives 1, which is not a valid identifier and there are infinitely more cases where the same kind of failure happens...

If you only want "kind of minimal", you can prepend _ and have a valid identifier.

If you really want minimal (within the bounds of 0-9, a-z), we need to modify the algorithm to avoid those invalid names. We also need to avoid things like undefined, var, etc.. There may be a good strategy to do this "pre-emptively", but I will simply be validating the result and fixing it (as well as the nameSeed) if it needs fixing.

The function below takes a seed to use for the name, and returns the generated name as well as the next potential seed. If the given seed would produce an invalid result, it uses the first valid seed larger than the given seed (if all seeds were valid, we would not have to return the "next" one, but now it is necessary since we may have skipped some).

function generateName( seed ) {
  var name = seed.toString( 36 );
  if ( isNaN( name.substring( 0, 1 ) ) ) {
    // The name starts with a letter, now see if it collides with any builtins
    if ( builtins.indexOf( name ) < 0 ) {
      // Got a good name
      return { nextSeed: seed + 1, name: name };
    } else {
      // There's a collision, try the next seed
      return generateName( seed + 1 );
    }
  } else {
    // The name starts with a digit, just replace it with 'a' and try again
    // We could use the same strategy as above (just increment seed), but that might take a long time... better to jump to something with a good chance of working.
    name = "a" + name.substring( 1 );
    var newSeed = parseInt( name, 36 );
    return generateName( newSeed );
  }
}

Constructing the builtins array is left as an exercise for the reader...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.