sam_header.c

   1 #include "sam_header.h"
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <ctype.h>
   5 #include <stdlib.h>
   6
   7 const char *o_hd_tags[] = {"SO","GO",NULL};
   8 const char *r_hd_tags[] = {"VN",NULL};
   9 const char *o_sq_tags[] = {"AS","M5","UR","SP",NULL};
  10 const char *r_sq_tags[] = {"SN","LN",NULL};
  11 const char *o_rg_tags[] = {"LB","DS","PU","PI","CN","DT","PL",NULL};
  12 const char *r_rg_tags[] = {"ID","SM",NULL};
  13 const char *o_pg_tags[] = {"VN","CL",NULL};
  14 const char *r_pg_tags[] = {"ID",NULL};
  15 const char *types[]          = {"HD","SQ","RG","PG","CO",NULL};
  16 const char **optional_tags[] = {o_hd_tags,o_sq_tags,o_rg_tags,o_pg_tags,NULL,NULL};
  17 const char **required_tags[] = {r_hd_tags,r_sq_tags,r_rg_tags,r_pg_tags,NULL,NULL};
  18
  19
  20 list_t *list_append(list_t *root, void *data)
  21 {
  22     list_t *l = root;
  23     while (l && l->next)
  24         l = l->next;
  25     if ( l )
  26     {
  27         l->next = malloc(sizeof(list_t));
  28         l = l->next;
  29     }
  30     else
  31     {
  32         l = malloc(sizeof(list_t));
  33         root = l;
  34     }
  35     l->data = data;
  36     l->next = NULL;
  37     return root;
  38 }
  39
  40 void list_free(list_t *root)
  41 {
  42     list_t *l = root;
  43     while (root)
  44     {
  45         l = root;
  46         root = root->next;
  47         free(l);
  48     }
  49 }
  50
  51
  52
  53 // Look for a tag "XY" in a predefined const char *[] array.
  54 int tag_exists(const char *tag, const char **tags)
  55 {
  56     int itag=0;
  57     if ( !tags ) return -1;
  58     while ( tags[itag] )
  59     {
  60         if ( tags[itag][0]==tag[0] && tags[itag][1]==tag[1] ) return itag;
  61         itag++;
  62     }
  63     return -1;
  64 }
  65
  66
  67
  68 // Mimics the behaviour of getline, except it returns pointer to the next chunk of the text
  69 //  or NULL if everything has been read. The lineptr should be freed by the caller. The
  70 //  newline character is stripped.
  71 const char *nextline(char **lineptr, size_t *n, const char *text)
  72 {
  73     int len;
  74     const char *to = text;
  75
  76     if ( !*to ) return NULL;
  77
  78     while ( *to && *to!='\n' && *to!='\r' ) to++;
  79     len = to - text + 1;
  80
  81     if ( *to )
  82     {
  83         // Advance the pointer for the next call
  84         if ( *to=='\n' ) to++;
  85         else if ( *to=='\r' && *(to+1)=='\n' ) to+=2;
  86     }
  87     if ( !len )
  88         return to;
  89
  90     if ( !*lineptr )
  91     {
  92         *lineptr = malloc(len);
  93         *n = len;
  94     }
  95     else if ( *n<len )
  96     {
  97         *lineptr = realloc(*lineptr, len);
  98         *n = len;
  99     }
 100     if ( !*lineptr )
 101             error("FIXME\n");
 102
 103     memcpy(*lineptr,text,len);
 104     (*lineptr)[len-1] = 0;
 105
 106     return to;
 107 }
 108
 109 // name points to "XY", value_from points to the first character of the value string and
 110 //  value_to points to the last character of the value string.
 111 HeaderTag *new_tag(const char *name, const char *value_from, const char *value_to)
 112 {
 113     HeaderTag *tag = malloc(sizeof(HeaderTag));
 114     int len = value_to-value_from+1;
 115
 116     tag->key[0] = name[0];
 117     tag->key[1] = name[1];
 118     tag->value = malloc(len+1);
 119     memcpy(tag->value,value_from,len+1);
 120     tag->value[len] = 0;
 121     return tag;
 122 }
 123
 124 HeaderTag *header_line_has_tag(HeaderLine *hline, const char *key)
 125 {
 126     list_t *tags = hline->tags;
 127     while (tags)
 128     {
 129         HeaderTag *tag = tags->data;
 130         if ( tag->key[0]==key[0] && tag->key[1]==key[1] ) return tag;
 131         tags = tags->next;
 132     }
 133     return NULL;
 134 }
 135
 136 #if 0
 137 // Is there a HeaderLine with all required fields identical to those given in the hline?
 138 HeaderLine *sam_header_has_line(HeaderDict *dict, HeaderLine *hline)
 139 {
 140     HeaderLine *found=NULL;
 141
 142     while (dict)
 143     {
 144         HeaderLine *dline = dict->data;
 145
 146         if ( hline->type[0]!=dline->type[0] || hline->type[1]!=dline->type[1] )
 147         {
 148             dict = dict->next;
 149             continue;
 150         }
 151
 152         int itype = tag_exists(hline->type,types);
 153         if ( itype==-1 ) error("[sam_header_has_line] Unknown type [%c%c]\n", hline->type[0],hline->type[1]);
 154
 155         int ireq=0, differ=0;
 156         while ( required_tags[itype] && required_tags[itype][ireq] )
 157         {
 158             HeaderTag *t1, *t2;
 159             t1 = header_line_has_tag(hline,required_tags[itype][ireq]);
 160             t2 = header_line_has_tag(dline,required_tags[itype][ireq]);
 161             if ( !t1 || !t2 ) error("[sam_header_has_line] Missing a required tag [%c%c]\n",
 162                 required_tags[itype][ireq][0],required_tags[itype][ireq][1]);
 163             if ( strcmp(t1->value,t2->value) )
 164             ireq++;
 165         }
 166         dict = dict->next;
 167     }
 168     return found;
 169 }
 170 #endif
 171
 172 HeaderLine *sam_header_line_parse(const char *headerLine)
 173 {
 174     HeaderLine *hline;
 175     HeaderTag *tag;
 176     const char *from, *to;
 177     from = headerLine;
 178
 179     if ( *from != '@' ) error("[sam_header_line_parse] expected '@', got [%s]\n", headerLine);
 180     to = ++from;
 181
 182     while (*to && *to!='\t') to++;
 183     if ( to-from != 2 ) error("[sam_header_line_parse] expected '@XY', got [%s]\n", headerLine);
 184
 185     hline = malloc(sizeof(HeaderLine));
 186     hline->type[0] = from[0];
 187     hline->type[1] = from[1];
 188     hline->tags = NULL;
 189
 190     int itype = tag_exists(hline->type, types);
 191
 192     from = to;
 193     while (*to && *to=='\t') to++;
 194     if ( to-from != 1 )
 195         error("[sam_header_line_parse] multiple tabs on line [%s] (%d)\n", headerLine,(int)(to-from));
 196     from = to;
 197     while (*from)
 198     {
 199         while (*to && *to!='\t') to++;
 200
 201         if ( !required_tags[itype] && !optional_tags[itype] )
 202             tag = new_tag("  ",from,to-1);
 203         else
 204             tag = new_tag(from,from+3,to-1);
 205
 206         if ( header_line_has_tag(hline,tag->key) )
 207                 debug("The tag '%c%c' present (at least) twice on line [%s]\n", tag->key[0],tag->key[1], headerLine);
 208         hline->tags = list_append(hline->tags, tag);
 209
 210         from = to;
 211         while (*to && *to=='\t') to++;
 212         if ( *to && to-from != 1 )
 213                 error("[sam_header_line_parse] multiple tabs on line [%s] (%d)\n", headerLine,(int)(to-from));
 214
 215         from = to;
 216     }
 217     return hline;
 218 }
 219
 220
 221 // Must be of an existing type, all tags must be recognised and all required tags must be present
 222 int sam_header_line_validate(HeaderLine *hline)
 223 {
 224     list_t *tags;
 225     HeaderTag *tag;
 226     int itype, itag;
 227
 228     // Is the type correct?
 229     itype = tag_exists(hline->type, types);
 230     if ( itype==-1 )
 231     {
 232         debug("The type [%c%c] not recognised.\n", hline->type[0],hline->type[1]);
 233         return 0;
 234     }
 235
 236     // Has all required tags?
 237     itag = 0;
 238     while ( required_tags[itype] && required_tags[itype][itag] )
 239     {
 240         if ( !header_line_has_tag(hline,required_tags[itype][itag]) )
 241         {
 242             debug("The tag [%c%c] required for [%c%c] not present.\n", required_tags[itype][itag][0],required_tags[itype][itag][1],
 243                 hline->type[0],hline->type[1]);
 244             return 0;
 245         }
 246         itag++;
 247     }
 248
 249     // Are all tags recognised?
 250     tags = hline->tags;
 251     while ( tags )
 252     {
 253         tag = tags->data;
 254         if ( !tag_exists(tag->key,required_tags[itype]) && !tag_exists(tag->key,optional_tags[itype]) )
 255         {
 256             debug("Unknown tag [%c%c] for [%c%c].\n", tag->key[0],tag->key[1], hline->type[0],hline->type[1]);
 257             return 0;
 258         }
 259         tags = tags->next;
 260     }
 261
 262     return 1;
 263 }
 264
 265 void print_header_line(HeaderLine *hline)
 266 {
 267     list_t *tags = hline->tags;
 268     HeaderTag *tag;
 269
 270     printf("@%c%c", hline->type[0],hline->type[1]);
 271     while (tags)
 272     {
 273         tag = tags->data;
 274         printf("\t%c%c:%s", tag->key[0],tag->key[1],tag->value);
 275         tags = tags->next;
 276     }
 277     printf("\n");
 278 }
 279
 280
 281 void sam_header_free(HeaderDict *header)
 282 {
 283     list_t *hlines = header;
 284     while (hlines)
 285     {
 286         HeaderLine *hline = hlines->data;
 287         list_t *tags = hline->tags;
 288         while (tags)
 289         {
 290             HeaderTag *tag = tags->data;
 291             free(tag->value);
 292             free(tag);
 293             tags = tags->next;
 294         }
 295         list_free(hline->tags);
 296         free(hline);
 297         hlines = hlines->next;
 298     }
 299     list_free(header);
 300 }
 301
 302 // Returns a newly allocated string
 303 char *sam_header_write(const HeaderDict *header)
 304 {
 305     char *out = NULL;
 306     int len=0, nout=0;
 307     const list_t *hlines;
 308
 309     // Calculate the length of the string to allocate
 310     hlines = header;
 311     while (hlines)
 312     {
 313         len += 4;   // @XY and \n
 314
 315         HeaderLine *hline = hlines->data;
 316         list_t *tags = hline->tags;
 317         while (tags)
 318         {
 319             HeaderTag *tag = tags->data;
 320             len += strlen(tag->value) + 1;                  // \t
 321             if ( tag->key[0]!=' ' || tag->key[1]!=' ' )
 322                 len += strlen(tag->value) + 3;              // XY:
 323             tags = tags->next;
 324         }
 325         hlines = hlines->next;
 326     }
 327
 328     nout = 0;
 329     out  = malloc(len+1);
 330     hlines = header;
 331     while (hlines)
 332     {
 333         HeaderLine *hline = hlines->data;
 334
 335         nout += sprintf(out+nout,"@%c%c",hline->type[0],hline->type[1]);
 336
 337         list_t *tags = hline->tags;
 338         while (tags)
 339         {
 340             HeaderTag *tag = tags->data;
 341             nout += sprintf(out+nout,"\t");
 342             if ( tag->key[0]!=' ' || tag->key[1]!=' ' )
 343                 nout += sprintf(out+nout,"%c%c:", tag->key[0],tag->key[1]);
 344             nout += sprintf(out+nout,"%s", tag->value);
 345             tags = tags->next;
 346         }
 347         hlines = hlines->next;
 348         nout += sprintf(out+nout,"\n");
 349     }
 350     out[len] = 0;
 351     return out;
 352 }
 353
 354 HeaderDict *sam_header_parse(const char *headerText)
 355 {
 356     list_t *hlines = NULL;
 357     HeaderLine *hline;
 358     const char *text;
 359     char *buf=NULL;
 360     size_t nbuf = 0;
 361
 362     if ( !headerText )
 363         error("FIXME");
 364
 365     text = headerText;
 366     while ( (text=nextline(&buf, &nbuf, text)) )
 367     {
 368         hline = sam_header_line_parse(buf);
 369         if ( sam_header_line_validate(hline) )
 370             hlines = list_append(hlines, hline);
 371         else
 372         {
 373             sam_header_free(hlines);
 374             return NULL;
 375         }
 376     }
 377     if ( buf ) free(buf);
 378
 379     return hlines;
 380 }
 381
 382 khash_t(str) *sam_header_lookup_table(const HeaderDict *dict, char type[2], char key_tag[2], char value_tag[2])
 383 {
 384     const list_t *l   = dict;
 385     khash_t(str) *tbl = kh_init(str);
 386     khiter_t k;
 387     int ret;
 388
 389     while (l)
 390     {
 391         HeaderLine *hline = l->data;
 392         if ( hline->type[0]!=type[0] || hline->type[1]!=type[1] )
 393         {
 394             l = l->next;
 395             continue;
 396         }
 397
 398         HeaderTag *key, *value;
 399         key   = header_line_has_tag(hline,key_tag);
 400         value = header_line_has_tag(hline,value_tag);
 401         if ( !key || !value )
 402         {
 403             l = l->next;
 404             continue;
 405         }
 406
 407         k = kh_get(str, tbl, key->value);
 408         if ( k != kh_end(tbl) )
 409             debug("[sam_header_lookup_table] They key %s not unique.\n", key->value);
 410         k = kh_put(str, tbl, key->value, &ret);
 411         kh_value(tbl, k) = value->value;
 412
 413         l = l->next;
 414     }
 415     return tbl;
 416 }
 417
 418
 419 #if 0
 420 TODO
 421 HeaderDict *sam_header_merge(int n, const HeaderDict **dicts)
 422 {
 423     HeaderDict *out=NULL;
 424     int idict;
 425
 426     for (idict=0; idict<n; idict++)
 427     {
 428         list_t *hlines = dicts[idict];
 429         while (hlines)
 430         {
 431             HeaderLine *hline = sam_header_has_line(out, hlines->data);
 432             sam_header_line_merge(hline,hlines->data);
 433             hlines = hlines->next;
 434         }
 435     }
 436 }
 437 #endif
 438