Showing posts with label regular expressions. Show all posts
Showing posts with label regular expressions. Show all posts

Friday, June 05, 2009

Waiting for Go-done

A coworker called this morning wanting to know how to get a list of files that do not contain the text 'Program complete' on any line. They run jobs in big batches, and each process writes its output to a separate file. The running times vary, and they wanted an easy way to see at a glance which processes are still running.

Running grep -v will print all lines that don't match the given pattern, but that doesn't help in this case because we want to treat the output files as though each contained a single line.

With the -c option, grep outputs the number of lines that matched. Say we have outputs named output1 through output4, and the odd-numbered jobs are finished. This would give us

$ grep -c 'Program complete' output*
output1:1
output2:0
output3:1
output4:0
The pattern requires quotes because it contains a space. Without the quotes, grep would search for Program in files named complete, output1, and so on.

The outputs for the processes still running are the ones containing zero matches, so let's look for those:

$ grep -c 'Program complete' output* | grep ':0$'
output2:0
output4:0
Remember that a dollar sign in a regular expression anchors the match to the end.

Quick cleanup with sed gives us the names of the outputs (backslash is the shell's line-continuation marker that lets us split long lines):

$ grep -c 'Program complete' output* | \
  grep ':0$' | \
  sed -e 's/:0$//'
output2
output4

UPDATE: Turns out there's a much easier way to do it. GNU grep has a --files-without-match option (aka -L), so the command is the simple

$ grep -L 'Program complete' output*
output2
output4

Wednesday, February 18, 2009

Scraping data from a program's output

Consider a (truncated) output from vmstat on AIX:
  2031616 memory pages
  1953185 lruable pages
   935166 free pages
        1 memory pools
   170943 pinned pages
     80.0 maxpin percentage
  ...
Say you want to grab the values for memory pages and free pages. Below, I explain a couple of ways to do it.
#! /usr/bin/perl

use warnings;
use strict;

no warnings "exec";

open my $fh, "vmstat -v |"
  or die "$0: can't execute vmstat: $!\n";

my %vmstat;

while () {
  chomp;
  my($n,$desc) = split " ", $_, 2;

  $vmstat{$desc} = $n;
}

print "Memory pages: $vmstat{'memory pages'}\n",
      "Free pages:   $vmstat{'free pages'}\n";
When the filename argument to open ends with a pipe, Perl runs the named command and makes its output available on the returned filehandle. I turn off the autogenerated error (no warnings "exec") because I like my format better.

Looking at vmstat's output, each line has a value and a description, so the plan is to read each line and stash the parameters where we can find them later. A hash is a perfect data structure for this task.

Most of the time, the pattern to the split operator is a regular expression, but with no arguments (or a pattern of a lone space) it acts like awk, throwing away leading whitespace. Because the descriptions contain spaces, we don't want to split on them and tell Perl to give us back exactly two fields. Because we've limited the number of splits, we have to remove the trailing newline with chomp.

The output is straightforward: print the desired values.

You can of course be more clever:

#! /usr/bin/perl

%vmstat = reverse `vmstat -v` =~ /(\S+) (.+)/g;

print "Memory pages: $vmstat{'memory pages'}\n",
      "Free pages:   $vmstat{'free pages'}\n";
Instead of a piped open, this time we use backticks (``) to capture vmstat's output and from the output extract the values and descriptions.

The regular expression \S+ means a sequence of one or more non-whitespace characters, and this matches the numbers in the output. You might be tempted to use \d+ (one or more digits), but this will give you surprising results on the floating-point numbers.

By default, dot does not match newline, so the (.+) subpattern matches through the rest of the current line — the description in this case.

The /g regular-expression switch means we get all possible non-overlapping matches.

The list returned from the match will look like (2031616, "memory pages", 1953185, "lruable pages", ...), but that's the opposite order from hash initialization, i.e., key then value. The reverse operator fixes this problem.

Friday, February 13, 2009

25 random songs

Bo hit me with the 25 random songs meme. Who wants to push buttons when you can write a program?
#! /usr/bin/perl

use warnings;
use strict;

use File::Find;

use constant CHOOSE_N => 25;

@ARGV = "." unless @ARGV;

my @mp3;
my $matches = sub {
  push @mp3 => $File::Find::name
    if /\.mp3$/i;
};

find $matches => @ARGV;

# Fisher-Yates-Knuth
for (my $n = $#mp3; $n >= 1; $n--) {
  my $k = int rand($n+1);
  @mp3[$k,$n] = @mp3[$n,$k];
}

for (1 .. CHOOSE_N) {
  last unless @mp3;
  my $song = shift @mp3;

  # e.g., .../Music/Bob Marley/Kaya/08 - Crisis.mp3
  if ($song =~ m!^.*/([^/]+)/[^/]+/\d+\s+-\s+(.+)\.!) {
    my($artist,$title) = ($1,$2);
    print qq{$_. "$title," $artist\n};
  }
}

The output:
  1. "The End," The Doors
  2. "Misty Morning," Bob Marley
  3. "My Mood Swings," Elvis Costello
  4. "Concerto Emperor: II. Adagio un poco moto," Ludwig van Beethoven
  5. "What's the Matter Here?," 10,000 Maniacs
  6. "Trench Town Rock," Bob Marley
  7. "Final Hour," Lauryn Hill
  8. "These Are Days," 10,000 Maniacs
  9. "Want-Ad Blues," John Lee Hooker
  10. "Loser," Beck
  11. "Sonata Pathétique: II. Adagio cantabile" Ludwig van Beethoven
  12. "Peer Gynt Suite No. 2: Ingrid's Lament," Edvard Grieg
  13. "4 Better or 4 Worse (interlude)," The Pharcyde
  14. "Bonita Applebum," A Tribe Called Quest
  15. "Hard Hearted Woman," John Lee Hooker
  16. "Jeremy," Pearl Jam
  17. "Toccata and Fugue in D minor," Johann Sebastian Bach
  18. "Ya Mama," The Pharcyde
  19. "Pennyroyal Tea," Nirvana
  20. "Concerto in C minor for Violin and Oboe," Johann Sebastian Bach
  21. "Sex Type Thing," Stone Temple Pilots
  22. "Drive," R.E.M.
  23. "People Are Strange," The Doors
  24. "Vivrant Thing - Violator (feat. Q-Tip)," A Tribe Called Quest
  25. "The New Pollution," Beck

Monday, December 29, 2008

Whose rev is it anyway?

Recently a teammate reported an inconsistency between our code and documentation: the cloud altitude in our rain model is supposed to be in units of meters with a default of 3km, but the default in the code was 10.

We checked both snapshots we thought they had, but both were in order. The last time the default changed in the trunk was over a year ago, and that was a change in units (i.e., 3.0 to 3000.0). 'Maybe they changed the code,' I thought but then remembered that the finger-pointing game is an evil at whose very root we must strike!

Principle is great — in principle — but now I had to hunt through more than a hundred tags to clear dB's name. That's a lot of clicky-clicky in the HTTP view. Instead, I could pull copies of rain_model.c from all hundred-plus tags and grep those.

Ugh. There ought to be a quicker way.

Then I remembered importing our Subversion repository into a Git repository using git-svn. With git-grep, searching through all those revisions is straightforward:

$ git grep 'cloud_altitude *= *[^3 ]' \
  `git branch -a | grep tags` -- \
  libs/env/rain_model.c
Joy!

The [^3 ] bit in the search pattern means find a character that's neither a 3 nor a space, the latter being necessary to prevent spuriously matching a space to the left of the value being assigned — effectively asking for all assignments in all tags to cloud_altitude. Not what we want.

Unlike Subversion, Git's operations are almost all local. That means fast! The above search ran in less than a quarter of a second.

Turns out the weird default was our doing after all, from a nearly two-year-old engineering release. Here's to keeping egg off our faces!

Thursday, October 05, 2006

Moral: a regular expression is a poor subsitute for a parser

A famous jwz soundbite is "Some people, when confronted with a problem, think 'I know, I'll use regular expressions.' Now they have two problems."

Snarky, yes, but a good sanity check.

Section 9 of the Perl FAQ addresses the issue of validating email addresses. RFC 2822 gives a specification for Internet email addresses, and the language is much broader than that matched by /^\w+@\w+\.\w+$/

The proper solution is to use a parser. To see why, consider the task of maintaining the following elegant -- but unit-tested! -- solution:

using System;
using System.Text.RegularExpressions;

using NUnit.Framework;

namespace Application
{
  public interface SyntaxChecker
  {
    bool WellFormed(string input);
  }

  public class EmailAddressChecker : SyntaxChecker
  {
    // derivative of work with the following copyright and license:
    // Copyright (c) 2004 Casey West.  All rights reserved.
    // This module is free software; you can redistribute it and/or
    // modify it under the same terms as Perl itself.

    // see http://search.cpan.org/~cwest/Email-Address-1.80/

    #region dumped regular expression
    private static string gibberish = @"
    (?-xism:(?:(?-xism:(?-xism:(?-xism:(?-xism:(?-xism:(?-xism:\
    s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^
    \x0A\x0D]))|(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))
    |(?-xism:\\(?-xism:[^\x0A\x0D]))|)+)*\s*\)\s*))+)*\s*\)\s*)+
    |\s+)*[^\x00-\x1F\x7F()<>\[\]:;@\,.<DQ>\s]+(?-xism:(?-xism:\
    s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^
    \x0A\x0D]))|(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))
    |(?-xism:\\(?-xism:[^\x0A\x0D]))|)+)*\s*\)\s*))+)*\s*\)\s*)+
    |\s+)*)|(?-xism:(?-xism:(?-xism:\s*\((?:\s*(?-xism:(?-xism:(
    ?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\((?
    :\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x
    0D]))|)+)*\s*\)\s*))+)*\s*\)\s*)+|\s+)*<DQ>(?-xism:(?-xism:[
    ^\\<DQ>])|(?-xism:\\(?-xism:[^\x0A\x0D])))+<DQ>(?-xism:(?-xi
    sm:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xis
    m:[^\x0A\x0D]))|(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\
    ]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|)+)*\s*\)\s*))+)*\s*\)\
    s*)+|\s+)*))+)?(?-xism:(?-xism:(?-xism:\s*\((?:\s*(?-xism:(?
    -xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:
    \s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[
    ^\x0A\x0D]))|)+)*\s*\)\s*))+)*\s*\)\s*)+|\s+)*<(?-xism:(?-xi
    sm:(?-xism:(?-xism:(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^(
    )\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\((?:\s*(
    ?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))
    |)+)*\s*\)\s*))+)*\s*\)\s*)+|\s+)*(?-xism:[^\x00-\x1F\x7F()<
    >\[\]:;@\,.<DQ>\s]+(?:\.[^\x00-\x1F\x7F()<>\[\]:;@\,.<DQ>\s]
    +)*)(?-xism:(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))
    |(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\((?:\s*(?-xism:
    (?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|)+)*\s
    *\)\s*))+)*\s*\)\s*)+|\s+)*)|(?-xism:(?-xism:(?-xism:\s*\((?
    :\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x
    0D]))|(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xi
    sm:\\(?-xism:[^\x0A\x0D]))|)+)*\s*\)\s*))+)*\s*\)\s*)+|\s+)*
    <DQ>(?-xism:(?-xism:[^\\<DQ>])|(?-xism:\\(?-xism:[^\x0A\x0D]
    )))+<DQ>(?-xism:(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\
    ]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\((?:\s*(?-x
    ism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|)+
    )*\s*\)\s*))+)*\s*\)\s*)+|\s+)*))\@(?-xism:(?-xism:(?-xism:(
    ?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?
    -xism:[^\x0A\x0D]))|(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^
    ()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|)+)*\s*\)\s*))+)*\s
    *\)\s*)+|\s+)*(?-xism:[^\x00-\x1F\x7F()<>\[\]:;@\,.<DQ>\s]+(
    ?:\.[^\x00-\x1F\x7F()<>\[\]:;@\,.<DQ>\s]+)*)(?-xism:(?-xism:
    \s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[
    ^\x0A\x0D]))|(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+)
    )|(?-xism:\\(?-xism:[^\x0A\x0D]))|)+)*\s*\)\s*))+)*\s*\)\s*)
    +|\s+)*)|(?-xism:(?-xism:(?-xism:\s*\((?:\s*(?-xism:(?-xism:
    (?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\((
    ?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\
    x0D]))|)+)*\s*\)\s*))+)*\s*\)\s*)+|\s+)*\[(?:\s*(?-xism:(?-x
    ism:[^\[\]\\])|(?-xism:\\(?-xism:[^\x0A\x0D])))+)*\s*\](?-xi
    sm:(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:
    \\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\((?:\s*(?-xism:(?-xism:(
    ?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|)+)*\s*\)\s*))+
    )*\s*\)\s*)+|\s+)*)))>(?-xism:(?-xism:\s*\((?:\s*(?-xism:(?-
    xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:\
    s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^
    \x0A\x0D]))|)+)*\s*\)\s*))+)*\s*\)\s*)+|\s+)*))|(?-xism:(?-x
    ism:(?-xism:(?-xism:(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^
    ()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\((?:\s*
    (?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D])
    )|)+)*\s*\)\s*))+)*\s*\)\s*)+|\s+)*(?-xism:[^\x00-\x1F\x7F()
    <>\[\]:;@\,.<DQ>\s]+(?:\.[^\x00-\x1F\x7F()<>\[\]:;@\,.<DQ>\s
    ]+)*)(?-xism:(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+)
    )|(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\((?:\s*(?-xism
    :(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|)+)*\
    s*\)\s*))+)*\s*\)\s*)+|\s+)*)|(?-xism:(?-xism:(?-xism:\s*\((
    ?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\
    x0D]))|(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-x
    ism:\\(?-xism:[^\x0A\x0D]))|)+)*\s*\)\s*))+)*\s*\)\s*)+|\s+)
    *<DQ>(?-xism:(?-xism:[^\\<DQ>])|(?-xism:\\(?-xism:[^\x0A\x0D
    ])))+<DQ>(?-xism:(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\
    \]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\((?:\s*(?-
    xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|)
    +)*\s*\)\s*))+)*\s*\)\s*)+|\s+)*))\@(?-xism:(?-xism:(?-xism:
    (?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(
    ?-xism:[^\x0A\x0D]))|(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[
    ^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|)+)*\s*\)\s*))+)*\
    s*\)\s*)+|\s+)*(?-xism:[^\x00-\x1F\x7F()<>\[\]:;@\,.<DQ>\s]+
    (?:\.[^\x00-\x1F\x7F()<>\[\]:;@\,.<DQ>\s]+)*)(?-xism:(?-xism
    :\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:
    [^\x0A\x0D]))|(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+
    ))|(?-xism:\\(?-xism:[^\x0A\x0D]))|)+)*\s*\)\s*))+)*\s*\)\s*
    )+|\s+)*)|(?-xism:(?-xism:(?-xism:\s*\((?:\s*(?-xism:(?-xism
    :(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\(
    (?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A
    \x0D]))|)+)*\s*\)\s*))+)*\s*\)\s*)+|\s+)*\[(?:\s*(?-xism:(?-
    xism:[^\[\]\\])|(?-xism:\\(?-xism:[^\x0A\x0D])))+)*\s*\](?-x
    ism:(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism
    :\\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\((?:\s*(?-xism:(?-xism:
    (?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|)+)*\s*\)\s*))
    +)*\s*\)\s*)+|\s+)*))))(?-xism:\s*\((?:\s*(?-xism:(?-xism:(?
    >[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0D]))|(?-xism:\s*\((?:
    \s*(?-xism:(?-xism:(?>[^()\\]+))|(?-xism:\\(?-xism:[^\x0A\x0
    D]))|)+)*\s*\)\s*))+)*\s*\)\s*)*)"
      .Replace("<DQ>", "\"")
      .Replace("\t", "")
      .Replace(" ", "")
      .Replace("\r", "")
      .Replace("\n", "");
    #endregion

    private static Regex mailbox =
      new Regex(gibberish, RegexOptions.ExplicitCapture);

    public bool WellFormed(string address)
    {
      return mailbox.IsMatch(address);
    }
  }

  [TestFixture]
  public class Test
  {
    private SyntaxChecker checker = null;

    [SetUp]
    public void SetUp()
    {
      checker = new EmailAddressChecker();
    }

    [Test]
    public void SimpleAddress()
    {
      Assert.IsTrue(checker.WellFormed("foo@example.com"));
    }

    [Test]
    public void MustHaveLocalAndDomain()
    {
      Assert.IsFalse(checker.WellFormed("justlocal"));
    }

    [Test]
    public void AmpersandInLocalPart()
    {
      Assert.IsTrue(checker.WellFormed("\"foo & bar\"@example.com"));
    }

    [Test]
    public void PhraseAndAngles()
    {
      Assert.IsTrue(checker.WellFormed("Joe <joe@example.com>"));
    }

    [Test]
    public void AddressAndComment()
    {
      Assert.IsTrue(checker.WellFormed("joe@example.com (Joe)"));
    }

    [Test]
    public void ContainsSingleQuoteInParenComment()
    {
      Assert.IsTrue(checker.WellFormed("oleary@example.com (Mr. O'Leary)"));
    }

    [Test]
    public void ContainsSingleQuoteInBareComment()
    {
      Assert.IsTrue(checker.WellFormed("Mr. O'Leary <oleary@example.com"));
    }

    [Test]
    public void ContainsSingleQuoteInLocalPart()
    {
      Assert.IsTrue(checker.WellFormed("o'leary@example.com"));
    }
  }
}