#!/usr/bin/perl -l

use strict;
use warnings;

my $tree = ['and', ['or', 1, 2], ['not', 3], ['or', 4, 5, 6]];
my $opts = options($tree);

for my $o (@$opts) {
  print "OPTION: ", join(", ", @$o);
}


sub options {
  my ($tree, $opts) = @_;

  if (! $opts) {
    $opts = [ [] ];
    options($tree, $opts);
    return $opts;
  }

  else {
    my $op = $tree->[0];

    if ($op eq 'and') {
      for my $val (@$tree[1 .. $#$tree]) {
        if (ref($val) eq 'ARRAY' and ($val->[0] eq 'and' or $val->[0] eq 'or' or $val->[0] eq 'not')) {
          my $subtree = options($val);
          my @new;

          for my $branch (@$subtree) {
            for my $o (@$opts) {
              push @new, [ @$o, @$branch ];
            }
          }

          @$opts = @new;
        }

        else {
          for my $o (@$opts) {
            push @$o, $val;
          }
        }
      }
    }

    elsif ($op eq 'or') {
      my @new;

      for my $val (@$tree[1 .. $#$tree]) {
        if (ref($val) eq 'ARRAY' and ($val->[0] eq 'and' or $val->[0] eq 'or' or $val->[0] eq 'not')) {
          my $subtree = options($val);

          for my $branch (@$subtree) {
            for my $o (@$opts) {
              push @new, [@$o, @$branch];
            }
          }
        }

        else {
          for my $o (@$opts) {
            push @new, [@$o, $val];
          }
        }
      }

      @$opts = @new;
    }
  }
}