Imported Upstream version 0.7.20
[platform/upstream/libsolv.git] / src / conda.c
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 *
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 *
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
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
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
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
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(&reg, buf, REG_EXTENDED | REG_NOSUB | (icase ? REG_ICASE : 0)))
242     {
243       solv_free(buf);
244       return 0;
245     }
246   r = regexec(&reg, evr, 0, NULL, 0);
247   regfree(&reg);
248   solv_free(buf);
249   return r == 0;
250 }
251
252 static int
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(&reg, buf, REG_EXTENDED | REG_NOSUB | (icase ? REG_ICASE : 0)))
271     {
272       solv_free(buf);
273       return 0;
274     }
275   r = regexec(&reg, evr, 0, NULL, 0);
276   regfree(&reg);
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
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
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
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
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
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
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
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       memmove(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