// makeRange returns a range filter for Elasticsearch given the 3 nodes that
// make up a comparison.
509336
func makeRange(lhs *gentypes.FieldType, op lex.TokenType, rhs expr.Node) (interface{}, error) {

	rhsval, ok := scalar(rhs)
	if !ok {
		return nil, fmt.Errorf("unsupported type for comparison: %T", rhs)
	}

	rhv := value.NewValue(rhsval)

	u.Debugf("makeRange:  lh:%+v %v  %v", lhs, rhsval, rhs)
	// Convert scalars to correct type
	switch lhs.Type {
	case value.IntType, value.MapIntType:
		// TODO:  we might need to change the operator???
		//  given lh identity "purchase_count" = int = 10
		//  right hand side = float 9.7
		iv, ok := value.ValueToInt64(rhv)
		if !ok {
			return nil, fmt.Errorf("Could not convert %T %v to int", rhsval, rhsval)
		}
		rhsval = iv
	case value.NumberType, value.MapNumberType:
		fv, ok := value.ValueToFloat64(rhv)
		if !ok {
			return nil, fmt.Errorf("Could not convert %T %v to float", rhsval, rhsval)
		}
		rhsval = fv
	default:
		if rhsstr, ok := rhsval.(string); ok {
			if rhsf, err := strconv.ParseFloat(rhsstr, 64); err == nil {
				// rhsval can be converted to a float!
				rhsval = rhsf
			}
		}
	}

	/*
		"nested": {
			"query": {
			    "term": {
			        "map_actioncounts.k": "Web hit"
			    }
			},
			"path": "map_actioncounts"
		}

		"nested": {
			"query": {
			    "bool": {
			      "must": [
			          {
			              "term": {
			                  "mapvals_fields.k": "has_data"
			              }
			          },
			          {
			              "term": {
			                  "mapvals_fields.b": true
			              }
			          }
			      ]
			    }
			},
			"path": "mapvals_fields"
		}
		"nested": {
			"query": {
				"bool": {
					"must": [
						{
							"term": {
								"k": "open"
							}
						},
						{
							"range": {
								"f": {"gte": 7}
							}
						}
					]
				}
			},
			"path": "map_events"
		}
		q = esMap{"nested": esMap{"path": parent, "filter": esMap{"and": []esMap{
					{"term": esMap{parent + ".k": child}},
					{"range": esMap{parent + valuePath: esMap{esRangeOps[seg.SegType]: rhsNum}}},
				}}}}
	*/

	fieldName := lhs.Field
	if lhs.Nested() {
		fieldName, rhsval = lhs.PrefixAndValue(rhsval)
	}
	r := &RangeFilter{}
	switch op {
	case lex.TokenGE:
		r.Range = map[string]RangeQry{fieldName: {GTE: rhsval}}
	case lex.TokenLE:
		r.Range = map[string]RangeQry{fieldName: {LTE: rhsval}}
	case lex.TokenGT:
		r.Range = map[string]RangeQry{fieldName: {GT: rhsval}}
	case lex.TokenLT:
		r.Range = map[string]RangeQry{fieldName: {LT: rhsval}}
	default:
		return nil, fmt.Errorf("qlindex: unsupported range operator %s", op)
	}
	if lhs.Nested() {
		return Nested(lhs, r), nil
	}
	return r, nil
}
1179691
func (ac *arrayContainer) iremoveRange(firstOfRange, endx int) container {
	if firstOfRange >= endx {
		return ac
	}
	indexstart := binarySearch(ac.content, uint16(firstOfRange))
	if indexstart < 0 {
		indexstart = -indexstart - 1
	}
	indexend := binarySearch(ac.content, uint16(endx-1))
	if indexend < 0 {
		indexend = -indexend - 1
	} else {
		indexend++
	}
	rangelength := indexend - indexstart
	answer := ac
	copy(answer.content[indexstart:], ac.content[indexstart+rangelength:])
	answer.content = answer.content[:ac.getCardinality()-rangelength]
	return answer
}
49059
func (p *Polygon) initEdgesAndIndex() {
	if p.IsFull() {
		return
	}
	const maxLinearSearchLoops = 12 // Based on benchmarks.
	if len(p.loops) > maxLinearSearchLoops {
		p.cumulativeEdges = make([]int, 0, len(p.loops))
	}

	for _, l := range p.loops {
		if p.cumulativeEdges != nil {
			p.cumulativeEdges = append(p.cumulativeEdges, p.numEdges)
		}
		p.numEdges += len(l.vertices)
	}

	p.index = NewShapeIndex()
	p.index.Add(p)
}
635224
func ParseRange(value string) (*Range, error) {
	value = strings.TrimSpace(value)
	b := &rangeBuilder{}
	if value == "" {
		return b.Range()
	}
	parts := strings.Split(value, "-")
	switch len(parts) {
	case 1:
		num, err := parseInt(parts[0])
		return b.from(num, err).to(num, err).Range()
	case 2:
		if parts[0] != "" {
			b.from(parseInt(parts[0]))
		}
		if parts[1] != "" {
			b.to(parseInt(parts[1]))
		}
		return b.Range()
	default:
		return nil, &ErrParseRange{}
	}
}
1212144
func (s *ShapeIndex) skipCellRange(begin, end CellID, t *tracker, disjointFromIndex bool) {
	// If we aren't in the interior of a shape, then skipping over cells is easy.
	if len(t.shapeIDs) == 0 {
		return
	}

	// Otherwise generate the list of cell ids that we need to visit, and create
	// an index entry for each one.
	skipped := CellUnionFromRange(begin, end)
	for _, cell := range skipped {
		var clippedEdges []*clippedEdge
		s.updateEdges(PaddedCellFromCellID(cell, cellPadding), clippedEdges, t, disjointFromIndex)
	}
}
897114
func (d *ChainDescriber) MakeGraph() (osgraph.Graph, error) {
	g := osgraph.New()

	loaders := []GraphLoader{}
	for namespace := range d.namespaces {
		klog.V(4).Infof("Loading build configurations from %q", namespace)
		loaders = append(loaders, &bcLoader{namespace: namespace, lister: d.c})
	}
	loadingFuncs := []func() error{}
	for _, loader := range loaders {
		loadingFuncs = append(loadingFuncs, loader.Load)
	}

	if errs := parallel.Run(loadingFuncs...); len(errs) > 0 {
		return g, utilerrors.NewAggregate(errs)
	}

	for _, loader := range loaders {
		loader.AddToGraph(g)
	}

	buildedges.AddAllInputOutputEdges(g)

	return g, nil
}
791787
func MakeRequest(request rest.Request) (*rest.Response, error) {
	return DefaultClient.Send(request)
}
786618
func maxRange(root, left, right *Node) Comparable {
	end := root.Elem.End()
	if left != nil && left.Range.End().Compare(end) > 0 {
		end = left.Range.End()
	}
	if right != nil && right.Range.End().Compare(end) > 0 {
		end = right.Range.End()
	}
	return end
}
865964
func makeReadCloser(r io.Reader, c io.Closer) io.ReadCloser {
	rc := struct {
		io.Reader
		io.Closer
	}{r, c}
	return io.ReadCloser(rc)
}
240992
func (n *Mounter) MakeRShared(path string) error {
	return mount.DoMakeRShared(path, hostProcMountinfoPath)
}
473847
func (l *WAL) DeleteRange(keys [][]byte, min, max int64) (int, error) {
	if len(keys) == 0 {
		return 0, nil
	}
	entry := &DeleteRangeWALEntry{
		Keys: keys,
		Min:  min,
		Max:  max,
	}

	id, err := l.writeToLog(entry)
	if err != nil {
		return -1, err
	}
	return id, nil
}
38110
func GraphToRanges(path []Edge) []TextRange {
	ranges := make([]TextRange, len(path))
	j := len(ranges) - 1
	for e := len(path) - 1; e > 0; {
		s := path[e].S
		ranges[j] = TextRange{s, e, path[e].EdgeType}
		j--
		e = s
	}
	return ranges[j+1:]
}
46205
func (e *Engine) DeleteBucketRange(name []byte, min, max int64) error {
	// TODO(jeff): we need to block writes to this prefix while deletes are in progress
	// otherwise we can end up in a situation where we have staged data in the cache or
	// WAL that was deleted from the index, or worse. This needs to happen at a higher
	// layer.

	// TODO(jeff): ensure the engine is not closed while we're running this. At least
	// now we know that the series file or index won't be closed out from underneath
	// of us.

	// Ensure that the index does not compact away the measurement or series we're
	// going to delete before we're done with them.
	e.index.DisableCompactions()
	defer e.index.EnableCompactions()
	e.index.Wait()

	// Disable and abort running compactions so that tombstones added existing tsm
	// files don't get removed. This would cause deleted measurements/series to
	// re-appear once the compaction completed. We only disable the level compactions
	// so that snapshotting does not stop while writing out tombstones. If it is stopped,
	// and writing tombstones takes a long time, writes can get rejected due to the cache
	// filling up.
	e.disableLevelCompactions(true)
	defer e.enableLevelCompactions(true)

	e.sfile.DisableCompactions()
	defer e.sfile.EnableCompactions()

	// TODO(jeff): are the query language values still a thing?
	// Min and max time in the engine are slightly different from the query language values.
	if min == influxql.MinTime {
		min = math.MinInt64
	}
	if max == influxql.MaxTime {
		max = math.MaxInt64
	}

	// Run the delete on each TSM file in parallel and keep track of possibly dead keys.

	// TODO(jeff): keep a set of keys for each file to avoid contention.
	// TODO(jeff): come up with a better way to figure out what keys we need to delete
	// from the index.

	var possiblyDead struct {
		sync.RWMutex
		keys map[string]struct{}
	}
	possiblyDead.keys = make(map[string]struct{})

	if err := e.FileStore.Apply(func(r TSMFile) error {
		return r.DeletePrefix(name, min, max, func(key []byte) {
			possiblyDead.Lock()
			possiblyDead.keys[string(key)] = struct{}{}
			possiblyDead.Unlock()
		})
	}); err != nil {
		return err
	}

	var deleteKeys [][]byte

	// ApplySerialEntryFn cannot return an error in this invocation.
	_ = e.Cache.ApplyEntryFn(func(k []byte, _ *entry) error {
		if bytes.HasPrefix(k, name) {
			if deleteKeys == nil {
				deleteKeys = make([][]byte, 0, 10000)
			}
			deleteKeys = append(deleteKeys, k)

			// we have to double check every key in the cache because maybe
			// it exists in the index but not yet on disk.
			possiblyDead.keys[string(k)] = struct{}{}
		}
		return nil
	})

	// Sort the series keys because ApplyEntryFn iterates over the keys randomly.
	bytesutil.Sort(deleteKeys)

	// Delete from the cache.
	e.Cache.DeleteBucketRange(name, min, max)

	// Now that all of the data is purged, we need to find if some keys are fully deleted
	// and if so, remove them from the index.
	if err := e.FileStore.Apply(func(r TSMFile) error {
		possiblyDead.RLock()
		defer possiblyDead.RUnlock()

		iter := r.Iterator(name)
		for i := 0; iter.Next(); i++ {
			key := iter.Key()
			if !bytes.HasPrefix(key, name) {
				break
			}

			// TODO(jeff): benchmark the locking here.
			if i%1024 == 0 { // allow writes to proceed.
				possiblyDead.RUnlock()
				possiblyDead.RLock()
			}

			if _, ok := possiblyDead.keys[string(key)]; ok {
				possiblyDead.RUnlock()
				possiblyDead.Lock()
				delete(possiblyDead.keys, string(key))
				possiblyDead.Unlock()
				possiblyDead.RLock()
			}
		}

		return iter.Err()
	}); err != nil {
		return err
	}

	// ApplySerialEntryFn cannot return an error in this invocation.
	_ = e.Cache.ApplyEntryFn(func(k []byte, _ *entry) error {
		if bytes.HasPrefix(k, name) {
			delete(possiblyDead.keys, string(k))
		}
		return nil
	})

	if len(possiblyDead.keys) > 0 {
		buf := make([]byte, 1024)

		// TODO(jeff): all of these methods have possible errors which opens us to partial
		// failure scenarios. we need to either ensure that partial errors here are ok or
		// do something to fix it.
		// TODO(jeff): it's also important that all of the deletes happen atomically with
		// the deletes of the data in the tsm files.

		// In this case the entire measurement (bucket) can be removed from the index.
		if min == math.MinInt64 && max == math.MaxInt64 {
			// The TSI index and Series File do not store series data in escaped form.
			name = models.UnescapeMeasurement(name)

			// Build up a set of series IDs that we need to remove from the series file.
			set := tsdb.NewSeriesIDSet()
			itr, err := e.index.MeasurementSeriesIDIterator(name)
			if err != nil {
				return err
			}

			var elem tsdb.SeriesIDElem
			for elem, err = itr.Next(); err != nil; elem, err = itr.Next() {
				if elem.SeriesID.IsZero() {
					break
				}

				set.AddNoLock(elem.SeriesID)
			}

			if err != nil {
				return err
			} else if err := itr.Close(); err != nil {
				return err
			}

			// Remove the measurement from the index before the series file.
			if err := e.index.DropMeasurement(name); err != nil {
				return err
			}

			// Iterate over the series ids we previously extracted from the index
			// and remove from the series file.
			set.ForEachNoLock(func(id tsdb.SeriesID) {
				if err = e.sfile.DeleteSeriesID(id); err != nil {
					return
				}
			})
			return err
		}

		// This is the slow path, when not dropping the entire bucket (measurement)
		for key := range possiblyDead.keys {
			// TODO(jeff): ugh reduce copies here
			keyb := []byte(key)
			keyb, _ = SeriesAndFieldFromCompositeKey(keyb)

			name, tags := models.ParseKeyBytes(keyb)
			sid := e.sfile.SeriesID(name, tags, buf)
			if sid.IsZero() {
				continue
			}

			if err := e.index.DropSeries(sid, keyb, true); err != nil {
				return err
			}

			if err := e.sfile.DeleteSeriesID(sid); err != nil {
				return err
			}
		}
	}

	return nil
}
302480
func (o *Operands) NinRange(from, to int64) bool {
	return o.T == 0 && from <= o.I && o.I <= to
}
453911
func (d *indirectIndex) OverlapsKeyPrefixRange(min, max []byte) bool {
	minKey, maxKey := d.minKey, d.maxKey
	if len(maxKey) > len(min) {
		maxKey = maxKey[:len(min)]
	}
	if len(minKey) > len(max) {
		minKey = minKey[:len(max)]
	}
	return bytes.Compare(minKey, max) <= 0 && bytes.Compare(maxKey, min) >= 0
}
941634
func (al *GraphQuery_AttemptRange) Normalize() error {
	if al.Quest == "" {
		return fmt.Errorf("must specify quest")
	}
	if al.Low == 0 {
		return fmt.Errorf("must specify low")
	}
	if al.High <= al.Low {
		return fmt.Errorf("high must be > low")
	}
	return nil
}
1187999
func (pdfa *ParametricDFA) isPrefixSink(state ParametricState, queryLen uint32) bool {
	if state.isDeadEnd() {
		return true
	}

	remOffset := queryLen - state.offset
	if remOffset < pdfa.diameter {
		stateDistances := pdfa.distance[pdfa.diameter*state.shapeID:]
		prefixDistance := stateDistances[remOffset]
		if prefixDistance > pdfa.maxDistance {
			return false
		}

		for _, d := range stateDistances {
			if d < prefixDistance {
				return false
			}
		}
		return true
	}
	return false
}