<commit_before>package quic

import (
	"errors"

	"github.com/lucas-clemente/quic-go/frames"
	"github.com/lucas-clemente/quic-go/protocol"
	"github.com/lucas-clemente/quic-go/qerr"
	"github.com/lucas-clemente/quic-go/utils"
)

type streamFrameSorter struct {
	queuedFrames map[protocol.ByteCount]*frames.StreamFrame
	readPosition protocol.ByteCount
	gaps         *utils.ByteIntervalList
}

var (
	errTooManyGapsInReceivedStreamData = errors.New("Too many gaps in received StreamFrame data")
	errDuplicateStreamData             = errors.New("Overlapping Stream Data")
	errEmptyStreamData                 = errors.New("Stream Data empty")
)

func newStreamFrameSorter() *streamFrameSorter {
	s := streamFrameSorter{
		gaps:         utils.NewByteIntervalList(),
		queuedFrames: make(map[protocol.ByteCount]*frames.StreamFrame),
	}
	s.gaps.PushFront(utils.ByteInterval{Start: 0, End: protocol.MaxByteCount})
	return &s
}

func (s *streamFrameSorter) Push(frame *frames.StreamFrame) error {
	_, ok := s.queuedFrames[frame.Offset]
	if ok {
		return errDuplicateStreamData
	}

	start := frame.Offset
	end := frame.Offset + frame.DataLen()

	if start == end {
		if frame.FinBit {
			s.queuedFrames[frame.Offset] = frame
			return nil
		}
		return errEmptyStreamData
	}

	var foundInGap bool

	for gap := s.gaps.Front(); gap != nil; gap = gap.Next() {
		// the complete frame lies before or after the gap
		if end <= gap.Value.Start || start > gap.Value.End {
			continue
		}

		if start < gap.Value.Start {
			return qerr.Error(qerr.OverlappingStreamData, "start of gap in stream chunk")
		}

		if start < gap.Value.End && end > gap.Value.End {
			return qerr.Error(qerr.OverlappingStreamData, "end of gap in stream chunk")
		}

		foundInGap = true

		if start == gap.Value.Start {
			if end == gap.Value.End {
				s.gaps.Remove(gap)
				break
			}
			if end < gap.Value.End {
				gap.Value.Start = end
				break
			}
		}

		if end == gap.Value.End {
			gap.Value.End = start
			break
		}

		if end < gap.Value.End {
			intv := utils.ByteInterval{Start: end, End: gap.Value.End}
			s.gaps.InsertAfter(intv, gap)
			gap.Value.End = start
			break
		}
	}

	if !foundInGap {
		return errDuplicateStreamData
	}

	if s.gaps.Len() > protocol.MaxStreamFrameSorterGaps {
		return errTooManyGapsInReceivedStreamData
	}

	s.queuedFrames[frame.Offset] = frame
	return nil<commit_msg>code refactoring in streamFrameSorter<commit_after>package quic

import (
	"errors"

	"github.com/lucas-clemente/quic-go/frames"
	"github.com/lucas-clemente/quic-go/protocol"
	"github.com/lucas-clemente/quic-go/qerr"
	"github.com/lucas-clemente/quic-go/utils"
)

type streamFrameSorter struct {
	queuedFrames map[protocol.ByteCount]*frames.StreamFrame
	readPosition protocol.ByteCount
	gaps         *utils.ByteIntervalList
}

var (
	errTooManyGapsInReceivedStreamData = errors.New("Too many gaps in received StreamFrame data")
	errDuplicateStreamData             = errors.New("Duplicate Stream Data")
	errEmptyStreamData                 = errors.New("Stream Data empty")
)

func newStreamFrameSorter() *streamFrameSorter {
	s := streamFrameSorter{
		gaps:         utils.NewByteIntervalList(),
		queuedFrames: make(map[protocol.ByteCount]*frames.StreamFrame),
	}
	s.gaps.PushFront(utils.ByteInterval{Start: 0, End: protocol.MaxByteCount})
	return &s
}

func (s *streamFrameSorter) Push(frame *frames.StreamFrame) error {
	if frame.DataLen() == 0 {
		if frame.FinBit {
			s.queuedFrames[frame.Offset] = frame
			return nil
		}
		return errEmptyStreamData
	}

	if _, ok := s.queuedFrames[frame.Offset]; ok {
		return errDuplicateStreamData
	}

	start := frame.Offset
	end := frame.Offset + frame.DataLen()

	if end <= s.gaps.Front().Value.Start {
		return errDuplicateStreamData
	}

	// skip all gaps that are before this stream frame
	var gap *utils.ByteIntervalElement
	for gap = s.gaps.Front(); gap != nil; gap = gap.Next() {
		if end > gap.Value.Start && start <= gap.Value.End {
			break
		}
	}

	if gap == nil {
		return errors.New("StreamFrameSorter BUG: no gap found")
	}

	if start < gap.Value.Start {
		return qerr.Error(qerr.OverlappingStreamData, "start of gap in stream chunk")
	}

	if end > gap.Value.End {
		return qerr.Error(qerr.OverlappingStreamData, "end of gap in stream chunk")
	}

	if start == gap.Value.Start {
		if end == gap.Value.End {
			// the frame completely fills this gap
			// delete the gap
			s.gaps.Remove(gap)
		} else if end < gap.Value.End {
			// the frame covers the beginning of the gap
			// adjust the Start value to shrink the gap
			gap.Value.Start = end
		}
	} else if end == gap.Value.End {
		// the frame covers the end of the gap
		// adjust the End value to shrink the gap
		gap.Value.End = start
	} else {
		// the frame lies within the current gap, splitting it into two
		// insert a new gap and adjust the current one
		intv := utils.ByteInterval{Start: end, End: gap.Value.End}
		s.gaps.InsertAfter(intv, gap)
		gap.Value.End = start
	}

	if s.gaps.Len() > protocol.MaxStreamFrameSorterGaps {
		return errTooManyGapsInReceivedStreamData
	}

	s.queuedFrames[frame.Offset] = frame
	return nil
{'fraction_non_alphanumeric': 0.11317799099275504, 'fraction_numerical': 0.0005874290189935383, 'mean_word_length': 3.4533565823888406, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4974594', 'n_tokens_mistral': 1912, 'n_tokens_neox': 1751, 'n_words': 413}