☰

이진 검색이 실패한 행

tag-icon • tag-icon shell-script text-processing search split
이진 검색이 실패한 행

gitbisect run어느 버전에서 버그가 발생했는지 알아 내야 합니다 .

대용량 파일(100GB)이 있는데 적어도 한 줄 이상은 불량인데, 확인해야 하는 프로그램이 어떤 줄인지 알려주지 않습니다.

행은 레코드이므로 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

경고: 이렇게 하면 이등분된 데이터가 모두 저장됩니다 /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 행을 식별합니다 . 두 가지 이진 검색을 수행하여 이를 수행합니다. 먼저 X=1을 유지하고 Y를 검색하므로 1..Y가 실패하는 가장 작은 Y를 찾습니다 myprogram. 그런 다음 Y를 유지하고 X를 검색하여 myprogram실패한 X..Y를 찾습니다.

부분 실패가 여러 개 있는 경우 myprogram그 중 하나만 인식됩니다.

답변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

관련 정보