stdlib.ngs

STDLIB_EOL = "\n"
STDLIB_PATH_SEP = '/'
STDLIB_MAX_RAND_REAL = Real(RAND_MAX)
STDLIB_RAND_SAFETY_MAX = 100
{
	GC.attrs({'doc': {'': 'Control NGS garbage collection'}})
	GC['enable'].attrs({'doc': {'': 'Enable garbage collection'}})
	GC['disable'].attrs({'doc': {'': 'Disable garbage collection'}})
	GC['get_parallel'].attrs({'doc': {'': 'Check parallel garbage collection. Please do not use!', '%STATUS': 'internal'}})
}

doc Deprecated. Use ExitCode.
doc %STATUS - deprecated
F to_exit_code(x) {
	warn("Using deprecated to_exit_code(). Use ExitCode() instead")
	ExitCode(x)
}

doc Do nothing
doc %RET - null
F nop(*args, **kwargs) null


# === Trivial init() helper ===

doc Trivial initialization helper for init(o, ...)
doc Sets object fields from the supplied parameters
doc %EX - # sets t.a and t.b
doc %EX - F init(t:MyType, a, b) init(args())
F init(h:Hash) {
	dst_kv = ll_hash_head(h)
	dst = dst_kv.ll_hash_entry_val() # dst - value of first Hash entry
	e = dst_kv.ll_hash_entry_next()
	while e != null {
		dst.(e.ll_hash_entry_key()) = e.ll_hash_entry_val()
		e .= ll_hash_entry_next()
	}
	dst
}

# === Exceptions ===

{
	doc Represents failed assertion, thrown by assert(). Should be used to catch programming errors.
	doc %EXSYN - commands
	doc %EX - F box_area(x:Int, y:Int) {
	doc %EX - 	assert(x > 0)
	doc %EX - 	assert(y > 0)
	doc %EX - 	x * y
	doc %EX - }
	doc %EX - echo(box_area(5, 10))
	doc %EX - # Output: 50
	doc %EX - echo(box_area(-5, 10))
	doc %EX - # ... Exception of type AssertFail ...
	doc %EX - #
	doc %EX - # Note that the following is better than using assert():
	doc %EX - # not(x > 0) throws InvalidArgument('x must be greater than zero').set('x', x)
	type AssertFail
	AssertFail.inherit(Exception)

	doc Represents an attempt to create an instance of an abstract type (not intended for instantiation).
	type InstantiatingAbstractType
	InstantiatingAbstractType.inherit(Exception)
}

doc IndexNotFound exception constructor
doc %RET - IndexNotFound object with the given message, container and key fields
F init(e:IndexNotFound, message:Str, container, key) init(args())

doc Throws AssertFail with givens message if condition is false
doc %RET - Unspecified, do not count on this value
doc %EX - my_array=[]
doc %EX - # ... Code that adds elements to my_array ...
doc %EX - assert(my_array.len() > 3, "my_array must have more than 3 elements")  # AssertFail exception, with the given message
F assert(condition:Bool, msg:Str) not(condition) throws AssertFail(msg)

doc Throws AssertFail if condition is false
doc %RET - Unspecified, do not count on this value
doc %EX - my_array=[]
doc %EX - # ... Code that adds elements to my_array ...
doc %EX - assert(my_array.len() > 3)  # AssertFail exception, with "Assertion failed" message
F assert(condition:Bool) assert(condition, "Assertion failed")

doc Throws AssertFail if condition, after conversion to Bool is false.
doc Same as super(Bool(condition), *args) .
doc condition - not Bool
doc %RET - Unspecified, do not count on this value
doc %EX - assert(my_array, "my_array must have elements at this point")
F assert(condition, *args) {
	guard condition is not Bool
	super(Bool(condition), *args)
}

doc Initializes InstantiatingAbstractType.
F init(e:InstantiatingAbstractType, t:Type) init(args())

# === Namespaces =================================

doc Get NormalType object field. Useful when calling method stored in an field.
doc %EX - myobj::method_in_field(arg)  # calls method stored in myobj.method_in_field
doc %EX - (myobj.method_in_field)(arg) # calls method stored in myobj.method_in_field
doc %EX - myobj.method_in_field(arg)   # calls global "method_in_field"
F '::'(nti:NormalTypeInstance, k) nti.(k)

doc Get Hash key. Useful when calling method stored in a Hash key.
doc Useful for working with namespaces, which are implemented as Hash instances.
doc %EX - elb = AWS::Elb(...).converge(...)
F '::'(h:Hash, k) h[k]

doc Set NormalType object field. It's implemented to complete the :: operator. There is no particular use case.
F '::='(nti:NormalTypeInstance, k, v) nti.(k) = v
doc Set Hash key. It's implemented to complete the :: operator. There is no particular use case.
F '::='(h:Hash, k, v) h[k] = v

# === Return =====================================

doc Implements calling of Return type instances
doc like the finish(i) call in the example below
doc %EX - F first(r:NumRange, predicate:Fun) {
doc %EX - 	finish = Return()
doc %EX - 	r.each(F(i) {
doc %EX - 		predicate(i) throws finish(i)
doc %EX - 	})
doc %EX - 	null
doc %EX - }
F call(r:Return, v=null) {
	r.val = v
	r
}

# === MultiMethod ================================

ns {
	global each
	# Preventing execution of F Arr(Eachable1) defined below.
	# It causes infinite loop when tries to convert Eachable1 MultiMethod: it uses this each(), which uses Arr()
	basic_arr = MultiMethod(Arr.constructors.Arr())

	doc Call cb for each method of the MultiMethod
	doc %EX - echo.each(F(method) echo("${method.params().name.join(", ")}"))
	F each(mm:MultiMethod, cb:Fun) mm.basic_arr().each(cb)
}

F Str(mm:MultiMethod) "<MultiMethod with ${mm.Arr().len()} method(s)>"

# === Misc functional ============================

{
	doc Parent type of all types that have each() method
	type Eachable

		doc Eachable which each() calls the callback with one argument
		type Eachable1
		Eachable1.inherit(Eachable)

		doc Eachable which each() calls the callback with two arguments
		type Eachable2
		Eachable2.inherit(Eachable)

	Int.inherit(Eachable1)
	Arr.inherit(Eachable1)
	Str.inherit(Eachable1)
	MultiMethod.inherit(Eachable1)
	# TODO: Consider Eachable2 subtype for Hash (as callback has 2 arguments)
	Hash.inherit(Eachable2)

	doc Absence of data
	type NoData
	Null.inherit(NoData)

	doc A number
	type Num
	Int.inherit(Num)
	Real.inherit(Num)

	doc Make empty array
	doc %RET - []
	F Arr()  { [] }
	doc Make empty hash
	doc %RET - {}
	F Hash() { {} }
	doc Make empty string
	doc %RET - ''
	F Str()  { '' }
	doc Get zero
	doc %RET - 0
	F Int()  { 0 }
	doc Get zero
	doc %RET - 0.0
	F Real() { 0.0 }
}


doc The identity function. Simply returns the given parameter.
doc %RET - The given argument
F identity(x)  x

TEST identity(10) == 10


# TODO: Add more info about the newly created function - useful for debugging
#       See https://docs.python.org/2/library/functools.html#partial-objects
doc Returns partially-applied function
doc f - The base function
doc Xunderscore_unsupportedXbind_args - The arguments to partial apply (bind the function to)
F partial(f:Fun, *bind_args)
	F(*args) f(*bind_args, *args)

TEST p = partial((-), 10); p(7) == 3


doc Same as partial() but the bound arguments are last ones
F partial_tail(f:Fun, *bind_args)
	F(*args) f(*args, *bind_args)

TEST p = partial_tail((-), 10); p(7) == -3

doc Sets the given field to the given value
doc %RET - The modified obj
doc %EX - s.len() != 1 throws InvalidArgument("ord() argument must be of length 1 exactly").set('given', s)
doc %EX - # Would else be written as
doc %EX - if s.len() != 1 {
doc %EX - 	e = InvalidArgument("ord() argument must be of length 1 exactly")
doc %EX - 	e.given = s
doc %EX - 	throw e
doc %EX - }
F set(obj, field:Str, val) {
	obj.(field) = val
	obj
}

doc Sets the given fields to the given values
doc %RET - The modified obj
doc %EX - my_cond throws InvalidArgument("Out of range").set(min=0, max=10, given=12)
F set(obj, **kwargs) {
	kwargs.each(obj.set(X, Y))
	obj
}

TEST type T; t=T().set(a=1, b=2); t.a == 1 and t.b == 2

doc Convert anything to a predicate.
doc anything - The value to compare to
doc %RET - A function that compares the only argument to the given value
doc %STATUS - deprecated
F Pred(anything:BasicTypeInstance) {
	warn("Using deprecated Pred(BasicTypeInstance)")
	F eq_pred(x) x == anything
}

doc Convert Hash to a predicate. The predicate asserts that
doc object fields named after h hash keys return true for predicates made of corresponding hash values.
doc Inspired by underscorejs' "matcher"
F Pred(h:Hash) {
	preds = h.mapv(Pred)
	F hash_pred(x) {
		preds.all(F(k, pred) (k in x) and x.(k).pred())
	}
}

TEST Pred({"a": Any})({"a": 1})
TEST Pred({"a": Any, "b": Any})({"a": 1}) == false
TEST Pred({"a": Any, "b": {false}})({"a": 1, "b": 2}) == false

doc Convert a function to predicate.
doc %RET - The given function, without any transformation
F Pred(f:Fun) f

doc Convert a type to a predicate.
doc t - A type
doc %RET - A function that checks whether the only argument is of type t
F Pred(t:Type) F is_pred(x) x is t

doc Map e to an Arr (array) of values using mapper.
doc e - Object of any type that has each(e, callback) implemented
doc %RET - Arr
doc %EX - [1,2,3].map(X*4)  # [4,8,12]
F map(e:Eachable, mapper:Fun)
	collector
		e.each(collect + mapper)

doc EXPERIMENTAL! Do not use!
doc Map e to same type. Mnemonics: "map original" / "MAP to Original type".
doc e - object of any type that has each(e, callback) implemented
doc e - Eachable1. WARNING: instances of same type as e must have empty constructor and push() method.
doc %RET - Of same type as e
doc %STATUS - experimental
doc %EX - Set([1,2]).mapo(X*2)  # Set([2,4])
F mapo(e:Eachable1, mapper:Fun) {
	t = typeof(e)
	ret = t()
	e.each(F(elt) {
		ret.push(mapper(elt))
	})
	ret
}

TEST Set([1,2]).mapo(X*2) == Set([2,4])


doc Transform mapper to handle only items matching predicate. Non-matching items will be returned as is.
doc %EX - ["abc", 1, "def", 2].map(only(Int, X*2))  # ["abc", 2, "def", 4]
F only(predicate, mapper:Fun) {
	p = Pred(predicate)
	F wrapped_in_only(elt) {
		if p(elt) {
			mapper(elt)
		} else {
			elt
		}
	}
}

TEST ["abc", 1, "def", 2].map(only(Int, X*2)) == ["abc", 2, "def", 4]

doc Filter e using predicate.
doc e - Eachable1. WARNING: instances of same type as e must have empty constructor and push() method.
doc predicate - Decision function to be called with each item as first argument.
doc predicate - When predicate(item) returns true, the item will appear in the resulting array.
doc %EX - (1...10).filter(F(num) num % 2 == 0)  # Gives [2,4,6,8,10]
doc %EX - (1...10).filter(X<5)  # Gives [1,2,3,4], predicate called as predicate(item, 5)
doc %RET - Of same type as e
F filter(e:Eachable1, predicate) {
	pred = Pred(predicate)
	t = typeof(e)
	ret = t()
	e.each() do F(elt) {
		if pred(elt)
			ret.push(elt)
	}
	ret
}


doc DEPRECATED! Do not use!
doc Use something.filter({field: predicate}) instead.
doc %STATUS - deprecated
F filter(something:Eachable1, field:Str, predicate) {
	p = Pred(predicate)
	something.filter({ p(A.(field)) })
}

doc Partition elements in something according to the predicate into two arrays.
doc First array contains all elements for which predicate(elt) is true and
doc the second array contains all elements for which predicate(elt) is false.
doc something - Eachable1
doc %RET - Array with two arrays in it
doc %EX - partition([1,10,2,20], X>=10)  # [[10, 20], [1, 2]]
F partition(something:Eachable1, predicate) {
	p = Pred(predicate)
	ret = [[], []]
	something.each(F(elt) ret[p(elt).not().Int()].push(elt))
	ret
}

TEST partition([1,10,2,20], X>=10) == [[10, 20], [1, 2]]

{
	type ElementNotFound
	ElementNotFound.inherit(LookupFail)
}

doc Find first element in e that satisfies the predicate.
doc %RET - Either the element or the provided default if element was not found.
doc %EX - (10..20).first(F(x) x % 3 == 0)        # 12 - first item divisible by 3
doc %EX - (10..20).first(F(x) x % 50 == 0, 1000) # 1000
F first(e:Eachable1, predicate, default) {
	p = Pred(predicate)
	finish = Return()
	e.each(F(i) {
		p(i) throws finish(i)
	})
	default
}

TEST [1,2,3].first(X>1, 10) == 2
TEST [1,2,3].first(X>5, 10) == 10

doc Find first element in e that satisfies the predicate. Throws ElementNotFound exception if no such element is found.
doc %RET - The element.
doc %EX - (10..20).first(F(x) x % 3 == 0)  # 12 - first item divisible by 3
doc %EX - (10..20).first(F(x) x % 50 == 0) # ElementNotFound exception
F first(e:Eachable1, predicate) {
	p = Pred(predicate)
	finish = Return()
	e.each(F(i) {
		p(i) throws finish(i)
	})
	throw ElementNotFound("first() did not find the element").set('container', e).set('predicate', predicate)
}

TEST [1,2,3].first(X>1) == 2
TEST try [1,2,3].first(X>5) catch(e:ElementNotFound) true

doc Find first element in e that satisfies Bool(e) == true.
doc Exactly same as first(e, identity).
doc %EX - [false, 0, null, "xyz", 100].first()  # "xyz"
doc %EX - [].first()                            # ElementNotFound exception
F first(e:Eachable1) first(e, identity)

doc Find the only element that satisfies the predicate.
doc Throws ElementNotFound exception if there are no elements that satisfy the predicate or if there is more than one element that satisfies the predicate.
doc %RET - The only element that satisfies the predicate.
F the_one(e:Eachable1, predicate) {
	p = Pred(predicate)
	ret = EmptyBox()
	e.each() do F(elt) {
		if p(elt) {
			ret throws ElementNotFound("the_one() had more than one match").set('container', e).set('predicate', predicate)
			ret = FullBox(elt)
		}
	}
	not(ret) throws ElementNotFound("the_one() had no matches").set('container', e).set('predicate', predicate)
	ret.get()
}

TEST [1,2,11,3,4].the_one(X>10) == 11
TEST try [1,2,11,12,4].the_one(X>10) catch(e:ElementNotFound) true
TEST try [1,2,3,4].the_one(X>10) catch(e:ElementNotFound) true

doc Find the only element that satisfies the predicate and execute given code with the value
doc body - The code to execute when exactly one element that satisfies the predicate was found. Executed with the found value. It's value will be returned as result of the_one().
doc found_more - The code to execute when more than one element satisfies the predicate. It's value will be returned as result of the_one(). Defaults to function returning null.
doc found_none - The code to execute when none of the elements satisfy the predicate. It's value will be returned as result of the_one(). Defaults to function returning null.
doc %RET - Result of running on of the following: body, found_more, found_none
doc %EX - F name(dn:MethodDocNode) {
doc %EX - 	dn.children.the_one(MethodNameDocNode).text[0]
doc %EX - }
F the_one(e:Eachable1, predicate, body:Fun, found_more:Fun=nop, found_none:Fun=nop) {
	p = Pred(predicate)
	ret = EmptyBox()
	r = Return()
	e.each(F(elt) {
		if p(elt) {
			if ret {
				throw r(found_more())
			}
			ret = FullBox(elt)
		}
	})
	if ret {
		body(ret.get())
	} else {
		found_none()
	}
}

TEST ok = false; [1,2,11,3,4].the_one(X>10, F(the_value) { if(the_value == 11) ok = true }); ok
TEST ok = false; [1,2,11,3,4].the_one(X>20, { does_not_matter }, found_none = { ok = true }); ok
TEST ok = false; [1,2,11,3,4].the_one(Int, { does_not_matter }, found_more = { ok = true }); ok

doc Extract the only element.
doc Throws ElementNotFound exception if there are no elements or if there is more than one element.
doc %RET - The only element.
doc %EX - ``aws ec2 describe-security-groups --group-ids $sg_id``.the_one()  # {OwnerId=..., VpcId=..., GroupId=..., ...}
F the_one(e:Eachable1) e.the_one({true})

doc Filter nulls out.
doc DEPRECATED, USE something.without(null) INSTEAD.
doc something - Object of any type that has each(something, callback) implemented
doc %STATUS - deprecated
doc %RET - Arr (array) of original items without nulls
F filter(e:Eachable1) {
	warn("Using deprecated filter(e)")
	filter(e, X is not Null)
}

TEST [1,2,null,3].filter() == [1,2,3]

doc Filter something to an Arr (array) of values using predicate
doc predicate - Decision function to be called with each item as first argument.
doc predicate - When predicate(item) returns true, the item will not appear in the resulting array
doc something - object of any type that has each(something, callback) implemented
doc %EX - (1...10).reject(F(num) num % 2 == 0)  # Gives [1,3,5,7,9]
doc %EX - (1...10).reject(X<5)  # Gives [5,6,7,8,9,10], predicate called as predicate(item, 5)
doc %RET - Arr
F reject(something:Eachable, predicate) {
	p = Pred(predicate)
	something.filter(not + p)
}


doc EXPERIMENTAL! Do not use!
doc %STATUS - experimental
doc %EX - [1,2,3,1,2].take(X<3)  # [1,2]
F take(something:Eachable1, predicate)
	collector {
		p = Pred(predicate)
		r = Return()
		something.each(F(elt) {
			if p(elt)
				collect(elt)
			else
				throw r()
		})
	}

TEST [1,2,3,1,2].take(X<3) == [1,2]

# Would look much better with an iterator of e.
doc EXPERIMENTAL! Do not use!
doc Filters out items that satisfy predicate at the begginning of e.
doc %STATUS - experimental
doc %EX - [1,2,3,1,2].drop(X<3)  # [3,1,2]
F drop(e:Eachable1, predicate)
	collector {
		p = Pred(predicate)
		found = false
		e.each(F(elt) {
			if found { collect(elt); return null; }
			if not(p(elt)) {
				collect(elt)
				found = true
			}
		})
	}

TEST [1,2,3,1,2].drop(X<3) == [3,1,2]

doc Replace all occurrences of src with dst
doc TODO: Return same type, not Arr
doc something - object of any type that has each(something, callback) implemented
doc %RET - Arr
doc %EX - ["ssh", "IP", "w"].replace("IP", "10.0.0.100")  # ['ssh','10.0.0.100','w']
F replace(something:Eachable1, src, dst) map(something, only(X == src, {dst}))

TEST ["ssh", "IP", "w"].replace("IP", "10.0.0.100") == ['ssh','10.0.0.100','w']

doc Combine items to a single value using the supplied binary function
doc First f is applied to start and the first element of something
doc then on each step f is applied to previous result and next element
doc of something.
doc start - First argument of f, for the first call of f
doc something - object of any type that has each(something, callback) implemented
doc f - The combining function
doc %EX - F sum(something) something.reduce(0, (+))
F reduce(something:Eachable1, start, f:Fun) {
	ret = start
	something.each(F(elt) ret = f(ret, elt))
	ret
}

TEST [1,2,3].reduce(0, (+)) == 6

{
	type EmptyEachableFail
	EmptyEachableFail.inherit(InvalidArgument)
}

doc Combine items to a single value using the supplied binary function
doc First f is applied to the first two elements of e
doc then on each step f is applied to previous result and next element
doc of e. Throws EmptyEachableFail if e has no elements. If e has only
doc one element, that element is returned.
doc e - object of any type that has each(e, callback) implemented
doc f - The combining function
doc %EX - F sum(e) e.reduce((+))
F reduce(e:Eachable1, f:Fun) {
	ret = EmptyBox()
	e.each(F(elt) {
		if ret {
			ret .= map(F(val) f(val, elt))
		} else {
			ret = FullBox(elt)
		}
	})
	not(ret) throws EmptyEachableFail("reduce(e:Eachable1, f:Fun): e must have at least one element").set('e', e)
	ret.get()
}

TEST [10].reduce((+)) == 10
TEST [1,2,3].reduce((+)) == 6
TEST try [].reduce((+)) catch(e:EmptyEachableFail) true

doc Deprecated.
doc Map when there is more than one element. If there is exactly one element, it's left as is
doc mapper - Will be called with zero based index and successive elements from arr
doc %STATUS - deprecated
doc %RET - Arr
F map_base_idx(base, n:Int, mapper:Fun) {
	warn("Using deprecated map_base_idx()")
	n == 1 returns [base]
	n.map(mapper(base, X))
}

doc Call cb with val
doc %RET - val
doc %EX - long_computation_part1().tap(F(x) echo("DEBUG: $x")).long_computation_part2()
F tap(val, cb:Fun) {
	cb(val)
	val
}

TEST ok=false; (7.tap({ if A == 7 ok = true}) == 7) and ok

doc Filter operator.
doc Same as calling x.filter(predicate)
doc %EX - [1,2,3,4] ? F(x) x > 2  # [3,4]
F ?(x, predicate:Fun) x.filter(predicate)

doc Map operator.
doc Same as calling x.map(mapper)
doc %EX - [1,2,3,4] / F(x) x * 10
F /(x, mapper:Fun) x.map(mapper)

doc Each operator.
doc Same as calling x.each(cb)
doc %EX - [1,2,3,4] % echo
F %(x, cb:Fun) x.each(cb)

doc Call operator.
doc Same as calling f(x)
doc %EX - [1,2,3,4] \ echo
F \(x, f:Fun) f(x)

doc Return a+b unless one of the arguments is falsy. In that case return that argument (a if both are falsy). Useful for building strings with optional parts.
doc %EX - status_detail = ' (' +? maybe_empty_array.join(',') +? ')'
doc %EX - echo("Status: ${main_status}${status_detail}")
doc %RET - a+b or a or b
F +?(a, b) {
	not(a) returns a
	not(b) returns b
	a + b
}

doc Checks whether element x is in Eachable1
doc x - Needle
doc e - Haystack
doc %EX -  1 in [1,2,3].Iter()  # true
doc %EX - 10 in [1,2,3].Iter()  # false
doc %RET - Bool
F in(x, e:Eachable1) e.any(X == x)

TEST ( 1 in [1,2,3].Iter()) == true
TEST (10 in [1,2,3].Iter()) == false

doc Push all elements of e into dst.
doc %RET - dst
F push_all(dst, e:Eachable1) {
	e.each(push(dst, X))
	dst
}

TEST a=[1,2]; a.push_all([3,4]); a==[1,2,3,4]

# === Eachable1 ==================================

# Should be low priority (ordered before others) method
F +(a:Eachable1, b:Eachable1) {
	guard typeof(a) === typeof(b)
	t = typeof(a)
	guard t != Int
	guard t != Arr
	guard t != Str
	t().push_all(a).push_all(b)
}

TEST Lines(["ab", "cd"]) + Lines(["ef"]) == Lines(["ab", "cd", "ef"])

doc EXPERIMENTAL! Do not use!
doc Makes sure returned value is of type t. If x is already of type t, returns x.
doc Otherwise, returns object of type t with single item x.
doc t - a subtype of Eachable1
doc %RET - Object of type t
doc %STATUS - experimental
F ensure(x, t:Type) {
	guard t.is_subtype(Eachable1)
	typeof(x) === t returns x
	t().push(x)
}


# === ArrLike ====================================
# TODO [doc]: examples in methods
{
	doc Parent type for user-defined types with array-like behaviour. Use in cases when you would like to inherit from built-in Arr. Inheriting from built-ins is not possible for now.
	doc items - default field for the underlying array
	doc %EX - type T(ArrLike)
	doc %EX - F Str(t:T) "<My array has ${len(t)} items totalling ${sum(t)}>"  # Override one of the Arr methods
	doc %EX - a = T()
	doc %EX - a.push(10)
	doc %EX - a.push(20)
	doc %EX - echo(a)  # <My array has 2 items totalling 30>
	doc %EX -
	doc %EX - # If you need init() you should have something like the following to allow ArrLike initialization:
	doc %EX - init(t:T) {
	doc %EX - 	super(t)
	doc %EX - 	...
	doc %EX - }
	type ArrLike
	ArrLike.inherit(Eachable1)
}

F init(al:ArrLike) {
	if al.attrs() is not Hash {
		al.attrs({})
	}
	al.attrs().ArrLike = []
}

doc ArrLike constructor.
doc field - DEPRECATED name of the field that holds the underlying array.
doc Throws NotImplemented if field is specified
F init(al:ArrLike, field:Str=null) {
	field throws NotImplemented("ArrLike(Str) is deprecated")
	super(al)
}

F init(al:ArrLike, arr:Arr) {
	super(al)
	al.attrs().ArrLike = arr
}

doc Get length of the underlying array.
F len(al:ArrLike)               al.attrs().ArrLike.len()

doc Set element in the underlying array.
F '[]'(al:ArrLike, idx:Int)     al.attrs().ArrLike[idx]

doc Get element from the underlying array.
F '[]='(al:ArrLike, idx:Int, x) al.attrs().ArrLike[idx] = x

doc Get element at the given index or return dflt if the index is out of range (element at the given index does not exist). See get(Arr).
F get(al:ArrLike, idx:Int, dflt) al.attrs().ArrLike.get(idx, dflt)

doc Call cb for each element in the underlying array.
F each(al:ArrLike, cb:Fun) al.attrs().ArrLike.each(cb)

doc Check whether al has any elements.
F Bool(al:ArrLike) al.attrs().ArrLike.Bool()

# NOTE: Never run because of Arr(Eachable1)
doc Get the underlying array
F Arr(al:ArrLike) al.attrs().ArrLike

doc Push an element to the underlying array.
F push(al:ArrLike, val) {
	al.attrs().ArrLike.push(val)
	al
}

doc Join items to a single string using given seperator s
doc %RET - Str
F join(al:ArrLike, s:Str) al.attrs().ArrLike.join(s)

doc Return array made of given field of each element of given array.
doc Will throw KeyNotFound if any of the elements does not have the desired field.
doc Use get() to handle missing field differently.
F .(al:ArrLike, s:Str) al.attrs().ArrLike.(s)

doc Defines collector { ... collect(...) ... } behaviour for ArrLike.
doc Very similar to collector for Arr. See collector(Arr,Fun).
F collector(al:ArrLike, body:Fun) {
	body(F(elt) al.push(elt))
	al
}

# === HashLike ===================================
# TODO [doc]: examples in methods
{
	doc Base type for user-defined hash-like types. This is a workaround: it's not possible currently no inherit from the built-in Hash type.
	type HashLike
	HashLike.inherit(Eachable2)
}

doc Check whether k is in the HashLike
doc %RET - Bool
F in(k, hl:HashLike)         k in hl.attrs().HashLike

doc Get number of key-value pairs in a HashLike
doc %RET - Int
F len(hl:HashLike)           hl.attrs().HashLike.len()


doc Get value by key. Throws KeyNotFound.
doc %AUTO - your_hashlike[k]
F '[]' (hl:HashLike, k)      hl.attrs().HashLike[k]

doc Set value.
doc %AUTO - your_hashlike[k] = v
F '[]='(hl:HashLike, k, v)   hl.attrs().HashLike[k] = v

doc Get value by key. Throws KeyNotFound.
doc %AUTO - your_hashlike.literal_key
doc %RET - Any
F .(hl:HashLike, k)          hl.attrs().HashLike[k]

doc Set value.
doc %AUTO - your_hashlike.literal_key = v
doc %RET - v
F .=(hl:HashLike, k, v)      hl.attrs().HashLike[k] = v

doc Get value by key or dflt if it does not exist
doc %RET - Any
F get(hl:HashLike, k, dflt)  hl.attrs().HashLike.get(k, dflt)

doc Get value by key or null if it does not exist
doc %RET - Any
F get(hl:HashLike, k)        hl.get(k, null)

doc Iterate over keys and values.
doc %EX - my_hashlike.each(F(k, v) echo("$k=$v"))
doc %RET - hl
F each(hl:HashLike, cb:Fun) {
	hl.attrs().HashLike.each(cb)
	hl
}

doc Get keys
doc %RET - Arr
F keys(hl:HashLike)          hl.attrs().HashLike.keys()

doc Get values
doc %RET - Arr
F values(hl:HashLike)        hl.attrs().HashLike.values()

doc Check whether hl has any elements.
doc %RET - Bool
F Bool(hl:HashLike)          hl.attrs().HashLike.Bool()

F map_idx_key_val(hl:HashLike, mapper:Fun) hl.attrs().HashLike.map_idx_key_val(mapper)

doc Filter hash. Build new HashLike with kev-value pairs selected by predicate.
doc predicate - Test function to be called with one key and one value at a time.
doc %EX - my_hashlike.filter(F(k, v) k == 'a')
doc %RET - HashLike
F filter(hl:HashLike, predicate:Fun) {
	ret = HashLike()
	ret.attrs().HashLike = hl.attrs().HashLike.filter(predicate)
	ret
}

doc Create a HashLike.
doc h - If provided, used as initial value.
doc %EX - HashLike(%{a aha b bee}) # <HashLike a=aha b=bee>
F init(hl:HashLike, h:Hash=null) {
	if hl.attrs() is not Hash {
		hl.attrs({})
	}
	hl.attrs().HashLike = h or {}
}

doc Get the underlying Hash with all the keys/values of the HashLike.
doc Note: the returned value is not a copy.
doc %RET - Hash
F Hash(hl:HashLike) hl.attrs().HashLike

# === Hook =======================================

{
	doc Hook is a simple pub-sub
	type Hook
	Hook.inherit(HashLike)
}

