Automated testing on Windows with AppVeyor

AppVeyor is a continuous integration service similar to Travis CI, just on Windows. If you have a Perl module on GitHub, it's not that hard to have it run tests automatically on Windows; it's just not well documented.

(The following information was taken from http://blogs.perl.org/users/eserte/2016/04/testing-with-appveyor.html, the AppVeyor documentation, and random trial and error.)

First you need to sign in to AppVeyor with your GitHub account and let it access your repositories, as described on https://www.appveyor.com/docs/.

Then you need to add a .appveyor.yml file to your repository. Mine looks like this:

cache:
  - C:\strawberry

install:
  - if not exist "C:\strawberry" choco install strawberryperl -y
  - set PATH=C:\strawberry\c\bin;C:\strawberry\perl\site\bin;C:\strawberry\perl\bin;%PATH%
  - cd %APPVEYOR_BUILD_FOLDER%
  - cpanm --quiet --installdeps --with-develop --notest .

build_script:
  - perl Makefile.PL
  - gmake

test_script:
  - gmake test

The cache part tells AppVeyor to save the contents of C:\strawberry after every successful build and to restore C:\strawberry (if available) before starting a fresh build. See https://www.appveyor.com/docs/build-cache/.

The install script checks for the existence of C:\strawberry. If it's not there, Chocolatey (a Windows package manager) is used to install the Strawberry Perl package (currently using Strawberry Perl 5.26.1.1). Then the relevant program directories are added to the PATH.

The next commands switch to the build directory and install any module dependencies (I run author tests on AppVeyor, so I include developer dependencies).

The build_script and test_script parts are just the usual perl Makefile.PL && make && make test step. Strawberry Perl comes with GNU make now, so we can use gmake instead of the older dmake.

And that's it. My module (including development branches and pull requests) is now automatically tested on Windows.


This post is not directly related to core perl, but AppVeyor was discussed at the 2017 Perl 5 Hackathon and this is what got me to take a closer look at the system (and write up the results). We had a good time.

Sponsors for the Perl 5 Hackathon 2017

This conference could not have happened without the generous contributions from the following companies:

Booking.com, cPanel, craigslist, bluehost, Assurant, Grant Street Group

/Fizz|Buzz/

use v5.12.0;
use warnings;

s/\A(?:[0369]|[147][0369]*(?:[147][0369]*[258][0369]*)*(?:[147][0369]*[147]|[258])|[258][0369]*(?:[258][0369]*[147][0369]*)*(?:[258][0369]*[258]|[147]))*(?:0|[147][0369]*(?:[147][0369]*[258][0369]*)*5|[258][0369]*(?:[258][0369]*[147][0369]*)*[258][0369]*5)\z/Fizzbuzz/,
s/\A(?:[0369]|[147][0369]*(?:[147][0369]*[258][0369]*)*(?:[147][0369]*[147]|[258])|[258][0369]*(?:[258][0369]*[147][0369]*)*(?:[258][0369]*[258]|[147]))+\z/Fizz/,
s/\A[0-9]*[05]\z/Buzz/,
say
for 1 .. 100

Converting glob patterns to efficient regexes in Perl and JavaScript

In Glob Matching Can Be Simple And Fast Too Russ Cox benchmarked several glob implementations by matching the string a100 against the pattern (a*)nb. (Here exponentiation refers to string repetition, as in 'a' x 100 matched against ('a*' x $n) . 'b' in Perl syntax.) What he found was that some implementations returned results instantly whereas others got extremely slow as soon as n grew past 5, taking seconds, minutes and even hours to finish.

This problem is caused by excessive backtracking. It's possible to implement globbing without nested backtracking (and the linked article explains a simple algorithm to do so), but a naive recursive implementation will suffer from this issue. It affects some shells, FTP servers, and programming languages, including Perl: File::Glob uses code from BSD libc (which is affected, unlike glibc). A patch was written and the next File::Glob release will include a fixed algorithm.

But what really caught my eye was the way Python implements glob matching: It translates each glob pattern to a regex, then simply invokes the regex engine. This approach also suffers from exponential backtracking because Python's regex engine uses an exponential-time algorithm. As it turns out I do something very similar in some of my JavaScript code to support user-specified wildcards.

The question is: Does converting the pattern to a regex suffer from the same problem in JavaScript and Perl, and can we avoid excessive backtracking somehow?

At first blush it seems like Perl is not affected:

$ perl -e '("a" x 100) =~ /\A(?:a.*?){6}b\z/s'

returns instantly. But this is because a specific regex optimization kicks in: Perl first checks whether the fixed substring 'b' appears in the target string, and because it doesn't, the match fails immediately. We can defeat this optimization by switching to:

$ perl -e '("a" x 100) =~ /\A(?:a.*?){6}[bc]\z/s'

or

$ perl -e '("a" x 100) =~ /\A(?:a.*?){6}b.*?a\z/s'

(Warning: This takes 1½ minutes to finish on my system; increasing the 6 to 7 or 8 is not recommended.)

So this approach seems vulnerable:

#!/usr/bin/env perl
use strict;
use warnings;

sub glob2re {
    my ($pat) = @_;
    $pat =~ s{(\W)}{
        $1 eq '?' ? '.' :
        $1 eq '*' ? '.*?' :
        '\\' . $1
    }eg;
    return qr/\A$pat\z/s;
}

('a' x 100) =~ glob2re(('a*' x 7) . 'b*a');

The above code indeed takes a long time to finish.

What about JavaScript? Here's the equivalent code:

function glob2re(pat) {
    pat = pat.replace(/\W/g, function (m0) {
        return (
            m0 === '?' ? '[\\s\\S]' :
            m0 === '*' ? '[\\s\\S]*?' :
            '\\' + m0
        );
    });
    return new RegExp('^' + pat + '$');
}

glob2re('a*'.repeat(7) + 'b').test('a'.repeat(100));

(Note the extra suckiness: JavaScript has no /s flag so you need something like [\s\S] to match any character.)

I've only tried this in Firefox but it also takes a long time to finish.

Clearly the naive approach does not work well. Can we fix it?

The algorithm presented by Russ Cox works by limiting the stack of saved backtracking states to at most 1 entry (yeah, that's not much of a "stack" anymore). As soon as a new instance of * starts being processed, all previous backtracking information is forgotten.

In Perl we can get the same effect by using the (*PRUNE) control verb:

#!/usr/bin/env perl
use strict;
use warnings;

sub glob2re {
    my ($pat) = @_;
    $pat =~ s{(\W)}{
        $1 eq '?' ? '.' :
        $1 eq '*' ? '(*PRUNE).*?' :
        '\\' . $1
    }eg;
    return qr/\A$pat\z/s;
}

('a' x 100) =~ glob2re(('a*' x 70) . 'b*a');

With this tiny change (adding (*PRUNE) to the generated regex), even 70 wildcards in a single pattern pose no problem: The program finishes instantly.

Again, what about JavaScript? Here the situation is a bit more complicated because JavaScript doesn't support control verbs. Normally this wouldn't be much of a problem because we could just turn foo*bar*baz into /foo(?>.*?bar)(?>.*?baz)/ instead, using (?>...) (an independent subexpression) to limit backtracking. Unfortunately JavaScript doesn't support (?>...) either. But wait! We can combine capturing groups, positive look-ahead, and backreferences to simulate (?>foo): Just use (?=(foo))\1 instead. Well, what we really want is a backreference to the last thing we captured. Perl again makes this easy with a relative backreference (\g{-1}) but in JavaScript we're forced to use absolute numbering instead. We can still do it because we control the whole regex, we just have to do a bit more manual work:

function glob2re(pat) {
    function tr(pat) {
        return pat.replace(/\W/g, function (m0) {
            return (
                m0 === '?' ? '[\\s\\S]' :
                '\\' + m0
            );
        });
    }

    var n = 1;
    pat = pat.replace(/\W[^*]*/g, function (m0, mp, ms) {
        if (m0.charAt(0) !== '*') {
            return tr(m0);
        }
        var eos = mp + m0.length === ms.length ? '$' : '';
        return '(?=([\\s\\S]*?' + tr(m0.substr(1)) + eos + '))\\' + n++;
    });
    return new RegExp('^' + pat + '$');
}

glob2re('a*'.repeat(70) + 'b').test('a'.repeat(100));

The code is starting to look a bit crazy and the regexes it generates are even worse, but it does work: Even 70 wildcards finish instantly.

Conclusion: Yes, converting glob patterns to efficient regexes is possible. It's even trivial in Perl. In JavaScript we have to jump through some annoying hoops but in the end we still get a regex that does what we want.

Cool Perl 6 features available in Perl 5

Today I saw Damian Conway giving a talk at YAPC::NA 2016 (also known as The Perl Conference now :-). He was talking about some cool Perl 6 features, and I realized that some of them are available right now in Perl 5.

  • Parameter lists / "signatures"

    Instead of manually unpacking @_, you can just write sub foo($bar, $baz) { ... } to define a function with two arguments.

    This feature is available in core perl5 since version 20 (the syntax changed slightly and it produces better error messages since version 22). It's still experimental in version 24 (and produces corresponding warnings when enabled).

    However, the CPAN module Function::Parameters adds full support for parameter lists to every perl since 5.14 (albeit with a new keyword (fun and method) instead of sub). It's available right now and not experimental:

    use Function::Parameters qw(:strict);
    fun foo($bar, $baz) {
        ...
    }
    
  • Keyword arguments / named parameters

    By defining your subroutine as sub foo(:$state, :$head, :$halt) {}, you can call it as

    foo(
        head  => 0,
        state => 'A',
        halt  => 'Z',
    );
    

    or

    foo(
        halt  => 'Z',
        state => 'A',
        head  => 0,
    );
    

    or any argument order you like. You no longer have to remember the position of each argument, which is great, especially if your function takes more than 3 arguments (or you haven't touched the code in a month or three).

    This is also available in Function::Parameters from perl 5.14 onwards:

    use Function::Parameters qw(:strict);
    fun foo(:$state, :$head, :$halt) {
    }
    
  • Interpolating blocks in strings

    Perl 5 lets you interpolate variables in double-quoted strings, which can be very convenient:

    say "$greeting, visitor! Would you like some $beverage?";
    

    However, this is limited to variables (scalars and arrays/array slices). There's no way to directly interpolate, say, method or function calls. That's why Perl 6 lets you interpolate arbitrary code in strings by using { blocks }:

    say "2 + 2 = {2 + 2}";  # "2 + 2 = 4"
    

    This feature is available in Quote::Code on CPAN for all perls since 5.14:

    use Quote::Code;
    say qc"2 + 2 = {2 + 2}";
    
  • Funny Unicode variable names

    One of the examples (Pollard ρ-factorization) uses (that's a Greek lowercase rho) as a variable name because Perl 6 supports Unicode in programs by default.

    Perl 5 doesn't. By default, that is. But after a use utf8; declaration, you can put arbitrary Unicode text in your string literals, regexes, etc. And it works for variables, too:

    # this works on any perl version >= 5.8
    use utf8;
    my $ρ = 42;
    print $ρ, "\n";
    

Of course there were many, many other things that are not so easily ported from Perl 6. But I think it's nice how much Just Works (or can be made to work with minimal effort) in existing Perl 5 code.

Perl curio: For loops and statement modifiers

Perl has a "statement modifier" form of most control structures:

EXPR if EXPR;
EXPR unless EXPR;
EXPR while EXPR;
EXPR until EXPR;
EXPR for EXPR;

Perl also has a C-style for loop:

for (INIT; COND; STEP) {
    ...
}

The curious part: COND is a normal expression, but STEP allows statement modifiers. That is, you can write:

for (my $i = 0; $i < 10; $i++ if rand() < 0.5) {
    print "$i\n";
}