3

git has bisect run to figure out which revision an error was introduced.

I have a big file (100GB) and at least one of the lines is bad, but the program I have to check it with will not tell me which line.

The lines are records, so I can write a binary search using head and tail and /2 (passing the first half to the program, and if no errors, the second half), and based on that splitting the one half again.

But does an automated tool already exist that can do this without my intervention (similar to git bisect run)?

3
  • What kind of file? Source code? Plain text?
    – kurtm
    Oct 16, 2013 at 13:50
  • Plain text: Each line is a full record.
    – Ole Tange
    Oct 16, 2013 at 14:27
  • I suggest looking into git-bisect.sh from git repository instead and modifying the code to suit your need.
    – Ivan Chau
    Oct 17, 2013 at 2:18

3 Answers 3

2

you can use split to split a file into multiple parts, and it has an option to only split at lines:

$ ls
bigfile
$ split -n l/2 bigfile
$ ls
bigfile xaa xab

this really only makes sense if the file can be split and is organized in lines, which is only true for textfiles.

with this you can easily build your own bisect-tool, e.g. something like the following:

#!/bin/sh

TESTPROG=$1
DATA=$2

usage() {
    echo "usage: $0 <testprog> <datafile>"
    echo "     will bisect <datafile> to the single line where <testprog> exits with '0'"
    exit 1
}

if [ ! -x "${TESTPROG}" ]; then  usage; fi
if [ ! -e "${DATA}" ]    ; then  usage; fi

BISECTDIR=$(mktemp -d)

splitfiles() {
    split -e -n l/2 $1 ${BISECTDIR}/$2bisect_
    echo ${BISECTDIR}/$2bisect_*
}
cleanup() {
    rm -rf "${BISECTDIR}"
    exit 0
}

i=1
while [ $(head -2 "${DATA}" | wc -l) -gt 1 ]; do
  echo "testing: ${DATA} $(head -2 "${DATA}" | wc -l)" 1>&2
  files=$(splitfiles ${DATA} ${i})
  count=$(echo $files | awk '{print NF}')
  if [  ${count} -lt 2 ]; then
      cat $files
      cleanup
  fi
  DATA=""
  for f in $files; do
          if ${TESTPROG} "${f}" 1>/dev/null 2>/dev/null; then
          DATA="${f}"
          break
      fi
  done
  i=$(( i+1 ))
done

cleanup

caveat: this will put all the bisected data into /tmp (change the definition of BISECTDIR is you don't like that); also this will only cleanup the bisected data files at the end. so you might need plenty of space...

2
  • What I am looking for is a bigger tool - similar to 'git bisect run' that will do the splitting and testing without my intervention.
    – Ole Tange
    Oct 16, 2013 at 13:14
  • @OleTange i've updated my answer to include such a tool written in bash.
    – umläute
    Oct 17, 2013 at 14:27
0

https://gitlab.com/ole.tange/tangetools/-/tree/master/find-first-fail

find-first-fail -f 100g.file -v myprogram

It will identify lines X..Y where myprogram fails. It does that with 2 binary searches: First it keeps X=1 and searches for Y, so it finds the minimal Y where myprogram fails for 1..Y. Then it keeps Y and searches for X, thus finding X..Y where myprogram fails.

If there are multiple sections where myprogram fails, it will only identify one of them.

1
  • . $(which find-first-fail) should be . find-first-fail in POSIX shells whose . is require to look for /-less files in $PATH. which is very unportable. You may want to use command -v instead, but like most which implementations, that only finds executable files. In any case leaving that command substitution unquoted doesn't make sense. Mar 19, 2023 at 10:45
0

Just finished a generic bisect tool, written in Bash and thoroughly tested. The code right now:

#!/usr/bin/env bash

set -o errexit -o noclobber -o nounset -o pipefail
shopt -s failglob inherit_errexit

next_file="$2"
entries_checked=0

cleanup() {
    if (("${DEBUG-0}" > 0)); then
        printf 'Number of entries checked: %d.\n' "$entries_checked" >&2
    fi
    rm --force --recursive "$work_dir"
}
work_dir="$(mktemp --directory)"
trap cleanup EXIT

while true; do
    ((++entries_checked))
    if (("${DEBUG-0}" > 0)); then
        printf 'Remaining entry count: %d.\n' "$(wc --lines < "$next_file")" >&2
    fi
    split_prefix="${work_dir}/${entries_checked}-"
    split --elide-empty-files --number=l/2 "$next_file" "$split_prefix"
    split_files=("$split_prefix"*)
    if (("${DEBUG-0}" > 1)); then
        printf 'First split file entry count: %d.\n' "$(wc --lines < "${split_files[0]}")" >&2
    fi
    if [[ -v split_files[1] ]]; then
        if (("${DEBUG-0}" > 1)); then
            printf 'Second split file entry count: %d.\n' "$(wc --lines < "${split_files[1]}")" >&2
        fi
    fi

    entry="$(tail --lines=1 "${split_files[0]}")"
    if (("${DEBUG-0}" > 1)); then
        printf 'Checking entry: “%s”.\n' "$entry" >&2
    fi

    if ENTRY="$entry" "$SHELL" <<< "$1"; then
        if (("${DEBUG-0}" > 1)); then
            printf 'Command successful.\n' >&2
        fi

        rm "${split_files[0]}"

        if ! [[ -v split_files[1] ]]; then
            echo 'No insertion point found.' >&2
            exit 3
        fi
        next_file="${split_files[1]}"
    else
        if (("${DEBUG-0}" > 1)); then
            printf 'Command failed.\n' >&2
        fi

        first_bad_entry="$entry"

        if [[ -v split_files[1] ]]; then
            rm "${split_files[1]}"
        fi
        next_file="${split_files[0]}"
        if (("$(head --lines=2 "$next_file" | wc --lines)" == 1)); then
            printf '%s\n' "$first_bad_entry"
            exit
        fi
    fi
done

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .