Explainer 10 of 15

From byte provenance to a field graph

Read first: Byte-extent aliasing, Gen/kill and reaching definitions

The fixpoint's output is byte provenance: for each statement, the source bytes, the target bytes, and the earlier statements (the definers) whose writes the source may hold. This page turns that into a graph whose nodes are elementary fields.

Nodes

A node is an elementary field: one with nothing declared under it. It is named PROGRAM:RECORD.FIELD, so two programs' fields never share a node, whatever they are called.

Each REDEFINES variant has its own fields.
Each OCCURS occurrence is its own node: LK-COMMAREA(25), X(2,5).
Literals, files, maps and queues are terminal nodes of their own program.

The example

A record arrives in IN-AREA, passes through an 8-byte buffer declared as one field, and lands in REC:

01  IN-AREA.
    05  I-ID     PIC X(4).
    05  I-AMT    PIC X(4).
01  BUF          PIC X(8).
01  REC.
    05  R-ID     PIC X(4).
    05  R-AMT    PIC X(4).

/0  MOVE IN-AREA TO BUF.
/1  MOVE BUF TO REC.

The fixpoint's provenance for the two moves:

site	source bytes	target bytes	definers of the source
/0	IN-AREA [0:8]	BUF [8:16]	none
/1	BUF [8:16]	REC [16:24]	/0

Mapping each move by name

Map each range to the fields declared over it. BUF has one field, so /1 links that one field to every target field:

flowchart LR
    IID["I-ID"] --> BUF["BUF"]
    IAMT["I-AMT"] --> BUF
    BUF --> RID["R-ID"]
    BUF --> RAMT["R-AMT"]

Now I-ID reaches both R-ID and R-AMT. Real programs do this constantly, with PIC X(500) work areas and whole-record I/O buffers. One buffer in the middle makes every field on one side look related to every field on the other.

Tracing back through the buffer

The read at /1 knows its definer, /0. /0 copied into an undivided field, so follow it back to its own source and take the fields that filled those bytes instead:

BUF's eight bytes, labelled by the field that filled them

BUF

from I-ID

from I-AMT

The read of BUF now presents two pieces, I-ID at bytes 0–3 and I-AMT at bytes 4–7. They cover all of BUF, so BUF itself drops out of this read. Several fields on both sides align by byte:

flowchart LR
    IID["I-ID"] --> BUF["BUF"]
    IAMT["I-AMT"] --> BUF
    IID --> RID["R-ID"]
    IAMT --> RAMT["R-AMT"]

A trace back takes the finer pieces only when it finds two or more. A buffer filled from one field keeps the field it already has.

Where the bytes land

Every edge records its placements: length bytes from offset source in the source field to offset target in the target field.

edge	alignments	aligned
I-ID → R-ID	{source 0, target 0, length 4}	yes
I-AMT → R-AMT	{source 0, target 0, length 4}	yes
I-AMT → BUF	{source 0, target 4, length 4}	yes

aligned is true when every site's placement is known. A statement that rewrites the bytes (arithmetic, STRING, a conversion between usages or into an edited picture), a move through a clamped range such as a table element with a computed subscript, and every edge from an origin or into a sink have none. rebuilt is true when every site's statement built the target's value in place, by arithmetic or STRING: such an edge has no placement, but its target is not a copy of anything. The next explainer, exact field classes, depends on these placements.

Fields that meet through a file

Two programs that never call each other can still share data through a file. Program W writes an 11-byte ID to dataset DS.A; program R reads the same record as GRP (bytes 0–4) and SEQ (bytes 5–10). The record is cut at every field boundary any site uses, and each piece becomes a slot node:

edge	alignment
W:WREC.ID → DS.A[0:5]	{source 0, target 0, length 5}
W:WREC.ID → DS.A[5:11]	{source 5, target 0, length 6}
DS.A[0:5] → R:RREC.GRP	{source 0, target 0, length 5}
DS.A[5:11] → R:RREC.SEQ	{source 0, target 0, length 6}

These are four of the edges cobble's dataset-link tests check for a layout like this one.

Finding the dataset is its own problem. A batch file statement goes through its SELECT, DD name and the JCL step that runs the program. A CICS one goes through the resolved file name and the CSD. Each dataset edge is exact, or possible with its reasons: several candidate files, the dataflow's own doubt about the file name (such as incomplete-walk), a step reached only through a dynamic call it may not make, a clamped record extent, or overlapping layouts in the slot:

candidatesincomplete-walk, …call-candidateclampedoverlapping-layouts

A possible edge carries no placement. A site that resolves to no dataset gets a slot of its own, linked only to that site's fields, by possible edges whose reason says why it did not resolve: no candidate file name, no JCL step runs the program, the step has no such DD, or neither a file target nor a SELECT:

uninitialisedno-stepdd-unboundunresolved-file

On CardDemo

A date through an undivided field. COTRN00C builds the current date as a group, copies it into a plain PIC X(08), and shows that on the screen:

       05 WS-CURDATE-MM-DD-YY.                    *> CSDAT01Y
         10  WS-CURDATE-MM             PIC 9(02).
         10  FILLER                    PIC X(01) VALUE '/'.
         10  WS-CURDATE-DD             PIC 9(02).
         10  FILLER                    PIC X(01) VALUE '/'.
         10  WS-CURDATE-YY             PIC 9(02).
       05 WS-TRAN-DATE               PIC X(08) VALUE '00/00/00'.
       ...
           MOVE WS-CURDATE-MM-DD-YY       TO WS-TRAN-DATE
           ...
                   MOVE WS-TRAN-DATE TO TDATE01I OF COTRN0AI

