integerintervalexpressions

README

integer-interval-expressions-go

A Go library for parsing integer interval expressions of the form 1,3-5,7-

Expressions of this kind are commonly seen in user-facing application contexts such as page selectors in print dialogs, field selector in the CLI cut tool, and so on. This library provides support for parsing and utilizing such expressions in wide variety of application contexts.

Internally, the library parses an input string into an abstract logical expression, which can be then evaluated with integer values to determine whether those values lie in any of the specified intervals. The parsed expressions do not contain any actual integer sequences, which allows for small memory usage and support for infinite ranges

Install

Add the library into your project:

$ go get github.com/MawKKe/integer-interval-expressions-go@latest

then import the library in your application:

import (
    ...
    intervals "github.com/MawKKe/integer-interval-expressions-go"
    ...
)

Usage

The library is quite simple to use. The primary function is ParseExpression which takes a string and returns the parsed intervals expression as an abstract Expression object:

inputString := "1,3-5,7-"
myExpr, err := intervals.ParseExpression(inputString)
if err != nil {
    fmt.Println("error:", err)
    return
}
fmt.Println("got valid expression:", myExpr)

Now you can evaluate the expression with various values:

myExpr.Matches(1) // == true
myExpr.Matches(2) // == false
myExpr.Matches(3) // == true
myExpr.Matches(4) // == true
myExpr.Matches(6) // == false
myExpr.Matches(7) // == true
myExpr.Matches(8) // == true
myExpr.Matches(9) // == true, is so for all values >=7

As you see, the expression evaluates to true only on the specified integer intervals.

NOTE: The ParseExpression() is merely a convenience function, while the actual work is performed by ParseExpressionWithOptions(). The difference is that the latter accepts a ParseOptions struct in addition to the input string; the options can be used for adjusting the operation of the parser to suit your needs. See the go doc documentation for more information. You may also be interested in the example and test functions in expr_test.go

Thats pretty much all there is to it. How you actually use this functionality is up to you. A typical use case is to iterate your application data entries and check each one against the expression:

for _, page := range MyDocument.Pages {
    if myExpr.Matches(page.Number){
        PrintPage(page)
    }
}

etc.

Syntax

See the documentation for function ParseExpressionWithOptions for description of supported intervals expression syntax.

Optimization

The expression parser will happily process an input containing duplicate or overlapping subexpressions. Likewise, the order of subexpressions is irrelevant to the parser. However, poorly constructed expressions may result in unsatisfactory Expression.Match performance. To overcome such issues, the Expression instance can be simplified via its Normalize() method. The method sorts the subexpression ranges and merges overlapping ones, producing a minimal set of subexpressions. The resulting new Expression should be semantically equivalent to the original, while being more performant from practical perspective.

NOTE: The parser does not perform the normalization automatically, unless ParseOptions::PostProcessNormalize is set to true.

NOTE: Normalization may significantly change how an Expression is represented in text form. See the documentation for Expression.String()

De-serialization

An Expression object can be converted back to string form via the String() method. For non-normalized expressions the resulting string should match closely the original expression string (omitting any superfluous whitespace). With normalized expressions, the resulting string is unlikely to be anything like the original input expression unless the original expression was already in normal form (this is not a bug).

Dependencies

The program is written in Go, version 1.18. It may compile with older compiler versions. The program does not have any third party dependencies.

License

Copyright 2022 Markus Holmström (MawKKe)

The works under this repository are licenced under Apache License 2.0. See file LICENSE for more information.

Contributing

This project is hosted at https://github.com/MawKKe/integer-interval-expressions-go

You are welcome to leave bug reports, fixes and feature requests. Thanks!

Documentation

Overview

Package integerintervalexpressions is a library for parsing integer interval expressions of the form '1,3-5,7-'

Expressions of this kind are commonly seen in user-facing application contexts such as page selectors in print dialogs, field selector in the CLI `cut` tool, and so on. This library provides support for parsing and utilizing such expressions in wide variety of application contexts.

Internally, the library parses an input string into an abstract logical expression, which can be then evaluated with integer values to determine whether those values lie in any of the specified intervals. The parsed expressions do not contain any actual integer sequences, which allows for small memory usage and support for infinite ranges

Index

• type Expression
  • func ParseExpression(input string) (Expression, error)
  • func ParseExpressionWithOptions(input string, opts ParseOptions) (Expression, error)
  • func (e Expression) Matches(val int) bool
  • func (e Expression) MatchesAll() bool
  • func (e Expression) MatchesNone() bool
  • func (e Expression) Normalize() Expression
  • func (e Expression) String() string
• type ParseOptions
  • func DefaultParseOptions() ParseOptions

Examples

• ParseExpression

Types

type Expression

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

Expression is an abstract type containing a sequence of subexpressions describing integer intervals. An Expression instance can only be constructed by ParseExpression() from a valid expression string.

The Expression only has one useful method: Matches(int), which tells you whether the given value lies inside any of the intervals contained within the expression.

func ParseExpression

func ParseExpression(input string) (Expression, error)

