File size: 18,927 Bytes
5316c4e
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
-- SPDX-License-Identifier: AGPL-3.0-or-later

-- | The rules, as a pure function from a snapshot of the repository to the
-- list of ways it breaks them. Purity is what makes the gate testable: the
-- test suite plants each defect in a snapshot and requires the named rule to
-- fire (VERIFICATION.md).
module MP.Gate.Rules
  ( Rule (..)
  , Violation (..)
  , SourceFile (..)
  , Package (..)
  , Repo (..)
  , checkRepo
  , bootPackages
  , spdxHeader
  ) where

import Data.Char (isSpace, toLower)
import Data.List (isInfixOf, isPrefixOf, isSuffixOf, nub, sort, (\\))
import MP.Gate.Model
import MP.Gate.Render (renderConformance)
import MP.Gate.Scan

data Rule
  = R1 -- ^ the model is the single source
  | R2 -- ^ honesty levels are load-bearing
  | R3 -- ^ every ID is tested, every test tag is an ID
  | R4 -- ^ nothing is deferred
  | R5 -- ^ everything shipped is total
  | R6 -- ^ nothing arrives from outside the compiler and this repository
  deriving (Eq, Ord, Show)

data Violation = Violation Rule String
  deriving (Eq, Show)

data SourceFile = SourceFile {sourcePath :: FilePath, sourceText :: String, sourceIsTest :: Bool}

data Package = Package
  { packageName :: String
  , packageCabal :: String
  , packageSources :: [SourceFile]
  }

data Repo = Repo
  { repoIds :: String
  , repoLedger :: String
  , repoAuthorities :: String
  , repoConformance :: String
  , repoProject :: String
  , repoPackageDirs :: [String]
  , repoPackages :: [Package]
  , repoFormal :: [SourceFile]
  -- ^ every @.agda@ file under @formal/@, with paths like @formal/Montrepol/Kish.agda@
  , repoLiquid :: [SourceFile]
  -- ^ every @.hs@ file under @liquid/@, the one layer allowed outside dependencies
  , repoLiquidProject :: Maybe String
  -- ^ @liquid/cabal.project@, if it exists
  , repoLiquidCabal :: Maybe String
  -- ^ @liquid/mp-liquid.cabal@, if it exists
  , repoDex :: [SourceFile]
  -- ^ every @.dx@ file under @dex/@: quines whose checks are tagged
  -- @# check XX-00@ and registered to the package @dex@
  }

-- | The first line of every Haskell source, and one of the first two of
-- every @.cabal@ file.
spdxHeader :: String
spdxHeader = "-- SPDX-License-" <> "Identifier: AGPL-3.0-or-later"

-- | Libraries that ship with GHC 9.10.1. Nothing else may be depended on.
bootPackages :: [String]
bootPackages = ["base", "array", "containers", "directory", "filepath", "process"]

checkRepo :: Repo -> [Violation]
checkRepo repo = case readModel (repoIds repo) (repoLedger repo) (repoAuthorities repo) of
  Left e -> Violation R1 ("the model does not parse: " <> e) : sourceRules repo ++ formalRules repo ++ liquidRules repo ++ dexRules repo
  Right model -> modelRules repo model ++ sourceRules repo ++ formalRules repo ++ liquidRules repo ++ dexRules repo

------------------------------------------------------------------------------

