Monday, September 24, 2012

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"]));
});

6 comments:

Anonymous said...

I tried submitting this comment earlier, but I don't think it worked. I apologize if this ends up as a double post.

While this problem may be non-trivial in Dart, it can be somewhat trivial in other languages. I wrote up a little script in Clojure, available here, that passes all your tests and actually has lower computational complexity. (It is O(num_lines * length_common_indent).) Note that I am a beginner with Clojure, so an experienced Clojure developer would probably be able to produce more idiomatic and/or efficient code.

Shannon Behrens said...

Did you port the tests too? Are you sure the complexity is actually different?

Sebastian said...

I think going column by column (rather than line by line) does the trick.

Shannon Behrens said...

Cool.

Anonymous said...

I tried submitting this comment earlier, but I don't think it worked. I apologize if this ends up as a double post.

I came across this post again and thought I'd respond to your comments.

I added the tests to the gist. You can view them at the same URL.

Looking at it again, I noticed that since the code has to check every line if it is all whitespace (due to your requirement to ignore all-whitespace lines in determining the common indentation length), the Clojure code actually has complexity O(total_length_of_initial_whitespace_for_all_lines). I believe this is optimal and the same as your Dart code.

Aside from that, the rest of the Clojure algorithm has lower computational complexity than the rest of the Dart algorithm, because, as Sebastian pointed out, it goes column-by-column. While this may not matter in the overall complexity of the whole algorithm, it is interesting.

Regardless of the similar computational complexity, the Clojure code is shorter and IMHO easier to read and understand. I think the key reasons are the use of lazy sequences and functional techniques.

Shannon Behrens said...

> as Sebastian pointed out, it goes column-by-column

Yes, this is a good improvement.

> the Clojure code is shorter and IMHO easier to read and understand

Whether or not it is easier to understand depends on the reader. Even though I've written a bunch of Lisp code over the years, it's not immediately easier for me to understand. I'm sure it would be equally short in Haskell as well, and I'm sure I'd struggle to understand that too because it takes me a while to get into a Haskell mindset. I think for it to be easier to understand, you need some practice understanding things in the language in question.