FORM  4.1
smart.c
Go to the documentation of this file.
1 
12 /* #[ License : */
13 /*
14  * Copyright (C) 1984-2013 J.A.M. Vermaseren
15  * When using this file you are requested to refer to the publication
16  * J.A.M.Vermaseren "New features of FORM" math-ph/0010025
17  * This is considered a matter of courtesy as the development was paid
18  * for by FOM the Dutch physics granting agency and we would like to
19  * be able to track its scientific use to convince FOM of its value
20  * for the community.
21  *
22  * This file is part of FORM.
23  *
24  * FORM is free software: you can redistribute it and/or modify it under the
25  * terms of the GNU General Public License as published by the Free Software
26  * Foundation, either version 3 of the License, or (at your option) any later
27  * version.
28  *
29  * FORM is distributed in the hope that it will be useful, but WITHOUT ANY
30  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
31  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
32  * details.
33  *
34  * You should have received a copy of the GNU General Public License along
35  * with FORM. If not, see <http://www.gnu.org/licenses/>.
36  */
37 /* #] License : */
38 /*
39  #[ Includes : function.c
40 */
41 
42 #include "form3.h"
43 
44 /*
45  #] Includes :
46  #[ StudyPattern :
47 
48  Argument is a complete lhs of an id-statement
49  Its last word is a zero (new convention(18-may-1997)) to indicate
50  that no extra information is following. We can add there information
51  about the pattern that will help during the actual pattern matching.
52  Currently the WorkPointer points to just after this lhs.
53 
54  Task of this routine: To study the functions, their symmetry properties
55  and their wildcards to determine in which order the functions can
56  be matched best. If the order should be different we can change it here.
57 
58  Problem encountered 22-dec-2008 (JV): we don't take noncommuting
59  functions into account.
60 */
61 
62 int StudyPattern(WORD *lhs)
63 {
64  GETIDENTITY
65  WORD *fullproto, *pat, *p, *p1, *p2, *pstop, *info, f, nn;
66  int numfun = 0, numsym = 0, allwilds = 0, i, j, k, nc;
67  FUN_INFO *finf, *fmin, *f1, *f2, funscratch;
68 
69  fullproto = lhs + IDHEAD;
70 /* if ( *lhs == TYPEIF ) fullproto--; */
71  pat = fullproto + fullproto[1];
72  info = pat + *pat;
73 
74  p = pat + 1;
75  while ( p < info ) {
76  if ( *p >= FUNCTION ) {
77  numfun++;
78  nn = *p - FUNCTION;
79  if ( nn >= WILDOFFSET ) nn -= WILDOFFSET;
80 /*
81  We check here for cases that are not allowed like ?a inside
82  symmetric functions or tensors.
83 */
84  if ( ( functions[nn].symmetric == SYMMETRIC ) ||
85  ( functions[nn].symmetric == ANTISYMMETRIC ) ) {
86  p2 = p+p[1]; p1 = p+FUNHEAD;
87  while ( p1 < p2 ) {
88  if ( *p1 == FUNNYWILD ) {
89  MesPrint("&Argument field wildcards are not allowed inside (anti)symmetric functions or tensors");
90  return(1);
91  }
92  NEXTARG(p1);
93  }
94  }
95  }
96  p += p[1];
97  }
98  if ( numfun == 0 ) return(0);
99 /*
100  We need now some room for the information about the functions
101 */
102  if ( numfun > AN.numfuninfo ) {
103  if ( AN.FunInfo ) M_free(AN.FunInfo,"funinfo");
104  AN.numfuninfo = numfun + 10;
105  AN.FunInfo = (FUN_INFO *)Malloc1(AN.numfuninfo*sizeof(FUN_INFO),"funinfo");
106  }
107 /*
108  Now collect the information. First the locations.
109 */
110  p = pat + 1; i = 0;
111  while ( p < info ) {
112  if ( *p >= FUNCTION ) AN.FunInfo[i++].location = p;
113  p += p[1];
114  }
115  for ( i = 0, finf = AN.FunInfo; i < numfun; i++, finf++ ) {
116  p = finf->location;
117  pstop = p + p[1];
118  f = *p;
119  if ( f > FUNCTION+WILDOFFSET ) f -= WILDOFFSET;
120  finf->numargs = finf->numfunnies = finf->numwildcards = 0;
121  finf->symmet = functions[f-FUNCTION].symmetric;
122  finf->tensor = functions[f-FUNCTION].spec;
123  finf->commute = functions[f-FUNCTION].commute;
124  if ( finf->tensor >= TENSORFUNCTION ) {
125  p += FUNHEAD;
126  while ( p < pstop ) {
127  if ( *p == FUNNYWILD ) {
128  finf->numfunnies++; p+= 2; continue;
129  }
130  else if ( *p < 0 ) {
131  if ( *p >= AM.OffsetVector + WILDOFFSET && *p < MINSPEC ) {
132  finf->numwildcards++;
133  }
134  }
135  else {
136  if ( *p >= AM.OffsetIndex + WILDOFFSET &&
137  *p <= AM.OffsetIndex + 2*WILDOFFSET ) finf->numwildcards++;
138  }
139  finf->numargs++;
140  p++;
141  }
142  }
143  else {
144  p += FUNHEAD;
145  while ( p < pstop ) {
146  if ( *p > 0 ) { finf->numargs++; p += *p; continue; }
147  if ( *p <= -FUNCTION ) {
148  if ( *p <= -FUNCTION - WILDOFFSET ) finf->numwildcards++;
149  p++;
150  }
151  else if ( *p == -SYMBOL ) {
152  if ( p[1] >= 2*MAXPOWER ) finf->numwildcards++;
153  p += 2;
154  }
155  else if ( *p == -INDEX ) {
156  if ( p[1] >= AM.OffsetIndex + WILDOFFSET &&
157  p[1] <= AM.OffsetIndex + 2*WILDOFFSET ) finf->numwildcards++;
158  p += 2;
159  }
160  else if ( *p == -VECTOR || *p == -MINVECTOR ) {
161  if ( p[1] >= AM.OffsetVector + WILDOFFSET && p[1] < MINSPEC ) {
162  finf->numwildcards++;
163  }
164  p += 2;
165  }
166  else if ( *p == -ARGWILD ) {
167  finf->numfunnies++;
168  p += 2;
169  }
170  else { p += 2; }
171  finf->numargs++;
172  }
173  }
174  if ( finf->symmet ) {
175  numsym++;
176  allwilds += finf->numwildcards + finf->numfunnies;
177  }
178  }
179  if ( numsym == 0 ) return(0);
180  if ( allwilds == 0 ) return(0);
181 /*
182  We have the information in the array AN.FunInfo.
183  We sort things and then write the sorted pattern.
184  Of course we may not play with the order of the noncommuting functions.
185  Of course we have to become even smarter in the future and look during
186  the sorting which wildcards are asigned when.
187  But for now this should do.
188 */
189  for ( nc = numfun-1; nc >= 0; nc-- ) { if ( AN.FunInfo[nc].commute ) break; }
190 
191  finf = AN.FunInfo;
192  for ( i = nc+2; i < numfun; i++ ) {
193  fmin = finf; finf++;
194  if ( ( finf->symmet < fmin->symmet ) || (
195  ( finf->symmet == fmin->symmet ) &&
196  ( ( finf->numwildcards+finf->numfunnies < fmin->numwildcards+fmin->numfunnies )
197  || ( ( finf->numwildcards+finf->numfunnies == fmin->numwildcards+fmin->numfunnies )
198  && ( finf->numwildcards < fmin->numfunnies ) ) ) ) ) {
199  funscratch = AN.FunInfo[i];
200  AN.FunInfo[i] = AN.FunInfo[i-1];
201  AN.FunInfo[i-1] = funscratch;
202  for ( j = i-1; j > nc && j > 0; j-- ) {
203  f1 = AN.FunInfo+j;
204  f2 = f1-1;
205  if ( ( f1->symmet < f2->symmet ) || (
206  ( f1->symmet == f2->symmet ) &&
207  ( ( f1->numwildcards+f1->numfunnies < f2->numwildcards+f2->numfunnies )
208  || ( ( f1->numwildcards+f1->numfunnies == f2->numwildcards+f2->numfunnies )
209  && ( f1->numwildcards < f2->numfunnies ) ) ) ) ) {
210  funscratch = AN.FunInfo[j];
211  AN.FunInfo[j] = AN.FunInfo[j-1];
212  AN.FunInfo[j-1] = funscratch;
213  }
214  else break;
215  }
216  }
217  }
218 /*
219  Now we rewrite the pattern. First into the space after it and then we
220  copy it back. Be careful with the non-commutative functions. There the
221  worst one should decide.
222 */
223  p = pat + 1;
224  p2 = info;
225  for ( i = 0; i < numfun; i++ ) {
226  if ( i == nc ) {
227  for ( k = 0; k <= nc; k++ ) {
228  if ( AN.FunInfo[k].commute ) {
229  p1 = AN.FunInfo[k].location; j = p1[1];
230  NCOPY(p2,p1,j)
231  }
232  }
233  }
234  else if ( AN.FunInfo[i].commute == 0 ) {
235  p1 = AN.FunInfo[i].location; j = p1[1];
236  NCOPY(p2,p1,j)
237  }
238  }
239  p = pat + 1; p1 = info;
240  while ( p1 < p2 ) *p++ = *p1++;
241 /*
242  And now we place the relevant information in the info part
243 */
244  p2 = info+1;
245  for ( i = 0; i < numfun; i++ ) {
246  if ( i == nc ) {
247  for ( k = 0; k <= nc; k++ ) {
248  if ( AN.FunInfo[k].commute ) {
249  finf = AN.FunInfo + k;
250  *p2++ = finf->numargs;
251  *p2++ = finf->numwildcards;
252  *p2++ = finf->numfunnies;
253  *p2++ = finf->symmet;
254  }
255  }
256  }
257  else if ( AN.FunInfo[i].commute == 0 ) {
258  finf = AN.FunInfo + i;
259  *p2++ = finf->numargs;
260  *p2++ = finf->numwildcards;
261  *p2++ = finf->numfunnies;
262  *p2++ = finf->symmet;
263  }
264  }
265  *info = p2-info;
266  lhs[1] = p2-lhs;
267  return(0);
268 }
269 
270 /*
271  #] StudyPattern :
272  #[ MatchIsPossible :
273 
274  We come here when there are functions and there is nontrivial
275  symmetry related wildcarding.
276 */
277 
278 int MatchIsPossible(WORD *pattern, WORD *term)
279 {
280  GETIDENTITY
281  WORD *info = pattern + *pattern;
282  WORD *t, *tstop, *tt, *inf, *p;
283  int numfun = 0, inpat, i, j, numargs;
284  FUN_INFO *finf;
285 /*
286  We need a list of functions and their number of arguments
287 */
288  GETSTOP(term,tstop);
289  t = term + 1;
290  while ( t < tstop ) {
291  if ( *t >= FUNCTION ) numfun++;
292  t += t[1];
293  }
294  if ( numfun == 0 ) goto NotPossible;
295  if ( *info == SETSET ) info += info[1];
296  inpat = (*info-1)/4;
297  if ( inpat > numfun ) goto NotPossible;
298 /*
299  We need now some room for the information about the functions
300 */
301  if ( numfun > AN.numfuninfo ) {
302  if ( AN.FunInfo ) M_free(AN.FunInfo,"funinfo");
303  AN.numfuninfo = numfun + 10;
304  AN.FunInfo = (FUN_INFO *)Malloc1(AN.numfuninfo*sizeof(FUN_INFO),"funinfo");
305  }
306  t = term + 1; finf = AN.FunInfo;
307  while ( t < tstop ) {
308  if ( *t >= FUNCTION ) {
309  finf->location = t;
310  if ( functions[*t-FUNCTION].spec >= TENSORFUNCTION ) {
311  numargs = t[1]-FUNHEAD;
312  t += t[1];
313  }
314  else {
315  numargs = 0;
316  tt = t + t[1];
317  t += FUNHEAD;
318  while ( t < tt ) {
319  numargs++;
320  NEXTARG(t)
321  }
322  }
323  finf->numargs = numargs;
324  finf++;
325  }
326  else t += t[1];
327  }
328 /*
329  Now we first find a partner for each function in the pattern
330  with a fixed number of arguments
331 */
332  for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
333  if ( inf[2] ) continue;
334  if ( *p >= FUNCTION+WILDOFFSET ) continue;
335  for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
336  if ( *p == *(finf->location) && *inf == finf->numargs ) {
337  finf->numargs = -finf->numargs-1;
338  break;
339  }
340  }
341  if ( j >= numfun ) goto NotPossible;
342  }
343  for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
344  if ( inf[2] ) continue;
345  if ( *p < FUNCTION+WILDOFFSET ) continue;
346  for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
347  if ( *inf == finf->numargs ) {
348  finf->numargs = -finf->numargs-1;
349  break;
350  }
351  }
352  if ( j >= numfun ) goto NotPossible;
353  }
354  for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
355  if ( inf[2] == 0 ) continue;
356  if ( *p >= FUNCTION+WILDOFFSET ) continue;
357  for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
358  if ( *p == *(finf->location) && *inf <= finf->numargs ) {
359  finf->numargs = -finf->numargs-1;
360  break;
361  }
362  }
363  if ( j >= numfun ) goto NotPossible;
364  }
365  for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
366  if ( inf[2] == 0 ) continue;
367  if ( *p < FUNCTION+WILDOFFSET ) continue;
368  for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
369  if ( *inf <= finf->numargs ) {
370  finf->numargs = -finf->numargs-1;
371  break;
372  }
373  }
374  if ( j >= numfun ) goto NotPossible;
375  }
376 /*
377  Thus far we have determined that for each function in the pattern
378  there is a potential partner with enough arguments.
379  For now the rest is up to the real pattern matcher.
380 
381  To undo the disabling of the number of arguments we need this code
382  for ( i = 0, finf = AN.FunInfo; i < numfun; i++, finf++ ) {
383  if ( finf->numargs < 0 ) finf->numargs = -finf->numargs-1;
384  }
385 */
386  return(1);
387 NotPossible:
388 /*
389  PrintTerm(pattern,"p");
390  PrintTerm(term,"t");
391 */
392  return(0);
393 }
394 
395 /*
396  #] MatchIsPossible :
397 */