modelRules :: Repo -> Model -> [Violation]
modelRules repo model@(Model rows claims auths) =
  concat
    [ -- R1
      [ Violation R1 "CONFORMANCE.md differs from the model; run `mp-gate write`"
      | repoConformance repo /= renderConformance model
      ]
    , [Violation R1 ("ID " <> i <> " is registered more than once") | i <- duplicates (map rowId rows)]
    , [Violation R1 ("ledger key " <> k <> " appears more than once") | k <- duplicates (map claimKey claims)]
    , [Violation R1 ("ID " <> show (rowId r) <> " is not of the form XX-00") | r <- rows, not (isConformanceId (rowId r))]
    , [ Violation R1 ("ID " <> rowId r <> " names package " <> rowPackage r <> ", which does not exist")
      | r <- rows
      , rowPackage r `notElem` map packageName (repoPackages repo)
      , not (rowPackage r == "dex" && not (null (repoDex repo)))
      ]
    , -- R2
      [ Violation R2 ("ID " <> rowId r <> " is `open`: an ID has a test, and a test asserts")
      | r <- rows, rowLevel r == Open
      ]
    , [ Violation R2 ("ID " <> rowId r <> " is `some-true` but cites no authority")
      | r <- rows, rowLevel r == SomeTrue, null (rowAuthorities r)
      ]
    , [ Violation R2 ("ledger " <> claimKey c <> " is `some-true` but cites no authority")
      | c <- claims, claimLevel c == SomeTrue, null (claimAuthorities c)
      ]
    , [ Violation R2 ("ledger " <> claimKey c <> " is `build`: a built claim needs an ID and a test")
      | c <- claims, claimLevel c == Build
      ]
    , [ Violation R2 ("ID " <> rowId r <> " is `proved`: a proof belongs in the ledger, with its Agda file as evidence")
      | r <- rows, rowLevel r == Proved
      ]
    , concat [provedEvidence repo c | c <- claims, claimLevel c == Proved]
    , [ Violation R2 ("ID " <> rowId r <> " is `refined`: a Liquid Haskell result belongs in the ledger")
      | r <- rows, rowLevel r == Refined
      ]
    , concat [refinedEvidence repo c | c <- claims, claimLevel c == Refined]
    , [ Violation R2 (what <> " asserts (" <> show w <> ") at level `" <> levelName l <> "`")
      | (what, l, text) <-
          [("ID " <> rowId r, rowLevel r, rowClaim r) | r <- rows]
            ++ [("ledger " <> claimKey c, claimLevel c, claimStatement c) | c <- claims]
      , l `notElem` [SomeTrue, Proved, Refined]
      , w <- assertingWords
      , w `isInfixOf` map toLower text
      ]
    , [ Violation R2 (who <> " cites unknown authority " <> show k)
      | (who, ks) <- [("ID " <> rowId r, rowAuthorities r) | r <- rows] ++ [("ledger " <> claimKey c, claimAuthorities c) | c <- claims]
      , k <- ks
      , k `notElem` map authKey auths
      ]
    , [ Violation R2 ("authority " <> authKey a <> " is cited by nothing")
      | a <- auths
      , authKey a `notElem` (concatMap rowAuthorities rows ++ concatMap claimAuthorities claims)
      ]
    , -- R3
      testRules repo model
    ]

-- | Words that claim more than a test or a measurement can carry. Halves, as
-- in "MP.Gate.Scan", so the gate does not trip over itself.
assertingWords :: [String]
assertingWords = ["pro" <> "ves", "pro" <> "ven", "guaran" <> "tee", "establish" <> "es", "always hol" <> "ds"]

testRules :: Repo -> Model -> [Violation]
testRules repo (Model rows _ _) =
  concat
    [ [ Violation R3 ("ID " <> rowId r <> " has no test tagged with it in " <> rowPackage r)
      | r <- rows
      , rowId r `notElem` tagsIn (rowPackage r)
      ]
    , [ Violation R3 (sourcePath f <> " is tagged " <> show t <> ", which is not registered")
      | f <- repoDex repo
      , t <- nub (dexTags (sourceText f))
      , t `notElem` map rowId rows
      ]
    , [ Violation R3 (sourcePath f <> " is tagged " <> t <> ", registered to " <> rowPackage r)
      | f <- repoDex repo
      , t <- nub (dexTags (sourceText f))
      , r <- rows
      , rowId r == t
      , rowPackage r /= "dex"
      ]
    , [ Violation R3 ("test in " <> packageName p <> " is tagged " <> show t <> ", which is not registered")
      | p <- repoPackages repo
      , t <- nub (tagsOf p)
      , t `notElem` map rowId rows
      ]
    , [ Violation R3 ("test in " <> packageName p <> " is tagged " <> t <> ", registered to " <> rowPackage r)
      | p <- repoPackages repo
      , t <- nub (tagsOf p)
      , r <- rows
      , rowId r == t
      , rowPackage r /= packageName p
      ]
    ]
  where
    tagsOf p = concatMap (testTags . sourceText) (filter sourceIsTest (packageSources p))
    tagsIn name
      | name == "dex" = concatMap (dexTags . sourceText) (repoDex repo)
      | otherwise = concatMap tagsOf (filter ((== name) . packageName) (repoPackages repo))

