Coverage for src / competitive_verifier / models / file.py: 100%

1import enum 

2import pathlib 

3from functools import cached_property 

4from logging import getLogger 

5from typing import TYPE_CHECKING, Any, NamedTuple 

6 

7from pydantic import AliasChoices, BaseModel, Field 

8 

9from competitive_verifier.log import GitHubMessageParams 

10from competitive_verifier.util import to_relative 

11 

12from ._scc import SccGraph 

13from .path import ForcePosixPath, SortedPathSet 

14from .verification import Verification 

15 

16if TYPE_CHECKING: 

17 from _typeshed import StrPath 

18 

19 from .result import FileResult 

20logger = getLogger(__name__) 

21 

22_DependencyEdges = dict[pathlib.Path, set[pathlib.Path]] 

23 

24 

25class _DependencyGraph(NamedTuple): 

26 depends_on: _DependencyEdges 

27 required_by: _DependencyEdges 

28 verified_with: _DependencyEdges 

29 

30 

31class DocumentOutputMode(str, enum.Enum): 

32 visible = "visible" 

33 """The document will be output. (default) 

34 """ 

35 

36 hidden = "hidden" 

37 """The document will be output but will not linked from other pages. 

38 """ 

39 

40 no_index = "no-index" 

41 """The document will be output but will not linked from index page. 

42 """ 

43 

44 never = "never" 

45 """The document will be never output. 

46 """ 

47 

48 

49class AdditionalSource(BaseModel): 

50 name: str = Field( 

51 examples=["source_name"], 

52 description="The name of source file.", 

53 ) 

54 """The name of source file. 

55 """ 

56 path: ForcePosixPath = Field( 

57 description="The path source file.", 

58 examples=["relative_path_of_directory/file_name.cpp"], 

59 ) 

60 """The path source file. 

61 """ 

62 

63 

64# Deprecated typo alias kept for compatibility with previous releases. 

65AddtionalSource = AdditionalSource 

66 

67 

68class VerificationFile(BaseModel): 

69 dependencies: SortedPathSet = Field( 

70 default_factory=set[ForcePosixPath], 

71 description="The list of dependent files as paths relative to root.", 

72 ) 

73 """The list of dependent files as paths relative to root. 

74 """ 

75 verification: list[Verification] | Verification | None = Field( 

76 default_factory=list[Verification] 

77 ) 

78 document_attributes: dict[str, Any] = Field( 

79 default_factory=dict[str, Any], 

80 description="The attributes for documentation.", 

81 ) 

82 """The attributes for documentation. 

83 """ 

84 additional_sources: list[AdditionalSource] = Field( 

85 default_factory=list[AdditionalSource], 

86 validation_alias=AliasChoices("additional_sources", "additonal_sources"), 

87 description="The additional source paths.", 

88 examples=[ 

89 [ 

90 AdditionalSource( 

91 name="source_name", 

92 path=pathlib.Path("relative_path_of_directory/file_name.cpp"), 

93 ), 

94 ], 

95 ], 

96 ) 

97 """The additional source paths 

98 """ 

99 

100 @property 

101 def title(self) -> str | None: 

102 """The document title specified as a attributes.""" 

103 d = self.document_attributes 

104 return d.get("TITLE") or d.get("document_title") 

105 

106 @property 

107 def display(self) -> DocumentOutputMode | None: 

108 """The document output mode as a attributes.""" 

109 d = self.document_attributes.get("DISPLAY") 

110 if not isinstance(d, str): 

111 return None 

112 try: 

113 return DocumentOutputMode[d.lower().replace("-", "_")] 

114 except KeyError: 

115 return None 

116 

117 @property 

118 def verification_list(self) -> list[Verification]: 

119 if self.verification is None: 

120 return [] 

121 if isinstance(self.verification, list): 

122 return self.verification 

123 return [self.verification] 

124 

125 def is_verification(self) -> bool: 

126 return bool(self.verification) 

127 

128 def is_lightweight_verification(self) -> bool: 

129 """If the effort required for verification is small, treat it as skippable.""" 

130 return self.is_verification() and all( 

131 v.is_lightweight for v in self.verification_list 

132 ) 

133 

134 

135class VerificationInput(BaseModel): 

