Source code

Download source archive ↓

upstream-dependencies/samtools/bam2depth.c

1/*  bam2depth.c -- depth subcommand.
2
3    Copyright (C) 2011, 2012 Broad Institute.
4    Copyright (C) 2012-2016, 2018, 2019-2022, 2024 Genome Research Ltd.
5
6    Author: Heng Li <lh3@sanger.ac.uk> (to 2020)
7    Author: James Bonfield <jkb@sanger.ac.uk> (2021 rewrite)
8
9
10Permission is hereby granted, free of charge, to any person obtaining a copy
11of this software and associated documentation files (the "Software"), to deal
12in the Software without restriction, including without limitation the rights
13to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
14copies of the Software, and to permit persons to whom the Software is
15furnished to do so, subject to the following conditions:
16
17The above copyright notice and this permission notice shall be included in
18all copies or substantial portions of the Software.
19
20THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
26DEALINGS IN THE SOFTWARE.  */
27
28/* This program demonstrates how to generate pileup from multiple BAMs
29 * simultaneously, to achieve random access and to use the BED interface.
30 * To compile this program separately, you may:
31 *
32 *   gcc -g -O2 -Wall -o bam2depth -D_MAIN_BAM2DEPTH bam2depth.c -lhts -lz
33 */
34
35#include <config.h>
36
37#include <stdlib.h>
38#include <string.h>
39#include <stdio.h>
40#include <limits.h>
41#include <unistd.h>
42#include "htslib/sam.h"
43#include "samtools.h"
44#include "bedidx.h"
45#include "sam_opts.h"
46#include "htslib/khash.h"
47
48// From bam_plcmd.c
49int read_file_list(const char *file_list, int *n, char **argv[]);
50
51// We accumulate to hist[pos & (size-1)].  This is a ring-buffer.
52// We track where we last got to in output and what the biggest value
53// we've written to so far (in absolute unmasked coordinates) in
54// "last_output" and "end_pos" respectively.
55// For each new record we just flush anything we haven't written yet
56// already, between "last_output" and this read's start position, and
57// initialise any newly seen positions between "end_pos" and this read's
58// end position.
59typedef struct {
60    size_t size;
61    int **hist;         // hist[nfiles][size]
62    hts_pos_t *end_pos; // end_pos[nfiles]
63    hts_pos_t last_output;
64    int last_ref;
65    int nfiles;
66    const char *ref;
67    kstring_t ks;
68    hts_pos_t beg, end; // limit to region
69    int tid;
70} depth_hist;
71
72typedef struct {
73    int header;
74    int flag;
75    int incl_flag;
76    int require_flag;
77    int min_qual;
78    int min_mqual;
79    int min_len;
80    int skip_del;
81    int all_pos;
82    int remove_overlaps;
83    FILE *out;
84    char *reg;
85    void *bed;
86} depth_opt;
87
88static void zero_region(depth_opt *opt, depth_hist *dh,
89                        const char *name, hts_pos_t start, hts_pos_t end) {
90    hts_pos_t i;
91    kstring_t *ks = &dh->ks;
92
93    kputs(name, ks_clear(ks));
94    kputc('\t', ks);
95    size_t cur_l = ks->l;
96    if (dh->beg >= 0 && start < dh->beg)
97        start = dh->beg;
98    if (dh->end >= 0 && end > dh->end)
99        end = dh->end;
100
101    for (i = start; i < end; i++) {
102        // Could be optimised, but needs better API to skip to next
103        // bed region.
104        if (opt->bed && bed_overlap(opt->bed, name, i, i+1) == 0)
105            continue;
106
107        ks->l = cur_l;
108        kputll(i+1,  ks);
109        int n;
110        for (n = 0; n < dh->nfiles; n++) {
111            kputc_('\t', ks);
112            kputc_('0',  ks);
113        }
114        kputc('\n',  ks);
115        fputs(ks->s, opt->out);
116    }
117    ks->l = cur_l;
118}
119
120// A variation of bam_cigar2qlen which doesn't count soft-clips in to the
121// equation.  Basically it's the number of bases in query that are aligned
122// in some way to the reference (including insertions, which are considered
123// to be aligned by dint of being anchored either side).
124hts_pos_t qlen_used(bam1_t *b) {
125    int n_cigar = b->core.n_cigar;
126    const uint32_t *cigar = bam_get_cigar(b);
127
128    hts_pos_t l;
129
130    if (b->core.l_qseq) {
131        // Known SEQ permits of short cut of l_qseq minus CSOFT_CLIPs.
132        // Full scan not needed, which helps on excessively long CIGARs.
133        l = b->core.l_qseq;
134        int kl, kr;
135        for (kl = 0; kl < n_cigar; kl++)
136            if (bam_cigar_op(cigar[kl]) == BAM_CSOFT_CLIP)
137                l -= bam_cigar_oplen(cigar[kl]);
138            else
139                break;
140
141        for (kr = n_cigar-1; kr > kl; kr--)
142            if (bam_cigar_op(cigar[kr]) == BAM_CSOFT_CLIP)
143                l -= bam_cigar_oplen(cigar[kr]);
144            else
145                break;
146    } else {
147        // Unknown SEQ ("*") needs a full scan through the CIGAR string.
148        static int query[16] = {
149          //M I D N  S H P =  X B ? ?  ? ? ? ?
150            1,1,0,0, 0,0,0,1, 1,0,0,0, 0,0,0,0
151        };
152        int k;
153        for (k = l = 0; k < n_cigar; k++)
154            if (query[bam_cigar_op(cigar[k])])
155                l += bam_cigar_oplen(cigar[k]);
156    }
157    return l;
158
159}
160
161// Without HTS_OPT3 gcc11 and earlier don't vectorize this, nor even
162// unroll it.  By adding HTS_OPT3 we can force a better level of optimization.
163// On an Illumina BAM with gcc11 -O2, with HTS_OPT3 is 9% quicker for the
164// entire process (ie decompress, iterator, aggregate & report)
165static inline void HTS_OPT3 incr_hist(int *hist, int oplen) {
166    const int N = 16;
167    int k;
168    for (k = 0; k < (oplen & ~(N-1)); k+=N) {
169        for (int i = 0; i < N; i++)
170            hist[k+i]++;
171    }
172    for (; k < oplen; k++)
173        hist[k]++;
174}
175
176static inline void HTS_OPT3
177incr_hist_qual(int *hist, uint8_t *qual, int min_qual, int oplen) {
178    if (!min_qual) {
179        incr_hist(hist, oplen);
180        return;
181    }
182
183    int k;
184    for (k = 0; k < (oplen & ~31); k+=32) {
185        int pass[32];
186        // Two separate loops helps clang to vectorize
187        for (int i = 0; i < 32; i++)
188            pass[i]=qual[k+i]>=min_qual;
189
190        for (int i = 0; i < 32; i++)
191            hist[k+i]+=pass[i];
192    }
193    for (; k < oplen; k++)
194        hist[k]+=qual[k]>=min_qual;
195}
196
197// Adds the depth for a single read to a depth_hist struct.
198// For just one file, this is easy.  We just have a circular buffer
199// where we increment values for bits that overlap existing data
200// and initialise values for coordinates which we're seeing for the first
201// time.  This is tracked by "end_pos" to know where we've got to.
202//
203// As the input is sorted, we can flush output from "last_output" to
204// b->core.pos.
205//
206// With multiple files, we must feed data in sorted order as if all files
207// are merged, but track depth per file.  This also means "end_pos" is per
208// file too, but "last_output" is global as it corresponds to rows printed.
209static int add_depth(depth_opt *opt, depth_hist *dh, sam_hdr_t *h, bam1_t *b,
210                     int overlap_clip, int file) {
211    hts_pos_t i;
212    size_t hmask = dh->size-1;
213    int n;
214
215    if (!b || b->core.tid != dh->last_ref) {
216        // New ref
217        if (dh->last_ref >= 0) {
218            // do end
219            size_t cur_l = dh->ks.l;
220            int nf = dh->nfiles;
221            i = dh->last_output;
222            for (i = dh->last_output; nf; i++) {
223                nf = 0;
224                for (n = 0; n < dh->nfiles; n++) {
225                    if (i < dh->end_pos[n])
226                        nf++;
227                }
228                if (!nf)
229                    break;
230
231                if (opt->bed && bed_overlap(opt->bed, dh->ref, i, i+1) == 0)
232                    continue;
233
234                dh->ks.l = cur_l;
235                kputll(i+1, &dh->ks);
236                for (n = 0; n < dh->nfiles; n++) {
237                    kputc_('\t', &dh->ks);
238                    int d = i < dh->end_pos[n]
239                        ? dh->hist[n][i & hmask]
240                        : 0;
241                    kputuw(d, &dh->ks);
242                }
243                kputc('\n', &dh->ks);
244                fputs(dh->ks.s, opt->out);
245            }
246            if (opt->all_pos) {
247                // End of last ref
248                zero_region(opt, dh,
249                            sam_hdr_tid2name(h, dh->last_ref),
250                            i, sam_hdr_tid2len(h, dh->last_ref));
251            }
252            dh->ks.l = cur_l;
253        }
254
255        if (opt->all_pos > 1 && !opt->reg) {
256            // Any previous unused refs
257            int lr = dh->last_ref < 0 ? 0 : dh->last_ref+1;
258            int rr = b ? b->core.tid : sam_hdr_nref(h), r;
259            for (r = lr; r < rr; r++)
260                zero_region(opt, dh,
261                            sam_hdr_tid2name(h, r),
262                            0, sam_hdr_tid2len(h, r));
263        }
264
265        if (!b) {
266            // we're just flushing to end of file
267            if (opt->all_pos && opt->reg && dh->last_ref < 0)
268                // -a or -aa without a single read being output yet
269                zero_region(opt, dh, sam_hdr_tid2name(h, dh->tid), dh->beg,
270                            MIN(dh->end, sam_hdr_tid2len(h, dh->tid)));
271
272            return 0;
273        }
274
275        for (n = 0; dh->end_pos && n < dh->nfiles; n++)
276            dh->end_pos[n] = 0;
277        dh->last_output = dh->beg >= 0
278            ? MAX(b->core.pos, dh->beg)
279            : b->core.pos;
280        dh->last_ref = b->core.tid;
281        dh->ref = sam_hdr_tid2name(h, b->core.tid);
282        kputs(dh->ref, ks_clear(&dh->ks));
283        kputc('\t', &dh->ks);
284
285        if (opt->all_pos)
286            // Start of ref
287            zero_region(opt, dh, dh->ref, 0, b->core.pos);
288    } else {
289        if (dh->last_output < b->core.pos) {
290            // Flush any depth outputs up to start of new read
291            size_t cur_l = dh->ks.l;
292            int nf = dh->nfiles;
293            for (i = dh->last_output; i < b->core.pos; i++) {
294                nf = 0;
295                for (n = 0; n < dh->nfiles; n++) {
296                    if (i < dh->end_pos[n])
297                        nf++;
298                }
299                if (!nf)
300                    break;
301
302                if (opt->bed && bed_overlap(opt->bed, dh->ref, i, i+1) == 0)
303                    continue;
304
305                dh->ks.l = cur_l;
306                kputll(i+1, &dh->ks);
307                for (n = 0; n < dh->nfiles; n++) {
308                    kputc_('\t', &dh->ks);
309                    int d = i < dh->end_pos[n]
310                        ? dh->hist[n][i & hmask]
311                        : 0;
312                    kputuw(d, &dh->ks);
313                }
314                kputc('\n', &dh->ks);
315                fputs(dh->ks.s, opt->out);
316            }
317            if (opt->all_pos && i < b->core.pos)
318                // Hole in middle of ref
319                zero_region(opt, dh, dh->ref, i, b->core.pos);
320
321            dh->ks.l = cur_l;
322            dh->last_output = b->core.pos;
323        }
324    }
325
326    hts_pos_t end_pos = bam_endpos(b); // 0 based, 1 past end.
327    //printf("%d %d\n", (int)b->core.pos+1, (int)end_pos);
328
329    if (b->core.tid < dh->last_ref ||
330        (dh->last_ref == b->core.tid && end_pos < dh->last_output)) {
331        print_error_errno("depth", "Data is not position sorted");
332        return -1;
333    }
334
335    // If needed, grow the circular buffer.
336    if (end_pos+1 - b->core.pos >= dh->size) {
337        size_t old_size = dh->size;
338        size_t old_hmask = hmask;
339        while (end_pos+1 - b->core.pos >= dh->size)
340            dh->size = dh->size ? 2*dh->size : 2048;
341        hmask = dh->size-1;
342        if (!dh->hist) {
343            dh->hist = calloc(dh->nfiles, sizeof(*dh->hist));
344            dh->end_pos = calloc(dh->nfiles, sizeof(*dh->end_pos));
345            if (!dh->hist || !dh->end_pos)
346                return -1;
347        }
348        for (n = 0; n < dh->nfiles; n++) {
349            int *hist = calloc(dh->size, sizeof(*dh->hist[n]));
350            if (!hist)
351                return -1;
352
353            // Simple approach for now; copy over old histogram verbatim.
354            for (i = dh->last_output; i < dh->last_output + old_size; i++)
355                hist[i & hmask] = dh->hist[n][i & old_hmask];
356            free(dh->hist[n]);
357            dh->hist[n] = hist;
358        }
359    }
360
361    // Accumulate depth, based on CIGAR
362    uint32_t *cig = bam_get_cigar(b);
363    int ncig = b->core.n_cigar, j, k, spos = 0;
364
365    // Zero new (previously unseen) coordinates so increment works later.
366    hts_pos_t end = MAX(dh->end_pos[file], b->core.pos);
367    if (end_pos > end && (end & hmask) < (end_pos & hmask)) {
368        memset(&dh->hist[file][end & hmask], 0,
369               sizeof(**dh->hist) * (end_pos - end));
370    } else {
371        for (i = end; i < end_pos; i++)
372            dh->hist[file][i & hmask] = 0;
373    }
374
375    i = b->core.pos;
376    uint8_t *qual = bam_get_qual(b);
377    int min_qual = opt->min_qual;
378    for (j = 0; j < ncig; j++) {
379        int op    = bam_cigar_op(cig[j]);
380        int oplen = bam_cigar_oplen(cig[j]);
381
382        switch (op) {
383        case BAM_CDEL:
384        case BAM_CREF_SKIP:
385            if (op != BAM_CDEL || opt->skip_del) {
386                // don't increment reference location
387                if (i + oplen >= dh->end_pos[file]) {
388                    for (k = 0; k < oplen; k++, i++) {
389                        if (i >= dh->end_pos[file])
390                            // redundant due to zero new elements above?
391                            dh->hist[file][i & hmask] = 0;
392                    }
393                } else {
394                    i += oplen;
395                }
396            } else { // op == BAM_CDEL and we count them (-J option),
397                // We don't incr spos here, but we still use qual.
398                // This doesn't make much sense, but it's for compatibility
399                // with the old code.  Arguably DEL shouldn't have a min
400                // qual and should always pass (as we've explicitly asked to
401                // include them).
402                int *hist = dh->hist[file];
403                k = 0;
404                if (overlap_clip) {
405                    if (i+oplen < overlap_clip) {
406                        i += oplen;
407                        break;
408                    } else if (i < overlap_clip) {
409                        k = overlap_clip - i;
410                        i = overlap_clip;
411                    }
412                }
413
414                // Question: should we even check quality values for DEL?
415                // We've explicitly asked to include them, and the quality
416                // is wrong anyway (it's the neighbouring base).  We do this
417                // for now for compatibility with the old depth command.
418                if (spos < b->core.l_qseq)
419                    for (; k < oplen; k++, i++)
420                        hist[i & hmask]+=qual[spos]>=min_qual;
421                else
422                    for (; k < oplen; k++, i++)
423                        hist[i & hmask]++;
424            }
425            break;
426
427        case BAM_CMATCH:
428        case BAM_CEQUAL:
429        case BAM_CDIFF: {
430            int *hist = dh->hist[file];
431            k = 0;
432            if (overlap_clip) {
433                if (i+oplen < overlap_clip) {
434                    i += oplen;
435                    break;
436                } else if (i < overlap_clip) {
437                    oplen -= overlap_clip - i;
438                    spos += overlap_clip - i;
439                    i = overlap_clip;
440                }
441            }
442
443            int len = (i & hmask) < ((i+oplen) & hmask)
444                ? oplen                  // doesn't wrap around
445                : dh->size - (i&hmask);  // does wrap around
446            incr_hist_qual(&hist[i & hmask], &qual[spos], min_qual, len);
447            if (oplen > len)
448                incr_hist_qual(hist, &qual[spos+len], min_qual, oplen-len);
449            spos += oplen;
450            i += oplen;
451            break;
452        }
453
454        case BAM_CINS:
455        case BAM_CSOFT_CLIP:
456            spos += oplen;
457            break;
458
459        case BAM_CPAD:
460        case BAM_CHARD_CLIP:
461            // ignore
462            break;
463
464        default:
465            print_error("depth", "Unsupported cigar op '%d'", op);
466            return -1;
467        }
468    }
469
470    if (dh->end >= 0 && end_pos > dh->end)
471        end_pos = dh->end;
472    if (dh->end_pos[file] < end_pos)
473        dh->end_pos[file] = end_pos;
474
475    return 0;
476}
477
478// Hash on name -> alignment end pos. This permits a naive overlap removal.
479// Note it cannot analyse the overlapping sequence and qualities, so the
480// interaction of basecalls/qualities and the -Q parameter cannot be
481// applied here (unlike the full mpileup algorithm).
482KHASH_MAP_INIT_STR(olap_hash, hts_pos_t)
483typedef khash_t(olap_hash) olap_hash_t;
484
485static int fastdepth_core(depth_opt *opt, uint32_t nfiles, char **fn,
486                          samFile **fp, hts_itr_t **itr, sam_hdr_t **h) {
487    int ret = -1, err = 1, i;
488    olap_hash_t **overlaps = NULL;
489    depth_hist dh = {0};
490
491    // An array of bam structs, one per input file, to hold the next entry
492    bam1_t **b = calloc(nfiles, sizeof(*b));
493    int *finished = calloc(nfiles, sizeof(*finished)), to_go = nfiles;
494    if (!b || !finished)
495        goto err;
496
497    for (i = 0; i < nfiles; i++)
498        if (!(b[i] = bam_init1()))
499            goto err;
500
501    // Do we need one overlap hash per file? Or shared?
502    if (opt->remove_overlaps) {
503        if (!(overlaps = calloc(nfiles, sizeof(*overlaps))))
504            return -1;
505        for (i = 0; i < nfiles; i++) {
506            if (!(overlaps[i] = kh_init(olap_hash)))
507                return -1;
508        }
509    }
510
511    // Create the initial histogram
512    dh.nfiles = nfiles;
513    dh.size = 0;
514    dh.hist = NULL;
515    dh.last_ref = -99;
516    dh.end_pos = NULL;
517    dh.last_output = itr && itr[0] ? itr[0]->beg : 0;
518    ks_initialize(&dh.ks);
519
520    // Clip results to region if specified
521    dh.beg = -1;
522    dh.end = -1;
523    dh.tid = 0;
524    if (itr && itr[0]) {
525        dh.tid = itr[0]->tid;
526        dh.beg = itr[0]->beg;
527        dh.end = itr[0]->end;
528    }
529
530    if (opt->header) {
531        fprintf(opt->out, "#CHROM\tPOS");
532        for (i = 0; i < nfiles; i++)
533            fprintf(opt->out, "\t%s", fn[i]);
534        fputc('\n', opt->out);
535    }
536
537    // Populate first record per file
538    for (i = 0; i < nfiles; i++) {
539        for(;;) {
540            ret = itr && itr[i]
541                ? sam_itr_next(fp[i], itr[i], b[i])
542                : sam_read1(fp[i], h[i], b[i]);
543            if (ret < -1)
544                goto err;
545            if (ret == -1) {
546                to_go--;
547                finished[i] = 1;
548                break;
549            }
550
551            if (b[i]->core.tid < 0)
552                continue;
553            if (b[i]->core.flag & opt->flag)
554                continue; // must have none of the flags set
555            if (opt->incl_flag && (b[i]->core.flag & opt->incl_flag) == 0)
556                continue; // must have at least one flag set
557            if ((b[i]->core.flag & opt->require_flag) != opt->require_flag)
558                continue; // must have all lags set
559            if (b[i]->core.qual < opt->min_mqual)
560                continue;
561
562            // Original samtools depth used the total sequence (l_qseq)
563            // including soft-clips.  This doesn't feel like a useful metric
564            // to be filtering on.  We now only count sequence bases that
565            // form the used part of the alignment.
566            if (opt->min_len) {
567                if (qlen_used(b[i]) < opt->min_len)
568                    continue;
569            }
570
571            break;
572        }
573    }
574
575    // Loop through input files, merging in order so we're
576    // always adding the next record in sequence
577    while (to_go) {
578        // Find next record in file list
579        int best_tid = INT_MAX, best_file = 0;
580        hts_pos_t best_pos = HTS_POS_MAX;
581
582        for (i = 0; i < nfiles; i++) {
583            if (finished[i])
584                continue;
585            if (best_tid > b[i]->core.tid) {
586                best_tid = b[i]->core.tid;
587                best_pos = b[i]->core.pos;
588                best_file = i;
589            } else if (best_tid == b[i]->core.tid &&
590                       best_pos > b[i]->core.pos) {
591                best_pos = b[i]->core.pos;
592                best_file = i;
593            }
594        }
595        i = best_file;
596
597        hts_pos_t clip = 0;
598        if (overlaps && (b[i]->core.flag & BAM_FPAIRED) &&
599            !(b[i]->core.flag & BAM_FMUNMAP)) {
600            khiter_t k = kh_get(olap_hash, overlaps[i], bam_get_qname(b[i]));
601            if (k == kh_end(overlaps[i])) {
602                // not seen before
603                hts_pos_t endpos = bam_endpos(b[i]);
604
605                // Don't add if mate location is known and can't overlap.
606                if (b[i]->core.mpos == -1 ||
607                    (b[i]->core.tid == b[i]->core.mtid &&
608                     b[i]->core.mpos <= endpos)) {
609                    k = kh_put(olap_hash, overlaps[i], bam_get_qname(b[i]),
610                               &ret);
611                    if (ret < 0)
612                        return -1;
613                    kh_key(overlaps[i], k) = strdup(bam_get_qname(b[i]));
614                    kh_value(overlaps[i], k) = endpos;
615                }
616            } else {
617                // seen before
618                clip = kh_value(overlaps[i], k);
619                free((char *)kh_key(overlaps[i], k));
620                kh_del(olap_hash, overlaps[i], k);
621            }
622        }
623
624        // Add the next merged BAM record to the depth plot
625        if ((ret = add_depth(opt, &dh, h[i], b[i], clip, i)) < 0) {
626            ret = -1;
627            goto err;
628        }
629
630        // Populate next record from this file
631        for(;!finished[i];) {
632            ret = itr && itr[i]
633                ? sam_itr_next(fp[i], itr[i], b[i])
634                : sam_read1(fp[i], h[i], b[i]);
635            if (ret < -1) {
636                ret = -1;
637                goto err;
638            }
639            if (ret == -1) {
640                to_go--;
641                finished[i] = 1;
642                break;
643            }
644
645            if (b[i]->core.tid < 0)
646                continue;
647            if (b[i]->core.flag & opt->flag)
648                continue; // must have none of the flags set
649            if (opt->incl_flag && (b[i]->core.flag & opt->incl_flag) == 0)
650                continue; // must have at least one flag set
651            if ((b[i]->core.flag & opt->require_flag) != opt->require_flag)
652                continue; // must have all lags set
653            if (b[i]->core.qual < opt->min_mqual)
654                continue;
655
656            if (opt->min_len) {
657                if (qlen_used(b[i]) < opt->min_len)
658                    continue;
659            }
660
661            break;
662        }
663    }
664
665    // Tidy up end.
666    ret = add_depth(opt, &dh, h[0], NULL, 0, 0);
667    err = 0;
668
669 err:
670    if (ret == 0 && err)
671        ret = -1;
672
673    for (i = 0; i < nfiles; i++) {
674        if (b[i])
675            bam_destroy1(b[i]);
676        if (dh.hist && dh.hist[i])
677            free(dh.hist[i]);
678    }
679    free(b);
680    free(finished);
681    ks_free(&dh.ks);
682    free(dh.hist);
683    free(dh.end_pos);
684    if (overlaps) {
685        khiter_t k;
686        for (i = 0; i < nfiles; i++) {
687            if (!overlaps[i])
688                continue;
689            for (k = kh_begin(overlaps[i]); k < kh_end(overlaps[i]); k++)
690                if (kh_exist(overlaps[i], k))
691                    free((char *)kh_key(overlaps[i], k));
692            kh_destroy(olap_hash, overlaps[i]);
693        }
694        free(overlaps);
695    }
696
697    return ret;
698}
699
700static void usage_exit(FILE *fp, int exit_status)
701{
702    fprintf(fp, "Usage: samtools depth [options] in.bam [in.bam ...]\n");
703    fprintf(fp, "\nOptions:\n");
704    fprintf(fp, "  -a           Output all positions (including zero depth)\n");
705    fprintf(fp, "  -a -a, -aa   Output absolutely all positions, including unused ref seqs\n");
706    fprintf(fp, "  -r REG       Specify a region in chr or chr:from-to syntax\n");
707    fprintf(fp, "  -b FILE      Use bed FILE for list of regions\n");
708    fprintf(fp, "  -f FILE      Specify list of input BAM/SAM/CRAM filenames\n");
709    fprintf(fp, "  -X           Use custom index files (in -X *.bam *.bam.bai order)\n");
710    fprintf(fp, "  -g INT       Remove specified flags from default filter-out flag list\n");
711    fprintf(fp, "  -G, --excl-flags FLAGS\n");
712    fprintf(fp, "               Add specified flags to the  default filter-out flag list\n");
713    fprintf(fp, "               [UNMAP,SECONDARY,QCFAIL,DUP]\n");
714    fprintf(fp, "      --incl-flags FLAGS\n");
715    fprintf(fp, "               Only include records with at least one the FLAGs present [0]\n");
716    fprintf(fp, "      --require-flags FLAGS\n");
717    fprintf(fp, "               Only include records with all of the FLAGs present [0]\n");
718    fprintf(fp, "  -H           Print a file header line\n");
719    fprintf(fp, "  -l INT       Minimum read length [0]\n");
720    fprintf(fp, "  -o FILE      Write output to FILE [stdout]\n");
721    fprintf(fp, "  -q, --min-BQ INT\n"
722                "               Filter bases with base quality smaller than INT [0]\n");
723    fprintf(fp, "  -Q, --min-MQ INT\n"
724                "               Filter alignments with mapping quality smaller than INT [0]\n");
725    fprintf(fp, "  -J           Include reads with deletions in depth computation\n");
726    fprintf(fp, "  -s           Do not count overlapping reads within a template\n");
727    sam_global_opt_help(fp, "-.--.@-.");
728    exit(exit_status);
729}
730
731int main_depth(int argc, char *argv[])
732{
733    int nfiles, i, tmp_flag;
734    samFile **fp;
735    sam_hdr_t **header;
736    int c, has_index_file = 0;
737    char *file_list = NULL, **fn = NULL;
738    char *out_file = NULL;
739    depth_opt opt = {
740        .flag = BAM_FUNMAP | BAM_FSECONDARY | BAM_FDUP | BAM_FQCFAIL,
741        .incl_flag = 0,
742        .require_flag = 0,
743        .min_qual = 0,
744        .min_mqual = 0,
745        .skip_del = 1,
746        .header = 0,
747        .min_len = 0,
748        .out = stdout,
749        .all_pos = 0,
750        .remove_overlaps = 0,
751        .reg = NULL,
752        .bed = NULL,
753    };
754
755    sam_global_args ga = SAM_GLOBAL_ARGS_INIT;
756    static const struct option lopts[] = {
757        {"min-MQ",        required_argument, NULL, 'Q'},
758        {"min-mq",        required_argument, NULL, 'Q'},
759        {"min-BQ",        required_argument, NULL, 'q'},
760        {"min-bq",        required_argument, NULL, 'q'},
761        {"excl-flags",    required_argument, NULL, 'G'},
762        {"incl-flags",    required_argument, NULL, 1},
763        {"require-flags", required_argument, NULL, 2},
764        SAM_OPT_GLOBAL_OPTIONS('-', 0, '-', '-', 0, '@'),
765        {NULL, 0, NULL, 0}
766    };
767
768    while ((c = getopt_long(argc, argv, "@:q:Q:JHd:m:l:g:G:o:ar:Xf:b:s",
769                            lopts, NULL)) >= 0) {
770        switch (c) {
771        case 'a':
772            opt.all_pos++;
773            break;
774
775        case 'b':
776            opt.bed = bed_read(optarg);
777            if (!opt.bed) {
778                print_error_errno("depth", "Could not read file \"%s\"",
779                                  optarg);
780                return 1;
781            }
782            break;
783
784        case 'f':
785            file_list = optarg;
786            break;
787
788        case 'd':
789        case 'm':
790            // depth limit - now ignored
791            break;
792
793        case 'g':
794            tmp_flag = bam_str2flag(optarg);
795
796            if (tmp_flag < 0) {
797                print_error("depth", "Unknown flag '%s'", optarg);
798                return 1;
799            }
800
801            opt.flag &= ~tmp_flag;
802            break;
803        case 'G': // reject if any set
804            tmp_flag = bam_str2flag(optarg);
805
806            if (tmp_flag < 0) {
807                print_error("depth", "Unknown flag '%s'", optarg);
808                return 1;
809            }
810
811            opt.flag |= tmp_flag;
812            break;
813        case 1: // reject unless at least one set (0 means ignore option)
814            tmp_flag = bam_str2flag(optarg);
815
816            if (tmp_flag < 0) {
817                print_error("depth", "Unknown flag '%s'", optarg);
818                return 1;
819            }
820
821            opt.incl_flag |= tmp_flag;
822            break;
823        case 2: // reject unless all set
824            tmp_flag = bam_str2flag(optarg);
825
826            if (tmp_flag < 0) {
827                print_error("depth", "Unknown flag '%s'", optarg);
828                return 1;
829            }
830
831            opt.require_flag |= tmp_flag;
832            break;
833
834        case 'l':
835            opt.min_len = atoi(optarg);
836            break;
837
838        case 'H':
839            opt.header = 1;
840            break;
841
842        case 'q':
843            opt.min_qual = atoi(optarg);
844            break;
845        case 'Q':
846            opt.min_mqual = atoi(optarg);
847            break;
848
849        case 'J':
850            opt.skip_del = 0;
851            break;
852
853        case 'o':
854            if (opt.out != stdout)
855                break;
856            opt.out = fopen(out_file = optarg, "w");
857            if (!opt.out) {
858                print_error_errno("depth", "Cannot open \"%s\" for writing.",
859                                  optarg);
860                return EXIT_FAILURE;
861            }
862            break;
863
864        case 'r':
865            opt.reg = optarg;
866            break;
867
868        case 's':
869            opt.remove_overlaps = 1;
870            break;
871
872        case 'X':
873            has_index_file = 1;
874            break;
875
876        default:  if (parse_sam_global_opt(c, optarg, lopts, &ga) == 0) break;
877            /* else fall-through */
878        case '?':
879            usage_exit(stderr, EXIT_FAILURE);
880        }
881    }
882
883    if (argc < optind+1 && !file_list) {
884        if (argc == optind)
885            usage_exit(stdout, EXIT_SUCCESS);
886        else
887            usage_exit(stderr, EXIT_FAILURE);
888    }
889
890    if (file_list) {
891        if (has_index_file) {
892            print_error("depth", "The -f option cannot be combined with -X");
893            return 1;
894        }
895        if (read_file_list(file_list, &nfiles, &fn))
896            return 1;
897        argv = fn;
898        argc = nfiles;
899        optind = 0;
900    } else {
901        nfiles = argc - optind;
902    }
903
904    if (has_index_file) {
905        if (nfiles%1) {
906            print_error("depth", "-X needs one index specified per bam file");
907            return 1;
908        }
909        nfiles /= 2;
910    }
911    fp = malloc(nfiles * sizeof(*fp));
912    header = malloc(nfiles * sizeof(*header));
913    if (!fp || !header) {
914        print_error_errno("depth", "Out of memory");
915        return 1;
916    }
917
918    hts_itr_t **itr = NULL;
919    if (opt.reg) {
920        itr = calloc(nfiles, sizeof(*itr));
921        if (!itr)
922            return 1;
923    }
924
925    for (i = 0; i < nfiles; i++, optind++) {
926        fp[i] = sam_open_format(argv[optind], "r", &ga.in);
927        if (fp[i] == NULL) {
928            print_error_errno("depth",
929                              "Cannot open input file \"%s\"", argv[optind]);
930            return 1;
931        }
932
933        if (ga.nthreads > 0)
934            hts_set_threads(fp[i], ga.nthreads);
935
936        if (hts_set_opt(fp[i], CRAM_OPT_REQUIRED_FIELDS,
937                        SAM_FLAG | SAM_RNAME | SAM_POS | SAM_CIGAR
938                        | (opt.remove_overlaps ? SAM_QNAME|SAM_RNEXT|SAM_PNEXT
939                                               : 0)
940                        | (opt.min_mqual       ? SAM_MAPQ  : 0)
941                        | (opt.min_len         ? SAM_SEQ   : 0)
942                        | (opt.min_qual        ? SAM_QUAL  : 0))) {
943            fprintf(stderr, "Failed to set CRAM_OPT_REQUIRED_FIELDS value\n");
944            return 1;
945        }
946
947        if (hts_set_opt(fp[i], CRAM_OPT_DECODE_MD, 0)) {
948            fprintf(stderr, "Failed to set CRAM_OPT_DECODE_MD value\n");
949            return 1;
950        }
951
952        // FIXME: what if headers differ?
953        header[i] = sam_hdr_read(fp[i]);
954        if (header == NULL) {
955            fprintf(stderr, "Failed to read header for \"%s\"\n",
956                    argv[optind]);
957            return 1;
958        }
959
960        if (opt.reg) {
961            hts_idx_t *idx = has_index_file
962                ? sam_index_load2(fp[i], argv[optind], argv[optind+nfiles])
963                : sam_index_load(fp[i], argv[optind]);
964            if (!idx) {
965                print_error("depth", "cannot load index for \"%s\"",
966                            argv[optind]);
967                return 1;
968            }
969            if (!(itr[i] = sam_itr_querys(idx, header[i], opt.reg))) {
970                print_error("depth", "cannot parse region \"%s\"", opt.reg);
971                return 1;
972            }
973            hts_idx_destroy(idx);
974        }
975    }
976
977    int ret = fastdepth_core(&opt, nfiles, &argv[argc-nfiles], fp, itr, header)
978        ? 1 : 0;
979
980    for (i = 0; i < nfiles; i++) {
981        sam_hdr_destroy(header[i]);
982        sam_close(fp[i]);
983        if (itr && itr[i])
984            hts_itr_destroy(itr[i]);
985    }
986    free(header);
987    free(fp);
988    free(itr);
989    if (file_list) {
990        for (i=0; i<nfiles; i++)
991            free(fn[i]);
992        free(fn);
993    }
994    if (opt.bed)
995        bed_destroy(opt.bed);
996    sam_global_args_free(&ga);
997    if (opt.out != stdout) {
998        if (fclose(opt.out) != 0 && ret == 0) {
999            print_error_errno("depth", "error on closing \"%s\"", out_file);
1000            ret = 1;
1001        }
1002    }
1003
1004    return ret;
1005}
1006
1007#ifdef _MAIN_BAM2DEPTH
1008int main(int argc, char *argv[])
1009{
1010    return main_depth(argc, argv);
1011}
1012#endif