doc Hook constructor.
doc %RET - Hook
F init(hook:Hook) {
	super(hook)
	hook.attrs().idx = 0
}

doc Add unnamed handler.
doc The hook is automatically named "pushed-N" where N is sequential integer.
doc %RET - New hook name
F push(hook:Hook, handler:UserDefinedMethod) {
	name = "pushed-${hook.attrs().idx}"
	hook.attrs().idx += 1
	hook[name] = handler
	name
}

# TODO: consider optional? try/catch isolation
doc Runs all handlers passing all args.
doc args - Arguments to pass to handlers
doc %RET - Arr. Results from all the handlers
F call(hook:Hook, *args) hook.attrs().HashLike.mapv(X(*args))

# === Real =======================================

# TODO: something more efficient
doc Convert a string to real (floating) number, inefficiently
doc %RET - Real
doc %EX - Real("1.1")  # 1.1
F Real(s:Str) {
	parts = s.split('.')
	parts.len() == 1 returns Real(Int(parts[0]))
	parts.len() != 2 throws InvalidArgument("Invalid argument ${s}")
	l = parts[1].len()
	frac = Real(Int(parts[1]))
	for(i;l) frac = frac / 10.0
	Real(Int(parts[0])) + frac
}

TEST Real('1.1') == 1.1

# === Fun helpers ================================

doc Do not use!
F StrParams(f:Fun) {
	guard f is UserDefinedMethod or f is NativeMethod
	f.params().map(F(p) {
		d = if 'dflt' in p then '=...' else ''
		"${p.get('splat', '')}${p.name}:${p.type.name}${d}"
	}).join(', ') \ "($X)"
}

# === NativeMethod ===============================

doc String representation of native method.
doc %RET - "<NativeMethod NAME(PARAMS)>"
doc %EX - (%).Arr()[0].Str().echo()  # Outputs: <NativeMethod %(a:Int, b:Int)>
F Str(nm:NativeMethod) "<${nm.typeof().name} ${nm.attrs().name}${StrParams(nm)}>"

# === NormalTypeConstructor ===============================

doc String representation of normal type constructor. NormalTypeConstructor
doc %RET - "<NormalTypeConstructor>"
doc %EX - Box.constructors.Arr()[0].Str().echo()  # Outputs: <NormalTypeConstructor>
F Str(ntc:NormalTypeConstructor) "<NormalTypeConstructor>"

# === UserDefinedMethod ====================================

# TODO: show arguments:
#   "<UserDefinedMethod ${c.attrs().name tor "<anonymous>"}(HERE) at ${location}>"
doc String representation of a closure
doc %RET - Str
doc %EX - Real.constructors[-1].Str().echo()  # Outputs: <UserDefinedMethod Real at /usr/share/ngs/stdlib.ngs:350>
F Str(c:UserDefinedMethod) {
	info = c.ip().resolve_instruction_pointer()
	location = "${info.file}:${info.first_line}" tor "<unknown location>"
	"<UserDefinedMethod ${c.attrs().name tor "<anonymous>"}${StrParams(c)} at ${location}>"
}

# === Type =======================================

doc Create a new type. Do not use directly.
doc %AUTO - type MyType2(MyType1)
F Type(t:Str, doc, ns, parent:Type) Type(t, doc, ns, [parent])

doc Create a new type. Do not use directly.
doc %AUTO - type MyType2([MyParent1, MyParent2, ...])
F Type(t:Str, doc, ns, parents:Arr) {
	ret = Type(t, doc, ns)
	parents % ret.inherit(X)
	ret
}

TEST type T1; type T2(T1); T2() is T1

doc EXPERIMENTAL! Do not use! Especially don't count on returned value beyond obvios Bool(x) behaviour. Match anything.
doc %STATUS - deprecated
F ~(something, pred) {
	warn("Using deprecated ~(something:Any, pred:Any)")
	if Pred(pred)(something) {
		MatchSuccess([something])
	} else {
		MatchFailure()
	}
}

doc String representation of a type
doc %RET - "<Type NAME>"
doc %EX - Real.Str().echo()  # Outputs: <Type Real>
F Str(t:Type) "<Type ${t.name}>"

doc Decode (parse) strings such as command line arguments or environment variables to result given type
doc TODO: Consider renaming to UnArgv or decode_arg
doc %STATUS - experimental
F decode(s:Str, t:Type) {
	t == Any returns s # For ArgvMatcher
	F _fail(cause:Exception=null) {
		args = ["Failed to decode value. Could not convert given value to type ${t.name}", cause].reject(Null)
		throw DecodeFail(*args).set('value', s).set('target_type', t)
	}
	if t in [Int, Real, Str] {
		return try {
			t(s)
		} catch(e:InvalidArgument) {
			_fail(e)
		}
	}
	if t == Bool {
		s ~ /^(1)|(y(es?)?)|true|on$/i returns true
		s ~ /^(0)|(no?)|false|off$/i returns false
		_fail()
	}
	guard false
}

TEST decode("no", Bool) == false
TEST decode("0", Bool) == false
TEST decode("yes", Bool) == true
TEST decode("1", Bool) == true
TEST decode("1", Int) == 1
TEST decode("1", Real) == 1.0

doc %STATUS - experimental
doc Check whether t is a subtype of maybe_supertype.
doc Note that if t and maybe_supertype are same type, this method also returns true.
doc TODO: consider symbol <: as method name.
doc %RET - Bool
doc %EX - Lines.is_subtype(Eachable1)  # true
doc %EX - Eachable.is_subtype(Lines)  # false
F is_subtype(t:Type, maybe_supertype:Type) {
	maybe_supertype === Any returns true
	F kern(t:Type) {
		t === maybe_supertype returns true
		t.parents.any(kern)
	}
	kern(t)
}

TEST Lines.is_subtype(Eachable1)
TEST Lines.is_subtype(Eachable)
TEST Int.is_subtype(Any)
TEST Eachable.is_subtype(Lines) == false

# === NormalType =================================

doc String representation of normal type instance i
doc Normal type is a user defined type. In addition some types defined by NGS are also normal types.
doc %EX - {
doc %EX -   type T
doc %EX -   # nti - Normal type instance
doc %EX -   nti = T()
doc %EX -   nti.a = 1
doc %EX -   nti.b = 2
doc %EX -   echo(Str(nti)) # <T a=1 b=2>
doc %EX - }
doc %RET - "<TYPE_NAME field1=val1 field2=val2 ...>"
F Str(i:NormalTypeInstance) {
	h = Hash(i)
	fields_dots = if len(h) > 10 {
		h .= limit(10)
		' ...'
	} else {
		''
	}
	# TODO limit key and value lengths
	fields = ' ' +? h.Strs().join(' ')
	"<${i.typeof().name}${fields}${fields_dots}>"
}

TEST type T; t=T(); Str(t) == '<T>'
TEST type T; t=T(); t.a=1; t.b=2; Str(t) == '<T a=1 b=2>'

doc Set object field if it's not already set
doc %EX - my_something.dflt(k, []).push(elt)
doc %RET - Field value, the already-existed or new.
F dflt(i:NormalTypeInstance, k, v) {
	if k not in i {
		i.(k) = v
	}
	i.(k)
}

TEST type T; t=T(); t.dflt("a", 1); t.a == 1
TEST type T; t=T(); t.a = 2; t.dflt("a", 1); t.a == 2

doc Set a field on all elements if it's not already set
doc e - Eachable1 with elements of type NormalTypeInstance or Hash
doc %EX - my_items.dflt("source", "(unknown)")
doc %RET - e
F dflt(e:Eachable1, k, v) {
	guard e.all({A is NormalTypeInstance or A is Hash})
	e.each(X.dflt(k, v))
	e
}

TEST [{}, {"x": 1}].dflt("x", 100) == [{"x": 100}, {"x": 1}]

doc Equality test for normal type instances: must be of same type and have same fields and their values
doc %RET - Bool
doc %EX - type T
doc %EX - t1 = T()
doc %EX - t1.a = 1
doc %EX - t2 = T()
doc %EX - t2.a = 1
doc %EX - echo(t1 == t2)  # Outputs: true
F ==(a:NormalTypeInstance, b:NormalTypeInstance) {
	typeof(a) != typeof(b) returns false
	# TODO: more efficient implementation:
	#       * Provide low level primitive to either access the fields (ll_nti_hash) or iterate them
	#       * Use it here
	Hash(a) == Hash(b)
}

# TODO: move to somewhere more appropriate, keep in mind - must be after dflt(NormalTypeInstance, ...)
doc Set a key if it's not already set
doc %EX - mysomething.dflt(k, []).push(elt)
doc %RET - Key value, the already-existed or new.
F dflt(hl:HashLike, k, v) hl.attrs().HashLike.dflt(k, v)

doc Make shallow copy of an object
F copy(nti:NormalTypeInstance) {
	t = typeof(nti)
	ret = t()
	nti.Hash().each(ret.set(X, Y))
	ret
}

TEST type T; t=T(); t.x=1; t2=t.copy(); t2.x==1

# === Exceptions =================================

{
	# TODO: Investigate why type CException(Error) does not work at this point
	doc Base type for exceptions arising from errors returned by calling C functions
	type CException
	CException.inherit(Error)

	doc CException constructor. In addition to storing message field, adds errno and errno_name fields.
	F init(e:CException, message:Str) {
		errno = c_errno()
		super(e, message)
		e.errno = errno
		e.errno_name = c_strerror(e.errno)
	}

	doc CException constructor. In addition to storing message field, adds errno and errno_name fields.
	F init(e:CException, errno:Int, message:Str) {
		super(e, message)
		e.errno = errno
		e.errno_name = c_strerror(e.errno)
	}

	doc Exception representing a failure to kill() a process
	type KillFail
	KillFail.inherit(CException)
}

# === Lock =======================================

{
	doc Synchronization lock.
	type Lock

	doc Re-entrant synchronization lock. Same thread can re-acquire the lock.
	type ReentrantLock()
	ReentrantLock.inherit(Lock)

	doc Failure to perform an operation on a lock.
	type LockFail
	LockFail.inherit(Exception)

	doc Initialize LockFail exception.
	F init(e:LockFail, op:Str, code:Int, msg:Str) init(args())

	doc Initialize Lock. Creates and initializes pthread_mutex.
	F init(l:Lock) {
		l.lock = c_pthread_mutex_t()
		code = c_pthread_mutex_init(l.lock)
		code throws LockFail("c_pthread_mutex_init", code, "Call to underlying API failed")
	}

	doc Block till the lock is avaiable and then acquire the lock.
	doc %EX - l = Lock()
	doc %EX - ...
	doc %EX - l.acquire()
	doc %EX - modify_global_state_safely(...)
	doc %EX - l.release()
	F acquire(l:Lock) {
		c_pthread_mutex_lock(l.lock)
		l
	}

	doc Release the lock
	doc %EX - l = Lock()
	doc %EX - ...
	doc %EX - l.acquire()
	doc %EX - modify_global_state_safely(...)
	doc %EX - l.release()
	F release(l:Lock) {
		c_pthread_mutex_unlock(l.lock)
		l
	}

	doc Call cb with lock l held. Releases the lock after cb returns or throws.
	doc %EX - l = Lock()
	doc %EX - ...
	doc %EX - l.acquire(F() {
	doc %EX -   modify_global_state_safely(...)
	doc %EX - })
	F acquire(l:Lock, cb:Fun) {
		l.acquire()
		try {
			ret = cb()
			l.release()
			ret
		} catch(e:Exception) {
			l.release()
			throw e
		}
	}

	TEST Lock().acquire(F() 1) == 1

	doc Initialize Lock. Creates and initializes PTHREAD_MUTEX_RECURSIVE pthread_mutex.
	F init(l:ReentrantLock) {
		l.lock_attr = c_pthread_mutexattr_t()
		code = c_pthread_mutexattr_init(l.lock_attr)
		code throws LockFail("c_pthread_mutexattr_init", code, "Call to underlying API failed")
		c_pthread_mutexattr_settype(l.lock_attr, C_PTHREAD_MUTEX_RECURSIVE)
		l.lock = c_pthread_mutex_t()
		code = c_pthread_mutex_init(l.lock, l.lock_attr)
		code throws LockFail("c_pthread_mutex_init", code, "Call to underlying API failed")
	}

	doc Convert c_pthread_mutex_t to Str for displaying to humans.
	F Str(cpm:c_pthread_mutex_t) "<c_pthread_mutex_t>"

	doc Convert c_pthread_mutexattr_t to Str for displaying to humans.
	F Str(cpma:c_pthread_mutexattr_t) "<c_pthread_mutexattr_t>"
}

# === auto-load ==================================

AUTOLOAD = ns {
	global global_not_found_handler
	_lock = ReentrantLock()

	# Sorted by: file, global variable name
	# Not exposing _global_name_to_autoload_file as use cases are not clear yet.
	# Also, it's probably better to expose an API and not the data.
	_global_name_to_autoload_file = %{
		InMemoryCache       Cache
		OnDiskCache         Cache

		IPAddr              IP
		IPNet               IP

		ArrIter             Iter
		ConstIter           Iter
		HashIter            Iter
		NoNext              Iter
		RangeIter           Iter

		ResDef              Res

		InputStream         Stream
		InputOutputStream   Stream
		OutputStream        Stream

		table               Table
	}

	invocation = 0

	doc Called when reading undefined global.
	doc Implements autoloading.
	doc Searches in $NGS_DIR/autoload/GLOBAL_NAME.ngs
	doc WARNING: May have security implications when looking up a name from untrusted source.
	doc %EX - test("My web server runs") do { .... }  # $NGS_DIR/autoload/test.ngs is automatically loaded.
	F global_not_found_handler(name:Str) {
		_lock.acquire() do {
			i = invocation
			invocation += 1
			F local_debug(s:Str) {
				debug("autoload", "global_not_found_handler() [invocation $i] ${s}")
			}
			local_debug("name=${name}")
			idx = ll_resolve_global_variable(name)
			ll_is_global_variable_defined(idx) returns
			if name in _global_name_to_autoload_file {
				local_debug("loading ${NGS_DIR}/autoload/${_global_name_to_autoload_file[name]}.ngs")
				require("${NGS_DIR}/autoload/${_global_name_to_autoload_file[name]}.ngs")
				return
			}
			local_debug("loading ${NGS_DIR}/autoload/${name}.ngs")
			val = require("${NGS_DIR}/autoload/${name}.ngs")
			if not(ll_is_global_variable_defined(idx)) {
				local_debug("global variable ${name} still not set; setting")
				ll_set_global_variable(idx, val)
			}
		}
	}
}

# === Range ======================================

{
	doc A range
	type Range
		NumRange.inherit(Range)
		NumRange.inherit(Eachable1)

	doc A range with start and end expressed as predicates.
	type PredRange
		PredRange.inherit(Range)
}

doc Range constructor. Throws InstantiatingAbstractType if r is exactly of type Range (not a sub-type).
F init(r:Range, start, end, include_start=true, include_end=false, step=1) {
	r.typeof() == Range throws InstantiatingAbstractType(Range)
	init(args())
}

doc Constructs open-open predicate range
doc %RET - PredRange
doc %EX - [10,200,300,40,50][(X==10)..(X==40)]          # [200, 300]
doc %EX - ["abc", "aaa", "bbb", "def"][/^abc/../^def/]  # ["aaa", "bbb"]
F ..(start, end)  PredRange(start, end, false, false)

doc Constructs closed-closed predicate range
doc %RET - PredRange
doc %EX - [10,200,300,40,50][(X==10)...(X==40)]          # [10,200,300,40]
doc %EX - ["abc", "aaa", "bbb", "def"][/^abc/.../^bbb/]  # ["abc", "aaa", "bbb"]
F ...(start, end) PredRange(start, end, true, true)

doc Constructs closed-open numerical range
doc start - numerical or null (at least one of start or end must be non-null)
doc end - numerical or null (at least one of start or end must be non-null)
doc %RET - NumRange
doc %EX - (1..4).sum()  # 6
F ..(start, end) {
	guard start is Num or end is Num
	guard start is Num or start is Null
	guard end is Num or end is Null
	NumRange(start, end, true, false)
}

doc Constructs closed-closed numerical range
doc %RET - NumRange
doc %EX - (1...4).sum()  # 10
F ...(start, end) {
	guard start is Num or end is Num
	guard start is Num or start is Null
	guard end is Num or end is Null
	NumRange(start, end, true, true)
}

TEST 0..null is NumRange
TEST null..null is PredRange
TEST null.."xyz" is PredRange

doc Iterates over the elements of r, passing each in turn to cb.
doc cb - Function to be called with values from r
doc args - Additional arguments for calling cb
doc %RET - r
doc %EX - s=0
doc %EX - (1...10).each(F(i) { global s; s+=i })
doc %EX - echo(s)  # Outputs: 55
F each(r:NumRange, cb:Fun) r.Iter().each(cb)

TEST (1..3).map(X*2) == [2, 4]
TEST (1...3).map(X*2) == [2, 4, 6]

TEST (10..20).first(F(x) x % 3 == 0) == 12

doc Check whether the number is in range
doc 10 in 10..20  # true
doc 1 in 10..20   # false
F in(n:Int, r:NumRange) {
	econd {
		r.include_start and n == r.start true
		r.start is not Null and n <= r.start false
		r.include_end and n == r.end true
		r.end is not Null and r.end <= n false
		true true
	}
}

# TODO: better coverage
TEST not(1 in NumRange(1,2,false,true))
TEST 2 in NumRange(1,2,false,true)
TEST not(10 in NumRange(1,2,false,true))
TEST 20 in NumRange(1,30,false,true)
TEST 30 in NumRange(1,30,false,true)

doc Convert range to human readable representation
F Str(r:Range) "<${r.typeof().name} ${r.start}..${r.end} include_start=${r.include_start} include_end=${r.include_end} step=${r.step}>"

# TODO: think about multi-valued results (say 10 hosts, 8 succeeded and 2 failed)
# TODO: think about Argv cooperation. Maybe Failure is NoData and Success is FullBox?
# === Syntactic sugar ============================

doc Boolean negation for non-boolean values. Converts to boolean first.
doc %RET - Bool
F not(x) { guard (x is Bool) == false; x.Bool().not() }

doc Inequality operator
doc %EX - 1 !=2  # true, same as not(1==2)
F !=(a,b) not(a==b)

doc Non-sameness operator
doc %EX - h1 = {"a": 1}
doc %EX - h2 = {"a": 1}
doc %EX - h1 !== h2  # true, same as not(h1===h2)
doc %EX - h1 == h2   # true
F !==(a,b) not(a===b)

TEST 1 != 2
TEST (1 != 1) == false

TEST 1 !== 2
TEST (1 !== 1) == false


doc "not in" operator. Exactly same as "not(a in b)"
doc %EX - 10 not in [1,2]  # true
doc %EX - 1  not in [1,2]  # false
F 'not in'(a,b) not(a in b)

TEST (1 not in [1,2,3]) == false
TEST 10 not in [1,2,3]

doc "is not" operator. Exactly same as "not(a is b)".
doc %EX - 1    is not Null  # true
doc %EX - null is not Null  # false
F 'is not'(a,b) not(a is b)

TEST 1 is not Null
TEST (null is not Null) == false


doc Exactly same as "element in container". It's just more convenient in specific cases.
doc %EX - [1,2,3].has(2)  # true
doc %EX - [[1,2,3], [1,20,30], [100,200,300]].filter(X.has(1))  # [ [1,2,3], [1,20,30] ]
doc %RET - Bool
F has(container, element) element in container

TEST [1,2,3].has(1)
TEST [1,2,3].has(10).not()


doc Defines collector { ... collect(...) ... } behaviour for arrays
doc a - Initial array
doc body - The body after collector keyword and possible initial value, wrapped in a function
doc body - "collector THIS_CODE" or "collector/my_init THIS_CODE"
doc %RET - Constructed array
doc %EX - items = collector {
doc %EX -   collect(10)
doc %EX -   for(i;2) collect(i)
doc %EX -   collect(20)
doc %EX - }
doc %EX - echo(items)  # Outputs: [10,0,1,20]
doc %EX -
doc %EX - # Or start with few items:
doc %EX - items = collector/[100,200] {
doc %EX -   collect(10)
doc %EX -   for(i;2) collect(i)
doc %EX -   collect(20)
doc %EX - }
doc %EX - echo(items)  # Outputs: [100,200,10,0,1,20]
F collector(a:Arr, body:Fun) {
	body(F(elt) a.push(elt))
	a
}

doc Defines collector { ... collect(...) ... } behaviour for hashes
doc h - Initial hash
doc body - The body after collector keyword and initial value, wrapped in a function
doc body - "collector/{'my': 'hash'} THIS_CODE"
doc %RET - Constructed array
doc %EX - arr = [{"Name": "n1", "Value": "v1"},{"Name": "n2", "Value": "v2"}]
doc %EX - my_hash = collector/{}
doc %EX - 	arr.each(F(elt) collect(elt.Name, elt.Value))
doc %EX - echo(my_hash)  # Outputs: {n1=v1, n2=v2}
F collector(h:Hash, body:Fun) {
	body(F(k, v) h[k] = v)
	h
}

doc Defines collector { ... collect(...) ... } behaviour for integers (summarizes collected items).
doc n - Initial number
doc body - The body after collector keyword and initial value, wrapped in a function
doc body - "collector/100 THIS_CODE"
doc %RET - Constructed array
doc %EX - collector/0 { (1...10).each(collect) }  # 55
F collector(n:Int, body:Fun) {
	body(F(incr) n=n+incr)
	n
}

ns {
	global collector
	# XXX
	join_strings = join.Arr()[0]

	doc EXPERIMENTAL! Do not use!
	F collector(s:Str, body:Fun) {
		ret = [s]
		body(ret.push(X))
		ret.join_strings('')
	}
}

TEST (collector/"a" collect("b")) == "ab"

doc Compare to null
doc %RET - false
F ==(a:Null, b) false

doc Compare to null
doc %RET - false
F ==(a, b:Null) false

doc Compare to null
doc %RET - true
F ==(a:Null, b:Null) true

doc Run cleanup after successful execution of body or exception in body
doc body - Main code to execute
doc cleanup - Cleanup code to execute
doc %RET - Whatever body call returns
doc %EX - finally(
doc %EX -   { while entry = c_readdir(d) { ... } },
doc %EX -   { ... c_closedir(d) ...}
doc %EX - )
doc %EX - # Alternative function call syntax:
doc %EX - finally()
doc %EX -   body => {
doc %EX -     while entry = c_readdir(d) {
doc %EX -       cb(Path(dirname / entry.d_name, subtype=subtype))
doc %EX -     }
doc %EX -   }
doc %EX -   cleanup => {
doc %EX -     r = c_closedir(d)
doc %EX -     r != 0 throws DirFail('Failed to close directory after listing').set('dirname', dirname)
doc %EX -   }
F finally(body:Fun, cleanup:Fun) {
	ret = Result(body)
	cleanup()
	if ret is Failure {
		throw ret.val
	}
	ret.get()
}

TEST a=0; {1/1}.finally({a=10}) == 1 and a == 10
TEST a=0; (try finally() with {1/0} with {a=10} catch(e:DivisionByZero) "OK") == "OK" and a == 10
TEST F f() { r=Return(); finally({throw r(7)}, {8}) }; f() == 7

# --- Hash ---

doc Get hash key.
doc %EX - h = {"a": 1}
doc %EX - h.a  # 1, Same as h["a"]
F .(h:Hash, field:Str) h[field]

doc Set hash key.
doc %EX - h = {"a": 1}
doc %EX - h.a = 2  # 2, Same as h["a"] = 2
doc %RET - v
F .=(h:Hash, field:Str, v) h[field] = v

doc Get hash value by key or null if it does not exist
doc %EX - h = {"a": 1}
doc %EX - h.get("a")  # 1
doc %EX - h.get("b")  # null
F get(h:Hash, k) get(h, k, null)

doc Convert hash values to integers where possible
doc %RET - New Hash
doc %STATUS - deprecated
doc %EX - %{k 7 kk "a"}["k"] is Str      # true
doc %EX - %{k 7 kk "a"}.n()              # {'k': 7, 'kk': 'a'}
doc %EX - %{k 7 kk "a"}.n()["k"] is Int  # true
F n(h:Hash) {
	warn("Using deprecated n(Hash)")
	h.mapv({Int(A) tor A})
}

TEST %{k 7 kk "a"}.n() == {'k': 7, 'kk': 'a'}

# --- Arr ---

# TODO: generalize to Eachable1 ?
doc Return array made of given field of each element of given array.
doc Will throw KeyNotFound if any of the elements does not have the desired field.
doc Use get() to handle missing field differently.
doc %EX - [{"x": 1}, {"x": 2}].x               # [1, 2]
doc %EX - [{"x": 1}, {"y": 2}].x               # KeyNotFound exeption
doc %EX - [{"x": 1}, {"y": 2}].get("x")        # [1] - skip
doc %EX - [{"x": 1}, {"y": 2}].get("x", null)  # [1, null] - use default value
doc %RET - Arr
F .(a:Arr, field:Str) a.map(X.(field))

TEST [{"x": 1}, {"x": 2}].x == [1, 2]

doc Set field of every element in array to v
doc %EX - a=[{"x": 1}, {"x": 2}]
doc %EX - a.y = 10
doc %EX - # a == [{"x": 1, "y": 10}, {"x": 2, "y": 10}]
doc %RET - v
F .=(a:Arr, field:Str, v) {
	a.each(F(elt) elt.(field) = v)
	v
}

TEST a=[{"x": 1}, {"x": 2}]; a.y = 10; a == [{"x": 1, "y": 10}, {"x": 2, "y": 10}]

doc Return array made of given field of each element of given Eachable1 where present
doc %EX - [{"x": 1}, {"y": 2}].get("x")  # [1]
doc %EX - ``aws ec2 describe-instances``.Tags.get("role").uniq()
doc %EX - # Returns Arr of Str with roles. Does not crash if some machines do not have "role" tag.
doc %RET - Arr
F get(e:Eachable1, field:Str)
	collector
		e.each(F(item) {
			try collect(item.(field))
		})

doc Return array made of given field of each element of given Eachable1 where present or default value where the field is not present.
doc %EX - [{"x": 1}, {"y": 2}].get("x", null)  # [1, null]
doc %RET - Arr
F get(e:Eachable1, field:Str, dflt) e.map(X.get(field, dflt))

doc Concatenate strings
doc %EX - "ab" + "cd"  # "abcd"
doc %RET - New Str
F +(s1:Str, s2:Str) "${s1}${s2}"

TEST "ab" + "cd" == "abcd"

# === Arr ========================================

doc Get element by index or null if it does not exist
doc %RET - Any
F get(a:Arr, idx:Int) get(a, idx, null)

TEST [1].get(0, 10) == 1
TEST [1].get(5, 10) == 10


doc Checks whether element x is in array arr
doc x - Needle
doc arr - Haystack
doc %EX -  1 in [1,2,3]  # true
doc %EX - 10 in [1,2,3]  # false
doc %RET - Bool
F in(x, arr:Arr) {
	l = arr.len()
	for(i;l) arr[i] == x returns true
	false
}

# Tested by has() tests

doc Arrays equality test.
doc True if arrays are of the same length and all elements are equal (==)
doc %RET - Bool
F ==(a:Arr, b:Arr) {
	l = a.len()
	l != b.len() returns false
	for(i;l) a[i] != b[i] returns false
	true
}

TEST [1, 2] == [1, 2]
TEST [1, 3] != [1, 2]
TEST [1] != [1, 2]

doc Compare arrays, elemt-wise. If all elements are equal, the longest array considered to be the "big" one.
doc %RET - Bool
doc %EX -  [1, 2] <= [1, 3]  # true
doc %EX -  [1] <= [1, 2]     # true
F '<='(a:Arr, b:Arr) {
	l = min([a.len(), b.len()])
	for(i;l) {
		a[i] < b[i] returns true
		a[i] > b[i] returns false
	}
	a.len() <= b.len() returns true
	false
}

TEST [1, 2] <= [1, 3]
TEST not([1, 3] <= [1, 2])
TEST [1] <= [1, 2]
TEST not([1,2] <= [1])

# TODO: Make it work on anything with Eachable2 too.
doc Check whether there is any element in e that satisfies the given predicate.
doc e - The items to check
doc predicate - Test function
doc args - Additional arguments for calling the predicate.
doc %EX - [1,2,10].any(F(elt) elt > 5)   # true
doc %EX - [1,2,10].any(F(elt) elt > 15)  # false
doc %RET - Bool
F any(e:Eachable1, predicate) {
	p = Pred(predicate)
	r = Return()
	e.each(F(x) {
		p(x) throws r(true)
	})
	false
}

TEST [1,2,10].any(F(elt) elt > 5)
TEST [1,2,3].any(F(elt) elt > 5).not()

doc Check whether all elements in arr satisfy the given predicate.
doc e - The items to check
doc predicate - Test function
doc args - Additional arguments for calling the predicate.
doc %RET - Bool
doc %EX - [1,2,3].all(X<10)   # true
doc %EX - [1,2,10].all(X>5)   # false
F all(e:Eachable, predicate) {
	p = Pred(predicate)
	r = Return()
	e.each(F(*x) {
		not(p(*x)) throws r(false)
	})
	true
}

TEST [1,2,3].all(X<10)
TEST [1,2,10].all(X>5).not()
TEST {"x": 1, "y": 2}.all(F(k, v) v is Int)

doc Check that there is no element in e that satisfies the given predicate. Exactly same as not(any(e, predicate)) .
doc %RET - Bool
doc %EX - [0,1,2].none(X>2)  # true
doc %EX - [0,1,2].none(X<2)  # false
F none(e:Eachable1, predicate:Fun) not(any(e, predicate))

TEST [0,1,2].none(X>2)
TEST [0,1,2].none(X<2).not()

TEST [1,2,3].map(X*4) == [4,8,12]

F subset(smaller:Arr, larger:Arr) {
	len(smaller) > len(larger) returns false
	h = if larger.len() > 10 {
		larger.Set()
	} else {
		larger
	}
	smaller.all(X in h)
}

TEST [1,2,3].subset([1,2,3,4])
TEST [1].subset([2]) == false

