[PATCH 01 of 22] New viff.sfdl package for SFDL related code

[Martin Geisler]

1 file changed, 18 insertions(+)
viff/sfdl/__init__.py | 18 ++++++++++++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518456 -3600
# Node ID acb9d741bb061ff7efb13601fed4a7f573e77be1
# Parent ee2eb3441cd9fc2c17ff1afb6a0a6591350cbec0
New viff.sfdl package for SFDL related code.

diff --git a/viff/sfdl/__init__.py b/viff/sfdl/__init__.py
new file mode 100644
--- /dev/null
+++ b/viff/sfdl/__init__.py
@@ -0,0 +1,18 @@
+# Copyright 2008 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+"""Support for parsing SFDL programs."""

[Martin Geisler]

2 files changed, 31 insertions(+), 2 deletions(-)
viff/sfdl/grammar.py | 15 +++++++++++++--
viff/test/sfdl/test_grammar.py | 18 ++++++++++++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518457 -3600
# Node ID d6c03577b82c2d26f7f0827c0e51bc6d10f47b95
# Parent 6afba4921987626a0211d1861aecccce808c7b02
Constant declarations.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -15,16 +15,27 @@
# You should have received a copy of the GNU Lesser General Public
# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.

-from pyparsing import Suppress, Word, Keyword, \
- cppStyleComment, alphas, alphanums
+from pyparsing import Suppress, Word, Keyword, ZeroOrMore, \
+ delimitedList, \
+ oneOf, operatorPrecedence, opAssoc, \
+ cppStyleComment, alphas, alphanums, nums

class SFDLGrammar:

def __init__(self):
+ SCOLON = Suppress(";")
+ EQUAL = Suppress("=")
LCURLY, RCURLY = Suppress("{"), Suppress("}")

self.ident = ident = Word(alphas + "_", alphanums + "_")

+ self.const_atom = const_atom \
+ = Word(nums) | delimitedList(ident, '.')
+ self.const_expr = const_expr \
+ = operatorPrecedence(const_atom, [(oneOf("+ -"), 2, opAssoc.LEFT)])
+ self.const_dec = const_dec \
+ = Keyword("const") + ident + EQUAL + const_expr + SCOLON
+
self.program = program = Keyword("program") + ident \
+ LCURLY + RCURLY
program.ignore(cppStyleComment)
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -65,5 +65,23 @@
self.assertParse(self.grammar.program, src,
['program', 'empty'])

+ def test_const_atom(self):
+ self.assertParse(self.grammar.const_atom, "123", ['123'])
+ self.assertParse(self.grammar.const_atom, "foo", ['foo'])
+ self.assertParse(self.grammar.const_atom, "x.y", ['x', 'y'])
+ self.assertParse(self.grammar.const_atom, "x.y.z", ['x', 'y', 'z'])
+
+ def test_const_expr(self):
+ self.assertParse(self.grammar.const_expr, "1 + 2", [['1', '+', '2']])
+ self.assertParse(self.grammar.const_expr, "1 + x", [['1', '+', 'x']])
+ self.assertParse(self.grammar.const_expr, "10 + (x - 20)",
+ [['10', '+', ['x', '-', '20']]])
+
+ def test_const_dec(self):
+ self.assertParse(self.grammar.const_dec, "const x = 10;",
+ ['const', 'x', '10'])
+ self.assertParse(self.grammar.const_dec, "const x = 10 + y;",
+ ['const', 'x', ['10', '+', 'y']])
+
if SFDLGrammar is None:
TestGrammar.skip = "Could not import SFDLGrammar, missing pyparsing?"

[Martin Geisler]

4 files changed, 112 insertions(+)
viff/test/sfdl/mp-millionaires.sfdl | 23 ++++++++++++++
viff/test/sfdl/mp-secondpriceauction.sfdl | 45 +++++++++++++++++++++++++++++
viff/test/sfdl/mp-voting.sfdl | 33 +++++++++++++++++++++
viff/test/sfdl/test_examples.py | 11 +++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518476 -3600
# Node ID ca37920c34868b17549b5bcf0fa17bbf07f05ebb
# Parent 4c16d331284ddcdffcc690c1703c769a16fa7519
Added multiparty SFDL examples.
The examples have been downloaded from the FairPlay project:

http://www.cs.huji.ac.il/project/Fairplay/fairplayMP.html

diff --git a/viff/test/sfdl/mp-millionaires.sfdl b/viff/test/sfdl/mp-millionaires.sfdl
new file mode 100644
--- /dev/null
+++ b/viff/test/sfdl/mp-millionaires.sfdl
@@ -0,0 +1,23 @@
+/*
+ * Alice, Bob and Charlie are player types.
+ * Alice has input and output, Bob only has an input and Charlie only has an output.
+ * alice0, alice1, bob and charlie are the players who participate in the protocol.
+ * alice0 is of type Alice. Her output is 1 if she is richer than bob.
+ * alice1 is of type Alice. Her output is 1 if she is richer than alice0 and than bob.
+ * charlie is of type Charlie. His output is 1 if bob is richer than alice0.
+ */
+program Millionaires{
+ type int = Int<4>;
+
+ type Alice = struct {int input, Boolean output};
+ type Bob = struct {int input};
+ type Charlie = struct {Boolean output};
+
+ function void main (Alice[2] alice, Bob bob, Charlie charlie){
+ alice[0].output = (alice[0].input > bob.input);
+ alice[1].output = (alice[1].input > alice[0].input)
+ && (alice[1].input > bob.input);
+ charlie.output = (bob.input > alice[0].input);
+ }
+}
+
diff --git a/viff/test/sfdl/mp-secondpriceauction.sfdl b/viff/test/sfdl/mp-secondpriceauction.sfdl
new file mode 100644
--- /dev/null
+++ b/viff/test/sfdl/mp-secondpriceauction.sfdl
@@ -0,0 +1,45 @@
+/**
+ * Performs a 2nd price auction between 4 bidders.
+ * At the end only the winning bidder and the seller know the identity of the winner
+ * Everyone knows the 2nd highest price,
+ * Nothing else is known to anyone.
+ **/
+program SecondPriceAuction{
+ const nBidders = 4;
+ type Bid = Int<4>; // enough bits to represent a small bid.
+ type WinningBidder = Int<3>; // enough bits to represent a winner (nBitters bits).
+
+ type SellerOutput = struct{WinningBidder winner, Bid winningPrice};
+ type Seller = struct{SellerOutput output}; // Seller has no input
+
+ type BidderOutput = struct{Boolean win, Bid winningPrice};
+ type Bidder = struct{Bid input, BidderOutput output};
+
+ function void main(Seller seller, Bidder[nBidders] bidder){
+ var Bid high;
+ var Bid second;
+ var WinningBidder winner;
+ winner = 0; high = bidder[0].input; second = 0;
+
+ // Making the auction.
+ for(i=1 to nBidders-1){
+ if(bidder[i].input > high){
+ winner = i;
+ second = high;
+ high = bidder[i].input;
+ }
+ else {
+ if(bidder[i].input > second)
+ second = bidder[i].input;
+ }
+ }
+
+ // Setting the result.
+ seller.output.winner = winner;
+ seller.output.winningPrice = second;
+ for(i=0 to nBidders-1){
+ bidder[i].output.win = (winner == i);
+ bidder[i].output.winningPrice = second;
+ }
+ }
+}
\ No newline at end of file
diff --git a/viff/test/sfdl/mp-voting.sfdl b/viff/test/sfdl/mp-voting.sfdl
new file mode 100644
--- /dev/null
+++ b/viff/test/sfdl/mp-voting.sfdl
@@ -0,0 +1,33 @@
+/**
+ * Performs a voting between two candidates.
+ * At the end all the voters know who won.
+ * Nothing else is known to anyone.
+ **/
+program voting{
+ const nVoters = 5;
+ type VotesCount = Int<4>; // Enough bits to count up to 5 voters.
+
+ // Two candidates (in two's compliment).
+ type Vote = Int<2>;
+ type Voter = struct{Vote input, Vote output};
+
+ function void main(Voter[nVoters] voters){
+ var VotesCount[2] vc;
+ var Vote win;
+
+ // Making the voting.
+ for(i=0 to nVoters-1){
+ if(voters[i].input == 0)
+ vc[0] = vc[0] + 1;
+ else
+ vc[1] = vc[1] + 1;
+ }
+
+ if (vc[1] > vc[0])
+ win = 1;
+
+ // Setting the result.
+ for(i=0 to nVoters-1)
+ voters[i].output = win;
+ }
+}
diff --git a/viff/test/sfdl/test_examples.py b/viff/test/sfdl/test_examples.py
--- a/viff/test/sfdl/test_examples.py
+++ b/viff/test/sfdl/test_examples.py
@@ -49,6 +49,17 @@
def test_median(self):
self.assertParse("median.sfdl")

