Bounding walks by crossings, and flagging what was cut

Read first: Answering every walk once

To say where a dynamic XCTL goes, the analysis walks its target's bytes backwards, crossing into whichever program they came from. Where programs hand areas round in a ring, those walks pile up: on a large CICS corpus, one cyclic group grew past a million places, though earlier fixes had made each walk cheap.

PROGT's XCTL goes to PROGM, a literal in PROGT, or to PROGQ, which PROGC stamped into the commarea two programs back. Allow one crossing (--max-hops 1) and the walk keeps PROGM, stops short of PROGC, and marks the answer hop-limit; allow two and it finds both, unmarked. Stop after N crossings, keep what was found, mark what was cut.

A crossing is a step of the walk that leaves one program for another. The COBOL/CICS primer has the rest of the vocabulary.

The example

Three programs in a chain, and where each XCTL can go:

flowchart TD
    C["PROGC"] -->|"PROGRAM('PROGP')"| P["PROGP"]
    P -->|"MOVE 'PROGT'"| T["PROGT"]
    P -.->|"commarea [0, 8)"| Q["PROGQ · not analysed"]
    T -.->|"MOVE 'PROGM'"| M["PROGM · not analysed"]
    T -.->|"commarea [0, 8)"| Q

PROGC stamps 'PROGQ' into the first eight bytes of its commarea and XCTLs to PROGP. PROGP and PROGT each XCTL to a literal or to the first eight bytes of the commarea they received, handing that commarea on. Dashed arrows lead to PROGQ and PROGM, which are not analysed; each arrow is labelled with the line that names its target.

The question is the target of PROGT's XCTL. Exactly, it is PROGM or PROGQ: PROGQ travels from PROGC through PROGP's commarea untouched and into PROGT, which is why PROGT's dashed commarea arrow also ends at PROGQ. Here is what the combine answers at four limits, for PROGT and for PROGP; these are the rows the test asserts:

Read the first two rows for PROGT together: the answer at 0 and at 1 is the same, yet both still carry hop-limit, and at 2 it grows. That is why the reason matters more than the comparison. The two solid edges, PROGC → PROGP (a literal) and PROGP → PROGT (from PROGP's own MOVE 'PROGT'), are found at every limit.

The lines that matter. PROGT is PROGP with 'PROGM' in place of 'PROGT':

* PROGC: WS-FROM is bytes [0, 8) of WS-AREA
MOVE 'PROGQ' TO WS-FROM.
EXEC CICS XCTL PROGRAM('PROGP')
     COMMAREA(WS-AREA) LENGTH(20) END-EXEC.

* PROGP: LK-FROM is DFHCOMMAREA [0, 8)
IF EIBCALEN = 0
    MOVE 'PROGT' TO WS-NEXT
ELSE
    MOVE LK-FROM TO WS-NEXT
END-IF.
EXEC CICS XCTL PROGRAM(WS-NEXT)
     COMMAREA(DFHCOMMAREA) LENGTH(20) END-EXEC.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGC.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-AREA.
           05  WS-FROM          PIC X(8).
           05  WS-REST          PIC X(12).
       PROCEDURE DIVISION.
           MOVE 'PROGQ' TO WS-FROM.
           EXEC CICS XCTL PROGRAM('PROGP')
                COMMAREA(WS-AREA) LENGTH(20) END-EXEC.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGP.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  WS-NEXT              PIC X(8).
       LINKAGE SECTION.
       01  DFHCOMMAREA.
           05  LK-FROM          PIC X(8).
           05  LK-REST          PIC X(12).
       PROCEDURE DIVISION.
           IF EIBCALEN = 0
               MOVE 'PROGT' TO WS-NEXT
           ELSE
               MOVE LK-FROM TO WS-NEXT
           END-IF.
           EXEC CICS XCTL PROGRAM(WS-NEXT)
                COMMAREA(DFHCOMMAREA) LENGTH(20) END-EXEC.

       IDENTIFICATION DIVISION.
       PROGRAM-ID. PROGT.
      *    Same as PROGP, with 'PROGM' in place of 'PROGT'.

Step by step

The walk from PROGT's XCTL meets three places, climbing the graph above from PROGT to PROGC. A place is a program, a statement in it, and a byte range. Each row is a place, what its own program gives, and where it would cross next. The first column is the place's hop count.

The second place is PROGP's commarea at the moment PROGP hands it on. PROGP never writes LK-FROM, so the bytes there are what PROGP received, and the walk must cross again.

PROGP's own target needs one crossing fewer: its walk starts at its XCTL with {PROGT} found locally and reaches PROGC at hops 1. That is why, in the example's table, PROGP's column loses hop-limit one row earlier than PROGT's.

Counting crossings

Inside one program a walk is cheap: the per-program memo answers each position once for the whole run. The expensive part is leaving the program, which the first two places of the step-by-step table do in their last column. There are three ways to leave, and each is a crossing:

A second, separate switch, --skip-readbacks, drops the RETURNED row altogether: those stops are not followed, and the bytes report readback-skipped. PROGL's table under what goes wrong shows it.

Give each place a counter: how many crossings it took to get here. When a place at the limit wants to cross again, it does not. It keeps the values it found in its own program, drops the crossings, and adds the reason hop-limit. In step 2 of the walk that place is PROGP's, at hops 1: it keeps its empty set and adds the reason, which travels back to PROGT's jump the same way every other reason in a value set does (see the reasons taxonomy for the full list). So PROGT's chips in step 2 carry hop-limit, though the cut was one program away:

The answer is a subset of the exact answer: at 1 it is {PROGM}, where the exact answer is {PROGM, PROGQ}. A target whose own walk was cut says so; a target shortened only because a cut elsewhere hid a link does not (see what goes wrong).

Why the walk needs a bound

The example's walk met three places and ended at a literal. A statement reached under many different byte ranges is many places, and where programs hand areas to each other in a ring, every program in the ring can reach every other under many ranges, so one cyclic group holds about as many places as the programs in the ring times the byte ranges each is reached under. The smallest ring is three copies of PROGP, each choosing the next program in the ring from a literal or from the first eight bytes of the commarea it received:

flowchart LR
    X["PROGX"] -->|"MOVE 'PROGY'"| Y["PROGY"]
    Y -->|"MOVE 'PROGZ'"| Z["PROGZ"]
    Z -->|"MOVE 'PROGX'"| X

Each arrow is an XCTL that hands on the whole commarea. Walking back from PROGX's XCTL, with no limit, meets these places. Only one byte range, [0, 8), travels round this ring, so each program adds one place to the walk; a ring that passed several ranges would add one place per program per range.

Row 4 is not row 1: the same statement, but the commarea's bytes rather than WS-NEXT's, so it is a separate place. Its crossing lands on place 2, which the memo already holds, and the walk ends. On the large corpus the same shape, with many more programs and ranges, grew past a million places.

The memo already answers each place once per round: the four rows above are each answered once. The remaining cost is the number of rows, which is a property of the corpus. No exact fix could be guaranteed faster without building it and measuring it on the corpus. What was needed was a walk whose cost has a known bound, and whose answers say when they may be incomplete. Here is the ring's walk from PROGX with --max-hops 2; the amber place is the one at the limit:

flowchart TD
    p1["PROGX · WS-NEXT [0, 8) · hops 0 · {PROGY}"] -->|"RECEIVED"| p2["PROGZ · commarea [0, 8) · hops 1 · {}"]
    p2 -->|"RECEIVED"| p3["PROGY · commarea [0, 8) · hops 2 · {}"]
    p3 -.->|"not crossed: hop-limit"| p4["PROGX · commarea [0, 8)"]
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000
    class p3 changed

PROGY's place, at hops 2, keeps its empty set and adds hop-limit, which travels back up the two solid arrows to PROGX's jump, so PROGX's target is:

The cost is now bounded by the programs within N crossings of the jump, not by the size of the corpus: the picture above has three places whatever lies beyond the dashed arrow.

Where this shows up

Cobble's last dataflow stage, cobble-dataflow-combine, answers one question for a CICS corpus: where can each dynamic jump go? On a large CICS corpus (about 3,800 programs and 19,000 jumps), a memo over strongly connected components (explainer 10), a per-program memo, an edge index, and places told apart by their bytes alone had made each walk cheap; even so, one cyclic group of walks, the ring's shape at scale, grew past a million places on the stack. The goal was narrow. Dynamic targets on that corpus come in three shapes, here as lines of PROGP with the crossings each needs:

The last shape, about 5% of them, is PROGP's own target: one crossing, to PROGC, finds 'PROGQ', so from --max-hops 1 up its row carries no hop-limit. An answer that walks a few crossings and says honestly where it stopped covers all three.

The rule

Each line of the box was applied in the walk above. The cut line is step 1 (PROGT's place at hops 0) and step 2 (PROGP's place at hops 1). The hops + 1 line is step 3, where PROGC's place is reached with hops 2. The stays 0 clause is step 4, where the hop column reads 0 on every row (amber where it changed). The --skip-readbacks line is PROGL's second row under what goes wrong.

Why hops are counted only when a limit is set: the hop count is part of the place. With no limit, a cycle across programs would come back to the same program, statement and bytes with a larger count — a new place on every lap, and the walk would never end. With the count held at 0, the lap returns to a place already seen and the memo closes the cycle: that is row 4 of the ring's table landing on place 2. With a limit N, a place can appear under at most N + 1 counts, so laps run out. The ring's walk from PROGX shows both, one row per limit:

Under limit N the walk holds N + 1 places, the last one cut. At 4, PROGZ's commarea is held twice, as Z·1 and Z·4. With no limit it holds four, and the lap that would have been Z·4 is the Z·0 the memo already has.

Why a target without hop-limit is exact: expansion depends on the hop count only through the cut. If no place reached from a jump was cut, each was expanded exactly as it would be with no limit, so the walk reaches the same programs, statements and bytes, and joins the same values and reasons. Steps 3 and 4 of the walk are this argument on PROGT: the same three places, expanded the same way, differing only in the hop column, with the same chips. (This holds within a round, given the same edges; see below.)

What goes wrong

• Cut targets are subsets. A hop-limit row keeps every value it found, and they are all real, but there may be more. PROGT at --max-hops 1:

  	candidates	reasons
  at 1	PROGM	hop-limit
  exact	PROGM, PROGQ	none

  PROGM is real; PROGQ is missing. A cut row is never silent: the reason is on the row in targets.jsonl. Rows downstream of a link a cut hid can be silent (see rounds couple targets below). (See the reasons taxonomy for the full list of reason codes.)
• Choosing N is empirical. Raise N until no row carries hop-limit, or the rows that still do are ones you can accept as possibly short. Some never clear: in the ring's table above, every limit from 0 to 4 leaves PROGX at PROGY · hop-limit, because every place on that ring has a crossing and nothing on it ever writes the commarea, so the last place held is always cut. Checking that targets.jsonl and links.jsonl stop changing between N and N + 1 helps, but it is not proof (next point): rows carrying hop-limit can still change, and so can rows that depend on a link a cut hid. On the large corpus:

  --max-hops	time	targets
  3	about 1 s	—
  4	about 10 s	identical to 3
  5	about a minute	chosen

  Rows 3 and 4 agree, yet 3 targets still carried hop-limit, so 5 was chosen. This page does not record how many, if any, still carried it at 5. On CardDemo, the targets were identical with no limit, with --max-hops 1, and with --max-hops 1 and --skip-readbacks together.
• Identical at N and N + 1 is not proof. The example shows it: PROGT's target, from the example's table,
  0: PROGM · hop-limit1: PROGM · hop-limit2: PROGM, PROGQ
  is the same at 0 and 1 and grows at 2, because the middle program, PROGP, only relays bytes (its row in step 2 finds {}). Every relay program in a chain is one more crossing that finds nothing. The hop-limit reason is the honest signal; the comparison is a heuristic.
• Rounds couple targets. The combine runs in rounds: a target's values become new edges, and edges feed other walks. A cut that hides a program name hides the edge to that program too, and a walk into that program then sees fewer callers without itself being cut. In the example, the name is PROGQ and the hidden edge is PROGT → PROGQ, the dashed arrow from PROGT to PROGQ in the example's graph:

  --max-hops	PROGT's target	callers of PROGQ a next round could know
  1	PROGM · hop-limit	PROGP
  2	PROGM, PROGQ	PROGP, PROGT

  PROGQ is not analysed, so here nothing is shortened. Were it analysed, a RECEIVED crossing in PROGQ's own walk at 1 would go to PROGP but not to PROGT, and nothing on PROGQ's row would say so. This follows from reading the code; it was not reproduced. The cut target that hid the name does carry hop-limit, so the trail starts at a flagged row.
• Cost is per program, not per statement. N bounds how many programs a walk enters, not how big they are. Under a limit a place can also exist under up to N + 1 hop counts, so the memo may hold that many copies of it: in the ring's table at 4, PROGZ's commarea is held as both Z·1 and Z·4.
• --skip-readbacks loses a whole shape. A program that LINKs to a routine which writes the next program's name into the commarea, and then XCTLs to that name, resolves to nothing with the flag set. PROGL is that program:

         PROGRAM-ID. PROGL.
         ...
         01  WS-AREA.
             05  WS-NEXT          PIC X(8).
             05  WS-REST          PIC X(12).
         PROCEDURE DIVISION.
             EXEC CICS LINK PROGRAM('PROGW')
                  COMMAREA(WS-AREA) LENGTH(20) END-EXEC.
             EXEC CICS XCTL PROGRAM(WS-NEXT) END-EXEC.
  
         PROGRAM-ID. PROGW.
         ...
         01  DFHCOMMAREA.
             05  LK-NEXT          PIC X(8).
             05  LK-REST          PIC X(12).
         PROCEDURE DIVISION.
             MOVE 'PROGN' TO LK-NEXT.
             EXEC CICS RETURN END-EXEC.

  WS-NEXT is bytes [0, 8) of the area PROGW wrote back, so PROGL's target needs one RETURNED crossing:

  run	target of PROGL
  default	PROGN
  --skip-readbacks	no candidate · readback-skipped
  --max-hops 0	no candidate · hop-limit

  The second row is the lost shape: the row says readback-skipped and has no candidate. The third shows the same crossing counted as a hop.

In cobble

The combine (cobble-dataflow-combine) applies the limit when --max-hops is set; with no limit, a walk follows links as far as they go. A walk cut at the limit carries the reason hop-limit. --skip-readbacks leaves RETURNED stops unfollowed, and the bytes report readback-skipped. Each place is answered once per round, as memoised reachability explains. Both flags are in the field dataflow reference. This is PROGT's row in targets.jsonl from running the combine on the example with --max-hops 1; it is the 1 row of the example's table, PROGT's column:

{"caller": "PROGT", "node": "%MAIN/1", "transfer": "CICS_XCTL",
 "expression": "WS-NEXT", "candidates": ["PROGM"],
 "reasons": ["hop-limit"], "dropped": [], "outside": []}