Mapped by name, the last move would link one field, WS-TRAN-DATE, to the screen. Traced back, the screen field gets the date's parts, each at its own bytes:

source field	lands in TDATE01I at
WS-CURDATE-MM	bytes 0–1
FILLER '/'	byte 2
WS-CURDATE-DD	bytes 3–4
FILLER '/'	byte 5
WS-CURDATE-YY	bytes 6–7

A file read by seven programs. The card cross-reference KSDS is read by six batch programs and one CICS one, and written by none. Its record is cut into these slots:

slot	read as, in the record copybook	read as, in the file's own record
[0:16]	XREF-CARD-NUM	FD-XREF-CARD-NUM
[16:25]	XREF-CUST-ID	FD-XREF-DATA at offset 0; FD-XREF-CUST-NUM in CBACT04C
[25:36]	XREF-ACCT-ID	FD-XREF-DATA at offset 9; FD-XREF-ACCT-ID in CBACT04C
[36:50]	FILLER	FD-XREF-DATA at offset 20; FD-XREF-FILLER in CBACT04C
[50:1000]	only CBSTM03B's 1,000-byte I/O area

The copybook's fields are read in CBACT03C, CBACT04C, CBEXPORT, CBTRN02C, CBTRN03C and COTRN02C. The file's own record fields are read in the batch readers that declare one: CBACT03C, CBACT04C, CBSTM03B, CBTRN02C and CBTRN03C.

The last slot exists because CBSTM03B, a file-access subprogram, reads its files into one 1,000-byte field as well. That field also reaches slots [0:16] to [36:50], at offsets 0, 16, 25 and 36. Every edge here is exact.

A file that resolves to nothing. CBTRN01C reads the same record, but no JCL step runs CBTRN01C, so its read gets a slot of its own, CBTRN01C/2000-LOOKUP-XREF/1|?XREF-FILE, with possible edges and the reason no-step. It meets none of the seven.

What it costs

Tracing back is a walk over definers, and definers branch. Picture a ladder of copies, each step filled from one of two earlier copies:

flowchart LR
    A0["copy 0"] --> A1["a1"] & B1["b1"]
    A1 --> A2["a2"] & B2["b2"]
    B1 --> A2 & B2
    A2 --> A3["…"]
    B2 --> A3

There are 2ⁿ paths through n steps, but only 2n copies. A memo keyed on (range, definers) answers each lookup once, so the cost grows with copies, not paths.

The first memo also keyed on the set of sites already on the walk, to cut loops. That set differs on every path, so the memo almost never hit, and the walk enumerated paths: its cost doubled with each step of the ladder.

Depth is the second limit. A recursive walk used about eight Python frames per copy, so a chain of about 130 copies hit Python's recursion limit. The walk now runs on an explicit stack: each lookup is a generator that yields the lookups it needs. Same order, same memo, same answers.

The rule

fields(range) = elementary fields declared over the range's bytes
traced(read) = fields(read) + for each definer d that wrote inside read:
if d copied into one undivided field: finer(d) = traced(d's source), shifted
else: the field d wrote
finer(d) = traced pieces if there are 2 or more, else d's own field
presented(read) = traced(read) − named fields its pieces cover
edges(target, source) = one field either side: every pair; else byte-aligned pairs

What goes wrong

Loops of copies. Where copies feed each other in a loop, the walk stops at a copy already on its way back. The first read to reach a range fixes its answer for every later read, so a later read may keep the undivided field where it would have taken the finer pieces.
Unresolved files. A file statement whose dataset is not known keeps a slot of its own, so its fields meet no other program through it.
Clamped moves. A move whose bytes are not known exactly has no placement, so nothing downstream can line its bytes up.

In cobble

Run on this page's program, cobble-dataflow-fixpoint writes the two provenance rows above. It writes each move and its definers apart; they are joined here, one line per site:

MAIN-PARA/0  IN-AREA@working_storage[0:8] -> BUF@working_storage[8:16]   definers: none
MAIN-PARA/1  BUF@working_storage[8:16] -> REC@working_storage[16:24]     definers: MAIN-PARA/0

and cobble-experimental-partition-graph writes exactly the traced graph's four edges, as source → target [(source offset, target offset, length)]:

BUFCOPY:IN-AREA.I-ID  -> BUFCOPY:BUF.BUF     [(0, 0, 4)]
BUFCOPY:IN-AREA.I-AMT -> BUFCOPY:BUF.BUF     [(0, 4, 4)]
BUFCOPY:IN-AREA.I-ID  -> BUFCOPY:REC.R-ID    [(0, 0, 4)]
BUFCOPY:IN-AREA.I-AMT -> BUFCOPY:REC.R-AMT   [(0, 0, 4)]

Full listing (BUFCOPY)

       IDENTIFICATION DIVISION.
       PROGRAM-ID. BUFCOPY.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  IN-AREA.
           05  I-ID             PIC X(4).
           05  I-AMT            PIC X(4).
       01  BUF                  PIC X(8).
       01  REC.
           05  R-ID             PIC X(4).
           05  R-AMT            PIC X(4).
       PROCEDURE DIVISION.
       MAIN-PARA.
           MOVE IN-AREA TO BUF.
           MOVE BUF TO REC.
           STOP RUN.