DEV Community: arclight

Revitalizing Castlequest, Part 4: Squarified Cushioned Treemaps

arclight — Tue, 19 Oct 2021 21:57:11 +0000

In the previous installment, we looked at the source code's literal text shape to quickly estimate code "legacyness". FORTRAN source code prior to Fortran 90 has a very distinct shape due to the historical use of punched cards for code input. Knowing the language evolved toward an ALGOL-like block structure, we can even differentiate F66 from F77 just by looking at code shape. While that allows us to make a quick qualitative assessment of individual files, we often want to quickly assess the complexity of a complete project.

Listings and Trees

A very quick way to get information about a project is simply to look at the project's directory listing. For Castlequest, we see:

$ dir /s /O-s
 Volume in drive C is OS
 Volume Serial Number is 569C-2024

 Directory of C:\Users\apthorpe\Documents\git_projects\appraiser\tests\data\Castlequest_F66

04/12/2021  07:57         6,847,398 castlequest.pdf
04/12/2021  07:57           341,671 castlequest.ocr.txt
09/17/2021  10:40             3,384 WizTree_20210917103835.csv
08/07/2021  10:56             2,179 README.md
04/12/2021  07:57               188 LICENSE
08/20/2021  07:39    <DIR>          src
09/17/2021  10:38    <DIR>          ..
09/17/2021  10:38    <DIR>          .
               5 File(s)      7,194,820 bytes

 Directory of C:\Users\apthorpe\Documents\git_projects\appraiser\tests\data\Castlequest_F66\src

08/07/2021  10:56            64,190 main.f
08/07/2021  10:56            20,196 long.dat
08/07/2021  10:56             6,663 move.f
08/07/2021  10:56             6,499 init.f
08/07/2021  10:56             4,347 des.f
08/07/2021  10:56             4,330 help.f
08/07/2021  10:56             3,971 input.f
08/07/2021  10:56             3,950 short.dat
08/07/2021  10:56             2,918 invent.f
08/07/2021  10:56             2,889 object.dat
08/07/2021  10:56             1,648 fread.f
08/07/2021  10:56             1,598 hint.dat
08/07/2021  10:56             1,465 inst.dat
08/07/2021  10:56             1,369 wwolf.f
08/07/2021  10:56             1,238 savres.f
08/07/2021  10:56             1,026 ggnome.f
08/07/2021  10:56               913 adscor.f
08/07/2021  10:56               653 obj.f
08/07/2021  10:56               423 Makefile
08/07/2021  10:56               413 yorn.f
08/07/2021  10:56               243 rstart.f
08/07/2021  10:56               178 isig.f
08/07/2021  10:56               126 asa.py
08/20/2021  07:39    <DIR>          .
08/20/2021  07:39    <DIR>          ..
              23 File(s)        131,246 bytes

     Total Files Listed:
              28 File(s)      7,326,066 bytes
               5 Dir(s)  617,442,611,200 bytes free

This is from using the Windows command shell; Linux and MacOS shell users can get about the same information with ls -R -S -s -h -1. The selected options are recursive, ordered by decreasing size in human-readable units, single column.

It's not the greatest display but it's simple. Source files are under ./src, the largest one is main.f followed by move.f down to isig.f. This may be adequate for small projects but starts showing its limits after about half a screen of output.

A slightly better command line tool is tree which as the name suggests displays the directory structure as a tree. Windows' tree.com is not nearly as useful as the Unix version. Here we see the files arranged in a tree structure ordered by decreasing file size:

$ c:\tools\msys64\usr\bin\tree.exe -h --sort=size
.
├── [6.5M]  castlequest.pdf
├── [334K]  castlequest.ocr.txt
├── [3.3K]  WizTree_20210917103835.csv
├── [2.1K]  README.md
├── [ 188]  LICENSE
└── [   0]  src
    ├── [ 63K]  main.f
    ├── [ 20K]  long.dat
    ├── [6.5K]  move.f
    ├── [6.3K]  init.f
    ├── [4.2K]  des.f
    ├── [4.2K]  help.f
    ├── [3.9K]  input.f
    ├── [3.9K]  short.dat
    ├── [2.8K]  invent.f
    ├── [2.8K]  object.dat
    ├── [1.6K]  fread.f
    ├── [1.6K]  hint.dat
    ├── [1.4K]  inst.dat
    ├── [1.3K]  wwolf.f
    ├── [1.2K]  savres.f
    ├── [1.0K]  ggnome.f
    ├── [ 913]  adscor.f
    ├── [ 653]  obj.f
    ├── [ 423]  Makefile
    ├── [ 413]  yorn.f
    ├── [ 243]  rstart.f
    ├── [ 178]  isig.f
    └── [ 126]  asa.py

1 directory, 28 files

Again, only slightly better than the flat display of dir or ls and really only suitable for small projects. Beyond a screenful of output, it's difficult to grasp the entirety of a project, its structure, size, and composition. The terminal interface is limiting; let's look for a graphical tool.

Treemaps

We'd like to have a single image which displays the fraction of project space occupied by each file and directory over the entire project, ideally with some means of differentiating code from data from infrastructure, etc.

Introducing the treemap, a way of displaying hierarchical information as a two-dimensional map. Elements and groups are represented as rectangles, hierarchy is displayed using arrangement / layout, and rectangle size and color communicate properties about each element. Here is the full Castlequest project viewed as a treemap:

The area of a rectangle corresponds to file or directory size. Files are represented as individual rectangles which may be grouped into larger rectangles to show the directory hierarchy. Color indicates file type (extension).

We immediately see that the bulk of the project's size is taken up by the PDF scans of the source code. This is not terribly useful but it does indicate that the interesting parts of the project take up only a small amount of space in the project.

Ideally there would be a way to emphasize only the types of files we're interested in, but common treemap visualizers have very limited filtering capabilities. The primary use case of this class of utility is to quickly identify large files to help with filesystem maintenance. The example here is taken from WizTree on Windows but there are a number of free and commercial tools available for each platform. SequoiaView, KDirStat/QDirStat, WinDirStat, and Disk Inventory X all provide roughly the same functionality.

This is a good starting point; let's move on to looking specifically at Castlequest's src directory:

One file (main.f) is obviously much larger than all the other source files. Knowing nothing else about the project, we can guess that most of our modernization effort will be focused on that single file. We also see a number of data files associated with the project which implies there are file operations and data structures within the source code to manage this data. The size of the data files may imply the amount of static storage (RAM) or file activity the code requires. Remember that we're looking at the whole project, not just source code.

This abstraction comes with a cost. While we gain an overall impression of project size and composition, some useful detail is obscured such as file and directory names. Using WizTree interactively we can see full path name and both allocated and actual file size. That's not apparent just from screenshots of the application. Still, we might like visual indication of the dialect of Fortran used in a file, the number and size of program units (e.g. functions, subroutines) in each file, and other metrics like number and severity of uncomfortable legacy constructs.

It's unlikely an existing tool does everything we might want but depending on how useful we find this analysis, we might put some effort toward extending these utilities or writing a custom visualizer as was done for displaying code shape.

Conveniently, treemap generation is not terribly complex; the original papers describing the algorithms for squarifying and cushioning treemaps are readily available. Further, treemaps have been used to visualize a wide variety of hierarchical data beyond filesystem contents. There are libraries in a number of languages which simplify treemap creation, for example the Python library squarify generates treemap images using the Matplotlib plotting library.

Visualizing Other Projects

Castlequest is a relatively small and simple project. A slightly more complex project is NASA's CEA2 (Chemical Equilibrium with Applications) which performs literal rocket science.

Source code is shown in yellow; we see it's a small fraction of the chemical transport and thermodynamic datafiles and example data. We also see source code spread over a few directories. CEA2 consists of an analytical package and several utilities for managing its physical property databases.

A larger legacy FORTRAN project is NASTRAN-95, a finite element structural analysis code (again from NASA) that consists of almost 2000 individual source files as well as substantial example case input and output files.

Here we see a very clear organization of source and data. Source files are rather uniform in size compared to Castlequest, suggesting that NASTRAN is more evenly decomposed. Individual routines may be more focused and clearer than what we expect of Castlequest's large main program.

Summary