+class TestMultiPlayerParsing(TestCase, ParsingMixin):
+
+ def test_mp_millionaires(self):
+ self.assertParse("mp-millionaires.sfdl")
+
+ def test_mp_secondpriceauction(self):
+ self.assertParse("mp-secondpriceauction.sfdl")
+
+ def test_mp_voting(self):
+ self.assertParse("mp-voting.sfdl")
+

if SFDLGrammar is None:
TestParsing.skip = "Could not import SFDLGrammar, missing pyparsing?"

[Martin Geisler]

2 files changed, 129 insertions(+), 1 deletion(-)
viff/sfdl/grammar.py | 13 ++++
viff/test/sfdl/test_grammar.py | 117 ++++++++++++++++++++++++++++++++++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518457 -3600
# Node ID 188dabcb4cdd7efeab8db6d88b26ef81c1348656
# Parent bc1b37d69c6193ea1b657675ec20a1c48dd168fa
Assignment, if and for statements.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -16,7 +16,7 @@
# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.

from pyparsing import Suppress, Word, Keyword, ZeroOrMore, Optional, Group, \
- Forward, delimitedList, \
+ OneOrMore, Forward, delimitedList, \
oneOf, operatorPrecedence, opAssoc, \
cppStyleComment, alphas, alphanums, nums

@@ -64,6 +64,17 @@
(oneOf("== !="), 2, opAssoc.LEFT),
(oneOf("&& || ! ^"), 2, opAssoc.LEFT)])

+ self.stm = stm = Forward()
+ self.assign_stm = assign_stm = qual_ident + EQUAL + expr + SCOLON
+ self.if_stm = if_stm = Keyword("if") + Group(LPAREN + expr + RPAREN) + stm \
+ + Optional(Keyword("else") + stm)
+ self.for_stm = for_stm = Keyword("for") + LPAREN \
+ + Group(ident + EQUAL + const_expr) \
+ + Keyword("to") + Group(const_expr) + RPAREN + stm
+ self.block_stm = block_stm = LCURLY + OneOrMore(stm) + RCURLY
+ stm << Group(assign_stm | if_stm | for_stm | block_stm)
+
+
self.program = program = Keyword("program") + ident \
+ LCURLY + RCURLY
program.ignore(cppStyleComment)
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -163,5 +163,122 @@
['h', 'z', '[', '1', ']']]
]])

+ def test_assign_stm(self):
+ self.assertParse(self.grammar.assign_stm, "x = 1;", ['x', '1'])
+ self.assertParse(self.grammar.assign_stm, "x[1] = 1;",
+ ['x', '[', '1', ']', '1'])
+ self.assertParse(self.grammar.assign_stm, "x.y = a[1] * b.c;",
+ ['x', '.', 'y',
+ ['a', '[', '1', ']', '*', 'b', '.', 'c']])
+
+ def test_if_stm(self):
+ self.assertParse(self.grammar.if_stm, "if (x == 10) y = false;",
+ ['if', [['x', '==', '10']], ['y', 'false']])
+ self.assertParse(self.grammar.if_stm, "if (x == 10) { y = false; }",
+ ['if', [['x', '==', '10']], [['y', 'false']]])
+ self.assertParse(self.grammar.if_stm,
+ "if (x == 10) { y = false; z = 0; }",
+ ['if', [['x', '==', '10']],
+ [['y', 'false'],
+ ['z', '0']]])
+
+ def test_if_else_stm(self):
+ self.assertParse(self.grammar.if_stm,
+ "if (x == 10) y = false; else z = false;",
+ ['if', [['x', '==', '10']],
+ ['y', 'false'],
+ 'else',
+ ['z', 'false']])
+
+ src = """
+ if (x < 10) {
+ y = false;
+ z = 0;
+ } else
+ x = x + 1;
+ """
+ self.assertParse(self.grammar.if_stm, src,
+ ['if', [['x', '<', '10']],
+ [['y', 'false'],
+ ['z', '0']],
+ 'else',
+ ['x', ['x', '+', '1']]])
+
+ def test_nested_if_stm(self):
+ src = """
+ if (x < 10) {
+ y = false;
+ if (x < 5) {
+ z = 0;
+ } else {
+ x = x + 1;
+ }
+ }
+ """
+ self.assertParse(self.grammar.if_stm, src,
+ ['if', [['x', '<', '10']],
+ [['y', 'false'],
+ ['if', [['x', '<', '5']],
+ [['z', '0']],
+ 'else',
+ [['x', ['x', '+', '1']]]]]])
+
+ src = """
+ if (x < 10) {
+ y = false;
+ if (x < 5)
+ z = 0;
+ else
+ x = x + 1;
+ }
+ """
+ self.assertParse(self.grammar.if_stm, src,
+ ['if', [['x', '<', '10']],
+ [['y', 'false'],
+ ['if', [['x', '<', '5']],
+ ['z', '0'],
+ 'else',
+ ['x', ['x', '+', '1']]]]])
+
+ def test_dangling_else(self):
+ src = """
+ if (x < 10)
+ if (x < 5)
+ z = 0;
+ else
+ x = x + 1;
+ """
+ # The inner else should bind to the inner if.
+ self.assertParse(self.grammar.if_stm, src,
+ ['if', [['x', '<', '10']],
+ ['if', [['x', '<', '5']],
+ ['z', '0'],
+ 'else',
+ ['x', ['x', '+', '1']]]])
+
+ def test_for_stm(self):
+ self.assertParse(self.grammar.for_stm,
+ "for (i = 0 to 10) { x[i] = 42; }",
+ ['for', ['i', '0'], 'to', ['10'],
+ [['x', '[', 'i', ']', '42']]])
+
+ src = """
+ for (i = MIN to MIN + 10) {
+ b[i] = x[i] < x[i+1];
+ y[i] = b[i] && z[i];
+ }
+ """
+ self.assertParse(self.grammar.for_stm, src,
+ ['for', ['i', 'MIN'], 'to', [['MIN', '+', '10']],
+ [['b', '[', 'i', ']',
+ ['x', '[', 'i', ']',
+ '<',
+ 'x', '[', ['i', '+', '1'], ']']],
+ ['y', '[', 'i', ']',
+ ['b', '[', 'i', ']',
+ '&&',
+ 'z', '[', 'i', ']']]]])
+
+
if SFDLGrammar is None:
TestGrammar.skip = "Could not import SFDLGrammar, missing pyparsing?"

[Martin Geisler]

2 files changed, 7 insertions(+), 2 deletions(-)
viff/sfdl/grammar.py | 4 ++++
viff/test/sfdl/test_grammar.py | 5 +++--


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518476 -3600
# Node ID 01b0e928dcbeea1b22329f4356840f3e49fefe30
# Parent ad84b1d50412b49b96041aae42210635723d89bc
Store type declarations in global scope.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -89,6 +89,7 @@

int_type.setParseAction(self.parse_int_type)
data_type.setParseAction(self.parse_data_type)
+ type_dec.setParseAction(self.parse_type_dec)

self.expr = expr = Forward()
self.qual_ident = qual_ident = ident \
@@ -172,3 +173,6 @@
return attrdict(length=toks[1])
else:
return toks
+
+ def parse_type_dec(self, s, loc, toks):
+ self.global_scope[toks[1]] = toks[2]
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -156,8 +156,9 @@
def test_type_dec(self):
self.assertParse(self.grammar.type_dec, "type x = Boolean;",
['type', 'x', 'Boolean'])
- self.assertParse(self.grammar.type_dec, "type x = AnotherType[4];",
- ['type', 'x', attrdict(length=4)])
+ self.assertParse(self.grammar.type_dec, "type xs = AnotherType[4];",
+ ['type', 'xs', attrdict(length=4)])
+ self.assertParse(self.grammar.const_expr, "xs.length", [4])


def test_qual_ident(self):

[Martin Geisler]

2 files changed, 49 insertions(+)
viff/sfdl/grammar.py | 12 ++++++++++++
viff/test/sfdl/test_grammar.py | 37 +++++++++++++++++++++++++++++++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518457 -3600
# Node ID 0763eaf0c1dd39d41795810bfeb29329c674cfff
# Parent d7a1eac0ed9675650ef09894e672cffcd554cc49
Parsing of data types.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -37,6 +37,18 @@
self.const_dec = const_dec \
= Keyword("const") + ident + EQUAL + const_expr + SCOLON