doc Iterates over the elements of arr, passing each in turn to cb along with args: cb(ITEM)
doc cb - Function to be called with values from arr
doc args - Additional arguments for calling cb
doc %RET - arr
doc %EX - s=0
doc %EX - [1,2,3].each(F(i) { global s; s+=i })
doc %EX - echo(s)  # Outputs: 6
F each(arr:Arr, cb:Fun) {
	l = arr.len()
	for(i;l) cb(arr[i])
	arr
}

# Tested by flatten() tests

doc Iterates over elements of e, passing each in turn to cb along with index and args: cb(INDEX, ITEM)
doc %RET - e
doc %EX - "abc".each_idx_val(F(idx, val) echo("Element #$idx equals to $val"))
F each_idx_val(e:Eachable1, cb:Fun) {
	idx = 0
	e.each(F(elt) {
		cb(idx, elt)
		idx += 1
	})
}

# TODO: map_idx_val
doc Iterates over the elements of arr, passing each in turn to cb along with index and args: cb(INDEX, ITEM)
doc %RET - arr
doc %EX - [10,20,30].each_idx_val(F(idx, val) echo("Element #$idx equals to $val"))
F each_idx_val(arr:Arr, cb:Fun) {
	l = arr.len()
	for(i;l) cb(i, arr[i])
	arr
}

doc Map an Eachable1 to an Arr (array) of values using mapper
doc mapper is called as mapper(INDEX, ITEM)
doc %RET - New Arr
doc %EX - echo("Array items: " + ArrLike().push(10).push(20).push(30).map_idx_val(F(idx, val) "[$idx]=$val").join(", "))
doc %EX - # Outputs: Array items: [0]=10, [1]=20, [2]=30
F map_idx_val(e:Eachable1, mapper:Fun) collector each_idx_val(e, collect + mapper)

doc Map an Arr to an Arr (array) of values using mapper
doc mapper is called as mapper(INDEX, ITEM)
doc %RET - New Arr
doc %EX - echo("Array items: " + [10,20,30].map_idx_val(F(idx, val) "[$idx]=$val").join(", "))
doc %EX - # Outputs: Array items: [0]=10, [1]=20, [2]=30
F map_idx_val(arr:Arr, mapper:Fun) {
	l = arr.len()
	collector
		for(i;l) collect(mapper(i, arr[i]))
}

TEST r=[]; ["a", "b"].each_idx_val(F(idx, val) r.push([idx, val])); r == [[0, "a"], [1, "b"]]


# TODO: make it work with anything that has each() method
# TODO: check if used anywhere
doc Process each N elements of an Array at a time.
doc Throws InvalidArgument if number of items in arr is not divisible by n.
doc cb is called as cb(eltI, ..., eltJ) where I is multiple of n and J is I+n-1
doc arr - Items to iterate in chunks of n
doc n - Number of items in chunk
doc cb - Function to be called with values from arr
doc args - Additional arguments for calling cb
doc %RET - arr
doc %EX - [1,2,3,4].each(2, F(a, b) echo("$a - $b"))  # Outputs: "1 - 2" and on the next line "3 - 4"
F each(arr:Arr, n:Int, cb:Fun) {
	arr.len() % n != 0 throws InvalidArgument("Can not iterate elements in groups of $n of array of size ${arr.len()}")
	chunks = arr.len() / n
	for(chunk_number; chunks) {
		cb(*arr[chunk_number*n..chunk_number*n+n])
	}
	arr
}

# Tested by map(arr:Arr, n:Int, cb:Fun)


doc Map each N elements of an Array at a time.
doc mapper is called as cb(eltI, ..., eltJ) where I is multiple of n and J is I+n-1
doc Throws InvalidArgument if number of items in arr is not divisible by n.
doc mapper is called as mapper(eltI, ..., eltJ) where I is multiple of n and J is I+n-1
doc arr - Items to iterate in chunks of n
doc n - Number of items in chunk
doc mapper - Function to be called with values from arr
doc args - Additional arguments for calling mapper
doc %RET - Arr
doc %EX - [1,2,3,4].map(2, F(a,b) "$a=$b").join("&")  # Outputs: 1=2&3=4
F map(arr:Arr, n:Int, mapper:Fun) collector arr.each(n, collect + mapper)

# Tested by ~(s:Str, r:RegExp)

doc Filter out all occurrences of specific value
doc e - items to filter
doc without_elt - The value to filter out
doc %RET - Arr
doc %EX - [1,2,3,2].without(2)  # [1,3]
F without(e:Eachable1, without_elt) e.filter(X != without_elt)

TEST [1,2,3,2].without(2) == [1,3]

doc Filter out all values in a that are also in b
doc %RET - Arr
doc %EX - [1,2,3] - [5,6,1]  # [2,3]
F -(a:Arr, b:Arr) {
	h = if b.len() > 10 {
		b.Set()
	} else {
		b
	}
	a.filter(X not in h)
}

TEST [1,2,3] - [5,6,1] == [2,3]
TEST [1,2,3] - [5,6,1,1,1,1,1,1,1,1,1,1,1,2] == [3]

doc Count number of items that satisfy the predicate.
doc e - Items to look at
doc predicate - Test function
doc args - Additional arguments for the predicate
doc %RET - Int
doc %EX - [1,2,3,11,12].count(X>10)  # 2
F count(e:Eachable1, predicate) {
	p = Pred(predicate)
	collector/0
		e.each(F(elt) {
			if p(elt)
				collect(1)
		})
}

TEST [1,2,3,11,12].count(X>10) == 2

doc Count all true values.
doc e - Items to look at
doc %RET - Int
doc %EX - [0,1,2,null,false].count()  # 2 (Only 1 and 2 count as true values)
F count(e:Arr) count(e, identity)

TEST [0,1,2,null,false].count() == 2

doc Flatten one level.
doc e - Eachable with each element also Eachable
doc %RET - Arr
doc %EX - [[1], [2,3]].flatten()  # [1,2,3]
F flatten(e:Eachable1) {
	guard not(e is Int)
	guard e.all(Eachable1)
	collector
		e.each(F(subarr) {
			subarr.each(collect)
		})
}

TEST [[1], [2,3]].flatten() == [1,2,3]

doc Return unique values.
doc Warning: uses Hash so comparison is not using == but a built-in hash keys comparison.
doc %RET - Arr
doc %EX - [1,2,2,3,4,4].uniq()  # [1,2,3,4]
F uniq(arr:Arr) arr.Hash({true}).keys()

TEST [1,2,2,3,4,4].uniq() == [1,2,3,4]

TEST [null, false, 10, 20].first() == 10

ns {
	global index
	no_default = []  # Just a unique object
	doc Find index of first value that satisfies the predicate.
	doc TODO: Make it work on anything with each() method.
	doc In future, will throw exception if element is not found and default is not provided. Now returns null for backwards compatibilty in this case.
	doc arr - Items to look at
	doc predicate - Test function
	doc start - Index to start search at
	doc dflt - default value to return when element is not found
	doc %RET - Int or dflt. Temporary also null, for backwards compatibilty.
	doc %EX - [1,2,11,3,4].index(X>10)  # 2
	F index(arr:Arr, predicate, start:Int=0, dflt=no_default) {
		p = Pred(predicate)
		l = arr.len()
		for(i=start; i<l; i+=1)
			p(arr[i]) returns i
		dflt !== no_default returns dflt
		warn("index() is returning null. In future, this will be an exception. You can change your call to index(..., dflt=null)")
		null
	}
}

doc Find all indexes of values that satisfy the predicate
doc arr - Items to look at
doc predicate - Test function
doc args - Additional arguments for the predicate
doc %RET - Arr of Int
doc %EX - [1,5,1,10].indexes(X>2)  # [1,3]
F indexes(e:Eachable1, predicate) {
	p = Pred(predicate)
	collector
		e.each_idx_val(F(idx, elt) {
			if p(elt) {
				collect(idx)
			}
		})
}

TEST [1,5,1,10].indexes(X>2) == [1,3]

TEST [5,10,15].first(X>7) == 10
TEST try [5,10,15].first(X>20) catch(e:ElementNotFound) true

doc Make new array which is a reversed given array
doc %RET - Arr
doc %EX - [1,2,3].reverse()  # [3,2,1]
F reverse(arr:Arr) {
	l = arr.len()
	l.map({ arr[l-A-1] })
	# TODO: maybe make this work: arr[NumRange(arr.len() - 1, 0, -1)]
}

TEST [1,2,3].reverse() == [3,2,1]

# Uses reduce method with start value as it is probably faster
doc Calculate sum of the elements
doc %EX - [1,2,3].sum()  # 6
F sum(something:Eachable1) something.reduce(0, (+))

doc Prepend one element to the given array
doc %RET - Modified arr
doc %EX - x=[1,2]
doc %EX - x.unshift(3)
doc %EX - echo(x)  # Outputs: [3,1,2]
F unshift(arr:Arr, elt) {
	arr[0..0] = [elt]
	arr
}

TEST x=[1,2]; x.unshift(3); x == [3, 1, 2]

doc EXPERIMENTAL! Do not use!
doc a - Array of arrays to join
doc sep - Separator elements
doc %EX - [[1,2], [3,4]].join([10,20])  # [1,2,10,20,3,4]
F join(a:Arr, sep:Arr) {
	guard a.all(Arr)
	collector
		a.each_idx_val(F(idx, subarr) {
			subarr.each(collect)
			if idx < a.len() - 1 {
				sep.each(collect)
			}
		})
}

# --- Conversions ---

doc Make Arr from Hash. Each key/value pair becomes two-items array.
doc %RET - Arr of form [[k1, v1], [k2, v2], ...]
doc %EX - Arr({'x': 7, 'y': 8})  # [['x', 7], ['y', 8]]
F Arr(h:Hash)
	h.map(F(*pair) pair)

TEST Arr({'x': 7, 'y': 8}) == [['x', 7], ['y', 8]]

doc Make new array which aggregates elements from each of the args arrays
doc n-th element of the new array is an array that contains n-th element of each of the given arrays
doc If some of the arrays in args are shorter than others, they will be logically padded with null
doc %EX - zip([1,2,3], [4,5,6])  # [[1,4], [2,5], [3,6]]
doc %EX - zip([1,2,3], [4,5])    # [[1,4], [2,5], [3,null]]
doc %RET - Arr of form [[arg[0][0], arg[1][0], ... arg[i][0]], [arg[0][1], arg[1][1], ... arg[i][1]], ...]
F zip(*args) {
	arrays = args.map(Arr)
	arrays.max(len).map({ arrays.map(X.get(A, null)) })
}

TEST zip([1,2,3], [4,5,6]) == [[1,4], [2,5], [3,6]]
TEST zip([1,2,3], [4,5,6], [7,8,9,10]) == [[1,4,7], [2,5,8], [3,6,9], [null, null, 10]]

doc Convert Eachable1 (anything with "each" method that takes callback of one parameter) to an array
doc %EX - Arr(1..3)   # [1,2]
doc %EX - Arr(1...3)  # [1,2,3]
F Arr(something:Eachable1)
	collector
		something.each(collect)

TEST Arr(1..3) == [1,2]
TEST Arr(1...3) == [1,2,3]

doc Make Arr from Arr. A no-op.
doc %RET - arr
F Arr(arr:Arr) arr

# --- Access elements ---

doc Get array element by index from the end (negative indexes handler). Throws IndexNotFound if abs(idx) > len(arr).
doc idx - Negative index
doc %EX - [10,20,30][-1]  # 30
F '[]'(arr:Arr, idx:Int) {
	guard idx < 0
	i = arr.len() + idx
	i < 0 throws IndexNotFound("[](Arr, Int): Index $idx is illegal for array of size ${arr.len()}", arr, idx)
	arr[i]
}

# TODO: Make "Indexable" and make this method work with Indexable
doc Get array elements at specified indexes. Indexes specified by NumRange.
doc r - NumRange with negatve .end
doc %EX - [10,20,30,40][1..-1]  # [20,30]
doc %RET - Arr
F '[]'(arr:Arr, r:NumRange) {
	guard r.end is Int and r.end < 0
	r.step != 1 throws NotImplemented("r.step must be 1")
	r.end < 0 - arr.len() throws IndexNotFound("[](Arr, NumRange): Index ${r.end} (range end) is illegal for array of size ${arr.len()}", arr, r.end)
	arr[r.start..arr.len() + r.end]
}

TEST [10,20,30,40][1..-1] == [20,30]

ns {
	global indexes
	no_default = []  # Just a unique object
	# TODO: something more effective
	doc Find the indexes of elements of the given PredRange.
	doc Throws IndexNotFound if there is no match between the elements of arr and r.
	doc %RET - NumRange with .include_start=true and .include_end=false
	doc %EX - %[a1 a2 b1 b2 c1].indexes(/^a/../^b/)   # <NumRange 1..2 include_start=true include_end=false step=1>
	doc %EX - %[a1 a2 b1 b2 c1].indexes(/^a/.../^b/)  # <NumRange 0..3 include_start=true include_end=false step=1>
	F indexes(arr:Arr, r:PredRange, dflt=no_default) {
		r.step != 1 throws NotImplemented("r.step must be 1")
		start = if r.start is Null {
			0
		} else {
			index(arr, r.start, dflt=null)
		}
		if start is Null {
			dflt !== no_default returns dflt
			throw IndexNotFound("Array did not match PredRange (start)", arr, r)
		}
		end = if r.end is Null {
			len(arr)
		} else {
			index(arr, r.end, start=start + Int(r.start is not Null and r.include_start.not()), dflt=null)
		}
		if end is Null {
			dflt !== no_default returns dflt
			throw IndexNotFound("Array did not match PredRange (end)", arr, r)
		}
		NumRange(start + Int(r.start is not Null and r.include_start.not()), end + Int(r.include_end))
	}
}

TEST try { indexes([1,2,3,4], ((X==1)..(X==14))); false } catch(e:IndexNotFound) true
TEST indexes([1,2,3,4], ((X==1)..(X==14)), []) == []

doc Extract array elements between the element that matches r.start and the element that matches r.end .
doc Starting and ending elements are optionally included, depending on r.include_start and r.include_end .
doc %EX - %[a1 a2 b1 b2][/^a/../^b/]   # ['a2']
doc %EX - %[a1 a2 b1 b2][/^a/.../^b/]  # ['a1', 'a2', 'b1']
doc %EX - %[a1 a2 b1 b2][/^a/.../^x/]  # IndexNotFound exception
F '[]'(arr:Arr, r:PredRange) arr[indexes(arr, r)]

TEST %[a1 a2 b1 b2][/^a/../^b/] == %[a2]
TEST %[a1 a2 b1 b2][null../^b/] == %[a1 a2]
TEST %[a1 a2 b1 b2][/^b/..null] == %[b2]
TEST %[a1 a2 b1 b2][/^a/.../^b/] == %[a1 a2 b1]
TEST try { %[a1 a2 b1 b2][/^a/.../^x/]; false } catch(e:IndexNotFound) true
TEST try { %[a1 a2 b1 b2][/^x/.../^b/]; false } catch(e:IndexNotFound) true

doc Replace array elements.
doc arr - Array to operate on.
doc r - Range of elements to replace.
doc replacement - New elements.
doc %EX - a = %[a1 a2 b1 b2]
doc %EX - a[/^a/.../^b/] = [7]  # a == [7, 'b2']
doc %EX - MARKERS = '# generated - start'..'# generated - end'
doc %EX - text[MARKERS] = newly_generated_content_lines
F '[]='(arr:Arr, r:PredRange, replacement:Arr) arr[indexes(arr, r)] = replacement
TEST a = %[a1 a2 b1 b2]; a[/^a/.../^b/] = [7]; a == [7, 'b2']

doc Check whether the array contains the given range. Finds first match.
doc %EX - a = %[a1 a2 b1 b2]
doc %EX - m = a ~ /^a/../^b/ # Exclusive range
doc %EX - # m.matches == [['a2']]
doc %EX - # m.before == ['a1']
doc %EX - # m.after == ['b1', 'b2']
doc %RET - MatchResult
F ~(arr:Arr, r:PredRange) {
	i = indexes(arr, r, dflt=null)
	i is Null returns MatchFailure(arr, r)
	ret = MatchSuccess([arr[i]])
	ret.named = {}
	ret.positions = [[i.start, i.end]]
	ret.whole = ret.matches[0]
	ret.before = arr[0..i.start]
	ret.after = arr[i.end..null]
	ret
}

TEST a = %[a1 a2 b1 b2]; m = a ~ /^a/../^b/; m.matches == [['a2']] and m.before == ['a1'] and m.after == ['b1', 'b2']
TEST a = %[a1 a2 b1 b2]; m = a ~ /^a/.../^b/; m.matches == [['a1','a2','b1']] and m.before == [] and m.after == ['b2']

doc Get array elements at specified indexes.
doc arr - Array to pick items from
doc indexes - Indexes of items to pick
doc %EX - [10,20,30,40][[0,3]]  # [10, 40]
doc %RET - Arr
F '[]'(arr:Arr, indexes:Arr) indexes.map(arr[X])

TEST [10,20,30,40][[0,3]] == [10, 40]

doc Truncate an array if necessary so it would have maximum l elements.
doc a - Array to (possibly) truncate.
doc l - Maximum elements
doc %RET - Either a or new Arr of length l
doc %EX - [10,11,12].limit(2)   # [10,11]
doc %EX - [10,11,12].limit(10)  # [10,11,12]
F limit(a:Arr, l:Int) {
	a.len() <= l returns a
	a[0..l]
}

TEST [10,11,12].limit(10) == [10,11,12]
TEST [10,11,12].limit(2) == [10,11]

# --- Misc ---

ns {
	global min, max
	F most(e:Eachable1, f:Fun) {
		guard e
		ret = e[0]
		e.each(F(elt) if f(elt, ret) { ret = elt })
		ret
	}

	F most_by_cb(e:Eachable1, f:Fun, cb:Fun) {
		guard e
		ret = e[0]
		ret_cb = cb(ret)
		e.each(F(elt) {
			elt_cb = cb(elt)
			if f(elt_cb, ret_cb) {
				ret = elt
				ret_cb = elt_cb
			}
		})
		ret_cb
	}

	doc Find minimal element under (<)
	F min(e:Eachable1) most(e, (<))
	doc Find maximal element under (>)
	F max(e:Eachable1) most(e, (>))

	doc Find minimal element under (<)
	F min(a, b, *rest) [a, b, *rest].min()

	doc Find maximal element under (>)
	F max(a, b, *rest) [a, b, *rest].max()

	doc EXPERIMENTAL! Do not use!
	doc %STATUS - deprecated
	F min(e:Eachable1, cb:Fun) {
		warn("Using deprecated min(Eachable1, Fun)")
		most_by_cb(e, (<), cb)
	}
	doc EXPERIMENTAL! Do not use!
	doc %STATUS - deprecated
	F max(e:Eachable1, cb:Fun) {
		warn("Using deprecated max(Eachable1, Fun)")
		most_by_cb(e, (>), cb)
	}
}

doc Repeat all elements in arr n times
doc arr - Elements to repeat
doc n - Number of times to repeat the elements
doc %RET - Arr
doc %EX - [10,20] * 2  # [10,20,10,20]
F *(arr:Arr, n:Int)
	collector
		for(i;n)
			arr.each(collect)

TEST [10,20] * 2 == [10,20,10,20]

doc Cartesian product
doc %RET - Arr of Arr[2]
doc %EX - [10,20] * [30,40]  # [[10, 30], [10, 40], [20, 30], [20, 40]]
F *(a:Arr, b:Arr)
	collector
		a.each(F(elt_a) {
			b.each(F(elt_b) {
				collect([elt_a, elt_b])
			})
		})

TEST [10,20] * [30,40] == [[10, 30], [10, 40], [20, 30], [20, 40]]

doc Echo non-string. Converts x to string first, using Str()
doc x - Anything but Str
doc %RET - null
doc %EX - echo(1)
F echo(x) {
	guard x is not Str
	echo(Str(x))
}

# Built-in join() can only handle Str elements
doc Join non-strings. Converts a elements to string first, then uses built-in join().
doc Warning - behaviour subject to change!
doc a - Array to join
doc s - Delimiter
doc %RET - Str
doc %EX - [1,2,3].join("::")  # The string 1::2::3
F join(a:Arr, s:Str) {
	guard a.any(X is not Str)
	a.map(Str).join(s)
	# TODO: maybe a.map({if A is Str then A else Str(A)}).join(s)
	# TODO: consider making Str(x) == x
}

# Can be more efficent I guess
doc Merge sorted arrays.
doc lte - Less-then-or-equal function to use for comparison of items in a and b
doc %RET - Arr
doc %EX - merge_sorted([1,3,10], [0, 7], (<=))  # [0, 1, 3, 7, 10]
F merge_sorted(a:Arr, b:Arr, lte:Fun) {
	ai = Iter(a)
	bi = Iter(b)
	collector
		while ai or bi {
			i = econd {
				not(ai) bi
				not(bi) ai
				lte(ai.peek(), bi.peek()) ai
				true bi
			}
			collect(i.next())
		}
}

TEST merge_sorted([1,3,10], [0, 7], (<=)) == [0, 1, 3, 7, 10]

# Current implemetation: https://en.wikipedia.org/wiki/Merge_sort
# TODO: replacte with Timsort https://en.wikipedia.org/wiki/Timsort
doc Sort an array.
doc lte - Less-then-or-equal function to use for comparison of the items in a
doc %RET - Arr
doc %EX - sort([0,5,3,-1], (<=))  # [-1, 0, 3, 5]
F sort(a:Arr, lte:Fun=(<=)) {
	# XXX: Not copied!
	a.len() <= 1 returns a
	mid = a.len() / 2
	l = a[0..mid]
	r = a[mid..null]
	merge_sorted(sort(l, lte), sort(r, lte), lte)
}

TEST sort([0,5,3,-1], (<=)) == [-1, 0, 3, 5]

doc Sort an array based on field value
doc lte - Less-then-or-equal function to use for comparison of the items' fields
doc %RET - Arr
doc %EX - [{'x': 1}, {'x': 5}, {'x': 3}].sort('x')  # [{'x': 1}, {'x': 3}, {'x': 5}]
F sort(a:Arr, field:Str, lte:Fun=(<=)) a.sort(F(a, b) lte(a.(field), b.(field)))

TEST [{'x': 1}, {'x': 5}, {'x': 3}].sort('x') == [{'x': 1}, {'x': 3}, {'x': 5}]

# TODO: better documentation
doc Split e into arrays
doc %RET - Arr of Arr
doc %EX - [1, "a", 2, 3, "a", 4].split("a")  # [[1], [2, 3], [4]]
F split(e:Eachable1, delim) {
	collector {
		cur = []
		e.each(F(elt) {
			if elt == delim {
				collect(cur)
				cur = []
			} else {
				cur.push(elt)
			}
		})
		collect(cur)
	}
}

TEST [1, "a", 2, 3, "a", 4].split("a") == [[1], [2, 3], [4]]

doc Call cb with array of maximum length of n, repeatedely for all items of e.
doc TODO: better doc
doc %STATUS - experimental
F each_chunk(e:Eachable1, n:Int, cb:Fun) {
	cur = []
	e.each(F(x) {
		cur.push(x)
		if len(cur) == n {
			cb(cur)
			cur = []
		}
	})
	if cur {
		cb(cur)
	}
}

doc Insert delimiter element between each two elements in an array
doc %RET - Arr
doc %EX [1,2,3].intersperse(0)  # [1,0,2,0,3]
F intersperse(a:Arr, delim) {
	not(a) returns []
	collector {
		a.each(F(elt) {
			collect(elt)
			collect(delim)
		})
	}[0..-1]
}

TEST [1,2,3].intersperse(0) == [1,0,2,0,3]

doc Optionally, wrap x in an array. Return x if it's already Arr.
doc %RET - Arr
doc %EX - ensure_array([1,2])  # [1,2]
doc %EX - ensure_array("aa")   # ["aa"]
F ensure_array(x) x.ensure(Arr)

TEST ensure_array([1,2]) == [1,2]
TEST ensure_array("aa") == ["aa"]


doc Convert an array to NGS code that would produce the array when executed. Not fully functional yet.
doc %RET - Str
F code(a:Arr) "[" + a.map(code).join(', ') + "]"

# === Hash =======================================


# --- Comparisons ---

doc Compare two Hashes. Hashes must have same keys with same values in same order to return true.
doc Both hashes must not be modified during comparison. This was not tested.
doc %RET - Bool
F ==(a:Hash, b:Hash) {
	len(a) != len(b) returns false
	a === b returns true

	e1 = ll_hash_head(a)
	e2 = ll_hash_head(b)
	while e1 != null {
		e1.ll_hash_entry_key() != e2.ll_hash_entry_key() returns false
		e1.ll_hash_entry_val() != e2.ll_hash_entry_val() returns false
		e1 .= ll_hash_entry_next()
		e2 .= ll_hash_entry_next()
	}
	true
}

F subset(smaller:Hash, larger:Hash) {
	not(len(smaller) <= len(larger)) returns false
	smaller.all(F(k, v) k in larger and larger[k] == v)
}

TEST subset({}, {"a": 1})
TEST subset({"a": 1}, {"a": 1})
TEST subset({"a": 1, "b":2}, {"b": 3, "d": 4}) == false
TEST subset({"a": 1}, {"a": 10}) == false

# --- Functional ---

doc Compose functions
doc %RET - Fun f(g(...))
doc %EX - F reject(something, predicate) {
doc %EX - 	something.filter(not + predicate)
doc %EX - }
F +(f:Fun, g:Fun) {
	F composed_function(*args) {
		f(g(*args))
	}
}

# Make it built in for speed?
doc Iterate a Hash.
doc h - Hash to iterate
doc cb - Function to call with successive keys and values
doc %RET - h
doc %EX - {"a": 1, "b": 2}.each(F(k, v) echo("$k=$v"))  # Outputs: "a=1" and on the next line "b=2"
F each(h:Hash, cb:Fun) {
	entry = ll_hash_head(h)
	while entry != null {
		cb(entry.ll_hash_entry_key(), entry.ll_hash_entry_val())
		entry = entry.ll_hash_entry_next()
	}
	h
}

doc Iterate a Hash.
doc h - Hash to iterate
doc cb - Function to call with successive keys
doc %RET - h
F eachk(h:Hash, cb:Fun) {
	entry = ll_hash_head(h)
	while entry != null {
		cb(entry.ll_hash_entry_key())
		entry = entry.ll_hash_entry_next()
	}
	h
}

doc Iterate a Hash.
doc h - Hash to iterate
doc cb - Function to call with successive values
doc %RET - h
F eachv(h:Hash, cb:Fun) {
	entry = ll_hash_head(h)
	while entry != null {
		cb(entry.ll_hash_entry_val())
		entry = entry.ll_hash_entry_next()
	}
	h
}

doc Iterate a Hash.
doc h - Hash to iterate
doc cb - Function to call with successive indexes, keys and values
doc args - Additional arguments for calling cb
doc %RET - h
doc %EX - {"a": 1, "b": 2}.each_idx_key_val(F(idx, k, v) echo("[$idx] $k=$v"))
doc %EX - # Outputs: "[0] a=1" and on the next line "[1] b=2"
F each_idx_key_val(h:Hash, cb:Fun) {
	entry = ll_hash_head(h)
	i = 0
	while entry != null {
		cb(i, entry.ll_hash_entry_key(), entry.ll_hash_entry_val())
		entry = entry.ll_hash_entry_next()
		i += 1
	}
	h
}

doc Map a Hash
doc h - Hash with source keys and values
doc mapper - Function to be called with keys and values from h
doc %RET - Arr
doc %EX - {'a': 1, 'b': 2}.map(F(k, v) "${k}-$v")  # ['a-1', 'b-2']
F map(h:Hash, mapper:Fun)
	collector
		h.each(collect + mapper)

TEST {'a': 1, 'b': 2}.map(F(k, v) "${k}-$v") == ['a-1', 'b-2']

doc Map a Hash
doc h - Hash with source keys and values
doc mapper - Function to be called with sequential zero-based index, keys and values from h
doc %RET - Arr
doc %EX - {'a': 1, 'b': 2}.map_idx_key_val(F(i, k, v) "${i}-${k}-$v")  # ['0-a-1', '1-b-2']
F map_idx_key_val(h:Hash, mapper:Fun) {
	idx = 0
	collector {
		entry = ll_hash_head(h)
		while entry != null {
			collect(mapper(idx, entry.ll_hash_entry_key(), entry.ll_hash_entry_val()))
			entry = entry.ll_hash_entry_next()
			idx += 1
		}
	}
}


doc Map Hash keys. Build new Hash with same values as in h but keys mapped by mapper.
doc h - Source hash
doc mapper - Function to be called with keys
doc args - Additional arguments for calling mapper
doc %RET - Hash
doc %EX - mapk({"a": 1}, F(k) k+"z")  # {"az": 1}
F mapk(h:Hash, mapper:Fun)
	collector/{}
		h.each(F(k, v) collect(mapper(k), v))

TEST mapk({"a": 1}, X+"z") == {"az": 1}

doc Map Hash values. Build new Hash with same keys as in h but values mapped by mapper.
doc h - Source hash
doc mapper - Function to be called with values
doc args - Additional arguments for calling mapper
doc %RET - Hash
doc %EX - LEN = 3
doc %EX - lines_ = read("/usr/share/dict/words").lines()
doc %EX - long_lines = lines_.filter({A.len()>LEN})
doc %EX - prefix_to_lines = long_lines.group(F(line) line[0..LEN])  # {"pfx1": ["pfx1a", "pfx1b", ...], "pfx2": ["pfx2a", "pfx2b", ...], ...}
doc %EX - prefix_to_count = prefix_to_lines.mapv(len)  # {"pfx1": 30, "pfx2": 35, ...}
doc %EX - top = prefix_to_count.Arr().sort(F(a, b) b[1] <= a[1]).Hash()
doc %EX - top .= limit(10)
doc %EX - echo(top)  # Outputs: {con=1219, dis=1001, pro=808, pre=607, com=600, int=543, tra=498, ove=431, per=422, imp=421}
F mapv(h:Hash, mapper:Fun)
	collector/{}
		h.each(F(k, v) collect(k, mapper(v)))

