java/ch/wlkl/wsm/Syntax.java
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package ch.wlkl.wsm;
import ch.wlkl.env.A2S;
import ch.wlkl.env.All2S;
import static ch.wlkl.env.Env.*;
import static ch.wlkl.wsm.Parser.xQuote;
import java.util.ArrayList;
import java.util.Arrays;
import static ch.wlkl.env.Ut.clone2;
import static java.lang.Integer.min;
import java.util.List;
import static ch.wlkl.env.Env.dy;
/**
*
* @author walter
*/
abstract public class Syntax implements Formattable, A2S {
public final Syntax[] nodes;
int fx = -9; // formatIndex: > 0 subFormat, -5 this whole, -1 use next free subIndex, -9 without index
Format format = null;
Class fClass = null;
public static final Syntax[] emptySyn = {};
final static SynLit refLit = new SynLit("<<<refLit>>>");
Syntax() {
nodes = emptySyn;
}
Syntax(Object... n) {
nodes = n == null || n.length == 0 ? emptySyn : atoms(n);
}
public static Syntax[] atoms(Object... a) {
Syntax[] r = new Syntax[a.length];
for (int i = 0; i < a.length; i++) {
if (a[i] == null) {
r[i] = null;
} else if (a[i] instanceof Syntax) {
r[i] = (Syntax) a[i];
} else {
r[i] = new SynLit(a[i]);
}
}
return r;
}
@Override
public void a2s(All2S a) {
a.a2s("fx=", fx, ", nodes=", nodes, " format=", format);
}
public boolean isFor(Formattable f) {
return fClass == null || f == null || f.getClass() == fClass;
}
@Override
public void format(Formatter f) {
for (int ix = 0; ix < nodes.length; ix++) {
f.format(1, nodes[ix]);
}
}
public Object formatKey() {
return this instanceof SynLit ? null : this instanceof SynFor ? ((SynFor) this).name : this;
}
public Format makeFormat(FormatFactory ff) {
String lx;
if (format != null) {
return format;
} else if (this instanceof SynRule && (lx = ((SynRule) this).lex) != null) {
return format = ff.fmt(formatKey(), fClass, lx);
} else if (nodes == null || nodes.length == 0) {
assert this instanceof SynLit : assFail("nodes == null", this);
return null;
}
debug("makeCode ", this);
ArrayList<Syntax> el = new ArrayList(); // sub Elements
el.add(refLit); // 0 reserved for start
for (Syntax n : nodes) {
n.makeEle(el);
}
el.add(refLit);
int ps = el.size();
ArrayList<Syntax>[][] ft = new ArrayList[ps][ps]; // from ele to ele paths
ArrayList<Syntax>[] pa = new ArrayList[ps]; // current paths from
pa[0] = new ArrayList(); // start from 0
makeFromTo(ft, pa, true);
for (int px = 0; px < ps; px++) { // add path to end
ft[px][ps - 1] = pa[px];
}
debug("ft ", ft);
int[] lB = new int[ps]; // how many path nodes before for each ele
int[] lA = new int[ps]; // how many path nodes before for each ele
ftSplit(ft, lB, lA); // split path nodes: attach to ele before/after
boolean[] or = new boolean[ps]; // do we need to prepend chc format before (e.g. for x+ loop(x) or x)
nodes[0].makeOr(or);
StringBuilder s = new StringBuilder(); // build the srcCode
int ax, fx, fy, l1;
for (ax = 0; ax < ps; ax++) { // after subEle 0
if (ft[0][ax] != null) {
Syntax.appFmtCode(s, ft[0][ax], 0, lA[0]);
break;
}
}
for (ax = 1; ax < ps; ax++) { // subEle 1 ...
s.append(" ,");
fy = -1;
l1 = s.length();
boolean mult = false;
for (fx = 0; fx < ps; fx++) { // variants from fx before subEle ax
if (ft[fx][ax] == null) {
continue;
}
if (fy < 0) {
} else if (eq(ft[fx][ax], lA[fx], ft[fx][ax].size() - lB[ax], ft[fy][ax], lA[fy], ft[fy][ax].size() - lB[ax])) {
continue;
} else {
s.append(" |").append(fx);
mult = true;
}
Syntax.appFmtCode(s, ft[fx][ax], lA[fx], ft[fx][ax].size() - lB[ax]);
fy = fx;
}
if (mult) {
s.insert(l1, " |").append(" |");
}
Syntax.appFmtCode(s, ft[fy][ax], ft[fy][ax].size() - lB[ax], lB[ax]); // unique before subEle ax
if (ax < ps - 1) {
appFmtCode(s, el.get(ax));
for (int tx = 0; tx < ps; tx++) {
if (ft[ax][tx] != null) {
Syntax.appFmtCode(s, ft[ax][tx], 0, lA[tx]); // unique after subEle ax
break;
}
}
}
}
// out("src " + s);
Format[] fmt = new Format[ps - 2]; // subFormats
Object ky;
for (fx = 1; fx < ps - 1; fx++) {
if (null != (ky = el.get(fx).formatKey())) {
fmt[fx - 1] = ff.at(ky);
}
}
// create formats
if (this instanceof SynOr && this.fx > 0) {
format = ff.chc(formatKey(), s.toString(), fmt); // or --> chc
} else if (this instanceof SynRule && nodes[0] instanceof SynSeq && nodes[0].fx == -5) {
format = ff.chc(formatKey(), s.toString(), fmt); // -5 --> chc
} else {
int cOr = 0;
for (boolean b : or) {
if (b) {
cOr++;
}
}
if (cOr == 0) {
format = ff.fmt(formatKey(), fClass, s.toString(), fmt); // direct format
} else { // prepend chc (or nest)
Format f1 = ff.fmt(fClass, s.toString(), fmt);
Format[] k = new Format[cOr + 1];
k[fx = 0] = f1;
for (ax = 1; ax < ps - 1; ax++) {
if (or[ax]) {
k[++fx] = ff.at(el.get(ax).formatKey());
}
}
format = ff.chc(formatKey(), "", k);
}
}
for (Syntax e : el) { // formats of subEle
e.makeFormat(ff);
}
return format;
}
/**
* check whether two subSequences are equal
* @param l
* @param lB
* @param lE
* @param r
* @param rB
* @param rE
* @return
*/
public static boolean eq(List l, int lB, int lE, List r, int rB, int rE) {
int i, ll = lE - lB;
if (ll != rE - rB) {
return false;
}
if (ll <= 0) {
return true;
}
for (i = 0; i < ll && l.get(lB + i).equals(r.get(rB + i)); i++) {
}
return i >= ll;
}
/**
* append to s the format code sources for Syntaxes in l in range b e
*/
public static void appFmtCode(StringBuilder s, List<Syntax> l, int b, int e) {
for (int i = b; i < e; i++) {
appFmtCode(s, l.get(i));
}
}
/**
* append to s the format code source for Syntax t
*/
public static void appFmtCode(StringBuilder s, Syntax t) {
Class c = t.getClass();
if (c == SynOr.class || c == SynRule.class) {
s.append(" $");
} else if (t instanceof SynFor) {
s.append(" '").append(((SynFor) t).name);
} else {
dy("appSrc implement " + c);
}
}
/**
* split the paths in the from Syntax to Syntax matrix to nodes
* before an ele, nodes after an ele, the remaining nodes remaining in the
* from/to path
*
* @param ft from Syntax to Syntax matrix
* @param lB nodes before each ele, precondition: filled with 0
* @param lA nodes after each ele, precondition: filled with 0
*/
public static void ftSplit(ArrayList<Syntax>[][] ft, int[] lB, int[] lA) {
int f, t,
rS = -1, // running size
j = -1, jS = -1, // first index, size
i, // offset
cC, cL = -1; // cumulated count, lenghtfirst index, size
final int l = ft.length;
boolean[] dB = new boolean[l]; // done Before
boolean[] dA = new boolean[l]; // done After
for (t = 0; t < l; t++) { // first set maximal before length for eles with 2 or more incoming paths
cC = 0;
cL = Integer.MAX_VALUE;
for (f = 0; f < l; f++) {
if (ft[f][t] == null) {
} else {
cC++;
cL = min(cL, (rS = ft[f][t].size()) - lA[f]);
if (cC == 1) {
j = f;
jS = rS;
} else {
for (i = 0; i < cL && ft[j][t].get(jS - i) == ft[f][t].get(rS - i); i++) {
}
cL = i;
}
}
}
if (cC >= 2) {
for (f = 0; f < l; f++) {
if (ft[f][t] != null) {
lB[t] = cL;
dB[t] = true;
}
}
}
}
debug("lB 1 ", lB);
for (f = 0; f < l; f++) { // set maximal after length for eles with 2 or more outgoing paths
cC = 0;
cL = Integer.MAX_VALUE;
for (t = 0; t < l; t++) {
if (ft[f][t] == null) {
} else {
cC++;
cL = min(cL, (rS = ft[f][t].size()) - lB[t]);
if (cC == 1) {
j = t;
jS = rS;
} else {
for (i = 0; i < cL && ft[f][j].get(i) == ft[f][t].get(i); i++) {
}
cL = i;
}
}
}
if (cC >= 2) {
for (t = 0; t < l; t++) {
if (ft[0][t] != null) {
lA[f] = cL;
dA[f] = true;
}
}
}
}
debug("lA 2 ", lA);
if (!dA[0]) { // set maximal after length for ele 0
cC = 0;
for (t = 0; t < l; t++) {
if (ft[0][t] != null) {
cC++;
lA[0] = ft[0][t].size() - lB[t];
dA[0] = true;
}
}
if (cC != 1) {
dy("lA[0] cC=" + cC);
}
}
all2s.restart();
debug("lA 3 ", lA);
for (t = 0; t < l; t++) { // set maximal before length for eles with only 1 incoming paths
if (dB[t]) {
continue;
}
cC = 0;
for (f = 0; f < l; f++) {
if (ft[f][t] != null) {
cC++;
lB[t] = ft[f][t].size() - lA[f];
}
}
if (cC != (t == 0 ? 0 : 1)) {
dy("lB[" + t + "] cC=" + cC);
}
}
debug("lB 4 ", lB);
}
/**
* build list of elements (subSyntax) ls, assign missing formatIndexes fx
* @param lx highest assigned/encountered fx
* @return highest assigned/encountered fx
*/
public void makeEle(List<Syntax> ls) {
if (fx == -1) {
fx = ls.size();
}
if (fx <= 0) {
for (Syntax n : nodes) {
n.makeEle(ls);
}
} else {
Syntax p = this instanceof SynRef ? nodes[0] : this;
if (fx >= ls.size()) {
while (fx - 1 > ls.size()) {
ls.add(null);
}
ls.add(p);
} else if (ls.get(fx) == null) {
ls.set(fx, p);
} else if (ls.get(fx) != p) {
dy("mismatch ls[" + fx + "]=", ls.get(fx), " <> p=", p);
}
}
}
/**
* build the paths in the from Syntax to Syntax matrix
*
* @param ft from Syntax to Syntax matrix
* @param pa current path from to this
*/
public void makeFromTo(ArrayList<Syntax>[][] ft, ArrayList<Syntax>[] pa, boolean start) {
if (fx >= 0 && !start) {
for (int fr = 0; fr < pa.length; fr++) {
if (pa[fr] == null) {
} else if (ft[fr][fx] == null) {
ft[fr][fx] = (ArrayList<Syntax>) pa[fr].clone();
} else if (!pa[fr].equals(ft[fr][fx])) {
dy("path mismatch");
}
pa[fr] = null;
}
pa[fx] = new ArrayList();
} else if (this instanceof SynRef || this instanceof SynRule) {
nodes[0].makeFromTo(ft, pa, false);
} else if (this instanceof SynLit) {
for (ArrayList<Syntax> n : pa) {
if (n != null) {
n.add(this);
}
}
} else {
dy("ex " + fx + ": " + this);
}
}
/**
* mark the elements that can used (or'd) instead of containing rule
*
* @param or mark as true, if ele can be used
*/
public void makeOr(boolean[] or) {
if (fx >= 0) {
if (!(this instanceof SynLex)) {
or[fx] = true;
}
} else if (this instanceof SynOr || this instanceof SynLoop) {
for (Syntax n : nodes) {
n.makeOr(or);
}
} else if (this instanceof SynSeq) {
Syntax f = null;
for (Syntax n : nodes) {
if (!(n instanceof SynLoop && ((SynLoop) n).beg == 0)) {
if (f == null) {
f = n;
} else if (f != n) {
return;
}
}
}
if (f != null) {
f.makeOr(or);
}
}
}
static class SynLit extends SynFor {
public SynLit(Object l) {
super(l.toString());
}
@Override
public boolean equals(Object o) {
return o.getClass() == getClass() && name.equals(((SynLit) o).name);
}
public void format(Formatter f) {
f.format(1, xQuote(name));
}
}
static class SynLex extends SynLit {
public SynLex(Object l) {
super(l);
fx = -1;
}
public void format(Formatter f) {
f.format(1, name);
}
}
static class SynBra extends Syntax { //
public SynBra(Syntax e) {
super(e);
}
}
static class SynRule extends SynFor {
String lex = null;
public SynRule(String n) {
super(n, new Object[1]);
}
public void format(Formatter f) {
f.format(1, name);
f.format(2, nodes[0]);
}
}
static abstract class SynFor extends Syntax {
final String name;
public SynFor(String n) {
name = n;
// fx = -2; wk???
}
public SynFor(String n, Object... o) {
super(o);
name = n;
// fx = -2; wk???
}
public void a2sName(All2S a) {
a.name(this, 3, name);
}
public void format(Formatter f) {
f.format(1, name);
}
}
static class SynRef extends SynFor {
public SynRef(String n, SynRule r) {
super(n, r);
fx = -1;
}
public SynRef(String n, SynOr r) {
super(n, r);
fx = -1;
}
final public static SynRule syn;
static {
SynRule r = new SynRule("<<<ref>>>");
r.nodes[0] = new SynRef("<<<ref>>>", r);
syn = r;
}
}
class SynSeq extends Syntax {
public SynSeq(Object... n) {
super(n);
}
public void makeFromTo(ArrayList<Syntax>[][] ft, ArrayList<Syntax>[] pa, boolean first) {
for (Syntax n : nodes) {
n.makeFromTo(ft, pa, false);
}
}
}
class SynOr extends Syntax {
public SynOr(Object... n) {
super(n);
}
public void makeFromTo(ArrayList<Syntax>[][] ft, ArrayList<Syntax>[] pa, boolean start) {
if (fx >= 0 && !start) {
super.makeFromTo(ft, pa, false);
return;
}
ArrayList<Syntax>[] pB = clone2(pa);
Arrays.fill(pa, null);
for (Syntax n : nodes) {
ArrayList<Syntax>[] pn = clone2(pB);
n.makeFromTo(ft, pn, false);
for (int i = 0; i < pn.length; i++) {
if (pn[i] == null) {
} else if (pa[i] == null) {
pa[i] = pn[i];
} else if (!pa[i].equals(pn[i])) {
dy("mismatch");
}
}
}
}
public void format(Formatter f) {
for (int i = 0; i < nodes.length; i++) {
f.format(1, nodes[i]);
}
}
}
class SynLoop extends Syntax {
final int beg, end;
public SynLoop(Syntax r, int b, int e) {
super(r);
beg = b;
end = e;
}
public void makeFromTo(ArrayList<Syntax>[][] ft, ArrayList<Syntax>[] pa, boolean start) {
ArrayList<Syntax>[] q = clone2(pa);
if (beg > 0) {
Arrays.fill(pa, null);
}
boolean fix = false;
for (int i = 0; i < end && !fix; i++) {
nodes[0].makeFromTo(ft, q, false);
fix = true;
for (int j = 0; j < pa.length; j++) {
if (q[j] == null) {
} else if (pa[j] == null) {
pa[j] = (ArrayList<Syntax>) q[j].clone();
fix = false;
} else if (!pa[j].equals(q[j])) {
dy("mismatch");
}
}
debug("SynLoop makeFromTo " + i + " ", pa);
};
}
public void format(Formatter f) {
f.format(1, nodes[0]);
f.format(end == 1 ? 2 : beg == 0 ? 3 : 4);
}
}
}