This sort of visualization is not necessary for refactoring but it helps with project estimation especially when a quick estimate is needed. Treemaps are an interesting way of visualizing data. Most standalone treemapping tools are aimed at filesystem maintenance but the general technique is useful for visualizing any form of hierarchical data.

Image Credits:

Cushion photo courtesy of ~riley, CC BY-SA 3.0, via Wikimedia Commons

Revitalizing Castlequest, Part 3: The Shape of Code

arclight — Thu, 30 Sep 2021 14:59:31 +0000

In the previous installment, I covered some of the inconvenient aspects of legacy FORTRAN composition and output, explained the origin of what we now consider misfeatures, and presented a case for changing Castlequest to play more comfortably on modern systems.

Apologies

Before I get into today's topic, I have to apologize for the delay in writing. The Castlequest story has been stagnant but not for lack of interest or motivation. Originally I hoped to discuss what we might mean by legacy code and show qualitative views of a project that may help us estimate "legacyness" of a project.

This rapidly devolved into an extended tool-building effort which has gone on far longer than I had intended. As tool construction dragged on, it has been difficult to show even interim results because showing a single indirect representation of the code or project seems to overemphasize the significance of the results or the importance of a single tool.

It's ironic that this article has taken so long to produce because the whole intent of using qualitative graphical views is to make initial assessment faster and easier.

Let's Talk About Code Shape

One method of assessing code "legacyness" I have been exploring is visualizing code "shape". You can often tell the vintage of old Fortran source code just by looking at the arrangement of text on a page without looking directly at the source code.

As an example, FORTRAN 66 is very "flat", monolithic, and linear because the language lacks the block constructs introduced in FORTRAN 77. "Structured" programming didn't arrive until the late 60s or early 70s. Also, F66 dates to the era of punchcards and batch computing on relatively limited hardware. The cost of whitespace, structure, routine calls, etc. was much higher in that era. The shape of F66 code reflects limitations of the language, hardware, and development paradigms available at the time.

In contrast, FORTRAN 77 inherited much of ALGOL's block structure (IF-THEN-ELSE-ENDIF, DO-ENDDO). It was released well into the era of interactive computing where developers had immediate access to a command shell, editor, and compiler. The cost of whitespace, routine calls, structure, etc. had dropped and resources for large programs were more widely available. The problems with monolithic and unstructured code were well known by this point. Developers knew decomposition was necessary to build and maintain large systems. The shape of F77 code again reflects the state of the language, hardware, and development paradigms. F77 source code is much more likely to be indented, decomposed into subroutines and functions, and generally be much more readable than F66.

Fortran 90 introduced free-form source format, doing away with the fixed columnar format dating back to the language's introduction in 1956. The form of comments and line continuations were substantially changed and new block structures, modules, user-defined data types, and classes were added to the language. The six character limit on variable and routine names was lifted and lower case names were supported as standard. These advances meant that modern Fortran can have a much less distinct shape than its predecessors; from a distance, modern Fortran can be indistinguishable from C or C++.

For better or worse, Fortran has valued backward compatibility from its earliest standards so it's possible to write F77 in F66 format or F90 in F77 format or just ignore modern constructs entirely and write F66 in F90 format. Due to backwards compatibility, the presence or absence of specific statements or constructs may not be enough to assess a code's "legacyness". Code shape may be a better indicator of "legacyness" than file extension.

While it's an imperfect measure, the shape of source can tell us much about the condition of a Fortran codebase. Compare that to Python where the shape of modern and legacy source code is virtually identical making "legacyness" difficult to detect without detailed analysis, either by automatic parsing or manual inspection.

The Problem With Parsing

Even though parsing can be automated, it is still computationally intensive compared to generating a bitmap image from a text file. Legacy code parsers also need to cope with a variety of proprietary and obsolete constructs whereas an image generator just needs the ability to read text and produce a bitmap. This makes a code shape visualizer much easier to write than a special-purpose legacy code parser or a utility to automate compilation and sift through errors and diagnostics. Special-purpose parsing is valuable, but as I have found out it's also complex and time-consuming. Identifying and visualizing characteristics of legacy code is not exactly straightforward and it's not a simple matter to repurpose a development tool for custom static analysis.

Another problem with repurposing a compiler for legacy code detection is that the source code may be so obtuse or non-standard that it does not compile with modern tools. A code may be of interest specifically because it does not easily compile and the owner wants to estimate the effort needed to return the code to a buildable, maintainable state.

The Benefits of Shape Analysis

Intentionally reducing the fidelity of the source code view keeps the eye focused on the code shape without the risk of staring too deeply into details. There's a limit to what code shape will tell you about a project but that's a good thing.

A quick assessment should be quick. It's too easy to get bogged down looking at specific code constructs and thinking through how they might be improved or eliminated instead of doing a quick high-level inspection.

Fire!

It's time for another tortured analogy to justify rapid low fidelity assessment.

Imagine there's a fire reported at an apartment complex. Firefighters arrive and the first thing they do is survey the fireground. They look very generally at what's on fire (a dumpster, a single unit, one building, multiple buildings, etc.), how intense or widespread the fire appears, and sort out where residents and employees are likely to be. They do this quickly.

Once they estimate the totality of the fire and the characteristics of the fireground, they'll formulate a plan of attack and get to work. Eventually they will check unit by unit, floor by floor, and building by building to evacuate people. Initially however they need a rough idea of what they're up against and will spend the time to gather enough information to make a plan.

Refactoring software does not have the same urgency and risk as firefighting. On the other hand, firefighters don't have to negotiate with the apartment complex owner, mayor, and city council over how many firefighters, trucks, hoses, gallons of water, and time they will be allowed to use to put out the fire.

In our case, gathering enough information to make a plan takes effort, effort translates to time which translates to money, and clients and managers want to see a plan and cost estimate before they risk any money.

Firefighters trade personal safety for freedom of action and occasionally a sweet mustache. They are very judicious about what risks they'll accept but they also have some very direct priorities: preserve life (theirs, the public's) and property in that order. If they need to break down a door or cut a hole in the roof, they just do it. No all-day meetings with managers and stakeholders. Door, meet halligan...

In both cases, you need enough information to make a plan and you need to gather that information quickly. That plan will be created from incomplete information but that's okay. It only needs to be good enough to address big picture risks and estimate the resources required to finish the job. You won't know what you're actually up against until you're in the middle of it. You always risk facing a situation substantially worse than your initial assessment. With practice and experience, you'll learn to "read" the fireground faster and more accurately, you'll make better plans and reduce avoidable risks.

Nice analogy, but what does this have to do with Castlequest? Not much. Let's look at some pretty pictures.

The Shape of ADSCOR

This is ADSCOR.F, the subroutine that totals the player's score and returns it via the argument II:

C----------------------------------------------------
      SUBROUTINE ADSCOR(II)
      INTEGER SAVAR(400)
      LOGICAL DEBUG
      COMMON  DEBUG, ISEED
      COMMON /BLOCK2/ SAVAR
      II = 0
           IF (SAVAR( 4) .EQ. 72) II=II+9
           IF (SAVAR( 7) .EQ. 72) II=II+10
           IF (SAVAR(12) .EQ. 72) II=II+10
           IF (SAVAR(17) .EQ. 72) II=II+10
           IF (SAVAR(18) .EQ. 81) II=II+1
           IF (SAVAR(19) .EQ. 72) II=II+10
           IF (SAVAR(23) .EQ. 72) II=II+10
           IF (SAVAR(24) .EQ. 72) II=II+10
           IF (SAVAR(28) .EQ. 72) II=II+10
           IF (SAVAR(29) .EQ. 72) II=II+10
           IF (SAVAR(30) .EQ. 72) II=II+10
C Score is dependent on the number of moves.
      ITEMP = SAVAR(90) - 250
      IF (ITEMP .GE. 0) II = II - (ITEMP/5)
      IF (DEBUG) WRITE(6,8001) II
 8001 FORMAT('0  RESULT OF "ADSCOR" IS:', I3)
      RETURN
      END

Try to ignore the literal text and just focus on its shape. It's difficult. We are familiar with text, we expect it to have meaning, and we are naturally predisposed to look for patterns. We can't really help it. If we want to look at the shape, we need to obscure the text:

A note on color: black is source code, red is a comment, light green is a line label (number), spaces are very light gray, and the page background is a very light cream color to very slightly differentiate space characters from empty space (a lack of characters).

What stands out?

There are very few comments and no blank lines
The first few columns contain either blanks, a label, or a comment
Every comment starts in the first column
Every line of code is indented by a (mostly) consistent number of spaces with only one further level of indenting
There is unique content at the top and bottom of the file but there are a number of very similar lines in the middle
This block of similar lines is the only section of the code which is indented
Only one line near the end of the file contains a statement label

We can immediately tell this source code is fixed-format, probably F77 or F66. It's rather short, probably a single routine. There's some indenting but nothing that would indicate more than one level of nesting.

In Fortran, line labels specify a GOTO target, the terminating statement of a loop, or the reference number of a non-executable FORMAT statement. If this is F66, it probably contains only one loop if it has any; multiple loops may use a single labeled statement as their termination. What we know is the label is not on a simple CONTINUE statement which is the typical loop termination. It has the right shape for a FORMAT statement but we can't infer much more than that. We don't know what the labeled statement is, but it's definitely not a CONTINUE.

The uniform section in the middle of the file is possibly a table of data or a block of very similar I/O statements. Looking closer, it's probably not I/O: each line starts with a two-character word, much too short to contain READ or WRITE. It's long enough to contain a variable name or the statements IF, or DO. We can rule out DO since there's only one labeled statement to act as a loop terminator and we can't identify a corresponding number of lines that could contain END DO or ENDDO statements. I believe the only statement which can begin with a variable name is an assignment such as A = B + C so this block is most likely a stretch of conditional statements or assignments.

This seems like a simple linear routine with no obvious signs of convoluted GOTO logic or deeply-nested loops. This really restricts the type of painful constructs that might appear. The routine is also short which limits how many painful constructs might appear.

Elementary?

There's something just so about this analysis. It feels like a Sherlock Holmes tale with too many "obvious" inferences and details. We looked at the source code first so how many of those brilliant inferences are just post hoc rationalizations?

Further, is this sort of detailed inference any faster or better than just looking at the source code? Did the shape tell us anything we couldn't discover just by skimming the source text or using simple line count and pattern matching utilities? Skepticism is definitely warranted. Keeping this criticism in mind, we can move on to a more complex example.

Differential Analysis

Let's look at the shape of several longer routines. DES.F, HELP.F, INIT.F, and MOVE.F are all about the same length (120-130 lines), about five times the length of ADSCOR.F. We'll reduce the magnification so the images fit better on the screen. This has the added benefit of making it more difficult to cheat by counting pixels.

Here's the bitmap of DES.F:

HELP.F:

INIT.F:

and MOVE.F:

A new color has appeared: cornflower blue indicates continuation characters.

Instead of analyzing each image individually, identifying and explaining interesting features, let's take a more open-ended approach. Compare the set of images and think through the following questions:

How many routines are there in each file?
Which routines are most likely to have complex logic, for example loops, conditionals, and GOTOs?
Which produce the most diverse output? Hint: Look at how the FORMAT statement is represented in ADSCOR.F, both as source code and as a bitmap.
Which routines contain the most static data?
What is the balance between data and code in each routine?
Can you tell the difference between comments that provide documentation versus those that disable source code?
Can you see groups of similar statements? For example, can you identify large blocks of assignment or FORMAT statements?
Do the routines look as if they were written by the same person, many different people, or a team using a consistent code style?
Which routines seem most interesting? If you could look at only one routine in detail, which would you choose?

Now review the list of questions and ask how the answers color your view of how "legacy" a project is and what sort of refactorings may be needed for each routine. This is clearly procedural code; if you were converting it to object-oriented code, which routines suggest attributes and which suggest methods?

Finally, consider how long it took to answer these questions for each file. The Castlequest source code is distributed among 16 files; how long would it take to assess the whole codebase by viewing bitmaps versus skimming source files in an IDE or text editor? By comparison, the NASTRAN-95 project consists of almost 1900 separate source files distributed among 10 directories - would the graphical or the textual approach be more effective on a project of that size? Would either approach be effective at that scale?

Aside: Copypasta

Compare the bitmaps of HELP.F and INIT.F: did you notice the large block of code that appears to be duplicated in both files?

Your Own Half-Acre of Misery

Part of my motivation for revitalizing Castlequest was to discover new and useful questions to ask about legacy code and find creative ways of getting answers. You probably aren't refactoring legacy FORTRAN or complex text adventure games, so what good is this in general?

I believe there's value in stepping back from your code and asking these questions. It took a few hours over a day or two to write a tool to create very simple colorized bitmaps from Fortran source code. What do you think you'd learn about your own projects with this sort of analysis? Does your code or language have an identifiable shape? For as well as you know your language, what details can you identify just by looking at the shape of your source code?

Tomb of Horrors

Let's look at one last bitmap: MAIN.F, the heart and brains of Castlequest. Overall, the project contains roughly 3000 lines of combined source code and comments in total, and of this, two-thirds is concentrated in MAIN.F. The shape of the code mostly speaks for itself:

Due to the color scheme and image scale it's difficult to see but there are a whole lot of statement labels scattered throughout this routine. There are many loops and at least 650 GOTO statements in this single routine.

Every one of those GOTO statements was refactored away. Eliminating the last 10 required a great deal of effort and resulted in some architectural compromises that I'm still not comfortable with. Rather than being an exercise in diminishing returns, it highlighted where deeper object oriented analysis and reorganization is needed. But that's a story for another day.

In the next installment in the Castlequest series I'll map the flow of control in MAIN.F. There's much we can learn by qualitatively visualizing our code's logical complexity.

References and Credits

My limited understanding of practical firefighting comes from "Collapse of Burning Buildings: A Guide to Fireground Safety", 2nd edition by Deputy Chief Vincent Dunn, NYFD (ret.). It's a fascinating book with interesting criticisms of fire science as well as modern building construction techniques. For as often as software developers use the analogy of firefighting, the reality is that a fire chief that regularly orders crews into hopeless conflagrations with inadequate planning and support and no regard for their well-being is unlikely to keep their job. In the software industry, that level of pathological behavior often gets one promoted.

Halligan bar photo by Marcel Rogge - Own work, CC BY-SA 3.0

Revitalizing Castlequest, Part 2: NOW WITHOUT SHOUTING

arclight — Fri, 03 Sep 2021 21:56:20 +0000

In the previous installment, I discussed several motivations for embarking on this modernization effort. It's important to be honest about why you are changing a code, whether you're modernizing, rewriting, or even retiring software.

Shall we play a game?

I've been writing about Castlequest but I haven't really shown it in action:

$ .\cquest.exe
- Welcome to CASTLEQUEST!! Would you like instructions?

Y
0  You are in a remote castle somewhere in Eastern Europe.
   I will be your eyes and hands.  Direct me with words such
   as "LOOK", "TAKE", or "DROP".  To move, enter compass points
   (N,NE,E,SE,S,SW,W,NW), UP, or DOWN.  To get a list of what
   you are carrying, say "INVENTORY".  To save the current game
   so it can be finished later say "SAVE".  Say "RESTORE" as
   your first command to finish a game that had been saved.
0  The object of the game is to find the master of the castle
   and kill him, while accumulating as many treasures as possible.
   You get maximum points for depositing the treasures in the
   vault.  Notice that the descriptions of treasures have an
   exclamation point.  Be wary, as many dangers await you in
   in the castle.
0  Would you like more detailed instructions?

N
0  You are in a large, tarnished brass bed in an old, musty bedroom.
   cobwebs hang from the ceiling.  A few rays of light filter through
   the shutters.  There is a nightstand nearby with a single wooden
   drawer.  The door west creaks in the breeze.  A macabre portrait
   hangs to the left of an empty fireplace.
0  The shutters are closed.
0  There is a silver bullet here.

OPEN SHUTTERS
0  The shutter is open, but there are bars over the window.
0  Something on the ground outside is glistening brightly.

TAKE BULLET
0  OK

INVENTORY
0  You are carrying the following object:
      Silver bullet   

QUIT
0  You scored    0 out of  300 points.
0  You are a GREENHORN at this game!!