TEST mapv({"a": 1}, X+1) == {"a": 2}


doc Map Hash keys and values. Build new Hash with keys and values mapped by mapper.
doc h - Source hash
doc mapper - Function to be called with keys and values
doc args - Additional arguments for calling mapper
doc %EX - mapkv({"a": 1}, {[A+"zz", B+10]})  # {"azz": 11}
F mapkv(h:Hash, mapper:Fun)
	collector/{}
		h.each(F(k, v) collect(*mapper(k, v)))

TEST mapkv({"a": 1}, {[A+"zz", B+10]}) == {"azz": 11}

doc Filter hash. Build new hash with kev-value pairs selected by predicate.
doc h - Source hash
doc predicate - Test function to be called with one key and one value at a time
doc args - Additional arguments for calling the predicate
doc %EX - {'a': 1, 'b': 2}.filter(F(k, v) k == 'a')  # {'a': 1}
F filter(h:Hash, predicate) {
	p = Pred(predicate)
	collector/{}
		h.each(F(k, v) {
			if p(k, v)
				collect(k, v)
		})
}

TEST {'a': 1, 'b': 2}.filter(F(k, v) k == 'a') == {'a': 1}

doc Filter hash by keys, keeping matched
doc %EX - {"a": 1, "b": 2, "ccc": 3}.filterk(/^.$/)    # {a=1, b=2}
doc %EX - {"aa": 1, "ab": 2, "ba": 3}.filterk(/^a/)    # {aa=1, ab=2}
doc %EX - {"aa": 1, "ab": 2, 10: 3}.filterk(Int)       # {10=3}
doc %EX - {10: "a", 20: "b", 30: "c"}.filterk(X > 10)  # {20=b, 30=c}
F filterk(h:Eachable2, predicate) filter(h, Pred(predicate) + {A})

TEST {"a1": 1, "a2": 2, "b1": 10}.filterk(/^b/) == {"b1": 10}

doc Filter hash by keys, removing matched. See filterk().
doc %EX - {"a1": 1, "a2": 2, "b1": 10}.rejectk(/^b/)  # {"a1": 1, "a2": 2}
F rejectk(h:Eachable2, predicate) h.filterk(not + Pred(predicate))

TEST {"a1": 1, "a2": 2, "b1": 10}.rejectk(/^b/) == {"a1": 1, "a2": 2}


doc Filter hash by values
doc %EX - {"a1": 1, "a2": 2, "b1": 10}.filterv(X>5)  # {"b1": 10}
F filterv(h:Eachable2, predicate) filter(h, Pred(predicate) + {B})

TEST {"a1": 1, "a2": 2, "b1": 10}.filterv(X>5) == {"b1": 10}


doc Filter hash by values
F rejectv(h:Eachable2, predicate) h.filterv(not + Pred(predicate))

TEST {"a1": 1, "a2": 2, "b1": 10}.rejectv(X>5) == {"a1": 1, "a2": 2}

doc Count number of key-value pairs in Hash that satisfy the predicate.
doc e - Something to check, typically a Hash
doc predicate - Test function to be called with one key and one value at a time
doc args - Additional arguments for calling the predicate.
doc %RET - Int
doc %EX - {'a': 1, 'b': 2, 'c': 11}.count(F(k, v) v>10)  # 1
F count(e:Eachable2, predicate) {
	p = Pred(predicate)
	collector/0
		e.each(F(k, v) {
			if p(k, v)
				collect(1)
		})
}

TEST {'a': 1, 'b': 2, 'c': 11}.count(F(k, v) v>10) == 1

doc Sort Hash by keys
doc %RET - Hash
doc %EX - {'b': 2, 'c': 11, 'a': 1}.sortk()  # {'a': 1, 'b': 2, 'c': 11}
F sortk(h:Hash, lte:Fun=(<=)) h.keys().sort(lte).Hash(h[X])

TEST {'b': 2, 'c': 11, 'a': 1}.sortk() == {'a': 1, 'b': 2, 'c': 11}
TEST {'a': 1, 'b': 2, 'c': 11}.sortk() == {'a': 1, 'b': 2, 'c': 11}

# --- Conversions ---

doc Create a Hash from Arr of Arr[2]
doc arr - Array of Arrays. Each one of the sub-arrays must have exactly two elements.
doc %RET - Hash
doc %EX - Hash([['a', 1], ['c', 3]])  # {'a': 1, 'c': 3}
F Hash(arr:Arr)
	collector/{}
		arr.each(F(pair) {
			collect(*pair)
		})

TEST Hash([['a', 1], ['c', 3]]) == {'a': 1, 'c': 3}

doc Create Hash with keys being the given field of array elements and the values being corresponding arr elements.
doc %RET - Hash
doc %EX - Hash([{'x': 1}, {'x': 2}], 'x')  # {1: {'x': 1}, 2: {'x': 2}}
F Hash(arr:Arr, field:Str)
	collector/{}
		arr.each(F(v) collect(v[field], v))

TEST Hash([{'x': 1}, {'x': 2}], 'x') == {1: {'x': 1}, 2: {'x': 2}}

doc Create a Hash from keys in arr using cb for values calculation
doc arr - Keys of the hash to build
doc cb - Function to be called with one key at a time. Should calculate a value for the given key.
doc %RET - Hash
doc %EX - Hash([1,2], F(x) x*2)  # {1: 2, 2: 4}
F Hash(arr:Arr, cb:Fun)
	collector/{}
		arr.each(F(elt) collect(elt, cb(elt)))

TEST Hash([1,2], F(x) x*2) == {1: 2, 2: 4}


doc Create a Hash from keys in "keys" and corresponding values in "values"
doc keys - Keys for the new Hash
doc values - Values for the new Hash
doc %RET - Hash
doc %EX - Hash(["a", "b", "c"], [1,2,3])  # {"a": 1, "b": 2, "c": 3}
F Hash(keys:Arr, values:Arr)
	collector/{}
		keys.len().each(F(idx) collect(keys[idx], values[idx]))

TEST Hash(["a", "b", "c"], [1,2,3]) == {"a": 1, "b": 2, "c": 3}

doc Create Hash from Arr of something that has key and value fields
doc e - Eachable1 with all the keys and values
doc key_field - Name of the field holding the keys of newly created Hash
doc val_field - Name of the field holding the values of newly created Hash
doc %RET - Hash
doc %EX - Hash([{"Name": "n1", "Value": "v1"},{"Name": "n2", "Value": "v2"}], "Name", "Value")  # {"n1": "v1", "n2": "v2"}
F Hash(e:Eachable1, key_field:Str, val_field:Str)
	collector/{}
		e.each(F(elt) collect(elt.(key_field), elt.(val_field)))

TEST Hash([{"Name": "n1", "Value": "v1"},{"Name": "n2", "Value": "v2"}], "Name", "Value") == {"n1": "v1", "n2": "v2"}


# --- Misc ---

doc Filter out specific key
doc e - Source
doc without_k - The key to filter out
doc %EX - {'a': 1, 'b': 2, 'c': 3}.without('a')  # {'b': 2, 'c': 3}
F without(e:Eachable2, without_k) e.filter(X != without_k)

TEST {'a': 1, 'b': 2, 'c': 3}.without('a') == {'b': 2, 'c': 3}

doc Filter out specific key-value pair
doc e - Source
doc without_k - The key to filter out
doc without_v - The value to filter out
doc %EX - {'a': 1, 'b': 2, 'c': 3}.without('a', 1).without('b', 22)  # {'b': 2, 'c': 3}
F without(e:Eachable2, without_k, without_v)
	e.reject(F(k, v) (k == without_k) and (v == without_v))

TEST {'a': 1, 'b': 2, 'c': 3}.without('a', 1).without('b', 22) == {'b': 2, 'c': 3}

doc Add Hashes. Builds new hash with key-value pairs from both a and b. If same key is present in both a and b, the value from b is used.
doc %RET - Hash
doc %EX - {'a': 1, 'b': 2, 'c': 3} + {'b': 20, 'd': 40}  # {'a': 1, 'b': 20, 'c': 3, 'd': 40}
F +(a:Hash, b:Hash) {
	{**a, **b}
}


TEST {'a': 1, 'b': 2, 'c': 3} + {'b': 20, 'd': 40} == {'a': 1, 'b': 20, 'c': 3, 'd': 40}

doc Build array of Str where each resulting string is of the form "KEY=VALUE"
doc h - Source hash
doc %RET - Arr of Str
doc %EX - {'a': 1, 'b': 2}.Strs()  # ['a=1', 'b=2']
F Strs(h:Hash) h / "$X=$Y"

TEST {'a': 1, 'b': 2}.Strs() == ['a=1', 'b=2']

doc Truncate a Hash if necessary so it would have maximum l key-value pairs.
doc h - Source hash
doc l - Maximum elements
doc %RET - Hash
doc %EX - {"a": 1, "b": 2}.limit(1)  # {"a": 1}
F limit(h:Hash, l:Int) h.keys().limit(l).Hash(h[X])

TEST {"a": 1, "b": 2}.limit(3) == {"a": 1, "b": 2}
TEST {"a": 1, "b": 2}.limit(1) == {"a": 1}

doc Group items from e by key returned by cb
doc %RET - Hash with Arr values
doc %EX - ["ab", "ac", "ba", "bc", "bd"].group(F(x) x[0])  # {a=[ab,ac], b=[ba,bc,bd]}
F group(e:Eachable1, cb:Fun)
	collector/ret={}
		e.each(F(elt) {
			k = cb(elt)
			ret.dflt(k, []).push(elt)
		})

doc Make shallow copy of a Hash
doc %RET - Hash
F copy(h:Hash) {
	{**h}
}

TEST h={"a": 1}; g=copy(h); h.b = 2; ("b" in h) and ("b" not in g)

doc Convert a Hash to NGS code that would produce the given Hash when executed. Not fully functional yet.
doc %RET - Str
F code(h:Hash) {
	'{' + h.map(F(k, v) "${k.code()}: ${v.code()}").join(', ') + '}'
}

doc Set a key in a Hash if it's not already set
doc %EX - my_hash.dflt(k, []).push(elt)
doc %RET - Hash value, the already-existed or new.
F dflt(h:Hash, k, v) {
	if k not in h {
		h[k] = v
	}
	h[k]
}

doc Sort a Hash.
doc lte - Less-then-or-equal function to use for comparison of the keys in h
doc %RET - Hash
doc %EX - {"b": 2, "c": 3, "a": 1}.sort()  # {"a": 1, "b": 2, "c": 3}
F sort(h:Hash, lte:Fun=(<=)) {
	collector/{}
		h.keys().sort(lte).each(F(k) collect(k, h[k]))
}

TEST {"b": 2, "c": 3, "a": 1}.sort() == {"a": 1, "b": 2, "c": 3}

doc Get the given key from a Hash and remove it from the Hash.
doc Underlying h[k] may throw KeyNotFound.
doc %EX - h = {"a": 1}
doc %EX - s = h.shift("a")  # h == {} and s == 1
F shift(h:Hash, k) {
	ret = h[k]
	del(h, k)
	ret
}

doc Get a key from a Hash and remove it from the Hash.
doc If they key is not in the Hash, return dflt
doc %EX - h = {}
doc %EX - h.shift("a", 7)  # 7
F shift(h:Hash, k, dflt) {
	k not in h returns dflt
	ret = h[k]
	del(h, k)
	ret
}

TEST h={"a": 1}; s = h.shift("a"); h == {} and s == 1
TEST h={}; try h.shift("a") catch(e:KeyNotFound) true
TEST h={}; h.shift("a", 7) == 7
TEST h={"a": 1, "b": 2}; s = h.shift("a"); h == {"b": 2} and s == 1


# === Box ========================================

# Inspired by Option from Scala. http://www.scala-lang.org/api/2.12.x/scala/Option.html

{
	doc Thrown when trying to get() a value from EmptyBox and no default value given.
	type BoxFail(Error)

	doc A box which might (FullBox) or might not (EmptyBox) contain a value.
	doc Box is somewhat similar to Arr of zero (EmptyBox) or exactly one (FullBox) element.
	doc This analogy helps understanding each() and filter() operation.
	type Box(Eachable1)

		doc Represents presence of a value
		doc val - The value
		type FullBox(Box)

		doc Represents absence of a value
		type EmptyBox([Box, NoData])
}

doc Do not use directly!
doc Helper constructor that throws InvalidArgument when
doc FullBox is created with zero or more than one argument.
F init(b:FullBox, *args) throw InvalidArgument("FullBox must be initialized with exactly one value")

doc FullBox constructor. Saves val into .val
doc %EX - # Simplified code from the_one() method:
doc %EX - ret = EmptyBox()
doc %EX - something.each(F(elt) {
doc %EX - 	if predicate(elt) {
doc %EX - 		ret throws ElementNotFound("the_one() had more than one match")
doc %EX - 		ret = FullBox(elt)
doc %EX - 	}
doc %EX - })
doc %EX - not(ret) throws ElementNotFound("the_one() had no matches")
doc %EX - ret.val # Has the value
F init(b:FullBox, val) b.val = val

doc Always true
F Bool(fb:FullBox) true

doc Always false
F Bool(eb:EmptyBox) false

doc Zero for FullBox and one for EmptyBox
F ExitCode(b:Box) b.Bool().ExitCode()

doc Map FullBox value
doc mapper - mapper to be called with the FullBox value
doc %RET - FullBox with value returned by mapper
doc %EX - Box(10).map(X*2)  # <FullBox val=20>
F map(fb:FullBox, mapper:Fun) FullBox(mapper(fb.val))

doc Do nothing
doc %RET - eb
doc %EX - EmptyBox().map(X*2)  # <EmptyBox>
F map(eb:EmptyBox, mapper:Fun) eb

doc Call cb with the value of the FullBox
doc %RET - fb
doc %EX - Box(10).each(echo)  # Output: 10
F each(fb:FullBox, cb:Fun) { cb(fb.val); fb }

doc Do nothing
doc %RET - eb
doc %EX - Box(null).each(echo)  # No output
F each(eb:EmptyBox, cb:Fun) eb

# each() allows any()
TEST Box(5).any(Int)
TEST EmptyBox().any(Str) == false
TEST EmptyBox().any(Int) == false

# each() allows none()
TEST Box(5).none(Int) == false
TEST Box(5).none(Str)
TEST EmptyBox().none(Int)

doc Conditionaly convert FullBox to EmptyBox.
doc predicate - Test function to be called with the value in the FullBox
doc %RET - Box. fb if predicate succeeds, EmptyBox if not.
doc %EX - Box(10).filter(X>5)   # <FullBox val=10>
doc %EX - Box(10).filter(X>20)  # <EmptyBox>
F filter(fb:FullBox, predicate) {
	p = Pred(predicate)
	p(fb.val) returns fb
	EmptyBox()
}

doc Do nothing
doc %RET - eb
doc %EX - EmptyBox().filter(X>20)  # <EmptyBox>
F filter(eb:EmptyBox, predicate) eb

doc Get FullBox value
doc %RET - Any
doc %EX - Box(10).get()  # 10
F get(fb:FullBox, dflt=null) fb.val

doc Get EmptyBox value. Always throws BoxFail.
F get(eb:EmptyBox) throw BoxFail("Can not get value from EmptyBox")

TEST try EmptyBox().get() catch(e:BoxFail) true

doc Get EmptyBox value
doc %RET - dflt
F get(eb:EmptyBox, dflt) dflt

TEST EmptyBox().get(10) == 10

doc Convert anything to Box (always FullBox)
doc x - value to enclose in a box
doc %RET - FullBox with given value
doc %EX - Box(7).map(X*2).get()  # 14
F Box(x) FullBox(x)

doc Convert Box with no arg to EmptyBox
doc %RET - EmptyBox
doc %EX - Box() == EmptyBox()
doc %EX - Box().get(10)  # 10
doc %EX - Box().map(X*2).get()  # InvalidArgument exception (in "get()")
F Box() EmptyBox()

TEST Box().get(10) == 10
TEST Box() == EmptyBox()

doc Convert null to Box (always EmptyBox)
doc %RET - EmptyBox
doc %EX - Box(null) == EmptyBox()
doc %EX - Box(null).map(X*2).get()  # InvalidArgument exception (in "get()")
F Box(n:Null) EmptyBox()

TEST Box(null) == EmptyBox()

doc Convert array value indexed by the given index
doc idx - key to look in hash
doc %RET - Box. FullBox if the array has the element indexed by idx, EmptyBox otherwise.
doc %EX - my_array = [10, 20]
doc %EX - my_array.Box(1).map(X*2).each(echo)
doc %EX - # output: 40
doc %EX - my_array.Box(5).map(X*2).each(echo)
doc %EX - # no output
F Box(a:Arr, idx) {
	l = a.len()
	if idx >= 0 {
		l <= idx returns EmptyBox()
	} else {
		l < abs(idx) returns EmptyBox()
	}
	FullBox(a[idx])
}

doc Convert hash value indexed by the given key to a Box
doc k - key to look in hash
doc %RET - Box. FullBox if the hash has the element referenced by k, EmptyBox otherwise.
doc %EX - my_hash = {"a": 10, "b": 300}
doc %EX - my_hash.Box("a").map(X*2).each(echo)
doc %EX - # output: 20
doc %EX - my_hash.Box("nope").map(X*2).each(echo)
doc %EX - # no output
F Box(h:Hash, k) {
	k not in h returns EmptyBox()
	FullBox(h[k])
}

doc Do nothing
doc %RET - fb
doc %EX - my_array = [10, 20]
doc %EX - # dflt on FullBox has no effect
doc %EX - my_array.Box(1).dflt(100).map(X*2).each(echo) # HERE
doc %EX - # output: 40
doc %EX - # dflt on EmptyBox creates FullBox with the given value
doc %EX - my_array.Box(5).dflt(100).map(X*2).each(echo)
doc %EX - # output: 200
F dflt(fb: FullBox, x) fb

doc Wrap x in a Box
doc %RET - FullBox with the value x
doc %EX - my_array = [10, 20]
doc %EX - # dflt on FullBox has no effect
doc %EX - my_array.Box(1).dflt(100).map(X*2).each(echo)
doc %EX - # output: 40
doc %EX - # dflt on EmptyBox creates FullBox with the given value
doc %EX - my_array.Box(5).dflt(100).map(X*2).each(echo) # HERE
doc %EX - # output: 200
F dflt(eb: EmptyBox, x) FullBox(x)

doc Compare boxes. Empty boxes and boxes with same content are considered to be equal.
doc %RET - Bool
doc %EX - EmptyBox() == EmptyBox()
doc %EX - EmptyBox() != FullBox(1)
doc %EX - FullBox(1) == FullBox(1)
doc %EX - FullBox(1) != FullBox(2)
F ==(b1:Box, b2:Box) {
	# Boxes comparison stolen from
	# http://learnyouahaskell.com/making-our-own-types-and-typeclasses
	# "instance Eq (Maybe m) where"
	b1 is EmptyBox and b2 is EmptyBox returns true
	b1 is FullBox and b2 is FullBox and b1.val == b2.val returns true
	false
}

TEST EmptyBox() == EmptyBox()
TEST EmptyBox() != FullBox(1)
TEST FullBox(1) == FullBox(1)
TEST FullBox(1) != FullBox(2)

# === Result =====================================
{
	doc Thrown by get(Failure) as it has no value to get
	type ResultFail(Error)

	doc Result of a computation
	doc val - computed value or exception
	type Result

		doc Successful computation
		doc val - computed value
		type Success(Result)

		doc Failed computation
		doc val - exception
		type Failure(Result)

	doc Runs the computation and wraps the result: a value is wrapped in Success and an exception is wrapped in Failure.
	doc %RET - Success or Failure
	F Result(fun:Fun) {
		try {
			Success(fun())
		} catch(e) {
			Failure(e)
		}
	}

	doc Initialize Success with the given value.
	F init(s:Success, v) s.val = v

	doc Initialize Failure with the given value.
	F init(f:Failure, e:Exception) f.val = e

	doc Gets wrapped value
	doc %RET - Any
	doc %EX - { 1 / 10 }.Result().get()  # 0
	F get(s:Success) s.val

	doc Throws ResultFail
	doc %EX - { 1 / 0 }.Result().get()  # ResultFail exception
	F get(f:Failure) {
		throw ResultFail("Can not get value of Failure").set('cause', f.val)
	}

	doc Gets wrapped value
	doc %RET - Any
	doc %EX - { 1 / 10 }.Result().get(100)  # 0
	F get(s:Success, dflt) s.val

	doc Retruns dflt
	doc %EX - { 1 / 0 }.Result().get(100)  # 100
	F get(f:Failure, dflt) dflt

	doc Run fun with wrapped value.
	F each(s:Success, fun:Fun) {
		fun(s.get())
		s
	}

	doc Run fun with wrapped value. If exception is thrown, Failure is returned; otherwise Success with new vaule is returned.
	doc %RET - Result
	F map(s:Success, fun:Fun) {
		try {
			Success(fun(s.get()))
		} catch(e) {
			Failure(e)
		}
	}

	doc No-op, returns f
	doc %RET - f
	F each(f:Failure, fun:Fun) f

	doc No-op, returns f
	doc %RET - f
	F map(f:Failure, fun:Fun) f

	doc Run predicate on wrapped value.
	doc %RET - s or Failure
	doc %EX - Success(10).filter(X>5)   # <Success val=10>
	doc %EX - Success(10).filter(X>15)  # <Failure val=<ResultFail ...>>
	F filter(s:Success, predicate) {
		p = Pred(predicate)
		p(s.val) returns s
		Failure(ResultFail("Success filtered out, resulting Failure").set('filter_predicate', predicate))
	}

	doc No-op, returns f
	doc %RET - f
	doc %EX - Failure("blah").filter(X>5)  # <Failure val=blah>
	F filter(f:Failure, predicate) f

	doc Convert Success to Bool (true)
	doc %RET - true
	F Bool(s:Success) true

	doc Convert Failure to Bool (false)
	doc %RET - false
	F Bool(f:Failure) false

	doc EXPERIMENTAL! Do not use!
	F ExitCode(r:Result) r.Bool().ExitCode()
}

TEST {read("/etc/passwd")}.Result() is Success
TEST {read("NO-SUCH-FILE")}.Result() is Failure
TEST Success(10).map(X*2).get() == 20
TEST try ({ throw Error("xx") }.Result().map(X*2).get()) catch(rf:ResultFail) true

# === Diff =======================================
{

	doc Represents desired target configuration list item presence
	type Presence

		type PartialPresence([FullBox, Presence])

			doc Represents a target configuration list item that must be present
			type Present([FullBox, PartialPresence])

			doc Represents a target configuration list item that must be absent
			type Absent([FullBox, PartialPresence])

		doc Represents a target configuration list item in a list
		type ExactPresence([FullBox, Presence])
}

doc Internal method. Please do not use.
doc Converts Presence or Arr[something] to Arr[Presence]. Used by Res and friends.
F normalize_presence_list(x) {
	econd {
		x is Presence   { [x] }
		x.all(Presence) x
		x is Eachable1  {
			x.any(Presence) throws InvalidArgument("Mixing Presence and non-Presence items in a list is not supported").set('value', x)
			x.map(ExactPresence)
		}
	}
}


{
	doc Represents difference
	type Diff
	doc Represents difference of elements between two arrays (order unimportant)
	type ArrDiff(Diff)
	doc Represents difference of elements between two hashes (order unimportant)
	type HashDiff(Diff)
}

doc Compare arrays. Warning: by default Hash is used so internal Hash keys comparison is used, not ==
doc full - Do not use Hash, work slower but use == comparison.
doc %EX - Diff([1,2], [2,3])  # .add = [3] .remove = [1]
F Diff(a:Arr, b:Arr, full:Bool=false) {
	d = ArrDiff()
	if full {
		d.add    = b.filter(X not in a)
		d.remove = a.filter(X not in b)
	} else {
		ah = Hash(a, {true})
		bh = Hash(b, {true})
		d.add    = bh.reject(X in ah).keys()
		d.remove = ah.reject(X in bh).keys()
	}
	d
}

TEST Diff([1,2], [2,3]).Hash().sort() == {'add': [3], 'remove': [1]}

doc EXPERIMENTAL! Do not use!
doc Compare arrays using eq as equality test. 2*n*m comparisons
doc %RET - ArrDiff
doc %STATUS - experimental
F Diff(a:Arr, b:Arr, eq:Fun) {
	d = ArrDiff()
	d.add    = b.filter(F(x) a.none(eq(x, X)))
	d.remove = a.filter(F(x) b.none(eq(x, X)))
	d
}

doc Compare arrays. Warning: by default Hash is used so internal Hash keys comparison is used, not ==
doc full - Do not use Hash, work slower but use == comparison.
doc b - Arr[PartialPresence]
doc %RET - ArrDiff
doc %EX - Diff([1,2,3], [Present(1)])  # <ArrDiff add=[] remove=[]>
doc %EX - Diff([1,2,3], [Present(5)])  # <ArrDiff add=[5] remove=[]>
doc %EX - Diff([1,2,3], [Absent(1)])   # <ArrDiff add=[] remove=[1]>
doc %EX - Diff([1,2,3], [Absent(5)])   # <ArrDiff add=[] remove=[]>
doc %EX - Diff(["a", "b"], [Present("a"), Present("c"), Absent("b"), Absent("d")])  # <ArrDiff add=[c] remove=[b]>
F Diff(a:Arr, b:Arr, full:Bool=false) {
	guard b and b.all(PartialPresence)

	d = ArrDiff()
	if full {
		d.add    = b.filter(Present).map(get).filter(X not in a)
		d.remove = a.filter(X in b.filter(Absent).map(get))
	} else {
		ah = Hash(a, {true})
		d.add    = Hash(b.filter(Present).map(get), b).reject(X in ah).keys()
		d.remove = ah.filter(X in Hash(b.filter(Absent).map(get), b)).keys()
	}
	d
}

TEST Diff(["a", "b"], [Present("a"), Present("c"), Absent("b"), Absent("d")], false).Hash().sort() == {"add": ["c"], "remove": ["b"]}
TEST Diff(["a", "b"], [Present("a"), Present("c"), Absent("b"), Absent("d")], true).Hash().sort() == {"add": ["c"], "remove": ["b"]}

doc Compare arrays. Warning: by default Hash is used so internal Hash keys comparison is used, not ==.
doc Calls Diff(a, b.map(get), full)
doc full - Do not use Hash, work slower but use == comparison.
doc b - Arr[ExactPresence]
doc %RET - Diff
F Diff(a:Arr, b:Arr, full:Bool=false) {
	guard b and b.all(ExactPresence)
	Diff(a, b.map(get), full)
}

doc Check whether there is a difference
doc %RET - Bool
doc %EX - arr_diff = Diff(current, desired)
doc %EX - # Implicit Bool() when using in "if": if arr_diff -> if Bool(arr_diff)
doc %EX - if arr_diff {
doc %EX -   echo("Will make modifications to the resource")
doc %EX -   if arr_diff.add {
doc %EX -     ...
doc %EX -   }
doc %EX -   if arr_diff.remove {
doc %EX -     ...
doc %EX -   }
doc %EX - }
F Bool(d:ArrDiff) Bool(d.add or d.remove)

doc Compare hashes
doc %EX - diff = Diff(current_tags, target_tags)
doc %EX - if (tags = AWS::cli_tags(diff.add + diff.change)) {
doc %EX - 	r.run('update_tags/add', %(aws ec2 create-tags --resources ${r.id()} --tags $*tags))
doc %EX - }
doc %EX - if (tags = diff.remove / "Key=$X") {
doc %EX - 	r.run('update_tags/remove', %(aws ec2 delete-tags --resources ${r.id()} --tags $*tags))
doc %EX - }
F Diff(a:Hash, b:Hash) {
	d = HashDiff()
	d.add    = b.reject(X in a)
	d.change = b.filter(X in a).filter(F(k, v) a[k] != v)
	d.remove = a.reject(X in b).keys()
	d
}

TEST Diff({"a": 1, "b":2}, {"b": 3, "d": 4}).Hash().sort() == {"add":{"d":4}, "change":{"b":3}, "remove":["a"]}

doc Whether there is a difference
doc %RET - Bool
doc %EX - hash_diff = Diff(current_properties, desired_properties)
doc %EX - # Implicit Bool() when using in "if": if hash_diff -> if Bool(hash_diff)
doc %EX - if hash_diff {
doc %EX -   echo("Will make modifications to the resource")
doc %EX -   if hash_diff.add {
doc %EX -     ...
doc %EX -   }
doc %EX -   if hash_diff.remove {
doc %EX -     ...
doc %EX -   }
doc %EX -   if hash_diff.change {
doc %EX -     ...
doc %EX -   }
doc %EX - }
F Bool(d:HashDiff) Bool(d.add or d.remove or d.change)

# === Bool =======================================

doc Convert a Bool to NGS code that would produce the given Bool when executed. Not fully functional yet.
doc %RET - Str
F code(b:Bool) Str(b)

# === Int ========================================

doc Absolute value of a number
doc %EX - abs(5)   # 5
doc %EX - abs(-5)  # 5
F abs(i:Int) {
	i >= 0 returns i
	0-i
}

# --- Functional ---

doc Iterate from zero up to but not including n
doc cb - Function to call with current number
doc args - Additional arguments for calling cb
doc %EX - 10.each(echo)  # Outputs numbers from 0 to 9 inclusive, one on each line
doc %RET - n
F each(n:Int, cb:Fun) {
	for(i;n) cb(i)
	n
}

TEST 3.map(identity) == [0, 1, 2]
TEST 3.map(X*3) == [0, 3, 6]

doc Call cb n times without arguments.
doc cb - Function to call
doc args - Arguments for calling cb
doc %EX - r=0; 5.times(F() r=r+2);  # r is now 10
F times(n:Int, cb:Fun) {
	for(i;n) cb()
	n
}

TEST r=0; 5.times(F() r=r+2); r==10

doc Convert Int to Int, a no-op
doc %RET - i
F Int(i:Int) i