-- | IDs in @# check XX-00@ comments (Dex comments start with @#@), which
-- tag the Dex check that follows.
dexTags :: String -> [String]
dexTags src = [i | l <- lines src, ["#", "check", i] <- [words l]]

-- | Dex's comment syntax is @#@, so its header is spelled that way.
dexSpdxHeader :: String
dexSpdxHeader = "# SPDX-License-" <> "Identifier: AGPL-3.0-or-later"

------------------------------------------------------------------------------

sourceRules :: Repo -> [Violation]
sourceRules repo =
  concat
    [ -- R4
      [ Violation R4 (sourcePath f <> ": deferral marker " <> m)
      | f <- sources, m <- deferralMarkers, m `isInfixOf` sourceText f
      ]
    , [ Violation R4 (sourcePath f <> ": stub " <> n)
      | f <- sources, n <- stubNames, n `elem` identifiers (codeOnly (sourceText f))
      ]
    , -- R5
      [ Violation R5 (sourcePath f <> ": partial or unsafe " <> n)
      | f <- sources
      , let code = codeOnly (sourceText f)
      , n <- nub (filter (`elem` partialNames) (identifiers code) ++ filter (`elem` partialOperators) (operators code))
      ]
    , [ Violation R5 ("cabal.project does not set " <> flag)
      | flag <- ["-Wall", "-Werror", "-Wincomplete-uni-patterns"]
      , flag `notElem` words (repoProject repo)
      ]
    , [ Violation R5 (packageName p <> ".cabal weakens warnings with " <> w)
      | p <- repoPackages repo
      , w <- ["-Wwarn", "-Wno-"]
      , w `isInfixOf` packageCabal p
      ]
    , -- R6
      [ Violation R6 (sourcePath f <> ": first line is not the SPDX licence header")
      | f <- sources
      , take 1 (lines (sourceText f)) /= [spdxHeader]
      ]
    , -- Cabal insists that cabal-version is the first line, so there the
      -- header may be second.
      [ Violation R6 (packageName p <> ".cabal: neither of the first two lines is the SPDX licence header")
      | p <- repoPackages repo
      , spdxHeader `notElem` take 2 (lines (packageCabal p))
      ]
    , [ Violation R6 "cabal.project does not set `active-repositories: :none`"
      | not ("active-repositories: :none" `isInfixOf` repoProject repo)
      ]
    , [ Violation R6 ("packages/" <> d <> " is not listed in cabal.project")
      | d <- repoPackageDirs repo
      , ("packages/" <> d) `notElem` words (repoProject repo)
      ]
    , [ Violation R6 (packageName p <> " depends on " <> name <> ", which is neither a GHC boot package nor in this repository")
      | p <- repoPackages repo
      , (name, _) <- dependencies (packageCabal p)
      , name `notElem` bootPackages
      , name `notElem` local
      ]
    , [ Violation R6 (packageName p <> " depends on " <> name <> " without both a lower and an upper bound")
      | p <- repoPackages repo
      , (name, bounds) <- dependencies (packageCabal p)
      , name `elem` bootPackages
      , not (">=" `isInfixOf` bounds && "<" `isInfixOf` filter (/= '=') bounds)
      ]
    ]
  where
    sources = concatMap packageSources (repoPackages repo)
    local = map packageName (repoPackages repo)

-- | @(name, version constraint)@ for every @build-depends@ entry. Entries
-- may continue on following, more-indented lines.
dependencies :: String -> [(String, String)]
dependencies cabal =
  [ (name, trim rest)
  | entry <- concatMap (splitOn ',') (dependsBlocks (lines cabal))
  , let (name, rest) = break isSpace (trim entry)
  , not (null name)
  ]
  where
    dependsBlocks [] = []
    dependsBlocks (l : ls)
      | "build-depends:" `isInfixOf` l =
          let ind = indent l
              (cont, others) = span (\x -> not (all isSpace x) && indent x > ind && not (':' `elem` x)) ls
           in unwords (drop 1 (dropWhile (/= "build-depends:") (words l)) ++ concatMap words cont) : dependsBlocks others
      | otherwise = dependsBlocks ls
    indent = length . takeWhile isSpace

------------------------------------------------------------------------------
-- The formal layer