$

It's a basic text adventure with a verb-noun command form. It recognizes only a few words (80 verbs and 76 nouns) and not every combination makes sense. Even fewer combinations do anything useful. Still, Castlequest's vocabulary is reasonable for the game's size and era.

Two aspects of the game transcript are worth further discussion: why all my commands are in UPPER CASE and why there are all those zeroes at the beginning of a line.

The Case of the Upper Case

The upper case user input is maybe easiest to explain, and no, it's not that the cat stepped on caps-lock while I was distracted. F66 has almost no support for character data. The language has no string types and there are no functions for changing case or otherwise manipulating text. About all you can do is print text.

Here's a fragment of the input routine (creatively named INPUT, located in the file input.f):

C-----------------------------------------------------
      SUBROUTINE INPUT(ACTION)
      IMPLICIT INTEGER (A - Z)
      INTEGER ACTION(2), VERBS(2,80), NOUNS(2,76),
     2        BLANK, N, V, NVERBS /80/,
     3        NNOUNS /76/
C
      INTEGER NOUN(3), VERB(3)
C
      EQUIVALENCE (VERB(1), V), (NOUN(1), N)
C
      DATA VERBS  /4hATTA, 15, 4hBACK, 40, 4hBREA, 37, 4hBRIE, 61,
     2             4hCHOP, 37, 4hCLIM,  9, 4hCLOS, 28, 4hCROS, 43,
     3             4hD   , 10, 4hDEBU, 59, 4hDOWN, 10, 4hDRIN, 24,
     4             4hDROP, 12, 4hE   ,  3, 4hEAST,  3, 4hEAT , 23,
     5             4hENTE, 13, 4hEXIT, 14, 4hEXTI, 34, 4hFEED, 22,
     6             4hFILL, 49, 4hFIRE, 54, 4hFUCK, 19, 4hGOTO, 51,
     7             4hHELP, 50, 4hHINT, 50, 4hHONK, 45, 4hIN  , 13,
     8             4hINVE, 26, 4hJUMP, 25, 4hKILL, 16, 4hL   , 52,
     9             4hLEAV, 14, 4hLEFT, 52, 4hLIGH, 32, 4hLOAD, 18,
     X             4hLOCK, 29, 4hLONG, 60, 4hLOOK, 35, 4hMELT, 42,
     1             4hN   ,  1, 4hNE  ,  2, 4hNORT,  1, 4hNW  ,  8,
     2             4hOFF , 33, 4hON  , 31, 4hOPEN, 27, 4hOUT , 14,
     3             4hPOOF, 56, 4hPOUR, 39, 4hQUIT, 44, 4hR   , 53,
     4             4hREAD, 48, 4hREST, 58, 4hRIGH, 53, 4hS   ,  5,
     5             4hSAVE, 57, 4hSCOR, 36, 4hSE  ,  4, 4hSHOO, 54,
     6             4hSHOW, 20, 4hSOUT,  5, 4hSTAB, 21, 4hSUSP, 57,
     7             4hSW  ,  6, 4hSWIM, 41, 4hT   , 11, 4hTAKE, 11,
     8             4hTHRO, 17, 4hTIE , 46, 4hU   ,  9, 4hUNLO, 30,
     9             4hUNTI, 47, 4hUP  ,  9, 4hVERB, 60, 4hW   ,  7,
     X             4hWAKE, 55, 4hWATE, 38, 4hWAVE, 20, 4hWEST,  7/

The code takes advantage of the fact that integer variables are stored as 4 consecutive bytes, characters can be represented with one byte, and most F66 compilers did not check type. So all the variables that look like they're holding nouns and verbs are actually integers. Here the big list of verbs is represented in Hollerith format (named after Herman Hollerith, famed inventor of punchcard tabulating machines in the 1890s). Hollerith format consists of the number of characters in the string followed by the letter 'H' followed by the actual characters in the string. The first verb in the list, 4hATTA is just the four characters ATTA. Why not just put text between quotes like a normal person?

There aren't any quotes in standard F66.

Seriously.

This is the entire F66 character set:

ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890 =+-*/(),.$

Compiler vendors could support other characters as unofficial extensions to the language. For portability however, you're limited to those 47 characters. So per the language standard the text ATTA should be written as 4HATTA. The upshot is all the game commands are upper case essentially because the language isn't guaranteed to support lower case and there's no good way to normalize text case in F66.

Zeroes for Heroes

Remember the gameplay from before? With all the leading zeroes sprinkled through the text? This?

- Welcome to CASTLEQUEST!! Would you like instructions?

Y
0  You are in a remote castle somewhere in Eastern Europe.
   I will be your eyes and hands.  Direct me with words such
   as "LOOK", "TAKE", or "DROP".  To move, enter compass points

The first character on each line is an ASA carriage control code used to format text sent to a (weird, ancient) printer. ' ' (a space) is single-space, '0' is double-space, '-' is triple-space, '+' is overstrike (zero-space?), and '1' is form-feed. This is how the original gameplay looks when run through an ASA format converter:

$ .\cquest.exe | .\asa.ex
 Welcome to CASTLEQUEST!! Would you like instructions?
Y


  You are in a remote castle somewhere in Eastern Europe.
  I will be your eyes and hands.  Direct me with words such
  as "LOOK", "TAKE", or "DROP".  To move, enter compass points
  (N,NE,E,SE,S,SW,W,NW), UP, or DOWN.  To get a list of what
  you are carrying, say "INVENTORY".  To save the current game
  so it can be finished later say "SAVE".  Say "RESTORE" as
  your first command to finish a game that had been saved.

  The object of the game is to find the master of the castle
  and kill him, while accumulating as many treasures as possible.
  You get maximum points for depositing the treasures in the
  vault.  Notice that the descriptions of treasures have an
  exclamation point.  Be wary, as many dangers await you in
  in the castle.

  Would you like more detailed instructions?
N


  You are in a large, tarnished brass bed in an old, musty bedroom.
  cobwebs hang from the ceiling.  A few rays of light filter through
  the shutters.  There is a nightstand nearby with a single wooden
  drawer.  The door west creaks in the breeze.  A macabre portrait
  hangs to the left of an empty fireplace.

  The shutters are closed.

  There is a silver bullet here.
OPEN SHUTTERS


  The shutter is open, but there are bars over the window.

  Something on the ground outside is glistening brightly.
TAKE BULLET


  OK
INVENTORY


  You are carrying the following object:
     Silver bullet
QUIT


  You scored    0 out of  300 points.

  You are a GREENHORN at this game!!

$

Much better but still not great. But that's what you get with a language that dates to the early 60s. Escaped notation such as "\n" wouldn't be invented until 1972 with C and wouldn't be a de facto standard until much later.

Why Do We Care?

So that's the explanation for SHOUTED COMMANDS and the Mystery Zeroes in the original game output.

Why does this matter? Two reasons: user experience and testing. The game is a lot less fun to play IF YOU HAVE TO SHOUT ALL YOUR COMMANDS. Recognizing commands in upper case only is authentic and there's an argument to be made for preserving that behavior. My counter-argument is that it doesn't add anything to game play, it strains the eyes, and the caps-lock key is stupid. When modernizing Castlequest, I made it a top priority to change the game to accept lower case.

This also leads to issues when testing. In its original form, Castlequest can only be tested interactively. The game logic is tangled up in an immense monolithic main program. By definition, unit testing only works on discrete program units, not the whole code at once -- that's integral testing. I did all the coding and testing so I wound up playing a lot of Castlequest.

So. Much. Castlequest.

To preserve my eyesight and my remaining sanity, I rewrote the input routines to ignore case. Replacing the long-deprecated Hollerith format with actual quotes was next, mainly because it was an easy change. Conversely, one of my very last changes was making ASA carriage control optional. That change was complex and miserable even after cleaning up the rest of the code.

Beyond that, I made very few changes to the user experience. All the original typos are preserved; the game just crashes less and is easier on the eyes. But the innards of the code? Very little was left untouched.

If you really want that authentic Castlequest experience, it's still in there. If you just want to play the game and find out what's in the drawer of the nightstand without fiddling about with asa, you can do that too. NOW WITHOUT SHOUTING.