doc Convert base-10 string to Int.
doc Throws InvalidArgument if the number in s is not well-formatted.
doc %RET - Int
doc %EX - Int(" 100 ")  # 100
F Int(s:Str) Int(s, 10)

TEST Int(" 100 ") == 100
TEST try Int(" XX ") catch(e:InvalidArgument) true
TEST Int(" XX ", 36) == 1221

doc Convert Bool to int.
doc %RET - Int
doc %EX - true.Int()   # 1
doc %EX - false.Int()  # 0
F Int(b:Bool) if b 1 0

TEST true.Int() == 1
TEST false.Int() == 0

doc Convert an Int to NGS code that would produce the integer when executed. Not fully functional yet.
doc %RET - Str
F code(n:Int) Str(n)


# === Str ========================================

# https://docs.python.org/2/library/string.html
CHARS = ns {
	ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
	ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
	ascii_letters = ascii_lowercase + ascii_uppercase
	digits = '0123456789'
	hexdigits_uppercase = '0123456789ABCDEF'
	hexdigits_lowercase = '0123456789abcdef'
	octdigits = '01234567'
	base64 = ascii_uppercase + ascii_lowercase + digits + '+/'
	base64url = ascii_uppercase + ascii_lowercase + digits + '-_'
	html_escape = {'&': '&amp;', '<': '&lt;', '>': '&gt;'}
	html_attr_escape = html_escape + {'"': '&quot;', "'": '&#39;'}
	shell_escape = {'\\': '\\\\', '"': '\\"', "'": "\\'", '&': '\\&'}
	shell_escape_with_eq = shell_escape + {'=': '\\='}

}

# --- Constructors ---

doc No-op constructor
doc %RET - s
F Str(s:Str) s

doc Convert Null to string
doc %RET - the string "null"
F Str(n:Null) "null"
F Str(b:Bool) if b "true" "false"

doc Convert Arr to string
doc %RET - Str
F Str(a:Arr) "[${a.map(Str).join(',')}]"

doc Convert Hash to string
doc %RET - Str
F Str(h:Hash) "{" + h.map(F(k, v) "${k}=${v}").join(", ") + "}"

# --- Functional ---

doc Iterates over all string characters (currently bytes).
doc cb - Function to be called with each character from s
doc args - Additional arguments for calling cb
doc %RET - s
doc %EX - "abc".each(echo)
doc %EX - # Output:
doc %EX - # a
doc %EX - # b
doc %EX - # c
F each(s:Str, cb:Fun) {
	s.len().each(F(idx) {
		cb(s[idx])
	})
	s
}

# --- Sugar ---

doc Find substring in a string.
doc haystack - The string to search in
doc needle - The string to find
doc %RET - Int or null
doc %EX - pos("abc", "cd")     # null
doc %EX - pos("abcdef", "cd")  # 2
F pos(haystack:Str, needle:Str) pos(haystack, needle, 0)

TEST pos("abc", "cd") == null
TEST pos("abcdef", "cd") == 2

TEST pos("a:b:c", ":") == 1
TEST pos("a:b:c", ":", 2) == 3

doc Determine if needle substring occurs at least once in haystack
doc haystack - The string to search in
doc needle - The string to find
doc %RET - Bool
doc %EX - "bc" in "abcd"
doc %EX - "x" not in "abcd"
F in(needle:Str, haystack:Str) pos(haystack, needle) is not Null

TEST "bc" in "abcd"
TEST "x" not in "abcd"

doc Get given character (currently byte) of the string
doc s - Original string
doc i - Index of the character to return
doc %EX - "abc"[0]  # "a"
F '[]'(s:Str, i:Int) s[i..i+1]

TEST ("abc"[0] == "a") and ("abc"[2] == "c")
TEST try "abc"[3] == "x" catch(e:IndexNotFound) true

doc Get given character (currently byte) of the string (negative indexes handler). Throws IndexNotFound if abs(i) > len(s).
doc s - Original string.
doc i - Negative index of the character to return
doc %EX - "abc"[-1]  # "c"
F '[]'(s:Str, i:Int) {
	guard i < 0
	i < 0-s.len() throws IndexNotFound("Negative index into string is (abs) larger than the string")
	s[s.len()+i]
}

TEST ("abc"[-1] == "c") and ("abc"[-3] == "a")
TEST try "abc"[-4] == "x" catch(e:IndexNotFound) true

doc Get a substring. Indexes in s are specified by NumRange.
doc s - Original string
doc r - NumRange with negatve .end
doc %EX - "(Look ma, no parens)"[1..-1]  # "Look ma, no parens"
doc %RET - Str
F '[]'(s:Str, r:NumRange) {
	guard r.end is Int and r.end < 0
	r.end < 0 - s.len() throws InvalidArgument("Negative index (range end) into string is (abs) larger than the string")
	s[r.start..s.len() + r.end]
}

# --- Misc utilities ---

doc Split string by substring
doc s - String to split
doc delim - Delimiter to split by
doc max_parts - Maximum number of resulting parts, 0 - unlimited
doc %RET - Arr of Str
doc %EX - ":a:bc:d:".split(":")   # ["", "a", "bc", "d", ""]
doc %EX - "bucket_name/dir/file".split("/", 2)  # ["bucket_name", "dir/file"]
doc %EX - ":a:bc:d:".split("bc")  # [":a:", ":d:"]
F split(s:Str, delim:Str, max_parts:Int=0) {
	l = delim.len()
	guard l > 0
	start = 0
	parts = 0
	collector {
		while (p = pos(s, delim, start)) is not Null {
			collect(s[start..p])
			start = p + l
			parts += 1
			parts == max_parts - 1 breaks
		}
		collect(s[start..null])
	}
}

TEST ":a:bc:d:".split(":") == ["", "a", "bc", "d", ""]
TEST "bucket_name/dir/file".split("/", 2) == ["bucket_name", "dir/file"]
TEST ":a:bc:d:".split("bc") == [":a:", ":d:"]

doc Repeat string n times
doc %EX - "abc" * 3  # "abcabcabc"
F *(s:Str, n:Int) ([s]*n).join('')

# Tested with Str(Str,Int)

doc Convert anything to Str of a given width
F Str(x, target_width:Int, ch:Str=' ') x.Str().Str(target_width, ch)

doc Pad a string to given width with spaces
doc target_width - Positive pads on right, negative pads on left
doc %EX - Str("x", 3)  # 'x  '
doc %EX - Str("x",-3)  # '  x'
F Str(s:Str, target_width:Int, ch:Str=' ') {
	assert(len(ch) == 1)
	l = s.len()
	pad_on_left = target_width < 0
	if pad_on_left {
		target_width = 0 - target_width
	}

	l >= target_width returns s

	padding = ch * (target_width - l)
	if pad_on_left {
		padding + s
	} else {
		s + padding
	}
}

# Not sure about this, might be confusing behaviour
doc Convert a number to a string and pad it
doc target_width - Positive pads on left, negative pads on right
doc %EX - Str(10,  4)  # '  10'
doc %EX - Str(10, -4)  # '10  '
F Str(n:Int, target_width:Int, ch:Str=' ') n.Str().Str(0-target_width, ch)

TEST Str(10,  4) == '  10'
TEST Str(10,  4, '0') == '0010'
TEST Str(10, -4) == '10  '
TEST Str('x', 3) == 'x  '
TEST Str('x',-3) == '  x'
TEST Str('x',-3, '.') == '..x'

doc Check whether a string starts with another string
doc %RET - Bool
doc %EX - "abcd".starts_with("ab")  # true
doc %EX - "ab".starts_with("abcd")  # false
F starts_with(haystack:Str, needle:Str) {
	needle.len() > haystack.len() returns false
	haystack[0..needle.len()] == needle
}

TEST "abcd".starts_with("ab")
TEST "ab".starts_with("abcd") == false

doc Check whether a string ends with another string
doc %RET - Bool
doc %EX - "abcd".ends_with("cd")  # true
doc %EX - "ab".ends_with("cdab")  # false
F ends_with(haystack:Str, needle:Str) {
	needle.len() > haystack.len() returns false
	l = haystack.len()
	haystack[l - needle.len()..l] == needle
}

TEST "abcd".ends_with("cd")
TEST "ab".ends_with("cdab") == false


doc Case-insensitive LessThan or Equal comparison for strings
doc %RET - Bool
F lte(a:Str, b:Str)
	c_strcasecmp(a, b) <= 0

doc Case sensitive LessThan or Equal comparison for strings
doc %RET - Bool
F '<='(a:Str, b:Str)
	c_strcmp(a, b) <= 0

doc Case sensitive LessThan comparison for strings
doc %RET - Bool
F '<'(a:Str, b:Str)
	c_strcmp(a, b) < 0

doc Case sensitive GreaterThan comparison for strings
doc %RET - Bool
F '>'(a:Str, b:Str)
	c_strcmp(a, b) > 0

doc Split s to strings using end-of-line separators.
doc Same as Lines(s).Arr()
doc %RET - Arr
F lines(s:Str) Lines(s).Arr()

doc Split s to strings using end-of-line separators and call cb for each one of the lines.
doc TODO: More efficient implementation, which would not have temporary array of all lines.
doc cb - Function to be called with each line
doc args - Additional arguments for calling cb
F lines(s:Str, cb:Fun) {
	lines(s).each(cb)
}

TEST "xx\nyy".lines() == %[xx yy]

doc Prepend each line in a with s
doc %EX - "a " + ["1", "2"]  # ["a 1", "a 2"]
doc %RET - Type of ret is same as type of a
F +(s:Str, a:Eachable1) {
	guard a is not Str
	guard a.all(Str)
	a.mapo(s+X)
}
TEST "a " + ["1", "2"] == ["a 1", "a 2"]

doc Append s to each line in a
doc %EX - ["1", "2"] + " a"  # ["1 a", "2 a"]
doc %RET - Type of ret is same as type of a
F +(a:Eachable1, s:Str) {
	guard a is not Str
	guard a.all(Str)
	a.mapo(X+s)
}
TEST ["1", "2"] + " a" == ["1 a", "2 a"]

doc Map a string, character by character.
doc %EX - "abcd".mapo(F(x) if x == "b" then "X" else x)  # "aXcd"
doc %RET - Str
F mapo(s:Str, mapper:Fun) s.map(mapper).join('')

TEST "abcd".mapo(F(x) if x == "b" then "X" else x) == "aXcd"

doc Truncate a string if necessary so it would have maximum n characters (currently bytes).
doc s - The string to (possibly) truncate.
doc n - Maximum characters
doc marker - The truncation marker
doc %RET - Either s or new Str of length n
doc %EX - "abc".limit(5, "...")     # "abc"
doc %EX - "abcdef".limit(5, "...")  # "ab..."
doc %EX - "abcdef".limit(2)         # "ab"
F limit(s:Str, n:Int, marker:Str='') {
	s.len() <= n returns s
	if marker {
		lim = n - len(marker)
		s[0..lim] + marker
	} else {
		s[0..n]
	}
}

TEST "abc".limit(5, "...") == "abc"
TEST "abcdef".limit(5, "...") == "ab..."
TEST "abcdef".limit(2) == "ab"

doc Get character (currently byte) code. Throws InvalidArgument if s is not of length 1.
doc %EX - ord("A")  # 65 on my machine
F ord(s:Str) {
	s.len() != 1 throws InvalidArgument("ord() argument must be of length 1 exactly").set('given', s)
	ord(s, 0)
}

doc Find substring in string. Uses pos().
doc %RET - MatchResult
doc %EX - "abc" ~ "bc"  # <MatchSuccess ...>
doc %EX - "abc" ~ "X"   # <MatchFailure>
F ~(haystack:Str, needle:Str, offset:Int=0) {
	p = pos(haystack, needle, offset)
	p is Null returns MatchFailure()
	l = needle.len()
	ret = MatchSuccess([needle])
	ret.named = {}
	ret.positions = [[p, p+l]]
	ret.whole = ret.matches[0]
	ret.before = haystack[0..p]
	ret.after = haystack[p+l..null]
	ret
}

doc Find all non-overlapping matches of a substring in a string.
doc %RET - if collect_unmatched - Arr with each element being MatchSuccess or Str, if not collect_unmatched - Arr of MatchSuccess
doc %EX - ["key=value", "key2=value2"].map(F(kv) {
doc %EX -   m = kv ~ "="
doc %EX -   [m.before, m.after]
doc %EX - }).Hash()  # {'key': 'value', 'key2': 'value2'}
F ~~(haystack:Str, needle:Str, collect_unmatched:Bool=false) {
	collector {
		m = (~)(haystack, needle, 0)
		if not(m) {
			if collect_unmatched collect(haystack)
			return null
		}
		start_offset = m.positions[0][0]
		next_offset = m.positions[0][1]
		if collect_unmatched and start_offset then collect(haystack[0..start_offset])
		collect(m)
		while true {
			if start_offset == next_offset {
				next_offset == len(haystack) breaks
			}
			m = (~)(haystack, needle, next_offset)
			if m {
				if collect_unmatched {
					if next_offset != m.positions[0][0] {
						collect(haystack[next_offset..m.positions[0][0]])
					}
				}
				start_offset = m.positions[0][0]
				next_offset = m.positions[0][1]
				collect(m)
				continue
			}
			break
		}
		if collect_unmatched and (next_offset < len(haystack)) {
			collect(haystack[next_offset..null])
		}
	}
}

TEST m = (~~)("abcbe", "b", true); m.len() == 5 and m[[0,2,4]] == %[a c e] and m[[1,3]].all(MatchSuccess)

doc Replace all occurrences of src with dst in s
F replace(s:Str, src:Str, dst:Str) (~~)(s, src, true).map(only(MatchSuccess, {dst})).join('')

TEST "x10ab20c30y".replace("0", "X") == "x1Xab2Xc3Xy"

doc Convert a Str to NGS code that would produce the string when executed. Not fully functional yet.
doc BUG: Does not do escaping.
doc %RET - Str
F code(s:Str) {
	# XXX TODO: escaping
	"'${s}'"
}

doc String expansion handler. Called automatically for every double-quoted string that has $* components.
doc %EX - "$*{ENV.PATH.split(":")}/od".filter(File(X))  # Find out where in PATH is the "od" binary
doc %AUTO - "abc$*{something}def"
F '"$*"'(components:Arr) {
	components.len() == 0 throws InvalidArgument("Must be one or more component")
	c = components
	c_len = c.len()
	cached_str = c.map(F(elt:NgsStrComp) {
		elt is not NgsStrCompSplatExp returns Str(elt.val)
	})
	collector {
		F kern(acc:Arr, i:Int) {
			if i == c_len {
				collect(acc.join(''))
				return
			}
			if c[i] is NgsStrCompSplatExp {
				c[i].val.each(F(v) kern(acc + [v], i+1))
			} else {
				kern(acc + [cached_str[i]], i+1)
			}
		}
		kern([], 0)
	}
}

TEST "a$*{[1,2]}b$*{10..12}c" == ["a1b10c", "a1b11c", "a2b10c", "a2b11c"]


# === Stats ========================================

{
	doc A group of named counters
	doc h - The underlying Hash
	doc %EX - s = Stats().push('a').push('a').push('b')
	doc %EX - s["a"]  # 2
	doc %EX - s["b"]  # 1
	doc %EX -
	doc %EX - a = ["x", "y", "y"]
	doc %EX - s = Stats(a)
	doc %EX - s["x"]  # 1
	doc %EX - s["y"]  # 2
	type Stats(HashLike)
}

doc Makes Stats, with each element in the array counted as if push()ed
doc %EX - Stats(['a', 'a', 'b']).Hash()  # {'a': 2, 'b': 1}
F init(s:Stats, a:Arr) {
	init(s)
	a.each(push(s, X))
}

doc Increment the named counter
doc k - the name of the counter to increment
doc %EX - Stats().push("a").push("a").push("b")["a"]  # 2
F push(s:Stats, k) {
	h = s.attrs().HashLike
	h[k] = h.get(k, 0) + 1
	s
}

TEST Stats().push('a').push('a').push('b').Hash() == {'a': 2, 'b': 1}
TEST Stats(['a', 'a', 'b']).Hash() == {'a': 2, 'b': 1}
TEST Stats(['a', 'a', 'b'])['a'] == 2
TEST Stats(['a', 'a', 'b']).a == 2

# === Thread ========================================
ns {
	global Thread, Threads, ThreadFail, init, join, pmap, ptimes, Str, (.)
	# TODO: consider *args for consistency with other parts of the language

	doc Execution thread. Currently a POSIX thread.
	type Thread

	doc Threads
	type Threads(ArrLike)

	# TODO: expose. Not called automatically because some names are
	#       already unique.
	_threads_names_lock = Lock()
	_threads_names_counters = Stats()
	F _make_thread_name(s:Str) {
		_threads_names_lock.acquire({
			_threads_names_counters.push(s)
			"${s}-${_threads_names_counters[s]}"
		})
	}

	doc Parent type of various thread exceptions
	type ThreadFail(Exception)

		doc Thrown when creating a thread (currently - c_pthread_create()) fails
		type ThreadCreateFail(ThreadFail)

		doc Thrown when joining a thread (currently - c_pthread_join()) fails
		type ThreadJoinFail(ThreadFail)

		doc Thrown where join()ing another thread that threw an exception
		doc %EX - Thread(F() 1/0).join()  # OtherThreadFail with .cause DivisionByZero
		type OtherThreadFail(ThreadFail)

	doc Creates and runs a thread. The code that the created thread runs is f, which is passed arg.
	F init(t:Thread, name:Str, f:Fun, arg) {
		t.id = name
		debug("process", "Creating thread ${t.id}")
		thread_attr = c_pthread_attr_t()
		c_pthread_attr_init(thread_attr)
		thread_setup_wrapper = F(t_arg) {
			# Not sure I can reference t here because the call frame
			# might have been removed already, so passing t via the argument
			Thread.local.thread = t_arg[0]
			debug("process", "Thread set up done, will run thread code")
			f(t_arg[1])
		}
		create_result = c_pthread_create(thread_attr, thread_setup_wrapper, [t, arg])
		code = create_result[0]
		if code {
			throw ThreadCreateFail("Failed to c_pthread_create").set('code', code)
		}
		t.thread = create_result[1]
	}

	doc Creates and runs a thread. The code that the created thread runs is f, which is passed arg.
	F init(t:Thread, f:Fun, arg) {
		super(t, 'unnamed', f, arg)
	}

	doc Creates and runs a thread. The code that the created thread runs is f without arguments.
	F init(t:Thread, f:Fun) {
		init(t, F thread_arg_discard_wrapper(discard) f(), null)
	}

	doc Creates and runs a thread. The code that the created thread runs is f without arguments.
	F init(t:Thread, name:Str, f:Fun) {
		init(t, name, F thread_arg_discard_wrapper(discard) f(), null)
	}

	# Not sure yet: %STATUS - deprecated
	doc Joins threads.
	doc threads - Arr of Thread.
	doc %RET - Arr, the results from threads, in order.
	F join(threads:Arr) {
		guard threads and threads.all(Thread)
		warn("Using deprecated join(threads:Arr)")
		threads.map(join)
	}

	doc Joins threads.
	doc %RET - Arr, the results from threads, in order.
	F join(threads:Threads) threads.map(join)

	doc Joins on thread. Waits for the thread to finish and returns the result from the thread.
	doc Currently, if a thread throwed an exception, it will be returned as the value.
	doc In future it might re-throw the exception, probably wrapped in ThreadExeption.
	doc %RET - Any
	F join(t:Thread) {
		debug("process", "Joining thread ${t}")
		join_result = c_pthread_join(t.thread)
		# join_result: [ join_status, [ result_is_exception:Bool, result ] ]
		if join_result[0] {
			throw ThreadJoinFail("Failed to c_pthread_join").set('code', code)
		}
		if join_result[1][0] {
			throw OtherThreadFail("Joined thread that threw exception").set('cause', join_result[1][1]).set('thread', t)
		}
		join_result[1][1]
	}

	# TODO: maybe limit number of concurrent threads (default to cores count?)
	doc Parallel map. Runs mapper in threads. Each thread processes one element from the array but this might change in future (preserving the total number of calls to mapper and the order of results).
	doc %RET - Arr, result of applying mapper to elements of e, preserving the order.
	doc %EX - pages_texts = abs_pages_urls.pmap(F(url)  `lynx -dump $url`)
	F pmap(e:Eachable1, mapper:Fun) {
		e_hash = hash(e)
		e.map_idx_val(F(idx, val) Thread("pmap-${e_hash}-${idx}", mapper, val)).map(join)
	}

	doc Run cb in n parallel threads. Each thread runs one cb but this might change in future (preserving the total n calls to cb).
	F ptimes(n:Int, cb:Fun) {
		threads = collector/Threads()
			for(i;n) {
				collect(Thread(cb))
			}
		threads.join()
	}

	TEST (1..3).Arr().pmap(X*10) == [10, 20]
	TEST 3.pmap(X*10) == [0, 10, 20]

	F Str(t:c_pthread_t) "<c_pthread_t ${id(t)}>"
	F Str(t:Thread) "<Thread ${t.id}>"

	F .(t:Type, field:Str) {
		guard t === Thread and field == 'local'
		ll_thread_local()
	}

	# ASSUMPTION: Thread is loadad in main thread
	assert('thread' not in Thread.local)

	Thread.local.thread = Thread().set('id', 'main').set('thread', 'MAIN THREAD REFERENCE IS NOT IMPLEMENTED YET')

}

# === Logging and status reporting (WIP) =========

{
	doc Represents an exception that should cause exit from the program
	doc exit_code - Contains the exit code to be used by ExitCode
	type ExitException(Exception)
		doc Represents a fatal error condition that causes the program to exit.
		doc %EX - throw ExitException("Input file not found")
		type FatalError(ExitException)
		type NormalExit(ExitException)
}

doc Initializes ExitException.
F init(ee:ExitException, message:Str, exit_code:Int=1) {
	super(ee, message)
	ee.exit_code = exit_code
}

F init(ee:ExitException, exit_code:Int=1) ee.exit_code = exit_code

doc Convert ExitException to an exit code.
doc %RET - ee.exit_code
F ExitCode(ee:ExitException) ee.exit_code

# TODO: timestamps

# TODO: allow control by facility and severity
#       and maybe source component or file.

# Not sure such flexibility is needed (NGS_ERR_FD)
stdlib_error_fd = ENV.NGS_ERR_FD.Int() tor 2

ns {
	global maybe_print_stacktrace

	# Set is not available at this point yet so using Hash as Set
	seen_backtraces = {}

	doc Do not use directly!
	doc %STATUS - internal
	F maybe_print_stacktrace(env_var:Str, pfx:Str) {
		ENV.get(env_var, '0').decode(Bool).not() returns
		bt = Exception("maybe_print_stacktrace").backtrace
		k = bt.frames.ip.map(Str).join(':')
		k in seen_backtraces returns
		seen_backtraces[k] = true
		msg = Lines(["(Showing backtrace because ${env_var} environment variable is set)"]) + Lines(bt)
		echo(stdlib_error_fd, (pfx +? ' ') + msg)
	}
}

doc Log to standard error. Later log output will be treated specially by the shell. It will have suitable representation in the UI. Use log() when it's semantically a log.
F log(s:Str) {
	echo(stdlib_error_fd, "[LOG ${Time()}] $s")
}

doc Same as debug('default', s)
F debug(s:Str) debug('default', s)

# TODO: more efficient
doc Debug to standard error.
doc "DEBUG" environment variable must be non-empty string to activate. Otherwise nothing is outputted.
doc TODO: Not output thread ID if there is only one thread.
doc TODO: Timestamps? Timestamps acquiring might not be safe after fork before exec.
F debug(facility:Str, s:Str) {
	if ENV.Box('DEBUG').map(split(X, ',')).map({facility in A or '*' in A}).get(false) {
		echo(stdlib_error_fd, "[DEBUG $facility ${c_getpid()} ${Thread.local.thread.id tor c_pthread_self().id()}] $s")
	}
}

doc Write error message to standard error.
doc %EX - error("Failed to read configuration file. Will clean up and exit now.")
doc %EX - # Approximate output on stderr:
doc %EX - # [ERROR 2018-01-01 00:00:00 YOUR_TZ] Failed to read configuration file. Will clean up and exit now.
F error(s:Str) {
	echo(stdlib_error_fd, "[ERROR ${Time()}] $s")
	maybe_print_stacktrace('NGS_ERROR_BACKTRACE', '[ERROR BACKTRACE]')
}

doc Write warning message to standard error. Prints backtrace if NGS_TRACE_WARNINGS environment variable is not an empty string.
doc %EX - warn("Could not open input file $my_file , skipping it.")
doc %EX - # Approximate output on stderr:
doc %EX - # [WARNING 2018-01-01 00:00:00 YOUR_TZ] Could not open input file ./my_file , skipping it.
F warn(s:Str) {
	echo(stdlib_error_fd, "[WARNING ${Time()}] $s")
	maybe_print_stacktrace('NGS_WARN_BACKTRACE', '[WARNING BACKTRACE]')
}

ns {
	global status

	status_terminal = null

	F status(s) {
		if status_terminal is Null {
			status_terminal = Terminal(stdlib_error_fd, stdlib_error_fd)
		}
		status_terminal.status(s)
	}
}

doc Write message in s to standard error and exit, printing backtrace
doc status - converted to exit code using ExitCode()
F die(s:Str, status=1) throw FatalError(s, status.ExitCode())

doc Exit with given status
doc status - converted to exit code using ExitCode()
F exit(status=1) throw NormalExit(status.ExitCode())

doc Write message in s to standard error and exit
doc status - converted to exit code using ExitCode()
F exit(s:Str, status=1) throw NormalExit(s, status.ExitCode())

# === Path =======================================

# Maybe TODO: F ==(Path,Path) --> https://stackoverflow.com/questions/12502552/can-i-check-if-two-file-or-file-descriptor-numbers-refer-to-the-same-file
{
	doc Represents file system path such as a file, a block device, etc
	type Path
		doc Represents a socket file in a file system (S_IFSOCK)
		type SocketFile(Path)  # S_IFSOCK
		doc Represents a link in a file system (S_IFLNK)
		type Symlink(Path)     # S_IFLNK
		doc Represents a file in a file system (S_IFREG)
		type File(Path)        # S_IFREG
		doc Represents a block device in a file system (S_IFBLK)
		type BlockDevice(Path) # S_IFBLK
		doc Represents a directory in a file system (S_IFBLK)
		type Dir(Path)         # S_IFDIR
		doc Represents a character device in a file system (S_IFCHR)
		type CharDevice(Path)  # S_IFCHR
		doc Represents a fifo file in a file system (S_IFIFO)
		type FifoFile(Path)    # S_IFIFO

	doc Represents a failure in stat() system call.
	type StatFail(CException)

}

# TODO: reconsider naming
STDLIB_FILE_TYPE = {
	C_S_IFSOCK: SocketFile
	C_S_IFLNK:  Symlink
	C_S_IFREG:  File
	C_S_IFBLK:  BlockDevice
	C_S_IFDIR:  Dir
	C_S_IFCHR:  CharDevice
	C_S_IFIFO:  FifoFile
}
{ STDLIB_FILE_TYPE.attrs({'doc': {'': 'Mapping between S_IFMT bits of st_mode returned by stat()/lstat() and NGS types. All types in this Namespace are subtypes of Path.'}}) }

doc Issue stat() system call. Throws StatFail if the call fails.
doc %RET - Stat
doc %EX - stat("/tmp")  # <Stat st_dev=51714 st_ino=25 st_mode=17407 ...>
F stat(pathname:Str) {
	ret = c_stat(pathname)
	ret is Null throws StatFail("Failed to c_stat()").set('pathname', pathname)
	ret
}

doc Issue stat() system call. Throws StatFail if the call fails.
doc %RET - Stat
F stat(p:Path) super(p.path)

doc Issue lstat() system call. Throws StatFail if the call fails.
doc %RET - Stat
doc %EX - stat("/usr/bin/cal").st_mode   # 33261
doc %EX - lstat("/usr/bin/cal").st_mode  # 41471
F lstat(pathname:Str) {
	ret = c_lstat(pathname)
	ret is Null throws StatFail("Failed to c_lstat()").set('pathname', pathname)
	ret
}

doc Issue lstat() system call. Throws StatFail if the call fails.
doc %RET - Stat
F lstat(p:Path) super(p.path)

# TODO: better name
doc EXPERIMENTAL, do not use outside of stdlib!
doc Instanciates Path sub-type, depending on what p is
F specific(p:Path) {
	s = lstat(p)
	file_type = s.st_mode.band(C_S_IFMT)
	STDLIB_FILE_TYPE[file_type](p.path).set('stat', s)
}

doc Path constructor
doc s - path
doc subtype - Return Path sub-type, depending on lstat() call
doc %RET - Path or sub-type of Path
doc %EX - Path(".")  # <Path path=.>
doc %EX - Path(".", true)  # <Dir path=.>
doc %EX - ``find tmp/v8``.map(Path(X, true)).map(typeof).name.Stats()  # <Stats: {Dir=287, File=9220}>
F Path(s:Str, subtype=false) {
	ret = Path()
	ret.path = s
	if subtype {
		ret.specific()
	} else {
		ret
	}
}

doc Path constructor
doc s - path
F init(p:Path, s:Str) {
	p.path = s
}

doc Path constructor. Duplicates other Path.
doc other - Path to duplicate
F init(p:Path, other:Path) {
	p.path = other.path
}

doc Checks whether the path is accessible using access(2) and F_OK.
doc %RET - Bool
F Bool(p:Path) c_access(p.path, ACCESS::F_OK) == 0

TEST Path('/').Bool()
TEST Path('/no-such-file').Bool() == false
TEST Path('/', true) is Dir

doc Check whether file system object at given path
doc is of the given type.
doc %EX - if File("myfile.txt") ...
doc %EX - if Dir("my_tmp_dir") ...
doc %STATUS - experimental
F Bool(p:Path) {
	# Only subclasses
	guard typeof(p) != Path
	ok = super(p)
	not(ok) returns false
	s = lstat(p)
	file_type = s.st_mode.band(C_S_IFMT)
	p is STDLIB_FILE_TYPE[file_type]
}

