Dendrology

Rendering of trees and DAGs in the console

Dendrology provides methods for rendering data in a tree or directed acyclic graph structure as lines, for rendering in a monospaced font, typically in a terminal.

Features

display any tree-structured data as a tree in a console
tree data can be of any type whose children can be accessed recursively
display directed acyclic graphs in a console
output is a linearized sequence of any type
tree input is processed lazily, and output is a stream
can be easily adapted to any grid-like layout, e.g. an HTML table
custom textual renderings are available

Availability Plan

Dendrology has not yet been published. The medium-term plan is to build Dendrology with Fury and to publish it as a source build on Vent. This will enable ordinary users to write and build software which depends on Dendrology.

Subsequently, Dendrology will also be made available as a binary in the Maven Central repository. This will enable users of other build tools to use it.

For the overeager, curious and impatient, see building.

Getting Started

Dendrology can render tree-like structures as text, such as the following,

├─● Plantae
├─● Fungi
│ ├─● Rozellomyceta
│ ├─● Aphelidiomyceta
│ └─● Eumycota
├─● Protozoa
├─● Bacteria
└─● Animalia
  └─● Chordata
    └─● Mammalia
      └─● Carnivora
        ├─● Feliadae
        ├─● Canidae
        │ └─● Canis
        └─● Ursidae

and DAGs such as this:

▪ Any
└─▪ Matchable
  ├─▪ AnyRef
  │ ├─▪ List[Int]
  └─│─│─▪ AnyVal
    │ │ ├─▪ Boolean
    │ │ ├─│─▪ Int
    │ │ └─│─│─▪ Unit
    └─│───│─│─│─▪ String
      └───│─│─│─┴─▪ Null
          └─┴─┴───┴─▪ Nothing

Dendrology is versatile, and can represent data in a variety of input and output types, so long as methods are specified for working with those types.

All Dendrology terms and types are in the dendrology package.

import dendrology.*

Trees

To create a tree, all we need is the root node (or nodes), of some type, and a way to access a node's children (of the same type). This can then be applied recursively to the root node to fully expand the tree. This approach has the advantage that it does not require the data to be reshaped into a particular data structure to be used.

Dendrology makes it possible to define the method for accessing a node's children in two ways: either as a lambda when a TreeDiagram is constructed, like so,

import anticipation.Text

case class Person(name: Text, age: Int, children: List[Person])
val daughter = Person(t"Jill", 7, List())
val son = Person(t"Jack", 9, List())
val headOfFamily = Person(t"John", 37, List(son, daughter))

val diagram = TreeDiagram.by[Person](person => person.children)(headOfFamily)

or alternatively through a contextual instance of the typeclass Expandable for the given node type. Types which are naturally hierarchical can, of course, define their own Expandable instances so they can be used in tree-structures without the need to specify how child nodes should be accessed. For example:

given Expandable[Person] = _.children
val diagram2 = TreeDiagram(headOfFamily)

It's possible to include multiple root nodes as parameters to TreeDiagram, which will appear as top-level siblings in the tree.

Instances of TreeDiagram provide a few methods to help with rendering a diagram. The render method will meet most requirements for rendering a tree diagram as a series of lines. The render method takes a single parameter, a lambda for converting from the type of the nodes, NodeType, to a serialized type of each line, LineType. Typical choices might be a NodeType of some user-defined type like Person, and a LineType of Text.

For example, we could write,

import treeStyles.default

val lines = diagram2.render(_.name)
@main
def run(): Unit =
  lines.foreach(Out.println(_))

The algorithm performs a depth-first traversal of the data, mapping each node to a line, and flattening the data in the process. The output will be a LazyList[LineType].

The parameter to the render method, _.name, will determine the LineType is Text, which will resolve a contextual TreeStyle[Text], which is needed to render the horizontal and vertical lines of the diagram as Text. The dendrology.treeStyles package provides default, rounded and ascii renderings for Text and other Textual types.

In addition to render, the method TreeDiagram#nodes can recover the node value used to generate each line in the diagram. A common way to make use of this is to zip it with the output from render to get a LazyList[(LineType, NodeType)] which could be used to perform additional post-processing of each line, based on information from its corresponding node.

Laziness

The drawTree implementation accesses the tree data structure mostly lazily, but does need to know the number of elements in each ancestor of the current node, yet does not need to know anything about the descendants of subsequent nodes in the traversal until they are reached in their natural order.

This is necessary because any subsequent siblings of any ancestor nodes will require an additional descending vertical line to be rendered in the appropriate column of the current line, whereas that vertical line should be absent for each ancestor that is the last of its siblings.

Directed Acyclic Graphs