136 files: dict[ForcePosixPath, VerificationFile] = Field( 

137 default_factory=dict[ForcePosixPath, VerificationFile], 

138 description="The key is relative path from the root.", 

139 ) 

140 

141 def merge(self, other: "VerificationInput") -> "VerificationInput": 

142 return VerificationInput(files=self.files | other.files) 

143 

144 @classmethod 

145 def parse_file_relative(cls, path: "StrPath") -> "VerificationInput": 

146 impl = cls.model_validate_json(pathlib.Path(path).read_bytes()) 

147 new_files: dict[pathlib.Path, VerificationFile] = {} 

148 for p, f in impl.files.items(): 

149 rp = to_relative(p) 

150 if not rp: 

151 logger.warning( 

152 "Files in other directories are not subject to verification: %s", 

153 p, 

154 extra={"github": GitHubMessageParams()}, 

155 ) 

156 continue 

157 f.dependencies = {d for d in map(to_relative, f.dependencies) if d} 

158 new_files[rp] = f 

159 

160 impl.files = new_files 

161 return impl 

162 

163 def scc(self, *, reverse: bool = False) -> list[set[pathlib.Path]]: 

164 """Strongly Connected Component. 

165 

166 Args: 

167 reverse (bool): if True, libraries are ahead. otherwise, tests are ahead 

168 Returns: 

169 list[set[pathlib.Path]]: Strongly Connected Component result 

170 """ 

171 paths = list(self.files.keys()) 

172 vers_rev = {v: i for i, v in enumerate(paths)} 

173 g = SccGraph(len(paths)) 

174 for p, file in self.files.items(): 

175 for e in file.dependencies: 

176 t = vers_rev.get(e, -1) 

177 if t >= 0: 

178 if reverse: 

179 g.add_edge(t, vers_rev[p]) 

180 else: 

181 g.add_edge(vers_rev[p], t) 

182 return [{paths[ix] for ix in ls} for ls in g.scc()] 

183 

184 @cached_property 

185 def transitive_depends_on(self) -> _DependencyEdges: 

186 d: _DependencyEdges = {} 

187 g = self.scc(reverse=True) 

188 for group in g: 

189 result = group.copy() 

190 for p in group: 

191 for dep in self.files[p].dependencies: 

192 if dep not in result: 

193 resolved = d.get(dep) 

194 if resolved is not None: 

195 result.update(resolved) 

196 for p in group: 

197 d[p] = result 

198 

199 return d 

200 

201 @cached_property 

202 def _dependency_graph( 

203 self, 

204 ) -> _DependencyGraph: 

205 """Resolve dependency graphs. 

206 

207 Returns: Dependency graphs 

208 """ 

209 depends_on: _DependencyEdges = {} 

210 required_by: _DependencyEdges = {} 

211 verified_with: _DependencyEdges = {} 

212 

213 # initialize 

214 for path in self.files: 

215 depends_on[path] = set() 

216 required_by[path] = set() 

217 verified_with[path] = set() 

218 

219 # build the graph 

220 for src, vf in self.files.items(): 

221 for dst in vf.dependencies: 

222 if src == dst: 

223 continue 

224 if dst not in depends_on: # pragma: no cover 

225 logger.warning( 

226 "The file `%s` which is depended from `%s` is ignored " 

227 "because it's not listed as a source code file.", 

228 dst, 

229 src, 

230 extra={"github": GitHubMessageParams()}, 

231 ) 

232 continue 

233 

234 depends_on[src].add(dst) 

235 if vf.is_verification(): 

236 verified_with[dst].add(src) 

237 else: 

238 required_by[dst].add(src) 

239 return _DependencyGraph( 

240 depends_on=depends_on, 

241 required_by=required_by, 

242 verified_with=verified_with, 

243 ) 

244 

245 @property 

246 def depends_on(self) -> _DependencyEdges: 

247 return self._dependency_graph.depends_on 

248 

249 @property 

250 def required_by(self) -> _DependencyEdges: 

251 return self._dependency_graph.required_by 

252 

253 @property 

254 def verified_with(self) -> _DependencyEdges: 

255 return self._dependency_graph.verified_with 

256 

257 def filtered_files(self, files: dict[ForcePosixPath, "FileResult"]): 

258 for k, v in files.items(): 

259 if k in self.files: 

260 yield k, v