1 /* GNU Mailutils -- a suite of utilities for electronic mail
2 Copyright (C) 2017-2021 Free Software Foundation, Inc.
3
4 This library is free software; you can redistribute it and/or
5 modify it under the terms of the GNU Lesser General Public
6 License as published by the Free Software Foundation; either
7 version 3 of the License, or (at your option) any later version.
8
9 This library is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General
15 Public License along with this library. If not, see
16 <http://www.gnu.org/licenses/>. */
17
18 #include <stdlib.h>
19 #include <errno.h>
20 #include <mailutils/types.h>
21 #include <mailutils/locus.h>
22 #include <mailutils/error.h>
23
24 /* The line-tracker structure keeps track of the last N lines read from one
25 or more input files. For each line read it keeps the number of characters
26 in that line including the newline. This information is stored in a
27 cyclic stack of N elements (N >= 2). Top of stack always represents the
28 current line. For the purpose of line tracker, current line is the line
29 that is being visited, such that its final newline character has not yet
30 been seen. Once the newline is seen, the line is pushed on stack, and a
31 new current line is assumed.
32
33 Each input file is represented by a directory entry keeping its name,
34 the number of the first line that is stored in the tracker and the index of
35 that line in the cols stack. Entries form a doubly-linked list, with
36 head pointing to the most recent (current) source. When a new line is
37 being added to the stack which is full, its eldest entry is discarded
38 and re-assigned to that line; at the same time the directory of the
39 eldest source is updated accordingly. If the entry to be discarded
40 represents the only line of the source, the source is discarded.
41 */
42
43 struct source
44 {
45 char const *file_name; /* Name of the source file */
46 size_t idx; /* Index of the first element on stack */
47 unsigned line; /* Number of line corresponding to cols[idx] */
48 struct source *next, *prev;
49 };
50
51 struct mu_linetrack
52 {
53 struct source *s_head, *s_tail;
54 /* Directory of source files. Most recent one is
55 s_head */
56
57 size_t max_lines; /* Max. number of lines history kept by tracker (N) */
58 size_t head; /* Index of the eldest element on stack */
59 size_t tos; /* Index of the most recent element on stack
60 (< max_lines) */
61 unsigned *cols; /* Cyclic stack or character counts.
62 Number of characters in line (head + n) is
63 cols[head + n] (0 <= n <= tos). */
64 };
65
66 static inline size_t
trk_incr(struct mu_linetrack * trk,size_t a)67 trk_incr (struct mu_linetrack *trk, size_t a)
68 {
69 return (a + 1) % trk->max_lines;
70 }
71
72 static inline size_t
trk_decr(struct mu_linetrack * trk,size_t a)73 trk_decr (struct mu_linetrack *trk, size_t a)
74 {
75 return (a + trk->max_lines - 1) % trk->max_lines;
76 }
77
78 static inline unsigned
count_lines(mu_linetrack_t trk,size_t from)79 count_lines (mu_linetrack_t trk, size_t from)
80 {
81 return (trk->tos + trk->max_lines - from) % trk->max_lines + 1;
82 }
83
84 #ifndef SIZE_MAX
85 # define SIZE_MAX (~((size_t)0))
86 #endif
87
88 static int
count_chars(struct mu_linetrack * trk,size_t i,size_t * ret)89 count_chars (struct mu_linetrack *trk, size_t i, size_t *ret)
90 {
91 size_t nch = 0;
92
93 while (1)
94 {
95 unsigned n = trk->cols[i];
96 if (SIZE_MAX - nch < n)
97 return ERANGE;
98 nch += n;
99 if (i == trk->tos)
100 break;
101 i = trk_incr (trk, i);
102 }
103 *ret = nch;
104 return 0;
105 }
106
107 static size_t
count_files(struct mu_linetrack * trk)108 count_files (struct mu_linetrack *trk)
109 {
110 struct source *sp;
111 size_t n = 0;
112 for (sp = trk->s_head; sp; sp = sp->next)
113 n++;
114 return n;
115 }
116
117 static void
del_source(mu_linetrack_t trk,struct source * sp)118 del_source (mu_linetrack_t trk, struct source *sp)
119 {
120 if (sp->prev)
121 sp->prev->next = sp->next;
122 else
123 trk->s_head = sp->next;
124 if (sp->next)
125 sp->next->prev = sp->prev;
126 else
127 trk->s_tail = sp->prev;
128 mu_ident_deref (sp->file_name);
129 free (sp);
130 }
131
132 static inline unsigned *
push(mu_linetrack_t trk)133 push (mu_linetrack_t trk)
134 {
135 trk->tos = trk_incr (trk, trk->tos);
136 if (trk->tos == trk->head)
137 {
138 trk->head = trk_incr (trk, trk->head);
139 trk->s_tail->idx = trk->head;
140 trk->s_tail->line++;
141 }
142 if (trk->s_tail->prev && trk->s_tail->idx == trk->s_tail->prev->idx)
143 del_source (trk, trk->s_tail);
144 trk->cols[trk->tos] = 0;
145 return &trk->cols[trk->tos];
146 }
147
148 static inline unsigned *
pop(mu_linetrack_t trk)149 pop (mu_linetrack_t trk)
150 {
151 if (trk->tos == trk->head)
152 return NULL;
153 if (trk->tos == trk->s_head->idx)
154 del_source (trk, trk->s_head);
155
156 trk->tos = trk_decr (trk, trk->tos);
157
158 return &trk->cols[trk->tos];
159 }
160
161 int
mu_linetrack_origin(mu_linetrack_t trk,struct mu_locus_point const * pt)162 mu_linetrack_origin (mu_linetrack_t trk, struct mu_locus_point const *pt)
163 {
164 int rc;
165 struct source *sp;
166 char const *file_name;
167
168 if (!trk || !pt || pt->mu_line == 0)
169 return EINVAL;
170 if (pt->mu_file)
171 file_name = pt->mu_file;
172 else if (trk->s_head)
173 file_name = trk->s_head->file_name;
174 else
175 return EINVAL;
176 sp = malloc (sizeof *sp);
177 if (!sp)
178 return errno;
179 rc = mu_ident_ref (file_name, &sp->file_name);
180 if (rc)
181 {
182 free (sp);
183 return rc;
184 }
185
186 if (trk->cols[trk->tos])
187 push (trk);
188
189 sp->idx = trk->tos;
190 sp->line = pt->mu_line;
191 trk->cols[sp->idx] = pt->mu_col;
192
193 sp->prev = NULL;
194 sp->next = trk->s_head;
195 if (trk->s_head)
196 trk->s_head->prev = sp;
197 else
198 trk->s_tail = sp;
199 trk->s_head = sp;
200 return 0;
201 }
202
203 int
mu_linetrack_create(mu_linetrack_t * ret,char const * file_name,size_t max_lines)204 mu_linetrack_create (mu_linetrack_t *ret,
205 char const *file_name, size_t max_lines)
206 {
207 int rc;
208 struct mu_linetrack *trk;
209 struct mu_locus_point pt;
210
211 trk = malloc (sizeof *trk);
212 if (!trk)
213 return errno;
214
215 trk->cols = calloc (max_lines, sizeof (trk->cols[0]));
216 if (!trk->cols)
217 {
218 rc = errno;
219 free (trk);
220 return rc;
221 }
222 trk->s_head = trk->s_tail = NULL;
223
224 if (max_lines < 2)
225 max_lines = 2;
226 trk->max_lines = max_lines;
227 trk->head = 0;
228 trk->tos = 0;
229 trk->cols[0] = 0;
230
231 pt.mu_file = file_name;
232 pt.mu_line = 1;
233 pt.mu_col = 0;
234 rc = mu_linetrack_origin (trk, &pt);
235 if (rc)
236 {
237 free (trk->cols);
238 free (trk);
239 return rc;
240 }
241
242 *ret = trk;
243 return 0;
244 }
245
246 int
mu_linetrack_rebase(mu_linetrack_t trk,struct mu_locus_point const * pt)247 mu_linetrack_rebase (mu_linetrack_t trk, struct mu_locus_point const *pt)
248 {
249 char const *file_name;
250 int rc = mu_ident_ref (pt->mu_file, &file_name);
251 if (rc)
252 return rc;
253 mu_ident_deref (trk->s_head->file_name);
254 trk->s_head->file_name = file_name;
255 trk->s_head->line = pt->mu_line;
256 trk->cols[trk->s_head->idx] = pt->mu_col;
257 return 0;
258 }
259
260 void
mu_linetrack_free(mu_linetrack_t trk)261 mu_linetrack_free (mu_linetrack_t trk)
262 {
263 if (trk)
264 {
265 while (trk->s_head)
266 del_source (trk, trk->s_head);
267 free (trk->cols);
268 free (trk);
269 }
270 }
271
272 void
mu_linetrack_destroy(mu_linetrack_t * trk)273 mu_linetrack_destroy (mu_linetrack_t *trk)
274 {
275 if (trk)
276 {
277 mu_linetrack_free (*trk);
278 *trk = NULL;
279 }
280 }
281
282 int
mu_linetrack_stat(struct mu_linetrack * trk,struct mu_linetrack_stat * st)283 mu_linetrack_stat (struct mu_linetrack *trk, struct mu_linetrack_stat *st)
284 {
285 if (count_chars (trk, trk->head, &st->n_chars))
286 return ERANGE;
287 st->n_files = count_files (trk);
288 st->n_lines = count_lines (trk, trk->head);
289 return 0;
290 }
291
292 int
mu_linetrack_at_bol(struct mu_linetrack * trk)293 mu_linetrack_at_bol (struct mu_linetrack *trk)
294 {
295 return trk->cols[trk->tos] == 0;
296 }
297
298 void
mu_linetrack_advance(struct mu_linetrack * trk,struct mu_locus_range * loc,char const * text,size_t leng)299 mu_linetrack_advance (struct mu_linetrack *trk,
300 struct mu_locus_range *loc,
301 char const *text, size_t leng)
302 {
303 unsigned *ptr;
304
305 if (text == NULL || leng == 0)
306 return;
307
308 mu_locus_point_set_file (&loc->beg, trk->s_head->file_name);
309 mu_locus_point_set_file (&loc->end, trk->s_head->file_name);
310 loc->beg.mu_line =
311 trk->s_head->line + count_lines (trk, trk->s_head->idx) - 1;
312 ptr = &trk->cols[trk->tos];
313 loc->beg.mu_col = *ptr + 1;
314 while (leng--)
315 {
316 (*ptr)++;
317 if (*text == '\n')
318 ptr = push (trk);
319 text++;
320 }
321
322 loc->end.mu_line =
323 trk->s_head->line + count_lines (trk, trk->s_head->idx) - 1;
324 if (*ptr)
325 {
326 loc->end.mu_col = *ptr;
327 }
328 else
329 {
330 /* Text ends with a newline. Keep the previous line number. */
331 loc->end.mu_line--;
332 loc->end.mu_col = trk->cols[trk_decr (trk, trk->tos)] - 1;
333 if (loc->end.mu_col + 1 == loc->beg.mu_col)
334 {
335 /* This happens if the previous line contained only newline. */
336 loc->beg.mu_col = loc->end.mu_col;
337 }
338 }
339 }
340
341 int
mu_linetrack_locus(struct mu_linetrack * trk,struct mu_locus_point * lp)342 mu_linetrack_locus (struct mu_linetrack *trk, struct mu_locus_point *lp)
343 {
344 int rc = mu_locus_point_set_file (lp, trk->s_head->file_name);
345 if (rc == 0)
346 {
347 lp->mu_line =
348 trk->s_head->line + count_lines (trk, trk->s_head->idx) - 1;
349 lp->mu_col = trk->cols[trk->tos];
350 }
351 return rc;
352 }
353
354 int
mu_linetrack_retreat(struct mu_linetrack * trk,size_t n)355 mu_linetrack_retreat (struct mu_linetrack *trk, size_t n)
356 {
357 size_t nch;
358
359 if (count_chars (trk, trk->head, &nch))
360 return ERANGE;
361 if (n > nch)
362 return ERANGE;
363 else
364 {
365 unsigned *ptr = &trk->cols[trk->tos];
366 while (n--)
367 {
368 if (*ptr == 0)
369 {
370 ptr = pop (trk);
371 if (!ptr || *ptr == 0)
372 {
373 mu_error ("%s:%d: INTERNAL ERROR: out of pop back\n",
374 __FILE__, __LINE__);
375 return ERANGE;
376 }
377 }
378 --*ptr;
379 }
380 }
381 return 0;
382 }
383
384
385