Like foldMap, but with an effectful projection.

Like Getting, but allows for retrieving the r element in some Applicative context m.

Given an effectful projection from a into a monoid r, retrieve the sum of all a values in an s structure as targetted by the GettingM optic. Note that the Monoid constraint on r is implicit via Const, but we note it in the type for clarity.

The proposition that some third value comes strictly after the first argument but strictly before the second argument.

This function yields Just of the union of its arguments if that union can be expressed as a single interval, and otherwise yields Nothing.

Finds the unique shortest list of intervals having the same set union as the given list and nondecreasing low endpoints.

The result also satisfies the definition of normal given below.

Each interval is specified by pairing its low and high endpoints, which are included in the interval, except when the first component of the pair exceeds the second, in which case the interval is empty.

Supporting Theory

Definition of normal

Call a list of intervals normal when it excludes empty intervals and for any two consecutive intervals [a .. b] and [c .. d], there exists an x such that b < x < c.

We claim that, among those interval lists having any given union, normality is equivalent to having minimal length and nondecreasing low endpoints.

Normal implies minimal length

To see why, first consider any normal interval list N. Clearly its low endpoints are nondecreasing--and in fact are strictly increasing with gaps inbetween. Therefore any interval intersecting at least two intervals of N necessarily includes at least one point in such a gap, and that point is outside the union of N. Hence every interval list with the same union as N consists of (possibly empty) subintervals of intervals listed by N. Hence N has minimal length among such lists.

Minimal length implies normal

To establish the converse, consider any interval list N having nondecreasing endpoints and minimal length. Deleting empty intervals from N would only decrease its length, so N must not include any. Next note that if [a .. b] and [c .. d] are consecutive intervals within N, then either there exists an x such that b < x < c, or else we may shorten N without changing its union by replacing both [a .. b] and [c .. d] by the single interval [a .. max b d], which would contradict the minimality of the length of N. Thus N fulfills all the requirements of being a normal interval list.

Existence

Having proved the desired equivalence, we turn to the question of the existence of the shortest interval list having the same union as any given interval list and nondecreasing low endpoints.

Consider the set S of interval lists having the same union as the given interval list and nondecreasing low endpoints. Note that by performing a stable sort on the given interval list we immediately find that S is nonempty. Being nonempty, it must contain at least one element of minimal length.

Uniqueness

But could there be two different interval lists of minimal length for their common union, both with nondecreasing low endpoints?

We claim the answer is no, and proceed by induction on that shared minimal length. The base case is trivial: if both lists are empty, then they cannot differ.

For the induction step, suppose that there are two interval lists that share the same positive minimal length among those that have nondecreasing low endpoints and a given same union. Call them L and N. We will prove that L = N.

Let (a, b) = head L and (e, f) = head N.

If a < e then a is in union L but not in union N, contradicting our assumpion that union L = union N. Likewise we may exclude e < a, leaving a = e and (a, f) = head N.

Next suppose that b < f. If tail L == [] then clearly f is outside of union L and yet inside of union N, which is once again beyond our scenario. Let (c, d) = head (tail L). By the equivalence we established earlier, L is normal and hence there exists an x such that b < x < c. If x <= f, then x is in [a .. f] and yet outside of union L, once again contradicting our hypotheses. Otherwise f < x < c, and hence f is outside of union L, a similar contradiction. Therefore our supposition that b < f must be impossible, and we can likewise exclude f < b. Hence b = f.

Having establishing both a = e and b = f, we conclude that head L = head N. It follows that tail L and tail N have the same union as each other. Both tails must be minimal in length, because otherwise there would also be a way to shorten L or N in a union-preserving way. Invoking our induction hypothesis we find that tail L = tail N; therefore L = N.

Conclusions

In conclusion, the desired behavior of this function is well defined by the first paragraph in this comment block, and the second paragraph (once combined with a requirement to preserve the union) provides an equivalent definition.

To check that the implementation actually fulfills these requirements, note that it filters out empty intervals, sorts those that remain, and then merges intervals until the resulting list becomes normal.

There are also unit tests checking that the result is normal and has the same union as the given list.

Returns a sorted list that contains all intervals from the minimal set of intervals to represent the given list of intervals.

