☰

バイナリ検索に失敗した行

tag-icon • tag-icon shell-script text-processing search split
バイナリ検索に失敗した行

gitbisect runどのバージョンでバグが発生したかを調べる必要があります。

大容量ファイル（100GB）がありますが、少なくとも1行以上は不良ですが、確認する必要があるプログラムがどの行かを教えてくれません。

行はレコードなので、headandと（前半をプログラムに渡し、エラーがない場合は後半）を使用してtailバイナリ検索を作成し、それに基づいて後半を再分割できます。/2

しかし、私の介入なしにこれを行うことができる自動化されたツール（と同様git bisect run）はすでにありますか？

答え1

以下を使用してファイルを複数の部分に分割することができsplit、行ごとにのみ分割するオプションがあります。

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

これは実際にはファイルにのみ意味があります。できる行に分割して設定すると、テキストファイルでのみ機能します。

これにより、次のような独自の二分法ツールを簡単に作成できます。

#!/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

警告：これを行うと、2等分されたデータがすべて保存されます/tmp（これが気に入らない場合は、BISECTDIRの定義を変更してください）。また、最後に二等分されたデータファイルのみがクリーンアップされます。だから十分なスペースが必要かもしれません...

答え2

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

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

myprogram失敗したX..Y行を識別します。 2つのバイナリ検索を実行してこれを行います。まず、X = 1を維持してYを検索するので、1..Yが失敗する最小のYを探しますmyprogram。次に Y を維持し、X を検索してmyprogram失敗した X..Y を探します。

部分的な失敗が複数ある場合、そのうちのmyprogram1つだけが認識されます。

答え3

たった一つ終わった普遍的な二等分ツール、Bashで書かれ、徹底的なテストを受けました。現在のコード：

#!/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

関連情報