Revitalizing Castlequest, Part 1: Museums and Garages

arclight — Fri, 03 Sep 2021 20:07:14 +0000

In the previous installment, I gave a brief overview of my eight week effort to convert the 1979 text adventure Castlequest from FORTRAN 66 to Fortran 2018.

A big question: "Why?"

What’s My Motivation?

My teen years were spent playing the text adventures that came in the wake of Castlequest, both Infocom classics such as Zork to BASIC programs you had to type in yourself from a magazine or library book. I won't lie - nostalgia is part of my motivation but there's more to it than that. If I just wanted to play the game, it is already in a working playable state. Similarly, if I wanted to study the code as if it was a museum piece, the original 1981 code is easily available in PDF form. Neither is a reason to modernize the code.

Aside: "FORTRAN" was spelled in all caps until the 1990 revision
when the name was officially changed to "Fortran". Typically
"FORTRAN" refers to the revisions I, II, IV, 66, and 77 and
"Fortran" refers to revisions made in 1990, 1995, 2003, 2008,
and 2018. The former set is currently considered
'legacy FORTRAN' and the latter 'Modern Fortran'.

To avoid eye strain and/or hearing loss, the 1966 and 1977
revisions of the language will be abbreviated "F66" and "F77"
respectively.

Arthur O'Dwyer (introduced last episode) went through no small amount of difficulty trying to build and run the game after forty years without maintenance. I want Castlequest to be playable forty years from now, preferably with less pain.

There is a problem, however. Well, problems. I will cover interesting problems in detail later, but the major problem is that the code contains a number of F66 features which have been deprecated and deleted in Fortran 2018. The next time the code fails to compile it will be even more difficult to recover and there will be fewer people who understand F66 and its idioms well enough to recover it.

It's not just that the implementation language is long obsolete. The design of the code is alien to software developers who have spent their careers using object-oriented languages such as C++, Java, Python, etc. Castlequest's design and implementation don't affect gameplay so, from the player's perspective, they don't matter. What the program does is far more important than how it does it.

The game is not the code.

Museums and Garages

Arthur and I have very different philosophies regarding Castlequest's source code. He's acting as a museum - acquiring artifacts, preserving them, and presenting them for display and study. With Castlequest, his goal is to keep the source code and gameplay as close as possible to the 1981 version while making the game playable on modern systems.

In contrast, I am acting as a garage. I bring a car into the bay, open the hood and assess its condition, then make it as safe, reliable, efficient, and maintainable as I can within the owner's constraints. At bare minimum it will be clean, road-legal, and will start, drive, and stop reliably. It may or may not have a pine tree air freshener hanging from the mirror but it will definitely have New Car Smell.

New Car Smell

My goals with Castlequest are to modernize the code to meet current language standards, restructure it to simplify maintenance, and clarify its internal operation should someone wish to implement the game in a new language. I want to preserve the original story and mechanics while improving the user experience on modern systems. I'm willing to sacrifice authenticity for playability and long-term maintainability.

Arthur and I have very different approaches but they're both completely valid. We don't have to make an either-or choice between museums and garages. There's space enough for archivists and mechanics and plenty of others.

You find one in every car -- you'll see.

Pine tree air freshener photo courtesy of Pål Berge via Wikimedia Commons

Revitalizing Castlequest, Part 0: A Rumor of Treasure

arclight — Fri, 03 Sep 2021 16:53:07 +0000

Back in the Days of Old when college students hung out in dank computer labs wasting time and avoiding the sun, there once was a game called Castlequest. Although widely believed to be forever lost, a determined adventurer by the name of Arthur O'Dwyer sought out its authors which led to the game's rediscovery deep within the catacombs of the US Copyright Office. With no small effort, Arthur manually transcribed the scanned source code to its original machine-readable format and through various magicks brought it back to life.

Ok, so he used a Fortran compiler.

Castlequest was originally written in FORTRAN 66, a language usually associated with numerical analysis, punchcards, and overwhelming malaise. F66 is not a particularly good language for writing games, but Castlequest was written in 1979. FORTRAN 77 had only been formalized the year before, so - all things considered - the decision to use FORTRAN 66 was completely reasonable at that time.

Arthur published the recovered Castlequest source code in March of 2021 and I learned of it in April. By mid-June I had converted the original rat's nest of FORTRAN 66 to Fortran 2018 - object-oriented, fully documented, with unit tests, build automation, and installation packages for MacOS, Windows, and Linux. From a user's perspective, Castlequest still plays the same but the internals are wildly different.

Castlequest is an interesting program with some history behind it. It's also a worst-case scenario of tangled logic and unstructured, unmaintained code, the sort that Dijkstra warned us about. But beyond that, it's a vehicle for applying modern software development techniques and tools such as build automation, continuous integration, test-driven-development (TDD), and more. Finally, it demonstrates the resilience of 40-year-old software written in a 55-year-old dialect of a 65-year-old language, one that's still widely used for large-scale high performance numerical computing.

I have been meaning to write about the Castlequest modernization project while the experience is still fresh: motivation, goals, processes and technologies applied, lessons learned, etc. Rarely does one have the time or motivation to draft an extended post mortem analysis of a software recovery project; my question is whether there's an audience for reading it. Drop me a comment if this tale sounds like it's worth continuing and what interests you the most about it.

In closing, much credit goes to Arthur O'Dwyer for his persistent detective work and initial code recovery. That was a lot of retyping...

Note: This article was originally published (by me) on LinkedIn

Balancing Clarity, Elegance, and Risk in Regular Expressions

arclight — Mon, 16 Aug 2021 20:57:53 +0000

Recently a colleague posted a security incident report about a single-character error in a regular expression. It got me thinking about the techniques I have used to reduce errors in my regular expressions and how I could use this incident as a guide to applying these techniques. In the process, I found this is a case where elegance works against clarity; sometimes clarity needs to win especially in security or safety applications.

Disclaimer

Before I start, I want to make one thing clear: regular expressions are complex and brittle. Everyone makes this sort of mistake so do not interpret this as a personal criticism of any individual, any group, any language, or any project. I am not second-guessing design decisions. Nobody cares about how I would have written the original code. Even I don't.

Very simply, the code is what it is; my goal is to see what we can learn from it and what a team can do to reduce the risk posed by regular expressions. This is not an exhaustive tutorial. The examples below are meant to illustrate techniques for writing safer, more reviewable code. That's all.

The Incident

Daniel Cuthbert (@dcuthbert) writes:

Nice little bug this showing how not properly escaping a full stop
(.) can lead to code execution The bug writeup is brilliant too
https://github.com/pi-hole/AdminLTE/security/advisories/GHSA-5cm9-6p3m-v259

`tl;dr`

The one line technical summary from @SchneiderSec gets right to the point:

The issue lies in the fact that one of the periods is not escaped
allowing any character to be used in it's place.

A Few Words About Regular Expressions

Regular expressions are extremely powerful tools
Regular expression notation is notoriously difficult to read
Regular expressions are remarkably brittle and can fail in unexpected and catastrophic ways

When we use them (or any construct, really) we are balancing clarity, elegance, and risk.

Regular expressions are not an always/never tool. There are as many good reasons to use them as to avoid them. Here we are analyzing short strings which is the dominant use case for regular expressions.

The Code

Here is code we are worried about:

function validDomainWildcard($domain_name)
{
    // There has to be either no or at most one "*" at the beginning of a line
    $validChars = preg_match("/^((\*.)?[_a-z\d](-*[_a-z\d])*)(\.([_a-z\d](-*[a-z\d])*))*(\.([_a-z\d])*)*$/i", $domain_name);
    $lengthCheck = preg_match("/^.{1,253}$/", $domain_name);
    $labelLengthCheck = preg_match("/^[^\.]{1,63}(\.[^\.]{1,63})*$/", $domain_name);
    return ( $validChars && $lengthCheck && $labelLengthCheck ); //length of each label
}

This function checks if a string matches three search patterns. The function returns True if all three patterns match; if any pattern doesn't match, it returns False.

Quick Impressions and Setting Focus

The problem is that there is a simple typo which drastically changes the function's behavior. It's not easy to see either as an author or reviewer. Otherwise there's nothing fundamentally wrong with this code.

