Debian Codegraph @

share/libc/__fc_string_axiomatic.h

raw
1 /**************************************************************************/
2 /* */
3 /* This file is part of Frama-C. */
4 /* */
5 /* Copyright (C) 2007-2022 */
6 /* CEA (Commissariat à l'énergie atomique et aux énergies */
7 /* alternatives) */
8 /* */
9 /* you can redistribute it and/or modify it under the terms of the GNU */
10 /* Lesser General Public License as published by the Free Software */
11 /* Foundation, version 2.1. */
12 /* */
13 /* It is distributed in the hope that it will be useful, */
14 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
15 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
16 /* GNU Lesser General Public License for more details. */
17 /* */
18 /* See the GNU Lesser General Public License version 2.1 */
19 /* for more details (enclosed in the file licenses/LGPLv2.1). */
20 /* */
21 /**************************************************************************/
22
23 /* $Id: jessie_machine_prolog.h,v 1.8 2008-12-09 10:17:25 uid525 Exp $ */
24
25 #ifndef __FC_STRING_AXIOMATIC
26 #define __FC_STRING_AXIOMATIC
27 #include "features.h"
28 __PUSH_FC_STDLIB
29
30 #include "__fc_define_null.h"
31 #include "__fc_define_wchar_t.h"
32
33 __BEGIN_DECLS
34
35 /*@ axiomatic MemCmp {
36 @ logic ℤ memcmp{L1,L2}(char *s1, char *s2, ℤ n)
37 @ reads \at(s1[0..n - 1],L1), \at(s2[0..n - 1],L2);
38 @
39 @ axiom memcmp_zero{L1,L2}:
40 @ \forall char *s1, *s2; \forall ℤ n;
41 @ memcmp{L1,L2}(s1,s2,n) == 0
42 @ <==> \forall ℤ i; 0 <= i < n ==> \at(s1[i],L1) == \at(s2[i],L2);
43 @
44 @ }
45 @*/
46
47 /*@ axiomatic MemChr {
48 @ logic 𝔹 memchr{L}(char *s, ℤ c, ℤ n)
49 @ reads s[0..n - 1];
50 @ // Returns [true] iff array [s] contains character [c]
51 @
52 @ logic ℤ memchr_off{L}(char *s, ℤ c, ℤ n)
53 @ reads s[0..n - 1];
54 @ // Returns the offset at which [c] appears in [s], or [n-1] otherwise.
55 @ // It represents the largest searched index when looking for [c] in [s].
56 @
57 @ axiom memchr_def{L}:
58 @ \forall char *s; \forall ℤ c; \forall ℤ n;
59 @ memchr(s,c,n) <==> \exists int i; 0 <= i < n && s[i] == c;
60 @ }
61 @*/
62
63 /*@ axiomatic MemSet {
64 @ logic 𝔹 memset{L}(char *s, ℤ c, ℤ n)
65 @ reads s[0..n - 1];
66 @ // Returns [true] iff array [s] contains only character [c]
67 @
68 @ axiom memset_def{L}:
69 @ \forall char *s; \forall ℤ c; \forall ℤ n;
70 @ memset(s,c,n) <==> \forall ℤ i; 0 <= i < n ==> s[i] == c;
71 @ }
72 @*/
73
74 /*@ axiomatic StrLen {
75 @ logic ℤ strlen{L}(char *s)
76 @ reads s[0..];
77 @
78 @ axiom strlen_pos_or_null{L}:
79 @ \forall char* s; \forall ℤ i;
80 @ (0 <= i
81 @ && (\forall ℤ j; 0 <= j < i ==> s[j] != '\0')
82 @ && s[i] == '\0') ==> strlen(s) == i;
83 @
84 @ axiom strlen_neg{L}:
85 @ \forall char* s;
86 @ (\forall ℤ i; 0 <= i ==> s[i] != '\0')
87 @ ==> strlen(s) < 0;
88 @
89 @ axiom strlen_before_null{L}:
90 @ \forall char* s; \forall ℤ i; 0 <= i < strlen(s) ==> s[i] != '\0';
91 @
92 @ axiom strlen_at_null{L}:
93 @ \forall char* s; 0 <= strlen(s) ==> s[strlen(s)] == '\0';
94 @
95 @ axiom strlen_not_zero{L}:
96 @ \forall char* s; \forall ℤ i;
97 @ 0 <= i <= strlen(s) && s[i] != '\0' ==> i < strlen(s);
98 @
99 @ axiom strlen_zero{L}:
100 @ \forall char* s; \forall ℤ i;
101 @ 0 <= i <= strlen(s) && s[i] == '\0' ==> i == strlen(s);
102 @
103 @ axiom strlen_sup{L}:
104 @ \forall char* s; \forall ℤ i;
105 @ 0 <= i && s[i] == '\0' ==> 0 <= strlen(s) <= i;
106 @
107 @ axiom strlen_shift{L}:
108 @ \forall char* s; \forall ℤ i;
109 @ 0 <= i <= strlen(s) ==> strlen(s + i) == strlen(s) - i;
110 @
111 @ axiom strlen_create{L}:
112 @ \forall char* s; \forall ℤ i;
113 @ 0 <= i && s[i] == '\0' ==> 0 <= strlen(s) <= i;
114 @
115 @ axiom strlen_create_shift{L}:
116 @ \forall char* s; \forall ℤ i; \forall ℤ k;
117 @ 0 <= k <= i && s[i] == '\0' ==> 0 <= strlen(s+k) <= i - k;
118 @
119 @ axiom memcmp_strlen_left{L}:
120 @ \forall char *s1, *s2; \forall ℤ n;
121 @ memcmp{L,L}(s1,s2,n) == 0 && strlen(s1) < n ==> strlen(s1) == strlen(s2);
122 @
123 @ axiom memcmp_strlen_right{L}:
124 @ \forall char *s1, *s2; \forall ℤ n;
125 @ memcmp{L,L}(s1,s2,n) == 0 && strlen(s2) < n ==> strlen(s1) == strlen(s2);
126 @
127 @ axiom memcmp_strlen_shift_left{L}:
128 @ \forall char *s1, *s2; \forall ℤ k, n;
129 @ memcmp{L,L}(s1,s2 + k,n) == 0 && 0 <= k && strlen(s1) < n ==>
130 @ 0 <= strlen(s2) <= k + strlen(s1);
131 @
132 @ axiom memcmp_strlen_shift_right{L}:
133 @ \forall char *s1, *s2; \forall ℤ k, n;
134 @ memcmp{L,L}(s1 + k,s2,n) == 0 && 0 <= k && strlen(s2) < n ==>
135 @ 0 <= strlen(s1) <= k + strlen(s2);
136 @ }
137 @*/
138
139 /*@ axiomatic StrCmp {
140 @ logic ℤ strcmp{L}(char *s1, char *s2)
141 @ reads s1[0..strlen(s1)], s2[0..strlen(s2)];
142 @
143 @ axiom strcmp_zero{L}:
144 @ \forall char *s1, *s2;
145 @ strcmp(s1,s2) == 0 <==>
146 @ (strlen(s1) == strlen(s2)
147 @ && \forall ℤ i; 0 <= i <= strlen(s1) ==> s1[i] == s2[i]);
148 @ }
149 @*/
150
151 /*@ axiomatic StrNCmp {
152 @ logic ℤ strncmp{L}(char *s1, char *s2, ℤ n)
153 @ reads s1[0..n-1], s2[0..n-1];
154 @
155 @ axiom strncmp_zero{L}:
156 @ \forall char *s1, *s2; \forall ℤ n;
157 @ strncmp(s1,s2,n) == 0 <==>
158 @ (strlen(s1) < n && strcmp(s1,s2) == 0
159 @ || \forall ℤ i; 0 <= i < n ==> s1[i] == s2[i]);
160 @ }
161 @*/
162
163 /*@ axiomatic StrChr {
164 @ logic 𝔹 strchr{L}(char *s, ℤ c)
165 @ reads s[0..strlen(s)];
166 @ // Returns [true] iff string [s] contains [c] (interpreted as char)
167 @
168 @ axiom strchr_def{L}:
169 @ \forall char *s; \forall ℤ c;
170 @ strchr(s,c) <==> \exists ℤ i; 0 <= i <= strlen(s) && s[i] == (char)c;
171 @ }
172 @*/
173
174 /*@ axiomatic WMemChr {
175 @ logic 𝔹 wmemchr{L}(wchar_t *s, wchar_t c, ℤ n)
176 @ reads s[0..n - 1];
177 @ // Returns [true] iff wide char array [s] contains wide character [c]
178 @
179 @ logic ℤ wmemchr_off{L}(wchar_t *s, wchar_t c, ℤ n)
180 @ reads s[0..n - 1];
181 @ // Returns the offset at which [c] appears in [s].
182 @
183 @ axiom wmemchr_def{L}:
184 @ \forall wchar_t *s; \forall wchar_t c; \forall ℤ n;
185 @ wmemchr(s,c,n) <==> \exists int i; 0 <= i < n && s[i] == c;
186 @ }
187 @*/
188
189 /*@ axiomatic WcsLen {
190 @ logic ℤ wcslen{L}(wchar_t *s)
191 @ reads s[0..];
192 @
193 @ axiom wcslen_pos_or_null{L}:
194 @ \forall wchar_t* s; \forall ℤ i;
195 @ (0 <= i
196 @ && (\forall ℤ j; 0 <= j < i ==> s[j] != L'\0')
197 @ && s[i] == L'\0') ==> wcslen(s) == i;
198 @
199 @ axiom wcslen_neg{L}:
200 @ \forall wchar_t* s;
201 @ (\forall ℤ i; 0 <= i ==> s[i] != L'\0')
202 @ ==> wcslen(s) < 0;
203 @
204 @ axiom wcslen_before_null{L}:
205 @ \forall wchar_t* s; \forall int i; 0 <= i < wcslen(s) ==> s[i] != L'\0';
206 @
207 @ axiom wcslen_at_null{L}:
208 @ \forall wchar_t* s; 0 <= wcslen(s) ==> s[wcslen(s)] == L'\0';
209 @
210 @ axiom wcslen_not_zero{L}:
211 @ \forall wchar_t* s; \forall int i;
212 @ 0 <= i <= wcslen(s) && s[i] != L'\0' ==> i < wcslen(s);
213 @
214 @ axiom wcslen_zero{L}:
215 @ \forall wchar_t* s; \forall int i;
216 @ 0 <= i <= wcslen(s) && s[i] == L'\0' ==> i == wcslen(s);
217 @
218 @ axiom wcslen_sup{L}:
219 @ \forall wchar_t* s; \forall int i;
220 @ 0 <= i && s[i] == L'\0' ==> 0 <= wcslen(s) <= i;
221 @
222 @ axiom wcslen_shift{L}:
223 @ \forall wchar_t* s; \forall int i;
224 @ 0 <= i <= wcslen(s) ==> wcslen(s+i) == wcslen(s)-i;
225 @
226 @ axiom wcslen_create{L}:
227 @ \forall wchar_t* s; \forall int i;
228 @ 0 <= i && s[i] == L'\0' ==> 0 <= wcslen(s) <= i;
229 @
230 @ axiom wcslen_create_shift{L}:
231 @ \forall wchar_t* s; \forall int i; \forall int k;
232 @ 0 <= k <= i && s[i] == L'\0' ==> 0 <= wcslen(s+k) <= i - k;
233 @ }
234 @*/
235
236 /*@ axiomatic WcsCmp {
237 @ logic ℤ wcscmp{L}(wchar_t *s1, wchar_t *s2)
238 @ reads s1[0..wcslen(s1)], s2[0..wcslen(s2)];
239 @
240 @ axiom wcscmp_zero{L}:
241 @ \forall wchar_t *s1, *s2;
242 @ wcscmp(s1,s2) == 0 <==>
243 @ (wcslen(s1) == wcslen(s2)
244 @ && \forall ℤ i; 0 <= i <= wcslen(s1) ==> s1[i] == s2[i]);
245 @ }
246 @*/
247
248 /*@ axiomatic WcsNCmp {
249 @ logic ℤ wcsncmp{L}(wchar_t *s1, wchar_t *s2, ℤ n)
250 @ reads s1[0..n-1], s2[0..n-1];
251 @
252 @ axiom wcsncmp_zero{L}:
253 @ \forall wchar_t *s1, *s2; \forall ℤ n;
254 @ wcsncmp(s1,s2,n) == 0 <==>
255 @ (wcslen(s1) < n && wcscmp(s1,s2) == 0
256 @ || \forall ℤ i; 0 <= i < n ==> s1[i] == s2[i]);
257 @ }
258 @*/
259
260 /*@ axiomatic WcsChr {
261 @ logic 𝔹 wcschr{L}(wchar_t *wcs, ℤ wc)
262 @ reads wcs[0..wcslen(wcs)];
263 @ // Returns [true] iff wide string [wcs] contains [wc]
264 @ //(interpreted as wchar_t)
265 @
266 @ axiom wcschr_def{L}:
267 @ \forall wchar_t *wcs; \forall ℤ wc;
268 @ wcschr(wcs,wc) <==> \exists ℤ i; 0 <= i <= wcslen(wcs)
269 @ && wcs[i] == (wchar_t)wc;
270 @ }
271 @*/
272
273 /*@ logic ℤ minimum(ℤ i, ℤ j) = i < j ? i : j;
274 @ logic ℤ maximum(ℤ i, ℤ j) = i < j ? j : i;
275 @*/
276
277 /*@ predicate valid_string{L}(char *s) =
278 @ 0 <= strlen(s) && \valid(s+(0..strlen(s)));
279 @
280 @ predicate valid_read_string{L}(char *s) =
281 @ 0 <= strlen(s) && \valid_read(s+(0..strlen(s)));
282 @
283 @ predicate valid_read_nstring{L}(char *s, ℤ n) =
284 @ (\valid_read(s+(0..n-1)) && \initialized(s+(0..n-1)))
285 @ || valid_read_string{L}(s);
286 @
287 @ predicate valid_string_or_null{L}(char *s) =
288 @ s == \null || valid_string(s);
289 @
290 @ predicate valid_wstring{L}(wchar_t *s) =
291 @ 0 <= wcslen(s) && \valid(s+(0..wcslen(s)));
292 @
293 @ predicate valid_read_wstring{L}(wchar_t *s) =
294 @ 0 <= wcslen(s) && \valid_read(s+(0..wcslen(s)));
295 @
296 @ predicate valid_read_nwstring{L}(wchar_t *s, ℤ n) =
297 @ (\valid_read(s+(0..n-1)) && \initialized(s+(0..n-1)))
298 @ || valid_read_wstring{L}(s);
299 @
300 @ predicate valid_wstring_or_null{L}(wchar_t *s) =
301 @ s == \null || valid_wstring(s);
302 @*/
303
304 __END_DECLS
305
306 #define FRAMA_C_PTR __declspec(valid)
307 #define FRAMA_C_ARRAY(n) __declspec(valid_range(0,n))
308 #define FRAMA_C_STRING __declspec(valid_string)
309 #define FRAMA_C_STRING_OR_NULL __declspec(valid_string_or_null)
310 #define FRAMA_C_WSTRING __declspec(valid_wstring)
311 #define FRAMA_C_WSTRING_OR_NULL __declspec(valid_wstring_or_null)
312
313 __POP_FC_STDLIB
314 #endif