grange: github.com/xaviershay/grange Index | Files

package grange

import "github.com/xaviershay/grange"

Grange implements a modern subset of the range query language. It is an expressive grammar for selecting information out of arbitrary, self-referential metadata. It was developed for querying information about hosts across datacenters.

Basics

A range query operates on a state containing clusters.

state := grange.NewState()
state.AddCluster("a", Cluster{
  CLUSTER: []string{"a", "b", "c"},
  TYPE:    []string{"letters"},
})
result, err = state.Query("%a")      // "a", "b", "c"
result, err = state.Query("%a:KEYS") // "CLUSTER", "TYPE"
result, err = state.Query("%a:TYPE") // "letters"

Range also allows for a default cluster (traditionally named GROUPS), that can be accessed with some shortcut syntax, documented below.

Values can also be range expressions, so that clusters can be defined in terms of each other ("self-referential").

state := grange.NewState()
state.AddCluster("down", Cluster{ CLUSTER: []string{"host1"})
state.AddCluster("dc1",  Cluster{ CLUSTER: []string{"@dc1 - %down"})

result, err := state.Query("%dc1")  // "host2"

For an example usage of this library, see https://github.com/xaviershay/grange-server

Syntax

host1         - value constant, returns itself.
host1,host2   - union, concatenates both sides.
host1..3      - numeric expansion.
a{b,c}d       - brace expansion, works just like your shell.
(a,b) & a     - returns intersection of boths sides.
(a,b) - a     - returns left side minus right side.
/abc/         - regex match using RE2 semantics. When used on the right
                side of an operator, filters the left side values using the
                regex.  When used by itself, matches all values in the
                default cluster..
%dc1          - cluster lookup, returns the values at CLUSTER key in "dc1"
                cluster.
%dc1:KEYS     - returns all available keys for a cluster.
%dc1:SOMEKEY  - returns values at SOMEKEY key.
%dc1:{A,B}    - returns values at both A and B key. Query inside braces can
                be any range expression.
@dc1          - key lookup in default cluster, equivalent to %GROUPS:dc1.
$SOMEKEY      - Looks up values from SOMEKEY in the current cluster when
                used as a cluster value. When used at top-level, the
                default cluster is used.
?host1        - returns all keys in the default cluster that contain host1.
clusters(h1)  - returns all clusters for which the h1 is present in the
                CLUSTER key. Parameter can be any range expression.
has(KEY;val)  - returns all clusters with SOMEKEY matching value.
count(EXPR)   - returns the number of results returned by EXPR.
allclusters() - returns the names of all clusters
q(x://blah)   - quote a constant value, the parameter will be returned as
                is and not evaluated as a range expression. Useful for
                storing metadata in clusters.

All of the above can be combined to form highly expressive queries.

%{has(DC;east) & has(TYPE;redis)}:DOWN
    - all down redis nodes in the east datacenter.

has(TYPE;%{clusters(host1)}:TYPE)
    - all clusters with types matching the clusters of host1.

%{clusters(/foo/)}:{DOC,OWNER}
    - OWNER and DOC values for all clusters on all hosts matching "foo".

Differences From Libcrange

A number of libcrange features have been deliberately omitted from grange, either becase they are archaic features of the language, or they are mis-aligned with the goals of this library.

- ^ "admin" operator is not supported. Not a useful concept anymore.
- # "hash" operator is not supported. Normal function calls are sufficient.
- Uses RE2 regular expressions rather than PCRE. RE2 is not as fully
  featured, but guarantees that searches run in time linear in the size of
  the input.  Regexes should not be used often anyway: prefer explicit
  metadata.
- Non-deterministic functions, in particular functions that make network
  calls. This library aims to provide fast query performance, which is much
  harder when dealing with non-determinism. Clients who wish to emulate
  this behaviour should either calculate function results upfront and
  import them into the state, or post-process results.

Index

Package Files

compress.go doc.go evaluator.go nodes.go parser.go range.peg.go

Variables

var (
    // Maximum number of characters that grange will try to parse in a query.
    // Queries longer than this will be rejected. This limit also applies to
    // cluster and group names and values. Combined with MaxResults, this limits
    // result sizes to approximately 4MB.
    MaxQuerySize = 4000

    // The maximum number of results a query can return. Execution will be
    // short-circuited once this many results have been gathered. No error will
    // be returned.
    MaxResults = 10000

    // Maximum number of subqueries that will be evaluated, including evaluation
    // of cluster values. If this is exceeded, an error will be returned.
    // Primarily useful for aborting cycles, but also can shortcut really
    // expensive queries. This should not be exceeded in normal operation.
    MaxQueryDepth = 100

    // The default cluster for new states, used by @ and ? syntax. Can be changed
    // per-state using SetDefaultCluster.
    DefaultCluster = "GROUPS"
)

func Compress Uses

func Compress(nodes *Result) string

Normalizes a result set into a minimal range expression, such as +{foo,bar}.example.com+.

type Cluster Uses

type Cluster map[string][]string

A Cluster is mapping of arbitrary keys to arrays of values. The only required key is CLUSTER, which is the default set of values for the cluster.

type Result Uses

type Result struct {
    mapset.Set
}

A set of values returned by a query. The size of this set is limited by MaxResults.

func NewResult Uses

func NewResult(args ...interface{}) Result

NewResult is mostly used internally, but is handy in testing scenarios when you need to compare a query result to a known value.

type State Uses

type State struct {
    // contains filtered or unexported fields
}

State holds data that queries operate over. Queries in grange are deterministic, so the same query will always return the same result for a given state. Clients are expected to build their own state to query from their own datasource, such as a database or files on disk.

State maintains an internal cache of expanded values to speed up queries. After constructing a large state it is recommended to call PrimeCache() before querying, otherwise initial queries will likely take longer than later ones as the cache is built up incrementally.

func NewState Uses

func NewState() State

NewState creates a new state to be passed into EvalRange. This will need to be used at least once before you can query anything.

func (*State) AddCluster Uses

func (state *State) AddCluster(name string, c Cluster)

AddCluster adds a new cluster to the state and resets the cache.

func (*State) Clusters Uses

func (s *State) Clusters() map[string]Cluster

Clusters is a getter for all clusters that have been added to the state. There isn't really a good reason to use this other than for debugging purposes.

func (*State) PrimeCache Uses

func (state *State) PrimeCache() []error

PrimeCache traverses over the entire state to expand all values and store them in the state's cache. Subsequent queries will be able to use the cache immediately, rather than having to build it up incrementally.

It returns all errors encountered during the traverse. This isn't necessarily a critical problem, often errors will be in obscure keys, but you should probably try to fix them.

func (*State) Query Uses

func (state *State) Query(input string) (Result, error)

Query is the main interface to grange. See the main package documentation for query language specification. On error, an empty result is returned alongside the error. Queries that are longer than MaxQuerySize are considered errors.

The size of the returned result is capped by MaxResults.

This method is only thread-safe if PrimeCache() has previously been called on the state.

func (*State) ResetCache Uses

func (state *State) ResetCache()

ResetCache clears cached expansions. The public API for modifying state already calls this when necessary, so you shouldn't really have a need to call this.

func (*State) SetDefaultCluster Uses

func (state *State) SetDefaultCluster(name string)

Changes the default cluster for the state.

Package grange imports 9 packages (graph) and is imported by 1 packages. Updated 2017-01-13. Refresh now. Tools for package owners. This is a quick bug-fix fork (has fewer than three commits, and only during the week it was created).