ParseExpression calls ParseExpressionWithOptions() with default options (see DefaultParseOptions())

Example

input := "1,3-5,7-"
myExpr, err := ParseExpression(input)
if err != nil {
	fmt.Println(err)
	return
}
for i := 0; i < 10; i++ {
	fmt.Printf("%d: %v\n", i, myExpr.Matches(i))
}

Output:

0: false
1: true
2: false
3: true
4: true
5: true
6: false
7: true
8: true
9: true

func ParseExpressionWithOptions

func ParseExpressionWithOptions(input string, opts ParseOptions) (Expression, error)

ParseExpressionWithOptions attempts to extract intervals expressions from input.

---

An intervals expression consists of sequence of individual subexpressions.

A subexpression describes a continuous range of integral values (i.e an interval). A single subexpression string contains one of the following:

- an single integer, for example "1": only the value 1.

- an integer, a dash, and another integer, for example "3-5": values 3,4 and 5.

- an integer and a dash, for example "7-": denotes all integers from 7 to infinity (i.e 7,8,9,...)

Currently the parser supports only positive integer values in subexpressions.

Additionally, the parser recognizes a subexpressions equal to "*" and interprets them as "match everything". Note that such subexpression will dominate over all others, short-circuiting the whole expression to "true".

The intervals expression is consists of subexpressions joined by a delimiter character. By default, a comma (",") is used as the delimiter (although a custom delimiter can be specified via the "ParseOptions" structure). For example, the expression "1,3-5,7-" can be understood to contain three subexpressions: "1", "3-5" and "7-".

Note that the interval expression need not contain any subexpressions, which means that "" and ",,,," are valid inputs. However, both of these parse into an Expression structure containing 0 subexpressions and are, as such, rather useless.

Semantically, a single subexpression is a predicate, and combining multiple predicates denotes a logical disjunction. The above expression thus states that we have three predicates and an overall expression:

func a(x int) { return x == 1 }             // "1"
func b(x int) { return x >= 3 && x <= 5 }   // "3-5"
func c(x int) { return x >= 7 }             // "7-"
func expr(x int) { return a(x) || b(x) || c(x) }

(However note that in the library internals the expressions are not actually represented this way.)

Note that the library does not support parsing expressions with spaces inside subexpressions, or between the subexpressions and delimiters. This may change in future version.

---

Return values:

In case of invalid/malformed input, the function returns an error and an empty Expression{}. The errors are constructed with fmt.Errorf, and should contain description of what exactly is wrong with the given input.

A valid input string is parsed into a populated Expression, which can then be evaluated using the associated methods.

NOTE: The resulting Expression is not guaranteed to be normalized, unless you set opts.PostProcessNormalize=true, or manually call .Normalize() on the result.

func (Expression) Matches

func (e Expression) Matches(val int) bool

Matches determines whether an integer is contained within the intervals expression

For example, given

expr, _ := ParseExpression("1,3-5,7-")

the expressions

expr.Matches(1)
expr.Matches(4)
expr.Matches(9)

evaluate to true, while

expr.Matches(2)
expr.Matches(6)

evaluate to false

This method does not require the Expression to be normalized, although normalized instances *should* allow for quicker evaluation due to reduced number of interval elements in the Expression; see .Normalize().

func (Expression) MatchesAll

func (e Expression) MatchesAll() bool

MatchesAll determines whether the Expression will match every possible input i.e if MatchesAll() == true; then Matches(x) == true for all x.

func (Expression) MatchesNone

func (e Expression) MatchesNone() bool

MatchesNone determines whether the Expression will ever match anything. i.e if MatchesNone() == true; then Matches(x) == false for all x.

Such Expressions are the result of input expression strings that contain no actual subexpressions. You may instruct the expression parser to reject such input expressions by setting ParseOptions.AllowEmptyExpression to false; the current default options also have this field set as false (see DefaultParseOptions()).

func (Expression) Normalize

func (e Expression) Normalize() Expression

Normalize reduces overlapping expressions to minimum set of intervals; some new interval elements may be totally new, while others are dropped. For example, expression '1-4,2-5' should normalize to '1-5'. The method returns a new normalized Expression derived from the current one.

func (Expression) String

func (e Expression) String() string

Convert Expression back to textual format.

Consider the following situation

// Assume Input is valid for brevity
Expr, _ := ParseExpression(Input)
Norm    := Expr.Normalize()

Now, the result of Expr.String() should resemble Input. However, if Expr != Norm, then Norm.String() likely differs greatly from Input. That is, a normalized Expression is unlikely to serialize back to the original input string (unless the input was written in normalized form to begin with).

type ParseOptions

type ParseOptions struct {
	Delimiter            string
	PostProcessNormalize bool

	// Allow parsing of empty input expressions strings (e.g "" or "   ")?
	// If false, parser will return error on empty input.
	// If true, empty input will result in Expression that will match nothing.
	AllowEmptyExpression bool
}

ParseOptions adjusts how the ParseExpression function will interpret the input

func DefaultParseOptions

func DefaultParseOptions() ParseOptions

DefaultParseOptions returns some sensible set of options for default usage.