Merges overlapping intervals in a list of intervals. Think disjunctive normal form.

toModulePath takes an include-relative path to a .proto file and produces a "module path" which is used during code generation.

Note that, with the exception of the '.proto' portion of the input filepath, this function interprets . in the filename components as if they were additional slashes (assuming that the . is not the first character, which is merely ignored). So e.g. "googleprotobuftimestamp.proto" and "google.protobuf.timestamp.proto" map to the same module path.

>>> toModulePath "/absolute/path/fails.proto"
Left "expected include-relative path"

>>> toModulePath "relative/path/to/file_without_proto_suffix_fails"
Left "expected .proto suffix"

>>> toModulePath "relative/path/to/file_without_proto_suffix_fails.txt"
Left "expected .proto suffix"

>>> toModulePath "../foo.proto"
Left "expected include-relative path, but the path started with ../"

>>> toModulePath "foo..proto"
Left "path contained unexpected .. after canonicalization, please use form x.y.z.proto"

>>> toModulePath "foo/bar/baz..proto"
Left "path contained unexpected .. after canonicalization, please use form x.y.z.proto"

>>> toModulePath "foo.bar../baz.proto"
Left "path contained unexpected .. after canonicalization, please use form x.y.z.proto"

>>> toModulePath "google/protobuf/timestamp.proto"
Right (Path {components = "Google" :| ["Protobuf","Timestamp"]})

>>> toModulePath "a/b/c/google.protobuf.timestamp.proto"
Right (Path {components = "A" :| ["B","C","Google","Protobuf","Timestamp"]})

>>> toModulePath "foo/FiLeName_underscore.and.then.some.dots.proto"
Right (Path {components = "Foo" :| ["FiLeName_underscore","And","Then","Some","Dots"]})

importProto searchPaths toplevel inc attempts to import include-relative inc after locating it somewhere in the searchPaths; toplevel is simply the path of toplevel .proto being processed so we can report it in an error message. This function terminates the program if it cannot find the file to import or if it cannot construct a valid module path from it.

Attempts to locate the first (if any) filename that exists on the given search paths, and constructs the "module path" from the given include-relative filename (2nd parameter). Terminates the program with an error if the given pathname is not relative.

A mapping from .proto type identifiers to their type information

Information about messages and enumerations

Whether a definition is an enumeration or a message

Returns True if the given primitive type is packable. The TypeContext is used to distinguish Named enums and messages, only the former of which are packable.

toPascalCase xs' sends a snake-case string xs to a pascal-cased string. Trailing underscores are not dropped from the input string and exactly double underscores are replaced by a single underscore.

toCamelCase xs sends a snake-case string xs to a camel-cased string.

Uppercases the first character of a string.

Examples

>>> toUpperFirst "abc"
"Abc"

>>> toUpperFirst ""
""

segmentBy p xs partitions xs into segments of Either [a] [a] with:

• Right sublists containing elements satisfying p, otherwise;
• Left sublists containing elements that do not satisfy p

Examples

>>> segmentBy (\c -> c == '_') "abc_123_xyz"
[Left "abc",Right "_",Left "123",Right "_",Left "xyz"]

suffixBy p xs yields Right (xs', suf) if suf is the longest suffix satisfying p and xs' is the rest of the rest, otherwise the string is given back as Left xs signifying xs had no suffix satisfying p.

typeLikeName xs produces either the pascal-cased version of the string xs if it begins with an alphabetical character or underscore - which is replaced with X. A CompileError is emitted if the starting character is non-alphabetic or if xs == "".

fieldLikeName field is the casing transformation used to produce record selectors from message fields. If field is prefixed by a span of uppercase characters then that prefix will be lowercased while the remaining string is left unchanged.

prefixedMethodName service method produces a Haskell record selector name for the service method method by joining the names service, method under concatenation on a camel-casing transformation.

prefixedFieldName prefix field constructs a Haskell record selector name by prepending prefix in camel-case to the message field/service method name field.

Given a DotProtoIdentifier for the parent type and the unqualified name of this type, generate the corresponding Haskell name

Bookeeping for qualified fields

Bookkeeping for fields

Bookkeeping for oneof fields

Bookkeeping for oneof subfields

Project qualified fields, given a projection function per field type.