+
+ self.data_type = data_type = Forward()
+ self.struct_field = struct_field = Group(data_type + ident)
+ self.struct_type = struct_type = Keyword("struct") \
+ + "{" + delimitedList(struct_field) + "}"
+ self.known_type = known_type \
+ = (Keyword("Int") + "<" + const_expr + ">") \
+ | Keyword("Boolean") | struct_type | Keyword("void")
+ data_type << (known_type | ident) \
+ + ZeroOrMore(Group('[' + const_expr + ']'))
+
+
self.expr = expr = Forward()
self.qual_ident = qual_ident = ident \
+ ZeroOrMore(("[" + expr + "]") | ("." + ident))
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -92,6 +92,43 @@
self.assertNoParse(self.grammar.const_dec, "const x;")
self.assertNoParse(self.grammar.const_dec, "const x 123;")

+ def test_known_type(self):
+ self.assertParse(self.grammar.known_type, "Boolean", ['Boolean'])
+ self.assertParse(self.grammar.known_type, "void", ['void'])
+
+ def test_int_type(self):
+ self.assertParse(self.grammar.known_type, "Int<8>",
+ ['Int', '<', '8', '>'])
+ self.assertParse(self.grammar.known_type, "Int<MAX>",
+ ['Int', '<', 'MAX', '>'])
+ self.assertParse(self.grammar.known_type, "Int<MAX+1>",
+ ['Int', '<', ['MAX', '+', '1'], '>'])
+
+ def test_struct_type(self):
+ self.assertParse(self.grammar.struct_type, "struct { Boolean x }",
+ ['struct', '{', ['Boolean', 'x'], '}'])
+ self.assertParse(self.grammar.struct_type,
+ "struct { Boolean x, Boolean y }",
+ ['struct', '{',
+ ['Boolean', 'x'],
+ ['Boolean', 'y'],
+ '}'])
+ self.assertParse(self.grammar.struct_type,
+ "struct { struct { Boolean x } y }",
+ ['struct', '{',
+ ['struct',
+ '{',
+ ['Boolean', 'x'],
+ '}', 'y'],
+ '}'])
+
+ def test_data_type(self):
+ self.assertParse(self.grammar.data_type, "Boolean[4]",
+ ['Boolean', ['[', '4', ']']])
+ self.assertParse(self.grammar.data_type, "Int<MAX>[MIN]",
+ ['Int', '<', 'MAX', '>', ['[', 'MIN', ']']])
+
+
def test_qual_ident(self):
self.assertParse(self.grammar.qual_ident, "x.y", ['x', '.', 'y'])
self.assertParse(self.grammar.qual_ident, "x[10]",

[Martin Geisler]

1 file changed, 2 insertions(+), 2 deletions(-)
viff/test/sfdl/test_grammar.py | 4 ++--


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518457 -3600
# Node ID 293f2a5d6e7ef7d95e8f453d78e95651e3379633
# Parent d6c03577b82c2d26f7f0827c0e51bc6d10f47b95
Require that the entire string is parsed.

diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -26,11 +26,11 @@
class TestGrammar(TestCase):

def assertParse(self, parser, src, expected):
- result = parser.parseString(src)
+ result = parser.parseString(src, parseAll=True)
self.assertEquals(result.asList(), expected)

def assertNoParse(self, parser, src):
- self.assertRaises(ParseException, parser.parseString, src)
+ self.assertRaises(ParseException, parser.parseString, src, True)

def setUp(self):
self.grammar = SFDLGrammar()

[Martin Geisler]

2 files changed, 11 insertions(+), 7 deletions(-)
viff/sfdl/grammar.py | 8 ++++++--
viff/test/sfdl/test_grammar.py | 10 +++++-----


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518476 -3600
# Node ID afb975f68296d2d278c1dbe449a4d61fc0e2fa5a
# Parent 26aeb27a29aa51078f6e9487febfb0a0939e5111
Parsing of integer types.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -77,15 +77,16 @@
self.struct_field = struct_field = Group(data_type + ident)
self.struct_type = struct_type = Keyword("struct") \
+ "{" + delimitedList(struct_field) + "}"
+ self.int_type = int_type = Keyword("Int") + "<" + const_expr + ">"
self.known_type = known_type \
- = (Keyword("Int") + "<" + const_expr + ">") \
- | Keyword("Boolean") | struct_type | Keyword("void")
+ = int_type | Keyword("Boolean") | struct_type | Keyword("void")
data_type << (known_type | ident) \
+ ZeroOrMore(Group('[' + const_expr + ']'))

self.type_dec = type_dec \
= Keyword("type") + ident + EQUAL + data_type + SCOLON

+ int_type.setParseAction(self.parse_int_type)

self.expr = expr = Forward()
self.qual_ident = qual_ident = ident \
@@ -160,3 +161,6 @@
else:
result = op(result, sym)
return result
+
+ def parse_int_type(self, s, loc, toks):
+ return attrdict(bitsize=toks[2])
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -119,13 +119,13 @@

def test_int_type(self):
self.assertParse(self.grammar.known_type, "Int<8>",
- ['Int', '<', 8, '>'])
+ [attrdict(bitsize=8)])

self.grammar.global_scope['MAX'] = 10
self.assertParse(self.grammar.known_type, "Int<MAX>",
- ['Int', '<', 10, '>'])
+ [attrdict(bitsize=10)])
self.assertParse(self.grammar.known_type, "Int<MAX+1>",
- ['Int', '<', 11, '>'])
+ [attrdict(bitsize=11)])

def test_struct_type(self):
self.assertParse(self.grammar.struct_type, "struct { Boolean x }",
@@ -151,7 +151,7 @@
self.grammar.global_scope['MIN'] = 17
self.grammar.global_scope['MAX'] = 4
self.assertParse(self.grammar.data_type, "Int<MAX>[MIN]",
- ['Int', '<', 4, '>', ['[', 17, ']']])
+ [attrdict(bitsize=4), ['[', 17, ']']])

def test_type_dec(self):
self.assertParse(self.grammar.type_dec, "type x = Boolean;",
@@ -357,7 +357,7 @@
"""
self.assertParse(self.grammar.program, src,
['program', 'p',
- ['type', 'Byte', 'Int', '<', 8, '>']])
+ ['type', 'Byte', attrdict(bitsize=8)]])

src = """
program p {

[Martin Geisler]

1 file changed, 30 insertions(+)
viff/sfdl/grammar.py | 30 ++++++++++++++++++++++++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518456 -3600
# Node ID 14a1378185796f4db0fdafe46ee4c774017eb49e
# Parent acb9d741bb061ff7efb13601fed4a7f573e77be1
Minimal grammar, parses empty program.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
new file mode 100644
--- /dev/null
+++ b/viff/sfdl/grammar.py
@@ -0,0 +1,30 @@
+# Copyright 2008 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+from pyparsing import Suppress, Word, Keyword, \
+ cppStyleComment, alphas, alphanums
+
+class SFDLGrammar:
+
+ def __init__(self):
+ LCURLY, RCURLY = Suppress("{"), Suppress("}")
+
+ self.ident = ident = Word(alphas + "_", alphanums + "_")
+
+ self.program = program = Keyword("program") + ident \
+ + LCURLY + RCURLY
+ program.ignore(cppStyleComment)

[Martin Geisler]

2 files changed, 50 insertions(+)
viff/sfdl/grammar.py | 7 ++++++
viff/test/sfdl/test_grammar.py | 43 ++++++++++++++++++++++++++++++++++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518473 -3600
# Node ID f10262f030b9a3c42f031b61f82b8da5dcbc5286
# Parent 188dabcb4cdd7efeab8db6d88b26ef81c1348656
Parsing of function declarations, with tests.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -74,6 +74,13 @@
self.block_stm = block_stm = LCURLY + OneOrMore(stm) + RCURLY
stm << Group(assign_stm | if_stm | for_stm | block_stm)

+ self.func_arg = func_arg = data_type + ident
+ self.func_var_dec = func_var_dec = Keyword("var") + data_type \
+ + Group(delimitedList(ident)) + SCOLON
+ self.func_body = func_body = ZeroOrMore(Group(func_var_dec)) + OneOrMore(stm)
+ self.func_dec = func_dec = Keyword("function") + data_type + ident \
+ + LPAREN + Optional(delimitedList(Group(func_arg))) + RPAREN \
+ + LCURLY + func_body + RCURLY

self.program = program = Keyword("program") + ident \
+ LCURLY + RCURLY
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -279,6 +279,49 @@
'&&',
'z', '[', 'i', ']']]]])