A DAG diagram is represented by the DagDiagram class, and should be constructed from a Dag instance from Acyclicity.

For example, given a value dag, an instance of Dag[Person], we can construct a new DagDiagram with DagDiagram(dag). Unlike TreeDiagram, DagDiagram always takes exactly one parameter.

Like TreeDiagram, though, DagDiagram provides render and nodes methods with the same purpose. While TreeDiagram returns a LazyList, DagDiagram cannot (due to the nature of the data it represents) evaluate lazily, and provides a strict List.

Here is the full code used to create the example DAG above:

import acyclicity.Dag
import gossamer.t
import turbulence.Out, turbulence.stdioSources.jvm
import dagStyles.default

val dag = Dag(
  t"Any"       -> Set(),
  t"Matchable" -> Set(t"Any"),
  t"AnyVal"    -> Set(t"Matchable"),
  t"AnyRef"    -> Set(t"Matchable"),
  t"Unit"      -> Set(t"AnyVal"),
  t"Boolean"   -> Set(t"AnyVal"),
  t"Int"       -> Set(t"AnyVal"),
  t"String"    -> Set(t"AnyRef"),
  t"List[Int]" -> Set(t"AnyRef"),
  t"Null"      -> Set(t"String", t"List[Int]"),
  t"Nothing"   -> Set(t"Null", t"Unit", t"Boolean", t"Int")
)

@main
def run2(): Unit =
  DagDiagram(dag).render { node => t"▪ $node" }.foreach(Out.println(_))

Status

Dendrology is classified as maturescent. For reference, Scala One projects are categorized into one of the following five stability levels:

embryonic: for experimental or demonstrative purposes only, without any guarantees of longevity
fledgling: of proven utility, seeking contributions, but liable to significant redesigns
maturescent: major design decisions broady settled, seeking probatory adoption and refinement
dependable: production-ready, subject to controlled ongoing maintenance and enhancement; tagged as version 1.0.0 or later
adamantine: proven, reliable and production-ready, with no further breaking changes ever anticipated

Projects at any stability level, even embryonic projects, can still be used, as long as caution is taken to avoid a mismatch between the project's stability level and the required stability and maintainability of your own project.

Dendrology is designed to be small. Its entire source code currently consists of 165 lines of code.

Building

Dendrology will ultimately be built by Fury, when it is published. In the meantime, two possibilities are offered, however they are acknowledged to be fragile, inadequately tested, and unsuitable for anything more than experimentation. They are provided only for the necessity of providing some answer to the question, "how can I try Dendrology?".

Copy the sources into your own project

Read the fury file in the repository root to understand Dendrology's build structure, dependencies and source location; the file format should be short and quite intuitive. Copy the sources into a source directory in your own project, then repeat (recursively) for each of the dependencies.

The sources are compiled against the latest nightly release of Scala 3. There should be no problem to compile the project together with all of its dependencies in a single compilation.
Build with Wrath

Wrath is a bootstrapping script for building Dendrology and other projects in the absence of a fully-featured build tool. It is designed to read the fury file in the project directory, and produce a collection of JAR files which can be added to a classpath, by compiling the project and all of its dependencies, including the Scala compiler itself.

Download the latest version of wrath, make it executable, and add it to your path, for example by copying it to /usr/local/bin/.

Clone this repository inside an empty directory, so that the build can safely make clones of repositories it depends on as peers of dendrology. Run wrath -F in the repository root. This will download and compile the latest version of Scala, as well as all of Dendrology's dependencies.

If the build was successful, the compiled JAR files can be found in the .wrath/dist directory.

Contributing

Contributors to Dendrology are welcome and encouraged. New contributors may like to look for issues marked beginner.

We suggest that all contributors read the Contributing Guide to make the process of contributing to Dendrology easier.

Please do not contact project maintainers privately with questions unless there is a good reason to keep them private. While it can be tempting to repsond to such questions, private answers cannot be shared with a wider audience, and it can result in duplication of effort.

Author

Dendrology was designed and developed by Jon Pretty, and commercial support and training on all aspects of Scala 3 is available from Propensive OÜ.

Name

Dendrology is the study of trees.

In general, Scala One project names are always chosen with some rationale, however it is usually frivolous. Each name is chosen for more for its uniqueness and intrigue than its concision or catchiness, and there is no bias towards names with positive or "nice" meanings—since many of the libraries perform some quite unpleasant tasks.

Names should be English words, though many are obscure or archaic, and it should be noted how willingly English adopts foreign words. Names are generally of Greek or Latin origin, and have often arrived in English via a romance language.

Logo

The logo shows a pattern of leaves from a tree; trees being the subject of Dendrology.

propensive/dendrology