• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

msakai / pseudo-boolean / 73

21 Mar 2024 03:19PM UTC coverage: 92.963% (+0.3%) from 92.655%
73

push

github

web-flow
Merge 8ab479938 into d4f85bfb0

22 of 22 new or added lines in 6 files covered. (100.0%)

9 existing lines in 3 files now uncovered.

502 of 540 relevant lines covered (92.96%)

0.93 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.73
/src/Data/PseudoBoolean/Parsec.hs
1
{-# LANGUAGE BangPatterns, FlexibleContexts #-}
2
{-# OPTIONS_GHC -Wall #-}
3
-----------------------------------------------------------------------------
4
-- |
5
-- Module      :  Data.PseudoBoolean.Parsec
6
-- Copyright   :  (c) Masahiro Sakai 2011-2015
7
-- License     :  BSD-style
8
-- 
9
-- Maintainer  :  masahiro.sakai@gmail.com
10
-- Portability :  non-portable (BangPatterns, FlexibleContexts)
11
--
12
-- A parser library for OPB file and WBO files used in pseudo boolean competition.
13
-- 
14
-- References:
15
--
16
-- * Input/Output Format and Solver Requirements for the Competitions of
17
--   Pseudo-Boolean Solvers
18
--   <http://www.cril.univ-artois.fr/PB11/format.pdf>
19
--
20
-----------------------------------------------------------------------------
21

22
module Data.PseudoBoolean.Parsec
23
  (
24
  -- * Parsing OPB files
25
    opbParser
26
  , parseOPBString
27
  , parseOPBByteString
28
  , parseOPBFile
29

30
  -- * Parsing WBO files
31
  , wboParser
32
  , parseWBOString
33
  , parseWBOByteString
34
  , parseWBOFile
35
  ) where
36

37
import Prelude hiding (sum)
38
import Control.Monad
39
import Data.ByteString.Lazy (ByteString)
40
import Data.Maybe
41
import Text.Parsec
42
import qualified Text.Parsec.ByteString.Lazy as ParsecBS
43
import Data.PseudoBoolean.Types
44
import Data.PseudoBoolean.Internal.TextUtil
45

46
-- | Parser for OPB files
47
opbParser :: Stream s m Char => ParsecT s u m Formula
48
opbParser = formula
×
49

50
-- | Parser for WBO files
51
wboParser :: Stream s m Char => ParsecT s u m SoftFormula
52
wboParser = softformula
×
53

54
-- <formula>::= <sequence_of_comments> [<objective>] <sequence_of_comments_or_constraints>
55
formula :: Stream s m Char => ParsecT s u m Formula
56
formula = do
1✔
57
  h <- optionMaybe hint
1✔
58
  sequence_of_comments
1✔
59
  obj <- optionMaybe objective
1✔
60
  cs <- sequence_of_comments_or_constraints
1✔
61
  return $
1✔
62
    Formula
1✔
63
    { pbObjectiveFunction = obj
1✔
64
    , pbConstraints = cs
1✔
65
    , pbNumVars = fromMaybe (pbComputeNumVars (fmap snd obj) cs) (fmap fst h)
1✔
66
    , pbNumConstraints = fromMaybe (length cs) (fmap snd h)
1✔
67
    }
68

69
hint :: Stream s m Char => ParsecT s u m (Int,Int)
70
hint = try $ do
1✔
71
  _ <- char '*'
1✔
72
  zeroOrMoreSpace
1✔
73
  _ <- string "#variable="
1✔
74
  zeroOrMoreSpace
1✔
75
  nv <- unsigned_integer
1✔
76
  oneOrMoreSpace  
1✔
77
  _ <- string "#constraint="
1✔
78
  zeroOrMoreSpace
1✔
79
  nc <- unsigned_integer
1✔
80
  _ <- manyTill anyChar eol
1✔
81
  return (fromIntegral nv, fromIntegral nc)
1✔
82

83
-- <sequence_of_comments>::= <comment> [<sequence_of_comments>]
84
sequence_of_comments :: Stream s m Char => ParsecT s u m ()
85
sequence_of_comments = skipMany comment -- XXX: we allow empty sequence
1✔
86

87
-- <comment>::= "*" <any_sequence_of_characters_other_than_EOL> <EOL>
88
comment :: Stream s m Char => ParsecT s u m ()
89
comment = do
1✔
90
  _ <- char '*' 
1✔
91
  _ <- manyTill anyChar eol
1✔
92
  spaces -- We relax the grammer and allow spaces in the beggining of next component.
1✔
93
  return ()
×
94

95
-- <sequence_of_comments_or_constraints>::= <comment_or_constraint> [<sequence_of_comments_or_constraints>]
96
sequence_of_comments_or_constraints :: Stream s m Char => ParsecT s u m [Constraint]
97
sequence_of_comments_or_constraints = do
1✔
98
  xs <- many comment_or_constraint -- We relax the grammer and allow spaces in the beginning of next component.
1✔
99
  return $ catMaybes xs
1✔
100

101
-- <comment_or_constraint>::= <comment>|<constraint>
102
comment_or_constraint :: Stream s m Char => ParsecT s u m (Maybe Constraint)
103
comment_or_constraint =
1✔
104
  (comment >> return Nothing) <|> (liftM Just constraint)
1✔
105

106
-- <objective>::= <objective_type> <zeroOrMoreSpace> <sum> ";"
107
objective :: Stream s m Char => ParsecT s u m Objective
108
objective = do
1✔
109
  dir <- objective_type
1✔
110
  zeroOrMoreSpace
1✔
111
  obj <- sum
1✔
112
  semi
1✔
113
  return (dir, obj)
1✔
114

115
-- <constraint>::= <sum> <relational_operator> <zeroOrMoreSpace> <integer> <zeroOrMoreSpace> ";"
116
constraint :: Stream s m Char => ParsecT s u m Constraint
117
constraint = do
1✔
118
  lhs <- sum
1✔
119
  op <- relational_operator
1✔
120
  zeroOrMoreSpace
1✔
121
  rhs <- integer
1✔
122
  zeroOrMoreSpace
1✔
123
  semi
1✔
124
  return (lhs, op, rhs)
1✔
125

126
-- <sum>::= <weightedterm> | <weightedterm> <sum>
127
sum :: Stream s m Char => ParsecT s u m Sum
128
sum = many weightedterm -- we relax the grammer to allow empty sum
1✔
129

130
-- <weightedterm>::= <integer> <oneOrMoreSpace> <term> <oneOrMoreSpace>
131
weightedterm :: Stream s m Char => ParsecT s u m WeightedTerm
132
weightedterm = do
1✔
133
  w <- integer
1✔
134
  oneOrMoreSpace
1✔
135
  t <- term
1✔
136
  zeroOrMoreSpace -- we relax the grammar to allow omitting spaces at the end of <sum>.
1✔
137
  return (w,t)
1✔
138

139
-- <integer>::= <unsigned_integer> | "+" <unsigned_integer> | "-" <unsigned_integer>
140
integer :: Stream s m Char => ParsecT s u m Integer
141
integer = msum
1✔
142
  [ unsigned_integer
1✔
143
  , char '+' >> unsigned_integer
1✔
144
  , char '-' >> liftM negate unsigned_integer
1✔
145
  ]
146

147
-- <unsigned_integer>::= <digit> | <digit><unsigned_integer>
148
unsigned_integer :: Stream s m Char => ParsecT s u m Integer
149
unsigned_integer = do
1✔
150
  ds <- many1 digit
1✔
151
  return $! readUnsignedInteger ds
1✔
152

153
-- <objective_type>::= "min:" | "max:"
154
objective_type :: Stream s m Char => ParsecT s u m OptDir
155
objective_type = (try (string "min:") >> return OptMin) <|> (string "max:" >> return OptMax)
1✔
156

157
-- <relational_operator>::= ">=" | "="
158
relational_operator :: Stream s m Char => ParsecT s u m Op
159
relational_operator = (string ">=" >> return Ge) <|> (string "=" >> return Eq)
1✔
160

161
-- <variablename>::= "x" <unsigned_integer>
162
variablename :: Stream s m Char => ParsecT s u m Var
163
variablename = do
1✔
164
  _ <- char 'x'
1✔
165
  i <- unsigned_integer
1✔
166
  return $! fromIntegral i
1✔
167

168
-- <oneOrMoreSpace>::= " " [<oneOrMoreSpace>]
169
oneOrMoreSpace :: Stream s m Char => ParsecT s u m ()
170
oneOrMoreSpace  = skipMany1 (char ' ')
1✔
171

172
-- <zeroOrMoreSpace>::= [" " <zeroOrMoreSpace>]
173
zeroOrMoreSpace :: Stream s m Char => ParsecT s u m ()
174
-- zeroOrMoreSpace = skipMany (char ' ')
175
zeroOrMoreSpace = spaces
1✔
176
-- We relax the grammer and allow more type of spacing
177

178
eol :: Stream s m Char => ParsecT s u m ()
UNCOV
179
eol = char '\n' >> return ()
×
180

181
semi :: Stream s m Char => ParsecT s u m ()
182
semi = char ';' >> spaces
1✔
183
-- We relax the grammer and allow spaces in the beginning of next component.
184

185
{-
186
For linear pseudo-Boolean instances, <term> is defined as
187
<term>::=<variablename>
188

189
For non-linear instances, <term> is defined as
190
<term>::= <oneOrMoreLiterals>
191
-}
192
term :: Stream s m Char => ParsecT s u m Term
193
term = oneOrMoreLiterals
1✔
194

195
-- <oneOrMoreLiterals>::= <literal> | <literal> <oneOrMoreSpace> <oneOrMoreLiterals>
196
oneOrMoreLiterals :: Stream s m Char => ParsecT s u m [Lit]
197
oneOrMoreLiterals = do
1✔
198
  l <- literal
1✔
199
  mplus (try $ oneOrMoreSpace >> liftM (l:) oneOrMoreLiterals) (return [l])
1✔
200
-- Note that we cannot use sepBy1.
201
-- In "p `sepBy1` q", p should success whenever q success.
202
-- But it's not the case here.
203

204
-- <literal>::= <variablename> | "~"<variablename>
205
literal :: Stream s m Char => ParsecT s u m Lit
206
literal = variablename <|> (char '~' >> liftM negate variablename)
1✔
207

208
-- | Parse a OPB format string containing pseudo boolean problem.
209
parseOPBString :: SourceName -> String -> Either ParseError Formula
210
parseOPBString = parse (formula <* eof)
1✔
211

212
-- | Parse a OPB format lazy bytestring containing pseudo boolean problem.
213
parseOPBByteString :: SourceName -> ByteString -> Either ParseError Formula
214
parseOPBByteString = parse (formula <* eof)
1✔
215

216
-- | Parse a OPB file containing pseudo boolean problem.
217
parseOPBFile :: FilePath -> IO (Either ParseError Formula)
218
parseOPBFile = ParsecBS.parseFromFile (formula <* eof)
1✔
219

220

221
-- <softformula>::= <sequence_of_comments> <softheader> <sequence_of_comments_or_constraints>
222
softformula :: Stream s m Char => ParsecT s u m SoftFormula
223
softformula = do
1✔
224
  h <- optionMaybe hint
1✔
225
  sequence_of_comments
1✔
226
  top <- softheader
1✔
227
  cs <- wbo_sequence_of_comments_or_constraints
1✔
228
  return $
1✔
229
    SoftFormula
1✔
230
    { wboTopCost = top
1✔
231
    , wboConstraints = cs
1✔
232
    , wboNumVars = fromMaybe (wboComputeNumVars cs) (fmap fst h)
1✔
233
    , wboNumConstraints = fromMaybe (length cs) (fmap snd h)
1✔
234
    }
235

236
-- <softheader>::= "soft:" [<unsigned_integer>] ";"
237
softheader :: Stream s m Char => ParsecT s u m (Maybe Integer)
238
softheader = do
1✔
239
  _ <- string "soft:"
1✔
240
  zeroOrMoreSpace -- XXX
1✔
241
  top <- optionMaybe unsigned_integer
1✔
242
  zeroOrMoreSpace -- XXX
1✔
243
  semi
1✔
244
  return top
1✔
245

246
-- <sequence_of_comments_or_constraints>::= <comment_or_constraint> [<sequence_of_comments_or_constraints>]
247
wbo_sequence_of_comments_or_constraints :: Stream s m Char => ParsecT s u m [SoftConstraint]
248
wbo_sequence_of_comments_or_constraints = do
1✔
249
  xs <- many wbo_comment_or_constraint -- XXX: we relax the grammer to allow empty sequence
1✔
250
  return $ catMaybes xs
1✔
251

252
-- <comment_or_constraint>::= <comment>|<constraint>|<softconstraint>
253
wbo_comment_or_constraint :: Stream s m Char => ParsecT s u m (Maybe SoftConstraint)
UNCOV
254
wbo_comment_or_constraint = (comment >> return Nothing) <|> m
×
255
  where
256
    m = liftM Just $ (constraint >>= \c -> return (Nothing, c)) <|> softconstraint
1✔
257

258
-- <softconstraint>::= "[" <zeroOrMoreSpace> <unsigned_integer> <zeroOrMoreSpace> "]" <constraint>
259
softconstraint :: Stream s m Char => ParsecT s u m SoftConstraint
260
softconstraint = do
1✔
261
  _ <- char '['
1✔
262
  zeroOrMoreSpace
1✔
263
  cost <- unsigned_integer
1✔
264
  zeroOrMoreSpace
1✔
265
  _ <- char ']'
1✔
266
  zeroOrMoreSpace -- XXX
1✔
267
  c <- constraint
1✔
268
  return (Just cost, c)
1✔
269

270
-- | Parse a WBO format string containing weighted boolean optimization problem.
271
parseWBOString :: SourceName -> String -> Either ParseError SoftFormula
272
parseWBOString = parse (softformula <* eof)
1✔
273

274
-- | Parse a WBO format lazy bytestring containing pseudo boolean problem.
275
parseWBOByteString :: SourceName -> ByteString -> Either ParseError SoftFormula
276
parseWBOByteString = parse (softformula <* eof)
1✔
277

278
-- | Parse a WBO file containing weighted boolean optimization problem.
279
parseWBOFile :: FilePath -> IO (Either ParseError SoftFormula)
280
parseWBOFile = ParsecBS.parseFromFile (softformula <* eof)
1✔
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc