1 /*
2 * Copyright (c) 2019, SUSE LLC
3 *
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
6 */
7
8 /*
9 * conda.c
10 *
11 * evr comparison and package matching for conda
12 */
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <stdarg.h>
17 #include <unistd.h>
18 #include <string.h>
19 #include <sys/types.h>
20 #include <regex.h>
21
22 #include "pool.h"
23 #include "repo.h"
24 #include "util.h"
25 #include "conda.h"
26
27 #ifdef _WIN32
28 #include "strfncs.h"
29 #endif
30
31 static const char *
endseg(const char * seg,const char * end)32 endseg(const char *seg, const char *end)
33 {
34 for (; seg < end; seg++)
35 if (*seg == '.' || *seg == '-' || *seg == '_')
36 break;
37 return seg;
38 }
39
40 static const char *
endpart(const char * seg,const char * end)41 endpart(const char *seg, const char *end)
42 {
43 if (seg == end)
44 return seg;
45 if (*seg >= '0' && *seg <= '9')
46 {
47 for (seg++; seg < end; seg++)
48 if (!(*seg >= '0' && *seg <= '9'))
49 break;
50 }
51 else if (*seg == '*')
52 {
53 for (seg++; seg < end; seg++)
54 if (*seg != '*')
55 break;
56 }
57 else
58 {
59 for (seg++; seg < end; seg++)
60 if ((*seg >= '0' && *seg <= '9') || *seg == '*')
61 break;
62 }
63 return seg;
64 }
65
66 /* C implementation of the version comparison code in conda/models/version.py */
67 /* startswith == 1 : check if s1 starts with s2 */
68 static int
solv_vercmp_conda(const char * s1,const char * q1,const char * s2,const char * q2,int startswith)69 solv_vercmp_conda(const char *s1, const char *q1, const char *s2, const char *q2, int startswith)
70 {
71 const char *s1p, *s2p;
72 const char *s1e, *s2e;
73 int r, isfirst;
74 const char *q2end = 0;
75
76 if (startswith)
77 {
78 for (q2end = q2; q2end > s2; q2end--)
79 if (q2end[-1] != '.' && q2end[-1] != '-' && q2end[-1] != '_')
80 break;
81 }
82 for (;;)
83 {
84 while (s1 < q1 && (*s1 == '.' || *s1 == '-' || *s1 == '_'))
85 s1++;
86 while (s2 < q2 && (*s2 == '.' || *s2 == '-' || *s2 == '_'))
87 s2++;
88 if (s1 == q1 && s2 == q2)
89 return 0;
90 if (startswith && s2 == q2)
91 return 0;
92 /* find end of component */
93 s1e = endseg(s1, q1);
94 s2e = endseg(s2, q2);
95
96 for (isfirst = 1; ; isfirst = 0)
97 {
98 if (s1 == s1e && s2 == s2e)
99 break;
100 if (s2 == q2end)
101 return 0;
102 s1p = endpart(s1, s1e);
103 s2p = endpart(s2, s2e);
104 /* prepend 0 if not numeric */
105 if (isfirst)
106 {
107 if (s1p != s1 && !(*s1 >= '0' && *s1 <= '9'))
108 s1p = s1;
109 if (s2p != s2 && !(*s2 >= '0' && *s2 <= '9'))
110 s2p = s2;
111 }
112 /* special case "post" */
113 if (s1p - s1 == 4 && !strncasecmp(s1, "post", 4))
114 {
115 if (s2p - s2 == 4 && !strncasecmp(s2, "post", 4))
116 {
117 s1 = s1p;
118 s2 = s2p;
119 continue;
120 }
121 return 1;
122 }
123 if (s2p - s2 == 4 && !strncasecmp(s2, "post", 4))
124 return -1;
125
126 if (isfirst || ((s1 == s1p || (*s1 >= '0' && *s1 <= '9')) && (s2 == s2p || (*s2 >= '0' && *s2 <= '9'))))
127 {
128 /* compare numbers */
129 while (s1 < s1p && *s1 == '0')
130 s1++;
131 while (s2 < s2p && *s2 == '0')
132 s2++;
133 if (s1p - s1 < s2p - s2)
134 return -1;
135 if (s1p - s1 > s2p - s2)
136 return 1;
137 r = s1p - s1 ? strncmp(s1, s2, s1p - s1) : 0;
138 if (r)
139 return r;
140 }
141 else if (s1 == s1p || (*s1 >= '0' && *s1 <= '9'))
142 return 1;
143 else if (s2 == s2p || (*s2 >= '0' && *s2 <= '9'))
144 return -1;
145 else
146 {
147 /* special case "dev" */
148 if (*s2 != '*' && s1p - s1 == 3 && !strncasecmp(s1, "dev", 3))
149 {
150 if (s2p - s2 == 3 && !strncasecmp(s2, "dev", 3))
151 {
152 s1 = s1p;
153 s2 = s2p;
154 continue;
155 }
156 return -1;
157 }
158 if (*s1 != '*' && s2p - s2 == 3 && !strncasecmp(s2, "dev", 3))
159 return 1;
160 /* compare strings */
161 r = s2p - s2 > s1p - s1 ? s1p - s1 : s2p - s2;
162 if (r)
163 r = strncasecmp(s1, s2, r);
164 if (r)
165 return r;
166 if (s1p - s1 < s2p - s2)
167 return -1;
168 if (s1p - s1 > s2p - s2)
169 return 1;
170 }
171 s1 = s1p;
172 s2 = s2p;
173 }
174 }
175 }
176
177 static int
pool_evrcmp_conda_int(const char * evr1,const char * evr1e,const char * evr2,const char * evr2e,int startswith)178 pool_evrcmp_conda_int(const char *evr1, const char *evr1e, const char *evr2, const char *evr2e, int startswith)
179 {
180 static char zero[2] = {'0', 0};
181 const char *s1, *s2;
182 const char *r1, *r2;
183 int r;
184
185 /* split and compare epoch */
186 for (s1 = evr1; s1 < evr1e && *s1 >= '0' && *s1 <= '9'; s1++)
187 ;
188 for (s2 = evr2; s2 < evr2e && *s2 >= '0' && *s2 <= '9'; s2++)
189 ;
190 if (s1 == evr1 || s1 == evr1e || *s1 != '!')
191 s1 = 0;
192 if (s2 == evr1 || s2 == evr2e || *s2 != '!')
193 s2 = 0;
194 if (s1 || s2)
195 {
196 r = solv_vercmp_conda(s1 ? evr1 : zero, s1 ? s1 : zero + 1,
197 s2 ? evr2 : zero, s2 ? s2 : zero + 1, 0);
198 if (r)
199 return r;
200 if (s1)
201 evr1 = s1 + 1;
202 if (s2)
203 evr2 = s2 + 1;
204 }
205 /* split into version/localversion */
206 for (s1 = evr1, r1 = 0; s1 < evr1e; s1++)
207 if (*s1 == '+')
208 r1 = s1;
209 for (s2 = evr2, r2 = 0; s2 < evr2e; s2++)
210 if (*s2 == '+')
211 r2 = s2;
212 r = solv_vercmp_conda(evr1, r1 ? r1 : s1, evr2, r2 ? r2 : s2, r2 ? 0 : startswith);
213 if (r)
214 return r;
215 if ((!r2 && startswith) || (!r1 && !r2))
216 return 0;
217 if (!r1 && r2)
218 return -1;
219 if (r1 && !r2)
220 return 1;
221 return solv_vercmp_conda(r1 + 1, s1, r2 + 1, s2, startswith);
222 }
223
224 int
pool_evrcmp_conda(const Pool * pool,const char * evr1,const char * evr2,int mode)225 pool_evrcmp_conda(const Pool *pool, const char *evr1, const char *evr2, int mode)
226 {
227 if (evr1 == evr2)
228 return 0;
229 return pool_evrcmp_conda_int(evr1, evr1 + strlen(evr1), evr2, evr2 + strlen(evr2), 0);
230 }
231
232 static int
regexmatch(const char * evr,const char * version,size_t versionlen,int icase)233 regexmatch(const char *evr, const char *version, size_t versionlen, int icase)
234 {
235 regex_t reg;
236 char *buf = solv_malloc(versionlen + 1);
237 int r;
238
239 memcpy(buf, version, versionlen);
240 buf[versionlen] = 0;
241 if (regcomp(®, buf, REG_EXTENDED | REG_NOSUB | (icase ? REG_ICASE : 0)))
242 {
243 solv_free(buf);
244 return 0;
245 }
246 r = regexec(®, evr, 0, NULL, 0);
247 regfree(®);
248 solv_free(buf);
249 return r == 0;
250 }
251
252 static int
globmatch(const char * evr,const char * version,size_t versionlen,int icase)253 globmatch(const char *evr, const char *version, size_t versionlen, int icase)
254 {
255 regex_t reg;
256 char *buf = solv_malloc(2 * versionlen + 3);
257 size_t i, j;
258 int r;
259
260 buf[0] = '^';
261 j = 1;
262 for (i = 0, j = 1; i < versionlen; i++)
263 {
264 if (version[i] == '.' || version[i] == '+' || version[i] == '*')
265 buf[j++] = version[i] == '*' ? '.' : '\\';
266 buf[j++] = version[i];
267 }
268 buf[j++] = '$';
269 buf[j] = 0;
270 if (regcomp(®, buf, REG_EXTENDED | REG_NOSUB | (icase ? REG_ICASE : 0)))
271 {
272 solv_free(buf);
273 return 0;
274 }
275 r = regexec(®, evr, 0, NULL, 0);
276 regfree(®);
277 solv_free(buf);
278 return r == 0;
279 }
280
281 /* return true if solvable s matches the version */
282 /* see conda/models/version.py */
283 static int
solvable_conda_matchversion_single(Solvable * s,const char * version,size_t versionlen)284 solvable_conda_matchversion_single(Solvable *s, const char *version, size_t versionlen)
285 {
286 const char *evr;
287 size_t i;
288 int r;
289
290 if (versionlen == 0 || (versionlen == 1 && *version == '*'))
291 return 1; /* matches every version */
292 evr = pool_id2str(s->repo->pool, s->evr);
293 if (versionlen >= 2 && version[0] == '^' && version[versionlen - 1] == '$')
294 return regexmatch(evr, version, versionlen, 0);
295 if (version[0] == '=' || version[0] == '<' || version[0] == '>' || version[0] == '!' || version[0] == '~')
296 {
297 int flags = 0;
298 int oplen;
299 if (version[0] == '=')
300 flags = version[1] == '=' ? REL_EQ : 8;
301 else if (version[0] == '!' || version[0] == '~')
302 {
303 if (version[1] != '=')
304 return 0;
305 flags = version[0] == '!' ? REL_LT | REL_GT : 9;
306 }
307 else if (version[0] == '<' || version[0] == '>')
308 {
309 flags = version[0] == '<' ? REL_LT : REL_GT;
310 if (version[1] == '=')
311 flags |= REL_EQ;
312 }
313 else
314 return 0;
315 oplen = flags == 8 || flags == REL_LT || flags == REL_GT ? 1 : 2;
316 if (versionlen < oplen + 1)
317 return 0;
318 version += oplen;
319 versionlen -= oplen;
320 if (version[0] == '=' || version[0] == '<' || version[0] == '>' || version[0] == '!' || version[0] == '~')
321 return 0; /* bad chars after op */
322 if (versionlen >= 2 && version[versionlen - 2] == '.' && version[versionlen - 1] == '*')
323 {
324 if (flags == 8 || flags == (REL_GT | REL_EQ))
325 versionlen -= 2;
326 else if (flags == (REL_LT | REL_GT))
327 {
328 versionlen -= 2;
329 flags = 10;
330 }
331 else
332 return 0;
333 }
334 if (flags < 8)
335 {
336 /* we now have an op and a version */
337 r = pool_evrcmp_conda_int(evr, evr + strlen(evr), version, version + versionlen, 0);
338 if (r < 0)
339 return (flags & REL_LT) ? 1 : 0;
340 if (r == 0)
341 return (flags & REL_EQ) ? 1 : 0;
342 if (r > 0)
343 return (flags & REL_GT) ? 1 : 0;
344 return 0;
345 }
346 if (flags == 8 || flags == 10) /* startswith, not-startswith */
347 {
348 r = pool_evrcmp_conda_int(evr, evr + strlen(evr), version, version + versionlen, 1);
349 return flags == 8 ? r == 0 : r != 0;
350 }
351 else if (flags == 9) /* compatible release op */
352 {
353 r = pool_evrcmp_conda_int(evr, evr + strlen(evr), version, version + versionlen, 0);
354 if (r < 0)
355 return 0;
356 /* split off last component */
357 while (versionlen > 0 && version[versionlen - 1] != '.')
358 versionlen--;
359 if (versionlen < 2)
360 return 0;
361 versionlen--;
362 r = pool_evrcmp_conda_int(evr, evr + strlen(evr), version, version + versionlen, 1);
363 return r == 0 ? 1 : 0;
364 }
365 return 0;
366 }
367
368 /* do we have a '*' in the version */
369 for (i = 0; i < versionlen; i++)
370 if (version[i] == '*')
371 {
372 for (i++; i < versionlen; i++)
373 if (version[i] != '*')
374 break;
375 if (i < versionlen)
376 return globmatch(evr, version, versionlen, 1);
377 }
378
379 if (versionlen > 1 && version[versionlen - 1] == '*')
380 {
381 /* startswith */
382 while (versionlen > 0 && version[versionlen - 1] == '*')
383 versionlen--;
384 while (versionlen > 0 && version[versionlen - 1] == '.')
385 versionlen--;
386 r = pool_evrcmp_conda_int(evr, evr + strlen(evr), version, version + versionlen, 1);
387 return r == 0 ? 1 : 0;
388 }
389 /* do we have a '@' in the version? */
390 for (i = 0; i < versionlen; i++)
391 if (version[i] == '@')
392 return strncmp(evr, version, versionlen) == 0 && evr[versionlen] == 0;
393 r = pool_evrcmp_conda_int(evr, evr + strlen(evr), version, version + versionlen, 0);
394 return r == 0 ? 1 : 0;
395 }
396
397 static int
solvable_conda_matchversion_rec(Solvable * s,const char ** versionp,const char * versionend)398 solvable_conda_matchversion_rec(Solvable *s, const char **versionp, const char *versionend)
399 {
400 const char *version = *versionp;
401 int v, vor = 0, vand = -1; /* -1: doing OR, 0,1: doing AND */
402
403 if (version == versionend)
404 return -1;
405 for (;;)
406 {
407 if (*version == '(')
408 {
409 version++;
410 v = solvable_conda_matchversion_rec(s, &version, versionend);
411 if (v == -1 || version == versionend || *version != ')')
412 return -1;
413 version++;
414 }
415 else if (*version == ')' || *version == '|' || *version == ',')
416 return -1;
417 else
418 {
419 const char *vstart = version;
420 while (version < versionend && *version != '(' && *version != ')' && *version != '|' && *version != ',')
421 version++;
422 if (vand >= 0 ? !vand : vor)
423 v = 0; /* no need to call expensive matchversion if the result does not matter */
424 else
425 v = solvable_conda_matchversion_single(s, vstart, version - vstart) ? 1 : 0;
426 }
427 if (version == versionend || *version == ')')
428 {
429 *versionp = version;
430 return vor | (vand >= 0 ? (vand & v) : v);
431 }
432 if (*version == ',')
433 vand = vand >= 0 ? (vand & v) : v;
434 else if (*version == '|')
435 {
436 vor |= vand >= 0 ? (vand & v) : v;
437 vand = -1;
438 }
439 else
440 return -1;
441 version++;
442 }
443 }
444
445 static int
solvable_conda_matchbuild(Solvable * s,const char * build,const char * buildend)446 solvable_conda_matchbuild(Solvable *s, const char *build, const char *buildend)
447 {
448 const char *bp;
449 const char *flavor = solvable_lookup_str(s, SOLVABLE_BUILDFLAVOR);
450
451 if (!flavor)
452 flavor = "";
453 if (build == buildend)
454 return *flavor ? 0 : 1;
455 if (build + 1 == buildend && *build == '*')
456 return 1;
457 if (*build == '^' && buildend[-1] == '$')
458 return regexmatch(flavor, build, buildend - build, 0);
459 for (bp = build; bp < buildend; bp++)
460 if (*bp == '*')
461 return globmatch(flavor, build, buildend - build, 0);
462 return strncmp(flavor, build, buildend - build) == 0 && flavor[buildend - build] == 0 ? 1 : 0;
463 }
464
465 /* return true if solvable s matches the version */
466 /* see conda/models/match_spec.py */
467 int
solvable_conda_matchversion(Solvable * s,const char * version)468 solvable_conda_matchversion(Solvable *s, const char *version)
469 {
470 const char *build, *versionend;
471 int r;
472 /* split off build */
473 if ((build = strchr(version, ' ')) != 0)
474 {
475 versionend = build++;
476 while (*build == ' ')
477 build++;
478 }
479 else
480 versionend = version + strlen(version);
481 r = solvable_conda_matchversion_rec(s, &version, versionend);
482 if (r != 1 || version != versionend)
483 return 0;
484 if (build && !solvable_conda_matchbuild(s, build, build + strlen(build)))
485 return 0;
486 return r;
487 }
488
489 static Id
pool_addrelproviders_conda_slow(Pool * pool,const char * namestr,Id evr,Queue * plist,int mode)490 pool_addrelproviders_conda_slow(Pool *pool, const char *namestr, Id evr, Queue *plist, int mode)
491 {
492 size_t namestrlen = strlen(namestr);
493 const char *evrstr = evr == 0 || evr == 1 ? 0 : pool_id2str(pool, evr);
494 Id p;
495
496 FOR_POOL_SOLVABLES(p)
497 {
498 Solvable *s = pool->solvables + p;
499 if (!pool_installable(pool, s))
500 continue;
501 if (mode == 1 && !globmatch(pool_id2str(pool, s->name), namestr, namestrlen, 1))
502 continue;
503 if (mode == 2 && !regexmatch(pool_id2str(pool, s->name), namestr, namestrlen, 1))
504 continue;
505 if (!evrstr || solvable_conda_matchversion(s, evrstr))
506 queue_push(plist, p);
507 }
508 return 0;
509 }
510
511 /* called from pool_addrelproviders, plist is an empty queue
512 * it can either return an offset into the whatprovides array
513 * or fill the plist queue and return zero */
514 Id
pool_addrelproviders_conda(Pool * pool,Id name,Id evr,Queue * plist)515 pool_addrelproviders_conda(Pool *pool, Id name, Id evr, Queue *plist)
516 {
517 const char *namestr = pool_id2str(pool, name), *np;
518 size_t l, nuc = 0;
519 Id wp, p, *pp;
520
521 /* is this a regex? */
522 if (*namestr && *namestr == '^')
523 {
524 l = strlen(namestr);
525 if (namestr[l - 1] == '$')
526 return pool_addrelproviders_conda_slow(pool, namestr, evr, plist, 2);
527 }
528 /* is this '*'? */
529 if (*namestr && *namestr == '*' && namestr[1] == 0)
530 return pool_addrelproviders_conda_slow(pool, namestr, evr, plist, 0);
531 /* does the string contain '*' or uppercase? */
532 for (np = namestr; *np; np++)
533 {
534 if (*np == '*')
535 return pool_addrelproviders_conda_slow(pool, namestr, evr, plist, 1);
536 else if (*np >= 'A' && *np <= 'Z')
537 nuc++;
538 }
539 if (nuc)
540 {
541 char *nbuf = solv_strdup(namestr), *nbufp;
542 for (nbufp = nbuf; *nbufp; nbufp++)
543 *nbufp = *nbufp >= 'A' && *nbufp <= 'Z' ? *nbufp + ('a' - 'A') : *nbufp;
544 name = pool_str2id(pool, nbuf, 0);
545 wp = name ? pool_whatprovides(pool, name) : 0;
546 solv_free(nbuf);
547 }
548 else
549 wp = pool_whatprovides(pool, name);
550 if (wp && evr && evr != 1)
551 {
552 const char *evrstr = pool_id2str(pool, evr);
553 pp = pool->whatprovidesdata + wp;
554 while ((p = *pp++) != 0)
555 {
556 if (solvable_conda_matchversion(pool->solvables + p, evrstr))
557 queue_push(plist, p);
558 else
559 wp = 0;
560 }
561 }
562 return wp;
563 }
564
565 /* create a CONDA_REL relation from a matchspec */
566 Id
pool_conda_matchspec(Pool * pool,const char * name)567 pool_conda_matchspec(Pool *pool, const char *name)
568 {
569 const char *p2;
570 char *name2;
571 char *p, *pp;
572 char *build, *buildend, *version, *versionend;
573 Id nameid, evrid;
574 int haveglob = 0;
575
576 /* ignore channel and namespace for now */
577 if ((p2 = strrchr(name, ':')))
578 name = p2 + 1;
579 name2 = solv_strdup(name);
580 /* find end of name */
581 for (p = name2; *p && *p != ' ' && *p != '=' && *p != '<' && *p != '>' && *p != '!' && *p != '~'; p++)
582 {
583 if (*p >= 'A' && *p <= 'Z')
584 *(char *)p += 'a' - 'A'; /* lower case the name */
585 else if (*p == '*')
586 haveglob = 1;
587 }
588 if (p == name2)
589 {
590 solv_free(name2);
591 return 0; /* error: empty package name */
592 }
593 nameid = pool_strn2id(pool, name2, p - name2, 1);
594 while (*p == ' ')
595 p++;
596 if (!*p)
597 {
598 if (*name2 != '^' && !haveglob)
599 {
600 solv_free(name2);
601 return nameid; /* return a simple dependency if no glob/regex */
602 }
603 evrid = pool_str2id(pool, "*", 1);
604 solv_free(name2);
605 return pool_rel2id(pool, nameid, evrid, REL_CONDA, 1);
606 }
607 /* have version */
608 version = p;
609 versionend = p + strlen(p);
610 while (versionend > version && versionend[-1] == ' ')
611 versionend--;
612 build = buildend = 0;
613 /* split of build */
614 p = versionend;
615 for (;;)
616 {
617 while (p > version && p[-1] != ' ' && p[-1] != '-' && p[-1] != '=' && p[-1] != ',' && p[-1] != '|' && p[-1] != '<' && p[-1] != '>' && p[-1] != '~')
618 p--;
619 if (p <= version + 1 || (p[-1] != ' ' && p[-1] != '='))
620 break; /* no build */
621 /* check char before delimiter */
622 if (p[-2] == '=' || p[-2] == '!' || p[-2] == '|' || p[-2] == ',' || p[-2] == '<' || p[-2] == '>' || p[-2] == '~')
623 {
624 /* illegal combination */
625 if (p[-1] == ' ')
626 {
627 p--;
628 continue; /* special case space: it may be in the build */
629 }
630 break; /* no build */
631 }
632 if (p < versionend)
633 {
634 build = p;
635 buildend = versionend;
636 versionend = p - 1;
637 }
638 break;
639 }
640 /* do weird version translation */
641 if (versionend > version && version[0] == '=')
642 {
643 if (versionend - version >= 2 && version[1] == '=')
644 {
645 if (!build)
646 version += 2;
647 }
648 else if (build)
649 version += 1;
650 else
651 {
652 for (p = version + 1; p < versionend; p++)
653 if (*p == '=' || *p == ',' || *p == '|')
654 break;
655 if (p == versionend)
656 {
657 memmove(version, version + 1, versionend - version - 1);
658 versionend[-1] = '*';
659 }
660 }
661 }
662 #if 0
663 printf("version: >%.*s<\n", (int)(versionend - version), version);
664 if (build) printf("build: >%.*s<\n", (int)(buildend - build), build);
665 #endif
666 /* strip spaces from version */
667 for (p = pp = version; pp < versionend; pp++)
668 if (*pp != ' ')
669 *p++ = *pp;
670 if (build)
671 {
672 *p++ = ' ';
673 memcpy(p, build, buildend - build);
674 p += buildend - build;
675 }
676 evrid = pool_strn2id(pool, version, p - version, 1);
677 solv_free(name2);
678 return pool_rel2id(pool, nameid, evrid, REL_CONDA, 1);
679 }
680
681