  Context: Container data types are ubiquitous in computer programming,
enabling developers to efficiently store and process collections of data with
an easy-to-use programming interface. Many programming languages offer a
variety of container implementations in their standard libraries based on data
structures offering different capabilities and performance characteristics.
  Inquiry: Choosing the *best* container for an application is not always
straightforward, as performance characteristics can change drastically in
different scenarios, and as real-world performance is not always correlated to
theoretical complexity.
  Approach: We present Primrose, a language-agnostic tool for selecting the
best performing valid container implementation from a set of container data
types that satisfy *properties* given by application developers. Primrose
automatically selects the set of valid container implementations for which the
*library specifications*, written by the developers of container libraries,
satisfies the specified properties. Finally, Primrose ranks the valid library
implementations based on their runtime performance.
  Knowledge: With Primrose, application developers can specify the expected
behaviour of a container as a type refinement with *semantic properties*, e.g.,
if the container should only contain unique values (such as a `set`) or should
satisfy the LIFO property of a `stack`. Semantic properties nicely complement
*syntactic properties* (i.e., traits, interfaces, or type classes), together
allowing developers to specify a container's programming interface *and*
behaviour without committing to a concrete implementation.
  Grounding: We present our prototype implementation of Primrose that
preprocesses annotated Rust code, selects valid container implementations and
ranks them on their performance. The design of Primrose is, however,
language-agnostic, and is easy to integrate into other programming languages
that support container data types and traits, interfaces, or type classes. Our
implementation encodes properties and library specifications into verification
conditions in Rosette, an interface for SMT solvers, which determines the set
of valid container implementations. We evaluate Primrose by specifying several
container implementations, and measuring the time taken to select valid
implementations for various combinations of properties with the solver. We
automatically validate that container implementations conform to their library
specifications via property-based testing.
  Importance: This work provides a novel approach to bring abstract modelling
and specification of container types directly into the programmer's workflow.
Instead of selecting concrete container implementations, application
programmers can now work on the level of specification, merely stating the
behaviours they require from their container types, and the best implementation
can be selected automatically.