Parts of this routine are extremely simple and parts are very complex. The simple parts are really simple - three assignments and a logical expression. The complex parts are the regexes so that is where we will focus our analytical efforts.

So what can we do to limit the risks that regexes pose?

Spacing and Documentation

Let's start by addressing clarity - how can we make regexes more readable?

We can:

add whitespace
decompose complex expressions into meaningful subexpressions
add comments to explain the intent of subexpressions

In some regex languages (for example PCRE and those embedded in Perl, Python, and PHP) you can disable the significance of carriage returns and other whitespace and allow embedded comments. Perl, Python, and PHP all support the 'x' option. In PHP, the 'x' option can also be enabled using the PCRE_EXTENDED modifier. Check your languagefor details.

Note that comments embedded in a regex are subject to additional escaping rules; we'll keep our documentation simple. There is already enough punctuation; let's try not to add any more.

But say our regex language doesn't support embedded comments. Can we still use this method?

Sure! Even without strange regex option flags, we can

decompose the pattern string into smaller substrings,
document them, and
compose the full pattern string from parts.

This is straightforward and should work in any language so you may want to try this tactic first.

When Should We Apply This?

There is no hard and fast rule but if a regex has more than 2-3 paren'd groups or is more than half a line, consider breaking it up and commenting it.

PHP Example

This is an example of adding whitespace and comments to the $validChars regex. The result is still rather long and confusing, but the structure and intent are much more apparent. Repetitive groups and character classes stand out and we can see inconsistencies in patterns. As a reviewer, I should at least mark these down and ask the author for clarification of any suspicious constructs.

Side note: My job as a reviewer is to ask for clarification, not to rewrite the code or redesign the application. These examples are more intended for code authors than reviewers.

We might want to break out groups 1, 4, and 6 and explain what we are looking for but this is a start.