-- | A @proved@ claim's evidence is @formal/Path.agda: lemma1, lemma2@. The
-- file must exist and define every lemma named. Whether the lemmas *prove*
-- the statement is Agda's job; that the claim points at real lemmas is this.
provedEvidence :: Repo -> Claim -> [Violation]
provedEvidence repo c = case break (== ':') (claimEvidence c) of
  (path, ':' : names) -> case [f | f <- repoFormal repo, sourcePath f == trim path] of
    [] -> [Violation R2 ("ledger " <> claimKey c <> " cites " <> trim path <> ", which does not exist")]
    (f : _) ->
      [ Violation R2 ("ledger " <> claimKey c <> " cites lemma " <> n <> ", which " <> trim path <> " does not define")
      | n <- map trim (splitOn ',' names)
      , not (null n)
      , not (any ((n <> " :") `isPrefixOf`) (map (dropWhile isSpace) (lines (sourceText f))))
      ]
        ++ [Violation R2 ("ledger " <> claimKey c <> " names no lemmas") | all (null . trim) (splitOn ',' names)]
  _ -> [Violation R2 ("ledger " <> claimKey c <> " is `proved` but its evidence is not `formal/File.agda: lemma, ...`")]

-- | A @refined@ claim's evidence is @packages/.../Module.hs: f, g@. The
-- file must be a core source, every function named must carry a
-- @{-\@ f :: ... \@-}@ spec in it, and its module must be one the liquid
-- build compiles: otherwise the spec would be a comment nothing checks.
refinedEvidence :: Repo -> Claim -> [Violation]
refinedEvidence repo c = case break (== ':') (claimEvidence c) of
  (path, ':' : names) -> case [f | p <- repoPackages repo, f <- packageSources p, sourcePath f == trim path] of
    [] -> [Violation R2 ("ledger " <> claimKey c <> " cites " <> trim path <> ", which is not a core source")]
    (f : _) ->
      [ Violation R2 ("ledger " <> claimKey c <> ": " <> trim path <> " has no Liquid Haskell spec for " <> n)
      | n <- map trim (splitOn ',' names)
      , not (null n)
      , not (any (("{-@ " <> n <> " ::") `isPrefixOf`) (map (dropWhile isSpace) (lines (sourceText f))))
      ]
        ++ [ Violation R2 ("ledger " <> claimKey c <> ": the liquid build does not compile " <> modName)
           | modName <- [moduleOfSource (trim path)]
           , not (modName `elem` words (maybe "" id (repoLiquidCabal repo)))
           ]
  _ -> [Violation R2 ("ledger " <> claimKey c <> " is `refined` but its evidence is not `packages/.../File.hs: f, ...`")]
  where
    -- packages/mp-lambda/src/MP/Lambda/Simple.hs is the module MP.Lambda.Simple
    moduleOfSource p =
      let rel = case breakOn "/src/" p of
            Just r -> r
            Nothing -> p
          base = if ".hs" `isSuffixOf` rel then take (length rel - 3) rel else rel
       in map (\ch -> if ch == '/' then '.' else ch) base
    breakOn needle hay = case [drop (length needle) t | t <- suffixes hay, needle `isPrefixOf` t] of
      (r : _) -> Just r
      [] -> Nothing
    suffixes s = s : case s of
      (_ : rest) -> suffixes rest
      [] -> []

-- | Agda escape hatches. Any of them would let a false statement check.
-- @--safe@ already refuses most of them; this is a second, independent net,
-- and it also catches an escape in a file that has lost its @--safe@.
agdaEscapes :: [String]
agdaEscapes =
  [ "postulate", "{!", "TERMINATING", "NON_TERMINATING", "NO_POSITIVITY_CHECK"
  , "NO_UNIVERSE_CHECK", "--type-in-type", "--allow-unsolved-metas", "--no-term" <> "ination-check"
  , "--cumulativity", "--sized-types", "--guardedness", "--injective-type-constructors"
  ]