+ def test_func_var_dec(self):
+ self.assertParse(self.grammar.func_var_dec, "var Boolean x;",
+ ['var', 'Boolean', ['x']])
+ self.assertParse(self.grammar.func_var_dec, "var Byte a, b, c;",
+ ['var', 'Byte', ['a', 'b', 'c']])
+ self.assertNoParse(self.grammar.func_var_dec, "var x;")
+
+ def test_func_body(self):
+ self.assertParse(self.grammar.func_body, "x = 1;", [['x', '1']])
+ self.assertParse(self.grammar.func_body, "var Byte x; x = 1;",
+ [['var', 'Byte', ['x']], ['x', '1']])
+ self.assertParse(self.grammar.func_body,
+ "var Byte x; var Boolean y; x = 1;",
+ [['var', 'Byte', ['x']],
+ ['var', 'Boolean', ['y']],
+ ['x', '1']])
+
+ self.assertNoParse(self.grammar.func_body, "")
+ # Function body with no statements:
+ self.assertNoParse(self.grammar.func_body, "var Byte x;")
+
+ def test_func_dec(self):
+ self.assertParse(self.grammar.func_dec,
+ "function Byte f() { f = 10; }",
+ ['function', 'Byte', 'f', ['f', '10']])
+ self.assertParse(self.grammar.func_dec,
+ "function Byte f(Byte x) { f = x+x; }",
+ ['function', 'Byte', 'f', ['Byte', 'x'],
+ ['f', ['x', '+', 'x']]])
+
+ self.assertNoParse(self.grammar.func_dec,
+ "function foo bar f() { f = 10; }")
+ self.assertNoParse(self.grammar.func_dec,
+ "function f();")
+ self.assertNoParse(self.grammar.func_dec,
+ """
+ function void f() {
+ // Uhh, inner functions?!
+ function void g() {
+ x = 1;
+ }
+ }
+ """)

if SFDLGrammar is None:
TestGrammar.skip = "Could not import SFDLGrammar, missing pyparsing?"

[Martin Geisler]

2 files changed, 109 insertions(+), 34 deletions(-)
viff/sfdl/grammar.py | 72 ++++++++++++++++++++++++++++++++++++++--
viff/test/sfdl/test_grammar.py | 71 +++++++++++++++++++++------------------


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518476 -3600
# Node ID 26aeb27a29aa51078f6e9487febfb0a0939e5111
# Parent bcc1d60786c59a8270aeb84fead22bec80267640
Parsing and evaluation of constant expressions.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -15,16 +15,43 @@
# You should have received a copy of the GNU Lesser General Public
# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.

+import operator
+from math import log, ceil
+
from pyparsing import Suppress, Word, Keyword, ZeroOrMore, Optional, Group, \
OneOrMore, Forward, delimitedList, \
oneOf, operatorPrecedence, opAssoc, \
- cppStyleComment, alphas, alphanums, nums
+ cppStyleComment, alphas, alphanums, nums, \
+ ParseException
+
+class attrdict(dict):
+
+ def __getattr__(self, attr):
+ try:
+ return self[attr]
+ except KeyError:
+ raise AttributeError("attrdict object has no attribute '%s'" % attr)
+
+ def __setattr__(self, attr, value):
+ if attr not in self and hasattr(self, attr):
+ raise AttributeError("cannot overwrite attribute '%s'" % attr)
+ self[attr] = value
+
+ def __delattr__(self, attr):
+ try:
+ del self[attr]
+ except KeyError:
+ raise AttributeError("attrdict object has no attribute '%s'" % attr)
+

class SFDLGrammar:

def __init__(self):
+ self.global_scope = {}
+
SCOLON = Suppress(";")
EQUAL = Suppress("=")
+ DOT = Suppress(".")
LCURLY, RCURLY = Suppress("{"), Suppress("}")
LPAREN, RPAREN = Suppress("("), Suppress(")")

@@ -33,7 +60,7 @@
const_op = oneOf(".bitSize .length")

self.const_atom = const_atom \
- = Word(nums) | ident + ZeroOrMore(~const_op + "." + ident)
+ = Word(nums) | ident + ZeroOrMore(~const_op + DOT + ident)
self.const_expr = const_expr \
= operatorPrecedence(const_atom,
[(const_op, 1, opAssoc.LEFT),
@@ -41,6 +68,10 @@
self.const_dec = const_dec \
= Keyword("const") + ident + EQUAL + const_expr + SCOLON

+ const_atom.setParseAction(self.parse_const_atom)
+ const_expr.setParseAction(self.parse_const_expr)
+ const_dec.setParseAction(self.parse_const_dec)
+

self.data_type = data_type = Forward()
self.struct_field = struct_field = Group(data_type + ident)
@@ -92,3 +123,40 @@
self.program = program = Keyword("program") + ident \
+ LCURLY + program_body + RCURLY
program.ignore(cppStyleComment)
+
+ def parse_const_atom(self, s, loc, toks):
+ atom = toks[0]
+ if atom.isdigit():
+ return int(atom)
+ else:
+ try:
+ result = self.global_scope[atom]
+ for atom in toks[1:]:
+ result = result[atom]
+ return result
+ except KeyError:
+ name = ".".join(toks)
+ raise ParseException(s, loc, "undefined constant: %s" % name)
+
+ def parse_const_dec(self, s, loc, toks):
+ self.global_scope[toks[1]] = toks[2]
+
+ def parse_const_expr(self, s, loc, toks):
+ if isinstance(toks[0], int):
+ return toks[0]
+ else:
+ result = toks[0][0]
+ op = operator.add
+ for sym in toks[0][1:]:
+ if sym == "+":
+ op = operator.add
+ elif sym == "-":
+ op = operator.sub
+ elif sym == ".bitSize":
+ # TODO: Fix for negative values and 2^n values.
+ result = int(ceil(log(result, 2))+1)
+ elif sym == ".length":
+ result = result.length
+ else:
+ result = op(result, sym)
+ return result
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -19,7 +19,7 @@

try:
from pyparsing import ParseException
- from viff.sfdl.grammar import SFDLGrammar
+ from viff.sfdl.grammar import SFDLGrammar, attrdict
except ImportError:
SFDLGrammar = None

@@ -66,47 +66,49 @@
['program', 'empty'])

def test_const_atom(self):
- self.assertParse(self.grammar.const_atom, "123", ['123'])
- self.assertParse(self.grammar.const_atom, "foo", ['foo'])
+ self.assertParse(self.grammar.const_atom, "123", [123])
+ self.grammar.global_scope["foo"] = 10
+ self.assertParse(self.grammar.const_atom, "foo", [10])

self.assertNoParse(self.grammar.const_atom, "x.10")
self.assertNoParse(self.grammar.const_atom, "10.x")

def test_const_expr(self):
- self.assertParse(self.grammar.const_expr, "1 + 2", [['1', '+', '2']])
- self.assertParse(self.grammar.const_expr, "1 + x", [['1', '+', 'x']])
- self.assertParse(self.grammar.const_expr, "10 + (x - 20)",
- [['10', '+', ['x', '-', '20']]])
+ self.assertParse(self.grammar.const_expr, "1 + 2", [3])
+ self.grammar.global_scope['x'] = 17
+ self.assertParse(self.grammar.const_expr, "1 + x", [18])
+ self.assertParse(self.grammar.const_expr, "10 + (x - 20)", [7])

self.assertNoParse(self.grammar.const_expr, "10 +")
self.assertNoParse(self.grammar.const_expr, "x y")

def test_const_expr_bitsize(self):
+ # TODO: Test negative numbers, check corner cases.
+
# Bit size of an integer:
- self.assertParse(self.grammar.const_expr, "32.bitSize",
- [['32', '.bitSize']])
- # Bit size of a declared variable:
- self.assertParse(self.grammar.const_expr, "x.bitSize",
- [['x', '.bitSize']])
+ self.assertParse(self.grammar.const_expr, "20.bitSize", [6])
+ # Bit size of a declared constant:
+ self.grammar.global_scope['x'] = 15
+ self.assertParse(self.grammar.const_expr, "x.bitSize", [5])
# Bit size of a compound expression:
- self.assertParse(self.grammar.const_expr, "(10 + x).bitSize",
- [[['10', '+', 'x'], '.bitSize']])
+ self.assertParse(self.grammar.const_expr, "(10 + x).bitSize", [6])

self.assertNoParse(self.grammar.const_expr, ".bitSize")

def test_const_expr_length(self):
+ # Length of an array:
+ self.grammar.global_scope['n'] = attrdict(length=10)
+ self.assertParse(self.grammar.const_expr, "n.length", [10])
+
# Length of an array in a struct:
- self.assertParse(self.grammar.const_expr, "n.length",
- [['n', '.length']])
-
- self.assertParse(self.grammar.const_expr, "x.y.length",
- [['x', '.', 'y', '.length']])
+ self.grammar.global_scope['x'] = attrdict(y=attrdict(length=2))
+ self.assertParse(self.grammar.const_expr, "x.y.length", [2])

def test_const_dec(self):
self.assertParse(self.grammar.const_dec, "const x = 10;",
- ['const', 'x', '10'])
- self.assertParse(self.grammar.const_dec, "const x = 10 + y;",
- ['const', 'x', ['10', '+', 'y']])
+ ['const', 'x', 10])
+ self.assertParse(self.grammar.const_dec, "const y = 10 + x;",
+ ['const', 'y', 20])