# TODO: better exceptions (use correct type, not string, maybe use errno)
# TODO: support platforms with non ":" path delimiter?
doc Finds given binary and returns it's full path.
doc Throws ExecutableNotFound if the binary was not found.
doc Search strategy: "/" in the name of the binary means that given executable_name is a path so it's returned as-is (wrapped in Path).
doc If PATH environment variable exists, the given directories are searched.
doc If PATH is not set built-in value for PATH is used to search: /usr/local/bin:/usr/bin:/bin:/sbin:/usr/sbin
doc %RET - Path
doc %EX - find_in_path("ls")  # <Path path=/bin/ls>
F find_in_path(executable_name:Str) {
	debug("process", "[find_in_path] got ${executable_name}")
	if "/" in executable_name {
		debug("process", "[find_in_path] leaving unprocessed ${executable_name}")
		return Path(executable_name)
	}
	# TODO: rethink default PATH
	path = ENV.get('PATH', '/usr/local/bin:/usr/bin:/bin:/sbin:/usr/sbin').split(':')
	debug("process", '[find_in_path] will search')
	ret = path.map(F(dir) Path(dir / executable_name)).first(identity, null)
	debug("process", "[find_in_path] ${executable_name} found at ${ret}")
	ret is Null throws ExecutableNotFound().set('path', path).set('name', executable_name)
	ret
}