formalRules :: Repo -> [Violation]
formalRules repo =
  concat
    [ [ Violation R4 (sourcePath f <> ": escape hatch " <> e)
      | f <- fs, e <- agdaEscapes, e `isInfixOf` sourceText f
      ]
    , [ Violation R4 (sourcePath f <> ": deferral marker " <> m)
      | f <- fs, m <- deferralMarkers, m `isInfixOf` sourceText f
      ]
    , [ Violation R5 (sourcePath f <> ": not checked under --safe")
      | f <- fs, not ("{-# OPTIONS --safe" `isInfixOf` sourceText f)
      ]
    , [ Violation R5 (sourcePath f <> " is not imported by formal/Everything.agda, so nothing checks it")
      | not (null fs)
      , f <- fs
      , sourcePath f /= "formal/Everything.agda"
      , ("import " <> moduleOf (sourcePath f)) `notElem` map (unwords . take 2 . words) everything
      ]
    , [ Violation R5 "formal/ has Agda files but no formal/Everything.agda to check them"
      | not (null fs), null [() | f <- fs, sourcePath f == "formal/Everything.agda"]
      ]
    , [ Violation R6 (sourcePath f <> ": first line is not the SPDX licence header")
      | f <- fs, [spdxHeader] /= take 1 (lines (sourceText f))
      ]
    ]
  where
    fs = repoFormal repo
    everything = concat [lines (sourceText f) | f <- fs, sourcePath f == "formal/Everything.agda"]
    -- formal/Montrepol/Kish.agda is the module Montrepol.Kish
    moduleOf p =
      let rel = drop (length "formal/") p
          base = if ".agda" `isSuffixOf` rel then take (length rel - length ".agda") rel else rel
       in map (\ch -> if ch == '/' then '.' else ch) base

------------------------------------------------------------------------------
-- The Liquid Haskell layer

-- | @liquid/@ is exempt from R6's no-outside-dependencies rule, and only in
-- one direction: it may use Hackage and Z3, but it is a separate build, the
-- root project may not include it, and no core package may depend on it (the
-- ordinary R6 dependency check already refuses @liquidhaskell@ and
-- @mp-liquid@ in @packages/@). Its sources keep every other rule that can
-- be read from them.
liquidRules :: Repo -> [Violation]
liquidRules repo =
  concat
    [ [ Violation R6 "liquid/ has sources but no liquid/cabal.project of its own"
      | not (null fs), repoLiquidProject repo == Nothing
      ]
    , [ Violation R6 ("the root cabal.project includes the liquid layer (" <> w <> ")")
      | w <- words (repoProject repo)
      , "liquid" `isPrefixOf` w
      ]
    , [ Violation R6 (sourcePath f <> ": first line is not the SPDX licence header")
      | f <- fs, [spdxHeader] /= take 1 (lines (sourceText f))
      ]
    , [ Violation R4 (sourcePath f <> ": deferral marker " <> m)
      | f <- fs, m <- deferralMarkers, m `isInfixOf` sourceText f
      ]
    , -- The refinements of core modules live in the core sources, so the
      -- escapes are refused there too.
      [ Violation R4 (sourcePath f <> ": lazy or assumed refinement (" <> a <> ")")
      | f <- fs ++ concatMap packageSources (repoPackages repo)
      , a <- liquidEscapes
      , a `isInfixOf` sourceText f
      ]
    ]
  where
    fs = repoLiquid repo

-- | Dex files keep the licence and deferral rules.
dexRules :: Repo -> [Violation]
dexRules repo =
  [ Violation R6 (sourcePath f <> ": first line is not the SPDX licence header")
  | f <- repoDex repo, [dexSpdxHeader] /= take 1 (lines (sourceText f))
  ]
    ++ [ Violation R4 (sourcePath f <> ": deferral marker " <> m)
       | f <- repoDex repo, m <- deferralMarkers, m `isInfixOf` sourceText f
       ]

-- | Liquid Haskell annotations that switch checking off for what they touch.
-- In halves, so that this list does not match itself (see "MP.Gate.Scan").
liquidEscapes :: [String]
liquidEscapes = ["@ ass" <> "ume", "@ la" <> "zy", "@ ig" <> "nore", "--no-term" <> "ination", "--skip-mod" <> "ule"]

trim :: String -> String
trim = reverse . dropWhile isSpace . reverse . dropWhile isSpace

splitOn :: Char -> String -> [String]
splitOn ch s = case break (== ch) s of
  (a, _ : b) -> a : splitOn ch b
  (a, []) -> [a]

duplicates :: Ord a => [a] -> [a]
duplicates xs = nub (sort (xs \\ nub xs))