self.assertNoParse(self.grammar.const_dec, "const x;")
self.assertNoParse(self.grammar.const_dec, "const x 123;")
@@ -117,11 +119,13 @@

def test_int_type(self):
self.assertParse(self.grammar.known_type, "Int<8>",
- ['Int', '<', '8', '>'])
+ ['Int', '<', 8, '>'])
+
+ self.grammar.global_scope['MAX'] = 10
self.assertParse(self.grammar.known_type, "Int<MAX>",
- ['Int', '<', 'MAX', '>'])
+ ['Int', '<', 10, '>'])
self.assertParse(self.grammar.known_type, "Int<MAX+1>",
- ['Int', '<', ['MAX', '+', '1'], '>'])
+ ['Int', '<', 11, '>'])

def test_struct_type(self):
self.assertParse(self.grammar.struct_type, "struct { Boolean x }",
@@ -143,15 +147,17 @@

def test_data_type(self):
self.assertParse(self.grammar.data_type, "Boolean[4]",
- ['Boolean', ['[', '4', ']']])
+ ['Boolean', ['[', 4, ']']])
+ self.grammar.global_scope['MIN'] = 17
+ self.grammar.global_scope['MAX'] = 4
self.assertParse(self.grammar.data_type, "Int<MAX>[MIN]",
- ['Int', '<', 'MAX', '>', ['[', 'MIN', ']']])
+ ['Int', '<', 4, '>', ['[', 17, ']']])

def test_type_dec(self):
self.assertParse(self.grammar.type_dec, "type x = Boolean;",
['type', 'x', 'Boolean'])
self.assertParse(self.grammar.type_dec, "type x = AnotherType[4];",
- ['type', 'x', 'AnotherType', ['[', '4', ']']])
+ ['type', 'x', 'AnotherType', ['[', 4, ']']])


