From 1c48ba9f3483505f53962731dc58c6c02d785fc4 Mon Sep 17 00:00:00 2001 From: Vivien Maisonneuve Date: Thu, 26 Jun 2014 11:57:59 +0200 Subject: [PATCH] Replace Polyhedron.fromstring() by Domain.fromstring() --- pypol/domains.py | 64 +++++++++++++++++++++++++++++++++++++++++++++- pypol/polyhedra.py | 52 +++---------------------------------- 2 files changed, 67 insertions(+), 49 deletions(-) diff --git a/pypol/domains.py b/pypol/domains.py index a34b75b..20493fa 100644 --- a/pypol/domains.py +++ b/pypol/domains.py @@ -1,8 +1,11 @@ +import ast import functools +import re from . import islhelper from .islhelper import mainctx, libisl, isl_set_basic_sets +from .linexprs import Expression __all__ = [ @@ -242,9 +245,68 @@ class Domain: islset1 = libisl.isl_set_union(islset1, islset2) return islset1 + @classmethod + def _fromast(cls, node): + from .polyhedra import Polyhedron + if isinstance(node, ast.Module) and len(node.body) == 1: + return cls._fromast(node.body[0]) + elif isinstance(node, ast.Expr): + return cls._fromast(node.value) + elif isinstance(node, ast.UnaryOp): + domain = cls._fromast(node.operand) + if isinstance(node.operand, ast.invert): + return Not(domain) + elif isinstance(node, ast.BinOp): + domain1 = cls._fromast(node.left) + domain2 = cls._fromast(node.right) + if isinstance(node.op, ast.BitAnd): + return And(domain1, domain2) + elif isinstance(node.op, ast.BitOr): + return Or(domain1, domain2) + elif isinstance(node, ast.Compare): + equalities = [] + inequalities = [] + left = Expression._fromast(node.left) + for i in range(len(node.ops)): + op = node.ops[i] + right = Expression._fromast(node.comparators[i]) + if isinstance(op, ast.Lt): + inequalities.append(right - left - 1) + elif isinstance(op, ast.LtE): + inequalities.append(right - left) + elif isinstance(op, ast.Eq): + equalities.append(left - right) + elif isinstance(op, ast.GtE): + inequalities.append(left - right) + elif isinstance(op, ast.Gt): + inequalities.append(left - right - 1) + else: + break + left = right + else: + return Polyhedron(equalities, inequalities) + raise SyntaxError('invalid syntax') + @classmethod def fromstring(cls, string): - raise NotImplementedError + # remove brackets + string = re.sub(r'^\{\s*|\s*\}$', '', string) + # replace '=' by '==' + string = re.sub(r'([^<=>])=([^<=>])', r'\1==\2', string) + # replace 'and', 'or', 'not' + string = re.sub(r'\band\b|,|&&|/\\|∧|∩', r' & ', string) + string = re.sub(r'\bor\b|;|\|\||\\/|∨|∪', r' | ', string) + string = re.sub(r'\bnot\b|!|¬', r' ~', string) + tokens = re.split(r'(&|\||~)', string) + for i, token in enumerate(tokens): + if i % 2 == 0: + # add implicit multiplication operators, e.g. '5x' -> '5*x' + token = re.sub(r'(\d+|\))\s*([^\W\d_]\w*|\()', r'\1*\2', token) + token = '({})'.format(token) + tokens[i] = token + string = ''.join(tokens) + tree = ast.parse(string) + return cls._fromast(tree) def __repr__(self): assert len(self.polyhedra) >= 2 diff --git a/pypol/polyhedra.py b/pypol/polyhedra.py index 787e965..d181646 100644 --- a/pypol/polyhedra.py +++ b/pypol/polyhedra.py @@ -1,7 +1,5 @@ -import ast import functools import numbers -import re from . import islhelper @@ -150,54 +148,12 @@ class Polyhedron(Domain): islbset = libisl.isl_basic_set_add_constraint(islbset, islin) return islbset - @classmethod - def _fromast(cls, node): - if isinstance(node, ast.Module) and len(node.body) == 1: - return cls._fromast(node.body[0]) - elif isinstance(node, ast.Expr): - return cls._fromast(node.value) - elif isinstance(node, ast.BinOp) and isinstance(node.op, ast.BitAnd): - equalities1, inequalities1 = cls._fromast(node.left) - equalities2, inequalities2 = cls._fromast(node.right) - equalities = equalities1 + equalities2 - inequalities = inequalities1 + inequalities2 - return equalities, inequalities - elif isinstance(node, ast.Compare): - equalities = [] - inequalities = [] - left = Expression._fromast(node.left) - for i in range(len(node.ops)): - op = node.ops[i] - right = Expression._fromast(node.comparators[i]) - if isinstance(op, ast.Lt): - inequalities.append(right - left - 1) - elif isinstance(op, ast.LtE): - inequalities.append(right - left) - elif isinstance(op, ast.Eq): - equalities.append(left - right) - elif isinstance(op, ast.GtE): - inequalities.append(left - right) - elif isinstance(op, ast.Gt): - inequalities.append(left - right - 1) - else: - break - left = right - else: - return equalities, inequalities - raise SyntaxError('invalid syntax') - @classmethod def fromstring(cls, string): - string = string.strip() - string = re.sub(r'^\{\s*|\s*\}$', '', string) - string = re.sub(r'([^<=>])=([^<=>])', r'\1==\2', string) - string = re.sub(r'(\d+|\))\s*([^\W\d_]\w*|\()', r'\1*\2', string) - tokens = re.split(r',|;|and|&&|/\\|∧', string, flags=re.I) - tokens = ['({})'.format(token) for token in tokens] - string = ' & '.join(tokens) - tree = ast.parse(string, 'eval') - equalities, inequalities = cls._fromast(tree) - return cls(equalities, inequalities) + domain = Domain.fromstring(string) + if not isinstance(domain, Polyhedron): + raise ValueError('non-polyhedral expression: {!r}'.format(string)) + return domain def __repr__(self): if self.isempty(): -- 2.20.1