Go to the documentation of this file. 1 package com.cliffc.aa.HM;
5 import org.jetbrains.annotations.
NotNull;
25 static final HashMap<String,T2>
PRIMS =
new HashMap<>();
65 int cnt_syns = prog.
prep_tree(
null,
null,work);
66 int init_T2s =
T2.
CNT;
68 while( work.
len()>0 ) {
91 private static byte[]
BUF;
97 if(
skipWS() != -1 )
throw unimpl(
"Junk at end of program: "+
new String(
BUF,
X,
BUF.length-
X));
101 if(
skipWS()==-1 )
return null;
138 if( fld==
null )
throw unimpl(
"Missing term for field "+
id);
152 throw unimpl(
"Unknown syntax");
155 private static String
id() {
160 if( s.length()==0 )
throw unimpl(
"Missing id");
166 sum = sum*10+
BUF[
X++]-
'0';
169 float f = (float)sum;
170 f = f + (
BUF[
X++]-
'0')/10.0f;
175 while(
X<
BUF.length &&
BUF[
X]!=
'"' )
X++;
182 private static boolean isWS (
byte c) {
return c ==
' ' || c ==
'\t' || c ==
'\n' || c ==
'\r'; }
183 private static boolean isDigit (
byte c) {
return '0' <= c && c <=
'9'; }
184 private static boolean isAlpha0(
byte c) {
return (
'a'<=c && c <=
'z') || (
'A'<=c && c <=
'Z') || (c==
'_') || (c==
'*') || (c==
'?'); }
185 private static boolean isAlpha1(
byte c) {
return isAlpha0(c) || (
'0'<=c && c <=
'9') || (c==
'/'); }
186 private static <T> T
require(
char c, T t) {
if(
skipWS()!=c )
throw unimpl(
"Missing '"+c+
"'");
X++;
return t; }
189 for(
int i=0; i<s.length(); i++ )
190 if(
X+i >=
BUF.length ||
BUF[
X+i]!=s.charAt(i) )
191 throw unimpl(
"Missing '"+s+
"'");
200 private final HashSet<Syntax>
_work =
new HashSet<>();
219 for(
VStack vs =
this; vs!=
null; vs = vs.
_par )
220 vs._nongen.get_dups(dups);
229 @NotNull @Override
public Iterator<T2>
iterator() {
return new Iter(); }
230 private class Iter implements Iterator<T2> {
247 return t==
_t ? t : (
_t=t);
284 boolean no_more_work = work.
has(
this) || !
hm(
null);
295 return p2(sb.
ii(1),dups).
di(1);
308 @Override
T2 lookup(String name) {
throw unimpl(
"should not reach here"); }
334 throw new RuntimeException(
"Parse error, "+
_name+
" is undefined");
337 @Override
T2 lookup(String name) {
throw unimpl(
"should not reach here"); }
350 syn.prep_lookup_deps(
this);
369 for( String arg :
_args ) sb.
p(arg).
p(
' ');
374 for( String arg :
_args ) sb.
p(arg).
p(
' ');
375 return sb.
p(
" -> ... } ");
380 boolean progress =
false;
384 if( work==
null && progress )
return true;
388 if( old.
is_err() )
return false;
390 for(
int i=0; i<
_targs.length; i++ )
392 { progress=
true;
break; }
400 return old.
unify(fun,work);
403 for(
int i=0; i<
_args.length; i++ )
410 for(
int i=0; i<
_targs.length; i++ )
416 for(
int i=0; i<
_targs.length; i++ )
421 for(
int i=0; i<
_args.length; i++ )
440 boolean progress =
false;
445 if( work==
null && progress )
return true;
485 @Override
SB p1(
SB sb) {
return sb.
p(
"(...)"); }
496 boolean progress =
false;
498 if( work==
null && progress )
return true;
500 if( work==
null && progress )
return true;
501 for(
int i=1; i<
_args.length; i++ ) {
503 if( work==
null && progress )
return true;
506 if( work==
null && progress )
return true;
513 if(
str!=
null &&
str.is_struct() &&
str._con==
null ) {
514 if( work==
null )
return true;
527 if( work==
null )
return true;
529 for(
int i=0; i<
_args.length; i++ )
533 progress = tfun.
unify(nfun,work);
540 for(
int i=0; i<
_args.length; i++ ) {
542 if( progress && work==
null )
557 for(
Syntax arg :
_args ) cnt += arg.prep_tree(
this,nongen,work);
559 if(
str!=
null )
str.push_update(
this);
566 for(
Syntax arg :
_args )
if( !arg.more_work(work) )
return false;
583 for(
int i=0; i<
_ids.length; i++ ) {
586 if( i <
_ids.length-1 ) sb.
p(
',');
592 for(
int i=0; i<
_ids.length; i++ )
598 boolean progress =
false, must_alloc=
false;
600 if( work==
null && progress )
return true;
601 for(
int i=1; i<
_flds.length; i++ ) {
603 if( work==
null && progress )
return true;
606 if( work==
null && progress )
return true;
611 for( String
id :
_ids )
613 { must_alloc =
true;
break; }
615 if( work==
null )
return true;
617 for(
int i=0; i<
_ids.length; i++ )
625 for(
int i=0; i<rec.
_ids.length; i++ ) {
627 if( work==
null )
return true;
633 for(
int i=0; i<
_ids.length; i++ ) {
636 if( work==
null && progress )
return true;
653 for(
int i=0; i<
_flds.length; i++ ) {
663 if( !fld.more_work(work) )
678 boolean progress =
false;
681 if( work==
null && progress )
return true;
686 if(
find().is_err() )
return false;
687 if( work==
null )
return true;
780 if( u==
null )
return this;
781 if( u.
no_uf() )
return u;
790 if( u==
this || u==
_args[0] )
return u;
799 return u==uu ? uu : (
_args[i]=uu);
806 if(
this==that )
return false;
807 if( work==
null )
return true;
809 if(
_deps !=
null ) {
812 if( that._deps==
null && that.is_leaf() ) that._deps =
_deps;
827 if( work==
null )
return that.
_con==
null;
831 return union(that,work);
840 static private final HashMap<Long,T2>
DUPS =
new HashMap<>();
842 if(
this==that )
return false;
843 assert
DUPS.isEmpty();
844 boolean progress =
_unify(that,work);
854 if(
this==that )
return false;
859 if( that.
is_err() )
return union(that,work);
863 if(
is_leaf() )
return union(that,work);
873 assert rez==
null || rez==that;
874 if( rez!=
null )
return false;
877 if( work==
null )
return true;
880 return union_err(that,work,
"Cannot unify "+
this+
" and "+that);
883 return union_err(that,work,
"Cannot unify "+
this+
" and "+that);
891 for(
int i=0; i<
_ids.length; i++ ) {
899 if(
this==that )
return true;
903 for(
int i=0; i<
_args.length; i++ )
909 for(
int i=0; i<
_args.length; i++ )
918 int len =
_ids.length;
930 if( con==that.
_con )
return false;
931 if( work==
null )
return true;
935 return union(that,work);
939 if( con==that.
_con )
return false;
940 if( work==
null )
return true;
956 static private final HashMap<T2,T2>
VARS =
new HashMap<>();
958 assert
VARS.isEmpty() &&
DUPS.isEmpty();
963 throw unimpl(
"busted, made T2s but just testing");
970 T2 prior =
VARS.get(
this);
991 return work==
null ||
vput(that,that.
or0(
_fresh(nongen),work));
995 return work ==
null ||
vput(that,that.
_unify(
make_err(
"Cannot unify "+
this+
" and "+that),work));
999 boolean progress =
false;
1003 for(
int i=0; i<
_args.length; i++ ) {
1005 if( progress && work==
null )
return true;
1014 if(
_con!=
null && that.
_con==
null ) {
1015 if( work==
null )
return true;
1018 boolean progress =
false;
1019 for(
int i=0; i<
_args.length; i++ ) {
1022 if( work==
null )
return true;
1027 if( progress && work==
null )
return true;
1032 private boolean vput(
T2 that,
boolean progress) {
VARS.put(
this,that);
return progress; }
1038 if( rez!=
null )
return rez;
1048 for(
int i=0; i<
_args.length; i++ )
1057 if( syn==
null )
return false;
1059 assert
ODUPS.isEmpty();
1065 assert
ODUPS.isEmpty();
1071 for( ; syn!=
null; syn=syn.
_par )
1079 if( x==
this )
return true;
1082 for(
int i=0; i<x.
_args.length; i++ )
1089 if( syn==
null )
return false;
1090 assert
ODUPS.isEmpty();
1096 for(
T2 t2 : nongen )
1104 static private final HashMap<T2,T2>
CDUPS =
new HashMap<>();
1106 assert
CDUPS.isEmpty();
1113 if(
this==t )
return true;
1127 for(
int i=0; i<
_args.length; i++ )
1136 for(
int i=0; i<
_args.length; i++ ) {
1147 if( alias >=
_args.length )
return null;
1149 assert
str==
null ||
str.is_struct();
1156 while( alias >=
_args.length )
1159 if( work!=
null )
_args[alias] =
str;
1176 for(
int i=0; i<
_args.length; i++ )
1177 if(
_args[i]!=
null )
1187 for(
int i=0; i<
_args.length; i++ )
1202 t._get_dups(visit,dups);
1215 boolean dup = dups.get(
_uid);
1216 if( dup ) sb.
p(
"$V").
p(
_uid);
1217 if( visit.
tset(
_uid) && dup )
return sb;
1218 if( dup ) sb.
p(
':');
1223 for(
int i=0; i<
_args.length-1; i++ )
1231 for(
int i=0; i<
_ids.length; i++ )
1241 for(
int i=0; i<
_args.length; i++ )
1242 if(
_args[i] !=
null )
1257 private static final HashMap<T2,Integer>
VNAMES =
new HashMap<>();
1264 Integer ii =
VNAMES.get(
this);
1268 if( later ) sb.
p(
'$');
1269 char c = (char)(
'A'+ii);
1270 if( c<
'V' ) sb.
p(c);
else sb.
p(
"V"+ii);
1271 if(
is_leaf() || later )
return sb;
1279 for(
int i=0; i<
_args.length-1; i++ )
1280 args(i).
_p(sb,visit,dups).
p(
" ");
1281 return args(
_args.length-1).
_p(sb.
p(
"-> "),visit,dups).
p(
" }");
1287 for(
int i=0; i<
_ids.length; i++ )
1297 for(
int i=0; i<
_args.length; i++ )
1298 if(
_args[i] !=
null )
1299 args(i).
_p(sb.
p(i).
p(
':'),visit,dups).
p(
", ");
1305 for(
int i=0; i<
_args.length; i++ )
args(i).
_p(sb,visit,dups).
p(
" ");
static< T > T require(char c, T t)
void add_fld(String id, T2 fld, Worklist work)
boolean union_err(T2 that, Worklist work, String msg)
Struct(String[] ids, Syntax[] flds)
void add_deps_work_impl(Worklist work)
void add_work(Worklist work)
boolean _cycle_equals_struct(T2 t)
abstract boolean hm(Worklist work)
E push(E e)
Add element in amortized constant time.
void add_deps_work(Worklist work)
SB p2(SB sb, VBitSet dups)
static int find(int[] es, int e)
static boolean eq(String s0, String s1)
void prep_lookup_deps(Ident id)
static T2 make_struct(String[] ids, BitsAlias aliases, T2[] flds)
boolean hm(Worklist work)
static Syntax parse(String s)
static boolean isAlpha0(byte c)
SB p2(SB sb, VBitSet dups)
int prep_tree(Syntax par, VStack nongen, Worklist work)
static T2 prim(String name, T2... args)
int prep_tree(Syntax par, VStack nongen, Worklist work)
static final HashMap< Long, T2 > DUPS
boolean _cycle_equals(T2 t)
T2 push_update(Ary< Syntax > as)
boolean union(T2 that, Worklist work)
VBitSet get_dups(VBitSet dups)
static final HashMap< T2, Integer > VNAMES
an implementation of language AA
T2(@NotNull String name, Type con, String[] ids, BitsAlias aliases, T2 @NotNull ... args)
int prep_tree(Syntax par, VStack nongen, Worklist work)
static TypeInt con(long con)
boolean hm(Worklist work)
boolean _fresh_unify_struct(T2 that, VStack nongen, Worklist work)
boolean unify(T2 that, Worklist work)
SB p2(SB sb, VBitSet dups)
boolean nongen_in(VStack syn)
boolean fresh_unify(T2 that, VStack nongen, Worklist work)
static int new_alias(int par)
static RuntimeException unimpl()
boolean hm(Worklist work)
boolean _occurs_in_type(T2 x)
boolean _occurs_in(Syntax syn)
void addAll(Ary<? extends Syntax > ss)
void add_work(Worklist work)
static final TypeInt INT64
static Type con(double con)
int prep_tree(Syntax par, VStack nongen, Worklist work)
boolean more_work(Worklist work)
static final VBitSet UPDATE_VISIT
Iterator< T2 > iterator()
static BitsAlias RECORD_BITS
abstract T2 lookup(String name)
final HashSet< Syntax > _work
static boolean DEBUG_LEAKS
static final HashMap< T2, T2 > CDUPS
boolean vput(T2 that, boolean progress)
Let(String arg0, Syntax def, Syntax body)
static final HashMap< T2, T2 > VARS
static boolean isAlpha1(byte c)
static void require(String s)
SB str(SB sb, VBitSet visit, VBitSet dups)
SB p2(SB sb, VBitSet dups)
SB p2(SB sb, VBitSet dups)
static TypeStr con(String con)
void prep_lookup_deps(Ident id)
static SB str(SB sb, VBitSet visit, T2 t, VBitSet dups)
boolean unify_base(T2 that, Worklist work)
void push_update(Syntax a)
abstract boolean more_work(Worklist work)
static T2 make_err(String s)
boolean more_work(Worklist work)
SB _p(SB sb, VBitSet visit, VBitSet dups)
boolean hm(Worklist work)
void prep_lookup_deps(Ident id)
SB p2(SB sb, VBitSet dups)
boolean more_work(Worklist work)
Tight/tiny StringBuilder wrapper.
VStack(VStack par, T2 nongen)
abstract SB p2(SB sb, VBitSet dups)
boolean more_work(Worklist work)
an implementation of language AA
abstract void add_work(Worklist work)
static boolean isWS(byte c)
final void prep_tree_impl(Syntax par, VStack nongen, Worklist work, T2 t)
void prep_lookup_deps(Ident id)
boolean unify_rec(int alias, T2 str, Worklist work)
static BitsAlias make0(int bit)
void prep_lookup_deps(Ident id)
void add_work(Worklist work)
boolean fresh_base(T2 that, Worklist work)
static T2 make_fun(T2... args)
void push_update_impl(Syntax a)
boolean hm(Worklist work)
static Syntax hm(String sprog)
final SB p0(SB sb, VBitSet dups)
static boolean isDigit(byte c)
SB p2(SB sb, VBitSet dups)
abstract int prep_tree(Syntax par, VStack nongen, Worklist work)
void add_work(Worklist work)
VBitSet _get_dups(VBitSet visit, VBitSet dups)
boolean _unify(T2 that, Worklist work)
int prep_tree(Syntax par, VStack nongen, Worklist work)
void add_work(Worklist work)
static T2 make_base(Type con)
boolean hm(Worklist work)
boolean more_work(Worklist work)
abstract void prep_lookup_deps(Ident id)
static final VBitSet ODUPS
Lambda(Syntax body, String... args)
boolean hm(Worklist work)
static final TypeMemPtr STRPTR
static final HashMap< String, T2 > PRIMS
void prep_lookup_deps(Ident id)
Field(String id, Syntax str)
boolean or0(T2 that, Worklist work)
boolean more_work(Worklist work)
boolean occurs_in(Syntax syn)
int prep_tree(Syntax par, VStack nongen, Worklist work)
boolean more_work(Worklist work)
boolean _fresh_unify(T2 that, VStack nongen, Worklist work)
final boolean more_work_impl(Worklist work)
void prep_lookup_deps(Ident id)
boolean occurs_in_type(T2 x)
static final TypeInt BOOL
void add_work(Worklist work)
boolean _nongen_in(VStack nongen)
Apply(Syntax fun, Syntax... args)
SB str(SB sb, VBitSet dups)
static final TypeFlt FLT64
int prep_tree(Syntax par, VStack nongen, Worklist work)
static void reset_to_init0()
void add_work(Worklist work)
boolean cycle_equals(T2 t)