title: What is a good heuristic for determining the tab width used in a source file?
body: <p>I would like to determine the tab width used in source files indented with spaces. 
  This is not hard for files with particularly regular indentation, where the leading spaces are only used for indentation, always in multiples of the tab width, and with indentation increasing one level at at time.
  But many files will have some departure from this sort of regular indentation, generally for some form of vertical alignment. I'm thus looking for a good heuristic to estimate what tab width was used, allowing some possibility for irregular indentation. </p>
  
  <p>The motivation for this is writing an extension for the SubEthaEdit editor. SubEthaEdit unfortunately doesn't make the tab width available for scripting, so I'm going to guess at it based on the text. </p>
  
  <p>A suitable heuristic should:</p>
  
  <ul>
  <li>Perform well enough for interactive use. I don't imagine this will be a problem, and just a portion of the text can be used if need be. </li>
  <li>Be language independent. </li>
  <li>Return the longest suitable tab width. For example, any file with a tab width of four spaces could also be a file with two-space tabs, if every indentation was actually by twice as many levels. Clearly, four spaces would be the right choice. </li>
  <li>Always get it right if the indentation is completely regular. </li>
  </ul>
  
  <p>Some simplifying factors:</p>
  
  <ul>
  <li>At least one line can be assumed to be indented.</li>
  <li>The tab width can be assumed to be at least two spaces. </li>
  <li>It's safe to assume that indentation is done with spaces only. It's not that I have anything against tabs---quite the contrary, I'll check first if there are any tabs used for indentation and handle it separately. This does mean that indentation mixing tabs and spaces might not be handled properly, but I don't consider it important.</li>
  <li>It may be assumed that there are no lines containing only whitespace. </li>
  <li>Not all languages need to be handled correctly. For example, success or failure with languages like lisp and go would be completely irrelevant, since they're not normally indented by hand. </li>
  <li>Perfection is not required. The world isn't going to end if a few lines occasionally need to be manually adjusted. </li>
  </ul>
  
  <p>What approach would you take, and what do you see as its advantages and disadvantages?</p>
  
  <p>If you want to provide working code in your answer, the best approach is probably to use a shell script that reads the source file from <code>stdin</code> and writes the tab width to <code>stdout</code>. Pseudocode or a clear description in words would be just fine, too. </p>
  
  <p><strong>Some Results</strong></p>
  
  <p>To test different strategies, we can apply different strategies to files in the standard libraries for language distributions, as they presumably follow the standard indentation for the language. I'll consider the Python 2.7 and Ruby 1.8 libraries (system framework installs on Mac OS X 10.7), which have expected tab widths of 4 and 2, respectively. Excluded are those files which have lines beginning with tab characters or which have no lines beginning with at least two spaces.  </p>
  
  <p>Python:</p>
  
  <pre><code>                     Right  None  Wrong
  Mode:                 2523     1    102
  First:                2169     1    456
  No-long (12):         2529     9     88
  No-long (8):          2535    16     75
  LR (changes):         2509     1    116
  LR (indent):          1533     1   1092
  Doublecheck (10):     2480    15    130
  Doublecheck (20):     2509    15    101
  </code></pre>
  
  <p>Ruby:</p>
  
  <pre><code>                     Right  None  Wrong
  Mode:                  594    29     51
  First:                 578     0     54
  No-long (12):          595    29     50
  No-long (8):           597    29     48
  LR (changes):          585     0     47
  LR (indent):           496     0    136
  Doublecheck (10):      610     0     22
  Doublecheck (20):      609     0     23
  </code></pre>
  
  <p>In these tables, "Right" should be taken as determination of the language-standard tab width, "Wrong" as a non-zero tab width not equal to the language-standard width, and "None" as zero tab-width or no answer. "Mode" is the strategy of selecting the most frequently occurring change in indentation; "First" is taking the indentation of the first indented line; "No-long" is FastAl's strategy of excluding lines with large indentation and taking the mode, with the number indicating the maximum allowed indent change; "LR" is Patrick87's strategy based on linear regression, with variants based on the change in indentation between lines and on the absolute indentation of lines; "Doublecheck" (couldn't resist the pun!) is Mark's modification of FastAl's strategy, restricting the possible tab width and checking whether half the modal value also occurs frequently, with two different thresholds for selecting the smaller width.</p>