Dart: An Algorithm to Unindent Code

Have you ever had to write an algorithm to unindent a block of code consistently? Figuring out the maximum amount of whitespace among all the lines and then removing that amount of whitespace is non-trivial. Remembering to ignore lines that only have whitespace makes the problem even harder. Here's some Dart code that I wrote to do it. I do believe the performance is O(num_lines * max_line_length), which I think is optimal. It should be easy to port this to other languages if you need it:

/**
 * Remove the indentation from the given lines.
 * 
 * Only remove as much indentation as the line with the least amount of
 * indentation.
 */
List<String> unindentFilter(List<String> lines) {
  // Make a copy so that we can modify it in place.
  lines = new List<String>.from(lines);
  
  // Make sure there is at least one line.
  if (!lines.isEmpty()) {
  
    // Figure out how much indentation the first line has.
    var indentation = new List<String>();
    for (String char in lines[0].splitChars()) {
      if (char == " " || char == "\t") {
        indentation.add(char);
      } else {
        break;
      }      
    }
    
    // Figure out the least amount of indentation any of the other lines has.
    for (var i = 1; i < lines.length; i++) {
      String line = lines[i];
      List<String> chars = line.splitChars();
      
      // Lines that only have whitespace should be set to "" and ignored.
      var whitespaceOnly = true;
      for (var char in chars) {
        if (char != " " && char != "\t") {
          whitespaceOnly = false;
          break;
        }          
      }
      if (whitespaceOnly) {
        lines[i] = "";          
      } else {
        
        // If the line has something other than whitespace, see how its
        // indentation compares to the least amount of indentation we've
        // seen so far.
        for (var j = 0; j < indentation.length && j < chars.length; j++) {
          String char = chars[j];
          if ((char != " " && char != "\t") ||
              char != indentation[j]) {
            
            // We found a new line with less indentation.
            indentation.removeRange(j, indentation.length - j);
            break;
          } 
        }
      }
    }
    
    // Loop over all the lines, and remove the right amount of indentation.
    for (var i = 0; i < lines.length; i++) {
      String line = lines[i];
      
      // Ignore blank lines.
      if (line != "") {
        
        // Otherwise, trim off the right amount of indentation.
        List<String> chars = line.splitChars();
        List<String> unindented = chars.getRange(indentation.length, chars.length - indentation.length);
        lines[i] = Strings.concatAll(unindented);
      }
    }
  }
  
  return lines;
}

Here are some tests:

test("unindentFilter unindents code", () {
  expect(merger.unindentFilter(["  1",
                                "  2"]),
         equals(["1",
                 "2"]));
});

test("unindentFilter unindents code where the first line is indented the most", () {
  expect(merger.unindentFilter(["\t    1",
                                "\t  2",
                                "\t    3"]),
         equals(["  1",
                 "2",
                 "  3"]));
});

test("unindentFilter does nothing for unindented code", () {
  expect(merger.unindentFilter(["1",
                                "2",
                                "3"]),
         equals(["1",
                 "2",
                 "3"]));
});

test("unindentFilter handles empty lists", () {
  expect(merger.unindentFilter([]),
         equals([]));
});

test("unindentFilter does not try to handle inconsistent indentation", () {
  expect(merger.unindentFilter(["\t1",
                                "  2",
                                "    3"
                                "        4"]),
         equals(["\t1",
                 "  2",
                 "    3"
                 "        4"]));
});

test("unindentFilter handles really awkward short lines", () {
  expect(merger.unindentFilter(["    1",
                                "2"]),
         equals(["    1",
                 "2"]));
});

test("unindentFilter handles blank lines and lines with only indentation", () {
  expect(merger.unindentFilter(["  1",
                                "",
                                " ",
                                "    2"]),
         equals(["1",
                 "",
                 "",
                 "  2"]));
});