1 /* 2 Copyright (c) 2013-2014 Genome Research Ltd. 3 Author: James Bonfield <jkb@sanger.ac.uk> 4 5 Redistribution and use in source and binary forms, with or without 6 modification, are permitted provided that the following conditions are met: 7 8 1. Redistributions of source code must retain the above copyright notice, 9 this list of conditions and the following disclaimer. 10 11 2. Redistributions in binary form must reproduce the above copyright notice, 12 this list of conditions and the following disclaimer in the documentation 13 and/or other materials provided with the distribution. 14 15 3. Neither the names Genome Research Ltd and Wellcome Trust Sanger 16 Institute nor the names of its contributors may be used to endorse or promote 17 products derived from this software without specific prior written permission. 18 19 THIS SOFTWARE IS PROVIDED BY GENOME RESEARCH LTD AND CONTRIBUTORS "AS IS" AND 20 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 21 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 22 DISCLAIMED. IN NO EVENT SHALL GENOME RESEARCH LTD OR CONTRIBUTORS BE LIABLE 23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 /*! \file 32 * SAM header parsing. 33 * 34 * These functions can be shared between SAM, BAM and CRAM file 35 * formats as all three internally use the same string encoding for 36 * header fields. 37 */ 38 39 /* 40 * TODO. 41 * 42 * - Sort order (parse to struct, enum type, updating funcs) 43 * - Removal of lines. 44 * - Updating of lines 45 */ 46 47 #ifndef _SAM_HDR_H_ 48 #define _SAM_HDR_H_ 49 50 #include <stdarg.h> 51 52 #include "cram/string_alloc.h" 53 #include "cram/pooled_alloc.h" 54 55 #include "htslib/khash.h" 56 #include "htslib/kstring.h" 57 58 #ifdef __cplusplus 59 extern "C" { 60 #endif 61 62 // For structure assignment. Eg kstring_t s = KS_INITIALIZER; 63 #define KS_INITIALIZER {0,0,0} 64 65 // For initialisation elsewhere. Eg KS_INIT(x->str); 66 #define KS_INIT(ks) ((ks)->l = 0, (ks)->m = 0, (ks)->s = NULL) 67 68 // Frees the string subfield only. Assumes 's' itself is static. 69 #define KS_FREE(ks) do { if ((ks)->s) free((ks)->s); } while(0) 70 71 /* 72 * Proposed new SAM header parsing 73 74 1 @SQ ID:foo LN:100 75 2 @SQ ID:bar LN:200 76 3 @SQ ID:ram LN:300 UR:xyz 77 4 @RG ID:r ... 78 5 @RG ID:s ... 79 80 Hash table for 2-char @keys without dup entries. 81 If dup lines, we form a circular linked list. Ie hash keys = {RG, SQ}. 82 83 HASH("SQ")--\ 84 | 85 (3) <-> 1 <-> 2 <-> 3 <-> (1) 86 87 HASH("RG")--\ 88 | 89 (5) <-> 4 <-> 5 <-> (4) 90 91 Items stored in the hash values also form their own linked lists: 92 Ie SQ->ID(foo)->LN(100) 93 SQ->ID(bar)->LN(200) 94 SQ->ID(ram)->LN(300)->UR(xyz) 95 RG->ID(r) 96 */ 97 98 /*! A single key:value pair on a header line 99 * 100 * These form a linked list and hold strings. The strings are 101 * allocated from a string_alloc_t pool referenced in the master 102 * SAM_hdr structure. Do not attempt to free, malloc or manipulate 103 * these strings directly. 104 */ 105 typedef struct SAM_hdr_tag_s { 106 struct SAM_hdr_tag_s *next; 107 char *str; 108 int len; 109 } SAM_hdr_tag; 110 111 /*! The parsed version of the SAM header string. 112 * 113 * Each header type (SQ, RG, HD, etc) points to its own SAM_hdr_type 114 * struct via the main hash table h in the SAM_hdr struct. 115 * 116 * These in turn consist of circular bi-directional linked lists (ie 117 * rings) to hold the multiple instances of the same header type 118 * code. For example if we have 5 \@SQ lines the primary hash table 119 * will key on \@SQ pointing to the first SAM_hdr_type and that in turn 120 * will be part of a ring of 5 elements. 121 * 122 * For each SAM_hdr_type structure we also point to a SAM_hdr_tag 123 * structure which holds the tokenised attributes; the tab separated 124 * key:value pairs per line. 125 */ 126 typedef struct SAM_hdr_item_s { 127 struct SAM_hdr_item_s *next; // cirular 128 struct SAM_hdr_item_s *prev; 129 SAM_hdr_tag *tag; // first tag 130 int order; // 0 upwards 131 } SAM_hdr_type; 132 133 /*! Parsed \@SQ lines */ 134 typedef struct { 135 char *name; 136 uint32_t len; 137 SAM_hdr_type *ty; 138 SAM_hdr_tag *tag; 139 } SAM_SQ; 140 141 /*! Parsed \@RG lines */ 142 typedef struct { 143 char *name; 144 SAM_hdr_type *ty; 145 SAM_hdr_tag *tag; 146 int name_len; 147 int id; // numerical ID 148 } SAM_RG; 149 150 /*! Parsed \@PG lines */ 151 typedef struct { 152 char *name; 153 SAM_hdr_type *ty; 154 SAM_hdr_tag *tag; 155 int name_len; 156 int id; // numerical ID 157 int prev_id; // -1 if none 158 } SAM_PG; 159 160 /*! Sort order parsed from @HD line */ 161 enum sam_sort_order { 162 ORDER_UNKNOWN =-1, 163 ORDER_UNSORTED = 0, 164 ORDER_NAME = 1, 165 ORDER_COORD = 2, 166 //ORDER_COLLATE = 3 // maybe one day! 167 }; 168 169 KHASH_MAP_INIT_INT(sam_hdr, SAM_hdr_type*) 170 KHASH_MAP_INIT_STR(m_s2i, int) 171 172 /*! Primary structure for header manipulation 173 * 174 * The initial header text is held in the text kstring_t, but is also 175 * parsed out into SQ, RG and PG arrays. These have a hash table 176 * associated with each to allow lookup by ID or SN fields instead of 177 * their numeric array indices. Additionally PG has an array to hold 178 * the linked list start points (the last in a PP chain). 179 * 180 * Use the appropriate sam_hdr_* functions to edit the header, and 181 * call sam_hdr_rebuild() any time the textual form needs to be 182 * updated again. 183 */ 184 typedef struct { 185 kstring_t text; //!< concatenated text, indexed by SAM_hdr_tag 186 khash_t(sam_hdr) *h; 187 string_alloc_t *str_pool; //!< Pool of SAM_hdr_tag->str strings 188 pool_alloc_t *type_pool;//!< Pool of SAM_hdr_type structs 189 pool_alloc_t *tag_pool; //!< Pool of SAM_hdr_tag structs 190 191 // @SQ lines / references 192 int nref; //!< Number of \@SQ lines 193 SAM_SQ *ref; //!< Array of parsed \@SQ lines 194 khash_t(m_s2i) *ref_hash; //!< Maps SQ SN field to sq[] index 195 196 // @RG lines / read-groups 197 int nrg; //!< Number of \@RG lines 198 SAM_RG *rg; //!< Array of parsed \@RG lines 199 khash_t(m_s2i) *rg_hash; //!< Maps RG ID field to rg[] index 200 201 // @PG lines / programs 202 int npg; //!< Number of \@PG lines 203 int npg_end; //!< Number of terminating \@PG lines 204 int npg_end_alloc; //!< Size of pg_end field 205 SAM_PG *pg; //!< Array of parsed \@PG lines 206 khash_t(m_s2i) *pg_hash; //!< Maps PG ID field to pg[] index 207 int *pg_end; //!< \@PG chain termination IDs 208 209 // @HD data 210 enum sam_sort_order sort_order; //!< @HD SO: field 211 212 // @cond internal 213 char ID_buf[1024]; // temporary buffer 214 int ID_cnt; 215 int ref_count; // number of uses of this SAM_hdr 216 // @endcond 217 } SAM_hdr; 218 219 /*! Creates an empty SAM header, ready to be populated. 220 * 221 * @return 222 * Returns a SAM_hdr struct on success (free with sam_hdr_free()) 223 * NULL on failure 224 */ 225 SAM_hdr *sam_hdr_new(void); 226 227 /*! Tokenises a SAM header into a hash table. 228 * 229 * Also extracts a few bits on specific data types, such as @RG lines. 230 * 231 * @return 232 * Returns a SAM_hdr struct on success (free with sam_hdr_free()); 233 * NULL on failure 234 */ 235 SAM_hdr *sam_hdr_parse_(const char *hdr, int len); 236 237 238 /*! Produces a duplicate copy of hdr and returns it. 239 * @return 240 * Returns NULL on failure 241 */ 242 SAM_hdr *sam_hdr_dup(SAM_hdr *hdr); 243 244 245 /*! Increments a reference count on hdr. 246 * 247 * This permits multiple files to share the same header, all calling 248 * sam_hdr_free when done, without causing errors for other open files. 249 */ 250 void sam_hdr_incr_ref(SAM_hdr *hdr); 251 252 253 /*! Increments a reference count on hdr. 254 * 255 * This permits multiple files to share the same header, all calling 256 * sam_hdr_free when done, without causing errors for other open files. 257 * 258 * If the reference count hits zero then the header is automatically 259 * freed. This makes it a synonym for sam_hdr_free(). 260 */ 261 void sam_hdr_decr_ref(SAM_hdr *hdr); 262 263 264 /*! Deallocates all storage used by a SAM_hdr struct. 265 * 266 * This also decrements the header reference count. If after decrementing 267 * it is still non-zero then the header is assumed to be in use by another 268 * caller and the free is not done. 269 * 270 * This is a synonym for sam_hdr_dec_ref(). 271 */ 272 void sam_hdr_free(SAM_hdr *hdr); 273 274 /*! Returns the current length of the SAM_hdr in text form. 275 * 276 * Call sam_hdr_rebuild() first if editing has taken place. 277 */ 278 int sam_hdr_length(SAM_hdr *hdr); 279 280 /*! Returns the string form of the SAM_hdr. 281 * 282 * Call sam_hdr_rebuild() first if editing has taken place. 283 */ 284 char *sam_hdr_str(SAM_hdr *hdr); 285 286 /*! Appends a formatted line to an existing SAM header. 287 * 288 * Line is a full SAM header record, eg "@SQ\tSN:foo\tLN:100", with 289 * optional new-line. If it contains more than 1 line then multiple lines 290 * will be added in order. 291 * 292 * Input text is of maximum length len or as terminated earlier by a NUL. 293 * Len may be 0 if unknown, in which case lines must be NUL-terminated. 294 * 295 * @return 296 * Returns 0 on success; 297 * -1 on failure 298 */ 299 int sam_hdr_add_lines(SAM_hdr *sh, const char *lines, int len); 300 301 /*! Adds a single line to a SAM header. 302 * 303 * Specify type and one or more key,value pairs, ending with the NULL key. 304 * Eg. sam_hdr_add(h, "SQ", "ID", "foo", "LN", "100", NULL). 305 * 306 * @return 307 * Returns 0 on success; 308 * -1 on failure 309 */ 310 int sam_hdr_add(SAM_hdr *sh, const char *type, ...); 311 312 /*! Adds a single line to a SAM header. 313 * 314 * This is much like sam_hdr_add() but with the additional va_list 315 * argument. This is followed by specifying type and one or more 316 * key,value pairs, ending with the NULL key. 317 * 318 * Eg. sam_hdr_vadd(h, "SQ", args, "ID", "foo", "LN", "100", NULL). 319 * 320 * The purpose of the additional va_list parameter is to permit other 321 * varargs functions to call this while including their own additional 322 * parameters; an example is in sam_hdr_add_PG(). 323 * 324 * Note: this function invokes va_arg at least once, making the value 325 * of ap indeterminate after the return. The caller should call 326 * va_start/va_end before/after calling this function or use va_copy. 327 * 328 * @return 329 * Returns 0 on success; 330 * -1 on failure 331 */ 332 int sam_hdr_vadd(SAM_hdr *sh, const char *type, va_list ap, ...); 333 334 /*! 335 * @return 336 * Returns the first header item matching 'type'. If ID is non-NULL it checks 337 * for the tag ID: and compares against the specified ID. 338 * 339 * Returns NULL if no type/ID is found 340 */ 341 SAM_hdr_type *sam_hdr_find(SAM_hdr *hdr, char *type, 342 char *ID_key, char *ID_value); 343 344 /*! 345 * 346 * As per SAM_hdr_type, but returns a complete line of formatted text 347 * for a specific head type/ID combination. If ID is NULL then it returns 348 * the first line of the specified type. 349 * 350 * The returned string is malloced and should be freed by the calling 351 * function with free(). 352 * 353 * @return 354 * Returns NULL if no type/ID is found. 355 */ 356 char *sam_hdr_find_line(SAM_hdr *hdr, char *type, 357 char *ID_key, char *ID_value); 358 359 /*! Looks for a specific key in a single sam header line. 360 * 361 * If prev is non-NULL it also fills this out with the previous tag, to 362 * permit use in key removal. *prev is set to NULL when the tag is the first 363 * key in the list. When a tag isn't found, prev (if non NULL) will be the last 364 * tag in the existing list. 365 * 366 * @return 367 * Returns the tag pointer on success; 368 * NULL on failure 369 */ 370 SAM_hdr_tag *sam_hdr_find_key(SAM_hdr *sh, 371 SAM_hdr_type *type, 372 char *key, 373 SAM_hdr_tag **prev); 374 375 /*! Adds or updates tag key,value pairs in a header line. 376 * 377 * Eg for adding M5 tags to @SQ lines or updating sort order for the 378 * @HD line (although use the sam_hdr_sort_order() function for 379 * HD manipulation, which is a wrapper around this funuction). 380 * 381 * Specify multiple key,value pairs ending in NULL. 382 * 383 * @return 384 * Returns 0 on success; 385 * -1 on failure 386 */ 387 int sam_hdr_update(SAM_hdr *hdr, SAM_hdr_type *type, ...); 388 389 /*! Returns the sort order from the @HD SO: field */ 390 enum sam_sort_order sam_hdr_sort_order(SAM_hdr *hdr); 391 392 /*! Reconstructs the kstring from the header hash table. 393 * @return 394 * Returns 0 on success; 395 * -1 on failure 396 */ 397 int sam_hdr_rebuild(SAM_hdr *hdr); 398 399 /*! Looks up a reference sequence by name and returns the numerical ID. 400 * @return 401 * Returns -1 if unknown reference. 402 */ 403 int sam_hdr_name2ref(SAM_hdr *hdr, const char *ref); 404 405 /*! Looks up a read-group by name and returns a pointer to the start of the 406 * associated tag list. 407 * 408 * @return 409 * Returns NULL on failure 410 */ 411 SAM_RG *sam_hdr_find_rg(SAM_hdr *hdr, const char *rg); 412 413 /*! Fixes any PP links in @PG headers. 414 * 415 * If the entries are in order then this doesn't need doing, but incase 416 * our header is out of order this goes through the sh->pg[] array 417 * setting the prev_id field. 418 * 419 * @return 420 * Returns 0 on sucess; 421 * -1 on failure (indicating broken PG/PP records) 422 */ 423 int sam_hdr_link_pg(SAM_hdr *hdr); 424 425 426 /*! Add an @PG line. 427 * 428 * If we wish complete control over this use sam_hdr_add() directly. This 429 * function uses that, but attempts to do a lot of tedious house work for 430 * you too. 431 * 432 * - It will generate a suitable ID if the supplied one clashes. 433 * - It will generate multiple @PG records if we have multiple PG chains. 434 * 435 * Call it as per sam_hdr_add() with a series of key,value pairs ending 436 * in NULL. 437 * 438 * @return 439 * Returns 0 on success; 440 * -1 on failure 441 */ 442 int sam_hdr_add_PG(SAM_hdr *sh, const char *name, ...); 443 444 /*! 445 * A function to help with construction of CL tags in @PG records. 446 * Takes an argc, argv pair and returns a single space-separated string. 447 * This string should be deallocated by the calling function. 448 * 449 * @return 450 * Returns malloced char * on success; 451 * NULL on failure 452 */ 453 char *stringify_argv(int argc, char *argv[]); 454 455 #ifdef __cplusplus 456 } 457 #endif 458 459 #endif /* _SAM_HDR_H_ */ 460