def test_qual_ident(self):
@@ -278,7 +284,7 @@
def test_for_stm(self):
self.assertParse(self.grammar.for_stm,
"for (i = 0 to 10) { x[i] = 42; }",
- ['for', ['i', '0'], 'to', ['10'],
+ ['for', ['i', 0], 'to', [10],
[['x', '[', 'i', ']', '42']]])

src = """
@@ -287,8 +293,9 @@
y[i] = b[i] && z[i];
}
"""
+ self.grammar.global_scope['MIN'] = 7
self.assertParse(self.grammar.for_stm, src,
- ['for', ['i', 'MIN'], 'to', [['MIN', '+', '10']],
+ ['for', ['i', 7], 'to', [17],
[['b', '[', 'i', ']',
['x', '[', 'i', ']',
'<',
@@ -350,7 +357,7 @@
"""
self.assertParse(self.grammar.program, src,
['program', 'p',
- ['type', 'Byte', 'Int', '<', '8', '>']])
+ ['type', 'Byte', 'Int', '<', 8, '>']])

src = """
program p {
@@ -358,7 +365,7 @@
}
"""
self.assertParse(self.grammar.program, src,
- ['program', 'p', ['const', 'x', '10']])
+ ['program', 'p', ['const', 'x', 10]])

src = """
program p {

[Martin Geisler]

1 file changed, 25 insertions(+)
viff/test/sfdl/test_grammar.py | 25 +++++++++++++++++++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518457 -3600
# Node ID 6afba4921987626a0211d1861aecccce808c7b02
# Parent c2211d5ab86f58e451cb23f1a5b47068319b9d08
Test parsing of comments.

diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -40,5 +40,30 @@
['program', 'empty'])
self.assertNoParse(self.grammar.program, "program {}")

+ def test_comment(self):
+ src = """
+ program empty {
+ // a C-style comment
+ }
+ """
+ self.assertParse(self.grammar.program, src,
+ ['program', 'empty'])
+
+ src = """
+ program empty {
+ // a C++-style comment
+ }
+ """
+ self.assertParse(self.grammar.program, src,
+ ['program', 'empty'])
+
+ src = """
+ program /* sneaky // comment */ empty {
+ /****/ // /****/
+ }
+ """
+ self.assertParse(self.grammar.program, src,
+ ['program', 'empty'])
+
if SFDLGrammar is None:
TestGrammar.skip = "Could not import SFDLGrammar, missing pyparsing?"

[Martin Geisler]

2 files changed, 32 insertions(+), 19 deletions(-)
viff/sfdl/grammar.py | 16 ++++++++++++++--
viff/test/sfdl/test_grammar.py | 35 ++++++++++++++++++-----------------


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1228899835 -3600
# Node ID 9dccd3a382898ec0e2d817eee18ba2deeb3c1d20
# Parent 01b0e928dcbeea1b22329f4356840f3e49fefe30
Restructure struct and parse defined types.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -77,17 +77,20 @@
self.data_type = data_type = Forward()
self.struct_field = struct_field = Group(data_type + ident)
self.struct_type = struct_type = Keyword("struct") \
- + "{" + delimitedList(struct_field) + "}"
+ + LCURLY + Group(delimitedList(struct_field)) + RCURLY
self.int_type = int_type = Keyword("Int") + "<" + const_expr + ">"
self.known_type = known_type \
= int_type | Keyword("Boolean") | struct_type | Keyword("void")
- data_type << (known_type | ident) \
+ self.defined_type = defined_type = ident.copy()
+ data_type << (known_type | defined_type) \
+ Optional(LBRACK + const_expr + RBRACK)

self.type_dec = type_dec \
= Keyword("type") + ident + EQUAL + data_type + SCOLON

int_type.setParseAction(self.parse_int_type)
+ struct_type.setParseAction(self.parse_struct_type)
+ defined_type.setParseAction(self.parse_defined_type)
data_type.setParseAction(self.parse_data_type)
type_dec.setParseAction(self.parse_type_dec)

@@ -168,6 +171,15 @@
def parse_int_type(self, s, loc, toks):
return attrdict(bitsize=toks[2])

+ def parse_struct_type(self, s, loc, toks):
+ return attrdict([(b, a) for (a, b) in toks[1]])
+
+ def parse_defined_type(self, s, loc, toks):
+ try:
+ return self.global_scope[toks[0]]
+ except KeyError:
+ raise ParseException(s, loc, "undefined type: %s" % toks[0])
+
def parse_data_type(self, s, loc, toks):
if len(toks) == 2:
return attrdict(length=toks[1])
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -128,22 +128,18 @@
[attrdict(bitsize=11)])

def test_struct_type(self):
- self.assertParse(self.grammar.struct_type, "struct { Boolean x }",
- ['struct', '{', ['Boolean', 'x'], '}'])
+ self.assertParse(self.grammar.struct_type, "struct { Int<8> x }",
+ [attrdict(x=attrdict(bitsize=8))])
+ self.grammar.global_scope['int'] = attrdict(bitsize=8)
+ self.assertParse(self.grammar.struct_type, "struct { int x }",
+ [attrdict(x=attrdict(bitsize=8))])
+
self.assertParse(self.grammar.struct_type,
"struct { Boolean x, Boolean y }",
- ['struct', '{',
- ['Boolean', 'x'],
- ['Boolean', 'y'],
- '}'])
+ [attrdict(x='Boolean', y='Boolean')])
self.assertParse(self.grammar.struct_type,
"struct { struct { Boolean x } y }",
- ['struct', '{',
- ['struct',
- '{',
- ['Boolean', 'x'],
- '}', 'y'],
- '}'])
+ [attrdict(y=attrdict(x='Boolean'))])

def test_data_type(self):
self.assertParse(self.grammar.data_type, "Boolean[4]",
@@ -156,6 +152,7 @@
def test_type_dec(self):
self.assertParse(self.grammar.type_dec, "type x = Boolean;",
['type', 'x', 'Boolean'])
+ self.grammar.global_scope["AnotherType"] = attrdict(bitsize=8)
self.assertParse(self.grammar.type_dec, "type xs = AnotherType[4];",
['type', 'xs', attrdict(length=4)])
self.assertParse(self.grammar.const_expr, "xs.length", [4])
@@ -309,17 +306,19 @@
def test_func_var_dec(self):
self.assertParse(self.grammar.func_var_dec, "var Boolean x;",
['var', 'Boolean', ['x']])
+ self.grammar.global_scope["Byte"] = attrdict(bitsize=8)
self.assertParse(self.grammar.func_var_dec, "var Byte a, b, c;",
- ['var', 'Byte', ['a', 'b', 'c']])
+ ['var', attrdict(bitsize=8), ['a', 'b', 'c']])
self.assertNoParse(self.grammar.func_var_dec, "var x;")

def test_func_body(self):
+ self.grammar.global_scope["Byte"] = attrdict(bitsize=8)
self.assertParse(self.grammar.func_body, "x = 1;", [['x', '1']])
self.assertParse(self.grammar.func_body, "var Byte x; x = 1;",
- [['var', 'Byte', ['x']], ['x', '1']])
+ [['var', attrdict(bitsize=8), ['x']], ['x', '1']])
self.assertParse(self.grammar.func_body,
"var Byte x; var Boolean y; x = 1;",
- [['var', 'Byte', ['x']],
+ [['var', attrdict(bitsize=8), ['x']],
['var', 'Boolean', ['y']],
['x', '1']])

@@ -328,12 +327,14 @@
self.assertNoParse(self.grammar.func_body, "var Byte x;")

def test_func_dec(self):
+ self.grammar.global_scope["Byte"] = attrdict(bitsize=8)
self.assertParse(self.grammar.func_dec,
"function Byte f() { f = 10; }",
- ['function', 'Byte', 'f', ['f', '10']])
+ ['function', attrdict(bitsize=8), 'f', ['f', '10']])
self.assertParse(self.grammar.func_dec,
"function Byte f(Byte x) { f = x+x; }",
- ['function', 'Byte', 'f', ['Byte', 'x'],
+ ['function', attrdict(bitsize=8), 'f',
+ [attrdict(bitsize=8), 'x'],
['f', ['x', '+', 'x']]])

self.assertNoParse(self.grammar.func_dec,

[Martin Geisler]

2 files changed, 12 insertions(+), 4 deletions(-)
viff/sfdl/grammar.py | 10 +++++++++-
viff/test/sfdl/test_grammar.py | 6 +++---


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518476 -3600
# Node ID fa87aafa06f27b55019438b4fda77b7a976be5ca
# Parent afb975f68296d2d278c1dbe449a4d61fc0e2fa5a
imported patch array-types

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -54,6 +54,7 @@
DOT = Suppress(".")
LCURLY, RCURLY = Suppress("{"), Suppress("}")
LPAREN, RPAREN = Suppress("("), Suppress(")")
+ LBRACK, RBRACK = Suppress("["), Suppress("]")

self.ident = ident = Word(alphas + "_", alphanums + "_")

@@ -81,12 +82,13 @@
self.known_type = known_type \
= int_type | Keyword("Boolean") | struct_type | Keyword("void")
data_type << (known_type | ident) \
- + ZeroOrMore(Group('[' + const_expr + ']'))
+ + ZeroOrMore(LBRACK + const_expr + RBRACK)

self.type_dec = type_dec \
= Keyword("type") + ident + EQUAL + data_type + SCOLON

int_type.setParseAction(self.parse_int_type)
+ data_type.setParseAction(self.parse_data_type)

self.expr = expr = Forward()
self.qual_ident = qual_ident = ident \
@@ -164,3 +166,9 @@

def parse_int_type(self, s, loc, toks):
return attrdict(bitsize=toks[2])
+
+ def parse_data_type(self, s, loc, toks):
+ if len(toks) == 2:
+ return attrdict(length=toks[1])
+ else:
+ return toks
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -147,17 +147,17 @@

def test_data_type(self):
self.assertParse(self.grammar.data_type, "Boolean[4]",
- ['Boolean', ['[', 4, ']']])
+ [attrdict(length=4)])
self.grammar.global_scope['MIN'] = 17
self.grammar.global_scope['MAX'] = 4
self.assertParse(self.grammar.data_type, "Int<MAX>[MIN]",
- [attrdict(bitsize=4), ['[', 17, ']']])
+ [attrdict(length=17)])

def test_type_dec(self):
self.assertParse(self.grammar.type_dec, "type x = Boolean;",
['type', 'x', 'Boolean'])
self.assertParse(self.grammar.type_dec, "type x = AnotherType[4];",
- ['type', 'x', 'AnotherType', ['[', 4, ']']])
+ ['type', 'x', attrdict(length=4)])


def test_qual_ident(self):

[Martin Geisler]

2 files changed, 43 insertions(+), 2 deletions(-)
viff/sfdl/grammar.py | 17 +++++++++++++++--
viff/test/sfdl/test_grammar.py | 28 ++++++++++++++++++++++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518457 -3600
# Node ID d7a1eac0ed9675650ef09894e672cffcd554cc49
# Parent be095927c9e007ef56652a475f524eea32c0515a
Parsing of expressions.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -15,8 +15,8 @@
# You should have received a copy of the GNU Lesser General Public
# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.

-from pyparsing import Suppress, Word, Keyword, ZeroOrMore, \
- delimitedList, \
+from pyparsing import Suppress, Word, Keyword, ZeroOrMore, Optional, Group, \
+ Forward, delimitedList, \
oneOf, operatorPrecedence, opAssoc, \
cppStyleComment, alphas, alphanums, nums

@@ -26,6 +26,7 @@
SCOLON = Suppress(";")
EQUAL = Suppress("=")
LCURLY, RCURLY = Suppress("{"), Suppress("}")
+ LPAREN, RPAREN = Suppress("("), Suppress(")")

self.ident = ident = Word(alphas + "_", alphanums + "_")

@@ -36,6 +37,18 @@
self.const_dec = const_dec \
= Keyword("const") + ident + EQUAL + const_expr + SCOLON

+ self.expr = expr = Forward()
+ self.qual_ident = qual_ident = ident \
+ + ZeroOrMore(("[" + expr + "]") | ("." + ident))
+ self.func_call = func_call \
+ = Group(ident + LPAREN + Optional(delimitedList(expr)) + RPAREN)
+ expr << operatorPrecedence(Word(nums) | func_call | qual_ident,
+ [(oneOf("* /"), 2, opAssoc.LEFT),
+ (oneOf("+ -"), 2, opAssoc.LEFT),
+ (oneOf("< > <= >="), 2, opAssoc.LEFT),
+ (oneOf("== !="), 2, opAssoc.LEFT),
+ (oneOf("&& || ! ^"), 2, opAssoc.LEFT)])
+
self.program = program = Keyword("program") + ident \
+ LCURLY + RCURLY
program.ignore(cppStyleComment)
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -92,5 +92,33 @@
self.assertNoParse(self.grammar.const_dec, "const x;")
self.assertNoParse(self.grammar.const_dec, "const x 123;")

+ def test_qual_ident(self):
+ self.assertParse(self.grammar.qual_ident, "x.y", ['x', '.', 'y'])
+ self.assertParse(self.grammar.qual_ident, "x[10]",
+ ['x', '[', '10', ']'])
+ self.assertParse(self.grammar.qual_ident, "x[y+1].foo",
+ ['x', '[', ['y', '+', '1'], ']', '.', 'foo'])
+
+ def test_func_call(self):
+ self.assertParse(self.grammar.func_call, "foo()", [['foo']])
+ self.assertParse(self.grammar.func_call, "foo(10)", [['foo', '10']])
+ self.assertParse(self.grammar.func_call, "foo(10+x)",
+ [['foo', ['10', '+', 'x']]])
+
+ def test_expr_atom(self):
+ self.assertParse(self.grammar.expr, "123", ['123'])
+ self.assertParse(self.grammar.expr, "foo", ['foo'])
+
+ def test_expr(self):
+ self.assertParse(self.grammar.expr, "1 + 2 * 3 / 4",
+ [['1', '+', ['2', '*', '3', '/', '4']]])
+ self.assertParse(self.grammar.expr, "123 + f(10) < g(x.y) * h(z[1])",
+ [[['123', '+', ['f', '10']],
+ '<',
+ [['g', 'x', '.', 'y'],
+ '*',
+ ['h', 'z', '[', '1', ']']]
+ ]])
+
if SFDLGrammar is None:
TestGrammar.skip = "Could not import SFDLGrammar, missing pyparsing?"

[Martin Geisler]

2 files changed, 60 insertions(+)
viff/test/sfdl/__init__.py | 16 ++++++++++++++
viff/test/sfdl/test_grammar.py | 44 ++++++++++++++++++++++++++++++++++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518456 -3600
# Node ID c2211d5ab86f58e451cb23f1a5b47068319b9d08
# Parent 14a1378185796f4db0fdafe46ee4c774017eb49e
Test parsing empty programs.

diff --git a/viff/test/sfdl/__init__.py b/viff/test/sfdl/__init__.py
new file mode 100644
--- /dev/null
+++ b/viff/test/sfdl/__init__.py
@@ -0,0 +1,16 @@
+# Copyright 2008 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
new file mode 100644
--- /dev/null
+++ b/viff/test/sfdl/test_grammar.py
@@ -0,0 +1,44 @@
+# Copyright 2008 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+from twisted.trial.unittest import TestCase
+
+try:
+ from pyparsing import ParseException
+ from viff.sfdl.grammar import SFDLGrammar
+except ImportError:
+ SFDLGrammar = None
+
+class TestGrammar(TestCase):
+
+ def assertParse(self, parser, src, expected):
+ result = parser.parseString(src)
+ self.assertEquals(result.asList(), expected)
+
+ def assertNoParse(self, parser, src):
+ self.assertRaises(ParseException, parser.parseString, src)
+
+ def setUp(self):
+ self.grammar = SFDLGrammar()
+
+ def test_empty(self):
+ self.assertParse(self.grammar.program, "program empty {}",
+ ['program', 'empty'])
+ self.assertNoParse(self.grammar.program, "program {}")
+
+if SFDLGrammar is None:
+ TestGrammar.skip = "Could not import SFDLGrammar, missing pyparsing?"

[Martin Geisler]

2 files changed, 55 insertions(+), 1 deletion(-)
viff/sfdl/grammar.py | 5 +++
viff/test/sfdl/test_grammar.py | 51 ++++++++++++++++++++++++++++++++++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518476 -3600
# Node ID d94925dfcd0f2ff83dc0cbf4efe7e9455fef6fd5
# Parent f10262f030b9a3c42f031b61f82b8da5dcbc5286
Parsing of full programs, with tests.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -82,6 +82,9 @@
+ LPAREN + Optional(delimitedList(Group(func_arg))) + RPAREN \
+ LCURLY + func_body + RCURLY

+ self.program_body = program_body \
+ = ZeroOrMore(Group(type_dec | const_dec)) \
+ + ZeroOrMore(Group(func_dec))
self.program = program = Keyword("program") + ident \
- + LCURLY + RCURLY
+ + LCURLY + program_body + RCURLY
program.ignore(cppStyleComment)
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -323,5 +323,56 @@
}
""")

+ def test_program(self):
+ src = """
+ program p {
+ type Byte = Int<8>;
+ }
+ """
+ self.assertParse(self.grammar.program, src,
+ ['program', 'p',
+ ['type', 'Byte', 'Int', '<', '8', '>']])
+
+ src = """
+ program p {
+ const x = 10;
+ }
+ """
+ self.assertParse(self.grammar.program, src,
+ ['program', 'p', ['const', 'x', '10']])
+
+ src = """
+ program p {
+ function Boolean f() {
+ f = true;
+ }
+ }
+ """
+ self.assertParse(self.grammar.program, src,
+ ['program', 'p',
+ ['function', 'Boolean', 'f',
+ ['f', 'true']]])
+
+ src = """
+ program p {
+ function Boolean f() {
+ f = true;
+ }
+ const trailing_const = 1;
+ }
+ """
+ self.assertNoParse(self.grammar.program, src)
+
+ src = """
+ program p {
+ function Boolean f() {
+ f = true;
+ }
+ type trailing_type = Int<32>;
+ }
+ """
+ self.assertNoParse(self.grammar.program, src)
+
+
if SFDLGrammar is None:
TestGrammar.skip = "Could not import SFDLGrammar, missing pyparsing?"

[Martin Geisler]

1 file changed, 9 insertions(+)
viff/test/sfdl/test_grammar.py | 9 +++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518457 -3600
# Node ID be095927c9e007ef56652a475f524eea32c0515a
# Parent 293f2a5d6e7ef7d95e8f453d78e95651e3379633
Tests for malformed program fragments.

diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -71,17 +71,26 @@
self.assertParse(self.grammar.const_atom, "x.y", ['x', 'y'])
self.assertParse(self.grammar.const_atom, "x.y.z", ['x', 'y', 'z'])

+ self.assertNoParse(self.grammar.const_atom, "x.10")
+ self.assertNoParse(self.grammar.const_atom, "10.x")
+
def test_const_expr(self):
self.assertParse(self.grammar.const_expr, "1 + 2", [['1', '+', '2']])
self.assertParse(self.grammar.const_expr, "1 + x", [['1', '+', 'x']])
self.assertParse(self.grammar.const_expr, "10 + (x - 20)",
[['10', '+', ['x', '-', '20']]])

+ self.assertNoParse(self.grammar.const_expr, "10 +")
+ self.assertNoParse(self.grammar.const_expr, "x y")
+
def test_const_dec(self):
self.assertParse(self.grammar.const_dec, "const x = 10;",
['const', 'x', '10'])
self.assertParse(self.grammar.const_dec, "const x = 10 + y;",
['const', 'x', ['10', '+', 'y']])

+ self.assertNoParse(self.grammar.const_dec, "const x;")
+ self.assertNoParse(self.grammar.const_dec, "const x 123;")
+
if SFDLGrammar is None:
TestGrammar.skip = "Could not import SFDLGrammar, missing pyparsing?"

[Martin Geisler]

2 files changed, 9 insertions(+)
viff/sfdl/grammar.py | 3 +++
viff/test/sfdl/test_grammar.py | 6 ++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518457 -3600
# Node ID bc1b37d69c6193ea1b657675ec20a1c48dd168fa
# Parent 0763eaf0c1dd39d41795810bfeb29329c674cfff
Type declarations.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -48,6 +48,9 @@
data_type << (known_type | ident) \
+ ZeroOrMore(Group('[' + const_expr + ']'))

+ self.type_dec = type_dec \
+ = Keyword("type") + ident + EQUAL + data_type + SCOLON
+

self.expr = expr = Forward()
self.qual_ident = qual_ident = ident \
diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -128,6 +128,12 @@
self.assertParse(self.grammar.data_type, "Int<MAX>[MIN]",
['Int', '<', 'MAX', '>', ['[', 'MIN', ']']])

+ def test_type_dec(self):
+ self.assertParse(self.grammar.type_dec, "type x = Boolean;",
+ ['type', 'x', 'Boolean'])
+ self.assertParse(self.grammar.type_dec, "type x = AnotherType[4];",
+ ['type', 'x', 'AnotherType', ['[', '4', ']']])
+

def test_qual_ident(self):
self.assertParse(self.grammar.qual_ident, "x.y", ['x', '.', 'y'])

[Martin Geisler]

1 file changed, 1 insertion(+), 1 deletion(-)
viff/sfdl/grammar.py | 2 +-


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518476 -3600
# Node ID ad84b1d50412b49b96041aae42210635723d89bc
# Parent fa87aafa06f27b55019438b4fda77b7a976be5ca
Restrict arrays to a single dimension.

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -82,7 +82,7 @@
self.known_type = known_type \
= int_type | Keyword("Boolean") | struct_type | Keyword("void")
data_type << (known_type | ident) \
- + ZeroOrMore(LBRACK + const_expr + RBRACK)
+ + Optional(LBRACK + const_expr + RBRACK)

self.type_dec = type_dec \
= Keyword("type") + ident + EQUAL + data_type + SCOLON

[Martin Geisler]

2 files changed, 27 insertions(+), 4 deletions(-)
viff/sfdl/grammar.py | 8 ++++++--
viff/test/sfdl/test_grammar.py | 23 +++++++++++++++++++++--


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518476 -3600
# Node ID bcc1d60786c59a8270aeb84fead22bec80267640
# Parent ca37920c34868b17549b5bcf0fa17bbf07f05ebb
imported patch const-type-refactor

diff --git a/viff/sfdl/grammar.py b/viff/sfdl/grammar.py
--- a/viff/sfdl/grammar.py
+++ b/viff/sfdl/grammar.py
@@ -30,10 +30,14 @@

self.ident = ident = Word(alphas + "_", alphanums + "_")

+ const_op = oneOf(".bitSize .length")
+
self.const_atom = const_atom \
- = Word(nums) | delimitedList(ident, '.')
+ = Word(nums) | ident + ZeroOrMore(~const_op + "." + ident)
self.const_expr = const_expr \
- = operatorPrecedence(const_atom, [(oneOf("+ -"), 2, opAssoc.LEFT)])
+ = operatorPrecedence(const_atom,
+ [(const_op, 1, opAssoc.LEFT),
+ (oneOf("+ -"), 2, opAssoc.LEFT)])
self.const_dec = const_dec \
= Keyword("const") + ident + EQUAL + const_expr + SCOLON

diff --git a/viff/test/sfdl/test_grammar.py b/viff/test/sfdl/test_grammar.py
--- a/viff/test/sfdl/test_grammar.py
+++ b/viff/test/sfdl/test_grammar.py
@@ -68,8 +68,6 @@
def test_const_atom(self):
self.assertParse(self.grammar.const_atom, "123", ['123'])
self.assertParse(self.grammar.const_atom, "foo", ['foo'])
- self.assertParse(self.grammar.const_atom, "x.y", ['x', 'y'])
- self.assertParse(self.grammar.const_atom, "x.y.z", ['x', 'y', 'z'])

self.assertNoParse(self.grammar.const_atom, "x.10")
self.assertNoParse(self.grammar.const_atom, "10.x")
@@ -83,6 +81,27 @@
self.assertNoParse(self.grammar.const_expr, "10 +")
self.assertNoParse(self.grammar.const_expr, "x y")

+ def test_const_expr_bitsize(self):
+ # Bit size of an integer:
+ self.assertParse(self.grammar.const_expr, "32.bitSize",
+ [['32', '.bitSize']])
+ # Bit size of a declared variable:
+ self.assertParse(self.grammar.const_expr, "x.bitSize",
+ [['x', '.bitSize']])
+ # Bit size of a compound expression:
+ self.assertParse(self.grammar.const_expr, "(10 + x).bitSize",
+ [[['10', '+', 'x'], '.bitSize']])
+
+ self.assertNoParse(self.grammar.const_expr, ".bitSize")
+
+ def test_const_expr_length(self):
+ # Length of an array in a struct:
+ self.assertParse(self.grammar.const_expr, "n.length",
+ [['n', '.length']])
+
+ self.assertParse(self.grammar.const_expr, "x.y.length",
+ [['x', '.', 'y', '.length']])
+
def test_const_dec(self):
self.assertParse(self.grammar.const_dec, "const x = 10;",
['const', 'x', '10'])

[Martin Geisler]

6 files changed, 179 insertions(+)
viff/test/sfdl/and.sfdl | 18 ++++++++++++
viff/test/sfdl/billionaires.sfdl | 19 +++++++++++++
viff/test/sfdl/kds.sfdl | 21 ++++++++++++++
viff/test/sfdl/median.sfdl | 48 +++++++++++++++++++++++++++++++++
viff/test/sfdl/millionaires.sfdl | 19 +++++++++++++
viff/test/sfdl/test_examples.py | 54 ++++++++++++++++++++++++++++++++++++++


# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1227518476 -3600
# Node ID 4c16d331284ddcdffcc690c1703c769a16fa7519
# Parent d94925dfcd0f2ff83dc0cbf4efe7e9455fef6fd5
Test parsing of SFDL example programs.
The examples are downloaded from the FairPlay project:

http://www.cs.huji.ac.il/project/Fairplay/fairplay.html

The millionaires.sfdl file (original name was Millionaires.txt) has
been edited slightly by replacing "&" with "&&" since "&" is not a
valid operator in SFDL 2.0 (the syntax changed from SFDL 1.0).

diff --git a/viff/test/sfdl/and.sfdl b/viff/test/sfdl/and.sfdl
new file mode 100644
--- /dev/null
+++ b/viff/test/sfdl/and.sfdl
@@ -0,0 +1,18 @@
+/*
+ * Compute AND of two byte
+ */
+program And {
+ const N=8;
+ type Byte = Int<N>;
+ type AliceInput = Byte;
+ type BobInput = Byte;
+ type AliceOutput = Byte;
+ type BobOutput = Byte;
+ type Input = struct {AliceInput alice, BobInput bob};
+ type Output = struct {AliceOutput alice, BobOutput bob};
+
+ function Output output(Input input) {
+ output.alice = (input.bob && input.alice);
+ output.bob = (input.bob && input.alice);
+ }
+}
diff --git a/viff/test/sfdl/billionaires.sfdl b/viff/test/sfdl/billionaires.sfdl
new file mode 100644
--- /dev/null
+++ b/viff/test/sfdl/billionaires.sfdl
@@ -0,0 +1,19 @@
+/*
+ * Check which of two Billionaires is richer
+ */
+program Billionaires {
+ type int = Int<32>; // 32-bit integer
+ type AliceInput = int;
+ type BobInput = int;
+ type AliceOutput = Boolean;
+ type BobOutput = Boolean;
+ type Output = struct {AliceOutput alice,
+ BobOutput bob};
+ type Input = struct {AliceInput alice,
+ BobInput bob};
+
+ function Output output(Input input) {
+ output.alice = (input.alice > input.bob);
+ output.bob = (input.bob > input.alice);
+ }
+}
diff --git a/viff/test/sfdl/kds.sfdl b/viff/test/sfdl/kds.sfdl
new file mode 100644
--- /dev/null
+++ b/viff/test/sfdl/kds.sfdl
@@ -0,0 +1,21 @@
+/*
+ * Alice accesses an entry in Bob's keyed-DB
+ */
+program Keyed_DB_Search {
+ const DBsize = 16;
+ type Key = Int<6>;
+ type Data = Int<24>;
+ type Pair = struct {Key key, Data data};
+ type AliceInput = Key;
+ type BobInput = Pair[DBsize];
+ type AliceOutput = Data;
+ type Output = struct {AliceOutput alice};
+ type Input = struct {AliceInput alice, BobInput bob};
+
+ function Output output(Input input) {
+ var Key i ;
+ for (i = 0 to DBsize-1)
+ if (input.alice == input.bob[i].key)
+ output.alice = input.bob[i].data;
+ }
+}
diff --git a/viff/test/sfdl/median.sfdl b/viff/test/sfdl/median.sfdl
new file mode 100644
--- /dev/null
+++ b/viff/test/sfdl/median.sfdl
@@ -0,0 +1,48 @@
+/*
+ * Compute the Median of two sorted arrays
+ */
+program Median {
+
+// Constants
+
+const inp_size = 10;
+
+// Type Definitions
+
+type Elem = Int<16>;
+type AliceInput = Elem[inp_size];
+type AliceOutput = Int<16>;
+type BobInput = Elem[inp_size];
+type BobOutput = Int<16>;
+type Input = struct {AliceInput alice, BobInput bob};
+type Output = struct {AliceOutput alice, BobOutput bob};
+
+// Function Definitions
+
+// This is the main function
+function Output output(Input input) {
+
+ var Int<8> i;
+ var Int<8> ai;
+ var Int<8> bi;
+
+ ai=0;
+ bi=0;
+
+ for (i = 1 to inp_size-1) {
+ if (input.alice[ai] >= input.bob[bi])
+ bi = bi + 1;
+ else
+ ai = ai + 1;
+ }
+
+ if (input.alice[ai] < input.bob[bi]) {
+ output.alice = input.alice[ai];
+ output.bob= input.alice[ai];
+ } else {
+ output.alice = input.bob[bi];
+ output.bob = input.bob[bi];
+ }
+}
+
+}
diff --git a/viff/test/sfdl/millionaires.sfdl b/viff/test/sfdl/millionaires.sfdl
new file mode 100644
--- /dev/null
+++ b/viff/test/sfdl/millionaires.sfdl
@@ -0,0 +1,19 @@
+/*
+ * Check which of two Millionaires is richer
+ */
+program Millionaires {
+ type int = Int<4>; // 4-bit integer
+ type AliceInput = int;
+ type BobInput = int;
+ type AliceOutput = Boolean;
+ type BobOutput = Boolean;
+ type Output = struct {AliceOutput alice,
+ BobOutput bob};
+ type Input = struct {AliceInput alice,
+ BobInput bob};
+
+ function Output output(Input input) {
+ output.alice = (input.alice > input.bob);
+ output.bob = (input.bob > input.alice);
+ }
+}
diff --git a/viff/test/sfdl/test_examples.py b/viff/test/sfdl/test_examples.py
new file mode 100644
--- /dev/null
+++ b/viff/test/sfdl/test_examples.py
@@ -0,0 +1,54 @@
+# Copyright 2008 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+import os
+from twisted.trial.unittest import TestCase
+
+try:
+ from pyparsing import ParseException, ParseFatalException
+ from viff.sfdl.grammar import SFDLGrammar
+except ImportError:
+ SFDLGrammar = None
+
+class ParsingMixin:
+ def assertParse(self, path):
+ fullpath = os.path.join(os.path.dirname(__file__), path)
+ g = SFDLGrammar()
+ result = g.program.parseFile(fullpath)
+ # Check that we got at least something.
+ self.assertNotEquals(result.asList(), [])
+
+class TestParsing(TestCase, ParsingMixin):
+
+ def test_and(self):
+ self.assertParse("and.sfdl")
+
+ def test_millionaires(self):
+ self.assertParse("millionaires.sfdl")
+
+ def test_billionaires(self):
+ self.assertParse("billionaires.sfdl")
+
+ def test_kds(self):
+ self.assertParse("kds.sfdl")
+
+ def test_median(self):
+ self.assertParse("median.sfdl")
+
+
+if SFDLGrammar is None:
+ TestParsing.skip = "Could not import SFDLGrammar, missing pyparsing?"