Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is to exceed 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - msfarey.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 24988-2584e74448) Lines: 184 190 96.8 %
Date: 2020-01-26 05:57:03 Functions: 17 17 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000, 2012  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : 
      17             : static long
      18       16611 : conginlist(GEN L, GEN g, void *E, long (*in)(void *, GEN ))
      19             : {
      20       16611 :   pari_sp av = avma;
      21       16611 :   long i, l = lg(L);
      22       16611 :   GEN gi = ginv(g);
      23      857115 :   for (i = 1; i < l; i++)
      24      854798 :     if (in(E, gmul(gel(L,i), gi))) break;
      25       16611 :   return gc_long(av, i);
      26             : }
      27             : 
      28             : static GEN
      29       22358 : normalise(GEN M)
      30             : {
      31       22358 :   long sd = signe(gcoeff(M,2,2));
      32       22358 :   if (sd < 0 || (!sd && signe(gcoeff(M,1,2)) < 0)) M = ZM_neg(M);
      33       22358 :   return M;
      34             : }
      35             : 
      36             : static void
      37        3619 : filln(GEN V, long n, long a, long c)
      38             : {
      39             :   long i, j;
      40       16555 :   for (j = a + 1, i = 1; i < n; i++)
      41             :   { /* j != a (mod n) */
      42       12936 :     gel(V,i) = mkvecsmall2(c, j);
      43       12936 :     if (++j > n) j = 1;
      44             :   }
      45        3619 : }
      46             : /* set v[k+1..k+n-1] or (k == l) append to v; 0 <= a < n */
      47             : static GEN
      48        3619 : vec_insertn(GEN v, long n, long k, long a, long c)
      49             : {
      50        3619 :   long i, j, l = lg(v), L = l + n-1;
      51        3619 :   GEN V = cgetg(L, t_VEC);
      52        3619 :   if (k == l)
      53             :   {
      54           0 :     for (i = 1; i < l; i++) gel(V,i) = gel(v,i);
      55           0 :     filln(V + i-1, n, a, c);
      56             :   }
      57             :   else
      58             :   {
      59        3619 :     for (i = 1; i <= k; i++) gel(V,i) = gel(v,i);
      60        3619 :     filln(V + i-1, n, a, c);
      61        3619 :     i += n - 1;
      62        3619 :     for (j = k + 1; j < l; j++) gel(V,i++) = gel(v,j);
      63             :   }
      64        3619 :   return V;
      65             : }
      66             : /* append the [c,L[i]], i=1..#L to v */
      67             : static GEN
      68        7238 : vec_appendL(GEN v, GEN L, long c)
      69             : {
      70        7238 :   long i, j, lv, l = lg(L);
      71             :   GEN w;
      72        7238 :   if (l == 1) return v;
      73        7196 :   lv = lg(v); w = cgetg(lv + l -1, typ(v));
      74        7196 :   for (i = 1; i < lv; i++) gel(w,i) = gel(v,i);
      75        7196 :   for (j = 1; j < l; i++, j++) gel(w,i) = mkvecsmall2(c, L[j]);
      76        7196 :   return w;
      77             : }
      78             : #define newcoset(g, k, a) \
      79             : { \
      80             :   long _c = lg(C); \
      81             :   C = vec_append(C, g); \
      82             :   M = vec_append(M, zero_zv(n)); \
      83             :   L3= vec_appendL(L3, list3, _c); \
      84             :   L = vec_appendL(L, list, _c); \
      85             :   B = vec_insertn(B, n, k, a % n, _c); \
      86             : }
      87             : 
      88             : static long
      89        2310 : _isin2(GEN L, long m, long a)
      90             : {
      91        2310 :   pari_sp av = avma;
      92        2310 :   long k = RgV_isin(L, mkvecsmall2(m,a));
      93        2310 :   return gc_long(av, k? k: lg(L));
      94             : }
      95             : static void
      96       27286 : get2(GEN x, long *a, long *b) { *a = x[1]; *b = x[2]; }
      97             : 
      98             : static GEN
      99         672 : denval(GEN g)
     100             : {
     101         672 :   GEN a = gcoeff(g,1,1), c = gcoeff(g,2,1);
     102         672 :   return signe(c)? denom_i(gdiv(a,c)): gen_0;
     103             : }
     104             : /* M * S, S = [0,1;-1,0] */
     105             : static GEN
     106         448 : mulS(GEN g)
     107             : {
     108         448 :   GEN a = gcoeff(g,1,1), b = gcoeff(g,1,2);
     109         448 :   GEN c = gcoeff(g,2,1), d = gcoeff(g,2,2);
     110         448 :   return mkmat22(negi(b), a, negi(d), c);
     111             : }
     112             : /* remove extra scales and reduce ast to involution */
     113             : static GEN
     114         105 : rectify(GEN V, GEN ast, GEN gam)
     115             : {
     116         105 :   long n = lg(V)-1, n1, i, def, m, dec;
     117             :   GEN V1, a1, g1, d, inj;
     118             :   pari_sp av;
     119             : 
     120       10836 :   for(i = 1, def = 0; i <= n; i++)
     121       10731 :     if (ast[ast[i]] != i) def++;
     122         105 :   def /= 3;
     123             : 
     124         105 :   if (!def) return mkvec3(V, ast, gam);
     125           7 :   n1 = n + def;
     126           7 :   g1 = cgetg(n1+1, t_VEC);
     127           7 :   V1 = cgetg(n1+1, t_VEC);
     128           7 :   a1 = cgetg(n1+1, t_VECSMALL);
     129           7 :   d = cgetg(def+1, t_VECSMALL);
     130           7 :   av = avma;
     131        9205 :   for (i = m = 1; i <= n; i++)
     132             :   {
     133        9198 :     long i2 = ast[i], i3 = ast[i2];
     134        9198 :     if (i2 > i && i3 > i)
     135             :     {
     136         224 :       GEN d1 = denval(ZM_mul(gel(gam,i),  gel(V,ast[i])));
     137         224 :       GEN d2 = denval(ZM_mul(gel(gam,i2), gel(V,ast[i2])));
     138         224 :       GEN d3 = denval(ZM_mul(gel(gam,i3), gel(V,ast[i3])));
     139         224 :       if (cmpii(d1,d2) <= 0)
     140         105 :         d[m++] = cmpii(d1,d3) <= 0? i: i3;
     141             :       else
     142         119 :         d[m++] = cmpii(d2,d3) <= 0? i2: i3;
     143             :     }
     144             :   }
     145           7 :   set_avma(av); inj = zero_zv(n);
     146           7 :   for (i = 1; i <= def; i++) inj[d[i]] = 1;
     147           7 :   for (i = 1, dec = 0; i <= n; i++) { dec += inj[i]; inj[i] = i + dec; }
     148        9205 :   for (i = 1; i <= n; i++)
     149        9198 :     if (ast[ast[i]] == i)
     150             :     {
     151        8526 :       gel(g1, inj[i]) = gel(gam,i);
     152        8526 :       gel(V1, inj[i]) = gel(V,i);
     153        8526 :       a1[inj[i]] = inj[ast[i]];
     154             :     }
     155         231 :   for (i = 1; i <= def; i++)
     156             :   {
     157         224 :     long a = d[i], b = ast[a], c = ast[b];
     158             :     GEN igc;
     159             : 
     160         224 :     gel(V1, inj[b]) = gel(V, b);
     161         224 :     gel(g1, inj[b]) = normalise(SL2_inv_shallow(gel(gam,a)));
     162         224 :     a1[inj[b]] = inj[a]-1;
     163             : 
     164         224 :     gel(V1, inj[c]) = gel(V, c);
     165         224 :     gel(g1, inj[c]) = gel(gam, c);
     166         224 :     a1[inj[c]] = inj[a];
     167             : 
     168         224 :     gel(V1, inj[a]-1) = normalise(ZM_mul(gel(gam,a), mulS(gel(V,b))));
     169         224 :     gel(g1, inj[a]-1) = gel(gam, a);
     170         224 :     a1[inj[a]-1] = inj[b];
     171             : 
     172         224 :     igc = SL2_inv_shallow(gel(gam,c));
     173         224 :     gel(V1, inj[a]) = normalise(ZM_mul(igc, mulS(gel(V,c))));
     174         224 :     gel(g1, inj[a]) = normalise(igc);
     175         224 :     a1[inj[a]] = inj[c];
     176             :   }
     177           7 :   return mkvec3(V1, a1, g1);
     178             : }
     179             : static GEN
     180       16555 : vecpop(GEN v)
     181             : {
     182       16555 :   long l = lg(v);
     183       16555 :   *v++ = evaltyp(t_VEC)|_evallg(1); /* stackdummy */
     184       16555 :   *v = evaltyp(t_VEC)|_evallg(l-1);
     185       16555 :   return v;
     186             : }
     187             : 
     188             : GEN
     189         105 : msfarey(GEN F, void *E, long (*in)(void *, GEN), GEN *pCM)
     190             : {
     191         105 :   pari_sp av = avma, av2, av3;
     192         105 :   GEN V = gel(F,1), ast = gel(F,2), gam = gel(F,3), V2, ast2, gam2;
     193             :   GEN C, M, L3, L, B, g, list3, list, perm, v2;
     194         105 :   long n = lg(gam)-1, i, k, m, a, l, c, c3;
     195             : 
     196         105 :   list = cgetg(n+1, t_VECSMALL);
     197         105 :   list3 = cgetg(n+1, t_VECSMALL);
     198         644 :   for (i = c = c3 = 1; i <= n; i++)
     199             :   {
     200             :     long t;
     201         539 :     if (ast[i] == i)
     202         203 :       t = !isintzero(gtrace(gel(gam,i)));
     203             :     else
     204         336 :       t = ast[ast[i]] != i;
     205         539 :     if (t) list3[c3++] = i; else list[c++] = i;
     206             :   }
     207         105 :   setlg(list, c); setlg(list3, c3);
     208         105 :   if (typ(ast) == t_VEC) ast = ZV_to_zv(ast);
     209         105 :   av2 = avma;
     210         105 :   C = M = L = L3 = cgetg(1, t_VEC);
     211         105 :   B = mkvec(mkvecsmall2(1,1));
     212         105 :   newcoset(matid(2),1,1);
     213       12432 :   while(lg(L)-1 + lg(L3)-1)
     214             :   {
     215       28777 :     while(lg(L3)-1)
     216             :     {
     217        4333 :       get2(gel(L3,1), &m,&a); L3 = vecpop(L3);
     218        4333 :       av3 = avma;
     219        4333 :       g = ZM_mul(gel(C,m), gel(gam,a));
     220        4333 :       k = conginlist(C, g, E, in);
     221        4333 :       gel(M,m)[a] = k;
     222        4333 :       if (k < lg(C)) avma = av3;
     223             :       else
     224             :       {
     225        1204 :         k = _isin2(B, m, a);
     226        1204 :         newcoset(g, k, ast[a]);
     227        1204 :         newcoset(ZM_mul(g,gel(gam,ast[a])), k+n-1, ast[ast[a]]);
     228        1204 :         B = vecsplice(B, k);
     229             :       }
     230             :     }
     231       12222 :     get2(gel(L,1), &m,&a); L = vecpop(L);
     232       12222 :     if (gc_needed(av,2))
     233             :     {
     234           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"msfarey, #L = %ld", lg(L)-1);
     235           0 :       gerepileall(av2, 4, &C, &M, &L, &B); L3 = cgetg(1, t_VEC);
     236             :     }
     237       12222 :     av3 = avma;
     238       12222 :     g = ZM_mul(gel(C,m), gel(gam,a));
     239       12222 :     k = conginlist(C, g, E, in);
     240       12222 :     gel(M,m)[a] = k; /* class of C[m]*gam[a] */
     241       12222 :     if (k < lg(C)) avma = av3;
     242             :     else
     243             :     {
     244        1106 :       k = _isin2(B, m, a);
     245        1106 :       newcoset(g,k,ast[a]);
     246        1106 :       B = vecsplice(B,k);
     247             :     }
     248             :   }
     249         105 :   vecvecsmall_sort_inplace(B, &perm);
     250         105 :   l = lg(B);
     251         105 :   V2 = cgetg(l, t_VEC);
     252         105 :   gam2 = cgetg(l, t_VEC);
     253         105 :   ast2 = cgetg(l, t_VECSMALL);
     254         105 :   v2 = cgetg(3, t_VECSMALL);
     255       10836 :   for (i = 1; i < l; i++)
     256             :   {
     257       10731 :     long r, j = perm[i];
     258             :     GEN ig;
     259       10731 :     get2(gel(B,i), &m,&a);
     260       10731 :     r = gel(M,m)[a]; ig = SL2_inv_shallow(gel(C,r));
     261       10731 :     gel(V2, j) = normalise(ZM_mul(gel(C,m), gel(V,a)));
     262       10731 :     gel(gam2, j) = normalise(ZM_mul(ZM_mul(gel(C,m), gel(gam,a)), ig));
     263       10731 :     v2[1] = r; v2[2] = ast[a]; ast2[j] = perm[vecvecsmall_search(B, v2, 0)];
     264             :   }
     265         105 :   F = rectify(V2, ast2, gam2);
     266         105 :   if (pCM) *pCM = mkvec2(C,M);
     267         105 :   gerepileall(av, pCM? 2: 1, &F, pCM); return F;
     268             : }
     269             : 
     270             : GEN
     271          14 : mscosets(GEN G, void *E, long (*in)(void *, GEN))
     272             : {
     273          14 :   pari_sp av = avma;
     274             :   GEN g, L, M;
     275          14 :   long n = lg(G)-1, i, m, k;
     276          14 :   g = gel(G,1);
     277          14 :   L = mkvec(typ(g) == t_VECSMALL? identity_perm(lg(g)-1): gdiv(g,g));
     278          14 :   M = mkvec(zero_zv(n));
     279          35 :   for (m = 1; m < lg(L); m++)
     280          77 :     for (i = 1; i <= n; i++)
     281             :     {
     282          56 :       g = gmul(gel(L,m), gel(G,i));
     283          56 :       mael(M, m, i) = k = conginlist(L, g, E, in);
     284          56 :       if (k > lg(L)-1) { L = vec_append(L,g); M = vec_append(M, zero_zv(n)); }
     285          56 :       if (gc_needed(av,2))
     286             :       {
     287           0 :         if (DEBUGMEM>1) pari_warn(warnmem,"mscosets, #L = %ld", lg(L)-1);
     288           0 :         gerepileall(av, 2, &M, &L);
     289             :       }
     290             :     }
     291          14 :   return gerepilecopy(av, mkvec2(L, M));
     292             : }
     293             : 
     294             : int
     295         231 : checkfarey_i(GEN F)
     296             : {
     297             :   GEN V, ast, gam;
     298         231 :   if (typ(F) != t_VEC || lg(F) < 4) return 0;
     299         231 :   V   = gel(F,1);
     300         231 :   ast = gel(F,2);
     301         231 :   gam = gel(F,3);
     302         231 :   if (typ(V) != t_VEC
     303         231 :       || (typ(ast) != t_VECSMALL && (typ(ast) != t_VEC || !RgV_is_ZV(ast)))
     304         105 :       || typ(gam) != t_VEC
     305         105 :       || lg(V) != lg(ast) || lg(ast) != lg(gam)) return 0;
     306         105 :   return 1;
     307             : }
     308             : static int
     309         133 : check_inH(GEN inH)
     310             : {
     311         266 :   return (typ(inH) == t_CLOSURE && closure_arity(inH) == 1
     312         259 :           && !closure_is_variadic(inH));
     313             : }
     314             : GEN
     315         105 : msfarey0(GEN F, GEN code, GEN *pCM)
     316             : {
     317         105 :   if (!checkfarey_i(F)) pari_err_TYPE("msfarey", F);
     318         105 :   if (!check_inH(code)) pari_err_TYPE("msfarey", code);
     319         105 :   return msfarey(F, (void*)code, gp_callbool, pCM);
     320             : }
     321             : GEN
     322          28 : mscosets0(GEN V, GEN code)
     323             : {
     324          28 :   if (typ(V) != t_VEC) pari_err_TYPE("mscosets", V);
     325          28 :   if (!check_inH(code)) pari_err_TYPE("mscosets", code);
     326          21 :   if (lg(V) == 1) pari_err_TYPE("mscosets [trivial group]", V);
     327          14 :   return mscosets(V, (void*)code, gp_callbool);
     328             : }

Generated by: LCOV version 1.13