$validChars = preg_match(
    "/^                         # Start of string,
      (                         # Open group 1
        (\*.)?           # ERROR: Optional '*.' literal (domain wildcard) as group 2
        [_a-z\d]                # One letter, digit, or underscore
        (                       # Start group 3
          -*                    # Any number of hyphens
          [_a-z\d]              # One letter, digit, or underscore
        )*                      # Any number of group 3 matches
      )                         # Close group 1; group 1 should match once
      (                         # Open group 4
        \.                      # Literal '.'
        (                       # Open group 5
          [_a-z\d]              # One letter, digit, or underscore
          (                     # Open group 6
            -*                  # Any number of hyphens
            [a-z\d]             # One letter or digit -- Q: Should this have an underscore?
          )*                    # Any number of group 6 matches
        )                       # Close group 5
      )*                        # Close group 4; any number of group 4 matches
      (                         # Open group 6
        \.                      # Literal '.'
        (                       # Open group 7
          [_a-z\d]              # One letter, digit, or underscore
        )*                      # Close group 7; any number of group 7 matches
                                # -- Q: Group 7 can be empty; is that intended?
      )*                        # Close group 6; any number of group 6
      $/ix", $domain_name);     # End of string; case-insensitive,

If you have ever spent time programming LISP or Scheme, you might think this looks very similar to those languages. That is no accident. Regular expression notation is a low-level functional language. It just isn't as obvious when it's all crammed onto a single line.

Backslashitis, Delimiters, and Character Classes

Another clarity-killer is excessive escaping or as it is more commonly known, Backslashitis. Some common entities and patterns require backslashes such as tab (\t), digit (\d), and word boundary (\b). Some characters require escaping because they match regex operators.

Basic examples:

. matches any character,
\. matches a literal .,
* is the Kleene closure which modifies the pattern before it (pattern matches zero or more times),
\* matches a literal *.

Parens are often used for embedding regex options or for capturing (grouping) parts of matches. This isn't consistent among regex languages so sometimes $ and $ are used for grouping, other times () defines a group.

Still other characters need to be escaped because they match pattern delimiters, historically /. For this reason Backslashitis is especially painful in web and filesystem code. The use of backslashes as path separators on Windows adds another layer of badness but it is only slightly less bad everywhere else.

Alternate Delimiters

Perl worked around delimiter collision by allowing letting users set alternate pattern delimiters; for example

/my\/path/

can be replaced with

m#my/path#

The leading m stands for match.

Python and PHP use normal strings to hold patterns so there is some overlap between escaped characters in both strings and regexes, e.g. \t for horizontal tab. You may not remove all escaping backslashes by changing delimiters but it is an easy way to clarify slash-heavy regexes.

Character Classes

If you can’t change delimiters, you can use character classes to reduce escaping. [.] can often be used for as \. and [*] for \* so the original example pattern

(\*\.)?

could be rephrased as

([*][.])?

That’s still not great; it looks like ASCII art of a confused robot. It is definitely clearer and it makes some problems more obvious.

Note that typos in character class notation have a very different failure mode than typos in backslash-escaped characters.

Accidentally omitting [ or ] will probably cause the regex to fail to compile. It won’t silently change the meaning as drastically as dropping \ from \. or \* will.

Named Entities

But what about entities like \d or \b which don't correspond to a single character? Often regex languages give these patterns explicit names.

\d is shorthand for [0-9]; in POSIX bracket expression notation it can be written as [:digit:]. [A-Za-z] can be written as [:alpha:]. [:alnum:] is equivalent to [A-Za-z0-9], and [A-Za-z0-9_] can be written as \w or [:word:].

In some regex dialects, \b matches a word boundary, a zero-length position before or after a pattern if it is outside a character class, but a backspace if inside a character class.

The point is that sometimes you are stuck using an escaped entity for which there is no good backslash-free substitute. That's okay; just rephrasing common patterns can improve clarity.

When Should We Apply This?

If there are many escaped slashes in your pattern, see if you can change the pattern delimiters to something other than /.

If you use the same character class more than 2-3 times in a pattern, try to substitute a POSIX bracketed expression or define it as a string, document it, and compose the main regex from these subpatterns.

Keep a cheat sheet on your language's regex syntax handy; the meaning of entities like \s (whitespace) varies among languages. You don't have to memorize all this weirdness; be safe and look it up. Life's too short to spend it debugging regexes.

PHP Example

Let's revisit our $validChars regex. PHP supports POSIX expressions so we can clarify our pattern by using named entities. Recall the named patterns we found earlier:

single digits can be matched with [0-9], \d, or [:digit:],
single letters can be matched with [A-Za-z] or [:alpha:],
a single digit or letter is called an alphanumeric character and can be matched with [A-Za-z0-9], and
'word' characters are defined as [A-Za-z0-9_] and can be matched using \w or [:word:]

Note that [[:alnum:]_] also matches word characters; please do not do this.

The $validChars regex made heavy use of [_a-z\d] and [a-z\d]. We can replace these with [:word:] and [:alnum:] respectively. This is possible because the /i flag at the end of the pattern makes it case-insensitive so [A-Z] is treated just like [a-z].

Also, let's replace the problematic (\*.)? construct with our confused robot regex. Our / delimiter is fine as-is; we would probably want to change it if we were matching paths or URLs.

We could also replace \. with [.]. It is not a big improvement in readability but it is cheap risk reduction so let's swap that in too. We can always change it back if it looks stupid.

Substitution gives us:

$validChars = preg_match(
    "/^                 # Start of string
    (                   # Open group 1
      ([*][.])?         # FIXED: Optional '*.' literal (domain wildcard) as group 2
      [:word:]          # One letter, digit, or underscore
      (                 # Start group 3
        -*              # Any number of hyphens
        [:word:]        # One letter, digit, or underscore
      )*                # Any number of group 3 matches
    )                   # Close group 1; group 1 should match once
    (                   # Open group 4
      [.]               # Literal '.'
      (                 # Open group 5
        [:word:]        # One letter, digit, or underscore
        (               # Open group 6
          -*            # Any number of hyphens
          [:alnum:]     # One letter or digit -- Q: Should this be [:word:]?
        )*              # Any number of group 6 matches
      )                 # Close group 5
    )*                  # Close group 4; any number of group 4 matches
    (                   # Open group 6
      [.]               # Literal '.'
      (                 # Open group 7
        [:word:]        # One letter, digit, or underscore
      )*                # Close group 7; any number of group 7 matches
                        # -- Q: Group 7 can be empty; is that intended?
    )*                  # Close group 6; any number of group 6
    $/ix",              $domain_name);     # End of string; case-insensitive,

We completely eliminated backslashes and made the distinction between [_a-z\d] and [a-z\d] much more obvious. Consistent use of [.] makes domain name separators look a little strange if we are used to \. but the domain wildcard pattern is safer. It is much easier to see the difference between

([*][.])? and ([*].)?

versus

(\*\.)? and (\*.)?

You have to drop both '[' and ']' from around '.' to cause the bug in the original code. Dropping just one would cause the regex to fail to compile and give us a chance to find the original error.

At this point we are mostly left with grouping characters (parens) and have possibly identified a larger subpattern we may want to extract, document, and test separately, i.e. [:word:](-*[:word:])*

We also see some breaks in symmetry; domain parts are variously matched by

[:word:](-*[:word:])*,
[:word:](-*[:alnum:])*, and
([:word:])*

The reviewer should ask if these differences are intended; it isn't clear from the context or documentation.

Testing

This is a deep and complex topic so I will keep it brief.

Build test cases that are expected to fail. This may be difficult to remember because unit testing is often a constructive affirmation process used to demonstrate expected behavior with expected input. Compare this against adversarial security testing which actively seeks to exploit a function by throwing mountains of bad input at it.

If you can test subpatterns, do so. It is easier to compose test cases for simple patterns than complex ones and you will need fewer tests overall.

Remember that unit tests are a developer convenience, not a substitute for verification and validation (V & V), acceptance tests, integral tests, regression tests, etc. In legacy code, the cost of backfitting unit tests is often prohibitive but you can add unit tests to new code and remediate the rest as time permits.

Is There a Simpler or Clearer Way to Do This?

I programmed Perl for over a decade; I think regexes are awesome. Also, I avoid them if possible because as we see here, regex errors are subtle, easy to make, and difficult to find.

What are some simpler replacements?

Direct Checks

One common regex is /^X/ (that is, does this string start with the specific character X?). It is simple, clear, and probably optimized in your language’s regex engine.

But why not directly compare the first character of the string to X?

Which is easier to explain, this?

$target = 'Xena';
if (preg_match('/^X/', $target)) {
    # Do some warrior princess things
}

Or this?

$target = 'Xena';
if ($target[0] === 'X') {
    # Do some warrior princess things
}

The direct check has several advantages:

it does not rely on cryptic regular expression notation,
direct checks often use fewer resources (memory, time) than regexes, and
direct checks fail less spectacularly than regexes

The regex has two advantages:

it is more flexible, and
it does not rely on the correct number of '=' signs to work correctly

Question: is this limited to PHP or are there other languages where this is an issue?

If we want to make this a case-insensitive test or search for multiple characters, the direct comparison method gets complex and ugly fast. It is easy enough to convert the direct check to a regex later if we need to.

Note that in PHP there is a risk of the conditional changing meaning if we leave out one or more = signs in the direct check. The consequences of using == instead of === may be small but the consequences of using = instead of == can be massive.

A simple way to guard against this is to swap the positions of the constant and the variable terms in the test, such as

$target = 'Xena';
if ('X' === $target[0]) {
    # Do some warrior princess things
}

It looks strange but it has the same meaning. The only difference is that if there is a typo in the conditional operator, the code will crash rather than silently making an assignment and continuing execution.

Simple Length Checks

The original example code uses two regexes to check the length of the domain name and its parts:

$lengthCheck = preg_match("/^.{1,253}$/", $domain_name);
$labelLengthCheck = preg_match("/^[^\.]{1,63}(\.[^\.]{1,63})*$/", $domain_name);

Let's focus on the first one. Most languages have a string length function. For example, string length is found in PHP using strlen(), Python uses len(), etc.

The regex here seems like seems like overkill. As a reviewer I have to ask if there is a reason string length checks are done with regexes instead of strlen()? There might be; I don't know. That's why I'm asking.

We can easily replace

$lengthCheck = preg_match("/^.{1,253}$/", $domain_name);

with

$domainLength = strlen($domain_name);
$lengthCheck = (($domainLength >= 1) && ($domainLength <= 253));

This can be clarified further if we define a utility function such as

**
 * Determines if $number is between $min and $max
 *
 * @param  integer  $number     The number to test
 * @param  integer  $min        The minimum value in the range
 * @param  integer  $max        The maximum value in the range
 * @param  boolean  $inclusive  Whether the range should be inclusive or not
 * @return boolean              Whether the number was in the range
 */
function in_range($number, $min, $max, $inclusive = FALSE)
{
    if (is_int($number) && is_int($min) && is_int($max))
    {
        return $inclusive
            ? ($number >= $min && $number <= $max)
            : ($number > $min && $number < $max) ;
    }

    return FALSE;
}

(credit: Luke at Stack Overflow https://stackoverflow.com/a/35272658 )

We can reduce the check down to a single line with:

$lengthCheck = in_range(strlen($domain_name), 1, 253, TRUE);

This change is not critical but it is an option.

Complex Length Checks

The second length check is more complex, checking if all the domain name components have a length between 1 and 63 inclusive.

$labelLengthCheck = preg_match("/^[^\.]{1,63}(\.[^\.]{1,63})*$/", $domain_name);

It would take some effort to replace this regex with elemental string functions and probably will not make it any clearer. What we can do is break up the regex and document it.

Maybe do this:

$labelLengthCheck = preg_match(
    "/^              # Starts with
    [^\.]{1,63}      # 1-63 non-dot chars
    (                # any number of groups
        \.           # containing a dot
        [^\.]{1,63}  # followed by 1-63 non-dot chars
    )*               # until the end of the string
    $/x", $domain_name);

Or this

$domain_part = '[^\.]{1,63}';
$labelLengthPattern = "/^${domain_part}(\.${domain_part})*$/";

$domain_name = 'reasonable.example.com';
$labelLengthCheck = preg_match($labelLengthPattern, $domain_name);

Or alternately, since we are already detecting and grouping domain parts in the $validChars regex, we could apply our length checks to selected groups. We might want to use non-capturing subpatterns to restrict the captured matches to just the full domain parts. Non-capturing subpatterns are inside parens just like groups but the opening paren is followed by '?:'. If we wanted our confused robot regex to be non-capturing, we
could change it from:

([*][.])?

(?:[*][.])?

Our Confused Robot Regex looks even more confused. The Very Confused Robot Regex.

The optional third argument to preg_match is a list of captured groups. We would really like to capture everything that matches groups 1, 4, and 6 and check if all those matches have 1-63 characters. Note that groups 4 and 6 may match multiple times and we need to check each one. This also leads to weird numbering in the capture array; here it doesn't matter since we have to check all the matched domain parts.

$validChars = preg_match(
    "/^                 # Start of string
    (                   # Open group 1
                        # Next line is non-capturing pattern AAA
      (?:[*][.])?       # FIXED: Optional '*.' literal (domain wildcard)
      [:word:]          # One letter, digit, or underscore
      (?:               # Open non-capturing pattern BBB
        -*              # Any number of hyphens
        [:word:]        # One letter, digit, or underscore
      )*                # Any number of group BBB matches
    )                   # Close group 1; group 1 should match once
    (?:                 # Open non-capturing group CCC
      [.]               # Literal '.'
      (                 # Open capturing group 2
        (?:             # Open non-capturing pattern DDD
          [:word:]      # One letter, digit, or underscore
          (?:           # Open non-capturing pattern EEE
            -*          # Any number of hyphens
            [:alnum:]   # One letter or digit -- Q: Should this be [:word:]?
          )*            # Close group EEE. Any number of group EEE matches
        )               # Close group DDD
      )                 # Close group 2; any number of group 2 matches captured
    )*                  # Close group CCC
    (?:                 # Open non-capturing pattern FFF
      [.]               # Literal '.'
      (                 # Open capturing group 3
        (?:             # Non-capturing group GGG
          [:word:]      # One letter, digit, or underscore
        )*              # Close non-capturing group GGG;
      )                 # Close group 3; There may be any number of group 3 matches
                        # -- Q: Group GGG can be empty; is that intended?
                        # -- Q: Can domain part end in a dot
    )*                  # Close non-capturing group FFF
    $/ix",              $domain_name, $domain_parts); # End of string; case-insensitive

Let's edit out unnecessary non-capturing groups and compress some of the vertical space:

$validChars = preg_match(
    "/^                   # Start of string
    (                     # Open group 1
      (?:[*][.])?         # FIXED: Optional '*.' literal (domain wildcard)
      [:word:]            # One letter, digit, or underscore
      (?:-*[:word:])*     # Optional hyphen then a word character (0 or more)
    )                     # Close group 1; group 1 should match once. Captured.
    (?:                   # Open non-capturing group AAA
      [.]                 # Literal '.'
      (                   # Open capturing group 2
        [:word:]          # One letter, digit, or underscore
        (?:-*[:alnum:])*  # Optional hyphen then an alphanumeric character (0 or more)
      )                   # Close group 2; any number of group 2 matches captured
    )*                    # Close group AAA
    (?:                   # Open non-capturing pattern BBB
      [.]                 # Literal '.'
      ([:word:]*)         # Group 3 captures any number of word characters
                          # -- Q: Group 3 can be empty; is that intended?
                          # -- Q: Can domain part end in a dot
    )*                    # Close non-capturing group BBB
    $/ix",                $domain_name, $domain_parts); # End of string; case-insensitive

// Initially set $labelLengthCheck = 1 (TRUE)
// Iterate over domain parts; if one is too short
// or too long, set $labelLengthCheck = 0 (FALSE) and exit loop
$labelLengthCheck = 1
foreach ($domain_parts as $part) {
    $partLength = strlen($part)
    if (! in_range($partLength, 1, 63, TRUE)) {
        $labelLengthCheck = 0
        break;
    }
}

I'm not sure this is any clearer than the original $labelLengthCheck regex; someone with more recent PHP experience could clean this further. Again, as a reviewer my job is to point out that the $ValidChars regex already returns enough information for free that we can set $labelLengthCheck without using an additional regex. It is not my goal to rewrite the code, just to ask if errors are more obvious or more catastrophic in the regex version or the strlen() version.

The $validChars regex has been simplified in some ways, made more complex in others. There is a legibility cost incurred by using non-capturing patterns.

When Do We Apply This?

When you see a short regex, ask if a regex is really necessary.

Look for clearer alternatives with safer and more obvious failure modes.

Elegance Does Not Guarantee Clarity

Let’s look at the original function again (complete with error), but rearrange it so regexes are stored in strings

function validDomainWildcard($domain_name)
{
    // There has to be either no or at most one "*" at the beginning of a line
    $validCharsPattern       = "/^((\*.)?[_a-z\d](-*[_a-z\d])*)"
                             . "(\.([_a-z\d](-*[a-z\d])*))*"
                             . "(\.([_a-z\d])*)*$/i";
    $lengthCheckPattern      = "/^.{1,253}$/";
    $labelLengthCheckPattern = "/^[^\.]{1,63}(\.[^\.]{1,63})*$/";

    $validChars       = preg_match($validCharsPattern,       $domain_name);
    $lengthCheck      = preg_match($lengthCheckPattern,      $domain_name);
    $labelLengthCheck = preg_match($labelLengthCheckPattern, $domain_name);

    return ( $validChars && $lengthCheck && $labelLengthCheck ); //length of each label
}

Using three regex checks in a row like this has a nice symmetry; a column each for results, regex patterns and targets. At a high level, it is very clear what is intended. At a low level it’s difficult to see if it is implemented correctly.

We can rephrase it as

function in_range($number, $min, $max, $inclusive = FALSE)
{
    if (is_int($number) && is_int($min) && is_int($max))
    {
        return $inclusive
            ? ($number >= $min && $number <= $max)
            : ($number > $min && $number < $max) ;
    }

    return FALSE;
}

function validDomainWildcard($domain_name)
{
    // There has to be either no or at most one "*" at the beginning of a line
    $validChars = preg_match(
        "/^                   # Start of string
        (                     # Open group 1
          (?:[*][.])?         # FIXED: Optional '*.' literal (domain wildcard)
          [:word:]            # One letter, digit, or underscore
          (?:-*[:word:])*     # Optional hyphen then a word character (0 or more)
        )                     # Close group 1; group 1 should match once. Captured.
        (?:                   # Open non-capturing group AAA
          [.]                 # Literal '.'
          (                   # Open capturing group 2
            [:word:]          # One letter, digit, or underscore
            (?:-*[:alnum:])*  # Optional hyphen then an alphanumeric character (0 or more)
          )                   # Close group 2; any number of group 2 matches captured
        )*                    # Close group AAA
        (?:                   # Open non-capturing pattern BBB
          [.]                 # Literal '.'
          ([:word:]*)         # Group 3 captures any number of word characters
                              # -- Q: Group 3 can be empty; is that intended?
                              # -- Q: Can domain part end in a dot
        )*                    # Close non-capturing group BBB
        $/ix",                $domain_name, $domain_parts); # End of string; case-insensitive

    // Check overall domain length is from 1 to 253 characters
    $lengthCheck = in_range(strlen($domain_name), 1, 253, TRUE)

    // Iterate over domain parts; if one is too short
    // or too long, set $labelLengthCheck = 0 (FALSE) and exit loop
    foreach ($domain_parts as $part) {
        $labelLengthCheck = in_range(strlen($part), 1, 63, TRUE)
        if (! $labelLengthCheck)
            break;
        }
    }

    // If any check fails, return false (0)
    return ( $validChars && $lengthCheck && $labelLengthCheck );
}

It is longer and uglier; we lost the clean symmetry and brevity of the original. We also added another function which needs testing, documentation, etc. It's less elegant but the complex regex is documented so overall it's easier to review.

Elegance isn’t bad, it just may not always serve us.

Important code like a security check requires extra clarity; failure modes are serious. Regexes are difficult to read and they are key to maintaining security at this point in the code. And here, clarity at low level is more important than at high level because errors are more likely to occur at the low level of regexes.

You Are Probably Misusing Use Peer Review

Find a colleague not on the project who can behave like a professional, have them read over your code and write down any technical questions they have. Read through their questions and resolve each one by changing the code or adding documentation to make it clearer. That's it.

Any mentoring that happens in this process is incidental. A technical review is for finding errors or weaknesses and making sure the code is clear enough that any member of the team can read and debug it.

Whatever you do, DO NOT sit around a table with a half-dozen team members going line-by-line through someone's code. This wastes a lot of time and can easily turn into a developer-beating party. This is neither productive nor effective and it can turn ugly and unprofessional before anyone realizes it's happening.

Aside: I worked in the nuclear industry under a formal independent technical review process. Every engineer was assigned as a technical reviewer on their peers' work; it was a normal, integral part of our work process whether we were documenting engineering calculations or writing code. I found errors in senior engineers' work. People found errors in mine. Errors happen; it is a team effort to sniff them out before a report is issued or code is released. Peer technical review is one aspect of nuclear work I miss when in other environments. If I could, I wouldn't release important code without it.

You don't have to be working on safety-critical systems to get the benefit of peer technical review. Peer review does not have to be a nitpicky ritual beating; it shouldn't be. If it is, something is very, very wrong with your process or work culture.

The three rules for technical review: be professional, be thorough, and be fast -- in that order.

Conclusion

Regular expressions are very powerful tools but they can be difficult to read. They fail in subtle, unexpected, and spectacular ways.

It is impossible to keep errors out of your regular expressions but there are techniques to make errors more obvious in review and less catastrophic in production. Some are easier to apply than others but none of them require you to become some regex wizard overnight. You may not need every one on every project but it helps to know what techniques are available to give you and your team the best chance of success.

How much do you trust your toolchain and why?

arclight — Mon, 30 Sep 2019 03:12:31 +0000

Whether you use a compiled or interpreted language or something in-between, how do you know your compiler/interpreter faithfully and correctly implements the language?

How much undefined or vendor/processor-dependent behavior is in your language specification? Meaning, how complete is your language's specification?

Do you evaluate your toolchain for completeness and correctness? Moreso than just having a list of open issues, how much can you trust that the language you use is consistently implementable?

Is this the first time you've ever thought about how much you can trust your toolchain?