doc String representation of a Path (or it's sub-type)
doc %RET - Str
doc %EX - find_in_path("ls").Str()  # The string: <Path path=/bin/ls>
F Str(p:Path) "<${p.typeof().name} path=${p.path}>"

doc Concatenate two path parts using STDLIB_PATH_SEP (currently "/") but should be platform-specific later.
doc %RET - Str
doc %EX - mydir="tmp"
doc %EX - mydir / "myfile"  # "tmp/myfile"
F /(a:Str, b:Str) "$a$STDLIB_PATH_SEP$b"

doc Concatenate two path parts using STDLIB_PATH_SEP (currently "/") but should be platform-specific later.
doc %RET - Str
doc %EX - mydir="tmp/"
doc %EX - mydir / "myfile"  # "tmp/myfile"
F /(a:Str, b:Str) {
	guard a and (a[-1] == STDLIB_PATH_SEP)
	"$a$b"
}

doc Concatenate two path parts using STDLIB_PATH_SEP (currently "/") but should be platform-specific later.
doc %RET - Str
doc %EX - mydir="./"
doc %EX - mydir / "myfile"  # "myfile"
F /(a:Str, b:Str) {
	guard (a == '.') or (a == './')
	b
}

doc Concatenate two Path-s using /(a:Str, b:Str)
doc %RET - Path
doc %EX - Path("tmp") / Path("v8")  # <Path path=tmp/v8>
F /(a:Path, b:Path) Path(a.path / b.path)

doc Concatenate two Path-s using /(a:Str, b:Str)
doc %RET - Path
doc %EX - Path("tmp") / "v8"  # <Path path=tmp/v8>
F /(a:Path, b:Str) Path(a.path / b)

{ type DirFail(CException) }

# TODO: recode after https://github.com/ngs-lang/ngs/issues/45 is solved
doc List directory contents. Warning: "." and ".." are included.
doc Throws DirFail when directory can not be listed.
doc subtype - Select type of returned items: true for Path sub-type, false for Path type
doc %RET - Arr of Path or it's sub-type
doc %EX - dir("tmp/v8", true).filter(File)  # [ ..., <File path=tmp/v8/README.md fd=null>, <File path=tmp/v8/LICENSE.valgrind fd=null>, ... ]
doc %EX - dir("tmp/v8", true).filter(Dir)   # [ ..., <Dir path=tmp/v8/tools>, <Dir path=tmp/v8/infra>, ... ]
F dir(dirname:Str, subtype=false, **kwargs) collector dir(dirname, collect, subtype, **(kwargs.without('subtype')))

# TODO: recurse ?
# TODO: filter out "." and ".." ?
doc List directory contents and call cb with Path() of each found item. Warning: "." and ".." are included.
doc %RET - unspecified at this time, do not count on it
doc %EX - 's=Stats(); dir("tmp/v8", {s.push(A.typeof().name)}, true); s  # <Stats: {File=23, Dir=16}>'
F dir(dirname:Str, cb:Fun, subtype=false, raw=false) {
	d = c_opendir(dirname)
	d is Null throws DirFail('Failed to list directory contents').set('dirname', dirname)
	SKIP_DIRS = ['.', '..']
	finally()
		body => {
			while entry = c_readdir(d) {
				entry.d_name in SKIP_DIRS continues
				if raw {
					cb(entry.d_name)
				} else {
					cb(Path(dirname / entry.d_name, subtype=subtype))
				}
			}
		}
		cleanup => {
			r = c_closedir(d)
			r != 0 throws DirFail('Failed to close directory after listing').set('dirname', dirname)
		}
}

# XXX: might not be correct on all platforms
TEST dir("/").path.has("/var")
TEST dir("/").all({A.typeof().name == 'Path'})
TEST dir("/", subtype=true).all({ (A is Path) and (A.typeof().name != 'Path') })

doc Same as dir(dirname.path, *args)
F dir(dirname:Path, *args, **kwargs) dir(dirname.path, *args, **kwargs)

doc Same as a.path > b.path
F '>'(a:Path, b:Path) a.path > b.path

doc Work in progress, do not use!
F glob(pattern:Str, start_dir='.') {
	throw NotImplemented("glob() is not implemented yet")
}

doc Convert to string, appropriate for using as argument to external process.
doc %AUTO - $(mycommand $mypath) # mypath is Path
doc %EX - conf_files = [Path("/usr/local/etc/some.conf"), Path("/etc/some.conf")].filter(Bool(X))
doc %EX - $(ls -l $*conf_files)
F Arg(p:Path) p.path

{
	doc Represents a failure in chdir() system call.
	type CdFail(CException)
}

# TODO p must be either Path or a Dir, not any subtype of Path
doc Change directory. Uses CHDIR(2).
doc p - Directory to cd to.
doc %RET - null
F chdir(p:Path) chdir(p.path)

doc Change directory. Uses CHDIR(2).
doc s - Directory to cd to.
doc %RET - null
F chdir(s:Str) {
	t = c_chdir(s)
	t throws CdFail("Failed to chdir to '${s}'").set('dir', s)
	null
}

# === Commands and processes (WIP) ===============

{
	type ProcessesPipeline
	type ProcessRedir
}

F init(pp:ProcessesPipeline, cp:CommandsPipeline) {
	pp.cp = cp
	pp.processes = []
	pp.pipe_in = null
	pp.pipe_out = null
}

F init(pr:ProcessRedir, cr:CommandRedir) {
	pr.fd = cr.fd
	pr.marker = cr.marker
	pr.datum = cr.datum
}

F init(pr:ProcessRedir, fd, marker, datum) init(args())

doc Duplicate a file descriptor. Uses DUP2(2). Handles EINTR.
F dup2(oldfd:Int, newfd:Int) {
	while true {
		status = c_dup2(oldfd, newfd)
		status != -1 returns newfd
		c_errno() != C_EINTR throws FileIOFail("Failed to c_dup2()").set('oldfd', oldfd).set('newfd', newfd)
	}
}

# TODO: Use some thread-local copy of the environment?
#       This would allow simple handling of modifications
#       for exec'ed processes.

# TODO: detect and process errors, throw exception(s)
# TODO: better exceptions (use correct type, not string, maybe use errno)
doc Read all data from a file referenced by file descriptor without parsing it.
doc fd - File descriptor to read from
doc %RET - Str
doc %EX - read(0)  # All data from stdin
F read(fd:Int, count=null) {
	guard count is Int or count is Null
	count == 0 throws InvalidArgument("read(fd, count) - count can't be 0").set('fd', fd)
	ret = []
	to_read = count
	while true {
		result = c_read(fd, to_read or 4096)
		# debug("file", "[FD $fd] Read ${result[0]} bytes <<${result.Box(1).dflt('(none)').get().SafeStr()}>>")
		debug("file", "[FD $fd] Read ${result[0]} bytes")
		result[0] == 0 returns ret.join('')
		if result[0] > 0 {
			ret.push(result[1])
			if count is not Null {
				to_read -= len(result[1])
				to_read <= 0 returns ret.join('')
			}
		} else {
			e = c_errno()
			if e != C_EINTR {
				debug("file", "[FD $fd] read failed, errno $e")
				# TODO: Better exception
				throw ReadFail("Failed to read()").set('fd', fd).set('cause', CException("Failed to c_read()"))
			}
		}
	}
}

doc Read all data from a file referenced by file descriptor 0 (stdin) without parsing it. Same as read(0)
F read() read(0)

doc DEPRECATED! Do not use!
doc %STATUS - deprecated
F write(s:Str, fd:Int) {
	warn("Using deprecated write() arguments order")
	write(fd, s)
}

doc Write data to a file referenced by file descriptor.
doc WARNING: Incomplete implementation.
doc TODO: handle errors, throw exceptions.
doc TODO: handle possible EINTR.
doc fd - File descriptor to write to
doc %RET - unspecified at this time, do not count on it
F write(fd:Int, s:Str) fd.c_write(s)

{ type TtyCheckFail(CException) }

doc Check whether given fd represents a TTY. Uses ISATTY(3).
doc Throws TtyCheckFail.
doc %RET - Bool
F isatty(fd:Int) {
	ret = c_isatty(fd)
	errno = c_errno()

	ret == 1 returns true
	ret != 0 throws TtyCheckFail("c_isatty($fd) - unknown response code $ret").set('fd', fd).set('isatty_returned', ret)

	errno in [C_EINVAL, C_ENOTTY] returns false
	throw TtyCheckFail("c_isatty() - failed").set('fd', fd)
}

# --- Pipe ---

# http://www.microhowto.info/howto/capture_the_output_of_a_child_process_in_c.html

{
	doc Wrapper around file descriptors returned by PIPE(2)
	type Pipe
		type PipeToChildProcess(Pipe)
			type PipeFromParentToChildProcess(PipeToChildProcess)
			type ReadingPipeBetweenChildren(PipeToChildProcess)
		type PipeFromChildProcess(Pipe)
			type PipeFromChildToParentProcess(PipeFromChildProcess)
				type CollectingPipeFromChildToParentProcess(PipeFromChildProcess)
			type WritingPipeBetweenChildren(PipeFromChildProcess)
	doc Represents failure of creating a Pipe when calling PIPE(2)
	type PipeCreateFail(CException)
}

# TODO: better exceptions (use correct type, not string, maybe use errno)
doc Pipe constructor. Create UNIX pipe using PIPE(2). Throws PipeCreateFail if pipe can not be created.
doc %EX - p = Pipe()
F init(pipe:Pipe) {
	result = c_pipe()
	# result: [result_code, read_end, write_end]
	result[0] != 0 throws PipeCreateFail("Failed to create Pipe")
	pipe.read_fd = result[1]
	pipe.write_fd = result[2]
	debug("file", "${pipe.typeof().name} created pipe with read_fd=${pipe.read_fd} and write_fd=${pipe.write_fd}")
}

doc Initializes Pipe, copying read_fd and write_fd from another Pipe.
doc %EX - my_pipe = ...
doc %EX - second_pipe = Pipe(my_pipe)
F init(pipe:Pipe, other:Pipe) {
	pipe.read_fd = other.read_fd
	pipe.write_fd = other.write_fd
}

doc Get child process end file descriptor of Pipe.
F child_fd(pipe:PipeToChildProcess) pipe.read_fd

doc Get child process end file descriptor of Pipe.
F child_fd(pipe:PipeFromChildProcess) pipe.write_fd

doc Get parent process end file descriptor of Pipe.
F parent_fd(pipe:PipeToChildProcess) pipe.write_fd

doc Get parent process end file descriptor of Pipe.
F parent_fd(pipe:PipeFromChildProcess) pipe.read_fd

F Str(p:Pipe) "<${p.typeof().name} read_fd=${p.read_fd} write_fd=${p.write_fd}>"

# TODO: exception on fail, maybe close() wrapper for c_close()

doc Close writing end of the Pipe
F close_writing_end(p:Pipe) p.write_fd.c_close()

doc Close reading end of the Pipe
F close_reading_end(p:Pipe) p.read_fd.c_close()

doc DEPRECATED! Do not use!
doc %STATUS - deprecated
F write(s:Str, p:Pipe) {
	warn("Using deprecated write() arguments order")
	write(p, s)
}

doc Write to Pipe. TODO: document if it throws.
doc %RET - unspecified at this time, do not count on it
F write(p:Pipe, s:Str) p.write_fd.c_write(s)

doc Read from Pipe without parsing. TODO: document if it throws.
doc %RET - read data
doc %EX - data = read(myipe)
F read(p:Pipe, count=null) {
	guard count is Int or count is Null
	p.read_fd.read(count)
}

doc DUP2(2) writing file descriptor
F dup2_writing_end(p:Pipe, newfd:Int) dup2(p.write_fd, newfd)

doc DUP2(2) reading file descriptor
F dup2_reading_end(p:Pipe, newfd:Int) dup2(p.read_fd, newfd)

# --- File ---

{ type FileIOFail(CException) }

doc Create File object from the given path. The file is not open.
doc %EX - f = File('/tmp/myfile')
F init(f:File, path:Str) {
	f.path = path
	f.fd = null
}

doc Create File object from the given file descriptor.
F init(f:File, fd:Int) {
	f.path = null
	f.fd = fd
}

F init(f:File, path:Path) super(f, path.path)

doc String representation of File
doc %EX - open(File("tmp/v8/LICENSE"), "r").Str().echo()  # Output: <File path=tmp/v8/LICENSE fd=4>
F Str(f:File) "<File path=${f.path} fd=${f.fd}>"

TEST File('xy').Str() == '<File path=xy fd=null>'

doc Open a file and set the "fd" field to the file descriptor. Uses OPEN(2).
doc Throws InvalidArgument if file is already open.
doc Throws FileIOFail if an underlying error occurs.
doc flags - Currently "r", "w" or "a" for read/write/append
doc %RET - f
F open(f:File, flags:Str) {
	f.fd is not Null throws InvalidArgument("open(f:File, flags:Str): file is already open").set('file', f)
	fd = c_open(f.path, flags)
	fd <= 0 throws FileIOFail("Failed to open the file ${f.path}").set('file', f)
	f.fd = fd
	f
}

# XXX: might not be correct on all platforms
TEST open(File("/etc/passwd"), "r").fd > 0

doc Get basename of the file. Uses BASENAME(1).
F basename(p:Path) p.path.basename()

doc Get basename of the file. Uses BASENAME(1).
F basename(s:Str) `line: basename $s`


# TODO: something more efficient than reading all of it. Some kind of streaming.
doc Iterate over lines of the file
doc f - Closed File
doc cb - function to call with successive lines from the file
F lines(f:File, cb:Fun) {
	f.open('r')
	finally()
		body => {
			f.fd.read().lines(cb)
		}
		cleanup => {
			f.close()
		}
}

# XXX: might not be correct on all platforms
TEST ok = false; File("/etc/passwd").lines({if ":" in A ok = true}); ok

doc Get all lines of the file
doc %RET - Arr of Str
F lines(f:File) collector f.lines(collect)

doc Write given lines to the file. Overwrites the file.
doc %RET - Arr of Str
F lines(f:File, lines_:Arr) {
	finally()
		body => {
			f.open('w')
			(lines_ + STDLIB_EOL).each(write(f.fd, X))
			f
		}
		cleanup => {
			f.close()
		}
}

# Note: EINTR should not be handled
doc Close a file and sets the "fd" field to null. Uses CLOSE(2).
doc Throws InvalidArgument if file is not open.
doc Throws FileIOFail if an underlying error occurs.
doc %RET - f
F close(f:File) {
	f.fd is Null throws InvalidArgument("File is not open. close() expects an open file").set('file', f)
	ret = c_close(f.fd)
	ret < 0 throws FileIOFail("Failed to close the file $f").set('file', f)
	f.fd = null
}

# Note: EINTR should not be handled
doc Close a file. Uses CLOSE(2).
doc Throws FileIOFail if an underlying error occurs.
F close(fd:Int) {
	ret = c_close(fd)
	ret < 0 throws FileIOFail("Failed to close file descriptor $fd").set('fd', fd)
	fd
}

doc read() and decode() the given file
doc %EX - fetch("1.json")  # Data structure, the parsed JSON
F fetch(filename:Str, decode_hints:Hash={}) {
	data = read(filename)
	decode(data, {'filename': filename} + decode_hints)
}

# TODO: think about protocols support, programs support (wget, curl, ...) and refactor
doc Fetch HTTP(S) file and decode() it
doc %EX - fetch('https://api.myip.com')  # Data structure, the parsed JSON
F fetch(url:Str, decode_hints:Hash={}) {
	guard url ~ /^(https?):\/\//
	decode(`curl -s $url`, {'url': url})
}

doc Read standard input and decode() it, passing "source" equals "stdin" hint.
doc %EX - fetch()  # Data structure, parsed stdin
F fetch(decode_hints:Hash={}) read(0).decode({'source': 'stdin'} + decode_hints)

doc read() and decode() the given file
doc %EX - fetch(File("1.json"))  # Data structure, the parsed JSON
F fetch(p:Path, decode_hints:Hash={}) p.path.fetch(decode_hints)

doc encode() and write() the data to the file
doc %RET - null (but subject to change)
F store(filename:Str, data, encode_hints:Hash={}) {
	write(filename, encode(data, {'filename': filename} + encode_hints))
	null
}

# --- CommandRedir ---

doc Initialize CommandRedir object. Used internally for commands syntax.
doc %AUTO - $(my_prog >my_file)
F init(r:CommandRedir, fd, marker, datum) {
	guard marker is Str or marker is Null
	guard datum is Str or datum is Pipe or datum == true or datum is Int
	init(args())
}

doc Convert Redit to human-readable string.
doc %RET - Str
F Str(r:CommandRedir) "<${r.typeof().name} ${r.fd} ${r.marker} ${r.datum}>"

# --- Process ---

{
	doc Running or finished process
	type Process

	doc Occurs when executable was not found in path or when executable was absolute or relative and was not found.
	type ExecutableNotFound(Exception)
}

doc Get process "stdout"
doc field - "stdout"
doc %RET - Str
F '.'(p:Process, field:Str) {
	guard field == 'stdout'
	p.outputs[1]
}

doc Set process "stdout"
doc field - "stdout"
doc %RET - Unspecified, do not count on this value
F '.='(p:Process, field:Str, v) {
	guard field == 'stdout'
	p.outputs[1] = v
}

doc Get process "stderr"
doc field - "stderr"
doc %RET - Str
F '.'(p:Process, field:Str) {
	guard field == 'stderr'
	p.outputs[2]
}

doc Set process "stderr"
doc field - "stderr"
doc %RET - Unspecified, do not count on this value
F '.='(p:Process, field:Str, v) {
	guard field == 'stderr'
	p.outputs[2] = v
}

ns {

	global finished_ok

	_finished_ok_exit_codes = {}

	doc Decide whether process finished normally: exit code must be 0.
	doc Note that processes terminated by a signal will have .exit_code null.
	doc p - any process
	doc %RET - bool
	F finished_ok(p:Process) {
		debug("finished_ok", "finished_ok() - default method")
		p.exit_code == 0
	}

	doc Decide whether a process finished normally: OK for any process that has "nofail:" option
	doc %EX - $(nofail: ls no-such-file)
	doc %STATUS - deprecated
	F finished_ok(p:Process) {
		guard p.command.options.get('nofail')
		debug("finished_ok", "finished_ok() - nofail method")
		warn("Using deprecated nofail: option, use ok: option instead (when running ${p.command.argv})")
		true
	}

	doc %STATUS - internal
	doc Decide whether a process finished normally.
	doc %EX - $(ok:0..10 ls no-such-file)
	F finished_ok(p:Process, field_name:Str, ok:NumRange) p.(field_name) in ok

	doc %STATUS - internal
	doc Decide whether a process finished normally.
	doc %EX - $(ok:[0,1,2] ls no-such-file)
	F finished_ok(p:Process, field_name:Str, ok:Arr) {
		len(ok) == 1 and ok[0] is NumRange throws InvalidArgument("finished_ok() got [some..range] but should be some..range")
		p.(field_name) in ok
	}

	doc %STATUS - internal
	doc Decide whether a process finished normally.
	doc %EX - $(ok:1 ls no-such-file)  # No exception
	doc %EX - $(ok:10 ls no-such-file) # ProcessFail exception
	F finished_ok(p:Process, field_name:Str, ok:Int) p.(field_name) == ok

	doc %STATUS - internal
	doc Decide whether a process finished normally.
	doc %EX - # 'ok' option is set to true when the value is missing after ':'
	doc %EX - $(ok: ls no-such-file)
	F finished_ok(p:Process, field_name:Str, ok:Bool) ok

	doc %STATUS - internal
	doc Decide whether a process with 'ok' option finished normally.
	doc %EX - $(ok:0..10 ls no-such-file)
	doc %EX - $(ok:[0,1,2] ls no-such-file)
	doc %EX - $(ok:1 ls no-such-file)  # No exception
	doc %EX - $(ok:10 ls no-such-file) # ProcessFail exception
	doc %EX - $(ok: ls no-such-file)
	F finished_ok(p:Process) {
		ok = p.command.options.get('ok')
		guard ok is not Null
		debug("finished_ok", "finished_ok(Process) method, 'ok:' option")
		finished_ok(p, 'exit_code', ok)
	}

	TEST try $(ok:2 cat NO_SUCH_FILE 2>/dev/null) catch(pf:ProcessFail) true
	TEST $(ok:1 cat NO_SUCH_FILE 2>/dev/null); true
	TEST $(ok:[1,10] cat NO_SUCH_FILE 2>/dev/null); true
	TEST $(ok:1..2 cat NO_SUCH_FILE 2>/dev/null); true

	doc Decide whether a process with 'ok_sig' option finished normally.
	doc %EX - p=$(sleep 10 &); p.kill(); p.wait()  # ProcessFail exception in wait()
	doc %EX - p=$(ok_sig:SIGNALS.TERM sleep 10 &); p.kill(); p.wait()  # No exception
	F finished_ok(p:Process) {
		ok = p.command.options.get('ok_sig')
		guard ok is not Null
		debug("finished_ok", "finished_ok(Process) method, 'ok_sig:' option")
		finished_ok(p, 'exit_signal', ok)
	}

	TEST p=$(sleep 10 &); p.kill(); try p.wait() catch(pf:ProcessFail) true
	TEST p=$(ok_sig:SIGNALS.TERM sleep 10 &); p.kill(); p.wait(); true

	doc Decide whether a process finished normally for known programs
	doc that return also non-zero exit codes which do not signal a failure.
	doc %EX - $(test -f my_file_that_might_be_present)
	doc %EX - $(fuser my_file)  # On Linux, exit code 1 means file is not used
	F finished_ok(p:Process) {
		ok = _finished_ok_exit_codes.get(p.executable.path)
		guard ok is not Null
		debug("finished_ok", "finished_ok(Process) method, _finished_ok checker method")
		finished_ok(p, 'exit_code', ok)
	}

	doc %STATUS - experimental
	F finished_ok(program_name:Str, ok) {
		_finished_ok_exit_codes[program_name] = ok
	}

	_known_programs = %{
		%[/bin/false /usr/bin/false] 1
		%[
			/bin/expr /usr/bin/expr
			/bin/grep /usr/bin/grep
			/bin/ping /usr/bin/ping
			/bin/test /usr/bin/test
		] %[0 1]
	}
	if OS.linux {
		_known_programs[%[/bin/fuser /usr/bin/fuser]] = %[0 1]
	}
	_known_programs.each(F(progs, ok) {
		debug("finished_ok", "known programs: ${progs} -> ${ok}")
		progs.each(finished_ok(X, ok))
	})
}

doc Process constructor. Initializes fields.
F init(p:Process, c:Command) {
	p.command = c
	p.executable = null
	p.pid = null
	p.exit_code = null
	p.exit_signal = null
	p.outputs = {1:null, 2:null}
	p.reading_threads = Threads()
	p.writing_threads = Threads()
	# p.lock = Lock()
}

# Maybe it should be pp.processes.all(Bool)? And implement Bool(p:Process)
doc Wait for all process to finish and see whether all exit codes are 0
doc %RET - Bool
doc %EX - if $(test -f myfile) ... # if runs Bool() on any non-Bool condition expression
F Bool(pp:ProcessesPipeline) pp.wait().processes.all({A.exit_code == 0})

doc Wait for a process. Waits for reading and writing threads to finish.
doc Waits for the process to finish. Checks whether to throw ProcessFail using finished_ok().
doc %RET - p
F wait(p:Process) {

	# TODO: reading/writing threads failure - throw at the end (allowing resources cleanup in this function)
	p.pid is Null throws InvalidArgument("Can not wait() on Process without PID")

	p.exit_code is Int returns p

	F join_threads(which:Str) {
		threads = p.(which)
		results = threads.join()
		p.(which) = []
		first_failure = results.first(Failure, null)
		first_failure throws ProcessFail('Error in reading/writing thread').set(process=p, cause=first_failure)
	}

	debug("process", "[wait] joining reading and writing threads")
	%[reading_threads writing_threads].each(join_threads)


	debug("process", "[wait] will waitpid(${p.pid})")
	w = c_waitpid(p.pid)
	debug("process", "[wait] waitpid(${p.pid}) -> ${w}")
	p.exit_code = C_WEXITSTATUS(w[1])
	p.exit_signal = C_WTERMSIG(w[1])
	finished_ok(p) returns p
	message = collector/Lines() {
		argv0 = ("'" + try p.command.argv[0] + "'") tor '(with unknown name)'
		collect("Executing external process ${argv0} failed")
		collect("Command: ${p.command.argv.map(escape_bash).join(' ') tor '(unavailable)'}")
		if p.exit_code is not Null {
			collect("Command exited with code: ${p.exit_code}")
		}
		if p.exit_signal is not Null {
			collect("Command exited with signal: ${p.exit_signal}")
		}
	}
	throw ProcessFail(p).set('message', message)
}

doc Wait for all processes to finish.
F wait(pp:ProcessesPipeline) {
	pp.processes.each(wait)
	pp
}

doc Convert Process to exit code. Waits for the process to finish and uses its exit code.
doc To be used for NGS process exit such as in "ngs -e 'my_code(); $(ls)'".
F ExitCode(p:Process) {
	ec = p.wait().exit_code
	ec is Int returns ec

	# http://tldp.org/LDP/abs/html/exitcodes.html
	es = p.exit_signal
	# echo("ES $es")
	es is Int returns 128 + es

	# Don't know what to do
	# error("Failed to convert process to exit code")
	240
}

doc Convert ProcessesPipeline to exit code. Waits for the processes to finish.
doc Returns first non-zero exit code. Returns zero if all exit codes are zero.
F ExitCode(pp:ProcessesPipeline) pp.wait().processes.map(ExitCode).first(X != 0, 0)

doc Wait for the process to finish and return its standard output.
doc %RET - Str
F Str(p:Process) p.wait().stdout

doc Wait for the processes to finish and return standard output of the last process in pipeline.
doc %RET - Str
F Str(pp:ProcessesPipeline) {
	pp.wait()
	assert(pp.processes)
	Str(pp.processes[-1])
}

# TODO: type Arg(Str) -- currently, inheriting built in types is not supported

doc Convert to string, appropriate for using as argument to external process.
doc %AUTO - $(mycommand $num) # num is Real
F Arg(x:Real) Str(x)

doc Convert to string, appropriate for using as argument to external process.
doc %AUTO - $(mycommand $num) # num is Int
F Arg(x:Int) Str(x)

doc Convert to string, appropriate for using as argument to external process. No-op for Str: return the same string.
doc %AUTO - $(mycommand $str) # str is Str
F Arg(x:Str) x

# TODO: Consider storing original h in one of the attrs() of the result
doc Convert a Hash, describing command line arguments, to array of strings, appropriate for using as argument to external process.
doc Key-value pairs with values of type NoData (null, EmptyBox) are discarded.
doc Key-value pairs with empty array values are discarded.
doc Values of type Box are unboxed.
doc For keys which are arrays of two elements, Bool value selects first (for true) or second (for false) element.
doc For keys which are arrays of a single element, Bool value selects whether the key is present or absent in the output.
doc For keys which are arrays of a single element, Eachable1 value causes the switch to br repeated for each element, building switch name and switch value pairs.
doc %EX - # Typical usage:
doc %EX - argv = Argv({'name1': value1, 'name2': value2, ...})
doc %EX - $(my_command $*argv)
doc %EX - # Handling of key-value pairs
doc %EX - Argv({"--a": 1, "-b": null})                         # ['--a', 1]
doc %EX - Argv({["-y1", "-n1"]: true, ["-y2", "-n2"]: false})  # ['-y1', '-n2']
doc %EX - Argv({["-y3"]: true, ["-y4"]: false})                # ["-y3"]
doc %EX - Argv({["--repeat"]: ["a", "b"]})                     # ["--repeat", "a", "--repeat", "b"]
doc %EX - Argv({"-a1": [], "-a2": [1,2,3]})                    # ["-a2", 1, 2, 3]
F Argv(h:Hash) {
	collector
		h.rejectv(NoData).mapv(only(Box, get)).each(F(k, v) {
			if k is Arr {
				ematch v {
					Bool {
						# ['--might-be-flag']: my_bool_expr
						# ['--flag-if-yes', '--flag-if-no']: my_bool_expr
						k.len() not in 1...2 throws InvalidArgument("Argv key which is array must be of length 1 or 2").set('value', k)
						# v == true -> use index 0, v == false -> use index 1
						k.Box(Int(not(v))).map(collect)
						return
					}
					Eachable1 {
						# ['--repeat']: my_eachable1
						v.each(F(elt) {
							collect(k[0])
							collect(elt)
						})
						return
					}
				}
			}

			# If you have nothing to give to the switch, skip the switch
			v == [] returns

			collect(k)
			# Convert non-arrays to FullBox so each() could be used on scalars
			only(X is not Arr, FullBox)(v).each(collect)
		})
}

TEST Argv({"--a": 1, "-b": null, ["-y1", "-n1"]: true, ["-y2", "-n2"]: false, ["-y3"]: true, ["-y4"]: false}) == ["--a", 1, "-y1", "-n2", "-y3"]
TEST Argv({"-a1": [], "-a2": [1,2,3]}) == ["-a2", 1, 2, 3]
TEST Argv({["--repeat"]: ["a", "b"]}) == ["--repeat", "a", "--repeat", "b"]

doc EXPERIMENTAL! Do not use!
F Argv(a:Arr) {
	a.reject(NoData).map(only(Box, get)).map(only(X is not Arr, FullBox)).flatten()
}

# --- $() ---

doc Run a process
F '$()'(p:Process) {

	argv = p.command.argv.map(Arg)

	debug("process", "Parsed command: ${argv}")

	if p.command.options.get('log') == true {
		log("Running command: ${argv.map(escape_bash).join(' ')}")
	}

	try {
		p.executable = find_in_path(argv[0])
	} catch(nf:ExecutableNotFound) {
		throw ProcessFail(p).set('cause', nf).set('message', 'Executable not found')
	}

	pid = c_fork()

	pid == -1 throws ProcessFail("Could not spawn a process").set('cause', CException("Failed to fork()"))

	debug("process", "PID after fork: $pid")

	pipes = p.redirects.filter({'datum': Pipe})
	debug("process2", "PIPES FROM REDIRECTS $pipes REDIRECTS ${p.redirects} COMMND ${p.Hash()}")
	child_fds = pipes.datum.map(child_fd)

	if pid == 0 {
		# === Child ===
		# TODO: See https://stackoverflow.com/questions/13101690/c-get-all-open-file-descriptors
		child_fds_to_keep_open = child_fds + p.redirects.datum.filter(Int)
		debug("process2", "CHILD CLOSING FDS 3 TO 100 EXCEPT FOR ${child_fds_to_keep_open}")
		for(i=3;i<100;i+=1) {
			if i not in child_fds_to_keep_open {
				# XXX child to parent also closed here
				# close() throws exception on invalid descriptors, hence c_close()
				i.c_close()
			}
		}

		marker_to_open_flags = {'<': 'r', '>': 'w', '>>': 'a'}
		marker_to_default_fd = {'<': 0, '>': 1, '>>': 1}

		p.redirects.each(F(r:ProcessRedir) {
			if r.datum is not Pipe {
				target_fd = r.fd.Box().get(marker_to_default_fd[r.marker])
			}
			ematch r.datum {
				Str {
					debug("process2", "CHILD FILE REDIRECT ${target_fd} -> ${r.datum}")
					f = File(r.datum).open(marker_to_open_flags[r.marker])
					dup2(f.fd, target_fd)
				}
				Pipe {
					debug("process2", "CHILD REDIRECT PIPE ${r.fd} -> ${child_fd(r.datum)}")
					dup2(child_fd(r.datum), r.fd)
					close(child_fd(r.datum)) # Is this needed?
				}
				Int {
					debug("process2", "CHILD DESCRIPTOR REDIRECT ${r.fd} -> ${r.datum}")
					dup2(r.datum, target_fd)
				}
			}
		})

		p.command.options.Box('cd').each(chdir)

		debug("process", "will execve()")
		result = c_execve(p.executable.path, argv, ENV.Strs())
		# TODO: propagate this error to parent, don't know how yet
		error("Process ${c_getpid()} (fork child) failed to execve()")
		c_exit(250)
	}

	if pid > 0 {
		# === Parent ===
		p.pid = pid
		child_fds.each(close)
		debug("process", "Reading all output of the child process")
		# XXX: maybe make it chunk based with c_poll() and single thread
		# TODO: some error handling inside these threads and after joining them
		p.reading_threads = p.redirects.filter({'datum': CollectingPipeFromChildToParentProcess}).map(F(r:ProcessRedir) {
			Thread("process-${p.pid}-output-fd-${r.fd}-reader", {
				Result({
					debug("process2", "READING ${r.datum}")
					p.outputs[r.fd] = r.datum.read()
					debug("process2", "READ <<${p.outputs[r.fd].limit(100, '...').SafeStr()}>>")
					debug("process2", "DATUM *** ${r.datum}")
					r.datum.close_reading_end()
					debug("process2", "CLOSED READING END OF PIPE, REDIRECT ${r}")
					debug("process", "Read all output of the child process for descriptor ${r.fd}, closing reading/parent end")
					null
				})
			})
		}).Threads()
	}

	debug("process2", "\$() returns process ${p.Hash()}")
	p
}

# TODO: Free (close) fds on failure
# TODO: better exceptions (use correct type, not string)
# TODO: c_waitpid() - handle signals
# TODO: split to methods for easy behaviour modification
# TODO: capture stderr
# TODO: provide additional communication channel on additional fd?
# TODO: handle built-in commands: do not execve,
# INFO: bash - redir.c
doc Run external processes described by the commands pipeline.
doc Waits for the commands to finish unless "&" is specified.
doc c - CommandsPipeline object, typically constructed by NGS when parsing the contents of $(...) .
doc %EX - if $(test -f /myfile) { ... }
doc %EX - # or
doc %EX - p = $(node main.js serve &)
doc %EX - YOUR_TESTS_OF_NODE_SERVER_HERE
doc %EX - p.kill()
doc %RET - Process
doc %AUTO - $(my_prog) , $(some | programs)
F '$()'(cp:CommandsPipeline) {

	if cp.commands.len() == 1 {

		# Special case: $($cmd)
		c = cp.commands[0]
		if (c.argv.len() == 1) and (c.argv[0] is CommandsPipeline) {
			cp = c.argv[0]
		}

		# Deprecate "top_level: cmd", should be "top_level::"
		if cp.commands[0].options.get('top_level') {
			warn("Use 'top_level::' instead of 'top_level:' in ${cp.commands[0].Str()}")
			cp.options.top_level = cp.commands[0].options.top_level
		}

	}

	# Validation - start
	for cmd in cp.commands {
		for r in cmd.redirects {
			if r.datum == true {
				r.marker != '>' throws InvalidArgument("Redirection to 'true' for collecting output can only be done with '>' redirection syntax, not '${r.marker}'").set('cp', cp)
			}
		}
	}
	# Validation - end

	pp = ProcessesPipeline(cp)
	pp.processes = cp.commands.map(F(cmd) {
		p = Process(cmd)
		p.redirects = cmd.redirects.map(ProcessRedir).each(F(r) {
			if r.datum == true {
				r.datum = CollectingPipeFromChildToParentProcess()
			}
		})
		p
	})

	# Commands:    C0    C1    C2
	# Pipes:    P0    P1    P2    P3
	# $(| ...) - uses P0
	# $(... |) - uses P3
	debug("process2", "cp.pipes.len()=${cp.pipes.len()}")
	for(i;cp.pipes.len()) {
		cp.pipes[i] is Null continues
		debug("process2", "cp.pipes[$i]")
		econd {
			i == 0 {
				debug("process2", "PIPE IN")
				pp.pipe_in = PipeToChildProcess()
				pp.processes[i].redirects.unshift(ProcessRedir(0, null, pp.pipe_in))
			}
			i == pp.processes.len() {
				debug("process2", "PIPE OUT")
				pp.pipe_out = PipeFromChildToParentProcess()
				pp.processes[i-1].redirects.unshift(ProcessRedir(1, null, pp.pipe_out))
			}
			true {
				p = Pipe()
				pp.processes[i-1].redirects.unshift(ProcessRedir(1, null, WritingPipeBetweenChildren(p)))
				pp.processes[i].redirects.unshift(ProcessRedir(0, null, ReadingPipeBetweenChildren(p)))
			}
		}
	}

	if not(cp.options.get('top_level')) and pp.pipe_out is Null {
		do_collect_output = pp.processes[-1].redirects.none(F(r) {
			# >${false} OR 1>${false}
			# 1>? OR 1<?
			(r.datum != true and r.marker == '>' and r.fd in [null, 1]) or
			r.fd == 1
		})
		if do_collect_output {
			pp.processes[-1].redirects.unshift(ProcessRedir(1, null, CollectingPipeFromChildToParentProcess()))
		}
	}

	pp.processes = pp.processes.map(('$()'))

	if not(cp.options.get('&')) and pp.pipe_in is Null and pp.pipe_out is Null {
		pp.wait()
	}

	pp
}

TEST $(true).Bool()
TEST $(false).Bool() == false
TEST "$(/bin/echo -n abc)" == 'abc'
TEST $(cd:"/" pwd).lines()[0] == '/'

doc Write to first process of ProcessesPipeline
doc %EX - p = (|cat -n | tac >/tmp/1)
doc %EX - p.write("one\n")
doc %EX - p.write("two\n")
doc %EX - p.close()
F write(pp:ProcessesPipeline, s:Str) {
	pp.pipe_in is Null throws InvalidArgument("ProcessesPipeline has no input pipe").set('pp', pp)
	pp.pipe_in.write(s)
	pp
}

doc Read from last process of ProcessesPipeline
doc %EX - p = $(seq 3 | tac |);
doc %EX - data = read(p);
doc %EX - p.close()
F read(pp:ProcessesPipeline, count=null) {
	guard count is Int or count is Null
	pp.pipe_out is Null throws InvalidArgument("ProcessesPipeline has no output pipe").set('pp', pp)
	pp.pipe_out.read(count)
}

# TODO: example
doc Close reading and writing pipes of ProcessesPipeline, if they exist
F close(pp:ProcessesPipeline) {
	pp.pipe_in.Box().map({A.parent_fd().close()})
	pp.pipe_out.Box().map({A.parent_fd().close()})
	pp
}

doc Get command standard output. Similar to bash. Does not strip trailing new line character(s)
doc `line:true my_command` will return the first line, stripping trailing new line character(s)
doc %AUTO - `my_command` , `my_command | my_other_command`
F ``(cp:CommandsPipeline) {
	processes = ('$()')(cp).processes
	assert(processes)
	ret = processes[-1].Str()
	if cp.commands[-1].options.get('line') == true {
		ret = ret.lines()[0]
	}
	if cp.commands[0..-1].options.get('line') {
		warn("Using 'line:' option on non-final command had no effect when running ${cp.commands.argv}")
	}
	ret
}

doc Get command standard output and decode() it.
doc %RET - structured data when the output can be parsed.
doc %EX - ``aws ec2 describe-instances`` is Arr  # true
doc %EX - ``aws ec2 describe-instances``.InstanceId.map(X[0..3]).join(",")  # i-3, i-9, i-8, i-a, i-7, ...
doc %AUTO - ``my_command`` , ``my_command | my_other_command``
F ````(cp:CommandsPipeline) {
	processes = ('$()')(cp).processes
	assert(processes)
	p = processes[-1]
	try {
		p.stdout.decode({'process': p, 'pipeline': cp})
	} catch(e) {
		throw ProcessFail("Failed to decode process output").set('process', p).set('cause', e)
	}
}

doc Send signal to a process. Uses KILL(2). Throws KillFail on error.
doc sig - Signal to send. Defaults to SIGNALS.TERM
doc %RET - unspecified at this time, do not count on it
F kill(pid:Int, sig:Int=SIGNALS.TERM) {
	ret = c_kill(pid, sig)
	ret == -1 throws KillFail("Failed to kill pid $pid with signal $sig")
	ret != 0 throws Error("c_kill() did not return 0 or -1")
	ret
}

# XXX: Must join reader/writer threads!
doc Send signal to a Process. Uses KILL(2).
doc Throws InvalidArgument if Process does not have "pid".
doc Throws KillFail on error.
doc sig - Signal to send. Defaults to SIGNALS.TERM
doc %RET - unspecified at this time, do not count on it
F kill(p:Process, sig:Int=SIGNALS.TERM) {
	p.pid is Null throws InvalidArgument("Can't kill() a process that does not have a pid")
	kill(p.pid, sig)
}

doc Kill all processes in the ProcessesPipeline. Throws InvalidArgument if ProcessesPipeline is not running (yet).
F kill(pp:ProcessesPipeline, sig:Int=SIGNALS.TERM) {
	pp.processes.map(kill(X, sig))
}

TEST counter = 0; p=$(sleep 5&); if p.processes[0].stdout == null counter +=1; p.kill(); try p.wait() catch(e:ProcessFail) true
TEST p=$(|cat); p.write("abc"); p.close(); p.Str() == "abc"
TEST p=$(|cat|); p.write("abc"); p.read(3) == "abc"
TEST $(echo abc | cat).Str().starts_with("abc")

doc Attempt to decode JSON. Uses decode_json().
F decode(s:Str, hints:Hash={}) {
	ret = FullBox(decode_json(s)) tor EmptyBox()
	guard ret
	ret.val
}

# TODO: handle more than one occurrence of kvsep in each line
doc EXPERIMENTAL. KVS (key-value separator) hint for decode()
doc %EX - decode('a b\nc d', {'KVS': ' '}) == {'a': 'b', 'c': 'd'}
F decode(s:Str, hints:Hash) {
	guard 'KVS' in hints
	s.lines().map(split(X, hints.KVS)).Hash()
}

TEST decode('a b\nc d', {'KVS': ' '}) == {'a': 'b', 'c': 'd'}

doc EXPERIMENTAL. FS (field separator) hint for decode()
doc %EX - decode('a b\nc d', {'FS': ' '})  # [['a', 'b'], ['c', 'd']]
F decode(s:Str, hints:Hash) {
	guard 'FS' in hints
	s.lines().map(split(X, hints.FS))
}

TEST decode('a b\nc d', {'FS': ' '}) == [['a', 'b'], ['c', 'd']]

doc EXPERIMENTAL! Do not use!
doc Handle fields_names hint - run decode() and make Arr[Hash] from Arr[Arr] using provided fields_names
doc %EX - backup_list = fetch('backup.list', {'FS': ' ', 'fields_names': %[env role]})
F decode(s:Str, hints:Hash) {
	guard 'fields_names' in hints
	decode(s, hints.without('fields_names')).map(F(row) {
		zip(hints.fields_names, row).Hash()
	})
}

doc Encode data as JSON if hints say that "filename" ends with ".json"
doc %RET - Str
F encode(data, hints:Hash={}) {
	guard hints.get('filename', '').ends_with('.json')
	encode_json(data)
}

doc Returns cp, wihout any processing. Convenient way to pass ready-to-run Command as an argument
doc %EX - F run_when_needed(cp:CommandsPipeline) { ... $(cp) ... }
doc %EX - ...
doc %EX - run_when_needed(%(ls >/tmp/my_ls))
doc %AUTO - %(my_command) , %(my_command | my_other_command)
F '%()'(cp:CommandsPipeline) cp

doc Wait for the process and return lines of its stdout.
doc %RET - Arr of Str
doc %EX - $(seq 10 2 20).lines().map(Int)  # [10,12,14,16,18,20]
F lines(p:Process) {
	p.wait()
	p.stdout.lines()
}

# TODO: ability to handle running process & its streaming stdout
doc Iterate lines of Process' stdout, calling cb with successive lines.
doc Warning: current implementation waits for the process to finish, accumulates all its stdout, and only then starts calling cb for each line.
F lines(p:Process, cb:Fun) {
	p.wait()
	p.stdout.lines(cb)
}

doc Wait for cp and return lines of stdout of the last process.
doc %RET - Arr of Str
doc %EX - $(seq 3 | tac).lines().map(Int)  # [3,2,1]
F lines(pp:ProcessesPipeline) {
	pp.wait()
	pp.processes[-1].stdout.lines()
}

doc Wait for pp and return call cb for each line of stdout of last process.
doc Warning: current implementation waits for the processes to finish, accumulates all stdout of the last process, and only then starts calling cb for each line.
doc %RET - Arr of Str
F lines(pp:ProcessesPipeline, cb:Fun) {
	pp.wait()
	pp.processes[-1].stdout.lines(cb)
}

# XXX: might not be correct on all platforms
TEST ok = false; $(cat /etc/passwd).lines({if ":" in A ok = true}); ok

# === Parse aws output ===========================
# TODO: move to separate auto-loaded file.

doc Do not use directly. Subject to change.
doc Convert "Tags" array in each element of AWS resources (typically returned by AWS CLI) into Hash.
doc Makes "Tags" much more usable.
F stdlib_aws_straighten_tags(a:Arr) a.each(stdlib_aws_straighten_tags)

doc Do not use directly. Subject to change.
doc Convert "Tags" array in the given AWS resource (typically returned by AWS CLI) into Hash.
doc %EX - t = {"Tags": [{"Key": "k", "Value": "v"},{"Key": "k2", "Value": "v2"}]}  # Not very convenient, is it?
doc %EX - t.stdlib_aws_straighten_tags()
doc %EX - t  # {Tags={k=v, k2=v2}}
F stdlib_aws_straighten_tags(h:Hash) {
	if 'Tags' in h {
		h.Tags = Hash(h.Tags.Key, h.Tags.Value)
	}
}

# For the case of { "SecurityGroups": [ "sg-XXXXXXXX" ] }
# Which is output of aws elb apply-security-groups-to-load-balancer --load-balancer-name SOMETHING -beame-servers-authz --security-groups sg-XXXXXXXX
doc Do not use directly. Subject to change.
doc A no-op
F stdlib_aws_straighten_tags(s:Str) null

TEST instances = [{"Tags": [{"Key": "k", "Value": "v"},{"Key": "k2", "Value": "v2"}]}]; stdlib_aws_straighten_tags(instances); instances.Tags == [{"k": "v", "k2": "v2"}]
TEST instances = ["something"]; stdlib_aws_straighten_tags(instances); instances == ["something"]

doc Parse the output of "aws" command. Extracts the array (see "s" below"). For "describe-instances", flattens the instance list.
doc s - Str containing JSON with a Hash at top level with exactly one Arr as value
doc hints - hints.process.command.argv[0] must be 'aws'
doc %RET - data structure, tyically an Arr at top level. If s is empty string - null.
F decode(s:Str, hints:Hash) {
	guard (try hints.process.command.argv[0] == 'aws') or (try hints.process.command.options.decode == 'aws')

	if s == '' {
		# cloudfront empty list
		if hints.process.command.argv.get(1, null) == 'cloudfront' and hints.process.command.argv.get(2, null) ~ /^list/ {
			return []
		}
		# aws ec2 create-tags/delete-tags
		return null
	}

	data = decode_json(s)
	guard data is Hash

	if hints.process.command.argv.get(1, null) == 'cloudfront' {
		# TODO: eliminate stupid 'Quantity' field.
		# Can not convert {'Quantity': ..., 'Items': [ iii ]} to just [ iii ]
		# because _some_ (of course, AWS) Hashes contain additional keys:
		# TrustedSigners: [Enabled]
		# AllowedMethods: [CachedMethods]
		# GeoRestriction: [RestrictionType]
	}

	# CloudFront
	# aws cloudfront list-invalidations --distribution-id --> { "InvalidationList": { "Items": [ ... ] } }

	if (len(data) == 1) and (data.values()[0] is Hash) and (data.values()[0].len() == 1) {
		candidate = data.values()[0].values().the_one()
		candidate is Arr returns candidate
	}

	if 'DistributionList' in data {
		guard data.DistributionList.len() == 1
		return data.DistributionList.Items
	}

	# Use the only top-level key that has array as it's value
	# Thanks goes to Elastic Beanstalk which complicates this,
	# all other APIs seem to return only one top-level key.
	# ( aws elasticbeanstalk describe-configuration-options )

	top_level_vals = data.values().filter(Arr)

	guard top_level_vals.len() == 1

	data = top_level_vals[0]

	# Anyone cares about Reservations? Certainly it's not the common case so...
	if data.all('ReservationId' in X) {
		# Put reservation data into ._Reservation field of each instance, just in case
		data.each(F(reservation) {
			reservation.Instances._Reservation = reservation.without('Instances')
		})
		data = data.Instances.flatten()
	}
	data.stdlib_aws_straighten_tags()
}

doc Parse the output of "find" command which does not use "-printf". Handles "-print0".
doc hints - hints.process.command.argv[0] must be 'find'
doc %RET - Arr of Str
F decode(s:Str, hints:Hash) {
	guard try hints['process'].command.argv[0] == 'find'
	argv = hints['process'].command.argv
	guard '-printf' not in argv
	zero_sep = '-print0' in argv
	if zero_sep then s.split(chr(0))[0..-1] else s.lines()
}

doc Parse the output of "locate" command.
doc hints - hints.process.command.argv[0] must be 'locate'
doc %RET - Arr of Str
F decode(s:Str, hints:Hash) {
	guard try hints['process'].command.argv[0] == 'locate'
	# .map(Path) ?
	s.lines()
}

# === config =====================================

STDLIB_CONFIG = {}

doc Get configuration for the given key. Lookup order / first wins: (1) Environment variable NGS_$k (2) previously set config(k, v)
doc k - Configuration key
doc %RET - Any. If data found in environment variable, it will be decode()d or returned as Str if decode() fails.
doc %EX - conf = config("table_${t.name}")
F config(k:Str) {
	# TODO: think, organize
	#       what about structured data? JSON?
	# TODO: read from config files
	# TODO: read from command line switches
	debug("config", "Getting key '$k'")
	v = try ENV["NGS_$k"]
	if v {
		debug("config", "'$k' found in the environment variable 'NGS_${k}': '$v'")
		return decode(v) tor v
	}
	v = try STDLIB_CONFIG[k]
	if v is not Null {
		debug("config", "'$k' found in STDLIB_CONFIG: $v")
		return v
	}
	debug("config", "'$k' was not found")
	v
}

doc Set configuration. To be used with config(k:Str).
doc %EX - config('table_Instances', %[InstanceId tag_Name tag_env tag_role IPs InstanceType State KeyName SecurityGroups AZ RestOfTags])
F config(k:Str, v) {
	debug("config", "Setting ${k}=${v}")
	STDLIB_CONFIG[k] = v
}

# === MatchResult, Pfx, Sfx ============================

{
	doc Successful or unsuccessful match result
	type MatchResult

		doc Successful match result
		doc matches - Successful matches
		type MatchSuccess([MatchResult, Success])

		doc Unsucessfull match result
		type MatchFailure([MatchResult, Failure])

	type SubSeq
		doc Prefix subsequence of a sequence
		type Pfx(SubSeq)
			doc Prefix that might or might not be present for (-) to succeed
			type MaybePfx(Pfx)
			doc Prefix that must be present for ~ matching to succeed
			type MustPfx(Pfx)
		doc Infix subsequence of a sequence
		type Ifx(SubSeq)
			doc Infix that might or might not be present for (-) to succeed
			type MaybeIfx(Ifx)
			doc Infix that must be present for ~ matching to succeed
			type MustIfx(Ifx)
		doc Suffix subsequence of a sequence
		type Sfx(SubSeq)
			doc Suffix that might or might not be present for (-) to succeed
			type MaybeSfx(Sfx)
			doc Suffix that must be present for ~ matching to succeed
			type MustSfx(Sfx)
}

doc Successful match constructor
F init(ms:MatchSuccess, matches:Arr) init(args())


doc Unsuccessful construtcor
F init(mf:MatchFailure, data, pattern) init(args())

doc Convert successful match to Bool (true)
doc %RET - true
F Bool(ms:MatchSuccess) true

doc Convert failed match to Bool (false)
doc %RET - false
F Bool(mf:MatchFailure) false

doc Get the values of successfull match
F get(ms:MatchSuccess) ms

doc Throws ResultFail
F get(mf:MatchFailure) throw ResultFail("There was no match").set('failure', mf)

doc Convert Success to FullBox
doc %RET - FullBox
doc %EX - Box("abcd" ~ /^(..)/).map({"First two letters: ${A[1]}"}).get("(too short)")  # First two letters: ab
F Box(s:Success) FullBox(ms)

doc Convert failure to EmptyBox
doc %RET - EmptyBox
doc %EX - Box("a" ~ /^(..)/).map({"First two letters: ${A[1]}"}).get("(too short)")  # (too short)
F Box(f:Failure) EmptyBox()

doc EXPERIMENTAL! Do not use!
F attempt(x, *cbs) {
	guard cbs.all(Fun)
	r = Return()
	cbs.each(F(cb) {
		t = cb(x)
		t throws r(t.get())
	})
	throw Error("attempt() failed").set('x', x).set('cbs', cbs)
}

doc SubSec construcor
F init(s:SubSeq, val) s.val = val

# The common case
doc Convenience method for creating MustPfx
doc %RET - MustPfx
F Pfx(val) MustPfx(val)

doc Convenience method for creating MustIfx
doc %RET - MustIfx
F Ifx(val) MustIfx(val)

doc Convenience method for creating MustSfx
doc %RET - MustSfx
F Sfx(val) MustSfx(val)

F Str(s:SubSeq) "<${s.typeof().name} ${s.val}>"

doc Return string without the prefix. Throws InvalidArgument if pfx is MustPfx but s does not start with it.
doc s - original string
doc pfx - prefix to get rid of
doc %RET - s without pfx
doc %EX - "abcde" - Pfx("ab")  # "cde"
doc %EX - "abcde" - Pfx("xy")  # InvalidArgument exception
doc %EX - "abcde" - MaybePfx("xy")  # "abcde"
F -(s:Str, pfx:Pfx) {
	s.starts_with(pfx.val) returns s[pfx.val.len()..null]
	pfx is MustPfx throws InvalidArgument("Given string '$s' does not start with prefix '${pfx.val}'").set('s', s).set('pfx', pfx)
	s
}

TEST "abc" - Pfx("a") == "bc"
TEST try "abc" - Pfx("wa") catch(mf:InvalidArgument) true
TEST "abc" - MaybePfx("wa") == "abc"


doc Return string without the suffix. Throws InvalidArgument if pfx is MustSfx but s does not end with it.
doc s - original string
doc sfx - suffix to get rid of
doc %RET - s without pfx
doc %EX - "abcde" - Sfx("de")  # "abc"
doc %EX - "abcde" - Sfx("xy")  # InvalidArgument exception
doc %EX - "abcde" - MaybeSfx("xy")  # "abcde"
F -(s:Str, sfx:Sfx) {
	s.ends_with(sfx.val) returns s[0 .. (s.len() - sfx.val.len())]
	sfx is MustSfx throws InvalidArgument("Given string '$s' does not end with suffix '${sfx.val}'").set('s', s).set('sfx', sfx)
	s
}

TEST "abc" - Sfx("c") == "ab"
TEST try "abc" - Sfx("cd") catch(mf:InvalidArgument) true
TEST "abc" - MaybeSfx("cd") == "abc"

doc Return string without the infix. Throws InvalidArgument if ifx is MustIfx but s does not contain it.
doc s - original string
doc ifx - infix to get rid of
doc %RET - s without ifx
doc %EX - "abcde" - Ifx("bc")  # "ade"
doc %EX - "abcde" - Ifx("xy")  # InvalidArgument exception
doc %EX - "abcde" - MaybeIfx("xy")  # "abcde"
F -(s:Str, ifx:Ifx) {
	p = s.pos(ifx.val)
	p is not Null returns s[0 .. p] + s[(p + ifx.val.len()) .. s.len()]
	ifx is MustIfx throws InvalidArgument("Given string '$s' does not contain infix '${ifx.val}'").set('s', s).set('ifx', ifx)
	s
}

TEST "abcde" - Ifx("bc") == "ade"
TEST try "abcde" - Ifx("xy") catch(mf:InvalidArgument) true
TEST "abcde" - MaybeIfx("xy") == "abcde"

doc Check whether s starts with pfx.
doc %EX - "abcde" ~ Pfx("ab")  # <MatchSuccess matches=['ab'] before= after=cde>
doc %EX - "abcde" ~ Pfx("xy")  # <MatchFailure >
doc %RET - MatchResult
F ~(s:Str, pfx:Pfx) {
	not(s.starts_with(pfx.val)) returns MatchFailure()
	ret = MatchSuccess([pfx.val])
	ret.before = ''
	ret.after = s[pfx.val.len()..null]
	ret
}

doc Check whether s contains i. Same as s ~ i.val
doc %RET - MatchResult
F ~(s:Str, i:Ifx) s ~ i.val

doc Check whether s ends with sfx.
doc %EX - "abcde" ~ Sfx("de")  # <MatchSuccess matches=['de'] before=abc after=>
doc %EX - "abcde" ~ Pfx("xy")  # <MatchFailure >
doc %RET - MatchResult
F ~(s:Str, sfx:Sfx) {
	not(s.ends_with(sfx.val)) returns MatchFailure()
	ret = MatchSuccess([sfx.val])
	ret.before = s[0..(s.len() - sfx.val.len())]
	ret.after = ''
	ret
}

# TODO: make it a low priority method implementation
doc Convenience method to access matches in MatchSuccess
doc %EX - ("abc" ~ /a(.)c/)[1]  # "b"
F '[]'(ms:MatchSuccess, idx:Int) ms.matches[idx]

TEST ("abc" ~ /a(.)c/)[1] == "b"

F Pred(s:SubSeq) F subseq_pred(x) x ~ s


# === RegExp =====================================

# TODO: better exceptions
doc Find PCRE regular expression in s. Empty string without options returns MatchFailure. Throws Error if more than 20 captures are used or if there is an error during matching.
doc offset - search start offset
doc options - options to pass to underlying PCRE_EXEC(3).
doc %RET - MatchResult
doc %EX - globals().keys().filter(/^C_PCRE/)  # lists possible options
doc %EX - "xabcy" ~ /a(.)c/  # <MatchSuccess matches=['abc','b'] named={} positions=[[1,4],[2,3]] whole=abc before=x after=y>
doc %EX - m = ("xabcy" ~ /a(?P<mychar>.)c/)
doc %EX - echo(m.named.mychar)  # Outputs: b
doc %AUTO - my_str ~ my_regexp
F ~(s:Str, r:RegExp, offset:Int=0, options:Int=0) {
	result = c_pcre_exec(r, s, offset, options)
	if result is Int {
		result == C_PCRE_ERROR_NOMATCH returns MatchFailure()
		result == 0 throws Error("Too many captures. Max 20")
		result < 0 throws Error("RegExp matching error in c_pcre_exec").set('code', result)
		assert(false, "Unexpected integer result from c_pcre_exec")
	}
	assert(result is Arr, "c_pcre_exec must return either integer or an array")
	ret = MatchSuccess(
		result.map(2, F(start_pos, end_pos) {
			if start_pos >= 0
				s[start_pos..end_pos]
			else
				null
		})
	)
	ret.named = r.names.mapv(F(capture_num) try ret.matches[capture_num])
	ret.positions = result.map(2, F(start_pos, end_pos) [start_pos, end_pos])
	ret.whole = ret.matches[0]
	ret.before = s[0..result[0]]
	ret.after = s[result[1]..null]
	ret
}

TEST m = "xabcy" ~ /a(.)c/; m.matches == ["abc", "b"] and m.before == 'x' and m.after == 'y' and m.whole == 'abc'
TEST m = "xAbcy" ~ /a(.)c/; m is MatchFailure

PCRE_NEWLINE_TO_OPTIONS = {
	         13: C_PCRE_NEWLINE_CR,
	         10: C_PCRE_NEWLINE_LF,
	13*256 + 10: C_PCRE_NEWLINE_CRLF,
	         -2: C_PCRE_NEWLINE_ANYCRLF,
	         -1: C_PCRE_NEWLINE_ANY,
}

doc Find all non-overlapping matches of regular expression in a string.
doc %RET - if collect_unmatched - Arr with each element being MatchSuccess or Str, if not collect_unmatched - Arr of MatchSuccess
doc %EX - ("x10ab20c30y" ~~ /[0-9]+/).whole.map(Int).sum()  # 60
doc %EX -
doc %EX - arr = (~~)("x10ab20c30y", /[0-9]+/, true)
doc %EX - arr .= map(F(elt) if elt is MatchSuccess "[${elt.whole}]" else elt)
doc %EX - arr.join("")  # "x[10]ab[20]c[30]y"
F ~~(s:Str, r:RegExp, collect_unmatched:Bool=false) {
	collector {
		m = (~)(s, r, 0)
		if not(m) {
			if collect_unmatched collect(s)
			return null
		}
		start_offset = m.positions[0][0]
		next_offset = m.positions[0][1]
		if collect_unmatched and start_offset then collect(s[0..start_offset])
		collect(m)
		option_bits = r.options
		utf8 = option_bits.band(C_PCRE_UTF8).Bool()
		option_bits = option_bits.band([C_PCRE_NEWLINE_CR, C_PCRE_NEWLINE_LF, C_PCRE_NEWLINE_CRLF, C_PCRE_NEWLINE_ANY, C_PCRE_NEWLINE_ANYCRLF].reduce(0, bor))
		option_bits = option_bits or PCRE_NEWLINE_TO_OPTIONS.get(PCRE_NEWLINE, 0)
		crlf_is_newline = option_bits in [C_PCRE_NEWLINE_ANY, C_PCRE_NEWLINE_CRLF, C_PCRE_NEWLINE_ANYCRLF]
		while true {
			options = 0
			if start_offset == next_offset {
				next_offset == len(s) breaks
				options = bor(C_PCRE_NOTEMPTY_ATSTART, C_PCRE_ANCHORED)
			}
			m = (~)(s, r, next_offset, options)
			if m {
				if collect_unmatched {
					if next_offset != m.positions[0][0] {
						collect(s[next_offset..m.positions[0][0]])
					}
				}
				start_offset = m.positions[0][0]
				next_offset = m.positions[0][1]
				collect(m)
				continue
			}
			options == 0 breaks
			next_offset += 1
			if (crlf_is_newline) and (try s[next_offset-1..next_offset+1] == '\r\n') {
				next_offset += 1
				continue
			}
			if utf8 {
				while (next_offset < len(s)) and (s[next_offset].ord().band(0xC0) == 0x80) {
					next_offset += 1
				}
				continue
			}
		}
		if collect_unmatched and (next_offset < len(s)) {
			collect(s[next_offset..null])
		}
	}
}

# TODO: test ~~() \r\n skipping
# Crashes on Ubuntu 14.04 clang 3.5.0 (Travis CI)
TEST (try ENV.TRAVIS and ENV.CC == "clang") returns true; ("ab\r\ncd" ~~ /(*CRLF)|./m).whole.filter(len) == ['a', 'b', 'c', 'd']
# Crashes on Ubuntu 14.04 clang 3.5.0 (Travis CI)
TEST (try ENV.TRAVIS and ENV.CC == "clang") returns true; ("ab\r\ncd" ~~ /|./m).whole.filter(len) == ['a', 'b', '\r', 'c', 'd']
# UTF-8 of "я" is 209(D1), 143(8F)
# Skip for older library using try ... catch
TEST try ("aяb" ~~ /(*UTF)|\\x8F|b/).whole.filter(len) == ['b'] catch(e:RegExpCompileFail) 'not recognized' in e.message

# Last two are for repeated searches
STDLIB_REGEXP_FLAGS = {
	'i': C_PCRE_CASELESS
	'm': C_PCRE_MULTILINE
	's': C_PCRE_DOTALL
	'x': C_PCRE_EXTENDED

	'a': C_PCRE_ANCHORED
	'n': C_PCRE_NOTEMPTY_ATSTART
}

doc Regular expression constructor.
doc %AUTO - /myregex/
doc %RET - RegExp
doc %EX - my_re = /blah/
F //(regexp:Str, flags:Str) {
	# Maybe add each(Str,Fun) ?
	# TOOD: bitwise or instead of sum()
	options = flags.map(F(flag) {
		STDLIB_REGEXP_FLAGS[flag] tor throw RegExpCompileFail("Unknown flag $flag").set('regexp', regexp).set('flags', flags)
	}).sum()

	c_pcre_compile(regexp, options)
}

TEST Bool("A" ~ /a/i)

doc Returns the string with one occurrence of regexp cut out of it. Throws InvalidArgument if s does not contain r.
doc %EX - "abc01def23" - /[0-9]+/  # "abcdef23"
doc %RET - Str
F -(s:Str, r:RegExp) {
	m = s ~ r
	not(m) throws InvalidArgument('String does not contain the RegExp').set('string', s).set('regexp', r)
	s[0..m.positions[0][0]] + s[m.positions[0][1]..null]
}

TEST "abc01def23" - /[0-9]+/ == "abcdef23"

doc Split string by regexp
doc %RET - Arr of Str
doc %EX - "x10ab20c30y".split(/[0-9]+/).join(" :: ")  # "x :: ab :: c :: y"
F split(s:Str, r:RegExp) (~~)(s, r, true).filter(Str)

# Crashes on Ubuntu 14.04 clang 3.5.0 (Travis CI)
TEST (try ENV.TRAVIS and ENV.CC == "clang") returns true; "ab01de12f".split(/[0-9]+/) == ['ab', 'de', 'f']

doc Get string with all occurrences of r removed
doc %RET - Str
doc %EX - "x10ab20c30y".without(/[0-9]+/)  # "xabcy"
F without(s:Str, r:RegExp) s.split(r).join('')

TEST (try ENV.TRAVIS and ENV.CC == "clang") returns true; "ab01de12f".without(/[0-9]+/) == 'abdef'

# TODO: make it a low priority method implementation
doc Get substring of a string that corresponds to first match of given regular expression
doc %EX - "x10ab20c30y"[/[0-9]+/]  # "10"
F '[]'(s:Str, r:RegExp) {
	not((m = s ~ r)) throws InvalidArgument("String does not contain the given RegExp").set('container', s).set('regexp', r)
	m.whole
}

TEST "ab01de12f"[/[0-9]+/] == '01'

doc Convert regular expression to a predicate.
doc %RET - A function that checks whether the only argument (of type Str) matches r
doc %EX - %[w1 w2].filter(/1/)  # %[w1]
F Pred(r:RegExp) F regexp_pred(x:Str) x ~ r

TEST %[w1 w2].filter(/1/) == %[w1]

doc Replace all occurrences of r
doc mapper - Function that will be called with one matching string at a time that provides the replacement
doc %RET - Str
doc %EX - "x10ab20c30y".replace(/[0-9]+/, F(match_text) "[$match_text]")  # "x[10]ab[20]c[30]y"
F replace(s:Str, r:RegExp, mapper:Fun) {
	(~~)(s, r, true).map(F(x) {
		ematch x {
			MatchSuccess mapper(x.whole)
			Str x
		}
	}).join('')
}

TEST "x10ab20c30y".replace(/[0-9]+/, F(match_text) "[$match_text]") == "x[10]ab[20]c[30]y"

# === Fun ========================================

doc Call cb n times without any parameters and accumulate the results.
doc %EX - a = Box * 2; a[0] is Box and a[1] is Box and a[0] !== a[1]  # true
F *(cb:Fun, n:Int) n.map({ cb() })

TEST a = Box * 2; a[0] is Box and a[1] is Box and a[0] !== a[1]

# === Null =======================================

doc Convert null to NGS code that would produce null when executed.
doc %RET - Str
F code(n:Null) "null"


# === exit_hook - Print uncaught exception =======

doc Convert an array to a possibly shorter version, for displaying to human.
doc chunk_size - number of elements to retain at the beginning and at the end.
doc marker - how to mark the cut elements in the middle.
doc %RET - Arr
doc %EX - my_array = Arr(1...100)
doc %EX - digest(my_array, 2).each(echo)
doc %EX - # 1
doc %EX - # 2
doc %EX - # (...)
doc %EX - # 99
doc %EX - # 100
F digest(a:Arr, chunk_size:Int, marker:Str='(...)') {
	l = a.len()
	l < chunk_size*2 returns a
	a[0..chunk_size] + [marker] + a[(l-chunk_size)..l]
}

doc Do nothing. Catch-all for exception_specific_message().
doc %RET - EmptyBox
F exception_specific_message(e:Exception) null

doc Format GlobalNotFound exception message.
doc %RET - FullBox with Str
F exception_specific_message(gnf:GlobalNotFound) "Global variable '${gnf.name}' not found"

doc Format MethodNotFound exception message.
doc %STATUS - WIP
F exception_specific_message(mnf:MethodNotFound) {
	methods_names = mnf.callable.Arr().map(attrs).get('name')
	mn = if methods_names and methods_names.all(X == methods_names[0]) {
		methods_names[0]
	} else {
		'(method name unavailable, maybe anonymous)'
	}
	Lines([
		"The arguments did not match any of the methods' parameters."
		"MultiMethod name: ${mn}"
		"Called with arguments' types: ${mnf.args.map(typeof).name.join(', ')}"
		"Please check that you pass the right number of arguments."
		"Please check that arguments' types are matching methods' parameters."
	])
}

# TODO: show relevant value part
doc Format JsonDecodeFail exception message.
F exception_specific_message(jdf:JsonDecodeFail) {
	Lines([
		"Failed to parse JSON"
		"Error message: ${jdf.error}"
		"Error position in given JSON: ${jdf.position}"
		"(TODO: show relevant value part)"
	])
}

doc Format KeyNotFound exception message for ENV global variable.
F exception_specific_message(knf:KeyNotFound) {
	guard knf.container === ENV
	"Environment variable '${knf.key}' is not set."
}

doc Don't use, subject to change, including name
doc %STATUS - experimental
F SafeStr(val) {
	v = "$val" tor "(Failed to inspect <${val.typeof().name tor '(unknown type)'}>)"
	v.map(F(ch) {
		o = ord(ch)
		o >= 32 and ch != '\\' returns ch
		'\\x' + encode_hex(ch)
	}).join('')
}

# TODO: in-depth inspect()

doc Inspect any value.
doc %RET - Lines with exactly one line
F inspect(val) Lines([SafeStr(val)])

doc Inspect boolean.
doc %RET - Lines with exactly one line
F inspect(b:Bool) Lines(["Bool: $b"])

# F inspect(mm:MultiMethod) ["MultiMethod "] + mm.map_idx_val({"  [${SafeStr(A)}] = ${SafeStr(B)}"})
doc Inspect MultiMethod
doc %RET - Lines
F inspect(mm:MultiMethod) Lines(["MultiMethod", "  Methods"]) + ("    " + mm.Arr().inspect())

doc Inspect Real
doc %RET - Lines with exactly one line
F inspect(r:Real) Lines(["Real: $r"])

doc Inspect Int
doc %RET - Lines with exactly one line
F inspect(i:Int) Lines(["Int: $i"])

doc Inspect Str
doc %RET - Lines
F inspect(s:Str) Lines(["String(${s.len()}): ${SafeStr(s)}"])

doc Inspect Arr
doc %RET - Lines
F inspect(a:Arr) Lines(["Array of size ${a.len()}"] + a.map_idx_val({"  [${SafeStr(A)}] = ${SafeStr(B)}"}))

doc Inspect Hash
doc %RET - Lines
F inspect(h:Hash) Lines(["Hash of size ${h.len()}"] + h.map({"  [${SafeStr(A)}] = ${SafeStr(B)}"}))

doc Inspect Process
doc %RET - Lines
F inspect(p:Process) {
	# XXX: Are there any platforms with different convention?
	outputs_names = {1: 'stdout', 2: 'stderr'}
	collector/Lines() {
		collect("Process")
		collect("  command = ${p.command}")
		collect("  pid = ${p.pid}")
		collect("  exit_code = ${p.exit_code}")
		collect("  exit_signal = ${p.exit_signal}")
		p.redirects.each_idx_val(F(idx, val) {
			("  redirects[${idx}]: " + p.redirects[idx].inspect()).each(collect)
		})
		p.outputs.each(F(k, val) {
			# Replacing 'lines' with 'Lines' does not work. Gives "(Failed to inspect)".
			val_lines = val.Box().map(lines).get([])
			name = ', ' +? outputs_names.get(k, '')
			collect("  output on fd ${k}${name} (${val_lines.len()} lines):")
			("    " + val_lines.digest(16)).each(collect)
		})
	}
}

doc Inspect CommandsPipeline
doc %RET - Lines
F inspect(cp:CommandsPipeline) {
	F p(idx:Int) {
		cp.pipes[idx] is Null returns []
		("     pipe[$idx]: " + inspect(cp.pipes[idx]))
	}
	collector/Lines() {
		collect(cp.typeof().name)
		if cp.options {
			("  options: " + inspect(cp.options)) % collect
		}
		p(0) % collect
		for(i;len(cp.commands)) {
			("  command[$i]: " + inspect(cp.commands[i])) % collect
			if 'processes' in cp and cp.processes {
				("  process[$i]: " + inspect(cp.processes[i])) % collect
			}
			p(i+1) % collect
		}
	}
}

doc Inspect ProcessesPipeline
doc %RET - Lines
F inspect(pp:ProcessesPipeline) {
	collector/Lines() {
		collect(pp.typeof().name)
		%[cp pipe_in pipe_out].each(F(k) {
			("  ${k}: " + inspect(pp.(k))) % collect
		})
		for(i;len(pp.processes)) {
			("  processes[$i]: " + inspect(pp.processes[i])) % collect
		}
	}
}

doc Convert Backtrace to human-readable format
doc %EX - Lines(bt).echo()
F init(lines:Lines, backtrace:Backtrace, parent_backtrace=null) {
	guard (parent_backtrace is Null) or (parent_backtrace is Backtrace)
	super(lines)
	parent_frames = parent_backtrace.frames tor []
	backtrace.frames.each_idx_val(F(idx, frame) {
		# Don't print frames that overlap with parent exception
		frame.ip == (try parent_frames[idx].ip) returns
		l = resolve_instruction_pointer(frame.ip)
		closure = " [in ${frame.closure.attrs().name}]" tor ''
		push(lines, "Frame $idx: ${l.file}:${l.first_line}:${l.first_column} - ${l.last_line}:${l.last_column}$closure")
	})
}

doc Print exception to stderr. Uses inspect().
doc level - indentation level to use (two spaces for each level)
doc parent - parent exception if print_exception() was called for .cause exception
F print_exception(e:Exception, level:Int = 0, parent:Exception = null) {

	F err(message) echo(stdlib_error_fd, pfx + message)

	pfx = "[ERROR ${Time()}] " + "  " * level
	h = Hash(e)

	F esm() {
		try {
			exception_specific_message(e)
		} catch(e) {
			guard not(ENV.get('NGS_THROW_ESM'))
			'(failed to get friendly exception message)'
		}
	}

	m =
		h.get('message') or
		esm() or
		Lines(["Unfortunately the exception had no message.", "Exception type might give a hint: ${e.typeof().name}"])

	m .= ensure(Lines)

	m.framed().err()

	err("Exception of type ${e.typeof().name} occurred")

	info_keys = h.keys() - %[message backtrace cause]

	info_keys.each(F (k) {
		out = inspect(h[k]) tor Lines(["Info: $k - (Failed to inspect)"])
		if (out is not Lines) or not(out) {
			out = Lines(["Info: $k - (Failed to inspect, no inspection info)"])
		}
		out .= mapo(limit(X, 128, '...'))
		if out.len() == 1 {
			err("Info: $k = ${out[0]}")
		} else {
			err("Info: $k:")
			err("  " + out)
		}
	})

	if 'backtrace' in h {
		err(Lines(h.backtrace, try parent.backtrace))
	}

	if 'cause' in h {
		err("Cause:")
		if e.cause is Exception {
			print_exception(e.cause, level+1, e)
		} else {
			err("  (WARNING: cause is not Exception)")
			err("  " + inspect(e.cause))
		}
	}

	if level == 0 {
		echo(stdlib_error_fd, m.framed())
	}

}

exit_hook = Hook()

ns {

	global print_exception

	do_exit_backtrace = ENV.get('NGS_EXIT_BACKTRACE', '0').decode(Bool)

	if not(do_exit_backtrace) {
		F print_exception(e:NormalExit) {
			if 'message' in e {
				echo(stdlib_error_fd, e.message)
			}
		}
	}

	# TODO: consider running this hook item last.
	#       If it has exception, it could prevent
	#       user-defined cleanups.
	exit_hook['print_exception'] = F(exit:Exit) {
		exit.exceptions.each(print_exception)
	}

}

# === Time =======================================

{
	type Time
	type TimeFail(CException)
}

TIME_FORMAT = ENV.get('NGS_TIME_FORMAT', '%F %T %Z')

doc Get epoch time
doc %RET - Int
F time() {
	ret = c_time()
	ret == -1 throws TimeFail("Failed to get time")
	ret
}

# TODO: handle errors
doc Low-level function. Do not use directly. Use Time type.
F gmtime(t:Int) {
	ret = c_gmtime(t)
	ret
}

# TODO: handle errors
doc Low-level function. Do not use directly. Use Time type.
F localtime(t:Int) {
	ret = c_localtime(t)
	ret
}

doc Low-level function. Do not use directly. Use Time type.
F strftime(tm:c_tm, format:Str) {
	ret = c_strftime(tm, format)
	ret is Null throws TimeFail("Failed to c_strftime()").set('tm', tm).set('format', format)
	ret
}

doc Initialize Time object with current time.
F init(t:Time) {
	t.epoch = time()
}

doc Initialize Time object with the given epoch time.
F init(t:Time, epoch:Int) {
	t.epoch = epoch
}

F init(t:Time, s:Str, format:Str) {
	tt = c_strptime(s, format)[1]
	tt is Null throws InvalidArgument("Failed to parse time").set('s', s).set('format', format)
	t.epoch = c_mktime(tt)
}

doc String representation of Time
doc format - strftime(3) format
doc gmt - Use GMT time zone (defaults to local time zone)
F Str(t:Time, format:Str=TIME_FORMAT, gmt:Bool=false) strftime([localtime, gmtime][Int(gmt)](t.epoch), format)

F Int(t:Time) t.epoch


doc Mesure running time of cb in microseconds
doc %RET - Int
F time(cb:Fun) {
	start = c_gettimeofday()
	cb()
	finish = c_gettimeofday()
	(finish[0]* 1000000 + finish[1]) - (start[0] * 1000000 + start[1])
}

F Bool(t:Time) true

# === Random =====================================
# This is _not_ crypto safe random!

srand(time())

doc Pick n random unique elements from something
doc %RET - Arr
F rand_uniq(something, n:Int) {
	# TODO: Fix the guard - it does not work with NumRange currently
	# guard n <= something.len()
	result = []
	safety_counter = 0
	while len(result) < n {
		r = rand(something)
		if r in result {
			safety_counter += 1
			safety_counter == STDLIB_RAND_SAFETY_MAX throws Error("Not making progress in rand_uniq(something, n:Int)")
		} else {
			result.push(r)
			safety_counter = 0
		}
	}
	result
}

doc Pick n elements from something. Uniqueness of picked elements is not guaranteed.
doc %RET - Any
F rand(something, n:Int) n.map({ rand(something) })

doc Pick random number from 0 up to but not including n
doc %RET - Int
F rand(n:Int) {
	n <= 0 throws InvalidArgument("rand(n:Int) - n must be 1 or greater")
	r = rand()
	(RAND_MAX+1) % n == 0 returns r % n
	scale = Real(n) / STDLIB_MAX_RAND_REAL
	Real(r) * scale \ floor \ Int
}

# TODO: Sequence super-type?

doc Pick one random element from array
doc %RET - Any
F rand(a:Arr) a[rand(a.len())]

doc Pick random character from a string
doc %RET - Str of length 1
F rand(a:Str) a[rand(a.len())]

F rand(a:Str, n:Int) super(a, n).join('')

doc Pick one random element from a range
doc %RET - Any
F rand(r:NumRange) {
	guard r.step == 1
	points = r.end - r.start - 1 + Int(r.include_start) + Int(r.include_end)
	rand(points) + r.start + if r.include_start then 0 else r.step
}

# === retry facility =============================

{
	doc Represents failure on all retries
	type RetryFail(Error)
}

doc Internal method. Used by retry().
F body_missing_in_retry() throw InvalidArgument("'body' argument missing in retry()")

# TODO: Handle NoNext that could occur in sleep iterator
doc Retry. Executes given "body" "times" times. Throws RetryFail if all calls fail and fail_cb is not provided.
doc times - Limit of times to run "body"
doc sleep - Either sleep in seconds between tries or Iter that returns successive sleep times in seconds
doc logger - Function to use to log attempts, caught body exceptions and sleep times. Defaults to stdlib's debug.
doc success_predicate - CANDIDATE FOR REMOVAL. Run against body results to. Says whether the attempt succeeded. Defaults to Bool.
doc title - Prefix strings sent to logger with this string. Defaults to "<retry>".
doc progress_cb - Called before each attempt with (1) current attempt number and (2) limit of attempts ("times"). Defaults to do nothing.
doc success_cb - Called when body succeeds with the result that comes from body. Defaults to identity function.
doc fail_cb - If passed, called if all attempts fail. Defaults to null.
doc %RET - Any. Result of success_cb or result of fail_cb.
doc %EX - page = retry(times=10, sleep=ExpBackIter(), body={ try `curl "http://flaky-site.com"` })
F retry(
	times:Int=60,
	sleep=1,
	logger:Fun=debug("retry", X),
	success_predicate=Bool,
	title="<retry>",
	progress_cb:Fun={null},
	success_cb:Fun=identity,
	fail_cb={throw RetryFail()},
	body:Fun=body_missing_in_retry
) {
	guard sleep is Int or sleep is Iter
	sleep_iter = if sleep is Int then ConstIter(sleep) else sleep
	result = null  # otherwise it will be local to try { ... }
	for(i;times) {
		n = i + 1
		progress_cb(n, times)
		logger("$title Attempt $n out of ${times}")
		try {
			result = body()
		} catch(e:Exception) {
			logger("$title Exception $e")
			throw e
		}
		if success_predicate(result) {
			return success_cb(result)
		}
		if(i < times - 1) {
			s = sleep_iter.next()
			logger("$title Sleeping ${s} seconds")
			$(sleep "$s")
		}
	}
	fail_cb()
}

TEST t = 0; retry(body={t+=1; false}, fail_cb={"OK"}, times=5, sleep=0) == "OK" and t == 5
TEST t = 0; retry(body={t+=1; "OK"}, fail_cb={"NOTOK"}, sleep=0) == "OK" and t == 1

# === Misc =======================================

doc Get process ID
F pid() c_getpid()

doc Get parent process ID
F ppid() c_getppid()

doc Encodes each character in a string as two uppercase hexadecimal digits
doc %RET - Str
doc %EX - encode_hex("ab")  # "6162"
F encode_hex(s:Str) {
	s.map(F(char) {
		n = ord(char)
		CHARS::hexdigits_uppercase[n / 16] + CHARS::hexdigits_uppercase[n % 16]
	}).join('')
}

TEST encode_hex('ab') == '6162'

doc Decodes each two hex digits into a character (byte). Reverse of encode_hex()
doc %RET - Str
F decode_hex(s:Str) {
	len(s) % 2 != 0 throws InvalidArgument("decode_hex() input string must contain even number of bytes")
	l = len(s) / 2
	l.map(F(i) chr(Int(s[i*2..(i*2+2)], 16))).join('')
}

TEST decode_hex("010203") == chr(1) + chr(2) + chr(3)
TEST try decode_hex("0102034") catch(e:InvalidArgument) true

STDLIB_INVALID_URI_CHAR_RE = /[^-a-zA-Z0-9_.!~*'()]/
#'

doc Encodes URI component, escaping with %XX hexadecimal codes.
doc %RET - Str
doc %EX - encode_uri_component("ab+c%")  # "ab%2Bc%25"
F encode_uri_component(s:Str) s.replace(STDLIB_INVALID_URI_CHAR_RE, F(char) '%' + encode_hex(char))

TEST encode_uri_component("ab+c%") == "ab%2Bc%25"

# TODO: more efficient
doc Decodes URI component, unsecaping %XX hexadecimals
doc %EX - decode_uri_component("ab%2Bc%25")  # "ab+c%"
F decode_uri_component(s:Str) {
	l = s.len()
	ret = ''
	for(i;l) {
		ret += if s[i] == '%' {
			i += 2
			decode_hex(s[i-1..i+1])
		} else {
			s[i]
		}
	}
	ret
}

TEST decode_uri_component("ab%2Bc%25") == "ab+c%"


doc Encodes HTML. Escapes &, < and > .
doc %RET - Str
doc %EX - "ab>+c%&'".encode_html()  # "ab&gt;+c%&amp;'"
F encode_html(s:Str) s.mapo(CHARS::html_escape.get(X, X))

TEST "ab>+c%&'".encode_html() == "ab&gt;+c%&amp;'"


doc Encodes HTML attribute. Escapes &, <, >, " and ' .
doc %RET - Str
doc %EX - "ab>+c%&'".encode_html_attr()  # "ab&gt;+c%&amp;&#39;"
F encode_html_attr(s:Str) s.mapo(CHARS::html_attr_escape.get(X, X))

TEST "ab>+c%&'".encode_html_attr() == "ab&gt;+c%&amp;&#39;"

doc Used by match EXPR { ... } construct to check whether the expression matches the case.
doc %AUTO match EXPR { ... }
doc %RET - Pred(b)(a)
doc %EX - r = match x {
doc %EX -   Int  "Got integer"
doc %EX -   /^a/ "Got special string"
doc %EX -   Str  "Got regular string"
doc %EX - }
F match(a,b) Pred(b)(a)

# === File =======================================

doc Check whether current process has the specified access to the file. Wrapper around ACCESS(2). Throws CException.
doc mode - One of the file ACCESS::* modes, defaults to ACCESS::F_OK (test file existance only).
doc %RET - Bool
doc %EX - access(File("mydata"), ACCESS::R_OK).not() throws Error("No access to data file").set("file", "mydata")
F access(f:File, mode:Int=ACCESS::F_OK) {
	ret = c_access(f.path, mode)
	ret == 0 returns true
	assert(ret < 0)
	e = c_errno()
	e == C_EACCES returns false
	# TODO: Better exception
	throw CException(e, "access() failed")
}

# Hope this is correct for all platforms
TEST access(File("/"), bor(ACCESS::R_OK, ACCESS::X_OK))

doc Read whole file
F read(fname:Str) {
	f = File(fname)
	open(f, 'r')
	finally(body = {read(f.fd)}, cleanup = {f.close()})
}

doc Read whole file
F read(f:File) read(f.path)

doc Write whole file
F write(fname:Str, s:Str) {
	'\n' in s and '\n' in fname throws InvalidArgument("Both data and file name contain newline characters").set('s', s).set('fname', fname)
	if '\n' in fname {
		warn("Using deprecated write() arguments order")
		return write(s, fname)
	}
	f = File(fname)
	open(f, 'w')
	finally(body = {write(f, s)}, cleanup = {f.close()})
}

doc Write whole file if it's closed, write to file descriptor if it's open
F write(s:Str, f:File) {
	warn("Using deprecated write() arguments order")
	write(f, s)
}

F write(f:File, s:Str) {
	write(if f.fd is Null then f.path else f.fd, s)
}

# === Misc =======================================

doc %STATUS - experimental
F encode_base64(s:Str, wrap:Int=0) {
	guard OS.posix
	`echo -n $s | base64 -w $wrap`
}

doc %STATUS - experimental
F encode_base64(s:Str, wrap:Int=0) {
	guard OS.darwin
	`echo -n $s | base64 -b $wrap`
}

doc %STATUS - experimental
F decode_base64(s:Str) `echo $s | base64 --decode`

# === Networking =================================

### F read(s:Str) {
### 	# impl curl
### 	guard s ~ /^http[s]?:\/\//i
### 	guard "curl" found
### }

F myip() {
	fetch('https://api.myip.com').ip.IPAddr()
}


# === Caching ====================================

# TODO: *args and per-args combination wrapping
doc Cache cb results. Runs cb only once. TODO: Support arguments.
doc %RET - New function which wraps cb.
doc %EX - my_func = cached( { expensive(); calculation(); steps(); result } )
doc %EX - use_result_of(my_func())
doc %EX - ...
doc %EX - use_result_of(my_func())
F cached(cb:Fun) {
	result = EmptyBox()
	F cached_function_wrapper() {
		if not(result) {
			result = FullBox(cb())
		}
		result.get()
	}
}

# === Doc ========================================

doc %STATUS - experimental
doc %AUTO - \name attr1=val1 attr2=val2 ... [ ... ]
F \(name:Str, attributes:Hash, children:Arr) {
	Doc::Node(name, children.reject(NoData).map(only(FullBox, get)), **attributes)
}